[Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
Timothy Arceri
tarceri at itsqueeze.com
Sun Oct 8 23:19:38 UTC 2017
On 04/10/17 11:17, Timothy Arceri wrote:
> Ping on patches 1 & 3
Ping again on these two.
Nicolai, I believe I've addressed all you feedback besides trying to add
a pass that flips the branches so that the break is always in the then
branch. I'd rather not spend to much more time on this code as it's
pretty much obsolete, if radeonsi switches to NIR it will only be used
by legacy drivers. I'm happy with the way it works now and I'm not
convinced handling the else branch is complex enough to mess around with
the additional lowering pass.
Tim
>
> On 21/09/17 20: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
>> @@ -18,21 +18,21 @@
>> * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES
>> OR OTHER
>> * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
>> ARISING
>> * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
>> * DEALINGS IN THE SOFTWARE.
>> */
>> #include "compiler/glsl_types.h"
>> #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 *);
>> static ir_rvalue *get_basic_induction_increment(ir_assignment *,
>> hash_table *);
>> /**
>> * Find an initializer of a variable outside a loop
>> *
>> * Works backwards from the loop to find the pre-loop value of the
>> variable.
>> @@ -80,21 +80,21 @@ find_initial_value(ir_loop *loop, ir_variable *var)
>> break;
>> }
>> }
>> return NULL;
>> }
>> 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;
>> void *mem_ctx = ralloc_context(NULL);
>> ir_expression *const sub =
>> new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from);
>> ir_expression *const div =
>> @@ -147,22 +147,24 @@ calculate_iterations(ir_rvalue *from, ir_rvalue
>> *to, ir_rvalue *increment,
>> unreachable("Unsupported type for loop iterator.");
>> }
>> ir_expression *const mul =
>> new(mem_ctx) ir_expression(ir_binop_mul, increment->type,
>> iter,
>> 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);
>> assert(cmp_result != NULL);
>> if (cmp_result->get_bool_component(0)) {
>> iter_value += bias[i];
>> valid_loop = true;
>> break;
>> }
>> }
>> @@ -299,26 +301,28 @@ loop_variable_state::insert(ir_variable *var)
>> lv->var = var;
>> _mesa_hash_table_insert(this->var_hash, lv->var, lv);
>> this->variables.push_tail(lv);
>> return lv;
>> }
>> 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;
>> }
>> /**
>> * If the given variable already is recorded in the state for this
>> loop,
>> * return the corresponding loop_variable object that records
>> information
>> * about it.
>> @@ -461,24 +465,22 @@ loop_analysis::visit_leave(ir_loop *ir)
>> return visit_continue;
>> 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;
>> + if (if_stmt != NULL)
>> + try_add_loop_terminator(ls, if_stmt);
>> }
>> 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);
>> @@ -607,21 +609,21 @@ loop_analysis::visit_leave(ir_loop *ir)
>> if ((counter == NULL) || (limit == NULL))
>> break;
>> ir_variable *var = counter->variable_referenced();
>> ir_rvalue *init = find_initial_value(ir, var);
>> 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--;
>> }
>> if (t->iterations >= 0 &&
>> (ls->limiting_terminator == NULL ||
>> t->iterations <
>> ls->limiting_terminator->iterations)) {
>> ls->limiting_terminator = t;
>> }
>> @@ -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
>> *
>> * 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));
>> }
>> loop_state *
>> analyze_loop_variables(exec_list *instructions)
>> {
>> loop_state *loops = new loop_state;
>> loop_analysis v(loops);
>> v.run(instructions);
>> diff --git a/src/compiler/glsl/loop_analysis.h
>> b/src/compiler/glsl/loop_analysis.h
>> index 99b6bf7563..4e11001846 100644
>> --- a/src/compiler/glsl/loop_analysis.h
>> +++ b/src/compiler/glsl/loop_analysis.h
>> @@ -48,21 +48,21 @@ unroll_loops(exec_list *instructions, loop_state *ls,
>> /**
>> * Tracking for all variables used in a loop
>> */
>> class loop_variable_state : public exec_node {
>> 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);
>> /**
>> * Variables that have not yet been classified
>> */
>> exec_list variables;
>> /**
>> * Variables whose values are constant within the body of the loop
>> *
>> @@ -203,20 +203,23 @@ public:
>> /**
>> * Statement which terminates the loop.
>> */
>> ir_if *ir;
>> /**
>> * The number of iterations after which the terminator is known to
>> * 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;
>> };
>> class loop_state {
>> public:
>> ~loop_state();
>> /**
>> * Get the loop variable state data for a particular loop
>> */
>> 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
>> @@ -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 second_term_then_continue,
>> + bool extra_interation_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_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
>>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list