[Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
Timothy Arceri
tarceri at itsqueeze.com
Wed Oct 4 00:17:17 UTC 2017
Ping on patches 1 & 3
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
>
More information about the mesa-dev
mailing list