[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

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

Is C->isMaxSignedValue() necessary?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161

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

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

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

2173–2174

Shouldn't we do this first?

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2173–2174

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

2173–2174

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

2173–2174

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

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()) {

2173–2174

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

2224

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

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

2224

See above.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2161

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

2173–2174

Then only this question remains

[dlrobertson]

Sorry for the delay. Made the requested changes.

[lebedev.ri]

LG.
@nikic ?

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2185

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

2176

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

2176

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

llvm/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:
+  case Intrinsic::usub_with_overflow: {
+    if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
+      return I;
+
+    break;
+  }
+
   case Intrinsic::ssub_with_overflow: {
+    assert(CI.getNumArgOperands() > 1 && "Need at least 2 args for ssubo");
+    const APInt *C;
+    Value *Arg1 = II->getArgOperand(1);
+    // Given a constant C that is not the minimum or maximum signed value
+    // for an integer of the given bit width:
+    //
+    // ssubo X, C -> saddo X, -C
+    if (match(Arg1, m_APInt(C)) &&
+        !(C->isMinSignedValue() || C->isMaxSignedValue())) {
+      // Create a copy of the original constant and negate it.
+      APInt NewC = APInt(*C);
+      NewC.negate();
+      // Build a saddo call that is equivalent to the discovered
+      // ssubo call.
+      Type *Tys[1] = {Arg1->getType()};
+      CI.setArgOperand(1, ConstantInt::get(Arg1->getType(), NewC));
+      CI.setCalledFunction(Intrinsic::getDeclaration(
+          CI.getModule(), Intrinsic::sadd_with_overflow, Tys));
+      return &CI;
+    }
     if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
       return I;
 
     break;
   }
 
   case Intrinsic::uadd_sat:
   case Intrinsic::sadd_sat:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     LLVM_FALLTHROUGH;
   case Intrinsic::usub_sat:
   case Intrinsic::ssub_sat: {
     Value *Arg0 = II->getArgOperand(0);
     Value *Arg1 = II->getArgOperand(1);
     Intrinsic::ID IID = II->getIntrinsicID();
 
     // Make use of known overflow information.
     OverflowResult OR;
     switch (IID) {
     default:
case Intrinsic::ssub_sat:
       if (willNotOverflowSignedSub(Arg0, Arg1, *II))
         return BinaryOperator::CreateNSWSub(Arg0, Arg1);
       break;
     }
 
     // ssub.sat(X, C) -> sadd.sat(X, -C) if C != MIN
     Constant *C;
     if (IID == Intrinsic::ssub_sat && match(Arg1, m_Constant(C)) &&
         C->isNotMinSignedValue()) {
       Value *NegVal = ConstantExpr::getNeg(C);
       return replaceInstUsesWith(
           *II, Builder.CreateBinaryIntrinsic(
               Intrinsic::sadd_sat, Arg0, NegVal));
     }
 
     // sat(sat(X + Val2) + Val) -> sat(X + (Val+Val2))
     // sat(sat(X - Val2) - Val) -> sat(X - (Val+Val2))

llvm/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:    [[A:%.*]] = add nsw i32 [[X:%.*]], -13
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 [[A]], i32 -7)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X:%.*]], i32 -6)
+; 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:    [[B:%.*]] = tail call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[A]], i8 -29)
 ; CHECK-NEXT:    ret { i8, i1 } [[B]]
 ;
   %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:    [[B:%.*]] = tail 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> } [[B]]
 ;
   %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:    [[B:%.*]] = tail 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> } [[B]]
 ;
   %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:    [[B:%.*]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[A]], i32 -30)
 ; CHECK-NEXT:    ret { i32, i1 } [[B]]
 ;
   %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(