pan/midgard: Compute liveness per-block

Rather than using a regalloc based on live internals, computed hastily
with repeated invocations of a forward-analysis pass, we switch to
compute liveness information on a per-block basis.

Within a given basic block, we compute liveness backwards with a
linear-time algorithm; for common shaders, this may help RA terminate
quicker.

Across blocks, we use a work list (really a work set) and check if we're
making progress. This isn't terribly efficient, but it gets the job
done. Point is, we get the live_in/live_out for each block.

From there, it's simple to rerun the linear-time update algorithm to
compute the interference graph.

The benefit of this technique is the ability to ignore "gaps" in
liveness across intermediate blocks that are never executed. On simple
shaders like the loops in glmark, this results in a minor reduction in
register pressure. The motivation was a complex shader in Krita that
failed register allocation due to an unfortunate interaction between
texture pipeline registers and control flow. This shader now compiles
successfully.

total instructions in shared programs: 3439 -> 3438 (-0.03%)
instructions in affected programs: 22 -> 21 (-4.55%)
helped: 1
HURT: 0

total bundles in shared programs: 2077 -> 2076 (-0.05%)
bundles in affected programs: 12 -> 11 (-8.33%)
helped: 1
HURT: 0

total quadwords in shared programs: 3457 -> 3456 (-0.03%)
quadwords in affected programs: 20 -> 19 (-5.00%)
helped: 1
HURT: 0

total registers in shared programs: 341 -> 338 (-0.88%)
registers in affected programs: 9 -> 6 (-33.33%)
helped: 3
HURT: 0
helped stats (abs) min: 1 max: 1 x̄: 1.00 x̃: 1
helped stats (rel) min: 33.33% max: 33.33% x̄: 33.33% x̃: 33.33%

Signed-off-by: Alyssa Rosenzweig <[email protected]>

1 files changed, 8 insertions, 0 deletions

diff --git a/src/panfrost/midgard/compiler.h b/src/panfrost/midgard/compiler.h
index 1cbebdbef2e..edf0c105a19 100644
--- a/src/panfrost/midgard/compiler.h
+++ b/src/panfrost/midgard/compiler.h
@@ -184,6 +184,14 @@ typedef struct midgard_block {
          * boolean for passes to use as they see fit, provided they
          * clean up later */
         bool visited;
+
+        /* In liveness analysis, these are live masks (per-component) for
+         * indices for the block. Scalar compilers have the luxury of using
+         * simple bit fields, but for us, liveness is a vector idea. We use
+         * 8-bit to allow finegrained tracking up to vec8. If you're
+         * implementing vec16 on Panfrost... I'm sorry. */
+        uint8_t *live_in;
+        uint8_t *live_out;
 } midgard_block;
 
 typedef struct midgard_bundle {