1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
25 This pass analyzes the evolution of scalar variables in loop
26 structures. The algorithm is based on the SSA representation,
27 and on the loop hierarchy tree. This algorithm is not based on
28 the notion of versions of a variable, as it was the case for the
29 previous implementations of the scalar evolution algorithm, but
30 it assumes that each defined name is unique.
32 The notation used in this file is called "chains of recurrences",
33 and has been proposed by Eugene Zima, Robert Van Engelen, and
34 others for describing induction variables in programs. For example
35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36 when entering in the loop_1 and has a step 2 in this loop, in other
37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38 this chain of recurrence (or chrec [shrek]) can contain the name of
39 other variables, in which case they are called parametric chrecs.
40 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41 is the value of "a". In most of the cases these parametric chrecs
42 are fully instantiated before their use because symbolic names can
43 hide some difficult cases such as self-references described later
44 (see the Fibonacci example).
46 A short sketch of the algorithm is:
48 Given a scalar variable to be analyzed, follow the SSA edge to
51 - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters ({a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2: Illustration of the algorithm on nested loops.
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
158 Example 3: Higher degree polynomials.
172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175 Example 4: Lucas, Fibonacci, or mixers in general.
187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188 following semantics: during the first iteration of the loop_1, the
189 variable contains the value 1, and then it contains the value "c".
190 Note that this syntax is close to the syntax of the loop-phi-node:
191 "a -> (1, c)_1" vs. "a = phi (1, c)".
193 The symbolic chrec representation contains all the semantics of the
194 original code. What is more difficult is to use this information.
196 Example 5: Flip-flops, or exchangers.
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
214 This transformation is not yet implemented.
218 You can find a more detailed description of the algorithm in:
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
221 this is a preliminary report and some of the details of the
222 algorithm have changed. I'm working on a research report that
223 updates the description of the algorithms to reflect the design
224 choices used in this implementation.
226 A set of slides show a high level overview of the algorithm and run
227 an example through the scalar evolution analyzer:
228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230 The slides that I have presented at the GCC Summit'04 are available
231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
236 #include "coretypes.h"
242 /* These RTL headers are needed for basic-block.h. */
244 #include "basic-block.h"
245 #include "diagnostic.h"
246 #include "tree-flow.h"
247 #include "tree-dump.h"
250 #include "tree-chrec.h"
251 #include "tree-scalar-evolution.h"
252 #include "tree-pass.h"
256 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
257 static tree
resolve_mixers (struct loop
*, tree
);
259 /* The cached information about a ssa name VAR, claiming that inside LOOP,
260 the value of VAR can be expressed as CHREC. */
268 /* Counters for the scev database. */
269 static unsigned nb_set_scev
= 0;
270 static unsigned nb_get_scev
= 0;
272 /* The following trees are unique elements. Thus the comparison of
273 another element to these elements should be done on the pointer to
274 these trees, and not on their value. */
276 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
277 tree chrec_not_analyzed_yet
;
279 /* Reserved to the cases where the analyzer has detected an
280 undecidable property at compile time. */
281 tree chrec_dont_know
;
283 /* When the analyzer has detected that a property will never
284 happen, then it qualifies it with chrec_known. */
287 static bitmap already_instantiated
;
289 static htab_t scalar_evolution_info
;
292 /* Constructs a new SCEV_INFO_STR structure. */
294 static inline struct scev_info_str
*
295 new_scev_info_str (tree var
)
297 struct scev_info_str
*res
;
299 res
= XNEW (struct scev_info_str
);
301 res
->chrec
= chrec_not_analyzed_yet
;
306 /* Computes a hash function for database element ELT. */
309 hash_scev_info (const void *elt
)
311 return SSA_NAME_VERSION (((struct scev_info_str
*) elt
)->var
);
314 /* Compares database elements E1 and E2. */
317 eq_scev_info (const void *e1
, const void *e2
)
319 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
320 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
322 return elt1
->var
== elt2
->var
;
325 /* Deletes database element E. */
328 del_scev_info (void *e
)
333 /* Get the index corresponding to VAR in the current LOOP. If
334 it's the first time we ask for this VAR, then we return
335 chrec_not_analyzed_yet for this VAR and return its index. */
338 find_var_scev_info (tree var
)
340 struct scev_info_str
*res
;
341 struct scev_info_str tmp
;
345 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
348 *slot
= new_scev_info_str (var
);
349 res
= (struct scev_info_str
*) *slot
;
354 /* Return true when CHREC contains symbolic names defined in
358 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
360 if (chrec
== NULL_TREE
)
363 if (TREE_INVARIANT (chrec
))
366 if (TREE_CODE (chrec
) == VAR_DECL
367 || TREE_CODE (chrec
) == PARM_DECL
368 || TREE_CODE (chrec
) == FUNCTION_DECL
369 || TREE_CODE (chrec
) == LABEL_DECL
370 || TREE_CODE (chrec
) == RESULT_DECL
371 || TREE_CODE (chrec
) == FIELD_DECL
)
374 if (TREE_CODE (chrec
) == SSA_NAME
)
376 tree def
= SSA_NAME_DEF_STMT (chrec
);
377 struct loop
*def_loop
= loop_containing_stmt (def
);
378 struct loop
*loop
= get_loop (loop_nb
);
380 if (def_loop
== NULL
)
383 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
389 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
392 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 2),
397 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 1),
402 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 0),
411 /* Return true when PHI is a loop-phi-node. */
414 loop_phi_node_p (tree phi
)
416 /* The implementation of this function is based on the following
417 property: "all the loop-phi-nodes of a loop are contained in the
418 loop's header basic block". */
420 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
423 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
424 In general, in the case of multivariate evolutions we want to get
425 the evolution in different loops. LOOP specifies the level for
426 which to get the evolution.
430 | for (j = 0; j < 100; j++)
432 | for (k = 0; k < 100; k++)
434 | i = k + j; - Here the value of i is a function of j, k.
436 | ... = i - Here the value of i is a function of j.
438 | ... = i - Here the value of i is a scalar.
444 | i_1 = phi (i_0, i_2)
448 This loop has the same effect as:
449 LOOP_1 has the same effect as:
453 The overall effect of the loop, "i_0 + 20" in the previous example,
454 is obtained by passing in the parameters: LOOP = 1,
455 EVOLUTION_FN = {i_0, +, 2}_1.
459 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
463 if (evolution_fn
== chrec_dont_know
)
464 return chrec_dont_know
;
466 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
468 if (CHREC_VARIABLE (evolution_fn
) >= (unsigned) loop
->num
)
470 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
471 tree nb_iter
= number_of_latch_executions (inner_loop
);
473 if (nb_iter
== chrec_dont_know
)
474 return chrec_dont_know
;
479 /* evolution_fn is the evolution function in LOOP. Get
480 its value in the nb_iter-th iteration. */
481 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
483 /* Continue the computation until ending on a parent of LOOP. */
484 return compute_overall_effect_of_inner_loop (loop
, res
);
491 /* If the evolution function is an invariant, there is nothing to do. */
492 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
496 return chrec_dont_know
;
499 /* Determine whether the CHREC is always positive/negative. If the expression
500 cannot be statically analyzed, return false, otherwise set the answer into
504 chrec_is_positive (tree chrec
, bool *value
)
506 bool value0
, value1
, value2
;
507 tree end_value
, nb_iter
;
509 switch (TREE_CODE (chrec
))
511 case POLYNOMIAL_CHREC
:
512 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
513 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
516 /* FIXME -- overflows. */
517 if (value0
== value1
)
523 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
524 and the proof consists in showing that the sign never
525 changes during the execution of the loop, from 0 to
526 loop->nb_iterations. */
527 if (!evolution_function_is_affine_p (chrec
))
530 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
531 if (chrec_contains_undetermined (nb_iter
))
535 /* TODO -- If the test is after the exit, we may decrease the number of
536 iterations by one. */
538 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
541 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
543 if (!chrec_is_positive (end_value
, &value2
))
547 return value0
== value1
;
550 *value
= (tree_int_cst_sgn (chrec
) == 1);
558 /* Associate CHREC to SCALAR. */
561 set_scalar_evolution (tree scalar
, tree chrec
)
565 if (TREE_CODE (scalar
) != SSA_NAME
)
568 scalar_info
= find_var_scev_info (scalar
);
572 if (dump_flags
& TDF_DETAILS
)
574 fprintf (dump_file
, "(set_scalar_evolution \n");
575 fprintf (dump_file
, " (scalar = ");
576 print_generic_expr (dump_file
, scalar
, 0);
577 fprintf (dump_file
, ")\n (scalar_evolution = ");
578 print_generic_expr (dump_file
, chrec
, 0);
579 fprintf (dump_file
, "))\n");
581 if (dump_flags
& TDF_STATS
)
585 *scalar_info
= chrec
;
588 /* Retrieve the chrec associated to SCALAR in the LOOP. */
591 get_scalar_evolution (tree scalar
)
597 if (dump_flags
& TDF_DETAILS
)
599 fprintf (dump_file
, "(get_scalar_evolution \n");
600 fprintf (dump_file
, " (scalar = ");
601 print_generic_expr (dump_file
, scalar
, 0);
602 fprintf (dump_file
, ")\n");
604 if (dump_flags
& TDF_STATS
)
608 switch (TREE_CODE (scalar
))
611 res
= *find_var_scev_info (scalar
);
620 res
= chrec_not_analyzed_yet
;
624 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
626 fprintf (dump_file
, " (scalar_evolution = ");
627 print_generic_expr (dump_file
, res
, 0);
628 fprintf (dump_file
, "))\n");
634 /* Helper function for add_to_evolution. Returns the evolution
635 function for an assignment of the form "a = b + c", where "a" and
636 "b" are on the strongly connected component. CHREC_BEFORE is the
637 information that we already have collected up to this point.
638 TO_ADD is the evolution of "c".
640 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
641 evolution the expression TO_ADD, otherwise construct an evolution
642 part for this loop. */
645 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
648 tree type
, left
, right
;
650 switch (TREE_CODE (chrec_before
))
652 case POLYNOMIAL_CHREC
:
653 if (CHREC_VARIABLE (chrec_before
) <= loop_nb
)
657 type
= chrec_type (chrec_before
);
659 /* When there is no evolution part in this loop, build it. */
660 if (CHREC_VARIABLE (chrec_before
) < loop_nb
)
664 right
= SCALAR_FLOAT_TYPE_P (type
)
665 ? build_real (type
, dconst0
)
666 : build_int_cst (type
, 0);
670 var
= CHREC_VARIABLE (chrec_before
);
671 left
= CHREC_LEFT (chrec_before
);
672 right
= CHREC_RIGHT (chrec_before
);
675 to_add
= chrec_convert (type
, to_add
, at_stmt
);
676 right
= chrec_convert (type
, right
, at_stmt
);
677 right
= chrec_fold_plus (type
, right
, to_add
);
678 return build_polynomial_chrec (var
, left
, right
);
682 /* Search the evolution in LOOP_NB. */
683 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
685 right
= CHREC_RIGHT (chrec_before
);
686 right
= chrec_convert (chrec_type (left
), right
, at_stmt
);
687 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
692 /* These nodes do not depend on a loop. */
693 if (chrec_before
== chrec_dont_know
)
694 return chrec_dont_know
;
697 right
= chrec_convert (chrec_type (left
), to_add
, at_stmt
);
698 return build_polynomial_chrec (loop_nb
, left
, right
);
702 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
705 Description (provided for completeness, for those who read code in
706 a plane, and for my poor 62 bytes brain that would have forgotten
707 all this in the next two or three months):
709 The algorithm of translation of programs from the SSA representation
710 into the chrecs syntax is based on a pattern matching. After having
711 reconstructed the overall tree expression for a loop, there are only
712 two cases that can arise:
714 1. a = loop-phi (init, a + expr)
715 2. a = loop-phi (init, expr)
717 where EXPR is either a scalar constant with respect to the analyzed
718 loop (this is a degree 0 polynomial), or an expression containing
719 other loop-phi definitions (these are higher degree polynomials).
726 | a = phi (init, a + 5)
733 | a = phi (inita, 2 * b + 3)
734 | b = phi (initb, b + 1)
737 For the first case, the semantics of the SSA representation is:
739 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
741 that is, there is a loop index "x" that determines the scalar value
742 of the variable during the loop execution. During the first
743 iteration, the value is that of the initial condition INIT, while
744 during the subsequent iterations, it is the sum of the initial
745 condition with the sum of all the values of EXPR from the initial
746 iteration to the before last considered iteration.
748 For the second case, the semantics of the SSA program is:
750 | a (x) = init, if x = 0;
751 | expr (x - 1), otherwise.
753 The second case corresponds to the PEELED_CHREC, whose syntax is
754 close to the syntax of a loop-phi-node:
756 | phi (init, expr) vs. (init, expr)_x
758 The proof of the translation algorithm for the first case is a
759 proof by structural induction based on the degree of EXPR.
762 When EXPR is a constant with respect to the analyzed loop, or in
763 other words when EXPR is a polynomial of degree 0, the evolution of
764 the variable A in the loop is an affine function with an initial
765 condition INIT, and a step EXPR. In order to show this, we start
766 from the semantics of the SSA representation:
768 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
770 and since "expr (j)" is a constant with respect to "j",
772 f (x) = init + x * expr
774 Finally, based on the semantics of the pure sum chrecs, by
775 identification we get the corresponding chrecs syntax:
777 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
778 f (x) -> {init, +, expr}_x
781 Suppose that EXPR is a polynomial of degree N with respect to the
782 analyzed loop_x for which we have already determined that it is
783 written under the chrecs syntax:
785 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
787 We start from the semantics of the SSA program:
789 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
791 | f (x) = init + \sum_{j = 0}^{x - 1}
792 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
794 | f (x) = init + \sum_{j = 0}^{x - 1}
795 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
797 | f (x) = init + \sum_{k = 0}^{n - 1}
798 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
800 | f (x) = init + \sum_{k = 0}^{n - 1}
801 | (b_k * \binom{x}{k + 1})
803 | f (x) = init + b_0 * \binom{x}{1} + ...
804 | + b_{n-1} * \binom{x}{n}
806 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
807 | + b_{n-1} * \binom{x}{n}
810 And finally from the definition of the chrecs syntax, we identify:
811 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
813 This shows the mechanism that stands behind the add_to_evolution
814 function. An important point is that the use of symbolic
815 parameters avoids the need of an analysis schedule.
822 | a = phi (inita, a + 2 + b)
823 | b = phi (initb, b + 1)
826 When analyzing "a", the algorithm keeps "b" symbolically:
828 | a -> {inita, +, 2 + b}_1
830 Then, after instantiation, the analyzer ends on the evolution:
832 | a -> {inita, +, 2 + initb, +, 1}_1
837 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
838 tree to_add
, tree at_stmt
)
840 tree type
= chrec_type (to_add
);
841 tree res
= NULL_TREE
;
843 if (to_add
== NULL_TREE
)
846 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
847 instantiated at this point. */
848 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
849 /* This should not happen. */
850 return chrec_dont_know
;
852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
854 fprintf (dump_file
, "(add_to_evolution \n");
855 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
856 fprintf (dump_file
, " (chrec_before = ");
857 print_generic_expr (dump_file
, chrec_before
, 0);
858 fprintf (dump_file
, ")\n (to_add = ");
859 print_generic_expr (dump_file
, to_add
, 0);
860 fprintf (dump_file
, ")\n");
863 if (code
== MINUS_EXPR
)
864 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
865 ? build_real (type
, dconstm1
)
866 : build_int_cst_type (type
, -1));
868 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
872 fprintf (dump_file
, " (res = ");
873 print_generic_expr (dump_file
, res
, 0);
874 fprintf (dump_file
, "))\n");
880 /* Helper function. */
883 set_nb_iterations_in_loop (struct loop
*loop
,
886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
888 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
889 print_generic_expr (dump_file
, res
, 0);
890 fprintf (dump_file
, "))\n");
893 loop
->nb_iterations
= res
;
899 /* This section selects the loops that will be good candidates for the
900 scalar evolution analysis. For the moment, greedily select all the
901 loop nests we could analyze. */
903 /* Return true when it is possible to analyze the condition expression
907 analyzable_condition (tree expr
)
911 if (TREE_CODE (expr
) != COND_EXPR
)
914 condition
= TREE_OPERAND (expr
, 0);
916 switch (TREE_CODE (condition
))
936 /* For a loop with a single exit edge, return the COND_EXPR that
937 guards the exit edge. If the expression is too difficult to
938 analyze, then give up. */
941 get_loop_exit_condition (struct loop
*loop
)
943 tree res
= NULL_TREE
;
944 edge exit_edge
= single_exit (loop
);
946 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
947 fprintf (dump_file
, "(get_loop_exit_condition \n ");
953 expr
= last_stmt (exit_edge
->src
);
954 if (analyzable_condition (expr
))
958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
960 print_generic_expr (dump_file
, res
, 0);
961 fprintf (dump_file
, ")\n");
967 /* Recursively determine and enqueue the exit conditions for a loop. */
970 get_exit_conditions_rec (struct loop
*loop
,
971 VEC(tree
,heap
) **exit_conditions
)
976 /* Recurse on the inner loops, then on the next (sibling) loops. */
977 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
978 get_exit_conditions_rec (loop
->next
, exit_conditions
);
980 if (single_exit (loop
))
982 tree loop_condition
= get_loop_exit_condition (loop
);
985 VEC_safe_push (tree
, heap
, *exit_conditions
, loop_condition
);
989 /* Select the candidate loop nests for the analysis. This function
990 initializes the EXIT_CONDITIONS array. */
993 select_loops_exit_conditions (VEC(tree
,heap
) **exit_conditions
)
995 struct loop
*function_body
= current_loops
->tree_root
;
997 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
1001 /* Depth first search algorithm. */
1003 typedef enum t_bool
{
1010 static t_bool
follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*, int);
1012 /* Follow the ssa edge into the right hand side RHS of an assignment.
1013 Return true if the strongly connected component has been found. */
1016 follow_ssa_edge_in_rhs (struct loop
*loop
, tree at_stmt
, tree rhs
,
1017 tree halting_phi
, tree
*evolution_of_loop
, int limit
)
1019 t_bool res
= t_false
;
1021 tree type_rhs
= TREE_TYPE (rhs
);
1024 /* The RHS is one of the following cases:
1030 - other cases are not yet handled. */
1031 switch (TREE_CODE (rhs
))
1034 /* This assignment is under the form "a_1 = (cast) rhs. */
1035 res
= follow_ssa_edge_in_rhs (loop
, at_stmt
, TREE_OPERAND (rhs
, 0),
1036 halting_phi
, evolution_of_loop
, limit
);
1037 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
),
1038 *evolution_of_loop
, at_stmt
);
1042 /* This assignment is under the form "a_1 = 7". */
1047 /* This assignment is under the form: "a_1 = b_2". */
1048 res
= follow_ssa_edge
1049 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
, limit
);
1053 /* This case is under the form "rhs0 + rhs1". */
1054 rhs0
= TREE_OPERAND (rhs
, 0);
1055 rhs1
= TREE_OPERAND (rhs
, 1);
1056 STRIP_TYPE_NOPS (rhs0
);
1057 STRIP_TYPE_NOPS (rhs1
);
1059 if (TREE_CODE (rhs0
) == SSA_NAME
)
1061 if (TREE_CODE (rhs1
) == SSA_NAME
)
1063 /* Match an assignment under the form:
1065 evol
= *evolution_of_loop
;
1066 res
= follow_ssa_edge
1067 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1071 *evolution_of_loop
= add_to_evolution
1073 chrec_convert (type_rhs
, evol
, at_stmt
),
1074 PLUS_EXPR
, rhs1
, at_stmt
);
1076 else if (res
== t_false
)
1078 res
= follow_ssa_edge
1079 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1080 evolution_of_loop
, limit
);
1083 *evolution_of_loop
= add_to_evolution
1085 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1086 PLUS_EXPR
, rhs0
, at_stmt
);
1088 else if (res
== t_dont_know
)
1089 *evolution_of_loop
= chrec_dont_know
;
1092 else if (res
== t_dont_know
)
1093 *evolution_of_loop
= chrec_dont_know
;
1098 /* Match an assignment under the form:
1100 res
= follow_ssa_edge
1101 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1102 evolution_of_loop
, limit
);
1104 *evolution_of_loop
= add_to_evolution
1105 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1107 PLUS_EXPR
, rhs1
, at_stmt
);
1109 else if (res
== t_dont_know
)
1110 *evolution_of_loop
= chrec_dont_know
;
1114 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1116 /* Match an assignment under the form:
1118 res
= follow_ssa_edge
1119 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1120 evolution_of_loop
, limit
);
1122 *evolution_of_loop
= add_to_evolution
1123 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1125 PLUS_EXPR
, rhs0
, at_stmt
);
1127 else if (res
== t_dont_know
)
1128 *evolution_of_loop
= chrec_dont_know
;
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
,
1151 evolution_of_loop
, limit
);
1153 *evolution_of_loop
= add_to_evolution
1154 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1155 MINUS_EXPR
, rhs1
, at_stmt
);
1157 else if (res
== t_dont_know
)
1158 *evolution_of_loop
= chrec_dont_know
;
1161 /* Otherwise, match an assignment under the form:
1163 /* And there is nothing to do. */
1170 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1171 It must be handled as a copy assignment of the form a_1 = a_2. */
1172 tree op0
= ASSERT_EXPR_VAR (rhs
);
1173 if (TREE_CODE (op0
) == SSA_NAME
)
1174 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1175 halting_phi
, evolution_of_loop
, limit
);
1190 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1193 backedge_phi_arg_p (tree phi
, int i
)
1195 edge e
= PHI_ARG_EDGE (phi
, i
);
1197 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1198 about updating it anywhere, and this should work as well most of the
1200 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1206 /* Helper function for one branch of the condition-phi-node. Return
1207 true if the strongly connected component has been found following
1210 static inline t_bool
1211 follow_ssa_edge_in_condition_phi_branch (int i
,
1215 tree
*evolution_of_branch
,
1216 tree init_cond
, int limit
)
1218 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1219 *evolution_of_branch
= chrec_dont_know
;
1221 /* Do not follow back edges (they must belong to an irreducible loop, which
1222 we really do not want to worry about). */
1223 if (backedge_phi_arg_p (condition_phi
, i
))
1226 if (TREE_CODE (branch
) == SSA_NAME
)
1228 *evolution_of_branch
= init_cond
;
1229 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1230 evolution_of_branch
, limit
);
1233 /* This case occurs when one of the condition branches sets
1234 the variable to a constant: i.e. a phi-node like
1235 "a_2 = PHI <a_7(5), 2(6)>;".
1237 FIXME: This case have to be refined correctly:
1238 in some cases it is possible to say something better than
1239 chrec_dont_know, for example using a wrap-around notation. */
1243 /* This function merges the branches of a condition-phi-node in a
1247 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1250 tree
*evolution_of_loop
, int limit
)
1253 tree init
= *evolution_of_loop
;
1254 tree evolution_of_branch
;
1255 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1257 &evolution_of_branch
,
1259 if (res
== t_false
|| res
== t_dont_know
)
1262 *evolution_of_loop
= evolution_of_branch
;
1264 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1266 /* Quickly give up when the evolution of one of the branches is
1268 if (*evolution_of_loop
== chrec_dont_know
)
1271 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1273 &evolution_of_branch
,
1275 if (res
== t_false
|| res
== t_dont_know
)
1278 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1279 evolution_of_branch
);
1285 /* Follow an SSA edge in an inner loop. It computes the overall
1286 effect of the loop, and following the symbolic initial conditions,
1287 it follows the edges in the parent loop. The inner loop is
1288 considered as a single statement. */
1291 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1294 tree
*evolution_of_loop
, int limit
)
1296 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1297 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1299 /* Sometimes, the inner loop is too difficult to analyze, and the
1300 result of the analysis is a symbolic parameter. */
1301 if (ev
== PHI_RESULT (loop_phi_node
))
1303 t_bool res
= t_false
;
1306 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1308 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1311 /* Follow the edges that exit the inner loop. */
1312 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1313 if (!flow_bb_inside_loop_p (loop
, bb
))
1314 res
= follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
,
1316 evolution_of_loop
, limit
);
1321 /* If the path crosses this loop-phi, give up. */
1323 *evolution_of_loop
= chrec_dont_know
;
1328 /* Otherwise, compute the overall effect of the inner loop. */
1329 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1330 return follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1331 evolution_of_loop
, limit
);
1334 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1335 path that is analyzed on the return walk. */
1338 follow_ssa_edge (struct loop
*loop
, tree def
, tree halting_phi
,
1339 tree
*evolution_of_loop
, int limit
)
1341 struct loop
*def_loop
;
1343 if (TREE_CODE (def
) == NOP_EXPR
)
1346 /* Give up if the path is longer than the MAX that we allow. */
1347 if (limit
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1350 def_loop
= loop_containing_stmt (def
);
1352 switch (TREE_CODE (def
))
1355 if (!loop_phi_node_p (def
))
1356 /* DEF is a condition-phi-node. Follow the branches, and
1357 record their evolutions. Finally, merge the collected
1358 information and set the approximation to the main
1360 return follow_ssa_edge_in_condition_phi
1361 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1363 /* When the analyzed phi is the halting_phi, the
1364 depth-first search is over: we have found a path from
1365 the halting_phi to itself in the loop. */
1366 if (def
== halting_phi
)
1369 /* Otherwise, the evolution of the HALTING_PHI depends
1370 on the evolution of another loop-phi-node, i.e. the
1371 evolution function is a higher degree polynomial. */
1372 if (def_loop
== loop
)
1376 if (flow_loop_nested_p (loop
, def_loop
))
1377 return follow_ssa_edge_inner_loop_phi
1378 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1383 case GIMPLE_MODIFY_STMT
:
1384 return follow_ssa_edge_in_rhs (loop
, def
,
1385 GIMPLE_STMT_OPERAND (def
, 1),
1387 evolution_of_loop
, limit
);
1390 /* At this level of abstraction, the program is just a set
1391 of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
1392 other node to be handled. */
1399 /* Given a LOOP_PHI_NODE, this function determines the evolution
1400 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1403 analyze_evolution_in_loop (tree loop_phi_node
,
1407 tree evolution_function
= chrec_not_analyzed_yet
;
1408 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1413 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1414 fprintf (dump_file
, " (loop_phi_node = ");
1415 print_generic_expr (dump_file
, loop_phi_node
, 0);
1416 fprintf (dump_file
, ")\n");
1419 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1421 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1422 tree ssa_chain
, ev_fn
;
1425 /* Select the edges that enter the loop body. */
1426 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1427 if (!flow_bb_inside_loop_p (loop
, bb
))
1430 if (TREE_CODE (arg
) == SSA_NAME
)
1432 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1434 /* Pass in the initial condition to the follow edge function. */
1436 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1441 /* When it is impossible to go back on the same
1442 loop_phi_node by following the ssa edges, the
1443 evolution is represented by a peeled chrec, i.e. the
1444 first iteration, EV_FN has the value INIT_COND, then
1445 all the other iterations it has the value of ARG.
1446 For the moment, PEELED_CHREC nodes are not built. */
1448 ev_fn
= chrec_dont_know
;
1450 /* When there are multiple back edges of the loop (which in fact never
1451 happens currently, but nevertheless), merge their evolutions. */
1452 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1457 fprintf (dump_file
, " (evolution_function = ");
1458 print_generic_expr (dump_file
, evolution_function
, 0);
1459 fprintf (dump_file
, "))\n");
1462 return evolution_function
;
1465 /* Given a loop-phi-node, return the initial conditions of the
1466 variable on entry of the loop. When the CCP has propagated
1467 constants into the loop-phi-node, the initial condition is
1468 instantiated, otherwise the initial condition is kept symbolic.
1469 This analyzer does not analyze the evolution outside the current
1470 loop, and leaves this task to the on-demand tree reconstructor. */
1473 analyze_initial_condition (tree loop_phi_node
)
1476 tree init_cond
= chrec_not_analyzed_yet
;
1477 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1481 fprintf (dump_file
, "(analyze_initial_condition \n");
1482 fprintf (dump_file
, " (loop_phi_node = \n");
1483 print_generic_expr (dump_file
, loop_phi_node
, 0);
1484 fprintf (dump_file
, ")\n");
1487 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1489 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1490 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1492 /* When the branch is oriented to the loop's body, it does
1493 not contribute to the initial condition. */
1494 if (flow_bb_inside_loop_p (loop
, bb
))
1497 if (init_cond
== chrec_not_analyzed_yet
)
1503 if (TREE_CODE (branch
) == SSA_NAME
)
1505 init_cond
= chrec_dont_know
;
1509 init_cond
= chrec_merge (init_cond
, branch
);
1512 /* Ooops -- a loop without an entry??? */
1513 if (init_cond
== chrec_not_analyzed_yet
)
1514 init_cond
= chrec_dont_know
;
1516 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1518 fprintf (dump_file
, " (init_cond = ");
1519 print_generic_expr (dump_file
, init_cond
, 0);
1520 fprintf (dump_file
, "))\n");
1526 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1529 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1532 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1535 if (phi_loop
!= loop
)
1537 struct loop
*subloop
;
1538 tree evolution_fn
= analyze_scalar_evolution
1539 (phi_loop
, PHI_RESULT (loop_phi_node
));
1541 /* Dive one level deeper. */
1542 subloop
= superloop_at_depth (phi_loop
, loop
->depth
+ 1);
1544 /* Interpret the subloop. */
1545 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1549 /* Otherwise really interpret the loop phi. */
1550 init_cond
= analyze_initial_condition (loop_phi_node
);
1551 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1556 /* This function merges the branches of a condition-phi-node,
1557 contained in the outermost loop, and whose arguments are already
1561 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1564 tree res
= chrec_not_analyzed_yet
;
1566 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1570 if (backedge_phi_arg_p (condition_phi
, i
))
1572 res
= chrec_dont_know
;
1576 branch_chrec
= analyze_scalar_evolution
1577 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1579 res
= chrec_merge (res
, branch_chrec
);
1585 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
1586 analyze this node before, follow the definitions until ending
1587 either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
1588 return path, this function propagates evolutions (ala constant copy
1589 propagation). OPND1 is not a GIMPLE expression because we could
1590 analyze the effect of an inner loop: see interpret_loop_phi. */
1593 interpret_rhs_modify_stmt (struct loop
*loop
, tree at_stmt
,
1594 tree opnd1
, tree type
)
1596 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1598 if (is_gimple_min_invariant (opnd1
))
1599 return chrec_convert (type
, opnd1
, at_stmt
);
1601 switch (TREE_CODE (opnd1
))
1604 opnd10
= TREE_OPERAND (opnd1
, 0);
1605 opnd11
= TREE_OPERAND (opnd1
, 1);
1606 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1607 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1608 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1609 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1610 res
= chrec_fold_plus (type
, chrec10
, chrec11
);
1614 opnd10
= TREE_OPERAND (opnd1
, 0);
1615 opnd11
= TREE_OPERAND (opnd1
, 1);
1616 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1617 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1618 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1619 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1620 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1624 opnd10
= TREE_OPERAND (opnd1
, 0);
1625 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1626 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1627 /* TYPE may be integer, real or complex, so use fold_convert. */
1628 res
= chrec_fold_multiply (type
, chrec10
,
1629 fold_convert (type
, integer_minus_one_node
));
1633 opnd10
= TREE_OPERAND (opnd1
, 0);
1634 opnd11
= TREE_OPERAND (opnd1
, 1);
1635 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1636 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1637 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1638 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1639 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1643 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
),
1648 opnd10
= ASSERT_EXPR_VAR (opnd1
);
1649 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd10
),
1655 opnd10
= TREE_OPERAND (opnd1
, 0);
1656 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1657 res
= chrec_convert (type
, chrec10
, at_stmt
);
1661 res
= chrec_dont_know
;
1670 /* This section contains all the entry points:
1671 - number_of_iterations_in_loop,
1672 - analyze_scalar_evolution,
1673 - instantiate_parameters.
1676 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1677 common ancestor of DEF_LOOP and USE_LOOP. */
1680 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1681 struct loop
*def_loop
,
1685 if (def_loop
== wrto_loop
)
1688 def_loop
= superloop_at_depth (def_loop
, wrto_loop
->depth
+ 1);
1689 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1691 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1694 /* Folds EXPR, if it is a cast to pointer, assuming that the created
1695 polynomial_chrec does not wrap. */
1698 fold_used_pointer_cast (tree expr
)
1701 tree type
, inner_type
;
1703 if (TREE_CODE (expr
) != NOP_EXPR
&& TREE_CODE (expr
) != CONVERT_EXPR
)
1706 op
= TREE_OPERAND (expr
, 0);
1707 if (TREE_CODE (op
) != POLYNOMIAL_CHREC
)
1710 type
= TREE_TYPE (expr
);
1711 inner_type
= TREE_TYPE (op
);
1713 if (!INTEGRAL_TYPE_P (inner_type
)
1714 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (type
))
1717 return build_polynomial_chrec (CHREC_VARIABLE (op
),
1718 chrec_convert (type
, CHREC_LEFT (op
), NULL_TREE
),
1719 chrec_convert (type
, CHREC_RIGHT (op
), NULL_TREE
));
1722 /* Returns true if EXPR is an expression corresponding to offset of pointer
1726 pointer_offset_p (tree expr
)
1728 if (TREE_CODE (expr
) == INTEGER_CST
)
1731 if ((TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1732 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0))))
1738 /* EXPR is a scalar evolution of a pointer that is dereferenced or used in
1739 comparison. This means that it must point to a part of some object in
1740 memory, which enables us to argue about overflows and possibly simplify
1741 the EXPR. AT_STMT is the statement in which this conversion has to be
1742 performed. Returns the simplified value.
1749 for (i = -n; i < n; i++)
1752 We generate the following code (assuming that size of int and size_t is
1755 for (i = -n; i < n; i++)
1760 tmp1 = (size_t) i; (1)
1761 tmp2 = 4 * tmp1; (2)
1762 tmp3 = (int *) tmp2; (3)
1763 tmp4 = p + tmp3; (4)
1768 We in general assume that pointer arithmetics does not overflow (since its
1769 behavior is undefined in that case). One of the problems is that our
1770 translation does not capture this property very well -- (int *) is
1771 considered unsigned, hence the computation in (4) does overflow if i is
1774 This impreciseness creates complications in scev analysis. The scalar
1775 evolution of i is [-n, +, 1]. Since int and size_t have the same precision
1776 (in this example), and size_t is unsigned (so we do not care about
1777 overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
1778 and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into
1779 problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
1780 places assume that this is not the case for scevs with pointer type, we
1781 cannot use this scev for tmp3; hence, its scev is
1782 (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
1783 p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to
1784 work with scevs of this shape.
1786 However, since tmp4 is dereferenced, all its values must belong to a single
1787 object, and taking into account that the precision of int * and size_t is
1788 the same, it is impossible for its scev to wrap. Hence, we can derive that
1789 its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
1792 ??? Maybe we should use different representation for pointer arithmetics,
1793 however that is a long-term project with a lot of potential for creating
1797 fold_used_pointer (tree expr
, tree at_stmt
)
1799 tree op0
, op1
, new0
, new1
;
1800 enum tree_code code
= TREE_CODE (expr
);
1802 if (code
== PLUS_EXPR
1803 || code
== MINUS_EXPR
)
1805 op0
= TREE_OPERAND (expr
, 0);
1806 op1
= TREE_OPERAND (expr
, 1);
1808 if (pointer_offset_p (op1
))
1810 new0
= fold_used_pointer (op0
, at_stmt
);
1811 new1
= fold_used_pointer_cast (op1
);
1813 else if (code
== PLUS_EXPR
&& pointer_offset_p (op0
))
1815 new0
= fold_used_pointer_cast (op0
);
1816 new1
= fold_used_pointer (op1
, at_stmt
);
1821 if (new0
== op0
&& new1
== op1
)
1824 new0
= chrec_convert (TREE_TYPE (expr
), new0
, at_stmt
);
1825 new1
= chrec_convert (TREE_TYPE (expr
), new1
, at_stmt
);
1827 if (code
== PLUS_EXPR
)
1828 expr
= chrec_fold_plus (TREE_TYPE (expr
), new0
, new1
);
1830 expr
= chrec_fold_minus (TREE_TYPE (expr
), new0
, new1
);
1835 return fold_used_pointer_cast (expr
);
1838 /* Returns true if PTR is dereferenced, or used in comparison. */
1841 pointer_used_p (tree ptr
)
1843 use_operand_p use_p
;
1844 imm_use_iterator imm_iter
;
1846 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
1848 /* Check whether the pointer has a memory tag; if it does, it is
1849 (or at least used to be) dereferenced. */
1850 if ((pi
!= NULL
&& pi
->name_mem_tag
!= NULL
)
1851 || symbol_mem_tag (SSA_NAME_VAR (ptr
)))
1854 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, ptr
)
1856 stmt
= USE_STMT (use_p
);
1857 if (TREE_CODE (stmt
) == COND_EXPR
)
1860 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1863 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1864 if (!COMPARISON_CLASS_P (rhs
))
1867 if (GIMPLE_STMT_OPERAND (stmt
, 0) == ptr
1868 || GIMPLE_STMT_OPERAND (stmt
, 1) == ptr
)
1875 /* Helper recursive function. */
1878 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1880 tree def
, type
= TREE_TYPE (var
);
1882 struct loop
*def_loop
;
1884 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1885 return chrec_dont_know
;
1887 if (TREE_CODE (var
) != SSA_NAME
)
1888 return interpret_rhs_modify_stmt (loop
, NULL_TREE
, var
, type
);
1890 def
= SSA_NAME_DEF_STMT (var
);
1891 bb
= bb_for_stmt (def
);
1892 def_loop
= bb
? bb
->loop_father
: NULL
;
1895 || !flow_bb_inside_loop_p (loop
, bb
))
1897 /* Keep the symbolic form. */
1902 if (res
!= chrec_not_analyzed_yet
)
1904 if (loop
!= bb
->loop_father
)
1905 res
= compute_scalar_evolution_in_loop
1906 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1911 if (loop
!= def_loop
)
1913 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1914 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1919 switch (TREE_CODE (def
))
1921 case GIMPLE_MODIFY_STMT
:
1922 res
= interpret_rhs_modify_stmt (loop
, def
,
1923 GIMPLE_STMT_OPERAND (def
, 1), type
);
1925 if (POINTER_TYPE_P (type
)
1926 && !automatically_generated_chrec_p (res
)
1927 && pointer_used_p (var
))
1928 res
= fold_used_pointer (res
, def
);
1932 if (loop_phi_node_p (def
))
1933 res
= interpret_loop_phi (loop
, def
);
1935 res
= interpret_condition_phi (loop
, def
);
1939 res
= chrec_dont_know
;
1945 /* Keep the symbolic form. */
1946 if (res
== chrec_dont_know
)
1949 if (loop
== def_loop
)
1950 set_scalar_evolution (var
, res
);
1955 /* Entry point for the scalar evolution analyzer.
1956 Analyzes and returns the scalar evolution of the ssa_name VAR.
1957 LOOP_NB is the identifier number of the loop in which the variable
1960 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1961 pointer to the statement that uses this variable, in order to
1962 determine the evolution function of the variable, use the following
1965 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1966 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1967 tree chrec_instantiated = instantiate_parameters
1968 (loop_nb, chrec_with_symbols);
1972 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1978 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1979 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1980 fprintf (dump_file
, " (scalar = ");
1981 print_generic_expr (dump_file
, var
, 0);
1982 fprintf (dump_file
, ")\n");
1985 res
= analyze_scalar_evolution_1 (loop
, var
, get_scalar_evolution (var
));
1987 if (TREE_CODE (var
) == SSA_NAME
&& res
== chrec_dont_know
)
1990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1991 fprintf (dump_file
, ")\n");
1996 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1997 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
2000 FOLDED_CASTS is set to true if resolve_mixers used
2001 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2002 at the moment in order to keep things simple). */
2005 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2006 tree version
, bool *folded_casts
)
2009 tree ev
= version
, tmp
;
2012 *folded_casts
= false;
2015 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2016 ev
= resolve_mixers (use_loop
, tmp
);
2018 if (folded_casts
&& tmp
!= ev
)
2019 *folded_casts
= true;
2021 if (use_loop
== wrto_loop
)
2024 /* If the value of the use changes in the inner loop, we cannot express
2025 its value in the outer loop (we might try to return interval chrec,
2026 but we do not have a user for it anyway) */
2027 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2029 return chrec_dont_know
;
2031 use_loop
= use_loop
->outer
;
2035 /* Returns instantiated value for VERSION in CACHE. */
2038 get_instantiated_value (htab_t cache
, tree version
)
2040 struct scev_info_str
*info
, pattern
;
2042 pattern
.var
= version
;
2043 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2051 /* Sets instantiated value for VERSION to VAL in CACHE. */
2054 set_instantiated_value (htab_t cache
, tree version
, tree val
)
2056 struct scev_info_str
*info
, pattern
;
2059 pattern
.var
= version
;
2060 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2063 *slot
= new_scev_info_str (version
);
2064 info
= (struct scev_info_str
*) *slot
;
2068 /* Return the closed_loop_phi node for VAR. If there is none, return
2072 loop_closed_phi_def (tree var
)
2078 if (var
== NULL_TREE
2079 || TREE_CODE (var
) != SSA_NAME
)
2082 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2083 exit
= single_exit (loop
);
2087 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
2088 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2089 return PHI_RESULT (phi
);
2094 /* Analyze all the parameters of the chrec that were left under a symbolic form,
2095 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
2096 of already instantiated values. FLAGS modify the way chrecs are
2097 instantiated. SIZE_EXPR is used for computing the size of the expression to
2098 be instantiated, and to stop if it exceeds some limit. */
2100 /* Values for FLAGS. */
2103 INSERT_SUPERLOOP_CHRECS
= 1, /* Loop invariants are replaced with chrecs
2105 FOLD_CONVERSIONS
= 2 /* The conversions that may wrap in
2106 signed/pointer type are folded, as long as the
2107 value of the chrec is preserved. */
2111 instantiate_parameters_1 (struct loop
*loop
, tree chrec
, int flags
, htab_t cache
,
2114 tree res
, op0
, op1
, op2
;
2116 struct loop
*def_loop
;
2117 tree type
= chrec_type (chrec
);
2119 /* Give up if the expression is larger than the MAX that we allow. */
2120 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2121 return chrec_dont_know
;
2123 if (automatically_generated_chrec_p (chrec
)
2124 || is_gimple_min_invariant (chrec
))
2127 switch (TREE_CODE (chrec
))
2130 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
2132 /* A parameter (or loop invariant and we do not want to include
2133 evolutions in outer loops), nothing to do. */
2135 || (!(flags
& INSERT_SUPERLOOP_CHRECS
)
2136 && !flow_bb_inside_loop_p (loop
, def_bb
)))
2139 /* We cache the value of instantiated variable to avoid exponential
2140 time complexity due to reevaluations. We also store the convenient
2141 value in the cache in order to prevent infinite recursion -- we do
2142 not want to instantiate the SSA_NAME if it is in a mixer
2143 structure. This is used for avoiding the instantiation of
2144 recursively defined functions, such as:
2146 | a_2 -> {0, +, 1, +, a_2}_1 */
2148 res
= get_instantiated_value (cache
, chrec
);
2152 /* Store the convenient value for chrec in the structure. If it
2153 is defined outside of the loop, we may just leave it in symbolic
2154 form, otherwise we need to admit that we do not know its behavior
2156 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
2157 set_instantiated_value (cache
, chrec
, res
);
2159 /* To make things even more complicated, instantiate_parameters_1
2160 calls analyze_scalar_evolution that may call # of iterations
2161 analysis that may in turn call instantiate_parameters_1 again.
2162 To prevent the infinite recursion, keep also the bitmap of
2163 ssa names that are being instantiated globally. */
2164 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
2167 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
2169 /* If the analysis yields a parametric chrec, instantiate the
2171 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2172 res
= analyze_scalar_evolution (def_loop
, chrec
);
2174 /* Don't instantiate loop-closed-ssa phi nodes. */
2175 if (TREE_CODE (res
) == SSA_NAME
2176 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2177 || (loop_containing_stmt (SSA_NAME_DEF_STMT (res
))->depth
2178 > def_loop
->depth
)))
2181 res
= loop_closed_phi_def (chrec
);
2185 if (res
== NULL_TREE
)
2186 res
= chrec_dont_know
;
2189 else if (res
!= chrec_dont_know
)
2190 res
= instantiate_parameters_1 (loop
, res
, flags
, cache
, size_expr
);
2192 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2194 /* Store the correct value to the cache. */
2195 set_instantiated_value (cache
, chrec
, res
);
2198 case POLYNOMIAL_CHREC
:
2199 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2200 flags
, cache
, size_expr
);
2201 if (op0
== chrec_dont_know
)
2202 return chrec_dont_know
;
2204 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2205 flags
, cache
, size_expr
);
2206 if (op1
== chrec_dont_know
)
2207 return chrec_dont_know
;
2209 if (CHREC_LEFT (chrec
) != op0
2210 || CHREC_RIGHT (chrec
) != op1
)
2212 op1
= chrec_convert (chrec_type (op0
), op1
, NULL_TREE
);
2213 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2218 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2219 flags
, cache
, size_expr
);
2220 if (op0
== chrec_dont_know
)
2221 return chrec_dont_know
;
2223 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2224 flags
, cache
, size_expr
);
2225 if (op1
== chrec_dont_know
)
2226 return chrec_dont_know
;
2228 if (TREE_OPERAND (chrec
, 0) != op0
2229 || TREE_OPERAND (chrec
, 1) != op1
)
2231 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2232 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2233 chrec
= chrec_fold_plus (type
, op0
, op1
);
2238 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2239 flags
, cache
, size_expr
);
2240 if (op0
== chrec_dont_know
)
2241 return chrec_dont_know
;
2243 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2244 flags
, cache
, size_expr
);
2245 if (op1
== chrec_dont_know
)
2246 return chrec_dont_know
;
2248 if (TREE_OPERAND (chrec
, 0) != op0
2249 || TREE_OPERAND (chrec
, 1) != op1
)
2251 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2252 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2253 chrec
= chrec_fold_minus (type
, op0
, op1
);
2258 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2259 flags
, cache
, size_expr
);
2260 if (op0
== chrec_dont_know
)
2261 return chrec_dont_know
;
2263 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2264 flags
, cache
, size_expr
);
2265 if (op1
== chrec_dont_know
)
2266 return chrec_dont_know
;
2268 if (TREE_OPERAND (chrec
, 0) != op0
2269 || TREE_OPERAND (chrec
, 1) != op1
)
2271 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2272 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2273 chrec
= chrec_fold_multiply (type
, op0
, op1
);
2279 case NON_LVALUE_EXPR
:
2280 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2281 flags
, cache
, size_expr
);
2282 if (op0
== chrec_dont_know
)
2283 return chrec_dont_know
;
2285 if (flags
& FOLD_CONVERSIONS
)
2287 tree tmp
= chrec_convert_aggressive (TREE_TYPE (chrec
), op0
);
2292 if (op0
== TREE_OPERAND (chrec
, 0))
2295 /* If we used chrec_convert_aggressive, we can no longer assume that
2296 signed chrecs do not overflow, as chrec_convert does, so avoid
2297 calling it in that case. */
2298 if (flags
& FOLD_CONVERSIONS
)
2299 return fold_convert (TREE_TYPE (chrec
), op0
);
2301 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL_TREE
);
2303 case SCEV_NOT_KNOWN
:
2304 return chrec_dont_know
;
2313 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2316 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2317 flags
, cache
, size_expr
);
2318 if (op0
== chrec_dont_know
)
2319 return chrec_dont_know
;
2321 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2322 flags
, cache
, size_expr
);
2323 if (op1
== chrec_dont_know
)
2324 return chrec_dont_know
;
2326 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2327 flags
, cache
, size_expr
);
2328 if (op2
== chrec_dont_know
)
2329 return chrec_dont_know
;
2331 if (op0
== TREE_OPERAND (chrec
, 0)
2332 && op1
== TREE_OPERAND (chrec
, 1)
2333 && op2
== TREE_OPERAND (chrec
, 2))
2336 return fold_build3 (TREE_CODE (chrec
),
2337 TREE_TYPE (chrec
), op0
, op1
, op2
);
2340 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2341 flags
, cache
, size_expr
);
2342 if (op0
== chrec_dont_know
)
2343 return chrec_dont_know
;
2345 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2346 flags
, cache
, size_expr
);
2347 if (op1
== chrec_dont_know
)
2348 return chrec_dont_know
;
2350 if (op0
== TREE_OPERAND (chrec
, 0)
2351 && op1
== TREE_OPERAND (chrec
, 1))
2353 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2356 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2357 flags
, cache
, size_expr
);
2358 if (op0
== chrec_dont_know
)
2359 return chrec_dont_know
;
2360 if (op0
== TREE_OPERAND (chrec
, 0))
2362 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2371 /* Too complicated to handle. */
2372 return chrec_dont_know
;
2375 /* Analyze all the parameters of the chrec that were left under a
2376 symbolic form. LOOP is the loop in which symbolic names have to
2377 be analyzed and instantiated. */
2380 instantiate_parameters (struct loop
*loop
,
2384 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2388 fprintf (dump_file
, "(instantiate_parameters \n");
2389 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2390 fprintf (dump_file
, " (chrec = ");
2391 print_generic_expr (dump_file
, chrec
, 0);
2392 fprintf (dump_file
, ")\n");
2395 res
= instantiate_parameters_1 (loop
, chrec
, INSERT_SUPERLOOP_CHRECS
, cache
,
2398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2400 fprintf (dump_file
, " (res = ");
2401 print_generic_expr (dump_file
, res
, 0);
2402 fprintf (dump_file
, "))\n");
2405 htab_delete (cache
);
2410 /* Similar to instantiate_parameters, but does not introduce the
2411 evolutions in outer loops for LOOP invariants in CHREC, and does not
2412 care about causing overflows, as long as they do not affect value
2413 of an expression. */
2416 resolve_mixers (struct loop
*loop
, tree chrec
)
2418 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2419 tree ret
= instantiate_parameters_1 (loop
, chrec
, FOLD_CONVERSIONS
, cache
, 0);
2420 htab_delete (cache
);
2424 /* Entry point for the analysis of the number of iterations pass.
2425 This function tries to safely approximate the number of iterations
2426 the loop will run. When this property is not decidable at compile
2427 time, the result is chrec_dont_know. Otherwise the result is
2428 a scalar or a symbolic parameter.
2430 Example of analysis: suppose that the loop has an exit condition:
2432 "if (b > 49) goto end_loop;"
2434 and that in a previous analysis we have determined that the
2435 variable 'b' has an evolution function:
2437 "EF = {23, +, 5}_2".
2439 When we evaluate the function at the point 5, i.e. the value of the
2440 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2441 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2442 the loop body has been executed 6 times. */
2445 number_of_latch_executions (struct loop
*loop
)
2449 struct tree_niter_desc niter_desc
;
2451 /* Determine whether the number_of_iterations_in_loop has already
2453 res
= loop
->nb_iterations
;
2456 res
= chrec_dont_know
;
2458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2459 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2461 exit
= single_exit (loop
);
2465 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2468 type
= TREE_TYPE (niter_desc
.niter
);
2469 if (integer_nonzerop (niter_desc
.may_be_zero
))
2470 res
= build_int_cst (type
, 0);
2471 else if (integer_zerop (niter_desc
.may_be_zero
))
2472 res
= niter_desc
.niter
;
2474 res
= chrec_dont_know
;
2477 return set_nb_iterations_in_loop (loop
, res
);
2480 /* Returns the number of executions of the exit condition of LOOP,
2481 i.e., the number by one higher than number_of_latch_executions.
2482 Note that unline number_of_latch_executions, this number does
2483 not necessarily fit in the unsigned variant of the type of
2484 the control variable -- if the number of iterations is a constant,
2485 we return chrec_dont_know if adding one to number_of_latch_executions
2486 overflows; however, in case the number of iterations is symbolic
2487 expression, the caller is responsible for dealing with this
2488 the possible overflow. */
2491 number_of_exit_cond_executions (struct loop
*loop
)
2493 tree ret
= number_of_latch_executions (loop
);
2494 tree type
= chrec_type (ret
);
2496 if (chrec_contains_undetermined (ret
))
2499 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2500 if (TREE_CODE (ret
) == INTEGER_CST
2501 && TREE_OVERFLOW (ret
))
2502 return chrec_dont_know
;
2507 /* One of the drivers for testing the scalar evolutions analysis.
2508 This function computes the number of iterations for all the loops
2509 from the EXIT_CONDITIONS array. */
2512 number_of_iterations_for_all_loops (VEC(tree
,heap
) **exit_conditions
)
2515 unsigned nb_chrec_dont_know_loops
= 0;
2516 unsigned nb_static_loops
= 0;
2519 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2521 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2522 if (chrec_contains_undetermined (res
))
2523 nb_chrec_dont_know_loops
++;
2530 fprintf (dump_file
, "\n(\n");
2531 fprintf (dump_file
, "-----------------------------------------\n");
2532 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2533 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2534 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2535 fprintf (dump_file
, "-----------------------------------------\n");
2536 fprintf (dump_file
, ")\n\n");
2538 print_loop_ir (dump_file
);
2544 /* Counters for the stats. */
2550 unsigned nb_affine_multivar
;
2551 unsigned nb_higher_poly
;
2552 unsigned nb_chrec_dont_know
;
2553 unsigned nb_undetermined
;
2556 /* Reset the counters. */
2559 reset_chrecs_counters (struct chrec_stats
*stats
)
2561 stats
->nb_chrecs
= 0;
2562 stats
->nb_affine
= 0;
2563 stats
->nb_affine_multivar
= 0;
2564 stats
->nb_higher_poly
= 0;
2565 stats
->nb_chrec_dont_know
= 0;
2566 stats
->nb_undetermined
= 0;
2569 /* Dump the contents of a CHREC_STATS structure. */
2572 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2574 fprintf (file
, "\n(\n");
2575 fprintf (file
, "-----------------------------------------\n");
2576 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2577 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2578 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2579 stats
->nb_higher_poly
);
2580 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2581 fprintf (file
, "-----------------------------------------\n");
2582 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2583 fprintf (file
, "%d\twith undetermined coefficients\n",
2584 stats
->nb_undetermined
);
2585 fprintf (file
, "-----------------------------------------\n");
2586 fprintf (file
, "%d\tchrecs in the scev database\n",
2587 (int) htab_elements (scalar_evolution_info
));
2588 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2589 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2590 fprintf (file
, "-----------------------------------------\n");
2591 fprintf (file
, ")\n\n");
2594 /* Gather statistics about CHREC. */
2597 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2599 if (dump_file
&& (dump_flags
& TDF_STATS
))
2601 fprintf (dump_file
, "(classify_chrec ");
2602 print_generic_expr (dump_file
, chrec
, 0);
2603 fprintf (dump_file
, "\n");
2608 if (chrec
== NULL_TREE
)
2610 stats
->nb_undetermined
++;
2614 switch (TREE_CODE (chrec
))
2616 case POLYNOMIAL_CHREC
:
2617 if (evolution_function_is_affine_p (chrec
))
2619 if (dump_file
&& (dump_flags
& TDF_STATS
))
2620 fprintf (dump_file
, " affine_univariate\n");
2623 else if (evolution_function_is_affine_multivariate_p (chrec
))
2625 if (dump_file
&& (dump_flags
& TDF_STATS
))
2626 fprintf (dump_file
, " affine_multivariate\n");
2627 stats
->nb_affine_multivar
++;
2631 if (dump_file
&& (dump_flags
& TDF_STATS
))
2632 fprintf (dump_file
, " higher_degree_polynomial\n");
2633 stats
->nb_higher_poly
++;
2642 if (chrec_contains_undetermined (chrec
))
2644 if (dump_file
&& (dump_flags
& TDF_STATS
))
2645 fprintf (dump_file
, " undetermined\n");
2646 stats
->nb_undetermined
++;
2649 if (dump_file
&& (dump_flags
& TDF_STATS
))
2650 fprintf (dump_file
, ")\n");
2653 /* One of the drivers for testing the scalar evolutions analysis.
2654 This function analyzes the scalar evolution of all the scalars
2655 defined as loop phi nodes in one of the loops from the
2656 EXIT_CONDITIONS array.
2658 TODO Optimization: A loop is in canonical form if it contains only
2659 a single scalar loop phi node. All the other scalars that have an
2660 evolution in the loop are rewritten in function of this single
2661 index. This allows the parallelization of the loop. */
2664 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree
,heap
) **exit_conditions
)
2667 struct chrec_stats stats
;
2670 reset_chrecs_counters (&stats
);
2672 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2678 loop
= loop_containing_stmt (cond
);
2681 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2682 if (is_gimple_reg (PHI_RESULT (phi
)))
2684 chrec
= instantiate_parameters
2686 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2688 if (dump_file
&& (dump_flags
& TDF_STATS
))
2689 gather_chrec_stats (chrec
, &stats
);
2693 if (dump_file
&& (dump_flags
& TDF_STATS
))
2694 dump_chrecs_stats (dump_file
, &stats
);
2697 /* Callback for htab_traverse, gathers information on chrecs in the
2701 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2703 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2705 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2710 /* Classify the chrecs of the whole database. */
2713 gather_stats_on_scev_database (void)
2715 struct chrec_stats stats
;
2720 reset_chrecs_counters (&stats
);
2722 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2725 dump_chrecs_stats (dump_file
, &stats
);
2733 initialize_scalar_evolutions_analyzer (void)
2735 /* The elements below are unique. */
2736 if (chrec_dont_know
== NULL_TREE
)
2738 chrec_not_analyzed_yet
= NULL_TREE
;
2739 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2740 chrec_known
= make_node (SCEV_KNOWN
);
2741 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2742 TREE_TYPE (chrec_known
) = void_type_node
;
2746 /* Initialize the analysis of scalar evolutions for LOOPS. */
2749 scev_initialize (void)
2754 scalar_evolution_info
= htab_create (100, hash_scev_info
,
2755 eq_scev_info
, del_scev_info
);
2756 already_instantiated
= BITMAP_ALLOC (NULL
);
2758 initialize_scalar_evolutions_analyzer ();
2760 FOR_EACH_LOOP (li
, loop
, 0)
2762 loop
->nb_iterations
= NULL_TREE
;
2766 /* Cleans up the information cached by the scalar evolutions analysis. */
2774 if (!scalar_evolution_info
|| !current_loops
)
2777 htab_empty (scalar_evolution_info
);
2778 FOR_EACH_LOOP (li
, loop
, 0)
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
->step
= build_int_cst (TREE_TYPE (ev
), 0);
2817 iv
->no_overflow
= true;
2821 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2822 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2825 iv
->step
= CHREC_RIGHT (ev
);
2826 if (allow_nonconstant_step
)
2828 if (tree_contains_chrecs (iv
->step
, NULL
)
2829 || chrec_contains_symbols_defined_in_loop (iv
->step
, loop
->num
))
2832 else if (TREE_CODE (iv
->step
) != INTEGER_CST
)
2835 iv
->base
= CHREC_LEFT (ev
);
2836 if (tree_contains_chrecs (iv
->base
, NULL
)
2837 || chrec_contains_symbols_defined_in_loop (iv
->base
, loop
->num
))
2840 iv
->no_overflow
= (!folded_casts
2842 && !TYPE_UNSIGNED (type
));
2846 /* Runs the analysis of scalar evolutions. */
2849 scev_analysis (void)
2851 VEC(tree
,heap
) *exit_conditions
;
2853 exit_conditions
= VEC_alloc (tree
, heap
, 37);
2854 select_loops_exit_conditions (&exit_conditions
);
2856 if (dump_file
&& (dump_flags
& TDF_STATS
))
2857 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2859 number_of_iterations_for_all_loops (&exit_conditions
);
2860 VEC_free (tree
, heap
, exit_conditions
);
2863 /* Finalize the scalar evolution analysis. */
2866 scev_finalize (void)
2868 htab_delete (scalar_evolution_info
);
2869 BITMAP_FREE (already_instantiated
);
2872 /* Returns true if EXPR looks expensive. */
2875 expression_expensive_p (tree expr
)
2877 return force_expr_to_var_cost (expr
) >= target_spill_cost
;
2880 /* Replace ssa names for that scev can prove they are constant by the
2881 appropriate constants. Also perform final value replacement in loops,
2882 in case the replacement expressions are cheap.
2884 We only consider SSA names defined by phi nodes; rest is left to the
2885 ordinary constant propagation pass. */
2888 scev_const_prop (void)
2891 tree name
, phi
, next_phi
, type
, ev
;
2892 struct loop
*loop
, *ex_loop
;
2893 bitmap ssa_names_to_remove
= NULL
;
2902 loop
= bb
->loop_father
;
2904 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2906 name
= PHI_RESULT (phi
);
2908 if (!is_gimple_reg (name
))
2911 type
= TREE_TYPE (name
);
2913 if (!POINTER_TYPE_P (type
)
2914 && !INTEGRAL_TYPE_P (type
))
2917 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
2918 if (!is_gimple_min_invariant (ev
)
2919 || !may_propagate_copy (name
, ev
))
2922 /* Replace the uses of the name. */
2924 replace_uses_by (name
, ev
);
2926 if (!ssa_names_to_remove
)
2927 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
2928 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
2932 /* Remove the ssa names that were replaced by constants. We do not
2933 remove them directly in the previous cycle, since this
2934 invalidates scev cache. */
2935 if (ssa_names_to_remove
)
2939 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
2941 name
= ssa_name (i
);
2942 phi
= SSA_NAME_DEF_STMT (name
);
2944 gcc_assert (TREE_CODE (phi
) == PHI_NODE
);
2945 remove_phi_node (phi
, NULL
, true);
2948 BITMAP_FREE (ssa_names_to_remove
);
2952 /* Now the regular final value replacement. */
2953 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
2956 tree def
, rslt
, ass
, niter
;
2957 block_stmt_iterator bsi
;
2959 /* If we do not know exact number of iterations of the loop, we cannot
2960 replace the final value. */
2961 exit
= single_exit (loop
);
2965 niter
= number_of_latch_executions (loop
);
2966 if (niter
== chrec_dont_know
2967 /* If computing the number of iterations is expensive, it may be
2968 better not to introduce computations involving it. */
2969 || expression_expensive_p (niter
))
2972 /* Ensure that it is possible to insert new statements somewhere. */
2973 if (!single_pred_p (exit
->dest
))
2974 split_loop_exit_edge (exit
);
2975 tree_block_label (exit
->dest
);
2976 bsi
= bsi_after_labels (exit
->dest
);
2978 ex_loop
= superloop_at_depth (loop
, exit
->dest
->loop_father
->depth
+ 1);
2980 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= next_phi
)
2982 next_phi
= PHI_CHAIN (phi
);
2983 rslt
= PHI_RESULT (phi
);
2984 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2985 if (!is_gimple_reg (def
))
2988 if (!POINTER_TYPE_P (TREE_TYPE (def
))
2989 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
2992 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
2993 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
2994 if (!tree_does_not_contain_chrecs (def
)
2995 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
2996 /* Moving the computation from the loop may prolong life range
2997 of some ssa names, which may cause problems if they appear
2998 on abnormal edges. */
2999 || contains_abnormal_ssa_name_p (def
))
3002 /* Eliminate the PHI node and replace it by a computation outside
3004 def
= unshare_expr (def
);
3005 remove_phi_node (phi
, NULL_TREE
, false);
3007 ass
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
, rslt
, NULL_TREE
);
3008 SSA_NAME_DEF_STMT (rslt
) = ass
;
3010 block_stmt_iterator dest
= bsi
;
3011 bsi_insert_before (&dest
, ass
, BSI_NEW_STMT
);
3012 def
= force_gimple_operand_bsi (&dest
, def
, false, NULL_TREE
);
3014 GIMPLE_STMT_OPERAND (ass
, 1) = def
;