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

[dinesh.d]

Summary

First Part: http://reviews.llvm.org/D3733

This patch enable following transform

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

Z3 verification code:

http://rise4fun.com/Z3/ZA06

[jingyue]

Hi Dinesh,

I didn't see the code handling the second case in your summary:

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

Am I missing anything?

Thanks,
Jingyue

[dinesh.d]

Hi Jingyue,

Added code can handle both cases. Basically it checks operands of OR and can deal with
both cases if it is just 'y' or '(y >> z). Now if I think, I should not have mentioned it as separate
pattern.

When I coded for this, I was looking at PR14365 and it has both pattern for XOR(AND()) and I
mentioned both pattern in my first patch for this (part 1) and just copied same for this and next
patch.

Sorry for confusing comment.

[jingyue]

I see. I wasn't involved with the first part, so was confused. Thanks for clarification!

lib/Transforms/InstCombine/InstCombineAddSub.cpp

980 ↗

(On Diff #10627)

If

LHS = w + 1
RHS = ((z & c) ^ c) + 1

the code swaps LHS and RHS and may miss some optimization opportunities.

Maybe instead of premature swapping, we can look deeper into both LHS and RHS. What do you think?

I may be over-concerned, because Reassociate will optimize (a + 1) + (b + 1) to a + (b + 2). I am not sure about the ordering.

998 ↗

(On Diff #10627)

Nit: I prefer

C1->countTrailingZeros() == 0

because C1->countTrailingZeros() is not a boolean.

998 ↗

(On Diff #10627)

Nit: Does LLVM coding standard say anything about:

} else if {

or

}
else if {

The first style seems more commonly used.

1001 ↗

(On Diff #10627)

I doubt using IHasNUW and IHasNSW is correct due to the logic at Line 985-986. The logic there reassociates

I = (x + 1) + ((z & c) ^ c)

into

I' = x + (((z & c) ^ c) + 1)

So, the toplevel "+" in I' may not inherit the NSW/NUW of the toplevel "+" in I.

Essentially, (a + 1) +nsw b != a +nsw (b + 1). Does that make sense to you?

[dinesh.d]

Thanks. I have replied inline. I will update code based on your comment on them.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

980 ↗

(On Diff #10627)

Yes, I think that should be taken care in Reassociate. I think that is the purpose of canonicalization so that we do not have to check of all permutations of inputs. But if
you say, I will change it.

998 ↗

(On Diff #10627)

will update it.

1001 ↗

(On Diff #10627)

code here is changing

I = (x + 1) + ((z & c) ^ c)

to

I = x - (z & c)

I assumed that if first version of I has NUW/ NSW, it is applied to second
version too. I am not shifting those flags from one instruction to other. Basically
this patch is not re-associating anything. It just look for pattern and if found,
transforms I from one form to another.

[dinesh.d]

forgot to reply for else if part.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

998 ↗

(On Diff #10627)

For else if, I have used clang-format on it. But may be because of comments, it left
else in next line. I will move comments after else if line, if you say so.

[jingyue]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

980 ↗

(On Diff #10627)

Can you run -O3 to verify Reassociate does canonicalize such cases before InstCombine? If so, I am fine with the current code. Thanks!

998 ↗

(On Diff #10627)

Please do. Sorry for being a little paranoid :)

1001 ↗

(On Diff #10627)

Although your code doesn't actually reassociate the expression, it does that conceptually.

For example, are you saying it's safe to transform

I = (x + 1) +nsw ((z & c) ^ c)

to

I = x -nsw (z | ~c)

?

Consider all integers are of type i4, and x = 0111, z = 0000, c = 0111. The first version finally computes

1000 + 0111

which does not sign-overflow. However, the second version finally computes

0111 - 1000 = 7 - (-8)

which sign-overflows.

[dinesh.d]

Updated as per comments

[dinesh.d]

Sorry for delay in reply. I have added comments inline.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

980 ↗

(On Diff #10627)

yes, it handled in re-association. For above case, I got following IR at -O3 (with/ without my patch)

%and = and i32 %z, 123
%xor = xor i32 %and, 123
%add1 = add i32 %w, 2

Moreover, checks in my patch will not match in case of above test case as they will match only if
there are only one '+ 1' and one pattern for XOR(AND())

Following code

LHS = ((w & 126) ^ 126) + 1;
RHS = ((z & 123) ^ 123) + 1;

gets transformed to

%and = and i32 %w, 126
%and1 = and i32 %z, 123
%xor2 = xor i32 %and1, 123
%add3 = sub i32 128, %and

i.e. only one patten is transformed. This will be fixed with my next patch, where I am planning to
use current logic to transform SUB instructions as well.

998 ↗

(On Diff #10627)

updated.

1001 ↗

(On Diff #10627)

I still have doubts about this. I think NSW belong to oparator and not operand. for above, example
my patch will not put NSW in '(z | ~c)' or in 'I'.

If we have something like

I = nsw ((x + 1) + ((z & c) ^ c))

then result will be

I = nsw (x - (z | ~c))

My patch does not upadate any flag for (x + 1) or ((z & c) ^ c).
'(z | ~c)' will be new instruction without any flag.

In the Z3 link above, I have proved that ((x + 1) + ((z & c) ^ c)) == (x - (z | ~c))
so if first version of 'I' is overflowing, second will too and if first doen't, neither do
second.

But I am not sure about above logic. If we have to take care of that, there are 2 options

1. to remove code for setting for nsw in instruction after transform, but this may loose nsw and opportunities for further optimization.
2. to add check 'if I has NSW return nullptr' i.e. do not transform in case I has nsw as add nsw is not reassociative.

I am not sure which one is better.

[jingyue]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1001 ↗

(On Diff #10627)

Hi Dinesh,

Sorry for the delay. I feel I need to first confirm my understanding of sign-overflow which may be wrong. I just sent a question to llvmdev.

Thanks,
Jingyue

[dinesh.d]

Removed code setting NSW/ NUW flags

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1001 ↗

(On Diff #10627)

Now I am too not sure about nsw flag here. I am planning to use Z3 to verify code keeping/ setting
NSW/ NUW flags. For now, I am removing code setting these flags from the patch.

I will send another patch once I do understand NSW/ NUW.

[jingyue]

Thanks for working on this! I'm moving on to Part 3.

[dinesh.d]

Thanks :)

[dinesh.d]

Closed by commit rL211765 (authored by dinesh).

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

bool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) {
   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))
-//   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
+ //   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);
 
-  // This function creates 2 instructions to replace ADD, we need at least one 
+   // 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;
 
-  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)))) {
        // 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(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);
+         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");
+         }
        }
      }
    }
 
    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(),
                                   I.hasNoUnsignedWrap(), DL))
      return ReplaceInstUsesWith(I, V);
 
    // (A*B)+(A*C) -> A*(B+C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
     // X + (signbit) --> X ^ signbit
     const APInt &Val = CI->getValue();
     if (Val.isSignBit())
       return BinaryOperator::CreateXor(LHS, RHS);

llvm/trunk/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, 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: ret i32 [[SUB]]
+}
+
+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
+ 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: 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
 }