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 /** 25 * \file opt_copy_propagation.cpp 26 * 27 * Moves usage of recently-copied variables to the previous copy of 28 * the variable. 29 * 30 * This should reduce the number of MOV instructions in the generated 31 * programs unless copy propagation is also done on the LIR, and may 32 * help anyway by triggering other optimizations that live in the HIR. 33 */ 34 35 #include "ir.h" 36 #include "ir_visitor.h" 37 #include "ir_basic_block.h" 38 #include "ir_optimization.h" 39 #include "glsl_types.h" 40 41 class acp_entry : public exec_node 42 { 43 public: 44 acp_entry(ir_variable *lhs, ir_variable *rhs) 45 { 46 assert(lhs); 47 assert(rhs); 48 this->lhs = lhs; 49 this->rhs = rhs; 50 } 51 52 ir_variable *lhs; 53 ir_variable *rhs; 54 }; 55 56 57 class kill_entry : public exec_node 58 { 59 public: 60 kill_entry(ir_variable *var) 61 { 62 assert(var); 63 this->var = var; 64 } 65 66 ir_variable *var; 67 }; 68 69 class ir_copy_propagation_visitor : public ir_hierarchical_visitor { 70 public: 71 ir_copy_propagation_visitor() 72 { 73 progress = false; 74 mem_ctx = hieralloc_new(0); 75 this->acp = new(mem_ctx) exec_list; 76 this->kills = new(mem_ctx) exec_list; 77 } 78 ~ir_copy_propagation_visitor() 79 { 80 hieralloc_free(mem_ctx); 81 } 82 83 virtual ir_visitor_status visit(class ir_dereference_variable *); 84 virtual ir_visitor_status visit_enter(class ir_loop *); 85 virtual ir_visitor_status visit_enter(class ir_function_signature *); 86 virtual ir_visitor_status visit_enter(class ir_function *); 87 virtual ir_visitor_status visit_leave(class ir_assignment *); 88 virtual ir_visitor_status visit_enter(class ir_call *); 89 virtual ir_visitor_status visit_enter(class ir_if *); 90 91 void add_copy(ir_assignment *ir); 92 void kill(ir_variable *ir); 93 void handle_if_block(exec_list *instructions); 94 95 /** List of acp_entry: The available copies to propagate */ 96 exec_list *acp; 97 /** 98 * List of kill_entry: The variables whose values were killed in this 99 * block. 100 */ 101 exec_list *kills; 102 103 bool progress; 104 105 bool killed_all; 106 107 void *mem_ctx; 108 }; 109 110 ir_visitor_status 111 ir_copy_propagation_visitor::visit_enter(ir_function_signature *ir) 112 { 113 /* Treat entry into a function signature as a completely separate 114 * block. Any instructions at global scope will be shuffled into 115 * main() at link time, so they're irrelevant to us. 116 */ 117 exec_list *orig_acp = this->acp; 118 exec_list *orig_kills = this->kills; 119 bool orig_killed_all = this->killed_all; 120 121 this->acp = new(mem_ctx) exec_list; 122 this->kills = new(mem_ctx) exec_list; 123 this->killed_all = false; 124 125 visit_list_elements(this, &ir->body); 126 127 this->kills = orig_kills; 128 this->acp = orig_acp; 129 this->killed_all = orig_killed_all; 130 131 return visit_continue_with_parent; 132 } 133 134 ir_visitor_status 135 ir_copy_propagation_visitor::visit_leave(ir_assignment *ir) 136 { 137 kill(ir->lhs->variable_referenced()); 138 139 add_copy(ir); 140 141 return visit_continue; 142 } 143 144 ir_visitor_status 145 ir_copy_propagation_visitor::visit_enter(ir_function *ir) 146 { 147 (void) ir; 148 return visit_continue; 149 } 150 151 /** 152 * Replaces dereferences of ACP RHS variables with ACP LHS variables. 153 * 154 * This is where the actual copy propagation occurs. Note that the 155 * rewriting of ir_dereference means that the ir_dereference instance 156 * must not be shared by multiple IR operations! 157 */ 158 ir_visitor_status 159 ir_copy_propagation_visitor::visit(ir_dereference_variable *ir) 160 { 161 if (this->in_assignee) 162 return visit_continue; 163 164 ir_variable *var = ir->var; 165 166 foreach_iter(exec_list_iterator, iter, *this->acp) { 167 acp_entry *entry = (acp_entry *)iter.get(); 168 169 if (var == entry->lhs) { 170 ir->var = entry->rhs; 171 this->progress = true; 172 break; 173 } 174 } 175 176 return visit_continue; 177 } 178 179 180 ir_visitor_status 181 ir_copy_propagation_visitor::visit_enter(ir_call *ir) 182 { 183 /* Do copy propagation on call parameters, but skip any out params */ 184 exec_list_iterator sig_param_iter = ir->get_callee()->parameters.iterator(); 185 foreach_iter(exec_list_iterator, iter, ir->actual_parameters) { 186 ir_variable *sig_param = (ir_variable *)sig_param_iter.get(); 187 ir_instruction *ir = (ir_instruction *)iter.get(); 188 if (sig_param->mode != ir_var_out && sig_param->mode != ir_var_inout) { 189 ir->accept(this); 190 } 191 sig_param_iter.next(); 192 } 193 194 /* Since we're unlinked, we don't (necssarily) know the side effects of 195 * this call. So kill all copies. 196 */ 197 acp->make_empty(); 198 this->killed_all = true; 199 200 return visit_continue_with_parent; 201 } 202 203 void 204 ir_copy_propagation_visitor::handle_if_block(exec_list *instructions) 205 { 206 exec_list *orig_acp = this->acp; 207 exec_list *orig_kills = this->kills; 208 bool orig_killed_all = this->killed_all; 209 210 this->acp = new(mem_ctx) exec_list; 211 this->kills = new(mem_ctx) exec_list; 212 this->killed_all = false; 213 214 /* Populate the initial acp with a copy of the original */ 215 foreach_iter(exec_list_iterator, iter, *orig_acp) { 216 acp_entry *a = (acp_entry *)iter.get(); 217 this->acp->push_tail(new(this->mem_ctx) acp_entry(a->lhs, a->rhs)); 218 } 219 220 visit_list_elements(this, instructions); 221 222 if (this->killed_all) { 223 orig_acp->make_empty(); 224 } 225 226 exec_list *new_kills = this->kills; 227 this->kills = orig_kills; 228 this->acp = orig_acp; 229 this->killed_all = this->killed_all || orig_killed_all; 230 231 foreach_iter(exec_list_iterator, iter, *new_kills) { 232 kill_entry *k = (kill_entry *)iter.get(); 233 kill(k->var); 234 } 235 } 236 237 ir_visitor_status 238 ir_copy_propagation_visitor::visit_enter(ir_if *ir) 239 { 240 ir->condition->accept(this); 241 242 handle_if_block(&ir->then_instructions); 243 handle_if_block(&ir->else_instructions); 244 245 /* handle_if_block() already descended into the children. */ 246 return visit_continue_with_parent; 247 } 248 249 ir_visitor_status 250 ir_copy_propagation_visitor::visit_enter(ir_loop *ir) 251 { 252 exec_list *orig_acp = this->acp; 253 exec_list *orig_kills = this->kills; 254 bool orig_killed_all = this->killed_all; 255 256 /* FINISHME: For now, the initial acp for loops is totally empty. 257 * We could go through once, then go through again with the acp 258 * cloned minus the killed entries after the first run through. 259 */ 260 this->acp = new(mem_ctx) exec_list; 261 this->kills = new(mem_ctx) exec_list; 262 this->killed_all = false; 263 264 visit_list_elements(this, &ir->body_instructions); 265 266 if (this->killed_all) { 267 orig_acp->make_empty(); 268 } 269 270 exec_list *new_kills = this->kills; 271 this->kills = orig_kills; 272 this->acp = orig_acp; 273 this->killed_all = this->killed_all || orig_killed_all; 274 275 foreach_iter(exec_list_iterator, iter, *new_kills) { 276 kill_entry *k = (kill_entry *)iter.get(); 277 kill(k->var); 278 } 279 280 /* already descended into the children. */ 281 return visit_continue_with_parent; 282 } 283 284 void 285 ir_copy_propagation_visitor::kill(ir_variable *var) 286 { 287 assert(var != NULL); 288 289 /* Remove any entries currently in the ACP for this kill. */ 290 foreach_iter(exec_list_iterator, iter, *acp) { 291 acp_entry *entry = (acp_entry *)iter.get(); 292 293 if (entry->lhs == var || entry->rhs == var) { 294 entry->remove(); 295 } 296 } 297 298 /* Add the LHS variable to the list of killed variables in this block. 299 */ 300 this->kills->push_tail(new(this->mem_ctx) kill_entry(var)); 301 } 302 303 /** 304 * Adds an entry to the available copy list if it's a plain assignment 305 * of a variable to a variable. 306 */ 307 void 308 ir_copy_propagation_visitor::add_copy(ir_assignment *ir) 309 { 310 acp_entry *entry; 311 312 if (ir->condition) { 313 ir_constant *condition = ir->condition->as_constant(); 314 if (!condition || !condition->value.b[0]) 315 return; 316 } 317 318 ir_variable *lhs_var = ir->whole_variable_written(); 319 ir_variable *rhs_var = ir->rhs->whole_variable_referenced(); 320 321 if ((lhs_var != NULL) && (rhs_var != NULL)) { 322 if (lhs_var == rhs_var) { 323 /* This is a dumb assignment, but we've conveniently noticed 324 * it here. Removing it now would mess up the loop iteration 325 * calling us. Just flag it to not execute, and someone else 326 * will clean up the mess. 327 */ 328 ir->condition = new(hieralloc_parent(ir)) ir_constant(false); 329 this->progress = true; 330 } else { 331 entry = new(this->mem_ctx) acp_entry(lhs_var, rhs_var); 332 this->acp->push_tail(entry); 333 } 334 } 335 } 336 337 /** 338 * Does a copy propagation pass on the code present in the instruction stream. 339 */ 340 bool 341 do_copy_propagation(exec_list *instructions) 342 { 343 ir_copy_propagation_visitor v; 344 345 visit_list_elements(&v, instructions); 346 347 return v.progress; 348 } 349
