[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