diff options
| -rw-r--r-- | src/glsl/Makefile | 1 | ||||
| -rw-r--r-- | src/glsl/Makefile.am | 3 | ||||
| -rw-r--r-- | src/glsl/loop_analysis.h | 20 | ||||
| -rw-r--r-- | src/glsl/loop_controls.cpp | 282 |
4 files changed, 305 insertions, 1 deletions
diff --git a/src/glsl/Makefile b/src/glsl/Makefile index e5375eff443..ed1453b14b5 100644 --- a/src/glsl/Makefile +++ b/src/glsl/Makefile @@ -73,6 +73,7 @@ CXX_SOURCES = \ linker.cpp \ link_functions.cpp \ loop_analysis.cpp \ + loop_controls.cpp \ s_expression.cpp LIBS = \ diff --git a/src/glsl/Makefile.am b/src/glsl/Makefile.am index 55e4332af53..0811ffbff1f 100644 --- a/src/glsl/Makefile.am +++ b/src/glsl/Makefile.am @@ -63,7 +63,8 @@ glsl_SOURCES = \ ir_validate.cpp \ ir_vec_index_to_swizzle.cpp \ linker.cpp \ - loop_analysis.cpp + loop_analysis.cpp \ + loop_controls.cpp BUILT_SOURCES = glsl_parser.h glsl_parser.cpp glsl_lexer.cpp CLEANFILES = $(BUILT_SOURCES) diff --git a/src/glsl/loop_analysis.h b/src/glsl/loop_analysis.h index 50c512f847f..b7c05149438 100644 --- a/src/glsl/loop_analysis.h +++ b/src/glsl/loop_analysis.h @@ -37,6 +37,26 @@ analyze_loop_variables(exec_list *instructions); /** + * Fill in loop control fields + * + * Based on analysis of loop variables, this function tries to remove sequences + * in the loop of the form + * + * (if (expression bool ...) (break)) + * + * and fill in the \c ir_loop::from, \c ir_loop::to, and \c ir_loop::counter + * fields of the \c ir_loop. + * + * In this process, some conditional break-statements may be eliminated + * altogether. For example, if it is provable that one loop exit condition will + * always be satisfied before another, the unnecessary exit condition will be + * removed. + */ +extern bool +set_loop_controls(exec_list *instructions, loop_state *ls); + + +/** * Tracking for all variables used in a loop */ class loop_variable_state : public exec_node { diff --git a/src/glsl/loop_controls.cpp b/src/glsl/loop_controls.cpp new file mode 100644 index 00000000000..2eddb913648 --- /dev/null +++ b/src/glsl/loop_controls.cpp @@ -0,0 +1,282 @@ +/* + * 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 <climits> +#include "main/compiler.h" +#include "glsl_types.h" +#include "loop_analysis.h" +#include "ir_hierarchical_visitor.h" + +/** + * Find an initializer of a variable outside a loop + * + * Works backwards from the loop to find the pre-loop value of the variable. + * This is used, for example, to find the initial value of loop induction + * variables. + * + * \param loop Loop where \c var is an induction variable + * \param var Variable whose initializer is to be found + * + * \return + * The \c ir_rvalue assigned to the variable outside the loop. May return + * \c NULL if no initializer can be found. + */ +ir_rvalue * +find_initial_value(ir_loop *loop, ir_variable *var) +{ + for (exec_node *node = loop->prev; + !node->is_head_sentinel(); + node = node->prev) { + ir_instruction *ir = (ir_instruction *) node; + + switch (ir->ir_type) { + case ir_type_call: + case ir_type_loop: + case ir_type_loop_jump: + case ir_type_return: + case ir_type_if: + return NULL; + + case ir_type_function: + case ir_type_function_signature: + assert(!"Should not get here."); + return NULL; + + case ir_type_assignment: { + ir_assignment *assign = ir->as_assignment(); + ir_variable *assignee = assign->lhs->whole_variable_referenced(); + + if (assignee == var) + return (assign->condition != NULL) ? NULL : assign->rhs; + + break; + } + + default: + break; + } + } + + return NULL; +} + + +int +calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, + enum ir_expression_operation op) +{ + void *mem_ctx = talloc_init(__func__); + + ir_expression *const sub = + new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from); + + ir_expression *const div = + new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment); + + ir_constant *iter = div->constant_expression_value(); + + if (iter == NULL) + return -1; + + if (!iter->type->is_integer()) { + ir_rvalue *cast = + new(mem_ctx) ir_expression(ir_unop_f2i, glsl_type::int_type, iter, + NULL); + + iter = cast->constant_expression_value(); + } + + int iter_value = iter->get_int_component(0); + + /* Make sure that the calculated number of iterations satisfies the exit + * condition. This is needed to catch off-by-one errors and some types of + * ill-formed loops. For example, we need to detect that the following + * loop does not have a maximum iteration count. + * + * for (float x = 0.0; x != 0.9; x += 0.2) + * ; + */ + const int bias[] = { -1, 0, 1 }; + bool valid_loop = false; + + for (unsigned i = 0; i < Elements(bias); i++) { + iter = (increment->type->is_integer()) + ? new(mem_ctx) ir_constant(iter_value + bias[i]) + : new(mem_ctx) ir_constant(float(iter_value + bias[i])); + + ir_expression *const mul = + new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter, + increment); + + ir_expression *const add = + new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from); + + ir_expression *const cmp = + new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to); + + ir_constant *const cmp_result = cmp->constant_expression_value(); + + assert(cmp_result != NULL); + if (cmp_result->get_bool_component(0)) { + iter_value += bias[i]; + valid_loop = true; + break; + } + } + + talloc_free(mem_ctx); + return (valid_loop) ? iter_value : -1; +} + + +class loop_control_visitor : public ir_hierarchical_visitor { +public: + loop_control_visitor(loop_state *state) + { + this->state = state; + this->progress = false; + } + + virtual ir_visitor_status visit_leave(ir_loop *ir); + + loop_state *state; + + bool progress; +}; + + +ir_visitor_status +loop_control_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) { + assert(ls != NULL); + 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. + */ + int max_iterations = INT_MAX; + 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]->constant_expression_value(); + enum ir_expression_operation cmp = cond->operation; + + if (limit == NULL) { + counter = cond->operands[1]->as_dereference_variable(); + limit = cond->operands[0]->constant_expression_value(); + + switch (cmp) { + case ir_binop_less: cmp = ir_binop_gequal; break; + case ir_binop_greater: cmp = ir_binop_lequal; break; + case ir_binop_lequal: cmp = ir_binop_greater; break; + case ir_binop_gequal: cmp = ir_binop_less; 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); + + foreach_list(iv_node, &ls->induction_variables) { + loop_variable *lv = (loop_variable *) iv_node; + + if (lv->var == 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, update the loop control values. + */ + if (iterations < max_iterations) { + ir->from = init->clone(ir, NULL); + ir->to = limit->clone(ir, NULL); + ir->increment = lv->increment->clone(ir, NULL); + ir->counter = lv->var; + ir->cmp = cmp; + + 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(); + this->progress = true; + } + + break; + } + } + break; + } + + default: + break; + } + } + + return visit_continue; +} + + +bool +set_loop_controls(exec_list *instructions, loop_state *ls) +{ + loop_control_visitor v(ls); + + v.run(instructions); + + return v.progress; +} |