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

[Luca Barbieri]

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

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