1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005 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 MODIFY_EXPR: 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
);
257 static tree
resolve_mixers (struct loop
*, tree
);
259 /* The cached information about a ssa name VAR, claiming that inside LOOP,
260 the value of VAR can be expressed as CHREC. */
268 /* Counters for the scev database. */
269 static unsigned nb_set_scev
= 0;
270 static unsigned nb_get_scev
= 0;
272 /* The following trees are unique elements. Thus the comparison of
273 another element to these elements should be done on the pointer to
274 these trees, and not on their value. */
276 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
277 tree chrec_not_analyzed_yet
;
279 /* Reserved to the cases where the analyzer has detected an
280 undecidable property at compile time. */
281 tree chrec_dont_know
;
283 /* When the analyzer has detected that a property will never
284 happen, then it qualifies it with chrec_known. */
287 static bitmap already_instantiated
;
289 static htab_t scalar_evolution_info
;
292 /* Constructs a new SCEV_INFO_STR structure. */
294 static inline struct scev_info_str
*
295 new_scev_info_str (tree var
)
297 struct scev_info_str
*res
;
299 res
= XNEW (struct scev_info_str
);
301 res
->chrec
= chrec_not_analyzed_yet
;
306 /* Computes a hash function for database element ELT. */
309 hash_scev_info (const void *elt
)
311 return SSA_NAME_VERSION (((struct scev_info_str
*) elt
)->var
);
314 /* Compares database elements E1 and E2. */
317 eq_scev_info (const void *e1
, const void *e2
)
319 const struct scev_info_str
*elt1
= (const struct scev_info_str
*) e1
;
320 const struct scev_info_str
*elt2
= (const struct scev_info_str
*) e2
;
322 return elt1
->var
== elt2
->var
;
325 /* Deletes database element E. */
328 del_scev_info (void *e
)
333 /* Get the index corresponding to VAR in the current LOOP. If
334 it's the first time we ask for this VAR, then we return
335 chrec_not_analyzed_yet for this VAR and return its index. */
338 find_var_scev_info (tree var
)
340 struct scev_info_str
*res
;
341 struct scev_info_str tmp
;
345 slot
= htab_find_slot (scalar_evolution_info
, &tmp
, INSERT
);
348 *slot
= new_scev_info_str (var
);
349 res
= (struct scev_info_str
*) *slot
;
354 /* Return true when CHREC contains symbolic names defined in
358 chrec_contains_symbols_defined_in_loop (tree chrec
, unsigned loop_nb
)
360 if (chrec
== NULL_TREE
)
363 if (TREE_INVARIANT (chrec
))
366 if (TREE_CODE (chrec
) == VAR_DECL
367 || TREE_CODE (chrec
) == PARM_DECL
368 || TREE_CODE (chrec
) == FUNCTION_DECL
369 || TREE_CODE (chrec
) == LABEL_DECL
370 || TREE_CODE (chrec
) == RESULT_DECL
371 || TREE_CODE (chrec
) == FIELD_DECL
)
374 if (TREE_CODE (chrec
) == SSA_NAME
)
376 tree def
= SSA_NAME_DEF_STMT (chrec
);
377 struct loop
*def_loop
= loop_containing_stmt (def
);
378 struct loop
*loop
= current_loops
->parray
[loop_nb
];
380 if (def_loop
== NULL
)
383 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
389 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
392 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 2),
397 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 1),
402 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, 0),
411 /* Return true when PHI is a loop-phi-node. */
414 loop_phi_node_p (tree phi
)
416 /* The implementation of this function is based on the following
417 property: "all the loop-phi-nodes of a loop are contained in the
418 loop's header basic block". */
420 return loop_containing_stmt (phi
)->header
== bb_for_stmt (phi
);
423 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
424 In general, in the case of multivariate evolutions we want to get
425 the evolution in different loops. LOOP specifies the level for
426 which to get the evolution.
430 | for (j = 0; j < 100; j++)
432 | for (k = 0; k < 100; k++)
434 | i = k + j; - Here the value of i is a function of j, k.
436 | ... = i - Here the value of i is a function of j.
438 | ... = i - Here the value of i is a scalar.
444 | i_1 = phi (i_0, i_2)
448 This loop has the same effect as:
449 LOOP_1 has the same effect as:
453 The overall effect of the loop, "i_0 + 20" in the previous example,
454 is obtained by passing in the parameters: LOOP = 1,
455 EVOLUTION_FN = {i_0, +, 2}_1.
459 compute_overall_effect_of_inner_loop (struct loop
*loop
, tree evolution_fn
)
463 if (evolution_fn
== chrec_dont_know
)
464 return chrec_dont_know
;
466 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
468 if (CHREC_VARIABLE (evolution_fn
) >= (unsigned) loop
->num
)
470 struct loop
*inner_loop
=
471 current_loops
->parray
[CHREC_VARIABLE (evolution_fn
)];
472 tree nb_iter
= number_of_iterations_in_loop (inner_loop
);
474 if (nb_iter
== chrec_dont_know
)
475 return chrec_dont_know
;
480 /* Number of iterations is off by one (the ssa name we
481 analyze must be defined before the exit). */
482 nb_iter
= chrec_fold_minus (chrec_type (nb_iter
),
484 build_int_cst_type (chrec_type (nb_iter
), 1));
486 /* evolution_fn is the evolution function in LOOP. Get
487 its value in the nb_iter-th iteration. */
488 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
490 /* Continue the computation until ending on a parent of LOOP. */
491 return compute_overall_effect_of_inner_loop (loop
, res
);
498 /* If the evolution function is an invariant, there is nothing to do. */
499 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
503 return chrec_dont_know
;
506 /* Determine whether the CHREC is always positive/negative. If the expression
507 cannot be statically analyzed, return false, otherwise set the answer into
511 chrec_is_positive (tree chrec
, bool *value
)
518 switch (TREE_CODE (chrec
))
520 case POLYNOMIAL_CHREC
:
521 if (!chrec_is_positive (CHREC_LEFT (chrec
), &value0
)
522 || !chrec_is_positive (CHREC_RIGHT (chrec
), &value1
))
525 /* FIXME -- overflows. */
526 if (value0
== value1
)
532 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
533 and the proof consists in showing that the sign never
534 changes during the execution of the loop, from 0 to
535 loop->nb_iterations. */
536 if (!evolution_function_is_affine_p (chrec
))
539 nb_iter
= number_of_iterations_in_loop
540 (current_loops
->parray
[CHREC_VARIABLE (chrec
)]);
542 if (chrec_contains_undetermined (nb_iter
))
545 nb_iter
= chrec_fold_minus
546 (chrec_type (nb_iter
), nb_iter
,
547 build_int_cst (chrec_type (nb_iter
), 1));
550 /* TODO -- If the test is after the exit, we may decrease the number of
551 iterations by one. */
553 nb_iter
= chrec_fold_minus
554 (chrec_type (nb_iter
), nb_iter
,
555 build_int_cst (chrec_type (nb_iter
), 1));
558 end_value
= chrec_apply (CHREC_VARIABLE (chrec
), chrec
, nb_iter
);
560 if (!chrec_is_positive (end_value
, &value2
))
564 return value0
== value1
;
567 *value
= (tree_int_cst_sgn (chrec
) == 1);
575 /* Associate CHREC to SCALAR. */
578 set_scalar_evolution (tree scalar
, tree chrec
)
582 if (TREE_CODE (scalar
) != SSA_NAME
)
585 scalar_info
= find_var_scev_info (scalar
);
589 if (dump_flags
& TDF_DETAILS
)
591 fprintf (dump_file
, "(set_scalar_evolution \n");
592 fprintf (dump_file
, " (scalar = ");
593 print_generic_expr (dump_file
, scalar
, 0);
594 fprintf (dump_file
, ")\n (scalar_evolution = ");
595 print_generic_expr (dump_file
, chrec
, 0);
596 fprintf (dump_file
, "))\n");
598 if (dump_flags
& TDF_STATS
)
602 *scalar_info
= chrec
;
605 /* Retrieve the chrec associated to SCALAR in the LOOP. */
608 get_scalar_evolution (tree scalar
)
614 if (dump_flags
& TDF_DETAILS
)
616 fprintf (dump_file
, "(get_scalar_evolution \n");
617 fprintf (dump_file
, " (scalar = ");
618 print_generic_expr (dump_file
, scalar
, 0);
619 fprintf (dump_file
, ")\n");
621 if (dump_flags
& TDF_STATS
)
625 switch (TREE_CODE (scalar
))
628 res
= *find_var_scev_info (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
,
666 switch (TREE_CODE (chrec_before
))
668 case POLYNOMIAL_CHREC
:
669 if (CHREC_VARIABLE (chrec_before
) <= loop_nb
)
673 tree type
= chrec_type (chrec_before
);
675 /* When there is no evolution part in this loop, build it. */
676 if (CHREC_VARIABLE (chrec_before
) < loop_nb
)
680 right
= SCALAR_FLOAT_TYPE_P (type
)
681 ? build_real (type
, dconst0
)
682 : build_int_cst (type
, 0);
686 var
= CHREC_VARIABLE (chrec_before
);
687 left
= CHREC_LEFT (chrec_before
);
688 right
= CHREC_RIGHT (chrec_before
);
691 return build_polynomial_chrec
692 (var
, left
, chrec_fold_plus (type
, right
, to_add
));
695 /* Search the evolution in LOOP_NB. */
696 return build_polynomial_chrec
697 (CHREC_VARIABLE (chrec_before
),
698 add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
), to_add
),
699 CHREC_RIGHT (chrec_before
));
702 /* These nodes do not depend on a loop. */
703 if (chrec_before
== chrec_dont_know
)
704 return chrec_dont_know
;
705 return build_polynomial_chrec (loop_nb
, chrec_before
, to_add
);
709 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
712 Description (provided for completeness, for those who read code in
713 a plane, and for my poor 62 bytes brain that would have forgotten
714 all this in the next two or three months):
716 The algorithm of translation of programs from the SSA representation
717 into the chrecs syntax is based on a pattern matching. After having
718 reconstructed the overall tree expression for a loop, there are only
719 two cases that can arise:
721 1. a = loop-phi (init, a + expr)
722 2. a = loop-phi (init, expr)
724 where EXPR is either a scalar constant with respect to the analyzed
725 loop (this is a degree 0 polynomial), or an expression containing
726 other loop-phi definitions (these are higher degree polynomials).
733 | a = phi (init, a + 5)
740 | a = phi (inita, 2 * b + 3)
741 | b = phi (initb, b + 1)
744 For the first case, the semantics of the SSA representation is:
746 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
748 that is, there is a loop index "x" that determines the scalar value
749 of the variable during the loop execution. During the first
750 iteration, the value is that of the initial condition INIT, while
751 during the subsequent iterations, it is the sum of the initial
752 condition with the sum of all the values of EXPR from the initial
753 iteration to the before last considered iteration.
755 For the second case, the semantics of the SSA program is:
757 | a (x) = init, if x = 0;
758 | expr (x - 1), otherwise.
760 The second case corresponds to the PEELED_CHREC, whose syntax is
761 close to the syntax of a loop-phi-node:
763 | phi (init, expr) vs. (init, expr)_x
765 The proof of the translation algorithm for the first case is a
766 proof by structural induction based on the degree of EXPR.
769 When EXPR is a constant with respect to the analyzed loop, or in
770 other words when EXPR is a polynomial of degree 0, the evolution of
771 the variable A in the loop is an affine function with an initial
772 condition INIT, and a step EXPR. In order to show this, we start
773 from the semantics of the SSA representation:
775 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
777 and since "expr (j)" is a constant with respect to "j",
779 f (x) = init + x * expr
781 Finally, based on the semantics of the pure sum chrecs, by
782 identification we get the corresponding chrecs syntax:
784 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
785 f (x) -> {init, +, expr}_x
788 Suppose that EXPR is a polynomial of degree N with respect to the
789 analyzed loop_x for which we have already determined that it is
790 written under the chrecs syntax:
792 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
794 We start from the semantics of the SSA program:
796 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
798 | f (x) = init + \sum_{j = 0}^{x - 1}
799 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
801 | f (x) = init + \sum_{j = 0}^{x - 1}
802 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
804 | f (x) = init + \sum_{k = 0}^{n - 1}
805 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
807 | f (x) = init + \sum_{k = 0}^{n - 1}
808 | (b_k * \binom{x}{k + 1})
810 | f (x) = init + b_0 * \binom{x}{1} + ...
811 | + b_{n-1} * \binom{x}{n}
813 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
814 | + b_{n-1} * \binom{x}{n}
817 And finally from the definition of the chrecs syntax, we identify:
818 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
820 This shows the mechanism that stands behind the add_to_evolution
821 function. An important point is that the use of symbolic
822 parameters avoids the need of an analysis schedule.
829 | a = phi (inita, a + 2 + b)
830 | b = phi (initb, b + 1)
833 When analyzing "a", the algorithm keeps "b" symbolically:
835 | a -> {inita, +, 2 + b}_1
837 Then, after instantiation, the analyzer ends on the evolution:
839 | a -> {inita, +, 2 + initb, +, 1}_1
844 add_to_evolution (unsigned loop_nb
,
849 tree type
= chrec_type (to_add
);
850 tree res
= NULL_TREE
;
852 if (to_add
== NULL_TREE
)
855 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
856 instantiated at this point. */
857 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
858 /* This should not happen. */
859 return chrec_dont_know
;
861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
863 fprintf (dump_file
, "(add_to_evolution \n");
864 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
865 fprintf (dump_file
, " (chrec_before = ");
866 print_generic_expr (dump_file
, chrec_before
, 0);
867 fprintf (dump_file
, ")\n (to_add = ");
868 print_generic_expr (dump_file
, to_add
, 0);
869 fprintf (dump_file
, ")\n");
872 if (code
== MINUS_EXPR
)
873 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
874 ? build_real (type
, dconstm1
)
875 : build_int_cst_type (type
, -1));
877 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
);
879 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
881 fprintf (dump_file
, " (res = ");
882 print_generic_expr (dump_file
, res
, 0);
883 fprintf (dump_file
, "))\n");
889 /* Helper function. */
892 set_nb_iterations_in_loop (struct loop
*loop
,
895 res
= chrec_fold_plus (chrec_type (res
), res
,
896 build_int_cst_type (chrec_type (res
), 1));
898 /* FIXME HWI: However we want to store one iteration less than the
899 count of the loop in order to be compatible with the other
900 nb_iter computations in loop-iv. This also allows the
901 representation of nb_iters that are equal to MAX_INT. */
902 if (TREE_CODE (res
) == INTEGER_CST
903 && (TREE_INT_CST_LOW (res
) == 0
904 || TREE_OVERFLOW (res
)))
905 res
= chrec_dont_know
;
907 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
909 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
910 print_generic_expr (dump_file
, res
, 0);
911 fprintf (dump_file
, "))\n");
914 loop
->nb_iterations
= res
;
920 /* This section selects the loops that will be good candidates for the
921 scalar evolution analysis. For the moment, greedily select all the
922 loop nests we could analyze. */
924 /* Return true when it is possible to analyze the condition expression
928 analyzable_condition (tree expr
)
932 if (TREE_CODE (expr
) != COND_EXPR
)
935 condition
= TREE_OPERAND (expr
, 0);
937 switch (TREE_CODE (condition
))
957 /* For a loop with a single exit edge, return the COND_EXPR that
958 guards the exit edge. If the expression is too difficult to
959 analyze, then give up. */
962 get_loop_exit_condition (struct loop
*loop
)
964 tree res
= NULL_TREE
;
965 edge exit_edge
= loop
->single_exit
;
968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
969 fprintf (dump_file
, "(get_loop_exit_condition \n ");
975 expr
= last_stmt (exit_edge
->src
);
976 if (analyzable_condition (expr
))
980 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
982 print_generic_expr (dump_file
, res
, 0);
983 fprintf (dump_file
, ")\n");
989 /* Recursively determine and enqueue the exit conditions for a loop. */
992 get_exit_conditions_rec (struct loop
*loop
,
993 VEC(tree
,heap
) **exit_conditions
)
998 /* Recurse on the inner loops, then on the next (sibling) loops. */
999 get_exit_conditions_rec (loop
->inner
, exit_conditions
);
1000 get_exit_conditions_rec (loop
->next
, exit_conditions
);
1002 if (loop
->single_exit
)
1004 tree loop_condition
= get_loop_exit_condition (loop
);
1007 VEC_safe_push (tree
, heap
, *exit_conditions
, loop_condition
);
1011 /* Select the candidate loop nests for the analysis. This function
1012 initializes the EXIT_CONDITIONS array. */
1015 select_loops_exit_conditions (struct loops
*loops
,
1016 VEC(tree
,heap
) **exit_conditions
)
1018 struct loop
*function_body
= loops
->parray
[0];
1020 get_exit_conditions_rec (function_body
->inner
, exit_conditions
);
1024 /* Depth first search algorithm. */
1026 typedef enum t_bool
{
1033 static t_bool
follow_ssa_edge (struct loop
*loop
, tree
, tree
, tree
*, int);
1035 /* Follow the ssa edge into the right hand side RHS of an assignment.
1036 Return true if the strongly connected component has been found. */
1039 follow_ssa_edge_in_rhs (struct loop
*loop
, tree at_stmt
, tree rhs
,
1040 tree halting_phi
, tree
*evolution_of_loop
, int limit
)
1042 t_bool res
= t_false
;
1044 tree type_rhs
= TREE_TYPE (rhs
);
1047 /* The RHS is one of the following cases:
1053 - other cases are not yet handled. */
1054 switch (TREE_CODE (rhs
))
1057 /* This assignment is under the form "a_1 = (cast) rhs. */
1058 res
= follow_ssa_edge_in_rhs (loop
, at_stmt
, TREE_OPERAND (rhs
, 0),
1059 halting_phi
, evolution_of_loop
, limit
);
1060 *evolution_of_loop
= chrec_convert (TREE_TYPE (rhs
),
1061 *evolution_of_loop
, at_stmt
);
1065 /* This assignment is under the form "a_1 = 7". */
1070 /* This assignment is under the form: "a_1 = b_2". */
1071 res
= follow_ssa_edge
1072 (loop
, SSA_NAME_DEF_STMT (rhs
), halting_phi
, evolution_of_loop
, limit
);
1076 /* This case is under the form "rhs0 + rhs1". */
1077 rhs0
= TREE_OPERAND (rhs
, 0);
1078 rhs1
= TREE_OPERAND (rhs
, 1);
1079 STRIP_TYPE_NOPS (rhs0
);
1080 STRIP_TYPE_NOPS (rhs1
);
1082 if (TREE_CODE (rhs0
) == SSA_NAME
)
1084 if (TREE_CODE (rhs1
) == SSA_NAME
)
1086 /* Match an assignment under the form:
1088 evol
= *evolution_of_loop
;
1089 res
= follow_ssa_edge
1090 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1094 *evolution_of_loop
= add_to_evolution
1096 chrec_convert (type_rhs
, evol
, at_stmt
),
1099 else if (res
== t_false
)
1101 res
= follow_ssa_edge
1102 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1103 evolution_of_loop
, limit
);
1106 *evolution_of_loop
= add_to_evolution
1108 chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1111 else if (res
== t_dont_know
)
1112 *evolution_of_loop
= chrec_dont_know
;
1115 else if (res
== t_dont_know
)
1116 *evolution_of_loop
= chrec_dont_know
;
1121 /* Match an assignment under the form:
1123 res
= follow_ssa_edge
1124 (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1125 evolution_of_loop
, limit
);
1127 *evolution_of_loop
= add_to_evolution
1128 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1132 else if (res
== t_dont_know
)
1133 *evolution_of_loop
= chrec_dont_know
;
1137 else if (TREE_CODE (rhs1
) == SSA_NAME
)
1139 /* Match an assignment under the form:
1141 res
= follow_ssa_edge
1142 (loop
, SSA_NAME_DEF_STMT (rhs1
), halting_phi
,
1143 evolution_of_loop
, limit
);
1145 *evolution_of_loop
= add_to_evolution
1146 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
,
1150 else if (res
== t_dont_know
)
1151 *evolution_of_loop
= chrec_dont_know
;
1155 /* Otherwise, match an assignment under the form:
1157 /* And there is nothing to do. */
1163 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1164 rhs0
= TREE_OPERAND (rhs
, 0);
1165 rhs1
= TREE_OPERAND (rhs
, 1);
1166 STRIP_TYPE_NOPS (rhs0
);
1167 STRIP_TYPE_NOPS (rhs1
);
1169 if (TREE_CODE (rhs0
) == SSA_NAME
)
1171 /* Match an assignment under the form:
1173 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (rhs0
), halting_phi
,
1174 evolution_of_loop
, limit
);
1176 *evolution_of_loop
= add_to_evolution
1177 (loop
->num
, chrec_convert (type_rhs
, *evolution_of_loop
, at_stmt
),
1180 else if (res
== t_dont_know
)
1181 *evolution_of_loop
= chrec_dont_know
;
1184 /* Otherwise, match an assignment under the form:
1186 /* And there is nothing to do. */
1193 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1194 It must be handled as a copy assignment of the form a_1 = a_2. */
1195 tree op0
= ASSERT_EXPR_VAR (rhs
);
1196 if (TREE_CODE (op0
) == SSA_NAME
)
1197 res
= follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (op0
),
1198 halting_phi
, evolution_of_loop
, limit
);
1213 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1216 backedge_phi_arg_p (tree phi
, int i
)
1218 edge e
= PHI_ARG_EDGE (phi
, i
);
1220 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1221 about updating it anywhere, and this should work as well most of the
1223 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1229 /* Helper function for one branch of the condition-phi-node. Return
1230 true if the strongly connected component has been found following
1233 static inline t_bool
1234 follow_ssa_edge_in_condition_phi_branch (int i
,
1238 tree
*evolution_of_branch
,
1239 tree init_cond
, int limit
)
1241 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1242 *evolution_of_branch
= chrec_dont_know
;
1244 /* Do not follow back edges (they must belong to an irreducible loop, which
1245 we really do not want to worry about). */
1246 if (backedge_phi_arg_p (condition_phi
, i
))
1249 if (TREE_CODE (branch
) == SSA_NAME
)
1251 *evolution_of_branch
= init_cond
;
1252 return follow_ssa_edge (loop
, SSA_NAME_DEF_STMT (branch
), halting_phi
,
1253 evolution_of_branch
, limit
);
1256 /* This case occurs when one of the condition branches sets
1257 the variable to a constant: i.e. a phi-node like
1258 "a_2 = PHI <a_7(5), 2(6)>;".
1260 FIXME: This case have to be refined correctly:
1261 in some cases it is possible to say something better than
1262 chrec_dont_know, for example using a wrap-around notation. */
1266 /* This function merges the branches of a condition-phi-node in a
1270 follow_ssa_edge_in_condition_phi (struct loop
*loop
,
1273 tree
*evolution_of_loop
, int limit
)
1276 tree init
= *evolution_of_loop
;
1277 tree evolution_of_branch
;
1278 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1280 &evolution_of_branch
,
1282 if (res
== t_false
|| res
== t_dont_know
)
1285 *evolution_of_loop
= evolution_of_branch
;
1287 for (i
= 1; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1289 /* Quickly give up when the evolution of one of the branches is
1291 if (*evolution_of_loop
== chrec_dont_know
)
1294 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1296 &evolution_of_branch
,
1298 if (res
== t_false
|| res
== t_dont_know
)
1301 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1302 evolution_of_branch
);
1308 /* Follow an SSA edge in an inner loop. It computes the overall
1309 effect of the loop, and following the symbolic initial conditions,
1310 it follows the edges in the parent loop. The inner loop is
1311 considered as a single statement. */
1314 follow_ssa_edge_inner_loop_phi (struct loop
*outer_loop
,
1317 tree
*evolution_of_loop
, int limit
)
1319 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1320 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1322 /* Sometimes, the inner loop is too difficult to analyze, and the
1323 result of the analysis is a symbolic parameter. */
1324 if (ev
== PHI_RESULT (loop_phi_node
))
1326 t_bool res
= t_false
;
1329 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1331 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1334 /* Follow the edges that exit the inner loop. */
1335 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1336 if (!flow_bb_inside_loop_p (loop
, bb
))
1337 res
= follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
,
1339 evolution_of_loop
, limit
);
1344 /* If the path crosses this loop-phi, give up. */
1346 *evolution_of_loop
= chrec_dont_know
;
1351 /* Otherwise, compute the overall effect of the inner loop. */
1352 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1353 return follow_ssa_edge_in_rhs (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1354 evolution_of_loop
, limit
);
1357 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1358 path that is analyzed on the return walk. */
1361 follow_ssa_edge (struct loop
*loop
, tree def
, tree halting_phi
,
1362 tree
*evolution_of_loop
, int limit
)
1364 struct loop
*def_loop
;
1366 if (TREE_CODE (def
) == NOP_EXPR
)
1369 /* Give up if the path is longer than the MAX that we allow. */
1370 if (limit
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1373 def_loop
= loop_containing_stmt (def
);
1375 switch (TREE_CODE (def
))
1378 if (!loop_phi_node_p (def
))
1379 /* DEF is a condition-phi-node. Follow the branches, and
1380 record their evolutions. Finally, merge the collected
1381 information and set the approximation to the main
1383 return follow_ssa_edge_in_condition_phi
1384 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1386 /* When the analyzed phi is the halting_phi, the
1387 depth-first search is over: we have found a path from
1388 the halting_phi to itself in the loop. */
1389 if (def
== halting_phi
)
1392 /* Otherwise, the evolution of the HALTING_PHI depends
1393 on the evolution of another loop-phi-node, i.e. the
1394 evolution function is a higher degree polynomial. */
1395 if (def_loop
== loop
)
1399 if (flow_loop_nested_p (loop
, def_loop
))
1400 return follow_ssa_edge_inner_loop_phi
1401 (loop
, def
, halting_phi
, evolution_of_loop
, limit
);
1407 return follow_ssa_edge_in_rhs (loop
, def
,
1408 TREE_OPERAND (def
, 1),
1410 evolution_of_loop
, limit
);
1413 /* At this level of abstraction, the program is just a set
1414 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1415 other node to be handled. */
1422 /* Given a LOOP_PHI_NODE, this function determines the evolution
1423 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1426 analyze_evolution_in_loop (tree loop_phi_node
,
1430 tree evolution_function
= chrec_not_analyzed_yet
;
1431 struct loop
*loop
= loop_containing_stmt (loop_phi_node
);
1434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1436 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1437 fprintf (dump_file
, " (loop_phi_node = ");
1438 print_generic_expr (dump_file
, loop_phi_node
, 0);
1439 fprintf (dump_file
, ")\n");
1442 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1444 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1445 tree ssa_chain
, ev_fn
;
1448 /* Select the edges that enter the loop body. */
1449 bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1450 if (!flow_bb_inside_loop_p (loop
, bb
))
1453 if (TREE_CODE (arg
) == SSA_NAME
)
1455 ssa_chain
= SSA_NAME_DEF_STMT (arg
);
1457 /* Pass in the initial condition to the follow edge function. */
1459 res
= follow_ssa_edge (loop
, ssa_chain
, loop_phi_node
, &ev_fn
, 0);
1464 /* When it is impossible to go back on the same
1465 loop_phi_node by following the ssa edges, the
1466 evolution is represented by a peeled chrec, i.e. the
1467 first iteration, EV_FN has the value INIT_COND, then
1468 all the other iterations it has the value of ARG.
1469 For the moment, PEELED_CHREC nodes are not built. */
1471 ev_fn
= chrec_dont_know
;
1473 /* When there are multiple back edges of the loop (which in fact never
1474 happens currently, but nevertheless), merge their evolutions. */
1475 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1480 fprintf (dump_file
, " (evolution_function = ");
1481 print_generic_expr (dump_file
, evolution_function
, 0);
1482 fprintf (dump_file
, "))\n");
1485 return evolution_function
;
1488 /* Given a loop-phi-node, return the initial conditions of the
1489 variable on entry of the loop. When the CCP has propagated
1490 constants into the loop-phi-node, the initial condition is
1491 instantiated, otherwise the initial condition is kept symbolic.
1492 This analyzer does not analyze the evolution outside the current
1493 loop, and leaves this task to the on-demand tree reconstructor. */
1496 analyze_initial_condition (tree loop_phi_node
)
1499 tree init_cond
= chrec_not_analyzed_yet
;
1500 struct loop
*loop
= bb_for_stmt (loop_phi_node
)->loop_father
;
1502 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1504 fprintf (dump_file
, "(analyze_initial_condition \n");
1505 fprintf (dump_file
, " (loop_phi_node = \n");
1506 print_generic_expr (dump_file
, loop_phi_node
, 0);
1507 fprintf (dump_file
, ")\n");
1510 for (i
= 0; i
< PHI_NUM_ARGS (loop_phi_node
); i
++)
1512 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1513 basic_block bb
= PHI_ARG_EDGE (loop_phi_node
, i
)->src
;
1515 /* When the branch is oriented to the loop's body, it does
1516 not contribute to the initial condition. */
1517 if (flow_bb_inside_loop_p (loop
, bb
))
1520 if (init_cond
== chrec_not_analyzed_yet
)
1526 if (TREE_CODE (branch
) == SSA_NAME
)
1528 init_cond
= chrec_dont_know
;
1532 init_cond
= chrec_merge (init_cond
, branch
);
1535 /* Ooops -- a loop without an entry??? */
1536 if (init_cond
== chrec_not_analyzed_yet
)
1537 init_cond
= chrec_dont_know
;
1539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1541 fprintf (dump_file
, " (init_cond = ");
1542 print_generic_expr (dump_file
, init_cond
, 0);
1543 fprintf (dump_file
, "))\n");
1549 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1552 interpret_loop_phi (struct loop
*loop
, tree loop_phi_node
)
1555 struct loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1558 if (phi_loop
!= loop
)
1560 struct loop
*subloop
;
1561 tree evolution_fn
= analyze_scalar_evolution
1562 (phi_loop
, PHI_RESULT (loop_phi_node
));
1564 /* Dive one level deeper. */
1565 subloop
= superloop_at_depth (phi_loop
, loop
->depth
+ 1);
1567 /* Interpret the subloop. */
1568 res
= compute_overall_effect_of_inner_loop (subloop
, evolution_fn
);
1572 /* Otherwise really interpret the loop phi. */
1573 init_cond
= analyze_initial_condition (loop_phi_node
);
1574 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1579 /* This function merges the branches of a condition-phi-node,
1580 contained in the outermost loop, and whose arguments are already
1584 interpret_condition_phi (struct loop
*loop
, tree condition_phi
)
1587 tree res
= chrec_not_analyzed_yet
;
1589 for (i
= 0; i
< PHI_NUM_ARGS (condition_phi
); i
++)
1593 if (backedge_phi_arg_p (condition_phi
, i
))
1595 res
= chrec_dont_know
;
1599 branch_chrec
= analyze_scalar_evolution
1600 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1602 res
= chrec_merge (res
, branch_chrec
);
1608 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1609 analyze this node before, follow the definitions until ending
1610 either on an analyzed modify_expr, or on a loop-phi-node. On the
1611 return path, this function propagates evolutions (ala constant copy
1612 propagation). OPND1 is not a GIMPLE expression because we could
1613 analyze the effect of an inner loop: see interpret_loop_phi. */
1616 interpret_rhs_modify_expr (struct loop
*loop
, tree at_stmt
,
1617 tree opnd1
, tree type
)
1619 tree res
, opnd10
, opnd11
, chrec10
, chrec11
;
1621 if (is_gimple_min_invariant (opnd1
))
1622 return chrec_convert (type
, opnd1
, at_stmt
);
1624 switch (TREE_CODE (opnd1
))
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_plus (type
, chrec10
, chrec11
);
1637 opnd10
= TREE_OPERAND (opnd1
, 0);
1638 opnd11
= TREE_OPERAND (opnd1
, 1);
1639 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1640 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1641 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1642 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1643 res
= chrec_fold_minus (type
, chrec10
, chrec11
);
1647 opnd10
= TREE_OPERAND (opnd1
, 0);
1648 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1649 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1650 res
= chrec_fold_multiply (type
, chrec10
, SCALAR_FLOAT_TYPE_P (type
)
1651 ? build_real (type
, dconstm1
)
1652 : build_int_cst_type (type
, -1));
1656 opnd10
= TREE_OPERAND (opnd1
, 0);
1657 opnd11
= TREE_OPERAND (opnd1
, 1);
1658 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1659 chrec11
= analyze_scalar_evolution (loop
, opnd11
);
1660 chrec10
= chrec_convert (type
, chrec10
, at_stmt
);
1661 chrec11
= chrec_convert (type
, chrec11
, at_stmt
);
1662 res
= chrec_fold_multiply (type
, chrec10
, chrec11
);
1666 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd1
),
1671 opnd10
= ASSERT_EXPR_VAR (opnd1
);
1672 res
= chrec_convert (type
, analyze_scalar_evolution (loop
, opnd10
),
1678 opnd10
= TREE_OPERAND (opnd1
, 0);
1679 chrec10
= analyze_scalar_evolution (loop
, opnd10
);
1680 res
= chrec_convert (type
, chrec10
, at_stmt
);
1684 res
= chrec_dont_know
;
1693 /* This section contains all the entry points:
1694 - number_of_iterations_in_loop,
1695 - analyze_scalar_evolution,
1696 - instantiate_parameters.
1699 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1700 common ancestor of DEF_LOOP and USE_LOOP. */
1703 compute_scalar_evolution_in_loop (struct loop
*wrto_loop
,
1704 struct loop
*def_loop
,
1708 if (def_loop
== wrto_loop
)
1711 def_loop
= superloop_at_depth (def_loop
, wrto_loop
->depth
+ 1);
1712 res
= compute_overall_effect_of_inner_loop (def_loop
, ev
);
1714 return analyze_scalar_evolution_1 (wrto_loop
, res
, chrec_not_analyzed_yet
);
1717 /* Helper recursive function. */
1720 analyze_scalar_evolution_1 (struct loop
*loop
, tree var
, tree res
)
1722 tree def
, type
= TREE_TYPE (var
);
1724 struct loop
*def_loop
;
1727 return chrec_dont_know
;
1729 if (TREE_CODE (var
) != SSA_NAME
)
1730 return interpret_rhs_modify_expr (loop
, NULL_TREE
, var
, type
);
1732 def
= SSA_NAME_DEF_STMT (var
);
1733 bb
= bb_for_stmt (def
);
1734 def_loop
= bb
? bb
->loop_father
: NULL
;
1737 || !flow_bb_inside_loop_p (loop
, bb
))
1739 /* Keep the symbolic form. */
1744 if (res
!= chrec_not_analyzed_yet
)
1746 if (loop
!= bb
->loop_father
)
1747 res
= compute_scalar_evolution_in_loop
1748 (find_common_loop (loop
, bb
->loop_father
), bb
->loop_father
, res
);
1753 if (loop
!= def_loop
)
1755 res
= analyze_scalar_evolution_1 (def_loop
, var
, chrec_not_analyzed_yet
);
1756 res
= compute_scalar_evolution_in_loop (loop
, def_loop
, res
);
1761 switch (TREE_CODE (def
))
1764 res
= interpret_rhs_modify_expr (loop
, def
, TREE_OPERAND (def
, 1), type
);
1768 if (loop_phi_node_p (def
))
1769 res
= interpret_loop_phi (loop
, def
);
1771 res
= interpret_condition_phi (loop
, def
);
1775 res
= chrec_dont_know
;
1781 /* Keep the symbolic form. */
1782 if (res
== chrec_dont_know
)
1785 if (loop
== def_loop
)
1786 set_scalar_evolution (var
, res
);
1791 /* Entry point for the scalar evolution analyzer.
1792 Analyzes and returns the scalar evolution of the ssa_name VAR.
1793 LOOP_NB is the identifier number of the loop in which the variable
1796 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1797 pointer to the statement that uses this variable, in order to
1798 determine the evolution function of the variable, use the following
1801 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1802 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1803 tree chrec_instantiated = instantiate_parameters
1804 (loop_nb, chrec_with_symbols);
1808 analyze_scalar_evolution (struct loop
*loop
, tree var
)
1812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1814 fprintf (dump_file
, "(analyze_scalar_evolution \n");
1815 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
1816 fprintf (dump_file
, " (scalar = ");
1817 print_generic_expr (dump_file
, var
, 0);
1818 fprintf (dump_file
, ")\n");
1821 res
= analyze_scalar_evolution_1 (loop
, var
, get_scalar_evolution (var
));
1823 if (TREE_CODE (var
) == SSA_NAME
&& res
== chrec_dont_know
)
1826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1827 fprintf (dump_file
, ")\n");
1832 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1833 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1837 analyze_scalar_evolution_in_loop (struct loop
*wrto_loop
, struct loop
*use_loop
,
1845 ev
= analyze_scalar_evolution (use_loop
, ev
);
1846 ev
= resolve_mixers (use_loop
, ev
);
1848 if (use_loop
== wrto_loop
)
1851 /* If the value of the use changes in the inner loop, we cannot express
1852 its value in the outer loop (we might try to return interval chrec,
1853 but we do not have a user for it anyway) */
1854 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
1856 return chrec_dont_know
;
1858 use_loop
= use_loop
->outer
;
1862 /* Returns instantiated value for VERSION in CACHE. */
1865 get_instantiated_value (htab_t cache
, tree version
)
1867 struct scev_info_str
*info
, pattern
;
1869 pattern
.var
= version
;
1870 info
= (struct scev_info_str
*) htab_find (cache
, &pattern
);
1878 /* Sets instantiated value for VERSION to VAL in CACHE. */
1881 set_instantiated_value (htab_t cache
, tree version
, tree val
)
1883 struct scev_info_str
*info
, pattern
;
1886 pattern
.var
= version
;
1887 slot
= htab_find_slot (cache
, &pattern
, INSERT
);
1890 *slot
= new_scev_info_str (version
);
1891 info
= (struct scev_info_str
*) *slot
;
1895 /* Return the closed_loop_phi node for VAR. If there is none, return
1899 loop_closed_phi_def (tree var
)
1905 if (var
== NULL_TREE
1906 || TREE_CODE (var
) != SSA_NAME
)
1909 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
1910 exit
= loop
->single_exit
;
1914 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1915 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
1916 return PHI_RESULT (phi
);
1921 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1922 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
1923 of already instantiated values. FLAGS modify the way chrecs are
1924 instantiated. SIZE_EXPR is used for computing the size of the expression to
1925 be instantiated, and to stop if it exceeds some limit. */
1927 /* Values for FLAGS. */
1930 INSERT_SUPERLOOP_CHRECS
= 1, /* Loop invariants are replaced with chrecs
1932 FOLD_CONVERSIONS
= 2 /* The conversions that may wrap in
1933 signed/pointer type are folded, as long as the
1934 value of the chrec is preserved. */
1938 instantiate_parameters_1 (struct loop
*loop
, tree chrec
, int flags
, htab_t cache
,
1941 tree res
, op0
, op1
, op2
;
1943 struct loop
*def_loop
;
1945 /* Give up if the expression is larger than the MAX that we allow. */
1946 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
1947 return chrec_dont_know
;
1949 if (automatically_generated_chrec_p (chrec
)
1950 || is_gimple_min_invariant (chrec
))
1953 switch (TREE_CODE (chrec
))
1956 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (chrec
));
1958 /* A parameter (or loop invariant and we do not want to include
1959 evolutions in outer loops), nothing to do. */
1961 || (!(flags
& INSERT_SUPERLOOP_CHRECS
)
1962 && !flow_bb_inside_loop_p (loop
, def_bb
)))
1965 /* We cache the value of instantiated variable to avoid exponential
1966 time complexity due to reevaluations. We also store the convenient
1967 value in the cache in order to prevent infinite recursion -- we do
1968 not want to instantiate the SSA_NAME if it is in a mixer
1969 structure. This is used for avoiding the instantiation of
1970 recursively defined functions, such as:
1972 | a_2 -> {0, +, 1, +, a_2}_1 */
1974 res
= get_instantiated_value (cache
, chrec
);
1978 /* Store the convenient value for chrec in the structure. If it
1979 is defined outside of the loop, we may just leave it in symbolic
1980 form, otherwise we need to admit that we do not know its behavior
1982 res
= !flow_bb_inside_loop_p (loop
, def_bb
) ? chrec
: chrec_dont_know
;
1983 set_instantiated_value (cache
, chrec
, res
);
1985 /* To make things even more complicated, instantiate_parameters_1
1986 calls analyze_scalar_evolution that may call # of iterations
1987 analysis that may in turn call instantiate_parameters_1 again.
1988 To prevent the infinite recursion, keep also the bitmap of
1989 ssa names that are being instantiated globally. */
1990 if (bitmap_bit_p (already_instantiated
, SSA_NAME_VERSION (chrec
)))
1993 def_loop
= find_common_loop (loop
, def_bb
->loop_father
);
1995 /* If the analysis yields a parametric chrec, instantiate the
1997 bitmap_set_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
1998 res
= analyze_scalar_evolution (def_loop
, chrec
);
2000 /* Don't instantiate loop-closed-ssa phi nodes. */
2001 if (TREE_CODE (res
) == SSA_NAME
2002 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res
)) == NULL
2003 || (loop_containing_stmt (SSA_NAME_DEF_STMT (res
))->depth
2004 > def_loop
->depth
)))
2007 res
= loop_closed_phi_def (chrec
);
2011 if (res
== NULL_TREE
)
2012 res
= chrec_dont_know
;
2015 else if (res
!= chrec_dont_know
)
2016 res
= instantiate_parameters_1 (loop
, res
, flags
, cache
, size_expr
);
2018 bitmap_clear_bit (already_instantiated
, SSA_NAME_VERSION (chrec
));
2020 /* Store the correct value to the cache. */
2021 set_instantiated_value (cache
, chrec
, res
);
2024 case POLYNOMIAL_CHREC
:
2025 op0
= instantiate_parameters_1 (loop
, CHREC_LEFT (chrec
),
2026 flags
, cache
, size_expr
);
2027 if (op0
== chrec_dont_know
)
2028 return chrec_dont_know
;
2030 op1
= instantiate_parameters_1 (loop
, CHREC_RIGHT (chrec
),
2031 flags
, cache
, size_expr
);
2032 if (op1
== chrec_dont_know
)
2033 return chrec_dont_know
;
2035 if (CHREC_LEFT (chrec
) != op0
2036 || CHREC_RIGHT (chrec
) != op1
)
2037 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2041 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2042 flags
, cache
, size_expr
);
2043 if (op0
== chrec_dont_know
)
2044 return chrec_dont_know
;
2046 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2047 flags
, cache
, size_expr
);
2048 if (op1
== chrec_dont_know
)
2049 return chrec_dont_know
;
2051 if (TREE_OPERAND (chrec
, 0) != op0
2052 || TREE_OPERAND (chrec
, 1) != op1
)
2053 chrec
= chrec_fold_plus (TREE_TYPE (chrec
), op0
, op1
);
2057 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2058 flags
, cache
, size_expr
);
2059 if (op0
== chrec_dont_know
)
2060 return chrec_dont_know
;
2062 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2063 flags
, cache
, size_expr
);
2064 if (op1
== chrec_dont_know
)
2065 return chrec_dont_know
;
2067 if (TREE_OPERAND (chrec
, 0) != op0
2068 || TREE_OPERAND (chrec
, 1) != op1
)
2069 chrec
= chrec_fold_minus (TREE_TYPE (chrec
), op0
, op1
);
2073 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2074 flags
, cache
, size_expr
);
2075 if (op0
== chrec_dont_know
)
2076 return chrec_dont_know
;
2078 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2079 flags
, cache
, size_expr
);
2080 if (op1
== chrec_dont_know
)
2081 return chrec_dont_know
;
2083 if (TREE_OPERAND (chrec
, 0) != op0
2084 || TREE_OPERAND (chrec
, 1) != op1
)
2085 chrec
= chrec_fold_multiply (TREE_TYPE (chrec
), op0
, op1
);
2090 case NON_LVALUE_EXPR
:
2091 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2092 flags
, cache
, size_expr
);
2093 if (op0
== chrec_dont_know
)
2094 return chrec_dont_know
;
2096 if (flags
& FOLD_CONVERSIONS
)
2098 tree tmp
= chrec_convert_aggressive (TREE_TYPE (chrec
), op0
);
2103 if (op0
== TREE_OPERAND (chrec
, 0))
2106 return chrec_convert (TREE_TYPE (chrec
), op0
, NULL_TREE
);
2108 case SCEV_NOT_KNOWN
:
2109 return chrec_dont_know
;
2118 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
2121 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2122 flags
, cache
, size_expr
);
2123 if (op0
== chrec_dont_know
)
2124 return chrec_dont_know
;
2126 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2127 flags
, cache
, size_expr
);
2128 if (op1
== chrec_dont_know
)
2129 return chrec_dont_know
;
2131 op2
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 2),
2132 flags
, cache
, size_expr
);
2133 if (op2
== chrec_dont_know
)
2134 return chrec_dont_know
;
2136 if (op0
== TREE_OPERAND (chrec
, 0)
2137 && op1
== TREE_OPERAND (chrec
, 1)
2138 && op2
== TREE_OPERAND (chrec
, 2))
2141 return fold_build3 (TREE_CODE (chrec
),
2142 TREE_TYPE (chrec
), op0
, op1
, op2
);
2145 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2146 flags
, cache
, size_expr
);
2147 if (op0
== chrec_dont_know
)
2148 return chrec_dont_know
;
2150 op1
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 1),
2151 flags
, cache
, size_expr
);
2152 if (op1
== chrec_dont_know
)
2153 return chrec_dont_know
;
2155 if (op0
== TREE_OPERAND (chrec
, 0)
2156 && op1
== TREE_OPERAND (chrec
, 1))
2158 return fold_build2 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
, op1
);
2161 op0
= instantiate_parameters_1 (loop
, TREE_OPERAND (chrec
, 0),
2162 flags
, cache
, size_expr
);
2163 if (op0
== chrec_dont_know
)
2164 return chrec_dont_know
;
2165 if (op0
== TREE_OPERAND (chrec
, 0))
2167 return fold_build1 (TREE_CODE (chrec
), TREE_TYPE (chrec
), op0
);
2176 /* Too complicated to handle. */
2177 return chrec_dont_know
;
2180 /* Analyze all the parameters of the chrec that were left under a
2181 symbolic form. LOOP is the loop in which symbolic names have to
2182 be analyzed and instantiated. */
2185 instantiate_parameters (struct loop
*loop
,
2189 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2193 fprintf (dump_file
, "(instantiate_parameters \n");
2194 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2195 fprintf (dump_file
, " (chrec = ");
2196 print_generic_expr (dump_file
, chrec
, 0);
2197 fprintf (dump_file
, ")\n");
2200 res
= instantiate_parameters_1 (loop
, chrec
, INSERT_SUPERLOOP_CHRECS
, cache
,
2203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2205 fprintf (dump_file
, " (res = ");
2206 print_generic_expr (dump_file
, res
, 0);
2207 fprintf (dump_file
, "))\n");
2210 htab_delete (cache
);
2215 /* Similar to instantiate_parameters, but does not introduce the
2216 evolutions in outer loops for LOOP invariants in CHREC, and does not
2217 care about causing overflows, as long as they do not affect value
2218 of an expression. */
2221 resolve_mixers (struct loop
*loop
, tree chrec
)
2223 htab_t cache
= htab_create (10, hash_scev_info
, eq_scev_info
, del_scev_info
);
2224 tree ret
= instantiate_parameters_1 (loop
, chrec
, FOLD_CONVERSIONS
, cache
, 0);
2225 htab_delete (cache
);
2229 /* Entry point for the analysis of the number of iterations pass.
2230 This function tries to safely approximate the number of iterations
2231 the loop will run. When this property is not decidable at compile
2232 time, the result is chrec_dont_know. Otherwise the result is
2233 a scalar or a symbolic parameter.
2235 Example of analysis: suppose that the loop has an exit condition:
2237 "if (b > 49) goto end_loop;"
2239 and that in a previous analysis we have determined that the
2240 variable 'b' has an evolution function:
2242 "EF = {23, +, 5}_2".
2244 When we evaluate the function at the point 5, i.e. the value of the
2245 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2246 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2247 the loop body has been executed 6 times. */
2250 number_of_iterations_in_loop (struct loop
*loop
)
2254 struct tree_niter_desc niter_desc
;
2256 /* Determine whether the number_of_iterations_in_loop has already
2258 res
= loop
->nb_iterations
;
2261 res
= chrec_dont_know
;
2263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2264 fprintf (dump_file
, "(number_of_iterations_in_loop\n");
2266 exit
= loop
->single_exit
;
2270 if (!number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2273 type
= TREE_TYPE (niter_desc
.niter
);
2274 if (integer_nonzerop (niter_desc
.may_be_zero
))
2275 res
= build_int_cst (type
, 0);
2276 else if (integer_zerop (niter_desc
.may_be_zero
))
2277 res
= niter_desc
.niter
;
2279 res
= chrec_dont_know
;
2282 return set_nb_iterations_in_loop (loop
, res
);
2285 /* One of the drivers for testing the scalar evolutions analysis.
2286 This function computes the number of iterations for all the loops
2287 from the EXIT_CONDITIONS array. */
2290 number_of_iterations_for_all_loops (VEC(tree
,heap
) **exit_conditions
)
2293 unsigned nb_chrec_dont_know_loops
= 0;
2294 unsigned nb_static_loops
= 0;
2297 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2299 tree res
= number_of_iterations_in_loop (loop_containing_stmt (cond
));
2300 if (chrec_contains_undetermined (res
))
2301 nb_chrec_dont_know_loops
++;
2308 fprintf (dump_file
, "\n(\n");
2309 fprintf (dump_file
, "-----------------------------------------\n");
2310 fprintf (dump_file
, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops
);
2311 fprintf (dump_file
, "%d\tnb_static_loops\n", nb_static_loops
);
2312 fprintf (dump_file
, "%d\tnb_total_loops\n", current_loops
->num
);
2313 fprintf (dump_file
, "-----------------------------------------\n");
2314 fprintf (dump_file
, ")\n\n");
2316 print_loop_ir (dump_file
);
2322 /* Counters for the stats. */
2328 unsigned nb_affine_multivar
;
2329 unsigned nb_higher_poly
;
2330 unsigned nb_chrec_dont_know
;
2331 unsigned nb_undetermined
;
2334 /* Reset the counters. */
2337 reset_chrecs_counters (struct chrec_stats
*stats
)
2339 stats
->nb_chrecs
= 0;
2340 stats
->nb_affine
= 0;
2341 stats
->nb_affine_multivar
= 0;
2342 stats
->nb_higher_poly
= 0;
2343 stats
->nb_chrec_dont_know
= 0;
2344 stats
->nb_undetermined
= 0;
2347 /* Dump the contents of a CHREC_STATS structure. */
2350 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2352 fprintf (file
, "\n(\n");
2353 fprintf (file
, "-----------------------------------------\n");
2354 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2355 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2356 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2357 stats
->nb_higher_poly
);
2358 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2359 fprintf (file
, "-----------------------------------------\n");
2360 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2361 fprintf (file
, "%d\twith undetermined coefficients\n",
2362 stats
->nb_undetermined
);
2363 fprintf (file
, "-----------------------------------------\n");
2364 fprintf (file
, "%d\tchrecs in the scev database\n",
2365 (int) htab_elements (scalar_evolution_info
));
2366 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2367 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2368 fprintf (file
, "-----------------------------------------\n");
2369 fprintf (file
, ")\n\n");
2372 /* Gather statistics about CHREC. */
2375 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2377 if (dump_file
&& (dump_flags
& TDF_STATS
))
2379 fprintf (dump_file
, "(classify_chrec ");
2380 print_generic_expr (dump_file
, chrec
, 0);
2381 fprintf (dump_file
, "\n");
2386 if (chrec
== NULL_TREE
)
2388 stats
->nb_undetermined
++;
2392 switch (TREE_CODE (chrec
))
2394 case POLYNOMIAL_CHREC
:
2395 if (evolution_function_is_affine_p (chrec
))
2397 if (dump_file
&& (dump_flags
& TDF_STATS
))
2398 fprintf (dump_file
, " affine_univariate\n");
2401 else if (evolution_function_is_affine_multivariate_p (chrec
))
2403 if (dump_file
&& (dump_flags
& TDF_STATS
))
2404 fprintf (dump_file
, " affine_multivariate\n");
2405 stats
->nb_affine_multivar
++;
2409 if (dump_file
&& (dump_flags
& TDF_STATS
))
2410 fprintf (dump_file
, " higher_degree_polynomial\n");
2411 stats
->nb_higher_poly
++;
2420 if (chrec_contains_undetermined (chrec
))
2422 if (dump_file
&& (dump_flags
& TDF_STATS
))
2423 fprintf (dump_file
, " undetermined\n");
2424 stats
->nb_undetermined
++;
2427 if (dump_file
&& (dump_flags
& TDF_STATS
))
2428 fprintf (dump_file
, ")\n");
2431 /* One of the drivers for testing the scalar evolutions analysis.
2432 This function analyzes the scalar evolution of all the scalars
2433 defined as loop phi nodes in one of the loops from the
2434 EXIT_CONDITIONS array.
2436 TODO Optimization: A loop is in canonical form if it contains only
2437 a single scalar loop phi node. All the other scalars that have an
2438 evolution in the loop are rewritten in function of this single
2439 index. This allows the parallelization of the loop. */
2442 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree
,heap
) **exit_conditions
)
2445 struct chrec_stats stats
;
2448 reset_chrecs_counters (&stats
);
2450 for (i
= 0; VEC_iterate (tree
, *exit_conditions
, i
, cond
); i
++)
2456 loop
= loop_containing_stmt (cond
);
2459 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2460 if (is_gimple_reg (PHI_RESULT (phi
)))
2462 chrec
= instantiate_parameters
2464 analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2466 if (dump_file
&& (dump_flags
& TDF_STATS
))
2467 gather_chrec_stats (chrec
, &stats
);
2471 if (dump_file
&& (dump_flags
& TDF_STATS
))
2472 dump_chrecs_stats (dump_file
, &stats
);
2475 /* Callback for htab_traverse, gathers information on chrecs in the
2479 gather_stats_on_scev_database_1 (void **slot
, void *stats
)
2481 struct scev_info_str
*entry
= (struct scev_info_str
*) *slot
;
2483 gather_chrec_stats (entry
->chrec
, (struct chrec_stats
*) stats
);
2488 /* Classify the chrecs of the whole database. */
2491 gather_stats_on_scev_database (void)
2493 struct chrec_stats stats
;
2498 reset_chrecs_counters (&stats
);
2500 htab_traverse (scalar_evolution_info
, gather_stats_on_scev_database_1
,
2503 dump_chrecs_stats (dump_file
, &stats
);
2511 initialize_scalar_evolutions_analyzer (void)
2513 /* The elements below are unique. */
2514 if (chrec_dont_know
== NULL_TREE
)
2516 chrec_not_analyzed_yet
= NULL_TREE
;
2517 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
2518 chrec_known
= make_node (SCEV_KNOWN
);
2519 TREE_TYPE (chrec_dont_know
) = void_type_node
;
2520 TREE_TYPE (chrec_known
) = void_type_node
;
2524 /* Initialize the analysis of scalar evolutions for LOOPS. */
2527 scev_initialize (struct loops
*loops
)
2530 current_loops
= loops
;
2532 scalar_evolution_info
= htab_create (100, hash_scev_info
,
2533 eq_scev_info
, del_scev_info
);
2534 already_instantiated
= BITMAP_ALLOC (NULL
);
2536 initialize_scalar_evolutions_analyzer ();
2538 for (i
= 1; i
< loops
->num
; i
++)
2539 if (loops
->parray
[i
])
2540 loops
->parray
[i
]->nb_iterations
= NULL_TREE
;
2543 /* Cleans up the information cached by the scalar evolutions analysis. */
2551 if (!scalar_evolution_info
|| !current_loops
)
2554 htab_empty (scalar_evolution_info
);
2555 for (i
= 1; i
< current_loops
->num
; i
++)
2557 loop
= current_loops
->parray
[i
];
2559 loop
->nb_iterations
= NULL_TREE
;
2563 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2564 its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
2565 want STEP to be invariant in LOOP. Otherwise we require it to be an
2566 integer constant. */
2569 simple_iv (struct loop
*loop
, tree stmt
, tree op
, tree
*base
, tree
*step
,
2570 bool allow_nonconstant_step
)
2572 basic_block bb
= bb_for_stmt (stmt
);
2578 type
= TREE_TYPE (op
);
2579 if (TREE_CODE (type
) != INTEGER_TYPE
2580 && TREE_CODE (type
) != POINTER_TYPE
)
2583 ev
= analyze_scalar_evolution_in_loop (loop
, bb
->loop_father
, op
);
2584 if (chrec_contains_undetermined (ev
))
2587 if (tree_does_not_contain_chrecs (ev
)
2588 && !chrec_contains_symbols_defined_in_loop (ev
, loop
->num
))
2594 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
2595 || CHREC_VARIABLE (ev
) != (unsigned) loop
->num
)
2598 *step
= CHREC_RIGHT (ev
);
2599 if (allow_nonconstant_step
)
2601 if (tree_contains_chrecs (*step
, NULL
)
2602 || chrec_contains_symbols_defined_in_loop (*step
, loop
->num
))
2605 else if (TREE_CODE (*step
) != INTEGER_CST
)
2608 *base
= CHREC_LEFT (ev
);
2609 if (tree_contains_chrecs (*base
, NULL
)
2610 || chrec_contains_symbols_defined_in_loop (*base
, loop
->num
))
2616 /* Runs the analysis of scalar evolutions. */
2619 scev_analysis (void)
2621 VEC(tree
,heap
) *exit_conditions
;
2623 exit_conditions
= VEC_alloc (tree
, heap
, 37);
2624 select_loops_exit_conditions (current_loops
, &exit_conditions
);
2626 if (dump_file
&& (dump_flags
& TDF_STATS
))
2627 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions
);
2629 number_of_iterations_for_all_loops (&exit_conditions
);
2630 VEC_free (tree
, heap
, exit_conditions
);
2633 /* Finalize the scalar evolution analysis. */
2636 scev_finalize (void)
2638 htab_delete (scalar_evolution_info
);
2639 BITMAP_FREE (already_instantiated
);
2642 /* Returns true if EXPR looks expensive. */
2645 expression_expensive_p (tree expr
)
2647 return force_expr_to_var_cost (expr
) >= target_spill_cost
;
2650 /* Replace ssa names for that scev can prove they are constant by the
2651 appropriate constants. Also perform final value replacement in loops,
2652 in case the replacement expressions are cheap.
2654 We only consider SSA names defined by phi nodes; rest is left to the
2655 ordinary constant propagation pass. */
2658 scev_const_prop (void)
2661 tree name
, phi
, next_phi
, type
, ev
;
2662 struct loop
*loop
, *ex_loop
;
2663 bitmap ssa_names_to_remove
= NULL
;
2671 loop
= bb
->loop_father
;
2673 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2675 name
= PHI_RESULT (phi
);
2677 if (!is_gimple_reg (name
))
2680 type
= TREE_TYPE (name
);
2682 if (!POINTER_TYPE_P (type
)
2683 && !INTEGRAL_TYPE_P (type
))
2686 ev
= resolve_mixers (loop
, analyze_scalar_evolution (loop
, name
));
2687 if (!is_gimple_min_invariant (ev
)
2688 || !may_propagate_copy (name
, ev
))
2691 /* Replace the uses of the name. */
2693 replace_uses_by (name
, ev
);
2695 if (!ssa_names_to_remove
)
2696 ssa_names_to_remove
= BITMAP_ALLOC (NULL
);
2697 bitmap_set_bit (ssa_names_to_remove
, SSA_NAME_VERSION (name
));
2701 /* Remove the ssa names that were replaced by constants. We do not remove them
2702 directly in the previous cycle, since this invalidates scev cache. */
2703 if (ssa_names_to_remove
)
2708 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove
, 0, i
, bi
)
2710 name
= ssa_name (i
);
2711 phi
= SSA_NAME_DEF_STMT (name
);
2713 gcc_assert (TREE_CODE (phi
) == PHI_NODE
);
2714 remove_phi_node (phi
, NULL
);
2717 BITMAP_FREE (ssa_names_to_remove
);
2721 /* Now the regular final value replacement. */
2722 for (i
= current_loops
->num
- 1; i
> 0; i
--)
2725 tree def
, rslt
, ass
;
2726 block_stmt_iterator bsi
;
2728 loop
= current_loops
->parray
[i
];
2732 /* If we do not know exact number of iterations of the loop, we cannot
2733 replace the final value. */
2734 exit
= loop
->single_exit
;
2736 || number_of_iterations_in_loop (loop
) == chrec_dont_know
)
2739 /* Ensure that it is possible to insert new statements somewhere. */
2740 if (!single_pred_p (exit
->dest
))
2741 split_loop_exit_edge (exit
);
2742 tree_block_label (exit
->dest
);
2743 bsi
= bsi_after_labels (exit
->dest
);
2745 ex_loop
= superloop_at_depth (loop
, exit
->dest
->loop_father
->depth
+ 1);
2747 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= next_phi
)
2749 next_phi
= PHI_CHAIN (phi
);
2750 rslt
= PHI_RESULT (phi
);
2751 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2752 if (!is_gimple_reg (def
))
2755 if (!POINTER_TYPE_P (TREE_TYPE (def
))
2756 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
2759 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
);
2760 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
2761 if (!tree_does_not_contain_chrecs (def
)
2762 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
))
2765 /* If computing the expression is expensive, let it remain in the
2767 if (expression_expensive_p (def
))
2770 /* Eliminate the phi node and replace it by a computation outside
2772 def
= unshare_expr (def
);
2773 SET_PHI_RESULT (phi
, NULL_TREE
);
2774 remove_phi_node (phi
, NULL_TREE
);
2776 ass
= build2 (MODIFY_EXPR
, void_type_node
, rslt
, NULL_TREE
);
2777 SSA_NAME_DEF_STMT (rslt
) = ass
;
2778 bsi_insert_after (&bsi
, ass
, BSI_NEW_STMT
);
2779 def
= force_gimple_operand_bsi (&bsi
, def
, false, NULL_TREE
);
2780 TREE_OPERAND (ass
, 1) = def
;