138fd1498Szrj /* Scalar evolution detector.
238fd1498Szrj Copyright (C) 2003-2018 Free Software Foundation, Inc.
338fd1498Szrj Contributed by Sebastian Pop <s.pop@laposte.net>
438fd1498Szrj
538fd1498Szrj This file is part of GCC.
638fd1498Szrj
738fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
838fd1498Szrj the terms of the GNU General Public License as published by the Free
938fd1498Szrj Software Foundation; either version 3, or (at your option) any later
1038fd1498Szrj version.
1138fd1498Szrj
1238fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1338fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
1438fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1538fd1498Szrj for more details.
1638fd1498Szrj
1738fd1498Szrj You should have received a copy of the GNU General Public License
1838fd1498Szrj along with GCC; see the file COPYING3. If not see
1938fd1498Szrj <http://www.gnu.org/licenses/>. */
2038fd1498Szrj
2138fd1498Szrj /*
2238fd1498Szrj Description:
2338fd1498Szrj
2438fd1498Szrj This pass analyzes the evolution of scalar variables in loop
2538fd1498Szrj structures. The algorithm is based on the SSA representation,
2638fd1498Szrj and on the loop hierarchy tree. This algorithm is not based on
2738fd1498Szrj the notion of versions of a variable, as it was the case for the
2838fd1498Szrj previous implementations of the scalar evolution algorithm, but
2938fd1498Szrj it assumes that each defined name is unique.
3038fd1498Szrj
3138fd1498Szrj The notation used in this file is called "chains of recurrences",
3238fd1498Szrj and has been proposed by Eugene Zima, Robert Van Engelen, and
3338fd1498Szrj others for describing induction variables in programs. For example
3438fd1498Szrj "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
3538fd1498Szrj when entering in the loop_1 and has a step 2 in this loop, in other
3638fd1498Szrj words "for (b = 0; b < N; b+=2);". Note that the coefficients of
3738fd1498Szrj this chain of recurrence (or chrec [shrek]) can contain the name of
3838fd1498Szrj other variables, in which case they are called parametric chrecs.
3938fd1498Szrj For example, "b -> {a, +, 2}_1" means that the initial value of "b"
4038fd1498Szrj is the value of "a". In most of the cases these parametric chrecs
4138fd1498Szrj are fully instantiated before their use because symbolic names can
4238fd1498Szrj hide some difficult cases such as self-references described later
4338fd1498Szrj (see the Fibonacci example).
4438fd1498Szrj
4538fd1498Szrj A short sketch of the algorithm is:
4638fd1498Szrj
4738fd1498Szrj Given a scalar variable to be analyzed, follow the SSA edge to
4838fd1498Szrj its definition:
4938fd1498Szrj
5038fd1498Szrj - When the definition is a GIMPLE_ASSIGN: if the right hand side
5138fd1498Szrj (RHS) of the definition cannot be statically analyzed, the answer
5238fd1498Szrj of the analyzer is: "don't know".
5338fd1498Szrj Otherwise, for all the variables that are not yet analyzed in the
5438fd1498Szrj RHS, try to determine their evolution, and finally try to
5538fd1498Szrj evaluate the operation of the RHS that gives the evolution
5638fd1498Szrj function of the analyzed variable.
5738fd1498Szrj
5838fd1498Szrj - When the definition is a condition-phi-node: determine the
5938fd1498Szrj evolution function for all the branches of the phi node, and
6038fd1498Szrj finally merge these evolutions (see chrec_merge).
6138fd1498Szrj
6238fd1498Szrj - When the definition is a loop-phi-node: determine its initial
6338fd1498Szrj condition, that is the SSA edge defined in an outer loop, and
6438fd1498Szrj keep it symbolic. Then determine the SSA edges that are defined
6538fd1498Szrj in the body of the loop. Follow the inner edges until ending on
6638fd1498Szrj another loop-phi-node of the same analyzed loop. If the reached
6738fd1498Szrj loop-phi-node is not the starting loop-phi-node, then we keep
6838fd1498Szrj this definition under a symbolic form. If the reached
6938fd1498Szrj loop-phi-node is the same as the starting one, then we compute a
7038fd1498Szrj symbolic stride on the return path. The result is then the
7138fd1498Szrj symbolic chrec {initial_condition, +, symbolic_stride}_loop.
7238fd1498Szrj
7338fd1498Szrj Examples:
7438fd1498Szrj
7538fd1498Szrj Example 1: Illustration of the basic algorithm.
7638fd1498Szrj
7738fd1498Szrj | a = 3
7838fd1498Szrj | loop_1
7938fd1498Szrj | b = phi (a, c)
8038fd1498Szrj | c = b + 1
8138fd1498Szrj | if (c > 10) exit_loop
8238fd1498Szrj | endloop
8338fd1498Szrj
8438fd1498Szrj Suppose that we want to know the number of iterations of the
8538fd1498Szrj loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
8638fd1498Szrj ask the scalar evolution analyzer two questions: what's the
8738fd1498Szrj scalar evolution (scev) of "c", and what's the scev of "10". For
8838fd1498Szrj "10" the answer is "10" since it is a scalar constant. For the
8938fd1498Szrj scalar variable "c", it follows the SSA edge to its definition,
9038fd1498Szrj "c = b + 1", and then asks again what's the scev of "b".
9138fd1498Szrj Following the SSA edge, we end on a loop-phi-node "b = phi (a,
9238fd1498Szrj c)", where the initial condition is "a", and the inner loop edge
9338fd1498Szrj is "c". The initial condition is kept under a symbolic form (it
9438fd1498Szrj may be the case that the copy constant propagation has done its
9538fd1498Szrj work and we end with the constant "3" as one of the edges of the
9638fd1498Szrj loop-phi-node). The update edge is followed to the end of the
9738fd1498Szrj loop, and until reaching again the starting loop-phi-node: b -> c
9838fd1498Szrj -> b. At this point we have drawn a path from "b" to "b" from
9938fd1498Szrj which we compute the stride in the loop: in this example it is
10038fd1498Szrj "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
10138fd1498Szrj that the scev for "b" is known, it is possible to compute the
10238fd1498Szrj scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
10338fd1498Szrj determine the number of iterations in the loop_1, we have to
10438fd1498Szrj instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
10538fd1498Szrj more analysis the scev {4, +, 1}_1, or in other words, this is
10638fd1498Szrj the function "f (x) = x + 4", where x is the iteration count of
10738fd1498Szrj the loop_1. Now we have to solve the inequality "x + 4 > 10",
10838fd1498Szrj and take the smallest iteration number for which the loop is
10938fd1498Szrj exited: x = 7. This loop runs from x = 0 to x = 7, and in total
11038fd1498Szrj there are 8 iterations. In terms of loop normalization, we have
11138fd1498Szrj created a variable that is implicitly defined, "x" or just "_1",
11238fd1498Szrj and all the other analyzed scalars of the loop are defined in
11338fd1498Szrj function of this variable:
11438fd1498Szrj
11538fd1498Szrj a -> 3
11638fd1498Szrj b -> {3, +, 1}_1
11738fd1498Szrj c -> {4, +, 1}_1
11838fd1498Szrj
11938fd1498Szrj or in terms of a C program:
12038fd1498Szrj
12138fd1498Szrj | a = 3
12238fd1498Szrj | for (x = 0; x <= 7; x++)
12338fd1498Szrj | {
12438fd1498Szrj | b = x + 3
12538fd1498Szrj | c = x + 4
12638fd1498Szrj | }
12738fd1498Szrj
12838fd1498Szrj Example 2a: Illustration of the algorithm on nested loops.
12938fd1498Szrj
13038fd1498Szrj | loop_1
13138fd1498Szrj | a = phi (1, b)
13238fd1498Szrj | c = a + 2
13338fd1498Szrj | loop_2 10 times
13438fd1498Szrj | b = phi (c, d)
13538fd1498Szrj | d = b + 3
13638fd1498Szrj | endloop
13738fd1498Szrj | endloop
13838fd1498Szrj
13938fd1498Szrj For analyzing the scalar evolution of "a", the algorithm follows
14038fd1498Szrj the SSA edge into the loop's body: "a -> b". "b" is an inner
14138fd1498Szrj loop-phi-node, and its analysis as in Example 1, gives:
14238fd1498Szrj
14338fd1498Szrj b -> {c, +, 3}_2
14438fd1498Szrj d -> {c + 3, +, 3}_2
14538fd1498Szrj
14638fd1498Szrj Following the SSA edge for the initial condition, we end on "c = a
14738fd1498Szrj + 2", and then on the starting loop-phi-node "a". From this point,
14838fd1498Szrj the loop stride is computed: back on "c = a + 2" we get a "+2" in
14938fd1498Szrj the loop_1, then on the loop-phi-node "b" we compute the overall
15038fd1498Szrj effect of the inner loop that is "b = c + 30", and we get a "+30"
15138fd1498Szrj in the loop_1. That means that the overall stride in loop_1 is
15238fd1498Szrj equal to "+32", and the result is:
15338fd1498Szrj
15438fd1498Szrj a -> {1, +, 32}_1
15538fd1498Szrj c -> {3, +, 32}_1
15638fd1498Szrj
15738fd1498Szrj Example 2b: Multivariate chains of recurrences.
15838fd1498Szrj
15938fd1498Szrj | loop_1
16038fd1498Szrj | k = phi (0, k + 1)
16138fd1498Szrj | loop_2 4 times
16238fd1498Szrj | j = phi (0, j + 1)
16338fd1498Szrj | loop_3 4 times
16438fd1498Szrj | i = phi (0, i + 1)
16538fd1498Szrj | A[j + k] = ...
16638fd1498Szrj | endloop
16738fd1498Szrj | endloop
16838fd1498Szrj | endloop
16938fd1498Szrj
17038fd1498Szrj Analyzing the access function of array A with
17138fd1498Szrj instantiate_parameters (loop_1, "j + k"), we obtain the
17238fd1498Szrj instantiation and the analysis of the scalar variables "j" and "k"
17338fd1498Szrj in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
17438fd1498Szrj value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
17538fd1498Szrj {0, +, 1}_1. To obtain the evolution function in loop_3 and
17638fd1498Szrj instantiate the scalar variables up to loop_1, one has to use:
17738fd1498Szrj instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
17838fd1498Szrj The result of this call is {{0, +, 1}_1, +, 1}_2.
17938fd1498Szrj
18038fd1498Szrj Example 3: Higher degree polynomials.
18138fd1498Szrj
18238fd1498Szrj | loop_1
18338fd1498Szrj | a = phi (2, b)
18438fd1498Szrj | c = phi (5, d)
18538fd1498Szrj | b = a + 1
18638fd1498Szrj | d = c + a
18738fd1498Szrj | endloop
18838fd1498Szrj
18938fd1498Szrj a -> {2, +, 1}_1
19038fd1498Szrj b -> {3, +, 1}_1
19138fd1498Szrj c -> {5, +, a}_1
19238fd1498Szrj d -> {5 + a, +, a}_1
19338fd1498Szrj
19438fd1498Szrj instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
19538fd1498Szrj instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
19638fd1498Szrj
19738fd1498Szrj Example 4: Lucas, Fibonacci, or mixers in general.
19838fd1498Szrj
19938fd1498Szrj | loop_1
20038fd1498Szrj | a = phi (1, b)
20138fd1498Szrj | c = phi (3, d)
20238fd1498Szrj | b = c
20338fd1498Szrj | d = c + a
20438fd1498Szrj | endloop
20538fd1498Szrj
20638fd1498Szrj a -> (1, c)_1
20738fd1498Szrj c -> {3, +, a}_1
20838fd1498Szrj
20938fd1498Szrj The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
21038fd1498Szrj following semantics: during the first iteration of the loop_1, the
21138fd1498Szrj variable contains the value 1, and then it contains the value "c".
21238fd1498Szrj Note that this syntax is close to the syntax of the loop-phi-node:
21338fd1498Szrj "a -> (1, c)_1" vs. "a = phi (1, c)".
21438fd1498Szrj
21538fd1498Szrj The symbolic chrec representation contains all the semantics of the
21638fd1498Szrj original code. What is more difficult is to use this information.
21738fd1498Szrj
21838fd1498Szrj Example 5: Flip-flops, or exchangers.
21938fd1498Szrj
22038fd1498Szrj | loop_1
22138fd1498Szrj | a = phi (1, b)
22238fd1498Szrj | c = phi (3, d)
22338fd1498Szrj | b = c
22438fd1498Szrj | d = a
22538fd1498Szrj | endloop
22638fd1498Szrj
22738fd1498Szrj a -> (1, c)_1
22838fd1498Szrj c -> (3, a)_1
22938fd1498Szrj
23038fd1498Szrj Based on these symbolic chrecs, it is possible to refine this
23138fd1498Szrj information into the more precise PERIODIC_CHRECs:
23238fd1498Szrj
23338fd1498Szrj a -> |1, 3|_1
23438fd1498Szrj c -> |3, 1|_1
23538fd1498Szrj
23638fd1498Szrj This transformation is not yet implemented.
23738fd1498Szrj
23838fd1498Szrj Further readings:
23938fd1498Szrj
24038fd1498Szrj You can find a more detailed description of the algorithm in:
24138fd1498Szrj http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
24238fd1498Szrj http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
24338fd1498Szrj this is a preliminary report and some of the details of the
24438fd1498Szrj algorithm have changed. I'm working on a research report that
24538fd1498Szrj updates the description of the algorithms to reflect the design
24638fd1498Szrj choices used in this implementation.
24738fd1498Szrj
24838fd1498Szrj A set of slides show a high level overview of the algorithm and run
24938fd1498Szrj an example through the scalar evolution analyzer:
25038fd1498Szrj http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
25138fd1498Szrj
25238fd1498Szrj The slides that I have presented at the GCC Summit'04 are available
25338fd1498Szrj at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
25438fd1498Szrj */
25538fd1498Szrj
25638fd1498Szrj #include "config.h"
25738fd1498Szrj #include "system.h"
25838fd1498Szrj #include "coretypes.h"
25938fd1498Szrj #include "backend.h"
26038fd1498Szrj #include "rtl.h"
26138fd1498Szrj #include "tree.h"
26238fd1498Szrj #include "gimple.h"
26338fd1498Szrj #include "ssa.h"
26438fd1498Szrj #include "gimple-pretty-print.h"
26538fd1498Szrj #include "fold-const.h"
26638fd1498Szrj #include "gimplify.h"
26738fd1498Szrj #include "gimple-iterator.h"
26838fd1498Szrj #include "gimplify-me.h"
26938fd1498Szrj #include "tree-cfg.h"
27038fd1498Szrj #include "tree-ssa-loop-ivopts.h"
27138fd1498Szrj #include "tree-ssa-loop-manip.h"
27238fd1498Szrj #include "tree-ssa-loop-niter.h"
27338fd1498Szrj #include "tree-ssa-loop.h"
27438fd1498Szrj #include "tree-ssa.h"
27538fd1498Szrj #include "cfgloop.h"
27638fd1498Szrj #include "tree-chrec.h"
27738fd1498Szrj #include "tree-affine.h"
27838fd1498Szrj #include "tree-scalar-evolution.h"
27938fd1498Szrj #include "dumpfile.h"
28038fd1498Szrj #include "params.h"
28138fd1498Szrj #include "tree-ssa-propagate.h"
28238fd1498Szrj #include "gimple-fold.h"
28338fd1498Szrj #include "tree-into-ssa.h"
28438fd1498Szrj
28538fd1498Szrj static tree analyze_scalar_evolution_1 (struct loop *, tree);
28638fd1498Szrj static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
28738fd1498Szrj tree var);
28838fd1498Szrj
28938fd1498Szrj /* The cached information about an SSA name with version NAME_VERSION,
29038fd1498Szrj claiming that below basic block with index INSTANTIATED_BELOW, the
29138fd1498Szrj value of the SSA name can be expressed as CHREC. */
29238fd1498Szrj
29338fd1498Szrj struct GTY((for_user)) scev_info_str {
29438fd1498Szrj unsigned int name_version;
29538fd1498Szrj int instantiated_below;
29638fd1498Szrj tree chrec;
29738fd1498Szrj };
29838fd1498Szrj
29938fd1498Szrj /* Counters for the scev database. */
30038fd1498Szrj static unsigned nb_set_scev = 0;
30138fd1498Szrj static unsigned nb_get_scev = 0;
30238fd1498Szrj
30338fd1498Szrj /* The following trees are unique elements. Thus the comparison of
30438fd1498Szrj another element to these elements should be done on the pointer to
30538fd1498Szrj these trees, and not on their value. */
30638fd1498Szrj
30738fd1498Szrj /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
30838fd1498Szrj tree chrec_not_analyzed_yet;
30938fd1498Szrj
31038fd1498Szrj /* Reserved to the cases where the analyzer has detected an
31138fd1498Szrj undecidable property at compile time. */
31238fd1498Szrj tree chrec_dont_know;
31338fd1498Szrj
31438fd1498Szrj /* When the analyzer has detected that a property will never
31538fd1498Szrj happen, then it qualifies it with chrec_known. */
31638fd1498Szrj tree chrec_known;
31738fd1498Szrj
31838fd1498Szrj struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
31938fd1498Szrj {
32038fd1498Szrj static hashval_t hash (scev_info_str *i);
32138fd1498Szrj static bool equal (const scev_info_str *a, const scev_info_str *b);
32238fd1498Szrj };
32338fd1498Szrj
32438fd1498Szrj static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
32538fd1498Szrj
32638fd1498Szrj
32738fd1498Szrj /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
32838fd1498Szrj
32938fd1498Szrj static inline struct scev_info_str *
new_scev_info_str(basic_block instantiated_below,tree var)33038fd1498Szrj new_scev_info_str (basic_block instantiated_below, tree var)
33138fd1498Szrj {
33238fd1498Szrj struct scev_info_str *res;
33338fd1498Szrj
33438fd1498Szrj res = ggc_alloc<scev_info_str> ();
33538fd1498Szrj res->name_version = SSA_NAME_VERSION (var);
33638fd1498Szrj res->chrec = chrec_not_analyzed_yet;
33738fd1498Szrj res->instantiated_below = instantiated_below->index;
33838fd1498Szrj
33938fd1498Szrj return res;
34038fd1498Szrj }
34138fd1498Szrj
34238fd1498Szrj /* Computes a hash function for database element ELT. */
34338fd1498Szrj
34438fd1498Szrj hashval_t
hash(scev_info_str * elt)34538fd1498Szrj scev_info_hasher::hash (scev_info_str *elt)
34638fd1498Szrj {
34738fd1498Szrj return elt->name_version ^ elt->instantiated_below;
34838fd1498Szrj }
34938fd1498Szrj
35038fd1498Szrj /* Compares database elements E1 and E2. */
35138fd1498Szrj
35238fd1498Szrj bool
equal(const scev_info_str * elt1,const scev_info_str * elt2)35338fd1498Szrj scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
35438fd1498Szrj {
35538fd1498Szrj return (elt1->name_version == elt2->name_version
35638fd1498Szrj && elt1->instantiated_below == elt2->instantiated_below);
35738fd1498Szrj }
35838fd1498Szrj
35938fd1498Szrj /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
36038fd1498Szrj A first query on VAR returns chrec_not_analyzed_yet. */
36138fd1498Szrj
36238fd1498Szrj static tree *
find_var_scev_info(basic_block instantiated_below,tree var)36338fd1498Szrj find_var_scev_info (basic_block instantiated_below, tree var)
36438fd1498Szrj {
36538fd1498Szrj struct scev_info_str *res;
36638fd1498Szrj struct scev_info_str tmp;
36738fd1498Szrj
36838fd1498Szrj tmp.name_version = SSA_NAME_VERSION (var);
36938fd1498Szrj tmp.instantiated_below = instantiated_below->index;
37038fd1498Szrj scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
37138fd1498Szrj
37238fd1498Szrj if (!*slot)
37338fd1498Szrj *slot = new_scev_info_str (instantiated_below, var);
37438fd1498Szrj res = *slot;
37538fd1498Szrj
37638fd1498Szrj return &res->chrec;
37738fd1498Szrj }
37838fd1498Szrj
37938fd1498Szrj /* Return true when CHREC contains symbolic names defined in
38038fd1498Szrj LOOP_NB. */
38138fd1498Szrj
38238fd1498Szrj bool
chrec_contains_symbols_defined_in_loop(const_tree chrec,unsigned loop_nb)38338fd1498Szrj chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
38438fd1498Szrj {
38538fd1498Szrj int i, n;
38638fd1498Szrj
38738fd1498Szrj if (chrec == NULL_TREE)
38838fd1498Szrj return false;
38938fd1498Szrj
39038fd1498Szrj if (is_gimple_min_invariant (chrec))
39138fd1498Szrj return false;
39238fd1498Szrj
39338fd1498Szrj if (TREE_CODE (chrec) == SSA_NAME)
39438fd1498Szrj {
39538fd1498Szrj gimple *def;
39638fd1498Szrj loop_p def_loop, loop;
39738fd1498Szrj
39838fd1498Szrj if (SSA_NAME_IS_DEFAULT_DEF (chrec))
39938fd1498Szrj return false;
40038fd1498Szrj
40138fd1498Szrj def = SSA_NAME_DEF_STMT (chrec);
40238fd1498Szrj def_loop = loop_containing_stmt (def);
40338fd1498Szrj loop = get_loop (cfun, loop_nb);
40438fd1498Szrj
40538fd1498Szrj if (def_loop == NULL)
40638fd1498Szrj return false;
40738fd1498Szrj
40838fd1498Szrj if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
40938fd1498Szrj return true;
41038fd1498Szrj
41138fd1498Szrj return false;
41238fd1498Szrj }
41338fd1498Szrj
41438fd1498Szrj n = TREE_OPERAND_LENGTH (chrec);
41538fd1498Szrj for (i = 0; i < n; i++)
41638fd1498Szrj if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
41738fd1498Szrj loop_nb))
41838fd1498Szrj return true;
41938fd1498Szrj return false;
42038fd1498Szrj }
42138fd1498Szrj
42238fd1498Szrj /* Return true when PHI is a loop-phi-node. */
42338fd1498Szrj
42438fd1498Szrj static bool
loop_phi_node_p(gimple * phi)42538fd1498Szrj loop_phi_node_p (gimple *phi)
42638fd1498Szrj {
42738fd1498Szrj /* The implementation of this function is based on the following
42838fd1498Szrj property: "all the loop-phi-nodes of a loop are contained in the
42938fd1498Szrj loop's header basic block". */
43038fd1498Szrj
43138fd1498Szrj return loop_containing_stmt (phi)->header == gimple_bb (phi);
43238fd1498Szrj }
43338fd1498Szrj
43438fd1498Szrj /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
43538fd1498Szrj In general, in the case of multivariate evolutions we want to get
43638fd1498Szrj the evolution in different loops. LOOP specifies the level for
43738fd1498Szrj which to get the evolution.
43838fd1498Szrj
43938fd1498Szrj Example:
44038fd1498Szrj
44138fd1498Szrj | for (j = 0; j < 100; j++)
44238fd1498Szrj | {
44338fd1498Szrj | for (k = 0; k < 100; k++)
44438fd1498Szrj | {
44538fd1498Szrj | i = k + j; - Here the value of i is a function of j, k.
44638fd1498Szrj | }
44738fd1498Szrj | ... = i - Here the value of i is a function of j.
44838fd1498Szrj | }
44938fd1498Szrj | ... = i - Here the value of i is a scalar.
45038fd1498Szrj
45138fd1498Szrj Example:
45238fd1498Szrj
45338fd1498Szrj | i_0 = ...
45438fd1498Szrj | loop_1 10 times
45538fd1498Szrj | i_1 = phi (i_0, i_2)
45638fd1498Szrj | i_2 = i_1 + 2
45738fd1498Szrj | endloop
45838fd1498Szrj
45938fd1498Szrj This loop has the same effect as:
46038fd1498Szrj LOOP_1 has the same effect as:
46138fd1498Szrj
46238fd1498Szrj | i_1 = i_0 + 20
46338fd1498Szrj
46438fd1498Szrj The overall effect of the loop, "i_0 + 20" in the previous example,
46538fd1498Szrj is obtained by passing in the parameters: LOOP = 1,
46638fd1498Szrj EVOLUTION_FN = {i_0, +, 2}_1.
46738fd1498Szrj */
46838fd1498Szrj
46938fd1498Szrj tree
compute_overall_effect_of_inner_loop(struct loop * loop,tree evolution_fn)47038fd1498Szrj compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
47138fd1498Szrj {
47238fd1498Szrj bool val = false;
47338fd1498Szrj
47438fd1498Szrj if (evolution_fn == chrec_dont_know)
47538fd1498Szrj return chrec_dont_know;
47638fd1498Szrj
47738fd1498Szrj else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
47838fd1498Szrj {
47938fd1498Szrj struct loop *inner_loop = get_chrec_loop (evolution_fn);
48038fd1498Szrj
48138fd1498Szrj if (inner_loop == loop
48238fd1498Szrj || flow_loop_nested_p (loop, inner_loop))
48338fd1498Szrj {
48438fd1498Szrj tree nb_iter = number_of_latch_executions (inner_loop);
48538fd1498Szrj
48638fd1498Szrj if (nb_iter == chrec_dont_know)
48738fd1498Szrj return chrec_dont_know;
48838fd1498Szrj else
48938fd1498Szrj {
49038fd1498Szrj tree res;
49138fd1498Szrj
49238fd1498Szrj /* evolution_fn is the evolution function in LOOP. Get
49338fd1498Szrj its value in the nb_iter-th iteration. */
49438fd1498Szrj res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
49538fd1498Szrj
49638fd1498Szrj if (chrec_contains_symbols_defined_in_loop (res, loop->num))
49738fd1498Szrj res = instantiate_parameters (loop, res);
49838fd1498Szrj
49938fd1498Szrj /* Continue the computation until ending on a parent of LOOP. */
50038fd1498Szrj return compute_overall_effect_of_inner_loop (loop, res);
50138fd1498Szrj }
50238fd1498Szrj }
50338fd1498Szrj else
50438fd1498Szrj return evolution_fn;
50538fd1498Szrj }
50638fd1498Szrj
50738fd1498Szrj /* If the evolution function is an invariant, there is nothing to do. */
50838fd1498Szrj else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
50938fd1498Szrj return evolution_fn;
51038fd1498Szrj
51138fd1498Szrj else
51238fd1498Szrj return chrec_dont_know;
51338fd1498Szrj }
51438fd1498Szrj
51538fd1498Szrj /* Associate CHREC to SCALAR. */
51638fd1498Szrj
51738fd1498Szrj static void
set_scalar_evolution(basic_block instantiated_below,tree scalar,tree chrec)51838fd1498Szrj set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
51938fd1498Szrj {
52038fd1498Szrj tree *scalar_info;
52138fd1498Szrj
52238fd1498Szrj if (TREE_CODE (scalar) != SSA_NAME)
52338fd1498Szrj return;
52438fd1498Szrj
52538fd1498Szrj scalar_info = find_var_scev_info (instantiated_below, scalar);
52638fd1498Szrj
52738fd1498Szrj if (dump_file)
52838fd1498Szrj {
52938fd1498Szrj if (dump_flags & TDF_SCEV)
53038fd1498Szrj {
53138fd1498Szrj fprintf (dump_file, "(set_scalar_evolution \n");
53238fd1498Szrj fprintf (dump_file, " instantiated_below = %d \n",
53338fd1498Szrj instantiated_below->index);
53438fd1498Szrj fprintf (dump_file, " (scalar = ");
53538fd1498Szrj print_generic_expr (dump_file, scalar);
53638fd1498Szrj fprintf (dump_file, ")\n (scalar_evolution = ");
53738fd1498Szrj print_generic_expr (dump_file, chrec);
53838fd1498Szrj fprintf (dump_file, "))\n");
53938fd1498Szrj }
54038fd1498Szrj if (dump_flags & TDF_STATS)
54138fd1498Szrj nb_set_scev++;
54238fd1498Szrj }
54338fd1498Szrj
54438fd1498Szrj *scalar_info = chrec;
54538fd1498Szrj }
54638fd1498Szrj
54738fd1498Szrj /* Retrieve the chrec associated to SCALAR instantiated below
54838fd1498Szrj INSTANTIATED_BELOW block. */
54938fd1498Szrj
55038fd1498Szrj static tree
get_scalar_evolution(basic_block instantiated_below,tree scalar)55138fd1498Szrj get_scalar_evolution (basic_block instantiated_below, tree scalar)
55238fd1498Szrj {
55338fd1498Szrj tree res;
55438fd1498Szrj
55538fd1498Szrj if (dump_file)
55638fd1498Szrj {
55738fd1498Szrj if (dump_flags & TDF_SCEV)
55838fd1498Szrj {
55938fd1498Szrj fprintf (dump_file, "(get_scalar_evolution \n");
56038fd1498Szrj fprintf (dump_file, " (scalar = ");
56138fd1498Szrj print_generic_expr (dump_file, scalar);
56238fd1498Szrj fprintf (dump_file, ")\n");
56338fd1498Szrj }
56438fd1498Szrj if (dump_flags & TDF_STATS)
56538fd1498Szrj nb_get_scev++;
56638fd1498Szrj }
56738fd1498Szrj
56838fd1498Szrj if (VECTOR_TYPE_P (TREE_TYPE (scalar))
56938fd1498Szrj || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
57038fd1498Szrj /* For chrec_dont_know we keep the symbolic form. */
57138fd1498Szrj res = scalar;
57238fd1498Szrj else
57338fd1498Szrj switch (TREE_CODE (scalar))
57438fd1498Szrj {
57538fd1498Szrj case SSA_NAME:
57638fd1498Szrj if (SSA_NAME_IS_DEFAULT_DEF (scalar))
57738fd1498Szrj res = scalar;
57838fd1498Szrj else
57938fd1498Szrj res = *find_var_scev_info (instantiated_below, scalar);
58038fd1498Szrj break;
58138fd1498Szrj
58238fd1498Szrj case REAL_CST:
58338fd1498Szrj case FIXED_CST:
58438fd1498Szrj case INTEGER_CST:
58538fd1498Szrj res = scalar;
58638fd1498Szrj break;
58738fd1498Szrj
58838fd1498Szrj default:
58938fd1498Szrj res = chrec_not_analyzed_yet;
59038fd1498Szrj break;
59138fd1498Szrj }
59238fd1498Szrj
59338fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
59438fd1498Szrj {
59538fd1498Szrj fprintf (dump_file, " (scalar_evolution = ");
59638fd1498Szrj print_generic_expr (dump_file, res);
59738fd1498Szrj fprintf (dump_file, "))\n");
59838fd1498Szrj }
59938fd1498Szrj
60038fd1498Szrj return res;
60138fd1498Szrj }
60238fd1498Szrj
60338fd1498Szrj /* Helper function for add_to_evolution. Returns the evolution
60438fd1498Szrj function for an assignment of the form "a = b + c", where "a" and
60538fd1498Szrj "b" are on the strongly connected component. CHREC_BEFORE is the
60638fd1498Szrj information that we already have collected up to this point.
60738fd1498Szrj TO_ADD is the evolution of "c".
60838fd1498Szrj
60938fd1498Szrj When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
61038fd1498Szrj evolution the expression TO_ADD, otherwise construct an evolution
61138fd1498Szrj part for this loop. */
61238fd1498Szrj
61338fd1498Szrj static tree
add_to_evolution_1(unsigned loop_nb,tree chrec_before,tree to_add,gimple * at_stmt)61438fd1498Szrj add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
61538fd1498Szrj gimple *at_stmt)
61638fd1498Szrj {
61738fd1498Szrj tree type, left, right;
61838fd1498Szrj struct loop *loop = get_loop (cfun, loop_nb), *chloop;
61938fd1498Szrj
62038fd1498Szrj switch (TREE_CODE (chrec_before))
62138fd1498Szrj {
62238fd1498Szrj case POLYNOMIAL_CHREC:
62338fd1498Szrj chloop = get_chrec_loop (chrec_before);
62438fd1498Szrj if (chloop == loop
62538fd1498Szrj || flow_loop_nested_p (chloop, loop))
62638fd1498Szrj {
62738fd1498Szrj unsigned var;
62838fd1498Szrj
62938fd1498Szrj type = chrec_type (chrec_before);
63038fd1498Szrj
63138fd1498Szrj /* When there is no evolution part in this loop, build it. */
63238fd1498Szrj if (chloop != loop)
63338fd1498Szrj {
63438fd1498Szrj var = loop_nb;
63538fd1498Szrj left = chrec_before;
63638fd1498Szrj right = SCALAR_FLOAT_TYPE_P (type)
63738fd1498Szrj ? build_real (type, dconst0)
63838fd1498Szrj : build_int_cst (type, 0);
63938fd1498Szrj }
64038fd1498Szrj else
64138fd1498Szrj {
64238fd1498Szrj var = CHREC_VARIABLE (chrec_before);
64338fd1498Szrj left = CHREC_LEFT (chrec_before);
64438fd1498Szrj right = CHREC_RIGHT (chrec_before);
64538fd1498Szrj }
64638fd1498Szrj
64738fd1498Szrj to_add = chrec_convert (type, to_add, at_stmt);
64838fd1498Szrj right = chrec_convert_rhs (type, right, at_stmt);
64938fd1498Szrj right = chrec_fold_plus (chrec_type (right), right, to_add);
65038fd1498Szrj return build_polynomial_chrec (var, left, right);
65138fd1498Szrj }
65238fd1498Szrj else
65338fd1498Szrj {
65438fd1498Szrj gcc_assert (flow_loop_nested_p (loop, chloop));
65538fd1498Szrj
65638fd1498Szrj /* Search the evolution in LOOP_NB. */
65738fd1498Szrj left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
65838fd1498Szrj to_add, at_stmt);
65938fd1498Szrj right = CHREC_RIGHT (chrec_before);
66038fd1498Szrj right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
66138fd1498Szrj return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
66238fd1498Szrj left, right);
66338fd1498Szrj }
66438fd1498Szrj
66538fd1498Szrj default:
66638fd1498Szrj /* These nodes do not depend on a loop. */
66738fd1498Szrj if (chrec_before == chrec_dont_know)
66838fd1498Szrj return chrec_dont_know;
66938fd1498Szrj
67038fd1498Szrj left = chrec_before;
67138fd1498Szrj right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
67238fd1498Szrj return build_polynomial_chrec (loop_nb, left, right);
67338fd1498Szrj }
67438fd1498Szrj }
67538fd1498Szrj
67638fd1498Szrj /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
67738fd1498Szrj of LOOP_NB.
67838fd1498Szrj
67938fd1498Szrj Description (provided for completeness, for those who read code in
68038fd1498Szrj a plane, and for my poor 62 bytes brain that would have forgotten
68138fd1498Szrj all this in the next two or three months):
68238fd1498Szrj
68338fd1498Szrj The algorithm of translation of programs from the SSA representation
68438fd1498Szrj into the chrecs syntax is based on a pattern matching. After having
68538fd1498Szrj reconstructed the overall tree expression for a loop, there are only
68638fd1498Szrj two cases that can arise:
68738fd1498Szrj
68838fd1498Szrj 1. a = loop-phi (init, a + expr)
68938fd1498Szrj 2. a = loop-phi (init, expr)
69038fd1498Szrj
69138fd1498Szrj where EXPR is either a scalar constant with respect to the analyzed
69238fd1498Szrj loop (this is a degree 0 polynomial), or an expression containing
69338fd1498Szrj other loop-phi definitions (these are higher degree polynomials).
69438fd1498Szrj
69538fd1498Szrj Examples:
69638fd1498Szrj
69738fd1498Szrj 1.
69838fd1498Szrj | init = ...
69938fd1498Szrj | loop_1
70038fd1498Szrj | a = phi (init, a + 5)
70138fd1498Szrj | endloop
70238fd1498Szrj
70338fd1498Szrj 2.
70438fd1498Szrj | inita = ...
70538fd1498Szrj | initb = ...
70638fd1498Szrj | loop_1
70738fd1498Szrj | a = phi (inita, 2 * b + 3)
70838fd1498Szrj | b = phi (initb, b + 1)
70938fd1498Szrj | endloop
71038fd1498Szrj
71138fd1498Szrj For the first case, the semantics of the SSA representation is:
71238fd1498Szrj
71338fd1498Szrj | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
71438fd1498Szrj
71538fd1498Szrj that is, there is a loop index "x" that determines the scalar value
71638fd1498Szrj of the variable during the loop execution. During the first
71738fd1498Szrj iteration, the value is that of the initial condition INIT, while
71838fd1498Szrj during the subsequent iterations, it is the sum of the initial
71938fd1498Szrj condition with the sum of all the values of EXPR from the initial
72038fd1498Szrj iteration to the before last considered iteration.
72138fd1498Szrj
72238fd1498Szrj For the second case, the semantics of the SSA program is:
72338fd1498Szrj
72438fd1498Szrj | a (x) = init, if x = 0;
72538fd1498Szrj | expr (x - 1), otherwise.
72638fd1498Szrj
72738fd1498Szrj The second case corresponds to the PEELED_CHREC, whose syntax is
72838fd1498Szrj close to the syntax of a loop-phi-node:
72938fd1498Szrj
73038fd1498Szrj | phi (init, expr) vs. (init, expr)_x
73138fd1498Szrj
73238fd1498Szrj The proof of the translation algorithm for the first case is a
73338fd1498Szrj proof by structural induction based on the degree of EXPR.
73438fd1498Szrj
73538fd1498Szrj Degree 0:
73638fd1498Szrj When EXPR is a constant with respect to the analyzed loop, or in
73738fd1498Szrj other words when EXPR is a polynomial of degree 0, the evolution of
73838fd1498Szrj the variable A in the loop is an affine function with an initial
73938fd1498Szrj condition INIT, and a step EXPR. In order to show this, we start
74038fd1498Szrj from the semantics of the SSA representation:
74138fd1498Szrj
74238fd1498Szrj f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
74338fd1498Szrj
74438fd1498Szrj and since "expr (j)" is a constant with respect to "j",
74538fd1498Szrj
74638fd1498Szrj f (x) = init + x * expr
74738fd1498Szrj
74838fd1498Szrj Finally, based on the semantics of the pure sum chrecs, by
74938fd1498Szrj identification we get the corresponding chrecs syntax:
75038fd1498Szrj
75138fd1498Szrj f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
75238fd1498Szrj f (x) -> {init, +, expr}_x
75338fd1498Szrj
75438fd1498Szrj Higher degree:
75538fd1498Szrj Suppose that EXPR is a polynomial of degree N with respect to the
75638fd1498Szrj analyzed loop_x for which we have already determined that it is
75738fd1498Szrj written under the chrecs syntax:
75838fd1498Szrj
75938fd1498Szrj | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
76038fd1498Szrj
76138fd1498Szrj We start from the semantics of the SSA program:
76238fd1498Szrj
76338fd1498Szrj | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
76438fd1498Szrj |
76538fd1498Szrj | f (x) = init + \sum_{j = 0}^{x - 1}
76638fd1498Szrj | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
76738fd1498Szrj |
76838fd1498Szrj | f (x) = init + \sum_{j = 0}^{x - 1}
76938fd1498Szrj | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
77038fd1498Szrj |
77138fd1498Szrj | f (x) = init + \sum_{k = 0}^{n - 1}
77238fd1498Szrj | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
77338fd1498Szrj |
77438fd1498Szrj | f (x) = init + \sum_{k = 0}^{n - 1}
77538fd1498Szrj | (b_k * \binom{x}{k + 1})
77638fd1498Szrj |
77738fd1498Szrj | f (x) = init + b_0 * \binom{x}{1} + ...
77838fd1498Szrj | + b_{n-1} * \binom{x}{n}
77938fd1498Szrj |
78038fd1498Szrj | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
78138fd1498Szrj | + b_{n-1} * \binom{x}{n}
78238fd1498Szrj |
78338fd1498Szrj
78438fd1498Szrj And finally from the definition of the chrecs syntax, we identify:
78538fd1498Szrj | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
78638fd1498Szrj
78738fd1498Szrj This shows the mechanism that stands behind the add_to_evolution
78838fd1498Szrj function. An important point is that the use of symbolic
78938fd1498Szrj parameters avoids the need of an analysis schedule.
79038fd1498Szrj
79138fd1498Szrj Example:
79238fd1498Szrj
79338fd1498Szrj | inita = ...
79438fd1498Szrj | initb = ...
79538fd1498Szrj | loop_1
79638fd1498Szrj | a = phi (inita, a + 2 + b)
79738fd1498Szrj | b = phi (initb, b + 1)
79838fd1498Szrj | endloop
79938fd1498Szrj
80038fd1498Szrj When analyzing "a", the algorithm keeps "b" symbolically:
80138fd1498Szrj
80238fd1498Szrj | a -> {inita, +, 2 + b}_1
80338fd1498Szrj
80438fd1498Szrj Then, after instantiation, the analyzer ends on the evolution:
80538fd1498Szrj
80638fd1498Szrj | a -> {inita, +, 2 + initb, +, 1}_1
80738fd1498Szrj
80838fd1498Szrj */
80938fd1498Szrj
81038fd1498Szrj static tree
add_to_evolution(unsigned loop_nb,tree chrec_before,enum tree_code code,tree to_add,gimple * at_stmt)81138fd1498Szrj add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
81238fd1498Szrj tree to_add, gimple *at_stmt)
81338fd1498Szrj {
81438fd1498Szrj tree type = chrec_type (to_add);
81538fd1498Szrj tree res = NULL_TREE;
81638fd1498Szrj
81738fd1498Szrj if (to_add == NULL_TREE)
81838fd1498Szrj return chrec_before;
81938fd1498Szrj
82038fd1498Szrj /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
82138fd1498Szrj instantiated at this point. */
82238fd1498Szrj if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
82338fd1498Szrj /* This should not happen. */
82438fd1498Szrj return chrec_dont_know;
82538fd1498Szrj
82638fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
82738fd1498Szrj {
82838fd1498Szrj fprintf (dump_file, "(add_to_evolution \n");
82938fd1498Szrj fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
83038fd1498Szrj fprintf (dump_file, " (chrec_before = ");
83138fd1498Szrj print_generic_expr (dump_file, chrec_before);
83238fd1498Szrj fprintf (dump_file, ")\n (to_add = ");
83338fd1498Szrj print_generic_expr (dump_file, to_add);
83438fd1498Szrj fprintf (dump_file, ")\n");
83538fd1498Szrj }
83638fd1498Szrj
83738fd1498Szrj if (code == MINUS_EXPR)
83838fd1498Szrj to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
83938fd1498Szrj ? build_real (type, dconstm1)
84038fd1498Szrj : build_int_cst_type (type, -1));
84138fd1498Szrj
84238fd1498Szrj res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
84338fd1498Szrj
84438fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
84538fd1498Szrj {
84638fd1498Szrj fprintf (dump_file, " (res = ");
84738fd1498Szrj print_generic_expr (dump_file, res);
84838fd1498Szrj fprintf (dump_file, "))\n");
84938fd1498Szrj }
85038fd1498Szrj
85138fd1498Szrj return res;
85238fd1498Szrj }
85338fd1498Szrj
85438fd1498Szrj
85538fd1498Szrj
85638fd1498Szrj /* This section selects the loops that will be good candidates for the
85738fd1498Szrj scalar evolution analysis. For the moment, greedily select all the
85838fd1498Szrj loop nests we could analyze. */
85938fd1498Szrj
86038fd1498Szrj /* For a loop with a single exit edge, return the COND_EXPR that
86138fd1498Szrj guards the exit edge. If the expression is too difficult to
86238fd1498Szrj analyze, then give up. */
86338fd1498Szrj
86438fd1498Szrj gcond *
get_loop_exit_condition(const struct loop * loop)86538fd1498Szrj get_loop_exit_condition (const struct loop *loop)
86638fd1498Szrj {
86738fd1498Szrj gcond *res = NULL;
86838fd1498Szrj edge exit_edge = single_exit (loop);
86938fd1498Szrj
87038fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
87138fd1498Szrj fprintf (dump_file, "(get_loop_exit_condition \n ");
87238fd1498Szrj
87338fd1498Szrj if (exit_edge)
87438fd1498Szrj {
87538fd1498Szrj gimple *stmt;
87638fd1498Szrj
87738fd1498Szrj stmt = last_stmt (exit_edge->src);
878*e215fc28Szrj if (gcond *cond_stmt = safe_dyn_cast <gcond *> (stmt))
87938fd1498Szrj res = cond_stmt;
88038fd1498Szrj }
88138fd1498Szrj
88238fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
88338fd1498Szrj {
88438fd1498Szrj print_gimple_stmt (dump_file, res, 0);
88538fd1498Szrj fprintf (dump_file, ")\n");
88638fd1498Szrj }
88738fd1498Szrj
88838fd1498Szrj return res;
88938fd1498Szrj }
89038fd1498Szrj
89138fd1498Szrj
89238fd1498Szrj /* Depth first search algorithm. */
89338fd1498Szrj
89438fd1498Szrj enum t_bool {
89538fd1498Szrj t_false,
89638fd1498Szrj t_true,
89738fd1498Szrj t_dont_know
89838fd1498Szrj };
89938fd1498Szrj
90038fd1498Szrj
90138fd1498Szrj static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *,
90238fd1498Szrj tree *, int);
90338fd1498Szrj
90438fd1498Szrj /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
90538fd1498Szrj Return true if the strongly connected component has been found. */
90638fd1498Szrj
90738fd1498Szrj static t_bool
follow_ssa_edge_binary(struct loop * loop,gimple * at_stmt,tree type,tree rhs0,enum tree_code code,tree rhs1,gphi * halting_phi,tree * evolution_of_loop,int limit)90838fd1498Szrj follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt,
90938fd1498Szrj tree type, tree rhs0, enum tree_code code, tree rhs1,
91038fd1498Szrj gphi *halting_phi, tree *evolution_of_loop,
91138fd1498Szrj int limit)
91238fd1498Szrj {
91338fd1498Szrj t_bool res = t_false;
91438fd1498Szrj tree evol;
91538fd1498Szrj
91638fd1498Szrj switch (code)
91738fd1498Szrj {
91838fd1498Szrj case POINTER_PLUS_EXPR:
91938fd1498Szrj case PLUS_EXPR:
92038fd1498Szrj if (TREE_CODE (rhs0) == SSA_NAME)
92138fd1498Szrj {
92238fd1498Szrj if (TREE_CODE (rhs1) == SSA_NAME)
92338fd1498Szrj {
92438fd1498Szrj /* Match an assignment under the form:
92538fd1498Szrj "a = b + c". */
92638fd1498Szrj
92738fd1498Szrj /* We want only assignments of form "name + name" contribute to
92838fd1498Szrj LIMIT, as the other cases do not necessarily contribute to
92938fd1498Szrj the complexity of the expression. */
93038fd1498Szrj limit++;
93138fd1498Szrj
93238fd1498Szrj evol = *evolution_of_loop;
93338fd1498Szrj evol = add_to_evolution
93438fd1498Szrj (loop->num,
93538fd1498Szrj chrec_convert (type, evol, at_stmt),
93638fd1498Szrj code, rhs1, at_stmt);
93738fd1498Szrj res = follow_ssa_edge
93838fd1498Szrj (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
93938fd1498Szrj if (res == t_true)
94038fd1498Szrj *evolution_of_loop = evol;
94138fd1498Szrj else if (res == t_false)
94238fd1498Szrj {
94338fd1498Szrj *evolution_of_loop = add_to_evolution
94438fd1498Szrj (loop->num,
94538fd1498Szrj chrec_convert (type, *evolution_of_loop, at_stmt),
94638fd1498Szrj code, rhs0, at_stmt);
94738fd1498Szrj res = follow_ssa_edge
94838fd1498Szrj (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
94938fd1498Szrj evolution_of_loop, limit);
95038fd1498Szrj if (res == t_true)
95138fd1498Szrj ;
95238fd1498Szrj else if (res == t_dont_know)
95338fd1498Szrj *evolution_of_loop = chrec_dont_know;
95438fd1498Szrj }
95538fd1498Szrj
95638fd1498Szrj else if (res == t_dont_know)
95738fd1498Szrj *evolution_of_loop = chrec_dont_know;
95838fd1498Szrj }
95938fd1498Szrj
96038fd1498Szrj else
96138fd1498Szrj {
96238fd1498Szrj /* Match an assignment under the form:
96338fd1498Szrj "a = b + ...". */
96438fd1498Szrj *evolution_of_loop = add_to_evolution
96538fd1498Szrj (loop->num, chrec_convert (type, *evolution_of_loop,
96638fd1498Szrj at_stmt),
96738fd1498Szrj code, rhs1, at_stmt);
96838fd1498Szrj res = follow_ssa_edge
96938fd1498Szrj (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
97038fd1498Szrj evolution_of_loop, limit);
97138fd1498Szrj if (res == t_true)
97238fd1498Szrj ;
97338fd1498Szrj else if (res == t_dont_know)
97438fd1498Szrj *evolution_of_loop = chrec_dont_know;
97538fd1498Szrj }
97638fd1498Szrj }
97738fd1498Szrj
97838fd1498Szrj else if (TREE_CODE (rhs1) == SSA_NAME)
97938fd1498Szrj {
98038fd1498Szrj /* Match an assignment under the form:
98138fd1498Szrj "a = ... + c". */
98238fd1498Szrj *evolution_of_loop = add_to_evolution
98338fd1498Szrj (loop->num, chrec_convert (type, *evolution_of_loop,
98438fd1498Szrj at_stmt),
98538fd1498Szrj code, rhs0, at_stmt);
98638fd1498Szrj res = follow_ssa_edge
98738fd1498Szrj (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
98838fd1498Szrj evolution_of_loop, limit);
98938fd1498Szrj if (res == t_true)
99038fd1498Szrj ;
99138fd1498Szrj else if (res == t_dont_know)
99238fd1498Szrj *evolution_of_loop = chrec_dont_know;
99338fd1498Szrj }
99438fd1498Szrj
99538fd1498Szrj else
99638fd1498Szrj /* Otherwise, match an assignment under the form:
99738fd1498Szrj "a = ... + ...". */
99838fd1498Szrj /* And there is nothing to do. */
99938fd1498Szrj res = t_false;
100038fd1498Szrj break;
100138fd1498Szrj
100238fd1498Szrj case MINUS_EXPR:
100338fd1498Szrj /* This case is under the form "opnd0 = rhs0 - rhs1". */
100438fd1498Szrj if (TREE_CODE (rhs0) == SSA_NAME)
100538fd1498Szrj {
100638fd1498Szrj /* Match an assignment under the form:
100738fd1498Szrj "a = b - ...". */
100838fd1498Szrj
100938fd1498Szrj /* We want only assignments of form "name - name" contribute to
101038fd1498Szrj LIMIT, as the other cases do not necessarily contribute to
101138fd1498Szrj the complexity of the expression. */
101238fd1498Szrj if (TREE_CODE (rhs1) == SSA_NAME)
101338fd1498Szrj limit++;
101438fd1498Szrj
101538fd1498Szrj *evolution_of_loop = add_to_evolution
101638fd1498Szrj (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
101738fd1498Szrj MINUS_EXPR, rhs1, at_stmt);
101838fd1498Szrj res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
101938fd1498Szrj evolution_of_loop, limit);
102038fd1498Szrj if (res == t_true)
102138fd1498Szrj ;
102238fd1498Szrj else if (res == t_dont_know)
102338fd1498Szrj *evolution_of_loop = chrec_dont_know;
102438fd1498Szrj }
102538fd1498Szrj else
102638fd1498Szrj /* Otherwise, match an assignment under the form:
102738fd1498Szrj "a = ... - ...". */
102838fd1498Szrj /* And there is nothing to do. */
102938fd1498Szrj res = t_false;
103038fd1498Szrj break;
103138fd1498Szrj
103238fd1498Szrj default:
103338fd1498Szrj res = t_false;
103438fd1498Szrj }
103538fd1498Szrj
103638fd1498Szrj return res;
103738fd1498Szrj }
103838fd1498Szrj
103938fd1498Szrj /* Follow the ssa edge into the expression EXPR.
104038fd1498Szrj Return true if the strongly connected component has been found. */
104138fd1498Szrj
104238fd1498Szrj static t_bool
follow_ssa_edge_expr(struct loop * loop,gimple * at_stmt,tree expr,gphi * halting_phi,tree * evolution_of_loop,int limit)104338fd1498Szrj follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr,
104438fd1498Szrj gphi *halting_phi, tree *evolution_of_loop,
104538fd1498Szrj int limit)
104638fd1498Szrj {
104738fd1498Szrj enum tree_code code = TREE_CODE (expr);
104838fd1498Szrj tree type = TREE_TYPE (expr), rhs0, rhs1;
104938fd1498Szrj t_bool res;
105038fd1498Szrj
105138fd1498Szrj /* The EXPR is one of the following cases:
105238fd1498Szrj - an SSA_NAME,
105338fd1498Szrj - an INTEGER_CST,
105438fd1498Szrj - a PLUS_EXPR,
105538fd1498Szrj - a POINTER_PLUS_EXPR,
105638fd1498Szrj - a MINUS_EXPR,
105738fd1498Szrj - an ASSERT_EXPR,
105838fd1498Szrj - other cases are not yet handled. */
105938fd1498Szrj
106038fd1498Szrj switch (code)
106138fd1498Szrj {
106238fd1498Szrj CASE_CONVERT:
106338fd1498Szrj /* This assignment is under the form "a_1 = (cast) rhs. */
106438fd1498Szrj res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
106538fd1498Szrj halting_phi, evolution_of_loop, limit);
106638fd1498Szrj *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
106738fd1498Szrj break;
106838fd1498Szrj
106938fd1498Szrj case INTEGER_CST:
107038fd1498Szrj /* This assignment is under the form "a_1 = 7". */
107138fd1498Szrj res = t_false;
107238fd1498Szrj break;
107338fd1498Szrj
107438fd1498Szrj case SSA_NAME:
107538fd1498Szrj /* This assignment is under the form: "a_1 = b_2". */
107638fd1498Szrj res = follow_ssa_edge
107738fd1498Szrj (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
107838fd1498Szrj break;
107938fd1498Szrj
108038fd1498Szrj case POINTER_PLUS_EXPR:
108138fd1498Szrj case PLUS_EXPR:
108238fd1498Szrj case MINUS_EXPR:
108338fd1498Szrj /* This case is under the form "rhs0 +- rhs1". */
108438fd1498Szrj rhs0 = TREE_OPERAND (expr, 0);
108538fd1498Szrj rhs1 = TREE_OPERAND (expr, 1);
108638fd1498Szrj type = TREE_TYPE (rhs0);
108738fd1498Szrj STRIP_USELESS_TYPE_CONVERSION (rhs0);
108838fd1498Szrj STRIP_USELESS_TYPE_CONVERSION (rhs1);
108938fd1498Szrj res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
109038fd1498Szrj halting_phi, evolution_of_loop, limit);
109138fd1498Szrj break;
109238fd1498Szrj
109338fd1498Szrj case ADDR_EXPR:
109438fd1498Szrj /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
109538fd1498Szrj if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
109638fd1498Szrj {
109738fd1498Szrj expr = TREE_OPERAND (expr, 0);
109838fd1498Szrj rhs0 = TREE_OPERAND (expr, 0);
109938fd1498Szrj rhs1 = TREE_OPERAND (expr, 1);
110038fd1498Szrj type = TREE_TYPE (rhs0);
110138fd1498Szrj STRIP_USELESS_TYPE_CONVERSION (rhs0);
110238fd1498Szrj STRIP_USELESS_TYPE_CONVERSION (rhs1);
110338fd1498Szrj res = follow_ssa_edge_binary (loop, at_stmt, type,
110438fd1498Szrj rhs0, POINTER_PLUS_EXPR, rhs1,
110538fd1498Szrj halting_phi, evolution_of_loop, limit);
110638fd1498Szrj }
110738fd1498Szrj else
110838fd1498Szrj res = t_false;
110938fd1498Szrj break;
111038fd1498Szrj
111138fd1498Szrj case ASSERT_EXPR:
111238fd1498Szrj /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
111338fd1498Szrj It must be handled as a copy assignment of the form a_1 = a_2. */
111438fd1498Szrj rhs0 = ASSERT_EXPR_VAR (expr);
111538fd1498Szrj if (TREE_CODE (rhs0) == SSA_NAME)
111638fd1498Szrj res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
111738fd1498Szrj halting_phi, evolution_of_loop, limit);
111838fd1498Szrj else
111938fd1498Szrj res = t_false;
112038fd1498Szrj break;
112138fd1498Szrj
112238fd1498Szrj default:
112338fd1498Szrj res = t_false;
112438fd1498Szrj break;
112538fd1498Szrj }
112638fd1498Szrj
112738fd1498Szrj return res;
112838fd1498Szrj }
112938fd1498Szrj
113038fd1498Szrj /* Follow the ssa edge into the right hand side of an assignment STMT.
113138fd1498Szrj Return true if the strongly connected component has been found. */
113238fd1498Szrj
113338fd1498Szrj static t_bool
follow_ssa_edge_in_rhs(struct loop * loop,gimple * stmt,gphi * halting_phi,tree * evolution_of_loop,int limit)113438fd1498Szrj follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt,
113538fd1498Szrj gphi *halting_phi, tree *evolution_of_loop,
113638fd1498Szrj int limit)
113738fd1498Szrj {
113838fd1498Szrj enum tree_code code = gimple_assign_rhs_code (stmt);
113938fd1498Szrj tree type = gimple_expr_type (stmt), rhs1, rhs2;
114038fd1498Szrj t_bool res;
114138fd1498Szrj
114238fd1498Szrj switch (code)
114338fd1498Szrj {
114438fd1498Szrj CASE_CONVERT:
114538fd1498Szrj /* This assignment is under the form "a_1 = (cast) rhs. */
114638fd1498Szrj res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
114738fd1498Szrj halting_phi, evolution_of_loop, limit);
114838fd1498Szrj *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
114938fd1498Szrj break;
115038fd1498Szrj
115138fd1498Szrj case POINTER_PLUS_EXPR:
115238fd1498Szrj case PLUS_EXPR:
115338fd1498Szrj case MINUS_EXPR:
115438fd1498Szrj rhs1 = gimple_assign_rhs1 (stmt);
115538fd1498Szrj rhs2 = gimple_assign_rhs2 (stmt);
115638fd1498Szrj type = TREE_TYPE (rhs1);
115738fd1498Szrj res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
115838fd1498Szrj halting_phi, evolution_of_loop, limit);
115938fd1498Szrj break;
116038fd1498Szrj
116138fd1498Szrj default:
116238fd1498Szrj if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
116338fd1498Szrj res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
116438fd1498Szrj halting_phi, evolution_of_loop, limit);
116538fd1498Szrj else
116638fd1498Szrj res = t_false;
116738fd1498Szrj break;
116838fd1498Szrj }
116938fd1498Szrj
117038fd1498Szrj return res;
117138fd1498Szrj }
117238fd1498Szrj
117338fd1498Szrj /* Checks whether the I-th argument of a PHI comes from a backedge. */
117438fd1498Szrj
117538fd1498Szrj static bool
backedge_phi_arg_p(gphi * phi,int i)117638fd1498Szrj backedge_phi_arg_p (gphi *phi, int i)
117738fd1498Szrj {
117838fd1498Szrj const_edge e = gimple_phi_arg_edge (phi, i);
117938fd1498Szrj
118038fd1498Szrj /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
118138fd1498Szrj about updating it anywhere, and this should work as well most of the
118238fd1498Szrj time. */
118338fd1498Szrj if (e->flags & EDGE_IRREDUCIBLE_LOOP)
118438fd1498Szrj return true;
118538fd1498Szrj
118638fd1498Szrj return false;
118738fd1498Szrj }
118838fd1498Szrj
118938fd1498Szrj /* Helper function for one branch of the condition-phi-node. Return
119038fd1498Szrj true if the strongly connected component has been found following
119138fd1498Szrj this path. */
119238fd1498Szrj
119338fd1498Szrj static inline t_bool
follow_ssa_edge_in_condition_phi_branch(int i,struct loop * loop,gphi * condition_phi,gphi * halting_phi,tree * evolution_of_branch,tree init_cond,int limit)119438fd1498Szrj follow_ssa_edge_in_condition_phi_branch (int i,
119538fd1498Szrj struct loop *loop,
119638fd1498Szrj gphi *condition_phi,
119738fd1498Szrj gphi *halting_phi,
119838fd1498Szrj tree *evolution_of_branch,
119938fd1498Szrj tree init_cond, int limit)
120038fd1498Szrj {
120138fd1498Szrj tree branch = PHI_ARG_DEF (condition_phi, i);
120238fd1498Szrj *evolution_of_branch = chrec_dont_know;
120338fd1498Szrj
120438fd1498Szrj /* Do not follow back edges (they must belong to an irreducible loop, which
120538fd1498Szrj we really do not want to worry about). */
120638fd1498Szrj if (backedge_phi_arg_p (condition_phi, i))
120738fd1498Szrj return t_false;
120838fd1498Szrj
120938fd1498Szrj if (TREE_CODE (branch) == SSA_NAME)
121038fd1498Szrj {
121138fd1498Szrj *evolution_of_branch = init_cond;
121238fd1498Szrj return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
121338fd1498Szrj evolution_of_branch, limit);
121438fd1498Szrj }
121538fd1498Szrj
121638fd1498Szrj /* This case occurs when one of the condition branches sets
121738fd1498Szrj the variable to a constant: i.e. a phi-node like
121838fd1498Szrj "a_2 = PHI <a_7(5), 2(6)>;".
121938fd1498Szrj
122038fd1498Szrj FIXME: This case have to be refined correctly:
122138fd1498Szrj in some cases it is possible to say something better than
122238fd1498Szrj chrec_dont_know, for example using a wrap-around notation. */
122338fd1498Szrj return t_false;
122438fd1498Szrj }
122538fd1498Szrj
122638fd1498Szrj /* This function merges the branches of a condition-phi-node in a
122738fd1498Szrj loop. */
122838fd1498Szrj
122938fd1498Szrj static t_bool
follow_ssa_edge_in_condition_phi(struct loop * loop,gphi * condition_phi,gphi * halting_phi,tree * evolution_of_loop,int limit)123038fd1498Szrj follow_ssa_edge_in_condition_phi (struct loop *loop,
123138fd1498Szrj gphi *condition_phi,
123238fd1498Szrj gphi *halting_phi,
123338fd1498Szrj tree *evolution_of_loop, int limit)
123438fd1498Szrj {
123538fd1498Szrj int i, n;
123638fd1498Szrj tree init = *evolution_of_loop;
123738fd1498Szrj tree evolution_of_branch;
123838fd1498Szrj t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
123938fd1498Szrj halting_phi,
124038fd1498Szrj &evolution_of_branch,
124138fd1498Szrj init, limit);
124238fd1498Szrj if (res == t_false || res == t_dont_know)
124338fd1498Szrj return res;
124438fd1498Szrj
124538fd1498Szrj *evolution_of_loop = evolution_of_branch;
124638fd1498Szrj
124738fd1498Szrj n = gimple_phi_num_args (condition_phi);
124838fd1498Szrj for (i = 1; i < n; i++)
124938fd1498Szrj {
125038fd1498Szrj /* Quickly give up when the evolution of one of the branches is
125138fd1498Szrj not known. */
125238fd1498Szrj if (*evolution_of_loop == chrec_dont_know)
125338fd1498Szrj return t_true;
125438fd1498Szrj
125538fd1498Szrj /* Increase the limit by the PHI argument number to avoid exponential
125638fd1498Szrj time and memory complexity. */
125738fd1498Szrj res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
125838fd1498Szrj halting_phi,
125938fd1498Szrj &evolution_of_branch,
126038fd1498Szrj init, limit + i);
126138fd1498Szrj if (res == t_false || res == t_dont_know)
126238fd1498Szrj return res;
126338fd1498Szrj
126438fd1498Szrj *evolution_of_loop = chrec_merge (*evolution_of_loop,
126538fd1498Szrj evolution_of_branch);
126638fd1498Szrj }
126738fd1498Szrj
126838fd1498Szrj return t_true;
126938fd1498Szrj }
127038fd1498Szrj
127138fd1498Szrj /* Follow an SSA edge in an inner loop. It computes the overall
127238fd1498Szrj effect of the loop, and following the symbolic initial conditions,
127338fd1498Szrj it follows the edges in the parent loop. The inner loop is
127438fd1498Szrj considered as a single statement. */
127538fd1498Szrj
127638fd1498Szrj static t_bool
follow_ssa_edge_inner_loop_phi(struct loop * outer_loop,gphi * loop_phi_node,gphi * halting_phi,tree * evolution_of_loop,int limit)127738fd1498Szrj follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
127838fd1498Szrj gphi *loop_phi_node,
127938fd1498Szrj gphi *halting_phi,
128038fd1498Szrj tree *evolution_of_loop, int limit)
128138fd1498Szrj {
128238fd1498Szrj struct loop *loop = loop_containing_stmt (loop_phi_node);
128338fd1498Szrj tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
128438fd1498Szrj
128538fd1498Szrj /* Sometimes, the inner loop is too difficult to analyze, and the
128638fd1498Szrj result of the analysis is a symbolic parameter. */
128738fd1498Szrj if (ev == PHI_RESULT (loop_phi_node))
128838fd1498Szrj {
128938fd1498Szrj t_bool res = t_false;
129038fd1498Szrj int i, n = gimple_phi_num_args (loop_phi_node);
129138fd1498Szrj
129238fd1498Szrj for (i = 0; i < n; i++)
129338fd1498Szrj {
129438fd1498Szrj tree arg = PHI_ARG_DEF (loop_phi_node, i);
129538fd1498Szrj basic_block bb;
129638fd1498Szrj
129738fd1498Szrj /* Follow the edges that exit the inner loop. */
129838fd1498Szrj bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
129938fd1498Szrj if (!flow_bb_inside_loop_p (loop, bb))
130038fd1498Szrj res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
130138fd1498Szrj arg, halting_phi,
130238fd1498Szrj evolution_of_loop, limit);
130338fd1498Szrj if (res == t_true)
130438fd1498Szrj break;
130538fd1498Szrj }
130638fd1498Szrj
130738fd1498Szrj /* If the path crosses this loop-phi, give up. */
130838fd1498Szrj if (res == t_true)
130938fd1498Szrj *evolution_of_loop = chrec_dont_know;
131038fd1498Szrj
131138fd1498Szrj return res;
131238fd1498Szrj }
131338fd1498Szrj
131438fd1498Szrj /* Otherwise, compute the overall effect of the inner loop. */
131538fd1498Szrj ev = compute_overall_effect_of_inner_loop (loop, ev);
131638fd1498Szrj return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
131738fd1498Szrj evolution_of_loop, limit);
131838fd1498Szrj }
131938fd1498Szrj
132038fd1498Szrj /* Follow an SSA edge from a loop-phi-node to itself, constructing a
132138fd1498Szrj path that is analyzed on the return walk. */
132238fd1498Szrj
132338fd1498Szrj static t_bool
follow_ssa_edge(struct loop * loop,gimple * def,gphi * halting_phi,tree * evolution_of_loop,int limit)132438fd1498Szrj follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi,
132538fd1498Szrj tree *evolution_of_loop, int limit)
132638fd1498Szrj {
132738fd1498Szrj struct loop *def_loop;
132838fd1498Szrj
132938fd1498Szrj if (gimple_nop_p (def))
133038fd1498Szrj return t_false;
133138fd1498Szrj
133238fd1498Szrj /* Give up if the path is longer than the MAX that we allow. */
133338fd1498Szrj if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
133438fd1498Szrj return t_dont_know;
133538fd1498Szrj
133638fd1498Szrj def_loop = loop_containing_stmt (def);
133738fd1498Szrj
133838fd1498Szrj switch (gimple_code (def))
133938fd1498Szrj {
134038fd1498Szrj case GIMPLE_PHI:
134138fd1498Szrj if (!loop_phi_node_p (def))
134238fd1498Szrj /* DEF is a condition-phi-node. Follow the branches, and
134338fd1498Szrj record their evolutions. Finally, merge the collected
134438fd1498Szrj information and set the approximation to the main
134538fd1498Szrj variable. */
134638fd1498Szrj return follow_ssa_edge_in_condition_phi
134738fd1498Szrj (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
134838fd1498Szrj limit);
134938fd1498Szrj
135038fd1498Szrj /* When the analyzed phi is the halting_phi, the
135138fd1498Szrj depth-first search is over: we have found a path from
135238fd1498Szrj the halting_phi to itself in the loop. */
135338fd1498Szrj if (def == halting_phi)
135438fd1498Szrj return t_true;
135538fd1498Szrj
135638fd1498Szrj /* Otherwise, the evolution of the HALTING_PHI depends
135738fd1498Szrj on the evolution of another loop-phi-node, i.e. the
135838fd1498Szrj evolution function is a higher degree polynomial. */
135938fd1498Szrj if (def_loop == loop)
136038fd1498Szrj return t_false;
136138fd1498Szrj
136238fd1498Szrj /* Inner loop. */
136338fd1498Szrj if (flow_loop_nested_p (loop, def_loop))
136438fd1498Szrj return follow_ssa_edge_inner_loop_phi
136538fd1498Szrj (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
136638fd1498Szrj limit + 1);
136738fd1498Szrj
136838fd1498Szrj /* Outer loop. */
136938fd1498Szrj return t_false;
137038fd1498Szrj
137138fd1498Szrj case GIMPLE_ASSIGN:
137238fd1498Szrj return follow_ssa_edge_in_rhs (loop, def, halting_phi,
137338fd1498Szrj evolution_of_loop, limit);
137438fd1498Szrj
137538fd1498Szrj default:
137638fd1498Szrj /* At this level of abstraction, the program is just a set
137738fd1498Szrj of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
137838fd1498Szrj other node to be handled. */
137938fd1498Szrj return t_false;
138038fd1498Szrj }
138138fd1498Szrj }
138238fd1498Szrj
138338fd1498Szrj
138438fd1498Szrj /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
138538fd1498Szrj Handle below case and return the corresponding POLYNOMIAL_CHREC:
138638fd1498Szrj
138738fd1498Szrj # i_17 = PHI <i_13(5), 0(3)>
138838fd1498Szrj # _20 = PHI <_5(5), start_4(D)(3)>
138938fd1498Szrj ...
139038fd1498Szrj i_13 = i_17 + 1;
139138fd1498Szrj _5 = start_4(D) + i_13;
139238fd1498Szrj
139338fd1498Szrj Though variable _20 appears as a PEELED_CHREC in the form of
139438fd1498Szrj (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
139538fd1498Szrj
139638fd1498Szrj See PR41488. */
139738fd1498Szrj
139838fd1498Szrj static tree
simplify_peeled_chrec(struct loop * loop,tree arg,tree init_cond)139938fd1498Szrj simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
140038fd1498Szrj {
140138fd1498Szrj aff_tree aff1, aff2;
140238fd1498Szrj tree ev, left, right, type, step_val;
140338fd1498Szrj hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
140438fd1498Szrj
140538fd1498Szrj ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
140638fd1498Szrj if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
140738fd1498Szrj return chrec_dont_know;
140838fd1498Szrj
140938fd1498Szrj left = CHREC_LEFT (ev);
141038fd1498Szrj right = CHREC_RIGHT (ev);
141138fd1498Szrj type = TREE_TYPE (left);
141238fd1498Szrj step_val = chrec_fold_plus (type, init_cond, right);
141338fd1498Szrj
141438fd1498Szrj /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
141538fd1498Szrj if "left" equals to "init + right". */
141638fd1498Szrj if (operand_equal_p (left, step_val, 0))
141738fd1498Szrj {
141838fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
141938fd1498Szrj fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
142038fd1498Szrj
142138fd1498Szrj return build_polynomial_chrec (loop->num, init_cond, right);
142238fd1498Szrj }
142338fd1498Szrj
1424*e215fc28Szrj /* The affine code only deals with pointer and integer types. */
1425*e215fc28Szrj if (!POINTER_TYPE_P (type)
1426*e215fc28Szrj && !INTEGRAL_TYPE_P (type))
1427*e215fc28Szrj return chrec_dont_know;
1428*e215fc28Szrj
142938fd1498Szrj /* Try harder to check if they are equal. */
143038fd1498Szrj tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
143138fd1498Szrj tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
143238fd1498Szrj free_affine_expand_cache (&peeled_chrec_map);
143338fd1498Szrj aff_combination_scale (&aff2, -1);
143438fd1498Szrj aff_combination_add (&aff1, &aff2);
143538fd1498Szrj
143638fd1498Szrj /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
143738fd1498Szrj if "left" equals to "init + right". */
143838fd1498Szrj if (aff_combination_zero_p (&aff1))
143938fd1498Szrj {
144038fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
144138fd1498Szrj fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
144238fd1498Szrj
144338fd1498Szrj return build_polynomial_chrec (loop->num, init_cond, right);
144438fd1498Szrj }
144538fd1498Szrj return chrec_dont_know;
144638fd1498Szrj }
144738fd1498Szrj
144838fd1498Szrj /* Given a LOOP_PHI_NODE, this function determines the evolution
144938fd1498Szrj function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
145038fd1498Szrj
145138fd1498Szrj static tree
analyze_evolution_in_loop(gphi * loop_phi_node,tree init_cond)145238fd1498Szrj analyze_evolution_in_loop (gphi *loop_phi_node,
145338fd1498Szrj tree init_cond)
145438fd1498Szrj {
145538fd1498Szrj int i, n = gimple_phi_num_args (loop_phi_node);
145638fd1498Szrj tree evolution_function = chrec_not_analyzed_yet;
145738fd1498Szrj struct loop *loop = loop_containing_stmt (loop_phi_node);
145838fd1498Szrj basic_block bb;
145938fd1498Szrj static bool simplify_peeled_chrec_p = true;
146038fd1498Szrj
146138fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
146238fd1498Szrj {
146338fd1498Szrj fprintf (dump_file, "(analyze_evolution_in_loop \n");
146438fd1498Szrj fprintf (dump_file, " (loop_phi_node = ");
146538fd1498Szrj print_gimple_stmt (dump_file, loop_phi_node, 0);
146638fd1498Szrj fprintf (dump_file, ")\n");
146738fd1498Szrj }
146838fd1498Szrj
146938fd1498Szrj for (i = 0; i < n; i++)
147038fd1498Szrj {
147138fd1498Szrj tree arg = PHI_ARG_DEF (loop_phi_node, i);
147238fd1498Szrj gimple *ssa_chain;
147338fd1498Szrj tree ev_fn;
147438fd1498Szrj t_bool res;
147538fd1498Szrj
147638fd1498Szrj /* Select the edges that enter the loop body. */
147738fd1498Szrj bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
147838fd1498Szrj if (!flow_bb_inside_loop_p (loop, bb))
147938fd1498Szrj continue;
148038fd1498Szrj
148138fd1498Szrj if (TREE_CODE (arg) == SSA_NAME)
148238fd1498Szrj {
148338fd1498Szrj bool val = false;
148438fd1498Szrj
148538fd1498Szrj ssa_chain = SSA_NAME_DEF_STMT (arg);
148638fd1498Szrj
148738fd1498Szrj /* Pass in the initial condition to the follow edge function. */
148838fd1498Szrj ev_fn = init_cond;
148938fd1498Szrj res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
149038fd1498Szrj
149138fd1498Szrj /* If ev_fn has no evolution in the inner loop, and the
149238fd1498Szrj init_cond is not equal to ev_fn, then we have an
149338fd1498Szrj ambiguity between two possible values, as we cannot know
149438fd1498Szrj the number of iterations at this point. */
149538fd1498Szrj if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
149638fd1498Szrj && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
149738fd1498Szrj && !operand_equal_p (init_cond, ev_fn, 0))
149838fd1498Szrj ev_fn = chrec_dont_know;
149938fd1498Szrj }
150038fd1498Szrj else
150138fd1498Szrj res = t_false;
150238fd1498Szrj
150338fd1498Szrj /* When it is impossible to go back on the same
150438fd1498Szrj loop_phi_node by following the ssa edges, the
150538fd1498Szrj evolution is represented by a peeled chrec, i.e. the
150638fd1498Szrj first iteration, EV_FN has the value INIT_COND, then
150738fd1498Szrj all the other iterations it has the value of ARG.
150838fd1498Szrj For the moment, PEELED_CHREC nodes are not built. */
150938fd1498Szrj if (res != t_true)
151038fd1498Szrj {
151138fd1498Szrj ev_fn = chrec_dont_know;
151238fd1498Szrj /* Try to recognize POLYNOMIAL_CHREC which appears in
151338fd1498Szrj the form of PEELED_CHREC, but guard the process with
151438fd1498Szrj a bool variable to keep the analyzer from infinite
151538fd1498Szrj recurrence for real PEELED_RECs. */
151638fd1498Szrj if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
151738fd1498Szrj {
151838fd1498Szrj simplify_peeled_chrec_p = false;
151938fd1498Szrj ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
152038fd1498Szrj simplify_peeled_chrec_p = true;
152138fd1498Szrj }
152238fd1498Szrj }
152338fd1498Szrj
152438fd1498Szrj /* When there are multiple back edges of the loop (which in fact never
152538fd1498Szrj happens currently, but nevertheless), merge their evolutions. */
152638fd1498Szrj evolution_function = chrec_merge (evolution_function, ev_fn);
152738fd1498Szrj
152838fd1498Szrj if (evolution_function == chrec_dont_know)
152938fd1498Szrj break;
153038fd1498Szrj }
153138fd1498Szrj
153238fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
153338fd1498Szrj {
153438fd1498Szrj fprintf (dump_file, " (evolution_function = ");
153538fd1498Szrj print_generic_expr (dump_file, evolution_function);
153638fd1498Szrj fprintf (dump_file, "))\n");
153738fd1498Szrj }
153838fd1498Szrj
153938fd1498Szrj return evolution_function;
154038fd1498Szrj }
154138fd1498Szrj
154238fd1498Szrj /* Looks to see if VAR is a copy of a constant (via straightforward assignments
154338fd1498Szrj or degenerate phi's). If so, returns the constant; else, returns VAR. */
154438fd1498Szrj
154538fd1498Szrj static tree
follow_copies_to_constant(tree var)154638fd1498Szrj follow_copies_to_constant (tree var)
154738fd1498Szrj {
154838fd1498Szrj tree res = var;
154938fd1498Szrj while (TREE_CODE (res) == SSA_NAME
155038fd1498Szrj /* We face not updated SSA form in multiple places and this walk
155138fd1498Szrj may end up in sibling loops so we have to guard it. */
155238fd1498Szrj && !name_registered_for_update_p (res))
155338fd1498Szrj {
155438fd1498Szrj gimple *def = SSA_NAME_DEF_STMT (res);
155538fd1498Szrj if (gphi *phi = dyn_cast <gphi *> (def))
155638fd1498Szrj {
155738fd1498Szrj if (tree rhs = degenerate_phi_result (phi))
155838fd1498Szrj res = rhs;
155938fd1498Szrj else
156038fd1498Szrj break;
156138fd1498Szrj }
156238fd1498Szrj else if (gimple_assign_single_p (def))
156338fd1498Szrj /* Will exit loop if not an SSA_NAME. */
156438fd1498Szrj res = gimple_assign_rhs1 (def);
156538fd1498Szrj else
156638fd1498Szrj break;
156738fd1498Szrj }
156838fd1498Szrj if (CONSTANT_CLASS_P (res))
156938fd1498Szrj return res;
157038fd1498Szrj return var;
157138fd1498Szrj }
157238fd1498Szrj
157338fd1498Szrj /* Given a loop-phi-node, return the initial conditions of the
157438fd1498Szrj variable on entry of the loop. When the CCP has propagated
157538fd1498Szrj constants into the loop-phi-node, the initial condition is
157638fd1498Szrj instantiated, otherwise the initial condition is kept symbolic.
157738fd1498Szrj This analyzer does not analyze the evolution outside the current
157838fd1498Szrj loop, and leaves this task to the on-demand tree reconstructor. */
157938fd1498Szrj
158038fd1498Szrj static tree
analyze_initial_condition(gphi * loop_phi_node)158138fd1498Szrj analyze_initial_condition (gphi *loop_phi_node)
158238fd1498Szrj {
158338fd1498Szrj int i, n;
158438fd1498Szrj tree init_cond = chrec_not_analyzed_yet;
158538fd1498Szrj struct loop *loop = loop_containing_stmt (loop_phi_node);
158638fd1498Szrj
158738fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
158838fd1498Szrj {
158938fd1498Szrj fprintf (dump_file, "(analyze_initial_condition \n");
159038fd1498Szrj fprintf (dump_file, " (loop_phi_node = \n");
159138fd1498Szrj print_gimple_stmt (dump_file, loop_phi_node, 0);
159238fd1498Szrj fprintf (dump_file, ")\n");
159338fd1498Szrj }
159438fd1498Szrj
159538fd1498Szrj n = gimple_phi_num_args (loop_phi_node);
159638fd1498Szrj for (i = 0; i < n; i++)
159738fd1498Szrj {
159838fd1498Szrj tree branch = PHI_ARG_DEF (loop_phi_node, i);
159938fd1498Szrj basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
160038fd1498Szrj
160138fd1498Szrj /* When the branch is oriented to the loop's body, it does
160238fd1498Szrj not contribute to the initial condition. */
160338fd1498Szrj if (flow_bb_inside_loop_p (loop, bb))
160438fd1498Szrj continue;
160538fd1498Szrj
160638fd1498Szrj if (init_cond == chrec_not_analyzed_yet)
160738fd1498Szrj {
160838fd1498Szrj init_cond = branch;
160938fd1498Szrj continue;
161038fd1498Szrj }
161138fd1498Szrj
161238fd1498Szrj if (TREE_CODE (branch) == SSA_NAME)
161338fd1498Szrj {
161438fd1498Szrj init_cond = chrec_dont_know;
161538fd1498Szrj break;
161638fd1498Szrj }
161738fd1498Szrj
161838fd1498Szrj init_cond = chrec_merge (init_cond, branch);
161938fd1498Szrj }
162038fd1498Szrj
162138fd1498Szrj /* Ooops -- a loop without an entry??? */
162238fd1498Szrj if (init_cond == chrec_not_analyzed_yet)
162338fd1498Szrj init_cond = chrec_dont_know;
162438fd1498Szrj
162538fd1498Szrj /* We may not have fully constant propagated IL. Handle degenerate PHIs here
162638fd1498Szrj to not miss important early loop unrollings. */
162738fd1498Szrj init_cond = follow_copies_to_constant (init_cond);
162838fd1498Szrj
162938fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
163038fd1498Szrj {
163138fd1498Szrj fprintf (dump_file, " (init_cond = ");
163238fd1498Szrj print_generic_expr (dump_file, init_cond);
163338fd1498Szrj fprintf (dump_file, "))\n");
163438fd1498Szrj }
163538fd1498Szrj
163638fd1498Szrj return init_cond;
163738fd1498Szrj }
163838fd1498Szrj
163938fd1498Szrj /* Analyze the scalar evolution for LOOP_PHI_NODE. */
164038fd1498Szrj
164138fd1498Szrj static tree
interpret_loop_phi(struct loop * loop,gphi * loop_phi_node)164238fd1498Szrj interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
164338fd1498Szrj {
164438fd1498Szrj tree res;
164538fd1498Szrj struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
164638fd1498Szrj tree init_cond;
164738fd1498Szrj
164838fd1498Szrj gcc_assert (phi_loop == loop);
164938fd1498Szrj
165038fd1498Szrj /* Otherwise really interpret the loop phi. */
165138fd1498Szrj init_cond = analyze_initial_condition (loop_phi_node);
165238fd1498Szrj res = analyze_evolution_in_loop (loop_phi_node, init_cond);
165338fd1498Szrj
165438fd1498Szrj /* Verify we maintained the correct initial condition throughout
165538fd1498Szrj possible conversions in the SSA chain. */
165638fd1498Szrj if (res != chrec_dont_know)
165738fd1498Szrj {
165838fd1498Szrj tree new_init = res;
165938fd1498Szrj if (CONVERT_EXPR_P (res)
166038fd1498Szrj && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
166138fd1498Szrj new_init = fold_convert (TREE_TYPE (res),
166238fd1498Szrj CHREC_LEFT (TREE_OPERAND (res, 0)));
166338fd1498Szrj else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
166438fd1498Szrj new_init = CHREC_LEFT (res);
166538fd1498Szrj STRIP_USELESS_TYPE_CONVERSION (new_init);
166638fd1498Szrj if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
166738fd1498Szrj || !operand_equal_p (init_cond, new_init, 0))
166838fd1498Szrj return chrec_dont_know;
166938fd1498Szrj }
167038fd1498Szrj
167138fd1498Szrj return res;
167238fd1498Szrj }
167338fd1498Szrj
167438fd1498Szrj /* This function merges the branches of a condition-phi-node,
167538fd1498Szrj contained in the outermost loop, and whose arguments are already
167638fd1498Szrj analyzed. */
167738fd1498Szrj
167838fd1498Szrj static tree
interpret_condition_phi(struct loop * loop,gphi * condition_phi)167938fd1498Szrj interpret_condition_phi (struct loop *loop, gphi *condition_phi)
168038fd1498Szrj {
168138fd1498Szrj int i, n = gimple_phi_num_args (condition_phi);
168238fd1498Szrj tree res = chrec_not_analyzed_yet;
168338fd1498Szrj
168438fd1498Szrj for (i = 0; i < n; i++)
168538fd1498Szrj {
168638fd1498Szrj tree branch_chrec;
168738fd1498Szrj
168838fd1498Szrj if (backedge_phi_arg_p (condition_phi, i))
168938fd1498Szrj {
169038fd1498Szrj res = chrec_dont_know;
169138fd1498Szrj break;
169238fd1498Szrj }
169338fd1498Szrj
169438fd1498Szrj branch_chrec = analyze_scalar_evolution
169538fd1498Szrj (loop, PHI_ARG_DEF (condition_phi, i));
169638fd1498Szrj
169738fd1498Szrj res = chrec_merge (res, branch_chrec);
169838fd1498Szrj if (res == chrec_dont_know)
169938fd1498Szrj break;
170038fd1498Szrj }
170138fd1498Szrj
170238fd1498Szrj return res;
170338fd1498Szrj }
170438fd1498Szrj
170538fd1498Szrj /* Interpret the operation RHS1 OP RHS2. If we didn't
170638fd1498Szrj analyze this node before, follow the definitions until ending
170738fd1498Szrj either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
170838fd1498Szrj return path, this function propagates evolutions (ala constant copy
170938fd1498Szrj propagation). OPND1 is not a GIMPLE expression because we could
171038fd1498Szrj analyze the effect of an inner loop: see interpret_loop_phi. */
171138fd1498Szrj
171238fd1498Szrj static tree
interpret_rhs_expr(struct loop * loop,gimple * at_stmt,tree type,tree rhs1,enum tree_code code,tree rhs2)171338fd1498Szrj interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
171438fd1498Szrj tree type, tree rhs1, enum tree_code code, tree rhs2)
171538fd1498Szrj {
171638fd1498Szrj tree res, chrec1, chrec2, ctype;
171738fd1498Szrj gimple *def;
171838fd1498Szrj
171938fd1498Szrj if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
172038fd1498Szrj {
172138fd1498Szrj if (is_gimple_min_invariant (rhs1))
172238fd1498Szrj return chrec_convert (type, rhs1, at_stmt);
172338fd1498Szrj
172438fd1498Szrj if (code == SSA_NAME)
172538fd1498Szrj return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
172638fd1498Szrj at_stmt);
172738fd1498Szrj
172838fd1498Szrj if (code == ASSERT_EXPR)
172938fd1498Szrj {
173038fd1498Szrj rhs1 = ASSERT_EXPR_VAR (rhs1);
173138fd1498Szrj return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
173238fd1498Szrj at_stmt);
173338fd1498Szrj }
173438fd1498Szrj }
173538fd1498Szrj
173638fd1498Szrj switch (code)
173738fd1498Szrj {
173838fd1498Szrj case ADDR_EXPR:
173938fd1498Szrj if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
174038fd1498Szrj || handled_component_p (TREE_OPERAND (rhs1, 0)))
174138fd1498Szrj {
174238fd1498Szrj machine_mode mode;
174338fd1498Szrj poly_int64 bitsize, bitpos;
174438fd1498Szrj int unsignedp, reversep;
174538fd1498Szrj int volatilep = 0;
174638fd1498Szrj tree base, offset;
174738fd1498Szrj tree chrec3;
174838fd1498Szrj tree unitpos;
174938fd1498Szrj
175038fd1498Szrj base = get_inner_reference (TREE_OPERAND (rhs1, 0),
175138fd1498Szrj &bitsize, &bitpos, &offset, &mode,
175238fd1498Szrj &unsignedp, &reversep, &volatilep);
175338fd1498Szrj
175438fd1498Szrj if (TREE_CODE (base) == MEM_REF)
175538fd1498Szrj {
175638fd1498Szrj rhs2 = TREE_OPERAND (base, 1);
175738fd1498Szrj rhs1 = TREE_OPERAND (base, 0);
175838fd1498Szrj
175938fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
176038fd1498Szrj chrec2 = analyze_scalar_evolution (loop, rhs2);
176138fd1498Szrj chrec1 = chrec_convert (type, chrec1, at_stmt);
176238fd1498Szrj chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
176338fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
176438fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
176538fd1498Szrj res = chrec_fold_plus (type, chrec1, chrec2);
176638fd1498Szrj }
176738fd1498Szrj else
176838fd1498Szrj {
176938fd1498Szrj chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
177038fd1498Szrj chrec1 = chrec_convert (type, chrec1, at_stmt);
177138fd1498Szrj res = chrec1;
177238fd1498Szrj }
177338fd1498Szrj
177438fd1498Szrj if (offset != NULL_TREE)
177538fd1498Szrj {
177638fd1498Szrj chrec2 = analyze_scalar_evolution (loop, offset);
177738fd1498Szrj chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
177838fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
177938fd1498Szrj res = chrec_fold_plus (type, res, chrec2);
178038fd1498Szrj }
178138fd1498Szrj
178238fd1498Szrj if (maybe_ne (bitpos, 0))
178338fd1498Szrj {
178438fd1498Szrj unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
178538fd1498Szrj chrec3 = analyze_scalar_evolution (loop, unitpos);
178638fd1498Szrj chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
178738fd1498Szrj chrec3 = instantiate_parameters (loop, chrec3);
178838fd1498Szrj res = chrec_fold_plus (type, res, chrec3);
178938fd1498Szrj }
179038fd1498Szrj }
179138fd1498Szrj else
179238fd1498Szrj res = chrec_dont_know;
179338fd1498Szrj break;
179438fd1498Szrj
179538fd1498Szrj case POINTER_PLUS_EXPR:
179638fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
179738fd1498Szrj chrec2 = analyze_scalar_evolution (loop, rhs2);
179838fd1498Szrj chrec1 = chrec_convert (type, chrec1, at_stmt);
179938fd1498Szrj chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
180038fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
180138fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
180238fd1498Szrj res = chrec_fold_plus (type, chrec1, chrec2);
180338fd1498Szrj break;
180438fd1498Szrj
180538fd1498Szrj case PLUS_EXPR:
180638fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
180738fd1498Szrj chrec2 = analyze_scalar_evolution (loop, rhs2);
180838fd1498Szrj ctype = type;
180938fd1498Szrj /* When the stmt is conditionally executed re-write the CHREC
181038fd1498Szrj into a form that has well-defined behavior on overflow. */
181138fd1498Szrj if (at_stmt
181238fd1498Szrj && INTEGRAL_TYPE_P (type)
181338fd1498Szrj && ! TYPE_OVERFLOW_WRAPS (type)
181438fd1498Szrj && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
181538fd1498Szrj gimple_bb (at_stmt)))
181638fd1498Szrj ctype = unsigned_type_for (type);
181738fd1498Szrj chrec1 = chrec_convert (ctype, chrec1, at_stmt);
181838fd1498Szrj chrec2 = chrec_convert (ctype, chrec2, at_stmt);
181938fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
182038fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
182138fd1498Szrj res = chrec_fold_plus (ctype, chrec1, chrec2);
182238fd1498Szrj if (type != ctype)
182338fd1498Szrj res = chrec_convert (type, res, at_stmt);
182438fd1498Szrj break;
182538fd1498Szrj
182638fd1498Szrj case MINUS_EXPR:
182738fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
182838fd1498Szrj chrec2 = analyze_scalar_evolution (loop, rhs2);
182938fd1498Szrj ctype = type;
183038fd1498Szrj /* When the stmt is conditionally executed re-write the CHREC
183138fd1498Szrj into a form that has well-defined behavior on overflow. */
183238fd1498Szrj if (at_stmt
183338fd1498Szrj && INTEGRAL_TYPE_P (type)
183438fd1498Szrj && ! TYPE_OVERFLOW_WRAPS (type)
183538fd1498Szrj && ! dominated_by_p (CDI_DOMINATORS,
183638fd1498Szrj loop->latch, gimple_bb (at_stmt)))
183738fd1498Szrj ctype = unsigned_type_for (type);
183838fd1498Szrj chrec1 = chrec_convert (ctype, chrec1, at_stmt);
183938fd1498Szrj chrec2 = chrec_convert (ctype, chrec2, at_stmt);
184038fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
184138fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
184238fd1498Szrj res = chrec_fold_minus (ctype, chrec1, chrec2);
184338fd1498Szrj if (type != ctype)
184438fd1498Szrj res = chrec_convert (type, res, at_stmt);
184538fd1498Szrj break;
184638fd1498Szrj
184738fd1498Szrj case NEGATE_EXPR:
184838fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
184938fd1498Szrj ctype = type;
185038fd1498Szrj /* When the stmt is conditionally executed re-write the CHREC
185138fd1498Szrj into a form that has well-defined behavior on overflow. */
185238fd1498Szrj if (at_stmt
185338fd1498Szrj && INTEGRAL_TYPE_P (type)
185438fd1498Szrj && ! TYPE_OVERFLOW_WRAPS (type)
185538fd1498Szrj && ! dominated_by_p (CDI_DOMINATORS,
185638fd1498Szrj loop->latch, gimple_bb (at_stmt)))
185738fd1498Szrj ctype = unsigned_type_for (type);
185838fd1498Szrj chrec1 = chrec_convert (ctype, chrec1, at_stmt);
185938fd1498Szrj /* TYPE may be integer, real or complex, so use fold_convert. */
186038fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
186138fd1498Szrj res = chrec_fold_multiply (ctype, chrec1,
186238fd1498Szrj fold_convert (ctype, integer_minus_one_node));
186338fd1498Szrj if (type != ctype)
186438fd1498Szrj res = chrec_convert (type, res, at_stmt);
186538fd1498Szrj break;
186638fd1498Szrj
186738fd1498Szrj case BIT_NOT_EXPR:
186838fd1498Szrj /* Handle ~X as -1 - X. */
186938fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
187038fd1498Szrj chrec1 = chrec_convert (type, chrec1, at_stmt);
187138fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
187238fd1498Szrj res = chrec_fold_minus (type,
187338fd1498Szrj fold_convert (type, integer_minus_one_node),
187438fd1498Szrj chrec1);
187538fd1498Szrj break;
187638fd1498Szrj
187738fd1498Szrj case MULT_EXPR:
187838fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
187938fd1498Szrj chrec2 = analyze_scalar_evolution (loop, rhs2);
188038fd1498Szrj ctype = type;
188138fd1498Szrj /* When the stmt is conditionally executed re-write the CHREC
188238fd1498Szrj into a form that has well-defined behavior on overflow. */
188338fd1498Szrj if (at_stmt
188438fd1498Szrj && INTEGRAL_TYPE_P (type)
188538fd1498Szrj && ! TYPE_OVERFLOW_WRAPS (type)
188638fd1498Szrj && ! dominated_by_p (CDI_DOMINATORS,
188738fd1498Szrj loop->latch, gimple_bb (at_stmt)))
188838fd1498Szrj ctype = unsigned_type_for (type);
188938fd1498Szrj chrec1 = chrec_convert (ctype, chrec1, at_stmt);
189038fd1498Szrj chrec2 = chrec_convert (ctype, chrec2, at_stmt);
189138fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
189238fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
189338fd1498Szrj res = chrec_fold_multiply (ctype, chrec1, chrec2);
189438fd1498Szrj if (type != ctype)
189538fd1498Szrj res = chrec_convert (type, res, at_stmt);
189638fd1498Szrj break;
189738fd1498Szrj
189838fd1498Szrj case LSHIFT_EXPR:
189938fd1498Szrj {
190038fd1498Szrj /* Handle A<<B as A * (1<<B). */
190138fd1498Szrj tree uns = unsigned_type_for (type);
190238fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
190338fd1498Szrj chrec2 = analyze_scalar_evolution (loop, rhs2);
190438fd1498Szrj chrec1 = chrec_convert (uns, chrec1, at_stmt);
190538fd1498Szrj chrec1 = instantiate_parameters (loop, chrec1);
190638fd1498Szrj chrec2 = instantiate_parameters (loop, chrec2);
190738fd1498Szrj
190838fd1498Szrj tree one = build_int_cst (uns, 1);
190938fd1498Szrj chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
191038fd1498Szrj res = chrec_fold_multiply (uns, chrec1, chrec2);
191138fd1498Szrj res = chrec_convert (type, res, at_stmt);
191238fd1498Szrj }
191338fd1498Szrj break;
191438fd1498Szrj
191538fd1498Szrj CASE_CONVERT:
191638fd1498Szrj /* In case we have a truncation of a widened operation that in
191738fd1498Szrj the truncated type has undefined overflow behavior analyze
191838fd1498Szrj the operation done in an unsigned type of the same precision
191938fd1498Szrj as the final truncation. We cannot derive a scalar evolution
192038fd1498Szrj for the widened operation but for the truncated result. */
192138fd1498Szrj if (TREE_CODE (type) == INTEGER_TYPE
192238fd1498Szrj && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
192338fd1498Szrj && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
192438fd1498Szrj && TYPE_OVERFLOW_UNDEFINED (type)
192538fd1498Szrj && TREE_CODE (rhs1) == SSA_NAME
192638fd1498Szrj && (def = SSA_NAME_DEF_STMT (rhs1))
192738fd1498Szrj && is_gimple_assign (def)
192838fd1498Szrj && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
192938fd1498Szrj && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
193038fd1498Szrj {
193138fd1498Szrj tree utype = unsigned_type_for (type);
193238fd1498Szrj chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
193338fd1498Szrj gimple_assign_rhs1 (def),
193438fd1498Szrj gimple_assign_rhs_code (def),
193538fd1498Szrj gimple_assign_rhs2 (def));
193638fd1498Szrj }
193738fd1498Szrj else
193838fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
193938fd1498Szrj res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
194038fd1498Szrj break;
194138fd1498Szrj
194238fd1498Szrj case BIT_AND_EXPR:
194338fd1498Szrj /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
194438fd1498Szrj If A is SCEV and its value is in the range of representable set
194538fd1498Szrj of type unsigned short, the result expression is a (no-overflow)
194638fd1498Szrj SCEV. */
194738fd1498Szrj res = chrec_dont_know;
194838fd1498Szrj if (tree_fits_uhwi_p (rhs2))
194938fd1498Szrj {
195038fd1498Szrj int precision;
195138fd1498Szrj unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
195238fd1498Szrj
195338fd1498Szrj val ++;
195438fd1498Szrj /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
195538fd1498Szrj it's not the maximum value of a smaller type than rhs1. */
195638fd1498Szrj if (val != 0
195738fd1498Szrj && (precision = exact_log2 (val)) > 0
195838fd1498Szrj && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
195938fd1498Szrj {
196038fd1498Szrj tree utype = build_nonstandard_integer_type (precision, 1);
196138fd1498Szrj
196238fd1498Szrj if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
196338fd1498Szrj {
196438fd1498Szrj chrec1 = analyze_scalar_evolution (loop, rhs1);
196538fd1498Szrj chrec1 = chrec_convert (utype, chrec1, at_stmt);
196638fd1498Szrj res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
196738fd1498Szrj }
196838fd1498Szrj }
196938fd1498Szrj }
197038fd1498Szrj break;
197138fd1498Szrj
197238fd1498Szrj default:
197338fd1498Szrj res = chrec_dont_know;
197438fd1498Szrj break;
197538fd1498Szrj }
197638fd1498Szrj
197738fd1498Szrj return res;
197838fd1498Szrj }
197938fd1498Szrj
198038fd1498Szrj /* Interpret the expression EXPR. */
198138fd1498Szrj
198238fd1498Szrj static tree
interpret_expr(struct loop * loop,gimple * at_stmt,tree expr)198338fd1498Szrj interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
198438fd1498Szrj {
198538fd1498Szrj enum tree_code code;
198638fd1498Szrj tree type = TREE_TYPE (expr), op0, op1;
198738fd1498Szrj
198838fd1498Szrj if (automatically_generated_chrec_p (expr))
198938fd1498Szrj return expr;
199038fd1498Szrj
199138fd1498Szrj if (TREE_CODE (expr) == POLYNOMIAL_CHREC
199238fd1498Szrj || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
199338fd1498Szrj return chrec_dont_know;
199438fd1498Szrj
199538fd1498Szrj extract_ops_from_tree (expr, &code, &op0, &op1);
199638fd1498Szrj
199738fd1498Szrj return interpret_rhs_expr (loop, at_stmt, type,
199838fd1498Szrj op0, code, op1);
199938fd1498Szrj }
200038fd1498Szrj
200138fd1498Szrj /* Interpret the rhs of the assignment STMT. */
200238fd1498Szrj
200338fd1498Szrj static tree
interpret_gimple_assign(struct loop * loop,gimple * stmt)200438fd1498Szrj interpret_gimple_assign (struct loop *loop, gimple *stmt)
200538fd1498Szrj {
200638fd1498Szrj tree type = TREE_TYPE (gimple_assign_lhs (stmt));
200738fd1498Szrj enum tree_code code = gimple_assign_rhs_code (stmt);
200838fd1498Szrj
200938fd1498Szrj return interpret_rhs_expr (loop, stmt, type,
201038fd1498Szrj gimple_assign_rhs1 (stmt), code,
201138fd1498Szrj gimple_assign_rhs2 (stmt));
201238fd1498Szrj }
201338fd1498Szrj
201438fd1498Szrj
201538fd1498Szrj
201638fd1498Szrj /* This section contains all the entry points:
201738fd1498Szrj - number_of_iterations_in_loop,
201838fd1498Szrj - analyze_scalar_evolution,
201938fd1498Szrj - instantiate_parameters.
202038fd1498Szrj */
202138fd1498Szrj
202238fd1498Szrj /* Helper recursive function. */
202338fd1498Szrj
202438fd1498Szrj static tree
analyze_scalar_evolution_1(struct loop * loop,tree var)202538fd1498Szrj analyze_scalar_evolution_1 (struct loop *loop, tree var)
202638fd1498Szrj {
202738fd1498Szrj gimple *def;
202838fd1498Szrj basic_block bb;
202938fd1498Szrj struct loop *def_loop;
203038fd1498Szrj tree res;
203138fd1498Szrj
203238fd1498Szrj if (TREE_CODE (var) != SSA_NAME)
203338fd1498Szrj return interpret_expr (loop, NULL, var);
203438fd1498Szrj
203538fd1498Szrj def = SSA_NAME_DEF_STMT (var);
203638fd1498Szrj bb = gimple_bb (def);
203738fd1498Szrj def_loop = bb->loop_father;
203838fd1498Szrj
203938fd1498Szrj if (!flow_bb_inside_loop_p (loop, bb))
204038fd1498Szrj {
204138fd1498Szrj /* Keep symbolic form, but look through obvious copies for constants. */
204238fd1498Szrj res = follow_copies_to_constant (var);
204338fd1498Szrj goto set_and_end;
204438fd1498Szrj }
204538fd1498Szrj
204638fd1498Szrj if (loop != def_loop)
204738fd1498Szrj {
204838fd1498Szrj res = analyze_scalar_evolution_1 (def_loop, var);
204938fd1498Szrj struct loop *loop_to_skip = superloop_at_depth (def_loop,
205038fd1498Szrj loop_depth (loop) + 1);
205138fd1498Szrj res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
205238fd1498Szrj if (chrec_contains_symbols_defined_in_loop (res, loop->num))
205338fd1498Szrj res = analyze_scalar_evolution_1 (loop, res);
205438fd1498Szrj goto set_and_end;
205538fd1498Szrj }
205638fd1498Szrj
205738fd1498Szrj switch (gimple_code (def))
205838fd1498Szrj {
205938fd1498Szrj case GIMPLE_ASSIGN:
206038fd1498Szrj res = interpret_gimple_assign (loop, def);
206138fd1498Szrj break;
206238fd1498Szrj
206338fd1498Szrj case GIMPLE_PHI:
206438fd1498Szrj if (loop_phi_node_p (def))
206538fd1498Szrj res = interpret_loop_phi (loop, as_a <gphi *> (def));
206638fd1498Szrj else
206738fd1498Szrj res = interpret_condition_phi (loop, as_a <gphi *> (def));
206838fd1498Szrj break;
206938fd1498Szrj
207038fd1498Szrj default:
207138fd1498Szrj res = chrec_dont_know;
207238fd1498Szrj break;
207338fd1498Szrj }
207438fd1498Szrj
207538fd1498Szrj set_and_end:
207638fd1498Szrj
207738fd1498Szrj /* Keep the symbolic form. */
207838fd1498Szrj if (res == chrec_dont_know)
207938fd1498Szrj res = var;
208038fd1498Szrj
208138fd1498Szrj if (loop == def_loop)
208238fd1498Szrj set_scalar_evolution (block_before_loop (loop), var, res);
208338fd1498Szrj
208438fd1498Szrj return res;
208538fd1498Szrj }
208638fd1498Szrj
208738fd1498Szrj /* Analyzes and returns the scalar evolution of the ssa_name VAR in
208838fd1498Szrj LOOP. LOOP is the loop in which the variable is used.
208938fd1498Szrj
209038fd1498Szrj Example of use: having a pointer VAR to a SSA_NAME node, STMT a
209138fd1498Szrj pointer to the statement that uses this variable, in order to
209238fd1498Szrj determine the evolution function of the variable, use the following
209338fd1498Szrj calls:
209438fd1498Szrj
209538fd1498Szrj loop_p loop = loop_containing_stmt (stmt);
209638fd1498Szrj tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
209738fd1498Szrj tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
209838fd1498Szrj */
209938fd1498Szrj
210038fd1498Szrj tree
analyze_scalar_evolution(struct loop * loop,tree var)210138fd1498Szrj analyze_scalar_evolution (struct loop *loop, tree var)
210238fd1498Szrj {
210338fd1498Szrj tree res;
210438fd1498Szrj
210538fd1498Szrj /* ??? Fix callers. */
210638fd1498Szrj if (! loop)
210738fd1498Szrj return var;
210838fd1498Szrj
210938fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
211038fd1498Szrj {
211138fd1498Szrj fprintf (dump_file, "(analyze_scalar_evolution \n");
211238fd1498Szrj fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
211338fd1498Szrj fprintf (dump_file, " (scalar = ");
211438fd1498Szrj print_generic_expr (dump_file, var);
211538fd1498Szrj fprintf (dump_file, ")\n");
211638fd1498Szrj }
211738fd1498Szrj
211838fd1498Szrj res = get_scalar_evolution (block_before_loop (loop), var);
211938fd1498Szrj if (res == chrec_not_analyzed_yet)
212038fd1498Szrj res = analyze_scalar_evolution_1 (loop, var);
212138fd1498Szrj
212238fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
212338fd1498Szrj fprintf (dump_file, ")\n");
212438fd1498Szrj
212538fd1498Szrj return res;
212638fd1498Szrj }
212738fd1498Szrj
212838fd1498Szrj /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
212938fd1498Szrj
213038fd1498Szrj static tree
analyze_scalar_evolution_for_address_of(struct loop * loop,tree var)213138fd1498Szrj analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
213238fd1498Szrj {
213338fd1498Szrj return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
213438fd1498Szrj }
213538fd1498Szrj
213638fd1498Szrj /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
213738fd1498Szrj WRTO_LOOP (which should be a superloop of USE_LOOP)
213838fd1498Szrj
213938fd1498Szrj FOLDED_CASTS is set to true if resolve_mixers used
214038fd1498Szrj chrec_convert_aggressive (TODO -- not really, we are way too conservative
214138fd1498Szrj at the moment in order to keep things simple).
214238fd1498Szrj
214338fd1498Szrj To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
214438fd1498Szrj example:
214538fd1498Szrj
214638fd1498Szrj for (i = 0; i < 100; i++) -- loop 1
214738fd1498Szrj {
214838fd1498Szrj for (j = 0; j < 100; j++) -- loop 2
214938fd1498Szrj {
215038fd1498Szrj k1 = i;
215138fd1498Szrj k2 = j;
215238fd1498Szrj
215338fd1498Szrj use2 (k1, k2);
215438fd1498Szrj
215538fd1498Szrj for (t = 0; t < 100; t++) -- loop 3
215638fd1498Szrj use3 (k1, k2);
215738fd1498Szrj
215838fd1498Szrj }
215938fd1498Szrj use1 (k1, k2);
216038fd1498Szrj }
216138fd1498Szrj
216238fd1498Szrj Both k1 and k2 are invariants in loop3, thus
216338fd1498Szrj analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
216438fd1498Szrj analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
216538fd1498Szrj
216638fd1498Szrj As they are invariant, it does not matter whether we consider their
216738fd1498Szrj usage in loop 3 or loop 2, hence
216838fd1498Szrj analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
216938fd1498Szrj analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
217038fd1498Szrj analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
217138fd1498Szrj analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
217238fd1498Szrj
217338fd1498Szrj Similarly for their evolutions with respect to loop 1. The values of K2
217438fd1498Szrj in the use in loop 2 vary independently on loop 1, thus we cannot express
217538fd1498Szrj the evolution with respect to loop 1:
217638fd1498Szrj analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
217738fd1498Szrj analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
217838fd1498Szrj analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
217938fd1498Szrj analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
218038fd1498Szrj
218138fd1498Szrj The value of k2 in the use in loop 1 is known, though:
218238fd1498Szrj analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
218338fd1498Szrj analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
218438fd1498Szrj */
218538fd1498Szrj
218638fd1498Szrj static tree
analyze_scalar_evolution_in_loop(struct loop * wrto_loop,struct loop * use_loop,tree version,bool * folded_casts)218738fd1498Szrj analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
218838fd1498Szrj tree version, bool *folded_casts)
218938fd1498Szrj {
219038fd1498Szrj bool val = false;
219138fd1498Szrj tree ev = version, tmp;
219238fd1498Szrj
219338fd1498Szrj /* We cannot just do
219438fd1498Szrj
219538fd1498Szrj tmp = analyze_scalar_evolution (use_loop, version);
219638fd1498Szrj ev = resolve_mixers (wrto_loop, tmp, folded_casts);
219738fd1498Szrj
219838fd1498Szrj as resolve_mixers would query the scalar evolution with respect to
219938fd1498Szrj wrto_loop. For example, in the situation described in the function
220038fd1498Szrj comment, suppose that wrto_loop = loop1, use_loop = loop3 and
220138fd1498Szrj version = k2. Then
220238fd1498Szrj
220338fd1498Szrj analyze_scalar_evolution (use_loop, version) = k2
220438fd1498Szrj
220538fd1498Szrj and resolve_mixers (loop1, k2, folded_casts) finds that the value of
220638fd1498Szrj k2 in loop 1 is 100, which is a wrong result, since we are interested
220738fd1498Szrj in the value in loop 3.
220838fd1498Szrj
220938fd1498Szrj Instead, we need to proceed from use_loop to wrto_loop loop by loop,
221038fd1498Szrj each time checking that there is no evolution in the inner loop. */
221138fd1498Szrj
221238fd1498Szrj if (folded_casts)
221338fd1498Szrj *folded_casts = false;
221438fd1498Szrj while (1)
221538fd1498Szrj {
221638fd1498Szrj tmp = analyze_scalar_evolution (use_loop, ev);
221738fd1498Szrj ev = resolve_mixers (use_loop, tmp, folded_casts);
221838fd1498Szrj
221938fd1498Szrj if (use_loop == wrto_loop)
222038fd1498Szrj return ev;
222138fd1498Szrj
222238fd1498Szrj /* If the value of the use changes in the inner loop, we cannot express
222338fd1498Szrj its value in the outer loop (we might try to return interval chrec,
222438fd1498Szrj but we do not have a user for it anyway) */
222538fd1498Szrj if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
222638fd1498Szrj || !val)
222738fd1498Szrj return chrec_dont_know;
222838fd1498Szrj
222938fd1498Szrj use_loop = loop_outer (use_loop);
223038fd1498Szrj }
223138fd1498Szrj }
223238fd1498Szrj
223338fd1498Szrj
223438fd1498Szrj /* Hashtable helpers for a temporary hash-table used when
223538fd1498Szrj instantiating a CHREC or resolving mixers. For this use
223638fd1498Szrj instantiated_below is always the same. */
223738fd1498Szrj
223838fd1498Szrj struct instantiate_cache_type
223938fd1498Szrj {
224038fd1498Szrj htab_t map;
224138fd1498Szrj vec<scev_info_str> entries;
224238fd1498Szrj
instantiate_cache_typeinstantiate_cache_type224338fd1498Szrj instantiate_cache_type () : map (NULL), entries (vNULL) {}
224438fd1498Szrj ~instantiate_cache_type ();
getinstantiate_cache_type224538fd1498Szrj tree get (unsigned slot) { return entries[slot].chrec; }
setinstantiate_cache_type224638fd1498Szrj void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
224738fd1498Szrj };
224838fd1498Szrj
~instantiate_cache_type()224938fd1498Szrj instantiate_cache_type::~instantiate_cache_type ()
225038fd1498Szrj {
225138fd1498Szrj if (map != NULL)
225238fd1498Szrj {
225338fd1498Szrj htab_delete (map);
225438fd1498Szrj entries.release ();
225538fd1498Szrj }
225638fd1498Szrj }
225738fd1498Szrj
225838fd1498Szrj /* Cache to avoid infinite recursion when instantiating an SSA name.
225938fd1498Szrj Live during the outermost instantiate_scev or resolve_mixers call. */
226038fd1498Szrj static instantiate_cache_type *global_cache;
226138fd1498Szrj
226238fd1498Szrj /* Computes a hash function for database element ELT. */
226338fd1498Szrj
226438fd1498Szrj static inline hashval_t
hash_idx_scev_info(const void * elt_)226538fd1498Szrj hash_idx_scev_info (const void *elt_)
226638fd1498Szrj {
226738fd1498Szrj unsigned idx = ((size_t) elt_) - 2;
226838fd1498Szrj return scev_info_hasher::hash (&global_cache->entries[idx]);
226938fd1498Szrj }
227038fd1498Szrj
227138fd1498Szrj /* Compares database elements E1 and E2. */
227238fd1498Szrj
227338fd1498Szrj static inline int
eq_idx_scev_info(const void * e1,const void * e2)227438fd1498Szrj eq_idx_scev_info (const void *e1, const void *e2)
227538fd1498Szrj {
227638fd1498Szrj unsigned idx1 = ((size_t) e1) - 2;
227738fd1498Szrj return scev_info_hasher::equal (&global_cache->entries[idx1],
227838fd1498Szrj (const scev_info_str *) e2);
227938fd1498Szrj }
228038fd1498Szrj
228138fd1498Szrj /* Returns from CACHE the slot number of the cached chrec for NAME. */
228238fd1498Szrj
228338fd1498Szrj static unsigned
get_instantiated_value_entry(instantiate_cache_type & cache,tree name,edge instantiate_below)228438fd1498Szrj get_instantiated_value_entry (instantiate_cache_type &cache,
228538fd1498Szrj tree name, edge instantiate_below)
228638fd1498Szrj {
228738fd1498Szrj if (!cache.map)
228838fd1498Szrj {
228938fd1498Szrj cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
229038fd1498Szrj cache.entries.create (10);
229138fd1498Szrj }
229238fd1498Szrj
229338fd1498Szrj scev_info_str e;
229438fd1498Szrj e.name_version = SSA_NAME_VERSION (name);
229538fd1498Szrj e.instantiated_below = instantiate_below->dest->index;
229638fd1498Szrj void **slot = htab_find_slot_with_hash (cache.map, &e,
229738fd1498Szrj scev_info_hasher::hash (&e), INSERT);
229838fd1498Szrj if (!*slot)
229938fd1498Szrj {
230038fd1498Szrj e.chrec = chrec_not_analyzed_yet;
230138fd1498Szrj *slot = (void *)(size_t)(cache.entries.length () + 2);
230238fd1498Szrj cache.entries.safe_push (e);
230338fd1498Szrj }
230438fd1498Szrj
230538fd1498Szrj return ((size_t)*slot) - 2;
230638fd1498Szrj }
230738fd1498Szrj
230838fd1498Szrj
230938fd1498Szrj /* Return the closed_loop_phi node for VAR. If there is none, return
231038fd1498Szrj NULL_TREE. */
231138fd1498Szrj
231238fd1498Szrj static tree
loop_closed_phi_def(tree var)231338fd1498Szrj loop_closed_phi_def (tree var)
231438fd1498Szrj {
231538fd1498Szrj struct loop *loop;
231638fd1498Szrj edge exit;
231738fd1498Szrj gphi *phi;
231838fd1498Szrj gphi_iterator psi;
231938fd1498Szrj
232038fd1498Szrj if (var == NULL_TREE
232138fd1498Szrj || TREE_CODE (var) != SSA_NAME)
232238fd1498Szrj return NULL_TREE;
232338fd1498Szrj
232438fd1498Szrj loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
232538fd1498Szrj exit = single_exit (loop);
232638fd1498Szrj if (!exit)
232738fd1498Szrj return NULL_TREE;
232838fd1498Szrj
232938fd1498Szrj for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
233038fd1498Szrj {
233138fd1498Szrj phi = psi.phi ();
233238fd1498Szrj if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
233338fd1498Szrj return PHI_RESULT (phi);
233438fd1498Szrj }
233538fd1498Szrj
233638fd1498Szrj return NULL_TREE;
233738fd1498Szrj }
233838fd1498Szrj
233938fd1498Szrj static tree instantiate_scev_r (edge, struct loop *, struct loop *,
234038fd1498Szrj tree, bool *, int);
234138fd1498Szrj
234238fd1498Szrj /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
234338fd1498Szrj and EVOLUTION_LOOP, that were left under a symbolic form.
234438fd1498Szrj
234538fd1498Szrj CHREC is an SSA_NAME to be instantiated.
234638fd1498Szrj
234738fd1498Szrj CACHE is the cache of already instantiated values.
234838fd1498Szrj
234938fd1498Szrj Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
235038fd1498Szrj conversions that may wrap in signed/pointer type are folded, as long
235138fd1498Szrj as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
235238fd1498Szrj then we don't do such fold.
235338fd1498Szrj
235438fd1498Szrj SIZE_EXPR is used for computing the size of the expression to be
235538fd1498Szrj instantiated, and to stop if it exceeds some limit. */
235638fd1498Szrj
235738fd1498Szrj static tree
instantiate_scev_name(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,bool * fold_conversions,int size_expr)235838fd1498Szrj instantiate_scev_name (edge instantiate_below,
235938fd1498Szrj struct loop *evolution_loop, struct loop *inner_loop,
236038fd1498Szrj tree chrec,
236138fd1498Szrj bool *fold_conversions,
236238fd1498Szrj int size_expr)
236338fd1498Szrj {
236438fd1498Szrj tree res;
236538fd1498Szrj struct loop *def_loop;
236638fd1498Szrj basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
236738fd1498Szrj
236838fd1498Szrj /* A parameter, nothing to do. */
236938fd1498Szrj if (!def_bb
237038fd1498Szrj || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
237138fd1498Szrj return chrec;
237238fd1498Szrj
237338fd1498Szrj /* We cache the value of instantiated variable to avoid exponential
237438fd1498Szrj time complexity due to reevaluations. We also store the convenient
237538fd1498Szrj value in the cache in order to prevent infinite recursion -- we do
237638fd1498Szrj not want to instantiate the SSA_NAME if it is in a mixer
237738fd1498Szrj structure. This is used for avoiding the instantiation of
237838fd1498Szrj recursively defined functions, such as:
237938fd1498Szrj
238038fd1498Szrj | a_2 -> {0, +, 1, +, a_2}_1 */
238138fd1498Szrj
238238fd1498Szrj unsigned si = get_instantiated_value_entry (*global_cache,
238338fd1498Szrj chrec, instantiate_below);
238438fd1498Szrj if (global_cache->get (si) != chrec_not_analyzed_yet)
238538fd1498Szrj return global_cache->get (si);
238638fd1498Szrj
238738fd1498Szrj /* On recursion return chrec_dont_know. */
238838fd1498Szrj global_cache->set (si, chrec_dont_know);
238938fd1498Szrj
239038fd1498Szrj def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
239138fd1498Szrj
239238fd1498Szrj if (! dominated_by_p (CDI_DOMINATORS,
239338fd1498Szrj def_loop->header, instantiate_below->dest))
239438fd1498Szrj {
239538fd1498Szrj gimple *def = SSA_NAME_DEF_STMT (chrec);
239638fd1498Szrj if (gassign *ass = dyn_cast <gassign *> (def))
239738fd1498Szrj {
239838fd1498Szrj switch (gimple_assign_rhs_class (ass))
239938fd1498Szrj {
240038fd1498Szrj case GIMPLE_UNARY_RHS:
240138fd1498Szrj {
240238fd1498Szrj tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
240338fd1498Szrj inner_loop, gimple_assign_rhs1 (ass),
240438fd1498Szrj fold_conversions, size_expr);
240538fd1498Szrj if (op0 == chrec_dont_know)
240638fd1498Szrj return chrec_dont_know;
240738fd1498Szrj res = fold_build1 (gimple_assign_rhs_code (ass),
240838fd1498Szrj TREE_TYPE (chrec), op0);
240938fd1498Szrj break;
241038fd1498Szrj }
241138fd1498Szrj case GIMPLE_BINARY_RHS:
241238fd1498Szrj {
241338fd1498Szrj tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
241438fd1498Szrj inner_loop, gimple_assign_rhs1 (ass),
241538fd1498Szrj fold_conversions, size_expr);
241638fd1498Szrj if (op0 == chrec_dont_know)
241738fd1498Szrj return chrec_dont_know;
241838fd1498Szrj tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
241938fd1498Szrj inner_loop, gimple_assign_rhs2 (ass),
242038fd1498Szrj fold_conversions, size_expr);
242138fd1498Szrj if (op1 == chrec_dont_know)
242238fd1498Szrj return chrec_dont_know;
242338fd1498Szrj res = fold_build2 (gimple_assign_rhs_code (ass),
242438fd1498Szrj TREE_TYPE (chrec), op0, op1);
242538fd1498Szrj break;
242638fd1498Szrj }
242738fd1498Szrj default:
242838fd1498Szrj res = chrec_dont_know;
242938fd1498Szrj }
243038fd1498Szrj }
243138fd1498Szrj else
243238fd1498Szrj res = chrec_dont_know;
243338fd1498Szrj global_cache->set (si, res);
243438fd1498Szrj return res;
243538fd1498Szrj }
243638fd1498Szrj
243738fd1498Szrj /* If the analysis yields a parametric chrec, instantiate the
243838fd1498Szrj result again. */
243938fd1498Szrj res = analyze_scalar_evolution (def_loop, chrec);
244038fd1498Szrj
244138fd1498Szrj /* Don't instantiate default definitions. */
244238fd1498Szrj if (TREE_CODE (res) == SSA_NAME
244338fd1498Szrj && SSA_NAME_IS_DEFAULT_DEF (res))
244438fd1498Szrj ;
244538fd1498Szrj
244638fd1498Szrj /* Don't instantiate loop-closed-ssa phi nodes. */
244738fd1498Szrj else if (TREE_CODE (res) == SSA_NAME
244838fd1498Szrj && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
244938fd1498Szrj > loop_depth (def_loop))
245038fd1498Szrj {
245138fd1498Szrj if (res == chrec)
245238fd1498Szrj res = loop_closed_phi_def (chrec);
245338fd1498Szrj else
245438fd1498Szrj res = chrec;
245538fd1498Szrj
245638fd1498Szrj /* When there is no loop_closed_phi_def, it means that the
245738fd1498Szrj variable is not used after the loop: try to still compute the
245838fd1498Szrj value of the variable when exiting the loop. */
245938fd1498Szrj if (res == NULL_TREE)
246038fd1498Szrj {
246138fd1498Szrj loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
246238fd1498Szrj res = analyze_scalar_evolution (loop, chrec);
246338fd1498Szrj res = compute_overall_effect_of_inner_loop (loop, res);
246438fd1498Szrj res = instantiate_scev_r (instantiate_below, evolution_loop,
246538fd1498Szrj inner_loop, res,
246638fd1498Szrj fold_conversions, size_expr);
246738fd1498Szrj }
246838fd1498Szrj else if (dominated_by_p (CDI_DOMINATORS,
246938fd1498Szrj gimple_bb (SSA_NAME_DEF_STMT (res)),
247038fd1498Szrj instantiate_below->dest))
247138fd1498Szrj res = chrec_dont_know;
247238fd1498Szrj }
247338fd1498Szrj
247438fd1498Szrj else if (res != chrec_dont_know)
247538fd1498Szrj {
247638fd1498Szrj if (inner_loop
247738fd1498Szrj && def_bb->loop_father != inner_loop
247838fd1498Szrj && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
247938fd1498Szrj /* ??? We could try to compute the overall effect of the loop here. */
248038fd1498Szrj res = chrec_dont_know;
248138fd1498Szrj else
248238fd1498Szrj res = instantiate_scev_r (instantiate_below, evolution_loop,
248338fd1498Szrj inner_loop, res,
248438fd1498Szrj fold_conversions, size_expr);
248538fd1498Szrj }
248638fd1498Szrj
248738fd1498Szrj /* Store the correct value to the cache. */
248838fd1498Szrj global_cache->set (si, res);
248938fd1498Szrj return res;
249038fd1498Szrj }
249138fd1498Szrj
249238fd1498Szrj /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
249338fd1498Szrj and EVOLUTION_LOOP, that were left under a symbolic form.
249438fd1498Szrj
249538fd1498Szrj CHREC is a polynomial chain of recurrence to be instantiated.
249638fd1498Szrj
249738fd1498Szrj CACHE is the cache of already instantiated values.
249838fd1498Szrj
249938fd1498Szrj Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
250038fd1498Szrj conversions that may wrap in signed/pointer type are folded, as long
250138fd1498Szrj as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
250238fd1498Szrj then we don't do such fold.
250338fd1498Szrj
250438fd1498Szrj SIZE_EXPR is used for computing the size of the expression to be
250538fd1498Szrj instantiated, and to stop if it exceeds some limit. */
250638fd1498Szrj
250738fd1498Szrj static tree
instantiate_scev_poly(edge instantiate_below,struct loop * evolution_loop,struct loop *,tree chrec,bool * fold_conversions,int size_expr)250838fd1498Szrj instantiate_scev_poly (edge instantiate_below,
250938fd1498Szrj struct loop *evolution_loop, struct loop *,
251038fd1498Szrj tree chrec, bool *fold_conversions, int size_expr)
251138fd1498Szrj {
251238fd1498Szrj tree op1;
251338fd1498Szrj tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
251438fd1498Szrj get_chrec_loop (chrec),
251538fd1498Szrj CHREC_LEFT (chrec), fold_conversions,
251638fd1498Szrj size_expr);
251738fd1498Szrj if (op0 == chrec_dont_know)
251838fd1498Szrj return chrec_dont_know;
251938fd1498Szrj
252038fd1498Szrj op1 = instantiate_scev_r (instantiate_below, evolution_loop,
252138fd1498Szrj get_chrec_loop (chrec),
252238fd1498Szrj CHREC_RIGHT (chrec), fold_conversions,
252338fd1498Szrj size_expr);
252438fd1498Szrj if (op1 == chrec_dont_know)
252538fd1498Szrj return chrec_dont_know;
252638fd1498Szrj
252738fd1498Szrj if (CHREC_LEFT (chrec) != op0
252838fd1498Szrj || CHREC_RIGHT (chrec) != op1)
252938fd1498Szrj {
253038fd1498Szrj op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
253138fd1498Szrj chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
253238fd1498Szrj }
253338fd1498Szrj
253438fd1498Szrj return chrec;
253538fd1498Szrj }
253638fd1498Szrj
253738fd1498Szrj /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
253838fd1498Szrj and EVOLUTION_LOOP, that were left under a symbolic form.
253938fd1498Szrj
254038fd1498Szrj "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
254138fd1498Szrj
254238fd1498Szrj CACHE is the cache of already instantiated values.
254338fd1498Szrj
254438fd1498Szrj Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
254538fd1498Szrj conversions that may wrap in signed/pointer type are folded, as long
254638fd1498Szrj as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
254738fd1498Szrj then we don't do such fold.
254838fd1498Szrj
254938fd1498Szrj SIZE_EXPR is used for computing the size of the expression to be
255038fd1498Szrj instantiated, and to stop if it exceeds some limit. */
255138fd1498Szrj
255238fd1498Szrj static tree
instantiate_scev_binary(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,enum tree_code code,tree type,tree c0,tree c1,bool * fold_conversions,int size_expr)255338fd1498Szrj instantiate_scev_binary (edge instantiate_below,
255438fd1498Szrj struct loop *evolution_loop, struct loop *inner_loop,
255538fd1498Szrj tree chrec, enum tree_code code,
255638fd1498Szrj tree type, tree c0, tree c1,
255738fd1498Szrj bool *fold_conversions, int size_expr)
255838fd1498Szrj {
255938fd1498Szrj tree op1;
256038fd1498Szrj tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
256138fd1498Szrj c0, fold_conversions, size_expr);
256238fd1498Szrj if (op0 == chrec_dont_know)
256338fd1498Szrj return chrec_dont_know;
256438fd1498Szrj
256538fd1498Szrj op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
256638fd1498Szrj c1, fold_conversions, size_expr);
256738fd1498Szrj if (op1 == chrec_dont_know)
256838fd1498Szrj return chrec_dont_know;
256938fd1498Szrj
257038fd1498Szrj if (c0 != op0
257138fd1498Szrj || c1 != op1)
257238fd1498Szrj {
257338fd1498Szrj op0 = chrec_convert (type, op0, NULL);
257438fd1498Szrj op1 = chrec_convert_rhs (type, op1, NULL);
257538fd1498Szrj
257638fd1498Szrj switch (code)
257738fd1498Szrj {
257838fd1498Szrj case POINTER_PLUS_EXPR:
257938fd1498Szrj case PLUS_EXPR:
258038fd1498Szrj return chrec_fold_plus (type, op0, op1);
258138fd1498Szrj
258238fd1498Szrj case MINUS_EXPR:
258338fd1498Szrj return chrec_fold_minus (type, op0, op1);
258438fd1498Szrj
258538fd1498Szrj case MULT_EXPR:
258638fd1498Szrj return chrec_fold_multiply (type, op0, op1);
258738fd1498Szrj
258838fd1498Szrj default:
258938fd1498Szrj gcc_unreachable ();
259038fd1498Szrj }
259138fd1498Szrj }
259238fd1498Szrj
259338fd1498Szrj return chrec ? chrec : fold_build2 (code, type, c0, c1);
259438fd1498Szrj }
259538fd1498Szrj
259638fd1498Szrj /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
259738fd1498Szrj and EVOLUTION_LOOP, that were left under a symbolic form.
259838fd1498Szrj
259938fd1498Szrj "CHREC" that stands for a convert expression "(TYPE) OP" is to be
260038fd1498Szrj instantiated.
260138fd1498Szrj
260238fd1498Szrj CACHE is the cache of already instantiated values.
260338fd1498Szrj
260438fd1498Szrj Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
260538fd1498Szrj conversions that may wrap in signed/pointer type are folded, as long
260638fd1498Szrj as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
260738fd1498Szrj then we don't do such fold.
260838fd1498Szrj
260938fd1498Szrj SIZE_EXPR is used for computing the size of the expression to be
261038fd1498Szrj instantiated, and to stop if it exceeds some limit. */
261138fd1498Szrj
261238fd1498Szrj static tree
instantiate_scev_convert(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,tree type,tree op,bool * fold_conversions,int size_expr)261338fd1498Szrj instantiate_scev_convert (edge instantiate_below,
261438fd1498Szrj struct loop *evolution_loop, struct loop *inner_loop,
261538fd1498Szrj tree chrec, tree type, tree op,
261638fd1498Szrj bool *fold_conversions, int size_expr)
261738fd1498Szrj {
261838fd1498Szrj tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
261938fd1498Szrj inner_loop, op,
262038fd1498Szrj fold_conversions, size_expr);
262138fd1498Szrj
262238fd1498Szrj if (op0 == chrec_dont_know)
262338fd1498Szrj return chrec_dont_know;
262438fd1498Szrj
262538fd1498Szrj if (fold_conversions)
262638fd1498Szrj {
262738fd1498Szrj tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
262838fd1498Szrj if (tmp)
262938fd1498Szrj return tmp;
263038fd1498Szrj
263138fd1498Szrj /* If we used chrec_convert_aggressive, we can no longer assume that
263238fd1498Szrj signed chrecs do not overflow, as chrec_convert does, so avoid
263338fd1498Szrj calling it in that case. */
263438fd1498Szrj if (*fold_conversions)
263538fd1498Szrj {
263638fd1498Szrj if (chrec && op0 == op)
263738fd1498Szrj return chrec;
263838fd1498Szrj
263938fd1498Szrj return fold_convert (type, op0);
264038fd1498Szrj }
264138fd1498Szrj }
264238fd1498Szrj
264338fd1498Szrj return chrec_convert (type, op0, NULL);
264438fd1498Szrj }
264538fd1498Szrj
264638fd1498Szrj /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
264738fd1498Szrj and EVOLUTION_LOOP, that were left under a symbolic form.
264838fd1498Szrj
264938fd1498Szrj CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
265038fd1498Szrj Handle ~X as -1 - X.
265138fd1498Szrj Handle -X as -1 * X.
265238fd1498Szrj
265338fd1498Szrj CACHE is the cache of already instantiated values.
265438fd1498Szrj
265538fd1498Szrj Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
265638fd1498Szrj conversions that may wrap in signed/pointer type are folded, as long
265738fd1498Szrj as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
265838fd1498Szrj then we don't do such fold.
265938fd1498Szrj
266038fd1498Szrj SIZE_EXPR is used for computing the size of the expression to be
266138fd1498Szrj instantiated, and to stop if it exceeds some limit. */
266238fd1498Szrj
266338fd1498Szrj static tree
instantiate_scev_not(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,enum tree_code code,tree type,tree op,bool * fold_conversions,int size_expr)266438fd1498Szrj instantiate_scev_not (edge instantiate_below,
266538fd1498Szrj struct loop *evolution_loop, struct loop *inner_loop,
266638fd1498Szrj tree chrec,
266738fd1498Szrj enum tree_code code, tree type, tree op,
266838fd1498Szrj bool *fold_conversions, int size_expr)
266938fd1498Szrj {
267038fd1498Szrj tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
267138fd1498Szrj inner_loop, op,
267238fd1498Szrj fold_conversions, size_expr);
267338fd1498Szrj
267438fd1498Szrj if (op0 == chrec_dont_know)
267538fd1498Szrj return chrec_dont_know;
267638fd1498Szrj
267738fd1498Szrj if (op != op0)
267838fd1498Szrj {
267938fd1498Szrj op0 = chrec_convert (type, op0, NULL);
268038fd1498Szrj
268138fd1498Szrj switch (code)
268238fd1498Szrj {
268338fd1498Szrj case BIT_NOT_EXPR:
268438fd1498Szrj return chrec_fold_minus
268538fd1498Szrj (type, fold_convert (type, integer_minus_one_node), op0);
268638fd1498Szrj
268738fd1498Szrj case NEGATE_EXPR:
268838fd1498Szrj return chrec_fold_multiply
268938fd1498Szrj (type, fold_convert (type, integer_minus_one_node), op0);
269038fd1498Szrj
269138fd1498Szrj default:
269238fd1498Szrj gcc_unreachable ();
269338fd1498Szrj }
269438fd1498Szrj }
269538fd1498Szrj
269638fd1498Szrj return chrec ? chrec : fold_build1 (code, type, op0);
269738fd1498Szrj }
269838fd1498Szrj
269938fd1498Szrj /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
270038fd1498Szrj and EVOLUTION_LOOP, that were left under a symbolic form.
270138fd1498Szrj
270238fd1498Szrj CHREC is the scalar evolution to instantiate.
270338fd1498Szrj
270438fd1498Szrj CACHE is the cache of already instantiated values.
270538fd1498Szrj
270638fd1498Szrj Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
270738fd1498Szrj conversions that may wrap in signed/pointer type are folded, as long
270838fd1498Szrj as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
270938fd1498Szrj then we don't do such fold.
271038fd1498Szrj
271138fd1498Szrj SIZE_EXPR is used for computing the size of the expression to be
271238fd1498Szrj instantiated, and to stop if it exceeds some limit. */
271338fd1498Szrj
271438fd1498Szrj static tree
instantiate_scev_r(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,bool * fold_conversions,int size_expr)271538fd1498Szrj instantiate_scev_r (edge instantiate_below,
271638fd1498Szrj struct loop *evolution_loop, struct loop *inner_loop,
271738fd1498Szrj tree chrec,
271838fd1498Szrj bool *fold_conversions, int size_expr)
271938fd1498Szrj {
272038fd1498Szrj /* Give up if the expression is larger than the MAX that we allow. */
272138fd1498Szrj if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
272238fd1498Szrj return chrec_dont_know;
272338fd1498Szrj
272438fd1498Szrj if (chrec == NULL_TREE
272538fd1498Szrj || automatically_generated_chrec_p (chrec)
272638fd1498Szrj || is_gimple_min_invariant (chrec))
272738fd1498Szrj return chrec;
272838fd1498Szrj
272938fd1498Szrj switch (TREE_CODE (chrec))
273038fd1498Szrj {
273138fd1498Szrj case SSA_NAME:
273238fd1498Szrj return instantiate_scev_name (instantiate_below, evolution_loop,
273338fd1498Szrj inner_loop, chrec,
273438fd1498Szrj fold_conversions, size_expr);
273538fd1498Szrj
273638fd1498Szrj case POLYNOMIAL_CHREC:
273738fd1498Szrj return instantiate_scev_poly (instantiate_below, evolution_loop,
273838fd1498Szrj inner_loop, chrec,
273938fd1498Szrj fold_conversions, size_expr);
274038fd1498Szrj
274138fd1498Szrj case POINTER_PLUS_EXPR:
274238fd1498Szrj case PLUS_EXPR:
274338fd1498Szrj case MINUS_EXPR:
274438fd1498Szrj case MULT_EXPR:
274538fd1498Szrj return instantiate_scev_binary (instantiate_below, evolution_loop,
274638fd1498Szrj inner_loop, chrec,
274738fd1498Szrj TREE_CODE (chrec), chrec_type (chrec),
274838fd1498Szrj TREE_OPERAND (chrec, 0),
274938fd1498Szrj TREE_OPERAND (chrec, 1),
275038fd1498Szrj fold_conversions, size_expr);
275138fd1498Szrj
275238fd1498Szrj CASE_CONVERT:
275338fd1498Szrj return instantiate_scev_convert (instantiate_below, evolution_loop,
275438fd1498Szrj inner_loop, chrec,
275538fd1498Szrj TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
275638fd1498Szrj fold_conversions, size_expr);
275738fd1498Szrj
275838fd1498Szrj case NEGATE_EXPR:
275938fd1498Szrj case BIT_NOT_EXPR:
276038fd1498Szrj return instantiate_scev_not (instantiate_below, evolution_loop,
276138fd1498Szrj inner_loop, chrec,
276238fd1498Szrj TREE_CODE (chrec), TREE_TYPE (chrec),
276338fd1498Szrj TREE_OPERAND (chrec, 0),
276438fd1498Szrj fold_conversions, size_expr);
276538fd1498Szrj
276638fd1498Szrj case ADDR_EXPR:
276738fd1498Szrj if (is_gimple_min_invariant (chrec))
276838fd1498Szrj return chrec;
276938fd1498Szrj /* Fallthru. */
277038fd1498Szrj case SCEV_NOT_KNOWN:
277138fd1498Szrj return chrec_dont_know;
277238fd1498Szrj
277338fd1498Szrj case SCEV_KNOWN:
277438fd1498Szrj return chrec_known;
277538fd1498Szrj
277638fd1498Szrj default:
277738fd1498Szrj if (CONSTANT_CLASS_P (chrec))
277838fd1498Szrj return chrec;
277938fd1498Szrj return chrec_dont_know;
278038fd1498Szrj }
278138fd1498Szrj }
278238fd1498Szrj
278338fd1498Szrj /* Analyze all the parameters of the chrec that were left under a
278438fd1498Szrj symbolic form. INSTANTIATE_BELOW is the basic block that stops the
278538fd1498Szrj recursive instantiation of parameters: a parameter is a variable
278638fd1498Szrj that is defined in a basic block that dominates INSTANTIATE_BELOW or
278738fd1498Szrj a function parameter. */
278838fd1498Szrj
278938fd1498Szrj tree
instantiate_scev(edge instantiate_below,struct loop * evolution_loop,tree chrec)279038fd1498Szrj instantiate_scev (edge instantiate_below, struct loop *evolution_loop,
279138fd1498Szrj tree chrec)
279238fd1498Szrj {
279338fd1498Szrj tree res;
279438fd1498Szrj
279538fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
279638fd1498Szrj {
279738fd1498Szrj fprintf (dump_file, "(instantiate_scev \n");
279838fd1498Szrj fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
279938fd1498Szrj instantiate_below->src->index, instantiate_below->dest->index);
280038fd1498Szrj if (evolution_loop)
280138fd1498Szrj fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
280238fd1498Szrj fprintf (dump_file, " (chrec = ");
280338fd1498Szrj print_generic_expr (dump_file, chrec);
280438fd1498Szrj fprintf (dump_file, ")\n");
280538fd1498Szrj }
280638fd1498Szrj
280738fd1498Szrj bool destr = false;
280838fd1498Szrj if (!global_cache)
280938fd1498Szrj {
281038fd1498Szrj global_cache = new instantiate_cache_type;
281138fd1498Szrj destr = true;
281238fd1498Szrj }
281338fd1498Szrj
281438fd1498Szrj res = instantiate_scev_r (instantiate_below, evolution_loop,
281538fd1498Szrj NULL, chrec, NULL, 0);
281638fd1498Szrj
281738fd1498Szrj if (destr)
281838fd1498Szrj {
281938fd1498Szrj delete global_cache;
282038fd1498Szrj global_cache = NULL;
282138fd1498Szrj }
282238fd1498Szrj
282338fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
282438fd1498Szrj {
282538fd1498Szrj fprintf (dump_file, " (res = ");
282638fd1498Szrj print_generic_expr (dump_file, res);
282738fd1498Szrj fprintf (dump_file, "))\n");
282838fd1498Szrj }
282938fd1498Szrj
283038fd1498Szrj return res;
283138fd1498Szrj }
283238fd1498Szrj
283338fd1498Szrj /* Similar to instantiate_parameters, but does not introduce the
283438fd1498Szrj evolutions in outer loops for LOOP invariants in CHREC, and does not
283538fd1498Szrj care about causing overflows, as long as they do not affect value
283638fd1498Szrj of an expression. */
283738fd1498Szrj
283838fd1498Szrj tree
resolve_mixers(struct loop * loop,tree chrec,bool * folded_casts)283938fd1498Szrj resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
284038fd1498Szrj {
284138fd1498Szrj bool destr = false;
284238fd1498Szrj bool fold_conversions = false;
284338fd1498Szrj if (!global_cache)
284438fd1498Szrj {
284538fd1498Szrj global_cache = new instantiate_cache_type;
284638fd1498Szrj destr = true;
284738fd1498Szrj }
284838fd1498Szrj
284938fd1498Szrj tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
285038fd1498Szrj chrec, &fold_conversions, 0);
285138fd1498Szrj
285238fd1498Szrj if (folded_casts && !*folded_casts)
285338fd1498Szrj *folded_casts = fold_conversions;
285438fd1498Szrj
285538fd1498Szrj if (destr)
285638fd1498Szrj {
285738fd1498Szrj delete global_cache;
285838fd1498Szrj global_cache = NULL;
285938fd1498Szrj }
286038fd1498Szrj
286138fd1498Szrj return ret;
286238fd1498Szrj }
286338fd1498Szrj
286438fd1498Szrj /* Entry point for the analysis of the number of iterations pass.
286538fd1498Szrj This function tries to safely approximate the number of iterations
286638fd1498Szrj the loop will run. When this property is not decidable at compile
286738fd1498Szrj time, the result is chrec_dont_know. Otherwise the result is a
286838fd1498Szrj scalar or a symbolic parameter. When the number of iterations may
286938fd1498Szrj be equal to zero and the property cannot be determined at compile
287038fd1498Szrj time, the result is a COND_EXPR that represents in a symbolic form
287138fd1498Szrj the conditions under which the number of iterations is not zero.
287238fd1498Szrj
287338fd1498Szrj Example of analysis: suppose that the loop has an exit condition:
287438fd1498Szrj
287538fd1498Szrj "if (b > 49) goto end_loop;"
287638fd1498Szrj
287738fd1498Szrj and that in a previous analysis we have determined that the
287838fd1498Szrj variable 'b' has an evolution function:
287938fd1498Szrj
288038fd1498Szrj "EF = {23, +, 5}_2".
288138fd1498Szrj
288238fd1498Szrj When we evaluate the function at the point 5, i.e. the value of the
288338fd1498Szrj variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
288438fd1498Szrj and EF (6) = 53. In this case the value of 'b' on exit is '53' and
288538fd1498Szrj the loop body has been executed 6 times. */
288638fd1498Szrj
288738fd1498Szrj tree
number_of_latch_executions(struct loop * loop)288838fd1498Szrj number_of_latch_executions (struct loop *loop)
288938fd1498Szrj {
289038fd1498Szrj edge exit;
289138fd1498Szrj struct tree_niter_desc niter_desc;
289238fd1498Szrj tree may_be_zero;
289338fd1498Szrj tree res;
289438fd1498Szrj
289538fd1498Szrj /* Determine whether the number of iterations in loop has already
289638fd1498Szrj been computed. */
289738fd1498Szrj res = loop->nb_iterations;
289838fd1498Szrj if (res)
289938fd1498Szrj return res;
290038fd1498Szrj
290138fd1498Szrj may_be_zero = NULL_TREE;
290238fd1498Szrj
290338fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
290438fd1498Szrj fprintf (dump_file, "(number_of_iterations_in_loop = \n");
290538fd1498Szrj
290638fd1498Szrj res = chrec_dont_know;
290738fd1498Szrj exit = single_exit (loop);
290838fd1498Szrj
290938fd1498Szrj if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
291038fd1498Szrj {
291138fd1498Szrj may_be_zero = niter_desc.may_be_zero;
291238fd1498Szrj res = niter_desc.niter;
291338fd1498Szrj }
291438fd1498Szrj
291538fd1498Szrj if (res == chrec_dont_know
291638fd1498Szrj || !may_be_zero
291738fd1498Szrj || integer_zerop (may_be_zero))
291838fd1498Szrj ;
291938fd1498Szrj else if (integer_nonzerop (may_be_zero))
292038fd1498Szrj res = build_int_cst (TREE_TYPE (res), 0);
292138fd1498Szrj
292238fd1498Szrj else if (COMPARISON_CLASS_P (may_be_zero))
292338fd1498Szrj res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
292438fd1498Szrj build_int_cst (TREE_TYPE (res), 0), res);
292538fd1498Szrj else
292638fd1498Szrj res = chrec_dont_know;
292738fd1498Szrj
292838fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
292938fd1498Szrj {
293038fd1498Szrj fprintf (dump_file, " (set_nb_iterations_in_loop = ");
293138fd1498Szrj print_generic_expr (dump_file, res);
293238fd1498Szrj fprintf (dump_file, "))\n");
293338fd1498Szrj }
293438fd1498Szrj
293538fd1498Szrj loop->nb_iterations = res;
293638fd1498Szrj return res;
293738fd1498Szrj }
293838fd1498Szrj
293938fd1498Szrj
294038fd1498Szrj /* Counters for the stats. */
294138fd1498Szrj
294238fd1498Szrj struct chrec_stats
294338fd1498Szrj {
294438fd1498Szrj unsigned nb_chrecs;
294538fd1498Szrj unsigned nb_affine;
294638fd1498Szrj unsigned nb_affine_multivar;
294738fd1498Szrj unsigned nb_higher_poly;
294838fd1498Szrj unsigned nb_chrec_dont_know;
294938fd1498Szrj unsigned nb_undetermined;
295038fd1498Szrj };
295138fd1498Szrj
295238fd1498Szrj /* Reset the counters. */
295338fd1498Szrj
295438fd1498Szrj static inline void
reset_chrecs_counters(struct chrec_stats * stats)295538fd1498Szrj reset_chrecs_counters (struct chrec_stats *stats)
295638fd1498Szrj {
295738fd1498Szrj stats->nb_chrecs = 0;
295838fd1498Szrj stats->nb_affine = 0;
295938fd1498Szrj stats->nb_affine_multivar = 0;
296038fd1498Szrj stats->nb_higher_poly = 0;
296138fd1498Szrj stats->nb_chrec_dont_know = 0;
296238fd1498Szrj stats->nb_undetermined = 0;
296338fd1498Szrj }
296438fd1498Szrj
296538fd1498Szrj /* Dump the contents of a CHREC_STATS structure. */
296638fd1498Szrj
296738fd1498Szrj static void
dump_chrecs_stats(FILE * file,struct chrec_stats * stats)296838fd1498Szrj dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
296938fd1498Szrj {
297038fd1498Szrj fprintf (file, "\n(\n");
297138fd1498Szrj fprintf (file, "-----------------------------------------\n");
297238fd1498Szrj fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
297338fd1498Szrj fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
297438fd1498Szrj fprintf (file, "%d\tdegree greater than 2 polynomials\n",
297538fd1498Szrj stats->nb_higher_poly);
297638fd1498Szrj fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
297738fd1498Szrj fprintf (file, "-----------------------------------------\n");
297838fd1498Szrj fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
297938fd1498Szrj fprintf (file, "%d\twith undetermined coefficients\n",
298038fd1498Szrj stats->nb_undetermined);
298138fd1498Szrj fprintf (file, "-----------------------------------------\n");
298238fd1498Szrj fprintf (file, "%d\tchrecs in the scev database\n",
298338fd1498Szrj (int) scalar_evolution_info->elements ());
298438fd1498Szrj fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
298538fd1498Szrj fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
298638fd1498Szrj fprintf (file, "-----------------------------------------\n");
298738fd1498Szrj fprintf (file, ")\n\n");
298838fd1498Szrj }
298938fd1498Szrj
299038fd1498Szrj /* Gather statistics about CHREC. */
299138fd1498Szrj
299238fd1498Szrj static void
gather_chrec_stats(tree chrec,struct chrec_stats * stats)299338fd1498Szrj gather_chrec_stats (tree chrec, struct chrec_stats *stats)
299438fd1498Szrj {
299538fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
299638fd1498Szrj {
299738fd1498Szrj fprintf (dump_file, "(classify_chrec ");
299838fd1498Szrj print_generic_expr (dump_file, chrec);
299938fd1498Szrj fprintf (dump_file, "\n");
300038fd1498Szrj }
300138fd1498Szrj
300238fd1498Szrj stats->nb_chrecs++;
300338fd1498Szrj
300438fd1498Szrj if (chrec == NULL_TREE)
300538fd1498Szrj {
300638fd1498Szrj stats->nb_undetermined++;
300738fd1498Szrj return;
300838fd1498Szrj }
300938fd1498Szrj
301038fd1498Szrj switch (TREE_CODE (chrec))
301138fd1498Szrj {
301238fd1498Szrj case POLYNOMIAL_CHREC:
301338fd1498Szrj if (evolution_function_is_affine_p (chrec))
301438fd1498Szrj {
301538fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
301638fd1498Szrj fprintf (dump_file, " affine_univariate\n");
301738fd1498Szrj stats->nb_affine++;
301838fd1498Szrj }
301938fd1498Szrj else if (evolution_function_is_affine_multivariate_p (chrec, 0))
302038fd1498Szrj {
302138fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
302238fd1498Szrj fprintf (dump_file, " affine_multivariate\n");
302338fd1498Szrj stats->nb_affine_multivar++;
302438fd1498Szrj }
302538fd1498Szrj else
302638fd1498Szrj {
302738fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
302838fd1498Szrj fprintf (dump_file, " higher_degree_polynomial\n");
302938fd1498Szrj stats->nb_higher_poly++;
303038fd1498Szrj }
303138fd1498Szrj
303238fd1498Szrj break;
303338fd1498Szrj
303438fd1498Szrj default:
303538fd1498Szrj break;
303638fd1498Szrj }
303738fd1498Szrj
303838fd1498Szrj if (chrec_contains_undetermined (chrec))
303938fd1498Szrj {
304038fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
304138fd1498Szrj fprintf (dump_file, " undetermined\n");
304238fd1498Szrj stats->nb_undetermined++;
304338fd1498Szrj }
304438fd1498Szrj
304538fd1498Szrj if (dump_file && (dump_flags & TDF_STATS))
304638fd1498Szrj fprintf (dump_file, ")\n");
304738fd1498Szrj }
304838fd1498Szrj
304938fd1498Szrj /* Classify the chrecs of the whole database. */
305038fd1498Szrj
305138fd1498Szrj void
gather_stats_on_scev_database(void)305238fd1498Szrj gather_stats_on_scev_database (void)
305338fd1498Szrj {
305438fd1498Szrj struct chrec_stats stats;
305538fd1498Szrj
305638fd1498Szrj if (!dump_file)
305738fd1498Szrj return;
305838fd1498Szrj
305938fd1498Szrj reset_chrecs_counters (&stats);
306038fd1498Szrj
306138fd1498Szrj hash_table<scev_info_hasher>::iterator iter;
306238fd1498Szrj scev_info_str *elt;
306338fd1498Szrj FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
306438fd1498Szrj iter)
306538fd1498Szrj gather_chrec_stats (elt->chrec, &stats);
306638fd1498Szrj
306738fd1498Szrj dump_chrecs_stats (dump_file, &stats);
306838fd1498Szrj }
306938fd1498Szrj
307038fd1498Szrj
307138fd1498Szrj
307238fd1498Szrj /* Initializer. */
307338fd1498Szrj
307438fd1498Szrj static void
initialize_scalar_evolutions_analyzer(void)307538fd1498Szrj initialize_scalar_evolutions_analyzer (void)
307638fd1498Szrj {
307738fd1498Szrj /* The elements below are unique. */
307838fd1498Szrj if (chrec_dont_know == NULL_TREE)
307938fd1498Szrj {
308038fd1498Szrj chrec_not_analyzed_yet = NULL_TREE;
308138fd1498Szrj chrec_dont_know = make_node (SCEV_NOT_KNOWN);
308238fd1498Szrj chrec_known = make_node (SCEV_KNOWN);
308338fd1498Szrj TREE_TYPE (chrec_dont_know) = void_type_node;
308438fd1498Szrj TREE_TYPE (chrec_known) = void_type_node;
308538fd1498Szrj }
308638fd1498Szrj }
308738fd1498Szrj
308838fd1498Szrj /* Initialize the analysis of scalar evolutions for LOOPS. */
308938fd1498Szrj
309038fd1498Szrj void
scev_initialize(void)309138fd1498Szrj scev_initialize (void)
309238fd1498Szrj {
309338fd1498Szrj struct loop *loop;
309438fd1498Szrj
309538fd1498Szrj gcc_assert (! scev_initialized_p ());
309638fd1498Szrj
309738fd1498Szrj scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
309838fd1498Szrj
309938fd1498Szrj initialize_scalar_evolutions_analyzer ();
310038fd1498Szrj
310138fd1498Szrj FOR_EACH_LOOP (loop, 0)
310238fd1498Szrj {
310338fd1498Szrj loop->nb_iterations = NULL_TREE;
310438fd1498Szrj }
310538fd1498Szrj }
310638fd1498Szrj
310738fd1498Szrj /* Return true if SCEV is initialized. */
310838fd1498Szrj
310938fd1498Szrj bool
scev_initialized_p(void)311038fd1498Szrj scev_initialized_p (void)
311138fd1498Szrj {
311238fd1498Szrj return scalar_evolution_info != NULL;
311338fd1498Szrj }
311438fd1498Szrj
311538fd1498Szrj /* Cleans up the information cached by the scalar evolutions analysis
311638fd1498Szrj in the hash table. */
311738fd1498Szrj
311838fd1498Szrj void
scev_reset_htab(void)311938fd1498Szrj scev_reset_htab (void)
312038fd1498Szrj {
312138fd1498Szrj if (!scalar_evolution_info)
312238fd1498Szrj return;
312338fd1498Szrj
312438fd1498Szrj scalar_evolution_info->empty ();
312538fd1498Szrj }
312638fd1498Szrj
312738fd1498Szrj /* Cleans up the information cached by the scalar evolutions analysis
312838fd1498Szrj in the hash table and in the loop->nb_iterations. */
312938fd1498Szrj
313038fd1498Szrj void
scev_reset(void)313138fd1498Szrj scev_reset (void)
313238fd1498Szrj {
313338fd1498Szrj struct loop *loop;
313438fd1498Szrj
313538fd1498Szrj scev_reset_htab ();
313638fd1498Szrj
313738fd1498Szrj FOR_EACH_LOOP (loop, 0)
313838fd1498Szrj {
313938fd1498Szrj loop->nb_iterations = NULL_TREE;
314038fd1498Szrj }
314138fd1498Szrj }
314238fd1498Szrj
314338fd1498Szrj /* Return true if the IV calculation in TYPE can overflow based on the knowledge
314438fd1498Szrj of the upper bound on the number of iterations of LOOP, the BASE and STEP
314538fd1498Szrj of IV.
314638fd1498Szrj
314738fd1498Szrj We do not use information whether TYPE can overflow so it is safe to
314838fd1498Szrj use this test even for derived IVs not computed every iteration or
314938fd1498Szrj hypotetical IVs to be inserted into code. */
315038fd1498Szrj
315138fd1498Szrj bool
iv_can_overflow_p(struct loop * loop,tree type,tree base,tree step)315238fd1498Szrj iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
315338fd1498Szrj {
315438fd1498Szrj widest_int nit;
315538fd1498Szrj wide_int base_min, base_max, step_min, step_max, type_min, type_max;
315638fd1498Szrj signop sgn = TYPE_SIGN (type);
315738fd1498Szrj
315838fd1498Szrj if (integer_zerop (step))
315938fd1498Szrj return false;
316038fd1498Szrj
316138fd1498Szrj if (TREE_CODE (base) == INTEGER_CST)
316238fd1498Szrj base_min = base_max = wi::to_wide (base);
316338fd1498Szrj else if (TREE_CODE (base) == SSA_NAME
316438fd1498Szrj && INTEGRAL_TYPE_P (TREE_TYPE (base))
316538fd1498Szrj && get_range_info (base, &base_min, &base_max) == VR_RANGE)
316638fd1498Szrj ;
316738fd1498Szrj else
316838fd1498Szrj return true;
316938fd1498Szrj
317038fd1498Szrj if (TREE_CODE (step) == INTEGER_CST)
317138fd1498Szrj step_min = step_max = wi::to_wide (step);
317238fd1498Szrj else if (TREE_CODE (step) == SSA_NAME
317338fd1498Szrj && INTEGRAL_TYPE_P (TREE_TYPE (step))
317438fd1498Szrj && get_range_info (step, &step_min, &step_max) == VR_RANGE)
317538fd1498Szrj ;
317638fd1498Szrj else
317738fd1498Szrj return true;
317838fd1498Szrj
317938fd1498Szrj if (!get_max_loop_iterations (loop, &nit))
318038fd1498Szrj return true;
318138fd1498Szrj
318238fd1498Szrj type_min = wi::min_value (type);
318338fd1498Szrj type_max = wi::max_value (type);
318438fd1498Szrj
318538fd1498Szrj /* Just sanity check that we don't see values out of the range of the type.
318638fd1498Szrj In this case the arithmetics bellow would overflow. */
318738fd1498Szrj gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
318838fd1498Szrj && wi::le_p (base_max, type_max, sgn));
318938fd1498Szrj
319038fd1498Szrj /* Account the possible increment in the last ieration. */
319138fd1498Szrj bool overflow = false;
319238fd1498Szrj nit = wi::add (nit, 1, SIGNED, &overflow);
319338fd1498Szrj if (overflow)
319438fd1498Szrj return true;
319538fd1498Szrj
319638fd1498Szrj /* NIT is typeless and can exceed the precision of the type. In this case
319738fd1498Szrj overflow is always possible, because we know STEP is non-zero. */
319838fd1498Szrj if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
319938fd1498Szrj return true;
320038fd1498Szrj wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
320138fd1498Szrj
320238fd1498Szrj /* If step can be positive, check that nit*step <= type_max-base.
320338fd1498Szrj This can be done by unsigned arithmetic and we only need to watch overflow
320438fd1498Szrj in the multiplication. The right hand side can always be represented in
320538fd1498Szrj the type. */
320638fd1498Szrj if (sgn == UNSIGNED || !wi::neg_p (step_max))
320738fd1498Szrj {
320838fd1498Szrj bool overflow = false;
320938fd1498Szrj if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
321038fd1498Szrj type_max - base_max)
321138fd1498Szrj || overflow)
321238fd1498Szrj return true;
321338fd1498Szrj }
321438fd1498Szrj /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
321538fd1498Szrj if (sgn == SIGNED && wi::neg_p (step_min))
321638fd1498Szrj {
321738fd1498Szrj bool overflow = false, overflow2 = false;
321838fd1498Szrj if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
321938fd1498Szrj nit2, UNSIGNED, &overflow),
322038fd1498Szrj base_min - type_min)
322138fd1498Szrj || overflow || overflow2)
322238fd1498Szrj return true;
322338fd1498Szrj }
322438fd1498Szrj
322538fd1498Szrj return false;
322638fd1498Szrj }
322738fd1498Szrj
322838fd1498Szrj /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
322938fd1498Szrj function tries to derive condition under which it can be simplified
323038fd1498Szrj into "{(type)inner_base, (type)inner_step}_loop". The condition is
323138fd1498Szrj the maximum number that inner iv can iterate. */
323238fd1498Szrj
323338fd1498Szrj static tree
derive_simple_iv_with_niters(tree ev,tree * niters)323438fd1498Szrj derive_simple_iv_with_niters (tree ev, tree *niters)
323538fd1498Szrj {
323638fd1498Szrj if (!CONVERT_EXPR_P (ev))
323738fd1498Szrj return ev;
323838fd1498Szrj
323938fd1498Szrj tree inner_ev = TREE_OPERAND (ev, 0);
324038fd1498Szrj if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
324138fd1498Szrj return ev;
324238fd1498Szrj
324338fd1498Szrj tree init = CHREC_LEFT (inner_ev);
324438fd1498Szrj tree step = CHREC_RIGHT (inner_ev);
324538fd1498Szrj if (TREE_CODE (init) != INTEGER_CST
324638fd1498Szrj || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
324738fd1498Szrj return ev;
324838fd1498Szrj
324938fd1498Szrj tree type = TREE_TYPE (ev);
325038fd1498Szrj tree inner_type = TREE_TYPE (inner_ev);
325138fd1498Szrj if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
325238fd1498Szrj return ev;
325338fd1498Szrj
325438fd1498Szrj /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
325538fd1498Szrj folded only if inner iv won't overflow. We compute the maximum
325638fd1498Szrj number the inner iv can iterate before overflowing and return the
325738fd1498Szrj simplified affine iv. */
325838fd1498Szrj tree delta;
325938fd1498Szrj init = fold_convert (type, init);
326038fd1498Szrj step = fold_convert (type, step);
326138fd1498Szrj ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
326238fd1498Szrj if (tree_int_cst_sign_bit (step))
326338fd1498Szrj {
326438fd1498Szrj tree bound = lower_bound_in_type (inner_type, inner_type);
326538fd1498Szrj delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
326638fd1498Szrj step = fold_build1 (NEGATE_EXPR, type, step);
326738fd1498Szrj }
326838fd1498Szrj else
326938fd1498Szrj {
327038fd1498Szrj tree bound = upper_bound_in_type (inner_type, inner_type);
327138fd1498Szrj delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
327238fd1498Szrj }
327338fd1498Szrj *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
327438fd1498Szrj return ev;
327538fd1498Szrj }
327638fd1498Szrj
327738fd1498Szrj /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
327838fd1498Szrj respect to WRTO_LOOP and returns its base and step in IV if possible
327938fd1498Szrj (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
328038fd1498Szrj and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
328138fd1498Szrj invariant in LOOP. Otherwise we require it to be an integer constant.
328238fd1498Szrj
328338fd1498Szrj IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
328438fd1498Szrj because it is computed in signed arithmetics). Consequently, adding an
328538fd1498Szrj induction variable
328638fd1498Szrj
328738fd1498Szrj for (i = IV->base; ; i += IV->step)
328838fd1498Szrj
328938fd1498Szrj is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
329038fd1498Szrj false for the type of the induction variable, or you can prove that i does
329138fd1498Szrj not wrap by some other argument. Otherwise, this might introduce undefined
329238fd1498Szrj behavior, and
329338fd1498Szrj
329438fd1498Szrj i = iv->base;
329538fd1498Szrj for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
329638fd1498Szrj
329738fd1498Szrj must be used instead.
329838fd1498Szrj
329938fd1498Szrj When IV_NITERS is not NULL, this function also checks case in which OP
330038fd1498Szrj is a conversion of an inner simple iv of below form:
330138fd1498Szrj
330238fd1498Szrj (outer_type){inner_base, inner_step}_loop.
330338fd1498Szrj
330438fd1498Szrj If type of inner iv has smaller precision than outer_type, it can't be
330538fd1498Szrj folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
330638fd1498Szrj the inner iv could overflow/wrap. In this case, we derive a condition
330738fd1498Szrj under which the inner iv won't overflow/wrap and do the simplification.
330838fd1498Szrj The derived condition normally is the maximum number the inner iv can
330938fd1498Szrj iterate, and will be stored in IV_NITERS. This is useful in loop niter
331038fd1498Szrj analysis, to derive break conditions when a loop must terminate, when is
331138fd1498Szrj infinite. */
331238fd1498Szrj
331338fd1498Szrj bool
simple_iv_with_niters(struct loop * wrto_loop,struct loop * use_loop,tree op,affine_iv * iv,tree * iv_niters,bool allow_nonconstant_step)331438fd1498Szrj simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop,
331538fd1498Szrj tree op, affine_iv *iv, tree *iv_niters,
331638fd1498Szrj bool allow_nonconstant_step)
331738fd1498Szrj {
331838fd1498Szrj enum tree_code code;
331938fd1498Szrj tree type, ev, base, e;
332038fd1498Szrj wide_int extreme;
332138fd1498Szrj bool folded_casts, overflow;
332238fd1498Szrj
332338fd1498Szrj iv->base = NULL_TREE;
332438fd1498Szrj iv->step = NULL_TREE;
332538fd1498Szrj iv->no_overflow = false;
332638fd1498Szrj
332738fd1498Szrj type = TREE_TYPE (op);
332838fd1498Szrj if (!POINTER_TYPE_P (type)
332938fd1498Szrj && !INTEGRAL_TYPE_P (type))
333038fd1498Szrj return false;
333138fd1498Szrj
333238fd1498Szrj ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
333338fd1498Szrj &folded_casts);
333438fd1498Szrj if (chrec_contains_undetermined (ev)
333538fd1498Szrj || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
333638fd1498Szrj return false;
333738fd1498Szrj
333838fd1498Szrj if (tree_does_not_contain_chrecs (ev))
333938fd1498Szrj {
334038fd1498Szrj iv->base = ev;
334138fd1498Szrj iv->step = build_int_cst (TREE_TYPE (ev), 0);
334238fd1498Szrj iv->no_overflow = true;
334338fd1498Szrj return true;
334438fd1498Szrj }
334538fd1498Szrj
334638fd1498Szrj /* If we can derive valid scalar evolution with assumptions. */
334738fd1498Szrj if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
334838fd1498Szrj ev = derive_simple_iv_with_niters (ev, iv_niters);
334938fd1498Szrj
335038fd1498Szrj if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
335138fd1498Szrj return false;
335238fd1498Szrj
335338fd1498Szrj if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
335438fd1498Szrj return false;
335538fd1498Szrj
335638fd1498Szrj iv->step = CHREC_RIGHT (ev);
335738fd1498Szrj if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
335838fd1498Szrj || tree_contains_chrecs (iv->step, NULL))
335938fd1498Szrj return false;
336038fd1498Szrj
336138fd1498Szrj iv->base = CHREC_LEFT (ev);
336238fd1498Szrj if (tree_contains_chrecs (iv->base, NULL))
336338fd1498Szrj return false;
336438fd1498Szrj
336538fd1498Szrj iv->no_overflow = !folded_casts && nowrap_type_p (type);
336638fd1498Szrj
336738fd1498Szrj if (!iv->no_overflow
336838fd1498Szrj && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
336938fd1498Szrj iv->no_overflow = true;
337038fd1498Szrj
337138fd1498Szrj /* Try to simplify iv base:
337238fd1498Szrj
337338fd1498Szrj (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
337438fd1498Szrj == (signed T)(unsigned T)base + step
337538fd1498Szrj == base + step
337638fd1498Szrj
337738fd1498Szrj If we can prove operation (base + step) doesn't overflow or underflow.
337838fd1498Szrj Specifically, we try to prove below conditions are satisfied:
337938fd1498Szrj
338038fd1498Szrj base <= UPPER_BOUND (type) - step ;;step > 0
338138fd1498Szrj base >= LOWER_BOUND (type) - step ;;step < 0
338238fd1498Szrj
338338fd1498Szrj This is done by proving the reverse conditions are false using loop's
338438fd1498Szrj initial conditions.
338538fd1498Szrj
338638fd1498Szrj The is necessary to make loop niter, or iv overflow analysis easier
338738fd1498Szrj for below example:
338838fd1498Szrj
338938fd1498Szrj int foo (int *a, signed char s, signed char l)
339038fd1498Szrj {
339138fd1498Szrj signed char i;
339238fd1498Szrj for (i = s; i < l; i++)
339338fd1498Szrj a[i] = 0;
339438fd1498Szrj return 0;
339538fd1498Szrj }
339638fd1498Szrj
339738fd1498Szrj Note variable I is firstly converted to type unsigned char, incremented,
339838fd1498Szrj then converted back to type signed char. */
339938fd1498Szrj
340038fd1498Szrj if (wrto_loop->num != use_loop->num)
340138fd1498Szrj return true;
340238fd1498Szrj
340338fd1498Szrj if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
340438fd1498Szrj return true;
340538fd1498Szrj
340638fd1498Szrj type = TREE_TYPE (iv->base);
340738fd1498Szrj e = TREE_OPERAND (iv->base, 0);
340838fd1498Szrj if (TREE_CODE (e) != PLUS_EXPR
340938fd1498Szrj || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
341038fd1498Szrj || !tree_int_cst_equal (iv->step,
341138fd1498Szrj fold_convert (type, TREE_OPERAND (e, 1))))
341238fd1498Szrj return true;
341338fd1498Szrj e = TREE_OPERAND (e, 0);
341438fd1498Szrj if (!CONVERT_EXPR_P (e))
341538fd1498Szrj return true;
341638fd1498Szrj base = TREE_OPERAND (e, 0);
341738fd1498Szrj if (!useless_type_conversion_p (type, TREE_TYPE (base)))
341838fd1498Szrj return true;
341938fd1498Szrj
342038fd1498Szrj if (tree_int_cst_sign_bit (iv->step))
342138fd1498Szrj {
342238fd1498Szrj code = LT_EXPR;
342338fd1498Szrj extreme = wi::min_value (type);
342438fd1498Szrj }
342538fd1498Szrj else
342638fd1498Szrj {
342738fd1498Szrj code = GT_EXPR;
342838fd1498Szrj extreme = wi::max_value (type);
342938fd1498Szrj }
343038fd1498Szrj overflow = false;
343138fd1498Szrj extreme = wi::sub (extreme, wi::to_wide (iv->step),
343238fd1498Szrj TYPE_SIGN (type), &overflow);
343338fd1498Szrj if (overflow)
343438fd1498Szrj return true;
343538fd1498Szrj e = fold_build2 (code, boolean_type_node, base,
343638fd1498Szrj wide_int_to_tree (type, extreme));
343738fd1498Szrj e = simplify_using_initial_conditions (use_loop, e);
343838fd1498Szrj if (!integer_zerop (e))
343938fd1498Szrj return true;
344038fd1498Szrj
344138fd1498Szrj if (POINTER_TYPE_P (TREE_TYPE (base)))
344238fd1498Szrj code = POINTER_PLUS_EXPR;
344338fd1498Szrj else
344438fd1498Szrj code = PLUS_EXPR;
344538fd1498Szrj
344638fd1498Szrj iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
344738fd1498Szrj return true;
344838fd1498Szrj }
344938fd1498Szrj
345038fd1498Szrj /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
345138fd1498Szrj affine iv unconditionally. */
345238fd1498Szrj
345338fd1498Szrj bool
simple_iv(struct loop * wrto_loop,struct loop * use_loop,tree op,affine_iv * iv,bool allow_nonconstant_step)345438fd1498Szrj simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
345538fd1498Szrj affine_iv *iv, bool allow_nonconstant_step)
345638fd1498Szrj {
345738fd1498Szrj return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
345838fd1498Szrj NULL, allow_nonconstant_step);
345938fd1498Szrj }
346038fd1498Szrj
346138fd1498Szrj /* Finalize the scalar evolution analysis. */
346238fd1498Szrj
346338fd1498Szrj void
scev_finalize(void)346438fd1498Szrj scev_finalize (void)
346538fd1498Szrj {
346638fd1498Szrj if (!scalar_evolution_info)
346738fd1498Szrj return;
346838fd1498Szrj scalar_evolution_info->empty ();
346938fd1498Szrj scalar_evolution_info = NULL;
347038fd1498Szrj free_numbers_of_iterations_estimates (cfun);
347138fd1498Szrj }
347238fd1498Szrj
347338fd1498Szrj /* Returns true if the expression EXPR is considered to be too expensive
347438fd1498Szrj for scev_const_prop. */
347538fd1498Szrj
347638fd1498Szrj bool
expression_expensive_p(tree expr)347738fd1498Szrj expression_expensive_p (tree expr)
347838fd1498Szrj {
347938fd1498Szrj enum tree_code code;
348038fd1498Szrj
348138fd1498Szrj if (is_gimple_val (expr))
348238fd1498Szrj return false;
348338fd1498Szrj
348438fd1498Szrj code = TREE_CODE (expr);
348538fd1498Szrj if (code == TRUNC_DIV_EXPR
348638fd1498Szrj || code == CEIL_DIV_EXPR
348738fd1498Szrj || code == FLOOR_DIV_EXPR
348838fd1498Szrj || code == ROUND_DIV_EXPR
348938fd1498Szrj || code == TRUNC_MOD_EXPR
349038fd1498Szrj || code == CEIL_MOD_EXPR
349138fd1498Szrj || code == FLOOR_MOD_EXPR
349238fd1498Szrj || code == ROUND_MOD_EXPR
349338fd1498Szrj || code == EXACT_DIV_EXPR)
349438fd1498Szrj {
349538fd1498Szrj /* Division by power of two is usually cheap, so we allow it.
349638fd1498Szrj Forbid anything else. */
349738fd1498Szrj if (!integer_pow2p (TREE_OPERAND (expr, 1)))
349838fd1498Szrj return true;
349938fd1498Szrj }
350038fd1498Szrj
350138fd1498Szrj switch (TREE_CODE_CLASS (code))
350238fd1498Szrj {
350338fd1498Szrj case tcc_binary:
350438fd1498Szrj case tcc_comparison:
350538fd1498Szrj if (expression_expensive_p (TREE_OPERAND (expr, 1)))
350638fd1498Szrj return true;
350738fd1498Szrj
350838fd1498Szrj /* Fallthru. */
350938fd1498Szrj case tcc_unary:
351038fd1498Szrj return expression_expensive_p (TREE_OPERAND (expr, 0));
351138fd1498Szrj
351238fd1498Szrj default:
351338fd1498Szrj return true;
351438fd1498Szrj }
351538fd1498Szrj }
351638fd1498Szrj
351738fd1498Szrj /* Do final value replacement for LOOP. */
351838fd1498Szrj
351938fd1498Szrj void
final_value_replacement_loop(struct loop * loop)352038fd1498Szrj final_value_replacement_loop (struct loop *loop)
352138fd1498Szrj {
352238fd1498Szrj /* If we do not know exact number of iterations of the loop, we cannot
352338fd1498Szrj replace the final value. */
352438fd1498Szrj edge exit = single_exit (loop);
352538fd1498Szrj if (!exit)
352638fd1498Szrj return;
352738fd1498Szrj
352838fd1498Szrj tree niter = number_of_latch_executions (loop);
352938fd1498Szrj if (niter == chrec_dont_know)
353038fd1498Szrj return;
353138fd1498Szrj
353238fd1498Szrj /* Ensure that it is possible to insert new statements somewhere. */
353338fd1498Szrj if (!single_pred_p (exit->dest))
353438fd1498Szrj split_loop_exit_edge (exit);
353538fd1498Szrj
353638fd1498Szrj /* Set stmt insertion pointer. All stmts are inserted before this point. */
353738fd1498Szrj gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
353838fd1498Szrj
353938fd1498Szrj struct loop *ex_loop
354038fd1498Szrj = superloop_at_depth (loop,
354138fd1498Szrj loop_depth (exit->dest->loop_father) + 1);
354238fd1498Szrj
354338fd1498Szrj gphi_iterator psi;
354438fd1498Szrj for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
354538fd1498Szrj {
354638fd1498Szrj gphi *phi = psi.phi ();
354738fd1498Szrj tree rslt = PHI_RESULT (phi);
354838fd1498Szrj tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
354938fd1498Szrj if (virtual_operand_p (def))
355038fd1498Szrj {
355138fd1498Szrj gsi_next (&psi);
355238fd1498Szrj continue;
355338fd1498Szrj }
355438fd1498Szrj
355538fd1498Szrj if (!POINTER_TYPE_P (TREE_TYPE (def))
355638fd1498Szrj && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
355738fd1498Szrj {
355838fd1498Szrj gsi_next (&psi);
355938fd1498Szrj continue;
356038fd1498Szrj }
356138fd1498Szrj
356238fd1498Szrj bool folded_casts;
356338fd1498Szrj def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
356438fd1498Szrj &folded_casts);
356538fd1498Szrj def = compute_overall_effect_of_inner_loop (ex_loop, def);
356638fd1498Szrj if (!tree_does_not_contain_chrecs (def)
356738fd1498Szrj || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
356838fd1498Szrj /* Moving the computation from the loop may prolong life range
356938fd1498Szrj of some ssa names, which may cause problems if they appear
357038fd1498Szrj on abnormal edges. */
357138fd1498Szrj || contains_abnormal_ssa_name_p (def)
357238fd1498Szrj /* Do not emit expensive expressions. The rationale is that
357338fd1498Szrj when someone writes a code like
357438fd1498Szrj
357538fd1498Szrj while (n > 45) n -= 45;
357638fd1498Szrj
357738fd1498Szrj he probably knows that n is not large, and does not want it
357838fd1498Szrj to be turned into n %= 45. */
357938fd1498Szrj || expression_expensive_p (def))
358038fd1498Szrj {
358138fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
358238fd1498Szrj {
358338fd1498Szrj fprintf (dump_file, "not replacing:\n ");
358438fd1498Szrj print_gimple_stmt (dump_file, phi, 0);
358538fd1498Szrj fprintf (dump_file, "\n");
358638fd1498Szrj }
358738fd1498Szrj gsi_next (&psi);
358838fd1498Szrj continue;
358938fd1498Szrj }
359038fd1498Szrj
359138fd1498Szrj /* Eliminate the PHI node and replace it by a computation outside
359238fd1498Szrj the loop. */
359338fd1498Szrj if (dump_file)
359438fd1498Szrj {
359538fd1498Szrj fprintf (dump_file, "\nfinal value replacement:\n ");
359638fd1498Szrj print_gimple_stmt (dump_file, phi, 0);
359738fd1498Szrj fprintf (dump_file, " with\n ");
359838fd1498Szrj }
359938fd1498Szrj def = unshare_expr (def);
360038fd1498Szrj remove_phi_node (&psi, false);
360138fd1498Szrj
360238fd1498Szrj /* If def's type has undefined overflow and there were folded
360338fd1498Szrj casts, rewrite all stmts added for def into arithmetics
360438fd1498Szrj with defined overflow behavior. */
360538fd1498Szrj if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
360638fd1498Szrj && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
360738fd1498Szrj {
360838fd1498Szrj gimple_seq stmts;
360938fd1498Szrj gimple_stmt_iterator gsi2;
361038fd1498Szrj def = force_gimple_operand (def, &stmts, true, NULL_TREE);
361138fd1498Szrj gsi2 = gsi_start (stmts);
361238fd1498Szrj while (!gsi_end_p (gsi2))
361338fd1498Szrj {
361438fd1498Szrj gimple *stmt = gsi_stmt (gsi2);
361538fd1498Szrj gimple_stmt_iterator gsi3 = gsi2;
361638fd1498Szrj gsi_next (&gsi2);
361738fd1498Szrj gsi_remove (&gsi3, false);
361838fd1498Szrj if (is_gimple_assign (stmt)
361938fd1498Szrj && arith_code_with_undefined_signed_overflow
362038fd1498Szrj (gimple_assign_rhs_code (stmt)))
362138fd1498Szrj gsi_insert_seq_before (&gsi,
362238fd1498Szrj rewrite_to_defined_overflow (stmt),
362338fd1498Szrj GSI_SAME_STMT);
362438fd1498Szrj else
362538fd1498Szrj gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
362638fd1498Szrj }
362738fd1498Szrj }
362838fd1498Szrj else
362938fd1498Szrj def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
363038fd1498Szrj true, GSI_SAME_STMT);
363138fd1498Szrj
363238fd1498Szrj gassign *ass = gimple_build_assign (rslt, def);
363338fd1498Szrj gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
363438fd1498Szrj if (dump_file)
363538fd1498Szrj {
363638fd1498Szrj print_gimple_stmt (dump_file, ass, 0);
363738fd1498Szrj fprintf (dump_file, "\n");
363838fd1498Szrj }
363938fd1498Szrj }
364038fd1498Szrj }
364138fd1498Szrj
364238fd1498Szrj /* Replace ssa names for that scev can prove they are constant by the
364338fd1498Szrj appropriate constants. Also perform final value replacement in loops,
364438fd1498Szrj in case the replacement expressions are cheap.
364538fd1498Szrj
364638fd1498Szrj We only consider SSA names defined by phi nodes; rest is left to the
364738fd1498Szrj ordinary constant propagation pass. */
364838fd1498Szrj
364938fd1498Szrj unsigned int
scev_const_prop(void)365038fd1498Szrj scev_const_prop (void)
365138fd1498Szrj {
365238fd1498Szrj basic_block bb;
365338fd1498Szrj tree name, type, ev;
365438fd1498Szrj gphi *phi;
365538fd1498Szrj struct loop *loop;
365638fd1498Szrj bitmap ssa_names_to_remove = NULL;
365738fd1498Szrj unsigned i;
365838fd1498Szrj gphi_iterator psi;
365938fd1498Szrj
366038fd1498Szrj if (number_of_loops (cfun) <= 1)
366138fd1498Szrj return 0;
366238fd1498Szrj
366338fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
366438fd1498Szrj {
366538fd1498Szrj loop = bb->loop_father;
366638fd1498Szrj
366738fd1498Szrj for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
366838fd1498Szrj {
366938fd1498Szrj phi = psi.phi ();
367038fd1498Szrj name = PHI_RESULT (phi);
367138fd1498Szrj
367238fd1498Szrj if (virtual_operand_p (name))
367338fd1498Szrj continue;
367438fd1498Szrj
367538fd1498Szrj type = TREE_TYPE (name);
367638fd1498Szrj
367738fd1498Szrj if (!POINTER_TYPE_P (type)
367838fd1498Szrj && !INTEGRAL_TYPE_P (type))
367938fd1498Szrj continue;
368038fd1498Szrj
368138fd1498Szrj ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
368238fd1498Szrj NULL);
368338fd1498Szrj if (!is_gimple_min_invariant (ev)
368438fd1498Szrj || !may_propagate_copy (name, ev))
368538fd1498Szrj continue;
368638fd1498Szrj
368738fd1498Szrj /* Replace the uses of the name. */
368838fd1498Szrj if (name != ev)
368938fd1498Szrj {
369038fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
369138fd1498Szrj {
369238fd1498Szrj fprintf (dump_file, "Replacing uses of: ");
369338fd1498Szrj print_generic_expr (dump_file, name);
369438fd1498Szrj fprintf (dump_file, " with: ");
369538fd1498Szrj print_generic_expr (dump_file, ev);
369638fd1498Szrj fprintf (dump_file, "\n");
369738fd1498Szrj }
369838fd1498Szrj replace_uses_by (name, ev);
369938fd1498Szrj }
370038fd1498Szrj
370138fd1498Szrj if (!ssa_names_to_remove)
370238fd1498Szrj ssa_names_to_remove = BITMAP_ALLOC (NULL);
370338fd1498Szrj bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
370438fd1498Szrj }
370538fd1498Szrj }
370638fd1498Szrj
370738fd1498Szrj /* Remove the ssa names that were replaced by constants. We do not
370838fd1498Szrj remove them directly in the previous cycle, since this
370938fd1498Szrj invalidates scev cache. */
371038fd1498Szrj if (ssa_names_to_remove)
371138fd1498Szrj {
371238fd1498Szrj bitmap_iterator bi;
371338fd1498Szrj
371438fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
371538fd1498Szrj {
371638fd1498Szrj gimple_stmt_iterator psi;
371738fd1498Szrj name = ssa_name (i);
371838fd1498Szrj phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
371938fd1498Szrj
372038fd1498Szrj gcc_assert (gimple_code (phi) == GIMPLE_PHI);
372138fd1498Szrj psi = gsi_for_stmt (phi);
372238fd1498Szrj remove_phi_node (&psi, true);
372338fd1498Szrj }
372438fd1498Szrj
372538fd1498Szrj BITMAP_FREE (ssa_names_to_remove);
372638fd1498Szrj scev_reset ();
372738fd1498Szrj }
372838fd1498Szrj
372938fd1498Szrj /* Now the regular final value replacement. */
373038fd1498Szrj FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
373138fd1498Szrj final_value_replacement_loop (loop);
373238fd1498Szrj
373338fd1498Szrj return 0;
373438fd1498Szrj }
373538fd1498Szrj
373638fd1498Szrj #include "gt-tree-scalar-evolution.h"
3737