Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 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 | /** |
Eric Anholt | aef0aae | 2010-05-05 09:38:09 -0700 | [diff] [blame] | 25 | * \file ir_copy_propagation.cpp |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 26 | * |
Eric Anholt | aef0aae | 2010-05-05 09:38:09 -0700 | [diff] [blame] | 27 | * Moves usage of recently-copied variables to the previous copy of |
| 28 | * the variable within basic blocks. |
| 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. |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 33 | */ |
| 34 | |
| 35 | #include <stdio.h> |
| 36 | #include "ir.h" |
| 37 | #include "ir_visitor.h" |
Eric Anholt | 4e2c0b9 | 2010-05-05 09:26:46 -0700 | [diff] [blame] | 38 | #include "ir_print_visitor.h" |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 39 | #include "ir_basic_block.h" |
Eric Anholt | bdd9b1f | 2010-05-05 11:45:30 -0700 | [diff] [blame^] | 40 | #include "ir_optimization.h" |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 41 | #include "glsl_types.h" |
| 42 | |
| 43 | class acp_entry : public exec_node |
| 44 | { |
| 45 | public: |
| 46 | acp_entry(ir_variable *lhs, ir_variable *rhs) |
| 47 | { |
| 48 | assert(lhs); |
| 49 | assert(rhs); |
| 50 | this->lhs = lhs; |
| 51 | this->rhs = rhs; |
| 52 | } |
| 53 | |
| 54 | ir_variable *lhs; |
| 55 | ir_variable *rhs; |
| 56 | }; |
| 57 | |
| 58 | class ir_copy_propagation_visitor : public ir_visitor { |
| 59 | public: |
| 60 | ir_copy_propagation_visitor(exec_list *acp) |
| 61 | { |
| 62 | progress = false; |
| 63 | this->acp = acp; |
| 64 | } |
| 65 | |
| 66 | /** |
| 67 | * \name Visit methods |
| 68 | * |
| 69 | * As typical for the visitor pattern, there must be one \c visit method for |
| 70 | * each concrete subclass of \c ir_instruction. Virtual base classes within |
| 71 | * the hierarchy should not have \c visit methods. |
| 72 | */ |
| 73 | /*@{*/ |
| 74 | virtual void visit(ir_variable *); |
| 75 | virtual void visit(ir_loop *); |
| 76 | virtual void visit(ir_loop_jump *); |
| 77 | virtual void visit(ir_function_signature *); |
| 78 | virtual void visit(ir_function *); |
| 79 | virtual void visit(ir_expression *); |
| 80 | virtual void visit(ir_swizzle *); |
| 81 | virtual void visit(ir_dereference *); |
| 82 | virtual void visit(ir_assignment *); |
| 83 | virtual void visit(ir_constant *); |
| 84 | virtual void visit(ir_call *); |
| 85 | virtual void visit(ir_return *); |
| 86 | virtual void visit(ir_if *); |
| 87 | /*@}*/ |
| 88 | |
| 89 | /** List of acp_entry */ |
| 90 | exec_list *acp; |
| 91 | bool progress; |
| 92 | }; |
| 93 | |
| 94 | |
| 95 | void |
| 96 | ir_copy_propagation_visitor::visit(ir_variable *ir) |
| 97 | { |
| 98 | (void)ir; |
| 99 | } |
| 100 | |
| 101 | |
| 102 | void |
| 103 | ir_copy_propagation_visitor::visit(ir_loop *ir) |
| 104 | { |
| 105 | (void)ir; |
| 106 | } |
| 107 | |
| 108 | void |
| 109 | ir_copy_propagation_visitor::visit(ir_loop_jump *ir) |
| 110 | { |
| 111 | (void) ir; |
| 112 | } |
| 113 | |
| 114 | |
| 115 | void |
| 116 | ir_copy_propagation_visitor::visit(ir_function_signature *ir) |
| 117 | { |
| 118 | (void)ir; |
| 119 | } |
| 120 | |
| 121 | void |
| 122 | ir_copy_propagation_visitor::visit(ir_function *ir) |
| 123 | { |
| 124 | (void) ir; |
| 125 | } |
| 126 | |
| 127 | void |
| 128 | ir_copy_propagation_visitor::visit(ir_expression *ir) |
| 129 | { |
| 130 | unsigned int operand; |
| 131 | |
| 132 | for (operand = 0; operand < ir->get_num_operands(); operand++) { |
| 133 | ir->operands[operand]->accept(this); |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | |
| 138 | void |
| 139 | ir_copy_propagation_visitor::visit(ir_swizzle *ir) |
| 140 | { |
| 141 | ir->val->accept(this); |
| 142 | } |
| 143 | |
| 144 | /** |
| 145 | * Replaces dereferences of ACP RHS variables with ACP LHS variables. |
| 146 | * |
| 147 | * This is where the actual copy propagation occurs. Note that the |
| 148 | * rewriting of ir_dereference means that the ir_dereference instance |
| 149 | * must not be shared by multiple IR operations! |
| 150 | */ |
| 151 | void |
| 152 | ir_copy_propagation_visitor::visit(ir_dereference *ir) |
| 153 | { |
| 154 | ir_variable *var; |
| 155 | |
| 156 | if (ir->mode == ir_dereference::ir_reference_array) { |
| 157 | ir->selector.array_index->accept(this); |
| 158 | } |
| 159 | |
| 160 | var = ir->var->as_variable(); |
| 161 | if (var) { |
| 162 | foreach_iter(exec_list_iterator, iter, *this->acp) { |
| 163 | acp_entry *entry = (acp_entry *)iter.get(); |
| 164 | |
| 165 | if (var == entry->lhs) { |
| 166 | ir->var = entry->rhs; |
| 167 | this->progress = true; |
| 168 | break; |
| 169 | } |
| 170 | } |
| 171 | } else { |
| 172 | ir->var->accept(this); |
| 173 | } |
| 174 | } |
| 175 | |
| 176 | void |
| 177 | ir_copy_propagation_visitor::visit(ir_assignment *ir) |
| 178 | { |
| 179 | if (ir->condition) |
| 180 | ir->condition->accept(this); |
| 181 | |
| 182 | /* Ignores the LHS. Don't want to rewrite the LHS to point at some |
| 183 | * other storage! |
| 184 | */ |
| 185 | |
| 186 | ir->rhs->accept(this); |
| 187 | } |
| 188 | |
| 189 | |
| 190 | void |
| 191 | ir_copy_propagation_visitor::visit(ir_constant *ir) |
| 192 | { |
| 193 | (void) ir; |
| 194 | } |
| 195 | |
| 196 | |
| 197 | void |
| 198 | ir_copy_propagation_visitor::visit(ir_call *ir) |
| 199 | { |
| 200 | (void)ir; |
| 201 | |
| 202 | /* Note, if we were to do copy propagation to parameters of calls, we'd |
| 203 | * have to be careful about out params. |
| 204 | */ |
| 205 | } |
| 206 | |
| 207 | |
| 208 | void |
| 209 | ir_copy_propagation_visitor::visit(ir_return *ir) |
| 210 | { |
| 211 | ir_rvalue *val = ir->get_value(); |
| 212 | |
| 213 | if (val) |
| 214 | val->accept(this); |
| 215 | } |
| 216 | |
| 217 | |
| 218 | void |
| 219 | ir_copy_propagation_visitor::visit(ir_if *ir) |
| 220 | { |
| 221 | ir->condition->accept(this); |
| 222 | } |
| 223 | |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 224 | static bool |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 225 | propagate_copies(ir_instruction *ir, exec_list *acp) |
| 226 | { |
| 227 | ir_copy_propagation_visitor v(acp); |
| 228 | |
| 229 | ir->accept(&v); |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 230 | |
| 231 | return v.progress; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 232 | } |
| 233 | |
| 234 | static void |
| 235 | kill_invalidated_copies(ir_assignment *ir, exec_list *acp) |
| 236 | { |
Eric Anholt | 4e2c0b9 | 2010-05-05 09:26:46 -0700 | [diff] [blame] | 237 | ir_instruction *current = ir->lhs; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 238 | |
Eric Anholt | 4e2c0b9 | 2010-05-05 09:26:46 -0700 | [diff] [blame] | 239 | /* Walk down the dereference chain to find the variable at the end |
| 240 | * of it that we're actually modifying. |
| 241 | */ |
| 242 | while (current != NULL) { |
| 243 | ir_swizzle *swiz; |
| 244 | ir_dereference *deref; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 245 | |
Eric Anholt | 4e2c0b9 | 2010-05-05 09:26:46 -0700 | [diff] [blame] | 246 | if ((swiz = current->as_swizzle())) { |
| 247 | current = swiz->val; |
| 248 | } else if ((deref = current->as_dereference())) { |
| 249 | current = deref->var; |
| 250 | } else { |
| 251 | ir_variable *var = current->as_variable(); |
| 252 | assert(var); |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 253 | |
Eric Anholt | 4e2c0b9 | 2010-05-05 09:26:46 -0700 | [diff] [blame] | 254 | foreach_iter(exec_list_iterator, iter, *acp) { |
| 255 | acp_entry *entry = (acp_entry *)iter.get(); |
| 256 | |
| 257 | if (entry->lhs == var || entry->rhs == var) { |
| 258 | entry->remove(); |
| 259 | } |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 260 | } |
Eric Anholt | 4e2c0b9 | 2010-05-05 09:26:46 -0700 | [diff] [blame] | 261 | current = NULL; |
| 262 | break; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 263 | } |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 264 | } |
| 265 | } |
| 266 | |
| 267 | /** |
| 268 | * Adds an entry to the available copy list if it's a plain assignment |
| 269 | * of a variable to a variable. |
| 270 | */ |
| 271 | static void |
| 272 | add_copy(ir_assignment *ir, exec_list *acp) |
| 273 | { |
| 274 | acp_entry *entry; |
| 275 | |
| 276 | if (ir->condition) { |
| 277 | ir_constant *condition = ir->condition->as_constant(); |
| 278 | if (!condition || !condition->value.b[0]) |
| 279 | return; |
| 280 | } |
| 281 | |
| 282 | ir_dereference *lhs_deref = ir->lhs->as_dereference(); |
| 283 | if (!lhs_deref || lhs_deref->mode != ir_dereference::ir_reference_variable) |
| 284 | return; |
| 285 | ir_variable *lhs_var = lhs_deref->var->as_variable(); |
| 286 | |
| 287 | ir_dereference *rhs_deref = ir->rhs->as_dereference(); |
| 288 | if (!rhs_deref || rhs_deref->mode != ir_dereference::ir_reference_variable) |
| 289 | return; |
| 290 | ir_variable *rhs_var = rhs_deref->var->as_variable(); |
| 291 | |
| 292 | entry = new acp_entry(lhs_var, rhs_var); |
| 293 | acp->push_tail(entry); |
| 294 | } |
| 295 | |
| 296 | static void |
| 297 | copy_propagation_basic_block(ir_instruction *first, |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 298 | ir_instruction *last, |
| 299 | void *data) |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 300 | { |
| 301 | ir_instruction *ir; |
| 302 | /* List of avaialble_copy */ |
| 303 | exec_list acp; |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 304 | bool *out_progress = (bool *)data; |
| 305 | bool progress = false; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 306 | |
| 307 | for (ir = first;; ir = (ir_instruction *)ir->next) { |
| 308 | ir_assignment *ir_assign = ir->as_assignment(); |
| 309 | |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 310 | progress = propagate_copies(ir, &acp) || progress; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 311 | |
| 312 | if (ir_assign) { |
| 313 | kill_invalidated_copies(ir_assign, &acp); |
| 314 | |
| 315 | add_copy(ir_assign, &acp); |
| 316 | } |
| 317 | if (ir == last) |
| 318 | break; |
| 319 | } |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 320 | *out_progress = progress; |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 321 | } |
| 322 | |
| 323 | /** |
| 324 | * Does a copy propagation pass on the code present in the instruction stream. |
| 325 | */ |
| 326 | bool |
| 327 | do_copy_propagation(exec_list *instructions) |
| 328 | { |
| 329 | bool progress = false; |
| 330 | |
Eric Anholt | 8e75de3 | 2010-05-05 09:31:53 -0700 | [diff] [blame] | 331 | call_for_basic_blocks(instructions, copy_propagation_basic_block, &progress); |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 332 | |
Eric Anholt | 5c89f0e | 2010-05-04 13:04:40 -0700 | [diff] [blame] | 333 | return progress; |
| 334 | } |