Mesa (master): i965: Add support for live variable analysis using dataflow analysis.
Eric Anholt
anholt at kemper.freedesktop.org
Fri Apr 20 01:00:28 UTC 2012
Module: Mesa
Branch: master
Commit: 0d6c96a5c34de3ffdd6167282d7520dfd3c863cb
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=0d6c96a5c34de3ffdd6167282d7520dfd3c863cb
Author: Eric Anholt <eric at anholt.net>
Date: Wed Apr 11 13:12:33 2012 -0700
i965: Add support for live variable analysis using dataflow analysis.
---
src/mesa/drivers/dri/i965/Makefile.sources | 1 +
.../drivers/dri/i965/brw_fs_live_variables.cpp | 158 ++++++++++++++++++++
src/mesa/drivers/dri/i965/brw_fs_live_variables.h | 86 +++++++++++
3 files changed, 245 insertions(+), 0 deletions(-)
diff --git a/src/mesa/drivers/dri/i965/Makefile.sources b/src/mesa/drivers/dri/i965/Makefile.sources
index 7421351..44a6c8f 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 0000000..fade132
--- /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 <eric at anholt.net>
+ *
+ */
+
+#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 0000000..17e7553
--- /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 <eric at anholt.net>
+ *
+ */
+
+#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 */
More information about the mesa-commit
mailing list