1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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_MODIFY_STMT: 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 ({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 2: 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 3: Higher degree polynomials.
172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175 Example 4: Lucas, Fibonacci, or mixers in general.
187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188 following semantics: during the first iteration of the loop_1, the
189 variable contains the value 1, and then it contains the value "c".
190 Note that this syntax is close to the syntax of the loop-phi-node:
191 "a -> (1, c)_1" vs. "a = phi (1, c)".
193 The symbolic chrec representation contains all the semantics of the
194 original code. What is more difficult is to use this information.
196 Example 5: Flip-flops, or exchangers.
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
214 This transformation is not yet implemented.
218 You can find a more detailed description of the algorithm in:
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
221 this is a preliminary report and some of the details of the
222 algorithm have changed. I'm working on a research report that
223 updates the description of the algorithms to reflect the design
224 choices used in this implementation.
226 A set of slides show a high level overview of the algorithm and run
227 an example through the scalar evolution analyzer:
228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230 The slides that I have presented at the GCC Summit'04 are available
231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
236 #include "coretypes.h"
242 /* These RTL headers are needed for basic-block.h. */
244 #include "basic-block.h"
245 #include "diagnostic.h"
246 #include "tree-flow.h"
247 #include "tree-dump.h"
250 #include "tree-chrec.h"
251 #include "tree-scalar-evolution.h"
252 #include "tree-pass.h"
256 static tree
analyze_scalar_evolution_1 (struct loop
*, tree
, tree
);
258 /* The cached information about a ssa name VAR, claiming that inside LOOP,
259 the value of VAR can be expressed as CHREC. */
261 struct scev_info_str
GTY(())
267 /* Counters for the scev database. */
268 static unsigned nb_set_scev
= 0;
269 static unsigned nb_get_scev
= 0;
271 /* The following trees are unique elements. Thus the comparison of
272 another element to these elements should be done on the pointer to
273 these trees, and not on their value. */
275 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
276 tree chrec_not_analyzed_yet
;
278 /* Reserved to the cases where the analyzer has detected an
279 undecidable property at compile time. */
280 tree chrec_dont_know
;
282 /* When the analyzer has detected that a property will never
283 happen, then it qualifies it with chrec_known. */
286 static bitmap already_instantiated
;
288 static GTY ((param_is (struct scev_info_str
))) htab_t scalar_evolution_info
;
291 /* Constructs a new SCEV_INFO_STR structure. */
293 static inline struct scev_info_str
*
294 new_scev_info_str (tree var
)
296 struct scev_info_str
*res
;
298 res
= GGC_NEW (struct scev_info_str
);
300 res
->chrec
= chrec_not_analyzed_yet
;
305 /* Computes a hash function for database element ELT. */
308 hash_scev_info (const void *elt
)
310 return SSA_NAME_VERSION (((struct scev_info_str
*) elt
)->var
);
313 /* Compares database elements E1 and E2. */
316 eq_scev_info (const void *e1
, const void *e2
)
318 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
319 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
321 return elt1
->var
== elt2
->var
;
324 /* Deletes database element E. */
327 del_scev_info (void *e
)
332 /* Get the index corresponding to VAR in the current LOOP. If
333 it's the first time we ask for this VAR, then we return
334 chrec_not_analyzed_yet for this VAR and return its index. */
337 find_var_scev_info (tree var
)
339 struct scev_info_str
*res
;
340 struct scev_info_str tmp
;
344 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
347 *slot
= new_scev_info_str (var
);
348 res
= (struct scev_info_str
*) *slot
;
353 /* Return true when CHREC contains symbolic names defined in
357 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
361 if (chrec
== NULL_TREE
)
364 if (TREE_INVARIANT (chrec
))
367 if (TREE_CODE (chrec
) == VAR_DECL
368 || TREE_CODE (chrec
) == PARM_DECL
369 || TREE_CODE (chrec
) == FUNCTION_DECL
370 || TREE_CODE (chrec
) == LABEL_DECL
371 || TREE_CODE (chrec
) == RESULT_DECL
372 || TREE_CODE (chrec
) == FIELD_DECL
)
375 if (TREE_CODE (chrec
) == SSA_NAME
)
377 tree def
= SSA_NAME_DEF_STMT (chrec
);
378 struct loop
*def_loop
= loop_containing_stmt (def
);
379 struct loop
*loop
= get_loop (loop_nb
);
381 if (def_loop
== NULL
)
384 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
390 n
= TREE_OPERAND_LENGTH (chrec
);
391 for (i
= 0; i
< n
; i
++)
392 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
398 /* Return true when PHI is a loop-phi-node. */
401 loop_phi_node_p (tree phi
)
403 /* The implementation of this function is based on the following
404 property: "all the loop-phi-nodes of a loop are contained in the
405 loop's header basic block". */
407 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
410 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
411 In general, in the case of multivariate evolutions we want to get
412 the evolution in different loops. LOOP specifies the level for
413 which to get the evolution.
417 | for (j = 0; j < 100; j++)
419 | for (k = 0; k < 100; k++)
421 | i = k + j; - Here the value of i is a function of j, k.
423 | ... = i - Here the value of i is a function of j.
425 | ... = i - Here the value of i is a scalar.
431 | i_1 = phi (i_0, i_2)
435 This loop has the same effect as:
436 LOOP_1 has the same effect as:
440 The overall effect of the loop, "i_0 + 20" in the previous example,
441 is obtained by passing in the parameters: LOOP = 1,
442 EVOLUTION_FN = {i_0, +, 2}_1.
446 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
450 if (evolution_fn
== chrec_dont_know
)
451 return chrec_dont_know
;
453 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
455 struct loop
*inner_loop
= get_chrec_loop (evolution_fn
);
457 if (inner_loop
== loop
458 || flow_loop_nested_p (loop
, inner_loop
))
460 tree nb_iter
= number_of_latch_executions (inner_loop
);
462 if (nb_iter
== chrec_dont_know
)
463 return chrec_dont_know
;
468 /* evolution_fn is the evolution function in LOOP. Get
469 its value in the nb_iter-th iteration. */
470 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
472 /* Continue the computation until ending on a parent of LOOP. */
473 return compute_overall_effect_of_inner_loop (loop
, res
);
480 /* If the evolution function is an invariant, there is nothing to do. */
481 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
485 return chrec_dont_know
;
488 /* Determine whether the CHREC is always positive/negative. If the expression
489 cannot be statically analyzed, return false, otherwise set the answer into
493 chrec_is_positive (tree chrec
, bool *value
)
495 bool value0
, value1
, value2
;
496 tree end_value
, nb_iter
;
498 switch (TREE_CODE (chrec
))
500 case POLYNOMIAL_CHREC
:
501 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
502 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
505 /* FIXME -- overflows. */
506 if (value0
== value1
)
512 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
513 and the proof consists in showing that the sign never
514 changes during the execution of the loop, from 0 to
515 loop->nb_iterations. */
516 if (!evolution_function_is_affine_p (chrec
))
519 nb_iter
= number_of_latch_executions (get_chrec_loop (chrec
));
520 if (chrec_contains_undetermined (nb_iter
))
524 /* TODO -- If the test is after the exit, we may decrease the number of
525 iterations by one. */
527 nb_iter
= chrec_fold_minus (type
, nb_iter
, build_int_cst (type
, 1));
530 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
532 if (!chrec_is_positive (end_value
, &value2
))
536 return value0
== value1
;
539 *value
= (tree_int_cst_sgn (chrec
) == 1);
547 /* Associate CHREC to SCALAR. */
550 set_scalar_evolution (tree scalar
, tree chrec
)
554 if (TREE_CODE (scalar
) != SSA_NAME
)
557 scalar_info
= find_var_scev_info (scalar
);
561 if (dump_flags
& TDF_DETAILS
)
563 fprintf (dump_file
, "(set_scalar_evolution \n");
564 fprintf (dump_file
, " (scalar = ");
565 print_generic_expr (dump_file
, scalar
, 0);
566 fprintf (dump_file
, ")\n (scalar_evolution = ");
567 print_generic_expr (dump_file
, chrec
, 0);
568 fprintf (dump_file
, "))\n");
570 if (dump_flags
& TDF_STATS
)
574 *scalar_info
= chrec
;
577 /* Retrieve the chrec associated to SCALAR in the LOOP. */
580 get_scalar_evolution (tree scalar
)
586 if (dump_flags
& TDF_DETAILS
)
588 fprintf (dump_file
, "(get_scalar_evolution \n");
589 fprintf (dump_file
, " (scalar = ");
590 print_generic_expr (dump_file
, scalar
, 0);
591 fprintf (dump_file
, ")\n");
593 if (dump_flags
& TDF_STATS
)
597 switch (TREE_CODE (scalar
))
600 res
= *find_var_scev_info (scalar
);
609 res
= chrec_not_analyzed_yet
;
613 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
615 fprintf (dump_file
, " (scalar_evolution = ");
616 print_generic_expr (dump_file
, res
, 0);
617 fprintf (dump_file
, "))\n");
623 /* Helper function for add_to_evolution. Returns the evolution
624 function for an assignment of the form "a = b + c", where "a" and
625 "b" are on the strongly connected component. CHREC_BEFORE is the
626 information that we already have collected up to this point.
627 TO_ADD is the evolution of "c".
629 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
630 evolution the expression TO_ADD, otherwise construct an evolution
631 part for this loop. */
634 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
637 tree type
, left
, right
;
638 struct loop
*loop
= get_loop (loop_nb
), *chloop
;
640 switch (TREE_CODE (chrec_before
))
642 case POLYNOMIAL_CHREC
:
643 chloop
= get_chrec_loop (chrec_before
);
645 || flow_loop_nested_p (chloop
, loop
))
649 type
= chrec_type (chrec_before
);
651 /* When there is no evolution part in this loop, build it. */
656 right
= SCALAR_FLOAT_TYPE_P (type
)
657 ? build_real (type
, dconst0
)
658 : build_int_cst (type
, 0);
662 var
= CHREC_VARIABLE (chrec_before
);
663 left
= CHREC_LEFT (chrec_before
);
664 right
= CHREC_RIGHT (chrec_before
);
667 to_add
= chrec_convert (type
, to_add
, at_stmt
);
668 right
= chrec_convert (type
, right
, at_stmt
);
669 right
= chrec_fold_plus (type
, right
, to_add
);
670 return build_polynomial_chrec (var
, left
, right
);
674 gcc_assert (flow_loop_nested_p (loop
, chloop
));
676 /* Search the evolution in LOOP_NB. */
677 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
679 right
= CHREC_RIGHT (chrec_before
);
680 right
= chrec_convert (chrec_type (left
), right
, at_stmt
);
681 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
686 /* These nodes do not depend on a loop. */
687 if (chrec_before
== chrec_dont_know
)
688 return chrec_dont_know
;
691 right
= chrec_convert (chrec_type (left
), to_add
, at_stmt
);
692 return build_polynomial_chrec (loop_nb
, left
, right
);
696 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
699 Description (provided for completeness, for those who read code in
700 a plane, and for my poor 62 bytes brain that would have forgotten
701 all this in the next two or three months):
703 The algorithm of translation of programs from the SSA representation
704 into the chrecs syntax is based on a pattern matching. After having
705 reconstructed the overall tree expression for a loop, there are only
706 two cases that can arise:
708 1. a = loop-phi (init, a + expr)
709 2. a = loop-phi (init, expr)
711 where EXPR is either a scalar constant with respect to the analyzed
712 loop (this is a degree 0 polynomial), or an expression containing
713 other loop-phi definitions (these are higher degree polynomials).
720 | a = phi (init, a + 5)
727 | a = phi (inita, 2 * b + 3)
728 | b = phi (initb, b + 1)
731 For the first case, the semantics of the SSA representation is:
733 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
735 that is, there is a loop index "x" that determines the scalar value
736 of the variable during the loop execution. During the first
737 iteration, the value is that of the initial condition INIT, while
738 during the subsequent iterations, it is the sum of the initial
739 condition with the sum of all the values of EXPR from the initial
740 iteration to the before last considered iteration.
742 For the second case, the semantics of the SSA program is:
744 | a (x) = init, if x = 0;
745 | expr (x - 1), otherwise.
747 The second case corresponds to the PEELED_CHREC, whose syntax is
748 close to the syntax of a loop-phi-node:
750 | phi (init, expr) vs. (init, expr)_x
752 The proof of the translation algorithm for the first case is a
753 proof by structural induction based on the degree of EXPR.
756 When EXPR is a constant with respect to the analyzed loop, or in
757 other words when EXPR is a polynomial of degree 0, the evolution of
758 the variable A in the loop is an affine function with an initial
759 condition INIT, and a step EXPR. In order to show this, we start
760 from the semantics of the SSA representation:
762 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
764 and since "expr (j)" is a constant with respect to "j",
766 f (x) = init + x * expr
768 Finally, based on the semantics of the pure sum chrecs, by
769 identification we get the corresponding chrecs syntax:
771 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
772 f (x) -> {init, +, expr}_x
775 Suppose that EXPR is a polynomial of degree N with respect to the
776 analyzed loop_x for which we have already determined that it is
777 written under the chrecs syntax:
779 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
781 We start from the semantics of the SSA program:
783 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
785 | f (x) = init + \sum_{j = 0}^{x - 1}
786 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
788 | f (x) = init + \sum_{j = 0}^{x - 1}
789 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
791 | f (x) = init + \sum_{k = 0}^{n - 1}
792 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
794 | f (x) = init + \sum_{k = 0}^{n - 1}
795 | (b_k * \binom{x}{k + 1})
797 | f (x) = init + b_0 * \binom{x}{1} + ...
798 | + b_{n-1} * \binom{x}{n}
800 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
801 | + b_{n-1} * \binom{x}{n}
804 And finally from the definition of the chrecs syntax, we identify:
805 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
807 This shows the mechanism that stands behind the add_to_evolution
808 function. An important point is that the use of symbolic
809 parameters avoids the need of an analysis schedule.
816 | a = phi (inita, a + 2 + b)
817 | b = phi (initb, b + 1)
820 When analyzing "a", the algorithm keeps "b" symbolically:
822 | a -> {inita, +, 2 + b}_1
824 Then, after instantiation, the analyzer ends on the evolution:
826 | a -> {inita, +, 2 + initb, +, 1}_1
831 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
832 tree to_add
, tree at_stmt
)
834 tree type
= chrec_type (to_add
);
835 tree res
= NULL_TREE
;
837 if (to_add
== NULL_TREE
)
840 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
841 instantiated at this point. */
842 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
843 /* This should not happen. */
844 return chrec_dont_know
;
846 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
848 fprintf (dump_file
, "(add_to_evolution \n");
849 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
850 fprintf (dump_file
, " (chrec_before = ");
851 print_generic_expr (dump_file
, chrec_before
, 0);
852 fprintf (dump_file
, ")\n (to_add = ");
853 print_generic_expr (dump_file
, to_add
, 0);
854 fprintf (dump_file
, ")\n");
857 if (code
== MINUS_EXPR
)
858 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
859 ? build_real (type
, dconstm1
)
860 : build_int_cst_type (type
, -1));
862 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
866 fprintf (dump_file
, " (res = ");
867 print_generic_expr (dump_file
, res
, 0);
868 fprintf (dump_file
, "))\n");
874 /* Helper function. */
877 set_nb_iterations_in_loop (struct loop
*loop
,
880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
882 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
883 print_generic_expr (dump_file
, res
, 0);
884 fprintf (dump_file
, "))\n");
887 loop
->nb_iterations
= res
;
893 /* This section selects the loops that will be good candidates for the
894 scalar evolution analysis. For the moment, greedily select all the
895 loop nests we could analyze. */
897 /* Return true when it is possible to analyze the condition expression
901 analyzable_condition (tree expr
)
905 if (TREE_CODE (expr
) != COND_EXPR
)
908 condition
= TREE_OPERAND (expr
, 0);
910 switch (TREE_CODE (condition
))
930 /* For a loop with a single exit edge, return the COND_EXPR that
931 guards the exit edge. If the expression is too difficult to
932 analyze, then give up. */
935 get_loop_exit_condition (struct loop
*loop
)
937 tree res
= NULL_TREE
;
938 edge exit_edge
= single_exit (loop
);
940 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
941 fprintf (dump_file
, "(get_loop_exit_condition \n ");
947 expr
= last_stmt (exit_edge
->src
);
948 if (analyzable_condition (expr
))
952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
954 print_generic_expr (dump_file
, res
, 0);
955 fprintf (dump_file
, ")\n");
961 /* Recursively determine and enqueue the exit conditions for a loop. */
964 get_exit_conditions_rec (struct loop
*loop
,
965 VEC(tree
,heap
) **exit_conditions
)
970 /* Recurse on the inner loops, then on the next (sibling) loops. */
971 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
972 get_exit_conditions_rec (loop
->next
, exit_conditions
);
974 if (single_exit (loop
))
976 tree loop_condition
= get_loop_exit_condition (loop
);
979 VEC_safe_push (tree
, heap
, *exit_conditions
, loop_condition
);
983 /* Select the candidate loop nests for the analysis. This function
984 initializes the EXIT_CONDITIONS array. */
987 select_loops_exit_conditions (VEC(tree
,heap
) **exit_conditions
)
989 struct loop
*function_body
= current_loops
->tree_root
;
991 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
995 /* Depth first search algorithm. */
997 typedef enum t_bool
{
1004 static t_bool
follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*, int);
1006 /* Follow the ssa edge into the right hand side RHS of an assignment.
1007 Return true if the strongly connected component has been found. */
1010 follow_ssa_edge_in_rhs (struct loop
*loop
, tree at_stmt
, tree rhs
,
1011 tree halting_phi
, tree
*evolution_of_loop
, int limit
)
1013 t_bool res
= t_false
;
1015 tree type_rhs
= TREE_TYPE (rhs
);
1018 /* The RHS is one of the following cases:
1024 - other cases are not yet handled. */
1025 switch (TREE_CODE (rhs
))
1028 /* This assignment is under the form "a_1 = (cast) rhs. */
1029 res
= follow_ssa_edge_in_rhs (loop
, at_stmt
, TREE_OPERAND (rhs
, 0),
1030 halting_phi
, evolution_of_loop
, limit
);
1031 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
),
1032 *evolution_of_loop
, at_stmt
);
1036 /* This assignment is under the form "a_1 = 7". */
1041 /* This assignment is under the form: "a_1 = b_2". */
1042 res
= follow_ssa_edge
1043 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
, limit
);
1047 /* This case is under the form "rhs0 + rhs1". */
1048 rhs0
= TREE_OPERAND (rhs
, 0);
1049 rhs1
= TREE_OPERAND (rhs
, 1);
1050 STRIP_TYPE_NOPS (rhs0
);
1051 STRIP_TYPE_NOPS (rhs1
);
1053 if (TREE_CODE (rhs0
) == SSA_NAME
)
1055 if (TREE_CODE (rhs1
) == SSA_NAME
)
1057 /* Match an assignment under the form:
1059 evol
= *evolution_of_loop
;
1060 res
= follow_ssa_edge
1061 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1065 *evolution_of_loop
= add_to_evolution
1067 chrec_convert (type_rhs
, evol
, at_stmt
),
1068 PLUS_EXPR
, rhs1
, at_stmt
);
1070 else if (res
== t_false
)
1072 res
= follow_ssa_edge
1073 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1074 evolution_of_loop
, limit
);
1077 *evolution_of_loop
= add_to_evolution
1079 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1080 PLUS_EXPR
, rhs0
, at_stmt
);
1082 else if (res
== t_dont_know
)
1083 *evolution_of_loop
= chrec_dont_know
;
1086 else if (res
== t_dont_know
)
1087 *evolution_of_loop
= chrec_dont_know
;
1092 /* Match an assignment under the form:
1094 res
= follow_ssa_edge
1095 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1096 evolution_of_loop
, limit
);
1098 *evolution_of_loop
= add_to_evolution
1099 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1101 PLUS_EXPR
, rhs1
, at_stmt
);
1103 else if (res
== t_dont_know
)
1104 *evolution_of_loop
= chrec_dont_know
;
1108 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1110 /* Match an assignment under the form:
1112 res
= follow_ssa_edge
1113 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1114 evolution_of_loop
, limit
);
1116 *evolution_of_loop
= add_to_evolution
1117 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1119 PLUS_EXPR
, rhs0
, at_stmt
);
1121 else if (res
== t_dont_know
)
1122 *evolution_of_loop
= chrec_dont_know
;
1126 /* Otherwise, match an assignment under the form:
1128 /* And there is nothing to do. */
1134 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1135 rhs0
= TREE_OPERAND (rhs
, 0);
1136 rhs1
= TREE_OPERAND (rhs
, 1);
1137 STRIP_TYPE_NOPS (rhs0
);
1138 STRIP_TYPE_NOPS (rhs1
);
1140 if (TREE_CODE (rhs0
) == SSA_NAME
)
1142 /* Match an assignment under the form:
1144 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1145 evolution_of_loop
, limit
);
1147 *evolution_of_loop
= add_to_evolution
1148 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1149 MINUS_EXPR
, rhs1
, at_stmt
);
1151 else if (res
== t_dont_know
)
1152 *evolution_of_loop
= chrec_dont_know
;
1155 /* Otherwise, match an assignment under the form:
1157 /* And there is nothing to do. */
1164 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1165 It must be handled as a copy assignment of the form a_1 = a_2. */
1166 tree op0
= ASSERT_EXPR_VAR (rhs
);
1167 if (TREE_CODE (op0
) == SSA_NAME
)
1168 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1169 halting_phi
, evolution_of_loop
, limit
);
1184 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1187 backedge_phi_arg_p (tree phi
, int i
)
1189 edge e
= PHI_ARG_EDGE (phi
, i
);
1191 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1192 about updating it anywhere, and this should work as well most of the
1194 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1200 /* Helper function for one branch of the condition-phi-node. Return
1201 true if the strongly connected component has been found following
1204 static inline t_bool
1205 follow_ssa_edge_in_condition_phi_branch (int i
,
1209 tree
*evolution_of_branch
,
1210 tree init_cond
, int limit
)
1212 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1213 *evolution_of_branch
= chrec_dont_know
;
1215 /* Do not follow back edges (they must belong to an irreducible loop, which
1216 we really do not want to worry about). */
1217 if (backedge_phi_arg_p (condition_phi
, i
))
1220 if (TREE_CODE (branch
) == SSA_NAME
)
1222 *evolution_of_branch
= init_cond
;
1223 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1224 evolution_of_branch
, limit
);
1227 /* This case occurs when one of the condition branches sets
1228 the variable to a constant: i.e. a phi-node like
1229 "a_2 = PHI <a_7(5), 2(6)>;".
1231 FIXME: This case have to be refined correctly:
1232 in some cases it is possible to say something better than
1233 chrec_dont_know, for example using a wrap-around notation. */
1237 /* This function merges the branches of a condition-phi-node in a
1241 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1244 tree
*evolution_of_loop
, int limit
)
1247 tree init
= *evolution_of_loop
;
1248 tree evolution_of_branch
;
1249 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1251 &evolution_of_branch
,
1253 if (res
== t_false
|| res
== t_dont_know
)
1256 *evolution_of_loop
= evolution_of_branch
;
1258 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1260 /* Quickly give up when the evolution of one of the branches is
1262 if (*evolution_of_loop
== chrec_dont_know
)
1265 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1267 &evolution_of_branch
,
1269 if (res
== t_false
|| res
== t_dont_know
)
1272 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1273 evolution_of_branch
);
1279 /* Follow an SSA edge in an inner loop. It computes the overall
1280 effect of the loop, and following the symbolic initial conditions,
1281 it follows the edges in the parent loop. The inner loop is
1282 considered as a single statement. */
1285 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1288 tree
*evolution_of_loop
, int limit
)
1290 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1291 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1293 /* Sometimes, the inner loop is too difficult to analyze, and the
1294 result of the analysis is a symbolic parameter. */
1295 if (ev
== PHI_RESULT (loop_phi_node
))
1297 t_bool res
= t_false
;
1300 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1302 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1305 /* Follow the edges that exit the inner loop. */
1306 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1307 if (!flow_bb_inside_loop_p (loop
, bb
))
1308 res
= follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
,
1310 evolution_of_loop
, limit
);
1315 /* If the path crosses this loop-phi, give up. */
1317 *evolution_of_loop
= chrec_dont_know
;
1322 /* Otherwise, compute the overall effect of the inner loop. */
1323 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1324 return follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1325 evolution_of_loop
, limit
);
1328 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1329 path that is analyzed on the return walk. */
1332 follow_ssa_edge (struct loop
*loop
, tree def
, tree halting_phi
,
1333 tree
*evolution_of_loop
, int limit
)
1335 struct loop
*def_loop
;
1337 if (TREE_CODE (def
) == NOP_EXPR
)
1340 /* Give up if the path is longer than the MAX that we allow. */
1341 if (limit
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1344 def_loop
= loop_containing_stmt (def
);
1346 switch (TREE_CODE (def
))
1349 if (!loop_phi_node_p (def
))
1350 /* DEF is a condition-phi-node. Follow the branches, and
1351 record their evolutions. Finally, merge the collected
1352 information and set the approximation to the main
1354 return follow_ssa_edge_in_condition_phi
1355 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1357 /* When the analyzed phi is the halting_phi, the
1358 depth-first search is over: we have found a path from
1359 the halting_phi to itself in the loop. */
1360 if (def
== halting_phi
)
1363 /* Otherwise, the evolution of the HALTING_PHI depends
1364 on the evolution of another loop-phi-node, i.e. the
1365 evolution function is a higher degree polynomial. */
1366 if (def_loop
== loop
)
1370 if (flow_loop_nested_p (loop
, def_loop
))
1371 return follow_ssa_edge_inner_loop_phi
1372 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1377 case GIMPLE_MODIFY_STMT
:
1378 return follow_ssa_edge_in_rhs (loop
, def
,
1379 GIMPLE_STMT_OPERAND (def
, 1),
1381 evolution_of_loop
, limit
);
1384 /* At this level of abstraction, the program is just a set
1385 of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
1386 other node to be handled. */
1393 /* Given a LOOP_PHI_NODE, this function determines the evolution
1394 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1397 analyze_evolution_in_loop (tree loop_phi_node
,
1401 tree evolution_function
= chrec_not_analyzed_yet
;
1402 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1405 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1407 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1408 fprintf (dump_file
, " (loop_phi_node = ");
1409 print_generic_expr (dump_file
, loop_phi_node
, 0);
1410 fprintf (dump_file
, ")\n");
1413 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1415 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1416 tree ssa_chain
, ev_fn
;
1419 /* Select the edges that enter the loop body. */
1420 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1421 if (!flow_bb_inside_loop_p (loop
, bb
))
1424 if (TREE_CODE (arg
) == SSA_NAME
)
1426 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1428 /* Pass in the initial condition to the follow edge function. */
1430 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1435 /* When it is impossible to go back on the same
1436 loop_phi_node by following the ssa edges, the
1437 evolution is represented by a peeled chrec, i.e. the
1438 first iteration, EV_FN has the value INIT_COND, then
1439 all the other iterations it has the value of ARG.
1440 For the moment, PEELED_CHREC nodes are not built. */
1442 ev_fn
= chrec_dont_know
;
1444 /* When there are multiple back edges of the loop (which in fact never
1445 happens currently, but nevertheless), merge their evolutions. */
1446 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1451 fprintf (dump_file
, " (evolution_function = ");
1452 print_generic_expr (dump_file
, evolution_function
, 0);
1453 fprintf (dump_file
, "))\n");
1456 return evolution_function
;
1459 /* Given a loop-phi-node, return the initial conditions of the
1460 variable on entry of the loop. When the CCP has propagated
1461 constants into the loop-phi-node, the initial condition is
1462 instantiated, otherwise the initial condition is kept symbolic.
1463 This analyzer does not analyze the evolution outside the current
1464 loop, and leaves this task to the on-demand tree reconstructor. */
1467 analyze_initial_condition (tree loop_phi_node
)
1470 tree init_cond
= chrec_not_analyzed_yet
;
1471 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1475 fprintf (dump_file
, "(analyze_initial_condition \n");
1476 fprintf (dump_file
, " (loop_phi_node = \n");
1477 print_generic_expr (dump_file
, loop_phi_node
, 0);
1478 fprintf (dump_file
, ")\n");
1481 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1483 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1484 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1486 /* When the branch is oriented to the loop's body, it does
1487 not contribute to the initial condition. */
1488 if (flow_bb_inside_loop_p (loop
, bb
))
1491 if (init_cond
== chrec_not_analyzed_yet
)
1497 if (TREE_CODE (branch
) == SSA_NAME
)
1499 init_cond
= chrec_dont_know
;
1503 init_cond
= chrec_merge (init_cond
, branch
);
1506 /* Ooops -- a loop without an entry??? */
1507 if (init_cond
== chrec_not_analyzed_yet
)
1508 init_cond
= chrec_dont_know
;
1510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1512 fprintf (dump_file
, " (init_cond = ");
1513 print_generic_expr (dump_file
, init_cond
, 0);
1514 fprintf (dump_file
, "))\n");
1520 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1523 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1526 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1529 if (phi_loop
!= loop
)
1531 struct loop
*subloop
;
1532 tree evolution_fn
= analyze_scalar_evolution
1533 (phi_loop
, PHI_RESULT (loop_phi_node
));
1535 /* Dive one level deeper. */
1536 subloop
= superloop_at_depth (phi_loop
, loop_depth (loop
) + 1);
1538 /* Interpret the subloop. */
1539 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1543 /* Otherwise really interpret the loop phi. */
1544 init_cond
= analyze_initial_condition (loop_phi_node
);
1545 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1550 /* This function merges the branches of a condition-phi-node,
1551 contained in the outermost loop, and whose arguments are already
1555 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1558 tree res
= chrec_not_analyzed_yet
;
1560 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1564 if (backedge_phi_arg_p (condition_phi
, i
))
1566 res
= chrec_dont_know
;
1570 branch_chrec
= analyze_scalar_evolution
1571 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1573 res
= chrec_merge (res
, branch_chrec
);
1579 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
1580 analyze this node before, follow the definitions until ending
1581 either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
1582 return path, this function propagates evolutions (ala constant copy
1583 propagation). OPND1 is not a GIMPLE expression because we could
1584 analyze the effect of an inner loop: see interpret_loop_phi. */
1587 interpret_rhs_modify_stmt (struct loop
*loop
, tree at_stmt
,
1588 tree opnd1
, tree type
)
1590 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1592 if (is_gimple_min_invariant (opnd1
))
1593 return chrec_convert (type
, opnd1
, at_stmt
);
1595 switch (TREE_CODE (opnd1
))
1598 opnd10
= TREE_OPERAND (opnd1
, 0);
1599 opnd11
= TREE_OPERAND (opnd1
, 1);
1600 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1601 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1602 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1603 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1604 res
= chrec_fold_plus (type
, chrec10
, chrec11
);
1608 opnd10
= TREE_OPERAND (opnd1
, 0);
1609 opnd11
= TREE_OPERAND (opnd1
, 1);
1610 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1611 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1612 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1613 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1614 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1618 opnd10
= TREE_OPERAND (opnd1
, 0);
1619 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1620 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1621 /* TYPE may be integer, real or complex, so use fold_convert. */
1622 res
= chrec_fold_multiply (type
, chrec10
,
1623 fold_convert (type
, integer_minus_one_node
));
1627 opnd10
= TREE_OPERAND (opnd1
, 0);
1628 opnd11
= TREE_OPERAND (opnd1
, 1);
1629 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1630 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1631 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1632 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1633 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1637 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
),
1642 opnd10
= ASSERT_EXPR_VAR (opnd1
);
1643 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd10
),
1649 opnd10
= TREE_OPERAND (opnd1
, 0);
1650 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1651 res
= chrec_convert (type
, chrec10
, at_stmt
);
1655 res
= chrec_dont_know
;
1664 /* This section contains all the entry points:
1665 - number_of_iterations_in_loop,
1666 - analyze_scalar_evolution,
1667 - instantiate_parameters.
1670 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1671 common ancestor of DEF_LOOP and USE_LOOP. */
1674 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1675 struct loop
*def_loop
,
1679 if (def_loop
== wrto_loop
)
1682 def_loop
= superloop_at_depth (def_loop
, loop_depth (wrto_loop
) + 1);
1683 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1685 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1688 /* Folds EXPR, if it is a cast to pointer, assuming that the created
1689 polynomial_chrec does not wrap. */
1692 fold_used_pointer_cast (tree expr
)
1695 tree type
, inner_type
;
1697 if (TREE_CODE (expr
) != NOP_EXPR
&& TREE_CODE (expr
) != CONVERT_EXPR
)
1700 op
= TREE_OPERAND (expr
, 0);
1701 if (TREE_CODE (op
) != POLYNOMIAL_CHREC
)
1704 type
= TREE_TYPE (expr
);
1705 inner_type
= TREE_TYPE (op
);
1707 if (!INTEGRAL_TYPE_P (inner_type
)
1708 || TYPE_PRECISION (inner_type
) != TYPE_PRECISION (type
))
1711 return build_polynomial_chrec (CHREC_VARIABLE (op
),
1712 chrec_convert (type
, CHREC_LEFT (op
), NULL_TREE
),
1713 chrec_convert (type
, CHREC_RIGHT (op
), NULL_TREE
));
1716 /* Returns true if EXPR is an expression corresponding to offset of pointer
1720 pointer_offset_p (tree expr
)
1722 if (TREE_CODE (expr
) == INTEGER_CST
)
1725 if ((TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1726 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0))))
1732 /* EXPR is a scalar evolution of a pointer that is dereferenced or used in
1733 comparison. This means that it must point to a part of some object in
1734 memory, which enables us to argue about overflows and possibly simplify
1735 the EXPR. AT_STMT is the statement in which this conversion has to be
1736 performed. Returns the simplified value.
1743 for (i = -n; i < n; i++)
1746 We generate the following code (assuming that size of int and size_t is
1749 for (i = -n; i < n; i++)
1754 tmp1 = (size_t) i; (1)
1755 tmp2 = 4 * tmp1; (2)
1756 tmp3 = (int *) tmp2; (3)
1757 tmp4 = p + tmp3; (4)
1762 We in general assume that pointer arithmetics does not overflow (since its
1763 behavior is undefined in that case). One of the problems is that our
1764 translation does not capture this property very well -- (int *) is
1765 considered unsigned, hence the computation in (4) does overflow if i is
1768 This impreciseness creates complications in scev analysis. The scalar
1769 evolution of i is [-n, +, 1]. Since int and size_t have the same precision
1770 (in this example), and size_t is unsigned (so we do not care about
1771 overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
1772 and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into
1773 problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
1774 places assume that this is not the case for scevs with pointer type, we
1775 cannot use this scev for tmp3; hence, its scev is
1776 (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
1777 p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to
1778 work with scevs of this shape.
1780 However, since tmp4 is dereferenced, all its values must belong to a single
1781 object, and taking into account that the precision of int * and size_t is
1782 the same, it is impossible for its scev to wrap. Hence, we can derive that
1783 its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
1786 ??? Maybe we should use different representation for pointer arithmetics,
1787 however that is a long-term project with a lot of potential for creating
1791 fold_used_pointer (tree expr
, tree at_stmt
)
1793 tree op0
, op1
, new0
, new1
;
1794 enum tree_code code
= TREE_CODE (expr
);
1796 if (code
== PLUS_EXPR
1797 || code
== MINUS_EXPR
)
1799 op0
= TREE_OPERAND (expr
, 0);
1800 op1
= TREE_OPERAND (expr
, 1);
1802 if (pointer_offset_p (op1
))
1804 new0
= fold_used_pointer (op0
, at_stmt
);
1805 new1
= fold_used_pointer_cast (op1
);
1807 else if (code
== PLUS_EXPR
&& pointer_offset_p (op0
))
1809 new0
= fold_used_pointer_cast (op0
);
1810 new1
= fold_used_pointer (op1
, at_stmt
);
1815 if (new0
== op0
&& new1
== op1
)
1818 new0
= chrec_convert (TREE_TYPE (expr
), new0
, at_stmt
);
1819 new1
= chrec_convert (TREE_TYPE (expr
), new1
, at_stmt
);
1821 if (code
== PLUS_EXPR
)
1822 expr
= chrec_fold_plus (TREE_TYPE (expr
), new0
, new1
);
1824 expr
= chrec_fold_minus (TREE_TYPE (expr
), new0
, new1
);
1829 return fold_used_pointer_cast (expr
);
1832 /* Returns true if PTR is dereferenced, or used in comparison. */
1835 pointer_used_p (tree ptr
)
1837 use_operand_p use_p
;
1838 imm_use_iterator imm_iter
;
1840 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
1842 /* Check whether the pointer has a memory tag; if it does, it is
1843 (or at least used to be) dereferenced. */
1844 if ((pi
!= NULL
&& pi
->name_mem_tag
!= NULL
)
1845 || symbol_mem_tag (SSA_NAME_VAR (ptr
)))
1848 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, ptr
)
1850 stmt
= USE_STMT (use_p
);
1851 if (TREE_CODE (stmt
) == COND_EXPR
)
1854 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1857 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1858 if (!COMPARISON_CLASS_P (rhs
))
1861 if (GIMPLE_STMT_OPERAND (stmt
, 0) == ptr
1862 || GIMPLE_STMT_OPERAND (stmt
, 1) == ptr
)
1869 /* Helper recursive function. */
1872 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1874 tree def
, type
= TREE_TYPE (var
);
1876 struct loop
*def_loop
;
1878 if (loop
== NULL
|| TREE_CODE (type
) == VECTOR_TYPE
)
1879 return chrec_dont_know
;
1881 if (TREE_CODE (var
) != SSA_NAME
)
1882 return interpret_rhs_modify_stmt (loop
, NULL_TREE
, var
, type
);
1884 def
= SSA_NAME_DEF_STMT (var
);
1885 bb
= bb_for_stmt (def
);
1886 def_loop
= bb
? bb
->loop_father
: NULL
;
1889 || !flow_bb_inside_loop_p (loop
, bb
))
1891 /* Keep the symbolic form. */
1896 if (res
!= chrec_not_analyzed_yet
)
1898 if (loop
!= bb
->loop_father
)
1899 res
= compute_scalar_evolution_in_loop
1900 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1905 if (loop
!= def_loop
)
1907 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1908 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1913 switch (TREE_CODE (def
))
1915 case GIMPLE_MODIFY_STMT
:
1916 res
= interpret_rhs_modify_stmt (loop
, def
,
1917 GIMPLE_STMT_OPERAND (def
, 1), type
);
1919 if (POINTER_TYPE_P (type
)
1920 && !automatically_generated_chrec_p (res
)
1921 && pointer_used_p (var
))
1922 res
= fold_used_pointer (res
, def
);
1926 if (loop_phi_node_p (def
))
1927 res
= interpret_loop_phi (loop
, def
);
1929 res
= interpret_condition_phi (loop
, def
);
1933 res
= chrec_dont_know
;
1939 /* Keep the symbolic form. */
1940 if (res
== chrec_dont_know
)
1943 if (loop
== def_loop
)
1944 set_scalar_evolution (var
, res
);
1949 /* Entry point for the scalar evolution analyzer.
1950 Analyzes and returns the scalar evolution of the ssa_name VAR.
1951 LOOP_NB is the identifier number of the loop in which the variable
1954 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1955 pointer to the statement that uses this variable, in order to
1956 determine the evolution function of the variable, use the following
1959 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1960 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1961 tree chrec_instantiated = instantiate_parameters
1962 (loop_nb, chrec_with_symbols);
1966 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1972 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1973 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1974 fprintf (dump_file
, " (scalar = ");
1975 print_generic_expr (dump_file
, var
, 0);
1976 fprintf (dump_file
, ")\n");
1979 res
= analyze_scalar_evolution_1 (loop
, var
, get_scalar_evolution (var
));
1981 if (TREE_CODE (var
) == SSA_NAME
&& res
== chrec_dont_know
)
1984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1985 fprintf (dump_file
, ")\n");
1990 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1991 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1994 FOLDED_CASTS is set to true if resolve_mixers used
1995 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1996 at the moment in order to keep things simple). */
1999 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
2000 tree version
, bool *folded_casts
)
2003 tree ev
= version
, tmp
;
2006 *folded_casts
= false;
2009 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2010 ev
= resolve_mixers (use_loop
, tmp
);
2012 if (folded_casts
&& tmp
!= ev
)
2013 *folded_casts
= true;
2015 if (use_loop
== wrto_loop
)
2018 /* If the value of the use changes in the inner loop, we cannot express
2019 its value in the outer loop (we might try to return interval chrec,
2020 but we do not have a user for it anyway) */
2021 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2023 return chrec_dont_know
;
2025 use_loop
= loop_outer (use_loop
);
2029 /* Returns instantiated value for VERSION in CACHE. */
2032 get_instantiated_value (htab_t cache
, tree version
)
2034 struct scev_info_str
*info
, pattern
;
2036 pattern
.var
= version
;
2037 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
2045 /* Sets instantiated value for VERSION to VAL in CACHE. */
2048 set_instantiated_value (htab_t cache
, tree version
, tree val
)
2050 struct scev_info_str
*info
, pattern
;
2053 pattern
.var
= version
;
2054 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
2057 *slot
= new_scev_info_str (version
);
2058 info
= (struct scev_info_str
*) *slot
;
2062 /* Return the closed_loop_phi node for VAR. If there is none, return
2066 loop_closed_phi_def (tree var
)
2072 if (var
== NULL_TREE
2073 || TREE_CODE (var
) != SSA_NAME
)
2076 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2077 exit
= single_exit (loop
);
2081 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
2082 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2083 return PHI_RESULT (phi
);
2088 /* Analyze all the parameters of the chrec that were left under a symbolic form,
2089 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
2090 of already instantiated values. FLAGS modify the way chrecs are
2091 instantiated. SIZE_EXPR is used for computing the size of the expression to
2092 be instantiated, and to stop if it exceeds some limit. */
2094 /* Values for FLAGS. */
2097 INSERT_SUPERLOOP_CHRECS
= 1, /* Loop invariants are replaced with chrecs
2099 FOLD_CONVERSIONS
= 2 /* The conversions that may wrap in
2100 signed/pointer type are folded, as long as the
2101 value of the chrec is preserved. */
2105 instantiate_parameters_1 (struct loop
*loop
, tree chrec
, int flags
, htab_t cache
,
2108 tree res
, op0
, op1
, op2
;
2110 struct loop
*def_loop
;
2111 tree type
= chrec_type (chrec
);
2113 /* Give up if the expression is larger than the MAX that we allow. */
2114 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2115 return chrec_dont_know
;
2117 if (automatically_generated_chrec_p (chrec
)
2118 || is_gimple_min_invariant (chrec
))
2121 switch (TREE_CODE (chrec
))
2124 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
2126 /* A parameter (or loop invariant and we do not want to include
2127 evolutions in outer loops), nothing to do. */
2129 || (!(flags
& INSERT_SUPERLOOP_CHRECS
)
2130 && !flow_bb_inside_loop_p (loop
, def_bb
)))
2133 /* We cache the value of instantiated variable to avoid exponential
2134 time complexity due to reevaluations. We also store the convenient
2135 value in the cache in order to prevent infinite recursion -- we do
2136 not want to instantiate the SSA_NAME if it is in a mixer
2137 structure. This is used for avoiding the instantiation of
2138 recursively defined functions, such as:
2140 | a_2 -> {0, +, 1, +, a_2}_1 */
2142 res
= get_instantiated_value (cache
, chrec
);
2146 /* Store the convenient value for chrec in the structure. If it
2147 is defined outside of the loop, we may just leave it in symbolic
2148 form, otherwise we need to admit that we do not know its behavior
2150 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
2151 set_instantiated_value (cache
, chrec
, res
);
2153 /* To make things even more complicated, instantiate_parameters_1
2154 calls analyze_scalar_evolution that may call # of iterations
2155 analysis that may in turn call instantiate_parameters_1 again.
2156 To prevent the infinite recursion, keep also the bitmap of
2157 ssa names that are being instantiated globally. */
2158 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
2161 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
2163 /* If the analysis yields a parametric chrec, instantiate the
2165 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2166 res
= analyze_scalar_evolution (def_loop
, chrec
);
2168 /* Don't instantiate loop-closed-ssa phi nodes. */
2169 if (TREE_CODE (res
) == SSA_NAME
2170 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2171 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)))
2172 > loop_depth (def_loop
))))
2175 res
= loop_closed_phi_def (chrec
);
2179 if (res
== NULL_TREE
)
2180 res
= chrec_dont_know
;
2183 else if (res
!= chrec_dont_know
)
2184 res
= instantiate_parameters_1 (loop
, res
, flags
, cache
, size_expr
);
2186 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2188 /* Store the correct value to the cache. */
2189 set_instantiated_value (cache
, chrec
, res
);
2192 case POLYNOMIAL_CHREC
:
2193 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2194 flags
, cache
, size_expr
);
2195 if (op0
== chrec_dont_know
)
2196 return chrec_dont_know
;
2198 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2199 flags
, cache
, size_expr
);
2200 if (op1
== chrec_dont_know
)
2201 return chrec_dont_know
;
2203 if (CHREC_LEFT (chrec
) != op0
2204 || CHREC_RIGHT (chrec
) != op1
)
2206 op1
= chrec_convert (chrec_type (op0
), op1
, NULL_TREE
);
2207 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2212 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2213 flags
, cache
, size_expr
);
2214 if (op0
== chrec_dont_know
)
2215 return chrec_dont_know
;
2217 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2218 flags
, cache
, size_expr
);
2219 if (op1
== chrec_dont_know
)
2220 return chrec_dont_know
;
2222 if (TREE_OPERAND (chrec
, 0) != op0
2223 || TREE_OPERAND (chrec
, 1) != op1
)
2225 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2226 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2227 chrec
= chrec_fold_plus (type
, op0
, op1
);
2232 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2233 flags
, cache
, size_expr
);
2234 if (op0
== chrec_dont_know
)
2235 return chrec_dont_know
;
2237 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2238 flags
, cache
, size_expr
);
2239 if (op1
== chrec_dont_know
)
2240 return chrec_dont_know
;
2242 if (TREE_OPERAND (chrec
, 0) != op0
2243 || TREE_OPERAND (chrec
, 1) != op1
)
2245 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2246 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2247 chrec
= chrec_fold_minus (type
, op0
, op1
);
2252 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2253 flags
, cache
, size_expr
);
2254 if (op0
== chrec_dont_know
)
2255 return chrec_dont_know
;
2257 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2258 flags
, cache
, size_expr
);
2259 if (op1
== chrec_dont_know
)
2260 return chrec_dont_know
;
2262 if (TREE_OPERAND (chrec
, 0) != op0
2263 || TREE_OPERAND (chrec
, 1) != op1
)
2265 op0
= chrec_convert (type
, op0
, NULL_TREE
);
2266 op1
= chrec_convert (type
, op1
, NULL_TREE
);
2267 chrec
= chrec_fold_multiply (type
, op0
, op1
);
2273 case NON_LVALUE_EXPR
:
2274 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2275 flags
, cache
, size_expr
);
2276 if (op0
== chrec_dont_know
)
2277 return chrec_dont_know
;
2279 if (flags
& FOLD_CONVERSIONS
)
2281 tree tmp
= chrec_convert_aggressive (TREE_TYPE (chrec
), op0
);
2286 if (op0
== TREE_OPERAND (chrec
, 0))
2289 /* If we used chrec_convert_aggressive, we can no longer assume that
2290 signed chrecs do not overflow, as chrec_convert does, so avoid
2291 calling it in that case. */
2292 if (flags
& FOLD_CONVERSIONS
)
2293 return fold_convert (TREE_TYPE (chrec
), op0
);
2295 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL_TREE
);
2297 case SCEV_NOT_KNOWN
:
2298 return chrec_dont_know
;
2307 gcc_assert (!VL_EXP_CLASS_P (chrec
));
2308 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2311 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2312 flags
, cache
, size_expr
);
2313 if (op0
== chrec_dont_know
)
2314 return chrec_dont_know
;
2316 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2317 flags
, cache
, size_expr
);
2318 if (op1
== chrec_dont_know
)
2319 return chrec_dont_know
;
2321 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2322 flags
, cache
, size_expr
);
2323 if (op2
== chrec_dont_know
)
2324 return chrec_dont_know
;
2326 if (op0
== TREE_OPERAND (chrec
, 0)
2327 && op1
== TREE_OPERAND (chrec
, 1)
2328 && op2
== TREE_OPERAND (chrec
, 2))
2331 return fold_build3 (TREE_CODE (chrec
),
2332 TREE_TYPE (chrec
), op0
, op1
, op2
);
2335 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2336 flags
, cache
, size_expr
);
2337 if (op0
== chrec_dont_know
)
2338 return chrec_dont_know
;
2340 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2341 flags
, cache
, size_expr
);
2342 if (op1
== chrec_dont_know
)
2343 return chrec_dont_know
;
2345 if (op0
== TREE_OPERAND (chrec
, 0)
2346 && op1
== TREE_OPERAND (chrec
, 1))
2348 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2351 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2352 flags
, cache
, size_expr
);
2353 if (op0
== chrec_dont_know
)
2354 return chrec_dont_know
;
2355 if (op0
== TREE_OPERAND (chrec
, 0))
2357 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2366 /* Too complicated to handle. */
2367 return chrec_dont_know
;
2370 /* Analyze all the parameters of the chrec that were left under a
2371 symbolic form. LOOP is the loop in which symbolic names have to
2372 be analyzed and instantiated. */
2375 instantiate_parameters (struct loop
*loop
,
2379 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2383 fprintf (dump_file
, "(instantiate_parameters \n");
2384 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2385 fprintf (dump_file
, " (chrec = ");
2386 print_generic_expr (dump_file
, chrec
, 0);
2387 fprintf (dump_file
, ")\n");
2390 res
= instantiate_parameters_1 (loop
, chrec
, INSERT_SUPERLOOP_CHRECS
, cache
,
2393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2395 fprintf (dump_file
, " (res = ");
2396 print_generic_expr (dump_file
, res
, 0);
2397 fprintf (dump_file
, "))\n");
2400 htab_delete (cache
);
2405 /* Similar to instantiate_parameters, but does not introduce the
2406 evolutions in outer loops for LOOP invariants in CHREC, and does not
2407 care about causing overflows, as long as they do not affect value
2408 of an expression. */
2411 resolve_mixers (struct loop
*loop
, tree chrec
)
2413 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2414 tree ret
= instantiate_parameters_1 (loop
, chrec
, FOLD_CONVERSIONS
, cache
, 0);
2415 htab_delete (cache
);
2419 /* Entry point for the analysis of the number of iterations pass.
2420 This function tries to safely approximate the number of iterations
2421 the loop will run. When this property is not decidable at compile
2422 time, the result is chrec_dont_know. Otherwise the result is
2423 a scalar or a symbolic parameter.
2425 Example of analysis: suppose that the loop has an exit condition:
2427 "if (b > 49) goto end_loop;"
2429 and that in a previous analysis we have determined that the
2430 variable 'b' has an evolution function:
2432 "EF = {23, +, 5}_2".
2434 When we evaluate the function at the point 5, i.e. the value of the
2435 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2436 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2437 the loop body has been executed 6 times. */
2440 number_of_latch_executions (struct loop
*loop
)
2444 struct tree_niter_desc niter_desc
;
2446 /* Determine whether the number_of_iterations_in_loop has already
2448 res
= loop
->nb_iterations
;
2451 res
= chrec_dont_know
;
2453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2454 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2456 exit
= single_exit (loop
);
2460 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2463 type
= TREE_TYPE (niter_desc
.niter
);
2464 if (integer_nonzerop (niter_desc
.may_be_zero
))
2465 res
= build_int_cst (type
, 0);
2466 else if (integer_zerop (niter_desc
.may_be_zero
))
2467 res
= niter_desc
.niter
;
2469 res
= chrec_dont_know
;
2472 return set_nb_iterations_in_loop (loop
, res
);
2475 /* Returns the number of executions of the exit condition of LOOP,
2476 i.e., the number by one higher than number_of_latch_executions.
2477 Note that unline number_of_latch_executions, this number does
2478 not necessarily fit in the unsigned variant of the type of
2479 the control variable -- if the number of iterations is a constant,
2480 we return chrec_dont_know if adding one to number_of_latch_executions
2481 overflows; however, in case the number of iterations is symbolic
2482 expression, the caller is responsible for dealing with this
2483 the possible overflow. */
2486 number_of_exit_cond_executions (struct loop
*loop
)
2488 tree ret
= number_of_latch_executions (loop
);
2489 tree type
= chrec_type (ret
);
2491 if (chrec_contains_undetermined (ret
))
2494 ret
= chrec_fold_plus (type
, ret
, build_int_cst (type
, 1));
2495 if (TREE_CODE (ret
) == INTEGER_CST
2496 && TREE_OVERFLOW (ret
))
2497 return chrec_dont_know
;
2502 /* One of the drivers for testing the scalar evolutions analysis.
2503 This function computes the number of iterations for all the loops
2504 from the EXIT_CONDITIONS array. */
2507 number_of_iterations_for_all_loops (VEC(tree
,heap
) **exit_conditions
)
2510 unsigned nb_chrec_dont_know_loops
= 0;
2511 unsigned nb_static_loops
= 0;
2514 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2516 tree res
= number_of_latch_executions (loop_containing_stmt (cond
));
2517 if (chrec_contains_undetermined (res
))
2518 nb_chrec_dont_know_loops
++;
2525 fprintf (dump_file
, "\n(\n");
2526 fprintf (dump_file
, "-----------------------------------------\n");
2527 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2528 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2529 fprintf (dump_file
, "%d\tnb_total_loops\n", number_of_loops ());
2530 fprintf (dump_file
, "-----------------------------------------\n");
2531 fprintf (dump_file
, ")\n\n");
2533 print_loop_ir (dump_file
);
2539 /* Counters for the stats. */
2545 unsigned nb_affine_multivar
;
2546 unsigned nb_higher_poly
;
2547 unsigned nb_chrec_dont_know
;
2548 unsigned nb_undetermined
;
2551 /* Reset the counters. */
2554 reset_chrecs_counters (struct chrec_stats
*stats
)
2556 stats
->nb_chrecs
= 0;
2557 stats
->nb_affine
= 0;
2558 stats
->nb_affine_multivar
= 0;
2559 stats
->nb_higher_poly
= 0;
2560 stats
->nb_chrec_dont_know
= 0;
2561 stats
->nb_undetermined
= 0;
2564 /* Dump the contents of a CHREC_STATS structure. */
2567 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2569 fprintf (file
, "\n(\n");
2570 fprintf (file
, "-----------------------------------------\n");
2571 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2572 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2573 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2574 stats
->nb_higher_poly
);
2575 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2576 fprintf (file
, "-----------------------------------------\n");
2577 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2578 fprintf (file
, "%d\twith undetermined coefficients\n",
2579 stats
->nb_undetermined
);
2580 fprintf (file
, "-----------------------------------------\n");
2581 fprintf (file
, "%d\tchrecs in the scev database\n",
2582 (int) htab_elements (scalar_evolution_info
));
2583 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2584 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2585 fprintf (file
, "-----------------------------------------\n");
2586 fprintf (file
, ")\n\n");
2589 /* Gather statistics about CHREC. */
2592 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2594 if (dump_file
&& (dump_flags
& TDF_STATS
))
2596 fprintf (dump_file
, "(classify_chrec ");
2597 print_generic_expr (dump_file
, chrec
, 0);
2598 fprintf (dump_file
, "\n");
2603 if (chrec
== NULL_TREE
)
2605 stats
->nb_undetermined
++;
2609 switch (TREE_CODE (chrec
))
2611 case POLYNOMIAL_CHREC
:
2612 if (evolution_function_is_affine_p (chrec
))
2614 if (dump_file
&& (dump_flags
& TDF_STATS
))
2615 fprintf (dump_file
, " affine_univariate\n");
2618 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2620 if (dump_file
&& (dump_flags
& TDF_STATS
))
2621 fprintf (dump_file
, " affine_multivariate\n");
2622 stats
->nb_affine_multivar
++;
2626 if (dump_file
&& (dump_flags
& TDF_STATS
))
2627 fprintf (dump_file
, " higher_degree_polynomial\n");
2628 stats
->nb_higher_poly
++;
2637 if (chrec_contains_undetermined (chrec
))
2639 if (dump_file
&& (dump_flags
& TDF_STATS
))
2640 fprintf (dump_file
, " undetermined\n");
2641 stats
->nb_undetermined
++;
2644 if (dump_file
&& (dump_flags
& TDF_STATS
))
2645 fprintf (dump_file
, ")\n");
2648 /* One of the drivers for testing the scalar evolutions analysis.
2649 This function analyzes the scalar evolution of all the scalars
2650 defined as loop phi nodes in one of the loops from the
2651 EXIT_CONDITIONS array.
2653 TODO Optimization: A loop is in canonical form if it contains only
2654 a single scalar loop phi node. All the other scalars that have an
2655 evolution in the loop are rewritten in function of this single
2656 index. This allows the parallelization of the loop. */
2659 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree
,heap
) **exit_conditions
)
2662 struct chrec_stats stats
;
2665 reset_chrecs_counters (&stats
);
2667 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2673 loop
= loop_containing_stmt (cond
);
2676 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2677 if (is_gimple_reg (PHI_RESULT (phi
)))
2679 chrec
= instantiate_parameters
2681 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2683 if (dump_file
&& (dump_flags
& TDF_STATS
))
2684 gather_chrec_stats (chrec
, &stats
);
2688 if (dump_file
&& (dump_flags
& TDF_STATS
))
2689 dump_chrecs_stats (dump_file
, &stats
);
2692 /* Callback for htab_traverse, gathers information on chrecs in the
2696 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2698 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2700 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2705 /* Classify the chrecs of the whole database. */
2708 gather_stats_on_scev_database (void)
2710 struct chrec_stats stats
;
2715 reset_chrecs_counters (&stats
);
2717 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2720 dump_chrecs_stats (dump_file
, &stats
);
2728 initialize_scalar_evolutions_analyzer (void)
2730 /* The elements below are unique. */
2731 if (chrec_dont_know
== NULL_TREE
)
2733 chrec_not_analyzed_yet
= NULL_TREE
;
2734 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2735 chrec_known
= make_node (SCEV_KNOWN
);
2736 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2737 TREE_TYPE (chrec_known
) = void_type_node
;
2741 /* Initialize the analysis of scalar evolutions for LOOPS. */
2744 scev_initialize (void)
2749 scalar_evolution_info
= htab_create_alloc (100,
2755 already_instantiated
= BITMAP_ALLOC (NULL
);
2757 initialize_scalar_evolutions_analyzer ();
2759 FOR_EACH_LOOP (li
, loop
, 0)
2761 loop
->nb_iterations
= NULL_TREE
;
2765 /* Cleans up the information cached by the scalar evolutions analysis. */
2773 if (!scalar_evolution_info
|| !current_loops
)
2776 htab_empty (scalar_evolution_info
);
2777 FOR_EACH_LOOP (li
, loop
, 0)
2779 loop
->nb_iterations
= NULL_TREE
;
2783 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2784 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2785 want step to be invariant in LOOP. Otherwise we require it to be an
2786 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2787 overflow (e.g. because it is computed in signed arithmetics). */
2790 simple_iv (struct loop
*loop
, tree stmt
, tree op
, affine_iv
*iv
,
2791 bool allow_nonconstant_step
)
2793 basic_block bb
= bb_for_stmt (stmt
);
2797 iv
->base
= NULL_TREE
;
2798 iv
->step
= NULL_TREE
;
2799 iv
->no_overflow
= false;
2801 type
= TREE_TYPE (op
);
2802 if (TREE_CODE (type
) != INTEGER_TYPE
2803 && TREE_CODE (type
) != POINTER_TYPE
)
2806 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
,
2808 if (chrec_contains_undetermined (ev
))
2811 if (tree_does_not_contain_chrecs (ev
)
2812 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2815 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
2816 iv
->no_overflow
= true;
2820 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2821 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2824 iv
->step
= CHREC_RIGHT (ev
);
2825 if (allow_nonconstant_step
)
2827 if (tree_contains_chrecs (iv
->step
, NULL
)
2828 || chrec_contains_symbols_defined_in_loop (iv
->step
, loop
->num
))
2831 else if (TREE_CODE (iv
->step
) != INTEGER_CST
)
2834 iv
->base
= CHREC_LEFT (ev
);
2835 if (tree_contains_chrecs (iv
->base
, NULL
)
2836 || chrec_contains_symbols_defined_in_loop (iv
->base
, loop
->num
))
2839 iv
->no_overflow
= !folded_casts
&& TYPE_OVERFLOW_UNDEFINED (type
);
2844 /* Runs the analysis of scalar evolutions. */
2847 scev_analysis (void)
2849 VEC(tree
,heap
) *exit_conditions
;
2851 exit_conditions
= VEC_alloc (tree
, heap
, 37);
2852 select_loops_exit_conditions (&exit_conditions
);
2854 if (dump_file
&& (dump_flags
& TDF_STATS
))
2855 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2857 number_of_iterations_for_all_loops (&exit_conditions
);
2858 VEC_free (tree
, heap
, exit_conditions
);
2861 /* Finalize the scalar evolution analysis. */
2864 scev_finalize (void)
2866 if (!scalar_evolution_info
)
2868 htab_delete (scalar_evolution_info
);
2869 BITMAP_FREE (already_instantiated
);
2870 scalar_evolution_info
= NULL
;
2873 /* Replace ssa names for that scev can prove they are constant by the
2874 appropriate constants. Also perform final value replacement in loops,
2875 in case the replacement expressions are cheap.
2877 We only consider SSA names defined by phi nodes; rest is left to the
2878 ordinary constant propagation pass. */
2881 scev_const_prop (void)
2884 tree name
, phi
, next_phi
, type
, ev
;
2885 struct loop
*loop
, *ex_loop
;
2886 bitmap ssa_names_to_remove
= NULL
;
2890 if (number_of_loops () <= 1)
2895 loop
= bb
->loop_father
;
2897 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2899 name
= PHI_RESULT (phi
);
2901 if (!is_gimple_reg (name
))
2904 type
= TREE_TYPE (name
);
2906 if (!POINTER_TYPE_P (type
)
2907 && !INTEGRAL_TYPE_P (type
))
2910 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
2911 if (!is_gimple_min_invariant (ev
)
2912 || !may_propagate_copy (name
, ev
))
2915 /* Replace the uses of the name. */
2917 replace_uses_by (name
, ev
);
2919 if (!ssa_names_to_remove
)
2920 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
2921 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
2925 /* Remove the ssa names that were replaced by constants. We do not
2926 remove them directly in the previous cycle, since this
2927 invalidates scev cache. */
2928 if (ssa_names_to_remove
)
2932 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
2934 name
= ssa_name (i
);
2935 phi
= SSA_NAME_DEF_STMT (name
);
2937 gcc_assert (TREE_CODE (phi
) == PHI_NODE
);
2938 remove_phi_node (phi
, NULL
, true);
2941 BITMAP_FREE (ssa_names_to_remove
);
2945 /* Now the regular final value replacement. */
2946 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
2949 tree def
, rslt
, ass
, niter
;
2950 block_stmt_iterator bsi
;
2952 /* If we do not know exact number of iterations of the loop, we cannot
2953 replace the final value. */
2954 exit
= single_exit (loop
);
2958 niter
= number_of_latch_executions (loop
);
2959 /* We used to check here whether the computation of NITER is expensive,
2960 and avoided final value elimination if that is the case. The problem
2961 is that it is hard to evaluate whether the expression is too
2962 expensive, as we do not know what optimization opportunities the
2963 the elimination of the final value may reveal. Therefore, we now
2964 eliminate the final values of induction variables unconditionally. */
2965 if (niter
== chrec_dont_know
)
2968 /* Ensure that it is possible to insert new statements somewhere. */
2969 if (!single_pred_p (exit
->dest
))
2970 split_loop_exit_edge (exit
);
2971 tree_block_label (exit
->dest
);
2972 bsi
= bsi_after_labels (exit
->dest
);
2974 ex_loop
= superloop_at_depth (loop
,
2975 loop_depth (exit
->dest
->loop_father
) + 1);
2977 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= next_phi
)
2979 next_phi
= PHI_CHAIN (phi
);
2980 rslt
= PHI_RESULT (phi
);
2981 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2982 if (!is_gimple_reg (def
))
2985 if (!POINTER_TYPE_P (TREE_TYPE (def
))
2986 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
2989 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
, NULL
);
2990 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
2991 if (!tree_does_not_contain_chrecs (def
)
2992 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
2993 /* Moving the computation from the loop may prolong life range
2994 of some ssa names, which may cause problems if they appear
2995 on abnormal edges. */
2996 || contains_abnormal_ssa_name_p (def
))
2999 /* Eliminate the PHI node and replace it by a computation outside
3001 def
= unshare_expr (def
);
3002 remove_phi_node (phi
, NULL_TREE
, false);
3004 ass
= build_gimple_modify_stmt (rslt
, NULL_TREE
);
3005 SSA_NAME_DEF_STMT (rslt
) = ass
;
3007 block_stmt_iterator dest
= bsi
;
3008 bsi_insert_before (&dest
, ass
, BSI_NEW_STMT
);
3009 def
= force_gimple_operand_bsi (&dest
, def
, false, NULL_TREE
);
3011 GIMPLE_STMT_OPERAND (ass
, 1) = def
;
3018 #include "gt-tree-scalar-evolution.h"