1 /* Scalar evolution detector.
2 Copyright (C) 2003-2015 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"
265 #include "insn-config.h"
266 #include "emit-rtl.h"
267 #include "gimple-pretty-print.h"
269 #include "fold-const.h"
277 #include "internal-fn.h"
278 #include "gimplify.h"
279 #include "gimple-iterator.h"
280 #include "gimplify-me.h"
281 #include "tree-cfg.h"
282 #include "tree-ssa-loop-ivopts.h"
283 #include "tree-ssa-loop-manip.h"
284 #include "tree-ssa-loop-niter.h"
285 #include "tree-ssa-loop.h"
286 #include "tree-ssa.h"
288 #include "tree-chrec.h"
289 #include "tree-affine.h"
290 #include "tree-scalar-evolution.h"
291 #include "dumpfile.h"
293 #include "tree-ssa-propagate.h"
294 #include "gimple-fold.h"
296 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
297 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
300 /* The cached information about an SSA name with version NAME_VERSION,
301 claiming that below basic block with index INSTANTIATED_BELOW, the
302 value of the SSA name can be expressed as CHREC. */
304 struct GTY((for_user
)) scev_info_str
{
305 unsigned int name_version
;
306 int instantiated_below
;
310 /* Counters for the scev database. */
311 static unsigned nb_set_scev
= 0;
312 static unsigned nb_get_scev
= 0;
314 /* The following trees are unique elements. Thus the comparison of
315 another element to these elements should be done on the pointer to
316 these trees, and not on their value. */
318 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
319 tree chrec_not_analyzed_yet
;
321 /* Reserved to the cases where the analyzer has detected an
322 undecidable property at compile time. */
323 tree chrec_dont_know
;
325 /* When the analyzer has detected that a property will never
326 happen, then it qualifies it with chrec_known. */
329 struct scev_info_hasher
: ggc_ptr_hash
<scev_info_str
>
331 static hashval_t
hash (scev_info_str
*i
);
332 static bool equal (const scev_info_str
*a
, const scev_info_str
*b
);
335 static GTY (()) hash_table
<scev_info_hasher
> *scalar_evolution_info
;
338 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
340 static inline struct scev_info_str
*
341 new_scev_info_str (basic_block instantiated_below
, tree var
)
343 struct scev_info_str
*res
;
345 res
= ggc_alloc
<scev_info_str
> ();
346 res
->name_version
= SSA_NAME_VERSION (var
);
347 res
->chrec
= chrec_not_analyzed_yet
;
348 res
->instantiated_below
= instantiated_below
->index
;
353 /* Computes a hash function for database element ELT. */
356 scev_info_hasher::hash (scev_info_str
*elt
)
358 return elt
->name_version
^ elt
->instantiated_below
;
361 /* Compares database elements E1 and E2. */
364 scev_info_hasher::equal (const scev_info_str
*elt1
, const scev_info_str
*elt2
)
366 return (elt1
->name_version
== elt2
->name_version
367 && elt1
->instantiated_below
== elt2
->instantiated_below
);
370 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
371 A first query on VAR returns chrec_not_analyzed_yet. */
374 find_var_scev_info (basic_block instantiated_below
, tree var
)
376 struct scev_info_str
*res
;
377 struct scev_info_str tmp
;
379 tmp
.name_version
= SSA_NAME_VERSION (var
);
380 tmp
.instantiated_below
= instantiated_below
->index
;
381 scev_info_str
**slot
= scalar_evolution_info
->find_slot (&tmp
, INSERT
);
384 *slot
= new_scev_info_str (instantiated_below
, var
);
390 /* Return true when CHREC contains symbolic names defined in
394 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
398 if (chrec
== NULL_TREE
)
401 if (is_gimple_min_invariant (chrec
))
404 if (TREE_CODE (chrec
) == SSA_NAME
)
407 loop_p def_loop
, loop
;
409 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
412 def
= SSA_NAME_DEF_STMT (chrec
);
413 def_loop
= loop_containing_stmt (def
);
414 loop
= get_loop (cfun
, loop_nb
);
416 if (def_loop
== NULL
)
419 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
425 n
= TREE_OPERAND_LENGTH (chrec
);
426 for (i
= 0; i
< n
; i
++)
427 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
433 /* Return true when PHI is a loop-phi-node. */
436 loop_phi_node_p (gimple
*phi
)
438 /* The implementation of this function is based on the following
439 property: "all the loop-phi-nodes of a loop are contained in the
440 loop's header basic block". */
442 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
445 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
446 In general, in the case of multivariate evolutions we want to get
447 the evolution in different loops. LOOP specifies the level for
448 which to get the evolution.
452 | for (j = 0; j < 100; j++)
454 | for (k = 0; k < 100; k++)
456 | i = k + j; - Here the value of i is a function of j, k.
458 | ... = i - Here the value of i is a function of j.
460 | ... = i - Here the value of i is a scalar.
466 | i_1 = phi (i_0, i_2)
470 This loop has the same effect as:
471 LOOP_1 has the same effect as:
475 The overall effect of the loop, "i_0 + 20" in the previous example,
476 is obtained by passing in the parameters: LOOP = 1,
477 EVOLUTION_FN = {i_0, +, 2}_1.
481 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
485 if (evolution_fn
== chrec_dont_know
)
486 return chrec_dont_know
;
488 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
490 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
492 if (inner_loop
== loop
493 || flow_loop_nested_p (loop
, inner_loop
))
495 tree nb_iter
= number_of_latch_executions (inner_loop
);
497 if (nb_iter
== chrec_dont_know
)
498 return chrec_dont_know
;
503 /* evolution_fn is the evolution function in LOOP. Get
504 its value in the nb_iter-th iteration. */
505 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
507 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
508 res
= instantiate_parameters (loop
, res
);
510 /* Continue the computation until ending on a parent of LOOP. */
511 return compute_overall_effect_of_inner_loop (loop
, res
);
518 /* If the evolution function is an invariant, there is nothing to do. */
519 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
523 return chrec_dont_know
;
526 /* Associate CHREC to SCALAR. */
529 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
533 if (TREE_CODE (scalar
) != SSA_NAME
)
536 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
540 if (dump_flags
& TDF_SCEV
)
542 fprintf (dump_file
, "(set_scalar_evolution \n");
543 fprintf (dump_file
, " instantiated_below = %d \n",
544 instantiated_below
->index
);
545 fprintf (dump_file
, " (scalar = ");
546 print_generic_expr (dump_file
, scalar
, 0);
547 fprintf (dump_file
, ")\n (scalar_evolution = ");
548 print_generic_expr (dump_file
, chrec
, 0);
549 fprintf (dump_file
, "))\n");
551 if (dump_flags
& TDF_STATS
)
555 *scalar_info
= chrec
;
558 /* Retrieve the chrec associated to SCALAR instantiated below
559 INSTANTIATED_BELOW block. */
562 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
568 if (dump_flags
& TDF_SCEV
)
570 fprintf (dump_file
, "(get_scalar_evolution \n");
571 fprintf (dump_file
, " (scalar = ");
572 print_generic_expr (dump_file
, scalar
, 0);
573 fprintf (dump_file
, ")\n");
575 if (dump_flags
& TDF_STATS
)
579 switch (TREE_CODE (scalar
))
582 res
= *find_var_scev_info (instantiated_below
, scalar
);
592 res
= chrec_not_analyzed_yet
;
596 if (dump_file
&& (dump_flags
& TDF_SCEV
))
598 fprintf (dump_file
, " (scalar_evolution = ");
599 print_generic_expr (dump_file
, res
, 0);
600 fprintf (dump_file
, "))\n");
606 /* Helper function for add_to_evolution. Returns the evolution
607 function for an assignment of the form "a = b + c", where "a" and
608 "b" are on the strongly connected component. CHREC_BEFORE is the
609 information that we already have collected up to this point.
610 TO_ADD is the evolution of "c".
612 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
613 evolution the expression TO_ADD, otherwise construct an evolution
614 part for this loop. */
617 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
620 tree type
, left
, right
;
621 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
623 switch (TREE_CODE (chrec_before
))
625 case POLYNOMIAL_CHREC
:
626 chloop
= get_chrec_loop (chrec_before
);
628 || flow_loop_nested_p (chloop
, loop
))
632 type
= chrec_type (chrec_before
);
634 /* When there is no evolution part in this loop, build it. */
639 right
= SCALAR_FLOAT_TYPE_P (type
)
640 ? build_real (type
, dconst0
)
641 : build_int_cst (type
, 0);
645 var
= CHREC_VARIABLE (chrec_before
);
646 left
= CHREC_LEFT (chrec_before
);
647 right
= CHREC_RIGHT (chrec_before
);
650 to_add
= chrec_convert (type
, to_add
, at_stmt
);
651 right
= chrec_convert_rhs (type
, right
, at_stmt
);
652 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
653 return build_polynomial_chrec (var
, left
, right
);
657 gcc_assert (flow_loop_nested_p (loop
, chloop
));
659 /* Search the evolution in LOOP_NB. */
660 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
662 right
= CHREC_RIGHT (chrec_before
);
663 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
664 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
669 /* These nodes do not depend on a loop. */
670 if (chrec_before
== chrec_dont_know
)
671 return chrec_dont_know
;
674 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
675 return build_polynomial_chrec (loop_nb
, left
, right
);
679 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
682 Description (provided for completeness, for those who read code in
683 a plane, and for my poor 62 bytes brain that would have forgotten
684 all this in the next two or three months):
686 The algorithm of translation of programs from the SSA representation
687 into the chrecs syntax is based on a pattern matching. After having
688 reconstructed the overall tree expression for a loop, there are only
689 two cases that can arise:
691 1. a = loop-phi (init, a + expr)
692 2. a = loop-phi (init, expr)
694 where EXPR is either a scalar constant with respect to the analyzed
695 loop (this is a degree 0 polynomial), or an expression containing
696 other loop-phi definitions (these are higher degree polynomials).
703 | a = phi (init, a + 5)
710 | a = phi (inita, 2 * b + 3)
711 | b = phi (initb, b + 1)
714 For the first case, the semantics of the SSA representation is:
716 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
718 that is, there is a loop index "x" that determines the scalar value
719 of the variable during the loop execution. During the first
720 iteration, the value is that of the initial condition INIT, while
721 during the subsequent iterations, it is the sum of the initial
722 condition with the sum of all the values of EXPR from the initial
723 iteration to the before last considered iteration.
725 For the second case, the semantics of the SSA program is:
727 | a (x) = init, if x = 0;
728 | expr (x - 1), otherwise.
730 The second case corresponds to the PEELED_CHREC, whose syntax is
731 close to the syntax of a loop-phi-node:
733 | phi (init, expr) vs. (init, expr)_x
735 The proof of the translation algorithm for the first case is a
736 proof by structural induction based on the degree of EXPR.
739 When EXPR is a constant with respect to the analyzed loop, or in
740 other words when EXPR is a polynomial of degree 0, the evolution of
741 the variable A in the loop is an affine function with an initial
742 condition INIT, and a step EXPR. In order to show this, we start
743 from the semantics of the SSA representation:
745 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
747 and since "expr (j)" is a constant with respect to "j",
749 f (x) = init + x * expr
751 Finally, based on the semantics of the pure sum chrecs, by
752 identification we get the corresponding chrecs syntax:
754 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
755 f (x) -> {init, +, expr}_x
758 Suppose that EXPR is a polynomial of degree N with respect to the
759 analyzed loop_x for which we have already determined that it is
760 written under the chrecs syntax:
762 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
764 We start from the semantics of the SSA program:
766 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
768 | f (x) = init + \sum_{j = 0}^{x - 1}
769 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
771 | f (x) = init + \sum_{j = 0}^{x - 1}
772 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
774 | f (x) = init + \sum_{k = 0}^{n - 1}
775 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
777 | f (x) = init + \sum_{k = 0}^{n - 1}
778 | (b_k * \binom{x}{k + 1})
780 | f (x) = init + b_0 * \binom{x}{1} + ...
781 | + b_{n-1} * \binom{x}{n}
783 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
784 | + b_{n-1} * \binom{x}{n}
787 And finally from the definition of the chrecs syntax, we identify:
788 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
790 This shows the mechanism that stands behind the add_to_evolution
791 function. An important point is that the use of symbolic
792 parameters avoids the need of an analysis schedule.
799 | a = phi (inita, a + 2 + b)
800 | b = phi (initb, b + 1)
803 When analyzing "a", the algorithm keeps "b" symbolically:
805 | a -> {inita, +, 2 + b}_1
807 Then, after instantiation, the analyzer ends on the evolution:
809 | a -> {inita, +, 2 + initb, +, 1}_1
814 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
815 tree to_add
, gimple
*at_stmt
)
817 tree type
= chrec_type (to_add
);
818 tree res
= NULL_TREE
;
820 if (to_add
== NULL_TREE
)
823 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
824 instantiated at this point. */
825 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
826 /* This should not happen. */
827 return chrec_dont_know
;
829 if (dump_file
&& (dump_flags
& TDF_SCEV
))
831 fprintf (dump_file
, "(add_to_evolution \n");
832 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
833 fprintf (dump_file
, " (chrec_before = ");
834 print_generic_expr (dump_file
, chrec_before
, 0);
835 fprintf (dump_file
, ")\n (to_add = ");
836 print_generic_expr (dump_file
, to_add
, 0);
837 fprintf (dump_file
, ")\n");
840 if (code
== MINUS_EXPR
)
841 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
842 ? build_real (type
, dconstm1
)
843 : build_int_cst_type (type
, -1));
845 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
847 if (dump_file
&& (dump_flags
& TDF_SCEV
))
849 fprintf (dump_file
, " (res = ");
850 print_generic_expr (dump_file
, res
, 0);
851 fprintf (dump_file
, "))\n");
859 /* This section selects the loops that will be good candidates for the
860 scalar evolution analysis. For the moment, greedily select all the
861 loop nests we could analyze. */
863 /* For a loop with a single exit edge, return the COND_EXPR that
864 guards the exit edge. If the expression is too difficult to
865 analyze, then give up. */
868 get_loop_exit_condition (const struct loop
*loop
)
871 edge exit_edge
= single_exit (loop
);
873 if (dump_file
&& (dump_flags
& TDF_SCEV
))
874 fprintf (dump_file
, "(get_loop_exit_condition \n ");
880 stmt
= last_stmt (exit_edge
->src
);
881 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
885 if (dump_file
&& (dump_flags
& TDF_SCEV
))
887 print_gimple_stmt (dump_file
, res
, 0, 0);
888 fprintf (dump_file
, ")\n");
895 /* Depth first search algorithm. */
904 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
*, gphi
*,
907 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
908 Return true if the strongly connected component has been found. */
911 follow_ssa_edge_binary (struct loop
*loop
, gimple
*at_stmt
,
912 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
913 gphi
*halting_phi
, tree
*evolution_of_loop
,
916 t_bool res
= t_false
;
921 case POINTER_PLUS_EXPR
:
923 if (TREE_CODE (rhs0
) == SSA_NAME
)
925 if (TREE_CODE (rhs1
) == SSA_NAME
)
927 /* Match an assignment under the form:
930 /* We want only assignments of form "name + name" contribute to
931 LIMIT, as the other cases do not necessarily contribute to
932 the complexity of the expression. */
935 evol
= *evolution_of_loop
;
936 evol
= add_to_evolution
938 chrec_convert (type
, evol
, at_stmt
),
939 code
, rhs1
, at_stmt
);
940 res
= follow_ssa_edge
941 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
943 *evolution_of_loop
= evol
;
944 else if (res
== t_false
)
946 *evolution_of_loop
= add_to_evolution
948 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
949 code
, rhs0
, at_stmt
);
950 res
= follow_ssa_edge
951 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
952 evolution_of_loop
, limit
);
955 else if (res
== t_dont_know
)
956 *evolution_of_loop
= chrec_dont_know
;
959 else if (res
== t_dont_know
)
960 *evolution_of_loop
= chrec_dont_know
;
965 /* Match an assignment under the form:
967 *evolution_of_loop
= add_to_evolution
968 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
970 code
, rhs1
, at_stmt
);
971 res
= follow_ssa_edge
972 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
973 evolution_of_loop
, limit
);
976 else if (res
== t_dont_know
)
977 *evolution_of_loop
= chrec_dont_know
;
981 else if (TREE_CODE (rhs1
) == SSA_NAME
)
983 /* Match an assignment under the form:
985 *evolution_of_loop
= add_to_evolution
986 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
988 code
, rhs0
, at_stmt
);
989 res
= follow_ssa_edge
990 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
991 evolution_of_loop
, limit
);
994 else if (res
== t_dont_know
)
995 *evolution_of_loop
= chrec_dont_know
;
999 /* Otherwise, match an assignment under the form:
1001 /* And there is nothing to do. */
1006 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1007 if (TREE_CODE (rhs0
) == SSA_NAME
)
1009 /* Match an assignment under the form:
1012 /* We want only assignments of form "name - name" contribute to
1013 LIMIT, as the other cases do not necessarily contribute to
1014 the complexity of the expression. */
1015 if (TREE_CODE (rhs1
) == SSA_NAME
)
1018 *evolution_of_loop
= add_to_evolution
1019 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1020 MINUS_EXPR
, rhs1
, at_stmt
);
1021 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1022 evolution_of_loop
, limit
);
1025 else if (res
== t_dont_know
)
1026 *evolution_of_loop
= chrec_dont_know
;
1029 /* Otherwise, match an assignment under the form:
1031 /* And there is nothing to do. */
1042 /* Follow the ssa edge into the expression EXPR.
1043 Return true if the strongly connected component has been found. */
1046 follow_ssa_edge_expr (struct loop
*loop
, gimple
*at_stmt
, tree expr
,
1047 gphi
*halting_phi
, tree
*evolution_of_loop
,
1050 enum tree_code code
= TREE_CODE (expr
);
1051 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1054 /* The EXPR is one of the following cases:
1058 - a POINTER_PLUS_EXPR,
1061 - other cases are not yet handled. */
1066 /* This assignment is under the form "a_1 = (cast) rhs. */
1067 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1068 halting_phi
, evolution_of_loop
, limit
);
1069 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1073 /* This assignment is under the form "a_1 = 7". */
1078 /* This assignment is under the form: "a_1 = b_2". */
1079 res
= follow_ssa_edge
1080 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1083 case POINTER_PLUS_EXPR
:
1086 /* This case is under the form "rhs0 +- rhs1". */
1087 rhs0
= TREE_OPERAND (expr
, 0);
1088 rhs1
= TREE_OPERAND (expr
, 1);
1089 type
= TREE_TYPE (rhs0
);
1090 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1091 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1092 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1093 halting_phi
, evolution_of_loop
, limit
);
1097 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1098 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1100 expr
= TREE_OPERAND (expr
, 0);
1101 rhs0
= TREE_OPERAND (expr
, 0);
1102 rhs1
= TREE_OPERAND (expr
, 1);
1103 type
= TREE_TYPE (rhs0
);
1104 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1105 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1106 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1107 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1108 halting_phi
, evolution_of_loop
, limit
);
1115 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1116 It must be handled as a copy assignment of the form a_1 = a_2. */
1117 rhs0
= ASSERT_EXPR_VAR (expr
);
1118 if (TREE_CODE (rhs0
) == SSA_NAME
)
1119 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1120 halting_phi
, evolution_of_loop
, limit
);
1133 /* Follow the ssa edge into the right hand side of an assignment STMT.
1134 Return true if the strongly connected component has been found. */
1137 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple
*stmt
,
1138 gphi
*halting_phi
, tree
*evolution_of_loop
,
1141 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1142 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1148 /* This assignment is under the form "a_1 = (cast) rhs. */
1149 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1150 halting_phi
, evolution_of_loop
, limit
);
1151 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1154 case POINTER_PLUS_EXPR
:
1157 rhs1
= gimple_assign_rhs1 (stmt
);
1158 rhs2
= gimple_assign_rhs2 (stmt
);
1159 type
= TREE_TYPE (rhs1
);
1160 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1161 halting_phi
, evolution_of_loop
, limit
);
1165 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1166 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1167 halting_phi
, evolution_of_loop
, limit
);
1176 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1179 backedge_phi_arg_p (gphi
*phi
, int i
)
1181 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1183 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1184 about updating it anywhere, and this should work as well most of the
1186 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1192 /* Helper function for one branch of the condition-phi-node. Return
1193 true if the strongly connected component has been found following
1196 static inline t_bool
1197 follow_ssa_edge_in_condition_phi_branch (int i
,
1199 gphi
*condition_phi
,
1201 tree
*evolution_of_branch
,
1202 tree init_cond
, int limit
)
1204 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1205 *evolution_of_branch
= chrec_dont_know
;
1207 /* Do not follow back edges (they must belong to an irreducible loop, which
1208 we really do not want to worry about). */
1209 if (backedge_phi_arg_p (condition_phi
, i
))
1212 if (TREE_CODE (branch
) == SSA_NAME
)
1214 *evolution_of_branch
= init_cond
;
1215 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1216 evolution_of_branch
, limit
);
1219 /* This case occurs when one of the condition branches sets
1220 the variable to a constant: i.e. a phi-node like
1221 "a_2 = PHI <a_7(5), 2(6)>;".
1223 FIXME: This case have to be refined correctly:
1224 in some cases it is possible to say something better than
1225 chrec_dont_know, for example using a wrap-around notation. */
1229 /* This function merges the branches of a condition-phi-node in a
1233 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1234 gphi
*condition_phi
,
1236 tree
*evolution_of_loop
, int limit
)
1239 tree init
= *evolution_of_loop
;
1240 tree evolution_of_branch
;
1241 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1243 &evolution_of_branch
,
1245 if (res
== t_false
|| res
== t_dont_know
)
1248 *evolution_of_loop
= evolution_of_branch
;
1250 n
= gimple_phi_num_args (condition_phi
);
1251 for (i
= 1; i
< n
; i
++)
1253 /* Quickly give up when the evolution of one of the branches is
1255 if (*evolution_of_loop
== chrec_dont_know
)
1258 /* Increase the limit by the PHI argument number to avoid exponential
1259 time and memory complexity. */
1260 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1262 &evolution_of_branch
,
1264 if (res
== t_false
|| res
== t_dont_know
)
1267 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1268 evolution_of_branch
);
1274 /* Follow an SSA edge in an inner loop. It computes the overall
1275 effect of the loop, and following the symbolic initial conditions,
1276 it follows the edges in the parent loop. The inner loop is
1277 considered as a single statement. */
1280 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1281 gphi
*loop_phi_node
,
1283 tree
*evolution_of_loop
, int limit
)
1285 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1286 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1288 /* Sometimes, the inner loop is too difficult to analyze, and the
1289 result of the analysis is a symbolic parameter. */
1290 if (ev
== PHI_RESULT (loop_phi_node
))
1292 t_bool res
= t_false
;
1293 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1295 for (i
= 0; i
< n
; i
++)
1297 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1300 /* Follow the edges that exit the inner loop. */
1301 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1302 if (!flow_bb_inside_loop_p (loop
, bb
))
1303 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1305 evolution_of_loop
, limit
);
1310 /* If the path crosses this loop-phi, give up. */
1312 *evolution_of_loop
= chrec_dont_know
;
1317 /* Otherwise, compute the overall effect of the inner loop. */
1318 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1319 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1320 evolution_of_loop
, limit
);
1323 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1324 path that is analyzed on the return walk. */
1327 follow_ssa_edge (struct loop
*loop
, gimple
*def
, gphi
*halting_phi
,
1328 tree
*evolution_of_loop
, int limit
)
1330 struct loop
*def_loop
;
1332 if (gimple_nop_p (def
))
1335 /* Give up if the path is longer than the MAX that we allow. */
1336 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1339 def_loop
= loop_containing_stmt (def
);
1341 switch (gimple_code (def
))
1344 if (!loop_phi_node_p (def
))
1345 /* DEF is a condition-phi-node. Follow the branches, and
1346 record their evolutions. Finally, merge the collected
1347 information and set the approximation to the main
1349 return follow_ssa_edge_in_condition_phi
1350 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1353 /* When the analyzed phi is the halting_phi, the
1354 depth-first search is over: we have found a path from
1355 the halting_phi to itself in the loop. */
1356 if (def
== halting_phi
)
1359 /* Otherwise, the evolution of the HALTING_PHI depends
1360 on the evolution of another loop-phi-node, i.e. the
1361 evolution function is a higher degree polynomial. */
1362 if (def_loop
== loop
)
1366 if (flow_loop_nested_p (loop
, def_loop
))
1367 return follow_ssa_edge_inner_loop_phi
1368 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1375 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1376 evolution_of_loop
, limit
);
1379 /* At this level of abstraction, the program is just a set
1380 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1381 other node to be handled. */
1387 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1388 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1390 # i_17 = PHI <i_13(5), 0(3)>
1391 # _20 = PHI <_5(5), start_4(D)(3)>
1394 _5 = start_4(D) + i_13;
1396 Though variable _20 appears as a PEELED_CHREC in the form of
1397 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1402 simplify_peeled_chrec (struct loop
*loop
, tree arg
, tree init_cond
)
1404 aff_tree aff1
, aff2
;
1405 tree ev
, left
, right
, type
, step_val
;
1406 hash_map
<tree
, name_expansion
*> *peeled_chrec_map
= NULL
;
1408 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1409 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1410 return chrec_dont_know
;
1412 left
= CHREC_LEFT (ev
);
1413 right
= CHREC_RIGHT (ev
);
1414 type
= TREE_TYPE (left
);
1415 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1417 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1418 if "left" equals to "init + right". */
1419 if (operand_equal_p (left
, step_val
, 0))
1421 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1422 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1424 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1427 /* Try harder to check if they are equal. */
1428 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1429 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1430 free_affine_expand_cache (&peeled_chrec_map
);
1431 aff_combination_scale (&aff2
, -1);
1432 aff_combination_add (&aff1
, &aff2
);
1434 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1435 if "left" equals to "init + right". */
1436 if (aff_combination_zero_p (&aff1
))
1438 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1439 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1441 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1443 return chrec_dont_know
;
1446 /* Given a LOOP_PHI_NODE, this function determines the evolution
1447 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1450 analyze_evolution_in_loop (gphi
*loop_phi_node
,
1453 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1454 tree evolution_function
= chrec_not_analyzed_yet
;
1455 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1457 static bool simplify_peeled_chrec_p
= true;
1459 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1461 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1462 fprintf (dump_file
, " (loop_phi_node = ");
1463 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1464 fprintf (dump_file
, ")\n");
1467 for (i
= 0; i
< n
; i
++)
1469 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1474 /* Select the edges that enter the loop body. */
1475 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1476 if (!flow_bb_inside_loop_p (loop
, bb
))
1479 if (TREE_CODE (arg
) == SSA_NAME
)
1483 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1485 /* Pass in the initial condition to the follow edge function. */
1487 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1489 /* If ev_fn has no evolution in the inner loop, and the
1490 init_cond is not equal to ev_fn, then we have an
1491 ambiguity between two possible values, as we cannot know
1492 the number of iterations at this point. */
1493 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1494 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1495 && !operand_equal_p (init_cond
, ev_fn
, 0))
1496 ev_fn
= chrec_dont_know
;
1501 /* When it is impossible to go back on the same
1502 loop_phi_node by following the ssa edges, the
1503 evolution is represented by a peeled chrec, i.e. the
1504 first iteration, EV_FN has the value INIT_COND, then
1505 all the other iterations it has the value of ARG.
1506 For the moment, PEELED_CHREC nodes are not built. */
1509 ev_fn
= chrec_dont_know
;
1510 /* Try to recognize POLYNOMIAL_CHREC which appears in
1511 the form of PEELED_CHREC, but guard the process with
1512 a bool variable to keep the analyzer from infinite
1513 recurrence for real PEELED_RECs. */
1514 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1516 simplify_peeled_chrec_p
= false;
1517 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1518 simplify_peeled_chrec_p
= true;
1522 /* When there are multiple back edges of the loop (which in fact never
1523 happens currently, but nevertheless), merge their evolutions. */
1524 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1527 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1529 fprintf (dump_file
, " (evolution_function = ");
1530 print_generic_expr (dump_file
, evolution_function
, 0);
1531 fprintf (dump_file
, "))\n");
1534 return evolution_function
;
1537 /* Given a loop-phi-node, return the initial conditions of the
1538 variable on entry of the loop. When the CCP has propagated
1539 constants into the loop-phi-node, the initial condition is
1540 instantiated, otherwise the initial condition is kept symbolic.
1541 This analyzer does not analyze the evolution outside the current
1542 loop, and leaves this task to the on-demand tree reconstructor. */
1545 analyze_initial_condition (gphi
*loop_phi_node
)
1548 tree init_cond
= chrec_not_analyzed_yet
;
1549 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1551 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1553 fprintf (dump_file
, "(analyze_initial_condition \n");
1554 fprintf (dump_file
, " (loop_phi_node = \n");
1555 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1556 fprintf (dump_file
, ")\n");
1559 n
= gimple_phi_num_args (loop_phi_node
);
1560 for (i
= 0; i
< n
; i
++)
1562 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1563 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1565 /* When the branch is oriented to the loop's body, it does
1566 not contribute to the initial condition. */
1567 if (flow_bb_inside_loop_p (loop
, bb
))
1570 if (init_cond
== chrec_not_analyzed_yet
)
1576 if (TREE_CODE (branch
) == SSA_NAME
)
1578 init_cond
= chrec_dont_know
;
1582 init_cond
= chrec_merge (init_cond
, branch
);
1585 /* Ooops -- a loop without an entry??? */
1586 if (init_cond
== chrec_not_analyzed_yet
)
1587 init_cond
= chrec_dont_know
;
1589 /* During early loop unrolling we do not have fully constant propagated IL.
1590 Handle degenerate PHIs here to not miss important unrollings. */
1591 if (TREE_CODE (init_cond
) == SSA_NAME
)
1593 gimple
*def
= SSA_NAME_DEF_STMT (init_cond
);
1594 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
1596 tree res
= degenerate_phi_result (phi
);
1597 if (res
!= NULL_TREE
1598 /* Only allow invariants here, otherwise we may break
1599 loop-closed SSA form. */
1600 && is_gimple_min_invariant (res
))
1605 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1607 fprintf (dump_file
, " (init_cond = ");
1608 print_generic_expr (dump_file
, init_cond
, 0);
1609 fprintf (dump_file
, "))\n");
1615 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1618 interpret_loop_phi (struct loop
*loop
, gphi
*loop_phi_node
)
1621 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1624 if (phi_loop
!= loop
)
1626 struct loop
*subloop
;
1627 tree evolution_fn
= analyze_scalar_evolution
1628 (phi_loop
, PHI_RESULT (loop_phi_node
));
1630 /* Dive one level deeper. */
1631 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1633 /* Interpret the subloop. */
1634 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1638 /* Otherwise really interpret the loop phi. */
1639 init_cond
= analyze_initial_condition (loop_phi_node
);
1640 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1642 /* Verify we maintained the correct initial condition throughout
1643 possible conversions in the SSA chain. */
1644 if (res
!= chrec_dont_know
)
1646 tree new_init
= res
;
1647 if (CONVERT_EXPR_P (res
)
1648 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1649 new_init
= fold_convert (TREE_TYPE (res
),
1650 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1651 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1652 new_init
= CHREC_LEFT (res
);
1653 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1654 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1655 || !operand_equal_p (init_cond
, new_init
, 0))
1656 return chrec_dont_know
;
1662 /* This function merges the branches of a condition-phi-node,
1663 contained in the outermost loop, and whose arguments are already
1667 interpret_condition_phi (struct loop
*loop
, gphi
*condition_phi
)
1669 int i
, n
= gimple_phi_num_args (condition_phi
);
1670 tree res
= chrec_not_analyzed_yet
;
1672 for (i
= 0; i
< n
; i
++)
1676 if (backedge_phi_arg_p (condition_phi
, i
))
1678 res
= chrec_dont_know
;
1682 branch_chrec
= analyze_scalar_evolution
1683 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1685 res
= chrec_merge (res
, branch_chrec
);
1691 /* Interpret the operation RHS1 OP RHS2. If we didn't
1692 analyze this node before, follow the definitions until ending
1693 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1694 return path, this function propagates evolutions (ala constant copy
1695 propagation). OPND1 is not a GIMPLE expression because we could
1696 analyze the effect of an inner loop: see interpret_loop_phi. */
1699 interpret_rhs_expr (struct loop
*loop
, gimple
*at_stmt
,
1700 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1702 tree res
, chrec1
, chrec2
;
1705 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1707 if (is_gimple_min_invariant (rhs1
))
1708 return chrec_convert (type
, rhs1
, at_stmt
);
1710 if (code
== SSA_NAME
)
1711 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1714 if (code
== ASSERT_EXPR
)
1716 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1717 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1725 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1726 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1729 HOST_WIDE_INT bitsize
, bitpos
;
1736 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1737 &bitsize
, &bitpos
, &offset
,
1738 &mode
, &unsignedp
, &volatilep
, false);
1740 if (TREE_CODE (base
) == MEM_REF
)
1742 rhs2
= TREE_OPERAND (base
, 1);
1743 rhs1
= TREE_OPERAND (base
, 0);
1745 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1746 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1747 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1748 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1749 chrec1
= instantiate_parameters (loop
, chrec1
);
1750 chrec2
= instantiate_parameters (loop
, chrec2
);
1751 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1755 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1756 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1760 if (offset
!= NULL_TREE
)
1762 chrec2
= analyze_scalar_evolution (loop
, offset
);
1763 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1764 chrec2
= instantiate_parameters (loop
, chrec2
);
1765 res
= chrec_fold_plus (type
, res
, chrec2
);
1770 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1772 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1773 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1774 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1775 chrec3
= instantiate_parameters (loop
, chrec3
);
1776 res
= chrec_fold_plus (type
, res
, chrec3
);
1780 res
= chrec_dont_know
;
1783 case POINTER_PLUS_EXPR
:
1784 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1785 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1786 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1787 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1788 chrec1
= instantiate_parameters (loop
, chrec1
);
1789 chrec2
= instantiate_parameters (loop
, chrec2
);
1790 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
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 (type
, chrec2
, at_stmt
);
1798 chrec1
= instantiate_parameters (loop
, chrec1
);
1799 chrec2
= instantiate_parameters (loop
, chrec2
);
1800 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1804 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1805 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1806 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1807 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1808 chrec1
= instantiate_parameters (loop
, chrec1
);
1809 chrec2
= instantiate_parameters (loop
, chrec2
);
1810 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1814 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1815 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1816 /* TYPE may be integer, real or complex, so use fold_convert. */
1817 chrec1
= instantiate_parameters (loop
, chrec1
);
1818 res
= chrec_fold_multiply (type
, chrec1
,
1819 fold_convert (type
, integer_minus_one_node
));
1823 /* Handle ~X as -1 - X. */
1824 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1825 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1826 chrec1
= instantiate_parameters (loop
, chrec1
);
1827 res
= chrec_fold_minus (type
,
1828 fold_convert (type
, integer_minus_one_node
),
1833 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1834 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1835 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1836 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1837 chrec1
= instantiate_parameters (loop
, chrec1
);
1838 chrec2
= instantiate_parameters (loop
, chrec2
);
1839 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1843 /* Handle A<<B as A * (1<<B). */
1844 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1845 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1846 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1847 chrec1
= instantiate_parameters (loop
, chrec1
);
1848 chrec2
= instantiate_parameters (loop
, chrec2
);
1850 chrec2
= fold_build2 (LSHIFT_EXPR
, type
,
1851 build_int_cst (TREE_TYPE (rhs1
), 1),
1853 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1857 /* In case we have a truncation of a widened operation that in
1858 the truncated type has undefined overflow behavior analyze
1859 the operation done in an unsigned type of the same precision
1860 as the final truncation. We cannot derive a scalar evolution
1861 for the widened operation but for the truncated result. */
1862 if (TREE_CODE (type
) == INTEGER_TYPE
1863 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1864 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1865 && TYPE_OVERFLOW_UNDEFINED (type
)
1866 && TREE_CODE (rhs1
) == SSA_NAME
1867 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1868 && is_gimple_assign (def
)
1869 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1870 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1872 tree utype
= unsigned_type_for (type
);
1873 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1874 gimple_assign_rhs1 (def
),
1875 gimple_assign_rhs_code (def
),
1876 gimple_assign_rhs2 (def
));
1879 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1880 res
= chrec_convert (type
, chrec1
, at_stmt
);
1884 res
= chrec_dont_know
;
1891 /* Interpret the expression EXPR. */
1894 interpret_expr (struct loop
*loop
, gimple
*at_stmt
, tree expr
)
1896 enum tree_code code
;
1897 tree type
= TREE_TYPE (expr
), op0
, op1
;
1899 if (automatically_generated_chrec_p (expr
))
1902 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1903 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1904 return chrec_dont_know
;
1906 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1908 return interpret_rhs_expr (loop
, at_stmt
, type
,
1912 /* Interpret the rhs of the assignment STMT. */
1915 interpret_gimple_assign (struct loop
*loop
, gimple
*stmt
)
1917 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1918 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1920 return interpret_rhs_expr (loop
, stmt
, type
,
1921 gimple_assign_rhs1 (stmt
), code
,
1922 gimple_assign_rhs2 (stmt
));
1927 /* This section contains all the entry points:
1928 - number_of_iterations_in_loop,
1929 - analyze_scalar_evolution,
1930 - instantiate_parameters.
1933 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1934 common ancestor of DEF_LOOP and USE_LOOP. */
1937 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1938 struct loop
*def_loop
,
1944 if (def_loop
== wrto_loop
)
1947 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1948 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1950 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1953 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1956 /* Helper recursive function. */
1959 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1961 tree type
= TREE_TYPE (var
);
1964 struct loop
*def_loop
;
1966 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1967 return chrec_dont_know
;
1969 if (TREE_CODE (var
) != SSA_NAME
)
1970 return interpret_expr (loop
, NULL
, var
);
1972 def
= SSA_NAME_DEF_STMT (var
);
1973 bb
= gimple_bb (def
);
1974 def_loop
= bb
? bb
->loop_father
: NULL
;
1977 || !flow_bb_inside_loop_p (loop
, bb
))
1979 /* Keep the symbolic form. */
1984 if (res
!= chrec_not_analyzed_yet
)
1986 if (loop
!= bb
->loop_father
)
1987 res
= compute_scalar_evolution_in_loop
1988 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1993 if (loop
!= def_loop
)
1995 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1996 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
2001 switch (gimple_code (def
))
2004 res
= interpret_gimple_assign (loop
, def
);
2008 if (loop_phi_node_p (def
))
2009 res
= interpret_loop_phi (loop
, as_a
<gphi
*> (def
));
2011 res
= interpret_condition_phi (loop
, as_a
<gphi
*> (def
));
2015 res
= chrec_dont_know
;
2021 /* Keep the symbolic form. */
2022 if (res
== chrec_dont_know
)
2025 if (loop
== def_loop
)
2026 set_scalar_evolution (block_before_loop (loop
), var
, res
);
2031 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2032 LOOP. LOOP is the loop in which the variable is used.
2034 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2035 pointer to the statement that uses this variable, in order to
2036 determine the evolution function of the variable, use the following
2039 loop_p loop = loop_containing_stmt (stmt);
2040 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2041 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2045 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2049 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2051 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2052 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2053 fprintf (dump_file
, " (scalar = ");
2054 print_generic_expr (dump_file
, var
, 0);
2055 fprintf (dump_file
, ")\n");
2058 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2059 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
2061 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2062 fprintf (dump_file
, ")\n");
2067 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2070 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
2072 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2075 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2076 WRTO_LOOP (which should be a superloop of USE_LOOP)
2078 FOLDED_CASTS is set to true if resolve_mixers used
2079 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2080 at the moment in order to keep things simple).
2082 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2085 for (i = 0; i < 100; i++) -- loop 1
2087 for (j = 0; j < 100; j++) -- loop 2
2094 for (t = 0; t < 100; t++) -- loop 3
2101 Both k1 and k2 are invariants in loop3, thus
2102 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2103 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2105 As they are invariant, it does not matter whether we consider their
2106 usage in loop 3 or loop 2, hence
2107 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2108 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2109 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2110 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2112 Similarly for their evolutions with respect to loop 1. The values of K2
2113 in the use in loop 2 vary independently on loop 1, thus we cannot express
2114 the evolution with respect to loop 1:
2115 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2116 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2117 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2118 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2120 The value of k2 in the use in loop 1 is known, though:
2121 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2122 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2126 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2127 tree version
, bool *folded_casts
)
2130 tree ev
= version
, tmp
;
2132 /* We cannot just do
2134 tmp = analyze_scalar_evolution (use_loop, version);
2135 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2137 as resolve_mixers would query the scalar evolution with respect to
2138 wrto_loop. For example, in the situation described in the function
2139 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2142 analyze_scalar_evolution (use_loop, version) = k2
2144 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2145 k2 in loop 1 is 100, which is a wrong result, since we are interested
2146 in the value in loop 3.
2148 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2149 each time checking that there is no evolution in the inner loop. */
2152 *folded_casts
= false;
2155 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2156 ev
= resolve_mixers (use_loop
, tmp
, folded_casts
);
2158 if (use_loop
== wrto_loop
)
2161 /* If the value of the use changes in the inner loop, we cannot express
2162 its value in the outer loop (we might try to return interval chrec,
2163 but we do not have a user for it anyway) */
2164 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2166 return chrec_dont_know
;
2168 use_loop
= loop_outer (use_loop
);
2173 /* Hashtable helpers for a temporary hash-table used when
2174 instantiating a CHREC or resolving mixers. For this use
2175 instantiated_below is always the same. */
2177 struct instantiate_cache_type
2180 vec
<scev_info_str
> entries
;
2182 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2183 ~instantiate_cache_type ();
2184 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2185 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2188 instantiate_cache_type::~instantiate_cache_type ()
2197 /* Cache to avoid infinite recursion when instantiating an SSA name.
2198 Live during the outermost instantiate_scev or resolve_mixers call. */
2199 static instantiate_cache_type
*global_cache
;
2201 /* Computes a hash function for database element ELT. */
2203 static inline hashval_t
2204 hash_idx_scev_info (const void *elt_
)
2206 unsigned idx
= ((size_t) elt_
) - 2;
2207 return scev_info_hasher::hash (&global_cache
->entries
[idx
]);
2210 /* Compares database elements E1 and E2. */
2213 eq_idx_scev_info (const void *e1
, const void *e2
)
2215 unsigned idx1
= ((size_t) e1
) - 2;
2216 return scev_info_hasher::equal (&global_cache
->entries
[idx1
],
2217 (const scev_info_str
*) e2
);
2220 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2223 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2224 tree name
, basic_block instantiate_below
)
2228 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2229 cache
.entries
.create (10);
2233 e
.name_version
= SSA_NAME_VERSION (name
);
2234 e
.instantiated_below
= instantiate_below
->index
;
2235 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2236 scev_info_hasher::hash (&e
), INSERT
);
2239 e
.chrec
= chrec_not_analyzed_yet
;
2240 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2241 cache
.entries
.safe_push (e
);
2244 return ((size_t)*slot
) - 2;
2248 /* Return the closed_loop_phi node for VAR. If there is none, return
2252 loop_closed_phi_def (tree var
)
2259 if (var
== NULL_TREE
2260 || TREE_CODE (var
) != SSA_NAME
)
2263 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2264 exit
= single_exit (loop
);
2268 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2271 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2272 return PHI_RESULT (phi
);
2278 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2281 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2282 and EVOLUTION_LOOP, that were left under a symbolic form.
2284 CHREC is an SSA_NAME to be instantiated.
2286 CACHE is the cache of already instantiated values.
2288 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2289 conversions that may wrap in signed/pointer type are folded, as long
2290 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2291 then we don't do such fold.
2293 SIZE_EXPR is used for computing the size of the expression to be
2294 instantiated, and to stop if it exceeds some limit. */
2297 instantiate_scev_name (basic_block instantiate_below
,
2298 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2300 bool *fold_conversions
,
2304 struct loop
*def_loop
;
2305 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2307 /* A parameter (or loop invariant and we do not want to include
2308 evolutions in outer loops), nothing to do. */
2310 || loop_depth (def_bb
->loop_father
) == 0
2311 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2314 /* We cache the value of instantiated variable to avoid exponential
2315 time complexity due to reevaluations. We also store the convenient
2316 value in the cache in order to prevent infinite recursion -- we do
2317 not want to instantiate the SSA_NAME if it is in a mixer
2318 structure. This is used for avoiding the instantiation of
2319 recursively defined functions, such as:
2321 | a_2 -> {0, +, 1, +, a_2}_1 */
2323 unsigned si
= get_instantiated_value_entry (*global_cache
,
2324 chrec
, instantiate_below
);
2325 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2326 return global_cache
->get (si
);
2328 /* On recursion return chrec_dont_know. */
2329 global_cache
->set (si
, chrec_dont_know
);
2331 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2333 /* If the analysis yields a parametric chrec, instantiate the
2335 res
= analyze_scalar_evolution (def_loop
, chrec
);
2337 /* Don't instantiate default definitions. */
2338 if (TREE_CODE (res
) == SSA_NAME
2339 && SSA_NAME_IS_DEFAULT_DEF (res
))
2342 /* Don't instantiate loop-closed-ssa phi nodes. */
2343 else if (TREE_CODE (res
) == SSA_NAME
2344 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2345 > loop_depth (def_loop
))
2348 res
= loop_closed_phi_def (chrec
);
2352 /* When there is no loop_closed_phi_def, it means that the
2353 variable is not used after the loop: try to still compute the
2354 value of the variable when exiting the loop. */
2355 if (res
== NULL_TREE
)
2357 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2358 res
= analyze_scalar_evolution (loop
, chrec
);
2359 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2360 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2362 fold_conversions
, size_expr
);
2364 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2365 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2366 res
= chrec_dont_know
;
2369 else if (res
!= chrec_dont_know
)
2372 && def_bb
->loop_father
!= inner_loop
2373 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2374 /* ??? We could try to compute the overall effect of the loop here. */
2375 res
= chrec_dont_know
;
2377 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2379 fold_conversions
, size_expr
);
2382 /* Store the correct value to the cache. */
2383 global_cache
->set (si
, res
);
2387 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2388 and EVOLUTION_LOOP, that were left under a symbolic form.
2390 CHREC is a polynomial chain of recurrence to be instantiated.
2392 CACHE is the cache of already instantiated values.
2394 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2395 conversions that may wrap in signed/pointer type are folded, as long
2396 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2397 then we don't do such fold.
2399 SIZE_EXPR is used for computing the size of the expression to be
2400 instantiated, and to stop if it exceeds some limit. */
2403 instantiate_scev_poly (basic_block instantiate_below
,
2404 struct loop
*evolution_loop
, struct loop
*,
2405 tree chrec
, bool *fold_conversions
, int size_expr
)
2408 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2409 get_chrec_loop (chrec
),
2410 CHREC_LEFT (chrec
), fold_conversions
,
2412 if (op0
== chrec_dont_know
)
2413 return chrec_dont_know
;
2415 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2416 get_chrec_loop (chrec
),
2417 CHREC_RIGHT (chrec
), fold_conversions
,
2419 if (op1
== chrec_dont_know
)
2420 return chrec_dont_know
;
2422 if (CHREC_LEFT (chrec
) != op0
2423 || CHREC_RIGHT (chrec
) != op1
)
2425 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2426 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2432 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2433 and EVOLUTION_LOOP, that were left under a symbolic form.
2435 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2437 CACHE is the cache of already instantiated values.
2439 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2440 conversions that may wrap in signed/pointer type are folded, as long
2441 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2442 then we don't do such fold.
2444 SIZE_EXPR is used for computing the size of the expression to be
2445 instantiated, and to stop if it exceeds some limit. */
2448 instantiate_scev_binary (basic_block instantiate_below
,
2449 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2450 tree chrec
, enum tree_code code
,
2451 tree type
, tree c0
, tree c1
,
2452 bool *fold_conversions
, int size_expr
)
2455 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2456 c0
, fold_conversions
, size_expr
);
2457 if (op0
== chrec_dont_know
)
2458 return chrec_dont_know
;
2460 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2461 c1
, fold_conversions
, size_expr
);
2462 if (op1
== chrec_dont_know
)
2463 return chrec_dont_know
;
2468 op0
= chrec_convert (type
, op0
, NULL
);
2469 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2473 case POINTER_PLUS_EXPR
:
2475 return chrec_fold_plus (type
, op0
, op1
);
2478 return chrec_fold_minus (type
, op0
, op1
);
2481 return chrec_fold_multiply (type
, op0
, op1
);
2488 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2491 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2492 and EVOLUTION_LOOP, that were left under a symbolic form.
2494 "CHREC" is an array reference to be instantiated.
2496 CACHE is the cache of already instantiated values.
2498 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2499 conversions that may wrap in signed/pointer type are folded, as long
2500 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2501 then we don't do such fold.
2503 SIZE_EXPR is used for computing the size of the expression to be
2504 instantiated, and to stop if it exceeds some limit. */
2507 instantiate_array_ref (basic_block instantiate_below
,
2508 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2509 tree chrec
, bool *fold_conversions
, int size_expr
)
2512 tree index
= TREE_OPERAND (chrec
, 1);
2513 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2515 fold_conversions
, size_expr
);
2517 if (op1
== chrec_dont_know
)
2518 return chrec_dont_know
;
2520 if (chrec
&& op1
== index
)
2523 res
= unshare_expr (chrec
);
2524 TREE_OPERAND (res
, 1) = op1
;
2528 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2529 and EVOLUTION_LOOP, that were left under a symbolic form.
2531 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2534 CACHE is the cache of already instantiated values.
2536 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2537 conversions that may wrap in signed/pointer type are folded, as long
2538 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2539 then we don't do such fold.
2541 SIZE_EXPR is used for computing the size of the expression to be
2542 instantiated, and to stop if it exceeds some limit. */
2545 instantiate_scev_convert (basic_block instantiate_below
,
2546 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2547 tree chrec
, tree type
, tree op
,
2548 bool *fold_conversions
, int size_expr
)
2550 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2552 fold_conversions
, size_expr
);
2554 if (op0
== chrec_dont_know
)
2555 return chrec_dont_know
;
2557 if (fold_conversions
)
2559 tree tmp
= chrec_convert_aggressive (type
, op0
, fold_conversions
);
2563 /* If we used chrec_convert_aggressive, we can no longer assume that
2564 signed chrecs do not overflow, as chrec_convert does, so avoid
2565 calling it in that case. */
2566 if (*fold_conversions
)
2568 if (chrec
&& op0
== op
)
2571 return fold_convert (type
, op0
);
2575 return chrec_convert (type
, op0
, NULL
);
2578 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2579 and EVOLUTION_LOOP, that were left under a symbolic form.
2581 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2582 Handle ~X as -1 - X.
2583 Handle -X as -1 * X.
2585 CACHE is the cache of already instantiated values.
2587 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2588 conversions that may wrap in signed/pointer type are folded, as long
2589 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2590 then we don't do such fold.
2592 SIZE_EXPR is used for computing the size of the expression to be
2593 instantiated, and to stop if it exceeds some limit. */
2596 instantiate_scev_not (basic_block instantiate_below
,
2597 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2599 enum tree_code code
, tree type
, tree op
,
2600 bool *fold_conversions
, int size_expr
)
2602 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2604 fold_conversions
, size_expr
);
2606 if (op0
== chrec_dont_know
)
2607 return chrec_dont_know
;
2611 op0
= chrec_convert (type
, op0
, NULL
);
2616 return chrec_fold_minus
2617 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2620 return chrec_fold_multiply
2621 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2628 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2631 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2632 and EVOLUTION_LOOP, that were left under a symbolic form.
2634 CHREC is an expression with 3 operands to be instantiated.
2636 CACHE is the cache of already instantiated values.
2638 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2639 conversions that may wrap in signed/pointer type are folded, as long
2640 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2641 then we don't do such fold.
2643 SIZE_EXPR is used for computing the size of the expression to be
2644 instantiated, and to stop if it exceeds some limit. */
2647 instantiate_scev_3 (basic_block instantiate_below
,
2648 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2650 bool *fold_conversions
, int size_expr
)
2653 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2654 inner_loop
, TREE_OPERAND (chrec
, 0),
2655 fold_conversions
, size_expr
);
2656 if (op0
== chrec_dont_know
)
2657 return chrec_dont_know
;
2659 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2660 inner_loop
, TREE_OPERAND (chrec
, 1),
2661 fold_conversions
, size_expr
);
2662 if (op1
== chrec_dont_know
)
2663 return chrec_dont_know
;
2665 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2666 inner_loop
, TREE_OPERAND (chrec
, 2),
2667 fold_conversions
, size_expr
);
2668 if (op2
== chrec_dont_know
)
2669 return chrec_dont_know
;
2671 if (op0
== TREE_OPERAND (chrec
, 0)
2672 && op1
== TREE_OPERAND (chrec
, 1)
2673 && op2
== TREE_OPERAND (chrec
, 2))
2676 return fold_build3 (TREE_CODE (chrec
),
2677 TREE_TYPE (chrec
), op0
, op1
, op2
);
2680 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2681 and EVOLUTION_LOOP, that were left under a symbolic form.
2683 CHREC is an expression with 2 operands to be instantiated.
2685 CACHE is the cache of already instantiated values.
2687 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2688 conversions that may wrap in signed/pointer type are folded, as long
2689 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2690 then we don't do such fold.
2692 SIZE_EXPR is used for computing the size of the expression to be
2693 instantiated, and to stop if it exceeds some limit. */
2696 instantiate_scev_2 (basic_block instantiate_below
,
2697 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2699 bool *fold_conversions
, int size_expr
)
2702 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2703 inner_loop
, TREE_OPERAND (chrec
, 0),
2704 fold_conversions
, size_expr
);
2705 if (op0
== chrec_dont_know
)
2706 return chrec_dont_know
;
2708 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2709 inner_loop
, TREE_OPERAND (chrec
, 1),
2710 fold_conversions
, size_expr
);
2711 if (op1
== chrec_dont_know
)
2712 return chrec_dont_know
;
2714 if (op0
== TREE_OPERAND (chrec
, 0)
2715 && op1
== TREE_OPERAND (chrec
, 1))
2718 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2721 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2722 and EVOLUTION_LOOP, that were left under a symbolic form.
2724 CHREC is an expression with 2 operands to be instantiated.
2726 CACHE is the cache of already instantiated values.
2728 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2729 conversions that may wrap in signed/pointer type are folded, as long
2730 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2731 then we don't do such fold.
2733 SIZE_EXPR is used for computing the size of the expression to be
2734 instantiated, and to stop if it exceeds some limit. */
2737 instantiate_scev_1 (basic_block instantiate_below
,
2738 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2740 bool *fold_conversions
, int size_expr
)
2742 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2743 inner_loop
, TREE_OPERAND (chrec
, 0),
2744 fold_conversions
, size_expr
);
2746 if (op0
== chrec_dont_know
)
2747 return chrec_dont_know
;
2749 if (op0
== TREE_OPERAND (chrec
, 0))
2752 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2755 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2756 and EVOLUTION_LOOP, that were left under a symbolic form.
2758 CHREC is the scalar evolution to instantiate.
2760 CACHE is the cache of already instantiated values.
2762 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2763 conversions that may wrap in signed/pointer type are folded, as long
2764 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2765 then we don't do such fold.
2767 SIZE_EXPR is used for computing the size of the expression to be
2768 instantiated, and to stop if it exceeds some limit. */
2771 instantiate_scev_r (basic_block instantiate_below
,
2772 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2774 bool *fold_conversions
, int size_expr
)
2776 /* Give up if the expression is larger than the MAX that we allow. */
2777 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2778 return chrec_dont_know
;
2780 if (chrec
== NULL_TREE
2781 || automatically_generated_chrec_p (chrec
)
2782 || is_gimple_min_invariant (chrec
))
2785 switch (TREE_CODE (chrec
))
2788 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2790 fold_conversions
, size_expr
);
2792 case POLYNOMIAL_CHREC
:
2793 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2795 fold_conversions
, size_expr
);
2797 case POINTER_PLUS_EXPR
:
2801 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2803 TREE_CODE (chrec
), chrec_type (chrec
),
2804 TREE_OPERAND (chrec
, 0),
2805 TREE_OPERAND (chrec
, 1),
2806 fold_conversions
, size_expr
);
2809 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2811 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2812 fold_conversions
, size_expr
);
2816 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2818 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2819 TREE_OPERAND (chrec
, 0),
2820 fold_conversions
, size_expr
);
2823 case SCEV_NOT_KNOWN
:
2824 return chrec_dont_know
;
2830 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2832 fold_conversions
, size_expr
);
2838 if (VL_EXP_CLASS_P (chrec
))
2839 return chrec_dont_know
;
2841 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2844 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2846 fold_conversions
, size_expr
);
2849 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2851 fold_conversions
, size_expr
);
2854 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2856 fold_conversions
, size_expr
);
2865 /* Too complicated to handle. */
2866 return chrec_dont_know
;
2869 /* Analyze all the parameters of the chrec that were left under a
2870 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2871 recursive instantiation of parameters: a parameter is a variable
2872 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2873 a function parameter. */
2876 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2881 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2883 fprintf (dump_file
, "(instantiate_scev \n");
2884 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2885 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2886 fprintf (dump_file
, " (chrec = ");
2887 print_generic_expr (dump_file
, chrec
, 0);
2888 fprintf (dump_file
, ")\n");
2894 global_cache
= new instantiate_cache_type
;
2898 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2899 NULL
, chrec
, NULL
, 0);
2903 delete global_cache
;
2904 global_cache
= NULL
;
2907 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2909 fprintf (dump_file
, " (res = ");
2910 print_generic_expr (dump_file
, res
, 0);
2911 fprintf (dump_file
, "))\n");
2917 /* Similar to instantiate_parameters, but does not introduce the
2918 evolutions in outer loops for LOOP invariants in CHREC, and does not
2919 care about causing overflows, as long as they do not affect value
2920 of an expression. */
2923 resolve_mixers (struct loop
*loop
, tree chrec
, bool *folded_casts
)
2926 bool fold_conversions
= false;
2929 global_cache
= new instantiate_cache_type
;
2933 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2934 chrec
, &fold_conversions
, 0);
2936 if (folded_casts
&& !*folded_casts
)
2937 *folded_casts
= fold_conversions
;
2941 delete global_cache
;
2942 global_cache
= NULL
;
2948 /* Entry point for the analysis of the number of iterations pass.
2949 This function tries to safely approximate the number of iterations
2950 the loop will run. When this property is not decidable at compile
2951 time, the result is chrec_dont_know. Otherwise the result is a
2952 scalar or a symbolic parameter. When the number of iterations may
2953 be equal to zero and the property cannot be determined at compile
2954 time, the result is a COND_EXPR that represents in a symbolic form
2955 the conditions under which the number of iterations is not zero.
2957 Example of analysis: suppose that the loop has an exit condition:
2959 "if (b > 49) goto end_loop;"
2961 and that in a previous analysis we have determined that the
2962 variable 'b' has an evolution function:
2964 "EF = {23, +, 5}_2".
2966 When we evaluate the function at the point 5, i.e. the value of the
2967 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2968 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2969 the loop body has been executed 6 times. */
2972 number_of_latch_executions (struct loop
*loop
)
2975 struct tree_niter_desc niter_desc
;
2979 /* Determine whether the number of iterations in loop has already
2981 res
= loop
->nb_iterations
;
2985 may_be_zero
= NULL_TREE
;
2987 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2988 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2990 res
= chrec_dont_know
;
2991 exit
= single_exit (loop
);
2993 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2995 may_be_zero
= niter_desc
.may_be_zero
;
2996 res
= niter_desc
.niter
;
2999 if (res
== chrec_dont_know
3001 || integer_zerop (may_be_zero
))
3003 else if (integer_nonzerop (may_be_zero
))
3004 res
= build_int_cst (TREE_TYPE (res
), 0);
3006 else if (COMPARISON_CLASS_P (may_be_zero
))
3007 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
3008 build_int_cst (TREE_TYPE (res
), 0), res
);
3010 res
= chrec_dont_know
;
3012 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3014 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
3015 print_generic_expr (dump_file
, res
, 0);
3016 fprintf (dump_file
, "))\n");
3019 loop
->nb_iterations
= res
;
3024 /* Counters for the stats. */
3030 unsigned nb_affine_multivar
;
3031 unsigned nb_higher_poly
;
3032 unsigned nb_chrec_dont_know
;
3033 unsigned nb_undetermined
;
3036 /* Reset the counters. */
3039 reset_chrecs_counters (struct chrec_stats
*stats
)
3041 stats
->nb_chrecs
= 0;
3042 stats
->nb_affine
= 0;
3043 stats
->nb_affine_multivar
= 0;
3044 stats
->nb_higher_poly
= 0;
3045 stats
->nb_chrec_dont_know
= 0;
3046 stats
->nb_undetermined
= 0;
3049 /* Dump the contents of a CHREC_STATS structure. */
3052 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
3054 fprintf (file
, "\n(\n");
3055 fprintf (file
, "-----------------------------------------\n");
3056 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
3057 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
3058 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
3059 stats
->nb_higher_poly
);
3060 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
3061 fprintf (file
, "-----------------------------------------\n");
3062 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
3063 fprintf (file
, "%d\twith undetermined coefficients\n",
3064 stats
->nb_undetermined
);
3065 fprintf (file
, "-----------------------------------------\n");
3066 fprintf (file
, "%d\tchrecs in the scev database\n",
3067 (int) scalar_evolution_info
->elements ());
3068 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
3069 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
3070 fprintf (file
, "-----------------------------------------\n");
3071 fprintf (file
, ")\n\n");
3074 /* Gather statistics about CHREC. */
3077 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
3079 if (dump_file
&& (dump_flags
& TDF_STATS
))
3081 fprintf (dump_file
, "(classify_chrec ");
3082 print_generic_expr (dump_file
, chrec
, 0);
3083 fprintf (dump_file
, "\n");
3088 if (chrec
== NULL_TREE
)
3090 stats
->nb_undetermined
++;
3094 switch (TREE_CODE (chrec
))
3096 case POLYNOMIAL_CHREC
:
3097 if (evolution_function_is_affine_p (chrec
))
3099 if (dump_file
&& (dump_flags
& TDF_STATS
))
3100 fprintf (dump_file
, " affine_univariate\n");
3103 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3105 if (dump_file
&& (dump_flags
& TDF_STATS
))
3106 fprintf (dump_file
, " affine_multivariate\n");
3107 stats
->nb_affine_multivar
++;
3111 if (dump_file
&& (dump_flags
& TDF_STATS
))
3112 fprintf (dump_file
, " higher_degree_polynomial\n");
3113 stats
->nb_higher_poly
++;
3122 if (chrec_contains_undetermined (chrec
))
3124 if (dump_file
&& (dump_flags
& TDF_STATS
))
3125 fprintf (dump_file
, " undetermined\n");
3126 stats
->nb_undetermined
++;
3129 if (dump_file
&& (dump_flags
& TDF_STATS
))
3130 fprintf (dump_file
, ")\n");
3133 /* Classify the chrecs of the whole database. */
3136 gather_stats_on_scev_database (void)
3138 struct chrec_stats stats
;
3143 reset_chrecs_counters (&stats
);
3145 hash_table
<scev_info_hasher
>::iterator iter
;
3147 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info
, elt
, scev_info_str
*,
3149 gather_chrec_stats (elt
->chrec
, &stats
);
3151 dump_chrecs_stats (dump_file
, &stats
);
3159 initialize_scalar_evolutions_analyzer (void)
3161 /* The elements below are unique. */
3162 if (chrec_dont_know
== NULL_TREE
)
3164 chrec_not_analyzed_yet
= NULL_TREE
;
3165 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3166 chrec_known
= make_node (SCEV_KNOWN
);
3167 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3168 TREE_TYPE (chrec_known
) = void_type_node
;
3172 /* Initialize the analysis of scalar evolutions for LOOPS. */
3175 scev_initialize (void)
3179 scalar_evolution_info
= hash_table
<scev_info_hasher
>::create_ggc (100);
3181 initialize_scalar_evolutions_analyzer ();
3183 FOR_EACH_LOOP (loop
, 0)
3185 loop
->nb_iterations
= NULL_TREE
;
3189 /* Return true if SCEV is initialized. */
3192 scev_initialized_p (void)
3194 return scalar_evolution_info
!= NULL
;
3197 /* Cleans up the information cached by the scalar evolutions analysis
3198 in the hash table. */
3201 scev_reset_htab (void)
3203 if (!scalar_evolution_info
)
3206 scalar_evolution_info
->empty ();
3209 /* Cleans up the information cached by the scalar evolutions analysis
3210 in the hash table and in the loop->nb_iterations. */
3219 FOR_EACH_LOOP (loop
, 0)
3221 loop
->nb_iterations
= NULL_TREE
;
3225 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3226 respect to WRTO_LOOP and returns its base and step in IV if possible
3227 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3228 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3229 invariant in LOOP. Otherwise we require it to be an integer constant.
3231 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3232 because it is computed in signed arithmetics). Consequently, adding an
3235 for (i = IV->base; ; i += IV->step)
3237 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3238 false for the type of the induction variable, or you can prove that i does
3239 not wrap by some other argument. Otherwise, this might introduce undefined
3242 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3244 must be used instead. */
3247 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3248 affine_iv
*iv
, bool allow_nonconstant_step
)
3250 enum tree_code code
;
3251 tree type
, ev
, base
, e
, stop
;
3253 bool folded_casts
, overflow
;
3255 iv
->base
= NULL_TREE
;
3256 iv
->step
= NULL_TREE
;
3257 iv
->no_overflow
= false;
3259 type
= TREE_TYPE (op
);
3260 if (!POINTER_TYPE_P (type
)
3261 && !INTEGRAL_TYPE_P (type
))
3264 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3266 if (chrec_contains_undetermined (ev
)
3267 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3270 if (tree_does_not_contain_chrecs (ev
))
3273 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3274 iv
->no_overflow
= true;
3278 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3279 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3282 iv
->step
= CHREC_RIGHT (ev
);
3283 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3284 || tree_contains_chrecs (iv
->step
, NULL
))
3287 iv
->base
= CHREC_LEFT (ev
);
3288 if (tree_contains_chrecs (iv
->base
, NULL
))
3291 iv
->no_overflow
= (!folded_casts
&& ANY_INTEGRAL_TYPE_P (type
)
3292 && TYPE_OVERFLOW_UNDEFINED (type
));
3294 /* Try to simplify iv base:
3296 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3297 == (signed T)(unsigned T)base + step
3300 If we can prove operation (base + step) doesn't overflow or underflow.
3301 Specifically, we try to prove below conditions are satisfied:
3303 base <= UPPER_BOUND (type) - step ;;step > 0
3304 base >= LOWER_BOUND (type) - step ;;step < 0
3306 This is done by proving the reverse conditions are false using loop's
3309 The is necessary to make loop niter, or iv overflow analysis easier
3312 int foo (int *a, signed char s, signed char l)
3315 for (i = s; i < l; i++)
3320 Note variable I is firstly converted to type unsigned char, incremented,
3321 then converted back to type signed char. */
3323 if (wrto_loop
->num
!= use_loop
->num
)
3326 if (!CONVERT_EXPR_P (iv
->base
) || TREE_CODE (iv
->step
) != INTEGER_CST
)
3329 type
= TREE_TYPE (iv
->base
);
3330 e
= TREE_OPERAND (iv
->base
, 0);
3331 if (TREE_CODE (e
) != PLUS_EXPR
3332 || TREE_CODE (TREE_OPERAND (e
, 1)) != INTEGER_CST
3333 || !tree_int_cst_equal (iv
->step
,
3334 fold_convert (type
, TREE_OPERAND (e
, 1))))
3336 e
= TREE_OPERAND (e
, 0);
3337 if (!CONVERT_EXPR_P (e
))
3339 base
= TREE_OPERAND (e
, 0);
3340 if (!useless_type_conversion_p (type
, TREE_TYPE (base
)))
3343 if (tree_int_cst_sign_bit (iv
->step
))
3346 extreme
= wi::min_value (type
);
3351 extreme
= wi::max_value (type
);
3354 extreme
= wi::sub (extreme
, iv
->step
, TYPE_SIGN (type
), &overflow
);
3357 e
= fold_build2 (code
, boolean_type_node
, base
,
3358 wide_int_to_tree (type
, extreme
));
3359 stop
= (TREE_CODE (base
) == SSA_NAME
) ? base
: NULL
;
3360 e
= simplify_using_initial_conditions (use_loop
, e
, stop
);
3361 if (!integer_zerop (e
))
3364 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3365 code
= POINTER_PLUS_EXPR
;
3369 iv
->base
= fold_build2 (code
, TREE_TYPE (base
), base
, iv
->step
);
3373 /* Finalize the scalar evolution analysis. */
3376 scev_finalize (void)
3378 if (!scalar_evolution_info
)
3380 scalar_evolution_info
->empty ();
3381 scalar_evolution_info
= NULL
;
3384 /* Returns true if the expression EXPR is considered to be too expensive
3385 for scev_const_prop. */
3388 expression_expensive_p (tree expr
)
3390 enum tree_code code
;
3392 if (is_gimple_val (expr
))
3395 code
= TREE_CODE (expr
);
3396 if (code
== TRUNC_DIV_EXPR
3397 || code
== CEIL_DIV_EXPR
3398 || code
== FLOOR_DIV_EXPR
3399 || code
== ROUND_DIV_EXPR
3400 || code
== TRUNC_MOD_EXPR
3401 || code
== CEIL_MOD_EXPR
3402 || code
== FLOOR_MOD_EXPR
3403 || code
== ROUND_MOD_EXPR
3404 || code
== EXACT_DIV_EXPR
)
3406 /* Division by power of two is usually cheap, so we allow it.
3407 Forbid anything else. */
3408 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3412 switch (TREE_CODE_CLASS (code
))
3415 case tcc_comparison
:
3416 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3421 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3428 /* Replace ssa names for that scev can prove they are constant by the
3429 appropriate constants. Also perform final value replacement in loops,
3430 in case the replacement expressions are cheap.
3432 We only consider SSA names defined by phi nodes; rest is left to the
3433 ordinary constant propagation pass. */
3436 scev_const_prop (void)
3439 tree name
, type
, ev
;
3442 struct loop
*loop
, *ex_loop
;
3443 bitmap ssa_names_to_remove
= NULL
;
3447 if (number_of_loops (cfun
) <= 1)
3450 FOR_EACH_BB_FN (bb
, cfun
)
3452 loop
= bb
->loop_father
;
3454 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3457 name
= PHI_RESULT (phi
);
3459 if (virtual_operand_p (name
))
3462 type
= TREE_TYPE (name
);
3464 if (!POINTER_TYPE_P (type
)
3465 && !INTEGRAL_TYPE_P (type
))
3468 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
),
3470 if (!is_gimple_min_invariant (ev
)
3471 || !may_propagate_copy (name
, ev
))
3474 /* Replace the uses of the name. */
3476 replace_uses_by (name
, ev
);
3478 if (!ssa_names_to_remove
)
3479 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3480 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3484 /* Remove the ssa names that were replaced by constants. We do not
3485 remove them directly in the previous cycle, since this
3486 invalidates scev cache. */
3487 if (ssa_names_to_remove
)
3491 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3493 gimple_stmt_iterator psi
;
3494 name
= ssa_name (i
);
3495 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (name
));
3497 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3498 psi
= gsi_for_stmt (phi
);
3499 remove_phi_node (&psi
, true);
3502 BITMAP_FREE (ssa_names_to_remove
);
3506 /* Now the regular final value replacement. */
3507 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3510 tree def
, rslt
, niter
;
3511 gimple_stmt_iterator gsi
;
3513 /* If we do not know exact number of iterations of the loop, we cannot
3514 replace the final value. */
3515 exit
= single_exit (loop
);
3519 niter
= number_of_latch_executions (loop
);
3520 if (niter
== chrec_dont_know
)
3523 /* Ensure that it is possible to insert new statements somewhere. */
3524 if (!single_pred_p (exit
->dest
))
3525 split_loop_exit_edge (exit
);
3526 gsi
= gsi_after_labels (exit
->dest
);
3528 ex_loop
= superloop_at_depth (loop
,
3529 loop_depth (exit
->dest
->loop_father
) + 1);
3531 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3534 rslt
= PHI_RESULT (phi
);
3535 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3536 if (virtual_operand_p (def
))
3542 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3543 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3550 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
,
3552 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3553 if (!tree_does_not_contain_chrecs (def
)
3554 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3555 /* Moving the computation from the loop may prolong life range
3556 of some ssa names, which may cause problems if they appear
3557 on abnormal edges. */
3558 || contains_abnormal_ssa_name_p (def
)
3559 /* Do not emit expensive expressions. The rationale is that
3560 when someone writes a code like
3562 while (n > 45) n -= 45;
3564 he probably knows that n is not large, and does not want it
3565 to be turned into n %= 45. */
3566 || expression_expensive_p (def
))
3568 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3570 fprintf (dump_file
, "not replacing:\n ");
3571 print_gimple_stmt (dump_file
, phi
, 0, 0);
3572 fprintf (dump_file
, "\n");
3578 /* Eliminate the PHI node and replace it by a computation outside
3582 fprintf (dump_file
, "\nfinal value replacement:\n ");
3583 print_gimple_stmt (dump_file
, phi
, 0, 0);
3584 fprintf (dump_file
, " with\n ");
3586 def
= unshare_expr (def
);
3587 remove_phi_node (&psi
, false);
3589 /* If def's type has undefined overflow and there were folded
3590 casts, rewrite all stmts added for def into arithmetics
3591 with defined overflow behavior. */
3592 if (folded_casts
&& ANY_INTEGRAL_TYPE_P (TREE_TYPE (def
))
3593 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def
)))
3596 gimple_stmt_iterator gsi2
;
3597 def
= force_gimple_operand (def
, &stmts
, true, NULL_TREE
);
3598 gsi2
= gsi_start (stmts
);
3599 while (!gsi_end_p (gsi2
))
3601 gimple
*stmt
= gsi_stmt (gsi2
);
3602 gimple_stmt_iterator gsi3
= gsi2
;
3604 gsi_remove (&gsi3
, false);
3605 if (is_gimple_assign (stmt
)
3606 && arith_code_with_undefined_signed_overflow
3607 (gimple_assign_rhs_code (stmt
)))
3608 gsi_insert_seq_before (&gsi
,
3609 rewrite_to_defined_overflow (stmt
),
3612 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3616 def
= force_gimple_operand_gsi (&gsi
, def
, false, NULL_TREE
,
3617 true, GSI_SAME_STMT
);
3619 ass
= gimple_build_assign (rslt
, def
);
3620 gsi_insert_before (&gsi
, ass
, GSI_SAME_STMT
);
3623 print_gimple_stmt (dump_file
, ass
, 0, 0);
3624 fprintf (dump_file
, "\n");
3631 #include "gt-tree-scalar-evolution.h"