[Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass

[Ilia Mirkin]

On Fri, May 10, 2019 at 5:47 AM Connor Abbott <cwabbott0 at gmail.com> wrote:
>
> On Fri, May 10, 2019 at 11:09 AM Christian Gmeiner
> <christian.gmeiner at gmail.com> wrote:
> >
> > Signed-off-by: Christian Gmeiner <christian.gmeiner at gmail.com>
> > ---
> >  src/etnaviv/compiler/eir.h                    |   3 +
> >  src/etnaviv/compiler/eir_live_variables.c     | 258 ++++++++++++++++++
> >  src/etnaviv/compiler/meson.build              |   1 +
> >  .../compiler/tests/eir_live_variables.cpp     | 162 +++++++++++
> >  src/etnaviv/compiler/tests/meson.build        |  11 +
> >  5 files changed, 435 insertions(+)
> >  create mode 100644 src/etnaviv/compiler/eir_live_variables.c
> >  create mode 100644 src/etnaviv/compiler/tests/eir_live_variables.cpp
> >
> > diff --git a/src/etnaviv/compiler/eir.h b/src/etnaviv/compiler/eir.h
> > index a05b12de94b..38c6af4e07e 100644
> > --- a/src/etnaviv/compiler/eir.h
> > +++ b/src/etnaviv/compiler/eir.h
> > @@ -151,6 +151,9 @@ struct eir
> >     /* keep track of number of allocated uniforms */
> >     struct util_dynarray uniform_alloc;
> >     unsigned uniform_offset;
> > +
> > +   /* Live ranges of temp registers */
> > +   int *temp_start, *temp_end;
>
> This way of representing liveness, and then using a coloring register
> allocator, is a common anti-pattern in Mesa, that was initially copied
> from i965 which dates back to before we knew any better. I really
> don't want to see it spread to yet another driver :(.
>
> Representing live ranges like this is imprecise. If I have a program like this:
>
> foo = ...
> if (...) {
>    bar = ...
>    ... = bar; /* last use of "bar" */
> }
> ... = foo;
>
> Then it will say that foo and bar interfere, even when they don't.
>
> Now, this approximation does make things a bit simpler. But, it turns
> out that if you're willing to make it, then the interference graph is
> trivially colorable via a simple linear-time algorithm. This is the
> basis of "linear-scan" register allocators, including the one in LLVM.
> If you want to go down this route, you can, but this hybrid is just
> useless as it gives you the worst of both worlds.
>
> If you want to properly build up the interference graph, it's actually
> not that hard. After doing the inter-basic-block liveness analysis,
> for each block, you initialize a bitset to the live-out bitset. Then
> you walk the block backwards, updating it at each instruction exactly
> as in liveness analysis, so that it always represents the live
> registers before each instruction. Then you add interferences between
> all of the live registers and the register(s) defined at the
> instruction.
>
> One last pitfall I'll mention is that in the real world, you'll also
> need to use reachability. If you have something like
>
> if (...)
>    foo = ... /* only definition of "foo" */
>
> ... = foo;
>
> where foo is only partially defined, then the liveness of foo will
> "leak" through the if. To fix this you need to consider what's called
> "reachability," i.e. something is only live if, in addition to
> potentially being used sometime later, it is reachable (potentially
> defined sometime earlier). Reachability analysis is exactly like
> liveness analysis, but everything is backwards. i965 does this
> properly nowadays, and the change had a huge effect on spilling/RA.

One more word on the reachability thing... watch out for code like

while() {
  use(foo);
  if ()
    foo = bar;
  more code that doesn't use foo
}

In SSA, this becomes like

foo1 = undef
while() {
  foo = phi(foo1, foo2)
  use(foo)
  if ()
    foo2 = bar
  more code that doesn't use foo2
}

And so you have to extend the live range of foo2 until the end of the
loop. This becomes even more fun with various nested control flow
scenarios. (I haven't reviewed whether this series handles this sort
of thing appropriately, but Connor's comment reminded me of it.)

  -ilia