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