[ValueTracking] Use computeConstantRange() for signed add overflow determination

[nikic]

Summary

This is D59386 for the signed add case. The computeConstantRange() result is now intersected into the existing known bits information, allowing to detect additional no-overflow/always-overflow conditions (though the latter isn't used yet).

This (finally...) covers the motivating case from D59071.

[lebedev.ri]

Please can you split up your changes?
https://llvm.org/docs/DeveloperPolicy.html#code-reviews

Split your patch into multiple smaller patches that build on each other. The smaller your patch, the higher the probability that somebody will take a quick look at it.

I would very much prefer to quickly look through 3 small differentials here rather than one medium..

llvm/lib/Analysis/ValueTracking.cpp

4087–4091 ↗

(On Diff #194198)

So the only thing happening here is that RangeType is now being passed, right?
Please, precommit the NFC part of the refactoring, and leave only

+ ConstantRange::PreferredRangeType RangeType =
+     ForSigned ? ConstantRange::Signed : ConstantRange::Unsigned;
- return CR1.intersectWith(CR2);
+ return CR1.intersectWith(CR2, RangeType);

4136–4159 ↗

(On Diff #194198)

This looks like it should be a new differential, after the this one.

4195–4198 ↗

(On Diff #194198)

And one more new differential

[nikic]

Rebase over committed changes, reduce diff to only handling signed add.

[nikic]

There are a few additional test changes due to the min/max handling in computeConstantRange() that has landed in the meantime.

llvm/lib/Analysis/ValueTracking.cpp

4087–4091 ↗

(On Diff #194198)

Done in rL357968.

4136–4159 ↗

(On Diff #194198)

This change is needed because the LHSKnown variable no longer exists, so it can't come after. There's no reason it can't come before though, so done in rL357969.

4195–4198 ↗

(On Diff #194198)

Done, I've reduced this to just the signed add case and will submit a followup for signed sub.

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

4136–4159 ↗

(On Diff #194198)

Sure. But i was talking about the entire block of code i highlighted with a comment.
I.e. i think the rest of the computeOverflowForSignedAdd() change should be in a new diff too.
Or if you leave just the computeConstantRangeIncludingKnownBits() part, there are no test changes?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4136–4159 ↗

(On Diff #194198)

Ooooh, I didn't realize that you can highlight a range of code and assumed your comment is about the change directly above.

But yes, just the computeConstantRangeIncludingKnownBits() change doesn't result in test changes (it it not strictly speaking NFC, but it's likely not possible to actually trigger a difference without using the function in a signed context).

[lebedev.ri]

LG

llvm/lib/Analysis/ValueTracking.cpp

4136–4159 ↗

(On Diff #194198)

Okay, thank you.

llvm/trunk/lib/Analysis/ValueTracking.cpp

 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 CR1 = ConstantRange::fromKnownBits(Known, ForSigned);
   ConstantRange CR2 = computeConstantRange(V, UseInstrInfo);
-  // TODO: Use ForSigned to determine preferred range.
-  ConstantRange::PreferredRangeType RangeType = ConstantRange::Smallest;
+  ConstantRange::PreferredRangeType RangeType =
+      ForSigned ? ConstantRange::Signed : ConstantRange::Unsigned;
   return CR1.intersectWith(CR2, RangeType);
 }
 
 OverflowResult llvm::computeOverflowForUnsignedAdd(
     const Value *LHS, const Value *RHS, const DataLayout &DL,
     AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
     bool UseInstrInfo) {
   ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
static OverflowResult computeOverflowForSignedAdd(const Value *LHS,
   // be 0 and therefore the carry out of the addition is also 1.
   //
   // 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);
-  ConstantRange LHSRange =
-      ConstantRange::fromKnownBits(LHSKnown, /*signed*/ true);
-  ConstantRange RHSRange =
-      ConstantRange::fromKnownBits(RHSKnown, /*signed*/ true);
+  ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
+      LHS, /*ForSigned=*/true, DL, /*Depth=*/0, AC, CxtI, DT);
+  ConstantRange RHSRange = computeConstantRangeIncludingKnownBits(
+      RHS, /*ForSigned=*/true, DL, /*Depth=*/0, AC, CxtI, DT);
   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;

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 nuw i8 [[SH]], [[AND]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw 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/icmp-add.ll

;
   %c = icmp ugt <2 x i8> %x, %a
   ret <2 x i1> %c
 }
 
 define i1 @sum_ugt_op_uses(i8 %p1, i8 %p2, i8* %p3) {
 ; CHECK-LABEL: @sum_ugt_op_uses(
 ; CHECK-NEXT:    [[X:%.*]] = sdiv i8 42, [[P1:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = sdiv i8 42, [[P2:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[X]], [[Y]]
+; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X]], [[Y]]
 ; CHECK-NEXT:    store i8 [[A]], i8* [[P3:%.*]], align 1
 ; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[X]], [[A]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %x = sdiv i8 42, %p1
   %y = sdiv i8 42, %p2
   %a = add i8 %x, %y
   store i8 %a, i8* %p3

llvm/trunk/test/Transforms/InstCombine/minmax-fold.ll

;
   %r = select <2 x i1> %c, <2 x i33> %a, <2 x i33> <i33 240, i33 240>
   ret <2 x i33> %r
 }
 
 define i8 @PR14613_smin(i8 %x) {
 ; CHECK-LABEL: @PR14613_smin(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 [[X:%.*]], 40
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 40
-; CHECK-NEXT:    [[U7:%.*]] = add i8 [[TMP2]], 15
+; CHECK-NEXT:    [[U7:%.*]] = add nsw i8 [[TMP2]], 15
 ; CHECK-NEXT:    ret i8 [[U7]]
 ;
   %u4 = sext i8 %x to i32
   %u5 = add nuw nsw i32 %u4, 15
   %u6 = icmp slt i32 %u5, 55
   %u7 = select i1 %u6, i32 %u5, i32 55
   %r = trunc i32 %u7 to i8
   ret i8 %r

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

 ;
   %a = add nsw i32 %x, 7
   %b = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %a, i32 13)
   ret { i32, i1 } %b
 }
 
 define { i32, i1 } @fold_mixed_signs(i32 %x) {
 ; CHECK-LABEL: @fold_mixed_signs(
-; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X:%.*]], i32 6)
+; CHECK-NEXT:    [[B:%.*]] = add nsw i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[B]], 0
 ; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = add nsw i32 %x, 13
   %b = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %a, i32 -7)
   ret { i32, i1 } %b
 }
 
 define { i8, i1 } @fold_on_constant_add_no_overflow(i8 %x) {

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

;
   %bb = and i8 %b, 63
   %r = call i8 @llvm.uadd.sat.i8(i8 %aa, i8 %bb)
   ret i8 %r
 }
 
 define i8 @test_scalar_sadd_srem_no_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_srem_no_ov(
 ; CHECK-NEXT:    [[B:%.*]] = srem i8 [[A:%.*]], 100
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[B]], i8 28)
+; CHECK-NEXT:    [[R:%.*]] = add nsw i8 [[B]], 28
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = srem i8 %a, 100
   %r = call i8 @llvm.sadd.sat.i8(i8 %b, i8 28)
   ret i8 %r
 }
 
 define i8 @test_scalar_sadd_srem_may_ov(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_srem_may_ov(
 ; CHECK-NEXT:    [[B:%.*]] = srem i8 [[A:%.*]], 100
 ; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[B]], i8 29)
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = srem i8 %a, 100
   %r = call i8 @llvm.sadd.sat.i8(i8 %b, i8 29)
   ret i8 %r
 }
 
 define i8 @test_scalar_sadd_srem_and_no_ov(i8 %a, i8 %b) {
 ; CHECK-LABEL: @test_scalar_sadd_srem_and_no_ov(
 ; CHECK-NEXT:    [[AA:%.*]] = srem i8 [[A:%.*]], 100
 ; CHECK-NEXT:    [[BB:%.*]] = and i8 [[B:%.*]], 15
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[AA]], i8 [[BB]])
+; CHECK-NEXT:    [[R:%.*]] = add nsw i8 [[AA]], [[BB]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %aa = srem i8 %a, 100
   %bb = and i8 %b, 15
   %r = call i8 @llvm.sadd.sat.i8(i8 %aa, i8 %bb)
   ret i8 %r
 }
 

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

;
   ret <2 x i32> %D
 }
 
 ; FIXME: Transform (neg (max ~X, C)) -> ((min X, ~C) + 1). Same for min.
 define i32 @test64(i32 %x) {
 ; CHECK-LABEL: @test64(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 255
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 255
-; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
+; CHECK-NEXT:    [[RES:%.*]] = add nsw i32 [[TMP2]], 1
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %1 = xor i32 %x, -1
   %2 = icmp sgt i32 %1, -256
   %3 = select i1 %2, i32 %1, i32 -256
   %res = sub i32 0, %3
   ret i32 %res
 }
;
   ret i32 %res
 }
 
 ; Check splat vectors too
 define <2 x i32> @test68(<2 x i32> %x) {
 ; CHECK-LABEL: @test68(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 255, i32 255>
 ; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> <i32 255, i32 255>
-; CHECK-NEXT:    [[RES:%.*]] = add <2 x i32> [[TMP2]], <i32 1, i32 1>
+; CHECK-NEXT:    [[RES:%.*]] = add nsw <2 x i32> [[TMP2]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i32> [[RES]]
 ;
   %1 = xor <2 x i32> %x, <i32 -1, i32 -1>
   %2 = icmp sgt <2 x i32> %1, <i32 -256, i32 -256>
   %3 = select <2 x i1> %2, <2 x i32> %1, <2 x i32> <i32 -256, i32 -256>
   %res = sub <2 x i32> zeroinitializer, %3
   ret <2 x i32> %res
 }