PostDominators.cpp revision 360784 
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