Mesa (shader-work): glsl: teach loop analysis that array dereferences are bounds on the index

[Luca Barbieri]

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.

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]);

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;
    }
 
@@ -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;
+
+   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);
+   }
+
+   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));
+   bound_if->self_link();
+   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
+		  {
+                     /* 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;