glsl: teach loop analysis that array dereferences are bounds on the index (v3)

Changes in v3:
- Only look for array dereferences in code that always executes, to avoid
  miscompilation

Changes in v2:
- Incorporate Ian Romanick's feedback
- Make GL_CONTEXT_FLAG_ROBUST_ACCESS_BIT_ARB disable this

Since out-of-bounds dereferences cause undefined behavior, we are allowed
to assume that they terminate the loop, if my interpretation of the GLSL
spec is correct.

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.

8 files changed, 92 insertions, 17 deletions

diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp
index 4ac062b42c..44e456be7a 100644
--- a/src/glsl/glsl_parser_extras.cpp
+++ b/src/glsl/glsl_parser_extras.cpp
@@ -685,7 +685,7 @@ ast_struct_specifier::ast_struct_specifier(char *identifier,
 }
 
 bool
-do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iterations)
+do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iterations, bool robust_access)
 {
    GLboolean progress = GL_FALSE;
 
@@ -718,7 +718,7 @@ do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iteration
 
    progress = optimize_redundant_jumps(ir) || progress;
 
-   loop_state *ls = analyze_loop_variables(ir);
+   loop_state *ls = analyze_loop_variables(ir, !robust_access);
    progress = set_loop_controls(ir, ls) || progress;
    progress = unroll_loops(ir, ls, max_unroll_iterations) || progress;
    delete ls;
diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h
index 8dbc6ed31a..02a7f37613 100644
--- a/src/glsl/ir_optimization.h
+++ b/src/glsl/ir_optimization.h
@@ -28,7 +28,7 @@
  * Prototypes for optimization passes to be called by the compiler and drivers.
  */
 
-bool do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iterations);
+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);
diff --git a/src/glsl/linker.cpp b/src/glsl/linker.cpp
index c2c662152e..8567efe28d 100644
--- a/src/glsl/linker.cpp
+++ b/src/glsl/linker.cpp
@@ -1471,7 +1471,7 @@ link_shaders(GLcontext *ctx, struct gl_shader_program *prog)
     * some of that unused.
     */
    for (unsigned i = 0; i < prog->_NumLinkedShaders; i++) {
-      while (do_common_optimization(prog->_LinkedShaders[i]->ir, true, 32))
+      while (do_common_optimization(prog->_LinkedShaders[i]->ir, true, 32, true))
 	 ;
    }
 
diff --git a/src/glsl/loop_analysis.cpp b/src/glsl/loop_analysis.cpp
index 687825cc93..d39e1b4839 100644
--- a/src/glsl/loop_analysis.cpp
+++ b/src/glsl/loop_analysis.cpp
@@ -64,6 +64,67 @@ bool contains_continue(ir_instruction* ir)
    return visitor.contains_continue;
 }
 
+struct dereference_array_visitor : public ir_hierarchical_visitor
+{
+   loop_variable_state* ls;
+
+   dereference_array_visitor(loop_variable_state* ls)
+   {
+      this->ls = ls;
+   }
+
+   ir_visitor_status visit_leave(ir_dereference_array *ir)
+   {
+      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);
+
+      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));
+      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 visit_enter(ir_if *ir)
+   {
+      ir->condition->accept(this);
+
+      /* do not visit conditionally executed code */
+      return visit_continue_with_parent;
+   }
+
+   ir_visitor_status visit_enter(ir_loop *ir)
+   {
+      /* FINISHME: perhaps we could allow this? */
+      return visit_continue_with_parent;
+   }
+};
+
+void visit_dereference_arrays(loop_variable_state* ls, ir_instruction* ir)
+{
+   dereference_array_visitor visitor(ls);
+   ir->accept(&visitor);
+}
+
 loop_state::loop_state()
 {
    this->ht = hash_table_ctor(0, hash_table_pointer_hash,
@@ -144,6 +205,8 @@ public:
    virtual ir_visitor_status visit_enter(ir_if *);
    virtual ir_visitor_status visit_leave(ir_if *);
 
+   bool out_of_bounds_can_break;
+
    loop_state *loops;
 
    int if_statement_depth;
@@ -249,6 +312,9 @@ loop_analysis::visit_leave(ir_loop *ir)
       if(contains_continue((ir_instruction*) node))
          break;
 
+      if(out_of_bounds_can_break)
+         visit_dereference_arrays(ls, (ir_instruction*)node);
+
       ir_if *if_stmt = ((ir_instruction *) node)->as_if();
 
       if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
@@ -527,9 +593,10 @@ is_loop_terminator(ir_if *ir)
 
 
 loop_state *
-analyze_loop_variables(exec_list *instructions)
+analyze_loop_variables(exec_list *instructions, bool out_of_bounds_can_break)
 {
    loop_analysis v;
+   v.out_of_bounds_can_break = out_of_bounds_can_break;
 
    v.run(instructions);
    return v.loops;
diff --git a/src/glsl/loop_analysis.h b/src/glsl/loop_analysis.h
index 7b0511fbbe..ef925aead1 100644
--- a/src/glsl/loop_analysis.h
+++ b/src/glsl/loop_analysis.h
@@ -33,7 +33,7 @@
  * Analyze and classify all variables used in all loops in the instruction list
  */
 extern class loop_state *
-analyze_loop_variables(exec_list *instructions);
+analyze_loop_variables(exec_list *instructions, bool out_of_bounds_can_break);
 
 
 /**
diff --git a/src/glsl/loop_controls.cpp b/src/glsl/loop_controls.cpp
index 9619d8ae55..35ff4c2d53 100644
--- a/src/glsl/loop_controls.cpp
+++ b/src/glsl/loop_controls.cpp
@@ -253,18 +253,24 @@ loop_control_visitor::visit_leave(ir_loop *ir)
 		     ir->cmp = cmp;
 
 		     max_iterations = iterations;
+
+		     this->progress = true;
 		  }
 
-		  /* Remove the conditional break statement.  The loop
-		   * controls are now set such that the exit condition will be
-		   * satisfied.
-		   */
-		  if_stmt->remove();
+		  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--;
+                     assert(ls->num_loop_jumps > 0);
+                     ls->num_loop_jumps--;
 
-		  this->progress = true;
+                     this->progress = true;
+		  }
 	       }
 
 	       break;
diff --git a/src/glsl/main.cpp b/src/glsl/main.cpp
index bfa1b71ff9..dddc181e32 100644
--- a/src/glsl/main.cpp
+++ b/src/glsl/main.cpp
@@ -148,6 +148,7 @@ int glsl_es = 0;
 int dump_ast = 0;
 int dump_hir = 0;
 int dump_lir = 0;
+int robustness = 0;
 int do_link = 0;
 
 const struct option compiler_opts[] = {
@@ -155,6 +156,7 @@ const struct option compiler_opts[] = {
    { "dump-ast", 0, &dump_ast, 1 },
    { "dump-hir", 0, &dump_hir, 1 },
    { "dump-lir", 0, &dump_lir, 1 },
+   { "robustness", 0, &robustness, 1 },
    { "link",     0, &do_link,  1 },
    { NULL, 0, NULL, 0 }
 };
@@ -213,7 +215,7 @@ compile_shader(GLcontext *ctx, struct gl_shader *shader)
 	 progress = do_vec_index_to_cond_assign(shader->ir) || progress;
 	 progress = do_swizzle_swizzle(shader->ir) || progress;
 
-	 loop_state *ls = analyze_loop_variables(shader->ir);
+	 loop_state *ls = analyze_loop_variables(shader->ir, !robustness);
 	 progress = set_loop_controls(shader->ir, ls) || progress;
 	 progress = unroll_loops(shader->ir, ls, 32) || progress;
 	 delete ls;
diff --git a/src/mesa/program/ir_to_mesa.cpp b/src/mesa/program/ir_to_mesa.cpp
index 2edf01bb8f..41ff561a7e 100644
--- a/src/mesa/program/ir_to_mesa.cpp
+++ b/src/mesa/program/ir_to_mesa.cpp
@@ -2737,7 +2737,7 @@ _mesa_ir_link_shader(GLcontext *ctx, struct gl_shader_program *prog)
 
 	 progress = do_lower_jumps(ir, true, true, options->EmitNoMainReturn, options->EmitNoCont, options->EmitNoLoops) || progress;
 
-	 progress = do_common_optimization(ir, true, options->MaxUnrollIterations) || progress;
+	 progress = do_common_optimization(ir, true, options->MaxUnrollIterations, !!(ctx->Const.ContextFlags & GL_CONTEXT_FLAG_ROBUST_ACCESS_BIT_ARB)) || progress;
 
 	 if (options->EmitNoIfs)
 	    progress = do_if_to_cond_assign(ir) || progress;
@@ -2820,7 +2820,7 @@ _mesa_glsl_compile_shader(GLcontext *ctx, struct gl_shader *shader)
       /* Do some optimization at compile time to reduce shader IR size
        * and reduce later work if the same shader is linked multiple times
        */
-      while (do_common_optimization(shader->ir, false, 32))
+      while (do_common_optimization(shader->ir, false, 32, true))
 	 ;
 
       validate_ir_tree(shader->ir);