Change ET-Forest to automatically recalculate its DFSnum's if too many slow

queries are made.

Patch by Daniel Berlin!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@25323 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 41 insertions, 14 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 947b22342e..4b2f61129d 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -397,16 +397,17 @@ public:
 ///
 struct ETForestBase : public DominatorBase {
   ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 
-                                 DFSInfoValid(false) {}
+                                 DFSInfoValid(false), SlowQueries(0) {}
   
   virtual void releaseMemory() { reset(); }
 
   typedef std::map<BasicBlock*, ETNode*> ETMapType;
 
-
+  void updateDFSNumbers();
+    
   /// dominates - Return true if A dominates B.
   ///
-  inline bool dominates(BasicBlock *A, BasicBlock *B) const {
+  inline bool dominates(BasicBlock *A, BasicBlock *B) {
     if (A == B)
       return true;
     
@@ -415,13 +416,21 @@ struct ETForestBase : public DominatorBase {
     
     if (DFSInfoValid)
       return NodeB->DominatedBy(NodeA);
-    else
+    else {
+      // If we end up with too many slow queries, just update the
+      // DFS numbers on the theory that we are going to keep querying.
+      SlowQueries++;
+      if (SlowQueries > 32) {
+        updateDFSNumbers();
+        return NodeB->DominatedBy(NodeA);
+      }
       return NodeB->DominatedBySlow(NodeA);
+    }
   }
 
   /// properlyDominates - Return true if A dominates B and A != B.
   ///
-  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
+  bool properlyDominates(BasicBlock *A, BasicBlock *B) {
     return dominates(A, B) && A != B;
   }
 
@@ -474,6 +483,7 @@ protected:
   void reset();
   ETMapType Nodes;
   bool DFSInfoValid;
+  unsigned int SlowQueries;
 
 };
 
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index dd278e76c8..425c33f418 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -297,8 +297,8 @@ public:
 
   static void stub();  // Noop
 private:
-  void Calculate(const ETForest &EF);
-  Loop *ConsiderForLoop(BasicBlock *BB, const ETForest &EF);
+  void Calculate(ETForest &EF);
+  Loop *ConsiderForLoop(BasicBlock *BB, ETForest &EF);
   void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent);
   void InsertLoopInto(Loop *L, Loop *Parent);
 };
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index cf6e20a909..20b470f3eb 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -104,7 +104,7 @@ void LoopInfo::releaseMemory() {
 }
 
 
-void LoopInfo::Calculate(const ETForest &EF) {
+void LoopInfo::Calculate(ETForest &EF) {
   BasicBlock *RootNode = EF.getRoot();
 
   for (df_iterator<BasicBlock*> NI = df_begin(RootNode),
@@ -135,7 +135,7 @@ static bool isNotAlreadyContainedIn(Loop *SubLoop, Loop *ParentLoop) {
   return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
 }
 
-Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, const ETForest &EF) {
+Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, ETForest &EF) {
   if (BBMap.find(BB) != BBMap.end()) return 0;   // Haven't processed this node?
 
   std::vector<BasicBlock *> TodoStack;
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 6021b33941..951da55589 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -812,6 +812,21 @@ void ETForestBase::reset() {
   Nodes.clear();
 }
 
+void ETForestBase::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) {
+      BasicBlock *BB = *I;
+      if (!getNode(BB)->hasFather())
+        getNode(BB)->assignDFSNumber(dfsnum);    
+  }
+  SlowQueries = 0;
+  DFSInfoValid = true;
+}
+
 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
   ETNode *&BBNode = Nodes[BB];
   if (BBNode) return BBNode;
@@ -855,12 +870,14 @@ void ETForest::calculate(const ImmediateDominators &ID) {
       }
     }
 
-  int dfsnum = 0;
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 
-   if (!getNodeForBlock(I)->hasFather())
-     getNodeForBlock(I)->assignDFSNumber(dfsnum);
+  // Make sure we've got nodes around for every block
+  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
+    ETNode *&BBNode = Nodes[I];
+    if (!BBNode)
+      BBNode = new ETNode(I);
   }
-  DFSInfoValid = true;
+
+  updateDFSNumbers ();
 }
 
 //===----------------------------------------------------------------------===//