Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1901 | 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_copy_propagation.cpp |
||
26 | * |
||
27 | * Moves usage of recently-copied variables to the previous copy of |
||
28 | * the variable. |
||
29 | * |
||
30 | * This should reduce the number of MOV instructions in the generated |
||
31 | * programs unless copy propagation is also done on the LIR, and may |
||
32 | * help anyway by triggering other optimizations that live in the HIR. |
||
33 | */ |
||
34 | |||
35 | #include "ir.h" |
||
36 | #include "ir_visitor.h" |
||
37 | #include "ir_basic_block.h" |
||
38 | #include "ir_optimization.h" |
||
39 | #include "glsl_types.h" |
||
40 | |||
41 | class acp_entry : public exec_node |
||
42 | { |
||
43 | public: |
||
44 | acp_entry(ir_variable *lhs, ir_variable *rhs) |
||
45 | { |
||
46 | assert(lhs); |
||
47 | assert(rhs); |
||
48 | this->lhs = lhs; |
||
49 | this->rhs = rhs; |
||
50 | } |
||
51 | |||
52 | ir_variable *lhs; |
||
53 | ir_variable *rhs; |
||
54 | }; |
||
55 | |||
56 | |||
57 | class kill_entry : public exec_node |
||
58 | { |
||
59 | public: |
||
60 | kill_entry(ir_variable *var) |
||
61 | { |
||
62 | assert(var); |
||
63 | this->var = var; |
||
64 | } |
||
65 | |||
66 | ir_variable *var; |
||
67 | }; |
||
68 | |||
69 | class ir_copy_propagation_visitor : public ir_hierarchical_visitor { |
||
70 | public: |
||
71 | ir_copy_propagation_visitor() |
||
72 | { |
||
73 | progress = false; |
||
74 | mem_ctx = ralloc_context(0); |
||
75 | this->acp = new(mem_ctx) exec_list; |
||
76 | this->kills = new(mem_ctx) exec_list; |
||
77 | } |
||
78 | ~ir_copy_propagation_visitor() |
||
79 | { |
||
80 | ralloc_free(mem_ctx); |
||
81 | } |
||
82 | |||
83 | virtual ir_visitor_status visit(class ir_dereference_variable *); |
||
84 | virtual ir_visitor_status visit_enter(class ir_loop *); |
||
85 | virtual ir_visitor_status visit_enter(class ir_function_signature *); |
||
86 | virtual ir_visitor_status visit_enter(class ir_function *); |
||
87 | virtual ir_visitor_status visit_leave(class ir_assignment *); |
||
88 | virtual ir_visitor_status visit_enter(class ir_call *); |
||
89 | virtual ir_visitor_status visit_enter(class ir_if *); |
||
90 | |||
91 | void add_copy(ir_assignment *ir); |
||
92 | void kill(ir_variable *ir); |
||
93 | void handle_if_block(exec_list *instructions); |
||
94 | |||
95 | /** List of acp_entry: The available copies to propagate */ |
||
96 | exec_list *acp; |
||
97 | /** |
||
98 | * List of kill_entry: The variables whose values were killed in this |
||
99 | * block. |
||
100 | */ |
||
101 | exec_list *kills; |
||
102 | |||
103 | bool progress; |
||
104 | |||
105 | bool killed_all; |
||
106 | |||
107 | void *mem_ctx; |
||
108 | }; |
||
109 | |||
110 | ir_visitor_status |
||
111 | ir_copy_propagation_visitor::visit_enter(ir_function_signature *ir) |
||
112 | { |
||
113 | /* Treat entry into a function signature as a completely separate |
||
114 | * block. Any instructions at global scope will be shuffled into |
||
115 | * main() at link time, so they're irrelevant to us. |
||
116 | */ |
||
117 | exec_list *orig_acp = this->acp; |
||
118 | exec_list *orig_kills = this->kills; |
||
119 | bool orig_killed_all = this->killed_all; |
||
120 | |||
121 | this->acp = new(mem_ctx) exec_list; |
||
122 | this->kills = new(mem_ctx) exec_list; |
||
123 | this->killed_all = false; |
||
124 | |||
125 | visit_list_elements(this, &ir->body); |
||
126 | |||
127 | this->kills = orig_kills; |
||
128 | this->acp = orig_acp; |
||
129 | this->killed_all = orig_killed_all; |
||
130 | |||
131 | return visit_continue_with_parent; |
||
132 | } |
||
133 | |||
134 | ir_visitor_status |
||
135 | ir_copy_propagation_visitor::visit_leave(ir_assignment *ir) |
||
136 | { |
||
137 | kill(ir->lhs->variable_referenced()); |
||
138 | |||
139 | add_copy(ir); |
||
140 | |||
141 | return visit_continue; |
||
142 | } |
||
143 | |||
144 | ir_visitor_status |
||
145 | ir_copy_propagation_visitor::visit_enter(ir_function *ir) |
||
146 | { |
||
147 | (void) ir; |
||
148 | return visit_continue; |
||
149 | } |
||
150 | |||
151 | /** |
||
152 | * Replaces dereferences of ACP RHS variables with ACP LHS variables. |
||
153 | * |
||
154 | * This is where the actual copy propagation occurs. Note that the |
||
155 | * rewriting of ir_dereference means that the ir_dereference instance |
||
156 | * must not be shared by multiple IR operations! |
||
157 | */ |
||
158 | ir_visitor_status |
||
159 | ir_copy_propagation_visitor::visit(ir_dereference_variable *ir) |
||
160 | { |
||
161 | if (this->in_assignee) |
||
162 | return visit_continue; |
||
163 | |||
164 | ir_variable *var = ir->var; |
||
165 | |||
166 | foreach_iter(exec_list_iterator, iter, *this->acp) { |
||
167 | acp_entry *entry = (acp_entry *)iter.get(); |
||
168 | |||
169 | if (var == entry->lhs) { |
||
170 | ir->var = entry->rhs; |
||
171 | this->progress = true; |
||
172 | break; |
||
173 | } |
||
174 | } |
||
175 | |||
176 | return visit_continue; |
||
177 | } |
||
178 | |||
179 | |||
180 | ir_visitor_status |
||
181 | ir_copy_propagation_visitor::visit_enter(ir_call *ir) |
||
182 | { |
||
183 | /* Do copy propagation on call parameters, but skip any out params */ |
||
184 | exec_list_iterator sig_param_iter = ir->get_callee()->parameters.iterator(); |
||
185 | foreach_iter(exec_list_iterator, iter, ir->actual_parameters) { |
||
186 | ir_variable *sig_param = (ir_variable *)sig_param_iter.get(); |
||
187 | ir_instruction *ir = (ir_instruction *)iter.get(); |
||
188 | if (sig_param->mode != ir_var_out && sig_param->mode != ir_var_inout) { |
||
189 | ir->accept(this); |
||
190 | } |
||
191 | sig_param_iter.next(); |
||
192 | } |
||
193 | |||
194 | /* Since we're unlinked, we don't (necssarily) know the side effects of |
||
195 | * this call. So kill all copies. |
||
196 | */ |
||
197 | acp->make_empty(); |
||
198 | this->killed_all = true; |
||
199 | |||
200 | return visit_continue_with_parent; |
||
201 | } |
||
202 | |||
203 | void |
||
204 | ir_copy_propagation_visitor::handle_if_block(exec_list *instructions) |
||
205 | { |
||
206 | exec_list *orig_acp = this->acp; |
||
207 | exec_list *orig_kills = this->kills; |
||
208 | bool orig_killed_all = this->killed_all; |
||
209 | |||
210 | this->acp = new(mem_ctx) exec_list; |
||
211 | this->kills = new(mem_ctx) exec_list; |
||
212 | this->killed_all = false; |
||
213 | |||
214 | /* Populate the initial acp with a copy of the original */ |
||
215 | foreach_iter(exec_list_iterator, iter, *orig_acp) { |
||
216 | acp_entry *a = (acp_entry *)iter.get(); |
||
217 | this->acp->push_tail(new(this->mem_ctx) acp_entry(a->lhs, a->rhs)); |
||
218 | } |
||
219 | |||
220 | visit_list_elements(this, instructions); |
||
221 | |||
222 | if (this->killed_all) { |
||
223 | orig_acp->make_empty(); |
||
224 | } |
||
225 | |||
226 | exec_list *new_kills = this->kills; |
||
227 | this->kills = orig_kills; |
||
228 | this->acp = orig_acp; |
||
229 | this->killed_all = this->killed_all || orig_killed_all; |
||
230 | |||
231 | foreach_iter(exec_list_iterator, iter, *new_kills) { |
||
232 | kill_entry *k = (kill_entry *)iter.get(); |
||
233 | kill(k->var); |
||
234 | } |
||
235 | } |
||
236 | |||
237 | ir_visitor_status |
||
238 | ir_copy_propagation_visitor::visit_enter(ir_if *ir) |
||
239 | { |
||
240 | ir->condition->accept(this); |
||
241 | |||
242 | handle_if_block(&ir->then_instructions); |
||
243 | handle_if_block(&ir->else_instructions); |
||
244 | |||
245 | /* handle_if_block() already descended into the children. */ |
||
246 | return visit_continue_with_parent; |
||
247 | } |
||
248 | |||
249 | ir_visitor_status |
||
250 | ir_copy_propagation_visitor::visit_enter(ir_loop *ir) |
||
251 | { |
||
252 | exec_list *orig_acp = this->acp; |
||
253 | exec_list *orig_kills = this->kills; |
||
254 | bool orig_killed_all = this->killed_all; |
||
255 | |||
256 | /* FINISHME: For now, the initial acp for loops is totally empty. |
||
257 | * We could go through once, then go through again with the acp |
||
258 | * cloned minus the killed entries after the first run through. |
||
259 | */ |
||
260 | this->acp = new(mem_ctx) exec_list; |
||
261 | this->kills = new(mem_ctx) exec_list; |
||
262 | this->killed_all = false; |
||
263 | |||
264 | visit_list_elements(this, &ir->body_instructions); |
||
265 | |||
266 | if (this->killed_all) { |
||
267 | orig_acp->make_empty(); |
||
268 | } |
||
269 | |||
270 | exec_list *new_kills = this->kills; |
||
271 | this->kills = orig_kills; |
||
272 | this->acp = orig_acp; |
||
273 | this->killed_all = this->killed_all || orig_killed_all; |
||
274 | |||
275 | foreach_iter(exec_list_iterator, iter, *new_kills) { |
||
276 | kill_entry *k = (kill_entry *)iter.get(); |
||
277 | kill(k->var); |
||
278 | } |
||
279 | |||
280 | /* already descended into the children. */ |
||
281 | return visit_continue_with_parent; |
||
282 | } |
||
283 | |||
284 | void |
||
285 | ir_copy_propagation_visitor::kill(ir_variable *var) |
||
286 | { |
||
287 | assert(var != NULL); |
||
288 | |||
289 | /* Remove any entries currently in the ACP for this kill. */ |
||
290 | foreach_iter(exec_list_iterator, iter, *acp) { |
||
291 | acp_entry *entry = (acp_entry *)iter.get(); |
||
292 | |||
293 | if (entry->lhs == var || entry->rhs == var) { |
||
294 | entry->remove(); |
||
295 | } |
||
296 | } |
||
297 | |||
298 | /* Add the LHS variable to the list of killed variables in this block. |
||
299 | */ |
||
300 | this->kills->push_tail(new(this->mem_ctx) kill_entry(var)); |
||
301 | } |
||
302 | |||
303 | /** |
||
304 | * Adds an entry to the available copy list if it's a plain assignment |
||
305 | * of a variable to a variable. |
||
306 | */ |
||
307 | void |
||
308 | ir_copy_propagation_visitor::add_copy(ir_assignment *ir) |
||
309 | { |
||
310 | acp_entry *entry; |
||
311 | |||
312 | if (ir->condition) { |
||
313 | ir_constant *condition = ir->condition->as_constant(); |
||
314 | if (!condition || !condition->value.b[0]) |
||
315 | return; |
||
316 | } |
||
317 | |||
318 | ir_variable *lhs_var = ir->whole_variable_written(); |
||
319 | ir_variable *rhs_var = ir->rhs->whole_variable_referenced(); |
||
320 | |||
321 | if ((lhs_var != NULL) && (rhs_var != NULL)) { |
||
322 | if (lhs_var == rhs_var) { |
||
323 | /* This is a dumb assignment, but we've conveniently noticed |
||
324 | * it here. Removing it now would mess up the loop iteration |
||
325 | * calling us. Just flag it to not execute, and someone else |
||
326 | * will clean up the mess. |
||
327 | */ |
||
328 | ir->condition = new(ralloc_parent(ir)) ir_constant(false); |
||
329 | this->progress = true; |
||
330 | } else { |
||
331 | entry = new(this->mem_ctx) acp_entry(lhs_var, rhs_var); |
||
332 | this->acp->push_tail(entry); |
||
333 | } |
||
334 | } |
||
335 | } |
||
336 | |||
337 | /** |
||
338 | * Does a copy propagation pass on the code present in the instruction stream. |
||
339 | */ |
||
340 | bool |
||
341 | do_copy_propagation(exec_list *instructions) |
||
342 | { |
||
343 | ir_copy_propagation_visitor v; |
||
344 | |||
345 | visit_list_elements(&v, instructions); |
||
346 | |||
347 | return v.progress; |
||
348 | } |