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
41static bool debug = false;
42
43namespace {
44
45class assignment_entry : public exec_node
46{
47public:
48   assignment_entry(ir_variable *lhs, ir_assignment *ir)
49   {
50      assert(lhs);
51      assert(ir);
52      this->lhs = lhs;
53      this->ir = ir;
54      this->available = ir->write_mask;
55   }
56
57   ir_variable *lhs;
58   ir_assignment *ir;
59
60   /* bitmask of xyzw channels written that haven't been used so far. */
61   int available;
62};
63
64class kill_for_derefs_visitor : public ir_hierarchical_visitor {
65public:
66   kill_for_derefs_visitor(exec_list *assignments)
67   {
68      this->assignments = assignments;
69   }
70
71   void kill_channels(ir_variable *const var, int used)
72   {
73      foreach_iter(exec_list_iterator, iter, *this->assignments) {
74	 assignment_entry *entry = (assignment_entry *)iter.get();
75
76	 if (entry->lhs == var) {
77	    if (var->type->is_scalar() || var->type->is_vector()) {
78	       if (debug)
79		  printf("kill %s (0x%01x - 0x%01x)\n", entry->lhs->name,
80			 entry->available, used);
81	       entry->available &= ~used;
82	       if (!entry->available)
83		  entry->remove();
84	    } else {
85	       if (debug)
86		  printf("kill %s\n", entry->lhs->name);
87	       entry->remove();
88	    }
89	 }
90      }
91   }
92
93   virtual ir_visitor_status visit(ir_dereference_variable *ir)
94   {
95      kill_channels(ir->var, ~0);
96
97      return visit_continue;
98   }
99
100   virtual ir_visitor_status visit(ir_swizzle *ir)
101   {
102      ir_dereference_variable *deref = ir->val->as_dereference_variable();
103      if (!deref)
104	 return visit_continue;
105
106      int used = 0;
107      used |= 1 << ir->mask.x;
108      used |= 1 << ir->mask.y;
109      used |= 1 << ir->mask.z;
110      used |= 1 << ir->mask.w;
111
112      kill_channels(deref->var, used);
113
114      return visit_continue_with_parent;
115   }
116
117private:
118   exec_list *assignments;
119};
120
121class array_index_visit : public ir_hierarchical_visitor {
122public:
123   array_index_visit(ir_hierarchical_visitor *v)
124   {
125      this->visitor = v;
126   }
127
128   virtual ir_visitor_status visit_enter(class ir_dereference_array *ir)
129   {
130      ir->array_index->accept(visitor);
131      return visit_continue;
132   }
133
134   static void run(ir_instruction *ir, ir_hierarchical_visitor *v)
135   {
136      array_index_visit top_visit(v);
137      ir->accept(& top_visit);
138   }
139
140   ir_hierarchical_visitor *visitor;
141};
142
143} /* unnamed namespace */
144
145/**
146 * Adds an entry to the available copy list if it's a plain assignment
147 * of a variable to a variable.
148 */
149static bool
150process_assignment(void *ctx, ir_assignment *ir, exec_list *assignments)
151{
152   ir_variable *var = NULL;
153   bool progress = false;
154   kill_for_derefs_visitor v(assignments);
155
156   /* Kill assignment entries for things used to produce this assignment. */
157   ir->rhs->accept(&v);
158   if (ir->condition) {
159      ir->condition->accept(&v);
160   }
161
162   /* Kill assignment enties used as array indices.
163    */
164   array_index_visit::run(ir->lhs, &v);
165   var = ir->lhs->variable_referenced();
166   assert(var);
167
168   /* Now, check if we did a whole-variable assignment. */
169   if (!ir->condition) {
170      ir_dereference_variable *deref_var = ir->lhs->as_dereference_variable();
171
172      /* If it's a vector type, we can do per-channel elimination of
173       * use of the RHS.
174       */
175      if (deref_var && (deref_var->var->type->is_scalar() ||
176			deref_var->var->type->is_vector())) {
177
178	 if (debug)
179	    printf("looking for %s.0x%01x to remove\n", var->name,
180		   ir->write_mask);
181
182	 foreach_iter(exec_list_iterator, iter, *assignments) {
183	    assignment_entry *entry = (assignment_entry *)iter.get();
184
185	    if (entry->lhs != var)
186	       continue;
187
188	    int remove = entry->available & ir->write_mask;
189	    if (debug) {
190	       printf("%s 0x%01x - 0x%01x = 0x%01x\n",
191		      var->name,
192		      entry->ir->write_mask,
193		      remove, entry->ir->write_mask & ~remove);
194	    }
195	    if (remove) {
196	       progress = true;
197
198	       if (debug) {
199		  printf("rewriting:\n  ");
200		  entry->ir->print();
201		  printf("\n");
202	       }
203
204	       entry->ir->write_mask &= ~remove;
205	       entry->available &= ~remove;
206	       if (entry->ir->write_mask == 0) {
207		  /* Delete the dead assignment. */
208		  entry->ir->remove();
209		  entry->remove();
210	       } else {
211		  void *mem_ctx = ralloc_parent(entry->ir);
212		  /* Reswizzle the RHS arguments according to the new
213		   * write_mask.
214		   */
215		  unsigned components[4];
216		  unsigned channels = 0;
217		  unsigned next = 0;
218
219		  for (int i = 0; i < 4; i++) {
220		     if ((entry->ir->write_mask | remove) & (1 << i)) {
221			if (!(remove & (1 << i)))
222			   components[channels++] = next;
223			next++;
224		     }
225		  }
226
227		  entry->ir->rhs = new(mem_ctx) ir_swizzle(entry->ir->rhs,
228							   components,
229							   channels);
230		  if (debug) {
231		     printf("to:\n  ");
232		     entry->ir->print();
233		     printf("\n");
234		  }
235	       }
236	    }
237	 }
238      } else if (ir->whole_variable_written() != NULL) {
239	 /* We did a whole-variable assignment.  So, any instruction in
240	  * the assignment list with the same LHS is dead.
241	  */
242	 if (debug)
243	    printf("looking for %s to remove\n", var->name);
244	 foreach_iter(exec_list_iterator, iter, *assignments) {
245	    assignment_entry *entry = (assignment_entry *)iter.get();
246
247	    if (entry->lhs == var) {
248	       if (debug)
249		  printf("removing %s\n", var->name);
250	       entry->ir->remove();
251	       entry->remove();
252	       progress = true;
253	    }
254	 }
255      }
256   }
257
258   /* Add this instruction to the assignment list available to be removed. */
259   assignment_entry *entry = new(ctx) assignment_entry(var, ir);
260   assignments->push_tail(entry);
261
262   if (debug) {
263      printf("add %s\n", var->name);
264
265      printf("current entries\n");
266      foreach_iter(exec_list_iterator, iter, *assignments) {
267	 assignment_entry *entry = (assignment_entry *)iter.get();
268
269	 printf("    %s (0x%01x)\n", entry->lhs->name, entry->available);
270      }
271   }
272
273   return progress;
274}
275
276static void
277dead_code_local_basic_block(ir_instruction *first,
278			     ir_instruction *last,
279			     void *data)
280{
281   ir_instruction *ir, *ir_next;
282   /* List of avaialble_copy */
283   exec_list assignments;
284   bool *out_progress = (bool *)data;
285   bool progress = false;
286
287   void *ctx = ralloc_context(NULL);
288   /* Safe looping, since process_assignment */
289   for (ir = first, ir_next = (ir_instruction *)first->next;;
290	ir = ir_next, ir_next = (ir_instruction *)ir->next) {
291      ir_assignment *ir_assign = ir->as_assignment();
292
293      if (debug) {
294	 ir->print();
295	 printf("\n");
296      }
297
298      if (ir_assign) {
299	 progress = process_assignment(ctx, ir_assign, &assignments) || progress;
300      } else {
301	 kill_for_derefs_visitor kill(&assignments);
302	 ir->accept(&kill);
303      }
304
305      if (ir == last)
306	 break;
307   }
308   *out_progress = progress;
309   ralloc_free(ctx);
310}
311
312/**
313 * Does a copy propagation pass on the code present in the instruction stream.
314 */
315bool
316do_dead_code_local(exec_list *instructions)
317{
318   bool progress = false;
319
320   call_for_basic_blocks(instructions, dead_code_local_basic_block, &progress);
321
322   return progress;
323}
324