[doc] Correct optimisation levels documentation for -fstore-merging
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobcbd17e8644fe4e488c28e63231f4f93e523646d7
1 /* Scalar evolution detector.
2 Copyright (C) 2003-2017 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);
1514 if (evolution_function == chrec_dont_know)
1515 break;
1518 if (dump_file && (dump_flags & TDF_SCEV))
1520 fprintf (dump_file, " (evolution_function = ");
1521 print_generic_expr (dump_file, evolution_function, 0);
1522 fprintf (dump_file, "))\n");
1525 return evolution_function;
1528 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1529 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1531 static tree
1532 follow_copies_to_constant (tree var)
1534 tree res = var;
1535 while (TREE_CODE (res) == SSA_NAME)
1537 gimple *def = SSA_NAME_DEF_STMT (res);
1538 if (gphi *phi = dyn_cast <gphi *> (def))
1540 if (tree rhs = degenerate_phi_result (phi))
1541 res = rhs;
1542 else
1543 break;
1545 else if (gimple_assign_single_p (def))
1546 /* Will exit loop if not an SSA_NAME. */
1547 res = gimple_assign_rhs1 (def);
1548 else
1549 break;
1551 if (CONSTANT_CLASS_P (res))
1552 return res;
1553 return var;
1556 /* Given a loop-phi-node, return the initial conditions of the
1557 variable on entry of the loop. When the CCP has propagated
1558 constants into the loop-phi-node, the initial condition is
1559 instantiated, otherwise the initial condition is kept symbolic.
1560 This analyzer does not analyze the evolution outside the current
1561 loop, and leaves this task to the on-demand tree reconstructor. */
1563 static tree
1564 analyze_initial_condition (gphi *loop_phi_node)
1566 int i, n;
1567 tree init_cond = chrec_not_analyzed_yet;
1568 struct loop *loop = loop_containing_stmt (loop_phi_node);
1570 if (dump_file && (dump_flags & TDF_SCEV))
1572 fprintf (dump_file, "(analyze_initial_condition \n");
1573 fprintf (dump_file, " (loop_phi_node = \n");
1574 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1575 fprintf (dump_file, ")\n");
1578 n = gimple_phi_num_args (loop_phi_node);
1579 for (i = 0; i < n; i++)
1581 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1582 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1584 /* When the branch is oriented to the loop's body, it does
1585 not contribute to the initial condition. */
1586 if (flow_bb_inside_loop_p (loop, bb))
1587 continue;
1589 if (init_cond == chrec_not_analyzed_yet)
1591 init_cond = branch;
1592 continue;
1595 if (TREE_CODE (branch) == SSA_NAME)
1597 init_cond = chrec_dont_know;
1598 break;
1601 init_cond = chrec_merge (init_cond, branch);
1604 /* Ooops -- a loop without an entry??? */
1605 if (init_cond == chrec_not_analyzed_yet)
1606 init_cond = chrec_dont_know;
1608 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1609 to not miss important early loop unrollings. */
1610 init_cond = follow_copies_to_constant (init_cond);
1612 if (dump_file && (dump_flags & TDF_SCEV))
1614 fprintf (dump_file, " (init_cond = ");
1615 print_generic_expr (dump_file, init_cond, 0);
1616 fprintf (dump_file, "))\n");
1619 return init_cond;
1622 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1624 static tree
1625 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1627 tree res;
1628 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1629 tree init_cond;
1631 if (phi_loop != loop)
1633 struct loop *subloop;
1634 tree evolution_fn = analyze_scalar_evolution
1635 (phi_loop, PHI_RESULT (loop_phi_node));
1637 /* Dive one level deeper. */
1638 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1640 /* Interpret the subloop. */
1641 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1642 return res;
1645 /* Otherwise really interpret the loop phi. */
1646 init_cond = analyze_initial_condition (loop_phi_node);
1647 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1649 /* Verify we maintained the correct initial condition throughout
1650 possible conversions in the SSA chain. */
1651 if (res != chrec_dont_know)
1653 tree new_init = res;
1654 if (CONVERT_EXPR_P (res)
1655 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1656 new_init = fold_convert (TREE_TYPE (res),
1657 CHREC_LEFT (TREE_OPERAND (res, 0)));
1658 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1659 new_init = CHREC_LEFT (res);
1660 STRIP_USELESS_TYPE_CONVERSION (new_init);
1661 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1662 || !operand_equal_p (init_cond, new_init, 0))
1663 return chrec_dont_know;
1666 return res;
1669 /* This function merges the branches of a condition-phi-node,
1670 contained in the outermost loop, and whose arguments are already
1671 analyzed. */
1673 static tree
1674 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1676 int i, n = gimple_phi_num_args (condition_phi);
1677 tree res = chrec_not_analyzed_yet;
1679 for (i = 0; i < n; i++)
1681 tree branch_chrec;
1683 if (backedge_phi_arg_p (condition_phi, i))
1685 res = chrec_dont_know;
1686 break;
1689 branch_chrec = analyze_scalar_evolution
1690 (loop, PHI_ARG_DEF (condition_phi, i));
1692 res = chrec_merge (res, branch_chrec);
1693 if (res == chrec_dont_know)
1694 break;
1697 return res;
1700 /* Interpret the operation RHS1 OP RHS2. If we didn't
1701 analyze this node before, follow the definitions until ending
1702 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1703 return path, this function propagates evolutions (ala constant copy
1704 propagation). OPND1 is not a GIMPLE expression because we could
1705 analyze the effect of an inner loop: see interpret_loop_phi. */
1707 static tree
1708 interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
1709 tree type, tree rhs1, enum tree_code code, tree rhs2)
1711 tree res, chrec1, chrec2, ctype;
1712 gimple *def;
1714 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1716 if (is_gimple_min_invariant (rhs1))
1717 return chrec_convert (type, rhs1, at_stmt);
1719 if (code == SSA_NAME)
1720 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1721 at_stmt);
1723 if (code == ASSERT_EXPR)
1725 rhs1 = ASSERT_EXPR_VAR (rhs1);
1726 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1727 at_stmt);
1731 switch (code)
1733 case ADDR_EXPR:
1734 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1735 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1737 machine_mode mode;
1738 HOST_WIDE_INT bitsize, bitpos;
1739 int unsignedp, reversep;
1740 int volatilep = 0;
1741 tree base, offset;
1742 tree chrec3;
1743 tree unitpos;
1745 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1746 &bitsize, &bitpos, &offset, &mode,
1747 &unsignedp, &reversep, &volatilep);
1749 if (TREE_CODE (base) == MEM_REF)
1751 rhs2 = TREE_OPERAND (base, 1);
1752 rhs1 = TREE_OPERAND (base, 0);
1754 chrec1 = analyze_scalar_evolution (loop, rhs1);
1755 chrec2 = analyze_scalar_evolution (loop, rhs2);
1756 chrec1 = chrec_convert (type, chrec1, at_stmt);
1757 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1758 chrec1 = instantiate_parameters (loop, chrec1);
1759 chrec2 = instantiate_parameters (loop, chrec2);
1760 res = chrec_fold_plus (type, chrec1, chrec2);
1762 else
1764 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1765 chrec1 = chrec_convert (type, chrec1, at_stmt);
1766 res = chrec1;
1769 if (offset != NULL_TREE)
1771 chrec2 = analyze_scalar_evolution (loop, offset);
1772 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1773 chrec2 = instantiate_parameters (loop, chrec2);
1774 res = chrec_fold_plus (type, res, chrec2);
1777 if (bitpos != 0)
1779 gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
1781 unitpos = size_int (bitpos / BITS_PER_UNIT);
1782 chrec3 = analyze_scalar_evolution (loop, unitpos);
1783 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1784 chrec3 = instantiate_parameters (loop, chrec3);
1785 res = chrec_fold_plus (type, res, chrec3);
1788 else
1789 res = chrec_dont_know;
1790 break;
1792 case POINTER_PLUS_EXPR:
1793 chrec1 = analyze_scalar_evolution (loop, rhs1);
1794 chrec2 = analyze_scalar_evolution (loop, rhs2);
1795 chrec1 = chrec_convert (type, chrec1, at_stmt);
1796 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1797 chrec1 = instantiate_parameters (loop, chrec1);
1798 chrec2 = instantiate_parameters (loop, chrec2);
1799 res = chrec_fold_plus (type, chrec1, chrec2);
1800 break;
1802 case PLUS_EXPR:
1803 chrec1 = analyze_scalar_evolution (loop, rhs1);
1804 chrec2 = analyze_scalar_evolution (loop, rhs2);
1805 ctype = type;
1806 /* When the stmt is conditionally executed re-write the CHREC
1807 into a form that has well-defined behavior on overflow. */
1808 if (at_stmt
1809 && INTEGRAL_TYPE_P (type)
1810 && ! TYPE_OVERFLOW_WRAPS (type)
1811 && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1812 gimple_bb (at_stmt)))
1813 ctype = unsigned_type_for (type);
1814 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1815 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1816 chrec1 = instantiate_parameters (loop, chrec1);
1817 chrec2 = instantiate_parameters (loop, chrec2);
1818 res = chrec_fold_plus (ctype, chrec1, chrec2);
1819 if (type != ctype)
1820 res = chrec_convert (type, res, at_stmt);
1821 break;
1823 case MINUS_EXPR:
1824 chrec1 = analyze_scalar_evolution (loop, rhs1);
1825 chrec2 = analyze_scalar_evolution (loop, rhs2);
1826 ctype = type;
1827 /* When the stmt is conditionally executed re-write the CHREC
1828 into a form that has well-defined behavior on overflow. */
1829 if (at_stmt
1830 && INTEGRAL_TYPE_P (type)
1831 && ! TYPE_OVERFLOW_WRAPS (type)
1832 && ! dominated_by_p (CDI_DOMINATORS,
1833 loop->latch, gimple_bb (at_stmt)))
1834 ctype = unsigned_type_for (type);
1835 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1836 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1837 chrec1 = instantiate_parameters (loop, chrec1);
1838 chrec2 = instantiate_parameters (loop, chrec2);
1839 res = chrec_fold_minus (ctype, chrec1, chrec2);
1840 if (type != ctype)
1841 res = chrec_convert (type, res, at_stmt);
1842 break;
1844 case NEGATE_EXPR:
1845 chrec1 = analyze_scalar_evolution (loop, rhs1);
1846 ctype = type;
1847 /* When the stmt is conditionally executed re-write the CHREC
1848 into a form that has well-defined behavior on overflow. */
1849 if (at_stmt
1850 && INTEGRAL_TYPE_P (type)
1851 && ! TYPE_OVERFLOW_WRAPS (type)
1852 && ! dominated_by_p (CDI_DOMINATORS,
1853 loop->latch, gimple_bb (at_stmt)))
1854 ctype = unsigned_type_for (type);
1855 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1856 /* TYPE may be integer, real or complex, so use fold_convert. */
1857 chrec1 = instantiate_parameters (loop, chrec1);
1858 res = chrec_fold_multiply (ctype, chrec1,
1859 fold_convert (ctype, integer_minus_one_node));
1860 if (type != ctype)
1861 res = chrec_convert (type, res, at_stmt);
1862 break;
1864 case BIT_NOT_EXPR:
1865 /* Handle ~X as -1 - X. */
1866 chrec1 = analyze_scalar_evolution (loop, rhs1);
1867 chrec1 = chrec_convert (type, chrec1, at_stmt);
1868 chrec1 = instantiate_parameters (loop, chrec1);
1869 res = chrec_fold_minus (type,
1870 fold_convert (type, integer_minus_one_node),
1871 chrec1);
1872 break;
1874 case MULT_EXPR:
1875 chrec1 = analyze_scalar_evolution (loop, rhs1);
1876 chrec2 = analyze_scalar_evolution (loop, rhs2);
1877 ctype = type;
1878 /* When the stmt is conditionally executed re-write the CHREC
1879 into a form that has well-defined behavior on overflow. */
1880 if (at_stmt
1881 && INTEGRAL_TYPE_P (type)
1882 && ! TYPE_OVERFLOW_WRAPS (type)
1883 && ! dominated_by_p (CDI_DOMINATORS,
1884 loop->latch, gimple_bb (at_stmt)))
1885 ctype = unsigned_type_for (type);
1886 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1887 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1888 chrec1 = instantiate_parameters (loop, chrec1);
1889 chrec2 = instantiate_parameters (loop, chrec2);
1890 res = chrec_fold_multiply (ctype, chrec1, chrec2);
1891 if (type != ctype)
1892 res = chrec_convert (type, res, at_stmt);
1893 break;
1895 case LSHIFT_EXPR:
1897 /* Handle A<<B as A * (1<<B). */
1898 tree uns = unsigned_type_for (type);
1899 chrec1 = analyze_scalar_evolution (loop, rhs1);
1900 chrec2 = analyze_scalar_evolution (loop, rhs2);
1901 chrec1 = chrec_convert (uns, chrec1, at_stmt);
1902 chrec1 = instantiate_parameters (loop, chrec1);
1903 chrec2 = instantiate_parameters (loop, chrec2);
1905 tree one = build_int_cst (uns, 1);
1906 chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1907 res = chrec_fold_multiply (uns, chrec1, chrec2);
1908 res = chrec_convert (type, res, at_stmt);
1910 break;
1912 CASE_CONVERT:
1913 /* In case we have a truncation of a widened operation that in
1914 the truncated type has undefined overflow behavior analyze
1915 the operation done in an unsigned type of the same precision
1916 as the final truncation. We cannot derive a scalar evolution
1917 for the widened operation but for the truncated result. */
1918 if (TREE_CODE (type) == INTEGER_TYPE
1919 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1920 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1921 && TYPE_OVERFLOW_UNDEFINED (type)
1922 && TREE_CODE (rhs1) == SSA_NAME
1923 && (def = SSA_NAME_DEF_STMT (rhs1))
1924 && is_gimple_assign (def)
1925 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1926 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1928 tree utype = unsigned_type_for (type);
1929 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1930 gimple_assign_rhs1 (def),
1931 gimple_assign_rhs_code (def),
1932 gimple_assign_rhs2 (def));
1934 else
1935 chrec1 = analyze_scalar_evolution (loop, rhs1);
1936 res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
1937 break;
1939 case BIT_AND_EXPR:
1940 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1941 If A is SCEV and its value is in the range of representable set
1942 of type unsigned short, the result expression is a (no-overflow)
1943 SCEV. */
1944 res = chrec_dont_know;
1945 if (tree_fits_uhwi_p (rhs2))
1947 int precision;
1948 unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1950 val ++;
1951 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1952 it's not the maximum value of a smaller type than rhs1. */
1953 if (val != 0
1954 && (precision = exact_log2 (val)) > 0
1955 && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1957 tree utype = build_nonstandard_integer_type (precision, 1);
1959 if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1961 chrec1 = analyze_scalar_evolution (loop, rhs1);
1962 chrec1 = chrec_convert (utype, chrec1, at_stmt);
1963 res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
1967 break;
1969 default:
1970 res = chrec_dont_know;
1971 break;
1974 return res;
1977 /* Interpret the expression EXPR. */
1979 static tree
1980 interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
1982 enum tree_code code;
1983 tree type = TREE_TYPE (expr), op0, op1;
1985 if (automatically_generated_chrec_p (expr))
1986 return expr;
1988 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1989 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1990 return chrec_dont_know;
1992 extract_ops_from_tree (expr, &code, &op0, &op1);
1994 return interpret_rhs_expr (loop, at_stmt, type,
1995 op0, code, op1);
1998 /* Interpret the rhs of the assignment STMT. */
2000 static tree
2001 interpret_gimple_assign (struct loop *loop, gimple *stmt)
2003 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2004 enum tree_code code = gimple_assign_rhs_code (stmt);
2006 return interpret_rhs_expr (loop, stmt, type,
2007 gimple_assign_rhs1 (stmt), code,
2008 gimple_assign_rhs2 (stmt));
2013 /* This section contains all the entry points:
2014 - number_of_iterations_in_loop,
2015 - analyze_scalar_evolution,
2016 - instantiate_parameters.
2019 /* Compute and return the evolution function in WRTO_LOOP, the nearest
2020 common ancestor of DEF_LOOP and USE_LOOP. */
2022 static tree
2023 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
2024 struct loop *def_loop,
2025 tree ev)
2027 bool val;
2028 tree res;
2030 if (def_loop == wrto_loop)
2031 return ev;
2033 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
2034 res = compute_overall_effect_of_inner_loop (def_loop, ev);
2036 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
2037 return res;
2039 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
2042 /* Helper recursive function. */
2044 static tree
2045 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
2047 tree type = TREE_TYPE (var);
2048 gimple *def;
2049 basic_block bb;
2050 struct loop *def_loop;
2052 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
2053 return chrec_dont_know;
2055 if (TREE_CODE (var) != SSA_NAME)
2056 return interpret_expr (loop, NULL, var);
2058 def = SSA_NAME_DEF_STMT (var);
2059 bb = gimple_bb (def);
2060 def_loop = bb ? bb->loop_father : NULL;
2062 if (bb == NULL
2063 || !flow_bb_inside_loop_p (loop, bb))
2065 /* Keep symbolic form, but look through obvious copies for constants. */
2066 res = follow_copies_to_constant (var);
2067 goto set_and_end;
2070 if (res != chrec_not_analyzed_yet)
2072 if (loop != bb->loop_father)
2073 res = compute_scalar_evolution_in_loop
2074 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
2076 goto set_and_end;
2079 if (loop != def_loop)
2081 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
2082 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
2084 goto set_and_end;
2087 switch (gimple_code (def))
2089 case GIMPLE_ASSIGN:
2090 res = interpret_gimple_assign (loop, def);
2091 break;
2093 case GIMPLE_PHI:
2094 if (loop_phi_node_p (def))
2095 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2096 else
2097 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2098 break;
2100 default:
2101 res = chrec_dont_know;
2102 break;
2105 set_and_end:
2107 /* Keep the symbolic form. */
2108 if (res == chrec_dont_know)
2109 res = var;
2111 if (loop == def_loop)
2112 set_scalar_evolution (block_before_loop (loop), var, res);
2114 return res;
2117 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2118 LOOP. LOOP is the loop in which the variable is used.
2120 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2121 pointer to the statement that uses this variable, in order to
2122 determine the evolution function of the variable, use the following
2123 calls:
2125 loop_p loop = loop_containing_stmt (stmt);
2126 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2127 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2130 tree
2131 analyze_scalar_evolution (struct loop *loop, tree var)
2133 tree res;
2135 if (dump_file && (dump_flags & TDF_SCEV))
2137 fprintf (dump_file, "(analyze_scalar_evolution \n");
2138 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2139 fprintf (dump_file, " (scalar = ");
2140 print_generic_expr (dump_file, var, 0);
2141 fprintf (dump_file, ")\n");
2144 res = get_scalar_evolution (block_before_loop (loop), var);
2145 res = analyze_scalar_evolution_1 (loop, var, res);
2147 if (dump_file && (dump_flags & TDF_SCEV))
2148 fprintf (dump_file, ")\n");
2150 return res;
2153 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2155 static tree
2156 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2158 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2161 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2162 WRTO_LOOP (which should be a superloop of USE_LOOP)
2164 FOLDED_CASTS is set to true if resolve_mixers used
2165 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2166 at the moment in order to keep things simple).
2168 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2169 example:
2171 for (i = 0; i < 100; i++) -- loop 1
2173 for (j = 0; j < 100; j++) -- loop 2
2175 k1 = i;
2176 k2 = j;
2178 use2 (k1, k2);
2180 for (t = 0; t < 100; t++) -- loop 3
2181 use3 (k1, k2);
2184 use1 (k1, k2);
2187 Both k1 and k2 are invariants in loop3, thus
2188 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2189 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2191 As they are invariant, it does not matter whether we consider their
2192 usage in loop 3 or loop 2, hence
2193 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2194 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2195 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2196 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2198 Similarly for their evolutions with respect to loop 1. The values of K2
2199 in the use in loop 2 vary independently on loop 1, thus we cannot express
2200 the evolution with respect to loop 1:
2201 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2202 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2203 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2204 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2206 The value of k2 in the use in loop 1 is known, though:
2207 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2208 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2211 static tree
2212 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2213 tree version, bool *folded_casts)
2215 bool val = false;
2216 tree ev = version, tmp;
2218 /* We cannot just do
2220 tmp = analyze_scalar_evolution (use_loop, version);
2221 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2223 as resolve_mixers would query the scalar evolution with respect to
2224 wrto_loop. For example, in the situation described in the function
2225 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2226 version = k2. Then
2228 analyze_scalar_evolution (use_loop, version) = k2
2230 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2231 k2 in loop 1 is 100, which is a wrong result, since we are interested
2232 in the value in loop 3.
2234 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2235 each time checking that there is no evolution in the inner loop. */
2237 if (folded_casts)
2238 *folded_casts = false;
2239 while (1)
2241 tmp = analyze_scalar_evolution (use_loop, ev);
2242 ev = resolve_mixers (use_loop, tmp, folded_casts);
2244 if (use_loop == wrto_loop)
2245 return ev;
2247 /* If the value of the use changes in the inner loop, we cannot express
2248 its value in the outer loop (we might try to return interval chrec,
2249 but we do not have a user for it anyway) */
2250 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2251 || !val)
2252 return chrec_dont_know;
2254 use_loop = loop_outer (use_loop);
2259 /* Hashtable helpers for a temporary hash-table used when
2260 instantiating a CHREC or resolving mixers. For this use
2261 instantiated_below is always the same. */
2263 struct instantiate_cache_type
2265 htab_t map;
2266 vec<scev_info_str> entries;
2268 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2269 ~instantiate_cache_type ();
2270 tree get (unsigned slot) { return entries[slot].chrec; }
2271 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2274 instantiate_cache_type::~instantiate_cache_type ()
2276 if (map != NULL)
2278 htab_delete (map);
2279 entries.release ();
2283 /* Cache to avoid infinite recursion when instantiating an SSA name.
2284 Live during the outermost instantiate_scev or resolve_mixers call. */
2285 static instantiate_cache_type *global_cache;
2287 /* Computes a hash function for database element ELT. */
2289 static inline hashval_t
2290 hash_idx_scev_info (const void *elt_)
2292 unsigned idx = ((size_t) elt_) - 2;
2293 return scev_info_hasher::hash (&global_cache->entries[idx]);
2296 /* Compares database elements E1 and E2. */
2298 static inline int
2299 eq_idx_scev_info (const void *e1, const void *e2)
2301 unsigned idx1 = ((size_t) e1) - 2;
2302 return scev_info_hasher::equal (&global_cache->entries[idx1],
2303 (const scev_info_str *) e2);
2306 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2308 static unsigned
2309 get_instantiated_value_entry (instantiate_cache_type &cache,
2310 tree name, basic_block instantiate_below)
2312 if (!cache.map)
2314 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2315 cache.entries.create (10);
2318 scev_info_str e;
2319 e.name_version = SSA_NAME_VERSION (name);
2320 e.instantiated_below = instantiate_below->index;
2321 void **slot = htab_find_slot_with_hash (cache.map, &e,
2322 scev_info_hasher::hash (&e), INSERT);
2323 if (!*slot)
2325 e.chrec = chrec_not_analyzed_yet;
2326 *slot = (void *)(size_t)(cache.entries.length () + 2);
2327 cache.entries.safe_push (e);
2330 return ((size_t)*slot) - 2;
2334 /* Return the closed_loop_phi node for VAR. If there is none, return
2335 NULL_TREE. */
2337 static tree
2338 loop_closed_phi_def (tree var)
2340 struct loop *loop;
2341 edge exit;
2342 gphi *phi;
2343 gphi_iterator psi;
2345 if (var == NULL_TREE
2346 || TREE_CODE (var) != SSA_NAME)
2347 return NULL_TREE;
2349 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2350 exit = single_exit (loop);
2351 if (!exit)
2352 return NULL_TREE;
2354 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2356 phi = psi.phi ();
2357 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2358 return PHI_RESULT (phi);
2361 return NULL_TREE;
2364 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2365 tree, bool *, int);
2367 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2368 and EVOLUTION_LOOP, that were left under a symbolic form.
2370 CHREC is an SSA_NAME to be instantiated.
2372 CACHE is the cache of already instantiated values.
2374 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2375 conversions that may wrap in signed/pointer type are folded, as long
2376 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2377 then we don't do such fold.
2379 SIZE_EXPR is used for computing the size of the expression to be
2380 instantiated, and to stop if it exceeds some limit. */
2382 static tree
2383 instantiate_scev_name (basic_block instantiate_below,
2384 struct loop *evolution_loop, struct loop *inner_loop,
2385 tree chrec,
2386 bool *fold_conversions,
2387 int size_expr)
2389 tree res;
2390 struct loop *def_loop;
2391 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2393 /* A parameter (or loop invariant and we do not want to include
2394 evolutions in outer loops), nothing to do. */
2395 if (!def_bb
2396 || loop_depth (def_bb->loop_father) == 0
2397 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2398 return chrec;
2400 /* We cache the value of instantiated variable to avoid exponential
2401 time complexity due to reevaluations. We also store the convenient
2402 value in the cache in order to prevent infinite recursion -- we do
2403 not want to instantiate the SSA_NAME if it is in a mixer
2404 structure. This is used for avoiding the instantiation of
2405 recursively defined functions, such as:
2407 | a_2 -> {0, +, 1, +, a_2}_1 */
2409 unsigned si = get_instantiated_value_entry (*global_cache,
2410 chrec, instantiate_below);
2411 if (global_cache->get (si) != chrec_not_analyzed_yet)
2412 return global_cache->get (si);
2414 /* On recursion return chrec_dont_know. */
2415 global_cache->set (si, chrec_dont_know);
2417 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2419 /* If the analysis yields a parametric chrec, instantiate the
2420 result again. */
2421 res = analyze_scalar_evolution (def_loop, chrec);
2423 /* Don't instantiate default definitions. */
2424 if (TREE_CODE (res) == SSA_NAME
2425 && SSA_NAME_IS_DEFAULT_DEF (res))
2428 /* Don't instantiate loop-closed-ssa phi nodes. */
2429 else if (TREE_CODE (res) == SSA_NAME
2430 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2431 > loop_depth (def_loop))
2433 if (res == chrec)
2434 res = loop_closed_phi_def (chrec);
2435 else
2436 res = chrec;
2438 /* When there is no loop_closed_phi_def, it means that the
2439 variable is not used after the loop: try to still compute the
2440 value of the variable when exiting the loop. */
2441 if (res == NULL_TREE)
2443 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2444 res = analyze_scalar_evolution (loop, chrec);
2445 res = compute_overall_effect_of_inner_loop (loop, res);
2446 res = instantiate_scev_r (instantiate_below, evolution_loop,
2447 inner_loop, res,
2448 fold_conversions, size_expr);
2450 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2451 gimple_bb (SSA_NAME_DEF_STMT (res))))
2452 res = chrec_dont_know;
2455 else if (res != chrec_dont_know)
2457 if (inner_loop
2458 && def_bb->loop_father != inner_loop
2459 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2460 /* ??? We could try to compute the overall effect of the loop here. */
2461 res = chrec_dont_know;
2462 else
2463 res = instantiate_scev_r (instantiate_below, evolution_loop,
2464 inner_loop, res,
2465 fold_conversions, size_expr);
2468 /* Store the correct value to the cache. */
2469 global_cache->set (si, res);
2470 return res;
2473 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2474 and EVOLUTION_LOOP, that were left under a symbolic form.
2476 CHREC is a polynomial chain of recurrence to be instantiated.
2478 CACHE is the cache of already instantiated values.
2480 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2481 conversions that may wrap in signed/pointer type are folded, as long
2482 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2483 then we don't do such fold.
2485 SIZE_EXPR is used for computing the size of the expression to be
2486 instantiated, and to stop if it exceeds some limit. */
2488 static tree
2489 instantiate_scev_poly (basic_block instantiate_below,
2490 struct loop *evolution_loop, struct loop *,
2491 tree chrec, bool *fold_conversions, int size_expr)
2493 tree op1;
2494 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2495 get_chrec_loop (chrec),
2496 CHREC_LEFT (chrec), fold_conversions,
2497 size_expr);
2498 if (op0 == chrec_dont_know)
2499 return chrec_dont_know;
2501 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2502 get_chrec_loop (chrec),
2503 CHREC_RIGHT (chrec), fold_conversions,
2504 size_expr);
2505 if (op1 == chrec_dont_know)
2506 return chrec_dont_know;
2508 if (CHREC_LEFT (chrec) != op0
2509 || CHREC_RIGHT (chrec) != op1)
2511 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2512 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2515 return chrec;
2518 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2519 and EVOLUTION_LOOP, that were left under a symbolic form.
2521 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2523 CACHE is the cache of already instantiated values.
2525 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2526 conversions that may wrap in signed/pointer type are folded, as long
2527 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2528 then we don't do such fold.
2530 SIZE_EXPR is used for computing the size of the expression to be
2531 instantiated, and to stop if it exceeds some limit. */
2533 static tree
2534 instantiate_scev_binary (basic_block instantiate_below,
2535 struct loop *evolution_loop, struct loop *inner_loop,
2536 tree chrec, enum tree_code code,
2537 tree type, tree c0, tree c1,
2538 bool *fold_conversions, int size_expr)
2540 tree op1;
2541 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2542 c0, fold_conversions, size_expr);
2543 if (op0 == chrec_dont_know)
2544 return chrec_dont_know;
2546 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2547 c1, fold_conversions, size_expr);
2548 if (op1 == chrec_dont_know)
2549 return chrec_dont_know;
2551 if (c0 != op0
2552 || c1 != op1)
2554 op0 = chrec_convert (type, op0, NULL);
2555 op1 = chrec_convert_rhs (type, op1, NULL);
2557 switch (code)
2559 case POINTER_PLUS_EXPR:
2560 case PLUS_EXPR:
2561 return chrec_fold_plus (type, op0, op1);
2563 case MINUS_EXPR:
2564 return chrec_fold_minus (type, op0, op1);
2566 case MULT_EXPR:
2567 return chrec_fold_multiply (type, op0, op1);
2569 default:
2570 gcc_unreachable ();
2574 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2577 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2578 and EVOLUTION_LOOP, that were left under a symbolic form.
2580 "CHREC" is an array reference to be instantiated.
2582 CACHE is the cache of already instantiated values.
2584 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2585 conversions that may wrap in signed/pointer type are folded, as long
2586 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2587 then we don't do such fold.
2589 SIZE_EXPR is used for computing the size of the expression to be
2590 instantiated, and to stop if it exceeds some limit. */
2592 static tree
2593 instantiate_array_ref (basic_block instantiate_below,
2594 struct loop *evolution_loop, struct loop *inner_loop,
2595 tree chrec, bool *fold_conversions, int size_expr)
2597 tree res;
2598 tree index = TREE_OPERAND (chrec, 1);
2599 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2600 inner_loop, index,
2601 fold_conversions, size_expr);
2603 if (op1 == chrec_dont_know)
2604 return chrec_dont_know;
2606 if (chrec && op1 == index)
2607 return chrec;
2609 res = unshare_expr (chrec);
2610 TREE_OPERAND (res, 1) = op1;
2611 return res;
2614 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2615 and EVOLUTION_LOOP, that were left under a symbolic form.
2617 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2618 instantiated.
2620 CACHE is the cache of already instantiated values.
2622 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2623 conversions that may wrap in signed/pointer type are folded, as long
2624 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2625 then we don't do such fold.
2627 SIZE_EXPR is used for computing the size of the expression to be
2628 instantiated, and to stop if it exceeds some limit. */
2630 static tree
2631 instantiate_scev_convert (basic_block instantiate_below,
2632 struct loop *evolution_loop, struct loop *inner_loop,
2633 tree chrec, tree type, tree op,
2634 bool *fold_conversions, int size_expr)
2636 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2637 inner_loop, op,
2638 fold_conversions, size_expr);
2640 if (op0 == chrec_dont_know)
2641 return chrec_dont_know;
2643 if (fold_conversions)
2645 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2646 if (tmp)
2647 return tmp;
2649 /* If we used chrec_convert_aggressive, we can no longer assume that
2650 signed chrecs do not overflow, as chrec_convert does, so avoid
2651 calling it in that case. */
2652 if (*fold_conversions)
2654 if (chrec && op0 == op)
2655 return chrec;
2657 return fold_convert (type, op0);
2661 return chrec_convert (type, op0, NULL);
2664 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2665 and EVOLUTION_LOOP, that were left under a symbolic form.
2667 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2668 Handle ~X as -1 - X.
2669 Handle -X as -1 * X.
2671 CACHE is the cache of already instantiated values.
2673 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2674 conversions that may wrap in signed/pointer type are folded, as long
2675 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2676 then we don't do such fold.
2678 SIZE_EXPR is used for computing the size of the expression to be
2679 instantiated, and to stop if it exceeds some limit. */
2681 static tree
2682 instantiate_scev_not (basic_block instantiate_below,
2683 struct loop *evolution_loop, struct loop *inner_loop,
2684 tree chrec,
2685 enum tree_code code, tree type, tree op,
2686 bool *fold_conversions, int size_expr)
2688 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2689 inner_loop, op,
2690 fold_conversions, size_expr);
2692 if (op0 == chrec_dont_know)
2693 return chrec_dont_know;
2695 if (op != op0)
2697 op0 = chrec_convert (type, op0, NULL);
2699 switch (code)
2701 case BIT_NOT_EXPR:
2702 return chrec_fold_minus
2703 (type, fold_convert (type, integer_minus_one_node), op0);
2705 case NEGATE_EXPR:
2706 return chrec_fold_multiply
2707 (type, fold_convert (type, integer_minus_one_node), op0);
2709 default:
2710 gcc_unreachable ();
2714 return chrec ? chrec : fold_build1 (code, type, op0);
2717 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2718 and EVOLUTION_LOOP, that were left under a symbolic form.
2720 CHREC is an expression with 3 operands to be instantiated.
2722 CACHE is the cache of already instantiated values.
2724 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2725 conversions that may wrap in signed/pointer type are folded, as long
2726 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2727 then we don't do such fold.
2729 SIZE_EXPR is used for computing the size of the expression to be
2730 instantiated, and to stop if it exceeds some limit. */
2732 static tree
2733 instantiate_scev_3 (basic_block instantiate_below,
2734 struct loop *evolution_loop, struct loop *inner_loop,
2735 tree chrec,
2736 bool *fold_conversions, int size_expr)
2738 tree op1, op2;
2739 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2740 inner_loop, TREE_OPERAND (chrec, 0),
2741 fold_conversions, size_expr);
2742 if (op0 == chrec_dont_know)
2743 return chrec_dont_know;
2745 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2746 inner_loop, TREE_OPERAND (chrec, 1),
2747 fold_conversions, size_expr);
2748 if (op1 == chrec_dont_know)
2749 return chrec_dont_know;
2751 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2752 inner_loop, TREE_OPERAND (chrec, 2),
2753 fold_conversions, size_expr);
2754 if (op2 == chrec_dont_know)
2755 return chrec_dont_know;
2757 if (op0 == TREE_OPERAND (chrec, 0)
2758 && op1 == TREE_OPERAND (chrec, 1)
2759 && op2 == TREE_OPERAND (chrec, 2))
2760 return chrec;
2762 return fold_build3 (TREE_CODE (chrec),
2763 TREE_TYPE (chrec), op0, op1, op2);
2766 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2767 and EVOLUTION_LOOP, that were left under a symbolic form.
2769 CHREC is an expression with 2 operands to be instantiated.
2771 CACHE is the cache of already instantiated values.
2773 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2774 conversions that may wrap in signed/pointer type are folded, as long
2775 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2776 then we don't do such fold.
2778 SIZE_EXPR is used for computing the size of the expression to be
2779 instantiated, and to stop if it exceeds some limit. */
2781 static tree
2782 instantiate_scev_2 (basic_block instantiate_below,
2783 struct loop *evolution_loop, struct loop *inner_loop,
2784 tree chrec,
2785 bool *fold_conversions, int size_expr)
2787 tree op1;
2788 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2789 inner_loop, TREE_OPERAND (chrec, 0),
2790 fold_conversions, size_expr);
2791 if (op0 == chrec_dont_know)
2792 return chrec_dont_know;
2794 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2795 inner_loop, TREE_OPERAND (chrec, 1),
2796 fold_conversions, size_expr);
2797 if (op1 == chrec_dont_know)
2798 return chrec_dont_know;
2800 if (op0 == TREE_OPERAND (chrec, 0)
2801 && op1 == TREE_OPERAND (chrec, 1))
2802 return chrec;
2804 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
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 an expression with 2 operands to be instantiated.
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_1 (basic_block instantiate_below,
2824 struct loop *evolution_loop, struct loop *inner_loop,
2825 tree chrec,
2826 bool *fold_conversions, int size_expr)
2828 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2829 inner_loop, TREE_OPERAND (chrec, 0),
2830 fold_conversions, size_expr);
2832 if (op0 == chrec_dont_know)
2833 return chrec_dont_know;
2835 if (op0 == TREE_OPERAND (chrec, 0))
2836 return chrec;
2838 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2841 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2842 and EVOLUTION_LOOP, that were left under a symbolic form.
2844 CHREC is the scalar evolution to instantiate.
2846 CACHE is the cache of already instantiated values.
2848 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2849 conversions that may wrap in signed/pointer type are folded, as long
2850 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2851 then we don't do such fold.
2853 SIZE_EXPR is used for computing the size of the expression to be
2854 instantiated, and to stop if it exceeds some limit. */
2856 static tree
2857 instantiate_scev_r (basic_block instantiate_below,
2858 struct loop *evolution_loop, struct loop *inner_loop,
2859 tree chrec,
2860 bool *fold_conversions, int size_expr)
2862 /* Give up if the expression is larger than the MAX that we allow. */
2863 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2864 return chrec_dont_know;
2866 if (chrec == NULL_TREE
2867 || automatically_generated_chrec_p (chrec)
2868 || is_gimple_min_invariant (chrec))
2869 return chrec;
2871 switch (TREE_CODE (chrec))
2873 case SSA_NAME:
2874 return instantiate_scev_name (instantiate_below, evolution_loop,
2875 inner_loop, chrec,
2876 fold_conversions, size_expr);
2878 case POLYNOMIAL_CHREC:
2879 return instantiate_scev_poly (instantiate_below, evolution_loop,
2880 inner_loop, chrec,
2881 fold_conversions, size_expr);
2883 case POINTER_PLUS_EXPR:
2884 case PLUS_EXPR:
2885 case MINUS_EXPR:
2886 case MULT_EXPR:
2887 return instantiate_scev_binary (instantiate_below, evolution_loop,
2888 inner_loop, chrec,
2889 TREE_CODE (chrec), chrec_type (chrec),
2890 TREE_OPERAND (chrec, 0),
2891 TREE_OPERAND (chrec, 1),
2892 fold_conversions, size_expr);
2894 CASE_CONVERT:
2895 return instantiate_scev_convert (instantiate_below, evolution_loop,
2896 inner_loop, chrec,
2897 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2898 fold_conversions, size_expr);
2900 case NEGATE_EXPR:
2901 case BIT_NOT_EXPR:
2902 return instantiate_scev_not (instantiate_below, evolution_loop,
2903 inner_loop, chrec,
2904 TREE_CODE (chrec), TREE_TYPE (chrec),
2905 TREE_OPERAND (chrec, 0),
2906 fold_conversions, size_expr);
2908 case ADDR_EXPR:
2909 case SCEV_NOT_KNOWN:
2910 return chrec_dont_know;
2912 case SCEV_KNOWN:
2913 return chrec_known;
2915 case ARRAY_REF:
2916 return instantiate_array_ref (instantiate_below, evolution_loop,
2917 inner_loop, chrec,
2918 fold_conversions, size_expr);
2920 default:
2921 break;
2924 if (VL_EXP_CLASS_P (chrec))
2925 return chrec_dont_know;
2927 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2929 case 3:
2930 return instantiate_scev_3 (instantiate_below, evolution_loop,
2931 inner_loop, chrec,
2932 fold_conversions, size_expr);
2934 case 2:
2935 return instantiate_scev_2 (instantiate_below, evolution_loop,
2936 inner_loop, chrec,
2937 fold_conversions, size_expr);
2939 case 1:
2940 return instantiate_scev_1 (instantiate_below, evolution_loop,
2941 inner_loop, chrec,
2942 fold_conversions, size_expr);
2944 case 0:
2945 return chrec;
2947 default:
2948 break;
2951 /* Too complicated to handle. */
2952 return chrec_dont_know;
2955 /* Analyze all the parameters of the chrec that were left under a
2956 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2957 recursive instantiation of parameters: a parameter is a variable
2958 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2959 a function parameter. */
2961 tree
2962 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2963 tree chrec)
2965 tree res;
2967 if (dump_file && (dump_flags & TDF_SCEV))
2969 fprintf (dump_file, "(instantiate_scev \n");
2970 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2971 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2972 fprintf (dump_file, " (chrec = ");
2973 print_generic_expr (dump_file, chrec, 0);
2974 fprintf (dump_file, ")\n");
2977 bool destr = false;
2978 if (!global_cache)
2980 global_cache = new instantiate_cache_type;
2981 destr = true;
2984 res = instantiate_scev_r (instantiate_below, evolution_loop,
2985 NULL, chrec, NULL, 0);
2987 if (destr)
2989 delete global_cache;
2990 global_cache = NULL;
2993 if (dump_file && (dump_flags & TDF_SCEV))
2995 fprintf (dump_file, " (res = ");
2996 print_generic_expr (dump_file, res, 0);
2997 fprintf (dump_file, "))\n");
3000 return res;
3003 /* Similar to instantiate_parameters, but does not introduce the
3004 evolutions in outer loops for LOOP invariants in CHREC, and does not
3005 care about causing overflows, as long as they do not affect value
3006 of an expression. */
3008 tree
3009 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
3011 bool destr = false;
3012 bool fold_conversions = false;
3013 if (!global_cache)
3015 global_cache = new instantiate_cache_type;
3016 destr = true;
3019 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
3020 chrec, &fold_conversions, 0);
3022 if (folded_casts && !*folded_casts)
3023 *folded_casts = fold_conversions;
3025 if (destr)
3027 delete global_cache;
3028 global_cache = NULL;
3031 return ret;
3034 /* Entry point for the analysis of the number of iterations pass.
3035 This function tries to safely approximate the number of iterations
3036 the loop will run. When this property is not decidable at compile
3037 time, the result is chrec_dont_know. Otherwise the result is a
3038 scalar or a symbolic parameter. When the number of iterations may
3039 be equal to zero and the property cannot be determined at compile
3040 time, the result is a COND_EXPR that represents in a symbolic form
3041 the conditions under which the number of iterations is not zero.
3043 Example of analysis: suppose that the loop has an exit condition:
3045 "if (b > 49) goto end_loop;"
3047 and that in a previous analysis we have determined that the
3048 variable 'b' has an evolution function:
3050 "EF = {23, +, 5}_2".
3052 When we evaluate the function at the point 5, i.e. the value of the
3053 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
3054 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
3055 the loop body has been executed 6 times. */
3057 tree
3058 number_of_latch_executions (struct loop *loop)
3060 edge exit;
3061 struct tree_niter_desc niter_desc;
3062 tree may_be_zero;
3063 tree res;
3065 /* Determine whether the number of iterations in loop has already
3066 been computed. */
3067 res = loop->nb_iterations;
3068 if (res)
3069 return res;
3071 may_be_zero = NULL_TREE;
3073 if (dump_file && (dump_flags & TDF_SCEV))
3074 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
3076 res = chrec_dont_know;
3077 exit = single_exit (loop);
3079 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
3081 may_be_zero = niter_desc.may_be_zero;
3082 res = niter_desc.niter;
3085 if (res == chrec_dont_know
3086 || !may_be_zero
3087 || integer_zerop (may_be_zero))
3089 else if (integer_nonzerop (may_be_zero))
3090 res = build_int_cst (TREE_TYPE (res), 0);
3092 else if (COMPARISON_CLASS_P (may_be_zero))
3093 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
3094 build_int_cst (TREE_TYPE (res), 0), res);
3095 else
3096 res = chrec_dont_know;
3098 if (dump_file && (dump_flags & TDF_SCEV))
3100 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
3101 print_generic_expr (dump_file, res, 0);
3102 fprintf (dump_file, "))\n");
3105 loop->nb_iterations = res;
3106 return res;
3110 /* Counters for the stats. */
3112 struct chrec_stats
3114 unsigned nb_chrecs;
3115 unsigned nb_affine;
3116 unsigned nb_affine_multivar;
3117 unsigned nb_higher_poly;
3118 unsigned nb_chrec_dont_know;
3119 unsigned nb_undetermined;
3122 /* Reset the counters. */
3124 static inline void
3125 reset_chrecs_counters (struct chrec_stats *stats)
3127 stats->nb_chrecs = 0;
3128 stats->nb_affine = 0;
3129 stats->nb_affine_multivar = 0;
3130 stats->nb_higher_poly = 0;
3131 stats->nb_chrec_dont_know = 0;
3132 stats->nb_undetermined = 0;
3135 /* Dump the contents of a CHREC_STATS structure. */
3137 static void
3138 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3140 fprintf (file, "\n(\n");
3141 fprintf (file, "-----------------------------------------\n");
3142 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3143 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3144 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3145 stats->nb_higher_poly);
3146 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3147 fprintf (file, "-----------------------------------------\n");
3148 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3149 fprintf (file, "%d\twith undetermined coefficients\n",
3150 stats->nb_undetermined);
3151 fprintf (file, "-----------------------------------------\n");
3152 fprintf (file, "%d\tchrecs in the scev database\n",
3153 (int) scalar_evolution_info->elements ());
3154 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3155 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3156 fprintf (file, "-----------------------------------------\n");
3157 fprintf (file, ")\n\n");
3160 /* Gather statistics about CHREC. */
3162 static void
3163 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3165 if (dump_file && (dump_flags & TDF_STATS))
3167 fprintf (dump_file, "(classify_chrec ");
3168 print_generic_expr (dump_file, chrec, 0);
3169 fprintf (dump_file, "\n");
3172 stats->nb_chrecs++;
3174 if (chrec == NULL_TREE)
3176 stats->nb_undetermined++;
3177 return;
3180 switch (TREE_CODE (chrec))
3182 case POLYNOMIAL_CHREC:
3183 if (evolution_function_is_affine_p (chrec))
3185 if (dump_file && (dump_flags & TDF_STATS))
3186 fprintf (dump_file, " affine_univariate\n");
3187 stats->nb_affine++;
3189 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3191 if (dump_file && (dump_flags & TDF_STATS))
3192 fprintf (dump_file, " affine_multivariate\n");
3193 stats->nb_affine_multivar++;
3195 else
3197 if (dump_file && (dump_flags & TDF_STATS))
3198 fprintf (dump_file, " higher_degree_polynomial\n");
3199 stats->nb_higher_poly++;
3202 break;
3204 default:
3205 break;
3208 if (chrec_contains_undetermined (chrec))
3210 if (dump_file && (dump_flags & TDF_STATS))
3211 fprintf (dump_file, " undetermined\n");
3212 stats->nb_undetermined++;
3215 if (dump_file && (dump_flags & TDF_STATS))
3216 fprintf (dump_file, ")\n");
3219 /* Classify the chrecs of the whole database. */
3221 void
3222 gather_stats_on_scev_database (void)
3224 struct chrec_stats stats;
3226 if (!dump_file)
3227 return;
3229 reset_chrecs_counters (&stats);
3231 hash_table<scev_info_hasher>::iterator iter;
3232 scev_info_str *elt;
3233 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3234 iter)
3235 gather_chrec_stats (elt->chrec, &stats);
3237 dump_chrecs_stats (dump_file, &stats);
3242 /* Initializer. */
3244 static void
3245 initialize_scalar_evolutions_analyzer (void)
3247 /* The elements below are unique. */
3248 if (chrec_dont_know == NULL_TREE)
3250 chrec_not_analyzed_yet = NULL_TREE;
3251 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3252 chrec_known = make_node (SCEV_KNOWN);
3253 TREE_TYPE (chrec_dont_know) = void_type_node;
3254 TREE_TYPE (chrec_known) = void_type_node;
3258 /* Initialize the analysis of scalar evolutions for LOOPS. */
3260 void
3261 scev_initialize (void)
3263 struct loop *loop;
3265 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3267 initialize_scalar_evolutions_analyzer ();
3269 FOR_EACH_LOOP (loop, 0)
3271 loop->nb_iterations = NULL_TREE;
3275 /* Return true if SCEV is initialized. */
3277 bool
3278 scev_initialized_p (void)
3280 return scalar_evolution_info != NULL;
3283 /* Cleans up the information cached by the scalar evolutions analysis
3284 in the hash table. */
3286 void
3287 scev_reset_htab (void)
3289 if (!scalar_evolution_info)
3290 return;
3292 scalar_evolution_info->empty ();
3295 /* Cleans up the information cached by the scalar evolutions analysis
3296 in the hash table and in the loop->nb_iterations. */
3298 void
3299 scev_reset (void)
3301 struct loop *loop;
3303 scev_reset_htab ();
3305 FOR_EACH_LOOP (loop, 0)
3307 loop->nb_iterations = NULL_TREE;
3311 /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3312 of the upper bound on the number of iterations of LOOP, the BASE and STEP
3313 of IV.
3315 We do not use information whether TYPE can overflow so it is safe to
3316 use this test even for derived IVs not computed every iteration or
3317 hypotetical IVs to be inserted into code. */
3319 bool
3320 iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
3322 widest_int nit;
3323 wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3324 signop sgn = TYPE_SIGN (type);
3326 if (integer_zerop (step))
3327 return false;
3329 if (TREE_CODE (base) == INTEGER_CST)
3330 base_min = base_max = base;
3331 else if (TREE_CODE (base) == SSA_NAME
3332 && INTEGRAL_TYPE_P (TREE_TYPE (base))
3333 && get_range_info (base, &base_min, &base_max) == VR_RANGE)
3335 else
3336 return true;
3338 if (TREE_CODE (step) == INTEGER_CST)
3339 step_min = step_max = step;
3340 else if (TREE_CODE (step) == SSA_NAME
3341 && INTEGRAL_TYPE_P (TREE_TYPE (step))
3342 && get_range_info (step, &step_min, &step_max) == VR_RANGE)
3344 else
3345 return true;
3347 if (!get_max_loop_iterations (loop, &nit))
3348 return true;
3350 type_min = wi::min_value (type);
3351 type_max = wi::max_value (type);
3353 /* Just sanity check that we don't see values out of the range of the type.
3354 In this case the arithmetics bellow would overflow. */
3355 gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3356 && wi::le_p (base_max, type_max, sgn));
3358 /* Account the possible increment in the last ieration. */
3359 bool overflow = false;
3360 nit = wi::add (nit, 1, SIGNED, &overflow);
3361 if (overflow)
3362 return true;
3364 /* NIT is typeless and can exceed the precision of the type. In this case
3365 overflow is always possible, because we know STEP is non-zero. */
3366 if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3367 return true;
3368 wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3370 /* If step can be positive, check that nit*step <= type_max-base.
3371 This can be done by unsigned arithmetic and we only need to watch overflow
3372 in the multiplication. The right hand side can always be represented in
3373 the type. */
3374 if (sgn == UNSIGNED || !wi::neg_p (step_max))
3376 bool overflow = false;
3377 if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3378 type_max - base_max)
3379 || overflow)
3380 return true;
3382 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3383 if (sgn == SIGNED && wi::neg_p (step_min))
3385 bool overflow = false, overflow2 = false;
3386 if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3387 nit2, UNSIGNED, &overflow),
3388 base_min - type_min)
3389 || overflow || overflow2)
3390 return true;
3393 return false;
3396 /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3397 function tries to derive condition under which it can be simplified
3398 into "{(type)inner_base, (type)inner_step}_loop". The condition is
3399 the maximum number that inner iv can iterate. */
3401 static tree
3402 derive_simple_iv_with_niters (tree ev, tree *niters)
3404 if (!CONVERT_EXPR_P (ev))
3405 return ev;
3407 tree inner_ev = TREE_OPERAND (ev, 0);
3408 if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3409 return ev;
3411 tree init = CHREC_LEFT (inner_ev);
3412 tree step = CHREC_RIGHT (inner_ev);
3413 if (TREE_CODE (init) != INTEGER_CST
3414 || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3415 return ev;
3417 tree type = TREE_TYPE (ev);
3418 tree inner_type = TREE_TYPE (inner_ev);
3419 if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3420 return ev;
3422 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3423 folded only if inner iv won't overflow. We compute the maximum
3424 number the inner iv can iterate before overflowing and return the
3425 simplified affine iv. */
3426 tree delta;
3427 init = fold_convert (type, init);
3428 step = fold_convert (type, step);
3429 ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3430 if (tree_int_cst_sign_bit (step))
3432 tree bound = lower_bound_in_type (inner_type, inner_type);
3433 delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3434 step = fold_build1 (NEGATE_EXPR, type, step);
3436 else
3438 tree bound = upper_bound_in_type (inner_type, inner_type);
3439 delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3441 *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3442 return ev;
3445 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3446 respect to WRTO_LOOP and returns its base and step in IV if possible
3447 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3448 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3449 invariant in LOOP. Otherwise we require it to be an integer constant.
3451 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3452 because it is computed in signed arithmetics). Consequently, adding an
3453 induction variable
3455 for (i = IV->base; ; i += IV->step)
3457 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3458 false for the type of the induction variable, or you can prove that i does
3459 not wrap by some other argument. Otherwise, this might introduce undefined
3460 behavior, and
3462 i = iv->base;
3463 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3465 must be used instead.
3467 When IV_NITERS is not NULL, this function also checks case in which OP
3468 is a conversion of an inner simple iv of below form:
3470 (outer_type){inner_base, inner_step}_loop.
3472 If type of inner iv has smaller precision than outer_type, it can't be
3473 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3474 the inner iv could overflow/wrap. In this case, we derive a condition
3475 under which the inner iv won't overflow/wrap and do the simplification.
3476 The derived condition normally is the maximum number the inner iv can
3477 iterate, and will be stored in IV_NITERS. This is useful in loop niter
3478 analysis, to derive break conditions when a loop must terminate, when is
3479 infinite. */
3481 bool
3482 simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop,
3483 tree op, affine_iv *iv, tree *iv_niters,
3484 bool allow_nonconstant_step)
3486 enum tree_code code;
3487 tree type, ev, base, e;
3488 wide_int extreme;
3489 bool folded_casts, overflow;
3491 iv->base = NULL_TREE;
3492 iv->step = NULL_TREE;
3493 iv->no_overflow = false;
3495 type = TREE_TYPE (op);
3496 if (!POINTER_TYPE_P (type)
3497 && !INTEGRAL_TYPE_P (type))
3498 return false;
3500 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3501 &folded_casts);
3502 if (chrec_contains_undetermined (ev)
3503 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3504 return false;
3506 if (tree_does_not_contain_chrecs (ev))
3508 iv->base = ev;
3509 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3510 iv->no_overflow = true;
3511 return true;
3514 /* If we can derive valid scalar evolution with assumptions. */
3515 if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3516 ev = derive_simple_iv_with_niters (ev, iv_niters);
3518 if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3519 return false;
3521 if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3522 return false;
3524 iv->step = CHREC_RIGHT (ev);
3525 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3526 || tree_contains_chrecs (iv->step, NULL))
3527 return false;
3529 iv->base = CHREC_LEFT (ev);
3530 if (tree_contains_chrecs (iv->base, NULL))
3531 return false;
3533 iv->no_overflow = !folded_casts && nowrap_type_p (type);
3535 if (!iv->no_overflow
3536 && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3537 iv->no_overflow = true;
3539 /* Try to simplify iv base:
3541 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3542 == (signed T)(unsigned T)base + step
3543 == base + step
3545 If we can prove operation (base + step) doesn't overflow or underflow.
3546 Specifically, we try to prove below conditions are satisfied:
3548 base <= UPPER_BOUND (type) - step ;;step > 0
3549 base >= LOWER_BOUND (type) - step ;;step < 0
3551 This is done by proving the reverse conditions are false using loop's
3552 initial conditions.
3554 The is necessary to make loop niter, or iv overflow analysis easier
3555 for below example:
3557 int foo (int *a, signed char s, signed char l)
3559 signed char i;
3560 for (i = s; i < l; i++)
3561 a[i] = 0;
3562 return 0;
3565 Note variable I is firstly converted to type unsigned char, incremented,
3566 then converted back to type signed char. */
3568 if (wrto_loop->num != use_loop->num)
3569 return true;
3571 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3572 return true;
3574 type = TREE_TYPE (iv->base);
3575 e = TREE_OPERAND (iv->base, 0);
3576 if (TREE_CODE (e) != PLUS_EXPR
3577 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3578 || !tree_int_cst_equal (iv->step,
3579 fold_convert (type, TREE_OPERAND (e, 1))))
3580 return true;
3581 e = TREE_OPERAND (e, 0);
3582 if (!CONVERT_EXPR_P (e))
3583 return true;
3584 base = TREE_OPERAND (e, 0);
3585 if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3586 return true;
3588 if (tree_int_cst_sign_bit (iv->step))
3590 code = LT_EXPR;
3591 extreme = wi::min_value (type);
3593 else
3595 code = GT_EXPR;
3596 extreme = wi::max_value (type);
3598 overflow = false;
3599 extreme = wi::sub (extreme, iv->step, TYPE_SIGN (type), &overflow);
3600 if (overflow)
3601 return true;
3602 e = fold_build2 (code, boolean_type_node, base,
3603 wide_int_to_tree (type, extreme));
3604 e = simplify_using_initial_conditions (use_loop, e);
3605 if (!integer_zerop (e))
3606 return true;
3608 if (POINTER_TYPE_P (TREE_TYPE (base)))
3609 code = POINTER_PLUS_EXPR;
3610 else
3611 code = PLUS_EXPR;
3613 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3614 return true;
3617 /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3618 affine iv unconditionally. */
3620 bool
3621 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3622 affine_iv *iv, bool allow_nonconstant_step)
3624 return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3625 NULL, allow_nonconstant_step);
3628 /* Finalize the scalar evolution analysis. */
3630 void
3631 scev_finalize (void)
3633 if (!scalar_evolution_info)
3634 return;
3635 scalar_evolution_info->empty ();
3636 scalar_evolution_info = NULL;
3639 /* Returns true if the expression EXPR is considered to be too expensive
3640 for scev_const_prop. */
3642 bool
3643 expression_expensive_p (tree expr)
3645 enum tree_code code;
3647 if (is_gimple_val (expr))
3648 return false;
3650 code = TREE_CODE (expr);
3651 if (code == TRUNC_DIV_EXPR
3652 || code == CEIL_DIV_EXPR
3653 || code == FLOOR_DIV_EXPR
3654 || code == ROUND_DIV_EXPR
3655 || code == TRUNC_MOD_EXPR
3656 || code == CEIL_MOD_EXPR
3657 || code == FLOOR_MOD_EXPR
3658 || code == ROUND_MOD_EXPR
3659 || code == EXACT_DIV_EXPR)
3661 /* Division by power of two is usually cheap, so we allow it.
3662 Forbid anything else. */
3663 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3664 return true;
3667 switch (TREE_CODE_CLASS (code))
3669 case tcc_binary:
3670 case tcc_comparison:
3671 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3672 return true;
3674 /* Fallthru. */
3675 case tcc_unary:
3676 return expression_expensive_p (TREE_OPERAND (expr, 0));
3678 default:
3679 return true;
3683 /* Do final value replacement for LOOP. */
3685 void
3686 final_value_replacement_loop (struct loop *loop)
3688 /* If we do not know exact number of iterations of the loop, we cannot
3689 replace the final value. */
3690 edge exit = single_exit (loop);
3691 if (!exit)
3692 return;
3694 tree niter = number_of_latch_executions (loop);
3695 if (niter == chrec_dont_know)
3696 return;
3698 /* Ensure that it is possible to insert new statements somewhere. */
3699 if (!single_pred_p (exit->dest))
3700 split_loop_exit_edge (exit);
3702 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3703 gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
3705 struct loop *ex_loop
3706 = superloop_at_depth (loop,
3707 loop_depth (exit->dest->loop_father) + 1);
3709 gphi_iterator psi;
3710 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3712 gphi *phi = psi.phi ();
3713 tree rslt = PHI_RESULT (phi);
3714 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3715 if (virtual_operand_p (def))
3717 gsi_next (&psi);
3718 continue;
3721 if (!POINTER_TYPE_P (TREE_TYPE (def))
3722 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3724 gsi_next (&psi);
3725 continue;
3728 bool folded_casts;
3729 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3730 &folded_casts);
3731 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3732 if (!tree_does_not_contain_chrecs (def)
3733 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3734 /* Moving the computation from the loop may prolong life range
3735 of some ssa names, which may cause problems if they appear
3736 on abnormal edges. */
3737 || contains_abnormal_ssa_name_p (def)
3738 /* Do not emit expensive expressions. The rationale is that
3739 when someone writes a code like
3741 while (n > 45) n -= 45;
3743 he probably knows that n is not large, and does not want it
3744 to be turned into n %= 45. */
3745 || expression_expensive_p (def))
3747 if (dump_file && (dump_flags & TDF_DETAILS))
3749 fprintf (dump_file, "not replacing:\n ");
3750 print_gimple_stmt (dump_file, phi, 0, 0);
3751 fprintf (dump_file, "\n");
3753 gsi_next (&psi);
3754 continue;
3757 /* Eliminate the PHI node and replace it by a computation outside
3758 the loop. */
3759 if (dump_file)
3761 fprintf (dump_file, "\nfinal value replacement:\n ");
3762 print_gimple_stmt (dump_file, phi, 0, 0);
3763 fprintf (dump_file, " with\n ");
3765 def = unshare_expr (def);
3766 remove_phi_node (&psi, false);
3768 /* If def's type has undefined overflow and there were folded
3769 casts, rewrite all stmts added for def into arithmetics
3770 with defined overflow behavior. */
3771 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3772 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3774 gimple_seq stmts;
3775 gimple_stmt_iterator gsi2;
3776 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3777 gsi2 = gsi_start (stmts);
3778 while (!gsi_end_p (gsi2))
3780 gimple *stmt = gsi_stmt (gsi2);
3781 gimple_stmt_iterator gsi3 = gsi2;
3782 gsi_next (&gsi2);
3783 gsi_remove (&gsi3, false);
3784 if (is_gimple_assign (stmt)
3785 && arith_code_with_undefined_signed_overflow
3786 (gimple_assign_rhs_code (stmt)))
3787 gsi_insert_seq_before (&gsi,
3788 rewrite_to_defined_overflow (stmt),
3789 GSI_SAME_STMT);
3790 else
3791 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3794 else
3795 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3796 true, GSI_SAME_STMT);
3798 gassign *ass = gimple_build_assign (rslt, def);
3799 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3800 if (dump_file)
3802 print_gimple_stmt (dump_file, ass, 0, 0);
3803 fprintf (dump_file, "\n");
3808 /* Replace ssa names for that scev can prove they are constant by the
3809 appropriate constants. Also perform final value replacement in loops,
3810 in case the replacement expressions are cheap.
3812 We only consider SSA names defined by phi nodes; rest is left to the
3813 ordinary constant propagation pass. */
3815 unsigned int
3816 scev_const_prop (void)
3818 basic_block bb;
3819 tree name, type, ev;
3820 gphi *phi;
3821 struct loop *loop;
3822 bitmap ssa_names_to_remove = NULL;
3823 unsigned i;
3824 gphi_iterator psi;
3826 if (number_of_loops (cfun) <= 1)
3827 return 0;
3829 FOR_EACH_BB_FN (bb, cfun)
3831 loop = bb->loop_father;
3833 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3835 phi = psi.phi ();
3836 name = PHI_RESULT (phi);
3838 if (virtual_operand_p (name))
3839 continue;
3841 type = TREE_TYPE (name);
3843 if (!POINTER_TYPE_P (type)
3844 && !INTEGRAL_TYPE_P (type))
3845 continue;
3847 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3848 NULL);
3849 if (!is_gimple_min_invariant (ev)
3850 || !may_propagate_copy (name, ev))
3851 continue;
3853 /* Replace the uses of the name. */
3854 if (name != ev)
3856 if (dump_file && (dump_flags & TDF_DETAILS))
3858 fprintf (dump_file, "Replacing uses of: ");
3859 print_generic_expr (dump_file, name, 0);
3860 fprintf (dump_file, " with: ");
3861 print_generic_expr (dump_file, ev, 0);
3862 fprintf (dump_file, "\n");
3864 replace_uses_by (name, ev);
3867 if (!ssa_names_to_remove)
3868 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3869 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3873 /* Remove the ssa names that were replaced by constants. We do not
3874 remove them directly in the previous cycle, since this
3875 invalidates scev cache. */
3876 if (ssa_names_to_remove)
3878 bitmap_iterator bi;
3880 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3882 gimple_stmt_iterator psi;
3883 name = ssa_name (i);
3884 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3886 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3887 psi = gsi_for_stmt (phi);
3888 remove_phi_node (&psi, true);
3891 BITMAP_FREE (ssa_names_to_remove);
3892 scev_reset ();
3895 /* Now the regular final value replacement. */
3896 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3897 final_value_replacement_loop (loop);
3899 return 0;
3902 #include "gt-tree-scalar-evolution.h"