From 5fcdfef1452b9b21a0ff3af88ac69d33704941f1 Mon Sep 17 00:00:00 2001
From: Philip Reames <listmail@philipreames.com>
Date: Tue, 26 Apr 2016 23:10:35 +0000
Subject: [PATCH] [LVI] Apply transfer rule for overdefine inputs for binary
 operators

As pointed out by John Regehr over in http://reviews.llvm.org/D19485, LVI was being incredibly stupid about applying its transfer rules.  Rather than gathering local facts from the expression itself, it was simply giving up entirely if one of the inputs was overdefined.  This greatly impacts the precision of the overall analysis and makes it far more fragile as well.

This patch builds on 267609 which did the same thing for unary casts.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@267620 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LazyValueInfo.cpp                     | 27 +++++++++++++---------
 .../Transforms/CorrelatedValuePropagation/basic.ll | 23 ++++++++++++++++++
 2 files changed, 39 insertions(+), 11 deletions(-)

diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 6bc639cf8b2..3b0ffb8d400 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -1063,22 +1063,27 @@ bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV,
 bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
                                                  Instruction *BBI,
                                                  BasicBlock *BB) {
+
+  assert(BBI->getOperand(0)->getType()->isSized() &&
+         "all operands to binary operators are sized");
   
-  // Figure out the range of the LHS.  If that fails, bail.
-  if (!hasBlockValue(BBI->getOperand(0), BB)) {
+  // Figure out the range of the LHS.  If that fails, use a conservative range,
+  // but apply the transfer rule anyways.  This lets us pick up facts from
+  // expressions like "and i32 (call i32 @foo()), 32"
+  if (!hasBlockValue(BBI->getOperand(0), BB))
     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
+      // More work to do before applying this transfer rule.
       return false;
-    BBLV.markOverdefined();
-    return true;
-  }
 
-  LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
-  intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
-  if (!LHSVal.isConstantRange()) {
-    BBLV.markOverdefined();
-    return true;
+  const unsigned OperandBitWidth =
+    DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
+  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
+  if (hasBlockValue(BBI->getOperand(0), BB)) {
+    LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
+    intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
+    if (LHSVal.isConstantRange())
+      LHSRange = LHSVal.getConstantRange();
   }
-  ConstantRange LHSRange = LHSVal.getConstantRange();
 
   ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
   ConstantRange RHSRange = ConstantRange(RHS->getValue());
diff --git a/test/Transforms/CorrelatedValuePropagation/basic.ll b/test/Transforms/CorrelatedValuePropagation/basic.ll
index 9f41807cc55..d0a17306c6b 100644
--- a/test/Transforms/CorrelatedValuePropagation/basic.ll
+++ b/test/Transforms/CorrelatedValuePropagation/basic.ll
@@ -440,3 +440,26 @@ entry:
 exit:
   ret i1 %cmp
 }
+
+
+define i1 @and_unknown(i32 %a) {
+; CHECK-LABEL: @and_unknown
+; CHECK: ret i1 true
+entry:
+  %and = and i32 %a, 128
+  %cmp = icmp sle i32 %and, 128
+  br label %exit
+exit:
+  ret i1 %cmp
+}
+
+define i1 @lshr_unknown(i32 %a) {
+; CHECK-LABEL: @lshr_unknown
+; CHECK: ret i1 true
+entry:
+  %and = lshr i32 %a, 30
+  %cmp = icmp sle i32 %and, 128
+  br label %exit
+exit:
+  ret i1 %cmp
+}
-- 
2.11.0