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 28namespace llvm { 29 30template <> 31inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( 32 MachineBasicBlock *MBB) { 33 this->Roots.push_back(MBB); 34} 35 36extern template class DomTreeNodeBase<MachineBasicBlock>; 37extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree 38extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree 39 40using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; 41 42//===------------------------------------- 43/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 44/// compute a normal dominator tree. 45/// 46class 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 80public: 81 static char ID; // Pass ID, replacement for typeid 82 83 MachineDominatorTree(); 84 explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) { 85 calculate(MF); 86 } 87 88 DomTreeT &getBase() { 89 if (!DT) DT.reset(new DomTreeT()); 90 applySplitCriticalEdges(); 91 return *DT; 92 } 93 94 void getAnalysisUsage(AnalysisUsage &AU) const override; 95 96 /// getRoots - Return the root blocks of the current CFG. This may include 97 /// multiple blocks if we are computing post dominators. For forward 98 /// dominators, this will always be a single block (the entry node). 99 /// 100 const SmallVectorImpl<MachineBasicBlock*> &getRoots() const { 101 applySplitCriticalEdges(); 102 return DT->getRoots(); 103 } 104 105 MachineBasicBlock *getRoot() const { 106 applySplitCriticalEdges(); 107 return DT->getRoot(); 108 } 109 110 MachineDomTreeNode *getRootNode() const { 111 applySplitCriticalEdges(); 112 return DT->getRootNode(); 113 } 114 115 bool runOnMachineFunction(MachineFunction &F) override; 116 117 void calculate(MachineFunction &F); 118 119 bool dominates(const MachineDomTreeNode *A, 120 const MachineDomTreeNode *B) const { 121 applySplitCriticalEdges(); 122 return DT->dominates(A, B); 123 } 124 125 bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { 126 applySplitCriticalEdges(); 127 return DT->dominates(A, B); 128 } 129 130 // dominates - Return true if A dominates B. This performs the 131 // special checks necessary if A and B are in the same basic block. 132 bool dominates(const MachineInstr *A, const MachineInstr *B) const { 133 applySplitCriticalEdges(); 134 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 135 if (BBA != BBB) return DT->dominates(BBA, BBB); 136 137 // Loop through the basic block until we find A or B. 138 MachineBasicBlock::const_iterator I = BBA->begin(); 139 for (; &*I != A && &*I != B; ++I) 140 /*empty*/ ; 141 142 return &*I == A; 143 } 144 145 bool properlyDominates(const MachineDomTreeNode *A, 146 const MachineDomTreeNode *B) const { 147 applySplitCriticalEdges(); 148 return DT->properlyDominates(A, B); 149 } 150 151 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 MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 160 MachineBasicBlock *B) { 161 applySplitCriticalEdges(); 162 return DT->findNearestCommonDominator(A, B); 163 } 164 165 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 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 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 void changeImmediateDominator(MachineBasicBlock *N, 191 MachineBasicBlock *NewIDom) { 192 applySplitCriticalEdges(); 193 DT->changeImmediateDominator(N, NewIDom); 194 } 195 196 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 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 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 258template <class Node, class ChildIterator> 259struct 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 268template <class T> struct GraphTraits; 269 270template <> 271struct GraphTraits<MachineDomTreeNode *> 272 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, 273 MachineDomTreeNode::iterator> {}; 274 275template <> 276struct GraphTraits<const MachineDomTreeNode *> 277 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, 278 MachineDomTreeNode::const_iterator> { 279}; 280 281template <> 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