From 63aa160b27935433208c34080e0458ce287030bb Mon Sep 17 00:00:00 2001
From: Tanya Lattner <tonic@nondot.org>
Date: Wed, 6 Feb 2008 00:54:55 +0000
Subject: [PATCH] Throttle the non-local dependence analysis for basic blocks
 with more than 50 predecessors. Added command line option to play with this
 threshold.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46790 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/MemoryDependenceAnalysis.cpp | 27 +++++++++++++++++------
 1 file changed, 20 insertions(+), 7 deletions(-)

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 60e9e6b9e4b..36c18f0c0b5 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -20,6 +20,7 @@
 #include "llvm/Function.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/ADT/Statistic.h"
 
@@ -27,6 +28,15 @@
 
 using namespace llvm;
 
+namespace {
+  // Control the calculation of non-local dependencies by only examining the
+  // predecessors if the basic block has less than X amount (50 by default).
+  cl::opt<int> 
+  PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
+            cl::desc("Control the calculation of non-local"
+                     "dependencies (default = 50)"));           
+}
+
 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
 
@@ -211,15 +221,18 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
     }
     
     // If we didn't find anything, recurse on the precessors of this block
+    // Only do this for blocks with a small number of predecessors.
     bool predOnStack = false;
     bool inserted = false;
-    for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
-         PI != PE; ++PI)
-      if (!visited.count(*PI)) {
-        stack.push_back(*PI);
-        inserted = true;
-      } else
-        predOnStack = true;
+    if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) { 
+      for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+           PI != PE; ++PI)
+        if (!visited.count(*PI)) {
+          stack.push_back(*PI);
+          inserted = true;
+        } else
+          predOnStack = true;
+    }
     
     // If we inserted a new predecessor, then we'll come back to this block
     if (inserted)
-- 
2.34.1