From e92935089bd9a987027d1f0791e7298bb3a57113 Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Thu, 15 Dec 2016 14:01:28 -0800 Subject: [PATCH] glsl: Mark a set of array elements as accessed using a list of array_deref_range Signed-off-by: Ian Romanick Cc: mesa-stable@lists.freedesktop.org Reviewed-by: Kenneth Graunke --- src/compiler/glsl/ir_array_refcount.cpp | 55 +++++++ src/compiler/glsl/ir_array_refcount.h | 49 ++++++ .../glsl/tests/array_refcount_test.cpp | 149 ++++++++++++++++++ 3 files changed, 253 insertions(+) diff --git a/src/compiler/glsl/ir_array_refcount.cpp b/src/compiler/glsl/ir_array_refcount.cpp index 1b5c43c9927..7627fa13bd2 100644 --- a/src/compiler/glsl/ir_array_refcount.cpp +++ b/src/compiler/glsl/ir_array_refcount.cpp @@ -60,6 +60,14 @@ ir_array_refcount_entry::ir_array_refcount_entry(ir_variable *var) num_bits = MAX2(1, var->type->arrays_of_arrays_size()); bits = new BITSET_WORD[BITSET_WORDS(num_bits)]; memset(bits, 0, BITSET_WORDS(num_bits) * sizeof(bits[0])); + + /* Count the "depth" of the arrays-of-arrays. */ + array_depth = 0; + for (const glsl_type *type = var->type; + type->is_array(); + type = type->fields.array) { + array_depth++; + } } @@ -69,6 +77,53 @@ ir_array_refcount_entry::~ir_array_refcount_entry() } +void +ir_array_refcount_entry::mark_array_elements_referenced(const array_deref_range *dr, + unsigned count) +{ + if (count != array_depth) + return; + + mark_array_elements_referenced(dr, count, 1, 0); +} + +void +ir_array_refcount_entry::mark_array_elements_referenced(const array_deref_range *dr, + unsigned count, + unsigned scale, + unsigned linearized_index) +{ + /* Walk through the list of array dereferences in least- to + * most-significant order. Along the way, accumulate the current + * linearized offset and the scale factor for each array-of-. + */ + for (unsigned i = 0; i < count; i++) { + if (dr[i].index < dr[i].size) { + linearized_index += dr[i].index * scale; + scale *= dr[i].size; + } else { + /* For each element in the current array, update the count and + * offset, then recurse to process the remaining arrays. + * + * There is some inefficency here if the last element in the + * array_deref_range list specifies the entire array. In that case, + * the loop will make recursive calls with count == 0. In the call, + * all that will happen is the bit will be set. + */ + for (unsigned j = 0; j < dr[i].size; j++) { + mark_array_elements_referenced(&dr[i + 1], + count - (i + 1), + scale * dr[i].size, + linearized_index + (j * scale)); + } + + return; + } + } + + BITSET_SET(bits, linearized_index); +} + ir_array_refcount_entry * ir_array_refcount_visitor::get_variable_entry(ir_variable *var) { diff --git a/src/compiler/glsl/ir_array_refcount.h b/src/compiler/glsl/ir_array_refcount.h index 1e7f34349f8..2988046aaed 100644 --- a/src/compiler/glsl/ir_array_refcount.h +++ b/src/compiler/glsl/ir_array_refcount.h @@ -60,6 +60,34 @@ public: /** Has the variable been referenced? */ bool is_referenced; + /** + * Mark a set of array elements as accessed. + * + * If every \c array_deref_range is for a single index, only a single + * element will be marked. If any \c array_deref_range is for an entire + * array-of-, then multiple elements will be marked. + * + * Items in the \c array_deref_range list appear in least- to + * most-significant order. This is the \b opposite order the indices + * appear in the GLSL shader text. An array access like + * + * x = y[1][i][3]; + * + * would appear as + * + * { { 3, n }, { m, m }, { 1, p } } + * + * where n, m, and p are the sizes of the arrays-of-arrays. + * + * The set of marked array elements can later be queried by + * \c ::is_linearized_index_referenced. + * + * \param dr List of array_deref_range elements to be processed. + * \param count Number of array_deref_range elements to be processed. + */ + void mark_array_elements_referenced(const array_deref_range *dr, + unsigned count); + /** Has a linearized array index been referenced? */ bool is_linearized_index_referenced(unsigned linearized_index) const { @@ -80,6 +108,27 @@ private: */ unsigned num_bits; + /** Count of nested arrays in the type. */ + unsigned array_depth; + + /** + * Recursive part of the public mark_array_elements_referenced method. + * + * The recursion occurs when an entire array-of- is accessed. See the + * implementation for more details. + * + * \param dr List of array_deref_range elements to be + * processed. + * \param count Number of array_deref_range elements to be + * processed. + * \param scale Current offset scale. + * \param linearized_index Current accumulated linearized array index. + */ + void mark_array_elements_referenced(const array_deref_range *dr, + unsigned count, + unsigned scale, + unsigned linearized_index); + friend class array_refcount_test; }; diff --git a/src/compiler/glsl/tests/array_refcount_test.cpp b/src/compiler/glsl/tests/array_refcount_test.cpp index d80ea810159..29bb133e231 100644 --- a/src/compiler/glsl/tests/array_refcount_test.cpp +++ b/src/compiler/glsl/tests/array_refcount_test.cpp @@ -62,6 +62,18 @@ public: { return entry.num_bits; } + + /** + * Wrapper to access private member "array_depth" of ir_array_refcount_entry + * + * The test class is a friend to ir_array_refcount_entry, but the + * individual tests are not part of the class. Since the friendliness of + * the test class does not extend to the tests, provide a wrapper. + */ + unsigned get_array_depth(const ir_array_refcount_entry &entry) + { + return entry.array_depth; + } }; void @@ -95,6 +107,7 @@ TEST_F(array_refcount_test, ir_array_refcount_entry_initial_state_for_scalar) ASSERT_NE((void *)0, get_bits(entry)); EXPECT_FALSE(entry.is_referenced); EXPECT_EQ(1, get_num_bits(entry)); + EXPECT_EQ(0, get_array_depth(entry)); EXPECT_FALSE(entry.is_linearized_index_referenced(0)); } @@ -108,6 +121,7 @@ TEST_F(array_refcount_test, ir_array_refcount_entry_initial_state_for_vector) ASSERT_NE((void *)0, get_bits(entry)); EXPECT_FALSE(entry.is_referenced); EXPECT_EQ(1, get_num_bits(entry)); + EXPECT_EQ(0, get_array_depth(entry)); EXPECT_FALSE(entry.is_linearized_index_referenced(0)); } @@ -121,6 +135,7 @@ TEST_F(array_refcount_test, ir_array_refcount_entry_initial_state_for_matrix) ASSERT_NE((void *)0, get_bits(entry)); EXPECT_FALSE(entry.is_referenced); EXPECT_EQ(1, get_num_bits(entry)); + EXPECT_EQ(0, get_array_depth(entry)); EXPECT_FALSE(entry.is_linearized_index_referenced(0)); } @@ -137,7 +152,141 @@ TEST_F(array_refcount_test, ir_array_refcount_entry_initial_state_for_array) ASSERT_NE((void *)0, get_bits(entry)); EXPECT_FALSE(entry.is_referenced); EXPECT_EQ(total_elements, get_num_bits(entry)); + EXPECT_EQ(3, get_array_depth(entry)); for (unsigned i = 0; i < total_elements; i++) EXPECT_FALSE(entry.is_linearized_index_referenced(i)) << "index = " << i; } + +TEST_F(array_refcount_test, mark_array_elements_referenced_simple) +{ + ir_variable *const var = + new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4, + "a", + ir_var_auto); + const unsigned total_elements = var->type->arrays_of_arrays_size(); + + ir_array_refcount_entry entry(var); + + static const array_deref_range dr[] = { + { 0, 5 }, { 1, 4 }, { 2, 3 } + }; + const unsigned accessed_element = 0 + (1 * 5) + (2 * 4 * 5); + + entry.mark_array_elements_referenced(dr, 3); + + for (unsigned i = 0; i < total_elements; i++) + EXPECT_EQ(i == accessed_element, entry.is_linearized_index_referenced(i)); +} + +TEST_F(array_refcount_test, mark_array_elements_referenced_whole_first_array) +{ + ir_variable *const var = + new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4, + "a", + ir_var_auto); + + ir_array_refcount_entry entry(var); + + static const array_deref_range dr[] = { + { 0, 5 }, { 1, 4 }, { 3, 3 } + }; + + entry.mark_array_elements_referenced(dr, 3); + + for (unsigned i = 0; i < 3; i++) { + for (unsigned j = 0; j < 4; j++) { + for (unsigned k = 0; k < 5; k++) { + const bool accessed = (j == 1) && (k == 0); + const unsigned linearized_index = k + (j * 5) + (i * 4 * 5); + + EXPECT_EQ(accessed, + entry.is_linearized_index_referenced(linearized_index)); + } + } + } +} + +TEST_F(array_refcount_test, mark_array_elements_referenced_whole_second_array) +{ + ir_variable *const var = + new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4, + "a", + ir_var_auto); + + ir_array_refcount_entry entry(var); + + static const array_deref_range dr[] = { + { 0, 5 }, { 4, 4 }, { 1, 3 } + }; + + entry.mark_array_elements_referenced(dr, 3); + + 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 == 1) && (k == 0); + const unsigned linearized_index = k + (j * 5) + (i * 4 * 5); + + EXPECT_EQ(accessed, + entry.is_linearized_index_referenced(linearized_index)); + } + } + } +} + +TEST_F(array_refcount_test, mark_array_elements_referenced_whole_third_array) +{ + ir_variable *const var = + new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4, + "a", + ir_var_auto); + + ir_array_refcount_entry entry(var); + + static const array_deref_range dr[] = { + { 5, 5 }, { 2, 4 }, { 1, 3 } + }; + + entry.mark_array_elements_referenced(dr, 3); + + 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 == 1) && (j == 2); + const unsigned linearized_index = k + (j * 5) + (i * 4 * 5); + + EXPECT_EQ(accessed, + entry.is_linearized_index_referenced(linearized_index)); + } + } + } +} + +TEST_F(array_refcount_test, mark_array_elements_referenced_whole_first_and_third_arrays) +{ + ir_variable *const var = + new(mem_ctx) ir_variable(array_3_of_array_4_of_array_5_of_vec4, + "a", + ir_var_auto); + + ir_array_refcount_entry entry(var); + + static const array_deref_range dr[] = { + { 5, 5 }, { 3, 4 }, { 3, 3 } + }; + + entry.mark_array_elements_referenced(dr, 3); + + for (unsigned i = 0; i < 3; i++) { + for (unsigned j = 0; j < 4; j++) { + for (unsigned k = 0; k < 5; k++) { + const bool accessed = (j == 3); + const unsigned linearized_index = k + (j * 5) + (i * 4 * 5); + + EXPECT_EQ(accessed, + entry.is_linearized_index_referenced(linearized_index)); + } + } + } +} -- 2.30.2