1 /* Scalar evolution detector.
2 Copyright (C) 2003-2016 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"
264 #include "gimple-pretty-print.h"
265 #include "fold-const.h"
266 #include "gimplify.h"
267 #include "gimple-iterator.h"
268 #include "gimplify-me.h"
269 #include "tree-cfg.h"
270 #include "tree-ssa-loop-ivopts.h"
271 #include "tree-ssa-loop-manip.h"
272 #include "tree-ssa-loop-niter.h"
273 #include "tree-ssa-loop.h"
274 #include "tree-ssa.h"
276 #include "tree-chrec.h"
277 #include "tree-affine.h"
278 #include "tree-scalar-evolution.h"
279 #include "dumpfile.h"
281 #include "tree-ssa-propagate.h"
282 #include "gimple-fold.h"
284 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
285 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
288 /* The cached information about an SSA name with version NAME_VERSION,
289 claiming that below basic block with index INSTANTIATED_BELOW, the
290 value of the SSA name can be expressed as CHREC. */
292 struct GTY((for_user
)) scev_info_str
{
293 unsigned int name_version
;
294 int instantiated_below
;
298 /* Counters for the scev database. */
299 static unsigned nb_set_scev
= 0;
300 static unsigned nb_get_scev
= 0;
302 /* The following trees are unique elements. Thus the comparison of
303 another element to these elements should be done on the pointer to
304 these trees, and not on their value. */
306 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
307 tree chrec_not_analyzed_yet
;
309 /* Reserved to the cases where the analyzer has detected an
310 undecidable property at compile time. */
311 tree chrec_dont_know
;
313 /* When the analyzer has detected that a property will never
314 happen, then it qualifies it with chrec_known. */
317 struct scev_info_hasher
: ggc_ptr_hash
<scev_info_str
>
319 static hashval_t
hash (scev_info_str
*i
);
320 static bool equal (const scev_info_str
*a
, const scev_info_str
*b
);
323 static GTY (()) hash_table
<scev_info_hasher
> *scalar_evolution_info
;
326 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
328 static inline struct scev_info_str
*
329 new_scev_info_str (basic_block instantiated_below
, tree var
)
331 struct scev_info_str
*res
;
333 res
= ggc_alloc
<scev_info_str
> ();
334 res
->name_version
= SSA_NAME_VERSION (var
);
335 res
->chrec
= chrec_not_analyzed_yet
;
336 res
->instantiated_below
= instantiated_below
->index
;
341 /* Computes a hash function for database element ELT. */
344 scev_info_hasher::hash (scev_info_str
*elt
)
346 return elt
->name_version
^ elt
->instantiated_below
;
349 /* Compares database elements E1 and E2. */
352 scev_info_hasher::equal (const scev_info_str
*elt1
, const scev_info_str
*elt2
)
354 return (elt1
->name_version
== elt2
->name_version
355 && elt1
->instantiated_below
== elt2
->instantiated_below
);
358 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
359 A first query on VAR returns chrec_not_analyzed_yet. */
362 find_var_scev_info (basic_block instantiated_below
, tree var
)
364 struct scev_info_str
*res
;
365 struct scev_info_str tmp
;
367 tmp
.name_version
= SSA_NAME_VERSION (var
);
368 tmp
.instantiated_below
= instantiated_below
->index
;
369 scev_info_str
**slot
= scalar_evolution_info
->find_slot (&tmp
, INSERT
);
372 *slot
= new_scev_info_str (instantiated_below
, var
);
378 /* Return true when CHREC contains symbolic names defined in
382 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
386 if (chrec
== NULL_TREE
)
389 if (is_gimple_min_invariant (chrec
))
392 if (TREE_CODE (chrec
) == SSA_NAME
)
395 loop_p def_loop
, loop
;
397 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
400 def
= SSA_NAME_DEF_STMT (chrec
);
401 def_loop
= loop_containing_stmt (def
);
402 loop
= get_loop (cfun
, loop_nb
);
404 if (def_loop
== NULL
)
407 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
413 n
= TREE_OPERAND_LENGTH (chrec
);
414 for (i
= 0; i
< n
; i
++)
415 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
421 /* Return true when PHI is a loop-phi-node. */
424 loop_phi_node_p (gimple
*phi
)
426 /* The implementation of this function is based on the following
427 property: "all the loop-phi-nodes of a loop are contained in the
428 loop's header basic block". */
430 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
433 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
434 In general, in the case of multivariate evolutions we want to get
435 the evolution in different loops. LOOP specifies the level for
436 which to get the evolution.
440 | for (j = 0; j < 100; j++)
442 | for (k = 0; k < 100; k++)
444 | i = k + j; - Here the value of i is a function of j, k.
446 | ... = i - Here the value of i is a function of j.
448 | ... = i - Here the value of i is a scalar.
454 | i_1 = phi (i_0, i_2)
458 This loop has the same effect as:
459 LOOP_1 has the same effect as:
463 The overall effect of the loop, "i_0 + 20" in the previous example,
464 is obtained by passing in the parameters: LOOP = 1,
465 EVOLUTION_FN = {i_0, +, 2}_1.
469 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
473 if (evolution_fn
== chrec_dont_know
)
474 return chrec_dont_know
;
476 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
478 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
480 if (inner_loop
== loop
481 || flow_loop_nested_p (loop
, inner_loop
))
483 tree nb_iter
= number_of_latch_executions (inner_loop
);
485 if (nb_iter
== chrec_dont_know
)
486 return chrec_dont_know
;
491 /* evolution_fn is the evolution function in LOOP. Get
492 its value in the nb_iter-th iteration. */
493 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
495 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
496 res
= instantiate_parameters (loop
, res
);
498 /* Continue the computation until ending on a parent of LOOP. */
499 return compute_overall_effect_of_inner_loop (loop
, res
);
506 /* If the evolution function is an invariant, there is nothing to do. */
507 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
511 return chrec_dont_know
;
514 /* Associate CHREC to SCALAR. */
517 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
521 if (TREE_CODE (scalar
) != SSA_NAME
)
524 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
528 if (dump_flags
& TDF_SCEV
)
530 fprintf (dump_file
, "(set_scalar_evolution \n");
531 fprintf (dump_file
, " instantiated_below = %d \n",
532 instantiated_below
->index
);
533 fprintf (dump_file
, " (scalar = ");
534 print_generic_expr (dump_file
, scalar
, 0);
535 fprintf (dump_file
, ")\n (scalar_evolution = ");
536 print_generic_expr (dump_file
, chrec
, 0);
537 fprintf (dump_file
, "))\n");
539 if (dump_flags
& TDF_STATS
)
543 *scalar_info
= chrec
;
546 /* Retrieve the chrec associated to SCALAR instantiated below
547 INSTANTIATED_BELOW block. */
550 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
556 if (dump_flags
& TDF_SCEV
)
558 fprintf (dump_file
, "(get_scalar_evolution \n");
559 fprintf (dump_file
, " (scalar = ");
560 print_generic_expr (dump_file
, scalar
, 0);
561 fprintf (dump_file
, ")\n");
563 if (dump_flags
& TDF_STATS
)
567 switch (TREE_CODE (scalar
))
570 res
= *find_var_scev_info (instantiated_below
, scalar
);
580 res
= chrec_not_analyzed_yet
;
584 if (dump_file
&& (dump_flags
& TDF_SCEV
))
586 fprintf (dump_file
, " (scalar_evolution = ");
587 print_generic_expr (dump_file
, res
, 0);
588 fprintf (dump_file
, "))\n");
594 /* Helper function for add_to_evolution. Returns the evolution
595 function for an assignment of the form "a = b + c", where "a" and
596 "b" are on the strongly connected component. CHREC_BEFORE is the
597 information that we already have collected up to this point.
598 TO_ADD is the evolution of "c".
600 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
601 evolution the expression TO_ADD, otherwise construct an evolution
602 part for this loop. */
605 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
608 tree type
, left
, right
;
609 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
611 switch (TREE_CODE (chrec_before
))
613 case POLYNOMIAL_CHREC
:
614 chloop
= get_chrec_loop (chrec_before
);
616 || flow_loop_nested_p (chloop
, loop
))
620 type
= chrec_type (chrec_before
);
622 /* When there is no evolution part in this loop, build it. */
627 right
= SCALAR_FLOAT_TYPE_P (type
)
628 ? build_real (type
, dconst0
)
629 : build_int_cst (type
, 0);
633 var
= CHREC_VARIABLE (chrec_before
);
634 left
= CHREC_LEFT (chrec_before
);
635 right
= CHREC_RIGHT (chrec_before
);
638 to_add
= chrec_convert (type
, to_add
, at_stmt
);
639 right
= chrec_convert_rhs (type
, right
, at_stmt
);
640 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
641 return build_polynomial_chrec (var
, left
, right
);
645 gcc_assert (flow_loop_nested_p (loop
, chloop
));
647 /* Search the evolution in LOOP_NB. */
648 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
650 right
= CHREC_RIGHT (chrec_before
);
651 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
652 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
657 /* These nodes do not depend on a loop. */
658 if (chrec_before
== chrec_dont_know
)
659 return chrec_dont_know
;
662 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
663 return build_polynomial_chrec (loop_nb
, left
, right
);
667 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
670 Description (provided for completeness, for those who read code in
671 a plane, and for my poor 62 bytes brain that would have forgotten
672 all this in the next two or three months):
674 The algorithm of translation of programs from the SSA representation
675 into the chrecs syntax is based on a pattern matching. After having
676 reconstructed the overall tree expression for a loop, there are only
677 two cases that can arise:
679 1. a = loop-phi (init, a + expr)
680 2. a = loop-phi (init, expr)
682 where EXPR is either a scalar constant with respect to the analyzed
683 loop (this is a degree 0 polynomial), or an expression containing
684 other loop-phi definitions (these are higher degree polynomials).
691 | a = phi (init, a + 5)
698 | a = phi (inita, 2 * b + 3)
699 | b = phi (initb, b + 1)
702 For the first case, the semantics of the SSA representation is:
704 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
706 that is, there is a loop index "x" that determines the scalar value
707 of the variable during the loop execution. During the first
708 iteration, the value is that of the initial condition INIT, while
709 during the subsequent iterations, it is the sum of the initial
710 condition with the sum of all the values of EXPR from the initial
711 iteration to the before last considered iteration.
713 For the second case, the semantics of the SSA program is:
715 | a (x) = init, if x = 0;
716 | expr (x - 1), otherwise.
718 The second case corresponds to the PEELED_CHREC, whose syntax is
719 close to the syntax of a loop-phi-node:
721 | phi (init, expr) vs. (init, expr)_x
723 The proof of the translation algorithm for the first case is a
724 proof by structural induction based on the degree of EXPR.
727 When EXPR is a constant with respect to the analyzed loop, or in
728 other words when EXPR is a polynomial of degree 0, the evolution of
729 the variable A in the loop is an affine function with an initial
730 condition INIT, and a step EXPR. In order to show this, we start
731 from the semantics of the SSA representation:
733 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
735 and since "expr (j)" is a constant with respect to "j",
737 f (x) = init + x * expr
739 Finally, based on the semantics of the pure sum chrecs, by
740 identification we get the corresponding chrecs syntax:
742 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
743 f (x) -> {init, +, expr}_x
746 Suppose that EXPR is a polynomial of degree N with respect to the
747 analyzed loop_x for which we have already determined that it is
748 written under the chrecs syntax:
750 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
752 We start from the semantics of the SSA program:
754 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
756 | f (x) = init + \sum_{j = 0}^{x - 1}
757 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
759 | f (x) = init + \sum_{j = 0}^{x - 1}
760 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
762 | f (x) = init + \sum_{k = 0}^{n - 1}
763 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
765 | f (x) = init + \sum_{k = 0}^{n - 1}
766 | (b_k * \binom{x}{k + 1})
768 | f (x) = init + b_0 * \binom{x}{1} + ...
769 | + b_{n-1} * \binom{x}{n}
771 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
772 | + b_{n-1} * \binom{x}{n}
775 And finally from the definition of the chrecs syntax, we identify:
776 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
778 This shows the mechanism that stands behind the add_to_evolution
779 function. An important point is that the use of symbolic
780 parameters avoids the need of an analysis schedule.
787 | a = phi (inita, a + 2 + b)
788 | b = phi (initb, b + 1)
791 When analyzing "a", the algorithm keeps "b" symbolically:
793 | a -> {inita, +, 2 + b}_1
795 Then, after instantiation, the analyzer ends on the evolution:
797 | a -> {inita, +, 2 + initb, +, 1}_1
802 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
803 tree to_add
, gimple
*at_stmt
)
805 tree type
= chrec_type (to_add
);
806 tree res
= NULL_TREE
;
808 if (to_add
== NULL_TREE
)
811 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
812 instantiated at this point. */
813 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
814 /* This should not happen. */
815 return chrec_dont_know
;
817 if (dump_file
&& (dump_flags
& TDF_SCEV
))
819 fprintf (dump_file
, "(add_to_evolution \n");
820 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
821 fprintf (dump_file
, " (chrec_before = ");
822 print_generic_expr (dump_file
, chrec_before
, 0);
823 fprintf (dump_file
, ")\n (to_add = ");
824 print_generic_expr (dump_file
, to_add
, 0);
825 fprintf (dump_file
, ")\n");
828 if (code
== MINUS_EXPR
)
829 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
830 ? build_real (type
, dconstm1
)
831 : build_int_cst_type (type
, -1));
833 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
835 if (dump_file
&& (dump_flags
& TDF_SCEV
))
837 fprintf (dump_file
, " (res = ");
838 print_generic_expr (dump_file
, res
, 0);
839 fprintf (dump_file
, "))\n");
847 /* This section selects the loops that will be good candidates for the
848 scalar evolution analysis. For the moment, greedily select all the
849 loop nests we could analyze. */
851 /* For a loop with a single exit edge, return the COND_EXPR that
852 guards the exit edge. If the expression is too difficult to
853 analyze, then give up. */
856 get_loop_exit_condition (const struct loop
*loop
)
859 edge exit_edge
= single_exit (loop
);
861 if (dump_file
&& (dump_flags
& TDF_SCEV
))
862 fprintf (dump_file
, "(get_loop_exit_condition \n ");
868 stmt
= last_stmt (exit_edge
->src
);
869 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
873 if (dump_file
&& (dump_flags
& TDF_SCEV
))
875 print_gimple_stmt (dump_file
, res
, 0, 0);
876 fprintf (dump_file
, ")\n");
883 /* Depth first search algorithm. */
892 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
*, gphi
*,
895 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
896 Return true if the strongly connected component has been found. */
899 follow_ssa_edge_binary (struct loop
*loop
, gimple
*at_stmt
,
900 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
901 gphi
*halting_phi
, tree
*evolution_of_loop
,
904 t_bool res
= t_false
;
909 case POINTER_PLUS_EXPR
:
911 if (TREE_CODE (rhs0
) == SSA_NAME
)
913 if (TREE_CODE (rhs1
) == SSA_NAME
)
915 /* Match an assignment under the form:
918 /* We want only assignments of form "name + name" contribute to
919 LIMIT, as the other cases do not necessarily contribute to
920 the complexity of the expression. */
923 evol
= *evolution_of_loop
;
924 evol
= add_to_evolution
926 chrec_convert (type
, evol
, at_stmt
),
927 code
, rhs1
, at_stmt
);
928 res
= follow_ssa_edge
929 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
931 *evolution_of_loop
= evol
;
932 else if (res
== t_false
)
934 *evolution_of_loop
= add_to_evolution
936 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
937 code
, rhs0
, at_stmt
);
938 res
= follow_ssa_edge
939 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
940 evolution_of_loop
, limit
);
943 else if (res
== t_dont_know
)
944 *evolution_of_loop
= chrec_dont_know
;
947 else if (res
== t_dont_know
)
948 *evolution_of_loop
= chrec_dont_know
;
953 /* Match an assignment under the form:
955 *evolution_of_loop
= add_to_evolution
956 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
958 code
, rhs1
, at_stmt
);
959 res
= follow_ssa_edge
960 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
961 evolution_of_loop
, limit
);
964 else if (res
== t_dont_know
)
965 *evolution_of_loop
= chrec_dont_know
;
969 else if (TREE_CODE (rhs1
) == SSA_NAME
)
971 /* Match an assignment under the form:
973 *evolution_of_loop
= add_to_evolution
974 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
976 code
, rhs0
, at_stmt
);
977 res
= follow_ssa_edge
978 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
979 evolution_of_loop
, limit
);
982 else if (res
== t_dont_know
)
983 *evolution_of_loop
= chrec_dont_know
;
987 /* Otherwise, match an assignment under the form:
989 /* And there is nothing to do. */
994 /* This case is under the form "opnd0 = rhs0 - rhs1". */
995 if (TREE_CODE (rhs0
) == SSA_NAME
)
997 /* Match an assignment under the form:
1000 /* We want only assignments of form "name - name" contribute to
1001 LIMIT, as the other cases do not necessarily contribute to
1002 the complexity of the expression. */
1003 if (TREE_CODE (rhs1
) == SSA_NAME
)
1006 *evolution_of_loop
= add_to_evolution
1007 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1008 MINUS_EXPR
, rhs1
, at_stmt
);
1009 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1010 evolution_of_loop
, limit
);
1013 else if (res
== t_dont_know
)
1014 *evolution_of_loop
= chrec_dont_know
;
1017 /* Otherwise, match an assignment under the form:
1019 /* And there is nothing to do. */
1030 /* Follow the ssa edge into the expression EXPR.
1031 Return true if the strongly connected component has been found. */
1034 follow_ssa_edge_expr (struct loop
*loop
, gimple
*at_stmt
, tree expr
,
1035 gphi
*halting_phi
, tree
*evolution_of_loop
,
1038 enum tree_code code
= TREE_CODE (expr
);
1039 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1042 /* The EXPR is one of the following cases:
1046 - a POINTER_PLUS_EXPR,
1049 - other cases are not yet handled. */
1054 /* This assignment is under the form "a_1 = (cast) rhs. */
1055 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1056 halting_phi
, evolution_of_loop
, limit
);
1057 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1061 /* This assignment is under the form "a_1 = 7". */
1066 /* This assignment is under the form: "a_1 = b_2". */
1067 res
= follow_ssa_edge
1068 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1071 case POINTER_PLUS_EXPR
:
1074 /* This case is under the form "rhs0 +- rhs1". */
1075 rhs0
= TREE_OPERAND (expr
, 0);
1076 rhs1
= TREE_OPERAND (expr
, 1);
1077 type
= TREE_TYPE (rhs0
);
1078 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1079 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1080 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1081 halting_phi
, evolution_of_loop
, limit
);
1085 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1086 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1088 expr
= TREE_OPERAND (expr
, 0);
1089 rhs0
= TREE_OPERAND (expr
, 0);
1090 rhs1
= TREE_OPERAND (expr
, 1);
1091 type
= TREE_TYPE (rhs0
);
1092 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1093 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1094 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1095 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1096 halting_phi
, evolution_of_loop
, limit
);
1103 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1104 It must be handled as a copy assignment of the form a_1 = a_2. */
1105 rhs0
= ASSERT_EXPR_VAR (expr
);
1106 if (TREE_CODE (rhs0
) == SSA_NAME
)
1107 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1108 halting_phi
, evolution_of_loop
, limit
);
1121 /* Follow the ssa edge into the right hand side of an assignment STMT.
1122 Return true if the strongly connected component has been found. */
1125 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple
*stmt
,
1126 gphi
*halting_phi
, tree
*evolution_of_loop
,
1129 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1130 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1136 /* This assignment is under the form "a_1 = (cast) rhs. */
1137 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1138 halting_phi
, evolution_of_loop
, limit
);
1139 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1142 case POINTER_PLUS_EXPR
:
1145 rhs1
= gimple_assign_rhs1 (stmt
);
1146 rhs2
= gimple_assign_rhs2 (stmt
);
1147 type
= TREE_TYPE (rhs1
);
1148 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1149 halting_phi
, evolution_of_loop
, limit
);
1153 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1154 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1155 halting_phi
, evolution_of_loop
, limit
);
1164 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1167 backedge_phi_arg_p (gphi
*phi
, int i
)
1169 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1171 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1172 about updating it anywhere, and this should work as well most of the
1174 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1180 /* Helper function for one branch of the condition-phi-node. Return
1181 true if the strongly connected component has been found following
1184 static inline t_bool
1185 follow_ssa_edge_in_condition_phi_branch (int i
,
1187 gphi
*condition_phi
,
1189 tree
*evolution_of_branch
,
1190 tree init_cond
, int limit
)
1192 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1193 *evolution_of_branch
= chrec_dont_know
;
1195 /* Do not follow back edges (they must belong to an irreducible loop, which
1196 we really do not want to worry about). */
1197 if (backedge_phi_arg_p (condition_phi
, i
))
1200 if (TREE_CODE (branch
) == SSA_NAME
)
1202 *evolution_of_branch
= init_cond
;
1203 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1204 evolution_of_branch
, limit
);
1207 /* This case occurs when one of the condition branches sets
1208 the variable to a constant: i.e. a phi-node like
1209 "a_2 = PHI <a_7(5), 2(6)>;".
1211 FIXME: This case have to be refined correctly:
1212 in some cases it is possible to say something better than
1213 chrec_dont_know, for example using a wrap-around notation. */
1217 /* This function merges the branches of a condition-phi-node in a
1221 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1222 gphi
*condition_phi
,
1224 tree
*evolution_of_loop
, int limit
)
1227 tree init
= *evolution_of_loop
;
1228 tree evolution_of_branch
;
1229 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1231 &evolution_of_branch
,
1233 if (res
== t_false
|| res
== t_dont_know
)
1236 *evolution_of_loop
= evolution_of_branch
;
1238 n
= gimple_phi_num_args (condition_phi
);
1239 for (i
= 1; i
< n
; i
++)
1241 /* Quickly give up when the evolution of one of the branches is
1243 if (*evolution_of_loop
== chrec_dont_know
)
1246 /* Increase the limit by the PHI argument number to avoid exponential
1247 time and memory complexity. */
1248 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1250 &evolution_of_branch
,
1252 if (res
== t_false
|| res
== t_dont_know
)
1255 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1256 evolution_of_branch
);
1262 /* Follow an SSA edge in an inner loop. It computes the overall
1263 effect of the loop, and following the symbolic initial conditions,
1264 it follows the edges in the parent loop. The inner loop is
1265 considered as a single statement. */
1268 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1269 gphi
*loop_phi_node
,
1271 tree
*evolution_of_loop
, int limit
)
1273 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1274 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1276 /* Sometimes, the inner loop is too difficult to analyze, and the
1277 result of the analysis is a symbolic parameter. */
1278 if (ev
== PHI_RESULT (loop_phi_node
))
1280 t_bool res
= t_false
;
1281 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1283 for (i
= 0; i
< n
; i
++)
1285 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1288 /* Follow the edges that exit the inner loop. */
1289 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1290 if (!flow_bb_inside_loop_p (loop
, bb
))
1291 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1293 evolution_of_loop
, limit
);
1298 /* If the path crosses this loop-phi, give up. */
1300 *evolution_of_loop
= chrec_dont_know
;
1305 /* Otherwise, compute the overall effect of the inner loop. */
1306 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1307 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1308 evolution_of_loop
, limit
);
1311 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1312 path that is analyzed on the return walk. */
1315 follow_ssa_edge (struct loop
*loop
, gimple
*def
, gphi
*halting_phi
,
1316 tree
*evolution_of_loop
, int limit
)
1318 struct loop
*def_loop
;
1320 if (gimple_nop_p (def
))
1323 /* Give up if the path is longer than the MAX that we allow. */
1324 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1327 def_loop
= loop_containing_stmt (def
);
1329 switch (gimple_code (def
))
1332 if (!loop_phi_node_p (def
))
1333 /* DEF is a condition-phi-node. Follow the branches, and
1334 record their evolutions. Finally, merge the collected
1335 information and set the approximation to the main
1337 return follow_ssa_edge_in_condition_phi
1338 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
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
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1363 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1364 evolution_of_loop
, limit
);
1367 /* At this level of abstraction, the program is just a set
1368 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1369 other node to be handled. */
1375 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1376 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1378 # i_17 = PHI <i_13(5), 0(3)>
1379 # _20 = PHI <_5(5), start_4(D)(3)>
1382 _5 = start_4(D) + i_13;
1384 Though variable _20 appears as a PEELED_CHREC in the form of
1385 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1390 simplify_peeled_chrec (struct loop
*loop
, tree arg
, tree init_cond
)
1392 aff_tree aff1
, aff2
;
1393 tree ev
, left
, right
, type
, step_val
;
1394 hash_map
<tree
, name_expansion
*> *peeled_chrec_map
= NULL
;
1396 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1397 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1398 return chrec_dont_know
;
1400 left
= CHREC_LEFT (ev
);
1401 right
= CHREC_RIGHT (ev
);
1402 type
= TREE_TYPE (left
);
1403 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1405 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1406 if "left" equals to "init + right". */
1407 if (operand_equal_p (left
, step_val
, 0))
1409 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1410 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1412 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1415 /* Try harder to check if they are equal. */
1416 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1417 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1418 free_affine_expand_cache (&peeled_chrec_map
);
1419 aff_combination_scale (&aff2
, -1);
1420 aff_combination_add (&aff1
, &aff2
);
1422 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1423 if "left" equals to "init + right". */
1424 if (aff_combination_zero_p (&aff1
))
1426 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1427 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1429 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1431 return chrec_dont_know
;
1434 /* Given a LOOP_PHI_NODE, this function determines the evolution
1435 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1438 analyze_evolution_in_loop (gphi
*loop_phi_node
,
1441 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1442 tree evolution_function
= chrec_not_analyzed_yet
;
1443 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1445 static bool simplify_peeled_chrec_p
= true;
1447 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1449 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1450 fprintf (dump_file
, " (loop_phi_node = ");
1451 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1452 fprintf (dump_file
, ")\n");
1455 for (i
= 0; i
< n
; i
++)
1457 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1462 /* Select the edges that enter the loop body. */
1463 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1464 if (!flow_bb_inside_loop_p (loop
, bb
))
1467 if (TREE_CODE (arg
) == SSA_NAME
)
1471 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1473 /* Pass in the initial condition to the follow edge function. */
1475 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1477 /* If ev_fn has no evolution in the inner loop, and the
1478 init_cond is not equal to ev_fn, then we have an
1479 ambiguity between two possible values, as we cannot know
1480 the number of iterations at this point. */
1481 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1482 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1483 && !operand_equal_p (init_cond
, ev_fn
, 0))
1484 ev_fn
= chrec_dont_know
;
1489 /* When it is impossible to go back on the same
1490 loop_phi_node by following the ssa edges, the
1491 evolution is represented by a peeled chrec, i.e. the
1492 first iteration, EV_FN has the value INIT_COND, then
1493 all the other iterations it has the value of ARG.
1494 For the moment, PEELED_CHREC nodes are not built. */
1497 ev_fn
= chrec_dont_know
;
1498 /* Try to recognize POLYNOMIAL_CHREC which appears in
1499 the form of PEELED_CHREC, but guard the process with
1500 a bool variable to keep the analyzer from infinite
1501 recurrence for real PEELED_RECs. */
1502 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1504 simplify_peeled_chrec_p
= false;
1505 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1506 simplify_peeled_chrec_p
= true;
1510 /* When there are multiple back edges of the loop (which in fact never
1511 happens currently, but nevertheless), merge their evolutions. */
1512 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1514 if (evolution_function
== chrec_dont_know
)
1518 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1520 fprintf (dump_file
, " (evolution_function = ");
1521 print_generic_expr (dump_file
, evolution_function
, 0);
1522 fprintf (dump_file
, "))\n");
1525 return evolution_function
;
1528 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1529 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1532 follow_copies_to_constant (tree var
)
1535 while (TREE_CODE (res
) == SSA_NAME
)
1537 gimple
*def
= SSA_NAME_DEF_STMT (res
);
1538 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
1540 if (tree rhs
= degenerate_phi_result (phi
))
1545 else if (gimple_assign_single_p (def
))
1546 /* Will exit loop if not an SSA_NAME. */
1547 res
= gimple_assign_rhs1 (def
);
1551 if (CONSTANT_CLASS_P (res
))
1556 /* Given a loop-phi-node, return the initial conditions of the
1557 variable on entry of the loop. When the CCP has propagated
1558 constants into the loop-phi-node, the initial condition is
1559 instantiated, otherwise the initial condition is kept symbolic.
1560 This analyzer does not analyze the evolution outside the current
1561 loop, and leaves this task to the on-demand tree reconstructor. */
1564 analyze_initial_condition (gphi
*loop_phi_node
)
1567 tree init_cond
= chrec_not_analyzed_yet
;
1568 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1570 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1572 fprintf (dump_file
, "(analyze_initial_condition \n");
1573 fprintf (dump_file
, " (loop_phi_node = \n");
1574 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1575 fprintf (dump_file
, ")\n");
1578 n
= gimple_phi_num_args (loop_phi_node
);
1579 for (i
= 0; i
< n
; i
++)
1581 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1582 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1584 /* When the branch is oriented to the loop's body, it does
1585 not contribute to the initial condition. */
1586 if (flow_bb_inside_loop_p (loop
, bb
))
1589 if (init_cond
== chrec_not_analyzed_yet
)
1595 if (TREE_CODE (branch
) == SSA_NAME
)
1597 init_cond
= chrec_dont_know
;
1601 init_cond
= chrec_merge (init_cond
, branch
);
1604 /* Ooops -- a loop without an entry??? */
1605 if (init_cond
== chrec_not_analyzed_yet
)
1606 init_cond
= chrec_dont_know
;
1608 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1609 to not miss important early loop unrollings. */
1610 init_cond
= follow_copies_to_constant (init_cond
);
1612 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1614 fprintf (dump_file
, " (init_cond = ");
1615 print_generic_expr (dump_file
, init_cond
, 0);
1616 fprintf (dump_file
, "))\n");
1622 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1625 interpret_loop_phi (struct loop
*loop
, gphi
*loop_phi_node
)
1628 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1631 if (phi_loop
!= loop
)
1633 struct loop
*subloop
;
1634 tree evolution_fn
= analyze_scalar_evolution
1635 (phi_loop
, PHI_RESULT (loop_phi_node
));
1637 /* Dive one level deeper. */
1638 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1640 /* Interpret the subloop. */
1641 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1645 /* Otherwise really interpret the loop phi. */
1646 init_cond
= analyze_initial_condition (loop_phi_node
);
1647 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1649 /* Verify we maintained the correct initial condition throughout
1650 possible conversions in the SSA chain. */
1651 if (res
!= chrec_dont_know
)
1653 tree new_init
= res
;
1654 if (CONVERT_EXPR_P (res
)
1655 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1656 new_init
= fold_convert (TREE_TYPE (res
),
1657 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1658 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1659 new_init
= CHREC_LEFT (res
);
1660 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1661 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1662 || !operand_equal_p (init_cond
, new_init
, 0))
1663 return chrec_dont_know
;
1669 /* This function merges the branches of a condition-phi-node,
1670 contained in the outermost loop, and whose arguments are already
1674 interpret_condition_phi (struct loop
*loop
, gphi
*condition_phi
)
1676 int i
, n
= gimple_phi_num_args (condition_phi
);
1677 tree res
= chrec_not_analyzed_yet
;
1679 for (i
= 0; i
< n
; i
++)
1683 if (backedge_phi_arg_p (condition_phi
, i
))
1685 res
= chrec_dont_know
;
1689 branch_chrec
= analyze_scalar_evolution
1690 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1692 res
= chrec_merge (res
, branch_chrec
);
1693 if (res
== chrec_dont_know
)
1700 /* Interpret the operation RHS1 OP RHS2. If we didn't
1701 analyze this node before, follow the definitions until ending
1702 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1703 return path, this function propagates evolutions (ala constant copy
1704 propagation). OPND1 is not a GIMPLE expression because we could
1705 analyze the effect of an inner loop: see interpret_loop_phi. */
1708 interpret_rhs_expr (struct loop
*loop
, gimple
*at_stmt
,
1709 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1711 tree res
, chrec1
, chrec2
, ctype
;
1714 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1716 if (is_gimple_min_invariant (rhs1
))
1717 return chrec_convert (type
, rhs1
, at_stmt
);
1719 if (code
== SSA_NAME
)
1720 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1723 if (code
== ASSERT_EXPR
)
1725 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1726 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1734 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1735 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1738 HOST_WIDE_INT bitsize
, bitpos
;
1739 int unsignedp
, reversep
;
1745 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1746 &bitsize
, &bitpos
, &offset
, &mode
,
1747 &unsignedp
, &reversep
, &volatilep
,
1750 if (TREE_CODE (base
) == MEM_REF
)
1752 rhs2
= TREE_OPERAND (base
, 1);
1753 rhs1
= TREE_OPERAND (base
, 0);
1755 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1756 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1757 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1758 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1759 chrec1
= instantiate_parameters (loop
, chrec1
);
1760 chrec2
= instantiate_parameters (loop
, chrec2
);
1761 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1765 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1766 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1770 if (offset
!= NULL_TREE
)
1772 chrec2
= analyze_scalar_evolution (loop
, offset
);
1773 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1774 chrec2
= instantiate_parameters (loop
, chrec2
);
1775 res
= chrec_fold_plus (type
, res
, chrec2
);
1780 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1782 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1783 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1784 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1785 chrec3
= instantiate_parameters (loop
, chrec3
);
1786 res
= chrec_fold_plus (type
, res
, chrec3
);
1790 res
= chrec_dont_know
;
1793 case POINTER_PLUS_EXPR
:
1794 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1795 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1796 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1797 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1798 chrec1
= instantiate_parameters (loop
, chrec1
);
1799 chrec2
= instantiate_parameters (loop
, chrec2
);
1800 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1804 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1805 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1807 /* When the stmt is conditionally executed re-write the CHREC
1808 into a form that has well-defined behavior on overflow. */
1810 && INTEGRAL_TYPE_P (type
)
1811 && ! TYPE_OVERFLOW_WRAPS (type
)
1812 && ! dominated_by_p (CDI_DOMINATORS
, loop
->latch
,
1813 gimple_bb (at_stmt
)))
1814 ctype
= unsigned_type_for (type
);
1815 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1816 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1817 chrec1
= instantiate_parameters (loop
, chrec1
);
1818 chrec2
= instantiate_parameters (loop
, chrec2
);
1819 res
= chrec_fold_plus (ctype
, chrec1
, chrec2
);
1821 res
= chrec_convert (type
, res
, at_stmt
);
1825 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1826 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1828 /* When the stmt is conditionally executed re-write the CHREC
1829 into a form that has well-defined behavior on overflow. */
1831 && INTEGRAL_TYPE_P (type
)
1832 && ! TYPE_OVERFLOW_WRAPS (type
)
1833 && ! dominated_by_p (CDI_DOMINATORS
,
1834 loop
->latch
, gimple_bb (at_stmt
)))
1835 ctype
= unsigned_type_for (type
);
1836 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1837 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1838 chrec1
= instantiate_parameters (loop
, chrec1
);
1839 chrec2
= instantiate_parameters (loop
, chrec2
);
1840 res
= chrec_fold_minus (ctype
, chrec1
, chrec2
);
1842 res
= chrec_convert (type
, res
, at_stmt
);
1846 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1848 /* When the stmt is conditionally executed re-write the CHREC
1849 into a form that has well-defined behavior on overflow. */
1851 && INTEGRAL_TYPE_P (type
)
1852 && ! TYPE_OVERFLOW_WRAPS (type
)
1853 && ! dominated_by_p (CDI_DOMINATORS
,
1854 loop
->latch
, gimple_bb (at_stmt
)))
1855 ctype
= unsigned_type_for (type
);
1856 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1857 /* TYPE may be integer, real or complex, so use fold_convert. */
1858 chrec1
= instantiate_parameters (loop
, chrec1
);
1859 res
= chrec_fold_multiply (ctype
, chrec1
,
1860 fold_convert (ctype
, integer_minus_one_node
));
1862 res
= chrec_convert (type
, res
, at_stmt
);
1866 /* Handle ~X as -1 - X. */
1867 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1868 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1869 chrec1
= instantiate_parameters (loop
, chrec1
);
1870 res
= chrec_fold_minus (type
,
1871 fold_convert (type
, integer_minus_one_node
),
1876 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1877 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1879 /* When the stmt is conditionally executed re-write the CHREC
1880 into a form that has well-defined behavior on overflow. */
1882 && INTEGRAL_TYPE_P (type
)
1883 && ! TYPE_OVERFLOW_WRAPS (type
)
1884 && ! dominated_by_p (CDI_DOMINATORS
,
1885 loop
->latch
, gimple_bb (at_stmt
)))
1886 ctype
= unsigned_type_for (type
);
1887 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1888 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1889 chrec1
= instantiate_parameters (loop
, chrec1
);
1890 chrec2
= instantiate_parameters (loop
, chrec2
);
1891 res
= chrec_fold_multiply (ctype
, chrec1
, chrec2
);
1893 res
= chrec_convert (type
, res
, at_stmt
);
1898 /* Handle A<<B as A * (1<<B). */
1899 tree uns
= unsigned_type_for (type
);
1900 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1901 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1902 chrec1
= chrec_convert (uns
, chrec1
, at_stmt
);
1903 chrec1
= instantiate_parameters (loop
, chrec1
);
1904 chrec2
= instantiate_parameters (loop
, chrec2
);
1906 tree one
= build_int_cst (uns
, 1);
1907 chrec2
= fold_build2 (LSHIFT_EXPR
, uns
, one
, chrec2
);
1908 res
= chrec_fold_multiply (uns
, chrec1
, chrec2
);
1909 res
= chrec_convert (type
, res
, at_stmt
);
1914 /* In case we have a truncation of a widened operation that in
1915 the truncated type has undefined overflow behavior analyze
1916 the operation done in an unsigned type of the same precision
1917 as the final truncation. We cannot derive a scalar evolution
1918 for the widened operation but for the truncated result. */
1919 if (TREE_CODE (type
) == INTEGER_TYPE
1920 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1921 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1922 && TYPE_OVERFLOW_UNDEFINED (type
)
1923 && TREE_CODE (rhs1
) == SSA_NAME
1924 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1925 && is_gimple_assign (def
)
1926 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1927 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1929 tree utype
= unsigned_type_for (type
);
1930 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1931 gimple_assign_rhs1 (def
),
1932 gimple_assign_rhs_code (def
),
1933 gimple_assign_rhs2 (def
));
1936 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1937 res
= chrec_convert (type
, chrec1
, at_stmt
);
1941 res
= chrec_dont_know
;
1948 /* Interpret the expression EXPR. */
1951 interpret_expr (struct loop
*loop
, gimple
*at_stmt
, tree expr
)
1953 enum tree_code code
;
1954 tree type
= TREE_TYPE (expr
), op0
, op1
;
1956 if (automatically_generated_chrec_p (expr
))
1959 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1960 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1961 return chrec_dont_know
;
1963 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1965 return interpret_rhs_expr (loop
, at_stmt
, type
,
1969 /* Interpret the rhs of the assignment STMT. */
1972 interpret_gimple_assign (struct loop
*loop
, gimple
*stmt
)
1974 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1975 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1977 return interpret_rhs_expr (loop
, stmt
, type
,
1978 gimple_assign_rhs1 (stmt
), code
,
1979 gimple_assign_rhs2 (stmt
));
1984 /* This section contains all the entry points:
1985 - number_of_iterations_in_loop,
1986 - analyze_scalar_evolution,
1987 - instantiate_parameters.
1990 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1991 common ancestor of DEF_LOOP and USE_LOOP. */
1994 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1995 struct loop
*def_loop
,
2001 if (def_loop
== wrto_loop
)
2004 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
2005 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
2007 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
2010 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
2013 /* Helper recursive function. */
2016 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
2018 tree type
= TREE_TYPE (var
);
2021 struct loop
*def_loop
;
2023 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
2024 return chrec_dont_know
;
2026 if (TREE_CODE (var
) != SSA_NAME
)
2027 return interpret_expr (loop
, NULL
, var
);
2029 def
= SSA_NAME_DEF_STMT (var
);
2030 bb
= gimple_bb (def
);
2031 def_loop
= bb
? bb
->loop_father
: NULL
;
2034 || !flow_bb_inside_loop_p (loop
, bb
))
2036 /* Keep symbolic form, but look through obvious copies for constants. */
2037 res
= follow_copies_to_constant (var
);
2041 if (res
!= chrec_not_analyzed_yet
)
2043 if (loop
!= bb
->loop_father
)
2044 res
= compute_scalar_evolution_in_loop
2045 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
2050 if (loop
!= def_loop
)
2052 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
2053 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
2058 switch (gimple_code (def
))
2061 res
= interpret_gimple_assign (loop
, def
);
2065 if (loop_phi_node_p (def
))
2066 res
= interpret_loop_phi (loop
, as_a
<gphi
*> (def
));
2068 res
= interpret_condition_phi (loop
, as_a
<gphi
*> (def
));
2072 res
= chrec_dont_know
;
2078 /* Keep the symbolic form. */
2079 if (res
== chrec_dont_know
)
2082 if (loop
== def_loop
)
2083 set_scalar_evolution (block_before_loop (loop
), var
, res
);
2088 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2089 LOOP. LOOP is the loop in which the variable is used.
2091 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2092 pointer to the statement that uses this variable, in order to
2093 determine the evolution function of the variable, use the following
2096 loop_p loop = loop_containing_stmt (stmt);
2097 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2098 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2102 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2106 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2108 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2109 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2110 fprintf (dump_file
, " (scalar = ");
2111 print_generic_expr (dump_file
, var
, 0);
2112 fprintf (dump_file
, ")\n");
2115 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2116 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
2118 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2119 fprintf (dump_file
, ")\n");
2124 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2127 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
2129 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2132 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2133 WRTO_LOOP (which should be a superloop of USE_LOOP)
2135 FOLDED_CASTS is set to true if resolve_mixers used
2136 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2137 at the moment in order to keep things simple).
2139 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2142 for (i = 0; i < 100; i++) -- loop 1
2144 for (j = 0; j < 100; j++) -- loop 2
2151 for (t = 0; t < 100; t++) -- loop 3
2158 Both k1 and k2 are invariants in loop3, thus
2159 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2160 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2162 As they are invariant, it does not matter whether we consider their
2163 usage in loop 3 or loop 2, hence
2164 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2165 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2166 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2167 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2169 Similarly for their evolutions with respect to loop 1. The values of K2
2170 in the use in loop 2 vary independently on loop 1, thus we cannot express
2171 the evolution with respect to loop 1:
2172 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2173 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2174 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2175 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2177 The value of k2 in the use in loop 1 is known, though:
2178 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2179 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2183 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2184 tree version
, bool *folded_casts
)
2187 tree ev
= version
, tmp
;
2189 /* We cannot just do
2191 tmp = analyze_scalar_evolution (use_loop, version);
2192 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2194 as resolve_mixers would query the scalar evolution with respect to
2195 wrto_loop. For example, in the situation described in the function
2196 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2199 analyze_scalar_evolution (use_loop, version) = k2
2201 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2202 k2 in loop 1 is 100, which is a wrong result, since we are interested
2203 in the value in loop 3.
2205 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2206 each time checking that there is no evolution in the inner loop. */
2209 *folded_casts
= false;
2212 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2213 ev
= resolve_mixers (use_loop
, tmp
, folded_casts
);
2215 if (use_loop
== wrto_loop
)
2218 /* If the value of the use changes in the inner loop, we cannot express
2219 its value in the outer loop (we might try to return interval chrec,
2220 but we do not have a user for it anyway) */
2221 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2223 return chrec_dont_know
;
2225 use_loop
= loop_outer (use_loop
);
2230 /* Hashtable helpers for a temporary hash-table used when
2231 instantiating a CHREC or resolving mixers. For this use
2232 instantiated_below is always the same. */
2234 struct instantiate_cache_type
2237 vec
<scev_info_str
> entries
;
2239 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2240 ~instantiate_cache_type ();
2241 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2242 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2245 instantiate_cache_type::~instantiate_cache_type ()
2254 /* Cache to avoid infinite recursion when instantiating an SSA name.
2255 Live during the outermost instantiate_scev or resolve_mixers call. */
2256 static instantiate_cache_type
*global_cache
;
2258 /* Computes a hash function for database element ELT. */
2260 static inline hashval_t
2261 hash_idx_scev_info (const void *elt_
)
2263 unsigned idx
= ((size_t) elt_
) - 2;
2264 return scev_info_hasher::hash (&global_cache
->entries
[idx
]);
2267 /* Compares database elements E1 and E2. */
2270 eq_idx_scev_info (const void *e1
, const void *e2
)
2272 unsigned idx1
= ((size_t) e1
) - 2;
2273 return scev_info_hasher::equal (&global_cache
->entries
[idx1
],
2274 (const scev_info_str
*) e2
);
2277 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2280 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2281 tree name
, basic_block instantiate_below
)
2285 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2286 cache
.entries
.create (10);
2290 e
.name_version
= SSA_NAME_VERSION (name
);
2291 e
.instantiated_below
= instantiate_below
->index
;
2292 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2293 scev_info_hasher::hash (&e
), INSERT
);
2296 e
.chrec
= chrec_not_analyzed_yet
;
2297 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2298 cache
.entries
.safe_push (e
);
2301 return ((size_t)*slot
) - 2;
2305 /* Return the closed_loop_phi node for VAR. If there is none, return
2309 loop_closed_phi_def (tree var
)
2316 if (var
== NULL_TREE
2317 || TREE_CODE (var
) != SSA_NAME
)
2320 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2321 exit
= single_exit (loop
);
2325 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2328 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2329 return PHI_RESULT (phi
);
2335 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2338 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2339 and EVOLUTION_LOOP, that were left under a symbolic form.
2341 CHREC is an SSA_NAME to be instantiated.
2343 CACHE is the cache of already instantiated values.
2345 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2346 conversions that may wrap in signed/pointer type are folded, as long
2347 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2348 then we don't do such fold.
2350 SIZE_EXPR is used for computing the size of the expression to be
2351 instantiated, and to stop if it exceeds some limit. */
2354 instantiate_scev_name (basic_block instantiate_below
,
2355 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2357 bool *fold_conversions
,
2361 struct loop
*def_loop
;
2362 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2364 /* A parameter (or loop invariant and we do not want to include
2365 evolutions in outer loops), nothing to do. */
2367 || loop_depth (def_bb
->loop_father
) == 0
2368 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2371 /* We cache the value of instantiated variable to avoid exponential
2372 time complexity due to reevaluations. We also store the convenient
2373 value in the cache in order to prevent infinite recursion -- we do
2374 not want to instantiate the SSA_NAME if it is in a mixer
2375 structure. This is used for avoiding the instantiation of
2376 recursively defined functions, such as:
2378 | a_2 -> {0, +, 1, +, a_2}_1 */
2380 unsigned si
= get_instantiated_value_entry (*global_cache
,
2381 chrec
, instantiate_below
);
2382 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2383 return global_cache
->get (si
);
2385 /* On recursion return chrec_dont_know. */
2386 global_cache
->set (si
, chrec_dont_know
);
2388 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2390 /* If the analysis yields a parametric chrec, instantiate the
2392 res
= analyze_scalar_evolution (def_loop
, chrec
);
2394 /* Don't instantiate default definitions. */
2395 if (TREE_CODE (res
) == SSA_NAME
2396 && SSA_NAME_IS_DEFAULT_DEF (res
))
2399 /* Don't instantiate loop-closed-ssa phi nodes. */
2400 else if (TREE_CODE (res
) == SSA_NAME
2401 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2402 > loop_depth (def_loop
))
2405 res
= loop_closed_phi_def (chrec
);
2409 /* When there is no loop_closed_phi_def, it means that the
2410 variable is not used after the loop: try to still compute the
2411 value of the variable when exiting the loop. */
2412 if (res
== NULL_TREE
)
2414 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2415 res
= analyze_scalar_evolution (loop
, chrec
);
2416 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2417 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2419 fold_conversions
, size_expr
);
2421 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2422 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2423 res
= chrec_dont_know
;
2426 else if (res
!= chrec_dont_know
)
2429 && def_bb
->loop_father
!= inner_loop
2430 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2431 /* ??? We could try to compute the overall effect of the loop here. */
2432 res
= chrec_dont_know
;
2434 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2436 fold_conversions
, size_expr
);
2439 /* Store the correct value to the cache. */
2440 global_cache
->set (si
, res
);
2444 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2445 and EVOLUTION_LOOP, that were left under a symbolic form.
2447 CHREC is a polynomial chain of recurrence to be instantiated.
2449 CACHE is the cache of already instantiated values.
2451 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2452 conversions that may wrap in signed/pointer type are folded, as long
2453 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2454 then we don't do such fold.
2456 SIZE_EXPR is used for computing the size of the expression to be
2457 instantiated, and to stop if it exceeds some limit. */
2460 instantiate_scev_poly (basic_block instantiate_below
,
2461 struct loop
*evolution_loop
, struct loop
*,
2462 tree chrec
, bool *fold_conversions
, int size_expr
)
2465 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2466 get_chrec_loop (chrec
),
2467 CHREC_LEFT (chrec
), fold_conversions
,
2469 if (op0
== chrec_dont_know
)
2470 return chrec_dont_know
;
2472 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2473 get_chrec_loop (chrec
),
2474 CHREC_RIGHT (chrec
), fold_conversions
,
2476 if (op1
== chrec_dont_know
)
2477 return chrec_dont_know
;
2479 if (CHREC_LEFT (chrec
) != op0
2480 || CHREC_RIGHT (chrec
) != op1
)
2482 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2483 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2489 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2490 and EVOLUTION_LOOP, that were left under a symbolic form.
2492 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2494 CACHE is the cache of already instantiated values.
2496 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2497 conversions that may wrap in signed/pointer type are folded, as long
2498 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2499 then we don't do such fold.
2501 SIZE_EXPR is used for computing the size of the expression to be
2502 instantiated, and to stop if it exceeds some limit. */
2505 instantiate_scev_binary (basic_block instantiate_below
,
2506 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2507 tree chrec
, enum tree_code code
,
2508 tree type
, tree c0
, tree c1
,
2509 bool *fold_conversions
, int size_expr
)
2512 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2513 c0
, fold_conversions
, size_expr
);
2514 if (op0
== chrec_dont_know
)
2515 return chrec_dont_know
;
2517 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2518 c1
, fold_conversions
, size_expr
);
2519 if (op1
== chrec_dont_know
)
2520 return chrec_dont_know
;
2525 op0
= chrec_convert (type
, op0
, NULL
);
2526 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2530 case POINTER_PLUS_EXPR
:
2532 return chrec_fold_plus (type
, op0
, op1
);
2535 return chrec_fold_minus (type
, op0
, op1
);
2538 return chrec_fold_multiply (type
, op0
, op1
);
2545 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2548 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2549 and EVOLUTION_LOOP, that were left under a symbolic form.
2551 "CHREC" is an array reference to be instantiated.
2553 CACHE is the cache of already instantiated values.
2555 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2556 conversions that may wrap in signed/pointer type are folded, as long
2557 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2558 then we don't do such fold.
2560 SIZE_EXPR is used for computing the size of the expression to be
2561 instantiated, and to stop if it exceeds some limit. */
2564 instantiate_array_ref (basic_block instantiate_below
,
2565 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2566 tree chrec
, bool *fold_conversions
, int size_expr
)
2569 tree index
= TREE_OPERAND (chrec
, 1);
2570 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2572 fold_conversions
, size_expr
);
2574 if (op1
== chrec_dont_know
)
2575 return chrec_dont_know
;
2577 if (chrec
&& op1
== index
)
2580 res
= unshare_expr (chrec
);
2581 TREE_OPERAND (res
, 1) = op1
;
2585 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2586 and EVOLUTION_LOOP, that were left under a symbolic form.
2588 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2591 CACHE is the cache of already instantiated values.
2593 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2594 conversions that may wrap in signed/pointer type are folded, as long
2595 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2596 then we don't do such fold.
2598 SIZE_EXPR is used for computing the size of the expression to be
2599 instantiated, and to stop if it exceeds some limit. */
2602 instantiate_scev_convert (basic_block instantiate_below
,
2603 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2604 tree chrec
, tree type
, tree op
,
2605 bool *fold_conversions
, int size_expr
)
2607 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2609 fold_conversions
, size_expr
);
2611 if (op0
== chrec_dont_know
)
2612 return chrec_dont_know
;
2614 if (fold_conversions
)
2616 tree tmp
= chrec_convert_aggressive (type
, op0
, fold_conversions
);
2620 /* If we used chrec_convert_aggressive, we can no longer assume that
2621 signed chrecs do not overflow, as chrec_convert does, so avoid
2622 calling it in that case. */
2623 if (*fold_conversions
)
2625 if (chrec
&& op0
== op
)
2628 return fold_convert (type
, op0
);
2632 return chrec_convert (type
, op0
, NULL
);
2635 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2636 and EVOLUTION_LOOP, that were left under a symbolic form.
2638 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2639 Handle ~X as -1 - X.
2640 Handle -X as -1 * X.
2642 CACHE is the cache of already instantiated values.
2644 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2645 conversions that may wrap in signed/pointer type are folded, as long
2646 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2647 then we don't do such fold.
2649 SIZE_EXPR is used for computing the size of the expression to be
2650 instantiated, and to stop if it exceeds some limit. */
2653 instantiate_scev_not (basic_block instantiate_below
,
2654 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2656 enum tree_code code
, tree type
, tree op
,
2657 bool *fold_conversions
, int size_expr
)
2659 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2661 fold_conversions
, size_expr
);
2663 if (op0
== chrec_dont_know
)
2664 return chrec_dont_know
;
2668 op0
= chrec_convert (type
, op0
, NULL
);
2673 return chrec_fold_minus
2674 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2677 return chrec_fold_multiply
2678 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2685 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2688 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2689 and EVOLUTION_LOOP, that were left under a symbolic form.
2691 CHREC is an expression with 3 operands to be instantiated.
2693 CACHE is the cache of already instantiated values.
2695 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2696 conversions that may wrap in signed/pointer type are folded, as long
2697 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2698 then we don't do such fold.
2700 SIZE_EXPR is used for computing the size of the expression to be
2701 instantiated, and to stop if it exceeds some limit. */
2704 instantiate_scev_3 (basic_block instantiate_below
,
2705 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2707 bool *fold_conversions
, int size_expr
)
2710 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2711 inner_loop
, TREE_OPERAND (chrec
, 0),
2712 fold_conversions
, size_expr
);
2713 if (op0
== chrec_dont_know
)
2714 return chrec_dont_know
;
2716 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2717 inner_loop
, TREE_OPERAND (chrec
, 1),
2718 fold_conversions
, size_expr
);
2719 if (op1
== chrec_dont_know
)
2720 return chrec_dont_know
;
2722 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2723 inner_loop
, TREE_OPERAND (chrec
, 2),
2724 fold_conversions
, size_expr
);
2725 if (op2
== chrec_dont_know
)
2726 return chrec_dont_know
;
2728 if (op0
== TREE_OPERAND (chrec
, 0)
2729 && op1
== TREE_OPERAND (chrec
, 1)
2730 && op2
== TREE_OPERAND (chrec
, 2))
2733 return fold_build3 (TREE_CODE (chrec
),
2734 TREE_TYPE (chrec
), op0
, op1
, op2
);
2737 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2738 and EVOLUTION_LOOP, that were left under a symbolic form.
2740 CHREC is an expression with 2 operands to be instantiated.
2742 CACHE is the cache of already instantiated values.
2744 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2745 conversions that may wrap in signed/pointer type are folded, as long
2746 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2747 then we don't do such fold.
2749 SIZE_EXPR is used for computing the size of the expression to be
2750 instantiated, and to stop if it exceeds some limit. */
2753 instantiate_scev_2 (basic_block instantiate_below
,
2754 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2756 bool *fold_conversions
, int size_expr
)
2759 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2760 inner_loop
, TREE_OPERAND (chrec
, 0),
2761 fold_conversions
, size_expr
);
2762 if (op0
== chrec_dont_know
)
2763 return chrec_dont_know
;
2765 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2766 inner_loop
, TREE_OPERAND (chrec
, 1),
2767 fold_conversions
, size_expr
);
2768 if (op1
== chrec_dont_know
)
2769 return chrec_dont_know
;
2771 if (op0
== TREE_OPERAND (chrec
, 0)
2772 && op1
== TREE_OPERAND (chrec
, 1))
2775 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2778 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2779 and EVOLUTION_LOOP, that were left under a symbolic form.
2781 CHREC is an expression with 2 operands to be instantiated.
2783 CACHE is the cache of already instantiated values.
2785 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2786 conversions that may wrap in signed/pointer type are folded, as long
2787 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2788 then we don't do such fold.
2790 SIZE_EXPR is used for computing the size of the expression to be
2791 instantiated, and to stop if it exceeds some limit. */
2794 instantiate_scev_1 (basic_block instantiate_below
,
2795 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2797 bool *fold_conversions
, int size_expr
)
2799 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2800 inner_loop
, TREE_OPERAND (chrec
, 0),
2801 fold_conversions
, size_expr
);
2803 if (op0
== chrec_dont_know
)
2804 return chrec_dont_know
;
2806 if (op0
== TREE_OPERAND (chrec
, 0))
2809 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2812 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2813 and EVOLUTION_LOOP, that were left under a symbolic form.
2815 CHREC is the scalar evolution to instantiate.
2817 CACHE is the cache of already instantiated values.
2819 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2820 conversions that may wrap in signed/pointer type are folded, as long
2821 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2822 then we don't do such fold.
2824 SIZE_EXPR is used for computing the size of the expression to be
2825 instantiated, and to stop if it exceeds some limit. */
2828 instantiate_scev_r (basic_block instantiate_below
,
2829 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2831 bool *fold_conversions
, int size_expr
)
2833 /* Give up if the expression is larger than the MAX that we allow. */
2834 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2835 return chrec_dont_know
;
2837 if (chrec
== NULL_TREE
2838 || automatically_generated_chrec_p (chrec
)
2839 || is_gimple_min_invariant (chrec
))
2842 switch (TREE_CODE (chrec
))
2845 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2847 fold_conversions
, size_expr
);
2849 case POLYNOMIAL_CHREC
:
2850 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2852 fold_conversions
, size_expr
);
2854 case POINTER_PLUS_EXPR
:
2858 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2860 TREE_CODE (chrec
), chrec_type (chrec
),
2861 TREE_OPERAND (chrec
, 0),
2862 TREE_OPERAND (chrec
, 1),
2863 fold_conversions
, size_expr
);
2866 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2868 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2869 fold_conversions
, size_expr
);
2873 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2875 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2876 TREE_OPERAND (chrec
, 0),
2877 fold_conversions
, size_expr
);
2880 case SCEV_NOT_KNOWN
:
2881 return chrec_dont_know
;
2887 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2889 fold_conversions
, size_expr
);
2895 if (VL_EXP_CLASS_P (chrec
))
2896 return chrec_dont_know
;
2898 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2901 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2903 fold_conversions
, size_expr
);
2906 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2908 fold_conversions
, size_expr
);
2911 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2913 fold_conversions
, size_expr
);
2922 /* Too complicated to handle. */
2923 return chrec_dont_know
;
2926 /* Analyze all the parameters of the chrec that were left under a
2927 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2928 recursive instantiation of parameters: a parameter is a variable
2929 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2930 a function parameter. */
2933 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2938 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2940 fprintf (dump_file
, "(instantiate_scev \n");
2941 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2942 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2943 fprintf (dump_file
, " (chrec = ");
2944 print_generic_expr (dump_file
, chrec
, 0);
2945 fprintf (dump_file
, ")\n");
2951 global_cache
= new instantiate_cache_type
;
2955 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2956 NULL
, chrec
, NULL
, 0);
2960 delete global_cache
;
2961 global_cache
= NULL
;
2964 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2966 fprintf (dump_file
, " (res = ");
2967 print_generic_expr (dump_file
, res
, 0);
2968 fprintf (dump_file
, "))\n");
2974 /* Similar to instantiate_parameters, but does not introduce the
2975 evolutions in outer loops for LOOP invariants in CHREC, and does not
2976 care about causing overflows, as long as they do not affect value
2977 of an expression. */
2980 resolve_mixers (struct loop
*loop
, tree chrec
, bool *folded_casts
)
2983 bool fold_conversions
= false;
2986 global_cache
= new instantiate_cache_type
;
2990 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2991 chrec
, &fold_conversions
, 0);
2993 if (folded_casts
&& !*folded_casts
)
2994 *folded_casts
= fold_conversions
;
2998 delete global_cache
;
2999 global_cache
= NULL
;
3005 /* Entry point for the analysis of the number of iterations pass.
3006 This function tries to safely approximate the number of iterations
3007 the loop will run. When this property is not decidable at compile
3008 time, the result is chrec_dont_know. Otherwise the result is a
3009 scalar or a symbolic parameter. When the number of iterations may
3010 be equal to zero and the property cannot be determined at compile
3011 time, the result is a COND_EXPR that represents in a symbolic form
3012 the conditions under which the number of iterations is not zero.
3014 Example of analysis: suppose that the loop has an exit condition:
3016 "if (b > 49) goto end_loop;"
3018 and that in a previous analysis we have determined that the
3019 variable 'b' has an evolution function:
3021 "EF = {23, +, 5}_2".
3023 When we evaluate the function at the point 5, i.e. the value of the
3024 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
3025 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
3026 the loop body has been executed 6 times. */
3029 number_of_latch_executions (struct loop
*loop
)
3032 struct tree_niter_desc niter_desc
;
3036 /* Determine whether the number of iterations in loop has already
3038 res
= loop
->nb_iterations
;
3042 may_be_zero
= NULL_TREE
;
3044 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3045 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
3047 res
= chrec_dont_know
;
3048 exit
= single_exit (loop
);
3050 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
3052 may_be_zero
= niter_desc
.may_be_zero
;
3053 res
= niter_desc
.niter
;
3056 if (res
== chrec_dont_know
3058 || integer_zerop (may_be_zero
))
3060 else if (integer_nonzerop (may_be_zero
))
3061 res
= build_int_cst (TREE_TYPE (res
), 0);
3063 else if (COMPARISON_CLASS_P (may_be_zero
))
3064 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
3065 build_int_cst (TREE_TYPE (res
), 0), res
);
3067 res
= chrec_dont_know
;
3069 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3071 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
3072 print_generic_expr (dump_file
, res
, 0);
3073 fprintf (dump_file
, "))\n");
3076 loop
->nb_iterations
= res
;
3081 /* Counters for the stats. */
3087 unsigned nb_affine_multivar
;
3088 unsigned nb_higher_poly
;
3089 unsigned nb_chrec_dont_know
;
3090 unsigned nb_undetermined
;
3093 /* Reset the counters. */
3096 reset_chrecs_counters (struct chrec_stats
*stats
)
3098 stats
->nb_chrecs
= 0;
3099 stats
->nb_affine
= 0;
3100 stats
->nb_affine_multivar
= 0;
3101 stats
->nb_higher_poly
= 0;
3102 stats
->nb_chrec_dont_know
= 0;
3103 stats
->nb_undetermined
= 0;
3106 /* Dump the contents of a CHREC_STATS structure. */
3109 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
3111 fprintf (file
, "\n(\n");
3112 fprintf (file
, "-----------------------------------------\n");
3113 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
3114 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
3115 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
3116 stats
->nb_higher_poly
);
3117 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
3118 fprintf (file
, "-----------------------------------------\n");
3119 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
3120 fprintf (file
, "%d\twith undetermined coefficients\n",
3121 stats
->nb_undetermined
);
3122 fprintf (file
, "-----------------------------------------\n");
3123 fprintf (file
, "%d\tchrecs in the scev database\n",
3124 (int) scalar_evolution_info
->elements ());
3125 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
3126 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
3127 fprintf (file
, "-----------------------------------------\n");
3128 fprintf (file
, ")\n\n");
3131 /* Gather statistics about CHREC. */
3134 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
3136 if (dump_file
&& (dump_flags
& TDF_STATS
))
3138 fprintf (dump_file
, "(classify_chrec ");
3139 print_generic_expr (dump_file
, chrec
, 0);
3140 fprintf (dump_file
, "\n");
3145 if (chrec
== NULL_TREE
)
3147 stats
->nb_undetermined
++;
3151 switch (TREE_CODE (chrec
))
3153 case POLYNOMIAL_CHREC
:
3154 if (evolution_function_is_affine_p (chrec
))
3156 if (dump_file
&& (dump_flags
& TDF_STATS
))
3157 fprintf (dump_file
, " affine_univariate\n");
3160 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3162 if (dump_file
&& (dump_flags
& TDF_STATS
))
3163 fprintf (dump_file
, " affine_multivariate\n");
3164 stats
->nb_affine_multivar
++;
3168 if (dump_file
&& (dump_flags
& TDF_STATS
))
3169 fprintf (dump_file
, " higher_degree_polynomial\n");
3170 stats
->nb_higher_poly
++;
3179 if (chrec_contains_undetermined (chrec
))
3181 if (dump_file
&& (dump_flags
& TDF_STATS
))
3182 fprintf (dump_file
, " undetermined\n");
3183 stats
->nb_undetermined
++;
3186 if (dump_file
&& (dump_flags
& TDF_STATS
))
3187 fprintf (dump_file
, ")\n");
3190 /* Classify the chrecs of the whole database. */
3193 gather_stats_on_scev_database (void)
3195 struct chrec_stats stats
;
3200 reset_chrecs_counters (&stats
);
3202 hash_table
<scev_info_hasher
>::iterator iter
;
3204 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info
, elt
, scev_info_str
*,
3206 gather_chrec_stats (elt
->chrec
, &stats
);
3208 dump_chrecs_stats (dump_file
, &stats
);
3216 initialize_scalar_evolutions_analyzer (void)
3218 /* The elements below are unique. */
3219 if (chrec_dont_know
== NULL_TREE
)
3221 chrec_not_analyzed_yet
= NULL_TREE
;
3222 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3223 chrec_known
= make_node (SCEV_KNOWN
);
3224 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3225 TREE_TYPE (chrec_known
) = void_type_node
;
3229 /* Initialize the analysis of scalar evolutions for LOOPS. */
3232 scev_initialize (void)
3236 scalar_evolution_info
= hash_table
<scev_info_hasher
>::create_ggc (100);
3238 initialize_scalar_evolutions_analyzer ();
3240 FOR_EACH_LOOP (loop
, 0)
3242 loop
->nb_iterations
= NULL_TREE
;
3246 /* Return true if SCEV is initialized. */
3249 scev_initialized_p (void)
3251 return scalar_evolution_info
!= NULL
;
3254 /* Cleans up the information cached by the scalar evolutions analysis
3255 in the hash table. */
3258 scev_reset_htab (void)
3260 if (!scalar_evolution_info
)
3263 scalar_evolution_info
->empty ();
3266 /* Cleans up the information cached by the scalar evolutions analysis
3267 in the hash table and in the loop->nb_iterations. */
3276 FOR_EACH_LOOP (loop
, 0)
3278 loop
->nb_iterations
= NULL_TREE
;
3282 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3283 respect to WRTO_LOOP and returns its base and step in IV if possible
3284 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3285 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3286 invariant in LOOP. Otherwise we require it to be an integer constant.
3288 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3289 because it is computed in signed arithmetics). Consequently, adding an
3292 for (i = IV->base; ; i += IV->step)
3294 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3295 false for the type of the induction variable, or you can prove that i does
3296 not wrap by some other argument. Otherwise, this might introduce undefined
3299 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3301 must be used instead. */
3304 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3305 affine_iv
*iv
, bool allow_nonconstant_step
)
3307 enum tree_code code
;
3308 tree type
, ev
, base
, e
, stop
;
3310 bool folded_casts
, overflow
;
3312 iv
->base
= NULL_TREE
;
3313 iv
->step
= NULL_TREE
;
3314 iv
->no_overflow
= false;
3316 type
= TREE_TYPE (op
);
3317 if (!POINTER_TYPE_P (type
)
3318 && !INTEGRAL_TYPE_P (type
))
3321 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3323 if (chrec_contains_undetermined (ev
)
3324 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3327 if (tree_does_not_contain_chrecs (ev
))
3330 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3331 iv
->no_overflow
= true;
3335 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3336 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3339 iv
->step
= CHREC_RIGHT (ev
);
3340 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3341 || tree_contains_chrecs (iv
->step
, NULL
))
3344 iv
->base
= CHREC_LEFT (ev
);
3345 if (tree_contains_chrecs (iv
->base
, NULL
))
3348 iv
->no_overflow
= (!folded_casts
&& ANY_INTEGRAL_TYPE_P (type
)
3349 && TYPE_OVERFLOW_UNDEFINED (type
));
3351 /* Try to simplify iv base:
3353 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3354 == (signed T)(unsigned T)base + step
3357 If we can prove operation (base + step) doesn't overflow or underflow.
3358 Specifically, we try to prove below conditions are satisfied:
3360 base <= UPPER_BOUND (type) - step ;;step > 0
3361 base >= LOWER_BOUND (type) - step ;;step < 0
3363 This is done by proving the reverse conditions are false using loop's
3366 The is necessary to make loop niter, or iv overflow analysis easier
3369 int foo (int *a, signed char s, signed char l)
3372 for (i = s; i < l; i++)
3377 Note variable I is firstly converted to type unsigned char, incremented,
3378 then converted back to type signed char. */
3380 if (wrto_loop
->num
!= use_loop
->num
)
3383 if (!CONVERT_EXPR_P (iv
->base
) || TREE_CODE (iv
->step
) != INTEGER_CST
)
3386 type
= TREE_TYPE (iv
->base
);
3387 e
= TREE_OPERAND (iv
->base
, 0);
3388 if (TREE_CODE (e
) != PLUS_EXPR
3389 || TREE_CODE (TREE_OPERAND (e
, 1)) != INTEGER_CST
3390 || !tree_int_cst_equal (iv
->step
,
3391 fold_convert (type
, TREE_OPERAND (e
, 1))))
3393 e
= TREE_OPERAND (e
, 0);
3394 if (!CONVERT_EXPR_P (e
))
3396 base
= TREE_OPERAND (e
, 0);
3397 if (!useless_type_conversion_p (type
, TREE_TYPE (base
)))
3400 if (tree_int_cst_sign_bit (iv
->step
))
3403 extreme
= wi::min_value (type
);
3408 extreme
= wi::max_value (type
);
3411 extreme
= wi::sub (extreme
, iv
->step
, TYPE_SIGN (type
), &overflow
);
3414 e
= fold_build2 (code
, boolean_type_node
, base
,
3415 wide_int_to_tree (type
, extreme
));
3416 stop
= (TREE_CODE (base
) == SSA_NAME
) ? base
: NULL
;
3417 e
= simplify_using_initial_conditions (use_loop
, e
, stop
);
3418 if (!integer_zerop (e
))
3421 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3422 code
= POINTER_PLUS_EXPR
;
3426 iv
->base
= fold_build2 (code
, TREE_TYPE (base
), base
, iv
->step
);
3430 /* Finalize the scalar evolution analysis. */
3433 scev_finalize (void)
3435 if (!scalar_evolution_info
)
3437 scalar_evolution_info
->empty ();
3438 scalar_evolution_info
= NULL
;
3441 /* Returns true if the expression EXPR is considered to be too expensive
3442 for scev_const_prop. */
3445 expression_expensive_p (tree expr
)
3447 enum tree_code code
;
3449 if (is_gimple_val (expr
))
3452 code
= TREE_CODE (expr
);
3453 if (code
== TRUNC_DIV_EXPR
3454 || code
== CEIL_DIV_EXPR
3455 || code
== FLOOR_DIV_EXPR
3456 || code
== ROUND_DIV_EXPR
3457 || code
== TRUNC_MOD_EXPR
3458 || code
== CEIL_MOD_EXPR
3459 || code
== FLOOR_MOD_EXPR
3460 || code
== ROUND_MOD_EXPR
3461 || code
== EXACT_DIV_EXPR
)
3463 /* Division by power of two is usually cheap, so we allow it.
3464 Forbid anything else. */
3465 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3469 switch (TREE_CODE_CLASS (code
))
3472 case tcc_comparison
:
3473 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3478 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3485 /* Do final value replacement for LOOP. */
3488 final_value_replacement_loop (struct loop
*loop
)
3490 /* If we do not know exact number of iterations of the loop, we cannot
3491 replace the final value. */
3492 edge exit
= single_exit (loop
);
3496 tree niter
= number_of_latch_executions (loop
);
3497 if (niter
== chrec_dont_know
)
3500 /* Ensure that it is possible to insert new statements somewhere. */
3501 if (!single_pred_p (exit
->dest
))
3502 split_loop_exit_edge (exit
);
3504 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3505 gimple_stmt_iterator gsi
= gsi_after_labels (exit
->dest
);
3507 struct loop
*ex_loop
3508 = superloop_at_depth (loop
,
3509 loop_depth (exit
->dest
->loop_father
) + 1);
3512 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3514 gphi
*phi
= psi
.phi ();
3515 tree rslt
= PHI_RESULT (phi
);
3516 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3517 if (virtual_operand_p (def
))
3523 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3524 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3531 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
,
3533 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3534 if (!tree_does_not_contain_chrecs (def
)
3535 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3536 /* Moving the computation from the loop may prolong life range
3537 of some ssa names, which may cause problems if they appear
3538 on abnormal edges. */
3539 || contains_abnormal_ssa_name_p (def
)
3540 /* Do not emit expensive expressions. The rationale is that
3541 when someone writes a code like
3543 while (n > 45) n -= 45;
3545 he probably knows that n is not large, and does not want it
3546 to be turned into n %= 45. */
3547 || expression_expensive_p (def
))
3549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3551 fprintf (dump_file
, "not replacing:\n ");
3552 print_gimple_stmt (dump_file
, phi
, 0, 0);
3553 fprintf (dump_file
, "\n");
3559 /* Eliminate the PHI node and replace it by a computation outside
3563 fprintf (dump_file
, "\nfinal value replacement:\n ");
3564 print_gimple_stmt (dump_file
, phi
, 0, 0);
3565 fprintf (dump_file
, " with\n ");
3567 def
= unshare_expr (def
);
3568 remove_phi_node (&psi
, false);
3570 /* If def's type has undefined overflow and there were folded
3571 casts, rewrite all stmts added for def into arithmetics
3572 with defined overflow behavior. */
3573 if (folded_casts
&& ANY_INTEGRAL_TYPE_P (TREE_TYPE (def
))
3574 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def
)))
3577 gimple_stmt_iterator gsi2
;
3578 def
= force_gimple_operand (def
, &stmts
, true, NULL_TREE
);
3579 gsi2
= gsi_start (stmts
);
3580 while (!gsi_end_p (gsi2
))
3582 gimple
*stmt
= gsi_stmt (gsi2
);
3583 gimple_stmt_iterator gsi3
= gsi2
;
3585 gsi_remove (&gsi3
, false);
3586 if (is_gimple_assign (stmt
)
3587 && arith_code_with_undefined_signed_overflow
3588 (gimple_assign_rhs_code (stmt
)))
3589 gsi_insert_seq_before (&gsi
,
3590 rewrite_to_defined_overflow (stmt
),
3593 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3597 def
= force_gimple_operand_gsi (&gsi
, def
, false, NULL_TREE
,
3598 true, GSI_SAME_STMT
);
3600 gassign
*ass
= gimple_build_assign (rslt
, def
);
3601 gsi_insert_before (&gsi
, ass
, GSI_SAME_STMT
);
3604 print_gimple_stmt (dump_file
, ass
, 0, 0);
3605 fprintf (dump_file
, "\n");
3610 /* Replace ssa names for that scev can prove they are constant by the
3611 appropriate constants. Also perform final value replacement in loops,
3612 in case the replacement expressions are cheap.
3614 We only consider SSA names defined by phi nodes; rest is left to the
3615 ordinary constant propagation pass. */
3618 scev_const_prop (void)
3621 tree name
, type
, ev
;
3624 bitmap ssa_names_to_remove
= NULL
;
3628 if (number_of_loops (cfun
) <= 1)
3631 FOR_EACH_BB_FN (bb
, cfun
)
3633 loop
= bb
->loop_father
;
3635 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3638 name
= PHI_RESULT (phi
);
3640 if (virtual_operand_p (name
))
3643 type
= TREE_TYPE (name
);
3645 if (!POINTER_TYPE_P (type
)
3646 && !INTEGRAL_TYPE_P (type
))
3649 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
),
3651 if (!is_gimple_min_invariant (ev
)
3652 || !may_propagate_copy (name
, ev
))
3655 /* Replace the uses of the name. */
3658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3660 fprintf (dump_file
, "Replacing uses of: ");
3661 print_generic_expr (dump_file
, name
, 0);
3662 fprintf (dump_file
, " with: ");
3663 print_generic_expr (dump_file
, ev
, 0);
3664 fprintf (dump_file
, "\n");
3666 replace_uses_by (name
, ev
);
3669 if (!ssa_names_to_remove
)
3670 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3671 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3675 /* Remove the ssa names that were replaced by constants. We do not
3676 remove them directly in the previous cycle, since this
3677 invalidates scev cache. */
3678 if (ssa_names_to_remove
)
3682 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3684 gimple_stmt_iterator psi
;
3685 name
= ssa_name (i
);
3686 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (name
));
3688 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3689 psi
= gsi_for_stmt (phi
);
3690 remove_phi_node (&psi
, true);
3693 BITMAP_FREE (ssa_names_to_remove
);
3697 /* Now the regular final value replacement. */
3698 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3699 final_value_replacement_loop (loop
);
3704 #include "gt-tree-scalar-evolution.h"