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