opt_constant_propagation.cpp revision 29a2e9133e415de8b010df5b80db758aaf1007a6
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 "glsl_types.h" 43 44using std::memset; 45 46class acp_entry : public exec_node 47{ 48public: 49 acp_entry(ir_variable *var, unsigned write_mask, ir_constant *constant) 50 { 51 assert(var); 52 assert(constant); 53 this->var = var; 54 this->write_mask = write_mask; 55 this->constant = constant; 56 } 57 58 ir_variable *var; 59 ir_constant *constant; 60 unsigned write_mask; 61}; 62 63 64class kill_entry : public exec_node 65{ 66public: 67 kill_entry(ir_variable *var, unsigned write_mask) 68 { 69 assert(var); 70 this->var = var; 71 this->write_mask = write_mask; 72 } 73 74 ir_variable *var; 75 unsigned write_mask; 76}; 77 78class ir_constant_propagation_visitor : public ir_rvalue_visitor { 79public: 80 ir_constant_propagation_visitor() 81 { 82 progress = false; 83 mem_ctx = ralloc_context(0); 84 this->acp = new(mem_ctx) exec_list; 85 this->kills = new(mem_ctx) exec_list; 86 } 87 ~ir_constant_propagation_visitor() 88 { 89 ralloc_free(mem_ctx); 90 } 91 92 virtual ir_visitor_status visit_enter(class ir_loop *); 93 virtual ir_visitor_status visit_enter(class ir_function_signature *); 94 virtual ir_visitor_status visit_enter(class ir_function *); 95 virtual ir_visitor_status visit_leave(class ir_assignment *); 96 virtual ir_visitor_status visit_enter(class ir_call *); 97 virtual ir_visitor_status visit_enter(class ir_if *); 98 99 void add_constant(ir_assignment *ir); 100 void kill(ir_variable *ir, unsigned write_mask); 101 void handle_if_block(exec_list *instructions); 102 void handle_rvalue(ir_rvalue **rvalue); 103 104 /** List of acp_entry: The available constants to propagate */ 105 exec_list *acp; 106 107 /** 108 * List of kill_entry: The masks of variables whose values were 109 * killed in this block. 110 */ 111 exec_list *kills; 112 113 bool progress; 114 115 bool killed_all; 116 117 void *mem_ctx; 118}; 119 120 121void 122ir_constant_propagation_visitor::handle_rvalue(ir_rvalue **rvalue) 123{ 124 if (this->in_assignee || !*rvalue) 125 return; 126 127 const glsl_type *type = (*rvalue)->type; 128 if (!type->is_scalar() && !type->is_vector()) 129 return; 130 131 ir_swizzle *swiz = NULL; 132 ir_dereference_variable *deref = (*rvalue)->as_dereference_variable(); 133 if (!deref) { 134 swiz = (*rvalue)->as_swizzle(); 135 if (!swiz) 136 return; 137 138 deref = swiz->val->as_dereference_variable(); 139 if (!deref) 140 return; 141 } 142 143 ir_constant_data data; 144 memset(&data, 0, sizeof(data)); 145 146 for (unsigned int i = 0; i < type->components(); i++) { 147 int channel; 148 acp_entry *found = NULL; 149 150 if (swiz) { 151 switch (i) { 152 case 0: channel = swiz->mask.x; break; 153 case 1: channel = swiz->mask.y; break; 154 case 2: channel = swiz->mask.z; break; 155 case 3: channel = swiz->mask.w; break; 156 default: assert(!"shouldn't be reached"); channel = 0; break; 157 } 158 } else { 159 channel = i; 160 } 161 162 foreach_iter(exec_list_iterator, iter, *this->acp) { 163 acp_entry *entry = (acp_entry *)iter.get(); 164 if (entry->var == deref->var && entry->write_mask & (1 << channel)) { 165 found = entry; 166 break; 167 } 168 } 169 170 if (!found) 171 return; 172 173 int rhs_channel = 0; 174 for (int j = 0; j < 4; j++) { 175 if (j == channel) 176 break; 177 if (found->write_mask & (1 << j)) 178 rhs_channel++; 179 } 180 181 switch (type->base_type) { 182 case GLSL_TYPE_FLOAT: 183 data.f[i] = found->constant->value.f[rhs_channel]; 184 break; 185 case GLSL_TYPE_INT: 186 data.i[i] = found->constant->value.i[rhs_channel]; 187 break; 188 case GLSL_TYPE_UINT: 189 data.u[i] = found->constant->value.u[rhs_channel]; 190 break; 191 case GLSL_TYPE_BOOL: 192 data.b[i] = found->constant->value.b[rhs_channel]; 193 break; 194 default: 195 assert(!"not reached"); 196 break; 197 } 198 } 199 200 *rvalue = new(ralloc_parent(deref)) ir_constant(type, &data); 201 this->progress = true; 202} 203 204ir_visitor_status 205ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir) 206{ 207 /* Treat entry into a function signature as a completely separate 208 * block. Any instructions at global scope will be shuffled into 209 * main() at link time, so they're irrelevant to us. 210 */ 211 exec_list *orig_acp = this->acp; 212 exec_list *orig_kills = this->kills; 213 bool orig_killed_all = this->killed_all; 214 215 this->acp = new(mem_ctx) exec_list; 216 this->kills = new(mem_ctx) exec_list; 217 this->killed_all = false; 218 219 visit_list_elements(this, &ir->body); 220 221 this->kills = orig_kills; 222 this->acp = orig_acp; 223 this->killed_all = orig_killed_all; 224 225 return visit_continue_with_parent; 226} 227 228ir_visitor_status 229ir_constant_propagation_visitor::visit_leave(ir_assignment *ir) 230{ 231 if (this->in_assignee) 232 return visit_continue; 233 234 kill(ir->lhs->variable_referenced(), ir->write_mask); 235 236 add_constant(ir); 237 238 return visit_continue; 239} 240 241ir_visitor_status 242ir_constant_propagation_visitor::visit_enter(ir_function *ir) 243{ 244 (void) ir; 245 return visit_continue; 246} 247 248ir_visitor_status 249ir_constant_propagation_visitor::visit_enter(ir_call *ir) 250{ 251 /* Do constant propagation on call parameters, but skip any out params */ 252 exec_list_iterator sig_param_iter = ir->get_callee()->parameters.iterator(); 253 foreach_iter(exec_list_iterator, iter, ir->actual_parameters) { 254 ir_variable *sig_param = (ir_variable *)sig_param_iter.get(); 255 ir_rvalue *param = (ir_rvalue *)iter.get(); 256 if (sig_param->mode != ir_var_out && sig_param->mode != ir_var_inout) { 257 ir_rvalue *new_param = param; 258 handle_rvalue(&new_param); 259 if (new_param != param) 260 param->replace_with(new_param); 261 else 262 param->accept(this); 263 } 264 sig_param_iter.next(); 265 } 266 267 /* Since we're unlinked, we don't (necssarily) know the side effects of 268 * this call. So kill all copies. 269 */ 270 acp->make_empty(); 271 this->killed_all = true; 272 273 return visit_continue_with_parent; 274} 275 276void 277ir_constant_propagation_visitor::handle_if_block(exec_list *instructions) 278{ 279 exec_list *orig_acp = this->acp; 280 exec_list *orig_kills = this->kills; 281 bool orig_killed_all = this->killed_all; 282 283 this->acp = new(mem_ctx) exec_list; 284 this->kills = new(mem_ctx) exec_list; 285 this->killed_all = false; 286 287 /* Populate the initial acp with a constant of the original */ 288 foreach_iter(exec_list_iterator, iter, *orig_acp) { 289 acp_entry *a = (acp_entry *)iter.get(); 290 this->acp->push_tail(new(this->mem_ctx) acp_entry(a->var, a->write_mask, 291 a->constant)); 292 } 293 294 visit_list_elements(this, instructions); 295 296 if (this->killed_all) { 297 orig_acp->make_empty(); 298 } 299 300 exec_list *new_kills = this->kills; 301 this->kills = orig_kills; 302 this->acp = orig_acp; 303 this->killed_all = this->killed_all || orig_killed_all; 304 305 foreach_iter(exec_list_iterator, iter, *new_kills) { 306 kill_entry *k = (kill_entry *)iter.get(); 307 kill(k->var, k->write_mask); 308 } 309} 310 311ir_visitor_status 312ir_constant_propagation_visitor::visit_enter(ir_if *ir) 313{ 314 ir->condition->accept(this); 315 handle_rvalue(&ir->condition); 316 317 handle_if_block(&ir->then_instructions); 318 handle_if_block(&ir->else_instructions); 319 320 /* handle_if_block() already descended into the children. */ 321 return visit_continue_with_parent; 322} 323 324ir_visitor_status 325ir_constant_propagation_visitor::visit_enter(ir_loop *ir) 326{ 327 exec_list *orig_acp = this->acp; 328 exec_list *orig_kills = this->kills; 329 bool orig_killed_all = this->killed_all; 330 331 /* FINISHME: For now, the initial acp for loops is totally empty. 332 * We could go through once, then go through again with the acp 333 * cloned minus the killed entries after the first run through. 334 */ 335 this->acp = new(mem_ctx) exec_list; 336 this->kills = new(mem_ctx) exec_list; 337 this->killed_all = false; 338 339 visit_list_elements(this, &ir->body_instructions); 340 341 if (this->killed_all) { 342 orig_acp->make_empty(); 343 } 344 345 exec_list *new_kills = this->kills; 346 this->kills = orig_kills; 347 this->acp = orig_acp; 348 this->killed_all = this->killed_all || orig_killed_all; 349 350 foreach_iter(exec_list_iterator, iter, *new_kills) { 351 kill_entry *k = (kill_entry *)iter.get(); 352 kill(k->var, k->write_mask); 353 } 354 355 /* already descended into the children. */ 356 return visit_continue_with_parent; 357} 358 359void 360ir_constant_propagation_visitor::kill(ir_variable *var, unsigned write_mask) 361{ 362 assert(var != NULL); 363 364 /* We don't track non-vectors. */ 365 if (!var->type->is_vector() && !var->type->is_scalar()) 366 return; 367 368 /* Remove any entries currently in the ACP for this kill. */ 369 foreach_iter(exec_list_iterator, iter, *this->acp) { 370 acp_entry *entry = (acp_entry *)iter.get(); 371 372 if (entry->var == var) { 373 entry->write_mask &= ~write_mask; 374 if (entry->write_mask == 0) 375 entry->remove(); 376 } 377 } 378 379 /* Add this writemask of the variable to the list of killed 380 * variables in this block. 381 */ 382 foreach_iter(exec_list_iterator, iter, *this->kills) { 383 kill_entry *entry = (kill_entry *)iter.get(); 384 385 if (entry->var == var) { 386 entry->write_mask |= write_mask; 387 return; 388 } 389 } 390 /* Not already in the list. Make new entry. */ 391 this->kills->push_tail(new(this->mem_ctx) kill_entry(var, write_mask)); 392} 393 394/** 395 * Adds an entry to the available constant list if it's a plain assignment 396 * of a variable to a variable. 397 */ 398void 399ir_constant_propagation_visitor::add_constant(ir_assignment *ir) 400{ 401 acp_entry *entry; 402 403 if (ir->condition) 404 return; 405 406 if (!ir->write_mask) 407 return; 408 409 ir_dereference_variable *deref = ir->lhs->as_dereference_variable(); 410 ir_constant *constant = ir->rhs->as_constant(); 411 412 if (!deref || !constant) 413 return; 414 415 /* Only do constant propagation on vectors. Constant matrices, 416 * arrays, or structures would require more work elsewhere. 417 */ 418 if (!deref->var->type->is_vector() && !deref->var->type->is_scalar()) 419 return; 420 421 entry = new(this->mem_ctx) acp_entry(deref->var, ir->write_mask, constant); 422 this->acp->push_tail(entry); 423} 424 425/** 426 * Does a constant propagation pass on the code present in the instruction stream. 427 */ 428bool 429do_constant_propagation(exec_list *instructions) 430{ 431 ir_constant_propagation_visitor v; 432 433 visit_list_elements(&v, instructions); 434 435 return v.progress; 436} 437