1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
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, 51 Franklin Street, Fifth Floor, 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 GIMPLE_MODIFY_STMT: 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"
256 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257 static tree resolve_mixers (struct loop *, tree);
259 /* The cached information about a ssa name VAR, claiming that inside LOOP,
260 the value of VAR can be expressed as CHREC. */
268 /* Counters for the scev database. */
269 static unsigned nb_set_scev = 0;
270 static unsigned nb_get_scev = 0;
272 /* The following trees are unique elements. Thus the comparison of
273 another element to these elements should be done on the pointer to
274 these trees, and not on their value. */
276 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
277 tree chrec_not_analyzed_yet;
279 /* Reserved to the cases where the analyzer has detected an
280 undecidable property at compile time. */
281 tree chrec_dont_know;
283 /* When the analyzer has detected that a property will never
284 happen, then it qualifies it with chrec_known. */
287 static bitmap already_instantiated;
289 static htab_t scalar_evolution_info;
292 /* Constructs a new SCEV_INFO_STR structure. */
294 static inline struct scev_info_str *
295 new_scev_info_str (tree var)
297 struct scev_info_str *res;
299 res = XNEW (struct scev_info_str);
301 res->chrec = chrec_not_analyzed_yet;
306 /* Computes a hash function for database element ELT. */
309 hash_scev_info (const void *elt)
311 return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
314 /* Compares database elements E1 and E2. */
317 eq_scev_info (const void *e1, const void *e2)
319 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
320 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
322 return elt1->var == elt2->var;
325 /* Deletes database element E. */
328 del_scev_info (void *e)
333 /* Get the index corresponding to VAR in the current LOOP. If
334 it's the first time we ask for this VAR, then we return
335 chrec_not_analyzed_yet for this VAR and return its index. */
338 find_var_scev_info (tree var)
340 struct scev_info_str *res;
341 struct scev_info_str tmp;
345 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
348 *slot = new_scev_info_str (var);
349 res = (struct scev_info_str *) *slot;
354 /* Return true when CHREC contains symbolic names defined in
358 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
360 if (chrec == NULL_TREE)
363 if (TREE_INVARIANT (chrec))
366 if (TREE_CODE (chrec) == VAR_DECL
367 || TREE_CODE (chrec) == PARM_DECL
368 || TREE_CODE (chrec) == FUNCTION_DECL
369 || TREE_CODE (chrec) == LABEL_DECL
370 || TREE_CODE (chrec) == RESULT_DECL
371 || TREE_CODE (chrec) == FIELD_DECL)
374 if (TREE_CODE (chrec) == SSA_NAME)
376 tree def = SSA_NAME_DEF_STMT (chrec);
377 struct loop *def_loop = loop_containing_stmt (def);
378 struct loop *loop = get_loop (loop_nb);
380 if (def_loop == NULL)
383 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
389 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
392 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
397 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
402 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
411 /* Return true when PHI is a loop-phi-node. */
414 loop_phi_node_p (tree phi)
416 /* The implementation of this function is based on the following
417 property: "all the loop-phi-nodes of a loop are contained in the
418 loop's header basic block". */
420 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
423 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
424 In general, in the case of multivariate evolutions we want to get
425 the evolution in different loops. LOOP specifies the level for
426 which to get the evolution.
430 | for (j = 0; j < 100; j++)
432 | for (k = 0; k < 100; k++)
434 | i = k + j; - Here the value of i is a function of j, k.
436 | ... = i - Here the value of i is a function of j.
438 | ... = i - Here the value of i is a scalar.
444 | i_1 = phi (i_0, i_2)
448 This loop has the same effect as:
449 LOOP_1 has the same effect as:
453 The overall effect of the loop, "i_0 + 20" in the previous example,
454 is obtained by passing in the parameters: LOOP = 1,
455 EVOLUTION_FN = {i_0, +, 2}_1.
459 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
463 if (evolution_fn == chrec_dont_know)
464 return chrec_dont_know;
466 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
468 if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
470 struct loop *inner_loop = get_chrec_loop (evolution_fn);
471 tree nb_iter = number_of_iterations_in_loop (inner_loop);
473 if (nb_iter == chrec_dont_know)
474 return chrec_dont_know;
478 tree type = chrec_type (nb_iter);
480 /* Number of iterations is off by one (the ssa name we
481 analyze must be defined before the exit). */
482 nb_iter = chrec_fold_minus (type, nb_iter,
483 build_int_cst (type, 1));
485 /* evolution_fn is the evolution function in LOOP. Get
486 its value in the nb_iter-th iteration. */
487 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
489 /* Continue the computation until ending on a parent of LOOP. */
490 return compute_overall_effect_of_inner_loop (loop, res);
497 /* If the evolution function is an invariant, there is nothing to do. */
498 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
502 return chrec_dont_know;
505 /* Determine whether the CHREC is always positive/negative. If the expression
506 cannot be statically analyzed, return false, otherwise set the answer into
510 chrec_is_positive (tree chrec, bool *value)
512 bool value0, value1, value2;
513 tree type, end_value, nb_iter;
515 switch (TREE_CODE (chrec))
517 case POLYNOMIAL_CHREC:
518 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
519 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
522 /* FIXME -- overflows. */
523 if (value0 == value1)
529 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
530 and the proof consists in showing that the sign never
531 changes during the execution of the loop, from 0 to
532 loop->nb_iterations. */
533 if (!evolution_function_is_affine_p (chrec))
536 nb_iter = number_of_iterations_in_loop (get_chrec_loop (chrec));
537 if (chrec_contains_undetermined (nb_iter))
540 type = chrec_type (nb_iter);
541 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
544 /* TODO -- If the test is after the exit, we may decrease the number of
545 iterations by one. */
547 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
550 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
552 if (!chrec_is_positive (end_value, &value2))
556 return value0 == value1;
559 *value = (tree_int_cst_sgn (chrec) == 1);
567 /* Associate CHREC to SCALAR. */
570 set_scalar_evolution (tree scalar, tree chrec)
574 if (TREE_CODE (scalar) != SSA_NAME)
577 scalar_info = find_var_scev_info (scalar);
581 if (dump_flags & TDF_DETAILS)
583 fprintf (dump_file, "(set_scalar_evolution \n");
584 fprintf (dump_file, " (scalar = ");
585 print_generic_expr (dump_file, scalar, 0);
586 fprintf (dump_file, ")\n (scalar_evolution = ");
587 print_generic_expr (dump_file, chrec, 0);
588 fprintf (dump_file, "))\n");
590 if (dump_flags & TDF_STATS)
594 *scalar_info = chrec;
597 /* Retrieve the chrec associated to SCALAR in the LOOP. */
600 get_scalar_evolution (tree scalar)
606 if (dump_flags & TDF_DETAILS)
608 fprintf (dump_file, "(get_scalar_evolution \n");
609 fprintf (dump_file, " (scalar = ");
610 print_generic_expr (dump_file, scalar, 0);
611 fprintf (dump_file, ")\n");
613 if (dump_flags & TDF_STATS)
617 switch (TREE_CODE (scalar))
620 res = *find_var_scev_info (scalar);
629 res = chrec_not_analyzed_yet;
633 if (dump_file && (dump_flags & TDF_DETAILS))
635 fprintf (dump_file, " (scalar_evolution = ");
636 print_generic_expr (dump_file, res, 0);
637 fprintf (dump_file, "))\n");
643 /* Helper function for add_to_evolution. Returns the evolution
644 function for an assignment of the form "a = b + c", where "a" and
645 "b" are on the strongly connected component. CHREC_BEFORE is the
646 information that we already have collected up to this point.
647 TO_ADD is the evolution of "c".
649 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
650 evolution the expression TO_ADD, otherwise construct an evolution
651 part for this loop. */
654 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
657 tree type, left, right;
659 switch (TREE_CODE (chrec_before))
661 case POLYNOMIAL_CHREC:
662 if (CHREC_VARIABLE (chrec_before) <= loop_nb)
666 type = chrec_type (chrec_before);
668 /* When there is no evolution part in this loop, build it. */
669 if (CHREC_VARIABLE (chrec_before) < loop_nb)
673 right = SCALAR_FLOAT_TYPE_P (type)
674 ? build_real (type, dconst0)
675 : build_int_cst (type, 0);
679 var = CHREC_VARIABLE (chrec_before);
680 left = CHREC_LEFT (chrec_before);
681 right = CHREC_RIGHT (chrec_before);
684 to_add = chrec_convert (type, to_add, at_stmt);
685 right = chrec_convert (type, right, at_stmt);
686 right = chrec_fold_plus (type, right, to_add);
687 return build_polynomial_chrec (var, left, right);
691 /* Search the evolution in LOOP_NB. */
692 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
694 right = CHREC_RIGHT (chrec_before);
695 right = chrec_convert (chrec_type (left), right, at_stmt);
696 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
701 /* These nodes do not depend on a loop. */
702 if (chrec_before == chrec_dont_know)
703 return chrec_dont_know;
706 right = chrec_convert (chrec_type (left), to_add, at_stmt);
707 return build_polynomial_chrec (loop_nb, left, right);
711 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
714 Description (provided for completeness, for those who read code in
715 a plane, and for my poor 62 bytes brain that would have forgotten
716 all this in the next two or three months):
718 The algorithm of translation of programs from the SSA representation
719 into the chrecs syntax is based on a pattern matching. After having
720 reconstructed the overall tree expression for a loop, there are only
721 two cases that can arise:
723 1. a = loop-phi (init, a + expr)
724 2. a = loop-phi (init, expr)
726 where EXPR is either a scalar constant with respect to the analyzed
727 loop (this is a degree 0 polynomial), or an expression containing
728 other loop-phi definitions (these are higher degree polynomials).
735 | a = phi (init, a + 5)
742 | a = phi (inita, 2 * b + 3)
743 | b = phi (initb, b + 1)
746 For the first case, the semantics of the SSA representation is:
748 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
750 that is, there is a loop index "x" that determines the scalar value
751 of the variable during the loop execution. During the first
752 iteration, the value is that of the initial condition INIT, while
753 during the subsequent iterations, it is the sum of the initial
754 condition with the sum of all the values of EXPR from the initial
755 iteration to the before last considered iteration.
757 For the second case, the semantics of the SSA program is:
759 | a (x) = init, if x = 0;
760 | expr (x - 1), otherwise.
762 The second case corresponds to the PEELED_CHREC, whose syntax is
763 close to the syntax of a loop-phi-node:
765 | phi (init, expr) vs. (init, expr)_x
767 The proof of the translation algorithm for the first case is a
768 proof by structural induction based on the degree of EXPR.
771 When EXPR is a constant with respect to the analyzed loop, or in
772 other words when EXPR is a polynomial of degree 0, the evolution of
773 the variable A in the loop is an affine function with an initial
774 condition INIT, and a step EXPR. In order to show this, we start
775 from the semantics of the SSA representation:
777 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
779 and since "expr (j)" is a constant with respect to "j",
781 f (x) = init + x * expr
783 Finally, based on the semantics of the pure sum chrecs, by
784 identification we get the corresponding chrecs syntax:
786 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
787 f (x) -> {init, +, expr}_x
790 Suppose that EXPR is a polynomial of degree N with respect to the
791 analyzed loop_x for which we have already determined that it is
792 written under the chrecs syntax:
794 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
796 We start from the semantics of the SSA program:
798 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
800 | f (x) = init + \sum_{j = 0}^{x - 1}
801 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
803 | f (x) = init + \sum_{j = 0}^{x - 1}
804 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
806 | f (x) = init + \sum_{k = 0}^{n - 1}
807 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
809 | f (x) = init + \sum_{k = 0}^{n - 1}
810 | (b_k * \binom{x}{k + 1})
812 | f (x) = init + b_0 * \binom{x}{1} + ...
813 | + b_{n-1} * \binom{x}{n}
815 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
816 | + b_{n-1} * \binom{x}{n}
819 And finally from the definition of the chrecs syntax, we identify:
820 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
822 This shows the mechanism that stands behind the add_to_evolution
823 function. An important point is that the use of symbolic
824 parameters avoids the need of an analysis schedule.
831 | a = phi (inita, a + 2 + b)
832 | b = phi (initb, b + 1)
835 When analyzing "a", the algorithm keeps "b" symbolically:
837 | a -> {inita, +, 2 + b}_1
839 Then, after instantiation, the analyzer ends on the evolution:
841 | a -> {inita, +, 2 + initb, +, 1}_1
846 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
847 tree to_add, tree at_stmt)
849 tree type = chrec_type (to_add);
850 tree res = NULL_TREE;
852 if (to_add == NULL_TREE)
855 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
856 instantiated at this point. */
857 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
858 /* This should not happen. */
859 return chrec_dont_know;
861 if (dump_file && (dump_flags & TDF_DETAILS))
863 fprintf (dump_file, "(add_to_evolution \n");
864 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
865 fprintf (dump_file, " (chrec_before = ");
866 print_generic_expr (dump_file, chrec_before, 0);
867 fprintf (dump_file, ")\n (to_add = ");
868 print_generic_expr (dump_file, to_add, 0);
869 fprintf (dump_file, ")\n");
872 if (code == MINUS_EXPR)
873 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
874 ? build_real (type, dconstm1)
875 : build_int_cst_type (type, -1));
877 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
879 if (dump_file && (dump_flags & TDF_DETAILS))
881 fprintf (dump_file, " (res = ");
882 print_generic_expr (dump_file, res, 0);
883 fprintf (dump_file, "))\n");
889 /* Helper function. */
892 set_nb_iterations_in_loop (struct loop *loop,
895 tree type = chrec_type (res);
897 res = chrec_fold_plus (type, res, build_int_cst (type, 1));
899 /* FIXME HWI: However we want to store one iteration less than the
900 count of the loop in order to be compatible with the other
901 nb_iter computations in loop-iv. This also allows the
902 representation of nb_iters that are equal to MAX_INT. */
903 if (TREE_CODE (res) == INTEGER_CST
904 && (TREE_INT_CST_LOW (res) == 0
905 || TREE_OVERFLOW (res)))
906 res = chrec_dont_know;
908 if (dump_file && (dump_flags & TDF_DETAILS))
910 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
911 print_generic_expr (dump_file, res, 0);
912 fprintf (dump_file, "))\n");
915 loop->nb_iterations = res;
921 /* This section selects the loops that will be good candidates for the
922 scalar evolution analysis. For the moment, greedily select all the
923 loop nests we could analyze. */
925 /* Return true when it is possible to analyze the condition expression
929 analyzable_condition (tree expr)
933 if (TREE_CODE (expr) != COND_EXPR)
936 condition = TREE_OPERAND (expr, 0);
938 switch (TREE_CODE (condition))
958 /* For a loop with a single exit edge, return the COND_EXPR that
959 guards the exit edge. If the expression is too difficult to
960 analyze, then give up. */
963 get_loop_exit_condition (struct loop *loop)
965 tree res = NULL_TREE;
966 edge exit_edge = single_exit (loop);
968 if (dump_file && (dump_flags & TDF_DETAILS))
969 fprintf (dump_file, "(get_loop_exit_condition \n ");
975 expr = last_stmt (exit_edge->src);
976 if (analyzable_condition (expr))
980 if (dump_file && (dump_flags & TDF_DETAILS))
982 print_generic_expr (dump_file, res, 0);
983 fprintf (dump_file, ")\n");
989 /* Recursively determine and enqueue the exit conditions for a loop. */
992 get_exit_conditions_rec (struct loop *loop,
993 VEC(tree,heap) **exit_conditions)
998 /* Recurse on the inner loops, then on the next (sibling) loops. */
999 get_exit_conditions_rec (loop->inner, exit_conditions);
1000 get_exit_conditions_rec (loop->next, exit_conditions);
1002 if (single_exit (loop))
1004 tree loop_condition = get_loop_exit_condition (loop);
1007 VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1011 /* Select the candidate loop nests for the analysis. This function
1012 initializes the EXIT_CONDITIONS array. */
1015 select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
1017 struct loop *function_body = current_loops->tree_root;
1019 get_exit_conditions_rec (function_body->inner, exit_conditions);
1023 /* Depth first search algorithm. */
1025 typedef enum t_bool {
1032 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1034 /* Follow the ssa edge into the right hand side RHS of an assignment.
1035 Return true if the strongly connected component has been found. */
1038 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1039 tree halting_phi, tree *evolution_of_loop, int limit)
1041 t_bool res = t_false;
1043 tree type_rhs = TREE_TYPE (rhs);
1046 /* The RHS is one of the following cases:
1052 - other cases are not yet handled. */
1053 switch (TREE_CODE (rhs))
1056 /* This assignment is under the form "a_1 = (cast) rhs. */
1057 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1058 halting_phi, evolution_of_loop, limit);
1059 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1060 *evolution_of_loop, at_stmt);
1064 /* This assignment is under the form "a_1 = 7". */
1069 /* This assignment is under the form: "a_1 = b_2". */
1070 res = follow_ssa_edge
1071 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1075 /* This case is under the form "rhs0 + rhs1". */
1076 rhs0 = TREE_OPERAND (rhs, 0);
1077 rhs1 = TREE_OPERAND (rhs, 1);
1078 STRIP_TYPE_NOPS (rhs0);
1079 STRIP_TYPE_NOPS (rhs1);
1081 if (TREE_CODE (rhs0) == SSA_NAME)
1083 if (TREE_CODE (rhs1) == SSA_NAME)
1085 /* Match an assignment under the form:
1087 evol = *evolution_of_loop;
1088 res = follow_ssa_edge
1089 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1093 *evolution_of_loop = add_to_evolution
1095 chrec_convert (type_rhs, evol, at_stmt),
1096 PLUS_EXPR, rhs1, at_stmt);
1098 else if (res == t_false)
1100 res = follow_ssa_edge
1101 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1102 evolution_of_loop, limit);
1105 *evolution_of_loop = add_to_evolution
1107 chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1108 PLUS_EXPR, rhs0, at_stmt);
1110 else if (res == t_dont_know)
1111 *evolution_of_loop = chrec_dont_know;
1114 else if (res == t_dont_know)
1115 *evolution_of_loop = chrec_dont_know;
1120 /* Match an assignment under the form:
1122 res = follow_ssa_edge
1123 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1124 evolution_of_loop, limit);
1126 *evolution_of_loop = add_to_evolution
1127 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1129 PLUS_EXPR, rhs1, at_stmt);
1131 else if (res == t_dont_know)
1132 *evolution_of_loop = chrec_dont_know;
1136 else if (TREE_CODE (rhs1) == SSA_NAME)
1138 /* Match an assignment under the form:
1140 res = follow_ssa_edge
1141 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1142 evolution_of_loop, limit);
1144 *evolution_of_loop = add_to_evolution
1145 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1147 PLUS_EXPR, rhs0, at_stmt);
1149 else if (res == t_dont_know)
1150 *evolution_of_loop = chrec_dont_know;
1154 /* Otherwise, match an assignment under the form:
1156 /* And there is nothing to do. */
1162 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1163 rhs0 = TREE_OPERAND (rhs, 0);
1164 rhs1 = TREE_OPERAND (rhs, 1);
1165 STRIP_TYPE_NOPS (rhs0);
1166 STRIP_TYPE_NOPS (rhs1);
1168 if (TREE_CODE (rhs0) == SSA_NAME)
1170 /* Match an assignment under the form:
1172 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1173 evolution_of_loop, limit);
1175 *evolution_of_loop = add_to_evolution
1176 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1177 MINUS_EXPR, rhs1, at_stmt);
1179 else if (res == t_dont_know)
1180 *evolution_of_loop = chrec_dont_know;
1183 /* Otherwise, match an assignment under the form:
1185 /* And there is nothing to do. */
1192 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1193 It must be handled as a copy assignment of the form a_1 = a_2. */
1194 tree op0 = ASSERT_EXPR_VAR (rhs);
1195 if (TREE_CODE (op0) == SSA_NAME)
1196 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1197 halting_phi, evolution_of_loop, limit);
1212 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1215 backedge_phi_arg_p (tree phi, int i)
1217 edge e = PHI_ARG_EDGE (phi, i);
1219 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1220 about updating it anywhere, and this should work as well most of the
1222 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1228 /* Helper function for one branch of the condition-phi-node. Return
1229 true if the strongly connected component has been found following
1232 static inline t_bool
1233 follow_ssa_edge_in_condition_phi_branch (int i,
1237 tree *evolution_of_branch,
1238 tree init_cond, int limit)
1240 tree branch = PHI_ARG_DEF (condition_phi, i);
1241 *evolution_of_branch = chrec_dont_know;
1243 /* Do not follow back edges (they must belong to an irreducible loop, which
1244 we really do not want to worry about). */
1245 if (backedge_phi_arg_p (condition_phi, i))
1248 if (TREE_CODE (branch) == SSA_NAME)
1250 *evolution_of_branch = init_cond;
1251 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1252 evolution_of_branch, limit);
1255 /* This case occurs when one of the condition branches sets
1256 the variable to a constant: i.e. a phi-node like
1257 "a_2 = PHI <a_7(5), 2(6)>;".
1259 FIXME: This case have to be refined correctly:
1260 in some cases it is possible to say something better than
1261 chrec_dont_know, for example using a wrap-around notation. */
1265 /* This function merges the branches of a condition-phi-node in a
1269 follow_ssa_edge_in_condition_phi (struct loop *loop,
1272 tree *evolution_of_loop, int limit)
1275 tree init = *evolution_of_loop;
1276 tree evolution_of_branch;
1277 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1279 &evolution_of_branch,
1281 if (res == t_false || res == t_dont_know)
1284 *evolution_of_loop = evolution_of_branch;
1286 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1288 /* Quickly give up when the evolution of one of the branches is
1290 if (*evolution_of_loop == chrec_dont_know)
1293 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1295 &evolution_of_branch,
1297 if (res == t_false || res == t_dont_know)
1300 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1301 evolution_of_branch);
1307 /* Follow an SSA edge in an inner loop. It computes the overall
1308 effect of the loop, and following the symbolic initial conditions,
1309 it follows the edges in the parent loop. The inner loop is
1310 considered as a single statement. */
1313 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1316 tree *evolution_of_loop, int limit)
1318 struct loop *loop = loop_containing_stmt (loop_phi_node);
1319 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1321 /* Sometimes, the inner loop is too difficult to analyze, and the
1322 result of the analysis is a symbolic parameter. */
1323 if (ev == PHI_RESULT (loop_phi_node))
1325 t_bool res = t_false;
1328 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1330 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1333 /* Follow the edges that exit the inner loop. */
1334 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1335 if (!flow_bb_inside_loop_p (loop, bb))
1336 res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1338 evolution_of_loop, limit);
1343 /* If the path crosses this loop-phi, give up. */
1345 *evolution_of_loop = chrec_dont_know;
1350 /* Otherwise, compute the overall effect of the inner loop. */
1351 ev = compute_overall_effect_of_inner_loop (loop, ev);
1352 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1353 evolution_of_loop, limit);
1356 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1357 path that is analyzed on the return walk. */
1360 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1361 tree *evolution_of_loop, int limit)
1363 struct loop *def_loop;
1365 if (TREE_CODE (def) == NOP_EXPR)
1368 /* Give up if the path is longer than the MAX that we allow. */
1369 if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1372 def_loop = loop_containing_stmt (def);
1374 switch (TREE_CODE (def))
1377 if (!loop_phi_node_p (def))
1378 /* DEF is a condition-phi-node. Follow the branches, and
1379 record their evolutions. Finally, merge the collected
1380 information and set the approximation to the main
1382 return follow_ssa_edge_in_condition_phi
1383 (loop, def, halting_phi, evolution_of_loop, limit);
1385 /* When the analyzed phi is the halting_phi, the
1386 depth-first search is over: we have found a path from
1387 the halting_phi to itself in the loop. */
1388 if (def == halting_phi)
1391 /* Otherwise, the evolution of the HALTING_PHI depends
1392 on the evolution of another loop-phi-node, i.e. the
1393 evolution function is a higher degree polynomial. */
1394 if (def_loop == loop)
1398 if (flow_loop_nested_p (loop, def_loop))
1399 return follow_ssa_edge_inner_loop_phi
1400 (loop, def, halting_phi, evolution_of_loop, limit);
1405 case GIMPLE_MODIFY_STMT:
1406 return follow_ssa_edge_in_rhs (loop, def,
1407 GIMPLE_STMT_OPERAND (def, 1),
1409 evolution_of_loop, limit);
1412 /* At this level of abstraction, the program is just a set
1413 of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
1414 other node to be handled. */
1421 /* Given a LOOP_PHI_NODE, this function determines the evolution
1422 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1425 analyze_evolution_in_loop (tree loop_phi_node,
1429 tree evolution_function = chrec_not_analyzed_yet;
1430 struct loop *loop = loop_containing_stmt (loop_phi_node);
1433 if (dump_file && (dump_flags & TDF_DETAILS))
1435 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1436 fprintf (dump_file, " (loop_phi_node = ");
1437 print_generic_expr (dump_file, loop_phi_node, 0);
1438 fprintf (dump_file, ")\n");
1441 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1443 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1444 tree ssa_chain, ev_fn;
1447 /* Select the edges that enter the loop body. */
1448 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1449 if (!flow_bb_inside_loop_p (loop, bb))
1452 if (TREE_CODE (arg) == SSA_NAME)
1454 ssa_chain = SSA_NAME_DEF_STMT (arg);
1456 /* Pass in the initial condition to the follow edge function. */
1458 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1463 /* When it is impossible to go back on the same
1464 loop_phi_node by following the ssa edges, the
1465 evolution is represented by a peeled chrec, i.e. the
1466 first iteration, EV_FN has the value INIT_COND, then
1467 all the other iterations it has the value of ARG.
1468 For the moment, PEELED_CHREC nodes are not built. */
1470 ev_fn = chrec_dont_know;
1472 /* When there are multiple back edges of the loop (which in fact never
1473 happens currently, but nevertheless), merge their evolutions. */
1474 evolution_function = chrec_merge (evolution_function, ev_fn);
1477 if (dump_file && (dump_flags & TDF_DETAILS))
1479 fprintf (dump_file, " (evolution_function = ");
1480 print_generic_expr (dump_file, evolution_function, 0);
1481 fprintf (dump_file, "))\n");
1484 return evolution_function;
1487 /* Given a loop-phi-node, return the initial conditions of the
1488 variable on entry of the loop. When the CCP has propagated
1489 constants into the loop-phi-node, the initial condition is
1490 instantiated, otherwise the initial condition is kept symbolic.
1491 This analyzer does not analyze the evolution outside the current
1492 loop, and leaves this task to the on-demand tree reconstructor. */
1495 analyze_initial_condition (tree loop_phi_node)
1498 tree init_cond = chrec_not_analyzed_yet;
1499 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1501 if (dump_file && (dump_flags & TDF_DETAILS))
1503 fprintf (dump_file, "(analyze_initial_condition \n");
1504 fprintf (dump_file, " (loop_phi_node = \n");
1505 print_generic_expr (dump_file, loop_phi_node, 0);
1506 fprintf (dump_file, ")\n");
1509 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1511 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1512 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1514 /* When the branch is oriented to the loop's body, it does
1515 not contribute to the initial condition. */
1516 if (flow_bb_inside_loop_p (loop, bb))
1519 if (init_cond == chrec_not_analyzed_yet)
1525 if (TREE_CODE (branch) == SSA_NAME)
1527 init_cond = chrec_dont_know;
1531 init_cond = chrec_merge (init_cond, branch);
1534 /* Ooops -- a loop without an entry??? */
1535 if (init_cond == chrec_not_analyzed_yet)
1536 init_cond = chrec_dont_know;
1538 if (dump_file && (dump_flags & TDF_DETAILS))
1540 fprintf (dump_file, " (init_cond = ");
1541 print_generic_expr (dump_file, init_cond, 0);
1542 fprintf (dump_file, "))\n");
1548 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1551 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1554 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1557 if (phi_loop != loop)
1559 struct loop *subloop;
1560 tree evolution_fn = analyze_scalar_evolution
1561 (phi_loop, PHI_RESULT (loop_phi_node));
1563 /* Dive one level deeper. */
1564 subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1566 /* Interpret the subloop. */
1567 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1571 /* Otherwise really interpret the loop phi. */
1572 init_cond = analyze_initial_condition (loop_phi_node);
1573 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1578 /* This function merges the branches of a condition-phi-node,
1579 contained in the outermost loop, and whose arguments are already
1583 interpret_condition_phi (struct loop *loop, tree condition_phi)
1586 tree res = chrec_not_analyzed_yet;
1588 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1592 if (backedge_phi_arg_p (condition_phi, i))
1594 res = chrec_dont_know;
1598 branch_chrec = analyze_scalar_evolution
1599 (loop, PHI_ARG_DEF (condition_phi, i));
1601 res = chrec_merge (res, branch_chrec);
1607 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
1608 analyze this node before, follow the definitions until ending
1609 either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
1610 return path, this function propagates evolutions (ala constant copy
1611 propagation). OPND1 is not a GIMPLE expression because we could
1612 analyze the effect of an inner loop: see interpret_loop_phi. */
1615 interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
1616 tree opnd1, tree type)
1618 tree res, opnd10, opnd11, chrec10, chrec11;
1620 if (is_gimple_min_invariant (opnd1))
1621 return chrec_convert (type, opnd1, at_stmt);
1623 switch (TREE_CODE (opnd1))
1626 opnd10 = TREE_OPERAND (opnd1, 0);
1627 opnd11 = TREE_OPERAND (opnd1, 1);
1628 chrec10 = analyze_scalar_evolution (loop, opnd10);
1629 chrec11 = analyze_scalar_evolution (loop, opnd11);
1630 chrec10 = chrec_convert (type, chrec10, at_stmt);
1631 chrec11 = chrec_convert (type, chrec11, at_stmt);
1632 res = chrec_fold_plus (type, chrec10, chrec11);
1636 opnd10 = TREE_OPERAND (opnd1, 0);
1637 opnd11 = TREE_OPERAND (opnd1, 1);
1638 chrec10 = analyze_scalar_evolution (loop, opnd10);
1639 chrec11 = analyze_scalar_evolution (loop, opnd11);
1640 chrec10 = chrec_convert (type, chrec10, at_stmt);
1641 chrec11 = chrec_convert (type, chrec11, at_stmt);
1642 res = chrec_fold_minus (type, chrec10, chrec11);
1646 opnd10 = TREE_OPERAND (opnd1, 0);
1647 chrec10 = analyze_scalar_evolution (loop, opnd10);
1648 chrec10 = chrec_convert (type, chrec10, at_stmt);
1649 /* TYPE may be integer, real or complex, so use fold_convert. */
1650 res = chrec_fold_multiply (type, chrec10,
1651 fold_convert (type, integer_minus_one_node));
1655 opnd10 = TREE_OPERAND (opnd1, 0);
1656 opnd11 = TREE_OPERAND (opnd1, 1);
1657 chrec10 = analyze_scalar_evolution (loop, opnd10);
1658 chrec11 = analyze_scalar_evolution (loop, opnd11);
1659 chrec10 = chrec_convert (type, chrec10, at_stmt);
1660 chrec11 = chrec_convert (type, chrec11, at_stmt);
1661 res = chrec_fold_multiply (type, chrec10, chrec11);
1665 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1670 opnd10 = ASSERT_EXPR_VAR (opnd1);
1671 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1677 opnd10 = TREE_OPERAND (opnd1, 0);
1678 chrec10 = analyze_scalar_evolution (loop, opnd10);
1679 res = chrec_convert (type, chrec10, at_stmt);
1683 res = chrec_dont_know;
1692 /* This section contains all the entry points:
1693 - number_of_iterations_in_loop,
1694 - analyze_scalar_evolution,
1695 - instantiate_parameters.
1698 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1699 common ancestor of DEF_LOOP and USE_LOOP. */
1702 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1703 struct loop *def_loop,
1707 if (def_loop == wrto_loop)
1710 def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1711 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1713 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1716 /* Folds EXPR, if it is a cast to pointer, assuming that the created
1717 polynomial_chrec does not wrap. */
1720 fold_used_pointer_cast (tree expr)
1723 tree type, inner_type;
1725 if (TREE_CODE (expr) != NOP_EXPR && TREE_CODE (expr) != CONVERT_EXPR)
1728 op = TREE_OPERAND (expr, 0);
1729 if (TREE_CODE (op) != POLYNOMIAL_CHREC)
1732 type = TREE_TYPE (expr);
1733 inner_type = TREE_TYPE (op);
1735 if (!INTEGRAL_TYPE_P (inner_type)
1736 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (type))
1739 return build_polynomial_chrec (CHREC_VARIABLE (op),
1740 chrec_convert (type, CHREC_LEFT (op), NULL_TREE),
1741 chrec_convert (type, CHREC_RIGHT (op), NULL_TREE));
1744 /* Returns true if EXPR is an expression corresponding to offset of pointer
1748 pointer_offset_p (tree expr)
1750 if (TREE_CODE (expr) == INTEGER_CST)
1753 if ((TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1754 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))))
1760 /* EXPR is a scalar evolution of a pointer that is dereferenced or used in
1761 comparison. This means that it must point to a part of some object in
1762 memory, which enables us to argue about overflows and possibly simplify
1763 the EXPR. AT_STMT is the statement in which this conversion has to be
1764 performed. Returns the simplified value.
1771 for (i = -n; i < n; i++)
1774 We generate the following code (assuming that size of int and size_t is
1777 for (i = -n; i < n; i++)
1782 tmp1 = (size_t) i; (1)
1783 tmp2 = 4 * tmp1; (2)
1784 tmp3 = (int *) tmp2; (3)
1785 tmp4 = p + tmp3; (4)
1790 We in general assume that pointer arithmetics does not overflow (since its
1791 behavior is undefined in that case). One of the problems is that our
1792 translation does not capture this property very well -- (int *) is
1793 considered unsigned, hence the computation in (4) does overflow if i is
1796 This impreciseness creates complications in scev analysis. The scalar
1797 evolution of i is [-n, +, 1]. Since int and size_t have the same precision
1798 (in this example), and size_t is unsigned (so we do not care about
1799 overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
1800 and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into
1801 problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
1802 places assume that this is not the case for scevs with pointer type, we
1803 cannot use this scev for tmp3; hence, its scev is
1804 (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
1805 p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to
1806 work with scevs of this shape.
1808 However, since tmp4 is dereferenced, all its values must belong to a single
1809 object, and taking into account that the precision of int * and size_t is
1810 the same, it is impossible for its scev to wrap. Hence, we can derive that
1811 its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
1814 ??? Maybe we should use different representation for pointer arithmetics,
1815 however that is a long-term project with a lot of potential for creating
1819 fold_used_pointer (tree expr, tree at_stmt)
1821 tree op0, op1, new0, new1;
1822 enum tree_code code = TREE_CODE (expr);
1824 if (code == PLUS_EXPR
1825 || code == MINUS_EXPR)
1827 op0 = TREE_OPERAND (expr, 0);
1828 op1 = TREE_OPERAND (expr, 1);
1830 if (pointer_offset_p (op1))
1832 new0 = fold_used_pointer (op0, at_stmt);
1833 new1 = fold_used_pointer_cast (op1);
1835 else if (code == PLUS_EXPR && pointer_offset_p (op0))
1837 new0 = fold_used_pointer_cast (op0);
1838 new1 = fold_used_pointer (op1, at_stmt);
1843 if (new0 == op0 && new1 == op1)
1846 new0 = chrec_convert (TREE_TYPE (expr), new0, at_stmt);
1847 new1 = chrec_convert (TREE_TYPE (expr), new1, at_stmt);
1849 if (code == PLUS_EXPR)
1850 expr = chrec_fold_plus (TREE_TYPE (expr), new0, new1);
1852 expr = chrec_fold_minus (TREE_TYPE (expr), new0, new1);
1857 return fold_used_pointer_cast (expr);
1860 /* Returns true if PTR is dereferenced, or used in comparison. */
1863 pointer_used_p (tree ptr)
1865 use_operand_p use_p;
1866 imm_use_iterator imm_iter;
1868 struct ptr_info_def *pi = get_ptr_info (ptr);
1869 var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
1871 /* Check whether the pointer has a memory tag; if it does, it is
1872 (or at least used to be) dereferenced. */
1873 if ((pi != NULL && pi->name_mem_tag != NULL)
1874 || v_ann->symbol_mem_tag)
1877 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr)
1879 stmt = USE_STMT (use_p);
1880 if (TREE_CODE (stmt) == COND_EXPR)
1883 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1886 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1887 if (!COMPARISON_CLASS_P (rhs))
1890 if (GIMPLE_STMT_OPERAND (stmt, 0) == ptr
1891 || GIMPLE_STMT_OPERAND (stmt, 1) == ptr)
1898 /* Helper recursive function. */
1901 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1903 tree def, type = TREE_TYPE (var);
1905 struct loop *def_loop;
1907 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1908 return chrec_dont_know;
1910 if (TREE_CODE (var) != SSA_NAME)
1911 return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
1913 def = SSA_NAME_DEF_STMT (var);
1914 bb = bb_for_stmt (def);
1915 def_loop = bb ? bb->loop_father : NULL;
1918 || !flow_bb_inside_loop_p (loop, bb))
1920 /* Keep the symbolic form. */
1925 if (res != chrec_not_analyzed_yet)
1927 if (loop != bb->loop_father)
1928 res = compute_scalar_evolution_in_loop
1929 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1934 if (loop != def_loop)
1936 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1937 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1942 switch (TREE_CODE (def))
1944 case GIMPLE_MODIFY_STMT:
1945 res = interpret_rhs_modify_stmt (loop, def,
1946 GIMPLE_STMT_OPERAND (def, 1), type);
1948 if (POINTER_TYPE_P (type)
1949 && !automatically_generated_chrec_p (res)
1950 && pointer_used_p (var))
1951 res = fold_used_pointer (res, def);
1955 if (loop_phi_node_p (def))
1956 res = interpret_loop_phi (loop, def);
1958 res = interpret_condition_phi (loop, def);
1962 res = chrec_dont_know;
1968 /* Keep the symbolic form. */
1969 if (res == chrec_dont_know)
1972 if (loop == def_loop)
1973 set_scalar_evolution (var, res);
1978 /* Entry point for the scalar evolution analyzer.
1979 Analyzes and returns the scalar evolution of the ssa_name VAR.
1980 LOOP_NB is the identifier number of the loop in which the variable
1983 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1984 pointer to the statement that uses this variable, in order to
1985 determine the evolution function of the variable, use the following
1988 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1989 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1990 tree chrec_instantiated = instantiate_parameters
1991 (loop_nb, chrec_with_symbols);
1995 analyze_scalar_evolution (struct loop *loop, tree var)
1999 if (dump_file && (dump_flags & TDF_DETAILS))
2001 fprintf (dump_file, "(analyze_scalar_evolution \n");
2002 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2003 fprintf (dump_file, " (scalar = ");
2004 print_generic_expr (dump_file, var, 0);
2005 fprintf (dump_file, ")\n");
2008 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
2010 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
2013 if (dump_file && (dump_flags & TDF_DETAILS))
2014 fprintf (dump_file, ")\n");
2019 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2020 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
2023 FOLDED_CASTS is set to true if resolve_mixers used
2024 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2025 at the moment in order to keep things simple). */
2028 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2029 tree version, bool *folded_casts)
2032 tree ev = version, tmp;
2035 *folded_casts = false;
2038 tmp = analyze_scalar_evolution (use_loop, ev);
2039 ev = resolve_mixers (use_loop, tmp);
2041 if (folded_casts && tmp != ev)
2042 *folded_casts = true;
2044 if (use_loop == wrto_loop)
2047 /* If the value of the use changes in the inner loop, we cannot express
2048 its value in the outer loop (we might try to return interval chrec,
2049 but we do not have a user for it anyway) */
2050 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2052 return chrec_dont_know;
2054 use_loop = use_loop->outer;
2058 /* Returns instantiated value for VERSION in CACHE. */
2061 get_instantiated_value (htab_t cache, tree version)
2063 struct scev_info_str *info, pattern;
2065 pattern.var = version;
2066 info = (struct scev_info_str *) htab_find (cache, &pattern);
2074 /* Sets instantiated value for VERSION to VAL in CACHE. */
2077 set_instantiated_value (htab_t cache, tree version, tree val)
2079 struct scev_info_str *info, pattern;
2082 pattern.var = version;
2083 slot = htab_find_slot (cache, &pattern, INSERT);
2086 *slot = new_scev_info_str (version);
2087 info = (struct scev_info_str *) *slot;
2091 /* Return the closed_loop_phi node for VAR. If there is none, return
2095 loop_closed_phi_def (tree var)
2101 if (var == NULL_TREE
2102 || TREE_CODE (var) != SSA_NAME)
2105 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2106 exit = single_exit (loop);
2110 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
2111 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2112 return PHI_RESULT (phi);
2117 /* Analyze all the parameters of the chrec that were left under a symbolic form,
2118 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
2119 of already instantiated values. FLAGS modify the way chrecs are
2120 instantiated. SIZE_EXPR is used for computing the size of the expression to
2121 be instantiated, and to stop if it exceeds some limit. */
2123 /* Values for FLAGS. */
2126 INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs
2128 FOLD_CONVERSIONS = 2 /* The conversions that may wrap in
2129 signed/pointer type are folded, as long as the
2130 value of the chrec is preserved. */
2134 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
2137 tree res, op0, op1, op2;
2139 struct loop *def_loop;
2140 tree type = chrec_type (chrec);
2142 /* Give up if the expression is larger than the MAX that we allow. */
2143 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2144 return chrec_dont_know;
2146 if (automatically_generated_chrec_p (chrec)
2147 || is_gimple_min_invariant (chrec))
2150 switch (TREE_CODE (chrec))
2153 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
2155 /* A parameter (or loop invariant and we do not want to include
2156 evolutions in outer loops), nothing to do. */
2158 || (!(flags & INSERT_SUPERLOOP_CHRECS)
2159 && !flow_bb_inside_loop_p (loop, def_bb)))
2162 /* We cache the value of instantiated variable to avoid exponential
2163 time complexity due to reevaluations. We also store the convenient
2164 value in the cache in order to prevent infinite recursion -- we do
2165 not want to instantiate the SSA_NAME if it is in a mixer
2166 structure. This is used for avoiding the instantiation of
2167 recursively defined functions, such as:
2169 | a_2 -> {0, +, 1, +, a_2}_1 */
2171 res = get_instantiated_value (cache, chrec);
2175 /* Store the convenient value for chrec in the structure. If it
2176 is defined outside of the loop, we may just leave it in symbolic
2177 form, otherwise we need to admit that we do not know its behavior
2179 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
2180 set_instantiated_value (cache, chrec, res);
2182 /* To make things even more complicated, instantiate_parameters_1
2183 calls analyze_scalar_evolution that may call # of iterations
2184 analysis that may in turn call instantiate_parameters_1 again.
2185 To prevent the infinite recursion, keep also the bitmap of
2186 ssa names that are being instantiated globally. */
2187 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2190 def_loop = find_common_loop (loop, def_bb->loop_father);
2192 /* If the analysis yields a parametric chrec, instantiate the
2194 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2195 res = analyze_scalar_evolution (def_loop, chrec);
2197 /* Don't instantiate loop-closed-ssa phi nodes. */
2198 if (TREE_CODE (res) == SSA_NAME
2199 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2200 || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth
2201 > def_loop->depth)))
2204 res = loop_closed_phi_def (chrec);
2208 if (res == NULL_TREE)
2209 res = chrec_dont_know;
2212 else if (res != chrec_dont_know)
2213 res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2215 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2217 /* Store the correct value to the cache. */
2218 set_instantiated_value (cache, chrec, res);
2221 case POLYNOMIAL_CHREC:
2222 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2223 flags, cache, size_expr);
2224 if (op0 == chrec_dont_know)
2225 return chrec_dont_know;
2227 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2228 flags, cache, size_expr);
2229 if (op1 == chrec_dont_know)
2230 return chrec_dont_know;
2232 if (CHREC_LEFT (chrec) != op0
2233 || CHREC_RIGHT (chrec) != op1)
2235 op1 = chrec_convert (chrec_type (op0), op1, NULL_TREE);
2236 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2241 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2242 flags, cache, size_expr);
2243 if (op0 == chrec_dont_know)
2244 return chrec_dont_know;
2246 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2247 flags, cache, size_expr);
2248 if (op1 == chrec_dont_know)
2249 return chrec_dont_know;
2251 if (TREE_OPERAND (chrec, 0) != op0
2252 || TREE_OPERAND (chrec, 1) != op1)
2254 op0 = chrec_convert (type, op0, NULL_TREE);
2255 op1 = chrec_convert (type, op1, NULL_TREE);
2256 chrec = chrec_fold_plus (type, op0, op1);
2261 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2262 flags, cache, size_expr);
2263 if (op0 == chrec_dont_know)
2264 return chrec_dont_know;
2266 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2267 flags, cache, size_expr);
2268 if (op1 == chrec_dont_know)
2269 return chrec_dont_know;
2271 if (TREE_OPERAND (chrec, 0) != op0
2272 || TREE_OPERAND (chrec, 1) != op1)
2274 op0 = chrec_convert (type, op0, NULL_TREE);
2275 op1 = chrec_convert (type, op1, NULL_TREE);
2276 chrec = chrec_fold_minus (type, op0, op1);
2281 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2282 flags, cache, size_expr);
2283 if (op0 == chrec_dont_know)
2284 return chrec_dont_know;
2286 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2287 flags, cache, size_expr);
2288 if (op1 == chrec_dont_know)
2289 return chrec_dont_know;
2291 if (TREE_OPERAND (chrec, 0) != op0
2292 || TREE_OPERAND (chrec, 1) != op1)
2294 op0 = chrec_convert (type, op0, NULL_TREE);
2295 op1 = chrec_convert (type, op1, NULL_TREE);
2296 chrec = chrec_fold_multiply (type, op0, op1);
2302 case NON_LVALUE_EXPR:
2303 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2304 flags, cache, size_expr);
2305 if (op0 == chrec_dont_know)
2306 return chrec_dont_know;
2308 if (flags & FOLD_CONVERSIONS)
2310 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2315 if (op0 == TREE_OPERAND (chrec, 0))
2318 /* If we used chrec_convert_aggressive, we can no longer assume that
2319 signed chrecs do not overflow, as chrec_convert does, so avoid
2320 calling it in that case. */
2321 if (flags & FOLD_CONVERSIONS)
2322 return fold_convert (TREE_TYPE (chrec), op0);
2324 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2326 case SCEV_NOT_KNOWN:
2327 return chrec_dont_know;
2336 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2339 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2340 flags, cache, size_expr);
2341 if (op0 == chrec_dont_know)
2342 return chrec_dont_know;
2344 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2345 flags, cache, size_expr);
2346 if (op1 == chrec_dont_know)
2347 return chrec_dont_know;
2349 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2350 flags, cache, size_expr);
2351 if (op2 == chrec_dont_know)
2352 return chrec_dont_know;
2354 if (op0 == TREE_OPERAND (chrec, 0)
2355 && op1 == TREE_OPERAND (chrec, 1)
2356 && op2 == TREE_OPERAND (chrec, 2))
2359 return fold_build3 (TREE_CODE (chrec),
2360 TREE_TYPE (chrec), op0, op1, op2);
2363 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2364 flags, cache, size_expr);
2365 if (op0 == chrec_dont_know)
2366 return chrec_dont_know;
2368 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2369 flags, cache, size_expr);
2370 if (op1 == chrec_dont_know)
2371 return chrec_dont_know;
2373 if (op0 == TREE_OPERAND (chrec, 0)
2374 && op1 == TREE_OPERAND (chrec, 1))
2376 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2379 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2380 flags, cache, size_expr);
2381 if (op0 == chrec_dont_know)
2382 return chrec_dont_know;
2383 if (op0 == TREE_OPERAND (chrec, 0))
2385 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2394 /* Too complicated to handle. */
2395 return chrec_dont_know;
2398 /* Analyze all the parameters of the chrec that were left under a
2399 symbolic form. LOOP is the loop in which symbolic names have to
2400 be analyzed and instantiated. */
2403 instantiate_parameters (struct loop *loop,
2407 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2409 if (dump_file && (dump_flags & TDF_DETAILS))
2411 fprintf (dump_file, "(instantiate_parameters \n");
2412 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2413 fprintf (dump_file, " (chrec = ");
2414 print_generic_expr (dump_file, chrec, 0);
2415 fprintf (dump_file, ")\n");
2418 res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2421 if (dump_file && (dump_flags & TDF_DETAILS))
2423 fprintf (dump_file, " (res = ");
2424 print_generic_expr (dump_file, res, 0);
2425 fprintf (dump_file, "))\n");
2428 htab_delete (cache);
2433 /* Similar to instantiate_parameters, but does not introduce the
2434 evolutions in outer loops for LOOP invariants in CHREC, and does not
2435 care about causing overflows, as long as they do not affect value
2436 of an expression. */
2439 resolve_mixers (struct loop *loop, tree chrec)
2441 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2442 tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2443 htab_delete (cache);
2447 /* Entry point for the analysis of the number of iterations pass.
2448 This function tries to safely approximate the number of iterations
2449 the loop will run. When this property is not decidable at compile
2450 time, the result is chrec_dont_know. Otherwise the result is
2451 a scalar or a symbolic parameter.
2453 Example of analysis: suppose that the loop has an exit condition:
2455 "if (b > 49) goto end_loop;"
2457 and that in a previous analysis we have determined that the
2458 variable 'b' has an evolution function:
2460 "EF = {23, +, 5}_2".
2462 When we evaluate the function at the point 5, i.e. the value of the
2463 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2464 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2465 the loop body has been executed 6 times. */
2468 number_of_iterations_in_loop (struct loop *loop)
2472 struct tree_niter_desc niter_desc;
2474 /* Determine whether the number_of_iterations_in_loop has already
2476 res = loop->nb_iterations;
2479 res = chrec_dont_know;
2481 if (dump_file && (dump_flags & TDF_DETAILS))
2482 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2484 exit = single_exit (loop);
2488 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2491 type = TREE_TYPE (niter_desc.niter);
2492 if (integer_nonzerop (niter_desc.may_be_zero))
2493 res = build_int_cst (type, 0);
2494 else if (integer_zerop (niter_desc.may_be_zero))
2495 res = niter_desc.niter;
2497 res = chrec_dont_know;
2500 return set_nb_iterations_in_loop (loop, res);
2503 /* One of the drivers for testing the scalar evolutions analysis.
2504 This function computes the number of iterations for all the loops
2505 from the EXIT_CONDITIONS array. */
2508 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2511 unsigned nb_chrec_dont_know_loops = 0;
2512 unsigned nb_static_loops = 0;
2515 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2517 tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
2518 if (chrec_contains_undetermined (res))
2519 nb_chrec_dont_know_loops++;
2526 fprintf (dump_file, "\n(\n");
2527 fprintf (dump_file, "-----------------------------------------\n");
2528 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2529 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2530 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2531 fprintf (dump_file, "-----------------------------------------\n");
2532 fprintf (dump_file, ")\n\n");
2534 print_loop_ir (dump_file);
2540 /* Counters for the stats. */
2546 unsigned nb_affine_multivar;
2547 unsigned nb_higher_poly;
2548 unsigned nb_chrec_dont_know;
2549 unsigned nb_undetermined;
2552 /* Reset the counters. */
2555 reset_chrecs_counters (struct chrec_stats *stats)
2557 stats->nb_chrecs = 0;
2558 stats->nb_affine = 0;
2559 stats->nb_affine_multivar = 0;
2560 stats->nb_higher_poly = 0;
2561 stats->nb_chrec_dont_know = 0;
2562 stats->nb_undetermined = 0;
2565 /* Dump the contents of a CHREC_STATS structure. */
2568 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2570 fprintf (file, "\n(\n");
2571 fprintf (file, "-----------------------------------------\n");
2572 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2573 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2574 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2575 stats->nb_higher_poly);
2576 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2577 fprintf (file, "-----------------------------------------\n");
2578 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2579 fprintf (file, "%d\twith undetermined coefficients\n",
2580 stats->nb_undetermined);
2581 fprintf (file, "-----------------------------------------\n");
2582 fprintf (file, "%d\tchrecs in the scev database\n",
2583 (int) htab_elements (scalar_evolution_info));
2584 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2585 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2586 fprintf (file, "-----------------------------------------\n");
2587 fprintf (file, ")\n\n");
2590 /* Gather statistics about CHREC. */
2593 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2595 if (dump_file && (dump_flags & TDF_STATS))
2597 fprintf (dump_file, "(classify_chrec ");
2598 print_generic_expr (dump_file, chrec, 0);
2599 fprintf (dump_file, "\n");
2604 if (chrec == NULL_TREE)
2606 stats->nb_undetermined++;
2610 switch (TREE_CODE (chrec))
2612 case POLYNOMIAL_CHREC:
2613 if (evolution_function_is_affine_p (chrec))
2615 if (dump_file && (dump_flags & TDF_STATS))
2616 fprintf (dump_file, " affine_univariate\n");
2619 else if (evolution_function_is_affine_multivariate_p (chrec))
2621 if (dump_file && (dump_flags & TDF_STATS))
2622 fprintf (dump_file, " affine_multivariate\n");
2623 stats->nb_affine_multivar++;
2627 if (dump_file && (dump_flags & TDF_STATS))
2628 fprintf (dump_file, " higher_degree_polynomial\n");
2629 stats->nb_higher_poly++;
2638 if (chrec_contains_undetermined (chrec))
2640 if (dump_file && (dump_flags & TDF_STATS))
2641 fprintf (dump_file, " undetermined\n");
2642 stats->nb_undetermined++;
2645 if (dump_file && (dump_flags & TDF_STATS))
2646 fprintf (dump_file, ")\n");
2649 /* One of the drivers for testing the scalar evolutions analysis.
2650 This function analyzes the scalar evolution of all the scalars
2651 defined as loop phi nodes in one of the loops from the
2652 EXIT_CONDITIONS array.
2654 TODO Optimization: A loop is in canonical form if it contains only
2655 a single scalar loop phi node. All the other scalars that have an
2656 evolution in the loop are rewritten in function of this single
2657 index. This allows the parallelization of the loop. */
2660 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2663 struct chrec_stats stats;
2666 reset_chrecs_counters (&stats);
2668 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2674 loop = loop_containing_stmt (cond);
2677 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2678 if (is_gimple_reg (PHI_RESULT (phi)))
2680 chrec = instantiate_parameters
2682 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2684 if (dump_file && (dump_flags & TDF_STATS))
2685 gather_chrec_stats (chrec, &stats);
2689 if (dump_file && (dump_flags & TDF_STATS))
2690 dump_chrecs_stats (dump_file, &stats);
2693 /* Callback for htab_traverse, gathers information on chrecs in the
2697 gather_stats_on_scev_database_1 (void **slot, void *stats)
2699 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2701 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2706 /* Classify the chrecs of the whole database. */
2709 gather_stats_on_scev_database (void)
2711 struct chrec_stats stats;
2716 reset_chrecs_counters (&stats);
2718 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2721 dump_chrecs_stats (dump_file, &stats);
2729 initialize_scalar_evolutions_analyzer (void)
2731 /* The elements below are unique. */
2732 if (chrec_dont_know == NULL_TREE)
2734 chrec_not_analyzed_yet = NULL_TREE;
2735 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2736 chrec_known = make_node (SCEV_KNOWN);
2737 TREE_TYPE (chrec_dont_know) = void_type_node;
2738 TREE_TYPE (chrec_known) = void_type_node;
2742 /* Initialize the analysis of scalar evolutions for LOOPS. */
2745 scev_initialize (void)
2750 scalar_evolution_info = htab_create (100, hash_scev_info,
2751 eq_scev_info, del_scev_info);
2752 already_instantiated = BITMAP_ALLOC (NULL);
2754 initialize_scalar_evolutions_analyzer ();
2756 FOR_EACH_LOOP (li, loop, 0)
2758 loop->nb_iterations = NULL_TREE;
2762 /* Cleans up the information cached by the scalar evolutions analysis. */
2770 if (!scalar_evolution_info || !current_loops)
2773 htab_empty (scalar_evolution_info);
2774 FOR_EACH_LOOP (li, loop, 0)
2776 loop->nb_iterations = NULL_TREE;
2780 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2781 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2782 want step to be invariant in LOOP. Otherwise we require it to be an
2783 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2784 overflow (e.g. because it is computed in signed arithmetics). */
2787 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2788 bool allow_nonconstant_step)
2790 basic_block bb = bb_for_stmt (stmt);
2794 iv->base = NULL_TREE;
2795 iv->step = NULL_TREE;
2796 iv->no_overflow = false;
2798 type = TREE_TYPE (op);
2799 if (TREE_CODE (type) != INTEGER_TYPE
2800 && TREE_CODE (type) != POINTER_TYPE)
2803 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2805 if (chrec_contains_undetermined (ev))
2808 if (tree_does_not_contain_chrecs (ev)
2809 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2812 iv->no_overflow = true;
2816 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2817 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2820 iv->step = CHREC_RIGHT (ev);
2821 if (allow_nonconstant_step)
2823 if (tree_contains_chrecs (iv->step, NULL)
2824 || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2827 else if (TREE_CODE (iv->step) != INTEGER_CST)
2830 iv->base = CHREC_LEFT (ev);
2831 if (tree_contains_chrecs (iv->base, NULL)
2832 || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2835 iv->no_overflow = (!folded_casts
2837 && !TYPE_UNSIGNED (type));
2841 /* Runs the analysis of scalar evolutions. */
2844 scev_analysis (void)
2846 VEC(tree,heap) *exit_conditions;
2848 exit_conditions = VEC_alloc (tree, heap, 37);
2849 select_loops_exit_conditions (&exit_conditions);
2851 if (dump_file && (dump_flags & TDF_STATS))
2852 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2854 number_of_iterations_for_all_loops (&exit_conditions);
2855 VEC_free (tree, heap, exit_conditions);
2858 /* Finalize the scalar evolution analysis. */
2861 scev_finalize (void)
2863 htab_delete (scalar_evolution_info);
2864 BITMAP_FREE (already_instantiated);
2867 /* Returns true if EXPR looks expensive. */
2870 expression_expensive_p (tree expr)
2872 return force_expr_to_var_cost (expr) >= target_spill_cost;
2875 /* Replace ssa names for that scev can prove they are constant by the
2876 appropriate constants. Also perform final value replacement in loops,
2877 in case the replacement expressions are cheap.
2879 We only consider SSA names defined by phi nodes; rest is left to the
2880 ordinary constant propagation pass. */
2883 scev_const_prop (void)
2886 tree name, phi, next_phi, type, ev;
2887 struct loop *loop, *ex_loop;
2888 bitmap ssa_names_to_remove = NULL;
2897 loop = bb->loop_father;
2899 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2901 name = PHI_RESULT (phi);
2903 if (!is_gimple_reg (name))
2906 type = TREE_TYPE (name);
2908 if (!POINTER_TYPE_P (type)
2909 && !INTEGRAL_TYPE_P (type))
2912 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2913 if (!is_gimple_min_invariant (ev)
2914 || !may_propagate_copy (name, ev))
2917 /* Replace the uses of the name. */
2919 replace_uses_by (name, ev);
2921 if (!ssa_names_to_remove)
2922 ssa_names_to_remove = BITMAP_ALLOC (NULL);
2923 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2927 /* Remove the ssa names that were replaced by constants. We do not remove them
2928 directly in the previous cycle, since this invalidates scev cache. */
2929 if (ssa_names_to_remove)
2933 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2935 name = ssa_name (i);
2936 phi = SSA_NAME_DEF_STMT (name);
2938 gcc_assert (TREE_CODE (phi) == PHI_NODE);
2939 remove_phi_node (phi, NULL);
2942 BITMAP_FREE (ssa_names_to_remove);
2946 /* Now the regular final value replacement. */
2947 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2950 tree def, rslt, ass, niter;
2951 block_stmt_iterator bsi;
2953 /* If we do not know exact number of iterations of the loop, we cannot
2954 replace the final value. */
2955 exit = single_exit (loop);
2959 niter = number_of_iterations_in_loop (loop);
2960 if (niter == chrec_dont_know
2961 /* If computing the number of iterations is expensive, it may be
2962 better not to introduce computations involving it. */
2963 || expression_expensive_p (niter))
2966 /* Ensure that it is possible to insert new statements somewhere. */
2967 if (!single_pred_p (exit->dest))
2968 split_loop_exit_edge (exit);
2969 tree_block_label (exit->dest);
2970 bsi = bsi_after_labels (exit->dest);
2972 ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1);
2974 for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2976 next_phi = PHI_CHAIN (phi);
2977 rslt = PHI_RESULT (phi);
2978 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2979 if (!is_gimple_reg (def))
2982 if (!POINTER_TYPE_P (TREE_TYPE (def))
2983 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2986 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2987 def = compute_overall_effect_of_inner_loop (ex_loop, def);
2988 if (!tree_does_not_contain_chrecs (def)
2989 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2990 /* Moving the computation from the loop may prolong life range
2991 of some ssa names, which may cause problems if they appear
2992 on abnormal edges. */
2993 || contains_abnormal_ssa_name_p (def))
2996 /* Eliminate the phi node and replace it by a computation outside
2998 def = unshare_expr (def);
2999 SET_PHI_RESULT (phi, NULL_TREE);
3000 remove_phi_node (phi, NULL_TREE);
3002 ass = build2 (GIMPLE_MODIFY_STMT, void_type_node, rslt, NULL_TREE);
3003 SSA_NAME_DEF_STMT (rslt) = ass;
3005 block_stmt_iterator dest = bsi;
3006 bsi_insert_before (&dest, ass, BSI_NEW_STMT);
3007 def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE);
3009 GIMPLE_STMT_OPERAND (ass, 1) = def;