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"
259 #include "hash-set.h"
260 #include "machmode.h"
262 #include "double-int.h"
267 #include "wide-int.h"
270 #include "fold-const.h"
273 #include "hard-reg-set.h"
274 #include "function.h"
277 #include "statistics.h"
279 #include "fixed-value.h"
280 #include "insn-config.h"
285 #include "emit-rtl.h"
289 #include "gimple-pretty-print.h"
291 #include "dominance.h"
293 #include "basic-block.h"
294 #include "tree-ssa-alias.h"
295 #include "internal-fn.h"
296 #include "gimple-expr.h"
299 #include "gimplify.h"
300 #include "gimple-iterator.h"
301 #include "gimplify-me.h"
302 #include "gimple-ssa.h"
303 #include "tree-cfg.h"
304 #include "tree-phinodes.h"
305 #include "stringpool.h"
306 #include "tree-ssanames.h"
307 #include "tree-ssa-loop-ivopts.h"
308 #include "tree-ssa-loop-manip.h"
309 #include "tree-ssa-loop-niter.h"
310 #include "tree-ssa-loop.h"
311 #include "tree-ssa.h"
313 #include "tree-chrec.h"
314 #include "tree-affine.h"
315 #include "tree-scalar-evolution.h"
316 #include "dumpfile.h"
318 #include "tree-ssa-propagate.h"
319 #include "gimple-fold.h"
321 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
322 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
325 /* The cached information about an SSA name with version NAME_VERSION,
326 claiming that below basic block with index INSTANTIATED_BELOW, the
327 value of the SSA name can be expressed as CHREC. */
329 struct GTY((for_user
)) scev_info_str
{
330 unsigned int name_version
;
331 int instantiated_below
;
335 /* Counters for the scev database. */
336 static unsigned nb_set_scev
= 0;
337 static unsigned nb_get_scev
= 0;
339 /* The following trees are unique elements. Thus the comparison of
340 another element to these elements should be done on the pointer to
341 these trees, and not on their value. */
343 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
344 tree chrec_not_analyzed_yet
;
346 /* Reserved to the cases where the analyzer has detected an
347 undecidable property at compile time. */
348 tree chrec_dont_know
;
350 /* When the analyzer has detected that a property will never
351 happen, then it qualifies it with chrec_known. */
354 struct scev_info_hasher
: ggc_hasher
<scev_info_str
*>
356 static hashval_t
hash (scev_info_str
*i
);
357 static bool equal (const scev_info_str
*a
, const scev_info_str
*b
);
360 static GTY (()) hash_table
<scev_info_hasher
> *scalar_evolution_info
;
363 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
365 static inline struct scev_info_str
*
366 new_scev_info_str (basic_block instantiated_below
, tree var
)
368 struct scev_info_str
*res
;
370 res
= ggc_alloc
<scev_info_str
> ();
371 res
->name_version
= SSA_NAME_VERSION (var
);
372 res
->chrec
= chrec_not_analyzed_yet
;
373 res
->instantiated_below
= instantiated_below
->index
;
378 /* Computes a hash function for database element ELT. */
381 scev_info_hasher::hash (scev_info_str
*elt
)
383 return elt
->name_version
^ elt
->instantiated_below
;
386 /* Compares database elements E1 and E2. */
389 scev_info_hasher::equal (const scev_info_str
*elt1
, const scev_info_str
*elt2
)
391 return (elt1
->name_version
== elt2
->name_version
392 && elt1
->instantiated_below
== elt2
->instantiated_below
);
395 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
396 A first query on VAR returns chrec_not_analyzed_yet. */
399 find_var_scev_info (basic_block instantiated_below
, tree var
)
401 struct scev_info_str
*res
;
402 struct scev_info_str tmp
;
404 tmp
.name_version
= SSA_NAME_VERSION (var
);
405 tmp
.instantiated_below
= instantiated_below
->index
;
406 scev_info_str
**slot
= scalar_evolution_info
->find_slot (&tmp
, INSERT
);
409 *slot
= new_scev_info_str (instantiated_below
, var
);
415 /* Return true when CHREC contains symbolic names defined in
419 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
423 if (chrec
== NULL_TREE
)
426 if (is_gimple_min_invariant (chrec
))
429 if (TREE_CODE (chrec
) == SSA_NAME
)
432 loop_p def_loop
, loop
;
434 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
437 def
= SSA_NAME_DEF_STMT (chrec
);
438 def_loop
= loop_containing_stmt (def
);
439 loop
= get_loop (cfun
, loop_nb
);
441 if (def_loop
== NULL
)
444 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
450 n
= TREE_OPERAND_LENGTH (chrec
);
451 for (i
= 0; i
< n
; i
++)
452 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
458 /* Return true when PHI is a loop-phi-node. */
461 loop_phi_node_p (gimple phi
)
463 /* The implementation of this function is based on the following
464 property: "all the loop-phi-nodes of a loop are contained in the
465 loop's header basic block". */
467 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
470 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
471 In general, in the case of multivariate evolutions we want to get
472 the evolution in different loops. LOOP specifies the level for
473 which to get the evolution.
477 | for (j = 0; j < 100; j++)
479 | for (k = 0; k < 100; k++)
481 | i = k + j; - Here the value of i is a function of j, k.
483 | ... = i - Here the value of i is a function of j.
485 | ... = i - Here the value of i is a scalar.
491 | i_1 = phi (i_0, i_2)
495 This loop has the same effect as:
496 LOOP_1 has the same effect as:
500 The overall effect of the loop, "i_0 + 20" in the previous example,
501 is obtained by passing in the parameters: LOOP = 1,
502 EVOLUTION_FN = {i_0, +, 2}_1.
506 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
510 if (evolution_fn
== chrec_dont_know
)
511 return chrec_dont_know
;
513 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
515 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
517 if (inner_loop
== loop
518 || flow_loop_nested_p (loop
, inner_loop
))
520 tree nb_iter
= number_of_latch_executions (inner_loop
);
522 if (nb_iter
== chrec_dont_know
)
523 return chrec_dont_know
;
528 /* evolution_fn is the evolution function in LOOP. Get
529 its value in the nb_iter-th iteration. */
530 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
532 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
533 res
= instantiate_parameters (loop
, res
);
535 /* Continue the computation until ending on a parent of LOOP. */
536 return compute_overall_effect_of_inner_loop (loop
, res
);
543 /* If the evolution function is an invariant, there is nothing to do. */
544 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
548 return chrec_dont_know
;
551 /* Associate CHREC to SCALAR. */
554 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
558 if (TREE_CODE (scalar
) != SSA_NAME
)
561 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
565 if (dump_flags
& TDF_SCEV
)
567 fprintf (dump_file
, "(set_scalar_evolution \n");
568 fprintf (dump_file
, " instantiated_below = %d \n",
569 instantiated_below
->index
);
570 fprintf (dump_file
, " (scalar = ");
571 print_generic_expr (dump_file
, scalar
, 0);
572 fprintf (dump_file
, ")\n (scalar_evolution = ");
573 print_generic_expr (dump_file
, chrec
, 0);
574 fprintf (dump_file
, "))\n");
576 if (dump_flags
& TDF_STATS
)
580 *scalar_info
= chrec
;
583 /* Retrieve the chrec associated to SCALAR instantiated below
584 INSTANTIATED_BELOW block. */
587 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
593 if (dump_flags
& TDF_SCEV
)
595 fprintf (dump_file
, "(get_scalar_evolution \n");
596 fprintf (dump_file
, " (scalar = ");
597 print_generic_expr (dump_file
, scalar
, 0);
598 fprintf (dump_file
, ")\n");
600 if (dump_flags
& TDF_STATS
)
604 switch (TREE_CODE (scalar
))
607 res
= *find_var_scev_info (instantiated_below
, scalar
);
617 res
= chrec_not_analyzed_yet
;
621 if (dump_file
&& (dump_flags
& TDF_SCEV
))
623 fprintf (dump_file
, " (scalar_evolution = ");
624 print_generic_expr (dump_file
, res
, 0);
625 fprintf (dump_file
, "))\n");
631 /* Helper function for add_to_evolution. Returns the evolution
632 function for an assignment of the form "a = b + c", where "a" and
633 "b" are on the strongly connected component. CHREC_BEFORE is the
634 information that we already have collected up to this point.
635 TO_ADD is the evolution of "c".
637 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
638 evolution the expression TO_ADD, otherwise construct an evolution
639 part for this loop. */
642 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
645 tree type
, left
, right
;
646 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
648 switch (TREE_CODE (chrec_before
))
650 case POLYNOMIAL_CHREC
:
651 chloop
= get_chrec_loop (chrec_before
);
653 || flow_loop_nested_p (chloop
, loop
))
657 type
= chrec_type (chrec_before
);
659 /* When there is no evolution part in this loop, build it. */
664 right
= SCALAR_FLOAT_TYPE_P (type
)
665 ? build_real (type
, dconst0
)
666 : build_int_cst (type
, 0);
670 var
= CHREC_VARIABLE (chrec_before
);
671 left
= CHREC_LEFT (chrec_before
);
672 right
= CHREC_RIGHT (chrec_before
);
675 to_add
= chrec_convert (type
, to_add
, at_stmt
);
676 right
= chrec_convert_rhs (type
, right
, at_stmt
);
677 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
678 return build_polynomial_chrec (var
, left
, right
);
682 gcc_assert (flow_loop_nested_p (loop
, chloop
));
684 /* Search the evolution in LOOP_NB. */
685 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
687 right
= CHREC_RIGHT (chrec_before
);
688 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
689 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
694 /* These nodes do not depend on a loop. */
695 if (chrec_before
== chrec_dont_know
)
696 return chrec_dont_know
;
699 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
700 return build_polynomial_chrec (loop_nb
, left
, right
);
704 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
707 Description (provided for completeness, for those who read code in
708 a plane, and for my poor 62 bytes brain that would have forgotten
709 all this in the next two or three months):
711 The algorithm of translation of programs from the SSA representation
712 into the chrecs syntax is based on a pattern matching. After having
713 reconstructed the overall tree expression for a loop, there are only
714 two cases that can arise:
716 1. a = loop-phi (init, a + expr)
717 2. a = loop-phi (init, expr)
719 where EXPR is either a scalar constant with respect to the analyzed
720 loop (this is a degree 0 polynomial), or an expression containing
721 other loop-phi definitions (these are higher degree polynomials).
728 | a = phi (init, a + 5)
735 | a = phi (inita, 2 * b + 3)
736 | b = phi (initb, b + 1)
739 For the first case, the semantics of the SSA representation is:
741 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
743 that is, there is a loop index "x" that determines the scalar value
744 of the variable during the loop execution. During the first
745 iteration, the value is that of the initial condition INIT, while
746 during the subsequent iterations, it is the sum of the initial
747 condition with the sum of all the values of EXPR from the initial
748 iteration to the before last considered iteration.
750 For the second case, the semantics of the SSA program is:
752 | a (x) = init, if x = 0;
753 | expr (x - 1), otherwise.
755 The second case corresponds to the PEELED_CHREC, whose syntax is
756 close to the syntax of a loop-phi-node:
758 | phi (init, expr) vs. (init, expr)_x
760 The proof of the translation algorithm for the first case is a
761 proof by structural induction based on the degree of EXPR.
764 When EXPR is a constant with respect to the analyzed loop, or in
765 other words when EXPR is a polynomial of degree 0, the evolution of
766 the variable A in the loop is an affine function with an initial
767 condition INIT, and a step EXPR. In order to show this, we start
768 from the semantics of the SSA representation:
770 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
772 and since "expr (j)" is a constant with respect to "j",
774 f (x) = init + x * expr
776 Finally, based on the semantics of the pure sum chrecs, by
777 identification we get the corresponding chrecs syntax:
779 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
780 f (x) -> {init, +, expr}_x
783 Suppose that EXPR is a polynomial of degree N with respect to the
784 analyzed loop_x for which we have already determined that it is
785 written under the chrecs syntax:
787 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
789 We start from the semantics of the SSA program:
791 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
793 | f (x) = init + \sum_{j = 0}^{x - 1}
794 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
796 | f (x) = init + \sum_{j = 0}^{x - 1}
797 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
799 | f (x) = init + \sum_{k = 0}^{n - 1}
800 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
802 | f (x) = init + \sum_{k = 0}^{n - 1}
803 | (b_k * \binom{x}{k + 1})
805 | f (x) = init + b_0 * \binom{x}{1} + ...
806 | + b_{n-1} * \binom{x}{n}
808 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
809 | + b_{n-1} * \binom{x}{n}
812 And finally from the definition of the chrecs syntax, we identify:
813 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
815 This shows the mechanism that stands behind the add_to_evolution
816 function. An important point is that the use of symbolic
817 parameters avoids the need of an analysis schedule.
824 | a = phi (inita, a + 2 + b)
825 | b = phi (initb, b + 1)
828 When analyzing "a", the algorithm keeps "b" symbolically:
830 | a -> {inita, +, 2 + b}_1
832 Then, after instantiation, the analyzer ends on the evolution:
834 | a -> {inita, +, 2 + initb, +, 1}_1
839 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
840 tree to_add
, gimple at_stmt
)
842 tree type
= chrec_type (to_add
);
843 tree res
= NULL_TREE
;
845 if (to_add
== NULL_TREE
)
848 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
849 instantiated at this point. */
850 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
851 /* This should not happen. */
852 return chrec_dont_know
;
854 if (dump_file
&& (dump_flags
& TDF_SCEV
))
856 fprintf (dump_file
, "(add_to_evolution \n");
857 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
858 fprintf (dump_file
, " (chrec_before = ");
859 print_generic_expr (dump_file
, chrec_before
, 0);
860 fprintf (dump_file
, ")\n (to_add = ");
861 print_generic_expr (dump_file
, to_add
, 0);
862 fprintf (dump_file
, ")\n");
865 if (code
== MINUS_EXPR
)
866 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
867 ? build_real (type
, dconstm1
)
868 : build_int_cst_type (type
, -1));
870 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
872 if (dump_file
&& (dump_flags
& TDF_SCEV
))
874 fprintf (dump_file
, " (res = ");
875 print_generic_expr (dump_file
, res
, 0);
876 fprintf (dump_file
, "))\n");
884 /* This section selects the loops that will be good candidates for the
885 scalar evolution analysis. For the moment, greedily select all the
886 loop nests we could analyze. */
888 /* For a loop with a single exit edge, return the COND_EXPR that
889 guards the exit edge. If the expression is too difficult to
890 analyze, then give up. */
893 get_loop_exit_condition (const struct loop
*loop
)
896 edge exit_edge
= single_exit (loop
);
898 if (dump_file
&& (dump_flags
& TDF_SCEV
))
899 fprintf (dump_file
, "(get_loop_exit_condition \n ");
905 stmt
= last_stmt (exit_edge
->src
);
906 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
910 if (dump_file
&& (dump_flags
& TDF_SCEV
))
912 print_gimple_stmt (dump_file
, res
, 0, 0);
913 fprintf (dump_file
, ")\n");
920 /* Depth first search algorithm. */
922 typedef enum t_bool
{
929 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gphi
*,
932 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
933 Return true if the strongly connected component has been found. */
936 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
937 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
938 gphi
*halting_phi
, tree
*evolution_of_loop
,
941 t_bool res
= t_false
;
946 case POINTER_PLUS_EXPR
:
948 if (TREE_CODE (rhs0
) == SSA_NAME
)
950 if (TREE_CODE (rhs1
) == SSA_NAME
)
952 /* Match an assignment under the form:
955 /* We want only assignments of form "name + name" contribute to
956 LIMIT, as the other cases do not necessarily contribute to
957 the complexity of the expression. */
960 evol
= *evolution_of_loop
;
961 res
= follow_ssa_edge
962 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
965 *evolution_of_loop
= add_to_evolution
967 chrec_convert (type
, evol
, at_stmt
),
968 code
, rhs1
, at_stmt
);
970 else if (res
== t_false
)
972 res
= follow_ssa_edge
973 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
974 evolution_of_loop
, limit
);
977 *evolution_of_loop
= add_to_evolution
979 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
980 code
, rhs0
, at_stmt
);
982 else if (res
== t_dont_know
)
983 *evolution_of_loop
= chrec_dont_know
;
986 else if (res
== t_dont_know
)
987 *evolution_of_loop
= chrec_dont_know
;
992 /* Match an assignment under the form:
994 res
= follow_ssa_edge
995 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
996 evolution_of_loop
, limit
);
998 *evolution_of_loop
= add_to_evolution
999 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1001 code
, rhs1
, at_stmt
);
1003 else if (res
== t_dont_know
)
1004 *evolution_of_loop
= chrec_dont_know
;
1008 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1010 /* Match an assignment under the form:
1012 res
= follow_ssa_edge
1013 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1014 evolution_of_loop
, limit
);
1016 *evolution_of_loop
= add_to_evolution
1017 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1019 code
, rhs0
, at_stmt
);
1021 else if (res
== t_dont_know
)
1022 *evolution_of_loop
= chrec_dont_know
;
1026 /* Otherwise, match an assignment under the form:
1028 /* And there is nothing to do. */
1033 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1034 if (TREE_CODE (rhs0
) == SSA_NAME
)
1036 /* Match an assignment under the form:
1039 /* We want only assignments of form "name - name" contribute to
1040 LIMIT, as the other cases do not necessarily contribute to
1041 the complexity of the expression. */
1042 if (TREE_CODE (rhs1
) == SSA_NAME
)
1045 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1046 evolution_of_loop
, limit
);
1048 *evolution_of_loop
= add_to_evolution
1049 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1050 MINUS_EXPR
, rhs1
, at_stmt
);
1052 else if (res
== t_dont_know
)
1053 *evolution_of_loop
= chrec_dont_know
;
1056 /* Otherwise, match an assignment under the form:
1058 /* And there is nothing to do. */
1069 /* Follow the ssa edge into the expression EXPR.
1070 Return true if the strongly connected component has been found. */
1073 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1074 gphi
*halting_phi
, tree
*evolution_of_loop
,
1077 enum tree_code code
= TREE_CODE (expr
);
1078 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1081 /* The EXPR is one of the following cases:
1085 - a POINTER_PLUS_EXPR,
1088 - other cases are not yet handled. */
1093 /* This assignment is under the form "a_1 = (cast) rhs. */
1094 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1095 halting_phi
, evolution_of_loop
, limit
);
1096 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1100 /* This assignment is under the form "a_1 = 7". */
1105 /* This assignment is under the form: "a_1 = b_2". */
1106 res
= follow_ssa_edge
1107 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1110 case POINTER_PLUS_EXPR
:
1113 /* This case is under the form "rhs0 +- rhs1". */
1114 rhs0
= TREE_OPERAND (expr
, 0);
1115 rhs1
= TREE_OPERAND (expr
, 1);
1116 type
= TREE_TYPE (rhs0
);
1117 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1118 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1119 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1120 halting_phi
, evolution_of_loop
, limit
);
1124 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1125 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1127 expr
= TREE_OPERAND (expr
, 0);
1128 rhs0
= TREE_OPERAND (expr
, 0);
1129 rhs1
= TREE_OPERAND (expr
, 1);
1130 type
= TREE_TYPE (rhs0
);
1131 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1132 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1133 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1134 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1135 halting_phi
, evolution_of_loop
, limit
);
1142 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1143 It must be handled as a copy assignment of the form a_1 = a_2. */
1144 rhs0
= ASSERT_EXPR_VAR (expr
);
1145 if (TREE_CODE (rhs0
) == SSA_NAME
)
1146 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1147 halting_phi
, evolution_of_loop
, limit
);
1160 /* Follow the ssa edge into the right hand side of an assignment STMT.
1161 Return true if the strongly connected component has been found. */
1164 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1165 gphi
*halting_phi
, tree
*evolution_of_loop
,
1168 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1169 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1175 /* This assignment is under the form "a_1 = (cast) rhs. */
1176 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1177 halting_phi
, evolution_of_loop
, limit
);
1178 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1181 case POINTER_PLUS_EXPR
:
1184 rhs1
= gimple_assign_rhs1 (stmt
);
1185 rhs2
= gimple_assign_rhs2 (stmt
);
1186 type
= TREE_TYPE (rhs1
);
1187 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1188 halting_phi
, evolution_of_loop
, limit
);
1192 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1193 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1194 halting_phi
, evolution_of_loop
, limit
);
1203 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1206 backedge_phi_arg_p (gphi
*phi
, int i
)
1208 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1210 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1211 about updating it anywhere, and this should work as well most of the
1213 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1219 /* Helper function for one branch of the condition-phi-node. Return
1220 true if the strongly connected component has been found following
1223 static inline t_bool
1224 follow_ssa_edge_in_condition_phi_branch (int i
,
1226 gphi
*condition_phi
,
1228 tree
*evolution_of_branch
,
1229 tree init_cond
, int limit
)
1231 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1232 *evolution_of_branch
= chrec_dont_know
;
1234 /* Do not follow back edges (they must belong to an irreducible loop, which
1235 we really do not want to worry about). */
1236 if (backedge_phi_arg_p (condition_phi
, i
))
1239 if (TREE_CODE (branch
) == SSA_NAME
)
1241 *evolution_of_branch
= init_cond
;
1242 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1243 evolution_of_branch
, limit
);
1246 /* This case occurs when one of the condition branches sets
1247 the variable to a constant: i.e. a phi-node like
1248 "a_2 = PHI <a_7(5), 2(6)>;".
1250 FIXME: This case have to be refined correctly:
1251 in some cases it is possible to say something better than
1252 chrec_dont_know, for example using a wrap-around notation. */
1256 /* This function merges the branches of a condition-phi-node in a
1260 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1261 gphi
*condition_phi
,
1263 tree
*evolution_of_loop
, int limit
)
1266 tree init
= *evolution_of_loop
;
1267 tree evolution_of_branch
;
1268 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1270 &evolution_of_branch
,
1272 if (res
== t_false
|| res
== t_dont_know
)
1275 *evolution_of_loop
= evolution_of_branch
;
1277 n
= gimple_phi_num_args (condition_phi
);
1278 for (i
= 1; i
< n
; i
++)
1280 /* Quickly give up when the evolution of one of the branches is
1282 if (*evolution_of_loop
== chrec_dont_know
)
1285 /* Increase the limit by the PHI argument number to avoid exponential
1286 time and memory complexity. */
1287 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1289 &evolution_of_branch
,
1291 if (res
== t_false
|| res
== t_dont_know
)
1294 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1295 evolution_of_branch
);
1301 /* Follow an SSA edge in an inner loop. It computes the overall
1302 effect of the loop, and following the symbolic initial conditions,
1303 it follows the edges in the parent loop. The inner loop is
1304 considered as a single statement. */
1307 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1308 gphi
*loop_phi_node
,
1310 tree
*evolution_of_loop
, int limit
)
1312 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1313 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1315 /* Sometimes, the inner loop is too difficult to analyze, and the
1316 result of the analysis is a symbolic parameter. */
1317 if (ev
== PHI_RESULT (loop_phi_node
))
1319 t_bool res
= t_false
;
1320 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1322 for (i
= 0; i
< n
; i
++)
1324 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1327 /* Follow the edges that exit the inner loop. */
1328 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1329 if (!flow_bb_inside_loop_p (loop
, bb
))
1330 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1332 evolution_of_loop
, limit
);
1337 /* If the path crosses this loop-phi, give up. */
1339 *evolution_of_loop
= chrec_dont_know
;
1344 /* Otherwise, compute the overall effect of the inner loop. */
1345 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1346 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1347 evolution_of_loop
, limit
);
1350 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1351 path that is analyzed on the return walk. */
1354 follow_ssa_edge (struct loop
*loop
, gimple def
, gphi
*halting_phi
,
1355 tree
*evolution_of_loop
, int limit
)
1357 struct loop
*def_loop
;
1359 if (gimple_nop_p (def
))
1362 /* Give up if the path is longer than the MAX that we allow. */
1363 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1366 def_loop
= loop_containing_stmt (def
);
1368 switch (gimple_code (def
))
1371 if (!loop_phi_node_p (def
))
1372 /* DEF is a condition-phi-node. Follow the branches, and
1373 record their evolutions. Finally, merge the collected
1374 information and set the approximation to the main
1376 return follow_ssa_edge_in_condition_phi
1377 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1380 /* When the analyzed phi is the halting_phi, the
1381 depth-first search is over: we have found a path from
1382 the halting_phi to itself in the loop. */
1383 if (def
== halting_phi
)
1386 /* Otherwise, the evolution of the HALTING_PHI depends
1387 on the evolution of another loop-phi-node, i.e. the
1388 evolution function is a higher degree polynomial. */
1389 if (def_loop
== loop
)
1393 if (flow_loop_nested_p (loop
, def_loop
))
1394 return follow_ssa_edge_inner_loop_phi
1395 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1402 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1403 evolution_of_loop
, limit
);
1406 /* At this level of abstraction, the program is just a set
1407 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1408 other node to be handled. */
1414 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1415 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1417 # i_17 = PHI <i_13(5), 0(3)>
1418 # _20 = PHI <_5(5), start_4(D)(3)>
1421 _5 = start_4(D) + i_13;
1423 Though variable _20 appears as a PEELED_CHREC in the form of
1424 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1429 simplify_peeled_chrec (struct loop
*loop
, tree arg
, tree init_cond
)
1431 aff_tree aff1
, aff2
;
1432 tree ev
, left
, right
, type
, step_val
;
1433 hash_map
<tree
, name_expansion
*> *peeled_chrec_map
= NULL
;
1435 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1436 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1437 return chrec_dont_know
;
1439 left
= CHREC_LEFT (ev
);
1440 right
= CHREC_RIGHT (ev
);
1441 type
= TREE_TYPE (left
);
1442 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1444 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1445 if "left" equals to "init + right". */
1446 if (operand_equal_p (left
, step_val
, 0))
1448 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1449 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1451 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1454 /* Try harder to check if they are equal. */
1455 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1456 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1457 free_affine_expand_cache (&peeled_chrec_map
);
1458 aff_combination_scale (&aff2
, -1);
1459 aff_combination_add (&aff1
, &aff2
);
1461 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1462 if "left" equals to "init + right". */
1463 if (aff_combination_zero_p (&aff1
))
1465 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1466 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1468 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1470 return chrec_dont_know
;
1473 /* Given a LOOP_PHI_NODE, this function determines the evolution
1474 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1477 analyze_evolution_in_loop (gphi
*loop_phi_node
,
1480 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1481 tree evolution_function
= chrec_not_analyzed_yet
;
1482 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1484 static bool simplify_peeled_chrec_p
= true;
1486 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1488 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1489 fprintf (dump_file
, " (loop_phi_node = ");
1490 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1491 fprintf (dump_file
, ")\n");
1494 for (i
= 0; i
< n
; i
++)
1496 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1501 /* Select the edges that enter the loop body. */
1502 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1503 if (!flow_bb_inside_loop_p (loop
, bb
))
1506 if (TREE_CODE (arg
) == SSA_NAME
)
1510 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1512 /* Pass in the initial condition to the follow edge function. */
1514 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1516 /* If ev_fn has no evolution in the inner loop, and the
1517 init_cond is not equal to ev_fn, then we have an
1518 ambiguity between two possible values, as we cannot know
1519 the number of iterations at this point. */
1520 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1521 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1522 && !operand_equal_p (init_cond
, ev_fn
, 0))
1523 ev_fn
= chrec_dont_know
;
1528 /* When it is impossible to go back on the same
1529 loop_phi_node by following the ssa edges, the
1530 evolution is represented by a peeled chrec, i.e. the
1531 first iteration, EV_FN has the value INIT_COND, then
1532 all the other iterations it has the value of ARG.
1533 For the moment, PEELED_CHREC nodes are not built. */
1536 ev_fn
= chrec_dont_know
;
1537 /* Try to recognize POLYNOMIAL_CHREC which appears in
1538 the form of PEELED_CHREC, but guard the process with
1539 a bool variable to keep the analyzer from infinite
1540 recurrence for real PEELED_RECs. */
1541 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1543 simplify_peeled_chrec_p
= false;
1544 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1545 simplify_peeled_chrec_p
= true;
1549 /* When there are multiple back edges of the loop (which in fact never
1550 happens currently, but nevertheless), merge their evolutions. */
1551 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1554 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1556 fprintf (dump_file
, " (evolution_function = ");
1557 print_generic_expr (dump_file
, evolution_function
, 0);
1558 fprintf (dump_file
, "))\n");
1561 return evolution_function
;
1564 /* Given a loop-phi-node, return the initial conditions of the
1565 variable on entry of the loop. When the CCP has propagated
1566 constants into the loop-phi-node, the initial condition is
1567 instantiated, otherwise the initial condition is kept symbolic.
1568 This analyzer does not analyze the evolution outside the current
1569 loop, and leaves this task to the on-demand tree reconstructor. */
1572 analyze_initial_condition (gphi
*loop_phi_node
)
1575 tree init_cond
= chrec_not_analyzed_yet
;
1576 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1578 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1580 fprintf (dump_file
, "(analyze_initial_condition \n");
1581 fprintf (dump_file
, " (loop_phi_node = \n");
1582 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1583 fprintf (dump_file
, ")\n");
1586 n
= gimple_phi_num_args (loop_phi_node
);
1587 for (i
= 0; i
< n
; i
++)
1589 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1590 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1592 /* When the branch is oriented to the loop's body, it does
1593 not contribute to the initial condition. */
1594 if (flow_bb_inside_loop_p (loop
, bb
))
1597 if (init_cond
== chrec_not_analyzed_yet
)
1603 if (TREE_CODE (branch
) == SSA_NAME
)
1605 init_cond
= chrec_dont_know
;
1609 init_cond
= chrec_merge (init_cond
, branch
);
1612 /* Ooops -- a loop without an entry??? */
1613 if (init_cond
== chrec_not_analyzed_yet
)
1614 init_cond
= chrec_dont_know
;
1616 /* During early loop unrolling we do not have fully constant propagated IL.
1617 Handle degenerate PHIs here to not miss important unrollings. */
1618 if (TREE_CODE (init_cond
) == SSA_NAME
)
1620 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1621 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
1623 tree res
= degenerate_phi_result (phi
);
1624 if (res
!= NULL_TREE
1625 /* Only allow invariants here, otherwise we may break
1626 loop-closed SSA form. */
1627 && is_gimple_min_invariant (res
))
1632 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1634 fprintf (dump_file
, " (init_cond = ");
1635 print_generic_expr (dump_file
, init_cond
, 0);
1636 fprintf (dump_file
, "))\n");
1642 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1645 interpret_loop_phi (struct loop
*loop
, gphi
*loop_phi_node
)
1648 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1651 if (phi_loop
!= loop
)
1653 struct loop
*subloop
;
1654 tree evolution_fn
= analyze_scalar_evolution
1655 (phi_loop
, PHI_RESULT (loop_phi_node
));
1657 /* Dive one level deeper. */
1658 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1660 /* Interpret the subloop. */
1661 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1665 /* Otherwise really interpret the loop phi. */
1666 init_cond
= analyze_initial_condition (loop_phi_node
);
1667 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1669 /* Verify we maintained the correct initial condition throughout
1670 possible conversions in the SSA chain. */
1671 if (res
!= chrec_dont_know
)
1673 tree new_init
= res
;
1674 if (CONVERT_EXPR_P (res
)
1675 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1676 new_init
= fold_convert (TREE_TYPE (res
),
1677 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1678 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1679 new_init
= CHREC_LEFT (res
);
1680 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1681 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1682 || !operand_equal_p (init_cond
, new_init
, 0))
1683 return chrec_dont_know
;
1689 /* This function merges the branches of a condition-phi-node,
1690 contained in the outermost loop, and whose arguments are already
1694 interpret_condition_phi (struct loop
*loop
, gphi
*condition_phi
)
1696 int i
, n
= gimple_phi_num_args (condition_phi
);
1697 tree res
= chrec_not_analyzed_yet
;
1699 for (i
= 0; i
< n
; i
++)
1703 if (backedge_phi_arg_p (condition_phi
, i
))
1705 res
= chrec_dont_know
;
1709 branch_chrec
= analyze_scalar_evolution
1710 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1712 res
= chrec_merge (res
, branch_chrec
);
1718 /* Interpret the operation RHS1 OP RHS2. If we didn't
1719 analyze this node before, follow the definitions until ending
1720 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1721 return path, this function propagates evolutions (ala constant copy
1722 propagation). OPND1 is not a GIMPLE expression because we could
1723 analyze the effect of an inner loop: see interpret_loop_phi. */
1726 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1727 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1729 tree res
, chrec1
, chrec2
;
1732 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1734 if (is_gimple_min_invariant (rhs1
))
1735 return chrec_convert (type
, rhs1
, at_stmt
);
1737 if (code
== SSA_NAME
)
1738 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1741 if (code
== ASSERT_EXPR
)
1743 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1744 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1752 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1753 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1756 HOST_WIDE_INT bitsize
, bitpos
;
1763 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1764 &bitsize
, &bitpos
, &offset
,
1765 &mode
, &unsignedp
, &volatilep
, false);
1767 if (TREE_CODE (base
) == MEM_REF
)
1769 rhs2
= TREE_OPERAND (base
, 1);
1770 rhs1
= TREE_OPERAND (base
, 0);
1772 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1773 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1774 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1775 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1776 chrec1
= instantiate_parameters (loop
, chrec1
);
1777 chrec2
= instantiate_parameters (loop
, chrec2
);
1778 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1782 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1783 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1787 if (offset
!= NULL_TREE
)
1789 chrec2
= analyze_scalar_evolution (loop
, offset
);
1790 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1791 chrec2
= instantiate_parameters (loop
, chrec2
);
1792 res
= chrec_fold_plus (type
, res
, chrec2
);
1797 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1799 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1800 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1801 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1802 chrec3
= instantiate_parameters (loop
, chrec3
);
1803 res
= chrec_fold_plus (type
, res
, chrec3
);
1807 res
= chrec_dont_know
;
1810 case POINTER_PLUS_EXPR
:
1811 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1812 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1813 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1814 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1815 chrec1
= instantiate_parameters (loop
, chrec1
);
1816 chrec2
= instantiate_parameters (loop
, chrec2
);
1817 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1821 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1822 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1823 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1824 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1825 chrec1
= instantiate_parameters (loop
, chrec1
);
1826 chrec2
= instantiate_parameters (loop
, chrec2
);
1827 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1831 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1832 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1833 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1834 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1835 chrec1
= instantiate_parameters (loop
, chrec1
);
1836 chrec2
= instantiate_parameters (loop
, chrec2
);
1837 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1841 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1842 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1843 /* TYPE may be integer, real or complex, so use fold_convert. */
1844 chrec1
= instantiate_parameters (loop
, chrec1
);
1845 res
= chrec_fold_multiply (type
, chrec1
,
1846 fold_convert (type
, integer_minus_one_node
));
1850 /* Handle ~X as -1 - X. */
1851 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1852 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1853 chrec1
= instantiate_parameters (loop
, chrec1
);
1854 res
= chrec_fold_minus (type
,
1855 fold_convert (type
, integer_minus_one_node
),
1860 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1861 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1862 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1863 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1864 chrec1
= instantiate_parameters (loop
, chrec1
);
1865 chrec2
= instantiate_parameters (loop
, chrec2
);
1866 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1870 /* In case we have a truncation of a widened operation that in
1871 the truncated type has undefined overflow behavior analyze
1872 the operation done in an unsigned type of the same precision
1873 as the final truncation. We cannot derive a scalar evolution
1874 for the widened operation but for the truncated result. */
1875 if (TREE_CODE (type
) == INTEGER_TYPE
1876 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1877 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1878 && TYPE_OVERFLOW_UNDEFINED (type
)
1879 && TREE_CODE (rhs1
) == SSA_NAME
1880 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1881 && is_gimple_assign (def
)
1882 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1883 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1885 tree utype
= unsigned_type_for (type
);
1886 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1887 gimple_assign_rhs1 (def
),
1888 gimple_assign_rhs_code (def
),
1889 gimple_assign_rhs2 (def
));
1892 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1893 res
= chrec_convert (type
, chrec1
, at_stmt
);
1897 res
= chrec_dont_know
;
1904 /* Interpret the expression EXPR. */
1907 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1909 enum tree_code code
;
1910 tree type
= TREE_TYPE (expr
), op0
, op1
;
1912 if (automatically_generated_chrec_p (expr
))
1915 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1916 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1917 return chrec_dont_know
;
1919 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1921 return interpret_rhs_expr (loop
, at_stmt
, type
,
1925 /* Interpret the rhs of the assignment STMT. */
1928 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1930 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1931 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1933 return interpret_rhs_expr (loop
, stmt
, type
,
1934 gimple_assign_rhs1 (stmt
), code
,
1935 gimple_assign_rhs2 (stmt
));
1940 /* This section contains all the entry points:
1941 - number_of_iterations_in_loop,
1942 - analyze_scalar_evolution,
1943 - instantiate_parameters.
1946 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1947 common ancestor of DEF_LOOP and USE_LOOP. */
1950 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1951 struct loop
*def_loop
,
1957 if (def_loop
== wrto_loop
)
1960 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1961 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1963 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1966 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1969 /* Helper recursive function. */
1972 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1974 tree type
= TREE_TYPE (var
);
1977 struct loop
*def_loop
;
1979 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1980 return chrec_dont_know
;
1982 if (TREE_CODE (var
) != SSA_NAME
)
1983 return interpret_expr (loop
, NULL
, var
);
1985 def
= SSA_NAME_DEF_STMT (var
);
1986 bb
= gimple_bb (def
);
1987 def_loop
= bb
? bb
->loop_father
: NULL
;
1990 || !flow_bb_inside_loop_p (loop
, bb
))
1992 /* Keep the symbolic form. */
1997 if (res
!= chrec_not_analyzed_yet
)
1999 if (loop
!= bb
->loop_father
)
2000 res
= compute_scalar_evolution_in_loop
2001 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
2006 if (loop
!= def_loop
)
2008 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
2009 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
2014 switch (gimple_code (def
))
2017 res
= interpret_gimple_assign (loop
, def
);
2021 if (loop_phi_node_p (def
))
2022 res
= interpret_loop_phi (loop
, as_a
<gphi
*> (def
));
2024 res
= interpret_condition_phi (loop
, as_a
<gphi
*> (def
));
2028 res
= chrec_dont_know
;
2034 /* Keep the symbolic form. */
2035 if (res
== chrec_dont_know
)
2038 if (loop
== def_loop
)
2039 set_scalar_evolution (block_before_loop (loop
), var
, res
);
2044 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2045 LOOP. LOOP is the loop in which the variable is used.
2047 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2048 pointer to the statement that uses this variable, in order to
2049 determine the evolution function of the variable, use the following
2052 loop_p loop = loop_containing_stmt (stmt);
2053 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2054 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2058 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2062 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2064 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2065 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2066 fprintf (dump_file
, " (scalar = ");
2067 print_generic_expr (dump_file
, var
, 0);
2068 fprintf (dump_file
, ")\n");
2071 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2072 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
2074 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2075 fprintf (dump_file
, ")\n");
2080 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2083 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
2085 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2088 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2089 WRTO_LOOP (which should be a superloop of USE_LOOP)
2091 FOLDED_CASTS is set to true if resolve_mixers used
2092 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2093 at the moment in order to keep things simple).
2095 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2098 for (i = 0; i < 100; i++) -- loop 1
2100 for (j = 0; j < 100; j++) -- loop 2
2107 for (t = 0; t < 100; t++) -- loop 3
2114 Both k1 and k2 are invariants in loop3, thus
2115 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2116 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2118 As they are invariant, it does not matter whether we consider their
2119 usage in loop 3 or loop 2, hence
2120 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2121 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2122 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2123 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2125 Similarly for their evolutions with respect to loop 1. The values of K2
2126 in the use in loop 2 vary independently on loop 1, thus we cannot express
2127 the evolution with respect to loop 1:
2128 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2129 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2130 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2131 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2133 The value of k2 in the use in loop 1 is known, though:
2134 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2135 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2139 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2140 tree version
, bool *folded_casts
)
2143 tree ev
= version
, tmp
;
2145 /* We cannot just do
2147 tmp = analyze_scalar_evolution (use_loop, version);
2148 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2150 as resolve_mixers would query the scalar evolution with respect to
2151 wrto_loop. For example, in the situation described in the function
2152 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2155 analyze_scalar_evolution (use_loop, version) = k2
2157 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2158 k2 in loop 1 is 100, which is a wrong result, since we are interested
2159 in the value in loop 3.
2161 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2162 each time checking that there is no evolution in the inner loop. */
2165 *folded_casts
= false;
2168 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2169 ev
= resolve_mixers (use_loop
, tmp
, folded_casts
);
2171 if (use_loop
== wrto_loop
)
2174 /* If the value of the use changes in the inner loop, we cannot express
2175 its value in the outer loop (we might try to return interval chrec,
2176 but we do not have a user for it anyway) */
2177 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2179 return chrec_dont_know
;
2181 use_loop
= loop_outer (use_loop
);
2186 /* Hashtable helpers for a temporary hash-table used when
2187 instantiating a CHREC or resolving mixers. For this use
2188 instantiated_below is always the same. */
2190 struct instantiate_cache_type
2193 vec
<scev_info_str
> entries
;
2195 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2196 ~instantiate_cache_type ();
2197 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2198 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2201 instantiate_cache_type::~instantiate_cache_type ()
2210 /* Cache to avoid infinite recursion when instantiating an SSA name.
2211 Live during the outermost instantiate_scev or resolve_mixers call. */
2212 static instantiate_cache_type
*global_cache
;
2214 /* Computes a hash function for database element ELT. */
2216 static inline hashval_t
2217 hash_idx_scev_info (const void *elt_
)
2219 unsigned idx
= ((size_t) elt_
) - 2;
2220 return scev_info_hasher::hash (&global_cache
->entries
[idx
]);
2223 /* Compares database elements E1 and E2. */
2226 eq_idx_scev_info (const void *e1
, const void *e2
)
2228 unsigned idx1
= ((size_t) e1
) - 2;
2229 return scev_info_hasher::equal (&global_cache
->entries
[idx1
],
2230 (const scev_info_str
*) e2
);
2233 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2236 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2237 tree name
, basic_block instantiate_below
)
2241 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2242 cache
.entries
.create (10);
2246 e
.name_version
= SSA_NAME_VERSION (name
);
2247 e
.instantiated_below
= instantiate_below
->index
;
2248 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2249 scev_info_hasher::hash (&e
), INSERT
);
2252 e
.chrec
= chrec_not_analyzed_yet
;
2253 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2254 cache
.entries
.safe_push (e
);
2257 return ((size_t)*slot
) - 2;
2261 /* Return the closed_loop_phi node for VAR. If there is none, return
2265 loop_closed_phi_def (tree var
)
2272 if (var
== NULL_TREE
2273 || TREE_CODE (var
) != SSA_NAME
)
2276 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2277 exit
= single_exit (loop
);
2281 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2284 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2285 return PHI_RESULT (phi
);
2291 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2294 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2295 and EVOLUTION_LOOP, that were left under a symbolic form.
2297 CHREC is an SSA_NAME to be instantiated.
2299 CACHE is the cache of already instantiated values.
2301 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2302 conversions that may wrap in signed/pointer type are folded, as long
2303 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2304 then we don't do such fold.
2306 SIZE_EXPR is used for computing the size of the expression to be
2307 instantiated, and to stop if it exceeds some limit. */
2310 instantiate_scev_name (basic_block instantiate_below
,
2311 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2313 bool *fold_conversions
,
2317 struct loop
*def_loop
;
2318 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2320 /* A parameter (or loop invariant and we do not want to include
2321 evolutions in outer loops), nothing to do. */
2323 || loop_depth (def_bb
->loop_father
) == 0
2324 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2327 /* We cache the value of instantiated variable to avoid exponential
2328 time complexity due to reevaluations. We also store the convenient
2329 value in the cache in order to prevent infinite recursion -- we do
2330 not want to instantiate the SSA_NAME if it is in a mixer
2331 structure. This is used for avoiding the instantiation of
2332 recursively defined functions, such as:
2334 | a_2 -> {0, +, 1, +, a_2}_1 */
2336 unsigned si
= get_instantiated_value_entry (*global_cache
,
2337 chrec
, instantiate_below
);
2338 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2339 return global_cache
->get (si
);
2341 /* On recursion return chrec_dont_know. */
2342 global_cache
->set (si
, chrec_dont_know
);
2344 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2346 /* If the analysis yields a parametric chrec, instantiate the
2348 res
= analyze_scalar_evolution (def_loop
, chrec
);
2350 /* Don't instantiate default definitions. */
2351 if (TREE_CODE (res
) == SSA_NAME
2352 && SSA_NAME_IS_DEFAULT_DEF (res
))
2355 /* Don't instantiate loop-closed-ssa phi nodes. */
2356 else if (TREE_CODE (res
) == SSA_NAME
2357 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2358 > loop_depth (def_loop
))
2361 res
= loop_closed_phi_def (chrec
);
2365 /* When there is no loop_closed_phi_def, it means that the
2366 variable is not used after the loop: try to still compute the
2367 value of the variable when exiting the loop. */
2368 if (res
== NULL_TREE
)
2370 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2371 res
= analyze_scalar_evolution (loop
, chrec
);
2372 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2373 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2375 fold_conversions
, size_expr
);
2377 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2378 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2379 res
= chrec_dont_know
;
2382 else if (res
!= chrec_dont_know
)
2385 && def_bb
->loop_father
!= inner_loop
2386 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2387 /* ??? We could try to compute the overall effect of the loop here. */
2388 res
= chrec_dont_know
;
2390 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2392 fold_conversions
, size_expr
);
2395 /* Store the correct value to the cache. */
2396 global_cache
->set (si
, res
);
2400 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2401 and EVOLUTION_LOOP, that were left under a symbolic form.
2403 CHREC is a polynomial chain of recurrence to be instantiated.
2405 CACHE is the cache of already instantiated values.
2407 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2408 conversions that may wrap in signed/pointer type are folded, as long
2409 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2410 then we don't do such fold.
2412 SIZE_EXPR is used for computing the size of the expression to be
2413 instantiated, and to stop if it exceeds some limit. */
2416 instantiate_scev_poly (basic_block instantiate_below
,
2417 struct loop
*evolution_loop
, struct loop
*,
2418 tree chrec
, bool *fold_conversions
, int size_expr
)
2421 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2422 get_chrec_loop (chrec
),
2423 CHREC_LEFT (chrec
), fold_conversions
,
2425 if (op0
== chrec_dont_know
)
2426 return chrec_dont_know
;
2428 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2429 get_chrec_loop (chrec
),
2430 CHREC_RIGHT (chrec
), fold_conversions
,
2432 if (op1
== chrec_dont_know
)
2433 return chrec_dont_know
;
2435 if (CHREC_LEFT (chrec
) != op0
2436 || CHREC_RIGHT (chrec
) != op1
)
2438 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2439 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2445 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2446 and EVOLUTION_LOOP, that were left under a symbolic form.
2448 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2450 CACHE is the cache of already instantiated values.
2452 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2453 conversions that may wrap in signed/pointer type are folded, as long
2454 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2455 then we don't do such fold.
2457 SIZE_EXPR is used for computing the size of the expression to be
2458 instantiated, and to stop if it exceeds some limit. */
2461 instantiate_scev_binary (basic_block instantiate_below
,
2462 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2463 tree chrec
, enum tree_code code
,
2464 tree type
, tree c0
, tree c1
,
2465 bool *fold_conversions
, int size_expr
)
2468 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2469 c0
, fold_conversions
, size_expr
);
2470 if (op0
== chrec_dont_know
)
2471 return chrec_dont_know
;
2473 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2474 c1
, fold_conversions
, size_expr
);
2475 if (op1
== chrec_dont_know
)
2476 return chrec_dont_know
;
2481 op0
= chrec_convert (type
, op0
, NULL
);
2482 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2486 case POINTER_PLUS_EXPR
:
2488 return chrec_fold_plus (type
, op0
, op1
);
2491 return chrec_fold_minus (type
, op0
, op1
);
2494 return chrec_fold_multiply (type
, op0
, op1
);
2501 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2504 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2505 and EVOLUTION_LOOP, that were left under a symbolic form.
2507 "CHREC" is an array reference to be instantiated.
2509 CACHE is the cache of already instantiated values.
2511 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2512 conversions that may wrap in signed/pointer type are folded, as long
2513 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2514 then we don't do such fold.
2516 SIZE_EXPR is used for computing the size of the expression to be
2517 instantiated, and to stop if it exceeds some limit. */
2520 instantiate_array_ref (basic_block instantiate_below
,
2521 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2522 tree chrec
, bool *fold_conversions
, int size_expr
)
2525 tree index
= TREE_OPERAND (chrec
, 1);
2526 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2528 fold_conversions
, size_expr
);
2530 if (op1
== chrec_dont_know
)
2531 return chrec_dont_know
;
2533 if (chrec
&& op1
== index
)
2536 res
= unshare_expr (chrec
);
2537 TREE_OPERAND (res
, 1) = op1
;
2541 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2542 and EVOLUTION_LOOP, that were left under a symbolic form.
2544 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2547 CACHE is the cache of already instantiated values.
2549 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2550 conversions that may wrap in signed/pointer type are folded, as long
2551 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2552 then we don't do such fold.
2554 SIZE_EXPR is used for computing the size of the expression to be
2555 instantiated, and to stop if it exceeds some limit. */
2558 instantiate_scev_convert (basic_block instantiate_below
,
2559 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2560 tree chrec
, tree type
, tree op
,
2561 bool *fold_conversions
, int size_expr
)
2563 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2565 fold_conversions
, size_expr
);
2567 if (op0
== chrec_dont_know
)
2568 return chrec_dont_know
;
2570 if (fold_conversions
)
2572 tree tmp
= chrec_convert_aggressive (type
, op0
, fold_conversions
);
2576 /* If we used chrec_convert_aggressive, we can no longer assume that
2577 signed chrecs do not overflow, as chrec_convert does, so avoid
2578 calling it in that case. */
2579 if (*fold_conversions
)
2581 if (chrec
&& op0
== op
)
2584 return fold_convert (type
, op0
);
2588 return chrec_convert (type
, op0
, NULL
);
2591 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2592 and EVOLUTION_LOOP, that were left under a symbolic form.
2594 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2595 Handle ~X as -1 - X.
2596 Handle -X as -1 * X.
2598 CACHE is the cache of already instantiated values.
2600 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2601 conversions that may wrap in signed/pointer type are folded, as long
2602 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2603 then we don't do such fold.
2605 SIZE_EXPR is used for computing the size of the expression to be
2606 instantiated, and to stop if it exceeds some limit. */
2609 instantiate_scev_not (basic_block instantiate_below
,
2610 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2612 enum tree_code code
, tree type
, tree op
,
2613 bool *fold_conversions
, int size_expr
)
2615 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2617 fold_conversions
, size_expr
);
2619 if (op0
== chrec_dont_know
)
2620 return chrec_dont_know
;
2624 op0
= chrec_convert (type
, op0
, NULL
);
2629 return chrec_fold_minus
2630 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2633 return chrec_fold_multiply
2634 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2641 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2644 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2645 and EVOLUTION_LOOP, that were left under a symbolic form.
2647 CHREC is an expression with 3 operands to be instantiated.
2649 CACHE is the cache of already instantiated values.
2651 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2652 conversions that may wrap in signed/pointer type are folded, as long
2653 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2654 then we don't do such fold.
2656 SIZE_EXPR is used for computing the size of the expression to be
2657 instantiated, and to stop if it exceeds some limit. */
2660 instantiate_scev_3 (basic_block instantiate_below
,
2661 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2663 bool *fold_conversions
, int size_expr
)
2666 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2667 inner_loop
, TREE_OPERAND (chrec
, 0),
2668 fold_conversions
, size_expr
);
2669 if (op0
== chrec_dont_know
)
2670 return chrec_dont_know
;
2672 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2673 inner_loop
, TREE_OPERAND (chrec
, 1),
2674 fold_conversions
, size_expr
);
2675 if (op1
== chrec_dont_know
)
2676 return chrec_dont_know
;
2678 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2679 inner_loop
, TREE_OPERAND (chrec
, 2),
2680 fold_conversions
, size_expr
);
2681 if (op2
== chrec_dont_know
)
2682 return chrec_dont_know
;
2684 if (op0
== TREE_OPERAND (chrec
, 0)
2685 && op1
== TREE_OPERAND (chrec
, 1)
2686 && op2
== TREE_OPERAND (chrec
, 2))
2689 return fold_build3 (TREE_CODE (chrec
),
2690 TREE_TYPE (chrec
), op0
, op1
, op2
);
2693 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2694 and EVOLUTION_LOOP, that were left under a symbolic form.
2696 CHREC is an expression with 2 operands to be instantiated.
2698 CACHE is the cache of already instantiated values.
2700 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2701 conversions that may wrap in signed/pointer type are folded, as long
2702 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2703 then we don't do such fold.
2705 SIZE_EXPR is used for computing the size of the expression to be
2706 instantiated, and to stop if it exceeds some limit. */
2709 instantiate_scev_2 (basic_block instantiate_below
,
2710 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2712 bool *fold_conversions
, int size_expr
)
2715 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2716 inner_loop
, TREE_OPERAND (chrec
, 0),
2717 fold_conversions
, size_expr
);
2718 if (op0
== chrec_dont_know
)
2719 return chrec_dont_know
;
2721 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2722 inner_loop
, TREE_OPERAND (chrec
, 1),
2723 fold_conversions
, size_expr
);
2724 if (op1
== chrec_dont_know
)
2725 return chrec_dont_know
;
2727 if (op0
== TREE_OPERAND (chrec
, 0)
2728 && op1
== TREE_OPERAND (chrec
, 1))
2731 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2734 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2735 and EVOLUTION_LOOP, that were left under a symbolic form.
2737 CHREC is an expression with 2 operands to be instantiated.
2739 CACHE is the cache of already instantiated values.
2741 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2742 conversions that may wrap in signed/pointer type are folded, as long
2743 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2744 then we don't do such fold.
2746 SIZE_EXPR is used for computing the size of the expression to be
2747 instantiated, and to stop if it exceeds some limit. */
2750 instantiate_scev_1 (basic_block instantiate_below
,
2751 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2753 bool *fold_conversions
, int size_expr
)
2755 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2756 inner_loop
, TREE_OPERAND (chrec
, 0),
2757 fold_conversions
, size_expr
);
2759 if (op0
== chrec_dont_know
)
2760 return chrec_dont_know
;
2762 if (op0
== TREE_OPERAND (chrec
, 0))
2765 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2768 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2769 and EVOLUTION_LOOP, that were left under a symbolic form.
2771 CHREC is the scalar evolution to instantiate.
2773 CACHE is the cache of already instantiated values.
2775 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2776 conversions that may wrap in signed/pointer type are folded, as long
2777 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2778 then we don't do such fold.
2780 SIZE_EXPR is used for computing the size of the expression to be
2781 instantiated, and to stop if it exceeds some limit. */
2784 instantiate_scev_r (basic_block instantiate_below
,
2785 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2787 bool *fold_conversions
, int size_expr
)
2789 /* Give up if the expression is larger than the MAX that we allow. */
2790 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2791 return chrec_dont_know
;
2793 if (chrec
== NULL_TREE
2794 || automatically_generated_chrec_p (chrec
)
2795 || is_gimple_min_invariant (chrec
))
2798 switch (TREE_CODE (chrec
))
2801 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2803 fold_conversions
, size_expr
);
2805 case POLYNOMIAL_CHREC
:
2806 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2808 fold_conversions
, size_expr
);
2810 case POINTER_PLUS_EXPR
:
2814 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2816 TREE_CODE (chrec
), chrec_type (chrec
),
2817 TREE_OPERAND (chrec
, 0),
2818 TREE_OPERAND (chrec
, 1),
2819 fold_conversions
, size_expr
);
2822 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2824 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2825 fold_conversions
, size_expr
);
2829 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2831 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2832 TREE_OPERAND (chrec
, 0),
2833 fold_conversions
, size_expr
);
2836 case SCEV_NOT_KNOWN
:
2837 return chrec_dont_know
;
2843 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2845 fold_conversions
, size_expr
);
2851 if (VL_EXP_CLASS_P (chrec
))
2852 return chrec_dont_know
;
2854 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2857 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2859 fold_conversions
, size_expr
);
2862 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2864 fold_conversions
, size_expr
);
2867 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2869 fold_conversions
, size_expr
);
2878 /* Too complicated to handle. */
2879 return chrec_dont_know
;
2882 /* Analyze all the parameters of the chrec that were left under a
2883 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2884 recursive instantiation of parameters: a parameter is a variable
2885 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2886 a function parameter. */
2889 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2894 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2896 fprintf (dump_file
, "(instantiate_scev \n");
2897 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2898 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2899 fprintf (dump_file
, " (chrec = ");
2900 print_generic_expr (dump_file
, chrec
, 0);
2901 fprintf (dump_file
, ")\n");
2907 global_cache
= new instantiate_cache_type
;
2911 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2912 NULL
, chrec
, NULL
, 0);
2916 delete global_cache
;
2917 global_cache
= NULL
;
2920 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2922 fprintf (dump_file
, " (res = ");
2923 print_generic_expr (dump_file
, res
, 0);
2924 fprintf (dump_file
, "))\n");
2930 /* Similar to instantiate_parameters, but does not introduce the
2931 evolutions in outer loops for LOOP invariants in CHREC, and does not
2932 care about causing overflows, as long as they do not affect value
2933 of an expression. */
2936 resolve_mixers (struct loop
*loop
, tree chrec
, bool *folded_casts
)
2939 bool fold_conversions
= false;
2942 global_cache
= new instantiate_cache_type
;
2946 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2947 chrec
, &fold_conversions
, 0);
2949 if (folded_casts
&& !*folded_casts
)
2950 *folded_casts
= fold_conversions
;
2954 delete global_cache
;
2955 global_cache
= NULL
;
2961 /* Entry point for the analysis of the number of iterations pass.
2962 This function tries to safely approximate the number of iterations
2963 the loop will run. When this property is not decidable at compile
2964 time, the result is chrec_dont_know. Otherwise the result is a
2965 scalar or a symbolic parameter. When the number of iterations may
2966 be equal to zero and the property cannot be determined at compile
2967 time, the result is a COND_EXPR that represents in a symbolic form
2968 the conditions under which the number of iterations is not zero.
2970 Example of analysis: suppose that the loop has an exit condition:
2972 "if (b > 49) goto end_loop;"
2974 and that in a previous analysis we have determined that the
2975 variable 'b' has an evolution function:
2977 "EF = {23, +, 5}_2".
2979 When we evaluate the function at the point 5, i.e. the value of the
2980 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2981 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2982 the loop body has been executed 6 times. */
2985 number_of_latch_executions (struct loop
*loop
)
2988 struct tree_niter_desc niter_desc
;
2992 /* Determine whether the number of iterations in loop has already
2994 res
= loop
->nb_iterations
;
2998 may_be_zero
= NULL_TREE
;
3000 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3001 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
3003 res
= chrec_dont_know
;
3004 exit
= single_exit (loop
);
3006 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
3008 may_be_zero
= niter_desc
.may_be_zero
;
3009 res
= niter_desc
.niter
;
3012 if (res
== chrec_dont_know
3014 || integer_zerop (may_be_zero
))
3016 else if (integer_nonzerop (may_be_zero
))
3017 res
= build_int_cst (TREE_TYPE (res
), 0);
3019 else if (COMPARISON_CLASS_P (may_be_zero
))
3020 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
3021 build_int_cst (TREE_TYPE (res
), 0), res
);
3023 res
= chrec_dont_know
;
3025 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3027 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
3028 print_generic_expr (dump_file
, res
, 0);
3029 fprintf (dump_file
, "))\n");
3032 loop
->nb_iterations
= res
;
3037 /* Counters for the stats. */
3043 unsigned nb_affine_multivar
;
3044 unsigned nb_higher_poly
;
3045 unsigned nb_chrec_dont_know
;
3046 unsigned nb_undetermined
;
3049 /* Reset the counters. */
3052 reset_chrecs_counters (struct chrec_stats
*stats
)
3054 stats
->nb_chrecs
= 0;
3055 stats
->nb_affine
= 0;
3056 stats
->nb_affine_multivar
= 0;
3057 stats
->nb_higher_poly
= 0;
3058 stats
->nb_chrec_dont_know
= 0;
3059 stats
->nb_undetermined
= 0;
3062 /* Dump the contents of a CHREC_STATS structure. */
3065 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
3067 fprintf (file
, "\n(\n");
3068 fprintf (file
, "-----------------------------------------\n");
3069 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
3070 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
3071 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
3072 stats
->nb_higher_poly
);
3073 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
3074 fprintf (file
, "-----------------------------------------\n");
3075 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
3076 fprintf (file
, "%d\twith undetermined coefficients\n",
3077 stats
->nb_undetermined
);
3078 fprintf (file
, "-----------------------------------------\n");
3079 fprintf (file
, "%d\tchrecs in the scev database\n",
3080 (int) scalar_evolution_info
->elements ());
3081 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
3082 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
3083 fprintf (file
, "-----------------------------------------\n");
3084 fprintf (file
, ")\n\n");
3087 /* Gather statistics about CHREC. */
3090 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
3092 if (dump_file
&& (dump_flags
& TDF_STATS
))
3094 fprintf (dump_file
, "(classify_chrec ");
3095 print_generic_expr (dump_file
, chrec
, 0);
3096 fprintf (dump_file
, "\n");
3101 if (chrec
== NULL_TREE
)
3103 stats
->nb_undetermined
++;
3107 switch (TREE_CODE (chrec
))
3109 case POLYNOMIAL_CHREC
:
3110 if (evolution_function_is_affine_p (chrec
))
3112 if (dump_file
&& (dump_flags
& TDF_STATS
))
3113 fprintf (dump_file
, " affine_univariate\n");
3116 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3118 if (dump_file
&& (dump_flags
& TDF_STATS
))
3119 fprintf (dump_file
, " affine_multivariate\n");
3120 stats
->nb_affine_multivar
++;
3124 if (dump_file
&& (dump_flags
& TDF_STATS
))
3125 fprintf (dump_file
, " higher_degree_polynomial\n");
3126 stats
->nb_higher_poly
++;
3135 if (chrec_contains_undetermined (chrec
))
3137 if (dump_file
&& (dump_flags
& TDF_STATS
))
3138 fprintf (dump_file
, " undetermined\n");
3139 stats
->nb_undetermined
++;
3142 if (dump_file
&& (dump_flags
& TDF_STATS
))
3143 fprintf (dump_file
, ")\n");
3146 /* Classify the chrecs of the whole database. */
3149 gather_stats_on_scev_database (void)
3151 struct chrec_stats stats
;
3156 reset_chrecs_counters (&stats
);
3158 hash_table
<scev_info_hasher
>::iterator iter
;
3160 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info
, elt
, scev_info_str
*,
3162 gather_chrec_stats (elt
->chrec
, &stats
);
3164 dump_chrecs_stats (dump_file
, &stats
);
3172 initialize_scalar_evolutions_analyzer (void)
3174 /* The elements below are unique. */
3175 if (chrec_dont_know
== NULL_TREE
)
3177 chrec_not_analyzed_yet
= NULL_TREE
;
3178 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3179 chrec_known
= make_node (SCEV_KNOWN
);
3180 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3181 TREE_TYPE (chrec_known
) = void_type_node
;
3185 /* Initialize the analysis of scalar evolutions for LOOPS. */
3188 scev_initialize (void)
3192 scalar_evolution_info
= hash_table
<scev_info_hasher
>::create_ggc (100);
3194 initialize_scalar_evolutions_analyzer ();
3196 FOR_EACH_LOOP (loop
, 0)
3198 loop
->nb_iterations
= NULL_TREE
;
3202 /* Return true if SCEV is initialized. */
3205 scev_initialized_p (void)
3207 return scalar_evolution_info
!= NULL
;
3210 /* Cleans up the information cached by the scalar evolutions analysis
3211 in the hash table. */
3214 scev_reset_htab (void)
3216 if (!scalar_evolution_info
)
3219 scalar_evolution_info
->empty ();
3222 /* Cleans up the information cached by the scalar evolutions analysis
3223 in the hash table and in the loop->nb_iterations. */
3232 FOR_EACH_LOOP (loop
, 0)
3234 loop
->nb_iterations
= NULL_TREE
;
3238 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3239 respect to WRTO_LOOP and returns its base and step in IV if possible
3240 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3241 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3242 invariant in LOOP. Otherwise we require it to be an integer constant.
3244 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3245 because it is computed in signed arithmetics). Consequently, adding an
3248 for (i = IV->base; ; i += IV->step)
3250 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3251 false for the type of the induction variable, or you can prove that i does
3252 not wrap by some other argument. Otherwise, this might introduce undefined
3255 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3257 must be used instead. */
3260 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3261 affine_iv
*iv
, bool allow_nonconstant_step
)
3266 iv
->base
= NULL_TREE
;
3267 iv
->step
= NULL_TREE
;
3268 iv
->no_overflow
= false;
3270 type
= TREE_TYPE (op
);
3271 if (!POINTER_TYPE_P (type
)
3272 && !INTEGRAL_TYPE_P (type
))
3275 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3277 if (chrec_contains_undetermined (ev
)
3278 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3281 if (tree_does_not_contain_chrecs (ev
))
3284 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3285 iv
->no_overflow
= true;
3289 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3290 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3293 iv
->step
= CHREC_RIGHT (ev
);
3294 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3295 || tree_contains_chrecs (iv
->step
, NULL
))
3298 iv
->base
= CHREC_LEFT (ev
);
3299 if (tree_contains_chrecs (iv
->base
, NULL
))
3302 iv
->no_overflow
= (!folded_casts
&& ANY_INTEGRAL_TYPE_P (type
)
3303 && TYPE_OVERFLOW_UNDEFINED (type
));
3308 /* Finalize the scalar evolution analysis. */
3311 scev_finalize (void)
3313 if (!scalar_evolution_info
)
3315 scalar_evolution_info
->empty ();
3316 scalar_evolution_info
= NULL
;
3319 /* Returns true if the expression EXPR is considered to be too expensive
3320 for scev_const_prop. */
3323 expression_expensive_p (tree expr
)
3325 enum tree_code code
;
3327 if (is_gimple_val (expr
))
3330 code
= TREE_CODE (expr
);
3331 if (code
== TRUNC_DIV_EXPR
3332 || code
== CEIL_DIV_EXPR
3333 || code
== FLOOR_DIV_EXPR
3334 || code
== ROUND_DIV_EXPR
3335 || code
== TRUNC_MOD_EXPR
3336 || code
== CEIL_MOD_EXPR
3337 || code
== FLOOR_MOD_EXPR
3338 || code
== ROUND_MOD_EXPR
3339 || code
== EXACT_DIV_EXPR
)
3341 /* Division by power of two is usually cheap, so we allow it.
3342 Forbid anything else. */
3343 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3347 switch (TREE_CODE_CLASS (code
))
3350 case tcc_comparison
:
3351 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3356 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3363 /* Replace ssa names for that scev can prove they are constant by the
3364 appropriate constants. Also perform final value replacement in loops,
3365 in case the replacement expressions are cheap.
3367 We only consider SSA names defined by phi nodes; rest is left to the
3368 ordinary constant propagation pass. */
3371 scev_const_prop (void)
3374 tree name
, type
, ev
;
3377 struct loop
*loop
, *ex_loop
;
3378 bitmap ssa_names_to_remove
= NULL
;
3382 if (number_of_loops (cfun
) <= 1)
3385 FOR_EACH_BB_FN (bb
, cfun
)
3387 loop
= bb
->loop_father
;
3389 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3392 name
= PHI_RESULT (phi
);
3394 if (virtual_operand_p (name
))
3397 type
= TREE_TYPE (name
);
3399 if (!POINTER_TYPE_P (type
)
3400 && !INTEGRAL_TYPE_P (type
))
3403 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
),
3405 if (!is_gimple_min_invariant (ev
)
3406 || !may_propagate_copy (name
, ev
))
3409 /* Replace the uses of the name. */
3411 replace_uses_by (name
, ev
);
3413 if (!ssa_names_to_remove
)
3414 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3415 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3419 /* Remove the ssa names that were replaced by constants. We do not
3420 remove them directly in the previous cycle, since this
3421 invalidates scev cache. */
3422 if (ssa_names_to_remove
)
3426 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3428 gimple_stmt_iterator psi
;
3429 name
= ssa_name (i
);
3430 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (name
));
3432 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3433 psi
= gsi_for_stmt (phi
);
3434 remove_phi_node (&psi
, true);
3437 BITMAP_FREE (ssa_names_to_remove
);
3441 /* Now the regular final value replacement. */
3442 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3445 tree def
, rslt
, niter
;
3446 gimple_stmt_iterator gsi
;
3448 /* If we do not know exact number of iterations of the loop, we cannot
3449 replace the final value. */
3450 exit
= single_exit (loop
);
3454 niter
= number_of_latch_executions (loop
);
3455 if (niter
== chrec_dont_know
)
3458 /* Ensure that it is possible to insert new statements somewhere. */
3459 if (!single_pred_p (exit
->dest
))
3460 split_loop_exit_edge (exit
);
3461 gsi
= gsi_after_labels (exit
->dest
);
3463 ex_loop
= superloop_at_depth (loop
,
3464 loop_depth (exit
->dest
->loop_father
) + 1);
3466 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3469 rslt
= PHI_RESULT (phi
);
3470 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3471 if (virtual_operand_p (def
))
3477 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3478 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3485 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
,
3487 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3488 if (!tree_does_not_contain_chrecs (def
)
3489 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3490 /* Moving the computation from the loop may prolong life range
3491 of some ssa names, which may cause problems if they appear
3492 on abnormal edges. */
3493 || contains_abnormal_ssa_name_p (def
)
3494 /* Do not emit expensive expressions. The rationale is that
3495 when someone writes a code like
3497 while (n > 45) n -= 45;
3499 he probably knows that n is not large, and does not want it
3500 to be turned into n %= 45. */
3501 || expression_expensive_p (def
))
3503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3505 fprintf (dump_file
, "not replacing:\n ");
3506 print_gimple_stmt (dump_file
, phi
, 0, 0);
3507 fprintf (dump_file
, "\n");
3513 /* Eliminate the PHI node and replace it by a computation outside
3517 fprintf (dump_file
, "\nfinal value replacement:\n ");
3518 print_gimple_stmt (dump_file
, phi
, 0, 0);
3519 fprintf (dump_file
, " with\n ");
3521 def
= unshare_expr (def
);
3522 remove_phi_node (&psi
, false);
3524 /* If def's type has undefined overflow and there were folded
3525 casts, rewrite all stmts added for def into arithmetics
3526 with defined overflow behavior. */
3527 if (folded_casts
&& ANY_INTEGRAL_TYPE_P (TREE_TYPE (def
))
3528 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def
)))
3531 gimple_stmt_iterator gsi2
;
3532 def
= force_gimple_operand (def
, &stmts
, true, NULL_TREE
);
3533 gsi2
= gsi_start (stmts
);
3534 while (!gsi_end_p (gsi2
))
3536 gimple stmt
= gsi_stmt (gsi2
);
3537 gimple_stmt_iterator gsi3
= gsi2
;
3539 gsi_remove (&gsi3
, false);
3540 if (is_gimple_assign (stmt
)
3541 && arith_code_with_undefined_signed_overflow
3542 (gimple_assign_rhs_code (stmt
)))
3543 gsi_insert_seq_before (&gsi
,
3544 rewrite_to_defined_overflow (stmt
),
3547 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3551 def
= force_gimple_operand_gsi (&gsi
, def
, false, NULL_TREE
,
3552 true, GSI_SAME_STMT
);
3554 ass
= gimple_build_assign (rslt
, def
);
3555 gsi_insert_before (&gsi
, ass
, GSI_SAME_STMT
);
3558 print_gimple_stmt (dump_file
, ass
, 0, 0);
3559 fprintf (dump_file
, "\n");
3566 #include "gt-tree-scalar-evolution.h"