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 = var_ref->constant_expression_value(); 158 if (constant) { 159 *rvalue = constant; 160 this->progress = true; 161 } 162 } 163 } 164 165 void 166 ir_constant_propagation_visitor::constant_propagation(ir_rvalue **rvalue) { 167 168 if (this->in_assignee || !*rvalue) 169 return; 170 171 const glsl_type *type = (*rvalue)->type; 172 if (!type->is_scalar() && !type->is_vector()) 173 return; 174 175 ir_swizzle *swiz = NULL; 176 ir_dereference_variable *deref = (*rvalue)->as_dereference_variable(); 177 if (!deref) { 178 swiz = (*rvalue)->as_swizzle(); 179 if (!swiz) 180 return; 181 182 deref = swiz->val->as_dereference_variable(); 183 if (!deref) 184 return; 185 } 186 187 ir_constant_data data; 188 memset(&data, 0, sizeof(data)); 189 190 for (unsigned int i = 0; i < type->components(); i++) { 191 int channel; 192 acp_entry *found = NULL; 193 194 if (swiz) { 195 switch (i) { 196 case 0: channel = swiz->mask.x; break; 197 case 1: channel = swiz->mask.y; break; 198 case 2: channel = swiz->mask.z; break; 199 case 3: channel = swiz->mask.w; break; 200 default: assert(!"shouldn't be reached"); channel = 0; break; 201 } 202 } else { 203 channel = i; 204 } 205 206 foreach_in_list(acp_entry, entry, this->acp) { 207 if (entry->var == deref->var && entry->write_mask & (1 << channel)) { 208 found = entry; 209 break; 210 } 211 } 212 213 if (!found) 214 return; 215 216 int rhs_channel = 0; 217 for (int j = 0; j < 4; j++) { 218 if (j == channel) 219 break; 220 if (found->initial_values & (1 << j)) 221 rhs_channel++; 222 } 223 224 switch (type->base_type) { 225 case GLSL_TYPE_FLOAT: 226 data.f[i] = found->constant->value.f[rhs_channel]; 227 break; 228 case GLSL_TYPE_DOUBLE: 229 data.d[i] = found->constant->value.d[rhs_channel]; 230 break; 231 case GLSL_TYPE_INT: 232 data.i[i] = found->constant->value.i[rhs_channel]; 233 break; 234 case GLSL_TYPE_UINT: 235 data.u[i] = found->constant->value.u[rhs_channel]; 236 break; 237 case GLSL_TYPE_BOOL: 238 data.b[i] = found->constant->value.b[rhs_channel]; 239 break; 240 default: 241 assert(!"not reached"); 242 break; 243 } 244 } 245 246 *rvalue = new(ralloc_parent(deref)) ir_constant(type, &data); 247 this->progress = true; 248 } 249 250 void 251 ir_constant_propagation_visitor::handle_rvalue(ir_rvalue **rvalue) 252 { 253 constant_propagation(rvalue); 254 constant_folding(rvalue); 255 } 256 257 ir_visitor_status 258 ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir) 259 { 260 /* Treat entry into a function signature as a completely separate 261 * block. Any instructions at global scope will be shuffled into 262 * main() at link time, so they're irrelevant to us. 263 */ 264 exec_list *orig_acp = this->acp; 265 hash_table *orig_kills = this->kills; 266 bool orig_killed_all = this->killed_all; 267 268 this->acp = new(mem_ctx) exec_list; 269 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 270 _mesa_key_pointer_equal); 271 this->killed_all = false; 272 273 visit_list_elements(this, &ir->body); 274 275 this->kills = orig_kills; 276 this->acp = orig_acp; 277 this->killed_all = orig_killed_all; 278 279 return visit_continue_with_parent; 280 } 281 282 ir_visitor_status 283 ir_constant_propagation_visitor::visit_leave(ir_assignment *ir) 284 { 285 constant_folding(&ir->rhs); 286 287 if (this->in_assignee) 288 return visit_continue; 289 290 unsigned kill_mask = ir->write_mask; 291 if (ir->lhs->as_dereference_array()) { 292 /* The LHS of the assignment uses an array indexing operator (e.g. v[i] 293 * = ...;). Since we only try to constant propagate vectors and 294 * scalars, this means that either (a) array indexing is being used to 295 * select a vector component, or (b) the variable in question is neither 296 * a scalar or a vector, so we don't care about it. In the former case, 297 * we want to kill the whole vector, since in general we can't predict 298 * which vector component will be selected by array indexing. In the 299 * latter case, it doesn't matter what we do, so go ahead and kill the 300 * whole variable anyway. 301 * 302 * Note that if the array index is constant (e.g. v[2] = ...;), we could 303 * in principle be smarter, but we don't need to, because a future 304 * optimization pass will convert it to a simple assignment with the 305 * correct mask. 306 */ 307 kill_mask = ~0; 308 } 309 kill(ir->lhs->variable_referenced(), kill_mask); 310 311 add_constant(ir); 312 313 return visit_continue; 314 } 315 316 ir_visitor_status 317 ir_constant_propagation_visitor::visit_enter(ir_function *ir) 318 { 319 (void) ir; 320 return visit_continue; 321 } 322 323 ir_visitor_status 324 ir_constant_propagation_visitor::visit_enter(ir_call *ir) 325 { 326 /* Do constant propagation on call parameters, but skip any out params */ 327 foreach_two_lists(formal_node, &ir->callee->parameters, 328 actual_node, &ir->actual_parameters) { 329 ir_variable *sig_param = (ir_variable *) formal_node; 330 ir_rvalue *param = (ir_rvalue *) actual_node; 331 if (sig_param->data.mode != ir_var_function_out 332 && sig_param->data.mode != ir_var_function_inout) { 333 ir_rvalue *new_param = param; 334 handle_rvalue(&new_param); 335 if (new_param != param) 336 param->replace_with(new_param); 337 else 338 param->accept(this); 339 } 340 } 341 342 /* Since we're unlinked, we don't (necssarily) know the side effects of 343 * this call. So kill all copies. 344 */ 345 acp->make_empty(); 346 this->killed_all = true; 347 348 return visit_continue_with_parent; 349 } 350 351 void 352 ir_constant_propagation_visitor::handle_if_block(exec_list *instructions) 353 { 354 exec_list *orig_acp = this->acp; 355 hash_table *orig_kills = this->kills; 356 bool orig_killed_all = this->killed_all; 357 358 this->acp = new(mem_ctx) exec_list; 359 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 360 _mesa_key_pointer_equal); 361 this->killed_all = false; 362 363 /* Populate the initial acp with a constant of the original */ 364 foreach_in_list(acp_entry, a, orig_acp) { 365 this->acp->push_tail(new(this->lin_ctx) acp_entry(a)); 366 } 367 368 visit_list_elements(this, instructions); 369 370 if (this->killed_all) { 371 orig_acp->make_empty(); 372 } 373 374 hash_table *new_kills = this->kills; 375 this->kills = orig_kills; 376 this->acp = orig_acp; 377 this->killed_all = this->killed_all || orig_killed_all; 378 379 hash_entry *htk; 380 hash_table_foreach(new_kills, htk) { 381 kill_entry *k = (kill_entry *) htk->data; 382 kill(k->var, k->write_mask); 383 } 384 } 385 386 ir_visitor_status 387 ir_constant_propagation_visitor::visit_enter(ir_if *ir) 388 { 389 ir->condition->accept(this); 390 handle_rvalue(&ir->condition); 391 392 handle_if_block(&ir->then_instructions); 393 handle_if_block(&ir->else_instructions); 394 395 /* handle_if_block() already descended into the children. */ 396 return visit_continue_with_parent; 397 } 398 399 ir_visitor_status 400 ir_constant_propagation_visitor::visit_enter(ir_loop *ir) 401 { 402 exec_list *orig_acp = this->acp; 403 hash_table *orig_kills = this->kills; 404 bool orig_killed_all = this->killed_all; 405 406 /* FINISHME: For now, the initial acp for loops is totally empty. 407 * We could go through once, then go through again with the acp 408 * cloned minus the killed entries after the first run through. 409 */ 410 this->acp = new(mem_ctx) exec_list; 411 this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, 412 _mesa_key_pointer_equal); 413 this->killed_all = false; 414 415 visit_list_elements(this, &ir->body_instructions); 416 417 if (this->killed_all) { 418 orig_acp->make_empty(); 419 } 420 421 hash_table *new_kills = this->kills; 422 this->kills = orig_kills; 423 this->acp = orig_acp; 424 this->killed_all = this->killed_all || orig_killed_all; 425 426 hash_entry *htk; 427 hash_table_foreach(new_kills, htk) { 428 kill_entry *k = (kill_entry *) htk->data; 429 kill(k->var, k->write_mask); 430 } 431 432 /* already descended into the children. */ 433 return visit_continue_with_parent; 434 } 435 436 void 437 ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask) 438 { 439 assert(var != NULL); 440 441 /* We don't track non-vectors. */ 442 if (!var->type->is_vector() && !var->type->is_scalar()) 443 return; 444 445 /* Remove any entries currently in the ACP for this kill. */ 446 foreach_in_list_safe(acp_entry, entry, this->acp) { 447 if (entry->var == var) { 448 entry->write_mask &= ~write_mask; 449 if (entry->write_mask == 0) 450 entry->remove(); 451 } 452 } 453 454 /* Add this writemask of the variable to the hash table of killed 455 * variables in this block. 456 */ 457 hash_entry *kill_hash_entry = _mesa_hash_table_search(this->kills, var); 458 if (kill_hash_entry) { 459 kill_entry *entry = (kill_entry *) kill_hash_entry->data; 460 entry->write_mask |= write_mask; 461 return; 462 } 463 /* Not already in the hash table. Make new entry. */ 464 _mesa_hash_table_insert(this->kills, var, 465 new(this->lin_ctx) kill_entry(var, write_mask)); 466 } 467 468 /** 469 * Adds an entry to the available constant list if it's a plain assignment 470 * of a variable to a variable. 471 */ 472 void 473 ir_constant_propagation_visitor::add_constant(ir_assignment *ir) 474 { 475 acp_entry *entry; 476 477 if (ir->condition) 478 return; 479 480 if (!ir->write_mask) 481 return; 482 483 ir_dereference_variable *deref = ir->lhs->as_dereference_variable(); 484 ir_constant *constant = ir->rhs->as_constant(); 485 486 if (!deref || !constant) 487 return; 488 489 /* Only do constant propagation on vectors. Constant matrices, 490 * arrays, or structures would require more work elsewhere. 491 */ 492 if (!deref->var->type->is_vector() && !deref->var->type->is_scalar()) 493 return; 494 495 /* We can't do copy propagation on buffer variables, since the underlying 496 * memory storage is shared across multiple threads we can't be sure that 497 * the variable value isn't modified between this assignment and the next 498 * instruction where its value is read. 499 */ 500 if (deref->var->data.mode == ir_var_shader_storage || 501 deref->var->data.mode == ir_var_shader_shared) 502 return; 503 504 entry = new(this->lin_ctx) acp_entry(deref->var, ir->write_mask, constant); 505 this->acp->push_tail(entry); 506 } 507 508 } /* unnamed namespace */ 509 510 /** 511 * Does a constant propagation pass on the code present in the instruction stream. 512 */ 513 bool 514 do_constant_propagation(exec_list *instructions) 515 { 516 ir_constant_propagation_visitor v; 517 518 visit_list_elements(&v, instructions); 519 520 return v.progress; 521 } 522