diff options
| -rw-r--r-- | src/compiler/glsl/loop_analysis.cpp | 53 | ||||
| -rw-r--r-- | src/compiler/glsl/loop_analysis.h | 5 | ||||
| -rw-r--r-- | src/compiler/glsl/loop_unroll.cpp | 172 |
3 files changed, 163 insertions, 67 deletions
diff --git a/src/compiler/glsl/loop_analysis.cpp b/src/compiler/glsl/loop_analysis.cpp index 78279844dc8..2979e09433f 100644 --- a/src/compiler/glsl/loop_analysis.cpp +++ b/src/compiler/glsl/loop_analysis.cpp @@ -25,7 +25,7 @@ #include "loop_analysis.h" #include "ir_hierarchical_visitor.h" -static bool is_loop_terminator(ir_if *ir); +static void try_add_loop_terminator(loop_variable_state *ls, ir_if *ir); static bool all_expression_operands_are_loop_constant(ir_rvalue *, hash_table *); @@ -87,7 +87,7 @@ find_initial_value(ir_loop *loop, ir_variable *var) static int calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, - enum ir_expression_operation op) + enum ir_expression_operation op, bool continue_from_then) { if (from == NULL || to == NULL || increment == NULL) return -1; @@ -154,8 +154,10 @@ calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, ir_expression *const add = new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from); - ir_expression *const cmp = + ir_expression *cmp = new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to); + if (continue_from_then) + cmp = new(mem_ctx) ir_expression(ir_unop_logic_not, cmp); ir_constant *const cmp_result = cmp->constant_expression_value(mem_ctx); @@ -306,12 +308,14 @@ loop_variable_state::insert(ir_variable *var) loop_terminator * -loop_variable_state::insert(ir_if *if_stmt) +loop_variable_state::insert(ir_if *if_stmt, bool continue_from_then) { void *mem_ctx = ralloc_parent(this); loop_terminator *t = new(mem_ctx) loop_terminator(); t->ir = if_stmt; + t->continue_from_then = continue_from_then; + this->terminators.push_tail(t); return t; @@ -468,10 +472,8 @@ loop_analysis::visit_leave(ir_loop *ir) ir_if *if_stmt = ((ir_instruction *) node)->as_if(); - if ((if_stmt != NULL) && is_loop_terminator(if_stmt)) - ls->insert(if_stmt); - else - break; + if (if_stmt != NULL) + try_add_loop_terminator(ls, if_stmt); } @@ -614,7 +616,7 @@ loop_analysis::visit_leave(ir_loop *ir) loop_variable *lv = ls->get(var); if (lv != NULL && lv->is_induction_var()) { t->iterations = calculate_iterations(init, limit, lv->increment, - cmp); + cmp, t->continue_from_then); if (incremented_before_terminator(ir, var, t->ir)) { t->iterations--; @@ -781,31 +783,26 @@ get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) /** - * Detect whether an if-statement is a loop terminating condition + * Detect whether an if-statement is a loop terminating condition, if so + * add it to the list of loop terminators. * * Detects if-statements of the form * - * (if (expression bool ...) (break)) + * (if (expression bool ...) (...then_instrs...break)) + * + * or + * + * (if (expression bool ...) ... (...else_instrs...break)) */ -bool -is_loop_terminator(ir_if *ir) +void +try_add_loop_terminator(loop_variable_state *ls, ir_if *ir) { - if (!ir->else_instructions.is_empty()) - return false; - - ir_instruction *const inst = - (ir_instruction *) ir->then_instructions.get_head(); - if (inst == NULL) - return false; - - if (inst->ir_type != ir_type_loop_jump) - return false; - - ir_loop_jump *const jump = (ir_loop_jump *) inst; - if (jump->mode != ir_loop_jump::jump_break) - return false; + ir_instruction *inst = (ir_instruction *) ir->then_instructions.get_tail(); + ir_instruction *else_inst = + (ir_instruction *) ir->else_instructions.get_tail(); - return true; + if (is_break(inst) || is_break(else_inst)) + ls->insert(ir, is_break(else_inst)); } diff --git a/src/compiler/glsl/loop_analysis.h b/src/compiler/glsl/loop_analysis.h index 99b6bf75638..4e110018461 100644 --- a/src/compiler/glsl/loop_analysis.h +++ b/src/compiler/glsl/loop_analysis.h @@ -55,7 +55,7 @@ public: class loop_variable *get(const ir_variable *); class loop_variable *insert(ir_variable *); class loop_variable *get_or_insert(ir_variable *, bool in_assignee); - class loop_terminator *insert(ir_if *); + class loop_terminator *insert(ir_if *, bool continue_from_then); /** @@ -210,6 +210,9 @@ public: * terminate the loop (if that is a fixed value). Otherwise -1. */ int iterations; + + /* Does the if continue from the then branch or the else branch */ + bool continue_from_then; }; diff --git a/src/compiler/glsl/loop_unroll.cpp b/src/compiler/glsl/loop_unroll.cpp index 358cbf10af4..6e06a30fb91 100644 --- a/src/compiler/glsl/loop_unroll.cpp +++ b/src/compiler/glsl/loop_unroll.cpp @@ -42,7 +42,9 @@ public: virtual ir_visitor_status visit_leave(ir_loop *ir); void simple_unroll(ir_loop *ir, int iterations); void complex_unroll(ir_loop *ir, int iterations, - bool continue_from_then_branch); + bool continue_from_then_branch, + bool limiting_term_first, + bool lt_continue_from_then_branch); void splice_post_if_instructions(ir_if *ir_if, exec_list *splice_dest); loop_state *state; @@ -176,6 +178,51 @@ void loop_unroll_visitor::simple_unroll(ir_loop *ir, int iterations) { void *const mem_ctx = ralloc_parent(ir); + loop_variable_state *const ls = this->state->get(ir); + + ir_instruction *first_ir = + (ir_instruction *) ir->body_instructions.get_head(); + + if (!first_ir) { + /* The loop is empty remove it and return */ + ir->remove(); + return; + } + + ir_if *limit_if = NULL; + bool exit_branch_has_instructions = false; + if (ls->limiting_terminator) { + limit_if = ls->limiting_terminator->ir; + ir_instruction *ir_if_last = (ir_instruction *) + limit_if->then_instructions.get_tail(); + + if (is_break(ir_if_last)) { + if (ir_if_last != limit_if->then_instructions.get_head()) + exit_branch_has_instructions = true; + + splice_post_if_instructions(limit_if, &limit_if->else_instructions); + ir_if_last->remove(); + } else { + ir_if_last = (ir_instruction *) + limit_if->else_instructions.get_tail(); + assert(is_break(ir_if_last)); + + if (ir_if_last != limit_if->else_instructions.get_head()) + exit_branch_has_instructions = true; + + splice_post_if_instructions(limit_if, &limit_if->then_instructions); + ir_if_last->remove(); + } + } + + /* Because 'iterations' is the number of times we pass over the *entire* + * loop body before hitting the first break, we need to bump the number of + * iterations if the limiting terminator is not the first instruction in + * the loop, or it the exit branch contains instructions. This ensures we + * execute any instructions before the terminator or in its exit branch. + */ + if (limit_if != first_ir->as_if() || exit_branch_has_instructions) + iterations++; for (int i = 0; i < iterations; i++) { exec_list copy_list; @@ -227,11 +274,22 @@ loop_unroll_visitor::simple_unroll(ir_loop *ir, int iterations) */ void loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations, - bool continue_from_then_branch) + bool second_term_then_continue, + bool extra_iteration_required, + bool first_term_then_continue) { void *const mem_ctx = ralloc_parent(ir); ir_instruction *ir_to_replace = ir; + /* Because 'iterations' is the number of times we pass over the *entire* + * loop body before hitting the first break, we need to bump the number of + * iterations if the limiting terminator is not the first instruction in + * the loop, or it the exit branch contains instructions. This ensures we + * execute any instructions before the terminator or in its exit branch. + */ + if (extra_iteration_required) + iterations++; + for (int i = 0; i < iterations; i++) { exec_list copy_list; @@ -241,6 +299,10 @@ loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations, ir_if *ir_if = ((ir_instruction *) copy_list.get_tail())->as_if(); assert(ir_if != NULL); + exec_list *const first_list = first_term_then_continue + ? &ir_if->then_instructions : &ir_if->else_instructions; + ir_if = ((ir_instruction *) first_list->get_tail())->as_if(); + ir_to_replace->insert_before(©_list); ir_to_replace->remove(); @@ -248,10 +310,10 @@ loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations, ir_to_replace = new(mem_ctx) ir_loop_jump(ir_loop_jump::jump_continue); - exec_list *const list = (continue_from_then_branch) + exec_list *const second_term_continue_list = second_term_then_continue ? &ir_if->then_instructions : &ir_if->else_instructions; - list->push_tail(ir_to_replace); + second_term_continue_list->push_tail(ir_to_replace); } ir_to_replace->remove(); @@ -293,6 +355,21 @@ loop_unroll_visitor::splice_post_if_instructions(ir_if *ir_if, } } +static bool +exit_branch_has_instructions(ir_if *term_if, bool lt_then_continue) +{ + if (lt_then_continue) { + if (term_if->else_instructions.get_head() == + term_if->else_instructions.get_tail()) + return false; + } else { + if (term_if->then_instructions.get_head() == + term_if->then_instructions.get_tail()) + return false; + } + + return true; +} ir_visitor_status loop_unroll_visitor::visit_leave(ir_loop *ir) @@ -417,7 +494,6 @@ loop_unroll_visitor::visit_leave(ir_loop *ir) return visit_continue; if (predicted_num_loop_jumps == 0) { - ls->limiting_terminator->ir->remove(); simple_unroll(ir, iterations); return visit_continue; } @@ -432,51 +508,71 @@ loop_unroll_visitor::visit_leave(ir_loop *ir) */ last_ir->remove(); - ls->limiting_terminator->ir->remove(); simple_unroll(ir, 1); return visit_continue; } - /* recognize loops in the form produced by ir_lower_jumps */ - foreach_in_list(ir_instruction, cur_ir, &ir->body_instructions) { - /* Skip the limiting terminator, since it will go away when we - * unroll. - */ - if (cur_ir == ls->limiting_terminator->ir) - continue; + /* Complex unrolling can only handle two terminators. One with an unknown + * iteration count and one with a known iteration count. We have already + * made sure we have a known iteration count above and removed any + * unreachable terminators with a known count. Here we make sure there + * isn't any additional unknown terminators, or any other jumps nested + * inside futher ifs. + */ + if (ls->num_loop_jumps != 2) + return visit_continue; - ir_if *ir_if = cur_ir->as_if(); - if (ir_if != NULL) { - /* 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 *ir_if_last = - (ir_instruction *) ir_if->then_instructions.get_tail(); + ir_instruction *first_ir = + (ir_instruction *) ir->body_instructions.get_head(); + unsigned term_count = 0; + bool first_term_then_continue = false; + foreach_in_list(loop_terminator, t, &ls->terminators) { + assert(term_count < 2); + + ir_if *ir_if = t->ir->as_if(); + assert(ir_if != NULL); + + ir_instruction *ir_if_last = + (ir_instruction *) ir_if->then_instructions.get_tail(); + + if (is_break(ir_if_last)) { + splice_post_if_instructions(ir_if, &ir_if->else_instructions); + ir_if_last->remove(); + if (term_count == 1) { + bool ebi = + exit_branch_has_instructions(ls->limiting_terminator->ir, + first_term_then_continue); + complex_unroll(ir, iterations, false, + first_ir->as_if() != ls->limiting_terminator->ir || + ebi, + first_term_then_continue); + return visit_continue; + } + } else { + ir_if_last = + (ir_instruction *) ir_if->else_instructions.get_tail(); + + assert(is_break(ir_if_last)); if (is_break(ir_if_last)) { - ls->limiting_terminator->ir->remove(); - splice_post_if_instructions(ir_if, &ir_if->else_instructions); + splice_post_if_instructions(ir_if, &ir_if->then_instructions); ir_if_last->remove(); - complex_unroll(ir, iterations, false); - return visit_continue; - } else { - ir_if_last = - (ir_instruction *) ir_if->else_instructions.get_tail(); - - if (is_break(ir_if_last)) { - ls->limiting_terminator->ir->remove(); - splice_post_if_instructions(ir_if, &ir_if->then_instructions); - ir_if_last->remove(); - complex_unroll(ir, iterations, true); + if (term_count == 1) { + bool ebi = + exit_branch_has_instructions(ls->limiting_terminator->ir, + first_term_then_continue); + complex_unroll(ir, iterations, true, + first_ir->as_if() != ls->limiting_terminator->ir || + ebi, + first_term_then_continue); return visit_continue; + } else { + first_term_then_continue = true; } } } + + term_count++; } /* Did not find the break statement. It must be in a complex if-nesting, |