LLVM  14.0.0git
Dominators.h
Go to the documentation of this file.
1 //===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===//
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 defines the DominatorTree class, which provides fast and efficient
10 // dominance queries.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_IR_DOMINATORS_H
15 #define LLVM_IR_DOMINATORS_H
16 
17 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/Hashing.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/PassManager.h"
24 #include "llvm/Pass.h"
26 #include <utility>
27 
28 namespace llvm {
29 
30 class Function;
31 class Instruction;
32 class Module;
33 class raw_ostream;
34 
35 extern template class DomTreeNodeBase<BasicBlock>;
36 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
37 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
38 
39 extern template class cfg::Update<BasicBlock *>;
40 
41 namespace DomTreeBuilder {
44 
46 
49 
50 extern template void Calculate<BBDomTree>(BBDomTree &DT);
51 extern template void CalculateWithUpdates<BBDomTree>(BBDomTree &DT,
52  BBUpdates U);
53 
54 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
55 
56 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
57  BasicBlock *To);
58 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
60  BasicBlock *To);
61 
62 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
63  BasicBlock *To);
64 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
66  BasicBlock *To);
67 
68 extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT,
71 extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT,
74 
75 extern template bool Verify<BBDomTree>(const BBDomTree &DT,
77 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
79 } // namespace DomTreeBuilder
80 
82 
84  const BasicBlock *Start;
85  const BasicBlock *End;
86 
87 public:
88  BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
89  Start(Start_), End(End_) {}
90 
91  BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
92  : Start(Pair.first), End(Pair.second) {}
93 
94  BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
95  : Start(Pair.first), End(Pair.second) {}
96 
97  const BasicBlock *getStart() const {
98  return Start;
99  }
100 
101  const BasicBlock *getEnd() const {
102  return End;
103  }
104 
105  /// Check if this is the only edge between Start and End.
106  bool isSingleEdge() const;
107 };
108 
109 template <> struct DenseMapInfo<BasicBlockEdge> {
111 
112  static unsigned getHashValue(const BasicBlockEdge *V);
113 
114  static inline BasicBlockEdge getEmptyKey() {
115  return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
116  }
117 
118  static inline BasicBlockEdge getTombstoneKey() {
119  return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
120  }
121 
122  static unsigned getHashValue(const BasicBlockEdge &Edge) {
123  return hash_combine(BBInfo::getHashValue(Edge.getStart()),
124  BBInfo::getHashValue(Edge.getEnd()));
125  }
126 
127  static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
128  return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
129  BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
130  }
131 };
132 
133 /// Concrete subclass of DominatorTreeBase that is used to compute a
134 /// normal dominator tree.
135 ///
136 /// Definition: A block is said to be forward statically reachable if there is
137 /// a path from the entry of the function to the block. A statically reachable
138 /// block may become statically unreachable during optimization.
139 ///
140 /// A forward unreachable block may appear in the dominator tree, or it may
141 /// not. If it does, dominance queries will return results as if all reachable
142 /// blocks dominate it. When asking for a Node corresponding to a potentially
143 /// unreachable block, calling code must handle the case where the block was
144 /// unreachable and the result of getNode() is nullptr.
145 ///
146 /// Generally, a block known to be unreachable when the dominator tree is
147 /// constructed will not be in the tree. One which becomes unreachable after
148 /// the dominator tree is initially constructed may still exist in the tree,
149 /// even if the tree is properly updated. Calling code should not rely on the
150 /// preceding statements; this is stated only to assist human understanding.
152  public:
154 
155  DominatorTree() = default;
156  explicit DominatorTree(Function &F) { recalculate(F); }
158  recalculate(*DT.Parent, U);
159  }
160 
161  /// Handle invalidation explicitly.
162  bool invalidate(Function &F, const PreservedAnalyses &PA,
164 
165  // Ensure base-class overloads are visible.
166  using Base::dominates;
167 
168  /// Return true if the (end of the) basic block BB dominates the use U.
169  bool dominates(const BasicBlock *BB, const Use &U) const;
170 
171  /// Return true if value Def dominates use U, in the sense that Def is
172  /// available at U, and could be substituted as the used value without
173  /// violating the SSA dominance requirement.
174  ///
175  /// In particular, it is worth noting that:
176  /// * Non-instruction Defs dominate everything.
177  /// * Def does not dominate a use in Def itself (outside of degenerate cases
178  /// like unreachable code or trivial phi cycles).
179  /// * Invoke/callbr Defs only dominate uses in their default destination.
180  bool dominates(const Value *Def, const Use &U) const;
181  /// Return true if value Def dominates all possible uses inside instruction
182  /// User. Same comments as for the Use-based API apply.
183  bool dominates(const Value *Def, const Instruction *User) const;
184  // Does not accept Value to avoid ambiguity with dominance checks between
185  // two basic blocks.
186  bool dominates(const Instruction *Def, const BasicBlock *BB) const;
187 
188  /// Return true if an edge dominates a use.
189  ///
190  /// If BBE is not a unique edge between start and end of the edge, it can
191  /// never dominate the use.
192  bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
193  bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
194  /// Returns true if edge \p BBE1 dominates edge \p BBE2.
195  bool dominates(const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const;
196 
197  // Ensure base class overloads are visible.
198  using Base::isReachableFromEntry;
199 
200  /// Provide an overload for a Use.
201  bool isReachableFromEntry(const Use &U) const;
202 
203  // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
204  void viewGraph(const Twine &Name, const Twine &Title);
205  void viewGraph();
206 };
207 
208 //===-------------------------------------
209 // DominatorTree GraphTraits specializations so the DominatorTree can be
210 // iterable by generic graph iterators.
211 
212 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
213  using NodeRef = Node *;
214  using ChildIteratorType = ChildIterator;
216 
217  static NodeRef getEntryNode(NodeRef N) { return N; }
218  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
219  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
220 
222  return df_begin(getEntryNode(N));
223  }
224 
225  static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
226 };
227 
228 template <>
231 };
232 
233 template <>
235  : public DomTreeGraphTraitsBase<const DomTreeNode,
237 
238 template <> struct GraphTraits<DominatorTree*>
239  : public GraphTraits<DomTreeNode*> {
240  static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
241 
243  return df_begin(getEntryNode(N));
244  }
245 
247  return df_end(getEntryNode(N));
248  }
249 };
250 
251 /// Analysis pass which computes a \c DominatorTree.
252 class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
254  static AnalysisKey Key;
255 
256 public:
257  /// Provide the result typedef for this analysis pass.
259 
260  /// Run the analysis pass over a function and produce a dominator tree.
262 };
263 
264 /// Printer pass for the \c DominatorTree.
266  : public PassInfoMixin<DominatorTreePrinterPass> {
267  raw_ostream &OS;
268 
269 public:
271 
273 };
274 
275 /// Verifier pass for the \c DominatorTree.
276 struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
278 };
279 
280 /// Enables verification of dominator trees.
281 ///
282 /// This check is expensive and is disabled by default. `-verify-dom-info`
283 /// allows selectively enabling the check without needing to recompile.
284 extern bool VerifyDomInfo;
285 
286 /// Legacy analysis pass which computes a \c DominatorTree.
288  DominatorTree DT;
289 
290 public:
291  static char ID;
292 
294 
295  DominatorTree &getDomTree() { return DT; }
296  const DominatorTree &getDomTree() const { return DT; }
297 
298  bool runOnFunction(Function &F) override;
299 
300  void verifyAnalysis() const override;
301 
302  void getAnalysisUsage(AnalysisUsage &AU) const override {
303  AU.setPreservesAll();
304  }
305 
306  void releaseMemory() override { DT.reset(); }
307 
308  void print(raw_ostream &OS, const Module *M = nullptr) const override;
309 };
310 } // end namespace llvm
311 
312 #endif // LLVM_IR_DOMINATORS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::DominatorTreeWrapperPass::ID
static char ID
Definition: Dominators.h:291
llvm::DomTreeBuilder::Verify< BBPostDomTree >
template bool Verify< BBPostDomTree >(const BBPostDomTree &DT, BBPostDomTree::VerificationLevel VL)
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::DenseMapInfo< BasicBlockEdge >::isEqual
static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS)
Definition: Dominators.h:127
llvm::DominatorTreeWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: Dominators.h:306
llvm::GraphTraits< DomTreeNode * >
Definition: Dominators.h:229
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::DomTreeBuilder::CalculateWithUpdates< BBDomTree >
template void CalculateWithUpdates< BBDomTree >(BBDomTree &DT, BBUpdates U)
llvm::DominatorTreeWrapperPass::getDomTree
const DominatorTree & getDomTree() const
Definition: Dominators.h:296
llvm::Function
Definition: Function.h:62
Pass.h
llvm::DomTreeNode
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:81
llvm::DomTreeBuilder::ApplyUpdates< BBPostDomTree >
template void ApplyUpdates< BBPostDomTree >(BBPostDomTree &DT, BBPostDomTreeGraphDiff &, BBPostDomTreeGraphDiff *)
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:223
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::DomTreeGraphTraitsBase< const VPDomTreeNode, VPDomTreeNode::const_iterator >::ChildIteratorType
VPDomTreeNode::const_iterator ChildIteratorType
Definition: Dominators.h:214
llvm::BasicBlockEdge
Definition: Dominators.h:83
llvm::DominatorTreeWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Dominators.h:302
Hashing.h
llvm::DominatorTreePrinterPass
Printer pass for the DominatorTree.
Definition: Dominators.h:265
DepthFirstIterator.h
llvm::DominatorTreeWrapperPass::print
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:417
llvm::DomTreeGraphTraitsBase::nodes_end
static nodes_iterator nodes_end(NodeRef N)
Definition: Dominators.h:225
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::GraphDiff
Definition: CFGDiff.h:57
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
GraphTraits.h
llvm::GraphTraits< DominatorTree * >::getEntryNode
static NodeRef getEntryNode(DominatorTree *DT)
Definition: Dominators.h:240
llvm::DominatorTree::DominatorTree
DominatorTree(Function &F)
Definition: Dominators.h:156
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::DenseMapInfo< BasicBlockEdge >::getEmptyKey
static BasicBlockEdge getEmptyKey()
Definition: Dominators.h:114
llvm::DomTreeBuilder::InsertEdge< BBDomTree >
template void InsertEdge< BBDomTree >(BBDomTree &DT, BasicBlock *From, BasicBlock *To)
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::User
Definition: User.h:44
llvm::DomTreeGraphTraitsBase
Definition: Dominators.h:212
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::BasicBlockEdge::BasicBlockEdge
BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_)
Definition: Dominators.h:88
llvm::DomTreeBuilder::DeleteEdge< BBPostDomTree >
template void DeleteEdge< BBPostDomTree >(BBPostDomTree &DT, BasicBlock *From, BasicBlock *To)
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
dominates
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
Definition: RegAllocFast.cpp:340
llvm::BasicBlockEdge::getStart
const BasicBlock * getStart() const
Definition: Dominators.h:97
llvm::DomTreeBuilder::Verify< BBDomTree >
template bool Verify< BBDomTree >(const BBDomTree &DT, BBDomTree::VerificationLevel VL)
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::DominatorTreePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:371
llvm::DomTreeBuilder::DeleteEdge< BBDomTree >
template void DeleteEdge< BBDomTree >(BBDomTree &DT, BasicBlock *From, BasicBlock *To)
CFG.h
BasicBlock.h
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::DominatorTree::DominatorTree
DominatorTree(DominatorTree &DT, DomTreeBuilder::BBUpdates U)
Definition: Dominators.h:157
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:218
llvm::BasicBlockEdge::BasicBlockEdge
BasicBlockEdge(const std::pair< BasicBlock *, BasicBlock * > &Pair)
Definition: Dominators.h:91
llvm::DenseMapInfo< BasicBlockEdge >::getHashValue
static unsigned getHashValue(const BasicBlockEdge &Edge)
Definition: Dominators.h:122
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::DominatorTreeAnalysis::run
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:360
llvm::DominatorTreeBase::reset
void reset()
Definition: GenericDomTree.h:806
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::BasicBlockEdge::BasicBlockEdge
BasicBlockEdge(const std::pair< const BasicBlock *, const BasicBlock * > &Pair)
Definition: Dominators.h:94
llvm::BasicBlockEdge::getEnd
const BasicBlock * getEnd() const
Definition: Dominators.h:101
llvm::DomTreeGraphTraitsBase::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:217
llvm::DominatorTreeWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:410
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::DominatorTreeBase::Parent
ParentPtr Parent
Definition: GenericDomTree.h:255
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
Node
Definition: ItaniumDemangle.h:235
llvm::GraphTraits< DominatorTree * >::nodes_begin
static nodes_iterator nodes_begin(DominatorTree *N)
Definition: Dominators.h:242
llvm::DomTreeNodeBase< BasicBlock >
llvm::DomTreeGraphTraitsBase::nodes_begin
static nodes_iterator nodes_begin(NodeRef N)
Definition: Dominators.h:221
llvm::DominatorTreeWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
GenericDomTree.h
llvm::DenseMapInfo< BasicBlockEdge >::getTombstoneKey
static BasicBlockEdge getTombstoneKey()
Definition: Dominators.h:118
PassManager.h
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1856
llvm::DominatorTreeWrapperPass::getDomTree
DominatorTree & getDomTree()
Definition: Dominators.h:295
llvm::DominatorTreeBase::VerificationLevel
VerificationLevel
Definition: GenericDomTree.h:245
llvm::DenseMapInfo< BasicBlockEdge >
Definition: Dominators.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::DomTreeBuilder::Calculate< BBPostDomTree >
template void Calculate< BBPostDomTree >(BBPostDomTree &DT)
llvm::DomTreeNodeBase< BasicBlock >::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
llvm::DominatorTreePrinterPass::DominatorTreePrinterPass
DominatorTreePrinterPass(raw_ostream &OS)
Definition: Dominators.cpp:369
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::DomTreeBuilder::ApplyUpdates< BBDomTree >
template void ApplyUpdates< BBDomTree >(BBDomTree &DT, BBDomTreeGraphDiff &, BBDomTreeGraphDiff *)
llvm::DomTreeGraphTraitsBase::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:219
N
#define N
llvm::GraphTraits< DominatorTree * >::nodes_end
static nodes_iterator nodes_end(DominatorTree *N)
Definition: Dominators.h:246
DenseMapInfo.h
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
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits
Definition: GraphTraits.h:35
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DomTreeBuilder::Calculate< BBDomTree >
template void Calculate< BBDomTree >(BBDomTree &DT)
llvm::DominatorTreeVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:379
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::DomTreeGraphTraitsBase::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:218
llvm::DominatorTreeVerifierPass
Verifier pass for the DominatorTree.
Definition: Dominators.h:276
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::VerifyDomInfo
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:32
llvm::DomTreeBuilder::InsertEdge< BBPostDomTree >
template void InsertEdge< BBPostDomTree >(BBPostDomTree &DT, BasicBlock *From, BasicBlock *To)
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::DominatorTreeWrapperPass::DominatorTreeWrapperPass
DominatorTreeWrapperPass()
Definition: Dominators.cpp:398