Author: lattner
Date: Wed Aug 8 00:51:24 2007
New Revision: 40920
URL: http://llvm.org/viewvc/llvm-project?rev=40920&view=rev
Log:
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.
Modified:
llvm/trunk/include/llvm/Analysis/Dominators.h
llvm/trunk/lib/Analysis/PostDominators.cpp
llvm/trunk/lib/VMCore/Dominators.cpp
Modified: llvm/trunk/include/llvm/Analysis/Dominators.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/Dominators.h?rev=40920&r1=40919&r2=40920&view=diff
==============================================================================
--- llvm/trunk/include/llvm/Analysis/Dominators.h (original)
+++ llvm/trunk/include/llvm/Analysis/Dominators.h Wed Aug 8 00:51:24 2007
@@ -97,17 +97,12 @@
return this->DFSNumIn >= other->DFSNumIn &&
this->DFSNumOut <= other->DFSNumOut;
}
-
- /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
- /// in dfs order.
- void assignDFSNumber(int num);
};
//===----------------------------------------------------------------------===//
/// DominatorTree - Calculate the immediate dominator tree for a function.
///
class DominatorTreeBase : public DominatorBase {
-
protected:
void reset();
typedef DenseMap<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
@@ -135,9 +130,7 @@
// Info - Collection of information used during the computation of idoms.
DenseMap<BasicBlock*, InfoRec> Info;
- void updateDFSNumbers();
-
- public:
+public:
DominatorTreeBase(intptr_t ID, bool isPostDom)
: DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
~DominatorTreeBase() { reset(); }
@@ -275,6 +268,11 @@
if (OS) print(*OS, M);
}
virtual void dump();
+
+protected:
+ /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
+ /// dominator tree in dfs order.
+ void updateDFSNumbers();
};
//===-------------------------------------
Modified: llvm/trunk/lib/Analysis/PostDominators.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/PostDominators.cpp?rev=40920&r1=40919&r2=40920&view=diff
==============================================================================
--- llvm/trunk/lib/Analysis/PostDominators.cpp (original)
+++ llvm/trunk/lib/Analysis/PostDominators.cpp Wed Aug 8 00:51:24 2007
@@ -193,15 +193,9 @@
Info.clear();
std::vector<BasicBlock*>().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<BasicBlock*> I = idf_begin(Roots[i]),
- E = idf_end(Roots[i]); I != E; ++I) {
- if (!getNodeForBlock(*I)->getIDom())
- getNodeForBlock(*I)->assignDFSNumber(dfsnum);
- }
- DFSInfoValid = true;
+ // Start out with the DFS numbers being invalid. Let them be computed if
+ // demanded.
+ DFSInfoValid = false;
}
Modified: llvm/trunk/lib/VMCore/Dominators.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/VMCore/Dominators.cpp?rev=40920&r1=40919&r2=40920&view=diff
==============================================================================
--- llvm/trunk/lib/VMCore/Dominators.cpp (original)
+++ llvm/trunk/lib/VMCore/Dominators.cpp Wed Aug 8 00:51:24 2007
@@ -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 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 @@
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) {
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
