diff options
author | Chris Lattner <sabre@nondot.org> | 2007-08-08 05:51:24 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-08-08 05:51:24 +0000 |
commit | 3e089ae0b8aa6d9daf0b8ca8f6059422c45936f0 (patch) | |
tree | 1a94bf7be024c94dc78329d4b0c549da4cee182d /lib/VMCore | |
parent | 6ca4cb37553fc8ab568d1695d2afc99cf100d777 (diff) | |
download | external_llvm-3e089ae0b8aa6d9daf0b8ca8f6059422c45936f0.zip external_llvm-3e089ae0b8aa6d9daf0b8ca8f6059422c45936f0.tar.gz external_llvm-3e089ae0b8aa6d9daf0b8ca8f6059422c45936f0.tar.bz2 |
reimplement dfs number computation to be significantly faster. This speeds up
natural loop canonicalization (which does many cfg xforms) by 4.3x, for
example. This also fixes a bug in postdom dfnumber computation.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40920 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore')
-rw-r--r-- | lib/VMCore/Dominators.cpp | 73 |
1 files changed, 33 insertions, 40 deletions
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 95ebca0..3dc8796 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -20,6 +20,7 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Instructions.h" #include "llvm/Support/Streams.h" #include <algorithm> @@ -383,15 +384,39 @@ void DominatorTree::calculate(Function &F) { } void DominatorTreeBase::updateDFSNumbers() { - int dfsnum = 0; - // Iterate over all nodes in depth first order. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (df_iterator<BasicBlock*> I = df_begin(Roots[i]), - E = df_end(Roots[i]); I != E; ++I) { - if (DomTreeNode *BBNode = getNode(*I)) { - if (!BBNode->getIDom()) - BBNode->assignDFSNumber(dfsnum); + unsigned DFSNum = 0; + + SmallVector<DomTreeNode *, 32> WorkStack; + SmallPtrSet<DomTreeNode *, 32> Visited; + + for (unsigned i = 0, e = Roots.size(); i != e; ++i) { + DomTreeNode *ThisRoot = getNode(Roots[i]); + WorkStack.push_back(ThisRoot); + Visited.insert(ThisRoot); + ThisRoot->DFSNumIn = DFSNum++; + + while (!WorkStack.empty()) { + DomTreeNode *Node = WorkStack.back(); + + bool MustVisitAChild = false; + for (DomTreeNode::iterator DI = Node->begin(), E = Node->end(); + DI != E; ++DI) { + DomTreeNode *Child = *DI; + if (!Visited.insert(Child)) + continue; + + MustVisitAChild = true; + Child->DFSNumIn = DFSNum++; + WorkStack.push_back(Child); + break; } + + if (!MustVisitAChild) { + // If we reach here means all children are visited + Node->DFSNumOut = DFSNum++; + WorkStack.pop_back(); + } + } } SlowQueries = 0; DFSInfoValid = true; @@ -489,38 +514,6 @@ BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, return NULL; } -/// assignDFSNumber - Assign In and Out numbers while walking dominator tree -/// in dfs order. -void DomTreeNode::assignDFSNumber(int num) { - std::vector<DomTreeNode *> workStack; - SmallPtrSet<DomTreeNode *, 32> Visited; - - workStack.push_back(this); - Visited.insert(this); - this->DFSNumIn = num++; - - while (!workStack.empty()) { - DomTreeNode *Node = workStack.back(); - - bool visitChild = false; - for (std::vector<DomTreeNode*>::iterator DI = Node->begin(), - E = Node->end(); DI != E && !visitChild; ++DI) { - DomTreeNode *Child = *DI; - if (!Visited.insert(Child)) - continue; - - visitChild = true; - Child->DFSNumIn = num++; - workStack.push_back(Child); - } - if (!visitChild) { - // If we reach here means all children are visited - Node->DFSNumOut = num++; - workStack.pop_back(); - } - } -} - void DomTreeNode::setIDom(DomTreeNode *NewIDom) { assert(IDom && "No immediate dominator?"); if (IDom != NewIDom) { |