[LVI] Exploit nsw/nuw when computing constant ranges

[reames]

Summary

As the title says. Modelled after similar code in SCEV.

This is useful when analysing induction variables in loops which have been canonicalized by other passes. I wrote the tests as non-loops specifically to avoid the generality introduced in http://reviews.llvm.org/D17174. While that can handle many induction variables without *needing* to exploit nsw, there's no reason not to use it if we've already proven it.

[sanjoy]

lgtm

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
   }
 
   ConstantRange LHSRange = LHSVal.getConstantRange();
   ConstantRange RHSRange(1);
   IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
   if (isa<BinaryOperator>(BBI)) {
     if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
       RHSRange = ConstantRange(RHS->getValue());
+
+      // Try to use information about wrap flags to refine the range LHS can
+      // legally have.  This is a slightly weird way to implement forward
+      // propagation over overflowing instructions, but it seems to be the only
+      // clean one we have.  NOTE: Because we may have speculated the
+      // instruction, we can't constrain other uses of LHS even if they would
+      // seem to be equivelent control dependent with this op.
+      if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BBI)) {
+        unsigned WrapKind = 0;
+        if (OBO->hasNoSignedWrap())
+          WrapKind |= OverflowingBinaryOperator::NoSignedWrap;
+        if (OBO->hasNoUnsignedWrap())
+          WrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
+
+        if (WrapKind) {
+          auto OpCode = static_cast<Instruction::BinaryOps>(BBI->getOpcode());
+          auto NoWrapCR =
+            ConstantRange::makeNoWrapRegion(OpCode, RHS->getValue(), WrapKind);
+          LHSRange = LHSRange.intersectWith(NoWrapCR);
+        }
+      }
     } else {
       BBLV.markOverdefined();
       return true;
     }
   }
 
   // NOTE: We're currently limited by the set of operations that ConstantRange
   // can evaluate symbolically.  Enhancing that set will allows us to analyze

llvm/trunk/test/Transforms/CorrelatedValuePropagation/basic.ll

 ; CHECK: br label %next
 
 out:
   ret void
 
 next:
   ret void
 }
+
+; Can we use nsw in LVI to prove lack of overflow?
+define i1 @add_nsw(i32 %s) {
+; CHECK-LABEL: @add_nsw(
+entry:
+  %cmp = icmp sgt i32 %s, 0
+  br i1 %cmp, label %positive, label %out
+
+positive:
+  %add = add nsw i32 %s, 1
+  %res = icmp sgt i32 %add, 0
+  br label %next
+next:
+; CHECK: next:
+; CHECK: ret i1 true
+  ret i1 %res
+out:
+  ret i1 false
+}
+
+define i1 @add_nsw2(i32 %s) {
+; CHECK-LABEL: @add_nsw2(
+entry:
+  %cmp = icmp sge i32 %s, 0
+  br i1 %cmp, label %positive, label %out
+
+positive:
+  %add = add nsw i32 %s, 1
+  %res = icmp ne i32 %add, 0
+  br label %next
+next:
+; CHECK: next:
+; CHECK: ret i1 true
+  ret i1 %res
+out:
+  ret i1 false
+}
+
+define i1 @add_nuw(i32 %s) {
+; CHECK-LABEL: @add_nuw(
+entry:
+  %cmp = icmp ult i32 %s, 400
+  br i1 %cmp, label %positive, label %out
+
+positive:
+  %add = add nsw i32 %s, 1
+  %res = icmp ne i32 %add, -100
+  br label %next
+next:
+; CHECK: next:
+; CHECK: ret i1 true
+  ret i1 %res
+out:
+  ret i1 false
+}