1 //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines classes mirroring those in llvm/Analysis/Dominators.h, 10 // but for target-specific code rather than target-independent IR. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H 15 #define LLVM_CODEGEN_MACHINEDOMINATORS_H 16 17 #include "llvm/ADT/SmallSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/CodeGen/MachineBasicBlock.h" 20 #include "llvm/CodeGen/MachineFunctionPass.h" 21 #include "llvm/CodeGen/MachineInstr.h" 22 #include "llvm/Support/GenericDomTree.h" 23 #include "llvm/Support/GenericDomTreeConstruction.h" 24 #include <cassert> 25 #include <memory> 26 #include <vector> 27 28 namespace llvm { 29 30 template <> 31 inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( 32 MachineBasicBlock *MBB) { 33 this->Roots.push_back(MBB); 34 } 35 36 extern template class DomTreeNodeBase<MachineBasicBlock>; 37 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree 38 extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree 39 40 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; 41 42 //===------------------------------------- 43 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 44 /// compute a normal dominator tree. 45 /// 46 class MachineDominatorTree : public MachineFunctionPass { 47 /// Helper structure used to hold all the basic blocks 48 /// involved in the split of a critical edge. 49 struct CriticalEdge { 50 MachineBasicBlock *FromBB; 51 MachineBasicBlock *ToBB; 52 MachineBasicBlock *NewBB; 53 }; 54 55 /// Pile up all the critical edges to be split. 56 /// The splitting of a critical edge is local and thus, it is possible 57 /// to apply several of those changes at the same time. 58 mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; 59 60 /// Remember all the basic blocks that are inserted during 61 /// edge splitting. 62 /// Invariant: NewBBs == all the basic blocks contained in the NewBB 63 /// field of all the elements of CriticalEdgesToSplit. 64 /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs 65 /// such as BB == elt.NewBB. 66 mutable SmallSet<MachineBasicBlock *, 32> NewBBs; 67 68 /// The DominatorTreeBase that is used to compute a normal dominator tree 69 std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT; 70 71 /// Apply all the recorded critical edges to the DT. 72 /// This updates the underlying DT information in a way that uses 73 /// the fast query path of DT as much as possible. 74 /// 75 /// \post CriticalEdgesToSplit.empty(). 76 void applySplitCriticalEdges() const; 77 78 public: 79 static char ID; // Pass ID, replacement for typeid 80 81 MachineDominatorTree(); 82 83 DomTreeBase<MachineBasicBlock> &getBase() { 84 if (!DT) DT.reset(new DomTreeBase<MachineBasicBlock>()); 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 SmallVectorImpl<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 /// 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 253 //===------------------------------------- 254 /// DominatorTree GraphTraits specialization so the DominatorTree can be 255 /// iterable by generic graph iterators. 256 /// 257 258 template <class Node, class ChildIterator> 259 struct MachineDomTreeGraphTraitsBase { 260 using NodeRef = Node *; 261 using ChildIteratorType = ChildIterator; 262 263 static NodeRef getEntryNode(NodeRef N) { return N; } 264 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 265 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 266 }; 267 268 template <class T> struct GraphTraits; 269 270 template <> 271 struct GraphTraits<MachineDomTreeNode *> 272 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, 273 MachineDomTreeNode::iterator> {}; 274 275 template <> 276 struct GraphTraits<const MachineDomTreeNode *> 277 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, 278 MachineDomTreeNode::const_iterator> { 279 }; 280 281 template <> struct GraphTraits<MachineDominatorTree*> 282 : public GraphTraits<MachineDomTreeNode *> { 283 static NodeRef getEntryNode(MachineDominatorTree *DT) { 284 return DT->getRootNode(); 285 } 286 }; 287 288 } // end namespace llvm 289 290 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H 291