X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FPostDominators.cpp;h=d1fe9dd7f6614ef8e8e4be6eca4db92437922d73;hb=663e711dc235cae94eb50abb1c0571fd0b3a6a35;hp=c241646b636441346340b4475e91e8348d752612;hpb=f0604b84c7273fc2503454ecaa198eaee5b615bd;p=oota-llvm.git diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index c241646b636..d1fe9dd7f66 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -1,383 +1,388 @@ -//===- DominatorSet.cpp - Dominator Set Calculation --------------*- C++ -*--=// +//===- PostDominators.cpp - Post-Dominator Calculation --------------------===// // -// This file provides a simple class to calculate the dominator set of a method. +// 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. // //===----------------------------------------------------------------------===// - -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/SimplifyCFG.h" // To get cfg::UnifyAllExitNodes -#include "llvm/Support/DepthFirstIterator.h" -#include "llvm/Support/STLExtras.h" -#include "llvm/Method.h" -#include - -//===----------------------------------------------------------------------===// -// Helper Template +// +// This file implements the post-dominator construction algorithms. +// //===----------------------------------------------------------------------===// -// set_intersect - Identical to set_intersection, except that it works on -// set<>'s and is nicer to use. Functionally, this iterates through S1, -// removing elements that are not contained in S2. -// -template -void set_intersect(set &S1, const set &S2) { - for (typename set::iterator I = S1.begin(); I != S1.end();) { - const Ty &E = *I; - ++I; - if (!S2.count(E)) S1.erase(E); // Erase element if not in S2 - } -} +#include "llvm/Analysis/PostDominators.h" +#include "llvm/Instructions.h" +#include "llvm/Support/CFG.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SetOperations.h" +using namespace llvm; //===----------------------------------------------------------------------===// -// DominatorBase Implementation +// ImmediatePostDominators Implementation //===----------------------------------------------------------------------===// -bool cfg::DominatorBase::isPostDominator() const { - // Root can be null if there is no exit node from the CFG and is postdom set - return Root == 0 || Root != Root->getParent()->front(); -} +static RegisterPass +D("postidom", "Immediate Post-Dominators Construction", true); +unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, + unsigned N) { + std::vector > workStack; + std::set visited; + workStack.push_back(std::make_pair(V, &VInfo)); -//===----------------------------------------------------------------------===// -// DominatorSet Implementation -//===----------------------------------------------------------------------===// + do { + BasicBlock *currentBB = workStack.back().first; + InfoRec *currentVInfo = workStack.back().second; -// DominatorSet ctor - Build either the dominator set or the post-dominator -// set for a method... -// -cfg::DominatorSet::DominatorSet(const Method *M) : DominatorBase(M->front()) { - calcForwardDominatorSet(M); -} + // Visit each block only once. + if (visited.count(currentBB) == 0) { -// calcForwardDominatorSet - This method calculates the forward dominator sets -// for the specified method. -// -void cfg::DominatorSet::calcForwardDominatorSet(const Method *M) { - assert(Root && M && "Can't build dominator set of null method!"); - assert(Root->use_size() == 0 && "Root node has predecessors in method!"); - bool Changed; - do { - Changed = false; - - DomSetType WorkingSet; - df_iterator It = df_begin(M), End = df_end(M); - for ( ; It != End; ++It) { - const BasicBlock *BB = *It; - BasicBlock::pred_const_iterator PI = BB->pred_begin(), - PEnd = BB->pred_end(); - if (PI != PEnd) { // Is there SOME predecessor? - // Loop until we get to a predecessor that has had it's dom set filled - // in at least once. We are guaranteed to have this because we are - // traversing the graph in DFO and have handled start nodes specially. - // - while (Doms[*PI].size() == 0) ++PI; - WorkingSet = Doms[*PI]; - - for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets - DomSetType &PredSet = Doms[*PI]; - if (PredSet.size()) - set_intersect(WorkingSet, PredSet); - } - } - - WorkingSet.insert(BB); // A block always dominates itself - DomSetType &BBSet = Doms[BB]; - if (BBSet != WorkingSet) { - BBSet.swap(WorkingSet); // Constant time operation! - Changed = true; // The sets changed. + visited.insert(currentBB); + currentVInfo->Semi = ++N; + currentVInfo->Label = currentBB; + + Vertex.push_back(currentBB); // Vertex[n] = current; + // Info[currentBB].Ancestor = 0; + // Ancestor[n] = 0 + // Child[currentBB] = 0; + currentVInfo->Size = 1; // Size[currentBB] = 1 + } + + // Visit children + bool visitChild = false; + for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB); + PI != PE && !visitChild; ++PI) { + InfoRec &SuccVInfo = Info[*PI]; + if (SuccVInfo.Semi == 0) { + SuccVInfo.Parent = currentBB; + if (visited.count (*PI) == 0) { + workStack.push_back(std::make_pair(*PI, &SuccVInfo)); + visitChild = true; + } } - WorkingSet.clear(); // Clear out the set for next iteration } - } while (Changed); + + // If all children are visited or if this block has no child then pop this + // block out of workStack. + if (!visitChild) + workStack.pop_back(); + + } while (!workStack.empty()); + + return N; } -// Postdominator set constructor. This ctor converts the specified method to -// only have a single exit node (return stmt), then calculates the post -// dominance sets for the method. -// -cfg::DominatorSet::DominatorSet(Method *M, bool PostDomSet) - : DominatorBase(M->front()) { - if (!PostDomSet) { calcForwardDominatorSet(M); return; } - - Root = cfg::UnifyAllExitNodes(M); - if (Root == 0) { // No exit node for the method? Postdomsets are all empty - for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) - Doms[*MI] = DomSetType(); +void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) { + BasicBlock *VAncestor = VInfo.Ancestor; + InfoRec &VAInfo = Info[VAncestor]; + if (VAInfo.Ancestor == 0) return; - } - - bool Changed; - do { - Changed = false; - - set Visited; - DomSetType WorkingSet; - idf_iterator It = idf_begin(Root), End = idf_end(Root); - for ( ; It != End; ++It) { - const BasicBlock *BB = *It; - BasicBlock::succ_const_iterator PI = BB->succ_begin(), - PEnd = BB->succ_end(); - if (PI != PEnd) { // Is there SOME predecessor? - // Loop until we get to a successor that has had it's dom set filled - // in at least once. We are guaranteed to have this because we are - // traversing the graph in DFO and have handled start nodes specially. - // - while (Doms[*PI].size() == 0) ++PI; - WorkingSet = Doms[*PI]; - - for (++PI; PI != PEnd; ++PI) { // Intersect all of the successor sets - DomSetType &PredSet = Doms[*PI]; - if (PredSet.size()) - set_intersect(WorkingSet, PredSet); - } - } - - WorkingSet.insert(BB); // A block always dominates itself - DomSetType &BBSet = Doms[BB]; - if (BBSet != WorkingSet) { - BBSet.swap(WorkingSet); // Constant time operation! - Changed = true; // The sets changed. - } - WorkingSet.clear(); // Clear out the set for next iteration - } - } while (Changed); + + Compress(VAncestor, VAInfo); + + BasicBlock *VAncestorLabel = VAInfo.Label; + BasicBlock *VLabel = VInfo.Label; + if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) + VInfo.Label = VAncestorLabel; + + VInfo.Ancestor = VAInfo.Ancestor; } +BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) { + InfoRec &VInfo = Info[V]; -//===----------------------------------------------------------------------===// -// ImmediateDominators Implementation -//===----------------------------------------------------------------------===// + // Higher-complexity but faster implementation + if (VInfo.Ancestor == 0) + return V; + Compress(V, VInfo); + return VInfo.Label; +} -// calcIDoms - Calculate the immediate dominator mapping, given a set of -// dominators for every basic block. -void cfg::ImmediateDominators::calcIDoms(const DominatorSet &DS) { - // Loop over all of the nodes that have dominators... figuring out the IDOM - // for each node... - // - for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end(); - DI != DEnd; ++DI) { - const BasicBlock *BB = DI->first; - const DominatorSet::DomSetType &Dominators = DI->second; - unsigned DomSetSize = Dominators.size(); - if (DomSetSize == 1) continue; // Root node... IDom = null - - // Loop over all dominators of this node. This corresponds to looping over - // nodes in the dominator chain, looking for a node whose dominator set is - // equal to the current nodes, except that the current node does not exist - // in it. This means that it is one level higher in the dom chain than the - // current node, and it is our idom! - // - DominatorSet::DomSetType::const_iterator I = Dominators.begin(); - DominatorSet::DomSetType::const_iterator End = Dominators.end(); - for (; I != End; ++I) { // Iterate over dominators... - // All of our dominators should form a chain, where the number of elements - // in the dominator set indicates what level the node is at in the chain. - // We want the node immediately above us, so it will have an identical - // dominator set, except that BB will not dominate it... therefore it's - // dominator set size will be one less than BB's... - // - if (DS.getDominators(*I).size() == DomSetSize - 1) { - IDoms[BB] = *I; - break; +void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W, + InfoRec &WInfo) { + // Higher-complexity but faster implementation + WInfo.Ancestor = V; +} + +bool ImmediatePostDominators::runOnFunction(Function &F) { + IDoms.clear(); // Reset from the last time we were run... + Roots.clear(); + + // Step #0: Scan the function looking for the root nodes of the post-dominance + // relationships. These blocks, which have no successors, end with return and + // unwind instructions. + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + if (succ_begin(I) == succ_end(I)) + Roots.push_back(I); + + 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]], N); + + for (unsigned i = N; i >= 2; --i) { + BasicBlock *W = Vertex[i]; + InfoRec &WInfo = Info[W]; + + // Step #2: Calculate the semidominators of all vertices + for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI) + if (Info.count(*SI)) { // Only if this predecessor is reachable! + unsigned SemiU = Info[Eval(*SI)].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; } } + + // 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]; + } + + // Free temporary memory used to construct idom's + Info.clear(); + std::vector().swap(Vertex); + + return false; } - //===----------------------------------------------------------------------===// -// DominatorTree Implementation +// PostDominatorSet Implementation //===----------------------------------------------------------------------===// -// DominatorTree dtor - Free all of the tree node memory. -// -cfg::DominatorTree::~DominatorTree() { - for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) - delete I->second; -} +static RegisterPass +B("postdomset", "Post-Dominator Set Construction", true); +// Postdominator set construction. This converts the specified function to only +// have a single exit node (return stmt), then calculates the post dominance +// sets for the function. +// +bool PostDominatorSet::runOnFunction(Function &F) { + // Scan the function looking for the root nodes of the post-dominance + // relationships. These blocks end with return and unwind instructions. + // While we are iterating over the function, we also initialize all of the + // domsets to empty. + Roots.clear(); + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + if (succ_begin(I) == succ_end(I)) + Roots.push_back(I); + + // If there are no exit nodes for the function, postdomsets are all empty. + // This can happen if the function just contains an infinite loop, for + // example. + ImmediatePostDominators &IPD = getAnalysis(); + Doms.clear(); // Reset from the last time we were run... + if (Roots.empty()) return false; + + // If we have more than one root, we insert an artificial "null" exit, which + // has "virtual edges" to each of the real exit nodes. + //if (Roots.size() > 1) + // Doms[0].insert(0); + + // 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 *IPDom = IPD[I]) { // Get idom if block is reachable + DomSetType &DS = Doms[I]; + assert(DS.empty() && "PostDomset already filled in for this block?"); + DS.insert(I); // Blocks always dominate themselves + + // Insert all dominators into the set... + while (IPDom) { + // If we have already computed the dominator sets for our immediate post + // dominator, just use it instead of walking all the way up to the root. + DomSetType &IPDS = Doms[IPDom]; + if (!IPDS.empty()) { + DS.insert(IPDS.begin(), IPDS.end()); + break; + } else { + DS.insert(IPDom); + IPDom = IPD[IPDom]; + } + } + } 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]; + } -cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms) - : DominatorBase(IDoms.getRoot()) { - const Method *M = Root->getParent(); + return false; +} - Nodes[Root] = new Node(Root, 0); // Add a node for the root... +//===----------------------------------------------------------------------===// +// PostDominatorTree Implementation +//===----------------------------------------------------------------------===// - // Iterate over all nodes in depth first order... - for (df_iterator I = df_begin(M), E = df_end(M); I != E; ++I) { - const BasicBlock *BB = *I, *IDom = IDoms[*I]; - - if (IDom != 0) { // Ignore the root node and other nasty nodes - // We know that the immediate dominator should already have a node, - // because we are traversing the CFG in depth first order! - // - assert(Nodes[IDom] && "No node for IDOM?"); - Node *IDomNode = Nodes[IDom]; - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); - } - } +static RegisterPass +F("postdomtree", "Post-Dominator Tree Construction", true); + +DominatorTreeBase::Node *PostDominatorTree::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 postdominator. + BasicBlock *IPDom = getAnalysis()[BB]; + Node *IPDomNode = getNodeForBlock(IPDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode)); } -void cfg::DominatorTree::calculate(const DominatorSet &DS) { - Nodes[Root] = new Node(Root, 0); // Add a node for the root... - - if (!isPostDominator()) { - // Iterate over all nodes in depth first order... - for (df_iterator I = df_begin(Root), E = df_end(Root); - I != E; ++I) { - const BasicBlock *BB = *I; - const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); - unsigned DomSetSize = Dominators.size(); - if (DomSetSize == 1) continue; // Root node... IDom = null - - // Loop over all dominators of this node. This corresponds to looping over - // nodes in the dominator chain, looking for a node whose dominator set is - // equal to the current nodes, except that the current node does not exist - // in it. This means that it is one level higher in the dom chain than the - // current node, and it is our idom! We know that we have already added - // a DominatorTree node for our idom, because the idom must be a - // predecessor in the depth first order that we are iterating through the - // method. - // - DominatorSet::DomSetType::const_iterator I = Dominators.begin(); - DominatorSet::DomSetType::const_iterator End = Dominators.end(); - for (; I != End; ++I) { // Iterate over dominators... - // All of our dominators should form a chain, where the number of - // elements in the dominator set indicates what level the node is at in - // the chain. We want the node immediately above us, so it will have - // an identical dominator set, except that BB will not dominate it... - // therefore it's dominator set size will be one less than BB's... - // - if (DS.getDominators(*I).size() == DomSetSize - 1) { - // We know that the immediate dominator should already have a node, - // because we are traversing the CFG in depth first order! - // - Node *IDomNode = Nodes[*I]; - assert(IDomNode && "No node for IDOM?"); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); - break; - } - } - } - } else if (Root) { - // Iterate over all nodes in depth first order... - for (idf_iterator I = idf_begin(Root), E = idf_end(Root); - I != E; ++I) { - const BasicBlock *BB = *I; - const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); - unsigned DomSetSize = Dominators.size(); - if (DomSetSize == 1) continue; // Root node... IDom = null - - // Loop over all dominators of this node. This corresponds to looping - // over nodes in the dominator chain, looking for a node whose dominator - // set is equal to the current nodes, except that the current node does - // not exist in it. This means that it is one level higher in the dom - // chain than the current node, and it is our idom! We know that we have - // already added a DominatorTree node for our idom, because the idom must - // be a predecessor in the depth first order that we are iterating through - // the method. - // - DominatorSet::DomSetType::const_iterator I = Dominators.begin(); - DominatorSet::DomSetType::const_iterator End = Dominators.end(); - for (; I != End; ++I) { // Iterate over dominators... - // All of our dominators should form a chain, where the number of elements - // in the dominator set indicates what level the node is at in the chain. - // We want the node immediately above us, so it will have an identical - // dominator set, except that BB will not dominate it... therefore it's - // dominator set size will be one less than BB's... - // - if (DS.getDominators(*I).size() == DomSetSize - 1) { - // We know that the immediate dominator should already have a node, - // because we are traversing the CFG in depth first order! - // - Node *IDomNode = Nodes[*I]; - assert(IDomNode && "No node for IDOM?"); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); - break; - } +void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) { + if (Roots.empty()) return; + + // Add a node for the root. This node might be the actual root, if there is + // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) + // which postdominates all real exits if there are multiple exit blocks. + BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0; + Nodes[Root] = RootNode = new Node(Root, 0); + + Function *F = Roots[0]->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 *ImmPostDom = IPD.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 *IPDomNode = getNodeForBlock(ImmPostDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + BBNode = IPDomNode->addChild(new Node(I, IPDomNode)); } } - } } - - //===----------------------------------------------------------------------===// -// DominanceFrontier Implementation +// PostETForest Implementation //===----------------------------------------------------------------------===// -const cfg::DominanceFrontier::DomSetType & -cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT, - const DominatorTree::Node *Node) { - // Loop over CFG successors to calculate DFlocal[Node] - const BasicBlock *BB = Node->getNode(); - DomSetType &S = Frontiers[BB]; // The new set to fill in... - - for (BasicBlock::succ_const_iterator SI = BB->succ_begin(), - SE = BB->succ_end(); SI != SE; ++SI) { - // Does Node immediately dominate this successor? - if (DT[*SI]->getIDom() != Node) - S.insert(*SI); +static RegisterPass +G("postetforest", "Post-ET-Forest Construction", true); + +ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) { + ETNode *&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]; + + // If we are unreachable, we may not have an immediate dominator. + if (!IDom) + return BBNode = new ETNode(BB); + else { + ETNode *IDomNode = getNodeForBlock(IDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + BBNode = new ETNode(BB); + BBNode->setFather(IDomNode); + return BBNode; } +} - // 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 = calcDomFrontier(DT, IDominee); - - DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); - for (; CDFI != CDFE; ++CDFI) { - if (!Node->dominates(DT[*CDFI])) - S.insert(*CDFI); +void PostETForest::calculate(const ImmediatePostDominators &ID) { + for (unsigned i = 0, e = Roots.size(); i != e; ++i) + Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root + + // Iterate over all nodes in inverse depth first order. + for (unsigned i = 0, e = Roots.size(); i != e; ++i) + for (idf_iterator I = idf_begin(Roots[i]), + E = idf_end(Roots[i]); I != E; ++I) { + BasicBlock *BB = *I; + ETNode *&BBNode = Nodes[BB]; + if (!BBNode) { + ETNode *IDomNode = NULL; + + if (ID.get(BB)) + IDomNode = getNodeForBlock(ID.get(BB)); + + // Add a new ETNode for this BasicBlock, and set it's parent + // to it's immediate dominator. + BBNode = new ETNode(BB); + if (IDomNode) + BBNode->setFather(IDomNode); } } - return S; + int dfsnum = 0; + // Iterate over all nodes in depth first order... + for (unsigned i = 0, e = Roots.size(); i != e; ++i) + for (idf_iterator I = idf_begin(Roots[i]), + E = idf_end(Roots[i]); I != E; ++I) { + if (!getNodeForBlock(*I)->hasFather()) + getNodeForBlock(*I)->assignDFSNumber(dfsnum); + } + DFSInfoValid = true; } -const cfg::DominanceFrontier::DomSetType & -cfg::DominanceFrontier::calcPostDomFrontier(const DominatorTree &DT, - const DominatorTree::Node *Node) { +//===----------------------------------------------------------------------===// +// PostDominanceFrontier Implementation +//===----------------------------------------------------------------------===// + +static RegisterPass +H("postdomfrontier", "Post-Dominance Frontier Construction", true); + +const DominanceFrontier::DomSetType & +PostDominanceFrontier::calculate(const PostDominatorTree &DT, + const DominatorTree::Node *Node) { // Loop over CFG successors to calculate DFlocal[Node] - const BasicBlock *BB = Node->getNode(); + BasicBlock *BB = Node->getBlock(); DomSetType &S = Frontiers[BB]; // The new set to fill in... - if (!Root) return S; + if (getRoots().empty()) return S; - for (BasicBlock::pred_const_iterator SI = BB->pred_begin(), - SE = BB->pred_end(); SI != SE; ++SI) { - // Does Node immediately dominate this predeccessor? - if (DT[*SI]->getIDom() != Node) - S.insert(*SI); - } + if (BB) + for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); + SI != SE; ++SI) + // Does Node immediately dominate this predecessor? + if (DT[*SI]->getIDom() != Node) + S.insert(*SI); // 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) { + for (PostDominatorTree::Node::const_iterator + NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { DominatorTree::Node *IDominee = *NI; - const DomSetType &ChildDF = calcPostDomFrontier(DT, IDominee); + const DomSetType &ChildDF = calculate(DT, IDominee); DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); for (; CDFI != CDFE; ++CDFI) { - if (!Node->dominates(DT[*CDFI])) - S.insert(*CDFI); + if (!Node->properlyDominates(DT[*CDFI])) + S.insert(*CDFI); } } return S; } + +// Ensure that this .cpp file gets linked when PostDominators.h is used. +DEFINING_FILE_FOR(PostDominanceFrontier)