1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
50 - When the definition is a MODIFY_EXPR: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
75 Example 1: Illustration of the basic algorithm.
81 | if (c > 10) exit_loop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters ({a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
119 or in terms of a C program:
122 | for (x = 0; x <= 7; x++)
128 Example 2: Illustration of the algorithm on nested loops.
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
157 Example 3: Higher degree polynomials.
171 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
172 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
174 Example 4: Lucas, Fibonacci, or mixers in general.
186 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
187 following semantics: during the first iteration of the loop_1, the
188 variable contains the value 1, and then it contains the value "c".
189 Note that this syntax is close to the syntax of the loop-phi-node:
190 "a -> (1, c)_1" vs. "a = phi (1, c)".
192 The symbolic chrec representation contains all the semantics of the
193 original code. What is more difficult is to use this information.
195 Example 5: Flip-flops, or exchangers.
207 Based on these symbolic chrecs, it is possible to refine this
208 information into the more precise PERIODIC_CHRECs:
213 This transformation is not yet implemented.
217 You can find a more detailed description of the algorithm in:
218 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
220 this is a preliminary report and some of the details of the
221 algorithm have changed. I'm working on a research report that
222 updates the description of the algorithms to reflect the design
223 choices used in this implementation.
225 A set of slides show a high level overview of the algorithm and run
226 an example through the scalar evolution analyzer:
227 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
229 The slides that I have presented at the GCC Summit'04 are available
230 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
235 #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"
255 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
256 static tree
resolve_mixers (struct loop
*, tree
);
258 /* The cached information about a ssa name VAR, claiming that inside LOOP,
259 the value of VAR can be expressed as CHREC. */
267 /* Counters for the scev database. */
268 static unsigned nb_set_scev
= 0;
269 static unsigned nb_get_scev
= 0;
271 /* The following trees are unique elements. Thus the comparison of
272 another element to these elements should be done on the pointer to
273 these trees, and not on their value. */
275 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
276 tree chrec_not_analyzed_yet
;
278 /* Reserved to the cases where the analyzer has detected an
279 undecidable property at compile time. */
280 tree chrec_dont_know
;
282 /* When the analyzer has detected that a property will never
283 happen, then it qualifies it with chrec_known. */
286 static bitmap already_instantiated
;
288 static htab_t scalar_evolution_info
;
291 /* Constructs a new SCEV_INFO_STR structure. */
293 static inline struct scev_info_str
*
294 new_scev_info_str (tree var
)
296 struct scev_info_str
*res
;
298 res
= XNEW (struct scev_info_str
);
300 res
->chrec
= chrec_not_analyzed_yet
;
305 /* Computes a hash function for database element ELT. */
308 hash_scev_info (const void *elt
)
310 return SSA_NAME_VERSION (((struct scev_info_str
*) elt
)->var
);
313 /* Compares database elements E1 and E2. */
316 eq_scev_info (const void *e1
, const void *e2
)
318 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
319 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
321 return elt1
->var
== elt2
->var
;
324 /* Deletes database element E. */
327 del_scev_info (void *e
)
332 /* Get the index corresponding to VAR in the current LOOP. If
333 it's the first time we ask for this VAR, then we return
334 chrec_not_analyzed_yet for this VAR and return its index. */
337 find_var_scev_info (tree var
)
339 struct scev_info_str
*res
;
340 struct scev_info_str tmp
;
344 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
347 *slot
= new_scev_info_str (var
);
348 res
= (struct scev_info_str
*) *slot
;
353 /* Return true when CHREC contains symbolic names defined in
357 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
359 if (chrec
== NULL_TREE
)
362 if (TREE_INVARIANT (chrec
))
365 if (TREE_CODE (chrec
) == VAR_DECL
366 || TREE_CODE (chrec
) == PARM_DECL
367 || TREE_CODE (chrec
) == FUNCTION_DECL
368 || TREE_CODE (chrec
) == LABEL_DECL
369 || TREE_CODE (chrec
) == RESULT_DECL
370 || TREE_CODE (chrec
) == FIELD_DECL
)
373 if (TREE_CODE (chrec
) == SSA_NAME
)
375 tree def
= SSA_NAME_DEF_STMT (chrec
);
376 struct loop
*def_loop
= loop_containing_stmt (def
);
377 struct loop
*loop
= current_loops
->parray
[loop_nb
];
379 if (def_loop
== NULL
)
382 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
388 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
391 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 2),
396 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 1),
401 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 0),
410 /* Return true when PHI is a loop-phi-node. */
413 loop_phi_node_p (tree phi
)
415 /* The implementation of this function is based on the following
416 property: "all the loop-phi-nodes of a loop are contained in the
417 loop's header basic block". */
419 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
422 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
423 In general, in the case of multivariate evolutions we want to get
424 the evolution in different loops. LOOP specifies the level for
425 which to get the evolution.
429 | for (j = 0; j < 100; j++)
431 | for (k = 0; k < 100; k++)
433 | i = k + j; - Here the value of i is a function of j, k.
435 | ... = i - Here the value of i is a function of j.
437 | ... = i - Here the value of i is a scalar.
443 | i_1 = phi (i_0, i_2)
447 This loop has the same effect as:
448 LOOP_1 has the same effect as:
452 The overall effect of the loop, "i_0 + 20" in the previous example,
453 is obtained by passing in the parameters: LOOP = 1,
454 EVOLUTION_FN = {i_0, +, 2}_1.
458 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
462 if (evolution_fn
== chrec_dont_know
)
463 return chrec_dont_know
;
465 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
467 if (CHREC_VARIABLE (evolution_fn
) >= (unsigned) loop
->num
)
469 struct loop
*inner_loop
=
470 current_loops
->parray
[CHREC_VARIABLE (evolution_fn
)];
471 tree nb_iter
= number_of_iterations_in_loop (inner_loop
);
473 if (nb_iter
== chrec_dont_know
)
474 return chrec_dont_know
;
478 tree type
= chrec_type (nb_iter
);
480 /* Number of iterations is off by one (the ssa name we
481 analyze must be defined before the exit). */
482 nb_iter
= chrec_fold_minus (type
, nb_iter
,
483 build_int_cst (type
, 1));
485 /* evolution_fn is the evolution function in LOOP. Get
486 its value in the nb_iter-th iteration. */
487 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
489 /* Continue the computation until ending on a parent of LOOP. */
490 return compute_overall_effect_of_inner_loop (loop
, res
);
497 /* If the evolution function is an invariant, there is nothing to do. */
498 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
502 return chrec_dont_know
;
505 /* Determine whether the CHREC is always positive/negative. If the expression
506 cannot be statically analyzed, return false, otherwise set the answer into
510 chrec_is_positive (tree chrec
, bool *value
)
512 bool value0
, value1
, value2
;
513 tree type
, end_value
, nb_iter
;
515 switch (TREE_CODE (chrec
))
517 case POLYNOMIAL_CHREC
:
518 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
519 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
522 /* FIXME -- overflows. */
523 if (value0
== value1
)
529 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
530 and the proof consists in showing that the sign never
531 changes during the execution of the loop, from 0 to
532 loop->nb_iterations. */
533 if (!evolution_function_is_affine_p (chrec
))
536 nb_iter
= number_of_iterations_in_loop
537 (current_loops
->parray
[CHREC_VARIABLE (chrec
)]);
539 if (chrec_contains_undetermined (nb_iter
))
542 type
= chrec_type (nb_iter
);
543 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
546 /* TODO -- If the test is after the exit, we may decrease the number of
547 iterations by one. */
549 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
552 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
554 if (!chrec_is_positive (end_value
, &value2
))
558 return value0
== value1
;
561 *value
= (tree_int_cst_sgn (chrec
) == 1);
569 /* Associate CHREC to SCALAR. */
572 set_scalar_evolution (tree scalar
, tree chrec
)
576 if (TREE_CODE (scalar
) != SSA_NAME
)
579 scalar_info
= find_var_scev_info (scalar
);
583 if (dump_flags
& TDF_DETAILS
)
585 fprintf (dump_file
, "(set_scalar_evolution \n");
586 fprintf (dump_file
, " (scalar = ");
587 print_generic_expr (dump_file
, scalar
, 0);
588 fprintf (dump_file
, ")\n (scalar_evolution = ");
589 print_generic_expr (dump_file
, chrec
, 0);
590 fprintf (dump_file
, "))\n");
592 if (dump_flags
& TDF_STATS
)
596 *scalar_info
= chrec
;
599 /* Retrieve the chrec associated to SCALAR in the LOOP. */
602 get_scalar_evolution (tree scalar
)
608 if (dump_flags
& TDF_DETAILS
)
610 fprintf (dump_file
, "(get_scalar_evolution \n");
611 fprintf (dump_file
, " (scalar = ");
612 print_generic_expr (dump_file
, scalar
, 0);
613 fprintf (dump_file
, ")\n");
615 if (dump_flags
& TDF_STATS
)
619 switch (TREE_CODE (scalar
))
622 res
= *find_var_scev_info (scalar
);
631 res
= chrec_not_analyzed_yet
;
635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
637 fprintf (dump_file
, " (scalar_evolution = ");
638 print_generic_expr (dump_file
, res
, 0);
639 fprintf (dump_file
, "))\n");
645 /* Helper function for add_to_evolution. Returns the evolution
646 function for an assignment of the form "a = b + c", where "a" and
647 "b" are on the strongly connected component. CHREC_BEFORE is the
648 information that we already have collected up to this point.
649 TO_ADD is the evolution of "c".
651 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
652 evolution the expression TO_ADD, otherwise construct an evolution
653 part for this loop. */
656 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
659 tree type
, left
, right
;
661 switch (TREE_CODE (chrec_before
))
663 case POLYNOMIAL_CHREC
:
664 if (CHREC_VARIABLE (chrec_before
) <= loop_nb
)
668 type
= chrec_type (chrec_before
);
670 /* When there is no evolution part in this loop, build it. */
671 if (CHREC_VARIABLE (chrec_before
) < loop_nb
)
675 right
= SCALAR_FLOAT_TYPE_P (type
)
676 ? build_real (type
, dconst0
)
677 : build_int_cst (type
, 0);
681 var
= CHREC_VARIABLE (chrec_before
);
682 left
= CHREC_LEFT (chrec_before
);
683 right
= CHREC_RIGHT (chrec_before
);
686 to_add
= chrec_convert (type
, to_add
, at_stmt
);
687 right
= chrec_convert (type
, right
, at_stmt
);
688 right
= chrec_fold_plus (type
, right
, to_add
);
689 return build_polynomial_chrec (var
, left
, right
);
693 /* Search the evolution in LOOP_NB. */
694 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
696 right
= CHREC_RIGHT (chrec_before
);
697 right
= chrec_convert (chrec_type (left
), right
, at_stmt
);
698 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
703 /* These nodes do not depend on a loop. */
704 if (chrec_before
== chrec_dont_know
)
705 return chrec_dont_know
;
708 right
= chrec_convert (chrec_type (left
), to_add
, at_stmt
);
709 return build_polynomial_chrec (loop_nb
, left
, right
);
713 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
716 Description (provided for completeness, for those who read code in
717 a plane, and for my poor 62 bytes brain that would have forgotten
718 all this in the next two or three months):
720 The algorithm of translation of programs from the SSA representation
721 into the chrecs syntax is based on a pattern matching. After having
722 reconstructed the overall tree expression for a loop, there are only
723 two cases that can arise:
725 1. a = loop-phi (init, a + expr)
726 2. a = loop-phi (init, expr)
728 where EXPR is either a scalar constant with respect to the analyzed
729 loop (this is a degree 0 polynomial), or an expression containing
730 other loop-phi definitions (these are higher degree polynomials).
737 | a = phi (init, a + 5)
744 | a = phi (inita, 2 * b + 3)
745 | b = phi (initb, b + 1)
748 For the first case, the semantics of the SSA representation is:
750 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
752 that is, there is a loop index "x" that determines the scalar value
753 of the variable during the loop execution. During the first
754 iteration, the value is that of the initial condition INIT, while
755 during the subsequent iterations, it is the sum of the initial
756 condition with the sum of all the values of EXPR from the initial
757 iteration to the before last considered iteration.
759 For the second case, the semantics of the SSA program is:
761 | a (x) = init, if x = 0;
762 | expr (x - 1), otherwise.
764 The second case corresponds to the PEELED_CHREC, whose syntax is
765 close to the syntax of a loop-phi-node:
767 | phi (init, expr) vs. (init, expr)_x
769 The proof of the translation algorithm for the first case is a
770 proof by structural induction based on the degree of EXPR.
773 When EXPR is a constant with respect to the analyzed loop, or in
774 other words when EXPR is a polynomial of degree 0, the evolution of
775 the variable A in the loop is an affine function with an initial
776 condition INIT, and a step EXPR. In order to show this, we start
777 from the semantics of the SSA representation:
779 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
781 and since "expr (j)" is a constant with respect to "j",
783 f (x) = init + x * expr
785 Finally, based on the semantics of the pure sum chrecs, by
786 identification we get the corresponding chrecs syntax:
788 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
789 f (x) -> {init, +, expr}_x
792 Suppose that EXPR is a polynomial of degree N with respect to the
793 analyzed loop_x for which we have already determined that it is
794 written under the chrecs syntax:
796 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
798 We start from the semantics of the SSA program:
800 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
802 | f (x) = init + \sum_{j = 0}^{x - 1}
803 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
805 | f (x) = init + \sum_{j = 0}^{x - 1}
806 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
808 | f (x) = init + \sum_{k = 0}^{n - 1}
809 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
811 | f (x) = init + \sum_{k = 0}^{n - 1}
812 | (b_k * \binom{x}{k + 1})
814 | f (x) = init + b_0 * \binom{x}{1} + ...
815 | + b_{n-1} * \binom{x}{n}
817 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
818 | + b_{n-1} * \binom{x}{n}
821 And finally from the definition of the chrecs syntax, we identify:
822 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
824 This shows the mechanism that stands behind the add_to_evolution
825 function. An important point is that the use of symbolic
826 parameters avoids the need of an analysis schedule.
833 | a = phi (inita, a + 2 + b)
834 | b = phi (initb, b + 1)
837 When analyzing "a", the algorithm keeps "b" symbolically:
839 | a -> {inita, +, 2 + b}_1
841 Then, after instantiation, the analyzer ends on the evolution:
843 | a -> {inita, +, 2 + initb, +, 1}_1
848 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
849 tree to_add
, tree at_stmt
)
851 tree type
= chrec_type (to_add
);
852 tree res
= NULL_TREE
;
854 if (to_add
== NULL_TREE
)
857 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
858 instantiated at this point. */
859 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
860 /* This should not happen. */
861 return chrec_dont_know
;
863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
865 fprintf (dump_file
, "(add_to_evolution \n");
866 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
867 fprintf (dump_file
, " (chrec_before = ");
868 print_generic_expr (dump_file
, chrec_before
, 0);
869 fprintf (dump_file
, ")\n (to_add = ");
870 print_generic_expr (dump_file
, to_add
, 0);
871 fprintf (dump_file
, ")\n");
874 if (code
== MINUS_EXPR
)
875 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
876 ? build_real (type
, dconstm1
)
877 : build_int_cst_type (type
, -1));
879 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 fprintf (dump_file
, " (res = ");
884 print_generic_expr (dump_file
, res
, 0);
885 fprintf (dump_file
, "))\n");
891 /* Helper function. */
894 set_nb_iterations_in_loop (struct loop
*loop
,
897 tree type
= chrec_type (res
);
899 res
= chrec_fold_plus (type
, res
, build_int_cst (type
, 1));
901 /* FIXME HWI: However we want to store one iteration less than the
902 count of the loop in order to be compatible with the other
903 nb_iter computations in loop-iv. This also allows the
904 representation of nb_iters that are equal to MAX_INT. */
905 if (TREE_CODE (res
) == INTEGER_CST
906 && (TREE_INT_CST_LOW (res
) == 0
907 || TREE_OVERFLOW (res
)))
908 res
= chrec_dont_know
;
910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
912 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
913 print_generic_expr (dump_file
, res
, 0);
914 fprintf (dump_file
, "))\n");
917 loop
->nb_iterations
= res
;
923 /* This section selects the loops that will be good candidates for the
924 scalar evolution analysis. For the moment, greedily select all the
925 loop nests we could analyze. */
927 /* Return true when it is possible to analyze the condition expression
931 analyzable_condition (tree expr
)
935 if (TREE_CODE (expr
) != COND_EXPR
)
938 condition
= TREE_OPERAND (expr
, 0);
940 switch (TREE_CODE (condition
))
960 /* For a loop with a single exit edge, return the COND_EXPR that
961 guards the exit edge. If the expression is too difficult to
962 analyze, then give up. */
965 get_loop_exit_condition (struct loop
*loop
)
967 tree res
= NULL_TREE
;
968 edge exit_edge
= loop
->single_exit
;
971 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
972 fprintf (dump_file
, "(get_loop_exit_condition \n ");
978 expr
= last_stmt (exit_edge
->src
);
979 if (analyzable_condition (expr
))
983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 print_generic_expr (dump_file
, res
, 0);
986 fprintf (dump_file
, ")\n");
992 /* Recursively determine and enqueue the exit conditions for a loop. */
995 get_exit_conditions_rec (struct loop
*loop
,
996 VEC(tree
,heap
) **exit_conditions
)
1001 /* Recurse on the inner loops, then on the next (sibling) loops. */
1002 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
1003 get_exit_conditions_rec (loop
->next
, exit_conditions
);
1005 if (loop
->single_exit
)
1007 tree loop_condition
= get_loop_exit_condition (loop
);
1010 VEC_safe_push (tree
, heap
, *exit_conditions
, loop_condition
);
1014 /* Select the candidate loop nests for the analysis. This function
1015 initializes the EXIT_CONDITIONS array. */
1018 select_loops_exit_conditions (struct loops
*loops
,
1019 VEC(tree
,heap
) **exit_conditions
)
1021 struct loop
*function_body
= loops
->parray
[0];
1023 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
1027 /* Depth first search algorithm. */
1029 typedef enum t_bool
{
1036 static t_bool
follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*, int);
1038 /* Follow the ssa edge into the right hand side RHS of an assignment.
1039 Return true if the strongly connected component has been found. */
1042 follow_ssa_edge_in_rhs (struct loop
*loop
, tree at_stmt
, tree rhs
,
1043 tree halting_phi
, tree
*evolution_of_loop
, int limit
)
1045 t_bool res
= t_false
;
1047 tree type_rhs
= TREE_TYPE (rhs
);
1050 /* The RHS is one of the following cases:
1056 - other cases are not yet handled. */
1057 switch (TREE_CODE (rhs
))
1060 /* This assignment is under the form "a_1 = (cast) rhs. */
1061 res
= follow_ssa_edge_in_rhs (loop
, at_stmt
, TREE_OPERAND (rhs
, 0),
1062 halting_phi
, evolution_of_loop
, limit
);
1063 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
),
1064 *evolution_of_loop
, at_stmt
);
1068 /* This assignment is under the form "a_1 = 7". */
1073 /* This assignment is under the form: "a_1 = b_2". */
1074 res
= follow_ssa_edge
1075 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
, limit
);
1079 /* This case is under the form "rhs0 + rhs1". */
1080 rhs0
= TREE_OPERAND (rhs
, 0);
1081 rhs1
= TREE_OPERAND (rhs
, 1);
1082 STRIP_TYPE_NOPS (rhs0
);
1083 STRIP_TYPE_NOPS (rhs1
);
1085 if (TREE_CODE (rhs0
) == SSA_NAME
)
1087 if (TREE_CODE (rhs1
) == SSA_NAME
)
1089 /* Match an assignment under the form:
1091 evol
= *evolution_of_loop
;
1092 res
= follow_ssa_edge
1093 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1097 *evolution_of_loop
= add_to_evolution
1099 chrec_convert (type_rhs
, evol
, at_stmt
),
1100 PLUS_EXPR
, rhs1
, at_stmt
);
1102 else if (res
== t_false
)
1104 res
= follow_ssa_edge
1105 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1106 evolution_of_loop
, limit
);
1109 *evolution_of_loop
= add_to_evolution
1111 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1112 PLUS_EXPR
, rhs0
, at_stmt
);
1114 else if (res
== t_dont_know
)
1115 *evolution_of_loop
= chrec_dont_know
;
1118 else if (res
== t_dont_know
)
1119 *evolution_of_loop
= chrec_dont_know
;
1124 /* Match an assignment under the form:
1126 res
= follow_ssa_edge
1127 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1128 evolution_of_loop
, limit
);
1130 *evolution_of_loop
= add_to_evolution
1131 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1133 PLUS_EXPR
, rhs1
, at_stmt
);
1135 else if (res
== t_dont_know
)
1136 *evolution_of_loop
= chrec_dont_know
;
1140 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1142 /* Match an assignment under the form:
1144 res
= follow_ssa_edge
1145 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1146 evolution_of_loop
, limit
);
1148 *evolution_of_loop
= add_to_evolution
1149 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1151 PLUS_EXPR
, rhs0
, at_stmt
);
1153 else if (res
== t_dont_know
)
1154 *evolution_of_loop
= chrec_dont_know
;
1158 /* Otherwise, match an assignment under the form:
1160 /* And there is nothing to do. */
1166 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1167 rhs0
= TREE_OPERAND (rhs
, 0);
1168 rhs1
= TREE_OPERAND (rhs
, 1);
1169 STRIP_TYPE_NOPS (rhs0
);
1170 STRIP_TYPE_NOPS (rhs1
);
1172 if (TREE_CODE (rhs0
) == SSA_NAME
)
1174 /* Match an assignment under the form:
1176 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1177 evolution_of_loop
, limit
);
1179 *evolution_of_loop
= add_to_evolution
1180 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1181 MINUS_EXPR
, rhs1
, at_stmt
);
1183 else if (res
== t_dont_know
)
1184 *evolution_of_loop
= chrec_dont_know
;
1187 /* Otherwise, match an assignment under the form:
1189 /* And there is nothing to do. */
1196 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1197 It must be handled as a copy assignment of the form a_1 = a_2. */
1198 tree op0
= ASSERT_EXPR_VAR (rhs
);
1199 if (TREE_CODE (op0
) == SSA_NAME
)
1200 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1201 halting_phi
, evolution_of_loop
, limit
);
1216 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1219 backedge_phi_arg_p (tree phi
, int i
)
1221 edge e
= PHI_ARG_EDGE (phi
, i
);
1223 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1224 about updating it anywhere, and this should work as well most of the
1226 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1232 /* Helper function for one branch of the condition-phi-node. Return
1233 true if the strongly connected component has been found following
1236 static inline t_bool
1237 follow_ssa_edge_in_condition_phi_branch (int i
,
1241 tree
*evolution_of_branch
,
1242 tree init_cond
, int limit
)
1244 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1245 *evolution_of_branch
= chrec_dont_know
;
1247 /* Do not follow back edges (they must belong to an irreducible loop, which
1248 we really do not want to worry about). */
1249 if (backedge_phi_arg_p (condition_phi
, i
))
1252 if (TREE_CODE (branch
) == SSA_NAME
)
1254 *evolution_of_branch
= init_cond
;
1255 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1256 evolution_of_branch
, limit
);
1259 /* This case occurs when one of the condition branches sets
1260 the variable to a constant: i.e. a phi-node like
1261 "a_2 = PHI <a_7(5), 2(6)>;".
1263 FIXME: This case have to be refined correctly:
1264 in some cases it is possible to say something better than
1265 chrec_dont_know, for example using a wrap-around notation. */
1269 /* This function merges the branches of a condition-phi-node in a
1273 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1276 tree
*evolution_of_loop
, int limit
)
1279 tree init
= *evolution_of_loop
;
1280 tree evolution_of_branch
;
1281 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1283 &evolution_of_branch
,
1285 if (res
== t_false
|| res
== t_dont_know
)
1288 *evolution_of_loop
= evolution_of_branch
;
1290 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1292 /* Quickly give up when the evolution of one of the branches is
1294 if (*evolution_of_loop
== chrec_dont_know
)
1297 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1299 &evolution_of_branch
,
1301 if (res
== t_false
|| res
== t_dont_know
)
1304 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1305 evolution_of_branch
);
1311 /* Follow an SSA edge in an inner loop. It computes the overall
1312 effect of the loop, and following the symbolic initial conditions,
1313 it follows the edges in the parent loop. The inner loop is
1314 considered as a single statement. */
1317 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1320 tree
*evolution_of_loop
, int limit
)
1322 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1323 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1325 /* Sometimes, the inner loop is too difficult to analyze, and the
1326 result of the analysis is a symbolic parameter. */
1327 if (ev
== PHI_RESULT (loop_phi_node
))
1329 t_bool res
= t_false
;
1332 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1334 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1337 /* Follow the edges that exit the inner loop. */
1338 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1339 if (!flow_bb_inside_loop_p (loop
, bb
))
1340 res
= follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
,
1342 evolution_of_loop
, limit
);
1347 /* If the path crosses this loop-phi, give up. */
1349 *evolution_of_loop
= chrec_dont_know
;
1354 /* Otherwise, compute the overall effect of the inner loop. */
1355 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1356 return follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1357 evolution_of_loop
, limit
);
1360 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1361 path that is analyzed on the return walk. */
1364 follow_ssa_edge (struct loop
*loop
, tree def
, tree halting_phi
,
1365 tree
*evolution_of_loop
, int limit
)
1367 struct loop
*def_loop
;
1369 if (TREE_CODE (def
) == NOP_EXPR
)
1372 /* Give up if the path is longer than the MAX that we allow. */
1373 if (limit
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1376 def_loop
= loop_containing_stmt (def
);
1378 switch (TREE_CODE (def
))
1381 if (!loop_phi_node_p (def
))
1382 /* DEF is a condition-phi-node. Follow the branches, and
1383 record their evolutions. Finally, merge the collected
1384 information and set the approximation to the main
1386 return follow_ssa_edge_in_condition_phi
1387 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1389 /* When the analyzed phi is the halting_phi, the
1390 depth-first search is over: we have found a path from
1391 the halting_phi to itself in the loop. */
1392 if (def
== halting_phi
)
1395 /* Otherwise, the evolution of the HALTING_PHI depends
1396 on the evolution of another loop-phi-node, i.e. the
1397 evolution function is a higher degree polynomial. */
1398 if (def_loop
== loop
)
1402 if (flow_loop_nested_p (loop
, def_loop
))
1403 return follow_ssa_edge_inner_loop_phi
1404 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1410 return follow_ssa_edge_in_rhs (loop
, def
,
1411 TREE_OPERAND (def
, 1),
1413 evolution_of_loop
, limit
);
1416 /* At this level of abstraction, the program is just a set
1417 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1418 other node to be handled. */
1425 /* Given a LOOP_PHI_NODE, this function determines the evolution
1426 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1429 analyze_evolution_in_loop (tree loop_phi_node
,
1433 tree evolution_function
= chrec_not_analyzed_yet
;
1434 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1439 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1440 fprintf (dump_file
, " (loop_phi_node = ");
1441 print_generic_expr (dump_file
, loop_phi_node
, 0);
1442 fprintf (dump_file
, ")\n");
1445 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1447 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1448 tree ssa_chain
, ev_fn
;
1451 /* Select the edges that enter the loop body. */
1452 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1453 if (!flow_bb_inside_loop_p (loop
, bb
))
1456 if (TREE_CODE (arg
) == SSA_NAME
)
1458 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1460 /* Pass in the initial condition to the follow edge function. */
1462 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1467 /* When it is impossible to go back on the same
1468 loop_phi_node by following the ssa edges, the
1469 evolution is represented by a peeled chrec, i.e. the
1470 first iteration, EV_FN has the value INIT_COND, then
1471 all the other iterations it has the value of ARG.
1472 For the moment, PEELED_CHREC nodes are not built. */
1474 ev_fn
= chrec_dont_know
;
1476 /* When there are multiple back edges of the loop (which in fact never
1477 happens currently, but nevertheless), merge their evolutions. */
1478 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1483 fprintf (dump_file
, " (evolution_function = ");
1484 print_generic_expr (dump_file
, evolution_function
, 0);
1485 fprintf (dump_file
, "))\n");
1488 return evolution_function
;
1491 /* Given a loop-phi-node, return the initial conditions of the
1492 variable on entry of the loop. When the CCP has propagated
1493 constants into the loop-phi-node, the initial condition is
1494 instantiated, otherwise the initial condition is kept symbolic.
1495 This analyzer does not analyze the evolution outside the current
1496 loop, and leaves this task to the on-demand tree reconstructor. */
1499 analyze_initial_condition (tree loop_phi_node
)
1502 tree init_cond
= chrec_not_analyzed_yet
;
1503 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1505 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1507 fprintf (dump_file
, "(analyze_initial_condition \n");
1508 fprintf (dump_file
, " (loop_phi_node = \n");
1509 print_generic_expr (dump_file
, loop_phi_node
, 0);
1510 fprintf (dump_file
, ")\n");
1513 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1515 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1516 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1518 /* When the branch is oriented to the loop's body, it does
1519 not contribute to the initial condition. */
1520 if (flow_bb_inside_loop_p (loop
, bb
))
1523 if (init_cond
== chrec_not_analyzed_yet
)
1529 if (TREE_CODE (branch
) == SSA_NAME
)
1531 init_cond
= chrec_dont_know
;
1535 init_cond
= chrec_merge (init_cond
, branch
);
1538 /* Ooops -- a loop without an entry??? */
1539 if (init_cond
== chrec_not_analyzed_yet
)
1540 init_cond
= chrec_dont_know
;
1542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1544 fprintf (dump_file
, " (init_cond = ");
1545 print_generic_expr (dump_file
, init_cond
, 0);
1546 fprintf (dump_file
, "))\n");
1552 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1555 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1558 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1561 if (phi_loop
!= loop
)
1563 struct loop
*subloop
;
1564 tree evolution_fn
= analyze_scalar_evolution
1565 (phi_loop
, PHI_RESULT (loop_phi_node
));
1567 /* Dive one level deeper. */
1568 subloop
= superloop_at_depth (phi_loop
, loop
->depth
+ 1);
1570 /* Interpret the subloop. */
1571 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1575 /* Otherwise really interpret the loop phi. */
1576 init_cond
= analyze_initial_condition (loop_phi_node
);
1577 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1582 /* This function merges the branches of a condition-phi-node,
1583 contained in the outermost loop, and whose arguments are already
1587 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1590 tree res
= chrec_not_analyzed_yet
;
1592 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1596 if (backedge_phi_arg_p (condition_phi
, i
))
1598 res
= chrec_dont_know
;
1602 branch_chrec
= analyze_scalar_evolution
1603 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1605 res
= chrec_merge (res
, branch_chrec
);
1611 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1612 analyze this node before, follow the definitions until ending
1613 either on an analyzed modify_expr, or on a loop-phi-node. On the
1614 return path, this function propagates evolutions (ala constant copy
1615 propagation). OPND1 is not a GIMPLE expression because we could
1616 analyze the effect of an inner loop: see interpret_loop_phi. */
1619 interpret_rhs_modify_expr (struct loop
*loop
, tree at_stmt
,
1620 tree opnd1
, tree type
)
1622 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1624 if (is_gimple_min_invariant (opnd1
))
1625 return chrec_convert (type
, opnd1
, at_stmt
);
1627 switch (TREE_CODE (opnd1
))
1630 opnd10
= TREE_OPERAND (opnd1
, 0);
1631 opnd11
= TREE_OPERAND (opnd1
, 1);
1632 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1633 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1634 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1635 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1636 res
= chrec_fold_plus (type
, chrec10
, chrec11
);
1640 opnd10
= TREE_OPERAND (opnd1
, 0);
1641 opnd11
= TREE_OPERAND (opnd1
, 1);
1642 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1643 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1644 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1645 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1646 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1650 opnd10
= TREE_OPERAND (opnd1
, 0);
1651 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1652 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1653 /* TYPE may be integer, real or complex, so use fold_convert. */
1654 res
= chrec_fold_multiply (type
, chrec10
,
1655 fold_convert (type
, integer_minus_one_node
));
1659 opnd10
= TREE_OPERAND (opnd1
, 0);
1660 opnd11
= TREE_OPERAND (opnd1
, 1);
1661 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1662 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1663 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1664 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1665 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1669 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
),
1674 opnd10
= ASSERT_EXPR_VAR (opnd1
);
1675 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd10
),
1681 opnd10
= TREE_OPERAND (opnd1
, 0);
1682 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1683 res
= chrec_convert (type
, chrec10
, at_stmt
);
1687 res
= chrec_dont_know
;
1696 /* This section contains all the entry points:
1697 - number_of_iterations_in_loop,
1698 - analyze_scalar_evolution,
1699 - instantiate_parameters.
1702 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1703 common ancestor of DEF_LOOP and USE_LOOP. */
1706 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1707 struct loop
*def_loop
,
1711 if (def_loop
== wrto_loop
)
1714 def_loop
= superloop_at_depth (def_loop
, wrto_loop
->depth
+ 1);
1715 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1717 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1720 /* Folds EXPR, if it is a cast to pointer, assuming that the created
1721 polynomial_chrec does not wrap. */
1724 fold_used_pointer_cast (tree expr
)
1727 tree type
, inner_type
;
1729 if (TREE_CODE (expr
) != NOP_EXPR
&& TREE_CODE (expr
) != CONVERT_EXPR
)
1732 op
= TREE_OPERAND (expr
, 0);
1733 if (TREE_CODE (op
) != POLYNOMIAL_CHREC
)
1736 type
= TREE_TYPE (expr
);
1737 inner_type
= TREE_TYPE (op
);
1739 if (!INTEGRAL_TYPE_P (inner_type
)
1740 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (type
))
1743 return build_polynomial_chrec (CHREC_VARIABLE (op
),
1744 chrec_convert (type
, CHREC_LEFT (op
), NULL_TREE
),
1745 chrec_convert (type
, CHREC_RIGHT (op
), NULL_TREE
));
1748 /* Returns true if EXPR is an expression corresponding to offset of pointer
1752 pointer_offset_p (tree expr
)
1754 if (TREE_CODE (expr
) == INTEGER_CST
)
1757 if ((TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1758 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0))))
1764 /* EXPR is a scalar evolution of a pointer that is dereferenced or used in
1765 comparison. This means that it must point to a part of some object in
1766 memory, which enables us to argue about overflows and possibly simplify
1767 the EXPR. AT_STMT is the statement in which this conversion has to be
1768 performed. Returns the simplified value.
1775 for (i = -n; i < n; i++)
1778 We generate the following code (assuming that size of int and size_t is
1781 for (i = -n; i < n; i++)
1786 tmp1 = (size_t) i; (1)
1787 tmp2 = 4 * tmp1; (2)
1788 tmp3 = (int *) tmp2; (3)
1789 tmp4 = p + tmp3; (4)
1794 We in general assume that pointer arithmetics does not overflow (since its
1795 behavior is undefined in that case). One of the problems is that our
1796 translation does not capture this property very well -- (int *) is
1797 considered unsigned, hence the computation in (4) does overflow if i is
1800 This impreciseness creates complications in scev analysis. The scalar
1801 evolution of i is [-n, +, 1]. Since int and size_t have the same precision
1802 (in this example), and size_t is unsigned (so we do not care about
1803 overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
1804 and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into
1805 problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
1806 places assume that this is not the case for scevs with pointer type, we
1807 cannot use this scev for tmp3; hence, its scev is
1808 (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
1809 p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to
1810 work with scevs of this shape.
1812 However, since tmp4 is dereferenced, all its values must belong to a single
1813 object, and taking into account that the precision of int * and size_t is
1814 the same, it is impossible for its scev to wrap. Hence, we can derive that
1815 its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
1818 ??? Maybe we should use different representation for pointer arithmetics,
1819 however that is a long-term project with a lot of potential for creating
1823 fold_used_pointer (tree expr
, tree at_stmt
)
1825 tree op0
, op1
, new0
, new1
;
1826 enum tree_code code
= TREE_CODE (expr
);
1828 if (code
== PLUS_EXPR
1829 || code
== MINUS_EXPR
)
1831 op0
= TREE_OPERAND (expr
, 0);
1832 op1
= TREE_OPERAND (expr
, 1);
1834 if (pointer_offset_p (op1
))
1836 new0
= fold_used_pointer (op0
, at_stmt
);
1837 new1
= fold_used_pointer_cast (op1
);
1839 else if (code
== PLUS_EXPR
&& pointer_offset_p (op0
))
1841 new0
= fold_used_pointer_cast (op0
);
1842 new1
= fold_used_pointer (op1
, at_stmt
);
1847 if (new0
== op0
&& new1
== op1
)
1850 new0
= chrec_convert (TREE_TYPE (expr
), new0
, at_stmt
);
1851 new1
= chrec_convert (TREE_TYPE (expr
), new1
, at_stmt
);
1853 if (code
== PLUS_EXPR
)
1854 expr
= chrec_fold_plus (TREE_TYPE (expr
), new0
, new1
);
1856 expr
= chrec_fold_minus (TREE_TYPE (expr
), new0
, new1
);
1861 return fold_used_pointer_cast (expr
);
1864 /* Returns true if PTR is dereferenced, or used in comparison. */
1867 pointer_used_p (tree ptr
)
1869 use_operand_p use_p
;
1870 imm_use_iterator imm_iter
;
1872 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
1873 var_ann_t v_ann
= var_ann (SSA_NAME_VAR (ptr
));
1875 /* Check whether the pointer has a memory tag; if it does, it is
1876 (or at least used to be) dereferenced. */
1877 if ((pi
!= NULL
&& pi
->name_mem_tag
!= NULL
)
1878 || v_ann
->symbol_mem_tag
)
1881 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, ptr
)
1883 stmt
= USE_STMT (use_p
);
1884 if (TREE_CODE (stmt
) == COND_EXPR
)
1887 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1890 rhs
= TREE_OPERAND (stmt
, 1);
1891 if (!COMPARISON_CLASS_P (rhs
))
1894 if (TREE_OPERAND (stmt
, 0) == ptr
1895 || TREE_OPERAND (stmt
, 1) == ptr
)
1902 /* Helper recursive function. */
1905 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1907 tree def
, type
= TREE_TYPE (var
);
1909 struct loop
*def_loop
;
1911 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1912 return chrec_dont_know
;
1914 if (TREE_CODE (var
) != SSA_NAME
)
1915 return interpret_rhs_modify_expr (loop
, NULL_TREE
, var
, type
);
1917 def
= SSA_NAME_DEF_STMT (var
);
1918 bb
= bb_for_stmt (def
);
1919 def_loop
= bb
? bb
->loop_father
: NULL
;
1922 || !flow_bb_inside_loop_p (loop
, bb
))
1924 /* Keep the symbolic form. */
1929 if (res
!= chrec_not_analyzed_yet
)
1931 if (loop
!= bb
->loop_father
)
1932 res
= compute_scalar_evolution_in_loop
1933 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1938 if (loop
!= def_loop
)
1940 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1941 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1946 switch (TREE_CODE (def
))
1949 res
= interpret_rhs_modify_expr (loop
, def
, TREE_OPERAND (def
, 1), type
);
1951 if (POINTER_TYPE_P (type
)
1952 && !automatically_generated_chrec_p (res
)
1953 && pointer_used_p (var
))
1954 res
= fold_used_pointer (res
, def
);
1958 if (loop_phi_node_p (def
))
1959 res
= interpret_loop_phi (loop
, def
);
1961 res
= interpret_condition_phi (loop
, def
);
1965 res
= chrec_dont_know
;
1971 /* Keep the symbolic form. */
1972 if (res
== chrec_dont_know
)
1975 if (loop
== def_loop
)
1976 set_scalar_evolution (var
, res
);
1981 /* Entry point for the scalar evolution analyzer.
1982 Analyzes and returns the scalar evolution of the ssa_name VAR.
1983 LOOP_NB is the identifier number of the loop in which the variable
1986 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1987 pointer to the statement that uses this variable, in order to
1988 determine the evolution function of the variable, use the following
1991 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1992 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1993 tree chrec_instantiated = instantiate_parameters
1994 (loop_nb, chrec_with_symbols);
1998 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2004 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2005 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2006 fprintf (dump_file
, " (scalar = ");
2007 print_generic_expr (dump_file
, var
, 0);
2008 fprintf (dump_file
, ")\n");
2011 res
= analyze_scalar_evolution_1 (loop
, var
, get_scalar_evolution (var
));
2013 if (TREE_CODE (var
) == SSA_NAME
&& res
== chrec_dont_know
)
2016 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2017 fprintf (dump_file
, ")\n");
2022 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2023 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
2026 FOLDED_CASTS is set to true if resolve_mixers used
2027 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2028 at the moment in order to keep things simple). */
2031 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2032 tree version
, bool *folded_casts
)
2035 tree ev
= version
, tmp
;
2038 *folded_casts
= false;
2041 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2042 ev
= resolve_mixers (use_loop
, tmp
);
2044 if (folded_casts
&& tmp
!= ev
)
2045 *folded_casts
= true;
2047 if (use_loop
== wrto_loop
)
2050 /* If the value of the use changes in the inner loop, we cannot express
2051 its value in the outer loop (we might try to return interval chrec,
2052 but we do not have a user for it anyway) */
2053 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2055 return chrec_dont_know
;
2057 use_loop
= use_loop
->outer
;
2061 /* Returns instantiated value for VERSION in CACHE. */
2064 get_instantiated_value (htab_t cache
, tree version
)
2066 struct scev_info_str
*info
, pattern
;
2068 pattern
.var
= version
;
2069 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2077 /* Sets instantiated value for VERSION to VAL in CACHE. */
2080 set_instantiated_value (htab_t cache
, tree version
, tree val
)
2082 struct scev_info_str
*info
, pattern
;
2085 pattern
.var
= version
;
2086 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2089 *slot
= new_scev_info_str (version
);
2090 info
= (struct scev_info_str
*) *slot
;
2094 /* Return the closed_loop_phi node for VAR. If there is none, return
2098 loop_closed_phi_def (tree var
)
2104 if (var
== NULL_TREE
2105 || TREE_CODE (var
) != SSA_NAME
)
2108 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2109 exit
= loop
->single_exit
;
2113 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
2114 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2115 return PHI_RESULT (phi
);
2120 /* Analyze all the parameters of the chrec that were left under a symbolic form,
2121 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
2122 of already instantiated values. FLAGS modify the way chrecs are
2123 instantiated. SIZE_EXPR is used for computing the size of the expression to
2124 be instantiated, and to stop if it exceeds some limit. */
2126 /* Values for FLAGS. */
2129 INSERT_SUPERLOOP_CHRECS
= 1, /* Loop invariants are replaced with chrecs
2131 FOLD_CONVERSIONS
= 2 /* The conversions that may wrap in
2132 signed/pointer type are folded, as long as the
2133 value of the chrec is preserved. */
2137 instantiate_parameters_1 (struct loop
*loop
, tree chrec
, int flags
, htab_t cache
,
2140 tree res
, op0
, op1
, op2
;
2142 struct loop
*def_loop
;
2143 tree type
= chrec_type (chrec
);
2145 /* Give up if the expression is larger than the MAX that we allow. */
2146 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2147 return chrec_dont_know
;
2149 if (automatically_generated_chrec_p (chrec
)
2150 || is_gimple_min_invariant (chrec
))
2153 switch (TREE_CODE (chrec
))
2156 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
2158 /* A parameter (or loop invariant and we do not want to include
2159 evolutions in outer loops), nothing to do. */
2161 || (!(flags
& INSERT_SUPERLOOP_CHRECS
)
2162 && !flow_bb_inside_loop_p (loop
, def_bb
)))
2165 /* We cache the value of instantiated variable to avoid exponential
2166 time complexity due to reevaluations. We also store the convenient
2167 value in the cache in order to prevent infinite recursion -- we do
2168 not want to instantiate the SSA_NAME if it is in a mixer
2169 structure. This is used for avoiding the instantiation of
2170 recursively defined functions, such as:
2172 | a_2 -> {0, +, 1, +, a_2}_1 */
2174 res
= get_instantiated_value (cache
, chrec
);
2178 /* Store the convenient value for chrec in the structure. If it
2179 is defined outside of the loop, we may just leave it in symbolic
2180 form, otherwise we need to admit that we do not know its behavior
2182 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
2183 set_instantiated_value (cache
, chrec
, res
);
2185 /* To make things even more complicated, instantiate_parameters_1
2186 calls analyze_scalar_evolution that may call # of iterations
2187 analysis that may in turn call instantiate_parameters_1 again.
2188 To prevent the infinite recursion, keep also the bitmap of
2189 ssa names that are being instantiated globally. */
2190 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
2193 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
2195 /* If the analysis yields a parametric chrec, instantiate the
2197 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2198 res
= analyze_scalar_evolution (def_loop
, chrec
);
2200 /* Don't instantiate loop-closed-ssa phi nodes. */
2201 if (TREE_CODE (res
) == SSA_NAME
2202 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2203 || (loop_containing_stmt (SSA_NAME_DEF_STMT (res
))->depth
2204 > def_loop
->depth
)))
2207 res
= loop_closed_phi_def (chrec
);
2211 if (res
== NULL_TREE
)
2212 res
= chrec_dont_know
;
2215 else if (res
!= chrec_dont_know
)
2216 res
= instantiate_parameters_1 (loop
, res
, flags
, cache
, size_expr
);
2218 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2220 /* Store the correct value to the cache. */
2221 set_instantiated_value (cache
, chrec
, res
);
2224 case POLYNOMIAL_CHREC
:
2225 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2226 flags
, cache
, size_expr
);
2227 if (op0
== chrec_dont_know
)
2228 return chrec_dont_know
;
2230 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2231 flags
, cache
, size_expr
);
2232 if (op1
== chrec_dont_know
)
2233 return chrec_dont_know
;
2235 if (CHREC_LEFT (chrec
) != op0
2236 || CHREC_RIGHT (chrec
) != op1
)
2238 op1
= chrec_convert (chrec_type (op0
), op1
, NULL_TREE
);
2239 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2244 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2245 flags
, cache
, size_expr
);
2246 if (op0
== chrec_dont_know
)
2247 return chrec_dont_know
;
2249 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2250 flags
, cache
, size_expr
);
2251 if (op1
== chrec_dont_know
)
2252 return chrec_dont_know
;
2254 if (TREE_OPERAND (chrec
, 0) != op0
2255 || TREE_OPERAND (chrec
, 1) != op1
)
2257 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2258 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2259 chrec
= chrec_fold_plus (type
, op0
, op1
);
2264 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2265 flags
, cache
, size_expr
);
2266 if (op0
== chrec_dont_know
)
2267 return chrec_dont_know
;
2269 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2270 flags
, cache
, size_expr
);
2271 if (op1
== chrec_dont_know
)
2272 return chrec_dont_know
;
2274 if (TREE_OPERAND (chrec
, 0) != op0
2275 || TREE_OPERAND (chrec
, 1) != op1
)
2277 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2278 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2279 chrec
= chrec_fold_minus (type
, op0
, op1
);
2284 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2285 flags
, cache
, size_expr
);
2286 if (op0
== chrec_dont_know
)
2287 return chrec_dont_know
;
2289 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2290 flags
, cache
, size_expr
);
2291 if (op1
== chrec_dont_know
)
2292 return chrec_dont_know
;
2294 if (TREE_OPERAND (chrec
, 0) != op0
2295 || TREE_OPERAND (chrec
, 1) != op1
)
2297 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2298 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2299 chrec
= chrec_fold_multiply (type
, op0
, op1
);
2305 case NON_LVALUE_EXPR
:
2306 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2307 flags
, cache
, size_expr
);
2308 if (op0
== chrec_dont_know
)
2309 return chrec_dont_know
;
2311 if (flags
& FOLD_CONVERSIONS
)
2313 tree tmp
= chrec_convert_aggressive (TREE_TYPE (chrec
), op0
);
2318 if (op0
== TREE_OPERAND (chrec
, 0))
2321 /* If we used chrec_convert_aggressive, we can no longer assume that
2322 signed chrecs do not overflow, as chrec_convert does, so avoid
2323 calling it in that case. */
2324 if (flags
& FOLD_CONVERSIONS
)
2325 return fold_convert (TREE_TYPE (chrec
), op0
);
2327 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL_TREE
);
2329 case SCEV_NOT_KNOWN
:
2330 return chrec_dont_know
;
2339 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2342 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2343 flags
, cache
, size_expr
);
2344 if (op0
== chrec_dont_know
)
2345 return chrec_dont_know
;
2347 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2348 flags
, cache
, size_expr
);
2349 if (op1
== chrec_dont_know
)
2350 return chrec_dont_know
;
2352 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2353 flags
, cache
, size_expr
);
2354 if (op2
== chrec_dont_know
)
2355 return chrec_dont_know
;
2357 if (op0
== TREE_OPERAND (chrec
, 0)
2358 && op1
== TREE_OPERAND (chrec
, 1)
2359 && op2
== TREE_OPERAND (chrec
, 2))
2362 return fold_build3 (TREE_CODE (chrec
),
2363 TREE_TYPE (chrec
), op0
, op1
, op2
);
2366 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2367 flags
, cache
, size_expr
);
2368 if (op0
== chrec_dont_know
)
2369 return chrec_dont_know
;
2371 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2372 flags
, cache
, size_expr
);
2373 if (op1
== chrec_dont_know
)
2374 return chrec_dont_know
;
2376 if (op0
== TREE_OPERAND (chrec
, 0)
2377 && op1
== TREE_OPERAND (chrec
, 1))
2379 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2382 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2383 flags
, cache
, size_expr
);
2384 if (op0
== chrec_dont_know
)
2385 return chrec_dont_know
;
2386 if (op0
== TREE_OPERAND (chrec
, 0))
2388 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2397 /* Too complicated to handle. */
2398 return chrec_dont_know
;
2401 /* Analyze all the parameters of the chrec that were left under a
2402 symbolic form. LOOP is the loop in which symbolic names have to
2403 be analyzed and instantiated. */
2406 instantiate_parameters (struct loop
*loop
,
2410 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2412 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2414 fprintf (dump_file
, "(instantiate_parameters \n");
2415 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2416 fprintf (dump_file
, " (chrec = ");
2417 print_generic_expr (dump_file
, chrec
, 0);
2418 fprintf (dump_file
, ")\n");
2421 res
= instantiate_parameters_1 (loop
, chrec
, INSERT_SUPERLOOP_CHRECS
, cache
,
2424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2426 fprintf (dump_file
, " (res = ");
2427 print_generic_expr (dump_file
, res
, 0);
2428 fprintf (dump_file
, "))\n");
2431 htab_delete (cache
);
2436 /* Similar to instantiate_parameters, but does not introduce the
2437 evolutions in outer loops for LOOP invariants in CHREC, and does not
2438 care about causing overflows, as long as they do not affect value
2439 of an expression. */
2442 resolve_mixers (struct loop
*loop
, tree chrec
)
2444 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2445 tree ret
= instantiate_parameters_1 (loop
, chrec
, FOLD_CONVERSIONS
, cache
, 0);
2446 htab_delete (cache
);
2450 /* Entry point for the analysis of the number of iterations pass.
2451 This function tries to safely approximate the number of iterations
2452 the loop will run. When this property is not decidable at compile
2453 time, the result is chrec_dont_know. Otherwise the result is
2454 a scalar or a symbolic parameter.
2456 Example of analysis: suppose that the loop has an exit condition:
2458 "if (b > 49) goto end_loop;"
2460 and that in a previous analysis we have determined that the
2461 variable 'b' has an evolution function:
2463 "EF = {23, +, 5}_2".
2465 When we evaluate the function at the point 5, i.e. the value of the
2466 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2467 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2468 the loop body has been executed 6 times. */
2471 number_of_iterations_in_loop (struct loop
*loop
)
2475 struct tree_niter_desc niter_desc
;
2477 /* Determine whether the number_of_iterations_in_loop has already
2479 res
= loop
->nb_iterations
;
2482 res
= chrec_dont_know
;
2484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2485 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2487 exit
= loop
->single_exit
;
2491 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2494 type
= TREE_TYPE (niter_desc
.niter
);
2495 if (integer_nonzerop (niter_desc
.may_be_zero
))
2496 res
= build_int_cst (type
, 0);
2497 else if (integer_zerop (niter_desc
.may_be_zero
))
2498 res
= niter_desc
.niter
;
2500 res
= chrec_dont_know
;
2503 return set_nb_iterations_in_loop (loop
, res
);
2506 /* One of the drivers for testing the scalar evolutions analysis.
2507 This function computes the number of iterations for all the loops
2508 from the EXIT_CONDITIONS array. */
2511 number_of_iterations_for_all_loops (VEC(tree
,heap
) **exit_conditions
)
2514 unsigned nb_chrec_dont_know_loops
= 0;
2515 unsigned nb_static_loops
= 0;
2518 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2520 tree res
= number_of_iterations_in_loop (loop_containing_stmt (cond
));
2521 if (chrec_contains_undetermined (res
))
2522 nb_chrec_dont_know_loops
++;
2529 fprintf (dump_file
, "\n(\n");
2530 fprintf (dump_file
, "-----------------------------------------\n");
2531 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2532 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2533 fprintf (dump_file
, "%d\tnb_total_loops\n", current_loops
->num
);
2534 fprintf (dump_file
, "-----------------------------------------\n");
2535 fprintf (dump_file
, ")\n\n");
2537 print_loop_ir (dump_file
);
2543 /* Counters for the stats. */
2549 unsigned nb_affine_multivar
;
2550 unsigned nb_higher_poly
;
2551 unsigned nb_chrec_dont_know
;
2552 unsigned nb_undetermined
;
2555 /* Reset the counters. */
2558 reset_chrecs_counters (struct chrec_stats
*stats
)
2560 stats
->nb_chrecs
= 0;
2561 stats
->nb_affine
= 0;
2562 stats
->nb_affine_multivar
= 0;
2563 stats
->nb_higher_poly
= 0;
2564 stats
->nb_chrec_dont_know
= 0;
2565 stats
->nb_undetermined
= 0;
2568 /* Dump the contents of a CHREC_STATS structure. */
2571 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2573 fprintf (file
, "\n(\n");
2574 fprintf (file
, "-----------------------------------------\n");
2575 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2576 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2577 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2578 stats
->nb_higher_poly
);
2579 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2580 fprintf (file
, "-----------------------------------------\n");
2581 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2582 fprintf (file
, "%d\twith undetermined coefficients\n",
2583 stats
->nb_undetermined
);
2584 fprintf (file
, "-----------------------------------------\n");
2585 fprintf (file
, "%d\tchrecs in the scev database\n",
2586 (int) htab_elements (scalar_evolution_info
));
2587 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2588 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2589 fprintf (file
, "-----------------------------------------\n");
2590 fprintf (file
, ")\n\n");
2593 /* Gather statistics about CHREC. */
2596 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2598 if (dump_file
&& (dump_flags
& TDF_STATS
))
2600 fprintf (dump_file
, "(classify_chrec ");
2601 print_generic_expr (dump_file
, chrec
, 0);
2602 fprintf (dump_file
, "\n");
2607 if (chrec
== NULL_TREE
)
2609 stats
->nb_undetermined
++;
2613 switch (TREE_CODE (chrec
))
2615 case POLYNOMIAL_CHREC
:
2616 if (evolution_function_is_affine_p (chrec
))
2618 if (dump_file
&& (dump_flags
& TDF_STATS
))
2619 fprintf (dump_file
, " affine_univariate\n");
2622 else if (evolution_function_is_affine_multivariate_p (chrec
))
2624 if (dump_file
&& (dump_flags
& TDF_STATS
))
2625 fprintf (dump_file
, " affine_multivariate\n");
2626 stats
->nb_affine_multivar
++;
2630 if (dump_file
&& (dump_flags
& TDF_STATS
))
2631 fprintf (dump_file
, " higher_degree_polynomial\n");
2632 stats
->nb_higher_poly
++;
2641 if (chrec_contains_undetermined (chrec
))
2643 if (dump_file
&& (dump_flags
& TDF_STATS
))
2644 fprintf (dump_file
, " undetermined\n");
2645 stats
->nb_undetermined
++;
2648 if (dump_file
&& (dump_flags
& TDF_STATS
))
2649 fprintf (dump_file
, ")\n");
2652 /* One of the drivers for testing the scalar evolutions analysis.
2653 This function analyzes the scalar evolution of all the scalars
2654 defined as loop phi nodes in one of the loops from the
2655 EXIT_CONDITIONS array.
2657 TODO Optimization: A loop is in canonical form if it contains only
2658 a single scalar loop phi node. All the other scalars that have an
2659 evolution in the loop are rewritten in function of this single
2660 index. This allows the parallelization of the loop. */
2663 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree
,heap
) **exit_conditions
)
2666 struct chrec_stats stats
;
2669 reset_chrecs_counters (&stats
);
2671 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2677 loop
= loop_containing_stmt (cond
);
2680 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2681 if (is_gimple_reg (PHI_RESULT (phi
)))
2683 chrec
= instantiate_parameters
2685 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2687 if (dump_file
&& (dump_flags
& TDF_STATS
))
2688 gather_chrec_stats (chrec
, &stats
);
2692 if (dump_file
&& (dump_flags
& TDF_STATS
))
2693 dump_chrecs_stats (dump_file
, &stats
);
2696 /* Callback for htab_traverse, gathers information on chrecs in the
2700 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2702 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2704 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2709 /* Classify the chrecs of the whole database. */
2712 gather_stats_on_scev_database (void)
2714 struct chrec_stats stats
;
2719 reset_chrecs_counters (&stats
);
2721 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2724 dump_chrecs_stats (dump_file
, &stats
);
2732 initialize_scalar_evolutions_analyzer (void)
2734 /* The elements below are unique. */
2735 if (chrec_dont_know
== NULL_TREE
)
2737 chrec_not_analyzed_yet
= NULL_TREE
;
2738 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2739 chrec_known
= make_node (SCEV_KNOWN
);
2740 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2741 TREE_TYPE (chrec_known
) = void_type_node
;
2745 /* Initialize the analysis of scalar evolutions for LOOPS. */
2748 scev_initialize (struct loops
*loops
)
2751 current_loops
= loops
;
2753 scalar_evolution_info
= htab_create (100, hash_scev_info
,
2754 eq_scev_info
, del_scev_info
);
2755 already_instantiated
= BITMAP_ALLOC (NULL
);
2757 initialize_scalar_evolutions_analyzer ();
2759 for (i
= 1; i
< loops
->num
; i
++)
2760 if (loops
->parray
[i
])
2761 loops
->parray
[i
]->nb_iterations
= NULL_TREE
;
2764 /* Cleans up the information cached by the scalar evolutions analysis. */
2772 if (!scalar_evolution_info
|| !current_loops
)
2775 htab_empty (scalar_evolution_info
);
2776 for (i
= 1; i
< current_loops
->num
; i
++)
2778 loop
= current_loops
->parray
[i
];
2780 loop
->nb_iterations
= NULL_TREE
;
2784 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2785 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2786 want step to be invariant in LOOP. Otherwise we require it to be an
2787 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2788 overflow (e.g. because it is computed in signed arithmetics). */
2791 simple_iv (struct loop
*loop
, tree stmt
, tree op
, affine_iv
*iv
,
2792 bool allow_nonconstant_step
)
2794 basic_block bb
= bb_for_stmt (stmt
);
2798 iv
->base
= NULL_TREE
;
2799 iv
->step
= NULL_TREE
;
2800 iv
->no_overflow
= false;
2802 type
= TREE_TYPE (op
);
2803 if (TREE_CODE (type
) != INTEGER_TYPE
2804 && TREE_CODE (type
) != POINTER_TYPE
)
2807 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
,
2809 if (chrec_contains_undetermined (ev
))
2812 if (tree_does_not_contain_chrecs (ev
)
2813 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2816 iv
->no_overflow
= true;
2820 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2821 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2824 iv
->step
= CHREC_RIGHT (ev
);
2825 if (allow_nonconstant_step
)
2827 if (tree_contains_chrecs (iv
->step
, NULL
)
2828 || chrec_contains_symbols_defined_in_loop (iv
->step
, loop
->num
))
2831 else if (TREE_CODE (iv
->step
) != INTEGER_CST
)
2834 iv
->base
= CHREC_LEFT (ev
);
2835 if (tree_contains_chrecs (iv
->base
, NULL
)
2836 || chrec_contains_symbols_defined_in_loop (iv
->base
, loop
->num
))
2839 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
2844 /* Runs the analysis of scalar evolutions. */
2847 scev_analysis (void)
2849 VEC(tree
,heap
) *exit_conditions
;
2851 exit_conditions
= VEC_alloc (tree
, heap
, 37);
2852 select_loops_exit_conditions (current_loops
, &exit_conditions
);
2854 if (dump_file
&& (dump_flags
& TDF_STATS
))
2855 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2857 number_of_iterations_for_all_loops (&exit_conditions
);
2858 VEC_free (tree
, heap
, exit_conditions
);
2861 /* Finalize the scalar evolution analysis. */
2864 scev_finalize (void)
2866 htab_delete (scalar_evolution_info
);
2867 BITMAP_FREE (already_instantiated
);
2870 /* Returns true if EXPR looks expensive. */
2873 expression_expensive_p (tree expr
)
2875 return force_expr_to_var_cost (expr
) >= target_spill_cost
;
2878 /* Replace ssa names for that scev can prove they are constant by the
2879 appropriate constants. Also perform final value replacement in loops,
2880 in case the replacement expressions are cheap.
2882 We only consider SSA names defined by phi nodes; rest is left to the
2883 ordinary constant propagation pass. */
2886 scev_const_prop (void)
2889 tree name
, phi
, next_phi
, type
, ev
;
2890 struct loop
*loop
, *ex_loop
;
2891 bitmap ssa_names_to_remove
= NULL
;
2899 loop
= bb
->loop_father
;
2901 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2903 name
= PHI_RESULT (phi
);
2905 if (!is_gimple_reg (name
))
2908 type
= TREE_TYPE (name
);
2910 if (!POINTER_TYPE_P (type
)
2911 && !INTEGRAL_TYPE_P (type
))
2914 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
2915 if (!is_gimple_min_invariant (ev
)
2916 || !may_propagate_copy (name
, ev
))
2919 /* Replace the uses of the name. */
2921 replace_uses_by (name
, ev
);
2923 if (!ssa_names_to_remove
)
2924 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
2925 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
2929 /* Remove the ssa names that were replaced by constants. We do not remove them
2930 directly in the previous cycle, since this invalidates scev cache. */
2931 if (ssa_names_to_remove
)
2936 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
2938 name
= ssa_name (i
);
2939 phi
= SSA_NAME_DEF_STMT (name
);
2941 gcc_assert (TREE_CODE (phi
) == PHI_NODE
);
2942 remove_phi_node (phi
, NULL
);
2945 BITMAP_FREE (ssa_names_to_remove
);
2949 /* Now the regular final value replacement. */
2950 for (i
= current_loops
->num
- 1; i
> 0; i
--)
2953 tree def
, rslt
, ass
, niter
;
2954 block_stmt_iterator bsi
;
2956 loop
= current_loops
->parray
[i
];
2960 /* If we do not know exact number of iterations of the loop, we cannot
2961 replace the final value. */
2962 exit
= loop
->single_exit
;
2966 niter
= number_of_iterations_in_loop (loop
);
2967 if (niter
== chrec_dont_know
2968 /* If computing the number of iterations is expensive, it may be
2969 better not to introduce computations involving it. */
2970 || expression_expensive_p (niter
))
2973 /* Ensure that it is possible to insert new statements somewhere. */
2974 if (!single_pred_p (exit
->dest
))
2975 split_loop_exit_edge (exit
);
2976 tree_block_label (exit
->dest
);
2977 bsi
= bsi_after_labels (exit
->dest
);
2979 ex_loop
= superloop_at_depth (loop
, exit
->dest
->loop_father
->depth
+ 1);
2981 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= next_phi
)
2983 next_phi
= PHI_CHAIN (phi
);
2984 rslt
= PHI_RESULT (phi
);
2985 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2986 if (!is_gimple_reg (def
))
2989 if (!POINTER_TYPE_P (TREE_TYPE (def
))
2990 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
2993 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
2994 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
2995 if (!tree_does_not_contain_chrecs (def
)
2996 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
2997 /* Moving the computation from the loop may prolong life range
2998 of some ssa names, which may cause problems if they appear
2999 on abnormal edges. */
3000 || contains_abnormal_ssa_name_p (def
))
3003 /* Eliminate the phi node and replace it by a computation outside
3005 def
= unshare_expr (def
);
3006 SET_PHI_RESULT (phi
, NULL_TREE
);
3007 remove_phi_node (phi
, NULL_TREE
);
3009 ass
= build2 (MODIFY_EXPR
, void_type_node
, rslt
, NULL_TREE
);
3010 SSA_NAME_DEF_STMT (rslt
) = ass
;
3012 block_stmt_iterator dest
= bsi
;
3013 bsi_insert_before (&dest
, ass
, BSI_NEW_STMT
);
3014 def
= force_gimple_operand_bsi (&dest
, def
, false, NULL_TREE
);
3016 TREE_OPERAND (ass
, 1) = def
;