* sr.po: Update.
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobfdd5da0589a86c0405db79655a205f08f9cbe801
1 /* Scalar evolution detector.
2 Copyright (C) 2003-2016 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"
284 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
285 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
286 tree var);
288 /* The cached information about an SSA name with version NAME_VERSION,
289 claiming that below basic block with index INSTANTIATED_BELOW, the
290 value of the SSA name can be expressed as CHREC. */
292 struct GTY((for_user)) scev_info_str {
293 unsigned int name_version;
294 int instantiated_below;
295 tree chrec;
298 /* Counters for the scev database. */
299 static unsigned nb_set_scev = 0;
300 static unsigned nb_get_scev = 0;
302 /* The following trees are unique elements. Thus the comparison of
303 another element to these elements should be done on the pointer to
304 these trees, and not on their value. */
306 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
307 tree chrec_not_analyzed_yet;
309 /* Reserved to the cases where the analyzer has detected an
310 undecidable property at compile time. */
311 tree chrec_dont_know;
313 /* When the analyzer has detected that a property will never
314 happen, then it qualifies it with chrec_known. */
315 tree chrec_known;
317 struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
319 static hashval_t hash (scev_info_str *i);
320 static bool equal (const scev_info_str *a, const scev_info_str *b);
323 static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
326 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
328 static inline struct scev_info_str *
329 new_scev_info_str (basic_block instantiated_below, tree var)
331 struct scev_info_str *res;
333 res = ggc_alloc<scev_info_str> ();
334 res->name_version = SSA_NAME_VERSION (var);
335 res->chrec = chrec_not_analyzed_yet;
336 res->instantiated_below = instantiated_below->index;
338 return res;
341 /* Computes a hash function for database element ELT. */
343 hashval_t
344 scev_info_hasher::hash (scev_info_str *elt)
346 return elt->name_version ^ elt->instantiated_below;
349 /* Compares database elements E1 and E2. */
351 bool
352 scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
354 return (elt1->name_version == elt2->name_version
355 && elt1->instantiated_below == elt2->instantiated_below);
358 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
359 A first query on VAR returns chrec_not_analyzed_yet. */
361 static tree *
362 find_var_scev_info (basic_block instantiated_below, tree var)
364 struct scev_info_str *res;
365 struct scev_info_str tmp;
367 tmp.name_version = SSA_NAME_VERSION (var);
368 tmp.instantiated_below = instantiated_below->index;
369 scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
371 if (!*slot)
372 *slot = new_scev_info_str (instantiated_below, var);
373 res = *slot;
375 return &res->chrec;
378 /* Return true when CHREC contains symbolic names defined in
379 LOOP_NB. */
381 bool
382 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
384 int i, n;
386 if (chrec == NULL_TREE)
387 return false;
389 if (is_gimple_min_invariant (chrec))
390 return false;
392 if (TREE_CODE (chrec) == SSA_NAME)
394 gimple *def;
395 loop_p def_loop, loop;
397 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
398 return false;
400 def = SSA_NAME_DEF_STMT (chrec);
401 def_loop = loop_containing_stmt (def);
402 loop = get_loop (cfun, loop_nb);
404 if (def_loop == NULL)
405 return false;
407 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
408 return true;
410 return false;
413 n = TREE_OPERAND_LENGTH (chrec);
414 for (i = 0; i < n; i++)
415 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
416 loop_nb))
417 return true;
418 return false;
421 /* Return true when PHI is a loop-phi-node. */
423 static bool
424 loop_phi_node_p (gimple *phi)
426 /* The implementation of this function is based on the following
427 property: "all the loop-phi-nodes of a loop are contained in the
428 loop's header basic block". */
430 return loop_containing_stmt (phi)->header == gimple_bb (phi);
433 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
434 In general, in the case of multivariate evolutions we want to get
435 the evolution in different loops. LOOP specifies the level for
436 which to get the evolution.
438 Example:
440 | for (j = 0; j < 100; j++)
442 | for (k = 0; k < 100; k++)
444 | i = k + j; - Here the value of i is a function of j, k.
446 | ... = i - Here the value of i is a function of j.
448 | ... = i - Here the value of i is a scalar.
450 Example:
452 | i_0 = ...
453 | loop_1 10 times
454 | i_1 = phi (i_0, i_2)
455 | i_2 = i_1 + 2
456 | endloop
458 This loop has the same effect as:
459 LOOP_1 has the same effect as:
461 | i_1 = i_0 + 20
463 The overall effect of the loop, "i_0 + 20" in the previous example,
464 is obtained by passing in the parameters: LOOP = 1,
465 EVOLUTION_FN = {i_0, +, 2}_1.
468 tree
469 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
471 bool val = false;
473 if (evolution_fn == chrec_dont_know)
474 return chrec_dont_know;
476 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
478 struct loop *inner_loop = get_chrec_loop (evolution_fn);
480 if (inner_loop == loop
481 || flow_loop_nested_p (loop, inner_loop))
483 tree nb_iter = number_of_latch_executions (inner_loop);
485 if (nb_iter == chrec_dont_know)
486 return chrec_dont_know;
487 else
489 tree res;
491 /* evolution_fn is the evolution function in LOOP. Get
492 its value in the nb_iter-th iteration. */
493 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
495 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
496 res = instantiate_parameters (loop, res);
498 /* Continue the computation until ending on a parent of LOOP. */
499 return compute_overall_effect_of_inner_loop (loop, res);
502 else
503 return evolution_fn;
506 /* If the evolution function is an invariant, there is nothing to do. */
507 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
508 return evolution_fn;
510 else
511 return chrec_dont_know;
514 /* Associate CHREC to SCALAR. */
516 static void
517 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
519 tree *scalar_info;
521 if (TREE_CODE (scalar) != SSA_NAME)
522 return;
524 scalar_info = find_var_scev_info (instantiated_below, scalar);
526 if (dump_file)
528 if (dump_flags & TDF_SCEV)
530 fprintf (dump_file, "(set_scalar_evolution \n");
531 fprintf (dump_file, " instantiated_below = %d \n",
532 instantiated_below->index);
533 fprintf (dump_file, " (scalar = ");
534 print_generic_expr (dump_file, scalar, 0);
535 fprintf (dump_file, ")\n (scalar_evolution = ");
536 print_generic_expr (dump_file, chrec, 0);
537 fprintf (dump_file, "))\n");
539 if (dump_flags & TDF_STATS)
540 nb_set_scev++;
543 *scalar_info = chrec;
546 /* Retrieve the chrec associated to SCALAR instantiated below
547 INSTANTIATED_BELOW block. */
549 static tree
550 get_scalar_evolution (basic_block instantiated_below, tree scalar)
552 tree res;
554 if (dump_file)
556 if (dump_flags & TDF_SCEV)
558 fprintf (dump_file, "(get_scalar_evolution \n");
559 fprintf (dump_file, " (scalar = ");
560 print_generic_expr (dump_file, scalar, 0);
561 fprintf (dump_file, ")\n");
563 if (dump_flags & TDF_STATS)
564 nb_get_scev++;
567 switch (TREE_CODE (scalar))
569 case SSA_NAME:
570 res = *find_var_scev_info (instantiated_below, scalar);
571 break;
573 case REAL_CST:
574 case FIXED_CST:
575 case INTEGER_CST:
576 res = scalar;
577 break;
579 default:
580 res = chrec_not_analyzed_yet;
581 break;
584 if (dump_file && (dump_flags & TDF_SCEV))
586 fprintf (dump_file, " (scalar_evolution = ");
587 print_generic_expr (dump_file, res, 0);
588 fprintf (dump_file, "))\n");
591 return res;
594 /* Helper function for add_to_evolution. Returns the evolution
595 function for an assignment of the form "a = b + c", where "a" and
596 "b" are on the strongly connected component. CHREC_BEFORE is the
597 information that we already have collected up to this point.
598 TO_ADD is the evolution of "c".
600 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
601 evolution the expression TO_ADD, otherwise construct an evolution
602 part for this loop. */
604 static tree
605 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
606 gimple *at_stmt)
608 tree type, left, right;
609 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
611 switch (TREE_CODE (chrec_before))
613 case POLYNOMIAL_CHREC:
614 chloop = get_chrec_loop (chrec_before);
615 if (chloop == loop
616 || flow_loop_nested_p (chloop, loop))
618 unsigned var;
620 type = chrec_type (chrec_before);
622 /* When there is no evolution part in this loop, build it. */
623 if (chloop != loop)
625 var = loop_nb;
626 left = chrec_before;
627 right = SCALAR_FLOAT_TYPE_P (type)
628 ? build_real (type, dconst0)
629 : build_int_cst (type, 0);
631 else
633 var = CHREC_VARIABLE (chrec_before);
634 left = CHREC_LEFT (chrec_before);
635 right = CHREC_RIGHT (chrec_before);
638 to_add = chrec_convert (type, to_add, at_stmt);
639 right = chrec_convert_rhs (type, right, at_stmt);
640 right = chrec_fold_plus (chrec_type (right), right, to_add);
641 return build_polynomial_chrec (var, left, right);
643 else
645 gcc_assert (flow_loop_nested_p (loop, chloop));
647 /* Search the evolution in LOOP_NB. */
648 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
649 to_add, at_stmt);
650 right = CHREC_RIGHT (chrec_before);
651 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
652 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
653 left, right);
656 default:
657 /* These nodes do not depend on a loop. */
658 if (chrec_before == chrec_dont_know)
659 return chrec_dont_know;
661 left = chrec_before;
662 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
663 return build_polynomial_chrec (loop_nb, left, right);
667 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
668 of LOOP_NB.
670 Description (provided for completeness, for those who read code in
671 a plane, and for my poor 62 bytes brain that would have forgotten
672 all this in the next two or three months):
674 The algorithm of translation of programs from the SSA representation
675 into the chrecs syntax is based on a pattern matching. After having
676 reconstructed the overall tree expression for a loop, there are only
677 two cases that can arise:
679 1. a = loop-phi (init, a + expr)
680 2. a = loop-phi (init, expr)
682 where EXPR is either a scalar constant with respect to the analyzed
683 loop (this is a degree 0 polynomial), or an expression containing
684 other loop-phi definitions (these are higher degree polynomials).
686 Examples:
689 | init = ...
690 | loop_1
691 | a = phi (init, a + 5)
692 | endloop
695 | inita = ...
696 | initb = ...
697 | loop_1
698 | a = phi (inita, 2 * b + 3)
699 | b = phi (initb, b + 1)
700 | endloop
702 For the first case, the semantics of the SSA representation is:
704 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
706 that is, there is a loop index "x" that determines the scalar value
707 of the variable during the loop execution. During the first
708 iteration, the value is that of the initial condition INIT, while
709 during the subsequent iterations, it is the sum of the initial
710 condition with the sum of all the values of EXPR from the initial
711 iteration to the before last considered iteration.
713 For the second case, the semantics of the SSA program is:
715 | a (x) = init, if x = 0;
716 | expr (x - 1), otherwise.
718 The second case corresponds to the PEELED_CHREC, whose syntax is
719 close to the syntax of a loop-phi-node:
721 | phi (init, expr) vs. (init, expr)_x
723 The proof of the translation algorithm for the first case is a
724 proof by structural induction based on the degree of EXPR.
726 Degree 0:
727 When EXPR is a constant with respect to the analyzed loop, or in
728 other words when EXPR is a polynomial of degree 0, the evolution of
729 the variable A in the loop is an affine function with an initial
730 condition INIT, and a step EXPR. In order to show this, we start
731 from the semantics of the SSA representation:
733 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
735 and since "expr (j)" is a constant with respect to "j",
737 f (x) = init + x * expr
739 Finally, based on the semantics of the pure sum chrecs, by
740 identification we get the corresponding chrecs syntax:
742 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
743 f (x) -> {init, +, expr}_x
745 Higher degree:
746 Suppose that EXPR is a polynomial of degree N with respect to the
747 analyzed loop_x for which we have already determined that it is
748 written under the chrecs syntax:
750 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
752 We start from the semantics of the SSA program:
754 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
756 | f (x) = init + \sum_{j = 0}^{x - 1}
757 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
759 | f (x) = init + \sum_{j = 0}^{x - 1}
760 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
762 | f (x) = init + \sum_{k = 0}^{n - 1}
763 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
765 | f (x) = init + \sum_{k = 0}^{n - 1}
766 | (b_k * \binom{x}{k + 1})
768 | f (x) = init + b_0 * \binom{x}{1} + ...
769 | + b_{n-1} * \binom{x}{n}
771 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
772 | + b_{n-1} * \binom{x}{n}
775 And finally from the definition of the chrecs syntax, we identify:
776 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
778 This shows the mechanism that stands behind the add_to_evolution
779 function. An important point is that the use of symbolic
780 parameters avoids the need of an analysis schedule.
782 Example:
784 | inita = ...
785 | initb = ...
786 | loop_1
787 | a = phi (inita, a + 2 + b)
788 | b = phi (initb, b + 1)
789 | endloop
791 When analyzing "a", the algorithm keeps "b" symbolically:
793 | a -> {inita, +, 2 + b}_1
795 Then, after instantiation, the analyzer ends on the evolution:
797 | a -> {inita, +, 2 + initb, +, 1}_1
801 static tree
802 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
803 tree to_add, gimple *at_stmt)
805 tree type = chrec_type (to_add);
806 tree res = NULL_TREE;
808 if (to_add == NULL_TREE)
809 return chrec_before;
811 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
812 instantiated at this point. */
813 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
814 /* This should not happen. */
815 return chrec_dont_know;
817 if (dump_file && (dump_flags & TDF_SCEV))
819 fprintf (dump_file, "(add_to_evolution \n");
820 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
821 fprintf (dump_file, " (chrec_before = ");
822 print_generic_expr (dump_file, chrec_before, 0);
823 fprintf (dump_file, ")\n (to_add = ");
824 print_generic_expr (dump_file, to_add, 0);
825 fprintf (dump_file, ")\n");
828 if (code == MINUS_EXPR)
829 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
830 ? build_real (type, dconstm1)
831 : build_int_cst_type (type, -1));
833 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
835 if (dump_file && (dump_flags & TDF_SCEV))
837 fprintf (dump_file, " (res = ");
838 print_generic_expr (dump_file, res, 0);
839 fprintf (dump_file, "))\n");
842 return res;
847 /* This section selects the loops that will be good candidates for the
848 scalar evolution analysis. For the moment, greedily select all the
849 loop nests we could analyze. */
851 /* For a loop with a single exit edge, return the COND_EXPR that
852 guards the exit edge. If the expression is too difficult to
853 analyze, then give up. */
855 gcond *
856 get_loop_exit_condition (const struct loop *loop)
858 gcond *res = NULL;
859 edge exit_edge = single_exit (loop);
861 if (dump_file && (dump_flags & TDF_SCEV))
862 fprintf (dump_file, "(get_loop_exit_condition \n ");
864 if (exit_edge)
866 gimple *stmt;
868 stmt = last_stmt (exit_edge->src);
869 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
870 res = cond_stmt;
873 if (dump_file && (dump_flags & TDF_SCEV))
875 print_gimple_stmt (dump_file, res, 0, 0);
876 fprintf (dump_file, ")\n");
879 return res;
883 /* Depth first search algorithm. */
885 enum t_bool {
886 t_false,
887 t_true,
888 t_dont_know
892 static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *,
893 tree *, int);
895 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
896 Return true if the strongly connected component has been found. */
898 static t_bool
899 follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt,
900 tree type, tree rhs0, enum tree_code code, tree rhs1,
901 gphi *halting_phi, tree *evolution_of_loop,
902 int limit)
904 t_bool res = t_false;
905 tree evol;
907 switch (code)
909 case POINTER_PLUS_EXPR:
910 case PLUS_EXPR:
911 if (TREE_CODE (rhs0) == SSA_NAME)
913 if (TREE_CODE (rhs1) == SSA_NAME)
915 /* Match an assignment under the form:
916 "a = b + c". */
918 /* We want only assignments of form "name + name" contribute to
919 LIMIT, as the other cases do not necessarily contribute to
920 the complexity of the expression. */
921 limit++;
923 evol = *evolution_of_loop;
924 evol = add_to_evolution
925 (loop->num,
926 chrec_convert (type, evol, at_stmt),
927 code, rhs1, at_stmt);
928 res = follow_ssa_edge
929 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
930 if (res == t_true)
931 *evolution_of_loop = evol;
932 else if (res == t_false)
934 *evolution_of_loop = add_to_evolution
935 (loop->num,
936 chrec_convert (type, *evolution_of_loop, at_stmt),
937 code, rhs0, at_stmt);
938 res = follow_ssa_edge
939 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
940 evolution_of_loop, limit);
941 if (res == t_true)
943 else if (res == t_dont_know)
944 *evolution_of_loop = chrec_dont_know;
947 else if (res == t_dont_know)
948 *evolution_of_loop = chrec_dont_know;
951 else
953 /* Match an assignment under the form:
954 "a = b + ...". */
955 *evolution_of_loop = add_to_evolution
956 (loop->num, chrec_convert (type, *evolution_of_loop,
957 at_stmt),
958 code, rhs1, at_stmt);
959 res = follow_ssa_edge
960 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
961 evolution_of_loop, limit);
962 if (res == t_true)
964 else if (res == t_dont_know)
965 *evolution_of_loop = chrec_dont_know;
969 else if (TREE_CODE (rhs1) == SSA_NAME)
971 /* Match an assignment under the form:
972 "a = ... + c". */
973 *evolution_of_loop = add_to_evolution
974 (loop->num, chrec_convert (type, *evolution_of_loop,
975 at_stmt),
976 code, rhs0, at_stmt);
977 res = follow_ssa_edge
978 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
979 evolution_of_loop, limit);
980 if (res == t_true)
982 else if (res == t_dont_know)
983 *evolution_of_loop = chrec_dont_know;
986 else
987 /* Otherwise, match an assignment under the form:
988 "a = ... + ...". */
989 /* And there is nothing to do. */
990 res = t_false;
991 break;
993 case MINUS_EXPR:
994 /* This case is under the form "opnd0 = rhs0 - rhs1". */
995 if (TREE_CODE (rhs0) == SSA_NAME)
997 /* Match an assignment under the form:
998 "a = b - ...". */
1000 /* We want only assignments of form "name - name" contribute to
1001 LIMIT, as the other cases do not necessarily contribute to
1002 the complexity of the expression. */
1003 if (TREE_CODE (rhs1) == SSA_NAME)
1004 limit++;
1006 *evolution_of_loop = add_to_evolution
1007 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1008 MINUS_EXPR, rhs1, at_stmt);
1009 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1010 evolution_of_loop, limit);
1011 if (res == t_true)
1013 else if (res == t_dont_know)
1014 *evolution_of_loop = chrec_dont_know;
1016 else
1017 /* Otherwise, match an assignment under the form:
1018 "a = ... - ...". */
1019 /* And there is nothing to do. */
1020 res = t_false;
1021 break;
1023 default:
1024 res = t_false;
1027 return res;
1030 /* Follow the ssa edge into the expression EXPR.
1031 Return true if the strongly connected component has been found. */
1033 static t_bool
1034 follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr,
1035 gphi *halting_phi, tree *evolution_of_loop,
1036 int limit)
1038 enum tree_code code = TREE_CODE (expr);
1039 tree type = TREE_TYPE (expr), rhs0, rhs1;
1040 t_bool res;
1042 /* The EXPR is one of the following cases:
1043 - an SSA_NAME,
1044 - an INTEGER_CST,
1045 - a PLUS_EXPR,
1046 - a POINTER_PLUS_EXPR,
1047 - a MINUS_EXPR,
1048 - an ASSERT_EXPR,
1049 - other cases are not yet handled. */
1051 switch (code)
1053 CASE_CONVERT:
1054 /* This assignment is under the form "a_1 = (cast) rhs. */
1055 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1056 halting_phi, evolution_of_loop, limit);
1057 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1058 break;
1060 case INTEGER_CST:
1061 /* This assignment is under the form "a_1 = 7". */
1062 res = t_false;
1063 break;
1065 case SSA_NAME:
1066 /* This assignment is under the form: "a_1 = b_2". */
1067 res = follow_ssa_edge
1068 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1069 break;
1071 case POINTER_PLUS_EXPR:
1072 case PLUS_EXPR:
1073 case MINUS_EXPR:
1074 /* This case is under the form "rhs0 +- rhs1". */
1075 rhs0 = TREE_OPERAND (expr, 0);
1076 rhs1 = TREE_OPERAND (expr, 1);
1077 type = TREE_TYPE (rhs0);
1078 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1079 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1080 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1081 halting_phi, evolution_of_loop, limit);
1082 break;
1084 case ADDR_EXPR:
1085 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1086 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1088 expr = TREE_OPERAND (expr, 0);
1089 rhs0 = TREE_OPERAND (expr, 0);
1090 rhs1 = TREE_OPERAND (expr, 1);
1091 type = TREE_TYPE (rhs0);
1092 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1093 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1094 res = follow_ssa_edge_binary (loop, at_stmt, type,
1095 rhs0, POINTER_PLUS_EXPR, rhs1,
1096 halting_phi, evolution_of_loop, limit);
1098 else
1099 res = t_false;
1100 break;
1102 case ASSERT_EXPR:
1103 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1104 It must be handled as a copy assignment of the form a_1 = a_2. */
1105 rhs0 = ASSERT_EXPR_VAR (expr);
1106 if (TREE_CODE (rhs0) == SSA_NAME)
1107 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1108 halting_phi, evolution_of_loop, limit);
1109 else
1110 res = t_false;
1111 break;
1113 default:
1114 res = t_false;
1115 break;
1118 return res;
1121 /* Follow the ssa edge into the right hand side of an assignment STMT.
1122 Return true if the strongly connected component has been found. */
1124 static t_bool
1125 follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt,
1126 gphi *halting_phi, tree *evolution_of_loop,
1127 int limit)
1129 enum tree_code code = gimple_assign_rhs_code (stmt);
1130 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1131 t_bool res;
1133 switch (code)
1135 CASE_CONVERT:
1136 /* This assignment is under the form "a_1 = (cast) rhs. */
1137 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1138 halting_phi, evolution_of_loop, limit);
1139 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1140 break;
1142 case POINTER_PLUS_EXPR:
1143 case PLUS_EXPR:
1144 case MINUS_EXPR:
1145 rhs1 = gimple_assign_rhs1 (stmt);
1146 rhs2 = gimple_assign_rhs2 (stmt);
1147 type = TREE_TYPE (rhs1);
1148 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1149 halting_phi, evolution_of_loop, limit);
1150 break;
1152 default:
1153 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1154 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1155 halting_phi, evolution_of_loop, limit);
1156 else
1157 res = t_false;
1158 break;
1161 return res;
1164 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1166 static bool
1167 backedge_phi_arg_p (gphi *phi, int i)
1169 const_edge e = gimple_phi_arg_edge (phi, i);
1171 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1172 about updating it anywhere, and this should work as well most of the
1173 time. */
1174 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1175 return true;
1177 return false;
1180 /* Helper function for one branch of the condition-phi-node. Return
1181 true if the strongly connected component has been found following
1182 this path. */
1184 static inline t_bool
1185 follow_ssa_edge_in_condition_phi_branch (int i,
1186 struct loop *loop,
1187 gphi *condition_phi,
1188 gphi *halting_phi,
1189 tree *evolution_of_branch,
1190 tree init_cond, int limit)
1192 tree branch = PHI_ARG_DEF (condition_phi, i);
1193 *evolution_of_branch = chrec_dont_know;
1195 /* Do not follow back edges (they must belong to an irreducible loop, which
1196 we really do not want to worry about). */
1197 if (backedge_phi_arg_p (condition_phi, i))
1198 return t_false;
1200 if (TREE_CODE (branch) == SSA_NAME)
1202 *evolution_of_branch = init_cond;
1203 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1204 evolution_of_branch, limit);
1207 /* This case occurs when one of the condition branches sets
1208 the variable to a constant: i.e. a phi-node like
1209 "a_2 = PHI <a_7(5), 2(6)>;".
1211 FIXME: This case have to be refined correctly:
1212 in some cases it is possible to say something better than
1213 chrec_dont_know, for example using a wrap-around notation. */
1214 return t_false;
1217 /* This function merges the branches of a condition-phi-node in a
1218 loop. */
1220 static t_bool
1221 follow_ssa_edge_in_condition_phi (struct loop *loop,
1222 gphi *condition_phi,
1223 gphi *halting_phi,
1224 tree *evolution_of_loop, int limit)
1226 int i, n;
1227 tree init = *evolution_of_loop;
1228 tree evolution_of_branch;
1229 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1230 halting_phi,
1231 &evolution_of_branch,
1232 init, limit);
1233 if (res == t_false || res == t_dont_know)
1234 return res;
1236 *evolution_of_loop = evolution_of_branch;
1238 n = gimple_phi_num_args (condition_phi);
1239 for (i = 1; i < n; i++)
1241 /* Quickly give up when the evolution of one of the branches is
1242 not known. */
1243 if (*evolution_of_loop == chrec_dont_know)
1244 return t_true;
1246 /* Increase the limit by the PHI argument number to avoid exponential
1247 time and memory complexity. */
1248 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1249 halting_phi,
1250 &evolution_of_branch,
1251 init, limit + i);
1252 if (res == t_false || res == t_dont_know)
1253 return res;
1255 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1256 evolution_of_branch);
1259 return t_true;
1262 /* Follow an SSA edge in an inner loop. It computes the overall
1263 effect of the loop, and following the symbolic initial conditions,
1264 it follows the edges in the parent loop. The inner loop is
1265 considered as a single statement. */
1267 static t_bool
1268 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1269 gphi *loop_phi_node,
1270 gphi *halting_phi,
1271 tree *evolution_of_loop, int limit)
1273 struct loop *loop = loop_containing_stmt (loop_phi_node);
1274 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1276 /* Sometimes, the inner loop is too difficult to analyze, and the
1277 result of the analysis is a symbolic parameter. */
1278 if (ev == PHI_RESULT (loop_phi_node))
1280 t_bool res = t_false;
1281 int i, n = gimple_phi_num_args (loop_phi_node);
1283 for (i = 0; i < n; i++)
1285 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1286 basic_block bb;
1288 /* Follow the edges that exit the inner loop. */
1289 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1290 if (!flow_bb_inside_loop_p (loop, bb))
1291 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1292 arg, halting_phi,
1293 evolution_of_loop, limit);
1294 if (res == t_true)
1295 break;
1298 /* If the path crosses this loop-phi, give up. */
1299 if (res == t_true)
1300 *evolution_of_loop = chrec_dont_know;
1302 return res;
1305 /* Otherwise, compute the overall effect of the inner loop. */
1306 ev = compute_overall_effect_of_inner_loop (loop, ev);
1307 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1308 evolution_of_loop, limit);
1311 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1312 path that is analyzed on the return walk. */
1314 static t_bool
1315 follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi,
1316 tree *evolution_of_loop, int limit)
1318 struct loop *def_loop;
1320 if (gimple_nop_p (def))
1321 return t_false;
1323 /* Give up if the path is longer than the MAX that we allow. */
1324 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1325 return t_dont_know;
1327 def_loop = loop_containing_stmt (def);
1329 switch (gimple_code (def))
1331 case GIMPLE_PHI:
1332 if (!loop_phi_node_p (def))
1333 /* DEF is a condition-phi-node. Follow the branches, and
1334 record their evolutions. Finally, merge the collected
1335 information and set the approximation to the main
1336 variable. */
1337 return follow_ssa_edge_in_condition_phi
1338 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1339 limit);
1341 /* When the analyzed phi is the halting_phi, the
1342 depth-first search is over: we have found a path from
1343 the halting_phi to itself in the loop. */
1344 if (def == halting_phi)
1345 return t_true;
1347 /* Otherwise, the evolution of the HALTING_PHI depends
1348 on the evolution of another loop-phi-node, i.e. the
1349 evolution function is a higher degree polynomial. */
1350 if (def_loop == loop)
1351 return t_false;
1353 /* Inner loop. */
1354 if (flow_loop_nested_p (loop, def_loop))
1355 return follow_ssa_edge_inner_loop_phi
1356 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1357 limit + 1);
1359 /* Outer loop. */
1360 return t_false;
1362 case GIMPLE_ASSIGN:
1363 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1364 evolution_of_loop, limit);
1366 default:
1367 /* At this level of abstraction, the program is just a set
1368 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1369 other node to be handled. */
1370 return t_false;
1375 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1376 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1378 # i_17 = PHI <i_13(5), 0(3)>
1379 # _20 = PHI <_5(5), start_4(D)(3)>
1381 i_13 = i_17 + 1;
1382 _5 = start_4(D) + i_13;
1384 Though variable _20 appears as a PEELED_CHREC in the form of
1385 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1387 See PR41488. */
1389 static tree
1390 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1392 aff_tree aff1, aff2;
1393 tree ev, left, right, type, step_val;
1394 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1396 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1397 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1398 return chrec_dont_know;
1400 left = CHREC_LEFT (ev);
1401 right = CHREC_RIGHT (ev);
1402 type = TREE_TYPE (left);
1403 step_val = chrec_fold_plus (type, init_cond, right);
1405 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1406 if "left" equals to "init + right". */
1407 if (operand_equal_p (left, step_val, 0))
1409 if (dump_file && (dump_flags & TDF_SCEV))
1410 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1412 return build_polynomial_chrec (loop->num, init_cond, right);
1415 /* Try harder to check if they are equal. */
1416 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1417 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1418 free_affine_expand_cache (&peeled_chrec_map);
1419 aff_combination_scale (&aff2, -1);
1420 aff_combination_add (&aff1, &aff2);
1422 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1423 if "left" equals to "init + right". */
1424 if (aff_combination_zero_p (&aff1))
1426 if (dump_file && (dump_flags & TDF_SCEV))
1427 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1429 return build_polynomial_chrec (loop->num, init_cond, right);
1431 return chrec_dont_know;
1434 /* Given a LOOP_PHI_NODE, this function determines the evolution
1435 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1437 static tree
1438 analyze_evolution_in_loop (gphi *loop_phi_node,
1439 tree init_cond)
1441 int i, n = gimple_phi_num_args (loop_phi_node);
1442 tree evolution_function = chrec_not_analyzed_yet;
1443 struct loop *loop = loop_containing_stmt (loop_phi_node);
1444 basic_block bb;
1445 static bool simplify_peeled_chrec_p = true;
1447 if (dump_file && (dump_flags & TDF_SCEV))
1449 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1450 fprintf (dump_file, " (loop_phi_node = ");
1451 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1452 fprintf (dump_file, ")\n");
1455 for (i = 0; i < n; i++)
1457 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1458 gimple *ssa_chain;
1459 tree ev_fn;
1460 t_bool res;
1462 /* Select the edges that enter the loop body. */
1463 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1464 if (!flow_bb_inside_loop_p (loop, bb))
1465 continue;
1467 if (TREE_CODE (arg) == SSA_NAME)
1469 bool val = false;
1471 ssa_chain = SSA_NAME_DEF_STMT (arg);
1473 /* Pass in the initial condition to the follow edge function. */
1474 ev_fn = init_cond;
1475 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1477 /* If ev_fn has no evolution in the inner loop, and the
1478 init_cond is not equal to ev_fn, then we have an
1479 ambiguity between two possible values, as we cannot know
1480 the number of iterations at this point. */
1481 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1482 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1483 && !operand_equal_p (init_cond, ev_fn, 0))
1484 ev_fn = chrec_dont_know;
1486 else
1487 res = t_false;
1489 /* When it is impossible to go back on the same
1490 loop_phi_node by following the ssa edges, the
1491 evolution is represented by a peeled chrec, i.e. the
1492 first iteration, EV_FN has the value INIT_COND, then
1493 all the other iterations it has the value of ARG.
1494 For the moment, PEELED_CHREC nodes are not built. */
1495 if (res != t_true)
1497 ev_fn = chrec_dont_know;
1498 /* Try to recognize POLYNOMIAL_CHREC which appears in
1499 the form of PEELED_CHREC, but guard the process with
1500 a bool variable to keep the analyzer from infinite
1501 recurrence for real PEELED_RECs. */
1502 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1504 simplify_peeled_chrec_p = false;
1505 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1506 simplify_peeled_chrec_p = true;
1510 /* When there are multiple back edges of the loop (which in fact never
1511 happens currently, but nevertheless), merge their evolutions. */
1512 evolution_function = chrec_merge (evolution_function, ev_fn);
1515 if (dump_file && (dump_flags & TDF_SCEV))
1517 fprintf (dump_file, " (evolution_function = ");
1518 print_generic_expr (dump_file, evolution_function, 0);
1519 fprintf (dump_file, "))\n");
1522 return evolution_function;
1525 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1526 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1528 static tree
1529 follow_copies_to_constant (tree var)
1531 tree res = var;
1532 while (TREE_CODE (res) == SSA_NAME)
1534 gimple *def = SSA_NAME_DEF_STMT (res);
1535 if (gphi *phi = dyn_cast <gphi *> (def))
1537 if (tree rhs = degenerate_phi_result (phi))
1538 res = rhs;
1539 else
1540 break;
1542 else if (gimple_assign_single_p (def))
1543 /* Will exit loop if not an SSA_NAME. */
1544 res = gimple_assign_rhs1 (def);
1545 else
1546 break;
1548 if (CONSTANT_CLASS_P (res))
1549 return res;
1550 return var;
1553 /* Given a loop-phi-node, return the initial conditions of the
1554 variable on entry of the loop. When the CCP has propagated
1555 constants into the loop-phi-node, the initial condition is
1556 instantiated, otherwise the initial condition is kept symbolic.
1557 This analyzer does not analyze the evolution outside the current
1558 loop, and leaves this task to the on-demand tree reconstructor. */
1560 static tree
1561 analyze_initial_condition (gphi *loop_phi_node)
1563 int i, n;
1564 tree init_cond = chrec_not_analyzed_yet;
1565 struct loop *loop = loop_containing_stmt (loop_phi_node);
1567 if (dump_file && (dump_flags & TDF_SCEV))
1569 fprintf (dump_file, "(analyze_initial_condition \n");
1570 fprintf (dump_file, " (loop_phi_node = \n");
1571 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1572 fprintf (dump_file, ")\n");
1575 n = gimple_phi_num_args (loop_phi_node);
1576 for (i = 0; i < n; i++)
1578 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1579 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1581 /* When the branch is oriented to the loop's body, it does
1582 not contribute to the initial condition. */
1583 if (flow_bb_inside_loop_p (loop, bb))
1584 continue;
1586 if (init_cond == chrec_not_analyzed_yet)
1588 init_cond = branch;
1589 continue;
1592 if (TREE_CODE (branch) == SSA_NAME)
1594 init_cond = chrec_dont_know;
1595 break;
1598 init_cond = chrec_merge (init_cond, branch);
1601 /* Ooops -- a loop without an entry??? */
1602 if (init_cond == chrec_not_analyzed_yet)
1603 init_cond = chrec_dont_know;
1605 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1606 to not miss important early loop unrollings. */
1607 init_cond = follow_copies_to_constant (init_cond);
1609 if (dump_file && (dump_flags & TDF_SCEV))
1611 fprintf (dump_file, " (init_cond = ");
1612 print_generic_expr (dump_file, init_cond, 0);
1613 fprintf (dump_file, "))\n");
1616 return init_cond;
1619 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1621 static tree
1622 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1624 tree res;
1625 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1626 tree init_cond;
1628 if (phi_loop != loop)
1630 struct loop *subloop;
1631 tree evolution_fn = analyze_scalar_evolution
1632 (phi_loop, PHI_RESULT (loop_phi_node));
1634 /* Dive one level deeper. */
1635 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1637 /* Interpret the subloop. */
1638 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1639 return res;
1642 /* Otherwise really interpret the loop phi. */
1643 init_cond = analyze_initial_condition (loop_phi_node);
1644 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1646 /* Verify we maintained the correct initial condition throughout
1647 possible conversions in the SSA chain. */
1648 if (res != chrec_dont_know)
1650 tree new_init = res;
1651 if (CONVERT_EXPR_P (res)
1652 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1653 new_init = fold_convert (TREE_TYPE (res),
1654 CHREC_LEFT (TREE_OPERAND (res, 0)));
1655 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1656 new_init = CHREC_LEFT (res);
1657 STRIP_USELESS_TYPE_CONVERSION (new_init);
1658 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1659 || !operand_equal_p (init_cond, new_init, 0))
1660 return chrec_dont_know;
1663 return res;
1666 /* This function merges the branches of a condition-phi-node,
1667 contained in the outermost loop, and whose arguments are already
1668 analyzed. */
1670 static tree
1671 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1673 int i, n = gimple_phi_num_args (condition_phi);
1674 tree res = chrec_not_analyzed_yet;
1676 for (i = 0; i < n; i++)
1678 tree branch_chrec;
1680 if (backedge_phi_arg_p (condition_phi, i))
1682 res = chrec_dont_know;
1683 break;
1686 branch_chrec = analyze_scalar_evolution
1687 (loop, PHI_ARG_DEF (condition_phi, i));
1689 res = chrec_merge (res, branch_chrec);
1692 return res;
1695 /* Interpret the operation RHS1 OP RHS2. If we didn't
1696 analyze this node before, follow the definitions until ending
1697 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1698 return path, this function propagates evolutions (ala constant copy
1699 propagation). OPND1 is not a GIMPLE expression because we could
1700 analyze the effect of an inner loop: see interpret_loop_phi. */
1702 static tree
1703 interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
1704 tree type, tree rhs1, enum tree_code code, tree rhs2)
1706 tree res, chrec1, chrec2, ctype;
1707 gimple *def;
1709 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1711 if (is_gimple_min_invariant (rhs1))
1712 return chrec_convert (type, rhs1, at_stmt);
1714 if (code == SSA_NAME)
1715 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1716 at_stmt);
1718 if (code == ASSERT_EXPR)
1720 rhs1 = ASSERT_EXPR_VAR (rhs1);
1721 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1722 at_stmt);
1726 switch (code)
1728 case ADDR_EXPR:
1729 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1730 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1732 machine_mode mode;
1733 HOST_WIDE_INT bitsize, bitpos;
1734 int unsignedp, reversep;
1735 int volatilep = 0;
1736 tree base, offset;
1737 tree chrec3;
1738 tree unitpos;
1740 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1741 &bitsize, &bitpos, &offset, &mode,
1742 &unsignedp, &reversep, &volatilep,
1743 false);
1745 if (TREE_CODE (base) == MEM_REF)
1747 rhs2 = TREE_OPERAND (base, 1);
1748 rhs1 = TREE_OPERAND (base, 0);
1750 chrec1 = analyze_scalar_evolution (loop, rhs1);
1751 chrec2 = analyze_scalar_evolution (loop, rhs2);
1752 chrec1 = chrec_convert (type, chrec1, at_stmt);
1753 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1754 chrec1 = instantiate_parameters (loop, chrec1);
1755 chrec2 = instantiate_parameters (loop, chrec2);
1756 res = chrec_fold_plus (type, chrec1, chrec2);
1758 else
1760 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1761 chrec1 = chrec_convert (type, chrec1, at_stmt);
1762 res = chrec1;
1765 if (offset != NULL_TREE)
1767 chrec2 = analyze_scalar_evolution (loop, offset);
1768 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1769 chrec2 = instantiate_parameters (loop, chrec2);
1770 res = chrec_fold_plus (type, res, chrec2);
1773 if (bitpos != 0)
1775 gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
1777 unitpos = size_int (bitpos / BITS_PER_UNIT);
1778 chrec3 = analyze_scalar_evolution (loop, unitpos);
1779 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1780 chrec3 = instantiate_parameters (loop, chrec3);
1781 res = chrec_fold_plus (type, res, chrec3);
1784 else
1785 res = chrec_dont_know;
1786 break;
1788 case POINTER_PLUS_EXPR:
1789 chrec1 = analyze_scalar_evolution (loop, rhs1);
1790 chrec2 = analyze_scalar_evolution (loop, rhs2);
1791 chrec1 = chrec_convert (type, chrec1, at_stmt);
1792 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1793 chrec1 = instantiate_parameters (loop, chrec1);
1794 chrec2 = instantiate_parameters (loop, chrec2);
1795 res = chrec_fold_plus (type, chrec1, chrec2);
1796 break;
1798 case PLUS_EXPR:
1799 chrec1 = analyze_scalar_evolution (loop, rhs1);
1800 chrec2 = analyze_scalar_evolution (loop, rhs2);
1801 ctype = type;
1802 /* When the stmt is conditionally executed re-write the CHREC
1803 into a form that has well-defined behavior on overflow. */
1804 if (at_stmt
1805 && INTEGRAL_TYPE_P (type)
1806 && ! TYPE_OVERFLOW_WRAPS (type)
1807 && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1808 gimple_bb (at_stmt)))
1809 ctype = unsigned_type_for (type);
1810 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1811 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1812 chrec1 = instantiate_parameters (loop, chrec1);
1813 chrec2 = instantiate_parameters (loop, chrec2);
1814 res = chrec_fold_plus (ctype, chrec1, chrec2);
1815 if (type != ctype)
1816 res = chrec_convert (type, res, at_stmt);
1817 break;
1819 case MINUS_EXPR:
1820 chrec1 = analyze_scalar_evolution (loop, rhs1);
1821 chrec2 = analyze_scalar_evolution (loop, rhs2);
1822 ctype = type;
1823 /* When the stmt is conditionally executed re-write the CHREC
1824 into a form that has well-defined behavior on overflow. */
1825 if (at_stmt
1826 && INTEGRAL_TYPE_P (type)
1827 && ! TYPE_OVERFLOW_WRAPS (type)
1828 && ! dominated_by_p (CDI_DOMINATORS,
1829 loop->latch, gimple_bb (at_stmt)))
1830 ctype = unsigned_type_for (type);
1831 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1832 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1833 chrec1 = instantiate_parameters (loop, chrec1);
1834 chrec2 = instantiate_parameters (loop, chrec2);
1835 res = chrec_fold_minus (ctype, chrec1, chrec2);
1836 if (type != ctype)
1837 res = chrec_convert (type, res, at_stmt);
1838 break;
1840 case NEGATE_EXPR:
1841 chrec1 = analyze_scalar_evolution (loop, rhs1);
1842 ctype = type;
1843 /* When the stmt is conditionally executed re-write the CHREC
1844 into a form that has well-defined behavior on overflow. */
1845 if (at_stmt
1846 && INTEGRAL_TYPE_P (type)
1847 && ! TYPE_OVERFLOW_WRAPS (type)
1848 && ! dominated_by_p (CDI_DOMINATORS,
1849 loop->latch, gimple_bb (at_stmt)))
1850 ctype = unsigned_type_for (type);
1851 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1852 /* TYPE may be integer, real or complex, so use fold_convert. */
1853 chrec1 = instantiate_parameters (loop, chrec1);
1854 res = chrec_fold_multiply (ctype, chrec1,
1855 fold_convert (ctype, integer_minus_one_node));
1856 if (type != ctype)
1857 res = chrec_convert (type, res, at_stmt);
1858 break;
1860 case BIT_NOT_EXPR:
1861 /* Handle ~X as -1 - X. */
1862 chrec1 = analyze_scalar_evolution (loop, rhs1);
1863 chrec1 = chrec_convert (type, chrec1, at_stmt);
1864 chrec1 = instantiate_parameters (loop, chrec1);
1865 res = chrec_fold_minus (type,
1866 fold_convert (type, integer_minus_one_node),
1867 chrec1);
1868 break;
1870 case MULT_EXPR:
1871 chrec1 = analyze_scalar_evolution (loop, rhs1);
1872 chrec2 = analyze_scalar_evolution (loop, rhs2);
1873 ctype = type;
1874 /* When the stmt is conditionally executed re-write the CHREC
1875 into a form that has well-defined behavior on overflow. */
1876 if (at_stmt
1877 && INTEGRAL_TYPE_P (type)
1878 && ! TYPE_OVERFLOW_WRAPS (type)
1879 && ! dominated_by_p (CDI_DOMINATORS,
1880 loop->latch, gimple_bb (at_stmt)))
1881 ctype = unsigned_type_for (type);
1882 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1883 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1884 chrec1 = instantiate_parameters (loop, chrec1);
1885 chrec2 = instantiate_parameters (loop, chrec2);
1886 res = chrec_fold_multiply (ctype, chrec1, chrec2);
1887 if (type != ctype)
1888 res = chrec_convert (type, res, at_stmt);
1889 break;
1891 case LSHIFT_EXPR:
1893 /* Handle A<<B as A * (1<<B). */
1894 tree uns = unsigned_type_for (type);
1895 chrec1 = analyze_scalar_evolution (loop, rhs1);
1896 chrec2 = analyze_scalar_evolution (loop, rhs2);
1897 chrec1 = chrec_convert (uns, chrec1, at_stmt);
1898 chrec1 = instantiate_parameters (loop, chrec1);
1899 chrec2 = instantiate_parameters (loop, chrec2);
1901 tree one = build_int_cst (uns, 1);
1902 chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1903 res = chrec_fold_multiply (uns, chrec1, chrec2);
1904 res = chrec_convert (type, res, at_stmt);
1906 break;
1908 CASE_CONVERT:
1909 /* In case we have a truncation of a widened operation that in
1910 the truncated type has undefined overflow behavior analyze
1911 the operation done in an unsigned type of the same precision
1912 as the final truncation. We cannot derive a scalar evolution
1913 for the widened operation but for the truncated result. */
1914 if (TREE_CODE (type) == INTEGER_TYPE
1915 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1916 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1917 && TYPE_OVERFLOW_UNDEFINED (type)
1918 && TREE_CODE (rhs1) == SSA_NAME
1919 && (def = SSA_NAME_DEF_STMT (rhs1))
1920 && is_gimple_assign (def)
1921 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1922 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1924 tree utype = unsigned_type_for (type);
1925 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1926 gimple_assign_rhs1 (def),
1927 gimple_assign_rhs_code (def),
1928 gimple_assign_rhs2 (def));
1930 else
1931 chrec1 = analyze_scalar_evolution (loop, rhs1);
1932 res = chrec_convert (type, chrec1, at_stmt);
1933 break;
1935 default:
1936 res = chrec_dont_know;
1937 break;
1940 return res;
1943 /* Interpret the expression EXPR. */
1945 static tree
1946 interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
1948 enum tree_code code;
1949 tree type = TREE_TYPE (expr), op0, op1;
1951 if (automatically_generated_chrec_p (expr))
1952 return expr;
1954 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1955 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1956 return chrec_dont_know;
1958 extract_ops_from_tree (expr, &code, &op0, &op1);
1960 return interpret_rhs_expr (loop, at_stmt, type,
1961 op0, code, op1);
1964 /* Interpret the rhs of the assignment STMT. */
1966 static tree
1967 interpret_gimple_assign (struct loop *loop, gimple *stmt)
1969 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1970 enum tree_code code = gimple_assign_rhs_code (stmt);
1972 return interpret_rhs_expr (loop, stmt, type,
1973 gimple_assign_rhs1 (stmt), code,
1974 gimple_assign_rhs2 (stmt));
1979 /* This section contains all the entry points:
1980 - number_of_iterations_in_loop,
1981 - analyze_scalar_evolution,
1982 - instantiate_parameters.
1985 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1986 common ancestor of DEF_LOOP and USE_LOOP. */
1988 static tree
1989 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1990 struct loop *def_loop,
1991 tree ev)
1993 bool val;
1994 tree res;
1996 if (def_loop == wrto_loop)
1997 return ev;
1999 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
2000 res = compute_overall_effect_of_inner_loop (def_loop, ev);
2002 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
2003 return res;
2005 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
2008 /* Helper recursive function. */
2010 static tree
2011 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
2013 tree type = TREE_TYPE (var);
2014 gimple *def;
2015 basic_block bb;
2016 struct loop *def_loop;
2018 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
2019 return chrec_dont_know;
2021 if (TREE_CODE (var) != SSA_NAME)
2022 return interpret_expr (loop, NULL, var);
2024 def = SSA_NAME_DEF_STMT (var);
2025 bb = gimple_bb (def);
2026 def_loop = bb ? bb->loop_father : NULL;
2028 if (bb == NULL
2029 || !flow_bb_inside_loop_p (loop, bb))
2031 /* Keep symbolic form, but look through obvious copies for constants. */
2032 res = follow_copies_to_constant (var);
2033 goto set_and_end;
2036 if (res != chrec_not_analyzed_yet)
2038 if (loop != bb->loop_father)
2039 res = compute_scalar_evolution_in_loop
2040 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
2042 goto set_and_end;
2045 if (loop != def_loop)
2047 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
2048 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
2050 goto set_and_end;
2053 switch (gimple_code (def))
2055 case GIMPLE_ASSIGN:
2056 res = interpret_gimple_assign (loop, def);
2057 break;
2059 case GIMPLE_PHI:
2060 if (loop_phi_node_p (def))
2061 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2062 else
2063 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2064 break;
2066 default:
2067 res = chrec_dont_know;
2068 break;
2071 set_and_end:
2073 /* Keep the symbolic form. */
2074 if (res == chrec_dont_know)
2075 res = var;
2077 if (loop == def_loop)
2078 set_scalar_evolution (block_before_loop (loop), var, res);
2080 return res;
2083 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2084 LOOP. LOOP is the loop in which the variable is used.
2086 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2087 pointer to the statement that uses this variable, in order to
2088 determine the evolution function of the variable, use the following
2089 calls:
2091 loop_p loop = loop_containing_stmt (stmt);
2092 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2093 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2096 tree
2097 analyze_scalar_evolution (struct loop *loop, tree var)
2099 tree res;
2101 if (dump_file && (dump_flags & TDF_SCEV))
2103 fprintf (dump_file, "(analyze_scalar_evolution \n");
2104 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2105 fprintf (dump_file, " (scalar = ");
2106 print_generic_expr (dump_file, var, 0);
2107 fprintf (dump_file, ")\n");
2110 res = get_scalar_evolution (block_before_loop (loop), var);
2111 res = analyze_scalar_evolution_1 (loop, var, res);
2113 if (dump_file && (dump_flags & TDF_SCEV))
2114 fprintf (dump_file, ")\n");
2116 return res;
2119 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2121 static tree
2122 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2124 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2127 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2128 WRTO_LOOP (which should be a superloop of USE_LOOP)
2130 FOLDED_CASTS is set to true if resolve_mixers used
2131 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2132 at the moment in order to keep things simple).
2134 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2135 example:
2137 for (i = 0; i < 100; i++) -- loop 1
2139 for (j = 0; j < 100; j++) -- loop 2
2141 k1 = i;
2142 k2 = j;
2144 use2 (k1, k2);
2146 for (t = 0; t < 100; t++) -- loop 3
2147 use3 (k1, k2);
2150 use1 (k1, k2);
2153 Both k1 and k2 are invariants in loop3, thus
2154 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2155 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2157 As they are invariant, it does not matter whether we consider their
2158 usage in loop 3 or loop 2, hence
2159 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2160 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2161 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2162 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2164 Similarly for their evolutions with respect to loop 1. The values of K2
2165 in the use in loop 2 vary independently on loop 1, thus we cannot express
2166 the evolution with respect to loop 1:
2167 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2168 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2169 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2170 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2172 The value of k2 in the use in loop 1 is known, though:
2173 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2174 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2177 static tree
2178 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2179 tree version, bool *folded_casts)
2181 bool val = false;
2182 tree ev = version, tmp;
2184 /* We cannot just do
2186 tmp = analyze_scalar_evolution (use_loop, version);
2187 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2189 as resolve_mixers would query the scalar evolution with respect to
2190 wrto_loop. For example, in the situation described in the function
2191 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2192 version = k2. Then
2194 analyze_scalar_evolution (use_loop, version) = k2
2196 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2197 k2 in loop 1 is 100, which is a wrong result, since we are interested
2198 in the value in loop 3.
2200 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2201 each time checking that there is no evolution in the inner loop. */
2203 if (folded_casts)
2204 *folded_casts = false;
2205 while (1)
2207 tmp = analyze_scalar_evolution (use_loop, ev);
2208 ev = resolve_mixers (use_loop, tmp, folded_casts);
2210 if (use_loop == wrto_loop)
2211 return ev;
2213 /* If the value of the use changes in the inner loop, we cannot express
2214 its value in the outer loop (we might try to return interval chrec,
2215 but we do not have a user for it anyway) */
2216 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2217 || !val)
2218 return chrec_dont_know;
2220 use_loop = loop_outer (use_loop);
2225 /* Hashtable helpers for a temporary hash-table used when
2226 instantiating a CHREC or resolving mixers. For this use
2227 instantiated_below is always the same. */
2229 struct instantiate_cache_type
2231 htab_t map;
2232 vec<scev_info_str> entries;
2234 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2235 ~instantiate_cache_type ();
2236 tree get (unsigned slot) { return entries[slot].chrec; }
2237 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2240 instantiate_cache_type::~instantiate_cache_type ()
2242 if (map != NULL)
2244 htab_delete (map);
2245 entries.release ();
2249 /* Cache to avoid infinite recursion when instantiating an SSA name.
2250 Live during the outermost instantiate_scev or resolve_mixers call. */
2251 static instantiate_cache_type *global_cache;
2253 /* Computes a hash function for database element ELT. */
2255 static inline hashval_t
2256 hash_idx_scev_info (const void *elt_)
2258 unsigned idx = ((size_t) elt_) - 2;
2259 return scev_info_hasher::hash (&global_cache->entries[idx]);
2262 /* Compares database elements E1 and E2. */
2264 static inline int
2265 eq_idx_scev_info (const void *e1, const void *e2)
2267 unsigned idx1 = ((size_t) e1) - 2;
2268 return scev_info_hasher::equal (&global_cache->entries[idx1],
2269 (const scev_info_str *) e2);
2272 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2274 static unsigned
2275 get_instantiated_value_entry (instantiate_cache_type &cache,
2276 tree name, basic_block instantiate_below)
2278 if (!cache.map)
2280 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2281 cache.entries.create (10);
2284 scev_info_str e;
2285 e.name_version = SSA_NAME_VERSION (name);
2286 e.instantiated_below = instantiate_below->index;
2287 void **slot = htab_find_slot_with_hash (cache.map, &e,
2288 scev_info_hasher::hash (&e), INSERT);
2289 if (!*slot)
2291 e.chrec = chrec_not_analyzed_yet;
2292 *slot = (void *)(size_t)(cache.entries.length () + 2);
2293 cache.entries.safe_push (e);
2296 return ((size_t)*slot) - 2;
2300 /* Return the closed_loop_phi node for VAR. If there is none, return
2301 NULL_TREE. */
2303 static tree
2304 loop_closed_phi_def (tree var)
2306 struct loop *loop;
2307 edge exit;
2308 gphi *phi;
2309 gphi_iterator psi;
2311 if (var == NULL_TREE
2312 || TREE_CODE (var) != SSA_NAME)
2313 return NULL_TREE;
2315 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2316 exit = single_exit (loop);
2317 if (!exit)
2318 return NULL_TREE;
2320 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2322 phi = psi.phi ();
2323 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2324 return PHI_RESULT (phi);
2327 return NULL_TREE;
2330 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2331 tree, bool *, int);
2333 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2334 and EVOLUTION_LOOP, that were left under a symbolic form.
2336 CHREC is an SSA_NAME to be instantiated.
2338 CACHE is the cache of already instantiated values.
2340 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2341 conversions that may wrap in signed/pointer type are folded, as long
2342 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2343 then we don't do such fold.
2345 SIZE_EXPR is used for computing the size of the expression to be
2346 instantiated, and to stop if it exceeds some limit. */
2348 static tree
2349 instantiate_scev_name (basic_block instantiate_below,
2350 struct loop *evolution_loop, struct loop *inner_loop,
2351 tree chrec,
2352 bool *fold_conversions,
2353 int size_expr)
2355 tree res;
2356 struct loop *def_loop;
2357 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2359 /* A parameter (or loop invariant and we do not want to include
2360 evolutions in outer loops), nothing to do. */
2361 if (!def_bb
2362 || loop_depth (def_bb->loop_father) == 0
2363 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2364 return chrec;
2366 /* We cache the value of instantiated variable to avoid exponential
2367 time complexity due to reevaluations. We also store the convenient
2368 value in the cache in order to prevent infinite recursion -- we do
2369 not want to instantiate the SSA_NAME if it is in a mixer
2370 structure. This is used for avoiding the instantiation of
2371 recursively defined functions, such as:
2373 | a_2 -> {0, +, 1, +, a_2}_1 */
2375 unsigned si = get_instantiated_value_entry (*global_cache,
2376 chrec, instantiate_below);
2377 if (global_cache->get (si) != chrec_not_analyzed_yet)
2378 return global_cache->get (si);
2380 /* On recursion return chrec_dont_know. */
2381 global_cache->set (si, chrec_dont_know);
2383 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2385 /* If the analysis yields a parametric chrec, instantiate the
2386 result again. */
2387 res = analyze_scalar_evolution (def_loop, chrec);
2389 /* Don't instantiate default definitions. */
2390 if (TREE_CODE (res) == SSA_NAME
2391 && SSA_NAME_IS_DEFAULT_DEF (res))
2394 /* Don't instantiate loop-closed-ssa phi nodes. */
2395 else if (TREE_CODE (res) == SSA_NAME
2396 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2397 > loop_depth (def_loop))
2399 if (res == chrec)
2400 res = loop_closed_phi_def (chrec);
2401 else
2402 res = chrec;
2404 /* When there is no loop_closed_phi_def, it means that the
2405 variable is not used after the loop: try to still compute the
2406 value of the variable when exiting the loop. */
2407 if (res == NULL_TREE)
2409 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2410 res = analyze_scalar_evolution (loop, chrec);
2411 res = compute_overall_effect_of_inner_loop (loop, res);
2412 res = instantiate_scev_r (instantiate_below, evolution_loop,
2413 inner_loop, res,
2414 fold_conversions, size_expr);
2416 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2417 gimple_bb (SSA_NAME_DEF_STMT (res))))
2418 res = chrec_dont_know;
2421 else if (res != chrec_dont_know)
2423 if (inner_loop
2424 && def_bb->loop_father != inner_loop
2425 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2426 /* ??? We could try to compute the overall effect of the loop here. */
2427 res = chrec_dont_know;
2428 else
2429 res = instantiate_scev_r (instantiate_below, evolution_loop,
2430 inner_loop, res,
2431 fold_conversions, size_expr);
2434 /* Store the correct value to the cache. */
2435 global_cache->set (si, res);
2436 return res;
2439 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2440 and EVOLUTION_LOOP, that were left under a symbolic form.
2442 CHREC is a polynomial chain of recurrence to be instantiated.
2444 CACHE is the cache of already instantiated values.
2446 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2447 conversions that may wrap in signed/pointer type are folded, as long
2448 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2449 then we don't do such fold.
2451 SIZE_EXPR is used for computing the size of the expression to be
2452 instantiated, and to stop if it exceeds some limit. */
2454 static tree
2455 instantiate_scev_poly (basic_block instantiate_below,
2456 struct loop *evolution_loop, struct loop *,
2457 tree chrec, bool *fold_conversions, int size_expr)
2459 tree op1;
2460 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2461 get_chrec_loop (chrec),
2462 CHREC_LEFT (chrec), fold_conversions,
2463 size_expr);
2464 if (op0 == chrec_dont_know)
2465 return chrec_dont_know;
2467 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2468 get_chrec_loop (chrec),
2469 CHREC_RIGHT (chrec), fold_conversions,
2470 size_expr);
2471 if (op1 == chrec_dont_know)
2472 return chrec_dont_know;
2474 if (CHREC_LEFT (chrec) != op0
2475 || CHREC_RIGHT (chrec) != op1)
2477 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2478 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2481 return chrec;
2484 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2485 and EVOLUTION_LOOP, that were left under a symbolic form.
2487 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2489 CACHE is the cache of already instantiated values.
2491 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2492 conversions that may wrap in signed/pointer type are folded, as long
2493 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2494 then we don't do such fold.
2496 SIZE_EXPR is used for computing the size of the expression to be
2497 instantiated, and to stop if it exceeds some limit. */
2499 static tree
2500 instantiate_scev_binary (basic_block instantiate_below,
2501 struct loop *evolution_loop, struct loop *inner_loop,
2502 tree chrec, enum tree_code code,
2503 tree type, tree c0, tree c1,
2504 bool *fold_conversions, int size_expr)
2506 tree op1;
2507 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2508 c0, fold_conversions, size_expr);
2509 if (op0 == chrec_dont_know)
2510 return chrec_dont_know;
2512 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2513 c1, fold_conversions, size_expr);
2514 if (op1 == chrec_dont_know)
2515 return chrec_dont_know;
2517 if (c0 != op0
2518 || c1 != op1)
2520 op0 = chrec_convert (type, op0, NULL);
2521 op1 = chrec_convert_rhs (type, op1, NULL);
2523 switch (code)
2525 case POINTER_PLUS_EXPR:
2526 case PLUS_EXPR:
2527 return chrec_fold_plus (type, op0, op1);
2529 case MINUS_EXPR:
2530 return chrec_fold_minus (type, op0, op1);
2532 case MULT_EXPR:
2533 return chrec_fold_multiply (type, op0, op1);
2535 default:
2536 gcc_unreachable ();
2540 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2543 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2544 and EVOLUTION_LOOP, that were left under a symbolic form.
2546 "CHREC" is an array reference to be instantiated.
2548 CACHE is the cache of already instantiated values.
2550 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2551 conversions that may wrap in signed/pointer type are folded, as long
2552 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2553 then we don't do such fold.
2555 SIZE_EXPR is used for computing the size of the expression to be
2556 instantiated, and to stop if it exceeds some limit. */
2558 static tree
2559 instantiate_array_ref (basic_block instantiate_below,
2560 struct loop *evolution_loop, struct loop *inner_loop,
2561 tree chrec, bool *fold_conversions, int size_expr)
2563 tree res;
2564 tree index = TREE_OPERAND (chrec, 1);
2565 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2566 inner_loop, index,
2567 fold_conversions, size_expr);
2569 if (op1 == chrec_dont_know)
2570 return chrec_dont_know;
2572 if (chrec && op1 == index)
2573 return chrec;
2575 res = unshare_expr (chrec);
2576 TREE_OPERAND (res, 1) = op1;
2577 return res;
2580 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2581 and EVOLUTION_LOOP, that were left under a symbolic form.
2583 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2584 instantiated.
2586 CACHE is the cache of already instantiated values.
2588 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2589 conversions that may wrap in signed/pointer type are folded, as long
2590 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2591 then we don't do such fold.
2593 SIZE_EXPR is used for computing the size of the expression to be
2594 instantiated, and to stop if it exceeds some limit. */
2596 static tree
2597 instantiate_scev_convert (basic_block instantiate_below,
2598 struct loop *evolution_loop, struct loop *inner_loop,
2599 tree chrec, tree type, tree op,
2600 bool *fold_conversions, int size_expr)
2602 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2603 inner_loop, op,
2604 fold_conversions, size_expr);
2606 if (op0 == chrec_dont_know)
2607 return chrec_dont_know;
2609 if (fold_conversions)
2611 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2612 if (tmp)
2613 return tmp;
2615 /* If we used chrec_convert_aggressive, we can no longer assume that
2616 signed chrecs do not overflow, as chrec_convert does, so avoid
2617 calling it in that case. */
2618 if (*fold_conversions)
2620 if (chrec && op0 == op)
2621 return chrec;
2623 return fold_convert (type, op0);
2627 return chrec_convert (type, op0, NULL);
2630 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2631 and EVOLUTION_LOOP, that were left under a symbolic form.
2633 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2634 Handle ~X as -1 - X.
2635 Handle -X as -1 * X.
2637 CACHE is the cache of already instantiated values.
2639 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2640 conversions that may wrap in signed/pointer type are folded, as long
2641 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2642 then we don't do such fold.
2644 SIZE_EXPR is used for computing the size of the expression to be
2645 instantiated, and to stop if it exceeds some limit. */
2647 static tree
2648 instantiate_scev_not (basic_block instantiate_below,
2649 struct loop *evolution_loop, struct loop *inner_loop,
2650 tree chrec,
2651 enum tree_code code, tree type, tree op,
2652 bool *fold_conversions, int size_expr)
2654 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2655 inner_loop, op,
2656 fold_conversions, size_expr);
2658 if (op0 == chrec_dont_know)
2659 return chrec_dont_know;
2661 if (op != op0)
2663 op0 = chrec_convert (type, op0, NULL);
2665 switch (code)
2667 case BIT_NOT_EXPR:
2668 return chrec_fold_minus
2669 (type, fold_convert (type, integer_minus_one_node), op0);
2671 case NEGATE_EXPR:
2672 return chrec_fold_multiply
2673 (type, fold_convert (type, integer_minus_one_node), op0);
2675 default:
2676 gcc_unreachable ();
2680 return chrec ? chrec : fold_build1 (code, type, op0);
2683 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2684 and EVOLUTION_LOOP, that were left under a symbolic form.
2686 CHREC is an expression with 3 operands to be instantiated.
2688 CACHE is the cache of already instantiated values.
2690 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2691 conversions that may wrap in signed/pointer type are folded, as long
2692 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2693 then we don't do such fold.
2695 SIZE_EXPR is used for computing the size of the expression to be
2696 instantiated, and to stop if it exceeds some limit. */
2698 static tree
2699 instantiate_scev_3 (basic_block instantiate_below,
2700 struct loop *evolution_loop, struct loop *inner_loop,
2701 tree chrec,
2702 bool *fold_conversions, int size_expr)
2704 tree op1, op2;
2705 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2706 inner_loop, TREE_OPERAND (chrec, 0),
2707 fold_conversions, size_expr);
2708 if (op0 == chrec_dont_know)
2709 return chrec_dont_know;
2711 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2712 inner_loop, TREE_OPERAND (chrec, 1),
2713 fold_conversions, size_expr);
2714 if (op1 == chrec_dont_know)
2715 return chrec_dont_know;
2717 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2718 inner_loop, TREE_OPERAND (chrec, 2),
2719 fold_conversions, size_expr);
2720 if (op2 == chrec_dont_know)
2721 return chrec_dont_know;
2723 if (op0 == TREE_OPERAND (chrec, 0)
2724 && op1 == TREE_OPERAND (chrec, 1)
2725 && op2 == TREE_OPERAND (chrec, 2))
2726 return chrec;
2728 return fold_build3 (TREE_CODE (chrec),
2729 TREE_TYPE (chrec), op0, op1, op2);
2732 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2733 and EVOLUTION_LOOP, that were left under a symbolic form.
2735 CHREC is an expression with 2 operands to be instantiated.
2737 CACHE is the cache of already instantiated values.
2739 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2740 conversions that may wrap in signed/pointer type are folded, as long
2741 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2742 then we don't do such fold.
2744 SIZE_EXPR is used for computing the size of the expression to be
2745 instantiated, and to stop if it exceeds some limit. */
2747 static tree
2748 instantiate_scev_2 (basic_block instantiate_below,
2749 struct loop *evolution_loop, struct loop *inner_loop,
2750 tree chrec,
2751 bool *fold_conversions, int size_expr)
2753 tree op1;
2754 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2755 inner_loop, TREE_OPERAND (chrec, 0),
2756 fold_conversions, size_expr);
2757 if (op0 == chrec_dont_know)
2758 return chrec_dont_know;
2760 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2761 inner_loop, TREE_OPERAND (chrec, 1),
2762 fold_conversions, size_expr);
2763 if (op1 == chrec_dont_know)
2764 return chrec_dont_know;
2766 if (op0 == TREE_OPERAND (chrec, 0)
2767 && op1 == TREE_OPERAND (chrec, 1))
2768 return chrec;
2770 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2773 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2774 and EVOLUTION_LOOP, that were left under a symbolic form.
2776 CHREC is an expression with 2 operands to be instantiated.
2778 CACHE is the cache of already instantiated values.
2780 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2781 conversions that may wrap in signed/pointer type are folded, as long
2782 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2783 then we don't do such fold.
2785 SIZE_EXPR is used for computing the size of the expression to be
2786 instantiated, and to stop if it exceeds some limit. */
2788 static tree
2789 instantiate_scev_1 (basic_block instantiate_below,
2790 struct loop *evolution_loop, struct loop *inner_loop,
2791 tree chrec,
2792 bool *fold_conversions, int size_expr)
2794 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2795 inner_loop, TREE_OPERAND (chrec, 0),
2796 fold_conversions, size_expr);
2798 if (op0 == chrec_dont_know)
2799 return chrec_dont_know;
2801 if (op0 == TREE_OPERAND (chrec, 0))
2802 return chrec;
2804 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2807 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2808 and EVOLUTION_LOOP, that were left under a symbolic form.
2810 CHREC is the scalar evolution to instantiate.
2812 CACHE is the cache of already instantiated values.
2814 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2815 conversions that may wrap in signed/pointer type are folded, as long
2816 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2817 then we don't do such fold.
2819 SIZE_EXPR is used for computing the size of the expression to be
2820 instantiated, and to stop if it exceeds some limit. */
2822 static tree
2823 instantiate_scev_r (basic_block instantiate_below,
2824 struct loop *evolution_loop, struct loop *inner_loop,
2825 tree chrec,
2826 bool *fold_conversions, int size_expr)
2828 /* Give up if the expression is larger than the MAX that we allow. */
2829 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2830 return chrec_dont_know;
2832 if (chrec == NULL_TREE
2833 || automatically_generated_chrec_p (chrec)
2834 || is_gimple_min_invariant (chrec))
2835 return chrec;
2837 switch (TREE_CODE (chrec))
2839 case SSA_NAME:
2840 return instantiate_scev_name (instantiate_below, evolution_loop,
2841 inner_loop, chrec,
2842 fold_conversions, size_expr);
2844 case POLYNOMIAL_CHREC:
2845 return instantiate_scev_poly (instantiate_below, evolution_loop,
2846 inner_loop, chrec,
2847 fold_conversions, size_expr);
2849 case POINTER_PLUS_EXPR:
2850 case PLUS_EXPR:
2851 case MINUS_EXPR:
2852 case MULT_EXPR:
2853 return instantiate_scev_binary (instantiate_below, evolution_loop,
2854 inner_loop, chrec,
2855 TREE_CODE (chrec), chrec_type (chrec),
2856 TREE_OPERAND (chrec, 0),
2857 TREE_OPERAND (chrec, 1),
2858 fold_conversions, size_expr);
2860 CASE_CONVERT:
2861 return instantiate_scev_convert (instantiate_below, evolution_loop,
2862 inner_loop, chrec,
2863 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2864 fold_conversions, size_expr);
2866 case NEGATE_EXPR:
2867 case BIT_NOT_EXPR:
2868 return instantiate_scev_not (instantiate_below, evolution_loop,
2869 inner_loop, chrec,
2870 TREE_CODE (chrec), TREE_TYPE (chrec),
2871 TREE_OPERAND (chrec, 0),
2872 fold_conversions, size_expr);
2874 case ADDR_EXPR:
2875 case SCEV_NOT_KNOWN:
2876 return chrec_dont_know;
2878 case SCEV_KNOWN:
2879 return chrec_known;
2881 case ARRAY_REF:
2882 return instantiate_array_ref (instantiate_below, evolution_loop,
2883 inner_loop, chrec,
2884 fold_conversions, size_expr);
2886 default:
2887 break;
2890 if (VL_EXP_CLASS_P (chrec))
2891 return chrec_dont_know;
2893 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2895 case 3:
2896 return instantiate_scev_3 (instantiate_below, evolution_loop,
2897 inner_loop, chrec,
2898 fold_conversions, size_expr);
2900 case 2:
2901 return instantiate_scev_2 (instantiate_below, evolution_loop,
2902 inner_loop, chrec,
2903 fold_conversions, size_expr);
2905 case 1:
2906 return instantiate_scev_1 (instantiate_below, evolution_loop,
2907 inner_loop, chrec,
2908 fold_conversions, size_expr);
2910 case 0:
2911 return chrec;
2913 default:
2914 break;
2917 /* Too complicated to handle. */
2918 return chrec_dont_know;
2921 /* Analyze all the parameters of the chrec that were left under a
2922 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2923 recursive instantiation of parameters: a parameter is a variable
2924 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2925 a function parameter. */
2927 tree
2928 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2929 tree chrec)
2931 tree res;
2933 if (dump_file && (dump_flags & TDF_SCEV))
2935 fprintf (dump_file, "(instantiate_scev \n");
2936 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2937 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2938 fprintf (dump_file, " (chrec = ");
2939 print_generic_expr (dump_file, chrec, 0);
2940 fprintf (dump_file, ")\n");
2943 bool destr = false;
2944 if (!global_cache)
2946 global_cache = new instantiate_cache_type;
2947 destr = true;
2950 res = instantiate_scev_r (instantiate_below, evolution_loop,
2951 NULL, chrec, NULL, 0);
2953 if (destr)
2955 delete global_cache;
2956 global_cache = NULL;
2959 if (dump_file && (dump_flags & TDF_SCEV))
2961 fprintf (dump_file, " (res = ");
2962 print_generic_expr (dump_file, res, 0);
2963 fprintf (dump_file, "))\n");
2966 return res;
2969 /* Similar to instantiate_parameters, but does not introduce the
2970 evolutions in outer loops for LOOP invariants in CHREC, and does not
2971 care about causing overflows, as long as they do not affect value
2972 of an expression. */
2974 tree
2975 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
2977 bool destr = false;
2978 bool fold_conversions = false;
2979 if (!global_cache)
2981 global_cache = new instantiate_cache_type;
2982 destr = true;
2985 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
2986 chrec, &fold_conversions, 0);
2988 if (folded_casts && !*folded_casts)
2989 *folded_casts = fold_conversions;
2991 if (destr)
2993 delete global_cache;
2994 global_cache = NULL;
2997 return ret;
3000 /* Entry point for the analysis of the number of iterations pass.
3001 This function tries to safely approximate the number of iterations
3002 the loop will run. When this property is not decidable at compile
3003 time, the result is chrec_dont_know. Otherwise the result is a
3004 scalar or a symbolic parameter. When the number of iterations may
3005 be equal to zero and the property cannot be determined at compile
3006 time, the result is a COND_EXPR that represents in a symbolic form
3007 the conditions under which the number of iterations is not zero.
3009 Example of analysis: suppose that the loop has an exit condition:
3011 "if (b > 49) goto end_loop;"
3013 and that in a previous analysis we have determined that the
3014 variable 'b' has an evolution function:
3016 "EF = {23, +, 5}_2".
3018 When we evaluate the function at the point 5, i.e. the value of the
3019 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
3020 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
3021 the loop body has been executed 6 times. */
3023 tree
3024 number_of_latch_executions (struct loop *loop)
3026 edge exit;
3027 struct tree_niter_desc niter_desc;
3028 tree may_be_zero;
3029 tree res;
3031 /* Determine whether the number of iterations in loop has already
3032 been computed. */
3033 res = loop->nb_iterations;
3034 if (res)
3035 return res;
3037 may_be_zero = NULL_TREE;
3039 if (dump_file && (dump_flags & TDF_SCEV))
3040 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
3042 res = chrec_dont_know;
3043 exit = single_exit (loop);
3045 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
3047 may_be_zero = niter_desc.may_be_zero;
3048 res = niter_desc.niter;
3051 if (res == chrec_dont_know
3052 || !may_be_zero
3053 || integer_zerop (may_be_zero))
3055 else if (integer_nonzerop (may_be_zero))
3056 res = build_int_cst (TREE_TYPE (res), 0);
3058 else if (COMPARISON_CLASS_P (may_be_zero))
3059 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
3060 build_int_cst (TREE_TYPE (res), 0), res);
3061 else
3062 res = chrec_dont_know;
3064 if (dump_file && (dump_flags & TDF_SCEV))
3066 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
3067 print_generic_expr (dump_file, res, 0);
3068 fprintf (dump_file, "))\n");
3071 loop->nb_iterations = res;
3072 return res;
3076 /* Counters for the stats. */
3078 struct chrec_stats
3080 unsigned nb_chrecs;
3081 unsigned nb_affine;
3082 unsigned nb_affine_multivar;
3083 unsigned nb_higher_poly;
3084 unsigned nb_chrec_dont_know;
3085 unsigned nb_undetermined;
3088 /* Reset the counters. */
3090 static inline void
3091 reset_chrecs_counters (struct chrec_stats *stats)
3093 stats->nb_chrecs = 0;
3094 stats->nb_affine = 0;
3095 stats->nb_affine_multivar = 0;
3096 stats->nb_higher_poly = 0;
3097 stats->nb_chrec_dont_know = 0;
3098 stats->nb_undetermined = 0;
3101 /* Dump the contents of a CHREC_STATS structure. */
3103 static void
3104 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3106 fprintf (file, "\n(\n");
3107 fprintf (file, "-----------------------------------------\n");
3108 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3109 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3110 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3111 stats->nb_higher_poly);
3112 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3113 fprintf (file, "-----------------------------------------\n");
3114 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3115 fprintf (file, "%d\twith undetermined coefficients\n",
3116 stats->nb_undetermined);
3117 fprintf (file, "-----------------------------------------\n");
3118 fprintf (file, "%d\tchrecs in the scev database\n",
3119 (int) scalar_evolution_info->elements ());
3120 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3121 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3122 fprintf (file, "-----------------------------------------\n");
3123 fprintf (file, ")\n\n");
3126 /* Gather statistics about CHREC. */
3128 static void
3129 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3131 if (dump_file && (dump_flags & TDF_STATS))
3133 fprintf (dump_file, "(classify_chrec ");
3134 print_generic_expr (dump_file, chrec, 0);
3135 fprintf (dump_file, "\n");
3138 stats->nb_chrecs++;
3140 if (chrec == NULL_TREE)
3142 stats->nb_undetermined++;
3143 return;
3146 switch (TREE_CODE (chrec))
3148 case POLYNOMIAL_CHREC:
3149 if (evolution_function_is_affine_p (chrec))
3151 if (dump_file && (dump_flags & TDF_STATS))
3152 fprintf (dump_file, " affine_univariate\n");
3153 stats->nb_affine++;
3155 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3157 if (dump_file && (dump_flags & TDF_STATS))
3158 fprintf (dump_file, " affine_multivariate\n");
3159 stats->nb_affine_multivar++;
3161 else
3163 if (dump_file && (dump_flags & TDF_STATS))
3164 fprintf (dump_file, " higher_degree_polynomial\n");
3165 stats->nb_higher_poly++;
3168 break;
3170 default:
3171 break;
3174 if (chrec_contains_undetermined (chrec))
3176 if (dump_file && (dump_flags & TDF_STATS))
3177 fprintf (dump_file, " undetermined\n");
3178 stats->nb_undetermined++;
3181 if (dump_file && (dump_flags & TDF_STATS))
3182 fprintf (dump_file, ")\n");
3185 /* Classify the chrecs of the whole database. */
3187 void
3188 gather_stats_on_scev_database (void)
3190 struct chrec_stats stats;
3192 if (!dump_file)
3193 return;
3195 reset_chrecs_counters (&stats);
3197 hash_table<scev_info_hasher>::iterator iter;
3198 scev_info_str *elt;
3199 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3200 iter)
3201 gather_chrec_stats (elt->chrec, &stats);
3203 dump_chrecs_stats (dump_file, &stats);
3208 /* Initializer. */
3210 static void
3211 initialize_scalar_evolutions_analyzer (void)
3213 /* The elements below are unique. */
3214 if (chrec_dont_know == NULL_TREE)
3216 chrec_not_analyzed_yet = NULL_TREE;
3217 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3218 chrec_known = make_node (SCEV_KNOWN);
3219 TREE_TYPE (chrec_dont_know) = void_type_node;
3220 TREE_TYPE (chrec_known) = void_type_node;
3224 /* Initialize the analysis of scalar evolutions for LOOPS. */
3226 void
3227 scev_initialize (void)
3229 struct loop *loop;
3231 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3233 initialize_scalar_evolutions_analyzer ();
3235 FOR_EACH_LOOP (loop, 0)
3237 loop->nb_iterations = NULL_TREE;
3241 /* Return true if SCEV is initialized. */
3243 bool
3244 scev_initialized_p (void)
3246 return scalar_evolution_info != NULL;
3249 /* Cleans up the information cached by the scalar evolutions analysis
3250 in the hash table. */
3252 void
3253 scev_reset_htab (void)
3255 if (!scalar_evolution_info)
3256 return;
3258 scalar_evolution_info->empty ();
3261 /* Cleans up the information cached by the scalar evolutions analysis
3262 in the hash table and in the loop->nb_iterations. */
3264 void
3265 scev_reset (void)
3267 struct loop *loop;
3269 scev_reset_htab ();
3271 FOR_EACH_LOOP (loop, 0)
3273 loop->nb_iterations = NULL_TREE;
3277 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3278 respect to WRTO_LOOP and returns its base and step in IV if possible
3279 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3280 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3281 invariant in LOOP. Otherwise we require it to be an integer constant.
3283 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3284 because it is computed in signed arithmetics). Consequently, adding an
3285 induction variable
3287 for (i = IV->base; ; i += IV->step)
3289 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3290 false for the type of the induction variable, or you can prove that i does
3291 not wrap by some other argument. Otherwise, this might introduce undefined
3292 behavior, and
3294 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3296 must be used instead. */
3298 bool
3299 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3300 affine_iv *iv, bool allow_nonconstant_step)
3302 enum tree_code code;
3303 tree type, ev, base, e, stop;
3304 wide_int extreme;
3305 bool folded_casts, overflow;
3307 iv->base = NULL_TREE;
3308 iv->step = NULL_TREE;
3309 iv->no_overflow = false;
3311 type = TREE_TYPE (op);
3312 if (!POINTER_TYPE_P (type)
3313 && !INTEGRAL_TYPE_P (type))
3314 return false;
3316 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3317 &folded_casts);
3318 if (chrec_contains_undetermined (ev)
3319 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3320 return false;
3322 if (tree_does_not_contain_chrecs (ev))
3324 iv->base = ev;
3325 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3326 iv->no_overflow = true;
3327 return true;
3330 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3331 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3332 return false;
3334 iv->step = CHREC_RIGHT (ev);
3335 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3336 || tree_contains_chrecs (iv->step, NULL))
3337 return false;
3339 iv->base = CHREC_LEFT (ev);
3340 if (tree_contains_chrecs (iv->base, NULL))
3341 return false;
3343 iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
3344 && TYPE_OVERFLOW_UNDEFINED (type));
3346 /* Try to simplify iv base:
3348 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3349 == (signed T)(unsigned T)base + step
3350 == base + step
3352 If we can prove operation (base + step) doesn't overflow or underflow.
3353 Specifically, we try to prove below conditions are satisfied:
3355 base <= UPPER_BOUND (type) - step ;;step > 0
3356 base >= LOWER_BOUND (type) - step ;;step < 0
3358 This is done by proving the reverse conditions are false using loop's
3359 initial conditions.
3361 The is necessary to make loop niter, or iv overflow analysis easier
3362 for below example:
3364 int foo (int *a, signed char s, signed char l)
3366 signed char i;
3367 for (i = s; i < l; i++)
3368 a[i] = 0;
3369 return 0;
3372 Note variable I is firstly converted to type unsigned char, incremented,
3373 then converted back to type signed char. */
3375 if (wrto_loop->num != use_loop->num)
3376 return true;
3378 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3379 return true;
3381 type = TREE_TYPE (iv->base);
3382 e = TREE_OPERAND (iv->base, 0);
3383 if (TREE_CODE (e) != PLUS_EXPR
3384 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3385 || !tree_int_cst_equal (iv->step,
3386 fold_convert (type, TREE_OPERAND (e, 1))))
3387 return true;
3388 e = TREE_OPERAND (e, 0);
3389 if (!CONVERT_EXPR_P (e))
3390 return true;
3391 base = TREE_OPERAND (e, 0);
3392 if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3393 return true;
3395 if (tree_int_cst_sign_bit (iv->step))
3397 code = LT_EXPR;
3398 extreme = wi::min_value (type);
3400 else
3402 code = GT_EXPR;
3403 extreme = wi::max_value (type);
3405 overflow = false;
3406 extreme = wi::sub (extreme, iv->step, TYPE_SIGN (type), &overflow);
3407 if (overflow)
3408 return true;
3409 e = fold_build2 (code, boolean_type_node, base,
3410 wide_int_to_tree (type, extreme));
3411 stop = (TREE_CODE (base) == SSA_NAME) ? base : NULL;
3412 e = simplify_using_initial_conditions (use_loop, e, stop);
3413 if (!integer_zerop (e))
3414 return true;
3416 if (POINTER_TYPE_P (TREE_TYPE (base)))
3417 code = POINTER_PLUS_EXPR;
3418 else
3419 code = PLUS_EXPR;
3421 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3422 return true;
3425 /* Finalize the scalar evolution analysis. */
3427 void
3428 scev_finalize (void)
3430 if (!scalar_evolution_info)
3431 return;
3432 scalar_evolution_info->empty ();
3433 scalar_evolution_info = NULL;
3436 /* Returns true if the expression EXPR is considered to be too expensive
3437 for scev_const_prop. */
3439 bool
3440 expression_expensive_p (tree expr)
3442 enum tree_code code;
3444 if (is_gimple_val (expr))
3445 return false;
3447 code = TREE_CODE (expr);
3448 if (code == TRUNC_DIV_EXPR
3449 || code == CEIL_DIV_EXPR
3450 || code == FLOOR_DIV_EXPR
3451 || code == ROUND_DIV_EXPR
3452 || code == TRUNC_MOD_EXPR
3453 || code == CEIL_MOD_EXPR
3454 || code == FLOOR_MOD_EXPR
3455 || code == ROUND_MOD_EXPR
3456 || code == EXACT_DIV_EXPR)
3458 /* Division by power of two is usually cheap, so we allow it.
3459 Forbid anything else. */
3460 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3461 return true;
3464 switch (TREE_CODE_CLASS (code))
3466 case tcc_binary:
3467 case tcc_comparison:
3468 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3469 return true;
3471 /* Fallthru. */
3472 case tcc_unary:
3473 return expression_expensive_p (TREE_OPERAND (expr, 0));
3475 default:
3476 return true;
3480 /* Do final value replacement for LOOP. */
3482 void
3483 final_value_replacement_loop (struct loop *loop)
3485 /* If we do not know exact number of iterations of the loop, we cannot
3486 replace the final value. */
3487 edge exit = single_exit (loop);
3488 if (!exit)
3489 return;
3491 tree niter = number_of_latch_executions (loop);
3492 if (niter == chrec_dont_know)
3493 return;
3495 /* Ensure that it is possible to insert new statements somewhere. */
3496 if (!single_pred_p (exit->dest))
3497 split_loop_exit_edge (exit);
3499 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3500 gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
3502 struct loop *ex_loop
3503 = superloop_at_depth (loop,
3504 loop_depth (exit->dest->loop_father) + 1);
3506 gphi_iterator psi;
3507 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3509 gphi *phi = psi.phi ();
3510 tree rslt = PHI_RESULT (phi);
3511 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3512 if (virtual_operand_p (def))
3514 gsi_next (&psi);
3515 continue;
3518 if (!POINTER_TYPE_P (TREE_TYPE (def))
3519 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3521 gsi_next (&psi);
3522 continue;
3525 bool folded_casts;
3526 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3527 &folded_casts);
3528 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3529 if (!tree_does_not_contain_chrecs (def)
3530 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3531 /* Moving the computation from the loop may prolong life range
3532 of some ssa names, which may cause problems if they appear
3533 on abnormal edges. */
3534 || contains_abnormal_ssa_name_p (def)
3535 /* Do not emit expensive expressions. The rationale is that
3536 when someone writes a code like
3538 while (n > 45) n -= 45;
3540 he probably knows that n is not large, and does not want it
3541 to be turned into n %= 45. */
3542 || expression_expensive_p (def))
3544 if (dump_file && (dump_flags & TDF_DETAILS))
3546 fprintf (dump_file, "not replacing:\n ");
3547 print_gimple_stmt (dump_file, phi, 0, 0);
3548 fprintf (dump_file, "\n");
3550 gsi_next (&psi);
3551 continue;
3554 /* Eliminate the PHI node and replace it by a computation outside
3555 the loop. */
3556 if (dump_file)
3558 fprintf (dump_file, "\nfinal value replacement:\n ");
3559 print_gimple_stmt (dump_file, phi, 0, 0);
3560 fprintf (dump_file, " with\n ");
3562 def = unshare_expr (def);
3563 remove_phi_node (&psi, false);
3565 /* If def's type has undefined overflow and there were folded
3566 casts, rewrite all stmts added for def into arithmetics
3567 with defined overflow behavior. */
3568 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3569 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3571 gimple_seq stmts;
3572 gimple_stmt_iterator gsi2;
3573 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3574 gsi2 = gsi_start (stmts);
3575 while (!gsi_end_p (gsi2))
3577 gimple *stmt = gsi_stmt (gsi2);
3578 gimple_stmt_iterator gsi3 = gsi2;
3579 gsi_next (&gsi2);
3580 gsi_remove (&gsi3, false);
3581 if (is_gimple_assign (stmt)
3582 && arith_code_with_undefined_signed_overflow
3583 (gimple_assign_rhs_code (stmt)))
3584 gsi_insert_seq_before (&gsi,
3585 rewrite_to_defined_overflow (stmt),
3586 GSI_SAME_STMT);
3587 else
3588 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3591 else
3592 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3593 true, GSI_SAME_STMT);
3595 gassign *ass = gimple_build_assign (rslt, def);
3596 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3597 if (dump_file)
3599 print_gimple_stmt (dump_file, ass, 0, 0);
3600 fprintf (dump_file, "\n");
3605 /* Replace ssa names for that scev can prove they are constant by the
3606 appropriate constants. Also perform final value replacement in loops,
3607 in case the replacement expressions are cheap.
3609 We only consider SSA names defined by phi nodes; rest is left to the
3610 ordinary constant propagation pass. */
3612 unsigned int
3613 scev_const_prop (void)
3615 basic_block bb;
3616 tree name, type, ev;
3617 gphi *phi;
3618 struct loop *loop;
3619 bitmap ssa_names_to_remove = NULL;
3620 unsigned i;
3621 gphi_iterator psi;
3623 if (number_of_loops (cfun) <= 1)
3624 return 0;
3626 FOR_EACH_BB_FN (bb, cfun)
3628 loop = bb->loop_father;
3630 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3632 phi = psi.phi ();
3633 name = PHI_RESULT (phi);
3635 if (virtual_operand_p (name))
3636 continue;
3638 type = TREE_TYPE (name);
3640 if (!POINTER_TYPE_P (type)
3641 && !INTEGRAL_TYPE_P (type))
3642 continue;
3644 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3645 NULL);
3646 if (!is_gimple_min_invariant (ev)
3647 || !may_propagate_copy (name, ev))
3648 continue;
3650 /* Replace the uses of the name. */
3651 if (name != ev)
3653 if (dump_file && (dump_flags & TDF_DETAILS))
3655 fprintf (dump_file, "Replacing uses of: ");
3656 print_generic_expr (dump_file, name, 0);
3657 fprintf (dump_file, " with: ");
3658 print_generic_expr (dump_file, ev, 0);
3659 fprintf (dump_file, "\n");
3661 replace_uses_by (name, ev);
3664 if (!ssa_names_to_remove)
3665 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3666 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3670 /* Remove the ssa names that were replaced by constants. We do not
3671 remove them directly in the previous cycle, since this
3672 invalidates scev cache. */
3673 if (ssa_names_to_remove)
3675 bitmap_iterator bi;
3677 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3679 gimple_stmt_iterator psi;
3680 name = ssa_name (i);
3681 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3683 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3684 psi = gsi_for_stmt (phi);
3685 remove_phi_node (&psi, true);
3688 BITMAP_FREE (ssa_names_to_remove);
3689 scev_reset ();
3692 /* Now the regular final value replacement. */
3693 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3694 final_value_replacement_loop (loop);
3696 return 0;
3699 #include "gt-tree-scalar-evolution.h"