[RFC,03/17] eir: add live ranges pass

Submitted by Christian Gmeiner on May 10, 2019, 9:09 a.m.

Details

Message ID 20190510090915.2739-4-christian.gmeiner@gmail.com
State New
Headers show
Series "An other look at nir" ( rev: 1 ) in Mesa

Not browsing as part of any series.

Commit Message

Christian Gmeiner May 10, 2019, 9:09 a.m.
Signed-off-by: Christian Gmeiner <christian.gmeiner@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

Patch hide | download patch | download mbox

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@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@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],
+  )
+)

Comments

On Fri, May 10, 2019 at 11:09 AM Christian Gmeiner
<christian.gmeiner@gmail.com> wrote:
>
> Signed-off-by: Christian Gmeiner <christian.gmeiner@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@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@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@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
On Fri, May 10, 2019 at 5:47 AM Connor Abbott <cwabbott0@gmail.com> wrote:
>
> On Fri, May 10, 2019 at 11:09 AM Christian Gmeiner
> <christian.gmeiner@gmail.com> wrote:
> >
> > Signed-off-by: Christian Gmeiner <christian.gmeiner@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.

One more word on the reachability thing... watch out for code like

while() {
  use(foo);
  if ()
    foo = bar;
  more code that doesn't use foo
}

In SSA, this becomes like

foo1 = undef
while() {
  foo = phi(foo1, foo2)
  use(foo)
  if ()
    foo2 = bar
  more code that doesn't use foo2
}

And so you have to extend the live range of foo2 until the end of the
loop. This becomes even more fun with various nested control flow
scenarios. (I haven't reviewed whether this series handles this sort
of thing appropriately, but Connor's comment reminded me of it.)

  -ilia
On Fri, May 10, 2019 at 11:47 AM Connor Abbott <cwabbott0@gmail.com> wrote:
>
>
> 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;

Whoops, that should actually read:

foo = ...
if (...) {
   bar = ...
   ... = bar; /* last use of "bar" */
} else {
   ... = 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.
>
On Fri, May 10, 2019 at 7:43 AM Connor Abbott <cwabbott0@gmail.com> wrote:
>
> On Fri, May 10, 2019 at 11:47 AM Connor Abbott <cwabbott0@gmail.com> wrote:
> >
> >
> > 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;
>
> Whoops, that should actually read:
>
> foo = ...
> if (...) {
>    bar = ...
>    ... = bar; /* last use of "bar" */
> } else {
>    ... = foo;
> }

hmm, my mind is a bit rusty on the live-range analysis, but foo and
bar do interfere in the if() side of the if/else..

I thought the case we didn't handle properly was more like a loop:

foo = ...
for (..) {
   bar = foo;
   ... stuff .. foo not live here..
   foo = ...
}
... = foo

where we end up considering foo live during the entire body of the
loop even though it isn't really.  I guess it is the same case as:

foo = ...
if () {
   bar = foo;
   ...
   foo = ...
}
... = foo;

BR,
-R

>
> >
> > 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.
> >
> _______________________________________________
> mesa-dev mailing list
> mesa-dev@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
On Fri, May 10, 2019 at 12:28 PM Rob Clark <robdclark@gmail.com> wrote:
>
> On Fri, May 10, 2019 at 7:43 AM Connor Abbott <cwabbott0@gmail.com> wrote:
> >
> > On Fri, May 10, 2019 at 11:47 AM Connor Abbott <cwabbott0@gmail.com> wrote:
> > >
> > >
> > > 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;
> >
> > Whoops, that should actually read:
> >
> > foo = ...
> > if (...) {
> >    bar = ...
> >    ... = bar; /* last use of "bar" */
> > } else {
> >    ... = foo;
> > }
>
> hmm, my mind is a bit rusty on the live-range analysis, but foo and
> bar do interfere in the if() side of the if/else..
>
> I thought the case we didn't handle properly was more like a loop:
>
> foo = ...
> for (..) {
>    bar = foo;
>    ... stuff .. foo not live here..
>    foo = ...
> }
> ... = foo
>
> where we end up considering foo live during the entire body of the
> loop even though it isn't really.  I guess it is the same case as:
>
> foo = ...
> if () {
>    bar = foo;
>    ...
>    foo = ...
> }
> ... = foo;
>

hmm, maybe I mis-read your example (damn gmail hiding quotes).. I
guess last use of bar is in the else block, so we are saying the same
(or similar) thing?

BR,
-R

> BR,
> -R
>
> >
> > >
> > > 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.
> > >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev@lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev