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 40 INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree", 41 "Post-Dominator Tree Construction", true, true) 42 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 52 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 74 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) { 75 DT.recalculate(F); 76 return false; 77 } 78 79 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 86 void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { 87 DT.print(OS); 88 } 89 90 FunctionPass* llvm::createPostDomTree() { 91 return new PostDominatorTreeWrapperPass(); 92 } 93 94 AnalysisKey PostDominatorTreeAnalysis::Key; 95 96 PostDominatorTree PostDominatorTreeAnalysis::run(Function &F, 97 FunctionAnalysisManager &) { 98 PostDominatorTree PDT(F); 99 return PDT; 100 } 101 102 PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS) 103 : OS(OS) {} 104 105 PreservedAnalyses 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