[Mesa-dev] [PATCH 11/11] i965/vs: Improve live interval calculation.
Eric Anholt
eric at anholt.net
Thu Oct 4 16:07:48 PDT 2012
This is derived from the FS visitor code for the same, but tracks each channel
separately (otherwise, some typical fill-a-channel-at-a-time patterns would
produce excessive live intervals across loops and produce spilling).
---
src/mesa/drivers/dri/i965/Makefile.sources | 1 +
src/mesa/drivers/dri/i965/brw_vec4.cpp | 96 -------
.../drivers/dri/i965/brw_vec4_live_variables.cpp | 277 ++++++++++++++++++++
.../drivers/dri/i965/brw_vec4_live_variables.h | 81 ++++++
src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp | 1 +
5 files changed, 360 insertions(+), 96 deletions(-)
create mode 100644 src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp
create mode 100644 src/mesa/drivers/dri/i965/brw_vec4_live_variables.h
diff --git a/src/mesa/drivers/dri/i965/Makefile.sources b/src/mesa/drivers/dri/i965/Makefile.sources
index 565750b..387002f 100644
--- a/src/mesa/drivers/dri/i965/Makefile.sources
+++ b/src/mesa/drivers/dri/i965/Makefile.sources
@@ -130,6 +130,7 @@ i965_CXX_FILES = \
brw_vec4.cpp \
brw_vec4_emit.cpp \
brw_vec4_copy_propagation.cpp \
+ brw_vec4_live_variables.cpp \
brw_vec4_reg_allocate.cpp \
brw_vec4_visitor.cpp \
gen6_blorp.cpp \
diff --git a/src/mesa/drivers/dri/i965/brw_vec4.cpp b/src/mesa/drivers/dri/i965/brw_vec4.cpp
index 47a2d58..575d8cf 100644
--- a/src/mesa/drivers/dri/i965/brw_vec4.cpp
+++ b/src/mesa/drivers/dri/i965/brw_vec4.cpp
@@ -265,102 +265,6 @@ src_reg::equals(src_reg *r)
imm.u == r->imm.u);
}
-void
-vec4_visitor::calculate_live_intervals()
-{
- int *def = ralloc_array(mem_ctx, int, virtual_grf_count);
- int *use = ralloc_array(mem_ctx, int, virtual_grf_count);
- int loop_depth = 0;
- int loop_start = 0;
-
- if (this->live_intervals_valid)
- return;
-
- for (int i = 0; i < virtual_grf_count; i++) {
- def[i] = MAX_INSTRUCTION;
- use[i] = -1;
- }
-
- int ip = 0;
- foreach_list(node, &this->instructions) {
- vec4_instruction *inst = (vec4_instruction *)node;
-
- if (inst->opcode == BRW_OPCODE_DO) {
- if (loop_depth++ == 0)
- loop_start = ip;
- } else if (inst->opcode == BRW_OPCODE_WHILE) {
- loop_depth--;
-
- if (loop_depth == 0) {
- /* Patches up the use of vars marked for being live across
- * the whole loop.
- */
- for (int i = 0; i < virtual_grf_count; i++) {
- if (use[i] == loop_start) {
- use[i] = ip;
- }
- }
- }
- } else {
- for (unsigned int i = 0; i < 3; i++) {
- if (inst->src[i].file == GRF) {
- int reg = inst->src[i].reg;
-
- if (!loop_depth) {
- use[reg] = ip;
- } else {
- def[reg] = MIN2(loop_start, def[reg]);
- use[reg] = loop_start;
-
- /* Nobody else is going to go smash our start to
- * later in the loop now, because def[reg] now
- * points before the bb header.
- */
- }
- }
- }
- if (inst->dst.file == GRF) {
- int reg = inst->dst.reg;
-
- if (!loop_depth) {
- def[reg] = MIN2(def[reg], ip);
- } else {
- def[reg] = MIN2(def[reg], loop_start);
- }
- }
- }
-
- ip++;
- }
-
- ralloc_free(this->virtual_grf_def);
- ralloc_free(this->virtual_grf_use);
- this->virtual_grf_def = def;
- this->virtual_grf_use = use;
-
- this->live_intervals_valid = true;
-}
-
-bool
-vec4_visitor::virtual_grf_interferes(int a, int b)
-{
- int start = MAX2(this->virtual_grf_def[a], this->virtual_grf_def[b]);
- int end = MIN2(this->virtual_grf_use[a], this->virtual_grf_use[b]);
-
- /* We can't handle dead register writes here, without iterating
- * over the whole instruction stream to find every single dead
- * write to that register to compare to the live interval of the
- * other register. Just assert that dead_code_eliminate() has been
- * called.
- */
- assert((this->virtual_grf_use[a] != -1 ||
- this->virtual_grf_def[a] == MAX_INSTRUCTION) &&
- (this->virtual_grf_use[b] != -1 ||
- this->virtual_grf_def[b] == MAX_INSTRUCTION));
-
- return start < end;
-}
-
/**
* Must be called after calculate_live_intervales() to remove unused
* writes to registers -- register allocation will fail otherwise
diff --git a/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp b/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp
new file mode 100644
index 0000000..4bec809
--- /dev/null
+++ b/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp
@@ -0,0 +1,277 @@
+/*
+ * 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_cfg.h"
+#include "brw_vec4_live_variables.h"
+
+using namespace brw;
+
+/** @file brw_vec4_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.
+ *
+ * We independently track each channel of a vec4.
+ */
+void
+vec4_live_variables::setup_def_use()
+{
+ int ip = 0;
+
+ for (int b = 0; b < cfg->num_blocks; b++) {
+ bblock_t *block = cfg->blocks[b];
+
+ assert(ip == block->start_ip);
+ if (b > 0)
+ assert(cfg->blocks[b - 1]->end_ip == ip - 1);
+
+ for (vec4_instruction *inst = (vec4_instruction *)block->start;
+ inst != block->end->next;
+ inst = (vec4_instruction *)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;
+
+ for (int j = 0; j < 4; j++) {
+ int c = BRW_GET_SWZ(inst->src[i].swizzle, j);
+ if (!bd[b].def[reg * 4 + c])
+ bd[b].use[reg * 4 + c] = 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 &&
+ v->virtual_grf_sizes[inst->dst.reg] == 1 &&
+ !inst->predicate) {
+ for (int c = 0; c < 4; c++) {
+ if (inst->dst.writemask & (1 << c)) {
+ int reg = inst->dst.reg;
+ if (!bd[b].use[reg * 4 + c])
+ bd[b].def[reg * 4 + c] = 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
+vec4_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) {
+ bblock_link *link = (bblock_link *)block_node;
+ bblock_t *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;
+ }
+ }
+ }
+ }
+ }
+}
+
+vec4_live_variables::vec4_live_variables(vec4_visitor *v, cfg_t *cfg)
+ : v(v), cfg(cfg)
+{
+ mem_ctx = ralloc_context(cfg->mem_ctx);
+
+ num_vars = v->virtual_grf_count * 4;
+ bd = rzalloc_array(mem_ctx, struct block_data, cfg->num_blocks);
+
+ 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();
+}
+
+vec4_live_variables::~vec4_live_variables()
+{
+ ralloc_free(mem_ctx);
+}
+
+#define MAX_INSTRUCTION (1 << 30)
+
+void
+vec4_visitor::calculate_live_intervals()
+{
+ if (this->live_intervals_valid)
+ return;
+
+ int *def = ralloc_array(mem_ctx, int, this->virtual_grf_count);
+ int *use = ralloc_array(mem_ctx, int, this->virtual_grf_count);
+ ralloc_free(this->virtual_grf_def);
+ ralloc_free(this->virtual_grf_use);
+ this->virtual_grf_def = def;
+ this->virtual_grf_use = use;
+
+ for (int i = 0; i < this->virtual_grf_count; i++) {
+ def[i] = MAX_INSTRUCTION;
+ use[i] = -1;
+ }
+
+ /* Start by setting up the intervals with no knowledge of control
+ * flow.
+ */
+ int ip = 0;
+ foreach_list(node, &this->instructions) {
+ vec4_instruction *inst = (vec4_instruction *)node;
+
+ for (unsigned int i = 0; i < 3; i++) {
+ if (inst->src[i].file == GRF) {
+ int reg = inst->src[i].reg;
+
+ use[reg] = ip;
+ }
+ }
+
+ if (inst->dst.file == GRF) {
+ int reg = inst->dst.reg;
+
+ def[reg] = MIN2(def[reg], ip);
+ }
+
+ ip++;
+ }
+
+ /* Now, extend those intervals using our analysis of control flow.
+ *
+ * The control flow-aware analysis was done at a channel level, while at
+ * this point we're distilling it down to vgrfs.
+ */
+ cfg_t cfg(this);
+ vec4_live_variables livevars(this, &cfg);
+
+ for (int b = 0; b < cfg.num_blocks; b++) {
+ for (int i = 0; i < livevars.num_vars; i++) {
+ if (livevars.bd[b].livein[i]) {
+ def[i / 4] = MIN2(def[i / 4], cfg.blocks[b]->start_ip);
+ use[i / 4] = MAX2(use[i / 4], cfg.blocks[b]->start_ip);
+ }
+
+ if (livevars.bd[b].liveout[i]) {
+ def[i / 4] = MIN2(def[i / 4], cfg.blocks[b]->end_ip);
+ use[i / 4] = MAX2(use[i / 4], cfg.blocks[b]->end_ip);
+ }
+ }
+ }
+
+ this->live_intervals_valid = true;
+
+ /* Note in the non-control-flow code above, that we only take def[] as the
+ * first store, and use[] as the last use. We use this in dead code
+ * elimination, to determine when a store never gets used. However, we
+ * also use these arrays to answer the virtual_grf_interferes() question
+ * (live interval analysis), which is used for register coalescing and
+ * register allocation.
+ *
+ * So, there's a conflict over what the array should mean: if use[]
+ * considers a def after the last use, then the dead code elimination pass
+ * never does anything (and it's an important pass!). But if we don't
+ * include dead code, then virtual_grf_interferes() lies and we'll do
+ * horrible things like coalesce the register that is dead-code-written
+ * into another register that was live across the dead write (causing the
+ * use of the second register to take the dead write's source value instead
+ * of the coalesced MOV's source value).
+ *
+ * To resolve the conflict, immediately after calculating live intervals,
+ * detect dead code, nuke it, and if we changed anything, calculate again
+ * before returning to the caller. Now we happen to produce def[] and
+ * use[] arrays that will work for virtual_grf_interferes().
+ */
+ if (dead_code_eliminate())
+ calculate_live_intervals();
+}
+
+bool
+vec4_visitor::virtual_grf_interferes(int a, int b)
+{
+ int a_def = this->virtual_grf_def[a], a_use = this->virtual_grf_use[a];
+ int b_def = this->virtual_grf_def[b], b_use = this->virtual_grf_use[b];
+
+ /* If there's dead code (def but not use), it would break our test
+ * unless we consider it used.
+ */
+ if ((a_use == -1 && a_def != MAX_INSTRUCTION) ||
+ (b_use == -1 && b_def != MAX_INSTRUCTION)) {
+ return true;
+ }
+
+ int start = MAX2(a_def, b_def);
+ int end = MIN2(a_use, b_use);
+
+ return start < end;
+}
diff --git a/src/mesa/drivers/dri/i965/brw_vec4_live_variables.h b/src/mesa/drivers/dri/i965/brw_vec4_live_variables.h
new file mode 100644
index 0000000..c5b5dcd
--- /dev/null
+++ b/src/mesa/drivers/dri/i965/brw_vec4_live_variables.h
@@ -0,0 +1,81 @@
+/*
+ * 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_vec4.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 devec4 reach the entry point of the block. */
+ bool *livein;
+
+ /** Which devec4 reach the exit point of the block. */
+ bool *liveout;
+};
+
+class vec4_live_variables {
+public:
+ static void* operator new(size_t size, void *ctx)
+ {
+ void *node;
+
+ node = rzalloc_size(ctx, size);
+ assert(node != NULL);
+
+ return node;
+ }
+
+ vec4_live_variables(vec4_visitor *v, cfg_t *cfg);
+ ~vec4_live_variables();
+
+ void setup_def_use();
+ void compute_live_variables();
+
+ vec4_visitor *v;
+ cfg_t *cfg;
+ void *mem_ctx;
+
+ int num_vars;
+
+ /** Per-basic-block information on live variables */
+ struct block_data *bd;
+};
+
+} /* namespace brw */
diff --git a/src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp b/src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp
index 1dfdcce..9482d47 100644
--- a/src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp
+++ b/src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp
@@ -2695,6 +2695,7 @@ vec4_visitor::vec4_visitor(struct brw_vs_compile *c,
this->virtual_grf_def = NULL;
this->virtual_grf_use = NULL;
this->virtual_grf_sizes = NULL;
+ this->virtual_grf_chans = NULL;
this->virtual_grf_count = 0;
this->virtual_grf_reg_map = NULL;
this->virtual_grf_reg_count = 0;
--
1.7.10.4
More information about the mesa-dev
mailing list