Added instruction combine to transform few more negative values addition to subtraction (Part 3)

[dinesh.d]

Summary

First Part: http://reviews.llvm.org/D3733
2nd Part: http://reviews.llvm.org/D4209

This patch enable following transform

(x + (~(y | c) + 1)   -->   x - (y | c) if c is odd
(x + (~((y >> z) | c) + 1)   -->   x - ((y>>z) | c)  if c is odd

Z3 verification code:

http://rise4fun.com/Z3/ZA06

[dinesh.d]

Removed code setting NSW/ NUW flag for now

[jingyue]

Looks good overall.

I have a more high-level question. Why are these logics in checkForNegativeOperand instead of visitXor? Aren't transformations such as

XOR(AND(Z, ~C), (~C + 1)) => NEG(OR(Z, C))

beneficial even the XOR is not the RHS of an ADD?

lib/Transforms/InstCombine/InstCombineAddSub.cpp

962 ↗

(On Diff #10820)

Make sure this TODO goes away after you rebase.

998 ↗

(On Diff #10820)

typo "LHS"

1007 ↗

(On Diff #10820)

LHS == NOT(AND(Z, ~C2))

is not consistent with previous comments using

NEG(OR(Z, C))

Are they mathematically equivalent? If so, could you make the comments consistent?

test/Transforms/InstCombine/add2.ll

154 ↗

(On Diff #10820)

I'd love to see some comments on what math expression these IR instructions compute, and what those magic numbers (e.g., -1431655766) mean.

Same for the next two test cases.

[dinesh.d]

I have updated patch for comments with following extra changes.

1. ADD(XOR(AND(Z, ~C), ~C), 1) == NEG(OR(Z, C)) is true for both if C is even or odd. [http://rise4fun.com/Z3/Pwkf]
2. Rearranged test cases, generated from following test code
   
   int test10(int x, int y) { return y + (~((x >> 3) & 0x55555555) + 1); } int test11(int x, int y) { return y + (~(x & 0x55555555) + 1); } int test12(int x, int y) { return (y + 1) + ~(x & 0x55555555); }
   
   int test13(int x, int y) { return y + (~(x & 0x55555556) + 1); } int test14(int x, int y) { return (y + 1) + ~(x & 0x55555556); }
   
   int test15(int x, int y) { return y + (~(x | 0x55555556) + 1); } int test16(int x, int y) { return (y + 1) + ~(x | 0x55555556); }
   
   int test17(int x, int y) { return y + (~(x | 0x55555555) + 1); } int test18(int x, int y) { return (y + 1) + ~(x | 0x55555555); }

[dinesh.d]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

962 ↗

(On Diff #10820)

sure, will take care of it.

998 ↗

(On Diff #10820)

updated.

1007 ↗

(On Diff #10820)

updated.

test/Transforms/InstCombine/add2.ll

154 ↗

(On Diff #10820)

updated

[dinesh.d]

I have a more high-level question. Why are these logics in checkForNegativeOperand instead of visitXor? Aren't transformations such as
XOR(AND(Z, ~C), (~C + 1)) => NEG(OR(Z, C))
beneficial even the XOR is not the RHS of an ADD?

NEG(X) gets converted to XOR.

NEG(X) = XOR(x, -1) + 1

So it is not useful to transform XOR(..) to NEG(..) and it will loop infinitely.

[dinesh.d]

thanks

[dinesh.d]

Closed by commit rL211881 (authored by dinesh).

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

bool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) {
   bool LHSKnownNonNegative, LHSKnownNegative;
   bool RHSKnownNonNegative, RHSKnownNegative;
   ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, 0);
   ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, 0);
   if (LHSKnownNonNegative && RHSKnownNonNegative)
     return true;
 
   return false;
- }
 
 // Checks if any operand is negative and we can convert add to sub.
- // This function checks for following negative patterns
- //   ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
- //   ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C)) if C is odd
- //   TODO: XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
- Value *checkForNegativeOperand(BinaryOperator &I,
-                                InstCombiner::BuilderTy *Builder) {
-   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+//   ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
+//   XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
 
-   // This function creates 2 instructions to replace ADD, we need at least one
-   // of LHS or RHS to have one use to ensure benefit in transform.
-   if (!LHS->hasOneUse() && !RHS->hasOneUse())
-     return nullptr;
 
-   Value *X = nullptr, *Y = nullptr, *Z = nullptr;
-   const APInt *C1 = nullptr, *C2 = nullptr;
 
-   // if ONE is on other side, swap
-   if (match(RHS, m_Add(m_Value(X), m_One())))
-     std::swap(LHS, RHS);
 
-   if (match(LHS, m_Add(m_Value(X), m_One()))) {
-     // if XOR on other side, swap
-     if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
-       std::swap(X, RHS);
 
-     if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
-       // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))
-       // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))
-       if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {
-         Value *NewAnd = Builder->CreateAnd(Z, *C1);
-         return Builder->CreateSub(RHS, NewAnd, "sub");
-       } else if (C1->countTrailingZeros() == 0) {
-         // if C1 is ODD and
-         // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))
-         // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))
-         if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
-           Value *NewOr = Builder->CreateOr(Z, ~(*C1));
-           return Builder->CreateSub(RHS, NewOr, "sub");
-         }
-       }
-     }
-   }
+      } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
 
-   return nullptr;
- }
+  // Restore LHS and RHS
+  LHS = I.getOperand(0);
+  RHS = I.getOperand(1);
+
+  // if XOR is on other side, swap
+  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
+    std::swap(LHS, RHS);
+
+  // C2 is ODD
+  // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))
+  // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))
+  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
+    if (C1->countTrailingZeros() == 0)
+      if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
+        Value *NewOr = Builder->CreateOr(Z, ~(*C2));
+        return Builder->CreateSub(RHS, NewOr, "sub");
+      }
 
- Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
    bool Changed = SimplifyAssociativeOrCommutative(I);
    Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
    if (Value *V = SimplifyVectorOp(I))
      return ReplaceInstUsesWith(I, V);
 
    if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
                                   I.hasNoUnsignedWrap(), DL))
if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
         return ReplaceInstUsesWith(I, Res);
 
     // trunc(p)-trunc(q) -> trunc(p-q)
     if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
         match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
         return ReplaceInstUsesWith(I, Res);
       }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))

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

define i16 @test9(i16 %a) {
        %c = mul i16 %a, 32767
        %d = add i16 %b, %c
        ret i16 %d
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  %d = mul i16 %a, -32767
 ; CHECK-NEXT:  ret i16 %d
 }
 
-define i32 @test10(i32 %x) {
-  %x.not = or i32 %x, -1431655766
-  %neg = xor i32 %x.not, 1431655765
-  %add = add i32 %x, 1
+; y + (~((x >> 3) & 0x55555555) + 1) -> y - ((x >> 3) & 0x55555555)
+define i32 @test10(i32 %x, i32 %y) {
+  %shr = ashr i32 %x, 3
+  %shr.not = or i32 %shr, -1431655766
+  %neg = xor i32 %shr.not, 1431655765
+  %add = add i32 %y, 1
   %add1 = add i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, -1431655766
-; CHECK-NEXT: ret i32 [[AND]]
+; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+; y + (~(x & 0x55555555) + 1) -> y - (x & 0x55555555)
 define i32 @test11(i32 %x, i32 %y) {
   %x.not = or i32 %x, -1431655766
   %neg = xor i32 %x.not, 1431655765
   %add = add i32 %y, 1
   %add1 = add i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655765
 ; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+; (y + 1) + ~(x & 0x55555555) -> y - (x & 0x55555555)
 define i32 @test12(i32 %x, i32 %y) {
-  %shr = ashr i32 %x, 3
-  %shr.not = or i32 %shr, -1431655766
-  %neg = xor i32 %shr.not, 1431655765
-  %add = add i32 %y, 1
-  %add1 = add i32 %add, %neg
+  %add = add nsw i32 %y, 1
+  %x.not = or i32 %x, -1431655766
+  %neg = xor i32 %x.not, 1431655765
+  %add1 = add nsw i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test12(
-; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
-; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655765
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655765
 ; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+; y + (~(x & 0x55555556) + 1) -> y - (x & 0x55555556)
 define i32 @test13(i32 %x, i32 %y) {
   %x.not = or i32 %x, -1431655767
   %neg = xor i32 %x.not, 1431655766
   %add = add i32 %y, 1
   %add1 = add i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655766
 ; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+; (y + 1) + ~(x & 0x55555556) -> y - (x & 0x55555556)
 define i32 @test14(i32 %x, i32 %y) {
-  %shr = ashr i32 %x, 3
-  %shr.not = or i32 %shr, -1431655767
-  %neg = xor i32 %shr.not, 1431655766
-  %add = add i32 %y, 1
-  %add1 = add i32 %add, %neg
+  %add = add nsw i32 %y, 1
+  %x.not = or i32 %x, -1431655767
+  %neg = xor i32 %x.not, 1431655766
+  %add1 = add nsw i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test14(
-; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
-; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655766
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655766
 ; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+; y + (~(x | 0x55555556) + 1) -> y - (x | 0x55555556)
 define i32 @test15(i32 %x, i32 %y) {
   %x.not = and i32 %x, -1431655767
   %neg = xor i32 %x.not, -1431655767
   %add = add i32 %y, 1
   %add1 = add i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test15(
-; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655766
-; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[OR]]
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+; (y + 1) + ~(x | 0x55555556) -> y - (x | 0x555555556)
 define i32 @test16(i32 %x, i32 %y) {
- %shr = ashr i32 %x, 3
- %shr.not = and i32 %shr, -1431655767
- %neg = xor i32 %shr.not, -1431655767
- %add = add i32 %y, 1
- %add1 = add i32 %add, %neg
+  %add = add nsw i32 %y, 1
+  %x.not = and i32 %x, -1431655767
+  %neg = xor i32 %x.not, -1431655767
+  %add1 = add nsw i32 %add, %neg
   ret i32 %add1
 ; CHECK-LABEL: @test16(
-; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
-; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 [[SHR]], 1431655766
-; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[OR]]
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+; y + (~(x | 0x55555555) + 1) -> y - (x | 0x55555555)
+define i32 @test17(i32 %x, i32 %y) {
+  %x.not = and i32 %x, -1431655766
+  %add2 = xor i32 %x.not, -1431655765
+  %add1 = add nsw i32 %add2, %y
+  ret i32 %add1
+; CHECK-LABEL: @test17(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+; (y + 1) + ~(x | 0x55555555) -> y - (x | 0x55555555)
+define i32 @test18(i32 %x, i32 %y) {
+  %add = add nsw i32 %y, 1
+  %x.not = and i32 %x, -1431655766
+  %neg = xor i32 %x.not, -1431655766
+  %add1 = add nsw i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test18(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
 define i16 @add_nsw_mul_nsw(i16 %x) {
  %add1 = add nsw i16 %x, %x
  %add2 = add nsw i16 %add1, %x
  ret i16 %add2
 ; CHECK-LABEL: @add_nsw_mul_nsw(