[ValueTracking] Use ConstantRange overflow check for signed add (NFC)

[nikic]

Summary

This is the same change as rL356290, but for signed add. It replaces the existing ripple logic with the overflow logic in ConstantRange, where the range is produced from KnownBits in a way that avoids wrapping the signed domain.

This is still intended as NFC, but it's somewhat less obvious here, so I'm putting up a review. It should be noted that this does make computeOverflowForSignedAdd more powerful, but only in that it can now also determine AlwaysOverflows conditions. However, none of the consumers of this method make use of this yet, so it does not impact optimization (I'll submit a followup to use AlwaysOverflows for with.overflow).

[lebedev.ri]

This is still intended as NFC

https://reviews.llvm.org/rL356290

This is NFC: <...> This is not the case for the
signed equivalents, so I'm only changing unsigned here.

So is it NFC (not counting the AlwaysOverflows) or not?

llvm/lib/Analysis/ValueTracking.cpp

4082 ↗

(On Diff #190952)

Please commit this rename directly.

4099 ↗

(On Diff #190952)

return unsignedConstantRangeFromKnownBits(Known); ?

[nikic]

So is it NFC (not counting the AlwaysOverflows) or not?

It is. The signed sub case wouldn't be though, as it only implements a basic sign check. At the time I wrote that I also thought that the ripple logic for signed add was more powerful than the constant range logic, but that was because I was thinking in unsigned ranges.

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

4104–4105 ↗

(On Diff #190952)

This seems like the only non-obvious place here.
There are tests that will fail if it is written any other way?

[lebedev.ri]

Actually, one more thought: why [un]signedConstantRangeFromKnownBits() are here, in ValueTracking?
Can they go into KnownBits class e.g. (as{Uns,S}ignedConstantRange())?

[nikic]

Switch to ConstantRange::fromKnownBits().

[lebedev.ri]

Almost there ...

llvm/lib/Analysis/ValueTracking.cpp

4151 ↗

(On Diff #191041)

This is still reachable, computeKnownBits(Add, ... is still more powerful than signedAddMayOverflow()?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4151 ↗

(On Diff #191041)

computeKnownBitsFromOperator() itself is not more powerful than signedAddMayOverflow (or the existing ripple logic). However, computeKnownBits() also computes known bits from assumes on the add, which is what this call is really for. I've created D59473 to both make that more explicit and avoid a redundant known bits calculation.

[lebedev.ri]

Looks good as a NFC to me.

llvm/lib/Analysis/ValueTracking.cpp

4132 ↗

(On Diff #191041)

I'm guessing OverflowResult won't grow, so there is no danger of accidentally doing the wrong thing here.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4132 ↗

(On Diff #191041)

I do want to grow it a bit... I'd like to split up the AlwaysOverflows case into AlwaysOverflowsLow and AlwaysOverflowsHigh, so that it can be used in saturating math optimization. But that shouldn't have any impact on this check :)

llvm/trunk/lib/Analysis/ValueTracking.cpp

KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
                                         nullptr, UseInstrInfo);
   ConstantRange LHSRange =
       ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false);
   ConstantRange RHSRange =
       ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false);
   return mapOverflowResult(LHSRange.unsignedAddMayOverflow(RHSRange));
 }
 
-/// Return true if we can prove that adding the two values of the
-/// knownbits will not overflow.
-/// Otherwise return false.
-static bool checkRippleForSignedAdd(const KnownBits &LHSKnown,
-                                    const KnownBits &RHSKnown) {
-  // Addition of two 2's complement numbers having opposite signs will never
-  // overflow.
-  if ((LHSKnown.isNegative() && RHSKnown.isNonNegative()) ||
-      (LHSKnown.isNonNegative() && RHSKnown.isNegative()))
-    return true;
-
-  // If either of the values is known to be non-negative, adding them can only
-  // overflow if the second is also non-negative, so we can assume that.
-  // Two non-negative numbers will only overflow if there is a carry to the
-  // sign bit, so we can check if even when the values are as big as possible
-  // there is no overflow to the sign bit.
-  if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative()) {
-    APInt MaxLHS = ~LHSKnown.Zero;
-    MaxLHS.clearSignBit();
-    APInt MaxRHS = ~RHSKnown.Zero;
-    MaxRHS.clearSignBit();
-    APInt Result = std::move(MaxLHS) + std::move(MaxRHS);
-    return Result.isSignBitClear();
-  }
-
-  // If either of the values is known to be negative, adding them can only
-  // overflow if the second is also negative, so we can assume that.
-  // Two negative number will only overflow if there is no carry to the sign
-  // bit, so we can check if even when the values are as small as possible
-  // there is overflow to the sign bit.
-  if (LHSKnown.isNegative() || RHSKnown.isNegative()) {
-    APInt MinLHS = LHSKnown.One;
-    MinLHS.clearSignBit();
-    APInt MinRHS = RHSKnown.One;
-    MinRHS.clearSignBit();
-    APInt Result = std::move(MinLHS) + std::move(MinRHS);
-    return Result.isSignBitSet();
-  }
-
-  // If we reached here it means that we know nothing about the sign bits.
-  // In this case we can't know if there will be an overflow, since by
-  // changing the sign bits any two values can be made to overflow.
-  return false;
-}
-
 static OverflowResult computeOverflowForSignedAdd(const Value *LHS,
                                                   const Value *RHS,
                                                   const AddOperator *Add,
                                                   const DataLayout &DL,
                                                   AssumptionCache *AC,
                                                   const Instruction *CxtI,
                                                   const DominatorTree *DT) {
   if (Add && Add->hasNoSignedWrap()) {
static OverflowResult computeOverflowForSignedAdd(const Value *LHS,
   // Since the carry into the most significant position is always equal to
   // the carry out of the addition, there is no signed overflow.
   if (ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) > 1 &&
       ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT) > 1)
     return OverflowResult::NeverOverflows;
 
   KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
   KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
-
-  if (checkRippleForSignedAdd(LHSKnown, RHSKnown))
-    return OverflowResult::NeverOverflows;
+  ConstantRange LHSRange =
+      ConstantRange::fromKnownBits(LHSKnown, /*signed*/ true);
+  ConstantRange RHSRange =
+      ConstantRange::fromKnownBits(RHSKnown, /*signed*/ true);
+  OverflowResult OR =
+      mapOverflowResult(LHSRange.signedAddMayOverflow(RHSRange));
+  if (OR != OverflowResult::MayOverflow)
+    return OR;
 
   // The remaining code needs Add to be available. Early returns if not so.
   if (!Add)
     return OverflowResult::MayOverflow;
 
   // If the sign of Add is the same as at least one of the operands, this add
   // CANNOT overflow. This is particularly useful when the sum is
   // @llvm.assume'ed non-negative rather than proved so from analyzing its