This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] generalize select + select/and/or folding using implied conditions
ClosedPublic

Authored by aqjune on May 2 2021, 4:19 AM.

Details

Summary

This patch optimizes the remaining possible cases in D101191 by generalizing isImpliedCondition()-based
foldings.

Assume that there is op a, (select b, _, _) where op is one of and i1, or i1 or their select forms.

We can do the following optimization based on the result of isImpliedCondition(a, b):

If a = true implies…

If a = false implies…

Diff Detail

Event Timeline

aqjune created this revision.May 2 2021, 4:19 AM
aqjune requested review of this revision.May 2 2021, 4:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 2 2021, 4:19 AM
nikic added inline comments.May 2 2021, 6:39 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1881

/* IsAnd */ true etc

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

I'm not sure about this assert. Can't you end up with an i1 CondVal, but an <n x i1> SI here?

2628

Don't think we need this.

2757

Missing indent

aqjune updated this revision to Diff 342241.May 2 2021, 7:30 AM

address comments

aqjune updated this revision to Diff 342242.May 2 2021, 7:35 AM
aqjune marked an inline comment as done.

remove assertion

aqjune marked 3 inline comments as done.May 2 2021, 7:36 AM
aqjune updated this revision to Diff 342243.May 2 2021, 7:38 AM

missing /* IsAnd */

nikic added inline comments.May 2 2021, 9:50 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2596

To clarify, I do think you need to check for that case, but as a normal condition, not an assert. You do check this before calling the helper for the and/or case, but I don't think anything ensures it for the case where the root instruction is a select.

Could you please add a test for this kind of scalar/vector mismatch?

aqjune updated this revision to Diff 342350.May 3 2021, 4:07 AM

add vector test

aqjune added inline comments.May 3 2021, 4:10 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2596

I think removing runtime check is fine: isImpliedCondition is handling this case well (simply returning None currently). Also, the created SelectInst does not contain Cond as well.
If isImpliesCondition is enhanced to deal with vector+nonvector ops, this code gets benefit as well.

I added the scalar/vector code mismatch test as well (a_true_implies_b_true_vec).

nikic added inline comments.May 3 2021, 5:16 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2596

Okay, if isImpliedCondition already checks this, then it's fine. In that case, should we also drop the type check when this helper is called for and/or?

aqjune updated this revision to Diff 342387.May 3 2021, 7:49 AM
  • Relax the condition at and/or
  • Add an assertion that Op should be i1 or vec i1
  • Add missing updates in select-safe-bool-transform.ll, revive one deleting code because it caused regression
aqjune added inline comments.May 3 2021, 7:51 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2596

It needed i1 or vec i1 check, but it could be relaxed as suggested, thanks.

nikic accepted this revision.May 3 2021, 11:16 AM

LGTM

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

if (auto *SI0 = dyn_cast<SelectInst>(Op0)) would be more idiomatic, I think.

This revision is now accepted and ready to land.May 3 2021, 11:16 AM
nikic added inline comments.May 3 2021, 1:48 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2615

a = true etc in these comments should be op = true.

nikic added inline comments.May 3 2021, 3:06 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2615

And b = true should be cond = true :)

aqjune updated this revision to Diff 342610.May 3 2021, 5:42 PM

Address comments

aqjune marked 3 inline comments as done.May 3 2021, 5:43 PM
This revision was landed with ongoing or failed builds.May 3 2021, 5:43 PM
This revision was automatically updated to reflect the committed changes.