[ConstantRange] Add overflow check helpers

Add functions to ConstantRange that determine whether the
unsigned/signed addition/subtraction of two ConstantRanges
may/always/never overflows. This will allow checking overflow
conditions based on known constant ranges in addition to known bits.

I'm implementing these methods on ConstantRange to allow them to be
unit tested independently of any ValueTracking machinery. The tests
include exhaustive testing on 4-bit ranges, to make sure the result
is both conservatively correct and maximally precise.

The OverflowResult enum is redeclared on ConstantRange, because
I wanted to avoid a dependency in either direction between
ValueTracking.h and ConstantRange.h.

Differential Revision: https://reviews.llvm.org/D59193

llvm-svn: 356276

1 files changed, 92 insertions, 0 deletions

diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index bab83fcddf7..23737bb4650 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1066,6 +1066,98 @@ ConstantRange ConstantRange::inverse() const {
   return ConstantRange(Upper, Lower);
 }
 
+ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
+  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
+
+  // a u+ b overflows iff a u> ~b.
+  if (Min.ugt(~OtherMin))
+    return OverflowResult::AlwaysOverflows;
+  if (Max.ugt(~OtherMax))
+    return OverflowResult::MayOverflow;
+  return OverflowResult::NeverOverflows;
+}
+
+ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getSignedMin(), Max = getSignedMax();
+  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
+
+  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
+  APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
+
+  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
+  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
+  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
+      Min.sgt(SignedMax - OtherMin))
+    return OverflowResult::AlwaysOverflows;
+  if (Max.isNegative() && OtherMax.isNegative() &&
+      Max.slt(SignedMin - OtherMax))
+    return OverflowResult::AlwaysOverflows;
+
+  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
+      Max.sgt(SignedMax - OtherMax))
+    return OverflowResult::MayOverflow;
+  if (Min.isNegative() && OtherMin.isNegative() &&
+      Min.slt(SignedMin - OtherMin))
+    return OverflowResult::MayOverflow;
+
+  return OverflowResult::NeverOverflows;
+}
+
+ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
+  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
+
+  // a u- b overflows iff a u< b.
+  if (Max.ult(OtherMin))
+    return OverflowResult::AlwaysOverflows;
+  if (Min.ult(OtherMax))
+    return OverflowResult::MayOverflow;
+  return OverflowResult::NeverOverflows;
+}
+
+ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getSignedMin(), Max = getSignedMax();
+  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
+
+  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
+  APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
+
+  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
+  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
+  if (Min.isNonNegative() && OtherMax.isNegative() &&
+      Min.sgt(SignedMax + OtherMax))
+    return OverflowResult::AlwaysOverflows;
+  if (Max.isNegative() && OtherMin.isNonNegative() &&
+      Max.slt(SignedMin + OtherMin))
+    return OverflowResult::AlwaysOverflows;
+
+  if (Max.isNonNegative() && OtherMin.isNegative() &&
+      Max.sgt(SignedMax + OtherMin))
+    return OverflowResult::MayOverflow;
+  if (Min.isNegative() && OtherMax.isNonNegative() &&
+      Min.slt(SignedMin + OtherMax))
+    return OverflowResult::MayOverflow;
+
+  return OverflowResult::NeverOverflows;
+}
+
 void ConstantRange::print(raw_ostream &OS) const {
   if (isFullSet())
     OS << "full-set";