Page MenuHomePhabricator

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

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

Details

Summary

We restrained from replacing uses of IV with IV.next if IV.next is potentially poison.
This patch loosens this restricton for one important particular case: memory instruction
is dominated by loop exit by condition icmp iV.next, X. In this case we can safely assume
that, whenever IV.next 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 IV.next, 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.
llvm/lib/CodeGen/CodeGenPrepare.cpp
3860

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. :)

3874

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.
llvm/lib/CodeGen/CodeGenPrepare.cpp
3874

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

nikic added inline comments.Mar 4 2021, 5:42 AM
llvm/lib/CodeGen/CodeGenPrepare.cpp
3874

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
llvm/lib/CodeGen/CodeGenPrepare.cpp
3874

Hi,
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
llvm/lib/CodeGen/CodeGenPrepare.cpp
3874

@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
llvm/lib/CodeGen/CodeGenPrepare.cpp
3874

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