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"
260 #include "hash-table.h"
261 #include "gimple-pretty-print.h"
262 #include "tree-ssa.h"
264 #include "tree-chrec.h"
265 #include "tree-scalar-evolution.h"
266 #include "dumpfile.h"
268 #include "tree-ssa-propagate.h"
270 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
271 static tree
analyze_scalar_evolution_for_address_of (struct loop
*loop
,
274 /* The cached information about an SSA name with version NAME_VERSION,
275 claiming that below basic block with index INSTANTIATED_BELOW, the
276 value of the SSA name can be expressed as CHREC. */
278 struct GTY(()) scev_info_str
{
279 unsigned int name_version
;
280 int instantiated_below
;
284 /* Counters for the scev database. */
285 static unsigned nb_set_scev
= 0;
286 static unsigned nb_get_scev
= 0;
288 /* The following trees are unique elements. Thus the comparison of
289 another element to these elements should be done on the pointer to
290 these trees, and not on their value. */
292 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
293 tree chrec_not_analyzed_yet
;
295 /* Reserved to the cases where the analyzer has detected an
296 undecidable property at compile time. */
297 tree chrec_dont_know
;
299 /* When the analyzer has detected that a property will never
300 happen, then it qualifies it with chrec_known. */
303 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
306 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
308 static inline struct scev_info_str
*
309 new_scev_info_str (basic_block instantiated_below
, tree var
)
311 struct scev_info_str
*res
;
313 res
= ggc_alloc_scev_info_str ();
314 res
->name_version
= SSA_NAME_VERSION (var
);
315 res
->chrec
= chrec_not_analyzed_yet
;
316 res
->instantiated_below
= instantiated_below
->index
;
321 /* Computes a hash function for database element ELT. */
323 static inline hashval_t
324 hash_scev_info (const void *elt_
)
326 const struct scev_info_str
*elt
= (const struct scev_info_str
*) elt_
;
327 return elt
->name_version
^ elt
->instantiated_below
;
330 /* Compares database elements E1 and E2. */
333 eq_scev_info (const void *e1
, const void *e2
)
335 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
336 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
338 return (elt1
->name_version
== elt2
->name_version
339 && elt1
->instantiated_below
== elt2
->instantiated_below
);
342 /* Deletes database element E. */
345 del_scev_info (void *e
)
351 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
352 A first query on VAR returns chrec_not_analyzed_yet. */
355 find_var_scev_info (basic_block instantiated_below
, tree var
)
357 struct scev_info_str
*res
;
358 struct scev_info_str tmp
;
361 tmp
.name_version
= SSA_NAME_VERSION (var
);
362 tmp
.instantiated_below
= instantiated_below
->index
;
363 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
366 *slot
= new_scev_info_str (instantiated_below
, var
);
367 res
= (struct scev_info_str
*) *slot
;
372 /* Return true when CHREC contains symbolic names defined in
376 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
380 if (chrec
== NULL_TREE
)
383 if (is_gimple_min_invariant (chrec
))
386 if (TREE_CODE (chrec
) == SSA_NAME
)
389 loop_p def_loop
, loop
;
391 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
394 def
= SSA_NAME_DEF_STMT (chrec
);
395 def_loop
= loop_containing_stmt (def
);
396 loop
= get_loop (cfun
, loop_nb
);
398 if (def_loop
== NULL
)
401 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
407 n
= TREE_OPERAND_LENGTH (chrec
);
408 for (i
= 0; i
< n
; i
++)
409 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
415 /* Return true when PHI is a loop-phi-node. */
418 loop_phi_node_p (gimple phi
)
420 /* The implementation of this function is based on the following
421 property: "all the loop-phi-nodes of a loop are contained in the
422 loop's header basic block". */
424 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
427 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
428 In general, in the case of multivariate evolutions we want to get
429 the evolution in different loops. LOOP specifies the level for
430 which to get the evolution.
434 | for (j = 0; j < 100; j++)
436 | for (k = 0; k < 100; k++)
438 | i = k + j; - Here the value of i is a function of j, k.
440 | ... = i - Here the value of i is a function of j.
442 | ... = i - Here the value of i is a scalar.
448 | i_1 = phi (i_0, i_2)
452 This loop has the same effect as:
453 LOOP_1 has the same effect as:
457 The overall effect of the loop, "i_0 + 20" in the previous example,
458 is obtained by passing in the parameters: LOOP = 1,
459 EVOLUTION_FN = {i_0, +, 2}_1.
463 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
467 if (evolution_fn
== chrec_dont_know
)
468 return chrec_dont_know
;
470 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
472 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
474 if (inner_loop
== loop
475 || flow_loop_nested_p (loop
, inner_loop
))
477 tree nb_iter
= number_of_latch_executions (inner_loop
);
479 if (nb_iter
== chrec_dont_know
)
480 return chrec_dont_know
;
485 /* evolution_fn is the evolution function in LOOP. Get
486 its value in the nb_iter-th iteration. */
487 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
489 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
490 res
= instantiate_parameters (loop
, res
);
492 /* Continue the computation until ending on a parent of LOOP. */
493 return compute_overall_effect_of_inner_loop (loop
, res
);
500 /* If the evolution function is an invariant, there is nothing to do. */
501 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
505 return chrec_dont_know
;
508 /* Associate CHREC to SCALAR. */
511 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
515 if (TREE_CODE (scalar
) != SSA_NAME
)
518 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
522 if (dump_flags
& TDF_SCEV
)
524 fprintf (dump_file
, "(set_scalar_evolution \n");
525 fprintf (dump_file
, " instantiated_below = %d \n",
526 instantiated_below
->index
);
527 fprintf (dump_file
, " (scalar = ");
528 print_generic_expr (dump_file
, scalar
, 0);
529 fprintf (dump_file
, ")\n (scalar_evolution = ");
530 print_generic_expr (dump_file
, chrec
, 0);
531 fprintf (dump_file
, "))\n");
533 if (dump_flags
& TDF_STATS
)
537 *scalar_info
= chrec
;
540 /* Retrieve the chrec associated to SCALAR instantiated below
541 INSTANTIATED_BELOW block. */
544 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
550 if (dump_flags
& TDF_SCEV
)
552 fprintf (dump_file
, "(get_scalar_evolution \n");
553 fprintf (dump_file
, " (scalar = ");
554 print_generic_expr (dump_file
, scalar
, 0);
555 fprintf (dump_file
, ")\n");
557 if (dump_flags
& TDF_STATS
)
561 switch (TREE_CODE (scalar
))
564 res
= *find_var_scev_info (instantiated_below
, scalar
);
574 res
= chrec_not_analyzed_yet
;
578 if (dump_file
&& (dump_flags
& TDF_SCEV
))
580 fprintf (dump_file
, " (scalar_evolution = ");
581 print_generic_expr (dump_file
, res
, 0);
582 fprintf (dump_file
, "))\n");
588 /* Helper function for add_to_evolution. Returns the evolution
589 function for an assignment of the form "a = b + c", where "a" and
590 "b" are on the strongly connected component. CHREC_BEFORE is the
591 information that we already have collected up to this point.
592 TO_ADD is the evolution of "c".
594 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
595 evolution the expression TO_ADD, otherwise construct an evolution
596 part for this loop. */
599 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
602 tree type
, left
, right
;
603 struct loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
605 switch (TREE_CODE (chrec_before
))
607 case POLYNOMIAL_CHREC
:
608 chloop
= get_chrec_loop (chrec_before
);
610 || flow_loop_nested_p (chloop
, loop
))
614 type
= chrec_type (chrec_before
);
616 /* When there is no evolution part in this loop, build it. */
621 right
= SCALAR_FLOAT_TYPE_P (type
)
622 ? build_real (type
, dconst0
)
623 : build_int_cst (type
, 0);
627 var
= CHREC_VARIABLE (chrec_before
);
628 left
= CHREC_LEFT (chrec_before
);
629 right
= CHREC_RIGHT (chrec_before
);
632 to_add
= chrec_convert (type
, to_add
, at_stmt
);
633 right
= chrec_convert_rhs (type
, right
, at_stmt
);
634 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
635 return build_polynomial_chrec (var
, left
, right
);
639 gcc_assert (flow_loop_nested_p (loop
, chloop
));
641 /* Search the evolution in LOOP_NB. */
642 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
644 right
= CHREC_RIGHT (chrec_before
);
645 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
646 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
651 /* These nodes do not depend on a loop. */
652 if (chrec_before
== chrec_dont_know
)
653 return chrec_dont_know
;
656 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
657 return build_polynomial_chrec (loop_nb
, left
, right
);
661 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
664 Description (provided for completeness, for those who read code in
665 a plane, and for my poor 62 bytes brain that would have forgotten
666 all this in the next two or three months):
668 The algorithm of translation of programs from the SSA representation
669 into the chrecs syntax is based on a pattern matching. After having
670 reconstructed the overall tree expression for a loop, there are only
671 two cases that can arise:
673 1. a = loop-phi (init, a + expr)
674 2. a = loop-phi (init, expr)
676 where EXPR is either a scalar constant with respect to the analyzed
677 loop (this is a degree 0 polynomial), or an expression containing
678 other loop-phi definitions (these are higher degree polynomials).
685 | a = phi (init, a + 5)
692 | a = phi (inita, 2 * b + 3)
693 | b = phi (initb, b + 1)
696 For the first case, the semantics of the SSA representation is:
698 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
700 that is, there is a loop index "x" that determines the scalar value
701 of the variable during the loop execution. During the first
702 iteration, the value is that of the initial condition INIT, while
703 during the subsequent iterations, it is the sum of the initial
704 condition with the sum of all the values of EXPR from the initial
705 iteration to the before last considered iteration.
707 For the second case, the semantics of the SSA program is:
709 | a (x) = init, if x = 0;
710 | expr (x - 1), otherwise.
712 The second case corresponds to the PEELED_CHREC, whose syntax is
713 close to the syntax of a loop-phi-node:
715 | phi (init, expr) vs. (init, expr)_x
717 The proof of the translation algorithm for the first case is a
718 proof by structural induction based on the degree of EXPR.
721 When EXPR is a constant with respect to the analyzed loop, or in
722 other words when EXPR is a polynomial of degree 0, the evolution of
723 the variable A in the loop is an affine function with an initial
724 condition INIT, and a step EXPR. In order to show this, we start
725 from the semantics of the SSA representation:
727 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
729 and since "expr (j)" is a constant with respect to "j",
731 f (x) = init + x * expr
733 Finally, based on the semantics of the pure sum chrecs, by
734 identification we get the corresponding chrecs syntax:
736 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
737 f (x) -> {init, +, expr}_x
740 Suppose that EXPR is a polynomial of degree N with respect to the
741 analyzed loop_x for which we have already determined that it is
742 written under the chrecs syntax:
744 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
746 We start from the semantics of the SSA program:
748 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
750 | f (x) = init + \sum_{j = 0}^{x - 1}
751 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
753 | f (x) = init + \sum_{j = 0}^{x - 1}
754 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
756 | f (x) = init + \sum_{k = 0}^{n - 1}
757 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
759 | f (x) = init + \sum_{k = 0}^{n - 1}
760 | (b_k * \binom{x}{k + 1})
762 | f (x) = init + b_0 * \binom{x}{1} + ...
763 | + b_{n-1} * \binom{x}{n}
765 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
766 | + b_{n-1} * \binom{x}{n}
769 And finally from the definition of the chrecs syntax, we identify:
770 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
772 This shows the mechanism that stands behind the add_to_evolution
773 function. An important point is that the use of symbolic
774 parameters avoids the need of an analysis schedule.
781 | a = phi (inita, a + 2 + b)
782 | b = phi (initb, b + 1)
785 When analyzing "a", the algorithm keeps "b" symbolically:
787 | a -> {inita, +, 2 + b}_1
789 Then, after instantiation, the analyzer ends on the evolution:
791 | a -> {inita, +, 2 + initb, +, 1}_1
796 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
797 tree to_add
, gimple at_stmt
)
799 tree type
= chrec_type (to_add
);
800 tree res
= NULL_TREE
;
802 if (to_add
== NULL_TREE
)
805 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
806 instantiated at this point. */
807 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
808 /* This should not happen. */
809 return chrec_dont_know
;
811 if (dump_file
&& (dump_flags
& TDF_SCEV
))
813 fprintf (dump_file
, "(add_to_evolution \n");
814 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
815 fprintf (dump_file
, " (chrec_before = ");
816 print_generic_expr (dump_file
, chrec_before
, 0);
817 fprintf (dump_file
, ")\n (to_add = ");
818 print_generic_expr (dump_file
, to_add
, 0);
819 fprintf (dump_file
, ")\n");
822 if (code
== MINUS_EXPR
)
823 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
824 ? build_real (type
, dconstm1
)
825 : build_int_cst_type (type
, -1));
827 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
829 if (dump_file
&& (dump_flags
& TDF_SCEV
))
831 fprintf (dump_file
, " (res = ");
832 print_generic_expr (dump_file
, res
, 0);
833 fprintf (dump_file
, "))\n");
841 /* This section selects the loops that will be good candidates for the
842 scalar evolution analysis. For the moment, greedily select all the
843 loop nests we could analyze. */
845 /* For a loop with a single exit edge, return the COND_EXPR that
846 guards the exit edge. If the expression is too difficult to
847 analyze, then give up. */
850 get_loop_exit_condition (const struct loop
*loop
)
853 edge exit_edge
= single_exit (loop
);
855 if (dump_file
&& (dump_flags
& TDF_SCEV
))
856 fprintf (dump_file
, "(get_loop_exit_condition \n ");
862 stmt
= last_stmt (exit_edge
->src
);
863 if (gimple_code (stmt
) == GIMPLE_COND
)
867 if (dump_file
&& (dump_flags
& TDF_SCEV
))
869 print_gimple_stmt (dump_file
, res
, 0, 0);
870 fprintf (dump_file
, ")\n");
877 /* Depth first search algorithm. */
879 typedef enum t_bool
{
886 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
888 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
889 Return true if the strongly connected component has been found. */
892 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
893 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
894 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
896 t_bool res
= t_false
;
901 case POINTER_PLUS_EXPR
:
903 if (TREE_CODE (rhs0
) == SSA_NAME
)
905 if (TREE_CODE (rhs1
) == SSA_NAME
)
907 /* Match an assignment under the form:
910 /* We want only assignments of form "name + name" contribute to
911 LIMIT, as the other cases do not necessarily contribute to
912 the complexity of the expression. */
915 evol
= *evolution_of_loop
;
916 res
= follow_ssa_edge
917 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
920 *evolution_of_loop
= add_to_evolution
922 chrec_convert (type
, evol
, at_stmt
),
923 code
, rhs1
, at_stmt
);
925 else if (res
== t_false
)
927 res
= follow_ssa_edge
928 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
929 evolution_of_loop
, limit
);
932 *evolution_of_loop
= add_to_evolution
934 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
935 code
, rhs0
, at_stmt
);
937 else if (res
== t_dont_know
)
938 *evolution_of_loop
= chrec_dont_know
;
941 else if (res
== t_dont_know
)
942 *evolution_of_loop
= chrec_dont_know
;
947 /* Match an assignment under the form:
949 res
= follow_ssa_edge
950 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
951 evolution_of_loop
, limit
);
953 *evolution_of_loop
= add_to_evolution
954 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
956 code
, rhs1
, at_stmt
);
958 else if (res
== t_dont_know
)
959 *evolution_of_loop
= chrec_dont_know
;
963 else if (TREE_CODE (rhs1
) == SSA_NAME
)
965 /* Match an assignment under the form:
967 res
= follow_ssa_edge
968 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
969 evolution_of_loop
, limit
);
971 *evolution_of_loop
= add_to_evolution
972 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
974 code
, rhs0
, at_stmt
);
976 else if (res
== t_dont_know
)
977 *evolution_of_loop
= chrec_dont_know
;
981 /* Otherwise, match an assignment under the form:
983 /* And there is nothing to do. */
988 /* This case is under the form "opnd0 = rhs0 - rhs1". */
989 if (TREE_CODE (rhs0
) == SSA_NAME
)
991 /* Match an assignment under the form:
994 /* We want only assignments of form "name - name" contribute to
995 LIMIT, as the other cases do not necessarily contribute to
996 the complexity of the expression. */
997 if (TREE_CODE (rhs1
) == SSA_NAME
)
1000 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1001 evolution_of_loop
, limit
);
1003 *evolution_of_loop
= add_to_evolution
1004 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1005 MINUS_EXPR
, rhs1
, at_stmt
);
1007 else if (res
== t_dont_know
)
1008 *evolution_of_loop
= chrec_dont_know
;
1011 /* Otherwise, match an assignment under the form:
1013 /* And there is nothing to do. */
1024 /* Follow the ssa edge into the expression EXPR.
1025 Return true if the strongly connected component has been found. */
1028 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1029 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1031 enum tree_code code
= TREE_CODE (expr
);
1032 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1035 /* The EXPR is one of the following cases:
1039 - a POINTER_PLUS_EXPR,
1042 - other cases are not yet handled. */
1047 /* This assignment is under the form "a_1 = (cast) rhs. */
1048 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1049 halting_phi
, evolution_of_loop
, limit
);
1050 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1054 /* This assignment is under the form "a_1 = 7". */
1059 /* This assignment is under the form: "a_1 = b_2". */
1060 res
= follow_ssa_edge
1061 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1064 case POINTER_PLUS_EXPR
:
1067 /* This case is under the form "rhs0 +- rhs1". */
1068 rhs0
= TREE_OPERAND (expr
, 0);
1069 rhs1
= TREE_OPERAND (expr
, 1);
1070 type
= TREE_TYPE (rhs0
);
1071 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1072 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1073 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1074 halting_phi
, evolution_of_loop
, limit
);
1078 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1079 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1081 expr
= TREE_OPERAND (expr
, 0);
1082 rhs0
= TREE_OPERAND (expr
, 0);
1083 rhs1
= TREE_OPERAND (expr
, 1);
1084 type
= TREE_TYPE (rhs0
);
1085 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1086 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1087 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1088 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1089 halting_phi
, evolution_of_loop
, limit
);
1096 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1097 It must be handled as a copy assignment of the form a_1 = a_2. */
1098 rhs0
= ASSERT_EXPR_VAR (expr
);
1099 if (TREE_CODE (rhs0
) == SSA_NAME
)
1100 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1101 halting_phi
, evolution_of_loop
, limit
);
1114 /* Follow the ssa edge into the right hand side of an assignment STMT.
1115 Return true if the strongly connected component has been found. */
1118 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1119 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1121 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1122 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1128 /* This assignment is under the form "a_1 = (cast) rhs. */
1129 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1130 halting_phi
, evolution_of_loop
, limit
);
1131 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1134 case POINTER_PLUS_EXPR
:
1137 rhs1
= gimple_assign_rhs1 (stmt
);
1138 rhs2
= gimple_assign_rhs2 (stmt
);
1139 type
= TREE_TYPE (rhs1
);
1140 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1141 halting_phi
, evolution_of_loop
, limit
);
1145 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1146 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1147 halting_phi
, evolution_of_loop
, limit
);
1156 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1159 backedge_phi_arg_p (gimple phi
, int i
)
1161 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1163 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1164 about updating it anywhere, and this should work as well most of the
1166 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1172 /* Helper function for one branch of the condition-phi-node. Return
1173 true if the strongly connected component has been found following
1176 static inline t_bool
1177 follow_ssa_edge_in_condition_phi_branch (int i
,
1179 gimple condition_phi
,
1181 tree
*evolution_of_branch
,
1182 tree init_cond
, int limit
)
1184 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1185 *evolution_of_branch
= chrec_dont_know
;
1187 /* Do not follow back edges (they must belong to an irreducible loop, which
1188 we really do not want to worry about). */
1189 if (backedge_phi_arg_p (condition_phi
, i
))
1192 if (TREE_CODE (branch
) == SSA_NAME
)
1194 *evolution_of_branch
= init_cond
;
1195 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1196 evolution_of_branch
, limit
);
1199 /* This case occurs when one of the condition branches sets
1200 the variable to a constant: i.e. a phi-node like
1201 "a_2 = PHI <a_7(5), 2(6)>;".
1203 FIXME: This case have to be refined correctly:
1204 in some cases it is possible to say something better than
1205 chrec_dont_know, for example using a wrap-around notation. */
1209 /* This function merges the branches of a condition-phi-node in a
1213 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1214 gimple condition_phi
,
1216 tree
*evolution_of_loop
, int limit
)
1219 tree init
= *evolution_of_loop
;
1220 tree evolution_of_branch
;
1221 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1223 &evolution_of_branch
,
1225 if (res
== t_false
|| res
== t_dont_know
)
1228 *evolution_of_loop
= evolution_of_branch
;
1230 n
= gimple_phi_num_args (condition_phi
);
1231 for (i
= 1; i
< n
; i
++)
1233 /* Quickly give up when the evolution of one of the branches is
1235 if (*evolution_of_loop
== chrec_dont_know
)
1238 /* Increase the limit by the PHI argument number to avoid exponential
1239 time and memory complexity. */
1240 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1242 &evolution_of_branch
,
1244 if (res
== t_false
|| res
== t_dont_know
)
1247 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1248 evolution_of_branch
);
1254 /* Follow an SSA edge in an inner loop. It computes the overall
1255 effect of the loop, and following the symbolic initial conditions,
1256 it follows the edges in the parent loop. The inner loop is
1257 considered as a single statement. */
1260 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1261 gimple loop_phi_node
,
1263 tree
*evolution_of_loop
, int limit
)
1265 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1266 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1268 /* Sometimes, the inner loop is too difficult to analyze, and the
1269 result of the analysis is a symbolic parameter. */
1270 if (ev
== PHI_RESULT (loop_phi_node
))
1272 t_bool res
= t_false
;
1273 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1275 for (i
= 0; i
< n
; i
++)
1277 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1280 /* Follow the edges that exit the inner loop. */
1281 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1282 if (!flow_bb_inside_loop_p (loop
, bb
))
1283 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1285 evolution_of_loop
, limit
);
1290 /* If the path crosses this loop-phi, give up. */
1292 *evolution_of_loop
= chrec_dont_know
;
1297 /* Otherwise, compute the overall effect of the inner loop. */
1298 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1299 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1300 evolution_of_loop
, limit
);
1303 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1304 path that is analyzed on the return walk. */
1307 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1308 tree
*evolution_of_loop
, int limit
)
1310 struct loop
*def_loop
;
1312 if (gimple_nop_p (def
))
1315 /* Give up if the path is longer than the MAX that we allow. */
1316 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1319 def_loop
= loop_containing_stmt (def
);
1321 switch (gimple_code (def
))
1324 if (!loop_phi_node_p (def
))
1325 /* DEF is a condition-phi-node. Follow the branches, and
1326 record their evolutions. Finally, merge the collected
1327 information and set the approximation to the main
1329 return follow_ssa_edge_in_condition_phi
1330 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1332 /* When the analyzed phi is the halting_phi, the
1333 depth-first search is over: we have found a path from
1334 the halting_phi to itself in the loop. */
1335 if (def
== halting_phi
)
1338 /* Otherwise, the evolution of the HALTING_PHI depends
1339 on the evolution of another loop-phi-node, i.e. the
1340 evolution function is a higher degree polynomial. */
1341 if (def_loop
== loop
)
1345 if (flow_loop_nested_p (loop
, def_loop
))
1346 return follow_ssa_edge_inner_loop_phi
1347 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1353 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1354 evolution_of_loop
, limit
);
1357 /* At this level of abstraction, the program is just a set
1358 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1359 other node to be handled. */
1366 /* Given a LOOP_PHI_NODE, this function determines the evolution
1367 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1370 analyze_evolution_in_loop (gimple loop_phi_node
,
1373 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1374 tree evolution_function
= chrec_not_analyzed_yet
;
1375 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1378 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1380 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1381 fprintf (dump_file
, " (loop_phi_node = ");
1382 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1383 fprintf (dump_file
, ")\n");
1386 for (i
= 0; i
< n
; i
++)
1388 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1393 /* Select the edges that enter the loop body. */
1394 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1395 if (!flow_bb_inside_loop_p (loop
, bb
))
1398 if (TREE_CODE (arg
) == SSA_NAME
)
1402 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1404 /* Pass in the initial condition to the follow edge function. */
1406 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1408 /* If ev_fn has no evolution in the inner loop, and the
1409 init_cond is not equal to ev_fn, then we have an
1410 ambiguity between two possible values, as we cannot know
1411 the number of iterations at this point. */
1412 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1413 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1414 && !operand_equal_p (init_cond
, ev_fn
, 0))
1415 ev_fn
= chrec_dont_know
;
1420 /* When it is impossible to go back on the same
1421 loop_phi_node by following the ssa edges, the
1422 evolution is represented by a peeled chrec, i.e. the
1423 first iteration, EV_FN has the value INIT_COND, then
1424 all the other iterations it has the value of ARG.
1425 For the moment, PEELED_CHREC nodes are not built. */
1427 ev_fn
= chrec_dont_know
;
1429 /* When there are multiple back edges of the loop (which in fact never
1430 happens currently, but nevertheless), merge their evolutions. */
1431 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1434 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1436 fprintf (dump_file
, " (evolution_function = ");
1437 print_generic_expr (dump_file
, evolution_function
, 0);
1438 fprintf (dump_file
, "))\n");
1441 return evolution_function
;
1444 /* Given a loop-phi-node, return the initial conditions of the
1445 variable on entry of the loop. When the CCP has propagated
1446 constants into the loop-phi-node, the initial condition is
1447 instantiated, otherwise the initial condition is kept symbolic.
1448 This analyzer does not analyze the evolution outside the current
1449 loop, and leaves this task to the on-demand tree reconstructor. */
1452 analyze_initial_condition (gimple loop_phi_node
)
1455 tree init_cond
= chrec_not_analyzed_yet
;
1456 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1458 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1460 fprintf (dump_file
, "(analyze_initial_condition \n");
1461 fprintf (dump_file
, " (loop_phi_node = \n");
1462 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1463 fprintf (dump_file
, ")\n");
1466 n
= gimple_phi_num_args (loop_phi_node
);
1467 for (i
= 0; i
< n
; i
++)
1469 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1470 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1472 /* When the branch is oriented to the loop's body, it does
1473 not contribute to the initial condition. */
1474 if (flow_bb_inside_loop_p (loop
, bb
))
1477 if (init_cond
== chrec_not_analyzed_yet
)
1483 if (TREE_CODE (branch
) == SSA_NAME
)
1485 init_cond
= chrec_dont_know
;
1489 init_cond
= chrec_merge (init_cond
, branch
);
1492 /* Ooops -- a loop without an entry??? */
1493 if (init_cond
== chrec_not_analyzed_yet
)
1494 init_cond
= chrec_dont_know
;
1496 /* During early loop unrolling we do not have fully constant propagated IL.
1497 Handle degenerate PHIs here to not miss important unrollings. */
1498 if (TREE_CODE (init_cond
) == SSA_NAME
)
1500 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1502 if (gimple_code (def
) == GIMPLE_PHI
1503 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1504 /* Only allow invariants here, otherwise we may break
1505 loop-closed SSA form. */
1506 && is_gimple_min_invariant (res
))
1510 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1512 fprintf (dump_file
, " (init_cond = ");
1513 print_generic_expr (dump_file
, init_cond
, 0);
1514 fprintf (dump_file
, "))\n");
1520 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1523 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1526 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1529 if (phi_loop
!= loop
)
1531 struct loop
*subloop
;
1532 tree evolution_fn
= analyze_scalar_evolution
1533 (phi_loop
, PHI_RESULT (loop_phi_node
));
1535 /* Dive one level deeper. */
1536 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1538 /* Interpret the subloop. */
1539 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1543 /* Otherwise really interpret the loop phi. */
1544 init_cond
= analyze_initial_condition (loop_phi_node
);
1545 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1547 /* Verify we maintained the correct initial condition throughout
1548 possible conversions in the SSA chain. */
1549 if (res
!= chrec_dont_know
)
1551 tree new_init
= res
;
1552 if (CONVERT_EXPR_P (res
)
1553 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1554 new_init
= fold_convert (TREE_TYPE (res
),
1555 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1556 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1557 new_init
= CHREC_LEFT (res
);
1558 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1559 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1560 || !operand_equal_p (init_cond
, new_init
, 0))
1561 return chrec_dont_know
;
1567 /* This function merges the branches of a condition-phi-node,
1568 contained in the outermost loop, and whose arguments are already
1572 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1574 int i
, n
= gimple_phi_num_args (condition_phi
);
1575 tree res
= chrec_not_analyzed_yet
;
1577 for (i
= 0; i
< n
; i
++)
1581 if (backedge_phi_arg_p (condition_phi
, i
))
1583 res
= chrec_dont_know
;
1587 branch_chrec
= analyze_scalar_evolution
1588 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1590 res
= chrec_merge (res
, branch_chrec
);
1596 /* Interpret the operation RHS1 OP RHS2. If we didn't
1597 analyze this node before, follow the definitions until ending
1598 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1599 return path, this function propagates evolutions (ala constant copy
1600 propagation). OPND1 is not a GIMPLE expression because we could
1601 analyze the effect of an inner loop: see interpret_loop_phi. */
1604 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1605 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1607 tree res
, chrec1
, chrec2
;
1610 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1612 if (is_gimple_min_invariant (rhs1
))
1613 return chrec_convert (type
, rhs1
, at_stmt
);
1615 if (code
== SSA_NAME
)
1616 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1619 if (code
== ASSERT_EXPR
)
1621 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1622 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1630 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1631 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1633 enum machine_mode mode
;
1634 HOST_WIDE_INT bitsize
, bitpos
;
1641 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1642 &bitsize
, &bitpos
, &offset
,
1643 &mode
, &unsignedp
, &volatilep
, false);
1645 if (TREE_CODE (base
) == MEM_REF
)
1647 rhs2
= TREE_OPERAND (base
, 1);
1648 rhs1
= TREE_OPERAND (base
, 0);
1650 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1651 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1652 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1653 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1654 chrec1
= instantiate_parameters (loop
, chrec1
);
1655 chrec2
= instantiate_parameters (loop
, chrec2
);
1656 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1660 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1661 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1665 if (offset
!= NULL_TREE
)
1667 chrec2
= analyze_scalar_evolution (loop
, offset
);
1668 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1669 chrec2
= instantiate_parameters (loop
, chrec2
);
1670 res
= chrec_fold_plus (type
, res
, chrec2
);
1675 gcc_assert ((bitpos
% BITS_PER_UNIT
) == 0);
1677 unitpos
= size_int (bitpos
/ BITS_PER_UNIT
);
1678 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1679 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1680 chrec3
= instantiate_parameters (loop
, chrec3
);
1681 res
= chrec_fold_plus (type
, res
, chrec3
);
1685 res
= chrec_dont_know
;
1688 case POINTER_PLUS_EXPR
:
1689 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1690 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1691 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1692 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1693 chrec1
= instantiate_parameters (loop
, chrec1
);
1694 chrec2
= instantiate_parameters (loop
, chrec2
);
1695 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1699 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1700 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1701 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1702 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1703 chrec1
= instantiate_parameters (loop
, chrec1
);
1704 chrec2
= instantiate_parameters (loop
, chrec2
);
1705 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1709 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1710 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1711 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1712 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1713 chrec1
= instantiate_parameters (loop
, chrec1
);
1714 chrec2
= instantiate_parameters (loop
, chrec2
);
1715 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1719 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1720 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1721 /* TYPE may be integer, real or complex, so use fold_convert. */
1722 chrec1
= instantiate_parameters (loop
, chrec1
);
1723 res
= chrec_fold_multiply (type
, chrec1
,
1724 fold_convert (type
, integer_minus_one_node
));
1728 /* Handle ~X as -1 - X. */
1729 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1730 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1731 chrec1
= instantiate_parameters (loop
, chrec1
);
1732 res
= chrec_fold_minus (type
,
1733 fold_convert (type
, integer_minus_one_node
),
1738 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1739 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1740 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1741 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1742 chrec1
= instantiate_parameters (loop
, chrec1
);
1743 chrec2
= instantiate_parameters (loop
, chrec2
);
1744 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1748 /* In case we have a truncation of a widened operation that in
1749 the truncated type has undefined overflow behavior analyze
1750 the operation done in an unsigned type of the same precision
1751 as the final truncation. We cannot derive a scalar evolution
1752 for the widened operation but for the truncated result. */
1753 if (TREE_CODE (type
) == INTEGER_TYPE
1754 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1755 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1756 && TYPE_OVERFLOW_UNDEFINED (type
)
1757 && TREE_CODE (rhs1
) == SSA_NAME
1758 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1759 && is_gimple_assign (def
)
1760 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1761 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1763 tree utype
= unsigned_type_for (type
);
1764 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1765 gimple_assign_rhs1 (def
),
1766 gimple_assign_rhs_code (def
),
1767 gimple_assign_rhs2 (def
));
1770 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1771 res
= chrec_convert (type
, chrec1
, at_stmt
);
1775 res
= chrec_dont_know
;
1782 /* Interpret the expression EXPR. */
1785 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1787 enum tree_code code
;
1788 tree type
= TREE_TYPE (expr
), op0
, op1
;
1790 if (automatically_generated_chrec_p (expr
))
1793 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1794 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1795 return chrec_dont_know
;
1797 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1799 return interpret_rhs_expr (loop
, at_stmt
, type
,
1803 /* Interpret the rhs of the assignment STMT. */
1806 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1808 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1809 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1811 return interpret_rhs_expr (loop
, stmt
, type
,
1812 gimple_assign_rhs1 (stmt
), code
,
1813 gimple_assign_rhs2 (stmt
));
1818 /* This section contains all the entry points:
1819 - number_of_iterations_in_loop,
1820 - analyze_scalar_evolution,
1821 - instantiate_parameters.
1824 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1825 common ancestor of DEF_LOOP and USE_LOOP. */
1828 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1829 struct loop
*def_loop
,
1835 if (def_loop
== wrto_loop
)
1838 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1839 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1841 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1844 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1847 /* Helper recursive function. */
1850 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1852 tree type
= TREE_TYPE (var
);
1855 struct loop
*def_loop
;
1857 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1858 return chrec_dont_know
;
1860 if (TREE_CODE (var
) != SSA_NAME
)
1861 return interpret_expr (loop
, NULL
, var
);
1863 def
= SSA_NAME_DEF_STMT (var
);
1864 bb
= gimple_bb (def
);
1865 def_loop
= bb
? bb
->loop_father
: NULL
;
1868 || !flow_bb_inside_loop_p (loop
, bb
))
1870 /* Keep the symbolic form. */
1875 if (res
!= chrec_not_analyzed_yet
)
1877 if (loop
!= bb
->loop_father
)
1878 res
= compute_scalar_evolution_in_loop
1879 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1884 if (loop
!= def_loop
)
1886 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1887 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1892 switch (gimple_code (def
))
1895 res
= interpret_gimple_assign (loop
, def
);
1899 if (loop_phi_node_p (def
))
1900 res
= interpret_loop_phi (loop
, def
);
1902 res
= interpret_condition_phi (loop
, def
);
1906 res
= chrec_dont_know
;
1912 /* Keep the symbolic form. */
1913 if (res
== chrec_dont_know
)
1916 if (loop
== def_loop
)
1917 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1922 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1923 LOOP. LOOP is the loop in which the variable is used.
1925 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1926 pointer to the statement that uses this variable, in order to
1927 determine the evolution function of the variable, use the following
1930 loop_p loop = loop_containing_stmt (stmt);
1931 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1932 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1936 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1940 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1942 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1943 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1944 fprintf (dump_file
, " (scalar = ");
1945 print_generic_expr (dump_file
, var
, 0);
1946 fprintf (dump_file
, ")\n");
1949 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1950 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1952 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1953 fprintf (dump_file
, ")\n");
1958 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
1961 analyze_scalar_evolution_for_address_of (struct loop
*loop
, tree var
)
1963 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
1966 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1967 WRTO_LOOP (which should be a superloop of USE_LOOP)
1969 FOLDED_CASTS is set to true if resolve_mixers used
1970 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1971 at the moment in order to keep things simple).
1973 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1976 for (i = 0; i < 100; i++) -- loop 1
1978 for (j = 0; j < 100; j++) -- loop 2
1985 for (t = 0; t < 100; t++) -- loop 3
1992 Both k1 and k2 are invariants in loop3, thus
1993 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1994 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1996 As they are invariant, it does not matter whether we consider their
1997 usage in loop 3 or loop 2, hence
1998 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1999 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2000 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2001 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2003 Similarly for their evolutions with respect to loop 1. The values of K2
2004 in the use in loop 2 vary independently on loop 1, thus we cannot express
2005 the evolution with respect to loop 1:
2006 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2007 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2008 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2009 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2011 The value of k2 in the use in loop 1 is known, though:
2012 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2013 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2017 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2018 tree version
, bool *folded_casts
)
2021 tree ev
= version
, tmp
;
2023 /* We cannot just do
2025 tmp = analyze_scalar_evolution (use_loop, version);
2026 ev = resolve_mixers (wrto_loop, tmp);
2028 as resolve_mixers would query the scalar evolution with respect to
2029 wrto_loop. For example, in the situation described in the function
2030 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2033 analyze_scalar_evolution (use_loop, version) = k2
2035 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2036 is 100, which is a wrong result, since we are interested in the
2039 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2040 each time checking that there is no evolution in the inner loop. */
2043 *folded_casts
= false;
2046 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2047 ev
= resolve_mixers (use_loop
, tmp
);
2049 if (folded_casts
&& tmp
!= ev
)
2050 *folded_casts
= true;
2052 if (use_loop
== wrto_loop
)
2055 /* If the value of the use changes in the inner loop, we cannot express
2056 its value in the outer loop (we might try to return interval chrec,
2057 but we do not have a user for it anyway) */
2058 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2060 return chrec_dont_know
;
2062 use_loop
= loop_outer (use_loop
);
2067 /* Hashtable helpers for a temporary hash-table used when
2068 instantiating a CHREC or resolving mixers. For this use
2069 instantiated_below is always the same. */
2071 struct instantiate_cache_type
2074 vec
<scev_info_str
> entries
;
2076 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
2077 ~instantiate_cache_type ();
2078 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
2079 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
2082 instantiate_cache_type::~instantiate_cache_type ()
2091 /* Cache to avoid infinite recursion when instantiating an SSA name.
2092 Live during the outermost instantiate_scev or resolve_mixers call. */
2093 static instantiate_cache_type
*global_cache
;
2095 /* Computes a hash function for database element ELT. */
2097 static inline hashval_t
2098 hash_idx_scev_info (const void *elt_
)
2100 unsigned idx
= ((size_t) elt_
) - 2;
2101 return hash_scev_info (&global_cache
->entries
[idx
]);
2104 /* Compares database elements E1 and E2. */
2107 eq_idx_scev_info (const void *e1
, const void *e2
)
2109 unsigned idx1
= ((size_t) e1
) - 2;
2110 return eq_scev_info (&global_cache
->entries
[idx1
], e2
);
2113 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2116 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2117 tree name
, basic_block instantiate_below
)
2121 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2122 cache
.entries
.create (10);
2126 e
.name_version
= SSA_NAME_VERSION (name
);
2127 e
.instantiated_below
= instantiate_below
->index
;
2128 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2129 hash_scev_info (&e
), INSERT
);
2132 e
.chrec
= chrec_not_analyzed_yet
;
2133 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2134 cache
.entries
.safe_push (e
);
2137 return ((size_t)*slot
) - 2;
2141 /* Return the closed_loop_phi node for VAR. If there is none, return
2145 loop_closed_phi_def (tree var
)
2150 gimple_stmt_iterator psi
;
2152 if (var
== NULL_TREE
2153 || TREE_CODE (var
) != SSA_NAME
)
2156 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2157 exit
= single_exit (loop
);
2161 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2163 phi
= gsi_stmt (psi
);
2164 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2165 return PHI_RESULT (phi
);
2171 static tree
instantiate_scev_r (basic_block
, struct loop
*, struct loop
*,
2174 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2175 and EVOLUTION_LOOP, that were left under a symbolic form.
2177 CHREC is an SSA_NAME to be instantiated.
2179 CACHE is the cache of already instantiated values.
2181 FOLD_CONVERSIONS should be set to true when the conversions that
2182 may wrap in signed/pointer type are folded, as long as the value of
2183 the chrec is preserved.
2185 SIZE_EXPR is used for computing the size of the expression to be
2186 instantiated, and to stop if it exceeds some limit. */
2189 instantiate_scev_name (basic_block instantiate_below
,
2190 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2192 bool fold_conversions
,
2196 struct loop
*def_loop
;
2197 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2199 /* A parameter (or loop invariant and we do not want to include
2200 evolutions in outer loops), nothing to do. */
2202 || loop_depth (def_bb
->loop_father
) == 0
2203 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2206 /* We cache the value of instantiated variable to avoid exponential
2207 time complexity due to reevaluations. We also store the convenient
2208 value in the cache in order to prevent infinite recursion -- we do
2209 not want to instantiate the SSA_NAME if it is in a mixer
2210 structure. This is used for avoiding the instantiation of
2211 recursively defined functions, such as:
2213 | a_2 -> {0, +, 1, +, a_2}_1 */
2215 unsigned si
= get_instantiated_value_entry (*global_cache
,
2216 chrec
, instantiate_below
);
2217 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2218 return global_cache
->get (si
);
2220 /* On recursion return chrec_dont_know. */
2221 global_cache
->set (si
, chrec_dont_know
);
2223 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2225 /* If the analysis yields a parametric chrec, instantiate the
2227 res
= analyze_scalar_evolution (def_loop
, chrec
);
2229 /* Don't instantiate default definitions. */
2230 if (TREE_CODE (res
) == SSA_NAME
2231 && SSA_NAME_IS_DEFAULT_DEF (res
))
2234 /* Don't instantiate loop-closed-ssa phi nodes. */
2235 else if (TREE_CODE (res
) == SSA_NAME
2236 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2237 > loop_depth (def_loop
))
2240 res
= loop_closed_phi_def (chrec
);
2244 /* When there is no loop_closed_phi_def, it means that the
2245 variable is not used after the loop: try to still compute the
2246 value of the variable when exiting the loop. */
2247 if (res
== NULL_TREE
)
2249 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2250 res
= analyze_scalar_evolution (loop
, chrec
);
2251 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2252 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2254 fold_conversions
, size_expr
);
2256 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2257 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2258 res
= chrec_dont_know
;
2261 else if (res
!= chrec_dont_know
)
2264 && def_bb
->loop_father
!= inner_loop
2265 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2266 /* ??? We could try to compute the overall effect of the loop here. */
2267 res
= chrec_dont_know
;
2269 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2271 fold_conversions
, size_expr
);
2274 /* Store the correct value to the cache. */
2275 global_cache
->set (si
, res
);
2279 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2280 and EVOLUTION_LOOP, that were left under a symbolic form.
2282 CHREC is a polynomial chain of recurrence to be instantiated.
2284 CACHE is the cache of already instantiated values.
2286 FOLD_CONVERSIONS should be set to true when the conversions that
2287 may wrap in signed/pointer type are folded, as long as the value of
2288 the chrec is preserved.
2290 SIZE_EXPR is used for computing the size of the expression to be
2291 instantiated, and to stop if it exceeds some limit. */
2294 instantiate_scev_poly (basic_block instantiate_below
,
2295 struct loop
*evolution_loop
, struct loop
*,
2296 tree chrec
, bool fold_conversions
, int size_expr
)
2299 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2300 get_chrec_loop (chrec
),
2301 CHREC_LEFT (chrec
), fold_conversions
,
2303 if (op0
== chrec_dont_know
)
2304 return chrec_dont_know
;
2306 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2307 get_chrec_loop (chrec
),
2308 CHREC_RIGHT (chrec
), fold_conversions
,
2310 if (op1
== chrec_dont_know
)
2311 return chrec_dont_know
;
2313 if (CHREC_LEFT (chrec
) != op0
2314 || CHREC_RIGHT (chrec
) != op1
)
2316 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2317 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2323 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2324 and EVOLUTION_LOOP, that were left under a symbolic form.
2326 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2328 CACHE is the cache of already instantiated values.
2330 FOLD_CONVERSIONS should be set to true when the conversions that
2331 may wrap in signed/pointer type are folded, as long as the value of
2332 the chrec is preserved.
2334 SIZE_EXPR is used for computing the size of the expression to be
2335 instantiated, and to stop if it exceeds some limit. */
2338 instantiate_scev_binary (basic_block instantiate_below
,
2339 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2340 tree chrec
, enum tree_code code
,
2341 tree type
, tree c0
, tree c1
,
2342 bool fold_conversions
, int size_expr
)
2345 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2346 c0
, fold_conversions
, size_expr
);
2347 if (op0
== chrec_dont_know
)
2348 return chrec_dont_know
;
2350 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2351 c1
, fold_conversions
, size_expr
);
2352 if (op1
== chrec_dont_know
)
2353 return chrec_dont_know
;
2358 op0
= chrec_convert (type
, op0
, NULL
);
2359 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2363 case POINTER_PLUS_EXPR
:
2365 return chrec_fold_plus (type
, op0
, op1
);
2368 return chrec_fold_minus (type
, op0
, op1
);
2371 return chrec_fold_multiply (type
, op0
, op1
);
2378 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2381 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2382 and EVOLUTION_LOOP, that were left under a symbolic form.
2384 "CHREC" is an array reference to be instantiated.
2386 CACHE is the cache of already instantiated values.
2388 FOLD_CONVERSIONS should be set to true when the conversions that
2389 may wrap in signed/pointer type are folded, as long as the value of
2390 the chrec is preserved.
2392 SIZE_EXPR is used for computing the size of the expression to be
2393 instantiated, and to stop if it exceeds some limit. */
2396 instantiate_array_ref (basic_block instantiate_below
,
2397 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2398 tree chrec
, bool fold_conversions
, int size_expr
)
2401 tree index
= TREE_OPERAND (chrec
, 1);
2402 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2404 fold_conversions
, size_expr
);
2406 if (op1
== chrec_dont_know
)
2407 return chrec_dont_know
;
2409 if (chrec
&& op1
== index
)
2412 res
= unshare_expr (chrec
);
2413 TREE_OPERAND (res
, 1) = op1
;
2417 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2418 and EVOLUTION_LOOP, that were left under a symbolic form.
2420 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2423 CACHE is the cache of already instantiated values.
2425 FOLD_CONVERSIONS should be set to true when the conversions that
2426 may wrap in signed/pointer type are folded, as long as the value of
2427 the chrec is preserved.
2429 SIZE_EXPR is used for computing the size of the expression to be
2430 instantiated, and to stop if it exceeds some limit. */
2433 instantiate_scev_convert (basic_block instantiate_below
,
2434 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2435 tree chrec
, tree type
, tree op
,
2436 bool fold_conversions
, int size_expr
)
2438 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2440 fold_conversions
, size_expr
);
2442 if (op0
== chrec_dont_know
)
2443 return chrec_dont_know
;
2445 if (fold_conversions
)
2447 tree tmp
= chrec_convert_aggressive (type
, op0
);
2452 if (chrec
&& op0
== op
)
2455 /* If we used chrec_convert_aggressive, we can no longer assume that
2456 signed chrecs do not overflow, as chrec_convert does, so avoid
2457 calling it in that case. */
2458 if (fold_conversions
)
2459 return fold_convert (type
, op0
);
2461 return chrec_convert (type
, op0
, NULL
);
2464 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2465 and EVOLUTION_LOOP, that were left under a symbolic form.
2467 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2468 Handle ~X as -1 - X.
2469 Handle -X as -1 * X.
2471 CACHE is the cache of already instantiated values.
2473 FOLD_CONVERSIONS should be set to true when the conversions that
2474 may wrap in signed/pointer type are folded, as long as the value of
2475 the chrec is preserved.
2477 SIZE_EXPR is used for computing the size of the expression to be
2478 instantiated, and to stop if it exceeds some limit. */
2481 instantiate_scev_not (basic_block instantiate_below
,
2482 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2484 enum tree_code code
, tree type
, tree op
,
2485 bool fold_conversions
, int size_expr
)
2487 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2489 fold_conversions
, size_expr
);
2491 if (op0
== chrec_dont_know
)
2492 return chrec_dont_know
;
2496 op0
= chrec_convert (type
, op0
, NULL
);
2501 return chrec_fold_minus
2502 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2505 return chrec_fold_multiply
2506 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2513 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2516 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2517 and EVOLUTION_LOOP, that were left under a symbolic form.
2519 CHREC is an expression with 3 operands to be instantiated.
2521 CACHE is the cache of already instantiated values.
2523 FOLD_CONVERSIONS should be set to true when the conversions that
2524 may wrap in signed/pointer type are folded, as long as the value of
2525 the chrec is preserved.
2527 SIZE_EXPR is used for computing the size of the expression to be
2528 instantiated, and to stop if it exceeds some limit. */
2531 instantiate_scev_3 (basic_block instantiate_below
,
2532 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2534 bool fold_conversions
, int size_expr
)
2537 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2538 inner_loop
, TREE_OPERAND (chrec
, 0),
2539 fold_conversions
, size_expr
);
2540 if (op0
== chrec_dont_know
)
2541 return chrec_dont_know
;
2543 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2544 inner_loop
, TREE_OPERAND (chrec
, 1),
2545 fold_conversions
, size_expr
);
2546 if (op1
== chrec_dont_know
)
2547 return chrec_dont_know
;
2549 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2550 inner_loop
, TREE_OPERAND (chrec
, 2),
2551 fold_conversions
, size_expr
);
2552 if (op2
== chrec_dont_know
)
2553 return chrec_dont_know
;
2555 if (op0
== TREE_OPERAND (chrec
, 0)
2556 && op1
== TREE_OPERAND (chrec
, 1)
2557 && op2
== TREE_OPERAND (chrec
, 2))
2560 return fold_build3 (TREE_CODE (chrec
),
2561 TREE_TYPE (chrec
), op0
, op1
, op2
);
2564 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2565 and EVOLUTION_LOOP, that were left under a symbolic form.
2567 CHREC is an expression with 2 operands to be instantiated.
2569 CACHE is the cache of already instantiated values.
2571 FOLD_CONVERSIONS should be set to true when the conversions that
2572 may wrap in signed/pointer type are folded, as long as the value of
2573 the chrec is preserved.
2575 SIZE_EXPR is used for computing the size of the expression to be
2576 instantiated, and to stop if it exceeds some limit. */
2579 instantiate_scev_2 (basic_block instantiate_below
,
2580 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2582 bool fold_conversions
, int size_expr
)
2585 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2586 inner_loop
, TREE_OPERAND (chrec
, 0),
2587 fold_conversions
, size_expr
);
2588 if (op0
== chrec_dont_know
)
2589 return chrec_dont_know
;
2591 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2592 inner_loop
, TREE_OPERAND (chrec
, 1),
2593 fold_conversions
, size_expr
);
2594 if (op1
== chrec_dont_know
)
2595 return chrec_dont_know
;
2597 if (op0
== TREE_OPERAND (chrec
, 0)
2598 && op1
== TREE_OPERAND (chrec
, 1))
2601 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2604 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2605 and EVOLUTION_LOOP, that were left under a symbolic form.
2607 CHREC is an expression with 2 operands to be instantiated.
2609 CACHE is the cache of already instantiated values.
2611 FOLD_CONVERSIONS should be set to true when the conversions that
2612 may wrap in signed/pointer type are folded, as long as the value of
2613 the chrec is preserved.
2615 SIZE_EXPR is used for computing the size of the expression to be
2616 instantiated, and to stop if it exceeds some limit. */
2619 instantiate_scev_1 (basic_block instantiate_below
,
2620 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2622 bool fold_conversions
, int size_expr
)
2624 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2625 inner_loop
, TREE_OPERAND (chrec
, 0),
2626 fold_conversions
, size_expr
);
2628 if (op0
== chrec_dont_know
)
2629 return chrec_dont_know
;
2631 if (op0
== TREE_OPERAND (chrec
, 0))
2634 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2637 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2638 and EVOLUTION_LOOP, that were left under a symbolic form.
2640 CHREC is the scalar evolution to instantiate.
2642 CACHE is the cache of already instantiated values.
2644 FOLD_CONVERSIONS should be set to true when the conversions that
2645 may wrap in signed/pointer type are folded, as long as the value of
2646 the chrec is preserved.
2648 SIZE_EXPR is used for computing the size of the expression to be
2649 instantiated, and to stop if it exceeds some limit. */
2652 instantiate_scev_r (basic_block instantiate_below
,
2653 struct loop
*evolution_loop
, struct loop
*inner_loop
,
2655 bool fold_conversions
, int size_expr
)
2657 /* Give up if the expression is larger than the MAX that we allow. */
2658 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2659 return chrec_dont_know
;
2661 if (chrec
== NULL_TREE
2662 || automatically_generated_chrec_p (chrec
)
2663 || is_gimple_min_invariant (chrec
))
2666 switch (TREE_CODE (chrec
))
2669 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2671 fold_conversions
, size_expr
);
2673 case POLYNOMIAL_CHREC
:
2674 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2676 fold_conversions
, size_expr
);
2678 case POINTER_PLUS_EXPR
:
2682 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2684 TREE_CODE (chrec
), chrec_type (chrec
),
2685 TREE_OPERAND (chrec
, 0),
2686 TREE_OPERAND (chrec
, 1),
2687 fold_conversions
, size_expr
);
2690 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2692 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2693 fold_conversions
, size_expr
);
2697 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2699 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2700 TREE_OPERAND (chrec
, 0),
2701 fold_conversions
, size_expr
);
2704 case SCEV_NOT_KNOWN
:
2705 return chrec_dont_know
;
2711 return instantiate_array_ref (instantiate_below
, evolution_loop
,
2713 fold_conversions
, size_expr
);
2719 if (VL_EXP_CLASS_P (chrec
))
2720 return chrec_dont_know
;
2722 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2725 return instantiate_scev_3 (instantiate_below
, evolution_loop
,
2727 fold_conversions
, size_expr
);
2730 return instantiate_scev_2 (instantiate_below
, evolution_loop
,
2732 fold_conversions
, size_expr
);
2735 return instantiate_scev_1 (instantiate_below
, evolution_loop
,
2737 fold_conversions
, size_expr
);
2746 /* Too complicated to handle. */
2747 return chrec_dont_know
;
2750 /* Analyze all the parameters of the chrec that were left under a
2751 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2752 recursive instantiation of parameters: a parameter is a variable
2753 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2754 a function parameter. */
2757 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2762 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2764 fprintf (dump_file
, "(instantiate_scev \n");
2765 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2766 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2767 fprintf (dump_file
, " (chrec = ");
2768 print_generic_expr (dump_file
, chrec
, 0);
2769 fprintf (dump_file
, ")\n");
2775 global_cache
= new instantiate_cache_type
;
2779 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2780 NULL
, chrec
, false, 0);
2784 delete global_cache
;
2785 global_cache
= NULL
;
2788 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2790 fprintf (dump_file
, " (res = ");
2791 print_generic_expr (dump_file
, res
, 0);
2792 fprintf (dump_file
, "))\n");
2798 /* Similar to instantiate_parameters, but does not introduce the
2799 evolutions in outer loops for LOOP invariants in CHREC, and does not
2800 care about causing overflows, as long as they do not affect value
2801 of an expression. */
2804 resolve_mixers (struct loop
*loop
, tree chrec
)
2809 global_cache
= new instantiate_cache_type
;
2813 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, NULL
,
2818 delete global_cache
;
2819 global_cache
= NULL
;
2825 /* Entry point for the analysis of the number of iterations pass.
2826 This function tries to safely approximate the number of iterations
2827 the loop will run. When this property is not decidable at compile
2828 time, the result is chrec_dont_know. Otherwise the result is a
2829 scalar or a symbolic parameter. When the number of iterations may
2830 be equal to zero and the property cannot be determined at compile
2831 time, the result is a COND_EXPR that represents in a symbolic form
2832 the conditions under which the number of iterations is not zero.
2834 Example of analysis: suppose that the loop has an exit condition:
2836 "if (b > 49) goto end_loop;"
2838 and that in a previous analysis we have determined that the
2839 variable 'b' has an evolution function:
2841 "EF = {23, +, 5}_2".
2843 When we evaluate the function at the point 5, i.e. the value of the
2844 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2845 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2846 the loop body has been executed 6 times. */
2849 number_of_latch_executions (struct loop
*loop
)
2852 struct tree_niter_desc niter_desc
;
2856 /* Determine whether the number of iterations in loop has already
2858 res
= loop
->nb_iterations
;
2862 may_be_zero
= NULL_TREE
;
2864 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2865 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2867 res
= chrec_dont_know
;
2868 exit
= single_exit (loop
);
2870 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2872 may_be_zero
= niter_desc
.may_be_zero
;
2873 res
= niter_desc
.niter
;
2876 if (res
== chrec_dont_know
2878 || integer_zerop (may_be_zero
))
2880 else if (integer_nonzerop (may_be_zero
))
2881 res
= build_int_cst (TREE_TYPE (res
), 0);
2883 else if (COMPARISON_CLASS_P (may_be_zero
))
2884 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2885 build_int_cst (TREE_TYPE (res
), 0), res
);
2887 res
= chrec_dont_know
;
2889 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2891 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2892 print_generic_expr (dump_file
, res
, 0);
2893 fprintf (dump_file
, "))\n");
2896 loop
->nb_iterations
= res
;
2900 /* Returns the number of executions of the exit condition of LOOP,
2901 i.e., the number by one higher than number_of_latch_executions.
2902 Note that unlike number_of_latch_executions, this number does
2903 not necessarily fit in the unsigned variant of the type of
2904 the control variable -- if the number of iterations is a constant,
2905 we return chrec_dont_know if adding one to number_of_latch_executions
2906 overflows; however, in case the number of iterations is symbolic
2907 expression, the caller is responsible for dealing with this
2908 the possible overflow. */
2911 number_of_exit_cond_executions (struct loop
*loop
)
2913 tree ret
= number_of_latch_executions (loop
);
2914 tree type
= chrec_type (ret
);
2916 if (chrec_contains_undetermined (ret
))
2919 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2920 if (TREE_CODE (ret
) == INTEGER_CST
2921 && TREE_OVERFLOW (ret
))
2922 return chrec_dont_know
;
2929 /* Counters for the stats. */
2935 unsigned nb_affine_multivar
;
2936 unsigned nb_higher_poly
;
2937 unsigned nb_chrec_dont_know
;
2938 unsigned nb_undetermined
;
2941 /* Reset the counters. */
2944 reset_chrecs_counters (struct chrec_stats
*stats
)
2946 stats
->nb_chrecs
= 0;
2947 stats
->nb_affine
= 0;
2948 stats
->nb_affine_multivar
= 0;
2949 stats
->nb_higher_poly
= 0;
2950 stats
->nb_chrec_dont_know
= 0;
2951 stats
->nb_undetermined
= 0;
2954 /* Dump the contents of a CHREC_STATS structure. */
2957 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2959 fprintf (file
, "\n(\n");
2960 fprintf (file
, "-----------------------------------------\n");
2961 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2962 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2963 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2964 stats
->nb_higher_poly
);
2965 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2966 fprintf (file
, "-----------------------------------------\n");
2967 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2968 fprintf (file
, "%d\twith undetermined coefficients\n",
2969 stats
->nb_undetermined
);
2970 fprintf (file
, "-----------------------------------------\n");
2971 fprintf (file
, "%d\tchrecs in the scev database\n",
2972 (int) htab_elements (scalar_evolution_info
));
2973 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2974 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2975 fprintf (file
, "-----------------------------------------\n");
2976 fprintf (file
, ")\n\n");
2979 /* Gather statistics about CHREC. */
2982 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2984 if (dump_file
&& (dump_flags
& TDF_STATS
))
2986 fprintf (dump_file
, "(classify_chrec ");
2987 print_generic_expr (dump_file
, chrec
, 0);
2988 fprintf (dump_file
, "\n");
2993 if (chrec
== NULL_TREE
)
2995 stats
->nb_undetermined
++;
2999 switch (TREE_CODE (chrec
))
3001 case POLYNOMIAL_CHREC
:
3002 if (evolution_function_is_affine_p (chrec
))
3004 if (dump_file
&& (dump_flags
& TDF_STATS
))
3005 fprintf (dump_file
, " affine_univariate\n");
3008 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
3010 if (dump_file
&& (dump_flags
& TDF_STATS
))
3011 fprintf (dump_file
, " affine_multivariate\n");
3012 stats
->nb_affine_multivar
++;
3016 if (dump_file
&& (dump_flags
& TDF_STATS
))
3017 fprintf (dump_file
, " higher_degree_polynomial\n");
3018 stats
->nb_higher_poly
++;
3027 if (chrec_contains_undetermined (chrec
))
3029 if (dump_file
&& (dump_flags
& TDF_STATS
))
3030 fprintf (dump_file
, " undetermined\n");
3031 stats
->nb_undetermined
++;
3034 if (dump_file
&& (dump_flags
& TDF_STATS
))
3035 fprintf (dump_file
, ")\n");
3038 /* Callback for htab_traverse, gathers information on chrecs in the
3042 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
3044 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
3046 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3051 /* Classify the chrecs of the whole database. */
3054 gather_stats_on_scev_database (void)
3056 struct chrec_stats stats
;
3061 reset_chrecs_counters (&stats
);
3063 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3066 dump_chrecs_stats (dump_file
, &stats
);
3074 initialize_scalar_evolutions_analyzer (void)
3076 /* The elements below are unique. */
3077 if (chrec_dont_know
== NULL_TREE
)
3079 chrec_not_analyzed_yet
= NULL_TREE
;
3080 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3081 chrec_known
= make_node (SCEV_KNOWN
);
3082 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3083 TREE_TYPE (chrec_known
) = void_type_node
;
3087 /* Initialize the analysis of scalar evolutions for LOOPS. */
3090 scev_initialize (void)
3096 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3099 initialize_scalar_evolutions_analyzer ();
3101 FOR_EACH_LOOP (li
, loop
, 0)
3103 loop
->nb_iterations
= NULL_TREE
;
3107 /* Return true if SCEV is initialized. */
3110 scev_initialized_p (void)
3112 return scalar_evolution_info
!= NULL
;
3115 /* Cleans up the information cached by the scalar evolutions analysis
3116 in the hash table. */
3119 scev_reset_htab (void)
3121 if (!scalar_evolution_info
)
3124 htab_empty (scalar_evolution_info
);
3127 /* Cleans up the information cached by the scalar evolutions analysis
3128 in the hash table and in the loop->nb_iterations. */
3141 FOR_EACH_LOOP (li
, loop
, 0)
3143 loop
->nb_iterations
= NULL_TREE
;
3147 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3148 respect to WRTO_LOOP and returns its base and step in IV if possible
3149 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3150 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3151 invariant in LOOP. Otherwise we require it to be an integer constant.
3153 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3154 because it is computed in signed arithmetics). Consequently, adding an
3157 for (i = IV->base; ; i += IV->step)
3159 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3160 false for the type of the induction variable, or you can prove that i does
3161 not wrap by some other argument. Otherwise, this might introduce undefined
3164 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3166 must be used instead. */
3169 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3170 affine_iv
*iv
, bool allow_nonconstant_step
)
3175 iv
->base
= NULL_TREE
;
3176 iv
->step
= NULL_TREE
;
3177 iv
->no_overflow
= false;
3179 type
= TREE_TYPE (op
);
3180 if (!POINTER_TYPE_P (type
)
3181 && !INTEGRAL_TYPE_P (type
))
3184 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3186 if (chrec_contains_undetermined (ev
)
3187 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3190 if (tree_does_not_contain_chrecs (ev
))
3193 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3194 iv
->no_overflow
= true;
3198 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3199 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3202 iv
->step
= CHREC_RIGHT (ev
);
3203 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3204 || tree_contains_chrecs (iv
->step
, NULL
))
3207 iv
->base
= CHREC_LEFT (ev
);
3208 if (tree_contains_chrecs (iv
->base
, NULL
))
3211 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3216 /* Finalize the scalar evolution analysis. */
3219 scev_finalize (void)
3221 if (!scalar_evolution_info
)
3223 htab_delete (scalar_evolution_info
);
3224 scalar_evolution_info
= NULL
;
3227 /* Returns true if the expression EXPR is considered to be too expensive
3228 for scev_const_prop. */
3231 expression_expensive_p (tree expr
)
3233 enum tree_code code
;
3235 if (is_gimple_val (expr
))
3238 code
= TREE_CODE (expr
);
3239 if (code
== TRUNC_DIV_EXPR
3240 || code
== CEIL_DIV_EXPR
3241 || code
== FLOOR_DIV_EXPR
3242 || code
== ROUND_DIV_EXPR
3243 || code
== TRUNC_MOD_EXPR
3244 || code
== CEIL_MOD_EXPR
3245 || code
== FLOOR_MOD_EXPR
3246 || code
== ROUND_MOD_EXPR
3247 || code
== EXACT_DIV_EXPR
)
3249 /* Division by power of two is usually cheap, so we allow it.
3250 Forbid anything else. */
3251 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3255 switch (TREE_CODE_CLASS (code
))
3258 case tcc_comparison
:
3259 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3264 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3271 /* Replace ssa names for that scev can prove they are constant by the
3272 appropriate constants. Also perform final value replacement in loops,
3273 in case the replacement expressions are cheap.
3275 We only consider SSA names defined by phi nodes; rest is left to the
3276 ordinary constant propagation pass. */
3279 scev_const_prop (void)
3282 tree name
, type
, ev
;
3284 struct loop
*loop
, *ex_loop
;
3285 bitmap ssa_names_to_remove
= NULL
;
3288 gimple_stmt_iterator psi
;
3290 if (number_of_loops (cfun
) <= 1)
3295 loop
= bb
->loop_father
;
3297 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3299 phi
= gsi_stmt (psi
);
3300 name
= PHI_RESULT (phi
);
3302 if (virtual_operand_p (name
))
3305 type
= TREE_TYPE (name
);
3307 if (!POINTER_TYPE_P (type
)
3308 && !INTEGRAL_TYPE_P (type
))
3311 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3312 if (!is_gimple_min_invariant (ev
)
3313 || !may_propagate_copy (name
, ev
))
3316 /* Replace the uses of the name. */
3318 replace_uses_by (name
, ev
);
3320 if (!ssa_names_to_remove
)
3321 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3322 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3326 /* Remove the ssa names that were replaced by constants. We do not
3327 remove them directly in the previous cycle, since this
3328 invalidates scev cache. */
3329 if (ssa_names_to_remove
)
3333 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3335 gimple_stmt_iterator psi
;
3336 name
= ssa_name (i
);
3337 phi
= SSA_NAME_DEF_STMT (name
);
3339 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3340 psi
= gsi_for_stmt (phi
);
3341 remove_phi_node (&psi
, true);
3344 BITMAP_FREE (ssa_names_to_remove
);
3348 /* Now the regular final value replacement. */
3349 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3352 tree def
, rslt
, niter
;
3353 gimple_stmt_iterator bsi
;
3355 /* If we do not know exact number of iterations of the loop, we cannot
3356 replace the final value. */
3357 exit
= single_exit (loop
);
3361 niter
= number_of_latch_executions (loop
);
3362 if (niter
== chrec_dont_know
)
3365 /* Ensure that it is possible to insert new statements somewhere. */
3366 if (!single_pred_p (exit
->dest
))
3367 split_loop_exit_edge (exit
);
3368 bsi
= gsi_after_labels (exit
->dest
);
3370 ex_loop
= superloop_at_depth (loop
,
3371 loop_depth (exit
->dest
->loop_father
) + 1);
3373 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3375 phi
= gsi_stmt (psi
);
3376 rslt
= PHI_RESULT (phi
);
3377 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3378 if (virtual_operand_p (def
))
3384 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3385 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3391 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3392 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3393 if (!tree_does_not_contain_chrecs (def
)
3394 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3395 /* Moving the computation from the loop may prolong life range
3396 of some ssa names, which may cause problems if they appear
3397 on abnormal edges. */
3398 || contains_abnormal_ssa_name_p (def
)
3399 /* Do not emit expensive expressions. The rationale is that
3400 when someone writes a code like
3402 while (n > 45) n -= 45;
3404 he probably knows that n is not large, and does not want it
3405 to be turned into n %= 45. */
3406 || expression_expensive_p (def
))
3408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3410 fprintf (dump_file
, "not replacing:\n ");
3411 print_gimple_stmt (dump_file
, phi
, 0, 0);
3412 fprintf (dump_file
, "\n");
3418 /* Eliminate the PHI node and replace it by a computation outside
3422 fprintf (dump_file
, "\nfinal value replacement:\n ");
3423 print_gimple_stmt (dump_file
, phi
, 0, 0);
3424 fprintf (dump_file
, " with\n ");
3426 def
= unshare_expr (def
);
3427 remove_phi_node (&psi
, false);
3429 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3430 true, GSI_SAME_STMT
);
3431 ass
= gimple_build_assign (rslt
, def
);
3432 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3435 print_gimple_stmt (dump_file
, ass
, 0, 0);
3436 fprintf (dump_file
, "\n");
3443 #include "gt-tree-scalar-evolution.h"