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