[InstCombine] Add new combine to add folding.

[cdawson]

Summary

(X | C1) + C2 --> (X | C1) ^ C1 iff (C1 == -C2)

I verified the correctness using Alive:
https://rise4fun.com/Alive/YNV

This transform enables the following transform that already exists in instcombine:

(X | Y) ^ Y --> X & ~Y

As a result, the full expected transform is:

(X | C1) + C2 --> X & ~C1 iff (C1 == -C2)

There already exists the transform in the sub case:

(X | Y) - Y --> X & ~Y

however this does not trigger in the case where Y is constant due to an earlier transform:

X - (-C) --> X + C

With this new add fold, both the add and sub constant cases are handled.

This is a spin off from: D61307

[lebedev.ri]

Needs some negative tests (non-matching scalar constants; non-matching vector constants; vector with undef; matching vector constants, but non-splat (i.e. not all constants in vector are identical); ..)

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

899 ↗

(On Diff #198023)

Constant is guaranteed to be on the rhs

llvm/test/Transforms/InstCombine/add.ll

998 ↗

(On Diff #198023)

This will already be canonicalized to the @test44.

[cdawson]

Addressed review comments

[lebedev.ri]

llvm/test/Transforms/InstCombine/sub.ll

1281 ↗

(On Diff #198034)

Hm, these are tests from D61307, right?
This comment seems wrong, i think it will trigger there.

[spatel]

I think we would've avoided some confusion if the tests were committed with baseline checks as a preliminary step. That way, we can see exactly what is and isn't changing with the code patch. Please do that or let me know if I should do that on your behalf.

[cdawson]

Updated patch after test pre-commit

[lebedev.ri]

Looks reasonable.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

896 ↗

(On Diff #198468)

this will never be the case

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

Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) {
   // ~X + C --> (C-1) - X
   if (match(Op0, m_Not(m_Value(X))))
     return BinaryOperator::CreateSub(SubOne(Op1C), 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));
+
   if (C->isSignMask()) {
     // If wrapping is not allowed, then the addition must set the sign bit:
     // X + (signmask) --> X | signmask
     if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())
       return BinaryOperator::CreateOr(Op0, Op1);
 
     // If wrapping is allowed, then the addition flips the sign bit of LHS:
     // X + (signmask) --> X ^ signmask
     return BinaryOperator::CreateXor(Op0, Op1);
   }
 
   // Is this add the last step in a convoluted sext?
   // add(zext(xor i16 X, -32768), -32768) --> sext X
   Type *Ty = Add.getType();
-  const APInt *C2;
   if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) &&
       C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C)
     return CastInst::Create(Instruction::SExt, X, Ty);
 
   if (C->isOneValue() && Op0->hasOneUse()) {
     // add (sext i1 X), 1 --> zext (not X)
     // TODO: The smallest IR representation is (select X, 0, 1), and that would
     // not require the one-use check. But we need to remove a transform in

llvm/trunk/test/Transforms/InstCombine/add.ll

;
   %D = add i32 %C, %A
   %E = add i32 %D, 1
   ret i32 %E
 }
 
 ; (X | C1) + C2 --> (X | C1) ^ C1 iff (C1 == -C2)
 define i32 @test44(i32 %A) {
 ; CHECK-LABEL: @test44(
-; CHECK-NEXT:    [[B:%.*]] = or i32 [[A:%.*]], 123
-; CHECK-NEXT:    [[C:%.*]] = add nsw i32 [[B]], -123
-; CHECK-NEXT:    ret i32 [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -124
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %B = or i32 %A, 123
   %C = add i32 %B, -123
   ret i32 %C
 }
 
 define i32 @test44_extra_use(i32 %A) {
 ; CHECK-LABEL: @test44_extra_use(
 ; CHECK-NEXT:    [[B:%.*]] = or i32 [[A:%.*]], 123
-; CHECK-NEXT:    [[C:%.*]] = add nsw i32 [[B]], -123
-; CHECK-NEXT:    [[D:%.*]] = mul i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A]], -124
+; CHECK-NEXT:    [[D:%.*]] = mul i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %B = or i32 %A, 123
   %C = add i32 %B, -123
   %D = mul i32 %B, %C
   ret i32 %D
 }
 
 define i32 @test44_non_matching(i32 %A) {
 ; CHECK-LABEL: @test44_non_matching(
 ; CHECK-NEXT:    [[B:%.*]] = or i32 [[A:%.*]], 123
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[B]], -321
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %B = or i32 %A, 123
   %C = add i32 %B, -321
   ret i32 %C
 }
 
 define <2 x i32> @test44_vec(<2 x i32> %A) {
 ; CHECK-LABEL: @test44_vec(
-; CHECK-NEXT:    [[B:%.*]] = or <2 x i32> [[A:%.*]], <i32 123, i32 123>
-; CHECK-NEXT:    [[C:%.*]] = add nsw <2 x i32> [[B]], <i32 -123, i32 -123>
-; CHECK-NEXT:    ret <2 x i32> [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 -124, i32 -124>
+; CHECK-NEXT:    ret <2 x i32> [[TMP1]]
 ;
   %B = or <2 x i32> %A, <i32 123, i32 123>
   %C = add <2 x i32> %B, <i32 -123, i32 -123>
   ret <2 x i32> %C
 }
 
 define <2 x i32> @test44_vec_non_matching(<2 x i32> %A) {
 ; CHECK-LABEL: @test44_vec_non_matching(

llvm/trunk/test/Transforms/InstCombine/sub.ll

;
   %3 = select <2 x i1> %2, <2 x i32> %1, <2 x i32> <i32 -256, i32 -128>
   %res = sub <2 x i32> zeroinitializer, %3
   ret <2 x i32> %res
 }
 
 ; Check (X | Y) - Y --> X & ~Y when Y is a constant
 define i32 @test70(i32 %A) {
 ; CHECK-LABEL: @test70(
-; CHECK-NEXT:    [[B:%.*]] = or i32 [[A:%.*]], 123
-; CHECK-NEXT:    [[C:%.*]] = add nsw i32 [[B]], -123
-; CHECK-NEXT:    ret i32 [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -124
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %B = or i32 %A, 123
   %C = sub i32 %B, 123
   ret i32 %C
 }
 
 ; Check (X | Y) - Y --> (X | Y) ^ Y doesn't happen where (X | Y) has multiple uses
 define i32 @test71(i32 %A, i32 %B) {

llvm/trunk/test/Transforms/InstCombine/with_overflow.ll

;
   %a = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 42, i32 %x)
   ret { i32, i1 } %a
 }
 
 ; Always overflow tests
 
 define { i8, i1 } @uadd_always_overflow(i8 %x) nounwind {
 ; CHECK-LABEL: @uadd_always_overflow(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], -64
-; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[Y]], 64
-; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i8, i1 } { i8 undef, i1 true }, i8 [[A]], 0
-; CHECK-NEXT:    ret { i8, i1 } [[TMP1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 63
+; CHECK-NEXT:    [[TMP2:%.*]] = insertvalue { i8, i1 } { i8 undef, i1 true }, i8 [[TMP1]], 0
+; CHECK-NEXT:    ret { i8, i1 } [[TMP2]]
 ;
   %y = or i8 %x, 192
   %a = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 %y, i8 64)
   ret { i8, i1 } %a
 }
 
 define { i8, i1 } @usub_always_overflow(i8 %x) nounwind {
 ; CHECK-LABEL: @usub_always_overflow(