Page MenuHomePhabricator

Simplify more cases of logical ops of masked icmps.
ClosedPublic

Authored by yamauchi on Feb 27 2018, 2:43 PM.

Details

Summary

For example,

((X & 255) != 0) && ((X & 15) == 8) -> ((X & 15) == 8).
((X & 7) != 0) && ((X & 15) == 8) -> false.

Diff Detail

Repository
rL LLVM

Event Timeline

yamauchi created this revision.Feb 27 2018, 2:43 PM

I found a bug in the first revision. Please hold off reviews. Will update.

yamauchi updated this revision to Diff 136573.Mar 1 2018, 10:33 AM

Fixed bugs in the previous revision.

Ok, ready for reviews.

davidxl added inline comments.Mar 1 2018, 11:07 AM
test/Transforms/InstCombine/icmp-logical.ll
332 ↗(On Diff #136573)

This one should be simplified to x & 15 != 9 // aka 1001

364 ↗(On Diff #136573)

This one should be simplified to x & 15 != 8

430 ↗(On Diff #136573)

perhaps also add a case of (x&6) == 0) || (x&15)!= 8 ==> true

yamauchi updated this revision to Diff 137265.Mar 6 2018, 1:49 PM
yamauchi marked 3 inline comments as done.

Addressed comments.

davidxl added inline comments.Mar 8 2018, 9:02 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
309 ↗(On Diff #137265)

Update the comment since return type changes. Also document parameters LHS, RHS, PredL and PredR.

438 ↗(On Diff #137265)

Document this method with a small example.

444 ↗(On Diff #137265)

&& -> &

448 ↗(On Diff #137265)
->
551 ↗(On Diff #137265)

Add function documentation.

test/Transforms/InstCombine/icmp-logical.ll
204 ↗(On Diff #137265)

x&&15 --> x&15

341 ↗(On Diff #137265)

&& --> &

Similarly, || --> | in other places.

yamauchi updated this revision to Diff 137770.Mar 9 2018, 8:54 AM
yamauchi marked 6 inline comments as done.

Addressed comments.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
448 ↗(On Diff #137265)

What does this comment mean?

yamauchi marked an inline comment as done.Mar 9 2018, 10:37 AM
yamauchi added inline comments.
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
448 ↗(On Diff #137265)

Now I see what you meant. Done. It was formatted as a table :)

davidxl added inline comments.Mar 9 2018, 4:09 PM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
440 ↗(On Diff #137770)

icmp(A&B) ==/!= C

450 ↗(On Diff #137770)

Do you have test case cover this when LSH and RHS are swapped?

(icmp eq (A &D), E) & (icmp ne (A & B, 0))

454 ↗(On Diff #137770)

replace 0 with 'C' in the example.

462 ↗(On Diff #137770)

Do you need to check CCst is Zero?

474 ↗(On Diff #137770)

It seems to me, it is sufficient to do the following check:

  1. check if mask B is a subset of mask D
  2. check if (E & B) != 0 is true

If both 1) and 2) are satisfied, the simplification is legal.

yamauchi marked an inline comment as done.Mar 9 2018, 5:36 PM
yamauchi added inline comments.
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
454 ↗(On Diff #137770)

LHS being of type Mask_NotAllZeroes means that LHS is or can be converted into the form "(icmp ne (A & B), 0)". I think 0 would be better here because the right hand side of the LHS isn't necessarily C. Note the case of Mask_NotAllZeroes where B==C and B is a power of two (see lines 216 and 269 above) where we get "(icmp eq (A & B), C)" (B==C) but interpret it as (equivalent) "(icmp ne (A & B), 0)".

462 ↗(On Diff #137770)

Similarly, C isn't necessarily zero if Mask_NotAllZeroes is due to the case for B==C and B is a power of two. So, no.

474 ↗(On Diff #137770)

I need a clarification on this.

I think the case you are referring to, which is an important one, is covered by lines 552-553 below. But there are several other cases of simplifications below. There are simplifications we can do even when B isn't a subset of D below, eg. (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).

Do you mean we can drop the other cases?

yamauchi updated this revision to Diff 138040.Mar 12 2018, 9:51 AM
yamauchi marked an inline comment as done.

Addressed comments.

yamauchi added inline comments.Mar 12 2018, 9:53 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
450 ↗(On Diff #137770)

Added swapped tests.

davidxl added inline comments.Mar 12 2018, 11:16 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
499 ↗(On Diff #138040)

This check can probably be extended:

  1. B's bitset subtracts the intersection of B and D contains only one bit
  2. B and D's intersection have zero values

In other words, D does not need to be power of 2

530 ↗(On Diff #138040)

Can you introduce a small lambda here to be reused here and other places?

auto IsSubset = [](Value *V1, Value *V2) {

....

};

if (IsSubset(BCst, DCst)) ....

536 ↗(On Diff #138040)

Can you split the comment here for case in line 548 and line 552?

yamauchi updated this revision to Diff 138236.Mar 13 2018, 11:16 AM
yamauchi marked 2 inline comments as done.

Addressed comments.

yamauchi added inline comments.Mar 13 2018, 11:17 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
499 ↗(On Diff #138040)

Is there a chance that those two conditions you are referring to *are* what the current code is already checking here?

To be more specific,

Isn't the condition 1 equivalent to "(B & (B ^ D)).isPowerOf2()" that the current code checks?

(I meant "(B & (B ^ D))" as the bits that are 1 in B but 0 in D.)

For example, suppose B = 1100 and D = 0101. The condition 1 would say 1100 - (1100 & 0101) = 1100 - 0100 = 1000 while (B & (B ^ D)) = (1100 & (1100 ^ 0101)) = (1100 & 1001) = 1000.

Also, isn't the condition 2 equivalent to "((B & D) & E) == 0" that the current code checks?

(Note that in the current code, it's not D, but (B & (B ^ D)) that needs to be a power of 2.)

Do you have an example that isn't handled by the current code but is handled by the suggested extension?

davidxl added inline comments.Mar 13 2018, 11:31 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
499 ↗(On Diff #138040)

You are right. Perhaps add a comment just before the condition to document the semantics of the check.

yamauchi updated this revision to Diff 138250.Mar 13 2018, 12:50 PM
yamauchi marked an inline comment as done.

Addressed comments.

davidxl accepted this revision.Mar 13 2018, 1:11 PM

lgtm

This revision is now accepted and ready to land.Mar 13 2018, 1:11 PM
This revision was automatically updated to reflect the committed changes.