[ValueTracking] ConstantRange based overflow detection for unsigned add/sub

[nikic]

Summary

Based on D59193 and rL356290 this makes some improvements to the computeOverflowForUnsignedAdd/Sub functions in ValueTracking:

• Additionally call computeConstantRange() and intersect it with the KnownBits range.
• Extend computeConstantRange() to compute constant ranges for constant integers and constant integer vectors.

The main tests are based on saturating math intrinsics, though a couple nuw's also get inferred in existing tests.

[lebedev.ri]

• The KnownBits are converted into ConstantRanges and the unsigned(Add|Sub)MayOverflow method on ConstantRange is used to determine the overflow condition. This part is NFC because this effectively matches what the code already did in a more explicit way.

Can you please at least separate the NFC ^ part?

• Additionally call computeConstantRange() and intersect it with the KnownBits range.
• Extend computeConstantRange() to compute constant ranges for constant integers and constant integer vectors.

[nikic]

Rebase over rL356290, which was the NFC portion of this change.

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

5708 ↗

(On Diff #190864)

This is used in simplifyICmpWithConstant(). thus i think this can be split off too,
although i'm not sure if that will show any test changes as-is?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

5708 ↗

(On Diff #190864)

For this code to apply in simplifyICmpWithConstant() it would have to be an icmp with both operands constant, which will already be folded earlier. (This code is split off from simplifyICmpWithConstant, which is why the constant handling was missing: It's not needed for that usage.)

[lebedev.ri]

Hmm, this looks reasonable to me, @spatel ?
Are there any concerns of performance impact of using ConstantRange() here ?
Though i do think it does pull it's weight.

llvm/lib/Analysis/ValueTracking.cpp

4212 ↗

(On Diff #190864)

When committing, it might be a good idea to commit the computeOverflowForUnsignedSub() change as a follow-up, as usual..

5708 ↗

(On Diff #190864)

Oh right, thanks for explanation.

[nikic]

Are there any concerns of performance impact of using ConstantRange() here ?

Right now the computeConstantRange() function only looks at one instruction to determine the constant range, so it should be rather cheap compared to the computeKnownBits() call (and in the signed case, additionally ComputeNumSignBits()).

For the longer-term future, I think it would make sense to turn the computeConstantRange() function into a recursive computation, in which case it could subsume both computeKnownBits and ComputeNumSignBits for the purpose of overflow checks (which are, in the end, purely range based). But getting to that point would be quite a bit of work...

[spatel]

In D59386#1432364, @lebedev.ri wrote:

Hmm, this looks reasonable to me, @spatel ?
Are there any concerns of performance impact of using ConstantRange() here ?
Though i do think it does pull it's weight.

At this point, any change to heavily used ValueTracking calls may be cause for compile-time concern.
I'd hope that ConstantRange can be optimized to just 2 ints in the usual case, so it should be fast (as we assume for KnownBits too I think).
To be safe, we could do a test-suite or stage2 compile and see if that shows regressions, but the optimizations in the tests do look nice. :)

llvm/lib/Analysis/ValueTracking.cpp

5717 ↗

(On Diff #190864)

By limiting to ConstantDataVector, are we excluding weird (non-power-of-2 bitwidths or number of elements) types? Is that intentional?

[nikic]

Rebase and remove constant vector code.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

5717 ↗

(On Diff #190864)

Nope, that's not intentional. This is just me being fuzzy on the Constant hierarchy...

I've dropped the non-splat vector handling code from this revision and will handle this properly in a followup.

[spatel]

LGTM

[lebedev.ri]

In D59386#1432364, @lebedev.ri wrote:

Hmm, this looks reasonable to me

llvm/trunk/lib/Analysis/ValueTracking.cpp

switch (OR) {
     case ConstantRange::OverflowResult::AlwaysOverflows:
       return OverflowResult::AlwaysOverflows;
     case ConstantRange::OverflowResult::NeverOverflows:
       return OverflowResult::NeverOverflows;
   }
   llvm_unreachable("Unknown OverflowResult");
 }
 
+/// Combine constant ranges from computeConstantRange() and computeKnownBits().
+static ConstantRange computeConstantRangeIncludingKnownBits(
+    const Value *V, bool ForSigned, const DataLayout &DL, unsigned Depth,
+    AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
+    OptimizationRemarkEmitter *ORE = nullptr, bool UseInstrInfo = true) {
+  KnownBits Known = computeKnownBits(
+      V, DL, Depth, AC, CxtI, DT, ORE, UseInstrInfo);
+  ConstantRange CR = computeConstantRange(V, UseInstrInfo);
+  return ConstantRange::fromKnownBits(Known, ForSigned).intersectWith(CR);
+}
+
 OverflowResult llvm::computeOverflowForUnsignedAdd(
     const Value *LHS, const Value *RHS, const DataLayout &DL,
     AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
     bool UseInstrInfo) {
-  KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT,
-                                        nullptr, UseInstrInfo);
-  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);
+  ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
+      LHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT,
+  ConstantRange RHSRange = computeConstantRangeIncludingKnownBits(
+      RHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT,
   return mapOverflowResult(LHSRange.unsignedAddMayOverflow(RHSRange));
 }
 
 static OverflowResult computeOverflowForSignedAdd(const Value *LHS,
                                                   const Value *RHS,
                                                   const AddOperator *Add,
                                                   const DataLayout &DL,
                                                   AssumptionCache *AC,

 }
 
 OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
                                                    const Value *RHS,
                                                    const DataLayout &DL,
                                                    AssumptionCache *AC,
                                                    const Instruction *CxtI,
                                                    const DominatorTree *DT) {
-  KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
-  KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
-  ConstantRange LHSRange =
-      ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false);
-  ConstantRange RHSRange =
-      ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false);
+  ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
+      LHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT);
+  ConstantRange RHSRange = computeConstantRangeIncludingKnownBits(
+      RHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT);
   return mapOverflowResult(LHSRange.unsignedSubMayOverflow(RHSRange));
 }
 
 OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,
                                                  const Value *RHS,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
static void setLimitsForSelectPattern(const SelectInst &SI, APInt &Lower,
   }
 
   // TODO Handle min/max flavors.
 }
 
 ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo) {
   assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction");
 
+  const APInt *C;
+  if (match(V, m_APInt(C)))
+    return ConstantRange(*C);
+
   InstrInfoQuery IIQ(UseInstrInfo);
   unsigned BitWidth = V->getType()->getScalarSizeInBits();
   APInt Lower = APInt(BitWidth, 0);
   APInt Upper = APInt(BitWidth, 0);
   if (auto *BO = dyn_cast<BinaryOperator>(V))
     setLimitsForBinOp(*BO, Lower, Upper, IIQ);
   else if (auto *II = dyn_cast<IntrinsicInst>(V))
     setLimitsForIntrinsic(*II, Lower, Upper);

llvm/trunk/test/Transforms/InstCombine/and2.ll

 }
 
 ; Don't do it if the shift has another use.
 
 define i8 @and1_lshr1_is_cmp_eq_0_multiuse(i8 %x) {
 ; CHECK-LABEL: @and1_lshr1_is_cmp_eq_0_multiuse(
 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 1, %x
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[SH]], 1
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[SH]], [[AND]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[SH]], [[AND]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %sh = lshr i8 1, %x
   %and = and i8 %sh, 1
   %add = add i8 %sh, %and
   ret i8 %add
 }
 

llvm/trunk/test/Transforms/InstCombine/saturating-add-sub.ll

;
   %b = sub nuw i8 %a, 10
   %r = call i8 @llvm.uadd.sat.i8(i8 %b, i8 9)
   ret i8 %r
 }
 
 define i8 @test_scalar_uadd_urem_no_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_uadd_urem_no_ov(
 ; CHECK-NEXT:    [[B:%.*]] = urem i8 [[A:%.*]], 100
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[B]], i8 -100)
+; CHECK-NEXT:    [[R:%.*]] = add nuw nsw i8 [[B]], -100
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = urem i8 %a, 100
   %r = call i8 @llvm.uadd.sat.i8(i8 %b, i8 156)
   ret i8 %r
 }
 
 define i8 @test_scalar_uadd_urem_may_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_uadd_urem_may_ov(
 ; CHECK-NEXT:    [[B:%.*]] = urem i8 [[A:%.*]], 100
 ; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[B]], i8 -99)
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = urem i8 %a, 100
   %r = call i8 @llvm.uadd.sat.i8(i8 %b, i8 157)
   ret i8 %r
 }
 
 ; We have a constant range for the LHS, but only known bits for the RHS
 define i8 @test_scalar_uadd_urem_known_bits(i8 %a, i8 %b) {
 ; CHECK-LABEL: @test_scalar_uadd_urem_known_bits(
 ; CHECK-NEXT:    [[AA:%.*]] = udiv i8 -66, [[A:%.*]]
 ; CHECK-NEXT:    [[BB:%.*]] = and i8 [[B:%.*]], 63
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[AA]], i8 [[BB]])
+; CHECK-NEXT:    [[R:%.*]] = add nuw i8 [[AA]], [[BB]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %aa = udiv i8 190, %a
   %bb = and i8 %b, 63
   %r = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %bb)
   ret i8 %r
 }
 

 ;
   %a_neg = or <2 x i8> %a, <i8 -128, i8 -128>
   %r = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %a_neg, <2 x i8> <i8 10, i8 20>)
   ret <2 x i8> %r
 }
 
 define i8 @test_scalar_usub_add_nuw_no_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_add_nuw_no_ov(
-; CHECK-NEXT:    [[B:%.*]] = add nuw i8 [[A:%.*]], 10
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[B]], i8 9)
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[A:%.*]], 1
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = add nuw i8 %a, 10
   %r = call i8 @llvm.usub.sat.i8(i8 %b, i8 9)
   ret i8 %r
 }
 
 define i8 @test_scalar_usub_add_nuw_eq(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_add_nuw_eq(
-; CHECK-NEXT:    [[B:%.*]] = add nuw i8 [[A:%.*]], 10
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[B]], i8 10)
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 [[A:%.*]]
 ;
   %b = add nuw i8 %a, 10
   %r = call i8 @llvm.usub.sat.i8(i8 %b, i8 10)
   ret i8 %r
 }
 
 define i8 @test_scalar_usub_add_nuw_may_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_add_nuw_may_ov(
 ; CHECK-NEXT:    [[B:%.*]] = add nuw i8 [[A:%.*]], 10
 ; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[B]], i8 11)
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = add nuw i8 %a, 10
   %r = call i8 @llvm.usub.sat.i8(i8 %b, i8 11)
   ret i8 %r
 }
 
 define i8 @test_scalar_usub_urem_must_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_urem_must_ov(
-; CHECK-NEXT:    [[B:%.*]] = urem i8 [[A:%.*]], 10
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[B]], i8 10)
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %b = urem i8 %a, 10
   %r = call i8 @llvm.usub.sat.i8(i8 %b, i8 10)
   ret i8 %r
 }
 
 ; Like the previous case, the result is always zero here. However, as there's
 ; no actual overflow, we won't know about it.
 define i8 @test_scalar_usub_urem_must_zero(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_urem_must_zero(
 ; CHECK-NEXT:    [[B:%.*]] = urem i8 [[A:%.*]], 10
 ; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[B]], i8 9)
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = urem i8 %a, 10
   %r = call i8 @llvm.usub.sat.i8(i8 %b, i8 9)
   ret i8 %r
 }
 
 ; We have a constant range for the LHS, but only known bits for the RHS
 define i8 @test_scalar_usub_add_nuw_known_bits(i8 %a, i8 %b) {
 ; CHECK-LABEL: @test_scalar_usub_add_nuw_known_bits(
 ; CHECK-NEXT:    [[AA:%.*]] = add nuw i8 [[A:%.*]], 10
 ; CHECK-NEXT:    [[BB:%.*]] = and i8 [[B:%.*]], 7
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[AA]], i8 [[BB]])
+; CHECK-NEXT:    [[R:%.*]] = sub nuw i8 [[AA]], [[BB]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %aa = add nuw i8 %a, 10
   %bb = and i8 %b, 7
   %r = call i8 @llvm.usub.sat.i8(i8 %aa, i8 %bb)
   ret i8 %r
 }
 
 define i8 @test_scalar_usub_add_nuw_inferred(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_add_nuw_inferred(
 ; CHECK-NEXT:    [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[B]], 9
+; CHECK-NEXT:    [[R:%.*]] = add nuw i8 [[B]], 9
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = call i8 @llvm.usub.sat.i8(i8 %a, i8 10)
   %r = add i8 %b, 9
   ret i8 %r
 }
 
 define <2 x i8> @test_vector_usub_add_nuw_no_ov(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_usub_add_nuw_no_ov(
-; CHECK-NEXT:    [[B:%.*]] = add nuw <2 x i8> [[A:%.*]], <i8 10, i8 10>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[B]], <2 x i8> <i8 9, i8 9>)
+; CHECK-NEXT:    [[R:%.*]] = add <2 x i8> [[A:%.*]], <i8 1, i8 1>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %b = add nuw <2 x i8> %a, <i8 10, i8 10>
   %r = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> %b, <2 x i8> <i8 9, i8 9>)
   ret <2 x i8> %r
 }
 
 ; Can be optimized if the usub.sat RHS constant range handles non-splat vectors.

llvm/trunk/test/Transforms/InstCombine/uadd-with-overflow.ll

 ;
   %a = add nuw i8 %x, 200
   %b = tail call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 %a, i8 55)
   ret { i8, i1 } %b
 }
 
 define { i8, i1 } @no_fold_on_constant_add_overflow(i8 %x) {
 ; CHECK-LABEL: @no_fold_on_constant_add_overflow(
-; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], -56
-; CHECK-NEXT:    [[B:%.*]] = tail call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[A]], i8 56)
-; CHECK-NEXT:    ret { i8, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i8, i1 } { i8 undef, i1 true }, i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret { i8, i1 } [[TMP1]]
 ;
   %a = add nuw i8 %x, 200
   %b = tail call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 %a, i8 56)
   ret { i8, i1 } %b
 }
 
 define { <2 x i8>, <2 x i1> } @no_fold_vector_no_overflow(<2 x i8> %x) {
 ; CHECK-LABEL: @no_fold_vector_no_overflow(

llvm/trunk/test/Transforms/LoopVectorize/X86/small-size.ll

 ; CHECK:       .lr.ph5.preheader:
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[N]], -1
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
 ; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    [[N_RND_UP:%.*]] = add nuw nsw i64 [[TMP3]], 4
 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP2]], 3
 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = zext i32 [[TMP4]] to i64
-; CHECK-NEXT:    [[N_VEC:%.*]] = sub nsw i64 [[N_RND_UP]], [[N_MOD_VF]]
+; CHECK-NEXT:    [[N_VEC:%.*]] = sub nuw nsw i64 [[N_RND_UP]], [[N_MOD_VF]]
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT1:%.*]] = insertelement <4 x i64> undef, i64 [[TMP3]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT2:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT1]], <4 x i64> undef, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[PRED_STORE_CONTINUE8:%.*]] ]
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i64> undef, i64 [[INDEX]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT]], <4 x i64> undef, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i64> [[BROADCAST_SPLAT]], <i64 0, i64 1, i64 2, i64 3>