libgomp: Use pthread mutexes in the nvptx plugin.
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobd4b246e7d420e85f65d463dee8ecc8826679df43
1 /* Scalar evolution detector.
2 Copyright (C) 2003-2015 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 "hash-set.h"
260 #include "machmode.h"
261 #include "vec.h"
262 #include "double-int.h"
263 #include "input.h"
264 #include "alias.h"
265 #include "symtab.h"
266 #include "options.h"
267 #include "wide-int.h"
268 #include "inchash.h"
269 #include "tree.h"
270 #include "fold-const.h"
271 #include "expr.h"
272 #include "gimple-pretty-print.h"
273 #include "predict.h"
274 #include "tm.h"
275 #include "hard-reg-set.h"
276 #include "input.h"
277 #include "function.h"
278 #include "dominance.h"
279 #include "cfg.h"
280 #include "basic-block.h"
281 #include "tree-ssa-alias.h"
282 #include "internal-fn.h"
283 #include "gimple-expr.h"
284 #include "is-a.h"
285 #include "gimple.h"
286 #include "gimplify.h"
287 #include "gimple-iterator.h"
288 #include "gimplify-me.h"
289 #include "gimple-ssa.h"
290 #include "tree-cfg.h"
291 #include "tree-phinodes.h"
292 #include "stringpool.h"
293 #include "tree-ssanames.h"
294 #include "tree-ssa-loop-ivopts.h"
295 #include "tree-ssa-loop-manip.h"
296 #include "tree-ssa-loop-niter.h"
297 #include "tree-ssa-loop.h"
298 #include "tree-ssa.h"
299 #include "cfgloop.h"
300 #include "tree-chrec.h"
301 #include "tree-affine.h"
302 #include "tree-scalar-evolution.h"
303 #include "dumpfile.h"
304 #include "params.h"
305 #include "tree-ssa-propagate.h"
306 #include "gimple-fold.h"
307 #include "gimplify-me.h"
309 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
310 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
311 tree var);
313 /* The cached information about an SSA name with version NAME_VERSION,
314 claiming that below basic block with index INSTANTIATED_BELOW, the
315 value of the SSA name can be expressed as CHREC. */
317 struct GTY((for_user)) scev_info_str {
318 unsigned int name_version;
319 int instantiated_below;
320 tree chrec;
323 /* Counters for the scev database. */
324 static unsigned nb_set_scev = 0;
325 static unsigned nb_get_scev = 0;
327 /* The following trees are unique elements. Thus the comparison of
328 another element to these elements should be done on the pointer to
329 these trees, and not on their value. */
331 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
332 tree chrec_not_analyzed_yet;
334 /* Reserved to the cases where the analyzer has detected an
335 undecidable property at compile time. */
336 tree chrec_dont_know;
338 /* When the analyzer has detected that a property will never
339 happen, then it qualifies it with chrec_known. */
340 tree chrec_known;
342 struct scev_info_hasher : ggc_hasher<scev_info_str *>
344 static hashval_t hash (scev_info_str *i);
345 static bool equal (const scev_info_str *a, const scev_info_str *b);
348 static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
351 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
353 static inline struct scev_info_str *
354 new_scev_info_str (basic_block instantiated_below, tree var)
356 struct scev_info_str *res;
358 res = ggc_alloc<scev_info_str> ();
359 res->name_version = SSA_NAME_VERSION (var);
360 res->chrec = chrec_not_analyzed_yet;
361 res->instantiated_below = instantiated_below->index;
363 return res;
366 /* Computes a hash function for database element ELT. */
368 hashval_t
369 scev_info_hasher::hash (scev_info_str *elt)
371 return elt->name_version ^ elt->instantiated_below;
374 /* Compares database elements E1 and E2. */
376 bool
377 scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
379 return (elt1->name_version == elt2->name_version
380 && elt1->instantiated_below == elt2->instantiated_below);
383 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
384 A first query on VAR returns chrec_not_analyzed_yet. */
386 static tree *
387 find_var_scev_info (basic_block instantiated_below, tree var)
389 struct scev_info_str *res;
390 struct scev_info_str tmp;
392 tmp.name_version = SSA_NAME_VERSION (var);
393 tmp.instantiated_below = instantiated_below->index;
394 scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
396 if (!*slot)
397 *slot = new_scev_info_str (instantiated_below, var);
398 res = *slot;
400 return &res->chrec;
403 /* Return true when CHREC contains symbolic names defined in
404 LOOP_NB. */
406 bool
407 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
409 int i, n;
411 if (chrec == NULL_TREE)
412 return false;
414 if (is_gimple_min_invariant (chrec))
415 return false;
417 if (TREE_CODE (chrec) == SSA_NAME)
419 gimple def;
420 loop_p def_loop, loop;
422 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
423 return false;
425 def = SSA_NAME_DEF_STMT (chrec);
426 def_loop = loop_containing_stmt (def);
427 loop = get_loop (cfun, loop_nb);
429 if (def_loop == NULL)
430 return false;
432 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
433 return true;
435 return false;
438 n = TREE_OPERAND_LENGTH (chrec);
439 for (i = 0; i < n; i++)
440 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
441 loop_nb))
442 return true;
443 return false;
446 /* Return true when PHI is a loop-phi-node. */
448 static bool
449 loop_phi_node_p (gimple phi)
451 /* The implementation of this function is based on the following
452 property: "all the loop-phi-nodes of a loop are contained in the
453 loop's header basic block". */
455 return loop_containing_stmt (phi)->header == gimple_bb (phi);
458 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
459 In general, in the case of multivariate evolutions we want to get
460 the evolution in different loops. LOOP specifies the level for
461 which to get the evolution.
463 Example:
465 | for (j = 0; j < 100; j++)
467 | for (k = 0; k < 100; k++)
469 | i = k + j; - Here the value of i is a function of j, k.
471 | ... = i - Here the value of i is a function of j.
473 | ... = i - Here the value of i is a scalar.
475 Example:
477 | i_0 = ...
478 | loop_1 10 times
479 | i_1 = phi (i_0, i_2)
480 | i_2 = i_1 + 2
481 | endloop
483 This loop has the same effect as:
484 LOOP_1 has the same effect as:
486 | i_1 = i_0 + 20
488 The overall effect of the loop, "i_0 + 20" in the previous example,
489 is obtained by passing in the parameters: LOOP = 1,
490 EVOLUTION_FN = {i_0, +, 2}_1.
493 tree
494 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
496 bool val = false;
498 if (evolution_fn == chrec_dont_know)
499 return chrec_dont_know;
501 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
503 struct loop *inner_loop = get_chrec_loop (evolution_fn);
505 if (inner_loop == loop
506 || flow_loop_nested_p (loop, inner_loop))
508 tree nb_iter = number_of_latch_executions (inner_loop);
510 if (nb_iter == chrec_dont_know)
511 return chrec_dont_know;
512 else
514 tree res;
516 /* evolution_fn is the evolution function in LOOP. Get
517 its value in the nb_iter-th iteration. */
518 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
520 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
521 res = instantiate_parameters (loop, res);
523 /* Continue the computation until ending on a parent of LOOP. */
524 return compute_overall_effect_of_inner_loop (loop, res);
527 else
528 return evolution_fn;
531 /* If the evolution function is an invariant, there is nothing to do. */
532 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
533 return evolution_fn;
535 else
536 return chrec_dont_know;
539 /* Associate CHREC to SCALAR. */
541 static void
542 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
544 tree *scalar_info;
546 if (TREE_CODE (scalar) != SSA_NAME)
547 return;
549 scalar_info = find_var_scev_info (instantiated_below, scalar);
551 if (dump_file)
553 if (dump_flags & TDF_SCEV)
555 fprintf (dump_file, "(set_scalar_evolution \n");
556 fprintf (dump_file, " instantiated_below = %d \n",
557 instantiated_below->index);
558 fprintf (dump_file, " (scalar = ");
559 print_generic_expr (dump_file, scalar, 0);
560 fprintf (dump_file, ")\n (scalar_evolution = ");
561 print_generic_expr (dump_file, chrec, 0);
562 fprintf (dump_file, "))\n");
564 if (dump_flags & TDF_STATS)
565 nb_set_scev++;
568 *scalar_info = chrec;
571 /* Retrieve the chrec associated to SCALAR instantiated below
572 INSTANTIATED_BELOW block. */
574 static tree
575 get_scalar_evolution (basic_block instantiated_below, tree scalar)
577 tree res;
579 if (dump_file)
581 if (dump_flags & TDF_SCEV)
583 fprintf (dump_file, "(get_scalar_evolution \n");
584 fprintf (dump_file, " (scalar = ");
585 print_generic_expr (dump_file, scalar, 0);
586 fprintf (dump_file, ")\n");
588 if (dump_flags & TDF_STATS)
589 nb_get_scev++;
592 switch (TREE_CODE (scalar))
594 case SSA_NAME:
595 res = *find_var_scev_info (instantiated_below, scalar);
596 break;
598 case REAL_CST:
599 case FIXED_CST:
600 case INTEGER_CST:
601 res = scalar;
602 break;
604 default:
605 res = chrec_not_analyzed_yet;
606 break;
609 if (dump_file && (dump_flags & TDF_SCEV))
611 fprintf (dump_file, " (scalar_evolution = ");
612 print_generic_expr (dump_file, res, 0);
613 fprintf (dump_file, "))\n");
616 return res;
619 /* Helper function for add_to_evolution. Returns the evolution
620 function for an assignment of the form "a = b + c", where "a" and
621 "b" are on the strongly connected component. CHREC_BEFORE is the
622 information that we already have collected up to this point.
623 TO_ADD is the evolution of "c".
625 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
626 evolution the expression TO_ADD, otherwise construct an evolution
627 part for this loop. */
629 static tree
630 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
631 gimple at_stmt)
633 tree type, left, right;
634 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
636 switch (TREE_CODE (chrec_before))
638 case POLYNOMIAL_CHREC:
639 chloop = get_chrec_loop (chrec_before);
640 if (chloop == loop
641 || flow_loop_nested_p (chloop, loop))
643 unsigned var;
645 type = chrec_type (chrec_before);
647 /* When there is no evolution part in this loop, build it. */
648 if (chloop != loop)
650 var = loop_nb;
651 left = chrec_before;
652 right = SCALAR_FLOAT_TYPE_P (type)
653 ? build_real (type, dconst0)
654 : build_int_cst (type, 0);
656 else
658 var = CHREC_VARIABLE (chrec_before);
659 left = CHREC_LEFT (chrec_before);
660 right = CHREC_RIGHT (chrec_before);
663 to_add = chrec_convert (type, to_add, at_stmt);
664 right = chrec_convert_rhs (type, right, at_stmt);
665 right = chrec_fold_plus (chrec_type (right), right, to_add);
666 return build_polynomial_chrec (var, left, right);
668 else
670 gcc_assert (flow_loop_nested_p (loop, chloop));
672 /* Search the evolution in LOOP_NB. */
673 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
674 to_add, at_stmt);
675 right = CHREC_RIGHT (chrec_before);
676 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
677 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
678 left, right);
681 default:
682 /* These nodes do not depend on a loop. */
683 if (chrec_before == chrec_dont_know)
684 return chrec_dont_know;
686 left = chrec_before;
687 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
688 return build_polynomial_chrec (loop_nb, left, right);
692 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
693 of LOOP_NB.
695 Description (provided for completeness, for those who read code in
696 a plane, and for my poor 62 bytes brain that would have forgotten
697 all this in the next two or three months):
699 The algorithm of translation of programs from the SSA representation
700 into the chrecs syntax is based on a pattern matching. After having
701 reconstructed the overall tree expression for a loop, there are only
702 two cases that can arise:
704 1. a = loop-phi (init, a + expr)
705 2. a = loop-phi (init, expr)
707 where EXPR is either a scalar constant with respect to the analyzed
708 loop (this is a degree 0 polynomial), or an expression containing
709 other loop-phi definitions (these are higher degree polynomials).
711 Examples:
714 | init = ...
715 | loop_1
716 | a = phi (init, a + 5)
717 | endloop
720 | inita = ...
721 | initb = ...
722 | loop_1
723 | a = phi (inita, 2 * b + 3)
724 | b = phi (initb, b + 1)
725 | endloop
727 For the first case, the semantics of the SSA representation is:
729 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
731 that is, there is a loop index "x" that determines the scalar value
732 of the variable during the loop execution. During the first
733 iteration, the value is that of the initial condition INIT, while
734 during the subsequent iterations, it is the sum of the initial
735 condition with the sum of all the values of EXPR from the initial
736 iteration to the before last considered iteration.
738 For the second case, the semantics of the SSA program is:
740 | a (x) = init, if x = 0;
741 | expr (x - 1), otherwise.
743 The second case corresponds to the PEELED_CHREC, whose syntax is
744 close to the syntax of a loop-phi-node:
746 | phi (init, expr) vs. (init, expr)_x
748 The proof of the translation algorithm for the first case is a
749 proof by structural induction based on the degree of EXPR.
751 Degree 0:
752 When EXPR is a constant with respect to the analyzed loop, or in
753 other words when EXPR is a polynomial of degree 0, the evolution of
754 the variable A in the loop is an affine function with an initial
755 condition INIT, and a step EXPR. In order to show this, we start
756 from the semantics of the SSA representation:
758 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
760 and since "expr (j)" is a constant with respect to "j",
762 f (x) = init + x * expr
764 Finally, based on the semantics of the pure sum chrecs, by
765 identification we get the corresponding chrecs syntax:
767 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
768 f (x) -> {init, +, expr}_x
770 Higher degree:
771 Suppose that EXPR is a polynomial of degree N with respect to the
772 analyzed loop_x for which we have already determined that it is
773 written under the chrecs syntax:
775 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
777 We start from the semantics of the SSA program:
779 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
781 | f (x) = init + \sum_{j = 0}^{x - 1}
782 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
784 | f (x) = init + \sum_{j = 0}^{x - 1}
785 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
787 | f (x) = init + \sum_{k = 0}^{n - 1}
788 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
790 | f (x) = init + \sum_{k = 0}^{n - 1}
791 | (b_k * \binom{x}{k + 1})
793 | f (x) = init + b_0 * \binom{x}{1} + ...
794 | + b_{n-1} * \binom{x}{n}
796 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
797 | + b_{n-1} * \binom{x}{n}
800 And finally from the definition of the chrecs syntax, we identify:
801 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
803 This shows the mechanism that stands behind the add_to_evolution
804 function. An important point is that the use of symbolic
805 parameters avoids the need of an analysis schedule.
807 Example:
809 | inita = ...
810 | initb = ...
811 | loop_1
812 | a = phi (inita, a + 2 + b)
813 | b = phi (initb, b + 1)
814 | endloop
816 When analyzing "a", the algorithm keeps "b" symbolically:
818 | a -> {inita, +, 2 + b}_1
820 Then, after instantiation, the analyzer ends on the evolution:
822 | a -> {inita, +, 2 + initb, +, 1}_1
826 static tree
827 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
828 tree to_add, gimple at_stmt)
830 tree type = chrec_type (to_add);
831 tree res = NULL_TREE;
833 if (to_add == NULL_TREE)
834 return chrec_before;
836 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
837 instantiated at this point. */
838 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
839 /* This should not happen. */
840 return chrec_dont_know;
842 if (dump_file && (dump_flags & TDF_SCEV))
844 fprintf (dump_file, "(add_to_evolution \n");
845 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
846 fprintf (dump_file, " (chrec_before = ");
847 print_generic_expr (dump_file, chrec_before, 0);
848 fprintf (dump_file, ")\n (to_add = ");
849 print_generic_expr (dump_file, to_add, 0);
850 fprintf (dump_file, ")\n");
853 if (code == MINUS_EXPR)
854 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
855 ? build_real (type, dconstm1)
856 : build_int_cst_type (type, -1));
858 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
860 if (dump_file && (dump_flags & TDF_SCEV))
862 fprintf (dump_file, " (res = ");
863 print_generic_expr (dump_file, res, 0);
864 fprintf (dump_file, "))\n");
867 return res;
872 /* This section selects the loops that will be good candidates for the
873 scalar evolution analysis. For the moment, greedily select all the
874 loop nests we could analyze. */
876 /* For a loop with a single exit edge, return the COND_EXPR that
877 guards the exit edge. If the expression is too difficult to
878 analyze, then give up. */
880 gcond *
881 get_loop_exit_condition (const struct loop *loop)
883 gcond *res = NULL;
884 edge exit_edge = single_exit (loop);
886 if (dump_file && (dump_flags & TDF_SCEV))
887 fprintf (dump_file, "(get_loop_exit_condition \n ");
889 if (exit_edge)
891 gimple stmt;
893 stmt = last_stmt (exit_edge->src);
894 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
895 res = cond_stmt;
898 if (dump_file && (dump_flags & TDF_SCEV))
900 print_gimple_stmt (dump_file, res, 0, 0);
901 fprintf (dump_file, ")\n");
904 return res;
908 /* Depth first search algorithm. */
910 typedef enum t_bool {
911 t_false,
912 t_true,
913 t_dont_know
914 } t_bool;
917 static t_bool follow_ssa_edge (struct loop *loop, gimple, gphi *,
918 tree *, int);
920 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
921 Return true if the strongly connected component has been found. */
923 static t_bool
924 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
925 tree type, tree rhs0, enum tree_code code, tree rhs1,
926 gphi *halting_phi, tree *evolution_of_loop,
927 int limit)
929 t_bool res = t_false;
930 tree evol;
932 switch (code)
934 case POINTER_PLUS_EXPR:
935 case PLUS_EXPR:
936 if (TREE_CODE (rhs0) == SSA_NAME)
938 if (TREE_CODE (rhs1) == SSA_NAME)
940 /* Match an assignment under the form:
941 "a = b + c". */
943 /* We want only assignments of form "name + name" contribute to
944 LIMIT, as the other cases do not necessarily contribute to
945 the complexity of the expression. */
946 limit++;
948 evol = *evolution_of_loop;
949 res = follow_ssa_edge
950 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
952 if (res == t_true)
953 *evolution_of_loop = add_to_evolution
954 (loop->num,
955 chrec_convert (type, evol, at_stmt),
956 code, rhs1, at_stmt);
958 else if (res == t_false)
960 res = follow_ssa_edge
961 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
962 evolution_of_loop, limit);
964 if (res == t_true)
965 *evolution_of_loop = add_to_evolution
966 (loop->num,
967 chrec_convert (type, *evolution_of_loop, at_stmt),
968 code, rhs0, at_stmt);
970 else if (res == t_dont_know)
971 *evolution_of_loop = chrec_dont_know;
974 else if (res == t_dont_know)
975 *evolution_of_loop = chrec_dont_know;
978 else
980 /* Match an assignment under the form:
981 "a = b + ...". */
982 res = follow_ssa_edge
983 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
984 evolution_of_loop, limit);
985 if (res == t_true)
986 *evolution_of_loop = add_to_evolution
987 (loop->num, chrec_convert (type, *evolution_of_loop,
988 at_stmt),
989 code, rhs1, at_stmt);
991 else if (res == t_dont_know)
992 *evolution_of_loop = chrec_dont_know;
996 else if (TREE_CODE (rhs1) == SSA_NAME)
998 /* Match an assignment under the form:
999 "a = ... + c". */
1000 res = follow_ssa_edge
1001 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1002 evolution_of_loop, limit);
1003 if (res == t_true)
1004 *evolution_of_loop = add_to_evolution
1005 (loop->num, chrec_convert (type, *evolution_of_loop,
1006 at_stmt),
1007 code, rhs0, at_stmt);
1009 else if (res == t_dont_know)
1010 *evolution_of_loop = chrec_dont_know;
1013 else
1014 /* Otherwise, match an assignment under the form:
1015 "a = ... + ...". */
1016 /* And there is nothing to do. */
1017 res = t_false;
1018 break;
1020 case MINUS_EXPR:
1021 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1022 if (TREE_CODE (rhs0) == SSA_NAME)
1024 /* Match an assignment under the form:
1025 "a = b - ...". */
1027 /* We want only assignments of form "name - name" contribute to
1028 LIMIT, as the other cases do not necessarily contribute to
1029 the complexity of the expression. */
1030 if (TREE_CODE (rhs1) == SSA_NAME)
1031 limit++;
1033 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1034 evolution_of_loop, limit);
1035 if (res == t_true)
1036 *evolution_of_loop = add_to_evolution
1037 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1038 MINUS_EXPR, rhs1, at_stmt);
1040 else if (res == t_dont_know)
1041 *evolution_of_loop = chrec_dont_know;
1043 else
1044 /* Otherwise, match an assignment under the form:
1045 "a = ... - ...". */
1046 /* And there is nothing to do. */
1047 res = t_false;
1048 break;
1050 default:
1051 res = t_false;
1054 return res;
1057 /* Follow the ssa edge into the expression EXPR.
1058 Return true if the strongly connected component has been found. */
1060 static t_bool
1061 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1062 gphi *halting_phi, tree *evolution_of_loop,
1063 int limit)
1065 enum tree_code code = TREE_CODE (expr);
1066 tree type = TREE_TYPE (expr), rhs0, rhs1;
1067 t_bool res;
1069 /* The EXPR is one of the following cases:
1070 - an SSA_NAME,
1071 - an INTEGER_CST,
1072 - a PLUS_EXPR,
1073 - a POINTER_PLUS_EXPR,
1074 - a MINUS_EXPR,
1075 - an ASSERT_EXPR,
1076 - other cases are not yet handled. */
1078 switch (code)
1080 CASE_CONVERT:
1081 /* This assignment is under the form "a_1 = (cast) rhs. */
1082 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1083 halting_phi, evolution_of_loop, limit);
1084 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1085 break;
1087 case INTEGER_CST:
1088 /* This assignment is under the form "a_1 = 7". */
1089 res = t_false;
1090 break;
1092 case SSA_NAME:
1093 /* This assignment is under the form: "a_1 = b_2". */
1094 res = follow_ssa_edge
1095 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1096 break;
1098 case POINTER_PLUS_EXPR:
1099 case PLUS_EXPR:
1100 case MINUS_EXPR:
1101 /* This case is under the form "rhs0 +- rhs1". */
1102 rhs0 = TREE_OPERAND (expr, 0);
1103 rhs1 = TREE_OPERAND (expr, 1);
1104 type = TREE_TYPE (rhs0);
1105 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1106 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1107 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1108 halting_phi, evolution_of_loop, limit);
1109 break;
1111 case ADDR_EXPR:
1112 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1113 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1115 expr = TREE_OPERAND (expr, 0);
1116 rhs0 = TREE_OPERAND (expr, 0);
1117 rhs1 = TREE_OPERAND (expr, 1);
1118 type = TREE_TYPE (rhs0);
1119 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1120 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1121 res = follow_ssa_edge_binary (loop, at_stmt, type,
1122 rhs0, POINTER_PLUS_EXPR, rhs1,
1123 halting_phi, evolution_of_loop, limit);
1125 else
1126 res = t_false;
1127 break;
1129 case ASSERT_EXPR:
1130 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1131 It must be handled as a copy assignment of the form a_1 = a_2. */
1132 rhs0 = ASSERT_EXPR_VAR (expr);
1133 if (TREE_CODE (rhs0) == SSA_NAME)
1134 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1135 halting_phi, evolution_of_loop, limit);
1136 else
1137 res = t_false;
1138 break;
1140 default:
1141 res = t_false;
1142 break;
1145 return res;
1148 /* Follow the ssa edge into the right hand side of an assignment STMT.
1149 Return true if the strongly connected component has been found. */
1151 static t_bool
1152 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1153 gphi *halting_phi, tree *evolution_of_loop,
1154 int limit)
1156 enum tree_code code = gimple_assign_rhs_code (stmt);
1157 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1158 t_bool res;
1160 switch (code)
1162 CASE_CONVERT:
1163 /* This assignment is under the form "a_1 = (cast) rhs. */
1164 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1165 halting_phi, evolution_of_loop, limit);
1166 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1167 break;
1169 case POINTER_PLUS_EXPR:
1170 case PLUS_EXPR:
1171 case MINUS_EXPR:
1172 rhs1 = gimple_assign_rhs1 (stmt);
1173 rhs2 = gimple_assign_rhs2 (stmt);
1174 type = TREE_TYPE (rhs1);
1175 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1176 halting_phi, evolution_of_loop, limit);
1177 break;
1179 default:
1180 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1181 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1182 halting_phi, evolution_of_loop, limit);
1183 else
1184 res = t_false;
1185 break;
1188 return res;
1191 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1193 static bool
1194 backedge_phi_arg_p (gphi *phi, int i)
1196 const_edge e = gimple_phi_arg_edge (phi, i);
1198 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1199 about updating it anywhere, and this should work as well most of the
1200 time. */
1201 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1202 return true;
1204 return false;
1207 /* Helper function for one branch of the condition-phi-node. Return
1208 true if the strongly connected component has been found following
1209 this path. */
1211 static inline t_bool
1212 follow_ssa_edge_in_condition_phi_branch (int i,
1213 struct loop *loop,
1214 gphi *condition_phi,
1215 gphi *halting_phi,
1216 tree *evolution_of_branch,
1217 tree init_cond, int limit)
1219 tree branch = PHI_ARG_DEF (condition_phi, i);
1220 *evolution_of_branch = chrec_dont_know;
1222 /* Do not follow back edges (they must belong to an irreducible loop, which
1223 we really do not want to worry about). */
1224 if (backedge_phi_arg_p (condition_phi, i))
1225 return t_false;
1227 if (TREE_CODE (branch) == SSA_NAME)
1229 *evolution_of_branch = init_cond;
1230 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1231 evolution_of_branch, limit);
1234 /* This case occurs when one of the condition branches sets
1235 the variable to a constant: i.e. a phi-node like
1236 "a_2 = PHI <a_7(5), 2(6)>;".
1238 FIXME: This case have to be refined correctly:
1239 in some cases it is possible to say something better than
1240 chrec_dont_know, for example using a wrap-around notation. */
1241 return t_false;
1244 /* This function merges the branches of a condition-phi-node in a
1245 loop. */
1247 static t_bool
1248 follow_ssa_edge_in_condition_phi (struct loop *loop,
1249 gphi *condition_phi,
1250 gphi *halting_phi,
1251 tree *evolution_of_loop, int limit)
1253 int i, n;
1254 tree init = *evolution_of_loop;
1255 tree evolution_of_branch;
1256 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1257 halting_phi,
1258 &evolution_of_branch,
1259 init, limit);
1260 if (res == t_false || res == t_dont_know)
1261 return res;
1263 *evolution_of_loop = evolution_of_branch;
1265 n = gimple_phi_num_args (condition_phi);
1266 for (i = 1; i < n; i++)
1268 /* Quickly give up when the evolution of one of the branches is
1269 not known. */
1270 if (*evolution_of_loop == chrec_dont_know)
1271 return t_true;
1273 /* Increase the limit by the PHI argument number to avoid exponential
1274 time and memory complexity. */
1275 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1276 halting_phi,
1277 &evolution_of_branch,
1278 init, limit + i);
1279 if (res == t_false || res == t_dont_know)
1280 return res;
1282 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1283 evolution_of_branch);
1286 return t_true;
1289 /* Follow an SSA edge in an inner loop. It computes the overall
1290 effect of the loop, and following the symbolic initial conditions,
1291 it follows the edges in the parent loop. The inner loop is
1292 considered as a single statement. */
1294 static t_bool
1295 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1296 gphi *loop_phi_node,
1297 gphi *halting_phi,
1298 tree *evolution_of_loop, int limit)
1300 struct loop *loop = loop_containing_stmt (loop_phi_node);
1301 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1303 /* Sometimes, the inner loop is too difficult to analyze, and the
1304 result of the analysis is a symbolic parameter. */
1305 if (ev == PHI_RESULT (loop_phi_node))
1307 t_bool res = t_false;
1308 int i, n = gimple_phi_num_args (loop_phi_node);
1310 for (i = 0; i < n; i++)
1312 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1313 basic_block bb;
1315 /* Follow the edges that exit the inner loop. */
1316 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1317 if (!flow_bb_inside_loop_p (loop, bb))
1318 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1319 arg, halting_phi,
1320 evolution_of_loop, limit);
1321 if (res == t_true)
1322 break;
1325 /* If the path crosses this loop-phi, give up. */
1326 if (res == t_true)
1327 *evolution_of_loop = chrec_dont_know;
1329 return res;
1332 /* Otherwise, compute the overall effect of the inner loop. */
1333 ev = compute_overall_effect_of_inner_loop (loop, ev);
1334 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1335 evolution_of_loop, limit);
1338 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1339 path that is analyzed on the return walk. */
1341 static t_bool
1342 follow_ssa_edge (struct loop *loop, gimple def, gphi *halting_phi,
1343 tree *evolution_of_loop, int limit)
1345 struct loop *def_loop;
1347 if (gimple_nop_p (def))
1348 return t_false;
1350 /* Give up if the path is longer than the MAX that we allow. */
1351 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1352 return t_dont_know;
1354 def_loop = loop_containing_stmt (def);
1356 switch (gimple_code (def))
1358 case GIMPLE_PHI:
1359 if (!loop_phi_node_p (def))
1360 /* DEF is a condition-phi-node. Follow the branches, and
1361 record their evolutions. Finally, merge the collected
1362 information and set the approximation to the main
1363 variable. */
1364 return follow_ssa_edge_in_condition_phi
1365 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1366 limit);
1368 /* When the analyzed phi is the halting_phi, the
1369 depth-first search is over: we have found a path from
1370 the halting_phi to itself in the loop. */
1371 if (def == halting_phi)
1372 return t_true;
1374 /* Otherwise, the evolution of the HALTING_PHI depends
1375 on the evolution of another loop-phi-node, i.e. the
1376 evolution function is a higher degree polynomial. */
1377 if (def_loop == loop)
1378 return t_false;
1380 /* Inner loop. */
1381 if (flow_loop_nested_p (loop, def_loop))
1382 return follow_ssa_edge_inner_loop_phi
1383 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1384 limit + 1);
1386 /* Outer loop. */
1387 return t_false;
1389 case GIMPLE_ASSIGN:
1390 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1391 evolution_of_loop, limit);
1393 default:
1394 /* At this level of abstraction, the program is just a set
1395 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1396 other node to be handled. */
1397 return t_false;
1402 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1403 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1405 # i_17 = PHI <i_13(5), 0(3)>
1406 # _20 = PHI <_5(5), start_4(D)(3)>
1408 i_13 = i_17 + 1;
1409 _5 = start_4(D) + i_13;
1411 Though variable _20 appears as a PEELED_CHREC in the form of
1412 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1414 See PR41488. */
1416 static tree
1417 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1419 aff_tree aff1, aff2;
1420 tree ev, left, right, type, step_val;
1421 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1423 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1424 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1425 return chrec_dont_know;
1427 left = CHREC_LEFT (ev);
1428 right = CHREC_RIGHT (ev);
1429 type = TREE_TYPE (left);
1430 step_val = chrec_fold_plus (type, init_cond, right);
1432 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1433 if "left" equals to "init + right". */
1434 if (operand_equal_p (left, step_val, 0))
1436 if (dump_file && (dump_flags & TDF_SCEV))
1437 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1439 return build_polynomial_chrec (loop->num, init_cond, right);
1442 /* Try harder to check if they are equal. */
1443 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1444 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1445 free_affine_expand_cache (&peeled_chrec_map);
1446 aff_combination_scale (&aff2, -1);
1447 aff_combination_add (&aff1, &aff2);
1449 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1450 if "left" equals to "init + right". */
1451 if (aff_combination_zero_p (&aff1))
1453 if (dump_file && (dump_flags & TDF_SCEV))
1454 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1456 return build_polynomial_chrec (loop->num, init_cond, right);
1458 return chrec_dont_know;
1461 /* Given a LOOP_PHI_NODE, this function determines the evolution
1462 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1464 static tree
1465 analyze_evolution_in_loop (gphi *loop_phi_node,
1466 tree init_cond)
1468 int i, n = gimple_phi_num_args (loop_phi_node);
1469 tree evolution_function = chrec_not_analyzed_yet;
1470 struct loop *loop = loop_containing_stmt (loop_phi_node);
1471 basic_block bb;
1472 static bool simplify_peeled_chrec_p = true;
1474 if (dump_file && (dump_flags & TDF_SCEV))
1476 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1477 fprintf (dump_file, " (loop_phi_node = ");
1478 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1479 fprintf (dump_file, ")\n");
1482 for (i = 0; i < n; i++)
1484 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1485 gimple ssa_chain;
1486 tree ev_fn;
1487 t_bool res;
1489 /* Select the edges that enter the loop body. */
1490 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1491 if (!flow_bb_inside_loop_p (loop, bb))
1492 continue;
1494 if (TREE_CODE (arg) == SSA_NAME)
1496 bool val = false;
1498 ssa_chain = SSA_NAME_DEF_STMT (arg);
1500 /* Pass in the initial condition to the follow edge function. */
1501 ev_fn = init_cond;
1502 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1504 /* If ev_fn has no evolution in the inner loop, and the
1505 init_cond is not equal to ev_fn, then we have an
1506 ambiguity between two possible values, as we cannot know
1507 the number of iterations at this point. */
1508 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1509 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1510 && !operand_equal_p (init_cond, ev_fn, 0))
1511 ev_fn = chrec_dont_know;
1513 else
1514 res = t_false;
1516 /* When it is impossible to go back on the same
1517 loop_phi_node by following the ssa edges, the
1518 evolution is represented by a peeled chrec, i.e. the
1519 first iteration, EV_FN has the value INIT_COND, then
1520 all the other iterations it has the value of ARG.
1521 For the moment, PEELED_CHREC nodes are not built. */
1522 if (res != t_true)
1524 ev_fn = chrec_dont_know;
1525 /* Try to recognize POLYNOMIAL_CHREC which appears in
1526 the form of PEELED_CHREC, but guard the process with
1527 a bool variable to keep the analyzer from infinite
1528 recurrence for real PEELED_RECs. */
1529 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1531 simplify_peeled_chrec_p = false;
1532 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1533 simplify_peeled_chrec_p = true;
1537 /* When there are multiple back edges of the loop (which in fact never
1538 happens currently, but nevertheless), merge their evolutions. */
1539 evolution_function = chrec_merge (evolution_function, ev_fn);
1542 if (dump_file && (dump_flags & TDF_SCEV))
1544 fprintf (dump_file, " (evolution_function = ");
1545 print_generic_expr (dump_file, evolution_function, 0);
1546 fprintf (dump_file, "))\n");
1549 return evolution_function;
1552 /* Given a loop-phi-node, return the initial conditions of the
1553 variable on entry of the loop. When the CCP has propagated
1554 constants into the loop-phi-node, the initial condition is
1555 instantiated, otherwise the initial condition is kept symbolic.
1556 This analyzer does not analyze the evolution outside the current
1557 loop, and leaves this task to the on-demand tree reconstructor. */
1559 static tree
1560 analyze_initial_condition (gphi *loop_phi_node)
1562 int i, n;
1563 tree init_cond = chrec_not_analyzed_yet;
1564 struct loop *loop = loop_containing_stmt (loop_phi_node);
1566 if (dump_file && (dump_flags & TDF_SCEV))
1568 fprintf (dump_file, "(analyze_initial_condition \n");
1569 fprintf (dump_file, " (loop_phi_node = \n");
1570 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1571 fprintf (dump_file, ")\n");
1574 n = gimple_phi_num_args (loop_phi_node);
1575 for (i = 0; i < n; i++)
1577 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1578 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1580 /* When the branch is oriented to the loop's body, it does
1581 not contribute to the initial condition. */
1582 if (flow_bb_inside_loop_p (loop, bb))
1583 continue;
1585 if (init_cond == chrec_not_analyzed_yet)
1587 init_cond = branch;
1588 continue;
1591 if (TREE_CODE (branch) == SSA_NAME)
1593 init_cond = chrec_dont_know;
1594 break;
1597 init_cond = chrec_merge (init_cond, branch);
1600 /* Ooops -- a loop without an entry??? */
1601 if (init_cond == chrec_not_analyzed_yet)
1602 init_cond = chrec_dont_know;
1604 /* During early loop unrolling we do not have fully constant propagated IL.
1605 Handle degenerate PHIs here to not miss important unrollings. */
1606 if (TREE_CODE (init_cond) == SSA_NAME)
1608 gimple def = SSA_NAME_DEF_STMT (init_cond);
1609 if (gphi *phi = dyn_cast <gphi *> (def))
1611 tree res = degenerate_phi_result (phi);
1612 if (res != NULL_TREE
1613 /* Only allow invariants here, otherwise we may break
1614 loop-closed SSA form. */
1615 && is_gimple_min_invariant (res))
1616 init_cond = res;
1620 if (dump_file && (dump_flags & TDF_SCEV))
1622 fprintf (dump_file, " (init_cond = ");
1623 print_generic_expr (dump_file, init_cond, 0);
1624 fprintf (dump_file, "))\n");
1627 return init_cond;
1630 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1632 static tree
1633 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1635 tree res;
1636 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1637 tree init_cond;
1639 if (phi_loop != loop)
1641 struct loop *subloop;
1642 tree evolution_fn = analyze_scalar_evolution
1643 (phi_loop, PHI_RESULT (loop_phi_node));
1645 /* Dive one level deeper. */
1646 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1648 /* Interpret the subloop. */
1649 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1650 return res;
1653 /* Otherwise really interpret the loop phi. */
1654 init_cond = analyze_initial_condition (loop_phi_node);
1655 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1657 /* Verify we maintained the correct initial condition throughout
1658 possible conversions in the SSA chain. */
1659 if (res != chrec_dont_know)
1661 tree new_init = res;
1662 if (CONVERT_EXPR_P (res)
1663 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1664 new_init = fold_convert (TREE_TYPE (res),
1665 CHREC_LEFT (TREE_OPERAND (res, 0)));
1666 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1667 new_init = CHREC_LEFT (res);
1668 STRIP_USELESS_TYPE_CONVERSION (new_init);
1669 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1670 || !operand_equal_p (init_cond, new_init, 0))
1671 return chrec_dont_know;
1674 return res;
1677 /* This function merges the branches of a condition-phi-node,
1678 contained in the outermost loop, and whose arguments are already
1679 analyzed. */
1681 static tree
1682 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1684 int i, n = gimple_phi_num_args (condition_phi);
1685 tree res = chrec_not_analyzed_yet;
1687 for (i = 0; i < n; i++)
1689 tree branch_chrec;
1691 if (backedge_phi_arg_p (condition_phi, i))
1693 res = chrec_dont_know;
1694 break;
1697 branch_chrec = analyze_scalar_evolution
1698 (loop, PHI_ARG_DEF (condition_phi, i));
1700 res = chrec_merge (res, branch_chrec);
1703 return res;
1706 /* Interpret the operation RHS1 OP RHS2. If we didn't
1707 analyze this node before, follow the definitions until ending
1708 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1709 return path, this function propagates evolutions (ala constant copy
1710 propagation). OPND1 is not a GIMPLE expression because we could
1711 analyze the effect of an inner loop: see interpret_loop_phi. */
1713 static tree
1714 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1715 tree type, tree rhs1, enum tree_code code, tree rhs2)
1717 tree res, chrec1, chrec2;
1718 gimple def;
1720 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1722 if (is_gimple_min_invariant (rhs1))
1723 return chrec_convert (type, rhs1, at_stmt);
1725 if (code == SSA_NAME)
1726 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1727 at_stmt);
1729 if (code == ASSERT_EXPR)
1731 rhs1 = ASSERT_EXPR_VAR (rhs1);
1732 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1733 at_stmt);
1737 switch (code)
1739 case ADDR_EXPR:
1740 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1741 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1743 machine_mode mode;
1744 HOST_WIDE_INT bitsize, bitpos;
1745 int unsignedp;
1746 int volatilep = 0;
1747 tree base, offset;
1748 tree chrec3;
1749 tree unitpos;
1751 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1752 &bitsize, &bitpos, &offset,
1753 &mode, &unsignedp, &volatilep, false);
1755 if (TREE_CODE (base) == MEM_REF)
1757 rhs2 = TREE_OPERAND (base, 1);
1758 rhs1 = TREE_OPERAND (base, 0);
1760 chrec1 = analyze_scalar_evolution (loop, rhs1);
1761 chrec2 = analyze_scalar_evolution (loop, rhs2);
1762 chrec1 = chrec_convert (type, chrec1, at_stmt);
1763 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1764 chrec1 = instantiate_parameters (loop, chrec1);
1765 chrec2 = instantiate_parameters (loop, chrec2);
1766 res = chrec_fold_plus (type, chrec1, chrec2);
1768 else
1770 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1771 chrec1 = chrec_convert (type, chrec1, at_stmt);
1772 res = chrec1;
1775 if (offset != NULL_TREE)
1777 chrec2 = analyze_scalar_evolution (loop, offset);
1778 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1779 chrec2 = instantiate_parameters (loop, chrec2);
1780 res = chrec_fold_plus (type, res, chrec2);
1783 if (bitpos != 0)
1785 gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
1787 unitpos = size_int (bitpos / BITS_PER_UNIT);
1788 chrec3 = analyze_scalar_evolution (loop, unitpos);
1789 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1790 chrec3 = instantiate_parameters (loop, chrec3);
1791 res = chrec_fold_plus (type, res, chrec3);
1794 else
1795 res = chrec_dont_know;
1796 break;
1798 case POINTER_PLUS_EXPR:
1799 chrec1 = analyze_scalar_evolution (loop, rhs1);
1800 chrec2 = analyze_scalar_evolution (loop, rhs2);
1801 chrec1 = chrec_convert (type, chrec1, at_stmt);
1802 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1803 chrec1 = instantiate_parameters (loop, chrec1);
1804 chrec2 = instantiate_parameters (loop, chrec2);
1805 res = chrec_fold_plus (type, chrec1, chrec2);
1806 break;
1808 case PLUS_EXPR:
1809 chrec1 = analyze_scalar_evolution (loop, rhs1);
1810 chrec2 = analyze_scalar_evolution (loop, rhs2);
1811 chrec1 = chrec_convert (type, chrec1, at_stmt);
1812 chrec2 = chrec_convert (type, chrec2, at_stmt);
1813 chrec1 = instantiate_parameters (loop, chrec1);
1814 chrec2 = instantiate_parameters (loop, chrec2);
1815 res = chrec_fold_plus (type, chrec1, chrec2);
1816 break;
1818 case MINUS_EXPR:
1819 chrec1 = analyze_scalar_evolution (loop, rhs1);
1820 chrec2 = analyze_scalar_evolution (loop, rhs2);
1821 chrec1 = chrec_convert (type, chrec1, at_stmt);
1822 chrec2 = chrec_convert (type, chrec2, at_stmt);
1823 chrec1 = instantiate_parameters (loop, chrec1);
1824 chrec2 = instantiate_parameters (loop, chrec2);
1825 res = chrec_fold_minus (type, chrec1, chrec2);
1826 break;
1828 case NEGATE_EXPR:
1829 chrec1 = analyze_scalar_evolution (loop, rhs1);
1830 chrec1 = chrec_convert (type, chrec1, at_stmt);
1831 /* TYPE may be integer, real or complex, so use fold_convert. */
1832 chrec1 = instantiate_parameters (loop, chrec1);
1833 res = chrec_fold_multiply (type, chrec1,
1834 fold_convert (type, integer_minus_one_node));
1835 break;
1837 case BIT_NOT_EXPR:
1838 /* Handle ~X as -1 - X. */
1839 chrec1 = analyze_scalar_evolution (loop, rhs1);
1840 chrec1 = chrec_convert (type, chrec1, at_stmt);
1841 chrec1 = instantiate_parameters (loop, chrec1);
1842 res = chrec_fold_minus (type,
1843 fold_convert (type, integer_minus_one_node),
1844 chrec1);
1845 break;
1847 case MULT_EXPR:
1848 chrec1 = analyze_scalar_evolution (loop, rhs1);
1849 chrec2 = analyze_scalar_evolution (loop, rhs2);
1850 chrec1 = chrec_convert (type, chrec1, at_stmt);
1851 chrec2 = chrec_convert (type, chrec2, at_stmt);
1852 chrec1 = instantiate_parameters (loop, chrec1);
1853 chrec2 = instantiate_parameters (loop, chrec2);
1854 res = chrec_fold_multiply (type, chrec1, chrec2);
1855 break;
1857 CASE_CONVERT:
1858 /* In case we have a truncation of a widened operation that in
1859 the truncated type has undefined overflow behavior analyze
1860 the operation done in an unsigned type of the same precision
1861 as the final truncation. We cannot derive a scalar evolution
1862 for the widened operation but for the truncated result. */
1863 if (TREE_CODE (type) == INTEGER_TYPE
1864 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1865 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1866 && TYPE_OVERFLOW_UNDEFINED (type)
1867 && TREE_CODE (rhs1) == SSA_NAME
1868 && (def = SSA_NAME_DEF_STMT (rhs1))
1869 && is_gimple_assign (def)
1870 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1871 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1873 tree utype = unsigned_type_for (type);
1874 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1875 gimple_assign_rhs1 (def),
1876 gimple_assign_rhs_code (def),
1877 gimple_assign_rhs2 (def));
1879 else
1880 chrec1 = analyze_scalar_evolution (loop, rhs1);
1881 res = chrec_convert (type, chrec1, at_stmt);
1882 break;
1884 default:
1885 res = chrec_dont_know;
1886 break;
1889 return res;
1892 /* Interpret the expression EXPR. */
1894 static tree
1895 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1897 enum tree_code code;
1898 tree type = TREE_TYPE (expr), op0, op1;
1900 if (automatically_generated_chrec_p (expr))
1901 return expr;
1903 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1904 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1905 return chrec_dont_know;
1907 extract_ops_from_tree (expr, &code, &op0, &op1);
1909 return interpret_rhs_expr (loop, at_stmt, type,
1910 op0, code, op1);
1913 /* Interpret the rhs of the assignment STMT. */
1915 static tree
1916 interpret_gimple_assign (struct loop *loop, gimple stmt)
1918 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1919 enum tree_code code = gimple_assign_rhs_code (stmt);
1921 return interpret_rhs_expr (loop, stmt, type,
1922 gimple_assign_rhs1 (stmt), code,
1923 gimple_assign_rhs2 (stmt));
1928 /* This section contains all the entry points:
1929 - number_of_iterations_in_loop,
1930 - analyze_scalar_evolution,
1931 - instantiate_parameters.
1934 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1935 common ancestor of DEF_LOOP and USE_LOOP. */
1937 static tree
1938 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1939 struct loop *def_loop,
1940 tree ev)
1942 bool val;
1943 tree res;
1945 if (def_loop == wrto_loop)
1946 return ev;
1948 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1949 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1951 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
1952 return res;
1954 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1957 /* Helper recursive function. */
1959 static tree
1960 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1962 tree type = TREE_TYPE (var);
1963 gimple def;
1964 basic_block bb;
1965 struct loop *def_loop;
1967 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1968 return chrec_dont_know;
1970 if (TREE_CODE (var) != SSA_NAME)
1971 return interpret_expr (loop, NULL, var);
1973 def = SSA_NAME_DEF_STMT (var);
1974 bb = gimple_bb (def);
1975 def_loop = bb ? bb->loop_father : NULL;
1977 if (bb == NULL
1978 || !flow_bb_inside_loop_p (loop, bb))
1980 /* Keep the symbolic form. */
1981 res = var;
1982 goto set_and_end;
1985 if (res != chrec_not_analyzed_yet)
1987 if (loop != bb->loop_father)
1988 res = compute_scalar_evolution_in_loop
1989 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1991 goto set_and_end;
1994 if (loop != def_loop)
1996 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1997 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1999 goto set_and_end;
2002 switch (gimple_code (def))
2004 case GIMPLE_ASSIGN:
2005 res = interpret_gimple_assign (loop, def);
2006 break;
2008 case GIMPLE_PHI:
2009 if (loop_phi_node_p (def))
2010 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2011 else
2012 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2013 break;
2015 default:
2016 res = chrec_dont_know;
2017 break;
2020 set_and_end:
2022 /* Keep the symbolic form. */
2023 if (res == chrec_dont_know)
2024 res = var;
2026 if (loop == def_loop)
2027 set_scalar_evolution (block_before_loop (loop), var, res);
2029 return res;
2032 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2033 LOOP. LOOP is the loop in which the variable is used.
2035 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2036 pointer to the statement that uses this variable, in order to
2037 determine the evolution function of the variable, use the following
2038 calls:
2040 loop_p loop = loop_containing_stmt (stmt);
2041 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2042 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2045 tree
2046 analyze_scalar_evolution (struct loop *loop, tree var)
2048 tree res;
2050 if (dump_file && (dump_flags & TDF_SCEV))
2052 fprintf (dump_file, "(analyze_scalar_evolution \n");
2053 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2054 fprintf (dump_file, " (scalar = ");
2055 print_generic_expr (dump_file, var, 0);
2056 fprintf (dump_file, ")\n");
2059 res = get_scalar_evolution (block_before_loop (loop), var);
2060 res = analyze_scalar_evolution_1 (loop, var, res);
2062 if (dump_file && (dump_flags & TDF_SCEV))
2063 fprintf (dump_file, ")\n");
2065 return res;
2068 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2070 static tree
2071 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2073 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2076 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2077 WRTO_LOOP (which should be a superloop of USE_LOOP)
2079 FOLDED_CASTS is set to true if resolve_mixers used
2080 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2081 at the moment in order to keep things simple).
2083 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2084 example:
2086 for (i = 0; i < 100; i++) -- loop 1
2088 for (j = 0; j < 100; j++) -- loop 2
2090 k1 = i;
2091 k2 = j;
2093 use2 (k1, k2);
2095 for (t = 0; t < 100; t++) -- loop 3
2096 use3 (k1, k2);
2099 use1 (k1, k2);
2102 Both k1 and k2 are invariants in loop3, thus
2103 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2104 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2106 As they are invariant, it does not matter whether we consider their
2107 usage in loop 3 or loop 2, hence
2108 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2109 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2110 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2111 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2113 Similarly for their evolutions with respect to loop 1. The values of K2
2114 in the use in loop 2 vary independently on loop 1, thus we cannot express
2115 the evolution with respect to loop 1:
2116 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2117 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2118 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2119 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2121 The value of k2 in the use in loop 1 is known, though:
2122 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2123 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2126 static tree
2127 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2128 tree version, bool *folded_casts)
2130 bool val = false;
2131 tree ev = version, tmp;
2133 /* We cannot just do
2135 tmp = analyze_scalar_evolution (use_loop, version);
2136 ev = resolve_mixers (wrto_loop, tmp);
2138 as resolve_mixers would query the scalar evolution with respect to
2139 wrto_loop. For example, in the situation described in the function
2140 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2141 version = k2. Then
2143 analyze_scalar_evolution (use_loop, version) = k2
2145 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2146 is 100, which is a wrong result, since we are interested in the
2147 value in loop 3.
2149 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2150 each time checking that there is no evolution in the inner loop. */
2152 if (folded_casts)
2153 *folded_casts = false;
2154 while (1)
2156 tmp = analyze_scalar_evolution (use_loop, ev);
2157 ev = resolve_mixers (use_loop, tmp);
2159 if (folded_casts && tmp != ev)
2160 *folded_casts = true;
2162 if (use_loop == wrto_loop)
2163 return ev;
2165 /* If the value of the use changes in the inner loop, we cannot express
2166 its value in the outer loop (we might try to return interval chrec,
2167 but we do not have a user for it anyway) */
2168 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2169 || !val)
2170 return chrec_dont_know;
2172 use_loop = loop_outer (use_loop);
2177 /* Hashtable helpers for a temporary hash-table used when
2178 instantiating a CHREC or resolving mixers. For this use
2179 instantiated_below is always the same. */
2181 struct instantiate_cache_type
2183 htab_t map;
2184 vec<scev_info_str> entries;
2186 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2187 ~instantiate_cache_type ();
2188 tree get (unsigned slot) { return entries[slot].chrec; }
2189 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2192 instantiate_cache_type::~instantiate_cache_type ()
2194 if (map != NULL)
2196 htab_delete (map);
2197 entries.release ();
2201 /* Cache to avoid infinite recursion when instantiating an SSA name.
2202 Live during the outermost instantiate_scev or resolve_mixers call. */
2203 static instantiate_cache_type *global_cache;
2205 /* Computes a hash function for database element ELT. */
2207 static inline hashval_t
2208 hash_idx_scev_info (const void *elt_)
2210 unsigned idx = ((size_t) elt_) - 2;
2211 return scev_info_hasher::hash (&global_cache->entries[idx]);
2214 /* Compares database elements E1 and E2. */
2216 static inline int
2217 eq_idx_scev_info (const void *e1, const void *e2)
2219 unsigned idx1 = ((size_t) e1) - 2;
2220 return scev_info_hasher::equal (&global_cache->entries[idx1],
2221 (const scev_info_str *) e2);
2224 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2226 static unsigned
2227 get_instantiated_value_entry (instantiate_cache_type &cache,
2228 tree name, basic_block instantiate_below)
2230 if (!cache.map)
2232 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2233 cache.entries.create (10);
2236 scev_info_str e;
2237 e.name_version = SSA_NAME_VERSION (name);
2238 e.instantiated_below = instantiate_below->index;
2239 void **slot = htab_find_slot_with_hash (cache.map, &e,
2240 scev_info_hasher::hash (&e), INSERT);
2241 if (!*slot)
2243 e.chrec = chrec_not_analyzed_yet;
2244 *slot = (void *)(size_t)(cache.entries.length () + 2);
2245 cache.entries.safe_push (e);
2248 return ((size_t)*slot) - 2;
2252 /* Return the closed_loop_phi node for VAR. If there is none, return
2253 NULL_TREE. */
2255 static tree
2256 loop_closed_phi_def (tree var)
2258 struct loop *loop;
2259 edge exit;
2260 gphi *phi;
2261 gphi_iterator psi;
2263 if (var == NULL_TREE
2264 || TREE_CODE (var) != SSA_NAME)
2265 return NULL_TREE;
2267 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2268 exit = single_exit (loop);
2269 if (!exit)
2270 return NULL_TREE;
2272 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2274 phi = psi.phi ();
2275 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2276 return PHI_RESULT (phi);
2279 return NULL_TREE;
2282 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2283 tree, bool, int);
2285 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2286 and EVOLUTION_LOOP, that were left under a symbolic form.
2288 CHREC is an SSA_NAME to be instantiated.
2290 CACHE is the cache of already instantiated values.
2292 FOLD_CONVERSIONS should be set to true when the conversions that
2293 may wrap in signed/pointer type are folded, as long as the value of
2294 the chrec is preserved.
2296 SIZE_EXPR is used for computing the size of the expression to be
2297 instantiated, and to stop if it exceeds some limit. */
2299 static tree
2300 instantiate_scev_name (basic_block instantiate_below,
2301 struct loop *evolution_loop, struct loop *inner_loop,
2302 tree chrec,
2303 bool fold_conversions,
2304 int size_expr)
2306 tree res;
2307 struct loop *def_loop;
2308 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2310 /* A parameter (or loop invariant and we do not want to include
2311 evolutions in outer loops), nothing to do. */
2312 if (!def_bb
2313 || loop_depth (def_bb->loop_father) == 0
2314 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2315 return chrec;
2317 /* We cache the value of instantiated variable to avoid exponential
2318 time complexity due to reevaluations. We also store the convenient
2319 value in the cache in order to prevent infinite recursion -- we do
2320 not want to instantiate the SSA_NAME if it is in a mixer
2321 structure. This is used for avoiding the instantiation of
2322 recursively defined functions, such as:
2324 | a_2 -> {0, +, 1, +, a_2}_1 */
2326 unsigned si = get_instantiated_value_entry (*global_cache,
2327 chrec, instantiate_below);
2328 if (global_cache->get (si) != chrec_not_analyzed_yet)
2329 return global_cache->get (si);
2331 /* On recursion return chrec_dont_know. */
2332 global_cache->set (si, chrec_dont_know);
2334 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2336 /* If the analysis yields a parametric chrec, instantiate the
2337 result again. */
2338 res = analyze_scalar_evolution (def_loop, chrec);
2340 /* Don't instantiate default definitions. */
2341 if (TREE_CODE (res) == SSA_NAME
2342 && SSA_NAME_IS_DEFAULT_DEF (res))
2345 /* Don't instantiate loop-closed-ssa phi nodes. */
2346 else if (TREE_CODE (res) == SSA_NAME
2347 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2348 > loop_depth (def_loop))
2350 if (res == chrec)
2351 res = loop_closed_phi_def (chrec);
2352 else
2353 res = chrec;
2355 /* When there is no loop_closed_phi_def, it means that the
2356 variable is not used after the loop: try to still compute the
2357 value of the variable when exiting the loop. */
2358 if (res == NULL_TREE)
2360 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2361 res = analyze_scalar_evolution (loop, chrec);
2362 res = compute_overall_effect_of_inner_loop (loop, res);
2363 res = instantiate_scev_r (instantiate_below, evolution_loop,
2364 inner_loop, res,
2365 fold_conversions, size_expr);
2367 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2368 gimple_bb (SSA_NAME_DEF_STMT (res))))
2369 res = chrec_dont_know;
2372 else if (res != chrec_dont_know)
2374 if (inner_loop
2375 && def_bb->loop_father != inner_loop
2376 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2377 /* ??? We could try to compute the overall effect of the loop here. */
2378 res = chrec_dont_know;
2379 else
2380 res = instantiate_scev_r (instantiate_below, evolution_loop,
2381 inner_loop, res,
2382 fold_conversions, size_expr);
2385 /* Store the correct value to the cache. */
2386 global_cache->set (si, res);
2387 return res;
2390 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2391 and EVOLUTION_LOOP, that were left under a symbolic form.
2393 CHREC is a polynomial chain of recurrence to be instantiated.
2395 CACHE is the cache of already instantiated values.
2397 FOLD_CONVERSIONS should be set to true when the conversions that
2398 may wrap in signed/pointer type are folded, as long as the value of
2399 the chrec is preserved.
2401 SIZE_EXPR is used for computing the size of the expression to be
2402 instantiated, and to stop if it exceeds some limit. */
2404 static tree
2405 instantiate_scev_poly (basic_block instantiate_below,
2406 struct loop *evolution_loop, struct loop *,
2407 tree chrec, bool fold_conversions, int size_expr)
2409 tree op1;
2410 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2411 get_chrec_loop (chrec),
2412 CHREC_LEFT (chrec), fold_conversions,
2413 size_expr);
2414 if (op0 == chrec_dont_know)
2415 return chrec_dont_know;
2417 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2418 get_chrec_loop (chrec),
2419 CHREC_RIGHT (chrec), fold_conversions,
2420 size_expr);
2421 if (op1 == chrec_dont_know)
2422 return chrec_dont_know;
2424 if (CHREC_LEFT (chrec) != op0
2425 || CHREC_RIGHT (chrec) != op1)
2427 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2428 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2431 return chrec;
2434 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2435 and EVOLUTION_LOOP, that were left under a symbolic form.
2437 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2439 CACHE is the cache of already instantiated values.
2441 FOLD_CONVERSIONS should be set to true when the conversions that
2442 may wrap in signed/pointer type are folded, as long as the value of
2443 the chrec is preserved.
2445 SIZE_EXPR is used for computing the size of the expression to be
2446 instantiated, and to stop if it exceeds some limit. */
2448 static tree
2449 instantiate_scev_binary (basic_block instantiate_below,
2450 struct loop *evolution_loop, struct loop *inner_loop,
2451 tree chrec, enum tree_code code,
2452 tree type, tree c0, tree c1,
2453 bool fold_conversions, int size_expr)
2455 tree op1;
2456 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2457 c0, fold_conversions, size_expr);
2458 if (op0 == chrec_dont_know)
2459 return chrec_dont_know;
2461 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2462 c1, fold_conversions, size_expr);
2463 if (op1 == chrec_dont_know)
2464 return chrec_dont_know;
2466 if (c0 != op0
2467 || c1 != op1)
2469 op0 = chrec_convert (type, op0, NULL);
2470 op1 = chrec_convert_rhs (type, op1, NULL);
2472 switch (code)
2474 case POINTER_PLUS_EXPR:
2475 case PLUS_EXPR:
2476 return chrec_fold_plus (type, op0, op1);
2478 case MINUS_EXPR:
2479 return chrec_fold_minus (type, op0, op1);
2481 case MULT_EXPR:
2482 return chrec_fold_multiply (type, op0, op1);
2484 default:
2485 gcc_unreachable ();
2489 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2492 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2493 and EVOLUTION_LOOP, that were left under a symbolic form.
2495 "CHREC" is an array reference to be instantiated.
2497 CACHE is the cache of already instantiated values.
2499 FOLD_CONVERSIONS should be set to true when the conversions that
2500 may wrap in signed/pointer type are folded, as long as the value of
2501 the chrec is preserved.
2503 SIZE_EXPR is used for computing the size of the expression to be
2504 instantiated, and to stop if it exceeds some limit. */
2506 static tree
2507 instantiate_array_ref (basic_block instantiate_below,
2508 struct loop *evolution_loop, struct loop *inner_loop,
2509 tree chrec, bool fold_conversions, int size_expr)
2511 tree res;
2512 tree index = TREE_OPERAND (chrec, 1);
2513 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2514 inner_loop, index,
2515 fold_conversions, size_expr);
2517 if (op1 == chrec_dont_know)
2518 return chrec_dont_know;
2520 if (chrec && op1 == index)
2521 return chrec;
2523 res = unshare_expr (chrec);
2524 TREE_OPERAND (res, 1) = op1;
2525 return res;
2528 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2529 and EVOLUTION_LOOP, that were left under a symbolic form.
2531 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2532 instantiated.
2534 CACHE is the cache of already instantiated values.
2536 FOLD_CONVERSIONS should be set to true when the conversions that
2537 may wrap in signed/pointer type are folded, as long as the value of
2538 the chrec is preserved.
2540 SIZE_EXPR is used for computing the size of the expression to be
2541 instantiated, and to stop if it exceeds some limit. */
2543 static tree
2544 instantiate_scev_convert (basic_block instantiate_below,
2545 struct loop *evolution_loop, struct loop *inner_loop,
2546 tree chrec, tree type, tree op,
2547 bool fold_conversions, int size_expr)
2549 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2550 inner_loop, op,
2551 fold_conversions, size_expr);
2553 if (op0 == chrec_dont_know)
2554 return chrec_dont_know;
2556 if (fold_conversions)
2558 tree tmp = chrec_convert_aggressive (type, op0);
2559 if (tmp)
2560 return tmp;
2563 if (chrec && op0 == op)
2564 return chrec;
2566 /* If we used chrec_convert_aggressive, we can no longer assume that
2567 signed chrecs do not overflow, as chrec_convert does, so avoid
2568 calling it in that case. */
2569 if (fold_conversions)
2570 return fold_convert (type, op0);
2572 return chrec_convert (type, op0, NULL);
2575 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2576 and EVOLUTION_LOOP, that were left under a symbolic form.
2578 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2579 Handle ~X as -1 - X.
2580 Handle -X as -1 * X.
2582 CACHE is the cache of already instantiated values.
2584 FOLD_CONVERSIONS should be set to true when the conversions that
2585 may wrap in signed/pointer type are folded, as long as the value of
2586 the chrec is preserved.
2588 SIZE_EXPR is used for computing the size of the expression to be
2589 instantiated, and to stop if it exceeds some limit. */
2591 static tree
2592 instantiate_scev_not (basic_block instantiate_below,
2593 struct loop *evolution_loop, struct loop *inner_loop,
2594 tree chrec,
2595 enum tree_code code, tree type, tree op,
2596 bool fold_conversions, int size_expr)
2598 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2599 inner_loop, op,
2600 fold_conversions, size_expr);
2602 if (op0 == chrec_dont_know)
2603 return chrec_dont_know;
2605 if (op != op0)
2607 op0 = chrec_convert (type, op0, NULL);
2609 switch (code)
2611 case BIT_NOT_EXPR:
2612 return chrec_fold_minus
2613 (type, fold_convert (type, integer_minus_one_node), op0);
2615 case NEGATE_EXPR:
2616 return chrec_fold_multiply
2617 (type, fold_convert (type, integer_minus_one_node), op0);
2619 default:
2620 gcc_unreachable ();
2624 return chrec ? chrec : fold_build1 (code, type, op0);
2627 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2628 and EVOLUTION_LOOP, that were left under a symbolic form.
2630 CHREC is an expression with 3 operands to be instantiated.
2632 CACHE is the cache of already instantiated values.
2634 FOLD_CONVERSIONS should be set to true when the conversions that
2635 may wrap in signed/pointer type are folded, as long as the value of
2636 the chrec is preserved.
2638 SIZE_EXPR is used for computing the size of the expression to be
2639 instantiated, and to stop if it exceeds some limit. */
2641 static tree
2642 instantiate_scev_3 (basic_block instantiate_below,
2643 struct loop *evolution_loop, struct loop *inner_loop,
2644 tree chrec,
2645 bool fold_conversions, int size_expr)
2647 tree op1, op2;
2648 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2649 inner_loop, TREE_OPERAND (chrec, 0),
2650 fold_conversions, size_expr);
2651 if (op0 == chrec_dont_know)
2652 return chrec_dont_know;
2654 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2655 inner_loop, TREE_OPERAND (chrec, 1),
2656 fold_conversions, size_expr);
2657 if (op1 == chrec_dont_know)
2658 return chrec_dont_know;
2660 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2661 inner_loop, TREE_OPERAND (chrec, 2),
2662 fold_conversions, size_expr);
2663 if (op2 == chrec_dont_know)
2664 return chrec_dont_know;
2666 if (op0 == TREE_OPERAND (chrec, 0)
2667 && op1 == TREE_OPERAND (chrec, 1)
2668 && op2 == TREE_OPERAND (chrec, 2))
2669 return chrec;
2671 return fold_build3 (TREE_CODE (chrec),
2672 TREE_TYPE (chrec), op0, op1, op2);
2675 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2676 and EVOLUTION_LOOP, that were left under a symbolic form.
2678 CHREC is an expression with 2 operands to be instantiated.
2680 CACHE is the cache of already instantiated values.
2682 FOLD_CONVERSIONS should be set to true when the conversions that
2683 may wrap in signed/pointer type are folded, as long as the value of
2684 the chrec is preserved.
2686 SIZE_EXPR is used for computing the size of the expression to be
2687 instantiated, and to stop if it exceeds some limit. */
2689 static tree
2690 instantiate_scev_2 (basic_block instantiate_below,
2691 struct loop *evolution_loop, struct loop *inner_loop,
2692 tree chrec,
2693 bool fold_conversions, int size_expr)
2695 tree op1;
2696 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2697 inner_loop, TREE_OPERAND (chrec, 0),
2698 fold_conversions, size_expr);
2699 if (op0 == chrec_dont_know)
2700 return chrec_dont_know;
2702 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2703 inner_loop, TREE_OPERAND (chrec, 1),
2704 fold_conversions, size_expr);
2705 if (op1 == chrec_dont_know)
2706 return chrec_dont_know;
2708 if (op0 == TREE_OPERAND (chrec, 0)
2709 && op1 == TREE_OPERAND (chrec, 1))
2710 return chrec;
2712 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2715 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2716 and EVOLUTION_LOOP, that were left under a symbolic form.
2718 CHREC is an expression with 2 operands to be instantiated.
2720 CACHE is the cache of already instantiated values.
2722 FOLD_CONVERSIONS should be set to true when the conversions that
2723 may wrap in signed/pointer type are folded, as long as the value of
2724 the chrec is preserved.
2726 SIZE_EXPR is used for computing the size of the expression to be
2727 instantiated, and to stop if it exceeds some limit. */
2729 static tree
2730 instantiate_scev_1 (basic_block instantiate_below,
2731 struct loop *evolution_loop, struct loop *inner_loop,
2732 tree chrec,
2733 bool fold_conversions, int size_expr)
2735 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2736 inner_loop, TREE_OPERAND (chrec, 0),
2737 fold_conversions, size_expr);
2739 if (op0 == chrec_dont_know)
2740 return chrec_dont_know;
2742 if (op0 == TREE_OPERAND (chrec, 0))
2743 return chrec;
2745 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2748 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2749 and EVOLUTION_LOOP, that were left under a symbolic form.
2751 CHREC is the scalar evolution to instantiate.
2753 CACHE is the cache of already instantiated values.
2755 FOLD_CONVERSIONS should be set to true when the conversions that
2756 may wrap in signed/pointer type are folded, as long as the value of
2757 the chrec is preserved.
2759 SIZE_EXPR is used for computing the size of the expression to be
2760 instantiated, and to stop if it exceeds some limit. */
2762 static tree
2763 instantiate_scev_r (basic_block instantiate_below,
2764 struct loop *evolution_loop, struct loop *inner_loop,
2765 tree chrec,
2766 bool fold_conversions, int size_expr)
2768 /* Give up if the expression is larger than the MAX that we allow. */
2769 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2770 return chrec_dont_know;
2772 if (chrec == NULL_TREE
2773 || automatically_generated_chrec_p (chrec)
2774 || is_gimple_min_invariant (chrec))
2775 return chrec;
2777 switch (TREE_CODE (chrec))
2779 case SSA_NAME:
2780 return instantiate_scev_name (instantiate_below, evolution_loop,
2781 inner_loop, chrec,
2782 fold_conversions, size_expr);
2784 case POLYNOMIAL_CHREC:
2785 return instantiate_scev_poly (instantiate_below, evolution_loop,
2786 inner_loop, chrec,
2787 fold_conversions, size_expr);
2789 case POINTER_PLUS_EXPR:
2790 case PLUS_EXPR:
2791 case MINUS_EXPR:
2792 case MULT_EXPR:
2793 return instantiate_scev_binary (instantiate_below, evolution_loop,
2794 inner_loop, chrec,
2795 TREE_CODE (chrec), chrec_type (chrec),
2796 TREE_OPERAND (chrec, 0),
2797 TREE_OPERAND (chrec, 1),
2798 fold_conversions, size_expr);
2800 CASE_CONVERT:
2801 return instantiate_scev_convert (instantiate_below, evolution_loop,
2802 inner_loop, chrec,
2803 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2804 fold_conversions, size_expr);
2806 case NEGATE_EXPR:
2807 case BIT_NOT_EXPR:
2808 return instantiate_scev_not (instantiate_below, evolution_loop,
2809 inner_loop, chrec,
2810 TREE_CODE (chrec), TREE_TYPE (chrec),
2811 TREE_OPERAND (chrec, 0),
2812 fold_conversions, size_expr);
2814 case ADDR_EXPR:
2815 case SCEV_NOT_KNOWN:
2816 return chrec_dont_know;
2818 case SCEV_KNOWN:
2819 return chrec_known;
2821 case ARRAY_REF:
2822 return instantiate_array_ref (instantiate_below, evolution_loop,
2823 inner_loop, chrec,
2824 fold_conversions, size_expr);
2826 default:
2827 break;
2830 if (VL_EXP_CLASS_P (chrec))
2831 return chrec_dont_know;
2833 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2835 case 3:
2836 return instantiate_scev_3 (instantiate_below, evolution_loop,
2837 inner_loop, chrec,
2838 fold_conversions, size_expr);
2840 case 2:
2841 return instantiate_scev_2 (instantiate_below, evolution_loop,
2842 inner_loop, chrec,
2843 fold_conversions, size_expr);
2845 case 1:
2846 return instantiate_scev_1 (instantiate_below, evolution_loop,
2847 inner_loop, chrec,
2848 fold_conversions, size_expr);
2850 case 0:
2851 return chrec;
2853 default:
2854 break;
2857 /* Too complicated to handle. */
2858 return chrec_dont_know;
2861 /* Analyze all the parameters of the chrec that were left under a
2862 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2863 recursive instantiation of parameters: a parameter is a variable
2864 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2865 a function parameter. */
2867 tree
2868 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2869 tree chrec)
2871 tree res;
2873 if (dump_file && (dump_flags & TDF_SCEV))
2875 fprintf (dump_file, "(instantiate_scev \n");
2876 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2877 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2878 fprintf (dump_file, " (chrec = ");
2879 print_generic_expr (dump_file, chrec, 0);
2880 fprintf (dump_file, ")\n");
2883 bool destr = false;
2884 if (!global_cache)
2886 global_cache = new instantiate_cache_type;
2887 destr = true;
2890 res = instantiate_scev_r (instantiate_below, evolution_loop,
2891 NULL, chrec, false, 0);
2893 if (destr)
2895 delete global_cache;
2896 global_cache = NULL;
2899 if (dump_file && (dump_flags & TDF_SCEV))
2901 fprintf (dump_file, " (res = ");
2902 print_generic_expr (dump_file, res, 0);
2903 fprintf (dump_file, "))\n");
2906 return res;
2909 /* Similar to instantiate_parameters, but does not introduce the
2910 evolutions in outer loops for LOOP invariants in CHREC, and does not
2911 care about causing overflows, as long as they do not affect value
2912 of an expression. */
2914 tree
2915 resolve_mixers (struct loop *loop, tree chrec)
2917 bool destr = false;
2918 if (!global_cache)
2920 global_cache = new instantiate_cache_type;
2921 destr = true;
2924 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
2925 chrec, true, 0);
2927 if (destr)
2929 delete global_cache;
2930 global_cache = NULL;
2933 return ret;
2936 /* Entry point for the analysis of the number of iterations pass.
2937 This function tries to safely approximate the number of iterations
2938 the loop will run. When this property is not decidable at compile
2939 time, the result is chrec_dont_know. Otherwise the result is a
2940 scalar or a symbolic parameter. When the number of iterations may
2941 be equal to zero and the property cannot be determined at compile
2942 time, the result is a COND_EXPR that represents in a symbolic form
2943 the conditions under which the number of iterations is not zero.
2945 Example of analysis: suppose that the loop has an exit condition:
2947 "if (b > 49) goto end_loop;"
2949 and that in a previous analysis we have determined that the
2950 variable 'b' has an evolution function:
2952 "EF = {23, +, 5}_2".
2954 When we evaluate the function at the point 5, i.e. the value of the
2955 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2956 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2957 the loop body has been executed 6 times. */
2959 tree
2960 number_of_latch_executions (struct loop *loop)
2962 edge exit;
2963 struct tree_niter_desc niter_desc;
2964 tree may_be_zero;
2965 tree res;
2967 /* Determine whether the number of iterations in loop has already
2968 been computed. */
2969 res = loop->nb_iterations;
2970 if (res)
2971 return res;
2973 may_be_zero = NULL_TREE;
2975 if (dump_file && (dump_flags & TDF_SCEV))
2976 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2978 res = chrec_dont_know;
2979 exit = single_exit (loop);
2981 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2983 may_be_zero = niter_desc.may_be_zero;
2984 res = niter_desc.niter;
2987 if (res == chrec_dont_know
2988 || !may_be_zero
2989 || integer_zerop (may_be_zero))
2991 else if (integer_nonzerop (may_be_zero))
2992 res = build_int_cst (TREE_TYPE (res), 0);
2994 else if (COMPARISON_CLASS_P (may_be_zero))
2995 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2996 build_int_cst (TREE_TYPE (res), 0), res);
2997 else
2998 res = chrec_dont_know;
3000 if (dump_file && (dump_flags & TDF_SCEV))
3002 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
3003 print_generic_expr (dump_file, res, 0);
3004 fprintf (dump_file, "))\n");
3007 loop->nb_iterations = res;
3008 return res;
3012 /* Counters for the stats. */
3014 struct chrec_stats
3016 unsigned nb_chrecs;
3017 unsigned nb_affine;
3018 unsigned nb_affine_multivar;
3019 unsigned nb_higher_poly;
3020 unsigned nb_chrec_dont_know;
3021 unsigned nb_undetermined;
3024 /* Reset the counters. */
3026 static inline void
3027 reset_chrecs_counters (struct chrec_stats *stats)
3029 stats->nb_chrecs = 0;
3030 stats->nb_affine = 0;
3031 stats->nb_affine_multivar = 0;
3032 stats->nb_higher_poly = 0;
3033 stats->nb_chrec_dont_know = 0;
3034 stats->nb_undetermined = 0;
3037 /* Dump the contents of a CHREC_STATS structure. */
3039 static void
3040 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3042 fprintf (file, "\n(\n");
3043 fprintf (file, "-----------------------------------------\n");
3044 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3045 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3046 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3047 stats->nb_higher_poly);
3048 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3049 fprintf (file, "-----------------------------------------\n");
3050 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3051 fprintf (file, "%d\twith undetermined coefficients\n",
3052 stats->nb_undetermined);
3053 fprintf (file, "-----------------------------------------\n");
3054 fprintf (file, "%d\tchrecs in the scev database\n",
3055 (int) scalar_evolution_info->elements ());
3056 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3057 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3058 fprintf (file, "-----------------------------------------\n");
3059 fprintf (file, ")\n\n");
3062 /* Gather statistics about CHREC. */
3064 static void
3065 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3067 if (dump_file && (dump_flags & TDF_STATS))
3069 fprintf (dump_file, "(classify_chrec ");
3070 print_generic_expr (dump_file, chrec, 0);
3071 fprintf (dump_file, "\n");
3074 stats->nb_chrecs++;
3076 if (chrec == NULL_TREE)
3078 stats->nb_undetermined++;
3079 return;
3082 switch (TREE_CODE (chrec))
3084 case POLYNOMIAL_CHREC:
3085 if (evolution_function_is_affine_p (chrec))
3087 if (dump_file && (dump_flags & TDF_STATS))
3088 fprintf (dump_file, " affine_univariate\n");
3089 stats->nb_affine++;
3091 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3093 if (dump_file && (dump_flags & TDF_STATS))
3094 fprintf (dump_file, " affine_multivariate\n");
3095 stats->nb_affine_multivar++;
3097 else
3099 if (dump_file && (dump_flags & TDF_STATS))
3100 fprintf (dump_file, " higher_degree_polynomial\n");
3101 stats->nb_higher_poly++;
3104 break;
3106 default:
3107 break;
3110 if (chrec_contains_undetermined (chrec))
3112 if (dump_file && (dump_flags & TDF_STATS))
3113 fprintf (dump_file, " undetermined\n");
3114 stats->nb_undetermined++;
3117 if (dump_file && (dump_flags & TDF_STATS))
3118 fprintf (dump_file, ")\n");
3121 /* Classify the chrecs of the whole database. */
3123 void
3124 gather_stats_on_scev_database (void)
3126 struct chrec_stats stats;
3128 if (!dump_file)
3129 return;
3131 reset_chrecs_counters (&stats);
3133 hash_table<scev_info_hasher>::iterator iter;
3134 scev_info_str *elt;
3135 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3136 iter)
3137 gather_chrec_stats (elt->chrec, &stats);
3139 dump_chrecs_stats (dump_file, &stats);
3144 /* Initializer. */
3146 static void
3147 initialize_scalar_evolutions_analyzer (void)
3149 /* The elements below are unique. */
3150 if (chrec_dont_know == NULL_TREE)
3152 chrec_not_analyzed_yet = NULL_TREE;
3153 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3154 chrec_known = make_node (SCEV_KNOWN);
3155 TREE_TYPE (chrec_dont_know) = void_type_node;
3156 TREE_TYPE (chrec_known) = void_type_node;
3160 /* Initialize the analysis of scalar evolutions for LOOPS. */
3162 void
3163 scev_initialize (void)
3165 struct loop *loop;
3167 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3169 initialize_scalar_evolutions_analyzer ();
3171 FOR_EACH_LOOP (loop, 0)
3173 loop->nb_iterations = NULL_TREE;
3177 /* Return true if SCEV is initialized. */
3179 bool
3180 scev_initialized_p (void)
3182 return scalar_evolution_info != NULL;
3185 /* Cleans up the information cached by the scalar evolutions analysis
3186 in the hash table. */
3188 void
3189 scev_reset_htab (void)
3191 if (!scalar_evolution_info)
3192 return;
3194 scalar_evolution_info->empty ();
3197 /* Cleans up the information cached by the scalar evolutions analysis
3198 in the hash table and in the loop->nb_iterations. */
3200 void
3201 scev_reset (void)
3203 struct loop *loop;
3205 scev_reset_htab ();
3207 FOR_EACH_LOOP (loop, 0)
3209 loop->nb_iterations = NULL_TREE;
3213 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3214 respect to WRTO_LOOP and returns its base and step in IV if possible
3215 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3216 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3217 invariant in LOOP. Otherwise we require it to be an integer constant.
3219 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3220 because it is computed in signed arithmetics). Consequently, adding an
3221 induction variable
3223 for (i = IV->base; ; i += IV->step)
3225 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3226 false for the type of the induction variable, or you can prove that i does
3227 not wrap by some other argument. Otherwise, this might introduce undefined
3228 behavior, and
3230 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3232 must be used instead. */
3234 bool
3235 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3236 affine_iv *iv, bool allow_nonconstant_step)
3238 tree type, ev;
3239 bool folded_casts;
3241 iv->base = NULL_TREE;
3242 iv->step = NULL_TREE;
3243 iv->no_overflow = false;
3245 type = TREE_TYPE (op);
3246 if (!POINTER_TYPE_P (type)
3247 && !INTEGRAL_TYPE_P (type))
3248 return false;
3250 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3251 &folded_casts);
3252 if (chrec_contains_undetermined (ev)
3253 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3254 return false;
3256 if (tree_does_not_contain_chrecs (ev))
3258 iv->base = ev;
3259 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3260 iv->no_overflow = true;
3261 return true;
3264 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3265 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3266 return false;
3268 iv->step = CHREC_RIGHT (ev);
3269 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3270 || tree_contains_chrecs (iv->step, NULL))
3271 return false;
3273 iv->base = CHREC_LEFT (ev);
3274 if (tree_contains_chrecs (iv->base, NULL))
3275 return false;
3277 iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
3278 && TYPE_OVERFLOW_UNDEFINED (type));
3280 return true;
3283 /* Finalize the scalar evolution analysis. */
3285 void
3286 scev_finalize (void)
3288 if (!scalar_evolution_info)
3289 return;
3290 scalar_evolution_info->empty ();
3291 scalar_evolution_info = NULL;
3294 /* Returns true if the expression EXPR is considered to be too expensive
3295 for scev_const_prop. */
3297 bool
3298 expression_expensive_p (tree expr)
3300 enum tree_code code;
3302 if (is_gimple_val (expr))
3303 return false;
3305 code = TREE_CODE (expr);
3306 if (code == TRUNC_DIV_EXPR
3307 || code == CEIL_DIV_EXPR
3308 || code == FLOOR_DIV_EXPR
3309 || code == ROUND_DIV_EXPR
3310 || code == TRUNC_MOD_EXPR
3311 || code == CEIL_MOD_EXPR
3312 || code == FLOOR_MOD_EXPR
3313 || code == ROUND_MOD_EXPR
3314 || code == EXACT_DIV_EXPR)
3316 /* Division by power of two is usually cheap, so we allow it.
3317 Forbid anything else. */
3318 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3319 return true;
3322 switch (TREE_CODE_CLASS (code))
3324 case tcc_binary:
3325 case tcc_comparison:
3326 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3327 return true;
3329 /* Fallthru. */
3330 case tcc_unary:
3331 return expression_expensive_p (TREE_OPERAND (expr, 0));
3333 default:
3334 return true;
3338 /* Replace ssa names for that scev can prove they are constant by the
3339 appropriate constants. Also perform final value replacement in loops,
3340 in case the replacement expressions are cheap.
3342 We only consider SSA names defined by phi nodes; rest is left to the
3343 ordinary constant propagation pass. */
3345 unsigned int
3346 scev_const_prop (void)
3348 basic_block bb;
3349 tree name, type, ev;
3350 gphi *phi;
3351 gassign *ass;
3352 struct loop *loop, *ex_loop;
3353 bitmap ssa_names_to_remove = NULL;
3354 unsigned i;
3355 gphi_iterator psi;
3357 if (number_of_loops (cfun) <= 1)
3358 return 0;
3360 FOR_EACH_BB_FN (bb, cfun)
3362 loop = bb->loop_father;
3364 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3366 phi = psi.phi ();
3367 name = PHI_RESULT (phi);
3369 if (virtual_operand_p (name))
3370 continue;
3372 type = TREE_TYPE (name);
3374 if (!POINTER_TYPE_P (type)
3375 && !INTEGRAL_TYPE_P (type))
3376 continue;
3378 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3379 if (!is_gimple_min_invariant (ev)
3380 || !may_propagate_copy (name, ev))
3381 continue;
3383 /* Replace the uses of the name. */
3384 if (name != ev)
3385 replace_uses_by (name, ev);
3387 if (!ssa_names_to_remove)
3388 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3389 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3393 /* Remove the ssa names that were replaced by constants. We do not
3394 remove them directly in the previous cycle, since this
3395 invalidates scev cache. */
3396 if (ssa_names_to_remove)
3398 bitmap_iterator bi;
3400 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3402 gimple_stmt_iterator psi;
3403 name = ssa_name (i);
3404 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3406 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3407 psi = gsi_for_stmt (phi);
3408 remove_phi_node (&psi, true);
3411 BITMAP_FREE (ssa_names_to_remove);
3412 scev_reset ();
3415 /* Now the regular final value replacement. */
3416 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3418 edge exit;
3419 tree def, rslt, niter;
3420 gimple_stmt_iterator gsi;
3422 /* If we do not know exact number of iterations of the loop, we cannot
3423 replace the final value. */
3424 exit = single_exit (loop);
3425 if (!exit)
3426 continue;
3428 niter = number_of_latch_executions (loop);
3429 if (niter == chrec_dont_know)
3430 continue;
3432 /* Ensure that it is possible to insert new statements somewhere. */
3433 if (!single_pred_p (exit->dest))
3434 split_loop_exit_edge (exit);
3435 gsi = gsi_after_labels (exit->dest);
3437 ex_loop = superloop_at_depth (loop,
3438 loop_depth (exit->dest->loop_father) + 1);
3440 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3442 phi = psi.phi ();
3443 rslt = PHI_RESULT (phi);
3444 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3445 if (virtual_operand_p (def))
3447 gsi_next (&psi);
3448 continue;
3451 if (!POINTER_TYPE_P (TREE_TYPE (def))
3452 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3454 gsi_next (&psi);
3455 continue;
3458 bool folded_casts;
3459 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3460 &folded_casts);
3461 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3462 if (!tree_does_not_contain_chrecs (def)
3463 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3464 /* Moving the computation from the loop may prolong life range
3465 of some ssa names, which may cause problems if they appear
3466 on abnormal edges. */
3467 || contains_abnormal_ssa_name_p (def)
3468 /* Do not emit expensive expressions. The rationale is that
3469 when someone writes a code like
3471 while (n > 45) n -= 45;
3473 he probably knows that n is not large, and does not want it
3474 to be turned into n %= 45. */
3475 || expression_expensive_p (def))
3477 if (dump_file && (dump_flags & TDF_DETAILS))
3479 fprintf (dump_file, "not replacing:\n ");
3480 print_gimple_stmt (dump_file, phi, 0, 0);
3481 fprintf (dump_file, "\n");
3483 gsi_next (&psi);
3484 continue;
3487 /* Eliminate the PHI node and replace it by a computation outside
3488 the loop. */
3489 if (dump_file)
3491 fprintf (dump_file, "\nfinal value replacement:\n ");
3492 print_gimple_stmt (dump_file, phi, 0, 0);
3493 fprintf (dump_file, " with\n ");
3495 def = unshare_expr (def);
3496 remove_phi_node (&psi, false);
3498 /* If def's type has undefined overflow and there were folded
3499 casts, rewrite all stmts added for def into arithmetics
3500 with defined overflow behavior. */
3501 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3502 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3504 gimple_seq stmts;
3505 gimple_stmt_iterator gsi2;
3506 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3507 gsi2 = gsi_start (stmts);
3508 while (!gsi_end_p (gsi2))
3510 gimple stmt = gsi_stmt (gsi2);
3511 gimple_stmt_iterator gsi3 = gsi2;
3512 gsi_next (&gsi2);
3513 gsi_remove (&gsi3, false);
3514 if (is_gimple_assign (stmt)
3515 && arith_code_with_undefined_signed_overflow
3516 (gimple_assign_rhs_code (stmt)))
3517 gsi_insert_seq_before (&gsi,
3518 rewrite_to_defined_overflow (stmt),
3519 GSI_SAME_STMT);
3520 else
3521 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3524 else
3525 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3526 true, GSI_SAME_STMT);
3528 ass = gimple_build_assign (rslt, def);
3529 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3530 if (dump_file)
3532 print_gimple_stmt (dump_file, ass, 0, 0);
3533 fprintf (dump_file, "\n");
3537 return 0;
3540 #include "gt-tree-scalar-evolution.h"