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, 59 Temple Place - Suite 330, Boston, MA
25 This pass analyzes the evolution of scalar variables in loop
26 structures. The algorithm is based on the SSA representation,
27 and on the loop hierarchy tree. This algorithm is not based on
28 the notion of versions of a variable, as it was the case for the
29 previous implementations of the scalar evolution algorithm, but
30 it assumes that each defined name is unique.
32 The notation used in this file is called "chains of recurrences",
33 and has been proposed by Eugene Zima, Robert Van Engelen, and
34 others for describing induction variables in programs. For example
35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36 when entering in the loop_1 and has a step 2 in this loop, in other
37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38 this chain of recurrence (or chrec [shrek]) can contain the name of
39 other variables, in which case they are called parametric chrecs.
40 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41 is the value of "a". In most of the cases these parametric chrecs
42 are fully instantiated before their use because symbolic names can
43 hide some difficult cases such as self-references described later
44 (see the Fibonacci example).
46 A short sketch of the algorithm is:
48 Given a scalar variable to be analyzed, follow the SSA edge to
51 - When the definition is a MODIFY_EXPR: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters ({a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2: Illustration of the algorithm on nested loops.
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
158 Example 3: Higher degree polynomials.
172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175 Example 4: Lucas, Fibonacci, or mixers in general.
187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188 following semantics: during the first iteration of the loop_1, the
189 variable contains the value 1, and then it contains the value "c".
190 Note that this syntax is close to the syntax of the loop-phi-node:
191 "a -> (1, c)_1" vs. "a = phi (1, c)".
193 The symbolic chrec representation contains all the semantics of the
194 original code. What is more difficult is to use this information.
196 Example 5: Flip-flops, or exchangers.
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
214 This transformation is not yet implemented.
218 You can find a more detailed description of the algorithm in:
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
221 this is a preliminary report and some of the details of the
222 algorithm have changed. I'm working on a research report that
223 updates the description of the algorithms to reflect the design
224 choices used in this implementation.
226 A set of slides show a high level overview of the algorithm and run
227 an example through the scalar evolution analyzer:
228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230 The slides that I have presented at the GCC Summit'04 are available
231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
236 #include "coretypes.h"
243 /* These RTL headers are needed for basic-block.h. */
245 #include "basic-block.h"
246 #include "diagnostic.h"
247 #include "tree-flow.h"
248 #include "tree-dump.h"
251 #include "tree-chrec.h"
252 #include "tree-scalar-evolution.h"
253 #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
= xmalloc (sizeof (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
= e1
;
320 const struct scev_info_str
*elt2
= 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
);
354 /* Tries to express CHREC in wider type TYPE. */
357 count_ev_in_wider_type (tree type
, tree chrec
)
362 if (!evolution_function_is_affine_p (chrec
))
363 return fold_convert (type
, chrec
);
365 base
= CHREC_LEFT (chrec
);
366 step
= CHREC_RIGHT (chrec
);
367 loop
= current_loops
->parray
[CHREC_VARIABLE (chrec
)];
369 /* TODO -- if we knew the statement at that the conversion occurs,
370 we could pass it to can_count_iv_in_wider_type and get a better
372 step
= can_count_iv_in_wider_type (loop
, type
, base
, step
, NULL_TREE
);
374 return fold_convert (type
, chrec
);
375 base
= chrec_convert (type
, base
);
377 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
381 /* Return true when CHREC contains symbolic names defined in
385 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
387 if (chrec
== NULL_TREE
)
390 if (TREE_INVARIANT (chrec
))
393 if (TREE_CODE (chrec
) == VAR_DECL
394 || TREE_CODE (chrec
) == PARM_DECL
395 || TREE_CODE (chrec
) == FUNCTION_DECL
396 || TREE_CODE (chrec
) == LABEL_DECL
397 || TREE_CODE (chrec
) == RESULT_DECL
398 || TREE_CODE (chrec
) == FIELD_DECL
)
401 if (TREE_CODE (chrec
) == SSA_NAME
)
403 tree def
= SSA_NAME_DEF_STMT (chrec
);
404 struct loop
*def_loop
= loop_containing_stmt (def
);
405 struct loop
*loop
= current_loops
->parray
[loop_nb
];
407 if (def_loop
== NULL
)
410 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
416 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
419 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 2),
424 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 1),
429 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 0),
438 /* Return true when PHI is a loop-phi-node. */
441 loop_phi_node_p (tree phi
)
443 /* The implementation of this function is based on the following
444 property: "all the loop-phi-nodes of a loop are contained in the
445 loop's header basic block". */
447 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
450 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
451 In general, in the case of multivariate evolutions we want to get
452 the evolution in different loops. LOOP specifies the level for
453 which to get the evolution.
457 | for (j = 0; j < 100; j++)
459 | for (k = 0; k < 100; k++)
461 | i = k + j; - Here the value of i is a function of j, k.
463 | ... = i - Here the value of i is a function of j.
465 | ... = i - Here the value of i is a scalar.
471 | i_1 = phi (i_0, i_2)
475 This loop has the same effect as:
476 LOOP_1 has the same effect as:
480 The overall effect of the loop, "i_0 + 20" in the previous example,
481 is obtained by passing in the parameters: LOOP = 1,
482 EVOLUTION_FN = {i_0, +, 2}_1.
486 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
490 if (evolution_fn
== chrec_dont_know
)
491 return chrec_dont_know
;
493 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
495 if (CHREC_VARIABLE (evolution_fn
) >= (unsigned) loop
->num
)
497 struct loop
*inner_loop
=
498 current_loops
->parray
[CHREC_VARIABLE (evolution_fn
)];
499 tree nb_iter
= number_of_iterations_in_loop (inner_loop
);
501 if (nb_iter
== chrec_dont_know
)
502 return chrec_dont_know
;
507 /* Number of iterations is off by one (the ssa name we
508 analyze must be defined before the exit). */
509 nb_iter
= chrec_fold_minus (chrec_type (nb_iter
),
511 build_int_cst_type (chrec_type (nb_iter
), 1));
513 /* evolution_fn is the evolution function in LOOP. Get
514 its value in the nb_iter-th iteration. */
515 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
517 /* Continue the computation until ending on a parent of LOOP. */
518 return compute_overall_effect_of_inner_loop (loop
, res
);
525 /* If the evolution function is an invariant, there is nothing to do. */
526 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
530 return chrec_dont_know
;
533 /* Determine whether the CHREC is always positive/negative. If the expression
534 cannot be statically analyzed, return false, otherwise set the answer into
538 chrec_is_positive (tree chrec
, bool *value
)
545 switch (TREE_CODE (chrec
))
547 case POLYNOMIAL_CHREC
:
548 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
549 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
552 /* FIXME -- overflows. */
553 if (value0
== value1
)
559 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
560 and the proof consists in showing that the sign never
561 changes during the execution of the loop, from 0 to
562 loop->nb_iterations. */
563 if (!evolution_function_is_affine_p (chrec
))
566 nb_iter
= number_of_iterations_in_loop
567 (current_loops
->parray
[CHREC_VARIABLE (chrec
)]);
569 if (chrec_contains_undetermined (nb_iter
))
572 nb_iter
= chrec_fold_minus
573 (chrec_type (nb_iter
), nb_iter
,
574 build_int_cst (chrec_type (nb_iter
), 1));
577 /* TODO -- If the test is after the exit, we may decrease the number of
578 iterations by one. */
580 nb_iter
= chrec_fold_minus
581 (chrec_type (nb_iter
), nb_iter
,
582 build_int_cst (chrec_type (nb_iter
), 1));
585 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
587 if (!chrec_is_positive (end_value
, &value2
))
591 return value0
== value1
;
594 *value
= (tree_int_cst_sgn (chrec
) == 1);
602 /* Associate CHREC to SCALAR. */
605 set_scalar_evolution (tree scalar
, tree chrec
)
609 if (TREE_CODE (scalar
) != SSA_NAME
)
612 scalar_info
= find_var_scev_info (scalar
);
616 if (dump_flags
& TDF_DETAILS
)
618 fprintf (dump_file
, "(set_scalar_evolution \n");
619 fprintf (dump_file
, " (scalar = ");
620 print_generic_expr (dump_file
, scalar
, 0);
621 fprintf (dump_file
, ")\n (scalar_evolution = ");
622 print_generic_expr (dump_file
, chrec
, 0);
623 fprintf (dump_file
, "))\n");
625 if (dump_flags
& TDF_STATS
)
629 *scalar_info
= chrec
;
632 /* Retrieve the chrec associated to SCALAR in the LOOP. */
635 get_scalar_evolution (tree scalar
)
641 if (dump_flags
& TDF_DETAILS
)
643 fprintf (dump_file
, "(get_scalar_evolution \n");
644 fprintf (dump_file
, " (scalar = ");
645 print_generic_expr (dump_file
, scalar
, 0);
646 fprintf (dump_file
, ")\n");
648 if (dump_flags
& TDF_STATS
)
652 switch (TREE_CODE (scalar
))
655 res
= *find_var_scev_info (scalar
);
664 res
= chrec_not_analyzed_yet
;
668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
670 fprintf (dump_file
, " (scalar_evolution = ");
671 print_generic_expr (dump_file
, res
, 0);
672 fprintf (dump_file
, "))\n");
678 /* Helper function for add_to_evolution. Returns the evolution
679 function for an assignment of the form "a = b + c", where "a" and
680 "b" are on the strongly connected component. CHREC_BEFORE is the
681 information that we already have collected up to this point.
682 TO_ADD is the evolution of "c".
684 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
685 evolution the expression TO_ADD, otherwise construct an evolution
686 part for this loop. */
689 add_to_evolution_1 (unsigned loop_nb
,
693 switch (TREE_CODE (chrec_before
))
695 case POLYNOMIAL_CHREC
:
696 if (CHREC_VARIABLE (chrec_before
) <= loop_nb
)
700 tree type
= chrec_type (chrec_before
);
702 /* When there is no evolution part in this loop, build it. */
703 if (CHREC_VARIABLE (chrec_before
) < loop_nb
)
707 right
= build_int_cst (type
, 0);
711 var
= CHREC_VARIABLE (chrec_before
);
712 left
= CHREC_LEFT (chrec_before
);
713 right
= CHREC_RIGHT (chrec_before
);
716 return build_polynomial_chrec
717 (var
, left
, chrec_fold_plus (type
, right
, to_add
));
720 /* Search the evolution in LOOP_NB. */
721 return build_polynomial_chrec
722 (CHREC_VARIABLE (chrec_before
),
723 add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
), to_add
),
724 CHREC_RIGHT (chrec_before
));
727 /* These nodes do not depend on a loop. */
728 if (chrec_before
== chrec_dont_know
)
729 return chrec_dont_know
;
730 return build_polynomial_chrec (loop_nb
, chrec_before
, to_add
);
734 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
737 Description (provided for completeness, for those who read code in
738 a plane, and for my poor 62 bytes brain that would have forgotten
739 all this in the next two or three months):
741 The algorithm of translation of programs from the SSA representation
742 into the chrecs syntax is based on a pattern matching. After having
743 reconstructed the overall tree expression for a loop, there are only
744 two cases that can arise:
746 1. a = loop-phi (init, a + expr)
747 2. a = loop-phi (init, expr)
749 where EXPR is either a scalar constant with respect to the analyzed
750 loop (this is a degree 0 polynomial), or an expression containing
751 other loop-phi definitions (these are higher degree polynomials).
758 | a = phi (init, a + 5)
765 | a = phi (inita, 2 * b + 3)
766 | b = phi (initb, b + 1)
769 For the first case, the semantics of the SSA representation is:
771 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
773 that is, there is a loop index "x" that determines the scalar value
774 of the variable during the loop execution. During the first
775 iteration, the value is that of the initial condition INIT, while
776 during the subsequent iterations, it is the sum of the initial
777 condition with the sum of all the values of EXPR from the initial
778 iteration to the before last considered iteration.
780 For the second case, the semantics of the SSA program is:
782 | a (x) = init, if x = 0;
783 | expr (x - 1), otherwise.
785 The second case corresponds to the PEELED_CHREC, whose syntax is
786 close to the syntax of a loop-phi-node:
788 | phi (init, expr) vs. (init, expr)_x
790 The proof of the translation algorithm for the first case is a
791 proof by structural induction based on the degree of EXPR.
794 When EXPR is a constant with respect to the analyzed loop, or in
795 other words when EXPR is a polynomial of degree 0, the evolution of
796 the variable A in the loop is an affine function with an initial
797 condition INIT, and a step EXPR. In order to show this, we start
798 from the semantics of the SSA representation:
800 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
802 and since "expr (j)" is a constant with respect to "j",
804 f (x) = init + x * expr
806 Finally, based on the semantics of the pure sum chrecs, by
807 identification we get the corresponding chrecs syntax:
809 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
810 f (x) -> {init, +, expr}_x
813 Suppose that EXPR is a polynomial of degree N with respect to the
814 analyzed loop_x for which we have already determined that it is
815 written under the chrecs syntax:
817 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
819 We start from the semantics of the SSA program:
821 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
823 | f (x) = init + \sum_{j = 0}^{x - 1}
824 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
826 | f (x) = init + \sum_{j = 0}^{x - 1}
827 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
829 | f (x) = init + \sum_{k = 0}^{n - 1}
830 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
832 | f (x) = init + \sum_{k = 0}^{n - 1}
833 | (b_k * \binom{x}{k + 1})
835 | f (x) = init + b_0 * \binom{x}{1} + ...
836 | + b_{n-1} * \binom{x}{n}
838 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
839 | + b_{n-1} * \binom{x}{n}
842 And finally from the definition of the chrecs syntax, we identify:
843 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
845 This shows the mechanism that stands behind the add_to_evolution
846 function. An important point is that the use of symbolic
847 parameters avoids the need of an analysis schedule.
854 | a = phi (inita, a + 2 + b)
855 | b = phi (initb, b + 1)
858 When analyzing "a", the algorithm keeps "b" symbolically:
860 | a -> {inita, +, 2 + b}_1
862 Then, after instantiation, the analyzer ends on the evolution:
864 | a -> {inita, +, 2 + initb, +, 1}_1
869 add_to_evolution (unsigned loop_nb
,
874 tree type
= chrec_type (to_add
);
875 tree res
= NULL_TREE
;
877 if (to_add
== NULL_TREE
)
880 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
881 instantiated at this point. */
882 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
883 /* This should not happen. */
884 return chrec_dont_know
;
886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
888 fprintf (dump_file
, "(add_to_evolution \n");
889 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
890 fprintf (dump_file
, " (chrec_before = ");
891 print_generic_expr (dump_file
, chrec_before
, 0);
892 fprintf (dump_file
, ")\n (to_add = ");
893 print_generic_expr (dump_file
, to_add
, 0);
894 fprintf (dump_file
, ")\n");
897 if (code
== MINUS_EXPR
)
898 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
899 ? build_real (type
, dconstm1
)
900 : build_int_cst_type (type
, -1));
902 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
);
904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
906 fprintf (dump_file
, " (res = ");
907 print_generic_expr (dump_file
, res
, 0);
908 fprintf (dump_file
, "))\n");
914 /* Helper function. */
917 set_nb_iterations_in_loop (struct loop
*loop
,
920 res
= chrec_fold_plus (chrec_type (res
), res
,
921 build_int_cst_type (chrec_type (res
), 1));
923 /* FIXME HWI: However we want to store one iteration less than the
924 count of the loop in order to be compatible with the other
925 nb_iter computations in loop-iv. This also allows the
926 representation of nb_iters that are equal to MAX_INT. */
927 if ((TREE_CODE (res
) == INTEGER_CST
&& TREE_INT_CST_LOW (res
) == 0)
928 || TREE_OVERFLOW (res
))
929 res
= chrec_dont_know
;
931 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
933 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
934 print_generic_expr (dump_file
, res
, 0);
935 fprintf (dump_file
, "))\n");
938 loop
->nb_iterations
= res
;
944 /* This section selects the loops that will be good candidates for the
945 scalar evolution analysis. For the moment, greedily select all the
946 loop nests we could analyze. */
948 /* Return true when it is possible to analyze the condition expression
952 analyzable_condition (tree expr
)
956 if (TREE_CODE (expr
) != COND_EXPR
)
959 condition
= TREE_OPERAND (expr
, 0);
961 switch (TREE_CODE (condition
))
981 /* For a loop with a single exit edge, return the COND_EXPR that
982 guards the exit edge. If the expression is too difficult to
983 analyze, then give up. */
986 get_loop_exit_condition (struct loop
*loop
)
988 tree res
= NULL_TREE
;
989 edge exit_edge
= loop
->single_exit
;
992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
993 fprintf (dump_file
, "(get_loop_exit_condition \n ");
999 expr
= last_stmt (exit_edge
->src
);
1000 if (analyzable_condition (expr
))
1004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1006 print_generic_expr (dump_file
, res
, 0);
1007 fprintf (dump_file
, ")\n");
1013 /* Recursively determine and enqueue the exit conditions for a loop. */
1016 get_exit_conditions_rec (struct loop
*loop
,
1017 varray_type
*exit_conditions
)
1022 /* Recurse on the inner loops, then on the next (sibling) loops. */
1023 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
1024 get_exit_conditions_rec (loop
->next
, exit_conditions
);
1026 if (loop
->single_exit
)
1028 tree loop_condition
= get_loop_exit_condition (loop
);
1031 VARRAY_PUSH_TREE (*exit_conditions
, loop_condition
);
1035 /* Select the candidate loop nests for the analysis. This function
1036 initializes the EXIT_CONDITIONS array. */
1039 select_loops_exit_conditions (struct loops
*loops
,
1040 varray_type
*exit_conditions
)
1042 struct loop
*function_body
= loops
->parray
[0];
1044 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
1048 /* Depth first search algorithm. */
1050 static bool follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*);
1052 /* Follow the ssa edge into the right hand side RHS of an assignment.
1053 Return true if the strongly connected component has been found. */
1056 follow_ssa_edge_in_rhs (struct loop
*loop
,
1059 tree
*evolution_of_loop
)
1063 tree type_rhs
= TREE_TYPE (rhs
);
1065 /* The RHS is one of the following cases:
1070 - other cases are not yet handled.
1072 switch (TREE_CODE (rhs
))
1075 /* This assignment is under the form "a_1 = (cast) rhs. */
1076 res
= follow_ssa_edge_in_rhs (loop
, TREE_OPERAND (rhs
, 0), halting_phi
,
1078 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
), *evolution_of_loop
);
1082 /* This assignment is under the form "a_1 = 7". */
1087 /* This assignment is under the form: "a_1 = b_2". */
1088 res
= follow_ssa_edge
1089 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
);
1093 /* This case is under the form "rhs0 + rhs1". */
1094 rhs0
= TREE_OPERAND (rhs
, 0);
1095 rhs1
= TREE_OPERAND (rhs
, 1);
1096 STRIP_TYPE_NOPS (rhs0
);
1097 STRIP_TYPE_NOPS (rhs1
);
1099 if (TREE_CODE (rhs0
) == SSA_NAME
)
1101 if (TREE_CODE (rhs1
) == SSA_NAME
)
1103 /* Match an assignment under the form:
1105 res
= follow_ssa_edge
1106 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1110 *evolution_of_loop
= add_to_evolution
1112 chrec_convert (type_rhs
, *evolution_of_loop
),
1117 res
= follow_ssa_edge
1118 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1122 *evolution_of_loop
= add_to_evolution
1124 chrec_convert (type_rhs
, *evolution_of_loop
),
1131 /* Match an assignment under the form:
1133 res
= follow_ssa_edge
1134 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1137 *evolution_of_loop
= add_to_evolution
1138 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
),
1143 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1145 /* Match an assignment under the form:
1147 res
= follow_ssa_edge
1148 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1151 *evolution_of_loop
= add_to_evolution
1152 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
),
1157 /* Otherwise, match an assignment under the form:
1159 /* And there is nothing to do. */
1165 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1166 rhs0
= TREE_OPERAND (rhs
, 0);
1167 rhs1
= TREE_OPERAND (rhs
, 1);
1168 STRIP_TYPE_NOPS (rhs0
);
1169 STRIP_TYPE_NOPS (rhs1
);
1171 if (TREE_CODE (rhs0
) == SSA_NAME
)
1173 /* Match an assignment under the form:
1175 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1178 *evolution_of_loop
= add_to_evolution
1179 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
),
1183 /* Otherwise, match an assignment under the form:
1185 /* And there is nothing to do. */
1191 /* This case is under the form "opnd0 = rhs0 * rhs1". */
1192 rhs0
= TREE_OPERAND (rhs
, 0);
1193 rhs1
= TREE_OPERAND (rhs
, 1);
1194 STRIP_TYPE_NOPS (rhs0
);
1195 STRIP_TYPE_NOPS (rhs1
);
1197 if (TREE_CODE (rhs0
) == SSA_NAME
)
1199 if (TREE_CODE (rhs1
) == SSA_NAME
)
1201 /* Match an assignment under the form:
1203 res
= follow_ssa_edge
1204 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1208 *evolution_of_loop
= chrec_dont_know
;
1212 res
= follow_ssa_edge
1213 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1217 *evolution_of_loop
= chrec_dont_know
;
1223 /* Match an assignment under the form:
1225 res
= follow_ssa_edge
1226 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1229 *evolution_of_loop
= chrec_dont_know
;
1233 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1235 /* Match an assignment under the form:
1237 res
= follow_ssa_edge
1238 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1241 *evolution_of_loop
= chrec_dont_know
;
1245 /* Otherwise, match an assignment under the form:
1247 /* And there is nothing to do. */
1260 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1263 backedge_phi_arg_p (tree phi
, int i
)
1265 edge e
= PHI_ARG_EDGE (phi
, i
);
1267 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1268 about updating it anywhere, and this should work as well most of the
1270 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1276 /* Helper function for one branch of the condition-phi-node. Return
1277 true if the strongly connected component has been found following
1281 follow_ssa_edge_in_condition_phi_branch (int i
,
1285 tree
*evolution_of_branch
,
1288 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1289 *evolution_of_branch
= chrec_dont_know
;
1291 /* Do not follow back edges (they must belong to an irreducible loop, which
1292 we really do not want to worry about). */
1293 if (backedge_phi_arg_p (condition_phi
, i
))
1296 if (TREE_CODE (branch
) == SSA_NAME
)
1298 *evolution_of_branch
= init_cond
;
1299 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1300 evolution_of_branch
);
1303 /* This case occurs when one of the condition branches sets
1304 the variable to a constant: i.e. a phi-node like
1305 "a_2 = PHI <a_7(5), 2(6)>;".
1307 FIXME: This case have to be refined correctly:
1308 in some cases it is possible to say something better than
1309 chrec_dont_know, for example using a wrap-around notation. */
1313 /* This function merges the branches of a condition-phi-node in a
1317 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1320 tree
*evolution_of_loop
)
1323 tree init
= *evolution_of_loop
;
1324 tree evolution_of_branch
;
1326 if (!follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1328 &evolution_of_branch
,
1331 *evolution_of_loop
= evolution_of_branch
;
1333 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1335 /* Quickly give up when the evolution of one of the branches is
1337 if (*evolution_of_loop
== chrec_dont_know
)
1340 if (!follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1342 &evolution_of_branch
,
1346 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1347 evolution_of_branch
);
1353 /* Follow an SSA edge in an inner loop. It computes the overall
1354 effect of the loop, and following the symbolic initial conditions,
1355 it follows the edges in the parent loop. The inner loop is
1356 considered as a single statement. */
1359 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1362 tree
*evolution_of_loop
)
1364 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1365 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1367 /* Sometimes, the inner loop is too difficult to analyze, and the
1368 result of the analysis is a symbolic parameter. */
1369 if (ev
== PHI_RESULT (loop_phi_node
))
1374 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1376 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1379 /* Follow the edges that exit the inner loop. */
1380 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1381 if (!flow_bb_inside_loop_p (loop
, bb
))
1382 res
= res
|| follow_ssa_edge_in_rhs (outer_loop
, arg
, halting_phi
,
1386 /* If the path crosses this loop-phi, give up. */
1388 *evolution_of_loop
= chrec_dont_know
;
1393 /* Otherwise, compute the overall effect of the inner loop. */
1394 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1395 return follow_ssa_edge_in_rhs (outer_loop
, ev
, halting_phi
,
1399 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1400 path that is analyzed on the return walk. */
1403 follow_ssa_edge (struct loop
*loop
,
1406 tree
*evolution_of_loop
)
1408 struct loop
*def_loop
;
1410 if (TREE_CODE (def
) == NOP_EXPR
)
1413 def_loop
= loop_containing_stmt (def
);
1415 switch (TREE_CODE (def
))
1418 if (!loop_phi_node_p (def
))
1419 /* DEF is a condition-phi-node. Follow the branches, and
1420 record their evolutions. Finally, merge the collected
1421 information and set the approximation to the main
1423 return follow_ssa_edge_in_condition_phi
1424 (loop
, def
, halting_phi
, evolution_of_loop
);
1426 /* When the analyzed phi is the halting_phi, the
1427 depth-first search is over: we have found a path from
1428 the halting_phi to itself in the loop. */
1429 if (def
== halting_phi
)
1432 /* Otherwise, the evolution of the HALTING_PHI depends
1433 on the evolution of another loop-phi-node, i.e. the
1434 evolution function is a higher degree polynomial. */
1435 if (def_loop
== loop
)
1439 if (flow_loop_nested_p (loop
, def_loop
))
1440 return follow_ssa_edge_inner_loop_phi
1441 (loop
, def
, halting_phi
, evolution_of_loop
);
1447 return follow_ssa_edge_in_rhs (loop
,
1448 TREE_OPERAND (def
, 1),
1453 /* At this level of abstraction, the program is just a set
1454 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1455 other node to be handled. */
1462 /* Given a LOOP_PHI_NODE, this function determines the evolution
1463 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1466 analyze_evolution_in_loop (tree loop_phi_node
,
1470 tree evolution_function
= chrec_not_analyzed_yet
;
1471 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1476 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1477 fprintf (dump_file
, " (loop_phi_node = ");
1478 print_generic_expr (dump_file
, loop_phi_node
, 0);
1479 fprintf (dump_file
, ")\n");
1482 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1484 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1485 tree ssa_chain
, ev_fn
;
1488 /* Select the edges that enter the loop body. */
1489 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1490 if (!flow_bb_inside_loop_p (loop
, bb
))
1493 if (TREE_CODE (arg
) == SSA_NAME
)
1495 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1497 /* Pass in the initial condition to the follow edge function. */
1499 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
);
1504 /* When it is impossible to go back on the same
1505 loop_phi_node by following the ssa edges, the
1506 evolution is represented by a peeled chrec, i.e. the
1507 first iteration, EV_FN has the value INIT_COND, then
1508 all the other iterations it has the value of ARG.
1509 For the moment, PEELED_CHREC nodes are not built. */
1511 ev_fn
= chrec_dont_know
;
1513 /* When there are multiple back edges of the loop (which in fact never
1514 happens currently, but nevertheless), merge their evolutions. */
1515 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1520 fprintf (dump_file
, " (evolution_function = ");
1521 print_generic_expr (dump_file
, evolution_function
, 0);
1522 fprintf (dump_file
, "))\n");
1525 return evolution_function
;
1528 /* Given a loop-phi-node, return the initial conditions of the
1529 variable on entry of the loop. When the CCP has propagated
1530 constants into the loop-phi-node, the initial condition is
1531 instantiated, otherwise the initial condition is kept symbolic.
1532 This analyzer does not analyze the evolution outside the current
1533 loop, and leaves this task to the on-demand tree reconstructor. */
1536 analyze_initial_condition (tree loop_phi_node
)
1539 tree init_cond
= chrec_not_analyzed_yet
;
1540 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1544 fprintf (dump_file
, "(analyze_initial_condition \n");
1545 fprintf (dump_file
, " (loop_phi_node = \n");
1546 print_generic_expr (dump_file
, loop_phi_node
, 0);
1547 fprintf (dump_file
, ")\n");
1550 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1552 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1553 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1555 /* When the branch is oriented to the loop's body, it does
1556 not contribute to the initial condition. */
1557 if (flow_bb_inside_loop_p (loop
, bb
))
1560 if (init_cond
== chrec_not_analyzed_yet
)
1566 if (TREE_CODE (branch
) == SSA_NAME
)
1568 init_cond
= chrec_dont_know
;
1572 init_cond
= chrec_merge (init_cond
, branch
);
1575 /* Ooops -- a loop without an entry??? */
1576 if (init_cond
== chrec_not_analyzed_yet
)
1577 init_cond
= chrec_dont_know
;
1579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1581 fprintf (dump_file
, " (init_cond = ");
1582 print_generic_expr (dump_file
, init_cond
, 0);
1583 fprintf (dump_file
, "))\n");
1589 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1592 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1595 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1598 if (phi_loop
!= loop
)
1600 struct loop
*subloop
;
1601 tree evolution_fn
= analyze_scalar_evolution
1602 (phi_loop
, PHI_RESULT (loop_phi_node
));
1604 /* Dive one level deeper. */
1605 subloop
= superloop_at_depth (phi_loop
, loop
->depth
+ 1);
1607 /* Interpret the subloop. */
1608 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1612 /* Otherwise really interpret the loop phi. */
1613 init_cond
= analyze_initial_condition (loop_phi_node
);
1614 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1619 /* This function merges the branches of a condition-phi-node,
1620 contained in the outermost loop, and whose arguments are already
1624 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1627 tree res
= chrec_not_analyzed_yet
;
1629 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1633 if (backedge_phi_arg_p (condition_phi
, i
))
1635 res
= chrec_dont_know
;
1639 branch_chrec
= analyze_scalar_evolution
1640 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1642 res
= chrec_merge (res
, branch_chrec
);
1648 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1649 analyzed this node before, follow the definitions until ending
1650 either on an analyzed modify_expr, or on a loop-phi-node. On the
1651 return path, this function propagates evolutions (ala constant copy
1652 propagation). OPND1 is not a GIMPLE expression because we could
1653 analyze the effect of an inner loop: see interpret_loop_phi. */
1656 interpret_rhs_modify_expr (struct loop
*loop
,
1657 tree opnd1
, tree type
)
1659 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1661 if (is_gimple_min_invariant (opnd1
))
1662 return chrec_convert (type
, opnd1
);
1664 switch (TREE_CODE (opnd1
))
1667 opnd10
= TREE_OPERAND (opnd1
, 0);
1668 opnd11
= TREE_OPERAND (opnd1
, 1);
1669 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1670 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1671 chrec10
= chrec_convert (type
, chrec10
);
1672 chrec11
= chrec_convert (type
, chrec11
);
1673 res
= chrec_fold_plus (type
, chrec10
, chrec11
);
1677 opnd10
= TREE_OPERAND (opnd1
, 0);
1678 opnd11
= TREE_OPERAND (opnd1
, 1);
1679 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1680 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1681 chrec10
= chrec_convert (type
, chrec10
);
1682 chrec11
= chrec_convert (type
, chrec11
);
1683 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1687 opnd10
= TREE_OPERAND (opnd1
, 0);
1688 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1689 chrec10
= chrec_convert (type
, chrec10
);
1690 res
= chrec_fold_minus (type
, build_int_cst (type
, 0), chrec10
);
1694 opnd10
= TREE_OPERAND (opnd1
, 0);
1695 opnd11
= TREE_OPERAND (opnd1
, 1);
1696 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1697 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1698 chrec10
= chrec_convert (type
, chrec10
);
1699 chrec11
= chrec_convert (type
, chrec11
);
1700 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1704 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
));
1709 opnd10
= TREE_OPERAND (opnd1
, 0);
1710 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1711 res
= chrec_convert (type
, chrec10
);
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
, 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
, 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 (chrec
== NULL_TREE
1943 || automatically_generated_chrec_p (chrec
))
1946 if (is_gimple_min_invariant (chrec
))
1949 switch (TREE_CODE (chrec
))
1952 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
1954 /* A parameter (or loop invariant and we do not want to include
1955 evolutions in outer loops), nothing to do. */
1957 || (!allow_superloop_chrecs
1958 && !flow_bb_inside_loop_p (loop
, def_bb
)))
1961 /* We cache the value of instantiated variable to avoid exponential
1962 time complexity due to reevaluations. We also store the convenient
1963 value in the cache in order to prevent infinite recursion -- we do
1964 not want to instantiate the SSA_NAME if it is in a mixer
1965 structure. This is used for avoiding the instantiation of
1966 recursively defined functions, such as:
1968 | a_2 -> {0, +, 1, +, a_2}_1 */
1970 res
= get_instantiated_value (cache
, chrec
);
1974 /* Store the convenient value for chrec in the structure. If it
1975 is defined outside of the loop, we may just leave it in symbolic
1976 form, otherwise we need to admit that we do not know its behavior
1978 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
1979 set_instantiated_value (cache
, chrec
, res
);
1981 /* To make things even more complicated, instantiate_parameters_1
1982 calls analyze_scalar_evolution that may call # of iterations
1983 analysis that may in turn call instantiate_parameters_1 again.
1984 To prevent the infinite recursion, keep also the bitmap of
1985 ssa names that are being instantiated globally. */
1986 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
1989 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
1991 /* If the analysis yields a parametric chrec, instantiate the
1993 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
1994 res
= analyze_scalar_evolution (def_loop
, chrec
);
1995 if (res
!= chrec_dont_know
)
1996 res
= instantiate_parameters_1 (loop
, res
, allow_superloop_chrecs
,
1998 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2000 /* Store the correct value to the cache. */
2001 set_instantiated_value (cache
, chrec
, res
);
2004 case POLYNOMIAL_CHREC
:
2005 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2006 allow_superloop_chrecs
, cache
);
2007 if (op0
== chrec_dont_know
)
2008 return chrec_dont_know
;
2010 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2011 allow_superloop_chrecs
, cache
);
2012 if (op1
== chrec_dont_know
)
2013 return chrec_dont_know
;
2015 if (CHREC_LEFT (chrec
) != op0
2016 || CHREC_RIGHT (chrec
) != op1
)
2017 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2021 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2022 allow_superloop_chrecs
, cache
);
2023 if (op0
== chrec_dont_know
)
2024 return chrec_dont_know
;
2026 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2027 allow_superloop_chrecs
, cache
);
2028 if (op1
== chrec_dont_know
)
2029 return chrec_dont_know
;
2031 if (TREE_OPERAND (chrec
, 0) != op0
2032 || TREE_OPERAND (chrec
, 1) != op1
)
2033 chrec
= chrec_fold_plus (TREE_TYPE (chrec
), op0
, op1
);
2037 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2038 allow_superloop_chrecs
, cache
);
2039 if (op0
== chrec_dont_know
)
2040 return chrec_dont_know
;
2042 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2043 allow_superloop_chrecs
, cache
);
2044 if (op1
== chrec_dont_know
)
2045 return chrec_dont_know
;
2047 if (TREE_OPERAND (chrec
, 0) != op0
2048 || TREE_OPERAND (chrec
, 1) != op1
)
2049 chrec
= chrec_fold_minus (TREE_TYPE (chrec
), op0
, op1
);
2053 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2054 allow_superloop_chrecs
, cache
);
2055 if (op0
== chrec_dont_know
)
2056 return chrec_dont_know
;
2058 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2059 allow_superloop_chrecs
, cache
);
2060 if (op1
== chrec_dont_know
)
2061 return chrec_dont_know
;
2063 if (TREE_OPERAND (chrec
, 0) != op0
2064 || TREE_OPERAND (chrec
, 1) != op1
)
2065 chrec
= chrec_fold_multiply (TREE_TYPE (chrec
), op0
, op1
);
2070 case NON_LVALUE_EXPR
:
2071 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2072 allow_superloop_chrecs
, cache
);
2073 if (op0
== chrec_dont_know
)
2074 return chrec_dont_know
;
2076 if (op0
== TREE_OPERAND (chrec
, 0))
2079 return chrec_convert (TREE_TYPE (chrec
), op0
);
2081 case SCEV_NOT_KNOWN
:
2082 return chrec_dont_know
;
2091 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2094 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2095 allow_superloop_chrecs
, cache
);
2096 if (op0
== chrec_dont_know
)
2097 return chrec_dont_know
;
2099 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2100 allow_superloop_chrecs
, cache
);
2101 if (op1
== chrec_dont_know
)
2102 return chrec_dont_know
;
2104 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2105 allow_superloop_chrecs
, cache
);
2106 if (op2
== chrec_dont_know
)
2107 return chrec_dont_know
;
2109 if (op0
== TREE_OPERAND (chrec
, 0)
2110 && op1
== TREE_OPERAND (chrec
, 1)
2111 && op2
== TREE_OPERAND (chrec
, 2))
2114 return fold (build (TREE_CODE (chrec
),
2115 TREE_TYPE (chrec
), op0
, op1
, op2
));
2118 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2119 allow_superloop_chrecs
, cache
);
2120 if (op0
== chrec_dont_know
)
2121 return chrec_dont_know
;
2123 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2124 allow_superloop_chrecs
, cache
);
2125 if (op1
== chrec_dont_know
)
2126 return chrec_dont_know
;
2128 if (op0
== TREE_OPERAND (chrec
, 0)
2129 && op1
== TREE_OPERAND (chrec
, 1))
2131 return fold (build (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
));
2134 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2135 allow_superloop_chrecs
, cache
);
2136 if (op0
== chrec_dont_know
)
2137 return chrec_dont_know
;
2138 if (op0
== TREE_OPERAND (chrec
, 0))
2140 return fold (build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
));
2149 /* Too complicated to handle. */
2150 return chrec_dont_know
;
2153 /* Analyze all the parameters of the chrec that were left under a
2154 symbolic form. LOOP is the loop in which symbolic names have to
2155 be analyzed and instantiated. */
2158 instantiate_parameters (struct loop
*loop
,
2162 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2166 fprintf (dump_file
, "(instantiate_parameters \n");
2167 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2168 fprintf (dump_file
, " (chrec = ");
2169 print_generic_expr (dump_file
, chrec
, 0);
2170 fprintf (dump_file
, ")\n");
2173 res
= instantiate_parameters_1 (loop
, chrec
, true, cache
);
2175 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2177 fprintf (dump_file
, " (res = ");
2178 print_generic_expr (dump_file
, res
, 0);
2179 fprintf (dump_file
, "))\n");
2182 htab_delete (cache
);
2187 /* Similar to instantiate_parameters, but does not introduce the
2188 evolutions in outer loops for LOOP invariants in CHREC. */
2191 resolve_mixers (struct loop
*loop
, tree chrec
)
2193 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2194 tree ret
= instantiate_parameters_1 (loop
, chrec
, false, cache
);
2195 htab_delete (cache
);
2199 /* Entry point for the analysis of the number of iterations pass.
2200 This function tries to safely approximate the number of iterations
2201 the loop will run. When this property is not decidable at compile
2202 time, the result is chrec_dont_know. Otherwise the result is
2203 a scalar or a symbolic parameter.
2205 Example of analysis: suppose that the loop has an exit condition:
2207 "if (b > 49) goto end_loop;"
2209 and that in a previous analysis we have determined that the
2210 variable 'b' has an evolution function:
2212 "EF = {23, +, 5}_2".
2214 When we evaluate the function at the point 5, i.e. the value of the
2215 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2216 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2217 the loop body has been executed 6 times. */
2220 number_of_iterations_in_loop (struct loop
*loop
)
2224 struct tree_niter_desc niter_desc
;
2226 /* Determine whether the number_of_iterations_in_loop has already
2228 res
= loop
->nb_iterations
;
2231 res
= chrec_dont_know
;
2233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2234 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2236 exit
= loop
->single_exit
;
2240 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
))
2243 type
= TREE_TYPE (niter_desc
.niter
);
2244 if (integer_nonzerop (niter_desc
.may_be_zero
))
2245 res
= build_int_cst (type
, 0);
2246 else if (integer_zerop (niter_desc
.may_be_zero
))
2247 res
= niter_desc
.niter
;
2249 res
= chrec_dont_know
;
2252 return set_nb_iterations_in_loop (loop
, res
);
2255 /* One of the drivers for testing the scalar evolutions analysis.
2256 This function computes the number of iterations for all the loops
2257 from the EXIT_CONDITIONS array. */
2260 number_of_iterations_for_all_loops (varray_type exit_conditions
)
2263 unsigned nb_chrec_dont_know_loops
= 0;
2264 unsigned nb_static_loops
= 0;
2266 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (exit_conditions
); i
++)
2268 tree res
= number_of_iterations_in_loop
2269 (loop_containing_stmt (VARRAY_TREE (exit_conditions
, i
)));
2270 if (chrec_contains_undetermined (res
))
2271 nb_chrec_dont_know_loops
++;
2278 fprintf (dump_file
, "\n(\n");
2279 fprintf (dump_file
, "-----------------------------------------\n");
2280 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2281 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2282 fprintf (dump_file
, "%d\tnb_total_loops\n", current_loops
->num
);
2283 fprintf (dump_file
, "-----------------------------------------\n");
2284 fprintf (dump_file
, ")\n\n");
2286 print_loop_ir (dump_file
);
2292 /* Counters for the stats. */
2298 unsigned nb_affine_multivar
;
2299 unsigned nb_higher_poly
;
2300 unsigned nb_chrec_dont_know
;
2301 unsigned nb_undetermined
;
2304 /* Reset the counters. */
2307 reset_chrecs_counters (struct chrec_stats
*stats
)
2309 stats
->nb_chrecs
= 0;
2310 stats
->nb_affine
= 0;
2311 stats
->nb_affine_multivar
= 0;
2312 stats
->nb_higher_poly
= 0;
2313 stats
->nb_chrec_dont_know
= 0;
2314 stats
->nb_undetermined
= 0;
2317 /* Dump the contents of a CHREC_STATS structure. */
2320 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2322 fprintf (file
, "\n(\n");
2323 fprintf (file
, "-----------------------------------------\n");
2324 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2325 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2326 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2327 stats
->nb_higher_poly
);
2328 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2329 fprintf (file
, "-----------------------------------------\n");
2330 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2331 fprintf (file
, "%d\twith undetermined coefficients\n",
2332 stats
->nb_undetermined
);
2333 fprintf (file
, "-----------------------------------------\n");
2334 fprintf (file
, "%d\tchrecs in the scev database\n",
2335 (int) htab_elements (scalar_evolution_info
));
2336 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2337 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2338 fprintf (file
, "-----------------------------------------\n");
2339 fprintf (file
, ")\n\n");
2342 /* Gather statistics about CHREC. */
2345 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2347 if (dump_file
&& (dump_flags
& TDF_STATS
))
2349 fprintf (dump_file
, "(classify_chrec ");
2350 print_generic_expr (dump_file
, chrec
, 0);
2351 fprintf (dump_file
, "\n");
2356 if (chrec
== NULL_TREE
)
2358 stats
->nb_undetermined
++;
2362 switch (TREE_CODE (chrec
))
2364 case POLYNOMIAL_CHREC
:
2365 if (evolution_function_is_affine_p (chrec
))
2367 if (dump_file
&& (dump_flags
& TDF_STATS
))
2368 fprintf (dump_file
, " affine_univariate\n");
2371 else if (evolution_function_is_affine_multivariate_p (chrec
))
2373 if (dump_file
&& (dump_flags
& TDF_STATS
))
2374 fprintf (dump_file
, " affine_multivariate\n");
2375 stats
->nb_affine_multivar
++;
2379 if (dump_file
&& (dump_flags
& TDF_STATS
))
2380 fprintf (dump_file
, " higher_degree_polynomial\n");
2381 stats
->nb_higher_poly
++;
2390 if (chrec_contains_undetermined (chrec
))
2392 if (dump_file
&& (dump_flags
& TDF_STATS
))
2393 fprintf (dump_file
, " undetermined\n");
2394 stats
->nb_undetermined
++;
2397 if (dump_file
&& (dump_flags
& TDF_STATS
))
2398 fprintf (dump_file
, ")\n");
2401 /* One of the drivers for testing the scalar evolutions analysis.
2402 This function analyzes the scalar evolution of all the scalars
2403 defined as loop phi nodes in one of the loops from the
2404 EXIT_CONDITIONS array.
2406 TODO Optimization: A loop is in canonical form if it contains only
2407 a single scalar loop phi node. All the other scalars that have an
2408 evolution in the loop are rewritten in function of this single
2409 index. This allows the parallelization of the loop. */
2412 analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions
)
2415 struct chrec_stats stats
;
2417 reset_chrecs_counters (&stats
);
2419 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (exit_conditions
); i
++)
2425 loop
= loop_containing_stmt (VARRAY_TREE (exit_conditions
, i
));
2428 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2429 if (is_gimple_reg (PHI_RESULT (phi
)))
2431 chrec
= instantiate_parameters
2433 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2435 if (dump_file
&& (dump_flags
& TDF_STATS
))
2436 gather_chrec_stats (chrec
, &stats
);
2440 if (dump_file
&& (dump_flags
& TDF_STATS
))
2441 dump_chrecs_stats (dump_file
, &stats
);
2444 /* Callback for htab_traverse, gathers information on chrecs in the
2448 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2450 struct scev_info_str
*entry
= *slot
;
2452 gather_chrec_stats (entry
->chrec
, stats
);
2457 /* Classify the chrecs of the whole database. */
2460 gather_stats_on_scev_database (void)
2462 struct chrec_stats stats
;
2467 reset_chrecs_counters (&stats
);
2469 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2472 dump_chrecs_stats (dump_file
, &stats
);
2480 initialize_scalar_evolutions_analyzer (void)
2482 /* The elements below are unique. */
2483 if (chrec_dont_know
== NULL_TREE
)
2485 chrec_not_analyzed_yet
= NULL_TREE
;
2486 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2487 chrec_known
= make_node (SCEV_KNOWN
);
2488 TREE_TYPE (chrec_dont_know
) = NULL_TREE
;
2489 TREE_TYPE (chrec_known
) = NULL_TREE
;
2493 /* Initialize the analysis of scalar evolutions for LOOPS. */
2496 scev_initialize (struct loops
*loops
)
2499 current_loops
= loops
;
2501 scalar_evolution_info
= htab_create (100, hash_scev_info
,
2502 eq_scev_info
, del_scev_info
);
2503 already_instantiated
= BITMAP_ALLOC (NULL
);
2505 initialize_scalar_evolutions_analyzer ();
2507 for (i
= 1; i
< loops
->num
; i
++)
2508 if (loops
->parray
[i
])
2509 loops
->parray
[i
]->nb_iterations
= NULL_TREE
;
2512 /* Cleans up the information cached by the scalar evolutions analysis. */
2520 if (!scalar_evolution_info
|| !current_loops
)
2523 htab_empty (scalar_evolution_info
);
2524 for (i
= 1; i
< current_loops
->num
; i
++)
2526 loop
= current_loops
->parray
[i
];
2528 loop
->nb_iterations
= NULL_TREE
;
2532 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2533 its BASE and STEP if possible. */
2536 simple_iv (struct loop
*loop
, tree stmt
, tree op
, tree
*base
, tree
*step
)
2538 basic_block bb
= bb_for_stmt (stmt
);
2544 type
= TREE_TYPE (op
);
2545 if (TREE_CODE (type
) != INTEGER_TYPE
2546 && TREE_CODE (type
) != POINTER_TYPE
)
2549 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
);
2550 if (chrec_contains_undetermined (ev
))
2553 if (tree_does_not_contain_chrecs (ev
)
2554 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2560 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2561 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2564 *step
= CHREC_RIGHT (ev
);
2565 if (TREE_CODE (*step
) != INTEGER_CST
)
2567 *base
= CHREC_LEFT (ev
);
2568 if (tree_contains_chrecs (*base
, NULL
)
2569 || chrec_contains_symbols_defined_in_loop (*base
, loop
->num
))
2575 /* Runs the analysis of scalar evolutions. */
2578 scev_analysis (void)
2580 varray_type exit_conditions
;
2582 VARRAY_GENERIC_PTR_INIT (exit_conditions
, 37, "exit_conditions");
2583 select_loops_exit_conditions (current_loops
, &exit_conditions
);
2585 if (dump_file
&& (dump_flags
& TDF_STATS
))
2586 analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions
);
2588 number_of_iterations_for_all_loops (exit_conditions
);
2589 VARRAY_CLEAR (exit_conditions
);
2592 /* Finalize the scalar evolution analysis. */
2595 scev_finalize (void)
2597 htab_delete (scalar_evolution_info
);
2598 BITMAP_FREE (already_instantiated
);