On Fri, May 10, 2019 at 11:47 AM Connor Abbott <cwabbo...@gmail.com> 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