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_dead_code_local.cpp 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 36 #include "ir.h" 37 #include "ir_basic_block.h" 38 #include "ir_optimization.h" 39 #include "glsl_types.h" 40 41 static bool debug = false; 42 43 class assignment_entry : public exec_node 44 { 45 public: 46 assignment_entry(ir_variable *lhs, ir_instruction *ir) 47 { 48 assert(lhs); 49 assert(ir); 50 this->lhs = lhs; 51 this->ir = ir; 52 } 53 54 ir_variable *lhs; 55 ir_instruction *ir; 56 }; 57 58 class kill_for_derefs_visitor : public ir_hierarchical_visitor { 59 public: 60 kill_for_derefs_visitor(exec_list *assignments) 61 { 62 this->assignments = assignments; 63 } 64 65 virtual ir_visitor_status visit(ir_dereference_variable *ir) 66 { 67 ir_variable *const var = ir->variable_referenced(); 68 69 foreach_iter(exec_list_iterator, iter, *this->assignments) { 70 assignment_entry *entry = (assignment_entry *)iter.get(); 71 72 if (entry->lhs == var) { 73 if (debug) 74 printf("kill %s\n", entry->lhs->name); 75 entry->remove(); 76 } 77 } 78 79 return visit_continue; 80 } 81 82 private: 83 exec_list *assignments; 84 }; 85 86 class array_index_visit : public ir_hierarchical_visitor { 87 public: 88 array_index_visit(ir_hierarchical_visitor *v) 89 { 90 this->visitor = v; 91 } 92 93 virtual ir_visitor_status visit_enter(class ir_dereference_array *ir) 94 { 95 ir->array_index->accept(visitor); 96 return visit_continue; 97 } 98 99 static void run(ir_instruction *ir, ir_hierarchical_visitor *v) 100 { 101 array_index_visit top_visit(v); 102 ir->accept(& top_visit); 103 } 104 105 ir_hierarchical_visitor *visitor; 106 }; 107 108 109 /** 110 * Adds an entry to the available copy list if it's a plain assignment 111 * of a variable to a variable. 112 */ 113 static bool 114 process_assignment(void *ctx, ir_assignment *ir, exec_list *assignments) 115 { 116 ir_variable *var = NULL; 117 bool progress = false; 118 kill_for_derefs_visitor v(assignments); 119 120 /* Kill assignment entries for things used to produce this assignment. */ 121 ir->rhs->accept(&v); 122 if (ir->condition) { 123 ir->condition->accept(&v); 124 } 125 126 /* Kill assignment enties used as array indices. 127 */ 128 array_index_visit::run(ir->lhs, &v); 129 var = ir->lhs->variable_referenced(); 130 assert(var); 131 132 bool always_assign = true; 133 if (ir->condition) { 134 ir_constant *condition = ir->condition->as_constant(); 135 if (!condition || !condition->value.b[0]) 136 always_assign = false; 137 } 138 139 /* Now, check if we did a whole-variable assignment. */ 140 if (always_assign && (ir->whole_variable_written() != NULL)) { 141 /* We did a whole-variable assignment. So, any instruction in 142 * the assignment list with the same LHS is dead. 143 */ 144 if (debug) 145 printf("looking for %s to remove\n", var->name); 146 foreach_iter(exec_list_iterator, iter, *assignments) { 147 assignment_entry *entry = (assignment_entry *)iter.get(); 148 149 if (entry->lhs == var) { 150 if (debug) 151 printf("removing %s\n", var->name); 152 entry->ir->remove(); 153 entry->remove(); 154 progress = true; 155 } 156 } 157 } 158 159 /* Add this instruction to the assignment list available to be removed. 160 * But not if the assignment has other side effects. 161 */ 162 if (ir_has_call(ir)) 163 return progress; 164 165 assignment_entry *entry = new(ctx) assignment_entry(var, ir); 166 assignments->push_tail(entry); 167 168 if (debug) { 169 printf("add %s\n", var->name); 170 171 printf("current entries\n"); 172 foreach_iter(exec_list_iterator, iter, *assignments) { 173 assignment_entry *entry = (assignment_entry *)iter.get(); 174 175 printf(" %s\n", entry->lhs->name); 176 } 177 } 178 179 return progress; 180 } 181 182 static void 183 dead_code_local_basic_block(ir_instruction *first, 184 ir_instruction *last, 185 void *data) 186 { 187 ir_instruction *ir, *ir_next; 188 /* List of avaialble_copy */ 189 exec_list assignments; 190 bool *out_progress = (bool *)data; 191 bool progress = false; 192 193 void *ctx = hieralloc_new(NULL); 194 /* Safe looping, since process_assignment */ 195 for (ir = first, ir_next = (ir_instruction *)first->next;; 196 ir = ir_next, ir_next = (ir_instruction *)ir->next) { 197 ir_assignment *ir_assign = ir->as_assignment(); 198 199 if (debug) { 200 ir->print(); 201 printf("\n"); 202 } 203 204 if (ir_assign) { 205 progress = process_assignment(ctx, ir_assign, &assignments) || progress; 206 } else { 207 kill_for_derefs_visitor kill(&assignments); 208 ir->accept(&kill); 209 } 210 211 if (ir == last) 212 break; 213 } 214 *out_progress = progress; 215 hieralloc_free(ctx); 216 } 217 218 /** 219 * Does a copy propagation pass on the code present in the instruction stream. 220 */ 221 bool 222 do_dead_code_local(exec_list *instructions) 223 { 224 bool progress = false; 225 226 call_for_basic_blocks(instructions, dead_code_local_basic_block, &progress); 227 228 return progress; 229 } 230