Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -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 | /** |
Chad Versace | df883eb | 2010-11-17 10:43:10 -0800 | [diff] [blame] | 25 | * \file opt_dead_code_local.cpp |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 26 | * |
| 27 | * Eliminates local dead assignments from the code. |
| 28 | * |
| 29 | * This operates on basic blocks, tracking assignments and finding if |
| 30 | * they're used before the variable is completely reassigned. |
| 31 | * |
| 32 | * Compare this to ir_dead_code.cpp, which operates globally looking |
| 33 | * for assignments to variables that are never read. |
| 34 | */ |
| 35 | |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 36 | #include "ir.h" |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 37 | #include "ir_basic_block.h" |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 38 | #include "ir_optimization.h" |
| 39 | #include "glsl_types.h" |
| 40 | |
| 41 | static bool debug = false; |
| 42 | |
Eric Anholt | 337d9c9 | 2012-05-29 16:18:37 -0700 | [diff] [blame] | 43 | namespace { |
| 44 | |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 45 | class assignment_entry : public exec_node |
| 46 | { |
| 47 | public: |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 48 | assignment_entry(ir_variable *lhs, ir_assignment *ir) |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 49 | { |
| 50 | assert(lhs); |
| 51 | assert(ir); |
| 52 | this->lhs = lhs; |
| 53 | this->ir = ir; |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 54 | this->unused = ir->write_mask; |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 55 | } |
| 56 | |
| 57 | ir_variable *lhs; |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 58 | ir_assignment *ir; |
| 59 | |
| 60 | /* bitmask of xyzw channels written that haven't been used so far. */ |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 61 | int unused; |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 62 | }; |
| 63 | |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 64 | class kill_for_derefs_visitor : public ir_hierarchical_visitor { |
| 65 | public: |
| 66 | kill_for_derefs_visitor(exec_list *assignments) |
| 67 | { |
| 68 | this->assignments = assignments; |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 69 | } |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 70 | |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 71 | void use_channels(ir_variable *const var, int used) |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 72 | { |
Matt Turner | c6a16f6 | 2014-06-24 21:58:35 -0700 | [diff] [blame] | 73 | foreach_in_list_safe(assignment_entry, entry, this->assignments) { |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 74 | if (entry->lhs == var) { |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 75 | if (var->type->is_scalar() || var->type->is_vector()) { |
| 76 | if (debug) |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 77 | printf("used %s (0x%01x - 0x%01x)\n", entry->lhs->name, |
| 78 | entry->unused, used & 0xf); |
| 79 | entry->unused &= ~used; |
| 80 | if (!entry->unused) |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 81 | entry->remove(); |
| 82 | } else { |
| 83 | if (debug) |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 84 | printf("used %s\n", entry->lhs->name); |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 85 | entry->remove(); |
| 86 | } |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 87 | } |
| 88 | } |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 89 | } |
| 90 | |
| 91 | virtual ir_visitor_status visit(ir_dereference_variable *ir) |
| 92 | { |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 93 | use_channels(ir->var, ~0); |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 94 | |
| 95 | return visit_continue; |
| 96 | } |
| 97 | |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 98 | virtual ir_visitor_status visit(ir_swizzle *ir) |
| 99 | { |
| 100 | ir_dereference_variable *deref = ir->val->as_dereference_variable(); |
| 101 | if (!deref) |
| 102 | return visit_continue; |
| 103 | |
| 104 | int used = 0; |
| 105 | used |= 1 << ir->mask.x; |
| 106 | used |= 1 << ir->mask.y; |
| 107 | used |= 1 << ir->mask.z; |
| 108 | used |= 1 << ir->mask.w; |
| 109 | |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 110 | use_channels(deref->var, used); |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 111 | |
| 112 | return visit_continue_with_parent; |
| 113 | } |
| 114 | |
Iago Toral Quiroga | 8639eff | 2014-06-20 10:26:29 +0200 | [diff] [blame] | 115 | virtual ir_visitor_status visit_leave(ir_emit_vertex *) |
Bryan Cain | ae6eba3 | 2013-02-15 09:26:35 -0600 | [diff] [blame] | 116 | { |
| 117 | /* For the purpose of dead code elimination, emitting a vertex counts as |
| 118 | * "reading" all of the currently assigned output variables. |
| 119 | */ |
Matt Turner | c6a16f6 | 2014-06-24 21:58:35 -0700 | [diff] [blame] | 120 | foreach_in_list_safe(assignment_entry, entry, this->assignments) { |
Tapani Pälli | 33ee2c6 | 2013-12-12 13:51:01 +0200 | [diff] [blame] | 121 | if (entry->lhs->data.mode == ir_var_shader_out) { |
Bryan Cain | ae6eba3 | 2013-02-15 09:26:35 -0600 | [diff] [blame] | 122 | if (debug) |
| 123 | printf("kill %s\n", entry->lhs->name); |
| 124 | entry->remove(); |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | return visit_continue; |
| 129 | } |
| 130 | |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 131 | private: |
| 132 | exec_list *assignments; |
| 133 | }; |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 134 | |
Ian Romanick | 7fe3de6 | 2010-05-19 13:47:39 +0200 | [diff] [blame] | 135 | class array_index_visit : public ir_hierarchical_visitor { |
| 136 | public: |
| 137 | array_index_visit(ir_hierarchical_visitor *v) |
| 138 | { |
| 139 | this->visitor = v; |
| 140 | } |
| 141 | |
| 142 | virtual ir_visitor_status visit_enter(class ir_dereference_array *ir) |
| 143 | { |
Ian Romanick | 36ea286 | 2010-05-19 13:52:29 +0200 | [diff] [blame] | 144 | ir->array_index->accept(visitor); |
Ian Romanick | 7fe3de6 | 2010-05-19 13:47:39 +0200 | [diff] [blame] | 145 | return visit_continue; |
| 146 | } |
| 147 | |
| 148 | static void run(ir_instruction *ir, ir_hierarchical_visitor *v) |
| 149 | { |
| 150 | array_index_visit top_visit(v); |
| 151 | ir->accept(& top_visit); |
| 152 | } |
| 153 | |
| 154 | ir_hierarchical_visitor *visitor; |
| 155 | }; |
| 156 | |
Eric Anholt | 337d9c9 | 2012-05-29 16:18:37 -0700 | [diff] [blame] | 157 | } /* unnamed namespace */ |
Ian Romanick | 7fe3de6 | 2010-05-19 13:47:39 +0200 | [diff] [blame] | 158 | |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 159 | /** |
| 160 | * Adds an entry to the available copy list if it's a plain assignment |
| 161 | * of a variable to a variable. |
| 162 | */ |
| 163 | static bool |
Kenneth Graunke | a815f7f | 2010-06-25 13:36:14 -0700 | [diff] [blame] | 164 | process_assignment(void *ctx, ir_assignment *ir, exec_list *assignments) |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 165 | { |
| 166 | ir_variable *var = NULL; |
| 167 | bool progress = false; |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 168 | kill_for_derefs_visitor v(assignments); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 169 | |
| 170 | /* Kill assignment entries for things used to produce this assignment. */ |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 171 | ir->rhs->accept(&v); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 172 | if (ir->condition) { |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 173 | ir->condition->accept(&v); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 174 | } |
| 175 | |
Ian Romanick | 7fe3de6 | 2010-05-19 13:47:39 +0200 | [diff] [blame] | 176 | /* Kill assignment enties used as array indices. |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 177 | */ |
Ian Romanick | 7fe3de6 | 2010-05-19 13:47:39 +0200 | [diff] [blame] | 178 | array_index_visit::run(ir->lhs, &v); |
| 179 | var = ir->lhs->variable_referenced(); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 180 | assert(var); |
| 181 | |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 182 | /* Now, check if we did a whole-variable assignment. */ |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 183 | if (!ir->condition) { |
| 184 | ir_dereference_variable *deref_var = ir->lhs->as_dereference_variable(); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 185 | |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 186 | /* If it's a vector type, we can do per-channel elimination of |
| 187 | * use of the RHS. |
| 188 | */ |
| 189 | if (deref_var && (deref_var->var->type->is_scalar() || |
| 190 | deref_var->var->type->is_vector())) { |
| 191 | |
| 192 | if (debug) |
| 193 | printf("looking for %s.0x%01x to remove\n", var->name, |
| 194 | ir->write_mask); |
| 195 | |
Matt Turner | c6a16f6 | 2014-06-24 21:58:35 -0700 | [diff] [blame] | 196 | foreach_in_list_safe(assignment_entry, entry, assignments) { |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 197 | if (entry->lhs != var) |
| 198 | continue; |
| 199 | |
Kristian Høgsberg Kristensen | 96b22fb | 2015-11-04 14:58:54 -0800 | [diff] [blame] | 200 | /* Skip if the assignment we're trying to eliminate isn't a plain |
| 201 | * variable deref. */ |
| 202 | if (entry->ir->lhs->ir_type != ir_type_dereference_variable) |
| 203 | continue; |
| 204 | |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 205 | int remove = entry->unused & ir->write_mask; |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 206 | if (debug) { |
| 207 | printf("%s 0x%01x - 0x%01x = 0x%01x\n", |
| 208 | var->name, |
| 209 | entry->ir->write_mask, |
| 210 | remove, entry->ir->write_mask & ~remove); |
| 211 | } |
| 212 | if (remove) { |
| 213 | progress = true; |
| 214 | |
| 215 | if (debug) { |
| 216 | printf("rewriting:\n "); |
| 217 | entry->ir->print(); |
| 218 | printf("\n"); |
| 219 | } |
| 220 | |
| 221 | entry->ir->write_mask &= ~remove; |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 222 | entry->unused &= ~remove; |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 223 | if (entry->ir->write_mask == 0) { |
| 224 | /* Delete the dead assignment. */ |
| 225 | entry->ir->remove(); |
| 226 | entry->remove(); |
| 227 | } else { |
| 228 | void *mem_ctx = ralloc_parent(entry->ir); |
| 229 | /* Reswizzle the RHS arguments according to the new |
| 230 | * write_mask. |
| 231 | */ |
| 232 | unsigned components[4]; |
| 233 | unsigned channels = 0; |
| 234 | unsigned next = 0; |
| 235 | |
| 236 | for (int i = 0; i < 4; i++) { |
| 237 | if ((entry->ir->write_mask | remove) & (1 << i)) { |
| 238 | if (!(remove & (1 << i))) |
| 239 | components[channels++] = next; |
| 240 | next++; |
| 241 | } |
| 242 | } |
| 243 | |
| 244 | entry->ir->rhs = new(mem_ctx) ir_swizzle(entry->ir->rhs, |
| 245 | components, |
| 246 | channels); |
| 247 | if (debug) { |
| 248 | printf("to:\n "); |
| 249 | entry->ir->print(); |
| 250 | printf("\n"); |
| 251 | } |
| 252 | } |
| 253 | } |
| 254 | } |
| 255 | } else if (ir->whole_variable_written() != NULL) { |
| 256 | /* We did a whole-variable assignment. So, any instruction in |
| 257 | * the assignment list with the same LHS is dead. |
| 258 | */ |
| 259 | if (debug) |
| 260 | printf("looking for %s to remove\n", var->name); |
Matt Turner | c6a16f6 | 2014-06-24 21:58:35 -0700 | [diff] [blame] | 261 | foreach_in_list_safe(assignment_entry, entry, assignments) { |
Eric Anholt | 05c200b | 2012-02-23 11:51:04 -0800 | [diff] [blame] | 262 | if (entry->lhs == var) { |
| 263 | if (debug) |
| 264 | printf("removing %s\n", var->name); |
| 265 | entry->ir->remove(); |
| 266 | entry->remove(); |
| 267 | progress = true; |
| 268 | } |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 269 | } |
| 270 | } |
| 271 | } |
| 272 | |
Kenneth Graunke | d884f60 | 2012-03-20 15:56:37 -0700 | [diff] [blame] | 273 | /* Add this instruction to the assignment list available to be removed. */ |
Carl Worth | 1660a29 | 2010-06-23 18:11:51 -0700 | [diff] [blame] | 274 | assignment_entry *entry = new(ctx) assignment_entry(var, ir); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 275 | assignments->push_tail(entry); |
| 276 | |
| 277 | if (debug) { |
| 278 | printf("add %s\n", var->name); |
| 279 | |
| 280 | printf("current entries\n"); |
Matt Turner | 4d78446 | 2014-06-24 21:34:05 -0700 | [diff] [blame] | 281 | foreach_in_list(assignment_entry, entry, assignments) { |
Eric Anholt | 2dbebbd | 2014-03-05 23:03:42 -0800 | [diff] [blame] | 282 | printf(" %s (0x%01x)\n", entry->lhs->name, entry->unused); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 283 | } |
| 284 | } |
| 285 | |
| 286 | return progress; |
| 287 | } |
| 288 | |
| 289 | static void |
| 290 | dead_code_local_basic_block(ir_instruction *first, |
| 291 | ir_instruction *last, |
| 292 | void *data) |
| 293 | { |
| 294 | ir_instruction *ir, *ir_next; |
| 295 | /* List of avaialble_copy */ |
| 296 | exec_list assignments; |
| 297 | bool *out_progress = (bool *)data; |
| 298 | bool progress = false; |
| 299 | |
Kenneth Graunke | d3073f5 | 2011-01-21 14:32:31 -0800 | [diff] [blame] | 300 | void *ctx = ralloc_context(NULL); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 301 | /* Safe looping, since process_assignment */ |
| 302 | for (ir = first, ir_next = (ir_instruction *)first->next;; |
| 303 | ir = ir_next, ir_next = (ir_instruction *)ir->next) { |
| 304 | ir_assignment *ir_assign = ir->as_assignment(); |
| 305 | |
| 306 | if (debug) { |
Eric Anholt | e46a454 | 2010-06-22 12:09:21 -0700 | [diff] [blame] | 307 | ir->print(); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 308 | printf("\n"); |
| 309 | } |
| 310 | |
| 311 | if (ir_assign) { |
Kenneth Graunke | a815f7f | 2010-06-25 13:36:14 -0700 | [diff] [blame] | 312 | progress = process_assignment(ctx, ir_assign, &assignments) || progress; |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 313 | } else { |
Ian Romanick | 551c9c0 | 2010-05-14 14:31:25 -0700 | [diff] [blame] | 314 | kill_for_derefs_visitor kill(&assignments); |
| 315 | ir->accept(&kill); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 316 | } |
| 317 | |
| 318 | if (ir == last) |
| 319 | break; |
| 320 | } |
| 321 | *out_progress = progress; |
Kenneth Graunke | d3073f5 | 2011-01-21 14:32:31 -0800 | [diff] [blame] | 322 | ralloc_free(ctx); |
Eric Anholt | 6255a1f | 2010-05-05 10:37:25 -0700 | [diff] [blame] | 323 | } |
| 324 | |
| 325 | /** |
| 326 | * Does a copy propagation pass on the code present in the instruction stream. |
| 327 | */ |
| 328 | bool |
| 329 | do_dead_code_local(exec_list *instructions) |
| 330 | { |
| 331 | bool progress = false; |
| 332 | |
| 333 | call_for_basic_blocks(instructions, dead_code_local_basic_block, &progress); |
| 334 | |
| 335 | return progress; |
| 336 | } |