1 /* Scalar evolution detector.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
50 - When the definition is a GIMPLE_ASSIGN: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
75 Example 1: Illustration of the basic algorithm.
81 | if (c > 10) exit_loop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
119 or in terms of a C program:
122 | for (x = 0; x <= 7; x++)
128 Example 2a: Illustration of the algorithm on nested loops.
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
157 Example 2b: Multivariate chains of recurrences.
170 Analyzing the access function of array A with
171 instantiate_parameters (loop_1, "j + k"), we obtain the
172 instantiation and the analysis of the scalar variables "j" and "k"
173 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175 {0, +, 1}_1. To obtain the evolution function in loop_3 and
176 instantiate the scalar variables up to loop_1, one has to use:
177 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178 The result of this call is {{0, +, 1}_1, +, 1}_2.
180 Example 3: Higher degree polynomials.
194 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197 Example 4: Lucas, Fibonacci, or mixers in general.
209 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210 following semantics: during the first iteration of the loop_1, the
211 variable contains the value 1, and then it contains the value "c".
212 Note that this syntax is close to the syntax of the loop-phi-node:
213 "a -> (1, c)_1" vs. "a = phi (1, c)".
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
218 Example 5: Flip-flops, or exchangers.
230 Based on these symbolic chrecs, it is possible to refine this
231 information into the more precise PERIODIC_CHRECs:
236 This transformation is not yet implemented.
240 You can find a more detailed description of the algorithm in:
241 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243 this is a preliminary report and some of the details of the
244 algorithm have changed. I'm working on a research report that
245 updates the description of the algorithms to reflect the design
246 choices used in this implementation.
248 A set of slides show a high level overview of the algorithm and run
249 an example through the scalar evolution analyzer:
250 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252 The slides that I have presented at the GCC Summit'04 are available
253 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
258 #include "coretypes.h"
260 #include "hash-table.h"
261 #include "gimple-pretty-print.h"
262 #include "gimplify.h"
263 #include "gimple-ssa.h"
264 #include "tree-cfg.h"
265 #include "tree-phinodes.h"
266 #include "tree-ssanames.h"
267 #include "tree-ssa-loop-ivopts.h"
268 #include "tree-ssa-loop-manip.h"
269 #include "tree-ssa-loop-niter.h"
270 #include "tree-ssa-loop.h"
271 #include "tree-ssa.h"
273 #include "tree-chrec.h"
274 #include "tree-scalar-evolution.h"
275 #include "dumpfile.h"
277 #include "tree-ssa-propagate.h"
279 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
280 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
283 /* The cached information about an SSA name with version NAME_VERSION,
284 claiming that below basic block with index INSTANTIATED_BELOW, the
285 value of the SSA name can be expressed as CHREC. */
287 struct GTY(()) scev_info_str
{
288 unsigned int name_version
;
289 int instantiated_below
;
293 /* Counters for the scev database. */
294 static unsigned nb_set_scev
= 0;
295 static unsigned nb_get_scev
= 0;
297 /* The following trees are unique elements. Thus the comparison of
298 another element to these elements should be done on the pointer to
299 these trees, and not on their value. */
301 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
302 tree chrec_not_analyzed_yet
;
304 /* Reserved to the cases where the analyzer has detected an
305 undecidable property at compile time. */
306 tree chrec_dont_know
;
308 /* When the analyzer has detected that a property will never
309 happen, then it qualifies it with chrec_known. */
312 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
315 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
317 static inline struct scev_info_str
*
318 new_scev_info_str (basic_block instantiated_below
, tree var
)
320 struct scev_info_str
*res
;
322 res
= ggc_alloc_scev_info_str ();
323 res
->name_version
= SSA_NAME_VERSION (var
);
324 res
->chrec
= chrec_not_analyzed_yet
;
325 res
->instantiated_below
= instantiated_below
->index
;
330 /* Computes a hash function for database element ELT. */
332 static inline hashval_t
333 hash_scev_info (const void *elt_
)
335 const struct scev_info_str
*elt
= (const struct scev_info_str
*) elt_
;
336 return elt
->name_version
^ elt
->instantiated_below
;
339 /* Compares database elements E1 and E2. */
342 eq_scev_info (const void *e1
, const void *e2
)
344 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
345 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
347 return (elt1
->name_version
== elt2
->name_version
348 && elt1
->instantiated_below
== elt2
->instantiated_below
);
351 /* Deletes database element E. */
354 del_scev_info (void *e
)
360 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
361 A first query on VAR returns chrec_not_analyzed_yet. */
364 find_var_scev_info (basic_block instantiated_below
, tree var
)
366 struct scev_info_str
*res
;
367 struct scev_info_str tmp
;
370 tmp
.name_version
= SSA_NAME_VERSION (var
);
371 tmp
.instantiated_below
= instantiated_below
->index
;
372 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
375 *slot
= new_scev_info_str (instantiated_below
, var
);
376 res
= (struct scev_info_str
*) *slot
;
381 /* Return true when CHREC contains symbolic names defined in
385 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
389 if (chrec
== NULL_TREE
)
392 if (is_gimple_min_invariant (chrec
))
395 if (TREE_CODE (chrec
) == SSA_NAME
)
398 loop_p def_loop
, loop
;
400 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
403 def
= SSA_NAME_DEF_STMT (chrec
);
404 def_loop
= loop_containing_stmt (def
);
405 loop
= get_loop (cfun
, loop_nb
);
407 if (def_loop
== NULL
)
410 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
416 n
= TREE_OPERAND_LENGTH (chrec
);
417 for (i
= 0; i
< n
; i
++)
418 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
424 /* Return true when PHI is a loop-phi-node. */
427 loop_phi_node_p (gimple phi
)
429 /* The implementation of this function is based on the following
430 property: "all the loop-phi-nodes of a loop are contained in the
431 loop's header basic block". */
433 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
436 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
437 In general, in the case of multivariate evolutions we want to get
438 the evolution in different loops. LOOP specifies the level for
439 which to get the evolution.
443 | for (j = 0; j < 100; j++)
445 | for (k = 0; k < 100; k++)
447 | i = k + j; - Here the value of i is a function of j, k.
449 | ... = i - Here the value of i is a function of j.
451 | ... = i - Here the value of i is a scalar.
457 | i_1 = phi (i_0, i_2)
461 This loop has the same effect as:
462 LOOP_1 has the same effect as:
466 The overall effect of the loop, "i_0 + 20" in the previous example,
467 is obtained by passing in the parameters: LOOP = 1,
468 EVOLUTION_FN = {i_0, +, 2}_1.
472 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
476 if (evolution_fn
== chrec_dont_know
)
477 return chrec_dont_know
;
479 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
481 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
483 if (inner_loop
== loop
484 || flow_loop_nested_p (loop
, inner_loop
))
486 tree nb_iter
= number_of_latch_executions (inner_loop
);
488 if (nb_iter
== chrec_dont_know
)
489 return chrec_dont_know
;
494 /* evolution_fn is the evolution function in LOOP. Get
495 its value in the nb_iter-th iteration. */
496 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
498 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
499 res
= instantiate_parameters (loop
, res
);
501 /* Continue the computation until ending on a parent of LOOP. */
502 return compute_overall_effect_of_inner_loop (loop
, res
);
509 /* If the evolution function is an invariant, there is nothing to do. */
510 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
514 return chrec_dont_know
;
517 /* Associate CHREC to SCALAR. */
520 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
524 if (TREE_CODE (scalar
) != SSA_NAME
)
527 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
531 if (dump_flags
& TDF_SCEV
)
533 fprintf (dump_file
, "(set_scalar_evolution \n");
534 fprintf (dump_file
, " instantiated_below = %d \n",
535 instantiated_below
->index
);
536 fprintf (dump_file
, " (scalar = ");
537 print_generic_expr (dump_file
, scalar
, 0);
538 fprintf (dump_file
, ")\n (scalar_evolution = ");
539 print_generic_expr (dump_file
, chrec
, 0);
540 fprintf (dump_file
, "))\n");
542 if (dump_flags
& TDF_STATS
)
546 *scalar_info
= chrec
;
549 /* Retrieve the chrec associated to SCALAR instantiated below
550 INSTANTIATED_BELOW block. */
553 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
559 if (dump_flags
& TDF_SCEV
)
561 fprintf (dump_file
, "(get_scalar_evolution \n");
562 fprintf (dump_file
, " (scalar = ");
563 print_generic_expr (dump_file
, scalar
, 0);
564 fprintf (dump_file
, ")\n");
566 if (dump_flags
& TDF_STATS
)
570 switch (TREE_CODE (scalar
))
573 res
= *find_var_scev_info (instantiated_below
, scalar
);
583 res
= chrec_not_analyzed_yet
;
587 if (dump_file
&& (dump_flags
& TDF_SCEV
))
589 fprintf (dump_file
, " (scalar_evolution = ");
590 print_generic_expr (dump_file
, res
, 0);
591 fprintf (dump_file
, "))\n");
597 /* Helper function for add_to_evolution. Returns the evolution
598 function for an assignment of the form "a = b + c", where "a" and
599 "b" are on the strongly connected component. CHREC_BEFORE is the
600 information that we already have collected up to this point.
601 TO_ADD is the evolution of "c".
603 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
604 evolution the expression TO_ADD, otherwise construct an evolution
605 part for this loop. */
608 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
611 tree type
, left
, right
;
612 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
614 switch (TREE_CODE (chrec_before
))
616 case POLYNOMIAL_CHREC
:
617 chloop
= get_chrec_loop (chrec_before
);
619 || flow_loop_nested_p (chloop
, loop
))
623 type
= chrec_type (chrec_before
);
625 /* When there is no evolution part in this loop, build it. */
630 right
= SCALAR_FLOAT_TYPE_P (type
)
631 ? build_real (type
, dconst0
)
632 : build_int_cst (type
, 0);
636 var
= CHREC_VARIABLE (chrec_before
);
637 left
= CHREC_LEFT (chrec_before
);
638 right
= CHREC_RIGHT (chrec_before
);
641 to_add
= chrec_convert (type
, to_add
, at_stmt
);
642 right
= chrec_convert_rhs (type
, right
, at_stmt
);
643 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
644 return build_polynomial_chrec (var
, left
, right
);
648 gcc_assert (flow_loop_nested_p (loop
, chloop
));
650 /* Search the evolution in LOOP_NB. */
651 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
653 right
= CHREC_RIGHT (chrec_before
);
654 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
655 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
660 /* These nodes do not depend on a loop. */
661 if (chrec_before
== chrec_dont_know
)
662 return chrec_dont_know
;
665 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
666 return build_polynomial_chrec (loop_nb
, left
, right
);
670 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
673 Description (provided for completeness, for those who read code in
674 a plane, and for my poor 62 bytes brain that would have forgotten
675 all this in the next two or three months):
677 The algorithm of translation of programs from the SSA representation
678 into the chrecs syntax is based on a pattern matching. After having
679 reconstructed the overall tree expression for a loop, there are only
680 two cases that can arise:
682 1. a = loop-phi (init, a + expr)
683 2. a = loop-phi (init, expr)
685 where EXPR is either a scalar constant with respect to the analyzed
686 loop (this is a degree 0 polynomial), or an expression containing
687 other loop-phi definitions (these are higher degree polynomials).
694 | a = phi (init, a + 5)
701 | a = phi (inita, 2 * b + 3)
702 | b = phi (initb, b + 1)
705 For the first case, the semantics of the SSA representation is:
707 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
709 that is, there is a loop index "x" that determines the scalar value
710 of the variable during the loop execution. During the first
711 iteration, the value is that of the initial condition INIT, while
712 during the subsequent iterations, it is the sum of the initial
713 condition with the sum of all the values of EXPR from the initial
714 iteration to the before last considered iteration.
716 For the second case, the semantics of the SSA program is:
718 | a (x) = init, if x = 0;
719 | expr (x - 1), otherwise.
721 The second case corresponds to the PEELED_CHREC, whose syntax is
722 close to the syntax of a loop-phi-node:
724 | phi (init, expr) vs. (init, expr)_x
726 The proof of the translation algorithm for the first case is a
727 proof by structural induction based on the degree of EXPR.
730 When EXPR is a constant with respect to the analyzed loop, or in
731 other words when EXPR is a polynomial of degree 0, the evolution of
732 the variable A in the loop is an affine function with an initial
733 condition INIT, and a step EXPR. In order to show this, we start
734 from the semantics of the SSA representation:
736 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
738 and since "expr (j)" is a constant with respect to "j",
740 f (x) = init + x * expr
742 Finally, based on the semantics of the pure sum chrecs, by
743 identification we get the corresponding chrecs syntax:
745 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
746 f (x) -> {init, +, expr}_x
749 Suppose that EXPR is a polynomial of degree N with respect to the
750 analyzed loop_x for which we have already determined that it is
751 written under the chrecs syntax:
753 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
755 We start from the semantics of the SSA program:
757 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
759 | f (x) = init + \sum_{j = 0}^{x - 1}
760 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
762 | f (x) = init + \sum_{j = 0}^{x - 1}
763 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
765 | f (x) = init + \sum_{k = 0}^{n - 1}
766 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
768 | f (x) = init + \sum_{k = 0}^{n - 1}
769 | (b_k * \binom{x}{k + 1})
771 | f (x) = init + b_0 * \binom{x}{1} + ...
772 | + b_{n-1} * \binom{x}{n}
774 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
775 | + b_{n-1} * \binom{x}{n}
778 And finally from the definition of the chrecs syntax, we identify:
779 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
781 This shows the mechanism that stands behind the add_to_evolution
782 function. An important point is that the use of symbolic
783 parameters avoids the need of an analysis schedule.
790 | a = phi (inita, a + 2 + b)
791 | b = phi (initb, b + 1)
794 When analyzing "a", the algorithm keeps "b" symbolically:
796 | a -> {inita, +, 2 + b}_1
798 Then, after instantiation, the analyzer ends on the evolution:
800 | a -> {inita, +, 2 + initb, +, 1}_1
805 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
806 tree to_add
, gimple at_stmt
)
808 tree type
= chrec_type (to_add
);
809 tree res
= NULL_TREE
;
811 if (to_add
== NULL_TREE
)
814 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
815 instantiated at this point. */
816 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
817 /* This should not happen. */
818 return chrec_dont_know
;
820 if (dump_file
&& (dump_flags
& TDF_SCEV
))
822 fprintf (dump_file
, "(add_to_evolution \n");
823 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
824 fprintf (dump_file
, " (chrec_before = ");
825 print_generic_expr (dump_file
, chrec_before
, 0);
826 fprintf (dump_file
, ")\n (to_add = ");
827 print_generic_expr (dump_file
, to_add
, 0);
828 fprintf (dump_file
, ")\n");
831 if (code
== MINUS_EXPR
)
832 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
833 ? build_real (type
, dconstm1
)
834 : build_int_cst_type (type
, -1));
836 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
838 if (dump_file
&& (dump_flags
& TDF_SCEV
))
840 fprintf (dump_file
, " (res = ");
841 print_generic_expr (dump_file
, res
, 0);
842 fprintf (dump_file
, "))\n");
850 /* This section selects the loops that will be good candidates for the
851 scalar evolution analysis. For the moment, greedily select all the
852 loop nests we could analyze. */
854 /* For a loop with a single exit edge, return the COND_EXPR that
855 guards the exit edge. If the expression is too difficult to
856 analyze, then give up. */
859 get_loop_exit_condition (const struct loop
*loop
)
862 edge exit_edge
= single_exit (loop
);
864 if (dump_file
&& (dump_flags
& TDF_SCEV
))
865 fprintf (dump_file
, "(get_loop_exit_condition \n ");
871 stmt
= last_stmt (exit_edge
->src
);
872 if (gimple_code (stmt
) == GIMPLE_COND
)
876 if (dump_file
&& (dump_flags
& TDF_SCEV
))
878 print_gimple_stmt (dump_file
, res
, 0, 0);
879 fprintf (dump_file
, ")\n");
886 /* Depth first search algorithm. */
888 typedef enum t_bool
{
895 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
897 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
898 Return true if the strongly connected component has been found. */
901 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
902 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
903 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
905 t_bool res
= t_false
;
910 case POINTER_PLUS_EXPR
:
912 if (TREE_CODE (rhs0
) == SSA_NAME
)
914 if (TREE_CODE (rhs1
) == SSA_NAME
)
916 /* Match an assignment under the form:
919 /* We want only assignments of form "name + name" contribute to
920 LIMIT, as the other cases do not necessarily contribute to
921 the complexity of the expression. */
924 evol
= *evolution_of_loop
;
925 res
= follow_ssa_edge
926 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
929 *evolution_of_loop
= add_to_evolution
931 chrec_convert (type
, evol
, at_stmt
),
932 code
, rhs1
, at_stmt
);
934 else if (res
== t_false
)
936 res
= follow_ssa_edge
937 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
938 evolution_of_loop
, limit
);
941 *evolution_of_loop
= add_to_evolution
943 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
944 code
, rhs0
, at_stmt
);
946 else if (res
== t_dont_know
)
947 *evolution_of_loop
= chrec_dont_know
;
950 else if (res
== t_dont_know
)
951 *evolution_of_loop
= chrec_dont_know
;
956 /* Match an assignment under the form:
958 res
= follow_ssa_edge
959 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
960 evolution_of_loop
, limit
);
962 *evolution_of_loop
= add_to_evolution
963 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
965 code
, rhs1
, at_stmt
);
967 else if (res
== t_dont_know
)
968 *evolution_of_loop
= chrec_dont_know
;
972 else if (TREE_CODE (rhs1
) == SSA_NAME
)
974 /* Match an assignment under the form:
976 res
= follow_ssa_edge
977 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
978 evolution_of_loop
, limit
);
980 *evolution_of_loop
= add_to_evolution
981 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
983 code
, rhs0
, at_stmt
);
985 else if (res
== t_dont_know
)
986 *evolution_of_loop
= chrec_dont_know
;
990 /* Otherwise, match an assignment under the form:
992 /* And there is nothing to do. */
997 /* This case is under the form "opnd0 = rhs0 - rhs1". */
998 if (TREE_CODE (rhs0
) == SSA_NAME
)
1000 /* Match an assignment under the form:
1003 /* We want only assignments of form "name - name" contribute to
1004 LIMIT, as the other cases do not necessarily contribute to
1005 the complexity of the expression. */
1006 if (TREE_CODE (rhs1
) == SSA_NAME
)
1009 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1010 evolution_of_loop
, limit
);
1012 *evolution_of_loop
= add_to_evolution
1013 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1014 MINUS_EXPR
, rhs1
, at_stmt
);
1016 else if (res
== t_dont_know
)
1017 *evolution_of_loop
= chrec_dont_know
;
1020 /* Otherwise, match an assignment under the form:
1022 /* And there is nothing to do. */
1033 /* Follow the ssa edge into the expression EXPR.
1034 Return true if the strongly connected component has been found. */
1037 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1038 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1040 enum tree_code code
= TREE_CODE (expr
);
1041 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1044 /* The EXPR is one of the following cases:
1048 - a POINTER_PLUS_EXPR,
1051 - other cases are not yet handled. */
1056 /* This assignment is under the form "a_1 = (cast) rhs. */
1057 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1058 halting_phi
, evolution_of_loop
, limit
);
1059 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1063 /* This assignment is under the form "a_1 = 7". */
1068 /* This assignment is under the form: "a_1 = b_2". */
1069 res
= follow_ssa_edge
1070 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1073 case POINTER_PLUS_EXPR
:
1076 /* This case is under the form "rhs0 +- rhs1". */
1077 rhs0
= TREE_OPERAND (expr
, 0);
1078 rhs1
= TREE_OPERAND (expr
, 1);
1079 type
= TREE_TYPE (rhs0
);
1080 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1081 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1082 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1083 halting_phi
, evolution_of_loop
, limit
);
1087 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1088 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1090 expr
= TREE_OPERAND (expr
, 0);
1091 rhs0
= TREE_OPERAND (expr
, 0);
1092 rhs1
= TREE_OPERAND (expr
, 1);
1093 type
= TREE_TYPE (rhs0
);
1094 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1095 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1096 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1097 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1098 halting_phi
, evolution_of_loop
, limit
);
1105 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1106 It must be handled as a copy assignment of the form a_1 = a_2. */
1107 rhs0
= ASSERT_EXPR_VAR (expr
);
1108 if (TREE_CODE (rhs0
) == SSA_NAME
)
1109 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1110 halting_phi
, evolution_of_loop
, limit
);
1123 /* Follow the ssa edge into the right hand side of an assignment STMT.
1124 Return true if the strongly connected component has been found. */
1127 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1128 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1130 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1131 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1137 /* This assignment is under the form "a_1 = (cast) rhs. */
1138 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1139 halting_phi
, evolution_of_loop
, limit
);
1140 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1143 case POINTER_PLUS_EXPR
:
1146 rhs1
= gimple_assign_rhs1 (stmt
);
1147 rhs2
= gimple_assign_rhs2 (stmt
);
1148 type
= TREE_TYPE (rhs1
);
1149 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1150 halting_phi
, evolution_of_loop
, limit
);
1154 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1155 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1156 halting_phi
, evolution_of_loop
, limit
);
1165 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1168 backedge_phi_arg_p (gimple phi
, int i
)
1170 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1172 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1173 about updating it anywhere, and this should work as well most of the
1175 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1181 /* Helper function for one branch of the condition-phi-node. Return
1182 true if the strongly connected component has been found following
1185 static inline t_bool
1186 follow_ssa_edge_in_condition_phi_branch (int i
,
1188 gimple condition_phi
,
1190 tree
*evolution_of_branch
,
1191 tree init_cond
, int limit
)
1193 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1194 *evolution_of_branch
= chrec_dont_know
;
1196 /* Do not follow back edges (they must belong to an irreducible loop, which
1197 we really do not want to worry about). */
1198 if (backedge_phi_arg_p (condition_phi
, i
))
1201 if (TREE_CODE (branch
) == SSA_NAME
)
1203 *evolution_of_branch
= init_cond
;
1204 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1205 evolution_of_branch
, limit
);
1208 /* This case occurs when one of the condition branches sets
1209 the variable to a constant: i.e. a phi-node like
1210 "a_2 = PHI <a_7(5), 2(6)>;".
1212 FIXME: This case have to be refined correctly:
1213 in some cases it is possible to say something better than
1214 chrec_dont_know, for example using a wrap-around notation. */
1218 /* This function merges the branches of a condition-phi-node in a
1222 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1223 gimple condition_phi
,
1225 tree
*evolution_of_loop
, int limit
)
1228 tree init
= *evolution_of_loop
;
1229 tree evolution_of_branch
;
1230 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1232 &evolution_of_branch
,
1234 if (res
== t_false
|| res
== t_dont_know
)
1237 *evolution_of_loop
= evolution_of_branch
;
1239 n
= gimple_phi_num_args (condition_phi
);
1240 for (i
= 1; i
< n
; i
++)
1242 /* Quickly give up when the evolution of one of the branches is
1244 if (*evolution_of_loop
== chrec_dont_know
)
1247 /* Increase the limit by the PHI argument number to avoid exponential
1248 time and memory complexity. */
1249 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1251 &evolution_of_branch
,
1253 if (res
== t_false
|| res
== t_dont_know
)
1256 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1257 evolution_of_branch
);
1263 /* Follow an SSA edge in an inner loop. It computes the overall
1264 effect of the loop, and following the symbolic initial conditions,
1265 it follows the edges in the parent loop. The inner loop is
1266 considered as a single statement. */
1269 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1270 gimple loop_phi_node
,
1272 tree
*evolution_of_loop
, int limit
)
1274 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1275 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1277 /* Sometimes, the inner loop is too difficult to analyze, and the
1278 result of the analysis is a symbolic parameter. */
1279 if (ev
== PHI_RESULT (loop_phi_node
))
1281 t_bool res
= t_false
;
1282 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1284 for (i
= 0; i
< n
; i
++)
1286 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1289 /* Follow the edges that exit the inner loop. */
1290 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1291 if (!flow_bb_inside_loop_p (loop
, bb
))
1292 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1294 evolution_of_loop
, limit
);
1299 /* If the path crosses this loop-phi, give up. */
1301 *evolution_of_loop
= chrec_dont_know
;
1306 /* Otherwise, compute the overall effect of the inner loop. */
1307 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1308 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1309 evolution_of_loop
, limit
);
1312 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1313 path that is analyzed on the return walk. */
1316 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1317 tree
*evolution_of_loop
, int limit
)
1319 struct loop
*def_loop
;
1321 if (gimple_nop_p (def
))
1324 /* Give up if the path is longer than the MAX that we allow. */
1325 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1328 def_loop
= loop_containing_stmt (def
);
1330 switch (gimple_code (def
))
1333 if (!loop_phi_node_p (def
))
1334 /* DEF is a condition-phi-node. Follow the branches, and
1335 record their evolutions. Finally, merge the collected
1336 information and set the approximation to the main
1338 return follow_ssa_edge_in_condition_phi
1339 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1341 /* When the analyzed phi is the halting_phi, the
1342 depth-first search is over: we have found a path from
1343 the halting_phi to itself in the loop. */
1344 if (def
== halting_phi
)
1347 /* Otherwise, the evolution of the HALTING_PHI depends
1348 on the evolution of another loop-phi-node, i.e. the
1349 evolution function is a higher degree polynomial. */
1350 if (def_loop
== loop
)
1354 if (flow_loop_nested_p (loop
, def_loop
))
1355 return follow_ssa_edge_inner_loop_phi
1356 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1362 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1363 evolution_of_loop
, limit
);
1366 /* At this level of abstraction, the program is just a set
1367 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1368 other node to be handled. */
1375 /* Given a LOOP_PHI_NODE, this function determines the evolution
1376 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1379 analyze_evolution_in_loop (gimple loop_phi_node
,
1382 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1383 tree evolution_function
= chrec_not_analyzed_yet
;
1384 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1387 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1389 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1390 fprintf (dump_file
, " (loop_phi_node = ");
1391 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1392 fprintf (dump_file
, ")\n");
1395 for (i
= 0; i
< n
; i
++)
1397 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1402 /* Select the edges that enter the loop body. */
1403 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1404 if (!flow_bb_inside_loop_p (loop
, bb
))
1407 if (TREE_CODE (arg
) == SSA_NAME
)
1411 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1413 /* Pass in the initial condition to the follow edge function. */
1415 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1417 /* If ev_fn has no evolution in the inner loop, and the
1418 init_cond is not equal to ev_fn, then we have an
1419 ambiguity between two possible values, as we cannot know
1420 the number of iterations at this point. */
1421 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1422 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1423 && !operand_equal_p (init_cond
, ev_fn
, 0))
1424 ev_fn
= chrec_dont_know
;
1429 /* When it is impossible to go back on the same
1430 loop_phi_node by following the ssa edges, the
1431 evolution is represented by a peeled chrec, i.e. the
1432 first iteration, EV_FN has the value INIT_COND, then
1433 all the other iterations it has the value of ARG.
1434 For the moment, PEELED_CHREC nodes are not built. */
1436 ev_fn
= chrec_dont_know
;
1438 /* When there are multiple back edges of the loop (which in fact never
1439 happens currently, but nevertheless), merge their evolutions. */
1440 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1443 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1445 fprintf (dump_file
, " (evolution_function = ");
1446 print_generic_expr (dump_file
, evolution_function
, 0);
1447 fprintf (dump_file
, "))\n");
1450 return evolution_function
;
1453 /* Given a loop-phi-node, return the initial conditions of the
1454 variable on entry of the loop. When the CCP has propagated
1455 constants into the loop-phi-node, the initial condition is
1456 instantiated, otherwise the initial condition is kept symbolic.
1457 This analyzer does not analyze the evolution outside the current
1458 loop, and leaves this task to the on-demand tree reconstructor. */
1461 analyze_initial_condition (gimple loop_phi_node
)
1464 tree init_cond
= chrec_not_analyzed_yet
;
1465 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1467 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1469 fprintf (dump_file
, "(analyze_initial_condition \n");
1470 fprintf (dump_file
, " (loop_phi_node = \n");
1471 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1472 fprintf (dump_file
, ")\n");
1475 n
= gimple_phi_num_args (loop_phi_node
);
1476 for (i
= 0; i
< n
; i
++)
1478 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1479 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1481 /* When the branch is oriented to the loop's body, it does
1482 not contribute to the initial condition. */
1483 if (flow_bb_inside_loop_p (loop
, bb
))
1486 if (init_cond
== chrec_not_analyzed_yet
)
1492 if (TREE_CODE (branch
) == SSA_NAME
)
1494 init_cond
= chrec_dont_know
;
1498 init_cond
= chrec_merge (init_cond
, branch
);
1501 /* Ooops -- a loop without an entry??? */
1502 if (init_cond
== chrec_not_analyzed_yet
)
1503 init_cond
= chrec_dont_know
;
1505 /* During early loop unrolling we do not have fully constant propagated IL.
1506 Handle degenerate PHIs here to not miss important unrollings. */
1507 if (TREE_CODE (init_cond
) == SSA_NAME
)
1509 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1511 if (gimple_code (def
) == GIMPLE_PHI
1512 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1513 /* Only allow invariants here, otherwise we may break
1514 loop-closed SSA form. */
1515 && is_gimple_min_invariant (res
))
1519 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1521 fprintf (dump_file
, " (init_cond = ");
1522 print_generic_expr (dump_file
, init_cond
, 0);
1523 fprintf (dump_file
, "))\n");
1529 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1532 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1535 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1538 if (phi_loop
!= loop
)
1540 struct loop
*subloop
;
1541 tree evolution_fn
= analyze_scalar_evolution
1542 (phi_loop
, PHI_RESULT (loop_phi_node
));
1544 /* Dive one level deeper. */
1545 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1547 /* Interpret the subloop. */
1548 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1552 /* Otherwise really interpret the loop phi. */
1553 init_cond
= analyze_initial_condition (loop_phi_node
);
1554 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1556 /* Verify we maintained the correct initial condition throughout
1557 possible conversions in the SSA chain. */
1558 if (res
!= chrec_dont_know
)
1560 tree new_init
= res
;
1561 if (CONVERT_EXPR_P (res
)
1562 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1563 new_init
= fold_convert (TREE_TYPE (res
),
1564 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1565 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1566 new_init
= CHREC_LEFT (res
);
1567 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1568 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1569 || !operand_equal_p (init_cond
, new_init
, 0))
1570 return chrec_dont_know
;
1576 /* This function merges the branches of a condition-phi-node,
1577 contained in the outermost loop, and whose arguments are already
1581 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1583 int i
, n
= gimple_phi_num_args (condition_phi
);
1584 tree res
= chrec_not_analyzed_yet
;
1586 for (i
= 0; i
< n
; i
++)
1590 if (backedge_phi_arg_p (condition_phi
, i
))
1592 res
= chrec_dont_know
;
1596 branch_chrec
= analyze_scalar_evolution
1597 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1599 res
= chrec_merge (res
, branch_chrec
);
1605 /* Interpret the operation RHS1 OP RHS2. If we didn't
1606 analyze this node before, follow the definitions until ending
1607 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1608 return path, this function propagates evolutions (ala constant copy
1609 propagation). OPND1 is not a GIMPLE expression because we could
1610 analyze the effect of an inner loop: see interpret_loop_phi. */
1613 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1614 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1616 tree res
, chrec1
, chrec2
;
1619 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1621 if (is_gimple_min_invariant (rhs1
))
1622 return chrec_convert (type
, rhs1
, at_stmt
);
1624 if (code
== SSA_NAME
)
1625 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1628 if (code
== ASSERT_EXPR
)
1630 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1631 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1639 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1640 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1642 enum machine_mode mode
;
1643 HOST_WIDE_INT bitsize
, bitpos
;
1650 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1651 &bitsize
, &bitpos
, &offset
,
1652 &mode
, &unsignedp
, &volatilep
, false);
1654 if (TREE_CODE (base
) == MEM_REF
)
1656 rhs2
= TREE_OPERAND (base
, 1);
1657 rhs1
= TREE_OPERAND (base
, 0);
1659 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1660 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1661 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1662 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1663 chrec1
= instantiate_parameters (loop
, chrec1
);
1664 chrec2
= instantiate_parameters (loop
, chrec2
);
1665 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1669 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1670 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1674 if (offset
!= NULL_TREE
)
1676 chrec2
= analyze_scalar_evolution (loop
, offset
);
1677 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1678 chrec2
= instantiate_parameters (loop
, chrec2
);
1679 res
= chrec_fold_plus (type
, res
, chrec2
);
1684 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1686 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1687 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1688 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1689 chrec3
= instantiate_parameters (loop
, chrec3
);
1690 res
= chrec_fold_plus (type
, res
, chrec3
);
1694 res
= chrec_dont_know
;
1697 case POINTER_PLUS_EXPR
:
1698 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1699 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1700 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1701 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1702 chrec1
= instantiate_parameters (loop
, chrec1
);
1703 chrec2
= instantiate_parameters (loop
, chrec2
);
1704 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1708 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1709 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1710 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1711 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1712 chrec1
= instantiate_parameters (loop
, chrec1
);
1713 chrec2
= instantiate_parameters (loop
, chrec2
);
1714 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1718 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1719 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1720 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1721 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1722 chrec1
= instantiate_parameters (loop
, chrec1
);
1723 chrec2
= instantiate_parameters (loop
, chrec2
);
1724 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1728 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1729 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1730 /* TYPE may be integer, real or complex, so use fold_convert. */
1731 chrec1
= instantiate_parameters (loop
, chrec1
);
1732 res
= chrec_fold_multiply (type
, chrec1
,
1733 fold_convert (type
, integer_minus_one_node
));
1737 /* Handle ~X as -1 - X. */
1738 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1739 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1740 chrec1
= instantiate_parameters (loop
, chrec1
);
1741 res
= chrec_fold_minus (type
,
1742 fold_convert (type
, integer_minus_one_node
),
1747 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1748 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1749 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1750 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1751 chrec1
= instantiate_parameters (loop
, chrec1
);
1752 chrec2
= instantiate_parameters (loop
, chrec2
);
1753 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1757 /* In case we have a truncation of a widened operation that in
1758 the truncated type has undefined overflow behavior analyze
1759 the operation done in an unsigned type of the same precision
1760 as the final truncation. We cannot derive a scalar evolution
1761 for the widened operation but for the truncated result. */
1762 if (TREE_CODE (type
) == INTEGER_TYPE
1763 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1764 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1765 && TYPE_OVERFLOW_UNDEFINED (type
)
1766 && TREE_CODE (rhs1
) == SSA_NAME
1767 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1768 && is_gimple_assign (def
)
1769 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1770 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1772 tree utype
= unsigned_type_for (type
);
1773 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1774 gimple_assign_rhs1 (def
),
1775 gimple_assign_rhs_code (def
),
1776 gimple_assign_rhs2 (def
));
1779 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1780 res
= chrec_convert (type
, chrec1
, at_stmt
);
1784 res
= chrec_dont_know
;
1791 /* Interpret the expression EXPR. */
1794 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1796 enum tree_code code
;
1797 tree type
= TREE_TYPE (expr
), op0
, op1
;
1799 if (automatically_generated_chrec_p (expr
))
1802 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1803 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1804 return chrec_dont_know
;
1806 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1808 return interpret_rhs_expr (loop
, at_stmt
, type
,
1812 /* Interpret the rhs of the assignment STMT. */
1815 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1817 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1818 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1820 return interpret_rhs_expr (loop
, stmt
, type
,
1821 gimple_assign_rhs1 (stmt
), code
,
1822 gimple_assign_rhs2 (stmt
));
1827 /* This section contains all the entry points:
1828 - number_of_iterations_in_loop,
1829 - analyze_scalar_evolution,
1830 - instantiate_parameters.
1833 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1834 common ancestor of DEF_LOOP and USE_LOOP. */
1837 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1838 struct loop
*def_loop
,
1844 if (def_loop
== wrto_loop
)
1847 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1848 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1850 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1853 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1856 /* Helper recursive function. */
1859 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1861 tree type
= TREE_TYPE (var
);
1864 struct loop
*def_loop
;
1866 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1867 return chrec_dont_know
;
1869 if (TREE_CODE (var
) != SSA_NAME
)
1870 return interpret_expr (loop
, NULL
, var
);
1872 def
= SSA_NAME_DEF_STMT (var
);
1873 bb
= gimple_bb (def
);
1874 def_loop
= bb
? bb
->loop_father
: NULL
;
1877 || !flow_bb_inside_loop_p (loop
, bb
))
1879 /* Keep the symbolic form. */
1884 if (res
!= chrec_not_analyzed_yet
)
1886 if (loop
!= bb
->loop_father
)
1887 res
= compute_scalar_evolution_in_loop
1888 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1893 if (loop
!= def_loop
)
1895 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1896 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1901 switch (gimple_code (def
))
1904 res
= interpret_gimple_assign (loop
, def
);
1908 if (loop_phi_node_p (def
))
1909 res
= interpret_loop_phi (loop
, def
);
1911 res
= interpret_condition_phi (loop
, def
);
1915 res
= chrec_dont_know
;
1921 /* Keep the symbolic form. */
1922 if (res
== chrec_dont_know
)
1925 if (loop
== def_loop
)
1926 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1931 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1932 LOOP. LOOP is the loop in which the variable is used.
1934 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1935 pointer to the statement that uses this variable, in order to
1936 determine the evolution function of the variable, use the following
1939 loop_p loop = loop_containing_stmt (stmt);
1940 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1941 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1945 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1949 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1951 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1952 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1953 fprintf (dump_file
, " (scalar = ");
1954 print_generic_expr (dump_file
, var
, 0);
1955 fprintf (dump_file
, ")\n");
1958 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1959 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1961 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1962 fprintf (dump_file
, ")\n");
1967 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
1970 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
1972 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
1975 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1976 WRTO_LOOP (which should be a superloop of USE_LOOP)
1978 FOLDED_CASTS is set to true if resolve_mixers used
1979 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1980 at the moment in order to keep things simple).
1982 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1985 for (i = 0; i < 100; i++) -- loop 1
1987 for (j = 0; j < 100; j++) -- loop 2
1994 for (t = 0; t < 100; t++) -- loop 3
2001 Both k1 and k2 are invariants in loop3, thus
2002 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2003 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2005 As they are invariant, it does not matter whether we consider their
2006 usage in loop 3 or loop 2, hence
2007 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2008 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2009 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2010 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2012 Similarly for their evolutions with respect to loop 1. The values of K2
2013 in the use in loop 2 vary independently on loop 1, thus we cannot express
2014 the evolution with respect to loop 1:
2015 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2016 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2017 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2018 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2020 The value of k2 in the use in loop 1 is known, though:
2021 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2022 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2026 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2027 tree version
, bool *folded_casts
)
2030 tree ev
= version
, tmp
;
2032 /* We cannot just do
2034 tmp = analyze_scalar_evolution (use_loop, version);
2035 ev = resolve_mixers (wrto_loop, tmp);
2037 as resolve_mixers would query the scalar evolution with respect to
2038 wrto_loop. For example, in the situation described in the function
2039 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2042 analyze_scalar_evolution (use_loop, version) = k2
2044 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2045 is 100, which is a wrong result, since we are interested in the
2048 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2049 each time checking that there is no evolution in the inner loop. */
2052 *folded_casts
= false;
2055 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2056 ev
= resolve_mixers (use_loop
, tmp
);
2058 if (folded_casts
&& tmp
!= ev
)
2059 *folded_casts
= true;
2061 if (use_loop
== wrto_loop
)
2064 /* If the value of the use changes in the inner loop, we cannot express
2065 its value in the outer loop (we might try to return interval chrec,
2066 but we do not have a user for it anyway) */
2067 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2069 return chrec_dont_know
;
2071 use_loop
= loop_outer (use_loop
);
2076 /* Hashtable helpers for a temporary hash-table used when
2077 instantiating a CHREC or resolving mixers. For this use
2078 instantiated_below is always the same. */
2080 struct instantiate_cache_type
2083 vec
<scev_info_str
> entries
;
2085 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2086 ~instantiate_cache_type ();
2087 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2088 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2091 instantiate_cache_type::~instantiate_cache_type ()
2100 /* Cache to avoid infinite recursion when instantiating an SSA name.
2101 Live during the outermost instantiate_scev or resolve_mixers call. */
2102 static instantiate_cache_type
*global_cache
;
2104 /* Computes a hash function for database element ELT. */
2106 static inline hashval_t
2107 hash_idx_scev_info (const void *elt_
)
2109 unsigned idx
= ((size_t) elt_
) - 2;
2110 return hash_scev_info (&global_cache
->entries
[idx
]);
2113 /* Compares database elements E1 and E2. */
2116 eq_idx_scev_info (const void *e1
, const void *e2
)
2118 unsigned idx1
= ((size_t) e1
) - 2;
2119 return eq_scev_info (&global_cache
->entries
[idx1
], e2
);
2122 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2125 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2126 tree name
, basic_block instantiate_below
)
2130 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2131 cache
.entries
.create (10);
2135 e
.name_version
= SSA_NAME_VERSION (name
);
2136 e
.instantiated_below
= instantiate_below
->index
;
2137 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2138 hash_scev_info (&e
), INSERT
);
2141 e
.chrec
= chrec_not_analyzed_yet
;
2142 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2143 cache
.entries
.safe_push (e
);
2146 return ((size_t)*slot
) - 2;
2150 /* Return the closed_loop_phi node for VAR. If there is none, return
2154 loop_closed_phi_def (tree var
)
2159 gimple_stmt_iterator psi
;
2161 if (var
== NULL_TREE
2162 || TREE_CODE (var
) != SSA_NAME
)
2165 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2166 exit
= single_exit (loop
);
2170 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2172 phi
= gsi_stmt (psi
);
2173 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2174 return PHI_RESULT (phi
);
2180 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2183 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2184 and EVOLUTION_LOOP, that were left under a symbolic form.
2186 CHREC is an SSA_NAME to be instantiated.
2188 CACHE is the cache of already instantiated values.
2190 FOLD_CONVERSIONS should be set to true when the conversions that
2191 may wrap in signed/pointer type are folded, as long as the value of
2192 the chrec is preserved.
2194 SIZE_EXPR is used for computing the size of the expression to be
2195 instantiated, and to stop if it exceeds some limit. */
2198 instantiate_scev_name (basic_block instantiate_below
,
2199 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2201 bool fold_conversions
,
2205 struct loop
*def_loop
;
2206 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2208 /* A parameter (or loop invariant and we do not want to include
2209 evolutions in outer loops), nothing to do. */
2211 || loop_depth (def_bb
->loop_father
) == 0
2212 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2215 /* We cache the value of instantiated variable to avoid exponential
2216 time complexity due to reevaluations. We also store the convenient
2217 value in the cache in order to prevent infinite recursion -- we do
2218 not want to instantiate the SSA_NAME if it is in a mixer
2219 structure. This is used for avoiding the instantiation of
2220 recursively defined functions, such as:
2222 | a_2 -> {0, +, 1, +, a_2}_1 */
2224 unsigned si
= get_instantiated_value_entry (*global_cache
,
2225 chrec
, instantiate_below
);
2226 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2227 return global_cache
->get (si
);
2229 /* On recursion return chrec_dont_know. */
2230 global_cache
->set (si
, chrec_dont_know
);
2232 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2234 /* If the analysis yields a parametric chrec, instantiate the
2236 res
= analyze_scalar_evolution (def_loop
, chrec
);
2238 /* Don't instantiate default definitions. */
2239 if (TREE_CODE (res
) == SSA_NAME
2240 && SSA_NAME_IS_DEFAULT_DEF (res
))
2243 /* Don't instantiate loop-closed-ssa phi nodes. */
2244 else if (TREE_CODE (res
) == SSA_NAME
2245 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2246 > loop_depth (def_loop
))
2249 res
= loop_closed_phi_def (chrec
);
2253 /* When there is no loop_closed_phi_def, it means that the
2254 variable is not used after the loop: try to still compute the
2255 value of the variable when exiting the loop. */
2256 if (res
== NULL_TREE
)
2258 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2259 res
= analyze_scalar_evolution (loop
, chrec
);
2260 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2261 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2263 fold_conversions
, size_expr
);
2265 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2266 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2267 res
= chrec_dont_know
;
2270 else if (res
!= chrec_dont_know
)
2273 && def_bb
->loop_father
!= inner_loop
2274 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2275 /* ??? We could try to compute the overall effect of the loop here. */
2276 res
= chrec_dont_know
;
2278 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2280 fold_conversions
, size_expr
);
2283 /* Store the correct value to the cache. */
2284 global_cache
->set (si
, res
);
2288 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2289 and EVOLUTION_LOOP, that were left under a symbolic form.
2291 CHREC is a polynomial chain of recurrence 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_poly (basic_block instantiate_below
,
2304 struct loop
*evolution_loop
, struct loop
*,
2305 tree chrec
, bool fold_conversions
, int size_expr
)
2308 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2309 get_chrec_loop (chrec
),
2310 CHREC_LEFT (chrec
), fold_conversions
,
2312 if (op0
== chrec_dont_know
)
2313 return chrec_dont_know
;
2315 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2316 get_chrec_loop (chrec
),
2317 CHREC_RIGHT (chrec
), fold_conversions
,
2319 if (op1
== chrec_dont_know
)
2320 return chrec_dont_know
;
2322 if (CHREC_LEFT (chrec
) != op0
2323 || CHREC_RIGHT (chrec
) != op1
)
2325 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2326 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2332 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2333 and EVOLUTION_LOOP, that were left under a symbolic form.
2335 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
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_binary (basic_block instantiate_below
,
2348 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2349 tree chrec
, enum tree_code code
,
2350 tree type
, tree c0
, tree c1
,
2351 bool fold_conversions
, int size_expr
)
2354 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2355 c0
, fold_conversions
, size_expr
);
2356 if (op0
== chrec_dont_know
)
2357 return chrec_dont_know
;
2359 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2360 c1
, fold_conversions
, size_expr
);
2361 if (op1
== chrec_dont_know
)
2362 return chrec_dont_know
;
2367 op0
= chrec_convert (type
, op0
, NULL
);
2368 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2372 case POINTER_PLUS_EXPR
:
2374 return chrec_fold_plus (type
, op0
, op1
);
2377 return chrec_fold_minus (type
, op0
, op1
);
2380 return chrec_fold_multiply (type
, op0
, op1
);
2387 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2390 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2391 and EVOLUTION_LOOP, that were left under a symbolic form.
2393 "CHREC" is an array reference to be instantiated.
2395 CACHE is the cache of already instantiated values.
2397 FOLD_CONVERSIONS should be set to true when the conversions that
2398 may wrap in signed/pointer type are folded, as long as the value of
2399 the chrec is preserved.
2401 SIZE_EXPR is used for computing the size of the expression to be
2402 instantiated, and to stop if it exceeds some limit. */
2405 instantiate_array_ref (basic_block instantiate_below
,
2406 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2407 tree chrec
, bool fold_conversions
, int size_expr
)
2410 tree index
= TREE_OPERAND (chrec
, 1);
2411 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2413 fold_conversions
, size_expr
);
2415 if (op1
== chrec_dont_know
)
2416 return chrec_dont_know
;
2418 if (chrec
&& op1
== index
)
2421 res
= unshare_expr (chrec
);
2422 TREE_OPERAND (res
, 1) = op1
;
2426 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2427 and EVOLUTION_LOOP, that were left under a symbolic form.
2429 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
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_convert (basic_block instantiate_below
,
2443 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2444 tree chrec
, tree type
, tree op
,
2445 bool fold_conversions
, int size_expr
)
2447 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2449 fold_conversions
, size_expr
);
2451 if (op0
== chrec_dont_know
)
2452 return chrec_dont_know
;
2454 if (fold_conversions
)
2456 tree tmp
= chrec_convert_aggressive (type
, op0
);
2461 if (chrec
&& op0
== op
)
2464 /* If we used chrec_convert_aggressive, we can no longer assume that
2465 signed chrecs do not overflow, as chrec_convert does, so avoid
2466 calling it in that case. */
2467 if (fold_conversions
)
2468 return fold_convert (type
, op0
);
2470 return chrec_convert (type
, op0
, NULL
);
2473 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2474 and EVOLUTION_LOOP, that were left under a symbolic form.
2476 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2477 Handle ~X as -1 - X.
2478 Handle -X as -1 * X.
2480 CACHE is the cache of already instantiated values.
2482 FOLD_CONVERSIONS should be set to true when the conversions that
2483 may wrap in signed/pointer type are folded, as long as the value of
2484 the chrec is preserved.
2486 SIZE_EXPR is used for computing the size of the expression to be
2487 instantiated, and to stop if it exceeds some limit. */
2490 instantiate_scev_not (basic_block instantiate_below
,
2491 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2493 enum tree_code code
, tree type
, tree op
,
2494 bool fold_conversions
, int size_expr
)
2496 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2498 fold_conversions
, size_expr
);
2500 if (op0
== chrec_dont_know
)
2501 return chrec_dont_know
;
2505 op0
= chrec_convert (type
, op0
, NULL
);
2510 return chrec_fold_minus
2511 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2514 return chrec_fold_multiply
2515 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2522 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
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 3 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_3 (basic_block instantiate_below
,
2541 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2543 bool fold_conversions
, int size_expr
)
2546 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2547 inner_loop
, TREE_OPERAND (chrec
, 0),
2548 fold_conversions
, size_expr
);
2549 if (op0
== chrec_dont_know
)
2550 return chrec_dont_know
;
2552 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2553 inner_loop
, TREE_OPERAND (chrec
, 1),
2554 fold_conversions
, size_expr
);
2555 if (op1
== chrec_dont_know
)
2556 return chrec_dont_know
;
2558 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2559 inner_loop
, TREE_OPERAND (chrec
, 2),
2560 fold_conversions
, size_expr
);
2561 if (op2
== chrec_dont_know
)
2562 return chrec_dont_know
;
2564 if (op0
== TREE_OPERAND (chrec
, 0)
2565 && op1
== TREE_OPERAND (chrec
, 1)
2566 && op2
== TREE_OPERAND (chrec
, 2))
2569 return fold_build3 (TREE_CODE (chrec
),
2570 TREE_TYPE (chrec
), op0
, op1
, op2
);
2573 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2574 and EVOLUTION_LOOP, that were left under a symbolic form.
2576 CHREC is an expression with 2 operands to be instantiated.
2578 CACHE is the cache of already instantiated values.
2580 FOLD_CONVERSIONS should be set to true when the conversions that
2581 may wrap in signed/pointer type are folded, as long as the value of
2582 the chrec is preserved.
2584 SIZE_EXPR is used for computing the size of the expression to be
2585 instantiated, and to stop if it exceeds some limit. */
2588 instantiate_scev_2 (basic_block instantiate_below
,
2589 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2591 bool fold_conversions
, int size_expr
)
2594 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2595 inner_loop
, TREE_OPERAND (chrec
, 0),
2596 fold_conversions
, size_expr
);
2597 if (op0
== chrec_dont_know
)
2598 return chrec_dont_know
;
2600 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2601 inner_loop
, TREE_OPERAND (chrec
, 1),
2602 fold_conversions
, size_expr
);
2603 if (op1
== chrec_dont_know
)
2604 return chrec_dont_know
;
2606 if (op0
== TREE_OPERAND (chrec
, 0)
2607 && op1
== TREE_OPERAND (chrec
, 1))
2610 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2613 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2614 and EVOLUTION_LOOP, that were left under a symbolic form.
2616 CHREC is an expression with 2 operands to be instantiated.
2618 CACHE is the cache of already instantiated values.
2620 FOLD_CONVERSIONS should be set to true when the conversions that
2621 may wrap in signed/pointer type are folded, as long as the value of
2622 the chrec is preserved.
2624 SIZE_EXPR is used for computing the size of the expression to be
2625 instantiated, and to stop if it exceeds some limit. */
2628 instantiate_scev_1 (basic_block instantiate_below
,
2629 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2631 bool fold_conversions
, int size_expr
)
2633 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2634 inner_loop
, TREE_OPERAND (chrec
, 0),
2635 fold_conversions
, size_expr
);
2637 if (op0
== chrec_dont_know
)
2638 return chrec_dont_know
;
2640 if (op0
== TREE_OPERAND (chrec
, 0))
2643 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2646 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2647 and EVOLUTION_LOOP, that were left under a symbolic form.
2649 CHREC is the scalar evolution to instantiate.
2651 CACHE is the cache of already instantiated values.
2653 FOLD_CONVERSIONS should be set to true when the conversions that
2654 may wrap in signed/pointer type are folded, as long as the value of
2655 the chrec is preserved.
2657 SIZE_EXPR is used for computing the size of the expression to be
2658 instantiated, and to stop if it exceeds some limit. */
2661 instantiate_scev_r (basic_block instantiate_below
,
2662 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2664 bool fold_conversions
, int size_expr
)
2666 /* Give up if the expression is larger than the MAX that we allow. */
2667 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2668 return chrec_dont_know
;
2670 if (chrec
== NULL_TREE
2671 || automatically_generated_chrec_p (chrec
)
2672 || is_gimple_min_invariant (chrec
))
2675 switch (TREE_CODE (chrec
))
2678 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2680 fold_conversions
, size_expr
);
2682 case POLYNOMIAL_CHREC
:
2683 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2685 fold_conversions
, size_expr
);
2687 case POINTER_PLUS_EXPR
:
2691 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2693 TREE_CODE (chrec
), chrec_type (chrec
),
2694 TREE_OPERAND (chrec
, 0),
2695 TREE_OPERAND (chrec
, 1),
2696 fold_conversions
, size_expr
);
2699 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2701 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2702 fold_conversions
, size_expr
);
2706 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2708 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2709 TREE_OPERAND (chrec
, 0),
2710 fold_conversions
, size_expr
);
2713 case SCEV_NOT_KNOWN
:
2714 return chrec_dont_know
;
2720 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2722 fold_conversions
, size_expr
);
2728 if (VL_EXP_CLASS_P (chrec
))
2729 return chrec_dont_know
;
2731 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2734 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2736 fold_conversions
, size_expr
);
2739 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2741 fold_conversions
, size_expr
);
2744 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2746 fold_conversions
, size_expr
);
2755 /* Too complicated to handle. */
2756 return chrec_dont_know
;
2759 /* Analyze all the parameters of the chrec that were left under a
2760 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2761 recursive instantiation of parameters: a parameter is a variable
2762 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2763 a function parameter. */
2766 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2771 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2773 fprintf (dump_file
, "(instantiate_scev \n");
2774 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2775 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2776 fprintf (dump_file
, " (chrec = ");
2777 print_generic_expr (dump_file
, chrec
, 0);
2778 fprintf (dump_file
, ")\n");
2784 global_cache
= new instantiate_cache_type
;
2788 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2789 NULL
, chrec
, false, 0);
2793 delete global_cache
;
2794 global_cache
= NULL
;
2797 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2799 fprintf (dump_file
, " (res = ");
2800 print_generic_expr (dump_file
, res
, 0);
2801 fprintf (dump_file
, "))\n");
2807 /* Similar to instantiate_parameters, but does not introduce the
2808 evolutions in outer loops for LOOP invariants in CHREC, and does not
2809 care about causing overflows, as long as they do not affect value
2810 of an expression. */
2813 resolve_mixers (struct loop
*loop
, tree chrec
)
2818 global_cache
= new instantiate_cache_type
;
2822 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2827 delete global_cache
;
2828 global_cache
= NULL
;
2834 /* Entry point for the analysis of the number of iterations pass.
2835 This function tries to safely approximate the number of iterations
2836 the loop will run. When this property is not decidable at compile
2837 time, the result is chrec_dont_know. Otherwise the result is a
2838 scalar or a symbolic parameter. When the number of iterations may
2839 be equal to zero and the property cannot be determined at compile
2840 time, the result is a COND_EXPR that represents in a symbolic form
2841 the conditions under which the number of iterations is not zero.
2843 Example of analysis: suppose that the loop has an exit condition:
2845 "if (b > 49) goto end_loop;"
2847 and that in a previous analysis we have determined that the
2848 variable 'b' has an evolution function:
2850 "EF = {23, +, 5}_2".
2852 When we evaluate the function at the point 5, i.e. the value of the
2853 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2854 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2855 the loop body has been executed 6 times. */
2858 number_of_latch_executions (struct loop
*loop
)
2861 struct tree_niter_desc niter_desc
;
2865 /* Determine whether the number of iterations in loop has already
2867 res
= loop
->nb_iterations
;
2871 may_be_zero
= NULL_TREE
;
2873 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2874 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2876 res
= chrec_dont_know
;
2877 exit
= single_exit (loop
);
2879 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2881 may_be_zero
= niter_desc
.may_be_zero
;
2882 res
= niter_desc
.niter
;
2885 if (res
== chrec_dont_know
2887 || integer_zerop (may_be_zero
))
2889 else if (integer_nonzerop (may_be_zero
))
2890 res
= build_int_cst (TREE_TYPE (res
), 0);
2892 else if (COMPARISON_CLASS_P (may_be_zero
))
2893 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2894 build_int_cst (TREE_TYPE (res
), 0), res
);
2896 res
= chrec_dont_know
;
2898 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2900 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2901 print_generic_expr (dump_file
, res
, 0);
2902 fprintf (dump_file
, "))\n");
2905 loop
->nb_iterations
= res
;
2909 /* Returns the number of executions of the exit condition of LOOP,
2910 i.e., the number by one higher than number_of_latch_executions.
2911 Note that unlike number_of_latch_executions, this number does
2912 not necessarily fit in the unsigned variant of the type of
2913 the control variable -- if the number of iterations is a constant,
2914 we return chrec_dont_know if adding one to number_of_latch_executions
2915 overflows; however, in case the number of iterations is symbolic
2916 expression, the caller is responsible for dealing with this
2917 the possible overflow. */
2920 number_of_exit_cond_executions (struct loop
*loop
)
2922 tree ret
= number_of_latch_executions (loop
);
2923 tree type
= chrec_type (ret
);
2925 if (chrec_contains_undetermined (ret
))
2928 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2929 if (TREE_CODE (ret
) == INTEGER_CST
2930 && TREE_OVERFLOW (ret
))
2931 return chrec_dont_know
;
2938 /* Counters for the stats. */
2944 unsigned nb_affine_multivar
;
2945 unsigned nb_higher_poly
;
2946 unsigned nb_chrec_dont_know
;
2947 unsigned nb_undetermined
;
2950 /* Reset the counters. */
2953 reset_chrecs_counters (struct chrec_stats
*stats
)
2955 stats
->nb_chrecs
= 0;
2956 stats
->nb_affine
= 0;
2957 stats
->nb_affine_multivar
= 0;
2958 stats
->nb_higher_poly
= 0;
2959 stats
->nb_chrec_dont_know
= 0;
2960 stats
->nb_undetermined
= 0;
2963 /* Dump the contents of a CHREC_STATS structure. */
2966 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2968 fprintf (file
, "\n(\n");
2969 fprintf (file
, "-----------------------------------------\n");
2970 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2971 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2972 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2973 stats
->nb_higher_poly
);
2974 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2975 fprintf (file
, "-----------------------------------------\n");
2976 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2977 fprintf (file
, "%d\twith undetermined coefficients\n",
2978 stats
->nb_undetermined
);
2979 fprintf (file
, "-----------------------------------------\n");
2980 fprintf (file
, "%d\tchrecs in the scev database\n",
2981 (int) htab_elements (scalar_evolution_info
));
2982 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2983 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2984 fprintf (file
, "-----------------------------------------\n");
2985 fprintf (file
, ")\n\n");
2988 /* Gather statistics about CHREC. */
2991 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2993 if (dump_file
&& (dump_flags
& TDF_STATS
))
2995 fprintf (dump_file
, "(classify_chrec ");
2996 print_generic_expr (dump_file
, chrec
, 0);
2997 fprintf (dump_file
, "\n");
3002 if (chrec
== NULL_TREE
)
3004 stats
->nb_undetermined
++;
3008 switch (TREE_CODE (chrec
))
3010 case POLYNOMIAL_CHREC
:
3011 if (evolution_function_is_affine_p (chrec
))
3013 if (dump_file
&& (dump_flags
& TDF_STATS
))
3014 fprintf (dump_file
, " affine_univariate\n");
3017 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3019 if (dump_file
&& (dump_flags
& TDF_STATS
))
3020 fprintf (dump_file
, " affine_multivariate\n");
3021 stats
->nb_affine_multivar
++;
3025 if (dump_file
&& (dump_flags
& TDF_STATS
))
3026 fprintf (dump_file
, " higher_degree_polynomial\n");
3027 stats
->nb_higher_poly
++;
3036 if (chrec_contains_undetermined (chrec
))
3038 if (dump_file
&& (dump_flags
& TDF_STATS
))
3039 fprintf (dump_file
, " undetermined\n");
3040 stats
->nb_undetermined
++;
3043 if (dump_file
&& (dump_flags
& TDF_STATS
))
3044 fprintf (dump_file
, ")\n");
3047 /* Callback for htab_traverse, gathers information on chrecs in the
3051 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
3053 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
3055 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3060 /* Classify the chrecs of the whole database. */
3063 gather_stats_on_scev_database (void)
3065 struct chrec_stats stats
;
3070 reset_chrecs_counters (&stats
);
3072 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3075 dump_chrecs_stats (dump_file
, &stats
);
3083 initialize_scalar_evolutions_analyzer (void)
3085 /* The elements below are unique. */
3086 if (chrec_dont_know
== NULL_TREE
)
3088 chrec_not_analyzed_yet
= NULL_TREE
;
3089 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3090 chrec_known
= make_node (SCEV_KNOWN
);
3091 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3092 TREE_TYPE (chrec_known
) = void_type_node
;
3096 /* Initialize the analysis of scalar evolutions for LOOPS. */
3099 scev_initialize (void)
3105 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3108 initialize_scalar_evolutions_analyzer ();
3110 FOR_EACH_LOOP (li
, loop
, 0)
3112 loop
->nb_iterations
= NULL_TREE
;
3116 /* Return true if SCEV is initialized. */
3119 scev_initialized_p (void)
3121 return scalar_evolution_info
!= NULL
;
3124 /* Cleans up the information cached by the scalar evolutions analysis
3125 in the hash table. */
3128 scev_reset_htab (void)
3130 if (!scalar_evolution_info
)
3133 htab_empty (scalar_evolution_info
);
3136 /* Cleans up the information cached by the scalar evolutions analysis
3137 in the hash table and in the loop->nb_iterations. */
3150 FOR_EACH_LOOP (li
, loop
, 0)
3152 loop
->nb_iterations
= NULL_TREE
;
3156 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3157 respect to WRTO_LOOP and returns its base and step in IV if possible
3158 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3159 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3160 invariant in LOOP. Otherwise we require it to be an integer constant.
3162 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3163 because it is computed in signed arithmetics). Consequently, adding an
3166 for (i = IV->base; ; i += IV->step)
3168 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3169 false for the type of the induction variable, or you can prove that i does
3170 not wrap by some other argument. Otherwise, this might introduce undefined
3173 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3175 must be used instead. */
3178 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3179 affine_iv
*iv
, bool allow_nonconstant_step
)
3184 iv
->base
= NULL_TREE
;
3185 iv
->step
= NULL_TREE
;
3186 iv
->no_overflow
= false;
3188 type
= TREE_TYPE (op
);
3189 if (!POINTER_TYPE_P (type
)
3190 && !INTEGRAL_TYPE_P (type
))
3193 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3195 if (chrec_contains_undetermined (ev
)
3196 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3199 if (tree_does_not_contain_chrecs (ev
))
3202 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3203 iv
->no_overflow
= true;
3207 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3208 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3211 iv
->step
= CHREC_RIGHT (ev
);
3212 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3213 || tree_contains_chrecs (iv
->step
, NULL
))
3216 iv
->base
= CHREC_LEFT (ev
);
3217 if (tree_contains_chrecs (iv
->base
, NULL
))
3220 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3225 /* Finalize the scalar evolution analysis. */
3228 scev_finalize (void)
3230 if (!scalar_evolution_info
)
3232 htab_delete (scalar_evolution_info
);
3233 scalar_evolution_info
= NULL
;
3236 /* Returns true if the expression EXPR is considered to be too expensive
3237 for scev_const_prop. */
3240 expression_expensive_p (tree expr
)
3242 enum tree_code code
;
3244 if (is_gimple_val (expr
))
3247 code
= TREE_CODE (expr
);
3248 if (code
== TRUNC_DIV_EXPR
3249 || code
== CEIL_DIV_EXPR
3250 || code
== FLOOR_DIV_EXPR
3251 || code
== ROUND_DIV_EXPR
3252 || code
== TRUNC_MOD_EXPR
3253 || code
== CEIL_MOD_EXPR
3254 || code
== FLOOR_MOD_EXPR
3255 || code
== ROUND_MOD_EXPR
3256 || code
== EXACT_DIV_EXPR
)
3258 /* Division by power of two is usually cheap, so we allow it.
3259 Forbid anything else. */
3260 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3264 switch (TREE_CODE_CLASS (code
))
3267 case tcc_comparison
:
3268 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3273 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3280 /* Replace ssa names for that scev can prove they are constant by the
3281 appropriate constants. Also perform final value replacement in loops,
3282 in case the replacement expressions are cheap.
3284 We only consider SSA names defined by phi nodes; rest is left to the
3285 ordinary constant propagation pass. */
3288 scev_const_prop (void)
3291 tree name
, type
, ev
;
3293 struct loop
*loop
, *ex_loop
;
3294 bitmap ssa_names_to_remove
= NULL
;
3297 gimple_stmt_iterator psi
;
3299 if (number_of_loops (cfun
) <= 1)
3304 loop
= bb
->loop_father
;
3306 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3308 phi
= gsi_stmt (psi
);
3309 name
= PHI_RESULT (phi
);
3311 if (virtual_operand_p (name
))
3314 type
= TREE_TYPE (name
);
3316 if (!POINTER_TYPE_P (type
)
3317 && !INTEGRAL_TYPE_P (type
))
3320 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3321 if (!is_gimple_min_invariant (ev
)
3322 || !may_propagate_copy (name
, ev
))
3325 /* Replace the uses of the name. */
3327 replace_uses_by (name
, ev
);
3329 if (!ssa_names_to_remove
)
3330 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3331 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3335 /* Remove the ssa names that were replaced by constants. We do not
3336 remove them directly in the previous cycle, since this
3337 invalidates scev cache. */
3338 if (ssa_names_to_remove
)
3342 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3344 gimple_stmt_iterator psi
;
3345 name
= ssa_name (i
);
3346 phi
= SSA_NAME_DEF_STMT (name
);
3348 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3349 psi
= gsi_for_stmt (phi
);
3350 remove_phi_node (&psi
, true);
3353 BITMAP_FREE (ssa_names_to_remove
);
3357 /* Now the regular final value replacement. */
3358 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3361 tree def
, rslt
, niter
;
3362 gimple_stmt_iterator bsi
;
3364 /* If we do not know exact number of iterations of the loop, we cannot
3365 replace the final value. */
3366 exit
= single_exit (loop
);
3370 niter
= number_of_latch_executions (loop
);
3371 if (niter
== chrec_dont_know
)
3374 /* Ensure that it is possible to insert new statements somewhere. */
3375 if (!single_pred_p (exit
->dest
))
3376 split_loop_exit_edge (exit
);
3377 bsi
= gsi_after_labels (exit
->dest
);
3379 ex_loop
= superloop_at_depth (loop
,
3380 loop_depth (exit
->dest
->loop_father
) + 1);
3382 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3384 phi
= gsi_stmt (psi
);
3385 rslt
= PHI_RESULT (phi
);
3386 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3387 if (virtual_operand_p (def
))
3393 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3394 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3400 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3401 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3402 if (!tree_does_not_contain_chrecs (def
)
3403 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3404 /* Moving the computation from the loop may prolong life range
3405 of some ssa names, which may cause problems if they appear
3406 on abnormal edges. */
3407 || contains_abnormal_ssa_name_p (def
)
3408 /* Do not emit expensive expressions. The rationale is that
3409 when someone writes a code like
3411 while (n > 45) n -= 45;
3413 he probably knows that n is not large, and does not want it
3414 to be turned into n %= 45. */
3415 || expression_expensive_p (def
))
3417 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3419 fprintf (dump_file
, "not replacing:\n ");
3420 print_gimple_stmt (dump_file
, phi
, 0, 0);
3421 fprintf (dump_file
, "\n");
3427 /* Eliminate the PHI node and replace it by a computation outside
3431 fprintf (dump_file
, "\nfinal value replacement:\n ");
3432 print_gimple_stmt (dump_file
, phi
, 0, 0);
3433 fprintf (dump_file
, " with\n ");
3435 def
= unshare_expr (def
);
3436 remove_phi_node (&psi
, false);
3438 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3439 true, GSI_SAME_STMT
);
3440 ass
= gimple_build_assign (rslt
, def
);
3441 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3444 print_gimple_stmt (dump_file
, ass
, 0, 0);
3445 fprintf (dump_file
, "\n");
3452 #include "gt-tree-scalar-evolution.h"