Page MenuHomePhabricator

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

Authored by aqjune on Wed, Dec 30, 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.Wed, Dec 30, 5:20 AM
aqjune requested review of this revision.Wed, Dec 30, 5:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Dec 30, 5:20 AM
nikic added a comment.Thu, Dec 31, 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.Thu, Dec 31, 1:09 PM

Insert freeze Extra if needed

nikic added a comment.Sun, Jan 3, 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.Tue, Jan 5, 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.