1 //===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the post-dominator construction algorithms.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/Analysis/PostDominators.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/PassManager.h"
17 #include "llvm/InitializePasses.h"
18 #include "llvm/Pass.h"
19 #include "llvm/Support/raw_ostream.h"
20
21 using namespace llvm;
22
23 #define DEBUG_TYPE "postdomtree"
24
25 #ifdef EXPENSIVE_CHECKS
26 static constexpr bool ExpensiveChecksEnabled = true;
27 #else
28 static constexpr bool ExpensiveChecksEnabled = false;
29 #endif
30
31 //===----------------------------------------------------------------------===//
32 // PostDominatorTree Implementation
33 //===----------------------------------------------------------------------===//
34
35 char PostDominatorTreeWrapperPass::ID = 0;
36
PostDominatorTreeWrapperPass()37 PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass()
38 : FunctionPass(ID) {}
39
40 INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",
41 "Post-Dominator Tree Construction", true, true)
42
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator &)43 bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
44 FunctionAnalysisManager::Invalidator &) {
45 // Check whether the analysis, all analyses on functions, or the function's
46 // CFG have been preserved.
47 auto PAC = PA.getChecker<PostDominatorTreeAnalysis>();
48 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
49 PAC.preservedSet<CFGAnalyses>());
50 }
51
dominates(const Instruction * I1,const Instruction * I2) const52 bool PostDominatorTree::dominates(const Instruction *I1,
53 const Instruction *I2) const {
54 assert(I1 && I2 && "Expecting valid I1 and I2");
55
56 const BasicBlock *BB1 = I1->getParent();
57 const BasicBlock *BB2 = I2->getParent();
58
59 if (BB1 != BB2)
60 return Base::dominates(BB1, BB2);
61
62 // PHINodes in a block are unordered.
63 if (isa<PHINode>(I1) && isa<PHINode>(I2))
64 return false;
65
66 // Loop through the basic block until we find I1 or I2.
67 BasicBlock::const_iterator I = BB1->begin();
68 for (; &*I != I1 && &*I != I2; ++I)
69 /*empty*/;
70
71 return &*I == I2;
72 }
73
runOnFunction(Function & F)74 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
75 DT.recalculate(F);
76 return false;
77 }
78
verifyAnalysis() const79 void PostDominatorTreeWrapperPass::verifyAnalysis() const {
80 if (VerifyDomInfo)
81 assert(DT.verify(PostDominatorTree::VerificationLevel::Full));
82 else if (ExpensiveChecksEnabled)
83 assert(DT.verify(PostDominatorTree::VerificationLevel::Basic));
84 }
85
print(raw_ostream & OS,const Module *) const86 void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
87 DT.print(OS);
88 }
89
createPostDomTree()90 FunctionPass* llvm::createPostDomTree() {
91 return new PostDominatorTreeWrapperPass();
92 }
93
94 AnalysisKey PostDominatorTreeAnalysis::Key;
95
run(Function & F,FunctionAnalysisManager &)96 PostDominatorTree PostDominatorTreeAnalysis::run(Function &F,
97 FunctionAnalysisManager &) {
98 PostDominatorTree PDT(F);
99 return PDT;
100 }
101
PostDominatorTreePrinterPass(raw_ostream & OS)102 PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS)
103 : OS(OS) {}
104
105 PreservedAnalyses
run(Function & F,FunctionAnalysisManager & AM)106 PostDominatorTreePrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
107 OS << "PostDominatorTree for function: " << F.getName() << "\n";
108 AM.getResult<PostDominatorTreeAnalysis>(F).print(OS);
109
110 return PreservedAnalyses::all();
111 }
112