loop_controls.cpp revision bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0
1/* 2 * Copyright © 2010 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24#include <climits> 25#include "main/compiler.h" 26#include "glsl_types.h" 27#include "loop_analysis.h" 28#include "ir_hierarchical_visitor.h" 29 30/** 31 * Find an initializer of a variable outside a loop 32 * 33 * Works backwards from the loop to find the pre-loop value of the variable. 34 * This is used, for example, to find the initial value of loop induction 35 * variables. 36 * 37 * \param loop Loop where \c var is an induction variable 38 * \param var Variable whose initializer is to be found 39 * 40 * \return 41 * The \c ir_rvalue assigned to the variable outside the loop. May return 42 * \c NULL if no initializer can be found. 43 */ 44ir_rvalue * 45find_initial_value(ir_loop *loop, ir_variable *var) 46{ 47 for (exec_node *node = loop->prev; 48 !node->is_head_sentinel(); 49 node = node->prev) { 50 ir_instruction *ir = (ir_instruction *) node; 51 52 switch (ir->ir_type) { 53 case ir_type_call: 54 case ir_type_loop: 55 case ir_type_loop_jump: 56 case ir_type_return: 57 case ir_type_if: 58 return NULL; 59 60 case ir_type_function: 61 case ir_type_function_signature: 62 assert(!"Should not get here."); 63 return NULL; 64 65 case ir_type_assignment: { 66 ir_assignment *assign = ir->as_assignment(); 67 ir_variable *assignee = assign->lhs->whole_variable_referenced(); 68 69 if (assignee == var) 70 return (assign->condition != NULL) ? NULL : assign->rhs; 71 72 break; 73 } 74 75 default: 76 break; 77 } 78 } 79 80 return NULL; 81} 82 83 84int 85calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, 86 enum ir_expression_operation op) 87{ 88 void *mem_ctx = talloc_init(__func__); 89 90 ir_expression *const sub = 91 new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from); 92 93 ir_expression *const div = 94 new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment); 95 96 ir_constant *iter = div->constant_expression_value(); 97 98 if (iter == NULL) 99 return -1; 100 101 if (!iter->type->is_integer()) { 102 ir_rvalue *cast = 103 new(mem_ctx) ir_expression(ir_unop_f2i, glsl_type::int_type, iter, 104 NULL); 105 106 iter = cast->constant_expression_value(); 107 } 108 109 int iter_value = iter->get_int_component(0); 110 111 /* Make sure that the calculated number of iterations satisfies the exit 112 * condition. This is needed to catch off-by-one errors and some types of 113 * ill-formed loops. For example, we need to detect that the following 114 * loop does not have a maximum iteration count. 115 * 116 * for (float x = 0.0; x != 0.9; x += 0.2) 117 * ; 118 */ 119 const int bias[] = { -1, 0, 1 }; 120 bool valid_loop = false; 121 122 for (unsigned i = 0; i < Elements(bias); i++) { 123 iter = (increment->type->is_integer()) 124 ? new(mem_ctx) ir_constant(iter_value + bias[i]) 125 : new(mem_ctx) ir_constant(float(iter_value + bias[i])); 126 127 ir_expression *const mul = 128 new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter, 129 increment); 130 131 ir_expression *const add = 132 new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from); 133 134 ir_expression *const cmp = 135 new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to); 136 137 ir_constant *const cmp_result = cmp->constant_expression_value(); 138 139 assert(cmp_result != NULL); 140 if (cmp_result->get_bool_component(0)) { 141 iter_value += bias[i]; 142 valid_loop = true; 143 break; 144 } 145 } 146 147 talloc_free(mem_ctx); 148 return (valid_loop) ? iter_value : -1; 149} 150 151 152class loop_control_visitor : public ir_hierarchical_visitor { 153public: 154 loop_control_visitor(loop_state *state) 155 { 156 this->state = state; 157 this->progress = false; 158 } 159 160 virtual ir_visitor_status visit_leave(ir_loop *ir); 161 162 loop_state *state; 163 164 bool progress; 165}; 166 167 168ir_visitor_status 169loop_control_visitor::visit_leave(ir_loop *ir) 170{ 171 loop_variable_state *const ls = this->state->get(ir); 172 173 /* If we've entered a loop that hasn't been analyzed, something really, 174 * really bad has happened. 175 */ 176 if (ls == NULL) { 177 assert(ls != NULL); 178 return visit_continue; 179 } 180 181 /* Search the loop terminating conditions for one of the form 'i < c' where 182 * i is a loop induction variable, c is a constant, and < is any relative 183 * operator. 184 */ 185 int max_iterations = INT_MAX; 186 foreach_list(node, &ls->terminators) { 187 loop_terminator *t = (loop_terminator *) node; 188 ir_if *if_stmt = t->ir; 189 190 /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care 191 * about the former here. 192 */ 193 ir_expression *cond = if_stmt->condition->as_expression(); 194 if (cond == NULL) 195 continue; 196 197 switch (cond->operation) { 198 case ir_binop_less: 199 case ir_binop_greater: 200 case ir_binop_lequal: 201 case ir_binop_gequal: { 202 /* The expressions that we care about will either be of the form 203 * 'counter < limit' or 'limit < counter'. Figure out which is 204 * which. 205 */ 206 ir_rvalue *counter = cond->operands[0]->as_dereference_variable(); 207 ir_constant *limit = cond->operands[1]->constant_expression_value(); 208 enum ir_expression_operation cmp = cond->operation; 209 210 if (limit == NULL) { 211 counter = cond->operands[1]->as_dereference_variable(); 212 limit = cond->operands[0]->constant_expression_value(); 213 214 switch (cmp) { 215 case ir_binop_less: cmp = ir_binop_gequal; break; 216 case ir_binop_greater: cmp = ir_binop_lequal; break; 217 case ir_binop_lequal: cmp = ir_binop_greater; break; 218 case ir_binop_gequal: cmp = ir_binop_less; break; 219 default: assert(!"Should not get here."); 220 } 221 } 222 223 if ((counter == NULL) || (limit == NULL)) 224 break; 225 226 ir_variable *var = counter->variable_referenced(); 227 228 ir_rvalue *init = find_initial_value(ir, var); 229 230 foreach_list(iv_node, &ls->induction_variables) { 231 loop_variable *lv = (loop_variable *) iv_node; 232 233 if (lv->var == var) { 234 const int iterations = calculate_iterations(init, limit, 235 lv->increment, 236 cmp); 237 if (iterations > 0) { 238 /* If the new iteration count is lower than the previously 239 * believed iteration count, update the loop control values. 240 */ 241 if (iterations < max_iterations) { 242 ir->from = init->clone(ir, NULL); 243 ir->to = limit->clone(ir, NULL); 244 ir->increment = lv->increment->clone(ir, NULL); 245 ir->counter = lv->var; 246 ir->cmp = cmp; 247 248 max_iterations = iterations; 249 } 250 251 /* Remove the conditional break statement. The loop 252 * controls are now set such that the exit condition will be 253 * satisfied. 254 */ 255 if_stmt->remove(); 256 this->progress = true; 257 } 258 259 break; 260 } 261 } 262 break; 263 } 264 265 default: 266 break; 267 } 268 } 269 270 return visit_continue; 271} 272 273 274bool 275set_loop_controls(exec_list *instructions, loop_state *ls) 276{ 277 loop_control_visitor v(ls); 278 279 v.run(instructions); 280 281 return v.progress; 282} 283