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?
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
--
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
