[Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass
Connor Abbott
cwabbott0 at gmail.com
Fri May 10 09:47:26 UTC 2019
On Fri, May 10, 2019 at 11:09 AM Christian Gmeiner
<christian.gmeiner at gmail.com> wrote:
>
> 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;
This way of representing liveness, and then using a coloring register
allocator, is a common anti-pattern in Mesa, that was initially copied
from i965 which dates back to before we knew any better. I really
don't want to see it spread to yet another driver :(.
Representing live ranges like this is imprecise. If I have a program like this:
foo = ...
if (...) {
bar = ...
... = bar; /* last use of "bar" */
}
... = foo;
Then it will say that foo and bar interfere, even when they don't.
Now, this approximation does make things a bit simpler. But, it turns
out that if you're willing to make it, then the interference graph is
trivially colorable via a simple linear-time algorithm. This is the
basis of "linear-scan" register allocators, including the one in LLVM.
If you want to go down this route, you can, but this hybrid is just
useless as it gives you the worst of both worlds.
If you want to properly build up the interference graph, it's actually
not that hard. After doing the inter-basic-block liveness analysis,
for each block, you initialize a bitset to the live-out bitset. Then
you walk the block backwards, updating it at each instruction exactly
as in liveness analysis, so that it always represents the live
registers before each instruction. Then you add interferences between
all of the live registers and the register(s) defined at the
instruction.
One last pitfall I'll mention is that in the real world, you'll also
need to use reachability. If you have something like
if (...)
foo = ... /* only definition of "foo" */
... = foo;
where foo is only partially defined, then the liveness of foo will
"leak" through the if. To fix this you need to consider what's called
"reachability," i.e. something is only live if, in addition to
potentially being used sometime later, it is reachable (potentially
defined sometime earlier). Reachability analysis is exactly like
liveness analysis, but everything is backwards. i965 does this
properly nowadays, and the change had a huge effect on spilling/RA.
> };
>
> 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
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list