[Transform] Improve fold of sadd.with.overflow

[dlrobertson]

Summary

Fold add nsw + sadd.with.overflow with constants in some cases.

Fixes: https://bugs.llvm.org/show_bug.cgi?id=38146

[dlrobertson]

Comments and feedback would be very much appreciated. I did my best to follow https://llvm.org/docs/Contributing.html and https://llvm.org/docs/Phabricator.html, but I might have missed something. Please let me know if I did.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2045

I was not entirely sure how to solve the last case. sadd.with.overflow returns an aggregate, while add nsw does not. I was not sure how to construct the aggregate, so I did not address the last case in my first attempt.

2063

This should be similar, but since I'm *very* new to LLVM, I'd like to keep this diff as small in scope as possible. I'd like to address uadd.with.overflow in a follow-up.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1825

nit: Unnecessary braces.

2045

You can construct the aggregate with the CreateOverflowTuple helper, with overflow set to a false constant.

It's probably better to leave it out in this patch though, as this is quite a different optimization. Generally I'd drop all the sign/range checks here, as the fold is valid in either case -- there's just an even better one possible that's not implemented yet.

2048

nit: The variables used in the matchers don't need to be initialized, and it's usually not done.

2050

It is better to use an m_APInt matcher for these, because it will also work with (splat) vector constants (and you're working on APInts below anyway).

2055

Consider something like %y = add nsw i8 %x, 127; sadd.with.overflow(%y, 127). The constants have same sign and you will transform this to sadd.with.overflow(%x, 127+127), where 127+127 = -2.

This transform can't be applied if the result of the addition overflows. You can use sadd_ov on APInt to check for that.

llvm/test/Transforms/InstCombine/call-add-with-overflow.ll

1 ↗

(On Diff #189067)

To make future diffs easier, it's preferred to automatically generate checks using the utils/update_test_checks.py script.

22 ↗

(On Diff #189067)

As we recently added vector support for these intrinsics, we should also have some vector tests. Good cases to cover are:

• Splat constant <2 x i32> <i32 42, i32 42> (will work out of the box once you switch to m_APInt)
• Splat constant with undef <2 x i32> <i32 42, i32 undef> (will also work out of the box)
• Non-splat constant <2 x i32> <i32 42, i32 24> (will not work, and that's okay)

Additionally, the overflowing case mentioned above should be checked, as a negative example. The inverted case here with -7 and 13 rather than the other way around, would also be good.

[nagisa]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2043

This last case can also be folded into an overflow call. While not optimal, it "feels" to me that we better do that, rather than skipping this case entirely, if just for now.

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2043

Per the comment below I'll update this in a follow up PR if that is okay.

2045

Ah! That makes perfect sense. Thanks!

It's probably better to leave it out in this patch though, as this is quite a different optimization.

Will do.

llvm/test/Transforms/InstCombine/call-add-with-overflow.ll

1 ↗

(On Diff #189067)

Thanks!

22 ↗

(On Diff #189067)

Splat constant with undef <2 x i32> <i32 42, i32 undef> (will also work out of the box)

The test I wrote for this did not fold, so I may have done something wrong.

[dlrobertson]

• Addressed nits
• Use m_APInt instead of ConstantInt
• Updated tests
• Removed special cases (Will add them in a follow-up)

[dlrobertson]

llvm/test/Transforms/InstCombine/call-add-with-overflow.ll

58 ↗

(On Diff #189104)

Note: this did not fold.

[nikic]

llvm/test/Transforms/InstCombine/call-add-with-overflow.ll

58 ↗

(On Diff #189104)

Ooops, my bad. I was under the impression that m_APInt ignores undefs, but apparently only matchers for specific constants like m_Zero() do that. Something we might want to improve.

71 ↗

(On Diff #189104)

One more test that would be good to have is a negative test for add (without nsw) with sadd. Could also have add nuw (no fold) and add nuw nsw (fold) variants to be thorough.

[lebedev.ri]

llvm/test/Transforms/InstCombine/call-add-with-overflow.ll

58 ↗

(On Diff #189104)

I tried to touch upon that in D47983.
It would require gradual migration.

[dlrobertson]

• Add tests

[nikic]

I've committed your tests with the current output in rL355328. Can you please rebase this revision over the committed tests, so that only the changes made by the new transform remain?

[dlrobertson]

• Rebase on master

[dlrobertson]

I've committed your tests with the current output in rL355328. Can you please rebase this revision over the committed tests, so that only the changes made by the new transform remain?

Is this the preferred way to add tests? E.g. for the future changes I make for uadd.with.overflow, should I add the tests in a diff and then follow the diff up with another that also contains code changes?

[lebedev.ri]

In D58881#1417653, @dlrobertson wrote:

I've committed your tests with the current output in rL355328. Can you please rebase this revision over the committed tests, so that only the changes made by the new transform remain?

Is this the preferred way to add tests? E.g. for the future changes I make for uadd.with.overflow, should I add the tests in a diff and then follow the diff up with another that also contains code changes?

Yes, absolutely.

1. That makes the diff readable. The changes will be visible, not just the test addition.
2. That helps with test coverage. You want those tests regardless of whether the change itself will land or be reverted.

[nikic]

LGTM. @spatel Do you have anything to add?

[dlrobertson]

In D58881#1418025, @lebedev.ri wrote:

Yes, absolutely.

1. That makes the diff readable. The changes will be visible, not just the test addition.
2. That helps with test coverage. You want those tests regardless of whether the change itself will land or be reverted.

Yeah that makes sense. Thanks for the explanation. I'll try to do this for future changes.

[spatel]

LGTM - see inline for a couple of minor points.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2038–2040

Nit: prefer to give constant values a 'C' name and write a code comment using those names to describe the transform.
So something like:

// If we have 2 constant operands whose sum does not overflow:
// saddo (X +nsw C0), C1 --> saddo X, C0+C1
const APInt *C0, *C1;
if (match(...))

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

36–37 ↗

(On Diff #189228)

Nit: Ideally, the positive test would use constants at the limit, and the negative test would use constants just over that limit. So the 1st test would be something like:

%2 = add nsw i8 %0, 100
%3 = tail call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %2, i8 27)
ret { i8, i1 } %3

and this one:

%2 = add nsw i8 %0, 100
%3 = tail call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %2, i8 28)
ret { i8, i1 } %3

That gives us just a bit more coverage in case the underlying code breaks somehow, and makes it clearer how the transform is implemented.

[dlrobertson]

• Fix nits
• Update tests

[dlrobertson]

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

36–37 ↗

(On Diff #189228)

Good point. Added in the update.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *canonicalizeConstantArg0ToArg1(CallInst &Call) {
   if (isa<Constant>(Arg0) && !isa<Constant>(Arg1)) {
     Call.setArgOperand(0, Arg1);
     Call.setArgOperand(1, Arg0);
     return &Call;
   }
   return nullptr;
 }
 
+Instruction *InstCombiner::foldIntrinsicWithOverflowCommon(IntrinsicInst *II) {
+  OverflowCheckFlavor OCF =
+      IntrinsicIDToOverflowCheckFlavor(II->getIntrinsicID());
+  assert(OCF != OCF_INVALID && "unexpected!");
+
+  Value *OperationResult = nullptr;
+  Constant *OverflowResult = nullptr;
+  if (OptimizeOverflowCheck(OCF, II->getArgOperand(0), II->getArgOperand(1),
+                            *II, OperationResult, OverflowResult))
+    return CreateOverflowTuple(II, OperationResult, OverflowResult);
+  return nullptr;
+}
+
 /// CallInst simplification. This mostly only handles folding of intrinsic
 /// instructions. For normal calls, it allows visitCallBase to do the heavy
 /// lifting.
 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
   if (Value *V = SimplifyCall(&CI, SQ.getWithInstruction(&CI)))
     return replaceInstUsesWith(CI, V);
 
   if (isFreeCall(&CI, &TLI))
case Intrinsic::fshr: {
     if (!isPowerOf2_32(BitWidth))
       break;
     APInt Op2Demanded = APInt::getLowBitsSet(BitWidth, Log2_32_Ceil(BitWidth));
     KnownBits Op2Known(BitWidth);
     if (SimplifyDemandedBits(II, 2, Op2Demanded, Op2Known))
       return &CI;
     break;
   }
+  case Intrinsic::sadd_with_overflow: {
+    if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
+      return I;
+    if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
+      return I;
+
+    // `add nsw` + `sadd.with.overflow` with constants should fold.
+    Value *X;
+    const APInt *RHS, *LHS;
+    Value *Arg0 = II->getArgOperand(0);
+    Value *Arg1 = II->getArgOperand(1);
+    if (match(Arg0, m_NSWAdd(m_Value(X), m_APInt(LHS))) &&
+        match(Arg1, m_APInt(RHS))) {
+      bool Overflow;
+      APInt NewC = RHS->sadd_ov(*LHS, Overflow);
+      if (!Overflow)
+        return replaceInstUsesWith(
+            *II, Builder.CreateBinaryIntrinsic(
+                     Intrinsic::sadd_with_overflow, X,
+                     ConstantInt::get(Arg1->getType(), NewC)));
+    }
+
+    break;
+  }
   case Intrinsic::uadd_with_overflow:
-  case Intrinsic::sadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     LLVM_FALLTHROUGH;
 
   case Intrinsic::usub_with_overflow:
   case Intrinsic::ssub_with_overflow: {
-    OverflowCheckFlavor OCF =
-        IntrinsicIDToOverflowCheckFlavor(II->getIntrinsicID());
-    assert(OCF != OCF_INVALID && "unexpected!");
-
-    Value *OperationResult = nullptr;
-    Constant *OverflowResult = nullptr;
-    if (OptimizeOverflowCheck(OCF, II->getArgOperand(0), II->getArgOperand(1),
-                              *II, OperationResult, OverflowResult))
-      return CreateOverflowTuple(II, OperationResult, OverflowResult);
+    if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
+      return I;
 
     break;
   }
 
   case Intrinsic::uadd_sat:
   case Intrinsic::sadd_sat:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   /// already be inserted into the function.
   Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
 
   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
                                        bool JoinedByAnd, Instruction &CxtI);
   Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
   Value *getSelectCondition(Value *A, Value *B);
 
+  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
+
 public:
   /// Inserts an instruction \p New before instruction \p Old
   ///
   /// Also adds the new instruction to the worklist and returns \p New so that
   /// it is suitable for use as the return from the visitation patterns.
   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
     assert(New && !New->getParent() &&
            "New instruction already inserted into a basic block!");

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32>, <2 x i32>)
+
+declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32)
+
+declare { i8, i1 } @llvm.sadd.with.overflow.i8(i8, i8)
+
+define { i32, i1 } @simple_fold(i32) {
+; CHECK-LABEL: @simple_fold(
+; 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]]
+;
+  %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 { i8, i1 } @no_fold_on_constant_add_overflow(i8) {
+; CHECK-LABEL: @no_fold_on_constant_add_overflow(
+; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i8 [[TMP0:%.*]], 127
+; CHECK-NEXT:    [[TMP3:%.*]] = tail call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[TMP2]], i8 127)
+; CHECK-NEXT:    ret { i8, i1 } [[TMP3]]
+;
+  %2 = add nsw i8 %0, 127
+  %3 = tail call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %2, i8 127)
+  ret { i8, i1 } %3
+}
+
+define { <2 x i32>, <2 x i1> } @fold_simple_splat_constant(<2 x i32>) {
+; CHECK-LABEL: @fold_simple_splat_constant(
+; CHECK-NEXT:    [[TMP2:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[TMP0:%.*]], <2 x i32> <i32 42, i32 42>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP2]]
+;
+  %2 = add nsw <2 x i32> %0, <i32 12, i32 12>
+  %3 = tail call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> %2, <2 x i32> <i32 30, i32 30>)
+  ret { <2 x i32>, <2 x i1> } %3
+}
+
+define { <2 x i32>, <2 x i1> } @no_fold_splat_undef_constant(<2 x i32>) {
+; CHECK-LABEL: @no_fold_splat_undef_constant(
+; CHECK-NEXT:    [[TMP2:%.*]] = add nsw <2 x i32> [[TMP0:%.*]], <i32 12, i32 undef>
+; CHECK-NEXT:    [[TMP3:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[TMP2]], <2 x i32> <i32 30, i32 30>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP3]]
+;
+  %2 = add nsw <2 x i32> %0, <i32 12, i32 undef>
+  %3 = tail call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> %2, <2 x i32> <i32 30, i32 30>)
+  ret { <2 x i32>, <2 x i1> } %3
+}
+
+define { <2 x i32>, <2 x i1> } @no_fold_splat_not_constant(<2 x i32>, <2 x i32>) {
+; CHECK-LABEL: @no_fold_splat_not_constant(
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw <2 x i32> [[TMP0:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[TMP3]], <2 x i32> <i32 30, i32 30>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP4]]
+;
+  %3 = add nsw <2 x i32> %0, %1
+  %4 = tail call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> %3, <2 x i32> <i32 30, i32 30>)
+  ret { <2 x i32>, <2 x i1> } %4
+}
+
+define { i32, i1 } @fold_nuwnsw(i32) {
+; CHECK-LABEL: @fold_nuwnsw(
+; CHECK-NEXT:    [[TMP2:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP0:%.*]], i32 42)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP2]]
+;
+  %2 = add nuw nsw i32 %0, 12
+  %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %2, i32 30)
+  ret { i32, i1 } %3
+}
+
+define { i32, i1 } @no_fold_nuw(i32) {
+; CHECK-LABEL: @no_fold_nuw(
+; CHECK-NEXT:    [[TMP2:%.*]] = add nuw i32 [[TMP0:%.*]], 12
+; CHECK-NEXT:    [[TMP3:%.*]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP2]], i32 30)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP3]]
+;
+  %2 = add nuw i32 %0, 12
+  %3 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %2, i32 30)
+  ret { i32, i1 } %3
+}