[ValueTracking] More accurate unsigned add overflow detection
Part of D58593.
Compute precise overflow conditions based on all known bits, rather
than just the sign bits. Unsigned a + b overflows iff a > ~b, and we
can determine whether this always/never happens based on the minimal
and maximal values achievable for a and ~b subject to the known bits
constraint.
llvm-svn: 355072
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index deb2fb9..80a08e2 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -4044,21 +4044,17 @@
bool UseInstrInfo) {
KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT,
nullptr, UseInstrInfo);
- if (LHSKnown.isNonNegative() || LHSKnown.isNegative()) {
- KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
- nullptr, UseInstrInfo);
+ KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
+ nullptr, UseInstrInfo);
- if (LHSKnown.isNegative() && RHSKnown.isNegative()) {
- // The sign bit is set in both cases: this MUST overflow.
- return OverflowResult::AlwaysOverflows;
- }
-
- if (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()) {
- // The sign bit is clear in both cases: this CANNOT overflow.
- return OverflowResult::NeverOverflows;
- }
- }
-
+ // a + b overflows iff a > ~b. Determine whether this is never/always true
+ // based on the min/max values achievable under the known bits constraint.
+ APInt MinLHS = LHSKnown.One, MaxLHS = ~LHSKnown.Zero;
+ APInt MinInvRHS = RHSKnown.Zero, MaxInvRHS = ~RHSKnown.One;
+ if (MaxLHS.ule(MinInvRHS))
+ return OverflowResult::NeverOverflows;
+ if (MinLHS.ugt(MaxInvRHS))
+ return OverflowResult::AlwaysOverflows;
return OverflowResult::MayOverflow;
}