1 //===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the DominatorTree class, which provides fast and efficient
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_IR_DOMINATORS_H
16 #define LLVM_IR_DOMINATORS_H
18 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/ADT/DepthFirstIterator.h"
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/Hashing.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/GenericDomTree.h"
36 extern template class DomTreeNodeBase<BasicBlock>;
37 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
38 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
40 namespace DomTreeBuilder {
41 using BBDomTree = DomTreeBase<BasicBlock>;
42 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
44 extern template struct Update<BasicBlock *>;
46 using BBUpdates = ArrayRef<Update<BasicBlock *>>;
48 extern template void Calculate<BBDomTree>(BBDomTree &DT);
49 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
51 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
53 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
57 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
59 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
63 extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
64 extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
66 extern template bool Verify<BBDomTree>(const BBDomTree &DT,
67 BBDomTree::VerificationLevel VL);
68 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
69 BBPostDomTree::VerificationLevel VL);
70 } // namespace DomTreeBuilder
72 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
74 class BasicBlockEdge {
75 const BasicBlock *Start;
76 const BasicBlock *End;
79 BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
80 Start(Start_), End(End_) {}
82 BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
83 : Start(Pair.first), End(Pair.second) {}
85 BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
86 : Start(Pair.first), End(Pair.second) {}
88 const BasicBlock *getStart() const {
92 const BasicBlock *getEnd() const {
96 /// Check if this is the only edge between Start and End.
97 bool isSingleEdge() const;
100 template <> struct DenseMapInfo<BasicBlockEdge> {
101 using BBInfo = DenseMapInfo<const BasicBlock *>;
103 static unsigned getHashValue(const BasicBlockEdge *V);
105 static inline BasicBlockEdge getEmptyKey() {
106 return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
109 static inline BasicBlockEdge getTombstoneKey() {
110 return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
113 static unsigned getHashValue(const BasicBlockEdge &Edge) {
114 return hash_combine(BBInfo::getHashValue(Edge.getStart()),
115 BBInfo::getHashValue(Edge.getEnd()));
118 static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
119 return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
120 BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
124 /// Concrete subclass of DominatorTreeBase that is used to compute a
125 /// normal dominator tree.
127 /// Definition: A block is said to be forward statically reachable if there is
128 /// a path from the entry of the function to the block. A statically reachable
129 /// block may become statically unreachable during optimization.
131 /// A forward unreachable block may appear in the dominator tree, or it may
132 /// not. If it does, dominance queries will return results as if all reachable
133 /// blocks dominate it. When asking for a Node corresponding to a potentially
134 /// unreachable block, calling code must handle the case where the block was
135 /// unreachable and the result of getNode() is nullptr.
137 /// Generally, a block known to be unreachable when the dominator tree is
138 /// constructed will not be in the tree. One which becomes unreachable after
139 /// the dominator tree is initially constructed may still exist in the tree,
140 /// even if the tree is properly updated. Calling code should not rely on the
141 /// preceding statements; this is stated only to assist human understanding.
142 class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
144 using Base = DominatorTreeBase<BasicBlock, false>;
146 DominatorTree() = default;
147 explicit DominatorTree(Function &F) { recalculate(F); }
149 /// Handle invalidation explicitly.
150 bool invalidate(Function &F, const PreservedAnalyses &PA,
151 FunctionAnalysisManager::Invalidator &);
153 // Ensure base-class overloads are visible.
154 using Base::dominates;
156 /// Return true if Def dominates a use in User.
158 /// This performs the special checks necessary if Def and User are in the same
159 /// basic block. Note that Def doesn't dominate a use in Def itself!
160 bool dominates(const Instruction *Def, const Use &U) const;
161 bool dominates(const Instruction *Def, const Instruction *User) const;
162 bool dominates(const Instruction *Def, const BasicBlock *BB) const;
164 /// Return true if an edge dominates a use.
166 /// If BBE is not a unique edge between start and end of the edge, it can
167 /// never dominate the use.
168 bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
169 bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
171 // Ensure base class overloads are visible.
172 using Base::isReachableFromEntry;
174 /// Provide an overload for a Use.
175 bool isReachableFromEntry(const Use &U) const;
177 // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
178 void viewGraph(const Twine &Name, const Twine &Title);
182 //===-------------------------------------
183 // DominatorTree GraphTraits specializations so the DominatorTree can be
184 // iterable by generic graph iterators.
186 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
187 using NodeRef = Node *;
188 using ChildIteratorType = ChildIterator;
189 using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
191 static NodeRef getEntryNode(NodeRef N) { return N; }
192 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
193 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
195 static nodes_iterator nodes_begin(NodeRef N) {
196 return df_begin(getEntryNode(N));
199 static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
203 struct GraphTraits<DomTreeNode *>
204 : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
207 struct GraphTraits<const DomTreeNode *>
208 : public DomTreeGraphTraitsBase<const DomTreeNode,
209 DomTreeNode::const_iterator> {};
211 template <> struct GraphTraits<DominatorTree*>
212 : public GraphTraits<DomTreeNode*> {
213 static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
215 static nodes_iterator nodes_begin(DominatorTree *N) {
216 return df_begin(getEntryNode(N));
219 static nodes_iterator nodes_end(DominatorTree *N) {
220 return df_end(getEntryNode(N));
224 /// Analysis pass which computes a \c DominatorTree.
225 class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
226 friend AnalysisInfoMixin<DominatorTreeAnalysis>;
227 static AnalysisKey Key;
230 /// Provide the result typedef for this analysis pass.
231 using Result = DominatorTree;
233 /// Run the analysis pass over a function and produce a dominator tree.
234 DominatorTree run(Function &F, FunctionAnalysisManager &);
237 /// Printer pass for the \c DominatorTree.
238 class DominatorTreePrinterPass
239 : public PassInfoMixin<DominatorTreePrinterPass> {
243 explicit DominatorTreePrinterPass(raw_ostream &OS);
245 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
248 /// Verifier pass for the \c DominatorTree.
249 struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
250 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
253 /// Legacy analysis pass which computes a \c DominatorTree.
254 class DominatorTreeWrapperPass : public FunctionPass {
260 DominatorTreeWrapperPass() : FunctionPass(ID) {
261 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
264 DominatorTree &getDomTree() { return DT; }
265 const DominatorTree &getDomTree() const { return DT; }
267 bool runOnFunction(Function &F) override;
269 void verifyAnalysis() const override;
271 void getAnalysisUsage(AnalysisUsage &AU) const override {
272 AU.setPreservesAll();
275 void releaseMemory() override { DT.releaseMemory(); }
277 void print(raw_ostream &OS, const Module *M = nullptr) const override;
280 //===-------------------------------------
281 /// Class to defer updates to a DominatorTree.
283 /// Definition: Applying updates to every edge insertion and deletion is
284 /// expensive and not necessary. When one needs the DominatorTree for analysis
285 /// they can request a flush() to perform a larger batch update. This has the
286 /// advantage of the DominatorTree inspecting the set of updates to find
287 /// duplicates or unnecessary subtree updates.
289 /// The scope of DeferredDominance operates at a Function level.
291 /// It is not necessary for the user to scrub the updates for duplicates or
292 /// updates that point to the same block (Delete, BB_A, BB_A). Performance
293 /// can be gained if the caller attempts to batch updates before submitting
294 /// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
297 /// It is required for the state of the LLVM IR to be applied *before*
298 /// submitting updates. The update routines must analyze the current state
299 /// between a pair of (From, To) basic blocks to determine if the update
300 /// needs to be queued.
302 /// TerminatorInstructionBB->removeFromParent();
303 /// DDT->deleteEdge(BB, Successor);
305 /// DDT->deleteEdge(BB, Successor);
306 /// TerminatorInstructionBB->removeFromParent();
307 class DeferredDominance {
309 DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
311 /// Queues multiple updates and discards duplicates.
312 void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
314 /// Helper method for a single edge insertion. It's almost always
315 /// better to batch updates and call applyUpdates to quickly remove duplicate
316 /// edges. This is best used when there is only a single insertion needed to
317 /// update Dominators.
318 void insertEdge(BasicBlock *From, BasicBlock *To);
320 /// Helper method for a single edge deletion. It's almost always better
321 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
322 /// This is best used when there is only a single deletion needed to update
324 void deleteEdge(BasicBlock *From, BasicBlock *To);
326 /// Delays the deletion of a basic block until a flush() event.
327 void deleteBB(BasicBlock *DelBB);
329 /// Returns true if DelBB is awaiting deletion at a flush() event.
330 bool pendingDeletedBB(BasicBlock *DelBB);
332 /// Returns true if pending DT updates are queued for a flush() event.
335 /// Flushes all pending updates and block deletions. Returns a
336 /// correct DominatorTree reference to be used by the caller for analysis.
337 DominatorTree &flush();
339 /// Drops all internal state and forces a (slow) recalculation of the
340 /// DominatorTree based on the current state of the LLVM IR in F. This should
341 /// only be used in corner cases such as the Entry block of F being deleted.
342 void recalculate(Function &F);
344 /// Debug method to help view the state of pending updates.
345 LLVM_DUMP_METHOD void dump() const;
349 SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
350 SmallPtrSet<BasicBlock *, 8> DeletedBBs;
352 /// Apply an update (Kind, From, To) to the internal queued updates. The
353 /// update is only added when determined to be necessary. Checks for
354 /// self-domination, unnecessary updates, duplicate requests, and balanced
355 /// pairs of requests are all performed. Returns true if the update is
356 /// queued and false if it is discarded.
357 bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
360 /// Performs all pending basic block deletions. We have to defer the deletion
361 /// of these blocks until after the DominatorTree updates are applied. The
362 /// internal workings of the DominatorTree code expect every update's From
363 /// and To blocks to exist and to be a member of the same Function.
367 } // end namespace llvm
369 #endif // LLVM_IR_DOMINATORS_H