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
) == SSA_NAME
)
391 loop_p def_loop
, loop
;
393 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
396 def
= SSA_NAME_DEF_STMT (chrec
);
397 def_loop
= loop_containing_stmt (def
);
398 loop
= get_loop (loop_nb
);
400 if (def_loop
== NULL
)
403 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
409 n
= TREE_OPERAND_LENGTH (chrec
);
410 for (i
= 0; i
< n
; i
++)
411 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
417 /* Return true when PHI is a loop-phi-node. */
420 loop_phi_node_p (gimple phi
)
422 /* The implementation of this function is based on the following
423 property: "all the loop-phi-nodes of a loop are contained in the
424 loop's header basic block". */
426 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
429 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
430 In general, in the case of multivariate evolutions we want to get
431 the evolution in different loops. LOOP specifies the level for
432 which to get the evolution.
436 | for (j = 0; j < 100; j++)
438 | for (k = 0; k < 100; k++)
440 | i = k + j; - Here the value of i is a function of j, k.
442 | ... = i - Here the value of i is a function of j.
444 | ... = i - Here the value of i is a scalar.
450 | i_1 = phi (i_0, i_2)
454 This loop has the same effect as:
455 LOOP_1 has the same effect as:
459 The overall effect of the loop, "i_0 + 20" in the previous example,
460 is obtained by passing in the parameters: LOOP = 1,
461 EVOLUTION_FN = {i_0, +, 2}_1.
465 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
469 if (evolution_fn
== chrec_dont_know
)
470 return chrec_dont_know
;
472 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
474 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
476 if (inner_loop
== loop
477 || flow_loop_nested_p (loop
, inner_loop
))
479 tree nb_iter
= number_of_latch_executions (inner_loop
);
481 if (nb_iter
== chrec_dont_know
)
482 return chrec_dont_know
;
487 /* evolution_fn is the evolution function in LOOP. Get
488 its value in the nb_iter-th iteration. */
489 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
491 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
492 res
= instantiate_parameters (loop
, res
);
494 /* Continue the computation until ending on a parent of LOOP. */
495 return compute_overall_effect_of_inner_loop (loop
, res
);
502 /* If the evolution function is an invariant, there is nothing to do. */
503 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
507 return chrec_dont_know
;
510 /* Determine whether the CHREC is always positive/negative. If the expression
511 cannot be statically analyzed, return false, otherwise set the answer into
515 chrec_is_positive (tree chrec
, bool *value
)
517 bool value0
, value1
, value2
;
518 tree end_value
, nb_iter
;
520 switch (TREE_CODE (chrec
))
522 case POLYNOMIAL_CHREC
:
523 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
524 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
527 /* FIXME -- overflows. */
528 if (value0
== value1
)
534 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
535 and the proof consists in showing that the sign never
536 changes during the execution of the loop, from 0 to
537 loop->nb_iterations. */
538 if (!evolution_function_is_affine_p (chrec
))
541 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
542 if (chrec_contains_undetermined (nb_iter
))
546 /* TODO -- If the test is after the exit, we may decrease the number of
547 iterations by one. */
549 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
552 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
554 if (!chrec_is_positive (end_value
, &value2
))
558 return value0
== value1
;
561 *value
= (tree_int_cst_sgn (chrec
) == 1);
569 /* Associate CHREC to SCALAR. */
572 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
576 if (TREE_CODE (scalar
) != SSA_NAME
)
579 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
583 if (dump_flags
& TDF_DETAILS
)
585 fprintf (dump_file
, "(set_scalar_evolution \n");
586 fprintf (dump_file
, " instantiated_below = %d \n",
587 instantiated_below
->index
);
588 fprintf (dump_file
, " (scalar = ");
589 print_generic_expr (dump_file
, scalar
, 0);
590 fprintf (dump_file
, ")\n (scalar_evolution = ");
591 print_generic_expr (dump_file
, chrec
, 0);
592 fprintf (dump_file
, "))\n");
594 if (dump_flags
& TDF_STATS
)
598 *scalar_info
= chrec
;
601 /* Retrieve the chrec associated to SCALAR instantiated below
602 INSTANTIATED_BELOW block. */
605 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
611 if (dump_flags
& TDF_DETAILS
)
613 fprintf (dump_file
, "(get_scalar_evolution \n");
614 fprintf (dump_file
, " (scalar = ");
615 print_generic_expr (dump_file
, scalar
, 0);
616 fprintf (dump_file
, ")\n");
618 if (dump_flags
& TDF_STATS
)
622 switch (TREE_CODE (scalar
))
625 res
= *find_var_scev_info (instantiated_below
, scalar
);
635 res
= chrec_not_analyzed_yet
;
639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
641 fprintf (dump_file
, " (scalar_evolution = ");
642 print_generic_expr (dump_file
, res
, 0);
643 fprintf (dump_file
, "))\n");
649 /* Helper function for add_to_evolution. Returns the evolution
650 function for an assignment of the form "a = b + c", where "a" and
651 "b" are on the strongly connected component. CHREC_BEFORE is the
652 information that we already have collected up to this point.
653 TO_ADD is the evolution of "c".
655 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
656 evolution the expression TO_ADD, otherwise construct an evolution
657 part for this loop. */
660 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
663 tree type
, left
, right
;
664 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
666 switch (TREE_CODE (chrec_before
))
668 case POLYNOMIAL_CHREC
:
669 chloop
= get_chrec_loop (chrec_before
);
671 || flow_loop_nested_p (chloop
, loop
))
675 type
= chrec_type (chrec_before
);
677 /* When there is no evolution part in this loop, build it. */
682 right
= SCALAR_FLOAT_TYPE_P (type
)
683 ? build_real (type
, dconst0
)
684 : build_int_cst (type
, 0);
688 var
= CHREC_VARIABLE (chrec_before
);
689 left
= CHREC_LEFT (chrec_before
);
690 right
= CHREC_RIGHT (chrec_before
);
693 to_add
= chrec_convert (type
, to_add
, at_stmt
);
694 right
= chrec_convert_rhs (type
, right
, at_stmt
);
695 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
696 return build_polynomial_chrec (var
, left
, right
);
700 gcc_assert (flow_loop_nested_p (loop
, chloop
));
702 /* Search the evolution in LOOP_NB. */
703 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
705 right
= CHREC_RIGHT (chrec_before
);
706 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
707 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
712 /* These nodes do not depend on a loop. */
713 if (chrec_before
== chrec_dont_know
)
714 return chrec_dont_know
;
717 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
718 return build_polynomial_chrec (loop_nb
, left
, right
);
722 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
725 Description (provided for completeness, for those who read code in
726 a plane, and for my poor 62 bytes brain that would have forgotten
727 all this in the next two or three months):
729 The algorithm of translation of programs from the SSA representation
730 into the chrecs syntax is based on a pattern matching. After having
731 reconstructed the overall tree expression for a loop, there are only
732 two cases that can arise:
734 1. a = loop-phi (init, a + expr)
735 2. a = loop-phi (init, expr)
737 where EXPR is either a scalar constant with respect to the analyzed
738 loop (this is a degree 0 polynomial), or an expression containing
739 other loop-phi definitions (these are higher degree polynomials).
746 | a = phi (init, a + 5)
753 | a = phi (inita, 2 * b + 3)
754 | b = phi (initb, b + 1)
757 For the first case, the semantics of the SSA representation is:
759 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
761 that is, there is a loop index "x" that determines the scalar value
762 of the variable during the loop execution. During the first
763 iteration, the value is that of the initial condition INIT, while
764 during the subsequent iterations, it is the sum of the initial
765 condition with the sum of all the values of EXPR from the initial
766 iteration to the before last considered iteration.
768 For the second case, the semantics of the SSA program is:
770 | a (x) = init, if x = 0;
771 | expr (x - 1), otherwise.
773 The second case corresponds to the PEELED_CHREC, whose syntax is
774 close to the syntax of a loop-phi-node:
776 | phi (init, expr) vs. (init, expr)_x
778 The proof of the translation algorithm for the first case is a
779 proof by structural induction based on the degree of EXPR.
782 When EXPR is a constant with respect to the analyzed loop, or in
783 other words when EXPR is a polynomial of degree 0, the evolution of
784 the variable A in the loop is an affine function with an initial
785 condition INIT, and a step EXPR. In order to show this, we start
786 from the semantics of the SSA representation:
788 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
790 and since "expr (j)" is a constant with respect to "j",
792 f (x) = init + x * expr
794 Finally, based on the semantics of the pure sum chrecs, by
795 identification we get the corresponding chrecs syntax:
797 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
798 f (x) -> {init, +, expr}_x
801 Suppose that EXPR is a polynomial of degree N with respect to the
802 analyzed loop_x for which we have already determined that it is
803 written under the chrecs syntax:
805 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
807 We start from the semantics of the SSA program:
809 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
811 | f (x) = init + \sum_{j = 0}^{x - 1}
812 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
814 | f (x) = init + \sum_{j = 0}^{x - 1}
815 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
817 | f (x) = init + \sum_{k = 0}^{n - 1}
818 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
820 | f (x) = init + \sum_{k = 0}^{n - 1}
821 | (b_k * \binom{x}{k + 1})
823 | f (x) = init + b_0 * \binom{x}{1} + ...
824 | + b_{n-1} * \binom{x}{n}
826 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
827 | + b_{n-1} * \binom{x}{n}
830 And finally from the definition of the chrecs syntax, we identify:
831 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
833 This shows the mechanism that stands behind the add_to_evolution
834 function. An important point is that the use of symbolic
835 parameters avoids the need of an analysis schedule.
842 | a = phi (inita, a + 2 + b)
843 | b = phi (initb, b + 1)
846 When analyzing "a", the algorithm keeps "b" symbolically:
848 | a -> {inita, +, 2 + b}_1
850 Then, after instantiation, the analyzer ends on the evolution:
852 | a -> {inita, +, 2 + initb, +, 1}_1
857 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
858 tree to_add
, gimple at_stmt
)
860 tree type
= chrec_type (to_add
);
861 tree res
= NULL_TREE
;
863 if (to_add
== NULL_TREE
)
866 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
867 instantiated at this point. */
868 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
869 /* This should not happen. */
870 return chrec_dont_know
;
872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
874 fprintf (dump_file
, "(add_to_evolution \n");
875 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
876 fprintf (dump_file
, " (chrec_before = ");
877 print_generic_expr (dump_file
, chrec_before
, 0);
878 fprintf (dump_file
, ")\n (to_add = ");
879 print_generic_expr (dump_file
, to_add
, 0);
880 fprintf (dump_file
, ")\n");
883 if (code
== MINUS_EXPR
)
884 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
885 ? build_real (type
, dconstm1
)
886 : build_int_cst_type (type
, -1));
888 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
892 fprintf (dump_file
, " (res = ");
893 print_generic_expr (dump_file
, res
, 0);
894 fprintf (dump_file
, "))\n");
902 /* This section selects the loops that will be good candidates for the
903 scalar evolution analysis. For the moment, greedily select all the
904 loop nests we could analyze. */
906 /* For a loop with a single exit edge, return the COND_EXPR that
907 guards the exit edge. If the expression is too difficult to
908 analyze, then give up. */
911 get_loop_exit_condition (const struct loop
*loop
)
914 edge exit_edge
= single_exit (loop
);
916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
917 fprintf (dump_file
, "(get_loop_exit_condition \n ");
923 stmt
= last_stmt (exit_edge
->src
);
924 if (gimple_code (stmt
) == GIMPLE_COND
)
928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
930 print_gimple_stmt (dump_file
, res
, 0, 0);
931 fprintf (dump_file
, ")\n");
937 /* Recursively determine and enqueue the exit conditions for a loop. */
940 get_exit_conditions_rec (struct loop
*loop
,
941 VEC(gimple
,heap
) **exit_conditions
)
946 /* Recurse on the inner loops, then on the next (sibling) loops. */
947 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
948 get_exit_conditions_rec (loop
->next
, exit_conditions
);
950 if (single_exit (loop
))
952 gimple loop_condition
= get_loop_exit_condition (loop
);
955 VEC_safe_push (gimple
, heap
, *exit_conditions
, loop_condition
);
959 /* Select the candidate loop nests for the analysis. This function
960 initializes the EXIT_CONDITIONS array. */
963 select_loops_exit_conditions (VEC(gimple
,heap
) **exit_conditions
)
965 struct loop
*function_body
= current_loops
->tree_root
;
967 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
971 /* Depth first search algorithm. */
973 typedef enum t_bool
{
980 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
982 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
983 Return true if the strongly connected component has been found. */
986 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
987 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
988 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
990 t_bool res
= t_false
;
995 case POINTER_PLUS_EXPR
:
997 if (TREE_CODE (rhs0
) == SSA_NAME
)
999 if (TREE_CODE (rhs1
) == SSA_NAME
)
1001 /* Match an assignment under the form:
1004 /* We want only assignments of form "name + name" contribute to
1005 LIMIT, as the other cases do not necessarily contribute to
1006 the complexity of the expression. */
1009 evol
= *evolution_of_loop
;
1010 res
= follow_ssa_edge
1011 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
1014 *evolution_of_loop
= add_to_evolution
1016 chrec_convert (type
, evol
, at_stmt
),
1017 code
, rhs1
, at_stmt
);
1019 else if (res
== t_false
)
1021 res
= follow_ssa_edge
1022 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1023 evolution_of_loop
, limit
);
1026 *evolution_of_loop
= add_to_evolution
1028 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1029 code
, rhs0
, at_stmt
);
1031 else if (res
== t_dont_know
)
1032 *evolution_of_loop
= chrec_dont_know
;
1035 else if (res
== t_dont_know
)
1036 *evolution_of_loop
= chrec_dont_know
;
1041 /* Match an assignment under the form:
1043 res
= follow_ssa_edge
1044 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1045 evolution_of_loop
, limit
);
1047 *evolution_of_loop
= add_to_evolution
1048 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1050 code
, rhs1
, at_stmt
);
1052 else if (res
== t_dont_know
)
1053 *evolution_of_loop
= chrec_dont_know
;
1057 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1059 /* Match an assignment under the form:
1061 res
= follow_ssa_edge
1062 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1063 evolution_of_loop
, limit
);
1065 *evolution_of_loop
= add_to_evolution
1066 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1068 code
, rhs0
, at_stmt
);
1070 else if (res
== t_dont_know
)
1071 *evolution_of_loop
= chrec_dont_know
;
1075 /* Otherwise, match an assignment under the form:
1077 /* And there is nothing to do. */
1082 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1083 if (TREE_CODE (rhs0
) == SSA_NAME
)
1085 /* Match an assignment under the form:
1088 /* We want only assignments of form "name - name" contribute to
1089 LIMIT, as the other cases do not necessarily contribute to
1090 the complexity of the expression. */
1091 if (TREE_CODE (rhs1
) == SSA_NAME
)
1094 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1095 evolution_of_loop
, limit
);
1097 *evolution_of_loop
= add_to_evolution
1098 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1099 MINUS_EXPR
, rhs1
, at_stmt
);
1101 else if (res
== t_dont_know
)
1102 *evolution_of_loop
= chrec_dont_know
;
1105 /* Otherwise, match an assignment under the form:
1107 /* And there is nothing to do. */
1118 /* Follow the ssa edge into the expression EXPR.
1119 Return true if the strongly connected component has been found. */
1122 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1123 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1125 enum tree_code code
= TREE_CODE (expr
);
1126 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1129 /* The EXPR is one of the following cases:
1133 - a POINTER_PLUS_EXPR,
1136 - other cases are not yet handled. */
1141 /* This assignment is under the form "a_1 = (cast) rhs. */
1142 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1143 halting_phi
, evolution_of_loop
, limit
);
1144 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1148 /* This assignment is under the form "a_1 = 7". */
1153 /* This assignment is under the form: "a_1 = b_2". */
1154 res
= follow_ssa_edge
1155 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1158 case POINTER_PLUS_EXPR
:
1161 /* This case is under the form "rhs0 +- rhs1". */
1162 rhs0
= TREE_OPERAND (expr
, 0);
1163 rhs1
= TREE_OPERAND (expr
, 1);
1164 type
= TREE_TYPE (rhs0
);
1165 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1166 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1167 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1168 halting_phi
, evolution_of_loop
, limit
);
1172 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1173 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1175 expr
= TREE_OPERAND (expr
, 0);
1176 rhs0
= TREE_OPERAND (expr
, 0);
1177 rhs1
= TREE_OPERAND (expr
, 1);
1178 type
= TREE_TYPE (rhs0
);
1179 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1180 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1181 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1182 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1183 halting_phi
, evolution_of_loop
, limit
);
1190 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1191 It must be handled as a copy assignment of the form a_1 = a_2. */
1192 rhs0
= ASSERT_EXPR_VAR (expr
);
1193 if (TREE_CODE (rhs0
) == SSA_NAME
)
1194 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1195 halting_phi
, evolution_of_loop
, limit
);
1208 /* Follow the ssa edge into the right hand side of an assignment STMT.
1209 Return true if the strongly connected component has been found. */
1212 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1213 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1215 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1216 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1222 /* This assignment is under the form "a_1 = (cast) rhs. */
1223 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1224 halting_phi
, evolution_of_loop
, limit
);
1225 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1228 case POINTER_PLUS_EXPR
:
1231 rhs1
= gimple_assign_rhs1 (stmt
);
1232 rhs2
= gimple_assign_rhs2 (stmt
);
1233 type
= TREE_TYPE (rhs1
);
1234 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1235 halting_phi
, evolution_of_loop
, limit
);
1239 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1240 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1241 halting_phi
, evolution_of_loop
, limit
);
1250 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1253 backedge_phi_arg_p (gimple phi
, int i
)
1255 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1257 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1258 about updating it anywhere, and this should work as well most of the
1260 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1266 /* Helper function for one branch of the condition-phi-node. Return
1267 true if the strongly connected component has been found following
1270 static inline t_bool
1271 follow_ssa_edge_in_condition_phi_branch (int i
,
1273 gimple condition_phi
,
1275 tree
*evolution_of_branch
,
1276 tree init_cond
, int limit
)
1278 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1279 *evolution_of_branch
= chrec_dont_know
;
1281 /* Do not follow back edges (they must belong to an irreducible loop, which
1282 we really do not want to worry about). */
1283 if (backedge_phi_arg_p (condition_phi
, i
))
1286 if (TREE_CODE (branch
) == SSA_NAME
)
1288 *evolution_of_branch
= init_cond
;
1289 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1290 evolution_of_branch
, limit
);
1293 /* This case occurs when one of the condition branches sets
1294 the variable to a constant: i.e. a phi-node like
1295 "a_2 = PHI <a_7(5), 2(6)>;".
1297 FIXME: This case have to be refined correctly:
1298 in some cases it is possible to say something better than
1299 chrec_dont_know, for example using a wrap-around notation. */
1303 /* This function merges the branches of a condition-phi-node in a
1307 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1308 gimple condition_phi
,
1310 tree
*evolution_of_loop
, int limit
)
1313 tree init
= *evolution_of_loop
;
1314 tree evolution_of_branch
;
1315 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1317 &evolution_of_branch
,
1319 if (res
== t_false
|| res
== t_dont_know
)
1322 *evolution_of_loop
= evolution_of_branch
;
1324 n
= gimple_phi_num_args (condition_phi
);
1325 for (i
= 1; i
< n
; i
++)
1327 /* Quickly give up when the evolution of one of the branches is
1329 if (*evolution_of_loop
== chrec_dont_know
)
1332 /* Increase the limit by the PHI argument number to avoid exponential
1333 time and memory complexity. */
1334 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1336 &evolution_of_branch
,
1338 if (res
== t_false
|| res
== t_dont_know
)
1341 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1342 evolution_of_branch
);
1348 /* Follow an SSA edge in an inner loop. It computes the overall
1349 effect of the loop, and following the symbolic initial conditions,
1350 it follows the edges in the parent loop. The inner loop is
1351 considered as a single statement. */
1354 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1355 gimple loop_phi_node
,
1357 tree
*evolution_of_loop
, int limit
)
1359 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1360 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1362 /* Sometimes, the inner loop is too difficult to analyze, and the
1363 result of the analysis is a symbolic parameter. */
1364 if (ev
== PHI_RESULT (loop_phi_node
))
1366 t_bool res
= t_false
;
1367 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1369 for (i
= 0; i
< n
; i
++)
1371 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1374 /* Follow the edges that exit the inner loop. */
1375 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1376 if (!flow_bb_inside_loop_p (loop
, bb
))
1377 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1379 evolution_of_loop
, limit
);
1384 /* If the path crosses this loop-phi, give up. */
1386 *evolution_of_loop
= chrec_dont_know
;
1391 /* Otherwise, compute the overall effect of the inner loop. */
1392 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1393 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1394 evolution_of_loop
, limit
);
1397 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1398 path that is analyzed on the return walk. */
1401 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1402 tree
*evolution_of_loop
, int limit
)
1404 struct loop
*def_loop
;
1406 if (gimple_nop_p (def
))
1409 /* Give up if the path is longer than the MAX that we allow. */
1410 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1413 def_loop
= loop_containing_stmt (def
);
1415 switch (gimple_code (def
))
1418 if (!loop_phi_node_p (def
))
1419 /* DEF is a condition-phi-node. Follow the branches, and
1420 record their evolutions. Finally, merge the collected
1421 information and set the approximation to the main
1423 return follow_ssa_edge_in_condition_phi
1424 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1426 /* When the analyzed phi is the halting_phi, the
1427 depth-first search is over: we have found a path from
1428 the halting_phi to itself in the loop. */
1429 if (def
== halting_phi
)
1432 /* Otherwise, the evolution of the HALTING_PHI depends
1433 on the evolution of another loop-phi-node, i.e. the
1434 evolution function is a higher degree polynomial. */
1435 if (def_loop
== loop
)
1439 if (flow_loop_nested_p (loop
, def_loop
))
1440 return follow_ssa_edge_inner_loop_phi
1441 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1447 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1448 evolution_of_loop
, limit
);
1451 /* At this level of abstraction, the program is just a set
1452 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1453 other node to be handled. */
1460 /* Given a LOOP_PHI_NODE, this function determines the evolution
1461 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1464 analyze_evolution_in_loop (gimple loop_phi_node
,
1467 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1468 tree evolution_function
= chrec_not_analyzed_yet
;
1469 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1474 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1475 fprintf (dump_file
, " (loop_phi_node = ");
1476 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1477 fprintf (dump_file
, ")\n");
1480 for (i
= 0; i
< n
; i
++)
1482 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1487 /* Select the edges that enter the loop body. */
1488 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1489 if (!flow_bb_inside_loop_p (loop
, bb
))
1492 if (TREE_CODE (arg
) == SSA_NAME
)
1496 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1498 /* Pass in the initial condition to the follow edge function. */
1500 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1502 /* If ev_fn has no evolution in the inner loop, and the
1503 init_cond is not equal to ev_fn, then we have an
1504 ambiguity between two possible values, as we cannot know
1505 the number of iterations at this point. */
1506 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1507 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1508 && !operand_equal_p (init_cond
, ev_fn
, 0))
1509 ev_fn
= chrec_dont_know
;
1514 /* When it is impossible to go back on the same
1515 loop_phi_node by following the ssa edges, the
1516 evolution is represented by a peeled chrec, i.e. the
1517 first iteration, EV_FN has the value INIT_COND, then
1518 all the other iterations it has the value of ARG.
1519 For the moment, PEELED_CHREC nodes are not built. */
1521 ev_fn
= chrec_dont_know
;
1523 /* When there are multiple back edges of the loop (which in fact never
1524 happens currently, but nevertheless), merge their evolutions. */
1525 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1528 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1530 fprintf (dump_file
, " (evolution_function = ");
1531 print_generic_expr (dump_file
, evolution_function
, 0);
1532 fprintf (dump_file
, "))\n");
1535 return evolution_function
;
1538 /* Given a loop-phi-node, return the initial conditions of the
1539 variable on entry of the loop. When the CCP has propagated
1540 constants into the loop-phi-node, the initial condition is
1541 instantiated, otherwise the initial condition is kept symbolic.
1542 This analyzer does not analyze the evolution outside the current
1543 loop, and leaves this task to the on-demand tree reconstructor. */
1546 analyze_initial_condition (gimple loop_phi_node
)
1549 tree init_cond
= chrec_not_analyzed_yet
;
1550 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1554 fprintf (dump_file
, "(analyze_initial_condition \n");
1555 fprintf (dump_file
, " (loop_phi_node = \n");
1556 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1557 fprintf (dump_file
, ")\n");
1560 n
= gimple_phi_num_args (loop_phi_node
);
1561 for (i
= 0; i
< n
; i
++)
1563 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1564 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1566 /* When the branch is oriented to the loop's body, it does
1567 not contribute to the initial condition. */
1568 if (flow_bb_inside_loop_p (loop
, bb
))
1571 if (init_cond
== chrec_not_analyzed_yet
)
1577 if (TREE_CODE (branch
) == SSA_NAME
)
1579 init_cond
= chrec_dont_know
;
1583 init_cond
= chrec_merge (init_cond
, branch
);
1586 /* Ooops -- a loop without an entry??? */
1587 if (init_cond
== chrec_not_analyzed_yet
)
1588 init_cond
= chrec_dont_know
;
1590 /* During early loop unrolling we do not have fully constant propagated IL.
1591 Handle degenerate PHIs here to not miss important unrollings. */
1592 if (TREE_CODE (init_cond
) == SSA_NAME
)
1594 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1596 if (gimple_code (def
) == GIMPLE_PHI
1597 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1598 /* Only allow invariants here, otherwise we may break
1599 loop-closed SSA form. */
1600 && is_gimple_min_invariant (res
))
1604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1606 fprintf (dump_file
, " (init_cond = ");
1607 print_generic_expr (dump_file
, init_cond
, 0);
1608 fprintf (dump_file
, "))\n");
1614 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1617 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1620 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1623 if (phi_loop
!= loop
)
1625 struct loop
*subloop
;
1626 tree evolution_fn
= analyze_scalar_evolution
1627 (phi_loop
, PHI_RESULT (loop_phi_node
));
1629 /* Dive one level deeper. */
1630 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1632 /* Interpret the subloop. */
1633 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1637 /* Otherwise really interpret the loop phi. */
1638 init_cond
= analyze_initial_condition (loop_phi_node
);
1639 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1641 /* Verify we maintained the correct initial condition throughout
1642 possible conversions in the SSA chain. */
1643 if (res
!= chrec_dont_know
)
1645 tree new_init
= res
;
1646 if (CONVERT_EXPR_P (res
)
1647 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1648 new_init
= fold_convert (TREE_TYPE (res
),
1649 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1650 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1651 new_init
= CHREC_LEFT (res
);
1652 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1653 gcc_assert (TREE_CODE (new_init
) != POLYNOMIAL_CHREC
);
1654 if (!operand_equal_p (init_cond
, new_init
, 0))
1655 return chrec_dont_know
;
1661 /* This function merges the branches of a condition-phi-node,
1662 contained in the outermost loop, and whose arguments are already
1666 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1668 int i
, n
= gimple_phi_num_args (condition_phi
);
1669 tree res
= chrec_not_analyzed_yet
;
1671 for (i
= 0; i
< n
; i
++)
1675 if (backedge_phi_arg_p (condition_phi
, i
))
1677 res
= chrec_dont_know
;
1681 branch_chrec
= analyze_scalar_evolution
1682 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1684 res
= chrec_merge (res
, branch_chrec
);
1690 /* Interpret the operation RHS1 OP RHS2. If we didn't
1691 analyze this node before, follow the definitions until ending
1692 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1693 return path, this function propagates evolutions (ala constant copy
1694 propagation). OPND1 is not a GIMPLE expression because we could
1695 analyze the effect of an inner loop: see interpret_loop_phi. */
1698 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1699 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1701 tree res
, chrec1
, chrec2
;
1703 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1705 if (is_gimple_min_invariant (rhs1
))
1706 return chrec_convert (type
, rhs1
, at_stmt
);
1708 if (code
== SSA_NAME
)
1709 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1712 if (code
== ASSERT_EXPR
)
1714 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1715 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1723 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1724 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) != MEM_REF
)
1726 res
= chrec_dont_know
;
1730 rhs2
= TREE_OPERAND (TREE_OPERAND (rhs1
, 0), 1);
1731 rhs1
= TREE_OPERAND (TREE_OPERAND (rhs1
, 0), 0);
1734 case POINTER_PLUS_EXPR
:
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 (sizetype
, 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_plus (type
, chrec1
, chrec2
);
1751 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1752 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1753 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1754 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1755 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1759 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1760 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1761 /* TYPE may be integer, real or complex, so use fold_convert. */
1762 res
= chrec_fold_multiply (type
, chrec1
,
1763 fold_convert (type
, integer_minus_one_node
));
1767 /* Handle ~X as -1 - X. */
1768 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1769 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1770 res
= chrec_fold_minus (type
,
1771 fold_convert (type
, integer_minus_one_node
),
1776 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1777 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1778 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1779 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1780 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1784 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1785 res
= chrec_convert (type
, chrec1
, at_stmt
);
1789 res
= chrec_dont_know
;
1796 /* Interpret the expression EXPR. */
1799 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1801 enum tree_code code
;
1802 tree type
= TREE_TYPE (expr
), op0
, op1
;
1804 if (automatically_generated_chrec_p (expr
))
1807 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
)
1808 return chrec_dont_know
;
1810 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1812 return interpret_rhs_expr (loop
, at_stmt
, type
,
1816 /* Interpret the rhs of the assignment STMT. */
1819 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1821 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1822 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1824 return interpret_rhs_expr (loop
, stmt
, type
,
1825 gimple_assign_rhs1 (stmt
), code
,
1826 gimple_assign_rhs2 (stmt
));
1831 /* This section contains all the entry points:
1832 - number_of_iterations_in_loop,
1833 - analyze_scalar_evolution,
1834 - instantiate_parameters.
1837 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1838 common ancestor of DEF_LOOP and USE_LOOP. */
1841 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1842 struct loop
*def_loop
,
1848 if (def_loop
== wrto_loop
)
1851 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1852 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1854 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1857 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1860 /* Helper recursive function. */
1863 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1865 tree type
= TREE_TYPE (var
);
1868 struct loop
*def_loop
;
1870 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1871 return chrec_dont_know
;
1873 if (TREE_CODE (var
) != SSA_NAME
)
1874 return interpret_expr (loop
, NULL
, var
);
1876 def
= SSA_NAME_DEF_STMT (var
);
1877 bb
= gimple_bb (def
);
1878 def_loop
= bb
? bb
->loop_father
: NULL
;
1881 || !flow_bb_inside_loop_p (loop
, bb
))
1883 /* Keep the symbolic form. */
1888 if (res
!= chrec_not_analyzed_yet
)
1890 if (loop
!= bb
->loop_father
)
1891 res
= compute_scalar_evolution_in_loop
1892 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1897 if (loop
!= def_loop
)
1899 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1900 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1905 switch (gimple_code (def
))
1908 res
= interpret_gimple_assign (loop
, def
);
1912 if (loop_phi_node_p (def
))
1913 res
= interpret_loop_phi (loop
, def
);
1915 res
= interpret_condition_phi (loop
, def
);
1919 res
= chrec_dont_know
;
1925 /* Keep the symbolic form. */
1926 if (res
== chrec_dont_know
)
1929 if (loop
== def_loop
)
1930 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1935 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1936 LOOP. LOOP is the loop in which the variable is used.
1938 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1939 pointer to the statement that uses this variable, in order to
1940 determine the evolution function of the variable, use the following
1943 loop_p loop = loop_containing_stmt (stmt);
1944 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1945 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1949 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1953 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1955 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1956 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1957 fprintf (dump_file
, " (scalar = ");
1958 print_generic_expr (dump_file
, var
, 0);
1959 fprintf (dump_file
, ")\n");
1962 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1963 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1966 fprintf (dump_file
, ")\n");
1971 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1972 WRTO_LOOP (which should be a superloop of USE_LOOP)
1974 FOLDED_CASTS is set to true if resolve_mixers used
1975 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1976 at the moment in order to keep things simple).
1978 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1981 for (i = 0; i < 100; i++) -- loop 1
1983 for (j = 0; j < 100; j++) -- loop 2
1990 for (t = 0; t < 100; t++) -- loop 3
1997 Both k1 and k2 are invariants in loop3, thus
1998 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1999 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2001 As they are invariant, it does not matter whether we consider their
2002 usage in loop 3 or loop 2, hence
2003 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2004 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2005 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2006 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2008 Similarly for their evolutions with respect to loop 1. The values of K2
2009 in the use in loop 2 vary independently on loop 1, thus we cannot express
2010 the evolution with respect to loop 1:
2011 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2012 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2013 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2014 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2016 The value of k2 in the use in loop 1 is known, though:
2017 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2018 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2022 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2023 tree version
, bool *folded_casts
)
2026 tree ev
= version
, tmp
;
2028 /* We cannot just do
2030 tmp = analyze_scalar_evolution (use_loop, version);
2031 ev = resolve_mixers (wrto_loop, tmp);
2033 as resolve_mixers would query the scalar evolution with respect to
2034 wrto_loop. For example, in the situation described in the function
2035 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2038 analyze_scalar_evolution (use_loop, version) = k2
2040 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2041 is 100, which is a wrong result, since we are interested in the
2044 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2045 each time checking that there is no evolution in the inner loop. */
2048 *folded_casts
= false;
2051 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2052 ev
= resolve_mixers (use_loop
, tmp
);
2054 if (folded_casts
&& tmp
!= ev
)
2055 *folded_casts
= true;
2057 if (use_loop
== wrto_loop
)
2060 /* If the value of the use changes in the inner loop, we cannot express
2061 its value in the outer loop (we might try to return interval chrec,
2062 but we do not have a user for it anyway) */
2063 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2065 return chrec_dont_know
;
2067 use_loop
= loop_outer (use_loop
);
2071 /* Returns from CACHE the value for VERSION instantiated below
2072 INSTANTIATED_BELOW block. */
2075 get_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2078 struct scev_info_str
*info
, pattern
;
2080 pattern
.var
= version
;
2081 pattern
.instantiated_below
= instantiated_below
;
2082 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2090 /* Sets in CACHE the value of VERSION instantiated below basic block
2091 INSTANTIATED_BELOW to VAL. */
2094 set_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2095 tree version
, tree val
)
2097 struct scev_info_str
*info
, pattern
;
2100 pattern
.var
= version
;
2101 pattern
.instantiated_below
= instantiated_below
;
2102 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2105 *slot
= new_scev_info_str (instantiated_below
, version
);
2106 info
= (struct scev_info_str
*) *slot
;
2110 /* Return the closed_loop_phi node for VAR. If there is none, return
2114 loop_closed_phi_def (tree var
)
2119 gimple_stmt_iterator psi
;
2121 if (var
== NULL_TREE
2122 || TREE_CODE (var
) != SSA_NAME
)
2125 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2126 exit
= single_exit (loop
);
2130 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2132 phi
= gsi_stmt (psi
);
2133 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2134 return PHI_RESULT (phi
);
2140 static tree
instantiate_scev_r (basic_block
, struct loop
*, tree
, bool,
2143 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2144 and EVOLUTION_LOOP, that were left under a symbolic form.
2146 CHREC is an SSA_NAME to be instantiated.
2148 CACHE is the cache of already instantiated values.
2150 FOLD_CONVERSIONS should be set to true when the conversions that
2151 may wrap in signed/pointer type are folded, as long as the value of
2152 the chrec is preserved.
2154 SIZE_EXPR is used for computing the size of the expression to be
2155 instantiated, and to stop if it exceeds some limit. */
2158 instantiate_scev_name (basic_block instantiate_below
,
2159 struct loop
*evolution_loop
, tree chrec
,
2160 bool fold_conversions
, htab_t cache
, int size_expr
)
2163 struct loop
*def_loop
;
2164 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2166 /* A parameter (or loop invariant and we do not want to include
2167 evolutions in outer loops), nothing to do. */
2169 || loop_depth (def_bb
->loop_father
) == 0
2170 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2173 /* We cache the value of instantiated variable to avoid exponential
2174 time complexity due to reevaluations. We also store the convenient
2175 value in the cache in order to prevent infinite recursion -- we do
2176 not want to instantiate the SSA_NAME if it is in a mixer
2177 structure. This is used for avoiding the instantiation of
2178 recursively defined functions, such as:
2180 | a_2 -> {0, +, 1, +, a_2}_1 */
2182 res
= get_instantiated_value (cache
, instantiate_below
, chrec
);
2186 res
= chrec_dont_know
;
2187 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2189 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2191 /* If the analysis yields a parametric chrec, instantiate the
2193 res
= analyze_scalar_evolution (def_loop
, chrec
);
2195 /* Don't instantiate default definitions. */
2196 if (TREE_CODE (res
) == SSA_NAME
2197 && SSA_NAME_IS_DEFAULT_DEF (res
))
2200 /* Don't instantiate loop-closed-ssa phi nodes. */
2201 else if (TREE_CODE (res
) == SSA_NAME
2202 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2203 > loop_depth (def_loop
))
2206 res
= loop_closed_phi_def (chrec
);
2210 /* When there is no loop_closed_phi_def, it means that the
2211 variable is not used after the loop: try to still compute the
2212 value of the variable when exiting the loop. */
2213 if (res
== NULL_TREE
)
2215 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2216 res
= analyze_scalar_evolution (loop
, chrec
);
2217 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2218 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2219 fold_conversions
, cache
, size_expr
);
2221 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2222 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2223 res
= chrec_dont_know
;
2226 else if (res
!= chrec_dont_know
)
2227 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2228 fold_conversions
, cache
, size_expr
);
2230 /* Store the correct value to the cache. */
2231 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2235 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2236 and EVOLUTION_LOOP, that were left under a symbolic form.
2238 CHREC is a polynomial chain of recurrence to be instantiated.
2240 CACHE is the cache of already instantiated values.
2242 FOLD_CONVERSIONS should be set to true when the conversions that
2243 may wrap in signed/pointer type are folded, as long as the value of
2244 the chrec is preserved.
2246 SIZE_EXPR is used for computing the size of the expression to be
2247 instantiated, and to stop if it exceeds some limit. */
2250 instantiate_scev_poly (basic_block instantiate_below
,
2251 struct loop
*evolution_loop
, tree chrec
,
2252 bool fold_conversions
, htab_t cache
, int size_expr
)
2255 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2256 CHREC_LEFT (chrec
), fold_conversions
, cache
,
2258 if (op0
== chrec_dont_know
)
2259 return chrec_dont_know
;
2261 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2262 CHREC_RIGHT (chrec
), fold_conversions
, cache
,
2264 if (op1
== chrec_dont_know
)
2265 return chrec_dont_know
;
2267 if (CHREC_LEFT (chrec
) != op0
2268 || CHREC_RIGHT (chrec
) != op1
)
2270 unsigned var
= CHREC_VARIABLE (chrec
);
2272 /* When the instantiated stride or base has an evolution in an
2273 innermost loop, return chrec_dont_know, as this is not a
2274 valid SCEV representation. In the reduced testcase for
2275 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2277 if ((tree_is_chrec (op0
) && CHREC_VARIABLE (op0
) > var
)
2278 || (tree_is_chrec (op1
) && CHREC_VARIABLE (op1
) > var
))
2279 return chrec_dont_know
;
2281 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2282 chrec
= build_polynomial_chrec (var
, op0
, op1
);
2288 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2289 and EVOLUTION_LOOP, that were left under a symbolic form.
2291 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2293 CACHE is the cache of already instantiated values.
2295 FOLD_CONVERSIONS should be set to true when the conversions that
2296 may wrap in signed/pointer type are folded, as long as the value of
2297 the chrec is preserved.
2299 SIZE_EXPR is used for computing the size of the expression to be
2300 instantiated, and to stop if it exceeds some limit. */
2303 instantiate_scev_binary (basic_block instantiate_below
,
2304 struct loop
*evolution_loop
, tree chrec
, enum tree_code code
,
2305 tree type
, tree c0
, tree c1
,
2306 bool fold_conversions
, htab_t cache
, int size_expr
)
2309 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2310 c0
, fold_conversions
, cache
,
2312 if (op0
== chrec_dont_know
)
2313 return chrec_dont_know
;
2315 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2316 c1
, fold_conversions
, cache
,
2318 if (op1
== chrec_dont_know
)
2319 return chrec_dont_know
;
2324 op0
= chrec_convert (type
, op0
, NULL
);
2325 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2329 case POINTER_PLUS_EXPR
:
2331 return chrec_fold_plus (type
, op0
, op1
);
2334 return chrec_fold_minus (type
, op0
, op1
);
2337 return chrec_fold_multiply (type
, op0
, op1
);
2344 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2347 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2348 and EVOLUTION_LOOP, that were left under a symbolic form.
2350 "CHREC" is an array reference to be instantiated.
2352 CACHE is the cache of already instantiated values.
2354 FOLD_CONVERSIONS should be set to true when the conversions that
2355 may wrap in signed/pointer type are folded, as long as the value of
2356 the chrec is preserved.
2358 SIZE_EXPR is used for computing the size of the expression to be
2359 instantiated, and to stop if it exceeds some limit. */
2362 instantiate_array_ref (basic_block instantiate_below
,
2363 struct loop
*evolution_loop
, tree chrec
,
2364 bool fold_conversions
, htab_t cache
, int size_expr
)
2367 tree index
= TREE_OPERAND (chrec
, 1);
2368 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, index
,
2369 fold_conversions
, cache
, size_expr
);
2371 if (op1
== chrec_dont_know
)
2372 return chrec_dont_know
;
2374 if (chrec
&& op1
== index
)
2377 res
= unshare_expr (chrec
);
2378 TREE_OPERAND (res
, 1) = op1
;
2382 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2383 and EVOLUTION_LOOP, that were left under a symbolic form.
2385 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2388 CACHE is the cache of already instantiated values.
2390 FOLD_CONVERSIONS should be set to true when the conversions that
2391 may wrap in signed/pointer type are folded, as long as the value of
2392 the chrec is preserved.
2394 SIZE_EXPR is used for computing the size of the expression to be
2395 instantiated, and to stop if it exceeds some limit. */
2398 instantiate_scev_convert (basic_block instantiate_below
,
2399 struct loop
*evolution_loop
, tree chrec
,
2401 bool fold_conversions
, htab_t cache
, int size_expr
)
2403 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2404 fold_conversions
, cache
, size_expr
);
2406 if (op0
== chrec_dont_know
)
2407 return chrec_dont_know
;
2409 if (fold_conversions
)
2411 tree tmp
= chrec_convert_aggressive (type
, op0
);
2416 if (chrec
&& op0
== op
)
2419 /* If we used chrec_convert_aggressive, we can no longer assume that
2420 signed chrecs do not overflow, as chrec_convert does, so avoid
2421 calling it in that case. */
2422 if (fold_conversions
)
2423 return fold_convert (type
, op0
);
2425 return chrec_convert (type
, op0
, NULL
);
2428 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2429 and EVOLUTION_LOOP, that were left under a symbolic form.
2431 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2432 Handle ~X as -1 - X.
2433 Handle -X as -1 * X.
2435 CACHE is the cache of already instantiated values.
2437 FOLD_CONVERSIONS should be set to true when the conversions that
2438 may wrap in signed/pointer type are folded, as long as the value of
2439 the chrec is preserved.
2441 SIZE_EXPR is used for computing the size of the expression to be
2442 instantiated, and to stop if it exceeds some limit. */
2445 instantiate_scev_not (basic_block instantiate_below
,
2446 struct loop
*evolution_loop
, tree chrec
,
2447 enum tree_code code
, tree type
, tree op
,
2448 bool fold_conversions
, htab_t cache
, int size_expr
)
2450 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2451 fold_conversions
, cache
, size_expr
);
2453 if (op0
== chrec_dont_know
)
2454 return chrec_dont_know
;
2458 op0
= chrec_convert (type
, op0
, NULL
);
2463 return chrec_fold_minus
2464 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2467 return chrec_fold_multiply
2468 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2475 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2478 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2479 and EVOLUTION_LOOP, that were left under a symbolic form.
2481 CHREC is an expression with 3 operands to be instantiated.
2483 CACHE is the cache of already instantiated values.
2485 FOLD_CONVERSIONS should be set to true when the conversions that
2486 may wrap in signed/pointer type are folded, as long as the value of
2487 the chrec is preserved.
2489 SIZE_EXPR is used for computing the size of the expression to be
2490 instantiated, and to stop if it exceeds some limit. */
2493 instantiate_scev_3 (basic_block instantiate_below
,
2494 struct loop
*evolution_loop
, tree chrec
,
2495 bool fold_conversions
, htab_t cache
, int size_expr
)
2498 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2499 TREE_OPERAND (chrec
, 0),
2500 fold_conversions
, cache
, size_expr
);
2501 if (op0
== chrec_dont_know
)
2502 return chrec_dont_know
;
2504 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2505 TREE_OPERAND (chrec
, 1),
2506 fold_conversions
, cache
, size_expr
);
2507 if (op1
== chrec_dont_know
)
2508 return chrec_dont_know
;
2510 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2511 TREE_OPERAND (chrec
, 2),
2512 fold_conversions
, cache
, size_expr
);
2513 if (op2
== chrec_dont_know
)
2514 return chrec_dont_know
;
2516 if (op0
== TREE_OPERAND (chrec
, 0)
2517 && op1
== TREE_OPERAND (chrec
, 1)
2518 && op2
== TREE_OPERAND (chrec
, 2))
2521 return fold_build3 (TREE_CODE (chrec
),
2522 TREE_TYPE (chrec
), op0
, op1
, op2
);
2525 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2526 and EVOLUTION_LOOP, that were left under a symbolic form.
2528 CHREC is an expression with 2 operands to be instantiated.
2530 CACHE is the cache of already instantiated values.
2532 FOLD_CONVERSIONS should be set to true when the conversions that
2533 may wrap in signed/pointer type are folded, as long as the value of
2534 the chrec is preserved.
2536 SIZE_EXPR is used for computing the size of the expression to be
2537 instantiated, and to stop if it exceeds some limit. */
2540 instantiate_scev_2 (basic_block instantiate_below
,
2541 struct loop
*evolution_loop
, tree chrec
,
2542 bool fold_conversions
, htab_t cache
, int size_expr
)
2545 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2546 TREE_OPERAND (chrec
, 0),
2547 fold_conversions
, cache
, size_expr
);
2548 if (op0
== chrec_dont_know
)
2549 return chrec_dont_know
;
2551 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2552 TREE_OPERAND (chrec
, 1),
2553 fold_conversions
, cache
, size_expr
);
2554 if (op1
== chrec_dont_know
)
2555 return chrec_dont_know
;
2557 if (op0
== TREE_OPERAND (chrec
, 0)
2558 && op1
== TREE_OPERAND (chrec
, 1))
2561 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2564 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2565 and EVOLUTION_LOOP, that were left under a symbolic form.
2567 CHREC is an expression with 2 operands to be instantiated.
2569 CACHE is the cache of already instantiated values.
2571 FOLD_CONVERSIONS should be set to true when the conversions that
2572 may wrap in signed/pointer type are folded, as long as the value of
2573 the chrec is preserved.
2575 SIZE_EXPR is used for computing the size of the expression to be
2576 instantiated, and to stop if it exceeds some limit. */
2579 instantiate_scev_1 (basic_block instantiate_below
,
2580 struct loop
*evolution_loop
, tree chrec
,
2581 bool fold_conversions
, htab_t cache
, int size_expr
)
2583 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2584 TREE_OPERAND (chrec
, 0),
2585 fold_conversions
, cache
, size_expr
);
2587 if (op0
== chrec_dont_know
)
2588 return chrec_dont_know
;
2590 if (op0
== TREE_OPERAND (chrec
, 0))
2593 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2596 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2597 and EVOLUTION_LOOP, that were left under a symbolic form.
2599 CHREC is the scalar evolution to instantiate.
2601 CACHE is the cache of already instantiated values.
2603 FOLD_CONVERSIONS should be set to true when the conversions that
2604 may wrap in signed/pointer type are folded, as long as the value of
2605 the chrec is preserved.
2607 SIZE_EXPR is used for computing the size of the expression to be
2608 instantiated, and to stop if it exceeds some limit. */
2611 instantiate_scev_r (basic_block instantiate_below
,
2612 struct loop
*evolution_loop
, tree chrec
,
2613 bool fold_conversions
, htab_t cache
, int size_expr
)
2615 /* Give up if the expression is larger than the MAX that we allow. */
2616 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2617 return chrec_dont_know
;
2619 if (automatically_generated_chrec_p (chrec
)
2620 || is_gimple_min_invariant (chrec
))
2623 switch (TREE_CODE (chrec
))
2626 return instantiate_scev_name (instantiate_below
, evolution_loop
, chrec
,
2627 fold_conversions
, cache
, size_expr
);
2629 case POLYNOMIAL_CHREC
:
2630 return instantiate_scev_poly (instantiate_below
, evolution_loop
, chrec
,
2631 fold_conversions
, cache
, size_expr
);
2633 case POINTER_PLUS_EXPR
:
2637 return instantiate_scev_binary (instantiate_below
, evolution_loop
, chrec
,
2638 TREE_CODE (chrec
), chrec_type (chrec
),
2639 TREE_OPERAND (chrec
, 0),
2640 TREE_OPERAND (chrec
, 1),
2641 fold_conversions
, cache
, size_expr
);
2644 return instantiate_scev_convert (instantiate_below
, evolution_loop
, chrec
,
2645 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2646 fold_conversions
, cache
, size_expr
);
2650 return instantiate_scev_not (instantiate_below
, evolution_loop
, chrec
,
2651 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2652 TREE_OPERAND (chrec
, 0),
2653 fold_conversions
, cache
, size_expr
);
2655 case SCEV_NOT_KNOWN
:
2656 return chrec_dont_know
;
2662 return instantiate_array_ref (instantiate_below
, evolution_loop
, chrec
,
2663 fold_conversions
, cache
, size_expr
);
2669 if (VL_EXP_CLASS_P (chrec
))
2670 return chrec_dont_know
;
2672 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2675 return instantiate_scev_3 (instantiate_below
, evolution_loop
, chrec
,
2676 fold_conversions
, cache
, size_expr
);
2679 return instantiate_scev_2 (instantiate_below
, evolution_loop
, chrec
,
2680 fold_conversions
, cache
, size_expr
);
2683 return instantiate_scev_1 (instantiate_below
, evolution_loop
, chrec
,
2684 fold_conversions
, cache
, size_expr
);
2693 /* Too complicated to handle. */
2694 return chrec_dont_know
;
2697 /* Analyze all the parameters of the chrec that were left under a
2698 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2699 recursive instantiation of parameters: a parameter is a variable
2700 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2701 a function parameter. */
2704 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2708 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2712 fprintf (dump_file
, "(instantiate_scev \n");
2713 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2714 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2715 fprintf (dump_file
, " (chrec = ");
2716 print_generic_expr (dump_file
, chrec
, 0);
2717 fprintf (dump_file
, ")\n");
2720 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, chrec
, false,
2723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2725 fprintf (dump_file
, " (res = ");
2726 print_generic_expr (dump_file
, res
, 0);
2727 fprintf (dump_file
, "))\n");
2730 htab_delete (cache
);
2735 /* Similar to instantiate_parameters, but does not introduce the
2736 evolutions in outer loops for LOOP invariants in CHREC, and does not
2737 care about causing overflows, as long as they do not affect value
2738 of an expression. */
2741 resolve_mixers (struct loop
*loop
, tree chrec
)
2743 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2744 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, chrec
, true,
2746 htab_delete (cache
);
2750 /* Entry point for the analysis of the number of iterations pass.
2751 This function tries to safely approximate the number of iterations
2752 the loop will run. When this property is not decidable at compile
2753 time, the result is chrec_dont_know. Otherwise the result is a
2754 scalar or a symbolic parameter. When the number of iterations may
2755 be equal to zero and the property cannot be determined at compile
2756 time, the result is a COND_EXPR that represents in a symbolic form
2757 the conditions under which the number of iterations is not zero.
2759 Example of analysis: suppose that the loop has an exit condition:
2761 "if (b > 49) goto end_loop;"
2763 and that in a previous analysis we have determined that the
2764 variable 'b' has an evolution function:
2766 "EF = {23, +, 5}_2".
2768 When we evaluate the function at the point 5, i.e. the value of the
2769 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2770 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2771 the loop body has been executed 6 times. */
2774 number_of_latch_executions (struct loop
*loop
)
2777 struct tree_niter_desc niter_desc
;
2781 /* Determine whether the number of iterations in loop has already
2783 res
= loop
->nb_iterations
;
2787 may_be_zero
= NULL_TREE
;
2789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2790 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2792 res
= chrec_dont_know
;
2793 exit
= single_exit (loop
);
2795 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2797 may_be_zero
= niter_desc
.may_be_zero
;
2798 res
= niter_desc
.niter
;
2801 if (res
== chrec_dont_know
2803 || integer_zerop (may_be_zero
))
2805 else if (integer_nonzerop (may_be_zero
))
2806 res
= build_int_cst (TREE_TYPE (res
), 0);
2808 else if (COMPARISON_CLASS_P (may_be_zero
))
2809 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2810 build_int_cst (TREE_TYPE (res
), 0), res
);
2812 res
= chrec_dont_know
;
2814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2816 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2817 print_generic_expr (dump_file
, res
, 0);
2818 fprintf (dump_file
, "))\n");
2821 loop
->nb_iterations
= res
;
2825 /* Returns the number of executions of the exit condition of LOOP,
2826 i.e., the number by one higher than number_of_latch_executions.
2827 Note that unlike number_of_latch_executions, this number does
2828 not necessarily fit in the unsigned variant of the type of
2829 the control variable -- if the number of iterations is a constant,
2830 we return chrec_dont_know if adding one to number_of_latch_executions
2831 overflows; however, in case the number of iterations is symbolic
2832 expression, the caller is responsible for dealing with this
2833 the possible overflow. */
2836 number_of_exit_cond_executions (struct loop
*loop
)
2838 tree ret
= number_of_latch_executions (loop
);
2839 tree type
= chrec_type (ret
);
2841 if (chrec_contains_undetermined (ret
))
2844 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2845 if (TREE_CODE (ret
) == INTEGER_CST
2846 && TREE_OVERFLOW (ret
))
2847 return chrec_dont_know
;
2852 /* One of the drivers for testing the scalar evolutions analysis.
2853 This function computes the number of iterations for all the loops
2854 from the EXIT_CONDITIONS array. */
2857 number_of_iterations_for_all_loops (VEC(gimple
,heap
) **exit_conditions
)
2860 unsigned nb_chrec_dont_know_loops
= 0;
2861 unsigned nb_static_loops
= 0;
2864 FOR_EACH_VEC_ELT (gimple
, *exit_conditions
, i
, cond
)
2866 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2867 if (chrec_contains_undetermined (res
))
2868 nb_chrec_dont_know_loops
++;
2875 fprintf (dump_file
, "\n(\n");
2876 fprintf (dump_file
, "-----------------------------------------\n");
2877 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2878 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2879 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2880 fprintf (dump_file
, "-----------------------------------------\n");
2881 fprintf (dump_file
, ")\n\n");
2883 print_loops (dump_file
, 3);
2889 /* Counters for the stats. */
2895 unsigned nb_affine_multivar
;
2896 unsigned nb_higher_poly
;
2897 unsigned nb_chrec_dont_know
;
2898 unsigned nb_undetermined
;
2901 /* Reset the counters. */
2904 reset_chrecs_counters (struct chrec_stats
*stats
)
2906 stats
->nb_chrecs
= 0;
2907 stats
->nb_affine
= 0;
2908 stats
->nb_affine_multivar
= 0;
2909 stats
->nb_higher_poly
= 0;
2910 stats
->nb_chrec_dont_know
= 0;
2911 stats
->nb_undetermined
= 0;
2914 /* Dump the contents of a CHREC_STATS structure. */
2917 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2919 fprintf (file
, "\n(\n");
2920 fprintf (file
, "-----------------------------------------\n");
2921 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2922 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2923 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2924 stats
->nb_higher_poly
);
2925 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2926 fprintf (file
, "-----------------------------------------\n");
2927 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2928 fprintf (file
, "%d\twith undetermined coefficients\n",
2929 stats
->nb_undetermined
);
2930 fprintf (file
, "-----------------------------------------\n");
2931 fprintf (file
, "%d\tchrecs in the scev database\n",
2932 (int) htab_elements (scalar_evolution_info
));
2933 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2934 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2935 fprintf (file
, "-----------------------------------------\n");
2936 fprintf (file
, ")\n\n");
2939 /* Gather statistics about CHREC. */
2942 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2944 if (dump_file
&& (dump_flags
& TDF_STATS
))
2946 fprintf (dump_file
, "(classify_chrec ");
2947 print_generic_expr (dump_file
, chrec
, 0);
2948 fprintf (dump_file
, "\n");
2953 if (chrec
== NULL_TREE
)
2955 stats
->nb_undetermined
++;
2959 switch (TREE_CODE (chrec
))
2961 case POLYNOMIAL_CHREC
:
2962 if (evolution_function_is_affine_p (chrec
))
2964 if (dump_file
&& (dump_flags
& TDF_STATS
))
2965 fprintf (dump_file
, " affine_univariate\n");
2968 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2970 if (dump_file
&& (dump_flags
& TDF_STATS
))
2971 fprintf (dump_file
, " affine_multivariate\n");
2972 stats
->nb_affine_multivar
++;
2976 if (dump_file
&& (dump_flags
& TDF_STATS
))
2977 fprintf (dump_file
, " higher_degree_polynomial\n");
2978 stats
->nb_higher_poly
++;
2987 if (chrec_contains_undetermined (chrec
))
2989 if (dump_file
&& (dump_flags
& TDF_STATS
))
2990 fprintf (dump_file
, " undetermined\n");
2991 stats
->nb_undetermined
++;
2994 if (dump_file
&& (dump_flags
& TDF_STATS
))
2995 fprintf (dump_file
, ")\n");
2998 /* One of the drivers for testing the scalar evolutions analysis.
2999 This function analyzes the scalar evolution of all the scalars
3000 defined as loop phi nodes in one of the loops from the
3001 EXIT_CONDITIONS array.
3003 TODO Optimization: A loop is in canonical form if it contains only
3004 a single scalar loop phi node. All the other scalars that have an
3005 evolution in the loop are rewritten in function of this single
3006 index. This allows the parallelization of the loop. */
3009 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple
,heap
) **exit_conditions
)
3012 struct chrec_stats stats
;
3014 gimple_stmt_iterator psi
;
3016 reset_chrecs_counters (&stats
);
3018 FOR_EACH_VEC_ELT (gimple
, *exit_conditions
, i
, cond
)
3024 loop
= loop_containing_stmt (cond
);
3027 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3029 phi
= gsi_stmt (psi
);
3030 if (is_gimple_reg (PHI_RESULT (phi
)))
3032 chrec
= instantiate_parameters
3034 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
3036 if (dump_file
&& (dump_flags
& TDF_STATS
))
3037 gather_chrec_stats (chrec
, &stats
);
3042 if (dump_file
&& (dump_flags
& TDF_STATS
))
3043 dump_chrecs_stats (dump_file
, &stats
);
3046 /* Callback for htab_traverse, gathers information on chrecs in the
3050 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
3052 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
3054 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3059 /* Classify the chrecs of the whole database. */
3062 gather_stats_on_scev_database (void)
3064 struct chrec_stats stats
;
3069 reset_chrecs_counters (&stats
);
3071 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3074 dump_chrecs_stats (dump_file
, &stats
);
3082 initialize_scalar_evolutions_analyzer (void)
3084 /* The elements below are unique. */
3085 if (chrec_dont_know
== NULL_TREE
)
3087 chrec_not_analyzed_yet
= NULL_TREE
;
3088 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3089 chrec_known
= make_node (SCEV_KNOWN
);
3090 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3091 TREE_TYPE (chrec_known
) = void_type_node
;
3095 /* Initialize the analysis of scalar evolutions for LOOPS. */
3098 scev_initialize (void)
3104 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3107 initialize_scalar_evolutions_analyzer ();
3109 FOR_EACH_LOOP (li
, loop
, 0)
3111 loop
->nb_iterations
= NULL_TREE
;
3115 /* Cleans up the information cached by the scalar evolutions analysis
3116 in the hash table. */
3119 scev_reset_htab (void)
3121 if (!scalar_evolution_info
)
3124 htab_empty (scalar_evolution_info
);
3127 /* Cleans up the information cached by the scalar evolutions analysis
3128 in the hash table and in the loop->nb_iterations. */
3141 FOR_EACH_LOOP (li
, loop
, 0)
3143 loop
->nb_iterations
= NULL_TREE
;
3147 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3148 respect to WRTO_LOOP and returns its base and step in IV if possible
3149 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3150 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3151 invariant in LOOP. Otherwise we require it to be an integer constant.
3153 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3154 because it is computed in signed arithmetics). Consequently, adding an
3157 for (i = IV->base; ; i += IV->step)
3159 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3160 false for the type of the induction variable, or you can prove that i does
3161 not wrap by some other argument. Otherwise, this might introduce undefined
3164 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3166 must be used instead. */
3169 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3170 affine_iv
*iv
, bool allow_nonconstant_step
)
3175 iv
->base
= NULL_TREE
;
3176 iv
->step
= NULL_TREE
;
3177 iv
->no_overflow
= false;
3179 type
= TREE_TYPE (op
);
3180 if (TREE_CODE (type
) != INTEGER_TYPE
3181 && TREE_CODE (type
) != POINTER_TYPE
)
3184 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3186 if (chrec_contains_undetermined (ev
)
3187 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3190 if (tree_does_not_contain_chrecs (ev
))
3193 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3194 iv
->no_overflow
= true;
3198 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3199 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3202 iv
->step
= CHREC_RIGHT (ev
);
3203 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3204 || tree_contains_chrecs (iv
->step
, NULL
))
3207 iv
->base
= CHREC_LEFT (ev
);
3208 if (tree_contains_chrecs (iv
->base
, NULL
))
3211 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3216 /* Runs the analysis of scalar evolutions. */
3219 scev_analysis (void)
3221 VEC(gimple
,heap
) *exit_conditions
;
3223 exit_conditions
= VEC_alloc (gimple
, heap
, 37);
3224 select_loops_exit_conditions (&exit_conditions
);
3226 if (dump_file
&& (dump_flags
& TDF_STATS
))
3227 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
3229 number_of_iterations_for_all_loops (&exit_conditions
);
3230 VEC_free (gimple
, heap
, exit_conditions
);
3233 /* Finalize the scalar evolution analysis. */
3236 scev_finalize (void)
3238 if (!scalar_evolution_info
)
3240 htab_delete (scalar_evolution_info
);
3241 scalar_evolution_info
= NULL
;
3244 /* Returns true if the expression EXPR is considered to be too expensive
3245 for scev_const_prop. */
3248 expression_expensive_p (tree expr
)
3250 enum tree_code code
;
3252 if (is_gimple_val (expr
))
3255 code
= TREE_CODE (expr
);
3256 if (code
== TRUNC_DIV_EXPR
3257 || code
== CEIL_DIV_EXPR
3258 || code
== FLOOR_DIV_EXPR
3259 || code
== ROUND_DIV_EXPR
3260 || code
== TRUNC_MOD_EXPR
3261 || code
== CEIL_MOD_EXPR
3262 || code
== FLOOR_MOD_EXPR
3263 || code
== ROUND_MOD_EXPR
3264 || code
== EXACT_DIV_EXPR
)
3266 /* Division by power of two is usually cheap, so we allow it.
3267 Forbid anything else. */
3268 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3272 switch (TREE_CODE_CLASS (code
))
3275 case tcc_comparison
:
3276 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3281 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3288 /* Replace ssa names for that scev can prove they are constant by the
3289 appropriate constants. Also perform final value replacement in loops,
3290 in case the replacement expressions are cheap.
3292 We only consider SSA names defined by phi nodes; rest is left to the
3293 ordinary constant propagation pass. */
3296 scev_const_prop (void)
3299 tree name
, type
, ev
;
3301 struct loop
*loop
, *ex_loop
;
3302 bitmap ssa_names_to_remove
= NULL
;
3305 gimple_stmt_iterator psi
;
3307 if (number_of_loops () <= 1)
3312 loop
= bb
->loop_father
;
3314 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3316 phi
= gsi_stmt (psi
);
3317 name
= PHI_RESULT (phi
);
3319 if (!is_gimple_reg (name
))
3322 type
= TREE_TYPE (name
);
3324 if (!POINTER_TYPE_P (type
)
3325 && !INTEGRAL_TYPE_P (type
))
3328 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3329 if (!is_gimple_min_invariant (ev
)
3330 || !may_propagate_copy (name
, ev
))
3333 /* Replace the uses of the name. */
3335 replace_uses_by (name
, ev
);
3337 if (!ssa_names_to_remove
)
3338 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3339 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3343 /* Remove the ssa names that were replaced by constants. We do not
3344 remove them directly in the previous cycle, since this
3345 invalidates scev cache. */
3346 if (ssa_names_to_remove
)
3350 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3352 gimple_stmt_iterator psi
;
3353 name
= ssa_name (i
);
3354 phi
= SSA_NAME_DEF_STMT (name
);
3356 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3357 psi
= gsi_for_stmt (phi
);
3358 remove_phi_node (&psi
, true);
3361 BITMAP_FREE (ssa_names_to_remove
);
3365 /* Now the regular final value replacement. */
3366 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3369 tree def
, rslt
, niter
;
3370 gimple_stmt_iterator bsi
;
3372 /* If we do not know exact number of iterations of the loop, we cannot
3373 replace the final value. */
3374 exit
= single_exit (loop
);
3378 niter
= number_of_latch_executions (loop
);
3379 if (niter
== chrec_dont_know
)
3382 /* Ensure that it is possible to insert new statements somewhere. */
3383 if (!single_pred_p (exit
->dest
))
3384 split_loop_exit_edge (exit
);
3385 bsi
= gsi_after_labels (exit
->dest
);
3387 ex_loop
= superloop_at_depth (loop
,
3388 loop_depth (exit
->dest
->loop_father
) + 1);
3390 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3392 phi
= gsi_stmt (psi
);
3393 rslt
= PHI_RESULT (phi
);
3394 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3395 if (!is_gimple_reg (def
))
3401 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3402 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3408 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3409 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3410 if (!tree_does_not_contain_chrecs (def
)
3411 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3412 /* Moving the computation from the loop may prolong life range
3413 of some ssa names, which may cause problems if they appear
3414 on abnormal edges. */
3415 || contains_abnormal_ssa_name_p (def
)
3416 /* Do not emit expensive expressions. The rationale is that
3417 when someone writes a code like
3419 while (n > 45) n -= 45;
3421 he probably knows that n is not large, and does not want it
3422 to be turned into n %= 45. */
3423 || expression_expensive_p (def
))
3429 /* Eliminate the PHI node and replace it by a computation outside
3431 def
= unshare_expr (def
);
3432 remove_phi_node (&psi
, false);
3434 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3435 true, GSI_SAME_STMT
);
3436 ass
= gimple_build_assign (rslt
, def
);
3437 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3443 #include "gt-tree-scalar-evolution.h"