llvm/lib/Analysis/PostDominators.cpp

   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 }