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
