Daily bump.
[official-gcc.git] / gcc / tree-scalar-evolution.c
blob4b0ec02b4de5e397ae57c442896e65d156fd38ab
1 /* Scalar evolution detector.
2 Copyright (C) 2003-2018 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 "backend.h"
260 #include "rtl.h"
261 #include "tree.h"
262 #include "gimple.h"
263 #include "ssa.h"
264 #include "gimple-pretty-print.h"
265 #include "fold-const.h"
266 #include "gimplify.h"
267 #include "gimple-iterator.h"
268 #include "gimplify-me.h"
269 #include "tree-cfg.h"
270 #include "tree-ssa-loop-ivopts.h"
271 #include "tree-ssa-loop-manip.h"
272 #include "tree-ssa-loop-niter.h"
273 #include "tree-ssa-loop.h"
274 #include "tree-ssa.h"
275 #include "cfgloop.h"
276 #include "tree-chrec.h"
277 #include "tree-affine.h"
278 #include "tree-scalar-evolution.h"
279 #include "dumpfile.h"
280 #include "params.h"
281 #include "tree-ssa-propagate.h"
282 #include "gimple-fold.h"
283 #include "tree-into-ssa.h"
284 #include "builtins.h"
286 static tree analyze_scalar_evolution_1 (struct loop *, tree);
287 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
288 tree var);
290 /* The cached information about an SSA name with version NAME_VERSION,
291 claiming that below basic block with index INSTANTIATED_BELOW, the
292 value of the SSA name can be expressed as CHREC. */
294 struct GTY((for_user)) scev_info_str {
295 unsigned int name_version;
296 int instantiated_below;
297 tree chrec;
300 /* Counters for the scev database. */
301 static unsigned nb_set_scev = 0;
302 static unsigned nb_get_scev = 0;
304 /* The following trees are unique elements. Thus the comparison of
305 another element to these elements should be done on the pointer to
306 these trees, and not on their value. */
308 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
309 tree chrec_not_analyzed_yet;
311 /* Reserved to the cases where the analyzer has detected an
312 undecidable property at compile time. */
313 tree chrec_dont_know;
315 /* When the analyzer has detected that a property will never
316 happen, then it qualifies it with chrec_known. */
317 tree chrec_known;
319 struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
321 static hashval_t hash (scev_info_str *i);
322 static bool equal (const scev_info_str *a, const scev_info_str *b);
325 static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
328 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
330 static inline struct scev_info_str *
331 new_scev_info_str (basic_block instantiated_below, tree var)
333 struct scev_info_str *res;
335 res = ggc_alloc<scev_info_str> ();
336 res->name_version = SSA_NAME_VERSION (var);
337 res->chrec = chrec_not_analyzed_yet;
338 res->instantiated_below = instantiated_below->index;
340 return res;
343 /* Computes a hash function for database element ELT. */
345 hashval_t
346 scev_info_hasher::hash (scev_info_str *elt)
348 return elt->name_version ^ elt->instantiated_below;
351 /* Compares database elements E1 and E2. */
353 bool
354 scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
356 return (elt1->name_version == elt2->name_version
357 && elt1->instantiated_below == elt2->instantiated_below);
360 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
361 A first query on VAR returns chrec_not_analyzed_yet. */
363 static tree *
364 find_var_scev_info (basic_block instantiated_below, tree var)
366 struct scev_info_str *res;
367 struct scev_info_str tmp;
369 tmp.name_version = SSA_NAME_VERSION (var);
370 tmp.instantiated_below = instantiated_below->index;
371 scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
373 if (!*slot)
374 *slot = new_scev_info_str (instantiated_below, var);
375 res = *slot;
377 return &res->chrec;
380 /* Return true when CHREC contains symbolic names defined in
381 LOOP_NB. */
383 bool
384 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
386 int i, n;
388 if (chrec == NULL_TREE)
389 return false;
391 if (is_gimple_min_invariant (chrec))
392 return false;
394 if (TREE_CODE (chrec) == SSA_NAME)
396 gimple *def;
397 loop_p def_loop, loop;
399 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
400 return false;
402 def = SSA_NAME_DEF_STMT (chrec);
403 def_loop = loop_containing_stmt (def);
404 loop = get_loop (cfun, loop_nb);
406 if (def_loop == NULL)
407 return false;
409 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
410 return true;
412 return false;
415 n = TREE_OPERAND_LENGTH (chrec);
416 for (i = 0; i < n; i++)
417 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
418 loop_nb))
419 return true;
420 return false;
423 /* Return true when PHI is a loop-phi-node. */
425 static bool
426 loop_phi_node_p (gimple *phi)
428 /* The implementation of this function is based on the following
429 property: "all the loop-phi-nodes of a loop are contained in the
430 loop's header basic block". */
432 return loop_containing_stmt (phi)->header == gimple_bb (phi);
435 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
436 In general, in the case of multivariate evolutions we want to get
437 the evolution in different loops. LOOP specifies the level for
438 which to get the evolution.
440 Example:
442 | for (j = 0; j < 100; j++)
444 | for (k = 0; k < 100; k++)
446 | i = k + j; - Here the value of i is a function of j, k.
448 | ... = i - Here the value of i is a function of j.
450 | ... = i - Here the value of i is a scalar.
452 Example:
454 | i_0 = ...
455 | loop_1 10 times
456 | i_1 = phi (i_0, i_2)
457 | i_2 = i_1 + 2
458 | endloop
460 This loop has the same effect as:
461 LOOP_1 has the same effect as:
463 | i_1 = i_0 + 20
465 The overall effect of the loop, "i_0 + 20" in the previous example,
466 is obtained by passing in the parameters: LOOP = 1,
467 EVOLUTION_FN = {i_0, +, 2}_1.
470 tree
471 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
473 bool val = false;
475 if (evolution_fn == chrec_dont_know)
476 return chrec_dont_know;
478 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
480 struct loop *inner_loop = get_chrec_loop (evolution_fn);
482 if (inner_loop == loop
483 || flow_loop_nested_p (loop, inner_loop))
485 tree nb_iter = number_of_latch_executions (inner_loop);
487 if (nb_iter == chrec_dont_know)
488 return chrec_dont_know;
489 else
491 tree res;
493 /* evolution_fn is the evolution function in LOOP. Get
494 its value in the nb_iter-th iteration. */
495 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
497 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
498 res = instantiate_parameters (loop, res);
500 /* Continue the computation until ending on a parent of LOOP. */
501 return compute_overall_effect_of_inner_loop (loop, res);
504 else
505 return evolution_fn;
508 /* If the evolution function is an invariant, there is nothing to do. */
509 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
510 return evolution_fn;
512 else
513 return chrec_dont_know;
516 /* Associate CHREC to SCALAR. */
518 static void
519 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
521 tree *scalar_info;
523 if (TREE_CODE (scalar) != SSA_NAME)
524 return;
526 scalar_info = find_var_scev_info (instantiated_below, scalar);
528 if (dump_file)
530 if (dump_flags & TDF_SCEV)
532 fprintf (dump_file, "(set_scalar_evolution \n");
533 fprintf (dump_file, " instantiated_below = %d \n",
534 instantiated_below->index);
535 fprintf (dump_file, " (scalar = ");
536 print_generic_expr (dump_file, scalar);
537 fprintf (dump_file, ")\n (scalar_evolution = ");
538 print_generic_expr (dump_file, chrec);
539 fprintf (dump_file, "))\n");
541 if (dump_flags & TDF_STATS)
542 nb_set_scev++;
545 *scalar_info = chrec;
548 /* Retrieve the chrec associated to SCALAR instantiated below
549 INSTANTIATED_BELOW block. */
551 static tree
552 get_scalar_evolution (basic_block instantiated_below, tree scalar)
554 tree res;
556 if (dump_file)
558 if (dump_flags & TDF_SCEV)
560 fprintf (dump_file, "(get_scalar_evolution \n");
561 fprintf (dump_file, " (scalar = ");
562 print_generic_expr (dump_file, scalar);
563 fprintf (dump_file, ")\n");
565 if (dump_flags & TDF_STATS)
566 nb_get_scev++;
569 if (VECTOR_TYPE_P (TREE_TYPE (scalar))
570 || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
571 /* For chrec_dont_know we keep the symbolic form. */
572 res = scalar;
573 else
574 switch (TREE_CODE (scalar))
576 case SSA_NAME:
577 if (SSA_NAME_IS_DEFAULT_DEF (scalar))
578 res = scalar;
579 else
580 res = *find_var_scev_info (instantiated_below, scalar);
581 break;
583 case REAL_CST:
584 case FIXED_CST:
585 case INTEGER_CST:
586 res = scalar;
587 break;
589 default:
590 res = chrec_not_analyzed_yet;
591 break;
594 if (dump_file && (dump_flags & TDF_SCEV))
596 fprintf (dump_file, " (scalar_evolution = ");
597 print_generic_expr (dump_file, res);
598 fprintf (dump_file, "))\n");
601 return res;
604 /* Helper function for add_to_evolution. Returns the evolution
605 function for an assignment of the form "a = b + c", where "a" and
606 "b" are on the strongly connected component. CHREC_BEFORE is the
607 information that we already have collected up to this point.
608 TO_ADD is the evolution of "c".
610 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
611 evolution the expression TO_ADD, otherwise construct an evolution
612 part for this loop. */
614 static tree
615 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
616 gimple *at_stmt)
618 tree type, left, right;
619 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
621 switch (TREE_CODE (chrec_before))
623 case POLYNOMIAL_CHREC:
624 chloop = get_chrec_loop (chrec_before);
625 if (chloop == loop
626 || flow_loop_nested_p (chloop, loop))
628 unsigned var;
630 type = chrec_type (chrec_before);
632 /* When there is no evolution part in this loop, build it. */
633 if (chloop != loop)
635 var = loop_nb;
636 left = chrec_before;
637 right = SCALAR_FLOAT_TYPE_P (type)
638 ? build_real (type, dconst0)
639 : build_int_cst (type, 0);
641 else
643 var = CHREC_VARIABLE (chrec_before);
644 left = CHREC_LEFT (chrec_before);
645 right = CHREC_RIGHT (chrec_before);
648 to_add = chrec_convert (type, to_add, at_stmt);
649 right = chrec_convert_rhs (type, right, at_stmt);
650 right = chrec_fold_plus (chrec_type (right), right, to_add);
651 return build_polynomial_chrec (var, left, right);
653 else
655 gcc_assert (flow_loop_nested_p (loop, chloop));
657 /* Search the evolution in LOOP_NB. */
658 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
659 to_add, at_stmt);
660 right = CHREC_RIGHT (chrec_before);
661 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
662 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
663 left, right);
666 default:
667 /* These nodes do not depend on a loop. */
668 if (chrec_before == chrec_dont_know)
669 return chrec_dont_know;
671 left = chrec_before;
672 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
673 return build_polynomial_chrec (loop_nb, left, right);
677 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
678 of LOOP_NB.
680 Description (provided for completeness, for those who read code in
681 a plane, and for my poor 62 bytes brain that would have forgotten
682 all this in the next two or three months):
684 The algorithm of translation of programs from the SSA representation
685 into the chrecs syntax is based on a pattern matching. After having
686 reconstructed the overall tree expression for a loop, there are only
687 two cases that can arise:
689 1. a = loop-phi (init, a + expr)
690 2. a = loop-phi (init, expr)
692 where EXPR is either a scalar constant with respect to the analyzed
693 loop (this is a degree 0 polynomial), or an expression containing
694 other loop-phi definitions (these are higher degree polynomials).
696 Examples:
699 | init = ...
700 | loop_1
701 | a = phi (init, a + 5)
702 | endloop
705 | inita = ...
706 | initb = ...
707 | loop_1
708 | a = phi (inita, 2 * b + 3)
709 | b = phi (initb, b + 1)
710 | endloop
712 For the first case, the semantics of the SSA representation is:
714 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
716 that is, there is a loop index "x" that determines the scalar value
717 of the variable during the loop execution. During the first
718 iteration, the value is that of the initial condition INIT, while
719 during the subsequent iterations, it is the sum of the initial
720 condition with the sum of all the values of EXPR from the initial
721 iteration to the before last considered iteration.
723 For the second case, the semantics of the SSA program is:
725 | a (x) = init, if x = 0;
726 | expr (x - 1), otherwise.
728 The second case corresponds to the PEELED_CHREC, whose syntax is
729 close to the syntax of a loop-phi-node:
731 | phi (init, expr) vs. (init, expr)_x
733 The proof of the translation algorithm for the first case is a
734 proof by structural induction based on the degree of EXPR.
736 Degree 0:
737 When EXPR is a constant with respect to the analyzed loop, or in
738 other words when EXPR is a polynomial of degree 0, the evolution of
739 the variable A in the loop is an affine function with an initial
740 condition INIT, and a step EXPR. In order to show this, we start
741 from the semantics of the SSA representation:
743 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
745 and since "expr (j)" is a constant with respect to "j",
747 f (x) = init + x * expr
749 Finally, based on the semantics of the pure sum chrecs, by
750 identification we get the corresponding chrecs syntax:
752 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
753 f (x) -> {init, +, expr}_x
755 Higher degree:
756 Suppose that EXPR is a polynomial of degree N with respect to the
757 analyzed loop_x for which we have already determined that it is
758 written under the chrecs syntax:
760 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
762 We start from the semantics of the SSA program:
764 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
766 | f (x) = init + \sum_{j = 0}^{x - 1}
767 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
769 | f (x) = init + \sum_{j = 0}^{x - 1}
770 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
772 | f (x) = init + \sum_{k = 0}^{n - 1}
773 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
775 | f (x) = init + \sum_{k = 0}^{n - 1}
776 | (b_k * \binom{x}{k + 1})
778 | f (x) = init + b_0 * \binom{x}{1} + ...
779 | + b_{n-1} * \binom{x}{n}
781 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
782 | + b_{n-1} * \binom{x}{n}
785 And finally from the definition of the chrecs syntax, we identify:
786 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
788 This shows the mechanism that stands behind the add_to_evolution
789 function. An important point is that the use of symbolic
790 parameters avoids the need of an analysis schedule.
792 Example:
794 | inita = ...
795 | initb = ...
796 | loop_1
797 | a = phi (inita, a + 2 + b)
798 | b = phi (initb, b + 1)
799 | endloop
801 When analyzing "a", the algorithm keeps "b" symbolically:
803 | a -> {inita, +, 2 + b}_1
805 Then, after instantiation, the analyzer ends on the evolution:
807 | a -> {inita, +, 2 + initb, +, 1}_1
811 static tree
812 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
813 tree to_add, gimple *at_stmt)
815 tree type = chrec_type (to_add);
816 tree res = NULL_TREE;
818 if (to_add == NULL_TREE)
819 return chrec_before;
821 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
822 instantiated at this point. */
823 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
824 /* This should not happen. */
825 return chrec_dont_know;
827 if (dump_file && (dump_flags & TDF_SCEV))
829 fprintf (dump_file, "(add_to_evolution \n");
830 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
831 fprintf (dump_file, " (chrec_before = ");
832 print_generic_expr (dump_file, chrec_before);
833 fprintf (dump_file, ")\n (to_add = ");
834 print_generic_expr (dump_file, to_add);
835 fprintf (dump_file, ")\n");
838 if (code == MINUS_EXPR)
839 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
840 ? build_real (type, dconstm1)
841 : build_int_cst_type (type, -1));
843 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
845 if (dump_file && (dump_flags & TDF_SCEV))
847 fprintf (dump_file, " (res = ");
848 print_generic_expr (dump_file, res);
849 fprintf (dump_file, "))\n");
852 return res;
857 /* This section selects the loops that will be good candidates for the
858 scalar evolution analysis. For the moment, greedily select all the
859 loop nests we could analyze. */
861 /* For a loop with a single exit edge, return the COND_EXPR that
862 guards the exit edge. If the expression is too difficult to
863 analyze, then give up. */
865 gcond *
866 get_loop_exit_condition (const struct loop *loop)
868 gcond *res = NULL;
869 edge exit_edge = single_exit (loop);
871 if (dump_file && (dump_flags & TDF_SCEV))
872 fprintf (dump_file, "(get_loop_exit_condition \n ");
874 if (exit_edge)
876 gimple *stmt;
878 stmt = last_stmt (exit_edge->src);
879 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
880 res = cond_stmt;
883 if (dump_file && (dump_flags & TDF_SCEV))
885 print_gimple_stmt (dump_file, res, 0);
886 fprintf (dump_file, ")\n");
889 return res;
893 /* Depth first search algorithm. */
895 enum t_bool {
896 t_false,
897 t_true,
898 t_dont_know
902 static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *,
903 tree *, int);
905 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
906 Return true if the strongly connected component has been found. */
908 static t_bool
909 follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt,
910 tree type, tree rhs0, enum tree_code code, tree rhs1,
911 gphi *halting_phi, tree *evolution_of_loop,
912 int limit)
914 t_bool res = t_false;
915 tree evol;
917 switch (code)
919 case POINTER_PLUS_EXPR:
920 case PLUS_EXPR:
921 if (TREE_CODE (rhs0) == SSA_NAME)
923 if (TREE_CODE (rhs1) == SSA_NAME)
925 /* Match an assignment under the form:
926 "a = b + c". */
928 /* We want only assignments of form "name + name" contribute to
929 LIMIT, as the other cases do not necessarily contribute to
930 the complexity of the expression. */
931 limit++;
933 evol = *evolution_of_loop;
934 evol = add_to_evolution
935 (loop->num,
936 chrec_convert (type, evol, at_stmt),
937 code, rhs1, at_stmt);
938 res = follow_ssa_edge
939 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
940 if (res == t_true)
941 *evolution_of_loop = evol;
942 else if (res == t_false)
944 *evolution_of_loop = add_to_evolution
945 (loop->num,
946 chrec_convert (type, *evolution_of_loop, at_stmt),
947 code, rhs0, at_stmt);
948 res = follow_ssa_edge
949 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
950 evolution_of_loop, limit);
951 if (res == t_true)
953 else if (res == t_dont_know)
954 *evolution_of_loop = chrec_dont_know;
957 else if (res == t_dont_know)
958 *evolution_of_loop = chrec_dont_know;
961 else
963 /* Match an assignment under the form:
964 "a = b + ...". */
965 *evolution_of_loop = add_to_evolution
966 (loop->num, chrec_convert (type, *evolution_of_loop,
967 at_stmt),
968 code, rhs1, at_stmt);
969 res = follow_ssa_edge
970 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
971 evolution_of_loop, limit);
972 if (res == t_true)
974 else if (res == t_dont_know)
975 *evolution_of_loop = chrec_dont_know;
979 else if (TREE_CODE (rhs1) == SSA_NAME)
981 /* Match an assignment under the form:
982 "a = ... + c". */
983 *evolution_of_loop = add_to_evolution
984 (loop->num, chrec_convert (type, *evolution_of_loop,
985 at_stmt),
986 code, rhs0, at_stmt);
987 res = follow_ssa_edge
988 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
989 evolution_of_loop, limit);
990 if (res == t_true)
992 else if (res == t_dont_know)
993 *evolution_of_loop = chrec_dont_know;
996 else
997 /* Otherwise, match an assignment under the form:
998 "a = ... + ...". */
999 /* And there is nothing to do. */
1000 res = t_false;
1001 break;
1003 case MINUS_EXPR:
1004 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1005 if (TREE_CODE (rhs0) == SSA_NAME)
1007 /* Match an assignment under the form:
1008 "a = b - ...". */
1010 /* We want only assignments of form "name - name" contribute to
1011 LIMIT, as the other cases do not necessarily contribute to
1012 the complexity of the expression. */
1013 if (TREE_CODE (rhs1) == SSA_NAME)
1014 limit++;
1016 *evolution_of_loop = add_to_evolution
1017 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1018 MINUS_EXPR, rhs1, at_stmt);
1019 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1020 evolution_of_loop, limit);
1021 if (res == t_true)
1023 else if (res == t_dont_know)
1024 *evolution_of_loop = chrec_dont_know;
1026 else
1027 /* Otherwise, match an assignment under the form:
1028 "a = ... - ...". */
1029 /* And there is nothing to do. */
1030 res = t_false;
1031 break;
1033 default:
1034 res = t_false;
1037 return res;
1040 /* Follow the ssa edge into the expression EXPR.
1041 Return true if the strongly connected component has been found. */
1043 static t_bool
1044 follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr,
1045 gphi *halting_phi, tree *evolution_of_loop,
1046 int limit)
1048 enum tree_code code = TREE_CODE (expr);
1049 tree type = TREE_TYPE (expr), rhs0, rhs1;
1050 t_bool res;
1052 /* The EXPR is one of the following cases:
1053 - an SSA_NAME,
1054 - an INTEGER_CST,
1055 - a PLUS_EXPR,
1056 - a POINTER_PLUS_EXPR,
1057 - a MINUS_EXPR,
1058 - an ASSERT_EXPR,
1059 - other cases are not yet handled. */
1061 switch (code)
1063 CASE_CONVERT:
1064 /* This assignment is under the form "a_1 = (cast) rhs. */
1065 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1066 halting_phi, evolution_of_loop, limit);
1067 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1068 break;
1070 case INTEGER_CST:
1071 /* This assignment is under the form "a_1 = 7". */
1072 res = t_false;
1073 break;
1075 case SSA_NAME:
1076 /* This assignment is under the form: "a_1 = b_2". */
1077 res = follow_ssa_edge
1078 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1079 break;
1081 case POINTER_PLUS_EXPR:
1082 case PLUS_EXPR:
1083 case MINUS_EXPR:
1084 /* This case is under the form "rhs0 +- rhs1". */
1085 rhs0 = TREE_OPERAND (expr, 0);
1086 rhs1 = TREE_OPERAND (expr, 1);
1087 type = TREE_TYPE (rhs0);
1088 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1089 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1090 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1091 halting_phi, evolution_of_loop, limit);
1092 break;
1094 case ADDR_EXPR:
1095 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1096 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1098 expr = TREE_OPERAND (expr, 0);
1099 rhs0 = TREE_OPERAND (expr, 0);
1100 rhs1 = TREE_OPERAND (expr, 1);
1101 type = TREE_TYPE (rhs0);
1102 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1103 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1104 res = follow_ssa_edge_binary (loop, at_stmt, type,
1105 rhs0, POINTER_PLUS_EXPR, rhs1,
1106 halting_phi, evolution_of_loop, limit);
1108 else
1109 res = t_false;
1110 break;
1112 case ASSERT_EXPR:
1113 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1114 It must be handled as a copy assignment of the form a_1 = a_2. */
1115 rhs0 = ASSERT_EXPR_VAR (expr);
1116 if (TREE_CODE (rhs0) == SSA_NAME)
1117 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1118 halting_phi, evolution_of_loop, limit);
1119 else
1120 res = t_false;
1121 break;
1123 default:
1124 res = t_false;
1125 break;
1128 return res;
1131 /* Follow the ssa edge into the right hand side of an assignment STMT.
1132 Return true if the strongly connected component has been found. */
1134 static t_bool
1135 follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt,
1136 gphi *halting_phi, tree *evolution_of_loop,
1137 int limit)
1139 enum tree_code code = gimple_assign_rhs_code (stmt);
1140 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1141 t_bool res;
1143 switch (code)
1145 CASE_CONVERT:
1146 /* This assignment is under the form "a_1 = (cast) rhs. */
1147 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1148 halting_phi, evolution_of_loop, limit);
1149 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1150 break;
1152 case POINTER_PLUS_EXPR:
1153 case PLUS_EXPR:
1154 case MINUS_EXPR:
1155 rhs1 = gimple_assign_rhs1 (stmt);
1156 rhs2 = gimple_assign_rhs2 (stmt);
1157 type = TREE_TYPE (rhs1);
1158 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1159 halting_phi, evolution_of_loop, limit);
1160 break;
1162 default:
1163 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1164 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1165 halting_phi, evolution_of_loop, limit);
1166 else
1167 res = t_false;
1168 break;
1171 return res;
1174 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1176 static bool
1177 backedge_phi_arg_p (gphi *phi, int i)
1179 const_edge e = gimple_phi_arg_edge (phi, i);
1181 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1182 about updating it anywhere, and this should work as well most of the
1183 time. */
1184 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1185 return true;
1187 return false;
1190 /* Helper function for one branch of the condition-phi-node. Return
1191 true if the strongly connected component has been found following
1192 this path. */
1194 static inline t_bool
1195 follow_ssa_edge_in_condition_phi_branch (int i,
1196 struct loop *loop,
1197 gphi *condition_phi,
1198 gphi *halting_phi,
1199 tree *evolution_of_branch,
1200 tree init_cond, int limit)
1202 tree branch = PHI_ARG_DEF (condition_phi, i);
1203 *evolution_of_branch = chrec_dont_know;
1205 /* Do not follow back edges (they must belong to an irreducible loop, which
1206 we really do not want to worry about). */
1207 if (backedge_phi_arg_p (condition_phi, i))
1208 return t_false;
1210 if (TREE_CODE (branch) == SSA_NAME)
1212 *evolution_of_branch = init_cond;
1213 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1214 evolution_of_branch, limit);
1217 /* This case occurs when one of the condition branches sets
1218 the variable to a constant: i.e. a phi-node like
1219 "a_2 = PHI <a_7(5), 2(6)>;".
1221 FIXME: This case have to be refined correctly:
1222 in some cases it is possible to say something better than
1223 chrec_dont_know, for example using a wrap-around notation. */
1224 return t_false;
1227 /* This function merges the branches of a condition-phi-node in a
1228 loop. */
1230 static t_bool
1231 follow_ssa_edge_in_condition_phi (struct loop *loop,
1232 gphi *condition_phi,
1233 gphi *halting_phi,
1234 tree *evolution_of_loop, int limit)
1236 int i, n;
1237 tree init = *evolution_of_loop;
1238 tree evolution_of_branch;
1239 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1240 halting_phi,
1241 &evolution_of_branch,
1242 init, limit);
1243 if (res == t_false || res == t_dont_know)
1244 return res;
1246 *evolution_of_loop = evolution_of_branch;
1248 n = gimple_phi_num_args (condition_phi);
1249 for (i = 1; i < n; i++)
1251 /* Quickly give up when the evolution of one of the branches is
1252 not known. */
1253 if (*evolution_of_loop == chrec_dont_know)
1254 return t_true;
1256 /* Increase the limit by the PHI argument number to avoid exponential
1257 time and memory complexity. */
1258 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1259 halting_phi,
1260 &evolution_of_branch,
1261 init, limit + i);
1262 if (res == t_false || res == t_dont_know)
1263 return res;
1265 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1266 evolution_of_branch);
1269 return t_true;
1272 /* Follow an SSA edge in an inner loop. It computes the overall
1273 effect of the loop, and following the symbolic initial conditions,
1274 it follows the edges in the parent loop. The inner loop is
1275 considered as a single statement. */
1277 static t_bool
1278 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1279 gphi *loop_phi_node,
1280 gphi *halting_phi,
1281 tree *evolution_of_loop, int limit)
1283 struct loop *loop = loop_containing_stmt (loop_phi_node);
1284 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1286 /* Sometimes, the inner loop is too difficult to analyze, and the
1287 result of the analysis is a symbolic parameter. */
1288 if (ev == PHI_RESULT (loop_phi_node))
1290 t_bool res = t_false;
1291 int i, n = gimple_phi_num_args (loop_phi_node);
1293 for (i = 0; i < n; i++)
1295 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1296 basic_block bb;
1298 /* Follow the edges that exit the inner loop. */
1299 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1300 if (!flow_bb_inside_loop_p (loop, bb))
1301 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1302 arg, halting_phi,
1303 evolution_of_loop, limit);
1304 if (res == t_true)
1305 break;
1308 /* If the path crosses this loop-phi, give up. */
1309 if (res == t_true)
1310 *evolution_of_loop = chrec_dont_know;
1312 return res;
1315 /* Otherwise, compute the overall effect of the inner loop. */
1316 ev = compute_overall_effect_of_inner_loop (loop, ev);
1317 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1318 evolution_of_loop, limit);
1321 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1322 path that is analyzed on the return walk. */
1324 static t_bool
1325 follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi,
1326 tree *evolution_of_loop, int limit)
1328 struct loop *def_loop;
1330 if (gimple_nop_p (def))
1331 return t_false;
1333 /* Give up if the path is longer than the MAX that we allow. */
1334 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1335 return t_dont_know;
1337 def_loop = loop_containing_stmt (def);
1339 switch (gimple_code (def))
1341 case GIMPLE_PHI:
1342 if (!loop_phi_node_p (def))
1343 /* DEF is a condition-phi-node. Follow the branches, and
1344 record their evolutions. Finally, merge the collected
1345 information and set the approximation to the main
1346 variable. */
1347 return follow_ssa_edge_in_condition_phi
1348 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1349 limit);
1351 /* When the analyzed phi is the halting_phi, the
1352 depth-first search is over: we have found a path from
1353 the halting_phi to itself in the loop. */
1354 if (def == halting_phi)
1355 return t_true;
1357 /* Otherwise, the evolution of the HALTING_PHI depends
1358 on the evolution of another loop-phi-node, i.e. the
1359 evolution function is a higher degree polynomial. */
1360 if (def_loop == loop)
1361 return t_false;
1363 /* Inner loop. */
1364 if (flow_loop_nested_p (loop, def_loop))
1365 return follow_ssa_edge_inner_loop_phi
1366 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1367 limit + 1);
1369 /* Outer loop. */
1370 return t_false;
1372 case GIMPLE_ASSIGN:
1373 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1374 evolution_of_loop, limit);
1376 default:
1377 /* At this level of abstraction, the program is just a set
1378 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1379 other node to be handled. */
1380 return t_false;
1385 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1386 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1388 # i_17 = PHI <i_13(5), 0(3)>
1389 # _20 = PHI <_5(5), start_4(D)(3)>
1391 i_13 = i_17 + 1;
1392 _5 = start_4(D) + i_13;
1394 Though variable _20 appears as a PEELED_CHREC in the form of
1395 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1397 See PR41488. */
1399 static tree
1400 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1402 aff_tree aff1, aff2;
1403 tree ev, left, right, type, step_val;
1404 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1406 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1407 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1408 return chrec_dont_know;
1410 left = CHREC_LEFT (ev);
1411 right = CHREC_RIGHT (ev);
1412 type = TREE_TYPE (left);
1413 step_val = chrec_fold_plus (type, init_cond, right);
1415 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1416 if "left" equals to "init + right". */
1417 if (operand_equal_p (left, step_val, 0))
1419 if (dump_file && (dump_flags & TDF_SCEV))
1420 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1422 return build_polynomial_chrec (loop->num, init_cond, right);
1425 /* Try harder to check if they are equal. */
1426 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1427 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1428 free_affine_expand_cache (&peeled_chrec_map);
1429 aff_combination_scale (&aff2, -1);
1430 aff_combination_add (&aff1, &aff2);
1432 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1433 if "left" equals to "init + right". */
1434 if (aff_combination_zero_p (&aff1))
1436 if (dump_file && (dump_flags & TDF_SCEV))
1437 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1439 return build_polynomial_chrec (loop->num, init_cond, right);
1441 return chrec_dont_know;
1444 /* Given a LOOP_PHI_NODE, this function determines the evolution
1445 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1447 static tree
1448 analyze_evolution_in_loop (gphi *loop_phi_node,
1449 tree init_cond)
1451 int i, n = gimple_phi_num_args (loop_phi_node);
1452 tree evolution_function = chrec_not_analyzed_yet;
1453 struct loop *loop = loop_containing_stmt (loop_phi_node);
1454 basic_block bb;
1455 static bool simplify_peeled_chrec_p = true;
1457 if (dump_file && (dump_flags & TDF_SCEV))
1459 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1460 fprintf (dump_file, " (loop_phi_node = ");
1461 print_gimple_stmt (dump_file, loop_phi_node, 0);
1462 fprintf (dump_file, ")\n");
1465 for (i = 0; i < n; i++)
1467 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1468 gimple *ssa_chain;
1469 tree ev_fn;
1470 t_bool res;
1472 /* Select the edges that enter the loop body. */
1473 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1474 if (!flow_bb_inside_loop_p (loop, bb))
1475 continue;
1477 if (TREE_CODE (arg) == SSA_NAME)
1479 bool val = false;
1481 ssa_chain = SSA_NAME_DEF_STMT (arg);
1483 /* Pass in the initial condition to the follow edge function. */
1484 ev_fn = init_cond;
1485 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1487 /* If ev_fn has no evolution in the inner loop, and the
1488 init_cond is not equal to ev_fn, then we have an
1489 ambiguity between two possible values, as we cannot know
1490 the number of iterations at this point. */
1491 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1492 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1493 && !operand_equal_p (init_cond, ev_fn, 0))
1494 ev_fn = chrec_dont_know;
1496 else
1497 res = t_false;
1499 /* When it is impossible to go back on the same
1500 loop_phi_node by following the ssa edges, the
1501 evolution is represented by a peeled chrec, i.e. the
1502 first iteration, EV_FN has the value INIT_COND, then
1503 all the other iterations it has the value of ARG.
1504 For the moment, PEELED_CHREC nodes are not built. */
1505 if (res != t_true)
1507 ev_fn = chrec_dont_know;
1508 /* Try to recognize POLYNOMIAL_CHREC which appears in
1509 the form of PEELED_CHREC, but guard the process with
1510 a bool variable to keep the analyzer from infinite
1511 recurrence for real PEELED_RECs. */
1512 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1514 simplify_peeled_chrec_p = false;
1515 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1516 simplify_peeled_chrec_p = true;
1520 /* When there are multiple back edges of the loop (which in fact never
1521 happens currently, but nevertheless), merge their evolutions. */
1522 evolution_function = chrec_merge (evolution_function, ev_fn);
1524 if (evolution_function == chrec_dont_know)
1525 break;
1528 if (dump_file && (dump_flags & TDF_SCEV))
1530 fprintf (dump_file, " (evolution_function = ");
1531 print_generic_expr (dump_file, evolution_function);
1532 fprintf (dump_file, "))\n");
1535 return evolution_function;
1538 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1539 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1541 static tree
1542 follow_copies_to_constant (tree var)
1544 tree res = var;
1545 while (TREE_CODE (res) == SSA_NAME
1546 /* We face not updated SSA form in multiple places and this walk
1547 may end up in sibling loops so we have to guard it. */
1548 && !name_registered_for_update_p (res))
1550 gimple *def = SSA_NAME_DEF_STMT (res);
1551 if (gphi *phi = dyn_cast <gphi *> (def))
1553 if (tree rhs = degenerate_phi_result (phi))
1554 res = rhs;
1555 else
1556 break;
1558 else if (gimple_assign_single_p (def))
1559 /* Will exit loop if not an SSA_NAME. */
1560 res = gimple_assign_rhs1 (def);
1561 else
1562 break;
1564 if (CONSTANT_CLASS_P (res))
1565 return res;
1566 return var;
1569 /* Given a loop-phi-node, return the initial conditions of the
1570 variable on entry of the loop. When the CCP has propagated
1571 constants into the loop-phi-node, the initial condition is
1572 instantiated, otherwise the initial condition is kept symbolic.
1573 This analyzer does not analyze the evolution outside the current
1574 loop, and leaves this task to the on-demand tree reconstructor. */
1576 static tree
1577 analyze_initial_condition (gphi *loop_phi_node)
1579 int i, n;
1580 tree init_cond = chrec_not_analyzed_yet;
1581 struct loop *loop = loop_containing_stmt (loop_phi_node);
1583 if (dump_file && (dump_flags & TDF_SCEV))
1585 fprintf (dump_file, "(analyze_initial_condition \n");
1586 fprintf (dump_file, " (loop_phi_node = \n");
1587 print_gimple_stmt (dump_file, loop_phi_node, 0);
1588 fprintf (dump_file, ")\n");
1591 n = gimple_phi_num_args (loop_phi_node);
1592 for (i = 0; i < n; i++)
1594 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1595 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1597 /* When the branch is oriented to the loop's body, it does
1598 not contribute to the initial condition. */
1599 if (flow_bb_inside_loop_p (loop, bb))
1600 continue;
1602 if (init_cond == chrec_not_analyzed_yet)
1604 init_cond = branch;
1605 continue;
1608 if (TREE_CODE (branch) == SSA_NAME)
1610 init_cond = chrec_dont_know;
1611 break;
1614 init_cond = chrec_merge (init_cond, branch);
1617 /* Ooops -- a loop without an entry??? */
1618 if (init_cond == chrec_not_analyzed_yet)
1619 init_cond = chrec_dont_know;
1621 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1622 to not miss important early loop unrollings. */
1623 init_cond = follow_copies_to_constant (init_cond);
1625 if (dump_file && (dump_flags & TDF_SCEV))
1627 fprintf (dump_file, " (init_cond = ");
1628 print_generic_expr (dump_file, init_cond);
1629 fprintf (dump_file, "))\n");
1632 return init_cond;
1635 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1637 static tree
1638 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1640 tree res;
1641 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1642 tree init_cond;
1644 gcc_assert (phi_loop == loop);
1646 /* Otherwise really interpret the loop phi. */
1647 init_cond = analyze_initial_condition (loop_phi_node);
1648 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1650 /* Verify we maintained the correct initial condition throughout
1651 possible conversions in the SSA chain. */
1652 if (res != chrec_dont_know)
1654 tree new_init = res;
1655 if (CONVERT_EXPR_P (res)
1656 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1657 new_init = fold_convert (TREE_TYPE (res),
1658 CHREC_LEFT (TREE_OPERAND (res, 0)));
1659 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1660 new_init = CHREC_LEFT (res);
1661 STRIP_USELESS_TYPE_CONVERSION (new_init);
1662 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1663 || !operand_equal_p (init_cond, new_init, 0))
1664 return chrec_dont_know;
1667 return res;
1670 /* This function merges the branches of a condition-phi-node,
1671 contained in the outermost loop, and whose arguments are already
1672 analyzed. */
1674 static tree
1675 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1677 int i, n = gimple_phi_num_args (condition_phi);
1678 tree res = chrec_not_analyzed_yet;
1680 for (i = 0; i < n; i++)
1682 tree branch_chrec;
1684 if (backedge_phi_arg_p (condition_phi, i))
1686 res = chrec_dont_know;
1687 break;
1690 branch_chrec = analyze_scalar_evolution
1691 (loop, PHI_ARG_DEF (condition_phi, i));
1693 res = chrec_merge (res, branch_chrec);
1694 if (res == chrec_dont_know)
1695 break;
1698 return res;
1701 /* Interpret the operation RHS1 OP RHS2. If we didn't
1702 analyze this node before, follow the definitions until ending
1703 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1704 return path, this function propagates evolutions (ala constant copy
1705 propagation). OPND1 is not a GIMPLE expression because we could
1706 analyze the effect of an inner loop: see interpret_loop_phi. */
1708 static tree
1709 interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
1710 tree type, tree rhs1, enum tree_code code, tree rhs2)
1712 tree res, chrec1, chrec2, ctype;
1713 gimple *def;
1715 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1717 if (is_gimple_min_invariant (rhs1))
1718 return chrec_convert (type, rhs1, at_stmt);
1720 if (code == SSA_NAME)
1721 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1722 at_stmt);
1724 if (code == ASSERT_EXPR)
1726 rhs1 = ASSERT_EXPR_VAR (rhs1);
1727 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1728 at_stmt);
1732 switch (code)
1734 case ADDR_EXPR:
1735 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1736 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1738 machine_mode mode;
1739 poly_int64 bitsize, bitpos;
1740 int unsignedp, reversep;
1741 int volatilep = 0;
1742 tree base, offset;
1743 tree chrec3;
1744 tree unitpos;
1746 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1747 &bitsize, &bitpos, &offset, &mode,
1748 &unsignedp, &reversep, &volatilep);
1750 if (TREE_CODE (base) == MEM_REF)
1752 rhs2 = TREE_OPERAND (base, 1);
1753 rhs1 = TREE_OPERAND (base, 0);
1755 chrec1 = analyze_scalar_evolution (loop, rhs1);
1756 chrec2 = analyze_scalar_evolution (loop, rhs2);
1757 chrec1 = chrec_convert (type, chrec1, at_stmt);
1758 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1759 chrec1 = instantiate_parameters (loop, chrec1);
1760 chrec2 = instantiate_parameters (loop, chrec2);
1761 res = chrec_fold_plus (type, chrec1, chrec2);
1763 else
1765 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1766 chrec1 = chrec_convert (type, chrec1, at_stmt);
1767 res = chrec1;
1770 if (offset != NULL_TREE)
1772 chrec2 = analyze_scalar_evolution (loop, offset);
1773 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1774 chrec2 = instantiate_parameters (loop, chrec2);
1775 res = chrec_fold_plus (type, res, chrec2);
1778 if (maybe_ne (bitpos, 0))
1780 unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
1781 chrec3 = analyze_scalar_evolution (loop, unitpos);
1782 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1783 chrec3 = instantiate_parameters (loop, chrec3);
1784 res = chrec_fold_plus (type, res, chrec3);
1787 else
1788 res = chrec_dont_know;
1789 break;
1791 case POINTER_PLUS_EXPR:
1792 chrec1 = analyze_scalar_evolution (loop, rhs1);
1793 chrec2 = analyze_scalar_evolution (loop, rhs2);
1794 chrec1 = chrec_convert (type, chrec1, at_stmt);
1795 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1796 chrec1 = instantiate_parameters (loop, chrec1);
1797 chrec2 = instantiate_parameters (loop, chrec2);
1798 res = chrec_fold_plus (type, chrec1, chrec2);
1799 break;
1801 case PLUS_EXPR:
1802 chrec1 = analyze_scalar_evolution (loop, rhs1);
1803 chrec2 = analyze_scalar_evolution (loop, rhs2);
1804 ctype = type;
1805 /* When the stmt is conditionally executed re-write the CHREC
1806 into a form that has well-defined behavior on overflow. */
1807 if (at_stmt
1808 && INTEGRAL_TYPE_P (type)
1809 && ! TYPE_OVERFLOW_WRAPS (type)
1810 && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1811 gimple_bb (at_stmt)))
1812 ctype = unsigned_type_for (type);
1813 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1814 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1815 chrec1 = instantiate_parameters (loop, chrec1);
1816 chrec2 = instantiate_parameters (loop, chrec2);
1817 res = chrec_fold_plus (ctype, chrec1, chrec2);
1818 if (type != ctype)
1819 res = chrec_convert (type, res, at_stmt);
1820 break;
1822 case MINUS_EXPR:
1823 chrec1 = analyze_scalar_evolution (loop, rhs1);
1824 chrec2 = analyze_scalar_evolution (loop, rhs2);
1825 ctype = type;
1826 /* When the stmt is conditionally executed re-write the CHREC
1827 into a form that has well-defined behavior on overflow. */
1828 if (at_stmt
1829 && INTEGRAL_TYPE_P (type)
1830 && ! TYPE_OVERFLOW_WRAPS (type)
1831 && ! dominated_by_p (CDI_DOMINATORS,
1832 loop->latch, gimple_bb (at_stmt)))
1833 ctype = unsigned_type_for (type);
1834 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1835 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1836 chrec1 = instantiate_parameters (loop, chrec1);
1837 chrec2 = instantiate_parameters (loop, chrec2);
1838 res = chrec_fold_minus (ctype, chrec1, chrec2);
1839 if (type != ctype)
1840 res = chrec_convert (type, res, at_stmt);
1841 break;
1843 case NEGATE_EXPR:
1844 chrec1 = analyze_scalar_evolution (loop, rhs1);
1845 ctype = type;
1846 /* When the stmt is conditionally executed re-write the CHREC
1847 into a form that has well-defined behavior on overflow. */
1848 if (at_stmt
1849 && INTEGRAL_TYPE_P (type)
1850 && ! TYPE_OVERFLOW_WRAPS (type)
1851 && ! dominated_by_p (CDI_DOMINATORS,
1852 loop->latch, gimple_bb (at_stmt)))
1853 ctype = unsigned_type_for (type);
1854 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1855 /* TYPE may be integer, real or complex, so use fold_convert. */
1856 chrec1 = instantiate_parameters (loop, chrec1);
1857 res = chrec_fold_multiply (ctype, chrec1,
1858 fold_convert (ctype, integer_minus_one_node));
1859 if (type != ctype)
1860 res = chrec_convert (type, res, at_stmt);
1861 break;
1863 case BIT_NOT_EXPR:
1864 /* Handle ~X as -1 - X. */
1865 chrec1 = analyze_scalar_evolution (loop, rhs1);
1866 chrec1 = chrec_convert (type, chrec1, at_stmt);
1867 chrec1 = instantiate_parameters (loop, chrec1);
1868 res = chrec_fold_minus (type,
1869 fold_convert (type, integer_minus_one_node),
1870 chrec1);
1871 break;
1873 case MULT_EXPR:
1874 chrec1 = analyze_scalar_evolution (loop, rhs1);
1875 chrec2 = analyze_scalar_evolution (loop, rhs2);
1876 ctype = type;
1877 /* When the stmt is conditionally executed re-write the CHREC
1878 into a form that has well-defined behavior on overflow. */
1879 if (at_stmt
1880 && INTEGRAL_TYPE_P (type)
1881 && ! TYPE_OVERFLOW_WRAPS (type)
1882 && ! dominated_by_p (CDI_DOMINATORS,
1883 loop->latch, gimple_bb (at_stmt)))
1884 ctype = unsigned_type_for (type);
1885 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1886 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1887 chrec1 = instantiate_parameters (loop, chrec1);
1888 chrec2 = instantiate_parameters (loop, chrec2);
1889 res = chrec_fold_multiply (ctype, chrec1, chrec2);
1890 if (type != ctype)
1891 res = chrec_convert (type, res, at_stmt);
1892 break;
1894 case LSHIFT_EXPR:
1896 /* Handle A<<B as A * (1<<B). */
1897 tree uns = unsigned_type_for (type);
1898 chrec1 = analyze_scalar_evolution (loop, rhs1);
1899 chrec2 = analyze_scalar_evolution (loop, rhs2);
1900 chrec1 = chrec_convert (uns, chrec1, at_stmt);
1901 chrec1 = instantiate_parameters (loop, chrec1);
1902 chrec2 = instantiate_parameters (loop, chrec2);
1904 tree one = build_int_cst (uns, 1);
1905 chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1906 res = chrec_fold_multiply (uns, chrec1, chrec2);
1907 res = chrec_convert (type, res, at_stmt);
1909 break;
1911 CASE_CONVERT:
1912 /* In case we have a truncation of a widened operation that in
1913 the truncated type has undefined overflow behavior analyze
1914 the operation done in an unsigned type of the same precision
1915 as the final truncation. We cannot derive a scalar evolution
1916 for the widened operation but for the truncated result. */
1917 if (TREE_CODE (type) == INTEGER_TYPE
1918 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1919 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1920 && TYPE_OVERFLOW_UNDEFINED (type)
1921 && TREE_CODE (rhs1) == SSA_NAME
1922 && (def = SSA_NAME_DEF_STMT (rhs1))
1923 && is_gimple_assign (def)
1924 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1925 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1927 tree utype = unsigned_type_for (type);
1928 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1929 gimple_assign_rhs1 (def),
1930 gimple_assign_rhs_code (def),
1931 gimple_assign_rhs2 (def));
1933 else
1934 chrec1 = analyze_scalar_evolution (loop, rhs1);
1935 res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
1936 break;
1938 case BIT_AND_EXPR:
1939 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1940 If A is SCEV and its value is in the range of representable set
1941 of type unsigned short, the result expression is a (no-overflow)
1942 SCEV. */
1943 res = chrec_dont_know;
1944 if (tree_fits_uhwi_p (rhs2))
1946 int precision;
1947 unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1949 val ++;
1950 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1951 it's not the maximum value of a smaller type than rhs1. */
1952 if (val != 0
1953 && (precision = exact_log2 (val)) > 0
1954 && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1956 tree utype = build_nonstandard_integer_type (precision, 1);
1958 if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1960 chrec1 = analyze_scalar_evolution (loop, rhs1);
1961 chrec1 = chrec_convert (utype, chrec1, at_stmt);
1962 res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
1966 break;
1968 default:
1969 res = chrec_dont_know;
1970 break;
1973 return res;
1976 /* Interpret the expression EXPR. */
1978 static tree
1979 interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
1981 enum tree_code code;
1982 tree type = TREE_TYPE (expr), op0, op1;
1984 if (automatically_generated_chrec_p (expr))
1985 return expr;
1987 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1988 || TREE_CODE (expr) == CALL_EXPR
1989 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1990 return chrec_dont_know;
1992 extract_ops_from_tree (expr, &code, &op0, &op1);
1994 return interpret_rhs_expr (loop, at_stmt, type,
1995 op0, code, op1);
1998 /* Interpret the rhs of the assignment STMT. */
2000 static tree
2001 interpret_gimple_assign (struct loop *loop, gimple *stmt)
2003 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2004 enum tree_code code = gimple_assign_rhs_code (stmt);
2006 return interpret_rhs_expr (loop, stmt, type,
2007 gimple_assign_rhs1 (stmt), code,
2008 gimple_assign_rhs2 (stmt));
2013 /* This section contains all the entry points:
2014 - number_of_iterations_in_loop,
2015 - analyze_scalar_evolution,
2016 - instantiate_parameters.
2019 /* Helper recursive function. */
2021 static tree
2022 analyze_scalar_evolution_1 (struct loop *loop, tree var)
2024 gimple *def;
2025 basic_block bb;
2026 struct loop *def_loop;
2027 tree res;
2029 if (TREE_CODE (var) != SSA_NAME)
2030 return interpret_expr (loop, NULL, var);
2032 def = SSA_NAME_DEF_STMT (var);
2033 bb = gimple_bb (def);
2034 def_loop = bb->loop_father;
2036 if (!flow_bb_inside_loop_p (loop, bb))
2038 /* Keep symbolic form, but look through obvious copies for constants. */
2039 res = follow_copies_to_constant (var);
2040 goto set_and_end;
2043 if (loop != def_loop)
2045 res = analyze_scalar_evolution_1 (def_loop, var);
2046 struct loop *loop_to_skip = superloop_at_depth (def_loop,
2047 loop_depth (loop) + 1);
2048 res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
2049 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
2050 res = analyze_scalar_evolution_1 (loop, res);
2051 goto set_and_end;
2054 switch (gimple_code (def))
2056 case GIMPLE_ASSIGN:
2057 res = interpret_gimple_assign (loop, def);
2058 break;
2060 case GIMPLE_PHI:
2061 if (loop_phi_node_p (def))
2062 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2063 else
2064 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2065 break;
2067 default:
2068 res = chrec_dont_know;
2069 break;
2072 set_and_end:
2074 /* Keep the symbolic form. */
2075 if (res == chrec_dont_know)
2076 res = var;
2078 if (loop == def_loop)
2079 set_scalar_evolution (block_before_loop (loop), var, res);
2081 return res;
2084 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2085 LOOP. LOOP is the loop in which the variable is used.
2087 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2088 pointer to the statement that uses this variable, in order to
2089 determine the evolution function of the variable, use the following
2090 calls:
2092 loop_p loop = loop_containing_stmt (stmt);
2093 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2094 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2097 tree
2098 analyze_scalar_evolution (struct loop *loop, tree var)
2100 tree res;
2102 /* ??? Fix callers. */
2103 if (! loop)
2104 return var;
2106 if (dump_file && (dump_flags & TDF_SCEV))
2108 fprintf (dump_file, "(analyze_scalar_evolution \n");
2109 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2110 fprintf (dump_file, " (scalar = ");
2111 print_generic_expr (dump_file, var);
2112 fprintf (dump_file, ")\n");
2115 res = get_scalar_evolution (block_before_loop (loop), var);
2116 if (res == chrec_not_analyzed_yet)
2117 res = analyze_scalar_evolution_1 (loop, var);
2119 if (dump_file && (dump_flags & TDF_SCEV))
2120 fprintf (dump_file, ")\n");
2122 return res;
2125 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2127 static tree
2128 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2130 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2133 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2134 WRTO_LOOP (which should be a superloop of USE_LOOP)
2136 FOLDED_CASTS is set to true if resolve_mixers used
2137 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2138 at the moment in order to keep things simple).
2140 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2141 example:
2143 for (i = 0; i < 100; i++) -- loop 1
2145 for (j = 0; j < 100; j++) -- loop 2
2147 k1 = i;
2148 k2 = j;
2150 use2 (k1, k2);
2152 for (t = 0; t < 100; t++) -- loop 3
2153 use3 (k1, k2);
2156 use1 (k1, k2);
2159 Both k1 and k2 are invariants in loop3, thus
2160 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2161 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2163 As they are invariant, it does not matter whether we consider their
2164 usage in loop 3 or loop 2, hence
2165 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2166 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2167 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2168 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2170 Similarly for their evolutions with respect to loop 1. The values of K2
2171 in the use in loop 2 vary independently on loop 1, thus we cannot express
2172 the evolution with respect to loop 1:
2173 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2174 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2175 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2176 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2178 The value of k2 in the use in loop 1 is known, though:
2179 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2180 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2183 static tree
2184 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2185 tree version, bool *folded_casts)
2187 bool val = false;
2188 tree ev = version, tmp;
2190 /* We cannot just do
2192 tmp = analyze_scalar_evolution (use_loop, version);
2193 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2195 as resolve_mixers would query the scalar evolution with respect to
2196 wrto_loop. For example, in the situation described in the function
2197 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2198 version = k2. Then
2200 analyze_scalar_evolution (use_loop, version) = k2
2202 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2203 k2 in loop 1 is 100, which is a wrong result, since we are interested
2204 in the value in loop 3.
2206 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2207 each time checking that there is no evolution in the inner loop. */
2209 if (folded_casts)
2210 *folded_casts = false;
2211 while (1)
2213 tmp = analyze_scalar_evolution (use_loop, ev);
2214 ev = resolve_mixers (use_loop, tmp, folded_casts);
2216 if (use_loop == wrto_loop)
2217 return ev;
2219 /* If the value of the use changes in the inner loop, we cannot express
2220 its value in the outer loop (we might try to return interval chrec,
2221 but we do not have a user for it anyway) */
2222 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2223 || !val)
2224 return chrec_dont_know;
2226 use_loop = loop_outer (use_loop);
2231 /* Hashtable helpers for a temporary hash-table used when
2232 instantiating a CHREC or resolving mixers. For this use
2233 instantiated_below is always the same. */
2235 struct instantiate_cache_type
2237 htab_t map;
2238 vec<scev_info_str> entries;
2240 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2241 ~instantiate_cache_type ();
2242 tree get (unsigned slot) { return entries[slot].chrec; }
2243 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2246 instantiate_cache_type::~instantiate_cache_type ()
2248 if (map != NULL)
2250 htab_delete (map);
2251 entries.release ();
2255 /* Cache to avoid infinite recursion when instantiating an SSA name.
2256 Live during the outermost instantiate_scev or resolve_mixers call. */
2257 static instantiate_cache_type *global_cache;
2259 /* Computes a hash function for database element ELT. */
2261 static inline hashval_t
2262 hash_idx_scev_info (const void *elt_)
2264 unsigned idx = ((size_t) elt_) - 2;
2265 return scev_info_hasher::hash (&global_cache->entries[idx]);
2268 /* Compares database elements E1 and E2. */
2270 static inline int
2271 eq_idx_scev_info (const void *e1, const void *e2)
2273 unsigned idx1 = ((size_t) e1) - 2;
2274 return scev_info_hasher::equal (&global_cache->entries[idx1],
2275 (const scev_info_str *) e2);
2278 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2280 static unsigned
2281 get_instantiated_value_entry (instantiate_cache_type &cache,
2282 tree name, edge instantiate_below)
2284 if (!cache.map)
2286 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2287 cache.entries.create (10);
2290 scev_info_str e;
2291 e.name_version = SSA_NAME_VERSION (name);
2292 e.instantiated_below = instantiate_below->dest->index;
2293 void **slot = htab_find_slot_with_hash (cache.map, &e,
2294 scev_info_hasher::hash (&e), INSERT);
2295 if (!*slot)
2297 e.chrec = chrec_not_analyzed_yet;
2298 *slot = (void *)(size_t)(cache.entries.length () + 2);
2299 cache.entries.safe_push (e);
2302 return ((size_t)*slot) - 2;
2306 /* Return the closed_loop_phi node for VAR. If there is none, return
2307 NULL_TREE. */
2309 static tree
2310 loop_closed_phi_def (tree var)
2312 struct loop *loop;
2313 edge exit;
2314 gphi *phi;
2315 gphi_iterator psi;
2317 if (var == NULL_TREE
2318 || TREE_CODE (var) != SSA_NAME)
2319 return NULL_TREE;
2321 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2322 exit = single_exit (loop);
2323 if (!exit)
2324 return NULL_TREE;
2326 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2328 phi = psi.phi ();
2329 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2330 return PHI_RESULT (phi);
2333 return NULL_TREE;
2336 static tree instantiate_scev_r (edge, struct loop *, struct loop *,
2337 tree, bool *, int);
2339 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2340 and EVOLUTION_LOOP, that were left under a symbolic form.
2342 CHREC is an SSA_NAME to be instantiated.
2344 CACHE is the cache of already instantiated values.
2346 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2347 conversions that may wrap in signed/pointer type are folded, as long
2348 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2349 then we don't do such fold.
2351 SIZE_EXPR is used for computing the size of the expression to be
2352 instantiated, and to stop if it exceeds some limit. */
2354 static tree
2355 instantiate_scev_name (edge instantiate_below,
2356 struct loop *evolution_loop, struct loop *inner_loop,
2357 tree chrec,
2358 bool *fold_conversions,
2359 int size_expr)
2361 tree res;
2362 struct loop *def_loop;
2363 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2365 /* A parameter, nothing to do. */
2366 if (!def_bb
2367 || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
2368 return chrec;
2370 /* We cache the value of instantiated variable to avoid exponential
2371 time complexity due to reevaluations. We also store the convenient
2372 value in the cache in order to prevent infinite recursion -- we do
2373 not want to instantiate the SSA_NAME if it is in a mixer
2374 structure. This is used for avoiding the instantiation of
2375 recursively defined functions, such as:
2377 | a_2 -> {0, +, 1, +, a_2}_1 */
2379 unsigned si = get_instantiated_value_entry (*global_cache,
2380 chrec, instantiate_below);
2381 if (global_cache->get (si) != chrec_not_analyzed_yet)
2382 return global_cache->get (si);
2384 /* On recursion return chrec_dont_know. */
2385 global_cache->set (si, chrec_dont_know);
2387 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2389 if (! dominated_by_p (CDI_DOMINATORS,
2390 def_loop->header, instantiate_below->dest))
2392 gimple *def = SSA_NAME_DEF_STMT (chrec);
2393 if (gassign *ass = dyn_cast <gassign *> (def))
2395 switch (gimple_assign_rhs_class (ass))
2397 case GIMPLE_UNARY_RHS:
2399 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2400 inner_loop, gimple_assign_rhs1 (ass),
2401 fold_conversions, size_expr);
2402 if (op0 == chrec_dont_know)
2403 return chrec_dont_know;
2404 res = fold_build1 (gimple_assign_rhs_code (ass),
2405 TREE_TYPE (chrec), op0);
2406 break;
2408 case GIMPLE_BINARY_RHS:
2410 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2411 inner_loop, gimple_assign_rhs1 (ass),
2412 fold_conversions, size_expr);
2413 if (op0 == chrec_dont_know)
2414 return chrec_dont_know;
2415 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2416 inner_loop, gimple_assign_rhs2 (ass),
2417 fold_conversions, size_expr);
2418 if (op1 == chrec_dont_know)
2419 return chrec_dont_know;
2420 res = fold_build2 (gimple_assign_rhs_code (ass),
2421 TREE_TYPE (chrec), op0, op1);
2422 break;
2424 default:
2425 res = chrec_dont_know;
2428 else
2429 res = chrec_dont_know;
2430 global_cache->set (si, res);
2431 return res;
2434 /* If the analysis yields a parametric chrec, instantiate the
2435 result again. */
2436 res = analyze_scalar_evolution (def_loop, chrec);
2438 /* Don't instantiate default definitions. */
2439 if (TREE_CODE (res) == SSA_NAME
2440 && SSA_NAME_IS_DEFAULT_DEF (res))
2443 /* Don't instantiate loop-closed-ssa phi nodes. */
2444 else if (TREE_CODE (res) == SSA_NAME
2445 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2446 > loop_depth (def_loop))
2448 if (res == chrec)
2449 res = loop_closed_phi_def (chrec);
2450 else
2451 res = chrec;
2453 /* When there is no loop_closed_phi_def, it means that the
2454 variable is not used after the loop: try to still compute the
2455 value of the variable when exiting the loop. */
2456 if (res == NULL_TREE)
2458 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2459 res = analyze_scalar_evolution (loop, chrec);
2460 res = compute_overall_effect_of_inner_loop (loop, res);
2461 res = instantiate_scev_r (instantiate_below, evolution_loop,
2462 inner_loop, res,
2463 fold_conversions, size_expr);
2465 else if (dominated_by_p (CDI_DOMINATORS,
2466 gimple_bb (SSA_NAME_DEF_STMT (res)),
2467 instantiate_below->dest))
2468 res = chrec_dont_know;
2471 else if (res != chrec_dont_know)
2473 if (inner_loop
2474 && def_bb->loop_father != inner_loop
2475 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2476 /* ??? We could try to compute the overall effect of the loop here. */
2477 res = chrec_dont_know;
2478 else
2479 res = instantiate_scev_r (instantiate_below, evolution_loop,
2480 inner_loop, res,
2481 fold_conversions, size_expr);
2484 /* Store the correct value to the cache. */
2485 global_cache->set (si, res);
2486 return res;
2489 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2490 and EVOLUTION_LOOP, that were left under a symbolic form.
2492 CHREC is a polynomial chain of recurrence to be instantiated.
2494 CACHE is the cache of already instantiated values.
2496 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2497 conversions that may wrap in signed/pointer type are folded, as long
2498 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2499 then we don't do such fold.
2501 SIZE_EXPR is used for computing the size of the expression to be
2502 instantiated, and to stop if it exceeds some limit. */
2504 static tree
2505 instantiate_scev_poly (edge instantiate_below,
2506 struct loop *evolution_loop, struct loop *,
2507 tree chrec, bool *fold_conversions, int size_expr)
2509 tree op1;
2510 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2511 get_chrec_loop (chrec),
2512 CHREC_LEFT (chrec), fold_conversions,
2513 size_expr);
2514 if (op0 == chrec_dont_know)
2515 return chrec_dont_know;
2517 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2518 get_chrec_loop (chrec),
2519 CHREC_RIGHT (chrec), fold_conversions,
2520 size_expr);
2521 if (op1 == chrec_dont_know)
2522 return chrec_dont_know;
2524 if (CHREC_LEFT (chrec) != op0
2525 || CHREC_RIGHT (chrec) != op1)
2527 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2528 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2531 return chrec;
2534 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2535 and EVOLUTION_LOOP, that were left under a symbolic form.
2537 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2539 CACHE is the cache of already instantiated values.
2541 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2542 conversions that may wrap in signed/pointer type are folded, as long
2543 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2544 then we don't do such fold.
2546 SIZE_EXPR is used for computing the size of the expression to be
2547 instantiated, and to stop if it exceeds some limit. */
2549 static tree
2550 instantiate_scev_binary (edge instantiate_below,
2551 struct loop *evolution_loop, struct loop *inner_loop,
2552 tree chrec, enum tree_code code,
2553 tree type, tree c0, tree c1,
2554 bool *fold_conversions, int size_expr)
2556 tree op1;
2557 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2558 c0, fold_conversions, size_expr);
2559 if (op0 == chrec_dont_know)
2560 return chrec_dont_know;
2562 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2563 c1, fold_conversions, size_expr);
2564 if (op1 == chrec_dont_know)
2565 return chrec_dont_know;
2567 if (c0 != op0
2568 || c1 != op1)
2570 op0 = chrec_convert (type, op0, NULL);
2571 op1 = chrec_convert_rhs (type, op1, NULL);
2573 switch (code)
2575 case POINTER_PLUS_EXPR:
2576 case PLUS_EXPR:
2577 return chrec_fold_plus (type, op0, op1);
2579 case MINUS_EXPR:
2580 return chrec_fold_minus (type, op0, op1);
2582 case MULT_EXPR:
2583 return chrec_fold_multiply (type, op0, op1);
2585 default:
2586 gcc_unreachable ();
2590 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2593 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2594 and EVOLUTION_LOOP, that were left under a symbolic form.
2596 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2597 instantiated.
2599 CACHE is the cache of already instantiated values.
2601 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2602 conversions that may wrap in signed/pointer type are folded, as long
2603 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2604 then we don't do such fold.
2606 SIZE_EXPR is used for computing the size of the expression to be
2607 instantiated, and to stop if it exceeds some limit. */
2609 static tree
2610 instantiate_scev_convert (edge instantiate_below,
2611 struct loop *evolution_loop, struct loop *inner_loop,
2612 tree chrec, tree type, tree op,
2613 bool *fold_conversions, int size_expr)
2615 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2616 inner_loop, op,
2617 fold_conversions, size_expr);
2619 if (op0 == chrec_dont_know)
2620 return chrec_dont_know;
2622 if (fold_conversions)
2624 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2625 if (tmp)
2626 return tmp;
2628 /* If we used chrec_convert_aggressive, we can no longer assume that
2629 signed chrecs do not overflow, as chrec_convert does, so avoid
2630 calling it in that case. */
2631 if (*fold_conversions)
2633 if (chrec && op0 == op)
2634 return chrec;
2636 return fold_convert (type, op0);
2640 return chrec_convert (type, op0, NULL);
2643 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2644 and EVOLUTION_LOOP, that were left under a symbolic form.
2646 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2647 Handle ~X as -1 - X.
2648 Handle -X as -1 * X.
2650 CACHE is the cache of already instantiated values.
2652 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2653 conversions that may wrap in signed/pointer type are folded, as long
2654 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2655 then we don't do such fold.
2657 SIZE_EXPR is used for computing the size of the expression to be
2658 instantiated, and to stop if it exceeds some limit. */
2660 static tree
2661 instantiate_scev_not (edge instantiate_below,
2662 struct loop *evolution_loop, struct loop *inner_loop,
2663 tree chrec,
2664 enum tree_code code, tree type, tree op,
2665 bool *fold_conversions, int size_expr)
2667 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2668 inner_loop, op,
2669 fold_conversions, size_expr);
2671 if (op0 == chrec_dont_know)
2672 return chrec_dont_know;
2674 if (op != op0)
2676 op0 = chrec_convert (type, op0, NULL);
2678 switch (code)
2680 case BIT_NOT_EXPR:
2681 return chrec_fold_minus
2682 (type, fold_convert (type, integer_minus_one_node), op0);
2684 case NEGATE_EXPR:
2685 return chrec_fold_multiply
2686 (type, fold_convert (type, integer_minus_one_node), op0);
2688 default:
2689 gcc_unreachable ();
2693 return chrec ? chrec : fold_build1 (code, type, op0);
2696 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2697 and EVOLUTION_LOOP, that were left under a symbolic form.
2699 CHREC is the scalar evolution to instantiate.
2701 CACHE is the cache of already instantiated values.
2703 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2704 conversions that may wrap in signed/pointer type are folded, as long
2705 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2706 then we don't do such fold.
2708 SIZE_EXPR is used for computing the size of the expression to be
2709 instantiated, and to stop if it exceeds some limit. */
2711 static tree
2712 instantiate_scev_r (edge instantiate_below,
2713 struct loop *evolution_loop, struct loop *inner_loop,
2714 tree chrec,
2715 bool *fold_conversions, int size_expr)
2717 /* Give up if the expression is larger than the MAX that we allow. */
2718 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2719 return chrec_dont_know;
2721 if (chrec == NULL_TREE
2722 || automatically_generated_chrec_p (chrec)
2723 || is_gimple_min_invariant (chrec))
2724 return chrec;
2726 switch (TREE_CODE (chrec))
2728 case SSA_NAME:
2729 return instantiate_scev_name (instantiate_below, evolution_loop,
2730 inner_loop, chrec,
2731 fold_conversions, size_expr);
2733 case POLYNOMIAL_CHREC:
2734 return instantiate_scev_poly (instantiate_below, evolution_loop,
2735 inner_loop, chrec,
2736 fold_conversions, size_expr);
2738 case POINTER_PLUS_EXPR:
2739 case PLUS_EXPR:
2740 case MINUS_EXPR:
2741 case MULT_EXPR:
2742 return instantiate_scev_binary (instantiate_below, evolution_loop,
2743 inner_loop, chrec,
2744 TREE_CODE (chrec), chrec_type (chrec),
2745 TREE_OPERAND (chrec, 0),
2746 TREE_OPERAND (chrec, 1),
2747 fold_conversions, size_expr);
2749 CASE_CONVERT:
2750 return instantiate_scev_convert (instantiate_below, evolution_loop,
2751 inner_loop, chrec,
2752 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2753 fold_conversions, size_expr);
2755 case NEGATE_EXPR:
2756 case BIT_NOT_EXPR:
2757 return instantiate_scev_not (instantiate_below, evolution_loop,
2758 inner_loop, chrec,
2759 TREE_CODE (chrec), TREE_TYPE (chrec),
2760 TREE_OPERAND (chrec, 0),
2761 fold_conversions, size_expr);
2763 case ADDR_EXPR:
2764 if (is_gimple_min_invariant (chrec))
2765 return chrec;
2766 /* Fallthru. */
2767 case SCEV_NOT_KNOWN:
2768 return chrec_dont_know;
2770 case SCEV_KNOWN:
2771 return chrec_known;
2773 default:
2774 if (CONSTANT_CLASS_P (chrec))
2775 return chrec;
2776 return chrec_dont_know;
2780 /* Analyze all the parameters of the chrec that were left under a
2781 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2782 recursive instantiation of parameters: a parameter is a variable
2783 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2784 a function parameter. */
2786 tree
2787 instantiate_scev (edge instantiate_below, struct loop *evolution_loop,
2788 tree chrec)
2790 tree res;
2792 if (dump_file && (dump_flags & TDF_SCEV))
2794 fprintf (dump_file, "(instantiate_scev \n");
2795 fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
2796 instantiate_below->src->index, instantiate_below->dest->index);
2797 if (evolution_loop)
2798 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2799 fprintf (dump_file, " (chrec = ");
2800 print_generic_expr (dump_file, chrec);
2801 fprintf (dump_file, ")\n");
2804 bool destr = false;
2805 if (!global_cache)
2807 global_cache = new instantiate_cache_type;
2808 destr = true;
2811 res = instantiate_scev_r (instantiate_below, evolution_loop,
2812 NULL, chrec, NULL, 0);
2814 if (destr)
2816 delete global_cache;
2817 global_cache = NULL;
2820 if (dump_file && (dump_flags & TDF_SCEV))
2822 fprintf (dump_file, " (res = ");
2823 print_generic_expr (dump_file, res);
2824 fprintf (dump_file, "))\n");
2827 return res;
2830 /* Similar to instantiate_parameters, but does not introduce the
2831 evolutions in outer loops for LOOP invariants in CHREC, and does not
2832 care about causing overflows, as long as they do not affect value
2833 of an expression. */
2835 tree
2836 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
2838 bool destr = false;
2839 bool fold_conversions = false;
2840 if (!global_cache)
2842 global_cache = new instantiate_cache_type;
2843 destr = true;
2846 tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
2847 chrec, &fold_conversions, 0);
2849 if (folded_casts && !*folded_casts)
2850 *folded_casts = fold_conversions;
2852 if (destr)
2854 delete global_cache;
2855 global_cache = NULL;
2858 return ret;
2861 /* Entry point for the analysis of the number of iterations pass.
2862 This function tries to safely approximate the number of iterations
2863 the loop will run. When this property is not decidable at compile
2864 time, the result is chrec_dont_know. Otherwise the result is a
2865 scalar or a symbolic parameter. When the number of iterations may
2866 be equal to zero and the property cannot be determined at compile
2867 time, the result is a COND_EXPR that represents in a symbolic form
2868 the conditions under which the number of iterations is not zero.
2870 Example of analysis: suppose that the loop has an exit condition:
2872 "if (b > 49) goto end_loop;"
2874 and that in a previous analysis we have determined that the
2875 variable 'b' has an evolution function:
2877 "EF = {23, +, 5}_2".
2879 When we evaluate the function at the point 5, i.e. the value of the
2880 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2881 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2882 the loop body has been executed 6 times. */
2884 tree
2885 number_of_latch_executions (struct loop *loop)
2887 edge exit;
2888 struct tree_niter_desc niter_desc;
2889 tree may_be_zero;
2890 tree res;
2892 /* Determine whether the number of iterations in loop has already
2893 been computed. */
2894 res = loop->nb_iterations;
2895 if (res)
2896 return res;
2898 may_be_zero = NULL_TREE;
2900 if (dump_file && (dump_flags & TDF_SCEV))
2901 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2903 res = chrec_dont_know;
2904 exit = single_exit (loop);
2906 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2908 may_be_zero = niter_desc.may_be_zero;
2909 res = niter_desc.niter;
2912 if (res == chrec_dont_know
2913 || !may_be_zero
2914 || integer_zerop (may_be_zero))
2916 else if (integer_nonzerop (may_be_zero))
2917 res = build_int_cst (TREE_TYPE (res), 0);
2919 else if (COMPARISON_CLASS_P (may_be_zero))
2920 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2921 build_int_cst (TREE_TYPE (res), 0), res);
2922 else
2923 res = chrec_dont_know;
2925 if (dump_file && (dump_flags & TDF_SCEV))
2927 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2928 print_generic_expr (dump_file, res);
2929 fprintf (dump_file, "))\n");
2932 loop->nb_iterations = res;
2933 return res;
2937 /* Counters for the stats. */
2939 struct chrec_stats
2941 unsigned nb_chrecs;
2942 unsigned nb_affine;
2943 unsigned nb_affine_multivar;
2944 unsigned nb_higher_poly;
2945 unsigned nb_chrec_dont_know;
2946 unsigned nb_undetermined;
2949 /* Reset the counters. */
2951 static inline void
2952 reset_chrecs_counters (struct chrec_stats *stats)
2954 stats->nb_chrecs = 0;
2955 stats->nb_affine = 0;
2956 stats->nb_affine_multivar = 0;
2957 stats->nb_higher_poly = 0;
2958 stats->nb_chrec_dont_know = 0;
2959 stats->nb_undetermined = 0;
2962 /* Dump the contents of a CHREC_STATS structure. */
2964 static void
2965 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2967 fprintf (file, "\n(\n");
2968 fprintf (file, "-----------------------------------------\n");
2969 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2970 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2971 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2972 stats->nb_higher_poly);
2973 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2974 fprintf (file, "-----------------------------------------\n");
2975 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2976 fprintf (file, "%d\twith undetermined coefficients\n",
2977 stats->nb_undetermined);
2978 fprintf (file, "-----------------------------------------\n");
2979 fprintf (file, "%d\tchrecs in the scev database\n",
2980 (int) scalar_evolution_info->elements ());
2981 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2982 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2983 fprintf (file, "-----------------------------------------\n");
2984 fprintf (file, ")\n\n");
2987 /* Gather statistics about CHREC. */
2989 static void
2990 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2992 if (dump_file && (dump_flags & TDF_STATS))
2994 fprintf (dump_file, "(classify_chrec ");
2995 print_generic_expr (dump_file, chrec);
2996 fprintf (dump_file, "\n");
2999 stats->nb_chrecs++;
3001 if (chrec == NULL_TREE)
3003 stats->nb_undetermined++;
3004 return;
3007 switch (TREE_CODE (chrec))
3009 case POLYNOMIAL_CHREC:
3010 if (evolution_function_is_affine_p (chrec))
3012 if (dump_file && (dump_flags & TDF_STATS))
3013 fprintf (dump_file, " affine_univariate\n");
3014 stats->nb_affine++;
3016 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3018 if (dump_file && (dump_flags & TDF_STATS))
3019 fprintf (dump_file, " affine_multivariate\n");
3020 stats->nb_affine_multivar++;
3022 else
3024 if (dump_file && (dump_flags & TDF_STATS))
3025 fprintf (dump_file, " higher_degree_polynomial\n");
3026 stats->nb_higher_poly++;
3029 break;
3031 default:
3032 break;
3035 if (chrec_contains_undetermined (chrec))
3037 if (dump_file && (dump_flags & TDF_STATS))
3038 fprintf (dump_file, " undetermined\n");
3039 stats->nb_undetermined++;
3042 if (dump_file && (dump_flags & TDF_STATS))
3043 fprintf (dump_file, ")\n");
3046 /* Classify the chrecs of the whole database. */
3048 void
3049 gather_stats_on_scev_database (void)
3051 struct chrec_stats stats;
3053 if (!dump_file)
3054 return;
3056 reset_chrecs_counters (&stats);
3058 hash_table<scev_info_hasher>::iterator iter;
3059 scev_info_str *elt;
3060 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3061 iter)
3062 gather_chrec_stats (elt->chrec, &stats);
3064 dump_chrecs_stats (dump_file, &stats);
3069 /* Initializer. */
3071 static void
3072 initialize_scalar_evolutions_analyzer (void)
3074 /* The elements below are unique. */
3075 if (chrec_dont_know == NULL_TREE)
3077 chrec_not_analyzed_yet = NULL_TREE;
3078 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3079 chrec_known = make_node (SCEV_KNOWN);
3080 TREE_TYPE (chrec_dont_know) = void_type_node;
3081 TREE_TYPE (chrec_known) = void_type_node;
3085 /* Initialize the analysis of scalar evolutions for LOOPS. */
3087 void
3088 scev_initialize (void)
3090 struct loop *loop;
3092 gcc_assert (! scev_initialized_p ());
3094 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3096 initialize_scalar_evolutions_analyzer ();
3098 FOR_EACH_LOOP (loop, 0)
3100 loop->nb_iterations = NULL_TREE;
3104 /* Return true if SCEV is initialized. */
3106 bool
3107 scev_initialized_p (void)
3109 return scalar_evolution_info != NULL;
3112 /* Cleans up the information cached by the scalar evolutions analysis
3113 in the hash table. */
3115 void
3116 scev_reset_htab (void)
3118 if (!scalar_evolution_info)
3119 return;
3121 scalar_evolution_info->empty ();
3124 /* Cleans up the information cached by the scalar evolutions analysis
3125 in the hash table and in the loop->nb_iterations. */
3127 void
3128 scev_reset (void)
3130 struct loop *loop;
3132 scev_reset_htab ();
3134 FOR_EACH_LOOP (loop, 0)
3136 loop->nb_iterations = NULL_TREE;
3140 /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3141 of the upper bound on the number of iterations of LOOP, the BASE and STEP
3142 of IV.
3144 We do not use information whether TYPE can overflow so it is safe to
3145 use this test even for derived IVs not computed every iteration or
3146 hypotetical IVs to be inserted into code. */
3148 bool
3149 iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
3151 widest_int nit;
3152 wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3153 signop sgn = TYPE_SIGN (type);
3155 if (integer_zerop (step))
3156 return false;
3158 if (TREE_CODE (base) == INTEGER_CST)
3159 base_min = base_max = wi::to_wide (base);
3160 else if (TREE_CODE (base) == SSA_NAME
3161 && INTEGRAL_TYPE_P (TREE_TYPE (base))
3162 && get_range_info (base, &base_min, &base_max) == VR_RANGE)
3164 else
3165 return true;
3167 if (TREE_CODE (step) == INTEGER_CST)
3168 step_min = step_max = wi::to_wide (step);
3169 else if (TREE_CODE (step) == SSA_NAME
3170 && INTEGRAL_TYPE_P (TREE_TYPE (step))
3171 && get_range_info (step, &step_min, &step_max) == VR_RANGE)
3173 else
3174 return true;
3176 if (!get_max_loop_iterations (loop, &nit))
3177 return true;
3179 type_min = wi::min_value (type);
3180 type_max = wi::max_value (type);
3182 /* Just sanity check that we don't see values out of the range of the type.
3183 In this case the arithmetics bellow would overflow. */
3184 gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3185 && wi::le_p (base_max, type_max, sgn));
3187 /* Account the possible increment in the last ieration. */
3188 bool overflow = false;
3189 nit = wi::add (nit, 1, SIGNED, &overflow);
3190 if (overflow)
3191 return true;
3193 /* NIT is typeless and can exceed the precision of the type. In this case
3194 overflow is always possible, because we know STEP is non-zero. */
3195 if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3196 return true;
3197 wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3199 /* If step can be positive, check that nit*step <= type_max-base.
3200 This can be done by unsigned arithmetic and we only need to watch overflow
3201 in the multiplication. The right hand side can always be represented in
3202 the type. */
3203 if (sgn == UNSIGNED || !wi::neg_p (step_max))
3205 bool overflow = false;
3206 if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3207 type_max - base_max)
3208 || overflow)
3209 return true;
3211 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3212 if (sgn == SIGNED && wi::neg_p (step_min))
3214 bool overflow = false, overflow2 = false;
3215 if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3216 nit2, UNSIGNED, &overflow),
3217 base_min - type_min)
3218 || overflow || overflow2)
3219 return true;
3222 return false;
3225 /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3226 function tries to derive condition under which it can be simplified
3227 into "{(type)inner_base, (type)inner_step}_loop". The condition is
3228 the maximum number that inner iv can iterate. */
3230 static tree
3231 derive_simple_iv_with_niters (tree ev, tree *niters)
3233 if (!CONVERT_EXPR_P (ev))
3234 return ev;
3236 tree inner_ev = TREE_OPERAND (ev, 0);
3237 if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3238 return ev;
3240 tree init = CHREC_LEFT (inner_ev);
3241 tree step = CHREC_RIGHT (inner_ev);
3242 if (TREE_CODE (init) != INTEGER_CST
3243 || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3244 return ev;
3246 tree type = TREE_TYPE (ev);
3247 tree inner_type = TREE_TYPE (inner_ev);
3248 if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3249 return ev;
3251 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3252 folded only if inner iv won't overflow. We compute the maximum
3253 number the inner iv can iterate before overflowing and return the
3254 simplified affine iv. */
3255 tree delta;
3256 init = fold_convert (type, init);
3257 step = fold_convert (type, step);
3258 ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3259 if (tree_int_cst_sign_bit (step))
3261 tree bound = lower_bound_in_type (inner_type, inner_type);
3262 delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3263 step = fold_build1 (NEGATE_EXPR, type, step);
3265 else
3267 tree bound = upper_bound_in_type (inner_type, inner_type);
3268 delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3270 *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3271 return ev;
3274 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3275 respect to WRTO_LOOP and returns its base and step in IV if possible
3276 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3277 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3278 invariant in LOOP. Otherwise we require it to be an integer constant.
3280 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3281 because it is computed in signed arithmetics). Consequently, adding an
3282 induction variable
3284 for (i = IV->base; ; i += IV->step)
3286 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3287 false for the type of the induction variable, or you can prove that i does
3288 not wrap by some other argument. Otherwise, this might introduce undefined
3289 behavior, and
3291 i = iv->base;
3292 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3294 must be used instead.
3296 When IV_NITERS is not NULL, this function also checks case in which OP
3297 is a conversion of an inner simple iv of below form:
3299 (outer_type){inner_base, inner_step}_loop.
3301 If type of inner iv has smaller precision than outer_type, it can't be
3302 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3303 the inner iv could overflow/wrap. In this case, we derive a condition
3304 under which the inner iv won't overflow/wrap and do the simplification.
3305 The derived condition normally is the maximum number the inner iv can
3306 iterate, and will be stored in IV_NITERS. This is useful in loop niter
3307 analysis, to derive break conditions when a loop must terminate, when is
3308 infinite. */
3310 bool
3311 simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop,
3312 tree op, affine_iv *iv, tree *iv_niters,
3313 bool allow_nonconstant_step)
3315 enum tree_code code;
3316 tree type, ev, base, e;
3317 wide_int extreme;
3318 bool folded_casts, overflow;
3320 iv->base = NULL_TREE;
3321 iv->step = NULL_TREE;
3322 iv->no_overflow = false;
3324 type = TREE_TYPE (op);
3325 if (!POINTER_TYPE_P (type)
3326 && !INTEGRAL_TYPE_P (type))
3327 return false;
3329 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3330 &folded_casts);
3331 if (chrec_contains_undetermined (ev)
3332 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3333 return false;
3335 if (tree_does_not_contain_chrecs (ev))
3337 iv->base = ev;
3338 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3339 iv->no_overflow = true;
3340 return true;
3343 /* If we can derive valid scalar evolution with assumptions. */
3344 if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3345 ev = derive_simple_iv_with_niters (ev, iv_niters);
3347 if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3348 return false;
3350 if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3351 return false;
3353 iv->step = CHREC_RIGHT (ev);
3354 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3355 || tree_contains_chrecs (iv->step, NULL))
3356 return false;
3358 iv->base = CHREC_LEFT (ev);
3359 if (tree_contains_chrecs (iv->base, NULL))
3360 return false;
3362 iv->no_overflow = !folded_casts && nowrap_type_p (type);
3364 if (!iv->no_overflow
3365 && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3366 iv->no_overflow = true;
3368 /* Try to simplify iv base:
3370 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3371 == (signed T)(unsigned T)base + step
3372 == base + step
3374 If we can prove operation (base + step) doesn't overflow or underflow.
3375 Specifically, we try to prove below conditions are satisfied:
3377 base <= UPPER_BOUND (type) - step ;;step > 0
3378 base >= LOWER_BOUND (type) - step ;;step < 0
3380 This is done by proving the reverse conditions are false using loop's
3381 initial conditions.
3383 The is necessary to make loop niter, or iv overflow analysis easier
3384 for below example:
3386 int foo (int *a, signed char s, signed char l)
3388 signed char i;
3389 for (i = s; i < l; i++)
3390 a[i] = 0;
3391 return 0;
3394 Note variable I is firstly converted to type unsigned char, incremented,
3395 then converted back to type signed char. */
3397 if (wrto_loop->num != use_loop->num)
3398 return true;
3400 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3401 return true;
3403 type = TREE_TYPE (iv->base);
3404 e = TREE_OPERAND (iv->base, 0);
3405 if (TREE_CODE (e) != PLUS_EXPR
3406 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3407 || !tree_int_cst_equal (iv->step,
3408 fold_convert (type, TREE_OPERAND (e, 1))))
3409 return true;
3410 e = TREE_OPERAND (e, 0);
3411 if (!CONVERT_EXPR_P (e))
3412 return true;
3413 base = TREE_OPERAND (e, 0);
3414 if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3415 return true;
3417 if (tree_int_cst_sign_bit (iv->step))
3419 code = LT_EXPR;
3420 extreme = wi::min_value (type);
3422 else
3424 code = GT_EXPR;
3425 extreme = wi::max_value (type);
3427 overflow = false;
3428 extreme = wi::sub (extreme, wi::to_wide (iv->step),
3429 TYPE_SIGN (type), &overflow);
3430 if (overflow)
3431 return true;
3432 e = fold_build2 (code, boolean_type_node, base,
3433 wide_int_to_tree (type, extreme));
3434 e = simplify_using_initial_conditions (use_loop, e);
3435 if (!integer_zerop (e))
3436 return true;
3438 if (POINTER_TYPE_P (TREE_TYPE (base)))
3439 code = POINTER_PLUS_EXPR;
3440 else
3441 code = PLUS_EXPR;
3443 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3444 return true;
3447 /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3448 affine iv unconditionally. */
3450 bool
3451 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3452 affine_iv *iv, bool allow_nonconstant_step)
3454 return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3455 NULL, allow_nonconstant_step);
3458 /* Finalize the scalar evolution analysis. */
3460 void
3461 scev_finalize (void)
3463 if (!scalar_evolution_info)
3464 return;
3465 scalar_evolution_info->empty ();
3466 scalar_evolution_info = NULL;
3467 free_numbers_of_iterations_estimates (cfun);
3470 /* Returns true if the expression EXPR is considered to be too expensive
3471 for scev_const_prop. */
3473 bool
3474 expression_expensive_p (tree expr)
3476 enum tree_code code;
3478 if (is_gimple_val (expr))
3479 return false;
3481 code = TREE_CODE (expr);
3482 if (code == TRUNC_DIV_EXPR
3483 || code == CEIL_DIV_EXPR
3484 || code == FLOOR_DIV_EXPR
3485 || code == ROUND_DIV_EXPR
3486 || code == TRUNC_MOD_EXPR
3487 || code == CEIL_MOD_EXPR
3488 || code == FLOOR_MOD_EXPR
3489 || code == ROUND_MOD_EXPR
3490 || code == EXACT_DIV_EXPR)
3492 /* Division by power of two is usually cheap, so we allow it.
3493 Forbid anything else. */
3494 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3495 return true;
3498 if (code == CALL_EXPR)
3500 tree arg;
3501 call_expr_arg_iterator iter;
3503 if (!is_inexpensive_builtin (get_callee_fndecl (expr)))
3504 return true;
3505 FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
3506 if (expression_expensive_p (arg))
3507 return true;
3508 return false;
3511 switch (TREE_CODE_CLASS (code))
3513 case tcc_binary:
3514 case tcc_comparison:
3515 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3516 return true;
3518 /* Fallthru. */
3519 case tcc_unary:
3520 return expression_expensive_p (TREE_OPERAND (expr, 0));
3522 default:
3523 return true;
3527 /* Do final value replacement for LOOP. */
3529 void
3530 final_value_replacement_loop (struct loop *loop)
3532 /* If we do not know exact number of iterations of the loop, we cannot
3533 replace the final value. */
3534 edge exit = single_exit (loop);
3535 if (!exit)
3536 return;
3538 tree niter = number_of_latch_executions (loop);
3539 if (niter == chrec_dont_know)
3540 return;
3542 /* Ensure that it is possible to insert new statements somewhere. */
3543 if (!single_pred_p (exit->dest))
3544 split_loop_exit_edge (exit);
3546 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3547 gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
3549 struct loop *ex_loop
3550 = superloop_at_depth (loop,
3551 loop_depth (exit->dest->loop_father) + 1);
3553 gphi_iterator psi;
3554 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3556 gphi *phi = psi.phi ();
3557 tree rslt = PHI_RESULT (phi);
3558 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3559 if (virtual_operand_p (def))
3561 gsi_next (&psi);
3562 continue;
3565 if (!POINTER_TYPE_P (TREE_TYPE (def))
3566 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3568 gsi_next (&psi);
3569 continue;
3572 bool folded_casts;
3573 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3574 &folded_casts);
3575 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3576 if (!tree_does_not_contain_chrecs (def)
3577 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3578 /* Moving the computation from the loop may prolong life range
3579 of some ssa names, which may cause problems if they appear
3580 on abnormal edges. */
3581 || contains_abnormal_ssa_name_p (def)
3582 /* Do not emit expensive expressions. The rationale is that
3583 when someone writes a code like
3585 while (n > 45) n -= 45;
3587 he probably knows that n is not large, and does not want it
3588 to be turned into n %= 45. */
3589 || expression_expensive_p (def))
3591 if (dump_file && (dump_flags & TDF_DETAILS))
3593 fprintf (dump_file, "not replacing:\n ");
3594 print_gimple_stmt (dump_file, phi, 0);
3595 fprintf (dump_file, "\n");
3597 gsi_next (&psi);
3598 continue;
3601 /* Eliminate the PHI node and replace it by a computation outside
3602 the loop. */
3603 if (dump_file)
3605 fprintf (dump_file, "\nfinal value replacement:\n ");
3606 print_gimple_stmt (dump_file, phi, 0);
3607 fprintf (dump_file, " with\n ");
3609 def = unshare_expr (def);
3610 remove_phi_node (&psi, false);
3612 /* If def's type has undefined overflow and there were folded
3613 casts, rewrite all stmts added for def into arithmetics
3614 with defined overflow behavior. */
3615 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3616 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3618 gimple_seq stmts;
3619 gimple_stmt_iterator gsi2;
3620 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3621 gsi2 = gsi_start (stmts);
3622 while (!gsi_end_p (gsi2))
3624 gimple *stmt = gsi_stmt (gsi2);
3625 gimple_stmt_iterator gsi3 = gsi2;
3626 gsi_next (&gsi2);
3627 gsi_remove (&gsi3, false);
3628 if (is_gimple_assign (stmt)
3629 && arith_code_with_undefined_signed_overflow
3630 (gimple_assign_rhs_code (stmt)))
3631 gsi_insert_seq_before (&gsi,
3632 rewrite_to_defined_overflow (stmt),
3633 GSI_SAME_STMT);
3634 else
3635 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3638 else
3639 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3640 true, GSI_SAME_STMT);
3642 gassign *ass = gimple_build_assign (rslt, def);
3643 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3644 if (dump_file)
3646 print_gimple_stmt (dump_file, ass, 0);
3647 fprintf (dump_file, "\n");
3652 /* Replace ssa names for that scev can prove they are constant by the
3653 appropriate constants. Also perform final value replacement in loops,
3654 in case the replacement expressions are cheap.
3656 We only consider SSA names defined by phi nodes; rest is left to the
3657 ordinary constant propagation pass. */
3659 unsigned int
3660 scev_const_prop (void)
3662 basic_block bb;
3663 tree name, type, ev;
3664 gphi *phi;
3665 struct loop *loop;
3666 bitmap ssa_names_to_remove = NULL;
3667 unsigned i;
3668 gphi_iterator psi;
3670 if (number_of_loops (cfun) <= 1)
3671 return 0;
3673 FOR_EACH_BB_FN (bb, cfun)
3675 loop = bb->loop_father;
3677 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3679 phi = psi.phi ();
3680 name = PHI_RESULT (phi);
3682 if (virtual_operand_p (name))
3683 continue;
3685 type = TREE_TYPE (name);
3687 if (!POINTER_TYPE_P (type)
3688 && !INTEGRAL_TYPE_P (type))
3689 continue;
3691 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3692 NULL);
3693 if (!is_gimple_min_invariant (ev)
3694 || !may_propagate_copy (name, ev))
3695 continue;
3697 /* Replace the uses of the name. */
3698 if (name != ev)
3700 if (dump_file && (dump_flags & TDF_DETAILS))
3702 fprintf (dump_file, "Replacing uses of: ");
3703 print_generic_expr (dump_file, name);
3704 fprintf (dump_file, " with: ");
3705 print_generic_expr (dump_file, ev);
3706 fprintf (dump_file, "\n");
3708 replace_uses_by (name, ev);
3711 if (!ssa_names_to_remove)
3712 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3713 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3717 /* Remove the ssa names that were replaced by constants. We do not
3718 remove them directly in the previous cycle, since this
3719 invalidates scev cache. */
3720 if (ssa_names_to_remove)
3722 bitmap_iterator bi;
3724 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3726 gimple_stmt_iterator psi;
3727 name = ssa_name (i);
3728 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3730 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3731 psi = gsi_for_stmt (phi);
3732 remove_phi_node (&psi, true);
3735 BITMAP_FREE (ssa_names_to_remove);
3736 scev_reset ();
3739 /* Now the regular final value replacement. */
3740 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3741 final_value_replacement_loop (loop);
3743 return 0;
3746 #include "gt-tree-scalar-evolution.h"