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/DenseMap.h"
19 #include "llvm/ADT/DepthFirstIterator.h"
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/Support/GenericDomTree.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include <algorithm>
31 
32 namespace llvm {
33 
34 // FIXME: Replace this brittle forward declaration with the include of the new
35 // PassManager.h when doing so doesn't break the PassManagerBuilder.
36 template <typename IRUnitT> class AnalysisManager;
37 class PreservedAnalyses;
38 
39 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
40 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
41 
42 #define LLVM_COMMA ,
43 EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>(
44     DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA
45         Function &F));
46 EXTERN_TEMPLATE_INSTANTIATION(
47     void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >(
48         DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT
49             LLVM_COMMA Function &F));
50 #undef LLVM_COMMA
51 
52 typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
53 
54 class BasicBlockEdge {
55   const BasicBlock *Start;
56   const BasicBlock *End;
57 public:
BasicBlockEdge(const BasicBlock * Start_,const BasicBlock * End_)58   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
59     Start(Start_), End(End_) { }
getStart()60   const BasicBlock *getStart() const {
61     return Start;
62   }
getEnd()63   const BasicBlock *getEnd() const {
64     return End;
65   }
66   bool isSingleEdge() const;
67 };
68 
69 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
70 /// normal dominator tree.
71 class DominatorTree : public DominatorTreeBase<BasicBlock> {
72 public:
73   typedef DominatorTreeBase<BasicBlock> Base;
74 
DominatorTree()75   DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
76 
DominatorTree(DominatorTree && Arg)77   DominatorTree(DominatorTree &&Arg)
78       : Base(std::move(static_cast<Base &>(Arg))) {}
79   DominatorTree &operator=(DominatorTree &&RHS) {
80     Base::operator=(std::move(static_cast<Base &>(RHS)));
81     return *this;
82   }
83 
84   /// \brief Returns *false* if the other dominator tree matches this dominator
85   /// tree.
compare(const DominatorTree & Other)86   inline bool compare(const DominatorTree &Other) const {
87     const DomTreeNode *R = getRootNode();
88     const DomTreeNode *OtherR = Other.getRootNode();
89 
90     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
91       return true;
92 
93     if (Base::compare(Other))
94       return true;
95 
96     return false;
97   }
98 
99   // Ensure base-class overloads are visible.
100   using Base::dominates;
101 
102   /// \brief Return true if Def dominates a use in User.
103   ///
104   /// This performs the special checks necessary if Def and User are in the same
105   /// basic block. Note that Def doesn't dominate a use in Def itself!
106   bool dominates(const Instruction *Def, const Use &U) const;
107   bool dominates(const Instruction *Def, const Instruction *User) const;
108   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
109   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
110   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
111 
112   // Ensure base class overloads are visible.
113   using Base::isReachableFromEntry;
114 
115   /// \brief Provide an overload for a Use.
116   bool isReachableFromEntry(const Use &U) const;
117 
118   /// \brief Verify the correctness of the domtree by re-computing it.
119   ///
120   /// This should only be used for debugging as it aborts the program if the
121   /// verification fails.
122   void verifyDomTree() const;
123 };
124 
125 //===-------------------------------------
126 // DominatorTree GraphTraits specializations so the DominatorTree can be
127 // iterable by generic graph iterators.
128 
129 template <> struct GraphTraits<DomTreeNode*> {
130   typedef DomTreeNode NodeType;
131   typedef NodeType::iterator  ChildIteratorType;
132 
133   static NodeType *getEntryNode(NodeType *N) {
134     return N;
135   }
136   static inline ChildIteratorType child_begin(NodeType *N) {
137     return N->begin();
138   }
139   static inline ChildIteratorType child_end(NodeType *N) {
140     return N->end();
141   }
142 
143   typedef df_iterator<DomTreeNode*> nodes_iterator;
144 
145   static nodes_iterator nodes_begin(DomTreeNode *N) {
146     return df_begin(getEntryNode(N));
147   }
148 
149   static nodes_iterator nodes_end(DomTreeNode *N) {
150     return df_end(getEntryNode(N));
151   }
152 };
153 
154 template <> struct GraphTraits<DominatorTree*>
155   : public GraphTraits<DomTreeNode*> {
156   static NodeType *getEntryNode(DominatorTree *DT) {
157     return DT->getRootNode();
158   }
159 
160   static nodes_iterator nodes_begin(DominatorTree *N) {
161     return df_begin(getEntryNode(N));
162   }
163 
164   static nodes_iterator nodes_end(DominatorTree *N) {
165     return df_end(getEntryNode(N));
166   }
167 };
168 
169 /// \brief Analysis pass which computes a \c DominatorTree.
170 class DominatorTreeAnalysis {
171 public:
172   /// \brief Provide the result typedef for this analysis pass.
173   typedef DominatorTree Result;
174 
175   /// \brief Opaque, unique identifier for this analysis pass.
176   static void *ID() { return (void *)&PassID; }
177 
178   /// \brief Run the analysis pass over a function and produce a dominator tree.
179   DominatorTree run(Function &F);
180 
181   /// \brief Provide access to a name for this pass for debugging purposes.
182   static StringRef name() { return "DominatorTreeAnalysis"; }
183 
184 private:
185   static char PassID;
186 };
187 
188 /// \brief Printer pass for the \c DominatorTree.
189 class DominatorTreePrinterPass {
190   raw_ostream &OS;
191 
192 public:
193   explicit DominatorTreePrinterPass(raw_ostream &OS);
194   PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
195 
196   static StringRef name() { return "DominatorTreePrinterPass"; }
197 };
198 
199 /// \brief Verifier pass for the \c DominatorTree.
200 struct DominatorTreeVerifierPass {
201   PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
202 
203   static StringRef name() { return "DominatorTreeVerifierPass"; }
204 };
205 
206 /// \brief Legacy analysis pass which computes a \c DominatorTree.
207 class DominatorTreeWrapperPass : public FunctionPass {
208   DominatorTree DT;
209 
210 public:
211   static char ID;
212 
213   DominatorTreeWrapperPass() : FunctionPass(ID) {
214     initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
215   }
216 
217   DominatorTree &getDomTree() { return DT; }
218   const DominatorTree &getDomTree() const { return DT; }
219 
220   bool runOnFunction(Function &F) override;
221 
222   void verifyAnalysis() const override;
223 
224   void getAnalysisUsage(AnalysisUsage &AU) const override {
225     AU.setPreservesAll();
226   }
227 
228   void releaseMemory() override { DT.releaseMemory(); }
229 
230   void print(raw_ostream &OS, const Module *M = nullptr) const override;
231 };
232 
233 } // End llvm namespace
234 
235 #endif
236