Re: [PATCH] experimental: code sinking

[Linus Torvalds <torvalds@linux-foundation.org>]

On Fri, Dec 4, 2020 at 9:45 AM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> > There might be cases where instruction sinking makes sense even
> > outside the "can we empty this bb entirely" issue. Not that I can
> > think of any, but I wonder if this could be used to actually shrink
> > liveness regions (if both the inputs to the sunk instruction are live
> > _anyway_ at the target, then sinking the instruction should actually
> > improve liveness in general, for example).
>
> I don't think I understand this. In the case of an UNOP, sinking it
> increase the liveness and decrease the liveness of the output, so
> it should not matter much.

Right. The UNOP case should be a no-op from a liveness perspective, but:

> In the case of an BINOP or select, sinking
> it will decrease the liveness of the unique output but increase the
> liveness of the inputs. So, it seems to me that sinking would
> globally increase the liveness (contrary to moving up instructions).
> Am I missing something?

No, moving a binop could actually *shrink* liveness under the right
circumstances - namely when the sources of the binop are live
regardless.

Completely stupid example that makes no sense, and only exists to
illustrate the issue:

    int diff(int x, int y);
    int fn2(int x, int y, int sum, int diff);

    int test(int x, int y)
    {
        int sum = x+y;

        return fn2(x, y, sum, diff(x,y));
    }

which generates

    add.32      %r3 <- %arg1, %arg2
    call.32     %r9 <- fn1, %arg1, %arg2
    call.32     %r10 <- fn2, %arg1, %arg2, %r3, %r9
    ret.32      %r10

but it would actually improve liveness if that "add" was moved down -
because even though it "expands" the liveness of %arg1/arg2 by moving
the use of those down, both of those argument pseudos have later uses
_anyway_. So that expansion of liveness is a non-issue.

Instead, it shrinks the liveness region of %r3. Ergo, it actually
shrinks liveness region in the big picture.

Now, the above stupid example is one single bb, so in that sense it's
not really relevant for your inter-bb movement, but that doesn't
actually change the argument at all. Insert a conditional in there to
get a multi-bb case.

              Linus