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 
37 PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass()
38     : FunctionPass(ID) {
39   initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
40 }
41 
42 INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",
43                 "Post-Dominator Tree Construction", true, true)
44 
45 bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
46                                    FunctionAnalysisManager::Invalidator &) {
47   // Check whether the analysis, all analyses on functions, or the function's
48   // CFG have been preserved.
49   auto PAC = PA.getChecker<PostDominatorTreeAnalysis>();
50   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
51            PAC.preservedSet<CFGAnalyses>());
52 }
53 
54 bool PostDominatorTree::dominates(const Instruction *I1,
55                                   const Instruction *I2) const {
56   assert(I1 && I2 && "Expecting valid I1 and I2");
57 
58   const BasicBlock *BB1 = I1->getParent();
59   const BasicBlock *BB2 = I2->getParent();
60 
61   if (BB1 != BB2)
62     return Base::dominates(BB1, BB2);
63 
64   // PHINodes in a block are unordered.
65   if (isa<PHINode>(I1) && isa<PHINode>(I2))
66     return false;
67 
68   // Loop through the basic block until we find I1 or I2.
69   BasicBlock::const_iterator I = BB1->begin();
70   for (; &*I != I1 && &*I != I2; ++I)
71     /*empty*/;
72 
73   return &*I == I2;
74 }
75 
76 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
77   DT.recalculate(F);
78   return false;
79 }
80 
81 void PostDominatorTreeWrapperPass::verifyAnalysis() const {
82   if (VerifyDomInfo)
83     assert(DT.verify(PostDominatorTree::VerificationLevel::Full));
84   else if (ExpensiveChecksEnabled)
85     assert(DT.verify(PostDominatorTree::VerificationLevel::Basic));
86 }
87 
88 void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
89   DT.print(OS);
90 }
91 
92 FunctionPass* llvm::createPostDomTree() {
93   return new PostDominatorTreeWrapperPass();
94 }
95 
96 AnalysisKey PostDominatorTreeAnalysis::Key;
97 
98 PostDominatorTree PostDominatorTreeAnalysis::run(Function &F,
99                                                  FunctionAnalysisManager &) {
100   PostDominatorTree PDT(F);
101   return PDT;
102 }
103 
104 PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS)
105   : OS(OS) {}
106 
107 PreservedAnalyses
108 PostDominatorTreePrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
109   OS << "PostDominatorTree for function: " << F.getName() << "\n";
110   AM.getResult<PostDominatorTreeAnalysis>(F).print(OS);
111 
112   return PreservedAnalyses::all();
113 }
114