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 27 namespace llvm { 28 29 template <> 30 inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( 31 MachineBasicBlock *MBB) { 32 this->Roots.push_back(MBB); 33 } 34 35 extern template class DomTreeNodeBase<MachineBasicBlock>; 36 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree 37 extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree 38 39 using MachineDomTree = DomTreeBase<MachineBasicBlock>; 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<MachineDomTree> 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 explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) { 83 calculate(MF); 84 } 85 86 MachineDomTree &getBase() { 87 if (!DT) 88 DT.reset(new MachineDomTree()); 89 applySplitCriticalEdges(); 90 return *DT; 91 } 92 93 void getAnalysisUsage(AnalysisUsage &AU) const override; 94 95 MachineBasicBlock *getRoot() const { 96 applySplitCriticalEdges(); 97 return DT->getRoot(); 98 } 99 100 MachineDomTreeNode *getRootNode() const { 101 applySplitCriticalEdges(); 102 return DT->getRootNode(); 103 } 104 105 bool runOnMachineFunction(MachineFunction &F) override; 106 107 void calculate(MachineFunction &F); 108 109 bool dominates(const MachineDomTreeNode *A, 110 const MachineDomTreeNode *B) const { 111 applySplitCriticalEdges(); 112 return DT->dominates(A, B); 113 } 114 115 void getDescendants(MachineBasicBlock *A, 116 SmallVectorImpl<MachineBasicBlock *> &Result) { 117 applySplitCriticalEdges(); 118 DT->getDescendants(A, Result); 119 } 120 121 bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { 122 applySplitCriticalEdges(); 123 return DT->dominates(A, B); 124 } 125 126 // dominates - Return true if A dominates B. This performs the 127 // special checks necessary if A and B are in the same basic block. 128 bool dominates(const MachineInstr *A, const MachineInstr *B) const { 129 applySplitCriticalEdges(); 130 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 131 if (BBA != BBB) return DT->dominates(BBA, BBB); 132 133 // Loop through the basic block until we find A or B. 134 MachineBasicBlock::const_iterator I = BBA->begin(); 135 for (; &*I != A && &*I != B; ++I) 136 /*empty*/ ; 137 138 return &*I == A; 139 } 140 141 bool properlyDominates(const MachineDomTreeNode *A, 142 const MachineDomTreeNode *B) const { 143 applySplitCriticalEdges(); 144 return DT->properlyDominates(A, B); 145 } 146 147 bool properlyDominates(const MachineBasicBlock *A, 148 const MachineBasicBlock *B) const { 149 applySplitCriticalEdges(); 150 return DT->properlyDominates(A, B); 151 } 152 153 /// findNearestCommonDominator - Find nearest common dominator basic block 154 /// for basic block A and B. If there is no such block then return NULL. 155 MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 156 MachineBasicBlock *B) { 157 applySplitCriticalEdges(); 158 return DT->findNearestCommonDominator(A, B); 159 } 160 161 MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 162 applySplitCriticalEdges(); 163 return DT->getNode(BB); 164 } 165 166 /// getNode - return the (Post)DominatorTree node for the specified basic 167 /// block. This is the same as using operator[] on this class. 168 /// 169 MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { 170 applySplitCriticalEdges(); 171 return DT->getNode(BB); 172 } 173 174 /// addNewBlock - Add a new node to the dominator tree information. This 175 /// creates a new node as a child of DomBB dominator node,linking it into 176 /// the children list of the immediate dominator. 177 MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, 178 MachineBasicBlock *DomBB) { 179 applySplitCriticalEdges(); 180 return DT->addNewBlock(BB, DomBB); 181 } 182 183 /// changeImmediateDominator - This method is used to update the dominator 184 /// tree information when a node's immediate dominator changes. 185 /// 186 void changeImmediateDominator(MachineBasicBlock *N, 187 MachineBasicBlock *NewIDom) { 188 applySplitCriticalEdges(); 189 DT->changeImmediateDominator(N, NewIDom); 190 } 191 192 void changeImmediateDominator(MachineDomTreeNode *N, 193 MachineDomTreeNode *NewIDom) { 194 applySplitCriticalEdges(); 195 DT->changeImmediateDominator(N, NewIDom); 196 } 197 198 /// eraseNode - Removes a node from the dominator tree. Block must not 199 /// dominate any other blocks. Removes node from its immediate dominator's 200 /// children list. Deletes dominator node associated with basic block BB. 201 void eraseNode(MachineBasicBlock *BB) { 202 applySplitCriticalEdges(); 203 DT->eraseNode(BB); 204 } 205 206 /// splitBlock - BB is split and now it has one successor. Update dominator 207 /// tree to reflect this change. 208 void splitBlock(MachineBasicBlock* NewBB) { 209 applySplitCriticalEdges(); 210 DT->splitBlock(NewBB); 211 } 212 213 /// isReachableFromEntry - Return true if A is dominated by the entry 214 /// block of the function containing it. 215 bool isReachableFromEntry(const MachineBasicBlock *A) { 216 applySplitCriticalEdges(); 217 return DT->isReachableFromEntry(A); 218 } 219 220 void releaseMemory() override; 221 222 void verifyAnalysis() const override; 223 224 void print(raw_ostream &OS, const Module*) const override; 225 226 /// Record that the critical edge (FromBB, ToBB) has been 227 /// split with NewBB. 228 /// This is best to use this method instead of directly update the 229 /// underlying information, because this helps mitigating the 230 /// number of time the DT information is invalidated. 231 /// 232 /// \note Do not use this method with regular edges. 233 /// 234 /// \note To benefit from the compile time improvement incurred by this 235 /// method, the users of this method have to limit the queries to the DT 236 /// interface between two edges splitting. In other words, they have to 237 /// pack the splitting of critical edges as much as possible. 238 void recordSplitCriticalEdge(MachineBasicBlock *FromBB, 239 MachineBasicBlock *ToBB, 240 MachineBasicBlock *NewBB) { 241 bool Inserted = NewBBs.insert(NewBB).second; 242 (void)Inserted; 243 assert(Inserted && 244 "A basic block inserted via edge splitting cannot appear twice"); 245 CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); 246 } 247 }; 248 249 //===------------------------------------- 250 /// DominatorTree GraphTraits specialization so the DominatorTree can be 251 /// iterable by generic graph iterators. 252 /// 253 254 template <class Node, class ChildIterator> 255 struct MachineDomTreeGraphTraitsBase { 256 using NodeRef = Node *; 257 using ChildIteratorType = ChildIterator; 258 259 static NodeRef getEntryNode(NodeRef N) { return N; } 260 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 261 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 262 }; 263 264 template <class T> struct GraphTraits; 265 266 template <> 267 struct GraphTraits<MachineDomTreeNode *> 268 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, 269 MachineDomTreeNode::const_iterator> { 270 }; 271 272 template <> 273 struct GraphTraits<const MachineDomTreeNode *> 274 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, 275 MachineDomTreeNode::const_iterator> { 276 }; 277 278 template <> struct GraphTraits<MachineDominatorTree*> 279 : public GraphTraits<MachineDomTreeNode *> { 280 static NodeRef getEntryNode(MachineDominatorTree *DT) { 281 return DT->getRootNode(); 282 } 283 }; 284 285 } // end namespace llvm 286 287 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H 288