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

Make sure this TODO goes away after you rebase.

998

typo "LHS"

1007

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

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

sure, will take care of it.

998

updated.

1007

updated.

test/Transforms/InstCombine/add2.ll

154

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).

lib/Transforms/InstCombine/InstCombineAddSub.cpp

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))
 //   TODO: ADD(XOR(AND(Z, ~C), ~C), 1) == NEG(OR(Z, C)) if C is even
-//   TODO: XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd
+//   XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd
 Value *checkForNegativeOperand(BinaryOperator &I,
                                InstCombiner::BuilderTy *Builder) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
   // 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;
if (match(LHS, m_Add(m_Value(X), m_One()))) {
     if (match(X, m_Xor(m_Value(Y), m_APInt(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, "", IHasNUW, IHasNSW);
       }
     }
   }
 
+  // Restore LSH 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 == NOT(AND(Z, ~C2))
+  // ADD(LHS, RHS) == SUB(RHS, AND(Z, ~C2))
+  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))) && !C1->countTrailingZeros())
+    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, "", IHasNUW, IHasNSW);
+    }
+
   return nullptr;
 }
 
 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))

test/Transforms/InstCombine/add2.ll

define i32 @test14(i32 %x, i32 %y) {
   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: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
 ; CHECK-NEXT: ret i32 [[SUB]]
 }
 
+define i32 @test15(i32 %x) {
+ %x.not = and i32 %x, -1431655766
+ %add3 = xor i32 %x.not, -1431655765
+ %add1 = add nsw i32 %add3, %x
+ ret i32 %add1
+; CHECK-LABEL: @test15(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub nsw i32 %x, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test16(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: @test16(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub nsw i32 %y, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test17(i32 %x, i32 %y) {
+ %shr = ashr i32 %x, 3
+ %shr.not = and i32 %shr, -1431655766
+ %add2 = xor i32 %shr.not, -1431655765
+ %add1 = add nsw i32 %add2, %y
+ ret i32 %add1
+; CHECK-LABEL: @test17(
+; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 [[SHR]], 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub nsw i32 %y, [[OR]]
+; 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(
 ; CHECK-NEXT: %add2 = mul nsw i16 %x, 3
 ; CHECK-NEXT: ret i16 %add2
 }