X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FPostDominators.cpp;h=1188cff0303644ebcb953eca24921a72c54e87c9;hb=3dfcf33cf897b04c95e252bbd645e9930f608701;hp=c9e15f4a51ac783cded715d7f2794d5d1d409512;hpb=94108ab8a36806d5c7fb56bed4ddffda064f5c5d;p=oota-llvm.git diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index c9e15f4a51a..1188cff0303 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -1,371 +1,266 @@ -//===- 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 // -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/SimplifyCFG.h" // To get cfg::UnifyAllExitNodes -#include "llvm/CFG.h" -#include "llvm/Tools/STLExtras.h" -#include - -//===----------------------------------------------------------------------===// -// Helper Template -//===----------------------------------------------------------------------===// - -// 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. +// 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. // -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 - } -} - //===----------------------------------------------------------------------===// -// DominatorBase Implementation +// +// This file implements the post-dominator construction algorithms. +// //===----------------------------------------------------------------------===// -bool cfg::DominatorBase::isPostDominator() const { - return Root != Root->getParent()->front(); -} - +#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; //===----------------------------------------------------------------------===// -// DominatorSet Implementation +// PostDominatorTree Implementation //===----------------------------------------------------------------------===// -// 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); -} - -// 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!"); - bool Changed; - do { - Changed = false; +char PostDominatorTree::ID = 0; +char PostDominanceFrontier::ID = 0; +static RegisterPass +F("postdomtree", "Post-Dominator Tree Construction", true); - DomSetType WorkingSet; - df_const_iterator It = df_begin(M), End = df_end(M); - for ( ; It != End; ++It) { - const BasicBlock *BB = *It; - pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB); - 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]; +unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, + unsigned N) { + std::vector > workStack; + std::set visited; + workStack.push_back(std::make_pair(V, &VInfo)); - 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. - } - WorkingSet.clear(); // Clear out the set for next iteration - } - } while (Changed); -} - -// 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); - assert(Root && "TODO: Don't handle case where there are no exit nodes yet!"); - - bool Changed; do { - Changed = false; + BasicBlock *currentBB = workStack.back().first; + InfoRec *currentVInfo = workStack.back().second; - set Visited; - DomSetType WorkingSet; - idf_const_iterator It = idf_begin(Root), End = idf_end(Root); - for ( ; It != End; ++It) { - const BasicBlock *BB = *It; - succ_const_iterator PI = succ_begin(BB), PEnd = succ_end(BB); - 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]; + // Visit each block only once. + if (visited.count(currentBB) == 0) { - 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 + 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 } - } while (Changed); -} - -//===----------------------------------------------------------------------===// -// ImmediateDominators Implementation -//===----------------------------------------------------------------------===// - -// 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; + // 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; + } } } - } -} + // If all children are visited or if this block has no child then pop this + // block out of workStack. + if (!visitChild) + workStack.pop_back(); -//===----------------------------------------------------------------------===// -// DominatorTree Implementation -//===----------------------------------------------------------------------===// + } while (!workStack.empty()); -// 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; + return N; } +void PostDominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) { + BasicBlock *VAncestor = VInfo.Ancestor; + InfoRec &VAInfo = Info[VAncestor]; + if (VAInfo.Ancestor == 0) + return; + + 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; +} -cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms) - : DominatorBase(IDoms.getRoot()) { - const Method *M = Root->getParent(); - - Nodes[Root] = new Node(Root, 0); // Add a node for the root... - - // Iterate over all nodes in depth first order... - for (df_const_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]; +BasicBlock *PostDominatorTree::Eval(BasicBlock *V) { + InfoRec &VInfo = Info[V]; - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); - } - } + // Higher-complexity but faster implementation + if (VInfo.Ancestor == 0) + return V; + Compress(V, VInfo); + return VInfo.Label; } -void cfg::DominatorTree::calculate(const DominatorSet &DS) { - Nodes[Root] = new Node(Root, 0); // Add a node for the root... +void PostDominatorTree::Link(BasicBlock *V, BasicBlock *W, + InfoRec &WInfo) { + // Higher-complexity but faster implementation + WInfo.Ancestor = V; +} - if (!isPostDominator()) { - // Iterate over all nodes in depth first order... - for (df_const_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; - } - } +void PostDominatorTree::calculate(Function &F) { + // 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)) { + Instruction *Insn = I->getTerminator(); + // Unreachable block is not a root node. + if (!isa(Insn)) + Roots.push_back(I); } - } else { - // Iterate over all nodes in depth first order... - for (idf_const_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; - } + + 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]; + } + + 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; + DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); + + // 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 = getIDom(I)) { // Reachable block. + DomTreeNode *&BBNode = DomTreeNodes[I]; + if (!BBNode) { // Haven't calculated this node yet? + // Get or calculate the node for the immediate dominator + DomTreeNode *IPDomNode = getNodeForBlock(ImmPostDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + DomTreeNode *C = new DomTreeNode(I, IPDomNode); + DomTreeNodes[I] = C; + BBNode = IPDomNode->addChild(C); + } + } + + // Free temporary memory used to construct idom's + IDoms.clear(); + Info.clear(); + std::vector().swap(Vertex); + + 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)->getIDom()) + getNodeForBlock(*I)->assignDFSNumber(dfsnum); + } + DFSInfoValid = true; } +DomTreeNode *PostDominatorTree::getNodeForBlock(BasicBlock *BB) { + DomTreeNode *&BBNode = DomTreeNodes[BB]; + if (BBNode) return BBNode; + + // Haven't calculated this node yet? Get or calculate the node for the + // immediate postdominator. + BasicBlock *IPDom = getIDom(BB); + DomTreeNode *IPDomNode = getNodeForBlock(IPDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + DomTreeNode *C = new DomTreeNode(BB, IPDomNode); + DomTreeNodes[BB] = C; + return BBNode = IPDomNode->addChild(C); +} //===----------------------------------------------------------------------===// -// DominanceFrontier Implementation +// PostDominanceFrontier 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 (succ_const_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); - } - - // 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); - } - } - - return S; -} +static RegisterPass +H("postdomfrontier", "Post-Dominance Frontier Construction", true); -const cfg::DominanceFrontier::DomSetType & -cfg::DominanceFrontier::calcPostDomFrontier(const DominatorTree &DT, - const DominatorTree::Node *Node) { +const DominanceFrontier::DomSetType & +PostDominanceFrontier::calculate(const PostDominatorTree &DT, + const DomTreeNode *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... - - for (pred_const_iterator SI = pred_begin(BB), SE = pred_end(BB); - SI != SE; ++SI) { - // Does Node immediately dominate this predeccessor? - if (DT[*SI]->getIDom() != Node) - S.insert(*SI); - } + if (getRoots().empty()) return S; + + if (BB) + for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); + SI != SE; ++SI) { + // Does Node immediately dominate this predecessor? + DomTreeNode *SINode = DT[*SI]; + if (SINode && SINode->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) { - DominatorTree::Node *IDominee = *NI; - const DomSetType &ChildDF = calcDomFrontier(DT, IDominee); + for (DomTreeNode::const_iterator + NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { + DomTreeNode *IDominee = *NI; + 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 (!DT.properlyDominates(Node, DT[*CDFI])) + S.insert(*CDFI); } } return S; } + +// Ensure that this .cpp file gets linked when PostDominators.h is used. +DEFINING_FILE_FOR(PostDominanceFrontier)