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