[Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
Christian Gmeiner
christian.gmeiner at gmail.com
Fri May 10 09:09:01 UTC 2019
Signed-off-by: Christian Gmeiner <christian.gmeiner at gmail.com>
---
src/etnaviv/compiler/eir.h | 3 +
src/etnaviv/compiler/eir_live_variables.c | 258 ++++++++++++++++++
src/etnaviv/compiler/meson.build | 1 +
.../compiler/tests/eir_live_variables.cpp | 162 +++++++++++
src/etnaviv/compiler/tests/meson.build | 11 +
5 files changed, 435 insertions(+)
create mode 100644 src/etnaviv/compiler/eir_live_variables.c
create mode 100644 src/etnaviv/compiler/tests/eir_live_variables.cpp
diff --git a/src/etnaviv/compiler/eir.h b/src/etnaviv/compiler/eir.h
index a05b12de94b..38c6af4e07e 100644
--- a/src/etnaviv/compiler/eir.h
+++ b/src/etnaviv/compiler/eir.h
@@ -151,6 +151,9 @@ struct eir
/* keep track of number of allocated uniforms */
struct util_dynarray uniform_alloc;
unsigned uniform_offset;
+
+ /* Live ranges of temp registers */
+ int *temp_start, *temp_end;
};
struct eir_info {
diff --git a/src/etnaviv/compiler/eir_live_variables.c b/src/etnaviv/compiler/eir_live_variables.c
new file mode 100644
index 00000000000..fe94e7a2a3d
--- /dev/null
+++ b/src/etnaviv/compiler/eir_live_variables.c
@@ -0,0 +1,258 @@
+/*
+ * Copyright (c) 2018 Etnaviv Project
+ * Copyright (C) 2018 Zodiac Inflight Innovations
+ *
+ * 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.
+ *
+ * Authors:
+ * Christian Gmeiner <christian.gmeiner at gmail.com>
+ */
+
+#include "eir.h"
+#include "util/bitset.h"
+#include "util/ralloc.h"
+#include "util/u_math.h"
+
+#define MAX_INSTRUCTION (1 << 30)
+
+struct block_data {
+ BITSET_WORD *def;
+ BITSET_WORD *use;
+ BITSET_WORD *livein;
+ BITSET_WORD *liveout;
+ int start_ip, end_ip;
+};
+
+/* Returns the variable index for the c-th component of register reg. */
+static inline unsigned
+var_from_reg(unsigned reg, unsigned c)
+{
+ assert(c < 4);
+ return (reg * 4) + c;
+}
+
+static void
+setup_use(struct eir_block *block, const struct eir_register *src, int ip)
+{
+ const struct eir *ir = block->ir;
+ struct block_data *bd = block->data;
+
+ if (src->type != EIR_REG_TEMP)
+ return;
+
+ /* The use[] bitset marks when the block makes
+ * use of a variable without having completely
+ * defined that variable within the block.
+ */
+
+ const unsigned swiz_comp[4] = {
+ /* x */ src->swizzle & 0x3,
+ /* y */ (src->swizzle & 0x0C) >> 2,
+ /* z */ (src->swizzle & 0x30) >> 4,
+ /* w */ (src->swizzle & 0xc0) >> 6,
+ };
+
+ for (unsigned c = 0; c < 4; c++) {
+ const unsigned var = var_from_reg(src->index, swiz_comp[c]);
+
+ ir->temp_start[var] = MIN2(ir->temp_start[var], ip);
+ ir->temp_end[var] = ip;
+
+ if (!BITSET_TEST(bd->def, var))
+ BITSET_SET(bd->use, var);
+ }
+}
+
+static inline void
+setup_def(struct eir_block *block, const struct eir_register *dst, int ip)
+{
+ const struct eir *ir = block->ir;
+ struct block_data *bd = block->data;
+
+ for (unsigned c = 0; c < 4; c++) {
+ if (dst->writemask & (1 << c)) {
+ const unsigned var = var_from_reg(dst->index, c);
+
+ ir->temp_start[var] = MIN2(ir->temp_start[var], ip);
+ ir->temp_end[var] = ip;
+
+ BITSET_SET(bd->def, var);
+ }
+ }
+}
+
+static void
+setup_def_use(struct eir *ir)
+{
+ int ip = 0;
+
+ eir_for_each_block(block, ir) {
+ struct block_data *bd = block->data;
+ bd->start_ip = ip;
+
+ eir_for_each_inst(instr, block) {
+ const struct gc_instr *gc = &instr->gc;
+
+ for (unsigned i = 0; i < gc_op_num_src(gc->opcode); i++)
+ setup_use(block, &instr->src[i], ip);
+
+ if (gc_op_has_dst(gc->opcode))
+ setup_def(block, &instr->dst, ip);
+
+ ip++;
+ }
+ bd->end_ip = ip;
+ }
+}
+
+static bool
+compute_live_variables(struct eir *ir, unsigned bitset_words)
+{
+ bool progress = false;
+
+ eir_for_each_block_rev(block, ir) {
+ struct block_data *bd = block->data;
+
+ /* update liveout */
+ eir_for_each_successor(succ, block) {
+ struct block_data *sd = succ->data;
+
+ for (unsigned i = 0; i < bitset_words; i++) {
+ BITSET_WORD new_liveout =
+ (sd->livein[i] & ~bd->liveout[i]);
+
+ if (new_liveout) {
+ bd->liveout[i] |= new_liveout;
+ progress = true;
+ }
+ }
+ }
+
+ /* update livein */
+ for (unsigned i = 0; i < bitset_words; i++) {
+ BITSET_WORD new_livein =
+ (bd->use[i] | (bd->liveout[i] & ~bd->def[i]));
+
+ if (new_livein & ~bd->livein[i]) {
+ bd->livein[i] |= new_livein;
+ progress = true;
+ }
+ }
+ }
+
+ return progress;
+}
+
+static void
+compute_start_end(struct eir *ir, const int num_vars)
+{
+ /* extend intervals using analysis of control flow */
+ eir_for_each_block(block, ir) {
+ struct block_data *bd = block->data;
+
+ for (int i = 0; i < num_vars; i++) {
+ if (BITSET_TEST(bd->livein, i)) {
+ ir->temp_start[i] = MIN2(ir->temp_start[i], bd->start_ip);
+ ir->temp_end[i] = MAX2(ir->temp_end[i], bd->start_ip);
+ }
+
+ if (BITSET_TEST(bd->liveout, i)) {
+ ir->temp_start[i] = MIN2(ir->temp_start[i], bd->end_ip);
+ ir->temp_end[i] = MAX2(ir->temp_end[i], bd->end_ip);
+ }
+ }
+ }
+}
+
+void
+eir_calculate_live_intervals(struct eir *ir)
+{
+ const int num = util_dynarray_num_elements(&ir->reg_alloc, unsigned);
+ if (num == 0)
+ return;
+
+ assert(!ir->temp_start);
+ assert(!ir->temp_end);
+
+ const int num_components = num * 4;
+ const unsigned bitset_words = BITSET_WORDS(num_components);
+
+ ir->temp_start = rzalloc_array(ir, int, num_components);
+ ir->temp_end = rzalloc_array(ir, int, num_components);
+
+ for (int i = 0; i < num_components; i++) {
+ ir->temp_start[i] = MAX_INSTRUCTION;
+ ir->temp_end[i] = -1;
+ }
+
+ void *mem_ctx = ralloc_context(NULL);
+ assert(mem_ctx);
+
+ eir_for_each_block(block, ir) {
+ struct block_data *bd = rzalloc(mem_ctx, struct block_data);
+
+ assert(bd);
+ assert(!block->data);
+
+ bd->def = rzalloc_array(bd, BITSET_WORD, bitset_words);
+ bd->use = rzalloc_array(bd, BITSET_WORD, bitset_words);
+ bd->livein = rzalloc_array(bd, BITSET_WORD, bitset_words);
+ bd->liveout = rzalloc_array(bd, BITSET_WORD, bitset_words);
+
+ block->data = bd;
+ }
+
+ setup_def_use(ir);
+ while (compute_live_variables(ir, bitset_words)) {}
+
+ compute_start_end(ir, num_components);
+
+ ralloc_free(mem_ctx);
+ eir_for_each_block(block, ir)
+ block->data = NULL;
+}
+
+int
+eir_temp_range_start(const struct eir* ir, unsigned n)
+{
+ int start = INT_MAX;
+
+ if (!ir->temp_start)
+ return start;
+
+ for (unsigned i = 0; i < 4; i++)
+ start = MIN2(start, ir->temp_start[(n * 4) + i]);
+
+ return start;
+}
+
+int
+eir_temp_range_end(const struct eir *ir, unsigned n)
+{
+ int end = INT_MIN;
+
+ if (!ir->temp_end)
+ return end;
+
+ for (unsigned i = 0; i < 4; i++)
+ end = MAX2(end, ir->temp_end[(n * 4) + i]);
+
+ return end;
+}
diff --git a/src/etnaviv/compiler/meson.build b/src/etnaviv/compiler/meson.build
index c83399d5297..280ccf8f59d 100644
--- a/src/etnaviv/compiler/meson.build
+++ b/src/etnaviv/compiler/meson.build
@@ -24,6 +24,7 @@ libetnaviv_compiler_files = files(
'eir.c',
'eir.h',
'eir_legalize.c',
+ 'eir_live_variables.c',
'eir_uniform.c',
)
diff --git a/src/etnaviv/compiler/tests/eir_live_variables.cpp b/src/etnaviv/compiler/tests/eir_live_variables.cpp
new file mode 100644
index 00000000000..004bf977518
--- /dev/null
+++ b/src/etnaviv/compiler/tests/eir_live_variables.cpp
@@ -0,0 +1,162 @@
+/*
+ * Copyright (c) 2018 Etnaviv Project
+ * Copyright (C) 2018 Zodiac Inflight Innovations
+ *
+ * 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.
+ *
+ * Authors:
+ * Christian Gmeiner <christian.gmeiner at gmail.com>
+ */
+
+#include <gtest/gtest.h>
+#include <limits.h>
+#include "etnaviv/compiler/eir.h"
+
+TEST (LiveVariableTest, NOP)
+{
+ struct eir *ir = eir_create();
+ struct eir_block *block = eir_block_create(ir);
+
+ eir_NOP(block);
+
+ eir_calculate_live_intervals(ir);
+
+ ASSERT_FALSE(ir->temp_start);
+ ASSERT_FALSE(ir->temp_end);
+
+ ASSERT_EQ(eir_temp_range_start(ir, 0), INT_MAX);
+ ASSERT_EQ(eir_temp_range_end(ir, 0), INT_MIN);
+
+ eir_destroy(ir);
+}
+
+TEST (LiveVariableTest, MOV)
+{
+ struct eir *ir = eir_create();
+ struct eir_block *block = eir_block_create(ir);
+
+ struct eir_register dst = eir_temp_register(ir, 4);
+ dst.writemask = INST_COMPS_X;
+
+ struct eir_register src0 = eir_temp_register(ir, 4);
+ src0.swizzle = INST_SWIZ_BROADCAST(0);
+
+ struct eir_register src1 = eir_temp_register(ir, 4);
+ src1.swizzle = INST_SWIZ_BROADCAST(1);
+
+ eir_MOV(block, &dst, &src0);
+ eir_NOP(block);
+ eir_MOV(block, &dst, &src1);
+
+ eir_calculate_live_intervals(ir);
+
+ static const int MAX_INSTRUCTION = (1 << 30);
+
+ // dst x___
+ ASSERT_EQ(ir->temp_start[0], 0);
+ ASSERT_EQ(ir->temp_start[1], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_start[2], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_start[3], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_end[0], 2);
+ ASSERT_EQ(ir->temp_end[1], -1);
+ ASSERT_EQ(ir->temp_end[2], -1);
+ ASSERT_EQ(ir->temp_end[3], -1);
+
+ ASSERT_EQ(eir_temp_range_start(ir, 0), 0);
+ ASSERT_EQ(eir_temp_range_end(ir, 0), 2);
+
+ // src0 xxxx
+ ASSERT_EQ(ir->temp_start[4], 0);
+ ASSERT_EQ(ir->temp_start[5], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_start[6], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_start[7], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_end[4], 0);
+ ASSERT_EQ(ir->temp_end[5], -1);
+ ASSERT_EQ(ir->temp_end[6], -1);
+ ASSERT_EQ(ir->temp_end[7], -1);
+
+ ASSERT_EQ(eir_temp_range_start(ir, 1), 0);
+ ASSERT_EQ(eir_temp_range_end(ir, 1), 0);
+
+ // src1 yyyy
+ ASSERT_EQ(ir->temp_start[8], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_start[9], 0);
+ ASSERT_EQ(ir->temp_start[10], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_start[11], MAX_INSTRUCTION);
+ ASSERT_EQ(ir->temp_end[8], -1);
+ ASSERT_EQ(ir->temp_end[9], 2);
+ ASSERT_EQ(ir->temp_end[10], -1);
+ ASSERT_EQ(ir->temp_end[11], -1);
+
+ ASSERT_EQ(eir_temp_range_start(ir, 2), 0);
+ ASSERT_EQ(eir_temp_range_end(ir, 2), 2);
+
+ eir_destroy(ir);
+}
+
+TEST (LiveVariableTest, MOVandADD)
+{
+ struct eir *ir = eir_create();
+ struct eir_block *block = eir_block_create(ir);
+ float v0[] = { 0.1f, 0.2f, 0.3f, 0.4f };
+ float v1[] = { 0.5f, 0.6f, 0.7f, 0.8f };
+ struct eir_register t0 = eir_temp_register(ir, 4);
+ struct eir_register t1 = eir_temp_register(ir, 4);
+ struct eir_register u0 = eir_uniform_register_vec4_f(ir, 4, v0);
+ struct eir_register u1 = eir_uniform_register_vec4_f(ir, 4, v1);
+
+ t0.writemask = INST_COMPS_X | INST_COMPS_Y | INST_COMPS_Z | INST_COMPS_W;
+ t0.swizzle = INST_SWIZ_IDENTITY;
+ t1.writemask = INST_COMPS_X | INST_COMPS_Y | INST_COMPS_Z | INST_COMPS_W;
+ t1.swizzle = INST_SWIZ_IDENTITY;
+
+ eir_MOV(block, &t1, &u0);
+ eir_ADD(block, &t0, &u1, &t1);
+
+ eir_calculate_live_intervals(ir);
+
+ // t0
+ ASSERT_EQ(ir->temp_start[0], 1);
+ ASSERT_EQ(ir->temp_start[1], 1);
+ ASSERT_EQ(ir->temp_start[2], 1);
+ ASSERT_EQ(ir->temp_start[3], 1);
+ ASSERT_EQ(ir->temp_end[0], 1);
+ ASSERT_EQ(ir->temp_end[1], 1);
+ ASSERT_EQ(ir->temp_end[2], 1);
+ ASSERT_EQ(ir->temp_end[3], 1);
+
+ ASSERT_EQ(eir_temp_range_start(ir, 0), 1);
+ ASSERT_EQ(eir_temp_range_end(ir, 0), 1);
+
+ // t1
+ ASSERT_EQ(ir->temp_start[4], 0);
+ ASSERT_EQ(ir->temp_start[5], 0);
+ ASSERT_EQ(ir->temp_start[6], 0);
+ ASSERT_EQ(ir->temp_start[7], 0);
+ ASSERT_EQ(ir->temp_end[4], 1);
+ ASSERT_EQ(ir->temp_end[5], 1);
+ ASSERT_EQ(ir->temp_end[6], 1);
+ ASSERT_EQ(ir->temp_end[7], 1);
+
+ ASSERT_EQ(eir_temp_range_start(ir, 1), 0);
+ ASSERT_EQ(eir_temp_range_end(ir, 1), 1);
+
+ eir_destroy(ir);
+}
diff --git a/src/etnaviv/compiler/tests/meson.build b/src/etnaviv/compiler/tests/meson.build
index f82acae5f1a..599c2342297 100644
--- a/src/etnaviv/compiler/tests/meson.build
+++ b/src/etnaviv/compiler/tests/meson.build
@@ -52,3 +52,14 @@ test(
dependencies : [dep_clock, dep_thread, idep_gtest],
)
)
+
+test(
+ 'eir_live_variables',
+ executable(
+ 'eir_live_variables', 'eir_live_variables.cpp',
+ cpp_args : [cpp_vis_args, cpp_msvc_compat_args],
+ link_with: [libetnaviv_gc, libetnaviv_compiler, libmesa_util],
+ include_directories: [inc_common, inc_etnaviv],
+ dependencies : [dep_clock, dep_thread, idep_gtest],
+ )
+)
--
2.21.0
More information about the mesa-dev
mailing list