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

1 files changed, 6 insertions, 8 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 7c7c56771a..a57f17bee1 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -97,17 +97,12 @@ private:
     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 @@ protected:
   // 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 @@ protected:
     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();
 };
 
 //===-------------------------------------