Re: [Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
On Fri, May 10, 2019 at 12:28 PM Rob Clark wrote:
>
> On Fri, May 10, 2019 at 7:43 AM Connor Abbott wrote:
> >
> > On Fri, May 10, 2019 at 11:47 AM Connor Abbott wrote:
> > >
> > >
> > > 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;
> >
> > Whoops, that should actually read:
> >
> > foo = ...
> > if (...) {
> >bar = ...
> >... = bar; /* last use of "bar" */
> > } else {
> >... = foo;
> > }
>
> hmm, my mind is a bit rusty on the live-range analysis, but foo and
> bar do interfere in the if() side of the if/else..
>
> I thought the case we didn't handle properly was more like a loop:
>
> foo = ...
> for (..) {
>bar = foo;
>... stuff .. foo not live here..
>foo = ...
> }
> ... = foo
>
> where we end up considering foo live during the entire body of the
> loop even though it isn't really. I guess it is the same case as:
>
> foo = ...
> if () {
>bar = foo;
>...
>foo = ...
> }
> ... = foo;
>
hmm, maybe I mis-read your example (damn gmail hiding quotes).. I
guess last use of bar is in the else block, so we are saying the same
(or similar) thing?
BR,
-R
> BR,
> -R
>
> >
> > >
> > > 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.
> > >
> > ___
> > mesa-dev mailing list
> > mesa-dev@lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
On Fri, May 10, 2019 at 7:43 AM Connor Abbott wrote:
>
> On Fri, May 10, 2019 at 11:47 AM Connor Abbott wrote:
> >
> >
> > 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;
>
> Whoops, that should actually read:
>
> foo = ...
> if (...) {
>bar = ...
>... = bar; /* last use of "bar" */
> } else {
>... = foo;
> }
hmm, my mind is a bit rusty on the live-range analysis, but foo and
bar do interfere in the if() side of the if/else..
I thought the case we didn't handle properly was more like a loop:
foo = ...
for (..) {
bar = foo;
... stuff .. foo not live here..
foo = ...
}
... = foo
where we end up considering foo live during the entire body of the
loop even though it isn't really. I guess it is the same case as:
foo = ...
if () {
bar = foo;
...
foo = ...
}
... = foo;
BR,
-R
>
> >
> > 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.
> >
> ___
> mesa-dev mailing list
> mesa-dev@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
On Fri, May 10, 2019 at 5:47 AM Connor Abbott wrote:
>
> On Fri, May 10, 2019 at 11:09 AM Christian Gmeiner
> wrote:
> >
> > Signed-off-by: Christian Gmeiner
> > ---
> > 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
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
On Fri, May 10, 2019 at 11:47 AM Connor Abbott wrote:
>
>
> 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;
Whoops, that should actually read:
foo = ...
if (...) {
bar = ...
... = bar; /* last use of "bar" */
} else {
... = 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.
>
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
On Fri, May 10, 2019 at 11:09 AM Christian Gmeiner
wrote:
>
> Signed-off-by: Christian Gmeiner
> ---
> 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.
> };
>
> struct eir_info {
> diff --git a/src/etnaviv/compiler/eir_live_variables.c
> b/src/etnaviv/compiler/eir_live_variables.c
> new file mode 100644
> index 000..fe94e7a2a3d
> --- /dev/null
> +++ b/src/etnaviv/compiler/eir_live_variables.c
> @@ -0,0 +1,258 @@
> +/*
> + * Copyright (c) 2018 Etnaviv Project
> + * Copyright (C) 2018 Zodiac Inflight Innovations
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sub license,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the
> + * next paragraph) shall be included in all copies or substantial portions
> + * of the Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
> + * DEALINGS IN THE SOFTWARE.
> + *
> + * Authors:
> + *Christian Gmeiner
> + */
> +
> +#include "eir.h"
> +#include "util/bitset.h"
> +#include "util/ralloc.h"
> +#include "util/u_math.h"
> +
> +#define MAX_INSTRUCTION (1 << 30)
> +
> +struct block_data {
> + BITSET_WORD *def;
> + BITSET_WORD *use;
> + BITSET_WORD *livein;
> + BITSET_WORD *liveout;
> + int start_ip, end_ip;
> +};
> +
> +/* Returns the variable index
