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 21using namespace llvm; 22 23#define DEBUG_TYPE "postdomtree" 24 25#ifdef EXPENSIVE_CHECKS 26static constexpr bool ExpensiveChecksEnabled = true; 27#else 28static constexpr bool ExpensiveChecksEnabled = false; 29#endif 30 31//===----------------------------------------------------------------------===// 32// PostDominatorTree Implementation 33//===----------------------------------------------------------------------===// 34 35char PostDominatorTreeWrapperPass::ID = 0; 36 37PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass() 38 : FunctionPass(ID) { 39 initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 40} 41 42INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree", 43 "Post-Dominator Tree Construction", true, true) 44 45bool 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 54bool 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 76bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) { 77 DT.recalculate(F); 78 return false; 79} 80 81void 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 88void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const { 89 DT.print(OS); 90} 91 92FunctionPass* llvm::createPostDomTree() { 93 return new PostDominatorTreeWrapperPass(); 94} 95 96AnalysisKey PostDominatorTreeAnalysis::Key; 97 98PostDominatorTree PostDominatorTreeAnalysis::run(Function &F, 99 FunctionAnalysisManager &) { 100 PostDominatorTree PDT(F); 101 return PDT; 102} 103 104PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS) 105 : OS(OS) {} 106 107PreservedAnalyses 108PostDominatorTreePrinterPass::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