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