This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold `(~(a | b) & c) | ~(a | c)` into `~((b & c) | a)`
ClosedPublic

Authored by rampitec on Oct 22 2021, 12:09 PM.

Details

Summary
----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
  %or1 = or i4 %b, %a
  %not1 = xor i4 %or1, -1
  %or2 = or i4 %a, %c
  %not2 = xor i4 %or2, -1
  %and = and i4 %not2, %b
  %or3 = or i4 %and, %not1
  ret i4 %or3
}

define i4 @tgt(i4 %a, i4 %b, i4 %c) {
  %and = and i4 %c, %b
  %or = or i4 %and, %a
  %or3 = xor i4 %or, -1
  ret i4 %or3
}
Transformation seems to be correct!

Diff Detail

Event Timeline

rampitec created this revision.Oct 22 2021, 12:09 PM
rampitec requested review of this revision.Oct 22 2021, 12:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 22 2021, 12:09 PM

Similar feedback as D112276 - more tests needed (8 commutes, extra uses of intermediate values).

rampitec updated this revision to Diff 382130.Oct 25 2021, 2:37 PM

Added more commute and use tests.

Please pre-commit the new tests so we just see the diffs.

spatel added inline comments.Oct 28 2021, 11:26 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2800–2801

This one's a little smaller/easier than the other patch. If we have one-use checks on Op0 (the 'and') and Op1 (the 'not' of RHS), then this transform should be fine. So we don't need the m_OneUse on the inner 'not' here.

llvm/test/Transforms/InstCombine/and-xor-or.ll
1105

Add an instruction to prevent this from commuting.

1110

This is identical to the first test?

1167

Flipped the wrong set of operands? This is effectively the same as "commute2".

The final 'or' doesn't really matter (but it's fine to commute that just to be sure).

1202

Add an instruction to prevent this from commuting.

rampitec updated this revision to Diff 383142.Oct 28 2021, 1:19 PM
rampitec marked 5 inline comments as done.

Addressed review feedback.

llvm/test/Transforms/InstCombine/and-xor-or.ll
1110

It has commuted 'and'. Now since I have added sdiv in the first test these are really different.

1167

This is exactly the test for commuted final 'or', just for completeness.

spatel accepted this revision.Oct 29 2021, 7:35 AM

LGTM.
The commute tests are not complete, but they should be enough to ensure the pattern-matching won't silently break.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
2822

The use checks aren't what I suggested, but either way, it is overly conservative (and we would see improvements on some of the tests that are currently left unchanged), so please put a TODO comment on this block to suggest we can loosen the use checks.

This revision is now accepted and ready to land.Oct 29 2021, 7:35 AM
rampitec updated this revision to Diff 383427.Oct 29 2021, 10:40 AM
rampitec marked an inline comment as done.

Added requested comment.

This revision was landed with ongoing or failed builds.Oct 29 2021, 10:58 AM
This revision was automatically updated to reflect the committed changes.