Mesa (main): pan/bi: Use bi_worklist for liveness

[GitLab Mirror]

Module: Mesa
Branch: main
Commit: 9ca625cf24b805507c8dce3154c3ddcb06aee206
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=9ca625cf24b805507c8dce3154c3ddcb06aee206

Author: Alyssa Rosenzweig <alyssa at collabora.com>
Date:   Tue Apr 19 14:04:20 2022 -0400

pan/bi: Use bi_worklist for liveness

Signed-off-by: Alyssa Rosenzweig <alyssa at collabora.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/16279>

---

 src/panfrost/bifrost/bi_liveness.c | 45 ++++++++++++--------------------------
 1 file changed, 14 insertions(+), 31 deletions(-)

diff --git a/src/panfrost/bifrost/bi_liveness.c b/src/panfrost/bifrost/bi_liveness.c
index 493b06d4ae8..069ceff88b3 100644
--- a/src/panfrost/bifrost/bi_liveness.c
+++ b/src/panfrost/bifrost/bi_liveness.c
@@ -96,14 +96,8 @@ bi_compute_liveness(bi_context *ctx)
 
         unsigned temp_count = bi_max_temp(ctx);
 
-        /* Set of bi_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);
+        u_worklist worklist;
+        bi_worklist_init(ctx, &worklist);
 
         bi_foreach_block(ctx, block) {
                 if (block->live_in)
@@ -114,35 +108,24 @@ bi_compute_liveness(bi_context *ctx)
 
                 block->live_in = rzalloc_array(block, uint8_t, temp_count);
                 block->live_out = rzalloc_array(block, uint8_t, temp_count);
-        }
-
-        /* Initialize the work list with the exit block */
-        struct set_entry *cur;
-
-        cur = _mesa_set_add(work_list, bi_exit_block(&ctx->blocks));
-
-        /* Iterate the work list */
 
-        do {
-                /* Pop off a block */
-                bi_block *blk = (struct bi_block *) cur->key;
-                _mesa_set_remove(work_list, cur);
-
-                /* Update its liveness information */
-                bool progress = liveness_block_update(blk, temp_count);
+                bi_worklist_push_tail(&worklist, block);
+        }
 
-                /* If we made progress, we need to process the predecessors */
+        while (!u_worklist_is_empty(&worklist)) {
+                /* Pop off in reverse order since liveness is backwards */
+                bi_block *blk = bi_worklist_pop_tail(&worklist);
 
-                if (progress || !_mesa_set_search(visited, blk)) {
+                /* Update liveness information. If we made progress, we need to
+                 * reprocess the predecessors
+                 */
+                if (liveness_block_update(blk, temp_count)) {
                         bi_foreach_predecessor(blk, pred)
-                                _mesa_set_add(work_list, pred);
+                                bi_worklist_push_head(&worklist, 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);
+        u_worklist_fini(&worklist);
 
         ctx->has_liveness = true;
 }