Mesa (shader-work): glsl: add pass to lower variable array indexing to conditional assignments
Luca Barbieri
lb at kemper.freedesktop.org
Wed Sep 8 04:52:12 UTC 2010
Module: Mesa
Branch: shader-work
Commit: e9fb955b3954234cae625c6752cbf64274ebfaa7
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=e9fb955b3954234cae625c6752cbf64274ebfaa7
Author: Luca Barbieri <luca at luca-barbieri.com>
Date: Wed Sep 8 01:35:44 2010 +0200
glsl: add pass to lower variable array indexing to conditional assignments
Currenly GLSL happily generates indirect addressing of any kind of
arrays.
Unfortunately DirectX 9 GPUs are not guaranteed to support any of them in
general.
This pass fixes that by lowering such constructs to a binary search on the
values, followed at the end by vectorized generation of equality masks, and
4 conditional assignments for each mask generation.
Note that this requires the ir_binop_equal change so that we can emit SEQ
to generate the boolean masks.
Unfortunately, ir_structure_splitting is too dumb to turn the resulting
constant array references to individual variables, so this will need to
be added too before this pass can actually be effective for temps.
---
src/glsl/Makefile | 1 +
src/glsl/SConscript | 1 +
src/glsl/ir_array_index_to_cond_assign.cpp | 277 ++++++++++++++++++++++++++++
src/glsl/ir_optimization.h | 1 +
src/glsl/ir_structure_splitting.cpp | 149 ++++++++++++---
src/glsl/main.cpp | 3 +
6 files changed, 402 insertions(+), 30 deletions(-)
diff --git a/src/glsl/Makefile b/src/glsl/Makefile
index efa274b..b12878c 100644
--- a/src/glsl/Makefile
+++ b/src/glsl/Makefile
@@ -31,6 +31,7 @@ CXX_SOURCES = \
glsl_symbol_table.cpp \
hir_field_selection.cpp \
ir_algebraic.cpp \
+ ir_array_index_to_cond_assign.cpp \
ir_basic_block.cpp \
ir_clone.cpp \
ir_constant_expression.cpp \
diff --git a/src/glsl/SConscript b/src/glsl/SConscript
index ac6324a..ed12e84 100644
--- a/src/glsl/SConscript
+++ b/src/glsl/SConscript
@@ -28,6 +28,7 @@ sources = [
'glsl_symbol_table.cpp',
'hir_field_selection.cpp',
'ir_algebraic.cpp',
+ 'ir_array_index_to_cond_assign.cpp',
'ir_basic_block.cpp',
'ir_clone.cpp',
'ir_constant_expression.cpp',
diff --git a/src/glsl/ir_array_index_to_cond_assign.cpp b/src/glsl/ir_array_index_to_cond_assign.cpp
new file mode 100644
index 0000000..517c4c0
--- /dev/null
+++ b/src/glsl/ir_array_index_to_cond_assign.cpp
@@ -0,0 +1,277 @@
+/*
+ * Copyright © 2010 Luca Barbieri
+ *
+ * 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, sublicense,
+ * 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 NONINFRINGEMENT. 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.
+ */
+
+/**
+ * \file ir_array_index_to_cond_assign.cpp
+ *
+ * Turns non-constant indexing into array types to a series of
+ * conditional moves of each element into a temporary.
+ *
+ * Pre-DX10 GPUs often don't have a native way to do this operation,
+ * and this works around that.
+ */
+
+#include "ir.h"
+#include "ir_rvalue_visitor.h"
+#include "ir_optimization.h"
+#include "glsl_types.h"
+#include <algorithm>
+
+template<typename TFunction>
+struct switch_generator
+{
+ const TFunction& generator;
+
+ ir_variable* index;
+ unsigned linear_sequence_max_length;
+ unsigned condition_components;
+
+ switch_generator(const TFunction& generator)
+ : generator(generator)
+ {}
+
+ exec_list linear_sequence(unsigned begin, unsigned end)
+ {
+ exec_list list, toappend;
+ if(begin == end)
+ return list;
+
+ /* do the first one unconditionally
+ * FINISHME: may not want this in some cases
+ */
+
+ toappend = this->generator(begin, 0);
+ list.append_list(&toappend);
+
+ for (unsigned i = begin + 1; i < end; i += 4) {
+ int comps = std::min(condition_components, end - i);
+
+ ir_rvalue* broadcast_index = new(index) ir_dereference_variable(index);
+ if(comps)
+ broadcast_index = new(index) ir_swizzle(broadcast_index, 0, 1, 2, 3, comps);
+
+ ir_constant* test_indices;
+ ir_constant_data test_indices_data;
+ memset(&test_indices_data, 0, sizeof(test_indices_data));
+ test_indices_data.i[0] = i;
+ test_indices_data.i[1] = i + 1;
+ test_indices_data.i[2] = i + 2;
+ test_indices_data.i[3] = i + 3;
+ test_indices = new(index) ir_constant(broadcast_index->type, &test_indices_data);
+
+ ir_rvalue* condition_val = new(index) ir_expression(ir_binop_equal,
+ &glsl_type::bool_type[comps - 1],
+ broadcast_index,
+ test_indices);
+ ir_variable* condition = new(index) ir_variable(&glsl_type::bool_type[comps], "dereference_array_condition", ir_var_temporary);
+ list.push_tail(condition);
+ list.push_tail(new (index) ir_assignment(new(index) ir_dereference_variable(condition), condition_val, 0));
+
+ if(comps == 1)
+ {
+ toappend = this->generator(i, new(index) ir_dereference_variable(condition));
+ list.append_list(&toappend);
+ }
+ else
+ {
+ for(int j = 0; j < comps; ++j)
+ {
+ toappend = this->generator(i + j, new(index) ir_swizzle(new(index) ir_dereference_variable(condition), j, 0, 0, 0, 1));
+ list.append_list(&toappend);
+ }
+ }
+ }
+
+ return list;
+ }
+
+ exec_list bisect(unsigned begin, unsigned end)
+ {
+ unsigned middle = (begin + end) >> 1;
+ ir_constant* middle_c;
+
+ if(index->type->base_type == GLSL_TYPE_UINT)
+ middle_c = new(index) ir_constant((unsigned)middle);
+ else if(index->type->base_type == GLSL_TYPE_UINT)
+ middle_c = new(index) ir_constant((int)middle);
+ else
+ assert(0);
+
+ ir_expression* less = new(index) ir_expression(
+ ir_binop_less, glsl_type::bool_type,
+ new(index) ir_dereference_variable(this->index),
+ middle_c);
+
+ ir_if* if_less = new(index) ir_if(less);
+ exec_list toappend;
+
+ toappend = (*this)(begin, middle);
+ if_less->then_instructions.append_list(&toappend);
+
+ toappend = (*this)(middle, end);
+ if_less->else_instructions.append_list(&toappend);
+
+ exec_list list;
+ list.push_tail(if_less);
+ return list;
+ }
+
+ exec_list operator()(unsigned begin, unsigned end)
+ {
+ unsigned length = end - begin;
+ if(length <= this->linear_sequence_max_length)
+ return linear_sequence(begin, end);
+ else
+ return bisect(begin, end);
+ }
+};
+
+struct assignment_generator
+{
+ ir_instruction* base_ir;
+ ir_rvalue* array;
+ bool is_write;
+ ir_variable* var;
+
+ assignment_generator()
+ {
+ }
+
+ exec_list operator()(unsigned i, ir_rvalue* condition) const
+ {
+ /* Just clone the rest of the deref chain when trying to get at the
+ * underlying variable.
+ * XXX: what if it has side effects?!? ir_vector_index_to_cond_assign does this too!
+ */
+ void *mem_ctx = talloc_parent(base_ir);
+ ir_rvalue* element = new(base_ir) ir_dereference_array(this->array->clone(mem_ctx, NULL), new(base_ir) ir_constant(i));
+ ir_rvalue* variable = new(base_ir) ir_dereference_variable(this->var);
+ exec_list list;
+ ir_assignment* assignment;
+ if(is_write)
+ assignment = new(base_ir) ir_assignment(element, variable, condition);
+ else
+ assignment = new(base_ir) ir_assignment(variable, element, condition);
+ list.push_tail(assignment);
+ return list;
+ }
+};
+
+/**
+ * Visitor class for replacing expressions with ir_constant values.
+ */
+
+class ir_array_index_to_cond_assign_visitor : public ir_rvalue_visitor {
+public:
+ ir_array_index_to_cond_assign_visitor()
+ {
+ progress = false;
+ }
+
+ bool progress;
+
+ ir_variable* convert_dereference_array(ir_dereference_array *orig_deref, ir_rvalue* value)
+ {
+ ir_assignment *assign;
+
+ unsigned length;
+ if (orig_deref->array->type->is_array())
+ length = orig_deref->array->type->length;
+ else if (orig_deref->array->type->is_matrix())
+ length = orig_deref->array->type->matrix_columns;
+ else
+ assert(0);
+
+ ir_variable* var = new(base_ir) ir_variable(orig_deref->type, "dereference_array_value", ir_var_temporary);
+ base_ir->insert_before(var);
+
+ if(value)
+ base_ir->insert_before(new(base_ir) ir_assignment(new(base_ir) ir_dereference_variable(var), value, NULL));
+
+ /* Store the index to a temporary to avoid reusing its tree. */
+ ir_variable *index = new(base_ir) ir_variable(orig_deref->array_index->type, "dereference_array_index", ir_var_temporary);
+ base_ir->insert_before(index);
+ assign = new(base_ir) ir_assignment(new(base_ir) ir_dereference_variable(index), orig_deref->array_index, NULL);
+ base_ir->insert_before(assign);
+
+ assignment_generator ag;
+ ag.array = orig_deref->array;
+ ag.base_ir = base_ir;
+ ag.var = var;
+ ag.is_write = !!value;
+
+ switch_generator<assignment_generator> sg(ag);
+ sg.index = index;
+ sg.linear_sequence_max_length = 4;
+ sg.condition_components = 4;
+
+ exec_list list = sg(0, length);
+ base_ir->insert_before(&list);
+
+ return var;
+ }
+
+ virtual void handle_rvalue(ir_rvalue **pir)
+ {
+ if(!*pir)
+ return;
+
+ ir_dereference_array* orig_deref = (*pir)->as_dereference_array();
+ if (orig_deref && !orig_deref->array_index->as_constant()
+ && (orig_deref->array->type->is_array() || orig_deref->array->type->is_matrix()))
+ {
+ ir_variable* var = convert_dereference_array(orig_deref, 0);
+ assert(var);
+ *pir = new(base_ir) ir_dereference_variable(var);
+ this->progress = true;
+ }
+ }
+
+ ir_visitor_status
+ visit_leave(ir_assignment *ir)
+ {
+ ir_rvalue_visitor::visit_leave(ir);
+
+ ir_dereference_array *orig_deref = ir->lhs->as_dereference_array();
+
+ if (orig_deref && !orig_deref->array_index->as_constant()
+ && (orig_deref->array->type->is_array() || orig_deref->array->type->is_matrix()))
+ {
+ convert_dereference_array(orig_deref, ir->rhs);
+ ir->remove();
+ this->progress = true;
+ }
+
+ return visit_continue;
+ }
+};
+
+bool
+do_array_index_to_cond_assign(exec_list *instructions)
+{
+ ir_array_index_to_cond_assign_visitor v;
+
+ visit_list_elements(&v, instructions);
+
+ return v.progress;
+}
diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h
index cba2976..8cb46b3 100644
--- a/src/glsl/ir_optimization.h
+++ b/src/glsl/ir_optimization.h
@@ -31,6 +31,7 @@
bool do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iterations, bool robust_access);
bool do_algebraic(exec_list *instructions);
+bool do_array_index_to_cond_assign(exec_list *instructions);
bool do_constant_folding(exec_list *instructions);
bool do_constant_variable(exec_list *instructions);
bool do_constant_variable_unlinked(exec_list *instructions);
diff --git a/src/glsl/ir_structure_splitting.cpp b/src/glsl/ir_structure_splitting.cpp
index ff3ec93..1925067 100644
--- a/src/glsl/ir_structure_splitting.cpp
+++ b/src/glsl/ir_structure_splitting.cpp
@@ -86,6 +86,7 @@ public:
virtual ir_visitor_status visit(ir_variable *);
virtual ir_visitor_status visit(ir_dereference_variable *);
virtual ir_visitor_status visit_enter(ir_dereference_record *);
+ virtual ir_visitor_status visit_enter(ir_dereference_array *);
virtual ir_visitor_status visit_enter(ir_assignment *);
virtual ir_visitor_status visit_enter(ir_function_signature *);
@@ -102,7 +103,9 @@ ir_structure_reference_visitor::get_variable_entry2(ir_variable *var)
{
assert(var);
- if (!var->type->is_record() || var->mode == ir_var_uniform)
+ printf("stru %s\n", var->name);
+ if ((!var->type->is_record() && !var->type->is_array())
+ || (var->mode != ir_var_auto && var->mode != ir_var_temporary))
return NULL;
foreach_iter(exec_list_iterator, iter, this->variable_list) {
@@ -149,6 +152,25 @@ ir_structure_reference_visitor::visit_enter(ir_dereference_record *ir)
}
ir_visitor_status
+ir_structure_reference_visitor::visit_enter(ir_dereference_array *ir)
+{
+ ir->array_index->accept(this);
+ if(!ir->array_index->as_constant())
+ {
+ /* FINISHME: could produce and make use of information
+ * about possible values of the index
+ */
+ ir_variable *const var = ir->array->variable_referenced();
+ variable_entry2 *entry = this->get_variable_entry2(var);
+
+ if (entry)
+ entry->whole_structure_access++;
+ }
+
+ /* Don't descend into the ir_dereference_variable below. */
+ return visit_continue_with_parent;
+}
+ir_visitor_status
ir_structure_reference_visitor::visit_enter(ir_assignment *ir)
{
if (ir->lhs->as_dereference_variable() &&
@@ -198,7 +220,7 @@ ir_structure_splitting_visitor::get_splitting_entry(ir_variable *var)
{
assert(var);
- if (!var->type->is_record())
+ if (!var->type->is_record() && !var->type->is_array())
return NULL;
foreach_iter(exec_list_iterator, iter, *this->variable_list) {
@@ -214,27 +236,62 @@ ir_structure_splitting_visitor::get_splitting_entry(ir_variable *var)
void
ir_structure_splitting_visitor::split_deref(ir_dereference **deref)
{
- if ((*deref)->ir_type != ir_type_dereference_record)
- return;
-
- ir_dereference_record *deref_record = (ir_dereference_record *)*deref;
- ir_dereference_variable *deref_var = deref_record->record->as_dereference_variable();
- if (!deref_var)
- return;
-
- variable_entry2 *entry = get_splitting_entry(deref_var->var);
- if (!entry)
- return;
+ if ((*deref)->ir_type == ir_type_dereference_record)
+ {
+ ir_dereference_record *deref_record = (ir_dereference_record *)*deref;
+ ir_dereference_variable *deref_var = deref_record->record->as_dereference_variable();
+ if (!deref_var)
+ return;
+
+ variable_entry2 *entry = get_splitting_entry(deref_var->var);
+ if (!entry)
+ return;
+
+ unsigned int i;
+ for (i = 0; i < entry->var->type->length; i++) {
+ if (strcmp(deref_record->field,
+ entry->var->type->fields.structure[i].name) == 0)
+ break;
+ }
+ assert(i != entry->var->type->length);
- unsigned int i;
- for (i = 0; i < entry->var->type->length; i++) {
- if (strcmp(deref_record->field,
- entry->var->type->fields.structure[i].name) == 0)
- break;
+ *deref = new(entry->mem_ctx) ir_dereference_variable(entry->components[i]);
+ }
+ else if ((*deref)->ir_type == ir_type_dereference_array)
+ {
+ ir_dereference_array *deref_array = (ir_dereference_array*)*deref;
+ ir_dereference_variable *deref_var = deref_array->array->as_dereference_variable();
+ if (!deref_var)
+ return;
+
+ variable_entry2 *entry = get_splitting_entry(deref_var->var);
+ if (!entry)
+ return;
+
+ ir_constant* index = deref_array->array_index->as_constant();
+ assert(index);
+ assert(index->type->is_scalar());
+ assert(index->type->base_type == GLSL_TYPE_INT || index->type->base_type == GLSL_TYPE_UINT);
+
+ unsigned i = index->value.u[0];
+ if(i < (unsigned)deref_var->var->type->length)
+ {
+ *deref = new(entry->mem_ctx) ir_dereference_variable(entry->components[i]);
+ }
+ else
+ {
+ ir_variable* undef = new(entry->mem_ctx) ir_variable((*deref)->type, "undef", ir_var_temporary);
+ base_ir->insert_before(undef);
+ *deref = new(entry->mem_ctx) ir_dereference_variable(undef);
+#if 0
+ /* FINISHME: add an "undef" value to the ir and use it, or perhaps just kill base_ir directly */
+ if(type->is_numeric() || type->is_boolean())
+ *deref = ir_constant::zero(entry->mem_ctx, (*deref)->type);
+ else
+ *deref = new(entry->mem_ctx) ir_dereference_variable(entry->components[0]);
+#endif
+ }
}
- assert(i != entry->var->type->length);
-
- *deref = new(entry->mem_ctx) ir_dereference_variable(entry->components[i]);
}
void
@@ -268,19 +325,30 @@ ir_structure_splitting_visitor::visit_leave(ir_assignment *ir)
if (lhs_entry) {
new_lhs = new(mem_ctx) ir_dereference_variable(lhs_entry->components[i]);
- } else {
+ } else if(type->is_record()) {
new_lhs = new(mem_ctx)
ir_dereference_record(ir->lhs->clone(mem_ctx, NULL),
type->fields.structure[i].name);
- }
+ } else if(type->is_array()) {
+ new_lhs = new(mem_ctx)
+ ir_dereference_array(ir->lhs->clone(mem_ctx, NULL),
+ new(mem_ctx) ir_constant((int)i));
+ } else
+ assert(0);
if (rhs_entry) {
new_rhs = new(mem_ctx) ir_dereference_variable(rhs_entry->components[i]);
- } else {
+ } else if(type->is_record()){
new_rhs = new(mem_ctx)
ir_dereference_record(ir->rhs->clone(mem_ctx, NULL),
type->fields.structure[i].name);
- }
+ } else if(type->is_array()) {
+ new_rhs = new(mem_ctx)
+ ir_dereference_array(ir->rhs->clone(mem_ctx, NULL),
+ new(mem_ctx) ir_constant((int)i));
+ } else
+ assert(0);
+
ir->insert_before(new(mem_ctx) ir_assignment(new_lhs,
new_rhs,
@@ -337,18 +405,39 @@ do_structure_splitting(exec_list *instructions)
ir_variable *,
type->length);
+ /* FINISHME: create these on demand */
for (unsigned int i = 0; i < entry->var->type->length; i++) {
- const char *name = talloc_asprintf(mem_ctx, "%s_%s",
+ const char *name;
+
+ if(type->is_record())
+ {
+ name = talloc_asprintf(mem_ctx, "%s_%s",
entry->var->name,
type->fields.structure[i].name);
- entry->components[i] =
- new(entry->mem_ctx) ir_variable(type->fields.structure[i].type,
- name,
- ir_var_temporary);
+ entry->components[i] =
+ new(entry->mem_ctx) ir_variable(type->fields.structure[i].type,
+ name,
+ ir_var_temporary);
+ }
+ else if(type->is_array())
+ {
+ name = talloc_asprintf(mem_ctx, "%s_%i",
+ entry->var->name,
+ i);
+
+ entry->components[i] =
+ new(entry->mem_ctx) ir_variable(type->fields.array,
+ name,
+ ir_var_temporary);
+ }
+ else
+ assert(0);
+
entry->var->insert_before(entry->components[i]);
}
+ printf("SPLIT %s\n", entry->var->name);
entry->var->remove();
}
diff --git a/src/glsl/main.cpp b/src/glsl/main.cpp
index 4d46730..b7c9335 100644
--- a/src/glsl/main.cpp
+++ b/src/glsl/main.cpp
@@ -182,6 +182,9 @@ compile_shader(struct gl_shader *shader)
progress = set_loop_controls(shader->ir, ls) || progress;
progress = unroll_loops(shader->ir, ls, 32) || progress;
delete ls;
+
+ progress = do_array_index_to_cond_assign(shader->ir) || progress;
+ progress = do_structure_splitting(shader->ir) || progress;
} while (progress);
validate_ir_tree(shader->ir);
More information about the mesa-commit
mailing list