1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements simple dominator construction algorithms for finding 11 // forward dominators on machine functions. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/CodeGen/MachineDominators.h" 16 #include "llvm/CodeGen/Passes.h" 17 #include "llvm/ADT/SmallBitVector.h" 18 19 using namespace llvm; 20 21 namespace llvm { 22 template class DomTreeNodeBase<MachineBasicBlock>; 23 template class DominatorTreeBase<MachineBasicBlock>; 24 } 25 26 char MachineDominatorTree::ID = 0; 27 28 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree", 29 "MachineDominator Tree Construction", true, true) 30 31 char &llvm::MachineDominatorsID = MachineDominatorTree::ID; 32 33 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { 34 AU.setPreservesAll(); 35 MachineFunctionPass::getAnalysisUsage(AU); 36 } 37 38 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) { 39 CriticalEdgesToSplit.clear(); 40 NewBBs.clear(); 41 DT->recalculate(F); 42 43 return false; 44 } 45 46 MachineDominatorTree::MachineDominatorTree() 47 : MachineFunctionPass(ID) { 48 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 49 DT = new DominatorTreeBase<MachineBasicBlock>(false); 50 } 51 52 MachineDominatorTree::~MachineDominatorTree() { 53 delete DT; 54 } 55 56 void MachineDominatorTree::releaseMemory() { 57 DT->releaseMemory(); 58 } 59 60 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const { 61 DT->print(OS); 62 } 63 64 void MachineDominatorTree::applySplitCriticalEdges() const { 65 // Bail out early if there is nothing to do. 66 if (CriticalEdgesToSplit.empty()) 67 return; 68 69 // For each element in CriticalEdgesToSplit, remember whether or not element 70 // is the new immediate domminator of its successor. The mapping is done by 71 // index, i.e., the information for the ith element of CriticalEdgesToSplit is 72 // the ith element of IsNewIDom. 73 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true); 74 size_t Idx = 0; 75 76 // Collect all the dominance properties info, before invalidating 77 // the underlying DT. 78 for (CriticalEdge &Edge : CriticalEdgesToSplit) { 79 // Update dominator information. 80 MachineBasicBlock *Succ = Edge.ToBB; 81 MachineDomTreeNode *SuccDTNode = DT->getNode(Succ); 82 83 for (MachineBasicBlock *PredBB : Succ->predecessors()) { 84 if (PredBB == Edge.NewBB) 85 continue; 86 // If we are in this situation: 87 // FromBB1 FromBB2 88 // + + 89 // + + + + 90 // + + + + 91 // ... Split1 Split2 ... 92 // + + 93 // + + 94 // + 95 // Succ 96 // Instead of checking the domiance property with Split2, we check it with 97 // FromBB2 since Split2 is still unknown of the underlying DT structure. 98 if (NewBBs.count(PredBB)) { 99 assert(PredBB->pred_size() == 1 && "A basic block resulting from a " 100 "critical edge split has more " 101 "than one predecessor!"); 102 PredBB = *PredBB->pred_begin(); 103 } 104 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) { 105 IsNewIDom[Idx] = false; 106 break; 107 } 108 } 109 ++Idx; 110 } 111 112 // Now, update DT with the collected dominance properties info. 113 Idx = 0; 114 for (CriticalEdge &Edge : CriticalEdgesToSplit) { 115 // We know FromBB dominates NewBB. 116 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB); 117 118 // If all the other predecessors of "Succ" are dominated by "Succ" itself 119 // then the new block is the new immediate dominator of "Succ". Otherwise, 120 // the new block doesn't dominate anything. 121 if (IsNewIDom[Idx]) 122 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode); 123 ++Idx; 124 } 125 NewBBs.clear(); 126 CriticalEdgesToSplit.clear(); 127 } 128