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