[Transform] Improve saddo with mixed signs

[dlrobertson]

Summary

Improve folding of the sadd.with.overflow intrinsic with add nsw
when given constants of mixed signs.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2060

The use of abs here makes me uncomfortable... abs(INT_MIN) is INT_MIN again. So if we take saddo(X +nsw INT_MIN, 1), then the check here is abs(INT_MIN) s< abs(1) which is INT_MIN s< 1, which is true. While this will ultimately give a conservatively correct result, you'd prefer this case to take the other branch.

[nikic]

Generally I feel that the optimization we want to go for here is a more general one. We already detect always/never overflow conditions based on known bits. This is a variation that detects never overflow based on the constant range of the input, for one specific case. We have generic code in InstructionSimplify to determine the ConstantRange of binary operators and intrinsics (setLimitsForBinOp and setLimitsForIntrinsic) for cases where this can be done cheaply (inspecting only one instruction).

I'm thinking that we should generalize that code to take any Instruction, move it as an exported API into ValueTracking and then do a generic ConstantRange based always/never overflow check here. Does that sound reasonable @spatel?

[spatel]

In D59071#1421411, @nikic wrote:

Generally I feel that the optimization we want to go for here is a more general one. We already detect always/never overflow conditions based on known bits. This is a variation that detects never overflow based on the constant range of the input, for one specific case. We have generic code in InstructionSimplify to determine the ConstantRange of binary operators and intrinsics (setLimitsForBinOp and setLimitsForIntrinsic) for cases where this can be done cheaply (inspecting only one instruction).

I'm thinking that we should generalize that code to take any Instruction, move it as an exported API into ValueTracking and then do a generic ConstantRange based always/never overflow check here. Does that sound reasonable @spatel?

Yes, if we can use the same/similar code for more general transforms, it makes sense to move it to ValueTracking.

[dlrobertson]

In D59071#1421411, @nikic wrote:

I'm thinking that we should generalize that code to take any Instruction, move it as an exported API into ValueTracking and then do a generic ConstantRange based always/never overflow check here.

So do you mean update the computeKnownBitsFromOperator for sadd_with_overflow to also take into account the overflow flag?

[nikic]

Moved constant range calculation into ValueTracking with rL355781.

In D59071#1422370, @dlrobertson wrote:

So do you mean update the computeKnownBitsFromOperator for sadd_with_overflow to also take into account the overflow flag?

Based on the previous commit, you can call computeConstantRange() on the LHS, and then check whether adding the RHS constant to that range can ever overflow. Assuming a range of Lo <= X <= Hi and constant C: If C >= 0 then an overflow cannot occur if Hi <= SignedMax - C and always occurs if Lo > SignedMax -C. If C < 0 then an overflow cannot occur if Lo >= SignedMin - C and always occurs if Hi < SignedMin - C.

To go one step further, rather than limiting this optimization to just the with.overflow intrinsics, this could be done in computeOverflowForSignedAdd (and friends), as this would also benefit saturated math intrinsics, as well as nsw/nuw inference on normal adds. (It might make sense to start with computeOverflowForUnsignedAdd, as the logic for unsigned is simpler.)

[nikic]

I've created D59193 to implement just the raw overflow checking logic based on ConstantRanges (without using it in ValueTracking).

[nikic]

D59386 implements the full optimization for the unsigned case, and D59450 is preparation for the signed add case, though there's a few more followups necessary there (for signed sub, for extension to use computeConstantRange, and for handling AlwaysOverflows).

[dlrobertson]

In D59071#1431908, @nikic wrote:

D59386 implements the full optimization for the unsigned case, and D59450 is preparation for the signed add case, though there's a few more followups necessary there (for signed sub, for extension to use computeConstantRange, and for handling AlwaysOverflows).

Awesome! I'll move on to uaddo

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::fshr: {
     break;
   }
   case Intrinsic::sadd_with_overflow: {
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
       return I;
 
-    // Given 2 constant operands whose sum does not overflow:
-    // saddo (X +nsw C0), C1 -> saddo X, C0 + C1
+    // Given 2 constant operands whose sum does not overflow the intrinsic
+    // may be folded.
+    //
+    // Cases for `saddo (X +nsw C0), C1 -> saddo X, C0 + C1`:
+    //
+    // - Same sign can be folded to a single `saddo` call.
+    // - Opposite signs with `|C1| > |C0|` can be folded to a single `saddo`
+    //   call.
+    //
+    // Cases for `saddo (X +nsw C0), C1 -> X +nsw (C0 + C1), false`:
+    //
+    // - Opposite signs with `|C1| <= |C0|` can be folded to a single `+nsw`
+    //   call with the overflow flag set to false.
     Value *X;
     const APInt *C0, *C1;
     Value *Arg0 = II->getArgOperand(0);
     Value *Arg1 = II->getArgOperand(1);
     if (match(Arg0, m_NSWAdd(m_Value(X), m_APInt(C0))) &&
         match(Arg1, m_APInt(C1))) {
       bool Overflow;
       APInt NewC = C1->sadd_ov(*C0, Overflow);
-      if (!Overflow)
+      if (!Overflow) {
+        if (C0->isNegative() == C1->isNegative() || C0->abs().slt(C1->abs())) {
           return replaceInstUsesWith(
               *II, Builder.CreateBinaryIntrinsic(
                        Intrinsic::sadd_with_overflow, X,
                        ConstantInt::get(Arg1->getType(), NewC)));
+        } else {
+          return CreateOverflowTuple(
+              II,
+              Builder.CreateNSWAdd(X, ConstantInt::get(Arg1->getType(), NewC)),
+              Builder.getFalse());
+        }
+      }
     }
 
     break;
   }
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))

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

 ; CHECK-NEXT:    [[TMP2:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP0:%.*]], i32 20)
 ; CHECK-NEXT:    ret { i32, i1 } [[TMP2]]
 ;
   %2 = add nsw i32 %0, 7
   %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %2, i32 13)
   ret { i32, i1 } %3
 }
 
-define { i32, i1 } @fold_mixed_signs(i32) {
-; CHECK-LABEL: @fold_mixed_signs(
-; CHECK-NEXT:    [[TMP2:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP0:%.*]], i32 6)
-; CHECK-NEXT:    ret { i32, i1 } [[TMP2]]
+define { i32, i1 } @fold_mixed_signs_first_high(i32) {
+; CHECK-LABEL: @fold_mixed_signs_first_high(
+; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[TMP0:%.*]], 6
+; CHECK-NEXT:    [[TMP3:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP2]], 0
+; CHECK-NEXT:    ret { i32, i1 } [[TMP3]]
 ;
   %2 = add nsw i32 %0, 13
   %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %2, i32 -7)
   ret { i32, i1 } %3
 }
 
+define { i32, i1 } @fold_mixed_signs_second_high(i32) {
+; CHECK-LABEL: @fold_mixed_signs_second_high(
+; CHECK-NEXT:    [[TMP2:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP0:%.*]], i32 -6)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP2]]
+;
+  %2 = add nsw i32 %0, 7
+  %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %2, i32 -13)
+  ret { i32, i1 } %3
+}
+
 define { i8, i1 } @fold_on_constant_add_no_overflow(i8) {
 ; CHECK-LABEL: @fold_on_constant_add_no_overflow(
 ; CHECK-NEXT:    [[TMP2:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[TMP0:%.*]], i8 127)
 ; CHECK-NEXT:    ret { i8, i1 } [[TMP2]]
 ;
   %2 = add nsw i8 %0, 100
   %3 = tail call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %2, i8 27)
   ret { i8, i1 } %3