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/CodeGen/MachineInstrBundleIterator.h" 23 #include "llvm/CodeGen/MachinePassManager.h" 24 #include "llvm/Support/GenericDomTree.h" 25 #include <cassert> 26 #include <memory> 27 #include <optional> 28 29 namespace llvm { 30 class AnalysisUsage; 31 class MachineFunction; 32 class Module; 33 class raw_ostream; 34 35 template <> 36 inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( 37 MachineBasicBlock *MBB) { 38 this->Roots.push_back(MBB); 39 } 40 41 extern template class DomTreeNodeBase<MachineBasicBlock>; 42 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree 43 44 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; 45 46 namespace DomTreeBuilder { 47 using MBBDomTree = DomTreeBase<MachineBasicBlock>; 48 using MBBUpdates = ArrayRef<llvm::cfg::Update<MachineBasicBlock *>>; 49 using MBBDomTreeGraphDiff = GraphDiff<MachineBasicBlock *, false>; 50 51 extern template void Calculate<MBBDomTree>(MBBDomTree &DT); 52 extern template void CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, 53 MBBUpdates U); 54 55 extern template void InsertEdge<MBBDomTree>(MBBDomTree &DT, 56 MachineBasicBlock *From, 57 MachineBasicBlock *To); 58 59 extern template void DeleteEdge<MBBDomTree>(MBBDomTree &DT, 60 MachineBasicBlock *From, 61 MachineBasicBlock *To); 62 63 extern template void ApplyUpdates<MBBDomTree>(MBBDomTree &DT, 64 MBBDomTreeGraphDiff &, 65 MBBDomTreeGraphDiff *); 66 67 extern template bool Verify<MBBDomTree>(const MBBDomTree &DT, 68 MBBDomTree::VerificationLevel VL); 69 } // namespace DomTreeBuilder 70 71 //===------------------------------------- 72 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 73 /// compute a normal dominator tree. 74 /// 75 class MachineDominatorTree : public DomTreeBase<MachineBasicBlock> { 76 /// Helper structure used to hold all the basic blocks 77 /// involved in the split of a critical edge. 78 struct CriticalEdge { 79 MachineBasicBlock *FromBB; 80 MachineBasicBlock *ToBB; 81 MachineBasicBlock *NewBB; 82 }; 83 84 /// Pile up all the critical edges to be split. 85 /// The splitting of a critical edge is local and thus, it is possible 86 /// to apply several of those changes at the same time. 87 mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; 88 89 /// Remember all the basic blocks that are inserted during 90 /// edge splitting. 91 /// Invariant: NewBBs == all the basic blocks contained in the NewBB 92 /// field of all the elements of CriticalEdgesToSplit. 93 /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs 94 /// such as BB == elt.NewBB. 95 mutable SmallSet<MachineBasicBlock *, 32> NewBBs; 96 97 /// Apply all the recorded critical edges to the DT. 98 /// This updates the underlying DT information in a way that uses 99 /// the fast query path of DT as much as possible. 100 /// FIXME: This method should not be a const member! 101 /// 102 /// \post CriticalEdgesToSplit.empty(). 103 void applySplitCriticalEdges() const; 104 105 public: 106 using Base = DomTreeBase<MachineBasicBlock>; 107 108 MachineDominatorTree() = default; 109 explicit MachineDominatorTree(MachineFunction &MF) { calculate(MF); } 110 111 /// Handle invalidation explicitly. 112 bool invalidate(MachineFunction &, const PreservedAnalyses &PA, 113 MachineFunctionAnalysisManager::Invalidator &); 114 115 // FIXME: If there is an updater for MachineDominatorTree, 116 // migrate to this updater and remove these wrappers. 117 118 MachineDominatorTree &getBase() { 119 applySplitCriticalEdges(); 120 return *this; 121 } 122 123 MachineBasicBlock *getRoot() const { 124 applySplitCriticalEdges(); 125 return Base::getRoot(); 126 } 127 128 MachineDomTreeNode *getRootNode() const { 129 applySplitCriticalEdges(); 130 return const_cast<MachineDomTreeNode *>(Base::getRootNode()); 131 } 132 133 void calculate(MachineFunction &F); 134 135 bool dominates(const MachineDomTreeNode *A, 136 const MachineDomTreeNode *B) const { 137 applySplitCriticalEdges(); 138 return Base::dominates(A, B); 139 } 140 141 void getDescendants(MachineBasicBlock *A, 142 SmallVectorImpl<MachineBasicBlock *> &Result) { 143 applySplitCriticalEdges(); 144 Base::getDescendants(A, Result); 145 } 146 147 bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { 148 applySplitCriticalEdges(); 149 return Base::dominates(A, B); 150 } 151 152 // dominates - Return true if A dominates B. This performs the 153 // special checks necessary if A and B are in the same basic block. 154 bool dominates(const MachineInstr *A, const MachineInstr *B) const { 155 applySplitCriticalEdges(); 156 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 157 if (BBA != BBB) 158 return Base::dominates(BBA, BBB); 159 160 // Loop through the basic block until we find A or B. 161 MachineBasicBlock::const_iterator I = BBA->begin(); 162 for (; &*I != A && &*I != B; ++I) 163 /*empty*/ ; 164 165 return &*I == A; 166 } 167 168 bool properlyDominates(const MachineDomTreeNode *A, 169 const MachineDomTreeNode *B) const { 170 applySplitCriticalEdges(); 171 return Base::properlyDominates(A, B); 172 } 173 174 bool properlyDominates(const MachineBasicBlock *A, 175 const MachineBasicBlock *B) const { 176 applySplitCriticalEdges(); 177 return Base::properlyDominates(A, B); 178 } 179 180 /// findNearestCommonDominator - Find nearest common dominator basic block 181 /// for basic block A and B. If there is no such block then return NULL. 182 MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, 183 MachineBasicBlock *B) { 184 applySplitCriticalEdges(); 185 return Base::findNearestCommonDominator(A, B); 186 } 187 188 MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 189 applySplitCriticalEdges(); 190 return Base::getNode(BB); 191 } 192 193 /// getNode - return the (Post)DominatorTree node for the specified basic 194 /// block. This is the same as using operator[] on this class. 195 /// 196 MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { 197 applySplitCriticalEdges(); 198 return Base::getNode(BB); 199 } 200 201 /// addNewBlock - Add a new node to the dominator tree information. This 202 /// creates a new node as a child of DomBB dominator node,linking it into 203 /// the children list of the immediate dominator. 204 MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, 205 MachineBasicBlock *DomBB) { 206 applySplitCriticalEdges(); 207 return Base::addNewBlock(BB, DomBB); 208 } 209 210 /// changeImmediateDominator - This method is used to update the dominator 211 /// tree information when a node's immediate dominator changes. 212 /// 213 void changeImmediateDominator(MachineBasicBlock *N, 214 MachineBasicBlock *NewIDom) { 215 applySplitCriticalEdges(); 216 Base::changeImmediateDominator(N, NewIDom); 217 } 218 219 void changeImmediateDominator(MachineDomTreeNode *N, 220 MachineDomTreeNode *NewIDom) { 221 applySplitCriticalEdges(); 222 Base::changeImmediateDominator(N, NewIDom); 223 } 224 225 /// eraseNode - Removes a node from the dominator tree. Block must not 226 /// dominate any other blocks. Removes node from its immediate dominator's 227 /// children list. Deletes dominator node associated with basic block BB. 228 void eraseNode(MachineBasicBlock *BB) { 229 applySplitCriticalEdges(); 230 Base::eraseNode(BB); 231 } 232 233 /// splitBlock - BB is split and now it has one successor. Update dominator 234 /// tree to reflect this change. 235 void splitBlock(MachineBasicBlock* NewBB) { 236 applySplitCriticalEdges(); 237 Base::splitBlock(NewBB); 238 } 239 240 /// isReachableFromEntry - Return true if A is dominated by the entry 241 /// block of the function containing it. 242 bool isReachableFromEntry(const MachineBasicBlock *A) { 243 applySplitCriticalEdges(); 244 return Base::isReachableFromEntry(A); 245 } 246 247 /// Record that the critical edge (FromBB, ToBB) has been 248 /// split with NewBB. 249 /// This is best to use this method instead of directly update the 250 /// underlying information, because this helps mitigating the 251 /// number of time the DT information is invalidated. 252 /// 253 /// \note Do not use this method with regular edges. 254 /// 255 /// \note To benefit from the compile time improvement incurred by this 256 /// method, the users of this method have to limit the queries to the DT 257 /// interface between two edges splitting. In other words, they have to 258 /// pack the splitting of critical edges as much as possible. 259 void recordSplitCriticalEdge(MachineBasicBlock *FromBB, 260 MachineBasicBlock *ToBB, 261 MachineBasicBlock *NewBB) { 262 bool Inserted = NewBBs.insert(NewBB).second; 263 (void)Inserted; 264 assert(Inserted && 265 "A basic block inserted via edge splitting cannot appear twice"); 266 CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); 267 } 268 }; 269 270 /// \brief Analysis pass which computes a \c MachineDominatorTree. 271 class MachineDominatorTreeAnalysis 272 : public AnalysisInfoMixin<MachineDominatorTreeAnalysis> { 273 friend AnalysisInfoMixin<MachineDominatorTreeAnalysis>; 274 275 static AnalysisKey Key; 276 277 public: 278 using Result = MachineDominatorTree; 279 280 Result run(MachineFunction &MF, MachineFunctionAnalysisManager &); 281 }; 282 283 /// \brief Machine function pass which print \c MachineDominatorTree. 284 class MachineDominatorTreePrinterPass 285 : public PassInfoMixin<MachineDominatorTreePrinterPass> { 286 raw_ostream &OS; 287 288 public: 289 explicit MachineDominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {} 290 PreservedAnalyses run(MachineFunction &MF, 291 MachineFunctionAnalysisManager &MFAM); 292 static bool isRequired() { return true; } 293 }; 294 295 /// \brief Analysis pass which computes a \c MachineDominatorTree. 296 class MachineDominatorTreeWrapperPass : public MachineFunctionPass { 297 // MachineFunctionPass may verify the analysis result without running pass, 298 // e.g. when `F.hasAvailableExternallyLinkage` is true. 299 std::optional<MachineDominatorTree> DT; 300 301 public: 302 static char ID; 303 304 MachineDominatorTreeWrapperPass(); 305 306 MachineDominatorTree &getDomTree() { return *DT; } 307 const MachineDominatorTree &getDomTree() const { return *DT; } 308 309 bool runOnMachineFunction(MachineFunction &MF) override; 310 311 void verifyAnalysis() const override; 312 313 void getAnalysisUsage(AnalysisUsage &AU) const override { 314 AU.setPreservesAll(); 315 MachineFunctionPass::getAnalysisUsage(AU); 316 } 317 318 void releaseMemory() override; 319 320 void print(raw_ostream &OS, const Module *M = nullptr) const override; 321 }; 322 323 //===------------------------------------- 324 /// DominatorTree GraphTraits specialization so the DominatorTree can be 325 /// iterable by generic graph iterators. 326 /// 327 328 template <class Node, class ChildIterator> 329 struct MachineDomTreeGraphTraitsBase { 330 using NodeRef = Node *; 331 using ChildIteratorType = ChildIterator; 332 333 static NodeRef getEntryNode(NodeRef N) { return N; } 334 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 335 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 336 }; 337 338 template <class T> struct GraphTraits; 339 340 template <> 341 struct GraphTraits<MachineDomTreeNode *> 342 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, 343 MachineDomTreeNode::const_iterator> { 344 }; 345 346 template <> 347 struct GraphTraits<const MachineDomTreeNode *> 348 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, 349 MachineDomTreeNode::const_iterator> { 350 }; 351 352 template <> struct GraphTraits<MachineDominatorTree*> 353 : public GraphTraits<MachineDomTreeNode *> { 354 static NodeRef getEntryNode(MachineDominatorTree *DT) { 355 return DT->getRootNode(); 356 } 357 }; 358 359 } // end namespace llvm 360 361 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H 362