summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLuca Barbieri <luca@luca-barbieri.com>2010-09-07 17:03:43 +0200
committerIan Romanick <ian.d.romanick@intel.com>2010-09-13 16:20:40 -0700
commit2cdbced10d98214616bcc5f960b21185c433d23b (patch)
tree0720ef1aeb31047bd7a9fdeffc9eabf892dad5a7
parent8f2214f4892acb994d13531d555196bd8f242dad (diff)
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@intel.com>
-rw-r--r--src/glsl/loop_unroll.cpp93
1 files changed, 89 insertions, 4 deletions
diff --git a/src/glsl/loop_unroll.cpp b/src/glsl/loop_unroll.cpp
index 80f9217159..90797bde37 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();