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
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 60e9e6b..36c18f0 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 @@
}
// 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)