Mesa (shader-work): loop_unroll: unroll loops with (lowered) breaks

[Luca Barbieri]

Module: Mesa
Branch: shader-work
Commit: f58a7d68a90bec8d6578b4c51942f69d5cec8212
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=f58a7d68a90bec8d6578b4c51942f69d5cec8212

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/two breaks, or in a single
break or continue, lower it.

This will generate the obvious if structure.

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.

---

 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..54fe388 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 > 2)
       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());
+      ir_if* last_if = last_ir->as_if();
+      if(last_if) {
+         ir_instruction* breaks[2] = {0, 0};
+
+         for(unsigned i = 0; i < 2; ++i)
+         {
+            ir_instruction* last = ((ir_instruction*)(i ? last_if->else_instructions : last_if->then_instructions).get_tail());
+            if(last && last->ir_type == ir_type_loop_jump && ((ir_loop_jump*)last)->is_break())
+               breaks[i] = (ir_loop_jump*)last;
+         }
+
+         if(ls->num_loop_jumps != (!!breaks[0] + !!breaks[1]))
+            return visit_continue;
+
+         if(breaks[0] && breaks[1]) {
+            breaks[0]->remove();
+            breaks[1]->remove();
+            last_if->insert_after(breaks[0]);
+            last_ir = breaks[0];
+            goto one_break;
+         }
+
+         unsigned break_branch = breaks[0] ? 0 : 1;
+         breaks[break_branch]->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);
+            /* this is the branch where there is NOT a break */
+            exec_list* list = break_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 && last_ir->ir_type == ir_type_loop_jump && ((ir_loop_jump*)last_ir)->is_break())
+      {
+         if(ls->num_loop_jumps != 1)
+            return visit_continue;
+
+one_break:
+         last_ir->remove();
+         if(max_iterations)
+            max_iterations = 1;
+         /* fall through to normal unrolling */
+      }
+      else if(last_ir && last_ir->ir_type == ir_type_loop_jump && ((ir_loop_jump*)last_ir)->is_continue())
+      {
+         /* this case might be somewhat redundant, but it's probably best
+          * not to rely on the rest of the optimizer too much, especially
+          * because this particular case might not be optimized yet...
+          */
+         if(ls->num_loop_jumps != 1)
+            return visit_continue;
+
+         last_ir->remove();
+         /* fall through to normal unrolling */
+      }
+      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();