1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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
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
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/>. */
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
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.
76 Example 1: Illustration of the basic algorithm.
82 | if (c > 10) exit_loop
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:
120 or in terms of a C program:
123 | for (x = 0; x <= 7; x++)
129 Example 2a: Illustration of the algorithm on nested loops.
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:
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:
158 Example 2b: Multivariate chains of recurrences.
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.
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.
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.
231 Based on these symbolic chrecs, it is possible to refine this
232 information into the more precise PERIODIC_CHRECs:
237 This transformation is not yet implemented.
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
259 #include "coretypes.h"
263 #include "basic-block.h"
264 #include "diagnostic.h"
265 #include "tree-flow.h"
266 #include "tree-dump.h"
269 #include "tree-chrec.h"
270 #include "tree-scalar-evolution.h"
271 #include "tree-pass.h"
275 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
277 /* The cached information about an SSA name VAR, claiming that below
278 basic block INSTANTIATED_BELOW, the value of VAR can be expressed
281 struct GTY(()) scev_info_str {
282 basic_block instantiated_below;
287 /* Counters for the scev database. */
288 static unsigned nb_set_scev = 0;
289 static unsigned nb_get_scev = 0;
291 /* The following trees are unique elements. Thus the comparison of
292 another element to these elements should be done on the pointer to
293 these trees, and not on their value. */
295 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
296 tree chrec_not_analyzed_yet;
298 /* Reserved to the cases where the analyzer has detected an
299 undecidable property at compile time. */
300 tree chrec_dont_know;
302 /* When the analyzer has detected that a property will never
303 happen, then it qualifies it with chrec_known. */
306 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
309 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
311 static inline struct scev_info_str *
312 new_scev_info_str (basic_block instantiated_below, tree var)
314 struct scev_info_str *res;
316 res = GGC_NEW (struct scev_info_str);
318 res->chrec = chrec_not_analyzed_yet;
319 res->instantiated_below = instantiated_below;
324 /* Computes a hash function for database element ELT. */
327 hash_scev_info (const void *elt)
329 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
332 /* Compares database elements E1 and E2. */
335 eq_scev_info (const void *e1, const void *e2)
337 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
338 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
340 return (elt1->var == elt2->var
341 && elt1->instantiated_below == elt2->instantiated_below);
344 /* Deletes database element E. */
347 del_scev_info (void *e)
352 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
353 A first query on VAR returns chrec_not_analyzed_yet. */
356 find_var_scev_info (basic_block instantiated_below, tree var)
358 struct scev_info_str *res;
359 struct scev_info_str tmp;
363 tmp.instantiated_below = instantiated_below;
364 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
367 *slot = new_scev_info_str (instantiated_below, var);
368 res = (struct scev_info_str *) *slot;
373 /* Return true when CHREC contains symbolic names defined in
377 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
381 if (chrec == NULL_TREE)
384 if (is_gimple_min_invariant (chrec))
387 if (TREE_CODE (chrec) == VAR_DECL
388 || TREE_CODE (chrec) == PARM_DECL
389 || TREE_CODE (chrec) == FUNCTION_DECL
390 || TREE_CODE (chrec) == LABEL_DECL
391 || TREE_CODE (chrec) == RESULT_DECL
392 || TREE_CODE (chrec) == FIELD_DECL)
395 if (TREE_CODE (chrec) == SSA_NAME)
397 gimple def = SSA_NAME_DEF_STMT (chrec);
398 struct loop *def_loop = loop_containing_stmt (def);
399 struct loop *loop = get_loop (loop_nb);
401 if (def_loop == NULL)
404 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
410 n = TREE_OPERAND_LENGTH (chrec);
411 for (i = 0; i < n; i++)
412 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
418 /* Return true when PHI is a loop-phi-node. */
421 loop_phi_node_p (gimple phi)
423 /* The implementation of this function is based on the following
424 property: "all the loop-phi-nodes of a loop are contained in the
425 loop's header basic block". */
427 return loop_containing_stmt (phi)->header == gimple_bb (phi);
430 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
431 In general, in the case of multivariate evolutions we want to get
432 the evolution in different loops. LOOP specifies the level for
433 which to get the evolution.
437 | for (j = 0; j < 100; j++)
439 | for (k = 0; k < 100; k++)
441 | i = k + j; - Here the value of i is a function of j, k.
443 | ... = i - Here the value of i is a function of j.
445 | ... = i - Here the value of i is a scalar.
451 | i_1 = phi (i_0, i_2)
455 This loop has the same effect as:
456 LOOP_1 has the same effect as:
460 The overall effect of the loop, "i_0 + 20" in the previous example,
461 is obtained by passing in the parameters: LOOP = 1,
462 EVOLUTION_FN = {i_0, +, 2}_1.
466 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
470 if (evolution_fn == chrec_dont_know)
471 return chrec_dont_know;
473 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
475 struct loop *inner_loop = get_chrec_loop (evolution_fn);
477 if (inner_loop == loop
478 || flow_loop_nested_p (loop, inner_loop))
480 tree nb_iter = number_of_latch_executions (inner_loop);
482 if (nb_iter == chrec_dont_know)
483 return chrec_dont_know;
488 /* evolution_fn is the evolution function in LOOP. Get
489 its value in the nb_iter-th iteration. */
490 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
492 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
493 res = instantiate_parameters (loop, res);
495 /* Continue the computation until ending on a parent of LOOP. */
496 return compute_overall_effect_of_inner_loop (loop, res);
503 /* If the evolution function is an invariant, there is nothing to do. */
504 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
508 return chrec_dont_know;
511 /* Determine whether the CHREC is always positive/negative. If the expression
512 cannot be statically analyzed, return false, otherwise set the answer into
516 chrec_is_positive (tree chrec, bool *value)
518 bool value0, value1, value2;
519 tree end_value, nb_iter;
521 switch (TREE_CODE (chrec))
523 case POLYNOMIAL_CHREC:
524 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
525 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
528 /* FIXME -- overflows. */
529 if (value0 == value1)
535 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
536 and the proof consists in showing that the sign never
537 changes during the execution of the loop, from 0 to
538 loop->nb_iterations. */
539 if (!evolution_function_is_affine_p (chrec))
542 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
543 if (chrec_contains_undetermined (nb_iter))
547 /* TODO -- If the test is after the exit, we may decrease the number of
548 iterations by one. */
550 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
553 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
555 if (!chrec_is_positive (end_value, &value2))
559 return value0 == value1;
562 *value = (tree_int_cst_sgn (chrec) == 1);
570 /* Associate CHREC to SCALAR. */
573 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
577 if (TREE_CODE (scalar) != SSA_NAME)
580 scalar_info = find_var_scev_info (instantiated_below, scalar);
584 if (dump_flags & TDF_DETAILS)
586 fprintf (dump_file, "(set_scalar_evolution \n");
587 fprintf (dump_file, " instantiated_below = %d \n",
588 instantiated_below->index);
589 fprintf (dump_file, " (scalar = ");
590 print_generic_expr (dump_file, scalar, 0);
591 fprintf (dump_file, ")\n (scalar_evolution = ");
592 print_generic_expr (dump_file, chrec, 0);
593 fprintf (dump_file, "))\n");
595 if (dump_flags & TDF_STATS)
599 *scalar_info = chrec;
602 /* Retrieve the chrec associated to SCALAR instantiated below
603 INSTANTIATED_BELOW block. */
606 get_scalar_evolution (basic_block instantiated_below, tree scalar)
612 if (dump_flags & TDF_DETAILS)
614 fprintf (dump_file, "(get_scalar_evolution \n");
615 fprintf (dump_file, " (scalar = ");
616 print_generic_expr (dump_file, scalar, 0);
617 fprintf (dump_file, ")\n");
619 if (dump_flags & TDF_STATS)
623 switch (TREE_CODE (scalar))
626 res = *find_var_scev_info (instantiated_below, scalar);
636 res = chrec_not_analyzed_yet;
640 if (dump_file && (dump_flags & TDF_DETAILS))
642 fprintf (dump_file, " (scalar_evolution = ");
643 print_generic_expr (dump_file, res, 0);
644 fprintf (dump_file, "))\n");
650 /* Helper function for add_to_evolution. Returns the evolution
651 function for an assignment of the form "a = b + c", where "a" and
652 "b" are on the strongly connected component. CHREC_BEFORE is the
653 information that we already have collected up to this point.
654 TO_ADD is the evolution of "c".
656 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
657 evolution the expression TO_ADD, otherwise construct an evolution
658 part for this loop. */
661 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
664 tree type, left, right;
665 struct loop *loop = get_loop (loop_nb), *chloop;
667 switch (TREE_CODE (chrec_before))
669 case POLYNOMIAL_CHREC:
670 chloop = get_chrec_loop (chrec_before);
672 || flow_loop_nested_p (chloop, loop))
676 type = chrec_type (chrec_before);
678 /* When there is no evolution part in this loop, build it. */
683 right = SCALAR_FLOAT_TYPE_P (type)
684 ? build_real (type, dconst0)
685 : build_int_cst (type, 0);
689 var = CHREC_VARIABLE (chrec_before);
690 left = CHREC_LEFT (chrec_before);
691 right = CHREC_RIGHT (chrec_before);
694 to_add = chrec_convert (type, to_add, at_stmt);
695 right = chrec_convert_rhs (type, right, at_stmt);
696 right = chrec_fold_plus (chrec_type (right), right, to_add);
697 return build_polynomial_chrec (var, left, right);
701 gcc_assert (flow_loop_nested_p (loop, chloop));
703 /* Search the evolution in LOOP_NB. */
704 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
706 right = CHREC_RIGHT (chrec_before);
707 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
708 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
713 /* These nodes do not depend on a loop. */
714 if (chrec_before == chrec_dont_know)
715 return chrec_dont_know;
718 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
719 return build_polynomial_chrec (loop_nb, left, right);
723 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
726 Description (provided for completeness, for those who read code in
727 a plane, and for my poor 62 bytes brain that would have forgotten
728 all this in the next two or three months):
730 The algorithm of translation of programs from the SSA representation
731 into the chrecs syntax is based on a pattern matching. After having
732 reconstructed the overall tree expression for a loop, there are only
733 two cases that can arise:
735 1. a = loop-phi (init, a + expr)
736 2. a = loop-phi (init, expr)
738 where EXPR is either a scalar constant with respect to the analyzed
739 loop (this is a degree 0 polynomial), or an expression containing
740 other loop-phi definitions (these are higher degree polynomials).
747 | a = phi (init, a + 5)
754 | a = phi (inita, 2 * b + 3)
755 | b = phi (initb, b + 1)
758 For the first case, the semantics of the SSA representation is:
760 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
762 that is, there is a loop index "x" that determines the scalar value
763 of the variable during the loop execution. During the first
764 iteration, the value is that of the initial condition INIT, while
765 during the subsequent iterations, it is the sum of the initial
766 condition with the sum of all the values of EXPR from the initial
767 iteration to the before last considered iteration.
769 For the second case, the semantics of the SSA program is:
771 | a (x) = init, if x = 0;
772 | expr (x - 1), otherwise.
774 The second case corresponds to the PEELED_CHREC, whose syntax is
775 close to the syntax of a loop-phi-node:
777 | phi (init, expr) vs. (init, expr)_x
779 The proof of the translation algorithm for the first case is a
780 proof by structural induction based on the degree of EXPR.
783 When EXPR is a constant with respect to the analyzed loop, or in
784 other words when EXPR is a polynomial of degree 0, the evolution of
785 the variable A in the loop is an affine function with an initial
786 condition INIT, and a step EXPR. In order to show this, we start
787 from the semantics of the SSA representation:
789 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
791 and since "expr (j)" is a constant with respect to "j",
793 f (x) = init + x * expr
795 Finally, based on the semantics of the pure sum chrecs, by
796 identification we get the corresponding chrecs syntax:
798 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
799 f (x) -> {init, +, expr}_x
802 Suppose that EXPR is a polynomial of degree N with respect to the
803 analyzed loop_x for which we have already determined that it is
804 written under the chrecs syntax:
806 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
808 We start from the semantics of the SSA program:
810 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
812 | f (x) = init + \sum_{j = 0}^{x - 1}
813 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
815 | f (x) = init + \sum_{j = 0}^{x - 1}
816 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
818 | f (x) = init + \sum_{k = 0}^{n - 1}
819 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
821 | f (x) = init + \sum_{k = 0}^{n - 1}
822 | (b_k * \binom{x}{k + 1})
824 | f (x) = init + b_0 * \binom{x}{1} + ...
825 | + b_{n-1} * \binom{x}{n}
827 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
828 | + b_{n-1} * \binom{x}{n}
831 And finally from the definition of the chrecs syntax, we identify:
832 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
834 This shows the mechanism that stands behind the add_to_evolution
835 function. An important point is that the use of symbolic
836 parameters avoids the need of an analysis schedule.
843 | a = phi (inita, a + 2 + b)
844 | b = phi (initb, b + 1)
847 When analyzing "a", the algorithm keeps "b" symbolically:
849 | a -> {inita, +, 2 + b}_1
851 Then, after instantiation, the analyzer ends on the evolution:
853 | a -> {inita, +, 2 + initb, +, 1}_1
858 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
859 tree to_add, gimple at_stmt)
861 tree type = chrec_type (to_add);
862 tree res = NULL_TREE;
864 if (to_add == NULL_TREE)
867 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
868 instantiated at this point. */
869 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
870 /* This should not happen. */
871 return chrec_dont_know;
873 if (dump_file && (dump_flags & TDF_DETAILS))
875 fprintf (dump_file, "(add_to_evolution \n");
876 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
877 fprintf (dump_file, " (chrec_before = ");
878 print_generic_expr (dump_file, chrec_before, 0);
879 fprintf (dump_file, ")\n (to_add = ");
880 print_generic_expr (dump_file, to_add, 0);
881 fprintf (dump_file, ")\n");
884 if (code == MINUS_EXPR)
885 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
886 ? build_real (type, dconstm1)
887 : build_int_cst_type (type, -1));
889 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
891 if (dump_file && (dump_flags & TDF_DETAILS))
893 fprintf (dump_file, " (res = ");
894 print_generic_expr (dump_file, res, 0);
895 fprintf (dump_file, "))\n");
901 /* Helper function. */
904 set_nb_iterations_in_loop (struct loop *loop,
907 if (dump_file && (dump_flags & TDF_DETAILS))
909 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
910 print_generic_expr (dump_file, res, 0);
911 fprintf (dump_file, "))\n");
914 loop->nb_iterations = res;
920 /* This section selects the loops that will be good candidates for the
921 scalar evolution analysis. For the moment, greedily select all the
922 loop nests we could analyze. */
924 /* For a loop with a single exit edge, return the COND_EXPR that
925 guards the exit edge. If the expression is too difficult to
926 analyze, then give up. */
929 get_loop_exit_condition (const struct loop *loop)
932 edge exit_edge = single_exit (loop);
934 if (dump_file && (dump_flags & TDF_DETAILS))
935 fprintf (dump_file, "(get_loop_exit_condition \n ");
941 stmt = last_stmt (exit_edge->src);
942 if (gimple_code (stmt) == GIMPLE_COND)
946 if (dump_file && (dump_flags & TDF_DETAILS))
948 print_gimple_stmt (dump_file, res, 0, 0);
949 fprintf (dump_file, ")\n");
955 /* Recursively determine and enqueue the exit conditions for a loop. */
958 get_exit_conditions_rec (struct loop *loop,
959 VEC(gimple,heap) **exit_conditions)
964 /* Recurse on the inner loops, then on the next (sibling) loops. */
965 get_exit_conditions_rec (loop->inner, exit_conditions);
966 get_exit_conditions_rec (loop->next, exit_conditions);
968 if (single_exit (loop))
970 gimple loop_condition = get_loop_exit_condition (loop);
973 VEC_safe_push (gimple, heap, *exit_conditions, loop_condition);
977 /* Select the candidate loop nests for the analysis. This function
978 initializes the EXIT_CONDITIONS array. */
981 select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions)
983 struct loop *function_body = current_loops->tree_root;
985 get_exit_conditions_rec (function_body->inner, exit_conditions);
989 /* Depth first search algorithm. */
991 typedef enum t_bool {
998 static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
1000 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
1001 Return true if the strongly connected component has been found. */
1004 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
1005 tree type, tree rhs0, enum tree_code code, tree rhs1,
1006 gimple halting_phi, tree *evolution_of_loop, int limit)
1008 t_bool res = t_false;
1013 case POINTER_PLUS_EXPR:
1015 if (TREE_CODE (rhs0) == SSA_NAME)
1017 if (TREE_CODE (rhs1) == SSA_NAME)
1019 /* Match an assignment under the form:
1022 /* We want only assignments of form "name + name" contribute to
1023 LIMIT, as the other cases do not necessarily contribute to
1024 the complexity of the expression. */
1027 evol = *evolution_of_loop;
1028 res = follow_ssa_edge
1029 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
1032 *evolution_of_loop = add_to_evolution
1034 chrec_convert (type, evol, at_stmt),
1035 code, rhs1, at_stmt);
1037 else if (res == t_false)
1039 res = follow_ssa_edge
1040 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1041 evolution_of_loop, limit);
1044 *evolution_of_loop = add_to_evolution
1046 chrec_convert (type, *evolution_of_loop, at_stmt),
1047 code, rhs0, at_stmt);
1049 else if (res == t_dont_know)
1050 *evolution_of_loop = chrec_dont_know;
1053 else if (res == t_dont_know)
1054 *evolution_of_loop = chrec_dont_know;
1059 /* Match an assignment under the form:
1061 res = follow_ssa_edge
1062 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1063 evolution_of_loop, limit);
1065 *evolution_of_loop = add_to_evolution
1066 (loop->num, chrec_convert (type, *evolution_of_loop,
1068 code, rhs1, at_stmt);
1070 else if (res == t_dont_know)
1071 *evolution_of_loop = chrec_dont_know;
1075 else if (TREE_CODE (rhs1) == SSA_NAME)
1077 /* Match an assignment under the form:
1079 res = follow_ssa_edge
1080 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1081 evolution_of_loop, limit);
1083 *evolution_of_loop = add_to_evolution
1084 (loop->num, chrec_convert (type, *evolution_of_loop,
1086 code, rhs0, at_stmt);
1088 else if (res == t_dont_know)
1089 *evolution_of_loop = chrec_dont_know;
1093 /* Otherwise, match an assignment under the form:
1095 /* And there is nothing to do. */
1100 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1101 if (TREE_CODE (rhs0) == SSA_NAME)
1103 /* Match an assignment under the form:
1106 /* We want only assignments of form "name - name" contribute to
1107 LIMIT, as the other cases do not necessarily contribute to
1108 the complexity of the expression. */
1109 if (TREE_CODE (rhs1) == SSA_NAME)
1112 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1113 evolution_of_loop, limit);
1115 *evolution_of_loop = add_to_evolution
1116 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1117 MINUS_EXPR, rhs1, at_stmt);
1119 else if (res == t_dont_know)
1120 *evolution_of_loop = chrec_dont_know;
1123 /* Otherwise, match an assignment under the form:
1125 /* And there is nothing to do. */
1136 /* Follow the ssa edge into the expression EXPR.
1137 Return true if the strongly connected component has been found. */
1140 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1141 gimple halting_phi, tree *evolution_of_loop, int limit)
1143 enum tree_code code = TREE_CODE (expr);
1144 tree type = TREE_TYPE (expr), rhs0, rhs1;
1147 /* The EXPR is one of the following cases:
1151 - a POINTER_PLUS_EXPR,
1154 - other cases are not yet handled. */
1159 /* This assignment is under the form "a_1 = (cast) rhs. */
1160 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1161 halting_phi, evolution_of_loop, limit);
1162 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1166 /* This assignment is under the form "a_1 = 7". */
1171 /* This assignment is under the form: "a_1 = b_2". */
1172 res = follow_ssa_edge
1173 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1176 case POINTER_PLUS_EXPR:
1179 /* This case is under the form "rhs0 +- rhs1". */
1180 rhs0 = TREE_OPERAND (expr, 0);
1181 rhs1 = TREE_OPERAND (expr, 1);
1182 type = TREE_TYPE (rhs0);
1183 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1184 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1185 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1186 halting_phi, evolution_of_loop, limit);
1190 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1191 It must be handled as a copy assignment of the form a_1 = a_2. */
1192 rhs0 = ASSERT_EXPR_VAR (expr);
1193 if (TREE_CODE (rhs0) == SSA_NAME)
1194 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1195 halting_phi, evolution_of_loop, limit);
1208 /* Follow the ssa edge into the right hand side of an assignment STMT.
1209 Return true if the strongly connected component has been found. */
1212 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1213 gimple halting_phi, tree *evolution_of_loop, int limit)
1215 enum tree_code code = gimple_assign_rhs_code (stmt);
1216 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1222 /* This assignment is under the form "a_1 = (cast) rhs. */
1223 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1224 halting_phi, evolution_of_loop, limit);
1225 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1228 case POINTER_PLUS_EXPR:
1231 rhs1 = gimple_assign_rhs1 (stmt);
1232 rhs2 = gimple_assign_rhs2 (stmt);
1233 type = TREE_TYPE (rhs1);
1234 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1235 halting_phi, evolution_of_loop, limit);
1239 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1240 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1241 halting_phi, evolution_of_loop, limit);
1250 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1253 backedge_phi_arg_p (gimple phi, int i)
1255 const_edge e = gimple_phi_arg_edge (phi, i);
1257 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1258 about updating it anywhere, and this should work as well most of the
1260 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1266 /* Helper function for one branch of the condition-phi-node. Return
1267 true if the strongly connected component has been found following
1270 static inline t_bool
1271 follow_ssa_edge_in_condition_phi_branch (int i,
1273 gimple condition_phi,
1275 tree *evolution_of_branch,
1276 tree init_cond, int limit)
1278 tree branch = PHI_ARG_DEF (condition_phi, i);
1279 *evolution_of_branch = chrec_dont_know;
1281 /* Do not follow back edges (they must belong to an irreducible loop, which
1282 we really do not want to worry about). */
1283 if (backedge_phi_arg_p (condition_phi, i))
1286 if (TREE_CODE (branch) == SSA_NAME)
1288 *evolution_of_branch = init_cond;
1289 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1290 evolution_of_branch, limit);
1293 /* This case occurs when one of the condition branches sets
1294 the variable to a constant: i.e. a phi-node like
1295 "a_2 = PHI <a_7(5), 2(6)>;".
1297 FIXME: This case have to be refined correctly:
1298 in some cases it is possible to say something better than
1299 chrec_dont_know, for example using a wrap-around notation. */
1303 /* This function merges the branches of a condition-phi-node in a
1307 follow_ssa_edge_in_condition_phi (struct loop *loop,
1308 gimple condition_phi,
1310 tree *evolution_of_loop, int limit)
1313 tree init = *evolution_of_loop;
1314 tree evolution_of_branch;
1315 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1317 &evolution_of_branch,
1319 if (res == t_false || res == t_dont_know)
1322 *evolution_of_loop = evolution_of_branch;
1324 n = gimple_phi_num_args (condition_phi);
1325 for (i = 1; i < n; i++)
1327 /* Quickly give up when the evolution of one of the branches is
1329 if (*evolution_of_loop == chrec_dont_know)
1332 /* Increase the limit by the PHI argument number to avoid exponential
1333 time and memory complexity. */
1334 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1336 &evolution_of_branch,
1338 if (res == t_false || res == t_dont_know)
1341 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1342 evolution_of_branch);
1348 /* Follow an SSA edge in an inner loop. It computes the overall
1349 effect of the loop, and following the symbolic initial conditions,
1350 it follows the edges in the parent loop. The inner loop is
1351 considered as a single statement. */
1354 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1355 gimple loop_phi_node,
1357 tree *evolution_of_loop, int limit)
1359 struct loop *loop = loop_containing_stmt (loop_phi_node);
1360 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1362 /* Sometimes, the inner loop is too difficult to analyze, and the
1363 result of the analysis is a symbolic parameter. */
1364 if (ev == PHI_RESULT (loop_phi_node))
1366 t_bool res = t_false;
1367 int i, n = gimple_phi_num_args (loop_phi_node);
1369 for (i = 0; i < n; i++)
1371 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1374 /* Follow the edges that exit the inner loop. */
1375 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1376 if (!flow_bb_inside_loop_p (loop, bb))
1377 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1379 evolution_of_loop, limit);
1384 /* If the path crosses this loop-phi, give up. */
1386 *evolution_of_loop = chrec_dont_know;
1391 /* Otherwise, compute the overall effect of the inner loop. */
1392 ev = compute_overall_effect_of_inner_loop (loop, ev);
1393 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1394 evolution_of_loop, limit);
1397 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1398 path that is analyzed on the return walk. */
1401 follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
1402 tree *evolution_of_loop, int limit)
1404 struct loop *def_loop;
1406 if (gimple_nop_p (def))
1409 /* Give up if the path is longer than the MAX that we allow. */
1410 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1413 def_loop = loop_containing_stmt (def);
1415 switch (gimple_code (def))
1418 if (!loop_phi_node_p (def))
1419 /* DEF is a condition-phi-node. Follow the branches, and
1420 record their evolutions. Finally, merge the collected
1421 information and set the approximation to the main
1423 return follow_ssa_edge_in_condition_phi
1424 (loop, def, halting_phi, evolution_of_loop, limit);
1426 /* When the analyzed phi is the halting_phi, the
1427 depth-first search is over: we have found a path from
1428 the halting_phi to itself in the loop. */
1429 if (def == halting_phi)
1432 /* Otherwise, the evolution of the HALTING_PHI depends
1433 on the evolution of another loop-phi-node, i.e. the
1434 evolution function is a higher degree polynomial. */
1435 if (def_loop == loop)
1439 if (flow_loop_nested_p (loop, def_loop))
1440 return follow_ssa_edge_inner_loop_phi
1441 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1447 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1448 evolution_of_loop, limit);
1451 /* At this level of abstraction, the program is just a set
1452 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1453 other node to be handled. */
1460 /* Given a LOOP_PHI_NODE, this function determines the evolution
1461 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1464 analyze_evolution_in_loop (gimple loop_phi_node,
1467 int i, n = gimple_phi_num_args (loop_phi_node);
1468 tree evolution_function = chrec_not_analyzed_yet;
1469 struct loop *loop = loop_containing_stmt (loop_phi_node);
1472 if (dump_file && (dump_flags & TDF_DETAILS))
1474 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1475 fprintf (dump_file, " (loop_phi_node = ");
1476 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1477 fprintf (dump_file, ")\n");
1480 for (i = 0; i < n; i++)
1482 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1487 /* Select the edges that enter the loop body. */
1488 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1489 if (!flow_bb_inside_loop_p (loop, bb))
1492 if (TREE_CODE (arg) == SSA_NAME)
1496 ssa_chain = SSA_NAME_DEF_STMT (arg);
1498 /* Pass in the initial condition to the follow edge function. */
1500 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1502 /* If ev_fn has no evolution in the inner loop, and the
1503 init_cond is not equal to ev_fn, then we have an
1504 ambiguity between two possible values, as we cannot know
1505 the number of iterations at this point. */
1506 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1507 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1508 && !operand_equal_p (init_cond, ev_fn, 0))
1509 ev_fn = chrec_dont_know;
1514 /* When it is impossible to go back on the same
1515 loop_phi_node by following the ssa edges, the
1516 evolution is represented by a peeled chrec, i.e. the
1517 first iteration, EV_FN has the value INIT_COND, then
1518 all the other iterations it has the value of ARG.
1519 For the moment, PEELED_CHREC nodes are not built. */
1521 ev_fn = chrec_dont_know;
1523 /* When there are multiple back edges of the loop (which in fact never
1524 happens currently, but nevertheless), merge their evolutions. */
1525 evolution_function = chrec_merge (evolution_function, ev_fn);
1528 if (dump_file && (dump_flags & TDF_DETAILS))
1530 fprintf (dump_file, " (evolution_function = ");
1531 print_generic_expr (dump_file, evolution_function, 0);
1532 fprintf (dump_file, "))\n");
1535 return evolution_function;
1538 /* Given a loop-phi-node, return the initial conditions of the
1539 variable on entry of the loop. When the CCP has propagated
1540 constants into the loop-phi-node, the initial condition is
1541 instantiated, otherwise the initial condition is kept symbolic.
1542 This analyzer does not analyze the evolution outside the current
1543 loop, and leaves this task to the on-demand tree reconstructor. */
1546 analyze_initial_condition (gimple loop_phi_node)
1549 tree init_cond = chrec_not_analyzed_yet;
1550 struct loop *loop = loop_containing_stmt (loop_phi_node);
1552 if (dump_file && (dump_flags & TDF_DETAILS))
1554 fprintf (dump_file, "(analyze_initial_condition \n");
1555 fprintf (dump_file, " (loop_phi_node = \n");
1556 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1557 fprintf (dump_file, ")\n");
1560 n = gimple_phi_num_args (loop_phi_node);
1561 for (i = 0; i < n; i++)
1563 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1564 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1566 /* When the branch is oriented to the loop's body, it does
1567 not contribute to the initial condition. */
1568 if (flow_bb_inside_loop_p (loop, bb))
1571 if (init_cond == chrec_not_analyzed_yet)
1577 if (TREE_CODE (branch) == SSA_NAME)
1579 init_cond = chrec_dont_know;
1583 init_cond = chrec_merge (init_cond, branch);
1586 /* Ooops -- a loop without an entry??? */
1587 if (init_cond == chrec_not_analyzed_yet)
1588 init_cond = chrec_dont_know;
1590 /* During early loop unrolling we do not have fully constant propagated IL.
1591 Handle degenerate PHIs here to not miss important unrollings. */
1592 if (TREE_CODE (init_cond) == SSA_NAME)
1594 gimple def = SSA_NAME_DEF_STMT (init_cond);
1596 if (gimple_code (def) == GIMPLE_PHI
1597 && (res = degenerate_phi_result (def)) != NULL_TREE
1598 /* Only allow invariants here, otherwise we may break
1599 loop-closed SSA form. */
1600 && is_gimple_min_invariant (res))
1604 if (dump_file && (dump_flags & TDF_DETAILS))
1606 fprintf (dump_file, " (init_cond = ");
1607 print_generic_expr (dump_file, init_cond, 0);
1608 fprintf (dump_file, "))\n");
1614 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1617 interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
1620 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1623 if (phi_loop != loop)
1625 struct loop *subloop;
1626 tree evolution_fn = analyze_scalar_evolution
1627 (phi_loop, PHI_RESULT (loop_phi_node));
1629 /* Dive one level deeper. */
1630 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1632 /* Interpret the subloop. */
1633 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1637 /* Otherwise really interpret the loop phi. */
1638 init_cond = analyze_initial_condition (loop_phi_node);
1639 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1641 /* Verify we maintained the correct initial condition throughout
1642 possible conversions in the SSA chain. */
1643 if (res != chrec_dont_know)
1645 tree new_init = res;
1646 if (CONVERT_EXPR_P (res)
1647 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1648 new_init = fold_convert (TREE_TYPE (res),
1649 CHREC_LEFT (TREE_OPERAND (res, 0)));
1650 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1651 new_init = CHREC_LEFT (res);
1652 STRIP_USELESS_TYPE_CONVERSION (new_init);
1653 gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC);
1654 if (!operand_equal_p (init_cond, new_init, 0))
1655 return chrec_dont_know;
1661 /* This function merges the branches of a condition-phi-node,
1662 contained in the outermost loop, and whose arguments are already
1666 interpret_condition_phi (struct loop *loop, gimple condition_phi)
1668 int i, n = gimple_phi_num_args (condition_phi);
1669 tree res = chrec_not_analyzed_yet;
1671 for (i = 0; i < n; i++)
1675 if (backedge_phi_arg_p (condition_phi, i))
1677 res = chrec_dont_know;
1681 branch_chrec = analyze_scalar_evolution
1682 (loop, PHI_ARG_DEF (condition_phi, i));
1684 res = chrec_merge (res, branch_chrec);
1690 /* Interpret the operation RHS1 OP RHS2. If we didn't
1691 analyze this node before, follow the definitions until ending
1692 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1693 return path, this function propagates evolutions (ala constant copy
1694 propagation). OPND1 is not a GIMPLE expression because we could
1695 analyze the effect of an inner loop: see interpret_loop_phi. */
1698 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1699 tree type, tree rhs1, enum tree_code code, tree rhs2)
1701 tree res, chrec1, chrec2;
1703 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1705 if (is_gimple_min_invariant (rhs1))
1706 return chrec_convert (type, rhs1, at_stmt);
1708 if (code == SSA_NAME)
1709 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1712 if (code == ASSERT_EXPR)
1714 rhs1 = ASSERT_EXPR_VAR (rhs1);
1715 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1719 return chrec_dont_know;
1724 case POINTER_PLUS_EXPR:
1725 chrec1 = analyze_scalar_evolution (loop, rhs1);
1726 chrec2 = analyze_scalar_evolution (loop, rhs2);
1727 chrec1 = chrec_convert (type, chrec1, at_stmt);
1728 chrec2 = chrec_convert (sizetype, chrec2, at_stmt);
1729 res = chrec_fold_plus (type, chrec1, chrec2);
1733 chrec1 = analyze_scalar_evolution (loop, rhs1);
1734 chrec2 = analyze_scalar_evolution (loop, rhs2);
1735 chrec1 = chrec_convert (type, chrec1, at_stmt);
1736 chrec2 = chrec_convert (type, chrec2, at_stmt);
1737 res = chrec_fold_plus (type, chrec1, chrec2);
1741 chrec1 = analyze_scalar_evolution (loop, rhs1);
1742 chrec2 = analyze_scalar_evolution (loop, rhs2);
1743 chrec1 = chrec_convert (type, chrec1, at_stmt);
1744 chrec2 = chrec_convert (type, chrec2, at_stmt);
1745 res = chrec_fold_minus (type, chrec1, chrec2);
1749 chrec1 = analyze_scalar_evolution (loop, rhs1);
1750 chrec1 = chrec_convert (type, chrec1, at_stmt);
1751 /* TYPE may be integer, real or complex, so use fold_convert. */
1752 res = chrec_fold_multiply (type, chrec1,
1753 fold_convert (type, integer_minus_one_node));
1757 /* Handle ~X as -1 - X. */
1758 chrec1 = analyze_scalar_evolution (loop, rhs1);
1759 chrec1 = chrec_convert (type, chrec1, at_stmt);
1760 res = chrec_fold_minus (type,
1761 fold_convert (type, integer_minus_one_node),
1766 chrec1 = analyze_scalar_evolution (loop, rhs1);
1767 chrec2 = analyze_scalar_evolution (loop, rhs2);
1768 chrec1 = chrec_convert (type, chrec1, at_stmt);
1769 chrec2 = chrec_convert (type, chrec2, at_stmt);
1770 res = chrec_fold_multiply (type, chrec1, chrec2);
1774 chrec1 = analyze_scalar_evolution (loop, rhs1);
1775 res = chrec_convert (type, chrec1, at_stmt);
1779 res = chrec_dont_know;
1786 /* Interpret the expression EXPR. */
1789 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1791 enum tree_code code;
1792 tree type = TREE_TYPE (expr), op0, op1;
1794 if (automatically_generated_chrec_p (expr))
1797 if (TREE_CODE (expr) == POLYNOMIAL_CHREC)
1798 return chrec_dont_know;
1800 extract_ops_from_tree (expr, &code, &op0, &op1);
1802 return interpret_rhs_expr (loop, at_stmt, type,
1806 /* Interpret the rhs of the assignment STMT. */
1809 interpret_gimple_assign (struct loop *loop, gimple stmt)
1811 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1812 enum tree_code code = gimple_assign_rhs_code (stmt);
1814 return interpret_rhs_expr (loop, stmt, type,
1815 gimple_assign_rhs1 (stmt), code,
1816 gimple_assign_rhs2 (stmt));
1821 /* This section contains all the entry points:
1822 - number_of_iterations_in_loop,
1823 - analyze_scalar_evolution,
1824 - instantiate_parameters.
1827 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1828 common ancestor of DEF_LOOP and USE_LOOP. */
1831 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1832 struct loop *def_loop,
1836 if (def_loop == wrto_loop)
1839 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1840 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1842 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1845 /* Helper recursive function. */
1848 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1850 tree type = TREE_TYPE (var);
1853 struct loop *def_loop;
1855 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1856 return chrec_dont_know;
1858 if (TREE_CODE (var) != SSA_NAME)
1859 return interpret_expr (loop, NULL, var);
1861 def = SSA_NAME_DEF_STMT (var);
1862 bb = gimple_bb (def);
1863 def_loop = bb ? bb->loop_father : NULL;
1866 || !flow_bb_inside_loop_p (loop, bb))
1868 /* Keep the symbolic form. */
1873 if (res != chrec_not_analyzed_yet)
1875 if (loop != bb->loop_father)
1876 res = compute_scalar_evolution_in_loop
1877 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1882 if (loop != def_loop)
1884 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1885 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1890 switch (gimple_code (def))
1893 res = interpret_gimple_assign (loop, def);
1897 if (loop_phi_node_p (def))
1898 res = interpret_loop_phi (loop, def);
1900 res = interpret_condition_phi (loop, def);
1904 res = chrec_dont_know;
1910 /* Keep the symbolic form. */
1911 if (res == chrec_dont_know)
1914 if (loop == def_loop)
1915 set_scalar_evolution (block_before_loop (loop), var, res);
1920 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1921 LOOP. LOOP is the loop in which the variable is used.
1923 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1924 pointer to the statement that uses this variable, in order to
1925 determine the evolution function of the variable, use the following
1928 loop_p loop = loop_containing_stmt (stmt);
1929 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1930 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1934 analyze_scalar_evolution (struct loop *loop, tree var)
1938 if (dump_file && (dump_flags & TDF_DETAILS))
1940 fprintf (dump_file, "(analyze_scalar_evolution \n");
1941 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1942 fprintf (dump_file, " (scalar = ");
1943 print_generic_expr (dump_file, var, 0);
1944 fprintf (dump_file, ")\n");
1947 res = get_scalar_evolution (block_before_loop (loop), var);
1948 res = analyze_scalar_evolution_1 (loop, var, res);
1950 if (dump_file && (dump_flags & TDF_DETAILS))
1951 fprintf (dump_file, ")\n");
1956 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1957 WRTO_LOOP (which should be a superloop of USE_LOOP)
1959 FOLDED_CASTS is set to true if resolve_mixers used
1960 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1961 at the moment in order to keep things simple).
1963 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1966 for (i = 0; i < 100; i++) -- loop 1
1968 for (j = 0; j < 100; j++) -- loop 2
1975 for (t = 0; t < 100; t++) -- loop 3
1982 Both k1 and k2 are invariants in loop3, thus
1983 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1984 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1986 As they are invariant, it does not matter whether we consider their
1987 usage in loop 3 or loop 2, hence
1988 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1989 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1990 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1991 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1993 Similarly for their evolutions with respect to loop 1. The values of K2
1994 in the use in loop 2 vary independently on loop 1, thus we cannot express
1995 the evolution with respect to loop 1:
1996 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
1997 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
1998 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
1999 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2001 The value of k2 in the use in loop 1 is known, though:
2002 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2003 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2007 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2008 tree version, bool *folded_casts)
2011 tree ev = version, tmp;
2013 /* We cannot just do
2015 tmp = analyze_scalar_evolution (use_loop, version);
2016 ev = resolve_mixers (wrto_loop, tmp);
2018 as resolve_mixers would query the scalar evolution with respect to
2019 wrto_loop. For example, in the situation described in the function
2020 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2023 analyze_scalar_evolution (use_loop, version) = k2
2025 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2026 is 100, which is a wrong result, since we are interested in the
2029 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2030 each time checking that there is no evolution in the inner loop. */
2033 *folded_casts = false;
2036 tmp = analyze_scalar_evolution (use_loop, ev);
2037 ev = resolve_mixers (use_loop, tmp);
2039 if (folded_casts && tmp != ev)
2040 *folded_casts = true;
2042 if (use_loop == wrto_loop)
2045 /* If the value of the use changes in the inner loop, we cannot express
2046 its value in the outer loop (we might try to return interval chrec,
2047 but we do not have a user for it anyway) */
2048 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2050 return chrec_dont_know;
2052 use_loop = loop_outer (use_loop);
2056 /* Returns from CACHE the value for VERSION instantiated below
2057 INSTANTIATED_BELOW block. */
2060 get_instantiated_value (htab_t cache, basic_block instantiated_below,
2063 struct scev_info_str *info, pattern;
2065 pattern.var = version;
2066 pattern.instantiated_below = instantiated_below;
2067 info = (struct scev_info_str *) htab_find (cache, &pattern);
2075 /* Sets in CACHE the value of VERSION instantiated below basic block
2076 INSTANTIATED_BELOW to VAL. */
2079 set_instantiated_value (htab_t cache, basic_block instantiated_below,
2080 tree version, tree val)
2082 struct scev_info_str *info, pattern;
2085 pattern.var = version;
2086 pattern.instantiated_below = instantiated_below;
2087 slot = htab_find_slot (cache, &pattern, INSERT);
2090 *slot = new_scev_info_str (instantiated_below, version);
2091 info = (struct scev_info_str *) *slot;
2095 /* Return the closed_loop_phi node for VAR. If there is none, return
2099 loop_closed_phi_def (tree var)
2104 gimple_stmt_iterator psi;
2106 if (var == NULL_TREE
2107 || TREE_CODE (var) != SSA_NAME)
2110 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2111 exit = single_exit (loop);
2115 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2117 phi = gsi_stmt (psi);
2118 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2119 return PHI_RESULT (phi);
2125 static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
2128 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2129 and EVOLUTION_LOOP, that were left under a symbolic form.
2131 CHREC is an SSA_NAME to be instantiated.
2133 CACHE is the cache of already instantiated values.
2135 FOLD_CONVERSIONS should be set to true when the conversions that
2136 may wrap in signed/pointer type are folded, as long as the value of
2137 the chrec is preserved.
2139 SIZE_EXPR is used for computing the size of the expression to be
2140 instantiated, and to stop if it exceeds some limit. */
2143 instantiate_scev_name (basic_block instantiate_below,
2144 struct loop *evolution_loop, tree chrec,
2145 bool fold_conversions, htab_t cache, int size_expr)
2148 struct loop *def_loop;
2149 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2151 /* A parameter (or loop invariant and we do not want to include
2152 evolutions in outer loops), nothing to do. */
2154 || loop_depth (def_bb->loop_father) == 0
2155 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2158 /* We cache the value of instantiated variable to avoid exponential
2159 time complexity due to reevaluations. We also store the convenient
2160 value in the cache in order to prevent infinite recursion -- we do
2161 not want to instantiate the SSA_NAME if it is in a mixer
2162 structure. This is used for avoiding the instantiation of
2163 recursively defined functions, such as:
2165 | a_2 -> {0, +, 1, +, a_2}_1 */
2167 res = get_instantiated_value (cache, instantiate_below, chrec);
2171 res = chrec_dont_know;
2172 set_instantiated_value (cache, instantiate_below, chrec, res);
2174 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2176 /* If the analysis yields a parametric chrec, instantiate the
2178 res = analyze_scalar_evolution (def_loop, chrec);
2180 /* Don't instantiate loop-closed-ssa phi nodes. */
2181 if (TREE_CODE (res) == SSA_NAME
2182 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2183 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2184 > loop_depth (def_loop))))
2187 res = loop_closed_phi_def (chrec);
2191 if (res == NULL_TREE
2192 || !dominated_by_p (CDI_DOMINATORS, instantiate_below,
2193 gimple_bb (SSA_NAME_DEF_STMT (res))))
2194 res = chrec_dont_know;
2197 else if (res != chrec_dont_know)
2198 res = instantiate_scev_r (instantiate_below, evolution_loop, res,
2199 fold_conversions, cache, size_expr);
2201 /* Store the correct value to the cache. */
2202 set_instantiated_value (cache, instantiate_below, chrec, res);
2207 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2208 and EVOLUTION_LOOP, that were left under a symbolic form.
2210 CHREC is a polynomial chain of recurrence to be instantiated.
2212 CACHE is the cache of already instantiated values.
2214 FOLD_CONVERSIONS should be set to true when the conversions that
2215 may wrap in signed/pointer type are folded, as long as the value of
2216 the chrec is preserved.
2218 SIZE_EXPR is used for computing the size of the expression to be
2219 instantiated, and to stop if it exceeds some limit. */
2222 instantiate_scev_poly (basic_block instantiate_below,
2223 struct loop *evolution_loop, tree chrec,
2224 bool fold_conversions, htab_t cache, int size_expr)
2227 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2228 CHREC_LEFT (chrec), fold_conversions, cache,
2230 if (op0 == chrec_dont_know)
2231 return chrec_dont_know;
2233 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2234 CHREC_RIGHT (chrec), fold_conversions, cache,
2236 if (op1 == chrec_dont_know)
2237 return chrec_dont_know;
2239 if (CHREC_LEFT (chrec) != op0
2240 || CHREC_RIGHT (chrec) != op1)
2242 unsigned var = CHREC_VARIABLE (chrec);
2244 /* When the instantiated stride or base has an evolution in an
2245 innermost loop, return chrec_dont_know, as this is not a
2246 valid SCEV representation. In the reduced testcase for
2247 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2249 if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var)
2250 || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var))
2251 return chrec_dont_know;
2253 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2254 chrec = build_polynomial_chrec (var, op0, op1);
2260 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2261 and EVOLUTION_LOOP, that were left under a symbolic form.
2263 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2265 CACHE is the cache of already instantiated values.
2267 FOLD_CONVERSIONS should be set to true when the conversions that
2268 may wrap in signed/pointer type are folded, as long as the value of
2269 the chrec is preserved.
2271 SIZE_EXPR is used for computing the size of the expression to be
2272 instantiated, and to stop if it exceeds some limit. */
2275 instantiate_scev_binary (basic_block instantiate_below,
2276 struct loop *evolution_loop, tree chrec, enum tree_code code,
2277 tree type, tree c0, tree c1,
2278 bool fold_conversions, htab_t cache, int size_expr)
2281 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2282 c0, fold_conversions, cache,
2284 if (op0 == chrec_dont_know)
2285 return chrec_dont_know;
2287 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2288 c1, fold_conversions, cache,
2290 if (op1 == chrec_dont_know)
2291 return chrec_dont_know;
2296 op0 = chrec_convert (type, op0, NULL);
2297 op1 = chrec_convert_rhs (type, op1, NULL);
2301 case POINTER_PLUS_EXPR:
2303 return chrec_fold_plus (type, op0, op1);
2306 return chrec_fold_minus (type, op0, op1);
2309 return chrec_fold_multiply (type, op0, op1);
2316 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2319 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2320 and EVOLUTION_LOOP, that were left under a symbolic form.
2322 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2325 CACHE is the cache of already instantiated values.
2327 FOLD_CONVERSIONS should be set to true when the conversions that
2328 may wrap in signed/pointer type are folded, as long as the value of
2329 the chrec is preserved.
2331 SIZE_EXPR is used for computing the size of the expression to be
2332 instantiated, and to stop if it exceeds some limit. */
2335 instantiate_scev_convert (basic_block instantiate_below,
2336 struct loop *evolution_loop, tree chrec,
2338 bool fold_conversions, htab_t cache, int size_expr)
2340 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2341 fold_conversions, cache, size_expr);
2343 if (op0 == chrec_dont_know)
2344 return chrec_dont_know;
2346 if (fold_conversions)
2348 tree tmp = chrec_convert_aggressive (type, op0);
2353 if (chrec && op0 == op)
2356 /* If we used chrec_convert_aggressive, we can no longer assume that
2357 signed chrecs do not overflow, as chrec_convert does, so avoid
2358 calling it in that case. */
2359 if (fold_conversions)
2360 return fold_convert (type, op0);
2362 return chrec_convert (type, op0, NULL);
2365 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2366 and EVOLUTION_LOOP, that were left under a symbolic form.
2368 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2369 Handle ~X as -1 - X.
2370 Handle -X as -1 * X.
2372 CACHE is the cache of already instantiated values.
2374 FOLD_CONVERSIONS should be set to true when the conversions that
2375 may wrap in signed/pointer type are folded, as long as the value of
2376 the chrec is preserved.
2378 SIZE_EXPR is used for computing the size of the expression to be
2379 instantiated, and to stop if it exceeds some limit. */
2382 instantiate_scev_not (basic_block instantiate_below,
2383 struct loop *evolution_loop, tree chrec,
2384 enum tree_code code, tree type, tree op,
2385 bool fold_conversions, htab_t cache, int size_expr)
2387 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2388 fold_conversions, cache, size_expr);
2390 if (op0 == chrec_dont_know)
2391 return chrec_dont_know;
2395 op0 = chrec_convert (type, op0, NULL);
2400 return chrec_fold_minus
2401 (type, fold_convert (type, integer_minus_one_node), op0);
2404 return chrec_fold_multiply
2405 (type, fold_convert (type, integer_minus_one_node), op0);
2412 return chrec ? chrec : fold_build1 (code, type, op0);
2415 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2416 and EVOLUTION_LOOP, that were left under a symbolic form.
2418 CHREC is an expression with 3 operands to be instantiated.
2420 CACHE is the cache of already instantiated values.
2422 FOLD_CONVERSIONS should be set to true when the conversions that
2423 may wrap in signed/pointer type are folded, as long as the value of
2424 the chrec is preserved.
2426 SIZE_EXPR is used for computing the size of the expression to be
2427 instantiated, and to stop if it exceeds some limit. */
2430 instantiate_scev_3 (basic_block instantiate_below,
2431 struct loop *evolution_loop, tree chrec,
2432 bool fold_conversions, htab_t cache, int size_expr)
2435 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2436 TREE_OPERAND (chrec, 0),
2437 fold_conversions, cache, size_expr);
2438 if (op0 == chrec_dont_know)
2439 return chrec_dont_know;
2441 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2442 TREE_OPERAND (chrec, 1),
2443 fold_conversions, cache, size_expr);
2444 if (op1 == chrec_dont_know)
2445 return chrec_dont_know;
2447 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2448 TREE_OPERAND (chrec, 2),
2449 fold_conversions, cache, size_expr);
2450 if (op2 == chrec_dont_know)
2451 return chrec_dont_know;
2453 if (op0 == TREE_OPERAND (chrec, 0)
2454 && op1 == TREE_OPERAND (chrec, 1)
2455 && op2 == TREE_OPERAND (chrec, 2))
2458 return fold_build3 (TREE_CODE (chrec),
2459 TREE_TYPE (chrec), op0, op1, op2);
2462 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2463 and EVOLUTION_LOOP, that were left under a symbolic form.
2465 CHREC is an expression with 2 operands to be instantiated.
2467 CACHE is the cache of already instantiated values.
2469 FOLD_CONVERSIONS should be set to true when the conversions that
2470 may wrap in signed/pointer type are folded, as long as the value of
2471 the chrec is preserved.
2473 SIZE_EXPR is used for computing the size of the expression to be
2474 instantiated, and to stop if it exceeds some limit. */
2477 instantiate_scev_2 (basic_block instantiate_below,
2478 struct loop *evolution_loop, tree chrec,
2479 bool fold_conversions, htab_t cache, int size_expr)
2482 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2483 TREE_OPERAND (chrec, 0),
2484 fold_conversions, cache, size_expr);
2485 if (op0 == chrec_dont_know)
2486 return chrec_dont_know;
2488 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2489 TREE_OPERAND (chrec, 1),
2490 fold_conversions, cache, size_expr);
2491 if (op1 == chrec_dont_know)
2492 return chrec_dont_know;
2494 if (op0 == TREE_OPERAND (chrec, 0)
2495 && op1 == TREE_OPERAND (chrec, 1))
2498 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2501 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2502 and EVOLUTION_LOOP, that were left under a symbolic form.
2504 CHREC is an expression with 2 operands to be instantiated.
2506 CACHE is the cache of already instantiated values.
2508 FOLD_CONVERSIONS should be set to true when the conversions that
2509 may wrap in signed/pointer type are folded, as long as the value of
2510 the chrec is preserved.
2512 SIZE_EXPR is used for computing the size of the expression to be
2513 instantiated, and to stop if it exceeds some limit. */
2516 instantiate_scev_1 (basic_block instantiate_below,
2517 struct loop *evolution_loop, tree chrec,
2518 bool fold_conversions, htab_t cache, int size_expr)
2520 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2521 TREE_OPERAND (chrec, 0),
2522 fold_conversions, cache, size_expr);
2524 if (op0 == chrec_dont_know)
2525 return chrec_dont_know;
2527 if (op0 == TREE_OPERAND (chrec, 0))
2530 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2533 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2534 and EVOLUTION_LOOP, that were left under a symbolic form.
2536 CHREC is the scalar evolution to instantiate.
2538 CACHE is the cache of already instantiated values.
2540 FOLD_CONVERSIONS should be set to true when the conversions that
2541 may wrap in signed/pointer type are folded, as long as the value of
2542 the chrec is preserved.
2544 SIZE_EXPR is used for computing the size of the expression to be
2545 instantiated, and to stop if it exceeds some limit. */
2548 instantiate_scev_r (basic_block instantiate_below,
2549 struct loop *evolution_loop, tree chrec,
2550 bool fold_conversions, htab_t cache, int size_expr)
2552 /* Give up if the expression is larger than the MAX that we allow. */
2553 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2554 return chrec_dont_know;
2556 if (automatically_generated_chrec_p (chrec)
2557 || is_gimple_min_invariant (chrec))
2560 switch (TREE_CODE (chrec))
2563 return instantiate_scev_name (instantiate_below, evolution_loop, chrec,
2564 fold_conversions, cache, size_expr);
2566 case POLYNOMIAL_CHREC:
2567 return instantiate_scev_poly (instantiate_below, evolution_loop, chrec,
2568 fold_conversions, cache, size_expr);
2570 case POINTER_PLUS_EXPR:
2574 return instantiate_scev_binary (instantiate_below, evolution_loop, chrec,
2575 TREE_CODE (chrec), chrec_type (chrec),
2576 TREE_OPERAND (chrec, 0),
2577 TREE_OPERAND (chrec, 1),
2578 fold_conversions, cache, size_expr);
2581 return instantiate_scev_convert (instantiate_below, evolution_loop, chrec,
2582 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2583 fold_conversions, cache, size_expr);
2587 return instantiate_scev_not (instantiate_below, evolution_loop, chrec,
2588 TREE_CODE (chrec), TREE_TYPE (chrec),
2589 TREE_OPERAND (chrec, 0),
2590 fold_conversions, cache, size_expr);
2592 case SCEV_NOT_KNOWN:
2593 return chrec_dont_know;
2602 if (VL_EXP_CLASS_P (chrec))
2603 return chrec_dont_know;
2605 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2608 return instantiate_scev_3 (instantiate_below, evolution_loop, chrec,
2609 fold_conversions, cache, size_expr);
2612 return instantiate_scev_2 (instantiate_below, evolution_loop, chrec,
2613 fold_conversions, cache, size_expr);
2616 return instantiate_scev_1 (instantiate_below, evolution_loop, chrec,
2617 fold_conversions, cache, size_expr);
2626 /* Too complicated to handle. */
2627 return chrec_dont_know;
2630 /* Analyze all the parameters of the chrec that were left under a
2631 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2632 recursive instantiation of parameters: a parameter is a variable
2633 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2634 a function parameter. */
2637 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2641 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2643 if (dump_file && (dump_flags & TDF_DETAILS))
2645 fprintf (dump_file, "(instantiate_scev \n");
2646 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2647 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2648 fprintf (dump_file, " (chrec = ");
2649 print_generic_expr (dump_file, chrec, 0);
2650 fprintf (dump_file, ")\n");
2653 res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false,
2656 if (dump_file && (dump_flags & TDF_DETAILS))
2658 fprintf (dump_file, " (res = ");
2659 print_generic_expr (dump_file, res, 0);
2660 fprintf (dump_file, "))\n");
2663 htab_delete (cache);
2668 /* Similar to instantiate_parameters, but does not introduce the
2669 evolutions in outer loops for LOOP invariants in CHREC, and does not
2670 care about causing overflows, as long as they do not affect value
2671 of an expression. */
2674 resolve_mixers (struct loop *loop, tree chrec)
2676 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2677 tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true,
2679 htab_delete (cache);
2683 /* Entry point for the analysis of the number of iterations pass.
2684 This function tries to safely approximate the number of iterations
2685 the loop will run. When this property is not decidable at compile
2686 time, the result is chrec_dont_know. Otherwise the result is
2687 a scalar or a symbolic parameter.
2689 Example of analysis: suppose that the loop has an exit condition:
2691 "if (b > 49) goto end_loop;"
2693 and that in a previous analysis we have determined that the
2694 variable 'b' has an evolution function:
2696 "EF = {23, +, 5}_2".
2698 When we evaluate the function at the point 5, i.e. the value of the
2699 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2700 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2701 the loop body has been executed 6 times. */
2704 number_of_latch_executions (struct loop *loop)
2708 struct tree_niter_desc niter_desc;
2710 /* Determine whether the number_of_iterations_in_loop has already
2712 res = loop->nb_iterations;
2715 res = chrec_dont_know;
2717 if (dump_file && (dump_flags & TDF_DETAILS))
2718 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2720 exit = single_exit (loop);
2724 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2727 type = TREE_TYPE (niter_desc.niter);
2728 if (integer_nonzerop (niter_desc.may_be_zero))
2729 res = build_int_cst (type, 0);
2730 else if (integer_zerop (niter_desc.may_be_zero))
2731 res = niter_desc.niter;
2733 res = chrec_dont_know;
2736 return set_nb_iterations_in_loop (loop, res);
2739 /* Returns the number of executions of the exit condition of LOOP,
2740 i.e., the number by one higher than number_of_latch_executions.
2741 Note that unlike number_of_latch_executions, this number does
2742 not necessarily fit in the unsigned variant of the type of
2743 the control variable -- if the number of iterations is a constant,
2744 we return chrec_dont_know if adding one to number_of_latch_executions
2745 overflows; however, in case the number of iterations is symbolic
2746 expression, the caller is responsible for dealing with this
2747 the possible overflow. */
2750 number_of_exit_cond_executions (struct loop *loop)
2752 tree ret = number_of_latch_executions (loop);
2753 tree type = chrec_type (ret);
2755 if (chrec_contains_undetermined (ret))
2758 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2759 if (TREE_CODE (ret) == INTEGER_CST
2760 && TREE_OVERFLOW (ret))
2761 return chrec_dont_know;
2766 /* One of the drivers for testing the scalar evolutions analysis.
2767 This function computes the number of iterations for all the loops
2768 from the EXIT_CONDITIONS array. */
2771 number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions)
2774 unsigned nb_chrec_dont_know_loops = 0;
2775 unsigned nb_static_loops = 0;
2778 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
2780 tree res = number_of_latch_executions (loop_containing_stmt (cond));
2781 if (chrec_contains_undetermined (res))
2782 nb_chrec_dont_know_loops++;
2789 fprintf (dump_file, "\n(\n");
2790 fprintf (dump_file, "-----------------------------------------\n");
2791 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2792 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2793 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2794 fprintf (dump_file, "-----------------------------------------\n");
2795 fprintf (dump_file, ")\n\n");
2797 print_loops (dump_file, 3);
2803 /* Counters for the stats. */
2809 unsigned nb_affine_multivar;
2810 unsigned nb_higher_poly;
2811 unsigned nb_chrec_dont_know;
2812 unsigned nb_undetermined;
2815 /* Reset the counters. */
2818 reset_chrecs_counters (struct chrec_stats *stats)
2820 stats->nb_chrecs = 0;
2821 stats->nb_affine = 0;
2822 stats->nb_affine_multivar = 0;
2823 stats->nb_higher_poly = 0;
2824 stats->nb_chrec_dont_know = 0;
2825 stats->nb_undetermined = 0;
2828 /* Dump the contents of a CHREC_STATS structure. */
2831 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2833 fprintf (file, "\n(\n");
2834 fprintf (file, "-----------------------------------------\n");
2835 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2836 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2837 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2838 stats->nb_higher_poly);
2839 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2840 fprintf (file, "-----------------------------------------\n");
2841 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2842 fprintf (file, "%d\twith undetermined coefficients\n",
2843 stats->nb_undetermined);
2844 fprintf (file, "-----------------------------------------\n");
2845 fprintf (file, "%d\tchrecs in the scev database\n",
2846 (int) htab_elements (scalar_evolution_info));
2847 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2848 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2849 fprintf (file, "-----------------------------------------\n");
2850 fprintf (file, ")\n\n");
2853 /* Gather statistics about CHREC. */
2856 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2858 if (dump_file && (dump_flags & TDF_STATS))
2860 fprintf (dump_file, "(classify_chrec ");
2861 print_generic_expr (dump_file, chrec, 0);
2862 fprintf (dump_file, "\n");
2867 if (chrec == NULL_TREE)
2869 stats->nb_undetermined++;
2873 switch (TREE_CODE (chrec))
2875 case POLYNOMIAL_CHREC:
2876 if (evolution_function_is_affine_p (chrec))
2878 if (dump_file && (dump_flags & TDF_STATS))
2879 fprintf (dump_file, " affine_univariate\n");
2882 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2884 if (dump_file && (dump_flags & TDF_STATS))
2885 fprintf (dump_file, " affine_multivariate\n");
2886 stats->nb_affine_multivar++;
2890 if (dump_file && (dump_flags & TDF_STATS))
2891 fprintf (dump_file, " higher_degree_polynomial\n");
2892 stats->nb_higher_poly++;
2901 if (chrec_contains_undetermined (chrec))
2903 if (dump_file && (dump_flags & TDF_STATS))
2904 fprintf (dump_file, " undetermined\n");
2905 stats->nb_undetermined++;
2908 if (dump_file && (dump_flags & TDF_STATS))
2909 fprintf (dump_file, ")\n");
2912 /* One of the drivers for testing the scalar evolutions analysis.
2913 This function analyzes the scalar evolution of all the scalars
2914 defined as loop phi nodes in one of the loops from the
2915 EXIT_CONDITIONS array.
2917 TODO Optimization: A loop is in canonical form if it contains only
2918 a single scalar loop phi node. All the other scalars that have an
2919 evolution in the loop are rewritten in function of this single
2920 index. This allows the parallelization of the loop. */
2923 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions)
2926 struct chrec_stats stats;
2928 gimple_stmt_iterator psi;
2930 reset_chrecs_counters (&stats);
2932 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
2938 loop = loop_containing_stmt (cond);
2941 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2943 phi = gsi_stmt (psi);
2944 if (is_gimple_reg (PHI_RESULT (phi)))
2946 chrec = instantiate_parameters
2948 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2950 if (dump_file && (dump_flags & TDF_STATS))
2951 gather_chrec_stats (chrec, &stats);
2956 if (dump_file && (dump_flags & TDF_STATS))
2957 dump_chrecs_stats (dump_file, &stats);
2960 /* Callback for htab_traverse, gathers information on chrecs in the
2964 gather_stats_on_scev_database_1 (void **slot, void *stats)
2966 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2968 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2973 /* Classify the chrecs of the whole database. */
2976 gather_stats_on_scev_database (void)
2978 struct chrec_stats stats;
2983 reset_chrecs_counters (&stats);
2985 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2988 dump_chrecs_stats (dump_file, &stats);
2996 initialize_scalar_evolutions_analyzer (void)
2998 /* The elements below are unique. */
2999 if (chrec_dont_know == NULL_TREE)
3001 chrec_not_analyzed_yet = NULL_TREE;
3002 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3003 chrec_known = make_node (SCEV_KNOWN);
3004 TREE_TYPE (chrec_dont_know) = void_type_node;
3005 TREE_TYPE (chrec_known) = void_type_node;
3009 /* Initialize the analysis of scalar evolutions for LOOPS. */
3012 scev_initialize (void)
3017 scalar_evolution_info = htab_create_alloc (100,
3024 initialize_scalar_evolutions_analyzer ();
3026 FOR_EACH_LOOP (li, loop, 0)
3028 loop->nb_iterations = NULL_TREE;
3032 /* Cleans up the information cached by the scalar evolutions analysis
3033 in the hash table. */
3036 scev_reset_htab (void)
3038 if (!scalar_evolution_info)
3041 htab_empty (scalar_evolution_info);
3044 /* Cleans up the information cached by the scalar evolutions analysis
3045 in the hash table and in the loop->nb_iterations. */
3058 FOR_EACH_LOOP (li, loop, 0)
3060 loop->nb_iterations = NULL_TREE;
3064 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3065 respect to WRTO_LOOP and returns its base and step in IV if possible
3066 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3067 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3068 invariant in LOOP. Otherwise we require it to be an integer constant.
3070 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3071 because it is computed in signed arithmetics). Consequently, adding an
3074 for (i = IV->base; ; i += IV->step)
3076 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3077 false for the type of the induction variable, or you can prove that i does
3078 not wrap by some other argument. Otherwise, this might introduce undefined
3081 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3083 must be used instead. */
3086 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3087 affine_iv *iv, bool allow_nonconstant_step)
3092 iv->base = NULL_TREE;
3093 iv->step = NULL_TREE;
3094 iv->no_overflow = false;
3096 type = TREE_TYPE (op);
3097 if (TREE_CODE (type) != INTEGER_TYPE
3098 && TREE_CODE (type) != POINTER_TYPE)
3101 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3103 if (chrec_contains_undetermined (ev)
3104 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3107 if (tree_does_not_contain_chrecs (ev))
3110 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3111 iv->no_overflow = true;
3115 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3116 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3119 iv->step = CHREC_RIGHT (ev);
3120 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3121 || tree_contains_chrecs (iv->step, NULL))
3124 iv->base = CHREC_LEFT (ev);
3125 if (tree_contains_chrecs (iv->base, NULL))
3128 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
3133 /* Runs the analysis of scalar evolutions. */
3136 scev_analysis (void)
3138 VEC(gimple,heap) *exit_conditions;
3140 exit_conditions = VEC_alloc (gimple, heap, 37);
3141 select_loops_exit_conditions (&exit_conditions);
3143 if (dump_file && (dump_flags & TDF_STATS))
3144 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
3146 number_of_iterations_for_all_loops (&exit_conditions);
3147 VEC_free (gimple, heap, exit_conditions);
3150 /* Finalize the scalar evolution analysis. */
3153 scev_finalize (void)
3155 if (!scalar_evolution_info)
3157 htab_delete (scalar_evolution_info);
3158 scalar_evolution_info = NULL;
3161 /* Returns true if the expression EXPR is considered to be too expensive
3162 for scev_const_prop. */
3165 expression_expensive_p (tree expr)
3167 enum tree_code code;
3169 if (is_gimple_val (expr))
3172 code = TREE_CODE (expr);
3173 if (code == TRUNC_DIV_EXPR
3174 || code == CEIL_DIV_EXPR
3175 || code == FLOOR_DIV_EXPR
3176 || code == ROUND_DIV_EXPR
3177 || code == TRUNC_MOD_EXPR
3178 || code == CEIL_MOD_EXPR
3179 || code == FLOOR_MOD_EXPR
3180 || code == ROUND_MOD_EXPR
3181 || code == EXACT_DIV_EXPR)
3183 /* Division by power of two is usually cheap, so we allow it.
3184 Forbid anything else. */
3185 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3189 switch (TREE_CODE_CLASS (code))
3192 case tcc_comparison:
3193 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3198 return expression_expensive_p (TREE_OPERAND (expr, 0));
3205 /* Replace ssa names for that scev can prove they are constant by the
3206 appropriate constants. Also perform final value replacement in loops,
3207 in case the replacement expressions are cheap.
3209 We only consider SSA names defined by phi nodes; rest is left to the
3210 ordinary constant propagation pass. */
3213 scev_const_prop (void)
3216 tree name, type, ev;
3218 struct loop *loop, *ex_loop;
3219 bitmap ssa_names_to_remove = NULL;
3222 gimple_stmt_iterator psi;
3224 if (number_of_loops () <= 1)
3229 loop = bb->loop_father;
3231 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3233 phi = gsi_stmt (psi);
3234 name = PHI_RESULT (phi);
3236 if (!is_gimple_reg (name))
3239 type = TREE_TYPE (name);
3241 if (!POINTER_TYPE_P (type)
3242 && !INTEGRAL_TYPE_P (type))
3245 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3246 if (!is_gimple_min_invariant (ev)
3247 || !may_propagate_copy (name, ev))
3250 /* Replace the uses of the name. */
3252 replace_uses_by (name, ev);
3254 if (!ssa_names_to_remove)
3255 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3256 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3260 /* Remove the ssa names that were replaced by constants. We do not
3261 remove them directly in the previous cycle, since this
3262 invalidates scev cache. */
3263 if (ssa_names_to_remove)
3267 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3269 gimple_stmt_iterator psi;
3270 name = ssa_name (i);
3271 phi = SSA_NAME_DEF_STMT (name);
3273 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3274 psi = gsi_for_stmt (phi);
3275 remove_phi_node (&psi, true);
3278 BITMAP_FREE (ssa_names_to_remove);
3282 /* Now the regular final value replacement. */
3283 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
3286 tree def, rslt, niter;
3287 gimple_stmt_iterator bsi;
3289 /* If we do not know exact number of iterations of the loop, we cannot
3290 replace the final value. */
3291 exit = single_exit (loop);
3295 niter = number_of_latch_executions (loop);
3296 if (niter == chrec_dont_know)
3299 /* Ensure that it is possible to insert new statements somewhere. */
3300 if (!single_pred_p (exit->dest))
3301 split_loop_exit_edge (exit);
3302 bsi = gsi_after_labels (exit->dest);
3304 ex_loop = superloop_at_depth (loop,
3305 loop_depth (exit->dest->loop_father) + 1);
3307 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3309 phi = gsi_stmt (psi);
3310 rslt = PHI_RESULT (phi);
3311 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3312 if (!is_gimple_reg (def))
3318 if (!POINTER_TYPE_P (TREE_TYPE (def))
3319 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3325 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
3326 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3327 if (!tree_does_not_contain_chrecs (def)
3328 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3329 /* Moving the computation from the loop may prolong life range
3330 of some ssa names, which may cause problems if they appear
3331 on abnormal edges. */
3332 || contains_abnormal_ssa_name_p (def)
3333 /* Do not emit expensive expressions. The rationale is that
3334 when someone writes a code like
3336 while (n > 45) n -= 45;
3338 he probably knows that n is not large, and does not want it
3339 to be turned into n %= 45. */
3340 || expression_expensive_p (def))
3346 /* Eliminate the PHI node and replace it by a computation outside
3348 def = unshare_expr (def);
3349 remove_phi_node (&psi, false);
3351 def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
3352 true, GSI_SAME_STMT);
3353 ass = gimple_build_assign (rslt, def);
3354 gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
3360 #include "gt-tree-scalar-evolution.h"