14676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich//===- DominanceFrontier.cpp - Dominance Frontier Calculation -------------===// 24676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich// 34676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich// The LLVM Compiler Infrastructure 44676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich// 54676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich// This file is distributed under the University of Illinois Open Source 64676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich// License. See LICENSE.TXT for details. 74676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich// 84676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich//===----------------------------------------------------------------------===// 94676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 104676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich#include "llvm/Analysis/DominanceFrontier.h" 114676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich#include "llvm/Support/Debug.h" 124676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich#include "llvm/ADT/SmallPtrSet.h" 134676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich#include "llvm/Assembly/Writer.h" 144676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich#include "llvm/Support/raw_ostream.h" 154676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarichusing namespace llvm; 164676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 174676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarichchar DominanceFrontier::ID = 0; 184676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron ZwarichINITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", 194676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich "Dominance Frontier Construction", true, true) 204676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron ZwarichINITIALIZE_PASS_DEPENDENCY(DominatorTree) 214676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron ZwarichINITIALIZE_PASS_END(DominanceFrontier, "domfrontier", 224676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich "Dominance Frontier Construction", true, true) 234676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 244676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarichnamespace { 254676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich class DFCalculateWorkObject { 264676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich public: 274676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 284676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *N, 294676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *PN) 304676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 314676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich BasicBlock *currentBB; 324676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich BasicBlock *parentBB; 334676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *Node; 344676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *parentNode; 354676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich }; 364676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich} 374676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 382d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid DominanceFrontier::anchor() { } 392d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 404676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarichconst DominanceFrontier::DomSetType & 414676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron ZwarichDominanceFrontier::calculate(const DominatorTree &DT, 424676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *Node) { 434676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich BasicBlock *BB = Node->getBlock(); 444676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DomSetType *Result = NULL; 454676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 464676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich std::vector<DFCalculateWorkObject> workList; 474676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich SmallPtrSet<BasicBlock *, 32> visited; 484676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 494676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 504676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich do { 514676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DFCalculateWorkObject *currentW = &workList.back(); 524676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich assert (currentW && "Missing work object."); 534676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 544676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich BasicBlock *currentBB = currentW->currentBB; 554676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich BasicBlock *parentBB = currentW->parentBB; 564676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *currentNode = currentW->Node; 574676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const DomTreeNode *parentNode = currentW->parentNode; 584676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich assert (currentBB && "Invalid work object. Missing current Basic Block"); 594676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich assert (currentNode && "Invalid work object. Missing current Node"); 604676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DomSetType &S = Frontiers[currentBB]; 614676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 624676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // Visit each block only once. 634676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (visited.count(currentBB) == 0) { 644676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich visited.insert(currentBB); 654676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 664676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // Loop over CFG successors to calculate DFlocal[currentNode] 674676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 684676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich SI != SE; ++SI) { 694676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // Does Node immediately dominate this successor? 704676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (DT[*SI]->getIDom() != currentNode) 714676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich S.insert(*SI); 724676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 734676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 744676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 754676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // At this point, S is DFlocal. Now we union in DFup's of our children... 764676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // Loop through and visit the nodes that Node immediately dominates (Node's 774676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // children in the IDomTree) 784676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich bool visitChild = false; 794676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich for (DomTreeNode::const_iterator NI = currentNode->begin(), 804676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich NE = currentNode->end(); NI != NE; ++NI) { 814676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DomTreeNode *IDominee = *NI; 824676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich BasicBlock *childBB = IDominee->getBlock(); 834676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (visited.count(childBB) == 0) { 844676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich workList.push_back(DFCalculateWorkObject(childBB, currentBB, 854676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich IDominee, currentNode)); 864676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich visitChild = true; 874676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 884676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 894676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 904676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // If all children are visited or there is any child then pop this block 914676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich // from the workList. 924676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (!visitChild) { 934676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 944676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (!parentBB) { 954676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich Result = &S; 964676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich break; 974676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 984676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 994676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 1004676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich DomSetType &parentSet = Frontiers[parentBB]; 1014676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich for (; CDFI != CDFE; ++CDFI) { 1024676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (!DT.properlyDominates(parentNode, DT[*CDFI])) 1034676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich parentSet.insert(*CDFI); 1044676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 1054676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich workList.pop_back(); 1064676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 1074676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 1084676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } while (!workList.empty()); 1094676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 1104676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich return *Result; 1114676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich} 1124676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 1134676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarichvoid DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { 1144676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich for (const_iterator I = begin(), E = end(); I != E; ++I) { 1154676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich OS << " DomFrontier for BB "; 1164676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (I->first) 1174676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich WriteAsOperand(OS, I->first, false); 1184676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich else 1194676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich OS << " <<exit node>>"; 1204676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich OS << " is:\t"; 1214676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 1224676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich const std::set<BasicBlock*> &BBs = I->second; 1234676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 1244676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 1254676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich I != E; ++I) { 1264676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich OS << ' '; 1274676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich if (*I) 1284676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich WriteAsOperand(OS, *I, false); 1294676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich else 1304676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich OS << "<<exit node>>"; 1314676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 1324676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich OS << "\n"; 1334676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich } 1344676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich} 1354676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 1364676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarichvoid DominanceFrontierBase::dump() const { 1374676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich print(dbgs()); 1384676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich} 1394676599e30da78d39d5fe8649a0e5dcb2b6b1372Cameron Zwarich 140