1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===// 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 implements simple dominator construction algorithms for finding 10 // forward dominators on machine functions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/MachineDominators.h" 15 #include "llvm/ADT/SmallBitVector.h" 16 #include "llvm/CodeGen/Passes.h" 17 #include "llvm/InitializePasses.h" 18 #include "llvm/Support/CommandLine.h" 19 20 using namespace llvm; 21 22 namespace llvm { 23 // Always verify dominfo if expensive checking is enabled. 24 #ifdef EXPENSIVE_CHECKS 25 bool VerifyMachineDomInfo = true; 26 #else 27 bool VerifyMachineDomInfo = false; 28 #endif 29 } // namespace llvm 30 31 static cl::opt<bool, true> VerifyMachineDomInfoX( 32 "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden, 33 cl::desc("Verify machine dominator info (time consuming)")); 34 35 namespace llvm { 36 template class DomTreeNodeBase<MachineBasicBlock>; 37 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase 38 } 39 40 char MachineDominatorTree::ID = 0; 41 42 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree", 43 "MachineDominator Tree Construction", true, true) 44 45 char &llvm::MachineDominatorsID = MachineDominatorTree::ID; 46 47 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { 48 AU.setPreservesAll(); 49 MachineFunctionPass::getAnalysisUsage(AU); 50 } 51 52 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) { 53 calculate(F); 54 return false; 55 } 56 57 void MachineDominatorTree::calculate(MachineFunction &F) { 58 CriticalEdgesToSplit.clear(); 59 NewBBs.clear(); 60 DT.reset(new DomTreeBase<MachineBasicBlock>()); 61 DT->recalculate(F); 62 } 63 64 MachineDominatorTree::MachineDominatorTree() 65 : MachineFunctionPass(ID) { 66 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 67 } 68 69 void MachineDominatorTree::releaseMemory() { 70 CriticalEdgesToSplit.clear(); 71 DT.reset(nullptr); 72 } 73 74 void MachineDominatorTree::verifyAnalysis() const { 75 if (DT && VerifyMachineDomInfo) 76 if (!DT->verify(DomTreeT::VerificationLevel::Basic)) { 77 errs() << "MachineDominatorTree verification failed\n"; 78 abort(); 79 } 80 } 81 82 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const { 83 if (DT) 84 DT->print(OS); 85 } 86 87 void MachineDominatorTree::applySplitCriticalEdges() const { 88 // Bail out early if there is nothing to do. 89 if (CriticalEdgesToSplit.empty()) 90 return; 91 92 // For each element in CriticalEdgesToSplit, remember whether or not element 93 // is the new immediate domminator of its successor. The mapping is done by 94 // index, i.e., the information for the ith element of CriticalEdgesToSplit is 95 // the ith element of IsNewIDom. 96 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true); 97 size_t Idx = 0; 98 99 // Collect all the dominance properties info, before invalidating 100 // the underlying DT. 101 for (CriticalEdge &Edge : CriticalEdgesToSplit) { 102 // Update dominator information. 103 MachineBasicBlock *Succ = Edge.ToBB; 104 MachineDomTreeNode *SuccDTNode = DT->getNode(Succ); 105 106 for (MachineBasicBlock *PredBB : Succ->predecessors()) { 107 if (PredBB == Edge.NewBB) 108 continue; 109 // If we are in this situation: 110 // FromBB1 FromBB2 111 // + + 112 // + + + + 113 // + + + + 114 // ... Split1 Split2 ... 115 // + + 116 // + + 117 // + 118 // Succ 119 // Instead of checking the domiance property with Split2, we check it with 120 // FromBB2 since Split2 is still unknown of the underlying DT structure. 121 if (NewBBs.count(PredBB)) { 122 assert(PredBB->pred_size() == 1 && "A basic block resulting from a " 123 "critical edge split has more " 124 "than one predecessor!"); 125 PredBB = *PredBB->pred_begin(); 126 } 127 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) { 128 IsNewIDom[Idx] = false; 129 break; 130 } 131 } 132 ++Idx; 133 } 134 135 // Now, update DT with the collected dominance properties info. 136 Idx = 0; 137 for (CriticalEdge &Edge : CriticalEdgesToSplit) { 138 // We know FromBB dominates NewBB. 139 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB); 140 141 // If all the other predecessors of "Succ" are dominated by "Succ" itself 142 // then the new block is the new immediate dominator of "Succ". Otherwise, 143 // the new block doesn't dominate anything. 144 if (IsNewIDom[Idx]) 145 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode); 146 ++Idx; 147 } 148 NewBBs.clear(); 149 CriticalEdgesToSplit.clear(); 150 } 151