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_tree_grafting.cpp 26 * 27 * Takes assignments to variables that are dereferenced only once and 28 * pastes the RHS expression into where the variable is dereferenced. 29 * 30 * In the process of various operations like function inlining and 31 * tertiary op handling, we'll end up with our expression trees having 32 * been chopped up into a series of assignments of short expressions 33 * to temps. Other passes like ir_algebraic.cpp would prefer to see 34 * the deepest expression trees they can to try to optimize them. 35 * 36 * This is a lot like copy propagaton. In comparison, copy 37 * propagation only acts on plain copies, not arbitrary expressions on 38 * the RHS. Generally, we wouldn't want to go pasting some 39 * complicated expression everywhere it got used, though, so we don't 40 * handle expressions in that pass. 41 * 42 * The hard part is making sure we don't move an expression across 43 * some other assignments that would change the value of the 44 * expression. So we split this into two passes: First, find the 45 * variables in our scope which are written to once and read once, and 46 * then go through basic blocks seeing if we find an opportunity to 47 * move those expressions safely. 48 */ 49 50 #include "ir.h" 51 #include "ir_visitor.h" 52 #include "ir_variable_refcount.h" 53 #include "ir_basic_block.h" 54 #include "ir_optimization.h" 55 #include "glsl_types.h" 56 57 static bool debug = false; 58 59 class ir_tree_grafting_visitor : public ir_hierarchical_visitor { 60 public: 61 ir_tree_grafting_visitor(ir_assignment *graft_assign, 62 ir_variable *graft_var) 63 { 64 this->progress = false; 65 this->graft_assign = graft_assign; 66 this->graft_var = graft_var; 67 } 68 69 virtual ir_visitor_status visit_leave(class ir_assignment *); 70 virtual ir_visitor_status visit_enter(class ir_call *); 71 virtual ir_visitor_status visit_enter(class ir_expression *); 72 virtual ir_visitor_status visit_enter(class ir_function *); 73 virtual ir_visitor_status visit_enter(class ir_function_signature *); 74 virtual ir_visitor_status visit_enter(class ir_if *); 75 virtual ir_visitor_status visit_enter(class ir_loop *); 76 virtual ir_visitor_status visit_enter(class ir_swizzle *); 77 virtual ir_visitor_status visit_enter(class ir_texture *); 78 79 bool do_graft(ir_rvalue **rvalue); 80 81 bool progress; 82 ir_variable *graft_var; 83 ir_assignment *graft_assign; 84 }; 85 86 struct find_deref_info { 87 ir_variable *var; 88 bool found; 89 }; 90 91 void 92 dereferences_variable_callback(ir_instruction *ir, void *data) 93 { 94 struct find_deref_info *info = (struct find_deref_info *)data; 95 ir_dereference_variable *deref = ir->as_dereference_variable(); 96 97 if (deref && deref->var == info->var) 98 info->found = true; 99 } 100 101 static bool 102 dereferences_variable(ir_instruction *ir, ir_variable *var) 103 { 104 struct find_deref_info info; 105 106 info.var = var; 107 info.found = false; 108 109 visit_tree(ir, dereferences_variable_callback, &info); 110 111 return info.found; 112 } 113 114 bool 115 ir_tree_grafting_visitor::do_graft(ir_rvalue **rvalue) 116 { 117 if (!*rvalue) 118 return false; 119 120 ir_dereference_variable *deref = (*rvalue)->as_dereference_variable(); 121 122 if (!deref || deref->var != this->graft_var) 123 return false; 124 125 if (debug) { 126 printf("GRAFTING:\n"); 127 this->graft_assign->print(); 128 printf("\n"); 129 printf("TO:\n"); 130 (*rvalue)->print(); 131 printf("\n"); 132 } 133 134 this->graft_assign->remove(); 135 *rvalue = this->graft_assign->rhs; 136 137 this->progress = true; 138 return true; 139 } 140 141 ir_visitor_status 142 ir_tree_grafting_visitor::visit_enter(ir_loop *ir) 143 { 144 (void)ir; 145 /* Do not traverse into the body of the loop since that is a 146 * different basic block. 147 */ 148 return visit_stop; 149 } 150 151 ir_visitor_status 152 ir_tree_grafting_visitor::visit_leave(ir_assignment *ir) 153 { 154 if (do_graft(&ir->rhs) || 155 do_graft(&ir->condition)) 156 return visit_stop; 157 158 /* If this assignment updates a variable used in the assignment 159 * we're trying to graft, then we're done. 160 */ 161 if (dereferences_variable(this->graft_assign->rhs, 162 ir->lhs->variable_referenced())) { 163 if (debug) { 164 printf("graft killed by: "); 165 ir->print(); 166 printf("\n"); 167 } 168 return visit_stop; 169 } 170 171 return visit_continue; 172 } 173 174 ir_visitor_status 175 ir_tree_grafting_visitor::visit_enter(ir_function *ir) 176 { 177 (void) ir; 178 return visit_continue_with_parent; 179 } 180 181 ir_visitor_status 182 ir_tree_grafting_visitor::visit_enter(ir_function_signature *ir) 183 { 184 (void)ir; 185 return visit_continue_with_parent; 186 } 187 188 ir_visitor_status 189 ir_tree_grafting_visitor::visit_enter(ir_call *ir) 190 { 191 exec_list_iterator sig_iter = ir->get_callee()->parameters.iterator(); 192 /* Reminder: iterating ir_call iterates its parameters. */ 193 foreach_iter(exec_list_iterator, iter, *ir) { 194 ir_variable *sig_param = (ir_variable *)sig_iter.get(); 195 ir_rvalue *ir = (ir_rvalue *)iter.get(); 196 ir_rvalue *new_ir = ir; 197 198 if (sig_param->mode != ir_var_in) 199 continue; 200 201 if (do_graft(&new_ir)) { 202 ir->replace_with(new_ir); 203 return visit_stop; 204 } 205 sig_iter.next(); 206 } 207 208 return visit_continue; 209 } 210 211 ir_visitor_status 212 ir_tree_grafting_visitor::visit_enter(ir_expression *ir) 213 { 214 for (unsigned int i = 0; i < ir->get_num_operands(); i++) { 215 if (do_graft(&ir->operands[i])) 216 return visit_stop; 217 } 218 219 return visit_continue; 220 } 221 222 ir_visitor_status 223 ir_tree_grafting_visitor::visit_enter(ir_if *ir) 224 { 225 if (do_graft(&ir->condition)) 226 return visit_stop; 227 228 /* Do not traverse into the body of the if-statement since that is a 229 * different basic block. 230 */ 231 return visit_continue_with_parent; 232 } 233 234 ir_visitor_status 235 ir_tree_grafting_visitor::visit_enter(ir_swizzle *ir) 236 { 237 if (do_graft(&ir->val)) 238 return visit_stop; 239 240 return visit_continue; 241 } 242 243 ir_visitor_status 244 ir_tree_grafting_visitor::visit_enter(ir_texture *ir) 245 { 246 if (do_graft(&ir->coordinate) || 247 do_graft(&ir->projector) || 248 do_graft(&ir->shadow_comparitor)) 249 return visit_stop; 250 251 switch (ir->op) { 252 case ir_tex: 253 break; 254 case ir_txb: 255 if (do_graft(&ir->lod_info.bias)) 256 return visit_stop; 257 break; 258 case ir_txf: 259 case ir_txl: 260 if (do_graft(&ir->lod_info.lod)) 261 return visit_stop; 262 break; 263 case ir_txd: 264 if (do_graft(&ir->lod_info.grad.dPdx) || 265 do_graft(&ir->lod_info.grad.dPdy)) 266 return visit_stop; 267 break; 268 } 269 270 return visit_continue; 271 } 272 273 struct tree_grafting_info { 274 ir_variable_refcount_visitor *refs; 275 bool progress; 276 }; 277 278 static bool 279 try_tree_grafting(ir_assignment *start, 280 ir_variable *lhs_var, 281 ir_instruction *bb_last) 282 { 283 ir_tree_grafting_visitor v(start, lhs_var); 284 285 if (debug) { 286 printf("trying to graft: "); 287 lhs_var->print(); 288 printf("\n"); 289 } 290 291 for (ir_instruction *ir = (ir_instruction *)start->next; 292 ir != bb_last->next; 293 ir = (ir_instruction *)ir->next) { 294 295 if (debug) { 296 printf("- "); 297 ir->print(); 298 printf("\n"); 299 } 300 301 ir_visitor_status s = ir->accept(&v); 302 if (s == visit_stop) 303 return v.progress; 304 } 305 306 return false; 307 } 308 309 static void 310 tree_grafting_basic_block(ir_instruction *bb_first, 311 ir_instruction *bb_last, 312 void *data) 313 { 314 struct tree_grafting_info *info = (struct tree_grafting_info *)data; 315 ir_instruction *ir, *next; 316 317 for (ir = bb_first, next = (ir_instruction *)ir->next; 318 ir != bb_last->next; 319 ir = next, next = (ir_instruction *)ir->next) { 320 ir_assignment *assign = ir->as_assignment(); 321 322 if (!assign) 323 continue; 324 325 ir_variable *lhs_var = assign->whole_variable_written(); 326 if (!lhs_var) 327 continue; 328 329 if (lhs_var->mode == ir_var_out || 330 lhs_var->mode == ir_var_inout) 331 continue; 332 333 variable_entry *entry = info->refs->get_variable_entry(lhs_var); 334 335 if (!entry->declaration || 336 entry->assigned_count != 1 || 337 entry->referenced_count != 2) 338 continue; 339 340 assert(assign == entry->assign); 341 342 /* Found a possibly graftable assignment. Now, walk through the 343 * rest of the BB seeing if the deref is here, and if nothing interfered with 344 * pasting its expression's values in between. 345 */ 346 info->progress |= try_tree_grafting(assign, lhs_var, bb_last); 347 } 348 } 349 350 /** 351 * Does a copy propagation pass on the code present in the instruction stream. 352 */ 353 bool 354 do_tree_grafting(exec_list *instructions) 355 { 356 ir_variable_refcount_visitor refs; 357 struct tree_grafting_info info; 358 359 info.progress = false; 360 info.refs = &refs; 361 362 visit_list_elements(info.refs, instructions); 363 364 call_for_basic_blocks(instructions, tree_grafting_basic_block, &info); 365 366 return info.progress; 367 } 368
