X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=lib%2FVMCore%2FDominators.cpp;h=14ec3ccd9f37f847f9b142ca1501d5c3949fa758;hb=551ccae044b0ff658fe629dd67edd5ffe75d10e8;hp=aad6e1cb386ba3d96b9c4968c98d9fa7f998861f;hpb=eb5230c4f98bd94c019bc2faed9432ca892e2f11;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index aad6e1cb386..14ec3ccd9f3 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -1,343 +1,434 @@ -//===- DominatorSet.cpp - Dominator Set Calculation --------------*- C++ -*--=// +//===- Dominators.cpp - Dominator Calculation -----------------------------===// +// +// The LLVM Compiler Infrastructure // -// This file provides a simple class to calculate the dominator set of a method. +// 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 implements simple dominator construction algorithms for finding +// forward dominators. Postdominators are available in libanalysis, but are not +// included in libvmcore, because it's not needed. Forward dominators are +// needed to support the Verifier pass. // //===----------------------------------------------------------------------===// #include "llvm/Analysis/Dominators.h" -#include "llvm/Transforms/UnifyMethodExitNodes.h" -#include "llvm/Method.h" -#include "Support/DepthFirstIterator.h" -#include "Support/STLExtras.h" -#include "Support/SetOperations.h" +#include "llvm/Support/CFG.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SetOperations.h" #include -using std::set; +using namespace llvm; //===----------------------------------------------------------------------===// -// DominatorSet Implementation +// ImmediateDominators 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 +// //===----------------------------------------------------------------------===// -AnalysisID cfg::DominatorSet::ID(AnalysisID::create()); -AnalysisID cfg::DominatorSet::PostDomID(AnalysisID::create()); +static RegisterAnalysis +C("idom", "Immediate Dominators Construction", true); -bool cfg::DominatorSet::runOnMethod(Method *M) { - Doms.clear(); // Reset from the last time we were run... +unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, + unsigned N) { + VInfo.Semi = ++N; + VInfo.Label = V; - if (isPostDominator()) - calcPostDominatorSet(M); - else - calcForwardDominatorSet(M); - return false; + 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 + + 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; } +void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) { + BasicBlock *VAncestor = VInfo.Ancestor; + InfoRec &VAInfo = Info[VAncestor]; + if (VAInfo.Ancestor == 0) + return; -// calcForwardDominatorSet - This method calculates the forward dominator sets -// for the specified method. -// -void cfg::DominatorSet::calcForwardDominatorSet(Method *M) { - Root = M->getEntryNode(); - assert(Root->pred_begin() == Root->pred_end() && - "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. - } - 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; } -// 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. -// -void cfg::DominatorSet::calcPostDominatorSet(Method *M) { - // Since we require that the unify all exit nodes pass has been run, we know - // that there can be at most one return instruction in the method left. - // Get it. - // - Root = getAnalysis().getExitNode(); +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 +} - if (Root == 0) { // No exit node for the method? Postdomsets are all empty - for (Method::const_iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) - Doms[*MI] = DomSetType(); - return; +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 +} - 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. + + +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; } - WorkingSet.clear(); // Clear out the set for next iteration + + 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; } - } while (Changed); + } + + // 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; } -// getAnalysisUsageInfo - This obviously provides a dominator set, but it also -// uses the UnifyMethodExitNodes pass if building post-dominators -// -void cfg::DominatorSet::getAnalysisUsageInfo(Pass::AnalysisSet &Requires, - Pass::AnalysisSet &Destroyed, - Pass::AnalysisSet &Provided) { - if (isPostDominator()) { - Provided.push_back(PostDomID); - Requires.push_back(UnifyMethodExitNodes::ID); - } else { - Provided.push_back(ID); +void ImmediateDominatorsBase::print(std::ostream &o) 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"; } + //===----------------------------------------------------------------------===// -// ImmediateDominators Implementation +// DominatorSet Implementation //===----------------------------------------------------------------------===// -AnalysisID cfg::ImmediateDominators::ID(AnalysisID::create()); -AnalysisID cfg::ImmediateDominators::PostDomID(AnalysisID::create()); +static RegisterAnalysis +B("domset", "Dominator Set Construction", true); -// 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; +// 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*/; + + // A dominates B if it is found first in the basic block... + return &*I == A; +} + + +// 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()); + 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; +} + +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 { + 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 //===----------------------------------------------------------------------===// -AnalysisID cfg::DominatorTree::ID(AnalysisID::create()); -AnalysisID cfg::DominatorTree::PostDomID(AnalysisID::create()); +static RegisterAnalysis +E("domtree", "Dominator Tree Construction", true); -// DominatorTree::reset - Free all of the tree node memory. +// DominatorTreeBase::reset - Free all of the tree node memory. // -void cfg::DominatorTree::reset() { +void DominatorTreeBase::reset() { for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) delete I->second; Nodes.clear(); + RootNode = 0; } - -#if 0 -// Given immediate dominators, we can also calculate the dominator tree -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_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)); - } +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); } } -#endif -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; - } +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)); +} + +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)); } } - } } +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 { + o << "=============================--------------------------------\n" + << "Inorder Dominator Tree:\n"; + PrintDomTree(getRootNode(), o, 1); +} //===----------------------------------------------------------------------===// // DominanceFrontier Implementation //===----------------------------------------------------------------------===// -AnalysisID cfg::DominanceFrontier::ID(AnalysisID::create()); -AnalysisID cfg::DominanceFrontier::PostDomID(AnalysisID::create()); +static RegisterAnalysis +G("domfrontier", "Dominance Frontier Construction", true); -const cfg::DominanceFrontier::DomSetType & -cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT, - const DominatorTree::Node *Node) { +const DominanceFrontier::DomSetType & +DominanceFrontier::calculate(const DominatorTree &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... - for (BasicBlock::succ_const_iterator SI = BB->succ_begin(), - SE = BB->succ_end(); SI != SE; ++SI) { + 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); @@ -350,7 +441,7 @@ cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT, for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { DominatorTree::Node *IDominee = *NI; - const DomSetType &ChildDF = calcDomFrontier(DT, IDominee); + const DomSetType &ChildDF = calculate(DT, IDominee); DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); for (; CDFI != CDFE; ++CDFI) { @@ -362,36 +453,14 @@ cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT, return S; } -const cfg::DominanceFrontier::DomSetType & -cfg::DominanceFrontier::calcPostDomFrontier(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... - if (!Root) 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); - } - - // 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 = calcPostDomFrontier(DT, IDominee); - - DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); - for (; CDFI != CDFE; ++CDFI) { - if (!Node->dominates(DT[*CDFI])) - S.insert(*CDFI); - } +void DominanceFrontierBase::print(std::ostream &o) const { + for (const_iterator I = begin(), E = end(); I != E; ++I) { + o << " DomFrontier for BB"; + if (I->first) + WriteAsOperand(o, I->first, false); + else + o << " <>"; + o << " is:\t" << I->second << "\n"; } - - return S; } +