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

2 files changed, 17 insertions, 7 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 947b223..4b2f611 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 dd278e7..425c33f 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);
 };