diff options
author | Chris Lattner <sabre@nondot.org> | 2003-12-07 00:38:08 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2003-12-07 00:38:08 +0000 |
commit | 16addf87bf331645de63575aa15627c74b9cab66 (patch) | |
tree | 3f863f02b76b49a64d9df9ee75547992481407e8 /lib/VMCore/Dominators.cpp | |
parent | 31b935357d1396d3be32fdf24dcb0319a6908c6f (diff) | |
download | external_llvm-16addf87bf331645de63575aa15627c74b9cab66.zip external_llvm-16addf87bf331645de63575aa15627c74b9cab66.tar.gz external_llvm-16addf87bf331645de63575aa15627c74b9cab66.tar.bz2 |
Completely rewrite domset, idom, and domtree implementation. Now it is based
on the algorithm for directly computing immediate dominators presented in this
paper:
A Fast Algorithm for Finding Dominators in a Flowgraph
T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
This _substantially_ speeds up construction of all dominator related information.
Post-dominators to follow.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10301 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore/Dominators.cpp')
-rw-r--r-- | lib/VMCore/Dominators.cpp | 425 |
1 files changed, 266 insertions, 159 deletions
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index dbdb409..b2d4d94 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -22,11 +22,218 @@ using namespace llvm; //===----------------------------------------------------------------------===// +// 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 +// +//===----------------------------------------------------------------------===// + +static RegisterAnalysis<ImmediateDominators> +C("idom", "Immediate Dominators Construction", true); + +unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, + unsigned N) { + VInfo.Semi = ++N; + VInfo.Label = V; + + 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; + + 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 *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 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 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<BasicBlock*> &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<BasicBlock*>().swap(Vertex); + + return false; +} + +void ImmediateDominatorsBase::print(std::ostream &o) const { + for (const_iterator I = begin(), E = end(); I != E; ++I) { + o << " Immediate Dominator For Basic Block:"; + if (I->first) + WriteAsOperand(o, I->first, false); + else + o << " <<exit node>>"; + o << " is:"; + if (I->second) + WriteAsOperand(o, I->second, false); + else + o << " <<exit node>>"; + o << "\n"; + } + o << "\n"; +} + + + +//===----------------------------------------------------------------------===// // DominatorSet Implementation //===----------------------------------------------------------------------===// static RegisterAnalysis<DominatorSet> -A("domset", "Dominator Set Construction", true); +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. @@ -44,53 +251,45 @@ bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const { } -void DominatorSet::calculateDominatorsFromBlock(BasicBlock *RootBB) { - bool Changed; - Doms[RootBB].insert(RootBB); // Root always dominates itself... - do { - Changed = false; - - DomSetType WorkingSet; - df_iterator<BasicBlock*> It = df_begin(RootBB), End = df_end(RootBB); - for ( ; It != End; ++It) { - BasicBlock *BB = *It; - pred_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 its 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, - // except when there are unreachable blocks. - // - while (PI != PEnd && Doms[*PI].empty()) ++PI; - if (PI != PEnd) { // Not unreachable code case? - WorkingSet = Doms[*PI]; - - // Intersect all of the predecessor sets - for (++PI; PI != PEnd; ++PI) { - DomSetType &PredSet = Doms[*PI]; - if (PredSet.size()) - set_intersect(WorkingSet, PredSet); - } +void DominatorSet::recalculate() { + ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); + Doms.clear(); + if (Roots.empty()) return; + + // Root nodes only dominate themselves. + for (unsigned i = 0, e = Roots.size(); i != e; ++i) + Doms[Roots[i]].insert(Roots[i]); + + Function *F = Roots.back()->getParent(); + + // 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 { - assert(Roots.size() == 1 && BB == Roots[0] && - "We got into unreachable code somehow!"); - } - - WorkingSet.insert(BB); // A block always dominates itself - DomSetType &BBSet = Doms[BB]; - if (BBSet != WorkingSet) { - //assert(WorkingSet.size() > BBSet.size() && "Must only grow sets!"); - BBSet.swap(WorkingSet); // Constant time operation! - Changed = true; // The sets changed. } - WorkingSet.clear(); // Clear out the set for next iteration + } 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]; } - } while (Changed); } - - // runOnFunction - This method calculates the forward dominator sets for the // specified function. // @@ -104,21 +303,6 @@ bool DominatorSet::runOnFunction(Function &F) { return false; } -void DominatorSet::recalculate() { - assert(Roots.size() == 1 && "DominatorSet should have single root block!"); - Doms.clear(); // Reset from the last time we were run... - - // Calculate dominator sets for the reachable basic blocks... - calculateDominatorsFromBlock(Roots[0]); - - - // Loop through the function, ensuring that every basic block has at least an - // empty set of nodes. This is important for the case when there is - // unreachable blocks. - Function *F = Roots[0]->getParent(); - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) Doms[I]; -} - namespace llvm { static std::ostream &operator<<(std::ostream &o, const std::set<BasicBlock*> &BBs) { @@ -144,67 +328,6 @@ void DominatorSetBase::print(std::ostream &o) const { } //===----------------------------------------------------------------------===// -// ImmediateDominators Implementation -//===----------------------------------------------------------------------===// - -static RegisterAnalysis<ImmediateDominators> -C("idom", "Immediate Dominators Construction", true); - -// calcIDoms - Calculate the immediate dominator mapping, given a set of -// dominators for every basic block. -void ImmediateDominatorsBase::calcIDoms(const DominatorSetBase &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) { - 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 ImmediateDominatorsBase::print(std::ostream &o) const { - for (const_iterator I = begin(), E = end(); I != E; ++I) { - o << " Immediate Dominator For Basic Block:"; - if (I->first) - WriteAsOperand(o, I->first, false); - else - o << " <<exit node>>"; - o << " is:"; - if (I->second) - WriteAsOperand(o, I->second, false); - else - o << " <<exit node>>"; - o << "\n"; - } - o << "\n"; -} - - -//===----------------------------------------------------------------------===// // DominatorTree Implementation //===----------------------------------------------------------------------===// @@ -236,56 +359,40 @@ void DominatorTreeBase::Node::setIDom(Node *NewIDom) { } } +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<ImmediateDominators>()[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 DominatorSet &DS) { +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... - // Iterate over all nodes in depth first order... - for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root); + // Loop over all of the reachable blocks in the function... + for (ImmediateDominators::const_iterator I = ID.begin(), E = ID.end(); I != E; ++I) { - 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 - // function. - // - 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; - } + Node *&BBNode = Nodes[I->first]; + if (!BBNode) { // Haven't calculated this node yet? + // Get or calculate the node for the immediate dominator + Node *IDomNode = getNodeForBlock(I->second); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + BBNode = IDomNode->addChild(new Node(I->first, IDomNode)); } } } - static std::ostream &operator<<(std::ostream &o, const DominatorTreeBase::Node *Node) { if (Node->getBlock()) |