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"
241 /* These RTL headers are needed for basic-block.h. */
243 #include "basic-block.h"
244 #include "diagnostic.h"
245 #include "tree-flow.h"
246 #include "tree-dump.h"
249 #include "tree-chrec.h"
250 #include "tree-scalar-evolution.h"
251 #include "tree-pass.h"
254 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
255 static tree
resolve_mixers (struct loop
*, tree
);
257 /* The cached information about a ssa name VAR, claiming that inside LOOP,
258 the value of VAR can be expressed as CHREC. */
266 /* Counters for the scev database. */
267 static unsigned nb_set_scev
= 0;
268 static unsigned nb_get_scev
= 0;
270 /* The following trees are unique elements. Thus the comparison of
271 another element to these elements should be done on the pointer to
272 these trees, and not on their value. */
274 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
275 tree chrec_not_analyzed_yet
;
277 /* Reserved to the cases where the analyzer has detected an
278 undecidable property at compile time. */
279 tree chrec_dont_know
;
281 /* When the analyzer has detected that a property will never
282 happen, then it qualifies it with chrec_known. */
285 static bitmap already_instantiated
;
287 static htab_t scalar_evolution_info
;
290 /* Constructs a new SCEV_INFO_STR structure. */
292 static inline struct scev_info_str
*
293 new_scev_info_str (tree var
)
295 struct scev_info_str
*res
;
297 res
= xmalloc (sizeof (struct scev_info_str
));
299 res
->chrec
= chrec_not_analyzed_yet
;
304 /* Computes a hash function for database element ELT. */
307 hash_scev_info (const void *elt
)
309 return SSA_NAME_VERSION (((struct scev_info_str
*) elt
)->var
);
312 /* Compares database elements E1 and E2. */
315 eq_scev_info (const void *e1
, const void *e2
)
317 const struct scev_info_str
*elt1
= e1
;
318 const struct scev_info_str
*elt2
= e2
;
320 return elt1
->var
== elt2
->var
;
323 /* Deletes database element E. */
326 del_scev_info (void *e
)
331 /* Get the index corresponding to VAR in the current LOOP. If
332 it's the first time we ask for this VAR, then we return
333 chrec_not_analyzed_yet for this VAR and return its index. */
336 find_var_scev_info (tree var
)
338 struct scev_info_str
*res
;
339 struct scev_info_str tmp
;
343 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
346 *slot
= new_scev_info_str (var
);
352 /* Return true when CHREC contains symbolic names defined in
356 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
358 if (chrec
== NULL_TREE
)
361 if (TREE_INVARIANT (chrec
))
364 if (TREE_CODE (chrec
) == VAR_DECL
365 || TREE_CODE (chrec
) == PARM_DECL
366 || TREE_CODE (chrec
) == FUNCTION_DECL
367 || TREE_CODE (chrec
) == LABEL_DECL
368 || TREE_CODE (chrec
) == RESULT_DECL
369 || TREE_CODE (chrec
) == FIELD_DECL
)
372 if (TREE_CODE (chrec
) == SSA_NAME
)
374 tree def
= SSA_NAME_DEF_STMT (chrec
);
375 struct loop
*def_loop
= loop_containing_stmt (def
);
376 struct loop
*loop
= current_loops
->parray
[loop_nb
];
378 if (def_loop
== NULL
)
381 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
387 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
390 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 2),
395 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 1),
400 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 0),
409 /* Return true when PHI is a loop-phi-node. */
412 loop_phi_node_p (tree phi
)
414 /* The implementation of this function is based on the following
415 property: "all the loop-phi-nodes of a loop are contained in the
416 loop's header basic block". */
418 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
421 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
422 In general, in the case of multivariate evolutions we want to get
423 the evolution in different loops. LOOP specifies the level for
424 which to get the evolution.
428 | for (j = 0; j < 100; j++)
430 | for (k = 0; k < 100; k++)
432 | i = k + j; - Here the value of i is a function of j, k.
434 | ... = i - Here the value of i is a function of j.
436 | ... = i - Here the value of i is a scalar.
442 | i_1 = phi (i_0, i_2)
446 This loop has the same effect as:
447 LOOP_1 has the same effect as:
451 The overall effect of the loop, "i_0 + 20" in the previous example,
452 is obtained by passing in the parameters: LOOP = 1,
453 EVOLUTION_FN = {i_0, +, 2}_1.
457 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
461 if (evolution_fn
== chrec_dont_know
)
462 return chrec_dont_know
;
464 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
466 if (CHREC_VARIABLE (evolution_fn
) >= (unsigned) loop
->num
)
468 struct loop
*inner_loop
=
469 current_loops
->parray
[CHREC_VARIABLE (evolution_fn
)];
470 tree nb_iter
= number_of_iterations_in_loop (inner_loop
);
472 if (nb_iter
== chrec_dont_know
)
473 return chrec_dont_know
;
478 /* Number of iterations is off by one (the ssa name we
479 analyze must be defined before the exit). */
480 nb_iter
= chrec_fold_minus (chrec_type (nb_iter
),
482 build_int_cst_type (chrec_type (nb_iter
), 1));
484 /* evolution_fn is the evolution function in LOOP. Get
485 its value in the nb_iter-th iteration. */
486 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
488 /* Continue the computation until ending on a parent of LOOP. */
489 return compute_overall_effect_of_inner_loop (loop
, res
);
496 /* If the evolution function is an invariant, there is nothing to do. */
497 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
501 return chrec_dont_know
;
504 /* Determine whether the CHREC is always positive/negative. If the expression
505 cannot be statically analyzed, return false, otherwise set the answer into
509 chrec_is_positive (tree chrec
, bool *value
)
516 switch (TREE_CODE (chrec
))
518 case POLYNOMIAL_CHREC
:
519 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
520 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
523 /* FIXME -- overflows. */
524 if (value0
== value1
)
530 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
531 and the proof consists in showing that the sign never
532 changes during the execution of the loop, from 0 to
533 loop->nb_iterations. */
534 if (!evolution_function_is_affine_p (chrec
))
537 nb_iter
= number_of_iterations_in_loop
538 (current_loops
->parray
[CHREC_VARIABLE (chrec
)]);
540 if (chrec_contains_undetermined (nb_iter
))
543 nb_iter
= chrec_fold_minus
544 (chrec_type (nb_iter
), nb_iter
,
545 build_int_cst (chrec_type (nb_iter
), 1));
548 /* TODO -- If the test is after the exit, we may decrease the number of
549 iterations by one. */
551 nb_iter
= chrec_fold_minus
552 (chrec_type (nb_iter
), nb_iter
,
553 build_int_cst (chrec_type (nb_iter
), 1));
556 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
558 if (!chrec_is_positive (end_value
, &value2
))
562 return value0
== value1
;
565 *value
= (tree_int_cst_sgn (chrec
) == 1);
573 /* Associate CHREC to SCALAR. */
576 set_scalar_evolution (tree scalar
, tree chrec
)
580 if (TREE_CODE (scalar
) != SSA_NAME
)
583 scalar_info
= find_var_scev_info (scalar
);
587 if (dump_flags
& TDF_DETAILS
)
589 fprintf (dump_file
, "(set_scalar_evolution \n");
590 fprintf (dump_file
, " (scalar = ");
591 print_generic_expr (dump_file
, scalar
, 0);
592 fprintf (dump_file
, ")\n (scalar_evolution = ");
593 print_generic_expr (dump_file
, chrec
, 0);
594 fprintf (dump_file
, "))\n");
596 if (dump_flags
& TDF_STATS
)
600 *scalar_info
= chrec
;
603 /* Retrieve the chrec associated to SCALAR in the LOOP. */
606 get_scalar_evolution (tree scalar
)
612 if (dump_flags
& TDF_DETAILS
)
614 fprintf (dump_file
, "(get_scalar_evolution \n");
615 fprintf (dump_file
, " (scalar = ");
616 print_generic_expr (dump_file
, scalar
, 0);
617 fprintf (dump_file
, ")\n");
619 if (dump_flags
& TDF_STATS
)
623 switch (TREE_CODE (scalar
))
626 res
= *find_var_scev_info (scalar
);
635 res
= chrec_not_analyzed_yet
;
639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
641 fprintf (dump_file
, " (scalar_evolution = ");
642 print_generic_expr (dump_file
, res
, 0);
643 fprintf (dump_file
, "))\n");
649 /* Helper function for add_to_evolution. Returns the evolution
650 function for an assignment of the form "a = b + c", where "a" and
651 "b" are on the strongly connected component. CHREC_BEFORE is the
652 information that we already have collected up to this point.
653 TO_ADD is the evolution of "c".
655 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
656 evolution the expression TO_ADD, otherwise construct an evolution
657 part for this loop. */
660 add_to_evolution_1 (unsigned loop_nb
,
664 switch (TREE_CODE (chrec_before
))
666 case POLYNOMIAL_CHREC
:
667 if (CHREC_VARIABLE (chrec_before
) <= loop_nb
)
671 tree type
= chrec_type (chrec_before
);
673 /* When there is no evolution part in this loop, build it. */
674 if (CHREC_VARIABLE (chrec_before
) < loop_nb
)
678 right
= build_int_cst (type
, 0);
682 var
= CHREC_VARIABLE (chrec_before
);
683 left
= CHREC_LEFT (chrec_before
);
684 right
= CHREC_RIGHT (chrec_before
);
687 return build_polynomial_chrec
688 (var
, left
, chrec_fold_plus (type
, right
, to_add
));
691 /* Search the evolution in LOOP_NB. */
692 return build_polynomial_chrec
693 (CHREC_VARIABLE (chrec_before
),
694 add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
), to_add
),
695 CHREC_RIGHT (chrec_before
));
698 /* These nodes do not depend on a loop. */
699 if (chrec_before
== chrec_dont_know
)
700 return chrec_dont_know
;
701 return build_polynomial_chrec (loop_nb
, chrec_before
, to_add
);
705 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
708 Description (provided for completeness, for those who read code in
709 a plane, and for my poor 62 bytes brain that would have forgotten
710 all this in the next two or three months):
712 The algorithm of translation of programs from the SSA representation
713 into the chrecs syntax is based on a pattern matching. After having
714 reconstructed the overall tree expression for a loop, there are only
715 two cases that can arise:
717 1. a = loop-phi (init, a + expr)
718 2. a = loop-phi (init, expr)
720 where EXPR is either a scalar constant with respect to the analyzed
721 loop (this is a degree 0 polynomial), or an expression containing
722 other loop-phi definitions (these are higher degree polynomials).
729 | a = phi (init, a + 5)
736 | a = phi (inita, 2 * b + 3)
737 | b = phi (initb, b + 1)
740 For the first case, the semantics of the SSA representation is:
742 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
744 that is, there is a loop index "x" that determines the scalar value
745 of the variable during the loop execution. During the first
746 iteration, the value is that of the initial condition INIT, while
747 during the subsequent iterations, it is the sum of the initial
748 condition with the sum of all the values of EXPR from the initial
749 iteration to the before last considered iteration.
751 For the second case, the semantics of the SSA program is:
753 | a (x) = init, if x = 0;
754 | expr (x - 1), otherwise.
756 The second case corresponds to the PEELED_CHREC, whose syntax is
757 close to the syntax of a loop-phi-node:
759 | phi (init, expr) vs. (init, expr)_x
761 The proof of the translation algorithm for the first case is a
762 proof by structural induction based on the degree of EXPR.
765 When EXPR is a constant with respect to the analyzed loop, or in
766 other words when EXPR is a polynomial of degree 0, the evolution of
767 the variable A in the loop is an affine function with an initial
768 condition INIT, and a step EXPR. In order to show this, we start
769 from the semantics of the SSA representation:
771 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
773 and since "expr (j)" is a constant with respect to "j",
775 f (x) = init + x * expr
777 Finally, based on the semantics of the pure sum chrecs, by
778 identification we get the corresponding chrecs syntax:
780 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
781 f (x) -> {init, +, expr}_x
784 Suppose that EXPR is a polynomial of degree N with respect to the
785 analyzed loop_x for which we have already determined that it is
786 written under the chrecs syntax:
788 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
790 We start from the semantics of the SSA program:
792 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
794 | f (x) = init + \sum_{j = 0}^{x - 1}
795 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
797 | f (x) = init + \sum_{j = 0}^{x - 1}
798 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
800 | f (x) = init + \sum_{k = 0}^{n - 1}
801 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
803 | f (x) = init + \sum_{k = 0}^{n - 1}
804 | (b_k * \binom{x}{k + 1})
806 | f (x) = init + b_0 * \binom{x}{1} + ...
807 | + b_{n-1} * \binom{x}{n}
809 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
810 | + b_{n-1} * \binom{x}{n}
813 And finally from the definition of the chrecs syntax, we identify:
814 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
816 This shows the mechanism that stands behind the add_to_evolution
817 function. An important point is that the use of symbolic
818 parameters avoids the need of an analysis schedule.
825 | a = phi (inita, a + 2 + b)
826 | b = phi (initb, b + 1)
829 When analyzing "a", the algorithm keeps "b" symbolically:
831 | a -> {inita, +, 2 + b}_1
833 Then, after instantiation, the analyzer ends on the evolution:
835 | a -> {inita, +, 2 + initb, +, 1}_1
840 add_to_evolution (unsigned loop_nb
,
845 tree type
= chrec_type (to_add
);
846 tree res
= NULL_TREE
;
848 if (to_add
== NULL_TREE
)
851 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
852 instantiated at this point. */
853 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
854 /* This should not happen. */
855 return chrec_dont_know
;
857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
859 fprintf (dump_file
, "(add_to_evolution \n");
860 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
861 fprintf (dump_file
, " (chrec_before = ");
862 print_generic_expr (dump_file
, chrec_before
, 0);
863 fprintf (dump_file
, ")\n (to_add = ");
864 print_generic_expr (dump_file
, to_add
, 0);
865 fprintf (dump_file
, ")\n");
868 if (code
== MINUS_EXPR
)
869 to_add
= chrec_fold_multiply (type
, to_add
,
870 build_int_cst_type (type
, -1));
872 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
);
874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, " (res = ");
877 print_generic_expr (dump_file
, res
, 0);
878 fprintf (dump_file
, "))\n");
884 /* Helper function. */
887 set_nb_iterations_in_loop (struct loop
*loop
,
890 res
= chrec_fold_plus (chrec_type (res
), res
,
891 build_int_cst_type (chrec_type (res
), 1));
893 /* FIXME HWI: However we want to store one iteration less than the
894 count of the loop in order to be compatible with the other
895 nb_iter computations in loop-iv. This also allows the
896 representation of nb_iters that are equal to MAX_INT. */
897 if (TREE_CODE (res
) == INTEGER_CST
898 && (TREE_INT_CST_LOW (res
) == 0
899 || TREE_OVERFLOW (res
)))
900 res
= chrec_dont_know
;
902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
904 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
905 print_generic_expr (dump_file
, res
, 0);
906 fprintf (dump_file
, "))\n");
909 loop
->nb_iterations
= res
;
915 /* This section selects the loops that will be good candidates for the
916 scalar evolution analysis. For the moment, greedily select all the
917 loop nests we could analyze. */
919 /* Return true when it is possible to analyze the condition expression
923 analyzable_condition (tree expr
)
927 if (TREE_CODE (expr
) != COND_EXPR
)
930 condition
= TREE_OPERAND (expr
, 0);
932 switch (TREE_CODE (condition
))
952 /* For a loop with a single exit edge, return the COND_EXPR that
953 guards the exit edge. If the expression is too difficult to
954 analyze, then give up. */
957 get_loop_exit_condition (struct loop
*loop
)
959 tree res
= NULL_TREE
;
960 edge exit_edge
= loop
->single_exit
;
963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
964 fprintf (dump_file
, "(get_loop_exit_condition \n ");
970 expr
= last_stmt (exit_edge
->src
);
971 if (analyzable_condition (expr
))
975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
977 print_generic_expr (dump_file
, res
, 0);
978 fprintf (dump_file
, ")\n");
984 /* Recursively determine and enqueue the exit conditions for a loop. */
987 get_exit_conditions_rec (struct loop
*loop
,
988 VEC(tree
,heap
) **exit_conditions
)
993 /* Recurse on the inner loops, then on the next (sibling) loops. */
994 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
995 get_exit_conditions_rec (loop
->next
, exit_conditions
);
997 if (loop
->single_exit
)
999 tree loop_condition
= get_loop_exit_condition (loop
);
1002 VEC_safe_push (tree
, heap
, *exit_conditions
, loop_condition
);
1006 /* Select the candidate loop nests for the analysis. This function
1007 initializes the EXIT_CONDITIONS array. */
1010 select_loops_exit_conditions (struct loops
*loops
,
1011 VEC(tree
,heap
) **exit_conditions
)
1013 struct loop
*function_body
= loops
->parray
[0];
1015 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
1019 /* Depth first search algorithm. */
1021 static bool follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*);
1023 /* Follow the ssa edge into the right hand side RHS of an assignment.
1024 Return true if the strongly connected component has been found. */
1027 follow_ssa_edge_in_rhs (struct loop
*loop
,
1031 tree
*evolution_of_loop
)
1035 tree type_rhs
= TREE_TYPE (rhs
);
1037 /* The RHS is one of the following cases:
1043 - other cases are not yet handled. */
1044 switch (TREE_CODE (rhs
))
1047 /* This assignment is under the form "a_1 = (cast) rhs. */
1048 res
= follow_ssa_edge_in_rhs (loop
, at_stmt
, TREE_OPERAND (rhs
, 0),
1049 halting_phi
, evolution_of_loop
);
1050 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
),
1051 *evolution_of_loop
, at_stmt
);
1055 /* This assignment is under the form "a_1 = 7". */
1060 /* This assignment is under the form: "a_1 = b_2". */
1061 res
= follow_ssa_edge
1062 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
);
1066 /* This case is under the form "rhs0 + rhs1". */
1067 rhs0
= TREE_OPERAND (rhs
, 0);
1068 rhs1
= TREE_OPERAND (rhs
, 1);
1069 STRIP_TYPE_NOPS (rhs0
);
1070 STRIP_TYPE_NOPS (rhs1
);
1072 if (TREE_CODE (rhs0
) == SSA_NAME
)
1074 if (TREE_CODE (rhs1
) == SSA_NAME
)
1076 /* Match an assignment under the form:
1078 res
= follow_ssa_edge
1079 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1083 *evolution_of_loop
= add_to_evolution
1085 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1090 res
= follow_ssa_edge
1091 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1095 *evolution_of_loop
= add_to_evolution
1097 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1104 /* Match an assignment under the form:
1106 res
= follow_ssa_edge
1107 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1110 *evolution_of_loop
= add_to_evolution
1111 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1117 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1119 /* Match an assignment under the form:
1121 res
= follow_ssa_edge
1122 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1125 *evolution_of_loop
= add_to_evolution
1126 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1132 /* Otherwise, match an assignment under the form:
1134 /* And there is nothing to do. */
1140 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1141 rhs0
= TREE_OPERAND (rhs
, 0);
1142 rhs1
= TREE_OPERAND (rhs
, 1);
1143 STRIP_TYPE_NOPS (rhs0
);
1144 STRIP_TYPE_NOPS (rhs1
);
1146 if (TREE_CODE (rhs0
) == SSA_NAME
)
1148 /* Match an assignment under the form:
1150 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1153 *evolution_of_loop
= add_to_evolution
1154 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1159 /* Otherwise, match an assignment under the form:
1161 /* And there is nothing to do. */
1167 /* This case is under the form "opnd0 = rhs0 * rhs1". */
1168 rhs0
= TREE_OPERAND (rhs
, 0);
1169 rhs1
= TREE_OPERAND (rhs
, 1);
1170 STRIP_TYPE_NOPS (rhs0
);
1171 STRIP_TYPE_NOPS (rhs1
);
1173 if (TREE_CODE (rhs0
) == SSA_NAME
)
1175 if (TREE_CODE (rhs1
) == SSA_NAME
)
1177 /* Match an assignment under the form:
1179 res
= follow_ssa_edge
1180 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1184 *evolution_of_loop
= chrec_dont_know
;
1188 res
= follow_ssa_edge
1189 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1193 *evolution_of_loop
= chrec_dont_know
;
1199 /* Match an assignment under the form:
1201 res
= follow_ssa_edge
1202 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1205 *evolution_of_loop
= chrec_dont_know
;
1209 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1211 /* Match an assignment under the form:
1213 res
= follow_ssa_edge
1214 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1217 *evolution_of_loop
= chrec_dont_know
;
1221 /* Otherwise, match an assignment under the form:
1223 /* And there is nothing to do. */
1230 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1231 It must be handled as a copy assignment of the form a_1 = a_2. */
1232 tree op0
= ASSERT_EXPR_VAR (rhs
);
1233 if (TREE_CODE (op0
) == SSA_NAME
)
1234 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1235 halting_phi
, evolution_of_loop
);
1250 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1253 backedge_phi_arg_p (tree phi
, int i
)
1255 edge e
= PHI_ARG_EDGE (phi
, i
);
1257 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1258 about updating it anywhere, and this should work as well most of the
1260 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1266 /* Helper function for one branch of the condition-phi-node. Return
1267 true if the strongly connected component has been found following
1271 follow_ssa_edge_in_condition_phi_branch (int i
,
1275 tree
*evolution_of_branch
,
1278 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1279 *evolution_of_branch
= chrec_dont_know
;
1281 /* Do not follow back edges (they must belong to an irreducible loop, which
1282 we really do not want to worry about). */
1283 if (backedge_phi_arg_p (condition_phi
, i
))
1286 if (TREE_CODE (branch
) == SSA_NAME
)
1288 *evolution_of_branch
= init_cond
;
1289 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1290 evolution_of_branch
);
1293 /* This case occurs when one of the condition branches sets
1294 the variable to a constant: i.e. a phi-node like
1295 "a_2 = PHI <a_7(5), 2(6)>;".
1297 FIXME: This case have to be refined correctly:
1298 in some cases it is possible to say something better than
1299 chrec_dont_know, for example using a wrap-around notation. */
1303 /* This function merges the branches of a condition-phi-node in a
1307 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1310 tree
*evolution_of_loop
)
1313 tree init
= *evolution_of_loop
;
1314 tree evolution_of_branch
;
1316 if (!follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1318 &evolution_of_branch
,
1321 *evolution_of_loop
= evolution_of_branch
;
1323 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1325 /* Quickly give up when the evolution of one of the branches is
1327 if (*evolution_of_loop
== chrec_dont_know
)
1330 if (!follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1332 &evolution_of_branch
,
1336 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1337 evolution_of_branch
);
1343 /* Follow an SSA edge in an inner loop. It computes the overall
1344 effect of the loop, and following the symbolic initial conditions,
1345 it follows the edges in the parent loop. The inner loop is
1346 considered as a single statement. */
1349 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1352 tree
*evolution_of_loop
)
1354 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1355 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1357 /* Sometimes, the inner loop is too difficult to analyze, and the
1358 result of the analysis is a symbolic parameter. */
1359 if (ev
== PHI_RESULT (loop_phi_node
))
1364 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1366 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1369 /* Follow the edges that exit the inner loop. */
1370 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1371 if (!flow_bb_inside_loop_p (loop
, bb
))
1372 res
= res
|| follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
,
1377 /* If the path crosses this loop-phi, give up. */
1379 *evolution_of_loop
= chrec_dont_know
;
1384 /* Otherwise, compute the overall effect of the inner loop. */
1385 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1386 return follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1390 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1391 path that is analyzed on the return walk. */
1394 follow_ssa_edge (struct loop
*loop
,
1397 tree
*evolution_of_loop
)
1399 struct loop
*def_loop
;
1401 if (TREE_CODE (def
) == NOP_EXPR
)
1404 def_loop
= loop_containing_stmt (def
);
1406 switch (TREE_CODE (def
))
1409 if (!loop_phi_node_p (def
))
1410 /* DEF is a condition-phi-node. Follow the branches, and
1411 record their evolutions. Finally, merge the collected
1412 information and set the approximation to the main
1414 return follow_ssa_edge_in_condition_phi
1415 (loop
, def
, halting_phi
, evolution_of_loop
);
1417 /* When the analyzed phi is the halting_phi, the
1418 depth-first search is over: we have found a path from
1419 the halting_phi to itself in the loop. */
1420 if (def
== halting_phi
)
1423 /* Otherwise, the evolution of the HALTING_PHI depends
1424 on the evolution of another loop-phi-node, i.e. the
1425 evolution function is a higher degree polynomial. */
1426 if (def_loop
== loop
)
1430 if (flow_loop_nested_p (loop
, def_loop
))
1431 return follow_ssa_edge_inner_loop_phi
1432 (loop
, def
, halting_phi
, evolution_of_loop
);
1438 return follow_ssa_edge_in_rhs (loop
, def
,
1439 TREE_OPERAND (def
, 1),
1444 /* At this level of abstraction, the program is just a set
1445 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1446 other node to be handled. */
1453 /* Given a LOOP_PHI_NODE, this function determines the evolution
1454 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1457 analyze_evolution_in_loop (tree loop_phi_node
,
1461 tree evolution_function
= chrec_not_analyzed_yet
;
1462 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1467 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1468 fprintf (dump_file
, " (loop_phi_node = ");
1469 print_generic_expr (dump_file
, loop_phi_node
, 0);
1470 fprintf (dump_file
, ")\n");
1473 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1475 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1476 tree ssa_chain
, ev_fn
;
1479 /* Select the edges that enter the loop body. */
1480 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1481 if (!flow_bb_inside_loop_p (loop
, bb
))
1484 if (TREE_CODE (arg
) == SSA_NAME
)
1486 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1488 /* Pass in the initial condition to the follow edge function. */
1490 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
);
1495 /* When it is impossible to go back on the same
1496 loop_phi_node by following the ssa edges, the
1497 evolution is represented by a peeled chrec, i.e. the
1498 first iteration, EV_FN has the value INIT_COND, then
1499 all the other iterations it has the value of ARG.
1500 For the moment, PEELED_CHREC nodes are not built. */
1502 ev_fn
= chrec_dont_know
;
1504 /* When there are multiple back edges of the loop (which in fact never
1505 happens currently, but nevertheless), merge their evolutions. */
1506 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1509 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1511 fprintf (dump_file
, " (evolution_function = ");
1512 print_generic_expr (dump_file
, evolution_function
, 0);
1513 fprintf (dump_file
, "))\n");
1516 return evolution_function
;
1519 /* Given a loop-phi-node, return the initial conditions of the
1520 variable on entry of the loop. When the CCP has propagated
1521 constants into the loop-phi-node, the initial condition is
1522 instantiated, otherwise the initial condition is kept symbolic.
1523 This analyzer does not analyze the evolution outside the current
1524 loop, and leaves this task to the on-demand tree reconstructor. */
1527 analyze_initial_condition (tree loop_phi_node
)
1530 tree init_cond
= chrec_not_analyzed_yet
;
1531 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1535 fprintf (dump_file
, "(analyze_initial_condition \n");
1536 fprintf (dump_file
, " (loop_phi_node = \n");
1537 print_generic_expr (dump_file
, loop_phi_node
, 0);
1538 fprintf (dump_file
, ")\n");
1541 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1543 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1544 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1546 /* When the branch is oriented to the loop's body, it does
1547 not contribute to the initial condition. */
1548 if (flow_bb_inside_loop_p (loop
, bb
))
1551 if (init_cond
== chrec_not_analyzed_yet
)
1557 if (TREE_CODE (branch
) == SSA_NAME
)
1559 init_cond
= chrec_dont_know
;
1563 init_cond
= chrec_merge (init_cond
, branch
);
1566 /* Ooops -- a loop without an entry??? */
1567 if (init_cond
== chrec_not_analyzed_yet
)
1568 init_cond
= chrec_dont_know
;
1570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1572 fprintf (dump_file
, " (init_cond = ");
1573 print_generic_expr (dump_file
, init_cond
, 0);
1574 fprintf (dump_file
, "))\n");
1580 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1583 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1586 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1589 if (phi_loop
!= loop
)
1591 struct loop
*subloop
;
1592 tree evolution_fn
= analyze_scalar_evolution
1593 (phi_loop
, PHI_RESULT (loop_phi_node
));
1595 /* Dive one level deeper. */
1596 subloop
= superloop_at_depth (phi_loop
, loop
->depth
+ 1);
1598 /* Interpret the subloop. */
1599 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1603 /* Otherwise really interpret the loop phi. */
1604 init_cond
= analyze_initial_condition (loop_phi_node
);
1605 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1610 /* This function merges the branches of a condition-phi-node,
1611 contained in the outermost loop, and whose arguments are already
1615 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1618 tree res
= chrec_not_analyzed_yet
;
1620 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1624 if (backedge_phi_arg_p (condition_phi
, i
))
1626 res
= chrec_dont_know
;
1630 branch_chrec
= analyze_scalar_evolution
1631 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1633 res
= chrec_merge (res
, branch_chrec
);
1639 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1640 analyze this node before, follow the definitions until ending
1641 either on an analyzed modify_expr, or on a loop-phi-node. On the
1642 return path, this function propagates evolutions (ala constant copy
1643 propagation). OPND1 is not a GIMPLE expression because we could
1644 analyze the effect of an inner loop: see interpret_loop_phi. */
1647 interpret_rhs_modify_expr (struct loop
*loop
, tree at_stmt
,
1648 tree opnd1
, tree type
)
1650 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1652 if (is_gimple_min_invariant (opnd1
))
1653 return chrec_convert (type
, opnd1
, at_stmt
);
1655 switch (TREE_CODE (opnd1
))
1658 opnd10
= TREE_OPERAND (opnd1
, 0);
1659 opnd11
= TREE_OPERAND (opnd1
, 1);
1660 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1661 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1662 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1663 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1664 res
= chrec_fold_plus (type
, chrec10
, chrec11
);
1668 opnd10
= TREE_OPERAND (opnd1
, 0);
1669 opnd11
= TREE_OPERAND (opnd1
, 1);
1670 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1671 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1672 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1673 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1674 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1678 opnd10
= TREE_OPERAND (opnd1
, 0);
1679 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1680 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1681 res
= chrec_fold_minus (type
, build_int_cst (type
, 0), chrec10
);
1685 opnd10
= TREE_OPERAND (opnd1
, 0);
1686 opnd11
= TREE_OPERAND (opnd1
, 1);
1687 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1688 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1689 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1690 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1691 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1695 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
),
1700 opnd10
= ASSERT_EXPR_VAR (opnd1
);
1701 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd10
),
1707 opnd10
= TREE_OPERAND (opnd1
, 0);
1708 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1709 res
= chrec_convert (type
, chrec10
, at_stmt
);
1713 res
= chrec_dont_know
;
1722 /* This section contains all the entry points:
1723 - number_of_iterations_in_loop,
1724 - analyze_scalar_evolution,
1725 - instantiate_parameters.
1728 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1729 common ancestor of DEF_LOOP and USE_LOOP. */
1732 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1733 struct loop
*def_loop
,
1737 if (def_loop
== wrto_loop
)
1740 def_loop
= superloop_at_depth (def_loop
, wrto_loop
->depth
+ 1);
1741 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1743 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1746 /* Helper recursive function. */
1749 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1751 tree def
, type
= TREE_TYPE (var
);
1753 struct loop
*def_loop
;
1756 return chrec_dont_know
;
1758 if (TREE_CODE (var
) != SSA_NAME
)
1759 return interpret_rhs_modify_expr (loop
, NULL_TREE
, var
, type
);
1761 def
= SSA_NAME_DEF_STMT (var
);
1762 bb
= bb_for_stmt (def
);
1763 def_loop
= bb
? bb
->loop_father
: NULL
;
1766 || !flow_bb_inside_loop_p (loop
, bb
))
1768 /* Keep the symbolic form. */
1773 if (res
!= chrec_not_analyzed_yet
)
1775 if (loop
!= bb
->loop_father
)
1776 res
= compute_scalar_evolution_in_loop
1777 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1782 if (loop
!= def_loop
)
1784 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1785 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1790 switch (TREE_CODE (def
))
1793 res
= interpret_rhs_modify_expr (loop
, def
, TREE_OPERAND (def
, 1), type
);
1797 if (loop_phi_node_p (def
))
1798 res
= interpret_loop_phi (loop
, def
);
1800 res
= interpret_condition_phi (loop
, def
);
1804 res
= chrec_dont_know
;
1810 /* Keep the symbolic form. */
1811 if (res
== chrec_dont_know
)
1814 if (loop
== def_loop
)
1815 set_scalar_evolution (var
, res
);
1820 /* Entry point for the scalar evolution analyzer.
1821 Analyzes and returns the scalar evolution of the ssa_name VAR.
1822 LOOP_NB is the identifier number of the loop in which the variable
1825 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1826 pointer to the statement that uses this variable, in order to
1827 determine the evolution function of the variable, use the following
1830 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1831 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1832 tree chrec_instantiated = instantiate_parameters
1833 (loop_nb, chrec_with_symbols);
1837 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1843 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1844 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1845 fprintf (dump_file
, " (scalar = ");
1846 print_generic_expr (dump_file
, var
, 0);
1847 fprintf (dump_file
, ")\n");
1850 res
= analyze_scalar_evolution_1 (loop
, var
, get_scalar_evolution (var
));
1852 if (TREE_CODE (var
) == SSA_NAME
&& res
== chrec_dont_know
)
1855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1856 fprintf (dump_file
, ")\n");
1861 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1862 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1866 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
1874 ev
= analyze_scalar_evolution (use_loop
, ev
);
1875 ev
= resolve_mixers (use_loop
, ev
);
1877 if (use_loop
== wrto_loop
)
1880 /* If the value of the use changes in the inner loop, we cannot express
1881 its value in the outer loop (we might try to return interval chrec,
1882 but we do not have a user for it anyway) */
1883 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
1885 return chrec_dont_know
;
1887 use_loop
= use_loop
->outer
;
1891 /* Returns instantiated value for VERSION in CACHE. */
1894 get_instantiated_value (htab_t cache
, tree version
)
1896 struct scev_info_str
*info
, pattern
;
1898 pattern
.var
= version
;
1899 info
= htab_find (cache
, &pattern
);
1907 /* Sets instantiated value for VERSION to VAL in CACHE. */
1910 set_instantiated_value (htab_t cache
, tree version
, tree val
)
1912 struct scev_info_str
*info
, pattern
;
1915 pattern
.var
= version
;
1916 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
1921 info
= *slot
= new_scev_info_str (version
);
1925 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1926 with respect to LOOP. CHREC is the chrec to instantiate. If
1927 ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1928 outer loop chrecs is done. CACHE is the cache of already instantiated
1932 instantiate_parameters_1 (struct loop
*loop
, tree chrec
,
1933 bool allow_superloop_chrecs
,
1936 tree res
, op0
, op1
, op2
;
1938 struct loop
*def_loop
;
1940 if (chrec
== NULL_TREE
1941 || automatically_generated_chrec_p (chrec
))
1944 if (is_gimple_min_invariant (chrec
))
1947 switch (TREE_CODE (chrec
))
1950 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
1952 /* A parameter (or loop invariant and we do not want to include
1953 evolutions in outer loops), nothing to do. */
1955 || (!allow_superloop_chrecs
1956 && !flow_bb_inside_loop_p (loop
, def_bb
)))
1959 /* We cache the value of instantiated variable to avoid exponential
1960 time complexity due to reevaluations. We also store the convenient
1961 value in the cache in order to prevent infinite recursion -- we do
1962 not want to instantiate the SSA_NAME if it is in a mixer
1963 structure. This is used for avoiding the instantiation of
1964 recursively defined functions, such as:
1966 | a_2 -> {0, +, 1, +, a_2}_1 */
1968 res
= get_instantiated_value (cache
, chrec
);
1972 /* Store the convenient value for chrec in the structure. If it
1973 is defined outside of the loop, we may just leave it in symbolic
1974 form, otherwise we need to admit that we do not know its behavior
1976 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
1977 set_instantiated_value (cache
, chrec
, res
);
1979 /* To make things even more complicated, instantiate_parameters_1
1980 calls analyze_scalar_evolution that may call # of iterations
1981 analysis that may in turn call instantiate_parameters_1 again.
1982 To prevent the infinite recursion, keep also the bitmap of
1983 ssa names that are being instantiated globally. */
1984 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
1987 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
1989 /* If the analysis yields a parametric chrec, instantiate the
1991 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
1992 res
= analyze_scalar_evolution (def_loop
, chrec
);
1993 if (res
!= chrec_dont_know
)
1994 res
= instantiate_parameters_1 (loop
, res
, allow_superloop_chrecs
,
1996 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
1998 /* Store the correct value to the cache. */
1999 set_instantiated_value (cache
, chrec
, res
);
2002 case POLYNOMIAL_CHREC
:
2003 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2004 allow_superloop_chrecs
, cache
);
2005 if (op0
== chrec_dont_know
)
2006 return chrec_dont_know
;
2008 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2009 allow_superloop_chrecs
, cache
);
2010 if (op1
== chrec_dont_know
)
2011 return chrec_dont_know
;
2013 if (CHREC_LEFT (chrec
) != op0
2014 || CHREC_RIGHT (chrec
) != op1
)
2015 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2019 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2020 allow_superloop_chrecs
, cache
);
2021 if (op0
== chrec_dont_know
)
2022 return chrec_dont_know
;
2024 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2025 allow_superloop_chrecs
, cache
);
2026 if (op1
== chrec_dont_know
)
2027 return chrec_dont_know
;
2029 if (TREE_OPERAND (chrec
, 0) != op0
2030 || TREE_OPERAND (chrec
, 1) != op1
)
2031 chrec
= chrec_fold_plus (TREE_TYPE (chrec
), op0
, op1
);
2035 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2036 allow_superloop_chrecs
, cache
);
2037 if (op0
== chrec_dont_know
)
2038 return chrec_dont_know
;
2040 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2041 allow_superloop_chrecs
, cache
);
2042 if (op1
== chrec_dont_know
)
2043 return chrec_dont_know
;
2045 if (TREE_OPERAND (chrec
, 0) != op0
2046 || TREE_OPERAND (chrec
, 1) != op1
)
2047 chrec
= chrec_fold_minus (TREE_TYPE (chrec
), op0
, op1
);
2051 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2052 allow_superloop_chrecs
, cache
);
2053 if (op0
== chrec_dont_know
)
2054 return chrec_dont_know
;
2056 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2057 allow_superloop_chrecs
, cache
);
2058 if (op1
== chrec_dont_know
)
2059 return chrec_dont_know
;
2061 if (TREE_OPERAND (chrec
, 0) != op0
2062 || TREE_OPERAND (chrec
, 1) != op1
)
2063 chrec
= chrec_fold_multiply (TREE_TYPE (chrec
), op0
, op1
);
2068 case NON_LVALUE_EXPR
:
2069 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2070 allow_superloop_chrecs
, cache
);
2071 if (op0
== chrec_dont_know
)
2072 return chrec_dont_know
;
2074 if (op0
== TREE_OPERAND (chrec
, 0))
2077 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL_TREE
);
2079 case SCEV_NOT_KNOWN
:
2080 return chrec_dont_know
;
2089 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2092 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2093 allow_superloop_chrecs
, cache
);
2094 if (op0
== chrec_dont_know
)
2095 return chrec_dont_know
;
2097 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2098 allow_superloop_chrecs
, cache
);
2099 if (op1
== chrec_dont_know
)
2100 return chrec_dont_know
;
2102 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2103 allow_superloop_chrecs
, cache
);
2104 if (op2
== chrec_dont_know
)
2105 return chrec_dont_know
;
2107 if (op0
== TREE_OPERAND (chrec
, 0)
2108 && op1
== TREE_OPERAND (chrec
, 1)
2109 && op2
== TREE_OPERAND (chrec
, 2))
2112 return fold (build (TREE_CODE (chrec
),
2113 TREE_TYPE (chrec
), op0
, op1
, op2
));
2116 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2117 allow_superloop_chrecs
, cache
);
2118 if (op0
== chrec_dont_know
)
2119 return chrec_dont_know
;
2121 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2122 allow_superloop_chrecs
, cache
);
2123 if (op1
== chrec_dont_know
)
2124 return chrec_dont_know
;
2126 if (op0
== TREE_OPERAND (chrec
, 0)
2127 && op1
== TREE_OPERAND (chrec
, 1))
2129 return fold (build (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
));
2132 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2133 allow_superloop_chrecs
, cache
);
2134 if (op0
== chrec_dont_know
)
2135 return chrec_dont_know
;
2136 if (op0
== TREE_OPERAND (chrec
, 0))
2138 return fold (build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
));
2147 /* Too complicated to handle. */
2148 return chrec_dont_know
;
2151 /* Analyze all the parameters of the chrec that were left under a
2152 symbolic form. LOOP is the loop in which symbolic names have to
2153 be analyzed and instantiated. */
2156 instantiate_parameters (struct loop
*loop
,
2160 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2164 fprintf (dump_file
, "(instantiate_parameters \n");
2165 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2166 fprintf (dump_file
, " (chrec = ");
2167 print_generic_expr (dump_file
, chrec
, 0);
2168 fprintf (dump_file
, ")\n");
2171 res
= instantiate_parameters_1 (loop
, chrec
, true, cache
);
2173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2175 fprintf (dump_file
, " (res = ");
2176 print_generic_expr (dump_file
, res
, 0);
2177 fprintf (dump_file
, "))\n");
2180 htab_delete (cache
);
2185 /* Similar to instantiate_parameters, but does not introduce the
2186 evolutions in outer loops for LOOP invariants in CHREC. */
2189 resolve_mixers (struct loop
*loop
, tree chrec
)
2191 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2192 tree ret
= instantiate_parameters_1 (loop
, chrec
, false, cache
);
2193 htab_delete (cache
);
2197 /* Entry point for the analysis of the number of iterations pass.
2198 This function tries to safely approximate the number of iterations
2199 the loop will run. When this property is not decidable at compile
2200 time, the result is chrec_dont_know. Otherwise the result is
2201 a scalar or a symbolic parameter.
2203 Example of analysis: suppose that the loop has an exit condition:
2205 "if (b > 49) goto end_loop;"
2207 and that in a previous analysis we have determined that the
2208 variable 'b' has an evolution function:
2210 "EF = {23, +, 5}_2".
2212 When we evaluate the function at the point 5, i.e. the value of the
2213 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2214 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2215 the loop body has been executed 6 times. */
2218 number_of_iterations_in_loop (struct loop
*loop
)
2222 struct tree_niter_desc niter_desc
;
2224 /* Determine whether the number_of_iterations_in_loop has already
2226 res
= loop
->nb_iterations
;
2229 res
= chrec_dont_know
;
2231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2232 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2234 exit
= loop
->single_exit
;
2238 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
))
2241 type
= TREE_TYPE (niter_desc
.niter
);
2242 if (integer_nonzerop (niter_desc
.may_be_zero
))
2243 res
= build_int_cst (type
, 0);
2244 else if (integer_zerop (niter_desc
.may_be_zero
))
2245 res
= niter_desc
.niter
;
2247 res
= chrec_dont_know
;
2250 return set_nb_iterations_in_loop (loop
, res
);
2253 /* One of the drivers for testing the scalar evolutions analysis.
2254 This function computes the number of iterations for all the loops
2255 from the EXIT_CONDITIONS array. */
2258 number_of_iterations_for_all_loops (VEC(tree
,heap
) **exit_conditions
)
2261 unsigned nb_chrec_dont_know_loops
= 0;
2262 unsigned nb_static_loops
= 0;
2265 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2267 tree res
= number_of_iterations_in_loop (loop_containing_stmt (cond
));
2268 if (chrec_contains_undetermined (res
))
2269 nb_chrec_dont_know_loops
++;
2276 fprintf (dump_file
, "\n(\n");
2277 fprintf (dump_file
, "-----------------------------------------\n");
2278 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2279 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2280 fprintf (dump_file
, "%d\tnb_total_loops\n", current_loops
->num
);
2281 fprintf (dump_file
, "-----------------------------------------\n");
2282 fprintf (dump_file
, ")\n\n");
2284 print_loop_ir (dump_file
);
2290 /* Counters for the stats. */
2296 unsigned nb_affine_multivar
;
2297 unsigned nb_higher_poly
;
2298 unsigned nb_chrec_dont_know
;
2299 unsigned nb_undetermined
;
2302 /* Reset the counters. */
2305 reset_chrecs_counters (struct chrec_stats
*stats
)
2307 stats
->nb_chrecs
= 0;
2308 stats
->nb_affine
= 0;
2309 stats
->nb_affine_multivar
= 0;
2310 stats
->nb_higher_poly
= 0;
2311 stats
->nb_chrec_dont_know
= 0;
2312 stats
->nb_undetermined
= 0;
2315 /* Dump the contents of a CHREC_STATS structure. */
2318 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2320 fprintf (file
, "\n(\n");
2321 fprintf (file
, "-----------------------------------------\n");
2322 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2323 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2324 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2325 stats
->nb_higher_poly
);
2326 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2327 fprintf (file
, "-----------------------------------------\n");
2328 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2329 fprintf (file
, "%d\twith undetermined coefficients\n",
2330 stats
->nb_undetermined
);
2331 fprintf (file
, "-----------------------------------------\n");
2332 fprintf (file
, "%d\tchrecs in the scev database\n",
2333 (int) htab_elements (scalar_evolution_info
));
2334 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2335 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2336 fprintf (file
, "-----------------------------------------\n");
2337 fprintf (file
, ")\n\n");
2340 /* Gather statistics about CHREC. */
2343 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2345 if (dump_file
&& (dump_flags
& TDF_STATS
))
2347 fprintf (dump_file
, "(classify_chrec ");
2348 print_generic_expr (dump_file
, chrec
, 0);
2349 fprintf (dump_file
, "\n");
2354 if (chrec
== NULL_TREE
)
2356 stats
->nb_undetermined
++;
2360 switch (TREE_CODE (chrec
))
2362 case POLYNOMIAL_CHREC
:
2363 if (evolution_function_is_affine_p (chrec
))
2365 if (dump_file
&& (dump_flags
& TDF_STATS
))
2366 fprintf (dump_file
, " affine_univariate\n");
2369 else if (evolution_function_is_affine_multivariate_p (chrec
))
2371 if (dump_file
&& (dump_flags
& TDF_STATS
))
2372 fprintf (dump_file
, " affine_multivariate\n");
2373 stats
->nb_affine_multivar
++;
2377 if (dump_file
&& (dump_flags
& TDF_STATS
))
2378 fprintf (dump_file
, " higher_degree_polynomial\n");
2379 stats
->nb_higher_poly
++;
2388 if (chrec_contains_undetermined (chrec
))
2390 if (dump_file
&& (dump_flags
& TDF_STATS
))
2391 fprintf (dump_file
, " undetermined\n");
2392 stats
->nb_undetermined
++;
2395 if (dump_file
&& (dump_flags
& TDF_STATS
))
2396 fprintf (dump_file
, ")\n");
2399 /* One of the drivers for testing the scalar evolutions analysis.
2400 This function analyzes the scalar evolution of all the scalars
2401 defined as loop phi nodes in one of the loops from the
2402 EXIT_CONDITIONS array.
2404 TODO Optimization: A loop is in canonical form if it contains only
2405 a single scalar loop phi node. All the other scalars that have an
2406 evolution in the loop are rewritten in function of this single
2407 index. This allows the parallelization of the loop. */
2410 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree
,heap
) **exit_conditions
)
2413 struct chrec_stats stats
;
2416 reset_chrecs_counters (&stats
);
2418 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2424 loop
= loop_containing_stmt (cond
);
2427 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2428 if (is_gimple_reg (PHI_RESULT (phi
)))
2430 chrec
= instantiate_parameters
2432 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2434 if (dump_file
&& (dump_flags
& TDF_STATS
))
2435 gather_chrec_stats (chrec
, &stats
);
2439 if (dump_file
&& (dump_flags
& TDF_STATS
))
2440 dump_chrecs_stats (dump_file
, &stats
);
2443 /* Callback for htab_traverse, gathers information on chrecs in the
2447 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2449 struct scev_info_str
*entry
= *slot
;
2451 gather_chrec_stats (entry
->chrec
, stats
);
2456 /* Classify the chrecs of the whole database. */
2459 gather_stats_on_scev_database (void)
2461 struct chrec_stats stats
;
2466 reset_chrecs_counters (&stats
);
2468 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2471 dump_chrecs_stats (dump_file
, &stats
);
2479 initialize_scalar_evolutions_analyzer (void)
2481 /* The elements below are unique. */
2482 if (chrec_dont_know
== NULL_TREE
)
2484 chrec_not_analyzed_yet
= NULL_TREE
;
2485 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2486 chrec_known
= make_node (SCEV_KNOWN
);
2487 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2488 TREE_TYPE (chrec_known
) = void_type_node
;
2492 /* Initialize the analysis of scalar evolutions for LOOPS. */
2495 scev_initialize (struct loops
*loops
)
2498 current_loops
= loops
;
2500 scalar_evolution_info
= htab_create (100, hash_scev_info
,
2501 eq_scev_info
, del_scev_info
);
2502 already_instantiated
= BITMAP_ALLOC (NULL
);
2504 initialize_scalar_evolutions_analyzer ();
2506 for (i
= 1; i
< loops
->num
; i
++)
2507 if (loops
->parray
[i
])
2508 loops
->parray
[i
]->nb_iterations
= NULL_TREE
;
2511 /* Cleans up the information cached by the scalar evolutions analysis. */
2519 if (!scalar_evolution_info
|| !current_loops
)
2522 htab_empty (scalar_evolution_info
);
2523 for (i
= 1; i
< current_loops
->num
; i
++)
2525 loop
= current_loops
->parray
[i
];
2527 loop
->nb_iterations
= NULL_TREE
;
2531 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2532 its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
2533 want STEP to be invariant in LOOP. Otherwise we require it to be an
2534 integer constant. */
2537 simple_iv (struct loop
*loop
, tree stmt
, tree op
, tree
*base
, tree
*step
,
2538 bool allow_nonconstant_step
)
2540 basic_block bb
= bb_for_stmt (stmt
);
2546 type
= TREE_TYPE (op
);
2547 if (TREE_CODE (type
) != INTEGER_TYPE
2548 && TREE_CODE (type
) != POINTER_TYPE
)
2551 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
);
2552 if (chrec_contains_undetermined (ev
))
2555 if (tree_does_not_contain_chrecs (ev
)
2556 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2562 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2563 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2566 *step
= CHREC_RIGHT (ev
);
2567 if (allow_nonconstant_step
)
2569 if (tree_contains_chrecs (*step
, NULL
)
2570 || chrec_contains_symbols_defined_in_loop (*step
, loop
->num
))
2573 else if (TREE_CODE (*step
) != INTEGER_CST
)
2576 *base
= CHREC_LEFT (ev
);
2577 if (tree_contains_chrecs (*base
, NULL
)
2578 || chrec_contains_symbols_defined_in_loop (*base
, loop
->num
))
2584 /* Runs the analysis of scalar evolutions. */
2587 scev_analysis (void)
2589 VEC(tree
,heap
) *exit_conditions
;
2591 exit_conditions
= VEC_alloc (tree
, heap
, 37);
2592 select_loops_exit_conditions (current_loops
, &exit_conditions
);
2594 if (dump_file
&& (dump_flags
& TDF_STATS
))
2595 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2597 number_of_iterations_for_all_loops (&exit_conditions
);
2598 VEC_free (tree
, heap
, exit_conditions
);
2601 /* Finalize the scalar evolution analysis. */
2604 scev_finalize (void)
2606 htab_delete (scalar_evolution_info
);
2607 BITMAP_FREE (already_instantiated
);
2610 /* Replace ssa names for that scev can prove they are constant by the
2611 appropriate constants. Most importantly, this takes care of final
2614 We only consider SSA names defined by phi nodes; rest is left to the
2615 ordinary constant propagation pass. */
2618 scev_const_prop (void)
2621 tree name
, phi
, type
, ev
;
2623 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
);