1 /* 2 * Copyright 2010 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * constant 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, constant, 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 constantright 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 CONSTANTRIGHT 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 /** 25 * \file opt_constant_propagation.cpp 26 * 27 * Tracks assignments of constants to channels of variables, and 28 * usage of those constant channels with direct usage of the constants. 29 * 30 * This can lead to constant folding and algebraic optimizations in 31 * those later expressions, while causing no increase in instruction 32 * count (due to constants being generally free to load from a 33 * constant push buffer or as instruction immediate values) and 34 * possibly reducing register pressure. 35 */ 36 37 #include "ir.h" 38 #include "ir_visitor.h" 39 #include "ir_rvalue_visitor.h" 40 #include "ir_basic_block.h" 41 #include "ir_optimization.h" 42 #include "compiler/glsl_types.h" 43 #include "util/hash_table.h" 44 45 namespace { 46 47 class acp_entry : public exec_node 48 { 49 public: 50 /* override operator new from exec_node */ 51 DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(acp_entry) 52 53 acp_entry(ir_variable *var, unsigned write_mask, ir_constant *constant) 54 { 55 assert(var); 56 assert(constant); 57 this->var = var; 58 this->write_mask = write_mask; 59 this->constant = constant; 60 this->initial_values = write_mask; 61 } 62 63 acp_entry(const acp_entry *src) 64 { 65 this->var = src->var; 66 this->write_mask = src->write_mask; 67 this->constant = src->constant; 68 this->initial_values = src->initial_values; 69 } 70 71 ir_variable *var; 72 ir_constant *constant; 73 unsigned write_mask; 74 75 /** Mask of values initially available in the constant. */ 76 unsigned initial_values; 77 }; 78 79 80 class kill_entry : public exec_node 81 { 82 public: 83 /* override operator new from exec_node */ 84 DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(kill_entry) 85 86 kill_entry(ir_variable *var, unsigned write_mask) 87 { 88 assert(var); 89 this->var = var; 90 this->write_mask = write_mask; 91 } 92 93 ir_variable *var; 94 unsigned write_mask; 95 }; 96 97 class ir_constant_propagation_visitor : public ir_rvalue_visitor { 98 public: 99 ir_constant_propagation_visitor() 100 { 101 progress = false; 102 killed_all = false; 103 mem_ctx = ralloc_context(0); 104 this->lin_ctx = linear_alloc_parent(this->mem_ctx, 0); 105 this->acp = new(mem_ctx) exec_list; 106 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 107 _mesa_key_pointer_equal); 108 } 109 ~ir_constant_propagation_visitor() 110 { 111 ralloc_free(mem_ctx); 112 } 113 114 virtual ir_visitor_status visit_enter(class ir_loop *); 115 virtual ir_visitor_status visit_enter(class ir_function_signature *); 116 virtual ir_visitor_status visit_enter(class ir_function *); 117 virtual ir_visitor_status visit_leave(class ir_assignment *); 118 virtual ir_visitor_status visit_enter(class ir_call *); 119 virtual ir_visitor_status visit_enter(class ir_if *); 120 121 void add_constant(ir_assignment *ir); 122 void constant_folding(ir_rvalue **rvalue); 123 void constant_propagation(ir_rvalue **rvalue); 124 void kill(ir_variable *ir, unsigned write_mask); 125 void handle_if_block(exec_list *instructions); 126 void handle_rvalue(ir_rvalue **rvalue); 127 128 /** List of acp_entry: The available constants to propagate */ 129 exec_list *acp; 130 131 /** 132 * Hash table of kill_entry: The masks of variables whose values were 133 * killed in this block. 134 */ 135 hash_table *kills; 136 137 bool progress; 138 139 bool killed_all; 140 141 void *mem_ctx; 142 void *lin_ctx; 143 }; 144 145 146 void 147 ir_constant_propagation_visitor::constant_folding(ir_rvalue **rvalue) 148 { 149 if (this->in_assignee || *rvalue == NULL) 150 return; 151 152 if (ir_constant_fold(rvalue)) 153 this->progress = true; 154 155 ir_dereference_variable *var_ref = (*rvalue)->as_dereference_variable(); 156 if (var_ref && !var_ref->type->is_array()) { 157 ir_constant *constant = 158 var_ref->constant_expression_value(ralloc_parent(var_ref)); 159 if (constant) { 160 *rvalue = constant; 161 this->progress = true; 162 } 163 } 164 } 165 166 void 167 ir_constant_propagation_visitor::constant_propagation(ir_rvalue **rvalue) { 168 169 if (this->in_assignee || !*rvalue) 170 return; 171 172 const glsl_type *type = (*rvalue)->type; 173 if (!type->is_scalar() && !type->is_vector()) 174 return; 175 176 ir_swizzle *swiz = NULL; 177 ir_dereference_variable *deref = (*rvalue)->as_dereference_variable(); 178 if (!deref) { 179 swiz = (*rvalue)->as_swizzle(); 180 if (!swiz) 181 return; 182 183 deref = swiz->val->as_dereference_variable(); 184 if (!deref) 185 return; 186 } 187 188 ir_constant_data data; 189 memset(&data, 0, sizeof(data)); 190 191 for (unsigned int i = 0; i < type->components(); i++) { 192 int channel; 193 acp_entry *found = NULL; 194 195 if (swiz) { 196 switch (i) { 197 case 0: channel = swiz->mask.x; break; 198 case 1: channel = swiz->mask.y; break; 199 case 2: channel = swiz->mask.z; break; 200 case 3: channel = swiz->mask.w; break; 201 default: assert(!"shouldn't be reached"); channel = 0; break; 202 } 203 } else { 204 channel = i; 205 } 206 207 foreach_in_list(acp_entry, entry, this->acp) { 208 if (entry->var == deref->var && entry->write_mask & (1 << channel)) { 209 found = entry; 210 break; 211 } 212 } 213 214 if (!found) 215 return; 216 217 int rhs_channel = 0; 218 for (int j = 0; j < 4; j++) { 219 if (j == channel) 220 break; 221 if (found->initial_values & (1 << j)) 222 rhs_channel++; 223 } 224 225 switch (type->base_type) { 226 case GLSL_TYPE_FLOAT: 227 data.f[i] = found->constant->value.f[rhs_channel]; 228 break; 229 case GLSL_TYPE_DOUBLE: 230 data.d[i] = found->constant->value.d[rhs_channel]; 231 break; 232 case GLSL_TYPE_INT: 233 data.i[i] = found->constant->value.i[rhs_channel]; 234 break; 235 case GLSL_TYPE_UINT: 236 data.u[i] = found->constant->value.u[rhs_channel]; 237 break; 238 case GLSL_TYPE_BOOL: 239 data.b[i] = found->constant->value.b[rhs_channel]; 240 break; 241 case GLSL_TYPE_UINT64: 242 data.u64[i] = found->constant->value.u64[rhs_channel]; 243 break; 244 case GLSL_TYPE_INT64: 245 data.i64[i] = found->constant->value.i64[rhs_channel]; 246 break; 247 default: 248 assert(!"not reached"); 249 break; 250 } 251 } 252 253 *rvalue = new(ralloc_parent(deref)) ir_constant(type, &data); 254 this->progress = true; 255 } 256 257 void 258 ir_constant_propagation_visitor::handle_rvalue(ir_rvalue **rvalue) 259 { 260 constant_propagation(rvalue); 261 constant_folding(rvalue); 262 } 263 264 ir_visitor_status 265 ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir) 266 { 267 /* Treat entry into a function signature as a completely separate 268 * block. Any instructions at global scope will be shuffled into 269 * main() at link time, so they're irrelevant to us. 270 */ 271 exec_list *orig_acp = this->acp; 272 hash_table *orig_kills = this->kills; 273 bool orig_killed_all = this->killed_all; 274 275 this->acp = new(mem_ctx) exec_list; 276 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 277 _mesa_key_pointer_equal); 278 this->killed_all = false; 279 280 visit_list_elements(this, &ir->body); 281 282 this->kills = orig_kills; 283 this->acp = orig_acp; 284 this->killed_all = orig_killed_all; 285 286 return visit_continue_with_parent; 287 } 288 289 ir_visitor_status 290 ir_constant_propagation_visitor::visit_leave(ir_assignment *ir) 291 { 292 constant_folding(&ir->rhs); 293 294 if (this->in_assignee) 295 return visit_continue; 296 297 unsigned kill_mask = ir->write_mask; 298 if (ir->lhs->as_dereference_array()) { 299 /* The LHS of the assignment uses an array indexing operator (e.g. v[i] 300 * = ...;). Since we only try to constant propagate vectors and 301 * scalars, this means that either (a) array indexing is being used to 302 * select a vector component, or (b) the variable in question is neither 303 * a scalar or a vector, so we don't care about it. In the former case, 304 * we want to kill the whole vector, since in general we can't predict 305 * which vector component will be selected by array indexing. In the 306 * latter case, it doesn't matter what we do, so go ahead and kill the 307 * whole variable anyway. 308 * 309 * Note that if the array index is constant (e.g. v[2] = ...;), we could 310 * in principle be smarter, but we don't need to, because a future 311 * optimization pass will convert it to a simple assignment with the 312 * correct mask. 313 */ 314 kill_mask = ~0; 315 } 316 kill(ir->lhs->variable_referenced(), kill_mask); 317 318 add_constant(ir); 319 320 return visit_continue; 321 } 322 323 ir_visitor_status 324 ir_constant_propagation_visitor::visit_enter(ir_function *ir) 325 { 326 (void) ir; 327 return visit_continue; 328 } 329 330 ir_visitor_status 331 ir_constant_propagation_visitor::visit_enter(ir_call *ir) 332 { 333 /* Do constant propagation on call parameters, but skip any out params */ 334 foreach_two_lists(formal_node, &ir->callee->parameters, 335 actual_node, &ir->actual_parameters) { 336 ir_variable *sig_param = (ir_variable *) formal_node; 337 ir_rvalue *param = (ir_rvalue *) actual_node; 338 if (sig_param->data.mode != ir_var_function_out 339 && sig_param->data.mode != ir_var_function_inout) { 340 ir_rvalue *new_param = param; 341 handle_rvalue(&new_param); 342 if (new_param != param) 343 param->replace_with(new_param); 344 else 345 param->accept(this); 346 } 347 } 348 349 /* Since we're unlinked, we don't (necssarily) know the side effects of 350 * this call. So kill all copies. 351 */ 352 acp->make_empty(); 353 this->killed_all = true; 354 355 return visit_continue_with_parent; 356 } 357 358 void 359 ir_constant_propagation_visitor::handle_if_block(exec_list *instructions) 360 { 361 exec_list *orig_acp = this->acp; 362 hash_table *orig_kills = this->kills; 363 bool orig_killed_all = this->killed_all; 364 365 this->acp = new(mem_ctx) exec_list; 366 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 367 _mesa_key_pointer_equal); 368 this->killed_all = false; 369 370 /* Populate the initial acp with a constant of the original */ 371 foreach_in_list(acp_entry, a, orig_acp) { 372 this->acp->push_tail(new(this->lin_ctx) acp_entry(a)); 373 } 374 375 visit_list_elements(this, instructions); 376 377 if (this->killed_all) { 378 orig_acp->make_empty(); 379 } 380 381 hash_table *new_kills = this->kills; 382 this->kills = orig_kills; 383 this->acp = orig_acp; 384 this->killed_all = this->killed_all || orig_killed_all; 385 386 hash_entry *htk; 387 hash_table_foreach(new_kills, htk) { 388 kill_entry *k = (kill_entry *) htk->data; 389 kill(k->var, k->write_mask); 390 } 391 } 392 393 ir_visitor_status 394 ir_constant_propagation_visitor::visit_enter(ir_if *ir) 395 { 396 ir->condition->accept(this); 397 handle_rvalue(&ir->condition); 398 399 handle_if_block(&ir->then_instructions); 400 handle_if_block(&ir->else_instructions); 401 402 /* handle_if_block() already descended into the children. */ 403 return visit_continue_with_parent; 404 } 405 406 ir_visitor_status 407 ir_constant_propagation_visitor::visit_enter(ir_loop *ir) 408 { 409 exec_list *orig_acp = this->acp; 410 hash_table *orig_kills = this->kills; 411 bool orig_killed_all = this->killed_all; 412 413 /* FINISHME: For now, the initial acp for loops is totally empty. 414 * We could go through once, then go through again with the acp 415 * cloned minus the killed entries after the first run through. 416 */ 417 this->acp = new(mem_ctx) exec_list; 418 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 419 _mesa_key_pointer_equal); 420 this->killed_all = false; 421 422 visit_list_elements(this, &ir->body_instructions); 423 424 if (this->killed_all) { 425 orig_acp->make_empty(); 426 } 427 428 hash_table *new_kills = this->kills; 429 this->kills = orig_kills; 430 this->acp = orig_acp; 431 this->killed_all = this->killed_all || orig_killed_all; 432 433 hash_entry *htk; 434 hash_table_foreach(new_kills, htk) { 435 kill_entry *k = (kill_entry *) htk->data; 436 kill(k->var, k->write_mask); 437 } 438 439 /* already descended into the children. */ 440 return visit_continue_with_parent; 441 } 442 443 void 444 ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask) 445 { 446 assert(var != NULL); 447 448 /* We don't track non-vectors. */ 449 if (!var->type->is_vector() && !var->type->is_scalar()) 450 return; 451 452 /* Remove any entries currently in the ACP for this kill. */ 453 foreach_in_list_safe(acp_entry, entry, this->acp) { 454 if (entry->var == var) { 455 entry->write_mask &= ~write_mask; 456 if (entry->write_mask == 0) 457 entry->remove(); 458 } 459 } 460 461 /* Add this writemask of the variable to the hash table of killed 462 * variables in this block. 463 */ 464 hash_entry *kill_hash_entry = _mesa_hash_table_search(this->kills, var); 465 if (kill_hash_entry) { 466 kill_entry *entry = (kill_entry *) kill_hash_entry->data; 467 entry->write_mask |= write_mask; 468 return; 469 } 470 /* Not already in the hash table. Make new entry. */ 471 _mesa_hash_table_insert(this->kills, var, 472 new(this->lin_ctx) kill_entry(var, write_mask)); 473 } 474 475 /** 476 * Adds an entry to the available constant list if it's a plain assignment 477 * of a variable to a variable. 478 */ 479 void 480 ir_constant_propagation_visitor::add_constant(ir_assignment *ir) 481 { 482 acp_entry *entry; 483 484 if (ir->condition) 485 return; 486 487 if (!ir->write_mask) 488 return; 489 490 ir_dereference_variable *deref = ir->lhs->as_dereference_variable(); 491 ir_constant *constant = ir->rhs->as_constant(); 492 493 if (!deref || !constant) 494 return; 495 496 /* Only do constant propagation on vectors. Constant matrices, 497 * arrays, or structures would require more work elsewhere. 498 */ 499 if (!deref->var->type->is_vector() && !deref->var->type->is_scalar()) 500 return; 501 502 /* We can't do copy propagation on buffer variables, since the underlying 503 * memory storage is shared across multiple threads we can't be sure that 504 * the variable value isn't modified between this assignment and the next 505 * instruction where its value is read. 506 */ 507 if (deref->var->data.mode == ir_var_shader_storage || 508 deref->var->data.mode == ir_var_shader_shared) 509 return; 510 511 entry = new(this->lin_ctx) acp_entry(deref->var, ir->write_mask, constant); 512 this->acp->push_tail(entry); 513 } 514 515 } /* unnamed namespace */ 516 517 /** 518 * Does a constant propagation pass on the code present in the instruction stream. 519 */ 520 bool 521 do_constant_propagation(exec_list *instructions) 522 { 523 ir_constant_propagation_visitor v; 524 525 visit_list_elements(&v, instructions); 526 527 return v.progress; 528 } 529