[Mesa-dev] [PATCH 3/3] glsl: make loop unrolling more like the nir unrolling path
Nicolai Hähnle
nhaehnle at gmail.com
Mon Sep 18 10:50:51 UTC 2017
On 14.09.2017 06:47, Timothy Arceri wrote:
> The old code incorrectly assumed that loop terminators will always
> be at the start of the loop. It really seems to be just luck that
> we haven't triggered any bugs here, for example if there is a loop
> terminator at the start of the loop we might actually ignore any
> other terminators that might be later in the loop because we break
> before checking all the instructions. Ignoring the other
> terminators might result in unrolling loops that we shouldn't be,
> or the wrong number of iterations being calculated etc.
>
> Incorrect analysis can also result in 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.
Some of that code is a bit tricky.
Could we perhaps normalize the loop terminators such that the break is
always in the then-branch? I.e. flip then- and else-branches if
required. This would simplify a lot of the case distinction.
Additionally, it's not clear to me what the value-add of the complex
loop at the end of visit_leave is. Couldn't we just unconditionally do
the splicing of terminators into a chain of if-statements, so that
loop {
...
if (cond) {
...
break
}
...
if (cond) {
...
break
}
...
}
becomes
loop {
...
if (cond) {
...
break
} else {
...
if (cond) {
...
break
} else {
...
// splice subsequent unrolled iterations here
}
}
}
regardless of which condition is the limiting terminator?
Unrolling chains the if-statements even further, and constant
propagation should take care of the rest. We already rely on constant
propagation for cleanups anyway.
Some other, more minor comments, below.
> ---
> src/compiler/glsl/loop_analysis.cpp | 7 +-
> src/compiler/glsl/loop_unroll.cpp | 177 ++++++++++++++++++++++++++++--------
> 2 files changed, 141 insertions(+), 43 deletions(-)
>
> diff --git a/src/compiler/glsl/loop_analysis.cpp b/src/compiler/glsl/loop_analysis.cpp
> index 8a0425d185..53372183dd 100644
> --- a/src/compiler/glsl/loop_analysis.cpp
> +++ b/src/compiler/glsl/loop_analysis.cpp
> @@ -324,22 +324,20 @@ loop_analysis::visit_leave(ir_loop *ir)
> foreach_in_list(ir_instruction, node, &ir->body_instructions) {
> /* Skip over declarations at the start of a loop.
> */
> if (node->as_variable())
> continue;
>
> ir_if *if_stmt = ((ir_instruction *) node)->as_if();
>
> if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
> ls->insert(if_stmt);
> - else
> - break;
> }
>
>
> foreach_in_list_safe(loop_variable, lv, &ls->variables) {
> /* Move variables that are already marked as being loop constant to
> * a separate list. These trivially don't need to be tested.
> */
> if (lv->is_loop_constant()) {
> lv->remove();
> ls->constants.push_tail(lv);
> @@ -644,25 +642,22 @@ get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
> /**
> * Detect whether an if-statement is a loop terminating condition
> *
> * Detects if-statements of the form
> *
> * (if (expression bool ...) (break))
Please update this comment to account for possibly having more
instruction and an else-branch.
> */
> bool
> is_loop_terminator(ir_if *ir)
> {
> - if (!ir->else_instructions.is_empty())
> - return false;
> -
> ir_instruction *const inst =
> - (ir_instruction *) ir->then_instructions.get_head();
> + (ir_instruction *) ir->then_instructions.get_tail();
> 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;
>
> diff --git a/src/compiler/glsl/loop_unroll.cpp b/src/compiler/glsl/loop_unroll.cpp
> index 7f601295a1..9aa2b975f7 100644
> --- a/src/compiler/glsl/loop_unroll.cpp
> +++ b/src/compiler/glsl/loop_unroll.cpp
> @@ -35,21 +35,23 @@ public:
> const struct gl_shader_compiler_options *options)
> {
> this->state = state;
> this->progress = false;
> this->options = options;
> }
>
> 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;
>
> bool progress;
> const struct gl_shader_compiler_options *options;
> };
>
> } /* anonymous namespace */
>
> @@ -169,20 +171,65 @@ private:
> * (loop (...) ...instrs...)
> *
> * And the iteration count is 3, the output will be:
> *
> * ...instrs... ...instrs... ...instrs...
> */
> 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;
>
> copy_list.make_empty();
> clone_ir_list(mem_ctx, ©_list, &ir->body_instructions);
>
> ir->insert_before(©_list);
> }
>
> @@ -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 continue_from_then_branch,
> + bool extra_interation_required,
*iteration
> + bool lt_continue_from_then_branch)
> {
> 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 lt_list = lt_continue_from_then_branch
> + ? &ir_if->then_instructions : &ir_if->else_instructions;
> + ir_if = ((ir_instruction *) lt_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 unknown_term_limit_list = (continue_from_then_branch)
> ? &ir_if->then_instructions : &ir_if->else_instructions;
>
> - list->push_tail(ir_to_replace);
> + unknown_term_limit_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;
> + }
Use exec_list::is_empty().
> +
> + return true;
> +}
>
> 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.
> */
> @@ -359,80 +436,106 @@ 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)
> + /* Remove unreachable terminators from the list */
> + unsigned term_count = 0;
> + foreach_in_list_safe(loop_terminator, t, &ls->terminators) {
> + if (t->iterations >= ls->limiting_terminator->iterations &&
> + t != ls->limiting_terminator) {
> + t->remove();
> continue;
> + }
> + term_count++;
> + }
Shouldn't that happen during loop analysis?
Cheers,
Nicolai
> + assert(term_count == 2);
> +
> + if (term_count != 2 || ls->num_loop_jumps != 2)
> + return visit_continue;
> +
> + ir_instruction *first_ir =
> + (ir_instruction *) ir->body_instructions.get_head();
>
> - 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();
> + term_count = 0;
> + bool lt_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,
> + lt_then_continue);
> + complex_unroll(ir, iterations, false,
> + first_ir->as_if() != ls->limiting_terminator->ir ||
> + ebi,
> + lt_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) {
> + lt_then_continue = t == ls->limiting_terminator ?
> + true : lt_then_continue;
> + bool ebi =
> + exit_branch_has_instructions(ls->limiting_terminator->ir,
> + lt_then_continue);
> + complex_unroll(ir, iterations, true,
> + first_ir->as_if() != ls->limiting_terminator->ir ||
> + ebi,
> + lt_then_continue);
> return visit_continue;
> + } else {
> + lt_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