From 2b9100dfbd4219727c6904e76403efda0d2d5e63 Mon Sep 17 00:00:00 2001
From: Philip Reames <listmail@philipreames.com>
Date: Fri, 12 Feb 2016 19:05:16 +0000
Subject: [PATCH] [LVI] Exploit nsw/nuw when computing constant ranges

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.

Differential Revision: http://reviews.llvm.org/D17177

llvm-svn: 260705
---
 llvm/lib/Analysis/LazyValueInfo.cpp                | 21 +++++++++
 .../Transforms/CorrelatedValuePropagation/basic.ll | 55 ++++++++++++++++++++++
 2 files changed, 76 insertions(+)

diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
index 8f12111..d21b1bd 100644
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -961,6 +961,27 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
   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;
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll
index 9d1253a..b0dacbf 100644
--- a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll
@@ -199,3 +199,58 @@ out:
 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
+}
-- 
2.7.4