Page MenuHomePhabricator

[InstCombine] Fold unfolded masked merge pattern with variable mask!
Changes PlannedPublic

Authored by lebedev.ri on May 13 2018, 2:36 PM.

Details

Summary

Finally fixes PR6773.

Now that the backend is all done, we can finally fold it!

The canonical unfolded masked merge pattern is

(x &  m) | (y & ~m)

There is a second, equivalent variant:

(x | ~m) & (y |  m)

Only one of them (the or-of-and's i think) is canonical.
And if the mask is not a constant, we should fold it to:

((x ^ y) & M) ^ y

https://rise4fun.com/Alive/ndQw

I have left out the constant handling out here, since i'm not quite sure how to properly handle that.
I can either do Builder.CreateNot(), rely on automatic deduplication, and do pointer comparison.
That will be enough for everything without undef.
But with undef i will need a undef-ignoring comparator (in Constant class?)
Or i could write a more specialized comparator, which specifically checks that one constant is ~another constant.
Suggestions welcomed. Maybe there is already such a thing, and i'm simply not aware of it?

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.May 13 2018, 2:36 PM
spatel added a subscriber: RKSimon.May 15 2018, 8:48 AM

I think we're close on the DAG safety belt (giving @RKSimon some time to look at the x86 tests I think).

...so hold off on this until that lands? Then we'd just convert directly to the xor sequence?

But I am curious - did you find this pattern in real code? I've never seen masked merge using or/nor before.

I think we're close on the DAG safety belt (giving @RKSimon some time to look at the x86 tests I think).

...so hold off on this until that lands?

Sure, can do!

Then we'd just convert directly to the xor sequence?

Yep, the plan is then to extend the matcher from

if (match(&I,
          m_c_And(m_OneUse(m_c_Or(m_Value(X), m_CombineAnd(m_Not(m_Value(M)),
                                                           m_Value(NotM)))),
                  m_OneUse(m_c_Or(m_Value(Y), m_Deferred(M)))))) {

to basically

if (match(&I,
          m_c_And(m_OneUse(m_c_Or(m_Value(X), m_CombineAnd(m_Not(m_Value(M)),
                                                           m_Value(NotM)))),
                  m_OneUse(m_c_Or(m_Value(Y), m_Deferred(M))))) ||
    match(&I,
                m_c_Or(m_OneUse(m_c_And(m_Value(Y), m_CombineAnd(m_Not(m_Value(M)),
                                                                 m_Value(NotM)))),
                       m_OneUse(m_c_And(m_Value(X), m_Deferred(M))))) || ) {

so they both will get folded.

But I am curious - did you find this pattern in real code? I've never seen masked merge using or/nor before.

In real high-level code, i agree i did not see it.
Which makes sense, since nor is not too widely available.

The most important point here is that i'm trying to have the full coverage,
since this is essentially the same pattern, just written differently.
And since it is this rare, it's possible that it is less properly covered by tests and transforms..

But additionally, if we canonicalize the (x | ~C) & (y | C) pattern,
then the haveNoCommonBitsSet() will be more likely to work,
since i'm not quite sure how it handles this odd pattern.

lebedev.ri retitled this revision from [InstCombine] Canonicalize (not fold!) unfolded masked merge pattern. to [InstCombine] Fold unfolded masked merge pattern with variable mask!.
lebedev.ri edited the summary of this revision. (Show Details)

Now that the backend is all done, we can finally fold it!

nicholas added inline comments.
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2436 ↗(On Diff #147893)

Typo "equivalend" -> "equivalent".

2438 ↗(On Diff #147893)

This line looks cut short?

2439 ↗(On Diff #147893)

I think the period after "constant" can be removed? (Otherwise, it should be a comma, or "we" should be capitalised.)

lebedev.ri marked 3 inline comments as done.

Fix typos in comments.

spatel accepted this revision.May 23 2018, 7:05 AM

LGTM - see inline for a possible improvement on the code comment.

Thanks for seeing this through!

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2434–2439 ↗(On Diff #147897)

I'd reword this because I suspect nobody is going to understand/remember the distinction between 'unfolded', 'folded', and 'canonical':

/// Bitwise masked merge (bitwise select) is typically coded as:
/// (x & m) | (y & ~m)
/// Another variant is:
/// (x | ~m) | (y | m)
/// Canonicalize those to a form with one less IR instruction:
/// ((x ^ y) & m) ^ y
This revision is now accepted and ready to land.May 23 2018, 7:05 AM
spatel added inline comments.May 23 2018, 7:07 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2434–2439 ↗(On Diff #147897)

Oops - typo'd the formula:

//// (x | ~m) & (y | m)

lebedev.ri added inline comments.May 23 2018, 7:08 AM
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2434–2439 ↗(On Diff #147897)

(You obviously meant /// (x | ~m) & (y | m))

LGTM - see inline for a possible improvement on the code comment.

Thanks for seeing this through!

Thank you for all the reviews!

This revision was automatically updated to reflect the committed changes.
lebedev.ri reopened this revision.May 30 2018, 11:09 PM

Reverted in rL333631.
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20180528/556578.html

At least, the (x | ~m) & (y | m) -> (x & m) | (y & ~m) part should be able to go back in later.

This revision is now accepted and ready to land.May 30 2018, 11:09 PM
lebedev.ri planned changes to this revision.Jun 20 2018, 1:42 AM

Depends on D29011.