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

[reames]

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.

[reames]

(with the right diff this time)

[nikic]

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]

In D116200#3208032, @nikic wrote:

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]

Address review comments

[anna]

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]

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]

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]

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]

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

[reames]

Rebase over landed tests

[reames]

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]

LGTM

[ronlieb]

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

[reames]

In D116200#3223025, @ronlieb wrote:

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

llvm/docs/HowToAddABuilder.rst

 #. Create a designated user account, your buildbot-worker will be running under,
    and set appropriate permissions.
 
 #. Choose the buildbot-worker root directory (all builds will be placed under
    it), buildbot-worker access name and password the build master will be using
    to authenticate your buildbot-worker.
 
 #. Create a buildbot-worker in context of that buildbot-worker account. Point it
-   to the **lab.llvm.org** port **9990** (see `Buildbot documentation,
+   to the **lab.llvm.org** port **9994** (see `Buildbot documentation,
    Creating a worker
    <http://docs.buildbot.net/current/tutorial/firstrun.html#creating-a-worker>`_
    for more details) by running the following command:
 
     .. code-block:: bash
 
        $ buildbot-worker create-worker <buildbot-worker-root-directory> \
-                    lab.llvm.org:9990 \
+                    lab.llvm.org:9994 \
                     <buildbot-worker-access-name> \
                     <buildbot-worker-access-password>
 
-   To point a worker to silent master please use lab.llvm.org:9994 instead
-   of lab.llvm.org:9990.
+   This will cause your new worker to connect to the staging buildmaster
+   which is silent by default.  Only once a new worker is stable, and
+   approval from Galina has been received (see last step) should it
+   be pointed at the main buildmaster.
 
 #. Fill the buildbot-worker description and admin name/e-mail.  Here is an
    example of the buildbot-worker description::
 
        Windows 7 x64
        Core i7 (2.66GHz), 16GB of RAM
 
        g++.exe (TDM-1 mingw32) 4.4.0
#. Send a patch which adds your build worker and your builder to
    This is particularly useful for the staging buildmaster which is silent
    otherwise.
 
 #. Send the buildbot-worker access name and the access password directly to
    `Galina Kistanova <mailto:[e-mail]>`_, and wait till she
    will let you know that your changes are applied and buildmaster is
    reconfigured.
 
-#. Check the status of your buildbot-worker on the `Waterfall Display
-   <http://lab.llvm.org/buildbot/#/waterfall>`_ to make sure it is connected,
-   and the `Workers Display <http://lab.llvm.org/buildbot/#/workers>`_ to see if
-   administrator contact and worker information are correct.
-
-#. Wait for the first build to succeed and enjoy.
-
+#. Check the status of your buildbot-worker on the `Waterfall Display (Staging)
+   <http://lab.llvm.org/staging/#/waterfall>`_ to make sure it is
+   connected, and the `Workers Display (Staging)
+   <http://lab.llvm.org/staging/#/workers>`_ to see if administrator
+   contact and worker information are correct.
+
+#. At this point, you have a working builder connected to the staging
+   buildmaster.  You can now make sure it is reliably green and keeps
+   up with the build queue.  No notifications will be sent, so you can
+   keep an unstable builder connected to staging indefinitely.
+
+#. (Optional) Once the builder is stable on the staging buildmaster with
+   several days of green history, you can chose to move it to the production
+   buildmaster to enable developer notifications.  Please email `Galina
+   Kistanova <mailto:[e-mail]>`_ for review and approval.
+
+   To move a worker to production (once approved), stop your worker, edit the
+   buildbot.tac file to change the port number from 9994 to 9990 and start it
+   again.
 
 Best Practices for Configuring a Fast Builder
 =============================================
 
 As mentioned above, we generally have a strong preference for
 builders which can build every commit as they come in.  This section
 includes best practices and some recommendations as to how to achieve
 that end.