1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
4 Contributed by Sebastian Pop <s.pop@laposte.net>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
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_ASSIGN: 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 (loop_1, {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 2a: 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 2b: Multivariate chains of recurrences.
171 Analyzing the access function of array A with
172 instantiate_parameters (loop_1, "j + k"), we obtain the
173 instantiation and the analysis of the scalar variables "j" and "k"
174 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
175 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
176 {0, +, 1}_1. To obtain the evolution function in loop_3 and
177 instantiate the scalar variables up to loop_1, one has to use:
178 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
179 The result of this call is {{0, +, 1}_1, +, 1}_2.
181 Example 3: Higher degree polynomials.
195 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
196 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
198 Example 4: Lucas, Fibonacci, or mixers in general.
210 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
211 following semantics: during the first iteration of the loop_1, the
212 variable contains the value 1, and then it contains the value "c".
213 Note that this syntax is close to the syntax of the loop-phi-node:
214 "a -> (1, c)_1" vs. "a = phi (1, c)".
216 The symbolic chrec representation contains all the semantics of the
217 original code. What is more difficult is to use this information.
219 Example 5: Flip-flops, or exchangers.
231 Based on these symbolic chrecs, it is possible to refine this
232 information into the more precise PERIODIC_CHRECs:
237 This transformation is not yet implemented.
241 You can find a more detailed description of the algorithm in:
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
243 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
244 this is a preliminary report and some of the details of the
245 algorithm have changed. I'm working on a research report that
246 updates the description of the algorithms to reflect the design
247 choices used in this implementation.
249 A set of slides show a high level overview of the algorithm and run
250 an example through the scalar evolution analyzer:
251 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
253 The slides that I have presented at the GCC Summit'04 are available
254 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
259 #include "coretypes.h"
265 /* These RTL headers are needed for basic-block.h. */
267 #include "basic-block.h"
268 #include "diagnostic.h"
269 #include "tree-flow.h"
270 #include "tree-dump.h"
273 #include "tree-chrec.h"
274 #include "tree-scalar-evolution.h"
275 #include "tree-pass.h"
279 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
281 /* The cached information about an SSA name VAR, claiming that below
282 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
285 struct scev_info_str
GTY(())
287 basic_block instantiated_below
;
292 /* Counters for the scev database. */
293 static unsigned nb_set_scev
= 0;
294 static unsigned nb_get_scev
= 0;
296 /* The following trees are unique elements. Thus the comparison of
297 another element to these elements should be done on the pointer to
298 these trees, and not on their value. */
300 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
301 tree chrec_not_analyzed_yet
;
303 /* Reserved to the cases where the analyzer has detected an
304 undecidable property at compile time. */
305 tree chrec_dont_know
;
307 /* When the analyzer has detected that a property will never
308 happen, then it qualifies it with chrec_known. */
311 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
314 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
316 static inline struct scev_info_str
*
317 new_scev_info_str (basic_block instantiated_below
, tree var
)
319 struct scev_info_str
*res
;
321 res
= GGC_NEW (struct scev_info_str
);
323 res
->chrec
= chrec_not_analyzed_yet
;
324 res
->instantiated_below
= instantiated_below
;
329 /* Computes a hash function for database element ELT. */
332 hash_scev_info (const void *elt
)
334 return SSA_NAME_VERSION (((const struct scev_info_str
*) elt
)->var
);
337 /* Compares database elements E1 and E2. */
340 eq_scev_info (const void *e1
, const void *e2
)
342 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
343 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
345 return (elt1
->var
== elt2
->var
346 && elt1
->instantiated_below
== elt2
->instantiated_below
);
349 /* Deletes database element E. */
352 del_scev_info (void *e
)
357 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
358 A first query on VAR returns chrec_not_analyzed_yet. */
361 find_var_scev_info (basic_block instantiated_below
, tree var
)
363 struct scev_info_str
*res
;
364 struct scev_info_str tmp
;
368 tmp
.instantiated_below
= instantiated_below
;
369 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
372 *slot
= new_scev_info_str (instantiated_below
, var
);
373 res
= (struct scev_info_str
*) *slot
;
378 /* Return true when CHREC contains symbolic names defined in
382 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
386 if (chrec
== NULL_TREE
)
389 if (is_gimple_min_invariant (chrec
))
392 if (TREE_CODE (chrec
) == VAR_DECL
393 || TREE_CODE (chrec
) == PARM_DECL
394 || TREE_CODE (chrec
) == FUNCTION_DECL
395 || TREE_CODE (chrec
) == LABEL_DECL
396 || TREE_CODE (chrec
) == RESULT_DECL
397 || TREE_CODE (chrec
) == FIELD_DECL
)
400 if (TREE_CODE (chrec
) == SSA_NAME
)
402 gimple def
= SSA_NAME_DEF_STMT (chrec
);
403 struct loop
*def_loop
= loop_containing_stmt (def
);
404 struct loop
*loop
= get_loop (loop_nb
);
406 if (def_loop
== NULL
)
409 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
415 n
= TREE_OPERAND_LENGTH (chrec
);
416 for (i
= 0; i
< n
; i
++)
417 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
423 /* Return true when PHI is a loop-phi-node. */
426 loop_phi_node_p (gimple phi
)
428 /* The implementation of this function is based on the following
429 property: "all the loop-phi-nodes of a loop are contained in the
430 loop's header basic block". */
432 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
435 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
436 In general, in the case of multivariate evolutions we want to get
437 the evolution in different loops. LOOP specifies the level for
438 which to get the evolution.
442 | for (j = 0; j < 100; j++)
444 | for (k = 0; k < 100; k++)
446 | i = k + j; - Here the value of i is a function of j, k.
448 | ... = i - Here the value of i is a function of j.
450 | ... = i - Here the value of i is a scalar.
456 | i_1 = phi (i_0, i_2)
460 This loop has the same effect as:
461 LOOP_1 has the same effect as:
465 The overall effect of the loop, "i_0 + 20" in the previous example,
466 is obtained by passing in the parameters: LOOP = 1,
467 EVOLUTION_FN = {i_0, +, 2}_1.
471 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
475 if (evolution_fn
== chrec_dont_know
)
476 return chrec_dont_know
;
478 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
480 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
482 if (inner_loop
== loop
483 || flow_loop_nested_p (loop
, inner_loop
))
485 tree nb_iter
= number_of_latch_executions (inner_loop
);
487 if (nb_iter
== chrec_dont_know
)
488 return chrec_dont_know
;
493 /* evolution_fn is the evolution function in LOOP. Get
494 its value in the nb_iter-th iteration. */
495 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
497 /* Continue the computation until ending on a parent of LOOP. */
498 return compute_overall_effect_of_inner_loop (loop
, res
);
505 /* If the evolution function is an invariant, there is nothing to do. */
506 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
510 return chrec_dont_know
;
513 /* Determine whether the CHREC is always positive/negative. If the expression
514 cannot be statically analyzed, return false, otherwise set the answer into
518 chrec_is_positive (tree chrec
, bool *value
)
520 bool value0
, value1
, value2
;
521 tree end_value
, nb_iter
;
523 switch (TREE_CODE (chrec
))
525 case POLYNOMIAL_CHREC
:
526 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
527 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
530 /* FIXME -- overflows. */
531 if (value0
== value1
)
537 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
538 and the proof consists in showing that the sign never
539 changes during the execution of the loop, from 0 to
540 loop->nb_iterations. */
541 if (!evolution_function_is_affine_p (chrec
))
544 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
545 if (chrec_contains_undetermined (nb_iter
))
549 /* TODO -- If the test is after the exit, we may decrease the number of
550 iterations by one. */
552 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
555 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
557 if (!chrec_is_positive (end_value
, &value2
))
561 return value0
== value1
;
564 *value
= (tree_int_cst_sgn (chrec
) == 1);
572 /* Associate CHREC to SCALAR. */
575 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
579 if (TREE_CODE (scalar
) != SSA_NAME
)
582 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
586 if (dump_flags
& TDF_DETAILS
)
588 fprintf (dump_file
, "(set_scalar_evolution \n");
589 fprintf (dump_file
, " instantiated_below = %d \n",
590 instantiated_below
->index
);
591 fprintf (dump_file
, " (scalar = ");
592 print_generic_expr (dump_file
, scalar
, 0);
593 fprintf (dump_file
, ")\n (scalar_evolution = ");
594 print_generic_expr (dump_file
, chrec
, 0);
595 fprintf (dump_file
, "))\n");
597 if (dump_flags
& TDF_STATS
)
601 *scalar_info
= chrec
;
604 /* Retrieve the chrec associated to SCALAR instantiated below
605 INSTANTIATED_BELOW block. */
608 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
614 if (dump_flags
& TDF_DETAILS
)
616 fprintf (dump_file
, "(get_scalar_evolution \n");
617 fprintf (dump_file
, " (scalar = ");
618 print_generic_expr (dump_file
, scalar
, 0);
619 fprintf (dump_file
, ")\n");
621 if (dump_flags
& TDF_STATS
)
625 switch (TREE_CODE (scalar
))
628 res
= *find_var_scev_info (instantiated_below
, scalar
);
638 res
= chrec_not_analyzed_yet
;
642 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
644 fprintf (dump_file
, " (scalar_evolution = ");
645 print_generic_expr (dump_file
, res
, 0);
646 fprintf (dump_file
, "))\n");
652 /* Helper function for add_to_evolution. Returns the evolution
653 function for an assignment of the form "a = b + c", where "a" and
654 "b" are on the strongly connected component. CHREC_BEFORE is the
655 information that we already have collected up to this point.
656 TO_ADD is the evolution of "c".
658 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
659 evolution the expression TO_ADD, otherwise construct an evolution
660 part for this loop. */
663 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
666 tree type
, left
, right
;
667 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
669 switch (TREE_CODE (chrec_before
))
671 case POLYNOMIAL_CHREC
:
672 chloop
= get_chrec_loop (chrec_before
);
674 || flow_loop_nested_p (chloop
, loop
))
678 type
= chrec_type (chrec_before
);
680 /* When there is no evolution part in this loop, build it. */
685 right
= SCALAR_FLOAT_TYPE_P (type
)
686 ? build_real (type
, dconst0
)
687 : build_int_cst (type
, 0);
691 var
= CHREC_VARIABLE (chrec_before
);
692 left
= CHREC_LEFT (chrec_before
);
693 right
= CHREC_RIGHT (chrec_before
);
696 to_add
= chrec_convert (type
, to_add
, at_stmt
);
697 right
= chrec_convert_rhs (type
, right
, at_stmt
);
698 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
699 return build_polynomial_chrec (var
, left
, right
);
703 gcc_assert (flow_loop_nested_p (loop
, chloop
));
705 /* Search the evolution in LOOP_NB. */
706 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
708 right
= CHREC_RIGHT (chrec_before
);
709 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
710 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
715 /* These nodes do not depend on a loop. */
716 if (chrec_before
== chrec_dont_know
)
717 return chrec_dont_know
;
720 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
721 return build_polynomial_chrec (loop_nb
, left
, right
);
725 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
728 Description (provided for completeness, for those who read code in
729 a plane, and for my poor 62 bytes brain that would have forgotten
730 all this in the next two or three months):
732 The algorithm of translation of programs from the SSA representation
733 into the chrecs syntax is based on a pattern matching. After having
734 reconstructed the overall tree expression for a loop, there are only
735 two cases that can arise:
737 1. a = loop-phi (init, a + expr)
738 2. a = loop-phi (init, expr)
740 where EXPR is either a scalar constant with respect to the analyzed
741 loop (this is a degree 0 polynomial), or an expression containing
742 other loop-phi definitions (these are higher degree polynomials).
749 | a = phi (init, a + 5)
756 | a = phi (inita, 2 * b + 3)
757 | b = phi (initb, b + 1)
760 For the first case, the semantics of the SSA representation is:
762 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
764 that is, there is a loop index "x" that determines the scalar value
765 of the variable during the loop execution. During the first
766 iteration, the value is that of the initial condition INIT, while
767 during the subsequent iterations, it is the sum of the initial
768 condition with the sum of all the values of EXPR from the initial
769 iteration to the before last considered iteration.
771 For the second case, the semantics of the SSA program is:
773 | a (x) = init, if x = 0;
774 | expr (x - 1), otherwise.
776 The second case corresponds to the PEELED_CHREC, whose syntax is
777 close to the syntax of a loop-phi-node:
779 | phi (init, expr) vs. (init, expr)_x
781 The proof of the translation algorithm for the first case is a
782 proof by structural induction based on the degree of EXPR.
785 When EXPR is a constant with respect to the analyzed loop, or in
786 other words when EXPR is a polynomial of degree 0, the evolution of
787 the variable A in the loop is an affine function with an initial
788 condition INIT, and a step EXPR. In order to show this, we start
789 from the semantics of the SSA representation:
791 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
793 and since "expr (j)" is a constant with respect to "j",
795 f (x) = init + x * expr
797 Finally, based on the semantics of the pure sum chrecs, by
798 identification we get the corresponding chrecs syntax:
800 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
801 f (x) -> {init, +, expr}_x
804 Suppose that EXPR is a polynomial of degree N with respect to the
805 analyzed loop_x for which we have already determined that it is
806 written under the chrecs syntax:
808 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
810 We start from the semantics of the SSA program:
812 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
814 | f (x) = init + \sum_{j = 0}^{x - 1}
815 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
817 | f (x) = init + \sum_{j = 0}^{x - 1}
818 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
820 | f (x) = init + \sum_{k = 0}^{n - 1}
821 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
823 | f (x) = init + \sum_{k = 0}^{n - 1}
824 | (b_k * \binom{x}{k + 1})
826 | f (x) = init + b_0 * \binom{x}{1} + ...
827 | + b_{n-1} * \binom{x}{n}
829 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
830 | + b_{n-1} * \binom{x}{n}
833 And finally from the definition of the chrecs syntax, we identify:
834 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
836 This shows the mechanism that stands behind the add_to_evolution
837 function. An important point is that the use of symbolic
838 parameters avoids the need of an analysis schedule.
845 | a = phi (inita, a + 2 + b)
846 | b = phi (initb, b + 1)
849 When analyzing "a", the algorithm keeps "b" symbolically:
851 | a -> {inita, +, 2 + b}_1
853 Then, after instantiation, the analyzer ends on the evolution:
855 | a -> {inita, +, 2 + initb, +, 1}_1
860 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
861 tree to_add
, gimple at_stmt
)
863 tree type
= chrec_type (to_add
);
864 tree res
= NULL_TREE
;
866 if (to_add
== NULL_TREE
)
869 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
870 instantiated at this point. */
871 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
872 /* This should not happen. */
873 return chrec_dont_know
;
875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
877 fprintf (dump_file
, "(add_to_evolution \n");
878 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
879 fprintf (dump_file
, " (chrec_before = ");
880 print_generic_expr (dump_file
, chrec_before
, 0);
881 fprintf (dump_file
, ")\n (to_add = ");
882 print_generic_expr (dump_file
, to_add
, 0);
883 fprintf (dump_file
, ")\n");
886 if (code
== MINUS_EXPR
)
887 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
888 ? build_real (type
, dconstm1
)
889 : build_int_cst_type (type
, -1));
891 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
895 fprintf (dump_file
, " (res = ");
896 print_generic_expr (dump_file
, res
, 0);
897 fprintf (dump_file
, "))\n");
903 /* Helper function. */
906 set_nb_iterations_in_loop (struct loop
*loop
,
909 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
911 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
912 print_generic_expr (dump_file
, res
, 0);
913 fprintf (dump_file
, "))\n");
916 loop
->nb_iterations
= res
;
922 /* This section selects the loops that will be good candidates for the
923 scalar evolution analysis. For the moment, greedily select all the
924 loop nests we could analyze. */
926 /* For a loop with a single exit edge, return the COND_EXPR that
927 guards the exit edge. If the expression is too difficult to
928 analyze, then give up. */
931 get_loop_exit_condition (const struct loop
*loop
)
934 edge exit_edge
= single_exit (loop
);
936 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
937 fprintf (dump_file
, "(get_loop_exit_condition \n ");
943 stmt
= last_stmt (exit_edge
->src
);
944 if (gimple_code (stmt
) == GIMPLE_COND
)
948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
950 print_gimple_stmt (dump_file
, res
, 0, 0);
951 fprintf (dump_file
, ")\n");
957 /* Recursively determine and enqueue the exit conditions for a loop. */
960 get_exit_conditions_rec (struct loop
*loop
,
961 VEC(gimple
,heap
) **exit_conditions
)
966 /* Recurse on the inner loops, then on the next (sibling) loops. */
967 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
968 get_exit_conditions_rec (loop
->next
, exit_conditions
);
970 if (single_exit (loop
))
972 gimple loop_condition
= get_loop_exit_condition (loop
);
975 VEC_safe_push (gimple
, heap
, *exit_conditions
, loop_condition
);
979 /* Select the candidate loop nests for the analysis. This function
980 initializes the EXIT_CONDITIONS array. */
983 select_loops_exit_conditions (VEC(gimple
,heap
) **exit_conditions
)
985 struct loop
*function_body
= current_loops
->tree_root
;
987 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
991 /* Depth first search algorithm. */
993 typedef enum t_bool
{
1000 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
1002 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
1003 Return true if the strongly connected component has been found. */
1006 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
1007 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
1008 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1010 t_bool res
= t_false
;
1015 case POINTER_PLUS_EXPR
:
1017 if (TREE_CODE (rhs0
) == SSA_NAME
)
1019 if (TREE_CODE (rhs1
) == SSA_NAME
)
1021 /* Match an assignment under the form:
1024 /* We want only assignments of form "name + name" contribute to
1025 LIMIT, as the other cases do not necessarily contribute to
1026 the complexity of the expression. */
1029 evol
= *evolution_of_loop
;
1030 res
= follow_ssa_edge
1031 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
1034 *evolution_of_loop
= add_to_evolution
1036 chrec_convert (type
, evol
, at_stmt
),
1037 code
, rhs1
, at_stmt
);
1039 else if (res
== t_false
)
1041 res
= follow_ssa_edge
1042 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1043 evolution_of_loop
, limit
);
1046 *evolution_of_loop
= add_to_evolution
1048 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1049 code
, rhs0
, at_stmt
);
1051 else if (res
== t_dont_know
)
1052 *evolution_of_loop
= chrec_dont_know
;
1055 else if (res
== t_dont_know
)
1056 *evolution_of_loop
= chrec_dont_know
;
1061 /* Match an assignment under the form:
1063 res
= follow_ssa_edge
1064 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1065 evolution_of_loop
, limit
);
1067 *evolution_of_loop
= add_to_evolution
1068 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1070 code
, rhs1
, at_stmt
);
1072 else if (res
== t_dont_know
)
1073 *evolution_of_loop
= chrec_dont_know
;
1077 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1079 /* Match an assignment under the form:
1081 res
= follow_ssa_edge
1082 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1083 evolution_of_loop
, limit
);
1085 *evolution_of_loop
= add_to_evolution
1086 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1088 code
, rhs0
, at_stmt
);
1090 else if (res
== t_dont_know
)
1091 *evolution_of_loop
= chrec_dont_know
;
1095 /* Otherwise, match an assignment under the form:
1097 /* And there is nothing to do. */
1102 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1103 if (TREE_CODE (rhs0
) == SSA_NAME
)
1105 /* Match an assignment under the form:
1108 /* We want only assignments of form "name - name" contribute to
1109 LIMIT, as the other cases do not necessarily contribute to
1110 the complexity of the expression. */
1111 if (TREE_CODE (rhs1
) == SSA_NAME
)
1114 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1115 evolution_of_loop
, limit
);
1117 *evolution_of_loop
= add_to_evolution
1118 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1119 MINUS_EXPR
, rhs1
, at_stmt
);
1121 else if (res
== t_dont_know
)
1122 *evolution_of_loop
= chrec_dont_know
;
1125 /* Otherwise, match an assignment under the form:
1127 /* And there is nothing to do. */
1138 /* Follow the ssa edge into the expression EXPR.
1139 Return true if the strongly connected component has been found. */
1142 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1143 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1145 t_bool res
= t_false
;
1147 tree type
= TREE_TYPE (expr
);
1148 enum tree_code code
;
1150 /* The EXPR is one of the following cases:
1154 - a POINTER_PLUS_EXPR,
1157 - other cases are not yet handled. */
1158 code
= TREE_CODE (expr
);
1162 /* This assignment is under the form "a_1 = (cast) rhs. */
1163 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1164 halting_phi
, evolution_of_loop
, limit
);
1165 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1169 /* This assignment is under the form "a_1 = 7". */
1174 /* This assignment is under the form: "a_1 = b_2". */
1175 res
= follow_ssa_edge
1176 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1179 case POINTER_PLUS_EXPR
:
1182 /* This case is under the form "rhs0 +- rhs1". */
1183 rhs0
= TREE_OPERAND (expr
, 0);
1184 rhs1
= TREE_OPERAND (expr
, 1);
1185 STRIP_TYPE_NOPS (rhs0
);
1186 STRIP_TYPE_NOPS (rhs1
);
1187 return follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1188 halting_phi
, evolution_of_loop
, limit
);
1192 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1193 It must be handled as a copy assignment of the form a_1 = a_2. */
1194 tree op0
= ASSERT_EXPR_VAR (expr
);
1195 if (TREE_CODE (op0
) == SSA_NAME
)
1196 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1197 halting_phi
, evolution_of_loop
, limit
);
1212 /* Follow the ssa edge into the right hand side of an assignment STMT.
1213 Return true if the strongly connected component has been found. */
1216 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1217 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1219 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1220 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1222 switch (get_gimple_rhs_class (code
))
1224 case GIMPLE_BINARY_RHS
:
1225 return follow_ssa_edge_binary (loop
, stmt
, type
,
1226 gimple_assign_rhs1 (stmt
), code
,
1227 gimple_assign_rhs2 (stmt
),
1228 halting_phi
, evolution_of_loop
, limit
);
1229 case GIMPLE_SINGLE_RHS
:
1230 return follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1231 halting_phi
, evolution_of_loop
, limit
);
1237 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1240 backedge_phi_arg_p (gimple phi
, int i
)
1242 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1244 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1245 about updating it anywhere, and this should work as well most of the
1247 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1253 /* Helper function for one branch of the condition-phi-node. Return
1254 true if the strongly connected component has been found following
1257 static inline t_bool
1258 follow_ssa_edge_in_condition_phi_branch (int i
,
1260 gimple condition_phi
,
1262 tree
*evolution_of_branch
,
1263 tree init_cond
, int limit
)
1265 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1266 *evolution_of_branch
= chrec_dont_know
;
1268 /* Do not follow back edges (they must belong to an irreducible loop, which
1269 we really do not want to worry about). */
1270 if (backedge_phi_arg_p (condition_phi
, i
))
1273 if (TREE_CODE (branch
) == SSA_NAME
)
1275 *evolution_of_branch
= init_cond
;
1276 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1277 evolution_of_branch
, limit
);
1280 /* This case occurs when one of the condition branches sets
1281 the variable to a constant: i.e. a phi-node like
1282 "a_2 = PHI <a_7(5), 2(6)>;".
1284 FIXME: This case have to be refined correctly:
1285 in some cases it is possible to say something better than
1286 chrec_dont_know, for example using a wrap-around notation. */
1290 /* This function merges the branches of a condition-phi-node in a
1294 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1295 gimple condition_phi
,
1297 tree
*evolution_of_loop
, int limit
)
1300 tree init
= *evolution_of_loop
;
1301 tree evolution_of_branch
;
1302 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1304 &evolution_of_branch
,
1306 if (res
== t_false
|| res
== t_dont_know
)
1309 *evolution_of_loop
= evolution_of_branch
;
1311 /* If the phi node is just a copy, do not increase the limit. */
1312 n
= gimple_phi_num_args (condition_phi
);
1316 for (i
= 1; i
< n
; i
++)
1318 /* Quickly give up when the evolution of one of the branches is
1320 if (*evolution_of_loop
== chrec_dont_know
)
1323 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1325 &evolution_of_branch
,
1327 if (res
== t_false
|| res
== t_dont_know
)
1330 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1331 evolution_of_branch
);
1337 /* Follow an SSA edge in an inner loop. It computes the overall
1338 effect of the loop, and following the symbolic initial conditions,
1339 it follows the edges in the parent loop. The inner loop is
1340 considered as a single statement. */
1343 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1344 gimple loop_phi_node
,
1346 tree
*evolution_of_loop
, int limit
)
1348 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1349 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1351 /* Sometimes, the inner loop is too difficult to analyze, and the
1352 result of the analysis is a symbolic parameter. */
1353 if (ev
== PHI_RESULT (loop_phi_node
))
1355 t_bool res
= t_false
;
1356 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1358 for (i
= 0; i
< n
; i
++)
1360 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1363 /* Follow the edges that exit the inner loop. */
1364 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1365 if (!flow_bb_inside_loop_p (loop
, bb
))
1366 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1368 evolution_of_loop
, limit
);
1373 /* If the path crosses this loop-phi, give up. */
1375 *evolution_of_loop
= chrec_dont_know
;
1380 /* Otherwise, compute the overall effect of the inner loop. */
1381 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1382 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1383 evolution_of_loop
, limit
);
1386 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1387 path that is analyzed on the return walk. */
1390 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1391 tree
*evolution_of_loop
, int limit
)
1393 struct loop
*def_loop
;
1395 if (gimple_nop_p (def
))
1398 /* Give up if the path is longer than the MAX that we allow. */
1399 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1402 def_loop
= loop_containing_stmt (def
);
1404 switch (gimple_code (def
))
1407 if (!loop_phi_node_p (def
))
1408 /* DEF is a condition-phi-node. Follow the branches, and
1409 record their evolutions. Finally, merge the collected
1410 information and set the approximation to the main
1412 return follow_ssa_edge_in_condition_phi
1413 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1415 /* When the analyzed phi is the halting_phi, the
1416 depth-first search is over: we have found a path from
1417 the halting_phi to itself in the loop. */
1418 if (def
== halting_phi
)
1421 /* Otherwise, the evolution of the HALTING_PHI depends
1422 on the evolution of another loop-phi-node, i.e. the
1423 evolution function is a higher degree polynomial. */
1424 if (def_loop
== loop
)
1428 if (flow_loop_nested_p (loop
, def_loop
))
1429 return follow_ssa_edge_inner_loop_phi
1430 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1436 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1437 evolution_of_loop
, limit
);
1440 /* At this level of abstraction, the program is just a set
1441 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1442 other node to be handled. */
1449 /* Given a LOOP_PHI_NODE, this function determines the evolution
1450 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1453 analyze_evolution_in_loop (gimple loop_phi_node
,
1456 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1457 tree evolution_function
= chrec_not_analyzed_yet
;
1458 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1463 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1464 fprintf (dump_file
, " (loop_phi_node = ");
1465 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1466 fprintf (dump_file
, ")\n");
1469 for (i
= 0; i
< n
; i
++)
1471 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1476 /* Select the edges that enter the loop body. */
1477 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1478 if (!flow_bb_inside_loop_p (loop
, bb
))
1481 if (TREE_CODE (arg
) == SSA_NAME
)
1483 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1485 /* Pass in the initial condition to the follow edge function. */
1487 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1492 /* When it is impossible to go back on the same
1493 loop_phi_node by following the ssa edges, the
1494 evolution is represented by a peeled chrec, i.e. the
1495 first iteration, EV_FN has the value INIT_COND, then
1496 all the other iterations it has the value of ARG.
1497 For the moment, PEELED_CHREC nodes are not built. */
1499 ev_fn
= chrec_dont_know
;
1501 /* When there are multiple back edges of the loop (which in fact never
1502 happens currently, but nevertheless), merge their evolutions. */
1503 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1506 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1508 fprintf (dump_file
, " (evolution_function = ");
1509 print_generic_expr (dump_file
, evolution_function
, 0);
1510 fprintf (dump_file
, "))\n");
1513 return evolution_function
;
1516 /* Given a loop-phi-node, return the initial conditions of the
1517 variable on entry of the loop. When the CCP has propagated
1518 constants into the loop-phi-node, the initial condition is
1519 instantiated, otherwise the initial condition is kept symbolic.
1520 This analyzer does not analyze the evolution outside the current
1521 loop, and leaves this task to the on-demand tree reconstructor. */
1524 analyze_initial_condition (gimple loop_phi_node
)
1527 tree init_cond
= chrec_not_analyzed_yet
;
1528 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1530 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1532 fprintf (dump_file
, "(analyze_initial_condition \n");
1533 fprintf (dump_file
, " (loop_phi_node = \n");
1534 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1535 fprintf (dump_file
, ")\n");
1538 n
= gimple_phi_num_args (loop_phi_node
);
1539 for (i
= 0; i
< n
; i
++)
1541 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1542 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1544 /* When the branch is oriented to the loop's body, it does
1545 not contribute to the initial condition. */
1546 if (flow_bb_inside_loop_p (loop
, bb
))
1549 if (init_cond
== chrec_not_analyzed_yet
)
1555 if (TREE_CODE (branch
) == SSA_NAME
)
1557 init_cond
= chrec_dont_know
;
1561 init_cond
= chrec_merge (init_cond
, branch
);
1564 /* Ooops -- a loop without an entry??? */
1565 if (init_cond
== chrec_not_analyzed_yet
)
1566 init_cond
= chrec_dont_know
;
1568 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1570 fprintf (dump_file
, " (init_cond = ");
1571 print_generic_expr (dump_file
, init_cond
, 0);
1572 fprintf (dump_file
, "))\n");
1578 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1581 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1584 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1587 if (phi_loop
!= loop
)
1589 struct loop
*subloop
;
1590 tree evolution_fn
= analyze_scalar_evolution
1591 (phi_loop
, PHI_RESULT (loop_phi_node
));
1593 /* Dive one level deeper. */
1594 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1596 /* Interpret the subloop. */
1597 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1601 /* Otherwise really interpret the loop phi. */
1602 init_cond
= analyze_initial_condition (loop_phi_node
);
1603 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1608 /* This function merges the branches of a condition-phi-node,
1609 contained in the outermost loop, and whose arguments are already
1613 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1615 int i
, n
= gimple_phi_num_args (condition_phi
);
1616 tree res
= chrec_not_analyzed_yet
;
1618 for (i
= 0; i
< n
; i
++)
1622 if (backedge_phi_arg_p (condition_phi
, i
))
1624 res
= chrec_dont_know
;
1628 branch_chrec
= analyze_scalar_evolution
1629 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1631 res
= chrec_merge (res
, branch_chrec
);
1637 /* Interpret the operation RHS1 OP RHS2. If we didn't
1638 analyze this node before, follow the definitions until ending
1639 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1640 return path, this function propagates evolutions (ala constant copy
1641 propagation). OPND1 is not a GIMPLE expression because we could
1642 analyze the effect of an inner loop: see interpret_loop_phi. */
1645 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1646 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1648 tree res
, chrec1
, chrec2
;
1650 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1652 if (is_gimple_min_invariant (rhs1
))
1653 return chrec_convert (type
, rhs1
, at_stmt
);
1655 if (code
== SSA_NAME
)
1656 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1659 if (code
== ASSERT_EXPR
)
1661 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1662 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1666 return chrec_dont_know
;
1671 case POINTER_PLUS_EXPR
:
1672 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1673 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1674 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1675 chrec2
= chrec_convert (sizetype
, chrec2
, at_stmt
);
1676 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1680 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1681 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1682 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1683 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1684 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1688 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1689 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1690 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1691 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1692 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1696 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1697 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1698 /* TYPE may be integer, real or complex, so use fold_convert. */
1699 res
= chrec_fold_multiply (type
, chrec1
,
1700 fold_convert (type
, integer_minus_one_node
));
1704 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1705 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1706 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1707 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1708 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1712 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1713 res
= chrec_convert (type
, chrec1
, at_stmt
);
1717 res
= chrec_dont_know
;
1724 /* Interpret the expression EXPR. */
1727 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1729 enum tree_code code
;
1730 tree type
= TREE_TYPE (expr
), op0
, op1
;
1732 if (automatically_generated_chrec_p (expr
))
1735 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
)
1736 return chrec_dont_know
;
1738 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1740 return interpret_rhs_expr (loop
, at_stmt
, type
,
1744 /* Interpret the rhs of the assignment STMT. */
1747 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1749 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1750 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1752 return interpret_rhs_expr (loop
, stmt
, type
,
1753 gimple_assign_rhs1 (stmt
), code
,
1754 gimple_assign_rhs2 (stmt
));
1759 /* This section contains all the entry points:
1760 - number_of_iterations_in_loop,
1761 - analyze_scalar_evolution,
1762 - instantiate_parameters.
1765 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1766 common ancestor of DEF_LOOP and USE_LOOP. */
1769 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1770 struct loop
*def_loop
,
1774 if (def_loop
== wrto_loop
)
1777 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1778 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1780 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1783 /* Helper recursive function. */
1786 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1788 tree type
= TREE_TYPE (var
);
1791 struct loop
*def_loop
;
1793 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1794 return chrec_dont_know
;
1796 if (TREE_CODE (var
) != SSA_NAME
)
1797 return interpret_expr (loop
, NULL
, var
);
1799 def
= SSA_NAME_DEF_STMT (var
);
1800 bb
= gimple_bb (def
);
1801 def_loop
= bb
? bb
->loop_father
: NULL
;
1804 || !flow_bb_inside_loop_p (loop
, bb
))
1806 /* Keep the symbolic form. */
1811 if (res
!= chrec_not_analyzed_yet
)
1813 if (loop
!= bb
->loop_father
)
1814 res
= compute_scalar_evolution_in_loop
1815 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1820 if (loop
!= def_loop
)
1822 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1823 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1828 switch (gimple_code (def
))
1831 res
= interpret_gimple_assign (loop
, def
);
1835 if (loop_phi_node_p (def
))
1836 res
= interpret_loop_phi (loop
, def
);
1838 res
= interpret_condition_phi (loop
, def
);
1842 res
= chrec_dont_know
;
1848 /* Keep the symbolic form. */
1849 if (res
== chrec_dont_know
)
1852 if (loop
== def_loop
)
1853 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1858 /* Entry point for the scalar evolution analyzer.
1859 Analyzes and returns the scalar evolution of the ssa_name VAR.
1860 LOOP_NB is the identifier number of the loop in which the variable
1863 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1864 pointer to the statement that uses this variable, in order to
1865 determine the evolution function of the variable, use the following
1868 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1869 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1870 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1874 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1880 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1881 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1882 fprintf (dump_file
, " (scalar = ");
1883 print_generic_expr (dump_file
, var
, 0);
1884 fprintf (dump_file
, ")\n");
1887 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1888 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1891 fprintf (dump_file
, ")\n");
1896 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1897 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1900 FOLDED_CASTS is set to true if resolve_mixers used
1901 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1902 at the moment in order to keep things simple). */
1905 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
1906 tree version
, bool *folded_casts
)
1909 tree ev
= version
, tmp
;
1912 *folded_casts
= false;
1915 tmp
= analyze_scalar_evolution (use_loop
, ev
);
1916 ev
= resolve_mixers (use_loop
, tmp
);
1918 if (folded_casts
&& tmp
!= ev
)
1919 *folded_casts
= true;
1921 if (use_loop
== wrto_loop
)
1924 /* If the value of the use changes in the inner loop, we cannot express
1925 its value in the outer loop (we might try to return interval chrec,
1926 but we do not have a user for it anyway) */
1927 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
1929 return chrec_dont_know
;
1931 use_loop
= loop_outer (use_loop
);
1935 /* Returns from CACHE the value for VERSION instantiated below
1936 INSTANTIATED_BELOW block. */
1939 get_instantiated_value (htab_t cache
, basic_block instantiated_below
,
1942 struct scev_info_str
*info
, pattern
;
1944 pattern
.var
= version
;
1945 pattern
.instantiated_below
= instantiated_below
;
1946 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
1954 /* Sets in CACHE the value of VERSION instantiated below basic block
1955 INSTANTIATED_BELOW to VAL. */
1958 set_instantiated_value (htab_t cache
, basic_block instantiated_below
,
1959 tree version
, tree val
)
1961 struct scev_info_str
*info
, pattern
;
1964 pattern
.var
= version
;
1965 pattern
.instantiated_below
= instantiated_below
;
1966 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
1969 *slot
= new_scev_info_str (instantiated_below
, version
);
1970 info
= (struct scev_info_str
*) *slot
;
1974 /* Return the closed_loop_phi node for VAR. If there is none, return
1978 loop_closed_phi_def (tree var
)
1983 gimple_stmt_iterator psi
;
1985 if (var
== NULL_TREE
1986 || TREE_CODE (var
) != SSA_NAME
)
1989 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
1990 exit
= single_exit (loop
);
1994 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
1996 phi
= gsi_stmt (psi
);
1997 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
1998 return PHI_RESULT (phi
);
2004 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2005 and EVOLUTION_LOOP, that were left under a symbolic form.
2007 CHREC is the scalar evolution to instantiate.
2009 CACHE is the cache of already instantiated values.
2011 FOLD_CONVERSIONS should be set to true when the conversions that
2012 may wrap in signed/pointer type are folded, as long as the value of
2013 the chrec is preserved.
2015 SIZE_EXPR is used for computing the size of the expression to be
2016 instantiated, and to stop if it exceeds some limit. */
2019 instantiate_scev_1 (basic_block instantiate_below
,
2020 struct loop
*evolution_loop
, tree chrec
,
2021 bool fold_conversions
, htab_t cache
, int size_expr
)
2023 tree res
, op0
, op1
, op2
;
2025 struct loop
*def_loop
;
2026 tree type
= chrec_type (chrec
);
2028 /* Give up if the expression is larger than the MAX that we allow. */
2029 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2030 return chrec_dont_know
;
2032 if (automatically_generated_chrec_p (chrec
)
2033 || is_gimple_min_invariant (chrec
))
2036 switch (TREE_CODE (chrec
))
2039 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2041 /* A parameter (or loop invariant and we do not want to include
2042 evolutions in outer loops), nothing to do. */
2044 || loop_depth (def_bb
->loop_father
) == 0
2045 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2048 /* We cache the value of instantiated variable to avoid exponential
2049 time complexity due to reevaluations. We also store the convenient
2050 value in the cache in order to prevent infinite recursion -- we do
2051 not want to instantiate the SSA_NAME if it is in a mixer
2052 structure. This is used for avoiding the instantiation of
2053 recursively defined functions, such as:
2055 | a_2 -> {0, +, 1, +, a_2}_1 */
2057 res
= get_instantiated_value (cache
, instantiate_below
, chrec
);
2061 res
= chrec_dont_know
;
2062 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2064 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2066 /* If the analysis yields a parametric chrec, instantiate the
2068 res
= analyze_scalar_evolution (def_loop
, chrec
);
2070 /* Don't instantiate loop-closed-ssa phi nodes. */
2071 if (TREE_CODE (res
) == SSA_NAME
2072 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2073 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2074 > loop_depth (def_loop
))))
2077 res
= loop_closed_phi_def (chrec
);
2081 if (res
== NULL_TREE
)
2082 res
= chrec_dont_know
;
2085 else if (res
!= chrec_dont_know
)
2086 res
= instantiate_scev_1 (instantiate_below
, evolution_loop
, res
,
2087 fold_conversions
, cache
, size_expr
);
2089 /* Store the correct value to the cache. */
2090 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2093 case POLYNOMIAL_CHREC
:
2094 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2095 CHREC_LEFT (chrec
), fold_conversions
, cache
,
2097 if (op0
== chrec_dont_know
)
2098 return chrec_dont_know
;
2100 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2101 CHREC_RIGHT (chrec
), fold_conversions
, cache
,
2103 if (op1
== chrec_dont_know
)
2104 return chrec_dont_know
;
2106 if (CHREC_LEFT (chrec
) != op0
2107 || CHREC_RIGHT (chrec
) != op1
)
2109 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2110 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2114 case POINTER_PLUS_EXPR
:
2116 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2117 TREE_OPERAND (chrec
, 0), fold_conversions
, cache
,
2119 if (op0
== chrec_dont_know
)
2120 return chrec_dont_know
;
2122 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2123 TREE_OPERAND (chrec
, 1), fold_conversions
, cache
,
2125 if (op1
== chrec_dont_know
)
2126 return chrec_dont_know
;
2128 if (TREE_OPERAND (chrec
, 0) != op0
2129 || TREE_OPERAND (chrec
, 1) != op1
)
2131 op0
= chrec_convert (type
, op0
, NULL
);
2132 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2133 chrec
= chrec_fold_plus (type
, op0
, op1
);
2138 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2139 TREE_OPERAND (chrec
, 0), fold_conversions
, cache
,
2141 if (op0
== chrec_dont_know
)
2142 return chrec_dont_know
;
2144 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2145 TREE_OPERAND (chrec
, 1),
2146 fold_conversions
, cache
, size_expr
);
2147 if (op1
== chrec_dont_know
)
2148 return chrec_dont_know
;
2150 if (TREE_OPERAND (chrec
, 0) != op0
2151 || TREE_OPERAND (chrec
, 1) != op1
)
2153 op0
= chrec_convert (type
, op0
, NULL
);
2154 op1
= chrec_convert (type
, op1
, NULL
);
2155 chrec
= chrec_fold_minus (type
, op0
, op1
);
2160 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2161 TREE_OPERAND (chrec
, 0),
2162 fold_conversions
, cache
, size_expr
);
2163 if (op0
== chrec_dont_know
)
2164 return chrec_dont_know
;
2166 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2167 TREE_OPERAND (chrec
, 1),
2168 fold_conversions
, cache
, size_expr
);
2169 if (op1
== chrec_dont_know
)
2170 return chrec_dont_know
;
2172 if (TREE_OPERAND (chrec
, 0) != op0
2173 || TREE_OPERAND (chrec
, 1) != op1
)
2175 op0
= chrec_convert (type
, op0
, NULL
);
2176 op1
= chrec_convert (type
, op1
, NULL
);
2177 chrec
= chrec_fold_multiply (type
, op0
, op1
);
2182 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2183 TREE_OPERAND (chrec
, 0),
2184 fold_conversions
, cache
, size_expr
);
2185 if (op0
== chrec_dont_know
)
2186 return chrec_dont_know
;
2188 if (fold_conversions
)
2190 tree tmp
= chrec_convert_aggressive (TREE_TYPE (chrec
), op0
);
2195 if (op0
== TREE_OPERAND (chrec
, 0))
2198 /* If we used chrec_convert_aggressive, we can no longer assume that
2199 signed chrecs do not overflow, as chrec_convert does, so avoid
2200 calling it in that case. */
2201 if (fold_conversions
)
2202 return fold_convert (TREE_TYPE (chrec
), op0
);
2204 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL
);
2206 case SCEV_NOT_KNOWN
:
2207 return chrec_dont_know
;
2216 if (VL_EXP_CLASS_P (chrec
))
2217 return chrec_dont_know
;
2219 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2222 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2223 TREE_OPERAND (chrec
, 0),
2224 fold_conversions
, cache
, size_expr
);
2225 if (op0
== chrec_dont_know
)
2226 return chrec_dont_know
;
2228 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2229 TREE_OPERAND (chrec
, 1),
2230 fold_conversions
, cache
, size_expr
);
2231 if (op1
== chrec_dont_know
)
2232 return chrec_dont_know
;
2234 op2
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2235 TREE_OPERAND (chrec
, 2),
2236 fold_conversions
, cache
, size_expr
);
2237 if (op2
== chrec_dont_know
)
2238 return chrec_dont_know
;
2240 if (op0
== TREE_OPERAND (chrec
, 0)
2241 && op1
== TREE_OPERAND (chrec
, 1)
2242 && op2
== TREE_OPERAND (chrec
, 2))
2245 return fold_build3 (TREE_CODE (chrec
),
2246 TREE_TYPE (chrec
), op0
, op1
, op2
);
2249 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2250 TREE_OPERAND (chrec
, 0),
2251 fold_conversions
, cache
, size_expr
);
2252 if (op0
== chrec_dont_know
)
2253 return chrec_dont_know
;
2255 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2256 TREE_OPERAND (chrec
, 1),
2257 fold_conversions
, cache
, size_expr
);
2258 if (op1
== chrec_dont_know
)
2259 return chrec_dont_know
;
2261 if (op0
== TREE_OPERAND (chrec
, 0)
2262 && op1
== TREE_OPERAND (chrec
, 1))
2264 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2267 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2268 TREE_OPERAND (chrec
, 0),
2269 fold_conversions
, cache
, size_expr
);
2270 if (op0
== chrec_dont_know
)
2271 return chrec_dont_know
;
2272 if (op0
== TREE_OPERAND (chrec
, 0))
2274 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2283 /* Too complicated to handle. */
2284 return chrec_dont_know
;
2287 /* Analyze all the parameters of the chrec that were left under a
2288 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2289 recursive instantiation of parameters: a parameter is a variable
2290 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2291 a function parameter. */
2294 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2298 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2302 fprintf (dump_file
, "(instantiate_scev \n");
2303 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2304 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2305 fprintf (dump_file
, " (chrec = ");
2306 print_generic_expr (dump_file
, chrec
, 0);
2307 fprintf (dump_file
, ")\n");
2310 res
= instantiate_scev_1 (instantiate_below
, evolution_loop
, chrec
, false,
2313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2315 fprintf (dump_file
, " (res = ");
2316 print_generic_expr (dump_file
, res
, 0);
2317 fprintf (dump_file
, "))\n");
2320 htab_delete (cache
);
2325 /* Similar to instantiate_parameters, but does not introduce the
2326 evolutions in outer loops for LOOP invariants in CHREC, and does not
2327 care about causing overflows, as long as they do not affect value
2328 of an expression. */
2331 resolve_mixers (struct loop
*loop
, tree chrec
)
2333 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2334 tree ret
= instantiate_scev_1 (block_before_loop (loop
), loop
, chrec
, true,
2336 htab_delete (cache
);
2340 /* Entry point for the analysis of the number of iterations pass.
2341 This function tries to safely approximate the number of iterations
2342 the loop will run. When this property is not decidable at compile
2343 time, the result is chrec_dont_know. Otherwise the result is
2344 a scalar or a symbolic parameter.
2346 Example of analysis: suppose that the loop has an exit condition:
2348 "if (b > 49) goto end_loop;"
2350 and that in a previous analysis we have determined that the
2351 variable 'b' has an evolution function:
2353 "EF = {23, +, 5}_2".
2355 When we evaluate the function at the point 5, i.e. the value of the
2356 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2357 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2358 the loop body has been executed 6 times. */
2361 number_of_latch_executions (struct loop
*loop
)
2365 struct tree_niter_desc niter_desc
;
2367 /* Determine whether the number_of_iterations_in_loop has already
2369 res
= loop
->nb_iterations
;
2372 res
= chrec_dont_know
;
2374 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2375 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2377 exit
= single_exit (loop
);
2381 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2384 type
= TREE_TYPE (niter_desc
.niter
);
2385 if (integer_nonzerop (niter_desc
.may_be_zero
))
2386 res
= build_int_cst (type
, 0);
2387 else if (integer_zerop (niter_desc
.may_be_zero
))
2388 res
= niter_desc
.niter
;
2390 res
= chrec_dont_know
;
2393 return set_nb_iterations_in_loop (loop
, res
);
2396 /* Returns the number of executions of the exit condition of LOOP,
2397 i.e., the number by one higher than number_of_latch_executions.
2398 Note that unlike number_of_latch_executions, this number does
2399 not necessarily fit in the unsigned variant of the type of
2400 the control variable -- if the number of iterations is a constant,
2401 we return chrec_dont_know if adding one to number_of_latch_executions
2402 overflows; however, in case the number of iterations is symbolic
2403 expression, the caller is responsible for dealing with this
2404 the possible overflow. */
2407 number_of_exit_cond_executions (struct loop
*loop
)
2409 tree ret
= number_of_latch_executions (loop
);
2410 tree type
= chrec_type (ret
);
2412 if (chrec_contains_undetermined (ret
))
2415 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2416 if (TREE_CODE (ret
) == INTEGER_CST
2417 && TREE_OVERFLOW (ret
))
2418 return chrec_dont_know
;
2423 /* One of the drivers for testing the scalar evolutions analysis.
2424 This function computes the number of iterations for all the loops
2425 from the EXIT_CONDITIONS array. */
2428 number_of_iterations_for_all_loops (VEC(gimple
,heap
) **exit_conditions
)
2431 unsigned nb_chrec_dont_know_loops
= 0;
2432 unsigned nb_static_loops
= 0;
2435 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2437 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2438 if (chrec_contains_undetermined (res
))
2439 nb_chrec_dont_know_loops
++;
2446 fprintf (dump_file
, "\n(\n");
2447 fprintf (dump_file
, "-----------------------------------------\n");
2448 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2449 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2450 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2451 fprintf (dump_file
, "-----------------------------------------\n");
2452 fprintf (dump_file
, ")\n\n");
2454 print_loops (dump_file
, 3);
2460 /* Counters for the stats. */
2466 unsigned nb_affine_multivar
;
2467 unsigned nb_higher_poly
;
2468 unsigned nb_chrec_dont_know
;
2469 unsigned nb_undetermined
;
2472 /* Reset the counters. */
2475 reset_chrecs_counters (struct chrec_stats
*stats
)
2477 stats
->nb_chrecs
= 0;
2478 stats
->nb_affine
= 0;
2479 stats
->nb_affine_multivar
= 0;
2480 stats
->nb_higher_poly
= 0;
2481 stats
->nb_chrec_dont_know
= 0;
2482 stats
->nb_undetermined
= 0;
2485 /* Dump the contents of a CHREC_STATS structure. */
2488 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2490 fprintf (file
, "\n(\n");
2491 fprintf (file
, "-----------------------------------------\n");
2492 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2493 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2494 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2495 stats
->nb_higher_poly
);
2496 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2497 fprintf (file
, "-----------------------------------------\n");
2498 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2499 fprintf (file
, "%d\twith undetermined coefficients\n",
2500 stats
->nb_undetermined
);
2501 fprintf (file
, "-----------------------------------------\n");
2502 fprintf (file
, "%d\tchrecs in the scev database\n",
2503 (int) htab_elements (scalar_evolution_info
));
2504 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2505 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2506 fprintf (file
, "-----------------------------------------\n");
2507 fprintf (file
, ")\n\n");
2510 /* Gather statistics about CHREC. */
2513 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2515 if (dump_file
&& (dump_flags
& TDF_STATS
))
2517 fprintf (dump_file
, "(classify_chrec ");
2518 print_generic_expr (dump_file
, chrec
, 0);
2519 fprintf (dump_file
, "\n");
2524 if (chrec
== NULL_TREE
)
2526 stats
->nb_undetermined
++;
2530 switch (TREE_CODE (chrec
))
2532 case POLYNOMIAL_CHREC
:
2533 if (evolution_function_is_affine_p (chrec
))
2535 if (dump_file
&& (dump_flags
& TDF_STATS
))
2536 fprintf (dump_file
, " affine_univariate\n");
2539 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2541 if (dump_file
&& (dump_flags
& TDF_STATS
))
2542 fprintf (dump_file
, " affine_multivariate\n");
2543 stats
->nb_affine_multivar
++;
2547 if (dump_file
&& (dump_flags
& TDF_STATS
))
2548 fprintf (dump_file
, " higher_degree_polynomial\n");
2549 stats
->nb_higher_poly
++;
2558 if (chrec_contains_undetermined (chrec
))
2560 if (dump_file
&& (dump_flags
& TDF_STATS
))
2561 fprintf (dump_file
, " undetermined\n");
2562 stats
->nb_undetermined
++;
2565 if (dump_file
&& (dump_flags
& TDF_STATS
))
2566 fprintf (dump_file
, ")\n");
2569 /* One of the drivers for testing the scalar evolutions analysis.
2570 This function analyzes the scalar evolution of all the scalars
2571 defined as loop phi nodes in one of the loops from the
2572 EXIT_CONDITIONS array.
2574 TODO Optimization: A loop is in canonical form if it contains only
2575 a single scalar loop phi node. All the other scalars that have an
2576 evolution in the loop are rewritten in function of this single
2577 index. This allows the parallelization of the loop. */
2580 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple
,heap
) **exit_conditions
)
2583 struct chrec_stats stats
;
2585 gimple_stmt_iterator psi
;
2587 reset_chrecs_counters (&stats
);
2589 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2595 loop
= loop_containing_stmt (cond
);
2598 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2600 phi
= gsi_stmt (psi
);
2601 if (is_gimple_reg (PHI_RESULT (phi
)))
2603 chrec
= instantiate_parameters
2605 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2607 if (dump_file
&& (dump_flags
& TDF_STATS
))
2608 gather_chrec_stats (chrec
, &stats
);
2613 if (dump_file
&& (dump_flags
& TDF_STATS
))
2614 dump_chrecs_stats (dump_file
, &stats
);
2617 /* Callback for htab_traverse, gathers information on chrecs in the
2621 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2623 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2625 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2630 /* Classify the chrecs of the whole database. */
2633 gather_stats_on_scev_database (void)
2635 struct chrec_stats stats
;
2640 reset_chrecs_counters (&stats
);
2642 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2645 dump_chrecs_stats (dump_file
, &stats
);
2653 initialize_scalar_evolutions_analyzer (void)
2655 /* The elements below are unique. */
2656 if (chrec_dont_know
== NULL_TREE
)
2658 chrec_not_analyzed_yet
= NULL_TREE
;
2659 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2660 chrec_known
= make_node (SCEV_KNOWN
);
2661 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2662 TREE_TYPE (chrec_known
) = void_type_node
;
2666 /* Initialize the analysis of scalar evolutions for LOOPS. */
2669 scev_initialize (void)
2674 scalar_evolution_info
= htab_create_alloc (100,
2681 initialize_scalar_evolutions_analyzer ();
2683 FOR_EACH_LOOP (li
, loop
, 0)
2685 loop
->nb_iterations
= NULL_TREE
;
2689 /* Cleans up the information cached by the scalar evolutions analysis. */
2697 if (!scalar_evolution_info
|| !current_loops
)
2700 htab_empty (scalar_evolution_info
);
2701 FOR_EACH_LOOP (li
, loop
, 0)
2703 loop
->nb_iterations
= NULL_TREE
;
2707 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2708 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2709 want step to be invariant in LOOP. Otherwise we require it to be an
2710 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2711 overflow (e.g. because it is computed in signed arithmetics). */
2714 simple_iv (struct loop
*loop
, gimple stmt
, tree op
, affine_iv
*iv
,
2715 bool allow_nonconstant_step
)
2717 basic_block bb
= gimple_bb (stmt
);
2721 iv
->base
= NULL_TREE
;
2722 iv
->step
= NULL_TREE
;
2723 iv
->no_overflow
= false;
2725 type
= TREE_TYPE (op
);
2726 if (TREE_CODE (type
) != INTEGER_TYPE
2727 && TREE_CODE (type
) != POINTER_TYPE
)
2730 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
,
2732 if (chrec_contains_undetermined (ev
))
2735 if (tree_does_not_contain_chrecs (ev
)
2736 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2739 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
2740 iv
->no_overflow
= true;
2744 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2745 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2748 iv
->step
= CHREC_RIGHT (ev
);
2749 if (allow_nonconstant_step
)
2751 if (tree_contains_chrecs (iv
->step
, NULL
)
2752 || chrec_contains_symbols_defined_in_loop (iv
->step
, loop
->num
))
2755 else if (TREE_CODE (iv
->step
) != INTEGER_CST
)
2758 iv
->base
= CHREC_LEFT (ev
);
2759 if (tree_contains_chrecs (iv
->base
, NULL
)
2760 || chrec_contains_symbols_defined_in_loop (iv
->base
, loop
->num
))
2763 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
2768 /* Runs the analysis of scalar evolutions. */
2771 scev_analysis (void)
2773 VEC(gimple
,heap
) *exit_conditions
;
2775 exit_conditions
= VEC_alloc (gimple
, heap
, 37);
2776 select_loops_exit_conditions (&exit_conditions
);
2778 if (dump_file
&& (dump_flags
& TDF_STATS
))
2779 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2781 number_of_iterations_for_all_loops (&exit_conditions
);
2782 VEC_free (gimple
, heap
, exit_conditions
);
2785 /* Finalize the scalar evolution analysis. */
2788 scev_finalize (void)
2790 if (!scalar_evolution_info
)
2792 htab_delete (scalar_evolution_info
);
2793 scalar_evolution_info
= NULL
;
2796 /* Replace ssa names for that scev can prove they are constant by the
2797 appropriate constants. Also perform final value replacement in loops,
2798 in case the replacement expressions are cheap.
2800 We only consider SSA names defined by phi nodes; rest is left to the
2801 ordinary constant propagation pass. */
2804 scev_const_prop (void)
2807 tree name
, type
, ev
;
2809 struct loop
*loop
, *ex_loop
;
2810 bitmap ssa_names_to_remove
= NULL
;
2813 gimple_stmt_iterator psi
;
2815 if (number_of_loops () <= 1)
2820 loop
= bb
->loop_father
;
2822 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2824 phi
= gsi_stmt (psi
);
2825 name
= PHI_RESULT (phi
);
2827 if (!is_gimple_reg (name
))
2830 type
= TREE_TYPE (name
);
2832 if (!POINTER_TYPE_P (type
)
2833 && !INTEGRAL_TYPE_P (type
))
2836 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
2837 if (!is_gimple_min_invariant (ev
)
2838 || !may_propagate_copy (name
, ev
))
2841 /* Replace the uses of the name. */
2843 replace_uses_by (name
, ev
);
2845 if (!ssa_names_to_remove
)
2846 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
2847 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
2851 /* Remove the ssa names that were replaced by constants. We do not
2852 remove them directly in the previous cycle, since this
2853 invalidates scev cache. */
2854 if (ssa_names_to_remove
)
2858 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
2860 gimple_stmt_iterator psi
;
2861 name
= ssa_name (i
);
2862 phi
= SSA_NAME_DEF_STMT (name
);
2864 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
2865 psi
= gsi_for_stmt (phi
);
2866 remove_phi_node (&psi
, true);
2869 BITMAP_FREE (ssa_names_to_remove
);
2873 /* Now the regular final value replacement. */
2874 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
2877 tree def
, rslt
, niter
;
2878 gimple_stmt_iterator bsi
;
2880 /* If we do not know exact number of iterations of the loop, we cannot
2881 replace the final value. */
2882 exit
= single_exit (loop
);
2886 niter
= number_of_latch_executions (loop
);
2887 /* We used to check here whether the computation of NITER is expensive,
2888 and avoided final value elimination if that is the case. The problem
2889 is that it is hard to evaluate whether the expression is too
2890 expensive, as we do not know what optimization opportunities the
2891 elimination of the final value may reveal. Therefore, we now
2892 eliminate the final values of induction variables unconditionally. */
2893 if (niter
== chrec_dont_know
)
2896 /* Ensure that it is possible to insert new statements somewhere. */
2897 if (!single_pred_p (exit
->dest
))
2898 split_loop_exit_edge (exit
);
2899 bsi
= gsi_after_labels (exit
->dest
);
2901 ex_loop
= superloop_at_depth (loop
,
2902 loop_depth (exit
->dest
->loop_father
) + 1);
2904 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
2906 phi
= gsi_stmt (psi
);
2907 rslt
= PHI_RESULT (phi
);
2908 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2909 if (!is_gimple_reg (def
))
2915 if (!POINTER_TYPE_P (TREE_TYPE (def
))
2916 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
2922 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
2923 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
2924 if (!tree_does_not_contain_chrecs (def
)
2925 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
2926 /* Moving the computation from the loop may prolong life range
2927 of some ssa names, which may cause problems if they appear
2928 on abnormal edges. */
2929 || contains_abnormal_ssa_name_p (def
))
2935 /* Eliminate the PHI node and replace it by a computation outside
2937 def
= unshare_expr (def
);
2938 remove_phi_node (&psi
, false);
2940 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
2941 true, GSI_SAME_STMT
);
2942 ass
= gimple_build_assign (rslt
, def
);
2943 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
2949 #include "gt-tree-scalar-evolution.h"