[Mesa-dev] Mesa (shader-work): glsl: teach loop analysis that array dereferences are bounds on the index
Ian Romanick
idr at freedesktop.org
Tue Sep 7 19:06:31 PDT 2010
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Luca Barbieri wrote:
> Module: Mesa
> Branch: shader-work
> Commit: 2ecf7b5cd5067d80cb6ce74d55b2ed93c974d8dc
> URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=2ecf7b5cd5067d80cb6ce74d55b2ed93c974d8dc
>
> Author: Luca Barbieri <luca at luca-barbieri.com>
> Date: Tue Sep 7 19:29:00 2010 +0200
>
> glsl: teach loop analysis that array dereferences are bounds on the index
>
> Since out-of-bounds dereferences cause undefined behavior, we are allowed
> to assume that they terminate the loop.
Clever. :)
Technically speaking only the access to the array has undefined
behavior, and that undefined behavior does not include program
termination. I'm a bit nervous / suspicious that there may be some app
out there that relies on the loop running too many times. I wonder if
there should be a flag to disable this particular optimization.
> This allows to find the maximum number of iterations in cases like this:
>
> uniform int texcoords;
> float4 gl_TexCoord[8];
>
> for(i = 0; i < texcoords; ++i)
> do_something_with(gl_TexCoord[i]);
The code as written will work with loops like this, but I believe that
it will miss loops like:
uniform int foo;
vec4 gl_TexCoord[8];
for (i = 0; i < foo; i++) {
int j = i * 2;
do_something_with(gl_TexCoord[j], gl_TexCoord[j+1]);
}
This isn't because of this code, but it's because ir_loop_analysis
doesn't identify j as a loop induction variable.
You keep stumbling across things on my todo list. :)
> This is apparently an interesting case since NV_fragment_program2 has
> a construct for this.
>
> ---
>
> src/glsl/loop_analysis.cpp | 51 ++++++++++++++++++++++++++++++++++++++++++++
> src/glsl/loop_controls.cpp | 29 ++++++++++++++++--------
> 2 files changed, 70 insertions(+), 10 deletions(-)
>
> diff --git a/src/glsl/loop_analysis.cpp b/src/glsl/loop_analysis.cpp
> index 32e8b8c..87ed7b7 100644
> --- a/src/glsl/loop_analysis.cpp
> +++ b/src/glsl/loop_analysis.cpp
> @@ -105,6 +105,7 @@ public:
>
> virtual ir_visitor_status visit(ir_loop_jump *);
> virtual ir_visitor_status visit(ir_dereference_variable *);
> + virtual ir_visitor_status visit_leave(ir_dereference_array *);
>
> virtual ir_visitor_status visit_enter(ir_loop *);
> virtual ir_visitor_status visit_leave(ir_loop *);
> @@ -164,6 +165,7 @@ loop_analysis::visit(ir_dereference_variable *ir)
>
> if (lv == NULL) {
> lv = ls->insert(var);
> + /* FINISHME XXX: seems wrong, what if this is gl_TexCoord[i] =, and this is the deref of i ? */
> lv->read_before_write = !this->in_assignee;
The in_assignee flag is cleared when entering the array index. See
ir_assignment::accept in ir_hv_accept.cpp.
> }
>
> @@ -191,6 +193,55 @@ loop_analysis::visit(ir_dereference_variable *ir)
> }
>
> ir_visitor_status
> +loop_analysis::visit_leave(ir_dereference_array *ir)
> +{
> + /* If we're not somewhere inside a loop, there's nothing to do.
> + */
> + if (this->state.is_empty())
> + return visit_continue_with_parent;
I fixed this bug in loop_analysis::visit(ir_dereference_variable *)
earlier today. See commit 956f049f.
> +
> + loop_variable_state *const ls =
> + (loop_variable_state *) this->state.get_head();
> +
> + int max_index;
> + if(ir->array->type->is_array())
> + max_index = ir->array->type->length - 1;
> + else if(ir->array->type->is_vector() || ir->array->type->is_matrix())
> + max_index = ir->array->type->components() - 1;
> + else
> + assert(0);
> +
> + ir_constant* max_index_c;
> + ir_constant* zero_c;
> + switch(ir->array_index->type->base_type)
> + {
> + case GLSL_TYPE_INT:
> + max_index_c = new(ir) ir_constant((int)max_index);
> + zero_c = new(ir) ir_constant((int)0);
> + break;
> + case GLSL_TYPE_UINT:
> + max_index_c = new(ir) ir_constant((unsigned)max_index);
> + zero_c = new(ir) ir_constant((unsigned)0);
> + break;
> + default:
> + assert(0);
> + }
How about:
assert(ir->array_index->type->is_integer());
ir_constant *const max_index_c =
(ir->array_index->type->base_type == GLSL_TYPE_UINT)
? new(ir) ir_constant((unsigned)max_index)
: new(ir) ir_constant((int)max_index);
ir_constant *const zero_c =
ir_constant::zero(ir, ir->array_index->type);
> +
> + ir_if* bound_if;
> +
> + bound_if = new (ir) ir_if(new(ir) ir_expression(ir_binop_greater, ir->array_index->type, ir->array_index, max_index_c));
Shouldn't this be ir_binop_gequal?
> + bound_if->self_link();
This is weird. Why not insert the new instructions at the top of the
loop? It seems like it would be better just store the minimum and
maximum "allowed" value for the variable in its entry in loop_variable.
This ought to simplify the follow-on patches as well. I think the key
observation is that this trick only works on variable identified as loop
induction variables.
> + ls->insert(bound_if);
> +
> + bound_if = new (ir) ir_if(new(ir) ir_expression(ir_binop_less, ir->array_index->type, ir->array_index, zero_c));
> + bound_if->self_link();
> + ls->insert(bound_if);
> +
> + return visit_continue;
> +}
> +
> +
> +ir_visitor_status
> loop_analysis::visit_enter(ir_loop *ir)
> {
> loop_variable_state *ls = this->loops->insert(ir);
> diff --git a/src/glsl/loop_controls.cpp b/src/glsl/loop_controls.cpp
> index 9619d8a..e6e8a5b 100644
> --- a/src/glsl/loop_controls.cpp
> +++ b/src/glsl/loop_controls.cpp
> @@ -253,18 +253,27 @@ loop_control_visitor::visit_leave(ir_loop *ir)
> ir->cmp = cmp;
>
> max_iterations = iterations;
> - }
> -
> - /* Remove the conditional break statement. The loop
> - * controls are now set such that the exit condition will be
> - * satisfied.
> - */
> - if_stmt->remove();
>
> - assert(ls->num_loop_jumps > 0);
> - ls->num_loop_jumps--;
> + this->progress = true;
> + }
>
> - this->progress = true;
> + if(if_stmt->next == if_stmt->prev && if_stmt->next == if_stmt)
> + {
> + /* this is a fake if with self_link() inserted to represent array bounds: ignore it */
> + }
> + else
> + {
Everywhere else in the compiler puts the { and } on the same line as the
if or the else.
> + /* Remove the conditional break statement. The loop
> + * controls are now set such that the exit condition will be
> + * satisfied.
> + */
> + if_stmt->remove();
> +
> + assert(ls->num_loop_jumps > 0);
> + ls->num_loop_jumps--;
> +
> + this->progress = true;
> + }
> }
>
> break;
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAkyG76QACgkQX1gOwKyEAw+nXQCeP9N1tDf1PoYj4c9MtlQxqqeu
L2sAn13LjvGKbEr+fr9VALlZvIxUeS7x
=QqRM
-----END PGP SIGNATURE-----
More information about the mesa-dev
mailing list