[LVI] Check for @llvm.assume dominating the edge branch

[oota-llvm.git] / lib / Analysis / LazyValueInfo.cpp

diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 961fb0f7aef9937f0edb23534d47107c0d28e4d3..ec2c798e6c6e8cf5e83d0cab871329458a846891 100644 (file)
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -27,7 +27,6 @@
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
-#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetLibraryInfo.h"
@@ -38,20 +37,6 @@ using namespace PatternMatch;
 
 #define DEBUG_TYPE "lazy-value-info"
 
-// Experimentally derived threshold for the number of basic blocks lowered for
-// lattice value overdefined.
-static cl::opt<unsigned>
-OverdefinedBBThreshold("lvi-overdefined-BB-threshold",
-    cl::init(1500), cl::Hidden,
-    cl::desc("Threshold of the number of basic blocks lowered for lattice value"
-             "'overdefined'."));
-
-// Experimentally derived threshold for additional lowering lattice values
-// overdefined per block.
-static cl::opt<unsigned>
-OverdefinedThreshold("lvi-overdefined-threshold", cl::init(10), cl::Hidden,
-    cl::desc("Threshold of lowering lattice value 'overdefined'."));
-
 char LazyValueInfo::ID = 0;
 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
                 "Lazy Value Information Analysis", false, true)
@@ -363,9 +348,6 @@ namespace {
     const DataLayout *DL;
     /// An optional DT pointer.
     DominatorTree *DT;
-    /// A counter to record how many times Overdefined has been tried to be
-    /// lowered.
-    DenseMap<BasicBlock *, unsigned> LoweringOverdefinedTimes;
     
     friend struct LVIValueHandle;
     
@@ -498,9 +480,6 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
 }
 
 void LazyValueInfoCache::solve() {
-  // Reset the counter of lowering overdefined value.
-  LoweringOverdefinedTimes.clear();
-
   while (!BlockValueStack.empty()) {
     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
     if (solveBlockValue(e.second, e.first)) {
@@ -545,31 +524,7 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   // cache needs updating, i.e. if we have solve a new value or not.
   OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
 
-  // Once this BB is encountered, Val's value for this BB will not be Undefined
-  // any longer. When we encounter this BB again, if Val's value is Overdefined,
-  // we need to compute its value again.
-  // 
-  // For example, considering this control flow,
-  //   BB1->BB2, BB1->BB3, BB2->BB3, BB2->BB4
-  //
-  // Suppose we have "icmp slt %v, 0" in BB1, and "icmp sgt %v, 0" in BB3. At
-  // the very beginning, when analyzing edge BB2->BB3, we don't know %v's value
-  // in BB2, and the data flow algorithm tries to compute BB2's predecessors, so
-  // then we know %v has negative value on edge BB1->BB2. And then we return to
-  // check BB2 again, and at this moment BB2 has Overdefined value for %v in
-  // BB2. So we should have to follow data flow propagation algorithm to get the
-  // value on edge BB1->BB2 propagated to BB2, and finally %v on BB2 has a
-  // constant range describing a negative value.
-  //
-  // In the mean time, limit the number of additional lowering lattice value to
-  // avoid unjustified memory grows.
-
-  if (LoweringOverdefinedTimes.count(BB) == 0)
-    LoweringOverdefinedTimes.insert(std::make_pair(BB, 0));
-  if ((!BBLV.isUndefined() && !BBLV.isOverdefined()) ||
-      (BBLV.isOverdefined() &&
-       (LoweringOverdefinedTimes[BB] > OverdefinedThreshold ||
-        LoweringOverdefinedTimes.size() > OverdefinedBBThreshold))) {
+  if (!BBLV.isUndefined()) {
     DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
     
     // Since we're reusing a cached value here, we don't need to update the 
@@ -583,7 +538,6 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   // lattice value to overdefined, so that cycles will terminate and be
   // conservatively correct.
   BBLV.markOverdefined();
-  ++LoweringOverdefinedTimes[BB];
   
   Instruction *BBI = dyn_cast<Instruction>(Val);
   if (!BBI || BBI->getParent() != BB) {
@@ -1000,6 +954,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 
     // Try to intersect ranges of the BB and the constraint on the edge.
     LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
+    mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
     mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
     if (!InBlock.isConstantRange())
       return true;
@@ -1017,6 +972,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 
   // if we couldn't compute the value on the edge, use the value from the BB
   Result = getBlockValue(Val, BBFrom);
+  mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
   mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
   return true;
 }