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 "glsl_types.h" 25 #include "loop_analysis.h" 26 #include "ir_hierarchical_visitor.h" 27 28 static bool is_loop_terminator(ir_if *ir); 29 30 static bool all_expression_operands_are_loop_constant(ir_rvalue *, 31 hash_table *); 32 33 static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *); 34 35 36 loop_state::loop_state() 37 { 38 this->ht = hash_table_ctor(0, hash_table_pointer_hash, 39 hash_table_pointer_compare); 40 this->mem_ctx = hieralloc_init("loop state"); 41 } 42 43 44 loop_state::~loop_state() 45 { 46 hash_table_dtor(this->ht); 47 hieralloc_free(this->mem_ctx); 48 } 49 50 51 loop_variable_state * 52 loop_state::insert(ir_loop *ir) 53 { 54 loop_variable_state *ls = new(this->mem_ctx) loop_variable_state; 55 hash_table_insert(this->ht, ls, ir); 56 57 return ls; 58 } 59 60 61 loop_variable_state * 62 loop_state::get(const ir_loop *ir) 63 { 64 return (loop_variable_state *) hash_table_find(this->ht, ir); 65 } 66 67 68 loop_variable * 69 loop_variable_state::get(const ir_variable *ir) 70 { 71 return (loop_variable *) hash_table_find(this->var_hash, ir); 72 } 73 74 75 loop_variable * 76 loop_variable_state::insert(ir_variable *var) 77 { 78 void *mem_ctx = hieralloc_parent(this); 79 loop_variable *lv = hieralloc_zero(mem_ctx, loop_variable); 80 81 lv->var = var; 82 83 hash_table_insert(this->var_hash, lv, lv->var); 84 this->variables.push_tail(lv); 85 86 return lv; 87 } 88 89 90 loop_terminator * 91 loop_variable_state::insert(ir_if *if_stmt) 92 { 93 void *mem_ctx = hieralloc_parent(this); 94 loop_terminator *t = hieralloc_zero(mem_ctx, loop_terminator); 95 96 t->ir = if_stmt; 97 this->terminators.push_tail(t); 98 99 return t; 100 } 101 102 103 class loop_analysis : public ir_hierarchical_visitor { 104 public: 105 loop_analysis(); 106 107 virtual ir_visitor_status visit(ir_loop_jump *); 108 virtual ir_visitor_status visit(ir_dereference_variable *); 109 110 virtual ir_visitor_status visit_enter(ir_loop *); 111 virtual ir_visitor_status visit_leave(ir_loop *); 112 virtual ir_visitor_status visit_enter(ir_assignment *); 113 virtual ir_visitor_status visit_leave(ir_assignment *); 114 virtual ir_visitor_status visit_enter(ir_if *); 115 virtual ir_visitor_status visit_leave(ir_if *); 116 117 loop_state *loops; 118 119 int if_statement_depth; 120 121 ir_assignment *current_assignment; 122 123 exec_list state; 124 }; 125 126 127 loop_analysis::loop_analysis() 128 { 129 this->loops = new loop_state; 130 131 this->if_statement_depth = 0; 132 this->current_assignment = NULL; 133 } 134 135 136 ir_visitor_status 137 loop_analysis::visit(ir_loop_jump *ir) 138 { 139 (void) ir; 140 141 assert(!this->state.is_empty()); 142 143 loop_variable_state *const ls = 144 (loop_variable_state *) this->state.get_head(); 145 146 ls->num_loop_jumps++; 147 148 return visit_continue; 149 } 150 151 152 ir_visitor_status 153 loop_analysis::visit(ir_dereference_variable *ir) 154 { 155 /* If we're not somewhere inside a loop, there's nothing to do. 156 */ 157 if (this->state.is_empty()) 158 return visit_continue; 159 160 loop_variable_state *const ls = 161 (loop_variable_state *) this->state.get_head(); 162 163 ir_variable *var = ir->variable_referenced(); 164 loop_variable *lv = ls->get(var); 165 166 if (lv == NULL) { 167 lv = ls->insert(var); 168 lv->read_before_write = !this->in_assignee; 169 } 170 171 if (this->in_assignee) { 172 assert(this->current_assignment != NULL); 173 174 lv->conditional_assignment = (this->if_statement_depth > 0) 175 || (this->current_assignment->condition != NULL); 176 177 if (lv->first_assignment == NULL) { 178 assert(lv->num_assignments == 0); 179 180 lv->first_assignment = this->current_assignment; 181 } 182 183 lv->num_assignments++; 184 } else if (lv->first_assignment == this->current_assignment) { 185 /* This catches the case where the variable is used in the RHS of an 186 * assignment where it is also in the LHS. 187 */ 188 lv->read_before_write = true; 189 } 190 191 return visit_continue; 192 } 193 194 ir_visitor_status 195 loop_analysis::visit_enter(ir_loop *ir) 196 { 197 loop_variable_state *ls = this->loops->insert(ir); 198 this->state.push_head(ls); 199 200 return visit_continue; 201 } 202 203 ir_visitor_status 204 loop_analysis::visit_leave(ir_loop *ir) 205 { 206 loop_variable_state *const ls = 207 (loop_variable_state *) this->state.pop_head(); 208 209 210 foreach_list(node, &ir->body_instructions) { 211 /* Skip over declarations at the start of a loop. 212 */ 213 if (((ir_instruction *) node)->as_variable()) 214 continue; 215 216 ir_if *if_stmt = ((ir_instruction *) node)->as_if(); 217 218 if ((if_stmt != NULL) && is_loop_terminator(if_stmt)) 219 ls->insert(if_stmt); 220 else 221 break; 222 } 223 224 225 foreach_list_safe(node, &ls->variables) { 226 loop_variable *lv = (loop_variable *) node; 227 228 /* Move variables that are already marked as being loop constant to 229 * a separate list. These trivially don't need to be tested. 230 */ 231 if (lv->is_loop_constant()) { 232 lv->remove(); 233 ls->constants.push_tail(lv); 234 } 235 } 236 237 /* Each variable assigned in the loop that isn't already marked as being loop 238 * constant might still be loop constant. The requirements at this point 239 * are: 240 * 241 * - Variable is written before it is read. 242 * 243 * - Only one assignment to the variable. 244 * 245 * - All operands on the RHS of the assignment are also loop constants. 246 * 247 * The last requirement is the reason for the progress loop. A variable 248 * marked as a loop constant on one pass may allow other variables to be 249 * marked as loop constant on following passes. 250 */ 251 bool progress; 252 do { 253 progress = false; 254 255 foreach_list_safe(node, &ls->variables) { 256 loop_variable *lv = (loop_variable *) node; 257 258 if (lv->conditional_assignment || (lv->num_assignments > 1)) 259 continue; 260 261 /* Process the RHS of the assignment. If all of the variables 262 * accessed there are loop constants, then add this 263 */ 264 ir_rvalue *const rhs = lv->first_assignment->rhs; 265 if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) { 266 lv->rhs_clean = true; 267 268 if (lv->is_loop_constant()) { 269 progress = true; 270 271 lv->remove(); 272 ls->constants.push_tail(lv); 273 } 274 } 275 } 276 } while (progress); 277 278 /* The remaining variables that are not loop invariant might be loop 279 * induction variables. 280 */ 281 foreach_list_safe(node, &ls->variables) { 282 loop_variable *lv = (loop_variable *) node; 283 284 /* If there is more than one assignment to a variable, it cannot be a 285 * loop induction variable. This isn't strictly true, but this is a 286 * very simple induction variable detector, and it can't handle more 287 * complex cases. 288 */ 289 if (lv->num_assignments > 1) 290 continue; 291 292 /* All of the variables with zero assignments in the loop are loop 293 * invariant, and they should have already been filtered out. 294 */ 295 assert(lv->num_assignments == 1); 296 assert(lv->first_assignment != NULL); 297 298 /* The assignmnet to the variable in the loop must be unconditional. 299 */ 300 if (lv->conditional_assignment) 301 continue; 302 303 /* Basic loop induction variables have a single assignment in the loop 304 * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a 305 * loop invariant. 306 */ 307 ir_rvalue *const inc = 308 get_basic_induction_increment(lv->first_assignment, ls->var_hash); 309 if (inc != NULL) { 310 lv->iv_scale = NULL; 311 lv->biv = lv->var; 312 lv->increment = inc; 313 314 lv->remove(); 315 ls->induction_variables.push_tail(lv); 316 } 317 } 318 319 return visit_continue; 320 } 321 322 ir_visitor_status 323 loop_analysis::visit_enter(ir_if *ir) 324 { 325 (void) ir; 326 327 if (!this->state.is_empty()) 328 this->if_statement_depth++; 329 330 return visit_continue; 331 } 332 333 ir_visitor_status 334 loop_analysis::visit_leave(ir_if *ir) 335 { 336 (void) ir; 337 338 if (!this->state.is_empty()) 339 this->if_statement_depth--; 340 341 return visit_continue; 342 } 343 344 ir_visitor_status 345 loop_analysis::visit_enter(ir_assignment *ir) 346 { 347 /* If we're not somewhere inside a loop, there's nothing to do. 348 */ 349 if (this->state.is_empty()) 350 return visit_continue_with_parent; 351 352 this->current_assignment = ir; 353 354 return visit_continue; 355 } 356 357 ir_visitor_status 358 loop_analysis::visit_leave(ir_assignment *ir) 359 { 360 /* Since the visit_enter exits with visit_continue_with_parent for this 361 * case, the loop state stack should never be empty here. 362 */ 363 assert(!this->state.is_empty()); 364 365 assert(this->current_assignment == ir); 366 this->current_assignment = NULL; 367 368 return visit_continue; 369 } 370 371 372 class examine_rhs : public ir_hierarchical_visitor { 373 public: 374 examine_rhs(hash_table *loop_variables) 375 { 376 this->only_uses_loop_constants = true; 377 this->loop_variables = loop_variables; 378 } 379 380 virtual ir_visitor_status visit(ir_dereference_variable *ir) 381 { 382 loop_variable *lv = 383 (loop_variable *) hash_table_find(this->loop_variables, ir->var); 384 385 assert(lv != NULL); 386 387 if (lv->is_loop_constant()) { 388 return visit_continue; 389 } else { 390 this->only_uses_loop_constants = false; 391 return visit_stop; 392 } 393 } 394 395 hash_table *loop_variables; 396 bool only_uses_loop_constants; 397 }; 398 399 400 bool 401 all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables) 402 { 403 examine_rhs v(variables); 404 405 ir->accept(&v); 406 407 return v.only_uses_loop_constants; 408 } 409 410 411 ir_rvalue * 412 get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) 413 { 414 /* The RHS must be a binary expression. 415 */ 416 ir_expression *const rhs = ir->rhs->as_expression(); 417 if ((rhs == NULL) 418 || ((rhs->operation != ir_binop_add) 419 && (rhs->operation != ir_binop_sub))) 420 return NULL; 421 422 /* One of the of operands of the expression must be the variable assigned. 423 * If the operation is subtraction, the variable in question must be the 424 * "left" operand. 425 */ 426 ir_variable *const var = ir->lhs->variable_referenced(); 427 428 ir_variable *const op0 = rhs->operands[0]->variable_referenced(); 429 ir_variable *const op1 = rhs->operands[1]->variable_referenced(); 430 431 if (((op0 != var) && (op1 != var)) 432 || ((op1 == var) && (rhs->operation == ir_binop_sub))) 433 return NULL; 434 435 ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0]; 436 437 if (inc->as_constant() == NULL) { 438 ir_variable *const inc_var = inc->variable_referenced(); 439 if (inc_var != NULL) { 440 loop_variable *lv = 441 (loop_variable *) hash_table_find(var_hash, inc_var); 442 443 if (!lv->is_loop_constant()) 444 inc = NULL; 445 } else 446 inc = NULL; 447 } 448 449 if ((inc != NULL) && (rhs->operation == ir_binop_sub)) { 450 void *mem_ctx = hieralloc_parent(ir); 451 452 inc = new(mem_ctx) ir_expression(ir_unop_neg, 453 inc->type, 454 inc->clone(mem_ctx, NULL), 455 NULL); 456 } 457 458 return inc; 459 } 460 461 462 /** 463 * Detect whether an if-statement is a loop terminating condition 464 * 465 * Detects if-statements of the form 466 * 467 * (if (expression bool ...) (break)) 468 */ 469 bool 470 is_loop_terminator(ir_if *ir) 471 { 472 if (!ir->else_instructions.is_empty()) 473 return false; 474 475 ir_instruction *const inst = 476 (ir_instruction *) ir->then_instructions.get_head(); 477 assert(inst != NULL); 478 479 if (inst->ir_type != ir_type_loop_jump) 480 return false; 481 482 ir_loop_jump *const jump = (ir_loop_jump *) inst; 483 if (jump->mode != ir_loop_jump::jump_break) 484 return false; 485 486 return true; 487 } 488 489 490 loop_state * 491 analyze_loop_variables(exec_list *instructions) 492 { 493 loop_analysis v; 494 495 v.run(instructions); 496 return v.loops; 497 } 498
