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"
265 /* These RTL headers are needed for basic-block.h. */
267 #include "basic-block.h"
268 #include "diagnostic.h"
269 #include "tree-flow.h"
270 #include "tree-dump.h"
273 #include "tree-chrec.h"
274 #include "tree-scalar-evolution.h"
275 #include "tree-pass.h"
279 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
281 /* The cached information about an SSA name VAR, claiming that below
282 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
285 struct GTY(()) scev_info_str
{
286 basic_block instantiated_below
;
291 /* Counters for the scev database. */
292 static unsigned nb_set_scev
= 0;
293 static unsigned nb_get_scev
= 0;
295 /* The following trees are unique elements. Thus the comparison of
296 another element to these elements should be done on the pointer to
297 these trees, and not on their value. */
299 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
300 tree chrec_not_analyzed_yet
;
302 /* Reserved to the cases where the analyzer has detected an
303 undecidable property at compile time. */
304 tree chrec_dont_know
;
306 /* When the analyzer has detected that a property will never
307 happen, then it qualifies it with chrec_known. */
310 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
313 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
315 static inline struct scev_info_str
*
316 new_scev_info_str (basic_block instantiated_below
, tree var
)
318 struct scev_info_str
*res
;
320 res
= GGC_NEW (struct scev_info_str
);
322 res
->chrec
= chrec_not_analyzed_yet
;
323 res
->instantiated_below
= instantiated_below
;
328 /* Computes a hash function for database element ELT. */
331 hash_scev_info (const void *elt
)
333 return SSA_NAME_VERSION (((const struct scev_info_str
*) elt
)->var
);
336 /* Compares database elements E1 and E2. */
339 eq_scev_info (const void *e1
, const void *e2
)
341 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
342 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
344 return (elt1
->var
== elt2
->var
345 && elt1
->instantiated_below
== elt2
->instantiated_below
);
348 /* Deletes database element E. */
351 del_scev_info (void *e
)
356 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
357 A first query on VAR returns chrec_not_analyzed_yet. */
360 find_var_scev_info (basic_block instantiated_below
, tree var
)
362 struct scev_info_str
*res
;
363 struct scev_info_str tmp
;
367 tmp
.instantiated_below
= instantiated_below
;
368 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
371 *slot
= new_scev_info_str (instantiated_below
, var
);
372 res
= (struct scev_info_str
*) *slot
;
377 /* Return true when CHREC contains symbolic names defined in
381 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
385 if (chrec
== NULL_TREE
)
388 if (is_gimple_min_invariant (chrec
))
391 if (TREE_CODE (chrec
) == VAR_DECL
392 || TREE_CODE (chrec
) == PARM_DECL
393 || TREE_CODE (chrec
) == FUNCTION_DECL
394 || TREE_CODE (chrec
) == LABEL_DECL
395 || TREE_CODE (chrec
) == RESULT_DECL
396 || TREE_CODE (chrec
) == FIELD_DECL
)
399 if (TREE_CODE (chrec
) == SSA_NAME
)
401 gimple def
= SSA_NAME_DEF_STMT (chrec
);
402 struct loop
*def_loop
= loop_containing_stmt (def
);
403 struct loop
*loop
= get_loop (loop_nb
);
405 if (def_loop
== NULL
)
408 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
414 n
= TREE_OPERAND_LENGTH (chrec
);
415 for (i
= 0; i
< n
; i
++)
416 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
422 /* Return true when PHI is a loop-phi-node. */
425 loop_phi_node_p (gimple phi
)
427 /* The implementation of this function is based on the following
428 property: "all the loop-phi-nodes of a loop are contained in the
429 loop's header basic block". */
431 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
434 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
435 In general, in the case of multivariate evolutions we want to get
436 the evolution in different loops. LOOP specifies the level for
437 which to get the evolution.
441 | for (j = 0; j < 100; j++)
443 | for (k = 0; k < 100; k++)
445 | i = k + j; - Here the value of i is a function of j, k.
447 | ... = i - Here the value of i is a function of j.
449 | ... = i - Here the value of i is a scalar.
455 | i_1 = phi (i_0, i_2)
459 This loop has the same effect as:
460 LOOP_1 has the same effect as:
464 The overall effect of the loop, "i_0 + 20" in the previous example,
465 is obtained by passing in the parameters: LOOP = 1,
466 EVOLUTION_FN = {i_0, +, 2}_1.
470 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
474 if (evolution_fn
== chrec_dont_know
)
475 return chrec_dont_know
;
477 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
479 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
481 if (inner_loop
== loop
482 || flow_loop_nested_p (loop
, inner_loop
))
484 tree nb_iter
= number_of_latch_executions (inner_loop
);
486 if (nb_iter
== chrec_dont_know
)
487 return chrec_dont_know
;
492 /* evolution_fn is the evolution function in LOOP. Get
493 its value in the nb_iter-th iteration. */
494 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
496 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
497 res
= instantiate_parameters (loop
, res
);
499 /* Continue the computation until ending on a parent of LOOP. */
500 return compute_overall_effect_of_inner_loop (loop
, res
);
507 /* If the evolution function is an invariant, there is nothing to do. */
508 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
512 return chrec_dont_know
;
515 /* Determine whether the CHREC is always positive/negative. If the expression
516 cannot be statically analyzed, return false, otherwise set the answer into
520 chrec_is_positive (tree chrec
, bool *value
)
522 bool value0
, value1
, value2
;
523 tree end_value
, nb_iter
;
525 switch (TREE_CODE (chrec
))
527 case POLYNOMIAL_CHREC
:
528 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
529 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
532 /* FIXME -- overflows. */
533 if (value0
== value1
)
539 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
540 and the proof consists in showing that the sign never
541 changes during the execution of the loop, from 0 to
542 loop->nb_iterations. */
543 if (!evolution_function_is_affine_p (chrec
))
546 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
547 if (chrec_contains_undetermined (nb_iter
))
551 /* TODO -- If the test is after the exit, we may decrease the number of
552 iterations by one. */
554 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
557 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
559 if (!chrec_is_positive (end_value
, &value2
))
563 return value0
== value1
;
566 *value
= (tree_int_cst_sgn (chrec
) == 1);
574 /* Associate CHREC to SCALAR. */
577 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
581 if (TREE_CODE (scalar
) != SSA_NAME
)
584 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
588 if (dump_flags
& TDF_DETAILS
)
590 fprintf (dump_file
, "(set_scalar_evolution \n");
591 fprintf (dump_file
, " instantiated_below = %d \n",
592 instantiated_below
->index
);
593 fprintf (dump_file
, " (scalar = ");
594 print_generic_expr (dump_file
, scalar
, 0);
595 fprintf (dump_file
, ")\n (scalar_evolution = ");
596 print_generic_expr (dump_file
, chrec
, 0);
597 fprintf (dump_file
, "))\n");
599 if (dump_flags
& TDF_STATS
)
603 *scalar_info
= chrec
;
606 /* Retrieve the chrec associated to SCALAR instantiated below
607 INSTANTIATED_BELOW block. */
610 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
616 if (dump_flags
& TDF_DETAILS
)
618 fprintf (dump_file
, "(get_scalar_evolution \n");
619 fprintf (dump_file
, " (scalar = ");
620 print_generic_expr (dump_file
, scalar
, 0);
621 fprintf (dump_file
, ")\n");
623 if (dump_flags
& TDF_STATS
)
627 switch (TREE_CODE (scalar
))
630 res
= *find_var_scev_info (instantiated_below
, scalar
);
640 res
= chrec_not_analyzed_yet
;
644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
646 fprintf (dump_file
, " (scalar_evolution = ");
647 print_generic_expr (dump_file
, res
, 0);
648 fprintf (dump_file
, "))\n");
654 /* Helper function for add_to_evolution. Returns the evolution
655 function for an assignment of the form "a = b + c", where "a" and
656 "b" are on the strongly connected component. CHREC_BEFORE is the
657 information that we already have collected up to this point.
658 TO_ADD is the evolution of "c".
660 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
661 evolution the expression TO_ADD, otherwise construct an evolution
662 part for this loop. */
665 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
668 tree type
, left
, right
;
669 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
671 switch (TREE_CODE (chrec_before
))
673 case POLYNOMIAL_CHREC
:
674 chloop
= get_chrec_loop (chrec_before
);
676 || flow_loop_nested_p (chloop
, loop
))
680 type
= chrec_type (chrec_before
);
682 /* When there is no evolution part in this loop, build it. */
687 right
= SCALAR_FLOAT_TYPE_P (type
)
688 ? build_real (type
, dconst0
)
689 : build_int_cst (type
, 0);
693 var
= CHREC_VARIABLE (chrec_before
);
694 left
= CHREC_LEFT (chrec_before
);
695 right
= CHREC_RIGHT (chrec_before
);
698 to_add
= chrec_convert (type
, to_add
, at_stmt
);
699 right
= chrec_convert_rhs (type
, right
, at_stmt
);
700 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
701 return build_polynomial_chrec (var
, left
, right
);
705 gcc_assert (flow_loop_nested_p (loop
, chloop
));
707 /* Search the evolution in LOOP_NB. */
708 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
710 right
= CHREC_RIGHT (chrec_before
);
711 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
712 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
717 /* These nodes do not depend on a loop. */
718 if (chrec_before
== chrec_dont_know
)
719 return chrec_dont_know
;
722 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
723 return build_polynomial_chrec (loop_nb
, left
, right
);
727 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
730 Description (provided for completeness, for those who read code in
731 a plane, and for my poor 62 bytes brain that would have forgotten
732 all this in the next two or three months):
734 The algorithm of translation of programs from the SSA representation
735 into the chrecs syntax is based on a pattern matching. After having
736 reconstructed the overall tree expression for a loop, there are only
737 two cases that can arise:
739 1. a = loop-phi (init, a + expr)
740 2. a = loop-phi (init, expr)
742 where EXPR is either a scalar constant with respect to the analyzed
743 loop (this is a degree 0 polynomial), or an expression containing
744 other loop-phi definitions (these are higher degree polynomials).
751 | a = phi (init, a + 5)
758 | a = phi (inita, 2 * b + 3)
759 | b = phi (initb, b + 1)
762 For the first case, the semantics of the SSA representation is:
764 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
766 that is, there is a loop index "x" that determines the scalar value
767 of the variable during the loop execution. During the first
768 iteration, the value is that of the initial condition INIT, while
769 during the subsequent iterations, it is the sum of the initial
770 condition with the sum of all the values of EXPR from the initial
771 iteration to the before last considered iteration.
773 For the second case, the semantics of the SSA program is:
775 | a (x) = init, if x = 0;
776 | expr (x - 1), otherwise.
778 The second case corresponds to the PEELED_CHREC, whose syntax is
779 close to the syntax of a loop-phi-node:
781 | phi (init, expr) vs. (init, expr)_x
783 The proof of the translation algorithm for the first case is a
784 proof by structural induction based on the degree of EXPR.
787 When EXPR is a constant with respect to the analyzed loop, or in
788 other words when EXPR is a polynomial of degree 0, the evolution of
789 the variable A in the loop is an affine function with an initial
790 condition INIT, and a step EXPR. In order to show this, we start
791 from the semantics of the SSA representation:
793 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
795 and since "expr (j)" is a constant with respect to "j",
797 f (x) = init + x * expr
799 Finally, based on the semantics of the pure sum chrecs, by
800 identification we get the corresponding chrecs syntax:
802 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
803 f (x) -> {init, +, expr}_x
806 Suppose that EXPR is a polynomial of degree N with respect to the
807 analyzed loop_x for which we have already determined that it is
808 written under the chrecs syntax:
810 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
812 We start from the semantics of the SSA program:
814 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
816 | f (x) = init + \sum_{j = 0}^{x - 1}
817 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
819 | f (x) = init + \sum_{j = 0}^{x - 1}
820 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
822 | f (x) = init + \sum_{k = 0}^{n - 1}
823 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
825 | f (x) = init + \sum_{k = 0}^{n - 1}
826 | (b_k * \binom{x}{k + 1})
828 | f (x) = init + b_0 * \binom{x}{1} + ...
829 | + b_{n-1} * \binom{x}{n}
831 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
832 | + b_{n-1} * \binom{x}{n}
835 And finally from the definition of the chrecs syntax, we identify:
836 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
838 This shows the mechanism that stands behind the add_to_evolution
839 function. An important point is that the use of symbolic
840 parameters avoids the need of an analysis schedule.
847 | a = phi (inita, a + 2 + b)
848 | b = phi (initb, b + 1)
851 When analyzing "a", the algorithm keeps "b" symbolically:
853 | a -> {inita, +, 2 + b}_1
855 Then, after instantiation, the analyzer ends on the evolution:
857 | a -> {inita, +, 2 + initb, +, 1}_1
862 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
863 tree to_add
, gimple at_stmt
)
865 tree type
= chrec_type (to_add
);
866 tree res
= NULL_TREE
;
868 if (to_add
== NULL_TREE
)
871 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
872 instantiated at this point. */
873 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
874 /* This should not happen. */
875 return chrec_dont_know
;
877 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
879 fprintf (dump_file
, "(add_to_evolution \n");
880 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
881 fprintf (dump_file
, " (chrec_before = ");
882 print_generic_expr (dump_file
, chrec_before
, 0);
883 fprintf (dump_file
, ")\n (to_add = ");
884 print_generic_expr (dump_file
, to_add
, 0);
885 fprintf (dump_file
, ")\n");
888 if (code
== MINUS_EXPR
)
889 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
890 ? build_real (type
, dconstm1
)
891 : build_int_cst_type (type
, -1));
893 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
897 fprintf (dump_file
, " (res = ");
898 print_generic_expr (dump_file
, res
, 0);
899 fprintf (dump_file
, "))\n");
905 /* Helper function. */
908 set_nb_iterations_in_loop (struct loop
*loop
,
911 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
913 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
914 print_generic_expr (dump_file
, res
, 0);
915 fprintf (dump_file
, "))\n");
918 loop
->nb_iterations
= res
;
924 /* This section selects the loops that will be good candidates for the
925 scalar evolution analysis. For the moment, greedily select all the
926 loop nests we could analyze. */
928 /* For a loop with a single exit edge, return the COND_EXPR that
929 guards the exit edge. If the expression is too difficult to
930 analyze, then give up. */
933 get_loop_exit_condition (const struct loop
*loop
)
936 edge exit_edge
= single_exit (loop
);
938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
939 fprintf (dump_file
, "(get_loop_exit_condition \n ");
945 stmt
= last_stmt (exit_edge
->src
);
946 if (gimple_code (stmt
) == GIMPLE_COND
)
950 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
952 print_gimple_stmt (dump_file
, res
, 0, 0);
953 fprintf (dump_file
, ")\n");
959 /* Recursively determine and enqueue the exit conditions for a loop. */
962 get_exit_conditions_rec (struct loop
*loop
,
963 VEC(gimple
,heap
) **exit_conditions
)
968 /* Recurse on the inner loops, then on the next (sibling) loops. */
969 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
970 get_exit_conditions_rec (loop
->next
, exit_conditions
);
972 if (single_exit (loop
))
974 gimple loop_condition
= get_loop_exit_condition (loop
);
977 VEC_safe_push (gimple
, heap
, *exit_conditions
, loop_condition
);
981 /* Select the candidate loop nests for the analysis. This function
982 initializes the EXIT_CONDITIONS array. */
985 select_loops_exit_conditions (VEC(gimple
,heap
) **exit_conditions
)
987 struct loop
*function_body
= current_loops
->tree_root
;
989 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
993 /* Depth first search algorithm. */
995 typedef enum t_bool
{
1002 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
1004 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
1005 Return true if the strongly connected component has been found. */
1008 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
1009 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
1010 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1012 t_bool res
= t_false
;
1017 case POINTER_PLUS_EXPR
:
1019 if (TREE_CODE (rhs0
) == SSA_NAME
)
1021 if (TREE_CODE (rhs1
) == SSA_NAME
)
1023 /* Match an assignment under the form:
1026 /* We want only assignments of form "name + name" contribute to
1027 LIMIT, as the other cases do not necessarily contribute to
1028 the complexity of the expression. */
1031 evol
= *evolution_of_loop
;
1032 res
= follow_ssa_edge
1033 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
1036 *evolution_of_loop
= add_to_evolution
1038 chrec_convert (type
, evol
, at_stmt
),
1039 code
, rhs1
, at_stmt
);
1041 else if (res
== t_false
)
1043 res
= follow_ssa_edge
1044 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1045 evolution_of_loop
, limit
);
1048 *evolution_of_loop
= add_to_evolution
1050 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1051 code
, rhs0
, at_stmt
);
1053 else if (res
== t_dont_know
)
1054 *evolution_of_loop
= chrec_dont_know
;
1057 else if (res
== t_dont_know
)
1058 *evolution_of_loop
= chrec_dont_know
;
1063 /* Match an assignment under the form:
1065 res
= follow_ssa_edge
1066 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1067 evolution_of_loop
, limit
);
1069 *evolution_of_loop
= add_to_evolution
1070 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1072 code
, rhs1
, at_stmt
);
1074 else if (res
== t_dont_know
)
1075 *evolution_of_loop
= chrec_dont_know
;
1079 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1081 /* Match an assignment under the form:
1083 res
= follow_ssa_edge
1084 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1085 evolution_of_loop
, limit
);
1087 *evolution_of_loop
= add_to_evolution
1088 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1090 code
, rhs0
, at_stmt
);
1092 else if (res
== t_dont_know
)
1093 *evolution_of_loop
= chrec_dont_know
;
1097 /* Otherwise, match an assignment under the form:
1099 /* And there is nothing to do. */
1104 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1105 if (TREE_CODE (rhs0
) == SSA_NAME
)
1107 /* Match an assignment under the form:
1110 /* We want only assignments of form "name - name" contribute to
1111 LIMIT, as the other cases do not necessarily contribute to
1112 the complexity of the expression. */
1113 if (TREE_CODE (rhs1
) == SSA_NAME
)
1116 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1117 evolution_of_loop
, limit
);
1119 *evolution_of_loop
= add_to_evolution
1120 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1121 MINUS_EXPR
, rhs1
, at_stmt
);
1123 else if (res
== t_dont_know
)
1124 *evolution_of_loop
= chrec_dont_know
;
1127 /* Otherwise, match an assignment under the form:
1129 /* And there is nothing to do. */
1140 /* Follow the ssa edge into the expression EXPR.
1141 Return true if the strongly connected component has been found. */
1144 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1145 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1147 enum tree_code code
= TREE_CODE (expr
);
1148 tree type
= TREE_TYPE (expr
), rhs0
, rhs1
;
1151 /* The EXPR is one of the following cases:
1155 - a POINTER_PLUS_EXPR,
1158 - other cases are not yet handled. */
1163 /* This assignment is under the form "a_1 = (cast) rhs. */
1164 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1165 halting_phi
, evolution_of_loop
, limit
);
1166 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1170 /* This assignment is under the form "a_1 = 7". */
1175 /* This assignment is under the form: "a_1 = b_2". */
1176 res
= follow_ssa_edge
1177 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1180 case POINTER_PLUS_EXPR
:
1183 /* This case is under the form "rhs0 +- rhs1". */
1184 rhs0
= TREE_OPERAND (expr
, 0);
1185 rhs1
= TREE_OPERAND (expr
, 1);
1186 type
= TREE_TYPE (rhs0
);
1187 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1188 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1189 res
= follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1190 halting_phi
, evolution_of_loop
, limit
);
1194 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1195 It must be handled as a copy assignment of the form a_1 = a_2. */
1196 rhs0
= ASSERT_EXPR_VAR (expr
);
1197 if (TREE_CODE (rhs0
) == SSA_NAME
)
1198 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
),
1199 halting_phi
, evolution_of_loop
, limit
);
1212 /* Follow the ssa edge into the right hand side of an assignment STMT.
1213 Return true if the strongly connected component has been found. */
1216 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1217 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1219 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1220 tree type
= gimple_expr_type (stmt
), rhs1
, rhs2
;
1226 /* This assignment is under the form "a_1 = (cast) rhs. */
1227 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1228 halting_phi
, evolution_of_loop
, limit
);
1229 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1232 case POINTER_PLUS_EXPR
:
1235 rhs1
= gimple_assign_rhs1 (stmt
);
1236 rhs2
= gimple_assign_rhs2 (stmt
);
1237 type
= TREE_TYPE (rhs1
);
1238 res
= follow_ssa_edge_binary (loop
, stmt
, type
, rhs1
, code
, rhs2
,
1239 halting_phi
, evolution_of_loop
, limit
);
1243 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1244 res
= follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1245 halting_phi
, evolution_of_loop
, limit
);
1254 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1257 backedge_phi_arg_p (gimple phi
, int i
)
1259 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1261 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1262 about updating it anywhere, and this should work as well most of the
1264 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1270 /* Helper function for one branch of the condition-phi-node. Return
1271 true if the strongly connected component has been found following
1274 static inline t_bool
1275 follow_ssa_edge_in_condition_phi_branch (int i
,
1277 gimple condition_phi
,
1279 tree
*evolution_of_branch
,
1280 tree init_cond
, int limit
)
1282 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1283 *evolution_of_branch
= chrec_dont_know
;
1285 /* Do not follow back edges (they must belong to an irreducible loop, which
1286 we really do not want to worry about). */
1287 if (backedge_phi_arg_p (condition_phi
, i
))
1290 if (TREE_CODE (branch
) == SSA_NAME
)
1292 *evolution_of_branch
= init_cond
;
1293 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1294 evolution_of_branch
, limit
);
1297 /* This case occurs when one of the condition branches sets
1298 the variable to a constant: i.e. a phi-node like
1299 "a_2 = PHI <a_7(5), 2(6)>;".
1301 FIXME: This case have to be refined correctly:
1302 in some cases it is possible to say something better than
1303 chrec_dont_know, for example using a wrap-around notation. */
1307 /* This function merges the branches of a condition-phi-node in a
1311 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1312 gimple condition_phi
,
1314 tree
*evolution_of_loop
, int limit
)
1317 tree init
= *evolution_of_loop
;
1318 tree evolution_of_branch
;
1319 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1321 &evolution_of_branch
,
1323 if (res
== t_false
|| res
== t_dont_know
)
1326 *evolution_of_loop
= evolution_of_branch
;
1328 n
= gimple_phi_num_args (condition_phi
);
1329 for (i
= 1; i
< n
; i
++)
1331 /* Quickly give up when the evolution of one of the branches is
1333 if (*evolution_of_loop
== chrec_dont_know
)
1336 /* Increase the limit by the PHI argument number to avoid exponential
1337 time and memory complexity. */
1338 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1340 &evolution_of_branch
,
1342 if (res
== t_false
|| res
== t_dont_know
)
1345 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1346 evolution_of_branch
);
1352 /* Follow an SSA edge in an inner loop. It computes the overall
1353 effect of the loop, and following the symbolic initial conditions,
1354 it follows the edges in the parent loop. The inner loop is
1355 considered as a single statement. */
1358 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1359 gimple loop_phi_node
,
1361 tree
*evolution_of_loop
, int limit
)
1363 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1364 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1366 /* Sometimes, the inner loop is too difficult to analyze, and the
1367 result of the analysis is a symbolic parameter. */
1368 if (ev
== PHI_RESULT (loop_phi_node
))
1370 t_bool res
= t_false
;
1371 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1373 for (i
= 0; i
< n
; i
++)
1375 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1378 /* Follow the edges that exit the inner loop. */
1379 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1380 if (!flow_bb_inside_loop_p (loop
, bb
))
1381 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1383 evolution_of_loop
, limit
);
1388 /* If the path crosses this loop-phi, give up. */
1390 *evolution_of_loop
= chrec_dont_know
;
1395 /* Otherwise, compute the overall effect of the inner loop. */
1396 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1397 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1398 evolution_of_loop
, limit
);
1401 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1402 path that is analyzed on the return walk. */
1405 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1406 tree
*evolution_of_loop
, int limit
)
1408 struct loop
*def_loop
;
1410 if (gimple_nop_p (def
))
1413 /* Give up if the path is longer than the MAX that we allow. */
1414 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1417 def_loop
= loop_containing_stmt (def
);
1419 switch (gimple_code (def
))
1422 if (!loop_phi_node_p (def
))
1423 /* DEF is a condition-phi-node. Follow the branches, and
1424 record their evolutions. Finally, merge the collected
1425 information and set the approximation to the main
1427 return follow_ssa_edge_in_condition_phi
1428 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1430 /* When the analyzed phi is the halting_phi, the
1431 depth-first search is over: we have found a path from
1432 the halting_phi to itself in the loop. */
1433 if (def
== halting_phi
)
1436 /* Otherwise, the evolution of the HALTING_PHI depends
1437 on the evolution of another loop-phi-node, i.e. the
1438 evolution function is a higher degree polynomial. */
1439 if (def_loop
== loop
)
1443 if (flow_loop_nested_p (loop
, def_loop
))
1444 return follow_ssa_edge_inner_loop_phi
1445 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1451 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1452 evolution_of_loop
, limit
);
1455 /* At this level of abstraction, the program is just a set
1456 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1457 other node to be handled. */
1464 /* Given a LOOP_PHI_NODE, this function determines the evolution
1465 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1468 analyze_evolution_in_loop (gimple loop_phi_node
,
1471 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1472 tree evolution_function
= chrec_not_analyzed_yet
;
1473 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1476 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1478 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1479 fprintf (dump_file
, " (loop_phi_node = ");
1480 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1481 fprintf (dump_file
, ")\n");
1484 for (i
= 0; i
< n
; i
++)
1486 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1491 /* Select the edges that enter the loop body. */
1492 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1493 if (!flow_bb_inside_loop_p (loop
, bb
))
1496 if (TREE_CODE (arg
) == SSA_NAME
)
1500 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1502 /* Pass in the initial condition to the follow edge function. */
1504 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1506 /* If ev_fn has no evolution in the inner loop, and the
1507 init_cond is not equal to ev_fn, then we have an
1508 ambiguity between two possible values, as we cannot know
1509 the number of iterations at this point. */
1510 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1511 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1512 && !operand_equal_p (init_cond
, ev_fn
, 0))
1513 ev_fn
= chrec_dont_know
;
1518 /* When it is impossible to go back on the same
1519 loop_phi_node by following the ssa edges, the
1520 evolution is represented by a peeled chrec, i.e. the
1521 first iteration, EV_FN has the value INIT_COND, then
1522 all the other iterations it has the value of ARG.
1523 For the moment, PEELED_CHREC nodes are not built. */
1525 ev_fn
= chrec_dont_know
;
1527 /* When there are multiple back edges of the loop (which in fact never
1528 happens currently, but nevertheless), merge their evolutions. */
1529 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1534 fprintf (dump_file
, " (evolution_function = ");
1535 print_generic_expr (dump_file
, evolution_function
, 0);
1536 fprintf (dump_file
, "))\n");
1539 return evolution_function
;
1542 /* Given a loop-phi-node, return the initial conditions of the
1543 variable on entry of the loop. When the CCP has propagated
1544 constants into the loop-phi-node, the initial condition is
1545 instantiated, otherwise the initial condition is kept symbolic.
1546 This analyzer does not analyze the evolution outside the current
1547 loop, and leaves this task to the on-demand tree reconstructor. */
1550 analyze_initial_condition (gimple loop_phi_node
)
1553 tree init_cond
= chrec_not_analyzed_yet
;
1554 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1556 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1558 fprintf (dump_file
, "(analyze_initial_condition \n");
1559 fprintf (dump_file
, " (loop_phi_node = \n");
1560 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1561 fprintf (dump_file
, ")\n");
1564 n
= gimple_phi_num_args (loop_phi_node
);
1565 for (i
= 0; i
< n
; i
++)
1567 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1568 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1570 /* When the branch is oriented to the loop's body, it does
1571 not contribute to the initial condition. */
1572 if (flow_bb_inside_loop_p (loop
, bb
))
1575 if (init_cond
== chrec_not_analyzed_yet
)
1581 if (TREE_CODE (branch
) == SSA_NAME
)
1583 init_cond
= chrec_dont_know
;
1587 init_cond
= chrec_merge (init_cond
, branch
);
1590 /* Ooops -- a loop without an entry??? */
1591 if (init_cond
== chrec_not_analyzed_yet
)
1592 init_cond
= chrec_dont_know
;
1594 /* During early loop unrolling we do not have fully constant propagated IL.
1595 Handle degenerate PHIs here to not miss important unrollings. */
1596 if (TREE_CODE (init_cond
) == SSA_NAME
)
1598 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1600 if (gimple_code (def
) == GIMPLE_PHI
1601 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1602 /* Only allow invariants here, otherwise we may break
1603 loop-closed SSA form. */
1604 && is_gimple_min_invariant (res
))
1608 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1610 fprintf (dump_file
, " (init_cond = ");
1611 print_generic_expr (dump_file
, init_cond
, 0);
1612 fprintf (dump_file
, "))\n");
1618 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1621 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1624 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1627 if (phi_loop
!= loop
)
1629 struct loop
*subloop
;
1630 tree evolution_fn
= analyze_scalar_evolution
1631 (phi_loop
, PHI_RESULT (loop_phi_node
));
1633 /* Dive one level deeper. */
1634 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1636 /* Interpret the subloop. */
1637 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1641 /* Otherwise really interpret the loop phi. */
1642 init_cond
= analyze_initial_condition (loop_phi_node
);
1643 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1645 /* Verify we maintained the correct initial condition throughout
1646 possible conversions in the SSA chain. */
1647 if (res
!= chrec_dont_know
)
1649 tree new_init
= res
;
1650 if (CONVERT_EXPR_P (res
)
1651 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1652 new_init
= fold_convert (TREE_TYPE (res
),
1653 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1654 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1655 new_init
= CHREC_LEFT (res
);
1656 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1657 gcc_assert (TREE_CODE (new_init
) != POLYNOMIAL_CHREC
);
1658 if (!operand_equal_p (init_cond
, new_init
, 0))
1659 return chrec_dont_know
;
1665 /* This function merges the branches of a condition-phi-node,
1666 contained in the outermost loop, and whose arguments are already
1670 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1672 int i
, n
= gimple_phi_num_args (condition_phi
);
1673 tree res
= chrec_not_analyzed_yet
;
1675 for (i
= 0; i
< n
; i
++)
1679 if (backedge_phi_arg_p (condition_phi
, i
))
1681 res
= chrec_dont_know
;
1685 branch_chrec
= analyze_scalar_evolution
1686 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1688 res
= chrec_merge (res
, branch_chrec
);
1694 /* Interpret the operation RHS1 OP RHS2. If we didn't
1695 analyze this node before, follow the definitions until ending
1696 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1697 return path, this function propagates evolutions (ala constant copy
1698 propagation). OPND1 is not a GIMPLE expression because we could
1699 analyze the effect of an inner loop: see interpret_loop_phi. */
1702 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1703 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1705 tree res
, chrec1
, chrec2
;
1707 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1709 if (is_gimple_min_invariant (rhs1
))
1710 return chrec_convert (type
, rhs1
, at_stmt
);
1712 if (code
== SSA_NAME
)
1713 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1716 if (code
== ASSERT_EXPR
)
1718 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1719 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1723 return chrec_dont_know
;
1728 case POINTER_PLUS_EXPR
:
1729 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1730 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1731 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1732 chrec2
= chrec_convert (sizetype
, chrec2
, at_stmt
);
1733 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1737 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1738 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1739 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1740 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1741 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1745 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1746 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1747 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1748 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1749 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1753 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1754 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1755 /* TYPE may be integer, real or complex, so use fold_convert. */
1756 res
= chrec_fold_multiply (type
, chrec1
,
1757 fold_convert (type
, integer_minus_one_node
));
1761 /* Handle ~X as -1 - X. */
1762 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1763 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1764 res
= chrec_fold_minus (type
,
1765 fold_convert (type
, integer_minus_one_node
),
1770 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1771 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1772 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1773 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1774 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1778 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1779 res
= chrec_convert (type
, chrec1
, at_stmt
);
1783 res
= chrec_dont_know
;
1790 /* Interpret the expression EXPR. */
1793 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1795 enum tree_code code
;
1796 tree type
= TREE_TYPE (expr
), op0
, op1
;
1798 if (automatically_generated_chrec_p (expr
))
1801 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
)
1802 return chrec_dont_know
;
1804 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1806 return interpret_rhs_expr (loop
, at_stmt
, type
,
1810 /* Interpret the rhs of the assignment STMT. */
1813 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1815 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1816 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1818 return interpret_rhs_expr (loop
, stmt
, type
,
1819 gimple_assign_rhs1 (stmt
), code
,
1820 gimple_assign_rhs2 (stmt
));
1825 /* This section contains all the entry points:
1826 - number_of_iterations_in_loop,
1827 - analyze_scalar_evolution,
1828 - instantiate_parameters.
1831 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1832 common ancestor of DEF_LOOP and USE_LOOP. */
1835 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1836 struct loop
*def_loop
,
1840 if (def_loop
== wrto_loop
)
1843 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1844 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1846 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1849 /* Helper recursive function. */
1852 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1854 tree type
= TREE_TYPE (var
);
1857 struct loop
*def_loop
;
1859 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1860 return chrec_dont_know
;
1862 if (TREE_CODE (var
) != SSA_NAME
)
1863 return interpret_expr (loop
, NULL
, var
);
1865 def
= SSA_NAME_DEF_STMT (var
);
1866 bb
= gimple_bb (def
);
1867 def_loop
= bb
? bb
->loop_father
: NULL
;
1870 || !flow_bb_inside_loop_p (loop
, bb
))
1872 /* Keep the symbolic form. */
1877 if (res
!= chrec_not_analyzed_yet
)
1879 if (loop
!= bb
->loop_father
)
1880 res
= compute_scalar_evolution_in_loop
1881 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1886 if (loop
!= def_loop
)
1888 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1889 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1894 switch (gimple_code (def
))
1897 res
= interpret_gimple_assign (loop
, def
);
1901 if (loop_phi_node_p (def
))
1902 res
= interpret_loop_phi (loop
, def
);
1904 res
= interpret_condition_phi (loop
, def
);
1908 res
= chrec_dont_know
;
1914 /* Keep the symbolic form. */
1915 if (res
== chrec_dont_know
)
1918 if (loop
== def_loop
)
1919 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1924 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1925 LOOP. LOOP is the loop in which the variable is used.
1927 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1928 pointer to the statement that uses this variable, in order to
1929 determine the evolution function of the variable, use the following
1932 loop_p loop = loop_containing_stmt (stmt);
1933 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1934 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1938 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1942 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1944 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1945 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1946 fprintf (dump_file
, " (scalar = ");
1947 print_generic_expr (dump_file
, var
, 0);
1948 fprintf (dump_file
, ")\n");
1951 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1952 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1955 fprintf (dump_file
, ")\n");
1960 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1961 WRTO_LOOP (which should be a superloop of USE_LOOP)
1963 FOLDED_CASTS is set to true if resolve_mixers used
1964 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1965 at the moment in order to keep things simple).
1967 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1970 for (i = 0; i < 100; i++) -- loop 1
1972 for (j = 0; j < 100; j++) -- loop 2
1979 for (t = 0; t < 100; t++) -- loop 3
1986 Both k1 and k2 are invariants in loop3, thus
1987 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1988 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1990 As they are invariant, it does not matter whether we consider their
1991 usage in loop 3 or loop 2, hence
1992 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1993 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1994 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1995 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1997 Similarly for their evolutions with respect to loop 1. The values of K2
1998 in the use in loop 2 vary independently on loop 1, thus we cannot express
1999 the evolution with respect to loop 1:
2000 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2001 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2002 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2003 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2005 The value of k2 in the use in loop 1 is known, though:
2006 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2007 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2011 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2012 tree version
, bool *folded_casts
)
2015 tree ev
= version
, tmp
;
2017 /* We cannot just do
2019 tmp = analyze_scalar_evolution (use_loop, version);
2020 ev = resolve_mixers (wrto_loop, tmp);
2022 as resolve_mixers would query the scalar evolution with respect to
2023 wrto_loop. For example, in the situation described in the function
2024 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2027 analyze_scalar_evolution (use_loop, version) = k2
2029 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2030 is 100, which is a wrong result, since we are interested in the
2033 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2034 each time checking that there is no evolution in the inner loop. */
2037 *folded_casts
= false;
2040 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2041 ev
= resolve_mixers (use_loop
, tmp
);
2043 if (folded_casts
&& tmp
!= ev
)
2044 *folded_casts
= true;
2046 if (use_loop
== wrto_loop
)
2049 /* If the value of the use changes in the inner loop, we cannot express
2050 its value in the outer loop (we might try to return interval chrec,
2051 but we do not have a user for it anyway) */
2052 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2054 return chrec_dont_know
;
2056 use_loop
= loop_outer (use_loop
);
2060 /* Returns from CACHE the value for VERSION instantiated below
2061 INSTANTIATED_BELOW block. */
2064 get_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2067 struct scev_info_str
*info
, pattern
;
2069 pattern
.var
= version
;
2070 pattern
.instantiated_below
= instantiated_below
;
2071 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2079 /* Sets in CACHE the value of VERSION instantiated below basic block
2080 INSTANTIATED_BELOW to VAL. */
2083 set_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2084 tree version
, tree val
)
2086 struct scev_info_str
*info
, pattern
;
2089 pattern
.var
= version
;
2090 pattern
.instantiated_below
= instantiated_below
;
2091 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2094 *slot
= new_scev_info_str (instantiated_below
, version
);
2095 info
= (struct scev_info_str
*) *slot
;
2099 /* Return the closed_loop_phi node for VAR. If there is none, return
2103 loop_closed_phi_def (tree var
)
2108 gimple_stmt_iterator psi
;
2110 if (var
== NULL_TREE
2111 || TREE_CODE (var
) != SSA_NAME
)
2114 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2115 exit
= single_exit (loop
);
2119 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2121 phi
= gsi_stmt (psi
);
2122 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2123 return PHI_RESULT (phi
);
2129 static tree
instantiate_scev_r (basic_block
, struct loop
*, tree
, bool,
2132 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2133 and EVOLUTION_LOOP, that were left under a symbolic form.
2135 CHREC is an SSA_NAME to be instantiated.
2137 CACHE is the cache of already instantiated values.
2139 FOLD_CONVERSIONS should be set to true when the conversions that
2140 may wrap in signed/pointer type are folded, as long as the value of
2141 the chrec is preserved.
2143 SIZE_EXPR is used for computing the size of the expression to be
2144 instantiated, and to stop if it exceeds some limit. */
2147 instantiate_scev_name (basic_block instantiate_below
,
2148 struct loop
*evolution_loop
, tree chrec
,
2149 bool fold_conversions
, htab_t cache
, int size_expr
)
2152 struct loop
*def_loop
;
2153 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2155 /* A parameter (or loop invariant and we do not want to include
2156 evolutions in outer loops), nothing to do. */
2158 || loop_depth (def_bb
->loop_father
) == 0
2159 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2162 /* We cache the value of instantiated variable to avoid exponential
2163 time complexity due to reevaluations. We also store the convenient
2164 value in the cache in order to prevent infinite recursion -- we do
2165 not want to instantiate the SSA_NAME if it is in a mixer
2166 structure. This is used for avoiding the instantiation of
2167 recursively defined functions, such as:
2169 | a_2 -> {0, +, 1, +, a_2}_1 */
2171 res
= get_instantiated_value (cache
, instantiate_below
, chrec
);
2175 res
= chrec_dont_know
;
2176 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2178 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2180 /* If the analysis yields a parametric chrec, instantiate the
2182 res
= analyze_scalar_evolution (def_loop
, chrec
);
2184 /* Don't instantiate loop-closed-ssa phi nodes. */
2185 if (TREE_CODE (res
) == SSA_NAME
2186 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2187 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2188 > loop_depth (def_loop
))))
2191 res
= loop_closed_phi_def (chrec
);
2195 if (res
== NULL_TREE
2196 || !dominated_by_p (CDI_DOMINATORS
, instantiate_below
,
2197 gimple_bb (SSA_NAME_DEF_STMT (res
))))
2198 res
= chrec_dont_know
;
2201 else if (res
!= chrec_dont_know
)
2202 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, res
,
2203 fold_conversions
, cache
, size_expr
);
2205 /* Store the correct value to the cache. */
2206 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2211 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2212 and EVOLUTION_LOOP, that were left under a symbolic form.
2214 CHREC is a polynomial chain of recurrence to be instantiated.
2216 CACHE is the cache of already instantiated values.
2218 FOLD_CONVERSIONS should be set to true when the conversions that
2219 may wrap in signed/pointer type are folded, as long as the value of
2220 the chrec is preserved.
2222 SIZE_EXPR is used for computing the size of the expression to be
2223 instantiated, and to stop if it exceeds some limit. */
2226 instantiate_scev_poly (basic_block instantiate_below
,
2227 struct loop
*evolution_loop
, tree chrec
,
2228 bool fold_conversions
, htab_t cache
, int size_expr
)
2231 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2232 CHREC_LEFT (chrec
), fold_conversions
, cache
,
2234 if (op0
== chrec_dont_know
)
2235 return chrec_dont_know
;
2237 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2238 CHREC_RIGHT (chrec
), fold_conversions
, cache
,
2240 if (op1
== chrec_dont_know
)
2241 return chrec_dont_know
;
2243 if (CHREC_LEFT (chrec
) != op0
2244 || CHREC_RIGHT (chrec
) != op1
)
2246 unsigned var
= CHREC_VARIABLE (chrec
);
2248 /* When the instantiated stride or base has an evolution in an
2249 innermost loop, return chrec_dont_know, as this is not a
2250 valid SCEV representation. In the reduced testcase for
2251 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2253 if ((tree_is_chrec (op0
) && CHREC_VARIABLE (op0
) > var
)
2254 || (tree_is_chrec (op1
) && CHREC_VARIABLE (op1
) > var
))
2255 return chrec_dont_know
;
2257 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2258 chrec
= build_polynomial_chrec (var
, op0
, op1
);
2264 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2265 and EVOLUTION_LOOP, that were left under a symbolic form.
2267 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2269 CACHE is the cache of already instantiated values.
2271 FOLD_CONVERSIONS should be set to true when the conversions that
2272 may wrap in signed/pointer type are folded, as long as the value of
2273 the chrec is preserved.
2275 SIZE_EXPR is used for computing the size of the expression to be
2276 instantiated, and to stop if it exceeds some limit. */
2279 instantiate_scev_binary (basic_block instantiate_below
,
2280 struct loop
*evolution_loop
, tree chrec
, enum tree_code code
,
2281 tree type
, tree c0
, tree c1
,
2282 bool fold_conversions
, htab_t cache
, int size_expr
)
2285 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2286 c0
, fold_conversions
, cache
,
2288 if (op0
== chrec_dont_know
)
2289 return chrec_dont_know
;
2291 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2292 c1
, fold_conversions
, cache
,
2294 if (op1
== chrec_dont_know
)
2295 return chrec_dont_know
;
2300 op0
= chrec_convert (type
, op0
, NULL
);
2301 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2305 case POINTER_PLUS_EXPR
:
2307 return chrec_fold_plus (type
, op0
, op1
);
2310 return chrec_fold_minus (type
, op0
, op1
);
2313 return chrec_fold_multiply (type
, op0
, op1
);
2320 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2323 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2324 and EVOLUTION_LOOP, that were left under a symbolic form.
2326 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2329 CACHE is the cache of already instantiated values.
2331 FOLD_CONVERSIONS should be set to true when the conversions that
2332 may wrap in signed/pointer type are folded, as long as the value of
2333 the chrec is preserved.
2335 SIZE_EXPR is used for computing the size of the expression to be
2336 instantiated, and to stop if it exceeds some limit. */
2339 instantiate_scev_convert (basic_block instantiate_below
,
2340 struct loop
*evolution_loop
, tree chrec
,
2342 bool fold_conversions
, htab_t cache
, int size_expr
)
2344 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2345 fold_conversions
, cache
, size_expr
);
2347 if (op0
== chrec_dont_know
)
2348 return chrec_dont_know
;
2350 if (fold_conversions
)
2352 tree tmp
= chrec_convert_aggressive (type
, op0
);
2357 if (chrec
&& op0
== op
)
2360 /* If we used chrec_convert_aggressive, we can no longer assume that
2361 signed chrecs do not overflow, as chrec_convert does, so avoid
2362 calling it in that case. */
2363 if (fold_conversions
)
2364 return fold_convert (type
, op0
);
2366 return chrec_convert (type
, op0
, NULL
);
2369 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2370 and EVOLUTION_LOOP, that were left under a symbolic form.
2372 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2373 Handle ~X as -1 - X.
2374 Handle -X as -1 * X.
2376 CACHE is the cache of already instantiated values.
2378 FOLD_CONVERSIONS should be set to true when the conversions that
2379 may wrap in signed/pointer type are folded, as long as the value of
2380 the chrec is preserved.
2382 SIZE_EXPR is used for computing the size of the expression to be
2383 instantiated, and to stop if it exceeds some limit. */
2386 instantiate_scev_not (basic_block instantiate_below
,
2387 struct loop
*evolution_loop
, tree chrec
,
2388 enum tree_code code
, tree type
, tree op
,
2389 bool fold_conversions
, htab_t cache
, int size_expr
)
2391 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, op
,
2392 fold_conversions
, cache
, size_expr
);
2394 if (op0
== chrec_dont_know
)
2395 return chrec_dont_know
;
2399 op0
= chrec_convert (type
, op0
, NULL
);
2404 return chrec_fold_minus
2405 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2408 return chrec_fold_multiply
2409 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2416 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2419 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2420 and EVOLUTION_LOOP, that were left under a symbolic form.
2422 CHREC is an expression with 3 operands to be instantiated.
2424 CACHE is the cache of already instantiated values.
2426 FOLD_CONVERSIONS should be set to true when the conversions that
2427 may wrap in signed/pointer type are folded, as long as the value of
2428 the chrec is preserved.
2430 SIZE_EXPR is used for computing the size of the expression to be
2431 instantiated, and to stop if it exceeds some limit. */
2434 instantiate_scev_3 (basic_block instantiate_below
,
2435 struct loop
*evolution_loop
, tree chrec
,
2436 bool fold_conversions
, htab_t cache
, int size_expr
)
2439 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2440 TREE_OPERAND (chrec
, 0),
2441 fold_conversions
, cache
, size_expr
);
2442 if (op0
== chrec_dont_know
)
2443 return chrec_dont_know
;
2445 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2446 TREE_OPERAND (chrec
, 1),
2447 fold_conversions
, cache
, size_expr
);
2448 if (op1
== chrec_dont_know
)
2449 return chrec_dont_know
;
2451 op2
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2452 TREE_OPERAND (chrec
, 2),
2453 fold_conversions
, cache
, size_expr
);
2454 if (op2
== chrec_dont_know
)
2455 return chrec_dont_know
;
2457 if (op0
== TREE_OPERAND (chrec
, 0)
2458 && op1
== TREE_OPERAND (chrec
, 1)
2459 && op2
== TREE_OPERAND (chrec
, 2))
2462 return fold_build3 (TREE_CODE (chrec
),
2463 TREE_TYPE (chrec
), op0
, op1
, op2
);
2466 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2467 and EVOLUTION_LOOP, that were left under a symbolic form.
2469 CHREC is an expression with 2 operands to be instantiated.
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_2 (basic_block instantiate_below
,
2482 struct loop
*evolution_loop
, tree chrec
,
2483 bool fold_conversions
, htab_t cache
, int size_expr
)
2486 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2487 TREE_OPERAND (chrec
, 0),
2488 fold_conversions
, cache
, size_expr
);
2489 if (op0
== chrec_dont_know
)
2490 return chrec_dont_know
;
2492 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2493 TREE_OPERAND (chrec
, 1),
2494 fold_conversions
, cache
, size_expr
);
2495 if (op1
== chrec_dont_know
)
2496 return chrec_dont_know
;
2498 if (op0
== TREE_OPERAND (chrec
, 0)
2499 && op1
== TREE_OPERAND (chrec
, 1))
2502 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2505 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2506 and EVOLUTION_LOOP, that were left under a symbolic form.
2508 CHREC is an expression with 2 operands to be instantiated.
2510 CACHE is the cache of already instantiated values.
2512 FOLD_CONVERSIONS should be set to true when the conversions that
2513 may wrap in signed/pointer type are folded, as long as the value of
2514 the chrec is preserved.
2516 SIZE_EXPR is used for computing the size of the expression to be
2517 instantiated, and to stop if it exceeds some limit. */
2520 instantiate_scev_1 (basic_block instantiate_below
,
2521 struct loop
*evolution_loop
, tree chrec
,
2522 bool fold_conversions
, htab_t cache
, int size_expr
)
2524 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2525 TREE_OPERAND (chrec
, 0),
2526 fold_conversions
, cache
, size_expr
);
2528 if (op0
== chrec_dont_know
)
2529 return chrec_dont_know
;
2531 if (op0
== TREE_OPERAND (chrec
, 0))
2534 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2537 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2538 and EVOLUTION_LOOP, that were left under a symbolic form.
2540 CHREC is the scalar evolution to instantiate.
2542 CACHE is the cache of already instantiated values.
2544 FOLD_CONVERSIONS should be set to true when the conversions that
2545 may wrap in signed/pointer type are folded, as long as the value of
2546 the chrec is preserved.
2548 SIZE_EXPR is used for computing the size of the expression to be
2549 instantiated, and to stop if it exceeds some limit. */
2552 instantiate_scev_r (basic_block instantiate_below
,
2553 struct loop
*evolution_loop
, tree chrec
,
2554 bool fold_conversions
, htab_t cache
, int size_expr
)
2556 /* Give up if the expression is larger than the MAX that we allow. */
2557 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2558 return chrec_dont_know
;
2560 if (automatically_generated_chrec_p (chrec
)
2561 || is_gimple_min_invariant (chrec
))
2564 switch (TREE_CODE (chrec
))
2567 return instantiate_scev_name (instantiate_below
, evolution_loop
, chrec
,
2568 fold_conversions
, cache
, size_expr
);
2570 case POLYNOMIAL_CHREC
:
2571 return instantiate_scev_poly (instantiate_below
, evolution_loop
, chrec
,
2572 fold_conversions
, cache
, size_expr
);
2574 case POINTER_PLUS_EXPR
:
2578 return instantiate_scev_binary (instantiate_below
, evolution_loop
, chrec
,
2579 TREE_CODE (chrec
), chrec_type (chrec
),
2580 TREE_OPERAND (chrec
, 0),
2581 TREE_OPERAND (chrec
, 1),
2582 fold_conversions
, cache
, size_expr
);
2585 return instantiate_scev_convert (instantiate_below
, evolution_loop
, chrec
,
2586 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2587 fold_conversions
, cache
, size_expr
);
2591 return instantiate_scev_not (instantiate_below
, evolution_loop
, chrec
,
2592 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2593 TREE_OPERAND (chrec
, 0),
2594 fold_conversions
, cache
, size_expr
);
2596 case SCEV_NOT_KNOWN
:
2597 return chrec_dont_know
;
2606 if (VL_EXP_CLASS_P (chrec
))
2607 return chrec_dont_know
;
2609 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2612 return instantiate_scev_3 (instantiate_below
, evolution_loop
, chrec
,
2613 fold_conversions
, cache
, size_expr
);
2616 return instantiate_scev_2 (instantiate_below
, evolution_loop
, chrec
,
2617 fold_conversions
, cache
, size_expr
);
2620 return instantiate_scev_1 (instantiate_below
, evolution_loop
, chrec
,
2621 fold_conversions
, cache
, size_expr
);
2630 /* Too complicated to handle. */
2631 return chrec_dont_know
;
2634 /* Analyze all the parameters of the chrec that were left under a
2635 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2636 recursive instantiation of parameters: a parameter is a variable
2637 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2638 a function parameter. */
2641 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2645 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2647 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2649 fprintf (dump_file
, "(instantiate_scev \n");
2650 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2651 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2652 fprintf (dump_file
, " (chrec = ");
2653 print_generic_expr (dump_file
, chrec
, 0);
2654 fprintf (dump_file
, ")\n");
2657 res
= instantiate_scev_r (instantiate_below
, evolution_loop
, chrec
, false,
2660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2662 fprintf (dump_file
, " (res = ");
2663 print_generic_expr (dump_file
, res
, 0);
2664 fprintf (dump_file
, "))\n");
2667 htab_delete (cache
);
2672 /* Similar to instantiate_parameters, but does not introduce the
2673 evolutions in outer loops for LOOP invariants in CHREC, and does not
2674 care about causing overflows, as long as they do not affect value
2675 of an expression. */
2678 resolve_mixers (struct loop
*loop
, tree chrec
)
2680 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2681 tree ret
= instantiate_scev_r (block_before_loop (loop
), loop
, chrec
, true,
2683 htab_delete (cache
);
2687 /* Entry point for the analysis of the number of iterations pass.
2688 This function tries to safely approximate the number of iterations
2689 the loop will run. When this property is not decidable at compile
2690 time, the result is chrec_dont_know. Otherwise the result is
2691 a scalar or a symbolic parameter.
2693 Example of analysis: suppose that the loop has an exit condition:
2695 "if (b > 49) goto end_loop;"
2697 and that in a previous analysis we have determined that the
2698 variable 'b' has an evolution function:
2700 "EF = {23, +, 5}_2".
2702 When we evaluate the function at the point 5, i.e. the value of the
2703 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2704 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2705 the loop body has been executed 6 times. */
2708 number_of_latch_executions (struct loop
*loop
)
2712 struct tree_niter_desc niter_desc
;
2714 /* Determine whether the number_of_iterations_in_loop has already
2716 res
= loop
->nb_iterations
;
2719 res
= chrec_dont_know
;
2721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2722 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2724 exit
= single_exit (loop
);
2728 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2731 type
= TREE_TYPE (niter_desc
.niter
);
2732 if (integer_nonzerop (niter_desc
.may_be_zero
))
2733 res
= build_int_cst (type
, 0);
2734 else if (integer_zerop (niter_desc
.may_be_zero
))
2735 res
= niter_desc
.niter
;
2737 res
= chrec_dont_know
;
2740 return set_nb_iterations_in_loop (loop
, res
);
2743 /* Returns the number of executions of the exit condition of LOOP,
2744 i.e., the number by one higher than number_of_latch_executions.
2745 Note that unlike number_of_latch_executions, this number does
2746 not necessarily fit in the unsigned variant of the type of
2747 the control variable -- if the number of iterations is a constant,
2748 we return chrec_dont_know if adding one to number_of_latch_executions
2749 overflows; however, in case the number of iterations is symbolic
2750 expression, the caller is responsible for dealing with this
2751 the possible overflow. */
2754 number_of_exit_cond_executions (struct loop
*loop
)
2756 tree ret
= number_of_latch_executions (loop
);
2757 tree type
= chrec_type (ret
);
2759 if (chrec_contains_undetermined (ret
))
2762 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2763 if (TREE_CODE (ret
) == INTEGER_CST
2764 && TREE_OVERFLOW (ret
))
2765 return chrec_dont_know
;
2770 /* One of the drivers for testing the scalar evolutions analysis.
2771 This function computes the number of iterations for all the loops
2772 from the EXIT_CONDITIONS array. */
2775 number_of_iterations_for_all_loops (VEC(gimple
,heap
) **exit_conditions
)
2778 unsigned nb_chrec_dont_know_loops
= 0;
2779 unsigned nb_static_loops
= 0;
2782 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2784 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2785 if (chrec_contains_undetermined (res
))
2786 nb_chrec_dont_know_loops
++;
2793 fprintf (dump_file
, "\n(\n");
2794 fprintf (dump_file
, "-----------------------------------------\n");
2795 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2796 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2797 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2798 fprintf (dump_file
, "-----------------------------------------\n");
2799 fprintf (dump_file
, ")\n\n");
2801 print_loops (dump_file
, 3);
2807 /* Counters for the stats. */
2813 unsigned nb_affine_multivar
;
2814 unsigned nb_higher_poly
;
2815 unsigned nb_chrec_dont_know
;
2816 unsigned nb_undetermined
;
2819 /* Reset the counters. */
2822 reset_chrecs_counters (struct chrec_stats
*stats
)
2824 stats
->nb_chrecs
= 0;
2825 stats
->nb_affine
= 0;
2826 stats
->nb_affine_multivar
= 0;
2827 stats
->nb_higher_poly
= 0;
2828 stats
->nb_chrec_dont_know
= 0;
2829 stats
->nb_undetermined
= 0;
2832 /* Dump the contents of a CHREC_STATS structure. */
2835 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2837 fprintf (file
, "\n(\n");
2838 fprintf (file
, "-----------------------------------------\n");
2839 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2840 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2841 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2842 stats
->nb_higher_poly
);
2843 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2844 fprintf (file
, "-----------------------------------------\n");
2845 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2846 fprintf (file
, "%d\twith undetermined coefficients\n",
2847 stats
->nb_undetermined
);
2848 fprintf (file
, "-----------------------------------------\n");
2849 fprintf (file
, "%d\tchrecs in the scev database\n",
2850 (int) htab_elements (scalar_evolution_info
));
2851 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2852 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2853 fprintf (file
, "-----------------------------------------\n");
2854 fprintf (file
, ")\n\n");
2857 /* Gather statistics about CHREC. */
2860 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2862 if (dump_file
&& (dump_flags
& TDF_STATS
))
2864 fprintf (dump_file
, "(classify_chrec ");
2865 print_generic_expr (dump_file
, chrec
, 0);
2866 fprintf (dump_file
, "\n");
2871 if (chrec
== NULL_TREE
)
2873 stats
->nb_undetermined
++;
2877 switch (TREE_CODE (chrec
))
2879 case POLYNOMIAL_CHREC
:
2880 if (evolution_function_is_affine_p (chrec
))
2882 if (dump_file
&& (dump_flags
& TDF_STATS
))
2883 fprintf (dump_file
, " affine_univariate\n");
2886 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2888 if (dump_file
&& (dump_flags
& TDF_STATS
))
2889 fprintf (dump_file
, " affine_multivariate\n");
2890 stats
->nb_affine_multivar
++;
2894 if (dump_file
&& (dump_flags
& TDF_STATS
))
2895 fprintf (dump_file
, " higher_degree_polynomial\n");
2896 stats
->nb_higher_poly
++;
2905 if (chrec_contains_undetermined (chrec
))
2907 if (dump_file
&& (dump_flags
& TDF_STATS
))
2908 fprintf (dump_file
, " undetermined\n");
2909 stats
->nb_undetermined
++;
2912 if (dump_file
&& (dump_flags
& TDF_STATS
))
2913 fprintf (dump_file
, ")\n");
2916 /* One of the drivers for testing the scalar evolutions analysis.
2917 This function analyzes the scalar evolution of all the scalars
2918 defined as loop phi nodes in one of the loops from the
2919 EXIT_CONDITIONS array.
2921 TODO Optimization: A loop is in canonical form if it contains only
2922 a single scalar loop phi node. All the other scalars that have an
2923 evolution in the loop are rewritten in function of this single
2924 index. This allows the parallelization of the loop. */
2927 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple
,heap
) **exit_conditions
)
2930 struct chrec_stats stats
;
2932 gimple_stmt_iterator psi
;
2934 reset_chrecs_counters (&stats
);
2936 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2942 loop
= loop_containing_stmt (cond
);
2945 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2947 phi
= gsi_stmt (psi
);
2948 if (is_gimple_reg (PHI_RESULT (phi
)))
2950 chrec
= instantiate_parameters
2952 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2954 if (dump_file
&& (dump_flags
& TDF_STATS
))
2955 gather_chrec_stats (chrec
, &stats
);
2960 if (dump_file
&& (dump_flags
& TDF_STATS
))
2961 dump_chrecs_stats (dump_file
, &stats
);
2964 /* Callback for htab_traverse, gathers information on chrecs in the
2968 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2970 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2972 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2977 /* Classify the chrecs of the whole database. */
2980 gather_stats_on_scev_database (void)
2982 struct chrec_stats stats
;
2987 reset_chrecs_counters (&stats
);
2989 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2992 dump_chrecs_stats (dump_file
, &stats
);
3000 initialize_scalar_evolutions_analyzer (void)
3002 /* The elements below are unique. */
3003 if (chrec_dont_know
== NULL_TREE
)
3005 chrec_not_analyzed_yet
= NULL_TREE
;
3006 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
3007 chrec_known
= make_node (SCEV_KNOWN
);
3008 TREE_TYPE (chrec_dont_know
) = void_type_node
;
3009 TREE_TYPE (chrec_known
) = void_type_node
;
3013 /* Initialize the analysis of scalar evolutions for LOOPS. */
3016 scev_initialize (void)
3021 scalar_evolution_info
= htab_create_alloc (100,
3028 initialize_scalar_evolutions_analyzer ();
3030 FOR_EACH_LOOP (li
, loop
, 0)
3032 loop
->nb_iterations
= NULL_TREE
;
3036 /* Cleans up the information cached by the scalar evolutions analysis
3037 in the hash table. */
3040 scev_reset_htab (void)
3042 if (!scalar_evolution_info
)
3045 htab_empty (scalar_evolution_info
);
3048 /* Cleans up the information cached by the scalar evolutions analysis
3049 in the hash table and in the loop->nb_iterations. */
3062 FOR_EACH_LOOP (li
, loop
, 0)
3064 loop
->nb_iterations
= NULL_TREE
;
3068 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3069 respect to WRTO_LOOP and returns its base and step in IV if possible
3070 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3071 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3072 invariant in LOOP. Otherwise we require it to be an integer constant.
3074 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3075 because it is computed in signed arithmetics). Consequently, adding an
3078 for (i = IV->base; ; i += IV->step)
3080 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3081 false for the type of the induction variable, or you can prove that i does
3082 not wrap by some other argument. Otherwise, this might introduce undefined
3085 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3087 must be used instead. */
3090 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
3091 affine_iv
*iv
, bool allow_nonconstant_step
)
3096 iv
->base
= NULL_TREE
;
3097 iv
->step
= NULL_TREE
;
3098 iv
->no_overflow
= false;
3100 type
= TREE_TYPE (op
);
3101 if (TREE_CODE (type
) != INTEGER_TYPE
3102 && TREE_CODE (type
) != POINTER_TYPE
)
3105 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3107 if (chrec_contains_undetermined (ev
)
3108 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3111 if (tree_does_not_contain_chrecs (ev
))
3114 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3115 iv
->no_overflow
= true;
3119 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
3120 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3123 iv
->step
= CHREC_RIGHT (ev
);
3124 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3125 || tree_contains_chrecs (iv
->step
, NULL
))
3128 iv
->base
= CHREC_LEFT (ev
);
3129 if (tree_contains_chrecs (iv
->base
, NULL
))
3132 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
3137 /* Runs the analysis of scalar evolutions. */
3140 scev_analysis (void)
3142 VEC(gimple
,heap
) *exit_conditions
;
3144 exit_conditions
= VEC_alloc (gimple
, heap
, 37);
3145 select_loops_exit_conditions (&exit_conditions
);
3147 if (dump_file
&& (dump_flags
& TDF_STATS
))
3148 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
3150 number_of_iterations_for_all_loops (&exit_conditions
);
3151 VEC_free (gimple
, heap
, exit_conditions
);
3154 /* Finalize the scalar evolution analysis. */
3157 scev_finalize (void)
3159 if (!scalar_evolution_info
)
3161 htab_delete (scalar_evolution_info
);
3162 scalar_evolution_info
= NULL
;
3165 /* Returns true if the expression EXPR is considered to be too expensive
3166 for scev_const_prop. */
3169 expression_expensive_p (tree expr
)
3171 enum tree_code code
;
3173 if (is_gimple_val (expr
))
3176 code
= TREE_CODE (expr
);
3177 if (code
== TRUNC_DIV_EXPR
3178 || code
== CEIL_DIV_EXPR
3179 || code
== FLOOR_DIV_EXPR
3180 || code
== ROUND_DIV_EXPR
3181 || code
== TRUNC_MOD_EXPR
3182 || code
== CEIL_MOD_EXPR
3183 || code
== FLOOR_MOD_EXPR
3184 || code
== ROUND_MOD_EXPR
3185 || code
== EXACT_DIV_EXPR
)
3187 /* Division by power of two is usually cheap, so we allow it.
3188 Forbid anything else. */
3189 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3193 switch (TREE_CODE_CLASS (code
))
3196 case tcc_comparison
:
3197 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
3202 return expression_expensive_p (TREE_OPERAND (expr
, 0));
3209 /* Replace ssa names for that scev can prove they are constant by the
3210 appropriate constants. Also perform final value replacement in loops,
3211 in case the replacement expressions are cheap.
3213 We only consider SSA names defined by phi nodes; rest is left to the
3214 ordinary constant propagation pass. */
3217 scev_const_prop (void)
3220 tree name
, type
, ev
;
3222 struct loop
*loop
, *ex_loop
;
3223 bitmap ssa_names_to_remove
= NULL
;
3226 gimple_stmt_iterator psi
;
3228 if (number_of_loops () <= 1)
3233 loop
= bb
->loop_father
;
3235 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
3237 phi
= gsi_stmt (psi
);
3238 name
= PHI_RESULT (phi
);
3240 if (!is_gimple_reg (name
))
3243 type
= TREE_TYPE (name
);
3245 if (!POINTER_TYPE_P (type
)
3246 && !INTEGRAL_TYPE_P (type
))
3249 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3250 if (!is_gimple_min_invariant (ev
)
3251 || !may_propagate_copy (name
, ev
))
3254 /* Replace the uses of the name. */
3256 replace_uses_by (name
, ev
);
3258 if (!ssa_names_to_remove
)
3259 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3260 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3264 /* Remove the ssa names that were replaced by constants. We do not
3265 remove them directly in the previous cycle, since this
3266 invalidates scev cache. */
3267 if (ssa_names_to_remove
)
3271 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3273 gimple_stmt_iterator psi
;
3274 name
= ssa_name (i
);
3275 phi
= SSA_NAME_DEF_STMT (name
);
3277 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3278 psi
= gsi_for_stmt (phi
);
3279 remove_phi_node (&psi
, true);
3282 BITMAP_FREE (ssa_names_to_remove
);
3286 /* Now the regular final value replacement. */
3287 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3290 tree def
, rslt
, niter
;
3291 gimple_stmt_iterator bsi
;
3293 /* If we do not know exact number of iterations of the loop, we cannot
3294 replace the final value. */
3295 exit
= single_exit (loop
);
3299 niter
= number_of_latch_executions (loop
);
3300 if (niter
== chrec_dont_know
)
3303 /* Ensure that it is possible to insert new statements somewhere. */
3304 if (!single_pred_p (exit
->dest
))
3305 split_loop_exit_edge (exit
);
3306 bsi
= gsi_after_labels (exit
->dest
);
3308 ex_loop
= superloop_at_depth (loop
,
3309 loop_depth (exit
->dest
->loop_father
) + 1);
3311 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3313 phi
= gsi_stmt (psi
);
3314 rslt
= PHI_RESULT (phi
);
3315 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3316 if (!is_gimple_reg (def
))
3322 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3323 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3329 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3330 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3331 if (!tree_does_not_contain_chrecs (def
)
3332 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3333 /* Moving the computation from the loop may prolong life range
3334 of some ssa names, which may cause problems if they appear
3335 on abnormal edges. */
3336 || contains_abnormal_ssa_name_p (def
)
3337 /* Do not emit expensive expressions. The rationale is that
3338 when someone writes a code like
3340 while (n > 45) n -= 45;
3342 he probably knows that n is not large, and does not want it
3343 to be turned into n %= 45. */
3344 || expression_expensive_p (def
))
3350 /* Eliminate the PHI node and replace it by a computation outside
3352 def
= unshare_expr (def
);
3353 remove_phi_node (&psi
, false);
3355 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3356 true, GSI_SAME_STMT
);
3357 ass
= gimple_build_assign (rslt
, def
);
3358 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3364 #include "gt-tree-scalar-evolution.h"