* check-init.c, decl.c, expr.c, gcj.texi, java-tree.h,
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobe74904797778578fc90d519250cc551fc4633c8a
1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
22 /*
23 Description:
25 This pass analyzes the evolution of scalar variables in loop
26 structures. The algorithm is based on the SSA representation,
27 and on the loop hierarchy tree. This algorithm is not based on
28 the notion of versions of a variable, as it was the case for the
29 previous implementations of the scalar evolution algorithm, but
30 it assumes that each defined name is unique.
32 The notation used in this file is called "chains of recurrences",
33 and has been proposed by Eugene Zima, Robert Van Engelen, and
34 others for describing induction variables in programs. For example
35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36 when entering in the loop_1 and has a step 2 in this loop, in other
37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38 this chain of recurrence (or chrec [shrek]) can contain the name of
39 other variables, in which case they are called parametric chrecs.
40 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41 is the value of "a". In most of the cases these parametric chrecs
42 are fully instantiated before their use because symbolic names can
43 hide some difficult cases such as self-references described later
44 (see the Fibonacci example).
46 A short sketch of the algorithm is:
48 Given a scalar variable to be analyzed, follow the SSA edge to
49 its definition:
51 - When the definition is a MODIFY_EXPR: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
74 Examples:
76 Example 1: Illustration of the basic algorithm.
78 | a = 3
79 | loop_1
80 | b = phi (a, c)
81 | c = b + 1
82 | if (c > 10) exit_loop
83 | endloop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters ({a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
116 a -> 3
117 b -> {3, +, 1}_1
118 c -> {4, +, 1}_1
120 or in terms of a C program:
122 | a = 3
123 | for (x = 0; x <= 7; x++)
125 | b = x + 3
126 | c = x + 4
129 Example 2: Illustration of the algorithm on nested loops.
131 | loop_1
132 | a = phi (1, b)
133 | c = a + 2
134 | loop_2 10 times
135 | b = phi (c, d)
136 | d = b + 3
137 | endloop
138 | endloop
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
144 b -> {c, +, 3}_2
145 d -> {c + 3, +, 3}_2
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
155 a -> {1, +, 32}_1
156 c -> {3, +, 32}_1
158 Example 3: Higher degree polynomials.
160 | loop_1
161 | a = phi (2, b)
162 | c = phi (5, d)
163 | b = a + 1
164 | d = c + a
165 | endloop
167 a -> {2, +, 1}_1
168 b -> {3, +, 1}_1
169 c -> {5, +, a}_1
170 d -> {5 + a, +, a}_1
172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175 Example 4: Lucas, Fibonacci, or mixers in general.
177 | loop_1
178 | a = phi (1, b)
179 | c = phi (3, d)
180 | b = c
181 | d = c + a
182 | endloop
184 a -> (1, c)_1
185 c -> {3, +, a}_1
187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188 following semantics: during the first iteration of the loop_1, the
189 variable contains the value 1, and then it contains the value "c".
190 Note that this syntax is close to the syntax of the loop-phi-node:
191 "a -> (1, c)_1" vs. "a = phi (1, c)".
193 The symbolic chrec representation contains all the semantics of the
194 original code. What is more difficult is to use this information.
196 Example 5: Flip-flops, or exchangers.
198 | loop_1
199 | a = phi (1, b)
200 | c = phi (3, d)
201 | b = c
202 | d = a
203 | endloop
205 a -> (1, c)_1
206 c -> (3, a)_1
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
211 a -> |1, 3|_1
212 c -> |3, 1|_1
214 This transformation is not yet implemented.
216 Further readings:
218 You can find a more detailed description of the algorithm in:
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
221 this is a preliminary report and some of the details of the
222 algorithm have changed. I'm working on a research report that
223 updates the description of the algorithms to reflect the design
224 choices used in this implementation.
226 A set of slides show a high level overview of the algorithm and run
227 an example through the scalar evolution analyzer:
228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230 The slides that I have presented at the GCC Summit'04 are available
231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
234 #include "config.h"
235 #include "system.h"
236 #include "coretypes.h"
237 #include "tm.h"
238 #include "ggc.h"
239 #include "tree.h"
240 #include "real.h"
242 /* These RTL headers are needed for basic-block.h. */
243 #include "rtl.h"
244 #include "basic-block.h"
245 #include "diagnostic.h"
246 #include "tree-flow.h"
247 #include "tree-dump.h"
248 #include "timevar.h"
249 #include "cfgloop.h"
250 #include "tree-chrec.h"
251 #include "tree-scalar-evolution.h"
252 #include "tree-pass.h"
253 #include "flags.h"
255 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
256 static tree resolve_mixers (struct loop *, tree);
258 /* The cached information about a ssa name VAR, claiming that inside LOOP,
259 the value of VAR can be expressed as CHREC. */
261 struct scev_info_str
263 tree var;
264 tree chrec;
267 /* Counters for the scev database. */
268 static unsigned nb_set_scev = 0;
269 static unsigned nb_get_scev = 0;
271 /* The following trees are unique elements. Thus the comparison of
272 another element to these elements should be done on the pointer to
273 these trees, and not on their value. */
275 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
276 tree chrec_not_analyzed_yet;
278 /* Reserved to the cases where the analyzer has detected an
279 undecidable property at compile time. */
280 tree chrec_dont_know;
282 /* When the analyzer has detected that a property will never
283 happen, then it qualifies it with chrec_known. */
284 tree chrec_known;
286 static bitmap already_instantiated;
288 static htab_t scalar_evolution_info;
291 /* Constructs a new SCEV_INFO_STR structure. */
293 static inline struct scev_info_str *
294 new_scev_info_str (tree var)
296 struct scev_info_str *res;
298 res = xmalloc (sizeof (struct scev_info_str));
299 res->var = var;
300 res->chrec = chrec_not_analyzed_yet;
302 return res;
305 /* Computes a hash function for database element ELT. */
307 static hashval_t
308 hash_scev_info (const void *elt)
310 return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
313 /* Compares database elements E1 and E2. */
315 static int
316 eq_scev_info (const void *e1, const void *e2)
318 const struct scev_info_str *elt1 = e1;
319 const struct scev_info_str *elt2 = e2;
321 return elt1->var == elt2->var;
324 /* Deletes database element E. */
326 static void
327 del_scev_info (void *e)
329 free (e);
332 /* Get the index corresponding to VAR in the current LOOP. If
333 it's the first time we ask for this VAR, then we return
334 chrec_not_analyzed_yet for this VAR and return its index. */
336 static tree *
337 find_var_scev_info (tree var)
339 struct scev_info_str *res;
340 struct scev_info_str tmp;
341 PTR *slot;
343 tmp.var = var;
344 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
346 if (!*slot)
347 *slot = new_scev_info_str (var);
348 res = *slot;
350 return &res->chrec;
353 /* Return true when CHREC contains symbolic names defined in
354 LOOP_NB. */
356 bool
357 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
359 if (chrec == NULL_TREE)
360 return false;
362 if (TREE_INVARIANT (chrec))
363 return false;
365 if (TREE_CODE (chrec) == VAR_DECL
366 || TREE_CODE (chrec) == PARM_DECL
367 || TREE_CODE (chrec) == FUNCTION_DECL
368 || TREE_CODE (chrec) == LABEL_DECL
369 || TREE_CODE (chrec) == RESULT_DECL
370 || TREE_CODE (chrec) == FIELD_DECL)
371 return true;
373 if (TREE_CODE (chrec) == SSA_NAME)
375 tree def = SSA_NAME_DEF_STMT (chrec);
376 struct loop *def_loop = loop_containing_stmt (def);
377 struct loop *loop = current_loops->parray[loop_nb];
379 if (def_loop == NULL)
380 return false;
382 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
383 return true;
385 return false;
388 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
390 case 3:
391 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
392 loop_nb))
393 return true;
395 case 2:
396 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
397 loop_nb))
398 return true;
400 case 1:
401 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
402 loop_nb))
403 return true;
405 default:
406 return false;
410 /* Return true when PHI is a loop-phi-node. */
412 static bool
413 loop_phi_node_p (tree phi)
415 /* The implementation of this function is based on the following
416 property: "all the loop-phi-nodes of a loop are contained in the
417 loop's header basic block". */
419 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
422 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
423 In general, in the case of multivariate evolutions we want to get
424 the evolution in different loops. LOOP specifies the level for
425 which to get the evolution.
427 Example:
429 | for (j = 0; j < 100; j++)
431 | for (k = 0; k < 100; k++)
433 | i = k + j; - Here the value of i is a function of j, k.
435 | ... = i - Here the value of i is a function of j.
437 | ... = i - Here the value of i is a scalar.
439 Example:
441 | i_0 = ...
442 | loop_1 10 times
443 | i_1 = phi (i_0, i_2)
444 | i_2 = i_1 + 2
445 | endloop
447 This loop has the same effect as:
448 LOOP_1 has the same effect as:
450 | i_1 = i_0 + 20
452 The overall effect of the loop, "i_0 + 20" in the previous example,
453 is obtained by passing in the parameters: LOOP = 1,
454 EVOLUTION_FN = {i_0, +, 2}_1.
457 static tree
458 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
460 bool val = false;
462 if (evolution_fn == chrec_dont_know)
463 return chrec_dont_know;
465 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
467 if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
469 struct loop *inner_loop =
470 current_loops->parray[CHREC_VARIABLE (evolution_fn)];
471 tree nb_iter = number_of_iterations_in_loop (inner_loop);
473 if (nb_iter == chrec_dont_know)
474 return chrec_dont_know;
475 else
477 tree res;
479 /* Number of iterations is off by one (the ssa name we
480 analyze must be defined before the exit). */
481 nb_iter = chrec_fold_minus (chrec_type (nb_iter),
482 nb_iter,
483 build_int_cst_type (chrec_type (nb_iter), 1));
485 /* evolution_fn is the evolution function in LOOP. Get
486 its value in the nb_iter-th iteration. */
487 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
489 /* Continue the computation until ending on a parent of LOOP. */
490 return compute_overall_effect_of_inner_loop (loop, res);
493 else
494 return evolution_fn;
497 /* If the evolution function is an invariant, there is nothing to do. */
498 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
499 return evolution_fn;
501 else
502 return chrec_dont_know;
505 /* Determine whether the CHREC is always positive/negative. If the expression
506 cannot be statically analyzed, return false, otherwise set the answer into
507 VALUE. */
509 bool
510 chrec_is_positive (tree chrec, bool *value)
512 bool value0, value1;
513 bool value2;
514 tree end_value;
515 tree nb_iter;
517 switch (TREE_CODE (chrec))
519 case POLYNOMIAL_CHREC:
520 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
521 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
522 return false;
524 /* FIXME -- overflows. */
525 if (value0 == value1)
527 *value = value0;
528 return true;
531 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
532 and the proof consists in showing that the sign never
533 changes during the execution of the loop, from 0 to
534 loop->nb_iterations. */
535 if (!evolution_function_is_affine_p (chrec))
536 return false;
538 nb_iter = number_of_iterations_in_loop
539 (current_loops->parray[CHREC_VARIABLE (chrec)]);
541 if (chrec_contains_undetermined (nb_iter))
542 return false;
544 nb_iter = chrec_fold_minus
545 (chrec_type (nb_iter), nb_iter,
546 build_int_cst (chrec_type (nb_iter), 1));
548 #if 0
549 /* TODO -- If the test is after the exit, we may decrease the number of
550 iterations by one. */
551 if (after_exit)
552 nb_iter = chrec_fold_minus
553 (chrec_type (nb_iter), nb_iter,
554 build_int_cst (chrec_type (nb_iter), 1));
555 #endif
557 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
559 if (!chrec_is_positive (end_value, &value2))
560 return false;
562 *value = value0;
563 return value0 == value1;
565 case INTEGER_CST:
566 *value = (tree_int_cst_sgn (chrec) == 1);
567 return true;
569 default:
570 return false;
574 /* Associate CHREC to SCALAR. */
576 static void
577 set_scalar_evolution (tree scalar, tree chrec)
579 tree *scalar_info;
581 if (TREE_CODE (scalar) != SSA_NAME)
582 return;
584 scalar_info = find_var_scev_info (scalar);
586 if (dump_file)
588 if (dump_flags & TDF_DETAILS)
590 fprintf (dump_file, "(set_scalar_evolution \n");
591 fprintf (dump_file, " (scalar = ");
592 print_generic_expr (dump_file, scalar, 0);
593 fprintf (dump_file, ")\n (scalar_evolution = ");
594 print_generic_expr (dump_file, chrec, 0);
595 fprintf (dump_file, "))\n");
597 if (dump_flags & TDF_STATS)
598 nb_set_scev++;
601 *scalar_info = chrec;
604 /* Retrieve the chrec associated to SCALAR in the LOOP. */
606 static tree
607 get_scalar_evolution (tree scalar)
609 tree res;
611 if (dump_file)
613 if (dump_flags & TDF_DETAILS)
615 fprintf (dump_file, "(get_scalar_evolution \n");
616 fprintf (dump_file, " (scalar = ");
617 print_generic_expr (dump_file, scalar, 0);
618 fprintf (dump_file, ")\n");
620 if (dump_flags & TDF_STATS)
621 nb_get_scev++;
624 switch (TREE_CODE (scalar))
626 case SSA_NAME:
627 res = *find_var_scev_info (scalar);
628 break;
630 case REAL_CST:
631 case INTEGER_CST:
632 res = scalar;
633 break;
635 default:
636 res = chrec_not_analyzed_yet;
637 break;
640 if (dump_file && (dump_flags & TDF_DETAILS))
642 fprintf (dump_file, " (scalar_evolution = ");
643 print_generic_expr (dump_file, res, 0);
644 fprintf (dump_file, "))\n");
647 return res;
650 /* Helper function for add_to_evolution. Returns the evolution
651 function for an assignment of the form "a = b + c", where "a" and
652 "b" are on the strongly connected component. CHREC_BEFORE is the
653 information that we already have collected up to this point.
654 TO_ADD is the evolution of "c".
656 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
657 evolution the expression TO_ADD, otherwise construct an evolution
658 part for this loop. */
660 static tree
661 add_to_evolution_1 (unsigned loop_nb,
662 tree chrec_before,
663 tree to_add)
665 switch (TREE_CODE (chrec_before))
667 case POLYNOMIAL_CHREC:
668 if (CHREC_VARIABLE (chrec_before) <= loop_nb)
670 unsigned var;
671 tree left, right;
672 tree type = chrec_type (chrec_before);
674 /* When there is no evolution part in this loop, build it. */
675 if (CHREC_VARIABLE (chrec_before) < loop_nb)
677 var = loop_nb;
678 left = chrec_before;
679 right = SCALAR_FLOAT_TYPE_P (type)
680 ? build_real (type, dconst0)
681 : build_int_cst (type, 0);
683 else
685 var = CHREC_VARIABLE (chrec_before);
686 left = CHREC_LEFT (chrec_before);
687 right = CHREC_RIGHT (chrec_before);
690 return build_polynomial_chrec
691 (var, left, chrec_fold_plus (type, right, to_add));
693 else
694 /* Search the evolution in LOOP_NB. */
695 return build_polynomial_chrec
696 (CHREC_VARIABLE (chrec_before),
697 add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
698 CHREC_RIGHT (chrec_before));
700 default:
701 /* These nodes do not depend on a loop. */
702 if (chrec_before == chrec_dont_know)
703 return chrec_dont_know;
704 return build_polynomial_chrec (loop_nb, chrec_before, to_add);
708 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
709 of LOOP_NB.
711 Description (provided for completeness, for those who read code in
712 a plane, and for my poor 62 bytes brain that would have forgotten
713 all this in the next two or three months):
715 The algorithm of translation of programs from the SSA representation
716 into the chrecs syntax is based on a pattern matching. After having
717 reconstructed the overall tree expression for a loop, there are only
718 two cases that can arise:
720 1. a = loop-phi (init, a + expr)
721 2. a = loop-phi (init, expr)
723 where EXPR is either a scalar constant with respect to the analyzed
724 loop (this is a degree 0 polynomial), or an expression containing
725 other loop-phi definitions (these are higher degree polynomials).
727 Examples:
730 | init = ...
731 | loop_1
732 | a = phi (init, a + 5)
733 | endloop
736 | inita = ...
737 | initb = ...
738 | loop_1
739 | a = phi (inita, 2 * b + 3)
740 | b = phi (initb, b + 1)
741 | endloop
743 For the first case, the semantics of the SSA representation is:
745 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
747 that is, there is a loop index "x" that determines the scalar value
748 of the variable during the loop execution. During the first
749 iteration, the value is that of the initial condition INIT, while
750 during the subsequent iterations, it is the sum of the initial
751 condition with the sum of all the values of EXPR from the initial
752 iteration to the before last considered iteration.
754 For the second case, the semantics of the SSA program is:
756 | a (x) = init, if x = 0;
757 | expr (x - 1), otherwise.
759 The second case corresponds to the PEELED_CHREC, whose syntax is
760 close to the syntax of a loop-phi-node:
762 | phi (init, expr) vs. (init, expr)_x
764 The proof of the translation algorithm for the first case is a
765 proof by structural induction based on the degree of EXPR.
767 Degree 0:
768 When EXPR is a constant with respect to the analyzed loop, or in
769 other words when EXPR is a polynomial of degree 0, the evolution of
770 the variable A in the loop is an affine function with an initial
771 condition INIT, and a step EXPR. In order to show this, we start
772 from the semantics of the SSA representation:
774 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
776 and since "expr (j)" is a constant with respect to "j",
778 f (x) = init + x * expr
780 Finally, based on the semantics of the pure sum chrecs, by
781 identification we get the corresponding chrecs syntax:
783 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
784 f (x) -> {init, +, expr}_x
786 Higher degree:
787 Suppose that EXPR is a polynomial of degree N with respect to the
788 analyzed loop_x for which we have already determined that it is
789 written under the chrecs syntax:
791 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
793 We start from the semantics of the SSA program:
795 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
797 | f (x) = init + \sum_{j = 0}^{x - 1}
798 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
800 | f (x) = init + \sum_{j = 0}^{x - 1}
801 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
803 | f (x) = init + \sum_{k = 0}^{n - 1}
804 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
806 | f (x) = init + \sum_{k = 0}^{n - 1}
807 | (b_k * \binom{x}{k + 1})
809 | f (x) = init + b_0 * \binom{x}{1} + ...
810 | + b_{n-1} * \binom{x}{n}
812 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
813 | + b_{n-1} * \binom{x}{n}
816 And finally from the definition of the chrecs syntax, we identify:
817 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
819 This shows the mechanism that stands behind the add_to_evolution
820 function. An important point is that the use of symbolic
821 parameters avoids the need of an analysis schedule.
823 Example:
825 | inita = ...
826 | initb = ...
827 | loop_1
828 | a = phi (inita, a + 2 + b)
829 | b = phi (initb, b + 1)
830 | endloop
832 When analyzing "a", the algorithm keeps "b" symbolically:
834 | a -> {inita, +, 2 + b}_1
836 Then, after instantiation, the analyzer ends on the evolution:
838 | a -> {inita, +, 2 + initb, +, 1}_1
842 static tree
843 add_to_evolution (unsigned loop_nb,
844 tree chrec_before,
845 enum tree_code code,
846 tree to_add)
848 tree type = chrec_type (to_add);
849 tree res = NULL_TREE;
851 if (to_add == NULL_TREE)
852 return chrec_before;
854 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
855 instantiated at this point. */
856 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
857 /* This should not happen. */
858 return chrec_dont_know;
860 if (dump_file && (dump_flags & TDF_DETAILS))
862 fprintf (dump_file, "(add_to_evolution \n");
863 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
864 fprintf (dump_file, " (chrec_before = ");
865 print_generic_expr (dump_file, chrec_before, 0);
866 fprintf (dump_file, ")\n (to_add = ");
867 print_generic_expr (dump_file, to_add, 0);
868 fprintf (dump_file, ")\n");
871 if (code == MINUS_EXPR)
872 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
873 ? build_real (type, dconstm1)
874 : build_int_cst_type (type, -1));
876 res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
878 if (dump_file && (dump_flags & TDF_DETAILS))
880 fprintf (dump_file, " (res = ");
881 print_generic_expr (dump_file, res, 0);
882 fprintf (dump_file, "))\n");
885 return res;
888 /* Helper function. */
890 static inline tree
891 set_nb_iterations_in_loop (struct loop *loop,
892 tree res)
894 res = chrec_fold_plus (chrec_type (res), res,
895 build_int_cst_type (chrec_type (res), 1));
897 /* FIXME HWI: However we want to store one iteration less than the
898 count of the loop in order to be compatible with the other
899 nb_iter computations in loop-iv. This also allows the
900 representation of nb_iters that are equal to MAX_INT. */
901 if (TREE_CODE (res) == INTEGER_CST
902 && (TREE_INT_CST_LOW (res) == 0
903 || TREE_OVERFLOW (res)))
904 res = chrec_dont_know;
906 if (dump_file && (dump_flags & TDF_DETAILS))
908 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
909 print_generic_expr (dump_file, res, 0);
910 fprintf (dump_file, "))\n");
913 loop->nb_iterations = res;
914 return res;
919 /* This section selects the loops that will be good candidates for the
920 scalar evolution analysis. For the moment, greedily select all the
921 loop nests we could analyze. */
923 /* Return true when it is possible to analyze the condition expression
924 EXPR. */
926 static bool
927 analyzable_condition (tree expr)
929 tree condition;
931 if (TREE_CODE (expr) != COND_EXPR)
932 return false;
934 condition = TREE_OPERAND (expr, 0);
936 switch (TREE_CODE (condition))
938 case SSA_NAME:
939 return true;
941 case LT_EXPR:
942 case LE_EXPR:
943 case GT_EXPR:
944 case GE_EXPR:
945 case EQ_EXPR:
946 case NE_EXPR:
947 return true;
949 default:
950 return false;
953 return false;
956 /* For a loop with a single exit edge, return the COND_EXPR that
957 guards the exit edge. If the expression is too difficult to
958 analyze, then give up. */
960 tree
961 get_loop_exit_condition (struct loop *loop)
963 tree res = NULL_TREE;
964 edge exit_edge = loop->single_exit;
967 if (dump_file && (dump_flags & TDF_DETAILS))
968 fprintf (dump_file, "(get_loop_exit_condition \n ");
970 if (exit_edge)
972 tree expr;
974 expr = last_stmt (exit_edge->src);
975 if (analyzable_condition (expr))
976 res = expr;
979 if (dump_file && (dump_flags & TDF_DETAILS))
981 print_generic_expr (dump_file, res, 0);
982 fprintf (dump_file, ")\n");
985 return res;
988 /* Recursively determine and enqueue the exit conditions for a loop. */
990 static void
991 get_exit_conditions_rec (struct loop *loop,
992 VEC(tree,heap) **exit_conditions)
994 if (!loop)
995 return;
997 /* Recurse on the inner loops, then on the next (sibling) loops. */
998 get_exit_conditions_rec (loop->inner, exit_conditions);
999 get_exit_conditions_rec (loop->next, exit_conditions);
1001 if (loop->single_exit)
1003 tree loop_condition = get_loop_exit_condition (loop);
1005 if (loop_condition)
1006 VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1010 /* Select the candidate loop nests for the analysis. This function
1011 initializes the EXIT_CONDITIONS array. */
1013 static void
1014 select_loops_exit_conditions (struct loops *loops,
1015 VEC(tree,heap) **exit_conditions)
1017 struct loop *function_body = loops->parray[0];
1019 get_exit_conditions_rec (function_body->inner, exit_conditions);
1023 /* Depth first search algorithm. */
1025 static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
1027 /* Follow the ssa edge into the right hand side RHS of an assignment.
1028 Return true if the strongly connected component has been found. */
1030 static bool
1031 follow_ssa_edge_in_rhs (struct loop *loop,
1032 tree at_stmt,
1033 tree rhs,
1034 tree halting_phi,
1035 tree *evolution_of_loop)
1037 bool res = false;
1038 tree rhs0, rhs1;
1039 tree type_rhs = TREE_TYPE (rhs);
1041 /* The RHS is one of the following cases:
1042 - an SSA_NAME,
1043 - an INTEGER_CST,
1044 - a PLUS_EXPR,
1045 - a MINUS_EXPR,
1046 - an ASSERT_EXPR,
1047 - other cases are not yet handled. */
1048 switch (TREE_CODE (rhs))
1050 case NOP_EXPR:
1051 /* This assignment is under the form "a_1 = (cast) rhs. */
1052 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1053 halting_phi, evolution_of_loop);
1054 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1055 *evolution_of_loop, at_stmt);
1056 break;
1058 case INTEGER_CST:
1059 /* This assignment is under the form "a_1 = 7". */
1060 res = false;
1061 break;
1063 case SSA_NAME:
1064 /* This assignment is under the form: "a_1 = b_2". */
1065 res = follow_ssa_edge
1066 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
1067 break;
1069 case PLUS_EXPR:
1070 /* This case is under the form "rhs0 + rhs1". */
1071 rhs0 = TREE_OPERAND (rhs, 0);
1072 rhs1 = TREE_OPERAND (rhs, 1);
1073 STRIP_TYPE_NOPS (rhs0);
1074 STRIP_TYPE_NOPS (rhs1);
1076 if (TREE_CODE (rhs0) == SSA_NAME)
1078 if (TREE_CODE (rhs1) == SSA_NAME)
1080 /* Match an assignment under the form:
1081 "a = b + c". */
1082 res = follow_ssa_edge
1083 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1084 evolution_of_loop);
1086 if (res)
1087 *evolution_of_loop = add_to_evolution
1088 (loop->num,
1089 chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1090 PLUS_EXPR, rhs1);
1092 else
1094 res = follow_ssa_edge
1095 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1096 evolution_of_loop);
1098 if (res)
1099 *evolution_of_loop = add_to_evolution
1100 (loop->num,
1101 chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1102 PLUS_EXPR, rhs0);
1106 else
1108 /* Match an assignment under the form:
1109 "a = b + ...". */
1110 res = follow_ssa_edge
1111 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1112 evolution_of_loop);
1113 if (res)
1114 *evolution_of_loop = add_to_evolution
1115 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1116 at_stmt),
1117 PLUS_EXPR, rhs1);
1121 else if (TREE_CODE (rhs1) == SSA_NAME)
1123 /* Match an assignment under the form:
1124 "a = ... + c". */
1125 res = follow_ssa_edge
1126 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1127 evolution_of_loop);
1128 if (res)
1129 *evolution_of_loop = add_to_evolution
1130 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1131 at_stmt),
1132 PLUS_EXPR, rhs0);
1135 else
1136 /* Otherwise, match an assignment under the form:
1137 "a = ... + ...". */
1138 /* And there is nothing to do. */
1139 res = false;
1141 break;
1143 case MINUS_EXPR:
1144 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1145 rhs0 = TREE_OPERAND (rhs, 0);
1146 rhs1 = TREE_OPERAND (rhs, 1);
1147 STRIP_TYPE_NOPS (rhs0);
1148 STRIP_TYPE_NOPS (rhs1);
1150 if (TREE_CODE (rhs0) == SSA_NAME)
1152 /* Match an assignment under the form:
1153 "a = b - ...". */
1154 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1155 evolution_of_loop);
1156 if (res)
1157 *evolution_of_loop = add_to_evolution
1158 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1159 at_stmt),
1160 MINUS_EXPR, rhs1);
1162 else
1163 /* Otherwise, match an assignment under the form:
1164 "a = ... - ...". */
1165 /* And there is nothing to do. */
1166 res = false;
1168 break;
1170 case MULT_EXPR:
1171 /* This case is under the form "opnd0 = rhs0 * rhs1". */
1172 rhs0 = TREE_OPERAND (rhs, 0);
1173 rhs1 = TREE_OPERAND (rhs, 1);
1174 STRIP_TYPE_NOPS (rhs0);
1175 STRIP_TYPE_NOPS (rhs1);
1177 if (TREE_CODE (rhs0) == SSA_NAME)
1179 if (TREE_CODE (rhs1) == SSA_NAME)
1181 /* Match an assignment under the form:
1182 "a = b * c". */
1183 res = follow_ssa_edge
1184 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1185 evolution_of_loop);
1187 if (res)
1188 *evolution_of_loop = chrec_dont_know;
1190 else
1192 res = follow_ssa_edge
1193 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1194 evolution_of_loop);
1196 if (res)
1197 *evolution_of_loop = chrec_dont_know;
1201 else
1203 /* Match an assignment under the form:
1204 "a = b * ...". */
1205 res = follow_ssa_edge
1206 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1207 evolution_of_loop);
1208 if (res)
1209 *evolution_of_loop = chrec_dont_know;
1213 else if (TREE_CODE (rhs1) == SSA_NAME)
1215 /* Match an assignment under the form:
1216 "a = ... * c". */
1217 res = follow_ssa_edge
1218 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1219 evolution_of_loop);
1220 if (res)
1221 *evolution_of_loop = chrec_dont_know;
1224 else
1225 /* Otherwise, match an assignment under the form:
1226 "a = ... * ...". */
1227 /* And there is nothing to do. */
1228 res = false;
1230 break;
1232 case ASSERT_EXPR:
1234 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1235 It must be handled as a copy assignment of the form a_1 = a_2. */
1236 tree op0 = ASSERT_EXPR_VAR (rhs);
1237 if (TREE_CODE (op0) == SSA_NAME)
1238 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1239 halting_phi, evolution_of_loop);
1240 else
1241 res = false;
1242 break;
1246 default:
1247 res = false;
1248 break;
1251 return res;
1254 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1256 static bool
1257 backedge_phi_arg_p (tree phi, int i)
1259 edge e = PHI_ARG_EDGE (phi, i);
1261 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1262 about updating it anywhere, and this should work as well most of the
1263 time. */
1264 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1265 return true;
1267 return false;
1270 /* Helper function for one branch of the condition-phi-node. Return
1271 true if the strongly connected component has been found following
1272 this path. */
1274 static inline bool
1275 follow_ssa_edge_in_condition_phi_branch (int i,
1276 struct loop *loop,
1277 tree condition_phi,
1278 tree halting_phi,
1279 tree *evolution_of_branch,
1280 tree init_cond)
1282 tree branch = PHI_ARG_DEF (condition_phi, i);
1283 *evolution_of_branch = chrec_dont_know;
1285 /* Do not follow back edges (they must belong to an irreducible loop, which
1286 we really do not want to worry about). */
1287 if (backedge_phi_arg_p (condition_phi, i))
1288 return false;
1290 if (TREE_CODE (branch) == SSA_NAME)
1292 *evolution_of_branch = init_cond;
1293 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1294 evolution_of_branch);
1297 /* This case occurs when one of the condition branches sets
1298 the variable to a constant: i.e. a phi-node like
1299 "a_2 = PHI <a_7(5), 2(6)>;".
1301 FIXME: This case have to be refined correctly:
1302 in some cases it is possible to say something better than
1303 chrec_dont_know, for example using a wrap-around notation. */
1304 return false;
1307 /* This function merges the branches of a condition-phi-node in a
1308 loop. */
1310 static bool
1311 follow_ssa_edge_in_condition_phi (struct loop *loop,
1312 tree condition_phi,
1313 tree halting_phi,
1314 tree *evolution_of_loop)
1316 int i;
1317 tree init = *evolution_of_loop;
1318 tree evolution_of_branch;
1320 if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1321 halting_phi,
1322 &evolution_of_branch,
1323 init))
1324 return false;
1325 *evolution_of_loop = evolution_of_branch;
1327 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1329 /* Quickly give up when the evolution of one of the branches is
1330 not known. */
1331 if (*evolution_of_loop == chrec_dont_know)
1332 return true;
1334 if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1335 halting_phi,
1336 &evolution_of_branch,
1337 init))
1338 return false;
1340 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1341 evolution_of_branch);
1344 return true;
1347 /* Follow an SSA edge in an inner loop. It computes the overall
1348 effect of the loop, and following the symbolic initial conditions,
1349 it follows the edges in the parent loop. The inner loop is
1350 considered as a single statement. */
1352 static bool
1353 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1354 tree loop_phi_node,
1355 tree halting_phi,
1356 tree *evolution_of_loop)
1358 struct loop *loop = loop_containing_stmt (loop_phi_node);
1359 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1361 /* Sometimes, the inner loop is too difficult to analyze, and the
1362 result of the analysis is a symbolic parameter. */
1363 if (ev == PHI_RESULT (loop_phi_node))
1365 bool res = false;
1366 int i;
1368 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1370 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1371 basic_block bb;
1373 /* Follow the edges that exit the inner loop. */
1374 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1375 if (!flow_bb_inside_loop_p (loop, bb))
1376 res = res || follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1377 arg, halting_phi,
1378 evolution_of_loop);
1381 /* If the path crosses this loop-phi, give up. */
1382 if (res == true)
1383 *evolution_of_loop = chrec_dont_know;
1385 return res;
1388 /* Otherwise, compute the overall effect of the inner loop. */
1389 ev = compute_overall_effect_of_inner_loop (loop, ev);
1390 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1391 evolution_of_loop);
1394 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1395 path that is analyzed on the return walk. */
1397 static bool
1398 follow_ssa_edge (struct loop *loop,
1399 tree def,
1400 tree halting_phi,
1401 tree *evolution_of_loop)
1403 struct loop *def_loop;
1405 if (TREE_CODE (def) == NOP_EXPR)
1406 return false;
1408 def_loop = loop_containing_stmt (def);
1410 switch (TREE_CODE (def))
1412 case PHI_NODE:
1413 if (!loop_phi_node_p (def))
1414 /* DEF is a condition-phi-node. Follow the branches, and
1415 record their evolutions. Finally, merge the collected
1416 information and set the approximation to the main
1417 variable. */
1418 return follow_ssa_edge_in_condition_phi
1419 (loop, def, halting_phi, evolution_of_loop);
1421 /* When the analyzed phi is the halting_phi, the
1422 depth-first search is over: we have found a path from
1423 the halting_phi to itself in the loop. */
1424 if (def == halting_phi)
1425 return true;
1427 /* Otherwise, the evolution of the HALTING_PHI depends
1428 on the evolution of another loop-phi-node, i.e. the
1429 evolution function is a higher degree polynomial. */
1430 if (def_loop == loop)
1431 return false;
1433 /* Inner loop. */
1434 if (flow_loop_nested_p (loop, def_loop))
1435 return follow_ssa_edge_inner_loop_phi
1436 (loop, def, halting_phi, evolution_of_loop);
1438 /* Outer loop. */
1439 return false;
1441 case MODIFY_EXPR:
1442 return follow_ssa_edge_in_rhs (loop, def,
1443 TREE_OPERAND (def, 1),
1444 halting_phi,
1445 evolution_of_loop);
1447 default:
1448 /* At this level of abstraction, the program is just a set
1449 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1450 other node to be handled. */
1451 return false;
1457 /* Given a LOOP_PHI_NODE, this function determines the evolution
1458 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1460 static tree
1461 analyze_evolution_in_loop (tree loop_phi_node,
1462 tree init_cond)
1464 int i;
1465 tree evolution_function = chrec_not_analyzed_yet;
1466 struct loop *loop = loop_containing_stmt (loop_phi_node);
1467 basic_block bb;
1469 if (dump_file && (dump_flags & TDF_DETAILS))
1471 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1472 fprintf (dump_file, " (loop_phi_node = ");
1473 print_generic_expr (dump_file, loop_phi_node, 0);
1474 fprintf (dump_file, ")\n");
1477 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1479 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1480 tree ssa_chain, ev_fn;
1481 bool res;
1483 /* Select the edges that enter the loop body. */
1484 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1485 if (!flow_bb_inside_loop_p (loop, bb))
1486 continue;
1488 if (TREE_CODE (arg) == SSA_NAME)
1490 ssa_chain = SSA_NAME_DEF_STMT (arg);
1492 /* Pass in the initial condition to the follow edge function. */
1493 ev_fn = init_cond;
1494 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
1496 else
1497 res = false;
1499 /* When it is impossible to go back on the same
1500 loop_phi_node by following the ssa edges, the
1501 evolution is represented by a peeled chrec, i.e. the
1502 first iteration, EV_FN has the value INIT_COND, then
1503 all the other iterations it has the value of ARG.
1504 For the moment, PEELED_CHREC nodes are not built. */
1505 if (!res)
1506 ev_fn = chrec_dont_know;
1508 /* When there are multiple back edges of the loop (which in fact never
1509 happens currently, but nevertheless), merge their evolutions. */
1510 evolution_function = chrec_merge (evolution_function, ev_fn);
1513 if (dump_file && (dump_flags & TDF_DETAILS))
1515 fprintf (dump_file, " (evolution_function = ");
1516 print_generic_expr (dump_file, evolution_function, 0);
1517 fprintf (dump_file, "))\n");
1520 return evolution_function;
1523 /* Given a loop-phi-node, return the initial conditions of the
1524 variable on entry of the loop. When the CCP has propagated
1525 constants into the loop-phi-node, the initial condition is
1526 instantiated, otherwise the initial condition is kept symbolic.
1527 This analyzer does not analyze the evolution outside the current
1528 loop, and leaves this task to the on-demand tree reconstructor. */
1530 static tree
1531 analyze_initial_condition (tree loop_phi_node)
1533 int i;
1534 tree init_cond = chrec_not_analyzed_yet;
1535 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1537 if (dump_file && (dump_flags & TDF_DETAILS))
1539 fprintf (dump_file, "(analyze_initial_condition \n");
1540 fprintf (dump_file, " (loop_phi_node = \n");
1541 print_generic_expr (dump_file, loop_phi_node, 0);
1542 fprintf (dump_file, ")\n");
1545 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1547 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1548 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1550 /* When the branch is oriented to the loop's body, it does
1551 not contribute to the initial condition. */
1552 if (flow_bb_inside_loop_p (loop, bb))
1553 continue;
1555 if (init_cond == chrec_not_analyzed_yet)
1557 init_cond = branch;
1558 continue;
1561 if (TREE_CODE (branch) == SSA_NAME)
1563 init_cond = chrec_dont_know;
1564 break;
1567 init_cond = chrec_merge (init_cond, branch);
1570 /* Ooops -- a loop without an entry??? */
1571 if (init_cond == chrec_not_analyzed_yet)
1572 init_cond = chrec_dont_know;
1574 if (dump_file && (dump_flags & TDF_DETAILS))
1576 fprintf (dump_file, " (init_cond = ");
1577 print_generic_expr (dump_file, init_cond, 0);
1578 fprintf (dump_file, "))\n");
1581 return init_cond;
1584 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1586 static tree
1587 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1589 tree res;
1590 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1591 tree init_cond;
1593 if (phi_loop != loop)
1595 struct loop *subloop;
1596 tree evolution_fn = analyze_scalar_evolution
1597 (phi_loop, PHI_RESULT (loop_phi_node));
1599 /* Dive one level deeper. */
1600 subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1602 /* Interpret the subloop. */
1603 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1604 return res;
1607 /* Otherwise really interpret the loop phi. */
1608 init_cond = analyze_initial_condition (loop_phi_node);
1609 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1611 return res;
1614 /* This function merges the branches of a condition-phi-node,
1615 contained in the outermost loop, and whose arguments are already
1616 analyzed. */
1618 static tree
1619 interpret_condition_phi (struct loop *loop, tree condition_phi)
1621 int i;
1622 tree res = chrec_not_analyzed_yet;
1624 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1626 tree branch_chrec;
1628 if (backedge_phi_arg_p (condition_phi, i))
1630 res = chrec_dont_know;
1631 break;
1634 branch_chrec = analyze_scalar_evolution
1635 (loop, PHI_ARG_DEF (condition_phi, i));
1637 res = chrec_merge (res, branch_chrec);
1640 return res;
1643 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1644 analyze this node before, follow the definitions until ending
1645 either on an analyzed modify_expr, or on a loop-phi-node. On the
1646 return path, this function propagates evolutions (ala constant copy
1647 propagation). OPND1 is not a GIMPLE expression because we could
1648 analyze the effect of an inner loop: see interpret_loop_phi. */
1650 static tree
1651 interpret_rhs_modify_expr (struct loop *loop, tree at_stmt,
1652 tree opnd1, tree type)
1654 tree res, opnd10, opnd11, chrec10, chrec11;
1656 if (is_gimple_min_invariant (opnd1))
1657 return chrec_convert (type, opnd1, at_stmt);
1659 switch (TREE_CODE (opnd1))
1661 case PLUS_EXPR:
1662 opnd10 = TREE_OPERAND (opnd1, 0);
1663 opnd11 = TREE_OPERAND (opnd1, 1);
1664 chrec10 = analyze_scalar_evolution (loop, opnd10);
1665 chrec11 = analyze_scalar_evolution (loop, opnd11);
1666 chrec10 = chrec_convert (type, chrec10, at_stmt);
1667 chrec11 = chrec_convert (type, chrec11, at_stmt);
1668 res = chrec_fold_plus (type, chrec10, chrec11);
1669 break;
1671 case MINUS_EXPR:
1672 opnd10 = TREE_OPERAND (opnd1, 0);
1673 opnd11 = TREE_OPERAND (opnd1, 1);
1674 chrec10 = analyze_scalar_evolution (loop, opnd10);
1675 chrec11 = analyze_scalar_evolution (loop, opnd11);
1676 chrec10 = chrec_convert (type, chrec10, at_stmt);
1677 chrec11 = chrec_convert (type, chrec11, at_stmt);
1678 res = chrec_fold_minus (type, chrec10, chrec11);
1679 break;
1681 case NEGATE_EXPR:
1682 opnd10 = TREE_OPERAND (opnd1, 0);
1683 chrec10 = analyze_scalar_evolution (loop, opnd10);
1684 chrec10 = chrec_convert (type, chrec10, at_stmt);
1685 res = chrec_fold_multiply (type, chrec10, SCALAR_FLOAT_TYPE_P (type)
1686 ? build_real (type, dconstm1)
1687 : build_int_cst_type (type, -1));
1688 break;
1690 case MULT_EXPR:
1691 opnd10 = TREE_OPERAND (opnd1, 0);
1692 opnd11 = TREE_OPERAND (opnd1, 1);
1693 chrec10 = analyze_scalar_evolution (loop, opnd10);
1694 chrec11 = analyze_scalar_evolution (loop, opnd11);
1695 chrec10 = chrec_convert (type, chrec10, at_stmt);
1696 chrec11 = chrec_convert (type, chrec11, at_stmt);
1697 res = chrec_fold_multiply (type, chrec10, chrec11);
1698 break;
1700 case SSA_NAME:
1701 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1702 at_stmt);
1703 break;
1705 case ASSERT_EXPR:
1706 opnd10 = ASSERT_EXPR_VAR (opnd1);
1707 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1708 at_stmt);
1709 break;
1711 case NOP_EXPR:
1712 case CONVERT_EXPR:
1713 opnd10 = TREE_OPERAND (opnd1, 0);
1714 chrec10 = analyze_scalar_evolution (loop, opnd10);
1715 res = chrec_convert (type, chrec10, at_stmt);
1716 break;
1718 default:
1719 res = chrec_dont_know;
1720 break;
1723 return res;
1728 /* This section contains all the entry points:
1729 - number_of_iterations_in_loop,
1730 - analyze_scalar_evolution,
1731 - instantiate_parameters.
1734 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1735 common ancestor of DEF_LOOP and USE_LOOP. */
1737 static tree
1738 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1739 struct loop *def_loop,
1740 tree ev)
1742 tree res;
1743 if (def_loop == wrto_loop)
1744 return ev;
1746 def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1747 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1749 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1752 /* Helper recursive function. */
1754 static tree
1755 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1757 tree def, type = TREE_TYPE (var);
1758 basic_block bb;
1759 struct loop *def_loop;
1761 if (loop == NULL)
1762 return chrec_dont_know;
1764 if (TREE_CODE (var) != SSA_NAME)
1765 return interpret_rhs_modify_expr (loop, NULL_TREE, var, type);
1767 def = SSA_NAME_DEF_STMT (var);
1768 bb = bb_for_stmt (def);
1769 def_loop = bb ? bb->loop_father : NULL;
1771 if (bb == NULL
1772 || !flow_bb_inside_loop_p (loop, bb))
1774 /* Keep the symbolic form. */
1775 res = var;
1776 goto set_and_end;
1779 if (res != chrec_not_analyzed_yet)
1781 if (loop != bb->loop_father)
1782 res = compute_scalar_evolution_in_loop
1783 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1785 goto set_and_end;
1788 if (loop != def_loop)
1790 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1791 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1793 goto set_and_end;
1796 switch (TREE_CODE (def))
1798 case MODIFY_EXPR:
1799 res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
1800 break;
1802 case PHI_NODE:
1803 if (loop_phi_node_p (def))
1804 res = interpret_loop_phi (loop, def);
1805 else
1806 res = interpret_condition_phi (loop, def);
1807 break;
1809 default:
1810 res = chrec_dont_know;
1811 break;
1814 set_and_end:
1816 /* Keep the symbolic form. */
1817 if (res == chrec_dont_know)
1818 res = var;
1820 if (loop == def_loop)
1821 set_scalar_evolution (var, res);
1823 return res;
1826 /* Entry point for the scalar evolution analyzer.
1827 Analyzes and returns the scalar evolution of the ssa_name VAR.
1828 LOOP_NB is the identifier number of the loop in which the variable
1829 is used.
1831 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1832 pointer to the statement that uses this variable, in order to
1833 determine the evolution function of the variable, use the following
1834 calls:
1836 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1837 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1838 tree chrec_instantiated = instantiate_parameters
1839 (loop_nb, chrec_with_symbols);
1842 tree
1843 analyze_scalar_evolution (struct loop *loop, tree var)
1845 tree res;
1847 if (dump_file && (dump_flags & TDF_DETAILS))
1849 fprintf (dump_file, "(analyze_scalar_evolution \n");
1850 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1851 fprintf (dump_file, " (scalar = ");
1852 print_generic_expr (dump_file, var, 0);
1853 fprintf (dump_file, ")\n");
1856 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1858 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1859 res = var;
1861 if (dump_file && (dump_flags & TDF_DETAILS))
1862 fprintf (dump_file, ")\n");
1864 return res;
1867 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1868 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1869 of VERSION). */
1871 static tree
1872 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1873 tree version)
1875 bool val = false;
1876 tree ev = version;
1878 while (1)
1880 ev = analyze_scalar_evolution (use_loop, ev);
1881 ev = resolve_mixers (use_loop, ev);
1883 if (use_loop == wrto_loop)
1884 return ev;
1886 /* If the value of the use changes in the inner loop, we cannot express
1887 its value in the outer loop (we might try to return interval chrec,
1888 but we do not have a user for it anyway) */
1889 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1890 || !val)
1891 return chrec_dont_know;
1893 use_loop = use_loop->outer;
1897 /* Returns instantiated value for VERSION in CACHE. */
1899 static tree
1900 get_instantiated_value (htab_t cache, tree version)
1902 struct scev_info_str *info, pattern;
1904 pattern.var = version;
1905 info = htab_find (cache, &pattern);
1907 if (info)
1908 return info->chrec;
1909 else
1910 return NULL_TREE;
1913 /* Sets instantiated value for VERSION to VAL in CACHE. */
1915 static void
1916 set_instantiated_value (htab_t cache, tree version, tree val)
1918 struct scev_info_str *info, pattern;
1919 PTR *slot;
1921 pattern.var = version;
1922 slot = htab_find_slot (cache, &pattern, INSERT);
1924 if (*slot)
1925 info = *slot;
1926 else
1927 info = *slot = new_scev_info_str (version);
1928 info->chrec = val;
1931 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1932 with respect to LOOP. CHREC is the chrec to instantiate. If
1933 ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1934 outer loop chrecs is done. CACHE is the cache of already instantiated
1935 values. */
1937 static tree
1938 instantiate_parameters_1 (struct loop *loop, tree chrec,
1939 bool allow_superloop_chrecs,
1940 htab_t cache)
1942 tree res, op0, op1, op2;
1943 basic_block def_bb;
1944 struct loop *def_loop;
1946 if (automatically_generated_chrec_p (chrec)
1947 || is_gimple_min_invariant (chrec))
1948 return chrec;
1950 switch (TREE_CODE (chrec))
1952 case SSA_NAME:
1953 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1955 /* A parameter (or loop invariant and we do not want to include
1956 evolutions in outer loops), nothing to do. */
1957 if (!def_bb
1958 || (!allow_superloop_chrecs
1959 && !flow_bb_inside_loop_p (loop, def_bb)))
1960 return chrec;
1962 /* We cache the value of instantiated variable to avoid exponential
1963 time complexity due to reevaluations. We also store the convenient
1964 value in the cache in order to prevent infinite recursion -- we do
1965 not want to instantiate the SSA_NAME if it is in a mixer
1966 structure. This is used for avoiding the instantiation of
1967 recursively defined functions, such as:
1969 | a_2 -> {0, +, 1, +, a_2}_1 */
1971 res = get_instantiated_value (cache, chrec);
1972 if (res)
1973 return res;
1975 /* Store the convenient value for chrec in the structure. If it
1976 is defined outside of the loop, we may just leave it in symbolic
1977 form, otherwise we need to admit that we do not know its behavior
1978 inside the loop. */
1979 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1980 set_instantiated_value (cache, chrec, res);
1982 /* To make things even more complicated, instantiate_parameters_1
1983 calls analyze_scalar_evolution that may call # of iterations
1984 analysis that may in turn call instantiate_parameters_1 again.
1985 To prevent the infinite recursion, keep also the bitmap of
1986 ssa names that are being instantiated globally. */
1987 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
1988 return res;
1990 def_loop = find_common_loop (loop, def_bb->loop_father);
1992 /* If the analysis yields a parametric chrec, instantiate the
1993 result again. */
1994 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
1995 res = analyze_scalar_evolution (def_loop, chrec);
1996 if (res != chrec_dont_know)
1997 res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs,
1998 cache);
1999 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2001 /* Store the correct value to the cache. */
2002 set_instantiated_value (cache, chrec, res);
2003 return res;
2005 case POLYNOMIAL_CHREC:
2006 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2007 allow_superloop_chrecs, cache);
2008 if (op0 == chrec_dont_know)
2009 return chrec_dont_know;
2011 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2012 allow_superloop_chrecs, cache);
2013 if (op1 == chrec_dont_know)
2014 return chrec_dont_know;
2016 if (CHREC_LEFT (chrec) != op0
2017 || CHREC_RIGHT (chrec) != op1)
2018 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2019 return chrec;
2021 case PLUS_EXPR:
2022 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2023 allow_superloop_chrecs, cache);
2024 if (op0 == chrec_dont_know)
2025 return chrec_dont_know;
2027 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2028 allow_superloop_chrecs, cache);
2029 if (op1 == chrec_dont_know)
2030 return chrec_dont_know;
2032 if (TREE_OPERAND (chrec, 0) != op0
2033 || TREE_OPERAND (chrec, 1) != op1)
2034 chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
2035 return chrec;
2037 case MINUS_EXPR:
2038 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2039 allow_superloop_chrecs, cache);
2040 if (op0 == chrec_dont_know)
2041 return chrec_dont_know;
2043 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2044 allow_superloop_chrecs, cache);
2045 if (op1 == chrec_dont_know)
2046 return chrec_dont_know;
2048 if (TREE_OPERAND (chrec, 0) != op0
2049 || TREE_OPERAND (chrec, 1) != op1)
2050 chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
2051 return chrec;
2053 case MULT_EXPR:
2054 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2055 allow_superloop_chrecs, cache);
2056 if (op0 == chrec_dont_know)
2057 return chrec_dont_know;
2059 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2060 allow_superloop_chrecs, cache);
2061 if (op1 == chrec_dont_know)
2062 return chrec_dont_know;
2064 if (TREE_OPERAND (chrec, 0) != op0
2065 || TREE_OPERAND (chrec, 1) != op1)
2066 chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
2067 return chrec;
2069 case NOP_EXPR:
2070 case CONVERT_EXPR:
2071 case NON_LVALUE_EXPR:
2072 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2073 allow_superloop_chrecs, cache);
2074 if (op0 == chrec_dont_know)
2075 return chrec_dont_know;
2077 if (op0 == TREE_OPERAND (chrec, 0))
2078 return chrec;
2080 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2082 case SCEV_NOT_KNOWN:
2083 return chrec_dont_know;
2085 case SCEV_KNOWN:
2086 return chrec_known;
2088 default:
2089 break;
2092 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2094 case 3:
2095 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2096 allow_superloop_chrecs, cache);
2097 if (op0 == chrec_dont_know)
2098 return chrec_dont_know;
2100 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2101 allow_superloop_chrecs, cache);
2102 if (op1 == chrec_dont_know)
2103 return chrec_dont_know;
2105 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2106 allow_superloop_chrecs, cache);
2107 if (op2 == chrec_dont_know)
2108 return chrec_dont_know;
2110 if (op0 == TREE_OPERAND (chrec, 0)
2111 && op1 == TREE_OPERAND (chrec, 1)
2112 && op2 == TREE_OPERAND (chrec, 2))
2113 return chrec;
2115 return fold_build3 (TREE_CODE (chrec),
2116 TREE_TYPE (chrec), op0, op1, op2);
2118 case 2:
2119 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2120 allow_superloop_chrecs, cache);
2121 if (op0 == chrec_dont_know)
2122 return chrec_dont_know;
2124 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2125 allow_superloop_chrecs, cache);
2126 if (op1 == chrec_dont_know)
2127 return chrec_dont_know;
2129 if (op0 == TREE_OPERAND (chrec, 0)
2130 && op1 == TREE_OPERAND (chrec, 1))
2131 return chrec;
2132 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2134 case 1:
2135 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2136 allow_superloop_chrecs, cache);
2137 if (op0 == chrec_dont_know)
2138 return chrec_dont_know;
2139 if (op0 == TREE_OPERAND (chrec, 0))
2140 return chrec;
2141 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2143 case 0:
2144 return chrec;
2146 default:
2147 break;
2150 /* Too complicated to handle. */
2151 return chrec_dont_know;
2154 /* Analyze all the parameters of the chrec that were left under a
2155 symbolic form. LOOP is the loop in which symbolic names have to
2156 be analyzed and instantiated. */
2158 tree
2159 instantiate_parameters (struct loop *loop,
2160 tree chrec)
2162 tree res;
2163 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2165 if (dump_file && (dump_flags & TDF_DETAILS))
2167 fprintf (dump_file, "(instantiate_parameters \n");
2168 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2169 fprintf (dump_file, " (chrec = ");
2170 print_generic_expr (dump_file, chrec, 0);
2171 fprintf (dump_file, ")\n");
2174 res = instantiate_parameters_1 (loop, chrec, true, cache);
2176 if (dump_file && (dump_flags & TDF_DETAILS))
2178 fprintf (dump_file, " (res = ");
2179 print_generic_expr (dump_file, res, 0);
2180 fprintf (dump_file, "))\n");
2183 htab_delete (cache);
2185 return res;
2188 /* Similar to instantiate_parameters, but does not introduce the
2189 evolutions in outer loops for LOOP invariants in CHREC. */
2191 static tree
2192 resolve_mixers (struct loop *loop, tree chrec)
2194 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2195 tree ret = instantiate_parameters_1 (loop, chrec, false, cache);
2196 htab_delete (cache);
2197 return ret;
2200 /* Entry point for the analysis of the number of iterations pass.
2201 This function tries to safely approximate the number of iterations
2202 the loop will run. When this property is not decidable at compile
2203 time, the result is chrec_dont_know. Otherwise the result is
2204 a scalar or a symbolic parameter.
2206 Example of analysis: suppose that the loop has an exit condition:
2208 "if (b > 49) goto end_loop;"
2210 and that in a previous analysis we have determined that the
2211 variable 'b' has an evolution function:
2213 "EF = {23, +, 5}_2".
2215 When we evaluate the function at the point 5, i.e. the value of the
2216 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2217 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2218 the loop body has been executed 6 times. */
2220 tree
2221 number_of_iterations_in_loop (struct loop *loop)
2223 tree res, type;
2224 edge exit;
2225 struct tree_niter_desc niter_desc;
2227 /* Determine whether the number_of_iterations_in_loop has already
2228 been computed. */
2229 res = loop->nb_iterations;
2230 if (res)
2231 return res;
2232 res = chrec_dont_know;
2234 if (dump_file && (dump_flags & TDF_DETAILS))
2235 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2237 exit = loop->single_exit;
2238 if (!exit)
2239 goto end;
2241 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2242 goto end;
2244 type = TREE_TYPE (niter_desc.niter);
2245 if (integer_nonzerop (niter_desc.may_be_zero))
2246 res = build_int_cst (type, 0);
2247 else if (integer_zerop (niter_desc.may_be_zero))
2248 res = niter_desc.niter;
2249 else
2250 res = chrec_dont_know;
2252 end:
2253 return set_nb_iterations_in_loop (loop, res);
2256 /* One of the drivers for testing the scalar evolutions analysis.
2257 This function computes the number of iterations for all the loops
2258 from the EXIT_CONDITIONS array. */
2260 static void
2261 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2263 unsigned int i;
2264 unsigned nb_chrec_dont_know_loops = 0;
2265 unsigned nb_static_loops = 0;
2266 tree cond;
2268 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2270 tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
2271 if (chrec_contains_undetermined (res))
2272 nb_chrec_dont_know_loops++;
2273 else
2274 nb_static_loops++;
2277 if (dump_file)
2279 fprintf (dump_file, "\n(\n");
2280 fprintf (dump_file, "-----------------------------------------\n");
2281 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2282 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2283 fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2284 fprintf (dump_file, "-----------------------------------------\n");
2285 fprintf (dump_file, ")\n\n");
2287 print_loop_ir (dump_file);
2293 /* Counters for the stats. */
2295 struct chrec_stats
2297 unsigned nb_chrecs;
2298 unsigned nb_affine;
2299 unsigned nb_affine_multivar;
2300 unsigned nb_higher_poly;
2301 unsigned nb_chrec_dont_know;
2302 unsigned nb_undetermined;
2305 /* Reset the counters. */
2307 static inline void
2308 reset_chrecs_counters (struct chrec_stats *stats)
2310 stats->nb_chrecs = 0;
2311 stats->nb_affine = 0;
2312 stats->nb_affine_multivar = 0;
2313 stats->nb_higher_poly = 0;
2314 stats->nb_chrec_dont_know = 0;
2315 stats->nb_undetermined = 0;
2318 /* Dump the contents of a CHREC_STATS structure. */
2320 static void
2321 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2323 fprintf (file, "\n(\n");
2324 fprintf (file, "-----------------------------------------\n");
2325 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2326 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2327 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2328 stats->nb_higher_poly);
2329 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2330 fprintf (file, "-----------------------------------------\n");
2331 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2332 fprintf (file, "%d\twith undetermined coefficients\n",
2333 stats->nb_undetermined);
2334 fprintf (file, "-----------------------------------------\n");
2335 fprintf (file, "%d\tchrecs in the scev database\n",
2336 (int) htab_elements (scalar_evolution_info));
2337 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2338 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2339 fprintf (file, "-----------------------------------------\n");
2340 fprintf (file, ")\n\n");
2343 /* Gather statistics about CHREC. */
2345 static void
2346 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2348 if (dump_file && (dump_flags & TDF_STATS))
2350 fprintf (dump_file, "(classify_chrec ");
2351 print_generic_expr (dump_file, chrec, 0);
2352 fprintf (dump_file, "\n");
2355 stats->nb_chrecs++;
2357 if (chrec == NULL_TREE)
2359 stats->nb_undetermined++;
2360 return;
2363 switch (TREE_CODE (chrec))
2365 case POLYNOMIAL_CHREC:
2366 if (evolution_function_is_affine_p (chrec))
2368 if (dump_file && (dump_flags & TDF_STATS))
2369 fprintf (dump_file, " affine_univariate\n");
2370 stats->nb_affine++;
2372 else if (evolution_function_is_affine_multivariate_p (chrec))
2374 if (dump_file && (dump_flags & TDF_STATS))
2375 fprintf (dump_file, " affine_multivariate\n");
2376 stats->nb_affine_multivar++;
2378 else
2380 if (dump_file && (dump_flags & TDF_STATS))
2381 fprintf (dump_file, " higher_degree_polynomial\n");
2382 stats->nb_higher_poly++;
2385 break;
2387 default:
2388 break;
2391 if (chrec_contains_undetermined (chrec))
2393 if (dump_file && (dump_flags & TDF_STATS))
2394 fprintf (dump_file, " undetermined\n");
2395 stats->nb_undetermined++;
2398 if (dump_file && (dump_flags & TDF_STATS))
2399 fprintf (dump_file, ")\n");
2402 /* One of the drivers for testing the scalar evolutions analysis.
2403 This function analyzes the scalar evolution of all the scalars
2404 defined as loop phi nodes in one of the loops from the
2405 EXIT_CONDITIONS array.
2407 TODO Optimization: A loop is in canonical form if it contains only
2408 a single scalar loop phi node. All the other scalars that have an
2409 evolution in the loop are rewritten in function of this single
2410 index. This allows the parallelization of the loop. */
2412 static void
2413 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2415 unsigned int i;
2416 struct chrec_stats stats;
2417 tree cond;
2419 reset_chrecs_counters (&stats);
2421 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2423 struct loop *loop;
2424 basic_block bb;
2425 tree phi, chrec;
2427 loop = loop_containing_stmt (cond);
2428 bb = loop->header;
2430 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2431 if (is_gimple_reg (PHI_RESULT (phi)))
2433 chrec = instantiate_parameters
2434 (loop,
2435 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2437 if (dump_file && (dump_flags & TDF_STATS))
2438 gather_chrec_stats (chrec, &stats);
2442 if (dump_file && (dump_flags & TDF_STATS))
2443 dump_chrecs_stats (dump_file, &stats);
2446 /* Callback for htab_traverse, gathers information on chrecs in the
2447 hashtable. */
2449 static int
2450 gather_stats_on_scev_database_1 (void **slot, void *stats)
2452 struct scev_info_str *entry = *slot;
2454 gather_chrec_stats (entry->chrec, stats);
2456 return 1;
2459 /* Classify the chrecs of the whole database. */
2461 void
2462 gather_stats_on_scev_database (void)
2464 struct chrec_stats stats;
2466 if (!dump_file)
2467 return;
2469 reset_chrecs_counters (&stats);
2471 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2472 &stats);
2474 dump_chrecs_stats (dump_file, &stats);
2479 /* Initializer. */
2481 static void
2482 initialize_scalar_evolutions_analyzer (void)
2484 /* The elements below are unique. */
2485 if (chrec_dont_know == NULL_TREE)
2487 chrec_not_analyzed_yet = NULL_TREE;
2488 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2489 chrec_known = make_node (SCEV_KNOWN);
2490 TREE_TYPE (chrec_dont_know) = void_type_node;
2491 TREE_TYPE (chrec_known) = void_type_node;
2495 /* Initialize the analysis of scalar evolutions for LOOPS. */
2497 void
2498 scev_initialize (struct loops *loops)
2500 unsigned i;
2501 current_loops = loops;
2503 scalar_evolution_info = htab_create (100, hash_scev_info,
2504 eq_scev_info, del_scev_info);
2505 already_instantiated = BITMAP_ALLOC (NULL);
2507 initialize_scalar_evolutions_analyzer ();
2509 for (i = 1; i < loops->num; i++)
2510 if (loops->parray[i])
2511 loops->parray[i]->nb_iterations = NULL_TREE;
2514 /* Cleans up the information cached by the scalar evolutions analysis. */
2516 void
2517 scev_reset (void)
2519 unsigned i;
2520 struct loop *loop;
2522 if (!scalar_evolution_info || !current_loops)
2523 return;
2525 htab_empty (scalar_evolution_info);
2526 for (i = 1; i < current_loops->num; i++)
2528 loop = current_loops->parray[i];
2529 if (loop)
2530 loop->nb_iterations = NULL_TREE;
2534 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2535 its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
2536 want STEP to be invariant in LOOP. Otherwise we require it to be an
2537 integer constant. */
2539 bool
2540 simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step,
2541 bool allow_nonconstant_step)
2543 basic_block bb = bb_for_stmt (stmt);
2544 tree type, ev;
2546 *base = NULL_TREE;
2547 *step = NULL_TREE;
2549 type = TREE_TYPE (op);
2550 if (TREE_CODE (type) != INTEGER_TYPE
2551 && TREE_CODE (type) != POINTER_TYPE)
2552 return false;
2554 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
2555 if (chrec_contains_undetermined (ev))
2556 return false;
2558 if (tree_does_not_contain_chrecs (ev)
2559 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2561 *base = ev;
2562 return true;
2565 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2566 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2567 return false;
2569 *step = CHREC_RIGHT (ev);
2570 if (allow_nonconstant_step)
2572 if (tree_contains_chrecs (*step, NULL)
2573 || chrec_contains_symbols_defined_in_loop (*step, loop->num))
2574 return false;
2576 else if (TREE_CODE (*step) != INTEGER_CST)
2577 return false;
2579 *base = CHREC_LEFT (ev);
2580 if (tree_contains_chrecs (*base, NULL)
2581 || chrec_contains_symbols_defined_in_loop (*base, loop->num))
2582 return false;
2584 return true;
2587 /* Runs the analysis of scalar evolutions. */
2589 void
2590 scev_analysis (void)
2592 VEC(tree,heap) *exit_conditions;
2594 exit_conditions = VEC_alloc (tree, heap, 37);
2595 select_loops_exit_conditions (current_loops, &exit_conditions);
2597 if (dump_file && (dump_flags & TDF_STATS))
2598 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2600 number_of_iterations_for_all_loops (&exit_conditions);
2601 VEC_free (tree, heap, exit_conditions);
2604 /* Finalize the scalar evolution analysis. */
2606 void
2607 scev_finalize (void)
2609 htab_delete (scalar_evolution_info);
2610 BITMAP_FREE (already_instantiated);
2613 /* Replace ssa names for that scev can prove they are constant by the
2614 appropriate constants. Also perform final value replacement in loops,
2615 in case the replacement expressions are cheap.
2617 We only consider SSA names defined by phi nodes; rest is left to the
2618 ordinary constant propagation pass. */
2620 void
2621 scev_const_prop (void)
2623 basic_block bb;
2624 tree name, phi, next_phi, type, ev;
2625 struct loop *loop, *ex_loop;
2626 bitmap ssa_names_to_remove = NULL;
2627 unsigned i;
2629 if (!current_loops)
2630 return;
2632 FOR_EACH_BB (bb)
2634 loop = bb->loop_father;
2636 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2638 name = PHI_RESULT (phi);
2640 if (!is_gimple_reg (name))
2641 continue;
2643 type = TREE_TYPE (name);
2645 if (!POINTER_TYPE_P (type)
2646 && !INTEGRAL_TYPE_P (type))
2647 continue;
2649 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2650 if (!is_gimple_min_invariant (ev)
2651 || !may_propagate_copy (name, ev))
2652 continue;
2654 /* Replace the uses of the name. */
2655 replace_uses_by (name, ev);
2657 if (!ssa_names_to_remove)
2658 ssa_names_to_remove = BITMAP_ALLOC (NULL);
2659 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2663 /* Remove the ssa names that were replaced by constants. We do not remove them
2664 directly in the previous cycle, since this invalidates scev cache. */
2665 if (ssa_names_to_remove)
2667 bitmap_iterator bi;
2668 unsigned i;
2670 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2672 name = ssa_name (i);
2673 phi = SSA_NAME_DEF_STMT (name);
2675 gcc_assert (TREE_CODE (phi) == PHI_NODE);
2676 remove_phi_node (phi, NULL);
2679 BITMAP_FREE (ssa_names_to_remove);
2680 scev_reset ();
2683 /* Now the regular final value replacement. */
2684 for (i = current_loops->num - 1; i > 0; i--)
2686 edge exit;
2687 tree def, stmts;
2689 loop = current_loops->parray[i];
2690 if (!loop)
2691 continue;
2693 /* If we do not know exact number of iterations of the loop, we cannot
2694 replace the final value. */
2695 exit = loop->single_exit;
2696 if (!exit
2697 || number_of_iterations_in_loop (loop) == chrec_dont_know)
2698 continue;
2699 ex_loop = exit->dest->loop_father;
2701 for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2703 next_phi = PHI_CHAIN (phi);
2704 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2705 if (!is_gimple_reg (def)
2706 || expr_invariant_in_loop_p (loop, def))
2707 continue;
2709 if (!POINTER_TYPE_P (TREE_TYPE (def))
2710 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2711 continue;
2713 def = analyze_scalar_evolution_in_loop (ex_loop, ex_loop, def);
2714 if (!tree_does_not_contain_chrecs (def)
2715 || chrec_contains_symbols_defined_in_loop (def, loop->num))
2716 continue;
2718 /* If computing the expression is expensive, let it remain in
2719 loop. TODO -- we should take the cost of computing the expression
2720 in loop into account. */
2721 if (force_expr_to_var_cost (def) >= target_spill_cost)
2722 continue;
2723 def = unshare_expr (def);
2725 if (is_gimple_val (def))
2726 stmts = NULL_TREE;
2727 else
2728 def = force_gimple_operand (def, &stmts, true,
2729 SSA_NAME_VAR (PHI_RESULT (phi)));
2730 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit), def);
2731 if (stmts)
2732 compute_phi_arg_on_exit (exit, stmts, def);