1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
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"
263 #include "basic-block.h"
264 #include "tree-pretty-print.h"
265 #include "gimple-pretty-print.h"
266 #include "tree-flow.h"
267 #include "tree-dump.h"
270 #include "tree-chrec.h"
271 #include "tree-scalar-evolution.h"
272 #include "tree-pass.h"
276 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
278 /* The cached information about an SSA name VAR, claiming that below
279 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
282 struct GTY(()) scev_info_str
{
283 basic_block instantiated_below
;
288 /* Counters for the scev database. */
289 static unsigned nb_set_scev
= 0;
290 static unsigned nb_get_scev
= 0;
292 /* The following trees are unique elements. Thus the comparison of
293 another element to these elements should be done on the pointer to
294 these trees, and not on their value. */
296 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
297 tree chrec_not_analyzed_yet
;
299 /* Reserved to the cases where the analyzer has detected an
300 undecidable property at compile time. */
301 tree chrec_dont_know
;
303 /* When the analyzer has detected that a property will never
304 happen, then it qualifies it with chrec_known. */
307 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
310 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
312 static inline struct scev_info_str
*
313 new_scev_info_str (basic_block instantiated_below
, tree var
)
315 struct scev_info_str
*res
;
317 res
= ggc_alloc_scev_info_str ();
319 res
->chrec
= chrec_not_analyzed_yet
;
320 res
->instantiated_below
= instantiated_below
;
325 /* Computes a hash function for database element ELT. */
328 hash_scev_info (const void *elt
)
330 return SSA_NAME_VERSION (((const struct scev_info_str
*) elt
)->var
);
333 /* Compares database elements E1 and E2. */
336 eq_scev_info (const void *e1
, const void *e2
)
338 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
339 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
341 return (elt1
->var
== elt2
->var
342 && elt1
->instantiated_below
== elt2
->instantiated_below
);
345 /* Deletes database element E. */
348 del_scev_info (void *e
)
353 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
354 A first query on VAR returns chrec_not_analyzed_yet. */
357 find_var_scev_info (basic_block instantiated_below
, tree var
)
359 struct scev_info_str
*res
;
360 struct scev_info_str tmp
;
364 tmp
.instantiated_below
= instantiated_below
;
365 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
368 *slot
= new_scev_info_str (instantiated_below
, var
);
369 res
= (struct scev_info_str
*) *slot
;
374 /* Return true when CHREC contains symbolic names defined in
378 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
382 if (chrec
== NULL_TREE
)
385 if (is_gimple_min_invariant (chrec
))
388 if (TREE_CODE (chrec
) == VAR_DECL
389 || TREE_CODE (chrec
) == PARM_DECL
390 || TREE_CODE (chrec
) == FUNCTION_DECL
391 || TREE_CODE (chrec
) == LABEL_DECL
392 || TREE_CODE (chrec
) == RESULT_DECL
393 || TREE_CODE (chrec
) == FIELD_DECL
)
396 if (TREE_CODE (chrec
) == SSA_NAME
)
398 gimple def
= SSA_NAME_DEF_STMT (chrec
);
399 struct loop
*def_loop
= loop_containing_stmt (def
);
400 struct loop
*loop
= get_loop (loop_nb
);
402 if (def_loop
== NULL
)
405 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
411 n
= TREE_OPERAND_LENGTH (chrec
);
412 for (i
= 0; i
< n
; i
++)
413 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
419 /* Return true when PHI is a loop-phi-node. */
422 loop_phi_node_p (gimple phi
)
424 /* The implementation of this function is based on the following
425 property: "all the loop-phi-nodes of a loop are contained in the
426 loop's header basic block". */
428 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
431 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
432 In general, in the case of multivariate evolutions we want to get
433 the evolution in different loops. LOOP specifies the level for
434 which to get the evolution.
438 | for (j = 0; j < 100; j++)
440 | for (k = 0; k < 100; k++)
442 | i = k + j; - Here the value of i is a function of j, k.
444 | ... = i - Here the value of i is a function of j.
446 | ... = i - Here the value of i is a scalar.
452 | i_1 = phi (i_0, i_2)
456 This loop has the same effect as:
457 LOOP_1 has the same effect as:
461 The overall effect of the loop, "i_0 + 20" in the previous example,
462 is obtained by passing in the parameters: LOOP = 1,
463 EVOLUTION_FN = {i_0, +, 2}_1.
467 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
471 if (evolution_fn
== chrec_dont_know
)
472 return chrec_dont_know
;
474 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
476 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
478 if (inner_loop
== loop
479 || flow_loop_nested_p (loop
, inner_loop
))
481 tree nb_iter
= number_of_latch_executions (inner_loop
);
483 if (nb_iter
== chrec_dont_know
)
484 return chrec_dont_know
;
489 /* evolution_fn is the evolution function in LOOP. Get
490 its value in the nb_iter-th iteration. */
491 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
493 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
494 res
= instantiate_parameters (loop
, res
);
496 /* Continue the computation until ending on a parent of LOOP. */
497 return compute_overall_effect_of_inner_loop (loop
, res
);
504 /* If the evolution function is an invariant, there is nothing to do. */
505 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
509 return chrec_dont_know
;
512 /* Determine whether the CHREC is always positive/negative. If the expression
513 cannot be statically analyzed, return false, otherwise set the answer into
517 chrec_is_positive (tree chrec
, bool *value
)
519 bool value0
, value1
, value2
;
520 tree end_value
, nb_iter
;
522 switch (TREE_CODE (chrec
))
524 case POLYNOMIAL_CHREC
:
525 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
526 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
529 /* FIXME -- overflows. */
530 if (value0
== value1
)
536 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
537 and the proof consists in showing that the sign never
538 changes during the execution of the loop, from 0 to
539 loop->nb_iterations. */
540 if (!evolution_function_is_affine_p (chrec
))
543 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
544 if (chrec_contains_undetermined (nb_iter
))
548 /* TODO -- If the test is after the exit, we may decrease the number of
549 iterations by one. */
551 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
554 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
556 if (!chrec_is_positive (end_value
, &value2
))
560 return value0
== value1
;
563 *value
= (tree_int_cst_sgn (chrec
) == 1);
571 /* Associate CHREC to SCALAR. */
574 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
578 if (TREE_CODE (scalar
) != SSA_NAME
)
581 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
585 if (dump_flags
& TDF_DETAILS
)
587 fprintf (dump_file
, "(set_scalar_evolution \n");
588 fprintf (dump_file
, " instantiated_below = %d \n",
589 instantiated_below
->index
);
590 fprintf (dump_file
, " (scalar = ");
591 print_generic_expr (dump_file
, scalar
, 0);
592 fprintf (dump_file
, ")\n (scalar_evolution = ");
593 print_generic_expr (dump_file
, chrec
, 0);
594 fprintf (dump_file
, "))\n");
596 if (dump_flags
& TDF_STATS
)
600 *scalar_info
= chrec
;
603 /* Retrieve the chrec associated to SCALAR instantiated below
604 INSTANTIATED_BELOW block. */
607 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
613 if (dump_flags
& TDF_DETAILS
)
615 fprintf (dump_file
, "(get_scalar_evolution \n");
616 fprintf (dump_file
, " (scalar = ");
617 print_generic_expr (dump_file
, scalar
, 0);
618 fprintf (dump_file
, ")\n");
620 if (dump_flags
& TDF_STATS
)
624 switch (TREE_CODE (scalar
))
627 res
= *find_var_scev_info (instantiated_below
, scalar
);
637 res
= chrec_not_analyzed_yet
;
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 fprintf (dump_file
, " (scalar_evolution = ");
644 print_generic_expr (dump_file
, res
, 0);
645 fprintf (dump_file
, "))\n");
651 /* Helper function for add_to_evolution. Returns the evolution
652 function for an assignment of the form "a = b + c", where "a" and
653 "b" are on the strongly connected component. CHREC_BEFORE is the
654 information that we already have collected up to this point.
655 TO_ADD is the evolution of "c".
657 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
658 evolution the expression TO_ADD, otherwise construct an evolution
659 part for this loop. */
662 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
665 tree type
, left
, right
;
666 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
668 switch (TREE_CODE (chrec_before
))
670 case POLYNOMIAL_CHREC
:
671 chloop
= get_chrec_loop (chrec_before
);
673 || flow_loop_nested_p (chloop
, loop
))
677 type
= chrec_type (chrec_before
);
679 /* When there is no evolution part in this loop, build it. */
684 right
= SCALAR_FLOAT_TYPE_P (type
)
685 ? build_real (type
, dconst0
)
686 : build_int_cst (type
, 0);
690 var
= CHREC_VARIABLE (chrec_before
);
691 left
= CHREC_LEFT (chrec_before
);
692 right
= CHREC_RIGHT (chrec_before
);
695 to_add
= chrec_convert (type
, to_add
, at_stmt
);
696 right
= chrec_convert_rhs (type
, right
, at_stmt
);
697 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
698 return build_polynomial_chrec (var
, left
, right
);
702 gcc_assert (flow_loop_nested_p (loop
, chloop
));
704 /* Search the evolution in LOOP_NB. */
705 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
707 right
= CHREC_RIGHT (chrec_before
);
708 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
709 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
714 /* These nodes do not depend on a loop. */
715 if (chrec_before
== chrec_dont_know
)
716 return chrec_dont_know
;
719 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
720 return build_polynomial_chrec (loop_nb
, left
, right
);
724 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
727 Description (provided for completeness, for those who read code in
728 a plane, and for my poor 62 bytes brain that would have forgotten
729 all this in the next two or three months):
731 The algorithm of translation of programs from the SSA representation
732 into the chrecs syntax is based on a pattern matching. After having
733 reconstructed the overall tree expression for a loop, there are only
734 two cases that can arise:
736 1. a = loop-phi (init, a + expr)
737 2. a = loop-phi (init, expr)
739 where EXPR is either a scalar constant with respect to the analyzed
740 loop (this is a degree 0 polynomial), or an expression containing
741 other loop-phi definitions (these are higher degree polynomials).
748 | a = phi (init, a + 5)
755 | a = phi (inita, 2 * b + 3)
756 | b = phi (initb, b + 1)
759 For the first case, the semantics of the SSA representation is:
761 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
763 that is, there is a loop index "x" that determines the scalar value
764 of the variable during the loop execution. During the first
765 iteration, the value is that of the initial condition INIT, while
766 during the subsequent iterations, it is the sum of the initial
767 condition with the sum of all the values of EXPR from the initial
768 iteration to the before last considered iteration.
770 For the second case, the semantics of the SSA program is:
772 | a (x) = init, if x = 0;
773 | expr (x - 1), otherwise.
775 The second case corresponds to the PEELED_CHREC, whose syntax is
776 close to the syntax of a loop-phi-node:
778 | phi (init, expr) vs. (init, expr)_x
780 The proof of the translation algorithm for the first case is a
781 proof by structural induction based on the degree of EXPR.
784 When EXPR is a constant with respect to the analyzed loop, or in
785 other words when EXPR is a polynomial of degree 0, the evolution of
786 the variable A in the loop is an affine function with an initial
787 condition INIT, and a step EXPR. In order to show this, we start
788 from the semantics of the SSA representation:
790 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
792 and since "expr (j)" is a constant with respect to "j",
794 f (x) = init + x * expr
796 Finally, based on the semantics of the pure sum chrecs, by
797 identification we get the corresponding chrecs syntax:
799 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
800 f (x) -> {init, +, expr}_x
803 Suppose that EXPR is a polynomial of degree N with respect to the
804 analyzed loop_x for which we have already determined that it is
805 written under the chrecs syntax:
807 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
809 We start from the semantics of the SSA program:
811 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
813 | f (x) = init + \sum_{j = 0}^{x - 1}
814 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
816 | f (x) = init + \sum_{j = 0}^{x - 1}
817 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
819 | f (x) = init + \sum_{k = 0}^{n - 1}
820 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
822 | f (x) = init + \sum_{k = 0}^{n - 1}
823 | (b_k * \binom{x}{k + 1})
825 | f (x) = init + b_0 * \binom{x}{1} + ...
826 | + b_{n-1} * \binom{x}{n}
828 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
829 | + b_{n-1} * \binom{x}{n}
832 And finally from the definition of the chrecs syntax, we identify:
833 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
835 This shows the mechanism that stands behind the add_to_evolution
836 function. An important point is that the use of symbolic
837 parameters avoids the need of an analysis schedule.
844 | a = phi (inita, a + 2 + b)
845 | b = phi (initb, b + 1)
848 When analyzing "a", the algorithm keeps "b" symbolically:
850 | a -> {inita, +, 2 + b}_1
852 Then, after instantiation, the analyzer ends on the evolution:
854 | a -> {inita, +, 2 + initb, +, 1}_1
859 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
860 tree to_add
, gimple at_stmt
)
862 tree type
= chrec_type (to_add
);
863 tree res
= NULL_TREE
;
865 if (to_add
== NULL_TREE
)
868 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
869 instantiated at this point. */
870 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
871 /* This should not happen. */
872 return chrec_dont_know
;
874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "(add_to_evolution \n");
877 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
878 fprintf (dump_file
, " (chrec_before = ");
879 print_generic_expr (dump_file
, chrec_before
, 0);
880 fprintf (dump_file
, ")\n (to_add = ");
881 print_generic_expr (dump_file
, to_add
, 0);
882 fprintf (dump_file
, ")\n");
885 if (code
== MINUS_EXPR
)
886 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
887 ? build_real (type
, dconstm1
)
888 : build_int_cst_type (type
, -1));
890 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
894 fprintf (dump_file
, " (res = ");
895 print_generic_expr (dump_file
, res
, 0);
896 fprintf (dump_file
, "))\n");
904 /* This section selects the loops that will be good candidates for the
905 scalar evolution analysis. For the moment, greedily select all the
906 loop nests we could analyze. */
908 /* For a loop with a single exit edge, return the COND_EXPR that
909 guards the exit edge. If the expression is too difficult to
910 analyze, then give up. */
913 get_loop_exit_condition (const struct loop
*loop
)
916 edge exit_edge
= single_exit (loop
);
918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
919 fprintf (dump_file
, "(get_loop_exit_condition \n ");
925 stmt
= last_stmt (exit_edge
->src
);
926 if (gimple_code (stmt
) == GIMPLE_COND
)
930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
932 print_gimple_stmt (dump_file
, res
, 0, 0);
933 fprintf (dump_file
, ")\n");
939 /* Recursively determine and enqueue the exit conditions for a loop. */
942 get_exit_conditions_rec (struct loop
*loop
,
943 VEC(gimple
,heap
) **exit_conditions
)
948 /* Recurse on the inner loops, then on the next (sibling) loops. */
949 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
950 get_exit_conditions_rec (loop
->next
, exit_conditions
);
952 if (single_exit (loop
))
954 gimple loop_condition
= get_loop_exit_condition (loop
);
957 VEC_safe_push (gimple
, heap
, *exit_conditions
, loop_condition
);
961 /* Select the candidate loop nests for the analysis. This function
962 initializes the EXIT_CONDITIONS array. */
965 select_loops_exit_conditions (VEC(gimple
,heap
) **exit_conditions
)
967 struct loop
*function_body
= current_loops
->tree_root
;
969 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
973 /* Depth first search algorithm. */
975 typedef enum t_bool
{
982 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
984 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
985 Return true if the strongly connected component has been found. */
988 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
989 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
990 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
992 t_bool res
= t_false
;
997 case POINTER_PLUS_EXPR
:
999 if (TREE_CODE (rhs0
) == SSA_NAME
)
1001 if (TREE_CODE (rhs1
) == SSA_NAME
)
1003 /* Match an assignment under the form:
1006 /* We want only assignments of form "name + name" contribute to
1007 LIMIT, as the other cases do not necessarily contribute to
1008 the complexity of the expression. */
1011 evol
= *evolution_of_loop
;
1012 res
= follow_ssa_edge
1013 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
1016 *evolution_of_loop
= add_to_evolution
1018 chrec_convert (type
, evol
, at_stmt
),
1019 code
, rhs1
, at_stmt
);
1021 else if (res
== t_false
)
1023 res
= follow_ssa_edge
1024 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1025 evolution_of_loop
, limit
);
1028 *evolution_of_loop
= add_to_evolution
1030 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1031 code
, rhs0
, at_stmt
);
1033 else if (res
== t_dont_know
)
1034 *evolution_of_loop
= chrec_dont_know
;
1037 else if (res
== t_dont_know
)
1038 *evolution_of_loop
= chrec_dont_know
;
1043 /* Match an assignment under the form:
1045 res
= follow_ssa_edge
1046 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1047 evolution_of_loop
, limit
);
1049 *evolution_of_loop
= add_to_evolution
1050 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1052 code
, rhs1
, at_stmt
);
1054 else if (res
== t_dont_know
)
1055 *evolution_of_loop
= chrec_dont_know
;
1059 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1061 /* Match an assignment under the form:
1063 res
= follow_ssa_edge
1064 (loop
, SSA_NAME_DEF_STMT (rhs1
), 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
, rhs0
, at_stmt
);
1072 else if (res
== t_dont_know
)
1073 *evolution_of_loop
= chrec_dont_know
;
1077 /* Otherwise, match an assignment under the form:
1079 /* And there is nothing to do. */
1084 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1085 if (TREE_CODE (rhs0
) == SSA_NAME
)
1087 /* Match an assignment under the form:
1090 /* We want only assignments of form "name - name" contribute to
1091 LIMIT, as the other cases do not necessarily contribute to
1092 the complexity of the expression. */
1093 if (TREE_CODE (rhs1
) == SSA_NAME
)
1096 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1097 evolution_of_loop
, limit
);
1099 *evolution_of_loop
= add_to_evolution
1100 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1101 MINUS_EXPR
, rhs1
, at_stmt
);
1103 else if (res
== t_dont_know
)
1104 *evolution_of_loop
= chrec_dont_know
;
1107 /* Otherwise, match an assignment under the form:
1109 /* And there is nothing to do. */
1120 /* Follow the ssa edge into the expression EXPR.
1121 Return true if the strongly connected component has been found. */
1124 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1125 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1127 enum tree_code code
= TREE_CODE (expr
);
1128 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1131 /* The EXPR is one of the following cases:
1135 - a POINTER_PLUS_EXPR,
1138 - other cases are not yet handled. */
1143 /* This assignment is under the form "a_1 = (cast) rhs. */
1144 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1145 halting_phi
, evolution_of_loop
, limit
);
1146 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1150 /* This assignment is under the form "a_1 = 7". */
1155 /* This assignment is under the form: "a_1 = b_2". */
1156 res
= follow_ssa_edge
1157 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1160 case POINTER_PLUS_EXPR
:
1163 /* This case is under the form "rhs0 +- rhs1". */
1164 rhs0
= TREE_OPERAND (expr
, 0);
1165 rhs1
= TREE_OPERAND (expr
, 1);
1166 type
= TREE_TYPE (rhs0
);
1167 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1168 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1169 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1170 halting_phi
, evolution_of_loop
, limit
);
1174 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1175 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1177 expr
= TREE_OPERAND (expr
, 0);
1178 rhs0
= TREE_OPERAND (expr
, 0);
1179 rhs1
= TREE_OPERAND (expr
, 1);
1180 type
= TREE_TYPE (rhs0
);
1181 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1182 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1183 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1184 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1185 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 rhs0
= ASSERT_EXPR_VAR (expr
);
1195 if (TREE_CODE (rhs0
) == SSA_NAME
)
1196 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1197 halting_phi
, evolution_of_loop
, limit
);
1210 /* Follow the ssa edge into the right hand side of an assignment STMT.
1211 Return true if the strongly connected component has been found. */
1214 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1215 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1217 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1218 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1224 /* This assignment is under the form "a_1 = (cast) rhs. */
1225 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1226 halting_phi
, evolution_of_loop
, limit
);
1227 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1230 case POINTER_PLUS_EXPR
:
1233 rhs1
= gimple_assign_rhs1 (stmt
);
1234 rhs2
= gimple_assign_rhs2 (stmt
);
1235 type
= TREE_TYPE (rhs1
);
1236 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1237 halting_phi
, evolution_of_loop
, limit
);
1241 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1242 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1243 halting_phi
, evolution_of_loop
, limit
);
1252 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1255 backedge_phi_arg_p (gimple phi
, int i
)
1257 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1259 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1260 about updating it anywhere, and this should work as well most of the
1262 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1268 /* Helper function for one branch of the condition-phi-node. Return
1269 true if the strongly connected component has been found following
1272 static inline t_bool
1273 follow_ssa_edge_in_condition_phi_branch (int i
,
1275 gimple condition_phi
,
1277 tree
*evolution_of_branch
,
1278 tree init_cond
, int limit
)
1280 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1281 *evolution_of_branch
= chrec_dont_know
;
1283 /* Do not follow back edges (they must belong to an irreducible loop, which
1284 we really do not want to worry about). */
1285 if (backedge_phi_arg_p (condition_phi
, i
))
1288 if (TREE_CODE (branch
) == SSA_NAME
)
1290 *evolution_of_branch
= init_cond
;
1291 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1292 evolution_of_branch
, limit
);
1295 /* This case occurs when one of the condition branches sets
1296 the variable to a constant: i.e. a phi-node like
1297 "a_2 = PHI <a_7(5), 2(6)>;".
1299 FIXME: This case have to be refined correctly:
1300 in some cases it is possible to say something better than
1301 chrec_dont_know, for example using a wrap-around notation. */
1305 /* This function merges the branches of a condition-phi-node in a
1309 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1310 gimple condition_phi
,
1312 tree
*evolution_of_loop
, int limit
)
1315 tree init
= *evolution_of_loop
;
1316 tree evolution_of_branch
;
1317 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1319 &evolution_of_branch
,
1321 if (res
== t_false
|| res
== t_dont_know
)
1324 *evolution_of_loop
= evolution_of_branch
;
1326 n
= gimple_phi_num_args (condition_phi
);
1327 for (i
= 1; i
< n
; i
++)
1329 /* Quickly give up when the evolution of one of the branches is
1331 if (*evolution_of_loop
== chrec_dont_know
)
1334 /* Increase the limit by the PHI argument number to avoid exponential
1335 time and memory complexity. */
1336 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1338 &evolution_of_branch
,
1340 if (res
== t_false
|| res
== t_dont_know
)
1343 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1344 evolution_of_branch
);
1350 /* Follow an SSA edge in an inner loop. It computes the overall
1351 effect of the loop, and following the symbolic initial conditions,
1352 it follows the edges in the parent loop. The inner loop is
1353 considered as a single statement. */
1356 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1357 gimple loop_phi_node
,
1359 tree
*evolution_of_loop
, int limit
)
1361 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1362 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1364 /* Sometimes, the inner loop is too difficult to analyze, and the
1365 result of the analysis is a symbolic parameter. */
1366 if (ev
== PHI_RESULT (loop_phi_node
))
1368 t_bool res
= t_false
;
1369 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1371 for (i
= 0; i
< n
; i
++)
1373 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1376 /* Follow the edges that exit the inner loop. */
1377 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1378 if (!flow_bb_inside_loop_p (loop
, bb
))
1379 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1381 evolution_of_loop
, limit
);
1386 /* If the path crosses this loop-phi, give up. */
1388 *evolution_of_loop
= chrec_dont_know
;
1393 /* Otherwise, compute the overall effect of the inner loop. */
1394 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1395 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1396 evolution_of_loop
, limit
);
1399 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1400 path that is analyzed on the return walk. */
1403 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1404 tree
*evolution_of_loop
, int limit
)
1406 struct loop
*def_loop
;
1408 if (gimple_nop_p (def
))
1411 /* Give up if the path is longer than the MAX that we allow. */
1412 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1415 def_loop
= loop_containing_stmt (def
);
1417 switch (gimple_code (def
))
1420 if (!loop_phi_node_p (def
))
1421 /* DEF is a condition-phi-node. Follow the branches, and
1422 record their evolutions. Finally, merge the collected
1423 information and set the approximation to the main
1425 return follow_ssa_edge_in_condition_phi
1426 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1428 /* When the analyzed phi is the halting_phi, the
1429 depth-first search is over: we have found a path from
1430 the halting_phi to itself in the loop. */
1431 if (def
== halting_phi
)
1434 /* Otherwise, the evolution of the HALTING_PHI depends
1435 on the evolution of another loop-phi-node, i.e. the
1436 evolution function is a higher degree polynomial. */
1437 if (def_loop
== loop
)
1441 if (flow_loop_nested_p (loop
, def_loop
))
1442 return follow_ssa_edge_inner_loop_phi
1443 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1449 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1450 evolution_of_loop
, limit
);
1453 /* At this level of abstraction, the program is just a set
1454 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1455 other node to be handled. */
1462 /* Given a LOOP_PHI_NODE, this function determines the evolution
1463 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1466 analyze_evolution_in_loop (gimple loop_phi_node
,
1469 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1470 tree evolution_function
= chrec_not_analyzed_yet
;
1471 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1476 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1477 fprintf (dump_file
, " (loop_phi_node = ");
1478 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1479 fprintf (dump_file
, ")\n");
1482 for (i
= 0; i
< n
; i
++)
1484 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1489 /* Select the edges that enter the loop body. */
1490 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1491 if (!flow_bb_inside_loop_p (loop
, bb
))
1494 if (TREE_CODE (arg
) == SSA_NAME
)
1498 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1500 /* Pass in the initial condition to the follow edge function. */
1502 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1504 /* If ev_fn has no evolution in the inner loop, and the
1505 init_cond is not equal to ev_fn, then we have an
1506 ambiguity between two possible values, as we cannot know
1507 the number of iterations at this point. */
1508 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1509 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1510 && !operand_equal_p (init_cond
, ev_fn
, 0))
1511 ev_fn
= chrec_dont_know
;
1516 /* When it is impossible to go back on the same
1517 loop_phi_node by following the ssa edges, the
1518 evolution is represented by a peeled chrec, i.e. the
1519 first iteration, EV_FN has the value INIT_COND, then
1520 all the other iterations it has the value of ARG.
1521 For the moment, PEELED_CHREC nodes are not built. */
1523 ev_fn
= chrec_dont_know
;
1525 /* When there are multiple back edges of the loop (which in fact never
1526 happens currently, but nevertheless), merge their evolutions. */
1527 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1530 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1532 fprintf (dump_file
, " (evolution_function = ");
1533 print_generic_expr (dump_file
, evolution_function
, 0);
1534 fprintf (dump_file
, "))\n");
1537 return evolution_function
;
1540 /* Given a loop-phi-node, return the initial conditions of the
1541 variable on entry of the loop. When the CCP has propagated
1542 constants into the loop-phi-node, the initial condition is
1543 instantiated, otherwise the initial condition is kept symbolic.
1544 This analyzer does not analyze the evolution outside the current
1545 loop, and leaves this task to the on-demand tree reconstructor. */
1548 analyze_initial_condition (gimple loop_phi_node
)
1551 tree init_cond
= chrec_not_analyzed_yet
;
1552 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1556 fprintf (dump_file
, "(analyze_initial_condition \n");
1557 fprintf (dump_file
, " (loop_phi_node = \n");
1558 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1559 fprintf (dump_file
, ")\n");
1562 n
= gimple_phi_num_args (loop_phi_node
);
1563 for (i
= 0; i
< n
; i
++)
1565 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1566 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1568 /* When the branch is oriented to the loop's body, it does
1569 not contribute to the initial condition. */
1570 if (flow_bb_inside_loop_p (loop
, bb
))
1573 if (init_cond
== chrec_not_analyzed_yet
)
1579 if (TREE_CODE (branch
) == SSA_NAME
)
1581 init_cond
= chrec_dont_know
;
1585 init_cond
= chrec_merge (init_cond
, branch
);
1588 /* Ooops -- a loop without an entry??? */
1589 if (init_cond
== chrec_not_analyzed_yet
)
1590 init_cond
= chrec_dont_know
;
1592 /* During early loop unrolling we do not have fully constant propagated IL.
1593 Handle degenerate PHIs here to not miss important unrollings. */
1594 if (TREE_CODE (init_cond
) == SSA_NAME
)
1596 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1598 if (gimple_code (def
) == GIMPLE_PHI
1599 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1600 /* Only allow invariants here, otherwise we may break
1601 loop-closed SSA form. */
1602 && is_gimple_min_invariant (res
))
1606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1608 fprintf (dump_file
, " (init_cond = ");
1609 print_generic_expr (dump_file
, init_cond
, 0);
1610 fprintf (dump_file
, "))\n");
1616 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1619 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1622 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1625 if (phi_loop
!= loop
)
1627 struct loop
*subloop
;
1628 tree evolution_fn
= analyze_scalar_evolution
1629 (phi_loop
, PHI_RESULT (loop_phi_node
));
1631 /* Dive one level deeper. */
1632 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1634 /* Interpret the subloop. */
1635 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1639 /* Otherwise really interpret the loop phi. */
1640 init_cond
= analyze_initial_condition (loop_phi_node
);
1641 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1643 /* Verify we maintained the correct initial condition throughout
1644 possible conversions in the SSA chain. */
1645 if (res
!= chrec_dont_know
)
1647 tree new_init
= res
;
1648 if (CONVERT_EXPR_P (res
)
1649 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1650 new_init
= fold_convert (TREE_TYPE (res
),
1651 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1652 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1653 new_init
= CHREC_LEFT (res
);
1654 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1655 gcc_assert (TREE_CODE (new_init
) != POLYNOMIAL_CHREC
);
1656 if (!operand_equal_p (init_cond
, new_init
, 0))
1657 return chrec_dont_know
;
1663 /* This function merges the branches of a condition-phi-node,
1664 contained in the outermost loop, and whose arguments are already
1668 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1670 int i
, n
= gimple_phi_num_args (condition_phi
);
1671 tree res
= chrec_not_analyzed_yet
;
1673 for (i
= 0; i
< n
; i
++)
1677 if (backedge_phi_arg_p (condition_phi
, i
))
1679 res
= chrec_dont_know
;
1683 branch_chrec
= analyze_scalar_evolution
1684 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1686 res
= chrec_merge (res
, branch_chrec
);
1692 /* Interpret the operation RHS1 OP RHS2. If we didn't
1693 analyze this node before, follow the definitions until ending
1694 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1695 return path, this function propagates evolutions (ala constant copy
1696 propagation). OPND1 is not a GIMPLE expression because we could
1697 analyze the effect of an inner loop: see interpret_loop_phi. */
1700 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1701 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1703 tree res
, chrec1
, chrec2
;
1705 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1707 if (is_gimple_min_invariant (rhs1
))
1708 return chrec_convert (type
, rhs1
, at_stmt
);
1710 if (code
== SSA_NAME
)
1711 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1714 if (code
== ASSERT_EXPR
)
1716 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1717 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1721 return chrec_dont_know
;
1726 case POINTER_PLUS_EXPR
:
1727 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1728 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1729 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1730 chrec2
= chrec_convert (sizetype
, chrec2
, at_stmt
);
1731 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1735 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1736 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1737 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1738 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1739 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1743 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1744 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1745 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1746 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1747 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1751 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1752 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1753 /* TYPE may be integer, real or complex, so use fold_convert. */
1754 res
= chrec_fold_multiply (type
, chrec1
,
1755 fold_convert (type
, integer_minus_one_node
));
1759 /* Handle ~X as -1 - X. */
1760 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1761 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1762 res
= chrec_fold_minus (type
,
1763 fold_convert (type
, integer_minus_one_node
),
1768 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1769 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1770 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1771 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1772 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1776 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1777 res
= chrec_convert (type
, chrec1
, at_stmt
);
1781 res
= chrec_dont_know
;
1788 /* Interpret the expression EXPR. */
1791 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1793 enum tree_code code
;
1794 tree type
= TREE_TYPE (expr
), op0
, op1
;
1796 if (automatically_generated_chrec_p (expr
))
1799 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
)
1800 return chrec_dont_know
;
1802 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1804 return interpret_rhs_expr (loop
, at_stmt
, type
,
1808 /* Interpret the rhs of the assignment STMT. */
1811 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1813 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1814 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1816 return interpret_rhs_expr (loop
, stmt
, type
,
1817 gimple_assign_rhs1 (stmt
), code
,
1818 gimple_assign_rhs2 (stmt
));
1823 /* This section contains all the entry points:
1824 - number_of_iterations_in_loop,
1825 - analyze_scalar_evolution,
1826 - instantiate_parameters.
1829 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1830 common ancestor of DEF_LOOP and USE_LOOP. */
1833 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1834 struct loop
*def_loop
,
1838 if (def_loop
== wrto_loop
)
1841 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1842 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1844 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1847 /* Helper recursive function. */
1850 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1852 tree type
= TREE_TYPE (var
);
1855 struct loop
*def_loop
;
1857 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1858 return chrec_dont_know
;
1860 if (TREE_CODE (var
) != SSA_NAME
)
1861 return interpret_expr (loop
, NULL
, var
);
1863 def
= SSA_NAME_DEF_STMT (var
);
1864 bb
= gimple_bb (def
);
1865 def_loop
= bb
? bb
->loop_father
: NULL
;
1868 || !flow_bb_inside_loop_p (loop
, bb
))
1870 /* Keep the symbolic form. */
1875 if (res
!= chrec_not_analyzed_yet
)
1877 if (loop
!= bb
->loop_father
)
1878 res
= compute_scalar_evolution_in_loop
1879 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1884 if (loop
!= def_loop
)
1886 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1887 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1892 switch (gimple_code (def
))
1895 res
= interpret_gimple_assign (loop
, def
);
1899 if (loop_phi_node_p (def
))
1900 res
= interpret_loop_phi (loop
, def
);
1902 res
= interpret_condition_phi (loop
, def
);
1906 res
= chrec_dont_know
;
1912 /* Keep the symbolic form. */
1913 if (res
== chrec_dont_know
)
1916 if (loop
== def_loop
)
1917 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1922 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1923 LOOP. LOOP is the loop in which the variable is used.
1925 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1926 pointer to the statement that uses this variable, in order to
1927 determine the evolution function of the variable, use the following
1930 loop_p loop = loop_containing_stmt (stmt);
1931 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1932 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1936 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1940 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1942 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1943 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1944 fprintf (dump_file
, " (scalar = ");
1945 print_generic_expr (dump_file
, var
, 0);
1946 fprintf (dump_file
, ")\n");
1949 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1950 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1953 fprintf (dump_file
, ")\n");
1958 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1959 WRTO_LOOP (which should be a superloop of USE_LOOP)
1961 FOLDED_CASTS is set to true if resolve_mixers used
1962 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1963 at the moment in order to keep things simple).
1965 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1968 for (i = 0; i < 100; i++) -- loop 1
1970 for (j = 0; j < 100; j++) -- loop 2
1977 for (t = 0; t < 100; t++) -- loop 3
1984 Both k1 and k2 are invariants in loop3, thus
1985 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1986 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1988 As they are invariant, it does not matter whether we consider their
1989 usage in loop 3 or loop 2, hence
1990 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1991 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1992 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1993 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1995 Similarly for their evolutions with respect to loop 1. The values of K2
1996 in the use in loop 2 vary independently on loop 1, thus we cannot express
1997 the evolution with respect to loop 1:
1998 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
1999 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2000 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2001 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2003 The value of k2 in the use in loop 1 is known, though:
2004 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2005 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2009 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2010 tree version
, bool *folded_casts
)
2013 tree ev
= version
, tmp
;
2015 /* We cannot just do
2017 tmp = analyze_scalar_evolution (use_loop, version);
2018 ev = resolve_mixers (wrto_loop, tmp);
2020 as resolve_mixers would query the scalar evolution with respect to
2021 wrto_loop. For example, in the situation described in the function
2022 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2025 analyze_scalar_evolution (use_loop, version) = k2
2027 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2028 is 100, which is a wrong result, since we are interested in the
2031 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2032 each time checking that there is no evolution in the inner loop. */
2035 *folded_casts
= false;
2038 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2039 ev
= resolve_mixers (use_loop
, tmp
);
2041 if (folded_casts
&& tmp
!= ev
)
2042 *folded_casts
= true;
2044 if (use_loop
== wrto_loop
)
2047 /* If the value of the use changes in the inner loop, we cannot express
2048 its value in the outer loop (we might try to return interval chrec,
2049 but we do not have a user for it anyway) */
2050 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2052 return chrec_dont_know
;
2054 use_loop
= loop_outer (use_loop
);
2058 /* Returns from CACHE the value for VERSION instantiated below
2059 INSTANTIATED_BELOW block. */
2062 get_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2065 struct scev_info_str
*info
, pattern
;
2067 pattern
.var
= version
;
2068 pattern
.instantiated_below
= instantiated_below
;
2069 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2077 /* Sets in CACHE the value of VERSION instantiated below basic block
2078 INSTANTIATED_BELOW to VAL. */
2081 set_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2082 tree version
, tree val
)
2084 struct scev_info_str
*info
, pattern
;
2087 pattern
.var
= version
;
2088 pattern
.instantiated_below
= instantiated_below
;
2089 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2092 *slot
= new_scev_info_str (instantiated_below
, version
);
2093 info
= (struct scev_info_str
*) *slot
;
2097 /* Return the closed_loop_phi node for VAR. If there is none, return
2101 loop_closed_phi_def (tree var
)
2106 gimple_stmt_iterator psi
;
2108 if (var
== NULL_TREE
2109 || TREE_CODE (var
) != SSA_NAME
)
2112 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2113 exit
= single_exit (loop
);
2117 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2119 phi
= gsi_stmt (psi
);
2120 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2121 return PHI_RESULT (phi
);
2127 static tree
instantiate_scev_r (basic_block
, struct loop
*, tree
, bool,
2130 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2131 and EVOLUTION_LOOP, that were left under a symbolic form.
2133 CHREC is an SSA_NAME to be instantiated.
2135 CACHE is the cache of already instantiated values.
2137 FOLD_CONVERSIONS should be set to true when the conversions that
2138 may wrap in signed/pointer type are folded, as long as the value of
2139 the chrec is preserved.
2141 SIZE_EXPR is used for computing the size of the expression to be
2142 instantiated, and to stop if it exceeds some limit. */
2145 instantiate_scev_name (basic_block instantiate_below
,
2146 struct loop
*evolution_loop
, tree chrec
,
2147 bool fold_conversions
, htab_t cache
, int size_expr
)
2150 struct loop
*def_loop
;
2151 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2153 /* A parameter (or loop invariant and we do not want to include
2154 evolutions in outer loops), nothing to do. */
2156 || loop_depth (def_bb
->loop_father
) == 0
2157 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2160 /* We cache the value of instantiated variable to avoid exponential
2161 time complexity due to reevaluations. We also store the convenient
2162 value in the cache in order to prevent infinite recursion -- we do
2163 not want to instantiate the SSA_NAME if it is in a mixer
2164 structure. This is used for avoiding the instantiation of
2165 recursively defined functions, such as:
2167 | a_2 -> {0, +, 1, +, a_2}_1 */
2169 res
= get_instantiated_value (cache
, instantiate_below
, chrec
);
2173 res
= chrec_dont_know
;
2174 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2176 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2178 /* If the analysis yields a parametric chrec, instantiate the
2180 res
= analyze_scalar_evolution (def_loop
, chrec
);
2182 /* Don't instantiate loop-closed-ssa phi nodes. */
2183 if (TREE_CODE (res
) == SSA_NAME
2184 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2185 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2186 > loop_depth (def_loop
))))
2189 res
= loop_closed_phi_def (chrec
);
2193 /* When there is no loop_closed_phi_def, it means that the
2194 variable is not used after the loop: try to still compute the
2195 value of the variable when exiting the loop. */
2196 if (res
== NULL_TREE
)
2198 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2199 res
= analyze_scalar_evolution (loop
, chrec
);
2200 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2201 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2202 fold_conversions
, cache
, size_expr
);
2204 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2205 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2206 res
= chrec_dont_know
;
2209 else if (res
!= chrec_dont_know
)
2210 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2211 fold_conversions
, cache
, size_expr
);
2213 /* Store the correct value to the cache. */
2214 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2219 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2220 and EVOLUTION_LOOP, that were left under a symbolic form.
2222 CHREC is a polynomial chain of recurrence to be instantiated.
2224 CACHE is the cache of already instantiated values.
2226 FOLD_CONVERSIONS should be set to true when the conversions that
2227 may wrap in signed/pointer type are folded, as long as the value of
2228 the chrec is preserved.
2230 SIZE_EXPR is used for computing the size of the expression to be
2231 instantiated, and to stop if it exceeds some limit. */
2234 instantiate_scev_poly (basic_block instantiate_below
,
2235 struct loop
*evolution_loop
, tree chrec
,
2236 bool fold_conversions
, htab_t cache
, int size_expr
)
2239 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2240 CHREC_LEFT (chrec
), fold_conversions
, cache
,
2242 if (op0
== chrec_dont_know
)
2243 return chrec_dont_know
;
2245 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2246 CHREC_RIGHT (chrec
), fold_conversions
, cache
,
2248 if (op1
== chrec_dont_know
)
2249 return chrec_dont_know
;
2251 if (CHREC_LEFT (chrec
) != op0
2252 || CHREC_RIGHT (chrec
) != op1
)
2254 unsigned var
= CHREC_VARIABLE (chrec
);
2256 /* When the instantiated stride or base has an evolution in an
2257 innermost loop, return chrec_dont_know, as this is not a
2258 valid SCEV representation. In the reduced testcase for
2259 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2261 if ((tree_is_chrec (op0
) && CHREC_VARIABLE (op0
) > var
)
2262 || (tree_is_chrec (op1
) && CHREC_VARIABLE (op1
) > var
))
2263 return chrec_dont_know
;
2265 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2266 chrec
= build_polynomial_chrec (var
, op0
, op1
);
2272 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2273 and EVOLUTION_LOOP, that were left under a symbolic form.
2275 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2277 CACHE is the cache of already instantiated values.
2279 FOLD_CONVERSIONS should be set to true when the conversions that
2280 may wrap in signed/pointer type are folded, as long as the value of
2281 the chrec is preserved.
2283 SIZE_EXPR is used for computing the size of the expression to be
2284 instantiated, and to stop if it exceeds some limit. */
2287 instantiate_scev_binary (basic_block instantiate_below
,
2288 struct loop
*evolution_loop
, tree chrec
, enum tree_code code
,
2289 tree type
, tree c0
, tree c1
,
2290 bool fold_conversions
, htab_t cache
, int size_expr
)
2293 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2294 c0
, fold_conversions
, cache
,
2296 if (op0
== chrec_dont_know
)
2297 return chrec_dont_know
;
2299 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2300 c1
, fold_conversions
, cache
,
2302 if (op1
== chrec_dont_know
)
2303 return chrec_dont_know
;
2308 op0
= chrec_convert (type
, op0
, NULL
);
2309 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2313 case POINTER_PLUS_EXPR
:
2315 return chrec_fold_plus (type
, op0
, op1
);
2318 return chrec_fold_minus (type
, op0
, op1
);
2321 return chrec_fold_multiply (type
, op0
, op1
);
2328 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2331 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2332 and EVOLUTION_LOOP, that were left under a symbolic form.
2334 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2337 CACHE is the cache of already instantiated values.
2339 FOLD_CONVERSIONS should be set to true when the conversions that
2340 may wrap in signed/pointer type are folded, as long as the value of
2341 the chrec is preserved.
2343 SIZE_EXPR is used for computing the size of the expression to be
2344 instantiated, and to stop if it exceeds some limit. */
2347 instantiate_scev_convert (basic_block instantiate_below
,
2348 struct loop
*evolution_loop
, tree chrec
,
2350 bool fold_conversions
, htab_t cache
, int size_expr
)
2352 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2353 fold_conversions
, cache
, size_expr
);
2355 if (op0
== chrec_dont_know
)
2356 return chrec_dont_know
;
2358 if (fold_conversions
)
2360 tree tmp
= chrec_convert_aggressive (type
, op0
);
2365 if (chrec
&& op0
== op
)
2368 /* If we used chrec_convert_aggressive, we can no longer assume that
2369 signed chrecs do not overflow, as chrec_convert does, so avoid
2370 calling it in that case. */
2371 if (fold_conversions
)
2372 return fold_convert (type
, op0
);
2374 return chrec_convert (type
, op0
, NULL
);
2377 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2378 and EVOLUTION_LOOP, that were left under a symbolic form.
2380 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2381 Handle ~X as -1 - X.
2382 Handle -X as -1 * X.
2384 CACHE is the cache of already instantiated values.
2386 FOLD_CONVERSIONS should be set to true when the conversions that
2387 may wrap in signed/pointer type are folded, as long as the value of
2388 the chrec is preserved.
2390 SIZE_EXPR is used for computing the size of the expression to be
2391 instantiated, and to stop if it exceeds some limit. */
2394 instantiate_scev_not (basic_block instantiate_below
,
2395 struct loop
*evolution_loop
, tree chrec
,
2396 enum tree_code code
, tree type
, tree op
,
2397 bool fold_conversions
, htab_t cache
, int size_expr
)
2399 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2400 fold_conversions
, cache
, size_expr
);
2402 if (op0
== chrec_dont_know
)
2403 return chrec_dont_know
;
2407 op0
= chrec_convert (type
, op0
, NULL
);
2412 return chrec_fold_minus
2413 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2416 return chrec_fold_multiply
2417 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2424 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2427 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2428 and EVOLUTION_LOOP, that were left under a symbolic form.
2430 CHREC is an expression with 3 operands to be instantiated.
2432 CACHE is the cache of already instantiated values.
2434 FOLD_CONVERSIONS should be set to true when the conversions that
2435 may wrap in signed/pointer type are folded, as long as the value of
2436 the chrec is preserved.
2438 SIZE_EXPR is used for computing the size of the expression to be
2439 instantiated, and to stop if it exceeds some limit. */
2442 instantiate_scev_3 (basic_block instantiate_below
,
2443 struct loop
*evolution_loop
, tree chrec
,
2444 bool fold_conversions
, htab_t cache
, int size_expr
)
2447 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2448 TREE_OPERAND (chrec
, 0),
2449 fold_conversions
, cache
, size_expr
);
2450 if (op0
== chrec_dont_know
)
2451 return chrec_dont_know
;
2453 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2454 TREE_OPERAND (chrec
, 1),
2455 fold_conversions
, cache
, size_expr
);
2456 if (op1
== chrec_dont_know
)
2457 return chrec_dont_know
;
2459 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2460 TREE_OPERAND (chrec
, 2),
2461 fold_conversions
, cache
, size_expr
);
2462 if (op2
== chrec_dont_know
)
2463 return chrec_dont_know
;
2465 if (op0
== TREE_OPERAND (chrec
, 0)
2466 && op1
== TREE_OPERAND (chrec
, 1)
2467 && op2
== TREE_OPERAND (chrec
, 2))
2470 return fold_build3 (TREE_CODE (chrec
),
2471 TREE_TYPE (chrec
), op0
, op1
, op2
);
2474 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2475 and EVOLUTION_LOOP, that were left under a symbolic form.
2477 CHREC is an expression with 2 operands to be instantiated.
2479 CACHE is the cache of already instantiated values.
2481 FOLD_CONVERSIONS should be set to true when the conversions that
2482 may wrap in signed/pointer type are folded, as long as the value of
2483 the chrec is preserved.
2485 SIZE_EXPR is used for computing the size of the expression to be
2486 instantiated, and to stop if it exceeds some limit. */
2489 instantiate_scev_2 (basic_block instantiate_below
,
2490 struct loop
*evolution_loop
, tree chrec
,
2491 bool fold_conversions
, htab_t cache
, int size_expr
)
2494 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2495 TREE_OPERAND (chrec
, 0),
2496 fold_conversions
, cache
, size_expr
);
2497 if (op0
== chrec_dont_know
)
2498 return chrec_dont_know
;
2500 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2501 TREE_OPERAND (chrec
, 1),
2502 fold_conversions
, cache
, size_expr
);
2503 if (op1
== chrec_dont_know
)
2504 return chrec_dont_know
;
2506 if (op0
== TREE_OPERAND (chrec
, 0)
2507 && op1
== TREE_OPERAND (chrec
, 1))
2510 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2513 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2514 and EVOLUTION_LOOP, that were left under a symbolic form.
2516 CHREC is an expression with 2 operands to be instantiated.
2518 CACHE is the cache of already instantiated values.
2520 FOLD_CONVERSIONS should be set to true when the conversions that
2521 may wrap in signed/pointer type are folded, as long as the value of
2522 the chrec is preserved.
2524 SIZE_EXPR is used for computing the size of the expression to be
2525 instantiated, and to stop if it exceeds some limit. */
2528 instantiate_scev_1 (basic_block instantiate_below
,
2529 struct loop
*evolution_loop
, tree chrec
,
2530 bool fold_conversions
, htab_t cache
, int size_expr
)
2532 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2533 TREE_OPERAND (chrec
, 0),
2534 fold_conversions
, cache
, size_expr
);
2536 if (op0
== chrec_dont_know
)
2537 return chrec_dont_know
;
2539 if (op0
== TREE_OPERAND (chrec
, 0))
2542 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2545 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2546 and EVOLUTION_LOOP, that were left under a symbolic form.
2548 CHREC is the scalar evolution to instantiate.
2550 CACHE is the cache of already instantiated values.
2552 FOLD_CONVERSIONS should be set to true when the conversions that
2553 may wrap in signed/pointer type are folded, as long as the value of
2554 the chrec is preserved.
2556 SIZE_EXPR is used for computing the size of the expression to be
2557 instantiated, and to stop if it exceeds some limit. */
2560 instantiate_scev_r (basic_block instantiate_below
,
2561 struct loop
*evolution_loop
, tree chrec
,
2562 bool fold_conversions
, htab_t cache
, int size_expr
)
2564 /* Give up if the expression is larger than the MAX that we allow. */
2565 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2566 return chrec_dont_know
;
2568 if (automatically_generated_chrec_p (chrec
)
2569 || is_gimple_min_invariant (chrec
))
2572 switch (TREE_CODE (chrec
))
2575 return instantiate_scev_name (instantiate_below
, evolution_loop
, chrec
,
2576 fold_conversions
, cache
, size_expr
);
2578 case POLYNOMIAL_CHREC
:
2579 return instantiate_scev_poly (instantiate_below
, evolution_loop
, chrec
,
2580 fold_conversions
, cache
, size_expr
);
2582 case POINTER_PLUS_EXPR
:
2586 return instantiate_scev_binary (instantiate_below
, evolution_loop
, chrec
,
2587 TREE_CODE (chrec
), chrec_type (chrec
),
2588 TREE_OPERAND (chrec
, 0),
2589 TREE_OPERAND (chrec
, 1),
2590 fold_conversions
, cache
, size_expr
);
2593 return instantiate_scev_convert (instantiate_below
, evolution_loop
, chrec
,
2594 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2595 fold_conversions
, cache
, size_expr
);
2599 return instantiate_scev_not (instantiate_below
, evolution_loop
, chrec
,
2600 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2601 TREE_OPERAND (chrec
, 0),
2602 fold_conversions
, cache
, size_expr
);
2604 case SCEV_NOT_KNOWN
:
2605 return chrec_dont_know
;
2614 if (VL_EXP_CLASS_P (chrec
))
2615 return chrec_dont_know
;
2617 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2620 return instantiate_scev_3 (instantiate_below
, evolution_loop
, chrec
,
2621 fold_conversions
, cache
, size_expr
);
2624 return instantiate_scev_2 (instantiate_below
, evolution_loop
, chrec
,
2625 fold_conversions
, cache
, size_expr
);
2628 return instantiate_scev_1 (instantiate_below
, evolution_loop
, chrec
,
2629 fold_conversions
, cache
, size_expr
);
2638 /* Too complicated to handle. */
2639 return chrec_dont_know
;
2642 /* Analyze all the parameters of the chrec that were left under a
2643 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2644 recursive instantiation of parameters: a parameter is a variable
2645 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2646 a function parameter. */
2649 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2653 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2655 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2657 fprintf (dump_file
, "(instantiate_scev \n");
2658 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2659 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2660 fprintf (dump_file
, " (chrec = ");
2661 print_generic_expr (dump_file
, chrec
, 0);
2662 fprintf (dump_file
, ")\n");
2665 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, chrec
, false,
2668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 fprintf (dump_file
, " (res = ");
2671 print_generic_expr (dump_file
, res
, 0);
2672 fprintf (dump_file
, "))\n");
2675 htab_delete (cache
);
2680 /* Similar to instantiate_parameters, but does not introduce the
2681 evolutions in outer loops for LOOP invariants in CHREC, and does not
2682 care about causing overflows, as long as they do not affect value
2683 of an expression. */
2686 resolve_mixers (struct loop
*loop
, tree chrec
)
2688 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2689 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, chrec
, true,
2691 htab_delete (cache
);
2695 /* Entry point for the analysis of the number of iterations pass.
2696 This function tries to safely approximate the number of iterations
2697 the loop will run. When this property is not decidable at compile
2698 time, the result is chrec_dont_know. Otherwise the result is a
2699 scalar or a symbolic parameter. When the number of iterations may
2700 be equal to zero and the property cannot be determined at compile
2701 time, the result is a COND_EXPR that represents in a symbolic form
2702 the conditions under which the number of iterations is not zero.
2704 Example of analysis: suppose that the loop has an exit condition:
2706 "if (b > 49) goto end_loop;"
2708 and that in a previous analysis we have determined that the
2709 variable 'b' has an evolution function:
2711 "EF = {23, +, 5}_2".
2713 When we evaluate the function at the point 5, i.e. the value of the
2714 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2715 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2716 the loop body has been executed 6 times. */
2719 number_of_latch_executions (struct loop
*loop
)
2722 struct tree_niter_desc niter_desc
;
2726 /* Determine whether the number of iterations in loop has already
2728 res
= loop
->nb_iterations
;
2732 may_be_zero
= NULL_TREE
;
2734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2735 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2737 res
= chrec_dont_know
;
2738 exit
= single_exit (loop
);
2740 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2742 may_be_zero
= niter_desc
.may_be_zero
;
2743 res
= niter_desc
.niter
;
2746 if (res
== chrec_dont_know
2748 || integer_zerop (may_be_zero
))
2750 else if (integer_nonzerop (may_be_zero
))
2751 res
= build_int_cst (TREE_TYPE (res
), 0);
2753 else if (COMPARISON_CLASS_P (may_be_zero
))
2754 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2755 build_int_cst (TREE_TYPE (res
), 0), res
);
2757 res
= chrec_dont_know
;
2759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2761 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2762 print_generic_expr (dump_file
, res
, 0);
2763 fprintf (dump_file
, "))\n");
2766 loop
->nb_iterations
= res
;
2770 /* Returns the number of executions of the exit condition of LOOP,
2771 i.e., the number by one higher than number_of_latch_executions.
2772 Note that unlike number_of_latch_executions, this number does
2773 not necessarily fit in the unsigned variant of the type of
2774 the control variable -- if the number of iterations is a constant,
2775 we return chrec_dont_know if adding one to number_of_latch_executions
2776 overflows; however, in case the number of iterations is symbolic
2777 expression, the caller is responsible for dealing with this
2778 the possible overflow. */
2781 number_of_exit_cond_executions (struct loop
*loop
)
2783 tree ret
= number_of_latch_executions (loop
);
2784 tree type
= chrec_type (ret
);
2786 if (chrec_contains_undetermined (ret
))
2789 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2790 if (TREE_CODE (ret
) == INTEGER_CST
2791 && TREE_OVERFLOW (ret
))
2792 return chrec_dont_know
;
2797 /* One of the drivers for testing the scalar evolutions analysis.
2798 This function computes the number of iterations for all the loops
2799 from the EXIT_CONDITIONS array. */
2802 number_of_iterations_for_all_loops (VEC(gimple
,heap
) **exit_conditions
)
2805 unsigned nb_chrec_dont_know_loops
= 0;
2806 unsigned nb_static_loops
= 0;
2809 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2811 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2812 if (chrec_contains_undetermined (res
))
2813 nb_chrec_dont_know_loops
++;
2820 fprintf (dump_file
, "\n(\n");
2821 fprintf (dump_file
, "-----------------------------------------\n");
2822 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2823 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2824 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2825 fprintf (dump_file
, "-----------------------------------------\n");
2826 fprintf (dump_file
, ")\n\n");
2828 print_loops (dump_file
, 3);
2834 /* Counters for the stats. */
2840 unsigned nb_affine_multivar
;
2841 unsigned nb_higher_poly
;
2842 unsigned nb_chrec_dont_know
;
2843 unsigned nb_undetermined
;
2846 /* Reset the counters. */
2849 reset_chrecs_counters (struct chrec_stats
*stats
)
2851 stats
->nb_chrecs
= 0;
2852 stats
->nb_affine
= 0;
2853 stats
->nb_affine_multivar
= 0;
2854 stats
->nb_higher_poly
= 0;
2855 stats
->nb_chrec_dont_know
= 0;
2856 stats
->nb_undetermined
= 0;
2859 /* Dump the contents of a CHREC_STATS structure. */
2862 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2864 fprintf (file
, "\n(\n");
2865 fprintf (file
, "-----------------------------------------\n");
2866 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2867 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2868 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2869 stats
->nb_higher_poly
);
2870 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2871 fprintf (file
, "-----------------------------------------\n");
2872 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2873 fprintf (file
, "%d\twith undetermined coefficients\n",
2874 stats
->nb_undetermined
);
2875 fprintf (file
, "-----------------------------------------\n");
2876 fprintf (file
, "%d\tchrecs in the scev database\n",
2877 (int) htab_elements (scalar_evolution_info
));
2878 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2879 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2880 fprintf (file
, "-----------------------------------------\n");
2881 fprintf (file
, ")\n\n");
2884 /* Gather statistics about CHREC. */
2887 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2889 if (dump_file
&& (dump_flags
& TDF_STATS
))
2891 fprintf (dump_file
, "(classify_chrec ");
2892 print_generic_expr (dump_file
, chrec
, 0);
2893 fprintf (dump_file
, "\n");
2898 if (chrec
== NULL_TREE
)
2900 stats
->nb_undetermined
++;
2904 switch (TREE_CODE (chrec
))
2906 case POLYNOMIAL_CHREC
:
2907 if (evolution_function_is_affine_p (chrec
))
2909 if (dump_file
&& (dump_flags
& TDF_STATS
))
2910 fprintf (dump_file
, " affine_univariate\n");
2913 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2915 if (dump_file
&& (dump_flags
& TDF_STATS
))
2916 fprintf (dump_file
, " affine_multivariate\n");
2917 stats
->nb_affine_multivar
++;
2921 if (dump_file
&& (dump_flags
& TDF_STATS
))
2922 fprintf (dump_file
, " higher_degree_polynomial\n");
2923 stats
->nb_higher_poly
++;
2932 if (chrec_contains_undetermined (chrec
))
2934 if (dump_file
&& (dump_flags
& TDF_STATS
))
2935 fprintf (dump_file
, " undetermined\n");
2936 stats
->nb_undetermined
++;
2939 if (dump_file
&& (dump_flags
& TDF_STATS
))
2940 fprintf (dump_file
, ")\n");
2943 /* One of the drivers for testing the scalar evolutions analysis.
2944 This function analyzes the scalar evolution of all the scalars
2945 defined as loop phi nodes in one of the loops from the
2946 EXIT_CONDITIONS array.
2948 TODO Optimization: A loop is in canonical form if it contains only
2949 a single scalar loop phi node. All the other scalars that have an
2950 evolution in the loop are rewritten in function of this single
2951 index. This allows the parallelization of the loop. */
2954 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple
,heap
) **exit_conditions
)
2957 struct chrec_stats stats
;
2959 gimple_stmt_iterator psi
;
2961 reset_chrecs_counters (&stats
);
2963 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2969 loop
= loop_containing_stmt (cond
);
2972 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2974 phi
= gsi_stmt (psi
);
2975 if (is_gimple_reg (PHI_RESULT (phi
)))
2977 chrec
= instantiate_parameters
2979 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2981 if (dump_file
&& (dump_flags
& TDF_STATS
))
2982 gather_chrec_stats (chrec
, &stats
);
2987 if (dump_file
&& (dump_flags
& TDF_STATS
))
2988 dump_chrecs_stats (dump_file
, &stats
);
2991 /* Callback for htab_traverse, gathers information on chrecs in the
2995 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2997 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2999 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3004 /* Classify the chrecs of the whole database. */
3007 gather_stats_on_scev_database (void)
3009 struct chrec_stats stats
;
3014 reset_chrecs_counters (&stats
);
3016 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3019 dump_chrecs_stats (dump_file
, &stats
);
3027 initialize_scalar_evolutions_analyzer (void)
3029 /* The elements below are unique. */
3030 if (chrec_dont_know
== NULL_TREE
)
3032 chrec_not_analyzed_yet
= NULL_TREE
;
3033 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3034 chrec_known
= make_node (SCEV_KNOWN
);
3035 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3036 TREE_TYPE (chrec_known
) = void_type_node
;
3040 /* Initialize the analysis of scalar evolutions for LOOPS. */
3043 scev_initialize (void)
3049 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3052 initialize_scalar_evolutions_analyzer ();
3054 FOR_EACH_LOOP (li
, loop
, 0)
3056 loop
->nb_iterations
= NULL_TREE
;
3060 /* Cleans up the information cached by the scalar evolutions analysis
3061 in the hash table. */
3064 scev_reset_htab (void)
3066 if (!scalar_evolution_info
)
3069 htab_empty (scalar_evolution_info
);
3072 /* Cleans up the information cached by the scalar evolutions analysis
3073 in the hash table and in the loop->nb_iterations. */
3086 FOR_EACH_LOOP (li
, loop
, 0)
3088 loop
->nb_iterations
= NULL_TREE
;
3092 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3093 respect to WRTO_LOOP and returns its base and step in IV if possible
3094 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3095 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3096 invariant in LOOP. Otherwise we require it to be an integer constant.
3098 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3099 because it is computed in signed arithmetics). Consequently, adding an
3102 for (i = IV->base; ; i += IV->step)
3104 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3105 false for the type of the induction variable, or you can prove that i does
3106 not wrap by some other argument. Otherwise, this might introduce undefined
3109 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3111 must be used instead. */
3114 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3115 affine_iv
*iv
, bool allow_nonconstant_step
)
3120 iv
->base
= NULL_TREE
;
3121 iv
->step
= NULL_TREE
;
3122 iv
->no_overflow
= false;
3124 type
= TREE_TYPE (op
);
3125 if (TREE_CODE (type
) != INTEGER_TYPE
3126 && TREE_CODE (type
) != POINTER_TYPE
)
3129 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3131 if (chrec_contains_undetermined (ev
)
3132 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3135 if (tree_does_not_contain_chrecs (ev
))
3138 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3139 iv
->no_overflow
= true;
3143 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3144 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3147 iv
->step
= CHREC_RIGHT (ev
);
3148 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3149 || tree_contains_chrecs (iv
->step
, NULL
))
3152 iv
->base
= CHREC_LEFT (ev
);
3153 if (tree_contains_chrecs (iv
->base
, NULL
))
3156 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3161 /* Runs the analysis of scalar evolutions. */
3164 scev_analysis (void)
3166 VEC(gimple
,heap
) *exit_conditions
;
3168 exit_conditions
= VEC_alloc (gimple
, heap
, 37);
3169 select_loops_exit_conditions (&exit_conditions
);
3171 if (dump_file
&& (dump_flags
& TDF_STATS
))
3172 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
3174 number_of_iterations_for_all_loops (&exit_conditions
);
3175 VEC_free (gimple
, heap
, exit_conditions
);
3178 /* Finalize the scalar evolution analysis. */
3181 scev_finalize (void)
3183 if (!scalar_evolution_info
)
3185 htab_delete (scalar_evolution_info
);
3186 scalar_evolution_info
= NULL
;
3189 /* Returns true if the expression EXPR is considered to be too expensive
3190 for scev_const_prop. */
3193 expression_expensive_p (tree expr
)
3195 enum tree_code code
;
3197 if (is_gimple_val (expr
))
3200 code
= TREE_CODE (expr
);
3201 if (code
== TRUNC_DIV_EXPR
3202 || code
== CEIL_DIV_EXPR
3203 || code
== FLOOR_DIV_EXPR
3204 || code
== ROUND_DIV_EXPR
3205 || code
== TRUNC_MOD_EXPR
3206 || code
== CEIL_MOD_EXPR
3207 || code
== FLOOR_MOD_EXPR
3208 || code
== ROUND_MOD_EXPR
3209 || code
== EXACT_DIV_EXPR
)
3211 /* Division by power of two is usually cheap, so we allow it.
3212 Forbid anything else. */
3213 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3217 switch (TREE_CODE_CLASS (code
))
3220 case tcc_comparison
:
3221 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3226 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3233 /* Replace ssa names for that scev can prove they are constant by the
3234 appropriate constants. Also perform final value replacement in loops,
3235 in case the replacement expressions are cheap.
3237 We only consider SSA names defined by phi nodes; rest is left to the
3238 ordinary constant propagation pass. */
3241 scev_const_prop (void)
3244 tree name
, type
, ev
;
3246 struct loop
*loop
, *ex_loop
;
3247 bitmap ssa_names_to_remove
= NULL
;
3250 gimple_stmt_iterator psi
;
3252 if (number_of_loops () <= 1)
3257 loop
= bb
->loop_father
;
3259 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3261 phi
= gsi_stmt (psi
);
3262 name
= PHI_RESULT (phi
);
3264 if (!is_gimple_reg (name
))
3267 type
= TREE_TYPE (name
);
3269 if (!POINTER_TYPE_P (type
)
3270 && !INTEGRAL_TYPE_P (type
))
3273 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3274 if (!is_gimple_min_invariant (ev
)
3275 || !may_propagate_copy (name
, ev
))
3278 /* Replace the uses of the name. */
3280 replace_uses_by (name
, ev
);
3282 if (!ssa_names_to_remove
)
3283 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3284 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3288 /* Remove the ssa names that were replaced by constants. We do not
3289 remove them directly in the previous cycle, since this
3290 invalidates scev cache. */
3291 if (ssa_names_to_remove
)
3295 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3297 gimple_stmt_iterator psi
;
3298 name
= ssa_name (i
);
3299 phi
= SSA_NAME_DEF_STMT (name
);
3301 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3302 psi
= gsi_for_stmt (phi
);
3303 remove_phi_node (&psi
, true);
3306 BITMAP_FREE (ssa_names_to_remove
);
3310 /* Now the regular final value replacement. */
3311 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3314 tree def
, rslt
, niter
;
3315 gimple_stmt_iterator bsi
;
3317 /* If we do not know exact number of iterations of the loop, we cannot
3318 replace the final value. */
3319 exit
= single_exit (loop
);
3323 niter
= number_of_latch_executions (loop
);
3324 if (niter
== chrec_dont_know
)
3327 /* Ensure that it is possible to insert new statements somewhere. */
3328 if (!single_pred_p (exit
->dest
))
3329 split_loop_exit_edge (exit
);
3330 bsi
= gsi_after_labels (exit
->dest
);
3332 ex_loop
= superloop_at_depth (loop
,
3333 loop_depth (exit
->dest
->loop_father
) + 1);
3335 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3337 phi
= gsi_stmt (psi
);
3338 rslt
= PHI_RESULT (phi
);
3339 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3340 if (!is_gimple_reg (def
))
3346 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3347 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3353 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3354 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3355 if (!tree_does_not_contain_chrecs (def
)
3356 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3357 /* Moving the computation from the loop may prolong life range
3358 of some ssa names, which may cause problems if they appear
3359 on abnormal edges. */
3360 || contains_abnormal_ssa_name_p (def
)
3361 /* Do not emit expensive expressions. The rationale is that
3362 when someone writes a code like
3364 while (n > 45) n -= 45;
3366 he probably knows that n is not large, and does not want it
3367 to be turned into n %= 45. */
3368 || expression_expensive_p (def
))
3374 /* Eliminate the PHI node and replace it by a computation outside
3376 def
= unshare_expr (def
);
3377 remove_phi_node (&psi
, false);
3379 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3380 true, GSI_SAME_STMT
);
3381 ass
= gimple_build_assign (rslt
, def
);
3382 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3388 #include "gt-tree-scalar-evolution.h"