LLVM  7.0.0svn
Dominators.h
Go to the documentation of this file.
1 //===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the DominatorTree class, which provides fast and efficient
11 // dominance queries.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_IR_DOMINATORS_H
16 #define LLVM_IR_DOMINATORS_H
17 
18 #include "llvm/ADT/DenseMapInfo.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"
27 #include <utility>
28 
29 namespace llvm {
30 
31 class Function;
32 class Instruction;
33 class Module;
34 class raw_ostream;
35 
36 extern template class DomTreeNodeBase<BasicBlock>;
37 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
38 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
39 
40 namespace DomTreeBuilder {
43 
44 extern template struct Update<BasicBlock *>;
45 
47 
48 extern template void Calculate<BBDomTree>(BBDomTree &DT);
49 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
50 
51 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
52  BasicBlock *To);
53 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
54  BasicBlock *From,
55  BasicBlock *To);
56 
57 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
58  BasicBlock *To);
59 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
60  BasicBlock *From,
61  BasicBlock *To);
62 
63 extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
64 extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
65 
66 extern template bool Verify<BBDomTree>(const BBDomTree &DT,
68 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
70 } // namespace DomTreeBuilder
71 
73 
75  const BasicBlock *Start;
76  const BasicBlock *End;
77 
78 public:
79  BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
80  Start(Start_), End(End_) {}
81 
82  BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
83  : Start(Pair.first), End(Pair.second) {}
84 
85  BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
86  : Start(Pair.first), End(Pair.second) {}
87 
88  const BasicBlock *getStart() const {
89  return Start;
90  }
91 
92  const BasicBlock *getEnd() const {
93  return End;
94  }
95 
96  /// Check if this is the only edge between Start and End.
97  bool isSingleEdge() const;
98 };
99 
100 template <> struct DenseMapInfo<BasicBlockEdge> {
102 
103  static unsigned getHashValue(const BasicBlockEdge *V);
104 
105  static inline BasicBlockEdge getEmptyKey() {
106  return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
107  }
108 
109  static inline BasicBlockEdge getTombstoneKey() {
110  return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
111  }
112 
113  static unsigned getHashValue(const BasicBlockEdge &Edge) {
114  return hash_combine(BBInfo::getHashValue(Edge.getStart()),
115  BBInfo::getHashValue(Edge.getEnd()));
116  }
117 
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());
121  }
122 };
123 
124 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
125 /// normal dominator tree.
126 ///
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.
130 ///
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.
136 ///
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.
143  public:
145 
146  DominatorTree() = default;
147  explicit DominatorTree(Function &F) { recalculate(F); }
148 
149  /// Handle invalidation explicitly.
150  bool invalidate(Function &F, const PreservedAnalyses &PA,
152 
153  // Ensure base-class overloads are visible.
154  using Base::dominates;
155 
156  /// \brief Return true if Def dominates a use in User.
157  ///
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;
163 
164  /// Return true if an edge dominates a use.
165  ///
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;
170 
171  // Ensure base class overloads are visible.
172  using Base::isReachableFromEntry;
173 
174  /// \brief Provide an overload for a Use.
175  bool isReachableFromEntry(const Use &U) const;
176 
177  // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
178  void viewGraph(const Twine &Name, const Twine &Title);
179  void viewGraph();
180 };
181 
182 //===-------------------------------------
183 // DominatorTree GraphTraits specializations so the DominatorTree can be
184 // iterable by generic graph iterators.
185 
186 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
187  using NodeRef = Node *;
188  using ChildIteratorType = ChildIterator;
190 
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(); }
194 
196  return df_begin(getEntryNode(N));
197  }
198 
199  static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
200 };
201 
202 template <>
205 
206 template <>
208  : public DomTreeGraphTraitsBase<const DomTreeNode,
210 
211 template <> struct GraphTraits<DominatorTree*>
212  : public GraphTraits<DomTreeNode*> {
213  static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
214 
215  static nodes_iterator nodes_begin(DominatorTree *N) {
216  return df_begin(getEntryNode(N));
217  }
218 
219  static nodes_iterator nodes_end(DominatorTree *N) {
220  return df_end(getEntryNode(N));
221  }
222 };
223 
224 /// \brief Analysis pass which computes a \c DominatorTree.
225 class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
227  static AnalysisKey Key;
228 
229 public:
230  /// \brief Provide the result typedef for this analysis pass.
232 
233  /// \brief Run the analysis pass over a function and produce a dominator tree.
235 };
236 
237 /// \brief Printer pass for the \c DominatorTree.
239  : public PassInfoMixin<DominatorTreePrinterPass> {
240  raw_ostream &OS;
241 
242 public:
244 
246 };
247 
248 /// \brief Verifier pass for the \c DominatorTree.
249 struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
251 };
252 
253 /// \brief Legacy analysis pass which computes a \c DominatorTree.
255  DominatorTree DT;
256 
257 public:
258  static char ID;
259 
262  }
263 
264  DominatorTree &getDomTree() { return DT; }
265  const DominatorTree &getDomTree() const { return DT; }
266 
267  bool runOnFunction(Function &F) override;
268 
269  void verifyAnalysis() const override;
270 
271  void getAnalysisUsage(AnalysisUsage &AU) const override {
272  AU.setPreservesAll();
273  }
274 
275  void releaseMemory() override { DT.releaseMemory(); }
276 
277  void print(raw_ostream &OS, const Module *M = nullptr) const override;
278 };
279 
280 //===-------------------------------------
281 /// \brief Class to defer updates to a DominatorTree.
282 ///
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.
288 ///
289 /// The scope of DeferredDominance operates at a Function level.
290 ///
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
295 /// occur.
296 ///
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.
301 /// Example (good):
302 /// TerminatorInstructionBB->removeFromParent();
303 /// DDT->deleteEdge(BB, Successor);
304 /// Example (bad):
305 /// DDT->deleteEdge(BB, Successor);
306 /// TerminatorInstructionBB->removeFromParent();
308 public:
309  DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
310 
311  /// \brief Queues multiple updates and discards duplicates.
312  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
313 
314  /// \brief 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);
319 
320  /// \brief 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
323  /// Dominators.
324  void deleteEdge(BasicBlock *From, BasicBlock *To);
325 
326  /// \brief Delays the deletion of a basic block until a flush() event.
327  void deleteBB(BasicBlock *DelBB);
328 
329  /// \brief Returns true if DelBB is awaiting deletion at a flush() event.
330  bool pendingDeletedBB(BasicBlock *DelBB);
331 
332  /// \brief Returns true if pending DT updates are queued for a flush() event.
333  bool pending();
334 
335  /// \brief Flushes all pending updates and block deletions. Returns a
336  /// correct DominatorTree reference to be used by the caller for analysis.
337  DominatorTree &flush();
338 
339  /// \brief 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);
343 
344  /// \brief Debug method to help view the state of pending updates.
345  LLVM_DUMP_METHOD void dump() const;
346 
347 private:
348  DominatorTree &DT;
350  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
351 
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,
358  BasicBlock *To);
359 
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.
364  bool flushDelBB();
365 };
366 
367 } // end namespace llvm
368 
369 #endif // LLVM_IR_DOMINATORS_H
typename std::vector< DomTreeNodeBase *>::const_iterator const_iterator
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
DominatorTree(Function &F)
Definition: Dominators.h:147
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS)
Definition: Dominators.h:118
template void DeleteEdge< BBPostDomTree >(BBPostDomTree &DT, BasicBlock *From, BasicBlock *To)
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:191
template void ApplyUpdates< BBDomTree >(BBDomTree &DT, BBUpdates)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Dominators.h:271
unsigned second
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
F(f)
const BasicBlock * getEnd() const
Definition: Dominators.h:92
static nodes_iterator nodes_begin(NodeRef N)
Definition: Dominators.h:195
static nodes_iterator nodes_begin(DominatorTree *N)
Definition: Dominators.h:215
void initializeDominatorTreeWrapperPassPass(PassRegistry &)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
BasicBlockEdge(const std::pair< BasicBlock *, BasicBlock *> &Pair)
Definition: Dominators.h:82
static BasicBlockEdge getEmptyKey()
Definition: Dominators.h:105
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
DominatorTree & getDomTree()
Definition: Dominators.h:264
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
template void ApplyUpdates< BBPostDomTree >(BBPostDomTree &DT, BBUpdates)
static bool isEqual(const Function &Caller, const Function &Callee)
static nodes_iterator nodes_end(DominatorTree *N)
Definition: Dominators.h:219
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:365
DeferredDominance(DominatorTree &DT_)
Definition: Dominators.h:309
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
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:275
static nodes_iterator nodes_end(NodeRef N)
Definition: Dominators.h:199
Core dominator tree base class.
Definition: LoopInfo.h:61
static bool runOnFunction(Function &F, bool PostInlining)
typename DomTreeNode *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:72
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
template bool Verify< BBDomTree >(const BBDomTree &DT, BBDomTree::VerificationLevel VL)
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:318
df_iterator< T > df_end(const T &G)
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
Represent the analysis usage information of a pass.
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Printer pass for the DominatorTree.
Definition: Dominators.h:238
template void Calculate< BBDomTree >(BBDomTree &DT)
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
ArrayRef< Update< BasicBlock * > > BBUpdates
Definition: Dominators.h:46
Verifier pass for the DominatorTree.
Definition: Dominators.h:249
unsigned first
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:192
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:193
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
template void InsertEdge< BBPostDomTree >(BBPostDomTree &DT, BasicBlock *From, BasicBlock *To)
const DominatorTree & getDomTree() const
Definition: Dominators.h:265
df_iterator< T > df_begin(const T &G)
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:602
Class to defer updates to a DominatorTree.
Definition: Dominators.h:307
void setPreservesAll()
Set by analyses that do not transform their input at all.
template void DeleteEdge< BBDomTree >(BBDomTree &DT, BasicBlock *From, BasicBlock *To)
#define N
static unsigned getHashValue(const BasicBlockEdge &Edge)
Definition: Dominators.h:113
static NodeRef getEntryNode(DominatorTree *DT)
Definition: Dominators.h:213
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
const unsigned Kind
template bool Verify< BBPostDomTree >(const BBPostDomTree &DT, BBPostDomTree::VerificationLevel VL)
BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_)
Definition: Dominators.h:79
const BasicBlock * getStart() const
Definition: Dominators.h:88
aarch64 promote const
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:72
template void Calculate< BBPostDomTree >(BBPostDomTree &DT)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
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:70
BasicBlockEdge(const std::pair< const BasicBlock *, const BasicBlock *> &Pair)
Definition: Dominators.h:85
template void InsertEdge< BBDomTree >(BBDomTree &DT, BasicBlock *From, BasicBlock *To)
static BasicBlockEdge getTombstoneKey()
Definition: Dominators.h:109