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 extern template class cfg::Update<BasicBlock *>;
42 namespace DomTreeBuilder {
43 using BBDomTree = DomTreeBase<BasicBlock>;
44 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
46 using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
48 extern template void Calculate<BBDomTree>(BBDomTree &DT);
49 extern template void CalculateWithUpdates<BBDomTree>(BBDomTree &DT,
52 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
54 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
56 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
60 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
62 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
66 extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
67 extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
69 extern template bool Verify<BBDomTree>(const BBDomTree &DT,
70 BBDomTree::VerificationLevel VL);
71 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
72 BBPostDomTree::VerificationLevel VL);
73 } // namespace DomTreeBuilder
75 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
77 class BasicBlockEdge {
78 const BasicBlock *Start;
79 const BasicBlock *End;
82 BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
83 Start(Start_), End(End_) {}
85 BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
86 : Start(Pair.first), End(Pair.second) {}
88 BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
89 : Start(Pair.first), End(Pair.second) {}
91 const BasicBlock *getStart() const {
95 const BasicBlock *getEnd() const {
99 /// Check if this is the only edge between Start and End.
100 bool isSingleEdge() const;
103 template <> struct DenseMapInfo<BasicBlockEdge> {
104 using BBInfo = DenseMapInfo<const BasicBlock *>;
106 static unsigned getHashValue(const BasicBlockEdge *V);
108 static inline BasicBlockEdge getEmptyKey() {
109 return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
112 static inline BasicBlockEdge getTombstoneKey() {
113 return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
116 static unsigned getHashValue(const BasicBlockEdge &Edge) {
117 return hash_combine(BBInfo::getHashValue(Edge.getStart()),
118 BBInfo::getHashValue(Edge.getEnd()));
121 static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
122 return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
123 BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
127 /// Concrete subclass of DominatorTreeBase that is used to compute a
128 /// normal dominator tree.
130 /// Definition: A block is said to be forward statically reachable if there is
131 /// a path from the entry of the function to the block. A statically reachable
132 /// block may become statically unreachable during optimization.
134 /// A forward unreachable block may appear in the dominator tree, or it may
135 /// not. If it does, dominance queries will return results as if all reachable
136 /// blocks dominate it. When asking for a Node corresponding to a potentially
137 /// unreachable block, calling code must handle the case where the block was
138 /// unreachable and the result of getNode() is nullptr.
140 /// Generally, a block known to be unreachable when the dominator tree is
141 /// constructed will not be in the tree. One which becomes unreachable after
142 /// the dominator tree is initially constructed may still exist in the tree,
143 /// even if the tree is properly updated. Calling code should not rely on the
144 /// preceding statements; this is stated only to assist human understanding.
145 class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
147 using Base = DominatorTreeBase<BasicBlock, false>;
149 DominatorTree() = default;
150 explicit DominatorTree(Function &F) { recalculate(F); }
151 explicit DominatorTree(DominatorTree &DT, DomTreeBuilder::BBUpdates U) {
152 recalculate(*DT.Parent, U);
155 /// Handle invalidation explicitly.
156 bool invalidate(Function &F, const PreservedAnalyses &PA,
157 FunctionAnalysisManager::Invalidator &);
159 // Ensure base-class overloads are visible.
160 using Base::dominates;
162 /// Return true if Def dominates a use in User.
164 /// This performs the special checks necessary if Def and User are in the same
165 /// basic block. Note that Def doesn't dominate a use in Def itself!
166 bool dominates(const Instruction *Def, const Use &U) const;
167 bool dominates(const Instruction *Def, const Instruction *User) const;
168 bool dominates(const Instruction *Def, const BasicBlock *BB) const;
170 /// Return true if an edge dominates a use.
172 /// If BBE is not a unique edge between start and end of the edge, it can
173 /// never dominate the use.
174 bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
175 bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
177 // Ensure base class overloads are visible.
178 using Base::isReachableFromEntry;
180 /// Provide an overload for a Use.
181 bool isReachableFromEntry(const Use &U) const;
183 // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
184 void viewGraph(const Twine &Name, const Twine &Title);
188 //===-------------------------------------
189 // DominatorTree GraphTraits specializations so the DominatorTree can be
190 // iterable by generic graph iterators.
192 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
193 using NodeRef = Node *;
194 using ChildIteratorType = ChildIterator;
195 using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
197 static NodeRef getEntryNode(NodeRef N) { return N; }
198 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
199 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
201 static nodes_iterator nodes_begin(NodeRef N) {
202 return df_begin(getEntryNode(N));
205 static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
209 struct GraphTraits<DomTreeNode *>
210 : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
213 struct GraphTraits<const DomTreeNode *>
214 : public DomTreeGraphTraitsBase<const DomTreeNode,
215 DomTreeNode::const_iterator> {};
217 template <> struct GraphTraits<DominatorTree*>
218 : public GraphTraits<DomTreeNode*> {
219 static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
221 static nodes_iterator nodes_begin(DominatorTree *N) {
222 return df_begin(getEntryNode(N));
225 static nodes_iterator nodes_end(DominatorTree *N) {
226 return df_end(getEntryNode(N));
230 /// Analysis pass which computes a \c DominatorTree.
231 class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
232 friend AnalysisInfoMixin<DominatorTreeAnalysis>;
233 static AnalysisKey Key;
236 /// Provide the result typedef for this analysis pass.
237 using Result = DominatorTree;
239 /// Run the analysis pass over a function and produce a dominator tree.
240 DominatorTree run(Function &F, FunctionAnalysisManager &);
243 /// Printer pass for the \c DominatorTree.
244 class DominatorTreePrinterPass
245 : public PassInfoMixin<DominatorTreePrinterPass> {
249 explicit DominatorTreePrinterPass(raw_ostream &OS);
251 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
254 /// Verifier pass for the \c DominatorTree.
255 struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
256 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
259 /// Legacy analysis pass which computes a \c DominatorTree.
260 class DominatorTreeWrapperPass : public FunctionPass {
266 DominatorTreeWrapperPass() : FunctionPass(ID) {
267 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
270 DominatorTree &getDomTree() { return DT; }
271 const DominatorTree &getDomTree() const { return DT; }
273 bool runOnFunction(Function &F) override;
275 void verifyAnalysis() const override;
277 void getAnalysisUsage(AnalysisUsage &AU) const override {
278 AU.setPreservesAll();
281 void releaseMemory() override { DT.releaseMemory(); }
283 void print(raw_ostream &OS, const Module *M = nullptr) const override;
285 } // end namespace llvm
287 #endif // LLVM_IR_DOMINATORS_H