X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=34417505814f7d8b53230acfb20e6abcb2fd1a06;hb=d2e63b7fdbdfd0f6986cc1563a6f0cc9446926c9;hp=0ddc370f4779ec193e4e8796cf3eb0a0275c942b;hpb=3e317534c7fd5ddbb340770926961c800f3d11c3;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 0ddc370f477..34417505814 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -16,459 +16,330 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Support/CFG.h" -#include "llvm/Assembly/Writer.h" +#include "llvm/Support/Compiler.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetOperations.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/DominatorInternals.h" +#include "llvm/Instructions.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/CommandLine.h" #include -#include using namespace llvm; +// Always verify dominfo if expensive checking is enabled. +#ifdef XDEBUG +bool VerifyDomInfo = true; +#else +bool VerifyDomInfo = false; +#endif +static cl::opt +VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), + cl::desc("Verify dominator info (time consuming)")); + //===----------------------------------------------------------------------===// -// ImmediateDominators Implementation +// DominatorTree Implementation //===----------------------------------------------------------------------===// // -// Immediate Dominators construction - This pass constructs immediate dominator -// information for a flow-graph based on the algorithm described in this -// document: -// -// A Fast Algorithm for Finding Dominators in a Flowgraph -// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. -// -// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and -// LINK, but it turns out that the theoretically slower O(n*log(n)) -// implementation is actually faster than the "efficient" algorithm (even for -// large CFGs) because the constant overheads are substantially smaller. The -// lower-complexity version can be enabled with the following #define: -// -#define BALANCE_IDOM_TREE 0 +// Provide public access to DominatorTree information. Implementation details +// can be found in DominatorCalculation.h. // //===----------------------------------------------------------------------===// -static RegisterAnalysis -C("idom", "Immediate Dominators Construction", true); - -unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, - unsigned N) { - VInfo.Semi = ++N; - VInfo.Label = V; +TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase); +TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase); - Vertex.push_back(V); // Vertex[n] = V; - //Info[V].Ancestor = 0; // Ancestor[n] = 0 - //Child[V] = 0; // Child[v] = 0 - VInfo.Size = 1; // Size[v] = 1 +char DominatorTree::ID = 0; +static RegisterPass +E("domtree", "Dominator Tree Construction", true, true); - for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { - InfoRec &SuccVInfo = Info[*SI]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = V; - N = DFSPass(*SI, SuccVInfo, N); - } - } - return N; +bool DominatorTree::runOnFunction(Function &F) { + DT->recalculate(F); + return false; } -void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) { - BasicBlock *VAncestor = VInfo.Ancestor; - InfoRec &VAInfo = Info[VAncestor]; - if (VAInfo.Ancestor == 0) - return; +void DominatorTree::verifyAnalysis() const { + if (!VerifyDomInfo) return; - Compress(VAncestor, VAInfo); + Function &F = *getRoot()->getParent(); - BasicBlock *VAncestorLabel = VAInfo.Label; - BasicBlock *VLabel = VInfo.Label; - if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) - VInfo.Label = VAncestorLabel; - - VInfo.Ancestor = VAInfo.Ancestor; + DominatorTree OtherDT; + OtherDT.getBase().recalculate(F); + assert(!compare(OtherDT) && "Invalid DominatorTree info!"); } -BasicBlock *ImmediateDominators::Eval(BasicBlock *V) { - InfoRec &VInfo = Info[V]; -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - if (VInfo.Ancestor == 0) - return V; - Compress(V, VInfo); - return VInfo.Label; -#else - // Lower-complexity but slower implementation - if (VInfo.Ancestor == 0) - return VInfo.Label; - Compress(V, VInfo); - BasicBlock *VLabel = VInfo.Label; - - BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; - if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) - return VLabel; - else - return VAncestorLabel; -#endif +void DominatorTree::print(raw_ostream &OS, const Module *) const { + DT->print(OS); } -void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - WInfo.Ancestor = V; -#else - // Lower-complexity but slower implementation - BasicBlock *WLabel = WInfo.Label; - unsigned WLabelSemi = Info[WLabel].Semi; - BasicBlock *S = W; - InfoRec *SInfo = &Info[S]; - - BasicBlock *SChild = SInfo->Child; - InfoRec *SChildInfo = &Info[SChild]; - - while (WLabelSemi < Info[SChildInfo->Label].Semi) { - BasicBlock *SChildChild = SChildInfo->Child; - if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { - SChildInfo->Ancestor = S; - SInfo->Child = SChild = SChildChild; - SChildInfo = &Info[SChild]; - } else { - SChildInfo->Size = SInfo->Size; - S = SInfo->Ancestor = SChild; - SInfo = SChildInfo; - SChild = SChildChild; - SChildInfo = &Info[SChild]; - } - } - - InfoRec &VInfo = Info[V]; - SInfo->Label = WLabel; - - assert(V != W && "The optimization here will not work in this case!"); - unsigned WSize = WInfo.Size; - unsigned VSize = (VInfo.Size += WSize); - - if (VSize < 2*WSize) - std::swap(S, VInfo.Child); - - while (S) { - SInfo = &Info[S]; - SInfo->Ancestor = V; - S = SInfo->Child; - } -#endif +// dominates - Return true if A dominates a use in B. This performs the +// special checks necessary if A and B are in the same basic block. +bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{ + const BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); + + // If A is an invoke instruction, its value is only available in this normal + // successor block. + if (const InvokeInst *II = dyn_cast(A)) + BBA = II->getNormalDest(); + + if (BBA != BBB) return dominates(BBA, BBB); + + // It is not possible to determine dominance between two PHI nodes + // based on their ordering. + if (isa(A) && isa(B)) + return false; + + // Loop through the basic block until we find A or B. + BasicBlock::const_iterator I = BBA->begin(); + for (; &*I != A && &*I != B; ++I) + /*empty*/; + + return &*I == A; } -bool ImmediateDominators::runOnFunction(Function &F) { - IDoms.clear(); // Reset from the last time we were run... - BasicBlock *Root = &F.getEntryBlock(); - Roots.clear(); - Roots.push_back(Root); - - Vertex.push_back(0); - - // Step #1: Number blocks in depth-first order and initialize variables used - // in later stages of the algorithm. - unsigned N = 0; - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - N = DFSPass(Roots[i], Info[Roots[i]], 0); - - for (unsigned i = N; i >= 2; --i) { - BasicBlock *W = Vertex[i]; - InfoRec &WInfo = Info[W]; - - // Step #2: Calculate the semidominators of all vertices - for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) - if (Info.count(*PI)) { // Only if this predecessor is reachable! - unsigned SemiU = Info[Eval(*PI)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; - } - - Info[Vertex[WInfo.Semi]].Bucket.push_back(W); - - BasicBlock *WParent = WInfo.Parent; - Link(WParent, W, WInfo); - - // Step #3: Implicitly define the immediate dominator of vertices - std::vector &WParentBucket = Info[WParent].Bucket; - while (!WParentBucket.empty()) { - BasicBlock *V = WParentBucket.back(); - WParentBucket.pop_back(); - BasicBlock *U = Eval(V); - IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; - } - } +//===----------------------------------------------------------------------===// +// DominanceFrontier Implementation +//===----------------------------------------------------------------------===// - // Step #4: Explicitly define the immediate dominator of each vertex - for (unsigned i = 2; i <= N; ++i) { - BasicBlock *W = Vertex[i]; - BasicBlock *&WIDom = IDoms[W]; - if (WIDom != Vertex[Info[W].Semi]) - WIDom = IDoms[WIDom]; - } +char DominanceFrontier::ID = 0; +static RegisterPass +G("domfrontier", "Dominance Frontier Construction", true, true); - // Free temporary memory used to construct idom's - Info.clear(); - std::vector().swap(Vertex); +void DominanceFrontier::verifyAnalysis() const { + if (!VerifyDomInfo) return; - return false; -} + DominatorTree &DT = getAnalysis(); -void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const { - Function *F = getRoots()[0]->getParent(); - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - o << " Immediate Dominator For Basic Block:"; - WriteAsOperand(o, I, false); - o << " is:"; - if (BasicBlock *ID = get(I)) - WriteAsOperand(o, ID, false); - else - o << " <>"; - o << "\n"; - } - o << "\n"; + DominanceFrontier OtherDF; + const std::vector &DTRoots = DT.getRoots(); + OtherDF.calculate(DT, DT.getNode(DTRoots[0])); + assert(!compare(OtherDF) && "Invalid DominanceFrontier info!"); } +// NewBB is split and now it has one successor. Update dominace frontier to +// reflect this change. +void DominanceFrontier::splitBlock(BasicBlock *NewBB) { + assert(NewBB->getTerminator()->getNumSuccessors() == 1 + && "NewBB should have a single successor!"); + BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); + + SmallVector PredBlocks; + for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); + PI != PE; ++PI) + PredBlocks.push_back(*PI); + + if (PredBlocks.empty()) + // If NewBB does not have any predecessors then it is a entry block. + // In this case, NewBB and its successor NewBBSucc dominates all + // other blocks. + return; + // NewBBSucc inherits original NewBB frontier. + DominanceFrontier::iterator NewBBI = find(NewBB); + if (NewBBI != end()) { + DominanceFrontier::DomSetType NewBBSet = NewBBI->second; + DominanceFrontier::DomSetType NewBBSuccSet; + NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end()); + addBasicBlock(NewBBSucc, NewBBSuccSet); + } -//===----------------------------------------------------------------------===// -// DominatorSet Implementation -//===----------------------------------------------------------------------===// - -static RegisterAnalysis -B("domset", "Dominator Set Construction", true); - -// dominates - Return true if A dominates B. This performs the special checks -// necessary if A and B are in the same basic block. -// -bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); - if (BBA != BBB) return dominates(BBA, BBB); - - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; + // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the + // DF(PredBlocks[0]) without the stuff that the new block does not dominate + // a predecessor of. + DominatorTree &DT = getAnalysis(); + if (DT.dominates(NewBB, NewBBSucc)) { + DominanceFrontier::iterator DFI = find(PredBlocks[0]); + if (DFI != end()) { + DominanceFrontier::DomSetType Set = DFI->second; + // Filter out stuff in Set that we do not dominate a predecessor of. + for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), + E = Set.end(); SetI != E;) { + bool DominatesPred = false; + for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); + PI != E; ++PI) + if (DT.dominates(NewBB, *PI)) + DominatesPred = true; + if (!DominatesPred) + Set.erase(SetI++); + else + ++SetI; + } - if(!IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; + if (NewBBI != end()) { + for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), + E = Set.end(); SetI != E; ++SetI) { + BasicBlock *SB = *SetI; + addToFrontier(NewBBI, SB); + } + } else + addBasicBlock(NewBB, Set); + } + } else { - // A post-dominates B if B is found first in the basic block. - return &*I == B; + // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate + // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> + // NewBBSucc)). NewBBSucc is the single successor of NewBB. + DominanceFrontier::DomSetType NewDFSet; + NewDFSet.insert(NewBBSucc); + addBasicBlock(NewBB, NewDFSet); } -} - + + // Now we must loop over all of the dominance frontiers in the function, + // replacing occurrences of NewBBSucc with NewBB in some cases. All + // blocks that dominate a block in PredBlocks and contained NewBBSucc in + // their dominance frontier must be updated to contain NewBB instead. + // + for (Function::iterator FI = NewBB->getParent()->begin(), + FE = NewBB->getParent()->end(); FI != FE; ++FI) { + DominanceFrontier::iterator DFI = find(FI); + if (DFI == end()) continue; // unreachable block. + + // Only consider nodes that have NewBBSucc in their dominator frontier. + if (!DFI->second.count(NewBBSucc)) continue; + + // Verify whether this block dominates a block in predblocks. If not, do + // not update it. + bool BlockDominatesAny = false; + for (SmallVectorImpl::const_iterator BI = PredBlocks.begin(), + BE = PredBlocks.end(); BI != BE; ++BI) { + if (DT.dominates(FI, *BI)) { + BlockDominatesAny = true; + break; + } + } -// runOnFunction - This method calculates the forward dominator sets for the -// specified function. -// -bool DominatorSet::runOnFunction(Function &F) { - BasicBlock *Root = &F.getEntryBlock(); - Roots.clear(); - Roots.push_back(Root); - assert(pred_begin(Root) == pred_end(Root) && - "Root node has predecessors in function!"); - - ImmediateDominators &ID = getAnalysis(); - Doms.clear(); - if (Roots.empty()) return false; - - // Root nodes only dominate themselves. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - Doms[Roots[i]].insert(Roots[i]); - - // Loop over all of the blocks in the function, calculating dominator sets for - // each function. - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (BasicBlock *IDom = ID[I]) { // Get idom if block is reachable - DomSetType &DS = Doms[I]; - assert(DS.empty() && "Domset already filled in for this block?"); - DS.insert(I); // Blocks always dominate themselves - - // Insert all dominators into the set... - while (IDom) { - // If we have already computed the dominator sets for our immediate - // dominator, just use it instead of walking all the way up to the root. - DomSetType &IDS = Doms[IDom]; - if (!IDS.empty()) { - DS.insert(IDS.begin(), IDS.end()); + // If NewBBSucc should not stay in our dominator frontier, remove it. + // We remove it unless there is a predecessor of NewBBSucc that we + // dominate, but we don't strictly dominate NewBBSucc. + bool ShouldRemove = true; + if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { + // Okay, we know that PredDom does not strictly dominate NewBBSucc. + // Check to see if it dominates any predecessors of NewBBSucc. + for (pred_iterator PI = pred_begin(NewBBSucc), + E = pred_end(NewBBSucc); PI != E; ++PI) + if (DT.dominates(FI, *PI)) { + ShouldRemove = false; break; - } else { - DS.insert(IDom); - IDom = ID[IDom]; } - } - } else { - // Ensure that every basic block has at least an empty set of nodes. This - // is important for the case when there is unreachable blocks. - Doms[I]; } - - return false; -} - -void DominatorSet::stub() {} - -namespace llvm { -static std::ostream &operator<<(std::ostream &o, - const std::set &BBs) { - for (std::set::const_iterator I = BBs.begin(), E = BBs.end(); - I != E; ++I) - if (*I) - WriteAsOperand(o, *I, false); - else - o << " <>"; - return o; -} -} - -void DominatorSetBase::print(std::ostream &o, const Module* ) const { - for (const_iterator I = begin(), E = end(); I != E; ++I) { - o << " DomSet For BB: "; - if (I->first) - WriteAsOperand(o, I->first, false); - else - o << " <>"; - o << " is:\t" << I->second << "\n"; - } -} - -//===----------------------------------------------------------------------===// -// DominatorTree Implementation -//===----------------------------------------------------------------------===// - -static RegisterAnalysis -E("domtree", "Dominator Tree Construction", true); - -// DominatorTreeBase::reset - Free all of the tree node memory. -// -void DominatorTreeBase::reset() { - for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) - delete I->second; - Nodes.clear(); - RootNode = 0; -} - -void DominatorTreeBase::Node::setIDom(Node *NewIDom) { - assert(IDom && "No immediate dominator?"); - if (IDom != NewIDom) { - std::vector::iterator I = - std::find(IDom->Children.begin(), IDom->Children.end(), this); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); - - // Switch to new dominator - IDom = NewIDom; - IDom->Children.push_back(this); + + if (ShouldRemove) + removeFromFrontier(DFI, NewBBSucc); + if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB))) + addToFrontier(DFI, NewBB); } } -DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) { - Node *&BBNode = Nodes[BB]; - if (BBNode) return BBNode; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate dominator. - BasicBlock *IDom = getAnalysis()[BB]; - Node *IDomNode = getNodeForBlock(IDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - return BBNode = IDomNode->addChild(new Node(BB, IDomNode)); +namespace { + class DFCalculateWorkObject { + public: + DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, + const DomTreeNode *N, + const DomTreeNode *PN) + : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} + BasicBlock *currentBB; + BasicBlock *parentBB; + const DomTreeNode *Node; + const DomTreeNode *parentNode; + }; } -void DominatorTree::calculate(const ImmediateDominators &ID) { - assert(Roots.size() == 1 && "DominatorTree should have 1 root block!"); - BasicBlock *Root = Roots[0]; - Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... - - Function *F = Root->getParent(); - // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) - if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block. - Node *&BBNode = Nodes[I]; - if (!BBNode) { // Haven't calculated this node yet? - // Get or calculate the node for the immediate dominator - Node *IDomNode = getNodeForBlock(ImmDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - BBNode = IDomNode->addChild(new Node(I, IDomNode)); +const DominanceFrontier::DomSetType & +DominanceFrontier::calculate(const DominatorTree &DT, + const DomTreeNode *Node) { + BasicBlock *BB = Node->getBlock(); + DomSetType *Result = NULL; + + std::vector workList; + SmallPtrSet visited; + + workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); + do { + DFCalculateWorkObject *currentW = &workList.back(); + assert (currentW && "Missing work object."); + + BasicBlock *currentBB = currentW->currentBB; + BasicBlock *parentBB = currentW->parentBB; + const DomTreeNode *currentNode = currentW->Node; + const DomTreeNode *parentNode = currentW->parentNode; + assert (currentBB && "Invalid work object. Missing current Basic Block"); + assert (currentNode && "Invalid work object. Missing current Node"); + DomSetType &S = Frontiers[currentBB]; + + // Visit each block only once. + if (visited.count(currentBB) == 0) { + visited.insert(currentBB); + + // Loop over CFG successors to calculate DFlocal[currentNode] + for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); + SI != SE; ++SI) { + // Does Node immediately dominate this successor? + if (DT[*SI]->getIDom() != currentNode) + S.insert(*SI); } } -} - -static std::ostream &operator<<(std::ostream &o, - const DominatorTreeBase::Node *Node) { - if (Node->getBlock()) - WriteAsOperand(o, Node->getBlock(), false); - else - o << " <>"; - return o << "\n"; -} -static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o, - unsigned Lev) { - o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; - for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end(); - I != E; ++I) - PrintDomTree(*I, o, Lev+1); -} - -void DominatorTreeBase::print(std::ostream &o, const Module* ) const { - o << "=============================--------------------------------\n" - << "Inorder Dominator Tree:\n"; - PrintDomTree(getRootNode(), o, 1); -} - - -//===----------------------------------------------------------------------===// -// DominanceFrontier Implementation -//===----------------------------------------------------------------------===// - -static RegisterAnalysis -G("domfrontier", "Dominance Frontier Construction", true); + // At this point, S is DFlocal. Now we union in DFup's of our children... + // Loop through and visit the nodes that Node immediately dominates (Node's + // children in the IDomTree) + bool visitChild = false; + for (DomTreeNode::const_iterator NI = currentNode->begin(), + NE = currentNode->end(); NI != NE; ++NI) { + DomTreeNode *IDominee = *NI; + BasicBlock *childBB = IDominee->getBlock(); + if (visited.count(childBB) == 0) { + workList.push_back(DFCalculateWorkObject(childBB, currentBB, + IDominee, currentNode)); + visitChild = true; + } + } -const DominanceFrontier::DomSetType & -DominanceFrontier::calculate(const DominatorTree &DT, - const DominatorTree::Node *Node) { - // Loop over CFG successors to calculate DFlocal[Node] - BasicBlock *BB = Node->getBlock(); - DomSetType &S = Frontiers[BB]; // The new set to fill in... + // If all children are visited or there is any child then pop this block + // from the workList. + if (!visitChild) { - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); - SI != SE; ++SI) { - // Does Node immediately dominate this successor? - if (DT[*SI]->getIDom() != Node) - S.insert(*SI); - } + if (!parentBB) { + Result = &S; + break; + } - // At this point, S is DFlocal. Now we union in DFup's of our children... - // Loop through and visit the nodes that Node immediately dominates (Node's - // children in the IDomTree) - // - for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); - NI != NE; ++NI) { - DominatorTree::Node *IDominee = *NI; - const DomSetType &ChildDF = calculate(DT, IDominee); - - DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); - for (; CDFI != CDFE; ++CDFI) { - if (!Node->properlyDominates(DT[*CDFI])) - S.insert(*CDFI); + DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); + DomSetType &parentSet = Frontiers[parentBB]; + for (; CDFI != CDFE; ++CDFI) { + if (!DT.properlyDominates(parentNode, DT[*CDFI])) + parentSet.insert(*CDFI); + } + workList.pop_back(); } - } - return S; + } while (!workList.empty()); + + return *Result; } -void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { +void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { for (const_iterator I = begin(), E = end(); I != E; ++I) { - o << " DomFrontier for BB"; + OS << " DomFrontier for BB "; if (I->first) - WriteAsOperand(o, I->first, false); + WriteAsOperand(OS, I->first, false); else - o << " <>"; - o << " is:\t" << I->second << "\n"; + OS << " <>"; + OS << " is:\t"; + + const std::set &BBs = I->second; + + for (std::set::const_iterator I = BBs.begin(), E = BBs.end(); + I != E; ++I) { + OS << ' '; + if (*I) + WriteAsOperand(OS, *I, false); + else + OS << "<>"; + } + OS << "\n"; } }