1218885Sdim//===- DominanceFrontier.cpp - Dominance Frontier Calculation -------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim 10218885Sdim#include "llvm/Analysis/DominanceFrontier.h" 11218885Sdim#include "llvm/ADT/SmallPtrSet.h" 12218885Sdim#include "llvm/Assembly/Writer.h" 13252723Sdim#include "llvm/Support/Debug.h" 14218885Sdim#include "llvm/Support/raw_ostream.h" 15218885Sdimusing namespace llvm; 16218885Sdim 17218885Sdimchar DominanceFrontier::ID = 0; 18218885SdimINITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", 19218885Sdim "Dominance Frontier Construction", true, true) 20218885SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 21218885SdimINITIALIZE_PASS_END(DominanceFrontier, "domfrontier", 22218885Sdim "Dominance Frontier Construction", true, true) 23218885Sdim 24218885Sdimnamespace { 25218885Sdim class DFCalculateWorkObject { 26218885Sdim public: 27218885Sdim DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 28218885Sdim const DomTreeNode *N, 29218885Sdim const DomTreeNode *PN) 30218885Sdim : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 31218885Sdim BasicBlock *currentBB; 32218885Sdim BasicBlock *parentBB; 33218885Sdim const DomTreeNode *Node; 34218885Sdim const DomTreeNode *parentNode; 35218885Sdim }; 36218885Sdim} 37218885Sdim 38235633Sdimvoid DominanceFrontier::anchor() { } 39235633Sdim 40218885Sdimconst DominanceFrontier::DomSetType & 41218885SdimDominanceFrontier::calculate(const DominatorTree &DT, 42218885Sdim const DomTreeNode *Node) { 43218885Sdim BasicBlock *BB = Node->getBlock(); 44218885Sdim DomSetType *Result = NULL; 45218885Sdim 46218885Sdim std::vector<DFCalculateWorkObject> workList; 47218885Sdim SmallPtrSet<BasicBlock *, 32> visited; 48218885Sdim 49218885Sdim workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 50218885Sdim do { 51218885Sdim DFCalculateWorkObject *currentW = &workList.back(); 52218885Sdim assert (currentW && "Missing work object."); 53218885Sdim 54218885Sdim BasicBlock *currentBB = currentW->currentBB; 55218885Sdim BasicBlock *parentBB = currentW->parentBB; 56218885Sdim const DomTreeNode *currentNode = currentW->Node; 57218885Sdim const DomTreeNode *parentNode = currentW->parentNode; 58218885Sdim assert (currentBB && "Invalid work object. Missing current Basic Block"); 59218885Sdim assert (currentNode && "Invalid work object. Missing current Node"); 60218885Sdim DomSetType &S = Frontiers[currentBB]; 61218885Sdim 62218885Sdim // Visit each block only once. 63218885Sdim if (visited.count(currentBB) == 0) { 64218885Sdim visited.insert(currentBB); 65218885Sdim 66218885Sdim // Loop over CFG successors to calculate DFlocal[currentNode] 67218885Sdim for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 68218885Sdim SI != SE; ++SI) { 69218885Sdim // Does Node immediately dominate this successor? 70218885Sdim if (DT[*SI]->getIDom() != currentNode) 71218885Sdim S.insert(*SI); 72218885Sdim } 73218885Sdim } 74218885Sdim 75218885Sdim // At this point, S is DFlocal. Now we union in DFup's of our children... 76218885Sdim // Loop through and visit the nodes that Node immediately dominates (Node's 77218885Sdim // children in the IDomTree) 78218885Sdim bool visitChild = false; 79218885Sdim for (DomTreeNode::const_iterator NI = currentNode->begin(), 80218885Sdim NE = currentNode->end(); NI != NE; ++NI) { 81218885Sdim DomTreeNode *IDominee = *NI; 82218885Sdim BasicBlock *childBB = IDominee->getBlock(); 83218885Sdim if (visited.count(childBB) == 0) { 84218885Sdim workList.push_back(DFCalculateWorkObject(childBB, currentBB, 85218885Sdim IDominee, currentNode)); 86218885Sdim visitChild = true; 87218885Sdim } 88218885Sdim } 89218885Sdim 90218885Sdim // If all children are visited or there is any child then pop this block 91218885Sdim // from the workList. 92218885Sdim if (!visitChild) { 93218885Sdim 94218885Sdim if (!parentBB) { 95218885Sdim Result = &S; 96218885Sdim break; 97218885Sdim } 98218885Sdim 99218885Sdim DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 100218885Sdim DomSetType &parentSet = Frontiers[parentBB]; 101218885Sdim for (; CDFI != CDFE; ++CDFI) { 102218885Sdim if (!DT.properlyDominates(parentNode, DT[*CDFI])) 103218885Sdim parentSet.insert(*CDFI); 104218885Sdim } 105218885Sdim workList.pop_back(); 106218885Sdim } 107218885Sdim 108218885Sdim } while (!workList.empty()); 109218885Sdim 110218885Sdim return *Result; 111218885Sdim} 112218885Sdim 113218885Sdimvoid DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { 114218885Sdim for (const_iterator I = begin(), E = end(); I != E; ++I) { 115218885Sdim OS << " DomFrontier for BB "; 116218885Sdim if (I->first) 117218885Sdim WriteAsOperand(OS, I->first, false); 118218885Sdim else 119218885Sdim OS << " <<exit node>>"; 120218885Sdim OS << " is:\t"; 121218885Sdim 122218885Sdim const std::set<BasicBlock*> &BBs = I->second; 123218885Sdim 124218885Sdim for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 125218885Sdim I != E; ++I) { 126218885Sdim OS << ' '; 127218885Sdim if (*I) 128218885Sdim WriteAsOperand(OS, *I, false); 129218885Sdim else 130218885Sdim OS << "<<exit node>>"; 131218885Sdim } 132218885Sdim OS << "\n"; 133218885Sdim } 134218885Sdim} 135218885Sdim 136245431Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 137218885Sdimvoid DominanceFrontierBase::dump() const { 138218885Sdim print(dbgs()); 139218885Sdim} 140245431Sdim#endif 141218885Sdim 142