glsl: Walk a list of ir_dereference_array to mark array elements as accessed

Signed-off-by: Ian Romanick <[email protected]>
Cc: [email protected]
Reviewed-by: Kenneth Graunke <[email protected]>

1 files changed, 425 insertions, 0 deletions

diff --git a/src/compiler/glsl/tests/array_refcount_test.cpp b/src/compiler/glsl/tests/array_refcount_test.cpp
index 29bb133e231..ecd7f46900b 100644
--- a/src/compiler/glsl/tests/array_refcount_test.cpp
+++ b/src/compiler/glsl/tests/array_refcount_test.cpp
@@ -23,12 +23,18 @@
 #include <gtest/gtest.h>
 #include "ir.h"
 #include "ir_array_refcount.h"
+#include "ir_builder.h"
+#include "util/hash_table.h"
+
+using namespace ir_builder;
 
 class array_refcount_test : public ::testing::Test {
 public:
    virtual void SetUp();
    virtual void TearDown();
 
+   exec_list instructions;
+   ir_factory *body;
    void *mem_ctx;
 
    /**
@@ -40,6 +46,14 @@ public:
    const glsl_type *array_3_of_array_4_of_array_5_of_vec4;
 
    /**
+    * glsl_type for a int[3].
+    *
+    * The exceptionally verbose name is picked because it matches the syntax
+    * of http://cdecl.org/.
+    */
+   const glsl_type *array_3_of_int;
+
+   /**
     * Wrapper to access private member "bits" of ir_array_refcount_entry
     *
     * The test class is a friend to ir_array_refcount_entry, but the
@@ -81,6 +95,9 @@ array_refcount_test::SetUp()
 {
    mem_ctx = ralloc_context(NULL);
 
+   instructions.make_empty();
+   body = new ir_factory(&instructions, mem_ctx);
+
    /* The type of vec4 x[3][4][5]; */
    const glsl_type *const array_5_of_vec4 =
       glsl_type::get_array_instance(glsl_type::vec4_type, 5);
@@ -88,15 +105,105 @@ array_refcount_test::SetUp()
       glsl_type::get_array_instance(array_5_of_vec4, 4);
    array_3_of_array_4_of_array_5_of_vec4 =
       glsl_type::get_array_instance(array_4_of_array_5_of_vec4, 3);
+
+   array_3_of_int = glsl_type::get_array_instance(glsl_type::int_type, 3);
 }
 
 void
 array_refcount_test::TearDown()
 {
+   delete body;
+   body = NULL;
+
    ralloc_free(mem_ctx);
    mem_ctx = NULL;
 }
 
+static operand
+deref_array(operand array, operand index)
+{
+   void *mem_ctx = ralloc_parent(array.val);
+
+   ir_rvalue *val = new(mem_ctx) ir_dereference_array(array.val, index.val);
+
+   return operand(val);
+}
+
+static operand
+deref_struct(operand s, const char *field)
+{
+   void *mem_ctx = ralloc_parent(s.val);
+
+   ir_rvalue *val = new(mem_ctx) ir_dereference_record(s.val, field);
+
+   return operand(val);
+}
+
+/**
+ * Verify that only the specified set of ir_variables exists in the hash table
+ */
+static void
+validate_variables_in_hash_table(struct hash_table *ht,
+                                 unsigned count,
+                                 ...)
+{
+   ir_variable **vars = new ir_variable *[count];
+   va_list args;
+
+   /* Make a copy of the list of expected ir_variables.  The copied list can
+    * be modified during the checking.
+    */
+   va_start(args, count);
+
+   for (unsigned i = 0; i < count; i++)
+      vars[i] = va_arg(args, ir_variable *);
+
+   va_end(args);
+
+   struct hash_entry *entry;
+   hash_table_foreach(ht, entry) {
+      const ir_instruction *const ir = (ir_instruction *) entry->key;
+      const ir_variable *const v = ir->as_variable();
+
+      if (v == NULL) {
+         ADD_FAILURE() << "Invalid junk in hash table: ir_type = "
+                       << ir->ir_type << ", address = "
+                       << (void *) ir;
+         continue;
+      }
+
+      unsigned i;
+      for (i = 0; i < count; i++) {
+         if (vars[i] == NULL)
+            continue;
+
+         if (vars[i] == v)
+            break;
+      }
+
+      if (i == count) {
+            ADD_FAILURE() << "Invalid variable in hash table: \""
+                          << v->name << "\"";
+      } else {
+         /* As each variable is encountered, remove it from the set.  Don't
+          * bother compacting the set because we don't care about
+          * performance here.
+          */
+         vars[i] = NULL;
+      }
+   }
+
+   /* Check that there's nothing left in the set. */
+   for (unsigned i = 0; i < count; i++) {
+      if (vars[i] != NULL) {
+         ADD_FAILURE() << "Variable was not in the hash table: \""
+                          << vars[i]->name << "\"";
+      }
+   }
+
+   delete [] vars;
+}
+
 TEST_F(array_refcount_test, ir_array_refcount_entry_initial_state_for_scalar)
 {
    ir_variable *const var =
@@ -290,3 +397,321 @@ TEST_F(array_refcount_test, mark_array_elements_referenced_whole_first_and_third
       }
    }
 }
+
+TEST_F(array_refcount_test, do_not_process_vector_indexing)
+{
+   /* Vectors and matrices can also be indexed in much the same manner as
+    * arrays.  The visitor should not try to track per-element accesses to
+    * these types.
+    */
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::float_type,
+                                                 "a",
+                                                 ir_var_auto);
+   ir_variable *var_b = new(mem_ctx) ir_variable(glsl_type::int_type,
+                                                 "b",
+                                                 ir_var_auto);
+   ir_variable *var_c = new(mem_ctx) ir_variable(glsl_type::vec4_type,
+                                                 "c",
+                                                 ir_var_auto);
+
+   body->emit(assign(var_a, deref_array(var_c, var_b)));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   ir_array_refcount_entry *entry_a = v.get_variable_entry(var_a);
+   ir_array_refcount_entry *entry_b = v.get_variable_entry(var_b);
+   ir_array_refcount_entry *entry_c = v.get_variable_entry(var_c);
+
+   EXPECT_TRUE(entry_a->is_referenced);
+   EXPECT_TRUE(entry_b->is_referenced);
+   EXPECT_TRUE(entry_c->is_referenced);
+
+   /* As validated by previous tests, for non-array types, num_bits is 1. */
+   ASSERT_EQ(1, get_num_bits(*entry_c));
+   EXPECT_FALSE(entry_c->is_linearized_index_referenced(0));
+}
+
+TEST_F(array_refcount_test, do_not_process_matrix_indexing)
+{
+   /* Vectors and matrices can also be indexed in much the same manner as
+    * arrays.  The visitor should not try to track per-element accesses to
+    * these types.
+    */
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::vec4_type,
+                                                 "a",
+                                                 ir_var_auto);
+   ir_variable *var_b = new(mem_ctx) ir_variable(glsl_type::int_type,
+                                                 "b",
+                                                 ir_var_auto);
+   ir_variable *var_c = new(mem_ctx) ir_variable(glsl_type::mat4_type,
+                                                 "c",
+                                                 ir_var_auto);
+
+   body->emit(assign(var_a, deref_array(var_c, var_b)));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   ir_array_refcount_entry *entry_a = v.get_variable_entry(var_a);
+   ir_array_refcount_entry *entry_b = v.get_variable_entry(var_b);
+   ir_array_refcount_entry *entry_c = v.get_variable_entry(var_c);
+
+   EXPECT_TRUE(entry_a->is_referenced);
+   EXPECT_TRUE(entry_b->is_referenced);
+   EXPECT_TRUE(entry_c->is_referenced);
+
+   /* As validated by previous tests, for non-array types, num_bits is 1. */
+   ASSERT_EQ(1, get_num_bits(*entry_c));
+   EXPECT_FALSE(entry_c->is_linearized_index_referenced(0));
+}
+
+TEST_F(array_refcount_test, do_not_process_array_inside_structure)
+{
+   /* Structures can contain arrays.  The visitor should not try to track
+    * per-element accesses to arrays contained inside structures.
+    */
+   const glsl_struct_field fields[] = {
+      glsl_struct_field(array_3_of_int, "i"),
+   };
+
+   const glsl_type *const record_of_array_3_of_int =
+      glsl_type::get_record_instance(fields, ARRAY_SIZE(fields), "S");
+
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::int_type,
+                                                 "a",
+                                                 ir_var_auto);
+
+   ir_variable *var_b = new(mem_ctx) ir_variable(record_of_array_3_of_int,
+                                                 "b",
+                                                 ir_var_auto);
+
+   /* a = b.i[2] */
+   body->emit(assign(var_a,
+                     deref_array(
+                        deref_struct(var_b, "i"),
+                        body->constant(int(2)))));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   ir_array_refcount_entry *entry_a = v.get_variable_entry(var_a);
+   ir_array_refcount_entry *entry_b = v.get_variable_entry(var_b);
+
+   EXPECT_TRUE(entry_a->is_referenced);
+   EXPECT_TRUE(entry_b->is_referenced);
+
+   ASSERT_EQ(1, get_num_bits(*entry_b));
+   EXPECT_FALSE(entry_b->is_linearized_index_referenced(0));
+
+   validate_variables_in_hash_table(v.ht, 2, var_a, var_b);
+}
+
+TEST_F(array_refcount_test, visit_simple_indexing)
+{
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::vec4_type,
+                                                 "a",
+                                                 ir_var_auto);
+   ir_variable *var_b = new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4,
+                                                 "b",
+                                                 ir_var_auto);
+
+   /* a = b[2][1][0] */
+   body->emit(assign(var_a,
+                     deref_array(
+                        deref_array(
+                           deref_array(var_b, body->constant(int(2))),
+                           body->constant(int(1))),
+                        body->constant(int(0)))));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   const unsigned accessed_element = 0 + (1 * 5) + (2 * 4 * 5);
+   ir_array_refcount_entry *entry_b = v.get_variable_entry(var_b);
+   const unsigned total_elements = var_b->type->arrays_of_arrays_size();
+
+   for (unsigned i = 0; i < total_elements; i++)
+      EXPECT_EQ(i == accessed_element, entry_b->is_linearized_index_referenced(i)) <<
+         "i = " << i;
+
+   validate_variables_in_hash_table(v.ht, 2, var_a, var_b);
+}
+
+TEST_F(array_refcount_test, visit_whole_second_array_indexing)
+{
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::vec4_type,
+                                                 "a",
+                                                 ir_var_auto);
+   ir_variable *var_b = new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4,
+                                                 "b",
+                                                 ir_var_auto);
+   ir_variable *var_i = new(mem_ctx) ir_variable(glsl_type::int_type,
+                                                 "i",
+                                                 ir_var_auto);
+
+   /* a = b[2][i][1] */
+   body->emit(assign(var_a,
+                     deref_array(
+                        deref_array(
+                           deref_array(var_b, body->constant(int(2))),
+                           var_i),
+                        body->constant(int(1)))));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   ir_array_refcount_entry *const entry_b = v.get_variable_entry(var_b);
+   for (unsigned i = 0; i < 3; i++) {
+      for (unsigned j = 0; j < 4; j++) {
+         for (unsigned k = 0; k < 5; k++) {
+            const bool accessed = (i == 2) && (k == 1);
+            const unsigned linearized_index = k + (j * 5) + (i * 4 * 5);
+
+            EXPECT_EQ(accessed,
+                      entry_b->is_linearized_index_referenced(linearized_index)) <<
+               "i = " << i;
+         }
+      }
+   }
+
+   validate_variables_in_hash_table(v.ht, 3, var_a, var_b, var_i);
+}
+
+TEST_F(array_refcount_test, visit_array_indexing_an_array)
+{
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::vec4_type,
+                                                 "a",
+                                                 ir_var_auto);
+   ir_variable *var_b = new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4,
+                                                 "b",
+                                                 ir_var_auto);
+   ir_variable *var_c = new(mem_ctx) ir_variable(array_3_of_int,
+                                                 "c",
+                                                 ir_var_auto);
+   ir_variable *var_i = new(mem_ctx) ir_variable(glsl_type::int_type,
+                                                 "i",
+                                                 ir_var_auto);
+
+   /* a = b[2][3][c[i]] */
+   body->emit(assign(var_a,
+                     deref_array(
+                        deref_array(
+                           deref_array(var_b, body->constant(int(2))),
+                           body->constant(int(3))),
+                        deref_array(var_c, var_i))));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   ir_array_refcount_entry *const entry_b = v.get_variable_entry(var_b);
+
+   for (unsigned i = 0; i < 3; i++) {
+      for (unsigned j = 0; j < 4; j++) {
+         for (unsigned k = 0; k < 5; k++) {
+            const bool accessed = (i == 2) && (j == 3);
+            const unsigned linearized_index = k + (j * 5) + (i * 4 * 5);
+
+            EXPECT_EQ(accessed,
+                      entry_b->is_linearized_index_referenced(linearized_index)) <<
+               "array b[" << i << "][" << j << "][" << k << "], " <<
+               "linear index = " << linearized_index;
+         }
+      }
+   }
+
+   ir_array_refcount_entry *const entry_c = v.get_variable_entry(var_c);
+
+   for (unsigned i = 0; i < var_c->type->array_size(); i++) {
+      EXPECT_EQ(true, entry_c->is_linearized_index_referenced(i)) <<
+         "array c, i = " << i;
+   }
+
+   validate_variables_in_hash_table(v.ht, 4, var_a, var_b, var_c, var_i);
+}
+
+TEST_F(array_refcount_test, visit_array_indexing_with_itself)
+{
+   const glsl_type *const array_2_of_array_3_of_int =
+      glsl_type::get_array_instance(array_3_of_int, 2);
+
+   const glsl_type *const array_2_of_array_2_of_array_3_of_int =
+      glsl_type::get_array_instance(array_2_of_array_3_of_int, 2);
+
+   ir_variable *var_a = new(mem_ctx) ir_variable(glsl_type::int_type,
+                                                 "a",
+                                                 ir_var_auto);
+   ir_variable *var_b = new(mem_ctx) ir_variable(array_2_of_array_2_of_array_3_of_int,
+                                                 "b",
+                                                 ir_var_auto);
+
+   /* Given GLSL code:
+    *
+    *    int b[2][2][3];
+    *    a = b[ b[0][0][0] ][ b[ b[0][1][0] ][ b[1][0][0] ][1] ][2]
+    *
+    * b[0][0][0], b[0][1][0], and b[1][0][0] are trivially accessed.
+    *
+    * b[*][*][1] and b[*][*][2] are accessed.
+    *
+    * Only b[1][1][0] is not accessed.
+    */
+   operand b000 = deref_array(
+      deref_array(
+         deref_array(var_b, body->constant(int(0))),
+         body->constant(int(0))),
+      body->constant(int(0)));
+
+   operand b010 = deref_array(
+      deref_array(
+         deref_array(var_b, body->constant(int(0))),
+         body->constant(int(1))),
+      body->constant(int(0)));
+
+   operand b100 = deref_array(
+      deref_array(
+         deref_array(var_b, body->constant(int(1))),
+         body->constant(int(0))),
+      body->constant(int(0)));
+
+   operand b_b010_b100_1 = deref_array(
+      deref_array(
+         deref_array(var_b, b010),
+         b100),
+      body->constant(int(1)));
+
+   body->emit(assign(var_a,
+                     deref_array(
+                        deref_array(
+                           deref_array(var_b, b000),
+                           b_b010_b100_1),
+                        body->constant(int(2)))));
+
+   ir_array_refcount_visitor v;
+
+   visit_list_elements(&v, &instructions);
+
+   ir_array_refcount_entry *const entry_b = v.get_variable_entry(var_b);
+
+   for (unsigned i = 0; i < 2; i++) {
+      for (unsigned j = 0; j < 2; j++) {
+         for (unsigned k = 0; k < 3; k++) {
+            const bool accessed = !(i == 1 && j == 1 && k == 0);
+            const unsigned linearized_index = k + (j * 3) + (i * 2 * 3);
+
+            EXPECT_EQ(accessed,
+                      entry_b->is_linearized_index_referenced(linearized_index)) <<
+               "array b[" << i << "][" << j << "][" << k << "], " <<
+               "linear index = " << linearized_index;
+         }
+      }
+   }
+
+   validate_variables_in_hash_table(v.ht, 2, var_a, var_b);
+}