From e8139ef6453aa3a8da5a07be74dcb80a35f083e3 Mon Sep 17 00:00:00 2001 From: Alyssa Rosenzweig Date: Wed, 11 Mar 2020 20:39:36 -0400 Subject: [PATCH] pan/bi: Add register allocator We model the machine as vector (with restrictions) to natively handle mixed types and I/O and other goodies. We use LCRA for the heavylifting. This commit adds only the modeling to feed into LCRA and spit LCRA solutions back; next commit will integrate it with the IR. Signed-off-by: Alyssa Rosenzweig Part-of: --- src/panfrost/bifrost/bi_ra.c | 112 +++++++++++++++++++++++++ src/panfrost/bifrost/bifrost_compile.c | 1 + src/panfrost/bifrost/compiler.h | 3 +- src/panfrost/bifrost/meson.build | 1 + 4 files changed, 116 insertions(+), 1 deletion(-) create mode 100644 src/panfrost/bifrost/bi_ra.c diff --git a/src/panfrost/bifrost/bi_ra.c b/src/panfrost/bifrost/bi_ra.c new file mode 100644 index 00000000000..b30f0e7aceb --- /dev/null +++ b/src/panfrost/bifrost/bi_ra.c @@ -0,0 +1,112 @@ +/* + * Copyright (C) 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. + * + * Authors (Collabora): + * Alyssa Rosenzweig + */ + +#include "compiler.h" +#include "panfrost/util/lcra.h" +#include "util/u_memory.h" + +static void +bi_compute_interference(bi_context *ctx, struct lcra_state *l) +{ + bi_compute_liveness(ctx); + + bi_foreach_block(ctx, _blk) { + bi_block *blk = (bi_block *) _blk; + uint16_t *live = mem_dup(_blk->live_out, l->node_count * sizeof(uint16_t)); + + bi_foreach_instr_in_block_rev(blk, ins) { + /* Mark all registers live after the instruction as + * interfering with the destination */ + + if (ins->dest && (ins->dest < l->node_count)) { + for (unsigned i = 1; i < l->node_count; ++i) { + if (live[i]) + lcra_add_node_interference(l, ins->dest, ins->writemask, i, live[i]); + } + } + + /* Update live_in */ + bi_liveness_ins_update(live, ins, l->node_count); + } + + free(live); + } +} + +enum { + BI_REG_CLASS_WORK = 0, +} bi_reg_class; + +static struct lcra_state * +bi_allocate_registers(bi_context *ctx, bool *success) +{ + unsigned node_count = bi_max_temp(ctx); + + struct lcra_state *l = + lcra_alloc_equations(node_count, 1, 8, 16, 1); + + l->class_start[BI_REG_CLASS_WORK] = 0; + l->class_size[BI_REG_CLASS_WORK] = 64 * 4; /* R0 - R63, all 32-bit */ + + bi_foreach_instr_global(ctx, ins) { + unsigned dest = ins->dest; + + if (!dest || (dest >= node_count)) + continue; + + l->class[dest] = BI_REG_CLASS_WORK; + lcra_set_alignment(l, dest, 2); /* 2^2 = 4 */ + lcra_restrict_range(l, dest, 4); + } + + bi_compute_interference(ctx, l); + + *success = lcra_solve(l); + + return l; +} + +void +bi_register_allocate(bi_context *ctx) +{ + struct lcra_state *l = NULL; + bool success = false; + + do { + if (l) { + lcra_free(l); + l = NULL; + } + + bi_invalidate_liveness(ctx); + l = bi_allocate_registers(ctx, &success); + + /* TODO: Spilling */ + assert(success); + } while(!success); + + lcra_free(l); +} diff --git a/src/panfrost/bifrost/bifrost_compile.c b/src/panfrost/bifrost/bifrost_compile.c index 0195940cda0..b9cb89d961b 100644 --- a/src/panfrost/bifrost/bifrost_compile.c +++ b/src/panfrost/bifrost/bifrost_compile.c @@ -863,6 +863,7 @@ bifrost_compile_shader_nir(nir_shader *nir, panfrost_program *program, unsigned bi_print_shader(ctx, stdout); bi_schedule(ctx); + bi_register_allocate(ctx); ralloc_free(ctx); } diff --git a/src/panfrost/bifrost/compiler.h b/src/panfrost/bifrost/compiler.h index 920ca7d7e06..499fa9a1363 100644 --- a/src/panfrost/bifrost/compiler.h +++ b/src/panfrost/bifrost/compiler.h @@ -387,7 +387,7 @@ static inline unsigned bi_max_temp(bi_context *ctx) { unsigned alloc = MAX2(ctx->impl->reg_alloc, ctx->impl->ssa_alloc); - return ((alloc + 1 + ctx->temp_alloc) << 1) | BIR_IS_REG; + return ((alloc + 2 + ctx->temp_alloc) << 1); } static inline unsigned @@ -508,6 +508,7 @@ uint16_t bi_bytemask_of_read_components(bi_instruction *ins, unsigned node); bool bi_opt_dead_code_eliminate(bi_context *ctx, bi_block *block); void bi_schedule(bi_context *ctx); +void bi_register_allocate(bi_context *ctx); /* Liveness */ diff --git a/src/panfrost/bifrost/meson.build b/src/panfrost/bifrost/meson.build index fac47e02981..86955267629 100644 --- a/src/panfrost/bifrost/meson.build +++ b/src/panfrost/bifrost/meson.build @@ -24,6 +24,7 @@ libpanfrost_bifrost_files = files( 'bi_liveness.c', 'bi_print.c', 'bi_opt_dce.c', + 'bi_ra.c', 'bi_schedule.c', 'bi_tables.c', 'bir.c', -- 2.30.2