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