1 //===- DominanceFrontier.cpp - Dominance Frontier 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 #include "llvm/Analysis/DominanceFrontier.h" 11 #include "llvm/Support/Debug.h" 12 #include "llvm/ADT/SmallPtrSet.h" 13 #include "llvm/Assembly/Writer.h" 14 #include "llvm/Support/raw_ostream.h" 15 using namespace llvm; 16 17 char DominanceFrontier::ID = 0; 18 INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", 19 "Dominance Frontier Construction", true, true) 20 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 21 INITIALIZE_PASS_END(DominanceFrontier, "domfrontier", 22 "Dominance Frontier Construction", true, true) 23 24 namespace { 25 class DFCalculateWorkObject { 26 public: DFCalculateWorkObject(BasicBlock * B,BasicBlock * P,const DomTreeNode * N,const DomTreeNode * PN)27 DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 28 const DomTreeNode *N, 29 const DomTreeNode *PN) 30 : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 31 BasicBlock *currentBB; 32 BasicBlock *parentBB; 33 const DomTreeNode *Node; 34 const DomTreeNode *parentNode; 35 }; 36 } 37 anchor()38 void DominanceFrontier::anchor() { } 39 40 const DominanceFrontier::DomSetType & calculate(const DominatorTree & DT,const DomTreeNode * Node)41 DominanceFrontier::calculate(const DominatorTree &DT, 42 const DomTreeNode *Node) { 43 BasicBlock *BB = Node->getBlock(); 44 DomSetType *Result = NULL; 45 46 std::vector<DFCalculateWorkObject> workList; 47 SmallPtrSet<BasicBlock *, 32> visited; 48 49 workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 50 do { 51 DFCalculateWorkObject *currentW = &workList.back(); 52 assert (currentW && "Missing work object."); 53 54 BasicBlock *currentBB = currentW->currentBB; 55 BasicBlock *parentBB = currentW->parentBB; 56 const DomTreeNode *currentNode = currentW->Node; 57 const DomTreeNode *parentNode = currentW->parentNode; 58 assert (currentBB && "Invalid work object. Missing current Basic Block"); 59 assert (currentNode && "Invalid work object. Missing current Node"); 60 DomSetType &S = Frontiers[currentBB]; 61 62 // Visit each block only once. 63 if (visited.count(currentBB) == 0) { 64 visited.insert(currentBB); 65 66 // Loop over CFG successors to calculate DFlocal[currentNode] 67 for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 68 SI != SE; ++SI) { 69 // Does Node immediately dominate this successor? 70 if (DT[*SI]->getIDom() != currentNode) 71 S.insert(*SI); 72 } 73 } 74 75 // At this point, S is DFlocal. Now we union in DFup's of our children... 76 // Loop through and visit the nodes that Node immediately dominates (Node's 77 // children in the IDomTree) 78 bool visitChild = false; 79 for (DomTreeNode::const_iterator NI = currentNode->begin(), 80 NE = currentNode->end(); NI != NE; ++NI) { 81 DomTreeNode *IDominee = *NI; 82 BasicBlock *childBB = IDominee->getBlock(); 83 if (visited.count(childBB) == 0) { 84 workList.push_back(DFCalculateWorkObject(childBB, currentBB, 85 IDominee, currentNode)); 86 visitChild = true; 87 } 88 } 89 90 // If all children are visited or there is any child then pop this block 91 // from the workList. 92 if (!visitChild) { 93 94 if (!parentBB) { 95 Result = &S; 96 break; 97 } 98 99 DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 100 DomSetType &parentSet = Frontiers[parentBB]; 101 for (; CDFI != CDFE; ++CDFI) { 102 if (!DT.properlyDominates(parentNode, DT[*CDFI])) 103 parentSet.insert(*CDFI); 104 } 105 workList.pop_back(); 106 } 107 108 } while (!workList.empty()); 109 110 return *Result; 111 } 112 print(raw_ostream & OS,const Module *) const113 void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { 114 for (const_iterator I = begin(), E = end(); I != E; ++I) { 115 OS << " DomFrontier for BB "; 116 if (I->first) 117 WriteAsOperand(OS, I->first, false); 118 else 119 OS << " <<exit node>>"; 120 OS << " is:\t"; 121 122 const std::set<BasicBlock*> &BBs = I->second; 123 124 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 125 I != E; ++I) { 126 OS << ' '; 127 if (*I) 128 WriteAsOperand(OS, *I, false); 129 else 130 OS << "<<exit node>>"; 131 } 132 OS << "\n"; 133 } 134 } 135 dump() const136 void DominanceFrontierBase::dump() const { 137 print(dbgs()); 138 } 139 140