Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
5563 | 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 | #include "glsl_types.h" |
||
25 | #include "loop_analysis.h" |
||
26 | #include "ir_hierarchical_visitor.h" |
||
27 | |||
28 | static bool is_loop_terminator(ir_if *ir); |
||
29 | |||
30 | static bool all_expression_operands_are_loop_constant(ir_rvalue *, |
||
31 | hash_table *); |
||
32 | |||
33 | static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *); |
||
34 | |||
35 | |||
36 | loop_state::loop_state() |
||
37 | { |
||
38 | this->ht = hash_table_ctor(0, hash_table_pointer_hash, |
||
39 | hash_table_pointer_compare); |
||
40 | this->mem_ctx = ralloc_context(NULL); |
||
41 | this->loop_found = false; |
||
42 | } |
||
43 | |||
44 | |||
45 | loop_state::~loop_state() |
||
46 | { |
||
47 | hash_table_dtor(this->ht); |
||
48 | ralloc_free(this->mem_ctx); |
||
49 | } |
||
50 | |||
51 | |||
52 | loop_variable_state * |
||
53 | loop_state::insert(ir_loop *ir) |
||
54 | { |
||
55 | loop_variable_state *ls = new(this->mem_ctx) loop_variable_state; |
||
56 | |||
57 | hash_table_insert(this->ht, ls, ir); |
||
58 | this->loop_found = true; |
||
59 | |||
60 | return ls; |
||
61 | } |
||
62 | |||
63 | |||
64 | loop_variable_state * |
||
65 | loop_state::get(const ir_loop *ir) |
||
66 | { |
||
67 | return (loop_variable_state *) hash_table_find(this->ht, ir); |
||
68 | } |
||
69 | |||
70 | |||
71 | loop_variable * |
||
72 | loop_variable_state::get(const ir_variable *ir) |
||
73 | { |
||
74 | return (loop_variable *) hash_table_find(this->var_hash, ir); |
||
75 | } |
||
76 | |||
77 | |||
78 | loop_variable * |
||
79 | loop_variable_state::insert(ir_variable *var) |
||
80 | { |
||
81 | void *mem_ctx = ralloc_parent(this); |
||
82 | loop_variable *lv = rzalloc(mem_ctx, loop_variable); |
||
83 | |||
84 | lv->var = var; |
||
85 | |||
86 | hash_table_insert(this->var_hash, lv, lv->var); |
||
87 | this->variables.push_tail(lv); |
||
88 | |||
89 | return lv; |
||
90 | } |
||
91 | |||
92 | |||
93 | loop_terminator * |
||
94 | loop_variable_state::insert(ir_if *if_stmt) |
||
95 | { |
||
96 | void *mem_ctx = ralloc_parent(this); |
||
97 | loop_terminator *t = rzalloc(mem_ctx, loop_terminator); |
||
98 | |||
99 | t->ir = if_stmt; |
||
100 | this->terminators.push_tail(t); |
||
101 | |||
102 | return t; |
||
103 | } |
||
104 | |||
105 | |||
106 | class loop_analysis : public ir_hierarchical_visitor { |
||
107 | public: |
||
108 | loop_analysis(loop_state *loops); |
||
109 | |||
110 | virtual ir_visitor_status visit(ir_loop_jump *); |
||
111 | virtual ir_visitor_status visit(ir_dereference_variable *); |
||
112 | |||
113 | virtual ir_visitor_status visit_enter(ir_call *); |
||
114 | |||
115 | virtual ir_visitor_status visit_enter(ir_loop *); |
||
116 | virtual ir_visitor_status visit_leave(ir_loop *); |
||
117 | virtual ir_visitor_status visit_enter(ir_assignment *); |
||
118 | virtual ir_visitor_status visit_leave(ir_assignment *); |
||
119 | virtual ir_visitor_status visit_enter(ir_if *); |
||
120 | virtual ir_visitor_status visit_leave(ir_if *); |
||
121 | |||
122 | loop_state *loops; |
||
123 | |||
124 | int if_statement_depth; |
||
125 | |||
126 | ir_assignment *current_assignment; |
||
127 | |||
128 | exec_list state; |
||
129 | }; |
||
130 | |||
131 | |||
132 | loop_analysis::loop_analysis(loop_state *loops) |
||
133 | : loops(loops), if_statement_depth(0), current_assignment(NULL) |
||
134 | { |
||
135 | /* empty */ |
||
136 | } |
||
137 | |||
138 | |||
139 | ir_visitor_status |
||
140 | loop_analysis::visit(ir_loop_jump *ir) |
||
141 | { |
||
142 | (void) ir; |
||
143 | |||
144 | assert(!this->state.is_empty()); |
||
145 | |||
146 | loop_variable_state *const ls = |
||
147 | (loop_variable_state *) this->state.get_head(); |
||
148 | |||
149 | ls->num_loop_jumps++; |
||
150 | |||
151 | return visit_continue; |
||
152 | } |
||
153 | |||
154 | |||
155 | ir_visitor_status |
||
156 | loop_analysis::visit_enter(ir_call *ir) |
||
157 | { |
||
158 | /* If we're not somewhere inside a loop, there's nothing to do. */ |
||
159 | if (this->state.is_empty()) |
||
160 | return visit_continue; |
||
161 | |||
162 | loop_variable_state *const ls = |
||
163 | (loop_variable_state *) this->state.get_head(); |
||
164 | |||
165 | ls->contains_calls = true; |
||
166 | return visit_continue_with_parent; |
||
167 | } |
||
168 | |||
169 | |||
170 | ir_visitor_status |
||
171 | loop_analysis::visit(ir_dereference_variable *ir) |
||
172 | { |
||
173 | /* If we're not somewhere inside a loop, there's nothing to do. |
||
174 | */ |
||
175 | if (this->state.is_empty()) |
||
176 | return visit_continue; |
||
177 | |||
178 | loop_variable_state *const ls = |
||
179 | (loop_variable_state *) this->state.get_head(); |
||
180 | |||
181 | ir_variable *var = ir->variable_referenced(); |
||
182 | loop_variable *lv = ls->get(var); |
||
183 | |||
184 | if (lv == NULL) { |
||
185 | lv = ls->insert(var); |
||
186 | lv->read_before_write = !this->in_assignee; |
||
187 | } |
||
188 | |||
189 | if (this->in_assignee) { |
||
190 | assert(this->current_assignment != NULL); |
||
191 | |||
192 | lv->conditional_assignment = (this->if_statement_depth > 0) |
||
193 | || (this->current_assignment->condition != NULL); |
||
194 | |||
195 | if (lv->first_assignment == NULL) { |
||
196 | assert(lv->num_assignments == 0); |
||
197 | |||
198 | lv->first_assignment = this->current_assignment; |
||
199 | } |
||
200 | |||
201 | lv->num_assignments++; |
||
202 | } else if (lv->first_assignment == this->current_assignment) { |
||
203 | /* This catches the case where the variable is used in the RHS of an |
||
204 | * assignment where it is also in the LHS. |
||
205 | */ |
||
206 | lv->read_before_write = true; |
||
207 | } |
||
208 | |||
209 | return visit_continue; |
||
210 | } |
||
211 | |||
212 | ir_visitor_status |
||
213 | loop_analysis::visit_enter(ir_loop *ir) |
||
214 | { |
||
215 | loop_variable_state *ls = this->loops->insert(ir); |
||
216 | this->state.push_head(ls); |
||
217 | |||
218 | return visit_continue; |
||
219 | } |
||
220 | |||
221 | ir_visitor_status |
||
222 | loop_analysis::visit_leave(ir_loop *ir) |
||
223 | { |
||
224 | loop_variable_state *const ls = |
||
225 | (loop_variable_state *) this->state.pop_head(); |
||
226 | |||
227 | /* Function calls may contain side effects. These could alter any of our |
||
228 | * variables in ways that cannot be known, and may even terminate shader |
||
229 | * execution (say, calling discard in the fragment shader). So we can't |
||
230 | * rely on any of our analysis about assignments to variables. |
||
231 | * |
||
232 | * We could perform some conservative analysis (prove there's no statically |
||
233 | * possible assignment, etc.) but it isn't worth it for now; function |
||
234 | * inlining will allow us to unroll loops anyway. |
||
235 | */ |
||
236 | if (ls->contains_calls) |
||
237 | return visit_continue; |
||
238 | |||
239 | foreach_list(node, &ir->body_instructions) { |
||
240 | /* Skip over declarations at the start of a loop. |
||
241 | */ |
||
242 | if (((ir_instruction *) node)->as_variable()) |
||
243 | continue; |
||
244 | |||
245 | ir_if *if_stmt = ((ir_instruction *) node)->as_if(); |
||
246 | |||
247 | if ((if_stmt != NULL) && is_loop_terminator(if_stmt)) |
||
248 | ls->insert(if_stmt); |
||
249 | else |
||
250 | break; |
||
251 | } |
||
252 | |||
253 | |||
254 | foreach_list_safe(node, &ls->variables) { |
||
255 | loop_variable *lv = (loop_variable *) node; |
||
256 | |||
257 | /* Move variables that are already marked as being loop constant to |
||
258 | * a separate list. These trivially don't need to be tested. |
||
259 | */ |
||
260 | if (lv->is_loop_constant()) { |
||
261 | lv->remove(); |
||
262 | ls->constants.push_tail(lv); |
||
263 | } |
||
264 | } |
||
265 | |||
266 | /* Each variable assigned in the loop that isn't already marked as being loop |
||
267 | * constant might still be loop constant. The requirements at this point |
||
268 | * are: |
||
269 | * |
||
270 | * - Variable is written before it is read. |
||
271 | * |
||
272 | * - Only one assignment to the variable. |
||
273 | * |
||
274 | * - All operands on the RHS of the assignment are also loop constants. |
||
275 | * |
||
276 | * The last requirement is the reason for the progress loop. A variable |
||
277 | * marked as a loop constant on one pass may allow other variables to be |
||
278 | * marked as loop constant on following passes. |
||
279 | */ |
||
280 | bool progress; |
||
281 | do { |
||
282 | progress = false; |
||
283 | |||
284 | foreach_list_safe(node, &ls->variables) { |
||
285 | loop_variable *lv = (loop_variable *) node; |
||
286 | |||
287 | if (lv->conditional_assignment || (lv->num_assignments > 1)) |
||
288 | continue; |
||
289 | |||
290 | /* Process the RHS of the assignment. If all of the variables |
||
291 | * accessed there are loop constants, then add this |
||
292 | */ |
||
293 | ir_rvalue *const rhs = lv->first_assignment->rhs; |
||
294 | if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) { |
||
295 | lv->rhs_clean = true; |
||
296 | |||
297 | if (lv->is_loop_constant()) { |
||
298 | progress = true; |
||
299 | |||
300 | lv->remove(); |
||
301 | ls->constants.push_tail(lv); |
||
302 | } |
||
303 | } |
||
304 | } |
||
305 | } while (progress); |
||
306 | |||
307 | /* The remaining variables that are not loop invariant might be loop |
||
308 | * induction variables. |
||
309 | */ |
||
310 | foreach_list_safe(node, &ls->variables) { |
||
311 | loop_variable *lv = (loop_variable *) node; |
||
312 | |||
313 | /* If there is more than one assignment to a variable, it cannot be a |
||
314 | * loop induction variable. This isn't strictly true, but this is a |
||
315 | * very simple induction variable detector, and it can't handle more |
||
316 | * complex cases. |
||
317 | */ |
||
318 | if (lv->num_assignments > 1) |
||
319 | continue; |
||
320 | |||
321 | /* All of the variables with zero assignments in the loop are loop |
||
322 | * invariant, and they should have already been filtered out. |
||
323 | */ |
||
324 | assert(lv->num_assignments == 1); |
||
325 | assert(lv->first_assignment != NULL); |
||
326 | |||
327 | /* The assignmnet to the variable in the loop must be unconditional. |
||
328 | */ |
||
329 | if (lv->conditional_assignment) |
||
330 | continue; |
||
331 | |||
332 | /* Basic loop induction variables have a single assignment in the loop |
||
333 | * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a |
||
334 | * loop invariant. |
||
335 | */ |
||
336 | ir_rvalue *const inc = |
||
337 | get_basic_induction_increment(lv->first_assignment, ls->var_hash); |
||
338 | if (inc != NULL) { |
||
339 | lv->iv_scale = NULL; |
||
340 | lv->biv = lv->var; |
||
341 | lv->increment = inc; |
||
342 | |||
343 | lv->remove(); |
||
344 | ls->induction_variables.push_tail(lv); |
||
345 | } |
||
346 | } |
||
347 | |||
348 | return visit_continue; |
||
349 | } |
||
350 | |||
351 | ir_visitor_status |
||
352 | loop_analysis::visit_enter(ir_if *ir) |
||
353 | { |
||
354 | (void) ir; |
||
355 | |||
356 | if (!this->state.is_empty()) |
||
357 | this->if_statement_depth++; |
||
358 | |||
359 | return visit_continue; |
||
360 | } |
||
361 | |||
362 | ir_visitor_status |
||
363 | loop_analysis::visit_leave(ir_if *ir) |
||
364 | { |
||
365 | (void) ir; |
||
366 | |||
367 | if (!this->state.is_empty()) |
||
368 | this->if_statement_depth--; |
||
369 | |||
370 | return visit_continue; |
||
371 | } |
||
372 | |||
373 | ir_visitor_status |
||
374 | loop_analysis::visit_enter(ir_assignment *ir) |
||
375 | { |
||
376 | /* If we're not somewhere inside a loop, there's nothing to do. |
||
377 | */ |
||
378 | if (this->state.is_empty()) |
||
379 | return visit_continue_with_parent; |
||
380 | |||
381 | this->current_assignment = ir; |
||
382 | |||
383 | return visit_continue; |
||
384 | } |
||
385 | |||
386 | ir_visitor_status |
||
387 | loop_analysis::visit_leave(ir_assignment *ir) |
||
388 | { |
||
389 | /* Since the visit_enter exits with visit_continue_with_parent for this |
||
390 | * case, the loop state stack should never be empty here. |
||
391 | */ |
||
392 | assert(!this->state.is_empty()); |
||
393 | |||
394 | assert(this->current_assignment == ir); |
||
395 | this->current_assignment = NULL; |
||
396 | |||
397 | return visit_continue; |
||
398 | } |
||
399 | |||
400 | |||
401 | class examine_rhs : public ir_hierarchical_visitor { |
||
402 | public: |
||
403 | examine_rhs(hash_table *loop_variables) |
||
404 | { |
||
405 | this->only_uses_loop_constants = true; |
||
406 | this->loop_variables = loop_variables; |
||
407 | } |
||
408 | |||
409 | virtual ir_visitor_status visit(ir_dereference_variable *ir) |
||
410 | { |
||
411 | loop_variable *lv = |
||
412 | (loop_variable *) hash_table_find(this->loop_variables, ir->var); |
||
413 | |||
414 | assert(lv != NULL); |
||
415 | |||
416 | if (lv->is_loop_constant()) { |
||
417 | return visit_continue; |
||
418 | } else { |
||
419 | this->only_uses_loop_constants = false; |
||
420 | return visit_stop; |
||
421 | } |
||
422 | } |
||
423 | |||
424 | hash_table *loop_variables; |
||
425 | bool only_uses_loop_constants; |
||
426 | }; |
||
427 | |||
428 | |||
429 | bool |
||
430 | all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables) |
||
431 | { |
||
432 | examine_rhs v(variables); |
||
433 | |||
434 | ir->accept(&v); |
||
435 | |||
436 | return v.only_uses_loop_constants; |
||
437 | } |
||
438 | |||
439 | |||
440 | ir_rvalue * |
||
441 | get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) |
||
442 | { |
||
443 | /* The RHS must be a binary expression. |
||
444 | */ |
||
445 | ir_expression *const rhs = ir->rhs->as_expression(); |
||
446 | if ((rhs == NULL) |
||
447 | || ((rhs->operation != ir_binop_add) |
||
448 | && (rhs->operation != ir_binop_sub))) |
||
449 | return NULL; |
||
450 | |||
451 | /* One of the of operands of the expression must be the variable assigned. |
||
452 | * If the operation is subtraction, the variable in question must be the |
||
453 | * "left" operand. |
||
454 | */ |
||
455 | ir_variable *const var = ir->lhs->variable_referenced(); |
||
456 | |||
457 | ir_variable *const op0 = rhs->operands[0]->variable_referenced(); |
||
458 | ir_variable *const op1 = rhs->operands[1]->variable_referenced(); |
||
459 | |||
460 | if (((op0 != var) && (op1 != var)) |
||
461 | || ((op1 == var) && (rhs->operation == ir_binop_sub))) |
||
462 | return NULL; |
||
463 | |||
464 | ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0]; |
||
465 | |||
466 | if (inc->as_constant() == NULL) { |
||
467 | ir_variable *const inc_var = inc->variable_referenced(); |
||
468 | if (inc_var != NULL) { |
||
469 | loop_variable *lv = |
||
470 | (loop_variable *) hash_table_find(var_hash, inc_var); |
||
471 | |||
472 | if (!lv->is_loop_constant()) |
||
473 | inc = NULL; |
||
474 | } else |
||
475 | inc = NULL; |
||
476 | } |
||
477 | |||
478 | if ((inc != NULL) && (rhs->operation == ir_binop_sub)) { |
||
479 | void *mem_ctx = ralloc_parent(ir); |
||
480 | |||
481 | inc = new(mem_ctx) ir_expression(ir_unop_neg, |
||
482 | inc->type, |
||
483 | inc->clone(mem_ctx, NULL), |
||
484 | NULL); |
||
485 | } |
||
486 | |||
487 | return inc; |
||
488 | } |
||
489 | |||
490 | |||
491 | /** |
||
492 | * Detect whether an if-statement is a loop terminating condition |
||
493 | * |
||
494 | * Detects if-statements of the form |
||
495 | * |
||
496 | * (if (expression bool ...) (break)) |
||
497 | */ |
||
498 | bool |
||
499 | is_loop_terminator(ir_if *ir) |
||
500 | { |
||
501 | if (!ir->else_instructions.is_empty()) |
||
502 | return false; |
||
503 | |||
504 | ir_instruction *const inst = |
||
505 | (ir_instruction *) ir->then_instructions.get_head(); |
||
506 | if (inst == NULL) |
||
507 | return false; |
||
508 | |||
509 | if (inst->ir_type != ir_type_loop_jump) |
||
510 | return false; |
||
511 | |||
512 | ir_loop_jump *const jump = (ir_loop_jump *) inst; |
||
513 | if (jump->mode != ir_loop_jump::jump_break) |
||
514 | return false; |
||
515 | |||
516 | return true; |
||
517 | } |
||
518 | |||
519 | |||
520 | loop_state * |
||
521 | analyze_loop_variables(exec_list *instructions) |
||
522 | { |
||
523 | loop_state *loops = new loop_state; |
||
524 | loop_analysis v(loops); |
||
525 | |||
526 | v.run(instructions); |
||
527 | return v.loops; |
||
528 | } |