This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Simplify 'xor'/'add' to 'or' if no common bits are set.
ClosedPublic

Authored by lebedev.ri on Apr 13 2018, 10:42 AM.

Details

Summary

In order to get the whole fold as specified in PR6773,
let's first handle the simple straight-forward things.
Let's start with the xor -> or simplification.

The one obvious thing missing here: the constant mask is not handled.
I have an idea how to handle it, but it will require some thinking,
and is not strictly required here, so i've left that for later.

This haveNoCommonBitsSet() change looks kinda monstrous, i could refactor
it e.g. into "out of these 2 pairs of two values, one of these 4 values is inverted value from another pair" matcher,
but i'm not sure if i should?

https://rise4fun.com/Alive/Pkmg

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.Apr 13 2018, 10:42 AM
lebedev.ri updated this revision to Diff 142471.EditedApr 13 2018, 3:02 PM
lebedev.ri retitled this revision from [InstCombine] Simplify 'xor' to 'or' if no common bits are set. to [InstCombine] Simplify 'xor'/'and' to 'or' if no common bits are set..
lebedev.ri edited the summary of this revision. (Show Details)

Show that add is also handled.

lebedev.ri retitled this revision from [InstCombine] Simplify 'xor'/'and' to 'or' if no common bits are set. to [InstCombine] Simplify 'xor'/'add' to 'or' if no common bits are set..Apr 13 2018, 3:03 PM
spatel added inline comments.Apr 15 2018, 7:54 AM
lib/Analysis/ValueTracking.cpp
200–201

It's probably better to put this check above the computeKnownBits calls because this check is cheap (don't waste time doing recursive work if we can match this case first)

200–203

I think that's logically correct, but it can be coded more simply. All we need to capture is the inverted mask (double-check that this results in the same test changes):

// Look for an inverted mask: (X & Y) op (~X & Z).
Value *X;
if (match(LHS, m_c_And(m_Not(m_Value(X)), m_Value())) &&
    match(RHS, m_c_And(m_Specific(X), m_Value())))
  return true;
if (match(RHS, m_c_And(m_Not(m_Value(X)), m_Value())) &&
    match(LHS, m_c_And(m_Specific(X), m_Value())))
  return true;
lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2449–2452

It's fine to include this in the review, but please make this (and the affected tests) a separate commit. In case there's a problem and/or need to revert, that will make it easier to diagnose the bug.

lebedev.ri marked 3 inline comments as done.

Adjusted based on @spatel review.
Thank you for the review!

lib/Analysis/ValueTracking.cpp
200–201

Right. I was wondering about that, but decided to add it after the existing logic. Will move.

200–203

Thanks, that is more succinct indeed!
Not too good at _c_ommutative matchers yet :/

The original code had full test coverage, and this code does not cause
any changes in tests as compared to my variant, so i *think* it's good.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2449–2452

Yep, sure.
I kinda did not realize that the call visitAnd() would already show
this transform, thus it got into this differential.

spatel accepted this revision.Apr 15 2018, 9:21 AM

LGTM.

Note that for the value tracking improvement, there are a couple of other passes (that I've never looked at) that use haveNoCommonBitsSet(). If it's possible to show a test improvement from this change for those passes, that would be nice.

Also note that SelectionDAG has a twin for llvm::haveNoCommonBitsSet(), so it would be good to add a 'TODO' there about the potential improvement and referencing the IR version of the code. If you have the C++ template skills to unify any of that code, that would be a great maintenance improvement.

This revision is now accepted and ready to land.Apr 15 2018, 9:21 AM

LGTM.

Thank you for the review!

Note that for the value tracking improvement, there are a couple of other passes (that I've never looked at) that use haveNoCommonBitsSet(). If it's possible to show a test improvement from this change for those passes, that would be nice.

There seem to be two other users:

  1. ConstantOffsetExtractor::CanTraceInto(), (llvm/test/CodeGen/AArch64/aarch64-gep-opt.ll, @test-struct_1) That use does not appear to be covered by any tests at all (at least with x86/aarch64 backends). Will add FIXME comment.
  2. StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(), (test/Transforms/StraightLineStrengthReduce/slsr-mul.ll, @or) It requires a value and a constant. So i'm also not sure i can show the effect there...

Also note that SelectionDAG has a twin for llvm::haveNoCommonBitsSet(), so it would be good to add a 'TODO' there about the potential improvement and referencing the IR version of the code.

Sure thing, will do.

If you have the C++ template skills to unify any of that code, that would be a great maintenance improvement.

Interesting, but will require tests, again, so i don't feel confident looking into it right now.

This revision was automatically updated to reflect the committed changes.