Mesa (main): pan/bi: Copy liveness routines back
GitLab Mirror
gitlab-mirror at kemper.freedesktop.org
Sun Jul 18 02:03:17 UTC 2021
Module: Mesa
Branch: main
Commit: a667e1bb6ddaafedcd1db16e1ff520c805338a9c
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=a667e1bb6ddaafedcd1db16e1ff520c805338a9c
Author: Alyssa Rosenzweig <alyssa at collabora.com>
Date: Fri Jul 16 18:18:08 2021 -0400
pan/bi: Copy liveness routines back
We'll diverge shortly.
Signed-off-by: Alyssa Rosenzweig <alyssa at collabora.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/11936>
---
src/panfrost/bifrost/bi_liveness.c | 113 ++++++++++++++++++++++++++++++++++---
1 file changed, 106 insertions(+), 7 deletions(-)
diff --git a/src/panfrost/bifrost/bi_liveness.c b/src/panfrost/bifrost/bi_liveness.c
index 1e4bfcbae3d..9ac03da3e68 100644
--- a/src/panfrost/bifrost/bi_liveness.c
+++ b/src/panfrost/bifrost/bi_liveness.c
@@ -23,6 +23,13 @@
*/
#include "compiler.h"
+#include "util/u_memory.h"
+#include "util/list.h"
+#include "util/set.h"
+
+/* Liveness analysis is a backwards-may dataflow analysis pass. Within a block,
+ * we compute live_out from live_in. The intrablock pass is linear-time. It
+ * returns whether progress was made. */
void
bi_liveness_ins_update(uint16_t *live, bi_instr *ins, unsigned max)
@@ -30,8 +37,10 @@ bi_liveness_ins_update(uint16_t *live, bi_instr *ins, unsigned max)
/* live_in[s] = GEN[s] + (live_out[s] - KILL[s]) */
bi_foreach_dest(ins, d) {
- pan_liveness_kill(live, bi_get_node(ins->dest[d]), max,
- bi_writemask(ins, d));
+ unsigned node = bi_get_node(ins->dest[d]);
+
+ if (node < max)
+ live[node] &= ~bi_writemask(ins, d);
}
bi_foreach_src(ins, src) {
@@ -40,14 +49,58 @@ bi_liveness_ins_update(uint16_t *live, bi_instr *ins, unsigned max)
uint16_t mask = (rmask << ins->src[src].offset);
unsigned node = bi_get_node(ins->src[src]);
- pan_liveness_gen(live, node, max, mask);
+ if (node < max)
+ live[node] |= mask;
}
}
+static bool
+liveness_block_update(pan_block *blk, unsigned temp_count)
+{
+ bool progress = false;
+
+ /* live_out[s] = sum { p in succ[s] } ( live_in[p] ) */
+ pan_foreach_successor(blk, succ) {
+ for (unsigned i = 0; i < temp_count; ++i)
+ blk->live_out[i] |= succ->live_in[i];
+ }
+
+ uint16_t *live = ralloc_array(blk, uint16_t, temp_count);
+ memcpy(live, blk->live_out, temp_count * sizeof(uint16_t));
+
+ pan_foreach_instr_in_block_rev(blk, ins)
+ bi_liveness_ins_update(live, (bi_instr *) ins, temp_count);
+
+ /* To figure out progress, diff live_in */
+
+ for (unsigned i = 0; (i < temp_count) && !progress; ++i)
+ progress |= (blk->live_in[i] != live[i]);
+
+ ralloc_free(blk->live_in);
+ blk->live_in = live;
+
+ return progress;
+}
+
+/* Globally, liveness analysis uses a fixed-point algorithm based on a
+ * worklist. We initialize a work list with the exit block. We iterate the work
+ * list to compute live_in from live_out for each block on the work list,
+ * adding the predecessors of the block to the work list if we made progress.
+ */
+
static void
-bi_liveness_ins_update_wrap(uint16_t *live, void *ins, unsigned max)
+free_liveness(struct list_head *blocks)
{
- bi_liveness_ins_update(live, (bi_instr *) ins, max);
+ list_for_each_entry(pan_block, block, blocks, link) {
+ if (block->live_in)
+ ralloc_free(block->live_in);
+
+ if (block->live_out)
+ ralloc_free(block->live_out);
+
+ block->live_in = NULL;
+ block->live_out = NULL;
+ }
}
void
@@ -56,7 +109,53 @@ bi_compute_liveness(bi_context *ctx)
if (ctx->has_liveness)
return;
- pan_compute_liveness(&ctx->blocks, bi_max_temp(ctx), bi_liveness_ins_update_wrap);
+ unsigned temp_count = bi_max_temp(ctx);
+
+ /* Set of pan_block */
+ struct set *work_list = _mesa_set_create(NULL,
+ _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
+
+ struct set *visited = _mesa_set_create(NULL,
+ _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
+
+ /* Free any previous liveness, and allocate */
+
+ free_liveness(&ctx->blocks);
+
+ list_for_each_entry(pan_block, block, &ctx->blocks, link) {
+ block->live_in = rzalloc_array(block, uint16_t, temp_count);
+ block->live_out = rzalloc_array(block, uint16_t, temp_count);
+ }
+
+ /* Initialize the work list with the exit block */
+ struct set_entry *cur;
+
+ cur = _mesa_set_add(work_list, pan_exit_block(&ctx->blocks));
+
+ /* Iterate the work list */
+
+ do {
+ /* Pop off a block */
+ pan_block *blk = (struct pan_block *) cur->key;
+ _mesa_set_remove(work_list, cur);
+
+ /* Update its liveness information */
+ bool progress = liveness_block_update(blk, temp_count);
+
+ /* If we made progress, we need to process the predecessors */
+
+ if (progress || !_mesa_set_search(visited, blk)) {
+ pan_foreach_predecessor(blk, pred)
+ _mesa_set_add(work_list, pred);
+ }
+
+ _mesa_set_add(visited, blk);
+ } while((cur = _mesa_set_next_entry(work_list, NULL)) != NULL);
+
+ _mesa_set_destroy(visited, NULL);
+ _mesa_set_destroy(work_list, NULL);
ctx->has_liveness = true;
}
@@ -67,7 +166,7 @@ void
bi_invalidate_liveness(bi_context *ctx)
{
if (ctx->has_liveness)
- pan_free_liveness(&ctx->blocks);
+ free_liveness(&ctx->blocks);
ctx->has_liveness = false;
}
More information about the mesa-commit
mailing list