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>;
39 extern template void Calculate<Function, BasicBlock *>(
40 DominatorTreeBaseByGraphTraits<GraphTraits<BasicBlock *>> &DT, Function &F);
41 extern template void Calculate<Function, Inverse<BasicBlock *>>(
42 DominatorTreeBaseByGraphTraits<GraphTraits<Inverse<BasicBlock *>>> &DT,
45 typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
47 class BasicBlockEdge {
48 const BasicBlock *Start;
49 const BasicBlock *End;
52 BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
53 Start(Start_), End(End_) {}
55 BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
56 : Start(Pair.first), End(Pair.second) {}
58 BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
59 : Start(Pair.first), End(Pair.second) {}
61 const BasicBlock *getStart() const {
65 const BasicBlock *getEnd() const {
69 bool isSingleEdge() const;
72 template <> struct DenseMapInfo<BasicBlockEdge> {
73 typedef DenseMapInfo<const BasicBlock *> BBInfo;
75 static unsigned getHashValue(const BasicBlockEdge *V);
77 static inline BasicBlockEdge getEmptyKey() {
78 return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
81 static inline BasicBlockEdge getTombstoneKey() {
82 return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
85 static unsigned getHashValue(const BasicBlockEdge &Edge) {
86 return hash_combine(BBInfo::getHashValue(Edge.getStart()),
87 BBInfo::getHashValue(Edge.getEnd()));
90 static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
91 return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
92 BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
96 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
97 /// normal dominator tree.
99 /// Definition: A block is said to be forward statically reachable if there is
100 /// a path from the entry of the function to the block. A statically reachable
101 /// block may become statically unreachable during optimization.
103 /// A forward unreachable block may appear in the dominator tree, or it may
104 /// not. If it does, dominance queries will return results as if all reachable
105 /// blocks dominate it. When asking for a Node corresponding to a potentially
106 /// unreachable block, calling code must handle the case where the block was
107 /// unreachable and the result of getNode() is nullptr.
109 /// Generally, a block known to be unreachable when the dominator tree is
110 /// constructed will not be in the tree. One which becomes unreachable after
111 /// the dominator tree is initially constructed may still exist in the tree,
112 /// even if the tree is properly updated. Calling code should not rely on the
113 /// preceding statements; this is stated only to assist human understanding.
114 class DominatorTree : public DominatorTreeBase<BasicBlock> {
116 typedef DominatorTreeBase<BasicBlock> Base;
118 DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
119 explicit DominatorTree(Function &F) : DominatorTreeBase<BasicBlock>(false) {
123 /// Handle invalidation explicitly.
124 bool invalidate(Function &F, const PreservedAnalyses &PA,
125 FunctionAnalysisManager::Invalidator &);
127 /// \brief Returns *false* if the other dominator tree matches this dominator
129 inline bool compare(const DominatorTree &Other) const {
130 const DomTreeNode *R = getRootNode();
131 const DomTreeNode *OtherR = Other.getRootNode();
132 return !R || !OtherR || R->getBlock() != OtherR->getBlock() ||
133 Base::compare(Other);
136 // Ensure base-class overloads are visible.
137 using Base::dominates;
139 /// \brief Return true if Def dominates a use in User.
141 /// This performs the special checks necessary if Def and User are in the same
142 /// basic block. Note that Def doesn't dominate a use in Def itself!
143 bool dominates(const Instruction *Def, const Use &U) const;
144 bool dominates(const Instruction *Def, const Instruction *User) const;
145 bool dominates(const Instruction *Def, const BasicBlock *BB) const;
146 bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
147 bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
149 // Ensure base class overloads are visible.
150 using Base::isReachableFromEntry;
152 /// \brief Provide an overload for a Use.
153 bool isReachableFromEntry(const Use &U) const;
155 /// \brief Verify the correctness of the domtree by re-computing it.
157 /// This should only be used for debugging as it aborts the program if the
158 /// verification fails.
159 void verifyDomTree() const;
162 //===-------------------------------------
163 // DominatorTree GraphTraits specializations so the DominatorTree can be
164 // iterable by generic graph iterators.
166 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
167 typedef Node *NodeRef;
168 typedef ChildIterator ChildIteratorType;
169 typedef df_iterator<Node *, df_iterator_default_set<Node*>> nodes_iterator;
171 static NodeRef getEntryNode(NodeRef N) { return N; }
172 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
173 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
175 static nodes_iterator nodes_begin(NodeRef N) {
176 return df_begin(getEntryNode(N));
179 static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
183 struct GraphTraits<DomTreeNode *>
184 : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
187 struct GraphTraits<const DomTreeNode *>
188 : public DomTreeGraphTraitsBase<const DomTreeNode,
189 DomTreeNode::const_iterator> {};
191 template <> struct GraphTraits<DominatorTree*>
192 : public GraphTraits<DomTreeNode*> {
193 static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
195 static nodes_iterator nodes_begin(DominatorTree *N) {
196 return df_begin(getEntryNode(N));
199 static nodes_iterator nodes_end(DominatorTree *N) {
200 return df_end(getEntryNode(N));
204 /// \brief Analysis pass which computes a \c DominatorTree.
205 class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
206 friend AnalysisInfoMixin<DominatorTreeAnalysis>;
207 static AnalysisKey Key;
210 /// \brief Provide the result typedef for this analysis pass.
211 typedef DominatorTree Result;
213 /// \brief Run the analysis pass over a function and produce a dominator tree.
214 DominatorTree run(Function &F, FunctionAnalysisManager &);
217 /// \brief Printer pass for the \c DominatorTree.
218 class DominatorTreePrinterPass
219 : public PassInfoMixin<DominatorTreePrinterPass> {
223 explicit DominatorTreePrinterPass(raw_ostream &OS);
225 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
228 /// \brief Verifier pass for the \c DominatorTree.
229 struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
230 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
233 /// \brief Legacy analysis pass which computes a \c DominatorTree.
234 class DominatorTreeWrapperPass : public FunctionPass {
240 DominatorTreeWrapperPass() : FunctionPass(ID) {
241 initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
244 DominatorTree &getDomTree() { return DT; }
245 const DominatorTree &getDomTree() const { return DT; }
247 bool runOnFunction(Function &F) override;
249 void verifyAnalysis() const override;
251 void getAnalysisUsage(AnalysisUsage &AU) const override {
252 AU.setPreservesAll();
255 void releaseMemory() override { DT.releaseMemory(); }
257 void print(raw_ostream &OS, const Module *M = nullptr) const override;
260 } // end namespace llvm
262 #endif // LLVM_IR_DOMINATORS_H