1 /* Scalar evolution detector.
2 Copyright (C) 2003-2015 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_ASSIGN: 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 (loop_1, {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 2a: 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 2b: Multivariate chains of recurrences.
170 Analyzing the access function of array A with
171 instantiate_parameters (loop_1, "j + k"), we obtain the
172 instantiation and the analysis of the scalar variables "j" and "k"
173 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175 {0, +, 1}_1. To obtain the evolution function in loop_3 and
176 instantiate the scalar variables up to loop_1, one has to use:
177 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178 The result of this call is {{0, +, 1}_1, +, 1}_2.
180 Example 3: Higher degree polynomials.
194 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197 Example 4: Lucas, Fibonacci, or mixers in general.
209 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210 following semantics: during the first iteration of the loop_1, the
211 variable contains the value 1, and then it contains the value "c".
212 Note that this syntax is close to the syntax of the loop-phi-node:
213 "a -> (1, c)_1" vs. "a = phi (1, c)".
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
218 Example 5: Flip-flops, or exchangers.
230 Based on these symbolic chrecs, it is possible to refine this
231 information into the more precise PERIODIC_CHRECs:
236 This transformation is not yet implemented.
240 You can find a more detailed description of the algorithm in:
241 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243 this is a preliminary report and some of the details of the
244 algorithm have changed. I'm working on a research report that
245 updates the description of the algorithms to reflect the design
246 choices used in this implementation.
248 A set of slides show a high level overview of the algorithm and run
249 an example through the scalar evolution analyzer:
250 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252 The slides that I have presented at the GCC Summit'04 are available
253 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
258 #include "coretypes.h"
266 #include "fold-const.h"
268 #include "insn-config.h"
273 #include "emit-rtl.h"
277 #include "gimple-pretty-print.h"
278 #include "internal-fn.h"
279 #include "gimplify.h"
280 #include "gimple-iterator.h"
281 #include "gimplify-me.h"
282 #include "tree-cfg.h"
283 #include "tree-ssa-loop-ivopts.h"
284 #include "tree-ssa-loop-manip.h"
285 #include "tree-ssa-loop-niter.h"
286 #include "tree-ssa-loop.h"
287 #include "tree-ssa.h"
289 #include "tree-chrec.h"
290 #include "tree-affine.h"
291 #include "tree-scalar-evolution.h"
292 #include "dumpfile.h"
294 #include "tree-ssa-propagate.h"
295 #include "gimple-fold.h"
297 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
298 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
301 /* The cached information about an SSA name with version NAME_VERSION,
302 claiming that below basic block with index INSTANTIATED_BELOW, the
303 value of the SSA name can be expressed as CHREC. */
305 struct GTY((for_user)) scev_info_str {
306 unsigned int name_version;
307 int instantiated_below;
311 /* Counters for the scev database. */
312 static unsigned nb_set_scev = 0;
313 static unsigned nb_get_scev = 0;
315 /* The following trees are unique elements. Thus the comparison of
316 another element to these elements should be done on the pointer to
317 these trees, and not on their value. */
319 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
320 tree chrec_not_analyzed_yet;
322 /* Reserved to the cases where the analyzer has detected an
323 undecidable property at compile time. */
324 tree chrec_dont_know;
326 /* When the analyzer has detected that a property will never
327 happen, then it qualifies it with chrec_known. */
330 struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
332 static hashval_t hash (scev_info_str *i);
333 static bool equal (const scev_info_str *a, const scev_info_str *b);
336 static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
339 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
341 static inline struct scev_info_str *
342 new_scev_info_str (basic_block instantiated_below, tree var)
344 struct scev_info_str *res;
346 res = ggc_alloc<scev_info_str> ();
347 res->name_version = SSA_NAME_VERSION (var);
348 res->chrec = chrec_not_analyzed_yet;
349 res->instantiated_below = instantiated_below->index;
354 /* Computes a hash function for database element ELT. */
357 scev_info_hasher::hash (scev_info_str *elt)
359 return elt->name_version ^ elt->instantiated_below;
362 /* Compares database elements E1 and E2. */
365 scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
367 return (elt1->name_version == elt2->name_version
368 && elt1->instantiated_below == elt2->instantiated_below);
371 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
372 A first query on VAR returns chrec_not_analyzed_yet. */
375 find_var_scev_info (basic_block instantiated_below, tree var)
377 struct scev_info_str *res;
378 struct scev_info_str tmp;
380 tmp.name_version = SSA_NAME_VERSION (var);
381 tmp.instantiated_below = instantiated_below->index;
382 scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
385 *slot = new_scev_info_str (instantiated_below, var);
391 /* Return true when CHREC contains symbolic names defined in
395 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
399 if (chrec == NULL_TREE)
402 if (is_gimple_min_invariant (chrec))
405 if (TREE_CODE (chrec) == SSA_NAME)
408 loop_p def_loop, loop;
410 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
413 def = SSA_NAME_DEF_STMT (chrec);
414 def_loop = loop_containing_stmt (def);
415 loop = get_loop (cfun, loop_nb);
417 if (def_loop == NULL)
420 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
426 n = TREE_OPERAND_LENGTH (chrec);
427 for (i = 0; i < n; i++)
428 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
434 /* Return true when PHI is a loop-phi-node. */
437 loop_phi_node_p (gimple *phi)
439 /* The implementation of this function is based on the following
440 property: "all the loop-phi-nodes of a loop are contained in the
441 loop's header basic block". */
443 return loop_containing_stmt (phi)->header == gimple_bb (phi);
446 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
447 In general, in the case of multivariate evolutions we want to get
448 the evolution in different loops. LOOP specifies the level for
449 which to get the evolution.
453 | for (j = 0; j < 100; j++)
455 | for (k = 0; k < 100; k++)
457 | i = k + j; - Here the value of i is a function of j, k.
459 | ... = i - Here the value of i is a function of j.
461 | ... = i - Here the value of i is a scalar.
467 | i_1 = phi (i_0, i_2)
471 This loop has the same effect as:
472 LOOP_1 has the same effect as:
476 The overall effect of the loop, "i_0 + 20" in the previous example,
477 is obtained by passing in the parameters: LOOP = 1,
478 EVOLUTION_FN = {i_0, +, 2}_1.
482 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
486 if (evolution_fn == chrec_dont_know)
487 return chrec_dont_know;
489 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
491 struct loop *inner_loop = get_chrec_loop (evolution_fn);
493 if (inner_loop == loop
494 || flow_loop_nested_p (loop, inner_loop))
496 tree nb_iter = number_of_latch_executions (inner_loop);
498 if (nb_iter == chrec_dont_know)
499 return chrec_dont_know;
504 /* evolution_fn is the evolution function in LOOP. Get
505 its value in the nb_iter-th iteration. */
506 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
508 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
509 res = instantiate_parameters (loop, res);
511 /* Continue the computation until ending on a parent of LOOP. */
512 return compute_overall_effect_of_inner_loop (loop, res);
519 /* If the evolution function is an invariant, there is nothing to do. */
520 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
524 return chrec_dont_know;
527 /* Associate CHREC to SCALAR. */
530 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
534 if (TREE_CODE (scalar) != SSA_NAME)
537 scalar_info = find_var_scev_info (instantiated_below, scalar);
541 if (dump_flags & TDF_SCEV)
543 fprintf (dump_file, "(set_scalar_evolution \n");
544 fprintf (dump_file, " instantiated_below = %d \n",
545 instantiated_below->index);
546 fprintf (dump_file, " (scalar = ");
547 print_generic_expr (dump_file, scalar, 0);
548 fprintf (dump_file, ")\n (scalar_evolution = ");
549 print_generic_expr (dump_file, chrec, 0);
550 fprintf (dump_file, "))\n");
552 if (dump_flags & TDF_STATS)
556 *scalar_info = chrec;
559 /* Retrieve the chrec associated to SCALAR instantiated below
560 INSTANTIATED_BELOW block. */
563 get_scalar_evolution (basic_block instantiated_below, tree scalar)
569 if (dump_flags & TDF_SCEV)
571 fprintf (dump_file, "(get_scalar_evolution \n");
572 fprintf (dump_file, " (scalar = ");
573 print_generic_expr (dump_file, scalar, 0);
574 fprintf (dump_file, ")\n");
576 if (dump_flags & TDF_STATS)
580 switch (TREE_CODE (scalar))
583 res = *find_var_scev_info (instantiated_below, scalar);
593 res = chrec_not_analyzed_yet;
597 if (dump_file && (dump_flags & TDF_SCEV))
599 fprintf (dump_file, " (scalar_evolution = ");
600 print_generic_expr (dump_file, res, 0);
601 fprintf (dump_file, "))\n");
607 /* Helper function for add_to_evolution. Returns the evolution
608 function for an assignment of the form "a = b + c", where "a" and
609 "b" are on the strongly connected component. CHREC_BEFORE is the
610 information that we already have collected up to this point.
611 TO_ADD is the evolution of "c".
613 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
614 evolution the expression TO_ADD, otherwise construct an evolution
615 part for this loop. */
618 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
621 tree type, left, right;
622 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
624 switch (TREE_CODE (chrec_before))
626 case POLYNOMIAL_CHREC:
627 chloop = get_chrec_loop (chrec_before);
629 || flow_loop_nested_p (chloop, loop))
633 type = chrec_type (chrec_before);
635 /* When there is no evolution part in this loop, build it. */
640 right = SCALAR_FLOAT_TYPE_P (type)
641 ? build_real (type, dconst0)
642 : build_int_cst (type, 0);
646 var = CHREC_VARIABLE (chrec_before);
647 left = CHREC_LEFT (chrec_before);
648 right = CHREC_RIGHT (chrec_before);
651 to_add = chrec_convert (type, to_add, at_stmt);
652 right = chrec_convert_rhs (type, right, at_stmt);
653 right = chrec_fold_plus (chrec_type (right), right, to_add);
654 return build_polynomial_chrec (var, left, right);
658 gcc_assert (flow_loop_nested_p (loop, chloop));
660 /* Search the evolution in LOOP_NB. */
661 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
663 right = CHREC_RIGHT (chrec_before);
664 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
665 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
670 /* These nodes do not depend on a loop. */
671 if (chrec_before == chrec_dont_know)
672 return chrec_dont_know;
675 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
676 return build_polynomial_chrec (loop_nb, left, right);
680 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
683 Description (provided for completeness, for those who read code in
684 a plane, and for my poor 62 bytes brain that would have forgotten
685 all this in the next two or three months):
687 The algorithm of translation of programs from the SSA representation
688 into the chrecs syntax is based on a pattern matching. After having
689 reconstructed the overall tree expression for a loop, there are only
690 two cases that can arise:
692 1. a = loop-phi (init, a + expr)
693 2. a = loop-phi (init, expr)
695 where EXPR is either a scalar constant with respect to the analyzed
696 loop (this is a degree 0 polynomial), or an expression containing
697 other loop-phi definitions (these are higher degree polynomials).
704 | a = phi (init, a + 5)
711 | a = phi (inita, 2 * b + 3)
712 | b = phi (initb, b + 1)
715 For the first case, the semantics of the SSA representation is:
717 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
719 that is, there is a loop index "x" that determines the scalar value
720 of the variable during the loop execution. During the first
721 iteration, the value is that of the initial condition INIT, while
722 during the subsequent iterations, it is the sum of the initial
723 condition with the sum of all the values of EXPR from the initial
724 iteration to the before last considered iteration.
726 For the second case, the semantics of the SSA program is:
728 | a (x) = init, if x = 0;
729 | expr (x - 1), otherwise.
731 The second case corresponds to the PEELED_CHREC, whose syntax is
732 close to the syntax of a loop-phi-node:
734 | phi (init, expr) vs. (init, expr)_x
736 The proof of the translation algorithm for the first case is a
737 proof by structural induction based on the degree of EXPR.
740 When EXPR is a constant with respect to the analyzed loop, or in
741 other words when EXPR is a polynomial of degree 0, the evolution of
742 the variable A in the loop is an affine function with an initial
743 condition INIT, and a step EXPR. In order to show this, we start
744 from the semantics of the SSA representation:
746 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
748 and since "expr (j)" is a constant with respect to "j",
750 f (x) = init + x * expr
752 Finally, based on the semantics of the pure sum chrecs, by
753 identification we get the corresponding chrecs syntax:
755 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
756 f (x) -> {init, +, expr}_x
759 Suppose that EXPR is a polynomial of degree N with respect to the
760 analyzed loop_x for which we have already determined that it is
761 written under the chrecs syntax:
763 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
765 We start from the semantics of the SSA program:
767 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
769 | f (x) = init + \sum_{j = 0}^{x - 1}
770 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
772 | f (x) = init + \sum_{j = 0}^{x - 1}
773 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
775 | f (x) = init + \sum_{k = 0}^{n - 1}
776 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
778 | f (x) = init + \sum_{k = 0}^{n - 1}
779 | (b_k * \binom{x}{k + 1})
781 | f (x) = init + b_0 * \binom{x}{1} + ...
782 | + b_{n-1} * \binom{x}{n}
784 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
785 | + b_{n-1} * \binom{x}{n}
788 And finally from the definition of the chrecs syntax, we identify:
789 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
791 This shows the mechanism that stands behind the add_to_evolution
792 function. An important point is that the use of symbolic
793 parameters avoids the need of an analysis schedule.
800 | a = phi (inita, a + 2 + b)
801 | b = phi (initb, b + 1)
804 When analyzing "a", the algorithm keeps "b" symbolically:
806 | a -> {inita, +, 2 + b}_1
808 Then, after instantiation, the analyzer ends on the evolution:
810 | a -> {inita, +, 2 + initb, +, 1}_1
815 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
816 tree to_add, gimple *at_stmt)
818 tree type = chrec_type (to_add);
819 tree res = NULL_TREE;
821 if (to_add == NULL_TREE)
824 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
825 instantiated at this point. */
826 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
827 /* This should not happen. */
828 return chrec_dont_know;
830 if (dump_file && (dump_flags & TDF_SCEV))
832 fprintf (dump_file, "(add_to_evolution \n");
833 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
834 fprintf (dump_file, " (chrec_before = ");
835 print_generic_expr (dump_file, chrec_before, 0);
836 fprintf (dump_file, ")\n (to_add = ");
837 print_generic_expr (dump_file, to_add, 0);
838 fprintf (dump_file, ")\n");
841 if (code == MINUS_EXPR)
842 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
843 ? build_real (type, dconstm1)
844 : build_int_cst_type (type, -1));
846 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
848 if (dump_file && (dump_flags & TDF_SCEV))
850 fprintf (dump_file, " (res = ");
851 print_generic_expr (dump_file, res, 0);
852 fprintf (dump_file, "))\n");
860 /* This section selects the loops that will be good candidates for the
861 scalar evolution analysis. For the moment, greedily select all the
862 loop nests we could analyze. */
864 /* For a loop with a single exit edge, return the COND_EXPR that
865 guards the exit edge. If the expression is too difficult to
866 analyze, then give up. */
869 get_loop_exit_condition (const struct loop *loop)
872 edge exit_edge = single_exit (loop);
874 if (dump_file && (dump_flags & TDF_SCEV))
875 fprintf (dump_file, "(get_loop_exit_condition \n ");
881 stmt = last_stmt (exit_edge->src);
882 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
886 if (dump_file && (dump_flags & TDF_SCEV))
888 print_gimple_stmt (dump_file, res, 0, 0);
889 fprintf (dump_file, ")\n");
896 /* Depth first search algorithm. */
905 static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *,
908 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
909 Return true if the strongly connected component has been found. */
912 follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt,
913 tree type, tree rhs0, enum tree_code code, tree rhs1,
914 gphi *halting_phi, tree *evolution_of_loop,
917 t_bool res = t_false;
922 case POINTER_PLUS_EXPR:
924 if (TREE_CODE (rhs0) == SSA_NAME)
926 if (TREE_CODE (rhs1) == SSA_NAME)
928 /* Match an assignment under the form:
931 /* We want only assignments of form "name + name" contribute to
932 LIMIT, as the other cases do not necessarily contribute to
933 the complexity of the expression. */
936 evol = *evolution_of_loop;
937 evol = add_to_evolution
939 chrec_convert (type, evol, at_stmt),
940 code, rhs1, at_stmt);
941 res = follow_ssa_edge
942 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
944 *evolution_of_loop = evol;
945 else if (res == t_false)
947 *evolution_of_loop = add_to_evolution
949 chrec_convert (type, *evolution_of_loop, at_stmt),
950 code, rhs0, at_stmt);
951 res = follow_ssa_edge
952 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
953 evolution_of_loop, limit);
956 else if (res == t_dont_know)
957 *evolution_of_loop = chrec_dont_know;
960 else if (res == t_dont_know)
961 *evolution_of_loop = chrec_dont_know;
966 /* Match an assignment under the form:
968 *evolution_of_loop = add_to_evolution
969 (loop->num, chrec_convert (type, *evolution_of_loop,
971 code, rhs1, at_stmt);
972 res = follow_ssa_edge
973 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
974 evolution_of_loop, limit);
977 else if (res == t_dont_know)
978 *evolution_of_loop = chrec_dont_know;
982 else if (TREE_CODE (rhs1) == SSA_NAME)
984 /* Match an assignment under the form:
986 *evolution_of_loop = add_to_evolution
987 (loop->num, chrec_convert (type, *evolution_of_loop,
989 code, rhs0, at_stmt);
990 res = follow_ssa_edge
991 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
992 evolution_of_loop, limit);
995 else if (res == t_dont_know)
996 *evolution_of_loop = chrec_dont_know;
1000 /* Otherwise, match an assignment under the form:
1002 /* And there is nothing to do. */
1007 /* This case is under the form "opnd0 = rhs0 - rhs1". */
1008 if (TREE_CODE (rhs0) == SSA_NAME)
1010 /* Match an assignment under the form:
1013 /* We want only assignments of form "name - name" contribute to
1014 LIMIT, as the other cases do not necessarily contribute to
1015 the complexity of the expression. */
1016 if (TREE_CODE (rhs1) == SSA_NAME)
1019 *evolution_of_loop = add_to_evolution
1020 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1021 MINUS_EXPR, rhs1, at_stmt);
1022 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1023 evolution_of_loop, limit);
1026 else if (res == t_dont_know)
1027 *evolution_of_loop = chrec_dont_know;
1030 /* Otherwise, match an assignment under the form:
1032 /* And there is nothing to do. */
1043 /* Follow the ssa edge into the expression EXPR.
1044 Return true if the strongly connected component has been found. */
1047 follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr,
1048 gphi *halting_phi, tree *evolution_of_loop,
1051 enum tree_code code = TREE_CODE (expr);
1052 tree type = TREE_TYPE (expr), rhs0, rhs1;
1055 /* The EXPR is one of the following cases:
1059 - a POINTER_PLUS_EXPR,
1062 - other cases are not yet handled. */
1067 /* This assignment is under the form "a_1 = (cast) rhs. */
1068 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1069 halting_phi, evolution_of_loop, limit);
1070 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1074 /* This assignment is under the form "a_1 = 7". */
1079 /* This assignment is under the form: "a_1 = b_2". */
1080 res = follow_ssa_edge
1081 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1084 case POINTER_PLUS_EXPR:
1087 /* This case is under the form "rhs0 +- rhs1". */
1088 rhs0 = TREE_OPERAND (expr, 0);
1089 rhs1 = TREE_OPERAND (expr, 1);
1090 type = TREE_TYPE (rhs0);
1091 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1092 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1093 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1094 halting_phi, evolution_of_loop, limit);
1098 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1099 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1101 expr = TREE_OPERAND (expr, 0);
1102 rhs0 = TREE_OPERAND (expr, 0);
1103 rhs1 = TREE_OPERAND (expr, 1);
1104 type = TREE_TYPE (rhs0);
1105 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1106 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1107 res = follow_ssa_edge_binary (loop, at_stmt, type,
1108 rhs0, POINTER_PLUS_EXPR, rhs1,
1109 halting_phi, evolution_of_loop, limit);
1116 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1117 It must be handled as a copy assignment of the form a_1 = a_2. */
1118 rhs0 = ASSERT_EXPR_VAR (expr);
1119 if (TREE_CODE (rhs0) == SSA_NAME)
1120 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1121 halting_phi, evolution_of_loop, limit);
1134 /* Follow the ssa edge into the right hand side of an assignment STMT.
1135 Return true if the strongly connected component has been found. */
1138 follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt,
1139 gphi *halting_phi, tree *evolution_of_loop,
1142 enum tree_code code = gimple_assign_rhs_code (stmt);
1143 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1149 /* This assignment is under the form "a_1 = (cast) rhs. */
1150 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1151 halting_phi, evolution_of_loop, limit);
1152 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1155 case POINTER_PLUS_EXPR:
1158 rhs1 = gimple_assign_rhs1 (stmt);
1159 rhs2 = gimple_assign_rhs2 (stmt);
1160 type = TREE_TYPE (rhs1);
1161 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1162 halting_phi, evolution_of_loop, limit);
1166 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1167 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1168 halting_phi, evolution_of_loop, limit);
1177 /* Checks whether the I-th argument of a PHI comes from a backedge. */
1180 backedge_phi_arg_p (gphi *phi, int i)
1182 const_edge e = gimple_phi_arg_edge (phi, i);
1184 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1185 about updating it anywhere, and this should work as well most of the
1187 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1193 /* Helper function for one branch of the condition-phi-node. Return
1194 true if the strongly connected component has been found following
1197 static inline t_bool
1198 follow_ssa_edge_in_condition_phi_branch (int i,
1200 gphi *condition_phi,
1202 tree *evolution_of_branch,
1203 tree init_cond, int limit)
1205 tree branch = PHI_ARG_DEF (condition_phi, i);
1206 *evolution_of_branch = chrec_dont_know;
1208 /* Do not follow back edges (they must belong to an irreducible loop, which
1209 we really do not want to worry about). */
1210 if (backedge_phi_arg_p (condition_phi, i))
1213 if (TREE_CODE (branch) == SSA_NAME)
1215 *evolution_of_branch = init_cond;
1216 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1217 evolution_of_branch, limit);
1220 /* This case occurs when one of the condition branches sets
1221 the variable to a constant: i.e. a phi-node like
1222 "a_2 = PHI <a_7(5), 2(6)>;".
1224 FIXME: This case have to be refined correctly:
1225 in some cases it is possible to say something better than
1226 chrec_dont_know, for example using a wrap-around notation. */
1230 /* This function merges the branches of a condition-phi-node in a
1234 follow_ssa_edge_in_condition_phi (struct loop *loop,
1235 gphi *condition_phi,
1237 tree *evolution_of_loop, int limit)
1240 tree init = *evolution_of_loop;
1241 tree evolution_of_branch;
1242 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1244 &evolution_of_branch,
1246 if (res == t_false || res == t_dont_know)
1249 *evolution_of_loop = evolution_of_branch;
1251 n = gimple_phi_num_args (condition_phi);
1252 for (i = 1; i < n; i++)
1254 /* Quickly give up when the evolution of one of the branches is
1256 if (*evolution_of_loop == chrec_dont_know)
1259 /* Increase the limit by the PHI argument number to avoid exponential
1260 time and memory complexity. */
1261 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1263 &evolution_of_branch,
1265 if (res == t_false || res == t_dont_know)
1268 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1269 evolution_of_branch);
1275 /* Follow an SSA edge in an inner loop. It computes the overall
1276 effect of the loop, and following the symbolic initial conditions,
1277 it follows the edges in the parent loop. The inner loop is
1278 considered as a single statement. */
1281 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1282 gphi *loop_phi_node,
1284 tree *evolution_of_loop, int limit)
1286 struct loop *loop = loop_containing_stmt (loop_phi_node);
1287 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1289 /* Sometimes, the inner loop is too difficult to analyze, and the
1290 result of the analysis is a symbolic parameter. */
1291 if (ev == PHI_RESULT (loop_phi_node))
1293 t_bool res = t_false;
1294 int i, n = gimple_phi_num_args (loop_phi_node);
1296 for (i = 0; i < n; i++)
1298 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1301 /* Follow the edges that exit the inner loop. */
1302 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1303 if (!flow_bb_inside_loop_p (loop, bb))
1304 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1306 evolution_of_loop, limit);
1311 /* If the path crosses this loop-phi, give up. */
1313 *evolution_of_loop = chrec_dont_know;
1318 /* Otherwise, compute the overall effect of the inner loop. */
1319 ev = compute_overall_effect_of_inner_loop (loop, ev);
1320 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1321 evolution_of_loop, limit);
1324 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1325 path that is analyzed on the return walk. */
1328 follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi,
1329 tree *evolution_of_loop, int limit)
1331 struct loop *def_loop;
1333 if (gimple_nop_p (def))
1336 /* Give up if the path is longer than the MAX that we allow. */
1337 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1340 def_loop = loop_containing_stmt (def);
1342 switch (gimple_code (def))
1345 if (!loop_phi_node_p (def))
1346 /* DEF is a condition-phi-node. Follow the branches, and
1347 record their evolutions. Finally, merge the collected
1348 information and set the approximation to the main
1350 return follow_ssa_edge_in_condition_phi
1351 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1354 /* When the analyzed phi is the halting_phi, the
1355 depth-first search is over: we have found a path from
1356 the halting_phi to itself in the loop. */
1357 if (def == halting_phi)
1360 /* Otherwise, the evolution of the HALTING_PHI depends
1361 on the evolution of another loop-phi-node, i.e. the
1362 evolution function is a higher degree polynomial. */
1363 if (def_loop == loop)
1367 if (flow_loop_nested_p (loop, def_loop))
1368 return follow_ssa_edge_inner_loop_phi
1369 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1376 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1377 evolution_of_loop, limit);
1380 /* At this level of abstraction, the program is just a set
1381 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1382 other node to be handled. */
1388 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1389 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1391 # i_17 = PHI <i_13(5), 0(3)>
1392 # _20 = PHI <_5(5), start_4(D)(3)>
1395 _5 = start_4(D) + i_13;
1397 Though variable _20 appears as a PEELED_CHREC in the form of
1398 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1403 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1405 aff_tree aff1, aff2;
1406 tree ev, left, right, type, step_val;
1407 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1409 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1410 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1411 return chrec_dont_know;
1413 left = CHREC_LEFT (ev);
1414 right = CHREC_RIGHT (ev);
1415 type = TREE_TYPE (left);
1416 step_val = chrec_fold_plus (type, init_cond, right);
1418 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1419 if "left" equals to "init + right". */
1420 if (operand_equal_p (left, step_val, 0))
1422 if (dump_file && (dump_flags & TDF_SCEV))
1423 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1425 return build_polynomial_chrec (loop->num, init_cond, right);
1428 /* Try harder to check if they are equal. */
1429 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1430 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1431 free_affine_expand_cache (&peeled_chrec_map);
1432 aff_combination_scale (&aff2, -1);
1433 aff_combination_add (&aff1, &aff2);
1435 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1436 if "left" equals to "init + right". */
1437 if (aff_combination_zero_p (&aff1))
1439 if (dump_file && (dump_flags & TDF_SCEV))
1440 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1442 return build_polynomial_chrec (loop->num, init_cond, right);
1444 return chrec_dont_know;
1447 /* Given a LOOP_PHI_NODE, this function determines the evolution
1448 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1451 analyze_evolution_in_loop (gphi *loop_phi_node,
1454 int i, n = gimple_phi_num_args (loop_phi_node);
1455 tree evolution_function = chrec_not_analyzed_yet;
1456 struct loop *loop = loop_containing_stmt (loop_phi_node);
1458 static bool simplify_peeled_chrec_p = true;
1460 if (dump_file && (dump_flags & TDF_SCEV))
1462 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1463 fprintf (dump_file, " (loop_phi_node = ");
1464 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1465 fprintf (dump_file, ")\n");
1468 for (i = 0; i < n; i++)
1470 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1475 /* Select the edges that enter the loop body. */
1476 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1477 if (!flow_bb_inside_loop_p (loop, bb))
1480 if (TREE_CODE (arg) == SSA_NAME)
1484 ssa_chain = SSA_NAME_DEF_STMT (arg);
1486 /* Pass in the initial condition to the follow edge function. */
1488 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1490 /* If ev_fn has no evolution in the inner loop, and the
1491 init_cond is not equal to ev_fn, then we have an
1492 ambiguity between two possible values, as we cannot know
1493 the number of iterations at this point. */
1494 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1495 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1496 && !operand_equal_p (init_cond, ev_fn, 0))
1497 ev_fn = chrec_dont_know;
1502 /* When it is impossible to go back on the same
1503 loop_phi_node by following the ssa edges, the
1504 evolution is represented by a peeled chrec, i.e. the
1505 first iteration, EV_FN has the value INIT_COND, then
1506 all the other iterations it has the value of ARG.
1507 For the moment, PEELED_CHREC nodes are not built. */
1510 ev_fn = chrec_dont_know;
1511 /* Try to recognize POLYNOMIAL_CHREC which appears in
1512 the form of PEELED_CHREC, but guard the process with
1513 a bool variable to keep the analyzer from infinite
1514 recurrence for real PEELED_RECs. */
1515 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1517 simplify_peeled_chrec_p = false;
1518 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1519 simplify_peeled_chrec_p = true;
1523 /* When there are multiple back edges of the loop (which in fact never
1524 happens currently, but nevertheless), merge their evolutions. */
1525 evolution_function = chrec_merge (evolution_function, ev_fn);
1528 if (dump_file && (dump_flags & TDF_SCEV))
1530 fprintf (dump_file, " (evolution_function = ");
1531 print_generic_expr (dump_file, evolution_function, 0);
1532 fprintf (dump_file, "))\n");
1535 return evolution_function;
1538 /* Given a loop-phi-node, return the initial conditions of the
1539 variable on entry of the loop. When the CCP has propagated
1540 constants into the loop-phi-node, the initial condition is
1541 instantiated, otherwise the initial condition is kept symbolic.
1542 This analyzer does not analyze the evolution outside the current
1543 loop, and leaves this task to the on-demand tree reconstructor. */
1546 analyze_initial_condition (gphi *loop_phi_node)
1549 tree init_cond = chrec_not_analyzed_yet;
1550 struct loop *loop = loop_containing_stmt (loop_phi_node);
1552 if (dump_file && (dump_flags & TDF_SCEV))
1554 fprintf (dump_file, "(analyze_initial_condition \n");
1555 fprintf (dump_file, " (loop_phi_node = \n");
1556 print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1557 fprintf (dump_file, ")\n");
1560 n = gimple_phi_num_args (loop_phi_node);
1561 for (i = 0; i < n; i++)
1563 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1564 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1566 /* When the branch is oriented to the loop's body, it does
1567 not contribute to the initial condition. */
1568 if (flow_bb_inside_loop_p (loop, bb))
1571 if (init_cond == chrec_not_analyzed_yet)
1577 if (TREE_CODE (branch) == SSA_NAME)
1579 init_cond = chrec_dont_know;
1583 init_cond = chrec_merge (init_cond, branch);
1586 /* Ooops -- a loop without an entry??? */
1587 if (init_cond == chrec_not_analyzed_yet)
1588 init_cond = chrec_dont_know;
1590 /* During early loop unrolling we do not have fully constant propagated IL.
1591 Handle degenerate PHIs here to not miss important unrollings. */
1592 if (TREE_CODE (init_cond) == SSA_NAME)
1594 gimple *def = SSA_NAME_DEF_STMT (init_cond);
1595 if (gphi *phi = dyn_cast <gphi *> (def))
1597 tree res = degenerate_phi_result (phi);
1598 if (res != NULL_TREE
1599 /* Only allow invariants here, otherwise we may break
1600 loop-closed SSA form. */
1601 && is_gimple_min_invariant (res))
1606 if (dump_file && (dump_flags & TDF_SCEV))
1608 fprintf (dump_file, " (init_cond = ");
1609 print_generic_expr (dump_file, init_cond, 0);
1610 fprintf (dump_file, "))\n");
1616 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1619 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1622 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1625 if (phi_loop != loop)
1627 struct loop *subloop;
1628 tree evolution_fn = analyze_scalar_evolution
1629 (phi_loop, PHI_RESULT (loop_phi_node));
1631 /* Dive one level deeper. */
1632 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1634 /* Interpret the subloop. */
1635 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1639 /* Otherwise really interpret the loop phi. */
1640 init_cond = analyze_initial_condition (loop_phi_node);
1641 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1643 /* Verify we maintained the correct initial condition throughout
1644 possible conversions in the SSA chain. */
1645 if (res != chrec_dont_know)
1647 tree new_init = res;
1648 if (CONVERT_EXPR_P (res)
1649 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1650 new_init = fold_convert (TREE_TYPE (res),
1651 CHREC_LEFT (TREE_OPERAND (res, 0)));
1652 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1653 new_init = CHREC_LEFT (res);
1654 STRIP_USELESS_TYPE_CONVERSION (new_init);
1655 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1656 || !operand_equal_p (init_cond, new_init, 0))
1657 return chrec_dont_know;
1663 /* This function merges the branches of a condition-phi-node,
1664 contained in the outermost loop, and whose arguments are already
1668 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1670 int i, n = gimple_phi_num_args (condition_phi);
1671 tree res = chrec_not_analyzed_yet;
1673 for (i = 0; i < n; i++)
1677 if (backedge_phi_arg_p (condition_phi, i))
1679 res = chrec_dont_know;
1683 branch_chrec = analyze_scalar_evolution
1684 (loop, PHI_ARG_DEF (condition_phi, i));
1686 res = chrec_merge (res, branch_chrec);
1692 /* Interpret the operation RHS1 OP RHS2. If we didn't
1693 analyze this node before, follow the definitions until ending
1694 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1695 return path, this function propagates evolutions (ala constant copy
1696 propagation). OPND1 is not a GIMPLE expression because we could
1697 analyze the effect of an inner loop: see interpret_loop_phi. */
1700 interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
1701 tree type, tree rhs1, enum tree_code code, tree rhs2)
1703 tree res, chrec1, chrec2;
1706 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1708 if (is_gimple_min_invariant (rhs1))
1709 return chrec_convert (type, rhs1, at_stmt);
1711 if (code == SSA_NAME)
1712 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1715 if (code == ASSERT_EXPR)
1717 rhs1 = ASSERT_EXPR_VAR (rhs1);
1718 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1726 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1727 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1730 HOST_WIDE_INT bitsize, bitpos;
1737 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1738 &bitsize, &bitpos, &offset,
1739 &mode, &unsignedp, &volatilep, false);
1741 if (TREE_CODE (base) == MEM_REF)
1743 rhs2 = TREE_OPERAND (base, 1);
1744 rhs1 = TREE_OPERAND (base, 0);
1746 chrec1 = analyze_scalar_evolution (loop, rhs1);
1747 chrec2 = analyze_scalar_evolution (loop, rhs2);
1748 chrec1 = chrec_convert (type, chrec1, at_stmt);
1749 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1750 chrec1 = instantiate_parameters (loop, chrec1);
1751 chrec2 = instantiate_parameters (loop, chrec2);
1752 res = chrec_fold_plus (type, chrec1, chrec2);
1756 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1757 chrec1 = chrec_convert (type, chrec1, at_stmt);
1761 if (offset != NULL_TREE)
1763 chrec2 = analyze_scalar_evolution (loop, offset);
1764 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1765 chrec2 = instantiate_parameters (loop, chrec2);
1766 res = chrec_fold_plus (type, res, chrec2);
1771 gcc_assert ((bitpos % BITS_PER_UNIT) == 0);
1773 unitpos = size_int (bitpos / BITS_PER_UNIT);
1774 chrec3 = analyze_scalar_evolution (loop, unitpos);
1775 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1776 chrec3 = instantiate_parameters (loop, chrec3);
1777 res = chrec_fold_plus (type, res, chrec3);
1781 res = chrec_dont_know;
1784 case POINTER_PLUS_EXPR:
1785 chrec1 = analyze_scalar_evolution (loop, rhs1);
1786 chrec2 = analyze_scalar_evolution (loop, rhs2);
1787 chrec1 = chrec_convert (type, chrec1, at_stmt);
1788 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1789 chrec1 = instantiate_parameters (loop, chrec1);
1790 chrec2 = instantiate_parameters (loop, chrec2);
1791 res = chrec_fold_plus (type, chrec1, chrec2);
1795 chrec1 = analyze_scalar_evolution (loop, rhs1);
1796 chrec2 = analyze_scalar_evolution (loop, rhs2);
1797 chrec1 = chrec_convert (type, chrec1, at_stmt);
1798 chrec2 = chrec_convert (type, chrec2, at_stmt);
1799 chrec1 = instantiate_parameters (loop, chrec1);
1800 chrec2 = instantiate_parameters (loop, chrec2);
1801 res = chrec_fold_plus (type, chrec1, chrec2);
1805 chrec1 = analyze_scalar_evolution (loop, rhs1);
1806 chrec2 = analyze_scalar_evolution (loop, rhs2);
1807 chrec1 = chrec_convert (type, chrec1, at_stmt);
1808 chrec2 = chrec_convert (type, chrec2, at_stmt);
1809 chrec1 = instantiate_parameters (loop, chrec1);
1810 chrec2 = instantiate_parameters (loop, chrec2);
1811 res = chrec_fold_minus (type, chrec1, chrec2);
1815 chrec1 = analyze_scalar_evolution (loop, rhs1);
1816 chrec1 = chrec_convert (type, chrec1, at_stmt);
1817 /* TYPE may be integer, real or complex, so use fold_convert. */
1818 chrec1 = instantiate_parameters (loop, chrec1);
1819 res = chrec_fold_multiply (type, chrec1,
1820 fold_convert (type, integer_minus_one_node));
1824 /* Handle ~X as -1 - X. */
1825 chrec1 = analyze_scalar_evolution (loop, rhs1);
1826 chrec1 = chrec_convert (type, chrec1, at_stmt);
1827 chrec1 = instantiate_parameters (loop, chrec1);
1828 res = chrec_fold_minus (type,
1829 fold_convert (type, integer_minus_one_node),
1834 chrec1 = analyze_scalar_evolution (loop, rhs1);
1835 chrec2 = analyze_scalar_evolution (loop, rhs2);
1836 chrec1 = chrec_convert (type, chrec1, at_stmt);
1837 chrec2 = chrec_convert (type, chrec2, at_stmt);
1838 chrec1 = instantiate_parameters (loop, chrec1);
1839 chrec2 = instantiate_parameters (loop, chrec2);
1840 res = chrec_fold_multiply (type, chrec1, chrec2);
1844 /* Handle A<<B as A * (1<<B). */
1845 chrec1 = analyze_scalar_evolution (loop, rhs1);
1846 chrec2 = analyze_scalar_evolution (loop, rhs2);
1847 chrec1 = chrec_convert (type, chrec1, at_stmt);
1848 chrec1 = instantiate_parameters (loop, chrec1);
1849 chrec2 = instantiate_parameters (loop, chrec2);
1851 chrec2 = fold_build2 (LSHIFT_EXPR, type,
1852 build_int_cst (TREE_TYPE (rhs1), 1),
1854 res = chrec_fold_multiply (type, chrec1, chrec2);
1858 /* In case we have a truncation of a widened operation that in
1859 the truncated type has undefined overflow behavior analyze
1860 the operation done in an unsigned type of the same precision
1861 as the final truncation. We cannot derive a scalar evolution
1862 for the widened operation but for the truncated result. */
1863 if (TREE_CODE (type) == INTEGER_TYPE
1864 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1865 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1866 && TYPE_OVERFLOW_UNDEFINED (type)
1867 && TREE_CODE (rhs1) == SSA_NAME
1868 && (def = SSA_NAME_DEF_STMT (rhs1))
1869 && is_gimple_assign (def)
1870 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1871 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1873 tree utype = unsigned_type_for (type);
1874 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1875 gimple_assign_rhs1 (def),
1876 gimple_assign_rhs_code (def),
1877 gimple_assign_rhs2 (def));
1880 chrec1 = analyze_scalar_evolution (loop, rhs1);
1881 res = chrec_convert (type, chrec1, at_stmt);
1885 res = chrec_dont_know;
1892 /* Interpret the expression EXPR. */
1895 interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
1897 enum tree_code code;
1898 tree type = TREE_TYPE (expr), op0, op1;
1900 if (automatically_generated_chrec_p (expr))
1903 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1904 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1905 return chrec_dont_know;
1907 extract_ops_from_tree (expr, &code, &op0, &op1);
1909 return interpret_rhs_expr (loop, at_stmt, type,
1913 /* Interpret the rhs of the assignment STMT. */
1916 interpret_gimple_assign (struct loop *loop, gimple *stmt)
1918 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1919 enum tree_code code = gimple_assign_rhs_code (stmt);
1921 return interpret_rhs_expr (loop, stmt, type,
1922 gimple_assign_rhs1 (stmt), code,
1923 gimple_assign_rhs2 (stmt));
1928 /* This section contains all the entry points:
1929 - number_of_iterations_in_loop,
1930 - analyze_scalar_evolution,
1931 - instantiate_parameters.
1934 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1935 common ancestor of DEF_LOOP and USE_LOOP. */
1938 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1939 struct loop *def_loop,
1945 if (def_loop == wrto_loop)
1948 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1949 res = compute_overall_effect_of_inner_loop (def_loop, ev);
1951 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
1954 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1957 /* Helper recursive function. */
1960 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1962 tree type = TREE_TYPE (var);
1965 struct loop *def_loop;
1967 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1968 return chrec_dont_know;
1970 if (TREE_CODE (var) != SSA_NAME)
1971 return interpret_expr (loop, NULL, var);
1973 def = SSA_NAME_DEF_STMT (var);
1974 bb = gimple_bb (def);
1975 def_loop = bb ? bb->loop_father : NULL;
1978 || !flow_bb_inside_loop_p (loop, bb))
1980 /* Keep the symbolic form. */
1985 if (res != chrec_not_analyzed_yet)
1987 if (loop != bb->loop_father)
1988 res = compute_scalar_evolution_in_loop
1989 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1994 if (loop != def_loop)
1996 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1997 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
2002 switch (gimple_code (def))
2005 res = interpret_gimple_assign (loop, def);
2009 if (loop_phi_node_p (def))
2010 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2012 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2016 res = chrec_dont_know;
2022 /* Keep the symbolic form. */
2023 if (res == chrec_dont_know)
2026 if (loop == def_loop)
2027 set_scalar_evolution (block_before_loop (loop), var, res);
2032 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2033 LOOP. LOOP is the loop in which the variable is used.
2035 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2036 pointer to the statement that uses this variable, in order to
2037 determine the evolution function of the variable, use the following
2040 loop_p loop = loop_containing_stmt (stmt);
2041 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2042 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2046 analyze_scalar_evolution (struct loop *loop, tree var)
2050 if (dump_file && (dump_flags & TDF_SCEV))
2052 fprintf (dump_file, "(analyze_scalar_evolution \n");
2053 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2054 fprintf (dump_file, " (scalar = ");
2055 print_generic_expr (dump_file, var, 0);
2056 fprintf (dump_file, ")\n");
2059 res = get_scalar_evolution (block_before_loop (loop), var);
2060 res = analyze_scalar_evolution_1 (loop, var, res);
2062 if (dump_file && (dump_flags & TDF_SCEV))
2063 fprintf (dump_file, ")\n");
2068 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2071 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2073 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2076 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2077 WRTO_LOOP (which should be a superloop of USE_LOOP)
2079 FOLDED_CASTS is set to true if resolve_mixers used
2080 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2081 at the moment in order to keep things simple).
2083 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2086 for (i = 0; i < 100; i++) -- loop 1
2088 for (j = 0; j < 100; j++) -- loop 2
2095 for (t = 0; t < 100; t++) -- loop 3
2102 Both k1 and k2 are invariants in loop3, thus
2103 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2104 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2106 As they are invariant, it does not matter whether we consider their
2107 usage in loop 3 or loop 2, hence
2108 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2109 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2110 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2111 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2113 Similarly for their evolutions with respect to loop 1. The values of K2
2114 in the use in loop 2 vary independently on loop 1, thus we cannot express
2115 the evolution with respect to loop 1:
2116 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2117 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2118 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2119 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2121 The value of k2 in the use in loop 1 is known, though:
2122 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2123 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2127 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2128 tree version, bool *folded_casts)
2131 tree ev = version, tmp;
2133 /* We cannot just do
2135 tmp = analyze_scalar_evolution (use_loop, version);
2136 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2138 as resolve_mixers would query the scalar evolution with respect to
2139 wrto_loop. For example, in the situation described in the function
2140 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2143 analyze_scalar_evolution (use_loop, version) = k2
2145 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2146 k2 in loop 1 is 100, which is a wrong result, since we are interested
2147 in the value in loop 3.
2149 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2150 each time checking that there is no evolution in the inner loop. */
2153 *folded_casts = false;
2156 tmp = analyze_scalar_evolution (use_loop, ev);
2157 ev = resolve_mixers (use_loop, tmp, folded_casts);
2159 if (use_loop == wrto_loop)
2162 /* If the value of the use changes in the inner loop, we cannot express
2163 its value in the outer loop (we might try to return interval chrec,
2164 but we do not have a user for it anyway) */
2165 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2167 return chrec_dont_know;
2169 use_loop = loop_outer (use_loop);
2174 /* Hashtable helpers for a temporary hash-table used when
2175 instantiating a CHREC or resolving mixers. For this use
2176 instantiated_below is always the same. */
2178 struct instantiate_cache_type
2181 vec<scev_info_str> entries;
2183 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2184 ~instantiate_cache_type ();
2185 tree get (unsigned slot) { return entries[slot].chrec; }
2186 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2189 instantiate_cache_type::~instantiate_cache_type ()
2198 /* Cache to avoid infinite recursion when instantiating an SSA name.
2199 Live during the outermost instantiate_scev or resolve_mixers call. */
2200 static instantiate_cache_type *global_cache;
2202 /* Computes a hash function for database element ELT. */
2204 static inline hashval_t
2205 hash_idx_scev_info (const void *elt_)
2207 unsigned idx = ((size_t) elt_) - 2;
2208 return scev_info_hasher::hash (&global_cache->entries[idx]);
2211 /* Compares database elements E1 and E2. */
2214 eq_idx_scev_info (const void *e1, const void *e2)
2216 unsigned idx1 = ((size_t) e1) - 2;
2217 return scev_info_hasher::equal (&global_cache->entries[idx1],
2218 (const scev_info_str *) e2);
2221 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2224 get_instantiated_value_entry (instantiate_cache_type &cache,
2225 tree name, basic_block instantiate_below)
2229 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2230 cache.entries.create (10);
2234 e.name_version = SSA_NAME_VERSION (name);
2235 e.instantiated_below = instantiate_below->index;
2236 void **slot = htab_find_slot_with_hash (cache.map, &e,
2237 scev_info_hasher::hash (&e), INSERT);
2240 e.chrec = chrec_not_analyzed_yet;
2241 *slot = (void *)(size_t)(cache.entries.length () + 2);
2242 cache.entries.safe_push (e);
2245 return ((size_t)*slot) - 2;
2249 /* Return the closed_loop_phi node for VAR. If there is none, return
2253 loop_closed_phi_def (tree var)
2260 if (var == NULL_TREE
2261 || TREE_CODE (var) != SSA_NAME)
2264 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2265 exit = single_exit (loop);
2269 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2272 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2273 return PHI_RESULT (phi);
2279 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2282 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2283 and EVOLUTION_LOOP, that were left under a symbolic form.
2285 CHREC is an SSA_NAME to be instantiated.
2287 CACHE is the cache of already instantiated values.
2289 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2290 conversions that may wrap in signed/pointer type are folded, as long
2291 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2292 then we don't do such fold.
2294 SIZE_EXPR is used for computing the size of the expression to be
2295 instantiated, and to stop if it exceeds some limit. */
2298 instantiate_scev_name (basic_block instantiate_below,
2299 struct loop *evolution_loop, struct loop *inner_loop,
2301 bool *fold_conversions,
2305 struct loop *def_loop;
2306 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2308 /* A parameter (or loop invariant and we do not want to include
2309 evolutions in outer loops), nothing to do. */
2311 || loop_depth (def_bb->loop_father) == 0
2312 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2315 /* We cache the value of instantiated variable to avoid exponential
2316 time complexity due to reevaluations. We also store the convenient
2317 value in the cache in order to prevent infinite recursion -- we do
2318 not want to instantiate the SSA_NAME if it is in a mixer
2319 structure. This is used for avoiding the instantiation of
2320 recursively defined functions, such as:
2322 | a_2 -> {0, +, 1, +, a_2}_1 */
2324 unsigned si = get_instantiated_value_entry (*global_cache,
2325 chrec, instantiate_below);
2326 if (global_cache->get (si) != chrec_not_analyzed_yet)
2327 return global_cache->get (si);
2329 /* On recursion return chrec_dont_know. */
2330 global_cache->set (si, chrec_dont_know);
2332 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2334 /* If the analysis yields a parametric chrec, instantiate the
2336 res = analyze_scalar_evolution (def_loop, chrec);
2338 /* Don't instantiate default definitions. */
2339 if (TREE_CODE (res) == SSA_NAME
2340 && SSA_NAME_IS_DEFAULT_DEF (res))
2343 /* Don't instantiate loop-closed-ssa phi nodes. */
2344 else if (TREE_CODE (res) == SSA_NAME
2345 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2346 > loop_depth (def_loop))
2349 res = loop_closed_phi_def (chrec);
2353 /* When there is no loop_closed_phi_def, it means that the
2354 variable is not used after the loop: try to still compute the
2355 value of the variable when exiting the loop. */
2356 if (res == NULL_TREE)
2358 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2359 res = analyze_scalar_evolution (loop, chrec);
2360 res = compute_overall_effect_of_inner_loop (loop, res);
2361 res = instantiate_scev_r (instantiate_below, evolution_loop,
2363 fold_conversions, size_expr);
2365 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2366 gimple_bb (SSA_NAME_DEF_STMT (res))))
2367 res = chrec_dont_know;
2370 else if (res != chrec_dont_know)
2373 && def_bb->loop_father != inner_loop
2374 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2375 /* ??? We could try to compute the overall effect of the loop here. */
2376 res = chrec_dont_know;
2378 res = instantiate_scev_r (instantiate_below, evolution_loop,
2380 fold_conversions, size_expr);
2383 /* Store the correct value to the cache. */
2384 global_cache->set (si, res);
2388 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2389 and EVOLUTION_LOOP, that were left under a symbolic form.
2391 CHREC is a polynomial chain of recurrence to be instantiated.
2393 CACHE is the cache of already instantiated values.
2395 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2396 conversions that may wrap in signed/pointer type are folded, as long
2397 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2398 then we don't do such fold.
2400 SIZE_EXPR is used for computing the size of the expression to be
2401 instantiated, and to stop if it exceeds some limit. */
2404 instantiate_scev_poly (basic_block instantiate_below,
2405 struct loop *evolution_loop, struct loop *,
2406 tree chrec, bool *fold_conversions, int size_expr)
2409 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2410 get_chrec_loop (chrec),
2411 CHREC_LEFT (chrec), fold_conversions,
2413 if (op0 == chrec_dont_know)
2414 return chrec_dont_know;
2416 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2417 get_chrec_loop (chrec),
2418 CHREC_RIGHT (chrec), fold_conversions,
2420 if (op1 == chrec_dont_know)
2421 return chrec_dont_know;
2423 if (CHREC_LEFT (chrec) != op0
2424 || CHREC_RIGHT (chrec) != op1)
2426 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2427 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2433 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2434 and EVOLUTION_LOOP, that were left under a symbolic form.
2436 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2438 CACHE is the cache of already instantiated values.
2440 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2441 conversions that may wrap in signed/pointer type are folded, as long
2442 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2443 then we don't do such fold.
2445 SIZE_EXPR is used for computing the size of the expression to be
2446 instantiated, and to stop if it exceeds some limit. */
2449 instantiate_scev_binary (basic_block instantiate_below,
2450 struct loop *evolution_loop, struct loop *inner_loop,
2451 tree chrec, enum tree_code code,
2452 tree type, tree c0, tree c1,
2453 bool *fold_conversions, int size_expr)
2456 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2457 c0, fold_conversions, size_expr);
2458 if (op0 == chrec_dont_know)
2459 return chrec_dont_know;
2461 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2462 c1, fold_conversions, size_expr);
2463 if (op1 == chrec_dont_know)
2464 return chrec_dont_know;
2469 op0 = chrec_convert (type, op0, NULL);
2470 op1 = chrec_convert_rhs (type, op1, NULL);
2474 case POINTER_PLUS_EXPR:
2476 return chrec_fold_plus (type, op0, op1);
2479 return chrec_fold_minus (type, op0, op1);
2482 return chrec_fold_multiply (type, op0, op1);
2489 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2492 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2493 and EVOLUTION_LOOP, that were left under a symbolic form.
2495 "CHREC" is an array reference to be instantiated.
2497 CACHE is the cache of already instantiated values.
2499 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2500 conversions that may wrap in signed/pointer type are folded, as long
2501 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2502 then we don't do such fold.
2504 SIZE_EXPR is used for computing the size of the expression to be
2505 instantiated, and to stop if it exceeds some limit. */
2508 instantiate_array_ref (basic_block instantiate_below,
2509 struct loop *evolution_loop, struct loop *inner_loop,
2510 tree chrec, bool *fold_conversions, int size_expr)
2513 tree index = TREE_OPERAND (chrec, 1);
2514 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2516 fold_conversions, size_expr);
2518 if (op1 == chrec_dont_know)
2519 return chrec_dont_know;
2521 if (chrec && op1 == index)
2524 res = unshare_expr (chrec);
2525 TREE_OPERAND (res, 1) = op1;
2529 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2530 and EVOLUTION_LOOP, that were left under a symbolic form.
2532 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2535 CACHE is the cache of already instantiated values.
2537 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2538 conversions that may wrap in signed/pointer type are folded, as long
2539 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2540 then we don't do such fold.
2542 SIZE_EXPR is used for computing the size of the expression to be
2543 instantiated, and to stop if it exceeds some limit. */
2546 instantiate_scev_convert (basic_block instantiate_below,
2547 struct loop *evolution_loop, struct loop *inner_loop,
2548 tree chrec, tree type, tree op,
2549 bool *fold_conversions, int size_expr)
2551 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2553 fold_conversions, size_expr);
2555 if (op0 == chrec_dont_know)
2556 return chrec_dont_know;
2558 if (fold_conversions)
2560 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2564 /* If we used chrec_convert_aggressive, we can no longer assume that
2565 signed chrecs do not overflow, as chrec_convert does, so avoid
2566 calling it in that case. */
2567 if (*fold_conversions)
2569 if (chrec && op0 == op)
2572 return fold_convert (type, op0);
2576 return chrec_convert (type, op0, NULL);
2579 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2580 and EVOLUTION_LOOP, that were left under a symbolic form.
2582 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2583 Handle ~X as -1 - X.
2584 Handle -X as -1 * X.
2586 CACHE is the cache of already instantiated values.
2588 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2589 conversions that may wrap in signed/pointer type are folded, as long
2590 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2591 then we don't do such fold.
2593 SIZE_EXPR is used for computing the size of the expression to be
2594 instantiated, and to stop if it exceeds some limit. */
2597 instantiate_scev_not (basic_block instantiate_below,
2598 struct loop *evolution_loop, struct loop *inner_loop,
2600 enum tree_code code, tree type, tree op,
2601 bool *fold_conversions, int size_expr)
2603 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2605 fold_conversions, size_expr);
2607 if (op0 == chrec_dont_know)
2608 return chrec_dont_know;
2612 op0 = chrec_convert (type, op0, NULL);
2617 return chrec_fold_minus
2618 (type, fold_convert (type, integer_minus_one_node), op0);
2621 return chrec_fold_multiply
2622 (type, fold_convert (type, integer_minus_one_node), op0);
2629 return chrec ? chrec : fold_build1 (code, type, op0);
2632 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2633 and EVOLUTION_LOOP, that were left under a symbolic form.
2635 CHREC is an expression with 3 operands to be instantiated.
2637 CACHE is the cache of already instantiated values.
2639 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2640 conversions that may wrap in signed/pointer type are folded, as long
2641 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2642 then we don't do such fold.
2644 SIZE_EXPR is used for computing the size of the expression to be
2645 instantiated, and to stop if it exceeds some limit. */
2648 instantiate_scev_3 (basic_block instantiate_below,
2649 struct loop *evolution_loop, struct loop *inner_loop,
2651 bool *fold_conversions, int size_expr)
2654 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2655 inner_loop, TREE_OPERAND (chrec, 0),
2656 fold_conversions, size_expr);
2657 if (op0 == chrec_dont_know)
2658 return chrec_dont_know;
2660 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2661 inner_loop, TREE_OPERAND (chrec, 1),
2662 fold_conversions, size_expr);
2663 if (op1 == chrec_dont_know)
2664 return chrec_dont_know;
2666 op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2667 inner_loop, TREE_OPERAND (chrec, 2),
2668 fold_conversions, size_expr);
2669 if (op2 == chrec_dont_know)
2670 return chrec_dont_know;
2672 if (op0 == TREE_OPERAND (chrec, 0)
2673 && op1 == TREE_OPERAND (chrec, 1)
2674 && op2 == TREE_OPERAND (chrec, 2))
2677 return fold_build3 (TREE_CODE (chrec),
2678 TREE_TYPE (chrec), op0, op1, op2);
2681 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2682 and EVOLUTION_LOOP, that were left under a symbolic form.
2684 CHREC is an expression with 2 operands to be instantiated.
2686 CACHE is the cache of already instantiated values.
2688 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2689 conversions that may wrap in signed/pointer type are folded, as long
2690 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2691 then we don't do such fold.
2693 SIZE_EXPR is used for computing the size of the expression to be
2694 instantiated, and to stop if it exceeds some limit. */
2697 instantiate_scev_2 (basic_block instantiate_below,
2698 struct loop *evolution_loop, struct loop *inner_loop,
2700 bool *fold_conversions, int size_expr)
2703 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2704 inner_loop, TREE_OPERAND (chrec, 0),
2705 fold_conversions, size_expr);
2706 if (op0 == chrec_dont_know)
2707 return chrec_dont_know;
2709 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2710 inner_loop, TREE_OPERAND (chrec, 1),
2711 fold_conversions, size_expr);
2712 if (op1 == chrec_dont_know)
2713 return chrec_dont_know;
2715 if (op0 == TREE_OPERAND (chrec, 0)
2716 && op1 == TREE_OPERAND (chrec, 1))
2719 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2722 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2723 and EVOLUTION_LOOP, that were left under a symbolic form.
2725 CHREC is an expression with 2 operands to be instantiated.
2727 CACHE is the cache of already instantiated values.
2729 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2730 conversions that may wrap in signed/pointer type are folded, as long
2731 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2732 then we don't do such fold.
2734 SIZE_EXPR is used for computing the size of the expression to be
2735 instantiated, and to stop if it exceeds some limit. */
2738 instantiate_scev_1 (basic_block instantiate_below,
2739 struct loop *evolution_loop, struct loop *inner_loop,
2741 bool *fold_conversions, int size_expr)
2743 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2744 inner_loop, TREE_OPERAND (chrec, 0),
2745 fold_conversions, size_expr);
2747 if (op0 == chrec_dont_know)
2748 return chrec_dont_know;
2750 if (op0 == TREE_OPERAND (chrec, 0))
2753 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2756 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2757 and EVOLUTION_LOOP, that were left under a symbolic form.
2759 CHREC is the scalar evolution to instantiate.
2761 CACHE is the cache of already instantiated values.
2763 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2764 conversions that may wrap in signed/pointer type are folded, as long
2765 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2766 then we don't do such fold.
2768 SIZE_EXPR is used for computing the size of the expression to be
2769 instantiated, and to stop if it exceeds some limit. */
2772 instantiate_scev_r (basic_block instantiate_below,
2773 struct loop *evolution_loop, struct loop *inner_loop,
2775 bool *fold_conversions, int size_expr)
2777 /* Give up if the expression is larger than the MAX that we allow. */
2778 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2779 return chrec_dont_know;
2781 if (chrec == NULL_TREE
2782 || automatically_generated_chrec_p (chrec)
2783 || is_gimple_min_invariant (chrec))
2786 switch (TREE_CODE (chrec))
2789 return instantiate_scev_name (instantiate_below, evolution_loop,
2791 fold_conversions, size_expr);
2793 case POLYNOMIAL_CHREC:
2794 return instantiate_scev_poly (instantiate_below, evolution_loop,
2796 fold_conversions, size_expr);
2798 case POINTER_PLUS_EXPR:
2802 return instantiate_scev_binary (instantiate_below, evolution_loop,
2804 TREE_CODE (chrec), chrec_type (chrec),
2805 TREE_OPERAND (chrec, 0),
2806 TREE_OPERAND (chrec, 1),
2807 fold_conversions, size_expr);
2810 return instantiate_scev_convert (instantiate_below, evolution_loop,
2812 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2813 fold_conversions, size_expr);
2817 return instantiate_scev_not (instantiate_below, evolution_loop,
2819 TREE_CODE (chrec), TREE_TYPE (chrec),
2820 TREE_OPERAND (chrec, 0),
2821 fold_conversions, size_expr);
2824 case SCEV_NOT_KNOWN:
2825 return chrec_dont_know;
2831 return instantiate_array_ref (instantiate_below, evolution_loop,
2833 fold_conversions, size_expr);
2839 if (VL_EXP_CLASS_P (chrec))
2840 return chrec_dont_know;
2842 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2845 return instantiate_scev_3 (instantiate_below, evolution_loop,
2847 fold_conversions, size_expr);
2850 return instantiate_scev_2 (instantiate_below, evolution_loop,
2852 fold_conversions, size_expr);
2855 return instantiate_scev_1 (instantiate_below, evolution_loop,
2857 fold_conversions, size_expr);
2866 /* Too complicated to handle. */
2867 return chrec_dont_know;
2870 /* Analyze all the parameters of the chrec that were left under a
2871 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2872 recursive instantiation of parameters: a parameter is a variable
2873 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2874 a function parameter. */
2877 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2882 if (dump_file && (dump_flags & TDF_SCEV))
2884 fprintf (dump_file, "(instantiate_scev \n");
2885 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2886 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2887 fprintf (dump_file, " (chrec = ");
2888 print_generic_expr (dump_file, chrec, 0);
2889 fprintf (dump_file, ")\n");
2895 global_cache = new instantiate_cache_type;
2899 res = instantiate_scev_r (instantiate_below, evolution_loop,
2900 NULL, chrec, NULL, 0);
2904 delete global_cache;
2905 global_cache = NULL;
2908 if (dump_file && (dump_flags & TDF_SCEV))
2910 fprintf (dump_file, " (res = ");
2911 print_generic_expr (dump_file, res, 0);
2912 fprintf (dump_file, "))\n");
2918 /* Similar to instantiate_parameters, but does not introduce the
2919 evolutions in outer loops for LOOP invariants in CHREC, and does not
2920 care about causing overflows, as long as they do not affect value
2921 of an expression. */
2924 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
2927 bool fold_conversions = false;
2930 global_cache = new instantiate_cache_type;
2934 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
2935 chrec, &fold_conversions, 0);
2937 if (folded_casts && !*folded_casts)
2938 *folded_casts = fold_conversions;
2942 delete global_cache;
2943 global_cache = NULL;
2949 /* Entry point for the analysis of the number of iterations pass.
2950 This function tries to safely approximate the number of iterations
2951 the loop will run. When this property is not decidable at compile
2952 time, the result is chrec_dont_know. Otherwise the result is a
2953 scalar or a symbolic parameter. When the number of iterations may
2954 be equal to zero and the property cannot be determined at compile
2955 time, the result is a COND_EXPR that represents in a symbolic form
2956 the conditions under which the number of iterations is not zero.
2958 Example of analysis: suppose that the loop has an exit condition:
2960 "if (b > 49) goto end_loop;"
2962 and that in a previous analysis we have determined that the
2963 variable 'b' has an evolution function:
2965 "EF = {23, +, 5}_2".
2967 When we evaluate the function at the point 5, i.e. the value of the
2968 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2969 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2970 the loop body has been executed 6 times. */
2973 number_of_latch_executions (struct loop *loop)
2976 struct tree_niter_desc niter_desc;
2980 /* Determine whether the number of iterations in loop has already
2982 res = loop->nb_iterations;
2986 may_be_zero = NULL_TREE;
2988 if (dump_file && (dump_flags & TDF_SCEV))
2989 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2991 res = chrec_dont_know;
2992 exit = single_exit (loop);
2994 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2996 may_be_zero = niter_desc.may_be_zero;
2997 res = niter_desc.niter;
3000 if (res == chrec_dont_know
3002 || integer_zerop (may_be_zero))
3004 else if (integer_nonzerop (may_be_zero))
3005 res = build_int_cst (TREE_TYPE (res), 0);
3007 else if (COMPARISON_CLASS_P (may_be_zero))
3008 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
3009 build_int_cst (TREE_TYPE (res), 0), res);
3011 res = chrec_dont_know;
3013 if (dump_file && (dump_flags & TDF_SCEV))
3015 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
3016 print_generic_expr (dump_file, res, 0);
3017 fprintf (dump_file, "))\n");
3020 loop->nb_iterations = res;
3025 /* Counters for the stats. */
3031 unsigned nb_affine_multivar;
3032 unsigned nb_higher_poly;
3033 unsigned nb_chrec_dont_know;
3034 unsigned nb_undetermined;
3037 /* Reset the counters. */
3040 reset_chrecs_counters (struct chrec_stats *stats)
3042 stats->nb_chrecs = 0;
3043 stats->nb_affine = 0;
3044 stats->nb_affine_multivar = 0;
3045 stats->nb_higher_poly = 0;
3046 stats->nb_chrec_dont_know = 0;
3047 stats->nb_undetermined = 0;
3050 /* Dump the contents of a CHREC_STATS structure. */
3053 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3055 fprintf (file, "\n(\n");
3056 fprintf (file, "-----------------------------------------\n");
3057 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3058 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3059 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3060 stats->nb_higher_poly);
3061 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3062 fprintf (file, "-----------------------------------------\n");
3063 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3064 fprintf (file, "%d\twith undetermined coefficients\n",
3065 stats->nb_undetermined);
3066 fprintf (file, "-----------------------------------------\n");
3067 fprintf (file, "%d\tchrecs in the scev database\n",
3068 (int) scalar_evolution_info->elements ());
3069 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3070 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3071 fprintf (file, "-----------------------------------------\n");
3072 fprintf (file, ")\n\n");
3075 /* Gather statistics about CHREC. */
3078 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3080 if (dump_file && (dump_flags & TDF_STATS))
3082 fprintf (dump_file, "(classify_chrec ");
3083 print_generic_expr (dump_file, chrec, 0);
3084 fprintf (dump_file, "\n");
3089 if (chrec == NULL_TREE)
3091 stats->nb_undetermined++;
3095 switch (TREE_CODE (chrec))
3097 case POLYNOMIAL_CHREC:
3098 if (evolution_function_is_affine_p (chrec))
3100 if (dump_file && (dump_flags & TDF_STATS))
3101 fprintf (dump_file, " affine_univariate\n");
3104 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3106 if (dump_file && (dump_flags & TDF_STATS))
3107 fprintf (dump_file, " affine_multivariate\n");
3108 stats->nb_affine_multivar++;
3112 if (dump_file && (dump_flags & TDF_STATS))
3113 fprintf (dump_file, " higher_degree_polynomial\n");
3114 stats->nb_higher_poly++;
3123 if (chrec_contains_undetermined (chrec))
3125 if (dump_file && (dump_flags & TDF_STATS))
3126 fprintf (dump_file, " undetermined\n");
3127 stats->nb_undetermined++;
3130 if (dump_file && (dump_flags & TDF_STATS))
3131 fprintf (dump_file, ")\n");
3134 /* Classify the chrecs of the whole database. */
3137 gather_stats_on_scev_database (void)
3139 struct chrec_stats stats;
3144 reset_chrecs_counters (&stats);
3146 hash_table<scev_info_hasher>::iterator iter;
3148 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3150 gather_chrec_stats (elt->chrec, &stats);
3152 dump_chrecs_stats (dump_file, &stats);
3160 initialize_scalar_evolutions_analyzer (void)
3162 /* The elements below are unique. */
3163 if (chrec_dont_know == NULL_TREE)
3165 chrec_not_analyzed_yet = NULL_TREE;
3166 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3167 chrec_known = make_node (SCEV_KNOWN);
3168 TREE_TYPE (chrec_dont_know) = void_type_node;
3169 TREE_TYPE (chrec_known) = void_type_node;
3173 /* Initialize the analysis of scalar evolutions for LOOPS. */
3176 scev_initialize (void)
3180 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3182 initialize_scalar_evolutions_analyzer ();
3184 FOR_EACH_LOOP (loop, 0)
3186 loop->nb_iterations = NULL_TREE;
3190 /* Return true if SCEV is initialized. */
3193 scev_initialized_p (void)
3195 return scalar_evolution_info != NULL;
3198 /* Cleans up the information cached by the scalar evolutions analysis
3199 in the hash table. */
3202 scev_reset_htab (void)
3204 if (!scalar_evolution_info)
3207 scalar_evolution_info->empty ();
3210 /* Cleans up the information cached by the scalar evolutions analysis
3211 in the hash table and in the loop->nb_iterations. */
3220 FOR_EACH_LOOP (loop, 0)
3222 loop->nb_iterations = NULL_TREE;
3226 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3227 respect to WRTO_LOOP and returns its base and step in IV if possible
3228 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3229 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3230 invariant in LOOP. Otherwise we require it to be an integer constant.
3232 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3233 because it is computed in signed arithmetics). Consequently, adding an
3236 for (i = IV->base; ; i += IV->step)
3238 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3239 false for the type of the induction variable, or you can prove that i does
3240 not wrap by some other argument. Otherwise, this might introduce undefined
3243 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3245 must be used instead. */
3248 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3249 affine_iv *iv, bool allow_nonconstant_step)
3251 enum tree_code code;
3252 tree type, ev, base, e, stop;
3254 bool folded_casts, overflow;
3256 iv->base = NULL_TREE;
3257 iv->step = NULL_TREE;
3258 iv->no_overflow = false;
3260 type = TREE_TYPE (op);
3261 if (!POINTER_TYPE_P (type)
3262 && !INTEGRAL_TYPE_P (type))
3265 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3267 if (chrec_contains_undetermined (ev)
3268 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3271 if (tree_does_not_contain_chrecs (ev))
3274 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3275 iv->no_overflow = true;
3279 if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3280 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3283 iv->step = CHREC_RIGHT (ev);
3284 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3285 || tree_contains_chrecs (iv->step, NULL))
3288 iv->base = CHREC_LEFT (ev);
3289 if (tree_contains_chrecs (iv->base, NULL))
3292 iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
3293 && TYPE_OVERFLOW_UNDEFINED (type));
3295 /* Try to simplify iv base:
3297 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3298 == (signed T)(unsigned T)base + step
3301 If we can prove operation (base + step) doesn't overflow or underflow.
3302 Specifically, we try to prove below conditions are satisfied:
3304 base <= UPPER_BOUND (type) - step ;;step > 0
3305 base >= LOWER_BOUND (type) - step ;;step < 0
3307 This is done by proving the reverse conditions are false using loop's
3310 The is necessary to make loop niter, or iv overflow analysis easier
3313 int foo (int *a, signed char s, signed char l)
3316 for (i = s; i < l; i++)
3321 Note variable I is firstly converted to type unsigned char, incremented,
3322 then converted back to type signed char. */
3324 if (wrto_loop->num != use_loop->num)
3327 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3330 type = TREE_TYPE (iv->base);
3331 e = TREE_OPERAND (iv->base, 0);
3332 if (TREE_CODE (e) != PLUS_EXPR
3333 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3334 || !tree_int_cst_equal (iv->step,
3335 fold_convert (type, TREE_OPERAND (e, 1))))
3337 e = TREE_OPERAND (e, 0);
3338 if (!CONVERT_EXPR_P (e))
3340 base = TREE_OPERAND (e, 0);
3341 if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3344 if (tree_int_cst_sign_bit (iv->step))
3347 extreme = wi::min_value (type);
3352 extreme = wi::max_value (type);
3355 extreme = wi::sub (extreme, iv->step, TYPE_SIGN (type), &overflow);
3358 e = fold_build2 (code, boolean_type_node, base,
3359 wide_int_to_tree (type, extreme));
3360 stop = (TREE_CODE (base) == SSA_NAME) ? base : NULL;
3361 e = simplify_using_initial_conditions (use_loop, e, stop);
3362 if (!integer_zerop (e))
3365 if (POINTER_TYPE_P (TREE_TYPE (base)))
3366 code = POINTER_PLUS_EXPR;
3370 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3374 /* Finalize the scalar evolution analysis. */
3377 scev_finalize (void)
3379 if (!scalar_evolution_info)
3381 scalar_evolution_info->empty ();
3382 scalar_evolution_info = NULL;
3385 /* Returns true if the expression EXPR is considered to be too expensive
3386 for scev_const_prop. */
3389 expression_expensive_p (tree expr)
3391 enum tree_code code;
3393 if (is_gimple_val (expr))
3396 code = TREE_CODE (expr);
3397 if (code == TRUNC_DIV_EXPR
3398 || code == CEIL_DIV_EXPR
3399 || code == FLOOR_DIV_EXPR
3400 || code == ROUND_DIV_EXPR
3401 || code == TRUNC_MOD_EXPR
3402 || code == CEIL_MOD_EXPR
3403 || code == FLOOR_MOD_EXPR
3404 || code == ROUND_MOD_EXPR
3405 || code == EXACT_DIV_EXPR)
3407 /* Division by power of two is usually cheap, so we allow it.
3408 Forbid anything else. */
3409 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3413 switch (TREE_CODE_CLASS (code))
3416 case tcc_comparison:
3417 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3422 return expression_expensive_p (TREE_OPERAND (expr, 0));
3429 /* Replace ssa names for that scev can prove they are constant by the
3430 appropriate constants. Also perform final value replacement in loops,
3431 in case the replacement expressions are cheap.
3433 We only consider SSA names defined by phi nodes; rest is left to the
3434 ordinary constant propagation pass. */
3437 scev_const_prop (void)
3440 tree name, type, ev;
3443 struct loop *loop, *ex_loop;
3444 bitmap ssa_names_to_remove = NULL;
3448 if (number_of_loops (cfun) <= 1)
3451 FOR_EACH_BB_FN (bb, cfun)
3453 loop = bb->loop_father;
3455 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3458 name = PHI_RESULT (phi);
3460 if (virtual_operand_p (name))
3463 type = TREE_TYPE (name);
3465 if (!POINTER_TYPE_P (type)
3466 && !INTEGRAL_TYPE_P (type))
3469 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3471 if (!is_gimple_min_invariant (ev)
3472 || !may_propagate_copy (name, ev))
3475 /* Replace the uses of the name. */
3477 replace_uses_by (name, ev);
3479 if (!ssa_names_to_remove)
3480 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3481 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3485 /* Remove the ssa names that were replaced by constants. We do not
3486 remove them directly in the previous cycle, since this
3487 invalidates scev cache. */
3488 if (ssa_names_to_remove)
3492 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3494 gimple_stmt_iterator psi;
3495 name = ssa_name (i);
3496 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3498 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3499 psi = gsi_for_stmt (phi);
3500 remove_phi_node (&psi, true);
3503 BITMAP_FREE (ssa_names_to_remove);
3507 /* Now the regular final value replacement. */
3508 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3511 tree def, rslt, niter;
3512 gimple_stmt_iterator gsi;
3514 /* If we do not know exact number of iterations of the loop, we cannot
3515 replace the final value. */
3516 exit = single_exit (loop);
3520 niter = number_of_latch_executions (loop);
3521 if (niter == chrec_dont_know)
3524 /* Ensure that it is possible to insert new statements somewhere. */
3525 if (!single_pred_p (exit->dest))
3526 split_loop_exit_edge (exit);
3527 gsi = gsi_after_labels (exit->dest);
3529 ex_loop = superloop_at_depth (loop,
3530 loop_depth (exit->dest->loop_father) + 1);
3532 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3535 rslt = PHI_RESULT (phi);
3536 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3537 if (virtual_operand_p (def))
3543 if (!POINTER_TYPE_P (TREE_TYPE (def))
3544 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3551 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3553 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3554 if (!tree_does_not_contain_chrecs (def)
3555 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3556 /* Moving the computation from the loop may prolong life range
3557 of some ssa names, which may cause problems if they appear
3558 on abnormal edges. */
3559 || contains_abnormal_ssa_name_p (def)
3560 /* Do not emit expensive expressions. The rationale is that
3561 when someone writes a code like
3563 while (n > 45) n -= 45;
3565 he probably knows that n is not large, and does not want it
3566 to be turned into n %= 45. */
3567 || expression_expensive_p (def))
3569 if (dump_file && (dump_flags & TDF_DETAILS))
3571 fprintf (dump_file, "not replacing:\n ");
3572 print_gimple_stmt (dump_file, phi, 0, 0);
3573 fprintf (dump_file, "\n");
3579 /* Eliminate the PHI node and replace it by a computation outside
3583 fprintf (dump_file, "\nfinal value replacement:\n ");
3584 print_gimple_stmt (dump_file, phi, 0, 0);
3585 fprintf (dump_file, " with\n ");
3587 def = unshare_expr (def);
3588 remove_phi_node (&psi, false);
3590 /* If def's type has undefined overflow and there were folded
3591 casts, rewrite all stmts added for def into arithmetics
3592 with defined overflow behavior. */
3593 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3594 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3597 gimple_stmt_iterator gsi2;
3598 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3599 gsi2 = gsi_start (stmts);
3600 while (!gsi_end_p (gsi2))
3602 gimple *stmt = gsi_stmt (gsi2);
3603 gimple_stmt_iterator gsi3 = gsi2;
3605 gsi_remove (&gsi3, false);
3606 if (is_gimple_assign (stmt)
3607 && arith_code_with_undefined_signed_overflow
3608 (gimple_assign_rhs_code (stmt)))
3609 gsi_insert_seq_before (&gsi,
3610 rewrite_to_defined_overflow (stmt),
3613 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3617 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3618 true, GSI_SAME_STMT);
3620 ass = gimple_build_assign (rslt, def);
3621 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3624 print_gimple_stmt (dump_file, ass, 0, 0);
3625 fprintf (dump_file, "\n");
3632 #include "gt-tree-scalar-evolution.h"