LLVM  12.0.0git
PostDominators.cpp
Go to the documentation of this file.
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 
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"
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 
36 
38  : FunctionPass(ID) {
40 }
41 
43  "Post-Dominator Tree Construction", true, true)
44 
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 
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.
70  for (; &*I != I1 && &*I != I2; ++I)
71  /*empty*/;
72 
73  return &*I == I2;
74 }
75 
77  DT.recalculate(F);
78  return false;
79 }
80 
82  if (VerifyDomInfo)
84  else if (ExpensiveChecksEnabled)
86 }
87 
89  DT.print(OS);
90 }
91 
93  return new PostDominatorTreeWrapperPass();
94 }
95 
96 AnalysisKey PostDominatorTreeAnalysis::Key;
97 
100  PostDominatorTree PDT(F);
101  return PDT;
102 }
103 
105  : OS(OS) {}
106 
109  OS << "PostDominatorTree for function: " << F.getName() << "\n";
111 
112  return PreservedAnalyses::all();
113 }
PostDominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a post dominator tree.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
F(f)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:289
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
void initializePostDominatorTreeWrapperPassPass(PassRegistry &)
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:32
INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree", "Post-Dominator Tree Construction", true, true) bool PostDominatorTree
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
void print(raw_ostream &O) const
print - Convert to human readable form
Iterator for intrusive lists based on ilist_node.
Analysis pass which computes a PostDominatorTree.
static constexpr bool ExpensiveChecksEnabled
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
#define I(x, y, z)
Definition: MD5.cpp:59
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:92
FunctionPass * createPostDomTree()
aarch64 promote const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
const BasicBlock * getParent() const
Definition: Instruction.h:94