Line data Source code
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"
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"
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 : extern template class cfg::Update<BasicBlock *>;
41 :
42 : namespace DomTreeBuilder {
43 : using BBDomTree = DomTreeBase<BasicBlock>;
44 : using BBPostDomTree = PostDomTreeBase<BasicBlock>;
45 :
46 : using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
47 :
48 : extern template void Calculate<BBDomTree>(BBDomTree &DT);
49 : extern template void CalculateWithUpdates<BBDomTree>(BBDomTree &DT,
50 : BBUpdates U);
51 :
52 : extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
53 :
54 : extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
55 : BasicBlock *To);
56 : extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
57 : BasicBlock *From,
58 : BasicBlock *To);
59 :
60 : extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
61 : BasicBlock *To);
62 : extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
63 : BasicBlock *From,
64 : BasicBlock *To);
65 :
66 : extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
67 : extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
68 :
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
74 :
75 : using DomTreeNode = DomTreeNodeBase<BasicBlock>;
76 :
77 : class BasicBlockEdge {
78 : const BasicBlock *Start;
79 : const BasicBlock *End;
80 :
81 : public:
82 1068892 : BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
83 1061308 : Start(Start_), End(End_) {}
84 :
85 : BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
86 760 : : Start(Pair.first), End(Pair.second) {}
87 :
88 : BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
89 : : Start(Pair.first), End(Pair.second) {}
90 :
91 0 : const BasicBlock *getStart() const {
92 0 : return Start;
93 : }
94 :
95 0 : const BasicBlock *getEnd() const {
96 0 : return End;
97 : }
98 :
99 : /// Check if this is the only edge between Start and End.
100 : bool isSingleEdge() const;
101 : };
102 :
103 : template <> struct DenseMapInfo<BasicBlockEdge> {
104 : using BBInfo = DenseMapInfo<const BasicBlock *>;
105 :
106 : static unsigned getHashValue(const BasicBlockEdge *V);
107 :
108 : static inline BasicBlockEdge getEmptyKey() {
109 : return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
110 : }
111 :
112 : static inline BasicBlockEdge getTombstoneKey() {
113 : return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
114 : }
115 :
116 2888 : static unsigned getHashValue(const BasicBlockEdge &Edge) {
117 8664 : return hash_combine(BBInfo::getHashValue(Edge.getStart()),
118 8664 : BBInfo::getHashValue(Edge.getEnd()));
119 : }
120 :
121 : static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
122 19011 : return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
123 15768 : BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
124 : }
125 : };
126 :
127 : /// Concrete subclass of DominatorTreeBase that is used to compute a
128 : /// normal dominator tree.
129 : ///
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.
133 : ///
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.
139 : ///
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 25008 : class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
146 : public:
147 : using Base = DominatorTreeBase<BasicBlock, false>;
148 :
149 : DominatorTree() = default;
150 1270 : explicit DominatorTree(Function &F) { recalculate(F); }
151 0 : explicit DominatorTree(DominatorTree &DT, DomTreeBuilder::BBUpdates U) {
152 0 : recalculate(*DT.Parent, U);
153 0 : }
154 :
155 : /// Handle invalidation explicitly.
156 : bool invalidate(Function &F, const PreservedAnalyses &PA,
157 : FunctionAnalysisManager::Invalidator &);
158 :
159 : // Ensure base-class overloads are visible.
160 : using Base::dominates;
161 :
162 : /// Return true if Def dominates a use in User.
163 : ///
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;
169 :
170 : /// Return true if an edge dominates a use.
171 : ///
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;
176 :
177 : // Ensure base class overloads are visible.
178 : using Base::isReachableFromEntry;
179 :
180 : /// Provide an overload for a Use.
181 : bool isReachableFromEntry(const Use &U) const;
182 :
183 : // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
184 : void viewGraph(const Twine &Name, const Twine &Title);
185 : void viewGraph();
186 : };
187 :
188 : //===-------------------------------------
189 : // DominatorTree GraphTraits specializations so the DominatorTree can be
190 : // iterable by generic graph iterators.
191 :
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*>>;
196 :
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(); }
200 :
201 : static nodes_iterator nodes_begin(NodeRef N) {
202 : return df_begin(getEntryNode(N));
203 : }
204 :
205 : static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
206 : };
207 :
208 : template <>
209 : struct GraphTraits<DomTreeNode *>
210 : : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
211 :
212 : template <>
213 : struct GraphTraits<const DomTreeNode *>
214 : : public DomTreeGraphTraitsBase<const DomTreeNode,
215 : DomTreeNode::const_iterator> {};
216 :
217 : template <> struct GraphTraits<DominatorTree*>
218 : : public GraphTraits<DomTreeNode*> {
219 0 : static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
220 :
221 : static nodes_iterator nodes_begin(DominatorTree *N) {
222 : return df_begin(getEntryNode(N));
223 : }
224 :
225 0 : static nodes_iterator nodes_end(DominatorTree *N) {
226 0 : return df_end(getEntryNode(N));
227 : }
228 : };
229 :
230 : /// Analysis pass which computes a \c DominatorTree.
231 : class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
232 : friend AnalysisInfoMixin<DominatorTreeAnalysis>;
233 : static AnalysisKey Key;
234 :
235 : public:
236 : /// Provide the result typedef for this analysis pass.
237 : using Result = DominatorTree;
238 :
239 : /// Run the analysis pass over a function and produce a dominator tree.
240 : DominatorTree run(Function &F, FunctionAnalysisManager &);
241 : };
242 :
243 : /// Printer pass for the \c DominatorTree.
244 : class DominatorTreePrinterPass
245 : : public PassInfoMixin<DominatorTreePrinterPass> {
246 : raw_ostream &OS;
247 :
248 : public:
249 : explicit DominatorTreePrinterPass(raw_ostream &OS);
250 :
251 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
252 : };
253 :
254 : /// Verifier pass for the \c DominatorTree.
255 : struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
256 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
257 : };
258 :
259 : /// Legacy analysis pass which computes a \c DominatorTree.
260 : class DominatorTreeWrapperPass : public FunctionPass {
261 : DominatorTree DT;
262 :
263 : public:
264 : static char ID;
265 :
266 354114 : DominatorTreeWrapperPass() : FunctionPass(ID) {
267 177057 : initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
268 177057 : }
269 :
270 5677213 : DominatorTree &getDomTree() { return DT; }
271 : const DominatorTree &getDomTree() const { return DT; }
272 :
273 : bool runOnFunction(Function &F) override;
274 :
275 : void verifyAnalysis() const override;
276 :
277 169554 : void getAnalysisUsage(AnalysisUsage &AU) const override {
278 : AU.setPreservesAll();
279 169554 : }
280 :
281 2123032 : void releaseMemory() override { DT.releaseMemory(); }
282 :
283 : void print(raw_ostream &OS, const Module *M = nullptr) const override;
284 : };
285 : } // end namespace llvm
286 :
287 : #endif // LLVM_IR_DOMINATORS_H
|
