[Mesa-dev] [RFC PATCH 06/10] glsl/loops: Move some analysis from loop_controls to loop_analysis.
Paul Berry
stereotype441 at gmail.com
Sat Nov 30 08:38:15 PST 2013
Previously, the sole responsibility of loop_analysis was to find all
the variables referenced in the loop that are either loop constant or
induction variables, and find all of the simple if statements that
might terminate the loop. The remainder of the analysis necessary to
determine how many times a loop executed was performed by
loop_controls.
This patch makes loop_analysis also responsible for determining the
number of iterations after which each loop terminator will terminate
the loop, and for figuring out which terminator will terminate the
loop first (I'm calling this the "limiting terminator").
This will allow loop unrolling to make use of information that was
previously only visible from loop_controls, namely the identity of the
limiting terminator.
---
src/glsl/loop_analysis.cpp | 69 +++++++++++++++++++++++++++++
src/glsl/loop_analysis.h | 30 +++++++++++++
src/glsl/loop_controls.cpp | 106 +++++++++++----------------------------------
3 files changed, 125 insertions(+), 80 deletions(-)
diff --git a/src/glsl/loop_analysis.cpp b/src/glsl/loop_analysis.cpp
index 425290b..c3b3f8e 100644
--- a/src/glsl/loop_analysis.cpp
+++ b/src/glsl/loop_analysis.cpp
@@ -395,6 +395,75 @@ loop_analysis::visit_leave(ir_loop *ir)
}
}
+ /* Search the loop terminating conditions for those of the form 'i < c'
+ * where i is a loop induction variable, c is a constant, and < is any
+ * relative operator. From each of these we can infer an iteration count.
+ * Also figure out which terminator (if any) produces the smallest
+ * iteration count--this is the limiting terminator.
+ */
+ foreach_list(node, &ls->terminators) {
+ loop_terminator *t = (loop_terminator *) node;
+ ir_if *if_stmt = t->ir;
+
+ /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care
+ * about the former here.
+ */
+ ir_expression *cond = if_stmt->condition->as_expression();
+ if (cond == NULL)
+ continue;
+
+ switch (cond->operation) {
+ case ir_binop_less:
+ case ir_binop_greater:
+ case ir_binop_lequal:
+ case ir_binop_gequal: {
+ /* The expressions that we care about will either be of the form
+ * 'counter < limit' or 'limit < counter'. Figure out which is
+ * which.
+ */
+ ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
+ ir_constant *limit = cond->operands[1]->as_constant();
+ enum ir_expression_operation cmp = cond->operation;
+
+ if (limit == NULL) {
+ counter = cond->operands[1]->as_dereference_variable();
+ limit = cond->operands[0]->as_constant();
+
+ switch (cmp) {
+ case ir_binop_less: cmp = ir_binop_greater; break;
+ case ir_binop_greater: cmp = ir_binop_less; break;
+ case ir_binop_lequal: cmp = ir_binop_gequal; break;
+ case ir_binop_gequal: cmp = ir_binop_lequal; break;
+ default: assert(!"Should not get here.");
+ }
+ }
+
+ 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);
+
+ if (t->iterations >= 0 &&
+ (ls->limiting_terminator == NULL ||
+ t->iterations < ls->limiting_terminator->iterations)) {
+ ls->limiting_terminator = t;
+ }
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
return visit_continue;
}
diff --git a/src/glsl/loop_analysis.h b/src/glsl/loop_analysis.h
index 8e57dac..0208890 100644
--- a/src/glsl/loop_analysis.h
+++ b/src/glsl/loop_analysis.h
@@ -58,6 +58,13 @@ set_loop_controls(exec_list *instructions, loop_state *ls);
extern bool
unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations);
+ir_rvalue *
+find_initial_value(ir_loop *loop, ir_variable *var);
+
+int
+calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
+ enum ir_expression_operation op);
+
/**
* Tracking for all variables used in a loop
@@ -99,6 +106,14 @@ public:
exec_list terminators;
/**
+ * If any of the terminators in \c terminators leads to termination of the
+ * loop after a constant number of iterations, this is the terminator that
+ * leads to termination after the smallest number of iterations. Otherwise
+ * NULL.
+ */
+ loop_terminator *limiting_terminator;
+
+ /**
* Hash table containing all variables accessed in this loop
*/
hash_table *var_hash;
@@ -129,6 +144,7 @@ public:
this->contains_calls = false;
this->var_hash = hash_table_ctor(0, hash_table_pointer_hash,
hash_table_pointer_compare);
+ this->limiting_terminator = NULL;
}
~loop_variable_state()
@@ -227,7 +243,21 @@ public:
class loop_terminator : public exec_node {
public:
+ loop_terminator()
+ : ir(NULL), iterations(-1)
+ {
+ }
+
+ /**
+ * 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;
};
diff --git a/src/glsl/loop_controls.cpp b/src/glsl/loop_controls.cpp
index ce05e09..a14ea6b 100644
--- a/src/glsl/loop_controls.cpp
+++ b/src/glsl/loop_controls.cpp
@@ -183,9 +183,9 @@ loop_control_visitor::visit_leave(ir_loop *ir)
return visit_continue;
}
- /* Search the loop terminating conditions for one of the form 'i < c' where
- * i is a loop induction variable, c is a constant, and < is any relative
- * operator.
+ /* Figure out how many times the loop will run based on the iteration count
+ * annotations made by loop analysis, and give the loop a normative bound
+ * if possible.
*/
unsigned max_iterations =
ls->max_iterations < 0 ? INT_MAX : ls->max_iterations;
@@ -193,86 +193,32 @@ loop_control_visitor::visit_leave(ir_loop *ir)
if (ir->normative_bound >= 0)
max_iterations = ir->normative_bound;
+ /* If the limiting terminator has a lower iteration count than we'd
+ * previously inferred for this loop, then make the new iteration count the
+ * normative bound for this loop.
+ */
+ if (ls->limiting_terminator != NULL &&
+ (unsigned) ls->limiting_terminator->iterations < max_iterations) {
+ ir->normative_bound = ls->limiting_terminator->iterations;
+ max_iterations = ls->limiting_terminator->iterations;
+ }
+
+ /* Remove the conditional break statements associated with all terminators
+ * that are associated with a fixed iteration count; the normative bound
+ * will take care of terminating the loop.
+ */
foreach_list(node, &ls->terminators) {
loop_terminator *t = (loop_terminator *) node;
- ir_if *if_stmt = t->ir;
-
- /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care
- * about the former here.
- */
- ir_expression *cond = if_stmt->condition->as_expression();
- if (cond == NULL)
- continue;
-
- switch (cond->operation) {
- case ir_binop_less:
- case ir_binop_greater:
- case ir_binop_lequal:
- case ir_binop_gequal: {
- /* The expressions that we care about will either be of the form
- * 'counter < limit' or 'limit < counter'. Figure out which is
- * which.
- */
- ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
- ir_constant *limit = cond->operands[1]->as_constant();
- enum ir_expression_operation cmp = cond->operation;
-
- if (limit == NULL) {
- counter = cond->operands[1]->as_dereference_variable();
- limit = cond->operands[0]->as_constant();
-
- switch (cmp) {
- case ir_binop_less: cmp = ir_binop_greater; break;
- case ir_binop_greater: cmp = ir_binop_less; break;
- case ir_binop_lequal: cmp = ir_binop_gequal; break;
- case ir_binop_gequal: cmp = ir_binop_lequal; break;
- default: assert(!"Should not get here.");
- }
- }
-
- 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()) {
- const int iterations = calculate_iterations(init, limit,
- lv->increment,
- cmp);
- if (iterations >= 0) {
- /* If the new iteration count is lower than the previously
- * believed iteration count, then add a normative bound to
- * this loop.
- */
- if ((unsigned) iterations < max_iterations) {
- ir->normative_bound = iterations;
-
- max_iterations = iterations;
- }
-
- /* Remove the conditional break statement. The loop
- * controls are now set such that the exit condition will be
- * satisfied.
- */
- if_stmt->remove();
-
- assert(ls->num_loop_jumps > 0);
- ls->num_loop_jumps--;
-
- this->progress = true;
- }
-
- break;
- }
- break;
- }
- default:
- break;
- }
+ if (t->iterations < 0)
+ continue;
+
+ t->ir->remove();
+
+ assert(ls->num_loop_jumps > 0);
+ ls->num_loop_jumps--;
+
+ this->progress = true;
}
/* If we have proven the one of the loop exit conditions is satisifed before
--
1.8.4.2
More information about the mesa-dev
mailing list