1 /* Scalar evolution detector.
2 Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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 MODIFY_EXPR: 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 ({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 2: 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 3: Higher degree polynomials.
172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175 Example 4: Lucas, Fibonacci, or mixers in general.
187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188 following semantics: during the first iteration of the loop_1, the
189 variable contains the value 1, and then it contains the value "c".
190 Note that this syntax is close to the syntax of the loop-phi-node:
191 "a -> (1, c)_1" vs. "a = phi (1, c)".
193 The symbolic chrec representation contains all the semantics of the
194 original code. What is more difficult is to use this information.
196 Example 5: Flip-flops, or exchangers.
208 Based on these symbolic chrecs, it is possible to refine this
209 information into the more precise PERIODIC_CHRECs:
214 This transformation is not yet implemented.
218 You can find a more detailed description of the algorithm in:
219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
221 this is a preliminary report and some of the details of the
222 algorithm have changed. I'm working on a research report that
223 updates the description of the algorithms to reflect the design
224 choices used in this implementation.
226 A set of slides show a high level overview of the algorithm and run
227 an example through the scalar evolution analyzer:
228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230 The slides that I have presented at the GCC Summit'04 are available
231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
236 #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"
254 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
255 static tree resolve_mixers (struct loop *, tree);
257 /* The cached information about a ssa name VAR, claiming that inside LOOP,
258 the value of VAR can be expressed as CHREC. */
266 /* Counters for the scev database. */
267 static unsigned nb_set_scev = 0;
268 static unsigned nb_get_scev = 0;
270 /* The following trees are unique elements. Thus the comparison of
271 another element to these elements should be done on the pointer to
272 these trees, and not on their value. */
274 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
275 tree chrec_not_analyzed_yet;
277 /* Reserved to the cases where the analyzer has detected an
278 undecidable property at compile time. */
279 tree chrec_dont_know;
281 /* When the analyzer has detected that a property will never
282 happen, then it qualifies it with chrec_known. */
285 static bitmap already_instantiated;
287 static 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 = xmalloc (sizeof (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 (((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 = e1;
318 const struct scev_info_str *elt2 = 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);
352 /* Tries to express CHREC in wider type TYPE. */
355 count_ev_in_wider_type (tree type, tree chrec)
360 if (!evolution_function_is_affine_p (chrec))
361 return fold_convert (type, chrec);
363 base = CHREC_LEFT (chrec);
364 step = CHREC_RIGHT (chrec);
365 loop = current_loops->parray[CHREC_VARIABLE (chrec)];
367 /* TODO -- if we knew the statement at that the conversion occurs,
368 we could pass it to can_count_iv_in_wider_type and get a better
370 step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
372 return fold_convert (type, chrec);
373 base = chrec_convert (type, base);
375 return build_polynomial_chrec (CHREC_VARIABLE (chrec),
379 /* Return true when CHREC contains symbolic names defined in
383 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
385 if (chrec == NULL_TREE)
388 if (TREE_INVARIANT (chrec))
391 if (TREE_CODE (chrec) == VAR_DECL
392 || TREE_CODE (chrec) == PARM_DECL
393 || TREE_CODE (chrec) == FUNCTION_DECL
394 || TREE_CODE (chrec) == LABEL_DECL
395 || TREE_CODE (chrec) == RESULT_DECL
396 || TREE_CODE (chrec) == FIELD_DECL)
399 if (TREE_CODE (chrec) == SSA_NAME)
401 tree def = SSA_NAME_DEF_STMT (chrec);
402 struct loop *def_loop = loop_containing_stmt (def);
403 struct loop *loop = current_loops->parray[loop_nb];
405 if (def_loop == NULL)
408 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
414 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
417 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
422 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
427 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
436 /* Return true when PHI is a loop-phi-node. */
439 loop_phi_node_p (tree phi)
441 /* The implementation of this function is based on the following
442 property: "all the loop-phi-nodes of a loop are contained in the
443 loop's header basic block". */
445 return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
448 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
449 In general, in the case of multivariate evolutions we want to get
450 the evolution in different loops. LOOP specifies the level for
451 which to get the evolution.
455 | for (j = 0; j < 100; j++)
457 | for (k = 0; k < 100; k++)
459 | i = k + j; - Here the value of i is a function of j, k.
461 | ... = i - Here the value of i is a function of j.
463 | ... = i - Here the value of i is a scalar.
469 | i_1 = phi (i_0, i_2)
473 This loop has the same effect as:
474 LOOP_1 has the same effect as:
478 The overall effect of the loop, "i_0 + 20" in the previous example,
479 is obtained by passing in the parameters: LOOP = 1,
480 EVOLUTION_FN = {i_0, +, 2}_1.
484 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
488 if (evolution_fn == chrec_dont_know)
489 return chrec_dont_know;
491 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
493 if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
495 struct loop *inner_loop =
496 current_loops->parray[CHREC_VARIABLE (evolution_fn)];
497 tree nb_iter = number_of_iterations_in_loop (inner_loop);
499 if (nb_iter == chrec_dont_know)
500 return chrec_dont_know;
505 /* Number of iterations is off by one (the ssa name we
506 analyze must be defined before the exit). */
507 nb_iter = chrec_fold_minus (chrec_type (nb_iter),
509 build_int_cst_type (chrec_type (nb_iter), 1));
511 /* evolution_fn is the evolution function in LOOP. Get
512 its value in the nb_iter-th iteration. */
513 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
515 /* Continue the computation until ending on a parent of LOOP. */
516 return compute_overall_effect_of_inner_loop (loop, res);
523 /* If the evolution function is an invariant, there is nothing to do. */
524 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
528 return chrec_dont_know;
531 /* Determine whether the CHREC is always positive/negative. If the expression
532 cannot be statically analyzed, return false, otherwise set the answer into
536 chrec_is_positive (tree chrec, bool *value)
543 switch (TREE_CODE (chrec))
545 case POLYNOMIAL_CHREC:
546 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
547 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
550 /* FIXME -- overflows. */
551 if (value0 == value1)
557 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
558 and the proof consists in showing that the sign never
559 changes during the execution of the loop, from 0 to
560 loop->nb_iterations. */
561 if (!evolution_function_is_affine_p (chrec))
564 nb_iter = number_of_iterations_in_loop
565 (current_loops->parray[CHREC_VARIABLE (chrec)]);
567 if (chrec_contains_undetermined (nb_iter))
570 nb_iter = chrec_fold_minus
571 (chrec_type (nb_iter), nb_iter,
572 build_int_cst (chrec_type (nb_iter), 1));
575 /* TODO -- If the test is after the exit, we may decrease the number of
576 iterations by one. */
578 nb_iter = chrec_fold_minus
579 (chrec_type (nb_iter), nb_iter,
580 build_int_cst (chrec_type (nb_iter), 1));
583 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
585 if (!chrec_is_positive (end_value, &value2))
589 return value0 == value1;
592 *value = (tree_int_cst_sgn (chrec) == 1);
600 /* Associate CHREC to SCALAR. */
603 set_scalar_evolution (tree scalar, tree chrec)
607 if (TREE_CODE (scalar) != SSA_NAME)
610 scalar_info = find_var_scev_info (scalar);
614 if (dump_flags & TDF_DETAILS)
616 fprintf (dump_file, "(set_scalar_evolution \n");
617 fprintf (dump_file, " (scalar = ");
618 print_generic_expr (dump_file, scalar, 0);
619 fprintf (dump_file, ")\n (scalar_evolution = ");
620 print_generic_expr (dump_file, chrec, 0);
621 fprintf (dump_file, "))\n");
623 if (dump_flags & TDF_STATS)
627 *scalar_info = chrec;
630 /* Retrieve the chrec associated to SCALAR in the LOOP. */
633 get_scalar_evolution (tree scalar)
639 if (dump_flags & TDF_DETAILS)
641 fprintf (dump_file, "(get_scalar_evolution \n");
642 fprintf (dump_file, " (scalar = ");
643 print_generic_expr (dump_file, scalar, 0);
644 fprintf (dump_file, ")\n");
646 if (dump_flags & TDF_STATS)
650 switch (TREE_CODE (scalar))
653 res = *find_var_scev_info (scalar);
662 res = chrec_not_analyzed_yet;
666 if (dump_file && (dump_flags & TDF_DETAILS))
668 fprintf (dump_file, " (scalar_evolution = ");
669 print_generic_expr (dump_file, res, 0);
670 fprintf (dump_file, "))\n");
676 /* Helper function for add_to_evolution. Returns the evolution
677 function for an assignment of the form "a = b + c", where "a" and
678 "b" are on the strongly connected component. CHREC_BEFORE is the
679 information that we already have collected up to this point.
680 TO_ADD is the evolution of "c".
682 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
683 evolution the expression TO_ADD, otherwise construct an evolution
684 part for this loop. */
687 add_to_evolution_1 (unsigned loop_nb,
691 switch (TREE_CODE (chrec_before))
693 case POLYNOMIAL_CHREC:
694 if (CHREC_VARIABLE (chrec_before) <= loop_nb)
698 tree type = chrec_type (chrec_before);
700 /* When there is no evolution part in this loop, build it. */
701 if (CHREC_VARIABLE (chrec_before) < loop_nb)
705 right = build_int_cst (type, 0);
709 var = CHREC_VARIABLE (chrec_before);
710 left = CHREC_LEFT (chrec_before);
711 right = CHREC_RIGHT (chrec_before);
714 return build_polynomial_chrec
715 (var, left, chrec_fold_plus (type, right, to_add));
718 /* Search the evolution in LOOP_NB. */
719 return build_polynomial_chrec
720 (CHREC_VARIABLE (chrec_before),
721 add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
722 CHREC_RIGHT (chrec_before));
725 /* These nodes do not depend on a loop. */
726 if (chrec_before == chrec_dont_know)
727 return chrec_dont_know;
728 return build_polynomial_chrec (loop_nb, chrec_before, to_add);
732 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
735 Description (provided for completeness, for those who read code in
736 a plane, and for my poor 62 bytes brain that would have forgotten
737 all this in the next two or three months):
739 The algorithm of translation of programs from the SSA representation
740 into the chrecs syntax is based on a pattern matching. After having
741 reconstructed the overall tree expression for a loop, there are only
742 two cases that can arise:
744 1. a = loop-phi (init, a + expr)
745 2. a = loop-phi (init, expr)
747 where EXPR is either a scalar constant with respect to the analyzed
748 loop (this is a degree 0 polynomial), or an expression containing
749 other loop-phi definitions (these are higher degree polynomials).
756 | a = phi (init, a + 5)
763 | a = phi (inita, 2 * b + 3)
764 | b = phi (initb, b + 1)
767 For the first case, the semantics of the SSA representation is:
769 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
771 that is, there is a loop index "x" that determines the scalar value
772 of the variable during the loop execution. During the first
773 iteration, the value is that of the initial condition INIT, while
774 during the subsequent iterations, it is the sum of the initial
775 condition with the sum of all the values of EXPR from the initial
776 iteration to the before last considered iteration.
778 For the second case, the semantics of the SSA program is:
780 | a (x) = init, if x = 0;
781 | expr (x - 1), otherwise.
783 The second case corresponds to the PEELED_CHREC, whose syntax is
784 close to the syntax of a loop-phi-node:
786 | phi (init, expr) vs. (init, expr)_x
788 The proof of the translation algorithm for the first case is a
789 proof by structural induction based on the degree of EXPR.
792 When EXPR is a constant with respect to the analyzed loop, or in
793 other words when EXPR is a polynomial of degree 0, the evolution of
794 the variable A in the loop is an affine function with an initial
795 condition INIT, and a step EXPR. In order to show this, we start
796 from the semantics of the SSA representation:
798 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
800 and since "expr (j)" is a constant with respect to "j",
802 f (x) = init + x * expr
804 Finally, based on the semantics of the pure sum chrecs, by
805 identification we get the corresponding chrecs syntax:
807 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
808 f (x) -> {init, +, expr}_x
811 Suppose that EXPR is a polynomial of degree N with respect to the
812 analyzed loop_x for which we have already determined that it is
813 written under the chrecs syntax:
815 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
817 We start from the semantics of the SSA program:
819 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
821 | f (x) = init + \sum_{j = 0}^{x - 1}
822 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
824 | f (x) = init + \sum_{j = 0}^{x - 1}
825 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
827 | f (x) = init + \sum_{k = 0}^{n - 1}
828 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
830 | f (x) = init + \sum_{k = 0}^{n - 1}
831 | (b_k * \binom{x}{k + 1})
833 | f (x) = init + b_0 * \binom{x}{1} + ...
834 | + b_{n-1} * \binom{x}{n}
836 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
837 | + b_{n-1} * \binom{x}{n}
840 And finally from the definition of the chrecs syntax, we identify:
841 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
843 This shows the mechanism that stands behind the add_to_evolution
844 function. An important point is that the use of symbolic
845 parameters avoids the need of an analysis schedule.
852 | a = phi (inita, a + 2 + b)
853 | b = phi (initb, b + 1)
856 When analyzing "a", the algorithm keeps "b" symbolically:
858 | a -> {inita, +, 2 + b}_1
860 Then, after instantiation, the analyzer ends on the evolution:
862 | a -> {inita, +, 2 + initb, +, 1}_1
867 add_to_evolution (unsigned loop_nb,
872 tree type = chrec_type (to_add);
873 tree res = NULL_TREE;
875 if (to_add == NULL_TREE)
878 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
879 instantiated at this point. */
880 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
881 /* This should not happen. */
882 return chrec_dont_know;
884 if (dump_file && (dump_flags & TDF_DETAILS))
886 fprintf (dump_file, "(add_to_evolution \n");
887 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
888 fprintf (dump_file, " (chrec_before = ");
889 print_generic_expr (dump_file, chrec_before, 0);
890 fprintf (dump_file, ")\n (to_add = ");
891 print_generic_expr (dump_file, to_add, 0);
892 fprintf (dump_file, ")\n");
895 if (code == MINUS_EXPR)
896 to_add = chrec_fold_multiply (type, to_add,
897 build_int_cst_type (type, -1));
899 res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
901 if (dump_file && (dump_flags & TDF_DETAILS))
903 fprintf (dump_file, " (res = ");
904 print_generic_expr (dump_file, res, 0);
905 fprintf (dump_file, "))\n");
911 /* Helper function. */
914 set_nb_iterations_in_loop (struct loop *loop,
917 res = chrec_fold_plus (chrec_type (res), res,
918 build_int_cst_type (chrec_type (res), 1));
920 /* FIXME HWI: However we want to store one iteration less than the
921 count of the loop in order to be compatible with the other
922 nb_iter computations in loop-iv. This also allows the
923 representation of nb_iters that are equal to MAX_INT. */
924 if (TREE_CODE (res) == INTEGER_CST
925 && (TREE_INT_CST_LOW (res) == 0
926 || TREE_OVERFLOW (res)))
927 res = chrec_dont_know;
929 if (dump_file && (dump_flags & TDF_DETAILS))
931 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
932 print_generic_expr (dump_file, res, 0);
933 fprintf (dump_file, "))\n");
936 loop->nb_iterations = res;
942 /* This section selects the loops that will be good candidates for the
943 scalar evolution analysis. For the moment, greedily select all the
944 loop nests we could analyze. */
946 /* Return true when it is possible to analyze the condition expression
950 analyzable_condition (tree expr)
954 if (TREE_CODE (expr) != COND_EXPR)
957 condition = TREE_OPERAND (expr, 0);
959 switch (TREE_CODE (condition))
979 /* For a loop with a single exit edge, return the COND_EXPR that
980 guards the exit edge. If the expression is too difficult to
981 analyze, then give up. */
984 get_loop_exit_condition (struct loop *loop)
986 tree res = NULL_TREE;
987 edge exit_edge = loop->single_exit;
990 if (dump_file && (dump_flags & TDF_DETAILS))
991 fprintf (dump_file, "(get_loop_exit_condition \n ");
997 expr = last_stmt (exit_edge->src);
998 if (analyzable_condition (expr))
1002 if (dump_file && (dump_flags & TDF_DETAILS))
1004 print_generic_expr (dump_file, res, 0);
1005 fprintf (dump_file, ")\n");
1011 /* Recursively determine and enqueue the exit conditions for a loop. */
1014 get_exit_conditions_rec (struct loop *loop,
1015 VEC(tree,heap) **exit_conditions)
1020 /* Recurse on the inner loops, then on the next (sibling) loops. */
1021 get_exit_conditions_rec (loop->inner, exit_conditions);
1022 get_exit_conditions_rec (loop->next, exit_conditions);
1024 if (loop->single_exit)
1026 tree loop_condition = get_loop_exit_condition (loop);
1029 VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1033 /* Select the candidate loop nests for the analysis. This function
1034 initializes the EXIT_CONDITIONS array. */
1037 select_loops_exit_conditions (struct loops *loops,
1038 VEC(tree,heap) **exit_conditions)
1040 struct loop *function_body = loops->parray[0];
1042 get_exit_conditions_rec (function_body->inner, exit_conditions);
1046 /* Depth first search algorithm. */
1048 static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
1050 /* Follow the ssa edge into the right hand side RHS of an assignment.
1051 Return true if the strongly connected component has been found. */
1054 follow_ssa_edge_in_rhs (struct loop *loop,
1057 tree *evolution_of_loop)
1061 tree type_rhs = TREE_TYPE (rhs);
1063 /* The RHS is one of the following cases:
1069 - other cases are not yet handled. */
1070 switch (TREE_CODE (rhs))
1073 /* This assignment is under the form "a_1 = (cast) rhs. */
1074 res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
1076 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
1080 /* This assignment is under the form "a_1 = 7". */
1085 /* This assignment is under the form: "a_1 = b_2". */
1086 res = follow_ssa_edge
1087 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
1091 /* This case is under the form "rhs0 + rhs1". */
1092 rhs0 = TREE_OPERAND (rhs, 0);
1093 rhs1 = TREE_OPERAND (rhs, 1);
1094 STRIP_TYPE_NOPS (rhs0);
1095 STRIP_TYPE_NOPS (rhs1);
1097 if (TREE_CODE (rhs0) == SSA_NAME)
1099 if (TREE_CODE (rhs1) == SSA_NAME)
1101 /* Match an assignment under the form:
1103 res = follow_ssa_edge
1104 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1108 *evolution_of_loop = add_to_evolution
1110 chrec_convert (type_rhs, *evolution_of_loop),
1115 res = follow_ssa_edge
1116 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1120 *evolution_of_loop = add_to_evolution
1122 chrec_convert (type_rhs, *evolution_of_loop),
1129 /* Match an assignment under the form:
1131 res = follow_ssa_edge
1132 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1135 *evolution_of_loop = add_to_evolution
1136 (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1141 else if (TREE_CODE (rhs1) == SSA_NAME)
1143 /* Match an assignment under the form:
1145 res = follow_ssa_edge
1146 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1149 *evolution_of_loop = add_to_evolution
1150 (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1155 /* Otherwise, match an assignment under the form:
1157 /* And there is nothing to do. */
1163 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1164 rhs0 = TREE_OPERAND (rhs, 0);
1165 rhs1 = TREE_OPERAND (rhs, 1);
1166 STRIP_TYPE_NOPS (rhs0);
1167 STRIP_TYPE_NOPS (rhs1);
1169 if (TREE_CODE (rhs0) == SSA_NAME)
1171 /* Match an assignment under the form:
1173 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1176 *evolution_of_loop = add_to_evolution
1177 (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1181 /* Otherwise, match an assignment under the form:
1183 /* And there is nothing to do. */
1189 /* This case is under the form "opnd0 = rhs0 * rhs1". */
1190 rhs0 = TREE_OPERAND (rhs, 0);
1191 rhs1 = TREE_OPERAND (rhs, 1);
1192 STRIP_TYPE_NOPS (rhs0);
1193 STRIP_TYPE_NOPS (rhs1);
1195 if (TREE_CODE (rhs0) == SSA_NAME)
1197 if (TREE_CODE (rhs1) == SSA_NAME)
1199 /* Match an assignment under the form:
1201 res = follow_ssa_edge
1202 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1206 *evolution_of_loop = chrec_dont_know;
1210 res = follow_ssa_edge
1211 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1215 *evolution_of_loop = chrec_dont_know;
1221 /* Match an assignment under the form:
1223 res = follow_ssa_edge
1224 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1227 *evolution_of_loop = chrec_dont_know;
1231 else if (TREE_CODE (rhs1) == SSA_NAME)
1233 /* Match an assignment under the form:
1235 res = follow_ssa_edge
1236 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1239 *evolution_of_loop = chrec_dont_know;
1243 /* Otherwise, match an assignment under the form:
1245 /* And there is nothing to do. */
1252 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1253 It must be handled as a copy assignment of the form a_1 = a_2. */
1254 tree op0 = ASSERT_EXPR_VAR (rhs);
1255 if (TREE_CODE (op0) == SSA_NAME)
1256 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1257 halting_phi, evolution_of_loop);
1272 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1275 backedge_phi_arg_p (tree phi, int i)
1277 edge e = PHI_ARG_EDGE (phi, i);
1279 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1280 about updating it anywhere, and this should work as well most of the
1282 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1288 /* Helper function for one branch of the condition-phi-node. Return
1289 true if the strongly connected component has been found following
1293 follow_ssa_edge_in_condition_phi_branch (int i,
1297 tree *evolution_of_branch,
1300 tree branch = PHI_ARG_DEF (condition_phi, i);
1301 *evolution_of_branch = chrec_dont_know;
1303 /* Do not follow back edges (they must belong to an irreducible loop, which
1304 we really do not want to worry about). */
1305 if (backedge_phi_arg_p (condition_phi, i))
1308 if (TREE_CODE (branch) == SSA_NAME)
1310 *evolution_of_branch = init_cond;
1311 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1312 evolution_of_branch);
1315 /* This case occurs when one of the condition branches sets
1316 the variable to a constant: i.e. a phi-node like
1317 "a_2 = PHI <a_7(5), 2(6)>;".
1319 FIXME: This case have to be refined correctly:
1320 in some cases it is possible to say something better than
1321 chrec_dont_know, for example using a wrap-around notation. */
1325 /* This function merges the branches of a condition-phi-node in a
1329 follow_ssa_edge_in_condition_phi (struct loop *loop,
1332 tree *evolution_of_loop)
1335 tree init = *evolution_of_loop;
1336 tree evolution_of_branch;
1338 if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1340 &evolution_of_branch,
1343 *evolution_of_loop = evolution_of_branch;
1345 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1347 /* Quickly give up when the evolution of one of the branches is
1349 if (*evolution_of_loop == chrec_dont_know)
1352 if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1354 &evolution_of_branch,
1358 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1359 evolution_of_branch);
1365 /* Follow an SSA edge in an inner loop. It computes the overall
1366 effect of the loop, and following the symbolic initial conditions,
1367 it follows the edges in the parent loop. The inner loop is
1368 considered as a single statement. */
1371 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1374 tree *evolution_of_loop)
1376 struct loop *loop = loop_containing_stmt (loop_phi_node);
1377 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1379 /* Sometimes, the inner loop is too difficult to analyze, and the
1380 result of the analysis is a symbolic parameter. */
1381 if (ev == PHI_RESULT (loop_phi_node))
1386 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1388 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1391 /* Follow the edges that exit the inner loop. */
1392 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1393 if (!flow_bb_inside_loop_p (loop, bb))
1394 res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
1398 /* If the path crosses this loop-phi, give up. */
1400 *evolution_of_loop = chrec_dont_know;
1405 /* Otherwise, compute the overall effect of the inner loop. */
1406 ev = compute_overall_effect_of_inner_loop (loop, ev);
1407 return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
1411 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1412 path that is analyzed on the return walk. */
1415 follow_ssa_edge (struct loop *loop,
1418 tree *evolution_of_loop)
1420 struct loop *def_loop;
1422 if (TREE_CODE (def) == NOP_EXPR)
1425 def_loop = loop_containing_stmt (def);
1427 switch (TREE_CODE (def))
1430 if (!loop_phi_node_p (def))
1431 /* DEF is a condition-phi-node. Follow the branches, and
1432 record their evolutions. Finally, merge the collected
1433 information and set the approximation to the main
1435 return follow_ssa_edge_in_condition_phi
1436 (loop, def, halting_phi, evolution_of_loop);
1438 /* When the analyzed phi is the halting_phi, the
1439 depth-first search is over: we have found a path from
1440 the halting_phi to itself in the loop. */
1441 if (def == halting_phi)
1444 /* Otherwise, the evolution of the HALTING_PHI depends
1445 on the evolution of another loop-phi-node, i.e. the
1446 evolution function is a higher degree polynomial. */
1447 if (def_loop == loop)
1451 if (flow_loop_nested_p (loop, def_loop))
1452 return follow_ssa_edge_inner_loop_phi
1453 (loop, def, halting_phi, evolution_of_loop);
1459 return follow_ssa_edge_in_rhs (loop,
1460 TREE_OPERAND (def, 1),
1465 /* At this level of abstraction, the program is just a set
1466 of MODIFY_EXPRs and PHI_NODEs. In principle there is no
1467 other node to be handled. */
1474 /* Given a LOOP_PHI_NODE, this function determines the evolution
1475 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1478 analyze_evolution_in_loop (tree loop_phi_node,
1482 tree evolution_function = chrec_not_analyzed_yet;
1483 struct loop *loop = loop_containing_stmt (loop_phi_node);
1486 if (dump_file && (dump_flags & TDF_DETAILS))
1488 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1489 fprintf (dump_file, " (loop_phi_node = ");
1490 print_generic_expr (dump_file, loop_phi_node, 0);
1491 fprintf (dump_file, ")\n");
1494 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1496 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1497 tree ssa_chain, ev_fn;
1500 /* Select the edges that enter the loop body. */
1501 bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1502 if (!flow_bb_inside_loop_p (loop, bb))
1505 if (TREE_CODE (arg) == SSA_NAME)
1507 ssa_chain = SSA_NAME_DEF_STMT (arg);
1509 /* Pass in the initial condition to the follow edge function. */
1511 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
1516 /* When it is impossible to go back on the same
1517 loop_phi_node by following the ssa edges, the
1518 evolution is represented by a peeled chrec, i.e. the
1519 first iteration, EV_FN has the value INIT_COND, then
1520 all the other iterations it has the value of ARG.
1521 For the moment, PEELED_CHREC nodes are not built. */
1523 ev_fn = chrec_dont_know;
1525 /* When there are multiple back edges of the loop (which in fact never
1526 happens currently, but nevertheless), merge their evolutions. */
1527 evolution_function = chrec_merge (evolution_function, ev_fn);
1530 if (dump_file && (dump_flags & TDF_DETAILS))
1532 fprintf (dump_file, " (evolution_function = ");
1533 print_generic_expr (dump_file, evolution_function, 0);
1534 fprintf (dump_file, "))\n");
1537 return evolution_function;
1540 /* Given a loop-phi-node, return the initial conditions of the
1541 variable on entry of the loop. When the CCP has propagated
1542 constants into the loop-phi-node, the initial condition is
1543 instantiated, otherwise the initial condition is kept symbolic.
1544 This analyzer does not analyze the evolution outside the current
1545 loop, and leaves this task to the on-demand tree reconstructor. */
1548 analyze_initial_condition (tree loop_phi_node)
1551 tree init_cond = chrec_not_analyzed_yet;
1552 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1554 if (dump_file && (dump_flags & TDF_DETAILS))
1556 fprintf (dump_file, "(analyze_initial_condition \n");
1557 fprintf (dump_file, " (loop_phi_node = \n");
1558 print_generic_expr (dump_file, loop_phi_node, 0);
1559 fprintf (dump_file, ")\n");
1562 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1564 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1565 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1567 /* When the branch is oriented to the loop's body, it does
1568 not contribute to the initial condition. */
1569 if (flow_bb_inside_loop_p (loop, bb))
1572 if (init_cond == chrec_not_analyzed_yet)
1578 if (TREE_CODE (branch) == SSA_NAME)
1580 init_cond = chrec_dont_know;
1584 init_cond = chrec_merge (init_cond, branch);
1587 /* Ooops -- a loop without an entry??? */
1588 if (init_cond == chrec_not_analyzed_yet)
1589 init_cond = chrec_dont_know;
1591 if (dump_file && (dump_flags & TDF_DETAILS))
1593 fprintf (dump_file, " (init_cond = ");
1594 print_generic_expr (dump_file, init_cond, 0);
1595 fprintf (dump_file, "))\n");
1601 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1604 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1607 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1610 if (phi_loop != loop)
1612 struct loop *subloop;
1613 tree evolution_fn = analyze_scalar_evolution
1614 (phi_loop, PHI_RESULT (loop_phi_node));
1616 /* Dive one level deeper. */
1617 subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1619 /* Interpret the subloop. */
1620 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1624 /* Otherwise really interpret the loop phi. */
1625 init_cond = analyze_initial_condition (loop_phi_node);
1626 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1631 /* This function merges the branches of a condition-phi-node,
1632 contained in the outermost loop, and whose arguments are already
1636 interpret_condition_phi (struct loop *loop, tree condition_phi)
1639 tree res = chrec_not_analyzed_yet;
1641 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1645 if (backedge_phi_arg_p (condition_phi, i))
1647 res = chrec_dont_know;
1651 branch_chrec = analyze_scalar_evolution
1652 (loop, PHI_ARG_DEF (condition_phi, i));
1654 res = chrec_merge (res, branch_chrec);
1660 /* Interpret the right hand side of a modify_expr OPND1. If we didn't
1661 analyze this node before, follow the definitions until ending
1662 either on an analyzed modify_expr, or on a loop-phi-node. On the
1663 return path, this function propagates evolutions (ala constant copy
1664 propagation). OPND1 is not a GIMPLE expression because we could
1665 analyze the effect of an inner loop: see interpret_loop_phi. */
1668 interpret_rhs_modify_expr (struct loop *loop,
1669 tree opnd1, tree type)
1671 tree res, opnd10, opnd11, chrec10, chrec11;
1673 if (is_gimple_min_invariant (opnd1))
1674 return chrec_convert (type, opnd1);
1676 switch (TREE_CODE (opnd1))
1679 opnd10 = TREE_OPERAND (opnd1, 0);
1680 opnd11 = TREE_OPERAND (opnd1, 1);
1681 chrec10 = analyze_scalar_evolution (loop, opnd10);
1682 chrec11 = analyze_scalar_evolution (loop, opnd11);
1683 chrec10 = chrec_convert (type, chrec10);
1684 chrec11 = chrec_convert (type, chrec11);
1685 res = chrec_fold_plus (type, chrec10, chrec11);
1689 opnd10 = TREE_OPERAND (opnd1, 0);
1690 opnd11 = TREE_OPERAND (opnd1, 1);
1691 chrec10 = analyze_scalar_evolution (loop, opnd10);
1692 chrec11 = analyze_scalar_evolution (loop, opnd11);
1693 chrec10 = chrec_convert (type, chrec10);
1694 chrec11 = chrec_convert (type, chrec11);
1695 res = chrec_fold_minus (type, chrec10, chrec11);
1699 opnd10 = TREE_OPERAND (opnd1, 0);
1700 chrec10 = analyze_scalar_evolution (loop, opnd10);
1701 chrec10 = chrec_convert (type, chrec10);
1702 res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10);
1706 opnd10 = TREE_OPERAND (opnd1, 0);
1707 opnd11 = TREE_OPERAND (opnd1, 1);
1708 chrec10 = analyze_scalar_evolution (loop, opnd10);
1709 chrec11 = analyze_scalar_evolution (loop, opnd11);
1710 chrec10 = chrec_convert (type, chrec10);
1711 chrec11 = chrec_convert (type, chrec11);
1712 res = chrec_fold_multiply (type, chrec10, chrec11);
1716 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
1720 opnd10 = ASSERT_EXPR_VAR (opnd1);
1721 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10));
1726 opnd10 = TREE_OPERAND (opnd1, 0);
1727 chrec10 = analyze_scalar_evolution (loop, opnd10);
1728 res = chrec_convert (type, chrec10);
1732 res = chrec_dont_know;
1741 /* This section contains all the entry points:
1742 - number_of_iterations_in_loop,
1743 - analyze_scalar_evolution,
1744 - instantiate_parameters.
1747 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1748 common ancestor of DEF_LOOP and USE_LOOP. */
1751 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1752 struct loop *def_loop,
1756 if (def_loop == wrto_loop)
1759 def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1760 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1762 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1765 /* Helper recursive function. */
1768 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1770 tree def, type = TREE_TYPE (var);
1772 struct loop *def_loop;
1775 return chrec_dont_know;
1777 if (TREE_CODE (var) != SSA_NAME)
1778 return interpret_rhs_modify_expr (loop, var, type);
1780 def = SSA_NAME_DEF_STMT (var);
1781 bb = bb_for_stmt (def);
1782 def_loop = bb ? bb->loop_father : NULL;
1785 || !flow_bb_inside_loop_p (loop, bb))
1787 /* Keep the symbolic form. */
1792 if (res != chrec_not_analyzed_yet)
1794 if (loop != bb->loop_father)
1795 res = compute_scalar_evolution_in_loop
1796 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1801 if (loop != def_loop)
1803 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1804 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1809 switch (TREE_CODE (def))
1812 res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
1816 if (loop_phi_node_p (def))
1817 res = interpret_loop_phi (loop, def);
1819 res = interpret_condition_phi (loop, def);
1823 res = chrec_dont_know;
1829 /* Keep the symbolic form. */
1830 if (res == chrec_dont_know)
1833 if (loop == def_loop)
1834 set_scalar_evolution (var, res);
1839 /* Entry point for the scalar evolution analyzer.
1840 Analyzes and returns the scalar evolution of the ssa_name VAR.
1841 LOOP_NB is the identifier number of the loop in which the variable
1844 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1845 pointer to the statement that uses this variable, in order to
1846 determine the evolution function of the variable, use the following
1849 unsigned loop_nb = loop_containing_stmt (stmt)->num;
1850 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1851 tree chrec_instantiated = instantiate_parameters
1852 (loop_nb, chrec_with_symbols);
1856 analyze_scalar_evolution (struct loop *loop, tree var)
1860 if (dump_file && (dump_flags & TDF_DETAILS))
1862 fprintf (dump_file, "(analyze_scalar_evolution \n");
1863 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1864 fprintf (dump_file, " (scalar = ");
1865 print_generic_expr (dump_file, var, 0);
1866 fprintf (dump_file, ")\n");
1869 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1871 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1874 if (dump_file && (dump_flags & TDF_DETAILS))
1875 fprintf (dump_file, ")\n");
1880 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1881 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1885 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1893 ev = analyze_scalar_evolution (use_loop, ev);
1894 ev = resolve_mixers (use_loop, ev);
1896 if (use_loop == wrto_loop)
1899 /* If the value of the use changes in the inner loop, we cannot express
1900 its value in the outer loop (we might try to return interval chrec,
1901 but we do not have a user for it anyway) */
1902 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1904 return chrec_dont_know;
1906 use_loop = use_loop->outer;
1910 /* Returns instantiated value for VERSION in CACHE. */
1913 get_instantiated_value (htab_t cache, tree version)
1915 struct scev_info_str *info, pattern;
1917 pattern.var = version;
1918 info = htab_find (cache, &pattern);
1926 /* Sets instantiated value for VERSION to VAL in CACHE. */
1929 set_instantiated_value (htab_t cache, tree version, tree val)
1931 struct scev_info_str *info, pattern;
1934 pattern.var = version;
1935 slot = htab_find_slot (cache, &pattern, INSERT);
1940 info = *slot = new_scev_info_str (version);
1944 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1945 with respect to LOOP. CHREC is the chrec to instantiate. If
1946 ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1947 outer loop chrecs is done. CACHE is the cache of already instantiated
1951 instantiate_parameters_1 (struct loop *loop, tree chrec,
1952 bool allow_superloop_chrecs,
1955 tree res, op0, op1, op2;
1957 struct loop *def_loop;
1959 if (chrec == NULL_TREE
1960 || automatically_generated_chrec_p (chrec))
1963 if (is_gimple_min_invariant (chrec))
1966 switch (TREE_CODE (chrec))
1969 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1971 /* A parameter (or loop invariant and we do not want to include
1972 evolutions in outer loops), nothing to do. */
1974 || (!allow_superloop_chrecs
1975 && !flow_bb_inside_loop_p (loop, def_bb)))
1978 /* We cache the value of instantiated variable to avoid exponential
1979 time complexity due to reevaluations. We also store the convenient
1980 value in the cache in order to prevent infinite recursion -- we do
1981 not want to instantiate the SSA_NAME if it is in a mixer
1982 structure. This is used for avoiding the instantiation of
1983 recursively defined functions, such as:
1985 | a_2 -> {0, +, 1, +, a_2}_1 */
1987 res = get_instantiated_value (cache, chrec);
1991 /* Store the convenient value for chrec in the structure. If it
1992 is defined outside of the loop, we may just leave it in symbolic
1993 form, otherwise we need to admit that we do not know its behavior
1995 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1996 set_instantiated_value (cache, chrec, res);
1998 /* To make things even more complicated, instantiate_parameters_1
1999 calls analyze_scalar_evolution that may call # of iterations
2000 analysis that may in turn call instantiate_parameters_1 again.
2001 To prevent the infinite recursion, keep also the bitmap of
2002 ssa names that are being instantiated globally. */
2003 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2006 def_loop = find_common_loop (loop, def_bb->loop_father);
2008 /* If the analysis yields a parametric chrec, instantiate the
2010 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2011 res = analyze_scalar_evolution (def_loop, chrec);
2012 if (res != chrec_dont_know)
2013 res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs,
2015 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2017 /* Store the correct value to the cache. */
2018 set_instantiated_value (cache, chrec, res);
2021 case POLYNOMIAL_CHREC:
2022 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2023 allow_superloop_chrecs, cache);
2024 if (op0 == chrec_dont_know)
2025 return chrec_dont_know;
2027 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2028 allow_superloop_chrecs, cache);
2029 if (op1 == chrec_dont_know)
2030 return chrec_dont_know;
2032 if (CHREC_LEFT (chrec) != op0
2033 || CHREC_RIGHT (chrec) != op1)
2034 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2038 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2039 allow_superloop_chrecs, cache);
2040 if (op0 == chrec_dont_know)
2041 return chrec_dont_know;
2043 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2044 allow_superloop_chrecs, cache);
2045 if (op1 == chrec_dont_know)
2046 return chrec_dont_know;
2048 if (TREE_OPERAND (chrec, 0) != op0
2049 || TREE_OPERAND (chrec, 1) != op1)
2050 chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
2054 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2055 allow_superloop_chrecs, cache);
2056 if (op0 == chrec_dont_know)
2057 return chrec_dont_know;
2059 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2060 allow_superloop_chrecs, cache);
2061 if (op1 == chrec_dont_know)
2062 return chrec_dont_know;
2064 if (TREE_OPERAND (chrec, 0) != op0
2065 || TREE_OPERAND (chrec, 1) != op1)
2066 chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
2070 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2071 allow_superloop_chrecs, cache);
2072 if (op0 == chrec_dont_know)
2073 return chrec_dont_know;
2075 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2076 allow_superloop_chrecs, cache);
2077 if (op1 == chrec_dont_know)
2078 return chrec_dont_know;
2080 if (TREE_OPERAND (chrec, 0) != op0
2081 || TREE_OPERAND (chrec, 1) != op1)
2082 chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
2087 case NON_LVALUE_EXPR:
2088 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2089 allow_superloop_chrecs, cache);
2090 if (op0 == chrec_dont_know)
2091 return chrec_dont_know;
2093 if (op0 == TREE_OPERAND (chrec, 0))
2096 return chrec_convert (TREE_TYPE (chrec), op0);
2098 case SCEV_NOT_KNOWN:
2099 return chrec_dont_know;
2108 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2111 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2112 allow_superloop_chrecs, cache);
2113 if (op0 == chrec_dont_know)
2114 return chrec_dont_know;
2116 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2117 allow_superloop_chrecs, cache);
2118 if (op1 == chrec_dont_know)
2119 return chrec_dont_know;
2121 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2122 allow_superloop_chrecs, cache);
2123 if (op2 == chrec_dont_know)
2124 return chrec_dont_know;
2126 if (op0 == TREE_OPERAND (chrec, 0)
2127 && op1 == TREE_OPERAND (chrec, 1)
2128 && op2 == TREE_OPERAND (chrec, 2))
2131 return fold (build (TREE_CODE (chrec),
2132 TREE_TYPE (chrec), op0, op1, op2));
2135 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2136 allow_superloop_chrecs, cache);
2137 if (op0 == chrec_dont_know)
2138 return chrec_dont_know;
2140 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2141 allow_superloop_chrecs, cache);
2142 if (op1 == chrec_dont_know)
2143 return chrec_dont_know;
2145 if (op0 == TREE_OPERAND (chrec, 0)
2146 && op1 == TREE_OPERAND (chrec, 1))
2148 return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
2151 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2152 allow_superloop_chrecs, cache);
2153 if (op0 == chrec_dont_know)
2154 return chrec_dont_know;
2155 if (op0 == TREE_OPERAND (chrec, 0))
2157 return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
2166 /* Too complicated to handle. */
2167 return chrec_dont_know;
2170 /* Analyze all the parameters of the chrec that were left under a
2171 symbolic form. LOOP is the loop in which symbolic names have to
2172 be analyzed and instantiated. */
2175 instantiate_parameters (struct loop *loop,
2179 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2181 if (dump_file && (dump_flags & TDF_DETAILS))
2183 fprintf (dump_file, "(instantiate_parameters \n");
2184 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2185 fprintf (dump_file, " (chrec = ");
2186 print_generic_expr (dump_file, chrec, 0);
2187 fprintf (dump_file, ")\n");
2190 res = instantiate_parameters_1 (loop, chrec, true, cache);
2192 if (dump_file && (dump_flags & TDF_DETAILS))
2194 fprintf (dump_file, " (res = ");
2195 print_generic_expr (dump_file, res, 0);
2196 fprintf (dump_file, "))\n");
2199 htab_delete (cache);
2204 /* Similar to instantiate_parameters, but does not introduce the
2205 evolutions in outer loops for LOOP invariants in CHREC. */
2208 resolve_mixers (struct loop *loop, tree chrec)
2210 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2211 tree ret = instantiate_parameters_1 (loop, chrec, false, cache);
2212 htab_delete (cache);
2216 /* Entry point for the analysis of the number of iterations pass.
2217 This function tries to safely approximate the number of iterations
2218 the loop will run. When this property is not decidable at compile
2219 time, the result is chrec_dont_know. Otherwise the result is
2220 a scalar or a symbolic parameter.
2222 Example of analysis: suppose that the loop has an exit condition:
2224 "if (b > 49) goto end_loop;"
2226 and that in a previous analysis we have determined that the
2227 variable 'b' has an evolution function:
2229 "EF = {23, +, 5}_2".
2231 When we evaluate the function at the point 5, i.e. the value of the
2232 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2233 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2234 the loop body has been executed 6 times. */
2237 number_of_iterations_in_loop (struct loop *loop)
2241 struct tree_niter_desc niter_desc;
2243 /* Determine whether the number_of_iterations_in_loop has already
2245 res = loop->nb_iterations;
2248 res = chrec_dont_know;
2250 if (dump_file && (dump_flags & TDF_DETAILS))
2251 fprintf (dump_file, "(number_of_iterations_in_loop\n");
2253 exit = loop->single_exit;
2257 if (!number_of_iterations_exit (loop, exit, &niter_desc))
2260 type = TREE_TYPE (niter_desc.niter);
2261 if (integer_nonzerop (niter_desc.may_be_zero))
2262 res = build_int_cst (type, 0);
2263 else if (integer_zerop (niter_desc.may_be_zero))
2264 res = niter_desc.niter;
2266 res = chrec_dont_know;
2269 return set_nb_iterations_in_loop (loop, res);
2272 /* One of the drivers for testing the scalar evolutions analysis.
2273 This function computes the number of iterations for all the loops
2274 from the EXIT_CONDITIONS array. */
2277 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2280 unsigned nb_chrec_dont_know_loops = 0;
2281 unsigned nb_static_loops = 0;
2284 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2286 tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
2287 if (chrec_contains_undetermined (res))
2288 nb_chrec_dont_know_loops++;
2295 fprintf (dump_file, "\n(\n");
2296 fprintf (dump_file, "-----------------------------------------\n");
2297 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2298 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2299 fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2300 fprintf (dump_file, "-----------------------------------------\n");
2301 fprintf (dump_file, ")\n\n");
2303 print_loop_ir (dump_file);
2309 /* Counters for the stats. */
2315 unsigned nb_affine_multivar;
2316 unsigned nb_higher_poly;
2317 unsigned nb_chrec_dont_know;
2318 unsigned nb_undetermined;
2321 /* Reset the counters. */
2324 reset_chrecs_counters (struct chrec_stats *stats)
2326 stats->nb_chrecs = 0;
2327 stats->nb_affine = 0;
2328 stats->nb_affine_multivar = 0;
2329 stats->nb_higher_poly = 0;
2330 stats->nb_chrec_dont_know = 0;
2331 stats->nb_undetermined = 0;
2334 /* Dump the contents of a CHREC_STATS structure. */
2337 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2339 fprintf (file, "\n(\n");
2340 fprintf (file, "-----------------------------------------\n");
2341 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2342 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2343 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2344 stats->nb_higher_poly);
2345 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2346 fprintf (file, "-----------------------------------------\n");
2347 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2348 fprintf (file, "%d\twith undetermined coefficients\n",
2349 stats->nb_undetermined);
2350 fprintf (file, "-----------------------------------------\n");
2351 fprintf (file, "%d\tchrecs in the scev database\n",
2352 (int) htab_elements (scalar_evolution_info));
2353 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2354 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2355 fprintf (file, "-----------------------------------------\n");
2356 fprintf (file, ")\n\n");
2359 /* Gather statistics about CHREC. */
2362 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2364 if (dump_file && (dump_flags & TDF_STATS))
2366 fprintf (dump_file, "(classify_chrec ");
2367 print_generic_expr (dump_file, chrec, 0);
2368 fprintf (dump_file, "\n");
2373 if (chrec == NULL_TREE)
2375 stats->nb_undetermined++;
2379 switch (TREE_CODE (chrec))
2381 case POLYNOMIAL_CHREC:
2382 if (evolution_function_is_affine_p (chrec))
2384 if (dump_file && (dump_flags & TDF_STATS))
2385 fprintf (dump_file, " affine_univariate\n");
2388 else if (evolution_function_is_affine_multivariate_p (chrec))
2390 if (dump_file && (dump_flags & TDF_STATS))
2391 fprintf (dump_file, " affine_multivariate\n");
2392 stats->nb_affine_multivar++;
2396 if (dump_file && (dump_flags & TDF_STATS))
2397 fprintf (dump_file, " higher_degree_polynomial\n");
2398 stats->nb_higher_poly++;
2407 if (chrec_contains_undetermined (chrec))
2409 if (dump_file && (dump_flags & TDF_STATS))
2410 fprintf (dump_file, " undetermined\n");
2411 stats->nb_undetermined++;
2414 if (dump_file && (dump_flags & TDF_STATS))
2415 fprintf (dump_file, ")\n");
2418 /* One of the drivers for testing the scalar evolutions analysis.
2419 This function analyzes the scalar evolution of all the scalars
2420 defined as loop phi nodes in one of the loops from the
2421 EXIT_CONDITIONS array.
2423 TODO Optimization: A loop is in canonical form if it contains only
2424 a single scalar loop phi node. All the other scalars that have an
2425 evolution in the loop are rewritten in function of this single
2426 index. This allows the parallelization of the loop. */
2429 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2432 struct chrec_stats stats;
2435 reset_chrecs_counters (&stats);
2437 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2443 loop = loop_containing_stmt (cond);
2446 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2447 if (is_gimple_reg (PHI_RESULT (phi)))
2449 chrec = instantiate_parameters
2451 analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2453 if (dump_file && (dump_flags & TDF_STATS))
2454 gather_chrec_stats (chrec, &stats);
2458 if (dump_file && (dump_flags & TDF_STATS))
2459 dump_chrecs_stats (dump_file, &stats);
2462 /* Callback for htab_traverse, gathers information on chrecs in the
2466 gather_stats_on_scev_database_1 (void **slot, void *stats)
2468 struct scev_info_str *entry = *slot;
2470 gather_chrec_stats (entry->chrec, stats);
2475 /* Classify the chrecs of the whole database. */
2478 gather_stats_on_scev_database (void)
2480 struct chrec_stats stats;
2485 reset_chrecs_counters (&stats);
2487 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2490 dump_chrecs_stats (dump_file, &stats);
2498 initialize_scalar_evolutions_analyzer (void)
2500 /* The elements below are unique. */
2501 if (chrec_dont_know == NULL_TREE)
2503 chrec_not_analyzed_yet = NULL_TREE;
2504 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2505 chrec_known = make_node (SCEV_KNOWN);
2506 TREE_TYPE (chrec_dont_know) = NULL_TREE;
2507 TREE_TYPE (chrec_known) = NULL_TREE;
2511 /* Initialize the analysis of scalar evolutions for LOOPS. */
2514 scev_initialize (struct loops *loops)
2517 current_loops = loops;
2519 scalar_evolution_info = htab_create (100, hash_scev_info,
2520 eq_scev_info, del_scev_info);
2521 already_instantiated = BITMAP_ALLOC (NULL);
2523 initialize_scalar_evolutions_analyzer ();
2525 for (i = 1; i < loops->num; i++)
2526 if (loops->parray[i])
2527 loops->parray[i]->nb_iterations = NULL_TREE;
2530 /* Cleans up the information cached by the scalar evolutions analysis. */
2538 if (!scalar_evolution_info || !current_loops)
2541 htab_empty (scalar_evolution_info);
2542 for (i = 1; i < current_loops->num; i++)
2544 loop = current_loops->parray[i];
2546 loop->nb_iterations = NULL_TREE;
2550 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2551 its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
2552 want STEP to be invariant in LOOP. Otherwise we require it to be an
2553 integer constant. */
2556 simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step,
2557 bool allow_nonconstant_step)
2559 basic_block bb = bb_for_stmt (stmt);
2565 type = TREE_TYPE (op);
2566 if (TREE_CODE (type) != INTEGER_TYPE
2567 && TREE_CODE (type) != POINTER_TYPE)
2570 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
2571 if (chrec_contains_undetermined (ev))
2574 if (tree_does_not_contain_chrecs (ev)
2575 && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2581 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2582 || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2585 *step = CHREC_RIGHT (ev);
2586 if (allow_nonconstant_step)
2588 if (tree_contains_chrecs (*step, NULL)
2589 || chrec_contains_symbols_defined_in_loop (*step, loop->num))
2592 else if (TREE_CODE (*step) != INTEGER_CST)
2595 *base = CHREC_LEFT (ev);
2596 if (tree_contains_chrecs (*base, NULL)
2597 || chrec_contains_symbols_defined_in_loop (*base, loop->num))
2603 /* Runs the analysis of scalar evolutions. */
2606 scev_analysis (void)
2608 VEC(tree,heap) *exit_conditions;
2610 exit_conditions = VEC_alloc (tree, heap, 37);
2611 select_loops_exit_conditions (current_loops, &exit_conditions);
2613 if (dump_file && (dump_flags & TDF_STATS))
2614 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2616 number_of_iterations_for_all_loops (&exit_conditions);
2617 VEC_free (tree, heap, exit_conditions);
2620 /* Finalize the scalar evolution analysis. */
2623 scev_finalize (void)
2625 htab_delete (scalar_evolution_info);
2626 BITMAP_FREE (already_instantiated);
2629 /* Replace ssa names for that scev can prove they are constant by the
2630 appropriate constants. Most importantly, this takes care of final
2633 We only consider SSA names defined by phi nodes; rest is left to the
2634 ordinary constant propagation pass. */
2637 scev_const_prop (void)
2640 tree name, phi, type, ev;
2642 bitmap ssa_names_to_remove = NULL;
2649 loop = bb->loop_father;
2651 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2653 name = PHI_RESULT (phi);
2655 if (!is_gimple_reg (name))
2658 type = TREE_TYPE (name);
2660 if (!POINTER_TYPE_P (type)
2661 && !INTEGRAL_TYPE_P (type))
2664 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2665 if (!is_gimple_min_invariant (ev)
2666 || !may_propagate_copy (name, ev))
2669 /* Replace the uses of the name. */
2670 replace_uses_by (name, ev);
2672 if (!ssa_names_to_remove)
2673 ssa_names_to_remove = BITMAP_ALLOC (NULL);
2674 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2678 /* Remove the ssa names that were replaced by constants. We do not remove them
2679 directly in the previous cycle, since this invalidates scev cache. */
2680 if (ssa_names_to_remove)
2685 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2687 name = ssa_name (i);
2688 phi = SSA_NAME_DEF_STMT (name);
2690 gcc_assert (TREE_CODE (phi) == PHI_NODE);
2691 remove_phi_node (phi, NULL);
2694 BITMAP_FREE (ssa_names_to_remove);