[Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
Nicolai Hähnle
nhaehnle at gmail.com
Mon Oct 9 14:26:30 UTC 2017
On 21.09.2017 12:55, Timothy Arceri wrote:
> The old code assumed that loop terminators will always be at
> the start of the loop, resulting in otherwise unrollable
> loops not being unrolled at all. For example the current
> code would unroll:
>
> int j = 0;
> do {
> if (j > 5)
> break;
>
> ... do stuff ...
>
> j++;
> } while (j < 4);
>
> But would fail to unroll the following as no iteration limit was
> calculated because it failed to find the terminator:
>
> int j = 0;
> do {
> ... do stuff ...
>
> j++;
> } while (j < 4);
>
> Also we would fail to unroll the following as we ended up
> calculating the iteration limit as 6 rather than 4. The unroll
> code then assumed we had 3 terminators rather the 2 as it
> wasn't able to determine that "if (j > 5)" was redundant.
>
> int j = 0;
> do {
> if (j > 5)
> break;
>
> ... do stuff ...
>
> if (bool(i))
> break;
>
> j++;
> } while (j < 4);
>
> This patch changes this pass to be more like the NIR unrolling pass.
> With this change we handle loop terminators correctly and also
> handle cases where the terminators have instructions in their
> branches other than a break.
>
> V2:
> - fixed regression where loops with a break in else were never
> unrolled in v1.
> - fixed confusing/wrong naming of bools in complex unrolling.
> ---
> src/compiler/glsl/loop_analysis.cpp | 50 +++++------
> src/compiler/glsl/loop_analysis.h | 5 +-
> src/compiler/glsl/loop_unroll.cpp | 172 ++++++++++++++++++++++++++++--------
> 3 files changed, 161 insertions(+), 66 deletions(-)
>
> diff --git a/src/compiler/glsl/loop_analysis.cpp b/src/compiler/glsl/loop_analysis.cpp
> index 78279844dc..5bf406e7ee 100644
> --- a/src/compiler/glsl/loop_analysis.cpp
> +++ b/src/compiler/glsl/loop_analysis.cpp
[snip]
> @@ -778,41 +780,35 @@ get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
>
> return inc;
> }
>
>
> /**
> * Detect whether an if-statement is a loop terminating condition
Please update this part of the comment.
[snip]
> diff --git a/src/compiler/glsl/loop_unroll.cpp b/src/compiler/glsl/loop_unroll.cpp
> index 358cbf10af..82931c9abf 100644
> --- a/src/compiler/glsl/loop_unroll.cpp
> +++ b/src/compiler/glsl/loop_unroll.cpp
[snip]
> @@ -220,45 +267,60 @@ loop_unroll_visitor::simple_unroll(ir_loop *ir, int iterations)
> * (...then_instrs...
> * ...body...
> * (if (cond)
> * (...then_instrs...)
> * (...else_instrs...)))
> * (...else_instrs...)))
> * (...else_instrs))
> */
> void
> loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
> - bool continue_from_then_branch)
> + bool second_term_then_continue,
> + bool extra_interation_required,
s/interation/iteration/
I also wonder whether this parameter can't be folded into iterations?
Cheers,
Nicolai
> + 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_interation_required)
> + iterations++;
> +
> for (int i = 0; i < iterations; i++) {
> exec_list copy_list;
>
> copy_list.make_empty();
> clone_ir_list(mem_ctx, ©_list, &ir->body_instructions);
>
> 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();
>
> /* 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)
> + 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();
>
> this->progress = true;
> }
>
>
> /**
> * Move all of the instructions which follow \c ir_if to the end of
> @@ -286,20 +348,35 @@ loop_unroll_visitor::splice_post_if_instructions(ir_if *ir_if,
> exec_list *splice_dest)
> {
> while (!ir_if->get_next()->is_tail_sentinel()) {
> ir_instruction *move_ir = (ir_instruction *) ir_if->get_next();
>
> move_ir->remove();
> splice_dest->push_tail(move_ir);
> }
> }
>
> +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)
> {
> loop_variable_state *const ls = this->state->get(ir);
>
> /* If we've entered a loop that hasn't been analyzed, something really,
> * really bad has happened.
> */
> if (ls == NULL) {
> @@ -410,80 +487,99 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
> /* Note: the limiting terminator contributes 1 to ls->num_loop_jumps.
> * We'll be removing the limiting terminator before we unroll.
> */
> assert(ls->num_loop_jumps > 0);
> unsigned predicted_num_loop_jumps = ls->num_loop_jumps - 1;
>
> if (predicted_num_loop_jumps > 1)
> return visit_continue;
>
> if (predicted_num_loop_jumps == 0) {
> - ls->limiting_terminator->ir->remove();
> simple_unroll(ir, iterations);
> return visit_continue;
> }
>
> ir_instruction *last_ir = (ir_instruction *) ir->body_instructions.get_tail();
> assert(last_ir != NULL);
>
> if (is_break(last_ir)) {
> /* If the only loop-jump is a break at the end of the loop, the loop
> * will execute exactly once. Remove the break and use the simple
> * unroller with an iteration count of 1.
> */
> 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
> + * interation 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,
> * so don't try to unroll.
> */
> return visit_continue;
> }
>
>
> bool
>
--
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.
More information about the mesa-dev
mailing list