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 "compiler/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 const ir_expression_operation op = iter->type->is_double() 106 ? ir_unop_d2i : ir_unop_f2i; 107 ir_rvalue *cast = 108 new(mem_ctx) ir_expression(op, glsl_type::int_type, iter, NULL); 109 110 iter = cast->constant_expression_value(); 111 } 112 113 int iter_value = iter->get_int_component(0); 114 115 /* Make sure that the calculated number of iterations satisfies the exit 116 * condition. This is needed to catch off-by-one errors and some types of 117 * ill-formed loops. For example, we need to detect that the following 118 * loop does not have a maximum iteration count. 119 * 120 * for (float x = 0.0; x != 0.9; x += 0.2) 121 * ; 122 */ 123 const int bias[] = { -1, 0, 1 }; 124 bool valid_loop = false; 125 126 for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) { 127 /* Increment may be of type int, uint or float. */ 128 switch (increment->type->base_type) { 129 case GLSL_TYPE_INT: 130 iter = new(mem_ctx) ir_constant(iter_value + bias[i]); 131 break; 132 case GLSL_TYPE_UINT: 133 iter = new(mem_ctx) ir_constant(unsigned(iter_value + bias[i])); 134 break; 135 case GLSL_TYPE_FLOAT: 136 iter = new(mem_ctx) ir_constant(float(iter_value + bias[i])); 137 break; 138 case GLSL_TYPE_DOUBLE: 139 iter = new(mem_ctx) ir_constant(double(iter_value + bias[i])); 140 break; 141 default: 142 unreachable("Unsupported type for loop iterator."); 143 } 144 145 ir_expression *const mul = 146 new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter, 147 increment); 148 149 ir_expression *const add = 150 new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from); 151 152 ir_expression *const cmp = 153 new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to); 154 155 ir_constant *const cmp_result = cmp->constant_expression_value(); 156 157 assert(cmp_result != NULL); 158 if (cmp_result->get_bool_component(0)) { 159 iter_value += bias[i]; 160 valid_loop = true; 161 break; 162 } 163 } 164 165 ralloc_free(mem_ctx); 166 return (valid_loop) ? iter_value : -1; 167 } 168 169 namespace { 170 171 class loop_control_visitor : public ir_hierarchical_visitor { 172 public: 173 loop_control_visitor(loop_state *state) 174 { 175 this->state = state; 176 this->progress = false; 177 } 178 179 virtual ir_visitor_status visit_leave(ir_loop *ir); 180 181 loop_state *state; 182 183 bool progress; 184 }; 185 186 } /* anonymous namespace */ 187 188 ir_visitor_status 189 loop_control_visitor::visit_leave(ir_loop *ir) 190 { 191 loop_variable_state *const ls = this->state->get(ir); 192 193 /* If we've entered a loop that hasn't been analyzed, something really, 194 * really bad has happened. 195 */ 196 if (ls == NULL) { 197 assert(ls != NULL); 198 return visit_continue; 199 } 200 201 if (ls->limiting_terminator != NULL) { 202 /* If the limiting terminator has an iteration count of zero, then we've 203 * proven that the loop cannot run, so delete it. 204 */ 205 int iterations = ls->limiting_terminator->iterations; 206 if (iterations == 0) { 207 ir->remove(); 208 this->progress = true; 209 return visit_continue; 210 } 211 } 212 213 /* Remove the conditional break statements associated with all terminators 214 * that are associated with a fixed iteration count, except for the one 215 * associated with the limiting terminator--that one needs to stay, since 216 * it terminates the loop. Exception: if the loop still has a normative 217 * bound, then that terminates the loop, so we don't even need the limiting 218 * terminator. 219 */ 220 foreach_in_list(loop_terminator, t, &ls->terminators) { 221 if (t->iterations < 0) 222 continue; 223 224 if (t != ls->limiting_terminator) { 225 t->ir->remove(); 226 227 assert(ls->num_loop_jumps > 0); 228 ls->num_loop_jumps--; 229 230 this->progress = true; 231 } 232 } 233 234 return visit_continue; 235 } 236 237 238 bool 239 set_loop_controls(exec_list *instructions, loop_state *ls) 240 { 241 loop_control_visitor v(ls); 242 243 v.run(instructions); 244 245 return v.progress; 246 } 247
