1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
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 /* Continue the computation until ending on a parent of LOOP. */
497 return compute_overall_effect_of_inner_loop (loop
, res
);
504 /* If the evolution function is an invariant, there is nothing to do. */
505 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
509 return chrec_dont_know
;
512 /* Determine whether the CHREC is always positive/negative. If the expression
513 cannot be statically analyzed, return false, otherwise set the answer into
517 chrec_is_positive (tree chrec
, bool *value
)
519 bool value0
, value1
, value2
;
520 tree end_value
, nb_iter
;
522 switch (TREE_CODE (chrec
))
524 case POLYNOMIAL_CHREC
:
525 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
526 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
529 /* FIXME -- overflows. */
530 if (value0
== value1
)
536 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
537 and the proof consists in showing that the sign never
538 changes during the execution of the loop, from 0 to
539 loop->nb_iterations. */
540 if (!evolution_function_is_affine_p (chrec
))
543 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
544 if (chrec_contains_undetermined (nb_iter
))
548 /* TODO -- If the test is after the exit, we may decrease the number of
549 iterations by one. */
551 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
554 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
556 if (!chrec_is_positive (end_value
, &value2
))
560 return value0
== value1
;
563 *value
= (tree_int_cst_sgn (chrec
) == 1);
571 /* Associate CHREC to SCALAR. */
574 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
578 if (TREE_CODE (scalar
) != SSA_NAME
)
581 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
585 if (dump_flags
& TDF_DETAILS
)
587 fprintf (dump_file
, "(set_scalar_evolution \n");
588 fprintf (dump_file
, " instantiated_below = %d \n",
589 instantiated_below
->index
);
590 fprintf (dump_file
, " (scalar = ");
591 print_generic_expr (dump_file
, scalar
, 0);
592 fprintf (dump_file
, ")\n (scalar_evolution = ");
593 print_generic_expr (dump_file
, chrec
, 0);
594 fprintf (dump_file
, "))\n");
596 if (dump_flags
& TDF_STATS
)
600 *scalar_info
= chrec
;
603 /* Retrieve the chrec associated to SCALAR instantiated below
604 INSTANTIATED_BELOW block. */
607 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
613 if (dump_flags
& TDF_DETAILS
)
615 fprintf (dump_file
, "(get_scalar_evolution \n");
616 fprintf (dump_file
, " (scalar = ");
617 print_generic_expr (dump_file
, scalar
, 0);
618 fprintf (dump_file
, ")\n");
620 if (dump_flags
& TDF_STATS
)
624 switch (TREE_CODE (scalar
))
627 res
= *find_var_scev_info (instantiated_below
, scalar
);
637 res
= chrec_not_analyzed_yet
;
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 fprintf (dump_file
, " (scalar_evolution = ");
644 print_generic_expr (dump_file
, res
, 0);
645 fprintf (dump_file
, "))\n");
651 /* Helper function for add_to_evolution. Returns the evolution
652 function for an assignment of the form "a = b + c", where "a" and
653 "b" are on the strongly connected component. CHREC_BEFORE is the
654 information that we already have collected up to this point.
655 TO_ADD is the evolution of "c".
657 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
658 evolution the expression TO_ADD, otherwise construct an evolution
659 part for this loop. */
662 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
665 tree type
, left
, right
;
666 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
668 switch (TREE_CODE (chrec_before
))
670 case POLYNOMIAL_CHREC
:
671 chloop
= get_chrec_loop (chrec_before
);
673 || flow_loop_nested_p (chloop
, loop
))
677 type
= chrec_type (chrec_before
);
679 /* When there is no evolution part in this loop, build it. */
684 right
= SCALAR_FLOAT_TYPE_P (type
)
685 ? build_real (type
, dconst0
)
686 : build_int_cst (type
, 0);
690 var
= CHREC_VARIABLE (chrec_before
);
691 left
= CHREC_LEFT (chrec_before
);
692 right
= CHREC_RIGHT (chrec_before
);
695 to_add
= chrec_convert (type
, to_add
, at_stmt
);
696 right
= chrec_convert_rhs (type
, right
, at_stmt
);
697 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
698 return build_polynomial_chrec (var
, left
, right
);
702 gcc_assert (flow_loop_nested_p (loop
, chloop
));
704 /* Search the evolution in LOOP_NB. */
705 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
707 right
= CHREC_RIGHT (chrec_before
);
708 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
709 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
714 /* These nodes do not depend on a loop. */
715 if (chrec_before
== chrec_dont_know
)
716 return chrec_dont_know
;
719 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
720 return build_polynomial_chrec (loop_nb
, left
, right
);
724 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
727 Description (provided for completeness, for those who read code in
728 a plane, and for my poor 62 bytes brain that would have forgotten
729 all this in the next two or three months):
731 The algorithm of translation of programs from the SSA representation
732 into the chrecs syntax is based on a pattern matching. After having
733 reconstructed the overall tree expression for a loop, there are only
734 two cases that can arise:
736 1. a = loop-phi (init, a + expr)
737 2. a = loop-phi (init, expr)
739 where EXPR is either a scalar constant with respect to the analyzed
740 loop (this is a degree 0 polynomial), or an expression containing
741 other loop-phi definitions (these are higher degree polynomials).
748 | a = phi (init, a + 5)
755 | a = phi (inita, 2 * b + 3)
756 | b = phi (initb, b + 1)
759 For the first case, the semantics of the SSA representation is:
761 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
763 that is, there is a loop index "x" that determines the scalar value
764 of the variable during the loop execution. During the first
765 iteration, the value is that of the initial condition INIT, while
766 during the subsequent iterations, it is the sum of the initial
767 condition with the sum of all the values of EXPR from the initial
768 iteration to the before last considered iteration.
770 For the second case, the semantics of the SSA program is:
772 | a (x) = init, if x = 0;
773 | expr (x - 1), otherwise.
775 The second case corresponds to the PEELED_CHREC, whose syntax is
776 close to the syntax of a loop-phi-node:
778 | phi (init, expr) vs. (init, expr)_x
780 The proof of the translation algorithm for the first case is a
781 proof by structural induction based on the degree of EXPR.
784 When EXPR is a constant with respect to the analyzed loop, or in
785 other words when EXPR is a polynomial of degree 0, the evolution of
786 the variable A in the loop is an affine function with an initial
787 condition INIT, and a step EXPR. In order to show this, we start
788 from the semantics of the SSA representation:
790 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
792 and since "expr (j)" is a constant with respect to "j",
794 f (x) = init + x * expr
796 Finally, based on the semantics of the pure sum chrecs, by
797 identification we get the corresponding chrecs syntax:
799 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
800 f (x) -> {init, +, expr}_x
803 Suppose that EXPR is a polynomial of degree N with respect to the
804 analyzed loop_x for which we have already determined that it is
805 written under the chrecs syntax:
807 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
809 We start from the semantics of the SSA program:
811 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
813 | f (x) = init + \sum_{j = 0}^{x - 1}
814 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
816 | f (x) = init + \sum_{j = 0}^{x - 1}
817 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
819 | f (x) = init + \sum_{k = 0}^{n - 1}
820 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
822 | f (x) = init + \sum_{k = 0}^{n - 1}
823 | (b_k * \binom{x}{k + 1})
825 | f (x) = init + b_0 * \binom{x}{1} + ...
826 | + b_{n-1} * \binom{x}{n}
828 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
829 | + b_{n-1} * \binom{x}{n}
832 And finally from the definition of the chrecs syntax, we identify:
833 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
835 This shows the mechanism that stands behind the add_to_evolution
836 function. An important point is that the use of symbolic
837 parameters avoids the need of an analysis schedule.
844 | a = phi (inita, a + 2 + b)
845 | b = phi (initb, b + 1)
848 When analyzing "a", the algorithm keeps "b" symbolically:
850 | a -> {inita, +, 2 + b}_1
852 Then, after instantiation, the analyzer ends on the evolution:
854 | a -> {inita, +, 2 + initb, +, 1}_1
859 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
860 tree to_add
, gimple at_stmt
)
862 tree type
= chrec_type (to_add
);
863 tree res
= NULL_TREE
;
865 if (to_add
== NULL_TREE
)
868 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
869 instantiated at this point. */
870 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
871 /* This should not happen. */
872 return chrec_dont_know
;
874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "(add_to_evolution \n");
877 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
878 fprintf (dump_file
, " (chrec_before = ");
879 print_generic_expr (dump_file
, chrec_before
, 0);
880 fprintf (dump_file
, ")\n (to_add = ");
881 print_generic_expr (dump_file
, to_add
, 0);
882 fprintf (dump_file
, ")\n");
885 if (code
== MINUS_EXPR
)
886 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
887 ? build_real (type
, dconstm1
)
888 : build_int_cst_type (type
, -1));
890 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
894 fprintf (dump_file
, " (res = ");
895 print_generic_expr (dump_file
, res
, 0);
896 fprintf (dump_file
, "))\n");
902 /* Helper function. */
905 set_nb_iterations_in_loop (struct loop
*loop
,
908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
910 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
911 print_generic_expr (dump_file
, res
, 0);
912 fprintf (dump_file
, "))\n");
915 loop
->nb_iterations
= res
;
921 /* This section selects the loops that will be good candidates for the
922 scalar evolution analysis. For the moment, greedily select all the
923 loop nests we could analyze. */
925 /* For a loop with a single exit edge, return the COND_EXPR that
926 guards the exit edge. If the expression is too difficult to
927 analyze, then give up. */
930 get_loop_exit_condition (const struct loop
*loop
)
933 edge exit_edge
= single_exit (loop
);
935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
936 fprintf (dump_file
, "(get_loop_exit_condition \n ");
942 stmt
= last_stmt (exit_edge
->src
);
943 if (gimple_code (stmt
) == GIMPLE_COND
)
947 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
949 print_gimple_stmt (dump_file
, res
, 0, 0);
950 fprintf (dump_file
, ")\n");
956 /* Recursively determine and enqueue the exit conditions for a loop. */
959 get_exit_conditions_rec (struct loop
*loop
,
960 VEC(gimple
,heap
) **exit_conditions
)
965 /* Recurse on the inner loops, then on the next (sibling) loops. */
966 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
967 get_exit_conditions_rec (loop
->next
, exit_conditions
);
969 if (single_exit (loop
))
971 gimple loop_condition
= get_loop_exit_condition (loop
);
974 VEC_safe_push (gimple
, heap
, *exit_conditions
, loop_condition
);
978 /* Select the candidate loop nests for the analysis. This function
979 initializes the EXIT_CONDITIONS array. */
982 select_loops_exit_conditions (VEC(gimple
,heap
) **exit_conditions
)
984 struct loop
*function_body
= current_loops
->tree_root
;
986 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
990 /* Depth first search algorithm. */
992 typedef enum t_bool
{
999 static t_bool
follow_ssa_edge (struct loop
*loop
, gimple
, gimple
, tree
*, int);
1001 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
1002 Return true if the strongly connected component has been found. */
1005 follow_ssa_edge_binary (struct loop
*loop
, gimple at_stmt
,
1006 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
1007 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1009 t_bool res
= t_false
;
1014 case POINTER_PLUS_EXPR
:
1016 if (TREE_CODE (rhs0
) == SSA_NAME
)
1018 if (TREE_CODE (rhs1
) == SSA_NAME
)
1020 /* Match an assignment under the form:
1023 /* We want only assignments of form "name + name" contribute to
1024 LIMIT, as the other cases do not necessarily contribute to
1025 the complexity of the expression. */
1028 evol
= *evolution_of_loop
;
1029 res
= follow_ssa_edge
1030 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
, &evol
, limit
);
1033 *evolution_of_loop
= add_to_evolution
1035 chrec_convert (type
, evol
, at_stmt
),
1036 code
, rhs1
, at_stmt
);
1038 else if (res
== t_false
)
1040 res
= follow_ssa_edge
1041 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1042 evolution_of_loop
, limit
);
1045 *evolution_of_loop
= add_to_evolution
1047 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1048 code
, rhs0
, at_stmt
);
1050 else if (res
== t_dont_know
)
1051 *evolution_of_loop
= chrec_dont_know
;
1054 else if (res
== t_dont_know
)
1055 *evolution_of_loop
= chrec_dont_know
;
1060 /* Match an assignment under the form:
1062 res
= follow_ssa_edge
1063 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1064 evolution_of_loop
, limit
);
1066 *evolution_of_loop
= add_to_evolution
1067 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1069 code
, rhs1
, at_stmt
);
1071 else if (res
== t_dont_know
)
1072 *evolution_of_loop
= chrec_dont_know
;
1076 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1078 /* Match an assignment under the form:
1080 res
= follow_ssa_edge
1081 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1082 evolution_of_loop
, limit
);
1084 *evolution_of_loop
= add_to_evolution
1085 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1087 code
, rhs0
, at_stmt
);
1089 else if (res
== t_dont_know
)
1090 *evolution_of_loop
= chrec_dont_know
;
1094 /* Otherwise, match an assignment under the form:
1096 /* And there is nothing to do. */
1101 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1102 if (TREE_CODE (rhs0
) == SSA_NAME
)
1104 /* Match an assignment under the form:
1107 /* We want only assignments of form "name - name" contribute to
1108 LIMIT, as the other cases do not necessarily contribute to
1109 the complexity of the expression. */
1110 if (TREE_CODE (rhs1
) == SSA_NAME
)
1113 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1114 evolution_of_loop
, limit
);
1116 *evolution_of_loop
= add_to_evolution
1117 (loop
->num
, chrec_convert (type
, *evolution_of_loop
, at_stmt
),
1118 MINUS_EXPR
, rhs1
, at_stmt
);
1120 else if (res
== t_dont_know
)
1121 *evolution_of_loop
= chrec_dont_know
;
1124 /* Otherwise, match an assignment under the form:
1126 /* And there is nothing to do. */
1137 /* Follow the ssa edge into the expression EXPR.
1138 Return true if the strongly connected component has been found. */
1141 follow_ssa_edge_expr (struct loop
*loop
, gimple at_stmt
, tree expr
,
1142 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1144 t_bool res
= t_false
;
1146 tree type
= TREE_TYPE (expr
);
1147 enum tree_code code
;
1149 /* The EXPR is one of the following cases:
1153 - a POINTER_PLUS_EXPR,
1156 - other cases are not yet handled. */
1157 code
= TREE_CODE (expr
);
1161 /* This assignment is under the form "a_1 = (cast) rhs. */
1162 res
= follow_ssa_edge_expr (loop
, at_stmt
, TREE_OPERAND (expr
, 0),
1163 halting_phi
, evolution_of_loop
, limit
);
1164 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1168 /* This assignment is under the form "a_1 = 7". */
1173 /* This assignment is under the form: "a_1 = b_2". */
1174 res
= follow_ssa_edge
1175 (loop
, SSA_NAME_DEF_STMT (expr
), halting_phi
, evolution_of_loop
, limit
);
1178 case POINTER_PLUS_EXPR
:
1181 /* This case is under the form "rhs0 +- rhs1". */
1182 rhs0
= TREE_OPERAND (expr
, 0);
1183 rhs1
= TREE_OPERAND (expr
, 1);
1184 STRIP_TYPE_NOPS (rhs0
);
1185 STRIP_TYPE_NOPS (rhs1
);
1186 return follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1187 halting_phi
, evolution_of_loop
, limit
);
1191 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1192 It must be handled as a copy assignment of the form a_1 = a_2. */
1193 tree op0
= ASSERT_EXPR_VAR (expr
);
1194 if (TREE_CODE (op0
) == SSA_NAME
)
1195 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1196 halting_phi
, evolution_of_loop
, limit
);
1211 /* Follow the ssa edge into the right hand side of an assignment STMT.
1212 Return true if the strongly connected component has been found. */
1215 follow_ssa_edge_in_rhs (struct loop
*loop
, gimple stmt
,
1216 gimple halting_phi
, tree
*evolution_of_loop
, int limit
)
1218 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1219 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1221 switch (get_gimple_rhs_class (code
))
1223 case GIMPLE_BINARY_RHS
:
1224 return follow_ssa_edge_binary (loop
, stmt
, type
,
1225 gimple_assign_rhs1 (stmt
), code
,
1226 gimple_assign_rhs2 (stmt
),
1227 halting_phi
, evolution_of_loop
, limit
);
1228 case GIMPLE_SINGLE_RHS
:
1229 return follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1230 halting_phi
, evolution_of_loop
, limit
);
1231 case GIMPLE_UNARY_RHS
:
1232 if (code
== NOP_EXPR
)
1234 /* This assignment is under the form "a_1 = (cast) rhs. */
1236 = follow_ssa_edge_expr (loop
, stmt
, gimple_assign_rhs1 (stmt
),
1237 halting_phi
, evolution_of_loop
, limit
);
1238 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, stmt
);
1248 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1251 backedge_phi_arg_p (gimple phi
, int i
)
1253 const_edge e
= gimple_phi_arg_edge (phi
, i
);
1255 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1256 about updating it anywhere, and this should work as well most of the
1258 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1264 /* Helper function for one branch of the condition-phi-node. Return
1265 true if the strongly connected component has been found following
1268 static inline t_bool
1269 follow_ssa_edge_in_condition_phi_branch (int i
,
1271 gimple condition_phi
,
1273 tree
*evolution_of_branch
,
1274 tree init_cond
, int limit
)
1276 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1277 *evolution_of_branch
= chrec_dont_know
;
1279 /* Do not follow back edges (they must belong to an irreducible loop, which
1280 we really do not want to worry about). */
1281 if (backedge_phi_arg_p (condition_phi
, i
))
1284 if (TREE_CODE (branch
) == SSA_NAME
)
1286 *evolution_of_branch
= init_cond
;
1287 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1288 evolution_of_branch
, limit
);
1291 /* This case occurs when one of the condition branches sets
1292 the variable to a constant: i.e. a phi-node like
1293 "a_2 = PHI <a_7(5), 2(6)>;".
1295 FIXME: This case have to be refined correctly:
1296 in some cases it is possible to say something better than
1297 chrec_dont_know, for example using a wrap-around notation. */
1301 /* This function merges the branches of a condition-phi-node in a
1305 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1306 gimple condition_phi
,
1308 tree
*evolution_of_loop
, int limit
)
1311 tree init
= *evolution_of_loop
;
1312 tree evolution_of_branch
;
1313 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1315 &evolution_of_branch
,
1317 if (res
== t_false
|| res
== t_dont_know
)
1320 *evolution_of_loop
= evolution_of_branch
;
1322 n
= gimple_phi_num_args (condition_phi
);
1323 for (i
= 1; i
< n
; i
++)
1325 /* Quickly give up when the evolution of one of the branches is
1327 if (*evolution_of_loop
== chrec_dont_know
)
1330 /* Increase the limit by the PHI argument number to avoid exponential
1331 time and memory complexity. */
1332 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1334 &evolution_of_branch
,
1336 if (res
== t_false
|| res
== t_dont_know
)
1339 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1340 evolution_of_branch
);
1346 /* Follow an SSA edge in an inner loop. It computes the overall
1347 effect of the loop, and following the symbolic initial conditions,
1348 it follows the edges in the parent loop. The inner loop is
1349 considered as a single statement. */
1352 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1353 gimple loop_phi_node
,
1355 tree
*evolution_of_loop
, int limit
)
1357 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1358 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1360 /* Sometimes, the inner loop is too difficult to analyze, and the
1361 result of the analysis is a symbolic parameter. */
1362 if (ev
== PHI_RESULT (loop_phi_node
))
1364 t_bool res
= t_false
;
1365 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1367 for (i
= 0; i
< n
; i
++)
1369 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1372 /* Follow the edges that exit the inner loop. */
1373 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1374 if (!flow_bb_inside_loop_p (loop
, bb
))
1375 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1377 evolution_of_loop
, limit
);
1382 /* If the path crosses this loop-phi, give up. */
1384 *evolution_of_loop
= chrec_dont_know
;
1389 /* Otherwise, compute the overall effect of the inner loop. */
1390 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1391 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1392 evolution_of_loop
, limit
);
1395 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1396 path that is analyzed on the return walk. */
1399 follow_ssa_edge (struct loop
*loop
, gimple def
, gimple halting_phi
,
1400 tree
*evolution_of_loop
, int limit
)
1402 struct loop
*def_loop
;
1404 if (gimple_nop_p (def
))
1407 /* Give up if the path is longer than the MAX that we allow. */
1408 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1411 def_loop
= loop_containing_stmt (def
);
1413 switch (gimple_code (def
))
1416 if (!loop_phi_node_p (def
))
1417 /* DEF is a condition-phi-node. Follow the branches, and
1418 record their evolutions. Finally, merge the collected
1419 information and set the approximation to the main
1421 return follow_ssa_edge_in_condition_phi
1422 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1424 /* When the analyzed phi is the halting_phi, the
1425 depth-first search is over: we have found a path from
1426 the halting_phi to itself in the loop. */
1427 if (def
== halting_phi
)
1430 /* Otherwise, the evolution of the HALTING_PHI depends
1431 on the evolution of another loop-phi-node, i.e. the
1432 evolution function is a higher degree polynomial. */
1433 if (def_loop
== loop
)
1437 if (flow_loop_nested_p (loop
, def_loop
))
1438 return follow_ssa_edge_inner_loop_phi
1439 (loop
, def
, halting_phi
, evolution_of_loop
, limit
+ 1);
1445 return follow_ssa_edge_in_rhs (loop
, def
, halting_phi
,
1446 evolution_of_loop
, limit
);
1449 /* At this level of abstraction, the program is just a set
1450 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1451 other node to be handled. */
1458 /* Given a LOOP_PHI_NODE, this function determines the evolution
1459 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1462 analyze_evolution_in_loop (gimple loop_phi_node
,
1465 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1466 tree evolution_function
= chrec_not_analyzed_yet
;
1467 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1472 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1473 fprintf (dump_file
, " (loop_phi_node = ");
1474 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1475 fprintf (dump_file
, ")\n");
1478 for (i
= 0; i
< n
; i
++)
1480 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1485 /* Select the edges that enter the loop body. */
1486 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1487 if (!flow_bb_inside_loop_p (loop
, bb
))
1490 if (TREE_CODE (arg
) == SSA_NAME
)
1492 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1494 /* Pass in the initial condition to the follow edge function. */
1496 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1501 /* When it is impossible to go back on the same
1502 loop_phi_node by following the ssa edges, the
1503 evolution is represented by a peeled chrec, i.e. the
1504 first iteration, EV_FN has the value INIT_COND, then
1505 all the other iterations it has the value of ARG.
1506 For the moment, PEELED_CHREC nodes are not built. */
1508 ev_fn
= chrec_dont_know
;
1510 /* When there are multiple back edges of the loop (which in fact never
1511 happens currently, but nevertheless), merge their evolutions. */
1512 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1517 fprintf (dump_file
, " (evolution_function = ");
1518 print_generic_expr (dump_file
, evolution_function
, 0);
1519 fprintf (dump_file
, "))\n");
1522 return evolution_function
;
1525 /* Given a loop-phi-node, return the initial conditions of the
1526 variable on entry of the loop. When the CCP has propagated
1527 constants into the loop-phi-node, the initial condition is
1528 instantiated, otherwise the initial condition is kept symbolic.
1529 This analyzer does not analyze the evolution outside the current
1530 loop, and leaves this task to the on-demand tree reconstructor. */
1533 analyze_initial_condition (gimple loop_phi_node
)
1536 tree init_cond
= chrec_not_analyzed_yet
;
1537 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1541 fprintf (dump_file
, "(analyze_initial_condition \n");
1542 fprintf (dump_file
, " (loop_phi_node = \n");
1543 print_gimple_stmt (dump_file
, loop_phi_node
, 0, 0);
1544 fprintf (dump_file
, ")\n");
1547 n
= gimple_phi_num_args (loop_phi_node
);
1548 for (i
= 0; i
< n
; i
++)
1550 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1551 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1553 /* When the branch is oriented to the loop's body, it does
1554 not contribute to the initial condition. */
1555 if (flow_bb_inside_loop_p (loop
, bb
))
1558 if (init_cond
== chrec_not_analyzed_yet
)
1564 if (TREE_CODE (branch
) == SSA_NAME
)
1566 init_cond
= chrec_dont_know
;
1570 init_cond
= chrec_merge (init_cond
, branch
);
1573 /* Ooops -- a loop without an entry??? */
1574 if (init_cond
== chrec_not_analyzed_yet
)
1575 init_cond
= chrec_dont_know
;
1577 /* During early loop unrolling we do not have fully constant propagated IL.
1578 Handle degenerate PHIs here to not miss important unrollings. */
1579 if (TREE_CODE (init_cond
) == SSA_NAME
)
1581 gimple def
= SSA_NAME_DEF_STMT (init_cond
);
1583 if (gimple_code (def
) == GIMPLE_PHI
1584 && (res
= degenerate_phi_result (def
)) != NULL_TREE
1585 /* Only allow invariants here, otherwise we may break
1586 loop-closed SSA form. */
1587 && is_gimple_min_invariant (res
))
1591 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1593 fprintf (dump_file
, " (init_cond = ");
1594 print_generic_expr (dump_file
, init_cond
, 0);
1595 fprintf (dump_file
, "))\n");
1601 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1604 interpret_loop_phi (struct loop
*loop
, gimple loop_phi_node
)
1607 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1610 if (phi_loop
!= loop
)
1612 struct loop
*subloop
;
1613 tree evolution_fn
= analyze_scalar_evolution
1614 (phi_loop
, PHI_RESULT (loop_phi_node
));
1616 /* Dive one level deeper. */
1617 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1619 /* Interpret the subloop. */
1620 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1624 /* Otherwise really interpret the loop phi. */
1625 init_cond
= analyze_initial_condition (loop_phi_node
);
1626 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1631 /* This function merges the branches of a condition-phi-node,
1632 contained in the outermost loop, and whose arguments are already
1636 interpret_condition_phi (struct loop
*loop
, gimple condition_phi
)
1638 int i
, n
= gimple_phi_num_args (condition_phi
);
1639 tree res
= chrec_not_analyzed_yet
;
1641 for (i
= 0; i
< n
; i
++)
1645 if (backedge_phi_arg_p (condition_phi
, i
))
1647 res
= chrec_dont_know
;
1651 branch_chrec
= analyze_scalar_evolution
1652 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1654 res
= chrec_merge (res
, branch_chrec
);
1660 /* Interpret the operation RHS1 OP RHS2. If we didn't
1661 analyze this node before, follow the definitions until ending
1662 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1663 return path, this function propagates evolutions (ala constant copy
1664 propagation). OPND1 is not a GIMPLE expression because we could
1665 analyze the effect of an inner loop: see interpret_loop_phi. */
1668 interpret_rhs_expr (struct loop
*loop
, gimple at_stmt
,
1669 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1671 tree res
, chrec1
, chrec2
;
1673 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1675 if (is_gimple_min_invariant (rhs1
))
1676 return chrec_convert (type
, rhs1
, at_stmt
);
1678 if (code
== SSA_NAME
)
1679 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1682 if (code
== ASSERT_EXPR
)
1684 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1685 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1689 return chrec_dont_know
;
1694 case POINTER_PLUS_EXPR
:
1695 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1696 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1697 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1698 chrec2
= chrec_convert (sizetype
, chrec2
, at_stmt
);
1699 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1703 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1704 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1705 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1706 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1707 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1711 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1712 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1713 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1714 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1715 res
= chrec_fold_minus (type
, chrec1
, chrec2
);
1719 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1720 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1721 /* TYPE may be integer, real or complex, so use fold_convert. */
1722 res
= chrec_fold_multiply (type
, chrec1
,
1723 fold_convert (type
, integer_minus_one_node
));
1727 /* Handle ~X as -1 - X. */
1728 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1729 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1730 res
= chrec_fold_minus (type
,
1731 fold_convert (type
, integer_minus_one_node
),
1736 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1737 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1738 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1739 chrec2
= chrec_convert (type
, chrec2
, at_stmt
);
1740 res
= chrec_fold_multiply (type
, chrec1
, chrec2
);
1744 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1745 res
= chrec_convert (type
, chrec1
, at_stmt
);
1749 res
= chrec_dont_know
;
1756 /* Interpret the expression EXPR. */
1759 interpret_expr (struct loop
*loop
, gimple at_stmt
, tree expr
)
1761 enum tree_code code
;
1762 tree type
= TREE_TYPE (expr
), op0
, op1
;
1764 if (automatically_generated_chrec_p (expr
))
1767 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
)
1768 return chrec_dont_know
;
1770 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1772 return interpret_rhs_expr (loop
, at_stmt
, type
,
1776 /* Interpret the rhs of the assignment STMT. */
1779 interpret_gimple_assign (struct loop
*loop
, gimple stmt
)
1781 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1782 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1784 return interpret_rhs_expr (loop
, stmt
, type
,
1785 gimple_assign_rhs1 (stmt
), code
,
1786 gimple_assign_rhs2 (stmt
));
1791 /* This section contains all the entry points:
1792 - number_of_iterations_in_loop,
1793 - analyze_scalar_evolution,
1794 - instantiate_parameters.
1797 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1798 common ancestor of DEF_LOOP and USE_LOOP. */
1801 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1802 struct loop
*def_loop
,
1806 if (def_loop
== wrto_loop
)
1809 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1810 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1812 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1815 /* Helper recursive function. */
1818 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1820 tree type
= TREE_TYPE (var
);
1823 struct loop
*def_loop
;
1825 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1826 return chrec_dont_know
;
1828 if (TREE_CODE (var
) != SSA_NAME
)
1829 return interpret_expr (loop
, NULL
, var
);
1831 def
= SSA_NAME_DEF_STMT (var
);
1832 bb
= gimple_bb (def
);
1833 def_loop
= bb
? bb
->loop_father
: NULL
;
1836 || !flow_bb_inside_loop_p (loop
, bb
))
1838 /* Keep the symbolic form. */
1843 if (res
!= chrec_not_analyzed_yet
)
1845 if (loop
!= bb
->loop_father
)
1846 res
= compute_scalar_evolution_in_loop
1847 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1852 if (loop
!= def_loop
)
1854 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1855 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1860 switch (gimple_code (def
))
1863 res
= interpret_gimple_assign (loop
, def
);
1867 if (loop_phi_node_p (def
))
1868 res
= interpret_loop_phi (loop
, def
);
1870 res
= interpret_condition_phi (loop
, def
);
1874 res
= chrec_dont_know
;
1880 /* Keep the symbolic form. */
1881 if (res
== chrec_dont_know
)
1884 if (loop
== def_loop
)
1885 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1890 /* Entry point for the scalar evolution analyzer.
1891 Analyzes and returns the scalar evolution of the ssa_name VAR.
1892 LOOP_NB is the identifier number of the loop in which the variable
1895 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1896 pointer to the statement that uses this variable, in order to
1897 determine the evolution function of the variable, use the following
1900 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1901 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1902 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1906 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1912 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1913 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1914 fprintf (dump_file
, " (scalar = ");
1915 print_generic_expr (dump_file
, var
, 0);
1916 fprintf (dump_file
, ")\n");
1919 res
= get_scalar_evolution (block_before_loop (loop
), var
);
1920 res
= analyze_scalar_evolution_1 (loop
, var
, res
);
1922 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1923 fprintf (dump_file
, ")\n");
1928 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1929 WRTO_LOOP (which should be a superloop of USE_LOOP)
1931 FOLDED_CASTS is set to true if resolve_mixers used
1932 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1933 at the moment in order to keep things simple).
1935 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1938 for (i = 0; i < 100; i++) -- loop 1
1940 for (j = 0; j < 100; j++) -- loop 2
1947 for (t = 0; t < 100; t++) -- loop 3
1954 Both k1 and k2 are invariants in loop3, thus
1955 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1956 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1958 As they are invariant, it does not matter whether we consider their
1959 usage in loop 3 or loop 2, hence
1960 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1961 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1962 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1963 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1965 Similarly for their evolutions with respect to loop 1. The values of K2
1966 in the use in loop 2 vary independently on loop 1, thus we cannot express
1967 the evolution with respect to loop 1:
1968 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
1969 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
1970 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
1971 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
1973 The value of k2 in the use in loop 1 is known, though:
1974 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
1975 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
1979 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
1980 tree version
, bool *folded_casts
)
1983 tree ev
= version
, tmp
;
1985 /* We cannot just do
1987 tmp = analyze_scalar_evolution (use_loop, version);
1988 ev = resolve_mixers (wrto_loop, tmp);
1990 as resolve_mixers would query the scalar evolution with respect to
1991 wrto_loop. For example, in the situation described in the function
1992 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
1995 analyze_scalar_evolution (use_loop, version) = k2
1997 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
1998 is 100, which is a wrong result, since we are interested in the
2001 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2002 each time checking that there is no evolution in the inner loop. */
2005 *folded_casts
= false;
2008 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2009 ev
= resolve_mixers (use_loop
, tmp
);
2011 if (folded_casts
&& tmp
!= ev
)
2012 *folded_casts
= true;
2014 if (use_loop
== wrto_loop
)
2017 /* If the value of the use changes in the inner loop, we cannot express
2018 its value in the outer loop (we might try to return interval chrec,
2019 but we do not have a user for it anyway) */
2020 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2022 return chrec_dont_know
;
2024 use_loop
= loop_outer (use_loop
);
2028 /* Returns from CACHE the value for VERSION instantiated below
2029 INSTANTIATED_BELOW block. */
2032 get_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2035 struct scev_info_str
*info
, pattern
;
2037 pattern
.var
= version
;
2038 pattern
.instantiated_below
= instantiated_below
;
2039 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2047 /* Sets in CACHE the value of VERSION instantiated below basic block
2048 INSTANTIATED_BELOW to VAL. */
2051 set_instantiated_value (htab_t cache
, basic_block instantiated_below
,
2052 tree version
, tree val
)
2054 struct scev_info_str
*info
, pattern
;
2057 pattern
.var
= version
;
2058 pattern
.instantiated_below
= instantiated_below
;
2059 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2062 *slot
= new_scev_info_str (instantiated_below
, version
);
2063 info
= (struct scev_info_str
*) *slot
;
2067 /* Return the closed_loop_phi node for VAR. If there is none, return
2071 loop_closed_phi_def (tree var
)
2076 gimple_stmt_iterator psi
;
2078 if (var
== NULL_TREE
2079 || TREE_CODE (var
) != SSA_NAME
)
2082 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2083 exit
= single_exit (loop
);
2087 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2089 phi
= gsi_stmt (psi
);
2090 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2091 return PHI_RESULT (phi
);
2097 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2098 and EVOLUTION_LOOP, that were left under a symbolic form.
2100 CHREC is the scalar evolution to instantiate.
2102 CACHE is the cache of already instantiated values.
2104 FOLD_CONVERSIONS should be set to true when the conversions that
2105 may wrap in signed/pointer type are folded, as long as the value of
2106 the chrec is preserved.
2108 SIZE_EXPR is used for computing the size of the expression to be
2109 instantiated, and to stop if it exceeds some limit. */
2112 instantiate_scev_1 (basic_block instantiate_below
,
2113 struct loop
*evolution_loop
, tree chrec
,
2114 bool fold_conversions
, htab_t cache
, int size_expr
)
2116 tree res
, op0
, op1
, op2
;
2118 struct loop
*def_loop
;
2119 tree type
= chrec_type (chrec
);
2121 /* Give up if the expression is larger than the MAX that we allow. */
2122 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2123 return chrec_dont_know
;
2125 if (automatically_generated_chrec_p (chrec
)
2126 || is_gimple_min_invariant (chrec
))
2129 switch (TREE_CODE (chrec
))
2132 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2134 /* A parameter (or loop invariant and we do not want to include
2135 evolutions in outer loops), nothing to do. */
2137 || loop_depth (def_bb
->loop_father
) == 0
2138 || dominated_by_p (CDI_DOMINATORS
, instantiate_below
, def_bb
))
2141 /* We cache the value of instantiated variable to avoid exponential
2142 time complexity due to reevaluations. We also store the convenient
2143 value in the cache in order to prevent infinite recursion -- we do
2144 not want to instantiate the SSA_NAME if it is in a mixer
2145 structure. This is used for avoiding the instantiation of
2146 recursively defined functions, such as:
2148 | a_2 -> {0, +, 1, +, a_2}_1 */
2150 res
= get_instantiated_value (cache
, instantiate_below
, chrec
);
2154 res
= chrec_dont_know
;
2155 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2157 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2159 /* If the analysis yields a parametric chrec, instantiate the
2161 res
= analyze_scalar_evolution (def_loop
, chrec
);
2163 /* Don't instantiate loop-closed-ssa phi nodes. */
2164 if (TREE_CODE (res
) == SSA_NAME
2165 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2166 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2167 > loop_depth (def_loop
))))
2170 res
= loop_closed_phi_def (chrec
);
2174 if (res
== NULL_TREE
)
2175 res
= chrec_dont_know
;
2178 else if (res
!= chrec_dont_know
)
2179 res
= instantiate_scev_1 (instantiate_below
, evolution_loop
, res
,
2180 fold_conversions
, cache
, size_expr
);
2182 /* Store the correct value to the cache. */
2183 set_instantiated_value (cache
, instantiate_below
, chrec
, res
);
2186 case POLYNOMIAL_CHREC
:
2187 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2188 CHREC_LEFT (chrec
), fold_conversions
, cache
,
2190 if (op0
== chrec_dont_know
)
2191 return chrec_dont_know
;
2193 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2194 CHREC_RIGHT (chrec
), fold_conversions
, cache
,
2196 if (op1
== chrec_dont_know
)
2197 return chrec_dont_know
;
2199 if (CHREC_LEFT (chrec
) != op0
2200 || CHREC_RIGHT (chrec
) != op1
)
2202 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2203 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2207 case POINTER_PLUS_EXPR
:
2209 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2210 TREE_OPERAND (chrec
, 0), fold_conversions
, cache
,
2212 if (op0
== chrec_dont_know
)
2213 return chrec_dont_know
;
2215 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2216 TREE_OPERAND (chrec
, 1), fold_conversions
, cache
,
2218 if (op1
== chrec_dont_know
)
2219 return chrec_dont_know
;
2221 if (TREE_OPERAND (chrec
, 0) != op0
2222 || TREE_OPERAND (chrec
, 1) != op1
)
2224 op0
= chrec_convert (type
, op0
, NULL
);
2225 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2226 chrec
= chrec_fold_plus (type
, op0
, op1
);
2231 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2232 TREE_OPERAND (chrec
, 0), fold_conversions
, cache
,
2234 if (op0
== chrec_dont_know
)
2235 return chrec_dont_know
;
2237 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2238 TREE_OPERAND (chrec
, 1),
2239 fold_conversions
, cache
, size_expr
);
2240 if (op1
== chrec_dont_know
)
2241 return chrec_dont_know
;
2243 if (TREE_OPERAND (chrec
, 0) != op0
2244 || TREE_OPERAND (chrec
, 1) != op1
)
2246 op0
= chrec_convert (type
, op0
, NULL
);
2247 op1
= chrec_convert (type
, op1
, NULL
);
2248 chrec
= chrec_fold_minus (type
, op0
, op1
);
2253 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2254 TREE_OPERAND (chrec
, 0),
2255 fold_conversions
, cache
, size_expr
);
2256 if (op0
== chrec_dont_know
)
2257 return chrec_dont_know
;
2259 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2260 TREE_OPERAND (chrec
, 1),
2261 fold_conversions
, cache
, size_expr
);
2262 if (op1
== chrec_dont_know
)
2263 return chrec_dont_know
;
2265 if (TREE_OPERAND (chrec
, 0) != op0
2266 || TREE_OPERAND (chrec
, 1) != op1
)
2268 op0
= chrec_convert (type
, op0
, NULL
);
2269 op1
= chrec_convert (type
, op1
, NULL
);
2270 chrec
= chrec_fold_multiply (type
, op0
, op1
);
2275 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2276 TREE_OPERAND (chrec
, 0),
2277 fold_conversions
, cache
, size_expr
);
2278 if (op0
== chrec_dont_know
)
2279 return chrec_dont_know
;
2281 if (fold_conversions
)
2283 tree tmp
= chrec_convert_aggressive (TREE_TYPE (chrec
), op0
);
2288 if (op0
== TREE_OPERAND (chrec
, 0))
2291 /* If we used chrec_convert_aggressive, we can no longer assume that
2292 signed chrecs do not overflow, as chrec_convert does, so avoid
2293 calling it in that case. */
2294 if (fold_conversions
)
2295 return fold_convert (TREE_TYPE (chrec
), op0
);
2297 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL
);
2300 /* Handle ~X as -1 - X. */
2301 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2302 TREE_OPERAND (chrec
, 0),
2303 fold_conversions
, cache
, size_expr
);
2304 if (op0
== chrec_dont_know
)
2305 return chrec_dont_know
;
2307 if (TREE_OPERAND (chrec
, 0) != op0
)
2309 op0
= chrec_convert (type
, op0
, NULL
);
2310 chrec
= chrec_fold_minus (type
,
2312 integer_minus_one_node
),
2317 case SCEV_NOT_KNOWN
:
2318 return chrec_dont_know
;
2327 if (VL_EXP_CLASS_P (chrec
))
2328 return chrec_dont_know
;
2330 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2333 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2334 TREE_OPERAND (chrec
, 0),
2335 fold_conversions
, cache
, size_expr
);
2336 if (op0
== chrec_dont_know
)
2337 return chrec_dont_know
;
2339 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2340 TREE_OPERAND (chrec
, 1),
2341 fold_conversions
, cache
, size_expr
);
2342 if (op1
== chrec_dont_know
)
2343 return chrec_dont_know
;
2345 op2
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2346 TREE_OPERAND (chrec
, 2),
2347 fold_conversions
, cache
, size_expr
);
2348 if (op2
== chrec_dont_know
)
2349 return chrec_dont_know
;
2351 if (op0
== TREE_OPERAND (chrec
, 0)
2352 && op1
== TREE_OPERAND (chrec
, 1)
2353 && op2
== TREE_OPERAND (chrec
, 2))
2356 return fold_build3 (TREE_CODE (chrec
),
2357 TREE_TYPE (chrec
), op0
, op1
, op2
);
2360 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2361 TREE_OPERAND (chrec
, 0),
2362 fold_conversions
, cache
, size_expr
);
2363 if (op0
== chrec_dont_know
)
2364 return chrec_dont_know
;
2366 op1
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2367 TREE_OPERAND (chrec
, 1),
2368 fold_conversions
, cache
, size_expr
);
2369 if (op1
== chrec_dont_know
)
2370 return chrec_dont_know
;
2372 if (op0
== TREE_OPERAND (chrec
, 0)
2373 && op1
== TREE_OPERAND (chrec
, 1))
2375 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2378 op0
= instantiate_scev_1 (instantiate_below
, evolution_loop
,
2379 TREE_OPERAND (chrec
, 0),
2380 fold_conversions
, cache
, size_expr
);
2381 if (op0
== chrec_dont_know
)
2382 return chrec_dont_know
;
2383 if (op0
== TREE_OPERAND (chrec
, 0))
2385 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2394 /* Too complicated to handle. */
2395 return chrec_dont_know
;
2398 /* Analyze all the parameters of the chrec that were left under a
2399 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2400 recursive instantiation of parameters: a parameter is a variable
2401 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2402 a function parameter. */
2405 instantiate_scev (basic_block instantiate_below
, struct loop
*evolution_loop
,
2409 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2413 fprintf (dump_file
, "(instantiate_scev \n");
2414 fprintf (dump_file
, " (instantiate_below = %d)\n", instantiate_below
->index
);
2415 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2416 fprintf (dump_file
, " (chrec = ");
2417 print_generic_expr (dump_file
, chrec
, 0);
2418 fprintf (dump_file
, ")\n");
2421 res
= instantiate_scev_1 (instantiate_below
, evolution_loop
, chrec
, false,
2424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2426 fprintf (dump_file
, " (res = ");
2427 print_generic_expr (dump_file
, res
, 0);
2428 fprintf (dump_file
, "))\n");
2431 htab_delete (cache
);
2436 /* Similar to instantiate_parameters, but does not introduce the
2437 evolutions in outer loops for LOOP invariants in CHREC, and does not
2438 care about causing overflows, as long as they do not affect value
2439 of an expression. */
2442 resolve_mixers (struct loop
*loop
, tree chrec
)
2444 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2445 tree ret
= instantiate_scev_1 (block_before_loop (loop
), loop
, chrec
, true,
2447 htab_delete (cache
);
2451 /* Entry point for the analysis of the number of iterations pass.
2452 This function tries to safely approximate the number of iterations
2453 the loop will run. When this property is not decidable at compile
2454 time, the result is chrec_dont_know. Otherwise the result is
2455 a scalar or a symbolic parameter.
2457 Example of analysis: suppose that the loop has an exit condition:
2459 "if (b > 49) goto end_loop;"
2461 and that in a previous analysis we have determined that the
2462 variable 'b' has an evolution function:
2464 "EF = {23, +, 5}_2".
2466 When we evaluate the function at the point 5, i.e. the value of the
2467 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2468 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2469 the loop body has been executed 6 times. */
2472 number_of_latch_executions (struct loop
*loop
)
2476 struct tree_niter_desc niter_desc
;
2478 /* Determine whether the number_of_iterations_in_loop has already
2480 res
= loop
->nb_iterations
;
2483 res
= chrec_dont_know
;
2485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2486 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2488 exit
= single_exit (loop
);
2492 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2495 type
= TREE_TYPE (niter_desc
.niter
);
2496 if (integer_nonzerop (niter_desc
.may_be_zero
))
2497 res
= build_int_cst (type
, 0);
2498 else if (integer_zerop (niter_desc
.may_be_zero
))
2499 res
= niter_desc
.niter
;
2501 res
= chrec_dont_know
;
2504 return set_nb_iterations_in_loop (loop
, res
);
2507 /* Returns the number of executions of the exit condition of LOOP,
2508 i.e., the number by one higher than number_of_latch_executions.
2509 Note that unlike number_of_latch_executions, this number does
2510 not necessarily fit in the unsigned variant of the type of
2511 the control variable -- if the number of iterations is a constant,
2512 we return chrec_dont_know if adding one to number_of_latch_executions
2513 overflows; however, in case the number of iterations is symbolic
2514 expression, the caller is responsible for dealing with this
2515 the possible overflow. */
2518 number_of_exit_cond_executions (struct loop
*loop
)
2520 tree ret
= number_of_latch_executions (loop
);
2521 tree type
= chrec_type (ret
);
2523 if (chrec_contains_undetermined (ret
))
2526 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2527 if (TREE_CODE (ret
) == INTEGER_CST
2528 && TREE_OVERFLOW (ret
))
2529 return chrec_dont_know
;
2534 /* One of the drivers for testing the scalar evolutions analysis.
2535 This function computes the number of iterations for all the loops
2536 from the EXIT_CONDITIONS array. */
2539 number_of_iterations_for_all_loops (VEC(gimple
,heap
) **exit_conditions
)
2542 unsigned nb_chrec_dont_know_loops
= 0;
2543 unsigned nb_static_loops
= 0;
2546 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2548 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2549 if (chrec_contains_undetermined (res
))
2550 nb_chrec_dont_know_loops
++;
2557 fprintf (dump_file
, "\n(\n");
2558 fprintf (dump_file
, "-----------------------------------------\n");
2559 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2560 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2561 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2562 fprintf (dump_file
, "-----------------------------------------\n");
2563 fprintf (dump_file
, ")\n\n");
2565 print_loops (dump_file
, 3);
2571 /* Counters for the stats. */
2577 unsigned nb_affine_multivar
;
2578 unsigned nb_higher_poly
;
2579 unsigned nb_chrec_dont_know
;
2580 unsigned nb_undetermined
;
2583 /* Reset the counters. */
2586 reset_chrecs_counters (struct chrec_stats
*stats
)
2588 stats
->nb_chrecs
= 0;
2589 stats
->nb_affine
= 0;
2590 stats
->nb_affine_multivar
= 0;
2591 stats
->nb_higher_poly
= 0;
2592 stats
->nb_chrec_dont_know
= 0;
2593 stats
->nb_undetermined
= 0;
2596 /* Dump the contents of a CHREC_STATS structure. */
2599 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2601 fprintf (file
, "\n(\n");
2602 fprintf (file
, "-----------------------------------------\n");
2603 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2604 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2605 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2606 stats
->nb_higher_poly
);
2607 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2608 fprintf (file
, "-----------------------------------------\n");
2609 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2610 fprintf (file
, "%d\twith undetermined coefficients\n",
2611 stats
->nb_undetermined
);
2612 fprintf (file
, "-----------------------------------------\n");
2613 fprintf (file
, "%d\tchrecs in the scev database\n",
2614 (int) htab_elements (scalar_evolution_info
));
2615 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2616 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2617 fprintf (file
, "-----------------------------------------\n");
2618 fprintf (file
, ")\n\n");
2621 /* Gather statistics about CHREC. */
2624 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2626 if (dump_file
&& (dump_flags
& TDF_STATS
))
2628 fprintf (dump_file
, "(classify_chrec ");
2629 print_generic_expr (dump_file
, chrec
, 0);
2630 fprintf (dump_file
, "\n");
2635 if (chrec
== NULL_TREE
)
2637 stats
->nb_undetermined
++;
2641 switch (TREE_CODE (chrec
))
2643 case POLYNOMIAL_CHREC
:
2644 if (evolution_function_is_affine_p (chrec
))
2646 if (dump_file
&& (dump_flags
& TDF_STATS
))
2647 fprintf (dump_file
, " affine_univariate\n");
2650 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2652 if (dump_file
&& (dump_flags
& TDF_STATS
))
2653 fprintf (dump_file
, " affine_multivariate\n");
2654 stats
->nb_affine_multivar
++;
2658 if (dump_file
&& (dump_flags
& TDF_STATS
))
2659 fprintf (dump_file
, " higher_degree_polynomial\n");
2660 stats
->nb_higher_poly
++;
2669 if (chrec_contains_undetermined (chrec
))
2671 if (dump_file
&& (dump_flags
& TDF_STATS
))
2672 fprintf (dump_file
, " undetermined\n");
2673 stats
->nb_undetermined
++;
2676 if (dump_file
&& (dump_flags
& TDF_STATS
))
2677 fprintf (dump_file
, ")\n");
2680 /* One of the drivers for testing the scalar evolutions analysis.
2681 This function analyzes the scalar evolution of all the scalars
2682 defined as loop phi nodes in one of the loops from the
2683 EXIT_CONDITIONS array.
2685 TODO Optimization: A loop is in canonical form if it contains only
2686 a single scalar loop phi node. All the other scalars that have an
2687 evolution in the loop are rewritten in function of this single
2688 index. This allows the parallelization of the loop. */
2691 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple
,heap
) **exit_conditions
)
2694 struct chrec_stats stats
;
2696 gimple_stmt_iterator psi
;
2698 reset_chrecs_counters (&stats
);
2700 for (i
= 0; VEC_iterate (gimple
, *exit_conditions
, i
, cond
); i
++)
2706 loop
= loop_containing_stmt (cond
);
2709 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2711 phi
= gsi_stmt (psi
);
2712 if (is_gimple_reg (PHI_RESULT (phi
)))
2714 chrec
= instantiate_parameters
2716 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2718 if (dump_file
&& (dump_flags
& TDF_STATS
))
2719 gather_chrec_stats (chrec
, &stats
);
2724 if (dump_file
&& (dump_flags
& TDF_STATS
))
2725 dump_chrecs_stats (dump_file
, &stats
);
2728 /* Callback for htab_traverse, gathers information on chrecs in the
2732 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2734 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2736 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2741 /* Classify the chrecs of the whole database. */
2744 gather_stats_on_scev_database (void)
2746 struct chrec_stats stats
;
2751 reset_chrecs_counters (&stats
);
2753 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2756 dump_chrecs_stats (dump_file
, &stats
);
2764 initialize_scalar_evolutions_analyzer (void)
2766 /* The elements below are unique. */
2767 if (chrec_dont_know
== NULL_TREE
)
2769 chrec_not_analyzed_yet
= NULL_TREE
;
2770 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2771 chrec_known
= make_node (SCEV_KNOWN
);
2772 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2773 TREE_TYPE (chrec_known
) = void_type_node
;
2777 /* Initialize the analysis of scalar evolutions for LOOPS. */
2780 scev_initialize (void)
2785 scalar_evolution_info
= htab_create_alloc (100,
2792 initialize_scalar_evolutions_analyzer ();
2794 FOR_EACH_LOOP (li
, loop
, 0)
2796 loop
->nb_iterations
= NULL_TREE
;
2800 /* Cleans up the information cached by the scalar evolutions analysis. */
2808 if (!scalar_evolution_info
|| !current_loops
)
2811 htab_empty (scalar_evolution_info
);
2812 FOR_EACH_LOOP (li
, loop
, 0)
2814 loop
->nb_iterations
= NULL_TREE
;
2818 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
2819 respect to WRTO_LOOP and returns its base and step in IV if possible
2820 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
2821 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
2822 invariant in LOOP. Otherwise we require it to be an integer constant.
2824 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
2825 because it is computed in signed arithmetics). Consequently, adding an
2828 for (i = IV->base; ; i += IV->step)
2830 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
2831 false for the type of the induction variable, or you can prove that i does
2832 not wrap by some other argument. Otherwise, this might introduce undefined
2835 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
2837 must be used instead. */
2840 simple_iv (struct loop
*wrto_loop
, struct loop
*use_loop
, tree op
,
2841 affine_iv
*iv
, bool allow_nonconstant_step
)
2846 iv
->base
= NULL_TREE
;
2847 iv
->step
= NULL_TREE
;
2848 iv
->no_overflow
= false;
2850 type
= TREE_TYPE (op
);
2851 if (TREE_CODE (type
) != INTEGER_TYPE
2852 && TREE_CODE (type
) != POINTER_TYPE
)
2855 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
2857 if (chrec_contains_undetermined (ev
)
2858 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
2861 if (tree_does_not_contain_chrecs (ev
))
2864 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
2865 iv
->no_overflow
= true;
2869 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2870 || CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
2873 iv
->step
= CHREC_RIGHT (ev
);
2874 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
2875 || tree_contains_chrecs (iv
->step
, NULL
))
2878 iv
->base
= CHREC_LEFT (ev
);
2879 if (tree_contains_chrecs (iv
->base
, NULL
))
2882 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
2887 /* Runs the analysis of scalar evolutions. */
2890 scev_analysis (void)
2892 VEC(gimple
,heap
) *exit_conditions
;
2894 exit_conditions
= VEC_alloc (gimple
, heap
, 37);
2895 select_loops_exit_conditions (&exit_conditions
);
2897 if (dump_file
&& (dump_flags
& TDF_STATS
))
2898 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2900 number_of_iterations_for_all_loops (&exit_conditions
);
2901 VEC_free (gimple
, heap
, exit_conditions
);
2904 /* Finalize the scalar evolution analysis. */
2907 scev_finalize (void)
2909 if (!scalar_evolution_info
)
2911 htab_delete (scalar_evolution_info
);
2912 scalar_evolution_info
= NULL
;
2915 /* Returns true if the expression EXPR is considered to be too expensive
2916 for scev_const_prop. */
2919 expression_expensive_p (tree expr
)
2921 enum tree_code code
;
2923 if (is_gimple_val (expr
))
2926 code
= TREE_CODE (expr
);
2927 if (code
== TRUNC_DIV_EXPR
2928 || code
== CEIL_DIV_EXPR
2929 || code
== FLOOR_DIV_EXPR
2930 || code
== ROUND_DIV_EXPR
2931 || code
== TRUNC_MOD_EXPR
2932 || code
== CEIL_MOD_EXPR
2933 || code
== FLOOR_MOD_EXPR
2934 || code
== ROUND_MOD_EXPR
2935 || code
== EXACT_DIV_EXPR
)
2937 /* Division by power of two is usually cheap, so we allow it.
2938 Forbid anything else. */
2939 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
2943 switch (TREE_CODE_CLASS (code
))
2946 case tcc_comparison
:
2947 if (expression_expensive_p (TREE_OPERAND (expr
, 1)))
2952 return expression_expensive_p (TREE_OPERAND (expr
, 0));
2959 /* Replace ssa names for that scev can prove they are constant by the
2960 appropriate constants. Also perform final value replacement in loops,
2961 in case the replacement expressions are cheap.
2963 We only consider SSA names defined by phi nodes; rest is left to the
2964 ordinary constant propagation pass. */
2967 scev_const_prop (void)
2970 tree name
, type
, ev
;
2972 struct loop
*loop
, *ex_loop
;
2973 bitmap ssa_names_to_remove
= NULL
;
2976 gimple_stmt_iterator psi
;
2978 if (number_of_loops () <= 1)
2983 loop
= bb
->loop_father
;
2985 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2987 phi
= gsi_stmt (psi
);
2988 name
= PHI_RESULT (phi
);
2990 if (!is_gimple_reg (name
))
2993 type
= TREE_TYPE (name
);
2995 if (!POINTER_TYPE_P (type
)
2996 && !INTEGRAL_TYPE_P (type
))
2999 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
3000 if (!is_gimple_min_invariant (ev
)
3001 || !may_propagate_copy (name
, ev
))
3004 /* Replace the uses of the name. */
3006 replace_uses_by (name
, ev
);
3008 if (!ssa_names_to_remove
)
3009 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
3010 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
3014 /* Remove the ssa names that were replaced by constants. We do not
3015 remove them directly in the previous cycle, since this
3016 invalidates scev cache. */
3017 if (ssa_names_to_remove
)
3021 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
3023 gimple_stmt_iterator psi
;
3024 name
= ssa_name (i
);
3025 phi
= SSA_NAME_DEF_STMT (name
);
3027 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3028 psi
= gsi_for_stmt (phi
);
3029 remove_phi_node (&psi
, true);
3032 BITMAP_FREE (ssa_names_to_remove
);
3036 /* Now the regular final value replacement. */
3037 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
3040 tree def
, rslt
, niter
;
3041 gimple_stmt_iterator bsi
;
3043 /* If we do not know exact number of iterations of the loop, we cannot
3044 replace the final value. */
3045 exit
= single_exit (loop
);
3049 niter
= number_of_latch_executions (loop
);
3050 if (niter
== chrec_dont_know
)
3053 /* Ensure that it is possible to insert new statements somewhere. */
3054 if (!single_pred_p (exit
->dest
))
3055 split_loop_exit_edge (exit
);
3056 bsi
= gsi_after_labels (exit
->dest
);
3058 ex_loop
= superloop_at_depth (loop
,
3059 loop_depth (exit
->dest
->loop_father
) + 1);
3061 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3063 phi
= gsi_stmt (psi
);
3064 rslt
= PHI_RESULT (phi
);
3065 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3066 if (!is_gimple_reg (def
))
3072 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3073 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3079 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
3080 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3081 if (!tree_does_not_contain_chrecs (def
)
3082 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3083 /* Moving the computation from the loop may prolong life range
3084 of some ssa names, which may cause problems if they appear
3085 on abnormal edges. */
3086 || contains_abnormal_ssa_name_p (def
)
3087 /* Do not emit expensive expressions. The rationale is that
3088 when someone writes a code like
3090 while (n > 45) n -= 45;
3092 he probably knows that n is not large, and does not want it
3093 to be turned into n %= 45. */
3094 || expression_expensive_p (def
))
3100 /* Eliminate the PHI node and replace it by a computation outside
3102 def
= unshare_expr (def
);
3103 remove_phi_node (&psi
, false);
3105 def
= force_gimple_operand_gsi (&bsi
, def
, false, NULL_TREE
,
3106 true, GSI_SAME_STMT
);
3107 ass
= gimple_build_assign (rslt
, def
);
3108 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
3114 #include "gt-tree-scalar-evolution.h"