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 MODIFY_EXPR: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters ({a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2: Illustration of the algorithm on nested loops.
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
158 Example 3: Higher degree polynomials.
172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175 Example 4: Lucas, Fibonacci, or mixers in general.
187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188 following semantics: during the first iteration of the loop_1, the
189 variable contains the value 1, and then it contains the value "c".
190 Note that this syntax is close to the syntax of the loop-phi-node:
191 "a -> (1, c)_1" vs. "a = phi (1, c)".
193 The symbolic chrec representation contains all the semantics of the
194 original code. What is more difficult is to use this information.
196 Example 5: Flip-flops, or exchangers.
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
214 This transformation is not yet implemented.
218 You can find a more detailed description of the algorithm in:
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
221 this is a preliminary report and some of the details of the
222 algorithm have changed. I'm working on a research report that
223 updates the description of the algorithms to reflect the design
224 choices used in this implementation.
226 A set of slides show a high level overview of the algorithm and run
227 an example through the scalar evolution analyzer:
228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230 The slides that I have presented at the GCC Summit'04 are available
231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
236 #include "coretypes.h"
242 /* These RTL headers are needed for basic-block.h. */
244 #include "basic-block.h"
245 #include "diagnostic.h"
246 #include "tree-flow.h"
247 #include "tree-dump.h"
250 #include "tree-chrec.h"
251 #include "tree-scalar-evolution.h"
252 #include "tree-pass.h"
255 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
256 static tree
resolve_mixers (struct loop
*, tree
);
258 /* The cached information about a ssa name VAR, claiming that inside LOOP,
259 the value of VAR can be expressed as CHREC. */
267 /* Counters for the scev database. */
268 static unsigned nb_set_scev
= 0;
269 static unsigned nb_get_scev
= 0;
271 /* The following trees are unique elements. Thus the comparison of
272 another element to these elements should be done on the pointer to
273 these trees, and not on their value. */
275 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
276 tree chrec_not_analyzed_yet
;
278 /* Reserved to the cases where the analyzer has detected an
279 undecidable property at compile time. */
280 tree chrec_dont_know
;
282 /* When the analyzer has detected that a property will never
283 happen, then it qualifies it with chrec_known. */
286 static bitmap already_instantiated
;
288 static htab_t scalar_evolution_info
;
291 /* Constructs a new SCEV_INFO_STR structure. */
293 static inline struct scev_info_str
*
294 new_scev_info_str (tree var
)
296 struct scev_info_str
*res
;
298 res
= xmalloc (sizeof (struct scev_info_str
));
300 res
->chrec
= chrec_not_analyzed_yet
;
305 /* Computes a hash function for database element ELT. */
308 hash_scev_info (const void *elt
)
310 return SSA_NAME_VERSION (((struct scev_info_str
*) elt
)->var
);
313 /* Compares database elements E1 and E2. */
316 eq_scev_info (const void *e1
, const void *e2
)
318 const struct scev_info_str
*elt1
= e1
;
319 const struct scev_info_str
*elt2
= e2
;
321 return elt1
->var
== elt2
->var
;
324 /* Deletes database element E. */
327 del_scev_info (void *e
)
332 /* Get the index corresponding to VAR in the current LOOP. If
333 it's the first time we ask for this VAR, then we return
334 chrec_not_analyzed_yet for this VAR and return its index. */
337 find_var_scev_info (tree var
)
339 struct scev_info_str
*res
;
340 struct scev_info_str tmp
;
344 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
347 *slot
= new_scev_info_str (var
);
353 /* Return true when CHREC contains symbolic names defined in
357 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
359 if (chrec
== NULL_TREE
)
362 if (TREE_INVARIANT (chrec
))
365 if (TREE_CODE (chrec
) == VAR_DECL
366 || TREE_CODE (chrec
) == PARM_DECL
367 || TREE_CODE (chrec
) == FUNCTION_DECL
368 || TREE_CODE (chrec
) == LABEL_DECL
369 || TREE_CODE (chrec
) == RESULT_DECL
370 || TREE_CODE (chrec
) == FIELD_DECL
)
373 if (TREE_CODE (chrec
) == SSA_NAME
)
375 tree def
= SSA_NAME_DEF_STMT (chrec
);
376 struct loop
*def_loop
= loop_containing_stmt (def
);
377 struct loop
*loop
= current_loops
->parray
[loop_nb
];
379 if (def_loop
== NULL
)
382 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
388 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
391 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 2),
396 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 1),
401 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 0),
410 /* Return true when PHI is a loop-phi-node. */
413 loop_phi_node_p (tree phi
)
415 /* The implementation of this function is based on the following
416 property: "all the loop-phi-nodes of a loop are contained in the
417 loop's header basic block". */
419 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
422 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
423 In general, in the case of multivariate evolutions we want to get
424 the evolution in different loops. LOOP specifies the level for
425 which to get the evolution.
429 | for (j = 0; j < 100; j++)
431 | for (k = 0; k < 100; k++)
433 | i = k + j; - Here the value of i is a function of j, k.
435 | ... = i - Here the value of i is a function of j.
437 | ... = i - Here the value of i is a scalar.
443 | i_1 = phi (i_0, i_2)
447 This loop has the same effect as:
448 LOOP_1 has the same effect as:
452 The overall effect of the loop, "i_0 + 20" in the previous example,
453 is obtained by passing in the parameters: LOOP = 1,
454 EVOLUTION_FN = {i_0, +, 2}_1.
458 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
462 if (evolution_fn
== chrec_dont_know
)
463 return chrec_dont_know
;
465 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
467 if (CHREC_VARIABLE (evolution_fn
) >= (unsigned) loop
->num
)
469 struct loop
*inner_loop
=
470 current_loops
->parray
[CHREC_VARIABLE (evolution_fn
)];
471 tree nb_iter
= number_of_iterations_in_loop (inner_loop
);
473 if (nb_iter
== chrec_dont_know
)
474 return chrec_dont_know
;
479 /* Number of iterations is off by one (the ssa name we
480 analyze must be defined before the exit). */
481 nb_iter
= chrec_fold_minus (chrec_type (nb_iter
),
483 build_int_cst_type (chrec_type (nb_iter
), 1));
485 /* evolution_fn is the evolution function in LOOP. Get
486 its value in the nb_iter-th iteration. */
487 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
489 /* Continue the computation until ending on a parent of LOOP. */
490 return compute_overall_effect_of_inner_loop (loop
, res
);
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
)
517 switch (TREE_CODE (chrec
))
519 case POLYNOMIAL_CHREC
:
520 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
521 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
524 /* FIXME -- overflows. */
525 if (value0
== value1
)
531 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
532 and the proof consists in showing that the sign never
533 changes during the execution of the loop, from 0 to
534 loop->nb_iterations. */
535 if (!evolution_function_is_affine_p (chrec
))
538 nb_iter
= number_of_iterations_in_loop
539 (current_loops
->parray
[CHREC_VARIABLE (chrec
)]);
541 if (chrec_contains_undetermined (nb_iter
))
544 nb_iter
= chrec_fold_minus
545 (chrec_type (nb_iter
), nb_iter
,
546 build_int_cst (chrec_type (nb_iter
), 1));
549 /* TODO -- If the test is after the exit, we may decrease the number of
550 iterations by one. */
552 nb_iter
= chrec_fold_minus
553 (chrec_type (nb_iter
), nb_iter
,
554 build_int_cst (chrec_type (nb_iter
), 1));
557 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
559 if (!chrec_is_positive (end_value
, &value2
))
563 return value0
== value1
;
566 *value
= (tree_int_cst_sgn (chrec
) == 1);
574 /* Associate CHREC to SCALAR. */
577 set_scalar_evolution (tree scalar
, tree chrec
)
581 if (TREE_CODE (scalar
) != SSA_NAME
)
584 scalar_info
= find_var_scev_info (scalar
);
588 if (dump_flags
& TDF_DETAILS
)
590 fprintf (dump_file
, "(set_scalar_evolution \n");
591 fprintf (dump_file
, " (scalar = ");
592 print_generic_expr (dump_file
, scalar
, 0);
593 fprintf (dump_file
, ")\n (scalar_evolution = ");
594 print_generic_expr (dump_file
, chrec
, 0);
595 fprintf (dump_file
, "))\n");
597 if (dump_flags
& TDF_STATS
)
601 *scalar_info
= chrec
;
604 /* Retrieve the chrec associated to SCALAR in the LOOP. */
607 get_scalar_evolution (tree scalar
)
613 if (dump_flags
& TDF_DETAILS
)
615 fprintf (dump_file
, "(get_scalar_evolution \n");
616 fprintf (dump_file
, " (scalar = ");
617 print_generic_expr (dump_file
, scalar
, 0);
618 fprintf (dump_file
, ")\n");
620 if (dump_flags
& TDF_STATS
)
624 switch (TREE_CODE (scalar
))
627 res
= *find_var_scev_info (scalar
);
636 res
= chrec_not_analyzed_yet
;
640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
642 fprintf (dump_file
, " (scalar_evolution = ");
643 print_generic_expr (dump_file
, res
, 0);
644 fprintf (dump_file
, "))\n");
650 /* Helper function for add_to_evolution. Returns the evolution
651 function for an assignment of the form "a = b + c", where "a" and
652 "b" are on the strongly connected component. CHREC_BEFORE is the
653 information that we already have collected up to this point.
654 TO_ADD is the evolution of "c".
656 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
657 evolution the expression TO_ADD, otherwise construct an evolution
658 part for this loop. */
661 add_to_evolution_1 (unsigned loop_nb
,
665 switch (TREE_CODE (chrec_before
))
667 case POLYNOMIAL_CHREC
:
668 if (CHREC_VARIABLE (chrec_before
) <= loop_nb
)
672 tree type
= chrec_type (chrec_before
);
674 /* When there is no evolution part in this loop, build it. */
675 if (CHREC_VARIABLE (chrec_before
) < loop_nb
)
679 right
= build_int_cst (type
, 0);
683 var
= CHREC_VARIABLE (chrec_before
);
684 left
= CHREC_LEFT (chrec_before
);
685 right
= CHREC_RIGHT (chrec_before
);
688 return build_polynomial_chrec
689 (var
, left
, chrec_fold_plus (type
, right
, to_add
));
692 /* Search the evolution in LOOP_NB. */
693 return build_polynomial_chrec
694 (CHREC_VARIABLE (chrec_before
),
695 add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
), to_add
),
696 CHREC_RIGHT (chrec_before
));
699 /* These nodes do not depend on a loop. */
700 if (chrec_before
== chrec_dont_know
)
701 return chrec_dont_know
;
702 return build_polynomial_chrec (loop_nb
, chrec_before
, to_add
);
706 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
709 Description (provided for completeness, for those who read code in
710 a plane, and for my poor 62 bytes brain that would have forgotten
711 all this in the next two or three months):
713 The algorithm of translation of programs from the SSA representation
714 into the chrecs syntax is based on a pattern matching. After having
715 reconstructed the overall tree expression for a loop, there are only
716 two cases that can arise:
718 1. a = loop-phi (init, a + expr)
719 2. a = loop-phi (init, expr)
721 where EXPR is either a scalar constant with respect to the analyzed
722 loop (this is a degree 0 polynomial), or an expression containing
723 other loop-phi definitions (these are higher degree polynomials).
730 | a = phi (init, a + 5)
737 | a = phi (inita, 2 * b + 3)
738 | b = phi (initb, b + 1)
741 For the first case, the semantics of the SSA representation is:
743 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
745 that is, there is a loop index "x" that determines the scalar value
746 of the variable during the loop execution. During the first
747 iteration, the value is that of the initial condition INIT, while
748 during the subsequent iterations, it is the sum of the initial
749 condition with the sum of all the values of EXPR from the initial
750 iteration to the before last considered iteration.
752 For the second case, the semantics of the SSA program is:
754 | a (x) = init, if x = 0;
755 | expr (x - 1), otherwise.
757 The second case corresponds to the PEELED_CHREC, whose syntax is
758 close to the syntax of a loop-phi-node:
760 | phi (init, expr) vs. (init, expr)_x
762 The proof of the translation algorithm for the first case is a
763 proof by structural induction based on the degree of EXPR.
766 When EXPR is a constant with respect to the analyzed loop, or in
767 other words when EXPR is a polynomial of degree 0, the evolution of
768 the variable A in the loop is an affine function with an initial
769 condition INIT, and a step EXPR. In order to show this, we start
770 from the semantics of the SSA representation:
772 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
774 and since "expr (j)" is a constant with respect to "j",
776 f (x) = init + x * expr
778 Finally, based on the semantics of the pure sum chrecs, by
779 identification we get the corresponding chrecs syntax:
781 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
782 f (x) -> {init, +, expr}_x
785 Suppose that EXPR is a polynomial of degree N with respect to the
786 analyzed loop_x for which we have already determined that it is
787 written under the chrecs syntax:
789 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
791 We start from the semantics of the SSA program:
793 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
795 | f (x) = init + \sum_{j = 0}^{x - 1}
796 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
798 | f (x) = init + \sum_{j = 0}^{x - 1}
799 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
801 | f (x) = init + \sum_{k = 0}^{n - 1}
802 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
804 | f (x) = init + \sum_{k = 0}^{n - 1}
805 | (b_k * \binom{x}{k + 1})
807 | f (x) = init + b_0 * \binom{x}{1} + ...
808 | + b_{n-1} * \binom{x}{n}
810 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
811 | + b_{n-1} * \binom{x}{n}
814 And finally from the definition of the chrecs syntax, we identify:
815 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
817 This shows the mechanism that stands behind the add_to_evolution
818 function. An important point is that the use of symbolic
819 parameters avoids the need of an analysis schedule.
826 | a = phi (inita, a + 2 + b)
827 | b = phi (initb, b + 1)
830 When analyzing "a", the algorithm keeps "b" symbolically:
832 | a -> {inita, +, 2 + b}_1
834 Then, after instantiation, the analyzer ends on the evolution:
836 | a -> {inita, +, 2 + initb, +, 1}_1
841 add_to_evolution (unsigned loop_nb
,
846 tree type
= chrec_type (to_add
);
847 tree res
= NULL_TREE
;
849 if (to_add
== NULL_TREE
)
852 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
853 instantiated at this point. */
854 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
855 /* This should not happen. */
856 return chrec_dont_know
;
858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
860 fprintf (dump_file
, "(add_to_evolution \n");
861 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
862 fprintf (dump_file
, " (chrec_before = ");
863 print_generic_expr (dump_file
, chrec_before
, 0);
864 fprintf (dump_file
, ")\n (to_add = ");
865 print_generic_expr (dump_file
, to_add
, 0);
866 fprintf (dump_file
, ")\n");
869 if (code
== MINUS_EXPR
)
870 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
871 ? build_real (type
, dconstm1
)
872 : build_int_cst_type (type
, -1));
874 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
);
876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
878 fprintf (dump_file
, " (res = ");
879 print_generic_expr (dump_file
, res
, 0);
880 fprintf (dump_file
, "))\n");
886 /* Helper function. */
889 set_nb_iterations_in_loop (struct loop
*loop
,
892 res
= chrec_fold_plus (chrec_type (res
), res
,
893 build_int_cst_type (chrec_type (res
), 1));
895 /* FIXME HWI: However we want to store one iteration less than the
896 count of the loop in order to be compatible with the other
897 nb_iter computations in loop-iv. This also allows the
898 representation of nb_iters that are equal to MAX_INT. */
899 if (TREE_CODE (res
) == INTEGER_CST
900 && (TREE_INT_CST_LOW (res
) == 0
901 || TREE_OVERFLOW (res
)))
902 res
= chrec_dont_know
;
904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
906 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
907 print_generic_expr (dump_file
, res
, 0);
908 fprintf (dump_file
, "))\n");
911 loop
->nb_iterations
= res
;
917 /* This section selects the loops that will be good candidates for the
918 scalar evolution analysis. For the moment, greedily select all the
919 loop nests we could analyze. */
921 /* Return true when it is possible to analyze the condition expression
925 analyzable_condition (tree expr
)
929 if (TREE_CODE (expr
) != COND_EXPR
)
932 condition
= TREE_OPERAND (expr
, 0);
934 switch (TREE_CODE (condition
))
954 /* For a loop with a single exit edge, return the COND_EXPR that
955 guards the exit edge. If the expression is too difficult to
956 analyze, then give up. */
959 get_loop_exit_condition (struct loop
*loop
)
961 tree res
= NULL_TREE
;
962 edge exit_edge
= loop
->single_exit
;
965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
966 fprintf (dump_file
, "(get_loop_exit_condition \n ");
972 expr
= last_stmt (exit_edge
->src
);
973 if (analyzable_condition (expr
))
977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
979 print_generic_expr (dump_file
, res
, 0);
980 fprintf (dump_file
, ")\n");
986 /* Recursively determine and enqueue the exit conditions for a loop. */
989 get_exit_conditions_rec (struct loop
*loop
,
990 VEC(tree
,heap
) **exit_conditions
)
995 /* Recurse on the inner loops, then on the next (sibling) loops. */
996 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
997 get_exit_conditions_rec (loop
->next
, exit_conditions
);
999 if (loop
->single_exit
)
1001 tree loop_condition
= get_loop_exit_condition (loop
);
1004 VEC_safe_push (tree
, heap
, *exit_conditions
, loop_condition
);
1008 /* Select the candidate loop nests for the analysis. This function
1009 initializes the EXIT_CONDITIONS array. */
1012 select_loops_exit_conditions (struct loops
*loops
,
1013 VEC(tree
,heap
) **exit_conditions
)
1015 struct loop
*function_body
= loops
->parray
[0];
1017 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
1021 /* Depth first search algorithm. */
1023 static bool follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*);
1025 /* Follow the ssa edge into the right hand side RHS of an assignment.
1026 Return true if the strongly connected component has been found. */
1029 follow_ssa_edge_in_rhs (struct loop
*loop
,
1033 tree
*evolution_of_loop
)
1037 tree type_rhs
= TREE_TYPE (rhs
);
1039 /* The RHS is one of the following cases:
1045 - other cases are not yet handled. */
1046 switch (TREE_CODE (rhs
))
1049 /* This assignment is under the form "a_1 = (cast) rhs. */
1050 res
= follow_ssa_edge_in_rhs (loop
, at_stmt
, TREE_OPERAND (rhs
, 0),
1051 halting_phi
, evolution_of_loop
);
1052 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
),
1053 *evolution_of_loop
, at_stmt
);
1057 /* This assignment is under the form "a_1 = 7". */
1062 /* This assignment is under the form: "a_1 = b_2". */
1063 res
= follow_ssa_edge
1064 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
);
1068 /* This case is under the form "rhs0 + rhs1". */
1069 rhs0
= TREE_OPERAND (rhs
, 0);
1070 rhs1
= TREE_OPERAND (rhs
, 1);
1071 STRIP_TYPE_NOPS (rhs0
);
1072 STRIP_TYPE_NOPS (rhs1
);
1074 if (TREE_CODE (rhs0
) == SSA_NAME
)
1076 if (TREE_CODE (rhs1
) == SSA_NAME
)
1078 /* Match an assignment under the form:
1080 res
= follow_ssa_edge
1081 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1085 *evolution_of_loop
= add_to_evolution
1087 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1092 res
= follow_ssa_edge
1093 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1097 *evolution_of_loop
= add_to_evolution
1099 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1106 /* Match an assignment under the form:
1108 res
= follow_ssa_edge
1109 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1112 *evolution_of_loop
= add_to_evolution
1113 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1119 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1121 /* Match an assignment under the form:
1123 res
= follow_ssa_edge
1124 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1127 *evolution_of_loop
= add_to_evolution
1128 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1134 /* Otherwise, match an assignment under the form:
1136 /* And there is nothing to do. */
1142 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1143 rhs0
= TREE_OPERAND (rhs
, 0);
1144 rhs1
= TREE_OPERAND (rhs
, 1);
1145 STRIP_TYPE_NOPS (rhs0
);
1146 STRIP_TYPE_NOPS (rhs1
);
1148 if (TREE_CODE (rhs0
) == SSA_NAME
)
1150 /* Match an assignment under the form:
1152 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1155 *evolution_of_loop
= add_to_evolution
1156 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1161 /* Otherwise, match an assignment under the form:
1163 /* And there is nothing to do. */
1169 /* This case is under the form "opnd0 = rhs0 * rhs1". */
1170 rhs0
= TREE_OPERAND (rhs
, 0);
1171 rhs1
= TREE_OPERAND (rhs
, 1);
1172 STRIP_TYPE_NOPS (rhs0
);
1173 STRIP_TYPE_NOPS (rhs1
);
1175 if (TREE_CODE (rhs0
) == SSA_NAME
)
1177 if (TREE_CODE (rhs1
) == SSA_NAME
)
1179 /* Match an assignment under the form:
1181 res
= follow_ssa_edge
1182 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1186 *evolution_of_loop
= chrec_dont_know
;
1190 res
= follow_ssa_edge
1191 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1195 *evolution_of_loop
= chrec_dont_know
;
1201 /* Match an assignment under the form:
1203 res
= follow_ssa_edge
1204 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1207 *evolution_of_loop
= chrec_dont_know
;
1211 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1213 /* Match an assignment under the form:
1215 res
= follow_ssa_edge
1216 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1219 *evolution_of_loop
= chrec_dont_know
;
1223 /* Otherwise, match an assignment under the form:
1225 /* And there is nothing to do. */
1232 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1233 It must be handled as a copy assignment of the form a_1 = a_2. */
1234 tree op0
= ASSERT_EXPR_VAR (rhs
);
1235 if (TREE_CODE (op0
) == SSA_NAME
)
1236 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1237 halting_phi
, evolution_of_loop
);
1252 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1255 backedge_phi_arg_p (tree phi
, int i
)
1257 edge e
= PHI_ARG_EDGE (phi
, i
);
1259 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1260 about updating it anywhere, and this should work as well most of the
1262 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1268 /* Helper function for one branch of the condition-phi-node. Return
1269 true if the strongly connected component has been found following
1273 follow_ssa_edge_in_condition_phi_branch (int i
,
1277 tree
*evolution_of_branch
,
1280 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1281 *evolution_of_branch
= chrec_dont_know
;
1283 /* Do not follow back edges (they must belong to an irreducible loop, which
1284 we really do not want to worry about). */
1285 if (backedge_phi_arg_p (condition_phi
, i
))
1288 if (TREE_CODE (branch
) == SSA_NAME
)
1290 *evolution_of_branch
= init_cond
;
1291 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1292 evolution_of_branch
);
1295 /* This case occurs when one of the condition branches sets
1296 the variable to a constant: i.e. a phi-node like
1297 "a_2 = PHI <a_7(5), 2(6)>;".
1299 FIXME: This case have to be refined correctly:
1300 in some cases it is possible to say something better than
1301 chrec_dont_know, for example using a wrap-around notation. */
1305 /* This function merges the branches of a condition-phi-node in a
1309 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1312 tree
*evolution_of_loop
)
1315 tree init
= *evolution_of_loop
;
1316 tree evolution_of_branch
;
1318 if (!follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1320 &evolution_of_branch
,
1323 *evolution_of_loop
= evolution_of_branch
;
1325 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1327 /* Quickly give up when the evolution of one of the branches is
1329 if (*evolution_of_loop
== chrec_dont_know
)
1332 if (!follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1334 &evolution_of_branch
,
1338 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1339 evolution_of_branch
);
1345 /* Follow an SSA edge in an inner loop. It computes the overall
1346 effect of the loop, and following the symbolic initial conditions,
1347 it follows the edges in the parent loop. The inner loop is
1348 considered as a single statement. */
1351 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1354 tree
*evolution_of_loop
)
1356 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1357 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1359 /* Sometimes, the inner loop is too difficult to analyze, and the
1360 result of the analysis is a symbolic parameter. */
1361 if (ev
== PHI_RESULT (loop_phi_node
))
1366 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1368 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1371 /* Follow the edges that exit the inner loop. */
1372 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1373 if (!flow_bb_inside_loop_p (loop
, bb
))
1374 res
= res
|| follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
,
1379 /* If the path crosses this loop-phi, give up. */
1381 *evolution_of_loop
= chrec_dont_know
;
1386 /* Otherwise, compute the overall effect of the inner loop. */
1387 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1388 return follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1392 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1393 path that is analyzed on the return walk. */
1396 follow_ssa_edge (struct loop
*loop
,
1399 tree
*evolution_of_loop
)
1401 struct loop
*def_loop
;
1403 if (TREE_CODE (def
) == NOP_EXPR
)
1406 def_loop
= loop_containing_stmt (def
);
1408 switch (TREE_CODE (def
))
1411 if (!loop_phi_node_p (def
))
1412 /* DEF is a condition-phi-node. Follow the branches, and
1413 record their evolutions. Finally, merge the collected
1414 information and set the approximation to the main
1416 return follow_ssa_edge_in_condition_phi
1417 (loop
, def
, halting_phi
, evolution_of_loop
);
1419 /* When the analyzed phi is the halting_phi, the
1420 depth-first search is over: we have found a path from
1421 the halting_phi to itself in the loop. */
1422 if (def
== halting_phi
)
1425 /* Otherwise, the evolution of the HALTING_PHI depends
1426 on the evolution of another loop-phi-node, i.e. the
1427 evolution function is a higher degree polynomial. */
1428 if (def_loop
== loop
)
1432 if (flow_loop_nested_p (loop
, def_loop
))
1433 return follow_ssa_edge_inner_loop_phi
1434 (loop
, def
, halting_phi
, evolution_of_loop
);
1440 return follow_ssa_edge_in_rhs (loop
, def
,
1441 TREE_OPERAND (def
, 1),
1446 /* At this level of abstraction, the program is just a set
1447 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1448 other node to be handled. */
1455 /* Given a LOOP_PHI_NODE, this function determines the evolution
1456 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1459 analyze_evolution_in_loop (tree loop_phi_node
,
1463 tree evolution_function
= chrec_not_analyzed_yet
;
1464 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1469 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1470 fprintf (dump_file
, " (loop_phi_node = ");
1471 print_generic_expr (dump_file
, loop_phi_node
, 0);
1472 fprintf (dump_file
, ")\n");
1475 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1477 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1478 tree ssa_chain
, ev_fn
;
1481 /* Select the edges that enter the loop body. */
1482 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1483 if (!flow_bb_inside_loop_p (loop
, bb
))
1486 if (TREE_CODE (arg
) == SSA_NAME
)
1488 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1490 /* Pass in the initial condition to the follow edge function. */
1492 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
);
1497 /* When it is impossible to go back on the same
1498 loop_phi_node by following the ssa edges, the
1499 evolution is represented by a peeled chrec, i.e. the
1500 first iteration, EV_FN has the value INIT_COND, then
1501 all the other iterations it has the value of ARG.
1502 For the moment, PEELED_CHREC nodes are not built. */
1504 ev_fn
= chrec_dont_know
;
1506 /* When there are multiple back edges of the loop (which in fact never
1507 happens currently, but nevertheless), merge their evolutions. */
1508 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1513 fprintf (dump_file
, " (evolution_function = ");
1514 print_generic_expr (dump_file
, evolution_function
, 0);
1515 fprintf (dump_file
, "))\n");
1518 return evolution_function
;
1521 /* Given a loop-phi-node, return the initial conditions of the
1522 variable on entry of the loop. When the CCP has propagated
1523 constants into the loop-phi-node, the initial condition is
1524 instantiated, otherwise the initial condition is kept symbolic.
1525 This analyzer does not analyze the evolution outside the current
1526 loop, and leaves this task to the on-demand tree reconstructor. */
1529 analyze_initial_condition (tree loop_phi_node
)
1532 tree init_cond
= chrec_not_analyzed_yet
;
1533 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1537 fprintf (dump_file
, "(analyze_initial_condition \n");
1538 fprintf (dump_file
, " (loop_phi_node = \n");
1539 print_generic_expr (dump_file
, loop_phi_node
, 0);
1540 fprintf (dump_file
, ")\n");
1543 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1545 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1546 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1548 /* When the branch is oriented to the loop's body, it does
1549 not contribute to the initial condition. */
1550 if (flow_bb_inside_loop_p (loop
, bb
))
1553 if (init_cond
== chrec_not_analyzed_yet
)
1559 if (TREE_CODE (branch
) == SSA_NAME
)
1561 init_cond
= chrec_dont_know
;
1565 init_cond
= chrec_merge (init_cond
, branch
);
1568 /* Ooops -- a loop without an entry??? */
1569 if (init_cond
== chrec_not_analyzed_yet
)
1570 init_cond
= chrec_dont_know
;
1572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1574 fprintf (dump_file
, " (init_cond = ");
1575 print_generic_expr (dump_file
, init_cond
, 0);
1576 fprintf (dump_file
, "))\n");
1582 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1585 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1588 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1591 if (phi_loop
!= loop
)
1593 struct loop
*subloop
;
1594 tree evolution_fn
= analyze_scalar_evolution
1595 (phi_loop
, PHI_RESULT (loop_phi_node
));
1597 /* Dive one level deeper. */
1598 subloop
= superloop_at_depth (phi_loop
, loop
->depth
+ 1);
1600 /* Interpret the subloop. */
1601 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1605 /* Otherwise really interpret the loop phi. */
1606 init_cond
= analyze_initial_condition (loop_phi_node
);
1607 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1612 /* This function merges the branches of a condition-phi-node,
1613 contained in the outermost loop, and whose arguments are already
1617 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1620 tree res
= chrec_not_analyzed_yet
;
1622 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1626 if (backedge_phi_arg_p (condition_phi
, i
))
1628 res
= chrec_dont_know
;
1632 branch_chrec
= analyze_scalar_evolution
1633 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1635 res
= chrec_merge (res
, branch_chrec
);
1641 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1642 analyze this node before, follow the definitions until ending
1643 either on an analyzed modify_expr, or on a loop-phi-node. On the
1644 return path, this function propagates evolutions (ala constant copy
1645 propagation). OPND1 is not a GIMPLE expression because we could
1646 analyze the effect of an inner loop: see interpret_loop_phi. */
1649 interpret_rhs_modify_expr (struct loop
*loop
, tree at_stmt
,
1650 tree opnd1
, tree type
)
1652 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1654 if (is_gimple_min_invariant (opnd1
))
1655 return chrec_convert (type
, opnd1
, at_stmt
);
1657 switch (TREE_CODE (opnd1
))
1660 opnd10
= TREE_OPERAND (opnd1
, 0);
1661 opnd11
= TREE_OPERAND (opnd1
, 1);
1662 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1663 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1664 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1665 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1666 res
= chrec_fold_plus (type
, chrec10
, chrec11
);
1670 opnd10
= TREE_OPERAND (opnd1
, 0);
1671 opnd11
= TREE_OPERAND (opnd1
, 1);
1672 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1673 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1674 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1675 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1676 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1680 opnd10
= TREE_OPERAND (opnd1
, 0);
1681 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1682 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1683 res
= chrec_fold_minus (type
, build_int_cst (type
, 0), chrec10
);
1687 opnd10
= TREE_OPERAND (opnd1
, 0);
1688 opnd11
= TREE_OPERAND (opnd1
, 1);
1689 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1690 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1691 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1692 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1693 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1697 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
),
1702 opnd10
= ASSERT_EXPR_VAR (opnd1
);
1703 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd10
),
1709 opnd10
= TREE_OPERAND (opnd1
, 0);
1710 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1711 res
= chrec_convert (type
, chrec10
, at_stmt
);
1715 res
= chrec_dont_know
;
1724 /* This section contains all the entry points:
1725 - number_of_iterations_in_loop,
1726 - analyze_scalar_evolution,
1727 - instantiate_parameters.
1730 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1731 common ancestor of DEF_LOOP and USE_LOOP. */
1734 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1735 struct loop
*def_loop
,
1739 if (def_loop
== wrto_loop
)
1742 def_loop
= superloop_at_depth (def_loop
, wrto_loop
->depth
+ 1);
1743 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1745 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1748 /* Helper recursive function. */
1751 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1753 tree def
, type
= TREE_TYPE (var
);
1755 struct loop
*def_loop
;
1758 return chrec_dont_know
;
1760 if (TREE_CODE (var
) != SSA_NAME
)
1761 return interpret_rhs_modify_expr (loop
, NULL_TREE
, var
, type
);
1763 def
= SSA_NAME_DEF_STMT (var
);
1764 bb
= bb_for_stmt (def
);
1765 def_loop
= bb
? bb
->loop_father
: NULL
;
1768 || !flow_bb_inside_loop_p (loop
, bb
))
1770 /* Keep the symbolic form. */
1775 if (res
!= chrec_not_analyzed_yet
)
1777 if (loop
!= bb
->loop_father
)
1778 res
= compute_scalar_evolution_in_loop
1779 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1784 if (loop
!= def_loop
)
1786 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1787 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1792 switch (TREE_CODE (def
))
1795 res
= interpret_rhs_modify_expr (loop
, def
, TREE_OPERAND (def
, 1), type
);
1799 if (loop_phi_node_p (def
))
1800 res
= interpret_loop_phi (loop
, def
);
1802 res
= interpret_condition_phi (loop
, def
);
1806 res
= chrec_dont_know
;
1812 /* Keep the symbolic form. */
1813 if (res
== chrec_dont_know
)
1816 if (loop
== def_loop
)
1817 set_scalar_evolution (var
, res
);
1822 /* Entry point for the scalar evolution analyzer.
1823 Analyzes and returns the scalar evolution of the ssa_name VAR.
1824 LOOP_NB is the identifier number of the loop in which the variable
1827 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1828 pointer to the statement that uses this variable, in order to
1829 determine the evolution function of the variable, use the following
1832 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1833 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1834 tree chrec_instantiated = instantiate_parameters
1835 (loop_nb, chrec_with_symbols);
1839 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1845 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1846 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1847 fprintf (dump_file
, " (scalar = ");
1848 print_generic_expr (dump_file
, var
, 0);
1849 fprintf (dump_file
, ")\n");
1852 res
= analyze_scalar_evolution_1 (loop
, var
, get_scalar_evolution (var
));
1854 if (TREE_CODE (var
) == SSA_NAME
&& res
== chrec_dont_know
)
1857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1858 fprintf (dump_file
, ")\n");
1863 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1864 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1868 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
1876 ev
= analyze_scalar_evolution (use_loop
, ev
);
1877 ev
= resolve_mixers (use_loop
, ev
);
1879 if (use_loop
== wrto_loop
)
1882 /* If the value of the use changes in the inner loop, we cannot express
1883 its value in the outer loop (we might try to return interval chrec,
1884 but we do not have a user for it anyway) */
1885 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
1887 return chrec_dont_know
;
1889 use_loop
= use_loop
->outer
;
1893 /* Returns instantiated value for VERSION in CACHE. */
1896 get_instantiated_value (htab_t cache
, tree version
)
1898 struct scev_info_str
*info
, pattern
;
1900 pattern
.var
= version
;
1901 info
= htab_find (cache
, &pattern
);
1909 /* Sets instantiated value for VERSION to VAL in CACHE. */
1912 set_instantiated_value (htab_t cache
, tree version
, tree val
)
1914 struct scev_info_str
*info
, pattern
;
1917 pattern
.var
= version
;
1918 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
1923 info
= *slot
= new_scev_info_str (version
);
1927 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1928 with respect to LOOP. CHREC is the chrec to instantiate. If
1929 ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1930 outer loop chrecs is done. CACHE is the cache of already instantiated
1934 instantiate_parameters_1 (struct loop
*loop
, tree chrec
,
1935 bool allow_superloop_chrecs
,
1938 tree res
, op0
, op1
, op2
;
1940 struct loop
*def_loop
;
1942 if (automatically_generated_chrec_p (chrec
)
1943 || is_gimple_min_invariant (chrec
))
1946 switch (TREE_CODE (chrec
))
1949 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
1951 /* A parameter (or loop invariant and we do not want to include
1952 evolutions in outer loops), nothing to do. */
1954 || (!allow_superloop_chrecs
1955 && !flow_bb_inside_loop_p (loop
, def_bb
)))
1958 /* We cache the value of instantiated variable to avoid exponential
1959 time complexity due to reevaluations. We also store the convenient
1960 value in the cache in order to prevent infinite recursion -- we do
1961 not want to instantiate the SSA_NAME if it is in a mixer
1962 structure. This is used for avoiding the instantiation of
1963 recursively defined functions, such as:
1965 | a_2 -> {0, +, 1, +, a_2}_1 */
1967 res
= get_instantiated_value (cache
, chrec
);
1971 /* Store the convenient value for chrec in the structure. If it
1972 is defined outside of the loop, we may just leave it in symbolic
1973 form, otherwise we need to admit that we do not know its behavior
1975 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
1976 set_instantiated_value (cache
, chrec
, res
);
1978 /* To make things even more complicated, instantiate_parameters_1
1979 calls analyze_scalar_evolution that may call # of iterations
1980 analysis that may in turn call instantiate_parameters_1 again.
1981 To prevent the infinite recursion, keep also the bitmap of
1982 ssa names that are being instantiated globally. */
1983 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
1986 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
1988 /* If the analysis yields a parametric chrec, instantiate the
1990 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
1991 res
= analyze_scalar_evolution (def_loop
, chrec
);
1992 if (res
!= chrec_dont_know
)
1993 res
= instantiate_parameters_1 (loop
, res
, allow_superloop_chrecs
,
1995 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
1997 /* Store the correct value to the cache. */
1998 set_instantiated_value (cache
, chrec
, res
);
2001 case POLYNOMIAL_CHREC
:
2002 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2003 allow_superloop_chrecs
, cache
);
2004 if (op0
== chrec_dont_know
)
2005 return chrec_dont_know
;
2007 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2008 allow_superloop_chrecs
, cache
);
2009 if (op1
== chrec_dont_know
)
2010 return chrec_dont_know
;
2012 if (CHREC_LEFT (chrec
) != op0
2013 || CHREC_RIGHT (chrec
) != op1
)
2014 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2018 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2019 allow_superloop_chrecs
, cache
);
2020 if (op0
== chrec_dont_know
)
2021 return chrec_dont_know
;
2023 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2024 allow_superloop_chrecs
, cache
);
2025 if (op1
== chrec_dont_know
)
2026 return chrec_dont_know
;
2028 if (TREE_OPERAND (chrec
, 0) != op0
2029 || TREE_OPERAND (chrec
, 1) != op1
)
2030 chrec
= chrec_fold_plus (TREE_TYPE (chrec
), op0
, op1
);
2034 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2035 allow_superloop_chrecs
, cache
);
2036 if (op0
== chrec_dont_know
)
2037 return chrec_dont_know
;
2039 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2040 allow_superloop_chrecs
, cache
);
2041 if (op1
== chrec_dont_know
)
2042 return chrec_dont_know
;
2044 if (TREE_OPERAND (chrec
, 0) != op0
2045 || TREE_OPERAND (chrec
, 1) != op1
)
2046 chrec
= chrec_fold_minus (TREE_TYPE (chrec
), op0
, op1
);
2050 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2051 allow_superloop_chrecs
, cache
);
2052 if (op0
== chrec_dont_know
)
2053 return chrec_dont_know
;
2055 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2056 allow_superloop_chrecs
, cache
);
2057 if (op1
== chrec_dont_know
)
2058 return chrec_dont_know
;
2060 if (TREE_OPERAND (chrec
, 0) != op0
2061 || TREE_OPERAND (chrec
, 1) != op1
)
2062 chrec
= chrec_fold_multiply (TREE_TYPE (chrec
), op0
, op1
);
2067 case NON_LVALUE_EXPR
:
2068 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2069 allow_superloop_chrecs
, cache
);
2070 if (op0
== chrec_dont_know
)
2071 return chrec_dont_know
;
2073 if (op0
== TREE_OPERAND (chrec
, 0))
2076 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL_TREE
);
2078 case SCEV_NOT_KNOWN
:
2079 return chrec_dont_know
;
2088 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2091 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2092 allow_superloop_chrecs
, cache
);
2093 if (op0
== chrec_dont_know
)
2094 return chrec_dont_know
;
2096 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2097 allow_superloop_chrecs
, cache
);
2098 if (op1
== chrec_dont_know
)
2099 return chrec_dont_know
;
2101 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2102 allow_superloop_chrecs
, cache
);
2103 if (op2
== chrec_dont_know
)
2104 return chrec_dont_know
;
2106 if (op0
== TREE_OPERAND (chrec
, 0)
2107 && op1
== TREE_OPERAND (chrec
, 1)
2108 && op2
== TREE_OPERAND (chrec
, 2))
2111 return fold_build3 (TREE_CODE (chrec
),
2112 TREE_TYPE (chrec
), op0
, op1
, op2
);
2115 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2116 allow_superloop_chrecs
, cache
);
2117 if (op0
== chrec_dont_know
)
2118 return chrec_dont_know
;
2120 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2121 allow_superloop_chrecs
, cache
);
2122 if (op1
== chrec_dont_know
)
2123 return chrec_dont_know
;
2125 if (op0
== TREE_OPERAND (chrec
, 0)
2126 && op1
== TREE_OPERAND (chrec
, 1))
2128 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2131 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2132 allow_superloop_chrecs
, cache
);
2133 if (op0
== chrec_dont_know
)
2134 return chrec_dont_know
;
2135 if (op0
== TREE_OPERAND (chrec
, 0))
2137 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2146 /* Too complicated to handle. */
2147 return chrec_dont_know
;
2150 /* Analyze all the parameters of the chrec that were left under a
2151 symbolic form. LOOP is the loop in which symbolic names have to
2152 be analyzed and instantiated. */
2155 instantiate_parameters (struct loop
*loop
,
2159 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2163 fprintf (dump_file
, "(instantiate_parameters \n");
2164 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2165 fprintf (dump_file
, " (chrec = ");
2166 print_generic_expr (dump_file
, chrec
, 0);
2167 fprintf (dump_file
, ")\n");
2170 res
= instantiate_parameters_1 (loop
, chrec
, true, cache
);
2172 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2174 fprintf (dump_file
, " (res = ");
2175 print_generic_expr (dump_file
, res
, 0);
2176 fprintf (dump_file
, "))\n");
2179 htab_delete (cache
);
2184 /* Similar to instantiate_parameters, but does not introduce the
2185 evolutions in outer loops for LOOP invariants in CHREC. */
2188 resolve_mixers (struct loop
*loop
, tree chrec
)
2190 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2191 tree ret
= instantiate_parameters_1 (loop
, chrec
, false, cache
);
2192 htab_delete (cache
);
2196 /* Entry point for the analysis of the number of iterations pass.
2197 This function tries to safely approximate the number of iterations
2198 the loop will run. When this property is not decidable at compile
2199 time, the result is chrec_dont_know. Otherwise the result is
2200 a scalar or a symbolic parameter.
2202 Example of analysis: suppose that the loop has an exit condition:
2204 "if (b > 49) goto end_loop;"
2206 and that in a previous analysis we have determined that the
2207 variable 'b' has an evolution function:
2209 "EF = {23, +, 5}_2".
2211 When we evaluate the function at the point 5, i.e. the value of the
2212 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2213 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2214 the loop body has been executed 6 times. */
2217 number_of_iterations_in_loop (struct loop
*loop
)
2221 struct tree_niter_desc niter_desc
;
2223 /* Determine whether the number_of_iterations_in_loop has already
2225 res
= loop
->nb_iterations
;
2228 res
= chrec_dont_know
;
2230 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2231 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2233 exit
= loop
->single_exit
;
2237 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2240 type
= TREE_TYPE (niter_desc
.niter
);
2241 if (integer_nonzerop (niter_desc
.may_be_zero
))
2242 res
= build_int_cst (type
, 0);
2243 else if (integer_zerop (niter_desc
.may_be_zero
))
2244 res
= niter_desc
.niter
;
2246 res
= chrec_dont_know
;
2249 return set_nb_iterations_in_loop (loop
, res
);
2252 /* One of the drivers for testing the scalar evolutions analysis.
2253 This function computes the number of iterations for all the loops
2254 from the EXIT_CONDITIONS array. */
2257 number_of_iterations_for_all_loops (VEC(tree
,heap
) **exit_conditions
)
2260 unsigned nb_chrec_dont_know_loops
= 0;
2261 unsigned nb_static_loops
= 0;
2264 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2266 tree res
= number_of_iterations_in_loop (loop_containing_stmt (cond
));
2267 if (chrec_contains_undetermined (res
))
2268 nb_chrec_dont_know_loops
++;
2275 fprintf (dump_file
, "\n(\n");
2276 fprintf (dump_file
, "-----------------------------------------\n");
2277 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2278 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2279 fprintf (dump_file
, "%d\tnb_total_loops\n", current_loops
->num
);
2280 fprintf (dump_file
, "-----------------------------------------\n");
2281 fprintf (dump_file
, ")\n\n");
2283 print_loop_ir (dump_file
);
2289 /* Counters for the stats. */
2295 unsigned nb_affine_multivar
;
2296 unsigned nb_higher_poly
;
2297 unsigned nb_chrec_dont_know
;
2298 unsigned nb_undetermined
;
2301 /* Reset the counters. */
2304 reset_chrecs_counters (struct chrec_stats
*stats
)
2306 stats
->nb_chrecs
= 0;
2307 stats
->nb_affine
= 0;
2308 stats
->nb_affine_multivar
= 0;
2309 stats
->nb_higher_poly
= 0;
2310 stats
->nb_chrec_dont_know
= 0;
2311 stats
->nb_undetermined
= 0;
2314 /* Dump the contents of a CHREC_STATS structure. */
2317 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2319 fprintf (file
, "\n(\n");
2320 fprintf (file
, "-----------------------------------------\n");
2321 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2322 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2323 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2324 stats
->nb_higher_poly
);
2325 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2326 fprintf (file
, "-----------------------------------------\n");
2327 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2328 fprintf (file
, "%d\twith undetermined coefficients\n",
2329 stats
->nb_undetermined
);
2330 fprintf (file
, "-----------------------------------------\n");
2331 fprintf (file
, "%d\tchrecs in the scev database\n",
2332 (int) htab_elements (scalar_evolution_info
));
2333 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2334 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2335 fprintf (file
, "-----------------------------------------\n");
2336 fprintf (file
, ")\n\n");
2339 /* Gather statistics about CHREC. */
2342 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2344 if (dump_file
&& (dump_flags
& TDF_STATS
))
2346 fprintf (dump_file
, "(classify_chrec ");
2347 print_generic_expr (dump_file
, chrec
, 0);
2348 fprintf (dump_file
, "\n");
2353 if (chrec
== NULL_TREE
)
2355 stats
->nb_undetermined
++;
2359 switch (TREE_CODE (chrec
))
2361 case POLYNOMIAL_CHREC
:
2362 if (evolution_function_is_affine_p (chrec
))
2364 if (dump_file
&& (dump_flags
& TDF_STATS
))
2365 fprintf (dump_file
, " affine_univariate\n");
2368 else if (evolution_function_is_affine_multivariate_p (chrec
))
2370 if (dump_file
&& (dump_flags
& TDF_STATS
))
2371 fprintf (dump_file
, " affine_multivariate\n");
2372 stats
->nb_affine_multivar
++;
2376 if (dump_file
&& (dump_flags
& TDF_STATS
))
2377 fprintf (dump_file
, " higher_degree_polynomial\n");
2378 stats
->nb_higher_poly
++;
2387 if (chrec_contains_undetermined (chrec
))
2389 if (dump_file
&& (dump_flags
& TDF_STATS
))
2390 fprintf (dump_file
, " undetermined\n");
2391 stats
->nb_undetermined
++;
2394 if (dump_file
&& (dump_flags
& TDF_STATS
))
2395 fprintf (dump_file
, ")\n");
2398 /* One of the drivers for testing the scalar evolutions analysis.
2399 This function analyzes the scalar evolution of all the scalars
2400 defined as loop phi nodes in one of the loops from the
2401 EXIT_CONDITIONS array.
2403 TODO Optimization: A loop is in canonical form if it contains only
2404 a single scalar loop phi node. All the other scalars that have an
2405 evolution in the loop are rewritten in function of this single
2406 index. This allows the parallelization of the loop. */
2409 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree
,heap
) **exit_conditions
)
2412 struct chrec_stats stats
;
2415 reset_chrecs_counters (&stats
);
2417 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2423 loop
= loop_containing_stmt (cond
);
2426 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2427 if (is_gimple_reg (PHI_RESULT (phi
)))
2429 chrec
= instantiate_parameters
2431 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2433 if (dump_file
&& (dump_flags
& TDF_STATS
))
2434 gather_chrec_stats (chrec
, &stats
);
2438 if (dump_file
&& (dump_flags
& TDF_STATS
))
2439 dump_chrecs_stats (dump_file
, &stats
);
2442 /* Callback for htab_traverse, gathers information on chrecs in the
2446 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2448 struct scev_info_str
*entry
= *slot
;
2450 gather_chrec_stats (entry
->chrec
, stats
);
2455 /* Classify the chrecs of the whole database. */
2458 gather_stats_on_scev_database (void)
2460 struct chrec_stats stats
;
2465 reset_chrecs_counters (&stats
);
2467 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2470 dump_chrecs_stats (dump_file
, &stats
);
2478 initialize_scalar_evolutions_analyzer (void)
2480 /* The elements below are unique. */
2481 if (chrec_dont_know
== NULL_TREE
)
2483 chrec_not_analyzed_yet
= NULL_TREE
;
2484 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2485 chrec_known
= make_node (SCEV_KNOWN
);
2486 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2487 TREE_TYPE (chrec_known
) = void_type_node
;
2491 /* Initialize the analysis of scalar evolutions for LOOPS. */
2494 scev_initialize (struct loops
*loops
)
2497 current_loops
= loops
;
2499 scalar_evolution_info
= htab_create (100, hash_scev_info
,
2500 eq_scev_info
, del_scev_info
);
2501 already_instantiated
= BITMAP_ALLOC (NULL
);
2503 initialize_scalar_evolutions_analyzer ();
2505 for (i
= 1; i
< loops
->num
; i
++)
2506 if (loops
->parray
[i
])
2507 loops
->parray
[i
]->nb_iterations
= NULL_TREE
;
2510 /* Cleans up the information cached by the scalar evolutions analysis. */
2518 if (!scalar_evolution_info
|| !current_loops
)
2521 htab_empty (scalar_evolution_info
);
2522 for (i
= 1; i
< current_loops
->num
; i
++)
2524 loop
= current_loops
->parray
[i
];
2526 loop
->nb_iterations
= NULL_TREE
;
2530 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2531 its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
2532 want STEP to be invariant in LOOP. Otherwise we require it to be an
2533 integer constant. */
2536 simple_iv (struct loop
*loop
, tree stmt
, tree op
, tree
*base
, tree
*step
,
2537 bool allow_nonconstant_step
)
2539 basic_block bb
= bb_for_stmt (stmt
);
2545 type
= TREE_TYPE (op
);
2546 if (TREE_CODE (type
) != INTEGER_TYPE
2547 && TREE_CODE (type
) != POINTER_TYPE
)
2550 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
);
2551 if (chrec_contains_undetermined (ev
))
2554 if (tree_does_not_contain_chrecs (ev
)
2555 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2561 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2562 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2565 *step
= CHREC_RIGHT (ev
);
2566 if (allow_nonconstant_step
)
2568 if (tree_contains_chrecs (*step
, NULL
)
2569 || chrec_contains_symbols_defined_in_loop (*step
, loop
->num
))
2572 else if (TREE_CODE (*step
) != INTEGER_CST
)
2575 *base
= CHREC_LEFT (ev
);
2576 if (tree_contains_chrecs (*base
, NULL
)
2577 || chrec_contains_symbols_defined_in_loop (*base
, loop
->num
))
2583 /* Runs the analysis of scalar evolutions. */
2586 scev_analysis (void)
2588 VEC(tree
,heap
) *exit_conditions
;
2590 exit_conditions
= VEC_alloc (tree
, heap
, 37);
2591 select_loops_exit_conditions (current_loops
, &exit_conditions
);
2593 if (dump_file
&& (dump_flags
& TDF_STATS
))
2594 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2596 number_of_iterations_for_all_loops (&exit_conditions
);
2597 VEC_free (tree
, heap
, exit_conditions
);
2600 /* Finalize the scalar evolution analysis. */
2603 scev_finalize (void)
2605 htab_delete (scalar_evolution_info
);
2606 BITMAP_FREE (already_instantiated
);
2609 /* Replace ssa names for that scev can prove they are constant by the
2610 appropriate constants. Also perform final value replacement in loops,
2611 in case the replacement expressions are cheap.
2613 We only consider SSA names defined by phi nodes; rest is left to the
2614 ordinary constant propagation pass. */
2617 scev_const_prop (void)
2620 tree name
, phi
, next_phi
, type
, ev
;
2621 struct loop
*loop
, *ex_loop
;
2622 bitmap ssa_names_to_remove
= NULL
;
2630 loop
= bb
->loop_father
;
2632 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2634 name
= PHI_RESULT (phi
);
2636 if (!is_gimple_reg (name
))
2639 type
= TREE_TYPE (name
);
2641 if (!POINTER_TYPE_P (type
)
2642 && !INTEGRAL_TYPE_P (type
))
2645 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
2646 if (!is_gimple_min_invariant (ev
)
2647 || !may_propagate_copy (name
, ev
))
2650 /* Replace the uses of the name. */
2651 replace_uses_by (name
, ev
);
2653 if (!ssa_names_to_remove
)
2654 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
2655 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
2659 /* Remove the ssa names that were replaced by constants. We do not remove them
2660 directly in the previous cycle, since this invalidates scev cache. */
2661 if (ssa_names_to_remove
)
2666 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
2668 name
= ssa_name (i
);
2669 phi
= SSA_NAME_DEF_STMT (name
);
2671 gcc_assert (TREE_CODE (phi
) == PHI_NODE
);
2672 remove_phi_node (phi
, NULL
);
2675 BITMAP_FREE (ssa_names_to_remove
);
2679 /* Now the regular final value replacement. */
2680 for (i
= current_loops
->num
- 1; i
> 0; i
--)
2685 loop
= current_loops
->parray
[i
];
2689 /* If we do not know exact number of iterations of the loop, we cannot
2690 replace the final value. */
2691 exit
= loop
->single_exit
;
2693 || number_of_iterations_in_loop (loop
) == chrec_dont_know
)
2695 ex_loop
= exit
->dest
->loop_father
;
2697 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= next_phi
)
2699 next_phi
= PHI_CHAIN (phi
);
2700 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2701 if (!is_gimple_reg (def
)
2702 || expr_invariant_in_loop_p (loop
, def
))
2705 if (!POINTER_TYPE_P (TREE_TYPE (def
))
2706 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
2709 def
= analyze_scalar_evolution_in_loop (ex_loop
, ex_loop
, def
);
2710 if (!tree_does_not_contain_chrecs (def
)
2711 || chrec_contains_symbols_defined_in_loop (def
, loop
->num
))
2714 /* If computing the expression is expensive, let it remain in
2715 loop. TODO -- we should take the cost of computing the expression
2716 in loop into account. */
2717 if (force_expr_to_var_cost (def
) >= target_spill_cost
)
2719 def
= unshare_expr (def
);
2721 if (is_gimple_val (def
))
2724 def
= force_gimple_operand (def
, &stmts
, true,
2725 SSA_NAME_VAR (PHI_RESULT (phi
)));
2726 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, exit
), def
);
2728 compute_phi_arg_on_exit (exit
, stmts
, def
);