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 namespace DomTreeBuilder { 42 template void Calculate<MBBDomTree>(MBBDomTree &DT); 43 template void CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U); 44 45 template void InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From, 46 MachineBasicBlock *To); 47 48 template void DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From, 49 MachineBasicBlock *To); 50 51 template void ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &, 52 MBBDomTreeGraphDiff *); 53 54 template bool Verify<MBBDomTree>(const MBBDomTree &DT, 55 MBBDomTree::VerificationLevel VL); 56 } // namespace DomTreeBuilder 57 } 58 59 char MachineDominatorTreeWrapperPass::ID = 0; 60 61 INITIALIZE_PASS(MachineDominatorTreeWrapperPass, "machinedomtree", 62 "MachineDominator Tree Construction", true, true) 63 64 MachineDominatorTreeWrapperPass::MachineDominatorTreeWrapperPass() 65 : MachineFunctionPass(ID) { 66 initializeMachineDominatorTreeWrapperPassPass( 67 *PassRegistry::getPassRegistry()); 68 } 69 70 void MachineDominatorTree::calculate(MachineFunction &F) { 71 CriticalEdgesToSplit.clear(); 72 NewBBs.clear(); 73 recalculate(F); 74 } 75 76 char &llvm::MachineDominatorsID = MachineDominatorTreeWrapperPass::ID; 77 78 bool MachineDominatorTreeWrapperPass::runOnMachineFunction(MachineFunction &F) { 79 DT = MachineDominatorTree(F); 80 return false; 81 } 82 83 void MachineDominatorTreeWrapperPass::releaseMemory() { DT.reset(); } 84 85 void MachineDominatorTreeWrapperPass::verifyAnalysis() const { 86 if (VerifyMachineDomInfo && DT) 87 if (!DT->verify(MachineDominatorTree::VerificationLevel::Basic)) 88 report_fatal_error("MachineDominatorTree verification failed!"); 89 } 90 91 void MachineDominatorTreeWrapperPass::print(raw_ostream &OS, 92 const Module *) const { 93 if (DT) 94 DT->print(OS); 95 } 96 97 void MachineDominatorTree::applySplitCriticalEdges() const { 98 // Bail out early if there is nothing to do. 99 if (CriticalEdgesToSplit.empty()) 100 return; 101 102 // For each element in CriticalEdgesToSplit, remember whether or not element 103 // is the new immediate domminator of its successor. The mapping is done by 104 // index, i.e., the information for the ith element of CriticalEdgesToSplit is 105 // the ith element of IsNewIDom. 106 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true); 107 size_t Idx = 0; 108 109 // Collect all the dominance properties info, before invalidating 110 // the underlying DT. 111 for (CriticalEdge &Edge : CriticalEdgesToSplit) { 112 // Update dominator information. 113 MachineBasicBlock *Succ = Edge.ToBB; 114 MachineDomTreeNode *SuccDTNode = Base::getNode(Succ); 115 116 for (MachineBasicBlock *PredBB : Succ->predecessors()) { 117 if (PredBB == Edge.NewBB) 118 continue; 119 // If we are in this situation: 120 // FromBB1 FromBB2 121 // + + 122 // + + + + 123 // + + + + 124 // ... Split1 Split2 ... 125 // + + 126 // + + 127 // + 128 // Succ 129 // Instead of checking the domiance property with Split2, we check it with 130 // FromBB2 since Split2 is still unknown of the underlying DT structure. 131 if (NewBBs.count(PredBB)) { 132 assert(PredBB->pred_size() == 1 && "A basic block resulting from a " 133 "critical edge split has more " 134 "than one predecessor!"); 135 PredBB = *PredBB->pred_begin(); 136 } 137 if (!Base::dominates(SuccDTNode, Base::getNode(PredBB))) { 138 IsNewIDom[Idx] = false; 139 break; 140 } 141 } 142 ++Idx; 143 } 144 145 // Now, update DT with the collected dominance properties info. 146 Idx = 0; 147 for (CriticalEdge &Edge : CriticalEdgesToSplit) { 148 // We know FromBB dominates NewBB. 149 MachineDomTreeNode *NewDTNode = 150 const_cast<MachineDominatorTree *>(this)->Base::addNewBlock( 151 Edge.NewBB, Edge.FromBB); 152 153 // If all the other predecessors of "Succ" are dominated by "Succ" itself 154 // then the new block is the new immediate dominator of "Succ". Otherwise, 155 // the new block doesn't dominate anything. 156 if (IsNewIDom[Idx]) 157 const_cast<MachineDominatorTree *>(this)->Base::changeImmediateDominator( 158 Base::getNode(Edge.ToBB), NewDTNode); 159 ++Idx; 160 } 161 NewBBs.clear(); 162 CriticalEdgesToSplit.clear(); 163 } 164