[InstCombine] (Y + ~X) + 1 --> Y - X fold (PR42459)

[lebedev.ri]

Summary

To be noted, this pattern is not unhandled by instcombine per-se,
it is somehow does end up being folded when one runs opt -O3,
but not if it's just -instcombine. Regardless, that fold is
indirect, depends on some other folds, and is thus blind
when there are extra uses.

This does address the regression being exposed in previous patch D63992.

https://godbolt.org/z/7DGltU
https://rise4fun.com/Alive/EPO0

Fixes PR42459

[lebedev.ri]

So apparently we were already handling the (A + 1) + ~B case,
but not this case with +1 being the outer instruction..
Move the fold to the original fold.

[spatel]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1207–1210

Here's the sibling matcher. The -reassociation pass tries to create this form (move constant operands up in a chain of reassociative ops).

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1207–1210

Yep, found it once i understood that the fold *was* being done by instcombine after all (after adding commutative tests), and moved the fold here.
Though i don't understand the -print-after-all output, -reassociation does not run there..

[spatel]

LGTM

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1207–1210

The descriptive text for -reassociation is "Reassociate expressions", so that might be obscuring your search, but I see the expected diff:

*** IR Dump After Simplify the CFG ***
; Function Attrs: norecurse nounwind readnone
define i32 @t0(i32 %x, i32 %y) local_unnamed_addr #0 {
  %o0 = xor i32 %x, -1
  %o1 = add i32 %o0, %y
  %o2 = add i32 %o1, 1
  ret i32 %o2
}
*** IR Dump After Reassociate expressions ***
; Function Attrs: norecurse nounwind readnone
define i32 @t0(i32 %x, i32 %y) local_unnamed_addr #0 {
  %o0 = xor i32 %x, -1
  %o1 = add i32 %o0, 1
  %o2 = add i32 %o1, %y
  ret i32 %o2
}

[lebedev.ri]

Thank you for the review!

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1207–1210

Oh yeah, thank you!
I was looking for something else, and kind-of did not notice *that* change.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) {
   if (match(Op0, m_ZExt(m_Value(X))) &&
       X->getType()->getScalarSizeInBits() == 1)
     return SelectInst::Create(X, AddOne(Op1C), Op1);
 
   // ~X + C --> (C-1) - X
   if (match(Op0, m_Not(m_Value(X))))
     return BinaryOperator::CreateSub(SubOne(Op1C), X);
 
+  // add (add (xor X, -1), Y), 1 --> sub Y, X
+  if (match(&Add, m_Add(m_c_Add(m_Not(m_Value(X)), m_Value(Y)), m_One())))
+    return BinaryOperator::CreateSub(Y, X);
+
   const APInt *C;
   if (!match(Op1, m_APInt(C)))
     return nullptr;
 
   // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C)
   const APInt *C2;
   if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && *C2 == -*C)
     return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2));
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 
   // A + -B  -->  A - B
   if (match(RHS, m_Neg(m_Value(B))))
     return BinaryOperator::CreateSub(LHS, B);
 
   if (Value *V = checkForNegativeOperand(I, Builder))
     return replaceInstUsesWith(I, V);
 
   // (A + 1) + ~B --> A - B
   // ~B + (A + 1) --> A - B
   if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))))
     return BinaryOperator::CreateSub(A, B);
 
   // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
   if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
 
   // A+B --> A|B iff A and B have no bits set in common.
   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
     return BinaryOperator::CreateOr(LHS, RHS);
 

test/Transforms/InstCombine/add.ll

;
   %E = add i32 %C, %D
   ret i32 %E
 }
 
 ; E = (A + ~B) + 1 = A - B
 define i32 @add_to_sub(i32 %M, i32 %B) {
 ; CHECK-LABEL: @add_to_sub(
 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[M:%.*]], 42
-; CHECK-NEXT:    [[C:%.*]] = xor i32 [[B:%.*]], -1
-; CHECK-NEXT:    [[D:%.*]] = add i32 [[A]], [[C]]
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[D]], 1
+; CHECK-NEXT:    [[E:%.*]] = sub i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %A = mul i32 %M, 42          ; thwart complexity-based ordering
   %C = xor i32 %B, -1
   %D = add i32 %A, %C
   %E = add i32 %D, 1
   ret i32 %E
 }
 
 ; E = (~B + A) + 1 = A - B
 define i32 @add_to_sub2(i32 %A, i32 %M) {
 ; CHECK-LABEL: @add_to_sub2(
-; CHECK-NEXT:    [[B:%.*]] = mul i32 [[M:%.*]], 42
-; CHECK-NEXT:    [[C:%.*]] = xor i32 [[B]], -1
-; CHECK-NEXT:    [[D:%.*]] = add i32 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[D]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[M:%.*]], -42
+; CHECK-NEXT:    [[E:%.*]] = add i32 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %B = mul i32 %M, 42          ; thwart complexity-based ordering
   %C = xor i32 %B, -1
   %D = add i32 %C, %A
   %E = add i32 %D, 1
   ret i32 %E
 }

test/Transforms/InstCombine/fold-inc-of-add-of-not-x-and-y-to-sub-x-from-y.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; Given:
 ;   add (add (xor %x, -1), %y), 1
 ; Transform it to:
 ;   sub %y, %x
 
 ;------------------------------------------------------------------------------;
 ; Scalar tests
 ;------------------------------------------------------------------------------;
 
 define i32 @t0(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t0(
-; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], 1
+; CHECK-NEXT:    [[T2:%.*]] = sub i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = xor i32 %x, -1
   %t1 = add i32 %t0, %y
   %t2 = add i32 %t1, 1
   ret i32 %t2
 }
 
 ;------------------------------------------------------------------------------;
 ; Vector tests
 ;------------------------------------------------------------------------------;
 
 define <4 x i32> @t1_vec_splat(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @t1_vec_splat(
-; CHECK-NEXT:    [[T0:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
-; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = add <4 x i32> [[T1]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    [[T2:%.*]] = sub <4 x i32> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T2]]
 ;
   %t0 = xor <4 x i32> %x, <i32 -1, i32 -1, i32 -1, i32 -1>
   %t1 = add <4 x i32> %t0, %y
   %t2 = add <4 x i32> %t1, <i32 1, i32 1, i32 1, i32 1>
   ret <4 x i32> %t2
 }
 
 define <4 x i32> @t2_vec_undef0(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @t2_vec_undef0(
-; CHECK-NEXT:    [[T0:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 undef, i32 -1>
-; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = add <4 x i32> [[T1]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    [[T2:%.*]] = sub <4 x i32> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T2]]
 ;
   %t0 = xor <4 x i32> %x, <i32 -1, i32 -1, i32 undef, i32 -1>
   %t1 = add <4 x i32> %t0, %y
   %t2 = add <4 x i32> %t1, <i32 1, i32 1, i32 1, i32 1>
   ret <4 x i32> %t2
 }
 
 define <4 x i32> @t3_vec_undef1(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @t3_vec_undef1(
-; CHECK-NEXT:    [[T0:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
-; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = add <4 x i32> [[T1]], <i32 1, i32 1, i32 undef, i32 1>
+; CHECK-NEXT:    [[T2:%.*]] = sub <4 x i32> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T2]]
 ;
   %t0 = xor <4 x i32> %x, <i32 -1, i32 -1, i32 -1, i32 -1>
   %t1 = add <4 x i32> %t0, %y
   %t2 = add <4 x i32> %t1, <i32 1, i32 1, i32 undef, i32 1>
   ret <4 x i32> %t2
 }
 
 define <4 x i32> @t4_vec_undef2(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @t4_vec_undef2(
-; CHECK-NEXT:    [[T0:%.*]] = xor <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 undef, i32 -1>
-; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = add <4 x i32> [[T1]], <i32 1, i32 1, i32 undef, i32 1>
+; CHECK-NEXT:    [[T2:%.*]] = sub <4 x i32> [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T2]]
 ;
   %t0 = xor <4 x i32> %x, <i32 -1, i32 -1, i32 undef, i32 -1>
   %t1 = add <4 x i32> %t0, %y
   %t2 = add <4 x i32> %t1, <i32 1, i32 1, i32 undef, i32 1>
   ret <4 x i32> %t2
 }
 
 ;------------------------------------------------------------------------------;
 ; One-use tests
 ;------------------------------------------------------------------------------;
 
 declare void @use32(i32)
 
 define i32 @t5(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t5(
 ; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], 1
+; CHECK-NEXT:    [[T2:%.*]] = sub i32 [[Y:%.*]], [[X]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = xor i32 %x, -1
   call void @use32(i32 %t0)
   %t1 = add i32 %t0, %y
   %t2 = add i32 %t1, 1
   ret i32 %t2
 }
 
 define i32 @t6(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t6(
 ; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -1
 ; CHECK-NEXT:    [[T1:%.*]] = add i32 [[T0]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], 1
+; CHECK-NEXT:    [[T2:%.*]] = sub i32 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = xor i32 %x, -1
   %t1 = add i32 %t0, %y
   call void @use32(i32 %t1)
   %t2 = add i32 %t1, 1
   ret i32 %t2
 }
 
 define i32 @t7(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t7(
 ; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = add i32 [[T0]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], 1
+; CHECK-NEXT:    [[T2:%.*]] = sub i32 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t0 = xor i32 %x, -1
   call void @use32(i32 %t0)
   %t1 = add i32 %t0, %y
   call void @use32(i32 %t1)
   %t2 = add i32 %t1, 1
   ret i32 %t2
 }
 
 ;------------------------------------------------------------------------------;
 ; Commutativity
 ;------------------------------------------------------------------------------;
 
 declare i32 @gen32()
 
 define i32 @t8_commutative(i32 %x) {
 ; CHECK-LABEL: @t8_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
-; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[Y]], [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[T1]], 1
+; CHECK-NEXT:    [[T2:%.*]] = sub i32 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %y = call i32 @gen32()
   %t0 = xor i32 %x, -1
   %t1 = add i32 %y, %t0 ; swapped
   %t2 = add i32 %t1, 1
   ret i32 %t2
 }

test/Transforms/InstCombine/sub-minmax.ll

 }
 
 
 define i32 @max_na_bi_minux_na_use(i32 %A, i32 %Bi) {
 ; CHECK-LABEL: @max_na_bi_minux_na_use(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[A:%.*]], -32
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[A]], i32 -32
 ; CHECK-NEXT:    [[L1:%.*]] = xor i32 [[TMP2]], -1
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[L1]], [[A]]
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[TMP3]], 1
+; CHECK-NEXT:    [[X:%.*]] = sub i32 [[A]], [[TMP2]]
 ; CHECK-NEXT:    call void @use32(i32 [[L1]])
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %not = xor i32 %A, -1
   %l0 = icmp ult i32 %not, 31
   %l1 = select i1 %l0, i32 %not, i32 31
   %x = sub i32 %l1, %not
   call void @use32(i32 %l1)
;
   ret i8 %minxy
 }
 
 define i8 @umin_not_sub_rev(i8 %x, i8 %y) {
 ; CHECK-LABEL: @umin_not_sub_rev(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Y]]
 ; CHECK-NEXT:    [[MINXY:%.*]] = xor i8 [[TMP2]], -1
-; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[MINXY]], [[X]]
-; CHECK-NEXT:    [[SUBX:%.*]] = add i8 [[TMP3]], 1
+; CHECK-NEXT:    [[SUBX:%.*]] = sub i8 [[X]], [[TMP2]]
 ; CHECK-NEXT:    [[SUBY:%.*]] = sub i8 [[Y]], [[TMP2]]
 ; CHECK-NEXT:    call void @use8(i8 [[SUBX]])
 ; CHECK-NEXT:    call void @use8(i8 [[SUBY]])
 ; CHECK-NEXT:    ret i8 [[MINXY]]
 ;
   %nx = xor i8 %x, -1
   %ny = xor i8 %y, -1
   %cmpxy = icmp ult i8 %nx, %ny