DominanceFrontier.cpp revision 243830
1174199Srwatson//===- DominanceFrontier.cpp - Dominance Frontier Calculation -------------===// 2174199Srwatson// 3174199Srwatson// The LLVM Compiler Infrastructure 4174199Srwatson// 5174199Srwatson// This file is distributed under the University of Illinois Open Source 6174199Srwatson// License. See LICENSE.TXT for details. 7174199Srwatson// 8174199Srwatson//===----------------------------------------------------------------------===// 9174199Srwatson 10174199Srwatson#include "llvm/Analysis/DominanceFrontier.h" 11174199Srwatson#include "llvm/Support/Debug.h" 12174199Srwatson#include "llvm/ADT/SmallPtrSet.h" 13174199Srwatson#include "llvm/Assembly/Writer.h" 14174199Srwatson#include "llvm/Support/raw_ostream.h" 15174199Srwatsonusing namespace llvm; 16174199Srwatson 17174199Srwatsonchar DominanceFrontier::ID = 0; 18174199SrwatsonINITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", 19174199Srwatson "Dominance Frontier Construction", true, true) 20174199SrwatsonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 21174199SrwatsonINITIALIZE_PASS_END(DominanceFrontier, "domfrontier", 22174199Srwatson "Dominance Frontier Construction", true, true) 23174199Srwatson 24174199Srwatsonnamespace { 25174199Srwatson class DFCalculateWorkObject { 26174199Srwatson public: 27174199Srwatson DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 28174199Srwatson const DomTreeNode *N, 29186567Srwatson const DomTreeNode *PN) 30174199Srwatson : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 31174199Srwatson BasicBlock *currentBB; 32174199Srwatson BasicBlock *parentBB; 33200462Sdelphij const DomTreeNode *Node; 34174199Srwatson const DomTreeNode *parentNode; 35221807Sstas }; 36174199Srwatson} 37174199Srwatson 38185563Spetervoid DominanceFrontier::anchor() { } 39185548Speter 40174199Srwatsonconst DominanceFrontier::DomSetType & 41174199SrwatsonDominanceFrontier::calculate(const DominatorTree &DT, 42174199Srwatson const DomTreeNode *Node) { 43174199Srwatson BasicBlock *BB = Node->getBlock(); 44249669Strociny DomSetType *Result = NULL; 45174199Srwatson 46174199Srwatson std::vector<DFCalculateWorkObject> workList; 47185548Speter SmallPtrSet<BasicBlock *, 32> visited; 48185548Speter 49174199Srwatson workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 50174199Srwatson do { 51174199Srwatson DFCalculateWorkObject *currentW = &workList.back(); 52174199Srwatson assert (currentW && "Missing work object."); 53238753Strociny 54174199Srwatson BasicBlock *currentBB = currentW->currentBB; 55174199Srwatson BasicBlock *parentBB = currentW->parentBB; 56174199Srwatson const DomTreeNode *currentNode = currentW->Node; 57249669Strociny const DomTreeNode *parentNode = currentW->parentNode; 58186315Smarcus assert (currentBB && "Invalid work object. Missing current Basic Block"); 59186315Smarcus assert (currentNode && "Invalid work object. Missing current Node"); 60185548Speter DomSetType &S = Frontiers[currentBB]; 61185548Speter 62221807Sstas // Visit each block only once. 63185563Speter if (visited.count(currentBB) == 0) { 64185563Speter visited.insert(currentBB); 65174199Srwatson 66174199Srwatson // Loop over CFG successors to calculate DFlocal[currentNode] 67174199Srwatson for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 68174199Srwatson SI != SE; ++SI) { 69174199Srwatson // Does Node immediately dominate this successor? 70174199Srwatson if (DT[*SI]->getIDom() != currentNode) 71174199Srwatson S.insert(*SI); 72174199Srwatson } 73227317Strociny } 74174199Srwatson 75238527Spgj // At this point, S is DFlocal. Now we union in DFup's of our children... 76238527Spgj // Loop through and visit the nodes that Node immediately dominates (Node's 77238527Spgj // children in the IDomTree) 78174199Srwatson bool visitChild = false; 79174199Srwatson for (DomTreeNode::const_iterator NI = currentNode->begin(), 80174199Srwatson NE = currentNode->end(); NI != NE; ++NI) { 81174199Srwatson DomTreeNode *IDominee = *NI; 82174199Srwatson BasicBlock *childBB = IDominee->getBlock(); 83174199Srwatson if (visited.count(childBB) == 0) { 84174199Srwatson workList.push_back(DFCalculateWorkObject(childBB, currentBB, 85174199Srwatson IDominee, currentNode)); 86174199Srwatson visitChild = true; 87174199Srwatson } 88174199Srwatson } 89174199Srwatson 90174199Srwatson // If all children are visited or there is any child then pop this block 91174199Srwatson // from the workList. 92174199Srwatson if (!visitChild) { 93174199Srwatson 94174199Srwatson if (!parentBB) { 95174199Srwatson Result = &S; 96174199Srwatson break; 97174199Srwatson } 98174199Srwatson 99174199Srwatson DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 100195840Sjhb DomSetType &parentSet = Frontiers[parentBB]; 101195840Sjhb for (; CDFI != CDFE; ++CDFI) { 102195840Sjhb if (!DT.properlyDominates(parentNode, DT[*CDFI])) 103262228Sjhb parentSet.insert(*CDFI); 104262228Sjhb } 105262228Sjhb workList.pop_back(); 106174199Srwatson } 107174199Srwatson 108174199Srwatson } while (!workList.empty()); 109174199Srwatson 110174199Srwatson return *Result; 111174199Srwatson} 112174199Srwatson 113174199Srwatsonvoid DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { 114174199Srwatson for (const_iterator I = begin(), E = end(); I != E; ++I) { 115174199Srwatson 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 136#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 137void DominanceFrontierBase::dump() const { 138 print(dbgs()); 139} 140#endif 141 142