Page MenuHomePhabricator

[SimplifyCFG] Update SimplifyBranchOnICmpChain to recognize select form of and/or
ClosedPublic

Authored by aqjune on Dec 30 2020, 5:20 AM.

Details

Summary

This patch teaches SimplifyCFG::SimplifyBranchOnICmpChain to understand select form of
(x == C1 || x == C2 || ...) / (x != C1 && x != C2 && ...) and optimize them into switch if possible.
D93065 has more context about the transition, including links to the list of optimizations being updated.

Diff Detail

Event Timeline

aqjune created this revision.Dec 30 2020, 5:20 AM
aqjune requested review of this revision.Dec 30 2020, 5:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 30 2020, 5:20 AM
nikic added a comment.Dec 31 2020, 2:46 AM

I think this may not be correct if there is an ExtraCase. ExtraCase || X == C || ... should be fine as it is converted into if (!ExtraCase) goto; switch (X), but something like ... || X == C || ExtraCase would not be fine.

I think this may not be correct if there is an ExtraCase. ExtraCase || X == C || ... should be fine as it is converted into if (!ExtraCase) goto; switch (X), but something like ... || X == C || ExtraCase would not be fine.

You're right. Actually, while updating test/Transforms/SimplifyCFG/switch_create.ll I realized this and maybe I wanted to think that it wasn't very important, *but* that's not the right direction. I'll update this patch.

aqjune updated this revision to Diff 314202.Dec 31 2020, 1:09 PM

Insert freeze Extra if needed

nikic added a comment.Jan 3 2021, 12:30 PM

I think this may not be correct if there is an ExtraCase. ExtraCase || X == C || ... should be fine as it is converted into if (!ExtraCase) goto; switch (X), but something like ... || X == C || ExtraCase would not be fine.

You're right. Actually, while updating test/Transforms/SimplifyCFG/switch_create.ll I realized this and maybe I wanted to think that it wasn't very important, *but* that's not the right direction. I'll update this patch.

Thinking about this again, don't we need to always freeze the extra condition (unless known non-undef/poison)? While poison is only a problem when converting the select form into a branch, doesn't undef need to be frozen even in the and/or form? As the other operand may make it unconditionally true/false and thus well-defined.

In that case, I think we should either always insert the freeze, or not inserted it in the select form either (your original patch) with a FIXME for the more general problem.

aqjune added a comment.Jan 5 2021, 7:19 PM

Thinking about this again, don't we need to always freeze the extra condition (unless known non-undef/poison)? While poison is only a problem when converting the select form into a branch, doesn't undef need to be frozen even in the and/or form? As the other operand may make it unconditionally true/false and thus well-defined.

In that case, I think we should either always insert the freeze, or not inserted it in the select form either (your original patch) with a FIXME for the more general problem.

I'm fine with either direction. I'll update this to uninsert freeze and leave FIXME.

aqjune updated this revision to Diff 317263.Jan 17 2021, 8:51 PM

Uninsert freeze
I'll make a separate patch that inserts freeze to ExtraCase

nikic accepted this revision.Jan 18 2021, 9:35 AM

LGTM

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
720

This assert seems a bit redundant to me (possibly leftover from previous implementation)?

This revision is now accepted and ready to land.Jan 18 2021, 9:35 AM
aqjune updated this revision to Diff 317428.Jan 18 2021, 3:54 PM

Remove the redundant assertion

This revision was landed with ongoing or failed builds.Jan 18 2021, 3:54 PM
This revision was automatically updated to reflect the committed changes.
aqjune marked an inline comment as done.Jan 18 2021, 3:54 PM