Added instruction combine to transform few more negative values addition to subtraction

[dinesh.d]

Summary

This patch enable following transform

(x + (~(y & c) + 1)   -->   x - (y & c)
(x + (~((y >> z) & c) + 1)   -->   x - ((y>>z) & c)
 
(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 hasOneUse() check and updated test cases. This patch takes care of PR14365

[bkramer]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

929

Can you return the fully transformed value? I find it confusing to have this split in half. You can create both instructions with IRBuilder and use ReplaceInstUsesWith at the call site.

[dinesh.d]

Updated patch to return fully transformed value.

Added additional transforms

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

Is it ok to loose names of instruction during transforms. This patch returns instruction names as %1, %2

[dinesh.d]

Updated patch to use APInts and simplified few checks

[dinesh.d]

gentle ping.

Will it help in reviewing if I break this patch in parts.

[dinesh.d]

This is to answer Philip's comments

Both your comment and function name here seem misleading. As far as I
can tell from your transforms, none are actual predicated on an argument
being negative. I also see no use of subtraction.

Then for this one, I'm probably missing something obvious, but where are
you initializing C1 and C2? In general, the code structure here is a
bit hard to read.

If name of the function is misleading, I don't mind any other name. This
function tries to find if any of the operand is negative and use them to
convert ADD to SUB and remove negation. I have not added ADD in function
name as I am looking to use this function to convert SUB to ADD too.

I have found 3 patterns mentioned in comment which llvm is not optimizing
any further. This functions tries to identify those patterns and optimise them.
I have put comments for one of the pattern in code. Other patterns are
implemented in similar fashion. Let me know if it is still not clear.

// Checks if any operand is negative and we can convert add to sub.
// This function checks for following 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 even
//   XOR(AND(Z, ~C), (~C + 1))      == NEG(OR(Z, C)) if C is odd

Value *checkForNegativeOperand(...) {

...

Here I am looking for first 2 patterns i.e. ADD(X, 1) where X is XOR-AND/ XOR-OR
which can occur on either side, following 2 lines to check if pattern is on RHS,
then swapping LHS and RHS will put it in LHS. This is just pointer swap and will
not change anything else. This approach will help in avoiding code duplication as
without this, I need to do all checks for first LHS and then RHS.

  // if ONE is on other side, swap
  if (match(RHS, m_Add(m_Value(X), m_One())))
    std::swap(LHS, RHS);

So if LHS = B and RHS = (X + 1), after above lines, it will become LHS = (X + 1), RHS = B.

    if (match(LHS, m_Add(m_Value(X), m_One()))) {

After this check, we can be sure that I has (X + 1) on any side and LHS is pointing to that
operand as match will true only of pattern matches and because of m_Value(X), Value *X will
be pointing to X part of (X + 1) pattern.

    // if XOR on other side, swap
    if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
      std::swap(X, RHS);

Above 2 lines is to check for XOR and swap (X, RHS) if pattern is LHS = (X + 1), RHS = B and
XOR on RHS.

	  
    if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {

Once above check is true, we will be sure that there is XOR(Y, Constant) instruction and X is
pointing to that. Again, above swap is to avoid code duplication. Further, because of m_APInt(C1),
if match returns true, C1 will point to constant part of XOR.

// ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C1 == ~(*C2))) {

Same way, I am checking if X is in OR(Z, C2) form where C2 == NOT(C1). if above match is true, we
can convert initial ADD(X+1, B) instruction to SUB(B, AND(Z, C1)) as 'ADD(XOR(OR(Z, NOT(C1)), C1)), 1)'
complete instruction can be converted to NEG(AND(Z, C1)) and ADD(NEG(AND(Z, C1)), B) is same as
SUB(B, AND(Z, C1))

Value *NewAnd = Builder->CreateAnd(Z, *C1);

Above line create AND(Z, C1)

		  
        return Builder->CreateSub(RHS, NewAnd, "", IHasNUW, IHasNSW);

and this line create SUB instruction and return to caller, where this SUB instruction can be used
to replace ADD instruction.

		  
      }
		
    ...

Returns nullptr, if I's operand does not match to any of the pattern.

return nullptr;

}

[dinesh.d]

Hi Philip,

I have added one comment at http://reviews.llvm.org/D3733 to reply your queries. Will you please
check it and let me know if it is clear or not ?

Regards
Dinesh Dwivedi

• Original Message -------

Sender : Philip Reames<[e-mail]>
Date : May 27, 2014 22:14 (GMT+05:30)
Title : Re: [PATCH] Added instruction combine to transform few more negative
values addition to subtraction

Glancing at your patch, a few quick comments.

Checks if any operand is negative and we can convert add to sub.
This function checks for following 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 even
// XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd
Value *checkForNegativeOperand(BinaryOperator &I,
InstCombiner::BuilderTy *Builder) { ...}

Both your comment and function name here seem misleading. As far as I
can tell from your transforms, none are actual predicated on an argument
being negative. I also see no use of subtraction.

Then for this one, I'm probably missing something obvious, but where are
you initializing C1 and C2? In general, the code structure here is a
bit hard to read.

Philip

[dinesh.d]

This patch creates 2 instructions to replace ADD. Updated patch to check
if atleast one of LHS or RHS to have one use to ensure benefit in transform.

[dinesh.d]

Breaking patch in to parts

[dinesh.d]

Is this the first one? Which patch is the second one?

Cheers,
Rafael

I have broken my previous patch to reduce size of patch. This is first one. As
other parts are depended on these changes, I will put them for review once this
patch is in [actually don't know how to submit dependent patches]

I have added TODO for those patches.

[dinesh.d]

Updated comments

[dinesh.d]

gentle ping

[reames]

Dinesh, I'm sorry, but I can not provide further review. I can not spot any obvious problems with your code, but after trying to justify the correctness of your change to myself several times, I can't quite do so. Rather than continue to waste your time - since you'd need to find another reviewer with commit rights anyways - I'm simply going to step aside.

[dinesh.d]

Thanks Philip.

If there is any specific part of the patch which is bothering you and you
are not sure for its correctness. I can explain why I have written it like that

and please don't think about wasting time. I mentioned this before too. I like
to hear from you so please continue review my patches if time permits.

[dinesh.d]

It will be gr8 if you can have a look.

[dinesh.d]

gentle ping

[nicholas]

Sadness. Did you know that gcc gets this even at -O0? Not this pattern mind you, but the original testcase. It's that simple, at least before we transform to xor(or) form. GCC doesn't get it in xor(or) form either.

I looked for a better way to address this optimizer deficiency and didn't find one. The one thing I didn't check is whether we could get it by reordering our optimizations inside instcombine and do something else before it gets into xor(or) form. Even if that did fix the testcase in PR14365 it would still leave the case where someone actually does write "((a|~c) ^ c) + (a+1)".

lib/Transforms/InstCombine/InstCombineAddSub.cpp

928

"atleast" --> "at least"

951

Optional: *C2 == ~(*C1) might be more efficient as !C2->intersects(*C1). It isn't, but in theory we could improve intersects to not compute an intermediate value (ie., it doesn't need to look at all the bits once it finds a pair are set in both).

test/Transforms/InstCombine/add2.ll

203

Please make sure there's a newline at the end of the file.

[dinesh.d]

Hi Nick,

m_Not checks for pattern XOR(X, -1) and will not work in current scenario.
i.e. it can check if we have XOR(X, -1) pattern but can not identify that
0x55555555 and 0xAAAAAAAA are NOT of each other.

Am I missing something?

Regards
Dinesh Dwivedi

• Original Message -------

Sender : Nick Lewycky<[e-mail]>
Date : Jun 19, 2014 11:50 (GMT+05:30)
Title : Re: [PATCH] Added instruction combine to transform few more negative
values addition to subtraction

Nick Lewycky wrote:

Sadness. Did you know that gcc gets this even at -O0? Not this pattern mind you, but the original testcase. It's that simple, at least before we transform to xor(or) form. GCC doesn't get it in xor(or) form either.

I looked for a better way to address this optimizer deficiency and didn't find one. The one thing I didn't check is whether we could get it by reordering our optimizations inside instcombine and do something else before it gets into xor(or) form. Even if that did fix the testcase in PR14365 it would still leave the case where someone actually does write "((a|~c) ^ c) + (a+1)".

Actually, I was just thinking about this some more. There's no reason
'C' needs to be a constant at all, is there? As long as it's X and ~X
(use m_Value(X) then m_Not(m_Specific(X))) the transform should be
correct, right?

Nick

Comment at: lib/Transforms/InstCombine/InstCombineAddSub.cpp:928
@@ +927,3 @@
+
+ // This function creates 2 instructions to replace ADD, we need atleast one of

+ // LHS or RHS to have one use to ensure benefit in transform.

"atleast" --> "at least"

Comment at: lib/Transforms/InstCombine/InstCombineAddSub.cpp:951
@@ +950,3 @@
+ 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);

Optional: *C2 == ~(*C1) might be more efficient as !C2->intersects(*C1). It isn't, but in theory we could improve intersects to not compute an intermediate value (ie., it doesn't need to look at all the bits once it finds a pair are set in both).

Comment at: test/Transforms/InstCombine/add2.ll:142
@@ +141,1 @@
+}
No newline at end of file

---

Please make sure there's a newline at the end of the file.

http://reviews.llvm.org/D3733

[dinesh.d]

Updated as per comments

[dinesh.d]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

928

updated

951

problem with intersects() is that it just ensure that same bit is not set in both C1 and C2 but does not ensure that if one but is set in one, it will not set in second.

We can compute xor and then check if result is all zero but I am not sure if that is more efficient than current code,
it will sure reduce readability though.

test/Transforms/InstCombine/add2.ll

203

updated.

[dinesh.d]

fixed typo in previous comment

lib/Transforms/InstCombine/InstCombineAddSub.cpp

951

Problem with intersects() is that it just ensure that same bit is not set in both C1 and C2 but does not ensure that if one bit is not set in one, it will be set in second.

[dinesh.d]

Closed by commit rL211266 (authored by dinesh).

lib/Transforms/InstCombine/InstCombineAddSub.cpp

bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) {
   // sign bit) the ripple may go up to and fill the zero, but won't change the
   // sign.  For example, (X & ~4) + 1.
 
   // TODO: Implement.
 
   return false;
 }
 
+// Checks if any operand is negative and we can convert add to sub.
+// This function checks for following 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 even
+//   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);
+
+  bool IHasNSW = I.hasNoSignedWrap();
+  bool IHasNUW = I.hasNoUnsignedWrap();
+
+  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)))) {
+      // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
+      if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C1 == ~(*C2))) {
+        Value *NewAnd = Builder->CreateAnd(Z, *C1);
+        return Builder->CreateSub(RHS, NewAnd, "", IHasNUW, IHasNSW);
+      }
+      // ADD(XOR(AND(Z, ~C), ~C), 1)== NEG(OR(Z, C)) if C is even
+      else if (!C1->countTrailingZeros()) {
+        if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (C1 == C2)) {
+          Value *NewOr = Builder->CreateOr(Z, ~(*C2));
+          return Builder->CreateSub(RHS, NewOr, "", 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);
+
+  // One is absorbed in XOR
+  // XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd
+  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))
     return ReplaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
if (Value *LHSV = dyn_castNegVal(LHS)) {
     return BinaryOperator::CreateSub(RHS, LHSV);
   }
 
   // A + -B  -->  A - B
   if (!isa<Constant>(RHS))
     if (Value *V = dyn_castNegVal(RHS))
       return BinaryOperator::CreateSub(LHS, V);
 
+  if (Value *V = checkForNegativeOperand(I, Builder))
+    return ReplaceInstUsesWith(I, V);
 
   {
     Constant *C2;
     if (Value *X = dyn_castFoldableMul(LHS, C2)) {
       if (X == RHS) // X*C + X --> X * (C+1)
         return BinaryOperator::CreateMul(RHS, AddOne(C2));
 
       // X*C1 + X*C2 --> X * (C1+C2)

test/Transforms/InstCombine/add2.ll

 define <2 x i64> @test8(<2 x i64> %A) {
   %xor = xor <2 x i64> %A, <i64 -1, i64 -1>
   %add = add <2 x i64> %xor, <i64 2, i64 3>
   ret <2 x i64> %add
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT: %add = sub <2 x i64> <i64 1, i64 2>, %A
 ; CHECK-NEXT: ret <2 x i64> %add
 }
+
+define i32 @test9(i32 %x) {
+  %x.not = or i32 %x, -1431655766
+  %neg = xor i32 %x.not, 1431655765
+  %add = add i32 %x, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test9(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, -1431655766
+; CHECK-NEXT: ret i32 [[AND]]
+}
+
+define i32 @test10(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: @test10(
+; 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 @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]]
+}
+
+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
+  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: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+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]]
+}
+
+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
+  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, 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: @test15(
+; 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 @test16(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: @test16(
+; 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 i32 @test17(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: @test17(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test18(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
+  ret i32 %add1
+; CHECK-LABEL: @test18(
+; 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: ret i32 [[SUB]]
+}
 No newline at end of file