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 <limits.h> 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 */ 44 ir_rvalue * 45 find_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 84 int 85 calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, 86 enum ir_expression_operation op) 87 { 88 if (from == NULL || to == NULL || increment == NULL) 89 return -1; 90 91 void *mem_ctx = ralloc_context(NULL); 92 93 ir_expression *const sub = 94 new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from); 95 96 ir_expression *const div = 97 new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment); 98 99 ir_constant *iter = div->constant_expression_value(); 100 101 if (iter == NULL) 102 return -1; 103 104 if (!iter->type->is_integer()) { 105 ir_rvalue *cast = 106 new(mem_ctx) ir_expression(ir_unop_f2i, glsl_type::int_type, iter, 107 NULL); 108 109 iter = cast->constant_expression_value(); 110 } 111 112 int iter_value = iter->get_int_component(0); 113 114 /* Make sure that the calculated number of iterations satisfies the exit 115 * condition. This is needed to catch off-by-one errors and some types of 116 * ill-formed loops. For example, we need to detect that the following 117 * loop does not have a maximum iteration count. 118 * 119 * for (float x = 0.0; x != 0.9; x += 0.2) 120 * ; 121 */ 122 const int bias[] = { -1, 0, 1 }; 123 bool valid_loop = false; 124 125 for (unsigned i = 0; i < Elements(bias); i++) { 126 iter = (increment->type->is_integer()) 127 ? new(mem_ctx) ir_constant(iter_value + bias[i]) 128 : new(mem_ctx) ir_constant(float(iter_value + bias[i])); 129 130 ir_expression *const mul = 131 new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter, 132 increment); 133 134 ir_expression *const add = 135 new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from); 136 137 ir_expression *const cmp = 138 new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to); 139 140 ir_constant *const cmp_result = cmp->constant_expression_value(); 141 142 assert(cmp_result != NULL); 143 if (cmp_result->get_bool_component(0)) { 144 iter_value += bias[i]; 145 valid_loop = true; 146 break; 147 } 148 } 149 150 ralloc_free(mem_ctx); 151 return (valid_loop) ? iter_value : -1; 152 } 153 154 155 class loop_control_visitor : public ir_hierarchical_visitor { 156 public: 157 loop_control_visitor(loop_state *state) 158 { 159 this->state = state; 160 this->progress = false; 161 } 162 163 virtual ir_visitor_status visit_leave(ir_loop *ir); 164 165 loop_state *state; 166 167 bool progress; 168 }; 169 170 171 ir_visitor_status 172 loop_control_visitor::visit_leave(ir_loop *ir) 173 { 174 loop_variable_state *const ls = this->state->get(ir); 175 176 /* If we've entered a loop that hasn't been analyzed, something really, 177 * really bad has happened. 178 */ 179 if (ls == NULL) { 180 assert(ls != NULL); 181 return visit_continue; 182 } 183 184 /* Search the loop terminating conditions for one of the form 'i < c' where 185 * i is a loop induction variable, c is a constant, and < is any relative 186 * operator. 187 */ 188 int max_iterations = ls->max_iterations; 189 190 if(ir->from && ir->to && ir->increment) 191 max_iterations = calculate_iterations(ir->from, ir->to, ir->increment, (ir_expression_operation)ir->cmp); 192 193 if(max_iterations < 0) 194 max_iterations = INT_MAX; 195 196 foreach_list(node, &ls->terminators) { 197 loop_terminator *t = (loop_terminator *) node; 198 ir_if *if_stmt = t->ir; 199 200 /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care 201 * about the former here. 202 */ 203 ir_expression *cond = if_stmt->condition->as_expression(); 204 if (cond == NULL) 205 continue; 206 207 switch (cond->operation) { 208 case ir_binop_less: 209 case ir_binop_greater: 210 case ir_binop_lequal: 211 case ir_binop_gequal: { 212 /* The expressions that we care about will either be of the form 213 * 'counter < limit' or 'limit < counter'. Figure out which is 214 * which. 215 */ 216 ir_rvalue *counter = cond->operands[0]->as_dereference_variable(); 217 ir_constant *limit = cond->operands[1]->as_constant(); 218 enum ir_expression_operation cmp = cond->operation; 219 220 if (limit == NULL) { 221 counter = cond->operands[1]->as_dereference_variable(); 222 limit = cond->operands[0]->as_constant(); 223 224 switch (cmp) { 225 case ir_binop_less: cmp = ir_binop_gequal; break; 226 case ir_binop_greater: cmp = ir_binop_lequal; break; 227 case ir_binop_lequal: cmp = ir_binop_greater; break; 228 case ir_binop_gequal: cmp = ir_binop_less; break; 229 default: assert(!"Should not get here."); 230 } 231 } 232 233 if ((counter == NULL) || (limit == NULL)) 234 break; 235 236 ir_variable *var = counter->variable_referenced(); 237 238 ir_rvalue *init = find_initial_value(ir, var); 239 240 foreach_list(iv_node, &ls->induction_variables) { 241 loop_variable *lv = (loop_variable *) iv_node; 242 243 if (lv->var == var) { 244 const int iterations = calculate_iterations(init, limit, 245 lv->increment, 246 cmp); 247 if (iterations >= 0) { 248 /* If the new iteration count is lower than the previously 249 * believed iteration count, update the loop control values. 250 */ 251 if (iterations < max_iterations) { 252 ir->from = init->clone(ir, NULL); 253 ir->to = limit->clone(ir, NULL); 254 ir->increment = lv->increment->clone(ir, NULL); 255 ir->counter = lv->var; 256 ir->cmp = cmp; 257 258 max_iterations = iterations; 259 } 260 261 /* Remove the conditional break statement. The loop 262 * controls are now set such that the exit condition will be 263 * satisfied. 264 */ 265 if_stmt->remove(); 266 267 assert(ls->num_loop_jumps > 0); 268 ls->num_loop_jumps--; 269 270 this->progress = true; 271 } 272 273 break; 274 } 275 } 276 break; 277 } 278 279 default: 280 break; 281 } 282 } 283 284 /* If we have proven the one of the loop exit conditions is satisifed before 285 * running the loop once, remove the loop. 286 */ 287 if (max_iterations == 0) 288 ir->remove(); 289 else 290 ls->max_iterations = max_iterations; 291 292 return visit_continue; 293 } 294 295 296 bool 297 set_loop_controls(exec_list *instructions, loop_state *ls) 298 { 299 loop_control_visitor v(ls); 300 301 v.run(instructions); 302 303 return v.progress; 304 } 305
