[Mesa-dev] [PATCH 3/3] glsl: make loop unrolling more like the nir unrolling path
Timothy Arceri
tarceri at itsqueeze.com
Thu Sep 14 04:47:50 UTC 2017
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.
---
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))
*/
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,
+ 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;
+ }
+
+ 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++;
+ }
+ 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
--
2.13.5
More information about the mesa-dev
mailing list