This is an archive of the discontinued LLVM Phabricator instance.

[instcombine] Allow sinking of calls with known writes to uses
ClosedPublic

Authored by reames on Dec 22 2021, 8:06 PM.

Details

Summary

If we have a call whose only side effect is a write to a location which is known to be dead, we can sink said call to the users of the call's result value. This is analogous to the recent changes to delete said calls if unused, but framed as a sinking transform instead.

This is an alternative to (subset of?) D109917. Note that change leaves the nothrow and willreturn requirements in place.

Diff Detail

Event Timeline

reames created this revision.Dec 22 2021, 8:06 PM
reames requested review of this revision.Dec 22 2021, 8:06 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 22 2021, 8:06 PM
reames updated this revision to Diff 395965.EditedDec 22 2021, 8:07 PM

(with the right diff this time)

nikic added a comment.Dec 23 2021, 7:50 AM

The logic here looks correct to me, but I'm still a bit uncomfortable with this addition: The core transform here is that if you have a potentially written pointer argument that is not read after the call, then it is safe to sink it. However, we currently don't have a way to indicate that this argument is not going to be read lateron, so this ends up doing some ad-hoc analysis that involves scanning all alloca users. It will be hard to meaningfully extend this, because we can't (or at least shouldn't) add sophisticated alias analysis to InstCombine. On the other hand, DSE could easily determine this as a matter of course, i.e. mark an argument as dead even if the call cannot be dropped entirely.

That would be more involved though and I don't want perfect to be the enemy of good. Is there an immediate need for this? From D109917 I got the impression that this was added purely for the sake of test coverage, and not because of a performance issue encountered in the wild.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3767 ↗(On Diff #395965)

dyn_cast -> cast

3768 ↗(On Diff #395965)

Should handle AddrSpaceCastInst as well.

reames added a comment.Jan 2 2022, 9:05 AM

The logic here looks correct to me, but I'm still a bit uncomfortable with this addition: The core transform here is that if you have a potentially written pointer argument that is not read after the call, then it is safe to sink it. However, we currently don't have a way to indicate that this argument is not going to be read lateron, so this ends up doing some ad-hoc analysis that involves scanning all alloca users. It will be hard to meaningfully extend this, because we can't (or at least shouldn't) add sophisticated alias analysis to InstCombine. On the other hand, DSE could easily determine this as a matter of course, i.e. mark an argument as dead even if the call cannot be dropped entirely.

I do agree with your point about this being generalizable by DSE, but I want to highlight that the otherwise unused alloca case is an entirely real one. If you have an out-param which is not used in a C/C++ function, this is exactly the form we get.

That would be more involved though and I don't want perfect to be the enemy of good. Is there an immediate need for this? From D109917 I got the impression that this was added purely for the sake of test coverage, and not because of a performance issue encountered in the wild.

The original motivation for discovering the out-param example was test coverage, but the example is real. I haven't tried to quantify how broadly it covers in real code bases, but it's certainly something I have seen in the wild.

Personally, I think this is justified.

I'll also note that while doing non-trivial AA in InstCombine is probably a no-no, a simple use walk and a dominance check is pretty consistent with the existing structure. Doing just that would let us handle out-params which are only read on a success path. That is a very very common idiom. (i.e. picture a multiple condition if chain with one of them being a helper routine with an out-param)

reames updated this revision to Diff 396944.Jan 2 2022, 12:03 PM

Address review comments

anna added inline comments.Jan 2 2022, 6:24 PM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3803 ↗(On Diff #396944)

Just a comment here, I had faced this exact same issue (the current instruction writing to memory) while trying to support allocation sinking, which I alternatively addressed through D114648 by adding an extra condition that this check need not be done for noalias calls.

I like the fact that once this change lands I can do allocation sinking using this recently introduced API of wouldInstructionBeTriviallyDeadOnUnusedPaths. In other words, we will have a usage of the API in upstream, basically what I was aiming for :) .

nikic added inline comments.Jan 3 2022, 1:30 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3740 ↗(On Diff #396944)

nit: Spurious change

3772 ↗(On Diff #396944)

FWIW this could also use getUnderlyingObject() instead, as we don't care that the start of the alloca in particular is passed to the function, having an offset is fine.

3779 ↗(On Diff #396944)

Unless something else already prevents this, I think you need a Visited set here to prevent potential infinite loops in unreachable code with cyclic references.

3790 ↗(On Diff #396944)

Cast to IntrinsicInst isn't necessary here -- isLifetimeStartOrEnd() is actually defined on Instruction.

3790 ↗(On Diff #396944)

This case is also untested. I think something we should check is that

lifetime.start
%x = call
lifetime.end

label:
use %x

doesn't get transformed into

lifetime.start
lifetime.end

label:
%x = call
use %x

I do believe the memory read check below protects against this, as we consider lifetime intrinsics to be reading memory as well.

reames added inline comments.Jan 4 2022, 11:07 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3772 ↗(On Diff #396944)

Without handling for GEP below, underlying object doesn't gain us anything. I was planning on leaving offsets to a follow up patch with separate testing.

3779 ↗(On Diff #396944)

Really good catch!

reames added inline comments.Jan 4 2022, 11:15 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3772 ↗(On Diff #396944)

Ignore this comment. My brain was out of sync with the code, we do have GEP below.

reames updated this revision to Diff 397359.Jan 4 2022, 11:42 AM

Address previous review comments, dropping lifetime end/start to be done in a followup with separate discussion.

reames updated this revision to Diff 397361.Jan 4 2022, 11:47 AM

Rebase over landed tests

reames added inline comments.Jan 4 2022, 12:04 PM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3790 ↗(On Diff #396944)

I landed a test inspired by this in 11a46b1 so that we don't forget it in the follow on. It's annoying much more complicated than it looks as depending on the semantics of lifetime.start/end, this may actually be a valid transform. But let's defer that conversion to that patch. :)

nikic accepted this revision.Jan 5 2022, 5:12 AM

LGTM

This revision is now accepted and ready to land.Jan 5 2022, 5:12 AM
This revision was landed with ongoing or failed builds.Jan 5 2022, 10:37 AM
This revision was automatically updated to reflect the committed changes.

Hi Philip
This seems to break our amdgpu buildbot https://lab.llvm.org/buildbot/#/builders/193/builds/4050

Hi Philip
This seems to break our amdgpu buildbot https://lab.llvm.org/buildbot/#/builders/193/builds/4050

Yeah, yours and pretty much every self host. Should be fixed in 356ada9. Sorry for the breakage.

(I'll add a test separately, just didn't want to delay the fix.)