From 1cdf585613da37f23d737ac4713af0484d4a30d7 Mon Sep 17 00:00:00 2001 From: Vasily Khoruzhick Date: Sun, 18 Aug 2019 23:34:22 -0700 Subject: [PATCH] lima/ppir: add better liveness analysis Add better liveness analysis that was modelled after one in vc4. It uses live ranges and is aware of multiple blocks which is prerequisite for adding CF support Tested-by: Andreas Baierl Reviewed-by: Qiang Yu Reviewed-by: Erico Nunes Signed-off-by: Vasily Khoruzhick --- src/gallium/drivers/lima/Android.mk | 1 + src/gallium/drivers/lima/ir/pp/liveness.c | 163 ++++++++++++++++++++++ src/gallium/drivers/lima/ir/pp/ppir.h | 32 +++++ src/gallium/drivers/lima/ir/pp/regalloc.c | 102 ++++---------- src/gallium/drivers/lima/meson.build | 1 + 5 files changed, 225 insertions(+), 74 deletions(-) create mode 100644 src/gallium/drivers/lima/ir/pp/liveness.c diff --git a/src/gallium/drivers/lima/Android.mk b/src/gallium/drivers/lima/Android.mk index 069ecc4b23c..10aba8dd3e2 100644 --- a/src/gallium/drivers/lima/Android.mk +++ b/src/gallium/drivers/lima/Android.mk @@ -46,6 +46,7 @@ LOCAL_SRC_FILES := \ ir/pp/node_to_instr.c \ ir/pp/ppir.h \ ir/pp/regalloc.c \ + ir/pp/liveness.c \ ir/pp/scheduler.c \ lima_bo.c \ lima_bo.h \ diff --git a/src/gallium/drivers/lima/ir/pp/liveness.c b/src/gallium/drivers/lima/ir/pp/liveness.c new file mode 100644 index 00000000000..f9d8695680c --- /dev/null +++ b/src/gallium/drivers/lima/ir/pp/liveness.c @@ -0,0 +1,163 @@ +/* + * Copyright (c) 2019 Lima Project + * + * 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, sub license, + * 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 NON-INFRINGEMENT. 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 "ppir.h" + +static void +ppir_liveness_setup_def_use(ppir_compiler *comp) +{ + list_for_each_entry(ppir_block, block, &comp->block_list, list) { + list_for_each_entry(ppir_instr, instr, &block->instr_list, list) { + for (int i = 0; i < PPIR_INSTR_SLOT_NUM; i++) { + ppir_node *node = instr->slots[i]; + if (!node) + continue; + switch (node->op) { + case ppir_op_const: + continue; + default: + break; + } + + for (int i = 0; i < ppir_node_get_src_num(node); i++) { + ppir_src *src = ppir_node_get_src(node, i); + if (!src) + continue; + ppir_reg *reg = ppir_src_get_reg(src); + if (!reg) + continue; + + reg->live_in = MIN2(reg->live_in, instr->seq); + reg->live_out = MAX2(reg->live_out, instr->seq); + + if (BITSET_TEST(block->def, reg->regalloc_index)) + continue; + BITSET_SET(block->use, reg->regalloc_index); + } + + ppir_dest *dest = ppir_node_get_dest(node); + if (!dest) + continue; + ppir_reg *reg = ppir_dest_get_reg(dest); + if (!reg) + continue; + + reg->live_in = MIN2(reg->live_in, instr->seq); + reg->live_out = MAX2(reg->live_out, instr->seq); + + if (BITSET_TEST(block->use, reg->regalloc_index)) + continue; + BITSET_SET(block->def, reg->regalloc_index); + } + } + } +} + +static bool +ppir_liveness_setup_live_in_out(ppir_compiler *comp, int bitset_words) +{ + bool cont = false; + list_for_each_entry_rev(ppir_block, block, &comp->block_list, list) { + /* Update live_out: Any successor using the variable + * on entrance needs us to have the variable live on + * exit. + */ + for (int i = 0; i < 2; i++) { + ppir_block *succ = block->successors[i]; + if (!succ) + continue; + for (int i = 0; i < bitset_words; i++) { + BITSET_WORD new_live_out = (succ->live_in[i] & + ~block->live_out[i]); + if (new_live_out) { + block->live_out[i] |= new_live_out; + cont = true; + } + } + } + /* Update live_in */ + for (int i = 0; i < bitset_words; i++) { + BITSET_WORD new_live_in = (block->use[i] | + (block->live_out[i] & + ~block->def[i])); + if (new_live_in & ~block->live_in[i]) { + block->live_in[i] |= new_live_in; + cont = true; + } + } + } + + return cont; +} + +static void +ppir_liveness_compute_start_end(ppir_compiler *comp) +{ + list_for_each_entry(ppir_block, block, &comp->block_list, list) { + list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { + if (!list_length(&block->instr_list)) + continue; + + if (BITSET_TEST(block->live_in, reg->regalloc_index)) { + ppir_instr *first = list_first_entry(&block->instr_list, + ppir_instr, list); + reg->live_in = MIN2(reg->live_in, first->seq); + reg->live_out = MAX2(reg->live_out, first->seq); + } + + if (BITSET_TEST(block->live_out, reg->regalloc_index)) { + ppir_instr *last = list_last_entry(&block->instr_list, + ppir_instr, list); + reg->live_in = MIN2(reg->live_in, last->seq); + reg->live_out = MAX2(reg->live_out, last->seq); + } + } + } +} + +/* Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis + * 1) Compute def and use for each block. 'Def' is variables that are set + * before they are read in block, 'set' is variables that are read before + * they're set in the block. Initial live_in and live_out values are set + * accordingly. + * 2) Compute live_in and live_out of blocks: + * live_in(block) = use(block) + (live_out(block) - set(block)) + * live_out(block) = live_in(successors[0]) + live_in(successors[1]) + * Loop walks blocks in reverse order and computes live_in/live_out of each + * block, loop is terminated when no live_in or live_out is updated. + * 3) Adjust live_in and live_out of variables to block boundaries if they + * appear in live_in or live_out. + */ +void +ppir_liveness_analysis(ppir_compiler *comp) +{ + int bitset_words = BITSET_WORDS(list_length(&comp->reg_list)); + + ppir_liveness_setup_def_use(comp); + + while (ppir_liveness_setup_live_in_out(comp, bitset_words)) + ; + + ppir_liveness_compute_start_end(comp); +} diff --git a/src/gallium/drivers/lima/ir/pp/ppir.h b/src/gallium/drivers/lima/ir/pp/ppir.h index f3bbc914919..db8087ede62 100644 --- a/src/gallium/drivers/lima/ir/pp/ppir.h +++ b/src/gallium/drivers/lima/ir/pp/ppir.h @@ -171,6 +171,7 @@ typedef enum { typedef struct ppir_reg { struct list_head list; int index; + int regalloc_index; int num_components; /* whether this reg has to start from the x component * of a full physical reg, this is true for reg used @@ -319,6 +320,12 @@ typedef struct ppir_block { int sched_instr_index; int sched_instr_base; int index; + + /* for liveness analysis */ + BITSET_WORD *def; + BITSET_WORD *use; + BITSET_WORD *live_in; + BITSET_WORD *live_out; } ppir_block; typedef struct { @@ -478,6 +485,30 @@ static inline ppir_src *ppir_node_get_src(ppir_node *node, int idx) return NULL; } +static inline ppir_reg *ppir_src_get_reg(ppir_src *src) +{ + switch (src->type) { + case ppir_target_ssa: + return src->ssa; + case ppir_target_register: + return src->reg; + default: + return NULL; + } +} + +static inline ppir_reg *ppir_dest_get_reg(ppir_dest *dest) +{ + switch (dest->type) { + case ppir_target_ssa: + return &dest->ssa; + case ppir_target_register: + return dest->reg; + default: + return NULL; + } +} + static inline ppir_src *ppir_node_get_src_for_pred(ppir_node *node, ppir_node *pred) { for (int i = 0; i < ppir_node_get_src_num(node); i++) { @@ -616,5 +647,6 @@ bool ppir_node_to_instr(ppir_compiler *comp); bool ppir_schedule_prog(ppir_compiler *comp); bool ppir_regalloc_prog(ppir_compiler *comp); bool ppir_codegen_prog(ppir_compiler *comp); +void ppir_liveness_analysis(ppir_compiler *comp); #endif diff --git a/src/gallium/drivers/lima/ir/pp/regalloc.c b/src/gallium/drivers/lima/ir/pp/regalloc.c index 0d6808d27fd..8df6058ec0a 100644 --- a/src/gallium/drivers/lima/ir/pp/regalloc.c +++ b/src/gallium/drivers/lima/ir/pp/regalloc.c @@ -134,18 +134,6 @@ struct ra_regs *ppir_regalloc_init(void *mem_ctx) return ret; } -static ppir_reg *get_src_reg(ppir_src *src) -{ - switch (src->type) { - case ppir_target_ssa: - return src->ssa; - case ppir_target_register: - return src->reg; - default: - return NULL; - } -} - static void ppir_regalloc_update_reglist_ssa(ppir_compiler *comp) { list_for_each_entry(ppir_block, block, &comp->block_list, list) { @@ -169,53 +157,6 @@ static void ppir_regalloc_update_reglist_ssa(ppir_compiler *comp) } } -static ppir_reg *ppir_regalloc_build_liveness_info(ppir_compiler *comp) -{ - ppir_reg *ret = NULL; - - list_for_each_entry(ppir_block, block, &comp->block_list, list) { - list_for_each_entry(ppir_node, node, &block->node_list, list) { - if (node->op == ppir_op_store_color) { - ppir_store_node *store = ppir_node_to_store(node); - if (store->src.type == ppir_target_ssa) - ret = store->src.ssa; - else - ret = store->src.reg; - ret->live_out = INT_MAX; - continue; - } - - if (!node->instr || node->op == ppir_op_const) - continue; - - /* update reg live_in from node dest (write) */ - ppir_dest *dest = ppir_node_get_dest(node); - if (dest) { - ppir_reg *reg = NULL; - - if (dest->type == ppir_target_ssa) { - reg = &dest->ssa; - } - else if (dest->type == ppir_target_register) - reg = dest->reg; - - if (reg && node->instr->seq < reg->live_in) - reg->live_in = node->instr->seq; - } - - /* update reg live_out from node src (read) */ - for (int i = 0; i < ppir_node_get_src_num(node); i++) - { - ppir_reg *reg = get_src_reg(ppir_node_get_src(node, i)); - if (reg && node->instr->seq > reg->live_out) - reg->live_out = node->instr->seq; - } - } - } - - return ret; -} - static int get_phy_reg_index(int reg) { int i; @@ -498,11 +439,7 @@ static bool ppir_regalloc_spill_reg(ppir_compiler *comp, ppir_reg *chosen) ppir_dest *dest = ppir_node_get_dest(node); ppir_reg *reg = NULL; if (dest) { - if (dest->type == ppir_target_ssa) - reg = &dest->ssa; - else if (dest->type == ppir_target_register) - reg = dest->reg; - + reg = ppir_dest_get_reg(dest); if (reg == chosen) ppir_update_spilled_dest(comp, block, node, dest); } @@ -516,7 +453,7 @@ static bool ppir_regalloc_spill_reg(ppir_compiler *comp, ppir_reg *chosen) ppir_alu_node *move_alu = NULL; ppir_alu_node *alu = ppir_node_to_alu(node); for (int i = 0; i < alu->num_src; i++) { - reg = get_src_reg(alu->src + i); + reg = ppir_src_get_reg(alu->src + i); if (reg == chosen) { move_alu = ppir_update_spilled_src(comp, block, node, alu->src + i, move_alu); @@ -528,7 +465,7 @@ static bool ppir_regalloc_spill_reg(ppir_compiler *comp, ppir_reg *chosen) { for (int i = 0; i < ppir_node_get_src_num(node); i++) { ppir_src *src = ppir_node_get_src(node, i); - reg = get_src_reg(src); + reg = ppir_src_get_reg(src); if (reg == chosen) { ppir_update_spilled_src(comp, block, node, src, NULL); } @@ -580,9 +517,31 @@ static ppir_reg *ppir_regalloc_choose_spill_node(ppir_compiler *comp, static void ppir_regalloc_reset_liveness_info(ppir_compiler *comp) { + int bitset_words = BITSET_WORDS(list_length(&comp->reg_list)); + int idx = 0; + list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { reg->live_in = INT_MAX; reg->live_out = 0; + reg->regalloc_index = idx++; + } + + list_for_each_entry(ppir_block, block, &comp->block_list, list) { + if (block->def) + ralloc_free(block->def); + block->def = rzalloc_array(comp, BITSET_WORD, bitset_words); + + if (block->use) + ralloc_free(block->use); + block->use = rzalloc_array(comp, BITSET_WORD, bitset_words); + + if (block->live_in) + ralloc_free(block->live_in); + block->live_in = rzalloc_array(comp, BITSET_WORD, bitset_words); + + if (block->live_out) + ralloc_free(block->live_out); + block->live_out = rzalloc_array(comp, BITSET_WORD, bitset_words); } } @@ -590,21 +549,18 @@ int lima_ppir_force_spilling = 0; static bool ppir_regalloc_prog_try(ppir_compiler *comp, bool *spilled) { - ppir_reg *end_reg; - ppir_regalloc_reset_liveness_info(comp); - end_reg = ppir_regalloc_build_liveness_info(comp); + + ppir_liveness_analysis(comp); struct ra_graph *g = ra_alloc_interference_graph( comp->ra, list_length(&comp->reg_list)); - int n = 0, end_reg_index = 0; + int n = 0; list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { int c = ppir_ra_reg_class_vec1 + (reg->num_components - 1); if (reg->is_head) c += 4; - if (reg == end_reg) - end_reg_index = n; ra_set_node_class(g, n++, c); } @@ -633,8 +589,6 @@ static bool ppir_regalloc_prog_try(ppir_compiler *comp, bool *spilled) n1++; } - ra_set_node_reg(g, end_reg_index, ppir_ra_reg_base[ppir_ra_reg_class_vec4]); - *spilled = false; bool ok = ra_allocate(g); if (!ok || (comp->force_spilling-- > 0)) { diff --git a/src/gallium/drivers/lima/meson.build b/src/gallium/drivers/lima/meson.build index 2ab2b2ae118..0d8f2f87c29 100644 --- a/src/gallium/drivers/lima/meson.build +++ b/src/gallium/drivers/lima/meson.build @@ -39,6 +39,7 @@ files_lima = files( 'ir/pp/scheduler.c', 'ir/pp/instr.c', 'ir/pp/regalloc.c', + 'ir/pp/liveness.c', 'ir/pp/codegen.h', 'ir/pp/codegen.c', 'ir/pp/node_to_instr.c', -- 2.30.2