1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <s.pop@laposte.net>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 This pass analyzes the evolution of scalar variables in loop
26 structures. The algorithm is based on the SSA representation,
27 and on the loop hierarchy tree. This algorithm is not based on
28 the notion of versions of a variable, as it was the case for the
29 previous implementations of the scalar evolution algorithm, but
30 it assumes that each defined name is unique.
32 The notation used in this file is called "chains of recurrences",
33 and has been proposed by Eugene Zima, Robert Van Engelen, and
34 others for describing induction variables in programs. For example
35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36 when entering in the loop_1 and has a step 2 in this loop, in other
37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38 this chain of recurrence (or chrec [shrek]) can contain the name of
39 other variables, in which case they are called parametric chrecs.
40 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41 is the value of "a". In most of the cases these parametric chrecs
42 are fully instantiated before their use because symbolic names can
43 hide some difficult cases such as self-references described later
44 (see the Fibonacci example).
46 A short sketch of the algorithm is:
48 Given a scalar variable to be analyzed, follow the SSA edge to
51 - When the definition is a GIMPLE_ASSIGN: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2a: Illustration of the algorithm on nested loops.
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
158 Example 2b: Multivariate chains of recurrences.
171 Analyzing the access function of array A with
172 instantiate_parameters (loop_1, "j + k"), we obtain the
173 instantiation and the analysis of the scalar variables "j" and "k"
174 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
175 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
176 {0, +, 1}_1. To obtain the evolution function in loop_3 and
177 instantiate the scalar variables up to loop_1, one has to use:
178 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
179 The result of this call is {{0, +, 1}_1, +, 1}_2.
181 Example 3: Higher degree polynomials.
195 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
196 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
198 Example 4: Lucas, Fibonacci, or mixers in general.
210 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
211 following semantics: during the first iteration of the loop_1, the
212 variable contains the value 1, and then it contains the value "c".
213 Note that this syntax is close to the syntax of the loop-phi-node:
214 "a -> (1, c)_1" vs. "a = phi (1, c)".
216 The symbolic chrec representation contains all the semantics of the
217 original code. What is more difficult is to use this information.
219 Example 5: Flip-flops, or exchangers.
231 Based on these symbolic chrecs, it is possible to refine this
232 information into the more precise PERIODIC_CHRECs:
237 This transformation is not yet implemented.
241 You can find a more detailed description of the algorithm in:
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
243 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
244 this is a preliminary report and some of the details of the
245 algorithm have changed. I'm working on a research report that
246 updates the description of the algorithms to reflect the design
247 choices used in this implementation.
249 A set of slides show a high level overview of the algorithm and run
250 an example through the scalar evolution analyzer:
251 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
253 The slides that I have presented at the GCC Summit'04 are available
254 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
259 #include "coretypes.h"
263 #include "basic-block.h"
264 #include "tree-pretty-print.h"
265 #include "gimple-pretty-print.h"
266 #include "tree-flow.h"
267 #include "tree-dump.h"
270 #include "tree-chrec.h"
271 #include "tree-scalar-evolution.h"
272 #include "tree-pass.h"
276 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
278 /* The cached information about an SSA name VAR, claiming that below
279 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
282 struct GTY(()) scev_info_str {
283 basic_block instantiated_below;
288 /* Counters for the scev database. */
289 static unsigned nb_set_scev = 0;
290 static unsigned nb_get_scev = 0;
292 /* The following trees are unique elements. Thus the comparison of
293 another element to these elements should be done on the pointer to
294 these trees, and not on their value. */
296 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
297 tree chrec_not_analyzed_yet;
299 /* Reserved to the cases where the analyzer has detected an
300 undecidable property at compile time. */
301 tree chrec_dont_know;
303 /* When the analyzer has detected that a property will never
304 happen, then it qualifies it with chrec_known. */
307 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
310 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
312 static inline struct scev_info_str *
313 new_scev_info_str (basic_block instantiated_below, tree var)
315 struct scev_info_str *res;
317 res = ggc_alloc_scev_info_str ();
319 res->chrec = chrec_not_analyzed_yet;
320 res->instantiated_below = instantiated_below;
325 /* Computes a hash function for database element ELT. */
328 hash_scev_info (const void *elt)
330 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
333 /* Compares database elements E1 and E2. */
336 eq_scev_info (const void *e1, const void *e2)
338 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
339 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
341 return (elt1->var == elt2->var
342 && elt1->instantiated_below == elt2->instantiated_below);
345 /* Deletes database element E. */
348 del_scev_info (void *e)
353 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
354 A first query on VAR returns chrec_not_analyzed_yet. */
357 find_var_scev_info (basic_block instantiated_below, tree var)
359 struct scev_info_str *res;
360 struct scev_info_str tmp;
364 tmp.instantiated_below = instantiated_below;
365 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
368 *slot = new_scev_info_str (instantiated_below, var);
369 res = (struct scev_info_str *) *slot;
374 /* Return true when CHREC contains symbolic names defined in
378 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
382 if (chrec == NULL_TREE)
385 if (is_gimple_min_invariant (chrec))
388 if (TREE_CODE (chrec) == VAR_DECL
389 || TREE_CODE (chrec) == PARM_DECL
390 || TREE_CODE (chrec) == FUNCTION_DECL
391 || TREE_CODE (chrec) == LABEL_DECL
392 || TREE_CODE (chrec) == RESULT_DECL
393 || TREE_CODE (chrec) == FIELD_DECL)
396 if (TREE_CODE (chrec) == SSA_NAME)
398 gimple def = SSA_NAME_DEF_STMT (chrec);
399 struct loop *def_loop = loop_containing_stmt (def);
400 struct loop *loop = get_loop (loop_nb);
402 if (def_loop == NULL)
405 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
411 n = TREE_OPERAND_LENGTH (chrec);
412 for (i = 0; i < n; i++)
413 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
419 /* Return true when PHI is a loop-phi-node. */
422 loop_phi_node_p (gimple phi)
424 /* The implementation of this function is based on the following
425 property: "all the loop-phi-nodes of a loop are contained in the
426 loop's header basic block". */
428 return loop_containing_stmt (phi)->header == gimple_bb (phi);
431 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
432 In general, in the case of multivariate evolutions we want to get
433 the evolution in different loops. LOOP specifies the level for
434 which to get the evolution.
438 | for (j = 0; j < 100; j++)
440 | for (k = 0; k < 100; k++)
442 | i = k + j; - Here the value of i is a function of j, k.
444 | ... = i - Here the value of i is a function of j.
446 | ... = i - Here the value of i is a scalar.
452 | i_1 = phi (i_0, i_2)
456 This loop has the same effect as:
457 LOOP_1 has the same effect as:
461 The overall effect of the loop, "i_0 + 20" in the previous example,
462 is obtained by passing in the parameters: LOOP = 1,
463 EVOLUTION_FN = {i_0, +, 2}_1.
467 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
471 if (evolution_fn == chrec_dont_know)
472 return chrec_dont_know;
474 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
476 struct loop *inner_loop = get_chrec_loop (evolution_fn);
478 if (inner_loop == loop
479 || flow_loop_nested_p (loop, inner_loop))
481 tree nb_iter = number_of_latch_executions (inner_loop);
483 if (nb_iter == chrec_dont_know)
484 return chrec_dont_know;
489 /* evolution_fn is the evolution function in LOOP. Get
490 its value in the nb_iter-th iteration. */
491 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
493 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
494 res = instantiate_parameters (loop, res);
496 /* Continue the computation until ending on a parent of LOOP. */
497 return compute_overall_effect_of_inner_loop (loop, res);
504 /* If the evolution function is an invariant, there is nothing to do. */
505 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
509 return chrec_dont_know;
512 /* Determine whether the CHREC is always positive/negative. If the expression
513 cannot be statically analyzed, return false, otherwise set the answer into
517 chrec_is_positive (tree chrec, bool *value)
519 bool value0, value1, value2;
520 tree end_value, nb_iter;
522 switch (TREE_CODE (chrec))
524 case POLYNOMIAL_CHREC:
525 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
526 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
529 /* FIXME -- overflows. */
530 if (value0 == value1)
536 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
537 and the proof consists in showing that the sign never
538 changes during the execution of the loop, from 0 to
539 loop->nb_iterations. */
540 if (!evolution_function_is_affine_p (chrec))
543 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
544 if (chrec_contains_undetermined (nb_iter))
548 /* TODO -- If the test is after the exit, we may decrease the number of
549 iterations by one. */
551 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
554 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
556 if (!chrec_is_positive (end_value, &value2))
560 return value0 == value1;
563 *value = (tree_int_cst_sgn (chrec) == 1);
571 /* Associate CHREC to SCALAR. */
574 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
578 if (TREE_CODE (scalar) != SSA_NAME)
581 scalar_info = find_var_scev_info (instantiated_below, scalar);
585 if (dump_flags & TDF_DETAILS)
587 fprintf (dump_file, "(set_scalar_evolution \n");
588 fprintf (dump_file, " instantiated_below = %d \n",
589 instantiated_below->index);
590 fprintf (dump_file, " (scalar = ");
591 print_generic_expr (dump_file, scalar, 0);
592 fprintf (dump_file, ")\n (scalar_evolution = ");
593 print_generic_expr (dump_file, chrec, 0);
594 fprintf (dump_file, "))\n");
596 if (dump_flags & TDF_STATS)
600 *scalar_info = chrec;
603 /* Retrieve the chrec associated to SCALAR instantiated below
604 INSTANTIATED_BELOW block. */
607 get_scalar_evolution (basic_block instantiated_below, tree scalar)
613 if (dump_flags & TDF_DETAILS)
615 fprintf (dump_file, "(get_scalar_evolution \n");
616 fprintf (dump_file, " (scalar = ");
617 print_generic_expr (dump_file, scalar, 0);
618 fprintf (dump_file, ")\n");
620 if (dump_flags & TDF_STATS)
624 switch (TREE_CODE (scalar))
627 res = *find_var_scev_info (instantiated_below, scalar);
637 res = chrec_not_analyzed_yet;
641 if (dump_file && (dump_flags & TDF_DETAILS))
643 fprintf (dump_file, " (scalar_evolution = ");
644 print_generic_expr (dump_file, res, 0);
645 fprintf (dump_file, "))\n");
651 /* Helper function for add_to_evolution. Returns the evolution
652 function for an assignment of the form "a = b + c", where "a" and
653 "b" are on the strongly connected component. CHREC_BEFORE is the
654 information that we already have collected up to this point.
655 TO_ADD is the evolution of "c".
657 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
658 evolution the expression TO_ADD, otherwise construct an evolution
659 part for this loop. */
662 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
665 tree type, left, right;
666 struct loop *loop = get_loop (loop_nb), *chloop;
668 switch (TREE_CODE (chrec_before))
670 case POLYNOMIAL_CHREC:
671 chloop = get_chrec_loop (chrec_before);
673 || flow_loop_nested_p (chloop, loop))
677 type = chrec_type (chrec_before);
679 /* When there is no evolution part in this loop, build it. */
684 right = SCALAR_FLOAT_TYPE_P (type)
685 ? build_real (type, dconst0)
686 : build_int_cst (type, 0);
690 var = CHREC_VARIABLE (chrec_before);
691 left = CHREC_LEFT (chrec_before);
692 right = CHREC_RIGHT (chrec_before);
695 to_add = chrec_convert (type, to_add, at_stmt);
696 right = chrec_convert_rhs (type, right, at_stmt);
697 right = chrec_fold_plus (chrec_type (right), right, to_add);
698 return build_polynomial_chrec (var, left, right);
702 gcc_assert (flow_loop_nested_p (loop, chloop));
704 /* Search the evolution in LOOP_NB. */
705 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
707 right = CHREC_RIGHT (chrec_before);
708 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
709 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
714 /* These nodes do not depend on a loop. */
715 if (chrec_before == chrec_dont_know)
716 return chrec_dont_know;
719 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
720 return build_polynomial_chrec (loop_nb, left, right);
724 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
727 Description (provided for completeness, for those who read code in
728 a plane, and for my poor 62 bytes brain that would have forgotten
729 all this in the next two or three months):
731 The algorithm of translation of programs from the SSA representation
732 into the chrecs syntax is based on a pattern matching. After having
733 reconstructed the overall tree expression for a loop, there are only
734 two cases that can arise:
736 1. a = loop-phi (init, a + expr)
737 2. a = loop-phi (init, expr)
739 where EXPR is either a scalar constant with respect to the analyzed
740 loop (this is a degree 0 polynomial), or an expression containing
741 other loop-phi definitions (these are higher degree polynomials).
748 | a = phi (init, a + 5)
755 | a = phi (inita, 2 * b + 3)
756 | b = phi (initb, b + 1)
759 For the first case, the semantics of the SSA representation is:
761 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
763 that is, there is a loop index "x" that determines the scalar value
764 of the variable during the loop execution. During the first
765 iteration, the value is that of the initial condition INIT, while
766 during the subsequent iterations, it is the sum of the initial
767 condition with the sum of all the values of EXPR from the initial
768 iteration to the before last considered iteration.
770 For the second case, the semantics of the SSA program is:
772 | a (x) = init, if x = 0;
773 | expr (x - 1), otherwise.
775 The second case corresponds to the PEELED_CHREC, whose syntax is
776 close to the syntax of a loop-phi-node:
778 | phi (init, expr) vs. (init, expr)_x
780 The proof of the translation algorithm for the first case is a
781 proof by structural induction based on the degree of EXPR.
784 When EXPR is a constant with respect to the analyzed loop, or in
785 other words when EXPR is a polynomial of degree 0, the evolution of
786 the variable A in the loop is an affine function with an initial
787 condition INIT, and a step EXPR. In order to show this, we start
788 from the semantics of the SSA representation:
790 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
792 and since "expr (j)" is a constant with respect to "j",
794 f (x) = init + x * expr
796 Finally, based on the semantics of the pure sum chrecs, by
797 identification we get the corresponding chrecs syntax:
799 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
800 f (x) -> {init, +, expr}_x
803 Suppose that EXPR is a polynomial of degree N with respect to the
804 analyzed loop_x for which we have already determined that it is
805 written under the chrecs syntax:
807 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
809 We start from the semantics of the SSA program:
811 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
813 | f (x) = init + \sum_{j = 0}^{x - 1}
814 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
816 | f (x) = init + \sum_{j = 0}^{x - 1}
817 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
819 | f (x) = init + \sum_{k = 0}^{n - 1}
820 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
822 | f (x) = init + \sum_{k = 0}^{n - 1}
823 | (b_k * \binom{x}{k + 1})
825 | f (x) = init + b_0 * \binom{x}{1} + ...
826 | + b_{n-1} * \binom{x}{n}
828 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
829 | + b_{n-1} * \binom{x}{n}
832 And finally from the definition of the chrecs syntax, we identify:
833 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
835 This shows the mechanism that stands behind the add_to_evolution
836 function. An important point is that the use of symbolic
837 parameters avoids the need of an analysis schedule.
844 | a = phi (inita, a + 2 + b)
845 | b = phi (initb, b + 1)
848 When analyzing "a", the algorithm keeps "b" symbolically:
850 | a -> {inita, +, 2 + b}_1
852 Then, after instantiation, the analyzer ends on the evolution:
854 | a -> {inita, +, 2 + initb, +, 1}_1
859 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
860 tree to_add, gimple at_stmt)
862 tree type = chrec_type (to_add);
863 tree res = NULL_TREE;
865 if (to_add == NULL_TREE)
868 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
869 instantiated at this point. */
870 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
871 /* This should not happen. */
872 return chrec_dont_know;
874 if (dump_file && (dump_flags & TDF_DETAILS))
876 fprintf (dump_file, "(add_to_evolution \n");
877 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
878 fprintf (dump_file, " (chrec_before = ");
879 print_generic_expr (dump_file, chrec_before, 0);
880 fprintf (dump_file, ")\n (to_add = ");
881 print_generic_expr (dump_file, to_add, 0);
882 fprintf (dump_file, ")\n");
885 if (code == MINUS_EXPR)
886 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
887 ? build_real (type, dconstm1)
888 : build_int_cst_type (type, -1));
890 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
892 if (dump_file && (dump_flags & TDF_DETAILS))
894 fprintf (dump_file, " (res = ");
895 print_generic_expr (dump_file, res, 0);
896 fprintf (dump_file, "))\n");
904 /* This section selects the loops that will be good candidates for the
905 scalar evolution analysis. For the moment, greedily select all the
906 loop nests we could analyze. */
908 /* For a loop with a single exit edge, return the COND_EXPR that
909 guards the exit edge. If the expression is too difficult to
910 analyze, then give up. */
913 get_loop_exit_condition (const struct loop *loop)
916 edge exit_edge = single_exit (loop);
918 if (dump_file && (dump_flags & TDF_DETAILS))
919 fprintf (dump_file, "(get_loop_exit_condition \n ");
925 stmt = last_stmt (exit_edge->src);
926 if (gimple_code (stmt) == GIMPLE_COND)
930 if (dump_file && (dump_flags & TDF_DETAILS))
932 print_gimple_stmt (dump_file, res, 0, 0);
933 fprintf (dump_file, ")\n");
939 /* Recursively determine and enqueue the exit conditions for a loop. */
942 get_exit_conditions_rec (struct loop *loop,
943 VEC(gimple,heap) **exit_conditions)
948 /* Recurse on the inner loops, then on the next (sibling) loops. */
949 get_exit_conditions_rec (loop->inner, exit_conditions);
950 get_exit_conditions_rec (loop->next, exit_conditions);
952 if (single_exit (loop))
954 gimple loop_condition = get_loop_exit_condition (loop);
957 VEC_safe_push (gimple, heap, *exit_conditions, loop_condition);
961 /* Select the candidate loop nests for the analysis. This function
962 initializes the EXIT_CONDITIONS array. */
965 select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions)
967 struct loop *function_body = current_loops->tree_root;
969 get_exit_conditions_rec (function_body->inner, exit_conditions);
973 /* Depth first search algorithm. */
975 typedef enum t_bool {
982 static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
984 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
985 Return true if the strongly connected component has been found. */
988 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
989 tree type, tree rhs0, enum tree_code code, tree rhs1,
990 gimple halting_phi, tree *evolution_of_loop, int limit)
992 t_bool res = t_false;
997 case POINTER_PLUS_EXPR:
999 if (TREE_CODE (rhs0) == SSA_NAME)
1001 if (TREE_CODE (rhs1) == SSA_NAME)
1003 /* Match an assignment under the form:
1006 /* We want only assignments of form "name + name" contribute to
1007 LIMIT, as the other cases do not necessarily contribute to
1008 the complexity of the expression. */
1011 evol = *evolution_of_loop;
1012 res = follow_ssa_edge
1013 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
1016 *evolution_of_loop = add_to_evolution
1018 chrec_convert (type, evol, at_stmt),
1019 code, rhs1, at_stmt);
1021 else if (res == t_false)
1023 res = follow_ssa_edge
1024 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1025 evolution_of_loop, limit);
1028 *evolution_of_loop = add_to_evolution
1030 chrec_convert (type, *evolution_of_loop, at_stmt),
1031 code, rhs0, at_stmt);
1033 else if (res == t_dont_know)
1034 *evolution_of_loop = chrec_dont_know;
1037 else if (res == t_dont_know)
1038 *evolution_of_loop = chrec_dont_know;
1043 /* Match an assignment under the form:
1045 res = follow_ssa_edge
1046 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1047 evolution_of_loop, limit);
1049 *evolution_of_loop = add_to_evolution
1050 (loop->num, chrec_convert (type, *evolution_of_loop,
1052 code, rhs1, at_stmt);
1054 else if (res == t_dont_know)
1055 *evolution_of_loop = chrec_dont_know;
1059 else if (TREE_CODE (rhs1) == SSA_NAME)
1061 /* Match an assignment under the form:
1063 res = follow_ssa_edge
1064 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1065 evolution_of_loop, limit);
1067 *evolution_of_loop = add_to_evolution
1068 (loop->num, chrec_convert (type, *evolution_of_loop,
1070 code, rhs0, at_stmt);
1072 else if (res == t_dont_know)
1073 *evolution_of_loop = chrec_dont_know;
1077 /* Otherwise, match an assignment under the form:
1079 /* And there is nothing to do. */
1084 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1085 if (TREE_CODE (rhs0) == SSA_NAME)
1087 /* Match an assignment under the form:
1090 /* We want only assignments of form "name - name" contribute to
1091 LIMIT, as the other cases do not necessarily contribute to
1092 the complexity of the expression. */
1093 if (TREE_CODE (rhs1) == SSA_NAME)
1096 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1097 evolution_of_loop, limit);
1099 *evolution_of_loop = add_to_evolution
1100 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1101 MINUS_EXPR, rhs1, at_stmt);
1103 else if (res == t_dont_know)
1104 *evolution_of_loop = chrec_dont_know;
1107 /* Otherwise, match an assignment under the form:
1109 /* And there is nothing to do. */
1120 /* Follow the ssa edge into the expression EXPR.
1121 Return true if the strongly connected component has been found. */
1124 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1125 gimple halting_phi, tree *evolution_of_loop, int limit)
1127 enum tree_code code = TREE_CODE (expr);
1128 tree type = TREE_TYPE (expr), rhs0, rhs1;
1131 /* The EXPR is one of the following cases:
1135 - a POINTER_PLUS_EXPR,
1138 - other cases are not yet handled. */
1143 /* This assignment is under the form "a_1 = (cast) rhs. */
1144 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1145 halting_phi, evolution_of_loop, limit);
1146 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1150 /* This assignment is under the form "a_1 = 7". */
1155 /* This assignment is under the form: "a_1 = b_2". */
1156 res = follow_ssa_edge
1157 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1160 case POINTER_PLUS_EXPR:
1163 /* This case is under the form "rhs0 +- rhs1". */
1164 rhs0 = TREE_OPERAND (expr, 0);
1165 rhs1 = TREE_OPERAND (expr, 1);
1166 type = TREE_TYPE (rhs0);
1167 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1168 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1169 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1170 halting_phi, evolution_of_loop, limit);
1174 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1175 It must be handled as a copy assignment of the form a_1 = a_2. */
1176 rhs0 = ASSERT_EXPR_VAR (expr);
1177 if (TREE_CODE (rhs0) == SSA_NAME)
1178 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1179 halting_phi, evolution_of_loop, limit);
1192 /* Follow the ssa edge into the right hand side of an assignment STMT.
1193 Return true if the strongly connected component has been found. */
1196 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1197 gimple halting_phi, tree *evolution_of_loop, int limit)
1199 enum tree_code code = gimple_assign_rhs_code (stmt);
1200 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1206 /* This assignment is under the form "a_1 = (cast) rhs. */
1207 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1208 halting_phi, evolution_of_loop, limit);
1209 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1212 case POINTER_PLUS_EXPR:
1215 rhs1 = gimple_assign_rhs1 (stmt);
1216 rhs2 = gimple_assign_rhs2 (stmt);
1217 type = TREE_TYPE (rhs1);
1218 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1219 halting_phi, evolution_of_loop, limit);
1223 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1224 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1225 halting_phi, evolution_of_loop, limit);
1234 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1237 backedge_phi_arg_p (gimple phi, int i)
1239 const_edge e = gimple_phi_arg_edge (phi, i);
1241 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1242 about updating it anywhere, and this should work as well most of the
1244 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1250 /* Helper function for one branch of the condition-phi-node. Return
1251 true if the strongly connected component has been found following
1254 static inline t_bool
1255 follow_ssa_edge_in_condition_phi_branch (int i,
1257 gimple condition_phi,
1259 tree *evolution_of_branch,
1260 tree init_cond, int limit)
1262 tree branch = PHI_ARG_DEF (condition_phi, i);
1263 *evolution_of_branch = chrec_dont_know;
1265 /* Do not follow back edges (they must belong to an irreducible loop, which
1266 we really do not want to worry about). */
1267 if (backedge_phi_arg_p (condition_phi, i))
1270 if (TREE_CODE (branch) == SSA_NAME)
1272 *evolution_of_branch = init_cond;
1273 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1274 evolution_of_branch, limit);
1277 /* This case occurs when one of the condition branches sets
1278 the variable to a constant: i.e. a phi-node like
1279 "a_2 = PHI <a_7(5), 2(6)>;".
1281 FIXME: This case have to be refined correctly:
1282 in some cases it is possible to say something better than
1283 chrec_dont_know, for example using a wrap-around notation. */
1287 /* This function merges the branches of a condition-phi-node in a
1291 follow_ssa_edge_in_condition_phi (struct loop *loop,
1292 gimple condition_phi,
1294 tree *evolution_of_loop, int limit)
1297 tree init = *evolution_of_loop;
1298 tree evolution_of_branch;
1299 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1301 &evolution_of_branch,
1303 if (res == t_false || res == t_dont_know)
1306 *evolution_of_loop = evolution_of_branch;
1308 n = gimple_phi_num_args (condition_phi);
1309 for (i = 1; i < n; i++)
1311 /* Quickly give up when the evolution of one of the branches is
1313 if (*evolution_of_loop == chrec_dont_know)
1316 /* Increase the limit by the PHI argument number to avoid exponential
1317 time and memory complexity. */
1318 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1320 &evolution_of_branch,
1322 if (res == t_false || res == t_dont_know)
1325 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1326 evolution_of_branch);
1332 /* Follow an SSA edge in an inner loop. It computes the overall
1333 effect of the loop, and following the symbolic initial conditions,
1334 it follows the edges in the parent loop. The inner loop is
1335 considered as a single statement. */
1338 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1339 gimple loop_phi_node,
1341 tree *evolution_of_loop, int limit)
1343 struct loop *loop = loop_containing_stmt (loop_phi_node);
1344 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1346 /* Sometimes, the inner loop is too difficult to analyze, and the
1347 result of the analysis is a symbolic parameter. */
1348 if (ev == PHI_RESULT (loop_phi_node))
1350 t_bool res = t_false;
1351 int i, n = gimple_phi_num_args (loop_phi_node);
1353 for (i = 0; i < n; i++)
1355 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1358 /* Follow the edges that exit the inner loop. */
1359 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1360 if (!flow_bb_inside_loop_p (loop, bb))
1361 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1363 evolution_of_loop, limit);
1368 /* If the path crosses this loop-phi, give up. */
1370 *evolution_of_loop = chrec_dont_know;
1375 /* Otherwise, compute the overall effect of the inner loop. */
1376 ev = compute_overall_effect_of_inner_loop (loop, ev);
1377 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1378 evolution_of_loop, limit);
1381 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1382 path that is analyzed on the return walk. */
1385 follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
1386 tree *evolution_of_loop, int limit)
1388 struct loop *def_loop;
1390 if (gimple_nop_p (def))
1393 /* Give up if the path is longer than the MAX that we allow. */
1394 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1397 def_loop = loop_containing_stmt (def);
1399 switch (gimple_code (def))
1402 if (!loop_phi_node_p (def))
1403 /* DEF is a condition-phi-node. Follow the branches, and
1404 record their evolutions. Finally, merge the collected
1405 information and set the approximation to the main
1407 return follow_ssa_edge_in_condition_phi
1408 (loop, def, halting_phi, evolution_of_loop, limit);
1410 /* When the analyzed phi is the halting_phi, the
1411 depth-first search is over: we have found a path from
1412 the halting_phi to itself in the loop. */
1413 if (def == halting_phi)
1416 /* Otherwise, the evolution of the HALTING_PHI depends
1417 on the evolution of another loop-phi-node, i.e. the
1418 evolution function is a higher degree polynomial. */
1419 if (def_loop == loop)
1423 if (flow_loop_nested_p (loop, def_loop))
1424 return follow_ssa_edge_inner_loop_phi
1425 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1431 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1432 evolution_of_loop, limit);
1435 /* At this level of abstraction, the program is just a set
1436 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1437 other node to be handled. */
1444 /* Given a LOOP_PHI_NODE, this function determines the evolution
1445 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1448 analyze_evolution_in_loop (gimple loop_phi_node,
1451 int i, n = gimple_phi_num_args (loop_phi_node);
1452 tree evolution_function = chrec_not_analyzed_yet;
1453 struct loop *loop = loop_containing_stmt (loop_phi_node);
1456 if (dump_file && (dump_flags & TDF_DETAILS))
1458 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1459 fprintf (dump_file, " (loop_phi_node = ");
1460 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1461 fprintf (dump_file, ")\n");
1464 for (i = 0; i < n; i++)
1466 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1471 /* Select the edges that enter the loop body. */
1472 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1473 if (!flow_bb_inside_loop_p (loop, bb))
1476 if (TREE_CODE (arg) == SSA_NAME)
1480 ssa_chain = SSA_NAME_DEF_STMT (arg);
1482 /* Pass in the initial condition to the follow edge function. */
1484 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1486 /* If ev_fn has no evolution in the inner loop, and the
1487 init_cond is not equal to ev_fn, then we have an
1488 ambiguity between two possible values, as we cannot know
1489 the number of iterations at this point. */
1490 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1491 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1492 && !operand_equal_p (init_cond, ev_fn, 0))
1493 ev_fn = chrec_dont_know;
1498 /* When it is impossible to go back on the same
1499 loop_phi_node by following the ssa edges, the
1500 evolution is represented by a peeled chrec, i.e. the
1501 first iteration, EV_FN has the value INIT_COND, then
1502 all the other iterations it has the value of ARG.
1503 For the moment, PEELED_CHREC nodes are not built. */
1505 ev_fn = chrec_dont_know;
1507 /* When there are multiple back edges of the loop (which in fact never
1508 happens currently, but nevertheless), merge their evolutions. */
1509 evolution_function = chrec_merge (evolution_function, ev_fn);
1512 if (dump_file && (dump_flags & TDF_DETAILS))
1514 fprintf (dump_file, " (evolution_function = ");
1515 print_generic_expr (dump_file, evolution_function, 0);
1516 fprintf (dump_file, "))\n");
1519 return evolution_function;
1522 /* Given a loop-phi-node, return the initial conditions of the
1523 variable on entry of the loop. When the CCP has propagated
1524 constants into the loop-phi-node, the initial condition is
1525 instantiated, otherwise the initial condition is kept symbolic.
1526 This analyzer does not analyze the evolution outside the current
1527 loop, and leaves this task to the on-demand tree reconstructor. */
1530 analyze_initial_condition (gimple loop_phi_node)
1533 tree init_cond = chrec_not_analyzed_yet;
1534 struct loop *loop = loop_containing_stmt (loop_phi_node);
1536 if (dump_file && (dump_flags & TDF_DETAILS))
1538 fprintf (dump_file, "(analyze_initial_condition \n");
1539 fprintf (dump_file, " (loop_phi_node = \n");
1540 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1541 fprintf (dump_file, ")\n");
1544 n = gimple_phi_num_args (loop_phi_node);
1545 for (i = 0; i < n; i++)
1547 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1548 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1550 /* When the branch is oriented to the loop's body, it does
1551 not contribute to the initial condition. */
1552 if (flow_bb_inside_loop_p (loop, bb))
1555 if (init_cond == chrec_not_analyzed_yet)
1561 if (TREE_CODE (branch) == SSA_NAME)
1563 init_cond = chrec_dont_know;
1567 init_cond = chrec_merge (init_cond, branch);
1570 /* Ooops -- a loop without an entry??? */
1571 if (init_cond == chrec_not_analyzed_yet)
1572 init_cond = chrec_dont_know;
1574 /* During early loop unrolling we do not have fully constant propagated IL.
1575 Handle degenerate PHIs here to not miss important unrollings. */
1576 if (TREE_CODE (init_cond) == SSA_NAME)
1578 gimple def = SSA_NAME_DEF_STMT (init_cond);
1580 if (gimple_code (def) == GIMPLE_PHI
1581 && (res = degenerate_phi_result (def)) != NULL_TREE
1582 /* Only allow invariants here, otherwise we may break
1583 loop-closed SSA form. */
1584 && is_gimple_min_invariant (res))
1588 if (dump_file && (dump_flags & TDF_DETAILS))
1590 fprintf (dump_file, " (init_cond = ");
1591 print_generic_expr (dump_file, init_cond, 0);
1592 fprintf (dump_file, "))\n");
1598 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1601 interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
1604 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1607 if (phi_loop != loop)
1609 struct loop *subloop;
1610 tree evolution_fn = analyze_scalar_evolution
1611 (phi_loop, PHI_RESULT (loop_phi_node));
1613 /* Dive one level deeper. */
1614 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1616 /* Interpret the subloop. */
1617 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1621 /* Otherwise really interpret the loop phi. */
1622 init_cond = analyze_initial_condition (loop_phi_node);
1623 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1625 /* Verify we maintained the correct initial condition throughout
1626 possible conversions in the SSA chain. */
1627 if (res != chrec_dont_know)
1629 tree new_init = res;
1630 if (CONVERT_EXPR_P (res)
1631 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1632 new_init = fold_convert (TREE_TYPE (res),
1633 CHREC_LEFT (TREE_OPERAND (res, 0)));
1634 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1635 new_init = CHREC_LEFT (res);
1636 STRIP_USELESS_TYPE_CONVERSION (new_init);
1637 gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC);
1638 if (!operand_equal_p (init_cond, new_init, 0))
1639 return chrec_dont_know;
1645 /* This function merges the branches of a condition-phi-node,
1646 contained in the outermost loop, and whose arguments are already
1650 interpret_condition_phi (struct loop *loop, gimple condition_phi)
1652 int i, n = gimple_phi_num_args (condition_phi);
1653 tree res = chrec_not_analyzed_yet;
1655 for (i = 0; i < n; i++)
1659 if (backedge_phi_arg_p (condition_phi, i))
1661 res = chrec_dont_know;
1665 branch_chrec = analyze_scalar_evolution
1666 (loop, PHI_ARG_DEF (condition_phi, i));
1668 res = chrec_merge (res, branch_chrec);
1674 /* Interpret the operation RHS1 OP RHS2. If we didn't
1675 analyze this node before, follow the definitions until ending
1676 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1677 return path, this function propagates evolutions (ala constant copy
1678 propagation). OPND1 is not a GIMPLE expression because we could
1679 analyze the effect of an inner loop: see interpret_loop_phi. */
1682 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1683 tree type, tree rhs1, enum tree_code code, tree rhs2)
1685 tree res, chrec1, chrec2;
1687 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1689 if (is_gimple_min_invariant (rhs1))
1690 return chrec_convert (type, rhs1, at_stmt);
1692 if (code == SSA_NAME)
1693 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1696 if (code == ASSERT_EXPR)
1698 rhs1 = ASSERT_EXPR_VAR (rhs1);
1699 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1703 return chrec_dont_know;
1708 case POINTER_PLUS_EXPR:
1709 chrec1 = analyze_scalar_evolution (loop, rhs1);
1710 chrec2 = analyze_scalar_evolution (loop, rhs2);
1711 chrec1 = chrec_convert (type, chrec1, at_stmt);
1712 chrec2 = chrec_convert (sizetype, chrec2, at_stmt);
1713 res = chrec_fold_plus (type, chrec1, chrec2);
1717 chrec1 = analyze_scalar_evolution (loop, rhs1);
1718 chrec2 = analyze_scalar_evolution (loop, rhs2);
1719 chrec1 = chrec_convert (type, chrec1, at_stmt);
1720 chrec2 = chrec_convert (type, chrec2, at_stmt);
1721 res = chrec_fold_plus (type, chrec1, chrec2);
1725 chrec1 = analyze_scalar_evolution (loop, rhs1);
1726 chrec2 = analyze_scalar_evolution (loop, rhs2);
1727 chrec1 = chrec_convert (type, chrec1, at_stmt);
1728 chrec2 = chrec_convert (type, chrec2, at_stmt);
1729 res = chrec_fold_minus (type, chrec1, chrec2);
1733 chrec1 = analyze_scalar_evolution (loop, rhs1);
1734 chrec1 = chrec_convert (type, chrec1, at_stmt);
1735 /* TYPE may be integer, real or complex, so use fold_convert. */
1736 res = chrec_fold_multiply (type, chrec1,
1737 fold_convert (type, integer_minus_one_node));
1741 /* Handle ~X as -1 - X. */
1742 chrec1 = analyze_scalar_evolution (loop, rhs1);
1743 chrec1 = chrec_convert (type, chrec1, at_stmt);
1744 res = chrec_fold_minus (type,
1745 fold_convert (type, integer_minus_one_node),
1750 chrec1 = analyze_scalar_evolution (loop, rhs1);
1751 chrec2 = analyze_scalar_evolution (loop, rhs2);
1752 chrec1 = chrec_convert (type, chrec1, at_stmt);
1753 chrec2 = chrec_convert (type, chrec2, at_stmt);
1754 res = chrec_fold_multiply (type, chrec1, chrec2);
1758 chrec1 = analyze_scalar_evolution (loop, rhs1);
1759 res = chrec_convert (type, chrec1, at_stmt);
1763 res = chrec_dont_know;
1770 /* Interpret the expression EXPR. */
1773 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1775 enum tree_code code;
1776 tree type = TREE_TYPE (expr), op0, op1;
1778 if (automatically_generated_chrec_p (expr))
1781 if (TREE_CODE (expr) == POLYNOMIAL_CHREC)
1782 return chrec_dont_know;
1784 extract_ops_from_tree (expr, &code, &op0, &op1);
1786 return interpret_rhs_expr (loop, at_stmt, type,
1790 /* Interpret the rhs of the assignment STMT. */
1793 interpret_gimple_assign (struct loop *loop, gimple stmt)
1795 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1796 enum tree_code code = gimple_assign_rhs_code (stmt);
1798 return interpret_rhs_expr (loop, stmt, type,
1799 gimple_assign_rhs1 (stmt), code,
1800 gimple_assign_rhs2 (stmt));
1805 /* This section contains all the entry points:
1806 - number_of_iterations_in_loop,
1807 - analyze_scalar_evolution,
1808 - instantiate_parameters.
1811 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1812 common ancestor of DEF_LOOP and USE_LOOP. */
1815 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1816 struct loop *def_loop,
1820 if (def_loop == wrto_loop)
1823 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1824 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1826 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1829 /* Helper recursive function. */
1832 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1834 tree type = TREE_TYPE (var);
1837 struct loop *def_loop;
1839 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1840 return chrec_dont_know;
1842 if (TREE_CODE (var) != SSA_NAME)
1843 return interpret_expr (loop, NULL, var);
1845 def = SSA_NAME_DEF_STMT (var);
1846 bb = gimple_bb (def);
1847 def_loop = bb ? bb->loop_father : NULL;
1850 || !flow_bb_inside_loop_p (loop, bb))
1852 /* Keep the symbolic form. */
1857 if (res != chrec_not_analyzed_yet)
1859 if (loop != bb->loop_father)
1860 res = compute_scalar_evolution_in_loop
1861 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1866 if (loop != def_loop)
1868 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1869 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1874 switch (gimple_code (def))
1877 res = interpret_gimple_assign (loop, def);
1881 if (loop_phi_node_p (def))
1882 res = interpret_loop_phi (loop, def);
1884 res = interpret_condition_phi (loop, def);
1888 res = chrec_dont_know;
1894 /* Keep the symbolic form. */
1895 if (res == chrec_dont_know)
1898 if (loop == def_loop)
1899 set_scalar_evolution (block_before_loop (loop), var, res);
1904 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1905 LOOP. LOOP is the loop in which the variable is used.
1907 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1908 pointer to the statement that uses this variable, in order to
1909 determine the evolution function of the variable, use the following
1912 loop_p loop = loop_containing_stmt (stmt);
1913 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1914 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1918 analyze_scalar_evolution (struct loop *loop, tree var)
1922 if (dump_file && (dump_flags & TDF_DETAILS))
1924 fprintf (dump_file, "(analyze_scalar_evolution \n");
1925 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1926 fprintf (dump_file, " (scalar = ");
1927 print_generic_expr (dump_file, var, 0);
1928 fprintf (dump_file, ")\n");
1931 res = get_scalar_evolution (block_before_loop (loop), var);
1932 res = analyze_scalar_evolution_1 (loop, var, res);
1934 if (dump_file && (dump_flags & TDF_DETAILS))
1935 fprintf (dump_file, ")\n");
1940 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1941 WRTO_LOOP (which should be a superloop of USE_LOOP)
1943 FOLDED_CASTS is set to true if resolve_mixers used
1944 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1945 at the moment in order to keep things simple).
1947 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1950 for (i = 0; i < 100; i++) -- loop 1
1952 for (j = 0; j < 100; j++) -- loop 2
1959 for (t = 0; t < 100; t++) -- loop 3
1966 Both k1 and k2 are invariants in loop3, thus
1967 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1968 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1970 As they are invariant, it does not matter whether we consider their
1971 usage in loop 3 or loop 2, hence
1972 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1973 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1974 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1975 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1977 Similarly for their evolutions with respect to loop 1. The values of K2
1978 in the use in loop 2 vary independently on loop 1, thus we cannot express
1979 the evolution with respect to loop 1:
1980 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
1981 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
1982 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
1983 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
1985 The value of k2 in the use in loop 1 is known, though:
1986 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
1987 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
1991 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1992 tree version, bool *folded_casts)
1995 tree ev = version, tmp;
1997 /* We cannot just do
1999 tmp = analyze_scalar_evolution (use_loop, version);
2000 ev = resolve_mixers (wrto_loop, tmp);
2002 as resolve_mixers would query the scalar evolution with respect to
2003 wrto_loop. For example, in the situation described in the function
2004 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2007 analyze_scalar_evolution (use_loop, version) = k2
2009 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2010 is 100, which is a wrong result, since we are interested in the
2013 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2014 each time checking that there is no evolution in the inner loop. */
2017 *folded_casts = false;
2020 tmp = analyze_scalar_evolution (use_loop, ev);
2021 ev = resolve_mixers (use_loop, tmp);
2023 if (folded_casts && tmp != ev)
2024 *folded_casts = true;
2026 if (use_loop == wrto_loop)
2029 /* If the value of the use changes in the inner loop, we cannot express
2030 its value in the outer loop (we might try to return interval chrec,
2031 but we do not have a user for it anyway) */
2032 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2034 return chrec_dont_know;
2036 use_loop = loop_outer (use_loop);
2040 /* Returns from CACHE the value for VERSION instantiated below
2041 INSTANTIATED_BELOW block. */
2044 get_instantiated_value (htab_t cache, basic_block instantiated_below,
2047 struct scev_info_str *info, pattern;
2049 pattern.var = version;
2050 pattern.instantiated_below = instantiated_below;
2051 info = (struct scev_info_str *) htab_find (cache, &pattern);
2059 /* Sets in CACHE the value of VERSION instantiated below basic block
2060 INSTANTIATED_BELOW to VAL. */
2063 set_instantiated_value (htab_t cache, basic_block instantiated_below,
2064 tree version, tree val)
2066 struct scev_info_str *info, pattern;
2069 pattern.var = version;
2070 pattern.instantiated_below = instantiated_below;
2071 slot = htab_find_slot (cache, &pattern, INSERT);
2074 *slot = new_scev_info_str (instantiated_below, version);
2075 info = (struct scev_info_str *) *slot;
2079 /* Return the closed_loop_phi node for VAR. If there is none, return
2083 loop_closed_phi_def (tree var)
2088 gimple_stmt_iterator psi;
2090 if (var == NULL_TREE
2091 || TREE_CODE (var) != SSA_NAME)
2094 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2095 exit = single_exit (loop);
2099 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2101 phi = gsi_stmt (psi);
2102 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2103 return PHI_RESULT (phi);
2109 static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
2112 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2113 and EVOLUTION_LOOP, that were left under a symbolic form.
2115 CHREC is an SSA_NAME to be instantiated.
2117 CACHE is the cache of already instantiated values.
2119 FOLD_CONVERSIONS should be set to true when the conversions that
2120 may wrap in signed/pointer type are folded, as long as the value of
2121 the chrec is preserved.
2123 SIZE_EXPR is used for computing the size of the expression to be
2124 instantiated, and to stop if it exceeds some limit. */
2127 instantiate_scev_name (basic_block instantiate_below,
2128 struct loop *evolution_loop, tree chrec,
2129 bool fold_conversions, htab_t cache, int size_expr)
2132 struct loop *def_loop;
2133 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2135 /* A parameter (or loop invariant and we do not want to include
2136 evolutions in outer loops), nothing to do. */
2138 || loop_depth (def_bb->loop_father) == 0
2139 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2142 /* We cache the value of instantiated variable to avoid exponential
2143 time complexity due to reevaluations. We also store the convenient
2144 value in the cache in order to prevent infinite recursion -- we do
2145 not want to instantiate the SSA_NAME if it is in a mixer
2146 structure. This is used for avoiding the instantiation of
2147 recursively defined functions, such as:
2149 | a_2 -> {0, +, 1, +, a_2}_1 */
2151 res = get_instantiated_value (cache, instantiate_below, chrec);
2155 res = chrec_dont_know;
2156 set_instantiated_value (cache, instantiate_below, chrec, res);
2158 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2160 /* If the analysis yields a parametric chrec, instantiate the
2162 res = analyze_scalar_evolution (def_loop, chrec);
2164 /* Don't instantiate loop-closed-ssa phi nodes. */
2165 if (TREE_CODE (res) == SSA_NAME
2166 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2167 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2168 > loop_depth (def_loop))))
2171 res = loop_closed_phi_def (chrec);
2175 if (res == NULL_TREE
2176 || !dominated_by_p (CDI_DOMINATORS, instantiate_below,
2177 gimple_bb (SSA_NAME_DEF_STMT (res))))
2178 res = chrec_dont_know;
2181 else if (res != chrec_dont_know)
2182 res = instantiate_scev_r (instantiate_below, evolution_loop, res,
2183 fold_conversions, cache, size_expr);
2185 /* Store the correct value to the cache. */
2186 set_instantiated_value (cache, instantiate_below, chrec, res);
2191 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2192 and EVOLUTION_LOOP, that were left under a symbolic form.
2194 CHREC is a polynomial chain of recurrence to be instantiated.
2196 CACHE is the cache of already instantiated values.
2198 FOLD_CONVERSIONS should be set to true when the conversions that
2199 may wrap in signed/pointer type are folded, as long as the value of
2200 the chrec is preserved.
2202 SIZE_EXPR is used for computing the size of the expression to be
2203 instantiated, and to stop if it exceeds some limit. */
2206 instantiate_scev_poly (basic_block instantiate_below,
2207 struct loop *evolution_loop, tree chrec,
2208 bool fold_conversions, htab_t cache, int size_expr)
2211 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2212 CHREC_LEFT (chrec), fold_conversions, cache,
2214 if (op0 == chrec_dont_know)
2215 return chrec_dont_know;
2217 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2218 CHREC_RIGHT (chrec), fold_conversions, cache,
2220 if (op1 == chrec_dont_know)
2221 return chrec_dont_know;
2223 if (CHREC_LEFT (chrec) != op0
2224 || CHREC_RIGHT (chrec) != op1)
2226 unsigned var = CHREC_VARIABLE (chrec);
2228 /* When the instantiated stride or base has an evolution in an
2229 innermost loop, return chrec_dont_know, as this is not a
2230 valid SCEV representation. In the reduced testcase for
2231 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2233 if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var)
2234 || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var))
2235 return chrec_dont_know;
2237 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2238 chrec = build_polynomial_chrec (var, op0, op1);
2244 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2245 and EVOLUTION_LOOP, that were left under a symbolic form.
2247 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2249 CACHE is the cache of already instantiated values.
2251 FOLD_CONVERSIONS should be set to true when the conversions that
2252 may wrap in signed/pointer type are folded, as long as the value of
2253 the chrec is preserved.
2255 SIZE_EXPR is used for computing the size of the expression to be
2256 instantiated, and to stop if it exceeds some limit. */
2259 instantiate_scev_binary (basic_block instantiate_below,
2260 struct loop *evolution_loop, tree chrec, enum tree_code code,
2261 tree type, tree c0, tree c1,
2262 bool fold_conversions, htab_t cache, int size_expr)
2265 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2266 c0, fold_conversions, cache,
2268 if (op0 == chrec_dont_know)
2269 return chrec_dont_know;
2271 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2272 c1, fold_conversions, cache,
2274 if (op1 == chrec_dont_know)
2275 return chrec_dont_know;
2280 op0 = chrec_convert (type, op0, NULL);
2281 op1 = chrec_convert_rhs (type, op1, NULL);
2285 case POINTER_PLUS_EXPR:
2287 return chrec_fold_plus (type, op0, op1);
2290 return chrec_fold_minus (type, op0, op1);
2293 return chrec_fold_multiply (type, op0, op1);
2300 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2303 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2304 and EVOLUTION_LOOP, that were left under a symbolic form.
2306 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2309 CACHE is the cache of already instantiated values.
2311 FOLD_CONVERSIONS should be set to true when the conversions that
2312 may wrap in signed/pointer type are folded, as long as the value of
2313 the chrec is preserved.
2315 SIZE_EXPR is used for computing the size of the expression to be
2316 instantiated, and to stop if it exceeds some limit. */
2319 instantiate_scev_convert (basic_block instantiate_below,
2320 struct loop *evolution_loop, tree chrec,
2322 bool fold_conversions, htab_t cache, int size_expr)
2324 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2325 fold_conversions, cache, size_expr);
2327 if (op0 == chrec_dont_know)
2328 return chrec_dont_know;
2330 if (fold_conversions)
2332 tree tmp = chrec_convert_aggressive (type, op0);
2337 if (chrec && op0 == op)
2340 /* If we used chrec_convert_aggressive, we can no longer assume that
2341 signed chrecs do not overflow, as chrec_convert does, so avoid
2342 calling it in that case. */
2343 if (fold_conversions)
2344 return fold_convert (type, op0);
2346 return chrec_convert (type, op0, NULL);
2349 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2350 and EVOLUTION_LOOP, that were left under a symbolic form.
2352 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2353 Handle ~X as -1 - X.
2354 Handle -X as -1 * X.
2356 CACHE is the cache of already instantiated values.
2358 FOLD_CONVERSIONS should be set to true when the conversions that
2359 may wrap in signed/pointer type are folded, as long as the value of
2360 the chrec is preserved.
2362 SIZE_EXPR is used for computing the size of the expression to be
2363 instantiated, and to stop if it exceeds some limit. */
2366 instantiate_scev_not (basic_block instantiate_below,
2367 struct loop *evolution_loop, tree chrec,
2368 enum tree_code code, tree type, tree op,
2369 bool fold_conversions, htab_t cache, int size_expr)
2371 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2372 fold_conversions, cache, size_expr);
2374 if (op0 == chrec_dont_know)
2375 return chrec_dont_know;
2379 op0 = chrec_convert (type, op0, NULL);
2384 return chrec_fold_minus
2385 (type, fold_convert (type, integer_minus_one_node), op0);
2388 return chrec_fold_multiply
2389 (type, fold_convert (type, integer_minus_one_node), op0);
2396 return chrec ? chrec : fold_build1 (code, type, op0);
2399 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2400 and EVOLUTION_LOOP, that were left under a symbolic form.
2402 CHREC is an expression with 3 operands to be instantiated.
2404 CACHE is the cache of already instantiated values.
2406 FOLD_CONVERSIONS should be set to true when the conversions that
2407 may wrap in signed/pointer type are folded, as long as the value of
2408 the chrec is preserved.
2410 SIZE_EXPR is used for computing the size of the expression to be
2411 instantiated, and to stop if it exceeds some limit. */
2414 instantiate_scev_3 (basic_block instantiate_below,
2415 struct loop *evolution_loop, tree chrec,
2416 bool fold_conversions, htab_t cache, int size_expr)
2419 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2420 TREE_OPERAND (chrec, 0),
2421 fold_conversions, cache, size_expr);
2422 if (op0 == chrec_dont_know)
2423 return chrec_dont_know;
2425 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2426 TREE_OPERAND (chrec, 1),
2427 fold_conversions, cache, size_expr);
2428 if (op1 == chrec_dont_know)
2429 return chrec_dont_know;
2431 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2432 TREE_OPERAND (chrec, 2),
2433 fold_conversions, cache, size_expr);
2434 if (op2 == chrec_dont_know)
2435 return chrec_dont_know;
2437 if (op0 == TREE_OPERAND (chrec, 0)
2438 && op1 == TREE_OPERAND (chrec, 1)
2439 && op2 == TREE_OPERAND (chrec, 2))
2442 return fold_build3 (TREE_CODE (chrec),
2443 TREE_TYPE (chrec), op0, op1, op2);
2446 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2447 and EVOLUTION_LOOP, that were left under a symbolic form.
2449 CHREC is an expression with 2 operands to be instantiated.
2451 CACHE is the cache of already instantiated values.
2453 FOLD_CONVERSIONS should be set to true when the conversions that
2454 may wrap in signed/pointer type are folded, as long as the value of
2455 the chrec is preserved.
2457 SIZE_EXPR is used for computing the size of the expression to be
2458 instantiated, and to stop if it exceeds some limit. */
2461 instantiate_scev_2 (basic_block instantiate_below,
2462 struct loop *evolution_loop, tree chrec,
2463 bool fold_conversions, htab_t cache, int size_expr)
2466 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2467 TREE_OPERAND (chrec, 0),
2468 fold_conversions, cache, size_expr);
2469 if (op0 == chrec_dont_know)
2470 return chrec_dont_know;
2472 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2473 TREE_OPERAND (chrec, 1),
2474 fold_conversions, cache, size_expr);
2475 if (op1 == chrec_dont_know)
2476 return chrec_dont_know;
2478 if (op0 == TREE_OPERAND (chrec, 0)
2479 && op1 == TREE_OPERAND (chrec, 1))
2482 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2485 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2486 and EVOLUTION_LOOP, that were left under a symbolic form.
2488 CHREC is an expression with 2 operands to be instantiated.
2490 CACHE is the cache of already instantiated values.
2492 FOLD_CONVERSIONS should be set to true when the conversions that
2493 may wrap in signed/pointer type are folded, as long as the value of
2494 the chrec is preserved.
2496 SIZE_EXPR is used for computing the size of the expression to be
2497 instantiated, and to stop if it exceeds some limit. */
2500 instantiate_scev_1 (basic_block instantiate_below,
2501 struct loop *evolution_loop, tree chrec,
2502 bool fold_conversions, htab_t cache, int size_expr)
2504 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2505 TREE_OPERAND (chrec, 0),
2506 fold_conversions, cache, size_expr);
2508 if (op0 == chrec_dont_know)
2509 return chrec_dont_know;
2511 if (op0 == TREE_OPERAND (chrec, 0))
2514 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2517 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2518 and EVOLUTION_LOOP, that were left under a symbolic form.
2520 CHREC is the scalar evolution to instantiate.
2522 CACHE is the cache of already instantiated values.
2524 FOLD_CONVERSIONS should be set to true when the conversions that
2525 may wrap in signed/pointer type are folded, as long as the value of
2526 the chrec is preserved.
2528 SIZE_EXPR is used for computing the size of the expression to be
2529 instantiated, and to stop if it exceeds some limit. */
2532 instantiate_scev_r (basic_block instantiate_below,
2533 struct loop *evolution_loop, tree chrec,
2534 bool fold_conversions, htab_t cache, int size_expr)
2536 /* Give up if the expression is larger than the MAX that we allow. */
2537 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2538 return chrec_dont_know;
2540 if (automatically_generated_chrec_p (chrec)
2541 || is_gimple_min_invariant (chrec))
2544 switch (TREE_CODE (chrec))
2547 return instantiate_scev_name (instantiate_below, evolution_loop, chrec,
2548 fold_conversions, cache, size_expr);
2550 case POLYNOMIAL_CHREC:
2551 return instantiate_scev_poly (instantiate_below, evolution_loop, chrec,
2552 fold_conversions, cache, size_expr);
2554 case POINTER_PLUS_EXPR:
2558 return instantiate_scev_binary (instantiate_below, evolution_loop, chrec,
2559 TREE_CODE (chrec), chrec_type (chrec),
2560 TREE_OPERAND (chrec, 0),
2561 TREE_OPERAND (chrec, 1),
2562 fold_conversions, cache, size_expr);
2565 return instantiate_scev_convert (instantiate_below, evolution_loop, chrec,
2566 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2567 fold_conversions, cache, size_expr);
2571 return instantiate_scev_not (instantiate_below, evolution_loop, chrec,
2572 TREE_CODE (chrec), TREE_TYPE (chrec),
2573 TREE_OPERAND (chrec, 0),
2574 fold_conversions, cache, size_expr);
2576 case SCEV_NOT_KNOWN:
2577 return chrec_dont_know;
2586 if (VL_EXP_CLASS_P (chrec))
2587 return chrec_dont_know;
2589 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2592 return instantiate_scev_3 (instantiate_below, evolution_loop, chrec,
2593 fold_conversions, cache, size_expr);
2596 return instantiate_scev_2 (instantiate_below, evolution_loop, chrec,
2597 fold_conversions, cache, size_expr);
2600 return instantiate_scev_1 (instantiate_below, evolution_loop, chrec,
2601 fold_conversions, cache, size_expr);
2610 /* Too complicated to handle. */
2611 return chrec_dont_know;
2614 /* Analyze all the parameters of the chrec that were left under a
2615 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2616 recursive instantiation of parameters: a parameter is a variable
2617 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2618 a function parameter. */
2621 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2625 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2627 if (dump_file && (dump_flags & TDF_DETAILS))
2629 fprintf (dump_file, "(instantiate_scev \n");
2630 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2631 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2632 fprintf (dump_file, " (chrec = ");
2633 print_generic_expr (dump_file, chrec, 0);
2634 fprintf (dump_file, ")\n");
2637 res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false,
2640 if (dump_file && (dump_flags & TDF_DETAILS))
2642 fprintf (dump_file, " (res = ");
2643 print_generic_expr (dump_file, res, 0);
2644 fprintf (dump_file, "))\n");
2647 htab_delete (cache);
2652 /* Similar to instantiate_parameters, but does not introduce the
2653 evolutions in outer loops for LOOP invariants in CHREC, and does not
2654 care about causing overflows, as long as they do not affect value
2655 of an expression. */
2658 resolve_mixers (struct loop *loop, tree chrec)
2660 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2661 tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true,
2663 htab_delete (cache);
2667 /* Entry point for the analysis of the number of iterations pass.
2668 This function tries to safely approximate the number of iterations
2669 the loop will run. When this property is not decidable at compile
2670 time, the result is chrec_dont_know. Otherwise the result is a
2671 scalar or a symbolic parameter. When the number of iterations may
2672 be equal to zero and the property cannot be determined at compile
2673 time, the result is a COND_EXPR that represents in a symbolic form
2674 the conditions under which the number of iterations is not zero.
2676 Example of analysis: suppose that the loop has an exit condition:
2678 "if (b > 49) goto end_loop;"
2680 and that in a previous analysis we have determined that the
2681 variable 'b' has an evolution function:
2683 "EF = {23, +, 5}_2".
2685 When we evaluate the function at the point 5, i.e. the value of the
2686 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2687 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2688 the loop body has been executed 6 times. */
2691 number_of_latch_executions (struct loop *loop)
2694 struct tree_niter_desc niter_desc;
2698 /* Determine whether the number of iterations in loop has already
2700 res = loop->nb_iterations;
2704 may_be_zero = NULL_TREE;
2706 if (dump_file && (dump_flags & TDF_DETAILS))
2707 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2709 res = chrec_dont_know;
2710 exit = single_exit (loop);
2712 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2714 may_be_zero = niter_desc.may_be_zero;
2715 res = niter_desc.niter;
2718 if (res == chrec_dont_know
2720 || integer_zerop (may_be_zero))
2722 else if (integer_nonzerop (may_be_zero))
2723 res = build_int_cst (TREE_TYPE (res), 0);
2725 else if (COMPARISON_CLASS_P (may_be_zero))
2726 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2727 build_int_cst (TREE_TYPE (res), 0), res);
2729 res = chrec_dont_know;
2731 if (dump_file && (dump_flags & TDF_DETAILS))
2733 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2734 print_generic_expr (dump_file, res, 0);
2735 fprintf (dump_file, "))\n");
2738 loop->nb_iterations = res;
2742 /* Returns the number of executions of the exit condition of LOOP,
2743 i.e., the number by one higher than number_of_latch_executions.
2744 Note that unlike number_of_latch_executions, this number does
2745 not necessarily fit in the unsigned variant of the type of
2746 the control variable -- if the number of iterations is a constant,
2747 we return chrec_dont_know if adding one to number_of_latch_executions
2748 overflows; however, in case the number of iterations is symbolic
2749 expression, the caller is responsible for dealing with this
2750 the possible overflow. */
2753 number_of_exit_cond_executions (struct loop *loop)
2755 tree ret = number_of_latch_executions (loop);
2756 tree type = chrec_type (ret);
2758 if (chrec_contains_undetermined (ret))
2761 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2762 if (TREE_CODE (ret) == INTEGER_CST
2763 && TREE_OVERFLOW (ret))
2764 return chrec_dont_know;
2769 /* One of the drivers for testing the scalar evolutions analysis.
2770 This function computes the number of iterations for all the loops
2771 from the EXIT_CONDITIONS array. */
2774 number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions)
2777 unsigned nb_chrec_dont_know_loops = 0;
2778 unsigned nb_static_loops = 0;
2781 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
2783 tree res = number_of_latch_executions (loop_containing_stmt (cond));
2784 if (chrec_contains_undetermined (res))
2785 nb_chrec_dont_know_loops++;
2792 fprintf (dump_file, "\n(\n");
2793 fprintf (dump_file, "-----------------------------------------\n");
2794 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2795 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2796 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2797 fprintf (dump_file, "-----------------------------------------\n");
2798 fprintf (dump_file, ")\n\n");
2800 print_loops (dump_file, 3);
2806 /* Counters for the stats. */
2812 unsigned nb_affine_multivar;
2813 unsigned nb_higher_poly;
2814 unsigned nb_chrec_dont_know;
2815 unsigned nb_undetermined;
2818 /* Reset the counters. */
2821 reset_chrecs_counters (struct chrec_stats *stats)
2823 stats->nb_chrecs = 0;
2824 stats->nb_affine = 0;
2825 stats->nb_affine_multivar = 0;
2826 stats->nb_higher_poly = 0;
2827 stats->nb_chrec_dont_know = 0;
2828 stats->nb_undetermined = 0;
2831 /* Dump the contents of a CHREC_STATS structure. */
2834 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2836 fprintf (file, "\n(\n");
2837 fprintf (file, "-----------------------------------------\n");
2838 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2839 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2840 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2841 stats->nb_higher_poly);
2842 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2843 fprintf (file, "-----------------------------------------\n");
2844 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2845 fprintf (file, "%d\twith undetermined coefficients\n",
2846 stats->nb_undetermined);
2847 fprintf (file, "-----------------------------------------\n");
2848 fprintf (file, "%d\tchrecs in the scev database\n",
2849 (int) htab_elements (scalar_evolution_info));
2850 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2851 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2852 fprintf (file, "-----------------------------------------\n");
2853 fprintf (file, ")\n\n");
2856 /* Gather statistics about CHREC. */
2859 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2861 if (dump_file && (dump_flags & TDF_STATS))
2863 fprintf (dump_file, "(classify_chrec ");
2864 print_generic_expr (dump_file, chrec, 0);
2865 fprintf (dump_file, "\n");
2870 if (chrec == NULL_TREE)
2872 stats->nb_undetermined++;
2876 switch (TREE_CODE (chrec))
2878 case POLYNOMIAL_CHREC:
2879 if (evolution_function_is_affine_p (chrec))
2881 if (dump_file && (dump_flags & TDF_STATS))
2882 fprintf (dump_file, " affine_univariate\n");
2885 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2887 if (dump_file && (dump_flags & TDF_STATS))
2888 fprintf (dump_file, " affine_multivariate\n");
2889 stats->nb_affine_multivar++;
2893 if (dump_file && (dump_flags & TDF_STATS))
2894 fprintf (dump_file, " higher_degree_polynomial\n");
2895 stats->nb_higher_poly++;
2904 if (chrec_contains_undetermined (chrec))
2906 if (dump_file && (dump_flags & TDF_STATS))
2907 fprintf (dump_file, " undetermined\n");
2908 stats->nb_undetermined++;
2911 if (dump_file && (dump_flags & TDF_STATS))
2912 fprintf (dump_file, ")\n");
2915 /* One of the drivers for testing the scalar evolutions analysis.
2916 This function analyzes the scalar evolution of all the scalars
2917 defined as loop phi nodes in one of the loops from the
2918 EXIT_CONDITIONS array.
2920 TODO Optimization: A loop is in canonical form if it contains only
2921 a single scalar loop phi node. All the other scalars that have an
2922 evolution in the loop are rewritten in function of this single
2923 index. This allows the parallelization of the loop. */
2926 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions)
2929 struct chrec_stats stats;
2931 gimple_stmt_iterator psi;
2933 reset_chrecs_counters (&stats);
2935 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
2941 loop = loop_containing_stmt (cond);
2944 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2946 phi = gsi_stmt (psi);
2947 if (is_gimple_reg (PHI_RESULT (phi)))
2949 chrec = instantiate_parameters
2951 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2953 if (dump_file && (dump_flags & TDF_STATS))
2954 gather_chrec_stats (chrec, &stats);
2959 if (dump_file && (dump_flags & TDF_STATS))
2960 dump_chrecs_stats (dump_file, &stats);
2963 /* Callback for htab_traverse, gathers information on chrecs in the
2967 gather_stats_on_scev_database_1 (void **slot, void *stats)
2969 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2971 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2976 /* Classify the chrecs of the whole database. */
2979 gather_stats_on_scev_database (void)
2981 struct chrec_stats stats;
2986 reset_chrecs_counters (&stats);
2988 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2991 dump_chrecs_stats (dump_file, &stats);
2999 initialize_scalar_evolutions_analyzer (void)
3001 /* The elements below are unique. */
3002 if (chrec_dont_know == NULL_TREE)
3004 chrec_not_analyzed_yet = NULL_TREE;
3005 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3006 chrec_known = make_node (SCEV_KNOWN);
3007 TREE_TYPE (chrec_dont_know) = void_type_node;
3008 TREE_TYPE (chrec_known) = void_type_node;
3012 /* Initialize the analysis of scalar evolutions for LOOPS. */
3015 scev_initialize (void)
3021 scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
3024 initialize_scalar_evolutions_analyzer ();
3026 FOR_EACH_LOOP (li, loop, 0)
3028 loop->nb_iterations = NULL_TREE;
3032 /* Cleans up the information cached by the scalar evolutions analysis
3033 in the hash table. */
3036 scev_reset_htab (void)
3038 if (!scalar_evolution_info)
3041 htab_empty (scalar_evolution_info);
3044 /* Cleans up the information cached by the scalar evolutions analysis
3045 in the hash table and in the loop->nb_iterations. */
3058 FOR_EACH_LOOP (li, loop, 0)
3060 loop->nb_iterations = NULL_TREE;
3064 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3065 respect to WRTO_LOOP and returns its base and step in IV if possible
3066 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3067 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3068 invariant in LOOP. Otherwise we require it to be an integer constant.
3070 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3071 because it is computed in signed arithmetics). Consequently, adding an
3074 for (i = IV->base; ; i += IV->step)
3076 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3077 false for the type of the induction variable, or you can prove that i does
3078 not wrap by some other argument. Otherwise, this might introduce undefined
3081 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3083 must be used instead. */
3086 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3087 affine_iv *iv, bool allow_nonconstant_step)
3092 iv->base = NULL_TREE;
3093 iv->step = NULL_TREE;
3094 iv->no_overflow = false;
3096 type = TREE_TYPE (op);
3097 if (TREE_CODE (type) != INTEGER_TYPE
3098 && TREE_CODE (type) != POINTER_TYPE)
3101 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3103 if (chrec_contains_undetermined (ev)
3104 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3107 if (tree_does_not_contain_chrecs (ev))
3110 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3111 iv->no_overflow = true;
3115 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3116 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3119 iv->step = CHREC_RIGHT (ev);
3120 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3121 || tree_contains_chrecs (iv->step, NULL))
3124 iv->base = CHREC_LEFT (ev);
3125 if (tree_contains_chrecs (iv->base, NULL))
3128 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
3133 /* Runs the analysis of scalar evolutions. */
3136 scev_analysis (void)
3138 VEC(gimple,heap) *exit_conditions;
3140 exit_conditions = VEC_alloc (gimple, heap, 37);
3141 select_loops_exit_conditions (&exit_conditions);
3143 if (dump_file && (dump_flags & TDF_STATS))
3144 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
3146 number_of_iterations_for_all_loops (&exit_conditions);
3147 VEC_free (gimple, heap, exit_conditions);
3150 /* Finalize the scalar evolution analysis. */
3153 scev_finalize (void)
3155 if (!scalar_evolution_info)
3157 htab_delete (scalar_evolution_info);
3158 scalar_evolution_info = NULL;
3161 /* Returns true if the expression EXPR is considered to be too expensive
3162 for scev_const_prop. */
3165 expression_expensive_p (tree expr)
3167 enum tree_code code;
3169 if (is_gimple_val (expr))
3172 code = TREE_CODE (expr);
3173 if (code == TRUNC_DIV_EXPR
3174 || code == CEIL_DIV_EXPR
3175 || code == FLOOR_DIV_EXPR
3176 || code == ROUND_DIV_EXPR
3177 || code == TRUNC_MOD_EXPR
3178 || code == CEIL_MOD_EXPR
3179 || code == FLOOR_MOD_EXPR
3180 || code == ROUND_MOD_EXPR
3181 || code == EXACT_DIV_EXPR)
3183 /* Division by power of two is usually cheap, so we allow it.
3184 Forbid anything else. */
3185 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3189 switch (TREE_CODE_CLASS (code))
3192 case tcc_comparison:
3193 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3198 return expression_expensive_p (TREE_OPERAND (expr, 0));
3205 /* Replace ssa names for that scev can prove they are constant by the
3206 appropriate constants. Also perform final value replacement in loops,
3207 in case the replacement expressions are cheap.
3209 We only consider SSA names defined by phi nodes; rest is left to the
3210 ordinary constant propagation pass. */
3213 scev_const_prop (void)
3216 tree name, type, ev;
3218 struct loop *loop, *ex_loop;
3219 bitmap ssa_names_to_remove = NULL;
3222 gimple_stmt_iterator psi;
3224 if (number_of_loops () <= 1)
3229 loop = bb->loop_father;
3231 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3233 phi = gsi_stmt (psi);
3234 name = PHI_RESULT (phi);
3236 if (!is_gimple_reg (name))
3239 type = TREE_TYPE (name);
3241 if (!POINTER_TYPE_P (type)
3242 && !INTEGRAL_TYPE_P (type))
3245 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3246 if (!is_gimple_min_invariant (ev)
3247 || !may_propagate_copy (name, ev))
3250 /* Replace the uses of the name. */
3252 replace_uses_by (name, ev);
3254 if (!ssa_names_to_remove)
3255 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3256 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3260 /* Remove the ssa names that were replaced by constants. We do not
3261 remove them directly in the previous cycle, since this
3262 invalidates scev cache. */
3263 if (ssa_names_to_remove)
3267 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3269 gimple_stmt_iterator psi;
3270 name = ssa_name (i);
3271 phi = SSA_NAME_DEF_STMT (name);
3273 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3274 psi = gsi_for_stmt (phi);
3275 remove_phi_node (&psi, true);
3278 BITMAP_FREE (ssa_names_to_remove);
3282 /* Now the regular final value replacement. */
3283 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
3286 tree def, rslt, niter;
3287 gimple_stmt_iterator bsi;
3289 /* If we do not know exact number of iterations of the loop, we cannot
3290 replace the final value. */
3291 exit = single_exit (loop);
3295 niter = number_of_latch_executions (loop);
3296 if (niter == chrec_dont_know)
3299 /* Ensure that it is possible to insert new statements somewhere. */
3300 if (!single_pred_p (exit->dest))
3301 split_loop_exit_edge (exit);
3302 bsi = gsi_after_labels (exit->dest);
3304 ex_loop = superloop_at_depth (loop,
3305 loop_depth (exit->dest->loop_father) + 1);
3307 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3309 phi = gsi_stmt (psi);
3310 rslt = PHI_RESULT (phi);
3311 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3312 if (!is_gimple_reg (def))
3318 if (!POINTER_TYPE_P (TREE_TYPE (def))
3319 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3325 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
3326 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3327 if (!tree_does_not_contain_chrecs (def)
3328 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3329 /* Moving the computation from the loop may prolong life range
3330 of some ssa names, which may cause problems if they appear
3331 on abnormal edges. */
3332 || contains_abnormal_ssa_name_p (def)
3333 /* Do not emit expensive expressions. The rationale is that
3334 when someone writes a code like
3336 while (n > 45) n -= 45;
3338 he probably knows that n is not large, and does not want it
3339 to be turned into n %= 45. */
3340 || expression_expensive_p (def))
3346 /* Eliminate the PHI node and replace it by a computation outside
3348 def = unshare_expr (def);
3349 remove_phi_node (&psi, false);
3351 def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
3352 true, GSI_SAME_STMT);
3353 ass = gimple_build_assign (rslt, def);
3354 gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
3360 #include "gt-tree-scalar-evolution.h"