Page MenuHomePhabricator

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

Authored by dinesh.d on Jun 19 2014, 5:02 AM.

Details

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

Diff Detail

Repository
rL LLVM

Event Timeline

dinesh.d updated this revision to Diff 10627.Jun 19 2014, 5:02 AM
dinesh.d retitled this revision from to Added instruction combine to transform few more negative values addition to subtraction (Part 2).
dinesh.d updated this object.
dinesh.d edited the test plan for this revision. (Show Details)
dinesh.d added a subscriber: Unknown Object (MLST).
jingyue edited edge metadata.Jun 19 2014, 9:59 PM

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

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.

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?

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.

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 added inline comments.Jun 20 2014, 10:18 PM
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 this revision to Diff 10739.Jun 23 2014, 1:25 AM
dinesh.d updated this object.
dinesh.d edited edge metadata.

Updated as per comments

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 added inline comments.Jun 24 2014, 9:51 PM
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 updated this revision to Diff 10819.Jun 24 2014, 11:39 PM

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 accepted this revision.Jun 25 2014, 11:45 AM
jingyue edited edge metadata.

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

This revision is now accepted and ready to land.Jun 25 2014, 11:45 AM
dinesh.d closed this revision.Jun 25 2014, 10:48 PM
dinesh.d updated this revision to Diff 10877.

Closed by commit rL211765 (authored by dinesh).