make LVI::getEdgeValue() always intersect the constraints of the edge with the range of the block. Previously it was only performing the intersection for a few cases, thus losing precision

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

2 files changed, 97 insertions, 36 deletions

diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 7539d93..83786dd 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -172,7 +172,7 @@ public:
       if (NewR.isEmptySet())
         return markOverdefined();
       
-      bool changed = Range == NewR;
+      bool changed = Range != NewR;
       Range = NewR;
       return changed;
     }
@@ -457,8 +457,10 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
 void LazyValueInfoCache::solve() {
   while (!BlockValueStack.empty()) {
     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
-    if (solveBlockValue(e.second, e.first))
+    if (solveBlockValue(e.second, e.first)) {
+      assert(BlockValueStack.top() == e);
       BlockValueStack.pop();
+    }
   }
 }
 
@@ -766,15 +768,10 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
   return true;
 }
 
-/// getEdgeValue - This method attempts to infer more complex 
-bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
-                                      BasicBlock *BBTo, LVILatticeVal &Result) {
-  // If already a constant, there is nothing to compute.
-  if (Constant *VC = dyn_cast<Constant>(Val)) {
-    Result = LVILatticeVal::get(VC);
-    return true;
-  }
-  
+/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
+/// Val is not constrained on the edge.
+static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
+                              BasicBlock *BBTo, LVILatticeVal &Result) {
   // TODO: Handle more complex conditionals.  If (v == 0 || v2 < 1) is false, we
   // know that v != 0.
   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
@@ -827,25 +824,8 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 
           // If we're interested in the false dest, invert the condition.
           if (!isTrueDest) TrueValues = TrueValues.inverse();
-          
-          // Figure out the possible values of the query BEFORE this branch.  
-          if (!hasBlockValue(Val, BBFrom)) {
-            BlockValueStack.push(std::make_pair(BBFrom, Val));
-            return false;
-          }
-          
-          LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
-          if (!InBlock.isConstantRange()) {
-            Result = LVILatticeVal::getRange(TrueValues);
-            return true;
-          }
-
-          // Find all potential values that satisfy both the input and output
-          // conditions.
-          ConstantRange PossibleValues =
-            TrueValues.intersectWith(InBlock.getConstantRange());
-
-          Result = LVILatticeVal::getRange(PossibleValues);
+
+          Result = LVILatticeVal::getRange(TrueValues);
           return true;
         }
       }
@@ -874,14 +854,51 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
       return true;
     }
   }
-  
-  // Otherwise see if the value is known in the block.
-  if (hasBlockValue(Val, BBFrom)) {
-    Result = getBlockValue(Val, BBFrom);
+  return false;
+}
+
+/// \brief Compute the value of Val on the edge BBFrom -> BBTo, or the value at
+/// the basic block if the edge does not constraint Val.
+bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
+                                      BasicBlock *BBTo, LVILatticeVal &Result) {
+  // If already a constant, there is nothing to compute.
+  if (Constant *VC = dyn_cast<Constant>(Val)) {
+    Result = LVILatticeVal::get(VC);
     return true;
   }
-  BlockValueStack.push(std::make_pair(BBFrom, Val));
-  return false;
+
+  if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
+    if (!Result.isConstantRange() ||
+      Result.getConstantRange().getSingleElement())
+      return true;
+
+    // FIXME: this check should be moved to the beginning of the function when
+    // LVI better supports recursive values. Even for the single value case, we
+    // can intersect to detect dead code (an empty range).
+    if (!hasBlockValue(Val, BBFrom)) {
+      BlockValueStack.push(std::make_pair(BBFrom, Val));
+      return false;
+    }
+
+    // Try to intersect ranges of the BB and the constraint on the edge.
+    LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
+    if (!InBlock.isConstantRange())
+      return true;
+
+    ConstantRange Range =
+      Result.getConstantRange().intersectWith(InBlock.getConstantRange());
+    Result = LVILatticeVal::getRange(Range);
+    return true;
+  }
+
+  if (!hasBlockValue(Val, BBFrom)) {
+    BlockValueStack.push(std::make_pair(BBFrom, Val));
+    return false;
+  }
+
+  // if we couldn't compute the value on the edge, use the value from the BB
+  Result = getBlockValue(Val, BBFrom);
+  return true;
 }
 
 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
diff --git a/test/Transforms/CorrelatedValuePropagation/range.ll b/test/Transforms/CorrelatedValuePropagation/range.ll
index 4ac478b..a9e27d6 100644
--- a/test/Transforms/CorrelatedValuePropagation/range.ll
+++ b/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -98,3 +98,47 @@ return:
   %retval.0 = phi i32 [ 42, %sw.default ], [ 4, %if.then ], [ 9, %if.end ]
   ret i32 %retval.0
 }
+
+; CHECK: @test5
+define i1 @test5(i32 %c) nounwind {
+  %cmp = icmp slt i32 %c, 5
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  %cmp1 = icmp eq i32 %c, 4
+  br i1 %cmp1, label %if.end, label %if.end8
+
+if.end:
+  ret i1 true
+
+if.end8:
+  %cmp2 = icmp eq i32 %c, 3
+  %cmp3 = icmp eq i32 %c, 4
+  %cmp4 = icmp eq i32 %c, 6
+; CHECK: %or = or i1 false, false
+  %or = or i1 %cmp3, %cmp4
+; CHECK: ret i1 %cmp2
+  ret i1 %cmp2
+}
+
+; CHECK: @test6
+define i1 @test6(i32 %c) nounwind {
+  %cmp = icmp ule i32 %c, 7
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+; CHECK: icmp eq i32 %c, 6
+; CHECK: br i1
+  switch i32 %c, label %if.end [
+    i32 6, label %sw.bb
+    i32 8, label %sw.bb
+  ]
+
+if.end:
+  ret i1 true
+
+sw.bb:
+  %cmp2 = icmp eq i32 %c, 6
+; CHECK: ret i1 true
+  ret i1 %cmp2
+}