1 /* Scalar evolution detector.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
50 - When the definition is a GIMPLE_ASSIGN: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
75 Example 1: Illustration of the basic algorithm.
81 | if (c > 10) exit_loop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
119 or in terms of a C program:
122 | for (x = 0; x <= 7; x++)
128 Example 2a: Illustration of the algorithm on nested loops.
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
157 Example 2b: Multivariate chains of recurrences.
170 Analyzing the access function of array A with
171 instantiate_parameters (loop_1, "j + k"), we obtain the
172 instantiation and the analysis of the scalar variables "j" and "k"
173 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175 {0, +, 1}_1. To obtain the evolution function in loop_3 and
176 instantiate the scalar variables up to loop_1, one has to use:
177 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178 The result of this call is {{0, +, 1}_1, +, 1}_2.
180 Example 3: Higher degree polynomials.
194 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197 Example 4: Lucas, Fibonacci, or mixers in general.
209 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210 following semantics: during the first iteration of the loop_1, the
211 variable contains the value 1, and then it contains the value "c".
212 Note that this syntax is close to the syntax of the loop-phi-node:
213 "a -> (1, c)_1" vs. "a = phi (1, c)".
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
218 Example 5: Flip-flops, or exchangers.
230 Based on these symbolic chrecs, it is possible to refine this
231 information into the more precise PERIODIC_CHRECs:
236 This transformation is not yet implemented.
240 You can find a more detailed description of the algorithm in:
241 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243 this is a preliminary report and some of the details of the
244 algorithm have changed. I'm working on a research report that
245 updates the description of the algorithms to reflect the design
246 choices used in this implementation.
248 A set of slides show a high level overview of the algorithm and run
249 an example through the scalar evolution analyzer:
250 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252 The slides that I have presented at the GCC Summit'04 are available
253 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
258 #include "coretypes.h"
261 #include "gimple-pretty-print.h"
262 #include "basic-block.h"
263 #include "tree-ssa-alias.h"
264 #include "internal-fn.h"
265 #include "gimple-expr.h"
268 #include "gimplify.h"
269 #include "gimple-iterator.h"
270 #include "gimplify-me.h"
271 #include "gimple-ssa.h"
272 #include "tree-cfg.h"
273 #include "tree-phinodes.h"
274 #include "stringpool.h"
275 #include "tree-ssanames.h"
276 #include "tree-ssa-loop-ivopts.h"
277 #include "tree-ssa-loop-manip.h"
278 #include "tree-ssa-loop-niter.h"
279 #include "tree-ssa-loop.h"
280 #include "tree-ssa.h"
282 #include "tree-chrec.h"
283 #include "pointer-set.h"
284 #include "tree-affine.h"
285 #include "tree-scalar-evolution.h"
286 #include "dumpfile.h"
288 #include "tree-ssa-propagate.h"
290 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
291 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
294 /* The cached information about an SSA name with version NAME_VERSION,
295 claiming that below basic block with index INSTANTIATED_BELOW, the
296 value of the SSA name can be expressed as CHREC. */
298 struct GTY(()) scev_info_str
{
299 unsigned int name_version
;
300 int instantiated_below
;
304 /* Counters for the scev database. */
305 static unsigned nb_set_scev
= 0;
306 static unsigned nb_get_scev
= 0;
308 /* The following trees are unique elements. Thus the comparison of
309 another element to these elements should be done on the pointer to
310 these trees, and not on their value. */
312 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
313 tree chrec_not_analyzed_yet
;
315 /* Reserved to the cases where the analyzer has detected an
316 undecidable property at compile time. */
317 tree chrec_dont_know
;
319 /* When the analyzer has detected that a property will never
320 happen, then it qualifies it with chrec_known. */
323 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
326 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
328 static inline struct scev_info_str
*
329 new_scev_info_str (basic_block instantiated_below
, tree var
)
331 struct scev_info_str
*res
;
333 res
= ggc_alloc_scev_info_str ();
334 res
->name_version
= SSA_NAME_VERSION (var
);
335 res
->chrec
= chrec_not_analyzed_yet
;
336 res
->instantiated_below
= instantiated_below
->index
;
341 /* Computes a hash function for database element ELT. */
343 static inline hashval_t
344 hash_scev_info (const void *elt_
)
346 const struct scev_info_str
*elt
= (const struct scev_info_str
*) elt_
;
347 return elt
->name_version
^ elt
->instantiated_below
;
350 /* Compares database elements E1 and E2. */
353 eq_scev_info (const void *e1
, const void *e2
)
355 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
356 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
358 return (elt1
->name_version
== elt2
->name_version
359 && elt1
->instantiated_below
== elt2
->instantiated_below
);
362 /* Deletes database element E. */
365 del_scev_info (void *e
)
371 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
372 A first query on VAR returns chrec_not_analyzed_yet. */
375 find_var_scev_info (basic_block instantiated_below
, tree var
)
377 struct scev_info_str
*res
;
378 struct scev_info_str tmp
;
381 tmp
.name_version
= SSA_NAME_VERSION (var
);
382 tmp
.instantiated_below
= instantiated_below
->index
;
383 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
386 *slot
= new_scev_info_str (instantiated_below
, var
);
387 res
= (struct scev_info_str
*) *slot
;
392 /* Return true when CHREC contains symbolic names defined in
396 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
400 if (chrec
== NULL_TREE
)
403 if (is_gimple_min_invariant (chrec
))
406 if (TREE_CODE (chrec
) == SSA_NAME
)
409 loop_p def_loop
, loop
;
411 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
414 def
= SSA_NAME_DEF_STMT (chrec
);
415 def_loop
= loop_containing_stmt (def
);
416 loop
= get_loop (cfun
, loop_nb
);
418 if (def_loop
== NULL
)
421 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
427 n
= TREE_OPERAND_LENGTH (chrec
);
428 for (i
= 0; i
< n
; i
++)
429 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
435 /* Return true when PHI is a loop-phi-node. */
438 loop_phi_node_p (gimple phi
)
440 /* The implementation of this function is based on the following
441 property: "all the loop-phi-nodes of a loop are contained in the
442 loop's header basic block". */
444 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
447 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
448 In general, in the case of multivariate evolutions we want to get
449 the evolution in different loops. LOOP specifies the level for
450 which to get the evolution.
454 | for (j = 0; j < 100; j++)
456 | for (k = 0; k < 100; k++)
458 | i = k + j; - Here the value of i is a function of j, k.
460 | ... = i - Here the value of i is a function of j.
462 | ... = i - Here the value of i is a scalar.
468 | i_1 = phi (i_0, i_2)
472 This loop has the same effect as:
473 LOOP_1 has the same effect as:
477 The overall effect of the loop, "i_0 + 20" in the previous example,
478 is obtained by passing in the parameters: LOOP = 1,
479 EVOLUTION_FN = {i_0, +, 2}_1.
483 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
487 if (evolution_fn
== chrec_dont_know
)
488 return chrec_dont_know
;
490 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
492 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
494 if (inner_loop
== loop
495 || flow_loop_nested_p (loop
, inner_loop
))
497 tree nb_iter
= number_of_latch_executions (inner_loop
);
499 if (nb_iter
== chrec_dont_know
)
500 return chrec_dont_know
;
505 /* evolution_fn is the evolution function in LOOP. Get
506 its value in the nb_iter-th iteration. */
507 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
509 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
510 res
= instantiate_parameters (loop
, res
);
512 /* Continue the computation until ending on a parent of LOOP. */
513 return compute_overall_effect_of_inner_loop (loop
, res
);
520 /* If the evolution function is an invariant, there is nothing to do. */
521 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
525 return chrec_dont_know
;
528 /* Associate CHREC to SCALAR. */
531 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
535 if (TREE_CODE (scalar
) != SSA_NAME
)
538 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
542 if (dump_flags
& TDF_SCEV
)
544 fprintf (dump_file
, "(set_scalar_evolution \n");
545 fprintf (dump_file
, " instantiated_below = %d \n",
546 instantiated_below
->index
);
547 fprintf (dump_file
, " (scalar = ");
548 print_generic_expr (dump_file
, scalar
, 0);
549 fprintf (dump_file
, ")\n (scalar_evolution = ");
550 print_generic_expr (dump_file
, chrec
, 0);
551 fprintf (dump_file
, "))\n");
553 if (dump_flags
& TDF_STATS
)
557 *scalar_info
= chrec
;
560 /* Retrieve the chrec associated to SCALAR instantiated below
561 INSTANTIATED_BELOW block. */
564 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
570 if (dump_flags
& TDF_SCEV
)
572 fprintf (dump_file
, "(get_scalar_evolution \n");
573 fprintf (dump_file
, " (scalar = ");
574 print_generic_expr (dump_file
, scalar
, 0);
575 fprintf (dump_file
, ")\n");
577 if (dump_flags
& TDF_STATS
)
581 switch (TREE_CODE (scalar
))
584 res
= *find_var_scev_info (instantiated_below
, scalar
);
594 res
= chrec_not_analyzed_yet
;
598 if (dump_file
&& (dump_flags
& TDF_SCEV
))
600 fprintf (dump_file
, " (scalar_evolution = ");
601 print_generic_expr (dump_file
, res
, 0);
602 fprintf (dump_file
, "))\n");
608 /* Helper function for add_to_evolution. Returns the evolution
609 function for an assignment of the form "a = b + c", where "a" and
610 "b" are on the strongly connected component. CHREC_BEFORE is the
611 information that we already have collected up to this point.
612 TO_ADD is the evolution of "c".
614 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
615 evolution the expression TO_ADD, otherwise construct an evolution
616 part for this loop. */
619 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
622 tree type
, left
, right
;
623 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
625 switch (TREE_CODE (chrec_before
))
627 case POLYNOMIAL_CHREC
:
628 chloop
= get_chrec_loop (chrec_before
);
630 || flow_loop_nested_p (chloop
, loop
))
634 type
= chrec_type (chrec_before
);
636 /* When there is no evolution part in this loop, build it. */
641 right
= SCALAR_FLOAT_TYPE_P (type
)
642 ? build_real (type
, dconst0
)
643 : build_int_cst (type
, 0);
647 var
= CHREC_VARIABLE (chrec_before
);
648 left
= CHREC_LEFT (chrec_before
);
649 right
= CHREC_RIGHT (chrec_before
);
652 to_add
= chrec_convert (type
, to_add
, at_stmt
);
653 right
= chrec_convert_rhs (type
, right
, at_stmt
);
654 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
655 return build_polynomial_chrec (var
, left
, right
);
659 gcc_assert (flow_loop_nested_p (loop
, chloop
));
661 /* Search the evolution in LOOP_NB. */
662 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
664 right
= CHREC_RIGHT (chrec_before
);
665 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
666 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
671 /* These nodes do not depend on a loop. */
672 if (chrec_before
== chrec_dont_know
)
673 return chrec_dont_know
;
676 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
677 return build_polynomial_chrec (loop_nb
, left
, right
);
681 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
684 Description (provided for completeness, for those who read code in
685 a plane, and for my poor 62 bytes brain that would have forgotten
686 all this in the next two or three months):
688 The algorithm of translation of programs from the SSA representation
689 into the chrecs syntax is based on a pattern matching. After having
690 reconstructed the overall tree expression for a loop, there are only
691 two cases that can arise:
693 1. a = loop-phi (init, a + expr)
694 2. a = loop-phi (init, expr)
696 where EXPR is either a scalar constant with respect to the analyzed
697 loop (this is a degree 0 polynomial), or an expression containing
698 other loop-phi definitions (these are higher degree polynomials).
705 | a = phi (init, a + 5)
712 | a = phi (inita, 2 * b + 3)
713 | b = phi (initb, b + 1)
716 For the first case, the semantics of the SSA representation is:
718 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
720 that is, there is a loop index "x" that determines the scalar value
721 of the variable during the loop execution. During the first
722 iteration, the value is that of the initial condition INIT, while
723 during the subsequent iterations, it is the sum of the initial
724 condition with the sum of all the values of EXPR from the initial
725 iteration to the before last considered iteration.
727 For the second case, the semantics of the SSA program is:
729 | a (x) = init, if x = 0;
730 | expr (x - 1), otherwise.
732 The second case corresponds to the PEELED_CHREC, whose syntax is
733 close to the syntax of a loop-phi-node:
735 | phi (init, expr) vs. (init, expr)_x
737 The proof of the translation algorithm for the first case is a
738 proof by structural induction based on the degree of EXPR.
741 When EXPR is a constant with respect to the analyzed loop, or in
742 other words when EXPR is a polynomial of degree 0, the evolution of
743 the variable A in the loop is an affine function with an initial
744 condition INIT, and a step EXPR. In order to show this, we start
745 from the semantics of the SSA representation:
747 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
749 and since "expr (j)" is a constant with respect to "j",
751 f (x) = init + x * expr
753 Finally, based on the semantics of the pure sum chrecs, by
754 identification we get the corresponding chrecs syntax:
756 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
757 f (x) -> {init, +, expr}_x
760 Suppose that EXPR is a polynomial of degree N with respect to the
761 analyzed loop_x for which we have already determined that it is
762 written under the chrecs syntax:
764 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
766 We start from the semantics of the SSA program:
768 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
770 | f (x) = init + \sum_{j = 0}^{x - 1}
771 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
773 | f (x) = init + \sum_{j = 0}^{x - 1}
774 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
776 | f (x) = init + \sum_{k = 0}^{n - 1}
777 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
779 | f (x) = init + \sum_{k = 0}^{n - 1}
780 | (b_k * \binom{x}{k + 1})
782 | f (x) = init + b_0 * \binom{x}{1} + ...
783 | + b_{n-1} * \binom{x}{n}
785 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
786 | + b_{n-1} * \binom{x}{n}
789 And finally from the definition of the chrecs syntax, we identify:
790 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
792 This shows the mechanism that stands behind the add_to_evolution
793 function. An important point is that the use of symbolic
794 parameters avoids the need of an analysis schedule.
801 | a = phi (inita, a + 2 + b)
802 | b = phi (initb, b + 1)
805 When analyzing "a", the algorithm keeps "b" symbolically:
807 | a -> {inita, +, 2 + b}_1
809 Then, after instantiation, the analyzer ends on the evolution:
811 | a -> {inita, +, 2 + initb, +, 1}_1
816 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
817 tree to_add
, gimple at_stmt
)
819 tree type
= chrec_type (to_add
);
820 tree res
= NULL_TREE
;
822 if (to_add
== NULL_TREE
)
825 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
826 instantiated at this point. */
827 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
828 /* This should not happen. */
829 return chrec_dont_know
;
831 if (dump_file
&& (dump_flags
& TDF_SCEV
))
833 fprintf (dump_file
, "(add_to_evolution \n");
834 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
835 fprintf (dump_file
, " (chrec_before = ");
836 print_generic_expr (dump_file
, chrec_before
, 0);
837 fprintf (dump_file
, ")\n (to_add = ");
838 print_generic_expr (dump_file
, to_add
, 0);
839 fprintf (dump_file
, ")\n");
842 if (code
== MINUS_EXPR
)
843 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
844 ? build_real (type
, dconstm1
)
845 : build_int_cst_type (type
, -1));
847 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
849 if (dump_file
&& (dump_flags
& TDF_SCEV
))
851 fprintf (dump_file
, " (res = ");
852 print_generic_expr (dump_file
, res
, 0);
853 fprintf (dump_file
, "))\n");
861 /* This section selects the loops that will be good candidates for the
862 scalar evolution analysis. For the moment, greedily select all the
863 loop nests we could analyze. */
865 /* For a loop with a single exit edge, return the COND_EXPR that
866 guards the exit edge. If the expression is too difficult to
867 analyze, then give up. */
870 get_loop_exit_condition (const struct loop
*loop
)
873 edge exit_edge
= single_exit (loop
);
875 if (dump_file
&& (dump_flags
& TDF_SCEV
))
876 fprintf (dump_file
, "(get_loop_exit_condition \n ");
882 stmt
= last_stmt (exit_edge
->src
);
883 if (gimple_code (stmt
) == GIMPLE_COND
)
887 if (dump_file
&& (dump_flags
& TDF_SCEV
))
889 print_gimple_stmt (dump_file
, res
, 0, 0);
890 fprintf (dump_file
, ")\n");
897 /* Depth first search algorithm. */
899 typedef enum t_bool
{
906 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
908 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
909 Return true if the strongly connected component has been found. */
912 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
913 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
914 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
916 t_bool res
= t_false
;
921 case POINTER_PLUS_EXPR
:
923 if (TREE_CODE (rhs0
) == SSA_NAME
)
925 if (TREE_CODE (rhs1
) == SSA_NAME
)
927 /* Match an assignment under the form:
930 /* We want only assignments of form "name + name" contribute to
931 LIMIT, as the other cases do not necessarily contribute to
932 the complexity of the expression. */
935 evol
= *evolution_of_loop
;
936 res
= follow_ssa_edge
937 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
940 *evolution_of_loop
= add_to_evolution
942 chrec_convert (type
, evol
, at_stmt
),
943 code
, rhs1
, at_stmt
);
945 else if (res
== t_false
)
947 res
= follow_ssa_edge
948 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
949 evolution_of_loop
, limit
);
952 *evolution_of_loop
= add_to_evolution
954 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
955 code
, rhs0
, at_stmt
);
957 else if (res
== t_dont_know
)
958 *evolution_of_loop
= chrec_dont_know
;
961 else if (res
== t_dont_know
)
962 *evolution_of_loop
= chrec_dont_know
;
967 /* Match an assignment under the form:
969 res
= follow_ssa_edge
970 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
971 evolution_of_loop
, limit
);
973 *evolution_of_loop
= add_to_evolution
974 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
976 code
, rhs1
, at_stmt
);
978 else if (res
== t_dont_know
)
979 *evolution_of_loop
= chrec_dont_know
;
983 else if (TREE_CODE (rhs1
) == SSA_NAME
)
985 /* Match an assignment under the form:
987 res
= follow_ssa_edge
988 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
989 evolution_of_loop
, limit
);
991 *evolution_of_loop
= add_to_evolution
992 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
994 code
, rhs0
, at_stmt
);
996 else if (res
== t_dont_know
)
997 *evolution_of_loop
= chrec_dont_know
;
1001 /* Otherwise, match an assignment under the form:
1003 /* And there is nothing to do. */
1008 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1009 if (TREE_CODE (rhs0
) == SSA_NAME
)
1011 /* Match an assignment under the form:
1014 /* We want only assignments of form "name - name" contribute to
1015 LIMIT, as the other cases do not necessarily contribute to
1016 the complexity of the expression. */
1017 if (TREE_CODE (rhs1
) == SSA_NAME
)
1020 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1021 evolution_of_loop
, limit
);
1023 *evolution_of_loop
= add_to_evolution
1024 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1025 MINUS_EXPR
, rhs1
, at_stmt
);
1027 else if (res
== t_dont_know
)
1028 *evolution_of_loop
= chrec_dont_know
;
1031 /* Otherwise, match an assignment under the form:
1033 /* And there is nothing to do. */
1044 /* Follow the ssa edge into the expression EXPR.
1045 Return true if the strongly connected component has been found. */
1048 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1049 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1051 enum tree_code code
= TREE_CODE (expr
);
1052 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1055 /* The EXPR is one of the following cases:
1059 - a POINTER_PLUS_EXPR,
1062 - other cases are not yet handled. */
1067 /* This assignment is under the form "a_1 = (cast) rhs. */
1068 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1069 halting_phi
, evolution_of_loop
, limit
);
1070 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1074 /* This assignment is under the form "a_1 = 7". */
1079 /* This assignment is under the form: "a_1 = b_2". */
1080 res
= follow_ssa_edge
1081 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1084 case POINTER_PLUS_EXPR
:
1087 /* This case is under the form "rhs0 +- rhs1". */
1088 rhs0
= TREE_OPERAND (expr
, 0);
1089 rhs1
= TREE_OPERAND (expr
, 1);
1090 type
= TREE_TYPE (rhs0
);
1091 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1092 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1093 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1094 halting_phi
, evolution_of_loop
, limit
);
1098 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1099 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1101 expr
= TREE_OPERAND (expr
, 0);
1102 rhs0
= TREE_OPERAND (expr
, 0);
1103 rhs1
= TREE_OPERAND (expr
, 1);
1104 type
= TREE_TYPE (rhs0
);
1105 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1106 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1107 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1108 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1109 halting_phi
, evolution_of_loop
, limit
);
1116 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1117 It must be handled as a copy assignment of the form a_1 = a_2. */
1118 rhs0
= ASSERT_EXPR_VAR (expr
);
1119 if (TREE_CODE (rhs0
) == SSA_NAME
)
1120 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1121 halting_phi
, evolution_of_loop
, limit
);
1134 /* Follow the ssa edge into the right hand side of an assignment STMT.
1135 Return true if the strongly connected component has been found. */
1138 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1139 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1141 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1142 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1148 /* This assignment is under the form "a_1 = (cast) rhs. */
1149 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1150 halting_phi
, evolution_of_loop
, limit
);
1151 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1154 case POINTER_PLUS_EXPR
:
1157 rhs1
= gimple_assign_rhs1 (stmt
);
1158 rhs2
= gimple_assign_rhs2 (stmt
);
1159 type
= TREE_TYPE (rhs1
);
1160 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1161 halting_phi
, evolution_of_loop
, limit
);
1165 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1166 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1167 halting_phi
, evolution_of_loop
, limit
);
1176 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1179 backedge_phi_arg_p (gimple phi
, int i
)
1181 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1183 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1184 about updating it anywhere, and this should work as well most of the
1186 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1192 /* Helper function for one branch of the condition-phi-node. Return
1193 true if the strongly connected component has been found following
1196 static inline t_bool
1197 follow_ssa_edge_in_condition_phi_branch (int i
,
1199 gimple condition_phi
,
1201 tree
*evolution_of_branch
,
1202 tree init_cond
, int limit
)
1204 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1205 *evolution_of_branch
= chrec_dont_know
;
1207 /* Do not follow back edges (they must belong to an irreducible loop, which
1208 we really do not want to worry about). */
1209 if (backedge_phi_arg_p (condition_phi
, i
))
1212 if (TREE_CODE (branch
) == SSA_NAME
)
1214 *evolution_of_branch
= init_cond
;
1215 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1216 evolution_of_branch
, limit
);
1219 /* This case occurs when one of the condition branches sets
1220 the variable to a constant: i.e. a phi-node like
1221 "a_2 = PHI <a_7(5), 2(6)>;".
1223 FIXME: This case have to be refined correctly:
1224 in some cases it is possible to say something better than
1225 chrec_dont_know, for example using a wrap-around notation. */
1229 /* This function merges the branches of a condition-phi-node in a
1233 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1234 gimple condition_phi
,
1236 tree
*evolution_of_loop
, int limit
)
1239 tree init
= *evolution_of_loop
;
1240 tree evolution_of_branch
;
1241 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1243 &evolution_of_branch
,
1245 if (res
== t_false
|| res
== t_dont_know
)
1248 *evolution_of_loop
= evolution_of_branch
;
1250 n
= gimple_phi_num_args (condition_phi
);
1251 for (i
= 1; i
< n
; i
++)
1253 /* Quickly give up when the evolution of one of the branches is
1255 if (*evolution_of_loop
== chrec_dont_know
)
1258 /* Increase the limit by the PHI argument number to avoid exponential
1259 time and memory complexity. */
1260 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1262 &evolution_of_branch
,
1264 if (res
== t_false
|| res
== t_dont_know
)
1267 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1268 evolution_of_branch
);
1274 /* Follow an SSA edge in an inner loop. It computes the overall
1275 effect of the loop, and following the symbolic initial conditions,
1276 it follows the edges in the parent loop. The inner loop is
1277 considered as a single statement. */
1280 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1281 gimple loop_phi_node
,
1283 tree
*evolution_of_loop
, int limit
)
1285 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1286 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1288 /* Sometimes, the inner loop is too difficult to analyze, and the
1289 result of the analysis is a symbolic parameter. */
1290 if (ev
== PHI_RESULT (loop_phi_node
))
1292 t_bool res
= t_false
;
1293 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1295 for (i
= 0; i
< n
; i
++)
1297 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1300 /* Follow the edges that exit the inner loop. */
1301 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1302 if (!flow_bb_inside_loop_p (loop
, bb
))
1303 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1305 evolution_of_loop
, limit
);
1310 /* If the path crosses this loop-phi, give up. */
1312 *evolution_of_loop
= chrec_dont_know
;
1317 /* Otherwise, compute the overall effect of the inner loop. */
1318 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1319 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1320 evolution_of_loop
, limit
);
1323 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1324 path that is analyzed on the return walk. */
1327 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1328 tree
*evolution_of_loop
, int limit
)
1330 struct loop
*def_loop
;
1332 if (gimple_nop_p (def
))
1335 /* Give up if the path is longer than the MAX that we allow. */
1336 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1339 def_loop
= loop_containing_stmt (def
);
1341 switch (gimple_code (def
))
1344 if (!loop_phi_node_p (def
))
1345 /* DEF is a condition-phi-node. Follow the branches, and
1346 record their evolutions. Finally, merge the collected
1347 information and set the approximation to the main
1349 return follow_ssa_edge_in_condition_phi
1350 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1352 /* When the analyzed phi is the halting_phi, the
1353 depth-first search is over: we have found a path from
1354 the halting_phi to itself in the loop. */
1355 if (def
== halting_phi
)
1358 /* Otherwise, the evolution of the HALTING_PHI depends
1359 on the evolution of another loop-phi-node, i.e. the
1360 evolution function is a higher degree polynomial. */
1361 if (def_loop
== loop
)
1365 if (flow_loop_nested_p (loop
, def_loop
))
1366 return follow_ssa_edge_inner_loop_phi
1367 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1373 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1374 evolution_of_loop
, limit
);
1377 /* At this level of abstraction, the program is just a set
1378 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1379 other node to be handled. */
1385 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1386 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1388 # i_17 = PHI <i_13(5), 0(3)>
1389 # _20 = PHI <_5(5), start_4(D)(3)>
1392 _5 = start_4(D) + i_13;
1394 Though variable _20 appears as a PEELED_CHREC in the form of
1395 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1400 simplify_peeled_chrec (struct loop
*loop
, tree arg
, tree init_cond
)
1402 aff_tree aff1
, aff2
;
1403 tree ev
, left
, right
, type
, step_val
;
1404 pointer_map_t
*peeled_chrec_map
= NULL
;
1406 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1407 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1408 return chrec_dont_know
;
1410 left
= CHREC_LEFT (ev
);
1411 right
= CHREC_RIGHT (ev
);
1412 type
= TREE_TYPE (left
);
1413 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1415 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1416 if "left" equals to "init + right". */
1417 if (operand_equal_p (left
, step_val
, 0))
1419 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1420 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1422 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1425 /* Try harder to check if they are equal. */
1426 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1427 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1428 free_affine_expand_cache (&peeled_chrec_map
);
1429 aff_combination_scale (&aff2
, double_int_minus_one
);
1430 aff_combination_add (&aff1
, &aff2
);
1432 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1433 if "left" equals to "init + right". */
1434 if (aff_combination_zero_p (&aff1
))
1436 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1437 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1439 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1441 return chrec_dont_know
;
1444 /* Given a LOOP_PHI_NODE, this function determines the evolution
1445 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1448 analyze_evolution_in_loop (gimple loop_phi_node
,
1451 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1452 tree evolution_function
= chrec_not_analyzed_yet
;
1453 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1455 static bool simplify_peeled_chrec_p
= true;
1457 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1459 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1460 fprintf (dump_file
, " (loop_phi_node = ");
1461 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1462 fprintf (dump_file
, ")\n");
1465 for (i
= 0; i
< n
; i
++)
1467 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1472 /* Select the edges that enter the loop body. */
1473 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1474 if (!flow_bb_inside_loop_p (loop
, bb
))
1477 if (TREE_CODE (arg
) == SSA_NAME
)
1481 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1483 /* Pass in the initial condition to the follow edge function. */
1485 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1487 /* If ev_fn has no evolution in the inner loop, and the
1488 init_cond is not equal to ev_fn, then we have an
1489 ambiguity between two possible values, as we cannot know
1490 the number of iterations at this point. */
1491 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1492 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1493 && !operand_equal_p (init_cond
, ev_fn
, 0))
1494 ev_fn
= chrec_dont_know
;
1499 /* When it is impossible to go back on the same
1500 loop_phi_node by following the ssa edges, the
1501 evolution is represented by a peeled chrec, i.e. the
1502 first iteration, EV_FN has the value INIT_COND, then
1503 all the other iterations it has the value of ARG.
1504 For the moment, PEELED_CHREC nodes are not built. */
1507 ev_fn
= chrec_dont_know
;
1508 /* Try to recognize POLYNOMIAL_CHREC which appears in
1509 the form of PEELED_CHREC, but guard the process with
1510 a bool variable to keep the analyzer from infinite
1511 recurrence for real PEELED_RECs. */
1512 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1514 simplify_peeled_chrec_p
= false;
1515 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1516 simplify_peeled_chrec_p
= true;
1520 /* When there are multiple back edges of the loop (which in fact never
1521 happens currently, but nevertheless), merge their evolutions. */
1522 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1525 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1527 fprintf (dump_file
, " (evolution_function = ");
1528 print_generic_expr (dump_file
, evolution_function
, 0);
1529 fprintf (dump_file
, "))\n");
1532 return evolution_function
;
1535 /* Given a loop-phi-node, return the initial conditions of the
1536 variable on entry of the loop. When the CCP has propagated
1537 constants into the loop-phi-node, the initial condition is
1538 instantiated, otherwise the initial condition is kept symbolic.
1539 This analyzer does not analyze the evolution outside the current
1540 loop, and leaves this task to the on-demand tree reconstructor. */
1543 analyze_initial_condition (gimple loop_phi_node
)
1546 tree init_cond
= chrec_not_analyzed_yet
;
1547 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1549 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1551 fprintf (dump_file
, "(analyze_initial_condition \n");
1552 fprintf (dump_file
, " (loop_phi_node = \n");
1553 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1554 fprintf (dump_file
, ")\n");
1557 n
= gimple_phi_num_args (loop_phi_node
);
1558 for (i
= 0; i
< n
; i
++)
1560 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1561 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1563 /* When the branch is oriented to the loop's body, it does
1564 not contribute to the initial condition. */
1565 if (flow_bb_inside_loop_p (loop
, bb
))
1568 if (init_cond
== chrec_not_analyzed_yet
)
1574 if (TREE_CODE (branch
) == SSA_NAME
)
1576 init_cond
= chrec_dont_know
;
1580 init_cond
= chrec_merge (init_cond
, branch
);
1583 /* Ooops -- a loop without an entry??? */
1584 if (init_cond
== chrec_not_analyzed_yet
)
1585 init_cond
= chrec_dont_know
;
1587 /* During early loop unrolling we do not have fully constant propagated IL.
1588 Handle degenerate PHIs here to not miss important unrollings. */
1589 if (TREE_CODE (init_cond
) == SSA_NAME
)
1591 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1593 if (gimple_code (def
) == GIMPLE_PHI
1594 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1595 /* Only allow invariants here, otherwise we may break
1596 loop-closed SSA form. */
1597 && is_gimple_min_invariant (res
))
1601 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1603 fprintf (dump_file
, " (init_cond = ");
1604 print_generic_expr (dump_file
, init_cond
, 0);
1605 fprintf (dump_file
, "))\n");
1611 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1614 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1617 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1620 if (phi_loop
!= loop
)
1622 struct loop
*subloop
;
1623 tree evolution_fn
= analyze_scalar_evolution
1624 (phi_loop
, PHI_RESULT (loop_phi_node
));
1626 /* Dive one level deeper. */
1627 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1629 /* Interpret the subloop. */
1630 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1634 /* Otherwise really interpret the loop phi. */
1635 init_cond
= analyze_initial_condition (loop_phi_node
);
1636 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1638 /* Verify we maintained the correct initial condition throughout
1639 possible conversions in the SSA chain. */
1640 if (res
!= chrec_dont_know
)
1642 tree new_init
= res
;
1643 if (CONVERT_EXPR_P (res
)
1644 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1645 new_init
= fold_convert (TREE_TYPE (res
),
1646 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1647 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1648 new_init
= CHREC_LEFT (res
);
1649 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1650 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1651 || !operand_equal_p (init_cond
, new_init
, 0))
1652 return chrec_dont_know
;
1658 /* This function merges the branches of a condition-phi-node,
1659 contained in the outermost loop, and whose arguments are already
1663 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1665 int i
, n
= gimple_phi_num_args (condition_phi
);
1666 tree res
= chrec_not_analyzed_yet
;
1668 for (i
= 0; i
< n
; i
++)
1672 if (backedge_phi_arg_p (condition_phi
, i
))
1674 res
= chrec_dont_know
;
1678 branch_chrec
= analyze_scalar_evolution
1679 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1681 res
= chrec_merge (res
, branch_chrec
);
1687 /* Interpret the operation RHS1 OP RHS2. If we didn't
1688 analyze this node before, follow the definitions until ending
1689 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1690 return path, this function propagates evolutions (ala constant copy
1691 propagation). OPND1 is not a GIMPLE expression because we could
1692 analyze the effect of an inner loop: see interpret_loop_phi. */
1695 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1696 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1698 tree res
, chrec1
, chrec2
;
1701 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1703 if (is_gimple_min_invariant (rhs1
))
1704 return chrec_convert (type
, rhs1
, at_stmt
);
1706 if (code
== SSA_NAME
)
1707 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1710 if (code
== ASSERT_EXPR
)
1712 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1713 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1721 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1722 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1724 enum machine_mode mode
;
1725 HOST_WIDE_INT bitsize
, bitpos
;
1732 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1733 &bitsize
, &bitpos
, &offset
,
1734 &mode
, &unsignedp
, &volatilep
, false);
1736 if (TREE_CODE (base
) == MEM_REF
)
1738 rhs2
= TREE_OPERAND (base
, 1);
1739 rhs1
= TREE_OPERAND (base
, 0);
1741 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1742 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1743 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1744 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1745 chrec1
= instantiate_parameters (loop
, chrec1
);
1746 chrec2
= instantiate_parameters (loop
, chrec2
);
1747 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1751 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1752 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1756 if (offset
!= NULL_TREE
)
1758 chrec2
= analyze_scalar_evolution (loop
, offset
);
1759 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1760 chrec2
= instantiate_parameters (loop
, chrec2
);
1761 res
= chrec_fold_plus (type
, res
, chrec2
);
1766 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1768 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1769 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1770 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1771 chrec3
= instantiate_parameters (loop
, chrec3
);
1772 res
= chrec_fold_plus (type
, res
, chrec3
);
1776 res
= chrec_dont_know
;
1779 case POINTER_PLUS_EXPR
:
1780 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1781 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1782 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1783 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1784 chrec1
= instantiate_parameters (loop
, chrec1
);
1785 chrec2
= instantiate_parameters (loop
, chrec2
);
1786 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1790 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1791 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1792 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1793 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1794 chrec1
= instantiate_parameters (loop
, chrec1
);
1795 chrec2
= instantiate_parameters (loop
, chrec2
);
1796 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1800 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1801 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1802 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1803 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1804 chrec1
= instantiate_parameters (loop
, chrec1
);
1805 chrec2
= instantiate_parameters (loop
, chrec2
);
1806 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1810 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1811 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1812 /* TYPE may be integer, real or complex, so use fold_convert. */
1813 chrec1
= instantiate_parameters (loop
, chrec1
);
1814 res
= chrec_fold_multiply (type
, chrec1
,
1815 fold_convert (type
, integer_minus_one_node
));
1819 /* Handle ~X as -1 - X. */
1820 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1821 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1822 chrec1
= instantiate_parameters (loop
, chrec1
);
1823 res
= chrec_fold_minus (type
,
1824 fold_convert (type
, integer_minus_one_node
),
1829 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1830 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1831 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1832 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1833 chrec1
= instantiate_parameters (loop
, chrec1
);
1834 chrec2
= instantiate_parameters (loop
, chrec2
);
1835 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1839 /* In case we have a truncation of a widened operation that in
1840 the truncated type has undefined overflow behavior analyze
1841 the operation done in an unsigned type of the same precision
1842 as the final truncation. We cannot derive a scalar evolution
1843 for the widened operation but for the truncated result. */
1844 if (TREE_CODE (type
) == INTEGER_TYPE
1845 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1846 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1847 && TYPE_OVERFLOW_UNDEFINED (type
)
1848 && TREE_CODE (rhs1
) == SSA_NAME
1849 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1850 && is_gimple_assign (def
)
1851 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1852 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1854 tree utype
= unsigned_type_for (type
);
1855 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1856 gimple_assign_rhs1 (def
),
1857 gimple_assign_rhs_code (def
),
1858 gimple_assign_rhs2 (def
));
1861 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1862 res
= chrec_convert (type
, chrec1
, at_stmt
);
1866 res
= chrec_dont_know
;
1873 /* Interpret the expression EXPR. */
1876 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1878 enum tree_code code
;
1879 tree type
= TREE_TYPE (expr
), op0
, op1
;
1881 if (automatically_generated_chrec_p (expr
))
1884 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1885 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1886 return chrec_dont_know
;
1888 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1890 return interpret_rhs_expr (loop
, at_stmt
, type
,
1894 /* Interpret the rhs of the assignment STMT. */
1897 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1899 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1900 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1902 return interpret_rhs_expr (loop
, stmt
, type
,
1903 gimple_assign_rhs1 (stmt
), code
,
1904 gimple_assign_rhs2 (stmt
));
1909 /* This section contains all the entry points:
1910 - number_of_iterations_in_loop,
1911 - analyze_scalar_evolution,
1912 - instantiate_parameters.
1915 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1916 common ancestor of DEF_LOOP and USE_LOOP. */
1919 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1920 struct loop
*def_loop
,
1926 if (def_loop
== wrto_loop
)
1929 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1930 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1932 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1935 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1938 /* Helper recursive function. */
1941 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1943 tree type
= TREE_TYPE (var
);
1946 struct loop
*def_loop
;
1948 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1949 return chrec_dont_know
;
1951 if (TREE_CODE (var
) != SSA_NAME
)
1952 return interpret_expr (loop
, NULL
, var
);
1954 def
= SSA_NAME_DEF_STMT (var
);
1955 bb
= gimple_bb (def
);
1956 def_loop
= bb
? bb
->loop_father
: NULL
;
1959 || !flow_bb_inside_loop_p (loop
, bb
))
1961 /* Keep the symbolic form. */
1966 if (res
!= chrec_not_analyzed_yet
)
1968 if (loop
!= bb
->loop_father
)
1969 res
= compute_scalar_evolution_in_loop
1970 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1975 if (loop
!= def_loop
)
1977 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1978 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1983 switch (gimple_code (def
))
1986 res
= interpret_gimple_assign (loop
, def
);
1990 if (loop_phi_node_p (def
))
1991 res
= interpret_loop_phi (loop
, def
);
1993 res
= interpret_condition_phi (loop
, def
);
1997 res
= chrec_dont_know
;
2003 /* Keep the symbolic form. */
2004 if (res
== chrec_dont_know
)
2007 if (loop
== def_loop
)
2008 set_scalar_evolution (block_before_loop (loop
), var
, res
);
2013 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2014 LOOP. LOOP is the loop in which the variable is used.
2016 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2017 pointer to the statement that uses this variable, in order to
2018 determine the evolution function of the variable, use the following
2021 loop_p loop = loop_containing_stmt (stmt);
2022 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2023 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2027 analyze_scalar_evolution (struct loop
*loop
, tree var
)
2031 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2033 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2034 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2035 fprintf (dump_file
, " (scalar = ");
2036 print_generic_expr (dump_file
, var
, 0);
2037 fprintf (dump_file
, ")\n");
2040 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2041 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
2043 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2044 fprintf (dump_file
, ")\n");
2049 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2052 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
2054 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2057 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2058 WRTO_LOOP (which should be a superloop of USE_LOOP)
2060 FOLDED_CASTS is set to true if resolve_mixers used
2061 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2062 at the moment in order to keep things simple).
2064 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2067 for (i = 0; i < 100; i++) -- loop 1
2069 for (j = 0; j < 100; j++) -- loop 2
2076 for (t = 0; t < 100; t++) -- loop 3
2083 Both k1 and k2 are invariants in loop3, thus
2084 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2085 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2087 As they are invariant, it does not matter whether we consider their
2088 usage in loop 3 or loop 2, hence
2089 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2090 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2091 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2092 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2094 Similarly for their evolutions with respect to loop 1. The values of K2
2095 in the use in loop 2 vary independently on loop 1, thus we cannot express
2096 the evolution with respect to loop 1:
2097 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2098 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2099 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2100 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2102 The value of k2 in the use in loop 1 is known, though:
2103 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2104 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2108 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2109 tree version
, bool *folded_casts
)
2112 tree ev
= version
, tmp
;
2114 /* We cannot just do
2116 tmp = analyze_scalar_evolution (use_loop, version);
2117 ev = resolve_mixers (wrto_loop, tmp);
2119 as resolve_mixers would query the scalar evolution with respect to
2120 wrto_loop. For example, in the situation described in the function
2121 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2124 analyze_scalar_evolution (use_loop, version) = k2
2126 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2127 is 100, which is a wrong result, since we are interested in the
2130 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2131 each time checking that there is no evolution in the inner loop. */
2134 *folded_casts
= false;
2137 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2138 ev
= resolve_mixers (use_loop
, tmp
);
2140 if (folded_casts
&& tmp
!= ev
)
2141 *folded_casts
= true;
2143 if (use_loop
== wrto_loop
)
2146 /* If the value of the use changes in the inner loop, we cannot express
2147 its value in the outer loop (we might try to return interval chrec,
2148 but we do not have a user for it anyway) */
2149 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2151 return chrec_dont_know
;
2153 use_loop
= loop_outer (use_loop
);
2158 /* Hashtable helpers for a temporary hash-table used when
2159 instantiating a CHREC or resolving mixers. For this use
2160 instantiated_below is always the same. */
2162 struct instantiate_cache_type
2165 vec
<scev_info_str
> entries
;
2167 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2168 ~instantiate_cache_type ();
2169 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2170 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2173 instantiate_cache_type::~instantiate_cache_type ()
2182 /* Cache to avoid infinite recursion when instantiating an SSA name.
2183 Live during the outermost instantiate_scev or resolve_mixers call. */
2184 static instantiate_cache_type
*global_cache
;
2186 /* Computes a hash function for database element ELT. */
2188 static inline hashval_t
2189 hash_idx_scev_info (const void *elt_
)
2191 unsigned idx
= ((size_t) elt_
) - 2;
2192 return hash_scev_info (&global_cache
->entries
[idx
]);
2195 /* Compares database elements E1 and E2. */
2198 eq_idx_scev_info (const void *e1
, const void *e2
)
2200 unsigned idx1
= ((size_t) e1
) - 2;
2201 return eq_scev_info (&global_cache
->entries
[idx1
], e2
);
2204 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2207 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2208 tree name
, basic_block instantiate_below
)
2212 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2213 cache
.entries
.create (10);
2217 e
.name_version
= SSA_NAME_VERSION (name
);
2218 e
.instantiated_below
= instantiate_below
->index
;
2219 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2220 hash_scev_info (&e
), INSERT
);
2223 e
.chrec
= chrec_not_analyzed_yet
;
2224 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2225 cache
.entries
.safe_push (e
);
2228 return ((size_t)*slot
) - 2;
2232 /* Return the closed_loop_phi node for VAR. If there is none, return
2236 loop_closed_phi_def (tree var
)
2241 gimple_stmt_iterator psi
;
2243 if (var
== NULL_TREE
2244 || TREE_CODE (var
) != SSA_NAME
)
2247 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2248 exit
= single_exit (loop
);
2252 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2254 phi
= gsi_stmt (psi
);
2255 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2256 return PHI_RESULT (phi
);
2262 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2265 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2266 and EVOLUTION_LOOP, that were left under a symbolic form.
2268 CHREC is an SSA_NAME to be instantiated.
2270 CACHE is the cache of already instantiated values.
2272 FOLD_CONVERSIONS should be set to true when the conversions that
2273 may wrap in signed/pointer type are folded, as long as the value of
2274 the chrec is preserved.
2276 SIZE_EXPR is used for computing the size of the expression to be
2277 instantiated, and to stop if it exceeds some limit. */
2280 instantiate_scev_name (basic_block instantiate_below
,
2281 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2283 bool fold_conversions
,
2287 struct loop
*def_loop
;
2288 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2290 /* A parameter (or loop invariant and we do not want to include
2291 evolutions in outer loops), nothing to do. */
2293 || loop_depth (def_bb
->loop_father
) == 0
2294 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2297 /* We cache the value of instantiated variable to avoid exponential
2298 time complexity due to reevaluations. We also store the convenient
2299 value in the cache in order to prevent infinite recursion -- we do
2300 not want to instantiate the SSA_NAME if it is in a mixer
2301 structure. This is used for avoiding the instantiation of
2302 recursively defined functions, such as:
2304 | a_2 -> {0, +, 1, +, a_2}_1 */
2306 unsigned si
= get_instantiated_value_entry (*global_cache
,
2307 chrec
, instantiate_below
);
2308 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2309 return global_cache
->get (si
);
2311 /* On recursion return chrec_dont_know. */
2312 global_cache
->set (si
, chrec_dont_know
);
2314 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2316 /* If the analysis yields a parametric chrec, instantiate the
2318 res
= analyze_scalar_evolution (def_loop
, chrec
);
2320 /* Don't instantiate default definitions. */
2321 if (TREE_CODE (res
) == SSA_NAME
2322 && SSA_NAME_IS_DEFAULT_DEF (res
))
2325 /* Don't instantiate loop-closed-ssa phi nodes. */
2326 else if (TREE_CODE (res
) == SSA_NAME
2327 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2328 > loop_depth (def_loop
))
2331 res
= loop_closed_phi_def (chrec
);
2335 /* When there is no loop_closed_phi_def, it means that the
2336 variable is not used after the loop: try to still compute the
2337 value of the variable when exiting the loop. */
2338 if (res
== NULL_TREE
)
2340 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2341 res
= analyze_scalar_evolution (loop
, chrec
);
2342 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2343 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2345 fold_conversions
, size_expr
);
2347 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2348 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2349 res
= chrec_dont_know
;
2352 else if (res
!= chrec_dont_know
)
2355 && def_bb
->loop_father
!= inner_loop
2356 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2357 /* ??? We could try to compute the overall effect of the loop here. */
2358 res
= chrec_dont_know
;
2360 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2362 fold_conversions
, size_expr
);
2365 /* Store the correct value to the cache. */
2366 global_cache
->set (si
, res
);
2370 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2371 and EVOLUTION_LOOP, that were left under a symbolic form.
2373 CHREC is a polynomial chain of recurrence to be instantiated.
2375 CACHE is the cache of already instantiated values.
2377 FOLD_CONVERSIONS should be set to true when the conversions that
2378 may wrap in signed/pointer type are folded, as long as the value of
2379 the chrec is preserved.
2381 SIZE_EXPR is used for computing the size of the expression to be
2382 instantiated, and to stop if it exceeds some limit. */
2385 instantiate_scev_poly (basic_block instantiate_below
,
2386 struct loop
*evolution_loop
, struct loop
*,
2387 tree chrec
, bool fold_conversions
, int size_expr
)
2390 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2391 get_chrec_loop (chrec
),
2392 CHREC_LEFT (chrec
), fold_conversions
,
2394 if (op0
== chrec_dont_know
)
2395 return chrec_dont_know
;
2397 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2398 get_chrec_loop (chrec
),
2399 CHREC_RIGHT (chrec
), fold_conversions
,
2401 if (op1
== chrec_dont_know
)
2402 return chrec_dont_know
;
2404 if (CHREC_LEFT (chrec
) != op0
2405 || CHREC_RIGHT (chrec
) != op1
)
2407 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2408 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2414 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2415 and EVOLUTION_LOOP, that were left under a symbolic form.
2417 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2419 CACHE is the cache of already instantiated values.
2421 FOLD_CONVERSIONS should be set to true when the conversions that
2422 may wrap in signed/pointer type are folded, as long as the value of
2423 the chrec is preserved.
2425 SIZE_EXPR is used for computing the size of the expression to be
2426 instantiated, and to stop if it exceeds some limit. */
2429 instantiate_scev_binary (basic_block instantiate_below
,
2430 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2431 tree chrec
, enum tree_code code
,
2432 tree type
, tree c0
, tree c1
,
2433 bool fold_conversions
, int size_expr
)
2436 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2437 c0
, fold_conversions
, size_expr
);
2438 if (op0
== chrec_dont_know
)
2439 return chrec_dont_know
;
2441 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2442 c1
, fold_conversions
, size_expr
);
2443 if (op1
== chrec_dont_know
)
2444 return chrec_dont_know
;
2449 op0
= chrec_convert (type
, op0
, NULL
);
2450 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2454 case POINTER_PLUS_EXPR
:
2456 return chrec_fold_plus (type
, op0
, op1
);
2459 return chrec_fold_minus (type
, op0
, op1
);
2462 return chrec_fold_multiply (type
, op0
, op1
);
2469 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2472 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2473 and EVOLUTION_LOOP, that were left under a symbolic form.
2475 "CHREC" is an array reference to be instantiated.
2477 CACHE is the cache of already instantiated values.
2479 FOLD_CONVERSIONS should be set to true when the conversions that
2480 may wrap in signed/pointer type are folded, as long as the value of
2481 the chrec is preserved.
2483 SIZE_EXPR is used for computing the size of the expression to be
2484 instantiated, and to stop if it exceeds some limit. */
2487 instantiate_array_ref (basic_block instantiate_below
,
2488 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2489 tree chrec
, bool fold_conversions
, int size_expr
)
2492 tree index
= TREE_OPERAND (chrec
, 1);
2493 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2495 fold_conversions
, size_expr
);
2497 if (op1
== chrec_dont_know
)
2498 return chrec_dont_know
;
2500 if (chrec
&& op1
== index
)
2503 res
= unshare_expr (chrec
);
2504 TREE_OPERAND (res
, 1) = op1
;
2508 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2509 and EVOLUTION_LOOP, that were left under a symbolic form.
2511 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2514 CACHE is the cache of already instantiated values.
2516 FOLD_CONVERSIONS should be set to true when the conversions that
2517 may wrap in signed/pointer type are folded, as long as the value of
2518 the chrec is preserved.
2520 SIZE_EXPR is used for computing the size of the expression to be
2521 instantiated, and to stop if it exceeds some limit. */
2524 instantiate_scev_convert (basic_block instantiate_below
,
2525 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2526 tree chrec
, tree type
, tree op
,
2527 bool fold_conversions
, int size_expr
)
2529 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2531 fold_conversions
, size_expr
);
2533 if (op0
== chrec_dont_know
)
2534 return chrec_dont_know
;
2536 if (fold_conversions
)
2538 tree tmp
= chrec_convert_aggressive (type
, op0
);
2543 if (chrec
&& op0
== op
)
2546 /* If we used chrec_convert_aggressive, we can no longer assume that
2547 signed chrecs do not overflow, as chrec_convert does, so avoid
2548 calling it in that case. */
2549 if (fold_conversions
)
2550 return fold_convert (type
, op0
);
2552 return chrec_convert (type
, op0
, NULL
);
2555 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2556 and EVOLUTION_LOOP, that were left under a symbolic form.
2558 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2559 Handle ~X as -1 - X.
2560 Handle -X as -1 * X.
2562 CACHE is the cache of already instantiated values.
2564 FOLD_CONVERSIONS should be set to true when the conversions that
2565 may wrap in signed/pointer type are folded, as long as the value of
2566 the chrec is preserved.
2568 SIZE_EXPR is used for computing the size of the expression to be
2569 instantiated, and to stop if it exceeds some limit. */
2572 instantiate_scev_not (basic_block instantiate_below
,
2573 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2575 enum tree_code code
, tree type
, tree op
,
2576 bool fold_conversions
, int size_expr
)
2578 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2580 fold_conversions
, size_expr
);
2582 if (op0
== chrec_dont_know
)
2583 return chrec_dont_know
;
2587 op0
= chrec_convert (type
, op0
, NULL
);
2592 return chrec_fold_minus
2593 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2596 return chrec_fold_multiply
2597 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2604 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2607 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2608 and EVOLUTION_LOOP, that were left under a symbolic form.
2610 CHREC is an expression with 3 operands to be instantiated.
2612 CACHE is the cache of already instantiated values.
2614 FOLD_CONVERSIONS should be set to true when the conversions that
2615 may wrap in signed/pointer type are folded, as long as the value of
2616 the chrec is preserved.
2618 SIZE_EXPR is used for computing the size of the expression to be
2619 instantiated, and to stop if it exceeds some limit. */
2622 instantiate_scev_3 (basic_block instantiate_below
,
2623 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2625 bool fold_conversions
, int size_expr
)
2628 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2629 inner_loop
, TREE_OPERAND (chrec
, 0),
2630 fold_conversions
, size_expr
);
2631 if (op0
== chrec_dont_know
)
2632 return chrec_dont_know
;
2634 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2635 inner_loop
, TREE_OPERAND (chrec
, 1),
2636 fold_conversions
, size_expr
);
2637 if (op1
== chrec_dont_know
)
2638 return chrec_dont_know
;
2640 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2641 inner_loop
, TREE_OPERAND (chrec
, 2),
2642 fold_conversions
, size_expr
);
2643 if (op2
== chrec_dont_know
)
2644 return chrec_dont_know
;
2646 if (op0
== TREE_OPERAND (chrec
, 0)
2647 && op1
== TREE_OPERAND (chrec
, 1)
2648 && op2
== TREE_OPERAND (chrec
, 2))
2651 return fold_build3 (TREE_CODE (chrec
),
2652 TREE_TYPE (chrec
), op0
, op1
, op2
);
2655 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2656 and EVOLUTION_LOOP, that were left under a symbolic form.
2658 CHREC is an expression with 2 operands to be instantiated.
2660 CACHE is the cache of already instantiated values.
2662 FOLD_CONVERSIONS should be set to true when the conversions that
2663 may wrap in signed/pointer type are folded, as long as the value of
2664 the chrec is preserved.
2666 SIZE_EXPR is used for computing the size of the expression to be
2667 instantiated, and to stop if it exceeds some limit. */
2670 instantiate_scev_2 (basic_block instantiate_below
,
2671 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2673 bool fold_conversions
, int size_expr
)
2676 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2677 inner_loop
, TREE_OPERAND (chrec
, 0),
2678 fold_conversions
, size_expr
);
2679 if (op0
== chrec_dont_know
)
2680 return chrec_dont_know
;
2682 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2683 inner_loop
, TREE_OPERAND (chrec
, 1),
2684 fold_conversions
, size_expr
);
2685 if (op1
== chrec_dont_know
)
2686 return chrec_dont_know
;
2688 if (op0
== TREE_OPERAND (chrec
, 0)
2689 && op1
== TREE_OPERAND (chrec
, 1))
2692 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2695 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2696 and EVOLUTION_LOOP, that were left under a symbolic form.
2698 CHREC is an expression with 2 operands to be instantiated.
2700 CACHE is the cache of already instantiated values.
2702 FOLD_CONVERSIONS should be set to true when the conversions that
2703 may wrap in signed/pointer type are folded, as long as the value of
2704 the chrec is preserved.
2706 SIZE_EXPR is used for computing the size of the expression to be
2707 instantiated, and to stop if it exceeds some limit. */
2710 instantiate_scev_1 (basic_block instantiate_below
,
2711 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2713 bool fold_conversions
, int size_expr
)
2715 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2716 inner_loop
, TREE_OPERAND (chrec
, 0),
2717 fold_conversions
, size_expr
);
2719 if (op0
== chrec_dont_know
)
2720 return chrec_dont_know
;
2722 if (op0
== TREE_OPERAND (chrec
, 0))
2725 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2728 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2729 and EVOLUTION_LOOP, that were left under a symbolic form.
2731 CHREC is the scalar evolution to instantiate.
2733 CACHE is the cache of already instantiated values.
2735 FOLD_CONVERSIONS should be set to true when the conversions that
2736 may wrap in signed/pointer type are folded, as long as the value of
2737 the chrec is preserved.
2739 SIZE_EXPR is used for computing the size of the expression to be
2740 instantiated, and to stop if it exceeds some limit. */
2743 instantiate_scev_r (basic_block instantiate_below
,
2744 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2746 bool fold_conversions
, int size_expr
)
2748 /* Give up if the expression is larger than the MAX that we allow. */
2749 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2750 return chrec_dont_know
;
2752 if (chrec
== NULL_TREE
2753 || automatically_generated_chrec_p (chrec
)
2754 || is_gimple_min_invariant (chrec
))
2757 switch (TREE_CODE (chrec
))
2760 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2762 fold_conversions
, size_expr
);
2764 case POLYNOMIAL_CHREC
:
2765 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2767 fold_conversions
, size_expr
);
2769 case POINTER_PLUS_EXPR
:
2773 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2775 TREE_CODE (chrec
), chrec_type (chrec
),
2776 TREE_OPERAND (chrec
, 0),
2777 TREE_OPERAND (chrec
, 1),
2778 fold_conversions
, size_expr
);
2781 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2783 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2784 fold_conversions
, size_expr
);
2788 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2790 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2791 TREE_OPERAND (chrec
, 0),
2792 fold_conversions
, size_expr
);
2795 case SCEV_NOT_KNOWN
:
2796 return chrec_dont_know
;
2802 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2804 fold_conversions
, size_expr
);
2810 if (VL_EXP_CLASS_P (chrec
))
2811 return chrec_dont_know
;
2813 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2816 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2818 fold_conversions
, size_expr
);
2821 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2823 fold_conversions
, size_expr
);
2826 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2828 fold_conversions
, size_expr
);
2837 /* Too complicated to handle. */
2838 return chrec_dont_know
;
2841 /* Analyze all the parameters of the chrec that were left under a
2842 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2843 recursive instantiation of parameters: a parameter is a variable
2844 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2845 a function parameter. */
2848 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2853 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2855 fprintf (dump_file
, "(instantiate_scev \n");
2856 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2857 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2858 fprintf (dump_file
, " (chrec = ");
2859 print_generic_expr (dump_file
, chrec
, 0);
2860 fprintf (dump_file
, ")\n");
2866 global_cache
= new instantiate_cache_type
;
2870 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2871 NULL
, chrec
, false, 0);
2875 delete global_cache
;
2876 global_cache
= NULL
;
2879 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2881 fprintf (dump_file
, " (res = ");
2882 print_generic_expr (dump_file
, res
, 0);
2883 fprintf (dump_file
, "))\n");
2889 /* Similar to instantiate_parameters, but does not introduce the
2890 evolutions in outer loops for LOOP invariants in CHREC, and does not
2891 care about causing overflows, as long as they do not affect value
2892 of an expression. */
2895 resolve_mixers (struct loop
*loop
, tree chrec
)
2900 global_cache
= new instantiate_cache_type
;
2904 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2909 delete global_cache
;
2910 global_cache
= NULL
;
2916 /* Entry point for the analysis of the number of iterations pass.
2917 This function tries to safely approximate the number of iterations
2918 the loop will run. When this property is not decidable at compile
2919 time, the result is chrec_dont_know. Otherwise the result is a
2920 scalar or a symbolic parameter. When the number of iterations may
2921 be equal to zero and the property cannot be determined at compile
2922 time, the result is a COND_EXPR that represents in a symbolic form
2923 the conditions under which the number of iterations is not zero.
2925 Example of analysis: suppose that the loop has an exit condition:
2927 "if (b > 49) goto end_loop;"
2929 and that in a previous analysis we have determined that the
2930 variable 'b' has an evolution function:
2932 "EF = {23, +, 5}_2".
2934 When we evaluate the function at the point 5, i.e. the value of the
2935 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2936 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2937 the loop body has been executed 6 times. */
2940 number_of_latch_executions (struct loop
*loop
)
2943 struct tree_niter_desc niter_desc
;
2947 /* Determine whether the number of iterations in loop has already
2949 res
= loop
->nb_iterations
;
2953 may_be_zero
= NULL_TREE
;
2955 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2956 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2958 res
= chrec_dont_know
;
2959 exit
= single_exit (loop
);
2961 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2963 may_be_zero
= niter_desc
.may_be_zero
;
2964 res
= niter_desc
.niter
;
2967 if (res
== chrec_dont_know
2969 || integer_zerop (may_be_zero
))
2971 else if (integer_nonzerop (may_be_zero
))
2972 res
= build_int_cst (TREE_TYPE (res
), 0);
2974 else if (COMPARISON_CLASS_P (may_be_zero
))
2975 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2976 build_int_cst (TREE_TYPE (res
), 0), res
);
2978 res
= chrec_dont_know
;
2980 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2982 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2983 print_generic_expr (dump_file
, res
, 0);
2984 fprintf (dump_file
, "))\n");
2987 loop
->nb_iterations
= res
;
2992 /* Counters for the stats. */
2998 unsigned nb_affine_multivar
;
2999 unsigned nb_higher_poly
;
3000 unsigned nb_chrec_dont_know
;
3001 unsigned nb_undetermined
;
3004 /* Reset the counters. */
3007 reset_chrecs_counters (struct chrec_stats
*stats
)
3009 stats
->nb_chrecs
= 0;
3010 stats
->nb_affine
= 0;
3011 stats
->nb_affine_multivar
= 0;
3012 stats
->nb_higher_poly
= 0;
3013 stats
->nb_chrec_dont_know
= 0;
3014 stats
->nb_undetermined
= 0;
3017 /* Dump the contents of a CHREC_STATS structure. */
3020 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
3022 fprintf (file
, "\n(\n");
3023 fprintf (file
, "-----------------------------------------\n");
3024 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
3025 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
3026 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
3027 stats
->nb_higher_poly
);
3028 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
3029 fprintf (file
, "-----------------------------------------\n");
3030 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
3031 fprintf (file
, "%d\twith undetermined coefficients\n",
3032 stats
->nb_undetermined
);
3033 fprintf (file
, "-----------------------------------------\n");
3034 fprintf (file
, "%d\tchrecs in the scev database\n",
3035 (int) htab_elements (scalar_evolution_info
));
3036 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
3037 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
3038 fprintf (file
, "-----------------------------------------\n");
3039 fprintf (file
, ")\n\n");
3042 /* Gather statistics about CHREC. */
3045 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
3047 if (dump_file
&& (dump_flags
& TDF_STATS
))
3049 fprintf (dump_file
, "(classify_chrec ");
3050 print_generic_expr (dump_file
, chrec
, 0);
3051 fprintf (dump_file
, "\n");
3056 if (chrec
== NULL_TREE
)
3058 stats
->nb_undetermined
++;
3062 switch (TREE_CODE (chrec
))
3064 case POLYNOMIAL_CHREC
:
3065 if (evolution_function_is_affine_p (chrec
))
3067 if (dump_file
&& (dump_flags
& TDF_STATS
))
3068 fprintf (dump_file
, " affine_univariate\n");
3071 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3073 if (dump_file
&& (dump_flags
& TDF_STATS
))
3074 fprintf (dump_file
, " affine_multivariate\n");
3075 stats
->nb_affine_multivar
++;
3079 if (dump_file
&& (dump_flags
& TDF_STATS
))
3080 fprintf (dump_file
, " higher_degree_polynomial\n");
3081 stats
->nb_higher_poly
++;
3090 if (chrec_contains_undetermined (chrec
))
3092 if (dump_file
&& (dump_flags
& TDF_STATS
))
3093 fprintf (dump_file
, " undetermined\n");
3094 stats
->nb_undetermined
++;
3097 if (dump_file
&& (dump_flags
& TDF_STATS
))
3098 fprintf (dump_file
, ")\n");
3101 /* Callback for htab_traverse, gathers information on chrecs in the
3105 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
3107 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
3109 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3114 /* Classify the chrecs of the whole database. */
3117 gather_stats_on_scev_database (void)
3119 struct chrec_stats stats
;
3124 reset_chrecs_counters (&stats
);
3126 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3129 dump_chrecs_stats (dump_file
, &stats
);
3137 initialize_scalar_evolutions_analyzer (void)
3139 /* The elements below are unique. */
3140 if (chrec_dont_know
== NULL_TREE
)
3142 chrec_not_analyzed_yet
= NULL_TREE
;
3143 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3144 chrec_known
= make_node (SCEV_KNOWN
);
3145 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3146 TREE_TYPE (chrec_known
) = void_type_node
;
3150 /* Initialize the analysis of scalar evolutions for LOOPS. */
3153 scev_initialize (void)
3157 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3160 initialize_scalar_evolutions_analyzer ();
3162 FOR_EACH_LOOP (loop
, 0)
3164 loop
->nb_iterations
= NULL_TREE
;
3168 /* Return true if SCEV is initialized. */
3171 scev_initialized_p (void)
3173 return scalar_evolution_info
!= NULL
;
3176 /* Cleans up the information cached by the scalar evolutions analysis
3177 in the hash table. */
3180 scev_reset_htab (void)
3182 if (!scalar_evolution_info
)
3185 htab_empty (scalar_evolution_info
);
3188 /* Cleans up the information cached by the scalar evolutions analysis
3189 in the hash table and in the loop->nb_iterations. */
3201 FOR_EACH_LOOP (loop
, 0)
3203 loop
->nb_iterations
= NULL_TREE
;
3207 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3208 respect to WRTO_LOOP and returns its base and step in IV if possible
3209 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3210 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3211 invariant in LOOP. Otherwise we require it to be an integer constant.
3213 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3214 because it is computed in signed arithmetics). Consequently, adding an
3217 for (i = IV->base; ; i += IV->step)
3219 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3220 false for the type of the induction variable, or you can prove that i does
3221 not wrap by some other argument. Otherwise, this might introduce undefined
3224 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3226 must be used instead. */
3229 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3230 affine_iv
*iv
, bool allow_nonconstant_step
)
3235 iv
->base
= NULL_TREE
;
3236 iv
->step
= NULL_TREE
;
3237 iv
->no_overflow
= false;
3239 type
= TREE_TYPE (op
);
3240 if (!POINTER_TYPE_P (type
)
3241 && !INTEGRAL_TYPE_P (type
))
3244 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3246 if (chrec_contains_undetermined (ev
)
3247 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3250 if (tree_does_not_contain_chrecs (ev
))
3253 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3254 iv
->no_overflow
= true;
3258 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3259 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3262 iv
->step
= CHREC_RIGHT (ev
);
3263 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3264 || tree_contains_chrecs (iv
->step
, NULL
))
3267 iv
->base
= CHREC_LEFT (ev
);
3268 if (tree_contains_chrecs (iv
->base
, NULL
))
3271 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3276 /* Finalize the scalar evolution analysis. */
3279 scev_finalize (void)
3281 if (!scalar_evolution_info
)
3283 htab_delete (scalar_evolution_info
);
3284 scalar_evolution_info
= NULL
;
3287 /* Returns true if the expression EXPR is considered to be too expensive
3288 for scev_const_prop. */
3291 expression_expensive_p (tree expr
)
3293 enum tree_code code
;
3295 if (is_gimple_val (expr
))
3298 code
= TREE_CODE (expr
);
3299 if (code
== TRUNC_DIV_EXPR
3300 || code
== CEIL_DIV_EXPR
3301 || code
== FLOOR_DIV_EXPR
3302 || code
== ROUND_DIV_EXPR
3303 || code
== TRUNC_MOD_EXPR
3304 || code
== CEIL_MOD_EXPR
3305 || code
== FLOOR_MOD_EXPR
3306 || code
== ROUND_MOD_EXPR
3307 || code
== EXACT_DIV_EXPR
)
3309 /* Division by power of two is usually cheap, so we allow it.
3310 Forbid anything else. */
3311 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3315 switch (TREE_CODE_CLASS (code
))
3318 case tcc_comparison
:
3319 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3324 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3331 /* Replace ssa names for that scev can prove they are constant by the
3332 appropriate constants. Also perform final value replacement in loops,
3333 in case the replacement expressions are cheap.
3335 We only consider SSA names defined by phi nodes; rest is left to the
3336 ordinary constant propagation pass. */
3339 scev_const_prop (void)
3342 tree name
, type
, ev
;
3344 struct loop
*loop
, *ex_loop
;
3345 bitmap ssa_names_to_remove
= NULL
;
3347 gimple_stmt_iterator psi
;
3349 if (number_of_loops (cfun
) <= 1)
3352 FOR_EACH_BB_FN (bb
, cfun
)
3354 loop
= bb
->loop_father
;
3356 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3358 phi
= gsi_stmt (psi
);
3359 name
= PHI_RESULT (phi
);
3361 if (virtual_operand_p (name
))
3364 type
= TREE_TYPE (name
);
3366 if (!POINTER_TYPE_P (type
)
3367 && !INTEGRAL_TYPE_P (type
))
3370 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3371 if (!is_gimple_min_invariant (ev
)
3372 || !may_propagate_copy (name
, ev
))
3375 /* Replace the uses of the name. */
3377 replace_uses_by (name
, ev
);
3379 if (!ssa_names_to_remove
)
3380 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3381 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3385 /* Remove the ssa names that were replaced by constants. We do not
3386 remove them directly in the previous cycle, since this
3387 invalidates scev cache. */
3388 if (ssa_names_to_remove
)
3392 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3394 gimple_stmt_iterator psi
;
3395 name
= ssa_name (i
);
3396 phi
= SSA_NAME_DEF_STMT (name
);
3398 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3399 psi
= gsi_for_stmt (phi
);
3400 remove_phi_node (&psi
, true);
3403 BITMAP_FREE (ssa_names_to_remove
);
3407 /* Now the regular final value replacement. */
3408 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3411 tree def
, rslt
, niter
;
3412 gimple_stmt_iterator bsi
;
3414 /* If we do not know exact number of iterations of the loop, we cannot
3415 replace the final value. */
3416 exit
= single_exit (loop
);
3420 niter
= number_of_latch_executions (loop
);
3421 if (niter
== chrec_dont_know
)
3424 /* Ensure that it is possible to insert new statements somewhere. */
3425 if (!single_pred_p (exit
->dest
))
3426 split_loop_exit_edge (exit
);
3427 bsi
= gsi_after_labels (exit
->dest
);
3429 ex_loop
= superloop_at_depth (loop
,
3430 loop_depth (exit
->dest
->loop_father
) + 1);
3432 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3434 phi
= gsi_stmt (psi
);
3435 rslt
= PHI_RESULT (phi
);
3436 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3437 if (virtual_operand_p (def
))
3443 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3444 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3450 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3451 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3452 if (!tree_does_not_contain_chrecs (def
)
3453 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3454 /* Moving the computation from the loop may prolong life range
3455 of some ssa names, which may cause problems if they appear
3456 on abnormal edges. */
3457 || contains_abnormal_ssa_name_p (def
)
3458 /* Do not emit expensive expressions. The rationale is that
3459 when someone writes a code like
3461 while (n > 45) n -= 45;
3463 he probably knows that n is not large, and does not want it
3464 to be turned into n %= 45. */
3465 || expression_expensive_p (def
))
3467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3469 fprintf (dump_file
, "not replacing:\n ");
3470 print_gimple_stmt (dump_file
, phi
, 0, 0);
3471 fprintf (dump_file
, "\n");
3477 /* Eliminate the PHI node and replace it by a computation outside
3481 fprintf (dump_file
, "\nfinal value replacement:\n ");
3482 print_gimple_stmt (dump_file
, phi
, 0, 0);
3483 fprintf (dump_file
, " with\n ");
3485 def
= unshare_expr (def
);
3486 remove_phi_node (&psi
, false);
3488 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3489 true, GSI_SAME_STMT
);
3490 ass
= gimple_build_assign (rslt
, def
);
3491 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3494 print_gimple_stmt (dump_file
, ass
, 0, 0);
3495 fprintf (dump_file
, "\n");
3502 #include "gt-tree-scalar-evolution.h"