* gcc.target/i386/387-3.c, gcc.target/i386/387-4.c,
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobf1ddc24b1a2c654ac09909d28a9114dd6faba79f
1 /* Scalar evolution detector.
2 Copyright (C) 2003-2014 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 3, or (at your option) any later
10 version.
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
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 Description:
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
48 its definition:
50 - When the definition is a GIMPLE_ASSIGN: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
73 Examples:
75 Example 1: Illustration of the basic algorithm.
77 | a = 3
78 | loop_1
79 | b = phi (a, c)
80 | c = b + 1
81 | if (c > 10) exit_loop
82 | endloop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
115 a -> 3
116 b -> {3, +, 1}_1
117 c -> {4, +, 1}_1
119 or in terms of a C program:
121 | a = 3
122 | for (x = 0; x <= 7; x++)
124 | b = x + 3
125 | c = x + 4
128 Example 2a: Illustration of the algorithm on nested loops.
130 | loop_1
131 | a = phi (1, b)
132 | c = a + 2
133 | loop_2 10 times
134 | b = phi (c, d)
135 | d = b + 3
136 | endloop
137 | endloop
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
143 b -> {c, +, 3}_2
144 d -> {c + 3, +, 3}_2
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
154 a -> {1, +, 32}_1
155 c -> {3, +, 32}_1
157 Example 2b: Multivariate chains of recurrences.
159 | loop_1
160 | k = phi (0, k + 1)
161 | loop_2 4 times
162 | j = phi (0, j + 1)
163 | loop_3 4 times
164 | i = phi (0, i + 1)
165 | A[j + k] = ...
166 | endloop
167 | endloop
168 | endloop
170 Analyzing the access function of array A with
171 instantiate_parameters (loop_1, "j + k"), we obtain the
172 instantiation and the analysis of the scalar variables "j" and "k"
173 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175 {0, +, 1}_1. To obtain the evolution function in loop_3 and
176 instantiate the scalar variables up to loop_1, one has to use:
177 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178 The result of this call is {{0, +, 1}_1, +, 1}_2.
180 Example 3: Higher degree polynomials.
182 | loop_1
183 | a = phi (2, b)
184 | c = phi (5, d)
185 | b = a + 1
186 | d = c + a
187 | endloop
189 a -> {2, +, 1}_1
190 b -> {3, +, 1}_1
191 c -> {5, +, a}_1
192 d -> {5 + a, +, a}_1
194 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197 Example 4: Lucas, Fibonacci, or mixers in general.
199 | loop_1
200 | a = phi (1, b)
201 | c = phi (3, d)
202 | b = c
203 | d = c + a
204 | endloop
206 a -> (1, c)_1
207 c -> {3, +, a}_1
209 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210 following semantics: during the first iteration of the loop_1, the
211 variable contains the value 1, and then it contains the value "c".
212 Note that this syntax is close to the syntax of the loop-phi-node:
213 "a -> (1, c)_1" vs. "a = phi (1, c)".
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
218 Example 5: Flip-flops, or exchangers.
220 | loop_1
221 | a = phi (1, b)
222 | c = phi (3, d)
223 | b = c
224 | d = a
225 | endloop
227 a -> (1, c)_1
228 c -> (3, a)_1
230 Based on these symbolic chrecs, it is possible to refine this
231 information into the more precise PERIODIC_CHRECs:
233 a -> |1, 3|_1
234 c -> |3, 1|_1
236 This transformation is not yet implemented.
238 Further readings:
240 You can find a more detailed description of the algorithm in:
241 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243 this is a preliminary report and some of the details of the
244 algorithm have changed. I'm working on a research report that
245 updates the description of the algorithms to reflect the design
246 choices used in this implementation.
248 A set of slides show a high level overview of the algorithm and run
249 an example through the scalar evolution analyzer:
250 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252 The slides that I have presented at the GCC Summit'04 are available
253 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
256 #include "config.h"
257 #include "system.h"
258 #include "coretypes.h"
259 #include "tree.h"
260 #include "expr.h"
261 #include "gimple-pretty-print.h"
262 #include "basic-block.h"
263 #include "tree-ssa-alias.h"
264 #include "internal-fn.h"
265 #include "gimple-expr.h"
266 #include "is-a.h"
267 #include "gimple.h"
268 #include "gimplify.h"
269 #include "gimple-iterator.h"
270 #include "gimplify-me.h"
271 #include "gimple-ssa.h"
272 #include "tree-cfg.h"
273 #include "tree-phinodes.h"
274 #include "stringpool.h"
275 #include "tree-ssanames.h"
276 #include "tree-ssa-loop-ivopts.h"
277 #include "tree-ssa-loop-manip.h"
278 #include "tree-ssa-loop-niter.h"
279 #include "tree-ssa-loop.h"
280 #include "tree-ssa.h"
281 #include "cfgloop.h"
282 #include "tree-chrec.h"
283 #include "pointer-set.h"
284 #include "tree-affine.h"
285 #include "tree-scalar-evolution.h"
286 #include "dumpfile.h"
287 #include "params.h"
288 #include "tree-ssa-propagate.h"
289 #include "gimple-fold.h"
290 #include "gimplify-me.h"
292 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
293 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
294 tree var);
296 /* The cached information about an SSA name with version NAME_VERSION,
297 claiming that below basic block with index INSTANTIATED_BELOW, the
298 value of the SSA name can be expressed as CHREC. */
300 struct GTY(()) scev_info_str {
301 unsigned int name_version;
302 int instantiated_below;
303 tree chrec;
306 /* Counters for the scev database. */
307 static unsigned nb_set_scev = 0;
308 static unsigned nb_get_scev = 0;
310 /* The following trees are unique elements. Thus the comparison of
311 another element to these elements should be done on the pointer to
312 these trees, and not on their value. */
314 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
315 tree chrec_not_analyzed_yet;
317 /* Reserved to the cases where the analyzer has detected an
318 undecidable property at compile time. */
319 tree chrec_dont_know;
321 /* When the analyzer has detected that a property will never
322 happen, then it qualifies it with chrec_known. */
323 tree chrec_known;
325 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
328 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
330 static inline struct scev_info_str *
331 new_scev_info_str (basic_block instantiated_below, tree var)
333 struct scev_info_str *res;
335 res = ggc_alloc_scev_info_str ();
336 res->name_version = SSA_NAME_VERSION (var);
337 res->chrec = chrec_not_analyzed_yet;
338 res->instantiated_below = instantiated_below->index;
340 return res;
343 /* Computes a hash function for database element ELT. */
345 static inline hashval_t
346 hash_scev_info (const void *elt_)
348 const struct scev_info_str *elt = (const struct scev_info_str *) elt_;
349 return elt->name_version ^ elt->instantiated_below;
352 /* Compares database elements E1 and E2. */
354 static inline int
355 eq_scev_info (const void *e1, const void *e2)
357 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
358 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
360 return (elt1->name_version == elt2->name_version
361 && elt1->instantiated_below == elt2->instantiated_below);
364 /* Deletes database element E. */
366 static void
367 del_scev_info (void *e)
369 ggc_free (e);
373 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
374 A first query on VAR returns chrec_not_analyzed_yet. */
376 static tree *
377 find_var_scev_info (basic_block instantiated_below, tree var)
379 struct scev_info_str *res;
380 struct scev_info_str tmp;
381 PTR *slot;
383 tmp.name_version = SSA_NAME_VERSION (var);
384 tmp.instantiated_below = instantiated_below->index;
385 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
387 if (!*slot)
388 *slot = new_scev_info_str (instantiated_below, var);
389 res = (struct scev_info_str *) *slot;
391 return &res->chrec;
394 /* Return true when CHREC contains symbolic names defined in
395 LOOP_NB. */
397 bool
398 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
400 int i, n;
402 if (chrec == NULL_TREE)
403 return false;
405 if (is_gimple_min_invariant (chrec))
406 return false;
408 if (TREE_CODE (chrec) == SSA_NAME)
410 gimple def;
411 loop_p def_loop, loop;
413 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
414 return false;
416 def = SSA_NAME_DEF_STMT (chrec);
417 def_loop = loop_containing_stmt (def);
418 loop = get_loop (cfun, loop_nb);
420 if (def_loop == NULL)
421 return false;
423 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
424 return true;
426 return false;
429 n = TREE_OPERAND_LENGTH (chrec);
430 for (i = 0; i < n; i++)
431 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
432 loop_nb))
433 return true;
434 return false;
437 /* Return true when PHI is a loop-phi-node. */
439 static bool
440 loop_phi_node_p (gimple phi)
442 /* The implementation of this function is based on the following
443 property: "all the loop-phi-nodes of a loop are contained in the
444 loop's header basic block". */
446 return loop_containing_stmt (phi)->header == gimple_bb (phi);
449 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
450 In general, in the case of multivariate evolutions we want to get
451 the evolution in different loops. LOOP specifies the level for
452 which to get the evolution.
454 Example:
456 | for (j = 0; j < 100; j++)
458 | for (k = 0; k < 100; k++)
460 | i = k + j; - Here the value of i is a function of j, k.
462 | ... = i - Here the value of i is a function of j.
464 | ... = i - Here the value of i is a scalar.
466 Example:
468 | i_0 = ...
469 | loop_1 10 times
470 | i_1 = phi (i_0, i_2)
471 | i_2 = i_1 + 2
472 | endloop
474 This loop has the same effect as:
475 LOOP_1 has the same effect as:
477 | i_1 = i_0 + 20
479 The overall effect of the loop, "i_0 + 20" in the previous example,
480 is obtained by passing in the parameters: LOOP = 1,
481 EVOLUTION_FN = {i_0, +, 2}_1.
484 tree
485 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
487 bool val = false;
489 if (evolution_fn == chrec_dont_know)
490 return chrec_dont_know;
492 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
494 struct loop *inner_loop = get_chrec_loop (evolution_fn);
496 if (inner_loop == loop
497 || flow_loop_nested_p (loop, inner_loop))
499 tree nb_iter = number_of_latch_executions (inner_loop);
501 if (nb_iter == chrec_dont_know)
502 return chrec_dont_know;
503 else
505 tree res;
507 /* evolution_fn is the evolution function in LOOP. Get
508 its value in the nb_iter-th iteration. */
509 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
511 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
512 res = instantiate_parameters (loop, res);
514 /* Continue the computation until ending on a parent of LOOP. */
515 return compute_overall_effect_of_inner_loop (loop, res);
518 else
519 return evolution_fn;
522 /* If the evolution function is an invariant, there is nothing to do. */
523 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
524 return evolution_fn;
526 else
527 return chrec_dont_know;
530 /* Associate CHREC to SCALAR. */
532 static void
533 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
535 tree *scalar_info;
537 if (TREE_CODE (scalar) != SSA_NAME)
538 return;
540 scalar_info = find_var_scev_info (instantiated_below, scalar);
542 if (dump_file)
544 if (dump_flags & TDF_SCEV)
546 fprintf (dump_file, "(set_scalar_evolution \n");
547 fprintf (dump_file, " instantiated_below = %d \n",
548 instantiated_below->index);
549 fprintf (dump_file, " (scalar = ");
550 print_generic_expr (dump_file, scalar, 0);
551 fprintf (dump_file, ")\n (scalar_evolution = ");
552 print_generic_expr (dump_file, chrec, 0);
553 fprintf (dump_file, "))\n");
555 if (dump_flags & TDF_STATS)
556 nb_set_scev++;
559 *scalar_info = chrec;
562 /* Retrieve the chrec associated to SCALAR instantiated below
563 INSTANTIATED_BELOW block. */
565 static tree
566 get_scalar_evolution (basic_block instantiated_below, tree scalar)
568 tree res;
570 if (dump_file)
572 if (dump_flags & TDF_SCEV)
574 fprintf (dump_file, "(get_scalar_evolution \n");
575 fprintf (dump_file, " (scalar = ");
576 print_generic_expr (dump_file, scalar, 0);
577 fprintf (dump_file, ")\n");
579 if (dump_flags & TDF_STATS)
580 nb_get_scev++;
583 switch (TREE_CODE (scalar))
585 case SSA_NAME:
586 res = *find_var_scev_info (instantiated_below, scalar);
587 break;
589 case REAL_CST:
590 case FIXED_CST:
591 case INTEGER_CST:
592 res = scalar;
593 break;
595 default:
596 res = chrec_not_analyzed_yet;
597 break;
600 if (dump_file && (dump_flags & TDF_SCEV))
602 fprintf (dump_file, " (scalar_evolution = ");
603 print_generic_expr (dump_file, res, 0);
604 fprintf (dump_file, "))\n");
607 return res;
610 /* Helper function for add_to_evolution. Returns the evolution
611 function for an assignment of the form "a = b + c", where "a" and
612 "b" are on the strongly connected component. CHREC_BEFORE is the
613 information that we already have collected up to this point.
614 TO_ADD is the evolution of "c".
616 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
617 evolution the expression TO_ADD, otherwise construct an evolution
618 part for this loop. */
620 static tree
621 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
622 gimple at_stmt)
624 tree type, left, right;
625 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
627 switch (TREE_CODE (chrec_before))
629 case POLYNOMIAL_CHREC:
630 chloop = get_chrec_loop (chrec_before);
631 if (chloop == loop
632 || flow_loop_nested_p (chloop, loop))
634 unsigned var;
636 type = chrec_type (chrec_before);
638 /* When there is no evolution part in this loop, build it. */
639 if (chloop != loop)
641 var = loop_nb;
642 left = chrec_before;
643 right = SCALAR_FLOAT_TYPE_P (type)
644 ? build_real (type, dconst0)
645 : build_int_cst (type, 0);
647 else
649 var = CHREC_VARIABLE (chrec_before);
650 left = CHREC_LEFT (chrec_before);
651 right = CHREC_RIGHT (chrec_before);
654 to_add = chrec_convert (type, to_add, at_stmt);
655 right = chrec_convert_rhs (type, right, at_stmt);
656 right = chrec_fold_plus (chrec_type (right), right, to_add);
657 return build_polynomial_chrec (var, left, right);
659 else
661 gcc_assert (flow_loop_nested_p (loop, chloop));
663 /* Search the evolution in LOOP_NB. */
664 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
665 to_add, at_stmt);
666 right = CHREC_RIGHT (chrec_before);
667 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
668 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
669 left, right);
672 default:
673 /* These nodes do not depend on a loop. */
674 if (chrec_before == chrec_dont_know)
675 return chrec_dont_know;
677 left = chrec_before;
678 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
679 return build_polynomial_chrec (loop_nb, left, right);
683 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
684 of LOOP_NB.
686 Description (provided for completeness, for those who read code in
687 a plane, and for my poor 62 bytes brain that would have forgotten
688 all this in the next two or three months):
690 The algorithm of translation of programs from the SSA representation
691 into the chrecs syntax is based on a pattern matching. After having
692 reconstructed the overall tree expression for a loop, there are only
693 two cases that can arise:
695 1. a = loop-phi (init, a + expr)
696 2. a = loop-phi (init, expr)
698 where EXPR is either a scalar constant with respect to the analyzed
699 loop (this is a degree 0 polynomial), or an expression containing
700 other loop-phi definitions (these are higher degree polynomials).
702 Examples:
705 | init = ...
706 | loop_1
707 | a = phi (init, a + 5)
708 | endloop
711 | inita = ...
712 | initb = ...
713 | loop_1
714 | a = phi (inita, 2 * b + 3)
715 | b = phi (initb, b + 1)
716 | endloop
718 For the first case, the semantics of the SSA representation is:
720 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
722 that is, there is a loop index "x" that determines the scalar value
723 of the variable during the loop execution. During the first
724 iteration, the value is that of the initial condition INIT, while
725 during the subsequent iterations, it is the sum of the initial
726 condition with the sum of all the values of EXPR from the initial
727 iteration to the before last considered iteration.
729 For the second case, the semantics of the SSA program is:
731 | a (x) = init, if x = 0;
732 | expr (x - 1), otherwise.
734 The second case corresponds to the PEELED_CHREC, whose syntax is
735 close to the syntax of a loop-phi-node:
737 | phi (init, expr) vs. (init, expr)_x
739 The proof of the translation algorithm for the first case is a
740 proof by structural induction based on the degree of EXPR.
742 Degree 0:
743 When EXPR is a constant with respect to the analyzed loop, or in
744 other words when EXPR is a polynomial of degree 0, the evolution of
745 the variable A in the loop is an affine function with an initial
746 condition INIT, and a step EXPR. In order to show this, we start
747 from the semantics of the SSA representation:
749 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
751 and since "expr (j)" is a constant with respect to "j",
753 f (x) = init + x * expr
755 Finally, based on the semantics of the pure sum chrecs, by
756 identification we get the corresponding chrecs syntax:
758 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
759 f (x) -> {init, +, expr}_x
761 Higher degree:
762 Suppose that EXPR is a polynomial of degree N with respect to the
763 analyzed loop_x for which we have already determined that it is
764 written under the chrecs syntax:
766 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
768 We start from the semantics of the SSA program:
770 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
772 | f (x) = init + \sum_{j = 0}^{x - 1}
773 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
775 | f (x) = init + \sum_{j = 0}^{x - 1}
776 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
778 | f (x) = init + \sum_{k = 0}^{n - 1}
779 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
781 | f (x) = init + \sum_{k = 0}^{n - 1}
782 | (b_k * \binom{x}{k + 1})
784 | f (x) = init + b_0 * \binom{x}{1} + ...
785 | + b_{n-1} * \binom{x}{n}
787 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
788 | + b_{n-1} * \binom{x}{n}
791 And finally from the definition of the chrecs syntax, we identify:
792 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
794 This shows the mechanism that stands behind the add_to_evolution
795 function. An important point is that the use of symbolic
796 parameters avoids the need of an analysis schedule.
798 Example:
800 | inita = ...
801 | initb = ...
802 | loop_1
803 | a = phi (inita, a + 2 + b)
804 | b = phi (initb, b + 1)
805 | endloop
807 When analyzing "a", the algorithm keeps "b" symbolically:
809 | a -> {inita, +, 2 + b}_1
811 Then, after instantiation, the analyzer ends on the evolution:
813 | a -> {inita, +, 2 + initb, +, 1}_1
817 static tree
818 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
819 tree to_add, gimple at_stmt)
821 tree type = chrec_type (to_add);
822 tree res = NULL_TREE;
824 if (to_add == NULL_TREE)
825 return chrec_before;
827 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
828 instantiated at this point. */
829 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
830 /* This should not happen. */
831 return chrec_dont_know;
833 if (dump_file && (dump_flags & TDF_SCEV))
835 fprintf (dump_file, "(add_to_evolution \n");
836 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
837 fprintf (dump_file, " (chrec_before = ");
838 print_generic_expr (dump_file, chrec_before, 0);
839 fprintf (dump_file, ")\n (to_add = ");
840 print_generic_expr (dump_file, to_add, 0);
841 fprintf (dump_file, ")\n");
844 if (code == MINUS_EXPR)
845 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
846 ? build_real (type, dconstm1)
847 : build_int_cst_type (type, -1));
849 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
851 if (dump_file && (dump_flags & TDF_SCEV))
853 fprintf (dump_file, " (res = ");
854 print_generic_expr (dump_file, res, 0);
855 fprintf (dump_file, "))\n");
858 return res;
863 /* This section selects the loops that will be good candidates for the
864 scalar evolution analysis. For the moment, greedily select all the
865 loop nests we could analyze. */
867 /* For a loop with a single exit edge, return the COND_EXPR that
868 guards the exit edge. If the expression is too difficult to
869 analyze, then give up. */
871 gimple
872 get_loop_exit_condition (const struct loop *loop)
874 gimple res = NULL;
875 edge exit_edge = single_exit (loop);
877 if (dump_file && (dump_flags & TDF_SCEV))
878 fprintf (dump_file, "(get_loop_exit_condition \n ");
880 if (exit_edge)
882 gimple stmt;
884 stmt = last_stmt (exit_edge->src);
885 if (gimple_code (stmt) == GIMPLE_COND)
886 res = stmt;
889 if (dump_file && (dump_flags & TDF_SCEV))
891 print_gimple_stmt (dump_file, res, 0, 0);
892 fprintf (dump_file, ")\n");
895 return res;
899 /* Depth first search algorithm. */
901 typedef enum t_bool {
902 t_false,
903 t_true,
904 t_dont_know
905 } t_bool;
908 static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
910 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
911 Return true if the strongly connected component has been found. */
913 static t_bool
914 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
915 tree type, tree rhs0, enum tree_code code, tree rhs1,
916 gimple halting_phi, tree *evolution_of_loop, int limit)
918 t_bool res = t_false;
919 tree evol;
921 switch (code)
923 case POINTER_PLUS_EXPR:
924 case PLUS_EXPR:
925 if (TREE_CODE (rhs0) == SSA_NAME)
927 if (TREE_CODE (rhs1) == SSA_NAME)
929 /* Match an assignment under the form:
930 "a = b + c". */
932 /* We want only assignments of form "name + name" contribute to
933 LIMIT, as the other cases do not necessarily contribute to
934 the complexity of the expression. */
935 limit++;
937 evol = *evolution_of_loop;
938 res = follow_ssa_edge
939 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
941 if (res == t_true)
942 *evolution_of_loop = add_to_evolution
943 (loop->num,
944 chrec_convert (type, evol, at_stmt),
945 code, rhs1, at_stmt);
947 else if (res == t_false)
949 res = follow_ssa_edge
950 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
951 evolution_of_loop, limit);
953 if (res == t_true)
954 *evolution_of_loop = add_to_evolution
955 (loop->num,
956 chrec_convert (type, *evolution_of_loop, at_stmt),
957 code, rhs0, at_stmt);
959 else if (res == t_dont_know)
960 *evolution_of_loop = chrec_dont_know;
963 else if (res == t_dont_know)
964 *evolution_of_loop = chrec_dont_know;
967 else
969 /* Match an assignment under the form:
970 "a = b + ...". */
971 res = follow_ssa_edge
972 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
973 evolution_of_loop, limit);
974 if (res == t_true)
975 *evolution_of_loop = add_to_evolution
976 (loop->num, chrec_convert (type, *evolution_of_loop,
977 at_stmt),
978 code, rhs1, at_stmt);
980 else if (res == t_dont_know)
981 *evolution_of_loop = chrec_dont_know;
985 else if (TREE_CODE (rhs1) == SSA_NAME)
987 /* Match an assignment under the form:
988 "a = ... + c". */
989 res = follow_ssa_edge
990 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
991 evolution_of_loop, limit);
992 if (res == t_true)
993 *evolution_of_loop = add_to_evolution
994 (loop->num, chrec_convert (type, *evolution_of_loop,
995 at_stmt),
996 code, rhs0, at_stmt);
998 else if (res == t_dont_know)
999 *evolution_of_loop = chrec_dont_know;
1002 else
1003 /* Otherwise, match an assignment under the form:
1004 "a = ... + ...". */
1005 /* And there is nothing to do. */
1006 res = t_false;
1007 break;
1009 case MINUS_EXPR:
1010 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1011 if (TREE_CODE (rhs0) == SSA_NAME)
1013 /* Match an assignment under the form:
1014 "a = b - ...". */
1016 /* We want only assignments of form "name - name" contribute to
1017 LIMIT, as the other cases do not necessarily contribute to
1018 the complexity of the expression. */
1019 if (TREE_CODE (rhs1) == SSA_NAME)
1020 limit++;
1022 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1023 evolution_of_loop, limit);
1024 if (res == t_true)
1025 *evolution_of_loop = add_to_evolution
1026 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1027 MINUS_EXPR, rhs1, at_stmt);
1029 else if (res == t_dont_know)
1030 *evolution_of_loop = chrec_dont_know;
1032 else
1033 /* Otherwise, match an assignment under the form:
1034 "a = ... - ...". */
1035 /* And there is nothing to do. */
1036 res = t_false;
1037 break;
1039 default:
1040 res = t_false;
1043 return res;
1046 /* Follow the ssa edge into the expression EXPR.
1047 Return true if the strongly connected component has been found. */
1049 static t_bool
1050 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1051 gimple halting_phi, tree *evolution_of_loop, int limit)
1053 enum tree_code code = TREE_CODE (expr);
1054 tree type = TREE_TYPE (expr), rhs0, rhs1;
1055 t_bool res;
1057 /* The EXPR is one of the following cases:
1058 - an SSA_NAME,
1059 - an INTEGER_CST,
1060 - a PLUS_EXPR,
1061 - a POINTER_PLUS_EXPR,
1062 - a MINUS_EXPR,
1063 - an ASSERT_EXPR,
1064 - other cases are not yet handled. */
1066 switch (code)
1068 CASE_CONVERT:
1069 /* This assignment is under the form "a_1 = (cast) rhs. */
1070 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1071 halting_phi, evolution_of_loop, limit);
1072 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1073 break;
1075 case INTEGER_CST:
1076 /* This assignment is under the form "a_1 = 7". */
1077 res = t_false;
1078 break;
1080 case SSA_NAME:
1081 /* This assignment is under the form: "a_1 = b_2". */
1082 res = follow_ssa_edge
1083 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1084 break;
1086 case POINTER_PLUS_EXPR:
1087 case PLUS_EXPR:
1088 case MINUS_EXPR:
1089 /* This case is under the form "rhs0 +- rhs1". */
1090 rhs0 = TREE_OPERAND (expr, 0);
1091 rhs1 = TREE_OPERAND (expr, 1);
1092 type = TREE_TYPE (rhs0);
1093 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1094 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1095 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1096 halting_phi, evolution_of_loop, limit);
1097 break;
1099 case ADDR_EXPR:
1100 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1101 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1103 expr = TREE_OPERAND (expr, 0);
1104 rhs0 = TREE_OPERAND (expr, 0);
1105 rhs1 = TREE_OPERAND (expr, 1);
1106 type = TREE_TYPE (rhs0);
1107 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1108 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1109 res = follow_ssa_edge_binary (loop, at_stmt, type,
1110 rhs0, POINTER_PLUS_EXPR, rhs1,
1111 halting_phi, evolution_of_loop, limit);
1113 else
1114 res = t_false;
1115 break;
1117 case ASSERT_EXPR:
1118 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1119 It must be handled as a copy assignment of the form a_1 = a_2. */
1120 rhs0 = ASSERT_EXPR_VAR (expr);
1121 if (TREE_CODE (rhs0) == SSA_NAME)
1122 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1123 halting_phi, evolution_of_loop, limit);
1124 else
1125 res = t_false;
1126 break;
1128 default:
1129 res = t_false;
1130 break;
1133 return res;
1136 /* Follow the ssa edge into the right hand side of an assignment STMT.
1137 Return true if the strongly connected component has been found. */
1139 static t_bool
1140 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1141 gimple halting_phi, tree *evolution_of_loop, int limit)
1143 enum tree_code code = gimple_assign_rhs_code (stmt);
1144 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1145 t_bool res;
1147 switch (code)
1149 CASE_CONVERT:
1150 /* This assignment is under the form "a_1 = (cast) rhs. */
1151 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1152 halting_phi, evolution_of_loop, limit);
1153 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1154 break;
1156 case POINTER_PLUS_EXPR:
1157 case PLUS_EXPR:
1158 case MINUS_EXPR:
1159 rhs1 = gimple_assign_rhs1 (stmt);
1160 rhs2 = gimple_assign_rhs2 (stmt);
1161 type = TREE_TYPE (rhs1);
1162 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1163 halting_phi, evolution_of_loop, limit);
1164 break;
1166 default:
1167 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1168 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1169 halting_phi, evolution_of_loop, limit);
1170 else
1171 res = t_false;
1172 break;
1175 return res;
1178 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1180 static bool
1181 backedge_phi_arg_p (gimple phi, int i)
1183 const_edge e = gimple_phi_arg_edge (phi, i);
1185 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1186 about updating it anywhere, and this should work as well most of the
1187 time. */
1188 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1189 return true;
1191 return false;
1194 /* Helper function for one branch of the condition-phi-node. Return
1195 true if the strongly connected component has been found following
1196 this path. */
1198 static inline t_bool
1199 follow_ssa_edge_in_condition_phi_branch (int i,
1200 struct loop *loop,
1201 gimple condition_phi,
1202 gimple halting_phi,
1203 tree *evolution_of_branch,
1204 tree init_cond, int limit)
1206 tree branch = PHI_ARG_DEF (condition_phi, i);
1207 *evolution_of_branch = chrec_dont_know;
1209 /* Do not follow back edges (they must belong to an irreducible loop, which
1210 we really do not want to worry about). */
1211 if (backedge_phi_arg_p (condition_phi, i))
1212 return t_false;
1214 if (TREE_CODE (branch) == SSA_NAME)
1216 *evolution_of_branch = init_cond;
1217 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1218 evolution_of_branch, limit);
1221 /* This case occurs when one of the condition branches sets
1222 the variable to a constant: i.e. a phi-node like
1223 "a_2 = PHI <a_7(5), 2(6)>;".
1225 FIXME: This case have to be refined correctly:
1226 in some cases it is possible to say something better than
1227 chrec_dont_know, for example using a wrap-around notation. */
1228 return t_false;
1231 /* This function merges the branches of a condition-phi-node in a
1232 loop. */
1234 static t_bool
1235 follow_ssa_edge_in_condition_phi (struct loop *loop,
1236 gimple condition_phi,
1237 gimple halting_phi,
1238 tree *evolution_of_loop, int limit)
1240 int i, n;
1241 tree init = *evolution_of_loop;
1242 tree evolution_of_branch;
1243 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1244 halting_phi,
1245 &evolution_of_branch,
1246 init, limit);
1247 if (res == t_false || res == t_dont_know)
1248 return res;
1250 *evolution_of_loop = evolution_of_branch;
1252 n = gimple_phi_num_args (condition_phi);
1253 for (i = 1; i < n; i++)
1255 /* Quickly give up when the evolution of one of the branches is
1256 not known. */
1257 if (*evolution_of_loop == chrec_dont_know)
1258 return t_true;
1260 /* Increase the limit by the PHI argument number to avoid exponential
1261 time and memory complexity. */
1262 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1263 halting_phi,
1264 &evolution_of_branch,
1265 init, limit + i);
1266 if (res == t_false || res == t_dont_know)
1267 return res;
1269 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1270 evolution_of_branch);
1273 return t_true;
1276 /* Follow an SSA edge in an inner loop. It computes the overall
1277 effect of the loop, and following the symbolic initial conditions,
1278 it follows the edges in the parent loop. The inner loop is
1279 considered as a single statement. */
1281 static t_bool
1282 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1283 gimple loop_phi_node,
1284 gimple halting_phi,
1285 tree *evolution_of_loop, int limit)
1287 struct loop *loop = loop_containing_stmt (loop_phi_node);
1288 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1290 /* Sometimes, the inner loop is too difficult to analyze, and the
1291 result of the analysis is a symbolic parameter. */
1292 if (ev == PHI_RESULT (loop_phi_node))
1294 t_bool res = t_false;
1295 int i, n = gimple_phi_num_args (loop_phi_node);
1297 for (i = 0; i < n; i++)
1299 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1300 basic_block bb;
1302 /* Follow the edges that exit the inner loop. */
1303 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1304 if (!flow_bb_inside_loop_p (loop, bb))
1305 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1306 arg, halting_phi,
1307 evolution_of_loop, limit);
1308 if (res == t_true)
1309 break;
1312 /* If the path crosses this loop-phi, give up. */
1313 if (res == t_true)
1314 *evolution_of_loop = chrec_dont_know;
1316 return res;
1319 /* Otherwise, compute the overall effect of the inner loop. */
1320 ev = compute_overall_effect_of_inner_loop (loop, ev);
1321 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1322 evolution_of_loop, limit);
1325 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1326 path that is analyzed on the return walk. */
1328 static t_bool
1329 follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
1330 tree *evolution_of_loop, int limit)
1332 struct loop *def_loop;
1334 if (gimple_nop_p (def))
1335 return t_false;
1337 /* Give up if the path is longer than the MAX that we allow. */
1338 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1339 return t_dont_know;
1341 def_loop = loop_containing_stmt (def);
1343 switch (gimple_code (def))
1345 case GIMPLE_PHI:
1346 if (!loop_phi_node_p (def))
1347 /* DEF is a condition-phi-node. Follow the branches, and
1348 record their evolutions. Finally, merge the collected
1349 information and set the approximation to the main
1350 variable. */
1351 return follow_ssa_edge_in_condition_phi
1352 (loop, def, halting_phi, evolution_of_loop, limit);
1354 /* When the analyzed phi is the halting_phi, the
1355 depth-first search is over: we have found a path from
1356 the halting_phi to itself in the loop. */
1357 if (def == halting_phi)
1358 return t_true;
1360 /* Otherwise, the evolution of the HALTING_PHI depends
1361 on the evolution of another loop-phi-node, i.e. the
1362 evolution function is a higher degree polynomial. */
1363 if (def_loop == loop)
1364 return t_false;
1366 /* Inner loop. */
1367 if (flow_loop_nested_p (loop, def_loop))
1368 return follow_ssa_edge_inner_loop_phi
1369 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1371 /* Outer loop. */
1372 return t_false;
1374 case GIMPLE_ASSIGN:
1375 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1376 evolution_of_loop, limit);
1378 default:
1379 /* At this level of abstraction, the program is just a set
1380 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1381 other node to be handled. */
1382 return t_false;
1387 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1388 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1390 # i_17 = PHI <i_13(5), 0(3)>
1391 # _20 = PHI <_5(5), start_4(D)(3)>
1393 i_13 = i_17 + 1;
1394 _5 = start_4(D) + i_13;
1396 Though variable _20 appears as a PEELED_CHREC in the form of
1397 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1399 See PR41488. */
1401 static tree
1402 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1404 aff_tree aff1, aff2;
1405 tree ev, left, right, type, step_val;
1406 pointer_map_t *peeled_chrec_map = NULL;
1408 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1409 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1410 return chrec_dont_know;
1412 left = CHREC_LEFT (ev);
1413 right = CHREC_RIGHT (ev);
1414 type = TREE_TYPE (left);
1415 step_val = chrec_fold_plus (type, init_cond, right);
1417 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1418 if "left" equals to "init + right". */
1419 if (operand_equal_p (left, step_val, 0))
1421 if (dump_file && (dump_flags & TDF_SCEV))
1422 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1424 return build_polynomial_chrec (loop->num, init_cond, right);
1427 /* Try harder to check if they are equal. */
1428 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1429 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1430 free_affine_expand_cache (&peeled_chrec_map);
1431 aff_combination_scale (&aff2, double_int_minus_one);
1432 aff_combination_add (&aff1, &aff2);
1434 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1435 if "left" equals to "init + right". */
1436 if (aff_combination_zero_p (&aff1))
1438 if (dump_file && (dump_flags & TDF_SCEV))
1439 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1441 return build_polynomial_chrec (loop->num, init_cond, right);
1443 return chrec_dont_know;
1446 /* Given a LOOP_PHI_NODE, this function determines the evolution
1447 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1449 static tree
1450 analyze_evolution_in_loop (gimple loop_phi_node,
1451 tree init_cond)
1453 int i, n = gimple_phi_num_args (loop_phi_node);
1454 tree evolution_function = chrec_not_analyzed_yet;
1455 struct loop *loop = loop_containing_stmt (loop_phi_node);
1456 basic_block bb;
1457 static bool simplify_peeled_chrec_p = true;
1459 if (dump_file && (dump_flags & TDF_SCEV))
1461 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1462 fprintf (dump_file, " (loop_phi_node = ");
1463 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1464 fprintf (dump_file, ")\n");
1467 for (i = 0; i < n; i++)
1469 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1470 gimple ssa_chain;
1471 tree ev_fn;
1472 t_bool res;
1474 /* Select the edges that enter the loop body. */
1475 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1476 if (!flow_bb_inside_loop_p (loop, bb))
1477 continue;
1479 if (TREE_CODE (arg) == SSA_NAME)
1481 bool val = false;
1483 ssa_chain = SSA_NAME_DEF_STMT (arg);
1485 /* Pass in the initial condition to the follow edge function. */
1486 ev_fn = init_cond;
1487 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1489 /* If ev_fn has no evolution in the inner loop, and the
1490 init_cond is not equal to ev_fn, then we have an
1491 ambiguity between two possible values, as we cannot know
1492 the number of iterations at this point. */
1493 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1494 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1495 && !operand_equal_p (init_cond, ev_fn, 0))
1496 ev_fn = chrec_dont_know;
1498 else
1499 res = t_false;
1501 /* When it is impossible to go back on the same
1502 loop_phi_node by following the ssa edges, the
1503 evolution is represented by a peeled chrec, i.e. the
1504 first iteration, EV_FN has the value INIT_COND, then
1505 all the other iterations it has the value of ARG.
1506 For the moment, PEELED_CHREC nodes are not built. */
1507 if (res != t_true)
1509 ev_fn = chrec_dont_know;
1510 /* Try to recognize POLYNOMIAL_CHREC which appears in
1511 the form of PEELED_CHREC, but guard the process with
1512 a bool variable to keep the analyzer from infinite
1513 recurrence for real PEELED_RECs. */
1514 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1516 simplify_peeled_chrec_p = false;
1517 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1518 simplify_peeled_chrec_p = true;
1522 /* When there are multiple back edges of the loop (which in fact never
1523 happens currently, but nevertheless), merge their evolutions. */
1524 evolution_function = chrec_merge (evolution_function, ev_fn);
1527 if (dump_file && (dump_flags & TDF_SCEV))
1529 fprintf (dump_file, " (evolution_function = ");
1530 print_generic_expr (dump_file, evolution_function, 0);
1531 fprintf (dump_file, "))\n");
1534 return evolution_function;
1537 /* Given a loop-phi-node, return the initial conditions of the
1538 variable on entry of the loop. When the CCP has propagated
1539 constants into the loop-phi-node, the initial condition is
1540 instantiated, otherwise the initial condition is kept symbolic.
1541 This analyzer does not analyze the evolution outside the current
1542 loop, and leaves this task to the on-demand tree reconstructor. */
1544 static tree
1545 analyze_initial_condition (gimple loop_phi_node)
1547 int i, n;
1548 tree init_cond = chrec_not_analyzed_yet;
1549 struct loop *loop = loop_containing_stmt (loop_phi_node);
1551 if (dump_file && (dump_flags & TDF_SCEV))
1553 fprintf (dump_file, "(analyze_initial_condition \n");
1554 fprintf (dump_file, " (loop_phi_node = \n");
1555 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1556 fprintf (dump_file, ")\n");
1559 n = gimple_phi_num_args (loop_phi_node);
1560 for (i = 0; i < n; i++)
1562 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1563 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1565 /* When the branch is oriented to the loop's body, it does
1566 not contribute to the initial condition. */
1567 if (flow_bb_inside_loop_p (loop, bb))
1568 continue;
1570 if (init_cond == chrec_not_analyzed_yet)
1572 init_cond = branch;
1573 continue;
1576 if (TREE_CODE (branch) == SSA_NAME)
1578 init_cond = chrec_dont_know;
1579 break;
1582 init_cond = chrec_merge (init_cond, branch);
1585 /* Ooops -- a loop without an entry??? */
1586 if (init_cond == chrec_not_analyzed_yet)
1587 init_cond = chrec_dont_know;
1589 /* During early loop unrolling we do not have fully constant propagated IL.
1590 Handle degenerate PHIs here to not miss important unrollings. */
1591 if (TREE_CODE (init_cond) == SSA_NAME)
1593 gimple def = SSA_NAME_DEF_STMT (init_cond);
1594 tree res;
1595 if (gimple_code (def) == GIMPLE_PHI
1596 && (res = degenerate_phi_result (def)) != NULL_TREE
1597 /* Only allow invariants here, otherwise we may break
1598 loop-closed SSA form. */
1599 && is_gimple_min_invariant (res))
1600 init_cond = res;
1603 if (dump_file && (dump_flags & TDF_SCEV))
1605 fprintf (dump_file, " (init_cond = ");
1606 print_generic_expr (dump_file, init_cond, 0);
1607 fprintf (dump_file, "))\n");
1610 return init_cond;
1613 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1615 static tree
1616 interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
1618 tree res;
1619 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1620 tree init_cond;
1622 if (phi_loop != loop)
1624 struct loop *subloop;
1625 tree evolution_fn = analyze_scalar_evolution
1626 (phi_loop, PHI_RESULT (loop_phi_node));
1628 /* Dive one level deeper. */
1629 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1631 /* Interpret the subloop. */
1632 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1633 return res;
1636 /* Otherwise really interpret the loop phi. */
1637 init_cond = analyze_initial_condition (loop_phi_node);
1638 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1640 /* Verify we maintained the correct initial condition throughout
1641 possible conversions in the SSA chain. */
1642 if (res != chrec_dont_know)
1644 tree new_init = res;
1645 if (CONVERT_EXPR_P (res)
1646 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1647 new_init = fold_convert (TREE_TYPE (res),
1648 CHREC_LEFT (TREE_OPERAND (res, 0)));
1649 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1650 new_init = CHREC_LEFT (res);
1651 STRIP_USELESS_TYPE_CONVERSION (new_init);
1652 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1653 || !operand_equal_p (init_cond, new_init, 0))
1654 return chrec_dont_know;
1657 return res;
1660 /* This function merges the branches of a condition-phi-node,
1661 contained in the outermost loop, and whose arguments are already
1662 analyzed. */
1664 static tree
1665 interpret_condition_phi (struct loop *loop, gimple condition_phi)
1667 int i, n = gimple_phi_num_args (condition_phi);
1668 tree res = chrec_not_analyzed_yet;
1670 for (i = 0; i < n; i++)
1672 tree branch_chrec;
1674 if (backedge_phi_arg_p (condition_phi, i))
1676 res = chrec_dont_know;
1677 break;
1680 branch_chrec = analyze_scalar_evolution
1681 (loop, PHI_ARG_DEF (condition_phi, i));
1683 res = chrec_merge (res, branch_chrec);
1686 return res;
1689 /* Interpret the operation RHS1 OP RHS2. If we didn't
1690 analyze this node before, follow the definitions until ending
1691 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1692 return path, this function propagates evolutions (ala constant copy
1693 propagation). OPND1 is not a GIMPLE expression because we could
1694 analyze the effect of an inner loop: see interpret_loop_phi. */
1696 static tree
1697 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1698 tree type, tree rhs1, enum tree_code code, tree rhs2)
1700 tree res, chrec1, chrec2;
1701 gimple def;
1703 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1705 if (is_gimple_min_invariant (rhs1))
1706 return chrec_convert (type, rhs1, at_stmt);
1708 if (code == SSA_NAME)
1709 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1710 at_stmt);
1712 if (code == ASSERT_EXPR)
1714 rhs1 = ASSERT_EXPR_VAR (rhs1);
1715 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1716 at_stmt);
1720 switch (code)
1722 case ADDR_EXPR:
1723 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1724 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1726 enum machine_mode mode;
1727 HOST_WIDE_INT bitsize, bitpos;
1728 int unsignedp;
1729 int volatilep = 0;
1730 tree base, offset;
1731 tree chrec3;
1732 tree unitpos;
1734 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1735 &bitsize, &bitpos, &offset,
1736 &mode, &unsignedp, &volatilep, false);
1738 if (TREE_CODE (base) == MEM_REF)
1740 rhs2 = TREE_OPERAND (base, 1);
1741 rhs1 = TREE_OPERAND (base, 0);
1743 chrec1 = analyze_scalar_evolution (loop, rhs1);
1744 chrec2 = analyze_scalar_evolution (loop, rhs2);
1745 chrec1 = chrec_convert (type, chrec1, at_stmt);
1746 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1747 chrec1 = instantiate_parameters (loop, chrec1);
1748 chrec2 = instantiate_parameters (loop, chrec2);
1749 res = chrec_fold_plus (type, chrec1, chrec2);
1751 else
1753 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1754 chrec1 = chrec_convert (type, chrec1, at_stmt);
1755 res = chrec1;
1758 if (offset != NULL_TREE)
1760 chrec2 = analyze_scalar_evolution (loop, offset);
1761 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1762 chrec2 = instantiate_parameters (loop, chrec2);
1763 res = chrec_fold_plus (type, res, chrec2);
1766 if (bitpos != 0)
1768 gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
1770 unitpos = size_int (bitpos / BITS_PER_UNIT);
1771 chrec3 = analyze_scalar_evolution (loop, unitpos);
1772 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1773 chrec3 = instantiate_parameters (loop, chrec3);
1774 res = chrec_fold_plus (type, res, chrec3);
1777 else
1778 res = chrec_dont_know;
1779 break;
1781 case POINTER_PLUS_EXPR:
1782 chrec1 = analyze_scalar_evolution (loop, rhs1);
1783 chrec2 = analyze_scalar_evolution (loop, rhs2);
1784 chrec1 = chrec_convert (type, chrec1, at_stmt);
1785 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1786 chrec1 = instantiate_parameters (loop, chrec1);
1787 chrec2 = instantiate_parameters (loop, chrec2);
1788 res = chrec_fold_plus (type, chrec1, chrec2);
1789 break;
1791 case PLUS_EXPR:
1792 chrec1 = analyze_scalar_evolution (loop, rhs1);
1793 chrec2 = analyze_scalar_evolution (loop, rhs2);
1794 chrec1 = chrec_convert (type, chrec1, at_stmt);
1795 chrec2 = chrec_convert (type, chrec2, at_stmt);
1796 chrec1 = instantiate_parameters (loop, chrec1);
1797 chrec2 = instantiate_parameters (loop, chrec2);
1798 res = chrec_fold_plus (type, chrec1, chrec2);
1799 break;
1801 case MINUS_EXPR:
1802 chrec1 = analyze_scalar_evolution (loop, rhs1);
1803 chrec2 = analyze_scalar_evolution (loop, rhs2);
1804 chrec1 = chrec_convert (type, chrec1, at_stmt);
1805 chrec2 = chrec_convert (type, chrec2, at_stmt);
1806 chrec1 = instantiate_parameters (loop, chrec1);
1807 chrec2 = instantiate_parameters (loop, chrec2);
1808 res = chrec_fold_minus (type, chrec1, chrec2);
1809 break;
1811 case NEGATE_EXPR:
1812 chrec1 = analyze_scalar_evolution (loop, rhs1);
1813 chrec1 = chrec_convert (type, chrec1, at_stmt);
1814 /* TYPE may be integer, real or complex, so use fold_convert. */
1815 chrec1 = instantiate_parameters (loop, chrec1);
1816 res = chrec_fold_multiply (type, chrec1,
1817 fold_convert (type, integer_minus_one_node));
1818 break;
1820 case BIT_NOT_EXPR:
1821 /* Handle ~X as -1 - X. */
1822 chrec1 = analyze_scalar_evolution (loop, rhs1);
1823 chrec1 = chrec_convert (type, chrec1, at_stmt);
1824 chrec1 = instantiate_parameters (loop, chrec1);
1825 res = chrec_fold_minus (type,
1826 fold_convert (type, integer_minus_one_node),
1827 chrec1);
1828 break;
1830 case MULT_EXPR:
1831 chrec1 = analyze_scalar_evolution (loop, rhs1);
1832 chrec2 = analyze_scalar_evolution (loop, rhs2);
1833 chrec1 = chrec_convert (type, chrec1, at_stmt);
1834 chrec2 = chrec_convert (type, chrec2, at_stmt);
1835 chrec1 = instantiate_parameters (loop, chrec1);
1836 chrec2 = instantiate_parameters (loop, chrec2);
1837 res = chrec_fold_multiply (type, chrec1, chrec2);
1838 break;
1840 CASE_CONVERT:
1841 /* In case we have a truncation of a widened operation that in
1842 the truncated type has undefined overflow behavior analyze
1843 the operation done in an unsigned type of the same precision
1844 as the final truncation. We cannot derive a scalar evolution
1845 for the widened operation but for the truncated result. */
1846 if (TREE_CODE (type) == INTEGER_TYPE
1847 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1848 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1849 && TYPE_OVERFLOW_UNDEFINED (type)
1850 && TREE_CODE (rhs1) == SSA_NAME
1851 && (def = SSA_NAME_DEF_STMT (rhs1))
1852 && is_gimple_assign (def)
1853 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1854 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1856 tree utype = unsigned_type_for (type);
1857 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1858 gimple_assign_rhs1 (def),
1859 gimple_assign_rhs_code (def),
1860 gimple_assign_rhs2 (def));
1862 else
1863 chrec1 = analyze_scalar_evolution (loop, rhs1);
1864 res = chrec_convert (type, chrec1, at_stmt);
1865 break;
1867 default:
1868 res = chrec_dont_know;
1869 break;
1872 return res;
1875 /* Interpret the expression EXPR. */
1877 static tree
1878 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1880 enum tree_code code;
1881 tree type = TREE_TYPE (expr), op0, op1;
1883 if (automatically_generated_chrec_p (expr))
1884 return expr;
1886 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1887 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1888 return chrec_dont_know;
1890 extract_ops_from_tree (expr, &code, &op0, &op1);
1892 return interpret_rhs_expr (loop, at_stmt, type,
1893 op0, code, op1);
1896 /* Interpret the rhs of the assignment STMT. */
1898 static tree
1899 interpret_gimple_assign (struct loop *loop, gimple stmt)
1901 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1902 enum tree_code code = gimple_assign_rhs_code (stmt);
1904 return interpret_rhs_expr (loop, stmt, type,
1905 gimple_assign_rhs1 (stmt), code,
1906 gimple_assign_rhs2 (stmt));
1911 /* This section contains all the entry points:
1912 - number_of_iterations_in_loop,
1913 - analyze_scalar_evolution,
1914 - instantiate_parameters.
1917 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1918 common ancestor of DEF_LOOP and USE_LOOP. */
1920 static tree
1921 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1922 struct loop *def_loop,
1923 tree ev)
1925 bool val;
1926 tree res;
1928 if (def_loop == wrto_loop)
1929 return ev;
1931 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1932 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1934 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
1935 return res;
1937 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1940 /* Helper recursive function. */
1942 static tree
1943 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1945 tree type = TREE_TYPE (var);
1946 gimple def;
1947 basic_block bb;
1948 struct loop *def_loop;
1950 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1951 return chrec_dont_know;
1953 if (TREE_CODE (var) != SSA_NAME)
1954 return interpret_expr (loop, NULL, var);
1956 def = SSA_NAME_DEF_STMT (var);
1957 bb = gimple_bb (def);
1958 def_loop = bb ? bb->loop_father : NULL;
1960 if (bb == NULL
1961 || !flow_bb_inside_loop_p (loop, bb))
1963 /* Keep the symbolic form. */
1964 res = var;
1965 goto set_and_end;
1968 if (res != chrec_not_analyzed_yet)
1970 if (loop != bb->loop_father)
1971 res = compute_scalar_evolution_in_loop
1972 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1974 goto set_and_end;
1977 if (loop != def_loop)
1979 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1980 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1982 goto set_and_end;
1985 switch (gimple_code (def))
1987 case GIMPLE_ASSIGN:
1988 res = interpret_gimple_assign (loop, def);
1989 break;
1991 case GIMPLE_PHI:
1992 if (loop_phi_node_p (def))
1993 res = interpret_loop_phi (loop, def);
1994 else
1995 res = interpret_condition_phi (loop, def);
1996 break;
1998 default:
1999 res = chrec_dont_know;
2000 break;
2003 set_and_end:
2005 /* Keep the symbolic form. */
2006 if (res == chrec_dont_know)
2007 res = var;
2009 if (loop == def_loop)
2010 set_scalar_evolution (block_before_loop (loop), var, res);
2012 return res;
2015 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2016 LOOP. LOOP is the loop in which the variable is used.
2018 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2019 pointer to the statement that uses this variable, in order to
2020 determine the evolution function of the variable, use the following
2021 calls:
2023 loop_p loop = loop_containing_stmt (stmt);
2024 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2025 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2028 tree
2029 analyze_scalar_evolution (struct loop *loop, tree var)
2031 tree res;
2033 if (dump_file && (dump_flags & TDF_SCEV))
2035 fprintf (dump_file, "(analyze_scalar_evolution \n");
2036 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2037 fprintf (dump_file, " (scalar = ");
2038 print_generic_expr (dump_file, var, 0);
2039 fprintf (dump_file, ")\n");
2042 res = get_scalar_evolution (block_before_loop (loop), var);
2043 res = analyze_scalar_evolution_1 (loop, var, res);
2045 if (dump_file && (dump_flags & TDF_SCEV))
2046 fprintf (dump_file, ")\n");
2048 return res;
2051 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2053 static tree
2054 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2056 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2059 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2060 WRTO_LOOP (which should be a superloop of USE_LOOP)
2062 FOLDED_CASTS is set to true if resolve_mixers used
2063 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2064 at the moment in order to keep things simple).
2066 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2067 example:
2069 for (i = 0; i < 100; i++) -- loop 1
2071 for (j = 0; j < 100; j++) -- loop 2
2073 k1 = i;
2074 k2 = j;
2076 use2 (k1, k2);
2078 for (t = 0; t < 100; t++) -- loop 3
2079 use3 (k1, k2);
2082 use1 (k1, k2);
2085 Both k1 and k2 are invariants in loop3, thus
2086 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2087 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2089 As they are invariant, it does not matter whether we consider their
2090 usage in loop 3 or loop 2, hence
2091 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2092 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2093 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2094 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2096 Similarly for their evolutions with respect to loop 1. The values of K2
2097 in the use in loop 2 vary independently on loop 1, thus we cannot express
2098 the evolution with respect to loop 1:
2099 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2100 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2101 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2102 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2104 The value of k2 in the use in loop 1 is known, though:
2105 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2106 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2109 static tree
2110 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2111 tree version, bool *folded_casts)
2113 bool val = false;
2114 tree ev = version, tmp;
2116 /* We cannot just do
2118 tmp = analyze_scalar_evolution (use_loop, version);
2119 ev = resolve_mixers (wrto_loop, tmp);
2121 as resolve_mixers would query the scalar evolution with respect to
2122 wrto_loop. For example, in the situation described in the function
2123 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2124 version = k2. Then
2126 analyze_scalar_evolution (use_loop, version) = k2
2128 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2129 is 100, which is a wrong result, since we are interested in the
2130 value in loop 3.
2132 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2133 each time checking that there is no evolution in the inner loop. */
2135 if (folded_casts)
2136 *folded_casts = false;
2137 while (1)
2139 tmp = analyze_scalar_evolution (use_loop, ev);
2140 ev = resolve_mixers (use_loop, tmp);
2142 if (folded_casts && tmp != ev)
2143 *folded_casts = true;
2145 if (use_loop == wrto_loop)
2146 return ev;
2148 /* If the value of the use changes in the inner loop, we cannot express
2149 its value in the outer loop (we might try to return interval chrec,
2150 but we do not have a user for it anyway) */
2151 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2152 || !val)
2153 return chrec_dont_know;
2155 use_loop = loop_outer (use_loop);
2160 /* Hashtable helpers for a temporary hash-table used when
2161 instantiating a CHREC or resolving mixers. For this use
2162 instantiated_below is always the same. */
2164 struct instantiate_cache_type
2166 htab_t map;
2167 vec<scev_info_str> entries;
2169 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2170 ~instantiate_cache_type ();
2171 tree get (unsigned slot) { return entries[slot].chrec; }
2172 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2175 instantiate_cache_type::~instantiate_cache_type ()
2177 if (map != NULL)
2179 htab_delete (map);
2180 entries.release ();
2184 /* Cache to avoid infinite recursion when instantiating an SSA name.
2185 Live during the outermost instantiate_scev or resolve_mixers call. */
2186 static instantiate_cache_type *global_cache;
2188 /* Computes a hash function for database element ELT. */
2190 static inline hashval_t
2191 hash_idx_scev_info (const void *elt_)
2193 unsigned idx = ((size_t) elt_) - 2;
2194 return hash_scev_info (&global_cache->entries[idx]);
2197 /* Compares database elements E1 and E2. */
2199 static inline int
2200 eq_idx_scev_info (const void *e1, const void *e2)
2202 unsigned idx1 = ((size_t) e1) - 2;
2203 return eq_scev_info (&global_cache->entries[idx1], e2);
2206 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2208 static unsigned
2209 get_instantiated_value_entry (instantiate_cache_type &cache,
2210 tree name, basic_block instantiate_below)
2212 if (!cache.map)
2214 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2215 cache.entries.create (10);
2218 scev_info_str e;
2219 e.name_version = SSA_NAME_VERSION (name);
2220 e.instantiated_below = instantiate_below->index;
2221 void **slot = htab_find_slot_with_hash (cache.map, &e,
2222 hash_scev_info (&e), INSERT);
2223 if (!*slot)
2225 e.chrec = chrec_not_analyzed_yet;
2226 *slot = (void *)(size_t)(cache.entries.length () + 2);
2227 cache.entries.safe_push (e);
2230 return ((size_t)*slot) - 2;
2234 /* Return the closed_loop_phi node for VAR. If there is none, return
2235 NULL_TREE. */
2237 static tree
2238 loop_closed_phi_def (tree var)
2240 struct loop *loop;
2241 edge exit;
2242 gimple phi;
2243 gimple_stmt_iterator psi;
2245 if (var == NULL_TREE
2246 || TREE_CODE (var) != SSA_NAME)
2247 return NULL_TREE;
2249 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2250 exit = single_exit (loop);
2251 if (!exit)
2252 return NULL_TREE;
2254 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2256 phi = gsi_stmt (psi);
2257 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2258 return PHI_RESULT (phi);
2261 return NULL_TREE;
2264 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2265 tree, bool, int);
2267 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2268 and EVOLUTION_LOOP, that were left under a symbolic form.
2270 CHREC is an SSA_NAME to be instantiated.
2272 CACHE is the cache of already instantiated values.
2274 FOLD_CONVERSIONS should be set to true when the conversions that
2275 may wrap in signed/pointer type are folded, as long as the value of
2276 the chrec is preserved.
2278 SIZE_EXPR is used for computing the size of the expression to be
2279 instantiated, and to stop if it exceeds some limit. */
2281 static tree
2282 instantiate_scev_name (basic_block instantiate_below,
2283 struct loop *evolution_loop, struct loop *inner_loop,
2284 tree chrec,
2285 bool fold_conversions,
2286 int size_expr)
2288 tree res;
2289 struct loop *def_loop;
2290 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2292 /* A parameter (or loop invariant and we do not want to include
2293 evolutions in outer loops), nothing to do. */
2294 if (!def_bb
2295 || loop_depth (def_bb->loop_father) == 0
2296 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2297 return chrec;
2299 /* We cache the value of instantiated variable to avoid exponential
2300 time complexity due to reevaluations. We also store the convenient
2301 value in the cache in order to prevent infinite recursion -- we do
2302 not want to instantiate the SSA_NAME if it is in a mixer
2303 structure. This is used for avoiding the instantiation of
2304 recursively defined functions, such as:
2306 | a_2 -> {0, +, 1, +, a_2}_1 */
2308 unsigned si = get_instantiated_value_entry (*global_cache,
2309 chrec, instantiate_below);
2310 if (global_cache->get (si) != chrec_not_analyzed_yet)
2311 return global_cache->get (si);
2313 /* On recursion return chrec_dont_know. */
2314 global_cache->set (si, chrec_dont_know);
2316 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2318 /* If the analysis yields a parametric chrec, instantiate the
2319 result again. */
2320 res = analyze_scalar_evolution (def_loop, chrec);
2322 /* Don't instantiate default definitions. */
2323 if (TREE_CODE (res) == SSA_NAME
2324 && SSA_NAME_IS_DEFAULT_DEF (res))
2327 /* Don't instantiate loop-closed-ssa phi nodes. */
2328 else if (TREE_CODE (res) == SSA_NAME
2329 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2330 > loop_depth (def_loop))
2332 if (res == chrec)
2333 res = loop_closed_phi_def (chrec);
2334 else
2335 res = chrec;
2337 /* When there is no loop_closed_phi_def, it means that the
2338 variable is not used after the loop: try to still compute the
2339 value of the variable when exiting the loop. */
2340 if (res == NULL_TREE)
2342 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2343 res = analyze_scalar_evolution (loop, chrec);
2344 res = compute_overall_effect_of_inner_loop (loop, res);
2345 res = instantiate_scev_r (instantiate_below, evolution_loop,
2346 inner_loop, res,
2347 fold_conversions, size_expr);
2349 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2350 gimple_bb (SSA_NAME_DEF_STMT (res))))
2351 res = chrec_dont_know;
2354 else if (res != chrec_dont_know)
2356 if (inner_loop
2357 && def_bb->loop_father != inner_loop
2358 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2359 /* ??? We could try to compute the overall effect of the loop here. */
2360 res = chrec_dont_know;
2361 else
2362 res = instantiate_scev_r (instantiate_below, evolution_loop,
2363 inner_loop, res,
2364 fold_conversions, size_expr);
2367 /* Store the correct value to the cache. */
2368 global_cache->set (si, res);
2369 return res;
2372 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2373 and EVOLUTION_LOOP, that were left under a symbolic form.
2375 CHREC is a polynomial chain of recurrence to be instantiated.
2377 CACHE is the cache of already instantiated values.
2379 FOLD_CONVERSIONS should be set to true when the conversions that
2380 may wrap in signed/pointer type are folded, as long as the value of
2381 the chrec is preserved.
2383 SIZE_EXPR is used for computing the size of the expression to be
2384 instantiated, and to stop if it exceeds some limit. */
2386 static tree
2387 instantiate_scev_poly (basic_block instantiate_below,
2388 struct loop *evolution_loop, struct loop *,
2389 tree chrec, bool fold_conversions, int size_expr)
2391 tree op1;
2392 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2393 get_chrec_loop (chrec),
2394 CHREC_LEFT (chrec), fold_conversions,
2395 size_expr);
2396 if (op0 == chrec_dont_know)
2397 return chrec_dont_know;
2399 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2400 get_chrec_loop (chrec),
2401 CHREC_RIGHT (chrec), fold_conversions,
2402 size_expr);
2403 if (op1 == chrec_dont_know)
2404 return chrec_dont_know;
2406 if (CHREC_LEFT (chrec) != op0
2407 || CHREC_RIGHT (chrec) != op1)
2409 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2410 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2413 return chrec;
2416 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2417 and EVOLUTION_LOOP, that were left under a symbolic form.
2419 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2421 CACHE is the cache of already instantiated values.
2423 FOLD_CONVERSIONS should be set to true when the conversions that
2424 may wrap in signed/pointer type are folded, as long as the value of
2425 the chrec is preserved.
2427 SIZE_EXPR is used for computing the size of the expression to be
2428 instantiated, and to stop if it exceeds some limit. */
2430 static tree
2431 instantiate_scev_binary (basic_block instantiate_below,
2432 struct loop *evolution_loop, struct loop *inner_loop,
2433 tree chrec, enum tree_code code,
2434 tree type, tree c0, tree c1,
2435 bool fold_conversions, int size_expr)
2437 tree op1;
2438 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2439 c0, fold_conversions, size_expr);
2440 if (op0 == chrec_dont_know)
2441 return chrec_dont_know;
2443 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2444 c1, fold_conversions, size_expr);
2445 if (op1 == chrec_dont_know)
2446 return chrec_dont_know;
2448 if (c0 != op0
2449 || c1 != op1)
2451 op0 = chrec_convert (type, op0, NULL);
2452 op1 = chrec_convert_rhs (type, op1, NULL);
2454 switch (code)
2456 case POINTER_PLUS_EXPR:
2457 case PLUS_EXPR:
2458 return chrec_fold_plus (type, op0, op1);
2460 case MINUS_EXPR:
2461 return chrec_fold_minus (type, op0, op1);
2463 case MULT_EXPR:
2464 return chrec_fold_multiply (type, op0, op1);
2466 default:
2467 gcc_unreachable ();
2471 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2474 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2475 and EVOLUTION_LOOP, that were left under a symbolic form.
2477 "CHREC" is an array reference to be instantiated.
2479 CACHE is the cache of already instantiated values.
2481 FOLD_CONVERSIONS should be set to true when the conversions that
2482 may wrap in signed/pointer type are folded, as long as the value of
2483 the chrec is preserved.
2485 SIZE_EXPR is used for computing the size of the expression to be
2486 instantiated, and to stop if it exceeds some limit. */
2488 static tree
2489 instantiate_array_ref (basic_block instantiate_below,
2490 struct loop *evolution_loop, struct loop *inner_loop,
2491 tree chrec, bool fold_conversions, int size_expr)
2493 tree res;
2494 tree index = TREE_OPERAND (chrec, 1);
2495 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2496 inner_loop, index,
2497 fold_conversions, size_expr);
2499 if (op1 == chrec_dont_know)
2500 return chrec_dont_know;
2502 if (chrec && op1 == index)
2503 return chrec;
2505 res = unshare_expr (chrec);
2506 TREE_OPERAND (res, 1) = op1;
2507 return res;
2510 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2511 and EVOLUTION_LOOP, that were left under a symbolic form.
2513 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2514 instantiated.
2516 CACHE is the cache of already instantiated values.
2518 FOLD_CONVERSIONS should be set to true when the conversions that
2519 may wrap in signed/pointer type are folded, as long as the value of
2520 the chrec is preserved.
2522 SIZE_EXPR is used for computing the size of the expression to be
2523 instantiated, and to stop if it exceeds some limit. */
2525 static tree
2526 instantiate_scev_convert (basic_block instantiate_below,
2527 struct loop *evolution_loop, struct loop *inner_loop,
2528 tree chrec, tree type, tree op,
2529 bool fold_conversions, int size_expr)
2531 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2532 inner_loop, op,
2533 fold_conversions, size_expr);
2535 if (op0 == chrec_dont_know)
2536 return chrec_dont_know;
2538 if (fold_conversions)
2540 tree tmp = chrec_convert_aggressive (type, op0);
2541 if (tmp)
2542 return tmp;
2545 if (chrec && op0 == op)
2546 return chrec;
2548 /* If we used chrec_convert_aggressive, we can no longer assume that
2549 signed chrecs do not overflow, as chrec_convert does, so avoid
2550 calling it in that case. */
2551 if (fold_conversions)
2552 return fold_convert (type, op0);
2554 return chrec_convert (type, op0, NULL);
2557 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2558 and EVOLUTION_LOOP, that were left under a symbolic form.
2560 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2561 Handle ~X as -1 - X.
2562 Handle -X as -1 * X.
2564 CACHE is the cache of already instantiated values.
2566 FOLD_CONVERSIONS should be set to true when the conversions that
2567 may wrap in signed/pointer type are folded, as long as the value of
2568 the chrec is preserved.
2570 SIZE_EXPR is used for computing the size of the expression to be
2571 instantiated, and to stop if it exceeds some limit. */
2573 static tree
2574 instantiate_scev_not (basic_block instantiate_below,
2575 struct loop *evolution_loop, struct loop *inner_loop,
2576 tree chrec,
2577 enum tree_code code, tree type, tree op,
2578 bool fold_conversions, int size_expr)
2580 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2581 inner_loop, op,
2582 fold_conversions, size_expr);
2584 if (op0 == chrec_dont_know)
2585 return chrec_dont_know;
2587 if (op != op0)
2589 op0 = chrec_convert (type, op0, NULL);
2591 switch (code)
2593 case BIT_NOT_EXPR:
2594 return chrec_fold_minus
2595 (type, fold_convert (type, integer_minus_one_node), op0);
2597 case NEGATE_EXPR:
2598 return chrec_fold_multiply
2599 (type, fold_convert (type, integer_minus_one_node), op0);
2601 default:
2602 gcc_unreachable ();
2606 return chrec ? chrec : fold_build1 (code, type, op0);
2609 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2610 and EVOLUTION_LOOP, that were left under a symbolic form.
2612 CHREC is an expression with 3 operands to be instantiated.
2614 CACHE is the cache of already instantiated values.
2616 FOLD_CONVERSIONS should be set to true when the conversions that
2617 may wrap in signed/pointer type are folded, as long as the value of
2618 the chrec is preserved.
2620 SIZE_EXPR is used for computing the size of the expression to be
2621 instantiated, and to stop if it exceeds some limit. */
2623 static tree
2624 instantiate_scev_3 (basic_block instantiate_below,
2625 struct loop *evolution_loop, struct loop *inner_loop,
2626 tree chrec,
2627 bool fold_conversions, int size_expr)
2629 tree op1, op2;
2630 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2631 inner_loop, TREE_OPERAND (chrec, 0),
2632 fold_conversions, size_expr);
2633 if (op0 == chrec_dont_know)
2634 return chrec_dont_know;
2636 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2637 inner_loop, TREE_OPERAND (chrec, 1),
2638 fold_conversions, size_expr);
2639 if (op1 == chrec_dont_know)
2640 return chrec_dont_know;
2642 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2643 inner_loop, TREE_OPERAND (chrec, 2),
2644 fold_conversions, size_expr);
2645 if (op2 == chrec_dont_know)
2646 return chrec_dont_know;
2648 if (op0 == TREE_OPERAND (chrec, 0)
2649 && op1 == TREE_OPERAND (chrec, 1)
2650 && op2 == TREE_OPERAND (chrec, 2))
2651 return chrec;
2653 return fold_build3 (TREE_CODE (chrec),
2654 TREE_TYPE (chrec), op0, op1, op2);
2657 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2658 and EVOLUTION_LOOP, that were left under a symbolic form.
2660 CHREC is an expression with 2 operands to be instantiated.
2662 CACHE is the cache of already instantiated values.
2664 FOLD_CONVERSIONS should be set to true when the conversions that
2665 may wrap in signed/pointer type are folded, as long as the value of
2666 the chrec is preserved.
2668 SIZE_EXPR is used for computing the size of the expression to be
2669 instantiated, and to stop if it exceeds some limit. */
2671 static tree
2672 instantiate_scev_2 (basic_block instantiate_below,
2673 struct loop *evolution_loop, struct loop *inner_loop,
2674 tree chrec,
2675 bool fold_conversions, int size_expr)
2677 tree op1;
2678 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2679 inner_loop, TREE_OPERAND (chrec, 0),
2680 fold_conversions, size_expr);
2681 if (op0 == chrec_dont_know)
2682 return chrec_dont_know;
2684 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2685 inner_loop, TREE_OPERAND (chrec, 1),
2686 fold_conversions, size_expr);
2687 if (op1 == chrec_dont_know)
2688 return chrec_dont_know;
2690 if (op0 == TREE_OPERAND (chrec, 0)
2691 && op1 == TREE_OPERAND (chrec, 1))
2692 return chrec;
2694 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2697 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2698 and EVOLUTION_LOOP, that were left under a symbolic form.
2700 CHREC is an expression with 2 operands to be instantiated.
2702 CACHE is the cache of already instantiated values.
2704 FOLD_CONVERSIONS should be set to true when the conversions that
2705 may wrap in signed/pointer type are folded, as long as the value of
2706 the chrec is preserved.
2708 SIZE_EXPR is used for computing the size of the expression to be
2709 instantiated, and to stop if it exceeds some limit. */
2711 static tree
2712 instantiate_scev_1 (basic_block instantiate_below,
2713 struct loop *evolution_loop, struct loop *inner_loop,
2714 tree chrec,
2715 bool fold_conversions, int size_expr)
2717 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2718 inner_loop, TREE_OPERAND (chrec, 0),
2719 fold_conversions, size_expr);
2721 if (op0 == chrec_dont_know)
2722 return chrec_dont_know;
2724 if (op0 == TREE_OPERAND (chrec, 0))
2725 return chrec;
2727 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2730 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2731 and EVOLUTION_LOOP, that were left under a symbolic form.
2733 CHREC is the scalar evolution to instantiate.
2735 CACHE is the cache of already instantiated values.
2737 FOLD_CONVERSIONS should be set to true when the conversions that
2738 may wrap in signed/pointer type are folded, as long as the value of
2739 the chrec is preserved.
2741 SIZE_EXPR is used for computing the size of the expression to be
2742 instantiated, and to stop if it exceeds some limit. */
2744 static tree
2745 instantiate_scev_r (basic_block instantiate_below,
2746 struct loop *evolution_loop, struct loop *inner_loop,
2747 tree chrec,
2748 bool fold_conversions, int size_expr)
2750 /* Give up if the expression is larger than the MAX that we allow. */
2751 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2752 return chrec_dont_know;
2754 if (chrec == NULL_TREE
2755 || automatically_generated_chrec_p (chrec)
2756 || is_gimple_min_invariant (chrec))
2757 return chrec;
2759 switch (TREE_CODE (chrec))
2761 case SSA_NAME:
2762 return instantiate_scev_name (instantiate_below, evolution_loop,
2763 inner_loop, chrec,
2764 fold_conversions, size_expr);
2766 case POLYNOMIAL_CHREC:
2767 return instantiate_scev_poly (instantiate_below, evolution_loop,
2768 inner_loop, chrec,
2769 fold_conversions, size_expr);
2771 case POINTER_PLUS_EXPR:
2772 case PLUS_EXPR:
2773 case MINUS_EXPR:
2774 case MULT_EXPR:
2775 return instantiate_scev_binary (instantiate_below, evolution_loop,
2776 inner_loop, chrec,
2777 TREE_CODE (chrec), chrec_type (chrec),
2778 TREE_OPERAND (chrec, 0),
2779 TREE_OPERAND (chrec, 1),
2780 fold_conversions, size_expr);
2782 CASE_CONVERT:
2783 return instantiate_scev_convert (instantiate_below, evolution_loop,
2784 inner_loop, chrec,
2785 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2786 fold_conversions, size_expr);
2788 case NEGATE_EXPR:
2789 case BIT_NOT_EXPR:
2790 return instantiate_scev_not (instantiate_below, evolution_loop,
2791 inner_loop, chrec,
2792 TREE_CODE (chrec), TREE_TYPE (chrec),
2793 TREE_OPERAND (chrec, 0),
2794 fold_conversions, size_expr);
2796 case ADDR_EXPR:
2797 case SCEV_NOT_KNOWN:
2798 return chrec_dont_know;
2800 case SCEV_KNOWN:
2801 return chrec_known;
2803 case ARRAY_REF:
2804 return instantiate_array_ref (instantiate_below, evolution_loop,
2805 inner_loop, chrec,
2806 fold_conversions, size_expr);
2808 default:
2809 break;
2812 if (VL_EXP_CLASS_P (chrec))
2813 return chrec_dont_know;
2815 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2817 case 3:
2818 return instantiate_scev_3 (instantiate_below, evolution_loop,
2819 inner_loop, chrec,
2820 fold_conversions, size_expr);
2822 case 2:
2823 return instantiate_scev_2 (instantiate_below, evolution_loop,
2824 inner_loop, chrec,
2825 fold_conversions, size_expr);
2827 case 1:
2828 return instantiate_scev_1 (instantiate_below, evolution_loop,
2829 inner_loop, chrec,
2830 fold_conversions, size_expr);
2832 case 0:
2833 return chrec;
2835 default:
2836 break;
2839 /* Too complicated to handle. */
2840 return chrec_dont_know;
2843 /* Analyze all the parameters of the chrec that were left under a
2844 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2845 recursive instantiation of parameters: a parameter is a variable
2846 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2847 a function parameter. */
2849 tree
2850 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2851 tree chrec)
2853 tree res;
2855 if (dump_file && (dump_flags & TDF_SCEV))
2857 fprintf (dump_file, "(instantiate_scev \n");
2858 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2859 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2860 fprintf (dump_file, " (chrec = ");
2861 print_generic_expr (dump_file, chrec, 0);
2862 fprintf (dump_file, ")\n");
2865 bool destr = false;
2866 if (!global_cache)
2868 global_cache = new instantiate_cache_type;
2869 destr = true;
2872 res = instantiate_scev_r (instantiate_below, evolution_loop,
2873 NULL, chrec, false, 0);
2875 if (destr)
2877 delete global_cache;
2878 global_cache = NULL;
2881 if (dump_file && (dump_flags & TDF_SCEV))
2883 fprintf (dump_file, " (res = ");
2884 print_generic_expr (dump_file, res, 0);
2885 fprintf (dump_file, "))\n");
2888 return res;
2891 /* Similar to instantiate_parameters, but does not introduce the
2892 evolutions in outer loops for LOOP invariants in CHREC, and does not
2893 care about causing overflows, as long as they do not affect value
2894 of an expression. */
2896 tree
2897 resolve_mixers (struct loop *loop, tree chrec)
2899 bool destr = false;
2900 if (!global_cache)
2902 global_cache = new instantiate_cache_type;
2903 destr = true;
2906 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
2907 chrec, true, 0);
2909 if (destr)
2911 delete global_cache;
2912 global_cache = NULL;
2915 return ret;
2918 /* Entry point for the analysis of the number of iterations pass.
2919 This function tries to safely approximate the number of iterations
2920 the loop will run. When this property is not decidable at compile
2921 time, the result is chrec_dont_know. Otherwise the result is a
2922 scalar or a symbolic parameter. When the number of iterations may
2923 be equal to zero and the property cannot be determined at compile
2924 time, the result is a COND_EXPR that represents in a symbolic form
2925 the conditions under which the number of iterations is not zero.
2927 Example of analysis: suppose that the loop has an exit condition:
2929 "if (b > 49) goto end_loop;"
2931 and that in a previous analysis we have determined that the
2932 variable 'b' has an evolution function:
2934 "EF = {23, +, 5}_2".
2936 When we evaluate the function at the point 5, i.e. the value of the
2937 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2938 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2939 the loop body has been executed 6 times. */
2941 tree
2942 number_of_latch_executions (struct loop *loop)
2944 edge exit;
2945 struct tree_niter_desc niter_desc;
2946 tree may_be_zero;
2947 tree res;
2949 /* Determine whether the number of iterations in loop has already
2950 been computed. */
2951 res = loop->nb_iterations;
2952 if (res)
2953 return res;
2955 may_be_zero = NULL_TREE;
2957 if (dump_file && (dump_flags & TDF_SCEV))
2958 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2960 res = chrec_dont_know;
2961 exit = single_exit (loop);
2963 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2965 may_be_zero = niter_desc.may_be_zero;
2966 res = niter_desc.niter;
2969 if (res == chrec_dont_know
2970 || !may_be_zero
2971 || integer_zerop (may_be_zero))
2973 else if (integer_nonzerop (may_be_zero))
2974 res = build_int_cst (TREE_TYPE (res), 0);
2976 else if (COMPARISON_CLASS_P (may_be_zero))
2977 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2978 build_int_cst (TREE_TYPE (res), 0), res);
2979 else
2980 res = chrec_dont_know;
2982 if (dump_file && (dump_flags & TDF_SCEV))
2984 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2985 print_generic_expr (dump_file, res, 0);
2986 fprintf (dump_file, "))\n");
2989 loop->nb_iterations = res;
2990 return res;
2994 /* Counters for the stats. */
2996 struct chrec_stats
2998 unsigned nb_chrecs;
2999 unsigned nb_affine;
3000 unsigned nb_affine_multivar;
3001 unsigned nb_higher_poly;
3002 unsigned nb_chrec_dont_know;
3003 unsigned nb_undetermined;
3006 /* Reset the counters. */
3008 static inline void
3009 reset_chrecs_counters (struct chrec_stats *stats)
3011 stats->nb_chrecs = 0;
3012 stats->nb_affine = 0;
3013 stats->nb_affine_multivar = 0;
3014 stats->nb_higher_poly = 0;
3015 stats->nb_chrec_dont_know = 0;
3016 stats->nb_undetermined = 0;
3019 /* Dump the contents of a CHREC_STATS structure. */
3021 static void
3022 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3024 fprintf (file, "\n(\n");
3025 fprintf (file, "-----------------------------------------\n");
3026 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3027 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3028 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3029 stats->nb_higher_poly);
3030 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3031 fprintf (file, "-----------------------------------------\n");
3032 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3033 fprintf (file, "%d\twith undetermined coefficients\n",
3034 stats->nb_undetermined);
3035 fprintf (file, "-----------------------------------------\n");
3036 fprintf (file, "%d\tchrecs in the scev database\n",
3037 (int) htab_elements (scalar_evolution_info));
3038 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3039 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3040 fprintf (file, "-----------------------------------------\n");
3041 fprintf (file, ")\n\n");
3044 /* Gather statistics about CHREC. */
3046 static void
3047 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3049 if (dump_file && (dump_flags & TDF_STATS))
3051 fprintf (dump_file, "(classify_chrec ");
3052 print_generic_expr (dump_file, chrec, 0);
3053 fprintf (dump_file, "\n");
3056 stats->nb_chrecs++;
3058 if (chrec == NULL_TREE)
3060 stats->nb_undetermined++;
3061 return;
3064 switch (TREE_CODE (chrec))
3066 case POLYNOMIAL_CHREC:
3067 if (evolution_function_is_affine_p (chrec))
3069 if (dump_file && (dump_flags & TDF_STATS))
3070 fprintf (dump_file, " affine_univariate\n");
3071 stats->nb_affine++;
3073 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3075 if (dump_file && (dump_flags & TDF_STATS))
3076 fprintf (dump_file, " affine_multivariate\n");
3077 stats->nb_affine_multivar++;
3079 else
3081 if (dump_file && (dump_flags & TDF_STATS))
3082 fprintf (dump_file, " higher_degree_polynomial\n");
3083 stats->nb_higher_poly++;
3086 break;
3088 default:
3089 break;
3092 if (chrec_contains_undetermined (chrec))
3094 if (dump_file && (dump_flags & TDF_STATS))
3095 fprintf (dump_file, " undetermined\n");
3096 stats->nb_undetermined++;
3099 if (dump_file && (dump_flags & TDF_STATS))
3100 fprintf (dump_file, ")\n");
3103 /* Callback for htab_traverse, gathers information on chrecs in the
3104 hashtable. */
3106 static int
3107 gather_stats_on_scev_database_1 (void **slot, void *stats)
3109 struct scev_info_str *entry = (struct scev_info_str *) *slot;
3111 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
3113 return 1;
3116 /* Classify the chrecs of the whole database. */
3118 void
3119 gather_stats_on_scev_database (void)
3121 struct chrec_stats stats;
3123 if (!dump_file)
3124 return;
3126 reset_chrecs_counters (&stats);
3128 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
3129 &stats);
3131 dump_chrecs_stats (dump_file, &stats);
3136 /* Initializer. */
3138 static void
3139 initialize_scalar_evolutions_analyzer (void)
3141 /* The elements below are unique. */
3142 if (chrec_dont_know == NULL_TREE)
3144 chrec_not_analyzed_yet = NULL_TREE;
3145 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3146 chrec_known = make_node (SCEV_KNOWN);
3147 TREE_TYPE (chrec_dont_know) = void_type_node;
3148 TREE_TYPE (chrec_known) = void_type_node;
3152 /* Initialize the analysis of scalar evolutions for LOOPS. */
3154 void
3155 scev_initialize (void)
3157 struct loop *loop;
3159 scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
3160 del_scev_info);
3162 initialize_scalar_evolutions_analyzer ();
3164 FOR_EACH_LOOP (loop, 0)
3166 loop->nb_iterations = NULL_TREE;
3170 /* Return true if SCEV is initialized. */
3172 bool
3173 scev_initialized_p (void)
3175 return scalar_evolution_info != NULL;
3178 /* Cleans up the information cached by the scalar evolutions analysis
3179 in the hash table. */
3181 void
3182 scev_reset_htab (void)
3184 if (!scalar_evolution_info)
3185 return;
3187 htab_empty (scalar_evolution_info);
3190 /* Cleans up the information cached by the scalar evolutions analysis
3191 in the hash table and in the loop->nb_iterations. */
3193 void
3194 scev_reset (void)
3196 struct loop *loop;
3198 scev_reset_htab ();
3200 if (!current_loops)
3201 return;
3203 FOR_EACH_LOOP (loop, 0)
3205 loop->nb_iterations = NULL_TREE;
3209 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3210 respect to WRTO_LOOP and returns its base and step in IV if possible
3211 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3212 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3213 invariant in LOOP. Otherwise we require it to be an integer constant.
3215 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3216 because it is computed in signed arithmetics). Consequently, adding an
3217 induction variable
3219 for (i = IV->base; ; i += IV->step)
3221 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3222 false for the type of the induction variable, or you can prove that i does
3223 not wrap by some other argument. Otherwise, this might introduce undefined
3224 behavior, and
3226 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3228 must be used instead. */
3230 bool
3231 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3232 affine_iv *iv, bool allow_nonconstant_step)
3234 tree type, ev;
3235 bool folded_casts;
3237 iv->base = NULL_TREE;
3238 iv->step = NULL_TREE;
3239 iv->no_overflow = false;
3241 type = TREE_TYPE (op);
3242 if (!POINTER_TYPE_P (type)
3243 && !INTEGRAL_TYPE_P (type))
3244 return false;
3246 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3247 &folded_casts);
3248 if (chrec_contains_undetermined (ev)
3249 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3250 return false;
3252 if (tree_does_not_contain_chrecs (ev))
3254 iv->base = ev;
3255 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3256 iv->no_overflow = true;
3257 return true;
3260 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3261 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3262 return false;
3264 iv->step = CHREC_RIGHT (ev);
3265 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3266 || tree_contains_chrecs (iv->step, NULL))
3267 return false;
3269 iv->base = CHREC_LEFT (ev);
3270 if (tree_contains_chrecs (iv->base, NULL))
3271 return false;
3273 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
3275 return true;
3278 /* Finalize the scalar evolution analysis. */
3280 void
3281 scev_finalize (void)
3283 if (!scalar_evolution_info)
3284 return;
3285 htab_delete (scalar_evolution_info);
3286 scalar_evolution_info = NULL;
3289 /* Returns true if the expression EXPR is considered to be too expensive
3290 for scev_const_prop. */
3292 bool
3293 expression_expensive_p (tree expr)
3295 enum tree_code code;
3297 if (is_gimple_val (expr))
3298 return false;
3300 code = TREE_CODE (expr);
3301 if (code == TRUNC_DIV_EXPR
3302 || code == CEIL_DIV_EXPR
3303 || code == FLOOR_DIV_EXPR
3304 || code == ROUND_DIV_EXPR
3305 || code == TRUNC_MOD_EXPR
3306 || code == CEIL_MOD_EXPR
3307 || code == FLOOR_MOD_EXPR
3308 || code == ROUND_MOD_EXPR
3309 || code == EXACT_DIV_EXPR)
3311 /* Division by power of two is usually cheap, so we allow it.
3312 Forbid anything else. */
3313 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3314 return true;
3317 switch (TREE_CODE_CLASS (code))
3319 case tcc_binary:
3320 case tcc_comparison:
3321 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3322 return true;
3324 /* Fallthru. */
3325 case tcc_unary:
3326 return expression_expensive_p (TREE_OPERAND (expr, 0));
3328 default:
3329 return true;
3333 /* Replace ssa names for that scev can prove they are constant by the
3334 appropriate constants. Also perform final value replacement in loops,
3335 in case the replacement expressions are cheap.
3337 We only consider SSA names defined by phi nodes; rest is left to the
3338 ordinary constant propagation pass. */
3340 unsigned int
3341 scev_const_prop (void)
3343 basic_block bb;
3344 tree name, type, ev;
3345 gimple phi, ass;
3346 struct loop *loop, *ex_loop;
3347 bitmap ssa_names_to_remove = NULL;
3348 unsigned i;
3349 gimple_stmt_iterator psi;
3351 if (number_of_loops (cfun) <= 1)
3352 return 0;
3354 FOR_EACH_BB_FN (bb, cfun)
3356 loop = bb->loop_father;
3358 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3360 phi = gsi_stmt (psi);
3361 name = PHI_RESULT (phi);
3363 if (virtual_operand_p (name))
3364 continue;
3366 type = TREE_TYPE (name);
3368 if (!POINTER_TYPE_P (type)
3369 && !INTEGRAL_TYPE_P (type))
3370 continue;
3372 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3373 if (!is_gimple_min_invariant (ev)
3374 || !may_propagate_copy (name, ev))
3375 continue;
3377 /* Replace the uses of the name. */
3378 if (name != ev)
3379 replace_uses_by (name, ev);
3381 if (!ssa_names_to_remove)
3382 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3383 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3387 /* Remove the ssa names that were replaced by constants. We do not
3388 remove them directly in the previous cycle, since this
3389 invalidates scev cache. */
3390 if (ssa_names_to_remove)
3392 bitmap_iterator bi;
3394 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3396 gimple_stmt_iterator psi;
3397 name = ssa_name (i);
3398 phi = SSA_NAME_DEF_STMT (name);
3400 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3401 psi = gsi_for_stmt (phi);
3402 remove_phi_node (&psi, true);
3405 BITMAP_FREE (ssa_names_to_remove);
3406 scev_reset ();
3409 /* Now the regular final value replacement. */
3410 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3412 edge exit;
3413 tree def, rslt, niter;
3414 gimple_stmt_iterator gsi;
3416 /* If we do not know exact number of iterations of the loop, we cannot
3417 replace the final value. */
3418 exit = single_exit (loop);
3419 if (!exit)
3420 continue;
3422 niter = number_of_latch_executions (loop);
3423 if (niter == chrec_dont_know)
3424 continue;
3426 /* Ensure that it is possible to insert new statements somewhere. */
3427 if (!single_pred_p (exit->dest))
3428 split_loop_exit_edge (exit);
3429 gsi = gsi_after_labels (exit->dest);
3431 ex_loop = superloop_at_depth (loop,
3432 loop_depth (exit->dest->loop_father) + 1);
3434 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3436 phi = gsi_stmt (psi);
3437 rslt = PHI_RESULT (phi);
3438 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3439 if (virtual_operand_p (def))
3441 gsi_next (&psi);
3442 continue;
3445 if (!POINTER_TYPE_P (TREE_TYPE (def))
3446 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3448 gsi_next (&psi);
3449 continue;
3452 bool folded_casts;
3453 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3454 &folded_casts);
3455 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3456 if (!tree_does_not_contain_chrecs (def)
3457 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3458 /* Moving the computation from the loop may prolong life range
3459 of some ssa names, which may cause problems if they appear
3460 on abnormal edges. */
3461 || contains_abnormal_ssa_name_p (def)
3462 /* Do not emit expensive expressions. The rationale is that
3463 when someone writes a code like
3465 while (n > 45) n -= 45;
3467 he probably knows that n is not large, and does not want it
3468 to be turned into n %= 45. */
3469 || expression_expensive_p (def))
3471 if (dump_file && (dump_flags & TDF_DETAILS))
3473 fprintf (dump_file, "not replacing:\n ");
3474 print_gimple_stmt (dump_file, phi, 0, 0);
3475 fprintf (dump_file, "\n");
3477 gsi_next (&psi);
3478 continue;
3481 /* Eliminate the PHI node and replace it by a computation outside
3482 the loop. */
3483 if (dump_file)
3485 fprintf (dump_file, "\nfinal value replacement:\n ");
3486 print_gimple_stmt (dump_file, phi, 0, 0);
3487 fprintf (dump_file, " with\n ");
3489 def = unshare_expr (def);
3490 remove_phi_node (&psi, false);
3492 /* If def's type has undefined overflow and there were folded
3493 casts, rewrite all stmts added for def into arithmetics
3494 with defined overflow behavior. */
3495 if (folded_casts && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3497 gimple_seq stmts;
3498 gimple_stmt_iterator gsi2;
3499 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3500 gsi2 = gsi_start (stmts);
3501 while (!gsi_end_p (gsi2))
3503 gimple stmt = gsi_stmt (gsi2);
3504 gimple_stmt_iterator gsi3 = gsi2;
3505 gsi_next (&gsi2);
3506 gsi_remove (&gsi3, false);
3507 if (is_gimple_assign (stmt)
3508 && arith_code_with_undefined_signed_overflow
3509 (gimple_assign_rhs_code (stmt)))
3510 gsi_insert_seq_before (&gsi,
3511 rewrite_to_defined_overflow (stmt),
3512 GSI_SAME_STMT);
3513 else
3514 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3517 else
3518 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3519 true, GSI_SAME_STMT);
3521 ass = gimple_build_assign (rslt, def);
3522 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3523 if (dump_file)
3525 print_gimple_stmt (dump_file, ass, 0, 0);
3526 fprintf (dump_file, "\n");
3530 return 0;
3533 #include "gt-tree-scalar-evolution.h"