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
57static bool debug = false;
58
59class ir_tree_grafting_visitor : public ir_hierarchical_visitor {
60public:
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
86struct find_deref_info {
87   ir_variable *var;
88   bool found;
89};
90
91void
92dereferences_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
101static bool
102dereferences_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
114bool
115ir_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
141ir_visitor_status
142ir_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
151ir_visitor_status
152ir_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
174ir_visitor_status
175ir_tree_grafting_visitor::visit_enter(ir_function *ir)
176{
177   (void) ir;
178   return visit_continue_with_parent;
179}
180
181ir_visitor_status
182ir_tree_grafting_visitor::visit_enter(ir_function_signature *ir)
183{
184   (void)ir;
185   return visit_continue_with_parent;
186}
187
188ir_visitor_status
189ir_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
211ir_visitor_status
212ir_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
222ir_visitor_status
223ir_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
234ir_visitor_status
235ir_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
243ir_visitor_status
244ir_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
273struct tree_grafting_info {
274   ir_variable_refcount_visitor *refs;
275   bool progress;
276};
277
278static bool
279try_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
309static void
310tree_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 */
353bool
354do_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