From 933e44dd435f285e652d29389456dbafca121482 Mon Sep 17 00:00:00 2001 From: Alyssa Rosenzweig Date: Wed, 11 Mar 2020 13:58:10 -0400 Subject: [PATCH] panfrost: Move liveness analysis to root panfrost/ This way we can share the code with Bifrost. Signed-off-by: Alyssa Rosenzweig Part-of: --- src/panfrost/midgard/compiler.h | 56 -------- src/panfrost/midgard/midgard_liveness.c | 141 ++----------------- src/panfrost/util/meson.build | 1 + src/panfrost/util/pan_ir.h | 60 ++++++++ src/panfrost/util/pan_liveness.c | 180 ++++++++++++++++++++++++ 5 files changed, 249 insertions(+), 189 deletions(-) create mode 100644 src/panfrost/util/pan_liveness.c diff --git a/src/panfrost/midgard/compiler.h b/src/panfrost/midgard/compiler.h index f9b0c8c2198..34a53cd1ac3 100644 --- a/src/panfrost/midgard/compiler.h +++ b/src/panfrost/midgard/compiler.h @@ -165,29 +165,6 @@ typedef struct midgard_instruction { }; } midgard_instruction; -typedef struct pan_block { - /* Link to next block. Must be first for mir_get_block */ - struct list_head link; - - /* List of instructions emitted for the current block */ - struct list_head instructions; - - /* Index of the block in source order */ - unsigned name; - - /* Control flow graph */ - struct pan_block *successors[2]; - unsigned nr_successors; - - struct set *predecessors; - - /* 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. */ - uint16_t *live_in; - uint16_t *live_out; -} pan_block; - typedef struct midgard_block { pan_block base; @@ -377,9 +354,6 @@ mir_next_op(struct midgard_instruction *ins) #define mir_foreach_instr_in_block_rev(block, v) \ list_for_each_entry_rev(struct midgard_instruction, v, &block->base.instructions, link) -#define pan_foreach_instr_in_block_rev(block, v) \ - list_for_each_entry_rev(struct midgard_instruction, v, &block->instructions, link) - #define mir_foreach_instr_in_block_safe(block, v) \ list_for_each_entry_safe(struct midgard_instruction, v, &block->base.instructions, link) @@ -422,14 +396,6 @@ mir_next_op(struct midgard_instruction *ins) v != NULL && _v < &blk->base.successors[2]; \ _v++, v = *_v) \ -#define pan_foreach_successor(blk, v) \ - pan_block *v; \ - pan_block **_v; \ - for (_v = (pan_block **) &blk->successors[0], \ - v = *_v; \ - v != NULL && _v < (pan_block **) &blk->successors[2]; \ - _v++, v = *_v) \ - /* Based on set_foreach, expanded with automatic type casts */ #define mir_foreach_predecessor(blk, v) \ @@ -441,15 +407,6 @@ mir_next_op(struct midgard_instruction *ins) _entry_##v = _mesa_set_next_entry(blk->base.predecessors, _entry_##v), \ v = (struct midgard_block *) (_entry_##v ? _entry_##v->key : NULL)) -#define pan_foreach_predecessor(blk, v) \ - struct set_entry *_entry_##v; \ - struct pan_block *v; \ - for (_entry_##v = _mesa_set_next_entry(blk->predecessors, NULL), \ - v = (struct pan_block *) (_entry_##v ? _entry_##v->key : NULL); \ - _entry_##v != NULL; \ - _entry_##v = _mesa_set_next_entry(blk->predecessors, _entry_##v), \ - v = (struct pan_block *) (_entry_##v ? _entry_##v->key : NULL)) - #define mir_foreach_src(ins, v) \ for (unsigned v = 0; v < ARRAY_SIZE(ins->src); ++v) @@ -470,19 +427,6 @@ mir_get_block(compiler_context *ctx, int idx) return (struct midgard_block *) lst; } -static inline midgard_block * -mir_exit_block(struct compiler_context *ctx) -{ - pan_block *last = list_last_entry(&ctx->blocks, pan_block, link); - - /* The last block must be empty logically but contains branch writeout - * for fragment shaders */ - - assert(last->nr_successors == 0); - - return (midgard_block *) last; -} - static inline bool mir_is_alu_bundle(midgard_bundle *bundle) { diff --git a/src/panfrost/midgard/midgard_liveness.c b/src/panfrost/midgard/midgard_liveness.c index 9481cded56a..af7fba9939c 100644 --- a/src/panfrost/midgard/midgard_liveness.c +++ b/src/panfrost/midgard/midgard_liveness.c @@ -22,99 +22,28 @@ */ #include "compiler.h" -#include "util/u_memory.h" - -/* Routines for liveness analysis. Liveness is tracked per byte per node. Per - * byte granularity is necessary for proper handling of int8 */ - -static void -liveness_gen(uint16_t *live, unsigned node, unsigned max, uint16_t mask) -{ - if (node >= max) - return; - - live[node] |= mask; -} - -static void -liveness_kill(uint16_t *live, unsigned node, unsigned max, uint16_t mask) -{ - if (node >= max) - return; - - live[node] &= ~mask; -} - -static bool -liveness_get(uint16_t *live, unsigned node, uint16_t max) { - if (node >= max) - return false; - - return live[node]; -} - -/* Updates live_in for a single instruction */ void mir_liveness_ins_update(uint16_t *live, midgard_instruction *ins, unsigned max) { /* live_in[s] = GEN[s] + (live_out[s] - KILL[s]) */ - liveness_kill(live, ins->dest, max, mir_bytemask(ins)); + pan_liveness_kill(live, ins->dest, max, mir_bytemask(ins)); mir_foreach_src(ins, src) { unsigned node = ins->src[src]; unsigned bytemask = mir_bytemask_of_read_components(ins, node); - liveness_gen(live, node, max, bytemask); + pan_liveness_gen(live, node, max, bytemask); } } -/* live_out[s] = sum { p in succ[s] } ( live_in[p] ) */ - static void -liveness_block_live_out(pan_block *blk, unsigned temp_count) +mir_liveness_ins_update_wrap(uint16_t *live, void *ins, unsigned max) { - pan_foreach_successor(blk, succ) { - for (unsigned i = 0; i < temp_count; ++i) - blk->live_out[i] |= succ->live_in[i]; - } + mir_liveness_ins_update(live, (midgard_instruction *) ins, max); } -/* 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. */ - -static bool -liveness_block_update(pan_block *blk, unsigned temp_count) -{ - bool progress = false; - - liveness_block_live_out(blk, temp_count); - - 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) - mir_liveness_ins_update(live, 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. - */ - void mir_compute_liveness(compiler_context *ctx) { @@ -123,52 +52,7 @@ mir_compute_liveness(compiler_context *ctx) return; mir_compute_temp_count(ctx); - unsigned temp_count = ctx->temp_count; - - /* List of midgard_block */ - struct set *work_list = _mesa_set_create(ctx, - _mesa_hash_pointer, - _mesa_key_pointer_equal); - - struct set *visited = _mesa_set_create(ctx, - _mesa_hash_pointer, - _mesa_key_pointer_equal); - - /* Allocate */ - - mir_foreach_block(ctx, block) { - block->live_in = rzalloc_array(NULL, uint16_t, temp_count); - block->live_out = rzalloc_array(NULL, uint16_t, temp_count); - } - - /* Initialize the work list with the exit block */ - struct set_entry *cur; - - midgard_block *exit = mir_exit_block(ctx); - cur = _mesa_set_add(work_list, exit); - - /* 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); + pan_compute_liveness(&ctx->blocks, ctx->temp_count, mir_liveness_ins_update_wrap); /* Liveness is now valid */ ctx->metadata |= MIDGARD_METADATA_LIVENESS; @@ -183,19 +67,10 @@ mir_invalidate_liveness(compiler_context *ctx) if (!(ctx->metadata & MIDGARD_METADATA_LIVENESS)) return; + pan_free_liveness(&ctx->blocks); + /* It's now invalid regardless */ ctx->metadata &= ~MIDGARD_METADATA_LIVENESS; - - mir_foreach_block(ctx, block) { - 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; - } } bool @@ -205,7 +80,7 @@ mir_is_live_after(compiler_context *ctx, midgard_block *block, midgard_instructi /* Check whether we're live in the successors */ - if (liveness_get(block->base.live_out, src, ctx->temp_count)) + if (pan_liveness_get(block->base.live_out, src, ctx->temp_count)) return true; /* Check the rest of the block for liveness */ diff --git a/src/panfrost/util/meson.build b/src/panfrost/util/meson.build index cf8577041dd..76e2249b60e 100644 --- a/src/panfrost/util/meson.build +++ b/src/panfrost/util/meson.build @@ -22,6 +22,7 @@ libpanfrost_util_files = files( 'pan_ir.c', 'pan_ir.h', + 'pan_liveness.c', 'pan_sysval.c', ) diff --git a/src/panfrost/util/pan_ir.h b/src/panfrost/util/pan_ir.h index 425c5246c1c..6b132228ddd 100644 --- a/src/panfrost/util/pan_ir.h +++ b/src/panfrost/util/pan_ir.h @@ -116,6 +116,66 @@ typedef struct { float alpha_ref; } panfrost_program; +typedef struct pan_block { + /* Link to next block. Must be first for mir_get_block */ + struct list_head link; + + /* List of instructions emitted for the current block */ + struct list_head instructions; + + /* Index of the block in source order */ + unsigned name; + + /* Control flow graph */ + struct pan_block *successors[2]; + unsigned nr_successors; + + struct set *predecessors; + + /* 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. */ + uint16_t *live_in; + uint16_t *live_out; +} pan_block; + +struct pan_instruction { + struct list_head link; +}; + +#define pan_foreach_instr_in_block_rev(block, v) \ + list_for_each_entry_rev(struct pan_instruction, v, &block->instructions, link) + +#define pan_foreach_successor(blk, v) \ + pan_block *v; \ + pan_block **_v; \ + for (_v = (pan_block **) &blk->successors[0], \ + v = *_v; \ + v != NULL && _v < (pan_block **) &blk->successors[2]; \ + _v++, v = *_v) \ + +#define pan_foreach_predecessor(blk, v) \ + struct set_entry *_entry_##v; \ + struct pan_block *v; \ + for (_entry_##v = _mesa_set_next_entry(blk->predecessors, NULL), \ + v = (struct pan_block *) (_entry_##v ? _entry_##v->key : NULL); \ + _entry_##v != NULL; \ + _entry_##v = _mesa_set_next_entry(blk->predecessors, _entry_##v), \ + v = (struct pan_block *) (_entry_##v ? _entry_##v->key : NULL)) + + +typedef void (*pan_liveness_update)(uint16_t *, void *, unsigned max); + +void pan_liveness_gen(uint16_t *live, unsigned node, unsigned max, uint16_t mask); +void pan_liveness_kill(uint16_t *live, unsigned node, unsigned max, uint16_t mask); +bool pan_liveness_get(uint16_t *live, unsigned node, uint16_t max); + +void pan_compute_liveness(struct list_head *blocks, + unsigned temp_count, + pan_liveness_update callback); + +void pan_free_liveness(struct list_head *blocks); + uint16_t pan_to_bytemask(unsigned bytes, unsigned mask); diff --git a/src/panfrost/util/pan_liveness.c b/src/panfrost/util/pan_liveness.c new file mode 100644 index 00000000000..48ec71b253a --- /dev/null +++ b/src/panfrost/util/pan_liveness.c @@ -0,0 +1,180 @@ +/* + * Copyright (C) 2019-2020 Collabora, Ltd. + * + * 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, sublicense, + * 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 NONINFRINGEMENT. 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. + */ + +#include "pan_ir.h" +#include "util/u_memory.h" +#include "util/list.h" +#include "util/set.h" + +/* Routines for liveness analysis. Liveness is tracked per byte per node. Per + * byte granularity is necessary for proper handling of int8 */ + +void +pan_liveness_gen(uint16_t *live, unsigned node, unsigned max, uint16_t mask) +{ + if (node >= max) + return; + + live[node] |= mask; +} + +void +pan_liveness_kill(uint16_t *live, unsigned node, unsigned max, uint16_t mask) +{ + if (node >= max) + return; + + live[node] &= ~mask; +} + +bool +pan_liveness_get(uint16_t *live, unsigned node, uint16_t max) +{ + if (node >= max) + return false; + + return live[node]; +} + +/* live_out[s] = sum { p in succ[s] } ( live_in[p] ) */ + +static void +liveness_block_live_out(pan_block *blk, unsigned temp_count) +{ + pan_foreach_successor(blk, succ) { + for (unsigned i = 0; i < temp_count; ++i) + blk->live_out[i] |= succ->live_in[i]; + } +} + +/* 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. */ + +static bool +liveness_block_update( + pan_block *blk, unsigned temp_count, + pan_liveness_update callback) +{ + bool progress = false; + + liveness_block_live_out(blk, temp_count); + + 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) + callback(live, (void *) 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 inline pan_block * +pan_exit_block(struct list_head *blocks) +{ + pan_block *last = list_last_entry(blocks, pan_block, link); + assert(last->nr_successors == 0); + return last; +} + +void +pan_compute_liveness( + struct list_head *blocks, + unsigned temp_count, + pan_liveness_update callback) +{ + + /* 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); + + /* Allocate */ + + list_for_each_entry(pan_block, block, blocks, link) { + block->live_in = rzalloc_array(NULL, uint16_t, temp_count); + block->live_out = rzalloc_array(NULL, 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(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, callback); + + /* 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); +} + +void +pan_free_liveness(struct list_head *blocks) +{ + 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; + } +} -- 2.30.2