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