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;
} /* anonymous namespace */
-static bool
-is_break(ir_instruction *ir)
-{
- return ir != NULL && ir->ir_type == ir_type_loop_jump
- && ((ir_loop_jump *) ir)->is_break();
-}
-
class loop_unroll_count : public ir_hierarchical_visitor {
public:
int nodes;
if (options->EmitNoIndirectSampler) {
if ((ir->array->type->is_array() &&
ir->array->type->contains_sampler()) &&
- !ir->array_index->constant_expression_value()) {
+ !ir->array_index->constant_expression_value(ralloc_parent(ir))) {
unsupported_variable_indexing = true;
return visit_continue;
}
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);
+
+ /* If there are no terminators, then the loop iteration count must be 1.
+ * This is the 'do { } while (false);' case.
+ */
+ assert(!ls->terminators.is_empty() || iterations == 1);
+
+ 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 (!ls->terminators.is_empty() &&
+ (limit_if != first_ir->as_if() || exit_branch_has_instructions))
+ iterations++;
for (int i = 0; i < iterations; i++) {
exec_list copy_list;
*/
void
loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
- bool continue_from_then_branch)
+ bool second_term_then_continue,
+ bool extra_iteration_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_iteration_required)
+ iterations++;
+
for (int i = 0; i < iterations; i++) {
exec_list copy_list;
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();
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();
}
}
+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.
return visit_continue;
}
- /* Don't try to unroll loops where the number of iterations is not known
- * at compile-time.
+ /* Limiting terminator may have iteration count of zero,
+ * this is a valid case because the loop may break during
+ * the first iteration.
*/
- if (ls->limiting_terminator == NULL)
+
+ /* Remove the conditional break statements associated with all terminators
+ * that are associated with a fixed iteration count, except for the one
+ * associated with the limiting terminator--that one needs to stay, since
+ * it terminates the loop. Exception: if the loop still has a normative
+ * bound, then that terminates the loop, so we don't even need the limiting
+ * terminator.
+ */
+ foreach_in_list_safe(loop_terminator, t, &ls->terminators) {
+ if (t->iterations < 0)
+ continue;
+
+ exec_list *branch_instructions;
+ if (t != ls->limiting_terminator) {
+ ir_instruction *ir_if_last = (ir_instruction *)
+ t->ir->then_instructions.get_tail();
+ if (is_break(ir_if_last)) {
+ branch_instructions = &t->ir->else_instructions;
+ } else {
+ branch_instructions = &t->ir->then_instructions;
+ assert(is_break((ir_instruction *)
+ t->ir->else_instructions.get_tail()));
+ }
+
+ exec_list copy_list;
+ copy_list.make_empty();
+ clone_ir_list(ir, ©_list, branch_instructions);
+
+ t->ir->insert_before(©_list);
+ t->ir->remove();
+
+ assert(ls->num_loop_jumps > 0);
+ ls->num_loop_jumps--;
+
+ /* Also remove it from the terminator list */
+ t->remove();
+
+ this->progress = true;
+ }
+ }
+
+ if (ls->limiting_terminator == NULL) {
+ ir_instruction *last_ir =
+ (ir_instruction *) ir->body_instructions.get_tail();
+
+ /* If a loop has no induction variable and the last instruction is
+ * a break, unroll the loop with a count of 1. This is the classic
+ *
+ * do {
+ * // ...
+ * } while (false)
+ *
+ * that is used to wrap multi-line macros.
+ *
+ * If num_loop_jumps is not zero, last_ir cannot be NULL... there has to
+ * be at least num_loop_jumps instructions in the loop.
+ */
+ if (ls->num_loop_jumps == 1 && is_break(last_ir)) {
+ last_ir->remove();
+
+ simple_unroll(ir, 1);
+ }
+
+ /* Don't try to unroll loops where the number of iterations is not known
+ * at compile-time.
+ */
return visit_continue;
+ }
- iterations = ls->limiting_terminator->iterations;
+ int iterations = ls->limiting_terminator->iterations;
const int max_iterations = options->MaxUnrollIterations;
return visit_continue;
if (predicted_num_loop_jumps == 0) {
- ls->limiting_terminator->ir->remove();
simple_unroll(ir, iterations);
return visit_continue;
}
*/
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
+ * iteration 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 || ls->terminators.length() != 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) {
+ 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,