2015-06-24 François Dumont <fdumont@gcc.gnu.org>
[official-gcc.git] / gcc / tree-scalar-evolution.c
blob1abefea69b463c79638438dd8e72e52bb10d45e5
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 "alias.h"
260 #include "symtab.h"
261 #include "options.h"
262 #include "tree.h"
263 #include "fold-const.h"
264 #include "tm.h"
265 #include "hard-reg-set.h"
266 #include "function.h"
267 #include "rtl.h"
268 #include "flags.h"
269 #include "insn-config.h"
270 #include "expmed.h"
271 #include "dojump.h"
272 #include "explow.h"
273 #include "calls.h"
274 #include "emit-rtl.h"
275 #include "varasm.h"
276 #include "stmt.h"
277 #include "expr.h"
278 #include "gimple-pretty-print.h"
279 #include "predict.h"
280 #include "dominance.h"
281 #include "cfg.h"
282 #include "basic-block.h"
283 #include "tree-ssa-alias.h"
284 #include "internal-fn.h"
285 #include "gimple-expr.h"
286 #include "gimple.h"
287 #include "gimplify.h"
288 #include "gimple-iterator.h"
289 #include "gimplify-me.h"
290 #include "gimple-ssa.h"
291 #include "tree-cfg.h"
292 #include "tree-phinodes.h"
293 #include "stringpool.h"
294 #include "tree-ssanames.h"
295 #include "tree-ssa-loop-ivopts.h"
296 #include "tree-ssa-loop-manip.h"
297 #include "tree-ssa-loop-niter.h"
298 #include "tree-ssa-loop.h"
299 #include "tree-ssa.h"
300 #include "cfgloop.h"
301 #include "tree-chrec.h"
302 #include "tree-affine.h"
303 #include "tree-scalar-evolution.h"
304 #include "dumpfile.h"
305 #include "params.h"
306 #include "tree-ssa-propagate.h"
307 #include "gimple-fold.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 evol = add_to_evolution
950 (loop->num,
951 chrec_convert (type, evol, at_stmt),
952 code, rhs1, at_stmt);
953 res = follow_ssa_edge
954 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
955 if (res == t_true)
956 *evolution_of_loop = evol;
957 else if (res == t_false)
959 *evolution_of_loop = add_to_evolution
960 (loop->num,
961 chrec_convert (type, *evolution_of_loop, at_stmt),
962 code, rhs0, at_stmt);
963 res = follow_ssa_edge
964 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
965 evolution_of_loop, limit);
966 if (res == t_true)
968 else if (res == t_dont_know)
969 *evolution_of_loop = chrec_dont_know;
972 else if (res == t_dont_know)
973 *evolution_of_loop = chrec_dont_know;
976 else
978 /* Match an assignment under the form:
979 "a = b + ...". */
980 *evolution_of_loop = add_to_evolution
981 (loop->num, chrec_convert (type, *evolution_of_loop,
982 at_stmt),
983 code, rhs1, at_stmt);
984 res = follow_ssa_edge
985 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
986 evolution_of_loop, limit);
987 if (res == t_true)
989 else if (res == t_dont_know)
990 *evolution_of_loop = chrec_dont_know;
994 else if (TREE_CODE (rhs1) == SSA_NAME)
996 /* Match an assignment under the form:
997 "a = ... + c". */
998 *evolution_of_loop = add_to_evolution
999 (loop->num, chrec_convert (type, *evolution_of_loop,
1000 at_stmt),
1001 code, rhs0, at_stmt);
1002 res = follow_ssa_edge
1003 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1004 evolution_of_loop, limit);
1005 if (res == t_true)
1007 else if (res == t_dont_know)
1008 *evolution_of_loop = chrec_dont_know;
1011 else
1012 /* Otherwise, match an assignment under the form:
1013 "a = ... + ...". */
1014 /* And there is nothing to do. */
1015 res = t_false;
1016 break;
1018 case MINUS_EXPR:
1019 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1020 if (TREE_CODE (rhs0) == SSA_NAME)
1022 /* Match an assignment under the form:
1023 "a = b - ...". */
1025 /* We want only assignments of form "name - name" contribute to
1026 LIMIT, as the other cases do not necessarily contribute to
1027 the complexity of the expression. */
1028 if (TREE_CODE (rhs1) == SSA_NAME)
1029 limit++;
1031 *evolution_of_loop = add_to_evolution
1032 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1033 MINUS_EXPR, rhs1, at_stmt);
1034 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1035 evolution_of_loop, limit);
1036 if (res == t_true)
1038 else if (res == t_dont_know)
1039 *evolution_of_loop = chrec_dont_know;
1041 else
1042 /* Otherwise, match an assignment under the form:
1043 "a = ... - ...". */
1044 /* And there is nothing to do. */
1045 res = t_false;
1046 break;
1048 default:
1049 res = t_false;
1052 return res;
1055 /* Follow the ssa edge into the expression EXPR.
1056 Return true if the strongly connected component has been found. */
1058 static t_bool
1059 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1060 gphi *halting_phi, tree *evolution_of_loop,
1061 int limit)
1063 enum tree_code code = TREE_CODE (expr);
1064 tree type = TREE_TYPE (expr), rhs0, rhs1;
1065 t_bool res;
1067 /* The EXPR is one of the following cases:
1068 - an SSA_NAME,
1069 - an INTEGER_CST,
1070 - a PLUS_EXPR,
1071 - a POINTER_PLUS_EXPR,
1072 - a MINUS_EXPR,
1073 - an ASSERT_EXPR,
1074 - other cases are not yet handled. */
1076 switch (code)
1078 CASE_CONVERT:
1079 /* This assignment is under the form "a_1 = (cast) rhs. */
1080 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1081 halting_phi, evolution_of_loop, limit);
1082 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1083 break;
1085 case INTEGER_CST:
1086 /* This assignment is under the form "a_1 = 7". */
1087 res = t_false;
1088 break;
1090 case SSA_NAME:
1091 /* This assignment is under the form: "a_1 = b_2". */
1092 res = follow_ssa_edge
1093 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1094 break;
1096 case POINTER_PLUS_EXPR:
1097 case PLUS_EXPR:
1098 case MINUS_EXPR:
1099 /* This case is under the form "rhs0 +- rhs1". */
1100 rhs0 = TREE_OPERAND (expr, 0);
1101 rhs1 = TREE_OPERAND (expr, 1);
1102 type = TREE_TYPE (rhs0);
1103 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1104 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1105 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1106 halting_phi, evolution_of_loop, limit);
1107 break;
1109 case ADDR_EXPR:
1110 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1111 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1113 expr = TREE_OPERAND (expr, 0);
1114 rhs0 = TREE_OPERAND (expr, 0);
1115 rhs1 = TREE_OPERAND (expr, 1);
1116 type = TREE_TYPE (rhs0);
1117 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1118 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1119 res = follow_ssa_edge_binary (loop, at_stmt, type,
1120 rhs0, POINTER_PLUS_EXPR, rhs1,
1121 halting_phi, evolution_of_loop, limit);
1123 else
1124 res = t_false;
1125 break;
1127 case ASSERT_EXPR:
1128 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1129 It must be handled as a copy assignment of the form a_1 = a_2. */
1130 rhs0 = ASSERT_EXPR_VAR (expr);
1131 if (TREE_CODE (rhs0) == SSA_NAME)
1132 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1133 halting_phi, evolution_of_loop, limit);
1134 else
1135 res = t_false;
1136 break;
1138 default:
1139 res = t_false;
1140 break;
1143 return res;
1146 /* Follow the ssa edge into the right hand side of an assignment STMT.
1147 Return true if the strongly connected component has been found. */
1149 static t_bool
1150 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1151 gphi *halting_phi, tree *evolution_of_loop,
1152 int limit)
1154 enum tree_code code = gimple_assign_rhs_code (stmt);
1155 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1156 t_bool res;
1158 switch (code)
1160 CASE_CONVERT:
1161 /* This assignment is under the form "a_1 = (cast) rhs. */
1162 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1163 halting_phi, evolution_of_loop, limit);
1164 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1165 break;
1167 case POINTER_PLUS_EXPR:
1168 case PLUS_EXPR:
1169 case MINUS_EXPR:
1170 rhs1 = gimple_assign_rhs1 (stmt);
1171 rhs2 = gimple_assign_rhs2 (stmt);
1172 type = TREE_TYPE (rhs1);
1173 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1174 halting_phi, evolution_of_loop, limit);
1175 break;
1177 default:
1178 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1179 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1180 halting_phi, evolution_of_loop, limit);
1181 else
1182 res = t_false;
1183 break;
1186 return res;
1189 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1191 static bool
1192 backedge_phi_arg_p (gphi *phi, int i)
1194 const_edge e = gimple_phi_arg_edge (phi, i);
1196 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1197 about updating it anywhere, and this should work as well most of the
1198 time. */
1199 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1200 return true;
1202 return false;
1205 /* Helper function for one branch of the condition-phi-node. Return
1206 true if the strongly connected component has been found following
1207 this path. */
1209 static inline t_bool
1210 follow_ssa_edge_in_condition_phi_branch (int i,
1211 struct loop *loop,
1212 gphi *condition_phi,
1213 gphi *halting_phi,
1214 tree *evolution_of_branch,
1215 tree init_cond, int limit)
1217 tree branch = PHI_ARG_DEF (condition_phi, i);
1218 *evolution_of_branch = chrec_dont_know;
1220 /* Do not follow back edges (they must belong to an irreducible loop, which
1221 we really do not want to worry about). */
1222 if (backedge_phi_arg_p (condition_phi, i))
1223 return t_false;
1225 if (TREE_CODE (branch) == SSA_NAME)
1227 *evolution_of_branch = init_cond;
1228 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1229 evolution_of_branch, limit);
1232 /* This case occurs when one of the condition branches sets
1233 the variable to a constant: i.e. a phi-node like
1234 "a_2 = PHI <a_7(5), 2(6)>;".
1236 FIXME: This case have to be refined correctly:
1237 in some cases it is possible to say something better than
1238 chrec_dont_know, for example using a wrap-around notation. */
1239 return t_false;
1242 /* This function merges the branches of a condition-phi-node in a
1243 loop. */
1245 static t_bool
1246 follow_ssa_edge_in_condition_phi (struct loop *loop,
1247 gphi *condition_phi,
1248 gphi *halting_phi,
1249 tree *evolution_of_loop, int limit)
1251 int i, n;
1252 tree init = *evolution_of_loop;
1253 tree evolution_of_branch;
1254 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1255 halting_phi,
1256 &evolution_of_branch,
1257 init, limit);
1258 if (res == t_false || res == t_dont_know)
1259 return res;
1261 *evolution_of_loop = evolution_of_branch;
1263 n = gimple_phi_num_args (condition_phi);
1264 for (i = 1; i < n; i++)
1266 /* Quickly give up when the evolution of one of the branches is
1267 not known. */
1268 if (*evolution_of_loop == chrec_dont_know)
1269 return t_true;
1271 /* Increase the limit by the PHI argument number to avoid exponential
1272 time and memory complexity. */
1273 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1274 halting_phi,
1275 &evolution_of_branch,
1276 init, limit + i);
1277 if (res == t_false || res == t_dont_know)
1278 return res;
1280 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1281 evolution_of_branch);
1284 return t_true;
1287 /* Follow an SSA edge in an inner loop. It computes the overall
1288 effect of the loop, and following the symbolic initial conditions,
1289 it follows the edges in the parent loop. The inner loop is
1290 considered as a single statement. */
1292 static t_bool
1293 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1294 gphi *loop_phi_node,
1295 gphi *halting_phi,
1296 tree *evolution_of_loop, int limit)
1298 struct loop *loop = loop_containing_stmt (loop_phi_node);
1299 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1301 /* Sometimes, the inner loop is too difficult to analyze, and the
1302 result of the analysis is a symbolic parameter. */
1303 if (ev == PHI_RESULT (loop_phi_node))
1305 t_bool res = t_false;
1306 int i, n = gimple_phi_num_args (loop_phi_node);
1308 for (i = 0; i < n; i++)
1310 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1311 basic_block bb;
1313 /* Follow the edges that exit the inner loop. */
1314 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1315 if (!flow_bb_inside_loop_p (loop, bb))
1316 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1317 arg, halting_phi,
1318 evolution_of_loop, limit);
1319 if (res == t_true)
1320 break;
1323 /* If the path crosses this loop-phi, give up. */
1324 if (res == t_true)
1325 *evolution_of_loop = chrec_dont_know;
1327 return res;
1330 /* Otherwise, compute the overall effect of the inner loop. */
1331 ev = compute_overall_effect_of_inner_loop (loop, ev);
1332 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1333 evolution_of_loop, limit);
1336 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1337 path that is analyzed on the return walk. */
1339 static t_bool
1340 follow_ssa_edge (struct loop *loop, gimple def, gphi *halting_phi,
1341 tree *evolution_of_loop, int limit)
1343 struct loop *def_loop;
1345 if (gimple_nop_p (def))
1346 return t_false;
1348 /* Give up if the path is longer than the MAX that we allow. */
1349 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1350 return t_dont_know;
1352 def_loop = loop_containing_stmt (def);
1354 switch (gimple_code (def))
1356 case GIMPLE_PHI:
1357 if (!loop_phi_node_p (def))
1358 /* DEF is a condition-phi-node. Follow the branches, and
1359 record their evolutions. Finally, merge the collected
1360 information and set the approximation to the main
1361 variable. */
1362 return follow_ssa_edge_in_condition_phi
1363 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1364 limit);
1366 /* When the analyzed phi is the halting_phi, the
1367 depth-first search is over: we have found a path from
1368 the halting_phi to itself in the loop. */
1369 if (def == halting_phi)
1370 return t_true;
1372 /* Otherwise, the evolution of the HALTING_PHI depends
1373 on the evolution of another loop-phi-node, i.e. the
1374 evolution function is a higher degree polynomial. */
1375 if (def_loop == loop)
1376 return t_false;
1378 /* Inner loop. */
1379 if (flow_loop_nested_p (loop, def_loop))
1380 return follow_ssa_edge_inner_loop_phi
1381 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1382 limit + 1);
1384 /* Outer loop. */
1385 return t_false;
1387 case GIMPLE_ASSIGN:
1388 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1389 evolution_of_loop, limit);
1391 default:
1392 /* At this level of abstraction, the program is just a set
1393 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1394 other node to be handled. */
1395 return t_false;
1400 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1401 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1403 # i_17 = PHI <i_13(5), 0(3)>
1404 # _20 = PHI <_5(5), start_4(D)(3)>
1406 i_13 = i_17 + 1;
1407 _5 = start_4(D) + i_13;
1409 Though variable _20 appears as a PEELED_CHREC in the form of
1410 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1412 See PR41488. */
1414 static tree
1415 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1417 aff_tree aff1, aff2;
1418 tree ev, left, right, type, step_val;
1419 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1421 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1422 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1423 return chrec_dont_know;
1425 left = CHREC_LEFT (ev);
1426 right = CHREC_RIGHT (ev);
1427 type = TREE_TYPE (left);
1428 step_val = chrec_fold_plus (type, init_cond, right);
1430 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1431 if "left" equals to "init + right". */
1432 if (operand_equal_p (left, step_val, 0))
1434 if (dump_file && (dump_flags & TDF_SCEV))
1435 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1437 return build_polynomial_chrec (loop->num, init_cond, right);
1440 /* Try harder to check if they are equal. */
1441 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1442 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1443 free_affine_expand_cache (&peeled_chrec_map);
1444 aff_combination_scale (&aff2, -1);
1445 aff_combination_add (&aff1, &aff2);
1447 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1448 if "left" equals to "init + right". */
1449 if (aff_combination_zero_p (&aff1))
1451 if (dump_file && (dump_flags & TDF_SCEV))
1452 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1454 return build_polynomial_chrec (loop->num, init_cond, right);
1456 return chrec_dont_know;
1459 /* Given a LOOP_PHI_NODE, this function determines the evolution
1460 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1462 static tree
1463 analyze_evolution_in_loop (gphi *loop_phi_node,
1464 tree init_cond)
1466 int i, n = gimple_phi_num_args (loop_phi_node);
1467 tree evolution_function = chrec_not_analyzed_yet;
1468 struct loop *loop = loop_containing_stmt (loop_phi_node);
1469 basic_block bb;
1470 static bool simplify_peeled_chrec_p = true;
1472 if (dump_file && (dump_flags & TDF_SCEV))
1474 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1475 fprintf (dump_file, " (loop_phi_node = ");
1476 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1477 fprintf (dump_file, ")\n");
1480 for (i = 0; i < n; i++)
1482 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1483 gimple ssa_chain;
1484 tree ev_fn;
1485 t_bool res;
1487 /* Select the edges that enter the loop body. */
1488 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1489 if (!flow_bb_inside_loop_p (loop, bb))
1490 continue;
1492 if (TREE_CODE (arg) == SSA_NAME)
1494 bool val = false;
1496 ssa_chain = SSA_NAME_DEF_STMT (arg);
1498 /* Pass in the initial condition to the follow edge function. */
1499 ev_fn = init_cond;
1500 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1502 /* If ev_fn has no evolution in the inner loop, and the
1503 init_cond is not equal to ev_fn, then we have an
1504 ambiguity between two possible values, as we cannot know
1505 the number of iterations at this point. */
1506 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1507 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1508 && !operand_equal_p (init_cond, ev_fn, 0))
1509 ev_fn = chrec_dont_know;
1511 else
1512 res = t_false;
1514 /* When it is impossible to go back on the same
1515 loop_phi_node by following the ssa edges, the
1516 evolution is represented by a peeled chrec, i.e. the
1517 first iteration, EV_FN has the value INIT_COND, then
1518 all the other iterations it has the value of ARG.
1519 For the moment, PEELED_CHREC nodes are not built. */
1520 if (res != t_true)
1522 ev_fn = chrec_dont_know;
1523 /* Try to recognize POLYNOMIAL_CHREC which appears in
1524 the form of PEELED_CHREC, but guard the process with
1525 a bool variable to keep the analyzer from infinite
1526 recurrence for real PEELED_RECs. */
1527 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1529 simplify_peeled_chrec_p = false;
1530 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1531 simplify_peeled_chrec_p = true;
1535 /* When there are multiple back edges of the loop (which in fact never
1536 happens currently, but nevertheless), merge their evolutions. */
1537 evolution_function = chrec_merge (evolution_function, ev_fn);
1540 if (dump_file && (dump_flags & TDF_SCEV))
1542 fprintf (dump_file, " (evolution_function = ");
1543 print_generic_expr (dump_file, evolution_function, 0);
1544 fprintf (dump_file, "))\n");
1547 return evolution_function;
1550 /* Given a loop-phi-node, return the initial conditions of the
1551 variable on entry of the loop. When the CCP has propagated
1552 constants into the loop-phi-node, the initial condition is
1553 instantiated, otherwise the initial condition is kept symbolic.
1554 This analyzer does not analyze the evolution outside the current
1555 loop, and leaves this task to the on-demand tree reconstructor. */
1557 static tree
1558 analyze_initial_condition (gphi *loop_phi_node)
1560 int i, n;
1561 tree init_cond = chrec_not_analyzed_yet;
1562 struct loop *loop = loop_containing_stmt (loop_phi_node);
1564 if (dump_file && (dump_flags & TDF_SCEV))
1566 fprintf (dump_file, "(analyze_initial_condition \n");
1567 fprintf (dump_file, " (loop_phi_node = \n");
1568 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1569 fprintf (dump_file, ")\n");
1572 n = gimple_phi_num_args (loop_phi_node);
1573 for (i = 0; i < n; i++)
1575 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1576 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1578 /* When the branch is oriented to the loop's body, it does
1579 not contribute to the initial condition. */
1580 if (flow_bb_inside_loop_p (loop, bb))
1581 continue;
1583 if (init_cond == chrec_not_analyzed_yet)
1585 init_cond = branch;
1586 continue;
1589 if (TREE_CODE (branch) == SSA_NAME)
1591 init_cond = chrec_dont_know;
1592 break;
1595 init_cond = chrec_merge (init_cond, branch);
1598 /* Ooops -- a loop without an entry??? */
1599 if (init_cond == chrec_not_analyzed_yet)
1600 init_cond = chrec_dont_know;
1602 /* During early loop unrolling we do not have fully constant propagated IL.
1603 Handle degenerate PHIs here to not miss important unrollings. */
1604 if (TREE_CODE (init_cond) == SSA_NAME)
1606 gimple def = SSA_NAME_DEF_STMT (init_cond);
1607 if (gphi *phi = dyn_cast <gphi *> (def))
1609 tree res = degenerate_phi_result (phi);
1610 if (res != NULL_TREE
1611 /* Only allow invariants here, otherwise we may break
1612 loop-closed SSA form. */
1613 && is_gimple_min_invariant (res))
1614 init_cond = res;
1618 if (dump_file && (dump_flags & TDF_SCEV))
1620 fprintf (dump_file, " (init_cond = ");
1621 print_generic_expr (dump_file, init_cond, 0);
1622 fprintf (dump_file, "))\n");
1625 return init_cond;
1628 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1630 static tree
1631 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1633 tree res;
1634 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1635 tree init_cond;
1637 if (phi_loop != loop)
1639 struct loop *subloop;
1640 tree evolution_fn = analyze_scalar_evolution
1641 (phi_loop, PHI_RESULT (loop_phi_node));
1643 /* Dive one level deeper. */
1644 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1646 /* Interpret the subloop. */
1647 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1648 return res;
1651 /* Otherwise really interpret the loop phi. */
1652 init_cond = analyze_initial_condition (loop_phi_node);
1653 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1655 /* Verify we maintained the correct initial condition throughout
1656 possible conversions in the SSA chain. */
1657 if (res != chrec_dont_know)
1659 tree new_init = res;
1660 if (CONVERT_EXPR_P (res)
1661 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1662 new_init = fold_convert (TREE_TYPE (res),
1663 CHREC_LEFT (TREE_OPERAND (res, 0)));
1664 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1665 new_init = CHREC_LEFT (res);
1666 STRIP_USELESS_TYPE_CONVERSION (new_init);
1667 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1668 || !operand_equal_p (init_cond, new_init, 0))
1669 return chrec_dont_know;
1672 return res;
1675 /* This function merges the branches of a condition-phi-node,
1676 contained in the outermost loop, and whose arguments are already
1677 analyzed. */
1679 static tree
1680 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1682 int i, n = gimple_phi_num_args (condition_phi);
1683 tree res = chrec_not_analyzed_yet;
1685 for (i = 0; i < n; i++)
1687 tree branch_chrec;
1689 if (backedge_phi_arg_p (condition_phi, i))
1691 res = chrec_dont_know;
1692 break;
1695 branch_chrec = analyze_scalar_evolution
1696 (loop, PHI_ARG_DEF (condition_phi, i));
1698 res = chrec_merge (res, branch_chrec);
1701 return res;
1704 /* Interpret the operation RHS1 OP RHS2. If we didn't
1705 analyze this node before, follow the definitions until ending
1706 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1707 return path, this function propagates evolutions (ala constant copy
1708 propagation). OPND1 is not a GIMPLE expression because we could
1709 analyze the effect of an inner loop: see interpret_loop_phi. */
1711 static tree
1712 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1713 tree type, tree rhs1, enum tree_code code, tree rhs2)
1715 tree res, chrec1, chrec2;
1716 gimple def;
1718 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1720 if (is_gimple_min_invariant (rhs1))
1721 return chrec_convert (type, rhs1, at_stmt);
1723 if (code == SSA_NAME)
1724 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1725 at_stmt);
1727 if (code == ASSERT_EXPR)
1729 rhs1 = ASSERT_EXPR_VAR (rhs1);
1730 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1731 at_stmt);
1735 switch (code)
1737 case ADDR_EXPR:
1738 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1739 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1741 machine_mode mode;
1742 HOST_WIDE_INT bitsize, bitpos;
1743 int unsignedp;
1744 int volatilep = 0;
1745 tree base, offset;
1746 tree chrec3;
1747 tree unitpos;
1749 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1750 &bitsize, &bitpos, &offset,
1751 &mode, &unsignedp, &volatilep, false);
1753 if (TREE_CODE (base) == MEM_REF)
1755 rhs2 = TREE_OPERAND (base, 1);
1756 rhs1 = TREE_OPERAND (base, 0);
1758 chrec1 = analyze_scalar_evolution (loop, rhs1);
1759 chrec2 = analyze_scalar_evolution (loop, rhs2);
1760 chrec1 = chrec_convert (type, chrec1, at_stmt);
1761 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1762 chrec1 = instantiate_parameters (loop, chrec1);
1763 chrec2 = instantiate_parameters (loop, chrec2);
1764 res = chrec_fold_plus (type, chrec1, chrec2);
1766 else
1768 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1769 chrec1 = chrec_convert (type, chrec1, at_stmt);
1770 res = chrec1;
1773 if (offset != NULL_TREE)
1775 chrec2 = analyze_scalar_evolution (loop, offset);
1776 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1777 chrec2 = instantiate_parameters (loop, chrec2);
1778 res = chrec_fold_plus (type, res, chrec2);
1781 if (bitpos != 0)
1783 gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
1785 unitpos = size_int (bitpos / BITS_PER_UNIT);
1786 chrec3 = analyze_scalar_evolution (loop, unitpos);
1787 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1788 chrec3 = instantiate_parameters (loop, chrec3);
1789 res = chrec_fold_plus (type, res, chrec3);
1792 else
1793 res = chrec_dont_know;
1794 break;
1796 case POINTER_PLUS_EXPR:
1797 chrec1 = analyze_scalar_evolution (loop, rhs1);
1798 chrec2 = analyze_scalar_evolution (loop, rhs2);
1799 chrec1 = chrec_convert (type, chrec1, at_stmt);
1800 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1801 chrec1 = instantiate_parameters (loop, chrec1);
1802 chrec2 = instantiate_parameters (loop, chrec2);
1803 res = chrec_fold_plus (type, chrec1, chrec2);
1804 break;
1806 case PLUS_EXPR:
1807 chrec1 = analyze_scalar_evolution (loop, rhs1);
1808 chrec2 = analyze_scalar_evolution (loop, rhs2);
1809 chrec1 = chrec_convert (type, chrec1, at_stmt);
1810 chrec2 = chrec_convert (type, chrec2, at_stmt);
1811 chrec1 = instantiate_parameters (loop, chrec1);
1812 chrec2 = instantiate_parameters (loop, chrec2);
1813 res = chrec_fold_plus (type, chrec1, chrec2);
1814 break;
1816 case MINUS_EXPR:
1817 chrec1 = analyze_scalar_evolution (loop, rhs1);
1818 chrec2 = analyze_scalar_evolution (loop, rhs2);
1819 chrec1 = chrec_convert (type, chrec1, at_stmt);
1820 chrec2 = chrec_convert (type, chrec2, at_stmt);
1821 chrec1 = instantiate_parameters (loop, chrec1);
1822 chrec2 = instantiate_parameters (loop, chrec2);
1823 res = chrec_fold_minus (type, chrec1, chrec2);
1824 break;
1826 case NEGATE_EXPR:
1827 chrec1 = analyze_scalar_evolution (loop, rhs1);
1828 chrec1 = chrec_convert (type, chrec1, at_stmt);
1829 /* TYPE may be integer, real or complex, so use fold_convert. */
1830 chrec1 = instantiate_parameters (loop, chrec1);
1831 res = chrec_fold_multiply (type, chrec1,
1832 fold_convert (type, integer_minus_one_node));
1833 break;
1835 case BIT_NOT_EXPR:
1836 /* Handle ~X as -1 - X. */
1837 chrec1 = analyze_scalar_evolution (loop, rhs1);
1838 chrec1 = chrec_convert (type, chrec1, at_stmt);
1839 chrec1 = instantiate_parameters (loop, chrec1);
1840 res = chrec_fold_minus (type,
1841 fold_convert (type, integer_minus_one_node),
1842 chrec1);
1843 break;
1845 case MULT_EXPR:
1846 chrec1 = analyze_scalar_evolution (loop, rhs1);
1847 chrec2 = analyze_scalar_evolution (loop, rhs2);
1848 chrec1 = chrec_convert (type, chrec1, at_stmt);
1849 chrec2 = chrec_convert (type, chrec2, at_stmt);
1850 chrec1 = instantiate_parameters (loop, chrec1);
1851 chrec2 = instantiate_parameters (loop, chrec2);
1852 res = chrec_fold_multiply (type, chrec1, chrec2);
1853 break;
1855 CASE_CONVERT:
1856 /* In case we have a truncation of a widened operation that in
1857 the truncated type has undefined overflow behavior analyze
1858 the operation done in an unsigned type of the same precision
1859 as the final truncation. We cannot derive a scalar evolution
1860 for the widened operation but for the truncated result. */
1861 if (TREE_CODE (type) == INTEGER_TYPE
1862 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1863 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1864 && TYPE_OVERFLOW_UNDEFINED (type)
1865 && TREE_CODE (rhs1) == SSA_NAME
1866 && (def = SSA_NAME_DEF_STMT (rhs1))
1867 && is_gimple_assign (def)
1868 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1869 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1871 tree utype = unsigned_type_for (type);
1872 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1873 gimple_assign_rhs1 (def),
1874 gimple_assign_rhs_code (def),
1875 gimple_assign_rhs2 (def));
1877 else
1878 chrec1 = analyze_scalar_evolution (loop, rhs1);
1879 res = chrec_convert (type, chrec1, at_stmt);
1880 break;
1882 default:
1883 res = chrec_dont_know;
1884 break;
1887 return res;
1890 /* Interpret the expression EXPR. */
1892 static tree
1893 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1895 enum tree_code code;
1896 tree type = TREE_TYPE (expr), op0, op1;
1898 if (automatically_generated_chrec_p (expr))
1899 return expr;
1901 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1902 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1903 return chrec_dont_know;
1905 extract_ops_from_tree (expr, &code, &op0, &op1);
1907 return interpret_rhs_expr (loop, at_stmt, type,
1908 op0, code, op1);
1911 /* Interpret the rhs of the assignment STMT. */
1913 static tree
1914 interpret_gimple_assign (struct loop *loop, gimple stmt)
1916 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1917 enum tree_code code = gimple_assign_rhs_code (stmt);
1919 return interpret_rhs_expr (loop, stmt, type,
1920 gimple_assign_rhs1 (stmt), code,
1921 gimple_assign_rhs2 (stmt));
1926 /* This section contains all the entry points:
1927 - number_of_iterations_in_loop,
1928 - analyze_scalar_evolution,
1929 - instantiate_parameters.
1932 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1933 common ancestor of DEF_LOOP and USE_LOOP. */
1935 static tree
1936 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1937 struct loop *def_loop,
1938 tree ev)
1940 bool val;
1941 tree res;
1943 if (def_loop == wrto_loop)
1944 return ev;
1946 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1947 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1949 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
1950 return res;
1952 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1955 /* Helper recursive function. */
1957 static tree
1958 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1960 tree type = TREE_TYPE (var);
1961 gimple def;
1962 basic_block bb;
1963 struct loop *def_loop;
1965 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1966 return chrec_dont_know;
1968 if (TREE_CODE (var) != SSA_NAME)
1969 return interpret_expr (loop, NULL, var);
1971 def = SSA_NAME_DEF_STMT (var);
1972 bb = gimple_bb (def);
1973 def_loop = bb ? bb->loop_father : NULL;
1975 if (bb == NULL
1976 || !flow_bb_inside_loop_p (loop, bb))
1978 /* Keep the symbolic form. */
1979 res = var;
1980 goto set_and_end;
1983 if (res != chrec_not_analyzed_yet)
1985 if (loop != bb->loop_father)
1986 res = compute_scalar_evolution_in_loop
1987 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1989 goto set_and_end;
1992 if (loop != def_loop)
1994 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1995 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1997 goto set_and_end;
2000 switch (gimple_code (def))
2002 case GIMPLE_ASSIGN:
2003 res = interpret_gimple_assign (loop, def);
2004 break;
2006 case GIMPLE_PHI:
2007 if (loop_phi_node_p (def))
2008 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2009 else
2010 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2011 break;
2013 default:
2014 res = chrec_dont_know;
2015 break;
2018 set_and_end:
2020 /* Keep the symbolic form. */
2021 if (res == chrec_dont_know)
2022 res = var;
2024 if (loop == def_loop)
2025 set_scalar_evolution (block_before_loop (loop), var, res);
2027 return res;
2030 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2031 LOOP. LOOP is the loop in which the variable is used.
2033 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2034 pointer to the statement that uses this variable, in order to
2035 determine the evolution function of the variable, use the following
2036 calls:
2038 loop_p loop = loop_containing_stmt (stmt);
2039 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2040 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2043 tree
2044 analyze_scalar_evolution (struct loop *loop, tree var)
2046 tree res;
2048 if (dump_file && (dump_flags & TDF_SCEV))
2050 fprintf (dump_file, "(analyze_scalar_evolution \n");
2051 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2052 fprintf (dump_file, " (scalar = ");
2053 print_generic_expr (dump_file, var, 0);
2054 fprintf (dump_file, ")\n");
2057 res = get_scalar_evolution (block_before_loop (loop), var);
2058 res = analyze_scalar_evolution_1 (loop, var, res);
2060 if (dump_file && (dump_flags & TDF_SCEV))
2061 fprintf (dump_file, ")\n");
2063 return res;
2066 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2068 static tree
2069 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2071 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2074 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2075 WRTO_LOOP (which should be a superloop of USE_LOOP)
2077 FOLDED_CASTS is set to true if resolve_mixers used
2078 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2079 at the moment in order to keep things simple).
2081 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2082 example:
2084 for (i = 0; i < 100; i++) -- loop 1
2086 for (j = 0; j < 100; j++) -- loop 2
2088 k1 = i;
2089 k2 = j;
2091 use2 (k1, k2);
2093 for (t = 0; t < 100; t++) -- loop 3
2094 use3 (k1, k2);
2097 use1 (k1, k2);
2100 Both k1 and k2 are invariants in loop3, thus
2101 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2102 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2104 As they are invariant, it does not matter whether we consider their
2105 usage in loop 3 or loop 2, hence
2106 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2107 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2108 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2109 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2111 Similarly for their evolutions with respect to loop 1. The values of K2
2112 in the use in loop 2 vary independently on loop 1, thus we cannot express
2113 the evolution with respect to loop 1:
2114 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2115 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2116 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2117 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2119 The value of k2 in the use in loop 1 is known, though:
2120 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2121 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2124 static tree
2125 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2126 tree version, bool *folded_casts)
2128 bool val = false;
2129 tree ev = version, tmp;
2131 /* We cannot just do
2133 tmp = analyze_scalar_evolution (use_loop, version);
2134 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2136 as resolve_mixers would query the scalar evolution with respect to
2137 wrto_loop. For example, in the situation described in the function
2138 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2139 version = k2. Then
2141 analyze_scalar_evolution (use_loop, version) = k2
2143 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2144 k2 in loop 1 is 100, which is a wrong result, since we are interested
2145 in the value in loop 3.
2147 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2148 each time checking that there is no evolution in the inner loop. */
2150 if (folded_casts)
2151 *folded_casts = false;
2152 while (1)
2154 tmp = analyze_scalar_evolution (use_loop, ev);
2155 ev = resolve_mixers (use_loop, tmp, folded_casts);
2157 if (use_loop == wrto_loop)
2158 return ev;
2160 /* If the value of the use changes in the inner loop, we cannot express
2161 its value in the outer loop (we might try to return interval chrec,
2162 but we do not have a user for it anyway) */
2163 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2164 || !val)
2165 return chrec_dont_know;
2167 use_loop = loop_outer (use_loop);
2172 /* Hashtable helpers for a temporary hash-table used when
2173 instantiating a CHREC or resolving mixers. For this use
2174 instantiated_below is always the same. */
2176 struct instantiate_cache_type
2178 htab_t map;
2179 vec<scev_info_str> entries;
2181 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2182 ~instantiate_cache_type ();
2183 tree get (unsigned slot) { return entries[slot].chrec; }
2184 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2187 instantiate_cache_type::~instantiate_cache_type ()
2189 if (map != NULL)
2191 htab_delete (map);
2192 entries.release ();
2196 /* Cache to avoid infinite recursion when instantiating an SSA name.
2197 Live during the outermost instantiate_scev or resolve_mixers call. */
2198 static instantiate_cache_type *global_cache;
2200 /* Computes a hash function for database element ELT. */
2202 static inline hashval_t
2203 hash_idx_scev_info (const void *elt_)
2205 unsigned idx = ((size_t) elt_) - 2;
2206 return scev_info_hasher::hash (&global_cache->entries[idx]);
2209 /* Compares database elements E1 and E2. */
2211 static inline int
2212 eq_idx_scev_info (const void *e1, const void *e2)
2214 unsigned idx1 = ((size_t) e1) - 2;
2215 return scev_info_hasher::equal (&global_cache->entries[idx1],
2216 (const scev_info_str *) e2);
2219 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2221 static unsigned
2222 get_instantiated_value_entry (instantiate_cache_type &cache,
2223 tree name, basic_block instantiate_below)
2225 if (!cache.map)
2227 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2228 cache.entries.create (10);
2231 scev_info_str e;
2232 e.name_version = SSA_NAME_VERSION (name);
2233 e.instantiated_below = instantiate_below->index;
2234 void **slot = htab_find_slot_with_hash (cache.map, &e,
2235 scev_info_hasher::hash (&e), INSERT);
2236 if (!*slot)
2238 e.chrec = chrec_not_analyzed_yet;
2239 *slot = (void *)(size_t)(cache.entries.length () + 2);
2240 cache.entries.safe_push (e);
2243 return ((size_t)*slot) - 2;
2247 /* Return the closed_loop_phi node for VAR. If there is none, return
2248 NULL_TREE. */
2250 static tree
2251 loop_closed_phi_def (tree var)
2253 struct loop *loop;
2254 edge exit;
2255 gphi *phi;
2256 gphi_iterator psi;
2258 if (var == NULL_TREE
2259 || TREE_CODE (var) != SSA_NAME)
2260 return NULL_TREE;
2262 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2263 exit = single_exit (loop);
2264 if (!exit)
2265 return NULL_TREE;
2267 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2269 phi = psi.phi ();
2270 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2271 return PHI_RESULT (phi);
2274 return NULL_TREE;
2277 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2278 tree, bool *, int);
2280 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2281 and EVOLUTION_LOOP, that were left under a symbolic form.
2283 CHREC is an SSA_NAME to be instantiated.
2285 CACHE is the cache of already instantiated values.
2287 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2288 conversions that may wrap in signed/pointer type are folded, as long
2289 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2290 then we don't do such fold.
2292 SIZE_EXPR is used for computing the size of the expression to be
2293 instantiated, and to stop if it exceeds some limit. */
2295 static tree
2296 instantiate_scev_name (basic_block instantiate_below,
2297 struct loop *evolution_loop, struct loop *inner_loop,
2298 tree chrec,
2299 bool *fold_conversions,
2300 int size_expr)
2302 tree res;
2303 struct loop *def_loop;
2304 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2306 /* A parameter (or loop invariant and we do not want to include
2307 evolutions in outer loops), nothing to do. */
2308 if (!def_bb
2309 || loop_depth (def_bb->loop_father) == 0
2310 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2311 return chrec;
2313 /* We cache the value of instantiated variable to avoid exponential
2314 time complexity due to reevaluations. We also store the convenient
2315 value in the cache in order to prevent infinite recursion -- we do
2316 not want to instantiate the SSA_NAME if it is in a mixer
2317 structure. This is used for avoiding the instantiation of
2318 recursively defined functions, such as:
2320 | a_2 -> {0, +, 1, +, a_2}_1 */
2322 unsigned si = get_instantiated_value_entry (*global_cache,
2323 chrec, instantiate_below);
2324 if (global_cache->get (si) != chrec_not_analyzed_yet)
2325 return global_cache->get (si);
2327 /* On recursion return chrec_dont_know. */
2328 global_cache->set (si, chrec_dont_know);
2330 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2332 /* If the analysis yields a parametric chrec, instantiate the
2333 result again. */
2334 res = analyze_scalar_evolution (def_loop, chrec);
2336 /* Don't instantiate default definitions. */
2337 if (TREE_CODE (res) == SSA_NAME
2338 && SSA_NAME_IS_DEFAULT_DEF (res))
2341 /* Don't instantiate loop-closed-ssa phi nodes. */
2342 else if (TREE_CODE (res) == SSA_NAME
2343 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2344 > loop_depth (def_loop))
2346 if (res == chrec)
2347 res = loop_closed_phi_def (chrec);
2348 else
2349 res = chrec;
2351 /* When there is no loop_closed_phi_def, it means that the
2352 variable is not used after the loop: try to still compute the
2353 value of the variable when exiting the loop. */
2354 if (res == NULL_TREE)
2356 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2357 res = analyze_scalar_evolution (loop, chrec);
2358 res = compute_overall_effect_of_inner_loop (loop, res);
2359 res = instantiate_scev_r (instantiate_below, evolution_loop,
2360 inner_loop, res,
2361 fold_conversions, size_expr);
2363 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2364 gimple_bb (SSA_NAME_DEF_STMT (res))))
2365 res = chrec_dont_know;
2368 else if (res != chrec_dont_know)
2370 if (inner_loop
2371 && def_bb->loop_father != inner_loop
2372 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2373 /* ??? We could try to compute the overall effect of the loop here. */
2374 res = chrec_dont_know;
2375 else
2376 res = instantiate_scev_r (instantiate_below, evolution_loop,
2377 inner_loop, res,
2378 fold_conversions, size_expr);
2381 /* Store the correct value to the cache. */
2382 global_cache->set (si, res);
2383 return res;
2386 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2387 and EVOLUTION_LOOP, that were left under a symbolic form.
2389 CHREC is a polynomial chain of recurrence to be instantiated.
2391 CACHE is the cache of already instantiated values.
2393 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2394 conversions that may wrap in signed/pointer type are folded, as long
2395 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2396 then we don't do such fold.
2398 SIZE_EXPR is used for computing the size of the expression to be
2399 instantiated, and to stop if it exceeds some limit. */
2401 static tree
2402 instantiate_scev_poly (basic_block instantiate_below,
2403 struct loop *evolution_loop, struct loop *,
2404 tree chrec, bool *fold_conversions, int size_expr)
2406 tree op1;
2407 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2408 get_chrec_loop (chrec),
2409 CHREC_LEFT (chrec), fold_conversions,
2410 size_expr);
2411 if (op0 == chrec_dont_know)
2412 return chrec_dont_know;
2414 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2415 get_chrec_loop (chrec),
2416 CHREC_RIGHT (chrec), fold_conversions,
2417 size_expr);
2418 if (op1 == chrec_dont_know)
2419 return chrec_dont_know;
2421 if (CHREC_LEFT (chrec) != op0
2422 || CHREC_RIGHT (chrec) != op1)
2424 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2425 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2428 return chrec;
2431 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2432 and EVOLUTION_LOOP, that were left under a symbolic form.
2434 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2436 CACHE is the cache of already instantiated values.
2438 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2439 conversions that may wrap in signed/pointer type are folded, as long
2440 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2441 then we don't do such fold.
2443 SIZE_EXPR is used for computing the size of the expression to be
2444 instantiated, and to stop if it exceeds some limit. */
2446 static tree
2447 instantiate_scev_binary (basic_block instantiate_below,
2448 struct loop *evolution_loop, struct loop *inner_loop,
2449 tree chrec, enum tree_code code,
2450 tree type, tree c0, tree c1,
2451 bool *fold_conversions, int size_expr)
2453 tree op1;
2454 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2455 c0, fold_conversions, size_expr);
2456 if (op0 == chrec_dont_know)
2457 return chrec_dont_know;
2459 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2460 c1, fold_conversions, size_expr);
2461 if (op1 == chrec_dont_know)
2462 return chrec_dont_know;
2464 if (c0 != op0
2465 || c1 != op1)
2467 op0 = chrec_convert (type, op0, NULL);
2468 op1 = chrec_convert_rhs (type, op1, NULL);
2470 switch (code)
2472 case POINTER_PLUS_EXPR:
2473 case PLUS_EXPR:
2474 return chrec_fold_plus (type, op0, op1);
2476 case MINUS_EXPR:
2477 return chrec_fold_minus (type, op0, op1);
2479 case MULT_EXPR:
2480 return chrec_fold_multiply (type, op0, op1);
2482 default:
2483 gcc_unreachable ();
2487 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2490 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2491 and EVOLUTION_LOOP, that were left under a symbolic form.
2493 "CHREC" is an array reference to be instantiated.
2495 CACHE is the cache of already instantiated values.
2497 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2498 conversions that may wrap in signed/pointer type are folded, as long
2499 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2500 then we don't do such fold.
2502 SIZE_EXPR is used for computing the size of the expression to be
2503 instantiated, and to stop if it exceeds some limit. */
2505 static tree
2506 instantiate_array_ref (basic_block instantiate_below,
2507 struct loop *evolution_loop, struct loop *inner_loop,
2508 tree chrec, bool *fold_conversions, int size_expr)
2510 tree res;
2511 tree index = TREE_OPERAND (chrec, 1);
2512 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2513 inner_loop, index,
2514 fold_conversions, size_expr);
2516 if (op1 == chrec_dont_know)
2517 return chrec_dont_know;
2519 if (chrec && op1 == index)
2520 return chrec;
2522 res = unshare_expr (chrec);
2523 TREE_OPERAND (res, 1) = op1;
2524 return res;
2527 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2528 and EVOLUTION_LOOP, that were left under a symbolic form.
2530 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2531 instantiated.
2533 CACHE is the cache of already instantiated values.
2535 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2536 conversions that may wrap in signed/pointer type are folded, as long
2537 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2538 then we don't do such fold.
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, fold_conversions);
2559 if (tmp)
2560 return tmp;
2562 /* If we used chrec_convert_aggressive, we can no longer assume that
2563 signed chrecs do not overflow, as chrec_convert does, so avoid
2564 calling it in that case. */
2565 if (*fold_conversions)
2567 if (chrec && op0 == op)
2568 return chrec;
2570 return fold_convert (type, op0);
2574 return chrec_convert (type, op0, NULL);
2577 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2578 and EVOLUTION_LOOP, that were left under a symbolic form.
2580 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2581 Handle ~X as -1 - X.
2582 Handle -X as -1 * X.
2584 CACHE is the cache of already instantiated values.
2586 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2587 conversions that may wrap in signed/pointer type are folded, as long
2588 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2589 then we don't do such fold.
2591 SIZE_EXPR is used for computing the size of the expression to be
2592 instantiated, and to stop if it exceeds some limit. */
2594 static tree
2595 instantiate_scev_not (basic_block instantiate_below,
2596 struct loop *evolution_loop, struct loop *inner_loop,
2597 tree chrec,
2598 enum tree_code code, tree type, tree op,
2599 bool *fold_conversions, int size_expr)
2601 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2602 inner_loop, op,
2603 fold_conversions, size_expr);
2605 if (op0 == chrec_dont_know)
2606 return chrec_dont_know;
2608 if (op != op0)
2610 op0 = chrec_convert (type, op0, NULL);
2612 switch (code)
2614 case BIT_NOT_EXPR:
2615 return chrec_fold_minus
2616 (type, fold_convert (type, integer_minus_one_node), op0);
2618 case NEGATE_EXPR:
2619 return chrec_fold_multiply
2620 (type, fold_convert (type, integer_minus_one_node), op0);
2622 default:
2623 gcc_unreachable ();
2627 return chrec ? chrec : fold_build1 (code, type, op0);
2630 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2631 and EVOLUTION_LOOP, that were left under a symbolic form.
2633 CHREC is an expression with 3 operands to be instantiated.
2635 CACHE is the cache of already instantiated values.
2637 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2638 conversions that may wrap in signed/pointer type are folded, as long
2639 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2640 then we don't do such fold.
2642 SIZE_EXPR is used for computing the size of the expression to be
2643 instantiated, and to stop if it exceeds some limit. */
2645 static tree
2646 instantiate_scev_3 (basic_block instantiate_below,
2647 struct loop *evolution_loop, struct loop *inner_loop,
2648 tree chrec,
2649 bool *fold_conversions, int size_expr)
2651 tree op1, op2;
2652 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2653 inner_loop, TREE_OPERAND (chrec, 0),
2654 fold_conversions, size_expr);
2655 if (op0 == chrec_dont_know)
2656 return chrec_dont_know;
2658 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2659 inner_loop, TREE_OPERAND (chrec, 1),
2660 fold_conversions, size_expr);
2661 if (op1 == chrec_dont_know)
2662 return chrec_dont_know;
2664 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2665 inner_loop, TREE_OPERAND (chrec, 2),
2666 fold_conversions, size_expr);
2667 if (op2 == chrec_dont_know)
2668 return chrec_dont_know;
2670 if (op0 == TREE_OPERAND (chrec, 0)
2671 && op1 == TREE_OPERAND (chrec, 1)
2672 && op2 == TREE_OPERAND (chrec, 2))
2673 return chrec;
2675 return fold_build3 (TREE_CODE (chrec),
2676 TREE_TYPE (chrec), op0, op1, op2);
2679 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2680 and EVOLUTION_LOOP, that were left under a symbolic form.
2682 CHREC is an expression with 2 operands to be instantiated.
2684 CACHE is the cache of already instantiated values.
2686 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2687 conversions that may wrap in signed/pointer type are folded, as long
2688 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2689 then we don't do such fold.
2691 SIZE_EXPR is used for computing the size of the expression to be
2692 instantiated, and to stop if it exceeds some limit. */
2694 static tree
2695 instantiate_scev_2 (basic_block instantiate_below,
2696 struct loop *evolution_loop, struct loop *inner_loop,
2697 tree chrec,
2698 bool *fold_conversions, int size_expr)
2700 tree op1;
2701 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2702 inner_loop, TREE_OPERAND (chrec, 0),
2703 fold_conversions, size_expr);
2704 if (op0 == chrec_dont_know)
2705 return chrec_dont_know;
2707 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2708 inner_loop, TREE_OPERAND (chrec, 1),
2709 fold_conversions, size_expr);
2710 if (op1 == chrec_dont_know)
2711 return chrec_dont_know;
2713 if (op0 == TREE_OPERAND (chrec, 0)
2714 && op1 == TREE_OPERAND (chrec, 1))
2715 return chrec;
2717 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2720 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2721 and EVOLUTION_LOOP, that were left under a symbolic form.
2723 CHREC is an expression with 2 operands to be instantiated.
2725 CACHE is the cache of already instantiated values.
2727 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2728 conversions that may wrap in signed/pointer type are folded, as long
2729 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2730 then we don't do such fold.
2732 SIZE_EXPR is used for computing the size of the expression to be
2733 instantiated, and to stop if it exceeds some limit. */
2735 static tree
2736 instantiate_scev_1 (basic_block instantiate_below,
2737 struct loop *evolution_loop, struct loop *inner_loop,
2738 tree chrec,
2739 bool *fold_conversions, int size_expr)
2741 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2742 inner_loop, TREE_OPERAND (chrec, 0),
2743 fold_conversions, size_expr);
2745 if (op0 == chrec_dont_know)
2746 return chrec_dont_know;
2748 if (op0 == TREE_OPERAND (chrec, 0))
2749 return chrec;
2751 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2754 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2755 and EVOLUTION_LOOP, that were left under a symbolic form.
2757 CHREC is the scalar evolution to instantiate.
2759 CACHE is the cache of already instantiated values.
2761 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2762 conversions that may wrap in signed/pointer type are folded, as long
2763 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2764 then we don't do such fold.
2766 SIZE_EXPR is used for computing the size of the expression to be
2767 instantiated, and to stop if it exceeds some limit. */
2769 static tree
2770 instantiate_scev_r (basic_block instantiate_below,
2771 struct loop *evolution_loop, struct loop *inner_loop,
2772 tree chrec,
2773 bool *fold_conversions, int size_expr)
2775 /* Give up if the expression is larger than the MAX that we allow. */
2776 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2777 return chrec_dont_know;
2779 if (chrec == NULL_TREE
2780 || automatically_generated_chrec_p (chrec)
2781 || is_gimple_min_invariant (chrec))
2782 return chrec;
2784 switch (TREE_CODE (chrec))
2786 case SSA_NAME:
2787 return instantiate_scev_name (instantiate_below, evolution_loop,
2788 inner_loop, chrec,
2789 fold_conversions, size_expr);
2791 case POLYNOMIAL_CHREC:
2792 return instantiate_scev_poly (instantiate_below, evolution_loop,
2793 inner_loop, chrec,
2794 fold_conversions, size_expr);
2796 case POINTER_PLUS_EXPR:
2797 case PLUS_EXPR:
2798 case MINUS_EXPR:
2799 case MULT_EXPR:
2800 return instantiate_scev_binary (instantiate_below, evolution_loop,
2801 inner_loop, chrec,
2802 TREE_CODE (chrec), chrec_type (chrec),
2803 TREE_OPERAND (chrec, 0),
2804 TREE_OPERAND (chrec, 1),
2805 fold_conversions, size_expr);
2807 CASE_CONVERT:
2808 return instantiate_scev_convert (instantiate_below, evolution_loop,
2809 inner_loop, chrec,
2810 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2811 fold_conversions, size_expr);
2813 case NEGATE_EXPR:
2814 case BIT_NOT_EXPR:
2815 return instantiate_scev_not (instantiate_below, evolution_loop,
2816 inner_loop, chrec,
2817 TREE_CODE (chrec), TREE_TYPE (chrec),
2818 TREE_OPERAND (chrec, 0),
2819 fold_conversions, size_expr);
2821 case ADDR_EXPR:
2822 case SCEV_NOT_KNOWN:
2823 return chrec_dont_know;
2825 case SCEV_KNOWN:
2826 return chrec_known;
2828 case ARRAY_REF:
2829 return instantiate_array_ref (instantiate_below, evolution_loop,
2830 inner_loop, chrec,
2831 fold_conversions, size_expr);
2833 default:
2834 break;
2837 if (VL_EXP_CLASS_P (chrec))
2838 return chrec_dont_know;
2840 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2842 case 3:
2843 return instantiate_scev_3 (instantiate_below, evolution_loop,
2844 inner_loop, chrec,
2845 fold_conversions, size_expr);
2847 case 2:
2848 return instantiate_scev_2 (instantiate_below, evolution_loop,
2849 inner_loop, chrec,
2850 fold_conversions, size_expr);
2852 case 1:
2853 return instantiate_scev_1 (instantiate_below, evolution_loop,
2854 inner_loop, chrec,
2855 fold_conversions, size_expr);
2857 case 0:
2858 return chrec;
2860 default:
2861 break;
2864 /* Too complicated to handle. */
2865 return chrec_dont_know;
2868 /* Analyze all the parameters of the chrec that were left under a
2869 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2870 recursive instantiation of parameters: a parameter is a variable
2871 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2872 a function parameter. */
2874 tree
2875 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2876 tree chrec)
2878 tree res;
2880 if (dump_file && (dump_flags & TDF_SCEV))
2882 fprintf (dump_file, "(instantiate_scev \n");
2883 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2884 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2885 fprintf (dump_file, " (chrec = ");
2886 print_generic_expr (dump_file, chrec, 0);
2887 fprintf (dump_file, ")\n");
2890 bool destr = false;
2891 if (!global_cache)
2893 global_cache = new instantiate_cache_type;
2894 destr = true;
2897 res = instantiate_scev_r (instantiate_below, evolution_loop,
2898 NULL, chrec, NULL, 0);
2900 if (destr)
2902 delete global_cache;
2903 global_cache = NULL;
2906 if (dump_file && (dump_flags & TDF_SCEV))
2908 fprintf (dump_file, " (res = ");
2909 print_generic_expr (dump_file, res, 0);
2910 fprintf (dump_file, "))\n");
2913 return res;
2916 /* Similar to instantiate_parameters, but does not introduce the
2917 evolutions in outer loops for LOOP invariants in CHREC, and does not
2918 care about causing overflows, as long as they do not affect value
2919 of an expression. */
2921 tree
2922 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
2924 bool destr = false;
2925 bool fold_conversions = false;
2926 if (!global_cache)
2928 global_cache = new instantiate_cache_type;
2929 destr = true;
2932 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
2933 chrec, &fold_conversions, 0);
2935 if (folded_casts && !*folded_casts)
2936 *folded_casts = fold_conversions;
2938 if (destr)
2940 delete global_cache;
2941 global_cache = NULL;
2944 return ret;
2947 /* Entry point for the analysis of the number of iterations pass.
2948 This function tries to safely approximate the number of iterations
2949 the loop will run. When this property is not decidable at compile
2950 time, the result is chrec_dont_know. Otherwise the result is a
2951 scalar or a symbolic parameter. When the number of iterations may
2952 be equal to zero and the property cannot be determined at compile
2953 time, the result is a COND_EXPR that represents in a symbolic form
2954 the conditions under which the number of iterations is not zero.
2956 Example of analysis: suppose that the loop has an exit condition:
2958 "if (b > 49) goto end_loop;"
2960 and that in a previous analysis we have determined that the
2961 variable 'b' has an evolution function:
2963 "EF = {23, +, 5}_2".
2965 When we evaluate the function at the point 5, i.e. the value of the
2966 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2967 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2968 the loop body has been executed 6 times. */
2970 tree
2971 number_of_latch_executions (struct loop *loop)
2973 edge exit;
2974 struct tree_niter_desc niter_desc;
2975 tree may_be_zero;
2976 tree res;
2978 /* Determine whether the number of iterations in loop has already
2979 been computed. */
2980 res = loop->nb_iterations;
2981 if (res)
2982 return res;
2984 may_be_zero = NULL_TREE;
2986 if (dump_file && (dump_flags & TDF_SCEV))
2987 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2989 res = chrec_dont_know;
2990 exit = single_exit (loop);
2992 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2994 may_be_zero = niter_desc.may_be_zero;
2995 res = niter_desc.niter;
2998 if (res == chrec_dont_know
2999 || !may_be_zero
3000 || integer_zerop (may_be_zero))
3002 else if (integer_nonzerop (may_be_zero))
3003 res = build_int_cst (TREE_TYPE (res), 0);
3005 else if (COMPARISON_CLASS_P (may_be_zero))
3006 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
3007 build_int_cst (TREE_TYPE (res), 0), res);
3008 else
3009 res = chrec_dont_know;
3011 if (dump_file && (dump_flags & TDF_SCEV))
3013 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
3014 print_generic_expr (dump_file, res, 0);
3015 fprintf (dump_file, "))\n");
3018 loop->nb_iterations = res;
3019 return res;
3023 /* Counters for the stats. */
3025 struct chrec_stats
3027 unsigned nb_chrecs;
3028 unsigned nb_affine;
3029 unsigned nb_affine_multivar;
3030 unsigned nb_higher_poly;
3031 unsigned nb_chrec_dont_know;
3032 unsigned nb_undetermined;
3035 /* Reset the counters. */
3037 static inline void
3038 reset_chrecs_counters (struct chrec_stats *stats)
3040 stats->nb_chrecs = 0;
3041 stats->nb_affine = 0;
3042 stats->nb_affine_multivar = 0;
3043 stats->nb_higher_poly = 0;
3044 stats->nb_chrec_dont_know = 0;
3045 stats->nb_undetermined = 0;
3048 /* Dump the contents of a CHREC_STATS structure. */
3050 static void
3051 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3053 fprintf (file, "\n(\n");
3054 fprintf (file, "-----------------------------------------\n");
3055 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3056 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3057 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3058 stats->nb_higher_poly);
3059 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3060 fprintf (file, "-----------------------------------------\n");
3061 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3062 fprintf (file, "%d\twith undetermined coefficients\n",
3063 stats->nb_undetermined);
3064 fprintf (file, "-----------------------------------------\n");
3065 fprintf (file, "%d\tchrecs in the scev database\n",
3066 (int) scalar_evolution_info->elements ());
3067 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3068 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3069 fprintf (file, "-----------------------------------------\n");
3070 fprintf (file, ")\n\n");
3073 /* Gather statistics about CHREC. */
3075 static void
3076 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3078 if (dump_file && (dump_flags & TDF_STATS))
3080 fprintf (dump_file, "(classify_chrec ");
3081 print_generic_expr (dump_file, chrec, 0);
3082 fprintf (dump_file, "\n");
3085 stats->nb_chrecs++;
3087 if (chrec == NULL_TREE)
3089 stats->nb_undetermined++;
3090 return;
3093 switch (TREE_CODE (chrec))
3095 case POLYNOMIAL_CHREC:
3096 if (evolution_function_is_affine_p (chrec))
3098 if (dump_file && (dump_flags & TDF_STATS))
3099 fprintf (dump_file, " affine_univariate\n");
3100 stats->nb_affine++;
3102 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3104 if (dump_file && (dump_flags & TDF_STATS))
3105 fprintf (dump_file, " affine_multivariate\n");
3106 stats->nb_affine_multivar++;
3108 else
3110 if (dump_file && (dump_flags & TDF_STATS))
3111 fprintf (dump_file, " higher_degree_polynomial\n");
3112 stats->nb_higher_poly++;
3115 break;
3117 default:
3118 break;
3121 if (chrec_contains_undetermined (chrec))
3123 if (dump_file && (dump_flags & TDF_STATS))
3124 fprintf (dump_file, " undetermined\n");
3125 stats->nb_undetermined++;
3128 if (dump_file && (dump_flags & TDF_STATS))
3129 fprintf (dump_file, ")\n");
3132 /* Classify the chrecs of the whole database. */
3134 void
3135 gather_stats_on_scev_database (void)
3137 struct chrec_stats stats;
3139 if (!dump_file)
3140 return;
3142 reset_chrecs_counters (&stats);
3144 hash_table<scev_info_hasher>::iterator iter;
3145 scev_info_str *elt;
3146 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3147 iter)
3148 gather_chrec_stats (elt->chrec, &stats);
3150 dump_chrecs_stats (dump_file, &stats);
3155 /* Initializer. */
3157 static void
3158 initialize_scalar_evolutions_analyzer (void)
3160 /* The elements below are unique. */
3161 if (chrec_dont_know == NULL_TREE)
3163 chrec_not_analyzed_yet = NULL_TREE;
3164 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3165 chrec_known = make_node (SCEV_KNOWN);
3166 TREE_TYPE (chrec_dont_know) = void_type_node;
3167 TREE_TYPE (chrec_known) = void_type_node;
3171 /* Initialize the analysis of scalar evolutions for LOOPS. */
3173 void
3174 scev_initialize (void)
3176 struct loop *loop;
3178 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3180 initialize_scalar_evolutions_analyzer ();
3182 FOR_EACH_LOOP (loop, 0)
3184 loop->nb_iterations = NULL_TREE;
3188 /* Return true if SCEV is initialized. */
3190 bool
3191 scev_initialized_p (void)
3193 return scalar_evolution_info != NULL;
3196 /* Cleans up the information cached by the scalar evolutions analysis
3197 in the hash table. */
3199 void
3200 scev_reset_htab (void)
3202 if (!scalar_evolution_info)
3203 return;
3205 scalar_evolution_info->empty ();
3208 /* Cleans up the information cached by the scalar evolutions analysis
3209 in the hash table and in the loop->nb_iterations. */
3211 void
3212 scev_reset (void)
3214 struct loop *loop;
3216 scev_reset_htab ();
3218 FOR_EACH_LOOP (loop, 0)
3220 loop->nb_iterations = NULL_TREE;
3224 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3225 respect to WRTO_LOOP and returns its base and step in IV if possible
3226 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3227 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3228 invariant in LOOP. Otherwise we require it to be an integer constant.
3230 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3231 because it is computed in signed arithmetics). Consequently, adding an
3232 induction variable
3234 for (i = IV->base; ; i += IV->step)
3236 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3237 false for the type of the induction variable, or you can prove that i does
3238 not wrap by some other argument. Otherwise, this might introduce undefined
3239 behavior, and
3241 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3243 must be used instead. */
3245 bool
3246 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3247 affine_iv *iv, bool allow_nonconstant_step)
3249 tree type, ev;
3250 bool folded_casts;
3252 iv->base = NULL_TREE;
3253 iv->step = NULL_TREE;
3254 iv->no_overflow = false;
3256 type = TREE_TYPE (op);
3257 if (!POINTER_TYPE_P (type)
3258 && !INTEGRAL_TYPE_P (type))
3259 return false;
3261 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3262 &folded_casts);
3263 if (chrec_contains_undetermined (ev)
3264 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3265 return false;
3267 if (tree_does_not_contain_chrecs (ev))
3269 iv->base = ev;
3270 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3271 iv->no_overflow = true;
3272 return true;
3275 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3276 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3277 return false;
3279 iv->step = CHREC_RIGHT (ev);
3280 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3281 || tree_contains_chrecs (iv->step, NULL))
3282 return false;
3284 iv->base = CHREC_LEFT (ev);
3285 if (tree_contains_chrecs (iv->base, NULL))
3286 return false;
3288 iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
3289 && TYPE_OVERFLOW_UNDEFINED (type));
3291 return true;
3294 /* Finalize the scalar evolution analysis. */
3296 void
3297 scev_finalize (void)
3299 if (!scalar_evolution_info)
3300 return;
3301 scalar_evolution_info->empty ();
3302 scalar_evolution_info = NULL;
3305 /* Returns true if the expression EXPR is considered to be too expensive
3306 for scev_const_prop. */
3308 bool
3309 expression_expensive_p (tree expr)
3311 enum tree_code code;
3313 if (is_gimple_val (expr))
3314 return false;
3316 code = TREE_CODE (expr);
3317 if (code == TRUNC_DIV_EXPR
3318 || code == CEIL_DIV_EXPR
3319 || code == FLOOR_DIV_EXPR
3320 || code == ROUND_DIV_EXPR
3321 || code == TRUNC_MOD_EXPR
3322 || code == CEIL_MOD_EXPR
3323 || code == FLOOR_MOD_EXPR
3324 || code == ROUND_MOD_EXPR
3325 || code == EXACT_DIV_EXPR)
3327 /* Division by power of two is usually cheap, so we allow it.
3328 Forbid anything else. */
3329 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3330 return true;
3333 switch (TREE_CODE_CLASS (code))
3335 case tcc_binary:
3336 case tcc_comparison:
3337 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3338 return true;
3340 /* Fallthru. */
3341 case tcc_unary:
3342 return expression_expensive_p (TREE_OPERAND (expr, 0));
3344 default:
3345 return true;
3349 /* Replace ssa names for that scev can prove they are constant by the
3350 appropriate constants. Also perform final value replacement in loops,
3351 in case the replacement expressions are cheap.
3353 We only consider SSA names defined by phi nodes; rest is left to the
3354 ordinary constant propagation pass. */
3356 unsigned int
3357 scev_const_prop (void)
3359 basic_block bb;
3360 tree name, type, ev;
3361 gphi *phi;
3362 gassign *ass;
3363 struct loop *loop, *ex_loop;
3364 bitmap ssa_names_to_remove = NULL;
3365 unsigned i;
3366 gphi_iterator psi;
3368 if (number_of_loops (cfun) <= 1)
3369 return 0;
3371 FOR_EACH_BB_FN (bb, cfun)
3373 loop = bb->loop_father;
3375 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3377 phi = psi.phi ();
3378 name = PHI_RESULT (phi);
3380 if (virtual_operand_p (name))
3381 continue;
3383 type = TREE_TYPE (name);
3385 if (!POINTER_TYPE_P (type)
3386 && !INTEGRAL_TYPE_P (type))
3387 continue;
3389 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3390 NULL);
3391 if (!is_gimple_min_invariant (ev)
3392 || !may_propagate_copy (name, ev))
3393 continue;
3395 /* Replace the uses of the name. */
3396 if (name != ev)
3397 replace_uses_by (name, ev);
3399 if (!ssa_names_to_remove)
3400 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3401 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3405 /* Remove the ssa names that were replaced by constants. We do not
3406 remove them directly in the previous cycle, since this
3407 invalidates scev cache. */
3408 if (ssa_names_to_remove)
3410 bitmap_iterator bi;
3412 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3414 gimple_stmt_iterator psi;
3415 name = ssa_name (i);
3416 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3418 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3419 psi = gsi_for_stmt (phi);
3420 remove_phi_node (&psi, true);
3423 BITMAP_FREE (ssa_names_to_remove);
3424 scev_reset ();
3427 /* Now the regular final value replacement. */
3428 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3430 edge exit;
3431 tree def, rslt, niter;
3432 gimple_stmt_iterator gsi;
3434 /* If we do not know exact number of iterations of the loop, we cannot
3435 replace the final value. */
3436 exit = single_exit (loop);
3437 if (!exit)
3438 continue;
3440 niter = number_of_latch_executions (loop);
3441 if (niter == chrec_dont_know)
3442 continue;
3444 /* Ensure that it is possible to insert new statements somewhere. */
3445 if (!single_pred_p (exit->dest))
3446 split_loop_exit_edge (exit);
3447 gsi = gsi_after_labels (exit->dest);
3449 ex_loop = superloop_at_depth (loop,
3450 loop_depth (exit->dest->loop_father) + 1);
3452 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3454 phi = psi.phi ();
3455 rslt = PHI_RESULT (phi);
3456 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3457 if (virtual_operand_p (def))
3459 gsi_next (&psi);
3460 continue;
3463 if (!POINTER_TYPE_P (TREE_TYPE (def))
3464 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3466 gsi_next (&psi);
3467 continue;
3470 bool folded_casts;
3471 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3472 &folded_casts);
3473 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3474 if (!tree_does_not_contain_chrecs (def)
3475 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3476 /* Moving the computation from the loop may prolong life range
3477 of some ssa names, which may cause problems if they appear
3478 on abnormal edges. */
3479 || contains_abnormal_ssa_name_p (def)
3480 /* Do not emit expensive expressions. The rationale is that
3481 when someone writes a code like
3483 while (n > 45) n -= 45;
3485 he probably knows that n is not large, and does not want it
3486 to be turned into n %= 45. */
3487 || expression_expensive_p (def))
3489 if (dump_file && (dump_flags & TDF_DETAILS))
3491 fprintf (dump_file, "not replacing:\n ");
3492 print_gimple_stmt (dump_file, phi, 0, 0);
3493 fprintf (dump_file, "\n");
3495 gsi_next (&psi);
3496 continue;
3499 /* Eliminate the PHI node and replace it by a computation outside
3500 the loop. */
3501 if (dump_file)
3503 fprintf (dump_file, "\nfinal value replacement:\n ");
3504 print_gimple_stmt (dump_file, phi, 0, 0);
3505 fprintf (dump_file, " with\n ");
3507 def = unshare_expr (def);
3508 remove_phi_node (&psi, false);
3510 /* If def's type has undefined overflow and there were folded
3511 casts, rewrite all stmts added for def into arithmetics
3512 with defined overflow behavior. */
3513 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3514 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3516 gimple_seq stmts;
3517 gimple_stmt_iterator gsi2;
3518 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3519 gsi2 = gsi_start (stmts);
3520 while (!gsi_end_p (gsi2))
3522 gimple stmt = gsi_stmt (gsi2);
3523 gimple_stmt_iterator gsi3 = gsi2;
3524 gsi_next (&gsi2);
3525 gsi_remove (&gsi3, false);
3526 if (is_gimple_assign (stmt)
3527 && arith_code_with_undefined_signed_overflow
3528 (gimple_assign_rhs_code (stmt)))
3529 gsi_insert_seq_before (&gsi,
3530 rewrite_to_defined_overflow (stmt),
3531 GSI_SAME_STMT);
3532 else
3533 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3536 else
3537 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3538 true, GSI_SAME_STMT);
3540 ass = gimple_build_assign (rslt, def);
3541 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3542 if (dump_file)
3544 print_gimple_stmt (dump_file, ass, 0, 0);
3545 fprintf (dump_file, "\n");
3549 return 0;
3552 #include "gt-tree-scalar-evolution.h"