[Mesa-dev] [PATCH 3/3] glsl: make loop unrolling more like the nir unrolling path
Timothy Arceri
tarceri at itsqueeze.com
Mon Sep 18 11:43:03 UTC 2017
On 18/09/17 20:50, Nicolai Hähnle wrote:
> 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.
I'm not sure what exactly the point is you are trying to make. This is
exactly what the code does. The difference between the simple unroll and
complex unroll is 1. you need to splice one if inside the other 2. you
need a placeholder so you can insert the subsequent iteration. These are
the only differences between the simple unroll, but trying combine them
would just make the code even harder to follow IMO.
>
> 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().
That is not what we are checking. We are checking if the exit branch
contains 1 instruction (the break) or more instructions.
>
>
>> +
>> + 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?
Yeah. It should be done in loop_control.cpp (where its updated in pacth
1) as this is where the terminator is deleted. TBH I'm not sure why that
extra control visitor needs to exist at all but I'd rather leave it as
is for now as I don't really have much time to work on GLSL IR at the
moment. Our focus is shifting to RADV for the immediate future.
I'd like to get this series in as it should be quite helpful but I don't
really see it happening if I need to spend a large amount of time
re-factoring the code.
One thing I seem to have overlooked is making sure that if branches
don't contain nested jumps and abort if they do. I'll need to update the
analysis pass to do this and retest with CTS. I meant to do a full CTS
test but seem to have forgotten this before sending.
>
> 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
>>
>
>
More information about the mesa-dev
mailing list