From 0d6c96a5c34de3ffdd6167282d7520dfd3c863cb Mon Sep 17 00:00:00 2001 From: Eric Anholt Date: Wed, 11 Apr 2012 13:12:33 -0700 Subject: [PATCH] i965: Add support for live variable analysis using dataflow analysis. --- src/mesa/drivers/dri/i965/Makefile.sources | 1 + .../dri/i965/brw_fs_live_variables.cpp | 158 ++++++++++++++++++ .../drivers/dri/i965/brw_fs_live_variables.h | 86 ++++++++++ 3 files changed, 245 insertions(+) create mode 100644 src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp create mode 100644 src/mesa/drivers/dri/i965/brw_fs_live_variables.h diff --git a/src/mesa/drivers/dri/i965/Makefile.sources b/src/mesa/drivers/dri/i965/Makefile.sources index 74213516210..44a6c8f30a2 100644 --- a/src/mesa/drivers/dri/i965/Makefile.sources +++ b/src/mesa/drivers/dri/i965/Makefile.sources @@ -116,6 +116,7 @@ i965_CXX_FILES := \ brw_fs.cpp \ brw_fs_cfg.cpp \ brw_fs_emit.cpp \ + brw_fs_live_variables.cpp \ brw_fs_visitor.cpp \ brw_fs_channel_expressions.cpp \ brw_fs_reg_allocate.cpp \ diff --git a/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp b/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp new file mode 100644 index 00000000000..fade132be5b --- /dev/null +++ b/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp @@ -0,0 +1,158 @@ +/* + * Copyright © 2012 Intel Corporation + * + * 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: + * Eric Anholt + * + */ + +#include "brw_fs_cfg.h" +#include "brw_fs_live_variables.h" + +using namespace brw; + +/** @file brw_fs_live_variables.cpp + * + * Support for computing at the basic block level which variables + * (virtual GRFs in our case) are live at entry and exit. + * + * See Muchnik's Advanced Compiler Design and Implementation, section + * 14.1 (p444). + */ + +/** + * Sets up the use[] and def[] arrays. + * + * The basic-block-level live variable analysis needs to know which + * variables get used before they're completely defined, and which + * variables are completely defined before they're used. + */ +void +fs_live_variables::setup_def_use() +{ + int ip = 0; + + for (int b = 0; b < cfg->num_blocks; b++) { + fs_bblock *block = cfg->blocks[b]; + + assert(ip == block->start_ip); + if (b > 0) + assert(cfg->blocks[b - 1]->end_ip == ip - 1); + + for (fs_inst *inst = block->start; + inst != block->end->next; + inst = (fs_inst *)inst->next) { + + /* Set use[] for this instruction */ + for (unsigned int i = 0; i < 3; i++) { + if (inst->src[i].file == GRF) { + int reg = inst->src[i].reg; + + if (!bd[b].def[reg]) + bd[b].use[reg] = true; + } + } + + /* Check for unconditional writes to whole registers. These + * are the things that screen off preceding definitions of a + * variable, and thus qualify for being in def[]. + */ + if (inst->dst.file == GRF && + inst->regs_written() == v->virtual_grf_sizes[inst->dst.reg] && + !inst->predicated && + !inst->force_uncompressed && + !inst->force_sechalf) { + int reg = inst->dst.reg; + if (!bd[b].use[reg]) + bd[b].def[reg] = true; + } + + ip++; + } + } +} + +/** + * The algorithm incrementally sets bits in liveout and livein, + * propagating it through control flow. It will eventually terminate + * because it only ever adds bits, and stops when no bits are added in + * a pass. + */ +void +fs_live_variables::compute_live_variables() +{ + bool cont = true; + + while (cont) { + cont = false; + + for (int b = 0; b < cfg->num_blocks; b++) { + /* Update livein */ + for (int i = 0; i < num_vars; i++) { + if (bd[b].use[i] || (bd[b].liveout[i] && !bd[b].def[i])) { + if (!bd[b].livein[i]) { + bd[b].livein[i] = true; + cont = true; + } + } + } + + /* Update liveout */ + foreach_list(block_node, &cfg->blocks[b]->children) { + fs_bblock_link *link = (fs_bblock_link *)block_node; + fs_bblock *block = link->block; + + for (int i = 0; i < num_vars; i++) { + if (bd[block->block_num].livein[i] && !bd[b].liveout[i]) { + bd[b].liveout[i] = true; + cont = true; + } + } + } + } + } +} + +fs_live_variables::fs_live_variables(fs_visitor *v, fs_cfg *cfg) + : v(v), cfg(cfg) +{ + mem_ctx = ralloc_context(cfg->mem_ctx); + + num_vars = v->virtual_grf_next; + bd = rzalloc_array(mem_ctx, struct block_data, cfg->num_blocks); + vars = rzalloc_array(mem_ctx, struct var, num_vars); + + for (int i = 0; i < cfg->num_blocks; i++) { + bd[i].def = rzalloc_array(mem_ctx, bool, num_vars); + bd[i].use = rzalloc_array(mem_ctx, bool, num_vars); + bd[i].livein = rzalloc_array(mem_ctx, bool, num_vars); + bd[i].liveout = rzalloc_array(mem_ctx, bool, num_vars); + } + + setup_def_use(); + compute_live_variables(); +} + +fs_live_variables::~fs_live_variables() +{ + ralloc_free(mem_ctx); +} diff --git a/src/mesa/drivers/dri/i965/brw_fs_live_variables.h b/src/mesa/drivers/dri/i965/brw_fs_live_variables.h new file mode 100644 index 00000000000..17e75531523 --- /dev/null +++ b/src/mesa/drivers/dri/i965/brw_fs_live_variables.h @@ -0,0 +1,86 @@ +/* + * Copyright © 2012 Intel Corporation + * + * 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: + * Eric Anholt + * + */ + +#include "brw_fs.h" + +namespace brw { + +struct block_data { + /** + * Which variables are defined before being used in the block. + * + * Note that for our purposes, "defined" means unconditionally, completely + * defined. + */ + bool *def; + + /** + * Which variables are used before being defined in the block. + */ + bool *use; + + /** Which defs reach the entry point of the block. */ + bool *livein; + + /** Which defs reach the exit point of the block. */ + bool *liveout; +}; + +class fs_live_variables { +public: + static void* operator new(size_t size, void *ctx) + { + void *node; + + node = rzalloc_size(ctx, size); + assert(node != NULL); + + return node; + } + + fs_live_variables(fs_visitor *v, fs_cfg *cfg); + ~fs_live_variables(); + + void setup_def_use(); + void compute_live_variables(); + + fs_visitor *v; + fs_cfg *cfg; + void *mem_ctx; + + struct var { + int blocknum; + int instnum; + fs_inst *inst; + } *vars; + int num_vars; + + /** Per-basic-block information on live variables */ + struct block_data *bd; +}; + +} /* namespace brw */ -- 2.30.2