Daily bump.
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobcc80794c5d9cab5d0f42ca51b0cdb033ca377c62
1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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/>. */
21 /*
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_MODIFY_STMT: 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 ({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 2: 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 3: Higher degree polynomials.
159 | loop_1
160 | a = phi (2, b)
161 | c = phi (5, d)
162 | b = a + 1
163 | d = c + a
164 | endloop
166 a -> {2, +, 1}_1
167 b -> {3, +, 1}_1
168 c -> {5, +, a}_1
169 d -> {5 + a, +, a}_1
171 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
172 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
174 Example 4: Lucas, Fibonacci, or mixers in general.
176 | loop_1
177 | a = phi (1, b)
178 | c = phi (3, d)
179 | b = c
180 | d = c + a
181 | endloop
183 a -> (1, c)_1
184 c -> {3, +, a}_1
186 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
187 following semantics: during the first iteration of the loop_1, the
188 variable contains the value 1, and then it contains the value "c".
189 Note that this syntax is close to the syntax of the loop-phi-node:
190 "a -> (1, c)_1" vs. "a = phi (1, c)".
192 The symbolic chrec representation contains all the semantics of the
193 original code. What is more difficult is to use this information.
195 Example 5: Flip-flops, or exchangers.
197 | loop_1
198 | a = phi (1, b)
199 | c = phi (3, d)
200 | b = c
201 | d = a
202 | endloop
204 a -> (1, c)_1
205 c -> (3, a)_1
207 Based on these symbolic chrecs, it is possible to refine this
208 information into the more precise PERIODIC_CHRECs:
210 a -> |1, 3|_1
211 c -> |3, 1|_1
213 This transformation is not yet implemented.
215 Further readings:
217 You can find a more detailed description of the algorithm in:
218 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
220 this is a preliminary report and some of the details of the
221 algorithm have changed. I'm working on a research report that
222 updates the description of the algorithms to reflect the design
223 choices used in this implementation.
225 A set of slides show a high level overview of the algorithm and run
226 an example through the scalar evolution analyzer:
227 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
229 The slides that I have presented at the GCC Summit'04 are available
230 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
233 #include "config.h"
234 #include "system.h"
235 #include "coretypes.h"
236 #include "tm.h"
237 #include "ggc.h"
238 #include "tree.h"
239 #include "real.h"
241 /* These RTL headers are needed for basic-block.h. */
242 #include "rtl.h"
243 #include "basic-block.h"
244 #include "diagnostic.h"
245 #include "tree-flow.h"
246 #include "tree-dump.h"
247 #include "timevar.h"
248 #include "cfgloop.h"
249 #include "tree-chrec.h"
250 #include "tree-scalar-evolution.h"
251 #include "tree-pass.h"
252 #include "flags.h"
253 #include "params.h"
255 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257 /* The cached information about a ssa name VAR, claiming that inside LOOP,
258 the value of VAR can be expressed as CHREC. */
260 struct scev_info_str GTY(())
262 tree var;
263 tree chrec;
266 /* Counters for the scev database. */
267 static unsigned nb_set_scev = 0;
268 static unsigned nb_get_scev = 0;
270 /* The following trees are unique elements. Thus the comparison of
271 another element to these elements should be done on the pointer to
272 these trees, and not on their value. */
274 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
275 tree chrec_not_analyzed_yet;
277 /* Reserved to the cases where the analyzer has detected an
278 undecidable property at compile time. */
279 tree chrec_dont_know;
281 /* When the analyzer has detected that a property will never
282 happen, then it qualifies it with chrec_known. */
283 tree chrec_known;
285 static bitmap already_instantiated;
287 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
290 /* Constructs a new SCEV_INFO_STR structure. */
292 static inline struct scev_info_str *
293 new_scev_info_str (tree var)
295 struct scev_info_str *res;
297 res = GGC_NEW (struct scev_info_str);
298 res->var = var;
299 res->chrec = chrec_not_analyzed_yet;
301 return res;
304 /* Computes a hash function for database element ELT. */
306 static hashval_t
307 hash_scev_info (const void *elt)
309 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
312 /* Compares database elements E1 and E2. */
314 static int
315 eq_scev_info (const void *e1, const void *e2)
317 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
318 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
320 return elt1->var == elt2->var;
323 /* Deletes database element E. */
325 static void
326 del_scev_info (void *e)
328 ggc_free (e);
331 /* Get the index corresponding to VAR in the current LOOP. If
332 it's the first time we ask for this VAR, then we return
333 chrec_not_analyzed_yet for this VAR and return its index. */
335 static tree *
336 find_var_scev_info (tree var)
338 struct scev_info_str *res;
339 struct scev_info_str tmp;
340 PTR *slot;
342 tmp.var = var;
343 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
345 if (!*slot)
346 *slot = new_scev_info_str (var);
347 res = (struct scev_info_str *) *slot;
349 return &res->chrec;
352 /* Return true when CHREC contains symbolic names defined in
353 LOOP_NB. */
355 bool
356 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
358 int i, n;
360 if (chrec == NULL_TREE)
361 return false;
363 if (TREE_INVARIANT (chrec))
364 return false;
366 if (TREE_CODE (chrec) == VAR_DECL
367 || TREE_CODE (chrec) == PARM_DECL
368 || TREE_CODE (chrec) == FUNCTION_DECL
369 || TREE_CODE (chrec) == LABEL_DECL
370 || TREE_CODE (chrec) == RESULT_DECL
371 || TREE_CODE (chrec) == FIELD_DECL)
372 return true;
374 if (TREE_CODE (chrec) == SSA_NAME)
376 tree def = SSA_NAME_DEF_STMT (chrec);
377 struct loop *def_loop = loop_containing_stmt (def);
378 struct loop *loop = get_loop (loop_nb);
380 if (def_loop == NULL)
381 return false;
383 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
384 return true;
386 return false;
389 n = TREE_OPERAND_LENGTH (chrec);
390 for (i = 0; i < n; i++)
391 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
392 loop_nb))
393 return true;
394 return false;
397 /* Return true when PHI is a loop-phi-node. */
399 static bool
400 loop_phi_node_p (tree phi)
402 /* The implementation of this function is based on the following
403 property: "all the loop-phi-nodes of a loop are contained in the
404 loop's header basic block". */
406 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
409 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
410 In general, in the case of multivariate evolutions we want to get
411 the evolution in different loops. LOOP specifies the level for
412 which to get the evolution.
414 Example:
416 | for (j = 0; j < 100; j++)
418 | for (k = 0; k < 100; k++)
420 | i = k + j; - Here the value of i is a function of j, k.
422 | ... = i - Here the value of i is a function of j.
424 | ... = i - Here the value of i is a scalar.
426 Example:
428 | i_0 = ...
429 | loop_1 10 times
430 | i_1 = phi (i_0, i_2)
431 | i_2 = i_1 + 2
432 | endloop
434 This loop has the same effect as:
435 LOOP_1 has the same effect as:
437 | i_1 = i_0 + 20
439 The overall effect of the loop, "i_0 + 20" in the previous example,
440 is obtained by passing in the parameters: LOOP = 1,
441 EVOLUTION_FN = {i_0, +, 2}_1.
444 static tree
445 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
447 bool val = false;
449 if (evolution_fn == chrec_dont_know)
450 return chrec_dont_know;
452 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
454 struct loop *inner_loop = get_chrec_loop (evolution_fn);
456 if (inner_loop == loop
457 || flow_loop_nested_p (loop, inner_loop))
459 tree nb_iter = number_of_latch_executions (inner_loop);
461 if (nb_iter == chrec_dont_know)
462 return chrec_dont_know;
463 else
465 tree res;
467 /* evolution_fn is the evolution function in LOOP. Get
468 its value in the nb_iter-th iteration. */
469 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
471 /* Continue the computation until ending on a parent of LOOP. */
472 return compute_overall_effect_of_inner_loop (loop, res);
475 else
476 return evolution_fn;
479 /* If the evolution function is an invariant, there is nothing to do. */
480 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
481 return evolution_fn;
483 else
484 return chrec_dont_know;
487 /* Determine whether the CHREC is always positive/negative. If the expression
488 cannot be statically analyzed, return false, otherwise set the answer into
489 VALUE. */
491 bool
492 chrec_is_positive (tree chrec, bool *value)
494 bool value0, value1, value2;
495 tree end_value, nb_iter;
497 switch (TREE_CODE (chrec))
499 case POLYNOMIAL_CHREC:
500 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
501 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
502 return false;
504 /* FIXME -- overflows. */
505 if (value0 == value1)
507 *value = value0;
508 return true;
511 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
512 and the proof consists in showing that the sign never
513 changes during the execution of the loop, from 0 to
514 loop->nb_iterations. */
515 if (!evolution_function_is_affine_p (chrec))
516 return false;
518 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
519 if (chrec_contains_undetermined (nb_iter))
520 return false;
522 #if 0
523 /* TODO -- If the test is after the exit, we may decrease the number of
524 iterations by one. */
525 if (after_exit)
526 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
527 #endif
529 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
531 if (!chrec_is_positive (end_value, &value2))
532 return false;
534 *value = value0;
535 return value0 == value1;
537 case INTEGER_CST:
538 *value = (tree_int_cst_sgn (chrec) == 1);
539 return true;
541 default:
542 return false;
546 /* Associate CHREC to SCALAR. */
548 static void
549 set_scalar_evolution (tree scalar, tree chrec)
551 tree *scalar_info;
553 if (TREE_CODE (scalar) != SSA_NAME)
554 return;
556 scalar_info = find_var_scev_info (scalar);
558 if (dump_file)
560 if (dump_flags & TDF_DETAILS)
562 fprintf (dump_file, "(set_scalar_evolution \n");
563 fprintf (dump_file, " (scalar = ");
564 print_generic_expr (dump_file, scalar, 0);
565 fprintf (dump_file, ")\n (scalar_evolution = ");
566 print_generic_expr (dump_file, chrec, 0);
567 fprintf (dump_file, "))\n");
569 if (dump_flags & TDF_STATS)
570 nb_set_scev++;
573 *scalar_info = chrec;
576 /* Retrieve the chrec associated to SCALAR in the LOOP. */
578 static tree
579 get_scalar_evolution (tree scalar)
581 tree res;
583 if (dump_file)
585 if (dump_flags & TDF_DETAILS)
587 fprintf (dump_file, "(get_scalar_evolution \n");
588 fprintf (dump_file, " (scalar = ");
589 print_generic_expr (dump_file, scalar, 0);
590 fprintf (dump_file, ")\n");
592 if (dump_flags & TDF_STATS)
593 nb_get_scev++;
596 switch (TREE_CODE (scalar))
598 case SSA_NAME:
599 res = *find_var_scev_info (scalar);
600 break;
602 case REAL_CST:
603 case FIXED_CST:
604 case INTEGER_CST:
605 res = scalar;
606 break;
608 default:
609 res = chrec_not_analyzed_yet;
610 break;
613 if (dump_file && (dump_flags & TDF_DETAILS))
615 fprintf (dump_file, " (scalar_evolution = ");
616 print_generic_expr (dump_file, res, 0);
617 fprintf (dump_file, "))\n");
620 return res;
623 /* Helper function for add_to_evolution. Returns the evolution
624 function for an assignment of the form "a = b + c", where "a" and
625 "b" are on the strongly connected component. CHREC_BEFORE is the
626 information that we already have collected up to this point.
627 TO_ADD is the evolution of "c".
629 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
630 evolution the expression TO_ADD, otherwise construct an evolution
631 part for this loop. */
633 static tree
634 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
635 tree at_stmt)
637 tree type, left, right;
638 struct loop *loop = get_loop (loop_nb), *chloop;
640 switch (TREE_CODE (chrec_before))
642 case POLYNOMIAL_CHREC:
643 chloop = get_chrec_loop (chrec_before);
644 if (chloop == loop
645 || flow_loop_nested_p (chloop, loop))
647 unsigned var;
649 type = chrec_type (chrec_before);
651 /* When there is no evolution part in this loop, build it. */
652 if (chloop != loop)
654 var = loop_nb;
655 left = chrec_before;
656 right = SCALAR_FLOAT_TYPE_P (type)
657 ? build_real (type, dconst0)
658 : build_int_cst (type, 0);
660 else
662 var = CHREC_VARIABLE (chrec_before);
663 left = CHREC_LEFT (chrec_before);
664 right = CHREC_RIGHT (chrec_before);
667 to_add = chrec_convert (type, to_add, at_stmt);
668 right = chrec_convert_rhs (type, right, at_stmt);
669 right = chrec_fold_plus (chrec_type (right), right, to_add);
670 return build_polynomial_chrec (var, left, right);
672 else
674 gcc_assert (flow_loop_nested_p (loop, chloop));
676 /* Search the evolution in LOOP_NB. */
677 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
678 to_add, at_stmt);
679 right = CHREC_RIGHT (chrec_before);
680 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
681 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
682 left, right);
685 default:
686 /* These nodes do not depend on a loop. */
687 if (chrec_before == chrec_dont_know)
688 return chrec_dont_know;
690 left = chrec_before;
691 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
692 return build_polynomial_chrec (loop_nb, left, right);
696 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
697 of LOOP_NB.
699 Description (provided for completeness, for those who read code in
700 a plane, and for my poor 62 bytes brain that would have forgotten
701 all this in the next two or three months):
703 The algorithm of translation of programs from the SSA representation
704 into the chrecs syntax is based on a pattern matching. After having
705 reconstructed the overall tree expression for a loop, there are only
706 two cases that can arise:
708 1. a = loop-phi (init, a + expr)
709 2. a = loop-phi (init, expr)
711 where EXPR is either a scalar constant with respect to the analyzed
712 loop (this is a degree 0 polynomial), or an expression containing
713 other loop-phi definitions (these are higher degree polynomials).
715 Examples:
718 | init = ...
719 | loop_1
720 | a = phi (init, a + 5)
721 | endloop
724 | inita = ...
725 | initb = ...
726 | loop_1
727 | a = phi (inita, 2 * b + 3)
728 | b = phi (initb, b + 1)
729 | endloop
731 For the first case, the semantics of the SSA representation is:
733 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
735 that is, there is a loop index "x" that determines the scalar value
736 of the variable during the loop execution. During the first
737 iteration, the value is that of the initial condition INIT, while
738 during the subsequent iterations, it is the sum of the initial
739 condition with the sum of all the values of EXPR from the initial
740 iteration to the before last considered iteration.
742 For the second case, the semantics of the SSA program is:
744 | a (x) = init, if x = 0;
745 | expr (x - 1), otherwise.
747 The second case corresponds to the PEELED_CHREC, whose syntax is
748 close to the syntax of a loop-phi-node:
750 | phi (init, expr) vs. (init, expr)_x
752 The proof of the translation algorithm for the first case is a
753 proof by structural induction based on the degree of EXPR.
755 Degree 0:
756 When EXPR is a constant with respect to the analyzed loop, or in
757 other words when EXPR is a polynomial of degree 0, the evolution of
758 the variable A in the loop is an affine function with an initial
759 condition INIT, and a step EXPR. In order to show this, we start
760 from the semantics of the SSA representation:
762 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
764 and since "expr (j)" is a constant with respect to "j",
766 f (x) = init + x * expr
768 Finally, based on the semantics of the pure sum chrecs, by
769 identification we get the corresponding chrecs syntax:
771 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
772 f (x) -> {init, +, expr}_x
774 Higher degree:
775 Suppose that EXPR is a polynomial of degree N with respect to the
776 analyzed loop_x for which we have already determined that it is
777 written under the chrecs syntax:
779 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
781 We start from the semantics of the SSA program:
783 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
785 | f (x) = init + \sum_{j = 0}^{x - 1}
786 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
788 | f (x) = init + \sum_{j = 0}^{x - 1}
789 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
791 | f (x) = init + \sum_{k = 0}^{n - 1}
792 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
794 | f (x) = init + \sum_{k = 0}^{n - 1}
795 | (b_k * \binom{x}{k + 1})
797 | f (x) = init + b_0 * \binom{x}{1} + ...
798 | + b_{n-1} * \binom{x}{n}
800 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
801 | + b_{n-1} * \binom{x}{n}
804 And finally from the definition of the chrecs syntax, we identify:
805 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
807 This shows the mechanism that stands behind the add_to_evolution
808 function. An important point is that the use of symbolic
809 parameters avoids the need of an analysis schedule.
811 Example:
813 | inita = ...
814 | initb = ...
815 | loop_1
816 | a = phi (inita, a + 2 + b)
817 | b = phi (initb, b + 1)
818 | endloop
820 When analyzing "a", the algorithm keeps "b" symbolically:
822 | a -> {inita, +, 2 + b}_1
824 Then, after instantiation, the analyzer ends on the evolution:
826 | a -> {inita, +, 2 + initb, +, 1}_1
830 static tree
831 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
832 tree to_add, tree at_stmt)
834 tree type = chrec_type (to_add);
835 tree res = NULL_TREE;
837 if (to_add == NULL_TREE)
838 return chrec_before;
840 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
841 instantiated at this point. */
842 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
843 /* This should not happen. */
844 return chrec_dont_know;
846 if (dump_file && (dump_flags & TDF_DETAILS))
848 fprintf (dump_file, "(add_to_evolution \n");
849 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
850 fprintf (dump_file, " (chrec_before = ");
851 print_generic_expr (dump_file, chrec_before, 0);
852 fprintf (dump_file, ")\n (to_add = ");
853 print_generic_expr (dump_file, to_add, 0);
854 fprintf (dump_file, ")\n");
857 if (code == MINUS_EXPR)
858 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
859 ? build_real (type, dconstm1)
860 : build_int_cst_type (type, -1));
862 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
864 if (dump_file && (dump_flags & TDF_DETAILS))
866 fprintf (dump_file, " (res = ");
867 print_generic_expr (dump_file, res, 0);
868 fprintf (dump_file, "))\n");
871 return res;
874 /* Helper function. */
876 static inline tree
877 set_nb_iterations_in_loop (struct loop *loop,
878 tree res)
880 if (dump_file && (dump_flags & TDF_DETAILS))
882 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
883 print_generic_expr (dump_file, res, 0);
884 fprintf (dump_file, "))\n");
887 loop->nb_iterations = res;
888 return res;
893 /* This section selects the loops that will be good candidates for the
894 scalar evolution analysis. For the moment, greedily select all the
895 loop nests we could analyze. */
897 /* Return true when it is possible to analyze the condition expression
898 EXPR. */
900 static bool
901 analyzable_condition (const_tree expr)
903 tree condition;
905 if (TREE_CODE (expr) != COND_EXPR)
906 return false;
908 condition = TREE_OPERAND (expr, 0);
910 switch (TREE_CODE (condition))
912 case SSA_NAME:
913 return true;
915 case LT_EXPR:
916 case LE_EXPR:
917 case GT_EXPR:
918 case GE_EXPR:
919 case EQ_EXPR:
920 case NE_EXPR:
921 return true;
923 default:
924 return false;
927 return false;
930 /* For a loop with a single exit edge, return the COND_EXPR that
931 guards the exit edge. If the expression is too difficult to
932 analyze, then give up. */
934 tree
935 get_loop_exit_condition (const struct loop *loop)
937 tree res = NULL_TREE;
938 edge exit_edge = single_exit (loop);
940 if (dump_file && (dump_flags & TDF_DETAILS))
941 fprintf (dump_file, "(get_loop_exit_condition \n ");
943 if (exit_edge)
945 tree expr;
947 expr = last_stmt (exit_edge->src);
948 if (analyzable_condition (expr))
949 res = expr;
952 if (dump_file && (dump_flags & TDF_DETAILS))
954 print_generic_expr (dump_file, res, 0);
955 fprintf (dump_file, ")\n");
958 return res;
961 /* Recursively determine and enqueue the exit conditions for a loop. */
963 static void
964 get_exit_conditions_rec (struct loop *loop,
965 VEC(tree,heap) **exit_conditions)
967 if (!loop)
968 return;
970 /* Recurse on the inner loops, then on the next (sibling) loops. */
971 get_exit_conditions_rec (loop->inner, exit_conditions);
972 get_exit_conditions_rec (loop->next, exit_conditions);
974 if (single_exit (loop))
976 tree loop_condition = get_loop_exit_condition (loop);
978 if (loop_condition)
979 VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
983 /* Select the candidate loop nests for the analysis. This function
984 initializes the EXIT_CONDITIONS array. */
986 static void
987 select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
989 struct loop *function_body = current_loops->tree_root;
991 get_exit_conditions_rec (function_body->inner, exit_conditions);
995 /* Depth first search algorithm. */
997 typedef enum t_bool {
998 t_false,
999 t_true,
1000 t_dont_know
1001 } t_bool;
1004 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1006 /* Follow the ssa edge into the right hand side RHS of an assignment.
1007 Return true if the strongly connected component has been found. */
1009 static t_bool
1010 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1011 tree halting_phi, tree *evolution_of_loop, int limit)
1013 t_bool res = t_false;
1014 tree rhs0, rhs1;
1015 tree type_rhs = TREE_TYPE (rhs);
1016 tree evol;
1017 enum tree_code code;
1019 /* The RHS is one of the following cases:
1020 - an SSA_NAME,
1021 - an INTEGER_CST,
1022 - a PLUS_EXPR,
1023 - a POINTER_PLUS_EXPR,
1024 - a MINUS_EXPR,
1025 - an ASSERT_EXPR,
1026 - other cases are not yet handled. */
1027 code = TREE_CODE (rhs);
1028 switch (code)
1030 case NOP_EXPR:
1031 /* This assignment is under the form "a_1 = (cast) rhs. */
1032 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1033 halting_phi, evolution_of_loop, limit);
1034 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1035 *evolution_of_loop, at_stmt);
1036 break;
1038 case INTEGER_CST:
1039 /* This assignment is under the form "a_1 = 7". */
1040 res = t_false;
1041 break;
1043 case SSA_NAME:
1044 /* This assignment is under the form: "a_1 = b_2". */
1045 res = follow_ssa_edge
1046 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1047 break;
1049 case POINTER_PLUS_EXPR:
1050 case PLUS_EXPR:
1051 /* This case is under the form "rhs0 + rhs1". */
1052 rhs0 = TREE_OPERAND (rhs, 0);
1053 rhs1 = TREE_OPERAND (rhs, 1);
1054 STRIP_TYPE_NOPS (rhs0);
1055 STRIP_TYPE_NOPS (rhs1);
1057 if (TREE_CODE (rhs0) == SSA_NAME)
1059 if (TREE_CODE (rhs1) == SSA_NAME)
1061 /* Match an assignment under the form:
1062 "a = b + c". */
1064 /* We want only assignments of form "name + name" contribute to
1065 LIMIT, as the other cases do not necessarily contribute to
1066 the complexity of the expression. */
1067 limit++;
1069 evol = *evolution_of_loop;
1070 res = follow_ssa_edge
1071 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1072 &evol, limit);
1074 if (res == t_true)
1075 *evolution_of_loop = add_to_evolution
1076 (loop->num,
1077 chrec_convert (type_rhs, evol, at_stmt),
1078 code, rhs1, at_stmt);
1080 else if (res == t_false)
1082 res = follow_ssa_edge
1083 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1084 evolution_of_loop, limit);
1086 if (res == t_true)
1087 *evolution_of_loop = add_to_evolution
1088 (loop->num,
1089 chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1090 code, rhs0, at_stmt);
1092 else if (res == t_dont_know)
1093 *evolution_of_loop = chrec_dont_know;
1096 else if (res == t_dont_know)
1097 *evolution_of_loop = chrec_dont_know;
1100 else
1102 /* Match an assignment under the form:
1103 "a = b + ...". */
1104 res = follow_ssa_edge
1105 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1106 evolution_of_loop, limit);
1107 if (res == t_true)
1108 *evolution_of_loop = add_to_evolution
1109 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1110 at_stmt),
1111 code, rhs1, at_stmt);
1113 else if (res == t_dont_know)
1114 *evolution_of_loop = chrec_dont_know;
1118 else if (TREE_CODE (rhs1) == SSA_NAME)
1120 /* Match an assignment under the form:
1121 "a = ... + c". */
1122 res = follow_ssa_edge
1123 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1124 evolution_of_loop, limit);
1125 if (res == t_true)
1126 *evolution_of_loop = add_to_evolution
1127 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1128 at_stmt),
1129 code, rhs0, at_stmt);
1131 else if (res == t_dont_know)
1132 *evolution_of_loop = chrec_dont_know;
1135 else
1136 /* Otherwise, match an assignment under the form:
1137 "a = ... + ...". */
1138 /* And there is nothing to do. */
1139 res = t_false;
1141 break;
1143 case MINUS_EXPR:
1144 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1145 rhs0 = TREE_OPERAND (rhs, 0);
1146 rhs1 = TREE_OPERAND (rhs, 1);
1147 STRIP_TYPE_NOPS (rhs0);
1148 STRIP_TYPE_NOPS (rhs1);
1150 if (TREE_CODE (rhs0) == SSA_NAME)
1152 /* Match an assignment under the form:
1153 "a = b - ...". */
1155 /* We want only assignments of form "name - name" contribute to
1156 LIMIT, as the other cases do not necessarily contribute to
1157 the complexity of the expression. */
1158 if (TREE_CODE (rhs1) == SSA_NAME)
1159 limit++;
1161 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1162 evolution_of_loop, limit);
1163 if (res == t_true)
1164 *evolution_of_loop = add_to_evolution
1165 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1166 MINUS_EXPR, rhs1, at_stmt);
1168 else if (res == t_dont_know)
1169 *evolution_of_loop = chrec_dont_know;
1171 else
1172 /* Otherwise, match an assignment under the form:
1173 "a = ... - ...". */
1174 /* And there is nothing to do. */
1175 res = t_false;
1177 break;
1179 case ASSERT_EXPR:
1181 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1182 It must be handled as a copy assignment of the form a_1 = a_2. */
1183 tree op0 = ASSERT_EXPR_VAR (rhs);
1184 if (TREE_CODE (op0) == SSA_NAME)
1185 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1186 halting_phi, evolution_of_loop, limit);
1187 else
1188 res = t_false;
1189 break;
1193 default:
1194 res = t_false;
1195 break;
1198 return res;
1201 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1203 static bool
1204 backedge_phi_arg_p (const_tree phi, int i)
1206 const_edge e = PHI_ARG_EDGE (phi, i);
1208 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1209 about updating it anywhere, and this should work as well most of the
1210 time. */
1211 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1212 return true;
1214 return false;
1217 /* Helper function for one branch of the condition-phi-node. Return
1218 true if the strongly connected component has been found following
1219 this path. */
1221 static inline t_bool
1222 follow_ssa_edge_in_condition_phi_branch (int i,
1223 struct loop *loop,
1224 tree condition_phi,
1225 tree halting_phi,
1226 tree *evolution_of_branch,
1227 tree init_cond, int limit)
1229 tree branch = PHI_ARG_DEF (condition_phi, i);
1230 *evolution_of_branch = chrec_dont_know;
1232 /* Do not follow back edges (they must belong to an irreducible loop, which
1233 we really do not want to worry about). */
1234 if (backedge_phi_arg_p (condition_phi, i))
1235 return t_false;
1237 if (TREE_CODE (branch) == SSA_NAME)
1239 *evolution_of_branch = init_cond;
1240 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1241 evolution_of_branch, limit);
1244 /* This case occurs when one of the condition branches sets
1245 the variable to a constant: i.e. a phi-node like
1246 "a_2 = PHI <a_7(5), 2(6)>;".
1248 FIXME: This case have to be refined correctly:
1249 in some cases it is possible to say something better than
1250 chrec_dont_know, for example using a wrap-around notation. */
1251 return t_false;
1254 /* This function merges the branches of a condition-phi-node in a
1255 loop. */
1257 static t_bool
1258 follow_ssa_edge_in_condition_phi (struct loop *loop,
1259 tree condition_phi,
1260 tree halting_phi,
1261 tree *evolution_of_loop, int limit)
1263 int i;
1264 tree init = *evolution_of_loop;
1265 tree evolution_of_branch;
1266 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1267 halting_phi,
1268 &evolution_of_branch,
1269 init, limit);
1270 if (res == t_false || res == t_dont_know)
1271 return res;
1273 *evolution_of_loop = evolution_of_branch;
1275 /* If the phi node is just a copy, do not increase the limit. */
1276 if (PHI_NUM_ARGS (condition_phi) > 1)
1277 limit++;
1279 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1281 /* Quickly give up when the evolution of one of the branches is
1282 not known. */
1283 if (*evolution_of_loop == chrec_dont_know)
1284 return t_true;
1286 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1287 halting_phi,
1288 &evolution_of_branch,
1289 init, limit);
1290 if (res == t_false || res == t_dont_know)
1291 return res;
1293 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1294 evolution_of_branch);
1297 return t_true;
1300 /* Follow an SSA edge in an inner loop. It computes the overall
1301 effect of the loop, and following the symbolic initial conditions,
1302 it follows the edges in the parent loop. The inner loop is
1303 considered as a single statement. */
1305 static t_bool
1306 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1307 tree loop_phi_node,
1308 tree halting_phi,
1309 tree *evolution_of_loop, int limit)
1311 struct loop *loop = loop_containing_stmt (loop_phi_node);
1312 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1314 /* Sometimes, the inner loop is too difficult to analyze, and the
1315 result of the analysis is a symbolic parameter. */
1316 if (ev == PHI_RESULT (loop_phi_node))
1318 t_bool res = t_false;
1319 int i;
1321 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1323 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1324 basic_block bb;
1326 /* Follow the edges that exit the inner loop. */
1327 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1328 if (!flow_bb_inside_loop_p (loop, bb))
1329 res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1330 arg, halting_phi,
1331 evolution_of_loop, limit);
1332 if (res == t_true)
1333 break;
1336 /* If the path crosses this loop-phi, give up. */
1337 if (res == t_true)
1338 *evolution_of_loop = chrec_dont_know;
1340 return res;
1343 /* Otherwise, compute the overall effect of the inner loop. */
1344 ev = compute_overall_effect_of_inner_loop (loop, ev);
1345 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1346 evolution_of_loop, limit);
1349 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1350 path that is analyzed on the return walk. */
1352 static t_bool
1353 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1354 tree *evolution_of_loop, int limit)
1356 struct loop *def_loop;
1358 if (TREE_CODE (def) == NOP_EXPR)
1359 return t_false;
1361 /* Give up if the path is longer than the MAX that we allow. */
1362 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1363 return t_dont_know;
1365 def_loop = loop_containing_stmt (def);
1367 switch (TREE_CODE (def))
1369 case PHI_NODE:
1370 if (!loop_phi_node_p (def))
1371 /* DEF is a condition-phi-node. Follow the branches, and
1372 record their evolutions. Finally, merge the collected
1373 information and set the approximation to the main
1374 variable. */
1375 return follow_ssa_edge_in_condition_phi
1376 (loop, def, halting_phi, evolution_of_loop, limit);
1378 /* When the analyzed phi is the halting_phi, the
1379 depth-first search is over: we have found a path from
1380 the halting_phi to itself in the loop. */
1381 if (def == halting_phi)
1382 return t_true;
1384 /* Otherwise, the evolution of the HALTING_PHI depends
1385 on the evolution of another loop-phi-node, i.e. the
1386 evolution function is a higher degree polynomial. */
1387 if (def_loop == loop)
1388 return t_false;
1390 /* Inner loop. */
1391 if (flow_loop_nested_p (loop, def_loop))
1392 return follow_ssa_edge_inner_loop_phi
1393 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1395 /* Outer loop. */
1396 return t_false;
1398 case GIMPLE_MODIFY_STMT:
1399 return follow_ssa_edge_in_rhs (loop, def,
1400 GIMPLE_STMT_OPERAND (def, 1),
1401 halting_phi,
1402 evolution_of_loop, limit);
1404 default:
1405 /* At this level of abstraction, the program is just a set
1406 of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
1407 other node to be handled. */
1408 return t_false;
1414 /* Given a LOOP_PHI_NODE, this function determines the evolution
1415 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1417 static tree
1418 analyze_evolution_in_loop (tree loop_phi_node,
1419 tree init_cond)
1421 int i;
1422 tree evolution_function = chrec_not_analyzed_yet;
1423 struct loop *loop = loop_containing_stmt (loop_phi_node);
1424 basic_block bb;
1426 if (dump_file && (dump_flags & TDF_DETAILS))
1428 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1429 fprintf (dump_file, " (loop_phi_node = ");
1430 print_generic_expr (dump_file, loop_phi_node, 0);
1431 fprintf (dump_file, ")\n");
1434 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1436 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1437 tree ssa_chain, ev_fn;
1438 t_bool res;
1440 /* Select the edges that enter the loop body. */
1441 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1442 if (!flow_bb_inside_loop_p (loop, bb))
1443 continue;
1445 if (TREE_CODE (arg) == SSA_NAME)
1447 ssa_chain = SSA_NAME_DEF_STMT (arg);
1449 /* Pass in the initial condition to the follow edge function. */
1450 ev_fn = init_cond;
1451 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1453 else
1454 res = t_false;
1456 /* When it is impossible to go back on the same
1457 loop_phi_node by following the ssa edges, the
1458 evolution is represented by a peeled chrec, i.e. the
1459 first iteration, EV_FN has the value INIT_COND, then
1460 all the other iterations it has the value of ARG.
1461 For the moment, PEELED_CHREC nodes are not built. */
1462 if (res != t_true)
1463 ev_fn = chrec_dont_know;
1465 /* When there are multiple back edges of the loop (which in fact never
1466 happens currently, but nevertheless), merge their evolutions. */
1467 evolution_function = chrec_merge (evolution_function, ev_fn);
1470 if (dump_file && (dump_flags & TDF_DETAILS))
1472 fprintf (dump_file, " (evolution_function = ");
1473 print_generic_expr (dump_file, evolution_function, 0);
1474 fprintf (dump_file, "))\n");
1477 return evolution_function;
1480 /* Given a loop-phi-node, return the initial conditions of the
1481 variable on entry of the loop. When the CCP has propagated
1482 constants into the loop-phi-node, the initial condition is
1483 instantiated, otherwise the initial condition is kept symbolic.
1484 This analyzer does not analyze the evolution outside the current
1485 loop, and leaves this task to the on-demand tree reconstructor. */
1487 static tree
1488 analyze_initial_condition (tree loop_phi_node)
1490 int i;
1491 tree init_cond = chrec_not_analyzed_yet;
1492 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1494 if (dump_file && (dump_flags & TDF_DETAILS))
1496 fprintf (dump_file, "(analyze_initial_condition \n");
1497 fprintf (dump_file, " (loop_phi_node = \n");
1498 print_generic_expr (dump_file, loop_phi_node, 0);
1499 fprintf (dump_file, ")\n");
1502 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1504 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1505 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1507 /* When the branch is oriented to the loop's body, it does
1508 not contribute to the initial condition. */
1509 if (flow_bb_inside_loop_p (loop, bb))
1510 continue;
1512 if (init_cond == chrec_not_analyzed_yet)
1514 init_cond = branch;
1515 continue;
1518 if (TREE_CODE (branch) == SSA_NAME)
1520 init_cond = chrec_dont_know;
1521 break;
1524 init_cond = chrec_merge (init_cond, branch);
1527 /* Ooops -- a loop without an entry??? */
1528 if (init_cond == chrec_not_analyzed_yet)
1529 init_cond = chrec_dont_know;
1531 if (dump_file && (dump_flags & TDF_DETAILS))
1533 fprintf (dump_file, " (init_cond = ");
1534 print_generic_expr (dump_file, init_cond, 0);
1535 fprintf (dump_file, "))\n");
1538 return init_cond;
1541 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1543 static tree
1544 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1546 tree res;
1547 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1548 tree init_cond;
1550 if (phi_loop != loop)
1552 struct loop *subloop;
1553 tree evolution_fn = analyze_scalar_evolution
1554 (phi_loop, PHI_RESULT (loop_phi_node));
1556 /* Dive one level deeper. */
1557 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1559 /* Interpret the subloop. */
1560 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1561 return res;
1564 /* Otherwise really interpret the loop phi. */
1565 init_cond = analyze_initial_condition (loop_phi_node);
1566 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1568 return res;
1571 /* This function merges the branches of a condition-phi-node,
1572 contained in the outermost loop, and whose arguments are already
1573 analyzed. */
1575 static tree
1576 interpret_condition_phi (struct loop *loop, tree condition_phi)
1578 int i;
1579 tree res = chrec_not_analyzed_yet;
1581 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1583 tree branch_chrec;
1585 if (backedge_phi_arg_p (condition_phi, i))
1587 res = chrec_dont_know;
1588 break;
1591 branch_chrec = analyze_scalar_evolution
1592 (loop, PHI_ARG_DEF (condition_phi, i));
1594 res = chrec_merge (res, branch_chrec);
1597 return res;
1600 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
1601 analyze this node before, follow the definitions until ending
1602 either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
1603 return path, this function propagates evolutions (ala constant copy
1604 propagation). OPND1 is not a GIMPLE expression because we could
1605 analyze the effect of an inner loop: see interpret_loop_phi. */
1607 static tree
1608 interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
1609 tree opnd1, tree type)
1611 tree res, opnd10, opnd11, chrec10, chrec11;
1613 if (is_gimple_min_invariant (opnd1))
1614 return chrec_convert (type, opnd1, at_stmt);
1616 switch (TREE_CODE (opnd1))
1618 case POINTER_PLUS_EXPR:
1619 opnd10 = TREE_OPERAND (opnd1, 0);
1620 opnd11 = TREE_OPERAND (opnd1, 1);
1621 chrec10 = analyze_scalar_evolution (loop, opnd10);
1622 chrec11 = analyze_scalar_evolution (loop, opnd11);
1623 chrec10 = chrec_convert (type, chrec10, at_stmt);
1624 chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
1625 res = chrec_fold_plus (type, chrec10, chrec11);
1626 break;
1628 case PLUS_EXPR:
1629 opnd10 = TREE_OPERAND (opnd1, 0);
1630 opnd11 = TREE_OPERAND (opnd1, 1);
1631 chrec10 = analyze_scalar_evolution (loop, opnd10);
1632 chrec11 = analyze_scalar_evolution (loop, opnd11);
1633 chrec10 = chrec_convert (type, chrec10, at_stmt);
1634 chrec11 = chrec_convert (type, chrec11, at_stmt);
1635 res = chrec_fold_plus (type, chrec10, chrec11);
1636 break;
1638 case MINUS_EXPR:
1639 opnd10 = TREE_OPERAND (opnd1, 0);
1640 opnd11 = TREE_OPERAND (opnd1, 1);
1641 chrec10 = analyze_scalar_evolution (loop, opnd10);
1642 chrec11 = analyze_scalar_evolution (loop, opnd11);
1643 chrec10 = chrec_convert (type, chrec10, at_stmt);
1644 chrec11 = chrec_convert (type, chrec11, at_stmt);
1645 res = chrec_fold_minus (type, chrec10, chrec11);
1646 break;
1648 case NEGATE_EXPR:
1649 opnd10 = TREE_OPERAND (opnd1, 0);
1650 chrec10 = analyze_scalar_evolution (loop, opnd10);
1651 chrec10 = chrec_convert (type, chrec10, at_stmt);
1652 /* TYPE may be integer, real or complex, so use fold_convert. */
1653 res = chrec_fold_multiply (type, chrec10,
1654 fold_convert (type, integer_minus_one_node));
1655 break;
1657 case MULT_EXPR:
1658 opnd10 = TREE_OPERAND (opnd1, 0);
1659 opnd11 = TREE_OPERAND (opnd1, 1);
1660 chrec10 = analyze_scalar_evolution (loop, opnd10);
1661 chrec11 = analyze_scalar_evolution (loop, opnd11);
1662 chrec10 = chrec_convert (type, chrec10, at_stmt);
1663 chrec11 = chrec_convert (type, chrec11, at_stmt);
1664 res = chrec_fold_multiply (type, chrec10, chrec11);
1665 break;
1667 case SSA_NAME:
1668 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1669 at_stmt);
1670 break;
1672 case ASSERT_EXPR:
1673 opnd10 = ASSERT_EXPR_VAR (opnd1);
1674 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1675 at_stmt);
1676 break;
1678 case NOP_EXPR:
1679 case CONVERT_EXPR:
1680 opnd10 = TREE_OPERAND (opnd1, 0);
1681 chrec10 = analyze_scalar_evolution (loop, opnd10);
1682 res = chrec_convert (type, chrec10, at_stmt);
1683 break;
1685 default:
1686 res = chrec_dont_know;
1687 break;
1690 return res;
1695 /* This section contains all the entry points:
1696 - number_of_iterations_in_loop,
1697 - analyze_scalar_evolution,
1698 - instantiate_parameters.
1701 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1702 common ancestor of DEF_LOOP and USE_LOOP. */
1704 static tree
1705 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1706 struct loop *def_loop,
1707 tree ev)
1709 tree res;
1710 if (def_loop == wrto_loop)
1711 return ev;
1713 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1714 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1716 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1719 /* Helper recursive function. */
1721 static tree
1722 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1724 tree def, type = TREE_TYPE (var);
1725 basic_block bb;
1726 struct loop *def_loop;
1728 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1729 return chrec_dont_know;
1731 if (TREE_CODE (var) != SSA_NAME)
1732 return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
1734 def = SSA_NAME_DEF_STMT (var);
1735 bb = bb_for_stmt (def);
1736 def_loop = bb ? bb->loop_father : NULL;
1738 if (bb == NULL
1739 || !flow_bb_inside_loop_p (loop, bb))
1741 /* Keep the symbolic form. */
1742 res = var;
1743 goto set_and_end;
1746 if (res != chrec_not_analyzed_yet)
1748 if (loop != bb->loop_father)
1749 res = compute_scalar_evolution_in_loop
1750 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1752 goto set_and_end;
1755 if (loop != def_loop)
1757 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1758 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1760 goto set_and_end;
1763 switch (TREE_CODE (def))
1765 case GIMPLE_MODIFY_STMT:
1766 res = interpret_rhs_modify_stmt (loop, def,
1767 GIMPLE_STMT_OPERAND (def, 1), type);
1768 break;
1770 case PHI_NODE:
1771 if (loop_phi_node_p (def))
1772 res = interpret_loop_phi (loop, def);
1773 else
1774 res = interpret_condition_phi (loop, def);
1775 break;
1777 default:
1778 res = chrec_dont_know;
1779 break;
1782 set_and_end:
1784 /* Keep the symbolic form. */
1785 if (res == chrec_dont_know)
1786 res = var;
1788 if (loop == def_loop)
1789 set_scalar_evolution (var, res);
1791 return res;
1794 /* Entry point for the scalar evolution analyzer.
1795 Analyzes and returns the scalar evolution of the ssa_name VAR.
1796 LOOP_NB is the identifier number of the loop in which the variable
1797 is used.
1799 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1800 pointer to the statement that uses this variable, in order to
1801 determine the evolution function of the variable, use the following
1802 calls:
1804 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1805 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1806 tree chrec_instantiated = instantiate_parameters
1807 (loop_nb, chrec_with_symbols);
1810 tree
1811 analyze_scalar_evolution (struct loop *loop, tree var)
1813 tree res;
1815 if (dump_file && (dump_flags & TDF_DETAILS))
1817 fprintf (dump_file, "(analyze_scalar_evolution \n");
1818 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1819 fprintf (dump_file, " (scalar = ");
1820 print_generic_expr (dump_file, var, 0);
1821 fprintf (dump_file, ")\n");
1824 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1826 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1827 res = var;
1829 if (dump_file && (dump_flags & TDF_DETAILS))
1830 fprintf (dump_file, ")\n");
1832 return res;
1835 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1836 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1837 of VERSION).
1839 FOLDED_CASTS is set to true if resolve_mixers used
1840 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1841 at the moment in order to keep things simple). */
1843 static tree
1844 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1845 tree version, bool *folded_casts)
1847 bool val = false;
1848 tree ev = version, tmp;
1850 if (folded_casts)
1851 *folded_casts = false;
1852 while (1)
1854 tmp = analyze_scalar_evolution (use_loop, ev);
1855 ev = resolve_mixers (use_loop, tmp);
1857 if (folded_casts && tmp != ev)
1858 *folded_casts = true;
1860 if (use_loop == wrto_loop)
1861 return ev;
1863 /* If the value of the use changes in the inner loop, we cannot express
1864 its value in the outer loop (we might try to return interval chrec,
1865 but we do not have a user for it anyway) */
1866 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1867 || !val)
1868 return chrec_dont_know;
1870 use_loop = loop_outer (use_loop);
1874 /* Returns instantiated value for VERSION in CACHE. */
1876 static tree
1877 get_instantiated_value (htab_t cache, tree version)
1879 struct scev_info_str *info, pattern;
1881 pattern.var = version;
1882 info = (struct scev_info_str *) htab_find (cache, &pattern);
1884 if (info)
1885 return info->chrec;
1886 else
1887 return NULL_TREE;
1890 /* Sets instantiated value for VERSION to VAL in CACHE. */
1892 static void
1893 set_instantiated_value (htab_t cache, tree version, tree val)
1895 struct scev_info_str *info, pattern;
1896 PTR *slot;
1898 pattern.var = version;
1899 slot = htab_find_slot (cache, &pattern, INSERT);
1901 if (!*slot)
1902 *slot = new_scev_info_str (version);
1903 info = (struct scev_info_str *) *slot;
1904 info->chrec = val;
1907 /* Return the closed_loop_phi node for VAR. If there is none, return
1908 NULL_TREE. */
1910 static tree
1911 loop_closed_phi_def (tree var)
1913 struct loop *loop;
1914 edge exit;
1915 tree phi;
1917 if (var == NULL_TREE
1918 || TREE_CODE (var) != SSA_NAME)
1919 return NULL_TREE;
1921 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
1922 exit = single_exit (loop);
1923 if (!exit)
1924 return NULL_TREE;
1926 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1927 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
1928 return PHI_RESULT (phi);
1930 return NULL_TREE;
1933 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1934 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
1935 of already instantiated values. FLAGS modify the way chrecs are
1936 instantiated. SIZE_EXPR is used for computing the size of the expression to
1937 be instantiated, and to stop if it exceeds some limit. */
1939 /* Values for FLAGS. */
1940 enum
1942 INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs
1943 in outer loops. */
1944 FOLD_CONVERSIONS = 2 /* The conversions that may wrap in
1945 signed/pointer type are folded, as long as the
1946 value of the chrec is preserved. */
1949 static tree
1950 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
1951 int size_expr)
1953 tree res, op0, op1, op2;
1954 basic_block def_bb;
1955 struct loop *def_loop;
1956 tree type = chrec_type (chrec);
1958 /* Give up if the expression is larger than the MAX that we allow. */
1959 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1960 return chrec_dont_know;
1962 if (automatically_generated_chrec_p (chrec)
1963 || is_gimple_min_invariant (chrec))
1964 return chrec;
1966 switch (TREE_CODE (chrec))
1968 case SSA_NAME:
1969 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1971 /* A parameter (or loop invariant and we do not want to include
1972 evolutions in outer loops), nothing to do. */
1973 if (!def_bb
1974 || (!(flags & INSERT_SUPERLOOP_CHRECS)
1975 && !flow_bb_inside_loop_p (loop, def_bb)))
1976 return chrec;
1978 /* We cache the value of instantiated variable to avoid exponential
1979 time complexity due to reevaluations. We also store the convenient
1980 value in the cache in order to prevent infinite recursion -- we do
1981 not want to instantiate the SSA_NAME if it is in a mixer
1982 structure. This is used for avoiding the instantiation of
1983 recursively defined functions, such as:
1985 | a_2 -> {0, +, 1, +, a_2}_1 */
1987 res = get_instantiated_value (cache, chrec);
1988 if (res)
1989 return res;
1991 /* Store the convenient value for chrec in the structure. If it
1992 is defined outside of the loop, we may just leave it in symbolic
1993 form, otherwise we need to admit that we do not know its behavior
1994 inside the loop. */
1995 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1996 set_instantiated_value (cache, chrec, res);
1998 /* To make things even more complicated, instantiate_parameters_1
1999 calls analyze_scalar_evolution that may call # of iterations
2000 analysis that may in turn call instantiate_parameters_1 again.
2001 To prevent the infinite recursion, keep also the bitmap of
2002 ssa names that are being instantiated globally. */
2003 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2004 return res;
2006 def_loop = find_common_loop (loop, def_bb->loop_father);
2008 /* If the analysis yields a parametric chrec, instantiate the
2009 result again. */
2010 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2011 res = analyze_scalar_evolution (def_loop, chrec);
2013 /* Don't instantiate loop-closed-ssa phi nodes. */
2014 if (TREE_CODE (res) == SSA_NAME
2015 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2016 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2017 > loop_depth (def_loop))))
2019 if (res == chrec)
2020 res = loop_closed_phi_def (chrec);
2021 else
2022 res = chrec;
2024 if (res == NULL_TREE)
2025 res = chrec_dont_know;
2028 else if (res != chrec_dont_know)
2029 res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2031 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2033 /* Store the correct value to the cache. */
2034 set_instantiated_value (cache, chrec, res);
2035 return res;
2037 case POLYNOMIAL_CHREC:
2038 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2039 flags, cache, size_expr);
2040 if (op0 == chrec_dont_know)
2041 return chrec_dont_know;
2043 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2044 flags, cache, size_expr);
2045 if (op1 == chrec_dont_know)
2046 return chrec_dont_know;
2048 if (CHREC_LEFT (chrec) != op0
2049 || CHREC_RIGHT (chrec) != op1)
2051 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
2052 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2054 return chrec;
2056 case POINTER_PLUS_EXPR:
2057 case PLUS_EXPR:
2058 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2059 flags, cache, size_expr);
2060 if (op0 == chrec_dont_know)
2061 return chrec_dont_know;
2063 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2064 flags, cache, size_expr);
2065 if (op1 == chrec_dont_know)
2066 return chrec_dont_know;
2068 if (TREE_OPERAND (chrec, 0) != op0
2069 || TREE_OPERAND (chrec, 1) != op1)
2071 op0 = chrec_convert (type, op0, NULL_TREE);
2072 op1 = chrec_convert_rhs (type, op1, NULL_TREE);
2073 chrec = chrec_fold_plus (type, op0, op1);
2075 return chrec;
2077 case MINUS_EXPR:
2078 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2079 flags, cache, size_expr);
2080 if (op0 == chrec_dont_know)
2081 return chrec_dont_know;
2083 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2084 flags, cache, size_expr);
2085 if (op1 == chrec_dont_know)
2086 return chrec_dont_know;
2088 if (TREE_OPERAND (chrec, 0) != op0
2089 || TREE_OPERAND (chrec, 1) != op1)
2091 op0 = chrec_convert (type, op0, NULL_TREE);
2092 op1 = chrec_convert (type, op1, NULL_TREE);
2093 chrec = chrec_fold_minus (type, op0, op1);
2095 return chrec;
2097 case MULT_EXPR:
2098 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2099 flags, cache, size_expr);
2100 if (op0 == chrec_dont_know)
2101 return chrec_dont_know;
2103 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2104 flags, cache, size_expr);
2105 if (op1 == chrec_dont_know)
2106 return chrec_dont_know;
2108 if (TREE_OPERAND (chrec, 0) != op0
2109 || TREE_OPERAND (chrec, 1) != op1)
2111 op0 = chrec_convert (type, op0, NULL_TREE);
2112 op1 = chrec_convert (type, op1, NULL_TREE);
2113 chrec = chrec_fold_multiply (type, op0, op1);
2115 return chrec;
2117 case NOP_EXPR:
2118 case CONVERT_EXPR:
2119 case NON_LVALUE_EXPR:
2120 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2121 flags, cache, size_expr);
2122 if (op0 == chrec_dont_know)
2123 return chrec_dont_know;
2125 if (flags & FOLD_CONVERSIONS)
2127 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2128 if (tmp)
2129 return tmp;
2132 if (op0 == TREE_OPERAND (chrec, 0))
2133 return chrec;
2135 /* If we used chrec_convert_aggressive, we can no longer assume that
2136 signed chrecs do not overflow, as chrec_convert does, so avoid
2137 calling it in that case. */
2138 if (flags & FOLD_CONVERSIONS)
2139 return fold_convert (TREE_TYPE (chrec), op0);
2141 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2143 case SCEV_NOT_KNOWN:
2144 return chrec_dont_know;
2146 case SCEV_KNOWN:
2147 return chrec_known;
2149 default:
2150 break;
2153 gcc_assert (!VL_EXP_CLASS_P (chrec));
2154 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2156 case 3:
2157 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2158 flags, cache, size_expr);
2159 if (op0 == chrec_dont_know)
2160 return chrec_dont_know;
2162 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2163 flags, cache, size_expr);
2164 if (op1 == chrec_dont_know)
2165 return chrec_dont_know;
2167 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2168 flags, cache, size_expr);
2169 if (op2 == chrec_dont_know)
2170 return chrec_dont_know;
2172 if (op0 == TREE_OPERAND (chrec, 0)
2173 && op1 == TREE_OPERAND (chrec, 1)
2174 && op2 == TREE_OPERAND (chrec, 2))
2175 return chrec;
2177 return fold_build3 (TREE_CODE (chrec),
2178 TREE_TYPE (chrec), op0, op1, op2);
2180 case 2:
2181 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2182 flags, cache, size_expr);
2183 if (op0 == chrec_dont_know)
2184 return chrec_dont_know;
2186 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2187 flags, cache, size_expr);
2188 if (op1 == chrec_dont_know)
2189 return chrec_dont_know;
2191 if (op0 == TREE_OPERAND (chrec, 0)
2192 && op1 == TREE_OPERAND (chrec, 1))
2193 return chrec;
2194 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2196 case 1:
2197 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2198 flags, cache, size_expr);
2199 if (op0 == chrec_dont_know)
2200 return chrec_dont_know;
2201 if (op0 == TREE_OPERAND (chrec, 0))
2202 return chrec;
2203 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2205 case 0:
2206 return chrec;
2208 default:
2209 break;
2212 /* Too complicated to handle. */
2213 return chrec_dont_know;
2216 /* Analyze all the parameters of the chrec that were left under a
2217 symbolic form. LOOP is the loop in which symbolic names have to
2218 be analyzed and instantiated. */
2220 tree
2221 instantiate_parameters (struct loop *loop,
2222 tree chrec)
2224 tree res;
2225 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2227 if (dump_file && (dump_flags & TDF_DETAILS))
2229 fprintf (dump_file, "(instantiate_parameters \n");
2230 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2231 fprintf (dump_file, " (chrec = ");
2232 print_generic_expr (dump_file, chrec, 0);
2233 fprintf (dump_file, ")\n");
2236 res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2239 if (dump_file && (dump_flags & TDF_DETAILS))
2241 fprintf (dump_file, " (res = ");
2242 print_generic_expr (dump_file, res, 0);
2243 fprintf (dump_file, "))\n");
2246 htab_delete (cache);
2248 return res;
2251 /* Similar to instantiate_parameters, but does not introduce the
2252 evolutions in outer loops for LOOP invariants in CHREC, and does not
2253 care about causing overflows, as long as they do not affect value
2254 of an expression. */
2256 tree
2257 resolve_mixers (struct loop *loop, tree chrec)
2259 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2260 tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2261 htab_delete (cache);
2262 return ret;
2265 /* Entry point for the analysis of the number of iterations pass.
2266 This function tries to safely approximate the number of iterations
2267 the loop will run. When this property is not decidable at compile
2268 time, the result is chrec_dont_know. Otherwise the result is
2269 a scalar or a symbolic parameter.
2271 Example of analysis: suppose that the loop has an exit condition:
2273 "if (b > 49) goto end_loop;"
2275 and that in a previous analysis we have determined that the
2276 variable 'b' has an evolution function:
2278 "EF = {23, +, 5}_2".
2280 When we evaluate the function at the point 5, i.e. the value of the
2281 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2282 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2283 the loop body has been executed 6 times. */
2285 tree
2286 number_of_latch_executions (struct loop *loop)
2288 tree res, type;
2289 edge exit;
2290 struct tree_niter_desc niter_desc;
2292 /* Determine whether the number_of_iterations_in_loop has already
2293 been computed. */
2294 res = loop->nb_iterations;
2295 if (res)
2296 return res;
2297 res = chrec_dont_know;
2299 if (dump_file && (dump_flags & TDF_DETAILS))
2300 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2302 exit = single_exit (loop);
2303 if (!exit)
2304 goto end;
2306 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2307 goto end;
2309 type = TREE_TYPE (niter_desc.niter);
2310 if (integer_nonzerop (niter_desc.may_be_zero))
2311 res = build_int_cst (type, 0);
2312 else if (integer_zerop (niter_desc.may_be_zero))
2313 res = niter_desc.niter;
2314 else
2315 res = chrec_dont_know;
2317 end:
2318 return set_nb_iterations_in_loop (loop, res);
2321 /* Returns the number of executions of the exit condition of LOOP,
2322 i.e., the number by one higher than number_of_latch_executions.
2323 Note that unline number_of_latch_executions, this number does
2324 not necessarily fit in the unsigned variant of the type of
2325 the control variable -- if the number of iterations is a constant,
2326 we return chrec_dont_know if adding one to number_of_latch_executions
2327 overflows; however, in case the number of iterations is symbolic
2328 expression, the caller is responsible for dealing with this
2329 the possible overflow. */
2331 tree
2332 number_of_exit_cond_executions (struct loop *loop)
2334 tree ret = number_of_latch_executions (loop);
2335 tree type = chrec_type (ret);
2337 if (chrec_contains_undetermined (ret))
2338 return ret;
2340 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2341 if (TREE_CODE (ret) == INTEGER_CST
2342 && TREE_OVERFLOW (ret))
2343 return chrec_dont_know;
2345 return ret;
2348 /* One of the drivers for testing the scalar evolutions analysis.
2349 This function computes the number of iterations for all the loops
2350 from the EXIT_CONDITIONS array. */
2352 static void
2353 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2355 unsigned int i;
2356 unsigned nb_chrec_dont_know_loops = 0;
2357 unsigned nb_static_loops = 0;
2358 tree cond;
2360 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2362 tree res = number_of_latch_executions (loop_containing_stmt (cond));
2363 if (chrec_contains_undetermined (res))
2364 nb_chrec_dont_know_loops++;
2365 else
2366 nb_static_loops++;
2369 if (dump_file)
2371 fprintf (dump_file, "\n(\n");
2372 fprintf (dump_file, "-----------------------------------------\n");
2373 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2374 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2375 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2376 fprintf (dump_file, "-----------------------------------------\n");
2377 fprintf (dump_file, ")\n\n");
2379 print_loop_ir (dump_file);
2385 /* Counters for the stats. */
2387 struct chrec_stats
2389 unsigned nb_chrecs;
2390 unsigned nb_affine;
2391 unsigned nb_affine_multivar;
2392 unsigned nb_higher_poly;
2393 unsigned nb_chrec_dont_know;
2394 unsigned nb_undetermined;
2397 /* Reset the counters. */
2399 static inline void
2400 reset_chrecs_counters (struct chrec_stats *stats)
2402 stats->nb_chrecs = 0;
2403 stats->nb_affine = 0;
2404 stats->nb_affine_multivar = 0;
2405 stats->nb_higher_poly = 0;
2406 stats->nb_chrec_dont_know = 0;
2407 stats->nb_undetermined = 0;
2410 /* Dump the contents of a CHREC_STATS structure. */
2412 static void
2413 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2415 fprintf (file, "\n(\n");
2416 fprintf (file, "-----------------------------------------\n");
2417 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2418 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2419 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2420 stats->nb_higher_poly);
2421 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2422 fprintf (file, "-----------------------------------------\n");
2423 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2424 fprintf (file, "%d\twith undetermined coefficients\n",
2425 stats->nb_undetermined);
2426 fprintf (file, "-----------------------------------------\n");
2427 fprintf (file, "%d\tchrecs in the scev database\n",
2428 (int) htab_elements (scalar_evolution_info));
2429 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2430 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2431 fprintf (file, "-----------------------------------------\n");
2432 fprintf (file, ")\n\n");
2435 /* Gather statistics about CHREC. */
2437 static void
2438 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2440 if (dump_file && (dump_flags & TDF_STATS))
2442 fprintf (dump_file, "(classify_chrec ");
2443 print_generic_expr (dump_file, chrec, 0);
2444 fprintf (dump_file, "\n");
2447 stats->nb_chrecs++;
2449 if (chrec == NULL_TREE)
2451 stats->nb_undetermined++;
2452 return;
2455 switch (TREE_CODE (chrec))
2457 case POLYNOMIAL_CHREC:
2458 if (evolution_function_is_affine_p (chrec))
2460 if (dump_file && (dump_flags & TDF_STATS))
2461 fprintf (dump_file, " affine_univariate\n");
2462 stats->nb_affine++;
2464 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2466 if (dump_file && (dump_flags & TDF_STATS))
2467 fprintf (dump_file, " affine_multivariate\n");
2468 stats->nb_affine_multivar++;
2470 else
2472 if (dump_file && (dump_flags & TDF_STATS))
2473 fprintf (dump_file, " higher_degree_polynomial\n");
2474 stats->nb_higher_poly++;
2477 break;
2479 default:
2480 break;
2483 if (chrec_contains_undetermined (chrec))
2485 if (dump_file && (dump_flags & TDF_STATS))
2486 fprintf (dump_file, " undetermined\n");
2487 stats->nb_undetermined++;
2490 if (dump_file && (dump_flags & TDF_STATS))
2491 fprintf (dump_file, ")\n");
2494 /* One of the drivers for testing the scalar evolutions analysis.
2495 This function analyzes the scalar evolution of all the scalars
2496 defined as loop phi nodes in one of the loops from the
2497 EXIT_CONDITIONS array.
2499 TODO Optimization: A loop is in canonical form if it contains only
2500 a single scalar loop phi node. All the other scalars that have an
2501 evolution in the loop are rewritten in function of this single
2502 index. This allows the parallelization of the loop. */
2504 static void
2505 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2507 unsigned int i;
2508 struct chrec_stats stats;
2509 tree cond;
2511 reset_chrecs_counters (&stats);
2513 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2515 struct loop *loop;
2516 basic_block bb;
2517 tree phi, chrec;
2519 loop = loop_containing_stmt (cond);
2520 bb = loop->header;
2522 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2523 if (is_gimple_reg (PHI_RESULT (phi)))
2525 chrec = instantiate_parameters
2526 (loop,
2527 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2529 if (dump_file && (dump_flags & TDF_STATS))
2530 gather_chrec_stats (chrec, &stats);
2534 if (dump_file && (dump_flags & TDF_STATS))
2535 dump_chrecs_stats (dump_file, &stats);
2538 /* Callback for htab_traverse, gathers information on chrecs in the
2539 hashtable. */
2541 static int
2542 gather_stats_on_scev_database_1 (void **slot, void *stats)
2544 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2546 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2548 return 1;
2551 /* Classify the chrecs of the whole database. */
2553 void
2554 gather_stats_on_scev_database (void)
2556 struct chrec_stats stats;
2558 if (!dump_file)
2559 return;
2561 reset_chrecs_counters (&stats);
2563 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2564 &stats);
2566 dump_chrecs_stats (dump_file, &stats);
2571 /* Initializer. */
2573 static void
2574 initialize_scalar_evolutions_analyzer (void)
2576 /* The elements below are unique. */
2577 if (chrec_dont_know == NULL_TREE)
2579 chrec_not_analyzed_yet = NULL_TREE;
2580 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2581 chrec_known = make_node (SCEV_KNOWN);
2582 TREE_TYPE (chrec_dont_know) = void_type_node;
2583 TREE_TYPE (chrec_known) = void_type_node;
2587 /* Initialize the analysis of scalar evolutions for LOOPS. */
2589 void
2590 scev_initialize (void)
2592 loop_iterator li;
2593 struct loop *loop;
2595 scalar_evolution_info = htab_create_alloc (100,
2596 hash_scev_info,
2597 eq_scev_info,
2598 del_scev_info,
2599 ggc_calloc,
2600 ggc_free);
2601 already_instantiated = BITMAP_ALLOC (NULL);
2603 initialize_scalar_evolutions_analyzer ();
2605 FOR_EACH_LOOP (li, loop, 0)
2607 loop->nb_iterations = NULL_TREE;
2611 /* Cleans up the information cached by the scalar evolutions analysis. */
2613 void
2614 scev_reset (void)
2616 loop_iterator li;
2617 struct loop *loop;
2619 if (!scalar_evolution_info || !current_loops)
2620 return;
2622 htab_empty (scalar_evolution_info);
2623 FOR_EACH_LOOP (li, loop, 0)
2625 loop->nb_iterations = NULL_TREE;
2629 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2630 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2631 want step to be invariant in LOOP. Otherwise we require it to be an
2632 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2633 overflow (e.g. because it is computed in signed arithmetics). */
2635 bool
2636 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2637 bool allow_nonconstant_step)
2639 basic_block bb = bb_for_stmt (stmt);
2640 tree type, ev;
2641 bool folded_casts;
2643 iv->base = NULL_TREE;
2644 iv->step = NULL_TREE;
2645 iv->no_overflow = false;
2647 type = TREE_TYPE (op);
2648 if (TREE_CODE (type) != INTEGER_TYPE
2649 && TREE_CODE (type) != POINTER_TYPE)
2650 return false;
2652 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2653 &folded_casts);
2654 if (chrec_contains_undetermined (ev))
2655 return false;
2657 if (tree_does_not_contain_chrecs (ev)
2658 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2660 iv->base = ev;
2661 iv->step = build_int_cst (TREE_TYPE (ev), 0);
2662 iv->no_overflow = true;
2663 return true;
2666 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2667 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2668 return false;
2670 iv->step = CHREC_RIGHT (ev);
2671 if (allow_nonconstant_step)
2673 if (tree_contains_chrecs (iv->step, NULL)
2674 || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2675 return false;
2677 else if (TREE_CODE (iv->step) != INTEGER_CST)
2678 return false;
2680 iv->base = CHREC_LEFT (ev);
2681 if (tree_contains_chrecs (iv->base, NULL)
2682 || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2683 return false;
2685 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2687 return true;
2690 /* Runs the analysis of scalar evolutions. */
2692 void
2693 scev_analysis (void)
2695 VEC(tree,heap) *exit_conditions;
2697 exit_conditions = VEC_alloc (tree, heap, 37);
2698 select_loops_exit_conditions (&exit_conditions);
2700 if (dump_file && (dump_flags & TDF_STATS))
2701 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2703 number_of_iterations_for_all_loops (&exit_conditions);
2704 VEC_free (tree, heap, exit_conditions);
2707 /* Finalize the scalar evolution analysis. */
2709 void
2710 scev_finalize (void)
2712 if (!scalar_evolution_info)
2713 return;
2714 htab_delete (scalar_evolution_info);
2715 BITMAP_FREE (already_instantiated);
2716 scalar_evolution_info = NULL;
2719 /* Replace ssa names for that scev can prove they are constant by the
2720 appropriate constants. Also perform final value replacement in loops,
2721 in case the replacement expressions are cheap.
2723 We only consider SSA names defined by phi nodes; rest is left to the
2724 ordinary constant propagation pass. */
2726 unsigned int
2727 scev_const_prop (void)
2729 basic_block bb;
2730 tree name, phi, next_phi, type, ev;
2731 struct loop *loop, *ex_loop;
2732 bitmap ssa_names_to_remove = NULL;
2733 unsigned i;
2734 loop_iterator li;
2736 if (number_of_loops () <= 1)
2737 return 0;
2739 FOR_EACH_BB (bb)
2741 loop = bb->loop_father;
2743 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2745 name = PHI_RESULT (phi);
2747 if (!is_gimple_reg (name))
2748 continue;
2750 type = TREE_TYPE (name);
2752 if (!POINTER_TYPE_P (type)
2753 && !INTEGRAL_TYPE_P (type))
2754 continue;
2756 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2757 if (!is_gimple_min_invariant (ev)
2758 || !may_propagate_copy (name, ev))
2759 continue;
2761 /* Replace the uses of the name. */
2762 if (name != ev)
2763 replace_uses_by (name, ev);
2765 if (!ssa_names_to_remove)
2766 ssa_names_to_remove = BITMAP_ALLOC (NULL);
2767 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2771 /* Remove the ssa names that were replaced by constants. We do not
2772 remove them directly in the previous cycle, since this
2773 invalidates scev cache. */
2774 if (ssa_names_to_remove)
2776 bitmap_iterator bi;
2778 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2780 name = ssa_name (i);
2781 phi = SSA_NAME_DEF_STMT (name);
2783 gcc_assert (TREE_CODE (phi) == PHI_NODE);
2784 remove_phi_node (phi, NULL, true);
2787 BITMAP_FREE (ssa_names_to_remove);
2788 scev_reset ();
2791 /* Now the regular final value replacement. */
2792 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2794 edge exit;
2795 tree def, rslt, ass, niter;
2796 block_stmt_iterator bsi;
2798 /* If we do not know exact number of iterations of the loop, we cannot
2799 replace the final value. */
2800 exit = single_exit (loop);
2801 if (!exit)
2802 continue;
2804 niter = number_of_latch_executions (loop);
2805 /* We used to check here whether the computation of NITER is expensive,
2806 and avoided final value elimination if that is the case. The problem
2807 is that it is hard to evaluate whether the expression is too
2808 expensive, as we do not know what optimization opportunities the
2809 the elimination of the final value may reveal. Therefore, we now
2810 eliminate the final values of induction variables unconditionally. */
2811 if (niter == chrec_dont_know)
2812 continue;
2814 /* Ensure that it is possible to insert new statements somewhere. */
2815 if (!single_pred_p (exit->dest))
2816 split_loop_exit_edge (exit);
2817 bsi = bsi_after_labels (exit->dest);
2819 ex_loop = superloop_at_depth (loop,
2820 loop_depth (exit->dest->loop_father) + 1);
2822 for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2824 next_phi = PHI_CHAIN (phi);
2825 rslt = PHI_RESULT (phi);
2826 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2827 if (!is_gimple_reg (def))
2828 continue;
2830 if (!POINTER_TYPE_P (TREE_TYPE (def))
2831 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2832 continue;
2834 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2835 def = compute_overall_effect_of_inner_loop (ex_loop, def);
2836 if (!tree_does_not_contain_chrecs (def)
2837 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2838 /* Moving the computation from the loop may prolong life range
2839 of some ssa names, which may cause problems if they appear
2840 on abnormal edges. */
2841 || contains_abnormal_ssa_name_p (def))
2842 continue;
2844 /* Eliminate the PHI node and replace it by a computation outside
2845 the loop. */
2846 def = unshare_expr (def);
2847 remove_phi_node (phi, NULL_TREE, false);
2849 ass = build_gimple_modify_stmt (rslt, NULL_TREE);
2850 SSA_NAME_DEF_STMT (rslt) = ass;
2852 block_stmt_iterator dest = bsi;
2853 bsi_insert_before (&dest, ass, BSI_NEW_STMT);
2854 def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
2855 true, BSI_SAME_STMT);
2857 GIMPLE_STMT_OPERAND (ass, 1) = def;
2858 update_stmt (ass);
2861 return 0;
2864 #include "gt-tree-scalar-evolution.h"