1 /* Scalar evolution detector.
2 Copyright (C) 2003-2019 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"
262 #include "optabs-query.h"
266 #include "gimple-pretty-print.h"
267 #include "fold-const.h"
268 #include "gimplify.h"
269 #include "gimple-iterator.h"
270 #include "gimplify-me.h"
271 #include "tree-cfg.h"
272 #include "tree-ssa-loop-ivopts.h"
273 #include "tree-ssa-loop-manip.h"
274 #include "tree-ssa-loop-niter.h"
275 #include "tree-ssa-loop.h"
276 #include "tree-ssa.h"
278 #include "tree-chrec.h"
279 #include "tree-affine.h"
280 #include "tree-scalar-evolution.h"
281 #include "dumpfile.h"
283 #include "tree-ssa-propagate.h"
284 #include "gimple-fold.h"
285 #include "tree-into-ssa.h"
286 #include "builtins.h"
287 #include "case-cfn-macros.h"
289 static tree
analyze_scalar_evolution_1 (class loop
*, tree
);
290 static tree
analyze_scalar_evolution_for_address_of (class loop
*loop
,
293 /* The cached information about an SSA name with version NAME_VERSION,
294 claiming that below basic block with index INSTANTIATED_BELOW, the
295 value of the SSA name can be expressed as CHREC. */
297 struct GTY((for_user
)) scev_info_str
{
298 unsigned int name_version
;
299 int instantiated_below
;
303 /* Counters for the scev database. */
304 static unsigned nb_set_scev
= 0;
305 static unsigned nb_get_scev
= 0;
307 struct scev_info_hasher
: ggc_ptr_hash
<scev_info_str
>
309 static hashval_t
hash (scev_info_str
*i
);
310 static bool equal (const scev_info_str
*a
, const scev_info_str
*b
);
313 static GTY (()) hash_table
<scev_info_hasher
> *scalar_evolution_info
;
316 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
318 static inline struct scev_info_str
*
319 new_scev_info_str (basic_block instantiated_below
, tree var
)
321 struct scev_info_str
*res
;
323 res
= ggc_alloc
<scev_info_str
> ();
324 res
->name_version
= SSA_NAME_VERSION (var
);
325 res
->chrec
= chrec_not_analyzed_yet
;
326 res
->instantiated_below
= instantiated_below
->index
;
331 /* Computes a hash function for database element ELT. */
334 scev_info_hasher::hash (scev_info_str
*elt
)
336 return elt
->name_version
^ elt
->instantiated_below
;
339 /* Compares database elements E1 and E2. */
342 scev_info_hasher::equal (const scev_info_str
*elt1
, const scev_info_str
*elt2
)
344 return (elt1
->name_version
== elt2
->name_version
345 && elt1
->instantiated_below
== elt2
->instantiated_below
);
348 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
349 A first query on VAR returns chrec_not_analyzed_yet. */
352 find_var_scev_info (basic_block instantiated_below
, tree var
)
354 struct scev_info_str
*res
;
355 struct scev_info_str tmp
;
357 tmp
.name_version
= SSA_NAME_VERSION (var
);
358 tmp
.instantiated_below
= instantiated_below
->index
;
359 scev_info_str
**slot
= scalar_evolution_info
->find_slot (&tmp
, INSERT
);
362 *slot
= new_scev_info_str (instantiated_below
, var
);
369 /* Hashtable helpers for a temporary hash-table used when
370 analyzing a scalar evolution, instantiating a CHREC or
373 class instantiate_cache_type
377 vec
<scev_info_str
> entries
;
379 instantiate_cache_type () : map (NULL
), entries (vNULL
) {}
380 ~instantiate_cache_type ();
381 tree
get (unsigned slot
) { return entries
[slot
].chrec
; }
382 void set (unsigned slot
, tree chrec
) { entries
[slot
].chrec
= chrec
; }
385 instantiate_cache_type::~instantiate_cache_type ()
394 /* Cache to avoid infinite recursion when instantiating an SSA name.
395 Live during the outermost analyze_scalar_evolution, instantiate_scev
396 or resolve_mixers call. */
397 static instantiate_cache_type
*global_cache
;
400 /* Return true when PHI is a loop-phi-node. */
403 loop_phi_node_p (gimple
*phi
)
405 /* The implementation of this function is based on the following
406 property: "all the loop-phi-nodes of a loop are contained in the
407 loop's header basic block". */
409 return loop_containing_stmt (phi
)->header
== gimple_bb (phi
);
412 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
413 In general, in the case of multivariate evolutions we want to get
414 the evolution in different loops. LOOP specifies the level for
415 which to get the evolution.
419 | for (j = 0; j < 100; j++)
421 | for (k = 0; k < 100; k++)
423 | i = k + j; - Here the value of i is a function of j, k.
425 | ... = i - Here the value of i is a function of j.
427 | ... = i - Here the value of i is a scalar.
433 | i_1 = phi (i_0, i_2)
437 This loop has the same effect as:
438 LOOP_1 has the same effect as:
442 The overall effect of the loop, "i_0 + 20" in the previous example,
443 is obtained by passing in the parameters: LOOP = 1,
444 EVOLUTION_FN = {i_0, +, 2}_1.
448 compute_overall_effect_of_inner_loop (class loop
*loop
, tree evolution_fn
)
452 if (evolution_fn
== chrec_dont_know
)
453 return chrec_dont_know
;
455 else if (TREE_CODE (evolution_fn
) == POLYNOMIAL_CHREC
)
457 class loop
*inner_loop
= get_chrec_loop (evolution_fn
);
459 if (inner_loop
== loop
460 || flow_loop_nested_p (loop
, inner_loop
))
462 tree nb_iter
= number_of_latch_executions (inner_loop
);
464 if (nb_iter
== chrec_dont_know
)
465 return chrec_dont_know
;
470 /* evolution_fn is the evolution function in LOOP. Get
471 its value in the nb_iter-th iteration. */
472 res
= chrec_apply (inner_loop
->num
, evolution_fn
, nb_iter
);
474 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
475 res
= instantiate_parameters (loop
, res
);
477 /* Continue the computation until ending on a parent of LOOP. */
478 return compute_overall_effect_of_inner_loop (loop
, res
);
485 /* If the evolution function is an invariant, there is nothing to do. */
486 else if (no_evolution_in_loop_p (evolution_fn
, loop
->num
, &val
) && val
)
490 return chrec_dont_know
;
493 /* Associate CHREC to SCALAR. */
496 set_scalar_evolution (basic_block instantiated_below
, tree scalar
, tree chrec
)
500 if (TREE_CODE (scalar
) != SSA_NAME
)
503 scalar_info
= find_var_scev_info (instantiated_below
, scalar
);
507 if (dump_flags
& TDF_SCEV
)
509 fprintf (dump_file
, "(set_scalar_evolution \n");
510 fprintf (dump_file
, " instantiated_below = %d \n",
511 instantiated_below
->index
);
512 fprintf (dump_file
, " (scalar = ");
513 print_generic_expr (dump_file
, scalar
);
514 fprintf (dump_file
, ")\n (scalar_evolution = ");
515 print_generic_expr (dump_file
, chrec
);
516 fprintf (dump_file
, "))\n");
518 if (dump_flags
& TDF_STATS
)
522 *scalar_info
= chrec
;
525 /* Retrieve the chrec associated to SCALAR instantiated below
526 INSTANTIATED_BELOW block. */
529 get_scalar_evolution (basic_block instantiated_below
, tree scalar
)
535 if (dump_flags
& TDF_SCEV
)
537 fprintf (dump_file
, "(get_scalar_evolution \n");
538 fprintf (dump_file
, " (scalar = ");
539 print_generic_expr (dump_file
, scalar
);
540 fprintf (dump_file
, ")\n");
542 if (dump_flags
& TDF_STATS
)
546 if (VECTOR_TYPE_P (TREE_TYPE (scalar
))
547 || TREE_CODE (TREE_TYPE (scalar
)) == COMPLEX_TYPE
)
548 /* For chrec_dont_know we keep the symbolic form. */
551 switch (TREE_CODE (scalar
))
554 if (SSA_NAME_IS_DEFAULT_DEF (scalar
))
557 res
= *find_var_scev_info (instantiated_below
, scalar
);
567 res
= chrec_not_analyzed_yet
;
571 if (dump_file
&& (dump_flags
& TDF_SCEV
))
573 fprintf (dump_file
, " (scalar_evolution = ");
574 print_generic_expr (dump_file
, res
);
575 fprintf (dump_file
, "))\n");
581 /* Helper function for add_to_evolution. Returns the evolution
582 function for an assignment of the form "a = b + c", where "a" and
583 "b" are on the strongly connected component. CHREC_BEFORE is the
584 information that we already have collected up to this point.
585 TO_ADD is the evolution of "c".
587 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
588 evolution the expression TO_ADD, otherwise construct an evolution
589 part for this loop. */
592 add_to_evolution_1 (unsigned loop_nb
, tree chrec_before
, tree to_add
,
595 tree type
, left
, right
;
596 class loop
*loop
= get_loop (cfun
, loop_nb
), *chloop
;
598 switch (TREE_CODE (chrec_before
))
600 case POLYNOMIAL_CHREC
:
601 chloop
= get_chrec_loop (chrec_before
);
603 || flow_loop_nested_p (chloop
, loop
))
607 type
= chrec_type (chrec_before
);
609 /* When there is no evolution part in this loop, build it. */
614 right
= SCALAR_FLOAT_TYPE_P (type
)
615 ? build_real (type
, dconst0
)
616 : build_int_cst (type
, 0);
620 var
= CHREC_VARIABLE (chrec_before
);
621 left
= CHREC_LEFT (chrec_before
);
622 right
= CHREC_RIGHT (chrec_before
);
625 to_add
= chrec_convert (type
, to_add
, at_stmt
);
626 right
= chrec_convert_rhs (type
, right
, at_stmt
);
627 right
= chrec_fold_plus (chrec_type (right
), right
, to_add
);
628 return build_polynomial_chrec (var
, left
, right
);
632 gcc_assert (flow_loop_nested_p (loop
, chloop
));
634 /* Search the evolution in LOOP_NB. */
635 left
= add_to_evolution_1 (loop_nb
, CHREC_LEFT (chrec_before
),
637 right
= CHREC_RIGHT (chrec_before
);
638 right
= chrec_convert_rhs (chrec_type (left
), right
, at_stmt
);
639 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before
),
644 /* These nodes do not depend on a loop. */
645 if (chrec_before
== chrec_dont_know
)
646 return chrec_dont_know
;
649 right
= chrec_convert_rhs (chrec_type (left
), to_add
, at_stmt
);
650 return build_polynomial_chrec (loop_nb
, left
, right
);
654 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
657 Description (provided for completeness, for those who read code in
658 a plane, and for my poor 62 bytes brain that would have forgotten
659 all this in the next two or three months):
661 The algorithm of translation of programs from the SSA representation
662 into the chrecs syntax is based on a pattern matching. After having
663 reconstructed the overall tree expression for a loop, there are only
664 two cases that can arise:
666 1. a = loop-phi (init, a + expr)
667 2. a = loop-phi (init, expr)
669 where EXPR is either a scalar constant with respect to the analyzed
670 loop (this is a degree 0 polynomial), or an expression containing
671 other loop-phi definitions (these are higher degree polynomials).
678 | a = phi (init, a + 5)
685 | a = phi (inita, 2 * b + 3)
686 | b = phi (initb, b + 1)
689 For the first case, the semantics of the SSA representation is:
691 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
693 that is, there is a loop index "x" that determines the scalar value
694 of the variable during the loop execution. During the first
695 iteration, the value is that of the initial condition INIT, while
696 during the subsequent iterations, it is the sum of the initial
697 condition with the sum of all the values of EXPR from the initial
698 iteration to the before last considered iteration.
700 For the second case, the semantics of the SSA program is:
702 | a (x) = init, if x = 0;
703 | expr (x - 1), otherwise.
705 The second case corresponds to the PEELED_CHREC, whose syntax is
706 close to the syntax of a loop-phi-node:
708 | phi (init, expr) vs. (init, expr)_x
710 The proof of the translation algorithm for the first case is a
711 proof by structural induction based on the degree of EXPR.
714 When EXPR is a constant with respect to the analyzed loop, or in
715 other words when EXPR is a polynomial of degree 0, the evolution of
716 the variable A in the loop is an affine function with an initial
717 condition INIT, and a step EXPR. In order to show this, we start
718 from the semantics of the SSA representation:
720 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
722 and since "expr (j)" is a constant with respect to "j",
724 f (x) = init + x * expr
726 Finally, based on the semantics of the pure sum chrecs, by
727 identification we get the corresponding chrecs syntax:
729 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
730 f (x) -> {init, +, expr}_x
733 Suppose that EXPR is a polynomial of degree N with respect to the
734 analyzed loop_x for which we have already determined that it is
735 written under the chrecs syntax:
737 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
739 We start from the semantics of the SSA program:
741 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
743 | f (x) = init + \sum_{j = 0}^{x - 1}
744 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
746 | f (x) = init + \sum_{j = 0}^{x - 1}
747 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
749 | f (x) = init + \sum_{k = 0}^{n - 1}
750 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
752 | f (x) = init + \sum_{k = 0}^{n - 1}
753 | (b_k * \binom{x}{k + 1})
755 | f (x) = init + b_0 * \binom{x}{1} + ...
756 | + b_{n-1} * \binom{x}{n}
758 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
759 | + b_{n-1} * \binom{x}{n}
762 And finally from the definition of the chrecs syntax, we identify:
763 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
765 This shows the mechanism that stands behind the add_to_evolution
766 function. An important point is that the use of symbolic
767 parameters avoids the need of an analysis schedule.
774 | a = phi (inita, a + 2 + b)
775 | b = phi (initb, b + 1)
778 When analyzing "a", the algorithm keeps "b" symbolically:
780 | a -> {inita, +, 2 + b}_1
782 Then, after instantiation, the analyzer ends on the evolution:
784 | a -> {inita, +, 2 + initb, +, 1}_1
789 add_to_evolution (unsigned loop_nb
, tree chrec_before
, enum tree_code code
,
790 tree to_add
, gimple
*at_stmt
)
792 tree type
= chrec_type (to_add
);
793 tree res
= NULL_TREE
;
795 if (to_add
== NULL_TREE
)
798 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
799 instantiated at this point. */
800 if (TREE_CODE (to_add
) == POLYNOMIAL_CHREC
)
801 /* This should not happen. */
802 return chrec_dont_know
;
804 if (dump_file
&& (dump_flags
& TDF_SCEV
))
806 fprintf (dump_file
, "(add_to_evolution \n");
807 fprintf (dump_file
, " (loop_nb = %d)\n", loop_nb
);
808 fprintf (dump_file
, " (chrec_before = ");
809 print_generic_expr (dump_file
, chrec_before
);
810 fprintf (dump_file
, ")\n (to_add = ");
811 print_generic_expr (dump_file
, to_add
);
812 fprintf (dump_file
, ")\n");
815 if (code
== MINUS_EXPR
)
816 to_add
= chrec_fold_multiply (type
, to_add
, SCALAR_FLOAT_TYPE_P (type
)
817 ? build_real (type
, dconstm1
)
818 : build_int_cst_type (type
, -1));
820 res
= add_to_evolution_1 (loop_nb
, chrec_before
, to_add
, at_stmt
);
822 if (dump_file
&& (dump_flags
& TDF_SCEV
))
824 fprintf (dump_file
, " (res = ");
825 print_generic_expr (dump_file
, res
);
826 fprintf (dump_file
, "))\n");
834 /* This section selects the loops that will be good candidates for the
835 scalar evolution analysis. For the moment, greedily select all the
836 loop nests we could analyze. */
838 /* For a loop with a single exit edge, return the COND_EXPR that
839 guards the exit edge. If the expression is too difficult to
840 analyze, then give up. */
843 get_loop_exit_condition (const class loop
*loop
)
846 edge exit_edge
= single_exit (loop
);
848 if (dump_file
&& (dump_flags
& TDF_SCEV
))
849 fprintf (dump_file
, "(get_loop_exit_condition \n ");
855 stmt
= last_stmt (exit_edge
->src
);
856 if (gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (stmt
))
860 if (dump_file
&& (dump_flags
& TDF_SCEV
))
862 print_gimple_stmt (dump_file
, res
, 0);
863 fprintf (dump_file
, ")\n");
870 /* Depth first search algorithm. */
879 static t_bool
follow_ssa_edge_expr (class loop
*loop
, gimple
*, tree
, gphi
*,
882 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
883 Return true if the strongly connected component has been found. */
886 follow_ssa_edge_binary (class loop
*loop
, gimple
*at_stmt
,
887 tree type
, tree rhs0
, enum tree_code code
, tree rhs1
,
888 gphi
*halting_phi
, tree
*evolution_of_loop
,
891 t_bool res
= t_false
;
896 case POINTER_PLUS_EXPR
:
898 if (TREE_CODE (rhs0
) == SSA_NAME
)
900 if (TREE_CODE (rhs1
) == SSA_NAME
)
902 /* Match an assignment under the form:
905 /* We want only assignments of form "name + name" contribute to
906 LIMIT, as the other cases do not necessarily contribute to
907 the complexity of the expression. */
910 evol
= *evolution_of_loop
;
911 evol
= add_to_evolution
913 chrec_convert (type
, evol
, at_stmt
),
914 code
, rhs1
, at_stmt
);
915 res
= follow_ssa_edge_expr
916 (loop
, at_stmt
, rhs0
, halting_phi
, &evol
, limit
);
918 *evolution_of_loop
= evol
;
919 else if (res
== t_false
)
921 *evolution_of_loop
= add_to_evolution
923 chrec_convert (type
, *evolution_of_loop
, at_stmt
),
924 code
, rhs0
, at_stmt
);
925 res
= follow_ssa_edge_expr
926 (loop
, at_stmt
, rhs1
, halting_phi
,
927 evolution_of_loop
, limit
);
932 gcc_unreachable (); /* Handled in caller. */
935 else if (TREE_CODE (rhs1
) == SSA_NAME
)
937 /* Match an assignment under the form:
939 *evolution_of_loop
= add_to_evolution
940 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
942 code
, rhs0
, at_stmt
);
943 res
= follow_ssa_edge_expr
944 (loop
, at_stmt
, rhs1
, halting_phi
,
945 evolution_of_loop
, limit
);
949 /* Otherwise, match an assignment under the form:
951 /* And there is nothing to do. */
956 /* This case is under the form "opnd0 = rhs0 - rhs1". */
957 if (TREE_CODE (rhs0
) == SSA_NAME
)
958 gcc_unreachable (); /* Handled in caller. */
960 /* Otherwise, match an assignment under the form:
962 /* And there is nothing to do. */
973 /* Checks whether the I-th argument of a PHI comes from a backedge. */
976 backedge_phi_arg_p (gphi
*phi
, int i
)
978 const_edge e
= gimple_phi_arg_edge (phi
, i
);
980 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
981 about updating it anywhere, and this should work as well most of the
983 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
989 /* Helper function for one branch of the condition-phi-node. Return
990 true if the strongly connected component has been found following
994 follow_ssa_edge_in_condition_phi_branch (int i
,
998 tree
*evolution_of_branch
,
999 tree init_cond
, int limit
)
1001 tree branch
= PHI_ARG_DEF (condition_phi
, i
);
1002 *evolution_of_branch
= chrec_dont_know
;
1004 /* Do not follow back edges (they must belong to an irreducible loop, which
1005 we really do not want to worry about). */
1006 if (backedge_phi_arg_p (condition_phi
, i
))
1009 if (TREE_CODE (branch
) == SSA_NAME
)
1011 *evolution_of_branch
= init_cond
;
1012 return follow_ssa_edge_expr (loop
, condition_phi
, branch
, halting_phi
,
1013 evolution_of_branch
, limit
);
1016 /* This case occurs when one of the condition branches sets
1017 the variable to a constant: i.e. a phi-node like
1018 "a_2 = PHI <a_7(5), 2(6)>;".
1020 FIXME: This case have to be refined correctly:
1021 in some cases it is possible to say something better than
1022 chrec_dont_know, for example using a wrap-around notation. */
1026 /* This function merges the branches of a condition-phi-node in a
1030 follow_ssa_edge_in_condition_phi (class loop
*loop
,
1031 gphi
*condition_phi
,
1033 tree
*evolution_of_loop
, int limit
)
1036 tree init
= *evolution_of_loop
;
1037 tree evolution_of_branch
;
1038 t_bool res
= follow_ssa_edge_in_condition_phi_branch (0, loop
, condition_phi
,
1040 &evolution_of_branch
,
1042 if (res
== t_false
|| res
== t_dont_know
)
1045 *evolution_of_loop
= evolution_of_branch
;
1047 n
= gimple_phi_num_args (condition_phi
);
1048 for (i
= 1; i
< n
; i
++)
1050 /* Quickly give up when the evolution of one of the branches is
1052 if (*evolution_of_loop
== chrec_dont_know
)
1055 /* Increase the limit by the PHI argument number to avoid exponential
1056 time and memory complexity. */
1057 res
= follow_ssa_edge_in_condition_phi_branch (i
, loop
, condition_phi
,
1059 &evolution_of_branch
,
1061 if (res
== t_false
|| res
== t_dont_know
)
1064 *evolution_of_loop
= chrec_merge (*evolution_of_loop
,
1065 evolution_of_branch
);
1071 /* Follow an SSA edge in an inner loop. It computes the overall
1072 effect of the loop, and following the symbolic initial conditions,
1073 it follows the edges in the parent loop. The inner loop is
1074 considered as a single statement. */
1077 follow_ssa_edge_inner_loop_phi (class loop
*outer_loop
,
1078 gphi
*loop_phi_node
,
1080 tree
*evolution_of_loop
, int limit
)
1082 class loop
*loop
= loop_containing_stmt (loop_phi_node
);
1083 tree ev
= analyze_scalar_evolution (loop
, PHI_RESULT (loop_phi_node
));
1085 /* Sometimes, the inner loop is too difficult to analyze, and the
1086 result of the analysis is a symbolic parameter. */
1087 if (ev
== PHI_RESULT (loop_phi_node
))
1089 t_bool res
= t_false
;
1090 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1092 for (i
= 0; i
< n
; i
++)
1094 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1097 /* Follow the edges that exit the inner loop. */
1098 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1099 if (!flow_bb_inside_loop_p (loop
, bb
))
1100 res
= follow_ssa_edge_expr (outer_loop
, loop_phi_node
,
1102 evolution_of_loop
, limit
);
1107 /* If the path crosses this loop-phi, give up. */
1109 *evolution_of_loop
= chrec_dont_know
;
1114 /* Otherwise, compute the overall effect of the inner loop. */
1115 ev
= compute_overall_effect_of_inner_loop (loop
, ev
);
1116 return follow_ssa_edge_expr (outer_loop
, loop_phi_node
, ev
, halting_phi
,
1117 evolution_of_loop
, limit
);
1120 /* Follow the ssa edge into the expression EXPR.
1121 Return true if the strongly connected component has been found. */
1124 follow_ssa_edge_expr (class loop
*loop
, gimple
*at_stmt
, tree expr
,
1125 gphi
*halting_phi
, tree
*evolution_of_loop
,
1128 enum tree_code code
;
1129 tree type
, rhs0
, rhs1
= NULL_TREE
;
1131 /* The EXPR is one of the following cases:
1135 - a POINTER_PLUS_EXPR,
1138 - other cases are not yet handled. */
1140 /* For SSA_NAME look at the definition statement, handling
1141 PHI nodes and otherwise expand appropriately for the expression
1144 if (TREE_CODE (expr
) == SSA_NAME
)
1146 gimple
*def
= SSA_NAME_DEF_STMT (expr
);
1148 if (gimple_nop_p (def
))
1151 /* Give up if the path is longer than the MAX that we allow. */
1152 if (limit
> PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY
))
1154 *evolution_of_loop
= chrec_dont_know
;
1158 if (gphi
*phi
= dyn_cast
<gphi
*>(def
))
1160 if (!loop_phi_node_p (phi
))
1161 /* DEF is a condition-phi-node. Follow the branches, and
1162 record their evolutions. Finally, merge the collected
1163 information and set the approximation to the main
1165 return follow_ssa_edge_in_condition_phi
1166 (loop
, phi
, halting_phi
, evolution_of_loop
, limit
);
1168 /* When the analyzed phi is the halting_phi, the
1169 depth-first search is over: we have found a path from
1170 the halting_phi to itself in the loop. */
1171 if (phi
== halting_phi
)
1174 /* Otherwise, the evolution of the HALTING_PHI depends
1175 on the evolution of another loop-phi-node, i.e. the
1176 evolution function is a higher degree polynomial. */
1177 class loop
*def_loop
= loop_containing_stmt (def
);
1178 if (def_loop
== loop
)
1182 if (flow_loop_nested_p (loop
, def_loop
))
1183 return follow_ssa_edge_inner_loop_phi
1184 (loop
, phi
, halting_phi
, evolution_of_loop
,
1191 /* At this level of abstraction, the program is just a set
1192 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1193 other def to be handled. */
1194 if (!is_gimple_assign (def
))
1197 code
= gimple_assign_rhs_code (def
);
1198 switch (get_gimple_rhs_class (code
))
1200 case GIMPLE_BINARY_RHS
:
1201 rhs0
= gimple_assign_rhs1 (def
);
1202 rhs1
= gimple_assign_rhs2 (def
);
1204 case GIMPLE_UNARY_RHS
:
1205 case GIMPLE_SINGLE_RHS
:
1206 rhs0
= gimple_assign_rhs1 (def
);
1211 type
= TREE_TYPE (gimple_assign_lhs (def
));
1216 code
= TREE_CODE (expr
);
1217 type
= TREE_TYPE (expr
);
1221 rhs0
= TREE_OPERAND (expr
, 0);
1223 case POINTER_PLUS_EXPR
:
1226 rhs0
= TREE_OPERAND (expr
, 0);
1227 rhs1
= TREE_OPERAND (expr
, 1);
1238 /* This assignment is under the form "a_1 = (cast) rhs. */
1239 t_bool res
= follow_ssa_edge_expr (loop
, at_stmt
, rhs0
, halting_phi
,
1240 evolution_of_loop
, limit
);
1241 *evolution_of_loop
= chrec_convert (type
, *evolution_of_loop
, at_stmt
);
1246 /* This assignment is under the form "a_1 = 7". */
1251 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1252 if (TREE_CODE (TREE_OPERAND (rhs0
, 0)) != MEM_REF
)
1254 tree mem
= TREE_OPERAND (rhs0
, 0);
1255 rhs0
= TREE_OPERAND (mem
, 0);
1256 rhs1
= TREE_OPERAND (mem
, 1);
1257 code
= POINTER_PLUS_EXPR
;
1260 case POINTER_PLUS_EXPR
:
1263 /* This case is under the form "rhs0 +- rhs1". */
1264 STRIP_USELESS_TYPE_CONVERSION (rhs0
);
1265 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
1266 if (TREE_CODE (rhs0
) == SSA_NAME
1267 && (TREE_CODE (rhs1
) != SSA_NAME
|| code
== MINUS_EXPR
))
1269 /* Match an assignment under the form:
1271 Use tail-recursion for the simple case. */
1272 *evolution_of_loop
= add_to_evolution
1273 (loop
->num
, chrec_convert (type
, *evolution_of_loop
,
1275 code
, rhs1
, at_stmt
);
1279 /* Else search for the SCC in both rhs0 and rhs1. */
1280 return follow_ssa_edge_binary (loop
, at_stmt
, type
, rhs0
, code
, rhs1
,
1281 halting_phi
, evolution_of_loop
, limit
);
1284 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1285 It must be handled as a copy assignment of the form a_1 = a_2. */
1286 expr
= ASSERT_EXPR_VAR (rhs0
);
1295 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1296 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1298 # i_17 = PHI <i_13(5), 0(3)>
1299 # _20 = PHI <_5(5), start_4(D)(3)>
1302 _5 = start_4(D) + i_13;
1304 Though variable _20 appears as a PEELED_CHREC in the form of
1305 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1310 simplify_peeled_chrec (class loop
*loop
, tree arg
, tree init_cond
)
1312 aff_tree aff1
, aff2
;
1313 tree ev
, left
, right
, type
, step_val
;
1314 hash_map
<tree
, name_expansion
*> *peeled_chrec_map
= NULL
;
1316 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, arg
));
1317 if (ev
== NULL_TREE
|| TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
1318 return chrec_dont_know
;
1320 left
= CHREC_LEFT (ev
);
1321 right
= CHREC_RIGHT (ev
);
1322 type
= TREE_TYPE (left
);
1323 step_val
= chrec_fold_plus (type
, init_cond
, right
);
1325 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1326 if "left" equals to "init + right". */
1327 if (operand_equal_p (left
, step_val
, 0))
1329 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1330 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1332 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1335 /* The affine code only deals with pointer and integer types. */
1336 if (!POINTER_TYPE_P (type
)
1337 && !INTEGRAL_TYPE_P (type
))
1338 return chrec_dont_know
;
1340 /* Try harder to check if they are equal. */
1341 tree_to_aff_combination_expand (left
, type
, &aff1
, &peeled_chrec_map
);
1342 tree_to_aff_combination_expand (step_val
, type
, &aff2
, &peeled_chrec_map
);
1343 free_affine_expand_cache (&peeled_chrec_map
);
1344 aff_combination_scale (&aff2
, -1);
1345 aff_combination_add (&aff1
, &aff2
);
1347 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1348 if "left" equals to "init + right". */
1349 if (aff_combination_zero_p (&aff1
))
1351 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1352 fprintf (dump_file
, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1354 return build_polynomial_chrec (loop
->num
, init_cond
, right
);
1356 return chrec_dont_know
;
1359 /* Given a LOOP_PHI_NODE, this function determines the evolution
1360 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1363 analyze_evolution_in_loop (gphi
*loop_phi_node
,
1366 int i
, n
= gimple_phi_num_args (loop_phi_node
);
1367 tree evolution_function
= chrec_not_analyzed_yet
;
1368 class loop
*loop
= loop_containing_stmt (loop_phi_node
);
1370 static bool simplify_peeled_chrec_p
= true;
1372 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1374 fprintf (dump_file
, "(analyze_evolution_in_loop \n");
1375 fprintf (dump_file
, " (loop_phi_node = ");
1376 print_gimple_stmt (dump_file
, loop_phi_node
, 0);
1377 fprintf (dump_file
, ")\n");
1380 for (i
= 0; i
< n
; i
++)
1382 tree arg
= PHI_ARG_DEF (loop_phi_node
, i
);
1386 /* Select the edges that enter the loop body. */
1387 bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1388 if (!flow_bb_inside_loop_p (loop
, bb
))
1391 if (TREE_CODE (arg
) == SSA_NAME
)
1395 /* Pass in the initial condition to the follow edge function. */
1397 res
= follow_ssa_edge_expr (loop
, loop_phi_node
, arg
,
1398 loop_phi_node
, &ev_fn
, 0);
1400 /* If ev_fn has no evolution in the inner loop, and the
1401 init_cond is not equal to ev_fn, then we have an
1402 ambiguity between two possible values, as we cannot know
1403 the number of iterations at this point. */
1404 if (TREE_CODE (ev_fn
) != POLYNOMIAL_CHREC
1405 && no_evolution_in_loop_p (ev_fn
, loop
->num
, &val
) && val
1406 && !operand_equal_p (init_cond
, ev_fn
, 0))
1407 ev_fn
= chrec_dont_know
;
1412 /* When it is impossible to go back on the same
1413 loop_phi_node by following the ssa edges, the
1414 evolution is represented by a peeled chrec, i.e. the
1415 first iteration, EV_FN has the value INIT_COND, then
1416 all the other iterations it has the value of ARG.
1417 For the moment, PEELED_CHREC nodes are not built. */
1420 ev_fn
= chrec_dont_know
;
1421 /* Try to recognize POLYNOMIAL_CHREC which appears in
1422 the form of PEELED_CHREC, but guard the process with
1423 a bool variable to keep the analyzer from infinite
1424 recurrence for real PEELED_RECs. */
1425 if (simplify_peeled_chrec_p
&& TREE_CODE (arg
) == SSA_NAME
)
1427 simplify_peeled_chrec_p
= false;
1428 ev_fn
= simplify_peeled_chrec (loop
, arg
, init_cond
);
1429 simplify_peeled_chrec_p
= true;
1433 /* When there are multiple back edges of the loop (which in fact never
1434 happens currently, but nevertheless), merge their evolutions. */
1435 evolution_function
= chrec_merge (evolution_function
, ev_fn
);
1437 if (evolution_function
== chrec_dont_know
)
1441 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1443 fprintf (dump_file
, " (evolution_function = ");
1444 print_generic_expr (dump_file
, evolution_function
);
1445 fprintf (dump_file
, "))\n");
1448 return evolution_function
;
1451 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1452 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1455 follow_copies_to_constant (tree var
)
1458 while (TREE_CODE (res
) == SSA_NAME
1459 /* We face not updated SSA form in multiple places and this walk
1460 may end up in sibling loops so we have to guard it. */
1461 && !name_registered_for_update_p (res
))
1463 gimple
*def
= SSA_NAME_DEF_STMT (res
);
1464 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
1466 if (tree rhs
= degenerate_phi_result (phi
))
1471 else if (gimple_assign_single_p (def
))
1472 /* Will exit loop if not an SSA_NAME. */
1473 res
= gimple_assign_rhs1 (def
);
1477 if (CONSTANT_CLASS_P (res
))
1482 /* Given a loop-phi-node, return the initial conditions of the
1483 variable on entry of the loop. When the CCP has propagated
1484 constants into the loop-phi-node, the initial condition is
1485 instantiated, otherwise the initial condition is kept symbolic.
1486 This analyzer does not analyze the evolution outside the current
1487 loop, and leaves this task to the on-demand tree reconstructor. */
1490 analyze_initial_condition (gphi
*loop_phi_node
)
1493 tree init_cond
= chrec_not_analyzed_yet
;
1494 class loop
*loop
= loop_containing_stmt (loop_phi_node
);
1496 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1498 fprintf (dump_file
, "(analyze_initial_condition \n");
1499 fprintf (dump_file
, " (loop_phi_node = \n");
1500 print_gimple_stmt (dump_file
, loop_phi_node
, 0);
1501 fprintf (dump_file
, ")\n");
1504 n
= gimple_phi_num_args (loop_phi_node
);
1505 for (i
= 0; i
< n
; i
++)
1507 tree branch
= PHI_ARG_DEF (loop_phi_node
, i
);
1508 basic_block bb
= gimple_phi_arg_edge (loop_phi_node
, i
)->src
;
1510 /* When the branch is oriented to the loop's body, it does
1511 not contribute to the initial condition. */
1512 if (flow_bb_inside_loop_p (loop
, bb
))
1515 if (init_cond
== chrec_not_analyzed_yet
)
1521 if (TREE_CODE (branch
) == SSA_NAME
)
1523 init_cond
= chrec_dont_know
;
1527 init_cond
= chrec_merge (init_cond
, branch
);
1530 /* Ooops -- a loop without an entry??? */
1531 if (init_cond
== chrec_not_analyzed_yet
)
1532 init_cond
= chrec_dont_know
;
1534 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1535 to not miss important early loop unrollings. */
1536 init_cond
= follow_copies_to_constant (init_cond
);
1538 if (dump_file
&& (dump_flags
& TDF_SCEV
))
1540 fprintf (dump_file
, " (init_cond = ");
1541 print_generic_expr (dump_file
, init_cond
);
1542 fprintf (dump_file
, "))\n");
1548 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1551 interpret_loop_phi (class loop
*loop
, gphi
*loop_phi_node
)
1554 class loop
*phi_loop
= loop_containing_stmt (loop_phi_node
);
1557 gcc_assert (phi_loop
== loop
);
1559 /* Otherwise really interpret the loop phi. */
1560 init_cond
= analyze_initial_condition (loop_phi_node
);
1561 res
= analyze_evolution_in_loop (loop_phi_node
, init_cond
);
1563 /* Verify we maintained the correct initial condition throughout
1564 possible conversions in the SSA chain. */
1565 if (res
!= chrec_dont_know
)
1567 tree new_init
= res
;
1568 if (CONVERT_EXPR_P (res
)
1569 && TREE_CODE (TREE_OPERAND (res
, 0)) == POLYNOMIAL_CHREC
)
1570 new_init
= fold_convert (TREE_TYPE (res
),
1571 CHREC_LEFT (TREE_OPERAND (res
, 0)));
1572 else if (TREE_CODE (res
) == POLYNOMIAL_CHREC
)
1573 new_init
= CHREC_LEFT (res
);
1574 STRIP_USELESS_TYPE_CONVERSION (new_init
);
1575 if (TREE_CODE (new_init
) == POLYNOMIAL_CHREC
1576 || !operand_equal_p (init_cond
, new_init
, 0))
1577 return chrec_dont_know
;
1583 /* This function merges the branches of a condition-phi-node,
1584 contained in the outermost loop, and whose arguments are already
1588 interpret_condition_phi (class loop
*loop
, gphi
*condition_phi
)
1590 int i
, n
= gimple_phi_num_args (condition_phi
);
1591 tree res
= chrec_not_analyzed_yet
;
1593 for (i
= 0; i
< n
; i
++)
1597 if (backedge_phi_arg_p (condition_phi
, i
))
1599 res
= chrec_dont_know
;
1603 branch_chrec
= analyze_scalar_evolution
1604 (loop
, PHI_ARG_DEF (condition_phi
, i
));
1606 res
= chrec_merge (res
, branch_chrec
);
1607 if (res
== chrec_dont_know
)
1614 /* Interpret the operation RHS1 OP RHS2. If we didn't
1615 analyze this node before, follow the definitions until ending
1616 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1617 return path, this function propagates evolutions (ala constant copy
1618 propagation). OPND1 is not a GIMPLE expression because we could
1619 analyze the effect of an inner loop: see interpret_loop_phi. */
1622 interpret_rhs_expr (class loop
*loop
, gimple
*at_stmt
,
1623 tree type
, tree rhs1
, enum tree_code code
, tree rhs2
)
1625 tree res
, chrec1
, chrec2
, ctype
;
1628 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1630 if (is_gimple_min_invariant (rhs1
))
1631 return chrec_convert (type
, rhs1
, at_stmt
);
1633 if (code
== SSA_NAME
)
1634 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1637 if (code
== ASSERT_EXPR
)
1639 rhs1
= ASSERT_EXPR_VAR (rhs1
);
1640 return chrec_convert (type
, analyze_scalar_evolution (loop
, rhs1
),
1648 if (TREE_CODE (TREE_OPERAND (rhs1
, 0)) == MEM_REF
1649 || handled_component_p (TREE_OPERAND (rhs1
, 0)))
1652 poly_int64 bitsize
, bitpos
;
1653 int unsignedp
, reversep
;
1659 base
= get_inner_reference (TREE_OPERAND (rhs1
, 0),
1660 &bitsize
, &bitpos
, &offset
, &mode
,
1661 &unsignedp
, &reversep
, &volatilep
);
1663 if (TREE_CODE (base
) == MEM_REF
)
1665 rhs2
= TREE_OPERAND (base
, 1);
1666 rhs1
= TREE_OPERAND (base
, 0);
1668 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1669 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1670 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1671 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1672 chrec1
= instantiate_parameters (loop
, chrec1
);
1673 chrec2
= instantiate_parameters (loop
, chrec2
);
1674 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1678 chrec1
= analyze_scalar_evolution_for_address_of (loop
, base
);
1679 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1683 if (offset
!= NULL_TREE
)
1685 chrec2
= analyze_scalar_evolution (loop
, offset
);
1686 chrec2
= chrec_convert (TREE_TYPE (offset
), chrec2
, at_stmt
);
1687 chrec2
= instantiate_parameters (loop
, chrec2
);
1688 res
= chrec_fold_plus (type
, res
, chrec2
);
1691 if (maybe_ne (bitpos
, 0))
1693 unitpos
= size_int (exact_div (bitpos
, BITS_PER_UNIT
));
1694 chrec3
= analyze_scalar_evolution (loop
, unitpos
);
1695 chrec3
= chrec_convert (TREE_TYPE (unitpos
), chrec3
, at_stmt
);
1696 chrec3
= instantiate_parameters (loop
, chrec3
);
1697 res
= chrec_fold_plus (type
, res
, chrec3
);
1701 res
= chrec_dont_know
;
1704 case POINTER_PLUS_EXPR
:
1705 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1706 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1707 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1708 chrec2
= chrec_convert (TREE_TYPE (rhs2
), chrec2
, at_stmt
);
1709 chrec1
= instantiate_parameters (loop
, chrec1
);
1710 chrec2
= instantiate_parameters (loop
, chrec2
);
1711 res
= chrec_fold_plus (type
, chrec1
, chrec2
);
1715 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1716 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1718 /* When the stmt is conditionally executed re-write the CHREC
1719 into a form that has well-defined behavior on overflow. */
1721 && INTEGRAL_TYPE_P (type
)
1722 && ! TYPE_OVERFLOW_WRAPS (type
)
1723 && ! dominated_by_p (CDI_DOMINATORS
, loop
->latch
,
1724 gimple_bb (at_stmt
)))
1725 ctype
= unsigned_type_for (type
);
1726 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1727 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1728 chrec1
= instantiate_parameters (loop
, chrec1
);
1729 chrec2
= instantiate_parameters (loop
, chrec2
);
1730 res
= chrec_fold_plus (ctype
, chrec1
, chrec2
);
1732 res
= chrec_convert (type
, res
, at_stmt
);
1736 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1737 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1739 /* When the stmt is conditionally executed re-write the CHREC
1740 into a form that has well-defined behavior on overflow. */
1742 && INTEGRAL_TYPE_P (type
)
1743 && ! TYPE_OVERFLOW_WRAPS (type
)
1744 && ! dominated_by_p (CDI_DOMINATORS
,
1745 loop
->latch
, gimple_bb (at_stmt
)))
1746 ctype
= unsigned_type_for (type
);
1747 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1748 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1749 chrec1
= instantiate_parameters (loop
, chrec1
);
1750 chrec2
= instantiate_parameters (loop
, chrec2
);
1751 res
= chrec_fold_minus (ctype
, chrec1
, chrec2
);
1753 res
= chrec_convert (type
, res
, at_stmt
);
1757 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1759 /* When the stmt is conditionally executed re-write the CHREC
1760 into a form that has well-defined behavior on overflow. */
1762 && INTEGRAL_TYPE_P (type
)
1763 && ! TYPE_OVERFLOW_WRAPS (type
)
1764 && ! dominated_by_p (CDI_DOMINATORS
,
1765 loop
->latch
, gimple_bb (at_stmt
)))
1766 ctype
= unsigned_type_for (type
);
1767 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1768 /* TYPE may be integer, real or complex, so use fold_convert. */
1769 chrec1
= instantiate_parameters (loop
, chrec1
);
1770 res
= chrec_fold_multiply (ctype
, chrec1
,
1771 fold_convert (ctype
, integer_minus_one_node
));
1773 res
= chrec_convert (type
, res
, at_stmt
);
1777 /* Handle ~X as -1 - X. */
1778 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1779 chrec1
= chrec_convert (type
, chrec1
, at_stmt
);
1780 chrec1
= instantiate_parameters (loop
, chrec1
);
1781 res
= chrec_fold_minus (type
,
1782 fold_convert (type
, integer_minus_one_node
),
1787 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1788 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1790 /* When the stmt is conditionally executed re-write the CHREC
1791 into a form that has well-defined behavior on overflow. */
1793 && INTEGRAL_TYPE_P (type
)
1794 && ! TYPE_OVERFLOW_WRAPS (type
)
1795 && ! dominated_by_p (CDI_DOMINATORS
,
1796 loop
->latch
, gimple_bb (at_stmt
)))
1797 ctype
= unsigned_type_for (type
);
1798 chrec1
= chrec_convert (ctype
, chrec1
, at_stmt
);
1799 chrec2
= chrec_convert (ctype
, chrec2
, at_stmt
);
1800 chrec1
= instantiate_parameters (loop
, chrec1
);
1801 chrec2
= instantiate_parameters (loop
, chrec2
);
1802 res
= chrec_fold_multiply (ctype
, chrec1
, chrec2
);
1804 res
= chrec_convert (type
, res
, at_stmt
);
1809 /* Handle A<<B as A * (1<<B). */
1810 tree uns
= unsigned_type_for (type
);
1811 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1812 chrec2
= analyze_scalar_evolution (loop
, rhs2
);
1813 chrec1
= chrec_convert (uns
, chrec1
, at_stmt
);
1814 chrec1
= instantiate_parameters (loop
, chrec1
);
1815 chrec2
= instantiate_parameters (loop
, chrec2
);
1817 tree one
= build_int_cst (uns
, 1);
1818 chrec2
= fold_build2 (LSHIFT_EXPR
, uns
, one
, chrec2
);
1819 res
= chrec_fold_multiply (uns
, chrec1
, chrec2
);
1820 res
= chrec_convert (type
, res
, at_stmt
);
1825 /* In case we have a truncation of a widened operation that in
1826 the truncated type has undefined overflow behavior analyze
1827 the operation done in an unsigned type of the same precision
1828 as the final truncation. We cannot derive a scalar evolution
1829 for the widened operation but for the truncated result. */
1830 if (TREE_CODE (type
) == INTEGER_TYPE
1831 && TREE_CODE (TREE_TYPE (rhs1
)) == INTEGER_TYPE
1832 && TYPE_PRECISION (type
) < TYPE_PRECISION (TREE_TYPE (rhs1
))
1833 && TYPE_OVERFLOW_UNDEFINED (type
)
1834 && TREE_CODE (rhs1
) == SSA_NAME
1835 && (def
= SSA_NAME_DEF_STMT (rhs1
))
1836 && is_gimple_assign (def
)
1837 && TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) == tcc_binary
1838 && TREE_CODE (gimple_assign_rhs2 (def
)) == INTEGER_CST
)
1840 tree utype
= unsigned_type_for (type
);
1841 chrec1
= interpret_rhs_expr (loop
, at_stmt
, utype
,
1842 gimple_assign_rhs1 (def
),
1843 gimple_assign_rhs_code (def
),
1844 gimple_assign_rhs2 (def
));
1847 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1848 res
= chrec_convert (type
, chrec1
, at_stmt
, true, rhs1
);
1852 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1853 If A is SCEV and its value is in the range of representable set
1854 of type unsigned short, the result expression is a (no-overflow)
1856 res
= chrec_dont_know
;
1857 if (tree_fits_uhwi_p (rhs2
))
1860 unsigned HOST_WIDE_INT val
= tree_to_uhwi (rhs2
);
1863 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1864 it's not the maximum value of a smaller type than rhs1. */
1866 && (precision
= exact_log2 (val
)) > 0
1867 && (unsigned) precision
< TYPE_PRECISION (TREE_TYPE (rhs1
)))
1869 tree utype
= build_nonstandard_integer_type (precision
, 1);
1871 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (TREE_TYPE (rhs1
)))
1873 chrec1
= analyze_scalar_evolution (loop
, rhs1
);
1874 chrec1
= chrec_convert (utype
, chrec1
, at_stmt
);
1875 res
= chrec_convert (TREE_TYPE (rhs1
), chrec1
, at_stmt
);
1882 res
= chrec_dont_know
;
1889 /* Interpret the expression EXPR. */
1892 interpret_expr (class loop
*loop
, gimple
*at_stmt
, tree expr
)
1894 enum tree_code code
;
1895 tree type
= TREE_TYPE (expr
), op0
, op1
;
1897 if (automatically_generated_chrec_p (expr
))
1900 if (TREE_CODE (expr
) == POLYNOMIAL_CHREC
1901 || TREE_CODE (expr
) == CALL_EXPR
1902 || get_gimple_rhs_class (TREE_CODE (expr
)) == GIMPLE_TERNARY_RHS
)
1903 return chrec_dont_know
;
1905 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1907 return interpret_rhs_expr (loop
, at_stmt
, type
,
1911 /* Interpret the rhs of the assignment STMT. */
1914 interpret_gimple_assign (class loop
*loop
, gimple
*stmt
)
1916 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1917 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1919 return interpret_rhs_expr (loop
, stmt
, type
,
1920 gimple_assign_rhs1 (stmt
), code
,
1921 gimple_assign_rhs2 (stmt
));
1926 /* This section contains all the entry points:
1927 - number_of_iterations_in_loop,
1928 - analyze_scalar_evolution,
1929 - instantiate_parameters.
1932 /* Helper recursive function. */
1935 analyze_scalar_evolution_1 (class loop
*loop
, tree var
)
1939 class loop
*def_loop
;
1942 if (TREE_CODE (var
) != SSA_NAME
)
1943 return interpret_expr (loop
, NULL
, var
);
1945 def
= SSA_NAME_DEF_STMT (var
);
1946 bb
= gimple_bb (def
);
1947 def_loop
= bb
->loop_father
;
1949 if (!flow_bb_inside_loop_p (loop
, bb
))
1951 /* Keep symbolic form, but look through obvious copies for constants. */
1952 res
= follow_copies_to_constant (var
);
1956 if (loop
!= def_loop
)
1958 res
= analyze_scalar_evolution_1 (def_loop
, var
);
1959 class loop
*loop_to_skip
= superloop_at_depth (def_loop
,
1960 loop_depth (loop
) + 1);
1961 res
= compute_overall_effect_of_inner_loop (loop_to_skip
, res
);
1962 if (chrec_contains_symbols_defined_in_loop (res
, loop
->num
))
1963 res
= analyze_scalar_evolution_1 (loop
, res
);
1967 switch (gimple_code (def
))
1970 res
= interpret_gimple_assign (loop
, def
);
1974 if (loop_phi_node_p (def
))
1975 res
= interpret_loop_phi (loop
, as_a
<gphi
*> (def
));
1977 res
= interpret_condition_phi (loop
, as_a
<gphi
*> (def
));
1981 res
= chrec_dont_know
;
1987 /* Keep the symbolic form. */
1988 if (res
== chrec_dont_know
)
1991 if (loop
== def_loop
)
1992 set_scalar_evolution (block_before_loop (loop
), var
, res
);
1997 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1998 LOOP. LOOP is the loop in which the variable is used.
2000 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2001 pointer to the statement that uses this variable, in order to
2002 determine the evolution function of the variable, use the following
2005 loop_p loop = loop_containing_stmt (stmt);
2006 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2007 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2011 analyze_scalar_evolution (class loop
*loop
, tree var
)
2015 /* ??? Fix callers. */
2019 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2021 fprintf (dump_file
, "(analyze_scalar_evolution \n");
2022 fprintf (dump_file
, " (loop_nb = %d)\n", loop
->num
);
2023 fprintf (dump_file
, " (scalar = ");
2024 print_generic_expr (dump_file
, var
);
2025 fprintf (dump_file
, ")\n");
2028 res
= get_scalar_evolution (block_before_loop (loop
), var
);
2029 if (res
== chrec_not_analyzed_yet
)
2031 /* We'll recurse into instantiate_scev, avoid tearing down the
2032 instantiate cache repeatedly and keep it live from here. */
2036 global_cache
= new instantiate_cache_type
;
2039 res
= analyze_scalar_evolution_1 (loop
, var
);
2042 delete global_cache
;
2043 global_cache
= NULL
;
2047 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2048 fprintf (dump_file
, ")\n");
2053 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2056 analyze_scalar_evolution_for_address_of (class loop
*loop
, tree var
)
2058 return analyze_scalar_evolution (loop
, build_fold_addr_expr (var
));
2061 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2062 WRTO_LOOP (which should be a superloop of USE_LOOP)
2064 FOLDED_CASTS is set to true if resolve_mixers used
2065 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2066 at the moment in order to keep things simple).
2068 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2071 for (i = 0; i < 100; i++) -- loop 1
2073 for (j = 0; j < 100; j++) -- loop 2
2080 for (t = 0; t < 100; t++) -- loop 3
2087 Both k1 and k2 are invariants in loop3, thus
2088 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2089 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2091 As they are invariant, it does not matter whether we consider their
2092 usage in loop 3 or loop 2, hence
2093 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2094 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2095 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2096 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2098 Similarly for their evolutions with respect to loop 1. The values of K2
2099 in the use in loop 2 vary independently on loop 1, thus we cannot express
2100 the evolution with respect to loop 1:
2101 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2102 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2103 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2104 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2106 The value of k2 in the use in loop 1 is known, though:
2107 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2108 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2112 analyze_scalar_evolution_in_loop (class loop
*wrto_loop
, class loop
*use_loop
,
2113 tree version
, bool *folded_casts
)
2116 tree ev
= version
, tmp
;
2118 /* We cannot just do
2120 tmp = analyze_scalar_evolution (use_loop, version);
2121 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2123 as resolve_mixers would query the scalar evolution with respect to
2124 wrto_loop. For example, in the situation described in the function
2125 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2128 analyze_scalar_evolution (use_loop, version) = k2
2130 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2131 k2 in loop 1 is 100, which is a wrong result, since we are interested
2132 in the value in loop 3.
2134 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2135 each time checking that there is no evolution in the inner loop. */
2138 *folded_casts
= false;
2141 tmp
= analyze_scalar_evolution (use_loop
, ev
);
2142 ev
= resolve_mixers (use_loop
, tmp
, folded_casts
);
2144 if (use_loop
== wrto_loop
)
2147 /* If the value of the use changes in the inner loop, we cannot express
2148 its value in the outer loop (we might try to return interval chrec,
2149 but we do not have a user for it anyway) */
2150 if (!no_evolution_in_loop_p (ev
, use_loop
->num
, &val
)
2152 return chrec_dont_know
;
2154 use_loop
= loop_outer (use_loop
);
2159 /* Computes a hash function for database element ELT. */
2161 static inline hashval_t
2162 hash_idx_scev_info (const void *elt_
)
2164 unsigned idx
= ((size_t) elt_
) - 2;
2165 return scev_info_hasher::hash (&global_cache
->entries
[idx
]);
2168 /* Compares database elements E1 and E2. */
2171 eq_idx_scev_info (const void *e1
, const void *e2
)
2173 unsigned idx1
= ((size_t) e1
) - 2;
2174 return scev_info_hasher::equal (&global_cache
->entries
[idx1
],
2175 (const scev_info_str
*) e2
);
2178 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2181 get_instantiated_value_entry (instantiate_cache_type
&cache
,
2182 tree name
, edge instantiate_below
)
2186 cache
.map
= htab_create (10, hash_idx_scev_info
, eq_idx_scev_info
, NULL
);
2187 cache
.entries
.create (10);
2191 e
.name_version
= SSA_NAME_VERSION (name
);
2192 e
.instantiated_below
= instantiate_below
->dest
->index
;
2193 void **slot
= htab_find_slot_with_hash (cache
.map
, &e
,
2194 scev_info_hasher::hash (&e
), INSERT
);
2197 e
.chrec
= chrec_not_analyzed_yet
;
2198 *slot
= (void *)(size_t)(cache
.entries
.length () + 2);
2199 cache
.entries
.safe_push (e
);
2202 return ((size_t)*slot
) - 2;
2206 /* Return the closed_loop_phi node for VAR. If there is none, return
2210 loop_closed_phi_def (tree var
)
2217 if (var
== NULL_TREE
2218 || TREE_CODE (var
) != SSA_NAME
)
2221 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (var
));
2222 exit
= single_exit (loop
);
2226 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2229 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == var
)
2230 return PHI_RESULT (phi
);
2236 static tree
instantiate_scev_r (edge
, class loop
*, class loop
*,
2239 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2240 and EVOLUTION_LOOP, that were left under a symbolic form.
2242 CHREC is an SSA_NAME to be instantiated.
2244 CACHE is the cache of already instantiated values.
2246 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2247 conversions that may wrap in signed/pointer type are folded, as long
2248 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2249 then we don't do such fold.
2251 SIZE_EXPR is used for computing the size of the expression to be
2252 instantiated, and to stop if it exceeds some limit. */
2255 instantiate_scev_name (edge instantiate_below
,
2256 class loop
*evolution_loop
, class loop
*inner_loop
,
2258 bool *fold_conversions
,
2262 class loop
*def_loop
;
2263 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (chrec
));
2265 /* A parameter, nothing to do. */
2267 || !dominated_by_p (CDI_DOMINATORS
, def_bb
, instantiate_below
->dest
))
2270 /* We cache the value of instantiated variable to avoid exponential
2271 time complexity due to reevaluations. We also store the convenient
2272 value in the cache in order to prevent infinite recursion -- we do
2273 not want to instantiate the SSA_NAME if it is in a mixer
2274 structure. This is used for avoiding the instantiation of
2275 recursively defined functions, such as:
2277 | a_2 -> {0, +, 1, +, a_2}_1 */
2279 unsigned si
= get_instantiated_value_entry (*global_cache
,
2280 chrec
, instantiate_below
);
2281 if (global_cache
->get (si
) != chrec_not_analyzed_yet
)
2282 return global_cache
->get (si
);
2284 /* On recursion return chrec_dont_know. */
2285 global_cache
->set (si
, chrec_dont_know
);
2287 def_loop
= find_common_loop (evolution_loop
, def_bb
->loop_father
);
2289 if (! dominated_by_p (CDI_DOMINATORS
,
2290 def_loop
->header
, instantiate_below
->dest
))
2292 gimple
*def
= SSA_NAME_DEF_STMT (chrec
);
2293 if (gassign
*ass
= dyn_cast
<gassign
*> (def
))
2295 switch (gimple_assign_rhs_class (ass
))
2297 case GIMPLE_UNARY_RHS
:
2299 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2300 inner_loop
, gimple_assign_rhs1 (ass
),
2301 fold_conversions
, size_expr
);
2302 if (op0
== chrec_dont_know
)
2303 return chrec_dont_know
;
2304 res
= fold_build1 (gimple_assign_rhs_code (ass
),
2305 TREE_TYPE (chrec
), op0
);
2308 case GIMPLE_BINARY_RHS
:
2310 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2311 inner_loop
, gimple_assign_rhs1 (ass
),
2312 fold_conversions
, size_expr
);
2313 if (op0
== chrec_dont_know
)
2314 return chrec_dont_know
;
2315 tree op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2316 inner_loop
, gimple_assign_rhs2 (ass
),
2317 fold_conversions
, size_expr
);
2318 if (op1
== chrec_dont_know
)
2319 return chrec_dont_know
;
2320 res
= fold_build2 (gimple_assign_rhs_code (ass
),
2321 TREE_TYPE (chrec
), op0
, op1
);
2325 res
= chrec_dont_know
;
2329 res
= chrec_dont_know
;
2330 global_cache
->set (si
, res
);
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
,
2366 gimple_bb (SSA_NAME_DEF_STMT (res
)),
2367 instantiate_below
->dest
))
2368 res
= chrec_dont_know
;
2371 else if (res
!= chrec_dont_know
)
2374 && def_bb
->loop_father
!= inner_loop
2375 && !flow_loop_nested_p (def_bb
->loop_father
, inner_loop
))
2376 /* ??? We could try to compute the overall effect of the loop here. */
2377 res
= chrec_dont_know
;
2379 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2381 fold_conversions
, size_expr
);
2384 /* Store the correct value to the cache. */
2385 global_cache
->set (si
, res
);
2389 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2390 and EVOLUTION_LOOP, that were left under a symbolic form.
2392 CHREC is a polynomial chain of recurrence to be instantiated.
2394 CACHE is the cache of already instantiated values.
2396 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2397 conversions that may wrap in signed/pointer type are folded, as long
2398 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2399 then we don't do such fold.
2401 SIZE_EXPR is used for computing the size of the expression to be
2402 instantiated, and to stop if it exceeds some limit. */
2405 instantiate_scev_poly (edge instantiate_below
,
2406 class loop
*evolution_loop
, class loop
*,
2407 tree chrec
, bool *fold_conversions
, int size_expr
)
2410 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2411 get_chrec_loop (chrec
),
2412 CHREC_LEFT (chrec
), fold_conversions
,
2414 if (op0
== chrec_dont_know
)
2415 return chrec_dont_know
;
2417 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2418 get_chrec_loop (chrec
),
2419 CHREC_RIGHT (chrec
), fold_conversions
,
2421 if (op1
== chrec_dont_know
)
2422 return chrec_dont_know
;
2424 if (CHREC_LEFT (chrec
) != op0
2425 || CHREC_RIGHT (chrec
) != op1
)
2427 op1
= chrec_convert_rhs (chrec_type (op0
), op1
, NULL
);
2428 chrec
= build_polynomial_chrec (CHREC_VARIABLE (chrec
), op0
, op1
);
2434 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2435 and EVOLUTION_LOOP, that were left under a symbolic form.
2437 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2439 CACHE is the cache of already instantiated values.
2441 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2442 conversions that may wrap in signed/pointer type are folded, as long
2443 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2444 then we don't do such fold.
2446 SIZE_EXPR is used for computing the size of the expression to be
2447 instantiated, and to stop if it exceeds some limit. */
2450 instantiate_scev_binary (edge instantiate_below
,
2451 class loop
*evolution_loop
, class loop
*inner_loop
,
2452 tree chrec
, enum tree_code code
,
2453 tree type
, tree c0
, tree c1
,
2454 bool *fold_conversions
, int size_expr
)
2457 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2458 c0
, fold_conversions
, size_expr
);
2459 if (op0
== chrec_dont_know
)
2460 return chrec_dont_know
;
2462 /* While we eventually compute the same op1 if c0 == c1 the process
2463 of doing this is expensive so the following short-cut prevents
2464 exponential compile-time behavior. */
2467 op1
= instantiate_scev_r (instantiate_below
, evolution_loop
, inner_loop
,
2468 c1
, fold_conversions
, size_expr
);
2469 if (op1
== chrec_dont_know
)
2470 return chrec_dont_know
;
2478 op0
= chrec_convert (type
, op0
, NULL
);
2479 op1
= chrec_convert_rhs (type
, op1
, NULL
);
2483 case POINTER_PLUS_EXPR
:
2485 return chrec_fold_plus (type
, op0
, op1
);
2488 return chrec_fold_minus (type
, op0
, op1
);
2491 return chrec_fold_multiply (type
, op0
, op1
);
2498 return chrec
? chrec
: fold_build2 (code
, type
, c0
, c1
);
2501 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2502 and EVOLUTION_LOOP, that were left under a symbolic form.
2504 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2507 CACHE is the cache of already instantiated values.
2509 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2510 conversions that may wrap in signed/pointer type are folded, as long
2511 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2512 then we don't do such fold.
2514 SIZE_EXPR is used for computing the size of the expression to be
2515 instantiated, and to stop if it exceeds some limit. */
2518 instantiate_scev_convert (edge instantiate_below
,
2519 class loop
*evolution_loop
, class loop
*inner_loop
,
2520 tree chrec
, tree type
, tree op
,
2521 bool *fold_conversions
, int size_expr
)
2523 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2525 fold_conversions
, size_expr
);
2527 if (op0
== chrec_dont_know
)
2528 return chrec_dont_know
;
2530 if (fold_conversions
)
2532 tree tmp
= chrec_convert_aggressive (type
, op0
, fold_conversions
);
2536 /* If we used chrec_convert_aggressive, we can no longer assume that
2537 signed chrecs do not overflow, as chrec_convert does, so avoid
2538 calling it in that case. */
2539 if (*fold_conversions
)
2541 if (chrec
&& op0
== op
)
2544 return fold_convert (type
, op0
);
2548 return chrec_convert (type
, op0
, NULL
);
2551 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2552 and EVOLUTION_LOOP, that were left under a symbolic form.
2554 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2555 Handle ~X as -1 - X.
2556 Handle -X as -1 * X.
2558 CACHE is the cache of already instantiated values.
2560 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2561 conversions that may wrap in signed/pointer type are folded, as long
2562 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2563 then we don't do such fold.
2565 SIZE_EXPR is used for computing the size of the expression to be
2566 instantiated, and to stop if it exceeds some limit. */
2569 instantiate_scev_not (edge instantiate_below
,
2570 class loop
*evolution_loop
, class loop
*inner_loop
,
2572 enum tree_code code
, tree type
, tree op
,
2573 bool *fold_conversions
, int size_expr
)
2575 tree op0
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2577 fold_conversions
, size_expr
);
2579 if (op0
== chrec_dont_know
)
2580 return chrec_dont_know
;
2584 op0
= chrec_convert (type
, op0
, NULL
);
2589 return chrec_fold_minus
2590 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2593 return chrec_fold_multiply
2594 (type
, fold_convert (type
, integer_minus_one_node
), op0
);
2601 return chrec
? chrec
: fold_build1 (code
, type
, op0
);
2604 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2605 and EVOLUTION_LOOP, that were left under a symbolic form.
2607 CHREC is the scalar evolution to instantiate.
2609 CACHE is the cache of already instantiated values.
2611 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2612 conversions that may wrap in signed/pointer type are folded, as long
2613 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2614 then we don't do such fold.
2616 SIZE_EXPR is used for computing the size of the expression to be
2617 instantiated, and to stop if it exceeds some limit. */
2620 instantiate_scev_r (edge instantiate_below
,
2621 class loop
*evolution_loop
, class loop
*inner_loop
,
2623 bool *fold_conversions
, int size_expr
)
2625 /* Give up if the expression is larger than the MAX that we allow. */
2626 if (size_expr
++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
2627 return chrec_dont_know
;
2629 if (chrec
== NULL_TREE
2630 || automatically_generated_chrec_p (chrec
)
2631 || is_gimple_min_invariant (chrec
))
2634 switch (TREE_CODE (chrec
))
2637 return instantiate_scev_name (instantiate_below
, evolution_loop
,
2639 fold_conversions
, size_expr
);
2641 case POLYNOMIAL_CHREC
:
2642 return instantiate_scev_poly (instantiate_below
, evolution_loop
,
2644 fold_conversions
, size_expr
);
2646 case POINTER_PLUS_EXPR
:
2650 return instantiate_scev_binary (instantiate_below
, evolution_loop
,
2652 TREE_CODE (chrec
), chrec_type (chrec
),
2653 TREE_OPERAND (chrec
, 0),
2654 TREE_OPERAND (chrec
, 1),
2655 fold_conversions
, size_expr
);
2658 return instantiate_scev_convert (instantiate_below
, evolution_loop
,
2660 TREE_TYPE (chrec
), TREE_OPERAND (chrec
, 0),
2661 fold_conversions
, size_expr
);
2665 return instantiate_scev_not (instantiate_below
, evolution_loop
,
2667 TREE_CODE (chrec
), TREE_TYPE (chrec
),
2668 TREE_OPERAND (chrec
, 0),
2669 fold_conversions
, size_expr
);
2672 if (is_gimple_min_invariant (chrec
))
2675 case SCEV_NOT_KNOWN
:
2676 return chrec_dont_know
;
2682 if (CONSTANT_CLASS_P (chrec
))
2684 return chrec_dont_know
;
2688 /* Analyze all the parameters of the chrec that were left under a
2689 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2690 recursive instantiation of parameters: a parameter is a variable
2691 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2692 a function parameter. */
2695 instantiate_scev (edge instantiate_below
, class loop
*evolution_loop
,
2700 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2702 fprintf (dump_file
, "(instantiate_scev \n");
2703 fprintf (dump_file
, " (instantiate_below = %d -> %d)\n",
2704 instantiate_below
->src
->index
, instantiate_below
->dest
->index
);
2706 fprintf (dump_file
, " (evolution_loop = %d)\n", evolution_loop
->num
);
2707 fprintf (dump_file
, " (chrec = ");
2708 print_generic_expr (dump_file
, chrec
);
2709 fprintf (dump_file
, ")\n");
2715 global_cache
= new instantiate_cache_type
;
2719 res
= instantiate_scev_r (instantiate_below
, evolution_loop
,
2720 NULL
, chrec
, NULL
, 0);
2724 delete global_cache
;
2725 global_cache
= NULL
;
2728 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2730 fprintf (dump_file
, " (res = ");
2731 print_generic_expr (dump_file
, res
);
2732 fprintf (dump_file
, "))\n");
2738 /* Similar to instantiate_parameters, but does not introduce the
2739 evolutions in outer loops for LOOP invariants in CHREC, and does not
2740 care about causing overflows, as long as they do not affect value
2741 of an expression. */
2744 resolve_mixers (class loop
*loop
, tree chrec
, bool *folded_casts
)
2747 bool fold_conversions
= false;
2750 global_cache
= new instantiate_cache_type
;
2754 tree ret
= instantiate_scev_r (loop_preheader_edge (loop
), loop
, NULL
,
2755 chrec
, &fold_conversions
, 0);
2757 if (folded_casts
&& !*folded_casts
)
2758 *folded_casts
= fold_conversions
;
2762 delete global_cache
;
2763 global_cache
= NULL
;
2769 /* Entry point for the analysis of the number of iterations pass.
2770 This function tries to safely approximate the number of iterations
2771 the loop will run. When this property is not decidable at compile
2772 time, the result is chrec_dont_know. Otherwise the result is a
2773 scalar or a symbolic parameter. When the number of iterations may
2774 be equal to zero and the property cannot be determined at compile
2775 time, the result is a COND_EXPR that represents in a symbolic form
2776 the conditions under which the number of iterations is not zero.
2778 Example of analysis: suppose that the loop has an exit condition:
2780 "if (b > 49) goto end_loop;"
2782 and that in a previous analysis we have determined that the
2783 variable 'b' has an evolution function:
2785 "EF = {23, +, 5}_2".
2787 When we evaluate the function at the point 5, i.e. the value of the
2788 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2789 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2790 the loop body has been executed 6 times. */
2793 number_of_latch_executions (class loop
*loop
)
2796 class tree_niter_desc niter_desc
;
2800 /* Determine whether the number of iterations in loop has already
2802 res
= loop
->nb_iterations
;
2806 may_be_zero
= NULL_TREE
;
2808 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2809 fprintf (dump_file
, "(number_of_iterations_in_loop = \n");
2811 res
= chrec_dont_know
;
2812 exit
= single_exit (loop
);
2814 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
2816 may_be_zero
= niter_desc
.may_be_zero
;
2817 res
= niter_desc
.niter
;
2820 if (res
== chrec_dont_know
2822 || integer_zerop (may_be_zero
))
2824 else if (integer_nonzerop (may_be_zero
))
2825 res
= build_int_cst (TREE_TYPE (res
), 0);
2827 else if (COMPARISON_CLASS_P (may_be_zero
))
2828 res
= fold_build3 (COND_EXPR
, TREE_TYPE (res
), may_be_zero
,
2829 build_int_cst (TREE_TYPE (res
), 0), res
);
2831 res
= chrec_dont_know
;
2833 if (dump_file
&& (dump_flags
& TDF_SCEV
))
2835 fprintf (dump_file
, " (set_nb_iterations_in_loop = ");
2836 print_generic_expr (dump_file
, res
);
2837 fprintf (dump_file
, "))\n");
2840 loop
->nb_iterations
= res
;
2845 /* Counters for the stats. */
2851 unsigned nb_affine_multivar
;
2852 unsigned nb_higher_poly
;
2853 unsigned nb_chrec_dont_know
;
2854 unsigned nb_undetermined
;
2857 /* Reset the counters. */
2860 reset_chrecs_counters (struct chrec_stats
*stats
)
2862 stats
->nb_chrecs
= 0;
2863 stats
->nb_affine
= 0;
2864 stats
->nb_affine_multivar
= 0;
2865 stats
->nb_higher_poly
= 0;
2866 stats
->nb_chrec_dont_know
= 0;
2867 stats
->nb_undetermined
= 0;
2870 /* Dump the contents of a CHREC_STATS structure. */
2873 dump_chrecs_stats (FILE *file
, struct chrec_stats
*stats
)
2875 fprintf (file
, "\n(\n");
2876 fprintf (file
, "-----------------------------------------\n");
2877 fprintf (file
, "%d\taffine univariate chrecs\n", stats
->nb_affine
);
2878 fprintf (file
, "%d\taffine multivariate chrecs\n", stats
->nb_affine_multivar
);
2879 fprintf (file
, "%d\tdegree greater than 2 polynomials\n",
2880 stats
->nb_higher_poly
);
2881 fprintf (file
, "%d\tchrec_dont_know chrecs\n", stats
->nb_chrec_dont_know
);
2882 fprintf (file
, "-----------------------------------------\n");
2883 fprintf (file
, "%d\ttotal chrecs\n", stats
->nb_chrecs
);
2884 fprintf (file
, "%d\twith undetermined coefficients\n",
2885 stats
->nb_undetermined
);
2886 fprintf (file
, "-----------------------------------------\n");
2887 fprintf (file
, "%d\tchrecs in the scev database\n",
2888 (int) scalar_evolution_info
->elements ());
2889 fprintf (file
, "%d\tsets in the scev database\n", nb_set_scev
);
2890 fprintf (file
, "%d\tgets in the scev database\n", nb_get_scev
);
2891 fprintf (file
, "-----------------------------------------\n");
2892 fprintf (file
, ")\n\n");
2895 /* Gather statistics about CHREC. */
2898 gather_chrec_stats (tree chrec
, struct chrec_stats
*stats
)
2900 if (dump_file
&& (dump_flags
& TDF_STATS
))
2902 fprintf (dump_file
, "(classify_chrec ");
2903 print_generic_expr (dump_file
, chrec
);
2904 fprintf (dump_file
, "\n");
2909 if (chrec
== NULL_TREE
)
2911 stats
->nb_undetermined
++;
2915 switch (TREE_CODE (chrec
))
2917 case POLYNOMIAL_CHREC
:
2918 if (evolution_function_is_affine_p (chrec
))
2920 if (dump_file
&& (dump_flags
& TDF_STATS
))
2921 fprintf (dump_file
, " affine_univariate\n");
2924 else if (evolution_function_is_affine_multivariate_p (chrec
, 0))
2926 if (dump_file
&& (dump_flags
& TDF_STATS
))
2927 fprintf (dump_file
, " affine_multivariate\n");
2928 stats
->nb_affine_multivar
++;
2932 if (dump_file
&& (dump_flags
& TDF_STATS
))
2933 fprintf (dump_file
, " higher_degree_polynomial\n");
2934 stats
->nb_higher_poly
++;
2943 if (chrec_contains_undetermined (chrec
))
2945 if (dump_file
&& (dump_flags
& TDF_STATS
))
2946 fprintf (dump_file
, " undetermined\n");
2947 stats
->nb_undetermined
++;
2950 if (dump_file
&& (dump_flags
& TDF_STATS
))
2951 fprintf (dump_file
, ")\n");
2954 /* Classify the chrecs of the whole database. */
2957 gather_stats_on_scev_database (void)
2959 struct chrec_stats stats
;
2964 reset_chrecs_counters (&stats
);
2966 hash_table
<scev_info_hasher
>::iterator iter
;
2968 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info
, elt
, scev_info_str
*,
2970 gather_chrec_stats (elt
->chrec
, &stats
);
2972 dump_chrecs_stats (dump_file
, &stats
);
2976 /* Initialize the analysis of scalar evolutions for LOOPS. */
2979 scev_initialize (void)
2983 gcc_assert (! scev_initialized_p ());
2985 scalar_evolution_info
= hash_table
<scev_info_hasher
>::create_ggc (100);
2987 FOR_EACH_LOOP (loop
, 0)
2989 loop
->nb_iterations
= NULL_TREE
;
2993 /* Return true if SCEV is initialized. */
2996 scev_initialized_p (void)
2998 return scalar_evolution_info
!= NULL
;
3001 /* Cleans up the information cached by the scalar evolutions analysis
3002 in the hash table. */
3005 scev_reset_htab (void)
3007 if (!scalar_evolution_info
)
3010 scalar_evolution_info
->empty ();
3013 /* Cleans up the information cached by the scalar evolutions analysis
3014 in the hash table and in the loop->nb_iterations. */
3023 FOR_EACH_LOOP (loop
, 0)
3025 loop
->nb_iterations
= NULL_TREE
;
3029 /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3030 of the upper bound on the number of iterations of LOOP, the BASE and STEP
3033 We do not use information whether TYPE can overflow so it is safe to
3034 use this test even for derived IVs not computed every iteration or
3035 hypotetical IVs to be inserted into code. */
3038 iv_can_overflow_p (class loop
*loop
, tree type
, tree base
, tree step
)
3041 wide_int base_min
, base_max
, step_min
, step_max
, type_min
, type_max
;
3042 signop sgn
= TYPE_SIGN (type
);
3044 if (integer_zerop (step
))
3047 if (TREE_CODE (base
) == INTEGER_CST
)
3048 base_min
= base_max
= wi::to_wide (base
);
3049 else if (TREE_CODE (base
) == SSA_NAME
3050 && INTEGRAL_TYPE_P (TREE_TYPE (base
))
3051 && get_range_info (base
, &base_min
, &base_max
) == VR_RANGE
)
3056 if (TREE_CODE (step
) == INTEGER_CST
)
3057 step_min
= step_max
= wi::to_wide (step
);
3058 else if (TREE_CODE (step
) == SSA_NAME
3059 && INTEGRAL_TYPE_P (TREE_TYPE (step
))
3060 && get_range_info (step
, &step_min
, &step_max
) == VR_RANGE
)
3065 if (!get_max_loop_iterations (loop
, &nit
))
3068 type_min
= wi::min_value (type
);
3069 type_max
= wi::max_value (type
);
3071 /* Just sanity check that we don't see values out of the range of the type.
3072 In this case the arithmetics bellow would overflow. */
3073 gcc_checking_assert (wi::ge_p (base_min
, type_min
, sgn
)
3074 && wi::le_p (base_max
, type_max
, sgn
));
3076 /* Account the possible increment in the last ieration. */
3077 wi::overflow_type overflow
= wi::OVF_NONE
;
3078 nit
= wi::add (nit
, 1, SIGNED
, &overflow
);
3082 /* NIT is typeless and can exceed the precision of the type. In this case
3083 overflow is always possible, because we know STEP is non-zero. */
3084 if (wi::min_precision (nit
, UNSIGNED
) > TYPE_PRECISION (type
))
3086 wide_int nit2
= wide_int::from (nit
, TYPE_PRECISION (type
), UNSIGNED
);
3088 /* If step can be positive, check that nit*step <= type_max-base.
3089 This can be done by unsigned arithmetic and we only need to watch overflow
3090 in the multiplication. The right hand side can always be represented in
3092 if (sgn
== UNSIGNED
|| !wi::neg_p (step_max
))
3094 wi::overflow_type overflow
= wi::OVF_NONE
;
3095 if (wi::gtu_p (wi::mul (step_max
, nit2
, UNSIGNED
, &overflow
),
3096 type_max
- base_max
)
3100 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3101 if (sgn
== SIGNED
&& wi::neg_p (step_min
))
3103 wi::overflow_type overflow
, overflow2
;
3104 overflow
= overflow2
= wi::OVF_NONE
;
3105 if (wi::gtu_p (wi::mul (wi::neg (step_min
, &overflow2
),
3106 nit2
, UNSIGNED
, &overflow
),
3107 base_min
- type_min
)
3108 || overflow
|| overflow2
)
3115 /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3116 function tries to derive condition under which it can be simplified
3117 into "{(type)inner_base, (type)inner_step}_loop". The condition is
3118 the maximum number that inner iv can iterate. */
3121 derive_simple_iv_with_niters (tree ev
, tree
*niters
)
3123 if (!CONVERT_EXPR_P (ev
))
3126 tree inner_ev
= TREE_OPERAND (ev
, 0);
3127 if (TREE_CODE (inner_ev
) != POLYNOMIAL_CHREC
)
3130 tree init
= CHREC_LEFT (inner_ev
);
3131 tree step
= CHREC_RIGHT (inner_ev
);
3132 if (TREE_CODE (init
) != INTEGER_CST
3133 || TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
3136 tree type
= TREE_TYPE (ev
);
3137 tree inner_type
= TREE_TYPE (inner_ev
);
3138 if (TYPE_PRECISION (inner_type
) >= TYPE_PRECISION (type
))
3141 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3142 folded only if inner iv won't overflow. We compute the maximum
3143 number the inner iv can iterate before overflowing and return the
3144 simplified affine iv. */
3146 init
= fold_convert (type
, init
);
3147 step
= fold_convert (type
, step
);
3148 ev
= build_polynomial_chrec (CHREC_VARIABLE (inner_ev
), init
, step
);
3149 if (tree_int_cst_sign_bit (step
))
3151 tree bound
= lower_bound_in_type (inner_type
, inner_type
);
3152 delta
= fold_build2 (MINUS_EXPR
, type
, init
, fold_convert (type
, bound
));
3153 step
= fold_build1 (NEGATE_EXPR
, type
, step
);
3157 tree bound
= upper_bound_in_type (inner_type
, inner_type
);
3158 delta
= fold_build2 (MINUS_EXPR
, type
, fold_convert (type
, bound
), init
);
3160 *niters
= fold_build2 (FLOOR_DIV_EXPR
, type
, delta
, step
);
3164 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3165 respect to WRTO_LOOP and returns its base and step in IV if possible
3166 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3167 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3168 invariant in LOOP. Otherwise we require it to be an integer constant.
3170 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3171 because it is computed in signed arithmetics). Consequently, adding an
3174 for (i = IV->base; ; i += IV->step)
3176 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3177 false for the type of the induction variable, or you can prove that i does
3178 not wrap by some other argument. Otherwise, this might introduce undefined
3182 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3184 must be used instead.
3186 When IV_NITERS is not NULL, this function also checks case in which OP
3187 is a conversion of an inner simple iv of below form:
3189 (outer_type){inner_base, inner_step}_loop.
3191 If type of inner iv has smaller precision than outer_type, it can't be
3192 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3193 the inner iv could overflow/wrap. In this case, we derive a condition
3194 under which the inner iv won't overflow/wrap and do the simplification.
3195 The derived condition normally is the maximum number the inner iv can
3196 iterate, and will be stored in IV_NITERS. This is useful in loop niter
3197 analysis, to derive break conditions when a loop must terminate, when is
3201 simple_iv_with_niters (class loop
*wrto_loop
, class loop
*use_loop
,
3202 tree op
, affine_iv
*iv
, tree
*iv_niters
,
3203 bool allow_nonconstant_step
)
3205 enum tree_code code
;
3206 tree type
, ev
, base
, e
;
3210 iv
->base
= NULL_TREE
;
3211 iv
->step
= NULL_TREE
;
3212 iv
->no_overflow
= false;
3214 type
= TREE_TYPE (op
);
3215 if (!POINTER_TYPE_P (type
)
3216 && !INTEGRAL_TYPE_P (type
))
3219 ev
= analyze_scalar_evolution_in_loop (wrto_loop
, use_loop
, op
,
3221 if (chrec_contains_undetermined (ev
)
3222 || chrec_contains_symbols_defined_in_loop (ev
, wrto_loop
->num
))
3225 if (tree_does_not_contain_chrecs (ev
))
3228 iv
->step
= build_int_cst (TREE_TYPE (ev
), 0);
3229 iv
->no_overflow
= true;
3233 /* If we can derive valid scalar evolution with assumptions. */
3234 if (iv_niters
&& TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
3235 ev
= derive_simple_iv_with_niters (ev
, iv_niters
);
3237 if (TREE_CODE (ev
) != POLYNOMIAL_CHREC
)
3240 if (CHREC_VARIABLE (ev
) != (unsigned) wrto_loop
->num
)
3243 iv
->step
= CHREC_RIGHT (ev
);
3244 if ((!allow_nonconstant_step
&& TREE_CODE (iv
->step
) != INTEGER_CST
)
3245 || tree_contains_chrecs (iv
->step
, NULL
))
3248 iv
->base
= CHREC_LEFT (ev
);
3249 if (tree_contains_chrecs (iv
->base
, NULL
))
3252 iv
->no_overflow
= !folded_casts
&& nowrap_type_p (type
);
3254 if (!iv
->no_overflow
3255 && !iv_can_overflow_p (wrto_loop
, type
, iv
->base
, iv
->step
))
3256 iv
->no_overflow
= true;
3258 /* Try to simplify iv base:
3260 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3261 == (signed T)(unsigned T)base + step
3264 If we can prove operation (base + step) doesn't overflow or underflow.
3265 Specifically, we try to prove below conditions are satisfied:
3267 base <= UPPER_BOUND (type) - step ;;step > 0
3268 base >= LOWER_BOUND (type) - step ;;step < 0
3270 This is done by proving the reverse conditions are false using loop's
3273 The is necessary to make loop niter, or iv overflow analysis easier
3276 int foo (int *a, signed char s, signed char l)
3279 for (i = s; i < l; i++)
3284 Note variable I is firstly converted to type unsigned char, incremented,
3285 then converted back to type signed char. */
3287 if (wrto_loop
->num
!= use_loop
->num
)
3290 if (!CONVERT_EXPR_P (iv
->base
) || TREE_CODE (iv
->step
) != INTEGER_CST
)
3293 type
= TREE_TYPE (iv
->base
);
3294 e
= TREE_OPERAND (iv
->base
, 0);
3295 if (TREE_CODE (e
) != PLUS_EXPR
3296 || TREE_CODE (TREE_OPERAND (e
, 1)) != INTEGER_CST
3297 || !tree_int_cst_equal (iv
->step
,
3298 fold_convert (type
, TREE_OPERAND (e
, 1))))
3300 e
= TREE_OPERAND (e
, 0);
3301 if (!CONVERT_EXPR_P (e
))
3303 base
= TREE_OPERAND (e
, 0);
3304 if (!useless_type_conversion_p (type
, TREE_TYPE (base
)))
3307 if (tree_int_cst_sign_bit (iv
->step
))
3310 extreme
= wi::min_value (type
);
3315 extreme
= wi::max_value (type
);
3317 wi::overflow_type overflow
= wi::OVF_NONE
;
3318 extreme
= wi::sub (extreme
, wi::to_wide (iv
->step
),
3319 TYPE_SIGN (type
), &overflow
);
3322 e
= fold_build2 (code
, boolean_type_node
, base
,
3323 wide_int_to_tree (type
, extreme
));
3324 e
= simplify_using_initial_conditions (use_loop
, e
);
3325 if (!integer_zerop (e
))
3328 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3329 code
= POINTER_PLUS_EXPR
;
3333 iv
->base
= fold_build2 (code
, TREE_TYPE (base
), base
, iv
->step
);
3337 /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3338 affine iv unconditionally. */
3341 simple_iv (class loop
*wrto_loop
, class loop
*use_loop
, tree op
,
3342 affine_iv
*iv
, bool allow_nonconstant_step
)
3344 return simple_iv_with_niters (wrto_loop
, use_loop
, op
, iv
,
3345 NULL
, allow_nonconstant_step
);
3348 /* Finalize the scalar evolution analysis. */
3351 scev_finalize (void)
3353 if (!scalar_evolution_info
)
3355 scalar_evolution_info
->empty ();
3356 scalar_evolution_info
= NULL
;
3357 free_numbers_of_iterations_estimates (cfun
);
3360 /* Returns true if the expression EXPR is considered to be too expensive
3361 for scev_const_prop. */
3364 expression_expensive_p (tree expr
, hash_map
<tree
, uint64_t> &cache
,
3367 enum tree_code code
;
3369 if (is_gimple_val (expr
))
3372 code
= TREE_CODE (expr
);
3373 if (code
== TRUNC_DIV_EXPR
3374 || code
== CEIL_DIV_EXPR
3375 || code
== FLOOR_DIV_EXPR
3376 || code
== ROUND_DIV_EXPR
3377 || code
== TRUNC_MOD_EXPR
3378 || code
== CEIL_MOD_EXPR
3379 || code
== FLOOR_MOD_EXPR
3380 || code
== ROUND_MOD_EXPR
3381 || code
== EXACT_DIV_EXPR
)
3383 /* Division by power of two is usually cheap, so we allow it.
3384 Forbid anything else. */
3385 if (!integer_pow2p (TREE_OPERAND (expr
, 1)))
3390 uint64_t &local_cost
= cache
.get_or_insert (expr
, &visited_p
);
3393 uint64_t tem
= cost
+ local_cost
;
3401 uint64_t op_cost
= 0;
3402 if (code
== CALL_EXPR
)
3405 call_expr_arg_iterator iter
;
3406 /* Even though is_inexpensive_builtin might say true, we will get a
3407 library call for popcount when backend does not have an instruction
3408 to do so. We consider this to be expenseive and generate
3409 __builtin_popcount only when backend defines it. */
3410 combined_fn cfn
= get_call_combined_fn (expr
);
3414 /* Check if opcode for popcount is available in the mode required. */
3415 if (optab_handler (popcount_optab
,
3416 TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr
, 0))))
3417 == CODE_FOR_nothing
)
3420 mode
= TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr
, 0)));
3421 scalar_int_mode int_mode
;
3423 /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
3424 double-word popcount by emitting two single-word popcount
3426 if (is_a
<scalar_int_mode
> (mode
, &int_mode
)
3427 && GET_MODE_SIZE (int_mode
) == 2 * UNITS_PER_WORD
3428 && (optab_handler (popcount_optab
, word_mode
)
3429 != CODE_FOR_nothing
))
3437 if (!is_inexpensive_builtin (get_callee_fndecl (expr
)))
3439 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
3440 if (expression_expensive_p (arg
, cache
, op_cost
))
3442 *cache
.get (expr
) += op_cost
;
3443 cost
+= op_cost
+ 1;
3447 if (code
== COND_EXPR
)
3449 if (expression_expensive_p (TREE_OPERAND (expr
, 0), cache
, op_cost
)
3450 || (EXPR_P (TREE_OPERAND (expr
, 1))
3451 && EXPR_P (TREE_OPERAND (expr
, 2)))
3452 /* If either branch has side effects or could trap. */
3453 || TREE_SIDE_EFFECTS (TREE_OPERAND (expr
, 1))
3454 || generic_expr_could_trap_p (TREE_OPERAND (expr
, 1))
3455 || TREE_SIDE_EFFECTS (TREE_OPERAND (expr
, 0))
3456 || generic_expr_could_trap_p (TREE_OPERAND (expr
, 0))
3457 || expression_expensive_p (TREE_OPERAND (expr
, 1),
3459 || expression_expensive_p (TREE_OPERAND (expr
, 2),
3462 *cache
.get (expr
) += op_cost
;
3463 cost
+= op_cost
+ 1;
3467 switch (TREE_CODE_CLASS (code
))
3470 case tcc_comparison
:
3471 if (expression_expensive_p (TREE_OPERAND (expr
, 1), cache
, op_cost
))
3476 if (expression_expensive_p (TREE_OPERAND (expr
, 0), cache
, op_cost
))
3478 *cache
.get (expr
) += op_cost
;
3479 cost
+= op_cost
+ 1;
3488 expression_expensive_p (tree expr
)
3490 hash_map
<tree
, uint64_t> cache
;
3491 uint64_t expanded_size
= 0;
3492 return (expression_expensive_p (expr
, cache
, expanded_size
)
3493 || expanded_size
> cache
.elements ());
3496 /* Do final value replacement for LOOP, return true if we did anything. */
3499 final_value_replacement_loop (class loop
*loop
)
3501 /* If we do not know exact number of iterations of the loop, we cannot
3502 replace the final value. */
3503 edge exit
= single_exit (loop
);
3507 tree niter
= number_of_latch_executions (loop
);
3508 if (niter
== chrec_dont_know
)
3511 /* Ensure that it is possible to insert new statements somewhere. */
3512 if (!single_pred_p (exit
->dest
))
3513 split_loop_exit_edge (exit
);
3515 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3516 gimple_stmt_iterator gsi
= gsi_after_labels (exit
->dest
);
3519 = superloop_at_depth (loop
,
3520 loop_depth (exit
->dest
->loop_father
) + 1);
3524 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); )
3526 gphi
*phi
= psi
.phi ();
3527 tree rslt
= PHI_RESULT (phi
);
3528 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
3529 if (virtual_operand_p (def
))
3535 if (!POINTER_TYPE_P (TREE_TYPE (def
))
3536 && !INTEGRAL_TYPE_P (TREE_TYPE (def
)))
3543 def
= analyze_scalar_evolution_in_loop (ex_loop
, loop
, def
,
3545 def
= compute_overall_effect_of_inner_loop (ex_loop
, def
);
3546 if (!tree_does_not_contain_chrecs (def
)
3547 || chrec_contains_symbols_defined_in_loop (def
, ex_loop
->num
)
3548 /* Moving the computation from the loop may prolong life range
3549 of some ssa names, which may cause problems if they appear
3550 on abnormal edges. */
3551 || contains_abnormal_ssa_name_p (def
)
3552 /* Do not emit expensive expressions. The rationale is that
3553 when someone writes a code like
3555 while (n > 45) n -= 45;
3557 he probably knows that n is not large, and does not want it
3558 to be turned into n %= 45. */
3559 || expression_expensive_p (def
))
3561 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3563 fprintf (dump_file
, "not replacing:\n ");
3564 print_gimple_stmt (dump_file
, phi
, 0);
3565 fprintf (dump_file
, "\n");
3571 /* Eliminate the PHI node and replace it by a computation outside
3575 fprintf (dump_file
, "\nfinal value replacement:\n ");
3576 print_gimple_stmt (dump_file
, phi
, 0);
3577 fprintf (dump_file
, " with expr: ");
3578 print_generic_expr (dump_file
, def
);
3581 def
= unshare_expr (def
);
3582 remove_phi_node (&psi
, false);
3584 /* If def's type has undefined overflow and there were folded
3585 casts, rewrite all stmts added for def into arithmetics
3586 with defined overflow behavior. */
3587 if (folded_casts
&& ANY_INTEGRAL_TYPE_P (TREE_TYPE (def
))
3588 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def
)))
3591 gimple_stmt_iterator gsi2
;
3592 def
= force_gimple_operand (def
, &stmts
, true, NULL_TREE
);
3593 gsi2
= gsi_start (stmts
);
3594 while (!gsi_end_p (gsi2
))
3596 gimple
*stmt
= gsi_stmt (gsi2
);
3597 gimple_stmt_iterator gsi3
= gsi2
;
3599 gsi_remove (&gsi3
, false);
3600 if (is_gimple_assign (stmt
)
3601 && arith_code_with_undefined_signed_overflow
3602 (gimple_assign_rhs_code (stmt
)))
3603 gsi_insert_seq_before (&gsi
,
3604 rewrite_to_defined_overflow (stmt
),
3607 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3611 def
= force_gimple_operand_gsi (&gsi
, def
, false, NULL_TREE
,
3612 true, GSI_SAME_STMT
);
3614 gassign
*ass
= gimple_build_assign (rslt
, def
);
3615 gimple_set_location (ass
,
3616 gimple_phi_arg_location (phi
, exit
->dest_idx
));
3617 gsi_insert_before (&gsi
, ass
, GSI_SAME_STMT
);
3620 fprintf (dump_file
, "\n final stmt:\n ");
3621 print_gimple_stmt (dump_file
, ass
, 0);
3622 fprintf (dump_file
, "\n");
3629 #include "gt-tree-scalar-evolution.h"