+ 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