Mesa (master): loop_unroll: unroll loops with (lowered) breaks

[Ian Romanick]

Module: Mesa
Branch: master
Commit: 2cdbced10d98214616bcc5f960b21185c433d23b
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=2cdbced10d98214616bcc5f960b21185c433d23b

Author: Luca Barbieri <luca at luca-barbieri.com>
Date:   Tue Sep  7 17:03:43 2010 +0200

loop_unroll: unroll loops with (lowered) breaks

If the loop ends with an if with one break or in a single break unroll
it.  Loops that end with a continue will have that continue removed by
the redundant jump optimizer.  Likewise loops that end with an
if-statement with a break at the end of both branches will have the
break pulled out after the if-statement.

Loops of the form

   for (...) {
      do_something1();
      if (cond) {
	 do_something2();
	 break;
      } else {
	 do_something3();
      }
   }

will be unrolled as

   do_something1();
   if (cond) {
      do_something2();
   } else {
      do_something3();
      do_something1();
      if (cond) {
	 do_something2();
      } else {
	 do_something3();
	 /* Repeat inserting iterations here.*/
      }
   }

ir_lower_jumps can guarantee that all loops are put in this form
and thus all loops are now potentially unrollable if an upper bound
on the number of iterations can be found.

Signed-off-by: Ian Romanick <ian.d.romanick at intel.com>

---

 src/glsl/loop_unroll.cpp |   93 ++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 89 insertions(+), 4 deletions(-)

diff --git a/src/glsl/loop_unroll.cpp b/src/glsl/loop_unroll.cpp
index 80f9217..90797bd 100644
--- a/src/glsl/loop_unroll.cpp
+++ b/src/glsl/loop_unroll.cpp
@@ -47,6 +47,7 @@ ir_visitor_status
 loop_unroll_visitor::visit_leave(ir_loop *ir)
 {
    loop_variable_state *const ls = this->state->get(ir);
+   int iterations;
 
    /* If we've entered a loop that hasn't been analyzed, something really,
     * really bad has happened.
@@ -56,23 +57,107 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
       return visit_continue;
    }
 
+   iterations = ls->max_iterations;
+
    /* Don't try to unroll loops where the number of iterations is not known
     * at compile-time.
     */
-   if (ls->max_iterations < 0)
+   if (iterations < 0)
       return visit_continue;
 
    /* Don't try to unroll loops that have zillions of iterations either.
     */
-   if (ls->max_iterations > max_iterations)
+   if (iterations > max_iterations)
       return visit_continue;
 
-   if (ls->num_loop_jumps > 0)
+   if (ls->num_loop_jumps > 1)
       return visit_continue;
+   else if (ls->num_loop_jumps) {
+      /* recognize loops in the form produced by ir_lower_jumps */
+      ir_instruction *last_ir =
+	 ((ir_instruction*)ir->body_instructions.get_tail());
+
+      assert(last_ir != NULL);
+
+      ir_if *last_if = last_ir->as_if();
+      if (last_if) {
+	 bool continue_from_then_branch;
+
+	 /* Determine which if-statement branch, if any, ends with a break.
+	  * The branch that did *not* have the break will get a temporary
+	  * continue inserted in each iteration of the loop unroll.
+	  *
+	  * Note that since ls->num_loop_jumps is <= 1, it is impossible for
+	  * both branches to end with a break.
+	  */
+	 ir_instruction *last =
+	    (ir_instruction *) last_if->then_instructions.get_tail();
+
+	 if (last && last->ir_type == ir_type_loop_jump
+	     && ((ir_loop_jump*) last)->is_break()) {
+	    continue_from_then_branch = false;
+	 } else {
+	    last = (ir_instruction *) last_if->then_instructions.get_tail();
+
+	    if (last && last->ir_type == ir_type_loop_jump
+		&& ((ir_loop_jump*) last)->is_break())
+	       continue_from_then_branch = true;
+	    else
+	       /* Bail out if neither if-statement branch ends with a break.
+		*/
+	       return visit_continue;
+	 }
+
+	 /* Remove the break from the if-statement.
+	  */
+	 last->remove();
+
+         void *const mem_ctx = talloc_parent(ir);
+         ir_instruction *ir_to_replace = ir;
+
+         for (int i = 0; i < iterations; i++) {
+            exec_list copy_list;
+
+            copy_list.make_empty();
+            clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
+
+            last_if = ((ir_instruction*)copy_list.get_tail())->as_if();
+            assert(last_if);
+
+            ir_to_replace->insert_before(&copy_list);
+            ir_to_replace->remove();
+
+            /* placeholder that will be removed in the next iteration */
+            ir_to_replace =
+	       new(mem_ctx) ir_loop_jump(ir_loop_jump::jump_continue);
+
+            exec_list *const list = (continue_from_then_branch)
+	       ? &last_if->then_instructions : &last_if->else_instructions;
+
+            list->push_tail(ir_to_replace);
+         }
+
+         ir_to_replace->remove();
+
+         this->progress = true;
+         return visit_continue;
+      } else if (last_ir->ir_type == ir_type_loop_jump
+		 && ((ir_loop_jump *)last_ir)->is_break()) {
+	 /* If the only loop-jump is a break at the end of the loop, the loop
+	  * will execute exactly once.  Remove the break, set the iteration
+	  * count, and fall through to the normal unroller.
+	  */
+         last_ir->remove();
+	 iterations = 1;
+
+	 this->progress = true;
+      } else
+         return visit_continue;
+   }
 
    void *const mem_ctx = talloc_parent(ir);
 
-   for (int i = 0; i < ls->max_iterations; i++) {
+   for (int i = 0; i < iterations; i++) {
       exec_list copy_list;
 
       copy_list.make_empty();