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