[InstCombine] ssubo X, C -> saddo X, -C

[dlrobertson]

Summary

ssubo X, C is equivalent to saddo X, -C. Make the transformation in
InstCombine and allow the logic implemented for saddo to fold prior
usages of add nsw or sub nsw with constants.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2160–2164 ↗

(On Diff #193069)

Hmm, why not just:

APInt NewC;
if (match(Arg1, m_APInt(C)) &&
    !subWithOverflow(NewC, 0, *C, /*IsSigned=*/II->getIntrinsicID() == Intrinsic::ssub_with_overflow)) {

?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161 ↗

(On Diff #193069)

Is C->isMaxSignedValue() necessary?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161 ↗

(On Diff #193069)

Checking for max signed value is not necessary, as -SignedMax doesn't overflow, only -SignedMin does.

For parity with ssub.sat canonicalization I'd suggest to use the same implementation here, which will also handle non-splat vector constants:

Constant *C;
if (match(Arg1, m_Constant(C)) && C->isNotMinSignedValue()) {
    Value *NegVal = ConstantExpr::getNeg(C);
    // Create ssubo with NegVal here.
}

[dlrobertson]

Gather some inspiration from ssub.sat

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2160–2164 ↗

(On Diff #193069)

Thanks for the suggestion, but as mentioned above I think isNotMinSignedValue is what I need here. If I am misunderstanding something, please let me know.

2161 ↗

(On Diff #193069)

Ah! Right. I updated the diff to look more like ssub.sat.

[dlrobertson]

Update comment

[lebedev.ri]

Looks good.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2170–2171 ↗

(On Diff #193222)

Shouldn't we do this first?

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2170–2171 ↗

(On Diff #193222)

Originally I did this so we wouldn't run this function twice (once here and once as sadd_with_overflow) , but you're correct. We need to run this first so we don't miss the optimization if the first arg is the constant.

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2170–2171 ↗

(On Diff #193222)

Actually this function doesn't call cannonicalizeConstantArg0ToArg1 so this is not the case. This function should be called when sadd_with_overflow is run, so I can't currently think of a reason why this would need to be called first.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2170–2171 ↗

(On Diff #193222)

Both orders are generally okay, and both may result in more/less work depending on the case we hit. If the common transform is first, then it might remove the intrinsic entirely right away, rather than first converting to saddo and only removing it afterwards. On the other hand, if it doesn't apply, but the saddo conversion does, then the checks will be run twice, as you already said.

I think @lebedev.ri's suggestion here is mainly a coding style choice to start with the generic transforms first and specific transforms afterwards.

[lebedev.ri]

Some notes

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161 ↗

(On Diff #193222)

This will be yet another miscompile for vectors if there is undef element.
You need to do

if (match(Arg1, m_Constant(C)) && C->isNotMinSignedValue() && !C->containsUndefElement()) {

2170–2171 ↗

(On Diff #193222)

I think @lebedev.ri's suggestion here is mainly a coding style choice to start with the generic transforms first and specific transforms afterwards.

Yes

2221 ↗

(On Diff #193222)

This is also a miscompile for vectors for undef elements (please submit fix as a new patch)

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161 ↗

(On Diff #193222)

isNotMinSignedValue() does not accept undef elements. Correctly handling non-splat vectors and undefs is why this function exists (rather than just negating isMinSignedValue).

2221 ↗

(On Diff #193222)

See above.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161 ↗

(On Diff #193222)

Hmm, very subtle. I now can notice those tests, at least in this testfile, so this won't regress if that changes.
Ok, sorry.

2170–2171 ↗

(On Diff #193222)

Then only this question remains

[dlrobertson]

Sorry for the delay. Made the requested changes.

[lebedev.ri]

LG.
@nikic ?

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2155 ↗

(On Diff #194346)

This does not create a copy of the original constant though, it just negates it.

[nikic]

LG with nit.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2146 ↗

(On Diff #194346)

This assert is a bit odd, because it checks for more than one arg, while ssubo requires exactly two. I think it can just be dropped entirely, we don't seem to have similar asserts in the surrounding code for other intrinsics.

[dlrobertson]

Removed an unneeded assert.

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2146 ↗

(On Diff #194346)

foldIntrinsiceWithOverflowCommon uses getArgOperand(1) too, so we'd hit that before the assert.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (HasNWAdd && match(Arg1, m_APInt(C1))) {
       if (!Overflow)
         return replaceInstUsesWith(
             *II, Builder.CreateBinaryIntrinsic(
                      II->getIntrinsicID(), X,
                      ConstantInt::get(Arg1->getType(), NewC)));
     }
     break;
   }
+
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     LLVM_FALLTHROUGH;
 
   case Intrinsic::usub_with_overflow:
+    if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
+      return I;
+    break;
+
   case Intrinsic::ssub_with_overflow: {
     if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
       return I;
 
+    Constant *C;
+    Value *Arg0 = II->getArgOperand(0);
+    Value *Arg1 = II->getArgOperand(1);
+    // Given a constant C that is not the minimum signed value
+    // for an integer of a given bit width:
+    //
+    // ssubo X, C -> saddo X, -C
+    if (match(Arg1, m_Constant(C)) && C->isNotMinSignedValue()) {
+      Value *NegVal = ConstantExpr::getNeg(C);
+      // Build a saddo call that is equivalent to the discovered
+      // ssubo call.
+      return replaceInstUsesWith(
+          *II, Builder.CreateBinaryIntrinsic(Intrinsic::sadd_with_overflow,
+                                             Arg0, NegVal));
+    }
+
     break;
   }
 
   case Intrinsic::uadd_sat:
   case Intrinsic::sadd_sat:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     LLVM_FALLTHROUGH;

llvm/trunk/test/Transforms/InstCombine/ssub-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.ssub.with.overflow.v2i32(<2 x i32>, <2 x i32>)
 
 declare { <2 x i8>, <2 x i1> } @llvm.ssub.with.overflow.v2i8(<2 x i8>, <2 x i8>)
 
 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32)
 
 declare { i8, i1 } @llvm.ssub.with.overflow.i8(i8, i8)
 
 define { i32, i1 } @simple_fold(i32 %x) {
 ; CHECK-LABEL: @simple_fold(
-; CHECK-NEXT:    [[A:%.*]] = add nsw i32 [[X:%.*]], -7
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 [[A]], i32 13)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X:%.*]], i32 -20)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = sub nsw i32 %x, 7
   %b = tail call { i32, i1 } @llvm.ssub.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:    [[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 = sub nsw i32 %x, 13
   %b = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 -7)
   ret { i32, i1 } %b
 }
 
 define { i8, i1 } @fold_on_constant_sub_no_overflow(i8 %x) {
 ; CHECK-LABEL: @fold_on_constant_sub_no_overflow(
-; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], -100
-; CHECK-NEXT:    [[B:%.*]] = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[A]], i8 28)
-; CHECK-NEXT:    ret { i8, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[X:%.*]], i8 -128)
+; CHECK-NEXT:    ret { i8, i1 } [[TMP1]]
 ;
   %a = sub nsw i8 %x, 100
   %b = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 %a, i8 28)
   ret { i8, i1 } %b
 }
 
 define { i8, i1 } @no_fold_on_constant_sub_overflow(i8 %x) {
 ; CHECK-LABEL: @no_fold_on_constant_sub_overflow(
 ; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], -100
-; CHECK-NEXT:    [[B:%.*]] = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[A]], i8 29)
-; CHECK-NEXT:    ret { i8, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[A]], i8 -29)
+; CHECK-NEXT:    ret { i8, i1 } [[TMP1]]
 ;
   %a = sub nsw i8 %x, 100
   %b = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 %a, i8 29)
   ret { i8, i1 } %b
 }
 
 define { <2 x i32>, <2 x i1> } @fold_simple_splat_constant(<2 x i32> %x) {
 ; CHECK-LABEL: @fold_simple_splat_constant(
-; CHECK-NEXT:    [[A:%.*]] = add nsw <2 x i32> [[X:%.*]], <i32 -12, i32 -12>
-; CHECK-NEXT:    [[B:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> [[A]], <2 x i32> <i32 30, i32 30>)
-; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[X:%.*]], <2 x i32> <i32 -42, i32 -42>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP1]]
 ;
   %a = sub nsw <2 x i32> %x, <i32 12, i32 12>
   %b = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> %a, <2 x i32> <i32 30, i32 30>)
   ret { <2 x i32>, <2 x i1> } %b
 }
 
 define { <2 x i32>, <2 x i1> } @no_fold_splat_undef_constant(<2 x i32> %x) {
 ; CHECK-LABEL: @no_fold_splat_undef_constant(
 ; CHECK-NEXT:    [[A:%.*]] = add <2 x i32> [[X:%.*]], <i32 -12, i32 undef>
-; CHECK-NEXT:    [[B:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> [[A]], <2 x i32> <i32 30, i32 30>)
-; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[A]], <2 x i32> <i32 -30, i32 -30>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP1]]
 ;
   %a = sub nsw <2 x i32> %x, <i32 12, i32 undef>
   %b = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> %a, <2 x i32> <i32 30, i32 30>)
   ret { <2 x i32>, <2 x i1> } %b
 }
 
 define { <2 x i32>, <2 x i1> } @no_fold_splat_not_constant(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @no_fold_splat_not_constant(
 ; CHECK-NEXT:    [[A:%.*]] = sub nsw <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> [[A]], <2 x i32> <i32 30, i32 30>)
-; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[A]], <2 x i32> <i32 -30, i32 -30>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP1]]
 ;
   %a = sub nsw <2 x i32> %x, %y
   %b = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> %a, <2 x i32> <i32 30, i32 30>)
   ret { <2 x i32>, <2 x i1> } %b
 }
 
 define { i32, i1 } @fold_nuwnsw(i32 %x) {
 ; CHECK-LABEL: @fold_nuwnsw(
-; CHECK-NEXT:    [[A:%.*]] = add nsw i32 [[X:%.*]], -12
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 [[A]], i32 30)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X:%.*]], i32 -42)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = sub nuw nsw i32 %x, 12
   %b = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 30)
   ret { i32, i1 } %b
 }
 
 define { i32, i1 } @no_fold_nuw(i32 %x) {
 ; CHECK-LABEL: @no_fold_nuw(
 ; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -12
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 [[A]], i32 30)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[A]], i32 -30)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = sub nuw i32 %x, 12
   %b = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 30)
   ret { i32, i1 } %b
 }
 
 define { i32, i1 } @no_fold_wrapped_sub(i32 %x) {
 ; CHECK-LABEL: @no_fold_wrapped_sub(
 ; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -12
 ; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 30, i32 [[A]])
 ; CHECK-NEXT:    ret { i32, i1 } [[B]]
 ;
   %a = sub i32 %x, 12
   %b = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 30, i32 %a)
   ret { i32, i1 } %b
 }
 
 define { i32, i1 } @fold_add_simple(i32 %x) {
 ; CHECK-LABEL: @fold_add_simple(
-; CHECK-NEXT:    [[A:%.*]] = add nsw i32 [[X:%.*]], -12
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 [[A]], i32 30)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X:%.*]], i32 -42)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = add nsw i32 %x, -12
   %b = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 30)
   ret { i32, i1 } %b
 }
 
 define { <2 x i32>, <2 x i1> } @keep_ssubo_undef(<2 x i32> %x) {
 ; CHECK-LABEL: @keep_ssubo_undef(
 ; CHECK-NEXT:    [[A:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> [[X:%.*]], <2 x i32> <i32 30, i32 undef>)
 ; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[A]]
 ;
   %a = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> %x, <2 x i32> <i32 30, i32 undef>)
   ret { <2 x i32>, <2 x i1> } %a
 }
 
 define { <2 x i32>, <2 x i1> } @keep_ssubo_non_splat(<2 x i32> %x) {
 ; CHECK-LABEL: @keep_ssubo_non_splat(
-; CHECK-NEXT:    [[A:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> [[X:%.*]], <2 x i32> <i32 30, i32 31>)
-; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.sadd.with.overflow.v2i32(<2 x i32> [[X:%.*]], <2 x i32> <i32 -30, i32 -31>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP1]]
 ;
   %a = tail call { <2 x i32>, <2 x i1> } @llvm.ssub.with.overflow.v2i32(<2 x i32> %x, <2 x i32> <i32 30, i32 31>)
   ret { <2 x i32>, <2 x i1> } %a
 }
 
 define { <2 x i8>, <2 x i1> } @keep_ssubo_one_element_is_128(<2 x i8> %x) {
 ; CHECK-LABEL: @keep_ssubo_one_element_is_128(
 ; CHECK-NEXT:    [[A:%.*]] = tail call { <2 x i8>, <2 x i1> } @llvm.ssub.with.overflow.v2i8(<2 x i8> [[X:%.*]], <2 x i8> <i8 0, i8 -128>)