1 /* Scalar evolution detector.
2 Copyright (C) 2003-2019 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"
262 #include "optabs-query.h"
266 #include "gimple-pretty-print.h"
267 #include "fold-const.h"
268 #include "gimplify.h"
269 #include "gimple-iterator.h"
270 #include "gimplify-me.h"
271 #include "tree-cfg.h"
272 #include "tree-ssa-loop-ivopts.h"
273 #include "tree-ssa-loop-manip.h"
274 #include "tree-ssa-loop-niter.h"
275 #include "tree-ssa-loop.h"
276 #include "tree-ssa.h"
278 #include "tree-chrec.h"
279 #include "tree-affine.h"
280 #include "tree-scalar-evolution.h"
281 #include "dumpfile.h"
283 #include "tree-ssa-propagate.h"
284 #include "gimple-fold.h"
285 #include "tree-into-ssa.h"
286 #include "builtins.h"
287 #include "case-cfn-macros.h"
289 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
);
290 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
293 /* The cached information about an SSA name with version NAME_VERSION,
294 claiming that below basic block with index INSTANTIATED_BELOW, the
295 value of the SSA name can be expressed as CHREC. */
297 struct GTY((for_user
)) scev_info_str
{
298 unsigned int name_version
;
299 int instantiated_below
;
303 /* Counters for the scev database. */
304 static unsigned nb_set_scev
= 0;
305 static unsigned nb_get_scev
= 0;
307 /* The following trees are unique elements. Thus the comparison of
308 another element to these elements should be done on the pointer to
309 these trees, and not on their value. */
311 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
312 tree chrec_not_analyzed_yet
;
314 /* Reserved to the cases where the analyzer has detected an
315 undecidable property at compile time. */
316 tree chrec_dont_know
;
318 /* When the analyzer has detected that a property will never
319 happen, then it qualifies it with chrec_known. */
322 struct scev_info_hasher
: ggc_ptr_hash
<scev_info_str
>
324 static hashval_t
hash (scev_info_str
*i
);
325 static bool equal (const scev_info_str
*a
, const scev_info_str
*b
);
328 static GTY (()) hash_table
<scev_info_hasher
> *scalar_evolution_info
;
331 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
333 static inline struct scev_info_str
*
334 new_scev_info_str (basic_block instantiated_below
, tree var
)
336 struct scev_info_str
*res
;
338 res
= ggc_alloc
<scev_info_str
> ();
339 res
->name_version
= SSA_NAME_VERSION (var
);
340 res
->chrec
= chrec_not_analyzed_yet
;
341 res
->instantiated_below
= instantiated_below
->index
;
346 /* Computes a hash function for database element ELT. */
349 scev_info_hasher::hash (scev_info_str
*elt
)
351 return elt
->name_version
^ elt
->instantiated_below
;
354 /* Compares database elements E1 and E2. */
357 scev_info_hasher::equal (const scev_info_str
*elt1
, const scev_info_str
*elt2
)
359 return (elt1
->name_version
== elt2
->name_version
360 && elt1
->instantiated_below
== elt2
->instantiated_below
);
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
;
372 tmp
.name_version
= SSA_NAME_VERSION (var
);
373 tmp
.instantiated_below
= instantiated_below
->index
;
374 scev_info_str
**slot
= scalar_evolution_info
->find_slot (&tmp
, INSERT
);
377 *slot
= new_scev_info_str (instantiated_below
, var
);
384 /* Hashtable helpers for a temporary hash-table used when
385 analyzing a scalar evolution, instantiating a CHREC or
388 struct instantiate_cache_type
391 vec
<scev_info_str
> entries
;
393 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
394 ~instantiate_cache_type ();
395 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
396 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
399 instantiate_cache_type::~instantiate_cache_type ()
408 /* Cache to avoid infinite recursion when instantiating an SSA name.
409 Live during the outermost analyze_scalar_evolution, instantiate_scev
410 or resolve_mixers call. */
411 static instantiate_cache_type
*global_cache
;
414 /* Return true when CHREC contains symbolic names defined in
418 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
422 if (chrec
== NULL_TREE
)
425 if (is_gimple_min_invariant (chrec
))
428 if (TREE_CODE (chrec
) == SSA_NAME
)
431 loop_p def_loop
, loop
;
433 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
436 def
= SSA_NAME_DEF_STMT (chrec
);
437 def_loop
= loop_containing_stmt (def
);
438 loop
= get_loop (cfun
, loop_nb
);
440 if (def_loop
== NULL
)
443 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
449 n
= TREE_OPERAND_LENGTH (chrec
);
450 for (i
= 0; i
< n
; i
++)
451 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
457 /* Return true when PHI is a loop-phi-node. */
460 loop_phi_node_p (gimple
*phi
)
462 /* The implementation of this function is based on the following
463 property: "all the loop-phi-nodes of a loop are contained in the
464 loop's header basic block". */
466 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
469 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
470 In general, in the case of multivariate evolutions we want to get
471 the evolution in different loops. LOOP specifies the level for
472 which to get the evolution.
476 | for (j = 0; j < 100; j++)
478 | for (k = 0; k < 100; k++)
480 | i = k + j; - Here the value of i is a function of j, k.
482 | ... = i - Here the value of i is a function of j.
484 | ... = i - Here the value of i is a scalar.
490 | i_1 = phi (i_0, i_2)
494 This loop has the same effect as:
495 LOOP_1 has the same effect as:
499 The overall effect of the loop, "i_0 + 20" in the previous example,
500 is obtained by passing in the parameters: LOOP = 1,
501 EVOLUTION_FN = {i_0, +, 2}_1.
505 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
509 if (evolution_fn
== chrec_dont_know
)
510 return chrec_dont_know
;
512 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
514 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
516 if (inner_loop
== loop
517 || flow_loop_nested_p (loop
, inner_loop
))
519 tree nb_iter
= number_of_latch_executions (inner_loop
);
521 if (nb_iter
== chrec_dont_know
)
522 return chrec_dont_know
;
527 /* evolution_fn is the evolution function in LOOP. Get
528 its value in the nb_iter-th iteration. */
529 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
531 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
532 res
= instantiate_parameters (loop
, res
);
534 /* Continue the computation until ending on a parent of LOOP. */
535 return compute_overall_effect_of_inner_loop (loop
, res
);
542 /* If the evolution function is an invariant, there is nothing to do. */
543 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
547 return chrec_dont_know
;
550 /* Associate CHREC to SCALAR. */
553 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
557 if (TREE_CODE (scalar
) != SSA_NAME
)
560 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
564 if (dump_flags
& TDF_SCEV
)
566 fprintf (dump_file
, "(set_scalar_evolution \n");
567 fprintf (dump_file
, " instantiated_below = %d \n",
568 instantiated_below
->index
);
569 fprintf (dump_file
, " (scalar = ");
570 print_generic_expr (dump_file
, scalar
);
571 fprintf (dump_file
, ")\n (scalar_evolution = ");
572 print_generic_expr (dump_file
, chrec
);
573 fprintf (dump_file
, "))\n");
575 if (dump_flags
& TDF_STATS
)
579 *scalar_info
= chrec
;
582 /* Retrieve the chrec associated to SCALAR instantiated below
583 INSTANTIATED_BELOW block. */
586 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
592 if (dump_flags
& TDF_SCEV
)
594 fprintf (dump_file
, "(get_scalar_evolution \n");
595 fprintf (dump_file
, " (scalar = ");
596 print_generic_expr (dump_file
, scalar
);
597 fprintf (dump_file
, ")\n");
599 if (dump_flags
& TDF_STATS
)
603 if (VECTOR_TYPE_P (TREE_TYPE (scalar
))
604 || TREE_CODE (TREE_TYPE (scalar
)) == COMPLEX_TYPE
)
605 /* For chrec_dont_know we keep the symbolic form. */
608 switch (TREE_CODE (scalar
))
611 if (SSA_NAME_IS_DEFAULT_DEF (scalar
))
614 res
= *find_var_scev_info (instantiated_below
, scalar
);
624 res
= chrec_not_analyzed_yet
;
628 if (dump_file
&& (dump_flags
& TDF_SCEV
))
630 fprintf (dump_file
, " (scalar_evolution = ");
631 print_generic_expr (dump_file
, res
);
632 fprintf (dump_file
, "))\n");
638 /* Helper function for add_to_evolution. Returns the evolution
639 function for an assignment of the form "a = b + c", where "a" and
640 "b" are on the strongly connected component. CHREC_BEFORE is the
641 information that we already have collected up to this point.
642 TO_ADD is the evolution of "c".
644 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
645 evolution the expression TO_ADD, otherwise construct an evolution
646 part for this loop. */
649 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
652 tree type
, left
, right
;
653 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
655 switch (TREE_CODE (chrec_before
))
657 case POLYNOMIAL_CHREC
:
658 chloop
= get_chrec_loop (chrec_before
);
660 || flow_loop_nested_p (chloop
, loop
))
664 type
= chrec_type (chrec_before
);
666 /* When there is no evolution part in this loop, build it. */
671 right
= SCALAR_FLOAT_TYPE_P (type
)
672 ? build_real (type
, dconst0
)
673 : build_int_cst (type
, 0);
677 var
= CHREC_VARIABLE (chrec_before
);
678 left
= CHREC_LEFT (chrec_before
);
679 right
= CHREC_RIGHT (chrec_before
);
682 to_add
= chrec_convert (type
, to_add
, at_stmt
);
683 right
= chrec_convert_rhs (type
, right
, at_stmt
);
684 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
685 return build_polynomial_chrec (var
, left
, right
);
689 gcc_assert (flow_loop_nested_p (loop
, chloop
));
691 /* Search the evolution in LOOP_NB. */
692 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
694 right
= CHREC_RIGHT (chrec_before
);
695 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
696 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
701 /* These nodes do not depend on a loop. */
702 if (chrec_before
== chrec_dont_know
)
703 return chrec_dont_know
;
706 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
707 return build_polynomial_chrec (loop_nb
, left
, right
);
711 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
714 Description (provided for completeness, for those who read code in
715 a plane, and for my poor 62 bytes brain that would have forgotten
716 all this in the next two or three months):
718 The algorithm of translation of programs from the SSA representation
719 into the chrecs syntax is based on a pattern matching. After having
720 reconstructed the overall tree expression for a loop, there are only
721 two cases that can arise:
723 1. a = loop-phi (init, a + expr)
724 2. a = loop-phi (init, expr)
726 where EXPR is either a scalar constant with respect to the analyzed
727 loop (this is a degree 0 polynomial), or an expression containing
728 other loop-phi definitions (these are higher degree polynomials).
735 | a = phi (init, a + 5)
742 | a = phi (inita, 2 * b + 3)
743 | b = phi (initb, b + 1)
746 For the first case, the semantics of the SSA representation is:
748 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
750 that is, there is a loop index "x" that determines the scalar value
751 of the variable during the loop execution. During the first
752 iteration, the value is that of the initial condition INIT, while
753 during the subsequent iterations, it is the sum of the initial
754 condition with the sum of all the values of EXPR from the initial
755 iteration to the before last considered iteration.
757 For the second case, the semantics of the SSA program is:
759 | a (x) = init, if x = 0;
760 | expr (x - 1), otherwise.
762 The second case corresponds to the PEELED_CHREC, whose syntax is
763 close to the syntax of a loop-phi-node:
765 | phi (init, expr) vs. (init, expr)_x
767 The proof of the translation algorithm for the first case is a
768 proof by structural induction based on the degree of EXPR.
771 When EXPR is a constant with respect to the analyzed loop, or in
772 other words when EXPR is a polynomial of degree 0, the evolution of
773 the variable A in the loop is an affine function with an initial
774 condition INIT, and a step EXPR. In order to show this, we start
775 from the semantics of the SSA representation:
777 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
779 and since "expr (j)" is a constant with respect to "j",
781 f (x) = init + x * expr
783 Finally, based on the semantics of the pure sum chrecs, by
784 identification we get the corresponding chrecs syntax:
786 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
787 f (x) -> {init, +, expr}_x
790 Suppose that EXPR is a polynomial of degree N with respect to the
791 analyzed loop_x for which we have already determined that it is
792 written under the chrecs syntax:
794 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
796 We start from the semantics of the SSA program:
798 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
800 | f (x) = init + \sum_{j = 0}^{x - 1}
801 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
803 | f (x) = init + \sum_{j = 0}^{x - 1}
804 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
806 | f (x) = init + \sum_{k = 0}^{n - 1}
807 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
809 | f (x) = init + \sum_{k = 0}^{n - 1}
810 | (b_k * \binom{x}{k + 1})
812 | f (x) = init + b_0 * \binom{x}{1} + ...
813 | + b_{n-1} * \binom{x}{n}
815 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
816 | + b_{n-1} * \binom{x}{n}
819 And finally from the definition of the chrecs syntax, we identify:
820 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
822 This shows the mechanism that stands behind the add_to_evolution
823 function. An important point is that the use of symbolic
824 parameters avoids the need of an analysis schedule.
831 | a = phi (inita, a + 2 + b)
832 | b = phi (initb, b + 1)
835 When analyzing "a", the algorithm keeps "b" symbolically:
837 | a -> {inita, +, 2 + b}_1
839 Then, after instantiation, the analyzer ends on the evolution:
841 | a -> {inita, +, 2 + initb, +, 1}_1
846 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
847 tree to_add
, gimple
*at_stmt
)
849 tree type
= chrec_type (to_add
);
850 tree res
= NULL_TREE
;
852 if (to_add
== NULL_TREE
)
855 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
856 instantiated at this point. */
857 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
858 /* This should not happen. */
859 return chrec_dont_know
;
861 if (dump_file
&& (dump_flags
& TDF_SCEV
))
863 fprintf (dump_file
, "(add_to_evolution \n");
864 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
865 fprintf (dump_file
, " (chrec_before = ");
866 print_generic_expr (dump_file
, chrec_before
);
867 fprintf (dump_file
, ")\n (to_add = ");
868 print_generic_expr (dump_file
, to_add
);
869 fprintf (dump_file
, ")\n");
872 if (code
== MINUS_EXPR
)
873 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
874 ? build_real (type
, dconstm1
)
875 : build_int_cst_type (type
, -1));
877 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
879 if (dump_file
&& (dump_flags
& TDF_SCEV
))
881 fprintf (dump_file
, " (res = ");
882 print_generic_expr (dump_file
, res
);
883 fprintf (dump_file
, "))\n");
891 /* This section selects the loops that will be good candidates for the
892 scalar evolution analysis. For the moment, greedily select all the
893 loop nests we could analyze. */
895 /* For a loop with a single exit edge, return the COND_EXPR that
896 guards the exit edge. If the expression is too difficult to
897 analyze, then give up. */
900 get_loop_exit_condition (const struct loop
*loop
)
903 edge exit_edge
= single_exit (loop
);
905 if (dump_file
&& (dump_flags
& TDF_SCEV
))
906 fprintf (dump_file
, "(get_loop_exit_condition \n ");
912 stmt
= last_stmt (exit_edge
->src
);
913 if (gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (stmt
))
917 if (dump_file
&& (dump_flags
& TDF_SCEV
))
919 print_gimple_stmt (dump_file
, res
, 0);
920 fprintf (dump_file
, ")\n");
927 /* Depth first search algorithm. */
936 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
*, gphi
*,
939 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
940 Return true if the strongly connected component has been found. */
943 follow_ssa_edge_binary (struct loop
*loop
, gimple
*at_stmt
,
944 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
945 gphi
*halting_phi
, tree
*evolution_of_loop
,
948 t_bool res
= t_false
;
953 case POINTER_PLUS_EXPR
:
955 if (TREE_CODE (rhs0
) == SSA_NAME
)
957 if (TREE_CODE (rhs1
) == SSA_NAME
)
959 /* Match an assignment under the form:
962 /* We want only assignments of form "name + name" contribute to
963 LIMIT, as the other cases do not necessarily contribute to
964 the complexity of the expression. */
967 evol
= *evolution_of_loop
;
968 evol
= add_to_evolution
970 chrec_convert (type
, evol
, at_stmt
),
971 code
, rhs1
, at_stmt
);
972 res
= follow_ssa_edge
973 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
975 *evolution_of_loop
= evol
;
976 else if (res
== t_false
)
978 *evolution_of_loop
= add_to_evolution
980 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
981 code
, rhs0
, at_stmt
);
982 res
= follow_ssa_edge
983 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
984 evolution_of_loop
, limit
);
987 else if (res
== t_dont_know
)
988 *evolution_of_loop
= chrec_dont_know
;
991 else if (res
== t_dont_know
)
992 *evolution_of_loop
= chrec_dont_know
;
997 /* Match an assignment under the form:
999 *evolution_of_loop
= add_to_evolution
1000 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1002 code
, rhs1
, at_stmt
);
1003 res
= follow_ssa_edge
1004 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1005 evolution_of_loop
, limit
);
1008 else if (res
== t_dont_know
)
1009 *evolution_of_loop
= chrec_dont_know
;
1013 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1015 /* Match an assignment under the form:
1017 *evolution_of_loop
= add_to_evolution
1018 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1020 code
, rhs0
, at_stmt
);
1021 res
= follow_ssa_edge
1022 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1023 evolution_of_loop
, limit
);
1026 else if (res
== t_dont_know
)
1027 *evolution_of_loop
= chrec_dont_know
;
1031 /* Otherwise, match an assignment under the form:
1033 /* And there is nothing to do. */
1038 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1039 if (TREE_CODE (rhs0
) == SSA_NAME
)
1041 /* Match an assignment under the form:
1044 /* We want only assignments of form "name - name" contribute to
1045 LIMIT, as the other cases do not necessarily contribute to
1046 the complexity of the expression. */
1047 if (TREE_CODE (rhs1
) == SSA_NAME
)
1050 *evolution_of_loop
= add_to_evolution
1051 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1052 MINUS_EXPR
, rhs1
, at_stmt
);
1053 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1054 evolution_of_loop
, limit
);
1057 else if (res
== t_dont_know
)
1058 *evolution_of_loop
= chrec_dont_know
;
1061 /* Otherwise, match an assignment under the form:
1063 /* And there is nothing to do. */
1074 /* Follow the ssa edge into the expression EXPR.
1075 Return true if the strongly connected component has been found. */
1078 follow_ssa_edge_expr (struct loop
*loop
, gimple
*at_stmt
, tree expr
,
1079 gphi
*halting_phi
, tree
*evolution_of_loop
,
1082 enum tree_code code
= TREE_CODE (expr
);
1083 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1086 /* The EXPR is one of the following cases:
1090 - a POINTER_PLUS_EXPR,
1093 - other cases are not yet handled. */
1098 /* This assignment is under the form "a_1 = (cast) rhs. */
1099 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1100 halting_phi
, evolution_of_loop
, limit
);
1101 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1105 /* This assignment is under the form "a_1 = 7". */
1110 /* This assignment is under the form: "a_1 = b_2". */
1111 res
= follow_ssa_edge
1112 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1115 case POINTER_PLUS_EXPR
:
1118 /* This case is under the form "rhs0 +- rhs1". */
1119 rhs0
= TREE_OPERAND (expr
, 0);
1120 rhs1
= TREE_OPERAND (expr
, 1);
1121 type
= TREE_TYPE (rhs0
);
1122 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1123 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1124 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1125 halting_phi
, evolution_of_loop
, limit
);
1129 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1130 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1132 expr
= TREE_OPERAND (expr
, 0);
1133 rhs0
= TREE_OPERAND (expr
, 0);
1134 rhs1
= TREE_OPERAND (expr
, 1);
1135 type
= TREE_TYPE (rhs0
);
1136 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1137 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1138 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1139 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1140 halting_phi
, evolution_of_loop
, limit
);
1147 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1148 It must be handled as a copy assignment of the form a_1 = a_2. */
1149 rhs0
= ASSERT_EXPR_VAR (expr
);
1150 if (TREE_CODE (rhs0
) == SSA_NAME
)
1151 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1152 halting_phi
, evolution_of_loop
, limit
);
1165 /* Follow the ssa edge into the right hand side of an assignment STMT.
1166 Return true if the strongly connected component has been found. */
1169 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple
*stmt
,
1170 gphi
*halting_phi
, tree
*evolution_of_loop
,
1173 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1174 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1180 /* This assignment is under the form "a_1 = (cast) rhs. */
1181 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1182 halting_phi
, evolution_of_loop
, limit
);
1183 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1186 case POINTER_PLUS_EXPR
:
1189 rhs1
= gimple_assign_rhs1 (stmt
);
1190 rhs2
= gimple_assign_rhs2 (stmt
);
1191 type
= TREE_TYPE (rhs1
);
1192 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1193 halting_phi
, evolution_of_loop
, limit
);
1197 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1198 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1199 halting_phi
, evolution_of_loop
, limit
);
1208 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1211 backedge_phi_arg_p (gphi
*phi
, int i
)
1213 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1215 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1216 about updating it anywhere, and this should work as well most of the
1218 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1224 /* Helper function for one branch of the condition-phi-node. Return
1225 true if the strongly connected component has been found following
1228 static inline t_bool
1229 follow_ssa_edge_in_condition_phi_branch (int i
,
1231 gphi
*condition_phi
,
1233 tree
*evolution_of_branch
,
1234 tree init_cond
, int limit
)
1236 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1237 *evolution_of_branch
= chrec_dont_know
;
1239 /* Do not follow back edges (they must belong to an irreducible loop, which
1240 we really do not want to worry about). */
1241 if (backedge_phi_arg_p (condition_phi
, i
))
1244 if (TREE_CODE (branch
) == SSA_NAME
)
1246 *evolution_of_branch
= init_cond
;
1247 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1248 evolution_of_branch
, limit
);
1251 /* This case occurs when one of the condition branches sets
1252 the variable to a constant: i.e. a phi-node like
1253 "a_2 = PHI <a_7(5), 2(6)>;".
1255 FIXME: This case have to be refined correctly:
1256 in some cases it is possible to say something better than
1257 chrec_dont_know, for example using a wrap-around notation. */
1261 /* This function merges the branches of a condition-phi-node in a
1265 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1266 gphi
*condition_phi
,
1268 tree
*evolution_of_loop
, int limit
)
1271 tree init
= *evolution_of_loop
;
1272 tree evolution_of_branch
;
1273 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1275 &evolution_of_branch
,
1277 if (res
== t_false
|| res
== t_dont_know
)
1280 *evolution_of_loop
= evolution_of_branch
;
1282 n
= gimple_phi_num_args (condition_phi
);
1283 for (i
= 1; i
< n
; i
++)
1285 /* Quickly give up when the evolution of one of the branches is
1287 if (*evolution_of_loop
== chrec_dont_know
)
1290 /* Increase the limit by the PHI argument number to avoid exponential
1291 time and memory complexity. */
1292 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1294 &evolution_of_branch
,
1296 if (res
== t_false
|| res
== t_dont_know
)
1299 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1300 evolution_of_branch
);
1306 /* Follow an SSA edge in an inner loop. It computes the overall
1307 effect of the loop, and following the symbolic initial conditions,
1308 it follows the edges in the parent loop. The inner loop is
1309 considered as a single statement. */
1312 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1313 gphi
*loop_phi_node
,
1315 tree
*evolution_of_loop
, int limit
)
1317 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1318 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1320 /* Sometimes, the inner loop is too difficult to analyze, and the
1321 result of the analysis is a symbolic parameter. */
1322 if (ev
== PHI_RESULT (loop_phi_node
))
1324 t_bool res
= t_false
;
1325 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1327 for (i
= 0; i
< n
; i
++)
1329 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1332 /* Follow the edges that exit the inner loop. */
1333 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1334 if (!flow_bb_inside_loop_p (loop
, bb
))
1335 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1337 evolution_of_loop
, limit
);
1342 /* If the path crosses this loop-phi, give up. */
1344 *evolution_of_loop
= chrec_dont_know
;
1349 /* Otherwise, compute the overall effect of the inner loop. */
1350 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1351 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1352 evolution_of_loop
, limit
);
1355 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1356 path that is analyzed on the return walk. */
1359 follow_ssa_edge (struct loop
*loop
, gimple
*def
, gphi
*halting_phi
,
1360 tree
*evolution_of_loop
, int limit
)
1362 struct loop
*def_loop
;
1364 if (gimple_nop_p (def
))
1367 /* Give up if the path is longer than the MAX that we allow. */
1368 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1371 def_loop
= loop_containing_stmt (def
);
1373 switch (gimple_code (def
))
1376 if (!loop_phi_node_p (def
))
1377 /* DEF is a condition-phi-node. Follow the branches, and
1378 record their evolutions. Finally, merge the collected
1379 information and set the approximation to the main
1381 return follow_ssa_edge_in_condition_phi
1382 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1385 /* When the analyzed phi is the halting_phi, the
1386 depth-first search is over: we have found a path from
1387 the halting_phi to itself in the loop. */
1388 if (def
== halting_phi
)
1391 /* Otherwise, the evolution of the HALTING_PHI depends
1392 on the evolution of another loop-phi-node, i.e. the
1393 evolution function is a higher degree polynomial. */
1394 if (def_loop
== loop
)
1398 if (flow_loop_nested_p (loop
, def_loop
))
1399 return follow_ssa_edge_inner_loop_phi
1400 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1407 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1408 evolution_of_loop
, limit
);
1411 /* At this level of abstraction, the program is just a set
1412 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1413 other node to be handled. */
1419 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1420 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1422 # i_17 = PHI <i_13(5), 0(3)>
1423 # _20 = PHI <_5(5), start_4(D)(3)>
1426 _5 = start_4(D) + i_13;
1428 Though variable _20 appears as a PEELED_CHREC in the form of
1429 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1434 simplify_peeled_chrec (struct loop
*loop
, tree arg
, tree init_cond
)
1436 aff_tree aff1
, aff2
;
1437 tree ev
, left
, right
, type
, step_val
;
1438 hash_map
<tree
, name_expansion
*> *peeled_chrec_map
= NULL
;
1440 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1441 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1442 return chrec_dont_know
;
1444 left
= CHREC_LEFT (ev
);
1445 right
= CHREC_RIGHT (ev
);
1446 type
= TREE_TYPE (left
);
1447 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1449 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1450 if "left" equals to "init + right". */
1451 if (operand_equal_p (left
, step_val
, 0))
1453 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1454 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1456 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1459 /* The affine code only deals with pointer and integer types. */
1460 if (!POINTER_TYPE_P (type
)
1461 && !INTEGRAL_TYPE_P (type
))
1462 return chrec_dont_know
;
1464 /* Try harder to check if they are equal. */
1465 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1466 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1467 free_affine_expand_cache (&peeled_chrec_map
);
1468 aff_combination_scale (&aff2
, -1);
1469 aff_combination_add (&aff1
, &aff2
);
1471 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1472 if "left" equals to "init + right". */
1473 if (aff_combination_zero_p (&aff1
))
1475 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1476 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1478 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1480 return chrec_dont_know
;
1483 /* Given a LOOP_PHI_NODE, this function determines the evolution
1484 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1487 analyze_evolution_in_loop (gphi
*loop_phi_node
,
1490 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1491 tree evolution_function
= chrec_not_analyzed_yet
;
1492 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1494 static bool simplify_peeled_chrec_p
= true;
1496 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1498 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1499 fprintf (dump_file
, " (loop_phi_node = ");
1500 print_gimple_stmt (dump_file
, loop_phi_node
, 0);
1501 fprintf (dump_file
, ")\n");
1504 for (i
= 0; i
< n
; i
++)
1506 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1511 /* Select the edges that enter the loop body. */
1512 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1513 if (!flow_bb_inside_loop_p (loop
, bb
))
1516 if (TREE_CODE (arg
) == SSA_NAME
)
1520 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1522 /* Pass in the initial condition to the follow edge function. */
1524 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1526 /* If ev_fn has no evolution in the inner loop, and the
1527 init_cond is not equal to ev_fn, then we have an
1528 ambiguity between two possible values, as we cannot know
1529 the number of iterations at this point. */
1530 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1531 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1532 && !operand_equal_p (init_cond
, ev_fn
, 0))
1533 ev_fn
= chrec_dont_know
;
1538 /* When it is impossible to go back on the same
1539 loop_phi_node by following the ssa edges, the
1540 evolution is represented by a peeled chrec, i.e. the
1541 first iteration, EV_FN has the value INIT_COND, then
1542 all the other iterations it has the value of ARG.
1543 For the moment, PEELED_CHREC nodes are not built. */
1546 ev_fn
= chrec_dont_know
;
1547 /* Try to recognize POLYNOMIAL_CHREC which appears in
1548 the form of PEELED_CHREC, but guard the process with
1549 a bool variable to keep the analyzer from infinite
1550 recurrence for real PEELED_RECs. */
1551 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1553 simplify_peeled_chrec_p
= false;
1554 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1555 simplify_peeled_chrec_p
= true;
1559 /* When there are multiple back edges of the loop (which in fact never
1560 happens currently, but nevertheless), merge their evolutions. */
1561 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1563 if (evolution_function
== chrec_dont_know
)
1567 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1569 fprintf (dump_file
, " (evolution_function = ");
1570 print_generic_expr (dump_file
, evolution_function
);
1571 fprintf (dump_file
, "))\n");
1574 return evolution_function
;
1577 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1578 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1581 follow_copies_to_constant (tree var
)
1584 while (TREE_CODE (res
) == SSA_NAME
1585 /* We face not updated SSA form in multiple places and this walk
1586 may end up in sibling loops so we have to guard it. */
1587 && !name_registered_for_update_p (res
))
1589 gimple
*def
= SSA_NAME_DEF_STMT (res
);
1590 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
1592 if (tree rhs
= degenerate_phi_result (phi
))
1597 else if (gimple_assign_single_p (def
))
1598 /* Will exit loop if not an SSA_NAME. */
1599 res
= gimple_assign_rhs1 (def
);
1603 if (CONSTANT_CLASS_P (res
))
1608 /* Given a loop-phi-node, return the initial conditions of the
1609 variable on entry of the loop. When the CCP has propagated
1610 constants into the loop-phi-node, the initial condition is
1611 instantiated, otherwise the initial condition is kept symbolic.
1612 This analyzer does not analyze the evolution outside the current
1613 loop, and leaves this task to the on-demand tree reconstructor. */
1616 analyze_initial_condition (gphi
*loop_phi_node
)
1619 tree init_cond
= chrec_not_analyzed_yet
;
1620 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1622 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1624 fprintf (dump_file
, "(analyze_initial_condition \n");
1625 fprintf (dump_file
, " (loop_phi_node = \n");
1626 print_gimple_stmt (dump_file
, loop_phi_node
, 0);
1627 fprintf (dump_file
, ")\n");
1630 n
= gimple_phi_num_args (loop_phi_node
);
1631 for (i
= 0; i
< n
; i
++)
1633 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1634 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1636 /* When the branch is oriented to the loop's body, it does
1637 not contribute to the initial condition. */
1638 if (flow_bb_inside_loop_p (loop
, bb
))
1641 if (init_cond
== chrec_not_analyzed_yet
)
1647 if (TREE_CODE (branch
) == SSA_NAME
)
1649 init_cond
= chrec_dont_know
;
1653 init_cond
= chrec_merge (init_cond
, branch
);
1656 /* Ooops -- a loop without an entry??? */
1657 if (init_cond
== chrec_not_analyzed_yet
)
1658 init_cond
= chrec_dont_know
;
1660 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1661 to not miss important early loop unrollings. */
1662 init_cond
= follow_copies_to_constant (init_cond
);
1664 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1666 fprintf (dump_file
, " (init_cond = ");
1667 print_generic_expr (dump_file
, init_cond
);
1668 fprintf (dump_file
, "))\n");
1674 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1677 interpret_loop_phi (struct loop
*loop
, gphi
*loop_phi_node
)
1680 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1683 gcc_assert (phi_loop
== loop
);
1685 /* Otherwise really interpret the loop phi. */
1686 init_cond
= analyze_initial_condition (loop_phi_node
);
1687 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1689 /* Verify we maintained the correct initial condition throughout
1690 possible conversions in the SSA chain. */
1691 if (res
!= chrec_dont_know
)
1693 tree new_init
= res
;
1694 if (CONVERT_EXPR_P (res
)
1695 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1696 new_init
= fold_convert (TREE_TYPE (res
),
1697 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1698 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1699 new_init
= CHREC_LEFT (res
);
1700 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1701 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1702 || !operand_equal_p (init_cond
, new_init
, 0))
1703 return chrec_dont_know
;
1709 /* This function merges the branches of a condition-phi-node,
1710 contained in the outermost loop, and whose arguments are already
1714 interpret_condition_phi (struct loop
*loop
, gphi
*condition_phi
)
1716 int i
, n
= gimple_phi_num_args (condition_phi
);
1717 tree res
= chrec_not_analyzed_yet
;
1719 for (i
= 0; i
< n
; i
++)
1723 if (backedge_phi_arg_p (condition_phi
, i
))
1725 res
= chrec_dont_know
;
1729 branch_chrec
= analyze_scalar_evolution
1730 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1732 res
= chrec_merge (res
, branch_chrec
);
1733 if (res
== chrec_dont_know
)
1740 /* Interpret the operation RHS1 OP RHS2. If we didn't
1741 analyze this node before, follow the definitions until ending
1742 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1743 return path, this function propagates evolutions (ala constant copy
1744 propagation). OPND1 is not a GIMPLE expression because we could
1745 analyze the effect of an inner loop: see interpret_loop_phi. */
1748 interpret_rhs_expr (struct loop
*loop
, gimple
*at_stmt
,
1749 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1751 tree res
, chrec1
, chrec2
, ctype
;
1754 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1756 if (is_gimple_min_invariant (rhs1
))
1757 return chrec_convert (type
, rhs1
, at_stmt
);
1759 if (code
== SSA_NAME
)
1760 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1763 if (code
== ASSERT_EXPR
)
1765 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1766 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1774 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1775 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1778 poly_int64 bitsize
, bitpos
;
1779 int unsignedp
, reversep
;
1785 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1786 &bitsize
, &bitpos
, &offset
, &mode
,
1787 &unsignedp
, &reversep
, &volatilep
);
1789 if (TREE_CODE (base
) == MEM_REF
)
1791 rhs2
= TREE_OPERAND (base
, 1);
1792 rhs1
= TREE_OPERAND (base
, 0);
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_for_address_of (loop
, base
);
1805 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1809 if (offset
!= NULL_TREE
)
1811 chrec2
= analyze_scalar_evolution (loop
, offset
);
1812 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1813 chrec2
= instantiate_parameters (loop
, chrec2
);
1814 res
= chrec_fold_plus (type
, res
, chrec2
);
1817 if (maybe_ne (bitpos
, 0))
1819 unitpos
= size_int (exact_div (bitpos
, BITS_PER_UNIT
));
1820 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1821 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1822 chrec3
= instantiate_parameters (loop
, chrec3
);
1823 res
= chrec_fold_plus (type
, res
, chrec3
);
1827 res
= chrec_dont_know
;
1830 case POINTER_PLUS_EXPR
:
1831 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1832 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1833 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1834 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1835 chrec1
= instantiate_parameters (loop
, chrec1
);
1836 chrec2
= instantiate_parameters (loop
, chrec2
);
1837 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1841 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1842 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1844 /* When the stmt is conditionally executed re-write the CHREC
1845 into a form that has well-defined behavior on overflow. */
1847 && INTEGRAL_TYPE_P (type
)
1848 && ! TYPE_OVERFLOW_WRAPS (type
)
1849 && ! dominated_by_p (CDI_DOMINATORS
, loop
->latch
,
1850 gimple_bb (at_stmt
)))
1851 ctype
= unsigned_type_for (type
);
1852 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1853 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1854 chrec1
= instantiate_parameters (loop
, chrec1
);
1855 chrec2
= instantiate_parameters (loop
, chrec2
);
1856 res
= chrec_fold_plus (ctype
, chrec1
, chrec2
);
1858 res
= chrec_convert (type
, res
, at_stmt
);
1862 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1863 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1865 /* When the stmt is conditionally executed re-write the CHREC
1866 into a form that has well-defined behavior on overflow. */
1868 && INTEGRAL_TYPE_P (type
)
1869 && ! TYPE_OVERFLOW_WRAPS (type
)
1870 && ! dominated_by_p (CDI_DOMINATORS
,
1871 loop
->latch
, gimple_bb (at_stmt
)))
1872 ctype
= unsigned_type_for (type
);
1873 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1874 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1875 chrec1
= instantiate_parameters (loop
, chrec1
);
1876 chrec2
= instantiate_parameters (loop
, chrec2
);
1877 res
= chrec_fold_minus (ctype
, chrec1
, chrec2
);
1879 res
= chrec_convert (type
, res
, at_stmt
);
1883 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1885 /* When the stmt is conditionally executed re-write the CHREC
1886 into a form that has well-defined behavior on overflow. */
1888 && INTEGRAL_TYPE_P (type
)
1889 && ! TYPE_OVERFLOW_WRAPS (type
)
1890 && ! dominated_by_p (CDI_DOMINATORS
,
1891 loop
->latch
, gimple_bb (at_stmt
)))
1892 ctype
= unsigned_type_for (type
);
1893 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1894 /* TYPE may be integer, real or complex, so use fold_convert. */
1895 chrec1
= instantiate_parameters (loop
, chrec1
);
1896 res
= chrec_fold_multiply (ctype
, chrec1
,
1897 fold_convert (ctype
, integer_minus_one_node
));
1899 res
= chrec_convert (type
, res
, at_stmt
);
1903 /* Handle ~X as -1 - X. */
1904 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1905 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1906 chrec1
= instantiate_parameters (loop
, chrec1
);
1907 res
= chrec_fold_minus (type
,
1908 fold_convert (type
, integer_minus_one_node
),
1913 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1914 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1916 /* When the stmt is conditionally executed re-write the CHREC
1917 into a form that has well-defined behavior on overflow. */
1919 && INTEGRAL_TYPE_P (type
)
1920 && ! TYPE_OVERFLOW_WRAPS (type
)
1921 && ! dominated_by_p (CDI_DOMINATORS
,
1922 loop
->latch
, gimple_bb (at_stmt
)))
1923 ctype
= unsigned_type_for (type
);
1924 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1925 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1926 chrec1
= instantiate_parameters (loop
, chrec1
);
1927 chrec2
= instantiate_parameters (loop
, chrec2
);
1928 res
= chrec_fold_multiply (ctype
, chrec1
, chrec2
);
1930 res
= chrec_convert (type
, res
, at_stmt
);
1935 /* Handle A<<B as A * (1<<B). */
1936 tree uns
= unsigned_type_for (type
);
1937 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1938 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1939 chrec1
= chrec_convert (uns
, chrec1
, at_stmt
);
1940 chrec1
= instantiate_parameters (loop
, chrec1
);
1941 chrec2
= instantiate_parameters (loop
, chrec2
);
1943 tree one
= build_int_cst (uns
, 1);
1944 chrec2
= fold_build2 (LSHIFT_EXPR
, uns
, one
, chrec2
);
1945 res
= chrec_fold_multiply (uns
, chrec1
, chrec2
);
1946 res
= chrec_convert (type
, res
, at_stmt
);
1951 /* In case we have a truncation of a widened operation that in
1952 the truncated type has undefined overflow behavior analyze
1953 the operation done in an unsigned type of the same precision
1954 as the final truncation. We cannot derive a scalar evolution
1955 for the widened operation but for the truncated result. */
1956 if (TREE_CODE (type
) == INTEGER_TYPE
1957 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1958 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1959 && TYPE_OVERFLOW_UNDEFINED (type
)
1960 && TREE_CODE (rhs1
) == SSA_NAME
1961 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1962 && is_gimple_assign (def
)
1963 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1964 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1966 tree utype
= unsigned_type_for (type
);
1967 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1968 gimple_assign_rhs1 (def
),
1969 gimple_assign_rhs_code (def
),
1970 gimple_assign_rhs2 (def
));
1973 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1974 res
= chrec_convert (type
, chrec1
, at_stmt
, true, rhs1
);
1978 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1979 If A is SCEV and its value is in the range of representable set
1980 of type unsigned short, the result expression is a (no-overflow)
1982 res
= chrec_dont_know
;
1983 if (tree_fits_uhwi_p (rhs2
))
1986 unsigned HOST_WIDE_INT val
= tree_to_uhwi (rhs2
);
1989 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1990 it's not the maximum value of a smaller type than rhs1. */
1992 && (precision
= exact_log2 (val
)) > 0
1993 && (unsigned) precision
< TYPE_PRECISION (TREE_TYPE (rhs1
)))
1995 tree utype
= build_nonstandard_integer_type (precision
, 1);
1997 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (TREE_TYPE (rhs1
)))
1999 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
2000 chrec1
= chrec_convert (utype
, chrec1
, at_stmt
);
2001 res
= chrec_convert (TREE_TYPE (rhs1
), chrec1
, at_stmt
);
2008 res
= chrec_dont_know
;
2015 /* Interpret the expression EXPR. */
2018 interpret_expr (struct loop
*loop
, gimple
*at_stmt
, tree expr
)
2020 enum tree_code code
;
2021 tree type
= TREE_TYPE (expr
), op0
, op1
;
2023 if (automatically_generated_chrec_p (expr
))
2026 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
2027 || TREE_CODE (expr
) == CALL_EXPR
2028 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
2029 return chrec_dont_know
;
2031 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2033 return interpret_rhs_expr (loop
, at_stmt
, type
,
2037 /* Interpret the rhs of the assignment STMT. */
2040 interpret_gimple_assign (struct loop
*loop
, gimple
*stmt
)
2042 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2043 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2045 return interpret_rhs_expr (loop
, stmt
, type
,
2046 gimple_assign_rhs1 (stmt
), code
,
2047 gimple_assign_rhs2 (stmt
));
2052 /* This section contains all the entry points:
2053 - number_of_iterations_in_loop,
2054 - analyze_scalar_evolution,
2055 - instantiate_parameters.
2058 /* Helper recursive function. */
2061 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
)
2065 struct loop
*def_loop
;
2068 if (TREE_CODE (var
) != SSA_NAME
)
2069 return interpret_expr (loop
, NULL
, var
);
2071 def
= SSA_NAME_DEF_STMT (var
);
2072 bb
= gimple_bb (def
);
2073 def_loop
= bb
->loop_father
;
2075 if (!flow_bb_inside_loop_p (loop
, bb
))
2077 /* Keep symbolic form, but look through obvious copies for constants. */
2078 res
= follow_copies_to_constant (var
);
2082 if (loop
!= def_loop
)
2084 res
= analyze_scalar_evolution_1 (def_loop
, var
);
2085 struct loop
*loop_to_skip
= superloop_at_depth (def_loop
,
2086 loop_depth (loop
) + 1);
2087 res
= compute_overall_effect_of_inner_loop (loop_to_skip
, res
);
2088 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
2089 res
= analyze_scalar_evolution_1 (loop
, res
);
2093 switch (gimple_code (def
))
2096 res
= interpret_gimple_assign (loop
, def
);
2100 if (loop_phi_node_p (def
))
2101 res
= interpret_loop_phi (loop
, as_a
<gphi
*> (def
));
2103 res
= interpret_condition_phi (loop
, as_a
<gphi
*> (def
));
2107 res
= chrec_dont_know
;
2113 /* Keep the symbolic form. */
2114 if (res
== chrec_dont_know
)
2117 if (loop
== def_loop
)
2118 set_scalar_evolution (block_before_loop (loop
), var
, res
);
2123 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2124 LOOP. LOOP is the loop in which the variable is used.
2126 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2127 pointer to the statement that uses this variable, in order to
2128 determine the evolution function of the variable, use the following
2131 loop_p loop = loop_containing_stmt (stmt);
2132 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2133 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2137 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2141 /* ??? Fix callers. */
2145 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2147 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2148 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2149 fprintf (dump_file
, " (scalar = ");
2150 print_generic_expr (dump_file
, var
);
2151 fprintf (dump_file
, ")\n");
2154 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2155 if (res
== chrec_not_analyzed_yet
)
2157 /* We'll recurse into instantiate_scev, avoid tearing down the
2158 instantiate cache repeatedly and keep it live from here. */
2162 global_cache
= new instantiate_cache_type
;
2165 res
= analyze_scalar_evolution_1 (loop
, var
);
2168 delete global_cache
;
2169 global_cache
= NULL
;
2173 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2174 fprintf (dump_file
, ")\n");
2179 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2182 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
2184 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2187 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2188 WRTO_LOOP (which should be a superloop of USE_LOOP)
2190 FOLDED_CASTS is set to true if resolve_mixers used
2191 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2192 at the moment in order to keep things simple).
2194 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2197 for (i = 0; i < 100; i++) -- loop 1
2199 for (j = 0; j < 100; j++) -- loop 2
2206 for (t = 0; t < 100; t++) -- loop 3
2213 Both k1 and k2 are invariants in loop3, thus
2214 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2215 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2217 As they are invariant, it does not matter whether we consider their
2218 usage in loop 3 or loop 2, hence
2219 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2220 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2221 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2222 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2224 Similarly for their evolutions with respect to loop 1. The values of K2
2225 in the use in loop 2 vary independently on loop 1, thus we cannot express
2226 the evolution with respect to loop 1:
2227 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2228 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2229 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2230 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2232 The value of k2 in the use in loop 1 is known, though:
2233 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2234 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2238 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2239 tree version
, bool *folded_casts
)
2242 tree ev
= version
, tmp
;
2244 /* We cannot just do
2246 tmp = analyze_scalar_evolution (use_loop, version);
2247 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2249 as resolve_mixers would query the scalar evolution with respect to
2250 wrto_loop. For example, in the situation described in the function
2251 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2254 analyze_scalar_evolution (use_loop, version) = k2
2256 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2257 k2 in loop 1 is 100, which is a wrong result, since we are interested
2258 in the value in loop 3.
2260 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2261 each time checking that there is no evolution in the inner loop. */
2264 *folded_casts
= false;
2267 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2268 ev
= resolve_mixers (use_loop
, tmp
, folded_casts
);
2270 if (use_loop
== wrto_loop
)
2273 /* If the value of the use changes in the inner loop, we cannot express
2274 its value in the outer loop (we might try to return interval chrec,
2275 but we do not have a user for it anyway) */
2276 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2278 return chrec_dont_know
;
2280 use_loop
= loop_outer (use_loop
);
2285 /* Computes a hash function for database element ELT. */
2287 static inline hashval_t
2288 hash_idx_scev_info (const void *elt_
)
2290 unsigned idx
= ((size_t) elt_
) - 2;
2291 return scev_info_hasher::hash (&global_cache
->entries
[idx
]);
2294 /* Compares database elements E1 and E2. */
2297 eq_idx_scev_info (const void *e1
, const void *e2
)
2299 unsigned idx1
= ((size_t) e1
) - 2;
2300 return scev_info_hasher::equal (&global_cache
->entries
[idx1
],
2301 (const scev_info_str
*) e2
);
2304 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2307 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2308 tree name
, edge instantiate_below
)
2312 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2313 cache
.entries
.create (10);
2317 e
.name_version
= SSA_NAME_VERSION (name
);
2318 e
.instantiated_below
= instantiate_below
->dest
->index
;
2319 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2320 scev_info_hasher::hash (&e
), INSERT
);
2323 e
.chrec
= chrec_not_analyzed_yet
;
2324 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2325 cache
.entries
.safe_push (e
);
2328 return ((size_t)*slot
) - 2;
2332 /* Return the closed_loop_phi node for VAR. If there is none, return
2336 loop_closed_phi_def (tree var
)
2343 if (var
== NULL_TREE
2344 || TREE_CODE (var
) != SSA_NAME
)
2347 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2348 exit
= single_exit (loop
);
2352 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2355 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2356 return PHI_RESULT (phi
);
2362 static tree
instantiate_scev_r (edge
, struct loop
*, struct loop
*,
2365 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2366 and EVOLUTION_LOOP, that were left under a symbolic form.
2368 CHREC is an SSA_NAME to be instantiated.
2370 CACHE is the cache of already instantiated values.
2372 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2373 conversions that may wrap in signed/pointer type are folded, as long
2374 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2375 then we don't do such fold.
2377 SIZE_EXPR is used for computing the size of the expression to be
2378 instantiated, and to stop if it exceeds some limit. */
2381 instantiate_scev_name (edge instantiate_below
,
2382 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2384 bool *fold_conversions
,
2388 struct loop
*def_loop
;
2389 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2391 /* A parameter, nothing to do. */
2393 || !dominated_by_p (CDI_DOMINATORS
, def_bb
, instantiate_below
->dest
))
2396 /* We cache the value of instantiated variable to avoid exponential
2397 time complexity due to reevaluations. We also store the convenient
2398 value in the cache in order to prevent infinite recursion -- we do
2399 not want to instantiate the SSA_NAME if it is in a mixer
2400 structure. This is used for avoiding the instantiation of
2401 recursively defined functions, such as:
2403 | a_2 -> {0, +, 1, +, a_2}_1 */
2405 unsigned si
= get_instantiated_value_entry (*global_cache
,
2406 chrec
, instantiate_below
);
2407 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2408 return global_cache
->get (si
);
2410 /* On recursion return chrec_dont_know. */
2411 global_cache
->set (si
, chrec_dont_know
);
2413 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2415 if (! dominated_by_p (CDI_DOMINATORS
,
2416 def_loop
->header
, instantiate_below
->dest
))
2418 gimple
*def
= SSA_NAME_DEF_STMT (chrec
);
2419 if (gassign
*ass
= dyn_cast
<gassign
*> (def
))
2421 switch (gimple_assign_rhs_class (ass
))
2423 case GIMPLE_UNARY_RHS
:
2425 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2426 inner_loop
, gimple_assign_rhs1 (ass
),
2427 fold_conversions
, size_expr
);
2428 if (op0
== chrec_dont_know
)
2429 return chrec_dont_know
;
2430 res
= fold_build1 (gimple_assign_rhs_code (ass
),
2431 TREE_TYPE (chrec
), op0
);
2434 case GIMPLE_BINARY_RHS
:
2436 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2437 inner_loop
, gimple_assign_rhs1 (ass
),
2438 fold_conversions
, size_expr
);
2439 if (op0
== chrec_dont_know
)
2440 return chrec_dont_know
;
2441 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2442 inner_loop
, gimple_assign_rhs2 (ass
),
2443 fold_conversions
, size_expr
);
2444 if (op1
== chrec_dont_know
)
2445 return chrec_dont_know
;
2446 res
= fold_build2 (gimple_assign_rhs_code (ass
),
2447 TREE_TYPE (chrec
), op0
, op1
);
2451 res
= chrec_dont_know
;
2455 res
= chrec_dont_know
;
2456 global_cache
->set (si
, res
);
2460 /* If the analysis yields a parametric chrec, instantiate the
2462 res
= analyze_scalar_evolution (def_loop
, chrec
);
2464 /* Don't instantiate default definitions. */
2465 if (TREE_CODE (res
) == SSA_NAME
2466 && SSA_NAME_IS_DEFAULT_DEF (res
))
2469 /* Don't instantiate loop-closed-ssa phi nodes. */
2470 else if (TREE_CODE (res
) == SSA_NAME
2471 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2472 > loop_depth (def_loop
))
2475 res
= loop_closed_phi_def (chrec
);
2479 /* When there is no loop_closed_phi_def, it means that the
2480 variable is not used after the loop: try to still compute the
2481 value of the variable when exiting the loop. */
2482 if (res
== NULL_TREE
)
2484 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2485 res
= analyze_scalar_evolution (loop
, chrec
);
2486 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2487 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2489 fold_conversions
, size_expr
);
2491 else if (dominated_by_p (CDI_DOMINATORS
,
2492 gimple_bb (SSA_NAME_DEF_STMT (res
)),
2493 instantiate_below
->dest
))
2494 res
= chrec_dont_know
;
2497 else if (res
!= chrec_dont_know
)
2500 && def_bb
->loop_father
!= inner_loop
2501 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2502 /* ??? We could try to compute the overall effect of the loop here. */
2503 res
= chrec_dont_know
;
2505 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2507 fold_conversions
, size_expr
);
2510 /* Store the correct value to the cache. */
2511 global_cache
->set (si
, res
);
2515 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2516 and EVOLUTION_LOOP, that were left under a symbolic form.
2518 CHREC is a polynomial chain of recurrence to be instantiated.
2520 CACHE is the cache of already instantiated values.
2522 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2523 conversions that may wrap in signed/pointer type are folded, as long
2524 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2525 then we don't do such fold.
2527 SIZE_EXPR is used for computing the size of the expression to be
2528 instantiated, and to stop if it exceeds some limit. */
2531 instantiate_scev_poly (edge instantiate_below
,
2532 struct loop
*evolution_loop
, struct loop
*,
2533 tree chrec
, bool *fold_conversions
, int size_expr
)
2536 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2537 get_chrec_loop (chrec
),
2538 CHREC_LEFT (chrec
), fold_conversions
,
2540 if (op0
== chrec_dont_know
)
2541 return chrec_dont_know
;
2543 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2544 get_chrec_loop (chrec
),
2545 CHREC_RIGHT (chrec
), fold_conversions
,
2547 if (op1
== chrec_dont_know
)
2548 return chrec_dont_know
;
2550 if (CHREC_LEFT (chrec
) != op0
2551 || CHREC_RIGHT (chrec
) != op1
)
2553 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2554 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2560 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2561 and EVOLUTION_LOOP, that were left under a symbolic form.
2563 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2565 CACHE is the cache of already instantiated values.
2567 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2568 conversions that may wrap in signed/pointer type are folded, as long
2569 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2570 then we don't do such fold.
2572 SIZE_EXPR is used for computing the size of the expression to be
2573 instantiated, and to stop if it exceeds some limit. */
2576 instantiate_scev_binary (edge instantiate_below
,
2577 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2578 tree chrec
, enum tree_code code
,
2579 tree type
, tree c0
, tree c1
,
2580 bool *fold_conversions
, int size_expr
)
2583 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2584 c0
, fold_conversions
, size_expr
);
2585 if (op0
== chrec_dont_know
)
2586 return chrec_dont_know
;
2588 /* While we eventually compute the same op1 if c0 == c1 the process
2589 of doing this is expensive so the following short-cut prevents
2590 exponential compile-time behavior. */
2593 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2594 c1
, fold_conversions
, size_expr
);
2595 if (op1
== chrec_dont_know
)
2596 return chrec_dont_know
;
2604 op0
= chrec_convert (type
, op0
, NULL
);
2605 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2609 case POINTER_PLUS_EXPR
:
2611 return chrec_fold_plus (type
, op0
, op1
);
2614 return chrec_fold_minus (type
, op0
, op1
);
2617 return chrec_fold_multiply (type
, op0
, op1
);
2624 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2627 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2628 and EVOLUTION_LOOP, that were left under a symbolic form.
2630 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2633 CACHE is the cache of already instantiated values.
2635 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2636 conversions that may wrap in signed/pointer type are folded, as long
2637 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2638 then we don't do such fold.
2640 SIZE_EXPR is used for computing the size of the expression to be
2641 instantiated, and to stop if it exceeds some limit. */
2644 instantiate_scev_convert (edge instantiate_below
,
2645 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2646 tree chrec
, tree type
, tree op
,
2647 bool *fold_conversions
, int size_expr
)
2649 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2651 fold_conversions
, size_expr
);
2653 if (op0
== chrec_dont_know
)
2654 return chrec_dont_know
;
2656 if (fold_conversions
)
2658 tree tmp
= chrec_convert_aggressive (type
, op0
, fold_conversions
);
2662 /* If we used chrec_convert_aggressive, we can no longer assume that
2663 signed chrecs do not overflow, as chrec_convert does, so avoid
2664 calling it in that case. */
2665 if (*fold_conversions
)
2667 if (chrec
&& op0
== op
)
2670 return fold_convert (type
, op0
);
2674 return chrec_convert (type
, op0
, NULL
);
2677 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2678 and EVOLUTION_LOOP, that were left under a symbolic form.
2680 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2681 Handle ~X as -1 - X.
2682 Handle -X as -1 * X.
2684 CACHE is the cache of already instantiated values.
2686 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2687 conversions that may wrap in signed/pointer type are folded, as long
2688 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2689 then we don't do such fold.
2691 SIZE_EXPR is used for computing the size of the expression to be
2692 instantiated, and to stop if it exceeds some limit. */
2695 instantiate_scev_not (edge instantiate_below
,
2696 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2698 enum tree_code code
, tree type
, tree op
,
2699 bool *fold_conversions
, int size_expr
)
2701 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2703 fold_conversions
, size_expr
);
2705 if (op0
== chrec_dont_know
)
2706 return chrec_dont_know
;
2710 op0
= chrec_convert (type
, op0
, NULL
);
2715 return chrec_fold_minus
2716 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2719 return chrec_fold_multiply
2720 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2727 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2730 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2731 and EVOLUTION_LOOP, that were left under a symbolic form.
2733 CHREC is the scalar evolution to instantiate.
2735 CACHE is the cache of already instantiated values.
2737 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2738 conversions that may wrap in signed/pointer type are folded, as long
2739 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2740 then we don't do such fold.
2742 SIZE_EXPR is used for computing the size of the expression to be
2743 instantiated, and to stop if it exceeds some limit. */
2746 instantiate_scev_r (edge instantiate_below
,
2747 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2749 bool *fold_conversions
, int size_expr
)
2751 /* Give up if the expression is larger than the MAX that we allow. */
2752 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2753 return chrec_dont_know
;
2755 if (chrec
== NULL_TREE
2756 || automatically_generated_chrec_p (chrec
)
2757 || is_gimple_min_invariant (chrec
))
2760 switch (TREE_CODE (chrec
))
2763 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2765 fold_conversions
, size_expr
);
2767 case POLYNOMIAL_CHREC
:
2768 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2770 fold_conversions
, size_expr
);
2772 case POINTER_PLUS_EXPR
:
2776 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2778 TREE_CODE (chrec
), chrec_type (chrec
),
2779 TREE_OPERAND (chrec
, 0),
2780 TREE_OPERAND (chrec
, 1),
2781 fold_conversions
, size_expr
);
2784 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2786 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2787 fold_conversions
, size_expr
);
2791 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2793 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2794 TREE_OPERAND (chrec
, 0),
2795 fold_conversions
, size_expr
);
2798 if (is_gimple_min_invariant (chrec
))
2801 case SCEV_NOT_KNOWN
:
2802 return chrec_dont_know
;
2808 if (CONSTANT_CLASS_P (chrec
))
2810 return chrec_dont_know
;
2814 /* Analyze all the parameters of the chrec that were left under a
2815 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2816 recursive instantiation of parameters: a parameter is a variable
2817 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2818 a function parameter. */
2821 instantiate_scev (edge instantiate_below
, struct loop
*evolution_loop
,
2826 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2828 fprintf (dump_file
, "(instantiate_scev \n");
2829 fprintf (dump_file
, " (instantiate_below = %d -> %d)\n",
2830 instantiate_below
->src
->index
, instantiate_below
->dest
->index
);
2832 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2833 fprintf (dump_file
, " (chrec = ");
2834 print_generic_expr (dump_file
, chrec
);
2835 fprintf (dump_file
, ")\n");
2841 global_cache
= new instantiate_cache_type
;
2845 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2846 NULL
, chrec
, NULL
, 0);
2850 delete global_cache
;
2851 global_cache
= NULL
;
2854 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2856 fprintf (dump_file
, " (res = ");
2857 print_generic_expr (dump_file
, res
);
2858 fprintf (dump_file
, "))\n");
2864 /* Similar to instantiate_parameters, but does not introduce the
2865 evolutions in outer loops for LOOP invariants in CHREC, and does not
2866 care about causing overflows, as long as they do not affect value
2867 of an expression. */
2870 resolve_mixers (struct loop
*loop
, tree chrec
, bool *folded_casts
)
2873 bool fold_conversions
= false;
2876 global_cache
= new instantiate_cache_type
;
2880 tree ret
= instantiate_scev_r (loop_preheader_edge (loop
), loop
, NULL
,
2881 chrec
, &fold_conversions
, 0);
2883 if (folded_casts
&& !*folded_casts
)
2884 *folded_casts
= fold_conversions
;
2888 delete global_cache
;
2889 global_cache
= NULL
;
2895 /* Entry point for the analysis of the number of iterations pass.
2896 This function tries to safely approximate the number of iterations
2897 the loop will run. When this property is not decidable at compile
2898 time, the result is chrec_dont_know. Otherwise the result is a
2899 scalar or a symbolic parameter. When the number of iterations may
2900 be equal to zero and the property cannot be determined at compile
2901 time, the result is a COND_EXPR that represents in a symbolic form
2902 the conditions under which the number of iterations is not zero.
2904 Example of analysis: suppose that the loop has an exit condition:
2906 "if (b > 49) goto end_loop;"
2908 and that in a previous analysis we have determined that the
2909 variable 'b' has an evolution function:
2911 "EF = {23, +, 5}_2".
2913 When we evaluate the function at the point 5, i.e. the value of the
2914 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2915 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2916 the loop body has been executed 6 times. */
2919 number_of_latch_executions (struct loop
*loop
)
2922 struct tree_niter_desc niter_desc
;
2926 /* Determine whether the number of iterations in loop has already
2928 res
= loop
->nb_iterations
;
2932 may_be_zero
= NULL_TREE
;
2934 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2935 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2937 res
= chrec_dont_know
;
2938 exit
= single_exit (loop
);
2940 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2942 may_be_zero
= niter_desc
.may_be_zero
;
2943 res
= niter_desc
.niter
;
2946 if (res
== chrec_dont_know
2948 || integer_zerop (may_be_zero
))
2950 else if (integer_nonzerop (may_be_zero
))
2951 res
= build_int_cst (TREE_TYPE (res
), 0);
2953 else if (COMPARISON_CLASS_P (may_be_zero
))
2954 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2955 build_int_cst (TREE_TYPE (res
), 0), res
);
2957 res
= chrec_dont_know
;
2959 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2961 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2962 print_generic_expr (dump_file
, res
);
2963 fprintf (dump_file
, "))\n");
2966 loop
->nb_iterations
= res
;
2971 /* Counters for the stats. */
2977 unsigned nb_affine_multivar
;
2978 unsigned nb_higher_poly
;
2979 unsigned nb_chrec_dont_know
;
2980 unsigned nb_undetermined
;
2983 /* Reset the counters. */
2986 reset_chrecs_counters (struct chrec_stats
*stats
)
2988 stats
->nb_chrecs
= 0;
2989 stats
->nb_affine
= 0;
2990 stats
->nb_affine_multivar
= 0;
2991 stats
->nb_higher_poly
= 0;
2992 stats
->nb_chrec_dont_know
= 0;
2993 stats
->nb_undetermined
= 0;
2996 /* Dump the contents of a CHREC_STATS structure. */
2999 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
3001 fprintf (file
, "\n(\n");
3002 fprintf (file
, "-----------------------------------------\n");
3003 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
3004 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
3005 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
3006 stats
->nb_higher_poly
);
3007 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
3008 fprintf (file
, "-----------------------------------------\n");
3009 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
3010 fprintf (file
, "%d\twith undetermined coefficients\n",
3011 stats
->nb_undetermined
);
3012 fprintf (file
, "-----------------------------------------\n");
3013 fprintf (file
, "%d\tchrecs in the scev database\n",
3014 (int) scalar_evolution_info
->elements ());
3015 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
3016 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
3017 fprintf (file
, "-----------------------------------------\n");
3018 fprintf (file
, ")\n\n");
3021 /* Gather statistics about CHREC. */
3024 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
3026 if (dump_file
&& (dump_flags
& TDF_STATS
))
3028 fprintf (dump_file
, "(classify_chrec ");
3029 print_generic_expr (dump_file
, chrec
);
3030 fprintf (dump_file
, "\n");
3035 if (chrec
== NULL_TREE
)
3037 stats
->nb_undetermined
++;
3041 switch (TREE_CODE (chrec
))
3043 case POLYNOMIAL_CHREC
:
3044 if (evolution_function_is_affine_p (chrec
))
3046 if (dump_file
&& (dump_flags
& TDF_STATS
))
3047 fprintf (dump_file
, " affine_univariate\n");
3050 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3052 if (dump_file
&& (dump_flags
& TDF_STATS
))
3053 fprintf (dump_file
, " affine_multivariate\n");
3054 stats
->nb_affine_multivar
++;
3058 if (dump_file
&& (dump_flags
& TDF_STATS
))
3059 fprintf (dump_file
, " higher_degree_polynomial\n");
3060 stats
->nb_higher_poly
++;
3069 if (chrec_contains_undetermined (chrec
))
3071 if (dump_file
&& (dump_flags
& TDF_STATS
))
3072 fprintf (dump_file
, " undetermined\n");
3073 stats
->nb_undetermined
++;
3076 if (dump_file
&& (dump_flags
& TDF_STATS
))
3077 fprintf (dump_file
, ")\n");
3080 /* Classify the chrecs of the whole database. */
3083 gather_stats_on_scev_database (void)
3085 struct chrec_stats stats
;
3090 reset_chrecs_counters (&stats
);
3092 hash_table
<scev_info_hasher
>::iterator iter
;
3094 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info
, elt
, scev_info_str
*,
3096 gather_chrec_stats (elt
->chrec
, &stats
);
3098 dump_chrecs_stats (dump_file
, &stats
);
3106 initialize_scalar_evolutions_analyzer (void)
3108 /* The elements below are unique. */
3109 if (chrec_dont_know
== NULL_TREE
)
3111 chrec_not_analyzed_yet
= NULL_TREE
;
3112 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3113 chrec_known
= make_node (SCEV_KNOWN
);
3114 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3115 TREE_TYPE (chrec_known
) = void_type_node
;
3119 /* Initialize the analysis of scalar evolutions for LOOPS. */
3122 scev_initialize (void)
3126 gcc_assert (! scev_initialized_p ());
3128 scalar_evolution_info
= hash_table
<scev_info_hasher
>::create_ggc (100);
3130 initialize_scalar_evolutions_analyzer ();
3132 FOR_EACH_LOOP (loop
, 0)
3134 loop
->nb_iterations
= NULL_TREE
;
3138 /* Return true if SCEV is initialized. */
3141 scev_initialized_p (void)
3143 return scalar_evolution_info
!= NULL
;
3146 /* Cleans up the information cached by the scalar evolutions analysis
3147 in the hash table. */
3150 scev_reset_htab (void)
3152 if (!scalar_evolution_info
)
3155 scalar_evolution_info
->empty ();
3158 /* Cleans up the information cached by the scalar evolutions analysis
3159 in the hash table and in the loop->nb_iterations. */
3168 FOR_EACH_LOOP (loop
, 0)
3170 loop
->nb_iterations
= NULL_TREE
;
3174 /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3175 of the upper bound on the number of iterations of LOOP, the BASE and STEP
3178 We do not use information whether TYPE can overflow so it is safe to
3179 use this test even for derived IVs not computed every iteration or
3180 hypotetical IVs to be inserted into code. */
3183 iv_can_overflow_p (struct loop
*loop
, tree type
, tree base
, tree step
)
3186 wide_int base_min
, base_max
, step_min
, step_max
, type_min
, type_max
;
3187 signop sgn
= TYPE_SIGN (type
);
3189 if (integer_zerop (step
))
3192 if (TREE_CODE (base
) == INTEGER_CST
)
3193 base_min
= base_max
= wi::to_wide (base
);
3194 else if (TREE_CODE (base
) == SSA_NAME
3195 && INTEGRAL_TYPE_P (TREE_TYPE (base
))
3196 && get_range_info (base
, &base_min
, &base_max
) == VR_RANGE
)
3201 if (TREE_CODE (step
) == INTEGER_CST
)
3202 step_min
= step_max
= wi::to_wide (step
);
3203 else if (TREE_CODE (step
) == SSA_NAME
3204 && INTEGRAL_TYPE_P (TREE_TYPE (step
))
3205 && get_range_info (step
, &step_min
, &step_max
) == VR_RANGE
)
3210 if (!get_max_loop_iterations (loop
, &nit
))
3213 type_min
= wi::min_value (type
);
3214 type_max
= wi::max_value (type
);
3216 /* Just sanity check that we don't see values out of the range of the type.
3217 In this case the arithmetics bellow would overflow. */
3218 gcc_checking_assert (wi::ge_p (base_min
, type_min
, sgn
)
3219 && wi::le_p (base_max
, type_max
, sgn
));
3221 /* Account the possible increment in the last ieration. */
3222 wi::overflow_type overflow
= wi::OVF_NONE
;
3223 nit
= wi::add (nit
, 1, SIGNED
, &overflow
);
3227 /* NIT is typeless and can exceed the precision of the type. In this case
3228 overflow is always possible, because we know STEP is non-zero. */
3229 if (wi::min_precision (nit
, UNSIGNED
) > TYPE_PRECISION (type
))
3231 wide_int nit2
= wide_int::from (nit
, TYPE_PRECISION (type
), UNSIGNED
);
3233 /* If step can be positive, check that nit*step <= type_max-base.
3234 This can be done by unsigned arithmetic and we only need to watch overflow
3235 in the multiplication. The right hand side can always be represented in
3237 if (sgn
== UNSIGNED
|| !wi::neg_p (step_max
))
3239 wi::overflow_type overflow
= wi::OVF_NONE
;
3240 if (wi::gtu_p (wi::mul (step_max
, nit2
, UNSIGNED
, &overflow
),
3241 type_max
- base_max
)
3245 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3246 if (sgn
== SIGNED
&& wi::neg_p (step_min
))
3248 wi::overflow_type overflow
, overflow2
;
3249 overflow
= overflow2
= wi::OVF_NONE
;
3250 if (wi::gtu_p (wi::mul (wi::neg (step_min
, &overflow2
),
3251 nit2
, UNSIGNED
, &overflow
),
3252 base_min
- type_min
)
3253 || overflow
|| overflow2
)
3260 /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3261 function tries to derive condition under which it can be simplified
3262 into "{(type)inner_base, (type)inner_step}_loop". The condition is
3263 the maximum number that inner iv can iterate. */
3266 derive_simple_iv_with_niters (tree ev
, tree
*niters
)
3268 if (!CONVERT_EXPR_P (ev
))
3271 tree inner_ev
= TREE_OPERAND (ev
, 0);
3272 if (TREE_CODE (inner_ev
) != POLYNOMIAL_CHREC
)
3275 tree init
= CHREC_LEFT (inner_ev
);
3276 tree step
= CHREC_RIGHT (inner_ev
);
3277 if (TREE_CODE (init
) != INTEGER_CST
3278 || TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
3281 tree type
= TREE_TYPE (ev
);
3282 tree inner_type
= TREE_TYPE (inner_ev
);
3283 if (TYPE_PRECISION (inner_type
) >= TYPE_PRECISION (type
))
3286 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3287 folded only if inner iv won't overflow. We compute the maximum
3288 number the inner iv can iterate before overflowing and return the
3289 simplified affine iv. */
3291 init
= fold_convert (type
, init
);
3292 step
= fold_convert (type
, step
);
3293 ev
= build_polynomial_chrec (CHREC_VARIABLE (inner_ev
), init
, step
);
3294 if (tree_int_cst_sign_bit (step
))
3296 tree bound
= lower_bound_in_type (inner_type
, inner_type
);
3297 delta
= fold_build2 (MINUS_EXPR
, type
, init
, fold_convert (type
, bound
));
3298 step
= fold_build1 (NEGATE_EXPR
, type
, step
);
3302 tree bound
= upper_bound_in_type (inner_type
, inner_type
);
3303 delta
= fold_build2 (MINUS_EXPR
, type
, fold_convert (type
, bound
), init
);
3305 *niters
= fold_build2 (FLOOR_DIV_EXPR
, type
, delta
, step
);
3309 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3310 respect to WRTO_LOOP and returns its base and step in IV if possible
3311 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3312 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3313 invariant in LOOP. Otherwise we require it to be an integer constant.
3315 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3316 because it is computed in signed arithmetics). Consequently, adding an
3319 for (i = IV->base; ; i += IV->step)
3321 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3322 false for the type of the induction variable, or you can prove that i does
3323 not wrap by some other argument. Otherwise, this might introduce undefined
3327 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3329 must be used instead.
3331 When IV_NITERS is not NULL, this function also checks case in which OP
3332 is a conversion of an inner simple iv of below form:
3334 (outer_type){inner_base, inner_step}_loop.
3336 If type of inner iv has smaller precision than outer_type, it can't be
3337 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3338 the inner iv could overflow/wrap. In this case, we derive a condition
3339 under which the inner iv won't overflow/wrap and do the simplification.
3340 The derived condition normally is the maximum number the inner iv can
3341 iterate, and will be stored in IV_NITERS. This is useful in loop niter
3342 analysis, to derive break conditions when a loop must terminate, when is
3346 simple_iv_with_niters (struct loop
*wrto_loop
, struct loop
*use_loop
,
3347 tree op
, affine_iv
*iv
, tree
*iv_niters
,
3348 bool allow_nonconstant_step
)
3350 enum tree_code code
;
3351 tree type
, ev
, base
, e
;
3355 iv
->base
= NULL_TREE
;
3356 iv
->step
= NULL_TREE
;
3357 iv
->no_overflow
= false;
3359 type
= TREE_TYPE (op
);
3360 if (!POINTER_TYPE_P (type
)
3361 && !INTEGRAL_TYPE_P (type
))
3364 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3366 if (chrec_contains_undetermined (ev
)
3367 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3370 if (tree_does_not_contain_chrecs (ev
))
3373 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3374 iv
->no_overflow
= true;
3378 /* If we can derive valid scalar evolution with assumptions. */
3379 if (iv_niters
&& TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
3380 ev
= derive_simple_iv_with_niters (ev
, iv_niters
);
3382 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
3385 if (CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3388 iv
->step
= CHREC_RIGHT (ev
);
3389 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3390 || tree_contains_chrecs (iv
->step
, NULL
))
3393 iv
->base
= CHREC_LEFT (ev
);
3394 if (tree_contains_chrecs (iv
->base
, NULL
))
3397 iv
->no_overflow
= !folded_casts
&& nowrap_type_p (type
);
3399 if (!iv
->no_overflow
3400 && !iv_can_overflow_p (wrto_loop
, type
, iv
->base
, iv
->step
))
3401 iv
->no_overflow
= true;
3403 /* Try to simplify iv base:
3405 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3406 == (signed T)(unsigned T)base + step
3409 If we can prove operation (base + step) doesn't overflow or underflow.
3410 Specifically, we try to prove below conditions are satisfied:
3412 base <= UPPER_BOUND (type) - step ;;step > 0
3413 base >= LOWER_BOUND (type) - step ;;step < 0
3415 This is done by proving the reverse conditions are false using loop's
3418 The is necessary to make loop niter, or iv overflow analysis easier
3421 int foo (int *a, signed char s, signed char l)
3424 for (i = s; i < l; i++)
3429 Note variable I is firstly converted to type unsigned char, incremented,
3430 then converted back to type signed char. */
3432 if (wrto_loop
->num
!= use_loop
->num
)
3435 if (!CONVERT_EXPR_P (iv
->base
) || TREE_CODE (iv
->step
) != INTEGER_CST
)
3438 type
= TREE_TYPE (iv
->base
);
3439 e
= TREE_OPERAND (iv
->base
, 0);
3440 if (TREE_CODE (e
) != PLUS_EXPR
3441 || TREE_CODE (TREE_OPERAND (e
, 1)) != INTEGER_CST
3442 || !tree_int_cst_equal (iv
->step
,
3443 fold_convert (type
, TREE_OPERAND (e
, 1))))
3445 e
= TREE_OPERAND (e
, 0);
3446 if (!CONVERT_EXPR_P (e
))
3448 base
= TREE_OPERAND (e
, 0);
3449 if (!useless_type_conversion_p (type
, TREE_TYPE (base
)))
3452 if (tree_int_cst_sign_bit (iv
->step
))
3455 extreme
= wi::min_value (type
);
3460 extreme
= wi::max_value (type
);
3462 wi::overflow_type overflow
= wi::OVF_NONE
;
3463 extreme
= wi::sub (extreme
, wi::to_wide (iv
->step
),
3464 TYPE_SIGN (type
), &overflow
);
3467 e
= fold_build2 (code
, boolean_type_node
, base
,
3468 wide_int_to_tree (type
, extreme
));
3469 e
= simplify_using_initial_conditions (use_loop
, e
);
3470 if (!integer_zerop (e
))
3473 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3474 code
= POINTER_PLUS_EXPR
;
3478 iv
->base
= fold_build2 (code
, TREE_TYPE (base
), base
, iv
->step
);
3482 /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3483 affine iv unconditionally. */
3486 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3487 affine_iv
*iv
, bool allow_nonconstant_step
)
3489 return simple_iv_with_niters (wrto_loop
, use_loop
, op
, iv
,
3490 NULL
, allow_nonconstant_step
);
3493 /* Finalize the scalar evolution analysis. */
3496 scev_finalize (void)
3498 if (!scalar_evolution_info
)
3500 scalar_evolution_info
->empty ();
3501 scalar_evolution_info
= NULL
;
3502 free_numbers_of_iterations_estimates (cfun
);
3505 /* Returns true if the expression EXPR is considered to be too expensive
3506 for scev_const_prop. */
3509 expression_expensive_p (tree expr
)
3511 enum tree_code code
;
3513 if (is_gimple_val (expr
))
3516 code
= TREE_CODE (expr
);
3517 if (code
== TRUNC_DIV_EXPR
3518 || code
== CEIL_DIV_EXPR
3519 || code
== FLOOR_DIV_EXPR
3520 || code
== ROUND_DIV_EXPR
3521 || code
== TRUNC_MOD_EXPR
3522 || code
== CEIL_MOD_EXPR
3523 || code
== FLOOR_MOD_EXPR
3524 || code
== ROUND_MOD_EXPR
3525 || code
== EXACT_DIV_EXPR
)
3527 /* Division by power of two is usually cheap, so we allow it.
3528 Forbid anything else. */
3529 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3533 if (code
== CALL_EXPR
)
3536 call_expr_arg_iterator iter
;
3537 /* Even though is_inexpensive_builtin might say true, we will get a
3538 library call for popcount when backend does not have an instruction
3539 to do so. We consider this to be expenseive and generate
3540 __builtin_popcount only when backend defines it. */
3541 combined_fn cfn
= get_call_combined_fn (expr
);
3545 /* Check if opcode for popcount is available in the mode required. */
3546 if (optab_handler (popcount_optab
,
3547 TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr
, 0))))
3548 == CODE_FOR_nothing
)
3551 mode
= TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr
, 0)));
3552 scalar_int_mode int_mode
;
3554 /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
3555 double-word popcount by emitting two single-word popcount
3557 if (is_a
<scalar_int_mode
> (mode
, &int_mode
)
3558 && GET_MODE_SIZE (int_mode
) == 2 * UNITS_PER_WORD
3559 && (optab_handler (popcount_optab
, word_mode
)
3560 != CODE_FOR_nothing
))
3568 if (!is_inexpensive_builtin (get_callee_fndecl (expr
)))
3570 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
3571 if (expression_expensive_p (arg
))
3576 if (code
== COND_EXPR
)
3577 return (expression_expensive_p (TREE_OPERAND (expr
, 0))
3578 || (EXPR_P (TREE_OPERAND (expr
, 1))
3579 && EXPR_P (TREE_OPERAND (expr
, 2)))
3580 /* If either branch has side effects or could trap. */
3581 || TREE_SIDE_EFFECTS (TREE_OPERAND (expr
, 1))
3582 || generic_expr_could_trap_p (TREE_OPERAND (expr
, 1))
3583 || TREE_SIDE_EFFECTS (TREE_OPERAND (expr
, 0))
3584 || generic_expr_could_trap_p (TREE_OPERAND (expr
, 0))
3585 || expression_expensive_p (TREE_OPERAND (expr
, 1))
3586 || expression_expensive_p (TREE_OPERAND (expr
, 2)));
3588 switch (TREE_CODE_CLASS (code
))
3591 case tcc_comparison
:
3592 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3597 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3604 /* Do final value replacement for LOOP, return true if we did anything. */
3607 final_value_replacement_loop (struct loop
*loop
)
3609 /* If we do not know exact number of iterations of the loop, we cannot
3610 replace the final value. */
3611 edge exit
= single_exit (loop
);
3615 tree niter
= number_of_latch_executions (loop
);
3616 if (niter
== chrec_dont_know
)
3619 /* Ensure that it is possible to insert new statements somewhere. */
3620 if (!single_pred_p (exit
->dest
))
3621 split_loop_exit_edge (exit
);
3623 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3624 gimple_stmt_iterator gsi
= gsi_after_labels (exit
->dest
);
3626 struct loop
*ex_loop
3627 = superloop_at_depth (loop
,
3628 loop_depth (exit
->dest
->loop_father
) + 1);
3632 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3634 gphi
*phi
= psi
.phi ();
3635 tree rslt
= PHI_RESULT (phi
);
3636 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3637 if (virtual_operand_p (def
))
3643 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3644 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3651 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
,
3653 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3654 if (!tree_does_not_contain_chrecs (def
)
3655 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3656 /* Moving the computation from the loop may prolong life range
3657 of some ssa names, which may cause problems if they appear
3658 on abnormal edges. */
3659 || contains_abnormal_ssa_name_p (def
)
3660 /* Do not emit expensive expressions. The rationale is that
3661 when someone writes a code like
3663 while (n > 45) n -= 45;
3665 he probably knows that n is not large, and does not want it
3666 to be turned into n %= 45. */
3667 || expression_expensive_p (def
))
3669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3671 fprintf (dump_file
, "not replacing:\n ");
3672 print_gimple_stmt (dump_file
, phi
, 0);
3673 fprintf (dump_file
, "\n");
3679 /* Eliminate the PHI node and replace it by a computation outside
3683 fprintf (dump_file
, "\nfinal value replacement:\n ");
3684 print_gimple_stmt (dump_file
, phi
, 0);
3685 fprintf (dump_file
, " with expr: ");
3686 print_generic_expr (dump_file
, def
);
3689 def
= unshare_expr (def
);
3690 remove_phi_node (&psi
, false);
3692 /* If def's type has undefined overflow and there were folded
3693 casts, rewrite all stmts added for def into arithmetics
3694 with defined overflow behavior. */
3695 if (folded_casts
&& ANY_INTEGRAL_TYPE_P (TREE_TYPE (def
))
3696 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def
)))
3699 gimple_stmt_iterator gsi2
;
3700 def
= force_gimple_operand (def
, &stmts
, true, NULL_TREE
);
3701 gsi2
= gsi_start (stmts
);
3702 while (!gsi_end_p (gsi2
))
3704 gimple
*stmt
= gsi_stmt (gsi2
);
3705 gimple_stmt_iterator gsi3
= gsi2
;
3707 gsi_remove (&gsi3
, false);
3708 if (is_gimple_assign (stmt
)
3709 && arith_code_with_undefined_signed_overflow
3710 (gimple_assign_rhs_code (stmt
)))
3711 gsi_insert_seq_before (&gsi
,
3712 rewrite_to_defined_overflow (stmt
),
3715 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3719 def
= force_gimple_operand_gsi (&gsi
, def
, false, NULL_TREE
,
3720 true, GSI_SAME_STMT
);
3722 gassign
*ass
= gimple_build_assign (rslt
, def
);
3723 gsi_insert_before (&gsi
, ass
, GSI_SAME_STMT
);
3726 fprintf (dump_file
, "\n final stmt:\n ");
3727 print_gimple_stmt (dump_file
, ass
, 0);
3728 fprintf (dump_file
, "\n");
3735 #include "gt-tree-scalar-evolution.h"