Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

[InstCombine] Fold two select patterns into or-and
ClosedPublic

Authored by dtcxzyw on Mon, Aug 28, 6:26 AM.

Details

Summary

This patch is the follow-up improvement of D122152.
Fixes https://github.com/llvm/llvm-project/issues/64558.

select (a | c), a, b -> select a, true, (select ~c, b, false) where c is free to invert
select (c & ~b), a, b -> select b, true, (select c, a, false)
Alive2: https://alive2.llvm.org/ce/z/KwxtMA

Diff Detail

Event Timeline

dtcxzyw created this revision.Mon, Aug 28, 6:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Aug 28, 6:26 AM
dtcxzyw requested review of this revision.Mon, Aug 28, 6:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Aug 28, 6:26 AM
nikic requested changes to this revision.Mon, Aug 28, 6:46 AM

The correct transforms are these: https://alive2.llvm.org/ce/z/K8cuab

This revision now requires changes to proceed.Mon, Aug 28, 6:46 AM
dtcxzyw updated this revision to Diff 553918.Mon, Aug 28, 7:08 AM
dtcxzyw edited the summary of this revision. (Show Details)

Fix the transformation.

I will fix D122152 in a separate patch.

nikic added inline comments.Mon, Aug 28, 7:30 AM
llvm/test/Transforms/InstCombine/select-and-or.ll
629

noundef on b seems irrelevant, did you mean to put it on a?

653

Drop noundef from these tests and call them _multiuse.

697

Is this supposed to be a commuted test? If so, put it next to the original test and make it _commuted.

711

Something is wrong with these negative tests. You have an unused variable %a.

dtcxzyw added inline comments.Mon, Aug 28, 7:39 AM
llvm/test/Transforms/InstCombine/select-and-or.ll
629

These tests are based on and_or* series above.

dtcxzyw updated this revision to Diff 553932.Mon, Aug 28, 7:49 AM

Cleanup tests.

dtcxzyw marked 3 inline comments as done.Mon, Aug 28, 7:50 AM
dtcxzyw marked an inline comment as done.Mon, Aug 28, 7:52 AM
dtcxzyw added inline comments.
llvm/test/Transforms/InstCombine/select-and-or.ll
697

I don't think commuted tests are necessary.

dtcxzyw marked an inline comment as done.Mon, Aug 28, 7:52 AM
nikic added inline comments.Mon, Aug 28, 7:54 AM
llvm/test/Transforms/InstCombine/select-and-or.ll
682

Swap the operand of the or here to cover the commuted case.

711

We do still need negative tests where the not operand is not the same as the other select operand. The previous test had the right idea, it just didn't use the correct variables. It should be something like this:

define i1 @or_and1_wrong_operand(i1 %a, i1 %b, i1 %c, i1 %c) {
  %notb = xor i1 %b, true
  %cond = and i1 %notb, %c
  %r = select i1 %cond, i1 %a, i1 %d
  ret i1 %r
}

And similar for the other case.

dtcxzyw updated this revision to Diff 553945.Mon, Aug 28, 8:11 AM

Add commuted tests and negative tests.

dtcxzyw marked 2 inline comments as done.Mon, Aug 28, 8:12 AM
goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
3093

Instead of matching m_Not imo should match m_Specific and then check isFreeToInvert and generate CreateNot if that is the case.

This looks reasonable to me, can you pleas precommit the tests?

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
3093

I don't get what you're suggesting here. isFreeToInvert doesn't tell you how inverted values are related, which is important here. (We need ~b and b, just being invertible is not enough.)

goldstein.w.n added inline comments.Mon, Aug 28, 7:29 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
3093

err doesn't work for the FalseVal one, but for the true case you can do:
match(CondVal, m_c_Or(m_Specific(TrueVal), m_Value(C)) && CondVal->hasOneUse() && IsFreeToInvert(C) { C = Builder.CreateNot(C); ...}. That gets more patterns.

nikic added a comment.Tue, Aug 29, 3:18 AM

FYI I slightly adjusted the test coverage in https://github.com/llvm/llvm-project/commit/5f9b4bc293c26d93c9115c5fbe99ddc4e5fab6da to make sure the operand order is right.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
3093

Thanks, I get what you mean now. That should indeed work for the first case.

dtcxzyw updated this revision to Diff 554291.Tue, Aug 29, 6:26 AM
dtcxzyw edited the summary of this revision. (Show Details)
dtcxzyw added a reviewer: goldstein.w.n.
  • Rebase
  • Fold select (a | c), a, b -> select a, true, (select ~c, b, false) where c is free to invert.
  • Add more tests for the generalized transform
dtcxzyw marked 4 inline comments as done.Tue, Aug 29, 6:26 AM
nikic accepted this revision.Tue, Aug 29, 7:22 AM

LGTM

This revision is now accepted and ready to land.Tue, Aug 29, 7:22 AM
This revision was landed with ongoing or failed builds.Tue, Aug 29, 9:58 AM
This revision was automatically updated to reflect the committed changes.