* config/arm/neon-gen.ml: Include vxWorks.h rather than stdint.h
[official-gcc.git] / gcc / tree-scalar-evolution.c
blobbac6e594d8f02ba32d961906d48c6bc90a03015c
1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <s.pop@laposte.net>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /*
23 Description:
25 This pass analyzes the evolution of scalar variables in loop
26 structures. The algorithm is based on the SSA representation,
27 and on the loop hierarchy tree. This algorithm is not based on
28 the notion of versions of a variable, as it was the case for the
29 previous implementations of the scalar evolution algorithm, but
30 it assumes that each defined name is unique.
32 The notation used in this file is called "chains of recurrences",
33 and has been proposed by Eugene Zima, Robert Van Engelen, and
34 others for describing induction variables in programs. For example
35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36 when entering in the loop_1 and has a step 2 in this loop, in other
37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38 this chain of recurrence (or chrec [shrek]) can contain the name of
39 other variables, in which case they are called parametric chrecs.
40 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41 is the value of "a". In most of the cases these parametric chrecs
42 are fully instantiated before their use because symbolic names can
43 hide some difficult cases such as self-references described later
44 (see the Fibonacci example).
46 A short sketch of the algorithm is:
48 Given a scalar variable to be analyzed, follow the SSA edge to
49 its definition:
51 - When the definition is a GIMPLE_ASSIGN: if the right hand side
52 (RHS) of the definition cannot be statically analyzed, the answer
53 of the analyzer is: "don't know".
54 Otherwise, for all the variables that are not yet analyzed in the
55 RHS, try to determine their evolution, and finally try to
56 evaluate the operation of the RHS that gives the evolution
57 function of the analyzed variable.
59 - When the definition is a condition-phi-node: determine the
60 evolution function for all the branches of the phi node, and
61 finally merge these evolutions (see chrec_merge).
63 - When the definition is a loop-phi-node: determine its initial
64 condition, that is the SSA edge defined in an outer loop, and
65 keep it symbolic. Then determine the SSA edges that are defined
66 in the body of the loop. Follow the inner edges until ending on
67 another loop-phi-node of the same analyzed loop. If the reached
68 loop-phi-node is not the starting loop-phi-node, then we keep
69 this definition under a symbolic form. If the reached
70 loop-phi-node is the same as the starting one, then we compute a
71 symbolic stride on the return path. The result is then the
72 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
74 Examples:
76 Example 1: Illustration of the basic algorithm.
78 | a = 3
79 | loop_1
80 | b = phi (a, c)
81 | c = b + 1
82 | if (c > 10) exit_loop
83 | endloop
85 Suppose that we want to know the number of iterations of the
86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87 ask the scalar evolution analyzer two questions: what's the
88 scalar evolution (scev) of "c", and what's the scev of "10". For
89 "10" the answer is "10" since it is a scalar constant. For the
90 scalar variable "c", it follows the SSA edge to its definition,
91 "c = b + 1", and then asks again what's the scev of "b".
92 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93 c)", where the initial condition is "a", and the inner loop edge
94 is "c". The initial condition is kept under a symbolic form (it
95 may be the case that the copy constant propagation has done its
96 work and we end with the constant "3" as one of the edges of the
97 loop-phi-node). The update edge is followed to the end of the
98 loop, and until reaching again the starting loop-phi-node: b -> c
99 -> b. At this point we have drawn a path from "b" to "b" from
100 which we compute the stride in the loop: in this example it is
101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102 that the scev for "b" is known, it is possible to compute the
103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104 determine the number of iterations in the loop_1, we have to
105 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
106 more analysis the scev {4, +, 1}_1, or in other words, this is
107 the function "f (x) = x + 4", where x is the iteration count of
108 the loop_1. Now we have to solve the inequality "x + 4 > 10",
109 and take the smallest iteration number for which the loop is
110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111 there are 8 iterations. In terms of loop normalization, we have
112 created a variable that is implicitly defined, "x" or just "_1",
113 and all the other analyzed scalars of the loop are defined in
114 function of this variable:
116 a -> 3
117 b -> {3, +, 1}_1
118 c -> {4, +, 1}_1
120 or in terms of a C program:
122 | a = 3
123 | for (x = 0; x <= 7; x++)
125 | b = x + 3
126 | c = x + 4
129 Example 2a: Illustration of the algorithm on nested loops.
131 | loop_1
132 | a = phi (1, b)
133 | c = a + 2
134 | loop_2 10 times
135 | b = phi (c, d)
136 | d = b + 3
137 | endloop
138 | endloop
140 For analyzing the scalar evolution of "a", the algorithm follows
141 the SSA edge into the loop's body: "a -> b". "b" is an inner
142 loop-phi-node, and its analysis as in Example 1, gives:
144 b -> {c, +, 3}_2
145 d -> {c + 3, +, 3}_2
147 Following the SSA edge for the initial condition, we end on "c = a
148 + 2", and then on the starting loop-phi-node "a". From this point,
149 the loop stride is computed: back on "c = a + 2" we get a "+2" in
150 the loop_1, then on the loop-phi-node "b" we compute the overall
151 effect of the inner loop that is "b = c + 30", and we get a "+30"
152 in the loop_1. That means that the overall stride in loop_1 is
153 equal to "+32", and the result is:
155 a -> {1, +, 32}_1
156 c -> {3, +, 32}_1
158 Example 2b: Multivariate chains of recurrences.
160 | loop_1
161 | k = phi (0, k + 1)
162 | loop_2 4 times
163 | j = phi (0, j + 1)
164 | loop_3 4 times
165 | i = phi (0, i + 1)
166 | A[j + k] = ...
167 | endloop
168 | endloop
169 | endloop
171 Analyzing the access function of array A with
172 instantiate_parameters (loop_1, "j + k"), we obtain the
173 instantiation and the analysis of the scalar variables "j" and "k"
174 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
175 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
176 {0, +, 1}_1. To obtain the evolution function in loop_3 and
177 instantiate the scalar variables up to loop_1, one has to use:
178 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
179 The result of this call is {{0, +, 1}_1, +, 1}_2.
181 Example 3: Higher degree polynomials.
183 | loop_1
184 | a = phi (2, b)
185 | c = phi (5, d)
186 | b = a + 1
187 | d = c + a
188 | endloop
190 a -> {2, +, 1}_1
191 b -> {3, +, 1}_1
192 c -> {5, +, a}_1
193 d -> {5 + a, +, a}_1
195 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
196 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
198 Example 4: Lucas, Fibonacci, or mixers in general.
200 | loop_1
201 | a = phi (1, b)
202 | c = phi (3, d)
203 | b = c
204 | d = c + a
205 | endloop
207 a -> (1, c)_1
208 c -> {3, +, a}_1
210 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
211 following semantics: during the first iteration of the loop_1, the
212 variable contains the value 1, and then it contains the value "c".
213 Note that this syntax is close to the syntax of the loop-phi-node:
214 "a -> (1, c)_1" vs. "a = phi (1, c)".
216 The symbolic chrec representation contains all the semantics of the
217 original code. What is more difficult is to use this information.
219 Example 5: Flip-flops, or exchangers.
221 | loop_1
222 | a = phi (1, b)
223 | c = phi (3, d)
224 | b = c
225 | d = a
226 | endloop
228 a -> (1, c)_1
229 c -> (3, a)_1
231 Based on these symbolic chrecs, it is possible to refine this
232 information into the more precise PERIODIC_CHRECs:
234 a -> |1, 3|_1
235 c -> |3, 1|_1
237 This transformation is not yet implemented.
239 Further readings:
241 You can find a more detailed description of the algorithm in:
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
243 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
244 this is a preliminary report and some of the details of the
245 algorithm have changed. I'm working on a research report that
246 updates the description of the algorithms to reflect the design
247 choices used in this implementation.
249 A set of slides show a high level overview of the algorithm and run
250 an example through the scalar evolution analyzer:
251 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
253 The slides that I have presented at the GCC Summit'04 are available
254 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
257 #include "config.h"
258 #include "system.h"
259 #include "coretypes.h"
260 #include "tm.h"
261 #include "ggc.h"
262 #include "tree.h"
263 #include "real.h"
265 /* These RTL headers are needed for basic-block.h. */
266 #include "rtl.h"
267 #include "basic-block.h"
268 #include "diagnostic.h"
269 #include "tree-flow.h"
270 #include "tree-dump.h"
271 #include "timevar.h"
272 #include "cfgloop.h"
273 #include "tree-chrec.h"
274 #include "tree-scalar-evolution.h"
275 #include "tree-pass.h"
276 #include "flags.h"
277 #include "params.h"
279 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
281 /* The cached information about an SSA name VAR, claiming that below
282 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
283 as CHREC. */
285 struct GTY(()) scev_info_str {
286 basic_block instantiated_below;
287 tree var;
288 tree chrec;
291 /* Counters for the scev database. */
292 static unsigned nb_set_scev = 0;
293 static unsigned nb_get_scev = 0;
295 /* The following trees are unique elements. Thus the comparison of
296 another element to these elements should be done on the pointer to
297 these trees, and not on their value. */
299 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
300 tree chrec_not_analyzed_yet;
302 /* Reserved to the cases where the analyzer has detected an
303 undecidable property at compile time. */
304 tree chrec_dont_know;
306 /* When the analyzer has detected that a property will never
307 happen, then it qualifies it with chrec_known. */
308 tree chrec_known;
310 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
313 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
315 static inline struct scev_info_str *
316 new_scev_info_str (basic_block instantiated_below, tree var)
318 struct scev_info_str *res;
320 res = GGC_NEW (struct scev_info_str);
321 res->var = var;
322 res->chrec = chrec_not_analyzed_yet;
323 res->instantiated_below = instantiated_below;
325 return res;
328 /* Computes a hash function for database element ELT. */
330 static hashval_t
331 hash_scev_info (const void *elt)
333 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
336 /* Compares database elements E1 and E2. */
338 static int
339 eq_scev_info (const void *e1, const void *e2)
341 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
342 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
344 return (elt1->var == elt2->var
345 && elt1->instantiated_below == elt2->instantiated_below);
348 /* Deletes database element E. */
350 static void
351 del_scev_info (void *e)
353 ggc_free (e);
356 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
357 A first query on VAR returns chrec_not_analyzed_yet. */
359 static tree *
360 find_var_scev_info (basic_block instantiated_below, tree var)
362 struct scev_info_str *res;
363 struct scev_info_str tmp;
364 PTR *slot;
366 tmp.var = var;
367 tmp.instantiated_below = instantiated_below;
368 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
370 if (!*slot)
371 *slot = new_scev_info_str (instantiated_below, var);
372 res = (struct scev_info_str *) *slot;
374 return &res->chrec;
377 /* Return true when CHREC contains symbolic names defined in
378 LOOP_NB. */
380 bool
381 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
383 int i, n;
385 if (chrec == NULL_TREE)
386 return false;
388 if (is_gimple_min_invariant (chrec))
389 return false;
391 if (TREE_CODE (chrec) == VAR_DECL
392 || TREE_CODE (chrec) == PARM_DECL
393 || TREE_CODE (chrec) == FUNCTION_DECL
394 || TREE_CODE (chrec) == LABEL_DECL
395 || TREE_CODE (chrec) == RESULT_DECL
396 || TREE_CODE (chrec) == FIELD_DECL)
397 return true;
399 if (TREE_CODE (chrec) == SSA_NAME)
401 gimple def = SSA_NAME_DEF_STMT (chrec);
402 struct loop *def_loop = loop_containing_stmt (def);
403 struct loop *loop = get_loop (loop_nb);
405 if (def_loop == NULL)
406 return false;
408 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
409 return true;
411 return false;
414 n = TREE_OPERAND_LENGTH (chrec);
415 for (i = 0; i < n; i++)
416 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
417 loop_nb))
418 return true;
419 return false;
422 /* Return true when PHI is a loop-phi-node. */
424 static bool
425 loop_phi_node_p (gimple phi)
427 /* The implementation of this function is based on the following
428 property: "all the loop-phi-nodes of a loop are contained in the
429 loop's header basic block". */
431 return loop_containing_stmt (phi)->header == gimple_bb (phi);
434 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
435 In general, in the case of multivariate evolutions we want to get
436 the evolution in different loops. LOOP specifies the level for
437 which to get the evolution.
439 Example:
441 | for (j = 0; j < 100; j++)
443 | for (k = 0; k < 100; k++)
445 | i = k + j; - Here the value of i is a function of j, k.
447 | ... = i - Here the value of i is a function of j.
449 | ... = i - Here the value of i is a scalar.
451 Example:
453 | i_0 = ...
454 | loop_1 10 times
455 | i_1 = phi (i_0, i_2)
456 | i_2 = i_1 + 2
457 | endloop
459 This loop has the same effect as:
460 LOOP_1 has the same effect as:
462 | i_1 = i_0 + 20
464 The overall effect of the loop, "i_0 + 20" in the previous example,
465 is obtained by passing in the parameters: LOOP = 1,
466 EVOLUTION_FN = {i_0, +, 2}_1.
469 static tree
470 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
472 bool val = false;
474 if (evolution_fn == chrec_dont_know)
475 return chrec_dont_know;
477 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
479 struct loop *inner_loop = get_chrec_loop (evolution_fn);
481 if (inner_loop == loop
482 || flow_loop_nested_p (loop, inner_loop))
484 tree nb_iter = number_of_latch_executions (inner_loop);
486 if (nb_iter == chrec_dont_know)
487 return chrec_dont_know;
488 else
490 tree res;
492 /* evolution_fn is the evolution function in LOOP. Get
493 its value in the nb_iter-th iteration. */
494 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
496 /* Continue the computation until ending on a parent of LOOP. */
497 return compute_overall_effect_of_inner_loop (loop, res);
500 else
501 return evolution_fn;
504 /* If the evolution function is an invariant, there is nothing to do. */
505 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
506 return evolution_fn;
508 else
509 return chrec_dont_know;
512 /* Determine whether the CHREC is always positive/negative. If the expression
513 cannot be statically analyzed, return false, otherwise set the answer into
514 VALUE. */
516 bool
517 chrec_is_positive (tree chrec, bool *value)
519 bool value0, value1, value2;
520 tree end_value, nb_iter;
522 switch (TREE_CODE (chrec))
524 case POLYNOMIAL_CHREC:
525 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
526 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
527 return false;
529 /* FIXME -- overflows. */
530 if (value0 == value1)
532 *value = value0;
533 return true;
536 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
537 and the proof consists in showing that the sign never
538 changes during the execution of the loop, from 0 to
539 loop->nb_iterations. */
540 if (!evolution_function_is_affine_p (chrec))
541 return false;
543 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
544 if (chrec_contains_undetermined (nb_iter))
545 return false;
547 #if 0
548 /* TODO -- If the test is after the exit, we may decrease the number of
549 iterations by one. */
550 if (after_exit)
551 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
552 #endif
554 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
556 if (!chrec_is_positive (end_value, &value2))
557 return false;
559 *value = value0;
560 return value0 == value1;
562 case INTEGER_CST:
563 *value = (tree_int_cst_sgn (chrec) == 1);
564 return true;
566 default:
567 return false;
571 /* Associate CHREC to SCALAR. */
573 static void
574 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
576 tree *scalar_info;
578 if (TREE_CODE (scalar) != SSA_NAME)
579 return;
581 scalar_info = find_var_scev_info (instantiated_below, scalar);
583 if (dump_file)
585 if (dump_flags & TDF_DETAILS)
587 fprintf (dump_file, "(set_scalar_evolution \n");
588 fprintf (dump_file, " instantiated_below = %d \n",
589 instantiated_below->index);
590 fprintf (dump_file, " (scalar = ");
591 print_generic_expr (dump_file, scalar, 0);
592 fprintf (dump_file, ")\n (scalar_evolution = ");
593 print_generic_expr (dump_file, chrec, 0);
594 fprintf (dump_file, "))\n");
596 if (dump_flags & TDF_STATS)
597 nb_set_scev++;
600 *scalar_info = chrec;
603 /* Retrieve the chrec associated to SCALAR instantiated below
604 INSTANTIATED_BELOW block. */
606 static tree
607 get_scalar_evolution (basic_block instantiated_below, tree scalar)
609 tree res;
611 if (dump_file)
613 if (dump_flags & TDF_DETAILS)
615 fprintf (dump_file, "(get_scalar_evolution \n");
616 fprintf (dump_file, " (scalar = ");
617 print_generic_expr (dump_file, scalar, 0);
618 fprintf (dump_file, ")\n");
620 if (dump_flags & TDF_STATS)
621 nb_get_scev++;
624 switch (TREE_CODE (scalar))
626 case SSA_NAME:
627 res = *find_var_scev_info (instantiated_below, scalar);
628 break;
630 case REAL_CST:
631 case FIXED_CST:
632 case INTEGER_CST:
633 res = scalar;
634 break;
636 default:
637 res = chrec_not_analyzed_yet;
638 break;
641 if (dump_file && (dump_flags & TDF_DETAILS))
643 fprintf (dump_file, " (scalar_evolution = ");
644 print_generic_expr (dump_file, res, 0);
645 fprintf (dump_file, "))\n");
648 return res;
651 /* Helper function for add_to_evolution. Returns the evolution
652 function for an assignment of the form "a = b + c", where "a" and
653 "b" are on the strongly connected component. CHREC_BEFORE is the
654 information that we already have collected up to this point.
655 TO_ADD is the evolution of "c".
657 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
658 evolution the expression TO_ADD, otherwise construct an evolution
659 part for this loop. */
661 static tree
662 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
663 gimple at_stmt)
665 tree type, left, right;
666 struct loop *loop = get_loop (loop_nb), *chloop;
668 switch (TREE_CODE (chrec_before))
670 case POLYNOMIAL_CHREC:
671 chloop = get_chrec_loop (chrec_before);
672 if (chloop == loop
673 || flow_loop_nested_p (chloop, loop))
675 unsigned var;
677 type = chrec_type (chrec_before);
679 /* When there is no evolution part in this loop, build it. */
680 if (chloop != loop)
682 var = loop_nb;
683 left = chrec_before;
684 right = SCALAR_FLOAT_TYPE_P (type)
685 ? build_real (type, dconst0)
686 : build_int_cst (type, 0);
688 else
690 var = CHREC_VARIABLE (chrec_before);
691 left = CHREC_LEFT (chrec_before);
692 right = CHREC_RIGHT (chrec_before);
695 to_add = chrec_convert (type, to_add, at_stmt);
696 right = chrec_convert_rhs (type, right, at_stmt);
697 right = chrec_fold_plus (chrec_type (right), right, to_add);
698 return build_polynomial_chrec (var, left, right);
700 else
702 gcc_assert (flow_loop_nested_p (loop, chloop));
704 /* Search the evolution in LOOP_NB. */
705 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
706 to_add, at_stmt);
707 right = CHREC_RIGHT (chrec_before);
708 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
709 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
710 left, right);
713 default:
714 /* These nodes do not depend on a loop. */
715 if (chrec_before == chrec_dont_know)
716 return chrec_dont_know;
718 left = chrec_before;
719 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
720 return build_polynomial_chrec (loop_nb, left, right);
724 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
725 of LOOP_NB.
727 Description (provided for completeness, for those who read code in
728 a plane, and for my poor 62 bytes brain that would have forgotten
729 all this in the next two or three months):
731 The algorithm of translation of programs from the SSA representation
732 into the chrecs syntax is based on a pattern matching. After having
733 reconstructed the overall tree expression for a loop, there are only
734 two cases that can arise:
736 1. a = loop-phi (init, a + expr)
737 2. a = loop-phi (init, expr)
739 where EXPR is either a scalar constant with respect to the analyzed
740 loop (this is a degree 0 polynomial), or an expression containing
741 other loop-phi definitions (these are higher degree polynomials).
743 Examples:
746 | init = ...
747 | loop_1
748 | a = phi (init, a + 5)
749 | endloop
752 | inita = ...
753 | initb = ...
754 | loop_1
755 | a = phi (inita, 2 * b + 3)
756 | b = phi (initb, b + 1)
757 | endloop
759 For the first case, the semantics of the SSA representation is:
761 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
763 that is, there is a loop index "x" that determines the scalar value
764 of the variable during the loop execution. During the first
765 iteration, the value is that of the initial condition INIT, while
766 during the subsequent iterations, it is the sum of the initial
767 condition with the sum of all the values of EXPR from the initial
768 iteration to the before last considered iteration.
770 For the second case, the semantics of the SSA program is:
772 | a (x) = init, if x = 0;
773 | expr (x - 1), otherwise.
775 The second case corresponds to the PEELED_CHREC, whose syntax is
776 close to the syntax of a loop-phi-node:
778 | phi (init, expr) vs. (init, expr)_x
780 The proof of the translation algorithm for the first case is a
781 proof by structural induction based on the degree of EXPR.
783 Degree 0:
784 When EXPR is a constant with respect to the analyzed loop, or in
785 other words when EXPR is a polynomial of degree 0, the evolution of
786 the variable A in the loop is an affine function with an initial
787 condition INIT, and a step EXPR. In order to show this, we start
788 from the semantics of the SSA representation:
790 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
792 and since "expr (j)" is a constant with respect to "j",
794 f (x) = init + x * expr
796 Finally, based on the semantics of the pure sum chrecs, by
797 identification we get the corresponding chrecs syntax:
799 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
800 f (x) -> {init, +, expr}_x
802 Higher degree:
803 Suppose that EXPR is a polynomial of degree N with respect to the
804 analyzed loop_x for which we have already determined that it is
805 written under the chrecs syntax:
807 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
809 We start from the semantics of the SSA program:
811 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
813 | f (x) = init + \sum_{j = 0}^{x - 1}
814 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
816 | f (x) = init + \sum_{j = 0}^{x - 1}
817 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
819 | f (x) = init + \sum_{k = 0}^{n - 1}
820 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
822 | f (x) = init + \sum_{k = 0}^{n - 1}
823 | (b_k * \binom{x}{k + 1})
825 | f (x) = init + b_0 * \binom{x}{1} + ...
826 | + b_{n-1} * \binom{x}{n}
828 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
829 | + b_{n-1} * \binom{x}{n}
832 And finally from the definition of the chrecs syntax, we identify:
833 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
835 This shows the mechanism that stands behind the add_to_evolution
836 function. An important point is that the use of symbolic
837 parameters avoids the need of an analysis schedule.
839 Example:
841 | inita = ...
842 | initb = ...
843 | loop_1
844 | a = phi (inita, a + 2 + b)
845 | b = phi (initb, b + 1)
846 | endloop
848 When analyzing "a", the algorithm keeps "b" symbolically:
850 | a -> {inita, +, 2 + b}_1
852 Then, after instantiation, the analyzer ends on the evolution:
854 | a -> {inita, +, 2 + initb, +, 1}_1
858 static tree
859 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
860 tree to_add, gimple at_stmt)
862 tree type = chrec_type (to_add);
863 tree res = NULL_TREE;
865 if (to_add == NULL_TREE)
866 return chrec_before;
868 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
869 instantiated at this point. */
870 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
871 /* This should not happen. */
872 return chrec_dont_know;
874 if (dump_file && (dump_flags & TDF_DETAILS))
876 fprintf (dump_file, "(add_to_evolution \n");
877 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
878 fprintf (dump_file, " (chrec_before = ");
879 print_generic_expr (dump_file, chrec_before, 0);
880 fprintf (dump_file, ")\n (to_add = ");
881 print_generic_expr (dump_file, to_add, 0);
882 fprintf (dump_file, ")\n");
885 if (code == MINUS_EXPR)
886 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
887 ? build_real (type, dconstm1)
888 : build_int_cst_type (type, -1));
890 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
892 if (dump_file && (dump_flags & TDF_DETAILS))
894 fprintf (dump_file, " (res = ");
895 print_generic_expr (dump_file, res, 0);
896 fprintf (dump_file, "))\n");
899 return res;
902 /* Helper function. */
904 static inline tree
905 set_nb_iterations_in_loop (struct loop *loop,
906 tree res)
908 if (dump_file && (dump_flags & TDF_DETAILS))
910 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
911 print_generic_expr (dump_file, res, 0);
912 fprintf (dump_file, "))\n");
915 loop->nb_iterations = res;
916 return res;
921 /* This section selects the loops that will be good candidates for the
922 scalar evolution analysis. For the moment, greedily select all the
923 loop nests we could analyze. */
925 /* For a loop with a single exit edge, return the COND_EXPR that
926 guards the exit edge. If the expression is too difficult to
927 analyze, then give up. */
929 gimple
930 get_loop_exit_condition (const struct loop *loop)
932 gimple res = NULL;
933 edge exit_edge = single_exit (loop);
935 if (dump_file && (dump_flags & TDF_DETAILS))
936 fprintf (dump_file, "(get_loop_exit_condition \n ");
938 if (exit_edge)
940 gimple stmt;
942 stmt = last_stmt (exit_edge->src);
943 if (gimple_code (stmt) == GIMPLE_COND)
944 res = stmt;
947 if (dump_file && (dump_flags & TDF_DETAILS))
949 print_gimple_stmt (dump_file, res, 0, 0);
950 fprintf (dump_file, ")\n");
953 return res;
956 /* Recursively determine and enqueue the exit conditions for a loop. */
958 static void
959 get_exit_conditions_rec (struct loop *loop,
960 VEC(gimple,heap) **exit_conditions)
962 if (!loop)
963 return;
965 /* Recurse on the inner loops, then on the next (sibling) loops. */
966 get_exit_conditions_rec (loop->inner, exit_conditions);
967 get_exit_conditions_rec (loop->next, exit_conditions);
969 if (single_exit (loop))
971 gimple loop_condition = get_loop_exit_condition (loop);
973 if (loop_condition)
974 VEC_safe_push (gimple, heap, *exit_conditions, loop_condition);
978 /* Select the candidate loop nests for the analysis. This function
979 initializes the EXIT_CONDITIONS array. */
981 static void
982 select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions)
984 struct loop *function_body = current_loops->tree_root;
986 get_exit_conditions_rec (function_body->inner, exit_conditions);
990 /* Depth first search algorithm. */
992 typedef enum t_bool {
993 t_false,
994 t_true,
995 t_dont_know
996 } t_bool;
999 static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
1001 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
1002 Return true if the strongly connected component has been found. */
1004 static t_bool
1005 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
1006 tree type, tree rhs0, enum tree_code code, tree rhs1,
1007 gimple halting_phi, tree *evolution_of_loop, int limit)
1009 t_bool res = t_false;
1010 tree evol;
1012 switch (code)
1014 case POINTER_PLUS_EXPR:
1015 case PLUS_EXPR:
1016 if (TREE_CODE (rhs0) == SSA_NAME)
1018 if (TREE_CODE (rhs1) == SSA_NAME)
1020 /* Match an assignment under the form:
1021 "a = b + c". */
1023 /* We want only assignments of form "name + name" contribute to
1024 LIMIT, as the other cases do not necessarily contribute to
1025 the complexity of the expression. */
1026 limit++;
1028 evol = *evolution_of_loop;
1029 res = follow_ssa_edge
1030 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
1032 if (res == t_true)
1033 *evolution_of_loop = add_to_evolution
1034 (loop->num,
1035 chrec_convert (type, evol, at_stmt),
1036 code, rhs1, at_stmt);
1038 else if (res == t_false)
1040 res = follow_ssa_edge
1041 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1042 evolution_of_loop, limit);
1044 if (res == t_true)
1045 *evolution_of_loop = add_to_evolution
1046 (loop->num,
1047 chrec_convert (type, *evolution_of_loop, at_stmt),
1048 code, rhs0, at_stmt);
1050 else if (res == t_dont_know)
1051 *evolution_of_loop = chrec_dont_know;
1054 else if (res == t_dont_know)
1055 *evolution_of_loop = chrec_dont_know;
1058 else
1060 /* Match an assignment under the form:
1061 "a = b + ...". */
1062 res = follow_ssa_edge
1063 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1064 evolution_of_loop, limit);
1065 if (res == t_true)
1066 *evolution_of_loop = add_to_evolution
1067 (loop->num, chrec_convert (type, *evolution_of_loop,
1068 at_stmt),
1069 code, rhs1, at_stmt);
1071 else if (res == t_dont_know)
1072 *evolution_of_loop = chrec_dont_know;
1076 else if (TREE_CODE (rhs1) == SSA_NAME)
1078 /* Match an assignment under the form:
1079 "a = ... + c". */
1080 res = follow_ssa_edge
1081 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1082 evolution_of_loop, limit);
1083 if (res == t_true)
1084 *evolution_of_loop = add_to_evolution
1085 (loop->num, chrec_convert (type, *evolution_of_loop,
1086 at_stmt),
1087 code, rhs0, at_stmt);
1089 else if (res == t_dont_know)
1090 *evolution_of_loop = chrec_dont_know;
1093 else
1094 /* Otherwise, match an assignment under the form:
1095 "a = ... + ...". */
1096 /* And there is nothing to do. */
1097 res = t_false;
1098 break;
1100 case MINUS_EXPR:
1101 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1102 if (TREE_CODE (rhs0) == SSA_NAME)
1104 /* Match an assignment under the form:
1105 "a = b - ...". */
1107 /* We want only assignments of form "name - name" contribute to
1108 LIMIT, as the other cases do not necessarily contribute to
1109 the complexity of the expression. */
1110 if (TREE_CODE (rhs1) == SSA_NAME)
1111 limit++;
1113 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1114 evolution_of_loop, limit);
1115 if (res == t_true)
1116 *evolution_of_loop = add_to_evolution
1117 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1118 MINUS_EXPR, rhs1, at_stmt);
1120 else if (res == t_dont_know)
1121 *evolution_of_loop = chrec_dont_know;
1123 else
1124 /* Otherwise, match an assignment under the form:
1125 "a = ... - ...". */
1126 /* And there is nothing to do. */
1127 res = t_false;
1128 break;
1130 default:
1131 res = t_false;
1134 return res;
1137 /* Follow the ssa edge into the expression EXPR.
1138 Return true if the strongly connected component has been found. */
1140 static t_bool
1141 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1142 gimple halting_phi, tree *evolution_of_loop, int limit)
1144 enum tree_code code = TREE_CODE (expr);
1145 tree type = TREE_TYPE (expr), rhs0, rhs1;
1146 t_bool res;
1148 /* The EXPR is one of the following cases:
1149 - an SSA_NAME,
1150 - an INTEGER_CST,
1151 - a PLUS_EXPR,
1152 - a POINTER_PLUS_EXPR,
1153 - a MINUS_EXPR,
1154 - an ASSERT_EXPR,
1155 - other cases are not yet handled. */
1157 switch (code)
1159 CASE_CONVERT:
1160 /* This assignment is under the form "a_1 = (cast) rhs. */
1161 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1162 halting_phi, evolution_of_loop, limit);
1163 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1164 break;
1166 case INTEGER_CST:
1167 /* This assignment is under the form "a_1 = 7". */
1168 res = t_false;
1169 break;
1171 case SSA_NAME:
1172 /* This assignment is under the form: "a_1 = b_2". */
1173 res = follow_ssa_edge
1174 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1175 break;
1177 case POINTER_PLUS_EXPR:
1178 case PLUS_EXPR:
1179 case MINUS_EXPR:
1180 /* This case is under the form "rhs0 +- rhs1". */
1181 rhs0 = TREE_OPERAND (expr, 0);
1182 rhs1 = TREE_OPERAND (expr, 1);
1183 type = TREE_TYPE (rhs0);
1184 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1185 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1186 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1187 halting_phi, evolution_of_loop, limit);
1188 break;
1190 case ASSERT_EXPR:
1191 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1192 It must be handled as a copy assignment of the form a_1 = a_2. */
1193 rhs0 = ASSERT_EXPR_VAR (expr);
1194 if (TREE_CODE (rhs0) == SSA_NAME)
1195 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1196 halting_phi, evolution_of_loop, limit);
1197 else
1198 res = t_false;
1199 break;
1201 default:
1202 res = t_false;
1203 break;
1206 return res;
1209 /* Follow the ssa edge into the right hand side of an assignment STMT.
1210 Return true if the strongly connected component has been found. */
1212 static t_bool
1213 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1214 gimple halting_phi, tree *evolution_of_loop, int limit)
1216 enum tree_code code = gimple_assign_rhs_code (stmt);
1217 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1218 t_bool res;
1220 switch (code)
1222 CASE_CONVERT:
1223 /* This assignment is under the form "a_1 = (cast) rhs. */
1224 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1225 halting_phi, evolution_of_loop, limit);
1226 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1227 break;
1229 case POINTER_PLUS_EXPR:
1230 case PLUS_EXPR:
1231 case MINUS_EXPR:
1232 rhs1 = gimple_assign_rhs1 (stmt);
1233 rhs2 = gimple_assign_rhs2 (stmt);
1234 type = TREE_TYPE (rhs1);
1235 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1236 halting_phi, evolution_of_loop, limit);
1237 break;
1239 default:
1240 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1241 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1242 halting_phi, evolution_of_loop, limit);
1243 else
1244 res = t_false;
1245 break;
1248 return res;
1251 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1253 static bool
1254 backedge_phi_arg_p (gimple phi, int i)
1256 const_edge e = gimple_phi_arg_edge (phi, i);
1258 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1259 about updating it anywhere, and this should work as well most of the
1260 time. */
1261 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1262 return true;
1264 return false;
1267 /* Helper function for one branch of the condition-phi-node. Return
1268 true if the strongly connected component has been found following
1269 this path. */
1271 static inline t_bool
1272 follow_ssa_edge_in_condition_phi_branch (int i,
1273 struct loop *loop,
1274 gimple condition_phi,
1275 gimple halting_phi,
1276 tree *evolution_of_branch,
1277 tree init_cond, int limit)
1279 tree branch = PHI_ARG_DEF (condition_phi, i);
1280 *evolution_of_branch = chrec_dont_know;
1282 /* Do not follow back edges (they must belong to an irreducible loop, which
1283 we really do not want to worry about). */
1284 if (backedge_phi_arg_p (condition_phi, i))
1285 return t_false;
1287 if (TREE_CODE (branch) == SSA_NAME)
1289 *evolution_of_branch = init_cond;
1290 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1291 evolution_of_branch, limit);
1294 /* This case occurs when one of the condition branches sets
1295 the variable to a constant: i.e. a phi-node like
1296 "a_2 = PHI <a_7(5), 2(6)>;".
1298 FIXME: This case have to be refined correctly:
1299 in some cases it is possible to say something better than
1300 chrec_dont_know, for example using a wrap-around notation. */
1301 return t_false;
1304 /* This function merges the branches of a condition-phi-node in a
1305 loop. */
1307 static t_bool
1308 follow_ssa_edge_in_condition_phi (struct loop *loop,
1309 gimple condition_phi,
1310 gimple halting_phi,
1311 tree *evolution_of_loop, int limit)
1313 int i, n;
1314 tree init = *evolution_of_loop;
1315 tree evolution_of_branch;
1316 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1317 halting_phi,
1318 &evolution_of_branch,
1319 init, limit);
1320 if (res == t_false || res == t_dont_know)
1321 return res;
1323 *evolution_of_loop = evolution_of_branch;
1325 n = gimple_phi_num_args (condition_phi);
1326 for (i = 1; i < n; i++)
1328 /* Quickly give up when the evolution of one of the branches is
1329 not known. */
1330 if (*evolution_of_loop == chrec_dont_know)
1331 return t_true;
1333 /* Increase the limit by the PHI argument number to avoid exponential
1334 time and memory complexity. */
1335 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1336 halting_phi,
1337 &evolution_of_branch,
1338 init, limit + i);
1339 if (res == t_false || res == t_dont_know)
1340 return res;
1342 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1343 evolution_of_branch);
1346 return t_true;
1349 /* Follow an SSA edge in an inner loop. It computes the overall
1350 effect of the loop, and following the symbolic initial conditions,
1351 it follows the edges in the parent loop. The inner loop is
1352 considered as a single statement. */
1354 static t_bool
1355 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1356 gimple loop_phi_node,
1357 gimple halting_phi,
1358 tree *evolution_of_loop, int limit)
1360 struct loop *loop = loop_containing_stmt (loop_phi_node);
1361 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1363 /* Sometimes, the inner loop is too difficult to analyze, and the
1364 result of the analysis is a symbolic parameter. */
1365 if (ev == PHI_RESULT (loop_phi_node))
1367 t_bool res = t_false;
1368 int i, n = gimple_phi_num_args (loop_phi_node);
1370 for (i = 0; i < n; i++)
1372 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1373 basic_block bb;
1375 /* Follow the edges that exit the inner loop. */
1376 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1377 if (!flow_bb_inside_loop_p (loop, bb))
1378 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1379 arg, halting_phi,
1380 evolution_of_loop, limit);
1381 if (res == t_true)
1382 break;
1385 /* If the path crosses this loop-phi, give up. */
1386 if (res == t_true)
1387 *evolution_of_loop = chrec_dont_know;
1389 return res;
1392 /* Otherwise, compute the overall effect of the inner loop. */
1393 ev = compute_overall_effect_of_inner_loop (loop, ev);
1394 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1395 evolution_of_loop, limit);
1398 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1399 path that is analyzed on the return walk. */
1401 static t_bool
1402 follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
1403 tree *evolution_of_loop, int limit)
1405 struct loop *def_loop;
1407 if (gimple_nop_p (def))
1408 return t_false;
1410 /* Give up if the path is longer than the MAX that we allow. */
1411 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1412 return t_dont_know;
1414 def_loop = loop_containing_stmt (def);
1416 switch (gimple_code (def))
1418 case GIMPLE_PHI:
1419 if (!loop_phi_node_p (def))
1420 /* DEF is a condition-phi-node. Follow the branches, and
1421 record their evolutions. Finally, merge the collected
1422 information and set the approximation to the main
1423 variable. */
1424 return follow_ssa_edge_in_condition_phi
1425 (loop, def, halting_phi, evolution_of_loop, limit);
1427 /* When the analyzed phi is the halting_phi, the
1428 depth-first search is over: we have found a path from
1429 the halting_phi to itself in the loop. */
1430 if (def == halting_phi)
1431 return t_true;
1433 /* Otherwise, the evolution of the HALTING_PHI depends
1434 on the evolution of another loop-phi-node, i.e. the
1435 evolution function is a higher degree polynomial. */
1436 if (def_loop == loop)
1437 return t_false;
1439 /* Inner loop. */
1440 if (flow_loop_nested_p (loop, def_loop))
1441 return follow_ssa_edge_inner_loop_phi
1442 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1444 /* Outer loop. */
1445 return t_false;
1447 case GIMPLE_ASSIGN:
1448 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1449 evolution_of_loop, limit);
1451 default:
1452 /* At this level of abstraction, the program is just a set
1453 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1454 other node to be handled. */
1455 return t_false;
1461 /* Given a LOOP_PHI_NODE, this function determines the evolution
1462 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1464 static tree
1465 analyze_evolution_in_loop (gimple loop_phi_node,
1466 tree init_cond)
1468 int i, n = gimple_phi_num_args (loop_phi_node);
1469 tree evolution_function = chrec_not_analyzed_yet;
1470 struct loop *loop = loop_containing_stmt (loop_phi_node);
1471 basic_block bb;
1473 if (dump_file && (dump_flags & TDF_DETAILS))
1475 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1476 fprintf (dump_file, " (loop_phi_node = ");
1477 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1478 fprintf (dump_file, ")\n");
1481 for (i = 0; i < n; i++)
1483 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1484 gimple ssa_chain;
1485 tree ev_fn;
1486 t_bool res;
1488 /* Select the edges that enter the loop body. */
1489 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1490 if (!flow_bb_inside_loop_p (loop, bb))
1491 continue;
1493 if (TREE_CODE (arg) == SSA_NAME)
1495 ssa_chain = SSA_NAME_DEF_STMT (arg);
1497 /* Pass in the initial condition to the follow edge function. */
1498 ev_fn = init_cond;
1499 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1501 else
1502 res = t_false;
1504 /* When it is impossible to go back on the same
1505 loop_phi_node by following the ssa edges, the
1506 evolution is represented by a peeled chrec, i.e. the
1507 first iteration, EV_FN has the value INIT_COND, then
1508 all the other iterations it has the value of ARG.
1509 For the moment, PEELED_CHREC nodes are not built. */
1510 if (res != t_true)
1511 ev_fn = chrec_dont_know;
1513 /* When there are multiple back edges of the loop (which in fact never
1514 happens currently, but nevertheless), merge their evolutions. */
1515 evolution_function = chrec_merge (evolution_function, ev_fn);
1518 if (dump_file && (dump_flags & TDF_DETAILS))
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 /* Given a loop-phi-node, return the initial conditions of the
1529 variable on entry of the loop. When the CCP has propagated
1530 constants into the loop-phi-node, the initial condition is
1531 instantiated, otherwise the initial condition is kept symbolic.
1532 This analyzer does not analyze the evolution outside the current
1533 loop, and leaves this task to the on-demand tree reconstructor. */
1535 static tree
1536 analyze_initial_condition (gimple loop_phi_node)
1538 int i, n;
1539 tree init_cond = chrec_not_analyzed_yet;
1540 struct loop *loop = loop_containing_stmt (loop_phi_node);
1542 if (dump_file && (dump_flags & TDF_DETAILS))
1544 fprintf (dump_file, "(analyze_initial_condition \n");
1545 fprintf (dump_file, " (loop_phi_node = \n");
1546 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1547 fprintf (dump_file, ")\n");
1550 n = gimple_phi_num_args (loop_phi_node);
1551 for (i = 0; i < n; i++)
1553 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1554 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1556 /* When the branch is oriented to the loop's body, it does
1557 not contribute to the initial condition. */
1558 if (flow_bb_inside_loop_p (loop, bb))
1559 continue;
1561 if (init_cond == chrec_not_analyzed_yet)
1563 init_cond = branch;
1564 continue;
1567 if (TREE_CODE (branch) == SSA_NAME)
1569 init_cond = chrec_dont_know;
1570 break;
1573 init_cond = chrec_merge (init_cond, branch);
1576 /* Ooops -- a loop without an entry??? */
1577 if (init_cond == chrec_not_analyzed_yet)
1578 init_cond = chrec_dont_know;
1580 /* During early loop unrolling we do not have fully constant propagated IL.
1581 Handle degenerate PHIs here to not miss important unrollings. */
1582 if (TREE_CODE (init_cond) == SSA_NAME)
1584 gimple def = SSA_NAME_DEF_STMT (init_cond);
1585 tree res;
1586 if (gimple_code (def) == GIMPLE_PHI
1587 && (res = degenerate_phi_result (def)) != NULL_TREE
1588 /* Only allow invariants here, otherwise we may break
1589 loop-closed SSA form. */
1590 && is_gimple_min_invariant (res))
1591 init_cond = res;
1594 if (dump_file && (dump_flags & TDF_DETAILS))
1596 fprintf (dump_file, " (init_cond = ");
1597 print_generic_expr (dump_file, init_cond, 0);
1598 fprintf (dump_file, "))\n");
1601 return init_cond;
1604 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1606 static tree
1607 interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
1609 tree res;
1610 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1611 tree init_cond;
1613 if (phi_loop != loop)
1615 struct loop *subloop;
1616 tree evolution_fn = analyze_scalar_evolution
1617 (phi_loop, PHI_RESULT (loop_phi_node));
1619 /* Dive one level deeper. */
1620 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1622 /* Interpret the subloop. */
1623 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1624 return res;
1627 /* Otherwise really interpret the loop phi. */
1628 init_cond = analyze_initial_condition (loop_phi_node);
1629 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1631 return res;
1634 /* This function merges the branches of a condition-phi-node,
1635 contained in the outermost loop, and whose arguments are already
1636 analyzed. */
1638 static tree
1639 interpret_condition_phi (struct loop *loop, gimple condition_phi)
1641 int i, n = gimple_phi_num_args (condition_phi);
1642 tree res = chrec_not_analyzed_yet;
1644 for (i = 0; i < n; i++)
1646 tree branch_chrec;
1648 if (backedge_phi_arg_p (condition_phi, i))
1650 res = chrec_dont_know;
1651 break;
1654 branch_chrec = analyze_scalar_evolution
1655 (loop, PHI_ARG_DEF (condition_phi, i));
1657 res = chrec_merge (res, branch_chrec);
1660 return res;
1663 /* Interpret the operation RHS1 OP RHS2. If we didn't
1664 analyze this node before, follow the definitions until ending
1665 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1666 return path, this function propagates evolutions (ala constant copy
1667 propagation). OPND1 is not a GIMPLE expression because we could
1668 analyze the effect of an inner loop: see interpret_loop_phi. */
1670 static tree
1671 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1672 tree type, tree rhs1, enum tree_code code, tree rhs2)
1674 tree res, chrec1, chrec2;
1676 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1678 if (is_gimple_min_invariant (rhs1))
1679 return chrec_convert (type, rhs1, at_stmt);
1681 if (code == SSA_NAME)
1682 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1683 at_stmt);
1685 if (code == ASSERT_EXPR)
1687 rhs1 = ASSERT_EXPR_VAR (rhs1);
1688 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1689 at_stmt);
1692 return chrec_dont_know;
1695 switch (code)
1697 case POINTER_PLUS_EXPR:
1698 chrec1 = analyze_scalar_evolution (loop, rhs1);
1699 chrec2 = analyze_scalar_evolution (loop, rhs2);
1700 chrec1 = chrec_convert (type, chrec1, at_stmt);
1701 chrec2 = chrec_convert (sizetype, chrec2, at_stmt);
1702 res = chrec_fold_plus (type, chrec1, chrec2);
1703 break;
1705 case PLUS_EXPR:
1706 chrec1 = analyze_scalar_evolution (loop, rhs1);
1707 chrec2 = analyze_scalar_evolution (loop, rhs2);
1708 chrec1 = chrec_convert (type, chrec1, at_stmt);
1709 chrec2 = chrec_convert (type, chrec2, at_stmt);
1710 res = chrec_fold_plus (type, chrec1, chrec2);
1711 break;
1713 case MINUS_EXPR:
1714 chrec1 = analyze_scalar_evolution (loop, rhs1);
1715 chrec2 = analyze_scalar_evolution (loop, rhs2);
1716 chrec1 = chrec_convert (type, chrec1, at_stmt);
1717 chrec2 = chrec_convert (type, chrec2, at_stmt);
1718 res = chrec_fold_minus (type, chrec1, chrec2);
1719 break;
1721 case NEGATE_EXPR:
1722 chrec1 = analyze_scalar_evolution (loop, rhs1);
1723 chrec1 = chrec_convert (type, chrec1, at_stmt);
1724 /* TYPE may be integer, real or complex, so use fold_convert. */
1725 res = chrec_fold_multiply (type, chrec1,
1726 fold_convert (type, integer_minus_one_node));
1727 break;
1729 case BIT_NOT_EXPR:
1730 /* Handle ~X as -1 - X. */
1731 chrec1 = analyze_scalar_evolution (loop, rhs1);
1732 chrec1 = chrec_convert (type, chrec1, at_stmt);
1733 res = chrec_fold_minus (type,
1734 fold_convert (type, integer_minus_one_node),
1735 chrec1);
1736 break;
1738 case MULT_EXPR:
1739 chrec1 = analyze_scalar_evolution (loop, rhs1);
1740 chrec2 = analyze_scalar_evolution (loop, rhs2);
1741 chrec1 = chrec_convert (type, chrec1, at_stmt);
1742 chrec2 = chrec_convert (type, chrec2, at_stmt);
1743 res = chrec_fold_multiply (type, chrec1, chrec2);
1744 break;
1746 CASE_CONVERT:
1747 chrec1 = analyze_scalar_evolution (loop, rhs1);
1748 res = chrec_convert (type, chrec1, at_stmt);
1749 break;
1751 default:
1752 res = chrec_dont_know;
1753 break;
1756 return res;
1759 /* Interpret the expression EXPR. */
1761 static tree
1762 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1764 enum tree_code code;
1765 tree type = TREE_TYPE (expr), op0, op1;
1767 if (automatically_generated_chrec_p (expr))
1768 return expr;
1770 if (TREE_CODE (expr) == POLYNOMIAL_CHREC)
1771 return chrec_dont_know;
1773 extract_ops_from_tree (expr, &code, &op0, &op1);
1775 return interpret_rhs_expr (loop, at_stmt, type,
1776 op0, code, op1);
1779 /* Interpret the rhs of the assignment STMT. */
1781 static tree
1782 interpret_gimple_assign (struct loop *loop, gimple stmt)
1784 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1785 enum tree_code code = gimple_assign_rhs_code (stmt);
1787 return interpret_rhs_expr (loop, stmt, type,
1788 gimple_assign_rhs1 (stmt), code,
1789 gimple_assign_rhs2 (stmt));
1794 /* This section contains all the entry points:
1795 - number_of_iterations_in_loop,
1796 - analyze_scalar_evolution,
1797 - instantiate_parameters.
1800 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1801 common ancestor of DEF_LOOP and USE_LOOP. */
1803 static tree
1804 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1805 struct loop *def_loop,
1806 tree ev)
1808 tree res;
1809 if (def_loop == wrto_loop)
1810 return ev;
1812 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1813 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1815 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1818 /* Helper recursive function. */
1820 static tree
1821 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1823 tree type = TREE_TYPE (var);
1824 gimple def;
1825 basic_block bb;
1826 struct loop *def_loop;
1828 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1829 return chrec_dont_know;
1831 if (TREE_CODE (var) != SSA_NAME)
1832 return interpret_expr (loop, NULL, var);
1834 def = SSA_NAME_DEF_STMT (var);
1835 bb = gimple_bb (def);
1836 def_loop = bb ? bb->loop_father : NULL;
1838 if (bb == NULL
1839 || !flow_bb_inside_loop_p (loop, bb))
1841 /* Keep the symbolic form. */
1842 res = var;
1843 goto set_and_end;
1846 if (res != chrec_not_analyzed_yet)
1848 if (loop != bb->loop_father)
1849 res = compute_scalar_evolution_in_loop
1850 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1852 goto set_and_end;
1855 if (loop != def_loop)
1857 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1858 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1860 goto set_and_end;
1863 switch (gimple_code (def))
1865 case GIMPLE_ASSIGN:
1866 res = interpret_gimple_assign (loop, def);
1867 break;
1869 case GIMPLE_PHI:
1870 if (loop_phi_node_p (def))
1871 res = interpret_loop_phi (loop, def);
1872 else
1873 res = interpret_condition_phi (loop, def);
1874 break;
1876 default:
1877 res = chrec_dont_know;
1878 break;
1881 set_and_end:
1883 /* Keep the symbolic form. */
1884 if (res == chrec_dont_know)
1885 res = var;
1887 if (loop == def_loop)
1888 set_scalar_evolution (block_before_loop (loop), var, res);
1890 return res;
1893 /* Entry point for the scalar evolution analyzer.
1894 Analyzes and returns the scalar evolution of the ssa_name VAR.
1895 LOOP_NB is the identifier number of the loop in which the variable
1896 is used.
1898 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1899 pointer to the statement that uses this variable, in order to
1900 determine the evolution function of the variable, use the following
1901 calls:
1903 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1904 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1905 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1908 tree
1909 analyze_scalar_evolution (struct loop *loop, tree var)
1911 tree res;
1913 if (dump_file && (dump_flags & TDF_DETAILS))
1915 fprintf (dump_file, "(analyze_scalar_evolution \n");
1916 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1917 fprintf (dump_file, " (scalar = ");
1918 print_generic_expr (dump_file, var, 0);
1919 fprintf (dump_file, ")\n");
1922 res = get_scalar_evolution (block_before_loop (loop), var);
1923 res = analyze_scalar_evolution_1 (loop, var, res);
1925 if (dump_file && (dump_flags & TDF_DETAILS))
1926 fprintf (dump_file, ")\n");
1928 return res;
1931 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1932 WRTO_LOOP (which should be a superloop of USE_LOOP)
1934 FOLDED_CASTS is set to true if resolve_mixers used
1935 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1936 at the moment in order to keep things simple).
1938 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1939 example:
1941 for (i = 0; i < 100; i++) -- loop 1
1943 for (j = 0; j < 100; j++) -- loop 2
1945 k1 = i;
1946 k2 = j;
1948 use2 (k1, k2);
1950 for (t = 0; t < 100; t++) -- loop 3
1951 use3 (k1, k2);
1954 use1 (k1, k2);
1957 Both k1 and k2 are invariants in loop3, thus
1958 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1959 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1961 As they are invariant, it does not matter whether we consider their
1962 usage in loop 3 or loop 2, hence
1963 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1964 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1965 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1966 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1968 Similarly for their evolutions with respect to loop 1. The values of K2
1969 in the use in loop 2 vary independently on loop 1, thus we cannot express
1970 the evolution with respect to loop 1:
1971 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
1972 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
1973 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
1974 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
1976 The value of k2 in the use in loop 1 is known, though:
1977 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
1978 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
1981 static tree
1982 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1983 tree version, bool *folded_casts)
1985 bool val = false;
1986 tree ev = version, tmp;
1988 /* We cannot just do
1990 tmp = analyze_scalar_evolution (use_loop, version);
1991 ev = resolve_mixers (wrto_loop, tmp);
1993 as resolve_mixers would query the scalar evolution with respect to
1994 wrto_loop. For example, in the situation described in the function
1995 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
1996 version = k2. Then
1998 analyze_scalar_evolution (use_loop, version) = k2
2000 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2001 is 100, which is a wrong result, since we are interested in the
2002 value in loop 3.
2004 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2005 each time checking that there is no evolution in the inner loop. */
2007 if (folded_casts)
2008 *folded_casts = false;
2009 while (1)
2011 tmp = analyze_scalar_evolution (use_loop, ev);
2012 ev = resolve_mixers (use_loop, tmp);
2014 if (folded_casts && tmp != ev)
2015 *folded_casts = true;
2017 if (use_loop == wrto_loop)
2018 return ev;
2020 /* If the value of the use changes in the inner loop, we cannot express
2021 its value in the outer loop (we might try to return interval chrec,
2022 but we do not have a user for it anyway) */
2023 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2024 || !val)
2025 return chrec_dont_know;
2027 use_loop = loop_outer (use_loop);
2031 /* Returns from CACHE the value for VERSION instantiated below
2032 INSTANTIATED_BELOW block. */
2034 static tree
2035 get_instantiated_value (htab_t cache, basic_block instantiated_below,
2036 tree version)
2038 struct scev_info_str *info, pattern;
2040 pattern.var = version;
2041 pattern.instantiated_below = instantiated_below;
2042 info = (struct scev_info_str *) htab_find (cache, &pattern);
2044 if (info)
2045 return info->chrec;
2046 else
2047 return NULL_TREE;
2050 /* Sets in CACHE the value of VERSION instantiated below basic block
2051 INSTANTIATED_BELOW to VAL. */
2053 static void
2054 set_instantiated_value (htab_t cache, basic_block instantiated_below,
2055 tree version, tree val)
2057 struct scev_info_str *info, pattern;
2058 PTR *slot;
2060 pattern.var = version;
2061 pattern.instantiated_below = instantiated_below;
2062 slot = htab_find_slot (cache, &pattern, INSERT);
2064 if (!*slot)
2065 *slot = new_scev_info_str (instantiated_below, version);
2066 info = (struct scev_info_str *) *slot;
2067 info->chrec = val;
2070 /* Return the closed_loop_phi node for VAR. If there is none, return
2071 NULL_TREE. */
2073 static tree
2074 loop_closed_phi_def (tree var)
2076 struct loop *loop;
2077 edge exit;
2078 gimple phi;
2079 gimple_stmt_iterator psi;
2081 if (var == NULL_TREE
2082 || TREE_CODE (var) != SSA_NAME)
2083 return NULL_TREE;
2085 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2086 exit = single_exit (loop);
2087 if (!exit)
2088 return NULL_TREE;
2090 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2092 phi = gsi_stmt (psi);
2093 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2094 return PHI_RESULT (phi);
2097 return NULL_TREE;
2100 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2101 and EVOLUTION_LOOP, that were left under a symbolic form.
2103 CHREC is the scalar evolution to instantiate.
2105 CACHE is the cache of already instantiated values.
2107 FOLD_CONVERSIONS should be set to true when the conversions that
2108 may wrap in signed/pointer type are folded, as long as the value of
2109 the chrec is preserved.
2111 SIZE_EXPR is used for computing the size of the expression to be
2112 instantiated, and to stop if it exceeds some limit. */
2114 static tree
2115 instantiate_scev_1 (basic_block instantiate_below,
2116 struct loop *evolution_loop, tree chrec,
2117 bool fold_conversions, htab_t cache, int size_expr)
2119 tree res, op0, op1, op2;
2120 basic_block def_bb;
2121 struct loop *def_loop;
2122 tree type = chrec_type (chrec);
2124 /* Give up if the expression is larger than the MAX that we allow. */
2125 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2126 return chrec_dont_know;
2128 if (automatically_generated_chrec_p (chrec)
2129 || is_gimple_min_invariant (chrec))
2130 return chrec;
2132 switch (TREE_CODE (chrec))
2134 case SSA_NAME:
2135 def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2137 /* A parameter (or loop invariant and we do not want to include
2138 evolutions in outer loops), nothing to do. */
2139 if (!def_bb
2140 || loop_depth (def_bb->loop_father) == 0
2141 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2142 return chrec;
2144 /* We cache the value of instantiated variable to avoid exponential
2145 time complexity due to reevaluations. We also store the convenient
2146 value in the cache in order to prevent infinite recursion -- we do
2147 not want to instantiate the SSA_NAME if it is in a mixer
2148 structure. This is used for avoiding the instantiation of
2149 recursively defined functions, such as:
2151 | a_2 -> {0, +, 1, +, a_2}_1 */
2153 res = get_instantiated_value (cache, instantiate_below, chrec);
2154 if (res)
2155 return res;
2157 res = chrec_dont_know;
2158 set_instantiated_value (cache, instantiate_below, chrec, res);
2160 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2162 /* If the analysis yields a parametric chrec, instantiate the
2163 result again. */
2164 res = analyze_scalar_evolution (def_loop, chrec);
2166 /* Don't instantiate loop-closed-ssa phi nodes. */
2167 if (TREE_CODE (res) == SSA_NAME
2168 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2169 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2170 > loop_depth (def_loop))))
2172 if (res == chrec)
2173 res = loop_closed_phi_def (chrec);
2174 else
2175 res = chrec;
2177 if (res == NULL_TREE)
2178 res = chrec_dont_know;
2181 else if (res != chrec_dont_know)
2182 res = instantiate_scev_1 (instantiate_below, evolution_loop, res,
2183 fold_conversions, cache, size_expr);
2185 /* Store the correct value to the cache. */
2186 set_instantiated_value (cache, instantiate_below, chrec, res);
2187 return res;
2189 case POLYNOMIAL_CHREC:
2190 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2191 CHREC_LEFT (chrec), fold_conversions, cache,
2192 size_expr);
2193 if (op0 == chrec_dont_know)
2194 return chrec_dont_know;
2196 op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
2197 CHREC_RIGHT (chrec), fold_conversions, cache,
2198 size_expr);
2199 if (op1 == chrec_dont_know)
2200 return chrec_dont_know;
2202 if (CHREC_LEFT (chrec) != op0
2203 || CHREC_RIGHT (chrec) != op1)
2205 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2206 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2208 return chrec;
2210 case POINTER_PLUS_EXPR:
2211 case PLUS_EXPR:
2212 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2213 TREE_OPERAND (chrec, 0), fold_conversions, cache,
2214 size_expr);
2215 if (op0 == chrec_dont_know)
2216 return chrec_dont_know;
2218 op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
2219 TREE_OPERAND (chrec, 1), fold_conversions, cache,
2220 size_expr);
2221 if (op1 == chrec_dont_know)
2222 return chrec_dont_know;
2224 if (TREE_OPERAND (chrec, 0) != op0
2225 || TREE_OPERAND (chrec, 1) != op1)
2227 op0 = chrec_convert (type, op0, NULL);
2228 op1 = chrec_convert_rhs (type, op1, NULL);
2229 chrec = chrec_fold_plus (type, op0, op1);
2231 return chrec;
2233 case MINUS_EXPR:
2234 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2235 TREE_OPERAND (chrec, 0), fold_conversions, cache,
2236 size_expr);
2237 if (op0 == chrec_dont_know)
2238 return chrec_dont_know;
2240 op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
2241 TREE_OPERAND (chrec, 1),
2242 fold_conversions, cache, size_expr);
2243 if (op1 == chrec_dont_know)
2244 return chrec_dont_know;
2246 if (TREE_OPERAND (chrec, 0) != op0
2247 || TREE_OPERAND (chrec, 1) != op1)
2249 op0 = chrec_convert (type, op0, NULL);
2250 op1 = chrec_convert (type, op1, NULL);
2251 chrec = chrec_fold_minus (type, op0, op1);
2253 return chrec;
2255 case MULT_EXPR:
2256 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2257 TREE_OPERAND (chrec, 0),
2258 fold_conversions, cache, size_expr);
2259 if (op0 == chrec_dont_know)
2260 return chrec_dont_know;
2262 op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
2263 TREE_OPERAND (chrec, 1),
2264 fold_conversions, cache, size_expr);
2265 if (op1 == chrec_dont_know)
2266 return chrec_dont_know;
2268 if (TREE_OPERAND (chrec, 0) != op0
2269 || TREE_OPERAND (chrec, 1) != op1)
2271 op0 = chrec_convert (type, op0, NULL);
2272 op1 = chrec_convert (type, op1, NULL);
2273 chrec = chrec_fold_multiply (type, op0, op1);
2275 return chrec;
2277 CASE_CONVERT:
2278 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2279 TREE_OPERAND (chrec, 0),
2280 fold_conversions, cache, size_expr);
2281 if (op0 == chrec_dont_know)
2282 return chrec_dont_know;
2284 if (fold_conversions)
2286 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2287 if (tmp)
2288 return tmp;
2291 if (op0 == TREE_OPERAND (chrec, 0))
2292 return chrec;
2294 /* If we used chrec_convert_aggressive, we can no longer assume that
2295 signed chrecs do not overflow, as chrec_convert does, so avoid
2296 calling it in that case. */
2297 if (fold_conversions)
2298 return fold_convert (TREE_TYPE (chrec), op0);
2300 return chrec_convert (TREE_TYPE (chrec), op0, NULL);
2302 case BIT_NOT_EXPR:
2303 /* Handle ~X as -1 - X. */
2304 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2305 TREE_OPERAND (chrec, 0),
2306 fold_conversions, cache, size_expr);
2307 if (op0 == chrec_dont_know)
2308 return chrec_dont_know;
2310 if (TREE_OPERAND (chrec, 0) != op0)
2312 op0 = chrec_convert (type, op0, NULL);
2313 chrec = chrec_fold_minus (type,
2314 fold_convert (type,
2315 integer_minus_one_node),
2316 op0);
2318 return chrec;
2320 case SCEV_NOT_KNOWN:
2321 return chrec_dont_know;
2323 case SCEV_KNOWN:
2324 return chrec_known;
2326 default:
2327 break;
2330 if (VL_EXP_CLASS_P (chrec))
2331 return chrec_dont_know;
2333 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2335 case 3:
2336 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2337 TREE_OPERAND (chrec, 0),
2338 fold_conversions, cache, size_expr);
2339 if (op0 == chrec_dont_know)
2340 return chrec_dont_know;
2342 op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
2343 TREE_OPERAND (chrec, 1),
2344 fold_conversions, cache, size_expr);
2345 if (op1 == chrec_dont_know)
2346 return chrec_dont_know;
2348 op2 = instantiate_scev_1 (instantiate_below, evolution_loop,
2349 TREE_OPERAND (chrec, 2),
2350 fold_conversions, cache, size_expr);
2351 if (op2 == chrec_dont_know)
2352 return chrec_dont_know;
2354 if (op0 == TREE_OPERAND (chrec, 0)
2355 && op1 == TREE_OPERAND (chrec, 1)
2356 && op2 == TREE_OPERAND (chrec, 2))
2357 return chrec;
2359 return fold_build3 (TREE_CODE (chrec),
2360 TREE_TYPE (chrec), op0, op1, op2);
2362 case 2:
2363 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2364 TREE_OPERAND (chrec, 0),
2365 fold_conversions, cache, size_expr);
2366 if (op0 == chrec_dont_know)
2367 return chrec_dont_know;
2369 op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
2370 TREE_OPERAND (chrec, 1),
2371 fold_conversions, cache, size_expr);
2372 if (op1 == chrec_dont_know)
2373 return chrec_dont_know;
2375 if (op0 == TREE_OPERAND (chrec, 0)
2376 && op1 == TREE_OPERAND (chrec, 1))
2377 return chrec;
2378 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2380 case 1:
2381 op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
2382 TREE_OPERAND (chrec, 0),
2383 fold_conversions, cache, size_expr);
2384 if (op0 == chrec_dont_know)
2385 return chrec_dont_know;
2386 if (op0 == TREE_OPERAND (chrec, 0))
2387 return chrec;
2388 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2390 case 0:
2391 return chrec;
2393 default:
2394 break;
2397 /* Too complicated to handle. */
2398 return chrec_dont_know;
2401 /* Analyze all the parameters of the chrec that were left under a
2402 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2403 recursive instantiation of parameters: a parameter is a variable
2404 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2405 a function parameter. */
2407 tree
2408 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2409 tree chrec)
2411 tree res;
2412 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2414 if (dump_file && (dump_flags & TDF_DETAILS))
2416 fprintf (dump_file, "(instantiate_scev \n");
2417 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2418 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2419 fprintf (dump_file, " (chrec = ");
2420 print_generic_expr (dump_file, chrec, 0);
2421 fprintf (dump_file, ")\n");
2424 res = instantiate_scev_1 (instantiate_below, evolution_loop, chrec, false,
2425 cache, 0);
2427 if (dump_file && (dump_flags & TDF_DETAILS))
2429 fprintf (dump_file, " (res = ");
2430 print_generic_expr (dump_file, res, 0);
2431 fprintf (dump_file, "))\n");
2434 htab_delete (cache);
2436 return res;
2439 /* Similar to instantiate_parameters, but does not introduce the
2440 evolutions in outer loops for LOOP invariants in CHREC, and does not
2441 care about causing overflows, as long as they do not affect value
2442 of an expression. */
2444 tree
2445 resolve_mixers (struct loop *loop, tree chrec)
2447 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2448 tree ret = instantiate_scev_1 (block_before_loop (loop), loop, chrec, true,
2449 cache, 0);
2450 htab_delete (cache);
2451 return ret;
2454 /* Entry point for the analysis of the number of iterations pass.
2455 This function tries to safely approximate the number of iterations
2456 the loop will run. When this property is not decidable at compile
2457 time, the result is chrec_dont_know. Otherwise the result is
2458 a scalar or a symbolic parameter.
2460 Example of analysis: suppose that the loop has an exit condition:
2462 "if (b > 49) goto end_loop;"
2464 and that in a previous analysis we have determined that the
2465 variable 'b' has an evolution function:
2467 "EF = {23, +, 5}_2".
2469 When we evaluate the function at the point 5, i.e. the value of the
2470 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2471 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2472 the loop body has been executed 6 times. */
2474 tree
2475 number_of_latch_executions (struct loop *loop)
2477 tree res, type;
2478 edge exit;
2479 struct tree_niter_desc niter_desc;
2481 /* Determine whether the number_of_iterations_in_loop has already
2482 been computed. */
2483 res = loop->nb_iterations;
2484 if (res)
2485 return res;
2486 res = chrec_dont_know;
2488 if (dump_file && (dump_flags & TDF_DETAILS))
2489 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2491 exit = single_exit (loop);
2492 if (!exit)
2493 goto end;
2495 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2496 goto end;
2498 type = TREE_TYPE (niter_desc.niter);
2499 if (integer_nonzerop (niter_desc.may_be_zero))
2500 res = build_int_cst (type, 0);
2501 else if (integer_zerop (niter_desc.may_be_zero))
2502 res = niter_desc.niter;
2503 else
2504 res = chrec_dont_know;
2506 end:
2507 return set_nb_iterations_in_loop (loop, res);
2510 /* Returns the number of executions of the exit condition of LOOP,
2511 i.e., the number by one higher than number_of_latch_executions.
2512 Note that unlike number_of_latch_executions, this number does
2513 not necessarily fit in the unsigned variant of the type of
2514 the control variable -- if the number of iterations is a constant,
2515 we return chrec_dont_know if adding one to number_of_latch_executions
2516 overflows; however, in case the number of iterations is symbolic
2517 expression, the caller is responsible for dealing with this
2518 the possible overflow. */
2520 tree
2521 number_of_exit_cond_executions (struct loop *loop)
2523 tree ret = number_of_latch_executions (loop);
2524 tree type = chrec_type (ret);
2526 if (chrec_contains_undetermined (ret))
2527 return ret;
2529 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2530 if (TREE_CODE (ret) == INTEGER_CST
2531 && TREE_OVERFLOW (ret))
2532 return chrec_dont_know;
2534 return ret;
2537 /* One of the drivers for testing the scalar evolutions analysis.
2538 This function computes the number of iterations for all the loops
2539 from the EXIT_CONDITIONS array. */
2541 static void
2542 number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions)
2544 unsigned int i;
2545 unsigned nb_chrec_dont_know_loops = 0;
2546 unsigned nb_static_loops = 0;
2547 gimple cond;
2549 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
2551 tree res = number_of_latch_executions (loop_containing_stmt (cond));
2552 if (chrec_contains_undetermined (res))
2553 nb_chrec_dont_know_loops++;
2554 else
2555 nb_static_loops++;
2558 if (dump_file)
2560 fprintf (dump_file, "\n(\n");
2561 fprintf (dump_file, "-----------------------------------------\n");
2562 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2563 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2564 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2565 fprintf (dump_file, "-----------------------------------------\n");
2566 fprintf (dump_file, ")\n\n");
2568 print_loops (dump_file, 3);
2574 /* Counters for the stats. */
2576 struct chrec_stats
2578 unsigned nb_chrecs;
2579 unsigned nb_affine;
2580 unsigned nb_affine_multivar;
2581 unsigned nb_higher_poly;
2582 unsigned nb_chrec_dont_know;
2583 unsigned nb_undetermined;
2586 /* Reset the counters. */
2588 static inline void
2589 reset_chrecs_counters (struct chrec_stats *stats)
2591 stats->nb_chrecs = 0;
2592 stats->nb_affine = 0;
2593 stats->nb_affine_multivar = 0;
2594 stats->nb_higher_poly = 0;
2595 stats->nb_chrec_dont_know = 0;
2596 stats->nb_undetermined = 0;
2599 /* Dump the contents of a CHREC_STATS structure. */
2601 static void
2602 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2604 fprintf (file, "\n(\n");
2605 fprintf (file, "-----------------------------------------\n");
2606 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2607 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2608 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2609 stats->nb_higher_poly);
2610 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2611 fprintf (file, "-----------------------------------------\n");
2612 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2613 fprintf (file, "%d\twith undetermined coefficients\n",
2614 stats->nb_undetermined);
2615 fprintf (file, "-----------------------------------------\n");
2616 fprintf (file, "%d\tchrecs in the scev database\n",
2617 (int) htab_elements (scalar_evolution_info));
2618 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2619 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2620 fprintf (file, "-----------------------------------------\n");
2621 fprintf (file, ")\n\n");
2624 /* Gather statistics about CHREC. */
2626 static void
2627 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2629 if (dump_file && (dump_flags & TDF_STATS))
2631 fprintf (dump_file, "(classify_chrec ");
2632 print_generic_expr (dump_file, chrec, 0);
2633 fprintf (dump_file, "\n");
2636 stats->nb_chrecs++;
2638 if (chrec == NULL_TREE)
2640 stats->nb_undetermined++;
2641 return;
2644 switch (TREE_CODE (chrec))
2646 case POLYNOMIAL_CHREC:
2647 if (evolution_function_is_affine_p (chrec))
2649 if (dump_file && (dump_flags & TDF_STATS))
2650 fprintf (dump_file, " affine_univariate\n");
2651 stats->nb_affine++;
2653 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2655 if (dump_file && (dump_flags & TDF_STATS))
2656 fprintf (dump_file, " affine_multivariate\n");
2657 stats->nb_affine_multivar++;
2659 else
2661 if (dump_file && (dump_flags & TDF_STATS))
2662 fprintf (dump_file, " higher_degree_polynomial\n");
2663 stats->nb_higher_poly++;
2666 break;
2668 default:
2669 break;
2672 if (chrec_contains_undetermined (chrec))
2674 if (dump_file && (dump_flags & TDF_STATS))
2675 fprintf (dump_file, " undetermined\n");
2676 stats->nb_undetermined++;
2679 if (dump_file && (dump_flags & TDF_STATS))
2680 fprintf (dump_file, ")\n");
2683 /* One of the drivers for testing the scalar evolutions analysis.
2684 This function analyzes the scalar evolution of all the scalars
2685 defined as loop phi nodes in one of the loops from the
2686 EXIT_CONDITIONS array.
2688 TODO Optimization: A loop is in canonical form if it contains only
2689 a single scalar loop phi node. All the other scalars that have an
2690 evolution in the loop are rewritten in function of this single
2691 index. This allows the parallelization of the loop. */
2693 static void
2694 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions)
2696 unsigned int i;
2697 struct chrec_stats stats;
2698 gimple cond, phi;
2699 gimple_stmt_iterator psi;
2701 reset_chrecs_counters (&stats);
2703 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
2705 struct loop *loop;
2706 basic_block bb;
2707 tree chrec;
2709 loop = loop_containing_stmt (cond);
2710 bb = loop->header;
2712 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2714 phi = gsi_stmt (psi);
2715 if (is_gimple_reg (PHI_RESULT (phi)))
2717 chrec = instantiate_parameters
2718 (loop,
2719 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2721 if (dump_file && (dump_flags & TDF_STATS))
2722 gather_chrec_stats (chrec, &stats);
2727 if (dump_file && (dump_flags & TDF_STATS))
2728 dump_chrecs_stats (dump_file, &stats);
2731 /* Callback for htab_traverse, gathers information on chrecs in the
2732 hashtable. */
2734 static int
2735 gather_stats_on_scev_database_1 (void **slot, void *stats)
2737 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2739 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2741 return 1;
2744 /* Classify the chrecs of the whole database. */
2746 void
2747 gather_stats_on_scev_database (void)
2749 struct chrec_stats stats;
2751 if (!dump_file)
2752 return;
2754 reset_chrecs_counters (&stats);
2756 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2757 &stats);
2759 dump_chrecs_stats (dump_file, &stats);
2764 /* Initializer. */
2766 static void
2767 initialize_scalar_evolutions_analyzer (void)
2769 /* The elements below are unique. */
2770 if (chrec_dont_know == NULL_TREE)
2772 chrec_not_analyzed_yet = NULL_TREE;
2773 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2774 chrec_known = make_node (SCEV_KNOWN);
2775 TREE_TYPE (chrec_dont_know) = void_type_node;
2776 TREE_TYPE (chrec_known) = void_type_node;
2780 /* Initialize the analysis of scalar evolutions for LOOPS. */
2782 void
2783 scev_initialize (void)
2785 loop_iterator li;
2786 struct loop *loop;
2788 scalar_evolution_info = htab_create_alloc (100,
2789 hash_scev_info,
2790 eq_scev_info,
2791 del_scev_info,
2792 ggc_calloc,
2793 ggc_free);
2795 initialize_scalar_evolutions_analyzer ();
2797 FOR_EACH_LOOP (li, loop, 0)
2799 loop->nb_iterations = NULL_TREE;
2803 /* Cleans up the information cached by the scalar evolutions analysis. */
2805 void
2806 scev_reset (void)
2808 loop_iterator li;
2809 struct loop *loop;
2811 if (!scalar_evolution_info || !current_loops)
2812 return;
2814 htab_empty (scalar_evolution_info);
2815 FOR_EACH_LOOP (li, loop, 0)
2817 loop->nb_iterations = NULL_TREE;
2821 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
2822 respect to WRTO_LOOP and returns its base and step in IV if possible
2823 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
2824 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
2825 invariant in LOOP. Otherwise we require it to be an integer constant.
2827 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
2828 because it is computed in signed arithmetics). Consequently, adding an
2829 induction variable
2831 for (i = IV->base; ; i += IV->step)
2833 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
2834 false for the type of the induction variable, or you can prove that i does
2835 not wrap by some other argument. Otherwise, this might introduce undefined
2836 behavior, and
2838 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
2840 must be used instead. */
2842 bool
2843 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
2844 affine_iv *iv, bool allow_nonconstant_step)
2846 tree type, ev;
2847 bool folded_casts;
2849 iv->base = NULL_TREE;
2850 iv->step = NULL_TREE;
2851 iv->no_overflow = false;
2853 type = TREE_TYPE (op);
2854 if (TREE_CODE (type) != INTEGER_TYPE
2855 && TREE_CODE (type) != POINTER_TYPE)
2856 return false;
2858 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
2859 &folded_casts);
2860 if (chrec_contains_undetermined (ev)
2861 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
2862 return false;
2864 if (tree_does_not_contain_chrecs (ev))
2866 iv->base = ev;
2867 iv->step = build_int_cst (TREE_TYPE (ev), 0);
2868 iv->no_overflow = true;
2869 return true;
2872 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2873 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
2874 return false;
2876 iv->step = CHREC_RIGHT (ev);
2877 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
2878 || tree_contains_chrecs (iv->step, NULL))
2879 return false;
2881 iv->base = CHREC_LEFT (ev);
2882 if (tree_contains_chrecs (iv->base, NULL))
2883 return false;
2885 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2887 return true;
2890 /* Runs the analysis of scalar evolutions. */
2892 void
2893 scev_analysis (void)
2895 VEC(gimple,heap) *exit_conditions;
2897 exit_conditions = VEC_alloc (gimple, heap, 37);
2898 select_loops_exit_conditions (&exit_conditions);
2900 if (dump_file && (dump_flags & TDF_STATS))
2901 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2903 number_of_iterations_for_all_loops (&exit_conditions);
2904 VEC_free (gimple, heap, exit_conditions);
2907 /* Finalize the scalar evolution analysis. */
2909 void
2910 scev_finalize (void)
2912 if (!scalar_evolution_info)
2913 return;
2914 htab_delete (scalar_evolution_info);
2915 scalar_evolution_info = NULL;
2918 /* Returns true if the expression EXPR is considered to be too expensive
2919 for scev_const_prop. */
2921 bool
2922 expression_expensive_p (tree expr)
2924 enum tree_code code;
2926 if (is_gimple_val (expr))
2927 return false;
2929 code = TREE_CODE (expr);
2930 if (code == TRUNC_DIV_EXPR
2931 || code == CEIL_DIV_EXPR
2932 || code == FLOOR_DIV_EXPR
2933 || code == ROUND_DIV_EXPR
2934 || code == TRUNC_MOD_EXPR
2935 || code == CEIL_MOD_EXPR
2936 || code == FLOOR_MOD_EXPR
2937 || code == ROUND_MOD_EXPR
2938 || code == EXACT_DIV_EXPR)
2940 /* Division by power of two is usually cheap, so we allow it.
2941 Forbid anything else. */
2942 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
2943 return true;
2946 switch (TREE_CODE_CLASS (code))
2948 case tcc_binary:
2949 case tcc_comparison:
2950 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
2951 return true;
2953 /* Fallthru. */
2954 case tcc_unary:
2955 return expression_expensive_p (TREE_OPERAND (expr, 0));
2957 default:
2958 return true;
2962 /* Replace ssa names for that scev can prove they are constant by the
2963 appropriate constants. Also perform final value replacement in loops,
2964 in case the replacement expressions are cheap.
2966 We only consider SSA names defined by phi nodes; rest is left to the
2967 ordinary constant propagation pass. */
2969 unsigned int
2970 scev_const_prop (void)
2972 basic_block bb;
2973 tree name, type, ev;
2974 gimple phi, ass;
2975 struct loop *loop, *ex_loop;
2976 bitmap ssa_names_to_remove = NULL;
2977 unsigned i;
2978 loop_iterator li;
2979 gimple_stmt_iterator psi;
2981 if (number_of_loops () <= 1)
2982 return 0;
2984 FOR_EACH_BB (bb)
2986 loop = bb->loop_father;
2988 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2990 phi = gsi_stmt (psi);
2991 name = PHI_RESULT (phi);
2993 if (!is_gimple_reg (name))
2994 continue;
2996 type = TREE_TYPE (name);
2998 if (!POINTER_TYPE_P (type)
2999 && !INTEGRAL_TYPE_P (type))
3000 continue;
3002 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3003 if (!is_gimple_min_invariant (ev)
3004 || !may_propagate_copy (name, ev))
3005 continue;
3007 /* Replace the uses of the name. */
3008 if (name != ev)
3009 replace_uses_by (name, ev);
3011 if (!ssa_names_to_remove)
3012 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3013 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3017 /* Remove the ssa names that were replaced by constants. We do not
3018 remove them directly in the previous cycle, since this
3019 invalidates scev cache. */
3020 if (ssa_names_to_remove)
3022 bitmap_iterator bi;
3024 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3026 gimple_stmt_iterator psi;
3027 name = ssa_name (i);
3028 phi = SSA_NAME_DEF_STMT (name);
3030 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3031 psi = gsi_for_stmt (phi);
3032 remove_phi_node (&psi, true);
3035 BITMAP_FREE (ssa_names_to_remove);
3036 scev_reset ();
3039 /* Now the regular final value replacement. */
3040 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
3042 edge exit;
3043 tree def, rslt, niter;
3044 gimple_stmt_iterator bsi;
3046 /* If we do not know exact number of iterations of the loop, we cannot
3047 replace the final value. */
3048 exit = single_exit (loop);
3049 if (!exit)
3050 continue;
3052 niter = number_of_latch_executions (loop);
3053 if (niter == chrec_dont_know)
3054 continue;
3056 /* Ensure that it is possible to insert new statements somewhere. */
3057 if (!single_pred_p (exit->dest))
3058 split_loop_exit_edge (exit);
3059 bsi = gsi_after_labels (exit->dest);
3061 ex_loop = superloop_at_depth (loop,
3062 loop_depth (exit->dest->loop_father) + 1);
3064 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3066 phi = gsi_stmt (psi);
3067 rslt = PHI_RESULT (phi);
3068 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3069 if (!is_gimple_reg (def))
3071 gsi_next (&psi);
3072 continue;
3075 if (!POINTER_TYPE_P (TREE_TYPE (def))
3076 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3078 gsi_next (&psi);
3079 continue;
3082 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
3083 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3084 if (!tree_does_not_contain_chrecs (def)
3085 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3086 /* Moving the computation from the loop may prolong life range
3087 of some ssa names, which may cause problems if they appear
3088 on abnormal edges. */
3089 || contains_abnormal_ssa_name_p (def)
3090 /* Do not emit expensive expressions. The rationale is that
3091 when someone writes a code like
3093 while (n > 45) n -= 45;
3095 he probably knows that n is not large, and does not want it
3096 to be turned into n %= 45. */
3097 || expression_expensive_p (def))
3099 gsi_next (&psi);
3100 continue;
3103 /* Eliminate the PHI node and replace it by a computation outside
3104 the loop. */
3105 def = unshare_expr (def);
3106 remove_phi_node (&psi, false);
3108 def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
3109 true, GSI_SAME_STMT);
3110 ass = gimple_build_assign (rslt, def);
3111 gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
3114 return 0;
3117 #include "gt-tree-scalar-evolution.h"