Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4358 | Serge | 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 | |||
57 | namespace { |
||
58 | |||
59 | static bool debug = false; |
||
60 | |||
61 | class ir_tree_grafting_visitor : public ir_hierarchical_visitor { |
||
62 | public: |
||
63 | ir_tree_grafting_visitor(ir_assignment *graft_assign, |
||
64 | ir_variable *graft_var) |
||
65 | { |
||
66 | this->progress = false; |
||
67 | this->graft_assign = graft_assign; |
||
68 | this->graft_var = graft_var; |
||
69 | } |
||
70 | |||
71 | virtual ir_visitor_status visit_leave(class ir_assignment *); |
||
72 | virtual ir_visitor_status visit_enter(class ir_call *); |
||
73 | virtual ir_visitor_status visit_enter(class ir_expression *); |
||
74 | virtual ir_visitor_status visit_enter(class ir_function *); |
||
75 | virtual ir_visitor_status visit_enter(class ir_function_signature *); |
||
76 | virtual ir_visitor_status visit_enter(class ir_if *); |
||
77 | virtual ir_visitor_status visit_enter(class ir_loop *); |
||
78 | virtual ir_visitor_status visit_enter(class ir_swizzle *); |
||
79 | virtual ir_visitor_status visit_enter(class ir_texture *); |
||
80 | |||
81 | ir_visitor_status check_graft(ir_instruction *ir, ir_variable *var); |
||
82 | |||
83 | bool do_graft(ir_rvalue **rvalue); |
||
84 | |||
85 | bool progress; |
||
86 | ir_variable *graft_var; |
||
87 | ir_assignment *graft_assign; |
||
88 | }; |
||
89 | |||
90 | struct find_deref_info { |
||
91 | ir_variable *var; |
||
92 | bool found; |
||
93 | }; |
||
94 | |||
95 | void |
||
96 | dereferences_variable_callback(ir_instruction *ir, void *data) |
||
97 | { |
||
98 | struct find_deref_info *info = (struct find_deref_info *)data; |
||
99 | ir_dereference_variable *deref = ir->as_dereference_variable(); |
||
100 | |||
101 | if (deref && deref->var == info->var) |
||
102 | info->found = true; |
||
103 | } |
||
104 | |||
105 | static bool |
||
106 | dereferences_variable(ir_instruction *ir, ir_variable *var) |
||
107 | { |
||
108 | struct find_deref_info info; |
||
109 | |||
110 | info.var = var; |
||
111 | info.found = false; |
||
112 | |||
113 | visit_tree(ir, dereferences_variable_callback, &info); |
||
114 | |||
115 | return info.found; |
||
116 | } |
||
117 | |||
118 | bool |
||
119 | ir_tree_grafting_visitor::do_graft(ir_rvalue **rvalue) |
||
120 | { |
||
121 | if (!*rvalue) |
||
122 | return false; |
||
123 | |||
124 | ir_dereference_variable *deref = (*rvalue)->as_dereference_variable(); |
||
125 | |||
126 | if (!deref || deref->var != this->graft_var) |
||
127 | return false; |
||
128 | |||
129 | if (debug) { |
||
130 | printf("GRAFTING:\n"); |
||
131 | this->graft_assign->print(); |
||
132 | printf("\n"); |
||
133 | printf("TO:\n"); |
||
134 | (*rvalue)->print(); |
||
135 | printf("\n"); |
||
136 | } |
||
137 | |||
138 | this->graft_assign->remove(); |
||
139 | *rvalue = this->graft_assign->rhs; |
||
140 | |||
141 | this->progress = true; |
||
142 | return true; |
||
143 | } |
||
144 | |||
145 | ir_visitor_status |
||
146 | ir_tree_grafting_visitor::visit_enter(ir_loop *ir) |
||
147 | { |
||
148 | (void)ir; |
||
149 | /* Do not traverse into the body of the loop since that is a |
||
150 | * different basic block. |
||
151 | */ |
||
152 | return visit_stop; |
||
153 | } |
||
154 | |||
155 | /** |
||
156 | * Check if we can continue grafting after writing to a variable. If the |
||
157 | * expression we're trying to graft references the variable, we must stop. |
||
158 | * |
||
159 | * \param ir An instruction that writes to a variable. |
||
160 | * \param var The variable being updated. |
||
161 | */ |
||
162 | ir_visitor_status |
||
163 | ir_tree_grafting_visitor::check_graft(ir_instruction *ir, ir_variable *var) |
||
164 | { |
||
165 | if (dereferences_variable(this->graft_assign->rhs, var)) { |
||
166 | if (debug) { |
||
167 | printf("graft killed by: "); |
||
168 | ir->print(); |
||
169 | printf("\n"); |
||
170 | } |
||
171 | return visit_stop; |
||
172 | } |
||
173 | |||
174 | return visit_continue; |
||
175 | } |
||
176 | |||
177 | ir_visitor_status |
||
178 | ir_tree_grafting_visitor::visit_leave(ir_assignment *ir) |
||
179 | { |
||
180 | if (do_graft(&ir->rhs) || |
||
181 | do_graft(&ir->condition)) |
||
182 | return visit_stop; |
||
183 | |||
184 | /* If this assignment updates a variable used in the assignment |
||
185 | * we're trying to graft, then we're done. |
||
186 | */ |
||
187 | return check_graft(ir, ir->lhs->variable_referenced()); |
||
188 | } |
||
189 | |||
190 | ir_visitor_status |
||
191 | ir_tree_grafting_visitor::visit_enter(ir_function *ir) |
||
192 | { |
||
193 | (void) ir; |
||
194 | return visit_continue_with_parent; |
||
195 | } |
||
196 | |||
197 | ir_visitor_status |
||
198 | ir_tree_grafting_visitor::visit_enter(ir_function_signature *ir) |
||
199 | { |
||
200 | (void)ir; |
||
201 | return visit_continue_with_parent; |
||
202 | } |
||
203 | |||
204 | ir_visitor_status |
||
205 | ir_tree_grafting_visitor::visit_enter(ir_call *ir) |
||
206 | { |
||
207 | exec_list_iterator sig_iter = ir->callee->parameters.iterator(); |
||
208 | /* Reminder: iterating ir_call iterates its parameters. */ |
||
209 | foreach_iter(exec_list_iterator, iter, *ir) { |
||
210 | ir_variable *sig_param = (ir_variable *)sig_iter.get(); |
||
211 | ir_rvalue *ir = (ir_rvalue *)iter.get(); |
||
212 | ir_rvalue *new_ir = ir; |
||
213 | |||
214 | if (sig_param->mode != ir_var_function_in |
||
215 | && sig_param->mode != ir_var_const_in) { |
||
216 | if (check_graft(ir, sig_param) == visit_stop) |
||
217 | return visit_stop; |
||
218 | continue; |
||
219 | } |
||
220 | |||
221 | if (do_graft(&new_ir)) { |
||
222 | ir->replace_with(new_ir); |
||
223 | return visit_stop; |
||
224 | } |
||
225 | sig_iter.next(); |
||
226 | } |
||
227 | |||
228 | if (ir->return_deref && check_graft(ir, ir->return_deref->var) == visit_stop) |
||
229 | return visit_stop; |
||
230 | |||
231 | return visit_continue; |
||
232 | } |
||
233 | |||
234 | ir_visitor_status |
||
235 | ir_tree_grafting_visitor::visit_enter(ir_expression *ir) |
||
236 | { |
||
237 | for (unsigned int i = 0; i < ir->get_num_operands(); i++) { |
||
238 | if (do_graft(&ir->operands[i])) |
||
239 | return visit_stop; |
||
240 | } |
||
241 | |||
242 | return visit_continue; |
||
243 | } |
||
244 | |||
245 | ir_visitor_status |
||
246 | ir_tree_grafting_visitor::visit_enter(ir_if *ir) |
||
247 | { |
||
248 | if (do_graft(&ir->condition)) |
||
249 | return visit_stop; |
||
250 | |||
251 | /* Do not traverse into the body of the if-statement since that is a |
||
252 | * different basic block. |
||
253 | */ |
||
254 | return visit_continue_with_parent; |
||
255 | } |
||
256 | |||
257 | ir_visitor_status |
||
258 | ir_tree_grafting_visitor::visit_enter(ir_swizzle *ir) |
||
259 | { |
||
260 | if (do_graft(&ir->val)) |
||
261 | return visit_stop; |
||
262 | |||
263 | return visit_continue; |
||
264 | } |
||
265 | |||
266 | ir_visitor_status |
||
267 | ir_tree_grafting_visitor::visit_enter(ir_texture *ir) |
||
268 | { |
||
269 | if (do_graft(&ir->coordinate) || |
||
270 | do_graft(&ir->projector) || |
||
271 | do_graft(&ir->offset) || |
||
272 | do_graft(&ir->shadow_comparitor)) |
||
273 | return visit_stop; |
||
274 | |||
275 | switch (ir->op) { |
||
276 | case ir_tex: |
||
277 | case ir_lod: |
||
278 | break; |
||
279 | case ir_txb: |
||
280 | if (do_graft(&ir->lod_info.bias)) |
||
281 | return visit_stop; |
||
282 | break; |
||
283 | case ir_txf: |
||
284 | case ir_txl: |
||
285 | case ir_txs: |
||
286 | if (do_graft(&ir->lod_info.lod)) |
||
287 | return visit_stop; |
||
288 | break; |
||
289 | case ir_txf_ms: |
||
290 | if (do_graft(&ir->lod_info.sample_index)) |
||
291 | return visit_stop; |
||
292 | break; |
||
293 | case ir_txd: |
||
294 | if (do_graft(&ir->lod_info.grad.dPdx) || |
||
295 | do_graft(&ir->lod_info.grad.dPdy)) |
||
296 | return visit_stop; |
||
297 | break; |
||
298 | } |
||
299 | |||
300 | return visit_continue; |
||
301 | } |
||
302 | |||
303 | struct tree_grafting_info { |
||
304 | ir_variable_refcount_visitor *refs; |
||
305 | bool progress; |
||
306 | }; |
||
307 | |||
308 | static bool |
||
309 | try_tree_grafting(ir_assignment *start, |
||
310 | ir_variable *lhs_var, |
||
311 | ir_instruction *bb_last) |
||
312 | { |
||
313 | ir_tree_grafting_visitor v(start, lhs_var); |
||
314 | |||
315 | if (debug) { |
||
316 | printf("trying to graft: "); |
||
317 | lhs_var->print(); |
||
318 | printf("\n"); |
||
319 | } |
||
320 | |||
321 | for (ir_instruction *ir = (ir_instruction *)start->next; |
||
322 | ir != bb_last->next; |
||
323 | ir = (ir_instruction *)ir->next) { |
||
324 | |||
325 | if (debug) { |
||
326 | printf("- "); |
||
327 | ir->print(); |
||
328 | printf("\n"); |
||
329 | } |
||
330 | |||
331 | ir_visitor_status s = ir->accept(&v); |
||
332 | if (s == visit_stop) |
||
333 | return v.progress; |
||
334 | } |
||
335 | |||
336 | return false; |
||
337 | } |
||
338 | |||
339 | static void |
||
340 | tree_grafting_basic_block(ir_instruction *bb_first, |
||
341 | ir_instruction *bb_last, |
||
342 | void *data) |
||
343 | { |
||
344 | struct tree_grafting_info *info = (struct tree_grafting_info *)data; |
||
345 | ir_instruction *ir, *next; |
||
346 | |||
347 | for (ir = bb_first, next = (ir_instruction *)ir->next; |
||
348 | ir != bb_last->next; |
||
349 | ir = next, next = (ir_instruction *)ir->next) { |
||
350 | ir_assignment *assign = ir->as_assignment(); |
||
351 | |||
352 | if (!assign) |
||
353 | continue; |
||
354 | |||
355 | ir_variable *lhs_var = assign->whole_variable_written(); |
||
356 | if (!lhs_var) |
||
357 | continue; |
||
358 | |||
359 | if (lhs_var->mode == ir_var_function_out || |
||
360 | lhs_var->mode == ir_var_function_inout || |
||
361 | lhs_var->mode == ir_var_shader_out) |
||
362 | continue; |
||
363 | |||
364 | ir_variable_refcount_entry *entry = info->refs->get_variable_entry(lhs_var); |
||
365 | |||
366 | if (!entry->declaration || |
||
367 | entry->assigned_count != 1 || |
||
368 | entry->referenced_count != 2) |
||
369 | continue; |
||
370 | |||
371 | assert(assign == entry->assign); |
||
372 | |||
373 | /* Found a possibly graftable assignment. Now, walk through the |
||
374 | * rest of the BB seeing if the deref is here, and if nothing interfered with |
||
375 | * pasting its expression's values in between. |
||
376 | */ |
||
377 | info->progress |= try_tree_grafting(assign, lhs_var, bb_last); |
||
378 | } |
||
379 | } |
||
380 | |||
381 | } /* unnamed namespace */ |
||
382 | |||
383 | /** |
||
384 | * Does a copy propagation pass on the code present in the instruction stream. |
||
385 | */ |
||
386 | bool |
||
387 | do_tree_grafting(exec_list *instructions) |
||
388 | { |
||
389 | ir_variable_refcount_visitor refs; |
||
390 | struct tree_grafting_info info; |
||
391 | |||
392 | info.progress = false; |
||
393 | info.refs = &refs; |
||
394 | |||
395 | visit_list_elements(info.refs, instructions); |
||
396 | |||
397 | call_for_basic_blocks(instructions, tree_grafting_basic_block, &info); |
||
398 | |||
399 | return info.progress; |
||
400 | }> |