static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *);
+/**
+ * Record the fact that the given loop variable was referenced inside the loop.
+ *
+ * \arg in_assignee is true if the reference was on the LHS of an assignment.
+ *
+ * \arg in_conditional_code_or_nested_loop is true if the reference occurred
+ * inside an if statement or a nested loop.
+ *
+ * \arg current_assignment is the ir_assignment node that the loop variable is
+ * on the LHS of, if any (ignored if \c in_assignee is false).
+ */
+void
+loop_variable::record_reference(bool in_assignee,
+ bool in_conditional_code_or_nested_loop,
+ ir_assignment *current_assignment)
+{
+ if (in_assignee) {
+ assert(current_assignment != NULL);
+
+ this->conditional_or_nested_assignment =
+ in_conditional_code_or_nested_loop
+ || current_assignment->condition != NULL;
+
+ if (this->first_assignment == NULL) {
+ assert(this->num_assignments == 0);
+
+ this->first_assignment = current_assignment;
+ }
+
+ this->num_assignments++;
+ } else if (this->first_assignment == current_assignment) {
+ /* This catches the case where the variable is used in the RHS of an
+ * assignment where it is also in the LHS.
+ */
+ this->read_before_write = true;
+ }
+}
+
+
loop_state::loop_state()
{
this->ht = hash_table_ctor(0, hash_table_pointer_hash,
hash_table_pointer_compare);
- this->mem_ctx = talloc_init("loop state");
+ this->mem_ctx = ralloc_context(NULL);
+ this->loop_found = false;
}
loop_state::~loop_state()
{
hash_table_dtor(this->ht);
+ ralloc_free(this->mem_ctx);
}
loop_state::insert(ir_loop *ir)
{
loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;
+
hash_table_insert(this->ht, ls, ir);
+ this->loop_found = true;
return ls;
}
loop_variable *
loop_variable_state::insert(ir_variable *var)
{
- void *mem_ctx = talloc_parent(this);
- loop_variable *lv = talloc_zero(mem_ctx, loop_variable);
+ void *mem_ctx = ralloc_parent(this);
+ loop_variable *lv = rzalloc(mem_ctx, loop_variable);
lv->var = var;
loop_terminator *
loop_variable_state::insert(ir_if *if_stmt)
{
- void *mem_ctx = talloc_parent(this);
- loop_terminator *t = talloc_zero(mem_ctx, loop_terminator);
+ void *mem_ctx = ralloc_parent(this);
+ loop_terminator *t = rzalloc(mem_ctx, loop_terminator);
t->ir = if_stmt;
this->terminators.push_tail(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.
+ *
+ * Otherwise, create a new loop_variable object to record information about
+ * the variable, and set its \c read_before_write field appropriately based on
+ * \c in_assignee.
+ *
+ * \arg in_assignee is true if this variable was encountered on the LHS of an
+ * assignment.
+ */
+loop_variable *
+loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee)
+{
+ loop_variable *lv = this->get(var);
+
+ if (lv == NULL) {
+ lv = this->insert(var);
+ lv->read_before_write = !in_assignee;
+ }
+
+ return lv;
+}
+
+
+namespace {
+
class loop_analysis : public ir_hierarchical_visitor {
public:
- loop_analysis();
+ loop_analysis(loop_state *loops);
+ virtual ir_visitor_status visit(ir_loop_jump *);
virtual ir_visitor_status visit(ir_dereference_variable *);
+ virtual ir_visitor_status visit_enter(ir_call *);
+
virtual ir_visitor_status visit_enter(ir_loop *);
virtual ir_visitor_status visit_leave(ir_loop *);
virtual ir_visitor_status visit_enter(ir_assignment *);
exec_list state;
};
+} /* anonymous namespace */
-loop_analysis::loop_analysis()
+loop_analysis::loop_analysis(loop_state *loops)
+ : loops(loops), if_statement_depth(0), current_assignment(NULL)
{
- this->loops = new loop_state;
+ /* empty */
+}
- this->if_statement_depth = 0;
- this->current_assignment = NULL;
+
+ir_visitor_status
+loop_analysis::visit(ir_loop_jump *ir)
+{
+ (void) ir;
+
+ assert(!this->state.is_empty());
+
+ loop_variable_state *const ls =
+ (loop_variable_state *) this->state.get_head();
+
+ ls->num_loop_jumps++;
+
+ return visit_continue;
}
ir_visitor_status
-loop_analysis::visit(ir_dereference_variable *ir)
+loop_analysis::visit_enter(ir_call *ir)
{
- /* If we're not somewhere inside a loop, there's nothing to do.
- */
+ /* If we're not somewhere inside a loop, there's nothing to do. */
if (this->state.is_empty())
- return visit_continue_with_parent;
+ return visit_continue;
loop_variable_state *const ls =
(loop_variable_state *) this->state.get_head();
- ir_variable *var = ir->variable_referenced();
- loop_variable *lv = ls->get(var);
+ ls->contains_calls = true;
+ return visit_continue_with_parent;
+}
- if (lv == NULL) {
- lv = ls->insert(var);
- lv->read_before_write = !this->in_assignee;
- }
- if (this->in_assignee) {
- assert(this->current_assignment != NULL);
+ir_visitor_status
+loop_analysis::visit(ir_dereference_variable *ir)
+{
+ /* If we're not somewhere inside a loop, there's nothing to do.
+ */
+ if (this->state.is_empty())
+ return visit_continue;
- lv->conditional_assignment = (this->if_statement_depth > 0)
- || (this->current_assignment->condition != NULL);
+ bool nested = false;
- if (lv->first_assignment == NULL) {
- assert(lv->num_assignments == 0);
+ foreach_list(node, &this->state) {
+ loop_variable_state *const ls = (loop_variable_state *) node;
- lv->first_assignment = this->current_assignment;
- }
+ ir_variable *var = ir->variable_referenced();
+ loop_variable *lv = ls->get_or_insert(var, this->in_assignee);
- lv->num_assignments++;
- } else if (lv->first_assignment == this->current_assignment) {
- /* This catches the case where the variable is used in the RHS of an
- * assignment where it is also in the LHS.
- */
- lv->read_before_write = true;
+ lv->record_reference(this->in_assignee,
+ nested || this->if_statement_depth > 0,
+ this->current_assignment);
+ nested = true;
}
return visit_continue;
loop_variable_state *const ls =
(loop_variable_state *) this->state.pop_head();
+ /* Function calls may contain side effects. These could alter any of our
+ * variables in ways that cannot be known, and may even terminate shader
+ * execution (say, calling discard in the fragment shader). So we can't
+ * rely on any of our analysis about assignments to variables.
+ *
+ * We could perform some conservative analysis (prove there's no statically
+ * possible assignment, etc.) but it isn't worth it for now; function
+ * inlining will allow us to unroll loops anyway.
+ */
+ if (ls->contains_calls)
+ return visit_continue;
foreach_list(node, &ir->body_instructions) {
/* Skip over declarations at the start of a loop.
foreach_list_safe(node, &ls->variables) {
loop_variable *lv = (loop_variable *) node;
- if (lv->conditional_assignment || (lv->num_assignments > 1))
+ if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
continue;
/* Process the RHS of the assignment. If all of the variables
assert(lv->num_assignments == 1);
assert(lv->first_assignment != NULL);
- /* The assignmnet to the variable in the loop must be unconditional.
+ /* The assignment to the variable in the loop must be unconditional and
+ * not inside a nested loop.
*/
- if (lv->conditional_assignment)
+ if (lv->conditional_or_nested_assignment)
continue;
/* Basic loop induction variables have a single assignment in the loop
ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];
- if (inc->constant_expression_value() == NULL) {
+ if (inc->as_constant() == NULL) {
ir_variable *const inc_var = inc->variable_referenced();
if (inc_var != NULL) {
loop_variable *lv =
}
if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
- void *mem_ctx = talloc_parent(ir);
+ void *mem_ctx = ralloc_parent(ir);
inc = new(mem_ctx) ir_expression(ir_unop_neg,
inc->type,
ir_instruction *const inst =
(ir_instruction *) ir->then_instructions.get_head();
- assert(inst != NULL);
+ if (inst == NULL)
+ return false;
if (inst->ir_type != ir_type_loop_jump)
return false;
loop_state *
analyze_loop_variables(exec_list *instructions)
{
- loop_analysis v;
+ loop_state *loops = new loop_state;
+ loop_analysis v(loops);
v.run(instructions);
return v.loops;