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 evol
= add_to_evolution
963 chrec_convert (type
, evol
, at_stmt
),
964 code
, rhs1
, at_stmt
);
965 res
= follow_ssa_edge
966 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
968 *evolution_of_loop
= evol
;
969 else if (res
== t_false
)
971 *evolution_of_loop
= add_to_evolution
973 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
974 code
, rhs0
, at_stmt
);
975 res
= follow_ssa_edge
976 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
977 evolution_of_loop
, limit
);
980 else if (res
== t_dont_know
)
981 *evolution_of_loop
= chrec_dont_know
;
984 else if (res
== t_dont_know
)
985 *evolution_of_loop
= chrec_dont_know
;
990 /* Match an assignment under the form:
992 *evolution_of_loop
= add_to_evolution
993 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
995 code
, rhs1
, at_stmt
);
996 res
= follow_ssa_edge
997 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
998 evolution_of_loop
, limit
);
1001 else if (res
== t_dont_know
)
1002 *evolution_of_loop
= chrec_dont_know
;
1006 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1008 /* Match an assignment under the form:
1010 *evolution_of_loop
= add_to_evolution
1011 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1013 code
, rhs0
, at_stmt
);
1014 res
= follow_ssa_edge
1015 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1016 evolution_of_loop
, limit
);
1019 else if (res
== t_dont_know
)
1020 *evolution_of_loop
= chrec_dont_know
;
1024 /* Otherwise, match an assignment under the form:
1026 /* And there is nothing to do. */
1031 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1032 if (TREE_CODE (rhs0
) == SSA_NAME
)
1034 /* Match an assignment under the form:
1037 /* We want only assignments of form "name - name" contribute to
1038 LIMIT, as the other cases do not necessarily contribute to
1039 the complexity of the expression. */
1040 if (TREE_CODE (rhs1
) == SSA_NAME
)
1043 *evolution_of_loop
= add_to_evolution
1044 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1045 MINUS_EXPR
, rhs1
, at_stmt
);
1046 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1047 evolution_of_loop
, limit
);
1050 else if (res
== t_dont_know
)
1051 *evolution_of_loop
= chrec_dont_know
;
1054 /* Otherwise, match an assignment under the form:
1056 /* And there is nothing to do. */
1067 /* Follow the ssa edge into the expression EXPR.
1068 Return true if the strongly connected component has been found. */
1071 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1072 gphi
*halting_phi
, tree
*evolution_of_loop
,
1075 enum tree_code code
= TREE_CODE (expr
);
1076 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1079 /* The EXPR is one of the following cases:
1083 - a POINTER_PLUS_EXPR,
1086 - other cases are not yet handled. */
1091 /* This assignment is under the form "a_1 = (cast) rhs. */
1092 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1093 halting_phi
, evolution_of_loop
, limit
);
1094 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1098 /* This assignment is under the form "a_1 = 7". */
1103 /* This assignment is under the form: "a_1 = b_2". */
1104 res
= follow_ssa_edge
1105 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1108 case POINTER_PLUS_EXPR
:
1111 /* This case is under the form "rhs0 +- rhs1". */
1112 rhs0
= TREE_OPERAND (expr
, 0);
1113 rhs1
= TREE_OPERAND (expr
, 1);
1114 type
= TREE_TYPE (rhs0
);
1115 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1116 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1117 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1118 halting_phi
, evolution_of_loop
, limit
);
1122 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1123 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1125 expr
= TREE_OPERAND (expr
, 0);
1126 rhs0
= TREE_OPERAND (expr
, 0);
1127 rhs1
= TREE_OPERAND (expr
, 1);
1128 type
= TREE_TYPE (rhs0
);
1129 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1130 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1131 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1132 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1133 halting_phi
, evolution_of_loop
, limit
);
1140 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1141 It must be handled as a copy assignment of the form a_1 = a_2. */
1142 rhs0
= ASSERT_EXPR_VAR (expr
);
1143 if (TREE_CODE (rhs0
) == SSA_NAME
)
1144 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1145 halting_phi
, evolution_of_loop
, limit
);
1158 /* Follow the ssa edge into the right hand side of an assignment STMT.
1159 Return true if the strongly connected component has been found. */
1162 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1163 gphi
*halting_phi
, tree
*evolution_of_loop
,
1166 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1167 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1173 /* This assignment is under the form "a_1 = (cast) rhs. */
1174 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1175 halting_phi
, evolution_of_loop
, limit
);
1176 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1179 case POINTER_PLUS_EXPR
:
1182 rhs1
= gimple_assign_rhs1 (stmt
);
1183 rhs2
= gimple_assign_rhs2 (stmt
);
1184 type
= TREE_TYPE (rhs1
);
1185 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1186 halting_phi
, evolution_of_loop
, limit
);
1190 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1191 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1192 halting_phi
, evolution_of_loop
, limit
);
1201 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1204 backedge_phi_arg_p (gphi
*phi
, int i
)
1206 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1208 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1209 about updating it anywhere, and this should work as well most of the
1211 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1217 /* Helper function for one branch of the condition-phi-node. Return
1218 true if the strongly connected component has been found following
1221 static inline t_bool
1222 follow_ssa_edge_in_condition_phi_branch (int i
,
1224 gphi
*condition_phi
,
1226 tree
*evolution_of_branch
,
1227 tree init_cond
, int limit
)
1229 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1230 *evolution_of_branch
= chrec_dont_know
;
1232 /* Do not follow back edges (they must belong to an irreducible loop, which
1233 we really do not want to worry about). */
1234 if (backedge_phi_arg_p (condition_phi
, i
))
1237 if (TREE_CODE (branch
) == SSA_NAME
)
1239 *evolution_of_branch
= init_cond
;
1240 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1241 evolution_of_branch
, limit
);
1244 /* This case occurs when one of the condition branches sets
1245 the variable to a constant: i.e. a phi-node like
1246 "a_2 = PHI <a_7(5), 2(6)>;".
1248 FIXME: This case have to be refined correctly:
1249 in some cases it is possible to say something better than
1250 chrec_dont_know, for example using a wrap-around notation. */
1254 /* This function merges the branches of a condition-phi-node in a
1258 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1259 gphi
*condition_phi
,
1261 tree
*evolution_of_loop
, int limit
)
1264 tree init
= *evolution_of_loop
;
1265 tree evolution_of_branch
;
1266 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1268 &evolution_of_branch
,
1270 if (res
== t_false
|| res
== t_dont_know
)
1273 *evolution_of_loop
= evolution_of_branch
;
1275 n
= gimple_phi_num_args (condition_phi
);
1276 for (i
= 1; i
< n
; i
++)
1278 /* Quickly give up when the evolution of one of the branches is
1280 if (*evolution_of_loop
== chrec_dont_know
)
1283 /* Increase the limit by the PHI argument number to avoid exponential
1284 time and memory complexity. */
1285 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1287 &evolution_of_branch
,
1289 if (res
== t_false
|| res
== t_dont_know
)
1292 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1293 evolution_of_branch
);
1299 /* Follow an SSA edge in an inner loop. It computes the overall
1300 effect of the loop, and following the symbolic initial conditions,
1301 it follows the edges in the parent loop. The inner loop is
1302 considered as a single statement. */
1305 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1306 gphi
*loop_phi_node
,
1308 tree
*evolution_of_loop
, int limit
)
1310 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1311 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1313 /* Sometimes, the inner loop is too difficult to analyze, and the
1314 result of the analysis is a symbolic parameter. */
1315 if (ev
== PHI_RESULT (loop_phi_node
))
1317 t_bool res
= t_false
;
1318 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1320 for (i
= 0; i
< n
; i
++)
1322 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1325 /* Follow the edges that exit the inner loop. */
1326 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1327 if (!flow_bb_inside_loop_p (loop
, bb
))
1328 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1330 evolution_of_loop
, limit
);
1335 /* If the path crosses this loop-phi, give up. */
1337 *evolution_of_loop
= chrec_dont_know
;
1342 /* Otherwise, compute the overall effect of the inner loop. */
1343 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1344 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1345 evolution_of_loop
, limit
);
1348 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1349 path that is analyzed on the return walk. */
1352 follow_ssa_edge (struct loop
*loop
, gimple def
, gphi
*halting_phi
,
1353 tree
*evolution_of_loop
, int limit
)
1355 struct loop
*def_loop
;
1357 if (gimple_nop_p (def
))
1360 /* Give up if the path is longer than the MAX that we allow. */
1361 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1364 def_loop
= loop_containing_stmt (def
);
1366 switch (gimple_code (def
))
1369 if (!loop_phi_node_p (def
))
1370 /* DEF is a condition-phi-node. Follow the branches, and
1371 record their evolutions. Finally, merge the collected
1372 information and set the approximation to the main
1374 return follow_ssa_edge_in_condition_phi
1375 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1378 /* When the analyzed phi is the halting_phi, the
1379 depth-first search is over: we have found a path from
1380 the halting_phi to itself in the loop. */
1381 if (def
== halting_phi
)
1384 /* Otherwise, the evolution of the HALTING_PHI depends
1385 on the evolution of another loop-phi-node, i.e. the
1386 evolution function is a higher degree polynomial. */
1387 if (def_loop
== loop
)
1391 if (flow_loop_nested_p (loop
, def_loop
))
1392 return follow_ssa_edge_inner_loop_phi
1393 (loop
, as_a
<gphi
*> (def
), halting_phi
, evolution_of_loop
,
1400 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1401 evolution_of_loop
, limit
);
1404 /* At this level of abstraction, the program is just a set
1405 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1406 other node to be handled. */
1412 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1413 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1415 # i_17 = PHI <i_13(5), 0(3)>
1416 # _20 = PHI <_5(5), start_4(D)(3)>
1419 _5 = start_4(D) + i_13;
1421 Though variable _20 appears as a PEELED_CHREC in the form of
1422 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1427 simplify_peeled_chrec (struct loop
*loop
, tree arg
, tree init_cond
)
1429 aff_tree aff1
, aff2
;
1430 tree ev
, left
, right
, type
, step_val
;
1431 hash_map
<tree
, name_expansion
*> *peeled_chrec_map
= NULL
;
1433 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1434 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1435 return chrec_dont_know
;
1437 left
= CHREC_LEFT (ev
);
1438 right
= CHREC_RIGHT (ev
);
1439 type
= TREE_TYPE (left
);
1440 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1442 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1443 if "left" equals to "init + right". */
1444 if (operand_equal_p (left
, step_val
, 0))
1446 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1447 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1449 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1452 /* Try harder to check if they are equal. */
1453 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1454 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1455 free_affine_expand_cache (&peeled_chrec_map
);
1456 aff_combination_scale (&aff2
, -1);
1457 aff_combination_add (&aff1
, &aff2
);
1459 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1460 if "left" equals to "init + right". */
1461 if (aff_combination_zero_p (&aff1
))
1463 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1464 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1466 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1468 return chrec_dont_know
;
1471 /* Given a LOOP_PHI_NODE, this function determines the evolution
1472 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1475 analyze_evolution_in_loop (gphi
*loop_phi_node
,
1478 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1479 tree evolution_function
= chrec_not_analyzed_yet
;
1480 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1482 static bool simplify_peeled_chrec_p
= true;
1484 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1486 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1487 fprintf (dump_file
, " (loop_phi_node = ");
1488 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1489 fprintf (dump_file
, ")\n");
1492 for (i
= 0; i
< n
; i
++)
1494 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1499 /* Select the edges that enter the loop body. */
1500 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1501 if (!flow_bb_inside_loop_p (loop
, bb
))
1504 if (TREE_CODE (arg
) == SSA_NAME
)
1508 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1510 /* Pass in the initial condition to the follow edge function. */
1512 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1514 /* If ev_fn has no evolution in the inner loop, and the
1515 init_cond is not equal to ev_fn, then we have an
1516 ambiguity between two possible values, as we cannot know
1517 the number of iterations at this point. */
1518 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1519 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1520 && !operand_equal_p (init_cond
, ev_fn
, 0))
1521 ev_fn
= chrec_dont_know
;
1526 /* When it is impossible to go back on the same
1527 loop_phi_node by following the ssa edges, the
1528 evolution is represented by a peeled chrec, i.e. the
1529 first iteration, EV_FN has the value INIT_COND, then
1530 all the other iterations it has the value of ARG.
1531 For the moment, PEELED_CHREC nodes are not built. */
1534 ev_fn
= chrec_dont_know
;
1535 /* Try to recognize POLYNOMIAL_CHREC which appears in
1536 the form of PEELED_CHREC, but guard the process with
1537 a bool variable to keep the analyzer from infinite
1538 recurrence for real PEELED_RECs. */
1539 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1541 simplify_peeled_chrec_p
= false;
1542 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1543 simplify_peeled_chrec_p
= true;
1547 /* When there are multiple back edges of the loop (which in fact never
1548 happens currently, but nevertheless), merge their evolutions. */
1549 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1552 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1554 fprintf (dump_file
, " (evolution_function = ");
1555 print_generic_expr (dump_file
, evolution_function
, 0);
1556 fprintf (dump_file
, "))\n");
1559 return evolution_function
;
1562 /* Given a loop-phi-node, return the initial conditions of the
1563 variable on entry of the loop. When the CCP has propagated
1564 constants into the loop-phi-node, the initial condition is
1565 instantiated, otherwise the initial condition is kept symbolic.
1566 This analyzer does not analyze the evolution outside the current
1567 loop, and leaves this task to the on-demand tree reconstructor. */
1570 analyze_initial_condition (gphi
*loop_phi_node
)
1573 tree init_cond
= chrec_not_analyzed_yet
;
1574 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1576 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1578 fprintf (dump_file
, "(analyze_initial_condition \n");
1579 fprintf (dump_file
, " (loop_phi_node = \n");
1580 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1581 fprintf (dump_file
, ")\n");
1584 n
= gimple_phi_num_args (loop_phi_node
);
1585 for (i
= 0; i
< n
; i
++)
1587 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1588 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1590 /* When the branch is oriented to the loop's body, it does
1591 not contribute to the initial condition. */
1592 if (flow_bb_inside_loop_p (loop
, bb
))
1595 if (init_cond
== chrec_not_analyzed_yet
)
1601 if (TREE_CODE (branch
) == SSA_NAME
)
1603 init_cond
= chrec_dont_know
;
1607 init_cond
= chrec_merge (init_cond
, branch
);
1610 /* Ooops -- a loop without an entry??? */
1611 if (init_cond
== chrec_not_analyzed_yet
)
1612 init_cond
= chrec_dont_know
;
1614 /* During early loop unrolling we do not have fully constant propagated IL.
1615 Handle degenerate PHIs here to not miss important unrollings. */
1616 if (TREE_CODE (init_cond
) == SSA_NAME
)
1618 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1619 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
1621 tree res
= degenerate_phi_result (phi
);
1622 if (res
!= NULL_TREE
1623 /* Only allow invariants here, otherwise we may break
1624 loop-closed SSA form. */
1625 && is_gimple_min_invariant (res
))
1630 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1632 fprintf (dump_file
, " (init_cond = ");
1633 print_generic_expr (dump_file
, init_cond
, 0);
1634 fprintf (dump_file
, "))\n");
1640 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1643 interpret_loop_phi (struct loop
*loop
, gphi
*loop_phi_node
)
1646 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1649 if (phi_loop
!= loop
)
1651 struct loop
*subloop
;
1652 tree evolution_fn
= analyze_scalar_evolution
1653 (phi_loop
, PHI_RESULT (loop_phi_node
));
1655 /* Dive one level deeper. */
1656 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1658 /* Interpret the subloop. */
1659 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1663 /* Otherwise really interpret the loop phi. */
1664 init_cond
= analyze_initial_condition (loop_phi_node
);
1665 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1667 /* Verify we maintained the correct initial condition throughout
1668 possible conversions in the SSA chain. */
1669 if (res
!= chrec_dont_know
)
1671 tree new_init
= res
;
1672 if (CONVERT_EXPR_P (res
)
1673 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1674 new_init
= fold_convert (TREE_TYPE (res
),
1675 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1676 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1677 new_init
= CHREC_LEFT (res
);
1678 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1679 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1680 || !operand_equal_p (init_cond
, new_init
, 0))
1681 return chrec_dont_know
;
1687 /* This function merges the branches of a condition-phi-node,
1688 contained in the outermost loop, and whose arguments are already
1692 interpret_condition_phi (struct loop
*loop
, gphi
*condition_phi
)
1694 int i
, n
= gimple_phi_num_args (condition_phi
);
1695 tree res
= chrec_not_analyzed_yet
;
1697 for (i
= 0; i
< n
; i
++)
1701 if (backedge_phi_arg_p (condition_phi
, i
))
1703 res
= chrec_dont_know
;
1707 branch_chrec
= analyze_scalar_evolution
1708 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1710 res
= chrec_merge (res
, branch_chrec
);
1716 /* Interpret the operation RHS1 OP RHS2. If we didn't
1717 analyze this node before, follow the definitions until ending
1718 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1719 return path, this function propagates evolutions (ala constant copy
1720 propagation). OPND1 is not a GIMPLE expression because we could
1721 analyze the effect of an inner loop: see interpret_loop_phi. */
1724 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1725 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1727 tree res
, chrec1
, chrec2
, ctype
;
1730 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1732 if (is_gimple_min_invariant (rhs1
))
1733 return chrec_convert (type
, rhs1
, at_stmt
);
1735 if (code
== SSA_NAME
)
1736 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1739 if (code
== ASSERT_EXPR
)
1741 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1742 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1750 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1751 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1754 HOST_WIDE_INT bitsize
, bitpos
;
1761 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1762 &bitsize
, &bitpos
, &offset
,
1763 &mode
, &unsignedp
, &volatilep
, false);
1765 if (TREE_CODE (base
) == MEM_REF
)
1767 rhs2
= TREE_OPERAND (base
, 1);
1768 rhs1
= TREE_OPERAND (base
, 0);
1770 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1771 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1772 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1773 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1774 chrec1
= instantiate_parameters (loop
, chrec1
);
1775 chrec2
= instantiate_parameters (loop
, chrec2
);
1776 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1780 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1781 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1785 if (offset
!= NULL_TREE
)
1787 chrec2
= analyze_scalar_evolution (loop
, offset
);
1788 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1789 chrec2
= instantiate_parameters (loop
, chrec2
);
1790 res
= chrec_fold_plus (type
, res
, chrec2
);
1795 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1797 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1798 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1799 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1800 chrec3
= instantiate_parameters (loop
, chrec3
);
1801 res
= chrec_fold_plus (type
, res
, chrec3
);
1805 res
= chrec_dont_know
;
1808 case POINTER_PLUS_EXPR
:
1809 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1810 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1811 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1812 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1813 chrec1
= instantiate_parameters (loop
, chrec1
);
1814 chrec2
= instantiate_parameters (loop
, chrec2
);
1815 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1819 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1820 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1822 /* When the stmt is conditionally executed re-write the CHREC
1823 into a form that has well-defined behavior on overflow. */
1825 && INTEGRAL_TYPE_P (type
)
1826 && ! TYPE_OVERFLOW_WRAPS (type
)
1827 && ! dominated_by_p (CDI_DOMINATORS
, loop
->latch
,
1828 gimple_bb (at_stmt
)))
1829 ctype
= unsigned_type_for (type
);
1830 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1831 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1832 chrec1
= instantiate_parameters (loop
, chrec1
);
1833 chrec2
= instantiate_parameters (loop
, chrec2
);
1834 res
= chrec_fold_plus (ctype
, chrec1
, chrec2
);
1836 res
= chrec_convert (type
, res
, at_stmt
);
1840 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1841 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1843 /* When the stmt is conditionally executed re-write the CHREC
1844 into a form that has well-defined behavior on overflow. */
1846 && INTEGRAL_TYPE_P (type
)
1847 && ! TYPE_OVERFLOW_WRAPS (type
)
1848 && ! dominated_by_p (CDI_DOMINATORS
,
1849 loop
->latch
, gimple_bb (at_stmt
)))
1850 ctype
= unsigned_type_for (type
);
1851 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1852 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1853 chrec1
= instantiate_parameters (loop
, chrec1
);
1854 chrec2
= instantiate_parameters (loop
, chrec2
);
1855 res
= chrec_fold_minus (ctype
, chrec1
, chrec2
);
1857 res
= chrec_convert (type
, res
, at_stmt
);
1861 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1863 /* When the stmt is conditionally executed re-write the CHREC
1864 into a form that has well-defined behavior on overflow. */
1866 && INTEGRAL_TYPE_P (type
)
1867 && ! TYPE_OVERFLOW_WRAPS (type
)
1868 && ! dominated_by_p (CDI_DOMINATORS
,
1869 loop
->latch
, gimple_bb (at_stmt
)))
1870 ctype
= unsigned_type_for (type
);
1871 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1872 /* TYPE may be integer, real or complex, so use fold_convert. */
1873 chrec1
= instantiate_parameters (loop
, chrec1
);
1874 res
= chrec_fold_multiply (ctype
, chrec1
,
1875 fold_convert (ctype
, integer_minus_one_node
));
1877 res
= chrec_convert (type
, res
, at_stmt
);
1881 /* Handle ~X as -1 - X. */
1882 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1883 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1884 chrec1
= instantiate_parameters (loop
, chrec1
);
1885 res
= chrec_fold_minus (type
,
1886 fold_convert (type
, integer_minus_one_node
),
1891 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1892 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1894 /* When the stmt is conditionally executed re-write the CHREC
1895 into a form that has well-defined behavior on overflow. */
1897 && INTEGRAL_TYPE_P (type
)
1898 && ! TYPE_OVERFLOW_WRAPS (type
)
1899 && ! dominated_by_p (CDI_DOMINATORS
,
1900 loop
->latch
, gimple_bb (at_stmt
)))
1901 ctype
= unsigned_type_for (type
);
1902 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1903 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1904 chrec1
= instantiate_parameters (loop
, chrec1
);
1905 chrec2
= instantiate_parameters (loop
, chrec2
);
1906 res
= chrec_fold_multiply (ctype
, chrec1
, chrec2
);
1908 res
= chrec_convert (type
, res
, at_stmt
);
1912 /* In case we have a truncation of a widened operation that in
1913 the truncated type has undefined overflow behavior analyze
1914 the operation done in an unsigned type of the same precision
1915 as the final truncation. We cannot derive a scalar evolution
1916 for the widened operation but for the truncated result. */
1917 if (TREE_CODE (type
) == INTEGER_TYPE
1918 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1919 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1920 && TYPE_OVERFLOW_UNDEFINED (type
)
1921 && TREE_CODE (rhs1
) == SSA_NAME
1922 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1923 && is_gimple_assign (def
)
1924 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1925 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1927 tree utype
= unsigned_type_for (type
);
1928 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1929 gimple_assign_rhs1 (def
),
1930 gimple_assign_rhs_code (def
),
1931 gimple_assign_rhs2 (def
));
1934 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1935 res
= chrec_convert (type
, chrec1
, at_stmt
);
1939 res
= chrec_dont_know
;
1946 /* Interpret the expression EXPR. */
1949 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1951 enum tree_code code
;
1952 tree type
= TREE_TYPE (expr
), op0
, op1
;
1954 if (automatically_generated_chrec_p (expr
))
1957 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1958 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1959 return chrec_dont_know
;
1961 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1963 return interpret_rhs_expr (loop
, at_stmt
, type
,
1967 /* Interpret the rhs of the assignment STMT. */
1970 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1972 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1973 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1975 return interpret_rhs_expr (loop
, stmt
, type
,
1976 gimple_assign_rhs1 (stmt
), code
,
1977 gimple_assign_rhs2 (stmt
));
1982 /* This section contains all the entry points:
1983 - number_of_iterations_in_loop,
1984 - analyze_scalar_evolution,
1985 - instantiate_parameters.
1988 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1989 common ancestor of DEF_LOOP and USE_LOOP. */
1992 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1993 struct loop
*def_loop
,
1999 if (def_loop
== wrto_loop
)
2002 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
2003 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
2005 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
2008 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
2011 /* Helper recursive function. */
2014 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
2016 tree type
= TREE_TYPE (var
);
2019 struct loop
*def_loop
;
2021 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
2022 return chrec_dont_know
;
2024 if (TREE_CODE (var
) != SSA_NAME
)
2025 return interpret_expr (loop
, NULL
, var
);
2027 def
= SSA_NAME_DEF_STMT (var
);
2028 bb
= gimple_bb (def
);
2029 def_loop
= bb
? bb
->loop_father
: NULL
;
2032 || !flow_bb_inside_loop_p (loop
, bb
))
2034 /* Keep the symbolic form. */
2039 if (res
!= chrec_not_analyzed_yet
)
2041 if (loop
!= bb
->loop_father
)
2042 res
= compute_scalar_evolution_in_loop
2043 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
2048 if (loop
!= def_loop
)
2050 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
2051 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
2056 switch (gimple_code (def
))
2059 res
= interpret_gimple_assign (loop
, def
);
2063 if (loop_phi_node_p (def
))
2064 res
= interpret_loop_phi (loop
, as_a
<gphi
*> (def
));
2066 res
= interpret_condition_phi (loop
, as_a
<gphi
*> (def
));
2070 res
= chrec_dont_know
;
2076 /* Keep the symbolic form. */
2077 if (res
== chrec_dont_know
)
2080 if (loop
== def_loop
)
2081 set_scalar_evolution (block_before_loop (loop
), var
, res
);
2086 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2087 LOOP. LOOP is the loop in which the variable is used.
2089 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2090 pointer to the statement that uses this variable, in order to
2091 determine the evolution function of the variable, use the following
2094 loop_p loop = loop_containing_stmt (stmt);
2095 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2096 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2100 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2104 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2106 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2107 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2108 fprintf (dump_file
, " (scalar = ");
2109 print_generic_expr (dump_file
, var
, 0);
2110 fprintf (dump_file
, ")\n");
2113 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2114 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
2116 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2117 fprintf (dump_file
, ")\n");
2122 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2125 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
2127 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2130 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2131 WRTO_LOOP (which should be a superloop of USE_LOOP)
2133 FOLDED_CASTS is set to true if resolve_mixers used
2134 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2135 at the moment in order to keep things simple).
2137 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2140 for (i = 0; i < 100; i++) -- loop 1
2142 for (j = 0; j < 100; j++) -- loop 2
2149 for (t = 0; t < 100; t++) -- loop 3
2156 Both k1 and k2 are invariants in loop3, thus
2157 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2158 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2160 As they are invariant, it does not matter whether we consider their
2161 usage in loop 3 or loop 2, hence
2162 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2163 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2164 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2165 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2167 Similarly for their evolutions with respect to loop 1. The values of K2
2168 in the use in loop 2 vary independently on loop 1, thus we cannot express
2169 the evolution with respect to loop 1:
2170 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2171 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2172 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2173 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2175 The value of k2 in the use in loop 1 is known, though:
2176 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2177 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2181 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2182 tree version
, bool *folded_casts
)
2185 tree ev
= version
, tmp
;
2187 /* We cannot just do
2189 tmp = analyze_scalar_evolution (use_loop, version);
2190 ev = resolve_mixers (wrto_loop, tmp);
2192 as resolve_mixers would query the scalar evolution with respect to
2193 wrto_loop. For example, in the situation described in the function
2194 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2197 analyze_scalar_evolution (use_loop, version) = k2
2199 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2200 is 100, which is a wrong result, since we are interested in the
2203 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2204 each time checking that there is no evolution in the inner loop. */
2207 *folded_casts
= false;
2210 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2211 ev
= resolve_mixers (use_loop
, tmp
);
2213 if (folded_casts
&& tmp
!= ev
)
2214 *folded_casts
= true;
2216 if (use_loop
== wrto_loop
)
2219 /* If the value of the use changes in the inner loop, we cannot express
2220 its value in the outer loop (we might try to return interval chrec,
2221 but we do not have a user for it anyway) */
2222 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2224 return chrec_dont_know
;
2226 use_loop
= loop_outer (use_loop
);
2231 /* Hashtable helpers for a temporary hash-table used when
2232 instantiating a CHREC or resolving mixers. For this use
2233 instantiated_below is always the same. */
2235 struct instantiate_cache_type
2238 vec
<scev_info_str
> entries
;
2240 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2241 ~instantiate_cache_type ();
2242 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2243 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2246 instantiate_cache_type::~instantiate_cache_type ()
2255 /* Cache to avoid infinite recursion when instantiating an SSA name.
2256 Live during the outermost instantiate_scev or resolve_mixers call. */
2257 static instantiate_cache_type
*global_cache
;
2259 /* Computes a hash function for database element ELT. */
2261 static inline hashval_t
2262 hash_idx_scev_info (const void *elt_
)
2264 unsigned idx
= ((size_t) elt_
) - 2;
2265 return scev_info_hasher::hash (&global_cache
->entries
[idx
]);
2268 /* Compares database elements E1 and E2. */
2271 eq_idx_scev_info (const void *e1
, const void *e2
)
2273 unsigned idx1
= ((size_t) e1
) - 2;
2274 return scev_info_hasher::equal (&global_cache
->entries
[idx1
],
2275 (const scev_info_str
*) e2
);
2278 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2281 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2282 tree name
, basic_block instantiate_below
)
2286 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2287 cache
.entries
.create (10);
2291 e
.name_version
= SSA_NAME_VERSION (name
);
2292 e
.instantiated_below
= instantiate_below
->index
;
2293 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2294 scev_info_hasher::hash (&e
), INSERT
);
2297 e
.chrec
= chrec_not_analyzed_yet
;
2298 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2299 cache
.entries
.safe_push (e
);
2302 return ((size_t)*slot
) - 2;
2306 /* Return the closed_loop_phi node for VAR. If there is none, return
2310 loop_closed_phi_def (tree var
)
2317 if (var
== NULL_TREE
2318 || TREE_CODE (var
) != SSA_NAME
)
2321 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2322 exit
= single_exit (loop
);
2326 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2329 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2330 return PHI_RESULT (phi
);
2336 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2339 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2340 and EVOLUTION_LOOP, that were left under a symbolic form.
2342 CHREC is an SSA_NAME to be instantiated.
2344 CACHE is the cache of already instantiated values.
2346 FOLD_CONVERSIONS should be set to true when the conversions that
2347 may wrap in signed/pointer type are folded, as long as the value of
2348 the chrec is preserved.
2350 SIZE_EXPR is used for computing the size of the expression to be
2351 instantiated, and to stop if it exceeds some limit. */
2354 instantiate_scev_name (basic_block instantiate_below
,
2355 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2357 bool fold_conversions
,
2361 struct loop
*def_loop
;
2362 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2364 /* A parameter (or loop invariant and we do not want to include
2365 evolutions in outer loops), nothing to do. */
2367 || loop_depth (def_bb
->loop_father
) == 0
2368 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2371 /* We cache the value of instantiated variable to avoid exponential
2372 time complexity due to reevaluations. We also store the convenient
2373 value in the cache in order to prevent infinite recursion -- we do
2374 not want to instantiate the SSA_NAME if it is in a mixer
2375 structure. This is used for avoiding the instantiation of
2376 recursively defined functions, such as:
2378 | a_2 -> {0, +, 1, +, a_2}_1 */
2380 unsigned si
= get_instantiated_value_entry (*global_cache
,
2381 chrec
, instantiate_below
);
2382 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2383 return global_cache
->get (si
);
2385 /* On recursion return chrec_dont_know. */
2386 global_cache
->set (si
, chrec_dont_know
);
2388 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2390 /* If the analysis yields a parametric chrec, instantiate the
2392 res
= analyze_scalar_evolution (def_loop
, chrec
);
2394 /* Don't instantiate default definitions. */
2395 if (TREE_CODE (res
) == SSA_NAME
2396 && SSA_NAME_IS_DEFAULT_DEF (res
))
2399 /* Don't instantiate loop-closed-ssa phi nodes. */
2400 else if (TREE_CODE (res
) == SSA_NAME
2401 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2402 > loop_depth (def_loop
))
2405 res
= loop_closed_phi_def (chrec
);
2409 /* When there is no loop_closed_phi_def, it means that the
2410 variable is not used after the loop: try to still compute the
2411 value of the variable when exiting the loop. */
2412 if (res
== NULL_TREE
)
2414 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2415 res
= analyze_scalar_evolution (loop
, chrec
);
2416 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2417 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2419 fold_conversions
, size_expr
);
2421 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2422 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2423 res
= chrec_dont_know
;
2426 else if (res
!= chrec_dont_know
)
2429 && def_bb
->loop_father
!= inner_loop
2430 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2431 /* ??? We could try to compute the overall effect of the loop here. */
2432 res
= chrec_dont_know
;
2434 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2436 fold_conversions
, size_expr
);
2439 /* Store the correct value to the cache. */
2440 global_cache
->set (si
, res
);
2444 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2445 and EVOLUTION_LOOP, that were left under a symbolic form.
2447 CHREC is a polynomial chain of recurrence to be instantiated.
2449 CACHE is the cache of already instantiated values.
2451 FOLD_CONVERSIONS should be set to true when the conversions that
2452 may wrap in signed/pointer type are folded, as long as the value of
2453 the chrec is preserved.
2455 SIZE_EXPR is used for computing the size of the expression to be
2456 instantiated, and to stop if it exceeds some limit. */
2459 instantiate_scev_poly (basic_block instantiate_below
,
2460 struct loop
*evolution_loop
, struct loop
*,
2461 tree chrec
, bool fold_conversions
, int size_expr
)
2464 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2465 get_chrec_loop (chrec
),
2466 CHREC_LEFT (chrec
), fold_conversions
,
2468 if (op0
== chrec_dont_know
)
2469 return chrec_dont_know
;
2471 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2472 get_chrec_loop (chrec
),
2473 CHREC_RIGHT (chrec
), fold_conversions
,
2475 if (op1
== chrec_dont_know
)
2476 return chrec_dont_know
;
2478 if (CHREC_LEFT (chrec
) != op0
2479 || CHREC_RIGHT (chrec
) != op1
)
2481 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2482 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2488 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2489 and EVOLUTION_LOOP, that were left under a symbolic form.
2491 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2493 CACHE is the cache of already instantiated values.
2495 FOLD_CONVERSIONS should be set to true when the conversions that
2496 may wrap in signed/pointer type are folded, as long as the value of
2497 the chrec is preserved.
2499 SIZE_EXPR is used for computing the size of the expression to be
2500 instantiated, and to stop if it exceeds some limit. */
2503 instantiate_scev_binary (basic_block instantiate_below
,
2504 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2505 tree chrec
, enum tree_code code
,
2506 tree type
, tree c0
, tree c1
,
2507 bool fold_conversions
, int size_expr
)
2510 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2511 c0
, fold_conversions
, size_expr
);
2512 if (op0
== chrec_dont_know
)
2513 return chrec_dont_know
;
2515 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2516 c1
, fold_conversions
, size_expr
);
2517 if (op1
== chrec_dont_know
)
2518 return chrec_dont_know
;
2523 op0
= chrec_convert (type
, op0
, NULL
);
2524 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2528 case POINTER_PLUS_EXPR
:
2530 return chrec_fold_plus (type
, op0
, op1
);
2533 return chrec_fold_minus (type
, op0
, op1
);
2536 return chrec_fold_multiply (type
, op0
, op1
);
2543 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2546 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2547 and EVOLUTION_LOOP, that were left under a symbolic form.
2549 "CHREC" is an array reference to be instantiated.
2551 CACHE is the cache of already instantiated values.
2553 FOLD_CONVERSIONS should be set to true when the conversions that
2554 may wrap in signed/pointer type are folded, as long as the value of
2555 the chrec is preserved.
2557 SIZE_EXPR is used for computing the size of the expression to be
2558 instantiated, and to stop if it exceeds some limit. */
2561 instantiate_array_ref (basic_block instantiate_below
,
2562 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2563 tree chrec
, bool fold_conversions
, int size_expr
)
2566 tree index
= TREE_OPERAND (chrec
, 1);
2567 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2569 fold_conversions
, size_expr
);
2571 if (op1
== chrec_dont_know
)
2572 return chrec_dont_know
;
2574 if (chrec
&& op1
== index
)
2577 res
= unshare_expr (chrec
);
2578 TREE_OPERAND (res
, 1) = op1
;
2582 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2583 and EVOLUTION_LOOP, that were left under a symbolic form.
2585 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2588 CACHE is the cache of already instantiated values.
2590 FOLD_CONVERSIONS should be set to true when the conversions that
2591 may wrap in signed/pointer type are folded, as long as the value of
2592 the chrec is preserved.
2594 SIZE_EXPR is used for computing the size of the expression to be
2595 instantiated, and to stop if it exceeds some limit. */
2598 instantiate_scev_convert (basic_block instantiate_below
,
2599 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2600 tree chrec
, tree type
, tree op
,
2601 bool fold_conversions
, int size_expr
)
2603 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2605 fold_conversions
, size_expr
);
2607 if (op0
== chrec_dont_know
)
2608 return chrec_dont_know
;
2610 if (fold_conversions
)
2612 tree tmp
= chrec_convert_aggressive (type
, op0
);
2617 if (chrec
&& op0
== op
)
2620 /* If we used chrec_convert_aggressive, we can no longer assume that
2621 signed chrecs do not overflow, as chrec_convert does, so avoid
2622 calling it in that case. */
2623 if (fold_conversions
)
2624 return fold_convert (type
, op0
);
2626 return chrec_convert (type
, op0
, NULL
);
2629 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2630 and EVOLUTION_LOOP, that were left under a symbolic form.
2632 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2633 Handle ~X as -1 - X.
2634 Handle -X as -1 * X.
2636 CACHE is the cache of already instantiated values.
2638 FOLD_CONVERSIONS should be set to true when the conversions that
2639 may wrap in signed/pointer type are folded, as long as the value of
2640 the chrec is preserved.
2642 SIZE_EXPR is used for computing the size of the expression to be
2643 instantiated, and to stop if it exceeds some limit. */
2646 instantiate_scev_not (basic_block instantiate_below
,
2647 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2649 enum tree_code code
, tree type
, tree op
,
2650 bool fold_conversions
, int size_expr
)
2652 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2654 fold_conversions
, size_expr
);
2656 if (op0
== chrec_dont_know
)
2657 return chrec_dont_know
;
2661 op0
= chrec_convert (type
, op0
, NULL
);
2666 return chrec_fold_minus
2667 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2670 return chrec_fold_multiply
2671 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2678 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2681 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2682 and EVOLUTION_LOOP, that were left under a symbolic form.
2684 CHREC is an expression with 3 operands to be instantiated.
2686 CACHE is the cache of already instantiated values.
2688 FOLD_CONVERSIONS should be set to true when the conversions that
2689 may wrap in signed/pointer type are folded, as long as the value of
2690 the chrec is preserved.
2692 SIZE_EXPR is used for computing the size of the expression to be
2693 instantiated, and to stop if it exceeds some limit. */
2696 instantiate_scev_3 (basic_block instantiate_below
,
2697 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2699 bool fold_conversions
, int size_expr
)
2702 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2703 inner_loop
, TREE_OPERAND (chrec
, 0),
2704 fold_conversions
, size_expr
);
2705 if (op0
== chrec_dont_know
)
2706 return chrec_dont_know
;
2708 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2709 inner_loop
, TREE_OPERAND (chrec
, 1),
2710 fold_conversions
, size_expr
);
2711 if (op1
== chrec_dont_know
)
2712 return chrec_dont_know
;
2714 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2715 inner_loop
, TREE_OPERAND (chrec
, 2),
2716 fold_conversions
, size_expr
);
2717 if (op2
== chrec_dont_know
)
2718 return chrec_dont_know
;
2720 if (op0
== TREE_OPERAND (chrec
, 0)
2721 && op1
== TREE_OPERAND (chrec
, 1)
2722 && op2
== TREE_OPERAND (chrec
, 2))
2725 return fold_build3 (TREE_CODE (chrec
),
2726 TREE_TYPE (chrec
), op0
, op1
, op2
);
2729 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2730 and EVOLUTION_LOOP, that were left under a symbolic form.
2732 CHREC is an expression with 2 operands to be instantiated.
2734 CACHE is the cache of already instantiated values.
2736 FOLD_CONVERSIONS should be set to true when the conversions that
2737 may wrap in signed/pointer type are folded, as long as the value of
2738 the chrec is preserved.
2740 SIZE_EXPR is used for computing the size of the expression to be
2741 instantiated, and to stop if it exceeds some limit. */
2744 instantiate_scev_2 (basic_block instantiate_below
,
2745 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2747 bool fold_conversions
, int size_expr
)
2750 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2751 inner_loop
, TREE_OPERAND (chrec
, 0),
2752 fold_conversions
, size_expr
);
2753 if (op0
== chrec_dont_know
)
2754 return chrec_dont_know
;
2756 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2757 inner_loop
, TREE_OPERAND (chrec
, 1),
2758 fold_conversions
, size_expr
);
2759 if (op1
== chrec_dont_know
)
2760 return chrec_dont_know
;
2762 if (op0
== TREE_OPERAND (chrec
, 0)
2763 && op1
== TREE_OPERAND (chrec
, 1))
2766 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2769 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2770 and EVOLUTION_LOOP, that were left under a symbolic form.
2772 CHREC is an expression with 2 operands to be instantiated.
2774 CACHE is the cache of already instantiated values.
2776 FOLD_CONVERSIONS should be set to true when the conversions that
2777 may wrap in signed/pointer type are folded, as long as the value of
2778 the chrec is preserved.
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_1 (basic_block instantiate_below
,
2785 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2787 bool fold_conversions
, int size_expr
)
2789 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2790 inner_loop
, TREE_OPERAND (chrec
, 0),
2791 fold_conversions
, size_expr
);
2793 if (op0
== chrec_dont_know
)
2794 return chrec_dont_know
;
2796 if (op0
== TREE_OPERAND (chrec
, 0))
2799 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2802 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2803 and EVOLUTION_LOOP, that were left under a symbolic form.
2805 CHREC is the scalar evolution to instantiate.
2807 CACHE is the cache of already instantiated values.
2809 FOLD_CONVERSIONS should be set to true when the conversions that
2810 may wrap in signed/pointer type are folded, as long as the value of
2811 the chrec is preserved.
2813 SIZE_EXPR is used for computing the size of the expression to be
2814 instantiated, and to stop if it exceeds some limit. */
2817 instantiate_scev_r (basic_block instantiate_below
,
2818 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2820 bool fold_conversions
, int size_expr
)
2822 /* Give up if the expression is larger than the MAX that we allow. */
2823 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2824 return chrec_dont_know
;
2826 if (chrec
== NULL_TREE
2827 || automatically_generated_chrec_p (chrec
)
2828 || is_gimple_min_invariant (chrec
))
2831 switch (TREE_CODE (chrec
))
2834 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2836 fold_conversions
, size_expr
);
2838 case POLYNOMIAL_CHREC
:
2839 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2841 fold_conversions
, size_expr
);
2843 case POINTER_PLUS_EXPR
:
2847 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2849 TREE_CODE (chrec
), chrec_type (chrec
),
2850 TREE_OPERAND (chrec
, 0),
2851 TREE_OPERAND (chrec
, 1),
2852 fold_conversions
, size_expr
);
2855 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2857 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2858 fold_conversions
, size_expr
);
2862 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2864 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2865 TREE_OPERAND (chrec
, 0),
2866 fold_conversions
, size_expr
);
2869 case SCEV_NOT_KNOWN
:
2870 return chrec_dont_know
;
2876 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2878 fold_conversions
, size_expr
);
2884 if (VL_EXP_CLASS_P (chrec
))
2885 return chrec_dont_know
;
2887 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2890 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2892 fold_conversions
, size_expr
);
2895 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2897 fold_conversions
, size_expr
);
2900 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2902 fold_conversions
, size_expr
);
2911 /* Too complicated to handle. */
2912 return chrec_dont_know
;
2915 /* Analyze all the parameters of the chrec that were left under a
2916 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2917 recursive instantiation of parameters: a parameter is a variable
2918 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2919 a function parameter. */
2922 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2927 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2929 fprintf (dump_file
, "(instantiate_scev \n");
2930 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2931 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2932 fprintf (dump_file
, " (chrec = ");
2933 print_generic_expr (dump_file
, chrec
, 0);
2934 fprintf (dump_file
, ")\n");
2940 global_cache
= new instantiate_cache_type
;
2944 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2945 NULL
, chrec
, false, 0);
2949 delete global_cache
;
2950 global_cache
= NULL
;
2953 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2955 fprintf (dump_file
, " (res = ");
2956 print_generic_expr (dump_file
, res
, 0);
2957 fprintf (dump_file
, "))\n");
2963 /* Similar to instantiate_parameters, but does not introduce the
2964 evolutions in outer loops for LOOP invariants in CHREC, and does not
2965 care about causing overflows, as long as they do not affect value
2966 of an expression. */
2969 resolve_mixers (struct loop
*loop
, tree chrec
)
2974 global_cache
= new instantiate_cache_type
;
2978 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2983 delete global_cache
;
2984 global_cache
= NULL
;
2990 /* Entry point for the analysis of the number of iterations pass.
2991 This function tries to safely approximate the number of iterations
2992 the loop will run. When this property is not decidable at compile
2993 time, the result is chrec_dont_know. Otherwise the result is a
2994 scalar or a symbolic parameter. When the number of iterations may
2995 be equal to zero and the property cannot be determined at compile
2996 time, the result is a COND_EXPR that represents in a symbolic form
2997 the conditions under which the number of iterations is not zero.
2999 Example of analysis: suppose that the loop has an exit condition:
3001 "if (b > 49) goto end_loop;"
3003 and that in a previous analysis we have determined that the
3004 variable 'b' has an evolution function:
3006 "EF = {23, +, 5}_2".
3008 When we evaluate the function at the point 5, i.e. the value of the
3009 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
3010 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
3011 the loop body has been executed 6 times. */
3014 number_of_latch_executions (struct loop
*loop
)
3017 struct tree_niter_desc niter_desc
;
3021 /* Determine whether the number of iterations in loop has already
3023 res
= loop
->nb_iterations
;
3027 may_be_zero
= NULL_TREE
;
3029 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3030 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
3032 res
= chrec_dont_know
;
3033 exit
= single_exit (loop
);
3035 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
3037 may_be_zero
= niter_desc
.may_be_zero
;
3038 res
= niter_desc
.niter
;
3041 if (res
== chrec_dont_know
3043 || integer_zerop (may_be_zero
))
3045 else if (integer_nonzerop (may_be_zero
))
3046 res
= build_int_cst (TREE_TYPE (res
), 0);
3048 else if (COMPARISON_CLASS_P (may_be_zero
))
3049 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
3050 build_int_cst (TREE_TYPE (res
), 0), res
);
3052 res
= chrec_dont_know
;
3054 if (dump_file
&& (dump_flags
& TDF_SCEV
))
3056 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
3057 print_generic_expr (dump_file
, res
, 0);
3058 fprintf (dump_file
, "))\n");
3061 loop
->nb_iterations
= res
;
3066 /* Counters for the stats. */
3072 unsigned nb_affine_multivar
;
3073 unsigned nb_higher_poly
;
3074 unsigned nb_chrec_dont_know
;
3075 unsigned nb_undetermined
;
3078 /* Reset the counters. */
3081 reset_chrecs_counters (struct chrec_stats
*stats
)
3083 stats
->nb_chrecs
= 0;
3084 stats
->nb_affine
= 0;
3085 stats
->nb_affine_multivar
= 0;
3086 stats
->nb_higher_poly
= 0;
3087 stats
->nb_chrec_dont_know
= 0;
3088 stats
->nb_undetermined
= 0;
3091 /* Dump the contents of a CHREC_STATS structure. */
3094 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
3096 fprintf (file
, "\n(\n");
3097 fprintf (file
, "-----------------------------------------\n");
3098 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
3099 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
3100 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
3101 stats
->nb_higher_poly
);
3102 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
3103 fprintf (file
, "-----------------------------------------\n");
3104 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
3105 fprintf (file
, "%d\twith undetermined coefficients\n",
3106 stats
->nb_undetermined
);
3107 fprintf (file
, "-----------------------------------------\n");
3108 fprintf (file
, "%d\tchrecs in the scev database\n",
3109 (int) scalar_evolution_info
->elements ());
3110 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
3111 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
3112 fprintf (file
, "-----------------------------------------\n");
3113 fprintf (file
, ")\n\n");
3116 /* Gather statistics about CHREC. */
3119 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
3121 if (dump_file
&& (dump_flags
& TDF_STATS
))
3123 fprintf (dump_file
, "(classify_chrec ");
3124 print_generic_expr (dump_file
, chrec
, 0);
3125 fprintf (dump_file
, "\n");
3130 if (chrec
== NULL_TREE
)
3132 stats
->nb_undetermined
++;
3136 switch (TREE_CODE (chrec
))
3138 case POLYNOMIAL_CHREC
:
3139 if (evolution_function_is_affine_p (chrec
))
3141 if (dump_file
&& (dump_flags
& TDF_STATS
))
3142 fprintf (dump_file
, " affine_univariate\n");
3145 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3147 if (dump_file
&& (dump_flags
& TDF_STATS
))
3148 fprintf (dump_file
, " affine_multivariate\n");
3149 stats
->nb_affine_multivar
++;
3153 if (dump_file
&& (dump_flags
& TDF_STATS
))
3154 fprintf (dump_file
, " higher_degree_polynomial\n");
3155 stats
->nb_higher_poly
++;
3164 if (chrec_contains_undetermined (chrec
))
3166 if (dump_file
&& (dump_flags
& TDF_STATS
))
3167 fprintf (dump_file
, " undetermined\n");
3168 stats
->nb_undetermined
++;
3171 if (dump_file
&& (dump_flags
& TDF_STATS
))
3172 fprintf (dump_file
, ")\n");
3175 /* Classify the chrecs of the whole database. */
3178 gather_stats_on_scev_database (void)
3180 struct chrec_stats stats
;
3185 reset_chrecs_counters (&stats
);
3187 hash_table
<scev_info_hasher
>::iterator iter
;
3189 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info
, elt
, scev_info_str
*,
3191 gather_chrec_stats (elt
->chrec
, &stats
);
3193 dump_chrecs_stats (dump_file
, &stats
);
3201 initialize_scalar_evolutions_analyzer (void)
3203 /* The elements below are unique. */
3204 if (chrec_dont_know
== NULL_TREE
)
3206 chrec_not_analyzed_yet
= NULL_TREE
;
3207 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3208 chrec_known
= make_node (SCEV_KNOWN
);
3209 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3210 TREE_TYPE (chrec_known
) = void_type_node
;
3214 /* Initialize the analysis of scalar evolutions for LOOPS. */
3217 scev_initialize (void)
3221 scalar_evolution_info
= hash_table
<scev_info_hasher
>::create_ggc (100);
3223 initialize_scalar_evolutions_analyzer ();
3225 FOR_EACH_LOOP (loop
, 0)
3227 loop
->nb_iterations
= NULL_TREE
;
3231 /* Return true if SCEV is initialized. */
3234 scev_initialized_p (void)
3236 return scalar_evolution_info
!= NULL
;
3239 /* Cleans up the information cached by the scalar evolutions analysis
3240 in the hash table. */
3243 scev_reset_htab (void)
3245 if (!scalar_evolution_info
)
3248 scalar_evolution_info
->empty ();
3251 /* Cleans up the information cached by the scalar evolutions analysis
3252 in the hash table and in the loop->nb_iterations. */
3261 FOR_EACH_LOOP (loop
, 0)
3263 loop
->nb_iterations
= NULL_TREE
;
3267 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3268 respect to WRTO_LOOP and returns its base and step in IV if possible
3269 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3270 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3271 invariant in LOOP. Otherwise we require it to be an integer constant.
3273 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3274 because it is computed in signed arithmetics). Consequently, adding an
3277 for (i = IV->base; ; i += IV->step)
3279 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3280 false for the type of the induction variable, or you can prove that i does
3281 not wrap by some other argument. Otherwise, this might introduce undefined
3284 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3286 must be used instead. */
3289 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3290 affine_iv
*iv
, bool allow_nonconstant_step
)
3295 iv
->base
= NULL_TREE
;
3296 iv
->step
= NULL_TREE
;
3297 iv
->no_overflow
= false;
3299 type
= TREE_TYPE (op
);
3300 if (!POINTER_TYPE_P (type
)
3301 && !INTEGRAL_TYPE_P (type
))
3304 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3306 if (chrec_contains_undetermined (ev
)
3307 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3310 if (tree_does_not_contain_chrecs (ev
))
3313 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3314 iv
->no_overflow
= true;
3318 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3319 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3322 iv
->step
= CHREC_RIGHT (ev
);
3323 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3324 || tree_contains_chrecs (iv
->step
, NULL
))
3327 iv
->base
= CHREC_LEFT (ev
);
3328 if (tree_contains_chrecs (iv
->base
, NULL
))
3331 iv
->no_overflow
= (!folded_casts
&& ANY_INTEGRAL_TYPE_P (type
)
3332 && TYPE_OVERFLOW_UNDEFINED (type
));
3337 /* Finalize the scalar evolution analysis. */
3340 scev_finalize (void)
3342 if (!scalar_evolution_info
)
3344 scalar_evolution_info
->empty ();
3345 scalar_evolution_info
= NULL
;
3348 /* Returns true if the expression EXPR is considered to be too expensive
3349 for scev_const_prop. */
3352 expression_expensive_p (tree expr
)
3354 enum tree_code code
;
3356 if (is_gimple_val (expr
))
3359 code
= TREE_CODE (expr
);
3360 if (code
== TRUNC_DIV_EXPR
3361 || code
== CEIL_DIV_EXPR
3362 || code
== FLOOR_DIV_EXPR
3363 || code
== ROUND_DIV_EXPR
3364 || code
== TRUNC_MOD_EXPR
3365 || code
== CEIL_MOD_EXPR
3366 || code
== FLOOR_MOD_EXPR
3367 || code
== ROUND_MOD_EXPR
3368 || code
== EXACT_DIV_EXPR
)
3370 /* Division by power of two is usually cheap, so we allow it.
3371 Forbid anything else. */
3372 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3376 switch (TREE_CODE_CLASS (code
))
3379 case tcc_comparison
:
3380 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3385 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3392 /* Replace ssa names for that scev can prove they are constant by the
3393 appropriate constants. Also perform final value replacement in loops,
3394 in case the replacement expressions are cheap.
3396 We only consider SSA names defined by phi nodes; rest is left to the
3397 ordinary constant propagation pass. */
3400 scev_const_prop (void)
3403 tree name
, type
, ev
;
3406 struct loop
*loop
, *ex_loop
;
3407 bitmap ssa_names_to_remove
= NULL
;
3411 if (number_of_loops (cfun
) <= 1)
3414 FOR_EACH_BB_FN (bb
, cfun
)
3416 loop
= bb
->loop_father
;
3418 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3421 name
= PHI_RESULT (phi
);
3423 if (virtual_operand_p (name
))
3426 type
= TREE_TYPE (name
);
3428 if (!POINTER_TYPE_P (type
)
3429 && !INTEGRAL_TYPE_P (type
))
3432 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3433 if (!is_gimple_min_invariant (ev
)
3434 || !may_propagate_copy (name
, ev
))
3437 /* Replace the uses of the name. */
3439 replace_uses_by (name
, ev
);
3441 if (!ssa_names_to_remove
)
3442 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3443 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3447 /* Remove the ssa names that were replaced by constants. We do not
3448 remove them directly in the previous cycle, since this
3449 invalidates scev cache. */
3450 if (ssa_names_to_remove
)
3454 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3456 gimple_stmt_iterator psi
;
3457 name
= ssa_name (i
);
3458 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (name
));
3460 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3461 psi
= gsi_for_stmt (phi
);
3462 remove_phi_node (&psi
, true);
3465 BITMAP_FREE (ssa_names_to_remove
);
3469 /* Now the regular final value replacement. */
3470 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3473 tree def
, rslt
, niter
;
3474 gimple_stmt_iterator gsi
;
3476 /* If we do not know exact number of iterations of the loop, we cannot
3477 replace the final value. */
3478 exit
= single_exit (loop
);
3482 niter
= number_of_latch_executions (loop
);
3483 if (niter
== chrec_dont_know
)
3486 /* Ensure that it is possible to insert new statements somewhere. */
3487 if (!single_pred_p (exit
->dest
))
3488 split_loop_exit_edge (exit
);
3489 gsi
= gsi_after_labels (exit
->dest
);
3491 ex_loop
= superloop_at_depth (loop
,
3492 loop_depth (exit
->dest
->loop_father
) + 1);
3494 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3497 rslt
= PHI_RESULT (phi
);
3498 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3499 if (virtual_operand_p (def
))
3505 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3506 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3513 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
,
3515 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3516 if (!tree_does_not_contain_chrecs (def
)
3517 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3518 /* Moving the computation from the loop may prolong life range
3519 of some ssa names, which may cause problems if they appear
3520 on abnormal edges. */
3521 || contains_abnormal_ssa_name_p (def
)
3522 /* Do not emit expensive expressions. The rationale is that
3523 when someone writes a code like
3525 while (n > 45) n -= 45;
3527 he probably knows that n is not large, and does not want it
3528 to be turned into n %= 45. */
3529 || expression_expensive_p (def
))
3531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3533 fprintf (dump_file
, "not replacing:\n ");
3534 print_gimple_stmt (dump_file
, phi
, 0, 0);
3535 fprintf (dump_file
, "\n");
3541 /* Eliminate the PHI node and replace it by a computation outside
3545 fprintf (dump_file
, "\nfinal value replacement:\n ");
3546 print_gimple_stmt (dump_file
, phi
, 0, 0);
3547 fprintf (dump_file
, " with\n ");
3549 def
= unshare_expr (def
);
3550 remove_phi_node (&psi
, false);
3552 /* If def's type has undefined overflow and there were folded
3553 casts, rewrite all stmts added for def into arithmetics
3554 with defined overflow behavior. */
3555 if (folded_casts
&& ANY_INTEGRAL_TYPE_P (TREE_TYPE (def
))
3556 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def
)))
3559 gimple_stmt_iterator gsi2
;
3560 def
= force_gimple_operand (def
, &stmts
, true, NULL_TREE
);
3561 gsi2
= gsi_start (stmts
);
3562 while (!gsi_end_p (gsi2
))
3564 gimple stmt
= gsi_stmt (gsi2
);
3565 gimple_stmt_iterator gsi3
= gsi2
;
3567 gsi_remove (&gsi3
, false);
3568 if (is_gimple_assign (stmt
)
3569 && arith_code_with_undefined_signed_overflow
3570 (gimple_assign_rhs_code (stmt
)))
3571 gsi_insert_seq_before (&gsi
,
3572 rewrite_to_defined_overflow (stmt
),
3575 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3579 def
= force_gimple_operand_gsi (&gsi
, def
, false, NULL_TREE
,
3580 true, GSI_SAME_STMT
);
3582 ass
= gimple_build_assign (rslt
, def
);
3583 gsi_insert_before (&gsi
, ass
, GSI_SAME_STMT
);
3586 print_gimple_stmt (dump_file
, ass
, 0, 0);
3587 fprintf (dump_file
, "\n");
3594 #include "gt-tree-scalar-evolution.h"