1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
50 - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
75 Example 1: Illustration of the basic algorithm.
81 | if (c > 10) exit_loop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
119 or in terms of a C program:
122 | for (x = 0; x <= 7; x++)
128 Example 2a: Illustration of the algorithm on nested loops.
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
157 Example 2b: Multivariate chains of recurrences.
170 Analyzing the access function of array A with
171 instantiate_parameters (loop_1, "j + k"), we obtain the
172 instantiation and the analysis of the scalar variables "j" and "k"
173 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175 {0, +, 1}_1. To obtain the evolution function in loop_3 and
176 instantiate the scalar variables up to loop_1, one has to use:
177 instantiate_scev (loop_1, loop_3, "j + k"). The result of this
178 call is {{0, +, 1}_1, +, 1}_2.
180 Example 3: Higher degree polynomials.
194 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197 Example 4: Lucas, Fibonacci, or mixers in general.
209 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210 following semantics: during the first iteration of the loop_1, the
211 variable contains the value 1, and then it contains the value "c".
212 Note that this syntax is close to the syntax of the loop-phi-node:
213 "a -> (1, c)_1" vs. "a = phi (1, c)".
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
218 Example 5: Flip-flops, or exchangers.
230 Based on these symbolic chrecs, it is possible to refine this
231 information into the more precise PERIODIC_CHRECs:
236 This transformation is not yet implemented.
240 You can find a more detailed description of the algorithm in:
241 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243 this is a preliminary report and some of the details of the
244 algorithm have changed. I'm working on a research report that
245 updates the description of the algorithms to reflect the design
246 choices used in this implementation.
248 A set of slides show a high level overview of the algorithm and run
249 an example through the scalar evolution analyzer:
250 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252 The slides that I have presented at the GCC Summit'04 are available
253 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
258 #include "coretypes.h"
264 /* These RTL headers are needed for basic-block.h. */
266 #include "basic-block.h"
267 #include "diagnostic.h"
268 #include "tree-flow.h"
269 #include "tree-dump.h"
272 #include "tree-chrec.h"
273 #include "tree-scalar-evolution.h"
274 #include "tree-pass.h"
278 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
280 /* The cached information about a ssa name VAR, claiming that inside LOOP,
281 the value of VAR can be expressed as CHREC. */
283 struct scev_info_str GTY(())
289 /* Counters for the scev database. */
290 static unsigned nb_set_scev = 0;
291 static unsigned nb_get_scev = 0;
293 /* The following trees are unique elements. Thus the comparison of
294 another element to these elements should be done on the pointer to
295 these trees, and not on their value. */
297 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
298 tree chrec_not_analyzed_yet;
300 /* Reserved to the cases where the analyzer has detected an
301 undecidable property at compile time. */
302 tree chrec_dont_know;
304 /* When the analyzer has detected that a property will never
305 happen, then it qualifies it with chrec_known. */
308 static bitmap already_instantiated;
310 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
313 /* Constructs a new SCEV_INFO_STR structure. */
315 static inline struct scev_info_str *
316 new_scev_info_str (tree var)
318 struct scev_info_str *res;
320 res = GGC_NEW (struct scev_info_str);
322 res->chrec = chrec_not_analyzed_yet;
327 /* Computes a hash function for database element ELT. */
330 hash_scev_info (const void *elt)
332 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
335 /* Compares database elements E1 and E2. */
338 eq_scev_info (const void *e1, const void *e2)
340 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
341 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
343 return elt1->var == elt2->var;
346 /* Deletes database element E. */
349 del_scev_info (void *e)
354 /* Get the index corresponding to VAR in the current LOOP. If
355 it's the first time we ask for this VAR, then we return
356 chrec_not_analyzed_yet for this VAR and return its index. */
359 find_var_scev_info (tree var)
361 struct scev_info_str *res;
362 struct scev_info_str tmp;
366 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
369 *slot = new_scev_info_str (var);
370 res = (struct scev_info_str *) *slot;
375 /* Return true when CHREC contains symbolic names defined in
379 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
383 if (chrec == NULL_TREE)
386 if (is_gimple_min_invariant (chrec))
389 if (TREE_CODE (chrec) == VAR_DECL
390 || TREE_CODE (chrec) == PARM_DECL
391 || TREE_CODE (chrec) == FUNCTION_DECL
392 || TREE_CODE (chrec) == LABEL_DECL
393 || TREE_CODE (chrec) == RESULT_DECL
394 || TREE_CODE (chrec) == FIELD_DECL)
397 if (TREE_CODE (chrec) == SSA_NAME)
399 tree def = SSA_NAME_DEF_STMT (chrec);
400 struct loop *def_loop = loop_containing_stmt (def);
401 struct loop *loop = get_loop (loop_nb);
403 if (def_loop == NULL)
406 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
412 n = TREE_OPERAND_LENGTH (chrec);
413 for (i = 0; i < n; i++)
414 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
420 /* Return true when PHI is a loop-phi-node. */
423 loop_phi_node_p (tree phi)
425 /* The implementation of this function is based on the following
426 property: "all the loop-phi-nodes of a loop are contained in the
427 loop's header basic block". */
429 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
432 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
433 In general, in the case of multivariate evolutions we want to get
434 the evolution in different loops. LOOP specifies the level for
435 which to get the evolution.
439 | for (j = 0; j < 100; j++)
441 | for (k = 0; k < 100; k++)
443 | i = k + j; - Here the value of i is a function of j, k.
445 | ... = i - Here the value of i is a function of j.
447 | ... = i - Here the value of i is a scalar.
453 | i_1 = phi (i_0, i_2)
457 This loop has the same effect as:
458 LOOP_1 has the same effect as:
462 The overall effect of the loop, "i_0 + 20" in the previous example,
463 is obtained by passing in the parameters: LOOP = 1,
464 EVOLUTION_FN = {i_0, +, 2}_1.
468 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
472 if (evolution_fn == chrec_dont_know)
473 return chrec_dont_know;
475 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
477 struct loop *inner_loop = get_chrec_loop (evolution_fn);
479 if (inner_loop == loop
480 || flow_loop_nested_p (loop, inner_loop))
482 tree nb_iter = number_of_latch_executions (inner_loop);
484 if (nb_iter == chrec_dont_know)
485 return chrec_dont_know;
490 /* evolution_fn is the evolution function in LOOP. Get
491 its value in the nb_iter-th iteration. */
492 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
494 /* Continue the computation until ending on a parent of LOOP. */
495 return compute_overall_effect_of_inner_loop (loop, res);
502 /* If the evolution function is an invariant, there is nothing to do. */
503 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
507 return chrec_dont_know;
510 /* Determine whether the CHREC is always positive/negative. If the expression
511 cannot be statically analyzed, return false, otherwise set the answer into
515 chrec_is_positive (tree chrec, bool *value)
517 bool value0, value1, value2;
518 tree end_value, nb_iter;
520 switch (TREE_CODE (chrec))
522 case POLYNOMIAL_CHREC:
523 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
524 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
527 /* FIXME -- overflows. */
528 if (value0 == value1)
534 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
535 and the proof consists in showing that the sign never
536 changes during the execution of the loop, from 0 to
537 loop->nb_iterations. */
538 if (!evolution_function_is_affine_p (chrec))
541 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
542 if (chrec_contains_undetermined (nb_iter))
546 /* TODO -- If the test is after the exit, we may decrease the number of
547 iterations by one. */
549 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
552 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
554 if (!chrec_is_positive (end_value, &value2))
558 return value0 == value1;
561 *value = (tree_int_cst_sgn (chrec) == 1);
569 /* Associate CHREC to SCALAR. */
572 set_scalar_evolution (tree scalar, tree chrec)
576 if (TREE_CODE (scalar) != SSA_NAME)
579 scalar_info = find_var_scev_info (scalar);
583 if (dump_flags & TDF_DETAILS)
585 fprintf (dump_file, "(set_scalar_evolution \n");
586 fprintf (dump_file, " (scalar = ");
587 print_generic_expr (dump_file, scalar, 0);
588 fprintf (dump_file, ")\n (scalar_evolution = ");
589 print_generic_expr (dump_file, chrec, 0);
590 fprintf (dump_file, "))\n");
592 if (dump_flags & TDF_STATS)
596 *scalar_info = chrec;
599 /* Retrieve the chrec associated to SCALAR in the LOOP. */
602 get_scalar_evolution (tree scalar)
608 if (dump_flags & TDF_DETAILS)
610 fprintf (dump_file, "(get_scalar_evolution \n");
611 fprintf (dump_file, " (scalar = ");
612 print_generic_expr (dump_file, scalar, 0);
613 fprintf (dump_file, ")\n");
615 if (dump_flags & TDF_STATS)
619 switch (TREE_CODE (scalar))
622 res = *find_var_scev_info (scalar);
632 res = chrec_not_analyzed_yet;
636 if (dump_file && (dump_flags & TDF_DETAILS))
638 fprintf (dump_file, " (scalar_evolution = ");
639 print_generic_expr (dump_file, res, 0);
640 fprintf (dump_file, "))\n");
646 /* Helper function for add_to_evolution. Returns the evolution
647 function for an assignment of the form "a = b + c", where "a" and
648 "b" are on the strongly connected component. CHREC_BEFORE is the
649 information that we already have collected up to this point.
650 TO_ADD is the evolution of "c".
652 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
653 evolution the expression TO_ADD, otherwise construct an evolution
654 part for this loop. */
657 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
660 tree type, left, right;
661 struct loop *loop = get_loop (loop_nb), *chloop;
663 switch (TREE_CODE (chrec_before))
665 case POLYNOMIAL_CHREC:
666 chloop = get_chrec_loop (chrec_before);
668 || flow_loop_nested_p (chloop, loop))
672 type = chrec_type (chrec_before);
674 /* When there is no evolution part in this loop, build it. */
679 right = SCALAR_FLOAT_TYPE_P (type)
680 ? build_real (type, dconst0)
681 : build_int_cst (type, 0);
685 var = CHREC_VARIABLE (chrec_before);
686 left = CHREC_LEFT (chrec_before);
687 right = CHREC_RIGHT (chrec_before);
690 to_add = chrec_convert (type, to_add, at_stmt);
691 right = chrec_convert_rhs (type, right, at_stmt);
692 right = chrec_fold_plus (chrec_type (right), right, to_add);
693 return build_polynomial_chrec (var, left, right);
697 gcc_assert (flow_loop_nested_p (loop, chloop));
699 /* Search the evolution in LOOP_NB. */
700 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
702 right = CHREC_RIGHT (chrec_before);
703 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
704 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
709 /* These nodes do not depend on a loop. */
710 if (chrec_before == chrec_dont_know)
711 return chrec_dont_know;
714 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
715 return build_polynomial_chrec (loop_nb, left, right);
719 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
722 Description (provided for completeness, for those who read code in
723 a plane, and for my poor 62 bytes brain that would have forgotten
724 all this in the next two or three months):
726 The algorithm of translation of programs from the SSA representation
727 into the chrecs syntax is based on a pattern matching. After having
728 reconstructed the overall tree expression for a loop, there are only
729 two cases that can arise:
731 1. a = loop-phi (init, a + expr)
732 2. a = loop-phi (init, expr)
734 where EXPR is either a scalar constant with respect to the analyzed
735 loop (this is a degree 0 polynomial), or an expression containing
736 other loop-phi definitions (these are higher degree polynomials).
743 | a = phi (init, a + 5)
750 | a = phi (inita, 2 * b + 3)
751 | b = phi (initb, b + 1)
754 For the first case, the semantics of the SSA representation is:
756 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
758 that is, there is a loop index "x" that determines the scalar value
759 of the variable during the loop execution. During the first
760 iteration, the value is that of the initial condition INIT, while
761 during the subsequent iterations, it is the sum of the initial
762 condition with the sum of all the values of EXPR from the initial
763 iteration to the before last considered iteration.
765 For the second case, the semantics of the SSA program is:
767 | a (x) = init, if x = 0;
768 | expr (x - 1), otherwise.
770 The second case corresponds to the PEELED_CHREC, whose syntax is
771 close to the syntax of a loop-phi-node:
773 | phi (init, expr) vs. (init, expr)_x
775 The proof of the translation algorithm for the first case is a
776 proof by structural induction based on the degree of EXPR.
779 When EXPR is a constant with respect to the analyzed loop, or in
780 other words when EXPR is a polynomial of degree 0, the evolution of
781 the variable A in the loop is an affine function with an initial
782 condition INIT, and a step EXPR. In order to show this, we start
783 from the semantics of the SSA representation:
785 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
787 and since "expr (j)" is a constant with respect to "j",
789 f (x) = init + x * expr
791 Finally, based on the semantics of the pure sum chrecs, by
792 identification we get the corresponding chrecs syntax:
794 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
795 f (x) -> {init, +, expr}_x
798 Suppose that EXPR is a polynomial of degree N with respect to the
799 analyzed loop_x for which we have already determined that it is
800 written under the chrecs syntax:
802 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
804 We start from the semantics of the SSA program:
806 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
808 | f (x) = init + \sum_{j = 0}^{x - 1}
809 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
811 | f (x) = init + \sum_{j = 0}^{x - 1}
812 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
814 | f (x) = init + \sum_{k = 0}^{n - 1}
815 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
817 | f (x) = init + \sum_{k = 0}^{n - 1}
818 | (b_k * \binom{x}{k + 1})
820 | f (x) = init + b_0 * \binom{x}{1} + ...
821 | + b_{n-1} * \binom{x}{n}
823 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
824 | + b_{n-1} * \binom{x}{n}
827 And finally from the definition of the chrecs syntax, we identify:
828 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
830 This shows the mechanism that stands behind the add_to_evolution
831 function. An important point is that the use of symbolic
832 parameters avoids the need of an analysis schedule.
839 | a = phi (inita, a + 2 + b)
840 | b = phi (initb, b + 1)
843 When analyzing "a", the algorithm keeps "b" symbolically:
845 | a -> {inita, +, 2 + b}_1
847 Then, after instantiation, the analyzer ends on the evolution:
849 | a -> {inita, +, 2 + initb, +, 1}_1
854 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
855 tree to_add, tree at_stmt)
857 tree type = chrec_type (to_add);
858 tree res = NULL_TREE;
860 if (to_add == NULL_TREE)
863 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
864 instantiated at this point. */
865 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
866 /* This should not happen. */
867 return chrec_dont_know;
869 if (dump_file && (dump_flags & TDF_DETAILS))
871 fprintf (dump_file, "(add_to_evolution \n");
872 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
873 fprintf (dump_file, " (chrec_before = ");
874 print_generic_expr (dump_file, chrec_before, 0);
875 fprintf (dump_file, ")\n (to_add = ");
876 print_generic_expr (dump_file, to_add, 0);
877 fprintf (dump_file, ")\n");
880 if (code == MINUS_EXPR)
881 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
882 ? build_real (type, dconstm1)
883 : build_int_cst_type (type, -1));
885 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
887 if (dump_file && (dump_flags & TDF_DETAILS))
889 fprintf (dump_file, " (res = ");
890 print_generic_expr (dump_file, res, 0);
891 fprintf (dump_file, "))\n");
897 /* Helper function. */
900 set_nb_iterations_in_loop (struct loop *loop,
903 if (dump_file && (dump_flags & TDF_DETAILS))
905 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
906 print_generic_expr (dump_file, res, 0);
907 fprintf (dump_file, "))\n");
910 loop->nb_iterations = res;
916 /* This section selects the loops that will be good candidates for the
917 scalar evolution analysis. For the moment, greedily select all the
918 loop nests we could analyze. */
920 /* Return true when it is possible to analyze the condition expression
924 analyzable_condition (const_tree expr)
928 if (TREE_CODE (expr) != COND_EXPR)
931 condition = TREE_OPERAND (expr, 0);
933 switch (TREE_CODE (condition))
953 /* For a loop with a single exit edge, return the COND_EXPR that
954 guards the exit edge. If the expression is too difficult to
955 analyze, then give up. */
958 get_loop_exit_condition (const struct loop *loop)
960 tree res = NULL_TREE;
961 edge exit_edge = single_exit (loop);
963 if (dump_file && (dump_flags & TDF_DETAILS))
964 fprintf (dump_file, "(get_loop_exit_condition \n ");
970 expr = last_stmt (exit_edge->src);
971 if (analyzable_condition (expr))
975 if (dump_file && (dump_flags & TDF_DETAILS))
977 print_generic_expr (dump_file, res, 0);
978 fprintf (dump_file, ")\n");
984 /* Recursively determine and enqueue the exit conditions for a loop. */
987 get_exit_conditions_rec (struct loop *loop,
988 VEC(tree,heap) **exit_conditions)
993 /* Recurse on the inner loops, then on the next (sibling) loops. */
994 get_exit_conditions_rec (loop->inner, exit_conditions);
995 get_exit_conditions_rec (loop->next, exit_conditions);
997 if (single_exit (loop))
999 tree loop_condition = get_loop_exit_condition (loop);
1002 VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1006 /* Select the candidate loop nests for the analysis. This function
1007 initializes the EXIT_CONDITIONS array. */
1010 select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
1012 struct loop *function_body = current_loops->tree_root;
1014 get_exit_conditions_rec (function_body->inner, exit_conditions);
1018 /* Depth first search algorithm. */
1020 typedef enum t_bool {
1027 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1029 /* Follow the ssa edge into the right hand side RHS of an assignment.
1030 Return true if the strongly connected component has been found. */
1033 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1034 tree halting_phi, tree *evolution_of_loop, int limit)
1036 t_bool res = t_false;
1038 tree type_rhs = TREE_TYPE (rhs);
1040 enum tree_code code;
1042 /* The RHS is one of the following cases:
1046 - a POINTER_PLUS_EXPR,
1049 - other cases are not yet handled. */
1050 code = TREE_CODE (rhs);
1054 /* This assignment is under the form "a_1 = (cast) rhs. */
1055 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1056 halting_phi, evolution_of_loop, limit);
1057 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1058 *evolution_of_loop, at_stmt);
1062 /* This assignment is under the form "a_1 = 7". */
1067 /* This assignment is under the form: "a_1 = b_2". */
1068 res = follow_ssa_edge
1069 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1072 case POINTER_PLUS_EXPR:
1074 /* This case is under the form "rhs0 + rhs1". */
1075 rhs0 = TREE_OPERAND (rhs, 0);
1076 rhs1 = TREE_OPERAND (rhs, 1);
1077 STRIP_TYPE_NOPS (rhs0);
1078 STRIP_TYPE_NOPS (rhs1);
1080 if (TREE_CODE (rhs0) == SSA_NAME)
1082 if (TREE_CODE (rhs1) == SSA_NAME)
1084 /* Match an assignment under the form:
1087 /* We want only assignments of form "name + name" contribute to
1088 LIMIT, as the other cases do not necessarily contribute to
1089 the complexity of the expression. */
1092 evol = *evolution_of_loop;
1093 res = follow_ssa_edge
1094 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1098 *evolution_of_loop = add_to_evolution
1100 chrec_convert (type_rhs, evol, at_stmt),
1101 code, rhs1, at_stmt);
1103 else if (res == t_false)
1105 res = follow_ssa_edge
1106 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1107 evolution_of_loop, limit);
1110 *evolution_of_loop = add_to_evolution
1112 chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1113 code, rhs0, at_stmt);
1115 else if (res == t_dont_know)
1116 *evolution_of_loop = chrec_dont_know;
1119 else if (res == t_dont_know)
1120 *evolution_of_loop = chrec_dont_know;
1125 /* Match an assignment under the form:
1127 res = follow_ssa_edge
1128 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1129 evolution_of_loop, limit);
1131 *evolution_of_loop = add_to_evolution
1132 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1134 code, rhs1, at_stmt);
1136 else if (res == t_dont_know)
1137 *evolution_of_loop = chrec_dont_know;
1141 else if (TREE_CODE (rhs1) == SSA_NAME)
1143 /* Match an assignment under the form:
1145 res = follow_ssa_edge
1146 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1147 evolution_of_loop, limit);
1149 *evolution_of_loop = add_to_evolution
1150 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1152 code, rhs0, at_stmt);
1154 else if (res == t_dont_know)
1155 *evolution_of_loop = chrec_dont_know;
1159 /* Otherwise, match an assignment under the form:
1161 /* And there is nothing to do. */
1167 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1168 rhs0 = TREE_OPERAND (rhs, 0);
1169 rhs1 = TREE_OPERAND (rhs, 1);
1170 STRIP_TYPE_NOPS (rhs0);
1171 STRIP_TYPE_NOPS (rhs1);
1173 if (TREE_CODE (rhs0) == SSA_NAME)
1175 /* Match an assignment under the form:
1178 /* We want only assignments of form "name - name" contribute to
1179 LIMIT, as the other cases do not necessarily contribute to
1180 the complexity of the expression. */
1181 if (TREE_CODE (rhs1) == SSA_NAME)
1184 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1185 evolution_of_loop, limit);
1187 *evolution_of_loop = add_to_evolution
1188 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1189 MINUS_EXPR, rhs1, at_stmt);
1191 else if (res == t_dont_know)
1192 *evolution_of_loop = chrec_dont_know;
1195 /* Otherwise, match an assignment under the form:
1197 /* And there is nothing to do. */
1204 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1205 It must be handled as a copy assignment of the form a_1 = a_2. */
1206 tree op0 = ASSERT_EXPR_VAR (rhs);
1207 if (TREE_CODE (op0) == SSA_NAME)
1208 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1209 halting_phi, evolution_of_loop, limit);
1224 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1227 backedge_phi_arg_p (const_tree phi, int i)
1229 const_edge e = PHI_ARG_EDGE (phi, i);
1231 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1232 about updating it anywhere, and this should work as well most of the
1234 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1240 /* Helper function for one branch of the condition-phi-node. Return
1241 true if the strongly connected component has been found following
1244 static inline t_bool
1245 follow_ssa_edge_in_condition_phi_branch (int i,
1249 tree *evolution_of_branch,
1250 tree init_cond, int limit)
1252 tree branch = PHI_ARG_DEF (condition_phi, i);
1253 *evolution_of_branch = chrec_dont_know;
1255 /* Do not follow back edges (they must belong to an irreducible loop, which
1256 we really do not want to worry about). */
1257 if (backedge_phi_arg_p (condition_phi, i))
1260 if (TREE_CODE (branch) == SSA_NAME)
1262 *evolution_of_branch = init_cond;
1263 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1264 evolution_of_branch, limit);
1267 /* This case occurs when one of the condition branches sets
1268 the variable to a constant: i.e. a phi-node like
1269 "a_2 = PHI <a_7(5), 2(6)>;".
1271 FIXME: This case have to be refined correctly:
1272 in some cases it is possible to say something better than
1273 chrec_dont_know, for example using a wrap-around notation. */
1277 /* This function merges the branches of a condition-phi-node in a
1281 follow_ssa_edge_in_condition_phi (struct loop *loop,
1284 tree *evolution_of_loop, int limit)
1287 tree init = *evolution_of_loop;
1288 tree evolution_of_branch;
1289 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1291 &evolution_of_branch,
1293 if (res == t_false || res == t_dont_know)
1296 *evolution_of_loop = evolution_of_branch;
1298 /* If the phi node is just a copy, do not increase the limit. */
1299 if (PHI_NUM_ARGS (condition_phi) > 1)
1302 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1304 /* Quickly give up when the evolution of one of the branches is
1306 if (*evolution_of_loop == chrec_dont_know)
1309 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1311 &evolution_of_branch,
1313 if (res == t_false || res == t_dont_know)
1316 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1317 evolution_of_branch);
1323 /* Follow an SSA edge in an inner loop. It computes the overall
1324 effect of the loop, and following the symbolic initial conditions,
1325 it follows the edges in the parent loop. The inner loop is
1326 considered as a single statement. */
1329 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1332 tree *evolution_of_loop, int limit)
1334 struct loop *loop = loop_containing_stmt (loop_phi_node);
1335 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1337 /* Sometimes, the inner loop is too difficult to analyze, and the
1338 result of the analysis is a symbolic parameter. */
1339 if (ev == PHI_RESULT (loop_phi_node))
1341 t_bool res = t_false;
1344 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1346 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1349 /* Follow the edges that exit the inner loop. */
1350 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1351 if (!flow_bb_inside_loop_p (loop, bb))
1352 res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1354 evolution_of_loop, limit);
1359 /* If the path crosses this loop-phi, give up. */
1361 *evolution_of_loop = chrec_dont_know;
1366 /* Otherwise, compute the overall effect of the inner loop. */
1367 ev = compute_overall_effect_of_inner_loop (loop, ev);
1368 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1369 evolution_of_loop, limit);
1372 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1373 path that is analyzed on the return walk. */
1376 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1377 tree *evolution_of_loop, int limit)
1379 struct loop *def_loop;
1381 if (TREE_CODE (def) == NOP_EXPR)
1384 /* Give up if the path is longer than the MAX that we allow. */
1385 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1388 def_loop = loop_containing_stmt (def);
1390 switch (TREE_CODE (def))
1393 if (!loop_phi_node_p (def))
1394 /* DEF is a condition-phi-node. Follow the branches, and
1395 record their evolutions. Finally, merge the collected
1396 information and set the approximation to the main
1398 return follow_ssa_edge_in_condition_phi
1399 (loop, def, halting_phi, evolution_of_loop, limit);
1401 /* When the analyzed phi is the halting_phi, the
1402 depth-first search is over: we have found a path from
1403 the halting_phi to itself in the loop. */
1404 if (def == halting_phi)
1407 /* Otherwise, the evolution of the HALTING_PHI depends
1408 on the evolution of another loop-phi-node, i.e. the
1409 evolution function is a higher degree polynomial. */
1410 if (def_loop == loop)
1414 if (flow_loop_nested_p (loop, def_loop))
1415 return follow_ssa_edge_inner_loop_phi
1416 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1421 case GIMPLE_MODIFY_STMT:
1422 return follow_ssa_edge_in_rhs (loop, def,
1423 GIMPLE_STMT_OPERAND (def, 1),
1425 evolution_of_loop, limit);
1428 /* At this level of abstraction, the program is just a set
1429 of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
1430 other node to be handled. */
1437 /* Given a LOOP_PHI_NODE, this function determines the evolution
1438 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1441 analyze_evolution_in_loop (tree loop_phi_node,
1445 tree evolution_function = chrec_not_analyzed_yet;
1446 struct loop *loop = loop_containing_stmt (loop_phi_node);
1449 if (dump_file && (dump_flags & TDF_DETAILS))
1451 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1452 fprintf (dump_file, " (loop_phi_node = ");
1453 print_generic_expr (dump_file, loop_phi_node, 0);
1454 fprintf (dump_file, ")\n");
1457 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1459 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1460 tree ssa_chain, ev_fn;
1463 /* Select the edges that enter the loop body. */
1464 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1465 if (!flow_bb_inside_loop_p (loop, bb))
1468 if (TREE_CODE (arg) == SSA_NAME)
1470 ssa_chain = SSA_NAME_DEF_STMT (arg);
1472 /* Pass in the initial condition to the follow edge function. */
1474 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1479 /* When it is impossible to go back on the same
1480 loop_phi_node by following the ssa edges, the
1481 evolution is represented by a peeled chrec, i.e. the
1482 first iteration, EV_FN has the value INIT_COND, then
1483 all the other iterations it has the value of ARG.
1484 For the moment, PEELED_CHREC nodes are not built. */
1486 ev_fn = chrec_dont_know;
1488 /* When there are multiple back edges of the loop (which in fact never
1489 happens currently, but nevertheless), merge their evolutions. */
1490 evolution_function = chrec_merge (evolution_function, ev_fn);
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1495 fprintf (dump_file, " (evolution_function = ");
1496 print_generic_expr (dump_file, evolution_function, 0);
1497 fprintf (dump_file, "))\n");
1500 return evolution_function;
1503 /* Given a loop-phi-node, return the initial conditions of the
1504 variable on entry of the loop. When the CCP has propagated
1505 constants into the loop-phi-node, the initial condition is
1506 instantiated, otherwise the initial condition is kept symbolic.
1507 This analyzer does not analyze the evolution outside the current
1508 loop, and leaves this task to the on-demand tree reconstructor. */
1511 analyze_initial_condition (tree loop_phi_node)
1514 tree init_cond = chrec_not_analyzed_yet;
1515 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1517 if (dump_file && (dump_flags & TDF_DETAILS))
1519 fprintf (dump_file, "(analyze_initial_condition \n");
1520 fprintf (dump_file, " (loop_phi_node = \n");
1521 print_generic_expr (dump_file, loop_phi_node, 0);
1522 fprintf (dump_file, ")\n");
1525 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1527 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1528 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1530 /* When the branch is oriented to the loop's body, it does
1531 not contribute to the initial condition. */
1532 if (flow_bb_inside_loop_p (loop, bb))
1535 if (init_cond == chrec_not_analyzed_yet)
1541 if (TREE_CODE (branch) == SSA_NAME)
1543 init_cond = chrec_dont_know;
1547 init_cond = chrec_merge (init_cond, branch);
1550 /* Ooops -- a loop without an entry??? */
1551 if (init_cond == chrec_not_analyzed_yet)
1552 init_cond = chrec_dont_know;
1554 if (dump_file && (dump_flags & TDF_DETAILS))
1556 fprintf (dump_file, " (init_cond = ");
1557 print_generic_expr (dump_file, init_cond, 0);
1558 fprintf (dump_file, "))\n");
1564 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1567 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1570 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1573 if (phi_loop != loop)
1575 struct loop *subloop;
1576 tree evolution_fn = analyze_scalar_evolution
1577 (phi_loop, PHI_RESULT (loop_phi_node));
1579 /* Dive one level deeper. */
1580 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1582 /* Interpret the subloop. */
1583 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1587 /* Otherwise really interpret the loop phi. */
1588 init_cond = analyze_initial_condition (loop_phi_node);
1589 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1594 /* This function merges the branches of a condition-phi-node,
1595 contained in the outermost loop, and whose arguments are already
1599 interpret_condition_phi (struct loop *loop, tree condition_phi)
1602 tree res = chrec_not_analyzed_yet;
1604 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1608 if (backedge_phi_arg_p (condition_phi, i))
1610 res = chrec_dont_know;
1614 branch_chrec = analyze_scalar_evolution
1615 (loop, PHI_ARG_DEF (condition_phi, i));
1617 res = chrec_merge (res, branch_chrec);
1623 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
1624 analyze this node before, follow the definitions until ending
1625 either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
1626 return path, this function propagates evolutions (ala constant copy
1627 propagation). OPND1 is not a GIMPLE expression because we could
1628 analyze the effect of an inner loop: see interpret_loop_phi. */
1631 interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
1632 tree opnd1, tree type)
1634 tree res, opnd10, opnd11, chrec10, chrec11;
1636 if (is_gimple_min_invariant (opnd1))
1637 return chrec_convert (type, opnd1, at_stmt);
1639 switch (TREE_CODE (opnd1))
1641 case POINTER_PLUS_EXPR:
1642 opnd10 = TREE_OPERAND (opnd1, 0);
1643 opnd11 = TREE_OPERAND (opnd1, 1);
1644 chrec10 = analyze_scalar_evolution (loop, opnd10);
1645 chrec11 = analyze_scalar_evolution (loop, opnd11);
1646 chrec10 = chrec_convert (type, chrec10, at_stmt);
1647 chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
1648 res = chrec_fold_plus (type, chrec10, chrec11);
1652 opnd10 = TREE_OPERAND (opnd1, 0);
1653 opnd11 = TREE_OPERAND (opnd1, 1);
1654 chrec10 = analyze_scalar_evolution (loop, opnd10);
1655 chrec11 = analyze_scalar_evolution (loop, opnd11);
1656 chrec10 = chrec_convert (type, chrec10, at_stmt);
1657 chrec11 = chrec_convert (type, chrec11, at_stmt);
1658 res = chrec_fold_plus (type, chrec10, chrec11);
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_minus (type, chrec10, chrec11);
1672 opnd10 = TREE_OPERAND (opnd1, 0);
1673 chrec10 = analyze_scalar_evolution (loop, opnd10);
1674 chrec10 = chrec_convert (type, chrec10, at_stmt);
1675 /* TYPE may be integer, real or complex, so use fold_convert. */
1676 res = chrec_fold_multiply (type, chrec10,
1677 fold_convert (type, integer_minus_one_node));
1681 opnd10 = TREE_OPERAND (opnd1, 0);
1682 opnd11 = TREE_OPERAND (opnd1, 1);
1683 chrec10 = analyze_scalar_evolution (loop, opnd10);
1684 chrec11 = analyze_scalar_evolution (loop, opnd11);
1685 chrec10 = chrec_convert (type, chrec10, at_stmt);
1686 chrec11 = chrec_convert (type, chrec11, at_stmt);
1687 res = chrec_fold_multiply (type, chrec10, chrec11);
1691 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1696 opnd10 = ASSERT_EXPR_VAR (opnd1);
1697 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1702 opnd10 = TREE_OPERAND (opnd1, 0);
1703 chrec10 = analyze_scalar_evolution (loop, opnd10);
1704 res = chrec_convert (type, chrec10, at_stmt);
1708 res = chrec_dont_know;
1717 /* This section contains all the entry points:
1718 - number_of_iterations_in_loop,
1719 - analyze_scalar_evolution,
1720 - instantiate_parameters.
1723 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1724 common ancestor of DEF_LOOP and USE_LOOP. */
1727 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1728 struct loop *def_loop,
1732 if (def_loop == wrto_loop)
1735 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1736 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1738 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1741 /* Helper recursive function. */
1744 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1746 tree def, type = TREE_TYPE (var);
1748 struct loop *def_loop;
1750 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1751 return chrec_dont_know;
1753 if (TREE_CODE (var) != SSA_NAME)
1754 return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
1756 def = SSA_NAME_DEF_STMT (var);
1757 bb = bb_for_stmt (def);
1758 def_loop = bb ? bb->loop_father : NULL;
1761 || !flow_bb_inside_loop_p (loop, bb))
1763 /* Keep the symbolic form. */
1768 if (res != chrec_not_analyzed_yet)
1770 if (loop != bb->loop_father)
1771 res = compute_scalar_evolution_in_loop
1772 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1777 if (loop != def_loop)
1779 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1780 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1785 switch (TREE_CODE (def))
1787 case GIMPLE_MODIFY_STMT:
1788 res = interpret_rhs_modify_stmt (loop, def,
1789 GIMPLE_STMT_OPERAND (def, 1), type);
1793 if (loop_phi_node_p (def))
1794 res = interpret_loop_phi (loop, def);
1796 res = interpret_condition_phi (loop, def);
1800 res = chrec_dont_know;
1806 /* Keep the symbolic form. */
1807 if (res == chrec_dont_know)
1810 if (loop == def_loop)
1811 set_scalar_evolution (var, res);
1816 /* Entry point for the scalar evolution analyzer.
1817 Analyzes and returns the scalar evolution of the ssa_name VAR.
1818 LOOP_NB is the identifier number of the loop in which the variable
1821 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1822 pointer to the statement that uses this variable, in order to
1823 determine the evolution function of the variable, use the following
1826 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1827 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1828 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1832 analyze_scalar_evolution (struct loop *loop, tree var)
1836 if (dump_file && (dump_flags & TDF_DETAILS))
1838 fprintf (dump_file, "(analyze_scalar_evolution \n");
1839 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1840 fprintf (dump_file, " (scalar = ");
1841 print_generic_expr (dump_file, var, 0);
1842 fprintf (dump_file, ")\n");
1845 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1847 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1850 if (dump_file && (dump_flags & TDF_DETAILS))
1851 fprintf (dump_file, ")\n");
1856 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1857 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1860 FOLDED_CASTS is set to true if resolve_mixers used
1861 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1862 at the moment in order to keep things simple). */
1865 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1866 tree version, bool *folded_casts)
1869 tree ev = version, tmp;
1872 *folded_casts = false;
1875 tmp = analyze_scalar_evolution (use_loop, ev);
1876 ev = resolve_mixers (use_loop, tmp);
1878 if (folded_casts && tmp != ev)
1879 *folded_casts = true;
1881 if (use_loop == wrto_loop)
1884 /* If the value of the use changes in the inner loop, we cannot express
1885 its value in the outer loop (we might try to return interval chrec,
1886 but we do not have a user for it anyway) */
1887 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1889 return chrec_dont_know;
1891 use_loop = loop_outer (use_loop);
1895 /* Returns instantiated value for VERSION in CACHE. */
1898 get_instantiated_value (htab_t cache, tree version)
1900 struct scev_info_str *info, pattern;
1902 pattern.var = version;
1903 info = (struct scev_info_str *) htab_find (cache, &pattern);
1911 /* Sets instantiated value for VERSION to VAL in CACHE. */
1914 set_instantiated_value (htab_t cache, tree version, tree val)
1916 struct scev_info_str *info, pattern;
1919 pattern.var = version;
1920 slot = htab_find_slot (cache, &pattern, INSERT);
1923 *slot = new_scev_info_str (version);
1924 info = (struct scev_info_str *) *slot;
1928 /* Return the closed_loop_phi node for VAR. If there is none, return
1932 loop_closed_phi_def (tree var)
1938 if (var == NULL_TREE
1939 || TREE_CODE (var) != SSA_NAME)
1942 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
1943 exit = single_exit (loop);
1947 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1948 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
1949 return PHI_RESULT (phi);
1954 /* Analyze all the parameters of the chrec, between INSTANTIATION_LOOP
1955 and EVOLUTION_LOOP, that were left under a symbolic form.
1957 CHREC is the scalar evolution to instantiate.
1959 CACHE is the cache of already instantiated values.
1961 FOLD_CONVERSIONS should be set to true when the conversions that
1962 may wrap in signed/pointer type are folded, as long as the value of
1963 the chrec is preserved.
1965 SIZE_EXPR is used for computing the size of the expression to be
1966 instantiated, and to stop if it exceeds some limit. */
1969 instantiate_scev_1 (struct loop *instantiation_loop,
1970 struct loop *evolution_loop, tree chrec,
1971 bool fold_conversions, htab_t cache, int size_expr)
1973 tree res, op0, op1, op2;
1975 struct loop *def_loop;
1976 tree type = chrec_type (chrec);
1978 /* Give up if the expression is larger than the MAX that we allow. */
1979 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1980 return chrec_dont_know;
1982 if (automatically_generated_chrec_p (chrec)
1983 || is_gimple_min_invariant (chrec))
1986 switch (TREE_CODE (chrec))
1989 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1991 /* A parameter (or loop invariant and we do not want to include
1992 evolutions in outer loops), nothing to do. */
1994 || loop_depth (def_bb->loop_father) == 0
1995 || !flow_bb_inside_loop_p (instantiation_loop, def_bb))
1998 /* We cache the value of instantiated variable to avoid exponential
1999 time complexity due to reevaluations. We also store the convenient
2000 value in the cache in order to prevent infinite recursion -- we do
2001 not want to instantiate the SSA_NAME if it is in a mixer
2002 structure. This is used for avoiding the instantiation of
2003 recursively defined functions, such as:
2005 | a_2 -> {0, +, 1, +, a_2}_1 */
2007 res = get_instantiated_value (cache, chrec);
2011 /* Store the convenient value for chrec in the structure. If it
2012 is defined outside of the loop, we may just leave it in symbolic
2013 form, otherwise we need to admit that we do not know its behavior
2015 res = !flow_bb_inside_loop_p (instantiation_loop, def_bb)
2016 ? chrec : chrec_dont_know;
2017 set_instantiated_value (cache, chrec, res);
2019 /* To make things even more complicated, instantiate_scev_1
2020 calls analyze_scalar_evolution that may call # of iterations
2021 analysis that may in turn call instantiate_scev_1 again.
2022 To prevent the infinite recursion, keep also the bitmap of
2023 ssa names that are being instantiated globally. */
2024 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2027 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2029 /* If the analysis yields a parametric chrec, instantiate the
2031 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2032 res = analyze_scalar_evolution (def_loop, chrec);
2034 /* Don't instantiate loop-closed-ssa phi nodes. */
2035 if (TREE_CODE (res) == SSA_NAME
2036 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2037 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2038 > loop_depth (def_loop))))
2041 res = loop_closed_phi_def (chrec);
2045 if (res == NULL_TREE)
2046 res = chrec_dont_know;
2049 else if (res != chrec_dont_know)
2050 res = instantiate_scev_1 (instantiation_loop, evolution_loop, res,
2051 fold_conversions, cache, size_expr);
2053 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2055 /* Store the correct value to the cache. */
2056 set_instantiated_value (cache, chrec, res);
2059 case POLYNOMIAL_CHREC:
2060 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2061 CHREC_LEFT (chrec), fold_conversions, cache,
2063 if (op0 == chrec_dont_know)
2064 return chrec_dont_know;
2066 op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2067 CHREC_RIGHT (chrec), fold_conversions, cache,
2069 if (op1 == chrec_dont_know)
2070 return chrec_dont_know;
2072 if (CHREC_LEFT (chrec) != op0
2073 || CHREC_RIGHT (chrec) != op1)
2075 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
2076 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2080 case POINTER_PLUS_EXPR:
2082 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2083 TREE_OPERAND (chrec, 0), fold_conversions, cache,
2085 if (op0 == chrec_dont_know)
2086 return chrec_dont_know;
2088 op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2089 TREE_OPERAND (chrec, 1), fold_conversions, cache,
2091 if (op1 == chrec_dont_know)
2092 return chrec_dont_know;
2094 if (TREE_OPERAND (chrec, 0) != op0
2095 || TREE_OPERAND (chrec, 1) != op1)
2097 op0 = chrec_convert (type, op0, NULL_TREE);
2098 op1 = chrec_convert_rhs (type, op1, NULL_TREE);
2099 chrec = chrec_fold_plus (type, op0, op1);
2104 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2105 TREE_OPERAND (chrec, 0), fold_conversions, cache,
2107 if (op0 == chrec_dont_know)
2108 return chrec_dont_know;
2110 op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2111 TREE_OPERAND (chrec, 1),
2112 fold_conversions, cache, size_expr);
2113 if (op1 == chrec_dont_know)
2114 return chrec_dont_know;
2116 if (TREE_OPERAND (chrec, 0) != op0
2117 || TREE_OPERAND (chrec, 1) != op1)
2119 op0 = chrec_convert (type, op0, NULL_TREE);
2120 op1 = chrec_convert (type, op1, NULL_TREE);
2121 chrec = chrec_fold_minus (type, op0, op1);
2126 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2127 TREE_OPERAND (chrec, 0),
2128 fold_conversions, cache, size_expr);
2129 if (op0 == chrec_dont_know)
2130 return chrec_dont_know;
2132 op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2133 TREE_OPERAND (chrec, 1),
2134 fold_conversions, cache, size_expr);
2135 if (op1 == chrec_dont_know)
2136 return chrec_dont_know;
2138 if (TREE_OPERAND (chrec, 0) != op0
2139 || TREE_OPERAND (chrec, 1) != op1)
2141 op0 = chrec_convert (type, op0, NULL_TREE);
2142 op1 = chrec_convert (type, op1, NULL_TREE);
2143 chrec = chrec_fold_multiply (type, op0, op1);
2148 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2149 TREE_OPERAND (chrec, 0),
2150 fold_conversions, cache, size_expr);
2151 if (op0 == chrec_dont_know)
2152 return chrec_dont_know;
2154 if (fold_conversions)
2156 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2161 if (op0 == TREE_OPERAND (chrec, 0))
2164 /* If we used chrec_convert_aggressive, we can no longer assume that
2165 signed chrecs do not overflow, as chrec_convert does, so avoid
2166 calling it in that case. */
2167 if (fold_conversions)
2168 return fold_convert (TREE_TYPE (chrec), op0);
2170 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2172 case SCEV_NOT_KNOWN:
2173 return chrec_dont_know;
2182 gcc_assert (!VL_EXP_CLASS_P (chrec));
2183 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2186 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2187 TREE_OPERAND (chrec, 0),
2188 fold_conversions, cache, size_expr);
2189 if (op0 == chrec_dont_know)
2190 return chrec_dont_know;
2192 op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2193 TREE_OPERAND (chrec, 1),
2194 fold_conversions, cache, size_expr);
2195 if (op1 == chrec_dont_know)
2196 return chrec_dont_know;
2198 op2 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2199 TREE_OPERAND (chrec, 2),
2200 fold_conversions, cache, size_expr);
2201 if (op2 == chrec_dont_know)
2202 return chrec_dont_know;
2204 if (op0 == TREE_OPERAND (chrec, 0)
2205 && op1 == TREE_OPERAND (chrec, 1)
2206 && op2 == TREE_OPERAND (chrec, 2))
2209 return fold_build3 (TREE_CODE (chrec),
2210 TREE_TYPE (chrec), op0, op1, op2);
2213 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2214 TREE_OPERAND (chrec, 0),
2215 fold_conversions, cache, size_expr);
2216 if (op0 == chrec_dont_know)
2217 return chrec_dont_know;
2219 op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2220 TREE_OPERAND (chrec, 1),
2221 fold_conversions, cache, size_expr);
2222 if (op1 == chrec_dont_know)
2223 return chrec_dont_know;
2225 if (op0 == TREE_OPERAND (chrec, 0)
2226 && op1 == TREE_OPERAND (chrec, 1))
2228 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2231 op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
2232 TREE_OPERAND (chrec, 0),
2233 fold_conversions, cache, size_expr);
2234 if (op0 == chrec_dont_know)
2235 return chrec_dont_know;
2236 if (op0 == TREE_OPERAND (chrec, 0))
2238 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2247 /* Too complicated to handle. */
2248 return chrec_dont_know;
2251 /* Analyze all the parameters of the chrec that were left under a
2252 symbolic form. INSTANTIATION_LOOP is the loop in which symbolic
2253 names have to be instantiated, and EVOLUTION_LOOP is the loop in
2254 which the evolution of scalars have to be analyzed. */
2257 instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop,
2261 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2263 if (dump_file && (dump_flags & TDF_DETAILS))
2265 fprintf (dump_file, "(instantiate_scev \n");
2266 fprintf (dump_file, " (instantiation_loop = %d)\n", instantiation_loop->num);
2267 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2268 fprintf (dump_file, " (chrec = ");
2269 print_generic_expr (dump_file, chrec, 0);
2270 fprintf (dump_file, ")\n");
2273 res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, false,
2276 if (dump_file && (dump_flags & TDF_DETAILS))
2278 fprintf (dump_file, " (res = ");
2279 print_generic_expr (dump_file, res, 0);
2280 fprintf (dump_file, "))\n");
2283 htab_delete (cache);
2288 /* Similar to instantiate_parameters, but does not introduce the
2289 evolutions in outer loops for LOOP invariants in CHREC, and does not
2290 care about causing overflows, as long as they do not affect value
2291 of an expression. */
2294 resolve_mixers (struct loop *loop, tree chrec)
2296 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2297 tree ret = instantiate_scev_1 (loop, loop, chrec, true, cache, 0);
2298 htab_delete (cache);
2302 /* Entry point for the analysis of the number of iterations pass.
2303 This function tries to safely approximate the number of iterations
2304 the loop will run. When this property is not decidable at compile
2305 time, the result is chrec_dont_know. Otherwise the result is
2306 a scalar or a symbolic parameter.
2308 Example of analysis: suppose that the loop has an exit condition:
2310 "if (b > 49) goto end_loop;"
2312 and that in a previous analysis we have determined that the
2313 variable 'b' has an evolution function:
2315 "EF = {23, +, 5}_2".
2317 When we evaluate the function at the point 5, i.e. the value of the
2318 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2319 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2320 the loop body has been executed 6 times. */
2323 number_of_latch_executions (struct loop *loop)
2327 struct tree_niter_desc niter_desc;
2329 /* Determine whether the number_of_iterations_in_loop has already
2331 res = loop->nb_iterations;
2334 res = chrec_dont_know;
2336 if (dump_file && (dump_flags & TDF_DETAILS))
2337 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2339 exit = single_exit (loop);
2343 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2346 type = TREE_TYPE (niter_desc.niter);
2347 if (integer_nonzerop (niter_desc.may_be_zero))
2348 res = build_int_cst (type, 0);
2349 else if (integer_zerop (niter_desc.may_be_zero))
2350 res = niter_desc.niter;
2352 res = chrec_dont_know;
2355 return set_nb_iterations_in_loop (loop, res);
2358 /* Returns the number of executions of the exit condition of LOOP,
2359 i.e., the number by one higher than number_of_latch_executions.
2360 Note that unline number_of_latch_executions, this number does
2361 not necessarily fit in the unsigned variant of the type of
2362 the control variable -- if the number of iterations is a constant,
2363 we return chrec_dont_know if adding one to number_of_latch_executions
2364 overflows; however, in case the number of iterations is symbolic
2365 expression, the caller is responsible for dealing with this
2366 the possible overflow. */
2369 number_of_exit_cond_executions (struct loop *loop)
2371 tree ret = number_of_latch_executions (loop);
2372 tree type = chrec_type (ret);
2374 if (chrec_contains_undetermined (ret))
2377 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2378 if (TREE_CODE (ret) == INTEGER_CST
2379 && TREE_OVERFLOW (ret))
2380 return chrec_dont_know;
2385 /* One of the drivers for testing the scalar evolutions analysis.
2386 This function computes the number of iterations for all the loops
2387 from the EXIT_CONDITIONS array. */
2390 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2393 unsigned nb_chrec_dont_know_loops = 0;
2394 unsigned nb_static_loops = 0;
2397 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2399 tree res = number_of_latch_executions (loop_containing_stmt (cond));
2400 if (chrec_contains_undetermined (res))
2401 nb_chrec_dont_know_loops++;
2408 fprintf (dump_file, "\n(\n");
2409 fprintf (dump_file, "-----------------------------------------\n");
2410 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2411 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2412 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2413 fprintf (dump_file, "-----------------------------------------\n");
2414 fprintf (dump_file, ")\n\n");
2416 print_loops (dump_file, 3);
2422 /* Counters for the stats. */
2428 unsigned nb_affine_multivar;
2429 unsigned nb_higher_poly;
2430 unsigned nb_chrec_dont_know;
2431 unsigned nb_undetermined;
2434 /* Reset the counters. */
2437 reset_chrecs_counters (struct chrec_stats *stats)
2439 stats->nb_chrecs = 0;
2440 stats->nb_affine = 0;
2441 stats->nb_affine_multivar = 0;
2442 stats->nb_higher_poly = 0;
2443 stats->nb_chrec_dont_know = 0;
2444 stats->nb_undetermined = 0;
2447 /* Dump the contents of a CHREC_STATS structure. */
2450 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2452 fprintf (file, "\n(\n");
2453 fprintf (file, "-----------------------------------------\n");
2454 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2455 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2456 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2457 stats->nb_higher_poly);
2458 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2459 fprintf (file, "-----------------------------------------\n");
2460 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2461 fprintf (file, "%d\twith undetermined coefficients\n",
2462 stats->nb_undetermined);
2463 fprintf (file, "-----------------------------------------\n");
2464 fprintf (file, "%d\tchrecs in the scev database\n",
2465 (int) htab_elements (scalar_evolution_info));
2466 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2467 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2468 fprintf (file, "-----------------------------------------\n");
2469 fprintf (file, ")\n\n");
2472 /* Gather statistics about CHREC. */
2475 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2477 if (dump_file && (dump_flags & TDF_STATS))
2479 fprintf (dump_file, "(classify_chrec ");
2480 print_generic_expr (dump_file, chrec, 0);
2481 fprintf (dump_file, "\n");
2486 if (chrec == NULL_TREE)
2488 stats->nb_undetermined++;
2492 switch (TREE_CODE (chrec))
2494 case POLYNOMIAL_CHREC:
2495 if (evolution_function_is_affine_p (chrec))
2497 if (dump_file && (dump_flags & TDF_STATS))
2498 fprintf (dump_file, " affine_univariate\n");
2501 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2503 if (dump_file && (dump_flags & TDF_STATS))
2504 fprintf (dump_file, " affine_multivariate\n");
2505 stats->nb_affine_multivar++;
2509 if (dump_file && (dump_flags & TDF_STATS))
2510 fprintf (dump_file, " higher_degree_polynomial\n");
2511 stats->nb_higher_poly++;
2520 if (chrec_contains_undetermined (chrec))
2522 if (dump_file && (dump_flags & TDF_STATS))
2523 fprintf (dump_file, " undetermined\n");
2524 stats->nb_undetermined++;
2527 if (dump_file && (dump_flags & TDF_STATS))
2528 fprintf (dump_file, ")\n");
2531 /* One of the drivers for testing the scalar evolutions analysis.
2532 This function analyzes the scalar evolution of all the scalars
2533 defined as loop phi nodes in one of the loops from the
2534 EXIT_CONDITIONS array.
2536 TODO Optimization: A loop is in canonical form if it contains only
2537 a single scalar loop phi node. All the other scalars that have an
2538 evolution in the loop are rewritten in function of this single
2539 index. This allows the parallelization of the loop. */
2542 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2545 struct chrec_stats stats;
2548 reset_chrecs_counters (&stats);
2550 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2556 loop = loop_containing_stmt (cond);
2559 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2560 if (is_gimple_reg (PHI_RESULT (phi)))
2562 chrec = instantiate_parameters
2564 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2566 if (dump_file && (dump_flags & TDF_STATS))
2567 gather_chrec_stats (chrec, &stats);
2571 if (dump_file && (dump_flags & TDF_STATS))
2572 dump_chrecs_stats (dump_file, &stats);
2575 /* Callback for htab_traverse, gathers information on chrecs in the
2579 gather_stats_on_scev_database_1 (void **slot, void *stats)
2581 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2583 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2588 /* Classify the chrecs of the whole database. */
2591 gather_stats_on_scev_database (void)
2593 struct chrec_stats stats;
2598 reset_chrecs_counters (&stats);
2600 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2603 dump_chrecs_stats (dump_file, &stats);
2611 initialize_scalar_evolutions_analyzer (void)
2613 /* The elements below are unique. */
2614 if (chrec_dont_know == NULL_TREE)
2616 chrec_not_analyzed_yet = NULL_TREE;
2617 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2618 chrec_known = make_node (SCEV_KNOWN);
2619 TREE_TYPE (chrec_dont_know) = void_type_node;
2620 TREE_TYPE (chrec_known) = void_type_node;
2624 /* Initialize the analysis of scalar evolutions for LOOPS. */
2627 scev_initialize (void)
2632 scalar_evolution_info = htab_create_alloc (100,
2638 already_instantiated = BITMAP_ALLOC (NULL);
2640 initialize_scalar_evolutions_analyzer ();
2642 FOR_EACH_LOOP (li, loop, 0)
2644 loop->nb_iterations = NULL_TREE;
2648 /* Clean the scalar evolution analysis cache, but preserve the cached
2649 numbers of iterations for the loops. */
2652 scev_reset_except_niters (void)
2654 if (scalar_evolution_info)
2655 htab_empty (scalar_evolution_info);
2658 /* Cleans up the information cached by the scalar evolutions analysis. */
2666 if (!scalar_evolution_info || !current_loops)
2669 scev_reset_except_niters ();
2671 FOR_EACH_LOOP (li, loop, 0)
2673 loop->nb_iterations = NULL_TREE;
2677 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2678 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2679 want step to be invariant in LOOP. Otherwise we require it to be an
2680 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2681 overflow (e.g. because it is computed in signed arithmetics). */
2684 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2685 bool allow_nonconstant_step)
2687 basic_block bb = bb_for_stmt (stmt);
2691 iv->base = NULL_TREE;
2692 iv->step = NULL_TREE;
2693 iv->no_overflow = false;
2695 type = TREE_TYPE (op);
2696 if (TREE_CODE (type) != INTEGER_TYPE
2697 && TREE_CODE (type) != POINTER_TYPE)
2700 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2702 if (chrec_contains_undetermined (ev))
2705 if (tree_does_not_contain_chrecs (ev)
2706 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2709 iv->step = build_int_cst (TREE_TYPE (ev), 0);
2710 iv->no_overflow = true;
2714 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2715 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2718 iv->step = CHREC_RIGHT (ev);
2719 if (allow_nonconstant_step)
2721 if (tree_contains_chrecs (iv->step, NULL)
2722 || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2725 else if (TREE_CODE (iv->step) != INTEGER_CST)
2728 iv->base = CHREC_LEFT (ev);
2729 if (tree_contains_chrecs (iv->base, NULL)
2730 || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2733 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2738 /* Runs the analysis of scalar evolutions. */
2741 scev_analysis (void)
2743 VEC(tree,heap) *exit_conditions;
2745 exit_conditions = VEC_alloc (tree, heap, 37);
2746 select_loops_exit_conditions (&exit_conditions);
2748 if (dump_file && (dump_flags & TDF_STATS))
2749 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2751 number_of_iterations_for_all_loops (&exit_conditions);
2752 VEC_free (tree, heap, exit_conditions);
2755 /* Finalize the scalar evolution analysis. */
2758 scev_finalize (void)
2760 if (!scalar_evolution_info)
2762 htab_delete (scalar_evolution_info);
2763 BITMAP_FREE (already_instantiated);
2764 scalar_evolution_info = NULL;
2767 /* Replace ssa names for that scev can prove they are constant by the
2768 appropriate constants. Also perform final value replacement in loops,
2769 in case the replacement expressions are cheap.
2771 We only consider SSA names defined by phi nodes; rest is left to the
2772 ordinary constant propagation pass. */
2775 scev_const_prop (void)
2778 tree name, phi, next_phi, type, ev;
2779 struct loop *loop, *ex_loop;
2780 bitmap ssa_names_to_remove = NULL;
2784 if (number_of_loops () <= 1)
2789 loop = bb->loop_father;
2791 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2793 name = PHI_RESULT (phi);
2795 if (!is_gimple_reg (name))
2798 type = TREE_TYPE (name);
2800 if (!POINTER_TYPE_P (type)
2801 && !INTEGRAL_TYPE_P (type))
2804 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2805 if (!is_gimple_min_invariant (ev)
2806 || !may_propagate_copy (name, ev))
2809 /* Replace the uses of the name. */
2811 replace_uses_by (name, ev);
2813 if (!ssa_names_to_remove)
2814 ssa_names_to_remove = BITMAP_ALLOC (NULL);
2815 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2819 /* Remove the ssa names that were replaced by constants. We do not
2820 remove them directly in the previous cycle, since this
2821 invalidates scev cache. */
2822 if (ssa_names_to_remove)
2826 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2828 name = ssa_name (i);
2829 phi = SSA_NAME_DEF_STMT (name);
2831 gcc_assert (TREE_CODE (phi) == PHI_NODE);
2832 remove_phi_node (phi, NULL, true);
2835 BITMAP_FREE (ssa_names_to_remove);
2839 /* Now the regular final value replacement. */
2840 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2843 tree def, rslt, ass, niter;
2844 block_stmt_iterator bsi;
2846 /* If we do not know exact number of iterations of the loop, we cannot
2847 replace the final value. */
2848 exit = single_exit (loop);
2852 niter = number_of_latch_executions (loop);
2853 /* We used to check here whether the computation of NITER is expensive,
2854 and avoided final value elimination if that is the case. The problem
2855 is that it is hard to evaluate whether the expression is too
2856 expensive, as we do not know what optimization opportunities the
2857 the elimination of the final value may reveal. Therefore, we now
2858 eliminate the final values of induction variables unconditionally. */
2859 if (niter == chrec_dont_know)
2862 /* Ensure that it is possible to insert new statements somewhere. */
2863 if (!single_pred_p (exit->dest))
2864 split_loop_exit_edge (exit);
2865 bsi = bsi_after_labels (exit->dest);
2867 ex_loop = superloop_at_depth (loop,
2868 loop_depth (exit->dest->loop_father) + 1);
2870 for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2872 next_phi = PHI_CHAIN (phi);
2873 rslt = PHI_RESULT (phi);
2874 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2875 if (!is_gimple_reg (def))
2878 if (!POINTER_TYPE_P (TREE_TYPE (def))
2879 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2882 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2883 def = compute_overall_effect_of_inner_loop (ex_loop, def);
2884 if (!tree_does_not_contain_chrecs (def)
2885 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2886 /* Moving the computation from the loop may prolong life range
2887 of some ssa names, which may cause problems if they appear
2888 on abnormal edges. */
2889 || contains_abnormal_ssa_name_p (def))
2892 /* Eliminate the PHI node and replace it by a computation outside
2894 def = unshare_expr (def);
2895 remove_phi_node (phi, NULL_TREE, false);
2897 ass = build_gimple_modify_stmt (rslt, NULL_TREE);
2898 SSA_NAME_DEF_STMT (rslt) = ass;
2900 block_stmt_iterator dest = bsi;
2901 bsi_insert_before (&dest, ass, BSI_NEW_STMT);
2902 def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
2903 true, BSI_SAME_STMT);
2905 GIMPLE_STMT_OPERAND (ass, 1) = def;
2912 #include "gt-tree-scalar-evolution.h"