1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <s.pop@laposte.net>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 This pass analyzes the evolution of scalar variables in loop
26 structures. The algorithm is based on the SSA representation,
27 and on the loop hierarchy tree. This algorithm is not based on
28 the notion of versions of a variable, as it was the case for the
29 previous implementations of the scalar evolution algorithm, but
30 it assumes that each defined name is unique.
32 The notation used in this file is called "chains of recurrences",
33 and has been proposed by Eugene Zima, Robert Van Engelen, and
34 others for describing induction variables in programs. For example
35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36 when entering in the loop_1 and has a step 2 in this loop, in other
37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38 this chain of recurrence (or chrec [shrek]) can contain the name of
39 other variables, in which case they are called parametric chrecs.
40 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41 is the value of "a". In most of the cases these parametric chrecs
42 are fully instantiated before their use because symbolic names can
43 hide some difficult cases such as self-references described later
44 (see the Fibonacci example).
46 A short sketch of the algorithm is:
48 Given a scalar variable to be analyzed, follow the SSA edge to
51 - When the definition is a GIMPLE_ASSIGN: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2a: Illustration of the algorithm on nested loops.
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
158 Example 2b: Multivariate chains of recurrences.
171 Analyzing the access function of array A with
172 instantiate_parameters (loop_1, "j + k"), we obtain the
173 instantiation and the analysis of the scalar variables "j" and "k"
174 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
175 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
176 {0, +, 1}_1. To obtain the evolution function in loop_3 and
177 instantiate the scalar variables up to loop_1, one has to use:
178 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
179 The result of this call is {{0, +, 1}_1, +, 1}_2.
181 Example 3: Higher degree polynomials.
195 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
196 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
198 Example 4: Lucas, Fibonacci, or mixers in general.
210 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
211 following semantics: during the first iteration of the loop_1, the
212 variable contains the value 1, and then it contains the value "c".
213 Note that this syntax is close to the syntax of the loop-phi-node:
214 "a -> (1, c)_1" vs. "a = phi (1, c)".
216 The symbolic chrec representation contains all the semantics of the
217 original code. What is more difficult is to use this information.
219 Example 5: Flip-flops, or exchangers.
231 Based on these symbolic chrecs, it is possible to refine this
232 information into the more precise PERIODIC_CHRECs:
237 This transformation is not yet implemented.
241 You can find a more detailed description of the algorithm in:
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
243 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
244 this is a preliminary report and some of the details of the
245 algorithm have changed. I'm working on a research report that
246 updates the description of the algorithms to reflect the design
247 choices used in this implementation.
249 A set of slides show a high level overview of the algorithm and run
250 an example through the scalar evolution analyzer:
251 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
253 The slides that I have presented at the GCC Summit'04 are available
254 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
259 #include "coretypes.h"
260 #include "gimple-pretty-print.h"
261 #include "tree-flow.h"
263 #include "tree-chrec.h"
264 #include "tree-scalar-evolution.h"
265 #include "tree-pass.h"
268 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
270 /* The cached information about an SSA name VAR, claiming that below
271 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
274 struct GTY(()) scev_info_str
{
275 basic_block instantiated_below
;
280 /* Counters for the scev database. */
281 static unsigned nb_set_scev
= 0;
282 static unsigned nb_get_scev
= 0;
284 /* The following trees are unique elements. Thus the comparison of
285 another element to these elements should be done on the pointer to
286 these trees, and not on their value. */
288 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
289 tree chrec_not_analyzed_yet
;
291 /* Reserved to the cases where the analyzer has detected an
292 undecidable property at compile time. */
293 tree chrec_dont_know
;
295 /* When the analyzer has detected that a property will never
296 happen, then it qualifies it with chrec_known. */
299 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
302 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
304 static inline struct scev_info_str
*
305 new_scev_info_str (basic_block instantiated_below
, tree var
)
307 struct scev_info_str
*res
;
309 res
= ggc_alloc_scev_info_str ();
311 res
->chrec
= chrec_not_analyzed_yet
;
312 res
->instantiated_below
= instantiated_below
;
317 /* Computes a hash function for database element ELT. */
320 hash_scev_info (const void *elt
)
322 return SSA_NAME_VERSION (((const struct scev_info_str
*) elt
)->var
);
325 /* Compares database elements E1 and E2. */
328 eq_scev_info (const void *e1
, const void *e2
)
330 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
331 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
333 return (elt1
->var
== elt2
->var
334 && elt1
->instantiated_below
== elt2
->instantiated_below
);
337 /* Deletes database element E. */
340 del_scev_info (void *e
)
345 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
346 A first query on VAR returns chrec_not_analyzed_yet. */
349 find_var_scev_info (basic_block instantiated_below
, tree var
)
351 struct scev_info_str
*res
;
352 struct scev_info_str tmp
;
356 tmp
.instantiated_below
= instantiated_below
;
357 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
360 *slot
= new_scev_info_str (instantiated_below
, var
);
361 res
= (struct scev_info_str
*) *slot
;
366 /* Return true when CHREC contains symbolic names defined in
370 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
374 if (chrec
== NULL_TREE
)
377 if (is_gimple_min_invariant (chrec
))
380 if (TREE_CODE (chrec
) == SSA_NAME
)
383 loop_p def_loop
, loop
;
385 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
388 def
= SSA_NAME_DEF_STMT (chrec
);
389 def_loop
= loop_containing_stmt (def
);
390 loop
= get_loop (loop_nb
);
392 if (def_loop
== NULL
)
395 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
401 n
= TREE_OPERAND_LENGTH (chrec
);
402 for (i
= 0; i
< n
; i
++)
403 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
409 /* Return true when PHI is a loop-phi-node. */
412 loop_phi_node_p (gimple phi
)
414 /* The implementation of this function is based on the following
415 property: "all the loop-phi-nodes of a loop are contained in the
416 loop's header basic block". */
418 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
421 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
422 In general, in the case of multivariate evolutions we want to get
423 the evolution in different loops. LOOP specifies the level for
424 which to get the evolution.
428 | for (j = 0; j < 100; j++)
430 | for (k = 0; k < 100; k++)
432 | i = k + j; - Here the value of i is a function of j, k.
434 | ... = i - Here the value of i is a function of j.
436 | ... = i - Here the value of i is a scalar.
442 | i_1 = phi (i_0, i_2)
446 This loop has the same effect as:
447 LOOP_1 has the same effect as:
451 The overall effect of the loop, "i_0 + 20" in the previous example,
452 is obtained by passing in the parameters: LOOP = 1,
453 EVOLUTION_FN = {i_0, +, 2}_1.
457 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
461 if (evolution_fn
== chrec_dont_know
)
462 return chrec_dont_know
;
464 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
466 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
468 if (inner_loop
== loop
469 || flow_loop_nested_p (loop
, inner_loop
))
471 tree nb_iter
= number_of_latch_executions (inner_loop
);
473 if (nb_iter
== chrec_dont_know
)
474 return chrec_dont_know
;
479 /* evolution_fn is the evolution function in LOOP. Get
480 its value in the nb_iter-th iteration. */
481 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
483 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
484 res
= instantiate_parameters (loop
, res
);
486 /* Continue the computation until ending on a parent of LOOP. */
487 return compute_overall_effect_of_inner_loop (loop
, res
);
494 /* If the evolution function is an invariant, there is nothing to do. */
495 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
499 return chrec_dont_know
;
502 /* Determine whether the CHREC is always positive/negative. If the expression
503 cannot be statically analyzed, return false, otherwise set the answer into
507 chrec_is_positive (tree chrec
, bool *value
)
509 bool value0
, value1
, value2
;
510 tree end_value
, nb_iter
;
512 switch (TREE_CODE (chrec
))
514 case POLYNOMIAL_CHREC
:
515 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
516 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
519 /* FIXME -- overflows. */
520 if (value0
== value1
)
526 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
527 and the proof consists in showing that the sign never
528 changes during the execution of the loop, from 0 to
529 loop->nb_iterations. */
530 if (!evolution_function_is_affine_p (chrec
))
533 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
534 if (chrec_contains_undetermined (nb_iter
))
538 /* TODO -- If the test is after the exit, we may decrease the number of
539 iterations by one. */
541 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
544 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
546 if (!chrec_is_positive (end_value
, &value2
))
550 return value0
== value1
;
553 *value
= (tree_int_cst_sgn (chrec
) == 1);
561 /* Associate CHREC to SCALAR. */
564 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
568 if (TREE_CODE (scalar
) != SSA_NAME
)
571 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
575 if (dump_flags
& TDF_SCEV
)
577 fprintf (dump_file
, "(set_scalar_evolution \n");
578 fprintf (dump_file
, " instantiated_below = %d \n",
579 instantiated_below
->index
);
580 fprintf (dump_file
, " (scalar = ");
581 print_generic_expr (dump_file
, scalar
, 0);
582 fprintf (dump_file
, ")\n (scalar_evolution = ");
583 print_generic_expr (dump_file
, chrec
, 0);
584 fprintf (dump_file
, "))\n");
586 if (dump_flags
& TDF_STATS
)
590 *scalar_info
= chrec
;
593 /* Retrieve the chrec associated to SCALAR instantiated below
594 INSTANTIATED_BELOW block. */
597 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
603 if (dump_flags
& TDF_SCEV
)
605 fprintf (dump_file
, "(get_scalar_evolution \n");
606 fprintf (dump_file
, " (scalar = ");
607 print_generic_expr (dump_file
, scalar
, 0);
608 fprintf (dump_file
, ")\n");
610 if (dump_flags
& TDF_STATS
)
614 switch (TREE_CODE (scalar
))
617 res
= *find_var_scev_info (instantiated_below
, scalar
);
627 res
= chrec_not_analyzed_yet
;
631 if (dump_file
&& (dump_flags
& TDF_SCEV
))
633 fprintf (dump_file
, " (scalar_evolution = ");
634 print_generic_expr (dump_file
, res
, 0);
635 fprintf (dump_file
, "))\n");
641 /* Helper function for add_to_evolution. Returns the evolution
642 function for an assignment of the form "a = b + c", where "a" and
643 "b" are on the strongly connected component. CHREC_BEFORE is the
644 information that we already have collected up to this point.
645 TO_ADD is the evolution of "c".
647 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
648 evolution the expression TO_ADD, otherwise construct an evolution
649 part for this loop. */
652 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
655 tree type
, left
, right
;
656 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
658 switch (TREE_CODE (chrec_before
))
660 case POLYNOMIAL_CHREC
:
661 chloop
= get_chrec_loop (chrec_before
);
663 || flow_loop_nested_p (chloop
, loop
))
667 type
= chrec_type (chrec_before
);
669 /* When there is no evolution part in this loop, build it. */
674 right
= SCALAR_FLOAT_TYPE_P (type
)
675 ? build_real (type
, dconst0
)
676 : build_int_cst (type
, 0);
680 var
= CHREC_VARIABLE (chrec_before
);
681 left
= CHREC_LEFT (chrec_before
);
682 right
= CHREC_RIGHT (chrec_before
);
685 to_add
= chrec_convert (type
, to_add
, at_stmt
);
686 right
= chrec_convert_rhs (type
, right
, at_stmt
);
687 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
688 return build_polynomial_chrec (var
, left
, right
);
692 gcc_assert (flow_loop_nested_p (loop
, chloop
));
694 /* Search the evolution in LOOP_NB. */
695 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
697 right
= CHREC_RIGHT (chrec_before
);
698 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
699 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
704 /* These nodes do not depend on a loop. */
705 if (chrec_before
== chrec_dont_know
)
706 return chrec_dont_know
;
709 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
710 return build_polynomial_chrec (loop_nb
, left
, right
);
714 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
717 Description (provided for completeness, for those who read code in
718 a plane, and for my poor 62 bytes brain that would have forgotten
719 all this in the next two or three months):
721 The algorithm of translation of programs from the SSA representation
722 into the chrecs syntax is based on a pattern matching. After having
723 reconstructed the overall tree expression for a loop, there are only
724 two cases that can arise:
726 1. a = loop-phi (init, a + expr)
727 2. a = loop-phi (init, expr)
729 where EXPR is either a scalar constant with respect to the analyzed
730 loop (this is a degree 0 polynomial), or an expression containing
731 other loop-phi definitions (these are higher degree polynomials).
738 | a = phi (init, a + 5)
745 | a = phi (inita, 2 * b + 3)
746 | b = phi (initb, b + 1)
749 For the first case, the semantics of the SSA representation is:
751 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
753 that is, there is a loop index "x" that determines the scalar value
754 of the variable during the loop execution. During the first
755 iteration, the value is that of the initial condition INIT, while
756 during the subsequent iterations, it is the sum of the initial
757 condition with the sum of all the values of EXPR from the initial
758 iteration to the before last considered iteration.
760 For the second case, the semantics of the SSA program is:
762 | a (x) = init, if x = 0;
763 | expr (x - 1), otherwise.
765 The second case corresponds to the PEELED_CHREC, whose syntax is
766 close to the syntax of a loop-phi-node:
768 | phi (init, expr) vs. (init, expr)_x
770 The proof of the translation algorithm for the first case is a
771 proof by structural induction based on the degree of EXPR.
774 When EXPR is a constant with respect to the analyzed loop, or in
775 other words when EXPR is a polynomial of degree 0, the evolution of
776 the variable A in the loop is an affine function with an initial
777 condition INIT, and a step EXPR. In order to show this, we start
778 from the semantics of the SSA representation:
780 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
782 and since "expr (j)" is a constant with respect to "j",
784 f (x) = init + x * expr
786 Finally, based on the semantics of the pure sum chrecs, by
787 identification we get the corresponding chrecs syntax:
789 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
790 f (x) -> {init, +, expr}_x
793 Suppose that EXPR is a polynomial of degree N with respect to the
794 analyzed loop_x for which we have already determined that it is
795 written under the chrecs syntax:
797 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
799 We start from the semantics of the SSA program:
801 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
803 | f (x) = init + \sum_{j = 0}^{x - 1}
804 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
806 | f (x) = init + \sum_{j = 0}^{x - 1}
807 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
809 | f (x) = init + \sum_{k = 0}^{n - 1}
810 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
812 | f (x) = init + \sum_{k = 0}^{n - 1}
813 | (b_k * \binom{x}{k + 1})
815 | f (x) = init + b_0 * \binom{x}{1} + ...
816 | + b_{n-1} * \binom{x}{n}
818 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
819 | + b_{n-1} * \binom{x}{n}
822 And finally from the definition of the chrecs syntax, we identify:
823 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
825 This shows the mechanism that stands behind the add_to_evolution
826 function. An important point is that the use of symbolic
827 parameters avoids the need of an analysis schedule.
834 | a = phi (inita, a + 2 + b)
835 | b = phi (initb, b + 1)
838 When analyzing "a", the algorithm keeps "b" symbolically:
840 | a -> {inita, +, 2 + b}_1
842 Then, after instantiation, the analyzer ends on the evolution:
844 | a -> {inita, +, 2 + initb, +, 1}_1
849 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
850 tree to_add
, gimple at_stmt
)
852 tree type
= chrec_type (to_add
);
853 tree res
= NULL_TREE
;
855 if (to_add
== NULL_TREE
)
858 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
859 instantiated at this point. */
860 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
861 /* This should not happen. */
862 return chrec_dont_know
;
864 if (dump_file
&& (dump_flags
& TDF_SCEV
))
866 fprintf (dump_file
, "(add_to_evolution \n");
867 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
868 fprintf (dump_file
, " (chrec_before = ");
869 print_generic_expr (dump_file
, chrec_before
, 0);
870 fprintf (dump_file
, ")\n (to_add = ");
871 print_generic_expr (dump_file
, to_add
, 0);
872 fprintf (dump_file
, ")\n");
875 if (code
== MINUS_EXPR
)
876 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
877 ? build_real (type
, dconstm1
)
878 : build_int_cst_type (type
, -1));
880 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
882 if (dump_file
&& (dump_flags
& TDF_SCEV
))
884 fprintf (dump_file
, " (res = ");
885 print_generic_expr (dump_file
, res
, 0);
886 fprintf (dump_file
, "))\n");
894 /* This section selects the loops that will be good candidates for the
895 scalar evolution analysis. For the moment, greedily select all the
896 loop nests we could analyze. */
898 /* For a loop with a single exit edge, return the COND_EXPR that
899 guards the exit edge. If the expression is too difficult to
900 analyze, then give up. */
903 get_loop_exit_condition (const struct loop
*loop
)
906 edge exit_edge
= single_exit (loop
);
908 if (dump_file
&& (dump_flags
& TDF_SCEV
))
909 fprintf (dump_file
, "(get_loop_exit_condition \n ");
915 stmt
= last_stmt (exit_edge
->src
);
916 if (gimple_code (stmt
) == GIMPLE_COND
)
920 if (dump_file
&& (dump_flags
& TDF_SCEV
))
922 print_gimple_stmt (dump_file
, res
, 0, 0);
923 fprintf (dump_file
, ")\n");
929 /* Recursively determine and enqueue the exit conditions for a loop. */
932 get_exit_conditions_rec (struct loop
*loop
,
933 VEC(gimple
,heap
) **exit_conditions
)
938 /* Recurse on the inner loops, then on the next (sibling) loops. */
939 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
940 get_exit_conditions_rec (loop
->next
, exit_conditions
);
942 if (single_exit (loop
))
944 gimple loop_condition
= get_loop_exit_condition (loop
);
947 VEC_safe_push (gimple
, heap
, *exit_conditions
, loop_condition
);
951 /* Select the candidate loop nests for the analysis. This function
952 initializes the EXIT_CONDITIONS array. */
955 select_loops_exit_conditions (VEC(gimple
,heap
) **exit_conditions
)
957 struct loop
*function_body
= current_loops
->tree_root
;
959 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
963 /* Depth first search algorithm. */
965 typedef enum t_bool
{
972 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
974 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
975 Return true if the strongly connected component has been found. */
978 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
979 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
980 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
982 t_bool res
= t_false
;
987 case POINTER_PLUS_EXPR
:
989 if (TREE_CODE (rhs0
) == SSA_NAME
)
991 if (TREE_CODE (rhs1
) == SSA_NAME
)
993 /* Match an assignment under the form:
996 /* We want only assignments of form "name + name" contribute to
997 LIMIT, as the other cases do not necessarily contribute to
998 the complexity of the expression. */
1001 evol
= *evolution_of_loop
;
1002 res
= follow_ssa_edge
1003 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
1006 *evolution_of_loop
= add_to_evolution
1008 chrec_convert (type
, evol
, at_stmt
),
1009 code
, rhs1
, at_stmt
);
1011 else if (res
== t_false
)
1013 res
= follow_ssa_edge
1014 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1015 evolution_of_loop
, limit
);
1018 *evolution_of_loop
= add_to_evolution
1020 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1021 code
, rhs0
, at_stmt
);
1023 else if (res
== t_dont_know
)
1024 *evolution_of_loop
= chrec_dont_know
;
1027 else if (res
== t_dont_know
)
1028 *evolution_of_loop
= chrec_dont_know
;
1033 /* Match an assignment under the form:
1035 res
= follow_ssa_edge
1036 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1037 evolution_of_loop
, limit
);
1039 *evolution_of_loop
= add_to_evolution
1040 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1042 code
, rhs1
, at_stmt
);
1044 else if (res
== t_dont_know
)
1045 *evolution_of_loop
= chrec_dont_know
;
1049 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1051 /* Match an assignment under the form:
1053 res
= follow_ssa_edge
1054 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1055 evolution_of_loop
, limit
);
1057 *evolution_of_loop
= add_to_evolution
1058 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1060 code
, rhs0
, at_stmt
);
1062 else if (res
== t_dont_know
)
1063 *evolution_of_loop
= chrec_dont_know
;
1067 /* Otherwise, match an assignment under the form:
1069 /* And there is nothing to do. */
1074 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1075 if (TREE_CODE (rhs0
) == SSA_NAME
)
1077 /* Match an assignment under the form:
1080 /* We want only assignments of form "name - name" contribute to
1081 LIMIT, as the other cases do not necessarily contribute to
1082 the complexity of the expression. */
1083 if (TREE_CODE (rhs1
) == SSA_NAME
)
1086 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1087 evolution_of_loop
, limit
);
1089 *evolution_of_loop
= add_to_evolution
1090 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1091 MINUS_EXPR
, rhs1
, at_stmt
);
1093 else if (res
== t_dont_know
)
1094 *evolution_of_loop
= chrec_dont_know
;
1097 /* Otherwise, match an assignment under the form:
1099 /* And there is nothing to do. */
1110 /* Follow the ssa edge into the expression EXPR.
1111 Return true if the strongly connected component has been found. */
1114 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1115 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1117 enum tree_code code
= TREE_CODE (expr
);
1118 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1121 /* The EXPR is one of the following cases:
1125 - a POINTER_PLUS_EXPR,
1128 - other cases are not yet handled. */
1133 /* This assignment is under the form "a_1 = (cast) rhs. */
1134 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1135 halting_phi
, evolution_of_loop
, limit
);
1136 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1140 /* This assignment is under the form "a_1 = 7". */
1145 /* This assignment is under the form: "a_1 = b_2". */
1146 res
= follow_ssa_edge
1147 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1150 case POINTER_PLUS_EXPR
:
1153 /* This case is under the form "rhs0 +- rhs1". */
1154 rhs0
= TREE_OPERAND (expr
, 0);
1155 rhs1
= TREE_OPERAND (expr
, 1);
1156 type
= TREE_TYPE (rhs0
);
1157 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1158 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1159 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1160 halting_phi
, evolution_of_loop
, limit
);
1164 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1165 if (TREE_CODE (TREE_OPERAND (expr
, 0)) == MEM_REF
)
1167 expr
= TREE_OPERAND (expr
, 0);
1168 rhs0
= TREE_OPERAND (expr
, 0);
1169 rhs1
= TREE_OPERAND (expr
, 1);
1170 type
= TREE_TYPE (rhs0
);
1171 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1172 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1173 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
,
1174 rhs0
, POINTER_PLUS_EXPR
, rhs1
,
1175 halting_phi
, evolution_of_loop
, limit
);
1182 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1183 It must be handled as a copy assignment of the form a_1 = a_2. */
1184 rhs0
= ASSERT_EXPR_VAR (expr
);
1185 if (TREE_CODE (rhs0
) == SSA_NAME
)
1186 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1187 halting_phi
, evolution_of_loop
, limit
);
1200 /* Follow the ssa edge into the right hand side of an assignment STMT.
1201 Return true if the strongly connected component has been found. */
1204 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1205 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1207 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1208 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1214 /* This assignment is under the form "a_1 = (cast) rhs. */
1215 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1216 halting_phi
, evolution_of_loop
, limit
);
1217 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1220 case POINTER_PLUS_EXPR
:
1223 rhs1
= gimple_assign_rhs1 (stmt
);
1224 rhs2
= gimple_assign_rhs2 (stmt
);
1225 type
= TREE_TYPE (rhs1
);
1226 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1227 halting_phi
, evolution_of_loop
, limit
);
1231 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1232 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1233 halting_phi
, evolution_of_loop
, limit
);
1242 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1245 backedge_phi_arg_p (gimple phi
, int i
)
1247 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1249 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1250 about updating it anywhere, and this should work as well most of the
1252 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1258 /* Helper function for one branch of the condition-phi-node. Return
1259 true if the strongly connected component has been found following
1262 static inline t_bool
1263 follow_ssa_edge_in_condition_phi_branch (int i
,
1265 gimple condition_phi
,
1267 tree
*evolution_of_branch
,
1268 tree init_cond
, int limit
)
1270 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1271 *evolution_of_branch
= chrec_dont_know
;
1273 /* Do not follow back edges (they must belong to an irreducible loop, which
1274 we really do not want to worry about). */
1275 if (backedge_phi_arg_p (condition_phi
, i
))
1278 if (TREE_CODE (branch
) == SSA_NAME
)
1280 *evolution_of_branch
= init_cond
;
1281 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1282 evolution_of_branch
, limit
);
1285 /* This case occurs when one of the condition branches sets
1286 the variable to a constant: i.e. a phi-node like
1287 "a_2 = PHI <a_7(5), 2(6)>;".
1289 FIXME: This case have to be refined correctly:
1290 in some cases it is possible to say something better than
1291 chrec_dont_know, for example using a wrap-around notation. */
1295 /* This function merges the branches of a condition-phi-node in a
1299 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1300 gimple condition_phi
,
1302 tree
*evolution_of_loop
, int limit
)
1305 tree init
= *evolution_of_loop
;
1306 tree evolution_of_branch
;
1307 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1309 &evolution_of_branch
,
1311 if (res
== t_false
|| res
== t_dont_know
)
1314 *evolution_of_loop
= evolution_of_branch
;
1316 n
= gimple_phi_num_args (condition_phi
);
1317 for (i
= 1; i
< n
; i
++)
1319 /* Quickly give up when the evolution of one of the branches is
1321 if (*evolution_of_loop
== chrec_dont_know
)
1324 /* Increase the limit by the PHI argument number to avoid exponential
1325 time and memory complexity. */
1326 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1328 &evolution_of_branch
,
1330 if (res
== t_false
|| res
== t_dont_know
)
1333 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1334 evolution_of_branch
);
1340 /* Follow an SSA edge in an inner loop. It computes the overall
1341 effect of the loop, and following the symbolic initial conditions,
1342 it follows the edges in the parent loop. The inner loop is
1343 considered as a single statement. */
1346 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1347 gimple loop_phi_node
,
1349 tree
*evolution_of_loop
, int limit
)
1351 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1352 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1354 /* Sometimes, the inner loop is too difficult to analyze, and the
1355 result of the analysis is a symbolic parameter. */
1356 if (ev
== PHI_RESULT (loop_phi_node
))
1358 t_bool res
= t_false
;
1359 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1361 for (i
= 0; i
< n
; i
++)
1363 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1366 /* Follow the edges that exit the inner loop. */
1367 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1368 if (!flow_bb_inside_loop_p (loop
, bb
))
1369 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1371 evolution_of_loop
, limit
);
1376 /* If the path crosses this loop-phi, give up. */
1378 *evolution_of_loop
= chrec_dont_know
;
1383 /* Otherwise, compute the overall effect of the inner loop. */
1384 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1385 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1386 evolution_of_loop
, limit
);
1389 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1390 path that is analyzed on the return walk. */
1393 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1394 tree
*evolution_of_loop
, int limit
)
1396 struct loop
*def_loop
;
1398 if (gimple_nop_p (def
))
1401 /* Give up if the path is longer than the MAX that we allow. */
1402 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1405 def_loop
= loop_containing_stmt (def
);
1407 switch (gimple_code (def
))
1410 if (!loop_phi_node_p (def
))
1411 /* DEF is a condition-phi-node. Follow the branches, and
1412 record their evolutions. Finally, merge the collected
1413 information and set the approximation to the main
1415 return follow_ssa_edge_in_condition_phi
1416 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1418 /* When the analyzed phi is the halting_phi, the
1419 depth-first search is over: we have found a path from
1420 the halting_phi to itself in the loop. */
1421 if (def
== halting_phi
)
1424 /* Otherwise, the evolution of the HALTING_PHI depends
1425 on the evolution of another loop-phi-node, i.e. the
1426 evolution function is a higher degree polynomial. */
1427 if (def_loop
== loop
)
1431 if (flow_loop_nested_p (loop
, def_loop
))
1432 return follow_ssa_edge_inner_loop_phi
1433 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1439 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1440 evolution_of_loop
, limit
);
1443 /* At this level of abstraction, the program is just a set
1444 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1445 other node to be handled. */
1452 /* Given a LOOP_PHI_NODE, this function determines the evolution
1453 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1456 analyze_evolution_in_loop (gimple loop_phi_node
,
1459 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1460 tree evolution_function
= chrec_not_analyzed_yet
;
1461 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1464 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1466 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1467 fprintf (dump_file
, " (loop_phi_node = ");
1468 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1469 fprintf (dump_file
, ")\n");
1472 for (i
= 0; i
< n
; i
++)
1474 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1479 /* Select the edges that enter the loop body. */
1480 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1481 if (!flow_bb_inside_loop_p (loop
, bb
))
1484 if (TREE_CODE (arg
) == SSA_NAME
)
1488 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1490 /* Pass in the initial condition to the follow edge function. */
1492 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1494 /* If ev_fn has no evolution in the inner loop, and the
1495 init_cond is not equal to ev_fn, then we have an
1496 ambiguity between two possible values, as we cannot know
1497 the number of iterations at this point. */
1498 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1499 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1500 && !operand_equal_p (init_cond
, ev_fn
, 0))
1501 ev_fn
= chrec_dont_know
;
1506 /* When it is impossible to go back on the same
1507 loop_phi_node by following the ssa edges, the
1508 evolution is represented by a peeled chrec, i.e. the
1509 first iteration, EV_FN has the value INIT_COND, then
1510 all the other iterations it has the value of ARG.
1511 For the moment, PEELED_CHREC nodes are not built. */
1513 ev_fn
= chrec_dont_know
;
1515 /* When there are multiple back edges of the loop (which in fact never
1516 happens currently, but nevertheless), merge their evolutions. */
1517 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1520 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1522 fprintf (dump_file
, " (evolution_function = ");
1523 print_generic_expr (dump_file
, evolution_function
, 0);
1524 fprintf (dump_file
, "))\n");
1527 return evolution_function
;
1530 /* Given a loop-phi-node, return the initial conditions of the
1531 variable on entry of the loop. When the CCP has propagated
1532 constants into the loop-phi-node, the initial condition is
1533 instantiated, otherwise the initial condition is kept symbolic.
1534 This analyzer does not analyze the evolution outside the current
1535 loop, and leaves this task to the on-demand tree reconstructor. */
1538 analyze_initial_condition (gimple loop_phi_node
)
1541 tree init_cond
= chrec_not_analyzed_yet
;
1542 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1544 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1546 fprintf (dump_file
, "(analyze_initial_condition \n");
1547 fprintf (dump_file
, " (loop_phi_node = \n");
1548 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1549 fprintf (dump_file
, ")\n");
1552 n
= gimple_phi_num_args (loop_phi_node
);
1553 for (i
= 0; i
< n
; i
++)
1555 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1556 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1558 /* When the branch is oriented to the loop's body, it does
1559 not contribute to the initial condition. */
1560 if (flow_bb_inside_loop_p (loop
, bb
))
1563 if (init_cond
== chrec_not_analyzed_yet
)
1569 if (TREE_CODE (branch
) == SSA_NAME
)
1571 init_cond
= chrec_dont_know
;
1575 init_cond
= chrec_merge (init_cond
, branch
);
1578 /* Ooops -- a loop without an entry??? */
1579 if (init_cond
== chrec_not_analyzed_yet
)
1580 init_cond
= chrec_dont_know
;
1582 /* During early loop unrolling we do not have fully constant propagated IL.
1583 Handle degenerate PHIs here to not miss important unrollings. */
1584 if (TREE_CODE (init_cond
) == SSA_NAME
)
1586 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1588 if (gimple_code (def
) == GIMPLE_PHI
1589 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1590 /* Only allow invariants here, otherwise we may break
1591 loop-closed SSA form. */
1592 && is_gimple_min_invariant (res
))
1596 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1598 fprintf (dump_file
, " (init_cond = ");
1599 print_generic_expr (dump_file
, init_cond
, 0);
1600 fprintf (dump_file
, "))\n");
1606 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1609 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1612 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1615 if (phi_loop
!= loop
)
1617 struct loop
*subloop
;
1618 tree evolution_fn
= analyze_scalar_evolution
1619 (phi_loop
, PHI_RESULT (loop_phi_node
));
1621 /* Dive one level deeper. */
1622 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1624 /* Interpret the subloop. */
1625 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1629 /* Otherwise really interpret the loop phi. */
1630 init_cond
= analyze_initial_condition (loop_phi_node
);
1631 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1633 /* Verify we maintained the correct initial condition throughout
1634 possible conversions in the SSA chain. */
1635 if (res
!= chrec_dont_know
)
1637 tree new_init
= res
;
1638 if (CONVERT_EXPR_P (res
)
1639 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1640 new_init
= fold_convert (TREE_TYPE (res
),
1641 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1642 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1643 new_init
= CHREC_LEFT (res
);
1644 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1645 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1646 || !operand_equal_p (init_cond
, new_init
, 0))
1647 return chrec_dont_know
;
1653 /* This function merges the branches of a condition-phi-node,
1654 contained in the outermost loop, and whose arguments are already
1658 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1660 int i
, n
= gimple_phi_num_args (condition_phi
);
1661 tree res
= chrec_not_analyzed_yet
;
1663 for (i
= 0; i
< n
; i
++)
1667 if (backedge_phi_arg_p (condition_phi
, i
))
1669 res
= chrec_dont_know
;
1673 branch_chrec
= analyze_scalar_evolution
1674 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1676 res
= chrec_merge (res
, branch_chrec
);
1682 /* Interpret the operation RHS1 OP RHS2. If we didn't
1683 analyze this node before, follow the definitions until ending
1684 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1685 return path, this function propagates evolutions (ala constant copy
1686 propagation). OPND1 is not a GIMPLE expression because we could
1687 analyze the effect of an inner loop: see interpret_loop_phi. */
1690 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1691 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1693 tree res
, chrec1
, chrec2
;
1695 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1697 if (is_gimple_min_invariant (rhs1
))
1698 return chrec_convert (type
, rhs1
, at_stmt
);
1700 if (code
== SSA_NAME
)
1701 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1704 if (code
== ASSERT_EXPR
)
1706 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1707 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1715 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1716 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) != MEM_REF
)
1718 res
= chrec_dont_know
;
1722 rhs2
= TREE_OPERAND (TREE_OPERAND (rhs1
, 0), 1);
1723 rhs1
= TREE_OPERAND (TREE_OPERAND (rhs1
, 0), 0);
1726 case POINTER_PLUS_EXPR
:
1727 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1728 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1729 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1730 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1731 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1735 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1736 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1737 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1738 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1739 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1743 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1744 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1745 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1746 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1747 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1751 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1752 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1753 /* TYPE may be integer, real or complex, so use fold_convert. */
1754 res
= chrec_fold_multiply (type
, chrec1
,
1755 fold_convert (type
, integer_minus_one_node
));
1759 /* Handle ~X as -1 - X. */
1760 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1761 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1762 res
= chrec_fold_minus (type
,
1763 fold_convert (type
, integer_minus_one_node
),
1768 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1769 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1770 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1771 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1772 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1776 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1777 res
= chrec_convert (type
, chrec1
, at_stmt
);
1781 res
= chrec_dont_know
;
1788 /* Interpret the expression EXPR. */
1791 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1793 enum tree_code code
;
1794 tree type
= TREE_TYPE (expr
), op0
, op1
;
1796 if (automatically_generated_chrec_p (expr
))
1799 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1800 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1801 return chrec_dont_know
;
1803 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1805 return interpret_rhs_expr (loop
, at_stmt
, type
,
1809 /* Interpret the rhs of the assignment STMT. */
1812 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1814 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1815 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1817 return interpret_rhs_expr (loop
, stmt
, type
,
1818 gimple_assign_rhs1 (stmt
), code
,
1819 gimple_assign_rhs2 (stmt
));
1824 /* This section contains all the entry points:
1825 - number_of_iterations_in_loop,
1826 - analyze_scalar_evolution,
1827 - instantiate_parameters.
1830 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1831 common ancestor of DEF_LOOP and USE_LOOP. */
1834 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1835 struct loop
*def_loop
,
1841 if (def_loop
== wrto_loop
)
1844 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1845 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1847 if (no_evolution_in_loop_p (res
, wrto_loop
->num
, &val
) && val
)
1850 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1853 /* Helper recursive function. */
1856 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1858 tree type
= TREE_TYPE (var
);
1861 struct loop
*def_loop
;
1863 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1864 return chrec_dont_know
;
1866 if (TREE_CODE (var
) != SSA_NAME
)
1867 return interpret_expr (loop
, NULL
, var
);
1869 def
= SSA_NAME_DEF_STMT (var
);
1870 bb
= gimple_bb (def
);
1871 def_loop
= bb
? bb
->loop_father
: NULL
;
1874 || !flow_bb_inside_loop_p (loop
, bb
))
1876 /* Keep the symbolic form. */
1881 if (res
!= chrec_not_analyzed_yet
)
1883 if (loop
!= bb
->loop_father
)
1884 res
= compute_scalar_evolution_in_loop
1885 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1890 if (loop
!= def_loop
)
1892 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1893 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1898 switch (gimple_code (def
))
1901 res
= interpret_gimple_assign (loop
, def
);
1905 if (loop_phi_node_p (def
))
1906 res
= interpret_loop_phi (loop
, def
);
1908 res
= interpret_condition_phi (loop
, def
);
1912 res
= chrec_dont_know
;
1918 /* Keep the symbolic form. */
1919 if (res
== chrec_dont_know
)
1922 if (loop
== def_loop
)
1923 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1928 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1929 LOOP. LOOP is the loop in which the variable is used.
1931 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1932 pointer to the statement that uses this variable, in order to
1933 determine the evolution function of the variable, use the following
1936 loop_p loop = loop_containing_stmt (stmt);
1937 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1938 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1942 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1946 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1948 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1949 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1950 fprintf (dump_file
, " (scalar = ");
1951 print_generic_expr (dump_file
, var
, 0);
1952 fprintf (dump_file
, ")\n");
1955 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1956 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1958 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1959 fprintf (dump_file
, ")\n");
1964 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1965 WRTO_LOOP (which should be a superloop of USE_LOOP)
1967 FOLDED_CASTS is set to true if resolve_mixers used
1968 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1969 at the moment in order to keep things simple).
1971 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1974 for (i = 0; i < 100; i++) -- loop 1
1976 for (j = 0; j < 100; j++) -- loop 2
1983 for (t = 0; t < 100; t++) -- loop 3
1990 Both k1 and k2 are invariants in loop3, thus
1991 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1992 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1994 As they are invariant, it does not matter whether we consider their
1995 usage in loop 3 or loop 2, hence
1996 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1997 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1998 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1999 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2001 Similarly for their evolutions with respect to loop 1. The values of K2
2002 in the use in loop 2 vary independently on loop 1, thus we cannot express
2003 the evolution with respect to loop 1:
2004 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2005 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2006 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2007 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2009 The value of k2 in the use in loop 1 is known, though:
2010 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2011 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2015 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2016 tree version
, bool *folded_casts
)
2019 tree ev
= version
, tmp
;
2021 /* We cannot just do
2023 tmp = analyze_scalar_evolution (use_loop, version);
2024 ev = resolve_mixers (wrto_loop, tmp);
2026 as resolve_mixers would query the scalar evolution with respect to
2027 wrto_loop. For example, in the situation described in the function
2028 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2031 analyze_scalar_evolution (use_loop, version) = k2
2033 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2034 is 100, which is a wrong result, since we are interested in the
2037 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2038 each time checking that there is no evolution in the inner loop. */
2041 *folded_casts
= false;
2044 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2045 ev
= resolve_mixers (use_loop
, tmp
);
2047 if (folded_casts
&& tmp
!= ev
)
2048 *folded_casts
= true;
2050 if (use_loop
== wrto_loop
)
2053 /* If the value of the use changes in the inner loop, we cannot express
2054 its value in the outer loop (we might try to return interval chrec,
2055 but we do not have a user for it anyway) */
2056 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2058 return chrec_dont_know
;
2060 use_loop
= loop_outer (use_loop
);
2064 /* Returns from CACHE the value for VERSION instantiated below
2065 INSTANTIATED_BELOW block. */
2068 get_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2071 struct scev_info_str
*info
, pattern
;
2073 pattern
.var
= version
;
2074 pattern
.instantiated_below
= instantiated_below
;
2075 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2083 /* Sets in CACHE the value of VERSION instantiated below basic block
2084 INSTANTIATED_BELOW to VAL. */
2087 set_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2088 tree version
, tree val
)
2090 struct scev_info_str
*info
, pattern
;
2093 pattern
.var
= version
;
2094 pattern
.instantiated_below
= instantiated_below
;
2095 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2098 *slot
= new_scev_info_str (instantiated_below
, version
);
2099 info
= (struct scev_info_str
*) *slot
;
2103 /* Return the closed_loop_phi node for VAR. If there is none, return
2107 loop_closed_phi_def (tree var
)
2112 gimple_stmt_iterator psi
;
2114 if (var
== NULL_TREE
2115 || TREE_CODE (var
) != SSA_NAME
)
2118 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2119 exit
= single_exit (loop
);
2123 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2125 phi
= gsi_stmt (psi
);
2126 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2127 return PHI_RESULT (phi
);
2133 static tree
instantiate_scev_r (basic_block
, struct loop
*, tree
, bool,
2136 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2137 and EVOLUTION_LOOP, that were left under a symbolic form.
2139 CHREC is an SSA_NAME to be instantiated.
2141 CACHE is the cache of already instantiated values.
2143 FOLD_CONVERSIONS should be set to true when the conversions that
2144 may wrap in signed/pointer type are folded, as long as the value of
2145 the chrec is preserved.
2147 SIZE_EXPR is used for computing the size of the expression to be
2148 instantiated, and to stop if it exceeds some limit. */
2151 instantiate_scev_name (basic_block instantiate_below
,
2152 struct loop
*evolution_loop
, tree chrec
,
2153 bool fold_conversions
, htab_t cache
, int size_expr
)
2156 struct loop
*def_loop
;
2157 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2159 /* A parameter (or loop invariant and we do not want to include
2160 evolutions in outer loops), nothing to do. */
2162 || loop_depth (def_bb
->loop_father
) == 0
2163 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2166 /* We cache the value of instantiated variable to avoid exponential
2167 time complexity due to reevaluations. We also store the convenient
2168 value in the cache in order to prevent infinite recursion -- we do
2169 not want to instantiate the SSA_NAME if it is in a mixer
2170 structure. This is used for avoiding the instantiation of
2171 recursively defined functions, such as:
2173 | a_2 -> {0, +, 1, +, a_2}_1 */
2175 res
= get_instantiated_value (cache
, instantiate_below
, chrec
);
2179 res
= chrec_dont_know
;
2180 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2182 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2184 /* If the analysis yields a parametric chrec, instantiate the
2186 res
= analyze_scalar_evolution (def_loop
, chrec
);
2188 /* Don't instantiate default definitions. */
2189 if (TREE_CODE (res
) == SSA_NAME
2190 && SSA_NAME_IS_DEFAULT_DEF (res
))
2193 /* Don't instantiate loop-closed-ssa phi nodes. */
2194 else if (TREE_CODE (res
) == SSA_NAME
2195 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2196 > loop_depth (def_loop
))
2199 res
= loop_closed_phi_def (chrec
);
2203 /* When there is no loop_closed_phi_def, it means that the
2204 variable is not used after the loop: try to still compute the
2205 value of the variable when exiting the loop. */
2206 if (res
== NULL_TREE
)
2208 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (chrec
));
2209 res
= analyze_scalar_evolution (loop
, chrec
);
2210 res
= compute_overall_effect_of_inner_loop (loop
, res
);
2211 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2212 fold_conversions
, cache
, size_expr
);
2214 else if (!dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2215 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2216 res
= chrec_dont_know
;
2219 else if (res
!= chrec_dont_know
)
2220 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2221 fold_conversions
, cache
, size_expr
);
2223 /* Store the correct value to the cache. */
2224 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2228 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2229 and EVOLUTION_LOOP, that were left under a symbolic form.
2231 CHREC is a polynomial chain of recurrence to be instantiated.
2233 CACHE is the cache of already instantiated values.
2235 FOLD_CONVERSIONS should be set to true when the conversions that
2236 may wrap in signed/pointer type are folded, as long as the value of
2237 the chrec is preserved.
2239 SIZE_EXPR is used for computing the size of the expression to be
2240 instantiated, and to stop if it exceeds some limit. */
2243 instantiate_scev_poly (basic_block instantiate_below
,
2244 struct loop
*evolution_loop
, tree chrec
,
2245 bool fold_conversions
, htab_t cache
, int size_expr
)
2248 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2249 CHREC_LEFT (chrec
), fold_conversions
, cache
,
2251 if (op0
== chrec_dont_know
)
2252 return chrec_dont_know
;
2254 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2255 CHREC_RIGHT (chrec
), fold_conversions
, cache
,
2257 if (op1
== chrec_dont_know
)
2258 return chrec_dont_know
;
2260 if (CHREC_LEFT (chrec
) != op0
2261 || CHREC_RIGHT (chrec
) != op1
)
2263 unsigned var
= CHREC_VARIABLE (chrec
);
2265 /* When the instantiated stride or base has an evolution in an
2266 innermost loop, return chrec_dont_know, as this is not a
2267 valid SCEV representation. In the reduced testcase for
2268 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2270 if ((tree_is_chrec (op0
) && CHREC_VARIABLE (op0
) > var
)
2271 || (tree_is_chrec (op1
) && CHREC_VARIABLE (op1
) > var
))
2272 return chrec_dont_know
;
2274 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2275 chrec
= build_polynomial_chrec (var
, op0
, op1
);
2281 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2282 and EVOLUTION_LOOP, that were left under a symbolic form.
2284 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2286 CACHE is the cache of already instantiated values.
2288 FOLD_CONVERSIONS should be set to true when the conversions that
2289 may wrap in signed/pointer type are folded, as long as the value of
2290 the chrec is preserved.
2292 SIZE_EXPR is used for computing the size of the expression to be
2293 instantiated, and to stop if it exceeds some limit. */
2296 instantiate_scev_binary (basic_block instantiate_below
,
2297 struct loop
*evolution_loop
, tree chrec
, enum tree_code code
,
2298 tree type
, tree c0
, tree c1
,
2299 bool fold_conversions
, htab_t cache
, int size_expr
)
2302 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2303 c0
, fold_conversions
, cache
,
2305 if (op0
== chrec_dont_know
)
2306 return chrec_dont_know
;
2308 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2309 c1
, fold_conversions
, cache
,
2311 if (op1
== chrec_dont_know
)
2312 return chrec_dont_know
;
2317 op0
= chrec_convert (type
, op0
, NULL
);
2318 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2322 case POINTER_PLUS_EXPR
:
2324 return chrec_fold_plus (type
, op0
, op1
);
2327 return chrec_fold_minus (type
, op0
, op1
);
2330 return chrec_fold_multiply (type
, op0
, op1
);
2337 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2340 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2341 and EVOLUTION_LOOP, that were left under a symbolic form.
2343 "CHREC" is an array reference to be instantiated.
2345 CACHE is the cache of already instantiated values.
2347 FOLD_CONVERSIONS should be set to true when the conversions that
2348 may wrap in signed/pointer type are folded, as long as the value of
2349 the chrec is preserved.
2351 SIZE_EXPR is used for computing the size of the expression to be
2352 instantiated, and to stop if it exceeds some limit. */
2355 instantiate_array_ref (basic_block instantiate_below
,
2356 struct loop
*evolution_loop
, tree chrec
,
2357 bool fold_conversions
, htab_t cache
, int size_expr
)
2360 tree index
= TREE_OPERAND (chrec
, 1);
2361 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, index
,
2362 fold_conversions
, cache
, size_expr
);
2364 if (op1
== chrec_dont_know
)
2365 return chrec_dont_know
;
2367 if (chrec
&& op1
== index
)
2370 res
= unshare_expr (chrec
);
2371 TREE_OPERAND (res
, 1) = op1
;
2375 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2376 and EVOLUTION_LOOP, that were left under a symbolic form.
2378 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2381 CACHE is the cache of already instantiated values.
2383 FOLD_CONVERSIONS should be set to true when the conversions that
2384 may wrap in signed/pointer type are folded, as long as the value of
2385 the chrec is preserved.
2387 SIZE_EXPR is used for computing the size of the expression to be
2388 instantiated, and to stop if it exceeds some limit. */
2391 instantiate_scev_convert (basic_block instantiate_below
,
2392 struct loop
*evolution_loop
, tree chrec
,
2394 bool fold_conversions
, htab_t cache
, int size_expr
)
2396 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2397 fold_conversions
, cache
, size_expr
);
2399 if (op0
== chrec_dont_know
)
2400 return chrec_dont_know
;
2402 if (fold_conversions
)
2404 tree tmp
= chrec_convert_aggressive (type
, op0
);
2409 if (chrec
&& op0
== op
)
2412 /* If we used chrec_convert_aggressive, we can no longer assume that
2413 signed chrecs do not overflow, as chrec_convert does, so avoid
2414 calling it in that case. */
2415 if (fold_conversions
)
2416 return fold_convert (type
, op0
);
2418 return chrec_convert (type
, op0
, NULL
);
2421 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2422 and EVOLUTION_LOOP, that were left under a symbolic form.
2424 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2425 Handle ~X as -1 - X.
2426 Handle -X as -1 * X.
2428 CACHE is the cache of already instantiated values.
2430 FOLD_CONVERSIONS should be set to true when the conversions that
2431 may wrap in signed/pointer type are folded, as long as the value of
2432 the chrec is preserved.
2434 SIZE_EXPR is used for computing the size of the expression to be
2435 instantiated, and to stop if it exceeds some limit. */
2438 instantiate_scev_not (basic_block instantiate_below
,
2439 struct loop
*evolution_loop
, tree chrec
,
2440 enum tree_code code
, tree type
, tree op
,
2441 bool fold_conversions
, htab_t cache
, int size_expr
)
2443 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2444 fold_conversions
, cache
, size_expr
);
2446 if (op0
== chrec_dont_know
)
2447 return chrec_dont_know
;
2451 op0
= chrec_convert (type
, op0
, NULL
);
2456 return chrec_fold_minus
2457 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2460 return chrec_fold_multiply
2461 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2468 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2471 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2472 and EVOLUTION_LOOP, that were left under a symbolic form.
2474 CHREC is an expression with 3 operands to be instantiated.
2476 CACHE is the cache of already instantiated values.
2478 FOLD_CONVERSIONS should be set to true when the conversions that
2479 may wrap in signed/pointer type are folded, as long as the value of
2480 the chrec is preserved.
2482 SIZE_EXPR is used for computing the size of the expression to be
2483 instantiated, and to stop if it exceeds some limit. */
2486 instantiate_scev_3 (basic_block instantiate_below
,
2487 struct loop
*evolution_loop
, tree chrec
,
2488 bool fold_conversions
, htab_t cache
, int size_expr
)
2491 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2492 TREE_OPERAND (chrec
, 0),
2493 fold_conversions
, cache
, size_expr
);
2494 if (op0
== chrec_dont_know
)
2495 return chrec_dont_know
;
2497 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2498 TREE_OPERAND (chrec
, 1),
2499 fold_conversions
, cache
, size_expr
);
2500 if (op1
== chrec_dont_know
)
2501 return chrec_dont_know
;
2503 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2504 TREE_OPERAND (chrec
, 2),
2505 fold_conversions
, cache
, size_expr
);
2506 if (op2
== chrec_dont_know
)
2507 return chrec_dont_know
;
2509 if (op0
== TREE_OPERAND (chrec
, 0)
2510 && op1
== TREE_OPERAND (chrec
, 1)
2511 && op2
== TREE_OPERAND (chrec
, 2))
2514 return fold_build3 (TREE_CODE (chrec
),
2515 TREE_TYPE (chrec
), op0
, op1
, op2
);
2518 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2519 and EVOLUTION_LOOP, that were left under a symbolic form.
2521 CHREC is an expression with 2 operands to be instantiated.
2523 CACHE is the cache of already instantiated values.
2525 FOLD_CONVERSIONS should be set to true when the conversions that
2526 may wrap in signed/pointer type are folded, as long as the value of
2527 the chrec is preserved.
2529 SIZE_EXPR is used for computing the size of the expression to be
2530 instantiated, and to stop if it exceeds some limit. */
2533 instantiate_scev_2 (basic_block instantiate_below
,
2534 struct loop
*evolution_loop
, tree chrec
,
2535 bool fold_conversions
, htab_t cache
, int size_expr
)
2538 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2539 TREE_OPERAND (chrec
, 0),
2540 fold_conversions
, cache
, size_expr
);
2541 if (op0
== chrec_dont_know
)
2542 return chrec_dont_know
;
2544 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2545 TREE_OPERAND (chrec
, 1),
2546 fold_conversions
, cache
, size_expr
);
2547 if (op1
== chrec_dont_know
)
2548 return chrec_dont_know
;
2550 if (op0
== TREE_OPERAND (chrec
, 0)
2551 && op1
== TREE_OPERAND (chrec
, 1))
2554 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2557 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2558 and EVOLUTION_LOOP, that were left under a symbolic form.
2560 CHREC is an expression with 2 operands to be instantiated.
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_1 (basic_block instantiate_below
,
2573 struct loop
*evolution_loop
, tree chrec
,
2574 bool fold_conversions
, htab_t cache
, int size_expr
)
2576 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2577 TREE_OPERAND (chrec
, 0),
2578 fold_conversions
, cache
, size_expr
);
2580 if (op0
== chrec_dont_know
)
2581 return chrec_dont_know
;
2583 if (op0
== TREE_OPERAND (chrec
, 0))
2586 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2589 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2590 and EVOLUTION_LOOP, that were left under a symbolic form.
2592 CHREC is the scalar evolution to instantiate.
2594 CACHE is the cache of already instantiated values.
2596 FOLD_CONVERSIONS should be set to true when the conversions that
2597 may wrap in signed/pointer type are folded, as long as the value of
2598 the chrec is preserved.
2600 SIZE_EXPR is used for computing the size of the expression to be
2601 instantiated, and to stop if it exceeds some limit. */
2604 instantiate_scev_r (basic_block instantiate_below
,
2605 struct loop
*evolution_loop
, tree chrec
,
2606 bool fold_conversions
, htab_t cache
, int size_expr
)
2608 /* Give up if the expression is larger than the MAX that we allow. */
2609 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2610 return chrec_dont_know
;
2612 if (chrec
== NULL_TREE
2613 || automatically_generated_chrec_p (chrec
)
2614 || is_gimple_min_invariant (chrec
))
2617 switch (TREE_CODE (chrec
))
2620 return instantiate_scev_name (instantiate_below
, evolution_loop
, chrec
,
2621 fold_conversions
, cache
, size_expr
);
2623 case POLYNOMIAL_CHREC
:
2624 return instantiate_scev_poly (instantiate_below
, evolution_loop
, chrec
,
2625 fold_conversions
, cache
, size_expr
);
2627 case POINTER_PLUS_EXPR
:
2631 return instantiate_scev_binary (instantiate_below
, evolution_loop
, chrec
,
2632 TREE_CODE (chrec
), chrec_type (chrec
),
2633 TREE_OPERAND (chrec
, 0),
2634 TREE_OPERAND (chrec
, 1),
2635 fold_conversions
, cache
, size_expr
);
2638 return instantiate_scev_convert (instantiate_below
, evolution_loop
, chrec
,
2639 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2640 fold_conversions
, cache
, size_expr
);
2644 return instantiate_scev_not (instantiate_below
, evolution_loop
, chrec
,
2645 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2646 TREE_OPERAND (chrec
, 0),
2647 fold_conversions
, cache
, size_expr
);
2650 case SCEV_NOT_KNOWN
:
2651 return chrec_dont_know
;
2657 return instantiate_array_ref (instantiate_below
, evolution_loop
, chrec
,
2658 fold_conversions
, cache
, size_expr
);
2664 if (VL_EXP_CLASS_P (chrec
))
2665 return chrec_dont_know
;
2667 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2670 return instantiate_scev_3 (instantiate_below
, evolution_loop
, chrec
,
2671 fold_conversions
, cache
, size_expr
);
2674 return instantiate_scev_2 (instantiate_below
, evolution_loop
, chrec
,
2675 fold_conversions
, cache
, size_expr
);
2678 return instantiate_scev_1 (instantiate_below
, evolution_loop
, chrec
,
2679 fold_conversions
, cache
, size_expr
);
2688 /* Too complicated to handle. */
2689 return chrec_dont_know
;
2692 /* Analyze all the parameters of the chrec that were left under a
2693 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2694 recursive instantiation of parameters: a parameter is a variable
2695 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2696 a function parameter. */
2699 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2703 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2705 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2707 fprintf (dump_file
, "(instantiate_scev \n");
2708 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2709 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2710 fprintf (dump_file
, " (chrec = ");
2711 print_generic_expr (dump_file
, chrec
, 0);
2712 fprintf (dump_file
, ")\n");
2715 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, chrec
, false,
2718 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2720 fprintf (dump_file
, " (res = ");
2721 print_generic_expr (dump_file
, res
, 0);
2722 fprintf (dump_file
, "))\n");
2725 htab_delete (cache
);
2730 /* Similar to instantiate_parameters, but does not introduce the
2731 evolutions in outer loops for LOOP invariants in CHREC, and does not
2732 care about causing overflows, as long as they do not affect value
2733 of an expression. */
2736 resolve_mixers (struct loop
*loop
, tree chrec
)
2738 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2739 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, chrec
, true,
2741 htab_delete (cache
);
2745 /* Entry point for the analysis of the number of iterations pass.
2746 This function tries to safely approximate the number of iterations
2747 the loop will run. When this property is not decidable at compile
2748 time, the result is chrec_dont_know. Otherwise the result is a
2749 scalar or a symbolic parameter. When the number of iterations may
2750 be equal to zero and the property cannot be determined at compile
2751 time, the result is a COND_EXPR that represents in a symbolic form
2752 the conditions under which the number of iterations is not zero.
2754 Example of analysis: suppose that the loop has an exit condition:
2756 "if (b > 49) goto end_loop;"
2758 and that in a previous analysis we have determined that the
2759 variable 'b' has an evolution function:
2761 "EF = {23, +, 5}_2".
2763 When we evaluate the function at the point 5, i.e. the value of the
2764 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2765 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2766 the loop body has been executed 6 times. */
2769 number_of_latch_executions (struct loop
*loop
)
2772 struct tree_niter_desc niter_desc
;
2776 /* Determine whether the number of iterations in loop has already
2778 res
= loop
->nb_iterations
;
2782 may_be_zero
= NULL_TREE
;
2784 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2785 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2787 res
= chrec_dont_know
;
2788 exit
= single_exit (loop
);
2790 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2792 may_be_zero
= niter_desc
.may_be_zero
;
2793 res
= niter_desc
.niter
;
2796 if (res
== chrec_dont_know
2798 || integer_zerop (may_be_zero
))
2800 else if (integer_nonzerop (may_be_zero
))
2801 res
= build_int_cst (TREE_TYPE (res
), 0);
2803 else if (COMPARISON_CLASS_P (may_be_zero
))
2804 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2805 build_int_cst (TREE_TYPE (res
), 0), res
);
2807 res
= chrec_dont_know
;
2809 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2811 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2812 print_generic_expr (dump_file
, res
, 0);
2813 fprintf (dump_file
, "))\n");
2816 loop
->nb_iterations
= res
;
2820 /* Returns the number of executions of the exit condition of LOOP,
2821 i.e., the number by one higher than number_of_latch_executions.
2822 Note that unlike number_of_latch_executions, this number does
2823 not necessarily fit in the unsigned variant of the type of
2824 the control variable -- if the number of iterations is a constant,
2825 we return chrec_dont_know if adding one to number_of_latch_executions
2826 overflows; however, in case the number of iterations is symbolic
2827 expression, the caller is responsible for dealing with this
2828 the possible overflow. */
2831 number_of_exit_cond_executions (struct loop
*loop
)
2833 tree ret
= number_of_latch_executions (loop
);
2834 tree type
= chrec_type (ret
);
2836 if (chrec_contains_undetermined (ret
))
2839 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2840 if (TREE_CODE (ret
) == INTEGER_CST
2841 && TREE_OVERFLOW (ret
))
2842 return chrec_dont_know
;
2847 /* One of the drivers for testing the scalar evolutions analysis.
2848 This function computes the number of iterations for all the loops
2849 from the EXIT_CONDITIONS array. */
2852 number_of_iterations_for_all_loops (VEC(gimple
,heap
) **exit_conditions
)
2855 unsigned nb_chrec_dont_know_loops
= 0;
2856 unsigned nb_static_loops
= 0;
2859 FOR_EACH_VEC_ELT (gimple
, *exit_conditions
, i
, cond
)
2861 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2862 if (chrec_contains_undetermined (res
))
2863 nb_chrec_dont_know_loops
++;
2870 fprintf (dump_file
, "\n(\n");
2871 fprintf (dump_file
, "-----------------------------------------\n");
2872 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2873 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2874 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2875 fprintf (dump_file
, "-----------------------------------------\n");
2876 fprintf (dump_file
, ")\n\n");
2878 print_loops (dump_file
, 3);
2884 /* Counters for the stats. */
2890 unsigned nb_affine_multivar
;
2891 unsigned nb_higher_poly
;
2892 unsigned nb_chrec_dont_know
;
2893 unsigned nb_undetermined
;
2896 /* Reset the counters. */
2899 reset_chrecs_counters (struct chrec_stats
*stats
)
2901 stats
->nb_chrecs
= 0;
2902 stats
->nb_affine
= 0;
2903 stats
->nb_affine_multivar
= 0;
2904 stats
->nb_higher_poly
= 0;
2905 stats
->nb_chrec_dont_know
= 0;
2906 stats
->nb_undetermined
= 0;
2909 /* Dump the contents of a CHREC_STATS structure. */
2912 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2914 fprintf (file
, "\n(\n");
2915 fprintf (file
, "-----------------------------------------\n");
2916 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2917 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2918 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2919 stats
->nb_higher_poly
);
2920 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2921 fprintf (file
, "-----------------------------------------\n");
2922 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2923 fprintf (file
, "%d\twith undetermined coefficients\n",
2924 stats
->nb_undetermined
);
2925 fprintf (file
, "-----------------------------------------\n");
2926 fprintf (file
, "%d\tchrecs in the scev database\n",
2927 (int) htab_elements (scalar_evolution_info
));
2928 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2929 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2930 fprintf (file
, "-----------------------------------------\n");
2931 fprintf (file
, ")\n\n");
2934 /* Gather statistics about CHREC. */
2937 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2939 if (dump_file
&& (dump_flags
& TDF_STATS
))
2941 fprintf (dump_file
, "(classify_chrec ");
2942 print_generic_expr (dump_file
, chrec
, 0);
2943 fprintf (dump_file
, "\n");
2948 if (chrec
== NULL_TREE
)
2950 stats
->nb_undetermined
++;
2954 switch (TREE_CODE (chrec
))
2956 case POLYNOMIAL_CHREC
:
2957 if (evolution_function_is_affine_p (chrec
))
2959 if (dump_file
&& (dump_flags
& TDF_STATS
))
2960 fprintf (dump_file
, " affine_univariate\n");
2963 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2965 if (dump_file
&& (dump_flags
& TDF_STATS
))
2966 fprintf (dump_file
, " affine_multivariate\n");
2967 stats
->nb_affine_multivar
++;
2971 if (dump_file
&& (dump_flags
& TDF_STATS
))
2972 fprintf (dump_file
, " higher_degree_polynomial\n");
2973 stats
->nb_higher_poly
++;
2982 if (chrec_contains_undetermined (chrec
))
2984 if (dump_file
&& (dump_flags
& TDF_STATS
))
2985 fprintf (dump_file
, " undetermined\n");
2986 stats
->nb_undetermined
++;
2989 if (dump_file
&& (dump_flags
& TDF_STATS
))
2990 fprintf (dump_file
, ")\n");
2993 /* One of the drivers for testing the scalar evolutions analysis.
2994 This function analyzes the scalar evolution of all the scalars
2995 defined as loop phi nodes in one of the loops from the
2996 EXIT_CONDITIONS array.
2998 TODO Optimization: A loop is in canonical form if it contains only
2999 a single scalar loop phi node. All the other scalars that have an
3000 evolution in the loop are rewritten in function of this single
3001 index. This allows the parallelization of the loop. */
3004 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple
,heap
) **exit_conditions
)
3007 struct chrec_stats stats
;
3009 gimple_stmt_iterator psi
;
3011 reset_chrecs_counters (&stats
);
3013 FOR_EACH_VEC_ELT (gimple
, *exit_conditions
, i
, cond
)
3019 loop
= loop_containing_stmt (cond
);
3022 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3024 phi
= gsi_stmt (psi
);
3025 if (is_gimple_reg (PHI_RESULT (phi
)))
3027 chrec
= instantiate_parameters
3029 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
3031 if (dump_file
&& (dump_flags
& TDF_STATS
))
3032 gather_chrec_stats (chrec
, &stats
);
3037 if (dump_file
&& (dump_flags
& TDF_STATS
))
3038 dump_chrecs_stats (dump_file
, &stats
);
3041 /* Callback for htab_traverse, gathers information on chrecs in the
3045 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
3047 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
3049 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
3054 /* Classify the chrecs of the whole database. */
3057 gather_stats_on_scev_database (void)
3059 struct chrec_stats stats
;
3064 reset_chrecs_counters (&stats
);
3066 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
3069 dump_chrecs_stats (dump_file
, &stats
);
3077 initialize_scalar_evolutions_analyzer (void)
3079 /* The elements below are unique. */
3080 if (chrec_dont_know
== NULL_TREE
)
3082 chrec_not_analyzed_yet
= NULL_TREE
;
3083 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3084 chrec_known
= make_node (SCEV_KNOWN
);
3085 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3086 TREE_TYPE (chrec_known
) = void_type_node
;
3090 /* Initialize the analysis of scalar evolutions for LOOPS. */
3093 scev_initialize (void)
3099 scalar_evolution_info
= htab_create_ggc (100, hash_scev_info
, eq_scev_info
,
3102 initialize_scalar_evolutions_analyzer ();
3104 FOR_EACH_LOOP (li
, loop
, 0)
3106 loop
->nb_iterations
= NULL_TREE
;
3110 /* Cleans up the information cached by the scalar evolutions analysis
3111 in the hash table. */
3114 scev_reset_htab (void)
3116 if (!scalar_evolution_info
)
3119 htab_empty (scalar_evolution_info
);
3122 /* Cleans up the information cached by the scalar evolutions analysis
3123 in the hash table and in the loop->nb_iterations. */
3136 FOR_EACH_LOOP (li
, loop
, 0)
3138 loop
->nb_iterations
= NULL_TREE
;
3142 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3143 respect to WRTO_LOOP and returns its base and step in IV if possible
3144 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3145 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3146 invariant in LOOP. Otherwise we require it to be an integer constant.
3148 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3149 because it is computed in signed arithmetics). Consequently, adding an
3152 for (i = IV->base; ; i += IV->step)
3154 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3155 false for the type of the induction variable, or you can prove that i does
3156 not wrap by some other argument. Otherwise, this might introduce undefined
3159 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3161 must be used instead. */
3164 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3165 affine_iv
*iv
, bool allow_nonconstant_step
)
3170 iv
->base
= NULL_TREE
;
3171 iv
->step
= NULL_TREE
;
3172 iv
->no_overflow
= false;
3174 type
= TREE_TYPE (op
);
3175 if (TREE_CODE (type
) != INTEGER_TYPE
3176 && TREE_CODE (type
) != POINTER_TYPE
)
3179 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3181 if (chrec_contains_undetermined (ev
)
3182 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3185 if (tree_does_not_contain_chrecs (ev
))
3188 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3189 iv
->no_overflow
= true;
3193 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3194 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3197 iv
->step
= CHREC_RIGHT (ev
);
3198 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3199 || tree_contains_chrecs (iv
->step
, NULL
))
3202 iv
->base
= CHREC_LEFT (ev
);
3203 if (tree_contains_chrecs (iv
->base
, NULL
))
3206 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3211 /* Runs the analysis of scalar evolutions. */
3214 scev_analysis (void)
3216 VEC(gimple
,heap
) *exit_conditions
;
3218 exit_conditions
= VEC_alloc (gimple
, heap
, 37);
3219 select_loops_exit_conditions (&exit_conditions
);
3221 if (dump_file
&& (dump_flags
& TDF_STATS
))
3222 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
3224 number_of_iterations_for_all_loops (&exit_conditions
);
3225 VEC_free (gimple
, heap
, exit_conditions
);
3228 /* Finalize the scalar evolution analysis. */
3231 scev_finalize (void)
3233 if (!scalar_evolution_info
)
3235 htab_delete (scalar_evolution_info
);
3236 scalar_evolution_info
= NULL
;
3239 /* Returns true if the expression EXPR is considered to be too expensive
3240 for scev_const_prop. */
3243 expression_expensive_p (tree expr
)
3245 enum tree_code code
;
3247 if (is_gimple_val (expr
))
3250 code
= TREE_CODE (expr
);
3251 if (code
== TRUNC_DIV_EXPR
3252 || code
== CEIL_DIV_EXPR
3253 || code
== FLOOR_DIV_EXPR
3254 || code
== ROUND_DIV_EXPR
3255 || code
== TRUNC_MOD_EXPR
3256 || code
== CEIL_MOD_EXPR
3257 || code
== FLOOR_MOD_EXPR
3258 || code
== ROUND_MOD_EXPR
3259 || code
== EXACT_DIV_EXPR
)
3261 /* Division by power of two is usually cheap, so we allow it.
3262 Forbid anything else. */
3263 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3267 switch (TREE_CODE_CLASS (code
))
3270 case tcc_comparison
:
3271 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3276 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3283 /* Replace ssa names for that scev can prove they are constant by the
3284 appropriate constants. Also perform final value replacement in loops,
3285 in case the replacement expressions are cheap.
3287 We only consider SSA names defined by phi nodes; rest is left to the
3288 ordinary constant propagation pass. */
3291 scev_const_prop (void)
3294 tree name
, type
, ev
;
3296 struct loop
*loop
, *ex_loop
;
3297 bitmap ssa_names_to_remove
= NULL
;
3300 gimple_stmt_iterator psi
;
3302 if (number_of_loops () <= 1)
3307 loop
= bb
->loop_father
;
3309 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3311 phi
= gsi_stmt (psi
);
3312 name
= PHI_RESULT (phi
);
3314 if (!is_gimple_reg (name
))
3317 type
= TREE_TYPE (name
);
3319 if (!POINTER_TYPE_P (type
)
3320 && !INTEGRAL_TYPE_P (type
))
3323 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3324 if (!is_gimple_min_invariant (ev
)
3325 || !may_propagate_copy (name
, ev
))
3328 /* Replace the uses of the name. */
3330 replace_uses_by (name
, ev
);
3332 if (!ssa_names_to_remove
)
3333 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3334 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3338 /* Remove the ssa names that were replaced by constants. We do not
3339 remove them directly in the previous cycle, since this
3340 invalidates scev cache. */
3341 if (ssa_names_to_remove
)
3345 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3347 gimple_stmt_iterator psi
;
3348 name
= ssa_name (i
);
3349 phi
= SSA_NAME_DEF_STMT (name
);
3351 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3352 psi
= gsi_for_stmt (phi
);
3353 remove_phi_node (&psi
, true);
3356 BITMAP_FREE (ssa_names_to_remove
);
3360 /* Now the regular final value replacement. */
3361 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3364 tree def
, rslt
, niter
;
3365 gimple_stmt_iterator bsi
;
3367 /* If we do not know exact number of iterations of the loop, we cannot
3368 replace the final value. */
3369 exit
= single_exit (loop
);
3373 niter
= number_of_latch_executions (loop
);
3374 if (niter
== chrec_dont_know
)
3377 /* Ensure that it is possible to insert new statements somewhere. */
3378 if (!single_pred_p (exit
->dest
))
3379 split_loop_exit_edge (exit
);
3380 bsi
= gsi_after_labels (exit
->dest
);
3382 ex_loop
= superloop_at_depth (loop
,
3383 loop_depth (exit
->dest
->loop_father
) + 1);
3385 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3387 phi
= gsi_stmt (psi
);
3388 rslt
= PHI_RESULT (phi
);
3389 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3390 if (!is_gimple_reg (def
))
3396 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3397 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3403 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3404 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3405 if (!tree_does_not_contain_chrecs (def
)
3406 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3407 /* Moving the computation from the loop may prolong life range
3408 of some ssa names, which may cause problems if they appear
3409 on abnormal edges. */
3410 || contains_abnormal_ssa_name_p (def
)
3411 /* Do not emit expensive expressions. The rationale is that
3412 when someone writes a code like
3414 while (n > 45) n -= 45;
3416 he probably knows that n is not large, and does not want it
3417 to be turned into n %= 45. */
3418 || expression_expensive_p (def
))
3424 /* Eliminate the PHI node and replace it by a computation outside
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
);
3438 #include "gt-tree-scalar-evolution.h"