1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 This pass analyzes the evolution of scalar variables in loop
25 structures. The algorithm is based on the SSA representation,
26 and on the loop hierarchy tree. This algorithm is not based on
27 the notion of versions of a variable, as it was the case for the
28 previous implementations of the scalar evolution algorithm, but
29 it assumes that each defined name is unique.
31 The notation used in this file is called "chains of recurrences",
32 and has been proposed by Eugene Zima, Robert Van Engelen, and
33 others for describing induction variables in programs. For example
34 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35 when entering in the loop_1 and has a step 2 in this loop, in other
36 words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37 this chain of recurrence (or chrec [shrek]) can contain the name of
38 other variables, in which case they are called parametric chrecs.
39 For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40 is the value of "a". In most of the cases these parametric chrecs
41 are fully instantiated before their use because symbolic names can
42 hide some difficult cases such as self-references described later
43 (see the Fibonacci example).
45 A short sketch of the algorithm is:
47 Given a scalar variable to be analyzed, follow the SSA edge to
50 - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
51 (RHS) of the definition cannot be statically analyzed, the answer
52 of the analyzer is: "don't know".
53 Otherwise, for all the variables that are not yet analyzed in the
54 RHS, try to determine their evolution, and finally try to
55 evaluate the operation of the RHS that gives the evolution
56 function of the analyzed variable.
58 - When the definition is a condition-phi-node: determine the
59 evolution function for all the branches of the phi node, and
60 finally merge these evolutions (see chrec_merge).
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
64 keep it symbolic. Then determine the SSA edges that are defined
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
68 this definition under a symbolic form. If the reached
69 loop-phi-node is the same as the starting one, then we compute a
70 symbolic stride on the return path. The result is then the
71 symbolic chrec {initial_condition, +, symbolic_stride}_loop.
75 Example 1: Illustration of the basic algorithm.
81 | if (c > 10) exit_loop
84 Suppose that we want to know the number of iterations of the
85 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86 ask the scalar evolution analyzer two questions: what's the
87 scalar evolution (scev) of "c", and what's the scev of "10". For
88 "10" the answer is "10" since it is a scalar constant. For the
89 scalar variable "c", it follows the SSA edge to its definition,
90 "c = b + 1", and then asks again what's the scev of "b".
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
93 is "c". The initial condition is kept under a symbolic form (it
94 may be the case that the copy constant propagation has done its
95 work and we end with the constant "3" as one of the edges of the
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
98 -> b. At this point we have drawn a path from "b" to "b" from
99 which we compute the stride in the loop: in this example it is
100 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101 that the scev for "b" is known, it is possible to compute the
102 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103 determine the number of iterations in the loop_1, we have to
104 instantiate_parameters ({a + 1, +, 1}_1), that gives after some
105 more analysis the scev {4, +, 1}_1, or in other words, this is
106 the function "f (x) = x + 4", where x is the iteration count of
107 the loop_1. Now we have to solve the inequality "x + 4 > 10",
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
111 created a variable that is implicitly defined, "x" or just "_1",
112 and all the other analyzed scalars of the loop are defined in
113 function of this variable:
119 or in terms of a C program:
122 | for (x = 0; x <= 7; x++)
128 Example 2: Illustration of the algorithm on nested loops.
139 For analyzing the scalar evolution of "a", the algorithm follows
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
146 Following the SSA edge for the initial condition, we end on "c = a
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
151 in the loop_1. That means that the overall stride in loop_1 is
152 equal to "+32", and the result is:
157 Example 3: Higher degree polynomials.
171 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
172 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
174 Example 4: Lucas, Fibonacci, or mixers in general.
186 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
187 following semantics: during the first iteration of the loop_1, the
188 variable contains the value 1, and then it contains the value "c".
189 Note that this syntax is close to the syntax of the loop-phi-node:
190 "a -> (1, c)_1" vs. "a = phi (1, c)".
192 The symbolic chrec representation contains all the semantics of the
193 original code. What is more difficult is to use this information.
195 Example 5: Flip-flops, or exchangers.
207 Based on these symbolic chrecs, it is possible to refine this
208 information into the more precise PERIODIC_CHRECs:
213 This transformation is not yet implemented.
217 You can find a more detailed description of the algorithm in:
218 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
220 this is a preliminary report and some of the details of the
221 algorithm have changed. I'm working on a research report that
222 updates the description of the algorithms to reflect the design
223 choices used in this implementation.
225 A set of slides show a high level overview of the algorithm and run
226 an example through the scalar evolution analyzer:
227 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
229 The slides that I have presented at the GCC Summit'04 are available
230 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
235 #include "coretypes.h"
241 /* These RTL headers are needed for basic-block.h. */
243 #include "basic-block.h"
244 #include "diagnostic.h"
245 #include "tree-flow.h"
246 #include "tree-dump.h"
249 #include "tree-chrec.h"
250 #include "tree-scalar-evolution.h"
251 #include "tree-pass.h"
255 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257 /* The cached information about a ssa name VAR, claiming that inside LOOP,
258 the value of VAR can be expressed as CHREC. */
260 struct scev_info_str GTY(())
266 /* Counters for the scev database. */
267 static unsigned nb_set_scev = 0;
268 static unsigned nb_get_scev = 0;
270 /* The following trees are unique elements. Thus the comparison of
271 another element to these elements should be done on the pointer to
272 these trees, and not on their value. */
274 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
275 tree chrec_not_analyzed_yet;
277 /* Reserved to the cases where the analyzer has detected an
278 undecidable property at compile time. */
279 tree chrec_dont_know;
281 /* When the analyzer has detected that a property will never
282 happen, then it qualifies it with chrec_known. */
285 static bitmap already_instantiated;
287 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
290 /* Constructs a new SCEV_INFO_STR structure. */
292 static inline struct scev_info_str *
293 new_scev_info_str (tree var)
295 struct scev_info_str *res;
297 res = GGC_NEW (struct scev_info_str);
299 res->chrec = chrec_not_analyzed_yet;
304 /* Computes a hash function for database element ELT. */
307 hash_scev_info (const void *elt)
309 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
312 /* Compares database elements E1 and E2. */
315 eq_scev_info (const void *e1, const void *e2)
317 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
318 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
320 return elt1->var == elt2->var;
323 /* Deletes database element E. */
326 del_scev_info (void *e)
331 /* Get the index corresponding to VAR in the current LOOP. If
332 it's the first time we ask for this VAR, then we return
333 chrec_not_analyzed_yet for this VAR and return its index. */
336 find_var_scev_info (tree var)
338 struct scev_info_str *res;
339 struct scev_info_str tmp;
343 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
346 *slot = new_scev_info_str (var);
347 res = (struct scev_info_str *) *slot;
352 /* Return true when CHREC contains symbolic names defined in
356 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
360 if (chrec == NULL_TREE)
363 if (TREE_INVARIANT (chrec))
366 if (TREE_CODE (chrec) == VAR_DECL
367 || TREE_CODE (chrec) == PARM_DECL
368 || TREE_CODE (chrec) == FUNCTION_DECL
369 || TREE_CODE (chrec) == LABEL_DECL
370 || TREE_CODE (chrec) == RESULT_DECL
371 || TREE_CODE (chrec) == FIELD_DECL)
374 if (TREE_CODE (chrec) == SSA_NAME)
376 tree def = SSA_NAME_DEF_STMT (chrec);
377 struct loop *def_loop = loop_containing_stmt (def);
378 struct loop *loop = get_loop (loop_nb);
380 if (def_loop == NULL)
383 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
389 n = TREE_OPERAND_LENGTH (chrec);
390 for (i = 0; i < n; i++)
391 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
397 /* Return true when PHI is a loop-phi-node. */
400 loop_phi_node_p (tree phi)
402 /* The implementation of this function is based on the following
403 property: "all the loop-phi-nodes of a loop are contained in the
404 loop's header basic block". */
406 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
409 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
410 In general, in the case of multivariate evolutions we want to get
411 the evolution in different loops. LOOP specifies the level for
412 which to get the evolution.
416 | for (j = 0; j < 100; j++)
418 | for (k = 0; k < 100; k++)
420 | i = k + j; - Here the value of i is a function of j, k.
422 | ... = i - Here the value of i is a function of j.
424 | ... = i - Here the value of i is a scalar.
430 | i_1 = phi (i_0, i_2)
434 This loop has the same effect as:
435 LOOP_1 has the same effect as:
439 The overall effect of the loop, "i_0 + 20" in the previous example,
440 is obtained by passing in the parameters: LOOP = 1,
441 EVOLUTION_FN = {i_0, +, 2}_1.
445 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
449 if (evolution_fn == chrec_dont_know)
450 return chrec_dont_know;
452 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
454 struct loop *inner_loop = get_chrec_loop (evolution_fn);
456 if (inner_loop == loop
457 || flow_loop_nested_p (loop, inner_loop))
459 tree nb_iter = number_of_latch_executions (inner_loop);
461 if (nb_iter == chrec_dont_know)
462 return chrec_dont_know;
467 /* evolution_fn is the evolution function in LOOP. Get
468 its value in the nb_iter-th iteration. */
469 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
471 /* Continue the computation until ending on a parent of LOOP. */
472 return compute_overall_effect_of_inner_loop (loop, res);
479 /* If the evolution function is an invariant, there is nothing to do. */
480 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
484 return chrec_dont_know;
487 /* Determine whether the CHREC is always positive/negative. If the expression
488 cannot be statically analyzed, return false, otherwise set the answer into
492 chrec_is_positive (tree chrec, bool *value)
494 bool value0, value1, value2;
495 tree end_value, nb_iter;
497 switch (TREE_CODE (chrec))
499 case POLYNOMIAL_CHREC:
500 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
501 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
504 /* FIXME -- overflows. */
505 if (value0 == value1)
511 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
512 and the proof consists in showing that the sign never
513 changes during the execution of the loop, from 0 to
514 loop->nb_iterations. */
515 if (!evolution_function_is_affine_p (chrec))
518 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
519 if (chrec_contains_undetermined (nb_iter))
523 /* TODO -- If the test is after the exit, we may decrease the number of
524 iterations by one. */
526 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
529 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
531 if (!chrec_is_positive (end_value, &value2))
535 return value0 == value1;
538 *value = (tree_int_cst_sgn (chrec) == 1);
546 /* Associate CHREC to SCALAR. */
549 set_scalar_evolution (tree scalar, tree chrec)
553 if (TREE_CODE (scalar) != SSA_NAME)
556 scalar_info = find_var_scev_info (scalar);
560 if (dump_flags & TDF_DETAILS)
562 fprintf (dump_file, "(set_scalar_evolution \n");
563 fprintf (dump_file, " (scalar = ");
564 print_generic_expr (dump_file, scalar, 0);
565 fprintf (dump_file, ")\n (scalar_evolution = ");
566 print_generic_expr (dump_file, chrec, 0);
567 fprintf (dump_file, "))\n");
569 if (dump_flags & TDF_STATS)
573 *scalar_info = chrec;
576 /* Retrieve the chrec associated to SCALAR in the LOOP. */
579 get_scalar_evolution (tree scalar)
585 if (dump_flags & TDF_DETAILS)
587 fprintf (dump_file, "(get_scalar_evolution \n");
588 fprintf (dump_file, " (scalar = ");
589 print_generic_expr (dump_file, scalar, 0);
590 fprintf (dump_file, ")\n");
592 if (dump_flags & TDF_STATS)
596 switch (TREE_CODE (scalar))
599 res = *find_var_scev_info (scalar);
608 res = chrec_not_analyzed_yet;
612 if (dump_file && (dump_flags & TDF_DETAILS))
614 fprintf (dump_file, " (scalar_evolution = ");
615 print_generic_expr (dump_file, res, 0);
616 fprintf (dump_file, "))\n");
622 /* Helper function for add_to_evolution. Returns the evolution
623 function for an assignment of the form "a = b + c", where "a" and
624 "b" are on the strongly connected component. CHREC_BEFORE is the
625 information that we already have collected up to this point.
626 TO_ADD is the evolution of "c".
628 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
629 evolution the expression TO_ADD, otherwise construct an evolution
630 part for this loop. */
633 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
636 tree type, left, right;
637 struct loop *loop = get_loop (loop_nb), *chloop;
639 switch (TREE_CODE (chrec_before))
641 case POLYNOMIAL_CHREC:
642 chloop = get_chrec_loop (chrec_before);
644 || flow_loop_nested_p (chloop, loop))
648 type = chrec_type (chrec_before);
650 /* When there is no evolution part in this loop, build it. */
655 right = SCALAR_FLOAT_TYPE_P (type)
656 ? build_real (type, dconst0)
657 : build_int_cst (type, 0);
661 var = CHREC_VARIABLE (chrec_before);
662 left = CHREC_LEFT (chrec_before);
663 right = CHREC_RIGHT (chrec_before);
666 to_add = chrec_convert (type, to_add, at_stmt);
667 right = chrec_convert_rhs (type, right, at_stmt);
668 right = chrec_fold_plus (chrec_type (right), right, to_add);
669 return build_polynomial_chrec (var, left, right);
673 gcc_assert (flow_loop_nested_p (loop, chloop));
675 /* Search the evolution in LOOP_NB. */
676 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
678 right = CHREC_RIGHT (chrec_before);
679 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
680 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
685 /* These nodes do not depend on a loop. */
686 if (chrec_before == chrec_dont_know)
687 return chrec_dont_know;
690 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
691 return build_polynomial_chrec (loop_nb, left, right);
695 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
698 Description (provided for completeness, for those who read code in
699 a plane, and for my poor 62 bytes brain that would have forgotten
700 all this in the next two or three months):
702 The algorithm of translation of programs from the SSA representation
703 into the chrecs syntax is based on a pattern matching. After having
704 reconstructed the overall tree expression for a loop, there are only
705 two cases that can arise:
707 1. a = loop-phi (init, a + expr)
708 2. a = loop-phi (init, expr)
710 where EXPR is either a scalar constant with respect to the analyzed
711 loop (this is a degree 0 polynomial), or an expression containing
712 other loop-phi definitions (these are higher degree polynomials).
719 | a = phi (init, a + 5)
726 | a = phi (inita, 2 * b + 3)
727 | b = phi (initb, b + 1)
730 For the first case, the semantics of the SSA representation is:
732 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
734 that is, there is a loop index "x" that determines the scalar value
735 of the variable during the loop execution. During the first
736 iteration, the value is that of the initial condition INIT, while
737 during the subsequent iterations, it is the sum of the initial
738 condition with the sum of all the values of EXPR from the initial
739 iteration to the before last considered iteration.
741 For the second case, the semantics of the SSA program is:
743 | a (x) = init, if x = 0;
744 | expr (x - 1), otherwise.
746 The second case corresponds to the PEELED_CHREC, whose syntax is
747 close to the syntax of a loop-phi-node:
749 | phi (init, expr) vs. (init, expr)_x
751 The proof of the translation algorithm for the first case is a
752 proof by structural induction based on the degree of EXPR.
755 When EXPR is a constant with respect to the analyzed loop, or in
756 other words when EXPR is a polynomial of degree 0, the evolution of
757 the variable A in the loop is an affine function with an initial
758 condition INIT, and a step EXPR. In order to show this, we start
759 from the semantics of the SSA representation:
761 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
763 and since "expr (j)" is a constant with respect to "j",
765 f (x) = init + x * expr
767 Finally, based on the semantics of the pure sum chrecs, by
768 identification we get the corresponding chrecs syntax:
770 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
771 f (x) -> {init, +, expr}_x
774 Suppose that EXPR is a polynomial of degree N with respect to the
775 analyzed loop_x for which we have already determined that it is
776 written under the chrecs syntax:
778 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
780 We start from the semantics of the SSA program:
782 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
784 | f (x) = init + \sum_{j = 0}^{x - 1}
785 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
787 | f (x) = init + \sum_{j = 0}^{x - 1}
788 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
790 | f (x) = init + \sum_{k = 0}^{n - 1}
791 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
793 | f (x) = init + \sum_{k = 0}^{n - 1}
794 | (b_k * \binom{x}{k + 1})
796 | f (x) = init + b_0 * \binom{x}{1} + ...
797 | + b_{n-1} * \binom{x}{n}
799 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
800 | + b_{n-1} * \binom{x}{n}
803 And finally from the definition of the chrecs syntax, we identify:
804 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
806 This shows the mechanism that stands behind the add_to_evolution
807 function. An important point is that the use of symbolic
808 parameters avoids the need of an analysis schedule.
815 | a = phi (inita, a + 2 + b)
816 | b = phi (initb, b + 1)
819 When analyzing "a", the algorithm keeps "b" symbolically:
821 | a -> {inita, +, 2 + b}_1
823 Then, after instantiation, the analyzer ends on the evolution:
825 | a -> {inita, +, 2 + initb, +, 1}_1
830 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
831 tree to_add, tree at_stmt)
833 tree type = chrec_type (to_add);
834 tree res = NULL_TREE;
836 if (to_add == NULL_TREE)
839 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
840 instantiated at this point. */
841 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
842 /* This should not happen. */
843 return chrec_dont_know;
845 if (dump_file && (dump_flags & TDF_DETAILS))
847 fprintf (dump_file, "(add_to_evolution \n");
848 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
849 fprintf (dump_file, " (chrec_before = ");
850 print_generic_expr (dump_file, chrec_before, 0);
851 fprintf (dump_file, ")\n (to_add = ");
852 print_generic_expr (dump_file, to_add, 0);
853 fprintf (dump_file, ")\n");
856 if (code == MINUS_EXPR)
857 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
858 ? build_real (type, dconstm1)
859 : build_int_cst_type (type, -1));
861 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
863 if (dump_file && (dump_flags & TDF_DETAILS))
865 fprintf (dump_file, " (res = ");
866 print_generic_expr (dump_file, res, 0);
867 fprintf (dump_file, "))\n");
873 /* Helper function. */
876 set_nb_iterations_in_loop (struct loop *loop,
879 if (dump_file && (dump_flags & TDF_DETAILS))
881 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
882 print_generic_expr (dump_file, res, 0);
883 fprintf (dump_file, "))\n");
886 loop->nb_iterations = res;
892 /* This section selects the loops that will be good candidates for the
893 scalar evolution analysis. For the moment, greedily select all the
894 loop nests we could analyze. */
896 /* Return true when it is possible to analyze the condition expression
900 analyzable_condition (tree expr)
904 if (TREE_CODE (expr) != COND_EXPR)
907 condition = TREE_OPERAND (expr, 0);
909 switch (TREE_CODE (condition))
929 /* For a loop with a single exit edge, return the COND_EXPR that
930 guards the exit edge. If the expression is too difficult to
931 analyze, then give up. */
934 get_loop_exit_condition (struct loop *loop)
936 tree res = NULL_TREE;
937 edge exit_edge = single_exit (loop);
939 if (dump_file && (dump_flags & TDF_DETAILS))
940 fprintf (dump_file, "(get_loop_exit_condition \n ");
946 expr = last_stmt (exit_edge->src);
947 if (analyzable_condition (expr))
951 if (dump_file && (dump_flags & TDF_DETAILS))
953 print_generic_expr (dump_file, res, 0);
954 fprintf (dump_file, ")\n");
960 /* Recursively determine and enqueue the exit conditions for a loop. */
963 get_exit_conditions_rec (struct loop *loop,
964 VEC(tree,heap) **exit_conditions)
969 /* Recurse on the inner loops, then on the next (sibling) loops. */
970 get_exit_conditions_rec (loop->inner, exit_conditions);
971 get_exit_conditions_rec (loop->next, exit_conditions);
973 if (single_exit (loop))
975 tree loop_condition = get_loop_exit_condition (loop);
978 VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
982 /* Select the candidate loop nests for the analysis. This function
983 initializes the EXIT_CONDITIONS array. */
986 select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
988 struct loop *function_body = current_loops->tree_root;
990 get_exit_conditions_rec (function_body->inner, exit_conditions);
994 /* Depth first search algorithm. */
996 typedef enum t_bool {
1003 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1005 /* Follow the ssa edge into the right hand side RHS of an assignment.
1006 Return true if the strongly connected component has been found. */
1009 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1010 tree halting_phi, tree *evolution_of_loop, int limit)
1012 t_bool res = t_false;
1014 tree type_rhs = TREE_TYPE (rhs);
1016 enum tree_code code;
1018 /* The RHS is one of the following cases:
1022 - a POINTER_PLUS_EXPR,
1025 - other cases are not yet handled. */
1026 code = TREE_CODE (rhs);
1030 /* This assignment is under the form "a_1 = (cast) rhs. */
1031 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1032 halting_phi, evolution_of_loop, limit);
1033 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1034 *evolution_of_loop, at_stmt);
1038 /* This assignment is under the form "a_1 = 7". */
1043 /* This assignment is under the form: "a_1 = b_2". */
1044 res = follow_ssa_edge
1045 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1048 case POINTER_PLUS_EXPR:
1050 /* This case is under the form "rhs0 + rhs1". */
1051 rhs0 = TREE_OPERAND (rhs, 0);
1052 rhs1 = TREE_OPERAND (rhs, 1);
1053 STRIP_TYPE_NOPS (rhs0);
1054 STRIP_TYPE_NOPS (rhs1);
1056 if (TREE_CODE (rhs0) == SSA_NAME)
1058 if (TREE_CODE (rhs1) == SSA_NAME)
1060 /* Match an assignment under the form:
1063 /* We want only assignments of form "name + name" contribute to
1064 LIMIT, as the other cases do not necessarily contribute to
1065 the complexity of the expression. */
1068 evol = *evolution_of_loop;
1069 res = follow_ssa_edge
1070 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1074 *evolution_of_loop = add_to_evolution
1076 chrec_convert (type_rhs, evol, at_stmt),
1077 code, rhs1, at_stmt);
1079 else if (res == t_false)
1081 res = follow_ssa_edge
1082 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1083 evolution_of_loop, limit);
1086 *evolution_of_loop = add_to_evolution
1088 chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1089 code, rhs0, at_stmt);
1091 else if (res == t_dont_know)
1092 *evolution_of_loop = chrec_dont_know;
1095 else if (res == t_dont_know)
1096 *evolution_of_loop = chrec_dont_know;
1101 /* Match an assignment under the form:
1103 res = follow_ssa_edge
1104 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1105 evolution_of_loop, limit);
1107 *evolution_of_loop = add_to_evolution
1108 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1110 code, rhs1, at_stmt);
1112 else if (res == t_dont_know)
1113 *evolution_of_loop = chrec_dont_know;
1117 else if (TREE_CODE (rhs1) == SSA_NAME)
1119 /* Match an assignment under the form:
1121 res = follow_ssa_edge
1122 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1123 evolution_of_loop, limit);
1125 *evolution_of_loop = add_to_evolution
1126 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1128 code, rhs0, at_stmt);
1130 else if (res == t_dont_know)
1131 *evolution_of_loop = chrec_dont_know;
1135 /* Otherwise, match an assignment under the form:
1137 /* And there is nothing to do. */
1143 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1144 rhs0 = TREE_OPERAND (rhs, 0);
1145 rhs1 = TREE_OPERAND (rhs, 1);
1146 STRIP_TYPE_NOPS (rhs0);
1147 STRIP_TYPE_NOPS (rhs1);
1149 if (TREE_CODE (rhs0) == SSA_NAME)
1151 /* Match an assignment under the form:
1154 /* We want only assignments of form "name - name" contribute to
1155 LIMIT, as the other cases do not necessarily contribute to
1156 the complexity of the expression. */
1157 if (TREE_CODE (rhs1) == SSA_NAME)
1160 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1161 evolution_of_loop, limit);
1163 *evolution_of_loop = add_to_evolution
1164 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1165 MINUS_EXPR, rhs1, at_stmt);
1167 else if (res == t_dont_know)
1168 *evolution_of_loop = chrec_dont_know;
1171 /* Otherwise, match an assignment under the form:
1173 /* And there is nothing to do. */
1180 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1181 It must be handled as a copy assignment of the form a_1 = a_2. */
1182 tree op0 = ASSERT_EXPR_VAR (rhs);
1183 if (TREE_CODE (op0) == SSA_NAME)
1184 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1185 halting_phi, evolution_of_loop, limit);
1200 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1203 backedge_phi_arg_p (tree phi, int i)
1205 edge e = PHI_ARG_EDGE (phi, i);
1207 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1208 about updating it anywhere, and this should work as well most of the
1210 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1216 /* Helper function for one branch of the condition-phi-node. Return
1217 true if the strongly connected component has been found following
1220 static inline t_bool
1221 follow_ssa_edge_in_condition_phi_branch (int i,
1225 tree *evolution_of_branch,
1226 tree init_cond, int limit)
1228 tree branch = PHI_ARG_DEF (condition_phi, i);
1229 *evolution_of_branch = chrec_dont_know;
1231 /* Do not follow back edges (they must belong to an irreducible loop, which
1232 we really do not want to worry about). */
1233 if (backedge_phi_arg_p (condition_phi, i))
1236 if (TREE_CODE (branch) == SSA_NAME)
1238 *evolution_of_branch = init_cond;
1239 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1240 evolution_of_branch, limit);
1243 /* This case occurs when one of the condition branches sets
1244 the variable to a constant: i.e. a phi-node like
1245 "a_2 = PHI <a_7(5), 2(6)>;".
1247 FIXME: This case have to be refined correctly:
1248 in some cases it is possible to say something better than
1249 chrec_dont_know, for example using a wrap-around notation. */
1253 /* This function merges the branches of a condition-phi-node in a
1257 follow_ssa_edge_in_condition_phi (struct loop *loop,
1260 tree *evolution_of_loop, int limit)
1263 tree init = *evolution_of_loop;
1264 tree evolution_of_branch;
1265 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1267 &evolution_of_branch,
1269 if (res == t_false || res == t_dont_know)
1272 *evolution_of_loop = evolution_of_branch;
1274 /* If the phi node is just a copy, do not increase the limit. */
1275 if (PHI_NUM_ARGS (condition_phi) > 1)
1278 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1280 /* Quickly give up when the evolution of one of the branches is
1282 if (*evolution_of_loop == chrec_dont_know)
1285 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1287 &evolution_of_branch,
1289 if (res == t_false || res == t_dont_know)
1292 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1293 evolution_of_branch);
1299 /* Follow an SSA edge in an inner loop. It computes the overall
1300 effect of the loop, and following the symbolic initial conditions,
1301 it follows the edges in the parent loop. The inner loop is
1302 considered as a single statement. */
1305 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1308 tree *evolution_of_loop, int limit)
1310 struct loop *loop = loop_containing_stmt (loop_phi_node);
1311 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1313 /* Sometimes, the inner loop is too difficult to analyze, and the
1314 result of the analysis is a symbolic parameter. */
1315 if (ev == PHI_RESULT (loop_phi_node))
1317 t_bool res = t_false;
1320 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1322 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1325 /* Follow the edges that exit the inner loop. */
1326 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1327 if (!flow_bb_inside_loop_p (loop, bb))
1328 res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1330 evolution_of_loop, limit);
1335 /* If the path crosses this loop-phi, give up. */
1337 *evolution_of_loop = chrec_dont_know;
1342 /* Otherwise, compute the overall effect of the inner loop. */
1343 ev = compute_overall_effect_of_inner_loop (loop, ev);
1344 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1345 evolution_of_loop, limit);
1348 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1349 path that is analyzed on the return walk. */
1352 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1353 tree *evolution_of_loop, int limit)
1355 struct loop *def_loop;
1357 if (TREE_CODE (def) == NOP_EXPR)
1360 /* Give up if the path is longer than the MAX that we allow. */
1361 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1364 def_loop = loop_containing_stmt (def);
1366 switch (TREE_CODE (def))
1369 if (!loop_phi_node_p (def))
1370 /* DEF is a condition-phi-node. Follow the branches, and
1371 record their evolutions. Finally, merge the collected
1372 information and set the approximation to the main
1374 return follow_ssa_edge_in_condition_phi
1375 (loop, def, halting_phi, evolution_of_loop, limit);
1377 /* When the analyzed phi is the halting_phi, the
1378 depth-first search is over: we have found a path from
1379 the halting_phi to itself in the loop. */
1380 if (def == halting_phi)
1383 /* Otherwise, the evolution of the HALTING_PHI depends
1384 on the evolution of another loop-phi-node, i.e. the
1385 evolution function is a higher degree polynomial. */
1386 if (def_loop == loop)
1390 if (flow_loop_nested_p (loop, def_loop))
1391 return follow_ssa_edge_inner_loop_phi
1392 (loop, def, halting_phi, evolution_of_loop, limit + 1);
1397 case GIMPLE_MODIFY_STMT:
1398 return follow_ssa_edge_in_rhs (loop, def,
1399 GIMPLE_STMT_OPERAND (def, 1),
1401 evolution_of_loop, limit);
1404 /* At this level of abstraction, the program is just a set
1405 of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
1406 other node to be handled. */
1413 /* Given a LOOP_PHI_NODE, this function determines the evolution
1414 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1417 analyze_evolution_in_loop (tree loop_phi_node,
1421 tree evolution_function = chrec_not_analyzed_yet;
1422 struct loop *loop = loop_containing_stmt (loop_phi_node);
1425 if (dump_file && (dump_flags & TDF_DETAILS))
1427 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1428 fprintf (dump_file, " (loop_phi_node = ");
1429 print_generic_expr (dump_file, loop_phi_node, 0);
1430 fprintf (dump_file, ")\n");
1433 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1435 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1436 tree ssa_chain, ev_fn;
1439 /* Select the edges that enter the loop body. */
1440 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1441 if (!flow_bb_inside_loop_p (loop, bb))
1444 if (TREE_CODE (arg) == SSA_NAME)
1446 ssa_chain = SSA_NAME_DEF_STMT (arg);
1448 /* Pass in the initial condition to the follow edge function. */
1450 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1455 /* When it is impossible to go back on the same
1456 loop_phi_node by following the ssa edges, the
1457 evolution is represented by a peeled chrec, i.e. the
1458 first iteration, EV_FN has the value INIT_COND, then
1459 all the other iterations it has the value of ARG.
1460 For the moment, PEELED_CHREC nodes are not built. */
1462 ev_fn = chrec_dont_know;
1464 /* When there are multiple back edges of the loop (which in fact never
1465 happens currently, but nevertheless), merge their evolutions. */
1466 evolution_function = chrec_merge (evolution_function, ev_fn);
1469 if (dump_file && (dump_flags & TDF_DETAILS))
1471 fprintf (dump_file, " (evolution_function = ");
1472 print_generic_expr (dump_file, evolution_function, 0);
1473 fprintf (dump_file, "))\n");
1476 return evolution_function;
1479 /* Given a loop-phi-node, return the initial conditions of the
1480 variable on entry of the loop. When the CCP has propagated
1481 constants into the loop-phi-node, the initial condition is
1482 instantiated, otherwise the initial condition is kept symbolic.
1483 This analyzer does not analyze the evolution outside the current
1484 loop, and leaves this task to the on-demand tree reconstructor. */
1487 analyze_initial_condition (tree loop_phi_node)
1490 tree init_cond = chrec_not_analyzed_yet;
1491 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1495 fprintf (dump_file, "(analyze_initial_condition \n");
1496 fprintf (dump_file, " (loop_phi_node = \n");
1497 print_generic_expr (dump_file, loop_phi_node, 0);
1498 fprintf (dump_file, ")\n");
1501 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1503 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1504 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1506 /* When the branch is oriented to the loop's body, it does
1507 not contribute to the initial condition. */
1508 if (flow_bb_inside_loop_p (loop, bb))
1511 if (init_cond == chrec_not_analyzed_yet)
1517 if (TREE_CODE (branch) == SSA_NAME)
1519 init_cond = chrec_dont_know;
1523 init_cond = chrec_merge (init_cond, branch);
1526 /* Ooops -- a loop without an entry??? */
1527 if (init_cond == chrec_not_analyzed_yet)
1528 init_cond = chrec_dont_know;
1530 if (dump_file && (dump_flags & TDF_DETAILS))
1532 fprintf (dump_file, " (init_cond = ");
1533 print_generic_expr (dump_file, init_cond, 0);
1534 fprintf (dump_file, "))\n");
1540 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1543 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1546 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1549 if (phi_loop != loop)
1551 struct loop *subloop;
1552 tree evolution_fn = analyze_scalar_evolution
1553 (phi_loop, PHI_RESULT (loop_phi_node));
1555 /* Dive one level deeper. */
1556 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1558 /* Interpret the subloop. */
1559 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1563 /* Otherwise really interpret the loop phi. */
1564 init_cond = analyze_initial_condition (loop_phi_node);
1565 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1570 /* This function merges the branches of a condition-phi-node,
1571 contained in the outermost loop, and whose arguments are already
1575 interpret_condition_phi (struct loop *loop, tree condition_phi)
1578 tree res = chrec_not_analyzed_yet;
1580 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1584 if (backedge_phi_arg_p (condition_phi, i))
1586 res = chrec_dont_know;
1590 branch_chrec = analyze_scalar_evolution
1591 (loop, PHI_ARG_DEF (condition_phi, i));
1593 res = chrec_merge (res, branch_chrec);
1599 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
1600 analyze this node before, follow the definitions until ending
1601 either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
1602 return path, this function propagates evolutions (ala constant copy
1603 propagation). OPND1 is not a GIMPLE expression because we could
1604 analyze the effect of an inner loop: see interpret_loop_phi. */
1607 interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
1608 tree opnd1, tree type)
1610 tree res, opnd10, opnd11, chrec10, chrec11;
1612 if (is_gimple_min_invariant (opnd1))
1613 return chrec_convert (type, opnd1, at_stmt);
1615 switch (TREE_CODE (opnd1))
1617 case POINTER_PLUS_EXPR:
1618 opnd10 = TREE_OPERAND (opnd1, 0);
1619 opnd11 = TREE_OPERAND (opnd1, 1);
1620 chrec10 = analyze_scalar_evolution (loop, opnd10);
1621 chrec11 = analyze_scalar_evolution (loop, opnd11);
1622 chrec10 = chrec_convert (type, chrec10, at_stmt);
1623 chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
1624 res = chrec_fold_plus (type, chrec10, chrec11);
1628 opnd10 = TREE_OPERAND (opnd1, 0);
1629 opnd11 = TREE_OPERAND (opnd1, 1);
1630 chrec10 = analyze_scalar_evolution (loop, opnd10);
1631 chrec11 = analyze_scalar_evolution (loop, opnd11);
1632 chrec10 = chrec_convert (type, chrec10, at_stmt);
1633 chrec11 = chrec_convert (type, chrec11, at_stmt);
1634 res = chrec_fold_plus (type, chrec10, chrec11);
1638 opnd10 = TREE_OPERAND (opnd1, 0);
1639 opnd11 = TREE_OPERAND (opnd1, 1);
1640 chrec10 = analyze_scalar_evolution (loop, opnd10);
1641 chrec11 = analyze_scalar_evolution (loop, opnd11);
1642 chrec10 = chrec_convert (type, chrec10, at_stmt);
1643 chrec11 = chrec_convert (type, chrec11, at_stmt);
1644 res = chrec_fold_minus (type, chrec10, chrec11);
1648 opnd10 = TREE_OPERAND (opnd1, 0);
1649 chrec10 = analyze_scalar_evolution (loop, opnd10);
1650 chrec10 = chrec_convert (type, chrec10, at_stmt);
1651 /* TYPE may be integer, real or complex, so use fold_convert. */
1652 res = chrec_fold_multiply (type, chrec10,
1653 fold_convert (type, integer_minus_one_node));
1657 opnd10 = TREE_OPERAND (opnd1, 0);
1658 opnd11 = TREE_OPERAND (opnd1, 1);
1659 chrec10 = analyze_scalar_evolution (loop, opnd10);
1660 chrec11 = analyze_scalar_evolution (loop, opnd11);
1661 chrec10 = chrec_convert (type, chrec10, at_stmt);
1662 chrec11 = chrec_convert (type, chrec11, at_stmt);
1663 res = chrec_fold_multiply (type, chrec10, chrec11);
1667 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1672 opnd10 = ASSERT_EXPR_VAR (opnd1);
1673 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1679 opnd10 = TREE_OPERAND (opnd1, 0);
1680 chrec10 = analyze_scalar_evolution (loop, opnd10);
1681 res = chrec_convert (type, chrec10, at_stmt);
1685 res = chrec_dont_know;
1694 /* This section contains all the entry points:
1695 - number_of_iterations_in_loop,
1696 - analyze_scalar_evolution,
1697 - instantiate_parameters.
1700 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1701 common ancestor of DEF_LOOP and USE_LOOP. */
1704 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1705 struct loop *def_loop,
1709 if (def_loop == wrto_loop)
1712 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1713 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1715 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1718 /* Helper recursive function. */
1721 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1723 tree def, type = TREE_TYPE (var);
1725 struct loop *def_loop;
1727 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1728 return chrec_dont_know;
1730 if (TREE_CODE (var) != SSA_NAME)
1731 return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
1733 def = SSA_NAME_DEF_STMT (var);
1734 bb = bb_for_stmt (def);
1735 def_loop = bb ? bb->loop_father : NULL;
1738 || !flow_bb_inside_loop_p (loop, bb))
1740 /* Keep the symbolic form. */
1745 if (res != chrec_not_analyzed_yet)
1747 if (loop != bb->loop_father)
1748 res = compute_scalar_evolution_in_loop
1749 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1754 if (loop != def_loop)
1756 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1757 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1762 switch (TREE_CODE (def))
1764 case GIMPLE_MODIFY_STMT:
1765 res = interpret_rhs_modify_stmt (loop, def,
1766 GIMPLE_STMT_OPERAND (def, 1), type);
1770 if (loop_phi_node_p (def))
1771 res = interpret_loop_phi (loop, def);
1773 res = interpret_condition_phi (loop, def);
1777 res = chrec_dont_know;
1783 /* Keep the symbolic form. */
1784 if (res == chrec_dont_know)
1787 if (loop == def_loop)
1788 set_scalar_evolution (var, res);
1793 /* Entry point for the scalar evolution analyzer.
1794 Analyzes and returns the scalar evolution of the ssa_name VAR.
1795 LOOP_NB is the identifier number of the loop in which the variable
1798 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1799 pointer to the statement that uses this variable, in order to
1800 determine the evolution function of the variable, use the following
1803 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1804 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1805 tree chrec_instantiated = instantiate_parameters
1806 (loop_nb, chrec_with_symbols);
1810 analyze_scalar_evolution (struct loop *loop, tree var)
1814 if (dump_file && (dump_flags & TDF_DETAILS))
1816 fprintf (dump_file, "(analyze_scalar_evolution \n");
1817 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1818 fprintf (dump_file, " (scalar = ");
1819 print_generic_expr (dump_file, var, 0);
1820 fprintf (dump_file, ")\n");
1823 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1825 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1828 if (dump_file && (dump_flags & TDF_DETAILS))
1829 fprintf (dump_file, ")\n");
1834 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1835 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1838 FOLDED_CASTS is set to true if resolve_mixers used
1839 chrec_convert_aggressive (TODO -- not really, we are way too conservative
1840 at the moment in order to keep things simple). */
1843 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1844 tree version, bool *folded_casts)
1847 tree ev = version, tmp;
1850 *folded_casts = false;
1853 tmp = analyze_scalar_evolution (use_loop, ev);
1854 ev = resolve_mixers (use_loop, tmp);
1856 if (folded_casts && tmp != ev)
1857 *folded_casts = true;
1859 if (use_loop == wrto_loop)
1862 /* If the value of the use changes in the inner loop, we cannot express
1863 its value in the outer loop (we might try to return interval chrec,
1864 but we do not have a user for it anyway) */
1865 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1867 return chrec_dont_know;
1869 use_loop = loop_outer (use_loop);
1873 /* Returns instantiated value for VERSION in CACHE. */
1876 get_instantiated_value (htab_t cache, tree version)
1878 struct scev_info_str *info, pattern;
1880 pattern.var = version;
1881 info = (struct scev_info_str *) htab_find (cache, &pattern);
1889 /* Sets instantiated value for VERSION to VAL in CACHE. */
1892 set_instantiated_value (htab_t cache, tree version, tree val)
1894 struct scev_info_str *info, pattern;
1897 pattern.var = version;
1898 slot = htab_find_slot (cache, &pattern, INSERT);
1901 *slot = new_scev_info_str (version);
1902 info = (struct scev_info_str *) *slot;
1906 /* Return the closed_loop_phi node for VAR. If there is none, return
1910 loop_closed_phi_def (tree var)
1916 if (var == NULL_TREE
1917 || TREE_CODE (var) != SSA_NAME)
1920 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
1921 exit = single_exit (loop);
1925 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1926 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
1927 return PHI_RESULT (phi);
1932 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1933 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
1934 of already instantiated values. FLAGS modify the way chrecs are
1935 instantiated. SIZE_EXPR is used for computing the size of the expression to
1936 be instantiated, and to stop if it exceeds some limit. */
1938 /* Values for FLAGS. */
1941 INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs
1943 FOLD_CONVERSIONS = 2 /* The conversions that may wrap in
1944 signed/pointer type are folded, as long as the
1945 value of the chrec is preserved. */
1949 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
1952 tree res, op0, op1, op2;
1954 struct loop *def_loop;
1955 tree type = chrec_type (chrec);
1957 /* Give up if the expression is larger than the MAX that we allow. */
1958 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1959 return chrec_dont_know;
1961 if (automatically_generated_chrec_p (chrec)
1962 || is_gimple_min_invariant (chrec))
1965 switch (TREE_CODE (chrec))
1968 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1970 /* A parameter (or loop invariant and we do not want to include
1971 evolutions in outer loops), nothing to do. */
1973 || (!(flags & INSERT_SUPERLOOP_CHRECS)
1974 && !flow_bb_inside_loop_p (loop, def_bb)))
1977 /* We cache the value of instantiated variable to avoid exponential
1978 time complexity due to reevaluations. We also store the convenient
1979 value in the cache in order to prevent infinite recursion -- we do
1980 not want to instantiate the SSA_NAME if it is in a mixer
1981 structure. This is used for avoiding the instantiation of
1982 recursively defined functions, such as:
1984 | a_2 -> {0, +, 1, +, a_2}_1 */
1986 res = get_instantiated_value (cache, chrec);
1990 /* Store the convenient value for chrec in the structure. If it
1991 is defined outside of the loop, we may just leave it in symbolic
1992 form, otherwise we need to admit that we do not know its behavior
1994 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1995 set_instantiated_value (cache, chrec, res);
1997 /* To make things even more complicated, instantiate_parameters_1
1998 calls analyze_scalar_evolution that may call # of iterations
1999 analysis that may in turn call instantiate_parameters_1 again.
2000 To prevent the infinite recursion, keep also the bitmap of
2001 ssa names that are being instantiated globally. */
2002 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2005 def_loop = find_common_loop (loop, def_bb->loop_father);
2007 /* If the analysis yields a parametric chrec, instantiate the
2009 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2010 res = analyze_scalar_evolution (def_loop, chrec);
2012 /* Don't instantiate loop-closed-ssa phi nodes. */
2013 if (TREE_CODE (res) == SSA_NAME
2014 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2015 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2016 > loop_depth (def_loop))))
2019 res = loop_closed_phi_def (chrec);
2023 if (res == NULL_TREE)
2024 res = chrec_dont_know;
2027 else if (res != chrec_dont_know)
2028 res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2030 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2032 /* Store the correct value to the cache. */
2033 set_instantiated_value (cache, chrec, res);
2036 case POLYNOMIAL_CHREC:
2037 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2038 flags, cache, size_expr);
2039 if (op0 == chrec_dont_know)
2040 return chrec_dont_know;
2042 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2043 flags, cache, size_expr);
2044 if (op1 == chrec_dont_know)
2045 return chrec_dont_know;
2047 if (CHREC_LEFT (chrec) != op0
2048 || CHREC_RIGHT (chrec) != op1)
2050 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
2051 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2055 case POINTER_PLUS_EXPR:
2057 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2058 flags, cache, size_expr);
2059 if (op0 == chrec_dont_know)
2060 return chrec_dont_know;
2062 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2063 flags, cache, size_expr);
2064 if (op1 == chrec_dont_know)
2065 return chrec_dont_know;
2067 if (TREE_OPERAND (chrec, 0) != op0
2068 || TREE_OPERAND (chrec, 1) != op1)
2070 op0 = chrec_convert (type, op0, NULL_TREE);
2071 op1 = chrec_convert_rhs (type, op1, NULL_TREE);
2072 chrec = chrec_fold_plus (type, op0, op1);
2077 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2078 flags, cache, size_expr);
2079 if (op0 == chrec_dont_know)
2080 return chrec_dont_know;
2082 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2083 flags, cache, size_expr);
2084 if (op1 == chrec_dont_know)
2085 return chrec_dont_know;
2087 if (TREE_OPERAND (chrec, 0) != op0
2088 || TREE_OPERAND (chrec, 1) != op1)
2090 op0 = chrec_convert (type, op0, NULL_TREE);
2091 op1 = chrec_convert (type, op1, NULL_TREE);
2092 chrec = chrec_fold_minus (type, op0, op1);
2097 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2098 flags, cache, size_expr);
2099 if (op0 == chrec_dont_know)
2100 return chrec_dont_know;
2102 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2103 flags, cache, size_expr);
2104 if (op1 == chrec_dont_know)
2105 return chrec_dont_know;
2107 if (TREE_OPERAND (chrec, 0) != op0
2108 || TREE_OPERAND (chrec, 1) != op1)
2110 op0 = chrec_convert (type, op0, NULL_TREE);
2111 op1 = chrec_convert (type, op1, NULL_TREE);
2112 chrec = chrec_fold_multiply (type, op0, op1);
2118 case NON_LVALUE_EXPR:
2119 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2120 flags, cache, size_expr);
2121 if (op0 == chrec_dont_know)
2122 return chrec_dont_know;
2124 if (flags & FOLD_CONVERSIONS)
2126 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2131 if (op0 == TREE_OPERAND (chrec, 0))
2134 /* If we used chrec_convert_aggressive, we can no longer assume that
2135 signed chrecs do not overflow, as chrec_convert does, so avoid
2136 calling it in that case. */
2137 if (flags & FOLD_CONVERSIONS)
2138 return fold_convert (TREE_TYPE (chrec), op0);
2140 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2142 case SCEV_NOT_KNOWN:
2143 return chrec_dont_know;
2152 gcc_assert (!VL_EXP_CLASS_P (chrec));
2153 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2156 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2157 flags, cache, size_expr);
2158 if (op0 == chrec_dont_know)
2159 return chrec_dont_know;
2161 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2162 flags, cache, size_expr);
2163 if (op1 == chrec_dont_know)
2164 return chrec_dont_know;
2166 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2167 flags, cache, size_expr);
2168 if (op2 == chrec_dont_know)
2169 return chrec_dont_know;
2171 if (op0 == TREE_OPERAND (chrec, 0)
2172 && op1 == TREE_OPERAND (chrec, 1)
2173 && op2 == TREE_OPERAND (chrec, 2))
2176 return fold_build3 (TREE_CODE (chrec),
2177 TREE_TYPE (chrec), op0, op1, op2);
2180 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2181 flags, cache, size_expr);
2182 if (op0 == chrec_dont_know)
2183 return chrec_dont_know;
2185 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2186 flags, cache, size_expr);
2187 if (op1 == chrec_dont_know)
2188 return chrec_dont_know;
2190 if (op0 == TREE_OPERAND (chrec, 0)
2191 && op1 == TREE_OPERAND (chrec, 1))
2193 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2196 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2197 flags, cache, size_expr);
2198 if (op0 == chrec_dont_know)
2199 return chrec_dont_know;
2200 if (op0 == TREE_OPERAND (chrec, 0))
2202 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2211 /* Too complicated to handle. */
2212 return chrec_dont_know;
2215 /* Analyze all the parameters of the chrec that were left under a
2216 symbolic form. LOOP is the loop in which symbolic names have to
2217 be analyzed and instantiated. */
2220 instantiate_parameters (struct loop *loop,
2224 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2226 if (dump_file && (dump_flags & TDF_DETAILS))
2228 fprintf (dump_file, "(instantiate_parameters \n");
2229 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2230 fprintf (dump_file, " (chrec = ");
2231 print_generic_expr (dump_file, chrec, 0);
2232 fprintf (dump_file, ")\n");
2235 res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2238 if (dump_file && (dump_flags & TDF_DETAILS))
2240 fprintf (dump_file, " (res = ");
2241 print_generic_expr (dump_file, res, 0);
2242 fprintf (dump_file, "))\n");
2245 htab_delete (cache);
2250 /* Similar to instantiate_parameters, but does not introduce the
2251 evolutions in outer loops for LOOP invariants in CHREC, and does not
2252 care about causing overflows, as long as they do not affect value
2253 of an expression. */
2256 resolve_mixers (struct loop *loop, tree chrec)
2258 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2259 tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2260 htab_delete (cache);
2264 /* Entry point for the analysis of the number of iterations pass.
2265 This function tries to safely approximate the number of iterations
2266 the loop will run. When this property is not decidable at compile
2267 time, the result is chrec_dont_know. Otherwise the result is
2268 a scalar or a symbolic parameter.
2270 Example of analysis: suppose that the loop has an exit condition:
2272 "if (b > 49) goto end_loop;"
2274 and that in a previous analysis we have determined that the
2275 variable 'b' has an evolution function:
2277 "EF = {23, +, 5}_2".
2279 When we evaluate the function at the point 5, i.e. the value of the
2280 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2281 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2282 the loop body has been executed 6 times. */
2285 number_of_latch_executions (struct loop *loop)
2289 struct tree_niter_desc niter_desc;
2291 /* Determine whether the number_of_iterations_in_loop has already
2293 res = loop->nb_iterations;
2296 res = chrec_dont_know;
2298 if (dump_file && (dump_flags & TDF_DETAILS))
2299 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2301 exit = single_exit (loop);
2305 if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2308 type = TREE_TYPE (niter_desc.niter);
2309 if (integer_nonzerop (niter_desc.may_be_zero))
2310 res = build_int_cst (type, 0);
2311 else if (integer_zerop (niter_desc.may_be_zero))
2312 res = niter_desc.niter;
2314 res = chrec_dont_know;
2317 return set_nb_iterations_in_loop (loop, res);
2320 /* Returns the number of executions of the exit condition of LOOP,
2321 i.e., the number by one higher than number_of_latch_executions.
2322 Note that unline number_of_latch_executions, this number does
2323 not necessarily fit in the unsigned variant of the type of
2324 the control variable -- if the number of iterations is a constant,
2325 we return chrec_dont_know if adding one to number_of_latch_executions
2326 overflows; however, in case the number of iterations is symbolic
2327 expression, the caller is responsible for dealing with this
2328 the possible overflow. */
2331 number_of_exit_cond_executions (struct loop *loop)
2333 tree ret = number_of_latch_executions (loop);
2334 tree type = chrec_type (ret);
2336 if (chrec_contains_undetermined (ret))
2339 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2340 if (TREE_CODE (ret) == INTEGER_CST
2341 && TREE_OVERFLOW (ret))
2342 return chrec_dont_know;
2347 /* One of the drivers for testing the scalar evolutions analysis.
2348 This function computes the number of iterations for all the loops
2349 from the EXIT_CONDITIONS array. */
2352 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2355 unsigned nb_chrec_dont_know_loops = 0;
2356 unsigned nb_static_loops = 0;
2359 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2361 tree res = number_of_latch_executions (loop_containing_stmt (cond));
2362 if (chrec_contains_undetermined (res))
2363 nb_chrec_dont_know_loops++;
2370 fprintf (dump_file, "\n(\n");
2371 fprintf (dump_file, "-----------------------------------------\n");
2372 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2373 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2374 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2375 fprintf (dump_file, "-----------------------------------------\n");
2376 fprintf (dump_file, ")\n\n");
2378 print_loop_ir (dump_file);
2384 /* Counters for the stats. */
2390 unsigned nb_affine_multivar;
2391 unsigned nb_higher_poly;
2392 unsigned nb_chrec_dont_know;
2393 unsigned nb_undetermined;
2396 /* Reset the counters. */
2399 reset_chrecs_counters (struct chrec_stats *stats)
2401 stats->nb_chrecs = 0;
2402 stats->nb_affine = 0;
2403 stats->nb_affine_multivar = 0;
2404 stats->nb_higher_poly = 0;
2405 stats->nb_chrec_dont_know = 0;
2406 stats->nb_undetermined = 0;
2409 /* Dump the contents of a CHREC_STATS structure. */
2412 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2414 fprintf (file, "\n(\n");
2415 fprintf (file, "-----------------------------------------\n");
2416 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2417 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2418 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2419 stats->nb_higher_poly);
2420 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2421 fprintf (file, "-----------------------------------------\n");
2422 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2423 fprintf (file, "%d\twith undetermined coefficients\n",
2424 stats->nb_undetermined);
2425 fprintf (file, "-----------------------------------------\n");
2426 fprintf (file, "%d\tchrecs in the scev database\n",
2427 (int) htab_elements (scalar_evolution_info));
2428 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2429 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2430 fprintf (file, "-----------------------------------------\n");
2431 fprintf (file, ")\n\n");
2434 /* Gather statistics about CHREC. */
2437 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2439 if (dump_file && (dump_flags & TDF_STATS))
2441 fprintf (dump_file, "(classify_chrec ");
2442 print_generic_expr (dump_file, chrec, 0);
2443 fprintf (dump_file, "\n");
2448 if (chrec == NULL_TREE)
2450 stats->nb_undetermined++;
2454 switch (TREE_CODE (chrec))
2456 case POLYNOMIAL_CHREC:
2457 if (evolution_function_is_affine_p (chrec))
2459 if (dump_file && (dump_flags & TDF_STATS))
2460 fprintf (dump_file, " affine_univariate\n");
2463 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2465 if (dump_file && (dump_flags & TDF_STATS))
2466 fprintf (dump_file, " affine_multivariate\n");
2467 stats->nb_affine_multivar++;
2471 if (dump_file && (dump_flags & TDF_STATS))
2472 fprintf (dump_file, " higher_degree_polynomial\n");
2473 stats->nb_higher_poly++;
2482 if (chrec_contains_undetermined (chrec))
2484 if (dump_file && (dump_flags & TDF_STATS))
2485 fprintf (dump_file, " undetermined\n");
2486 stats->nb_undetermined++;
2489 if (dump_file && (dump_flags & TDF_STATS))
2490 fprintf (dump_file, ")\n");
2493 /* One of the drivers for testing the scalar evolutions analysis.
2494 This function analyzes the scalar evolution of all the scalars
2495 defined as loop phi nodes in one of the loops from the
2496 EXIT_CONDITIONS array.
2498 TODO Optimization: A loop is in canonical form if it contains only
2499 a single scalar loop phi node. All the other scalars that have an
2500 evolution in the loop are rewritten in function of this single
2501 index. This allows the parallelization of the loop. */
2504 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2507 struct chrec_stats stats;
2510 reset_chrecs_counters (&stats);
2512 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2518 loop = loop_containing_stmt (cond);
2521 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2522 if (is_gimple_reg (PHI_RESULT (phi)))
2524 chrec = instantiate_parameters
2526 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2528 if (dump_file && (dump_flags & TDF_STATS))
2529 gather_chrec_stats (chrec, &stats);
2533 if (dump_file && (dump_flags & TDF_STATS))
2534 dump_chrecs_stats (dump_file, &stats);
2537 /* Callback for htab_traverse, gathers information on chrecs in the
2541 gather_stats_on_scev_database_1 (void **slot, void *stats)
2543 struct scev_info_str *entry = (struct scev_info_str *) *slot;
2545 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2550 /* Classify the chrecs of the whole database. */
2553 gather_stats_on_scev_database (void)
2555 struct chrec_stats stats;
2560 reset_chrecs_counters (&stats);
2562 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2565 dump_chrecs_stats (dump_file, &stats);
2573 initialize_scalar_evolutions_analyzer (void)
2575 /* The elements below are unique. */
2576 if (chrec_dont_know == NULL_TREE)
2578 chrec_not_analyzed_yet = NULL_TREE;
2579 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2580 chrec_known = make_node (SCEV_KNOWN);
2581 TREE_TYPE (chrec_dont_know) = void_type_node;
2582 TREE_TYPE (chrec_known) = void_type_node;
2586 /* Initialize the analysis of scalar evolutions for LOOPS. */
2589 scev_initialize (void)
2594 scalar_evolution_info = htab_create_alloc (100,
2600 already_instantiated = BITMAP_ALLOC (NULL);
2602 initialize_scalar_evolutions_analyzer ();
2604 FOR_EACH_LOOP (li, loop, 0)
2606 loop->nb_iterations = NULL_TREE;
2610 /* Cleans up the information cached by the scalar evolutions analysis. */
2618 if (!scalar_evolution_info || !current_loops)
2621 htab_empty (scalar_evolution_info);
2622 FOR_EACH_LOOP (li, loop, 0)
2624 loop->nb_iterations = NULL_TREE;
2628 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2629 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
2630 want step to be invariant in LOOP. Otherwise we require it to be an
2631 integer constant. IV->no_overflow is set to true if we are sure the iv cannot
2632 overflow (e.g. because it is computed in signed arithmetics). */
2635 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2636 bool allow_nonconstant_step)
2638 basic_block bb = bb_for_stmt (stmt);
2642 iv->base = NULL_TREE;
2643 iv->step = NULL_TREE;
2644 iv->no_overflow = false;
2646 type = TREE_TYPE (op);
2647 if (TREE_CODE (type) != INTEGER_TYPE
2648 && TREE_CODE (type) != POINTER_TYPE)
2651 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2653 if (chrec_contains_undetermined (ev))
2656 if (tree_does_not_contain_chrecs (ev)
2657 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2660 iv->step = build_int_cst (TREE_TYPE (ev), 0);
2661 iv->no_overflow = true;
2665 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2666 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2669 iv->step = CHREC_RIGHT (ev);
2670 if (allow_nonconstant_step)
2672 if (tree_contains_chrecs (iv->step, NULL)
2673 || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2676 else if (TREE_CODE (iv->step) != INTEGER_CST)
2679 iv->base = CHREC_LEFT (ev);
2680 if (tree_contains_chrecs (iv->base, NULL)
2681 || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2684 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2689 /* Runs the analysis of scalar evolutions. */
2692 scev_analysis (void)
2694 VEC(tree,heap) *exit_conditions;
2696 exit_conditions = VEC_alloc (tree, heap, 37);
2697 select_loops_exit_conditions (&exit_conditions);
2699 if (dump_file && (dump_flags & TDF_STATS))
2700 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2702 number_of_iterations_for_all_loops (&exit_conditions);
2703 VEC_free (tree, heap, exit_conditions);
2706 /* Finalize the scalar evolution analysis. */
2709 scev_finalize (void)
2711 if (!scalar_evolution_info)
2713 htab_delete (scalar_evolution_info);
2714 BITMAP_FREE (already_instantiated);
2715 scalar_evolution_info = NULL;
2718 /* Replace ssa names for that scev can prove they are constant by the
2719 appropriate constants. Also perform final value replacement in loops,
2720 in case the replacement expressions are cheap.
2722 We only consider SSA names defined by phi nodes; rest is left to the
2723 ordinary constant propagation pass. */
2726 scev_const_prop (void)
2729 tree name, phi, next_phi, type, ev;
2730 struct loop *loop, *ex_loop;
2731 bitmap ssa_names_to_remove = NULL;
2735 if (number_of_loops () <= 1)
2740 loop = bb->loop_father;
2742 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2744 name = PHI_RESULT (phi);
2746 if (!is_gimple_reg (name))
2749 type = TREE_TYPE (name);
2751 if (!POINTER_TYPE_P (type)
2752 && !INTEGRAL_TYPE_P (type))
2755 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2756 if (!is_gimple_min_invariant (ev)
2757 || !may_propagate_copy (name, ev))
2760 /* Replace the uses of the name. */
2762 replace_uses_by (name, ev);
2764 if (!ssa_names_to_remove)
2765 ssa_names_to_remove = BITMAP_ALLOC (NULL);
2766 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2770 /* Remove the ssa names that were replaced by constants. We do not
2771 remove them directly in the previous cycle, since this
2772 invalidates scev cache. */
2773 if (ssa_names_to_remove)
2777 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2779 name = ssa_name (i);
2780 phi = SSA_NAME_DEF_STMT (name);
2782 gcc_assert (TREE_CODE (phi) == PHI_NODE);
2783 remove_phi_node (phi, NULL, true);
2786 BITMAP_FREE (ssa_names_to_remove);
2790 /* Now the regular final value replacement. */
2791 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2794 tree def, rslt, ass, niter;
2795 block_stmt_iterator bsi;
2797 /* If we do not know exact number of iterations of the loop, we cannot
2798 replace the final value. */
2799 exit = single_exit (loop);
2803 niter = number_of_latch_executions (loop);
2804 /* We used to check here whether the computation of NITER is expensive,
2805 and avoided final value elimination if that is the case. The problem
2806 is that it is hard to evaluate whether the expression is too
2807 expensive, as we do not know what optimization opportunities the
2808 the elimination of the final value may reveal. Therefore, we now
2809 eliminate the final values of induction variables unconditionally. */
2810 if (niter == chrec_dont_know)
2813 /* Ensure that it is possible to insert new statements somewhere. */
2814 if (!single_pred_p (exit->dest))
2815 split_loop_exit_edge (exit);
2816 bsi = bsi_after_labels (exit->dest);
2818 ex_loop = superloop_at_depth (loop,
2819 loop_depth (exit->dest->loop_father) + 1);
2821 for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2823 next_phi = PHI_CHAIN (phi);
2824 rslt = PHI_RESULT (phi);
2825 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2826 if (!is_gimple_reg (def))
2829 if (!POINTER_TYPE_P (TREE_TYPE (def))
2830 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2833 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2834 def = compute_overall_effect_of_inner_loop (ex_loop, def);
2835 if (!tree_does_not_contain_chrecs (def)
2836 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2837 /* Moving the computation from the loop may prolong life range
2838 of some ssa names, which may cause problems if they appear
2839 on abnormal edges. */
2840 || contains_abnormal_ssa_name_p (def))
2843 /* Eliminate the PHI node and replace it by a computation outside
2845 def = unshare_expr (def);
2846 remove_phi_node (phi, NULL_TREE, false);
2848 ass = build_gimple_modify_stmt (rslt, NULL_TREE);
2849 SSA_NAME_DEF_STMT (rslt) = ass;
2851 block_stmt_iterator dest = bsi;
2852 bsi_insert_before (&dest, ass, BSI_NEW_STMT);
2853 def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
2854 true, BSI_SAME_STMT);
2856 GIMPLE_STMT_OPERAND (ass, 1) = def;
2863 #include "gt-tree-scalar-evolution.h"