Page MenuHomePhabricator

[Codegenprepare] Use IV increment instead of IV if we can prove it is not a poisoned value

Authored by mkazantsev on Feb 26 2021, 3:02 AM.



We restrained from replacing uses of IV with if is potentially poison.
This patch loosens this restricton for one important particular case: memory instruction
is dominated by loop exit by condition icmp, X. In this case we can safely assume
that, whenever is poison, we exit the loop at this point. So only non-poisoned
values may reach the memory instruction.

Note that this transform reduces overlap of live ranges of IV and, so potentially it
can lead to better opt decisions overall.

Diff Detail

Event Timeline

mkazantsev created this revision.Feb 26 2021, 3:02 AM
mkazantsev requested review of this revision.Feb 26 2021, 3:02 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 26 2021, 3:02 AM
reames requested changes to this revision.Mar 3 2021, 4:10 PM
reames added inline comments.

The code that follows looks analogous to programUndefinedIfPoison from ValueTracking.hpp. (Though you handle slightly different cases.) I'd encourage you to split this into a helper function and use analogous naming conventions to make it easier to follow.

Side note - I'd suggest trying the existing implementation from ValueTracking. While the reason is definitely different, if that's enough to catch your interesting cases, you can save a bunch of work. :)


Detail on the proof here -- the fact the branch is a loop exit is definitely irrelevant.

It's not clear to me whether branching on poison is immediate UB. LangRef seems to say "yes", but the code in ValueTracking seems to say "no". We need to draw in the experts here. (Juneyoung)

This revision now requires changes to proceed.Mar 3 2021, 4:10 PM
spatel added inline comments.

cc @aqjune @lebedev.ri @nikic for branch-on-poison question.

nikic added inline comments.Mar 4 2021, 5:42 AM

See D92739. Branch on poison is UB, but we're currently being conservative about it due to some known bugs (imho to our detriment).

aqjune added inline comments.Mar 4 2021, 7:55 AM

Yes, branching on poison is immediate UB, but it isn't listed in getGuaranteedWellDefinedOps (which is called by programUndefinedIfPoison). It's because there are a few known transformations that are poison-unsafe but still exist, and adding the case to getGuaranteedWellDefinedOps globally impacts optimizations, increasing opportunities for miscompilation bug.

The two most frequently happening (mis)transformations are short circuiting in SimplifyCFG (D95026) and select i1 -> and/or i1 in InstCombine (D93840). And then, there are a few optimizations that require either freeze or other workarounds, but they happen less frequently and fixing them is expected to have smaller performance impact.

For the SimplifyCFG patch: I believe it is almost there; combined with the enhancement in loop unswitch (which is mentioned in the patch) its impact is relatively small, as its asmdiff for llvm-testsuite result mentioned in its comments.
It would be great if the patches could be reviewed and get in. :)

For the select -> and/or InstCombine opt: its fix is hidden under a flag, but I and people have already written many patches to resolve possible regressions (D93065 has links).

reames added inline comments.Mar 4 2021, 9:52 AM

@aqjune Given the proposed use case here is CGP, which is well after the specific mid-level optimizer cases you mention, what is your take on the practicality of using branching on poison as immediate UB here? I'm tempted to say we should go ahead, but you're much more current with the practical status and tradeoffs than I am.

aqjune added inline comments.Mar 4 2021, 9:30 PM

Since this transformation is correct and does not globally affect others, I think this is fine.
I remember there was no poison-unsafe transformation in CodeGenPrepare (there were a few in the past, but finally fixed). Also, CodeGenPrepare does not use or update SCEV, which is the analysis that was mainly impacted by getGuaranteedWellDefinedOps's branch-poison change.

mkazantsev abandoned this revision.Apr 19 2021, 8:33 AM