1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004 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
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
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, 59 Temple Place - Suite 330, Boston, MA
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
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.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
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:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2: Illustration of the algorithm on nested loops.
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:
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:
158 Example 3: Higher degree polynomials.
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.
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.
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
214 This transformation is not yet implemented.
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
236 #include "coretypes.h"
242 /* These RTL headers are needed for basic-block.h. */
244 #include "basic-block.h"
245 #include "diagnostic.h"
246 #include "tree-flow.h"
247 #include "tree-dump.h"
250 #include "tree-chrec.h"
251 #include "tree-scalar-evolution.h"
252 #include "tree-pass.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. */
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. */
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));
300 res->chrec = chrec_not_analyzed_yet;
305 /* Computes a hash function for database element ELT. */
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. */
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. */
327 del_scev_info (void *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. */
337 find_var_scev_info (tree var)
339 struct scev_info_str *res;
340 struct scev_info_str tmp;
344 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
347 *slot = new_scev_info_str (var);
353 /* Tries to express CHREC in wider type TYPE. */
356 count_ev_in_wider_type (tree type, tree chrec)
361 if (!evolution_function_is_affine_p (chrec))
362 return fold_convert (type, chrec);
364 base = CHREC_LEFT (chrec);
365 step = CHREC_RIGHT (chrec);
366 loop = current_loops->parray[CHREC_VARIABLE (chrec)];
368 /* TODO -- if we knew the statement at that the conversion occurs,
369 we could pass it to can_count_iv_in_wider_type and get a better
371 step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
373 return fold_convert (type, chrec);
374 base = chrec_convert (type, base);
376 return build_polynomial_chrec (CHREC_VARIABLE (chrec),
380 /* Return true when CHREC contains symbolic names defined in
384 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
386 if (chrec == NULL_TREE)
389 if (TREE_INVARIANT (chrec))
392 if (TREE_CODE (chrec) == VAR_DECL
393 || TREE_CODE (chrec) == PARM_DECL
394 || TREE_CODE (chrec) == FUNCTION_DECL
395 || TREE_CODE (chrec) == LABEL_DECL
396 || TREE_CODE (chrec) == RESULT_DECL
397 || TREE_CODE (chrec) == FIELD_DECL)
400 if (TREE_CODE (chrec) == SSA_NAME)
402 tree def = SSA_NAME_DEF_STMT (chrec);
403 struct loop *def_loop = loop_containing_stmt (def);
404 struct loop *loop = current_loops->parray[loop_nb];
406 if (def_loop == NULL)
409 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
415 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
418 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
423 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
428 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
437 /* Return true when PHI is a loop-phi-node. */
440 loop_phi_node_p (tree phi)
442 /* The implementation of this function is based on the following
443 property: "all the loop-phi-nodes of a loop are contained in the
444 loop's header basic block". */
446 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
449 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
450 In general, in the case of multivariate evolutions we want to get
451 the evolution in different loops. LOOP specifies the level for
452 which to get the evolution.
456 | for (j = 0; j < 100; j++)
458 | for (k = 0; k < 100; k++)
460 | i = k + j; - Here the value of i is a function of j, k.
462 | ... = i - Here the value of i is a function of j.
464 | ... = i - Here the value of i is a scalar.
470 | i_1 = phi (i_0, i_2)
474 This loop has the same effect as:
475 LOOP_1 has the same effect as:
479 The overall effect of the loop, "i_0 + 20" in the previous example,
480 is obtained by passing in the parameters: LOOP = 1,
481 EVOLUTION_FN = {i_0, +, 2}_1.
485 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
489 if (evolution_fn == chrec_dont_know)
490 return chrec_dont_know;
492 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
494 if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
496 struct loop *inner_loop =
497 current_loops->parray[CHREC_VARIABLE (evolution_fn)];
498 tree nb_iter = number_of_iterations_in_loop (inner_loop);
500 if (nb_iter == chrec_dont_know)
501 return chrec_dont_know;
506 /* Number of iterations is off by one (the ssa name we
507 analyze must be defined before the exit). */
508 nb_iter = chrec_fold_minus (chrec_type (nb_iter),
510 build_int_cst_type (chrec_type (nb_iter), 1));
512 /* evolution_fn is the evolution function in LOOP. Get
513 its value in the nb_iter-th iteration. */
514 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
516 /* Continue the computation until ending on a parent of LOOP. */
517 return compute_overall_effect_of_inner_loop (loop, res);
524 /* If the evolution function is an invariant, there is nothing to do. */
525 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
529 return chrec_dont_know;
532 /* Determine whether the CHREC is always positive/negative. If the expression
533 cannot be statically analyzed, return false, otherwise set the answer into
537 chrec_is_positive (tree chrec, bool *value)
544 switch (TREE_CODE (chrec))
546 case POLYNOMIAL_CHREC:
547 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
548 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
551 /* FIXME -- overflows. */
552 if (value0 == value1)
558 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
559 and the proof consists in showing that the sign never
560 changes during the execution of the loop, from 0 to
561 loop->nb_iterations. */
562 if (!evolution_function_is_affine_p (chrec))
565 nb_iter = number_of_iterations_in_loop
566 (current_loops->parray[CHREC_VARIABLE (chrec)]);
568 if (chrec_contains_undetermined (nb_iter))
571 nb_iter = chrec_fold_minus
572 (chrec_type (nb_iter), nb_iter,
573 build_int_cst (chrec_type (nb_iter), 1));
576 /* TODO -- If the test is after the exit, we may decrease the number of
577 iterations by one. */
579 nb_iter = chrec_fold_minus
580 (chrec_type (nb_iter), nb_iter,
581 build_int_cst (chrec_type (nb_iter), 1));
584 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
586 if (!chrec_is_positive (end_value, &value2))
590 return value0 == value1;
593 *value = (tree_int_cst_sgn (chrec) == 1);
601 /* Associate CHREC to SCALAR. */
604 set_scalar_evolution (tree scalar, tree chrec)
608 if (TREE_CODE (scalar) != SSA_NAME)
611 scalar_info = find_var_scev_info (scalar);
615 if (dump_flags & TDF_DETAILS)
617 fprintf (dump_file, "(set_scalar_evolution \n");
618 fprintf (dump_file, " (scalar = ");
619 print_generic_expr (dump_file, scalar, 0);
620 fprintf (dump_file, ")\n (scalar_evolution = ");
621 print_generic_expr (dump_file, chrec, 0);
622 fprintf (dump_file, "))\n");
624 if (dump_flags & TDF_STATS)
628 *scalar_info = chrec;
631 /* Retrieve the chrec associated to SCALAR in the LOOP. */
634 get_scalar_evolution (tree scalar)
640 if (dump_flags & TDF_DETAILS)
642 fprintf (dump_file, "(get_scalar_evolution \n");
643 fprintf (dump_file, " (scalar = ");
644 print_generic_expr (dump_file, scalar, 0);
645 fprintf (dump_file, ")\n");
647 if (dump_flags & TDF_STATS)
651 switch (TREE_CODE (scalar))
654 res = *find_var_scev_info (scalar);
663 res = chrec_not_analyzed_yet;
667 if (dump_file && (dump_flags & TDF_DETAILS))
669 fprintf (dump_file, " (scalar_evolution = ");
670 print_generic_expr (dump_file, res, 0);
671 fprintf (dump_file, "))\n");
677 /* Helper function for add_to_evolution. Returns the evolution
678 function for an assignment of the form "a = b + c", where "a" and
679 "b" are on the strongly connected component. CHREC_BEFORE is the
680 information that we already have collected up to this point.
681 TO_ADD is the evolution of "c".
683 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
684 evolution the expression TO_ADD, otherwise construct an evolution
685 part for this loop. */
688 add_to_evolution_1 (unsigned loop_nb,
692 switch (TREE_CODE (chrec_before))
694 case POLYNOMIAL_CHREC:
695 if (CHREC_VARIABLE (chrec_before) <= loop_nb)
699 tree type = chrec_type (chrec_before);
701 /* When there is no evolution part in this loop, build it. */
702 if (CHREC_VARIABLE (chrec_before) < loop_nb)
706 right = build_int_cst (type, 0);
710 var = CHREC_VARIABLE (chrec_before);
711 left = CHREC_LEFT (chrec_before);
712 right = CHREC_RIGHT (chrec_before);
715 return build_polynomial_chrec
716 (var, left, chrec_fold_plus (type, right, to_add));
719 /* Search the evolution in LOOP_NB. */
720 return build_polynomial_chrec
721 (CHREC_VARIABLE (chrec_before),
722 add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
723 CHREC_RIGHT (chrec_before));
726 /* These nodes do not depend on a loop. */
727 if (chrec_before == chrec_dont_know)
728 return chrec_dont_know;
729 return build_polynomial_chrec (loop_nb, chrec_before, to_add);
733 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
736 Description (provided for completeness, for those who read code in
737 a plane, and for my poor 62 bytes brain that would have forgotten
738 all this in the next two or three months):
740 The algorithm of translation of programs from the SSA representation
741 into the chrecs syntax is based on a pattern matching. After having
742 reconstructed the overall tree expression for a loop, there are only
743 two cases that can arise:
745 1. a = loop-phi (init, a + expr)
746 2. a = loop-phi (init, expr)
748 where EXPR is either a scalar constant with respect to the analyzed
749 loop (this is a degree 0 polynomial), or an expression containing
750 other loop-phi definitions (these are higher degree polynomials).
757 | a = phi (init, a + 5)
764 | a = phi (inita, 2 * b + 3)
765 | b = phi (initb, b + 1)
768 For the first case, the semantics of the SSA representation is:
770 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
772 that is, there is a loop index "x" that determines the scalar value
773 of the variable during the loop execution. During the first
774 iteration, the value is that of the initial condition INIT, while
775 during the subsequent iterations, it is the sum of the initial
776 condition with the sum of all the values of EXPR from the initial
777 iteration to the before last considered iteration.
779 For the second case, the semantics of the SSA program is:
781 | a (x) = init, if x = 0;
782 | expr (x - 1), otherwise.
784 The second case corresponds to the PEELED_CHREC, whose syntax is
785 close to the syntax of a loop-phi-node:
787 | phi (init, expr) vs. (init, expr)_x
789 The proof of the translation algorithm for the first case is a
790 proof by structural induction based on the degree of EXPR.
793 When EXPR is a constant with respect to the analyzed loop, or in
794 other words when EXPR is a polynomial of degree 0, the evolution of
795 the variable A in the loop is an affine function with an initial
796 condition INIT, and a step EXPR. In order to show this, we start
797 from the semantics of the SSA representation:
799 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
801 and since "expr (j)" is a constant with respect to "j",
803 f (x) = init + x * expr
805 Finally, based on the semantics of the pure sum chrecs, by
806 identification we get the corresponding chrecs syntax:
808 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
809 f (x) -> {init, +, expr}_x
812 Suppose that EXPR is a polynomial of degree N with respect to the
813 analyzed loop_x for which we have already determined that it is
814 written under the chrecs syntax:
816 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
818 We start from the semantics of the SSA program:
820 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
822 | f (x) = init + \sum_{j = 0}^{x - 1}
823 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
825 | f (x) = init + \sum_{j = 0}^{x - 1}
826 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
828 | f (x) = init + \sum_{k = 0}^{n - 1}
829 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
831 | f (x) = init + \sum_{k = 0}^{n - 1}
832 | (b_k * \binom{x}{k + 1})
834 | f (x) = init + b_0 * \binom{x}{1} + ...
835 | + b_{n-1} * \binom{x}{n}
837 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
838 | + b_{n-1} * \binom{x}{n}
841 And finally from the definition of the chrecs syntax, we identify:
842 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
844 This shows the mechanism that stands behind the add_to_evolution
845 function. An important point is that the use of symbolic
846 parameters avoids the need of an analysis schedule.
853 | a = phi (inita, a + 2 + b)
854 | b = phi (initb, b + 1)
857 When analyzing "a", the algorithm keeps "b" symbolically:
859 | a -> {inita, +, 2 + b}_1
861 Then, after instantiation, the analyzer ends on the evolution:
863 | a -> {inita, +, 2 + initb, +, 1}_1
868 add_to_evolution (unsigned loop_nb,
873 tree type = chrec_type (to_add);
874 tree res = NULL_TREE;
876 if (to_add == NULL_TREE)
879 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
880 instantiated at this point. */
881 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
882 /* This should not happen. */
883 return chrec_dont_know;
885 if (dump_file && (dump_flags & TDF_DETAILS))
887 fprintf (dump_file, "(add_to_evolution \n");
888 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
889 fprintf (dump_file, " (chrec_before = ");
890 print_generic_expr (dump_file, chrec_before, 0);
891 fprintf (dump_file, ")\n (to_add = ");
892 print_generic_expr (dump_file, to_add, 0);
893 fprintf (dump_file, ")\n");
896 if (code == MINUS_EXPR)
897 to_add = chrec_fold_multiply (type, to_add,
898 build_int_cst_type (type, -1));
900 res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
902 if (dump_file && (dump_flags & TDF_DETAILS))
904 fprintf (dump_file, " (res = ");
905 print_generic_expr (dump_file, res, 0);
906 fprintf (dump_file, "))\n");
912 /* Helper function. */
915 set_nb_iterations_in_loop (struct loop *loop,
918 res = chrec_fold_plus (chrec_type (res), res,
919 build_int_cst_type (chrec_type (res), 1));
921 /* FIXME HWI: However we want to store one iteration less than the
922 count of the loop in order to be compatible with the other
923 nb_iter computations in loop-iv. This also allows the
924 representation of nb_iters that are equal to MAX_INT. */
925 if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
926 || TREE_OVERFLOW (res))
927 res = chrec_dont_know;
929 if (dump_file && (dump_flags & TDF_DETAILS))
931 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
932 print_generic_expr (dump_file, res, 0);
933 fprintf (dump_file, "))\n");
936 loop->nb_iterations = res;
942 /* This section selects the loops that will be good candidates for the
943 scalar evolution analysis. For the moment, greedily select all the
944 loop nests we could analyze. */
946 /* Return true when it is possible to analyze the condition expression
950 analyzable_condition (tree expr)
954 if (TREE_CODE (expr) != COND_EXPR)
957 condition = TREE_OPERAND (expr, 0);
959 switch (TREE_CODE (condition))
962 /* Volatile expressions are not analyzable. */
963 if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition)))
976 opnd0 = TREE_OPERAND (condition, 0);
977 opnd1 = TREE_OPERAND (condition, 1);
979 if (TREE_CODE (opnd0) == SSA_NAME
980 && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0)))
983 if (TREE_CODE (opnd1) == SSA_NAME
984 && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1)))
997 /* For a loop with a single exit edge, return the COND_EXPR that
998 guards the exit edge. If the expression is too difficult to
999 analyze, then give up. */
1002 get_loop_exit_condition (struct loop *loop)
1004 tree res = NULL_TREE;
1005 edge exit_edge = loop->single_exit;
1008 if (dump_file && (dump_flags & TDF_DETAILS))
1009 fprintf (dump_file, "(get_loop_exit_condition \n ");
1015 expr = last_stmt (exit_edge->src);
1016 if (analyzable_condition (expr))
1020 if (dump_file && (dump_flags & TDF_DETAILS))
1022 print_generic_expr (dump_file, res, 0);
1023 fprintf (dump_file, ")\n");
1029 /* Recursively determine and enqueue the exit conditions for a loop. */
1032 get_exit_conditions_rec (struct loop *loop,
1033 varray_type *exit_conditions)
1038 /* Recurse on the inner loops, then on the next (sibling) loops. */
1039 get_exit_conditions_rec (loop->inner, exit_conditions);
1040 get_exit_conditions_rec (loop->next, exit_conditions);
1042 if (loop->single_exit)
1044 tree loop_condition = get_loop_exit_condition (loop);
1047 VARRAY_PUSH_TREE (*exit_conditions, loop_condition);
1051 /* Select the candidate loop nests for the analysis. This function
1052 initializes the EXIT_CONDITIONS array. */
1055 select_loops_exit_conditions (struct loops *loops,
1056 varray_type *exit_conditions)
1058 struct loop *function_body = loops->parray[0];
1060 get_exit_conditions_rec (function_body->inner, exit_conditions);
1064 /* Depth first search algorithm. */
1066 static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
1068 /* Follow the ssa edge into the right hand side RHS of an assignment.
1069 Return true if the strongly connected component has been found. */
1072 follow_ssa_edge_in_rhs (struct loop *loop,
1075 tree *evolution_of_loop)
1079 tree type_rhs = TREE_TYPE (rhs);
1081 /* The RHS is one of the following cases:
1086 - other cases are not yet handled.
1088 switch (TREE_CODE (rhs))
1091 /* This assignment is under the form "a_1 = (cast) rhs. */
1092 res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
1094 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
1098 /* This assignment is under the form "a_1 = 7". */
1103 /* This assignment is under the form: "a_1 = b_2". */
1104 res = follow_ssa_edge
1105 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
1109 /* This case is under the form "rhs0 + rhs1". */
1110 rhs0 = TREE_OPERAND (rhs, 0);
1111 rhs1 = TREE_OPERAND (rhs, 1);
1112 STRIP_TYPE_NOPS (rhs0);
1113 STRIP_TYPE_NOPS (rhs1);
1115 if (TREE_CODE (rhs0) == SSA_NAME)
1117 if (TREE_CODE (rhs1) == SSA_NAME)
1119 /* Match an assignment under the form:
1121 res = follow_ssa_edge
1122 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1126 *evolution_of_loop = add_to_evolution
1128 chrec_convert (type_rhs, *evolution_of_loop),
1133 res = follow_ssa_edge
1134 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1138 *evolution_of_loop = add_to_evolution
1140 chrec_convert (type_rhs, *evolution_of_loop),
1147 /* Match an assignment under the form:
1149 res = follow_ssa_edge
1150 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1153 *evolution_of_loop = add_to_evolution
1154 (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1159 else if (TREE_CODE (rhs1) == SSA_NAME)
1161 /* Match an assignment under the form:
1163 res = follow_ssa_edge
1164 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1167 *evolution_of_loop = add_to_evolution
1168 (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1173 /* Otherwise, match an assignment under the form:
1175 /* And there is nothing to do. */
1181 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1182 rhs0 = TREE_OPERAND (rhs, 0);
1183 rhs1 = TREE_OPERAND (rhs, 1);
1184 STRIP_TYPE_NOPS (rhs0);
1185 STRIP_TYPE_NOPS (rhs1);
1187 if (TREE_CODE (rhs0) == SSA_NAME)
1189 /* Match an assignment under the form:
1191 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1194 *evolution_of_loop = add_to_evolution
1195 (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1199 /* Otherwise, match an assignment under the form:
1201 /* And there is nothing to do. */
1207 /* This case is under the form "opnd0 = rhs0 * rhs1". */
1208 rhs0 = TREE_OPERAND (rhs, 0);
1209 rhs1 = TREE_OPERAND (rhs, 1);
1210 STRIP_TYPE_NOPS (rhs0);
1211 STRIP_TYPE_NOPS (rhs1);
1213 if (TREE_CODE (rhs0) == SSA_NAME)
1215 if (TREE_CODE (rhs1) == SSA_NAME)
1217 /* Match an assignment under the form:
1219 res = follow_ssa_edge
1220 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1224 *evolution_of_loop = chrec_dont_know;
1228 res = follow_ssa_edge
1229 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1233 *evolution_of_loop = chrec_dont_know;
1239 /* Match an assignment under the form:
1241 res = follow_ssa_edge
1242 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1245 *evolution_of_loop = chrec_dont_know;
1249 else if (TREE_CODE (rhs1) == SSA_NAME)
1251 /* Match an assignment under the form:
1253 res = follow_ssa_edge
1254 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1257 *evolution_of_loop = chrec_dont_know;
1261 /* Otherwise, match an assignment under the form:
1263 /* And there is nothing to do. */
1276 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1279 backedge_phi_arg_p (tree phi, int i)
1281 edge e = PHI_ARG_EDGE (phi, i);
1283 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1284 about updating it anywhere, and this should work as well most of the
1286 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1292 /* Helper function for one branch of the condition-phi-node. Return
1293 true if the strongly connected component has been found following
1297 follow_ssa_edge_in_condition_phi_branch (int i,
1301 tree *evolution_of_branch,
1304 tree branch = PHI_ARG_DEF (condition_phi, i);
1305 *evolution_of_branch = chrec_dont_know;
1307 /* Do not follow back edges (they must belong to an irreducible loop, which
1308 we really do not want to worry about). */
1309 if (backedge_phi_arg_p (condition_phi, i))
1312 if (TREE_CODE (branch) == SSA_NAME)
1314 *evolution_of_branch = init_cond;
1315 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1316 evolution_of_branch);
1319 /* This case occurs when one of the condition branches sets
1320 the variable to a constant: i.e. a phi-node like
1321 "a_2 = PHI <a_7(5), 2(6)>;".
1323 FIXME: This case have to be refined correctly:
1324 in some cases it is possible to say something better than
1325 chrec_dont_know, for example using a wrap-around notation. */
1329 /* This function merges the branches of a condition-phi-node in a
1333 follow_ssa_edge_in_condition_phi (struct loop *loop,
1336 tree *evolution_of_loop)
1339 tree init = *evolution_of_loop;
1340 tree evolution_of_branch;
1342 if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1344 &evolution_of_branch,
1347 *evolution_of_loop = evolution_of_branch;
1349 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1351 /* Quickly give up when the evolution of one of the branches is
1353 if (*evolution_of_loop == chrec_dont_know)
1356 if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1358 &evolution_of_branch,
1362 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1363 evolution_of_branch);
1369 /* Follow an SSA edge in an inner loop. It computes the overall
1370 effect of the loop, and following the symbolic initial conditions,
1371 it follows the edges in the parent loop. The inner loop is
1372 considered as a single statement. */
1375 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1378 tree *evolution_of_loop)
1380 struct loop *loop = loop_containing_stmt (loop_phi_node);
1381 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1383 /* Sometimes, the inner loop is too difficult to analyze, and the
1384 result of the analysis is a symbolic parameter. */
1385 if (ev == PHI_RESULT (loop_phi_node))
1390 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1392 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1395 /* Follow the edges that exit the inner loop. */
1396 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1397 if (!flow_bb_inside_loop_p (loop, bb))
1398 res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
1402 /* If the path crosses this loop-phi, give up. */
1404 *evolution_of_loop = chrec_dont_know;
1409 /* Otherwise, compute the overall effect of the inner loop. */
1410 ev = compute_overall_effect_of_inner_loop (loop, ev);
1411 return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
1415 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1416 path that is analyzed on the return walk. */
1419 follow_ssa_edge (struct loop *loop,
1422 tree *evolution_of_loop)
1424 struct loop *def_loop;
1426 if (TREE_CODE (def) == NOP_EXPR)
1429 def_loop = loop_containing_stmt (def);
1431 switch (TREE_CODE (def))
1434 if (!loop_phi_node_p (def))
1435 /* DEF is a condition-phi-node. Follow the branches, and
1436 record their evolutions. Finally, merge the collected
1437 information and set the approximation to the main
1439 return follow_ssa_edge_in_condition_phi
1440 (loop, def, halting_phi, evolution_of_loop);
1442 /* When the analyzed phi is the halting_phi, the
1443 depth-first search is over: we have found a path from
1444 the halting_phi to itself in the loop. */
1445 if (def == halting_phi)
1448 /* Otherwise, the evolution of the HALTING_PHI depends
1449 on the evolution of another loop-phi-node, i.e. the
1450 evolution function is a higher degree polynomial. */
1451 if (def_loop == loop)
1455 if (flow_loop_nested_p (loop, def_loop))
1456 return follow_ssa_edge_inner_loop_phi
1457 (loop, def, halting_phi, evolution_of_loop);
1463 return follow_ssa_edge_in_rhs (loop,
1464 TREE_OPERAND (def, 1),
1469 /* At this level of abstraction, the program is just a set
1470 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1471 other node to be handled. */
1478 /* Given a LOOP_PHI_NODE, this function determines the evolution
1479 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1482 analyze_evolution_in_loop (tree loop_phi_node,
1486 tree evolution_function = chrec_not_analyzed_yet;
1487 struct loop *loop = loop_containing_stmt (loop_phi_node);
1490 if (dump_file && (dump_flags & TDF_DETAILS))
1492 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1493 fprintf (dump_file, " (loop_phi_node = ");
1494 print_generic_expr (dump_file, loop_phi_node, 0);
1495 fprintf (dump_file, ")\n");
1498 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1500 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1501 tree ssa_chain, ev_fn;
1504 /* Select the edges that enter the loop body. */
1505 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1506 if (!flow_bb_inside_loop_p (loop, bb))
1509 if (TREE_CODE (arg) == SSA_NAME)
1511 ssa_chain = SSA_NAME_DEF_STMT (arg);
1513 /* Pass in the initial condition to the follow edge function. */
1515 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
1520 /* When it is impossible to go back on the same
1521 loop_phi_node by following the ssa edges, the
1522 evolution is represented by a peeled chrec, i.e. the
1523 first iteration, EV_FN has the value INIT_COND, then
1524 all the other iterations it has the value of ARG.
1525 For the moment, PEELED_CHREC nodes are not built. */
1527 ev_fn = chrec_dont_know;
1529 /* When there are multiple back edges of the loop (which in fact never
1530 happens currently, but nevertheless), merge their evolutions. */
1531 evolution_function = chrec_merge (evolution_function, ev_fn);
1534 if (dump_file && (dump_flags & TDF_DETAILS))
1536 fprintf (dump_file, " (evolution_function = ");
1537 print_generic_expr (dump_file, evolution_function, 0);
1538 fprintf (dump_file, "))\n");
1541 return evolution_function;
1544 /* Given a loop-phi-node, return the initial conditions of the
1545 variable on entry of the loop. When the CCP has propagated
1546 constants into the loop-phi-node, the initial condition is
1547 instantiated, otherwise the initial condition is kept symbolic.
1548 This analyzer does not analyze the evolution outside the current
1549 loop, and leaves this task to the on-demand tree reconstructor. */
1552 analyze_initial_condition (tree loop_phi_node)
1555 tree init_cond = chrec_not_analyzed_yet;
1556 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1558 if (dump_file && (dump_flags & TDF_DETAILS))
1560 fprintf (dump_file, "(analyze_initial_condition \n");
1561 fprintf (dump_file, " (loop_phi_node = \n");
1562 print_generic_expr (dump_file, loop_phi_node, 0);
1563 fprintf (dump_file, ")\n");
1566 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1568 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1569 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1571 /* When the branch is oriented to the loop's body, it does
1572 not contribute to the initial condition. */
1573 if (flow_bb_inside_loop_p (loop, bb))
1576 if (init_cond == chrec_not_analyzed_yet)
1582 if (TREE_CODE (branch) == SSA_NAME)
1584 init_cond = chrec_dont_know;
1588 init_cond = chrec_merge (init_cond, branch);
1591 /* Ooops -- a loop without an entry??? */
1592 if (init_cond == chrec_not_analyzed_yet)
1593 init_cond = chrec_dont_know;
1595 if (dump_file && (dump_flags & TDF_DETAILS))
1597 fprintf (dump_file, " (init_cond = ");
1598 print_generic_expr (dump_file, init_cond, 0);
1599 fprintf (dump_file, "))\n");
1605 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1608 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1611 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1614 if (phi_loop != loop)
1616 struct loop *subloop;
1617 tree evolution_fn = analyze_scalar_evolution
1618 (phi_loop, PHI_RESULT (loop_phi_node));
1620 /* Dive one level deeper. */
1621 subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1623 /* Interpret the subloop. */
1624 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1628 /* Otherwise really interpret the loop phi. */
1629 init_cond = analyze_initial_condition (loop_phi_node);
1630 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1635 /* This function merges the branches of a condition-phi-node,
1636 contained in the outermost loop, and whose arguments are already
1640 interpret_condition_phi (struct loop *loop, tree condition_phi)
1643 tree res = chrec_not_analyzed_yet;
1645 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1649 if (backedge_phi_arg_p (condition_phi, i))
1651 res = chrec_dont_know;
1655 branch_chrec = analyze_scalar_evolution
1656 (loop, PHI_ARG_DEF (condition_phi, i));
1658 res = chrec_merge (res, branch_chrec);
1664 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1665 analyzed this node before, follow the definitions until ending
1666 either on an analyzed modify_expr, or on a loop-phi-node. On the
1667 return path, this function propagates evolutions (ala constant copy
1668 propagation). OPND1 is not a GIMPLE expression because we could
1669 analyze the effect of an inner loop: see interpret_loop_phi. */
1672 interpret_rhs_modify_expr (struct loop *loop,
1673 tree opnd1, tree type)
1675 tree res, opnd10, opnd11, chrec10, chrec11;
1677 if (is_gimple_min_invariant (opnd1))
1678 return chrec_convert (type, opnd1);
1680 switch (TREE_CODE (opnd1))
1683 opnd10 = TREE_OPERAND (opnd1, 0);
1684 opnd11 = TREE_OPERAND (opnd1, 1);
1685 chrec10 = analyze_scalar_evolution (loop, opnd10);
1686 chrec11 = analyze_scalar_evolution (loop, opnd11);
1687 chrec10 = chrec_convert (type, chrec10);
1688 chrec11 = chrec_convert (type, chrec11);
1689 res = chrec_fold_plus (type, chrec10, chrec11);
1693 opnd10 = TREE_OPERAND (opnd1, 0);
1694 opnd11 = TREE_OPERAND (opnd1, 1);
1695 chrec10 = analyze_scalar_evolution (loop, opnd10);
1696 chrec11 = analyze_scalar_evolution (loop, opnd11);
1697 chrec10 = chrec_convert (type, chrec10);
1698 chrec11 = chrec_convert (type, chrec11);
1699 res = chrec_fold_minus (type, chrec10, chrec11);
1703 opnd10 = TREE_OPERAND (opnd1, 0);
1704 chrec10 = analyze_scalar_evolution (loop, opnd10);
1705 chrec10 = chrec_convert (type, chrec10);
1706 res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10);
1710 opnd10 = TREE_OPERAND (opnd1, 0);
1711 opnd11 = TREE_OPERAND (opnd1, 1);
1712 chrec10 = analyze_scalar_evolution (loop, opnd10);
1713 chrec11 = analyze_scalar_evolution (loop, opnd11);
1714 chrec10 = chrec_convert (type, chrec10);
1715 chrec11 = chrec_convert (type, chrec11);
1716 res = chrec_fold_multiply (type, chrec10, chrec11);
1720 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
1725 opnd10 = TREE_OPERAND (opnd1, 0);
1726 chrec10 = analyze_scalar_evolution (loop, opnd10);
1727 res = chrec_convert (type, chrec10);
1731 res = chrec_dont_know;
1740 /* This section contains all the entry points:
1741 - number_of_iterations_in_loop,
1742 - analyze_scalar_evolution,
1743 - instantiate_parameters.
1746 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1747 common ancestor of DEF_LOOP and USE_LOOP. */
1750 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1751 struct loop *def_loop,
1755 if (def_loop == wrto_loop)
1758 def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1759 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1761 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1764 /* Helper recursive function. */
1767 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1769 tree def, type = TREE_TYPE (var);
1771 struct loop *def_loop;
1774 return chrec_dont_know;
1776 if (TREE_CODE (var) != SSA_NAME)
1777 return interpret_rhs_modify_expr (loop, var, type);
1779 def = SSA_NAME_DEF_STMT (var);
1780 bb = bb_for_stmt (def);
1781 def_loop = bb ? bb->loop_father : NULL;
1784 || !flow_bb_inside_loop_p (loop, bb))
1786 /* Keep the symbolic form. */
1791 if (res != chrec_not_analyzed_yet)
1793 if (loop != bb->loop_father)
1794 res = compute_scalar_evolution_in_loop
1795 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1800 if (loop != def_loop)
1802 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1803 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1808 switch (TREE_CODE (def))
1811 res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
1815 if (loop_phi_node_p (def))
1816 res = interpret_loop_phi (loop, def);
1818 res = interpret_condition_phi (loop, def);
1822 res = chrec_dont_know;
1828 /* Keep the symbolic form. */
1829 if (res == chrec_dont_know)
1832 if (loop == def_loop)
1833 set_scalar_evolution (var, res);
1838 /* Entry point for the scalar evolution analyzer.
1839 Analyzes and returns the scalar evolution of the ssa_name VAR.
1840 LOOP_NB is the identifier number of the loop in which the variable
1843 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1844 pointer to the statement that uses this variable, in order to
1845 determine the evolution function of the variable, use the following
1848 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1849 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1850 tree chrec_instantiated = instantiate_parameters
1851 (loop_nb, chrec_with_symbols);
1855 analyze_scalar_evolution (struct loop *loop, tree var)
1859 if (dump_file && (dump_flags & TDF_DETAILS))
1861 fprintf (dump_file, "(analyze_scalar_evolution \n");
1862 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1863 fprintf (dump_file, " (scalar = ");
1864 print_generic_expr (dump_file, var, 0);
1865 fprintf (dump_file, ")\n");
1868 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1870 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1873 if (dump_file && (dump_flags & TDF_DETAILS))
1874 fprintf (dump_file, ")\n");
1879 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1880 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1884 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1892 ev = analyze_scalar_evolution (use_loop, ev);
1893 ev = resolve_mixers (use_loop, ev);
1895 if (use_loop == wrto_loop)
1898 /* If the value of the use changes in the inner loop, we cannot express
1899 its value in the outer loop (we might try to return interval chrec,
1900 but we do not have a user for it anyway) */
1901 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1903 return chrec_dont_know;
1905 use_loop = use_loop->outer;
1909 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1910 with respect to LOOP. CHREC is the chrec to instantiate. If
1911 ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1912 outer loop chrecs is done. */
1915 instantiate_parameters_1 (struct loop *loop, tree chrec,
1916 bool allow_superloop_chrecs)
1918 tree res, op0, op1, op2;
1920 struct loop *def_loop;
1922 if (chrec == NULL_TREE
1923 || automatically_generated_chrec_p (chrec))
1926 if (is_gimple_min_invariant (chrec))
1929 switch (TREE_CODE (chrec))
1932 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1934 /* A parameter (or loop invariant and we do not want to include
1935 evolutions in outer loops), nothing to do. */
1937 || (!allow_superloop_chrecs
1938 && !flow_bb_inside_loop_p (loop, def_bb)))
1941 /* Don't instantiate the SSA_NAME if it is in a mixer
1942 structure. This is used for avoiding the instantiation of
1943 recursively defined functions, such as:
1945 | a_2 -> {0, +, 1, +, a_2}_1 */
1947 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
1949 if (!flow_bb_inside_loop_p (loop, def_bb))
1951 /* We may keep the loop invariant in symbolic form. */
1956 /* Something with unknown behavior in LOOP. */
1957 return chrec_dont_know;
1961 def_loop = find_common_loop (loop, def_bb->loop_father);
1963 /* If the analysis yields a parametric chrec, instantiate the
1964 result again. Avoid the cyclic instantiation in mixers. */
1965 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
1966 res = analyze_scalar_evolution (def_loop, chrec);
1967 res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
1968 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
1971 case POLYNOMIAL_CHREC:
1972 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
1973 allow_superloop_chrecs);
1974 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
1975 allow_superloop_chrecs);
1976 return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
1979 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
1980 allow_superloop_chrecs);
1981 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
1982 allow_superloop_chrecs);
1983 return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
1986 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
1987 allow_superloop_chrecs);
1988 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
1989 allow_superloop_chrecs);
1990 return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
1993 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
1994 allow_superloop_chrecs);
1995 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
1996 allow_superloop_chrecs);
1997 return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
2001 case NON_LVALUE_EXPR:
2002 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2003 allow_superloop_chrecs);
2004 if (op0 == chrec_dont_know)
2005 return chrec_dont_know;
2007 return chrec_convert (TREE_TYPE (chrec), op0);
2009 case SCEV_NOT_KNOWN:
2010 return chrec_dont_know;
2019 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2022 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2023 allow_superloop_chrecs);
2024 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2025 allow_superloop_chrecs);
2026 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2027 allow_superloop_chrecs);
2028 if (op0 == chrec_dont_know
2029 || op1 == chrec_dont_know
2030 || op2 == chrec_dont_know)
2031 return chrec_dont_know;
2032 return fold (build (TREE_CODE (chrec),
2033 TREE_TYPE (chrec), op0, op1, op2));
2036 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2037 allow_superloop_chrecs);
2038 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2039 allow_superloop_chrecs);
2040 if (op0 == chrec_dont_know
2041 || op1 == chrec_dont_know)
2042 return chrec_dont_know;
2043 return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
2046 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2047 allow_superloop_chrecs);
2048 if (op0 == chrec_dont_know)
2049 return chrec_dont_know;
2050 return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
2059 /* Too complicated to handle. */
2060 return chrec_dont_know;
2063 /* Analyze all the parameters of the chrec that were left under a
2064 symbolic form. LOOP is the loop in which symbolic names have to
2065 be analyzed and instantiated. */
2068 instantiate_parameters (struct loop *loop,
2073 if (dump_file && (dump_flags & TDF_DETAILS))
2075 fprintf (dump_file, "(instantiate_parameters \n");
2076 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2077 fprintf (dump_file, " (chrec = ");
2078 print_generic_expr (dump_file, chrec, 0);
2079 fprintf (dump_file, ")\n");
2082 res = instantiate_parameters_1 (loop, chrec, true);
2084 if (dump_file && (dump_flags & TDF_DETAILS))
2086 fprintf (dump_file, " (res = ");
2087 print_generic_expr (dump_file, res, 0);
2088 fprintf (dump_file, "))\n");
2094 /* Similar to instantiate_parameters, but does not introduce the
2095 evolutions in outer loops for LOOP invariants in CHREC. */
2098 resolve_mixers (struct loop *loop, tree chrec)
2100 return instantiate_parameters_1 (loop, chrec, false);
2103 /* Entry point for the analysis of the number of iterations pass.
2104 This function tries to safely approximate the number of iterations
2105 the loop will run. When this property is not decidable at compile
2106 time, the result is chrec_dont_know. Otherwise the result is
2107 a scalar or a symbolic parameter.
2109 Example of analysis: suppose that the loop has an exit condition:
2111 "if (b > 49) goto end_loop;"
2113 and that in a previous analysis we have determined that the
2114 variable 'b' has an evolution function:
2116 "EF = {23, +, 5}_2".
2118 When we evaluate the function at the point 5, i.e. the value of the
2119 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2120 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2121 the loop body has been executed 6 times. */
2124 number_of_iterations_in_loop (struct loop *loop)
2128 struct tree_niter_desc niter_desc;
2130 /* Determine whether the number_of_iterations_in_loop has already
2132 res = loop->nb_iterations;
2135 res = chrec_dont_know;
2137 if (dump_file && (dump_flags & TDF_DETAILS))
2138 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2140 exit = loop->single_exit;
2144 if (!number_of_iterations_exit (loop, exit, &niter_desc))
2147 type = TREE_TYPE (niter_desc.niter);
2148 if (integer_nonzerop (niter_desc.may_be_zero))
2149 res = build_int_cst (type, 0);
2150 else if (integer_zerop (niter_desc.may_be_zero))
2151 res = niter_desc.niter;
2153 res = chrec_dont_know;
2156 return set_nb_iterations_in_loop (loop, res);
2159 /* One of the drivers for testing the scalar evolutions analysis.
2160 This function computes the number of iterations for all the loops
2161 from the EXIT_CONDITIONS array. */
2164 number_of_iterations_for_all_loops (varray_type exit_conditions)
2167 unsigned nb_chrec_dont_know_loops = 0;
2168 unsigned nb_static_loops = 0;
2170 for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
2172 tree res = number_of_iterations_in_loop
2173 (loop_containing_stmt (VARRAY_TREE (exit_conditions, i)));
2174 if (chrec_contains_undetermined (res))
2175 nb_chrec_dont_know_loops++;
2182 fprintf (dump_file, "\n(\n");
2183 fprintf (dump_file, "-----------------------------------------\n");
2184 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2185 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2186 fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2187 fprintf (dump_file, "-----------------------------------------\n");
2188 fprintf (dump_file, ")\n\n");
2190 print_loop_ir (dump_file);
2196 /* Counters for the stats. */
2202 unsigned nb_affine_multivar;
2203 unsigned nb_higher_poly;
2204 unsigned nb_chrec_dont_know;
2205 unsigned nb_undetermined;
2208 /* Reset the counters. */
2211 reset_chrecs_counters (struct chrec_stats *stats)
2213 stats->nb_chrecs = 0;
2214 stats->nb_affine = 0;
2215 stats->nb_affine_multivar = 0;
2216 stats->nb_higher_poly = 0;
2217 stats->nb_chrec_dont_know = 0;
2218 stats->nb_undetermined = 0;
2221 /* Dump the contents of a CHREC_STATS structure. */
2224 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2226 fprintf (file, "\n(\n");
2227 fprintf (file, "-----------------------------------------\n");
2228 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2229 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2230 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2231 stats->nb_higher_poly);
2232 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2233 fprintf (file, "-----------------------------------------\n");
2234 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2235 fprintf (file, "%d\twith undetermined coefficients\n",
2236 stats->nb_undetermined);
2237 fprintf (file, "-----------------------------------------\n");
2238 fprintf (file, "%d\tchrecs in the scev database\n",
2239 (int) htab_elements (scalar_evolution_info));
2240 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2241 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2242 fprintf (file, "-----------------------------------------\n");
2243 fprintf (file, ")\n\n");
2246 /* Gather statistics about CHREC. */
2249 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2251 if (dump_file && (dump_flags & TDF_STATS))
2253 fprintf (dump_file, "(classify_chrec ");
2254 print_generic_expr (dump_file, chrec, 0);
2255 fprintf (dump_file, "\n");
2260 if (chrec == NULL_TREE)
2262 stats->nb_undetermined++;
2266 switch (TREE_CODE (chrec))
2268 case POLYNOMIAL_CHREC:
2269 if (evolution_function_is_affine_p (chrec))
2271 if (dump_file && (dump_flags & TDF_STATS))
2272 fprintf (dump_file, " affine_univariate\n");
2275 else if (evolution_function_is_affine_multivariate_p (chrec))
2277 if (dump_file && (dump_flags & TDF_STATS))
2278 fprintf (dump_file, " affine_multivariate\n");
2279 stats->nb_affine_multivar++;
2283 if (dump_file && (dump_flags & TDF_STATS))
2284 fprintf (dump_file, " higher_degree_polynomial\n");
2285 stats->nb_higher_poly++;
2294 if (chrec_contains_undetermined (chrec))
2296 if (dump_file && (dump_flags & TDF_STATS))
2297 fprintf (dump_file, " undetermined\n");
2298 stats->nb_undetermined++;
2301 if (dump_file && (dump_flags & TDF_STATS))
2302 fprintf (dump_file, ")\n");
2305 /* One of the drivers for testing the scalar evolutions analysis.
2306 This function analyzes the scalar evolution of all the scalars
2307 defined as loop phi nodes in one of the loops from the
2308 EXIT_CONDITIONS array.
2310 TODO Optimization: A loop is in canonical form if it contains only
2311 a single scalar loop phi node. All the other scalars that have an
2312 evolution in the loop are rewritten in function of this single
2313 index. This allows the parallelization of the loop. */
2316 analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
2319 struct chrec_stats stats;
2321 reset_chrecs_counters (&stats);
2323 for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
2329 loop = loop_containing_stmt (VARRAY_TREE (exit_conditions, i));
2332 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2333 if (is_gimple_reg (PHI_RESULT (phi)))
2335 chrec = instantiate_parameters
2337 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2339 if (dump_file && (dump_flags & TDF_STATS))
2340 gather_chrec_stats (chrec, &stats);
2344 if (dump_file && (dump_flags & TDF_STATS))
2345 dump_chrecs_stats (dump_file, &stats);
2348 /* Callback for htab_traverse, gathers information on chrecs in the
2352 gather_stats_on_scev_database_1 (void **slot, void *stats)
2354 struct scev_info_str *entry = *slot;
2356 gather_chrec_stats (entry->chrec, stats);
2361 /* Classify the chrecs of the whole database. */
2364 gather_stats_on_scev_database (void)
2366 struct chrec_stats stats;
2371 reset_chrecs_counters (&stats);
2373 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2376 dump_chrecs_stats (dump_file, &stats);
2384 initialize_scalar_evolutions_analyzer (void)
2386 /* The elements below are unique. */
2387 if (chrec_dont_know == NULL_TREE)
2389 chrec_not_analyzed_yet = NULL_TREE;
2390 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2391 chrec_known = make_node (SCEV_KNOWN);
2392 TREE_TYPE (chrec_dont_know) = NULL_TREE;
2393 TREE_TYPE (chrec_known) = NULL_TREE;
2397 /* Initialize the analysis of scalar evolutions for LOOPS. */
2400 scev_initialize (struct loops *loops)
2403 current_loops = loops;
2405 scalar_evolution_info = htab_create (100, hash_scev_info,
2406 eq_scev_info, del_scev_info);
2407 already_instantiated = BITMAP_XMALLOC ();
2409 initialize_scalar_evolutions_analyzer ();
2411 for (i = 1; i < loops->num; i++)
2412 if (loops->parray[i])
2413 loops->parray[i]->nb_iterations = NULL_TREE;
2416 /* Cleans up the information cached by the scalar evolutions analysis. */
2424 if (!scalar_evolution_info || !current_loops)
2427 htab_empty (scalar_evolution_info);
2428 for (i = 1; i < current_loops->num; i++)
2430 loop = current_loops->parray[i];
2432 loop->nb_iterations = NULL_TREE;
2436 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2437 its BASE and STEP if possible. */
2440 simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
2442 basic_block bb = bb_for_stmt (stmt);
2448 type = TREE_TYPE (op);
2449 if (TREE_CODE (type) != INTEGER_TYPE
2450 && TREE_CODE (type) != POINTER_TYPE)
2453 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
2454 if (chrec_contains_undetermined (ev))
2457 if (tree_does_not_contain_chrecs (ev)
2458 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2464 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2465 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2468 *step = CHREC_RIGHT (ev);
2469 if (TREE_CODE (*step) != INTEGER_CST)
2471 *base = CHREC_LEFT (ev);
2472 if (tree_contains_chrecs (*base)
2473 || chrec_contains_symbols_defined_in_loop (*base, loop->num))
2479 /* Runs the analysis of scalar evolutions. */
2482 scev_analysis (void)
2484 varray_type exit_conditions;
2486 VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions");
2487 select_loops_exit_conditions (current_loops, &exit_conditions);
2489 if (dump_file && (dump_flags & TDF_STATS))
2490 analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions);
2492 number_of_iterations_for_all_loops (exit_conditions);
2493 VARRAY_CLEAR (exit_conditions);
2496 /* Finalize the scalar evolution analysis. */
2499 scev_finalize (void)
2501 htab_delete (scalar_evolution_info);
2502 BITMAP_XFREE (already_instantiated);