1 /* Scalar evolution detector.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
50 - When the definition is a GIMPLE_ASSIGN: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
75 Example 1: Illustration of the basic algorithm.
81 | if (c > 10) exit_loop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
119 or in terms of a C program:
122 | for (x = 0; x <= 7; x++)
128 Example 2a: Illustration of the algorithm on nested loops.
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
157 Example 2b: Multivariate chains of recurrences.
170 Analyzing the access function of array A with
171 instantiate_parameters (loop_1, "j + k"), we obtain the
172 instantiation and the analysis of the scalar variables "j" and "k"
173 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175 {0, +, 1}_1. To obtain the evolution function in loop_3 and
176 instantiate the scalar variables up to loop_1, one has to use:
177 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178 The result of this call is {{0, +, 1}_1, +, 1}_2.
180 Example 3: Higher degree polynomials.
194 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197 Example 4: Lucas, Fibonacci, or mixers in general.
209 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210 following semantics: during the first iteration of the loop_1, the
211 variable contains the value 1, and then it contains the value "c".
212 Note that this syntax is close to the syntax of the loop-phi-node:
213 "a -> (1, c)_1" vs. "a = phi (1, c)".
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
218 Example 5: Flip-flops, or exchangers.
230 Based on these symbolic chrecs, it is possible to refine this
231 information into the more precise PERIODIC_CHRECs:
236 This transformation is not yet implemented.
240 You can find a more detailed description of the algorithm in:
241 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243 this is a preliminary report and some of the details of the
244 algorithm have changed. I'm working on a research report that
245 updates the description of the algorithms to reflect the design
246 choices used in this implementation.
248 A set of slides show a high level overview of the algorithm and run
249 an example through the scalar evolution analyzer:
250 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252 The slides that I have presented at the GCC Summit'04 are available
253 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
258 #include "coretypes.h"
260 #include "hash-table.h"
261 #include "gimple-pretty-print.h"
263 #include "gimplify.h"
264 #include "gimple-iterator.h"
265 #include "gimplify-me.h"
266 #include "gimple-ssa.h"
267 #include "tree-cfg.h"
268 #include "tree-phinodes.h"
269 #include "tree-ssanames.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-scalar-evolution.h"
278 #include "dumpfile.h"
280 #include "tree-ssa-propagate.h"
282 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
283 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
286 /* The cached information about an SSA name with version NAME_VERSION,
287 claiming that below basic block with index INSTANTIATED_BELOW, the
288 value of the SSA name can be expressed as CHREC. */
290 struct GTY(()) scev_info_str
{
291 unsigned int name_version
;
292 int instantiated_below
;
296 /* Counters for the scev database. */
297 static unsigned nb_set_scev
= 0;
298 static unsigned nb_get_scev
= 0;
300 /* The following trees are unique elements. Thus the comparison of
301 another element to these elements should be done on the pointer to
302 these trees, and not on their value. */
304 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
305 tree chrec_not_analyzed_yet
;
307 /* Reserved to the cases where the analyzer has detected an
308 undecidable property at compile time. */
309 tree chrec_dont_know
;
311 /* When the analyzer has detected that a property will never
312 happen, then it qualifies it with chrec_known. */
315 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
318 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
320 static inline struct scev_info_str
*
321 new_scev_info_str (basic_block instantiated_below
, tree var
)
323 struct scev_info_str
*res
;
325 res
= ggc_alloc_scev_info_str ();
326 res
->name_version
= SSA_NAME_VERSION (var
);
327 res
->chrec
= chrec_not_analyzed_yet
;
328 res
->instantiated_below
= instantiated_below
->index
;
333 /* Computes a hash function for database element ELT. */
335 static inline hashval_t
336 hash_scev_info (const void *elt_
)
338 const struct scev_info_str
*elt
= (const struct scev_info_str
*) elt_
;
339 return elt
->name_version
^ elt
->instantiated_below
;
342 /* Compares database elements E1 and E2. */
345 eq_scev_info (const void *e1
, const void *e2
)
347 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
348 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
350 return (elt1
->name_version
== elt2
->name_version
351 && elt1
->instantiated_below
== elt2
->instantiated_below
);
354 /* Deletes database element E. */
357 del_scev_info (void *e
)
363 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
364 A first query on VAR returns chrec_not_analyzed_yet. */
367 find_var_scev_info (basic_block instantiated_below
, tree var
)
369 struct scev_info_str
*res
;
370 struct scev_info_str tmp
;
373 tmp
.name_version
= SSA_NAME_VERSION (var
);
374 tmp
.instantiated_below
= instantiated_below
->index
;
375 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
378 *slot
= new_scev_info_str (instantiated_below
, var
);
379 res
= (struct scev_info_str
*) *slot
;
384 /* Return true when CHREC contains symbolic names defined in
388 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
392 if (chrec
== NULL_TREE
)
395 if (is_gimple_min_invariant (chrec
))
398 if (TREE_CODE (chrec
) == SSA_NAME
)
401 loop_p def_loop
, loop
;
403 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
406 def
= SSA_NAME_DEF_STMT (chrec
);
407 def_loop
= loop_containing_stmt (def
);
408 loop
= get_loop (cfun
, loop_nb
);
410 if (def_loop
== NULL
)
413 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
419 n
= TREE_OPERAND_LENGTH (chrec
);
420 for (i
= 0; i
< n
; i
++)
421 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
427 /* Return true when PHI is a loop-phi-node. */
430 loop_phi_node_p (gimple phi
)
432 /* The implementation of this function is based on the following
433 property: "all the loop-phi-nodes of a loop are contained in the
434 loop's header basic block". */
436 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
439 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
440 In general, in the case of multivariate evolutions we want to get
441 the evolution in different loops. LOOP specifies the level for
442 which to get the evolution.
446 | for (j = 0; j < 100; j++)
448 | for (k = 0; k < 100; k++)
450 | i = k + j; - Here the value of i is a function of j, k.
452 | ... = i - Here the value of i is a function of j.
454 | ... = i - Here the value of i is a scalar.
460 | i_1 = phi (i_0, i_2)
464 This loop has the same effect as:
465 LOOP_1 has the same effect as:
469 The overall effect of the loop, "i_0 + 20" in the previous example,
470 is obtained by passing in the parameters: LOOP = 1,
471 EVOLUTION_FN = {i_0, +, 2}_1.
475 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
479 if (evolution_fn
== chrec_dont_know
)
480 return chrec_dont_know
;
482 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
484 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
486 if (inner_loop
== loop
487 || flow_loop_nested_p (loop
, inner_loop
))
489 tree nb_iter
= number_of_latch_executions (inner_loop
);
491 if (nb_iter
== chrec_dont_know
)
492 return chrec_dont_know
;
497 /* evolution_fn is the evolution function in LOOP. Get
498 its value in the nb_iter-th iteration. */
499 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
501 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
502 res
= instantiate_parameters (loop
, res
);
504 /* Continue the computation until ending on a parent of LOOP. */
505 return compute_overall_effect_of_inner_loop (loop
, res
);
512 /* If the evolution function is an invariant, there is nothing to do. */
513 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
517 return chrec_dont_know
;
520 /* Associate CHREC to SCALAR. */
523 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
527 if (TREE_CODE (scalar
) != SSA_NAME
)
530 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
534 if (dump_flags
& TDF_SCEV
)
536 fprintf (dump_file
, "(set_scalar_evolution \n");
537 fprintf (dump_file
, " instantiated_below = %d \n",
538 instantiated_below
->index
);
539 fprintf (dump_file
, " (scalar = ");
540 print_generic_expr (dump_file
, scalar
, 0);
541 fprintf (dump_file
, ")\n (scalar_evolution = ");
542 print_generic_expr (dump_file
, chrec
, 0);
543 fprintf (dump_file
, "))\n");
545 if (dump_flags
& TDF_STATS
)
549 *scalar_info
= chrec
;
552 /* Retrieve the chrec associated to SCALAR instantiated below
553 INSTANTIATED_BELOW block. */
556 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
562 if (dump_flags
& TDF_SCEV
)
564 fprintf (dump_file
, "(get_scalar_evolution \n");
565 fprintf (dump_file
, " (scalar = ");
566 print_generic_expr (dump_file
, scalar
, 0);
567 fprintf (dump_file
, ")\n");
569 if (dump_flags
& TDF_STATS
)
573 switch (TREE_CODE (scalar
))
576 res
= *find_var_scev_info (instantiated_below
, scalar
);
586 res
= chrec_not_analyzed_yet
;
590 if (dump_file
&& (dump_flags
& TDF_SCEV
))
592 fprintf (dump_file
, " (scalar_evolution = ");
593 print_generic_expr (dump_file
, res
, 0);
594 fprintf (dump_file
, "))\n");
600 /* Helper function for add_to_evolution. Returns the evolution
601 function for an assignment of the form "a = b + c", where "a" and
602 "b" are on the strongly connected component. CHREC_BEFORE is the
603 information that we already have collected up to this point.
604 TO_ADD is the evolution of "c".
606 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
607 evolution the expression TO_ADD, otherwise construct an evolution
608 part for this loop. */
611 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
614 tree type
, left
, right
;
615 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
617 switch (TREE_CODE (chrec_before
))
619 case POLYNOMIAL_CHREC
:
620 chloop
= get_chrec_loop (chrec_before
);
622 || flow_loop_nested_p (chloop
, loop
))
626 type
= chrec_type (chrec_before
);
628 /* When there is no evolution part in this loop, build it. */
633 right
= SCALAR_FLOAT_TYPE_P (type
)
634 ? build_real (type
, dconst0
)
635 : build_int_cst (type
, 0);
639 var
= CHREC_VARIABLE (chrec_before
);
640 left
= CHREC_LEFT (chrec_before
);
641 right
= CHREC_RIGHT (chrec_before
);
644 to_add
= chrec_convert (type
, to_add
, at_stmt
);
645 right
= chrec_convert_rhs (type
, right
, at_stmt
);
646 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
647 return build_polynomial_chrec (var
, left
, right
);
651 gcc_assert (flow_loop_nested_p (loop
, chloop
));
653 /* Search the evolution in LOOP_NB. */
654 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
656 right
= CHREC_RIGHT (chrec_before
);
657 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
658 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
663 /* These nodes do not depend on a loop. */
664 if (chrec_before
== chrec_dont_know
)
665 return chrec_dont_know
;
668 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
669 return build_polynomial_chrec (loop_nb
, left
, right
);
673 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
676 Description (provided for completeness, for those who read code in
677 a plane, and for my poor 62 bytes brain that would have forgotten
678 all this in the next two or three months):
680 The algorithm of translation of programs from the SSA representation
681 into the chrecs syntax is based on a pattern matching. After having
682 reconstructed the overall tree expression for a loop, there are only
683 two cases that can arise:
685 1. a = loop-phi (init, a + expr)
686 2. a = loop-phi (init, expr)
688 where EXPR is either a scalar constant with respect to the analyzed
689 loop (this is a degree 0 polynomial), or an expression containing
690 other loop-phi definitions (these are higher degree polynomials).
697 | a = phi (init, a + 5)
704 | a = phi (inita, 2 * b + 3)
705 | b = phi (initb, b + 1)
708 For the first case, the semantics of the SSA representation is:
710 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
712 that is, there is a loop index "x" that determines the scalar value
713 of the variable during the loop execution. During the first
714 iteration, the value is that of the initial condition INIT, while
715 during the subsequent iterations, it is the sum of the initial
716 condition with the sum of all the values of EXPR from the initial
717 iteration to the before last considered iteration.
719 For the second case, the semantics of the SSA program is:
721 | a (x) = init, if x = 0;
722 | expr (x - 1), otherwise.
724 The second case corresponds to the PEELED_CHREC, whose syntax is
725 close to the syntax of a loop-phi-node:
727 | phi (init, expr) vs. (init, expr)_x
729 The proof of the translation algorithm for the first case is a
730 proof by structural induction based on the degree of EXPR.
733 When EXPR is a constant with respect to the analyzed loop, or in
734 other words when EXPR is a polynomial of degree 0, the evolution of
735 the variable A in the loop is an affine function with an initial
736 condition INIT, and a step EXPR. In order to show this, we start
737 from the semantics of the SSA representation:
739 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
741 and since "expr (j)" is a constant with respect to "j",
743 f (x) = init + x * expr
745 Finally, based on the semantics of the pure sum chrecs, by
746 identification we get the corresponding chrecs syntax:
748 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
749 f (x) -> {init, +, expr}_x
752 Suppose that EXPR is a polynomial of degree N with respect to the
753 analyzed loop_x for which we have already determined that it is
754 written under the chrecs syntax:
756 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
758 We start from the semantics of the SSA program:
760 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
762 | f (x) = init + \sum_{j = 0}^{x - 1}
763 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
765 | f (x) = init + \sum_{j = 0}^{x - 1}
766 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
768 | f (x) = init + \sum_{k = 0}^{n - 1}
769 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
771 | f (x) = init + \sum_{k = 0}^{n - 1}
772 | (b_k * \binom{x}{k + 1})
774 | f (x) = init + b_0 * \binom{x}{1} + ...
775 | + b_{n-1} * \binom{x}{n}
777 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
778 | + b_{n-1} * \binom{x}{n}
781 And finally from the definition of the chrecs syntax, we identify:
782 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
784 This shows the mechanism that stands behind the add_to_evolution
785 function. An important point is that the use of symbolic
786 parameters avoids the need of an analysis schedule.
793 | a = phi (inita, a + 2 + b)
794 | b = phi (initb, b + 1)
797 When analyzing "a", the algorithm keeps "b" symbolically:
799 | a -> {inita, +, 2 + b}_1
801 Then, after instantiation, the analyzer ends on the evolution:
803 | a -> {inita, +, 2 + initb, +, 1}_1
808 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
809 tree to_add
, gimple at_stmt
)
811 tree type
= chrec_type (to_add
);
812 tree res
= NULL_TREE
;
814 if (to_add
== NULL_TREE
)
817 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
818 instantiated at this point. */
819 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
820 /* This should not happen. */
821 return chrec_dont_know
;
823 if (dump_file
&& (dump_flags
& TDF_SCEV
))
825 fprintf (dump_file
, "(add_to_evolution \n");
826 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
827 fprintf (dump_file
, " (chrec_before = ");
828 print_generic_expr (dump_file
, chrec_before
, 0);
829 fprintf (dump_file
, ")\n (to_add = ");
830 print_generic_expr (dump_file
, to_add
, 0);
831 fprintf (dump_file
, ")\n");
834 if (code
== MINUS_EXPR
)
835 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
836 ? build_real (type
, dconstm1
)
837 : build_int_cst_type (type
, -1));
839 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
841 if (dump_file
&& (dump_flags
& TDF_SCEV
))
843 fprintf (dump_file
, " (res = ");
844 print_generic_expr (dump_file
, res
, 0);
845 fprintf (dump_file
, "))\n");
853 /* This section selects the loops that will be good candidates for the
854 scalar evolution analysis. For the moment, greedily select all the
855 loop nests we could analyze. */
857 /* For a loop with a single exit edge, return the COND_EXPR that
858 guards the exit edge. If the expression is too difficult to
859 analyze, then give up. */
862 get_loop_exit_condition (const struct loop
*loop
)
865 edge exit_edge
= single_exit (loop
);
867 if (dump_file
&& (dump_flags
& TDF_SCEV
))
868 fprintf (dump_file
, "(get_loop_exit_condition \n ");
874 stmt
= last_stmt (exit_edge
->src
);
875 if (gimple_code (stmt
) == GIMPLE_COND
)
879 if (dump_file
&& (dump_flags
& TDF_SCEV
))
881 print_gimple_stmt (dump_file
, res
, 0, 0);
882 fprintf (dump_file
, ")\n");
889 /* Depth first search algorithm. */
891 typedef enum t_bool
{
898 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
900 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
901 Return true if the strongly connected component has been found. */
904 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
905 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
906 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
908 t_bool res
= t_false
;
913 case POINTER_PLUS_EXPR
:
915 if (TREE_CODE (rhs0
) == SSA_NAME
)
917 if (TREE_CODE (rhs1
) == SSA_NAME
)
919 /* Match an assignment under the form:
922 /* We want only assignments of form "name + name" contribute to
923 LIMIT, as the other cases do not necessarily contribute to
924 the complexity of the expression. */
927 evol
= *evolution_of_loop
;
928 res
= follow_ssa_edge
929 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
932 *evolution_of_loop
= add_to_evolution
934 chrec_convert (type
, evol
, at_stmt
),
935 code
, rhs1
, at_stmt
);
937 else if (res
== t_false
)
939 res
= follow_ssa_edge
940 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
941 evolution_of_loop
, limit
);
944 *evolution_of_loop
= add_to_evolution
946 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
947 code
, rhs0
, at_stmt
);
949 else if (res
== t_dont_know
)
950 *evolution_of_loop
= chrec_dont_know
;
953 else if (res
== t_dont_know
)
954 *evolution_of_loop
= chrec_dont_know
;
959 /* Match an assignment under the form:
961 res
= follow_ssa_edge
962 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
963 evolution_of_loop
, limit
);
965 *evolution_of_loop
= add_to_evolution
966 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
968 code
, rhs1
, at_stmt
);
970 else if (res
== t_dont_know
)
971 *evolution_of_loop
= chrec_dont_know
;
975 else if (TREE_CODE (rhs1
) == SSA_NAME
)
977 /* Match an assignment under the form:
979 res
= follow_ssa_edge
980 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
981 evolution_of_loop
, limit
);
983 *evolution_of_loop
= add_to_evolution
984 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
986 code
, rhs0
, at_stmt
);
988 else if (res
== t_dont_know
)
989 *evolution_of_loop
= chrec_dont_know
;
993 /* Otherwise, match an assignment under the form:
995 /* And there is nothing to do. */
1000 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1001 if (TREE_CODE (rhs0
) == SSA_NAME
)
1003 /* Match an assignment under the form:
1006 /* We want only assignments of form "name - name" contribute to
1007 LIMIT, as the other cases do not necessarily contribute to
1008 the complexity of the expression. */
1009 if (TREE_CODE (rhs1
) == SSA_NAME
)
1012 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1013 evolution_of_loop
, limit
);
1015 *evolution_of_loop
= add_to_evolution
1016 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1017 MINUS_EXPR
, rhs1
, at_stmt
);
1019 else if (res
== t_dont_know
)
1020 *evolution_of_loop
= chrec_dont_know
;
1023 /* Otherwise, match an assignment under the form:
1025 /* And there is nothing to do. */
1036 /* Follow the ssa edge into the expression EXPR.
1037 Return true if the strongly connected component has been found. */
1040 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1041 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1043 enum tree_code code
= TREE_CODE (expr
);
1044 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1047 /* The EXPR is one of the following cases:
1051 - a POINTER_PLUS_EXPR,
1054 - other cases are not yet handled. */
1059 /* This assignment is under the form "a_1 = (cast) rhs. */
1060 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1061 halting_phi
, evolution_of_loop
, limit
);
1062 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1066 /* This assignment is under the form "a_1 = 7". */
1071 /* This assignment is under the form: "a_1 = b_2". */
1072 res
= follow_ssa_edge
1073 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1076 case POINTER_PLUS_EXPR
:
1079 /* This case is under the form "rhs0 +- rhs1". */
1080 rhs0
= TREE_OPERAND (expr
, 0);
1081 rhs1
= TREE_OPERAND (expr
, 1);
1082 type
= TREE_TYPE (rhs0
);
1083 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1084 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1085 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1086 halting_phi
, evolution_of_loop
, limit
);
1090 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1091 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1093 expr
= TREE_OPERAND (expr
, 0);
1094 rhs0
= TREE_OPERAND (expr
, 0);
1095 rhs1
= TREE_OPERAND (expr
, 1);
1096 type
= TREE_TYPE (rhs0
);
1097 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1098 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1099 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1100 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1101 halting_phi
, evolution_of_loop
, limit
);
1108 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1109 It must be handled as a copy assignment of the form a_1 = a_2. */
1110 rhs0
= ASSERT_EXPR_VAR (expr
);
1111 if (TREE_CODE (rhs0
) == SSA_NAME
)
1112 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1113 halting_phi
, evolution_of_loop
, limit
);
1126 /* Follow the ssa edge into the right hand side of an assignment STMT.
1127 Return true if the strongly connected component has been found. */
1130 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1131 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1133 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1134 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1140 /* This assignment is under the form "a_1 = (cast) rhs. */
1141 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1142 halting_phi
, evolution_of_loop
, limit
);
1143 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1146 case POINTER_PLUS_EXPR
:
1149 rhs1
= gimple_assign_rhs1 (stmt
);
1150 rhs2
= gimple_assign_rhs2 (stmt
);
1151 type
= TREE_TYPE (rhs1
);
1152 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1153 halting_phi
, evolution_of_loop
, limit
);
1157 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1158 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1159 halting_phi
, evolution_of_loop
, limit
);
1168 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1171 backedge_phi_arg_p (gimple phi
, int i
)
1173 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1175 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1176 about updating it anywhere, and this should work as well most of the
1178 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1184 /* Helper function for one branch of the condition-phi-node. Return
1185 true if the strongly connected component has been found following
1188 static inline t_bool
1189 follow_ssa_edge_in_condition_phi_branch (int i
,
1191 gimple condition_phi
,
1193 tree
*evolution_of_branch
,
1194 tree init_cond
, int limit
)
1196 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1197 *evolution_of_branch
= chrec_dont_know
;
1199 /* Do not follow back edges (they must belong to an irreducible loop, which
1200 we really do not want to worry about). */
1201 if (backedge_phi_arg_p (condition_phi
, i
))
1204 if (TREE_CODE (branch
) == SSA_NAME
)
1206 *evolution_of_branch
= init_cond
;
1207 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1208 evolution_of_branch
, limit
);
1211 /* This case occurs when one of the condition branches sets
1212 the variable to a constant: i.e. a phi-node like
1213 "a_2 = PHI <a_7(5), 2(6)>;".
1215 FIXME: This case have to be refined correctly:
1216 in some cases it is possible to say something better than
1217 chrec_dont_know, for example using a wrap-around notation. */
1221 /* This function merges the branches of a condition-phi-node in a
1225 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1226 gimple condition_phi
,
1228 tree
*evolution_of_loop
, int limit
)
1231 tree init
= *evolution_of_loop
;
1232 tree evolution_of_branch
;
1233 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1235 &evolution_of_branch
,
1237 if (res
== t_false
|| res
== t_dont_know
)
1240 *evolution_of_loop
= evolution_of_branch
;
1242 n
= gimple_phi_num_args (condition_phi
);
1243 for (i
= 1; i
< n
; i
++)
1245 /* Quickly give up when the evolution of one of the branches is
1247 if (*evolution_of_loop
== chrec_dont_know
)
1250 /* Increase the limit by the PHI argument number to avoid exponential
1251 time and memory complexity. */
1252 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1254 &evolution_of_branch
,
1256 if (res
== t_false
|| res
== t_dont_know
)
1259 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1260 evolution_of_branch
);
1266 /* Follow an SSA edge in an inner loop. It computes the overall
1267 effect of the loop, and following the symbolic initial conditions,
1268 it follows the edges in the parent loop. The inner loop is
1269 considered as a single statement. */
1272 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1273 gimple loop_phi_node
,
1275 tree
*evolution_of_loop
, int limit
)
1277 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1278 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1280 /* Sometimes, the inner loop is too difficult to analyze, and the
1281 result of the analysis is a symbolic parameter. */
1282 if (ev
== PHI_RESULT (loop_phi_node
))
1284 t_bool res
= t_false
;
1285 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1287 for (i
= 0; i
< n
; i
++)
1289 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1292 /* Follow the edges that exit the inner loop. */
1293 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1294 if (!flow_bb_inside_loop_p (loop
, bb
))
1295 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1297 evolution_of_loop
, limit
);
1302 /* If the path crosses this loop-phi, give up. */
1304 *evolution_of_loop
= chrec_dont_know
;
1309 /* Otherwise, compute the overall effect of the inner loop. */
1310 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1311 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1312 evolution_of_loop
, limit
);
1315 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1316 path that is analyzed on the return walk. */
1319 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1320 tree
*evolution_of_loop
, int limit
)
1322 struct loop
*def_loop
;
1324 if (gimple_nop_p (def
))
1327 /* Give up if the path is longer than the MAX that we allow. */
1328 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1331 def_loop
= loop_containing_stmt (def
);
1333 switch (gimple_code (def
))
1336 if (!loop_phi_node_p (def
))
1337 /* DEF is a condition-phi-node. Follow the branches, and
1338 record their evolutions. Finally, merge the collected
1339 information and set the approximation to the main
1341 return follow_ssa_edge_in_condition_phi
1342 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1344 /* When the analyzed phi is the halting_phi, the
1345 depth-first search is over: we have found a path from
1346 the halting_phi to itself in the loop. */
1347 if (def
== halting_phi
)
1350 /* Otherwise, the evolution of the HALTING_PHI depends
1351 on the evolution of another loop-phi-node, i.e. the
1352 evolution function is a higher degree polynomial. */
1353 if (def_loop
== loop
)
1357 if (flow_loop_nested_p (loop
, def_loop
))
1358 return follow_ssa_edge_inner_loop_phi
1359 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1365 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1366 evolution_of_loop
, limit
);
1369 /* At this level of abstraction, the program is just a set
1370 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1371 other node to be handled. */
1378 /* Given a LOOP_PHI_NODE, this function determines the evolution
1379 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1382 analyze_evolution_in_loop (gimple loop_phi_node
,
1385 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1386 tree evolution_function
= chrec_not_analyzed_yet
;
1387 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1390 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1392 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1393 fprintf (dump_file
, " (loop_phi_node = ");
1394 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1395 fprintf (dump_file
, ")\n");
1398 for (i
= 0; i
< n
; i
++)
1400 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1405 /* Select the edges that enter the loop body. */
1406 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1407 if (!flow_bb_inside_loop_p (loop
, bb
))
1410 if (TREE_CODE (arg
) == SSA_NAME
)
1414 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1416 /* Pass in the initial condition to the follow edge function. */
1418 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1420 /* If ev_fn has no evolution in the inner loop, and the
1421 init_cond is not equal to ev_fn, then we have an
1422 ambiguity between two possible values, as we cannot know
1423 the number of iterations at this point. */
1424 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1425 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1426 && !operand_equal_p (init_cond
, ev_fn
, 0))
1427 ev_fn
= chrec_dont_know
;
1432 /* When it is impossible to go back on the same
1433 loop_phi_node by following the ssa edges, the
1434 evolution is represented by a peeled chrec, i.e. the
1435 first iteration, EV_FN has the value INIT_COND, then
1436 all the other iterations it has the value of ARG.
1437 For the moment, PEELED_CHREC nodes are not built. */
1439 ev_fn
= chrec_dont_know
;
1441 /* When there are multiple back edges of the loop (which in fact never
1442 happens currently, but nevertheless), merge their evolutions. */
1443 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1446 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1448 fprintf (dump_file
, " (evolution_function = ");
1449 print_generic_expr (dump_file
, evolution_function
, 0);
1450 fprintf (dump_file
, "))\n");
1453 return evolution_function
;
1456 /* Given a loop-phi-node, return the initial conditions of the
1457 variable on entry of the loop. When the CCP has propagated
1458 constants into the loop-phi-node, the initial condition is
1459 instantiated, otherwise the initial condition is kept symbolic.
1460 This analyzer does not analyze the evolution outside the current
1461 loop, and leaves this task to the on-demand tree reconstructor. */
1464 analyze_initial_condition (gimple loop_phi_node
)
1467 tree init_cond
= chrec_not_analyzed_yet
;
1468 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1470 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1472 fprintf (dump_file
, "(analyze_initial_condition \n");
1473 fprintf (dump_file
, " (loop_phi_node = \n");
1474 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1475 fprintf (dump_file
, ")\n");
1478 n
= gimple_phi_num_args (loop_phi_node
);
1479 for (i
= 0; i
< n
; i
++)
1481 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1482 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1484 /* When the branch is oriented to the loop's body, it does
1485 not contribute to the initial condition. */
1486 if (flow_bb_inside_loop_p (loop
, bb
))
1489 if (init_cond
== chrec_not_analyzed_yet
)
1495 if (TREE_CODE (branch
) == SSA_NAME
)
1497 init_cond
= chrec_dont_know
;
1501 init_cond
= chrec_merge (init_cond
, branch
);
1504 /* Ooops -- a loop without an entry??? */
1505 if (init_cond
== chrec_not_analyzed_yet
)
1506 init_cond
= chrec_dont_know
;
1508 /* During early loop unrolling we do not have fully constant propagated IL.
1509 Handle degenerate PHIs here to not miss important unrollings. */
1510 if (TREE_CODE (init_cond
) == SSA_NAME
)
1512 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1514 if (gimple_code (def
) == GIMPLE_PHI
1515 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1516 /* Only allow invariants here, otherwise we may break
1517 loop-closed SSA form. */
1518 && is_gimple_min_invariant (res
))
1522 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1524 fprintf (dump_file
, " (init_cond = ");
1525 print_generic_expr (dump_file
, init_cond
, 0);
1526 fprintf (dump_file
, "))\n");
1532 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1535 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1538 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1541 if (phi_loop
!= loop
)
1543 struct loop
*subloop
;
1544 tree evolution_fn
= analyze_scalar_evolution
1545 (phi_loop
, PHI_RESULT (loop_phi_node
));
1547 /* Dive one level deeper. */
1548 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1550 /* Interpret the subloop. */
1551 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1555 /* Otherwise really interpret the loop phi. */
1556 init_cond
= analyze_initial_condition (loop_phi_node
);
1557 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1559 /* Verify we maintained the correct initial condition throughout
1560 possible conversions in the SSA chain. */
1561 if (res
!= chrec_dont_know
)
1563 tree new_init
= res
;
1564 if (CONVERT_EXPR_P (res
)
1565 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1566 new_init
= fold_convert (TREE_TYPE (res
),
1567 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1568 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1569 new_init
= CHREC_LEFT (res
);
1570 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1571 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1572 || !operand_equal_p (init_cond
, new_init
, 0))
1573 return chrec_dont_know
;
1579 /* This function merges the branches of a condition-phi-node,
1580 contained in the outermost loop, and whose arguments are already
1584 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1586 int i
, n
= gimple_phi_num_args (condition_phi
);
1587 tree res
= chrec_not_analyzed_yet
;
1589 for (i
= 0; i
< n
; i
++)
1593 if (backedge_phi_arg_p (condition_phi
, i
))
1595 res
= chrec_dont_know
;
1599 branch_chrec
= analyze_scalar_evolution
1600 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1602 res
= chrec_merge (res
, branch_chrec
);
1608 /* Interpret the operation RHS1 OP RHS2. If we didn't
1609 analyze this node before, follow the definitions until ending
1610 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1611 return path, this function propagates evolutions (ala constant copy
1612 propagation). OPND1 is not a GIMPLE expression because we could
1613 analyze the effect of an inner loop: see interpret_loop_phi. */
1616 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1617 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1619 tree res
, chrec1
, chrec2
;
1622 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1624 if (is_gimple_min_invariant (rhs1
))
1625 return chrec_convert (type
, rhs1
, at_stmt
);
1627 if (code
== SSA_NAME
)
1628 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1631 if (code
== ASSERT_EXPR
)
1633 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1634 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1642 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1643 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1645 enum machine_mode mode
;
1646 HOST_WIDE_INT bitsize
, bitpos
;
1653 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1654 &bitsize
, &bitpos
, &offset
,
1655 &mode
, &unsignedp
, &volatilep
, false);
1657 if (TREE_CODE (base
) == MEM_REF
)
1659 rhs2
= TREE_OPERAND (base
, 1);
1660 rhs1
= TREE_OPERAND (base
, 0);
1662 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1663 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1664 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1665 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1666 chrec1
= instantiate_parameters (loop
, chrec1
);
1667 chrec2
= instantiate_parameters (loop
, chrec2
);
1668 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1672 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1673 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1677 if (offset
!= NULL_TREE
)
1679 chrec2
= analyze_scalar_evolution (loop
, offset
);
1680 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1681 chrec2
= instantiate_parameters (loop
, chrec2
);
1682 res
= chrec_fold_plus (type
, res
, chrec2
);
1687 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1689 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1690 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1691 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1692 chrec3
= instantiate_parameters (loop
, chrec3
);
1693 res
= chrec_fold_plus (type
, res
, chrec3
);
1697 res
= chrec_dont_know
;
1700 case POINTER_PLUS_EXPR
:
1701 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1702 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1703 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1704 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1705 chrec1
= instantiate_parameters (loop
, chrec1
);
1706 chrec2
= instantiate_parameters (loop
, chrec2
);
1707 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1711 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1712 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1713 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1714 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1715 chrec1
= instantiate_parameters (loop
, chrec1
);
1716 chrec2
= instantiate_parameters (loop
, chrec2
);
1717 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1721 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1722 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1723 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1724 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1725 chrec1
= instantiate_parameters (loop
, chrec1
);
1726 chrec2
= instantiate_parameters (loop
, chrec2
);
1727 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1731 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1732 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1733 /* TYPE may be integer, real or complex, so use fold_convert. */
1734 chrec1
= instantiate_parameters (loop
, chrec1
);
1735 res
= chrec_fold_multiply (type
, chrec1
,
1736 fold_convert (type
, integer_minus_one_node
));
1740 /* Handle ~X as -1 - X. */
1741 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1742 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1743 chrec1
= instantiate_parameters (loop
, chrec1
);
1744 res
= chrec_fold_minus (type
,
1745 fold_convert (type
, integer_minus_one_node
),
1750 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1751 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1752 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1753 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1754 chrec1
= instantiate_parameters (loop
, chrec1
);
1755 chrec2
= instantiate_parameters (loop
, chrec2
);
1756 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1760 /* In case we have a truncation of a widened operation that in
1761 the truncated type has undefined overflow behavior analyze
1762 the operation done in an unsigned type of the same precision
1763 as the final truncation. We cannot derive a scalar evolution
1764 for the widened operation but for the truncated result. */
1765 if (TREE_CODE (type
) == INTEGER_TYPE
1766 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1767 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1768 && TYPE_OVERFLOW_UNDEFINED (type
)
1769 && TREE_CODE (rhs1
) == SSA_NAME
1770 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1771 && is_gimple_assign (def
)
1772 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1773 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1775 tree utype
= unsigned_type_for (type
);
1776 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1777 gimple_assign_rhs1 (def
),
1778 gimple_assign_rhs_code (def
),
1779 gimple_assign_rhs2 (def
));
1782 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1783 res
= chrec_convert (type
, chrec1
, at_stmt
);
1787 res
= chrec_dont_know
;
1794 /* Interpret the expression EXPR. */
1797 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1799 enum tree_code code
;
1800 tree type
= TREE_TYPE (expr
), op0
, op1
;
1802 if (automatically_generated_chrec_p (expr
))
1805 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1806 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1807 return chrec_dont_know
;
1809 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1811 return interpret_rhs_expr (loop
, at_stmt
, type
,
1815 /* Interpret the rhs of the assignment STMT. */
1818 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1820 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1821 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1823 return interpret_rhs_expr (loop
, stmt
, type
,
1824 gimple_assign_rhs1 (stmt
), code
,
1825 gimple_assign_rhs2 (stmt
));
1830 /* This section contains all the entry points:
1831 - number_of_iterations_in_loop,
1832 - analyze_scalar_evolution,
1833 - instantiate_parameters.
1836 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1837 common ancestor of DEF_LOOP and USE_LOOP. */
1840 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1841 struct loop
*def_loop
,
1847 if (def_loop
== wrto_loop
)
1850 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1851 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1853 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1856 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1859 /* Helper recursive function. */
1862 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1864 tree type
= TREE_TYPE (var
);
1867 struct loop
*def_loop
;
1869 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1870 return chrec_dont_know
;
1872 if (TREE_CODE (var
) != SSA_NAME
)
1873 return interpret_expr (loop
, NULL
, var
);
1875 def
= SSA_NAME_DEF_STMT (var
);
1876 bb
= gimple_bb (def
);
1877 def_loop
= bb
? bb
->loop_father
: NULL
;
1880 || !flow_bb_inside_loop_p (loop
, bb
))
1882 /* Keep the symbolic form. */
1887 if (res
!= chrec_not_analyzed_yet
)
1889 if (loop
!= bb
->loop_father
)
1890 res
= compute_scalar_evolution_in_loop
1891 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1896 if (loop
!= def_loop
)
1898 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1899 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1904 switch (gimple_code (def
))
1907 res
= interpret_gimple_assign (loop
, def
);
1911 if (loop_phi_node_p (def
))
1912 res
= interpret_loop_phi (loop
, def
);
1914 res
= interpret_condition_phi (loop
, def
);
1918 res
= chrec_dont_know
;
1924 /* Keep the symbolic form. */
1925 if (res
== chrec_dont_know
)
1928 if (loop
== def_loop
)
1929 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1934 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1935 LOOP. LOOP is the loop in which the variable is used.
1937 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1938 pointer to the statement that uses this variable, in order to
1939 determine the evolution function of the variable, use the following
1942 loop_p loop = loop_containing_stmt (stmt);
1943 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1944 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1948 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1952 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1954 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1955 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1956 fprintf (dump_file
, " (scalar = ");
1957 print_generic_expr (dump_file
, var
, 0);
1958 fprintf (dump_file
, ")\n");
1961 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1962 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1964 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1965 fprintf (dump_file
, ")\n");
1970 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
1973 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
1975 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
1978 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1979 WRTO_LOOP (which should be a superloop of USE_LOOP)
1981 FOLDED_CASTS is set to true if resolve_mixers used
1982 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1983 at the moment in order to keep things simple).
1985 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1988 for (i = 0; i < 100; i++) -- loop 1
1990 for (j = 0; j < 100; j++) -- loop 2
1997 for (t = 0; t < 100; t++) -- loop 3
2004 Both k1 and k2 are invariants in loop3, thus
2005 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2006 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2008 As they are invariant, it does not matter whether we consider their
2009 usage in loop 3 or loop 2, hence
2010 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2011 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2012 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2013 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2015 Similarly for their evolutions with respect to loop 1. The values of K2
2016 in the use in loop 2 vary independently on loop 1, thus we cannot express
2017 the evolution with respect to loop 1:
2018 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2019 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2020 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2021 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2023 The value of k2 in the use in loop 1 is known, though:
2024 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2025 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2029 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2030 tree version
, bool *folded_casts
)
2033 tree ev
= version
, tmp
;
2035 /* We cannot just do
2037 tmp = analyze_scalar_evolution (use_loop, version);
2038 ev = resolve_mixers (wrto_loop, tmp);
2040 as resolve_mixers would query the scalar evolution with respect to
2041 wrto_loop. For example, in the situation described in the function
2042 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2045 analyze_scalar_evolution (use_loop, version) = k2
2047 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2048 is 100, which is a wrong result, since we are interested in the
2051 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2052 each time checking that there is no evolution in the inner loop. */
2055 *folded_casts
= false;
2058 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2059 ev
= resolve_mixers (use_loop
, tmp
);
2061 if (folded_casts
&& tmp
!= ev
)
2062 *folded_casts
= true;
2064 if (use_loop
== wrto_loop
)
2067 /* If the value of the use changes in the inner loop, we cannot express
2068 its value in the outer loop (we might try to return interval chrec,
2069 but we do not have a user for it anyway) */
2070 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2072 return chrec_dont_know
;
2074 use_loop
= loop_outer (use_loop
);
2079 /* Hashtable helpers for a temporary hash-table used when
2080 instantiating a CHREC or resolving mixers. For this use
2081 instantiated_below is always the same. */
2083 struct instantiate_cache_type
2086 vec
<scev_info_str
> entries
;
2088 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2089 ~instantiate_cache_type ();
2090 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2091 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2094 instantiate_cache_type::~instantiate_cache_type ()
2103 /* Cache to avoid infinite recursion when instantiating an SSA name.
2104 Live during the outermost instantiate_scev or resolve_mixers call. */
2105 static instantiate_cache_type
*global_cache
;
2107 /* Computes a hash function for database element ELT. */
2109 static inline hashval_t
2110 hash_idx_scev_info (const void *elt_
)
2112 unsigned idx
= ((size_t) elt_
) - 2;
2113 return hash_scev_info (&global_cache
->entries
[idx
]);
2116 /* Compares database elements E1 and E2. */
2119 eq_idx_scev_info (const void *e1
, const void *e2
)
2121 unsigned idx1
= ((size_t) e1
) - 2;
2122 return eq_scev_info (&global_cache
->entries
[idx1
], e2
);
2125 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2128 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2129 tree name
, basic_block instantiate_below
)
2133 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2134 cache
.entries
.create (10);
2138 e
.name_version
= SSA_NAME_VERSION (name
);
2139 e
.instantiated_below
= instantiate_below
->index
;
2140 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2141 hash_scev_info (&e
), INSERT
);
2144 e
.chrec
= chrec_not_analyzed_yet
;
2145 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2146 cache
.entries
.safe_push (e
);
2149 return ((size_t)*slot
) - 2;
2153 /* Return the closed_loop_phi node for VAR. If there is none, return
2157 loop_closed_phi_def (tree var
)
2162 gimple_stmt_iterator psi
;
2164 if (var
== NULL_TREE
2165 || TREE_CODE (var
) != SSA_NAME
)
2168 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2169 exit
= single_exit (loop
);
2173 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2175 phi
= gsi_stmt (psi
);
2176 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2177 return PHI_RESULT (phi
);
2183 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2186 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2187 and EVOLUTION_LOOP, that were left under a symbolic form.
2189 CHREC is an SSA_NAME to be instantiated.
2191 CACHE is the cache of already instantiated values.
2193 FOLD_CONVERSIONS should be set to true when the conversions that
2194 may wrap in signed/pointer type are folded, as long as the value of
2195 the chrec is preserved.
2197 SIZE_EXPR is used for computing the size of the expression to be
2198 instantiated, and to stop if it exceeds some limit. */
2201 instantiate_scev_name (basic_block instantiate_below
,
2202 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2204 bool fold_conversions
,
2208 struct loop
*def_loop
;
2209 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2211 /* A parameter (or loop invariant and we do not want to include
2212 evolutions in outer loops), nothing to do. */
2214 || loop_depth (def_bb
->loop_father
) == 0
2215 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2218 /* We cache the value of instantiated variable to avoid exponential
2219 time complexity due to reevaluations. We also store the convenient
2220 value in the cache in order to prevent infinite recursion -- we do
2221 not want to instantiate the SSA_NAME if it is in a mixer
2222 structure. This is used for avoiding the instantiation of
2223 recursively defined functions, such as:
2225 | a_2 -> {0, +, 1, +, a_2}_1 */
2227 unsigned si
= get_instantiated_value_entry (*global_cache
,
2228 chrec
, instantiate_below
);
2229 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2230 return global_cache
->get (si
);
2232 /* On recursion return chrec_dont_know. */
2233 global_cache
->set (si
, chrec_dont_know
);
2235 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2237 /* If the analysis yields a parametric chrec, instantiate the
2239 res
= analyze_scalar_evolution (def_loop
, chrec
);
2241 /* Don't instantiate default definitions. */
2242 if (TREE_CODE (res
) == SSA_NAME
2243 && SSA_NAME_IS_DEFAULT_DEF (res
))
2246 /* Don't instantiate loop-closed-ssa phi nodes. */
2247 else if (TREE_CODE (res
) == SSA_NAME
2248 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2249 > loop_depth (def_loop
))
2252 res
= loop_closed_phi_def (chrec
);
2256 /* When there is no loop_closed_phi_def, it means that the
2257 variable is not used after the loop: try to still compute the
2258 value of the variable when exiting the loop. */
2259 if (res
== NULL_TREE
)
2261 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2262 res
= analyze_scalar_evolution (loop
, chrec
);
2263 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2264 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2266 fold_conversions
, size_expr
);
2268 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2269 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2270 res
= chrec_dont_know
;
2273 else if (res
!= chrec_dont_know
)
2276 && def_bb
->loop_father
!= inner_loop
2277 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2278 /* ??? We could try to compute the overall effect of the loop here. */
2279 res
= chrec_dont_know
;
2281 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2283 fold_conversions
, size_expr
);
2286 /* Store the correct value to the cache. */
2287 global_cache
->set (si
, res
);
2291 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2292 and EVOLUTION_LOOP, that were left under a symbolic form.
2294 CHREC is a polynomial chain of recurrence to be instantiated.
2296 CACHE is the cache of already instantiated values.
2298 FOLD_CONVERSIONS should be set to true when the conversions that
2299 may wrap in signed/pointer type are folded, as long as the value of
2300 the chrec is preserved.
2302 SIZE_EXPR is used for computing the size of the expression to be
2303 instantiated, and to stop if it exceeds some limit. */
2306 instantiate_scev_poly (basic_block instantiate_below
,
2307 struct loop
*evolution_loop
, struct loop
*,
2308 tree chrec
, bool fold_conversions
, int size_expr
)
2311 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2312 get_chrec_loop (chrec
),
2313 CHREC_LEFT (chrec
), fold_conversions
,
2315 if (op0
== chrec_dont_know
)
2316 return chrec_dont_know
;
2318 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2319 get_chrec_loop (chrec
),
2320 CHREC_RIGHT (chrec
), fold_conversions
,
2322 if (op1
== chrec_dont_know
)
2323 return chrec_dont_know
;
2325 if (CHREC_LEFT (chrec
) != op0
2326 || CHREC_RIGHT (chrec
) != op1
)
2328 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2329 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2335 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2336 and EVOLUTION_LOOP, that were left under a symbolic form.
2338 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2340 CACHE is the cache of already instantiated values.
2342 FOLD_CONVERSIONS should be set to true when the conversions that
2343 may wrap in signed/pointer type are folded, as long as the value of
2344 the chrec is preserved.
2346 SIZE_EXPR is used for computing the size of the expression to be
2347 instantiated, and to stop if it exceeds some limit. */
2350 instantiate_scev_binary (basic_block instantiate_below
,
2351 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2352 tree chrec
, enum tree_code code
,
2353 tree type
, tree c0
, tree c1
,
2354 bool fold_conversions
, int size_expr
)
2357 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2358 c0
, fold_conversions
, size_expr
);
2359 if (op0
== chrec_dont_know
)
2360 return chrec_dont_know
;
2362 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2363 c1
, fold_conversions
, size_expr
);
2364 if (op1
== chrec_dont_know
)
2365 return chrec_dont_know
;
2370 op0
= chrec_convert (type
, op0
, NULL
);
2371 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2375 case POINTER_PLUS_EXPR
:
2377 return chrec_fold_plus (type
, op0
, op1
);
2380 return chrec_fold_minus (type
, op0
, op1
);
2383 return chrec_fold_multiply (type
, op0
, op1
);
2390 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2393 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2394 and EVOLUTION_LOOP, that were left under a symbolic form.
2396 "CHREC" is an array reference to be instantiated.
2398 CACHE is the cache of already instantiated values.
2400 FOLD_CONVERSIONS should be set to true when the conversions that
2401 may wrap in signed/pointer type are folded, as long as the value of
2402 the chrec is preserved.
2404 SIZE_EXPR is used for computing the size of the expression to be
2405 instantiated, and to stop if it exceeds some limit. */
2408 instantiate_array_ref (basic_block instantiate_below
,
2409 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2410 tree chrec
, bool fold_conversions
, int size_expr
)
2413 tree index
= TREE_OPERAND (chrec
, 1);
2414 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2416 fold_conversions
, size_expr
);
2418 if (op1
== chrec_dont_know
)
2419 return chrec_dont_know
;
2421 if (chrec
&& op1
== index
)
2424 res
= unshare_expr (chrec
);
2425 TREE_OPERAND (res
, 1) = op1
;
2429 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2430 and EVOLUTION_LOOP, that were left under a symbolic form.
2432 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2435 CACHE is the cache of already instantiated values.
2437 FOLD_CONVERSIONS should be set to true when the conversions that
2438 may wrap in signed/pointer type are folded, as long as the value of
2439 the chrec is preserved.
2441 SIZE_EXPR is used for computing the size of the expression to be
2442 instantiated, and to stop if it exceeds some limit. */
2445 instantiate_scev_convert (basic_block instantiate_below
,
2446 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2447 tree chrec
, tree type
, tree op
,
2448 bool fold_conversions
, int size_expr
)
2450 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2452 fold_conversions
, size_expr
);
2454 if (op0
== chrec_dont_know
)
2455 return chrec_dont_know
;
2457 if (fold_conversions
)
2459 tree tmp
= chrec_convert_aggressive (type
, op0
);
2464 if (chrec
&& op0
== op
)
2467 /* If we used chrec_convert_aggressive, we can no longer assume that
2468 signed chrecs do not overflow, as chrec_convert does, so avoid
2469 calling it in that case. */
2470 if (fold_conversions
)
2471 return fold_convert (type
, op0
);
2473 return chrec_convert (type
, op0
, NULL
);
2476 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2477 and EVOLUTION_LOOP, that were left under a symbolic form.
2479 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2480 Handle ~X as -1 - X.
2481 Handle -X as -1 * X.
2483 CACHE is the cache of already instantiated values.
2485 FOLD_CONVERSIONS should be set to true when the conversions that
2486 may wrap in signed/pointer type are folded, as long as the value of
2487 the chrec is preserved.
2489 SIZE_EXPR is used for computing the size of the expression to be
2490 instantiated, and to stop if it exceeds some limit. */
2493 instantiate_scev_not (basic_block instantiate_below
,
2494 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2496 enum tree_code code
, tree type
, tree op
,
2497 bool fold_conversions
, int size_expr
)
2499 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2501 fold_conversions
, size_expr
);
2503 if (op0
== chrec_dont_know
)
2504 return chrec_dont_know
;
2508 op0
= chrec_convert (type
, op0
, NULL
);
2513 return chrec_fold_minus
2514 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2517 return chrec_fold_multiply
2518 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2525 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2528 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2529 and EVOLUTION_LOOP, that were left under a symbolic form.
2531 CHREC is an expression with 3 operands to be instantiated.
2533 CACHE is the cache of already instantiated values.
2535 FOLD_CONVERSIONS should be set to true when the conversions that
2536 may wrap in signed/pointer type are folded, as long as the value of
2537 the chrec is preserved.
2539 SIZE_EXPR is used for computing the size of the expression to be
2540 instantiated, and to stop if it exceeds some limit. */
2543 instantiate_scev_3 (basic_block instantiate_below
,
2544 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2546 bool fold_conversions
, int size_expr
)
2549 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2550 inner_loop
, TREE_OPERAND (chrec
, 0),
2551 fold_conversions
, size_expr
);
2552 if (op0
== chrec_dont_know
)
2553 return chrec_dont_know
;
2555 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2556 inner_loop
, TREE_OPERAND (chrec
, 1),
2557 fold_conversions
, size_expr
);
2558 if (op1
== chrec_dont_know
)
2559 return chrec_dont_know
;
2561 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2562 inner_loop
, TREE_OPERAND (chrec
, 2),
2563 fold_conversions
, size_expr
);
2564 if (op2
== chrec_dont_know
)
2565 return chrec_dont_know
;
2567 if (op0
== TREE_OPERAND (chrec
, 0)
2568 && op1
== TREE_OPERAND (chrec
, 1)
2569 && op2
== TREE_OPERAND (chrec
, 2))
2572 return fold_build3 (TREE_CODE (chrec
),
2573 TREE_TYPE (chrec
), op0
, op1
, op2
);
2576 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2577 and EVOLUTION_LOOP, that were left under a symbolic form.
2579 CHREC is an expression with 2 operands to be instantiated.
2581 CACHE is the cache of already instantiated values.
2583 FOLD_CONVERSIONS should be set to true when the conversions that
2584 may wrap in signed/pointer type are folded, as long as the value of
2585 the chrec is preserved.
2587 SIZE_EXPR is used for computing the size of the expression to be
2588 instantiated, and to stop if it exceeds some limit. */
2591 instantiate_scev_2 (basic_block instantiate_below
,
2592 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2594 bool fold_conversions
, int size_expr
)
2597 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2598 inner_loop
, TREE_OPERAND (chrec
, 0),
2599 fold_conversions
, size_expr
);
2600 if (op0
== chrec_dont_know
)
2601 return chrec_dont_know
;
2603 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2604 inner_loop
, TREE_OPERAND (chrec
, 1),
2605 fold_conversions
, size_expr
);
2606 if (op1
== chrec_dont_know
)
2607 return chrec_dont_know
;
2609 if (op0
== TREE_OPERAND (chrec
, 0)
2610 && op1
== TREE_OPERAND (chrec
, 1))
2613 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2616 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2617 and EVOLUTION_LOOP, that were left under a symbolic form.
2619 CHREC is an expression with 2 operands to be instantiated.
2621 CACHE is the cache of already instantiated values.
2623 FOLD_CONVERSIONS should be set to true when the conversions that
2624 may wrap in signed/pointer type are folded, as long as the value of
2625 the chrec is preserved.
2627 SIZE_EXPR is used for computing the size of the expression to be
2628 instantiated, and to stop if it exceeds some limit. */
2631 instantiate_scev_1 (basic_block instantiate_below
,
2632 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2634 bool fold_conversions
, int size_expr
)
2636 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2637 inner_loop
, TREE_OPERAND (chrec
, 0),
2638 fold_conversions
, size_expr
);
2640 if (op0
== chrec_dont_know
)
2641 return chrec_dont_know
;
2643 if (op0
== TREE_OPERAND (chrec
, 0))
2646 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2649 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2650 and EVOLUTION_LOOP, that were left under a symbolic form.
2652 CHREC is the scalar evolution to instantiate.
2654 CACHE is the cache of already instantiated values.
2656 FOLD_CONVERSIONS should be set to true when the conversions that
2657 may wrap in signed/pointer type are folded, as long as the value of
2658 the chrec is preserved.
2660 SIZE_EXPR is used for computing the size of the expression to be
2661 instantiated, and to stop if it exceeds some limit. */
2664 instantiate_scev_r (basic_block instantiate_below
,
2665 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2667 bool fold_conversions
, int size_expr
)
2669 /* Give up if the expression is larger than the MAX that we allow. */
2670 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2671 return chrec_dont_know
;
2673 if (chrec
== NULL_TREE
2674 || automatically_generated_chrec_p (chrec
)
2675 || is_gimple_min_invariant (chrec
))
2678 switch (TREE_CODE (chrec
))
2681 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2683 fold_conversions
, size_expr
);
2685 case POLYNOMIAL_CHREC
:
2686 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2688 fold_conversions
, size_expr
);
2690 case POINTER_PLUS_EXPR
:
2694 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2696 TREE_CODE (chrec
), chrec_type (chrec
),
2697 TREE_OPERAND (chrec
, 0),
2698 TREE_OPERAND (chrec
, 1),
2699 fold_conversions
, size_expr
);
2702 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2704 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2705 fold_conversions
, size_expr
);
2709 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2711 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2712 TREE_OPERAND (chrec
, 0),
2713 fold_conversions
, size_expr
);
2716 case SCEV_NOT_KNOWN
:
2717 return chrec_dont_know
;
2723 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2725 fold_conversions
, size_expr
);
2731 if (VL_EXP_CLASS_P (chrec
))
2732 return chrec_dont_know
;
2734 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2737 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2739 fold_conversions
, size_expr
);
2742 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2744 fold_conversions
, size_expr
);
2747 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2749 fold_conversions
, size_expr
);
2758 /* Too complicated to handle. */
2759 return chrec_dont_know
;
2762 /* Analyze all the parameters of the chrec that were left under a
2763 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2764 recursive instantiation of parameters: a parameter is a variable
2765 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2766 a function parameter. */
2769 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2774 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2776 fprintf (dump_file
, "(instantiate_scev \n");
2777 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2778 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2779 fprintf (dump_file
, " (chrec = ");
2780 print_generic_expr (dump_file
, chrec
, 0);
2781 fprintf (dump_file
, ")\n");
2787 global_cache
= new instantiate_cache_type
;
2791 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2792 NULL
, chrec
, false, 0);
2796 delete global_cache
;
2797 global_cache
= NULL
;
2800 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2802 fprintf (dump_file
, " (res = ");
2803 print_generic_expr (dump_file
, res
, 0);
2804 fprintf (dump_file
, "))\n");
2810 /* Similar to instantiate_parameters, but does not introduce the
2811 evolutions in outer loops for LOOP invariants in CHREC, and does not
2812 care about causing overflows, as long as they do not affect value
2813 of an expression. */
2816 resolve_mixers (struct loop
*loop
, tree chrec
)
2821 global_cache
= new instantiate_cache_type
;
2825 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2830 delete global_cache
;
2831 global_cache
= NULL
;
2837 /* Entry point for the analysis of the number of iterations pass.
2838 This function tries to safely approximate the number of iterations
2839 the loop will run. When this property is not decidable at compile
2840 time, the result is chrec_dont_know. Otherwise the result is a
2841 scalar or a symbolic parameter. When the number of iterations may
2842 be equal to zero and the property cannot be determined at compile
2843 time, the result is a COND_EXPR that represents in a symbolic form
2844 the conditions under which the number of iterations is not zero.
2846 Example of analysis: suppose that the loop has an exit condition:
2848 "if (b > 49) goto end_loop;"
2850 and that in a previous analysis we have determined that the
2851 variable 'b' has an evolution function:
2853 "EF = {23, +, 5}_2".
2855 When we evaluate the function at the point 5, i.e. the value of the
2856 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2857 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2858 the loop body has been executed 6 times. */
2861 number_of_latch_executions (struct loop
*loop
)
2864 struct tree_niter_desc niter_desc
;
2868 /* Determine whether the number of iterations in loop has already
2870 res
= loop
->nb_iterations
;
2874 may_be_zero
= NULL_TREE
;
2876 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2877 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2879 res
= chrec_dont_know
;
2880 exit
= single_exit (loop
);
2882 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2884 may_be_zero
= niter_desc
.may_be_zero
;
2885 res
= niter_desc
.niter
;
2888 if (res
== chrec_dont_know
2890 || integer_zerop (may_be_zero
))
2892 else if (integer_nonzerop (may_be_zero
))
2893 res
= build_int_cst (TREE_TYPE (res
), 0);
2895 else if (COMPARISON_CLASS_P (may_be_zero
))
2896 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2897 build_int_cst (TREE_TYPE (res
), 0), res
);
2899 res
= chrec_dont_know
;
2901 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2903 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2904 print_generic_expr (dump_file
, res
, 0);
2905 fprintf (dump_file
, "))\n");
2908 loop
->nb_iterations
= res
;
2912 /* Returns the number of executions of the exit condition of LOOP,
2913 i.e., the number by one higher than number_of_latch_executions.
2914 Note that unlike number_of_latch_executions, this number does
2915 not necessarily fit in the unsigned variant of the type of
2916 the control variable -- if the number of iterations is a constant,
2917 we return chrec_dont_know if adding one to number_of_latch_executions
2918 overflows; however, in case the number of iterations is symbolic
2919 expression, the caller is responsible for dealing with this
2920 the possible overflow. */
2923 number_of_exit_cond_executions (struct loop
*loop
)
2925 tree ret
= number_of_latch_executions (loop
);
2926 tree type
= chrec_type (ret
);
2928 if (chrec_contains_undetermined (ret
))
2931 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2932 if (TREE_CODE (ret
) == INTEGER_CST
2933 && TREE_OVERFLOW (ret
))
2934 return chrec_dont_know
;
2941 /* Counters for the stats. */
2947 unsigned nb_affine_multivar
;
2948 unsigned nb_higher_poly
;
2949 unsigned nb_chrec_dont_know
;
2950 unsigned nb_undetermined
;
2953 /* Reset the counters. */
2956 reset_chrecs_counters (struct chrec_stats
*stats
)
2958 stats
->nb_chrecs
= 0;
2959 stats
->nb_affine
= 0;
2960 stats
->nb_affine_multivar
= 0;
2961 stats
->nb_higher_poly
= 0;
2962 stats
->nb_chrec_dont_know
= 0;
2963 stats
->nb_undetermined
= 0;
2966 /* Dump the contents of a CHREC_STATS structure. */
2969 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2971 fprintf (file
, "\n(\n");
2972 fprintf (file
, "-----------------------------------------\n");
2973 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2974 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2975 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2976 stats
->nb_higher_poly
);
2977 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2978 fprintf (file
, "-----------------------------------------\n");
2979 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2980 fprintf (file
, "%d\twith undetermined coefficients\n",
2981 stats
->nb_undetermined
);
2982 fprintf (file
, "-----------------------------------------\n");
2983 fprintf (file
, "%d\tchrecs in the scev database\n",
2984 (int) htab_elements (scalar_evolution_info
));
2985 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2986 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2987 fprintf (file
, "-----------------------------------------\n");
2988 fprintf (file
, ")\n\n");
2991 /* Gather statistics about CHREC. */
2994 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2996 if (dump_file
&& (dump_flags
& TDF_STATS
))
2998 fprintf (dump_file
, "(classify_chrec ");
2999 print_generic_expr (dump_file
, chrec
, 0);
3000 fprintf (dump_file
, "\n");
3005 if (chrec
== NULL_TREE
)
3007 stats
->nb_undetermined
++;
3011 switch (TREE_CODE (chrec
))
3013 case POLYNOMIAL_CHREC
:
3014 if (evolution_function_is_affine_p (chrec
))
3016 if (dump_file
&& (dump_flags
& TDF_STATS
))
3017 fprintf (dump_file
, " affine_univariate\n");
3020 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3022 if (dump_file
&& (dump_flags
& TDF_STATS
))
3023 fprintf (dump_file
, " affine_multivariate\n");
3024 stats
->nb_affine_multivar
++;
3028 if (dump_file
&& (dump_flags
& TDF_STATS
))
3029 fprintf (dump_file
, " higher_degree_polynomial\n");
3030 stats
->nb_higher_poly
++;
3039 if (chrec_contains_undetermined (chrec
))
3041 if (dump_file
&& (dump_flags
& TDF_STATS
))
3042 fprintf (dump_file
, " undetermined\n");
3043 stats
->nb_undetermined
++;
3046 if (dump_file
&& (dump_flags
& TDF_STATS
))
3047 fprintf (dump_file
, ")\n");
3050 /* Callback for htab_traverse, gathers information on chrecs in the
3054 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
3056 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
3058 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3063 /* Classify the chrecs of the whole database. */
3066 gather_stats_on_scev_database (void)
3068 struct chrec_stats stats
;
3073 reset_chrecs_counters (&stats
);
3075 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3078 dump_chrecs_stats (dump_file
, &stats
);
3086 initialize_scalar_evolutions_analyzer (void)
3088 /* The elements below are unique. */
3089 if (chrec_dont_know
== NULL_TREE
)
3091 chrec_not_analyzed_yet
= NULL_TREE
;
3092 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3093 chrec_known
= make_node (SCEV_KNOWN
);
3094 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3095 TREE_TYPE (chrec_known
) = void_type_node
;
3099 /* Initialize the analysis of scalar evolutions for LOOPS. */
3102 scev_initialize (void)
3108 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3111 initialize_scalar_evolutions_analyzer ();
3113 FOR_EACH_LOOP (li
, loop
, 0)
3115 loop
->nb_iterations
= NULL_TREE
;
3119 /* Return true if SCEV is initialized. */
3122 scev_initialized_p (void)
3124 return scalar_evolution_info
!= NULL
;
3127 /* Cleans up the information cached by the scalar evolutions analysis
3128 in the hash table. */
3131 scev_reset_htab (void)
3133 if (!scalar_evolution_info
)
3136 htab_empty (scalar_evolution_info
);
3139 /* Cleans up the information cached by the scalar evolutions analysis
3140 in the hash table and in the loop->nb_iterations. */
3153 FOR_EACH_LOOP (li
, loop
, 0)
3155 loop
->nb_iterations
= NULL_TREE
;
3159 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3160 respect to WRTO_LOOP and returns its base and step in IV if possible
3161 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3162 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3163 invariant in LOOP. Otherwise we require it to be an integer constant.
3165 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3166 because it is computed in signed arithmetics). Consequently, adding an
3169 for (i = IV->base; ; i += IV->step)
3171 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3172 false for the type of the induction variable, or you can prove that i does
3173 not wrap by some other argument. Otherwise, this might introduce undefined
3176 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3178 must be used instead. */
3181 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3182 affine_iv
*iv
, bool allow_nonconstant_step
)
3187 iv
->base
= NULL_TREE
;
3188 iv
->step
= NULL_TREE
;
3189 iv
->no_overflow
= false;
3191 type
= TREE_TYPE (op
);
3192 if (!POINTER_TYPE_P (type
)
3193 && !INTEGRAL_TYPE_P (type
))
3196 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3198 if (chrec_contains_undetermined (ev
)
3199 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3202 if (tree_does_not_contain_chrecs (ev
))
3205 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3206 iv
->no_overflow
= true;
3210 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3211 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3214 iv
->step
= CHREC_RIGHT (ev
);
3215 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3216 || tree_contains_chrecs (iv
->step
, NULL
))
3219 iv
->base
= CHREC_LEFT (ev
);
3220 if (tree_contains_chrecs (iv
->base
, NULL
))
3223 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3228 /* Finalize the scalar evolution analysis. */
3231 scev_finalize (void)
3233 if (!scalar_evolution_info
)
3235 htab_delete (scalar_evolution_info
);
3236 scalar_evolution_info
= NULL
;
3239 /* Returns true if the expression EXPR is considered to be too expensive
3240 for scev_const_prop. */
3243 expression_expensive_p (tree expr
)
3245 enum tree_code code
;
3247 if (is_gimple_val (expr
))
3250 code
= TREE_CODE (expr
);
3251 if (code
== TRUNC_DIV_EXPR
3252 || code
== CEIL_DIV_EXPR
3253 || code
== FLOOR_DIV_EXPR
3254 || code
== ROUND_DIV_EXPR
3255 || code
== TRUNC_MOD_EXPR
3256 || code
== CEIL_MOD_EXPR
3257 || code
== FLOOR_MOD_EXPR
3258 || code
== ROUND_MOD_EXPR
3259 || code
== EXACT_DIV_EXPR
)
3261 /* Division by power of two is usually cheap, so we allow it.
3262 Forbid anything else. */
3263 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3267 switch (TREE_CODE_CLASS (code
))
3270 case tcc_comparison
:
3271 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3276 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3283 /* Replace ssa names for that scev can prove they are constant by the
3284 appropriate constants. Also perform final value replacement in loops,
3285 in case the replacement expressions are cheap.
3287 We only consider SSA names defined by phi nodes; rest is left to the
3288 ordinary constant propagation pass. */
3291 scev_const_prop (void)
3294 tree name
, type
, ev
;
3296 struct loop
*loop
, *ex_loop
;
3297 bitmap ssa_names_to_remove
= NULL
;
3300 gimple_stmt_iterator psi
;
3302 if (number_of_loops (cfun
) <= 1)
3307 loop
= bb
->loop_father
;
3309 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3311 phi
= gsi_stmt (psi
);
3312 name
= PHI_RESULT (phi
);
3314 if (virtual_operand_p (name
))
3317 type
= TREE_TYPE (name
);
3319 if (!POINTER_TYPE_P (type
)
3320 && !INTEGRAL_TYPE_P (type
))
3323 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3324 if (!is_gimple_min_invariant (ev
)
3325 || !may_propagate_copy (name
, ev
))
3328 /* Replace the uses of the name. */
3330 replace_uses_by (name
, ev
);
3332 if (!ssa_names_to_remove
)
3333 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3334 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3338 /* Remove the ssa names that were replaced by constants. We do not
3339 remove them directly in the previous cycle, since this
3340 invalidates scev cache. */
3341 if (ssa_names_to_remove
)
3345 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3347 gimple_stmt_iterator psi
;
3348 name
= ssa_name (i
);
3349 phi
= SSA_NAME_DEF_STMT (name
);
3351 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3352 psi
= gsi_for_stmt (phi
);
3353 remove_phi_node (&psi
, true);
3356 BITMAP_FREE (ssa_names_to_remove
);
3360 /* Now the regular final value replacement. */
3361 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3364 tree def
, rslt
, niter
;
3365 gimple_stmt_iterator bsi
;
3367 /* If we do not know exact number of iterations of the loop, we cannot
3368 replace the final value. */
3369 exit
= single_exit (loop
);
3373 niter
= number_of_latch_executions (loop
);
3374 if (niter
== chrec_dont_know
)
3377 /* Ensure that it is possible to insert new statements somewhere. */
3378 if (!single_pred_p (exit
->dest
))
3379 split_loop_exit_edge (exit
);
3380 bsi
= gsi_after_labels (exit
->dest
);
3382 ex_loop
= superloop_at_depth (loop
,
3383 loop_depth (exit
->dest
->loop_father
) + 1);
3385 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3387 phi
= gsi_stmt (psi
);
3388 rslt
= PHI_RESULT (phi
);
3389 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3390 if (virtual_operand_p (def
))
3396 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3397 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3403 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3404 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3405 if (!tree_does_not_contain_chrecs (def
)
3406 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3407 /* Moving the computation from the loop may prolong life range
3408 of some ssa names, which may cause problems if they appear
3409 on abnormal edges. */
3410 || contains_abnormal_ssa_name_p (def
)
3411 /* Do not emit expensive expressions. The rationale is that
3412 when someone writes a code like
3414 while (n > 45) n -= 45;
3416 he probably knows that n is not large, and does not want it
3417 to be turned into n %= 45. */
3418 || expression_expensive_p (def
))
3420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3422 fprintf (dump_file
, "not replacing:\n ");
3423 print_gimple_stmt (dump_file
, phi
, 0, 0);
3424 fprintf (dump_file
, "\n");
3430 /* Eliminate the PHI node and replace it by a computation outside
3434 fprintf (dump_file
, "\nfinal value replacement:\n ");
3435 print_gimple_stmt (dump_file
, phi
, 0, 0);
3436 fprintf (dump_file
, " with\n ");
3438 def
= unshare_expr (def
);
3439 remove_phi_node (&psi
, false);
3441 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3442 true, GSI_SAME_STMT
);
3443 ass
= gimple_build_assign (rslt
, def
);
3444 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3447 print_gimple_stmt (dump_file
, ass
, 0, 0);
3448 fprintf (dump_file
, "\n");
3455 #include "gt-tree-scalar-evolution.h"