1//==- llvm/CodeGen/MachineDominators.h - Machine Dom 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 classes mirroring those in llvm/Analysis/Dominators.h,
11// but for target-specific code rather than target-independent IR.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
16#define LLVM_CODEGEN_MACHINEDOMINATORS_H
17
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineFunctionPass.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/Support/GenericDomTree.h"
24#include "llvm/Support/GenericDomTreeConstruction.h"
25#include <cassert>
26#include <memory>
27#include <vector>
28
29namespace llvm {
30
31template <>
32inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot(
33    MachineBasicBlock *MBB) {
34  this->Roots.push_back(MBB);
35}
36
37extern template class DomTreeNodeBase<MachineBasicBlock>;
38extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
39extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
40
41using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
42
43//===-------------------------------------
44/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
45/// compute a normal dominator tree.
46///
47class MachineDominatorTree : public MachineFunctionPass {
48  /// \brief Helper structure used to hold all the basic blocks
49  /// involved in the split of a critical edge.
50  struct CriticalEdge {
51    MachineBasicBlock *FromBB;
52    MachineBasicBlock *ToBB;
53    MachineBasicBlock *NewBB;
54  };
55
56  /// \brief Pile up all the critical edges to be split.
57  /// The splitting of a critical edge is local and thus, it is possible
58  /// to apply several of those changes at the same time.
59  mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
60
61  /// \brief Remember all the basic blocks that are inserted during
62  /// edge splitting.
63  /// Invariant: NewBBs == all the basic blocks contained in the NewBB
64  /// field of all the elements of CriticalEdgesToSplit.
65  /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
66  /// such as BB == elt.NewBB.
67  mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
68
69  /// The DominatorTreeBase that is used to compute a normal dominator tree
70  std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT;
71
72  /// \brief Apply all the recorded critical edges to the DT.
73  /// This updates the underlying DT information in a way that uses
74  /// the fast query path of DT as much as possible.
75  ///
76  /// \post CriticalEdgesToSplit.empty().
77  void applySplitCriticalEdges() const;
78
79public:
80  static char ID; // Pass ID, replacement for typeid
81
82  MachineDominatorTree();
83
84  DomTreeBase<MachineBasicBlock> &getBase() {
85    if (!DT) DT.reset(new DomTreeBase<MachineBasicBlock>());
86    applySplitCriticalEdges();
87    return *DT;
88  }
89
90  void getAnalysisUsage(AnalysisUsage &AU) const override;
91
92  /// getRoots -  Return the root blocks of the current CFG.  This may include
93  /// multiple blocks if we are computing post dominators.  For forward
94  /// dominators, this will always be a single block (the entry node).
95  ///
96  inline const SmallVectorImpl<MachineBasicBlock*> &getRoots() const {
97    applySplitCriticalEdges();
98    return DT->getRoots();
99  }
100
101  inline MachineBasicBlock *getRoot() const {
102    applySplitCriticalEdges();
103    return DT->getRoot();
104  }
105
106  inline MachineDomTreeNode *getRootNode() const {
107    applySplitCriticalEdges();
108    return DT->getRootNode();
109  }
110
111  bool runOnMachineFunction(MachineFunction &F) override;
112
113  inline bool dominates(const MachineDomTreeNode* A,
114                        const MachineDomTreeNode* B) const {
115    applySplitCriticalEdges();
116    return DT->dominates(A, B);
117  }
118
119  inline bool dominates(const MachineBasicBlock* A,
120                        const MachineBasicBlock* B) const {
121    applySplitCriticalEdges();
122    return DT->dominates(A, B);
123  }
124
125  // dominates - Return true if A dominates B. This performs the
126  // special checks necessary if A and B are in the same basic block.
127  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
128    applySplitCriticalEdges();
129    const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
130    if (BBA != BBB) return DT->dominates(BBA, BBB);
131
132    // Loop through the basic block until we find A or B.
133    MachineBasicBlock::const_iterator I = BBA->begin();
134    for (; &*I != A && &*I != B; ++I)
135      /*empty*/ ;
136
137    //if(!DT.IsPostDominators) {
138      // A dominates B if it is found first in the basic block.
139      return &*I == A;
140    //} else {
141    //  // A post-dominates B if B is found first in the basic block.
142    //  return &*I == B;
143    //}
144  }
145
146  inline bool properlyDominates(const MachineDomTreeNode* A,
147                                const MachineDomTreeNode* B) const {
148    applySplitCriticalEdges();
149    return DT->properlyDominates(A, B);
150  }
151
152  inline bool properlyDominates(const MachineBasicBlock* A,
153                                const MachineBasicBlock* B) const {
154    applySplitCriticalEdges();
155    return DT->properlyDominates(A, B);
156  }
157
158  /// findNearestCommonDominator - Find nearest common dominator basic block
159  /// for basic block A and B. If there is no such block then return NULL.
160  inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
161                                                       MachineBasicBlock *B) {
162    applySplitCriticalEdges();
163    return DT->findNearestCommonDominator(A, B);
164  }
165
166  inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
167    applySplitCriticalEdges();
168    return DT->getNode(BB);
169  }
170
171  /// getNode - return the (Post)DominatorTree node for the specified basic
172  /// block.  This is the same as using operator[] on this class.
173  ///
174  inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
175    applySplitCriticalEdges();
176    return DT->getNode(BB);
177  }
178
179  /// addNewBlock - Add a new node to the dominator tree information.  This
180  /// creates a new node as a child of DomBB dominator node,linking it into
181  /// the children list of the immediate dominator.
182  inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
183                                         MachineBasicBlock *DomBB) {
184    applySplitCriticalEdges();
185    return DT->addNewBlock(BB, DomBB);
186  }
187
188  /// changeImmediateDominator - This method is used to update the dominator
189  /// tree information when a node's immediate dominator changes.
190  ///
191  inline void changeImmediateDominator(MachineBasicBlock *N,
192                                       MachineBasicBlock* NewIDom) {
193    applySplitCriticalEdges();
194    DT->changeImmediateDominator(N, NewIDom);
195  }
196
197  inline void changeImmediateDominator(MachineDomTreeNode *N,
198                                       MachineDomTreeNode* NewIDom) {
199    applySplitCriticalEdges();
200    DT->changeImmediateDominator(N, NewIDom);
201  }
202
203  /// eraseNode - Removes a node from  the dominator tree. Block must not
204  /// dominate any other blocks. Removes node from its immediate dominator's
205  /// children list. Deletes dominator node associated with basic block BB.
206  inline void eraseNode(MachineBasicBlock *BB) {
207    applySplitCriticalEdges();
208    DT->eraseNode(BB);
209  }
210
211  /// splitBlock - BB is split and now it has one successor. Update dominator
212  /// tree to reflect this change.
213  inline void splitBlock(MachineBasicBlock* NewBB) {
214    applySplitCriticalEdges();
215    DT->splitBlock(NewBB);
216  }
217
218  /// isReachableFromEntry - Return true if A is dominated by the entry
219  /// block of the function containing it.
220  bool isReachableFromEntry(const MachineBasicBlock *A) {
221    applySplitCriticalEdges();
222    return DT->isReachableFromEntry(A);
223  }
224
225  void releaseMemory() override;
226
227  void verifyAnalysis() const override;
228
229  void print(raw_ostream &OS, const Module*) const override;
230
231  /// \brief Record that the critical edge (FromBB, ToBB) has been
232  /// split with NewBB.
233  /// This is best to use this method instead of directly update the
234  /// underlying information, because this helps mitigating the
235  /// number of time the DT information is invalidated.
236  ///
237  /// \note Do not use this method with regular edges.
238  ///
239  /// \note To benefit from the compile time improvement incurred by this
240  /// method, the users of this method have to limit the queries to the DT
241  /// interface between two edges splitting. In other words, they have to
242  /// pack the splitting of critical edges as much as possible.
243  void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
244                              MachineBasicBlock *ToBB,
245                              MachineBasicBlock *NewBB) {
246    bool Inserted = NewBBs.insert(NewBB).second;
247    (void)Inserted;
248    assert(Inserted &&
249           "A basic block inserted via edge splitting cannot appear twice");
250    CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
251  }
252
253  /// \brief Verify the correctness of the domtree by re-computing it.
254  ///
255  /// This should only be used for debugging as it aborts the program if the
256  /// verification fails.
257  void verifyDomTree() const;
258};
259
260//===-------------------------------------
261/// DominatorTree GraphTraits specialization so the DominatorTree can be
262/// iterable by generic graph iterators.
263///
264
265template <class Node, class ChildIterator>
266struct MachineDomTreeGraphTraitsBase {
267  using NodeRef = Node *;
268  using ChildIteratorType = ChildIterator;
269
270  static NodeRef getEntryNode(NodeRef N) { return N; }
271  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
272  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
273};
274
275template <class T> struct GraphTraits;
276
277template <>
278struct GraphTraits<MachineDomTreeNode *>
279    : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
280                                           MachineDomTreeNode::iterator> {};
281
282template <>
283struct GraphTraits<const MachineDomTreeNode *>
284    : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
285                                           MachineDomTreeNode::const_iterator> {
286};
287
288template <> struct GraphTraits<MachineDominatorTree*>
289  : public GraphTraits<MachineDomTreeNode *> {
290  static NodeRef getEntryNode(MachineDominatorTree *DT) {
291    return DT->getRootNode();
292  }
293};
294
295} // end namespace llvm
296
297#endif // LLVM_CODEGEN_MACHINEDOMINATORS_H
298