0,0 → 1,253 |
/* |
* Copyright © 2010 Intel Corporation |
* |
* Permission is hereby granted, free of charge, to any person obtaining a |
* copy of this software and associated documentation files (the "Software"), |
* to deal in the Software without restriction, including without limitation |
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
* and/or sell copies of the Software, and to permit persons to whom the |
* Software is furnished to do so, subject to the following conditions: |
* |
* The above copyright notice and this permission notice (including the next |
* paragraph) shall be included in all copies or substantial portions of the |
* Software. |
* |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
* 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 "glsl_types.h" |
#include "loop_analysis.h" |
#include "ir_hierarchical_visitor.h" |
|
class loop_unroll_visitor : public ir_hierarchical_visitor { |
public: |
loop_unroll_visitor(loop_state *state, unsigned max_iterations) |
{ |
this->state = state; |
this->progress = false; |
this->max_iterations = max_iterations; |
} |
|
virtual ir_visitor_status visit_leave(ir_loop *ir); |
|
loop_state *state; |
|
bool progress; |
unsigned max_iterations; |
}; |
|
|
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; |
bool fail; |
|
loop_unroll_count(exec_list *list) |
{ |
nodes = 0; |
fail = false; |
|
run(list); |
} |
|
virtual ir_visitor_status visit_enter(ir_assignment *ir) |
{ |
nodes++; |
return visit_continue; |
} |
|
virtual ir_visitor_status visit_enter(ir_expression *ir) |
{ |
nodes++; |
return visit_continue; |
} |
|
virtual ir_visitor_status visit_enter(ir_loop *ir) |
{ |
fail = true; |
return visit_continue; |
} |
}; |
|
|
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. |
*/ |
if (ls == NULL) { |
assert(ls != NULL); |
return visit_continue; |
} |
|
iterations = ls->max_iterations; |
|
/* Don't try to unroll loops where the number of iterations is not known |
* at compile-time. |
*/ |
if (iterations < 0) |
return visit_continue; |
|
/* Don't try to unroll loops that have zillions of iterations either. |
*/ |
if (iterations > (int) max_iterations) |
return visit_continue; |
|
/* Don't try to unroll nested loops and loops with a huge body. |
*/ |
loop_unroll_count count(&ir->body_instructions); |
|
if (count.fail || count.nodes * iterations > (int)max_iterations * 5) |
return visit_continue; |
|
if (ls->num_loop_jumps > 1) |
return visit_continue; |
else if (ls->num_loop_jumps) { |
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, set the iteration |
* count, and fall through to the normal unroller. |
*/ |
last_ir->remove(); |
iterations = 1; |
|
this->progress = true; |
} else { |
ir_if *ir_if = NULL; |
ir_instruction *break_ir = NULL; |
bool continue_from_then_branch = false; |
|
foreach_list(node, &ir->body_instructions) { |
/* recognize loops in the form produced by ir_lower_jumps */ |
ir_instruction *cur_ir = (ir_instruction *) node; |
|
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(); |
|
if (is_break(ir_if_last)) { |
continue_from_then_branch = false; |
break_ir = ir_if_last; |
break; |
} else { |
ir_if_last = |
(ir_instruction *) ir_if->else_instructions.get_tail(); |
|
if (is_break(ir_if_last)) { |
break_ir = ir_if_last; |
continue_from_then_branch = true; |
break; |
} |
} |
} |
} |
|
if (break_ir == NULL) |
return visit_continue; |
|
/* move instructions after then if in the continue branch */ |
while (!ir_if->get_next()->is_tail_sentinel()) { |
ir_instruction *move_ir = (ir_instruction *) ir_if->get_next(); |
|
move_ir->remove(); |
if (continue_from_then_branch) |
ir_if->then_instructions.push_tail(move_ir); |
else |
ir_if->else_instructions.push_tail(move_ir); |
} |
|
/* Remove the break from the if-statement. |
*/ |
break_ir->remove(); |
|
void *const mem_ctx = ralloc_parent(ir); |
ir_instruction *ir_to_replace = ir; |
|
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_instruction *) copy_list.get_tail())->as_if(); |
assert(ir_if != NULL); |
|
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) |
? &ir_if->then_instructions : &ir_if->else_instructions; |
|
list->push_tail(ir_to_replace); |
} |
|
ir_to_replace->remove(); |
|
this->progress = true; |
return visit_continue; |
} |
} |
|
void *const mem_ctx = ralloc_parent(ir); |
|
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); |
} |
|
/* The loop has been replaced by the unrolled copies. Remove the original |
* loop from the IR sequence. |
*/ |
ir->remove(); |
|
this->progress = true; |
return visit_continue; |
} |
|
|
bool |
unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations) |
{ |
loop_unroll_visitor v(ls, max_iterations); |
|
v.run(instructions); |
|
return v.progress; |
} |