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 #include "ir_variable_refcount.h"
28 #include "util/hash_table.h"
29
30 static bool is_loop_terminator(ir_if *ir);
31
32 static bool all_expression_operands_are_loop_constant(ir_rvalue *,
33 hash_table *);
34
35 static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *);
36
37
38 /**
39 * Record the fact that the given loop variable was referenced inside the loop.
40 *
41 * \arg in_assignee is true if the reference was on the LHS of an assignment.
42 *
43 * \arg in_conditional_code_or_nested_loop is true if the reference occurred
44 * inside an if statement or a nested loop.
45 *
46 * \arg current_assignment is the ir_assignment node that the loop variable is
47 * on the LHS of, if any (ignored if \c in_assignee is false).
48 */
49 void
record_reference(bool in_assignee,bool in_conditional_code_or_nested_loop,ir_assignment * current_assignment)50 loop_variable::record_reference(bool in_assignee,
51 bool in_conditional_code_or_nested_loop,
52 ir_assignment *current_assignment)
53 {
54 if (in_assignee) {
55 assert(current_assignment != NULL);
56
57 if (in_conditional_code_or_nested_loop ||
58 current_assignment->condition != NULL) {
59 this->conditional_or_nested_assignment = true;
60 }
61
62 if (this->first_assignment == NULL) {
63 assert(this->num_assignments == 0);
64
65 this->first_assignment = current_assignment;
66 }
67
68 this->num_assignments++;
69 } else if (this->first_assignment == current_assignment) {
70 /* This catches the case where the variable is used in the RHS of an
71 * assignment where it is also in the LHS.
72 */
73 this->read_before_write = true;
74 }
75 }
76
77
loop_state()78 loop_state::loop_state()
79 {
80 this->ht = hash_table_ctor(0, hash_table_pointer_hash,
81 hash_table_pointer_compare);
82 this->ht_inductors = hash_table_ctor(0, hash_table_pointer_hash,
83 hash_table_pointer_compare);
84 this->ht_non_inductors = hash_table_ctor(0, hash_table_pointer_hash,
85 hash_table_pointer_compare);
86 this->ht_variables = hash_table_ctor(0, hash_table_pointer_hash,
87 hash_table_pointer_compare);
88 this->mem_ctx = ralloc_context(NULL);
89 this->loop_found = false;
90 }
91
92
~loop_state()93 loop_state::~loop_state()
94 {
95 hash_table_dtor(this->ht);
96 hash_table_dtor(this->ht_inductors);
97 hash_table_dtor(this->ht_non_inductors);
98 hash_table_dtor(this->ht_variables);
99 ralloc_free(this->mem_ctx);
100 }
101
102
103 loop_variable_state *
insert(ir_loop * ir)104 loop_state::insert(ir_loop *ir)
105 {
106 loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;
107
108 hash_table_insert(this->ht, ls, ir);
109 this->loop_found = true;
110
111 return ls;
112 }
113
114
115 loop_variable_state *
get(const ir_loop * ir)116 loop_state::get(const ir_loop *ir)
117 {
118 return (loop_variable_state *) hash_table_find(this->ht, ir);
119 }
120
121 loop_variable_state *
get_for_inductor(const ir_variable * ir)122 loop_state::get_for_inductor(const ir_variable *ir)
123 {
124 return (loop_variable_state *) hash_table_find(this->ht_inductors, ir);
125 }
126
127 static void *unreferenced_variable = (void *)1;
128 static void *assigned_variable = (void *)2;
129
130 void
insert_variable(ir_variable * var)131 loop_state::insert_variable(ir_variable *var)
132 {
133 // data starts as 1. If an assignment is seen, it's replaced with 2.
134 // this way we can mark a variable as a non-inductor if it's referenced
135 // other than the first assignment
136 hash_table_insert(this->ht_variables, unreferenced_variable, var);
137 }
138
139 void
reference_variable(ir_variable * var,bool assignment)140 loop_state::reference_variable(ir_variable *var, bool assignment)
141 {
142 void *ref = hash_table_find(this->ht_variables, var);
143
144 // variable declaration was not seen or already discarded, just ignore
145 if (ref == NULL)
146 return;
147
148 if (ref == unreferenced_variable && assignment)
149 {
150 hash_table_replace(this->ht_variables, assigned_variable, var);
151 return;
152 }
153
154 // variable is referenced and not just in an initial assignment,
155 // so it cannot be an inductor
156 hash_table_remove(this->ht_variables, var);
157 hash_table_insert(this->ht_non_inductors, this, var);
158 }
159
160 bool
insert_inductor(loop_variable * loopvar,loop_variable_state * state,ir_loop * loop)161 loop_state::insert_inductor(loop_variable* loopvar, loop_variable_state* state, ir_loop* loop)
162 {
163 ir_variable* var = loopvar->var;
164
165 // Check if this variable is already marked as "sure can't be a private inductor variable"
166 if (hash_table_find(this->ht_non_inductors, var))
167 return false;
168
169 // Check if this variable is used after the loop anywhere. If it is, it can't be a
170 // variable that's private to the loop.
171 ir_variable_refcount_visitor refs;
172 for (exec_node* node = loop->next;
173 !node->is_tail_sentinel();
174 node = node->next)
175 {
176 ir_instruction *ir = (ir_instruction *) node;
177 ir->accept (&refs);
178 if (refs.find_variable_entry(var))
179 {
180 // add to list of "non inductors", so that next loop does not try
181 // to add it as inductor again
182 hash_table_insert(this->ht_non_inductors, state, var);
183 return false;
184 }
185 }
186
187 // Check if this variable is used before the loop anywhere. If it is, it can't be a
188 // variable that's private to the loop.
189 // Skip over the IR that declared the variable or assigned the initial value though.
190 for (exec_node* node = loop->prev;
191 !node->is_head_sentinel();
192 node = node->prev)
193 {
194 ir_instruction *ir = (ir_instruction *) node;
195 if (ir == loopvar->initial_value_ir)
196 continue;
197 if (ir->ir_type == ir_type_variable)
198 continue;
199
200 ir->accept (&refs);
201 if (refs.find_variable_entry(var))
202 {
203 // add to list of "non inductors", so that next loop does not try
204 // to add it as inductor again
205 hash_table_insert(this->ht_non_inductors, state, var);
206 return false;
207 }
208 }
209
210 state->private_induction_variable_count++;
211 hash_table_insert(this->ht_inductors, state, var);
212 return true;
213 }
214
215
216 loop_variable *
get(const ir_variable * ir)217 loop_variable_state::get(const ir_variable *ir)
218 {
219 return (loop_variable *) hash_table_find(this->var_hash, ir);
220 }
221
222
223 loop_variable *
insert(ir_variable * var)224 loop_variable_state::insert(ir_variable *var)
225 {
226 void *mem_ctx = ralloc_parent(this);
227 loop_variable *lv = rzalloc(mem_ctx, loop_variable);
228
229 lv->var = var;
230
231 hash_table_insert(this->var_hash, lv, lv->var);
232 this->variables.push_tail(lv);
233
234 return lv;
235 }
236
237
238 loop_terminator *
insert(ir_if * if_stmt)239 loop_variable_state::insert(ir_if *if_stmt)
240 {
241 void *mem_ctx = ralloc_parent(this);
242 loop_terminator *t = new(mem_ctx) loop_terminator();
243
244 t->ir = if_stmt;
245 this->terminators.push_tail(t);
246
247 return t;
248 }
249
250
251 /**
252 * If the given variable already is recorded in the state for this loop,
253 * return the corresponding loop_variable object that records information
254 * about it.
255 *
256 * Otherwise, create a new loop_variable object to record information about
257 * the variable, and set its \c read_before_write field appropriately based on
258 * \c in_assignee.
259 *
260 * \arg in_assignee is true if this variable was encountered on the LHS of an
261 * assignment.
262 */
263 loop_variable *
get_or_insert(ir_variable * var,bool in_assignee)264 loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee)
265 {
266 loop_variable *lv = this->get(var);
267
268 if (lv == NULL) {
269 lv = this->insert(var);
270 lv->read_before_write = !in_assignee;
271 }
272
273 return lv;
274 }
275
276
277 namespace {
278
279 class loop_analysis : public ir_hierarchical_visitor {
280 public:
281 loop_analysis(loop_state *loops);
282
283 virtual ir_visitor_status visit(ir_loop_jump *);
284 virtual ir_visitor_status visit(ir_dereference_variable *);
285
286 virtual ir_visitor_status visit(ir_variable *);
287
288 virtual ir_visitor_status visit_enter(ir_call *);
289
290 virtual ir_visitor_status visit_enter(ir_loop *);
291 virtual ir_visitor_status visit_leave(ir_loop *);
292 virtual ir_visitor_status visit_enter(ir_assignment *);
293 virtual ir_visitor_status visit_leave(ir_assignment *);
294 virtual ir_visitor_status visit_enter(ir_if *);
295 virtual ir_visitor_status visit_leave(ir_if *);
296
297 void visit_general(ir_instruction *);
298
299 loop_state *loops;
300
301 int if_statement_depth;
302
303 bool first_pass;
304
305 ir_assignment *current_assignment;
306
307 exec_list state;
308 };
309
310 } /* anonymous namespace */
311
loop_enter_callback(class ir_instruction * ir,void * data)312 void loop_enter_callback(class ir_instruction *ir, void *data)
313 {
314 ((loop_analysis *)data)->visit_general(ir);
315 }
316
loop_analysis(loop_state * loops)317 loop_analysis::loop_analysis(loop_state *loops)
318 : loops(loops), if_statement_depth(0), current_assignment(NULL), first_pass(false)
319 {
320 /* empty */
321 data_enter = this;
322 callback_enter = &loop_enter_callback;
323 }
324
325
326 ir_visitor_status
visit(ir_loop_jump * ir)327 loop_analysis::visit(ir_loop_jump *ir)
328 {
329 (void) ir;
330
331 assert(!this->state.is_empty());
332
333 loop_variable_state *const ls =
334 (loop_variable_state *) this->state.get_head();
335
336 ls->num_loop_jumps++;
337
338 return visit_continue;
339 }
340
341
342 ir_visitor_status
visit(ir_variable * var)343 loop_analysis::visit(ir_variable *var)
344 {
345 // if inside a loop, simply continue - we're only interested in variables declared
346 // entirely outside of any loops
347 if (!this->state.is_empty())
348 return visit_continue;
349
350 // In the first pass over the instructions we look at variables declared and
351 // examine their references to determine if they can be an inductor or not
352 // for the second pass
353 if (this->first_pass)
354 loops->insert_variable(var);
355
356 return visit_continue;
357 }
358
359 ir_visitor_status
visit_enter(ir_call *)360 loop_analysis::visit_enter(ir_call *)
361 {
362 /* Mark every loop that we're currently analyzing as containing an ir_call
363 * (even those at outer nesting levels).
364 */
365 foreach_in_list(loop_variable_state, ls, &this->state) {
366 ls->contains_calls = true;
367 }
368
369 return visit_continue_with_parent;
370 }
371
372
373 ir_visitor_status
visit(ir_dereference_variable * ir)374 loop_analysis::visit(ir_dereference_variable *ir)
375 {
376 /* If we're not somewhere inside a loop, just check for
377 * non-inductors
378 */
379 if (this->state.is_empty() || this->first_pass)
380 {
381 if (this->state.is_empty() && this->first_pass)
382 loops->reference_variable(ir->variable_referenced(), this->in_assignee);
383 return visit_continue;
384 }
385
386 bool nested = false;
387
388 foreach_in_list(loop_variable_state, ls, &this->state) {
389 ir_variable *var = ir->variable_referenced();
390 loop_variable *lv = ls->get_or_insert(var, this->in_assignee);
391
392 lv->record_reference(this->in_assignee,
393 nested || this->if_statement_depth > 0,
394 this->current_assignment);
395 nested = true;
396 }
397
398 return visit_continue;
399 }
400
401 ir_visitor_status
visit_enter(ir_loop * ir)402 loop_analysis::visit_enter(ir_loop *ir)
403 {
404 loop_variable_state *ls = this->loops->insert(ir);
405 this->state.push_head(ls);
406
407 return visit_continue;
408 }
409
410 ir_visitor_status
visit_leave(ir_loop * ir)411 loop_analysis::visit_leave(ir_loop *ir)
412 {
413 loop_variable_state *const ls =
414 (loop_variable_state *) this->state.pop_head();
415
416 /* Function calls may contain side effects. These could alter any of our
417 * variables in ways that cannot be known, and may even terminate shader
418 * execution (say, calling discard in the fragment shader). So we can't
419 * rely on any of our analysis about assignments to variables.
420 *
421 * We could perform some conservative analysis (prove there's no statically
422 * possible assignment, etc.) but it isn't worth it for now; function
423 * inlining will allow us to unroll loops anyway.
424 *
425 * We also skip doing any work in the first pass, where we are just identifying
426 * variables that cannot be inductors.
427 */
428 if (ls->contains_calls || this->first_pass)
429 return visit_continue;
430
431 foreach_in_list(ir_instruction, node, &ir->body_instructions) {
432 /* Skip over declarations at the start of a loop.
433 */
434 if (node->as_variable())
435 continue;
436
437 ir_if *if_stmt = ((ir_instruction *) node)->as_if();
438
439 if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
440 ls->insert(if_stmt);
441 else
442 break;
443 }
444
445
446 foreach_in_list_safe(loop_variable, lv, &ls->variables) {
447 ir_variable *var = lv->var;
448 if (var != NULL) {
449 lv->initial_value = find_initial_value(ir, var, &lv->initial_value_ir);
450 }
451 /* Move variables that are already marked as being loop constant to
452 * a separate list. These trivially don't need to be tested.
453 */
454 if (lv->is_loop_constant()) {
455 lv->remove();
456 ls->constants.push_tail(lv);
457 }
458 }
459
460 /* Each variable assigned in the loop that isn't already marked as being loop
461 * constant might still be loop constant. The requirements at this point
462 * are:
463 *
464 * - Variable is written before it is read.
465 *
466 * - Only one assignment to the variable.
467 *
468 * - All operands on the RHS of the assignment are also loop constants.
469 *
470 * The last requirement is the reason for the progress loop. A variable
471 * marked as a loop constant on one pass may allow other variables to be
472 * marked as loop constant on following passes.
473 */
474 bool progress;
475 do {
476 progress = false;
477
478 foreach_in_list_safe(loop_variable, lv, &ls->variables) {
479 if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
480 continue;
481
482 /* Process the RHS of the assignment. If all of the variables
483 * accessed there are loop constants, then add this
484 */
485 ir_rvalue *const rhs = lv->first_assignment->rhs;
486 if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) {
487 lv->rhs_clean = true;
488
489 if (lv->is_loop_constant()) {
490 progress = true;
491
492 lv->remove();
493 ls->constants.push_tail(lv);
494 }
495 }
496 }
497 } while (progress);
498
499 /* The remaining variables that are not loop invariant might be loop
500 * induction variables.
501 */
502 foreach_in_list_safe(loop_variable, lv, &ls->variables) {
503 /* If there is more than one assignment to a variable, it cannot be a
504 * loop induction variable. This isn't strictly true, but this is a
505 * very simple induction variable detector, and it can't handle more
506 * complex cases.
507 */
508 if (lv->num_assignments > 1)
509 continue;
510
511 /* All of the variables with zero assignments in the loop are loop
512 * invariant, and they should have already been filtered out.
513 */
514 assert(lv->num_assignments == 1);
515 assert(lv->first_assignment != NULL);
516
517 /* The assignment to the variable in the loop must be unconditional and
518 * not inside a nested loop.
519 */
520 if (lv->conditional_or_nested_assignment)
521 continue;
522
523 /* Basic loop induction variables have a single assignment in the loop
524 * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
525 * loop invariant.
526 */
527 ir_rvalue *const inc =
528 get_basic_induction_increment(lv->first_assignment, ls->var_hash);
529 if (inc != NULL) {
530 lv->increment = inc;
531
532 if (loops->insert_inductor(lv, ls, ir)) {
533 lv->remove();
534 ls->induction_variables.push_tail(lv);
535 }
536 }
537 }
538
539 /* Search the loop terminating conditions for those of the form 'i < c'
540 * where i is a loop induction variable, c is a constant, and < is any
541 * relative operator. From each of these we can infer an iteration count.
542 * Also figure out which terminator (if any) produces the smallest
543 * iteration count--this is the limiting terminator.
544 */
545 foreach_in_list(loop_terminator, t, &ls->terminators) {
546 ir_if *if_stmt = t->ir;
547
548 /* If-statements can be either 'if (expr)' or 'if (deref)'. We only care
549 * about the former here.
550 */
551 ir_expression *cond = if_stmt->condition->as_expression();
552 if (cond == NULL)
553 continue;
554
555 switch (cond->operation) {
556 case ir_binop_less:
557 case ir_binop_greater:
558 case ir_binop_lequal:
559 case ir_binop_gequal: {
560 /* The expressions that we care about will either be of the form
561 * 'counter < limit' or 'limit < counter'. Figure out which is
562 * which.
563 */
564 ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
565 ir_constant *limit = cond->operands[1]->as_constant();
566 enum ir_expression_operation cmp = cond->operation;
567
568 if (limit == NULL) {
569 counter = cond->operands[1]->as_dereference_variable();
570 limit = cond->operands[0]->as_constant();
571
572 switch (cmp) {
573 case ir_binop_less: cmp = ir_binop_greater; break;
574 case ir_binop_greater: cmp = ir_binop_less; break;
575 case ir_binop_lequal: cmp = ir_binop_gequal; break;
576 case ir_binop_gequal: cmp = ir_binop_lequal; break;
577 default: assert(!"Should not get here.");
578 }
579 }
580
581 if ((counter == NULL) || (limit == NULL))
582 break;
583
584 ir_variable *var = counter->variable_referenced();
585
586 loop_variable *lv = ls->get(var);
587 if (lv != NULL && lv->is_induction_var()) {
588 t->iterations = calculate_iterations(lv->initial_value, limit, lv->increment,
589 cmp);
590
591 if (t->iterations >= 0 &&
592 (ls->limiting_terminator == NULL ||
593 t->iterations < ls->limiting_terminator->iterations)) {
594 ls->limiting_terminator = t;
595 }
596 }
597 break;
598 }
599
600 default:
601 break;
602 }
603 }
604
605 return visit_continue;
606 }
607
608 ir_visitor_status
visit_enter(ir_if * ir)609 loop_analysis::visit_enter(ir_if *ir)
610 {
611 (void) ir;
612
613 if (!this->state.is_empty())
614 this->if_statement_depth++;
615
616 return visit_continue;
617 }
618
619 ir_visitor_status
visit_leave(ir_if * ir)620 loop_analysis::visit_leave(ir_if *ir)
621 {
622 (void) ir;
623
624 if (!this->state.is_empty())
625 this->if_statement_depth--;
626
627 return visit_continue;
628 }
629
630 ir_visitor_status
visit_enter(ir_assignment * ir)631 loop_analysis::visit_enter(ir_assignment *ir)
632 {
633 /* If we're not somewhere inside a loop, there's nothing to do.
634 */
635 if (this->state.is_empty())
636 return visit_continue;
637
638 this->current_assignment = ir;
639
640 return visit_continue;
641 }
642
643 ir_visitor_status
visit_leave(ir_assignment * ir)644 loop_analysis::visit_leave(ir_assignment *ir)
645 {
646 if (this->state.is_empty())
647 return visit_continue;
648
649 assert(this->current_assignment == ir);
650 this->current_assignment = NULL;
651
652 return visit_continue;
653 }
654
655 void
visit_general(ir_instruction * ir)656 loop_analysis::visit_general(ir_instruction *ir)
657 {
658 /* If we're inside a loop, we can't start marking things as non-inductors
659 * Likewise in the second pass we've done all this work, so return early
660 */
661 if (!this->state.is_empty() || !this->first_pass)
662 return;
663
664 ir_variable_refcount_visitor refs;
665 ir->accept (&refs);
666
667 struct hash_entry *referenced_var;
668 hash_table_foreach (refs.ht, referenced_var) {
669 ir_variable *var = (ir_variable *)referenced_var->key;
670 loops->reference_variable(var, false);
671 }
672 }
673
674 class examine_rhs : public ir_hierarchical_visitor {
675 public:
examine_rhs(hash_table * loop_variables)676 examine_rhs(hash_table *loop_variables)
677 {
678 this->only_uses_loop_constants = true;
679 this->loop_variables = loop_variables;
680 }
681
visit(ir_dereference_variable * ir)682 virtual ir_visitor_status visit(ir_dereference_variable *ir)
683 {
684 loop_variable *lv =
685 (loop_variable *) hash_table_find(this->loop_variables, ir->var);
686
687 assert(lv != NULL);
688
689 if (lv->is_loop_constant()) {
690 return visit_continue;
691 } else {
692 this->only_uses_loop_constants = false;
693 return visit_stop;
694 }
695 }
696
697 hash_table *loop_variables;
698 bool only_uses_loop_constants;
699 };
700
701
702 bool
all_expression_operands_are_loop_constant(ir_rvalue * ir,hash_table * variables)703 all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables)
704 {
705 examine_rhs v(variables);
706
707 ir->accept(&v);
708
709 return v.only_uses_loop_constants;
710 }
711
712
713 ir_rvalue *
get_basic_induction_increment(ir_assignment * ir,hash_table * var_hash)714 get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
715 {
716 /* The RHS must be a binary expression.
717 */
718 ir_expression *const rhs = ir->rhs->as_expression();
719 if ((rhs == NULL)
720 || ((rhs->operation != ir_binop_add)
721 && (rhs->operation != ir_binop_sub)))
722 return NULL;
723
724 /* One of the of operands of the expression must be the variable assigned.
725 * If the operation is subtraction, the variable in question must be the
726 * "left" operand.
727 */
728 ir_variable *const var = ir->lhs->variable_referenced();
729
730 ir_variable *const op0 = rhs->operands[0]->variable_referenced();
731 ir_variable *const op1 = rhs->operands[1]->variable_referenced();
732
733 if (((op0 != var) && (op1 != var))
734 || ((op1 == var) && (rhs->operation == ir_binop_sub)))
735 return NULL;
736
737 ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];
738
739 if (inc->as_constant() == NULL) {
740 ir_variable *const inc_var = inc->variable_referenced();
741 if (inc_var != NULL) {
742 loop_variable *lv =
743 (loop_variable *) hash_table_find(var_hash, inc_var);
744
745 if (lv == NULL || !lv->is_loop_constant()) {
746 assert(lv != NULL);
747 inc = NULL;
748 }
749 } else
750 inc = NULL;
751 }
752
753 if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
754 void *mem_ctx = ralloc_parent(ir);
755
756 inc = new(mem_ctx) ir_expression(ir_unop_neg,
757 inc->type,
758 inc->clone(mem_ctx, NULL),
759 NULL);
760 }
761
762 return inc;
763 }
764
765
766 /**
767 * Detect whether an if-statement is a loop terminating condition
768 *
769 * Detects if-statements of the form
770 *
771 * (if (expression bool ...) (break))
772 */
773 bool
is_loop_terminator(ir_if * ir)774 is_loop_terminator(ir_if *ir)
775 {
776 if (!ir->else_instructions.is_empty())
777 return false;
778
779 ir_instruction *const inst =
780 (ir_instruction *) ir->then_instructions.get_head();
781 if (inst == NULL)
782 return false;
783
784 if (inst->ir_type != ir_type_loop_jump)
785 return false;
786
787 ir_loop_jump *const jump = (ir_loop_jump *) inst;
788 if (jump->mode != ir_loop_jump::jump_break)
789 return false;
790
791 return true;
792 }
793
794 loop_state *
analyze_loop_variables(exec_list * instructions)795 analyze_loop_variables(exec_list *instructions)
796 {
797 loop_state *loops = new loop_state;
798 loop_analysis v(loops);
799
800 /* Do two passes over the instructions. The first pass builds a view
801 * of the variables declared and whether or not they're used outside
802 * of loops (if so, they cannot be inductors).
803 *
804 * In the second pass we apply this information to do the loop analysis
805 * itself.
806 */
807 v.first_pass = true;
808 v.run(instructions);
809 v.first_pass = false;
810 v.run(instructions);
811
812 return v.loops;
813 }
814