[ValueTracking] More accurate unsigned sub overflow detection
Second 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: 355109
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index f6e3886..8b3d16a 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -4165,18 +4165,16 @@
const Instruction *CxtI,
const DominatorTree *DT) {
KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
- if (LHSKnown.isNonNegative() || LHSKnown.isNegative()) {
- KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
+ KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
- // If the LHS is negative and the RHS is non-negative, no unsigned wrap.
- if (LHSKnown.isNegative() && RHSKnown.isNonNegative())
- return OverflowResult::NeverOverflows;
-
- // If the LHS is non-negative and the RHS negative, we always wrap.
- if (LHSKnown.isNonNegative() && RHSKnown.isNegative())
- return OverflowResult::AlwaysOverflows;
- }
-
+ // 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 MinRHS = RHSKnown.One, MaxRHS = ~RHSKnown.Zero;
+ if (MinLHS.uge(MaxRHS))
+ return OverflowResult::NeverOverflows;
+ if (MaxLHS.ult(MinRHS))
+ return OverflowResult::AlwaysOverflows;
return OverflowResult::MayOverflow;
}