[Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
Timothy Arceri
tarceri at itsqueeze.com
Mon Oct 9 21:54:04 UTC 2017
On 10/10/17 01:26, Nicolai Hähnle wrote:
> 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?
It could but to avoid duplication of the comment below I think its best
to leave it in one place.
Thanks for the review! I know the unrolling code isn't the easiest to
follow :) I was worried I wouldn't find anyone to review these changes.
Thanks,
Tim
>
> 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
>>
>
>
More information about the mesa-dev
mailing list