[LVI] Exploit trivial range information from unknown RHS of icmp

[reames]

Summary

The primary motivation is in proving overflow facts. Particularly, overflow facts for loop induction variables. SCEV gets many of these cases today, but there's no reason LVI shouldn't get them to and having LVI able to catch the simple cases makes our pass order less fragile.

Note that this patch is only the analysis changes. A separate change will build on top of this to actually make "add" instructions as nsw/nuw.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1162

I wouldn't put all this logic here. Instead, it is easier to do:

ConstantRange RHSRange = FullRange;
ConstantRange LHSRange = makeAllowedRange(ICI->getPredicate(), RHSRange);
if (LHSRange is not full set)
  Result = LVILatticeVal::getRange(LHSRange);

Later you can improve precision by making RHSRange more precise.

[reames]

lib/Analysis/LazyValueInfo.cpp

1162

I really like this idea. I'm going to rewrite this patch when I get a chance and probably simplify a lot of other code nearby using the same trick.

[reames]

No longer needed, and extremely stale.

Tests landed as 340660. The code just above my diff was generalized as Sanjoy suggested in his review, so none of the dedicated code was needed.

lib/Analysis/LazyValueInfo.cpp

if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
       // If we're interested in the false dest, invert the condition.
       if (!isTrueDest) TrueValues = TrueValues.inverse();
 
       Result = LVILatticeVal::getRange(std::move(TrueValues));
       return true;
     }
   }
 
+  if (isTrueDest && ICI->getOperand(0) == Val) {
+    // TODO: generalize this for when Val is operand(1)
+    unsigned BitWidth = Val->getType()->getPrimitiveSizeInBits();
+
+    // A <s B for any A and B implies A <s INT_MAX on success path
+    // A <u B for any A and B implies A <u UINT_MAX on success path
+    if ((ICI->getPredicate() == ICmpInst::ICMP_SLT ||
+         ICI->getPredicate() == ICmpInst::ICMP_ULT)) {
+      ConstantRange Max = ICI->isSigned() ?
+        ConstantRange(APInt::getSignedMaxValue(BitWidth)) :
+        ConstantRange(APInt::getMaxValue(BitWidth));
+      ConstantRange TrueValues =
+        ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), Max);
+      Result = LVILatticeVal::getRange(std::move(TrueValues));
+      return true;
+    }
+    // A >s B for any A and B implies A >s INT_MIN on success path
+    // A >u B for any A and B implies A >u UINT_MIN on success path
+    if ((ICI->getPredicate() == ICmpInst::ICMP_SGT ||
+         ICI->getPredicate() == ICmpInst::ICMP_UGT)) {
+      ConstantRange Min = ICI->isSigned() ?
+        ConstantRange(APInt::getSignedMinValue(BitWidth)) :
+        ConstantRange(APInt::getMinValue(BitWidth));
+      ConstantRange TrueValues =
+        ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), Min);
+      Result = LVILatticeVal::getRange(std::move(TrueValues));
+      return true;
+    }
+  }
+
   return false;
 }
 
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
                               BasicBlock *BBTo, LVILatticeVal &Result) {

test/Transforms/CorrelatedValuePropagation/overflow.ll

+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; Just showing arbitrary constants work, not really a clamp
+define i1 @slt(i8 %a, i8 %b) {
+; CHECK-LABEL: @slt(
+; CHECK: ret i1 true
+entry:
+  %cmp = icmp slt i8 %a, %b
+  call void @llvm.assume(i1 %cmp)
+  %res = icmp slt i8 %a, 127
+  ret i1 %res
+}
+
+define i1 @sgt(i8 %a, i8 %b) {
+; CHECK-LABEL: @sgt(
+; CHECK: ret i1 true
+entry:
+  %cmp = icmp sgt i8 %a, %b
+  call void @llvm.assume(i1 %cmp)
+  %res = icmp sgt i8 %a, -128
+  ret i1 %res
+}
+
+define i1 @ult(i8 %a, i8 %b) {
+; CHECK-LABEL: @ult(
+; CHECK: ret i1 true
+entry:
+  %cmp = icmp ult i8 %a, %b
+  call void @llvm.assume(i1 %cmp)
+  %res = icmp ult i8 %a, 255
+  ret i1 %res
+}
+
+define i1 @ugt(i8 %a, i8 %b) {
+; CHECK-LABEL: @ugt(
+; CHECK: ret i1 true
+entry:
+  %cmp = icmp ugt i8 %a, %b
+  call void @llvm.assume(i1 %cmp)
+  %res = icmp ugt i8 %a, 0
+  ret i1 %res
+}
+
+declare void @llvm.assume(i1)