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