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

Luca Barbieri lb at kemper.freedesktop.org
Tue Sep 7 08:05:41 PDT 2010


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

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 |   98 ++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 94 insertions(+), 4 deletions(-)

diff --git a/src/glsl/loop_unroll.cpp b/src/glsl/loop_unroll.cpp
index 80f9217..9b3d9cd 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,112 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
       return visit_continue;
    }
 
+   iterations = ls->max_iterations;
+
+   printf("iter %i\n", 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)
+   printf("unroll with jumps %i\n", ls->num_loop_jumps);
+   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;
+
+         printf("yup!\n");
+
+         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();



More information about the mesa-commit mailing list