glsl/loops: Move some analysis from loop_controls to loop_analysis.

Previously, the sole responsibility of loop_analysis was to find all
the variables referenced in the loop that are either loop constant or
induction variables, and find all of the simple if statements that
might terminate the loop.  The remainder of the analysis necessary to
determine how many times a loop executed was performed by
loop_controls.

This patch makes loop_analysis also responsible for determining the
number of iterations after which each loop terminator will terminate
the loop, and for figuring out which terminator will terminate the
loop first (I'm calling this the "limiting terminator").

This will allow loop unrolling to make use of information that was
previously only visible from loop_controls, namely the identity of the
limiting terminator.

Reviewed-by: Ian Romanick <ian.d.romanick@intel.com>

diff --git a/src/glsl/loop_analysis.cpp b/src/glsl/loop_analysis.cpp
index 302e931234f1486030ae2ca12e370920366a8393..fd2b6c923681a79fec01e0e15e3fd199ba545a11 100644 (file)
--- a/src/glsl/loop_analysis.cpp
+++ b/src/glsl/loop_analysis.cpp
@@ -396,6 +396,75 @@ loop_analysis::visit_leave(ir_loop *ir)
       }
    }
 
+   /* Search the loop terminating conditions for those of the form 'i < c'
+    * where i is a loop induction variable, c is a constant, and < is any
+    * relative operator.  From each of these we can infer an iteration count.
+    * Also figure out which terminator (if any) produces the smallest
+    * iteration count--this is the limiting terminator.
+    */
+   foreach_list(node, &ls->terminators) {
+      loop_terminator *t = (loop_terminator *) node;
+      ir_if *if_stmt = t->ir;
+
+      /* If-statements can be either 'if (expr)' or 'if (deref)'.  We only care
+       * about the former here.
+       */
+      ir_expression *cond = if_stmt->condition->as_expression();
+      if (cond == NULL)
+        continue;
+
+      switch (cond->operation) {
+      case ir_binop_less:
+      case ir_binop_greater:
+      case ir_binop_lequal:
+      case ir_binop_gequal: {
+        /* The expressions that we care about will either be of the form
+         * 'counter < limit' or 'limit < counter'.  Figure out which is
+         * which.
+         */
+        ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
+        ir_constant *limit = cond->operands[1]->as_constant();
+        enum ir_expression_operation cmp = cond->operation;
+
+        if (limit == NULL) {
+           counter = cond->operands[1]->as_dereference_variable();
+           limit = cond->operands[0]->as_constant();
+
+           switch (cmp) {
+           case ir_binop_less:    cmp = ir_binop_greater; break;
+           case ir_binop_greater: cmp = ir_binop_less;    break;
+           case ir_binop_lequal:  cmp = ir_binop_gequal;  break;
+           case ir_binop_gequal:  cmp = ir_binop_lequal;  break;
+           default: assert(!"Should not get here.");
+           }
+        }
+
+        if ((counter == NULL) || (limit == NULL))
+           break;
+
+        ir_variable *var = counter->variable_referenced();
+
+        ir_rvalue *init = find_initial_value(ir, var);
+
+         loop_variable *lv = ls->get(var);
+         if (lv != NULL && lv->is_induction_var()) {
+            t->iterations = calculate_iterations(init, limit, lv->increment,
+                                                 cmp);
+
+            if (t->iterations >= 0 &&
+                (ls->limiting_terminator == NULL ||
+                 t->iterations < ls->limiting_terminator->iterations)) {
+               ls->limiting_terminator = t;
+            }
+         }
+         break;
+      }
+
+      default:
+         break;
+      }
+   }
+
    return visit_continue;
 }
 

diff --git a/src/glsl/loop_analysis.h b/src/glsl/loop_analysis.h
index 8e57dacbf6b6beb9b92465cdd172aab6c029ac19..0208890b1fd9df5f00cde537caf81126034e0cbe 100644 (file)
--- a/src/glsl/loop_analysis.h
+++ b/src/glsl/loop_analysis.h
@@ -58,6 +58,13 @@ set_loop_controls(exec_list *instructions, loop_state *ls);
 extern bool
 unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations);
 
+ir_rvalue *
+find_initial_value(ir_loop *loop, ir_variable *var);
+
+int
+calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
+                    enum ir_expression_operation op);
+
 
 /**
  * Tracking for all variables used in a loop
@@ -98,6 +105,14 @@ public:
     */
    exec_list terminators;
 
+   /**
+    * If any of the terminators in \c terminators leads to termination of the
+    * loop after a constant number of iterations, this is the terminator that
+    * leads to termination after the smallest number of iterations.  Otherwise
+    * NULL.
+    */
+   loop_terminator *limiting_terminator;
+
    /**
     * Hash table containing all variables accessed in this loop
     */
@@ -129,6 +144,7 @@ public:
       this->contains_calls = false;
       this->var_hash = hash_table_ctor(0, hash_table_pointer_hash,
                                       hash_table_pointer_compare);
+      this->limiting_terminator = NULL;
    }
 
    ~loop_variable_state()
@@ -227,7 +243,21 @@ public:
 
 class loop_terminator : public exec_node {
 public:
+   loop_terminator()
+      : ir(NULL), iterations(-1)
+   {
+   }
+
+   /**
+    * Statement which terminates the loop.
+    */
    ir_if *ir;
+
+   /**
+    * The number of iterations after which the terminator is known to
+    * terminate the loop (if that is a fixed value).  Otherwise -1.
+    */
+   int iterations;
 };
 
 

diff --git a/src/glsl/loop_controls.cpp b/src/glsl/loop_controls.cpp
index ce05e09a6ab890575b4824ebe28a3614975f63bd..a14ea6ba6be2f44d498a1a23243f0ec5050d90f3 100644 (file)
--- a/src/glsl/loop_controls.cpp
+++ b/src/glsl/loop_controls.cpp
@@ -183,9 +183,9 @@ loop_control_visitor::visit_leave(ir_loop *ir)
       return visit_continue;
    }
 
-   /* Search the loop terminating conditions for one of the form 'i < c' where
-    * i is a loop induction variable, c is a constant, and < is any relative
-    * operator.
+   /* Figure out how many times the loop will run based on the iteration count
+    * annotations made by loop analysis, and give the loop a normative bound
+    * if possible.
     */
    unsigned max_iterations =
       ls->max_iterations < 0 ? INT_MAX : ls->max_iterations;
@@ -193,86 +193,32 @@ loop_control_visitor::visit_leave(ir_loop *ir)
    if (ir->normative_bound >= 0)
       max_iterations = ir->normative_bound;
 
+   /* If the limiting terminator has a lower iteration count than we'd
+    * previously inferred for this loop, then make the new iteration count the
+    * normative bound for this loop.
+    */
+   if (ls->limiting_terminator != NULL &&
+       (unsigned) ls->limiting_terminator->iterations < max_iterations) {
+      ir->normative_bound = ls->limiting_terminator->iterations;
+      max_iterations = ls->limiting_terminator->iterations;
+   }
+
+   /* Remove the conditional break statements associated with all terminators
+    * that are associated with a fixed iteration count; the normative bound
+    * will take care of terminating the loop.
+    */
    foreach_list(node, &ls->terminators) {
       loop_terminator *t = (loop_terminator *) node;
-      ir_if *if_stmt = t->ir;
-
-      /* If-statements can be either 'if (expr)' or 'if (deref)'.  We only care
-       * about the former here.
-       */
-      ir_expression *cond = if_stmt->condition->as_expression();
-      if (cond == NULL)
-        continue;
-
-      switch (cond->operation) {
-      case ir_binop_less:
-      case ir_binop_greater:
-      case ir_binop_lequal:
-      case ir_binop_gequal: {
-        /* The expressions that we care about will either be of the form
-         * 'counter < limit' or 'limit < counter'.  Figure out which is
-         * which.
-         */
-        ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
-        ir_constant *limit = cond->operands[1]->as_constant();
-        enum ir_expression_operation cmp = cond->operation;
-
-        if (limit == NULL) {
-           counter = cond->operands[1]->as_dereference_variable();
-           limit = cond->operands[0]->as_constant();
-
-           switch (cmp) {
-           case ir_binop_less:    cmp = ir_binop_greater; break;
-           case ir_binop_greater: cmp = ir_binop_less;    break;
-           case ir_binop_lequal:  cmp = ir_binop_gequal;  break;
-           case ir_binop_gequal:  cmp = ir_binop_lequal;  break;
-           default: assert(!"Should not get here.");
-           }
-        }
-
-        if ((counter == NULL) || (limit == NULL))
-           break;
-
-        ir_variable *var = counter->variable_referenced();
-
-        ir_rvalue *init = find_initial_value(ir, var);
-
-         loop_variable *lv = ls->get(var);
-         if (lv != NULL && lv->is_induction_var()) {
-            const int iterations = calculate_iterations(init, limit,
-                                                        lv->increment,
-                                                        cmp);
-            if (iterations >= 0) {
-               /* If the new iteration count is lower than the previously
-                * believed iteration count, then add a normative bound to
-                * this loop.
-                */
-               if ((unsigned) iterations < max_iterations) {
-                  ir->normative_bound = iterations;
-
-                  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;
-            }
-
-            break;
-         }
-        break;
-      }
 
-      default:
-        break;
-      }
+      if (t->iterations < 0)
+         continue;
+
+      t->ir->remove();
+
+      assert(ls->num_loop_jumps > 0);
+      ls->num_loop_jumps--;
+
+      this->progress = true;
    }
 
    /* If we have proven the one of the loop exit conditions is satisifed before