LLVM  14.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 
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 
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 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::print
void print(raw_ostream &O) const
print - Convert to human readable form
Definition: GenericDomTree.h:709
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::PostDominatorTreeAnalysis::run
PostDominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a post dominator tree.
Definition: PostDominators.cpp:98
llvm::Function
Definition: Function.h:61
Pass.h
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
llvm::PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass
PostDominatorTreeWrapperPass()
Definition: PostDominators.cpp:37
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PostDominatorTreeWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: PostDominators.cpp:76
PostDominators.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::PostDominatorTreeWrapperPass::DT
PostDominatorTree DT
Definition: PostDominators.h:76
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::createPostDomTree
FunctionPass * createPostDomTree()
Definition: PostDominators.cpp:92
llvm::PostDominatorTreeWrapperPass::print
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: PostDominators.cpp:88
llvm::PostDominatorTreePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PostDominators.cpp:108
llvm::PostDominatorTreeWrapperPass::ID
static char ID
Definition: PostDominators.h:74
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::DominatorTreeBase::recalculate
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Definition: GenericDomTree.h:778
ExpensiveChecksEnabled
static constexpr bool ExpensiveChecksEnabled
Definition: PostDominators.cpp:28
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::DominatorTreeBase::dominates
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
Definition: GenericDomTree.h:416
llvm::PostDominatorTreeWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: PostDominators.cpp:81
llvm::PostDominatorTreePrinterPass::PostDominatorTreePrinterPass
PostDominatorTreePrinterPass(raw_ostream &OS)
Definition: PostDominators.cpp:104
llvm::DominatorTreeBase::VerificationLevel::Basic
@ Basic
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Function.h
PassManager.h
llvm::initializePostDominatorTreeWrapperPassPass
void initializePostDominatorTreeWrapperPassPass(PassRegistry &)
INITIALIZE_PASS
INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree", "Post-Dominator Tree Construction", true, true) bool PostDominatorTree
Definition: PostDominators.cpp:42
Instructions.h
llvm::DominatorTreeBase::VerificationLevel::Full
@ Full
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::PostDominatorTreeAnalysis
Analysis pass which computes a PostDominatorTree.
Definition: PostDominators.h:47
raw_ostream.h
llvm::PostDominatorTree::dominates
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
Definition: PostDominators.cpp:54
InitializePasses.h
llvm::VerifyDomInfo
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:32
llvm::BasicBlock::const_iterator
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:91
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37