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
32namespace llvm {
33
34EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
35EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
36
37#define LLVM_COMMA ,
38EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>(
39    DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA
40        Function &F));
41EXTERN_TEMPLATE_INSTANTIATION(
42    void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >(
43        DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT
44            LLVM_COMMA Function &F));
45#undef LLVM_COMMA
46
47typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
48
49class BasicBlockEdge {
50  const BasicBlock *Start;
51  const BasicBlock *End;
52public:
53  BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
54    Start(Start_), End(End_) { }
55  const BasicBlock *getStart() const {
56    return Start;
57  }
58  const BasicBlock *getEnd() const {
59    return End;
60  }
61  bool isSingleEdge() const;
62};
63
64/// \brief Concrete subclass of DominatorTreeBase that is used to compute a
65/// normal dominator tree.
66class DominatorTree : public DominatorTreeBase<BasicBlock> {
67public:
68  typedef DominatorTreeBase<BasicBlock> Base;
69
70  DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
71
72  /// \brief Returns *false* if the other dominator tree matches this dominator
73  /// tree.
74  inline bool compare(const DominatorTree &Other) const {
75    const DomTreeNode *R = getRootNode();
76    const DomTreeNode *OtherR = Other.getRootNode();
77
78    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
79      return true;
80
81    if (Base::compare(Other))
82      return true;
83
84    return false;
85  }
86
87  // Ensure base-class overloads are visible.
88  using Base::dominates;
89
90  /// \brief Return true if Def dominates a use in User.
91  ///
92  /// This performs the special checks necessary if Def and User are in the same
93  /// basic block. Note that Def doesn't dominate a use in Def itself!
94  bool dominates(const Instruction *Def, const Use &U) const;
95  bool dominates(const Instruction *Def, const Instruction *User) const;
96  bool dominates(const Instruction *Def, const BasicBlock *BB) const;
97  bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
98  bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
99
100  // Ensure base class overloads are visible.
101  using Base::isReachableFromEntry;
102
103  /// \brief Provide an overload for a Use.
104  bool isReachableFromEntry(const Use &U) const;
105
106  /// \brief Verify the correctness of the domtree by re-computing it.
107  ///
108  /// This should only be used for debugging as it aborts the program if the
109  /// verification fails.
110  void verifyDomTree() const;
111};
112
113//===-------------------------------------
114// DominatorTree GraphTraits specializations so the DominatorTree can be
115// iterable by generic graph iterators.
116
117template <> struct GraphTraits<DomTreeNode*> {
118  typedef DomTreeNode NodeType;
119  typedef NodeType::iterator  ChildIteratorType;
120
121  static NodeType *getEntryNode(NodeType *N) {
122    return N;
123  }
124  static inline ChildIteratorType child_begin(NodeType *N) {
125    return N->begin();
126  }
127  static inline ChildIteratorType child_end(NodeType *N) {
128    return N->end();
129  }
130
131  typedef df_iterator<DomTreeNode*> nodes_iterator;
132
133  static nodes_iterator nodes_begin(DomTreeNode *N) {
134    return df_begin(getEntryNode(N));
135  }
136
137  static nodes_iterator nodes_end(DomTreeNode *N) {
138    return df_end(getEntryNode(N));
139  }
140};
141
142template <> struct GraphTraits<DominatorTree*>
143  : public GraphTraits<DomTreeNode*> {
144  static NodeType *getEntryNode(DominatorTree *DT) {
145    return DT->getRootNode();
146  }
147
148  static nodes_iterator nodes_begin(DominatorTree *N) {
149    return df_begin(getEntryNode(N));
150  }
151
152  static nodes_iterator nodes_end(DominatorTree *N) {
153    return df_end(getEntryNode(N));
154  }
155};
156
157/// \brief Analysis pass which computes a \c DominatorTree.
158class DominatorTreeWrapperPass : public FunctionPass {
159  DominatorTree DT;
160
161public:
162  static char ID;
163
164  DominatorTreeWrapperPass() : FunctionPass(ID) {
165    initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
166  }
167
168  DominatorTree &getDomTree() { return DT; }
169  const DominatorTree &getDomTree() const { return DT; }
170
171  bool runOnFunction(Function &F) override;
172
173  void verifyAnalysis() const override;
174
175  void getAnalysisUsage(AnalysisUsage &AU) const override {
176    AU.setPreservesAll();
177  }
178
179  void releaseMemory() override { DT.releaseMemory(); }
180
181  void print(raw_ostream &OS, const Module *M = nullptr) const override;
182};
183
184} // End llvm namespace
185
186#endif
187