1*e4b17023SJohn Marino /* Scalar evolution detector.
2*e4b17023SJohn Marino Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3*e4b17023SJohn Marino Free Software Foundation, Inc.
4*e4b17023SJohn Marino Contributed by Sebastian Pop <s.pop@laposte.net>
5*e4b17023SJohn Marino
6*e4b17023SJohn Marino This file is part of GCC.
7*e4b17023SJohn Marino
8*e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify it under
9*e4b17023SJohn Marino the terms of the GNU General Public License as published by the Free
10*e4b17023SJohn Marino Software Foundation; either version 3, or (at your option) any later
11*e4b17023SJohn Marino version.
12*e4b17023SJohn Marino
13*e4b17023SJohn Marino GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14*e4b17023SJohn Marino WARRANTY; without even the implied warranty of MERCHANTABILITY or
15*e4b17023SJohn Marino FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16*e4b17023SJohn Marino for more details.
17*e4b17023SJohn Marino
18*e4b17023SJohn Marino You should have received a copy of the GNU General Public License
19*e4b17023SJohn Marino along with GCC; see the file COPYING3. If not see
20*e4b17023SJohn Marino <http://www.gnu.org/licenses/>. */
21*e4b17023SJohn Marino
22*e4b17023SJohn Marino /*
23*e4b17023SJohn Marino Description:
24*e4b17023SJohn Marino
25*e4b17023SJohn Marino This pass analyzes the evolution of scalar variables in loop
26*e4b17023SJohn Marino structures. The algorithm is based on the SSA representation,
27*e4b17023SJohn Marino and on the loop hierarchy tree. This algorithm is not based on
28*e4b17023SJohn Marino the notion of versions of a variable, as it was the case for the
29*e4b17023SJohn Marino previous implementations of the scalar evolution algorithm, but
30*e4b17023SJohn Marino it assumes that each defined name is unique.
31*e4b17023SJohn Marino
32*e4b17023SJohn Marino The notation used in this file is called "chains of recurrences",
33*e4b17023SJohn Marino and has been proposed by Eugene Zima, Robert Van Engelen, and
34*e4b17023SJohn Marino others for describing induction variables in programs. For example
35*e4b17023SJohn Marino "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36*e4b17023SJohn Marino when entering in the loop_1 and has a step 2 in this loop, in other
37*e4b17023SJohn Marino words "for (b = 0; b < N; b+=2);". Note that the coefficients of
38*e4b17023SJohn Marino this chain of recurrence (or chrec [shrek]) can contain the name of
39*e4b17023SJohn Marino other variables, in which case they are called parametric chrecs.
40*e4b17023SJohn Marino For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41*e4b17023SJohn Marino is the value of "a". In most of the cases these parametric chrecs
42*e4b17023SJohn Marino are fully instantiated before their use because symbolic names can
43*e4b17023SJohn Marino hide some difficult cases such as self-references described later
44*e4b17023SJohn Marino (see the Fibonacci example).
45*e4b17023SJohn Marino
46*e4b17023SJohn Marino A short sketch of the algorithm is:
47*e4b17023SJohn Marino
48*e4b17023SJohn Marino Given a scalar variable to be analyzed, follow the SSA edge to
49*e4b17023SJohn Marino its definition:
50*e4b17023SJohn Marino
51*e4b17023SJohn Marino - When the definition is a GIMPLE_ASSIGN: if the right hand side
52*e4b17023SJohn Marino (RHS) of the definition cannot be statically analyzed, the answer
53*e4b17023SJohn Marino of the analyzer is: "don't know".
54*e4b17023SJohn Marino Otherwise, for all the variables that are not yet analyzed in the
55*e4b17023SJohn Marino RHS, try to determine their evolution, and finally try to
56*e4b17023SJohn Marino evaluate the operation of the RHS that gives the evolution
57*e4b17023SJohn Marino function of the analyzed variable.
58*e4b17023SJohn Marino
59*e4b17023SJohn Marino - When the definition is a condition-phi-node: determine the
60*e4b17023SJohn Marino evolution function for all the branches of the phi node, and
61*e4b17023SJohn Marino finally merge these evolutions (see chrec_merge).
62*e4b17023SJohn Marino
63*e4b17023SJohn Marino - When the definition is a loop-phi-node: determine its initial
64*e4b17023SJohn Marino condition, that is the SSA edge defined in an outer loop, and
65*e4b17023SJohn Marino keep it symbolic. Then determine the SSA edges that are defined
66*e4b17023SJohn Marino in the body of the loop. Follow the inner edges until ending on
67*e4b17023SJohn Marino another loop-phi-node of the same analyzed loop. If the reached
68*e4b17023SJohn Marino loop-phi-node is not the starting loop-phi-node, then we keep
69*e4b17023SJohn Marino this definition under a symbolic form. If the reached
70*e4b17023SJohn Marino loop-phi-node is the same as the starting one, then we compute a
71*e4b17023SJohn Marino symbolic stride on the return path. The result is then the
72*e4b17023SJohn Marino symbolic chrec {initial_condition, +, symbolic_stride}_loop.
73*e4b17023SJohn Marino
74*e4b17023SJohn Marino Examples:
75*e4b17023SJohn Marino
76*e4b17023SJohn Marino Example 1: Illustration of the basic algorithm.
77*e4b17023SJohn Marino
78*e4b17023SJohn Marino | a = 3
79*e4b17023SJohn Marino | loop_1
80*e4b17023SJohn Marino | b = phi (a, c)
81*e4b17023SJohn Marino | c = b + 1
82*e4b17023SJohn Marino | if (c > 10) exit_loop
83*e4b17023SJohn Marino | endloop
84*e4b17023SJohn Marino
85*e4b17023SJohn Marino Suppose that we want to know the number of iterations of the
86*e4b17023SJohn Marino loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
87*e4b17023SJohn Marino ask the scalar evolution analyzer two questions: what's the
88*e4b17023SJohn Marino scalar evolution (scev) of "c", and what's the scev of "10". For
89*e4b17023SJohn Marino "10" the answer is "10" since it is a scalar constant. For the
90*e4b17023SJohn Marino scalar variable "c", it follows the SSA edge to its definition,
91*e4b17023SJohn Marino "c = b + 1", and then asks again what's the scev of "b".
92*e4b17023SJohn Marino Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93*e4b17023SJohn Marino c)", where the initial condition is "a", and the inner loop edge
94*e4b17023SJohn Marino is "c". The initial condition is kept under a symbolic form (it
95*e4b17023SJohn Marino may be the case that the copy constant propagation has done its
96*e4b17023SJohn Marino work and we end with the constant "3" as one of the edges of the
97*e4b17023SJohn Marino loop-phi-node). The update edge is followed to the end of the
98*e4b17023SJohn Marino loop, and until reaching again the starting loop-phi-node: b -> c
99*e4b17023SJohn Marino -> b. At this point we have drawn a path from "b" to "b" from
100*e4b17023SJohn Marino which we compute the stride in the loop: in this example it is
101*e4b17023SJohn Marino "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
102*e4b17023SJohn Marino that the scev for "b" is known, it is possible to compute the
103*e4b17023SJohn Marino scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
104*e4b17023SJohn Marino determine the number of iterations in the loop_1, we have to
105*e4b17023SJohn Marino instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
106*e4b17023SJohn Marino more analysis the scev {4, +, 1}_1, or in other words, this is
107*e4b17023SJohn Marino the function "f (x) = x + 4", where x is the iteration count of
108*e4b17023SJohn Marino the loop_1. Now we have to solve the inequality "x + 4 > 10",
109*e4b17023SJohn Marino and take the smallest iteration number for which the loop is
110*e4b17023SJohn Marino exited: x = 7. This loop runs from x = 0 to x = 7, and in total
111*e4b17023SJohn Marino there are 8 iterations. In terms of loop normalization, we have
112*e4b17023SJohn Marino created a variable that is implicitly defined, "x" or just "_1",
113*e4b17023SJohn Marino and all the other analyzed scalars of the loop are defined in
114*e4b17023SJohn Marino function of this variable:
115*e4b17023SJohn Marino
116*e4b17023SJohn Marino a -> 3
117*e4b17023SJohn Marino b -> {3, +, 1}_1
118*e4b17023SJohn Marino c -> {4, +, 1}_1
119*e4b17023SJohn Marino
120*e4b17023SJohn Marino or in terms of a C program:
121*e4b17023SJohn Marino
122*e4b17023SJohn Marino | a = 3
123*e4b17023SJohn Marino | for (x = 0; x <= 7; x++)
124*e4b17023SJohn Marino | {
125*e4b17023SJohn Marino | b = x + 3
126*e4b17023SJohn Marino | c = x + 4
127*e4b17023SJohn Marino | }
128*e4b17023SJohn Marino
129*e4b17023SJohn Marino Example 2a: Illustration of the algorithm on nested loops.
130*e4b17023SJohn Marino
131*e4b17023SJohn Marino | loop_1
132*e4b17023SJohn Marino | a = phi (1, b)
133*e4b17023SJohn Marino | c = a + 2
134*e4b17023SJohn Marino | loop_2 10 times
135*e4b17023SJohn Marino | b = phi (c, d)
136*e4b17023SJohn Marino | d = b + 3
137*e4b17023SJohn Marino | endloop
138*e4b17023SJohn Marino | endloop
139*e4b17023SJohn Marino
140*e4b17023SJohn Marino For analyzing the scalar evolution of "a", the algorithm follows
141*e4b17023SJohn Marino the SSA edge into the loop's body: "a -> b". "b" is an inner
142*e4b17023SJohn Marino loop-phi-node, and its analysis as in Example 1, gives:
143*e4b17023SJohn Marino
144*e4b17023SJohn Marino b -> {c, +, 3}_2
145*e4b17023SJohn Marino d -> {c + 3, +, 3}_2
146*e4b17023SJohn Marino
147*e4b17023SJohn Marino Following the SSA edge for the initial condition, we end on "c = a
148*e4b17023SJohn Marino + 2", and then on the starting loop-phi-node "a". From this point,
149*e4b17023SJohn Marino the loop stride is computed: back on "c = a + 2" we get a "+2" in
150*e4b17023SJohn Marino the loop_1, then on the loop-phi-node "b" we compute the overall
151*e4b17023SJohn Marino effect of the inner loop that is "b = c + 30", and we get a "+30"
152*e4b17023SJohn Marino in the loop_1. That means that the overall stride in loop_1 is
153*e4b17023SJohn Marino equal to "+32", and the result is:
154*e4b17023SJohn Marino
155*e4b17023SJohn Marino a -> {1, +, 32}_1
156*e4b17023SJohn Marino c -> {3, +, 32}_1
157*e4b17023SJohn Marino
158*e4b17023SJohn Marino Example 2b: Multivariate chains of recurrences.
159*e4b17023SJohn Marino
160*e4b17023SJohn Marino | loop_1
161*e4b17023SJohn Marino | k = phi (0, k + 1)
162*e4b17023SJohn Marino | loop_2 4 times
163*e4b17023SJohn Marino | j = phi (0, j + 1)
164*e4b17023SJohn Marino | loop_3 4 times
165*e4b17023SJohn Marino | i = phi (0, i + 1)
166*e4b17023SJohn Marino | A[j + k] = ...
167*e4b17023SJohn Marino | endloop
168*e4b17023SJohn Marino | endloop
169*e4b17023SJohn Marino | endloop
170*e4b17023SJohn Marino
171*e4b17023SJohn Marino Analyzing the access function of array A with
172*e4b17023SJohn Marino instantiate_parameters (loop_1, "j + k"), we obtain the
173*e4b17023SJohn Marino instantiation and the analysis of the scalar variables "j" and "k"
174*e4b17023SJohn Marino in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
175*e4b17023SJohn Marino value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
176*e4b17023SJohn Marino {0, +, 1}_1. To obtain the evolution function in loop_3 and
177*e4b17023SJohn Marino instantiate the scalar variables up to loop_1, one has to use:
178*e4b17023SJohn Marino instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
179*e4b17023SJohn Marino The result of this call is {{0, +, 1}_1, +, 1}_2.
180*e4b17023SJohn Marino
181*e4b17023SJohn Marino Example 3: Higher degree polynomials.
182*e4b17023SJohn Marino
183*e4b17023SJohn Marino | loop_1
184*e4b17023SJohn Marino | a = phi (2, b)
185*e4b17023SJohn Marino | c = phi (5, d)
186*e4b17023SJohn Marino | b = a + 1
187*e4b17023SJohn Marino | d = c + a
188*e4b17023SJohn Marino | endloop
189*e4b17023SJohn Marino
190*e4b17023SJohn Marino a -> {2, +, 1}_1
191*e4b17023SJohn Marino b -> {3, +, 1}_1
192*e4b17023SJohn Marino c -> {5, +, a}_1
193*e4b17023SJohn Marino d -> {5 + a, +, a}_1
194*e4b17023SJohn Marino
195*e4b17023SJohn Marino instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
196*e4b17023SJohn Marino instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197*e4b17023SJohn Marino
198*e4b17023SJohn Marino Example 4: Lucas, Fibonacci, or mixers in general.
199*e4b17023SJohn Marino
200*e4b17023SJohn Marino | loop_1
201*e4b17023SJohn Marino | a = phi (1, b)
202*e4b17023SJohn Marino | c = phi (3, d)
203*e4b17023SJohn Marino | b = c
204*e4b17023SJohn Marino | d = c + a
205*e4b17023SJohn Marino | endloop
206*e4b17023SJohn Marino
207*e4b17023SJohn Marino a -> (1, c)_1
208*e4b17023SJohn Marino c -> {3, +, a}_1
209*e4b17023SJohn Marino
210*e4b17023SJohn Marino The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
211*e4b17023SJohn Marino following semantics: during the first iteration of the loop_1, the
212*e4b17023SJohn Marino variable contains the value 1, and then it contains the value "c".
213*e4b17023SJohn Marino Note that this syntax is close to the syntax of the loop-phi-node:
214*e4b17023SJohn Marino "a -> (1, c)_1" vs. "a = phi (1, c)".
215*e4b17023SJohn Marino
216*e4b17023SJohn Marino The symbolic chrec representation contains all the semantics of the
217*e4b17023SJohn Marino original code. What is more difficult is to use this information.
218*e4b17023SJohn Marino
219*e4b17023SJohn Marino Example 5: Flip-flops, or exchangers.
220*e4b17023SJohn Marino
221*e4b17023SJohn Marino | loop_1
222*e4b17023SJohn Marino | a = phi (1, b)
223*e4b17023SJohn Marino | c = phi (3, d)
224*e4b17023SJohn Marino | b = c
225*e4b17023SJohn Marino | d = a
226*e4b17023SJohn Marino | endloop
227*e4b17023SJohn Marino
228*e4b17023SJohn Marino a -> (1, c)_1
229*e4b17023SJohn Marino c -> (3, a)_1
230*e4b17023SJohn Marino
231*e4b17023SJohn Marino Based on these symbolic chrecs, it is possible to refine this
232*e4b17023SJohn Marino information into the more precise PERIODIC_CHRECs:
233*e4b17023SJohn Marino
234*e4b17023SJohn Marino a -> |1, 3|_1
235*e4b17023SJohn Marino c -> |3, 1|_1
236*e4b17023SJohn Marino
237*e4b17023SJohn Marino This transformation is not yet implemented.
238*e4b17023SJohn Marino
239*e4b17023SJohn Marino Further readings:
240*e4b17023SJohn Marino
241*e4b17023SJohn Marino You can find a more detailed description of the algorithm in:
242*e4b17023SJohn Marino http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
243*e4b17023SJohn Marino http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
244*e4b17023SJohn Marino this is a preliminary report and some of the details of the
245*e4b17023SJohn Marino algorithm have changed. I'm working on a research report that
246*e4b17023SJohn Marino updates the description of the algorithms to reflect the design
247*e4b17023SJohn Marino choices used in this implementation.
248*e4b17023SJohn Marino
249*e4b17023SJohn Marino A set of slides show a high level overview of the algorithm and run
250*e4b17023SJohn Marino an example through the scalar evolution analyzer:
251*e4b17023SJohn Marino http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252*e4b17023SJohn Marino
253*e4b17023SJohn Marino The slides that I have presented at the GCC Summit'04 are available
254*e4b17023SJohn Marino at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
255*e4b17023SJohn Marino */
256*e4b17023SJohn Marino
257*e4b17023SJohn Marino #include "config.h"
258*e4b17023SJohn Marino #include "system.h"
259*e4b17023SJohn Marino #include "coretypes.h"
260*e4b17023SJohn Marino #include "gimple-pretty-print.h"
261*e4b17023SJohn Marino #include "tree-flow.h"
262*e4b17023SJohn Marino #include "cfgloop.h"
263*e4b17023SJohn Marino #include "tree-chrec.h"
264*e4b17023SJohn Marino #include "tree-scalar-evolution.h"
265*e4b17023SJohn Marino #include "tree-pass.h"
266*e4b17023SJohn Marino #include "params.h"
267*e4b17023SJohn Marino
268*e4b17023SJohn Marino static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
269*e4b17023SJohn Marino
270*e4b17023SJohn Marino /* The cached information about an SSA name VAR, claiming that below
271*e4b17023SJohn Marino basic block INSTANTIATED_BELOW, the value of VAR can be expressed
272*e4b17023SJohn Marino as CHREC. */
273*e4b17023SJohn Marino
274*e4b17023SJohn Marino struct GTY(()) scev_info_str {
275*e4b17023SJohn Marino basic_block instantiated_below;
276*e4b17023SJohn Marino tree var;
277*e4b17023SJohn Marino tree chrec;
278*e4b17023SJohn Marino };
279*e4b17023SJohn Marino
280*e4b17023SJohn Marino /* Counters for the scev database. */
281*e4b17023SJohn Marino static unsigned nb_set_scev = 0;
282*e4b17023SJohn Marino static unsigned nb_get_scev = 0;
283*e4b17023SJohn Marino
284*e4b17023SJohn Marino /* The following trees are unique elements. Thus the comparison of
285*e4b17023SJohn Marino another element to these elements should be done on the pointer to
286*e4b17023SJohn Marino these trees, and not on their value. */
287*e4b17023SJohn Marino
288*e4b17023SJohn Marino /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
289*e4b17023SJohn Marino tree chrec_not_analyzed_yet;
290*e4b17023SJohn Marino
291*e4b17023SJohn Marino /* Reserved to the cases where the analyzer has detected an
292*e4b17023SJohn Marino undecidable property at compile time. */
293*e4b17023SJohn Marino tree chrec_dont_know;
294*e4b17023SJohn Marino
295*e4b17023SJohn Marino /* When the analyzer has detected that a property will never
296*e4b17023SJohn Marino happen, then it qualifies it with chrec_known. */
297*e4b17023SJohn Marino tree chrec_known;
298*e4b17023SJohn Marino
299*e4b17023SJohn Marino static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
300*e4b17023SJohn Marino
301*e4b17023SJohn Marino
302*e4b17023SJohn Marino /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
303*e4b17023SJohn Marino
304*e4b17023SJohn Marino static inline struct scev_info_str *
new_scev_info_str(basic_block instantiated_below,tree var)305*e4b17023SJohn Marino new_scev_info_str (basic_block instantiated_below, tree var)
306*e4b17023SJohn Marino {
307*e4b17023SJohn Marino struct scev_info_str *res;
308*e4b17023SJohn Marino
309*e4b17023SJohn Marino res = ggc_alloc_scev_info_str ();
310*e4b17023SJohn Marino res->var = var;
311*e4b17023SJohn Marino res->chrec = chrec_not_analyzed_yet;
312*e4b17023SJohn Marino res->instantiated_below = instantiated_below;
313*e4b17023SJohn Marino
314*e4b17023SJohn Marino return res;
315*e4b17023SJohn Marino }
316*e4b17023SJohn Marino
317*e4b17023SJohn Marino /* Computes a hash function for database element ELT. */
318*e4b17023SJohn Marino
319*e4b17023SJohn Marino static hashval_t
hash_scev_info(const void * elt)320*e4b17023SJohn Marino hash_scev_info (const void *elt)
321*e4b17023SJohn Marino {
322*e4b17023SJohn Marino return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
323*e4b17023SJohn Marino }
324*e4b17023SJohn Marino
325*e4b17023SJohn Marino /* Compares database elements E1 and E2. */
326*e4b17023SJohn Marino
327*e4b17023SJohn Marino static int
eq_scev_info(const void * e1,const void * e2)328*e4b17023SJohn Marino eq_scev_info (const void *e1, const void *e2)
329*e4b17023SJohn Marino {
330*e4b17023SJohn Marino const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
331*e4b17023SJohn Marino const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
332*e4b17023SJohn Marino
333*e4b17023SJohn Marino return (elt1->var == elt2->var
334*e4b17023SJohn Marino && elt1->instantiated_below == elt2->instantiated_below);
335*e4b17023SJohn Marino }
336*e4b17023SJohn Marino
337*e4b17023SJohn Marino /* Deletes database element E. */
338*e4b17023SJohn Marino
339*e4b17023SJohn Marino static void
del_scev_info(void * e)340*e4b17023SJohn Marino del_scev_info (void *e)
341*e4b17023SJohn Marino {
342*e4b17023SJohn Marino ggc_free (e);
343*e4b17023SJohn Marino }
344*e4b17023SJohn Marino
345*e4b17023SJohn Marino /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
346*e4b17023SJohn Marino A first query on VAR returns chrec_not_analyzed_yet. */
347*e4b17023SJohn Marino
348*e4b17023SJohn Marino static tree *
find_var_scev_info(basic_block instantiated_below,tree var)349*e4b17023SJohn Marino find_var_scev_info (basic_block instantiated_below, tree var)
350*e4b17023SJohn Marino {
351*e4b17023SJohn Marino struct scev_info_str *res;
352*e4b17023SJohn Marino struct scev_info_str tmp;
353*e4b17023SJohn Marino PTR *slot;
354*e4b17023SJohn Marino
355*e4b17023SJohn Marino tmp.var = var;
356*e4b17023SJohn Marino tmp.instantiated_below = instantiated_below;
357*e4b17023SJohn Marino slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
358*e4b17023SJohn Marino
359*e4b17023SJohn Marino if (!*slot)
360*e4b17023SJohn Marino *slot = new_scev_info_str (instantiated_below, var);
361*e4b17023SJohn Marino res = (struct scev_info_str *) *slot;
362*e4b17023SJohn Marino
363*e4b17023SJohn Marino return &res->chrec;
364*e4b17023SJohn Marino }
365*e4b17023SJohn Marino
366*e4b17023SJohn Marino /* Return true when CHREC contains symbolic names defined in
367*e4b17023SJohn Marino LOOP_NB. */
368*e4b17023SJohn Marino
369*e4b17023SJohn Marino bool
chrec_contains_symbols_defined_in_loop(const_tree chrec,unsigned loop_nb)370*e4b17023SJohn Marino chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
371*e4b17023SJohn Marino {
372*e4b17023SJohn Marino int i, n;
373*e4b17023SJohn Marino
374*e4b17023SJohn Marino if (chrec == NULL_TREE)
375*e4b17023SJohn Marino return false;
376*e4b17023SJohn Marino
377*e4b17023SJohn Marino if (is_gimple_min_invariant (chrec))
378*e4b17023SJohn Marino return false;
379*e4b17023SJohn Marino
380*e4b17023SJohn Marino if (TREE_CODE (chrec) == SSA_NAME)
381*e4b17023SJohn Marino {
382*e4b17023SJohn Marino gimple def;
383*e4b17023SJohn Marino loop_p def_loop, loop;
384*e4b17023SJohn Marino
385*e4b17023SJohn Marino if (SSA_NAME_IS_DEFAULT_DEF (chrec))
386*e4b17023SJohn Marino return false;
387*e4b17023SJohn Marino
388*e4b17023SJohn Marino def = SSA_NAME_DEF_STMT (chrec);
389*e4b17023SJohn Marino def_loop = loop_containing_stmt (def);
390*e4b17023SJohn Marino loop = get_loop (loop_nb);
391*e4b17023SJohn Marino
392*e4b17023SJohn Marino if (def_loop == NULL)
393*e4b17023SJohn Marino return false;
394*e4b17023SJohn Marino
395*e4b17023SJohn Marino if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
396*e4b17023SJohn Marino return true;
397*e4b17023SJohn Marino
398*e4b17023SJohn Marino return false;
399*e4b17023SJohn Marino }
400*e4b17023SJohn Marino
401*e4b17023SJohn Marino n = TREE_OPERAND_LENGTH (chrec);
402*e4b17023SJohn Marino for (i = 0; i < n; i++)
403*e4b17023SJohn Marino if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
404*e4b17023SJohn Marino loop_nb))
405*e4b17023SJohn Marino return true;
406*e4b17023SJohn Marino return false;
407*e4b17023SJohn Marino }
408*e4b17023SJohn Marino
409*e4b17023SJohn Marino /* Return true when PHI is a loop-phi-node. */
410*e4b17023SJohn Marino
411*e4b17023SJohn Marino static bool
loop_phi_node_p(gimple phi)412*e4b17023SJohn Marino loop_phi_node_p (gimple phi)
413*e4b17023SJohn Marino {
414*e4b17023SJohn Marino /* The implementation of this function is based on the following
415*e4b17023SJohn Marino property: "all the loop-phi-nodes of a loop are contained in the
416*e4b17023SJohn Marino loop's header basic block". */
417*e4b17023SJohn Marino
418*e4b17023SJohn Marino return loop_containing_stmt (phi)->header == gimple_bb (phi);
419*e4b17023SJohn Marino }
420*e4b17023SJohn Marino
421*e4b17023SJohn Marino /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
422*e4b17023SJohn Marino In general, in the case of multivariate evolutions we want to get
423*e4b17023SJohn Marino the evolution in different loops. LOOP specifies the level for
424*e4b17023SJohn Marino which to get the evolution.
425*e4b17023SJohn Marino
426*e4b17023SJohn Marino Example:
427*e4b17023SJohn Marino
428*e4b17023SJohn Marino | for (j = 0; j < 100; j++)
429*e4b17023SJohn Marino | {
430*e4b17023SJohn Marino | for (k = 0; k < 100; k++)
431*e4b17023SJohn Marino | {
432*e4b17023SJohn Marino | i = k + j; - Here the value of i is a function of j, k.
433*e4b17023SJohn Marino | }
434*e4b17023SJohn Marino | ... = i - Here the value of i is a function of j.
435*e4b17023SJohn Marino | }
436*e4b17023SJohn Marino | ... = i - Here the value of i is a scalar.
437*e4b17023SJohn Marino
438*e4b17023SJohn Marino Example:
439*e4b17023SJohn Marino
440*e4b17023SJohn Marino | i_0 = ...
441*e4b17023SJohn Marino | loop_1 10 times
442*e4b17023SJohn Marino | i_1 = phi (i_0, i_2)
443*e4b17023SJohn Marino | i_2 = i_1 + 2
444*e4b17023SJohn Marino | endloop
445*e4b17023SJohn Marino
446*e4b17023SJohn Marino This loop has the same effect as:
447*e4b17023SJohn Marino LOOP_1 has the same effect as:
448*e4b17023SJohn Marino
449*e4b17023SJohn Marino | i_1 = i_0 + 20
450*e4b17023SJohn Marino
451*e4b17023SJohn Marino The overall effect of the loop, "i_0 + 20" in the previous example,
452*e4b17023SJohn Marino is obtained by passing in the parameters: LOOP = 1,
453*e4b17023SJohn Marino EVOLUTION_FN = {i_0, +, 2}_1.
454*e4b17023SJohn Marino */
455*e4b17023SJohn Marino
456*e4b17023SJohn Marino tree
compute_overall_effect_of_inner_loop(struct loop * loop,tree evolution_fn)457*e4b17023SJohn Marino compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
458*e4b17023SJohn Marino {
459*e4b17023SJohn Marino bool val = false;
460*e4b17023SJohn Marino
461*e4b17023SJohn Marino if (evolution_fn == chrec_dont_know)
462*e4b17023SJohn Marino return chrec_dont_know;
463*e4b17023SJohn Marino
464*e4b17023SJohn Marino else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
465*e4b17023SJohn Marino {
466*e4b17023SJohn Marino struct loop *inner_loop = get_chrec_loop (evolution_fn);
467*e4b17023SJohn Marino
468*e4b17023SJohn Marino if (inner_loop == loop
469*e4b17023SJohn Marino || flow_loop_nested_p (loop, inner_loop))
470*e4b17023SJohn Marino {
471*e4b17023SJohn Marino tree nb_iter = number_of_latch_executions (inner_loop);
472*e4b17023SJohn Marino
473*e4b17023SJohn Marino if (nb_iter == chrec_dont_know)
474*e4b17023SJohn Marino return chrec_dont_know;
475*e4b17023SJohn Marino else
476*e4b17023SJohn Marino {
477*e4b17023SJohn Marino tree res;
478*e4b17023SJohn Marino
479*e4b17023SJohn Marino /* evolution_fn is the evolution function in LOOP. Get
480*e4b17023SJohn Marino its value in the nb_iter-th iteration. */
481*e4b17023SJohn Marino res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
482*e4b17023SJohn Marino
483*e4b17023SJohn Marino if (chrec_contains_symbols_defined_in_loop (res, loop->num))
484*e4b17023SJohn Marino res = instantiate_parameters (loop, res);
485*e4b17023SJohn Marino
486*e4b17023SJohn Marino /* Continue the computation until ending on a parent of LOOP. */
487*e4b17023SJohn Marino return compute_overall_effect_of_inner_loop (loop, res);
488*e4b17023SJohn Marino }
489*e4b17023SJohn Marino }
490*e4b17023SJohn Marino else
491*e4b17023SJohn Marino return evolution_fn;
492*e4b17023SJohn Marino }
493*e4b17023SJohn Marino
494*e4b17023SJohn Marino /* If the evolution function is an invariant, there is nothing to do. */
495*e4b17023SJohn Marino else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
496*e4b17023SJohn Marino return evolution_fn;
497*e4b17023SJohn Marino
498*e4b17023SJohn Marino else
499*e4b17023SJohn Marino return chrec_dont_know;
500*e4b17023SJohn Marino }
501*e4b17023SJohn Marino
502*e4b17023SJohn Marino /* Associate CHREC to SCALAR. */
503*e4b17023SJohn Marino
504*e4b17023SJohn Marino static void
set_scalar_evolution(basic_block instantiated_below,tree scalar,tree chrec)505*e4b17023SJohn Marino set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
506*e4b17023SJohn Marino {
507*e4b17023SJohn Marino tree *scalar_info;
508*e4b17023SJohn Marino
509*e4b17023SJohn Marino if (TREE_CODE (scalar) != SSA_NAME)
510*e4b17023SJohn Marino return;
511*e4b17023SJohn Marino
512*e4b17023SJohn Marino scalar_info = find_var_scev_info (instantiated_below, scalar);
513*e4b17023SJohn Marino
514*e4b17023SJohn Marino if (dump_file)
515*e4b17023SJohn Marino {
516*e4b17023SJohn Marino if (dump_flags & TDF_SCEV)
517*e4b17023SJohn Marino {
518*e4b17023SJohn Marino fprintf (dump_file, "(set_scalar_evolution \n");
519*e4b17023SJohn Marino fprintf (dump_file, " instantiated_below = %d \n",
520*e4b17023SJohn Marino instantiated_below->index);
521*e4b17023SJohn Marino fprintf (dump_file, " (scalar = ");
522*e4b17023SJohn Marino print_generic_expr (dump_file, scalar, 0);
523*e4b17023SJohn Marino fprintf (dump_file, ")\n (scalar_evolution = ");
524*e4b17023SJohn Marino print_generic_expr (dump_file, chrec, 0);
525*e4b17023SJohn Marino fprintf (dump_file, "))\n");
526*e4b17023SJohn Marino }
527*e4b17023SJohn Marino if (dump_flags & TDF_STATS)
528*e4b17023SJohn Marino nb_set_scev++;
529*e4b17023SJohn Marino }
530*e4b17023SJohn Marino
531*e4b17023SJohn Marino *scalar_info = chrec;
532*e4b17023SJohn Marino }
533*e4b17023SJohn Marino
534*e4b17023SJohn Marino /* Retrieve the chrec associated to SCALAR instantiated below
535*e4b17023SJohn Marino INSTANTIATED_BELOW block. */
536*e4b17023SJohn Marino
537*e4b17023SJohn Marino static tree
get_scalar_evolution(basic_block instantiated_below,tree scalar)538*e4b17023SJohn Marino get_scalar_evolution (basic_block instantiated_below, tree scalar)
539*e4b17023SJohn Marino {
540*e4b17023SJohn Marino tree res;
541*e4b17023SJohn Marino
542*e4b17023SJohn Marino if (dump_file)
543*e4b17023SJohn Marino {
544*e4b17023SJohn Marino if (dump_flags & TDF_SCEV)
545*e4b17023SJohn Marino {
546*e4b17023SJohn Marino fprintf (dump_file, "(get_scalar_evolution \n");
547*e4b17023SJohn Marino fprintf (dump_file, " (scalar = ");
548*e4b17023SJohn Marino print_generic_expr (dump_file, scalar, 0);
549*e4b17023SJohn Marino fprintf (dump_file, ")\n");
550*e4b17023SJohn Marino }
551*e4b17023SJohn Marino if (dump_flags & TDF_STATS)
552*e4b17023SJohn Marino nb_get_scev++;
553*e4b17023SJohn Marino }
554*e4b17023SJohn Marino
555*e4b17023SJohn Marino switch (TREE_CODE (scalar))
556*e4b17023SJohn Marino {
557*e4b17023SJohn Marino case SSA_NAME:
558*e4b17023SJohn Marino res = *find_var_scev_info (instantiated_below, scalar);
559*e4b17023SJohn Marino break;
560*e4b17023SJohn Marino
561*e4b17023SJohn Marino case REAL_CST:
562*e4b17023SJohn Marino case FIXED_CST:
563*e4b17023SJohn Marino case INTEGER_CST:
564*e4b17023SJohn Marino res = scalar;
565*e4b17023SJohn Marino break;
566*e4b17023SJohn Marino
567*e4b17023SJohn Marino default:
568*e4b17023SJohn Marino res = chrec_not_analyzed_yet;
569*e4b17023SJohn Marino break;
570*e4b17023SJohn Marino }
571*e4b17023SJohn Marino
572*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
573*e4b17023SJohn Marino {
574*e4b17023SJohn Marino fprintf (dump_file, " (scalar_evolution = ");
575*e4b17023SJohn Marino print_generic_expr (dump_file, res, 0);
576*e4b17023SJohn Marino fprintf (dump_file, "))\n");
577*e4b17023SJohn Marino }
578*e4b17023SJohn Marino
579*e4b17023SJohn Marino return res;
580*e4b17023SJohn Marino }
581*e4b17023SJohn Marino
582*e4b17023SJohn Marino /* Helper function for add_to_evolution. Returns the evolution
583*e4b17023SJohn Marino function for an assignment of the form "a = b + c", where "a" and
584*e4b17023SJohn Marino "b" are on the strongly connected component. CHREC_BEFORE is the
585*e4b17023SJohn Marino information that we already have collected up to this point.
586*e4b17023SJohn Marino TO_ADD is the evolution of "c".
587*e4b17023SJohn Marino
588*e4b17023SJohn Marino When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
589*e4b17023SJohn Marino evolution the expression TO_ADD, otherwise construct an evolution
590*e4b17023SJohn Marino part for this loop. */
591*e4b17023SJohn Marino
592*e4b17023SJohn Marino static tree
add_to_evolution_1(unsigned loop_nb,tree chrec_before,tree to_add,gimple at_stmt)593*e4b17023SJohn Marino add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
594*e4b17023SJohn Marino gimple at_stmt)
595*e4b17023SJohn Marino {
596*e4b17023SJohn Marino tree type, left, right;
597*e4b17023SJohn Marino struct loop *loop = get_loop (loop_nb), *chloop;
598*e4b17023SJohn Marino
599*e4b17023SJohn Marino switch (TREE_CODE (chrec_before))
600*e4b17023SJohn Marino {
601*e4b17023SJohn Marino case POLYNOMIAL_CHREC:
602*e4b17023SJohn Marino chloop = get_chrec_loop (chrec_before);
603*e4b17023SJohn Marino if (chloop == loop
604*e4b17023SJohn Marino || flow_loop_nested_p (chloop, loop))
605*e4b17023SJohn Marino {
606*e4b17023SJohn Marino unsigned var;
607*e4b17023SJohn Marino
608*e4b17023SJohn Marino type = chrec_type (chrec_before);
609*e4b17023SJohn Marino
610*e4b17023SJohn Marino /* When there is no evolution part in this loop, build it. */
611*e4b17023SJohn Marino if (chloop != loop)
612*e4b17023SJohn Marino {
613*e4b17023SJohn Marino var = loop_nb;
614*e4b17023SJohn Marino left = chrec_before;
615*e4b17023SJohn Marino right = SCALAR_FLOAT_TYPE_P (type)
616*e4b17023SJohn Marino ? build_real (type, dconst0)
617*e4b17023SJohn Marino : build_int_cst (type, 0);
618*e4b17023SJohn Marino }
619*e4b17023SJohn Marino else
620*e4b17023SJohn Marino {
621*e4b17023SJohn Marino var = CHREC_VARIABLE (chrec_before);
622*e4b17023SJohn Marino left = CHREC_LEFT (chrec_before);
623*e4b17023SJohn Marino right = CHREC_RIGHT (chrec_before);
624*e4b17023SJohn Marino }
625*e4b17023SJohn Marino
626*e4b17023SJohn Marino to_add = chrec_convert (type, to_add, at_stmt);
627*e4b17023SJohn Marino right = chrec_convert_rhs (type, right, at_stmt);
628*e4b17023SJohn Marino right = chrec_fold_plus (chrec_type (right), right, to_add);
629*e4b17023SJohn Marino return build_polynomial_chrec (var, left, right);
630*e4b17023SJohn Marino }
631*e4b17023SJohn Marino else
632*e4b17023SJohn Marino {
633*e4b17023SJohn Marino gcc_assert (flow_loop_nested_p (loop, chloop));
634*e4b17023SJohn Marino
635*e4b17023SJohn Marino /* Search the evolution in LOOP_NB. */
636*e4b17023SJohn Marino left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
637*e4b17023SJohn Marino to_add, at_stmt);
638*e4b17023SJohn Marino right = CHREC_RIGHT (chrec_before);
639*e4b17023SJohn Marino right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
640*e4b17023SJohn Marino return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
641*e4b17023SJohn Marino left, right);
642*e4b17023SJohn Marino }
643*e4b17023SJohn Marino
644*e4b17023SJohn Marino default:
645*e4b17023SJohn Marino /* These nodes do not depend on a loop. */
646*e4b17023SJohn Marino if (chrec_before == chrec_dont_know)
647*e4b17023SJohn Marino return chrec_dont_know;
648*e4b17023SJohn Marino
649*e4b17023SJohn Marino left = chrec_before;
650*e4b17023SJohn Marino right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
651*e4b17023SJohn Marino return build_polynomial_chrec (loop_nb, left, right);
652*e4b17023SJohn Marino }
653*e4b17023SJohn Marino }
654*e4b17023SJohn Marino
655*e4b17023SJohn Marino /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
656*e4b17023SJohn Marino of LOOP_NB.
657*e4b17023SJohn Marino
658*e4b17023SJohn Marino Description (provided for completeness, for those who read code in
659*e4b17023SJohn Marino a plane, and for my poor 62 bytes brain that would have forgotten
660*e4b17023SJohn Marino all this in the next two or three months):
661*e4b17023SJohn Marino
662*e4b17023SJohn Marino The algorithm of translation of programs from the SSA representation
663*e4b17023SJohn Marino into the chrecs syntax is based on a pattern matching. After having
664*e4b17023SJohn Marino reconstructed the overall tree expression for a loop, there are only
665*e4b17023SJohn Marino two cases that can arise:
666*e4b17023SJohn Marino
667*e4b17023SJohn Marino 1. a = loop-phi (init, a + expr)
668*e4b17023SJohn Marino 2. a = loop-phi (init, expr)
669*e4b17023SJohn Marino
670*e4b17023SJohn Marino where EXPR is either a scalar constant with respect to the analyzed
671*e4b17023SJohn Marino loop (this is a degree 0 polynomial), or an expression containing
672*e4b17023SJohn Marino other loop-phi definitions (these are higher degree polynomials).
673*e4b17023SJohn Marino
674*e4b17023SJohn Marino Examples:
675*e4b17023SJohn Marino
676*e4b17023SJohn Marino 1.
677*e4b17023SJohn Marino | init = ...
678*e4b17023SJohn Marino | loop_1
679*e4b17023SJohn Marino | a = phi (init, a + 5)
680*e4b17023SJohn Marino | endloop
681*e4b17023SJohn Marino
682*e4b17023SJohn Marino 2.
683*e4b17023SJohn Marino | inita = ...
684*e4b17023SJohn Marino | initb = ...
685*e4b17023SJohn Marino | loop_1
686*e4b17023SJohn Marino | a = phi (inita, 2 * b + 3)
687*e4b17023SJohn Marino | b = phi (initb, b + 1)
688*e4b17023SJohn Marino | endloop
689*e4b17023SJohn Marino
690*e4b17023SJohn Marino For the first case, the semantics of the SSA representation is:
691*e4b17023SJohn Marino
692*e4b17023SJohn Marino | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
693*e4b17023SJohn Marino
694*e4b17023SJohn Marino that is, there is a loop index "x" that determines the scalar value
695*e4b17023SJohn Marino of the variable during the loop execution. During the first
696*e4b17023SJohn Marino iteration, the value is that of the initial condition INIT, while
697*e4b17023SJohn Marino during the subsequent iterations, it is the sum of the initial
698*e4b17023SJohn Marino condition with the sum of all the values of EXPR from the initial
699*e4b17023SJohn Marino iteration to the before last considered iteration.
700*e4b17023SJohn Marino
701*e4b17023SJohn Marino For the second case, the semantics of the SSA program is:
702*e4b17023SJohn Marino
703*e4b17023SJohn Marino | a (x) = init, if x = 0;
704*e4b17023SJohn Marino | expr (x - 1), otherwise.
705*e4b17023SJohn Marino
706*e4b17023SJohn Marino The second case corresponds to the PEELED_CHREC, whose syntax is
707*e4b17023SJohn Marino close to the syntax of a loop-phi-node:
708*e4b17023SJohn Marino
709*e4b17023SJohn Marino | phi (init, expr) vs. (init, expr)_x
710*e4b17023SJohn Marino
711*e4b17023SJohn Marino The proof of the translation algorithm for the first case is a
712*e4b17023SJohn Marino proof by structural induction based on the degree of EXPR.
713*e4b17023SJohn Marino
714*e4b17023SJohn Marino Degree 0:
715*e4b17023SJohn Marino When EXPR is a constant with respect to the analyzed loop, or in
716*e4b17023SJohn Marino other words when EXPR is a polynomial of degree 0, the evolution of
717*e4b17023SJohn Marino the variable A in the loop is an affine function with an initial
718*e4b17023SJohn Marino condition INIT, and a step EXPR. In order to show this, we start
719*e4b17023SJohn Marino from the semantics of the SSA representation:
720*e4b17023SJohn Marino
721*e4b17023SJohn Marino f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
722*e4b17023SJohn Marino
723*e4b17023SJohn Marino and since "expr (j)" is a constant with respect to "j",
724*e4b17023SJohn Marino
725*e4b17023SJohn Marino f (x) = init + x * expr
726*e4b17023SJohn Marino
727*e4b17023SJohn Marino Finally, based on the semantics of the pure sum chrecs, by
728*e4b17023SJohn Marino identification we get the corresponding chrecs syntax:
729*e4b17023SJohn Marino
730*e4b17023SJohn Marino f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
731*e4b17023SJohn Marino f (x) -> {init, +, expr}_x
732*e4b17023SJohn Marino
733*e4b17023SJohn Marino Higher degree:
734*e4b17023SJohn Marino Suppose that EXPR is a polynomial of degree N with respect to the
735*e4b17023SJohn Marino analyzed loop_x for which we have already determined that it is
736*e4b17023SJohn Marino written under the chrecs syntax:
737*e4b17023SJohn Marino
738*e4b17023SJohn Marino | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
739*e4b17023SJohn Marino
740*e4b17023SJohn Marino We start from the semantics of the SSA program:
741*e4b17023SJohn Marino
742*e4b17023SJohn Marino | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
743*e4b17023SJohn Marino |
744*e4b17023SJohn Marino | f (x) = init + \sum_{j = 0}^{x - 1}
745*e4b17023SJohn Marino | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
746*e4b17023SJohn Marino |
747*e4b17023SJohn Marino | f (x) = init + \sum_{j = 0}^{x - 1}
748*e4b17023SJohn Marino | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
749*e4b17023SJohn Marino |
750*e4b17023SJohn Marino | f (x) = init + \sum_{k = 0}^{n - 1}
751*e4b17023SJohn Marino | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
752*e4b17023SJohn Marino |
753*e4b17023SJohn Marino | f (x) = init + \sum_{k = 0}^{n - 1}
754*e4b17023SJohn Marino | (b_k * \binom{x}{k + 1})
755*e4b17023SJohn Marino |
756*e4b17023SJohn Marino | f (x) = init + b_0 * \binom{x}{1} + ...
757*e4b17023SJohn Marino | + b_{n-1} * \binom{x}{n}
758*e4b17023SJohn Marino |
759*e4b17023SJohn Marino | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
760*e4b17023SJohn Marino | + b_{n-1} * \binom{x}{n}
761*e4b17023SJohn Marino |
762*e4b17023SJohn Marino
763*e4b17023SJohn Marino And finally from the definition of the chrecs syntax, we identify:
764*e4b17023SJohn Marino | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
765*e4b17023SJohn Marino
766*e4b17023SJohn Marino This shows the mechanism that stands behind the add_to_evolution
767*e4b17023SJohn Marino function. An important point is that the use of symbolic
768*e4b17023SJohn Marino parameters avoids the need of an analysis schedule.
769*e4b17023SJohn Marino
770*e4b17023SJohn Marino Example:
771*e4b17023SJohn Marino
772*e4b17023SJohn Marino | inita = ...
773*e4b17023SJohn Marino | initb = ...
774*e4b17023SJohn Marino | loop_1
775*e4b17023SJohn Marino | a = phi (inita, a + 2 + b)
776*e4b17023SJohn Marino | b = phi (initb, b + 1)
777*e4b17023SJohn Marino | endloop
778*e4b17023SJohn Marino
779*e4b17023SJohn Marino When analyzing "a", the algorithm keeps "b" symbolically:
780*e4b17023SJohn Marino
781*e4b17023SJohn Marino | a -> {inita, +, 2 + b}_1
782*e4b17023SJohn Marino
783*e4b17023SJohn Marino Then, after instantiation, the analyzer ends on the evolution:
784*e4b17023SJohn Marino
785*e4b17023SJohn Marino | a -> {inita, +, 2 + initb, +, 1}_1
786*e4b17023SJohn Marino
787*e4b17023SJohn Marino */
788*e4b17023SJohn Marino
789*e4b17023SJohn Marino static tree
add_to_evolution(unsigned loop_nb,tree chrec_before,enum tree_code code,tree to_add,gimple at_stmt)790*e4b17023SJohn Marino add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
791*e4b17023SJohn Marino tree to_add, gimple at_stmt)
792*e4b17023SJohn Marino {
793*e4b17023SJohn Marino tree type = chrec_type (to_add);
794*e4b17023SJohn Marino tree res = NULL_TREE;
795*e4b17023SJohn Marino
796*e4b17023SJohn Marino if (to_add == NULL_TREE)
797*e4b17023SJohn Marino return chrec_before;
798*e4b17023SJohn Marino
799*e4b17023SJohn Marino /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
800*e4b17023SJohn Marino instantiated at this point. */
801*e4b17023SJohn Marino if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
802*e4b17023SJohn Marino /* This should not happen. */
803*e4b17023SJohn Marino return chrec_dont_know;
804*e4b17023SJohn Marino
805*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
806*e4b17023SJohn Marino {
807*e4b17023SJohn Marino fprintf (dump_file, "(add_to_evolution \n");
808*e4b17023SJohn Marino fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
809*e4b17023SJohn Marino fprintf (dump_file, " (chrec_before = ");
810*e4b17023SJohn Marino print_generic_expr (dump_file, chrec_before, 0);
811*e4b17023SJohn Marino fprintf (dump_file, ")\n (to_add = ");
812*e4b17023SJohn Marino print_generic_expr (dump_file, to_add, 0);
813*e4b17023SJohn Marino fprintf (dump_file, ")\n");
814*e4b17023SJohn Marino }
815*e4b17023SJohn Marino
816*e4b17023SJohn Marino if (code == MINUS_EXPR)
817*e4b17023SJohn Marino to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
818*e4b17023SJohn Marino ? build_real (type, dconstm1)
819*e4b17023SJohn Marino : build_int_cst_type (type, -1));
820*e4b17023SJohn Marino
821*e4b17023SJohn Marino res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
822*e4b17023SJohn Marino
823*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
824*e4b17023SJohn Marino {
825*e4b17023SJohn Marino fprintf (dump_file, " (res = ");
826*e4b17023SJohn Marino print_generic_expr (dump_file, res, 0);
827*e4b17023SJohn Marino fprintf (dump_file, "))\n");
828*e4b17023SJohn Marino }
829*e4b17023SJohn Marino
830*e4b17023SJohn Marino return res;
831*e4b17023SJohn Marino }
832*e4b17023SJohn Marino
833*e4b17023SJohn Marino
834*e4b17023SJohn Marino
835*e4b17023SJohn Marino /* This section selects the loops that will be good candidates for the
836*e4b17023SJohn Marino scalar evolution analysis. For the moment, greedily select all the
837*e4b17023SJohn Marino loop nests we could analyze. */
838*e4b17023SJohn Marino
839*e4b17023SJohn Marino /* For a loop with a single exit edge, return the COND_EXPR that
840*e4b17023SJohn Marino guards the exit edge. If the expression is too difficult to
841*e4b17023SJohn Marino analyze, then give up. */
842*e4b17023SJohn Marino
843*e4b17023SJohn Marino gimple
get_loop_exit_condition(const struct loop * loop)844*e4b17023SJohn Marino get_loop_exit_condition (const struct loop *loop)
845*e4b17023SJohn Marino {
846*e4b17023SJohn Marino gimple res = NULL;
847*e4b17023SJohn Marino edge exit_edge = single_exit (loop);
848*e4b17023SJohn Marino
849*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
850*e4b17023SJohn Marino fprintf (dump_file, "(get_loop_exit_condition \n ");
851*e4b17023SJohn Marino
852*e4b17023SJohn Marino if (exit_edge)
853*e4b17023SJohn Marino {
854*e4b17023SJohn Marino gimple stmt;
855*e4b17023SJohn Marino
856*e4b17023SJohn Marino stmt = last_stmt (exit_edge->src);
857*e4b17023SJohn Marino if (gimple_code (stmt) == GIMPLE_COND)
858*e4b17023SJohn Marino res = stmt;
859*e4b17023SJohn Marino }
860*e4b17023SJohn Marino
861*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
862*e4b17023SJohn Marino {
863*e4b17023SJohn Marino print_gimple_stmt (dump_file, res, 0, 0);
864*e4b17023SJohn Marino fprintf (dump_file, ")\n");
865*e4b17023SJohn Marino }
866*e4b17023SJohn Marino
867*e4b17023SJohn Marino return res;
868*e4b17023SJohn Marino }
869*e4b17023SJohn Marino
870*e4b17023SJohn Marino /* Recursively determine and enqueue the exit conditions for a loop. */
871*e4b17023SJohn Marino
872*e4b17023SJohn Marino static void
get_exit_conditions_rec(struct loop * loop,VEC (gimple,heap)** exit_conditions)873*e4b17023SJohn Marino get_exit_conditions_rec (struct loop *loop,
874*e4b17023SJohn Marino VEC(gimple,heap) **exit_conditions)
875*e4b17023SJohn Marino {
876*e4b17023SJohn Marino if (!loop)
877*e4b17023SJohn Marino return;
878*e4b17023SJohn Marino
879*e4b17023SJohn Marino /* Recurse on the inner loops, then on the next (sibling) loops. */
880*e4b17023SJohn Marino get_exit_conditions_rec (loop->inner, exit_conditions);
881*e4b17023SJohn Marino get_exit_conditions_rec (loop->next, exit_conditions);
882*e4b17023SJohn Marino
883*e4b17023SJohn Marino if (single_exit (loop))
884*e4b17023SJohn Marino {
885*e4b17023SJohn Marino gimple loop_condition = get_loop_exit_condition (loop);
886*e4b17023SJohn Marino
887*e4b17023SJohn Marino if (loop_condition)
888*e4b17023SJohn Marino VEC_safe_push (gimple, heap, *exit_conditions, loop_condition);
889*e4b17023SJohn Marino }
890*e4b17023SJohn Marino }
891*e4b17023SJohn Marino
892*e4b17023SJohn Marino /* Select the candidate loop nests for the analysis. This function
893*e4b17023SJohn Marino initializes the EXIT_CONDITIONS array. */
894*e4b17023SJohn Marino
895*e4b17023SJohn Marino static void
select_loops_exit_conditions(VEC (gimple,heap)** exit_conditions)896*e4b17023SJohn Marino select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions)
897*e4b17023SJohn Marino {
898*e4b17023SJohn Marino struct loop *function_body = current_loops->tree_root;
899*e4b17023SJohn Marino
900*e4b17023SJohn Marino get_exit_conditions_rec (function_body->inner, exit_conditions);
901*e4b17023SJohn Marino }
902*e4b17023SJohn Marino
903*e4b17023SJohn Marino
904*e4b17023SJohn Marino /* Depth first search algorithm. */
905*e4b17023SJohn Marino
906*e4b17023SJohn Marino typedef enum t_bool {
907*e4b17023SJohn Marino t_false,
908*e4b17023SJohn Marino t_true,
909*e4b17023SJohn Marino t_dont_know
910*e4b17023SJohn Marino } t_bool;
911*e4b17023SJohn Marino
912*e4b17023SJohn Marino
913*e4b17023SJohn Marino static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
914*e4b17023SJohn Marino
915*e4b17023SJohn Marino /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
916*e4b17023SJohn Marino Return true if the strongly connected component has been found. */
917*e4b17023SJohn Marino
918*e4b17023SJohn Marino static t_bool
follow_ssa_edge_binary(struct loop * loop,gimple at_stmt,tree type,tree rhs0,enum tree_code code,tree rhs1,gimple halting_phi,tree * evolution_of_loop,int limit)919*e4b17023SJohn Marino follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
920*e4b17023SJohn Marino tree type, tree rhs0, enum tree_code code, tree rhs1,
921*e4b17023SJohn Marino gimple halting_phi, tree *evolution_of_loop, int limit)
922*e4b17023SJohn Marino {
923*e4b17023SJohn Marino t_bool res = t_false;
924*e4b17023SJohn Marino tree evol;
925*e4b17023SJohn Marino
926*e4b17023SJohn Marino switch (code)
927*e4b17023SJohn Marino {
928*e4b17023SJohn Marino case POINTER_PLUS_EXPR:
929*e4b17023SJohn Marino case PLUS_EXPR:
930*e4b17023SJohn Marino if (TREE_CODE (rhs0) == SSA_NAME)
931*e4b17023SJohn Marino {
932*e4b17023SJohn Marino if (TREE_CODE (rhs1) == SSA_NAME)
933*e4b17023SJohn Marino {
934*e4b17023SJohn Marino /* Match an assignment under the form:
935*e4b17023SJohn Marino "a = b + c". */
936*e4b17023SJohn Marino
937*e4b17023SJohn Marino /* We want only assignments of form "name + name" contribute to
938*e4b17023SJohn Marino LIMIT, as the other cases do not necessarily contribute to
939*e4b17023SJohn Marino the complexity of the expression. */
940*e4b17023SJohn Marino limit++;
941*e4b17023SJohn Marino
942*e4b17023SJohn Marino evol = *evolution_of_loop;
943*e4b17023SJohn Marino res = follow_ssa_edge
944*e4b17023SJohn Marino (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
945*e4b17023SJohn Marino
946*e4b17023SJohn Marino if (res == t_true)
947*e4b17023SJohn Marino *evolution_of_loop = add_to_evolution
948*e4b17023SJohn Marino (loop->num,
949*e4b17023SJohn Marino chrec_convert (type, evol, at_stmt),
950*e4b17023SJohn Marino code, rhs1, at_stmt);
951*e4b17023SJohn Marino
952*e4b17023SJohn Marino else if (res == t_false)
953*e4b17023SJohn Marino {
954*e4b17023SJohn Marino res = follow_ssa_edge
955*e4b17023SJohn Marino (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
956*e4b17023SJohn Marino evolution_of_loop, limit);
957*e4b17023SJohn Marino
958*e4b17023SJohn Marino if (res == t_true)
959*e4b17023SJohn Marino *evolution_of_loop = add_to_evolution
960*e4b17023SJohn Marino (loop->num,
961*e4b17023SJohn Marino chrec_convert (type, *evolution_of_loop, at_stmt),
962*e4b17023SJohn Marino code, rhs0, at_stmt);
963*e4b17023SJohn Marino
964*e4b17023SJohn Marino else if (res == t_dont_know)
965*e4b17023SJohn Marino *evolution_of_loop = chrec_dont_know;
966*e4b17023SJohn Marino }
967*e4b17023SJohn Marino
968*e4b17023SJohn Marino else if (res == t_dont_know)
969*e4b17023SJohn Marino *evolution_of_loop = chrec_dont_know;
970*e4b17023SJohn Marino }
971*e4b17023SJohn Marino
972*e4b17023SJohn Marino else
973*e4b17023SJohn Marino {
974*e4b17023SJohn Marino /* Match an assignment under the form:
975*e4b17023SJohn Marino "a = b + ...". */
976*e4b17023SJohn Marino res = follow_ssa_edge
977*e4b17023SJohn Marino (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
978*e4b17023SJohn Marino evolution_of_loop, limit);
979*e4b17023SJohn Marino if (res == t_true)
980*e4b17023SJohn Marino *evolution_of_loop = add_to_evolution
981*e4b17023SJohn Marino (loop->num, chrec_convert (type, *evolution_of_loop,
982*e4b17023SJohn Marino at_stmt),
983*e4b17023SJohn Marino code, rhs1, at_stmt);
984*e4b17023SJohn Marino
985*e4b17023SJohn Marino else if (res == t_dont_know)
986*e4b17023SJohn Marino *evolution_of_loop = chrec_dont_know;
987*e4b17023SJohn Marino }
988*e4b17023SJohn Marino }
989*e4b17023SJohn Marino
990*e4b17023SJohn Marino else if (TREE_CODE (rhs1) == SSA_NAME)
991*e4b17023SJohn Marino {
992*e4b17023SJohn Marino /* Match an assignment under the form:
993*e4b17023SJohn Marino "a = ... + c". */
994*e4b17023SJohn Marino res = follow_ssa_edge
995*e4b17023SJohn Marino (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
996*e4b17023SJohn Marino evolution_of_loop, limit);
997*e4b17023SJohn Marino if (res == t_true)
998*e4b17023SJohn Marino *evolution_of_loop = add_to_evolution
999*e4b17023SJohn Marino (loop->num, chrec_convert (type, *evolution_of_loop,
1000*e4b17023SJohn Marino at_stmt),
1001*e4b17023SJohn Marino code, rhs0, at_stmt);
1002*e4b17023SJohn Marino
1003*e4b17023SJohn Marino else if (res == t_dont_know)
1004*e4b17023SJohn Marino *evolution_of_loop = chrec_dont_know;
1005*e4b17023SJohn Marino }
1006*e4b17023SJohn Marino
1007*e4b17023SJohn Marino else
1008*e4b17023SJohn Marino /* Otherwise, match an assignment under the form:
1009*e4b17023SJohn Marino "a = ... + ...". */
1010*e4b17023SJohn Marino /* And there is nothing to do. */
1011*e4b17023SJohn Marino res = t_false;
1012*e4b17023SJohn Marino break;
1013*e4b17023SJohn Marino
1014*e4b17023SJohn Marino case MINUS_EXPR:
1015*e4b17023SJohn Marino /* This case is under the form "opnd0 = rhs0 - rhs1". */
1016*e4b17023SJohn Marino if (TREE_CODE (rhs0) == SSA_NAME)
1017*e4b17023SJohn Marino {
1018*e4b17023SJohn Marino /* Match an assignment under the form:
1019*e4b17023SJohn Marino "a = b - ...". */
1020*e4b17023SJohn Marino
1021*e4b17023SJohn Marino /* We want only assignments of form "name - name" contribute to
1022*e4b17023SJohn Marino LIMIT, as the other cases do not necessarily contribute to
1023*e4b17023SJohn Marino the complexity of the expression. */
1024*e4b17023SJohn Marino if (TREE_CODE (rhs1) == SSA_NAME)
1025*e4b17023SJohn Marino limit++;
1026*e4b17023SJohn Marino
1027*e4b17023SJohn Marino res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1028*e4b17023SJohn Marino evolution_of_loop, limit);
1029*e4b17023SJohn Marino if (res == t_true)
1030*e4b17023SJohn Marino *evolution_of_loop = add_to_evolution
1031*e4b17023SJohn Marino (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1032*e4b17023SJohn Marino MINUS_EXPR, rhs1, at_stmt);
1033*e4b17023SJohn Marino
1034*e4b17023SJohn Marino else if (res == t_dont_know)
1035*e4b17023SJohn Marino *evolution_of_loop = chrec_dont_know;
1036*e4b17023SJohn Marino }
1037*e4b17023SJohn Marino else
1038*e4b17023SJohn Marino /* Otherwise, match an assignment under the form:
1039*e4b17023SJohn Marino "a = ... - ...". */
1040*e4b17023SJohn Marino /* And there is nothing to do. */
1041*e4b17023SJohn Marino res = t_false;
1042*e4b17023SJohn Marino break;
1043*e4b17023SJohn Marino
1044*e4b17023SJohn Marino default:
1045*e4b17023SJohn Marino res = t_false;
1046*e4b17023SJohn Marino }
1047*e4b17023SJohn Marino
1048*e4b17023SJohn Marino return res;
1049*e4b17023SJohn Marino }
1050*e4b17023SJohn Marino
1051*e4b17023SJohn Marino /* Follow the ssa edge into the expression EXPR.
1052*e4b17023SJohn Marino Return true if the strongly connected component has been found. */
1053*e4b17023SJohn Marino
1054*e4b17023SJohn Marino static t_bool
follow_ssa_edge_expr(struct loop * loop,gimple at_stmt,tree expr,gimple halting_phi,tree * evolution_of_loop,int limit)1055*e4b17023SJohn Marino follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1056*e4b17023SJohn Marino gimple halting_phi, tree *evolution_of_loop, int limit)
1057*e4b17023SJohn Marino {
1058*e4b17023SJohn Marino enum tree_code code = TREE_CODE (expr);
1059*e4b17023SJohn Marino tree type = TREE_TYPE (expr), rhs0, rhs1;
1060*e4b17023SJohn Marino t_bool res;
1061*e4b17023SJohn Marino
1062*e4b17023SJohn Marino /* The EXPR is one of the following cases:
1063*e4b17023SJohn Marino - an SSA_NAME,
1064*e4b17023SJohn Marino - an INTEGER_CST,
1065*e4b17023SJohn Marino - a PLUS_EXPR,
1066*e4b17023SJohn Marino - a POINTER_PLUS_EXPR,
1067*e4b17023SJohn Marino - a MINUS_EXPR,
1068*e4b17023SJohn Marino - an ASSERT_EXPR,
1069*e4b17023SJohn Marino - other cases are not yet handled. */
1070*e4b17023SJohn Marino
1071*e4b17023SJohn Marino switch (code)
1072*e4b17023SJohn Marino {
1073*e4b17023SJohn Marino CASE_CONVERT:
1074*e4b17023SJohn Marino /* This assignment is under the form "a_1 = (cast) rhs. */
1075*e4b17023SJohn Marino res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1076*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1077*e4b17023SJohn Marino *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1078*e4b17023SJohn Marino break;
1079*e4b17023SJohn Marino
1080*e4b17023SJohn Marino case INTEGER_CST:
1081*e4b17023SJohn Marino /* This assignment is under the form "a_1 = 7". */
1082*e4b17023SJohn Marino res = t_false;
1083*e4b17023SJohn Marino break;
1084*e4b17023SJohn Marino
1085*e4b17023SJohn Marino case SSA_NAME:
1086*e4b17023SJohn Marino /* This assignment is under the form: "a_1 = b_2". */
1087*e4b17023SJohn Marino res = follow_ssa_edge
1088*e4b17023SJohn Marino (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1089*e4b17023SJohn Marino break;
1090*e4b17023SJohn Marino
1091*e4b17023SJohn Marino case POINTER_PLUS_EXPR:
1092*e4b17023SJohn Marino case PLUS_EXPR:
1093*e4b17023SJohn Marino case MINUS_EXPR:
1094*e4b17023SJohn Marino /* This case is under the form "rhs0 +- rhs1". */
1095*e4b17023SJohn Marino rhs0 = TREE_OPERAND (expr, 0);
1096*e4b17023SJohn Marino rhs1 = TREE_OPERAND (expr, 1);
1097*e4b17023SJohn Marino type = TREE_TYPE (rhs0);
1098*e4b17023SJohn Marino STRIP_USELESS_TYPE_CONVERSION (rhs0);
1099*e4b17023SJohn Marino STRIP_USELESS_TYPE_CONVERSION (rhs1);
1100*e4b17023SJohn Marino res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1101*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1102*e4b17023SJohn Marino break;
1103*e4b17023SJohn Marino
1104*e4b17023SJohn Marino case ADDR_EXPR:
1105*e4b17023SJohn Marino /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1106*e4b17023SJohn Marino if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1107*e4b17023SJohn Marino {
1108*e4b17023SJohn Marino expr = TREE_OPERAND (expr, 0);
1109*e4b17023SJohn Marino rhs0 = TREE_OPERAND (expr, 0);
1110*e4b17023SJohn Marino rhs1 = TREE_OPERAND (expr, 1);
1111*e4b17023SJohn Marino type = TREE_TYPE (rhs0);
1112*e4b17023SJohn Marino STRIP_USELESS_TYPE_CONVERSION (rhs0);
1113*e4b17023SJohn Marino STRIP_USELESS_TYPE_CONVERSION (rhs1);
1114*e4b17023SJohn Marino res = follow_ssa_edge_binary (loop, at_stmt, type,
1115*e4b17023SJohn Marino rhs0, POINTER_PLUS_EXPR, rhs1,
1116*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1117*e4b17023SJohn Marino }
1118*e4b17023SJohn Marino else
1119*e4b17023SJohn Marino res = t_false;
1120*e4b17023SJohn Marino break;
1121*e4b17023SJohn Marino
1122*e4b17023SJohn Marino case ASSERT_EXPR:
1123*e4b17023SJohn Marino /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1124*e4b17023SJohn Marino It must be handled as a copy assignment of the form a_1 = a_2. */
1125*e4b17023SJohn Marino rhs0 = ASSERT_EXPR_VAR (expr);
1126*e4b17023SJohn Marino if (TREE_CODE (rhs0) == SSA_NAME)
1127*e4b17023SJohn Marino res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1128*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1129*e4b17023SJohn Marino else
1130*e4b17023SJohn Marino res = t_false;
1131*e4b17023SJohn Marino break;
1132*e4b17023SJohn Marino
1133*e4b17023SJohn Marino default:
1134*e4b17023SJohn Marino res = t_false;
1135*e4b17023SJohn Marino break;
1136*e4b17023SJohn Marino }
1137*e4b17023SJohn Marino
1138*e4b17023SJohn Marino return res;
1139*e4b17023SJohn Marino }
1140*e4b17023SJohn Marino
1141*e4b17023SJohn Marino /* Follow the ssa edge into the right hand side of an assignment STMT.
1142*e4b17023SJohn Marino Return true if the strongly connected component has been found. */
1143*e4b17023SJohn Marino
1144*e4b17023SJohn Marino static t_bool
follow_ssa_edge_in_rhs(struct loop * loop,gimple stmt,gimple halting_phi,tree * evolution_of_loop,int limit)1145*e4b17023SJohn Marino follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1146*e4b17023SJohn Marino gimple halting_phi, tree *evolution_of_loop, int limit)
1147*e4b17023SJohn Marino {
1148*e4b17023SJohn Marino enum tree_code code = gimple_assign_rhs_code (stmt);
1149*e4b17023SJohn Marino tree type = gimple_expr_type (stmt), rhs1, rhs2;
1150*e4b17023SJohn Marino t_bool res;
1151*e4b17023SJohn Marino
1152*e4b17023SJohn Marino switch (code)
1153*e4b17023SJohn Marino {
1154*e4b17023SJohn Marino CASE_CONVERT:
1155*e4b17023SJohn Marino /* This assignment is under the form "a_1 = (cast) rhs. */
1156*e4b17023SJohn Marino res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1157*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1158*e4b17023SJohn Marino *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1159*e4b17023SJohn Marino break;
1160*e4b17023SJohn Marino
1161*e4b17023SJohn Marino case POINTER_PLUS_EXPR:
1162*e4b17023SJohn Marino case PLUS_EXPR:
1163*e4b17023SJohn Marino case MINUS_EXPR:
1164*e4b17023SJohn Marino rhs1 = gimple_assign_rhs1 (stmt);
1165*e4b17023SJohn Marino rhs2 = gimple_assign_rhs2 (stmt);
1166*e4b17023SJohn Marino type = TREE_TYPE (rhs1);
1167*e4b17023SJohn Marino res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1168*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1169*e4b17023SJohn Marino break;
1170*e4b17023SJohn Marino
1171*e4b17023SJohn Marino default:
1172*e4b17023SJohn Marino if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1173*e4b17023SJohn Marino res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1174*e4b17023SJohn Marino halting_phi, evolution_of_loop, limit);
1175*e4b17023SJohn Marino else
1176*e4b17023SJohn Marino res = t_false;
1177*e4b17023SJohn Marino break;
1178*e4b17023SJohn Marino }
1179*e4b17023SJohn Marino
1180*e4b17023SJohn Marino return res;
1181*e4b17023SJohn Marino }
1182*e4b17023SJohn Marino
1183*e4b17023SJohn Marino /* Checks whether the I-th argument of a PHI comes from a backedge. */
1184*e4b17023SJohn Marino
1185*e4b17023SJohn Marino static bool
backedge_phi_arg_p(gimple phi,int i)1186*e4b17023SJohn Marino backedge_phi_arg_p (gimple phi, int i)
1187*e4b17023SJohn Marino {
1188*e4b17023SJohn Marino const_edge e = gimple_phi_arg_edge (phi, i);
1189*e4b17023SJohn Marino
1190*e4b17023SJohn Marino /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1191*e4b17023SJohn Marino about updating it anywhere, and this should work as well most of the
1192*e4b17023SJohn Marino time. */
1193*e4b17023SJohn Marino if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1194*e4b17023SJohn Marino return true;
1195*e4b17023SJohn Marino
1196*e4b17023SJohn Marino return false;
1197*e4b17023SJohn Marino }
1198*e4b17023SJohn Marino
1199*e4b17023SJohn Marino /* Helper function for one branch of the condition-phi-node. Return
1200*e4b17023SJohn Marino true if the strongly connected component has been found following
1201*e4b17023SJohn Marino this path. */
1202*e4b17023SJohn Marino
1203*e4b17023SJohn Marino static inline t_bool
follow_ssa_edge_in_condition_phi_branch(int i,struct loop * loop,gimple condition_phi,gimple halting_phi,tree * evolution_of_branch,tree init_cond,int limit)1204*e4b17023SJohn Marino follow_ssa_edge_in_condition_phi_branch (int i,
1205*e4b17023SJohn Marino struct loop *loop,
1206*e4b17023SJohn Marino gimple condition_phi,
1207*e4b17023SJohn Marino gimple halting_phi,
1208*e4b17023SJohn Marino tree *evolution_of_branch,
1209*e4b17023SJohn Marino tree init_cond, int limit)
1210*e4b17023SJohn Marino {
1211*e4b17023SJohn Marino tree branch = PHI_ARG_DEF (condition_phi, i);
1212*e4b17023SJohn Marino *evolution_of_branch = chrec_dont_know;
1213*e4b17023SJohn Marino
1214*e4b17023SJohn Marino /* Do not follow back edges (they must belong to an irreducible loop, which
1215*e4b17023SJohn Marino we really do not want to worry about). */
1216*e4b17023SJohn Marino if (backedge_phi_arg_p (condition_phi, i))
1217*e4b17023SJohn Marino return t_false;
1218*e4b17023SJohn Marino
1219*e4b17023SJohn Marino if (TREE_CODE (branch) == SSA_NAME)
1220*e4b17023SJohn Marino {
1221*e4b17023SJohn Marino *evolution_of_branch = init_cond;
1222*e4b17023SJohn Marino return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1223*e4b17023SJohn Marino evolution_of_branch, limit);
1224*e4b17023SJohn Marino }
1225*e4b17023SJohn Marino
1226*e4b17023SJohn Marino /* This case occurs when one of the condition branches sets
1227*e4b17023SJohn Marino the variable to a constant: i.e. a phi-node like
1228*e4b17023SJohn Marino "a_2 = PHI <a_7(5), 2(6)>;".
1229*e4b17023SJohn Marino
1230*e4b17023SJohn Marino FIXME: This case have to be refined correctly:
1231*e4b17023SJohn Marino in some cases it is possible to say something better than
1232*e4b17023SJohn Marino chrec_dont_know, for example using a wrap-around notation. */
1233*e4b17023SJohn Marino return t_false;
1234*e4b17023SJohn Marino }
1235*e4b17023SJohn Marino
1236*e4b17023SJohn Marino /* This function merges the branches of a condition-phi-node in a
1237*e4b17023SJohn Marino loop. */
1238*e4b17023SJohn Marino
1239*e4b17023SJohn Marino static t_bool
follow_ssa_edge_in_condition_phi(struct loop * loop,gimple condition_phi,gimple halting_phi,tree * evolution_of_loop,int limit)1240*e4b17023SJohn Marino follow_ssa_edge_in_condition_phi (struct loop *loop,
1241*e4b17023SJohn Marino gimple condition_phi,
1242*e4b17023SJohn Marino gimple halting_phi,
1243*e4b17023SJohn Marino tree *evolution_of_loop, int limit)
1244*e4b17023SJohn Marino {
1245*e4b17023SJohn Marino int i, n;
1246*e4b17023SJohn Marino tree init = *evolution_of_loop;
1247*e4b17023SJohn Marino tree evolution_of_branch;
1248*e4b17023SJohn Marino t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1249*e4b17023SJohn Marino halting_phi,
1250*e4b17023SJohn Marino &evolution_of_branch,
1251*e4b17023SJohn Marino init, limit);
1252*e4b17023SJohn Marino if (res == t_false || res == t_dont_know)
1253*e4b17023SJohn Marino return res;
1254*e4b17023SJohn Marino
1255*e4b17023SJohn Marino *evolution_of_loop = evolution_of_branch;
1256*e4b17023SJohn Marino
1257*e4b17023SJohn Marino n = gimple_phi_num_args (condition_phi);
1258*e4b17023SJohn Marino for (i = 1; i < n; i++)
1259*e4b17023SJohn Marino {
1260*e4b17023SJohn Marino /* Quickly give up when the evolution of one of the branches is
1261*e4b17023SJohn Marino not known. */
1262*e4b17023SJohn Marino if (*evolution_of_loop == chrec_dont_know)
1263*e4b17023SJohn Marino return t_true;
1264*e4b17023SJohn Marino
1265*e4b17023SJohn Marino /* Increase the limit by the PHI argument number to avoid exponential
1266*e4b17023SJohn Marino time and memory complexity. */
1267*e4b17023SJohn Marino res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1268*e4b17023SJohn Marino halting_phi,
1269*e4b17023SJohn Marino &evolution_of_branch,
1270*e4b17023SJohn Marino init, limit + i);
1271*e4b17023SJohn Marino if (res == t_false || res == t_dont_know)
1272*e4b17023SJohn Marino return res;
1273*e4b17023SJohn Marino
1274*e4b17023SJohn Marino *evolution_of_loop = chrec_merge (*evolution_of_loop,
1275*e4b17023SJohn Marino evolution_of_branch);
1276*e4b17023SJohn Marino }
1277*e4b17023SJohn Marino
1278*e4b17023SJohn Marino return t_true;
1279*e4b17023SJohn Marino }
1280*e4b17023SJohn Marino
1281*e4b17023SJohn Marino /* Follow an SSA edge in an inner loop. It computes the overall
1282*e4b17023SJohn Marino effect of the loop, and following the symbolic initial conditions,
1283*e4b17023SJohn Marino it follows the edges in the parent loop. The inner loop is
1284*e4b17023SJohn Marino considered as a single statement. */
1285*e4b17023SJohn Marino
1286*e4b17023SJohn Marino static t_bool
follow_ssa_edge_inner_loop_phi(struct loop * outer_loop,gimple loop_phi_node,gimple halting_phi,tree * evolution_of_loop,int limit)1287*e4b17023SJohn Marino follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1288*e4b17023SJohn Marino gimple loop_phi_node,
1289*e4b17023SJohn Marino gimple halting_phi,
1290*e4b17023SJohn Marino tree *evolution_of_loop, int limit)
1291*e4b17023SJohn Marino {
1292*e4b17023SJohn Marino struct loop *loop = loop_containing_stmt (loop_phi_node);
1293*e4b17023SJohn Marino tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1294*e4b17023SJohn Marino
1295*e4b17023SJohn Marino /* Sometimes, the inner loop is too difficult to analyze, and the
1296*e4b17023SJohn Marino result of the analysis is a symbolic parameter. */
1297*e4b17023SJohn Marino if (ev == PHI_RESULT (loop_phi_node))
1298*e4b17023SJohn Marino {
1299*e4b17023SJohn Marino t_bool res = t_false;
1300*e4b17023SJohn Marino int i, n = gimple_phi_num_args (loop_phi_node);
1301*e4b17023SJohn Marino
1302*e4b17023SJohn Marino for (i = 0; i < n; i++)
1303*e4b17023SJohn Marino {
1304*e4b17023SJohn Marino tree arg = PHI_ARG_DEF (loop_phi_node, i);
1305*e4b17023SJohn Marino basic_block bb;
1306*e4b17023SJohn Marino
1307*e4b17023SJohn Marino /* Follow the edges that exit the inner loop. */
1308*e4b17023SJohn Marino bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1309*e4b17023SJohn Marino if (!flow_bb_inside_loop_p (loop, bb))
1310*e4b17023SJohn Marino res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1311*e4b17023SJohn Marino arg, halting_phi,
1312*e4b17023SJohn Marino evolution_of_loop, limit);
1313*e4b17023SJohn Marino if (res == t_true)
1314*e4b17023SJohn Marino break;
1315*e4b17023SJohn Marino }
1316*e4b17023SJohn Marino
1317*e4b17023SJohn Marino /* If the path crosses this loop-phi, give up. */
1318*e4b17023SJohn Marino if (res == t_true)
1319*e4b17023SJohn Marino *evolution_of_loop = chrec_dont_know;
1320*e4b17023SJohn Marino
1321*e4b17023SJohn Marino return res;
1322*e4b17023SJohn Marino }
1323*e4b17023SJohn Marino
1324*e4b17023SJohn Marino /* Otherwise, compute the overall effect of the inner loop. */
1325*e4b17023SJohn Marino ev = compute_overall_effect_of_inner_loop (loop, ev);
1326*e4b17023SJohn Marino return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1327*e4b17023SJohn Marino evolution_of_loop, limit);
1328*e4b17023SJohn Marino }
1329*e4b17023SJohn Marino
1330*e4b17023SJohn Marino /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1331*e4b17023SJohn Marino path that is analyzed on the return walk. */
1332*e4b17023SJohn Marino
1333*e4b17023SJohn Marino static t_bool
follow_ssa_edge(struct loop * loop,gimple def,gimple halting_phi,tree * evolution_of_loop,int limit)1334*e4b17023SJohn Marino follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
1335*e4b17023SJohn Marino tree *evolution_of_loop, int limit)
1336*e4b17023SJohn Marino {
1337*e4b17023SJohn Marino struct loop *def_loop;
1338*e4b17023SJohn Marino
1339*e4b17023SJohn Marino if (gimple_nop_p (def))
1340*e4b17023SJohn Marino return t_false;
1341*e4b17023SJohn Marino
1342*e4b17023SJohn Marino /* Give up if the path is longer than the MAX that we allow. */
1343*e4b17023SJohn Marino if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1344*e4b17023SJohn Marino return t_dont_know;
1345*e4b17023SJohn Marino
1346*e4b17023SJohn Marino def_loop = loop_containing_stmt (def);
1347*e4b17023SJohn Marino
1348*e4b17023SJohn Marino switch (gimple_code (def))
1349*e4b17023SJohn Marino {
1350*e4b17023SJohn Marino case GIMPLE_PHI:
1351*e4b17023SJohn Marino if (!loop_phi_node_p (def))
1352*e4b17023SJohn Marino /* DEF is a condition-phi-node. Follow the branches, and
1353*e4b17023SJohn Marino record their evolutions. Finally, merge the collected
1354*e4b17023SJohn Marino information and set the approximation to the main
1355*e4b17023SJohn Marino variable. */
1356*e4b17023SJohn Marino return follow_ssa_edge_in_condition_phi
1357*e4b17023SJohn Marino (loop, def, halting_phi, evolution_of_loop, limit);
1358*e4b17023SJohn Marino
1359*e4b17023SJohn Marino /* When the analyzed phi is the halting_phi, the
1360*e4b17023SJohn Marino depth-first search is over: we have found a path from
1361*e4b17023SJohn Marino the halting_phi to itself in the loop. */
1362*e4b17023SJohn Marino if (def == halting_phi)
1363*e4b17023SJohn Marino return t_true;
1364*e4b17023SJohn Marino
1365*e4b17023SJohn Marino /* Otherwise, the evolution of the HALTING_PHI depends
1366*e4b17023SJohn Marino on the evolution of another loop-phi-node, i.e. the
1367*e4b17023SJohn Marino evolution function is a higher degree polynomial. */
1368*e4b17023SJohn Marino if (def_loop == loop)
1369*e4b17023SJohn Marino return t_false;
1370*e4b17023SJohn Marino
1371*e4b17023SJohn Marino /* Inner loop. */
1372*e4b17023SJohn Marino if (flow_loop_nested_p (loop, def_loop))
1373*e4b17023SJohn Marino return follow_ssa_edge_inner_loop_phi
1374*e4b17023SJohn Marino (loop, def, halting_phi, evolution_of_loop, limit + 1);
1375*e4b17023SJohn Marino
1376*e4b17023SJohn Marino /* Outer loop. */
1377*e4b17023SJohn Marino return t_false;
1378*e4b17023SJohn Marino
1379*e4b17023SJohn Marino case GIMPLE_ASSIGN:
1380*e4b17023SJohn Marino return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1381*e4b17023SJohn Marino evolution_of_loop, limit);
1382*e4b17023SJohn Marino
1383*e4b17023SJohn Marino default:
1384*e4b17023SJohn Marino /* At this level of abstraction, the program is just a set
1385*e4b17023SJohn Marino of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1386*e4b17023SJohn Marino other node to be handled. */
1387*e4b17023SJohn Marino return t_false;
1388*e4b17023SJohn Marino }
1389*e4b17023SJohn Marino }
1390*e4b17023SJohn Marino
1391*e4b17023SJohn Marino
1392*e4b17023SJohn Marino
1393*e4b17023SJohn Marino /* Given a LOOP_PHI_NODE, this function determines the evolution
1394*e4b17023SJohn Marino function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1395*e4b17023SJohn Marino
1396*e4b17023SJohn Marino static tree
analyze_evolution_in_loop(gimple loop_phi_node,tree init_cond)1397*e4b17023SJohn Marino analyze_evolution_in_loop (gimple loop_phi_node,
1398*e4b17023SJohn Marino tree init_cond)
1399*e4b17023SJohn Marino {
1400*e4b17023SJohn Marino int i, n = gimple_phi_num_args (loop_phi_node);
1401*e4b17023SJohn Marino tree evolution_function = chrec_not_analyzed_yet;
1402*e4b17023SJohn Marino struct loop *loop = loop_containing_stmt (loop_phi_node);
1403*e4b17023SJohn Marino basic_block bb;
1404*e4b17023SJohn Marino
1405*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
1406*e4b17023SJohn Marino {
1407*e4b17023SJohn Marino fprintf (dump_file, "(analyze_evolution_in_loop \n");
1408*e4b17023SJohn Marino fprintf (dump_file, " (loop_phi_node = ");
1409*e4b17023SJohn Marino print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1410*e4b17023SJohn Marino fprintf (dump_file, ")\n");
1411*e4b17023SJohn Marino }
1412*e4b17023SJohn Marino
1413*e4b17023SJohn Marino for (i = 0; i < n; i++)
1414*e4b17023SJohn Marino {
1415*e4b17023SJohn Marino tree arg = PHI_ARG_DEF (loop_phi_node, i);
1416*e4b17023SJohn Marino gimple ssa_chain;
1417*e4b17023SJohn Marino tree ev_fn;
1418*e4b17023SJohn Marino t_bool res;
1419*e4b17023SJohn Marino
1420*e4b17023SJohn Marino /* Select the edges that enter the loop body. */
1421*e4b17023SJohn Marino bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1422*e4b17023SJohn Marino if (!flow_bb_inside_loop_p (loop, bb))
1423*e4b17023SJohn Marino continue;
1424*e4b17023SJohn Marino
1425*e4b17023SJohn Marino if (TREE_CODE (arg) == SSA_NAME)
1426*e4b17023SJohn Marino {
1427*e4b17023SJohn Marino bool val = false;
1428*e4b17023SJohn Marino
1429*e4b17023SJohn Marino ssa_chain = SSA_NAME_DEF_STMT (arg);
1430*e4b17023SJohn Marino
1431*e4b17023SJohn Marino /* Pass in the initial condition to the follow edge function. */
1432*e4b17023SJohn Marino ev_fn = init_cond;
1433*e4b17023SJohn Marino res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1434*e4b17023SJohn Marino
1435*e4b17023SJohn Marino /* If ev_fn has no evolution in the inner loop, and the
1436*e4b17023SJohn Marino init_cond is not equal to ev_fn, then we have an
1437*e4b17023SJohn Marino ambiguity between two possible values, as we cannot know
1438*e4b17023SJohn Marino the number of iterations at this point. */
1439*e4b17023SJohn Marino if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1440*e4b17023SJohn Marino && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1441*e4b17023SJohn Marino && !operand_equal_p (init_cond, ev_fn, 0))
1442*e4b17023SJohn Marino ev_fn = chrec_dont_know;
1443*e4b17023SJohn Marino }
1444*e4b17023SJohn Marino else
1445*e4b17023SJohn Marino res = t_false;
1446*e4b17023SJohn Marino
1447*e4b17023SJohn Marino /* When it is impossible to go back on the same
1448*e4b17023SJohn Marino loop_phi_node by following the ssa edges, the
1449*e4b17023SJohn Marino evolution is represented by a peeled chrec, i.e. the
1450*e4b17023SJohn Marino first iteration, EV_FN has the value INIT_COND, then
1451*e4b17023SJohn Marino all the other iterations it has the value of ARG.
1452*e4b17023SJohn Marino For the moment, PEELED_CHREC nodes are not built. */
1453*e4b17023SJohn Marino if (res != t_true)
1454*e4b17023SJohn Marino ev_fn = chrec_dont_know;
1455*e4b17023SJohn Marino
1456*e4b17023SJohn Marino /* When there are multiple back edges of the loop (which in fact never
1457*e4b17023SJohn Marino happens currently, but nevertheless), merge their evolutions. */
1458*e4b17023SJohn Marino evolution_function = chrec_merge (evolution_function, ev_fn);
1459*e4b17023SJohn Marino }
1460*e4b17023SJohn Marino
1461*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
1462*e4b17023SJohn Marino {
1463*e4b17023SJohn Marino fprintf (dump_file, " (evolution_function = ");
1464*e4b17023SJohn Marino print_generic_expr (dump_file, evolution_function, 0);
1465*e4b17023SJohn Marino fprintf (dump_file, "))\n");
1466*e4b17023SJohn Marino }
1467*e4b17023SJohn Marino
1468*e4b17023SJohn Marino return evolution_function;
1469*e4b17023SJohn Marino }
1470*e4b17023SJohn Marino
1471*e4b17023SJohn Marino /* Given a loop-phi-node, return the initial conditions of the
1472*e4b17023SJohn Marino variable on entry of the loop. When the CCP has propagated
1473*e4b17023SJohn Marino constants into the loop-phi-node, the initial condition is
1474*e4b17023SJohn Marino instantiated, otherwise the initial condition is kept symbolic.
1475*e4b17023SJohn Marino This analyzer does not analyze the evolution outside the current
1476*e4b17023SJohn Marino loop, and leaves this task to the on-demand tree reconstructor. */
1477*e4b17023SJohn Marino
1478*e4b17023SJohn Marino static tree
analyze_initial_condition(gimple loop_phi_node)1479*e4b17023SJohn Marino analyze_initial_condition (gimple loop_phi_node)
1480*e4b17023SJohn Marino {
1481*e4b17023SJohn Marino int i, n;
1482*e4b17023SJohn Marino tree init_cond = chrec_not_analyzed_yet;
1483*e4b17023SJohn Marino struct loop *loop = loop_containing_stmt (loop_phi_node);
1484*e4b17023SJohn Marino
1485*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
1486*e4b17023SJohn Marino {
1487*e4b17023SJohn Marino fprintf (dump_file, "(analyze_initial_condition \n");
1488*e4b17023SJohn Marino fprintf (dump_file, " (loop_phi_node = \n");
1489*e4b17023SJohn Marino print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1490*e4b17023SJohn Marino fprintf (dump_file, ")\n");
1491*e4b17023SJohn Marino }
1492*e4b17023SJohn Marino
1493*e4b17023SJohn Marino n = gimple_phi_num_args (loop_phi_node);
1494*e4b17023SJohn Marino for (i = 0; i < n; i++)
1495*e4b17023SJohn Marino {
1496*e4b17023SJohn Marino tree branch = PHI_ARG_DEF (loop_phi_node, i);
1497*e4b17023SJohn Marino basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1498*e4b17023SJohn Marino
1499*e4b17023SJohn Marino /* When the branch is oriented to the loop's body, it does
1500*e4b17023SJohn Marino not contribute to the initial condition. */
1501*e4b17023SJohn Marino if (flow_bb_inside_loop_p (loop, bb))
1502*e4b17023SJohn Marino continue;
1503*e4b17023SJohn Marino
1504*e4b17023SJohn Marino if (init_cond == chrec_not_analyzed_yet)
1505*e4b17023SJohn Marino {
1506*e4b17023SJohn Marino init_cond = branch;
1507*e4b17023SJohn Marino continue;
1508*e4b17023SJohn Marino }
1509*e4b17023SJohn Marino
1510*e4b17023SJohn Marino if (TREE_CODE (branch) == SSA_NAME)
1511*e4b17023SJohn Marino {
1512*e4b17023SJohn Marino init_cond = chrec_dont_know;
1513*e4b17023SJohn Marino break;
1514*e4b17023SJohn Marino }
1515*e4b17023SJohn Marino
1516*e4b17023SJohn Marino init_cond = chrec_merge (init_cond, branch);
1517*e4b17023SJohn Marino }
1518*e4b17023SJohn Marino
1519*e4b17023SJohn Marino /* Ooops -- a loop without an entry??? */
1520*e4b17023SJohn Marino if (init_cond == chrec_not_analyzed_yet)
1521*e4b17023SJohn Marino init_cond = chrec_dont_know;
1522*e4b17023SJohn Marino
1523*e4b17023SJohn Marino /* During early loop unrolling we do not have fully constant propagated IL.
1524*e4b17023SJohn Marino Handle degenerate PHIs here to not miss important unrollings. */
1525*e4b17023SJohn Marino if (TREE_CODE (init_cond) == SSA_NAME)
1526*e4b17023SJohn Marino {
1527*e4b17023SJohn Marino gimple def = SSA_NAME_DEF_STMT (init_cond);
1528*e4b17023SJohn Marino tree res;
1529*e4b17023SJohn Marino if (gimple_code (def) == GIMPLE_PHI
1530*e4b17023SJohn Marino && (res = degenerate_phi_result (def)) != NULL_TREE
1531*e4b17023SJohn Marino /* Only allow invariants here, otherwise we may break
1532*e4b17023SJohn Marino loop-closed SSA form. */
1533*e4b17023SJohn Marino && is_gimple_min_invariant (res))
1534*e4b17023SJohn Marino init_cond = res;
1535*e4b17023SJohn Marino }
1536*e4b17023SJohn Marino
1537*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
1538*e4b17023SJohn Marino {
1539*e4b17023SJohn Marino fprintf (dump_file, " (init_cond = ");
1540*e4b17023SJohn Marino print_generic_expr (dump_file, init_cond, 0);
1541*e4b17023SJohn Marino fprintf (dump_file, "))\n");
1542*e4b17023SJohn Marino }
1543*e4b17023SJohn Marino
1544*e4b17023SJohn Marino return init_cond;
1545*e4b17023SJohn Marino }
1546*e4b17023SJohn Marino
1547*e4b17023SJohn Marino /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1548*e4b17023SJohn Marino
1549*e4b17023SJohn Marino static tree
interpret_loop_phi(struct loop * loop,gimple loop_phi_node)1550*e4b17023SJohn Marino interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
1551*e4b17023SJohn Marino {
1552*e4b17023SJohn Marino tree res;
1553*e4b17023SJohn Marino struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1554*e4b17023SJohn Marino tree init_cond;
1555*e4b17023SJohn Marino
1556*e4b17023SJohn Marino if (phi_loop != loop)
1557*e4b17023SJohn Marino {
1558*e4b17023SJohn Marino struct loop *subloop;
1559*e4b17023SJohn Marino tree evolution_fn = analyze_scalar_evolution
1560*e4b17023SJohn Marino (phi_loop, PHI_RESULT (loop_phi_node));
1561*e4b17023SJohn Marino
1562*e4b17023SJohn Marino /* Dive one level deeper. */
1563*e4b17023SJohn Marino subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1564*e4b17023SJohn Marino
1565*e4b17023SJohn Marino /* Interpret the subloop. */
1566*e4b17023SJohn Marino res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1567*e4b17023SJohn Marino return res;
1568*e4b17023SJohn Marino }
1569*e4b17023SJohn Marino
1570*e4b17023SJohn Marino /* Otherwise really interpret the loop phi. */
1571*e4b17023SJohn Marino init_cond = analyze_initial_condition (loop_phi_node);
1572*e4b17023SJohn Marino res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1573*e4b17023SJohn Marino
1574*e4b17023SJohn Marino /* Verify we maintained the correct initial condition throughout
1575*e4b17023SJohn Marino possible conversions in the SSA chain. */
1576*e4b17023SJohn Marino if (res != chrec_dont_know)
1577*e4b17023SJohn Marino {
1578*e4b17023SJohn Marino tree new_init = res;
1579*e4b17023SJohn Marino if (CONVERT_EXPR_P (res)
1580*e4b17023SJohn Marino && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1581*e4b17023SJohn Marino new_init = fold_convert (TREE_TYPE (res),
1582*e4b17023SJohn Marino CHREC_LEFT (TREE_OPERAND (res, 0)));
1583*e4b17023SJohn Marino else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1584*e4b17023SJohn Marino new_init = CHREC_LEFT (res);
1585*e4b17023SJohn Marino STRIP_USELESS_TYPE_CONVERSION (new_init);
1586*e4b17023SJohn Marino if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1587*e4b17023SJohn Marino || !operand_equal_p (init_cond, new_init, 0))
1588*e4b17023SJohn Marino return chrec_dont_know;
1589*e4b17023SJohn Marino }
1590*e4b17023SJohn Marino
1591*e4b17023SJohn Marino return res;
1592*e4b17023SJohn Marino }
1593*e4b17023SJohn Marino
1594*e4b17023SJohn Marino /* This function merges the branches of a condition-phi-node,
1595*e4b17023SJohn Marino contained in the outermost loop, and whose arguments are already
1596*e4b17023SJohn Marino analyzed. */
1597*e4b17023SJohn Marino
1598*e4b17023SJohn Marino static tree
interpret_condition_phi(struct loop * loop,gimple condition_phi)1599*e4b17023SJohn Marino interpret_condition_phi (struct loop *loop, gimple condition_phi)
1600*e4b17023SJohn Marino {
1601*e4b17023SJohn Marino int i, n = gimple_phi_num_args (condition_phi);
1602*e4b17023SJohn Marino tree res = chrec_not_analyzed_yet;
1603*e4b17023SJohn Marino
1604*e4b17023SJohn Marino for (i = 0; i < n; i++)
1605*e4b17023SJohn Marino {
1606*e4b17023SJohn Marino tree branch_chrec;
1607*e4b17023SJohn Marino
1608*e4b17023SJohn Marino if (backedge_phi_arg_p (condition_phi, i))
1609*e4b17023SJohn Marino {
1610*e4b17023SJohn Marino res = chrec_dont_know;
1611*e4b17023SJohn Marino break;
1612*e4b17023SJohn Marino }
1613*e4b17023SJohn Marino
1614*e4b17023SJohn Marino branch_chrec = analyze_scalar_evolution
1615*e4b17023SJohn Marino (loop, PHI_ARG_DEF (condition_phi, i));
1616*e4b17023SJohn Marino
1617*e4b17023SJohn Marino res = chrec_merge (res, branch_chrec);
1618*e4b17023SJohn Marino }
1619*e4b17023SJohn Marino
1620*e4b17023SJohn Marino return res;
1621*e4b17023SJohn Marino }
1622*e4b17023SJohn Marino
1623*e4b17023SJohn Marino /* Interpret the operation RHS1 OP RHS2. If we didn't
1624*e4b17023SJohn Marino analyze this node before, follow the definitions until ending
1625*e4b17023SJohn Marino either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1626*e4b17023SJohn Marino return path, this function propagates evolutions (ala constant copy
1627*e4b17023SJohn Marino propagation). OPND1 is not a GIMPLE expression because we could
1628*e4b17023SJohn Marino analyze the effect of an inner loop: see interpret_loop_phi. */
1629*e4b17023SJohn Marino
1630*e4b17023SJohn Marino static tree
interpret_rhs_expr(struct loop * loop,gimple at_stmt,tree type,tree rhs1,enum tree_code code,tree rhs2)1631*e4b17023SJohn Marino interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1632*e4b17023SJohn Marino tree type, tree rhs1, enum tree_code code, tree rhs2)
1633*e4b17023SJohn Marino {
1634*e4b17023SJohn Marino tree res, chrec1, chrec2;
1635*e4b17023SJohn Marino
1636*e4b17023SJohn Marino if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1637*e4b17023SJohn Marino {
1638*e4b17023SJohn Marino if (is_gimple_min_invariant (rhs1))
1639*e4b17023SJohn Marino return chrec_convert (type, rhs1, at_stmt);
1640*e4b17023SJohn Marino
1641*e4b17023SJohn Marino if (code == SSA_NAME)
1642*e4b17023SJohn Marino return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1643*e4b17023SJohn Marino at_stmt);
1644*e4b17023SJohn Marino
1645*e4b17023SJohn Marino if (code == ASSERT_EXPR)
1646*e4b17023SJohn Marino {
1647*e4b17023SJohn Marino rhs1 = ASSERT_EXPR_VAR (rhs1);
1648*e4b17023SJohn Marino return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1649*e4b17023SJohn Marino at_stmt);
1650*e4b17023SJohn Marino }
1651*e4b17023SJohn Marino }
1652*e4b17023SJohn Marino
1653*e4b17023SJohn Marino switch (code)
1654*e4b17023SJohn Marino {
1655*e4b17023SJohn Marino case ADDR_EXPR:
1656*e4b17023SJohn Marino /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1657*e4b17023SJohn Marino if (TREE_CODE (TREE_OPERAND (rhs1, 0)) != MEM_REF)
1658*e4b17023SJohn Marino {
1659*e4b17023SJohn Marino res = chrec_dont_know;
1660*e4b17023SJohn Marino break;
1661*e4b17023SJohn Marino }
1662*e4b17023SJohn Marino
1663*e4b17023SJohn Marino rhs2 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 1);
1664*e4b17023SJohn Marino rhs1 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 0);
1665*e4b17023SJohn Marino /* Fall through. */
1666*e4b17023SJohn Marino
1667*e4b17023SJohn Marino case POINTER_PLUS_EXPR:
1668*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1669*e4b17023SJohn Marino chrec2 = analyze_scalar_evolution (loop, rhs2);
1670*e4b17023SJohn Marino chrec1 = chrec_convert (type, chrec1, at_stmt);
1671*e4b17023SJohn Marino chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1672*e4b17023SJohn Marino res = chrec_fold_plus (type, chrec1, chrec2);
1673*e4b17023SJohn Marino break;
1674*e4b17023SJohn Marino
1675*e4b17023SJohn Marino case PLUS_EXPR:
1676*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1677*e4b17023SJohn Marino chrec2 = analyze_scalar_evolution (loop, rhs2);
1678*e4b17023SJohn Marino chrec1 = chrec_convert (type, chrec1, at_stmt);
1679*e4b17023SJohn Marino chrec2 = chrec_convert (type, chrec2, at_stmt);
1680*e4b17023SJohn Marino res = chrec_fold_plus (type, chrec1, chrec2);
1681*e4b17023SJohn Marino break;
1682*e4b17023SJohn Marino
1683*e4b17023SJohn Marino case MINUS_EXPR:
1684*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1685*e4b17023SJohn Marino chrec2 = analyze_scalar_evolution (loop, rhs2);
1686*e4b17023SJohn Marino chrec1 = chrec_convert (type, chrec1, at_stmt);
1687*e4b17023SJohn Marino chrec2 = chrec_convert (type, chrec2, at_stmt);
1688*e4b17023SJohn Marino res = chrec_fold_minus (type, chrec1, chrec2);
1689*e4b17023SJohn Marino break;
1690*e4b17023SJohn Marino
1691*e4b17023SJohn Marino case NEGATE_EXPR:
1692*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1693*e4b17023SJohn Marino chrec1 = chrec_convert (type, chrec1, at_stmt);
1694*e4b17023SJohn Marino /* TYPE may be integer, real or complex, so use fold_convert. */
1695*e4b17023SJohn Marino res = chrec_fold_multiply (type, chrec1,
1696*e4b17023SJohn Marino fold_convert (type, integer_minus_one_node));
1697*e4b17023SJohn Marino break;
1698*e4b17023SJohn Marino
1699*e4b17023SJohn Marino case BIT_NOT_EXPR:
1700*e4b17023SJohn Marino /* Handle ~X as -1 - X. */
1701*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1702*e4b17023SJohn Marino chrec1 = chrec_convert (type, chrec1, at_stmt);
1703*e4b17023SJohn Marino res = chrec_fold_minus (type,
1704*e4b17023SJohn Marino fold_convert (type, integer_minus_one_node),
1705*e4b17023SJohn Marino chrec1);
1706*e4b17023SJohn Marino break;
1707*e4b17023SJohn Marino
1708*e4b17023SJohn Marino case MULT_EXPR:
1709*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1710*e4b17023SJohn Marino chrec2 = analyze_scalar_evolution (loop, rhs2);
1711*e4b17023SJohn Marino chrec1 = chrec_convert (type, chrec1, at_stmt);
1712*e4b17023SJohn Marino chrec2 = chrec_convert (type, chrec2, at_stmt);
1713*e4b17023SJohn Marino res = chrec_fold_multiply (type, chrec1, chrec2);
1714*e4b17023SJohn Marino break;
1715*e4b17023SJohn Marino
1716*e4b17023SJohn Marino CASE_CONVERT:
1717*e4b17023SJohn Marino chrec1 = analyze_scalar_evolution (loop, rhs1);
1718*e4b17023SJohn Marino res = chrec_convert (type, chrec1, at_stmt);
1719*e4b17023SJohn Marino break;
1720*e4b17023SJohn Marino
1721*e4b17023SJohn Marino default:
1722*e4b17023SJohn Marino res = chrec_dont_know;
1723*e4b17023SJohn Marino break;
1724*e4b17023SJohn Marino }
1725*e4b17023SJohn Marino
1726*e4b17023SJohn Marino return res;
1727*e4b17023SJohn Marino }
1728*e4b17023SJohn Marino
1729*e4b17023SJohn Marino /* Interpret the expression EXPR. */
1730*e4b17023SJohn Marino
1731*e4b17023SJohn Marino static tree
interpret_expr(struct loop * loop,gimple at_stmt,tree expr)1732*e4b17023SJohn Marino interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1733*e4b17023SJohn Marino {
1734*e4b17023SJohn Marino enum tree_code code;
1735*e4b17023SJohn Marino tree type = TREE_TYPE (expr), op0, op1;
1736*e4b17023SJohn Marino
1737*e4b17023SJohn Marino if (automatically_generated_chrec_p (expr))
1738*e4b17023SJohn Marino return expr;
1739*e4b17023SJohn Marino
1740*e4b17023SJohn Marino if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1741*e4b17023SJohn Marino || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1742*e4b17023SJohn Marino return chrec_dont_know;
1743*e4b17023SJohn Marino
1744*e4b17023SJohn Marino extract_ops_from_tree (expr, &code, &op0, &op1);
1745*e4b17023SJohn Marino
1746*e4b17023SJohn Marino return interpret_rhs_expr (loop, at_stmt, type,
1747*e4b17023SJohn Marino op0, code, op1);
1748*e4b17023SJohn Marino }
1749*e4b17023SJohn Marino
1750*e4b17023SJohn Marino /* Interpret the rhs of the assignment STMT. */
1751*e4b17023SJohn Marino
1752*e4b17023SJohn Marino static tree
interpret_gimple_assign(struct loop * loop,gimple stmt)1753*e4b17023SJohn Marino interpret_gimple_assign (struct loop *loop, gimple stmt)
1754*e4b17023SJohn Marino {
1755*e4b17023SJohn Marino tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1756*e4b17023SJohn Marino enum tree_code code = gimple_assign_rhs_code (stmt);
1757*e4b17023SJohn Marino
1758*e4b17023SJohn Marino return interpret_rhs_expr (loop, stmt, type,
1759*e4b17023SJohn Marino gimple_assign_rhs1 (stmt), code,
1760*e4b17023SJohn Marino gimple_assign_rhs2 (stmt));
1761*e4b17023SJohn Marino }
1762*e4b17023SJohn Marino
1763*e4b17023SJohn Marino
1764*e4b17023SJohn Marino
1765*e4b17023SJohn Marino /* This section contains all the entry points:
1766*e4b17023SJohn Marino - number_of_iterations_in_loop,
1767*e4b17023SJohn Marino - analyze_scalar_evolution,
1768*e4b17023SJohn Marino - instantiate_parameters.
1769*e4b17023SJohn Marino */
1770*e4b17023SJohn Marino
1771*e4b17023SJohn Marino /* Compute and return the evolution function in WRTO_LOOP, the nearest
1772*e4b17023SJohn Marino common ancestor of DEF_LOOP and USE_LOOP. */
1773*e4b17023SJohn Marino
1774*e4b17023SJohn Marino static tree
compute_scalar_evolution_in_loop(struct loop * wrto_loop,struct loop * def_loop,tree ev)1775*e4b17023SJohn Marino compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1776*e4b17023SJohn Marino struct loop *def_loop,
1777*e4b17023SJohn Marino tree ev)
1778*e4b17023SJohn Marino {
1779*e4b17023SJohn Marino bool val;
1780*e4b17023SJohn Marino tree res;
1781*e4b17023SJohn Marino
1782*e4b17023SJohn Marino if (def_loop == wrto_loop)
1783*e4b17023SJohn Marino return ev;
1784*e4b17023SJohn Marino
1785*e4b17023SJohn Marino def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1786*e4b17023SJohn Marino res = compute_overall_effect_of_inner_loop (def_loop, ev);
1787*e4b17023SJohn Marino
1788*e4b17023SJohn Marino if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
1789*e4b17023SJohn Marino return res;
1790*e4b17023SJohn Marino
1791*e4b17023SJohn Marino return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1792*e4b17023SJohn Marino }
1793*e4b17023SJohn Marino
1794*e4b17023SJohn Marino /* Helper recursive function. */
1795*e4b17023SJohn Marino
1796*e4b17023SJohn Marino static tree
analyze_scalar_evolution_1(struct loop * loop,tree var,tree res)1797*e4b17023SJohn Marino analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1798*e4b17023SJohn Marino {
1799*e4b17023SJohn Marino tree type = TREE_TYPE (var);
1800*e4b17023SJohn Marino gimple def;
1801*e4b17023SJohn Marino basic_block bb;
1802*e4b17023SJohn Marino struct loop *def_loop;
1803*e4b17023SJohn Marino
1804*e4b17023SJohn Marino if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1805*e4b17023SJohn Marino return chrec_dont_know;
1806*e4b17023SJohn Marino
1807*e4b17023SJohn Marino if (TREE_CODE (var) != SSA_NAME)
1808*e4b17023SJohn Marino return interpret_expr (loop, NULL, var);
1809*e4b17023SJohn Marino
1810*e4b17023SJohn Marino def = SSA_NAME_DEF_STMT (var);
1811*e4b17023SJohn Marino bb = gimple_bb (def);
1812*e4b17023SJohn Marino def_loop = bb ? bb->loop_father : NULL;
1813*e4b17023SJohn Marino
1814*e4b17023SJohn Marino if (bb == NULL
1815*e4b17023SJohn Marino || !flow_bb_inside_loop_p (loop, bb))
1816*e4b17023SJohn Marino {
1817*e4b17023SJohn Marino /* Keep the symbolic form. */
1818*e4b17023SJohn Marino res = var;
1819*e4b17023SJohn Marino goto set_and_end;
1820*e4b17023SJohn Marino }
1821*e4b17023SJohn Marino
1822*e4b17023SJohn Marino if (res != chrec_not_analyzed_yet)
1823*e4b17023SJohn Marino {
1824*e4b17023SJohn Marino if (loop != bb->loop_father)
1825*e4b17023SJohn Marino res = compute_scalar_evolution_in_loop
1826*e4b17023SJohn Marino (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1827*e4b17023SJohn Marino
1828*e4b17023SJohn Marino goto set_and_end;
1829*e4b17023SJohn Marino }
1830*e4b17023SJohn Marino
1831*e4b17023SJohn Marino if (loop != def_loop)
1832*e4b17023SJohn Marino {
1833*e4b17023SJohn Marino res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1834*e4b17023SJohn Marino res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1835*e4b17023SJohn Marino
1836*e4b17023SJohn Marino goto set_and_end;
1837*e4b17023SJohn Marino }
1838*e4b17023SJohn Marino
1839*e4b17023SJohn Marino switch (gimple_code (def))
1840*e4b17023SJohn Marino {
1841*e4b17023SJohn Marino case GIMPLE_ASSIGN:
1842*e4b17023SJohn Marino res = interpret_gimple_assign (loop, def);
1843*e4b17023SJohn Marino break;
1844*e4b17023SJohn Marino
1845*e4b17023SJohn Marino case GIMPLE_PHI:
1846*e4b17023SJohn Marino if (loop_phi_node_p (def))
1847*e4b17023SJohn Marino res = interpret_loop_phi (loop, def);
1848*e4b17023SJohn Marino else
1849*e4b17023SJohn Marino res = interpret_condition_phi (loop, def);
1850*e4b17023SJohn Marino break;
1851*e4b17023SJohn Marino
1852*e4b17023SJohn Marino default:
1853*e4b17023SJohn Marino res = chrec_dont_know;
1854*e4b17023SJohn Marino break;
1855*e4b17023SJohn Marino }
1856*e4b17023SJohn Marino
1857*e4b17023SJohn Marino set_and_end:
1858*e4b17023SJohn Marino
1859*e4b17023SJohn Marino /* Keep the symbolic form. */
1860*e4b17023SJohn Marino if (res == chrec_dont_know)
1861*e4b17023SJohn Marino res = var;
1862*e4b17023SJohn Marino
1863*e4b17023SJohn Marino if (loop == def_loop)
1864*e4b17023SJohn Marino set_scalar_evolution (block_before_loop (loop), var, res);
1865*e4b17023SJohn Marino
1866*e4b17023SJohn Marino return res;
1867*e4b17023SJohn Marino }
1868*e4b17023SJohn Marino
1869*e4b17023SJohn Marino /* Analyzes and returns the scalar evolution of the ssa_name VAR in
1870*e4b17023SJohn Marino LOOP. LOOP is the loop in which the variable is used.
1871*e4b17023SJohn Marino
1872*e4b17023SJohn Marino Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1873*e4b17023SJohn Marino pointer to the statement that uses this variable, in order to
1874*e4b17023SJohn Marino determine the evolution function of the variable, use the following
1875*e4b17023SJohn Marino calls:
1876*e4b17023SJohn Marino
1877*e4b17023SJohn Marino loop_p loop = loop_containing_stmt (stmt);
1878*e4b17023SJohn Marino tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1879*e4b17023SJohn Marino tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1880*e4b17023SJohn Marino */
1881*e4b17023SJohn Marino
1882*e4b17023SJohn Marino tree
analyze_scalar_evolution(struct loop * loop,tree var)1883*e4b17023SJohn Marino analyze_scalar_evolution (struct loop *loop, tree var)
1884*e4b17023SJohn Marino {
1885*e4b17023SJohn Marino tree res;
1886*e4b17023SJohn Marino
1887*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
1888*e4b17023SJohn Marino {
1889*e4b17023SJohn Marino fprintf (dump_file, "(analyze_scalar_evolution \n");
1890*e4b17023SJohn Marino fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
1891*e4b17023SJohn Marino fprintf (dump_file, " (scalar = ");
1892*e4b17023SJohn Marino print_generic_expr (dump_file, var, 0);
1893*e4b17023SJohn Marino fprintf (dump_file, ")\n");
1894*e4b17023SJohn Marino }
1895*e4b17023SJohn Marino
1896*e4b17023SJohn Marino res = get_scalar_evolution (block_before_loop (loop), var);
1897*e4b17023SJohn Marino res = analyze_scalar_evolution_1 (loop, var, res);
1898*e4b17023SJohn Marino
1899*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
1900*e4b17023SJohn Marino fprintf (dump_file, ")\n");
1901*e4b17023SJohn Marino
1902*e4b17023SJohn Marino return res;
1903*e4b17023SJohn Marino }
1904*e4b17023SJohn Marino
1905*e4b17023SJohn Marino /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1906*e4b17023SJohn Marino WRTO_LOOP (which should be a superloop of USE_LOOP)
1907*e4b17023SJohn Marino
1908*e4b17023SJohn Marino FOLDED_CASTS is set to true if resolve_mixers used
1909*e4b17023SJohn Marino chrec_convert_aggressive (TODO -- not really, we are way too conservative
1910*e4b17023SJohn Marino at the moment in order to keep things simple).
1911*e4b17023SJohn Marino
1912*e4b17023SJohn Marino To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1913*e4b17023SJohn Marino example:
1914*e4b17023SJohn Marino
1915*e4b17023SJohn Marino for (i = 0; i < 100; i++) -- loop 1
1916*e4b17023SJohn Marino {
1917*e4b17023SJohn Marino for (j = 0; j < 100; j++) -- loop 2
1918*e4b17023SJohn Marino {
1919*e4b17023SJohn Marino k1 = i;
1920*e4b17023SJohn Marino k2 = j;
1921*e4b17023SJohn Marino
1922*e4b17023SJohn Marino use2 (k1, k2);
1923*e4b17023SJohn Marino
1924*e4b17023SJohn Marino for (t = 0; t < 100; t++) -- loop 3
1925*e4b17023SJohn Marino use3 (k1, k2);
1926*e4b17023SJohn Marino
1927*e4b17023SJohn Marino }
1928*e4b17023SJohn Marino use1 (k1, k2);
1929*e4b17023SJohn Marino }
1930*e4b17023SJohn Marino
1931*e4b17023SJohn Marino Both k1 and k2 are invariants in loop3, thus
1932*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1933*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1934*e4b17023SJohn Marino
1935*e4b17023SJohn Marino As they are invariant, it does not matter whether we consider their
1936*e4b17023SJohn Marino usage in loop 3 or loop 2, hence
1937*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1938*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1939*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1940*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
1941*e4b17023SJohn Marino
1942*e4b17023SJohn Marino Similarly for their evolutions with respect to loop 1. The values of K2
1943*e4b17023SJohn Marino in the use in loop 2 vary independently on loop 1, thus we cannot express
1944*e4b17023SJohn Marino the evolution with respect to loop 1:
1945*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
1946*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
1947*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
1948*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
1949*e4b17023SJohn Marino
1950*e4b17023SJohn Marino The value of k2 in the use in loop 1 is known, though:
1951*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
1952*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
1953*e4b17023SJohn Marino */
1954*e4b17023SJohn Marino
1955*e4b17023SJohn Marino static tree
analyze_scalar_evolution_in_loop(struct loop * wrto_loop,struct loop * use_loop,tree version,bool * folded_casts)1956*e4b17023SJohn Marino analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1957*e4b17023SJohn Marino tree version, bool *folded_casts)
1958*e4b17023SJohn Marino {
1959*e4b17023SJohn Marino bool val = false;
1960*e4b17023SJohn Marino tree ev = version, tmp;
1961*e4b17023SJohn Marino
1962*e4b17023SJohn Marino /* We cannot just do
1963*e4b17023SJohn Marino
1964*e4b17023SJohn Marino tmp = analyze_scalar_evolution (use_loop, version);
1965*e4b17023SJohn Marino ev = resolve_mixers (wrto_loop, tmp);
1966*e4b17023SJohn Marino
1967*e4b17023SJohn Marino as resolve_mixers would query the scalar evolution with respect to
1968*e4b17023SJohn Marino wrto_loop. For example, in the situation described in the function
1969*e4b17023SJohn Marino comment, suppose that wrto_loop = loop1, use_loop = loop3 and
1970*e4b17023SJohn Marino version = k2. Then
1971*e4b17023SJohn Marino
1972*e4b17023SJohn Marino analyze_scalar_evolution (use_loop, version) = k2
1973*e4b17023SJohn Marino
1974*e4b17023SJohn Marino and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
1975*e4b17023SJohn Marino is 100, which is a wrong result, since we are interested in the
1976*e4b17023SJohn Marino value in loop 3.
1977*e4b17023SJohn Marino
1978*e4b17023SJohn Marino Instead, we need to proceed from use_loop to wrto_loop loop by loop,
1979*e4b17023SJohn Marino each time checking that there is no evolution in the inner loop. */
1980*e4b17023SJohn Marino
1981*e4b17023SJohn Marino if (folded_casts)
1982*e4b17023SJohn Marino *folded_casts = false;
1983*e4b17023SJohn Marino while (1)
1984*e4b17023SJohn Marino {
1985*e4b17023SJohn Marino tmp = analyze_scalar_evolution (use_loop, ev);
1986*e4b17023SJohn Marino ev = resolve_mixers (use_loop, tmp);
1987*e4b17023SJohn Marino
1988*e4b17023SJohn Marino if (folded_casts && tmp != ev)
1989*e4b17023SJohn Marino *folded_casts = true;
1990*e4b17023SJohn Marino
1991*e4b17023SJohn Marino if (use_loop == wrto_loop)
1992*e4b17023SJohn Marino return ev;
1993*e4b17023SJohn Marino
1994*e4b17023SJohn Marino /* If the value of the use changes in the inner loop, we cannot express
1995*e4b17023SJohn Marino its value in the outer loop (we might try to return interval chrec,
1996*e4b17023SJohn Marino but we do not have a user for it anyway) */
1997*e4b17023SJohn Marino if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1998*e4b17023SJohn Marino || !val)
1999*e4b17023SJohn Marino return chrec_dont_know;
2000*e4b17023SJohn Marino
2001*e4b17023SJohn Marino use_loop = loop_outer (use_loop);
2002*e4b17023SJohn Marino }
2003*e4b17023SJohn Marino }
2004*e4b17023SJohn Marino
2005*e4b17023SJohn Marino /* Returns from CACHE the value for VERSION instantiated below
2006*e4b17023SJohn Marino INSTANTIATED_BELOW block. */
2007*e4b17023SJohn Marino
2008*e4b17023SJohn Marino static tree
get_instantiated_value(htab_t cache,basic_block instantiated_below,tree version)2009*e4b17023SJohn Marino get_instantiated_value (htab_t cache, basic_block instantiated_below,
2010*e4b17023SJohn Marino tree version)
2011*e4b17023SJohn Marino {
2012*e4b17023SJohn Marino struct scev_info_str *info, pattern;
2013*e4b17023SJohn Marino
2014*e4b17023SJohn Marino pattern.var = version;
2015*e4b17023SJohn Marino pattern.instantiated_below = instantiated_below;
2016*e4b17023SJohn Marino info = (struct scev_info_str *) htab_find (cache, &pattern);
2017*e4b17023SJohn Marino
2018*e4b17023SJohn Marino if (info)
2019*e4b17023SJohn Marino return info->chrec;
2020*e4b17023SJohn Marino else
2021*e4b17023SJohn Marino return NULL_TREE;
2022*e4b17023SJohn Marino }
2023*e4b17023SJohn Marino
2024*e4b17023SJohn Marino /* Sets in CACHE the value of VERSION instantiated below basic block
2025*e4b17023SJohn Marino INSTANTIATED_BELOW to VAL. */
2026*e4b17023SJohn Marino
2027*e4b17023SJohn Marino static void
set_instantiated_value(htab_t cache,basic_block instantiated_below,tree version,tree val)2028*e4b17023SJohn Marino set_instantiated_value (htab_t cache, basic_block instantiated_below,
2029*e4b17023SJohn Marino tree version, tree val)
2030*e4b17023SJohn Marino {
2031*e4b17023SJohn Marino struct scev_info_str *info, pattern;
2032*e4b17023SJohn Marino PTR *slot;
2033*e4b17023SJohn Marino
2034*e4b17023SJohn Marino pattern.var = version;
2035*e4b17023SJohn Marino pattern.instantiated_below = instantiated_below;
2036*e4b17023SJohn Marino slot = htab_find_slot (cache, &pattern, INSERT);
2037*e4b17023SJohn Marino
2038*e4b17023SJohn Marino if (!*slot)
2039*e4b17023SJohn Marino *slot = new_scev_info_str (instantiated_below, version);
2040*e4b17023SJohn Marino info = (struct scev_info_str *) *slot;
2041*e4b17023SJohn Marino info->chrec = val;
2042*e4b17023SJohn Marino }
2043*e4b17023SJohn Marino
2044*e4b17023SJohn Marino /* Return the closed_loop_phi node for VAR. If there is none, return
2045*e4b17023SJohn Marino NULL_TREE. */
2046*e4b17023SJohn Marino
2047*e4b17023SJohn Marino static tree
loop_closed_phi_def(tree var)2048*e4b17023SJohn Marino loop_closed_phi_def (tree var)
2049*e4b17023SJohn Marino {
2050*e4b17023SJohn Marino struct loop *loop;
2051*e4b17023SJohn Marino edge exit;
2052*e4b17023SJohn Marino gimple phi;
2053*e4b17023SJohn Marino gimple_stmt_iterator psi;
2054*e4b17023SJohn Marino
2055*e4b17023SJohn Marino if (var == NULL_TREE
2056*e4b17023SJohn Marino || TREE_CODE (var) != SSA_NAME)
2057*e4b17023SJohn Marino return NULL_TREE;
2058*e4b17023SJohn Marino
2059*e4b17023SJohn Marino loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2060*e4b17023SJohn Marino exit = single_exit (loop);
2061*e4b17023SJohn Marino if (!exit)
2062*e4b17023SJohn Marino return NULL_TREE;
2063*e4b17023SJohn Marino
2064*e4b17023SJohn Marino for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2065*e4b17023SJohn Marino {
2066*e4b17023SJohn Marino phi = gsi_stmt (psi);
2067*e4b17023SJohn Marino if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2068*e4b17023SJohn Marino return PHI_RESULT (phi);
2069*e4b17023SJohn Marino }
2070*e4b17023SJohn Marino
2071*e4b17023SJohn Marino return NULL_TREE;
2072*e4b17023SJohn Marino }
2073*e4b17023SJohn Marino
2074*e4b17023SJohn Marino static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
2075*e4b17023SJohn Marino htab_t, int);
2076*e4b17023SJohn Marino
2077*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2078*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2079*e4b17023SJohn Marino
2080*e4b17023SJohn Marino CHREC is an SSA_NAME to be instantiated.
2081*e4b17023SJohn Marino
2082*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2083*e4b17023SJohn Marino
2084*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2085*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2086*e4b17023SJohn Marino the chrec is preserved.
2087*e4b17023SJohn Marino
2088*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2089*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2090*e4b17023SJohn Marino
2091*e4b17023SJohn Marino static tree
instantiate_scev_name(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2092*e4b17023SJohn Marino instantiate_scev_name (basic_block instantiate_below,
2093*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2094*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2095*e4b17023SJohn Marino {
2096*e4b17023SJohn Marino tree res;
2097*e4b17023SJohn Marino struct loop *def_loop;
2098*e4b17023SJohn Marino basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2099*e4b17023SJohn Marino
2100*e4b17023SJohn Marino /* A parameter (or loop invariant and we do not want to include
2101*e4b17023SJohn Marino evolutions in outer loops), nothing to do. */
2102*e4b17023SJohn Marino if (!def_bb
2103*e4b17023SJohn Marino || loop_depth (def_bb->loop_father) == 0
2104*e4b17023SJohn Marino || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2105*e4b17023SJohn Marino return chrec;
2106*e4b17023SJohn Marino
2107*e4b17023SJohn Marino /* We cache the value of instantiated variable to avoid exponential
2108*e4b17023SJohn Marino time complexity due to reevaluations. We also store the convenient
2109*e4b17023SJohn Marino value in the cache in order to prevent infinite recursion -- we do
2110*e4b17023SJohn Marino not want to instantiate the SSA_NAME if it is in a mixer
2111*e4b17023SJohn Marino structure. This is used for avoiding the instantiation of
2112*e4b17023SJohn Marino recursively defined functions, such as:
2113*e4b17023SJohn Marino
2114*e4b17023SJohn Marino | a_2 -> {0, +, 1, +, a_2}_1 */
2115*e4b17023SJohn Marino
2116*e4b17023SJohn Marino res = get_instantiated_value (cache, instantiate_below, chrec);
2117*e4b17023SJohn Marino if (res)
2118*e4b17023SJohn Marino return res;
2119*e4b17023SJohn Marino
2120*e4b17023SJohn Marino res = chrec_dont_know;
2121*e4b17023SJohn Marino set_instantiated_value (cache, instantiate_below, chrec, res);
2122*e4b17023SJohn Marino
2123*e4b17023SJohn Marino def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2124*e4b17023SJohn Marino
2125*e4b17023SJohn Marino /* If the analysis yields a parametric chrec, instantiate the
2126*e4b17023SJohn Marino result again. */
2127*e4b17023SJohn Marino res = analyze_scalar_evolution (def_loop, chrec);
2128*e4b17023SJohn Marino
2129*e4b17023SJohn Marino /* Don't instantiate default definitions. */
2130*e4b17023SJohn Marino if (TREE_CODE (res) == SSA_NAME
2131*e4b17023SJohn Marino && SSA_NAME_IS_DEFAULT_DEF (res))
2132*e4b17023SJohn Marino ;
2133*e4b17023SJohn Marino
2134*e4b17023SJohn Marino /* Don't instantiate loop-closed-ssa phi nodes. */
2135*e4b17023SJohn Marino else if (TREE_CODE (res) == SSA_NAME
2136*e4b17023SJohn Marino && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2137*e4b17023SJohn Marino > loop_depth (def_loop))
2138*e4b17023SJohn Marino {
2139*e4b17023SJohn Marino if (res == chrec)
2140*e4b17023SJohn Marino res = loop_closed_phi_def (chrec);
2141*e4b17023SJohn Marino else
2142*e4b17023SJohn Marino res = chrec;
2143*e4b17023SJohn Marino
2144*e4b17023SJohn Marino /* When there is no loop_closed_phi_def, it means that the
2145*e4b17023SJohn Marino variable is not used after the loop: try to still compute the
2146*e4b17023SJohn Marino value of the variable when exiting the loop. */
2147*e4b17023SJohn Marino if (res == NULL_TREE)
2148*e4b17023SJohn Marino {
2149*e4b17023SJohn Marino loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2150*e4b17023SJohn Marino res = analyze_scalar_evolution (loop, chrec);
2151*e4b17023SJohn Marino res = compute_overall_effect_of_inner_loop (loop, res);
2152*e4b17023SJohn Marino res = instantiate_scev_r (instantiate_below, evolution_loop, res,
2153*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2154*e4b17023SJohn Marino }
2155*e4b17023SJohn Marino else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2156*e4b17023SJohn Marino gimple_bb (SSA_NAME_DEF_STMT (res))))
2157*e4b17023SJohn Marino res = chrec_dont_know;
2158*e4b17023SJohn Marino }
2159*e4b17023SJohn Marino
2160*e4b17023SJohn Marino else if (res != chrec_dont_know)
2161*e4b17023SJohn Marino res = instantiate_scev_r (instantiate_below, evolution_loop, res,
2162*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2163*e4b17023SJohn Marino
2164*e4b17023SJohn Marino /* Store the correct value to the cache. */
2165*e4b17023SJohn Marino set_instantiated_value (cache, instantiate_below, chrec, res);
2166*e4b17023SJohn Marino return res;
2167*e4b17023SJohn Marino }
2168*e4b17023SJohn Marino
2169*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2170*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2171*e4b17023SJohn Marino
2172*e4b17023SJohn Marino CHREC is a polynomial chain of recurrence to be instantiated.
2173*e4b17023SJohn Marino
2174*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2175*e4b17023SJohn Marino
2176*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2177*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2178*e4b17023SJohn Marino the chrec is preserved.
2179*e4b17023SJohn Marino
2180*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2181*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2182*e4b17023SJohn Marino
2183*e4b17023SJohn Marino static tree
instantiate_scev_poly(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2184*e4b17023SJohn Marino instantiate_scev_poly (basic_block instantiate_below,
2185*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2186*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2187*e4b17023SJohn Marino {
2188*e4b17023SJohn Marino tree op1;
2189*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2190*e4b17023SJohn Marino CHREC_LEFT (chrec), fold_conversions, cache,
2191*e4b17023SJohn Marino size_expr);
2192*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2193*e4b17023SJohn Marino return chrec_dont_know;
2194*e4b17023SJohn Marino
2195*e4b17023SJohn Marino op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2196*e4b17023SJohn Marino CHREC_RIGHT (chrec), fold_conversions, cache,
2197*e4b17023SJohn Marino size_expr);
2198*e4b17023SJohn Marino if (op1 == chrec_dont_know)
2199*e4b17023SJohn Marino return chrec_dont_know;
2200*e4b17023SJohn Marino
2201*e4b17023SJohn Marino if (CHREC_LEFT (chrec) != op0
2202*e4b17023SJohn Marino || CHREC_RIGHT (chrec) != op1)
2203*e4b17023SJohn Marino {
2204*e4b17023SJohn Marino unsigned var = CHREC_VARIABLE (chrec);
2205*e4b17023SJohn Marino
2206*e4b17023SJohn Marino /* When the instantiated stride or base has an evolution in an
2207*e4b17023SJohn Marino innermost loop, return chrec_dont_know, as this is not a
2208*e4b17023SJohn Marino valid SCEV representation. In the reduced testcase for
2209*e4b17023SJohn Marino PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2210*e4b17023SJohn Marino meaning. */
2211*e4b17023SJohn Marino if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var)
2212*e4b17023SJohn Marino || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var))
2213*e4b17023SJohn Marino return chrec_dont_know;
2214*e4b17023SJohn Marino
2215*e4b17023SJohn Marino op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2216*e4b17023SJohn Marino chrec = build_polynomial_chrec (var, op0, op1);
2217*e4b17023SJohn Marino }
2218*e4b17023SJohn Marino
2219*e4b17023SJohn Marino return chrec;
2220*e4b17023SJohn Marino }
2221*e4b17023SJohn Marino
2222*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2223*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2224*e4b17023SJohn Marino
2225*e4b17023SJohn Marino "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2226*e4b17023SJohn Marino
2227*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2228*e4b17023SJohn Marino
2229*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2230*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2231*e4b17023SJohn Marino the chrec is preserved.
2232*e4b17023SJohn Marino
2233*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2234*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2235*e4b17023SJohn Marino
2236*e4b17023SJohn Marino static tree
instantiate_scev_binary(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,enum tree_code code,tree type,tree c0,tree c1,bool fold_conversions,htab_t cache,int size_expr)2237*e4b17023SJohn Marino instantiate_scev_binary (basic_block instantiate_below,
2238*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec, enum tree_code code,
2239*e4b17023SJohn Marino tree type, tree c0, tree c1,
2240*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2241*e4b17023SJohn Marino {
2242*e4b17023SJohn Marino tree op1;
2243*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2244*e4b17023SJohn Marino c0, fold_conversions, cache,
2245*e4b17023SJohn Marino size_expr);
2246*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2247*e4b17023SJohn Marino return chrec_dont_know;
2248*e4b17023SJohn Marino
2249*e4b17023SJohn Marino op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2250*e4b17023SJohn Marino c1, fold_conversions, cache,
2251*e4b17023SJohn Marino size_expr);
2252*e4b17023SJohn Marino if (op1 == chrec_dont_know)
2253*e4b17023SJohn Marino return chrec_dont_know;
2254*e4b17023SJohn Marino
2255*e4b17023SJohn Marino if (c0 != op0
2256*e4b17023SJohn Marino || c1 != op1)
2257*e4b17023SJohn Marino {
2258*e4b17023SJohn Marino op0 = chrec_convert (type, op0, NULL);
2259*e4b17023SJohn Marino op1 = chrec_convert_rhs (type, op1, NULL);
2260*e4b17023SJohn Marino
2261*e4b17023SJohn Marino switch (code)
2262*e4b17023SJohn Marino {
2263*e4b17023SJohn Marino case POINTER_PLUS_EXPR:
2264*e4b17023SJohn Marino case PLUS_EXPR:
2265*e4b17023SJohn Marino return chrec_fold_plus (type, op0, op1);
2266*e4b17023SJohn Marino
2267*e4b17023SJohn Marino case MINUS_EXPR:
2268*e4b17023SJohn Marino return chrec_fold_minus (type, op0, op1);
2269*e4b17023SJohn Marino
2270*e4b17023SJohn Marino case MULT_EXPR:
2271*e4b17023SJohn Marino return chrec_fold_multiply (type, op0, op1);
2272*e4b17023SJohn Marino
2273*e4b17023SJohn Marino default:
2274*e4b17023SJohn Marino gcc_unreachable ();
2275*e4b17023SJohn Marino }
2276*e4b17023SJohn Marino }
2277*e4b17023SJohn Marino
2278*e4b17023SJohn Marino return chrec ? chrec : fold_build2 (code, type, c0, c1);
2279*e4b17023SJohn Marino }
2280*e4b17023SJohn Marino
2281*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2282*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2283*e4b17023SJohn Marino
2284*e4b17023SJohn Marino "CHREC" is an array reference to be instantiated.
2285*e4b17023SJohn Marino
2286*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2287*e4b17023SJohn Marino
2288*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2289*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2290*e4b17023SJohn Marino the chrec is preserved.
2291*e4b17023SJohn Marino
2292*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2293*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2294*e4b17023SJohn Marino
2295*e4b17023SJohn Marino static tree
instantiate_array_ref(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2296*e4b17023SJohn Marino instantiate_array_ref (basic_block instantiate_below,
2297*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2298*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2299*e4b17023SJohn Marino {
2300*e4b17023SJohn Marino tree res;
2301*e4b17023SJohn Marino tree index = TREE_OPERAND (chrec, 1);
2302*e4b17023SJohn Marino tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index,
2303*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2304*e4b17023SJohn Marino
2305*e4b17023SJohn Marino if (op1 == chrec_dont_know)
2306*e4b17023SJohn Marino return chrec_dont_know;
2307*e4b17023SJohn Marino
2308*e4b17023SJohn Marino if (chrec && op1 == index)
2309*e4b17023SJohn Marino return chrec;
2310*e4b17023SJohn Marino
2311*e4b17023SJohn Marino res = unshare_expr (chrec);
2312*e4b17023SJohn Marino TREE_OPERAND (res, 1) = op1;
2313*e4b17023SJohn Marino return res;
2314*e4b17023SJohn Marino }
2315*e4b17023SJohn Marino
2316*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2317*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2318*e4b17023SJohn Marino
2319*e4b17023SJohn Marino "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2320*e4b17023SJohn Marino instantiated.
2321*e4b17023SJohn Marino
2322*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2323*e4b17023SJohn Marino
2324*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2325*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2326*e4b17023SJohn Marino the chrec is preserved.
2327*e4b17023SJohn Marino
2328*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2329*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2330*e4b17023SJohn Marino
2331*e4b17023SJohn Marino static tree
instantiate_scev_convert(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,tree type,tree op,bool fold_conversions,htab_t cache,int size_expr)2332*e4b17023SJohn Marino instantiate_scev_convert (basic_block instantiate_below,
2333*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2334*e4b17023SJohn Marino tree type, tree op,
2335*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2336*e4b17023SJohn Marino {
2337*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2338*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2339*e4b17023SJohn Marino
2340*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2341*e4b17023SJohn Marino return chrec_dont_know;
2342*e4b17023SJohn Marino
2343*e4b17023SJohn Marino if (fold_conversions)
2344*e4b17023SJohn Marino {
2345*e4b17023SJohn Marino tree tmp = chrec_convert_aggressive (type, op0);
2346*e4b17023SJohn Marino if (tmp)
2347*e4b17023SJohn Marino return tmp;
2348*e4b17023SJohn Marino }
2349*e4b17023SJohn Marino
2350*e4b17023SJohn Marino if (chrec && op0 == op)
2351*e4b17023SJohn Marino return chrec;
2352*e4b17023SJohn Marino
2353*e4b17023SJohn Marino /* If we used chrec_convert_aggressive, we can no longer assume that
2354*e4b17023SJohn Marino signed chrecs do not overflow, as chrec_convert does, so avoid
2355*e4b17023SJohn Marino calling it in that case. */
2356*e4b17023SJohn Marino if (fold_conversions)
2357*e4b17023SJohn Marino return fold_convert (type, op0);
2358*e4b17023SJohn Marino
2359*e4b17023SJohn Marino return chrec_convert (type, op0, NULL);
2360*e4b17023SJohn Marino }
2361*e4b17023SJohn Marino
2362*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2363*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2364*e4b17023SJohn Marino
2365*e4b17023SJohn Marino CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2366*e4b17023SJohn Marino Handle ~X as -1 - X.
2367*e4b17023SJohn Marino Handle -X as -1 * X.
2368*e4b17023SJohn Marino
2369*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2370*e4b17023SJohn Marino
2371*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2372*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2373*e4b17023SJohn Marino the chrec is preserved.
2374*e4b17023SJohn Marino
2375*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2376*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2377*e4b17023SJohn Marino
2378*e4b17023SJohn Marino static tree
instantiate_scev_not(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,enum tree_code code,tree type,tree op,bool fold_conversions,htab_t cache,int size_expr)2379*e4b17023SJohn Marino instantiate_scev_not (basic_block instantiate_below,
2380*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2381*e4b17023SJohn Marino enum tree_code code, tree type, tree op,
2382*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2383*e4b17023SJohn Marino {
2384*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2385*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2386*e4b17023SJohn Marino
2387*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2388*e4b17023SJohn Marino return chrec_dont_know;
2389*e4b17023SJohn Marino
2390*e4b17023SJohn Marino if (op != op0)
2391*e4b17023SJohn Marino {
2392*e4b17023SJohn Marino op0 = chrec_convert (type, op0, NULL);
2393*e4b17023SJohn Marino
2394*e4b17023SJohn Marino switch (code)
2395*e4b17023SJohn Marino {
2396*e4b17023SJohn Marino case BIT_NOT_EXPR:
2397*e4b17023SJohn Marino return chrec_fold_minus
2398*e4b17023SJohn Marino (type, fold_convert (type, integer_minus_one_node), op0);
2399*e4b17023SJohn Marino
2400*e4b17023SJohn Marino case NEGATE_EXPR:
2401*e4b17023SJohn Marino return chrec_fold_multiply
2402*e4b17023SJohn Marino (type, fold_convert (type, integer_minus_one_node), op0);
2403*e4b17023SJohn Marino
2404*e4b17023SJohn Marino default:
2405*e4b17023SJohn Marino gcc_unreachable ();
2406*e4b17023SJohn Marino }
2407*e4b17023SJohn Marino }
2408*e4b17023SJohn Marino
2409*e4b17023SJohn Marino return chrec ? chrec : fold_build1 (code, type, op0);
2410*e4b17023SJohn Marino }
2411*e4b17023SJohn Marino
2412*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2413*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2414*e4b17023SJohn Marino
2415*e4b17023SJohn Marino CHREC is an expression with 3 operands to be instantiated.
2416*e4b17023SJohn Marino
2417*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2418*e4b17023SJohn Marino
2419*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2420*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2421*e4b17023SJohn Marino the chrec is preserved.
2422*e4b17023SJohn Marino
2423*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2424*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2425*e4b17023SJohn Marino
2426*e4b17023SJohn Marino static tree
instantiate_scev_3(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2427*e4b17023SJohn Marino instantiate_scev_3 (basic_block instantiate_below,
2428*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2429*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2430*e4b17023SJohn Marino {
2431*e4b17023SJohn Marino tree op1, op2;
2432*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2433*e4b17023SJohn Marino TREE_OPERAND (chrec, 0),
2434*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2435*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2436*e4b17023SJohn Marino return chrec_dont_know;
2437*e4b17023SJohn Marino
2438*e4b17023SJohn Marino op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2439*e4b17023SJohn Marino TREE_OPERAND (chrec, 1),
2440*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2441*e4b17023SJohn Marino if (op1 == chrec_dont_know)
2442*e4b17023SJohn Marino return chrec_dont_know;
2443*e4b17023SJohn Marino
2444*e4b17023SJohn Marino op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2445*e4b17023SJohn Marino TREE_OPERAND (chrec, 2),
2446*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2447*e4b17023SJohn Marino if (op2 == chrec_dont_know)
2448*e4b17023SJohn Marino return chrec_dont_know;
2449*e4b17023SJohn Marino
2450*e4b17023SJohn Marino if (op0 == TREE_OPERAND (chrec, 0)
2451*e4b17023SJohn Marino && op1 == TREE_OPERAND (chrec, 1)
2452*e4b17023SJohn Marino && op2 == TREE_OPERAND (chrec, 2))
2453*e4b17023SJohn Marino return chrec;
2454*e4b17023SJohn Marino
2455*e4b17023SJohn Marino return fold_build3 (TREE_CODE (chrec),
2456*e4b17023SJohn Marino TREE_TYPE (chrec), op0, op1, op2);
2457*e4b17023SJohn Marino }
2458*e4b17023SJohn Marino
2459*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2460*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2461*e4b17023SJohn Marino
2462*e4b17023SJohn Marino CHREC is an expression with 2 operands to be instantiated.
2463*e4b17023SJohn Marino
2464*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2465*e4b17023SJohn Marino
2466*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2467*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2468*e4b17023SJohn Marino the chrec is preserved.
2469*e4b17023SJohn Marino
2470*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2471*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2472*e4b17023SJohn Marino
2473*e4b17023SJohn Marino static tree
instantiate_scev_2(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2474*e4b17023SJohn Marino instantiate_scev_2 (basic_block instantiate_below,
2475*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2476*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2477*e4b17023SJohn Marino {
2478*e4b17023SJohn Marino tree op1;
2479*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2480*e4b17023SJohn Marino TREE_OPERAND (chrec, 0),
2481*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2482*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2483*e4b17023SJohn Marino return chrec_dont_know;
2484*e4b17023SJohn Marino
2485*e4b17023SJohn Marino op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2486*e4b17023SJohn Marino TREE_OPERAND (chrec, 1),
2487*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2488*e4b17023SJohn Marino if (op1 == chrec_dont_know)
2489*e4b17023SJohn Marino return chrec_dont_know;
2490*e4b17023SJohn Marino
2491*e4b17023SJohn Marino if (op0 == TREE_OPERAND (chrec, 0)
2492*e4b17023SJohn Marino && op1 == TREE_OPERAND (chrec, 1))
2493*e4b17023SJohn Marino return chrec;
2494*e4b17023SJohn Marino
2495*e4b17023SJohn Marino return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2496*e4b17023SJohn Marino }
2497*e4b17023SJohn Marino
2498*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2499*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2500*e4b17023SJohn Marino
2501*e4b17023SJohn Marino CHREC is an expression with 2 operands to be instantiated.
2502*e4b17023SJohn Marino
2503*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2504*e4b17023SJohn Marino
2505*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2506*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2507*e4b17023SJohn Marino the chrec is preserved.
2508*e4b17023SJohn Marino
2509*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2510*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2511*e4b17023SJohn Marino
2512*e4b17023SJohn Marino static tree
instantiate_scev_1(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2513*e4b17023SJohn Marino instantiate_scev_1 (basic_block instantiate_below,
2514*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2515*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2516*e4b17023SJohn Marino {
2517*e4b17023SJohn Marino tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2518*e4b17023SJohn Marino TREE_OPERAND (chrec, 0),
2519*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2520*e4b17023SJohn Marino
2521*e4b17023SJohn Marino if (op0 == chrec_dont_know)
2522*e4b17023SJohn Marino return chrec_dont_know;
2523*e4b17023SJohn Marino
2524*e4b17023SJohn Marino if (op0 == TREE_OPERAND (chrec, 0))
2525*e4b17023SJohn Marino return chrec;
2526*e4b17023SJohn Marino
2527*e4b17023SJohn Marino return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2528*e4b17023SJohn Marino }
2529*e4b17023SJohn Marino
2530*e4b17023SJohn Marino /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2531*e4b17023SJohn Marino and EVOLUTION_LOOP, that were left under a symbolic form.
2532*e4b17023SJohn Marino
2533*e4b17023SJohn Marino CHREC is the scalar evolution to instantiate.
2534*e4b17023SJohn Marino
2535*e4b17023SJohn Marino CACHE is the cache of already instantiated values.
2536*e4b17023SJohn Marino
2537*e4b17023SJohn Marino FOLD_CONVERSIONS should be set to true when the conversions that
2538*e4b17023SJohn Marino may wrap in signed/pointer type are folded, as long as the value of
2539*e4b17023SJohn Marino the chrec is preserved.
2540*e4b17023SJohn Marino
2541*e4b17023SJohn Marino SIZE_EXPR is used for computing the size of the expression to be
2542*e4b17023SJohn Marino instantiated, and to stop if it exceeds some limit. */
2543*e4b17023SJohn Marino
2544*e4b17023SJohn Marino static tree
instantiate_scev_r(basic_block instantiate_below,struct loop * evolution_loop,tree chrec,bool fold_conversions,htab_t cache,int size_expr)2545*e4b17023SJohn Marino instantiate_scev_r (basic_block instantiate_below,
2546*e4b17023SJohn Marino struct loop *evolution_loop, tree chrec,
2547*e4b17023SJohn Marino bool fold_conversions, htab_t cache, int size_expr)
2548*e4b17023SJohn Marino {
2549*e4b17023SJohn Marino /* Give up if the expression is larger than the MAX that we allow. */
2550*e4b17023SJohn Marino if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2551*e4b17023SJohn Marino return chrec_dont_know;
2552*e4b17023SJohn Marino
2553*e4b17023SJohn Marino if (chrec == NULL_TREE
2554*e4b17023SJohn Marino || automatically_generated_chrec_p (chrec)
2555*e4b17023SJohn Marino || is_gimple_min_invariant (chrec))
2556*e4b17023SJohn Marino return chrec;
2557*e4b17023SJohn Marino
2558*e4b17023SJohn Marino switch (TREE_CODE (chrec))
2559*e4b17023SJohn Marino {
2560*e4b17023SJohn Marino case SSA_NAME:
2561*e4b17023SJohn Marino return instantiate_scev_name (instantiate_below, evolution_loop, chrec,
2562*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2563*e4b17023SJohn Marino
2564*e4b17023SJohn Marino case POLYNOMIAL_CHREC:
2565*e4b17023SJohn Marino return instantiate_scev_poly (instantiate_below, evolution_loop, chrec,
2566*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2567*e4b17023SJohn Marino
2568*e4b17023SJohn Marino case POINTER_PLUS_EXPR:
2569*e4b17023SJohn Marino case PLUS_EXPR:
2570*e4b17023SJohn Marino case MINUS_EXPR:
2571*e4b17023SJohn Marino case MULT_EXPR:
2572*e4b17023SJohn Marino return instantiate_scev_binary (instantiate_below, evolution_loop, chrec,
2573*e4b17023SJohn Marino TREE_CODE (chrec), chrec_type (chrec),
2574*e4b17023SJohn Marino TREE_OPERAND (chrec, 0),
2575*e4b17023SJohn Marino TREE_OPERAND (chrec, 1),
2576*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2577*e4b17023SJohn Marino
2578*e4b17023SJohn Marino CASE_CONVERT:
2579*e4b17023SJohn Marino return instantiate_scev_convert (instantiate_below, evolution_loop, chrec,
2580*e4b17023SJohn Marino TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2581*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2582*e4b17023SJohn Marino
2583*e4b17023SJohn Marino case NEGATE_EXPR:
2584*e4b17023SJohn Marino case BIT_NOT_EXPR:
2585*e4b17023SJohn Marino return instantiate_scev_not (instantiate_below, evolution_loop, chrec,
2586*e4b17023SJohn Marino TREE_CODE (chrec), TREE_TYPE (chrec),
2587*e4b17023SJohn Marino TREE_OPERAND (chrec, 0),
2588*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2589*e4b17023SJohn Marino
2590*e4b17023SJohn Marino case ADDR_EXPR:
2591*e4b17023SJohn Marino case SCEV_NOT_KNOWN:
2592*e4b17023SJohn Marino return chrec_dont_know;
2593*e4b17023SJohn Marino
2594*e4b17023SJohn Marino case SCEV_KNOWN:
2595*e4b17023SJohn Marino return chrec_known;
2596*e4b17023SJohn Marino
2597*e4b17023SJohn Marino case ARRAY_REF:
2598*e4b17023SJohn Marino return instantiate_array_ref (instantiate_below, evolution_loop, chrec,
2599*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2600*e4b17023SJohn Marino
2601*e4b17023SJohn Marino default:
2602*e4b17023SJohn Marino break;
2603*e4b17023SJohn Marino }
2604*e4b17023SJohn Marino
2605*e4b17023SJohn Marino if (VL_EXP_CLASS_P (chrec))
2606*e4b17023SJohn Marino return chrec_dont_know;
2607*e4b17023SJohn Marino
2608*e4b17023SJohn Marino switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2609*e4b17023SJohn Marino {
2610*e4b17023SJohn Marino case 3:
2611*e4b17023SJohn Marino return instantiate_scev_3 (instantiate_below, evolution_loop, chrec,
2612*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2613*e4b17023SJohn Marino
2614*e4b17023SJohn Marino case 2:
2615*e4b17023SJohn Marino return instantiate_scev_2 (instantiate_below, evolution_loop, chrec,
2616*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2617*e4b17023SJohn Marino
2618*e4b17023SJohn Marino case 1:
2619*e4b17023SJohn Marino return instantiate_scev_1 (instantiate_below, evolution_loop, chrec,
2620*e4b17023SJohn Marino fold_conversions, cache, size_expr);
2621*e4b17023SJohn Marino
2622*e4b17023SJohn Marino case 0:
2623*e4b17023SJohn Marino return chrec;
2624*e4b17023SJohn Marino
2625*e4b17023SJohn Marino default:
2626*e4b17023SJohn Marino break;
2627*e4b17023SJohn Marino }
2628*e4b17023SJohn Marino
2629*e4b17023SJohn Marino /* Too complicated to handle. */
2630*e4b17023SJohn Marino return chrec_dont_know;
2631*e4b17023SJohn Marino }
2632*e4b17023SJohn Marino
2633*e4b17023SJohn Marino /* Analyze all the parameters of the chrec that were left under a
2634*e4b17023SJohn Marino symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2635*e4b17023SJohn Marino recursive instantiation of parameters: a parameter is a variable
2636*e4b17023SJohn Marino that is defined in a basic block that dominates INSTANTIATE_BELOW or
2637*e4b17023SJohn Marino a function parameter. */
2638*e4b17023SJohn Marino
2639*e4b17023SJohn Marino tree
instantiate_scev(basic_block instantiate_below,struct loop * evolution_loop,tree chrec)2640*e4b17023SJohn Marino instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2641*e4b17023SJohn Marino tree chrec)
2642*e4b17023SJohn Marino {
2643*e4b17023SJohn Marino tree res;
2644*e4b17023SJohn Marino htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2645*e4b17023SJohn Marino
2646*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
2647*e4b17023SJohn Marino {
2648*e4b17023SJohn Marino fprintf (dump_file, "(instantiate_scev \n");
2649*e4b17023SJohn Marino fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
2650*e4b17023SJohn Marino fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2651*e4b17023SJohn Marino fprintf (dump_file, " (chrec = ");
2652*e4b17023SJohn Marino print_generic_expr (dump_file, chrec, 0);
2653*e4b17023SJohn Marino fprintf (dump_file, ")\n");
2654*e4b17023SJohn Marino }
2655*e4b17023SJohn Marino
2656*e4b17023SJohn Marino res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false,
2657*e4b17023SJohn Marino cache, 0);
2658*e4b17023SJohn Marino
2659*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
2660*e4b17023SJohn Marino {
2661*e4b17023SJohn Marino fprintf (dump_file, " (res = ");
2662*e4b17023SJohn Marino print_generic_expr (dump_file, res, 0);
2663*e4b17023SJohn Marino fprintf (dump_file, "))\n");
2664*e4b17023SJohn Marino }
2665*e4b17023SJohn Marino
2666*e4b17023SJohn Marino htab_delete (cache);
2667*e4b17023SJohn Marino
2668*e4b17023SJohn Marino return res;
2669*e4b17023SJohn Marino }
2670*e4b17023SJohn Marino
2671*e4b17023SJohn Marino /* Similar to instantiate_parameters, but does not introduce the
2672*e4b17023SJohn Marino evolutions in outer loops for LOOP invariants in CHREC, and does not
2673*e4b17023SJohn Marino care about causing overflows, as long as they do not affect value
2674*e4b17023SJohn Marino of an expression. */
2675*e4b17023SJohn Marino
2676*e4b17023SJohn Marino tree
resolve_mixers(struct loop * loop,tree chrec)2677*e4b17023SJohn Marino resolve_mixers (struct loop *loop, tree chrec)
2678*e4b17023SJohn Marino {
2679*e4b17023SJohn Marino htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2680*e4b17023SJohn Marino tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true,
2681*e4b17023SJohn Marino cache, 0);
2682*e4b17023SJohn Marino htab_delete (cache);
2683*e4b17023SJohn Marino return ret;
2684*e4b17023SJohn Marino }
2685*e4b17023SJohn Marino
2686*e4b17023SJohn Marino /* Entry point for the analysis of the number of iterations pass.
2687*e4b17023SJohn Marino This function tries to safely approximate the number of iterations
2688*e4b17023SJohn Marino the loop will run. When this property is not decidable at compile
2689*e4b17023SJohn Marino time, the result is chrec_dont_know. Otherwise the result is a
2690*e4b17023SJohn Marino scalar or a symbolic parameter. When the number of iterations may
2691*e4b17023SJohn Marino be equal to zero and the property cannot be determined at compile
2692*e4b17023SJohn Marino time, the result is a COND_EXPR that represents in a symbolic form
2693*e4b17023SJohn Marino the conditions under which the number of iterations is not zero.
2694*e4b17023SJohn Marino
2695*e4b17023SJohn Marino Example of analysis: suppose that the loop has an exit condition:
2696*e4b17023SJohn Marino
2697*e4b17023SJohn Marino "if (b > 49) goto end_loop;"
2698*e4b17023SJohn Marino
2699*e4b17023SJohn Marino and that in a previous analysis we have determined that the
2700*e4b17023SJohn Marino variable 'b' has an evolution function:
2701*e4b17023SJohn Marino
2702*e4b17023SJohn Marino "EF = {23, +, 5}_2".
2703*e4b17023SJohn Marino
2704*e4b17023SJohn Marino When we evaluate the function at the point 5, i.e. the value of the
2705*e4b17023SJohn Marino variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2706*e4b17023SJohn Marino and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2707*e4b17023SJohn Marino the loop body has been executed 6 times. */
2708*e4b17023SJohn Marino
2709*e4b17023SJohn Marino tree
number_of_latch_executions(struct loop * loop)2710*e4b17023SJohn Marino number_of_latch_executions (struct loop *loop)
2711*e4b17023SJohn Marino {
2712*e4b17023SJohn Marino edge exit;
2713*e4b17023SJohn Marino struct tree_niter_desc niter_desc;
2714*e4b17023SJohn Marino tree may_be_zero;
2715*e4b17023SJohn Marino tree res;
2716*e4b17023SJohn Marino
2717*e4b17023SJohn Marino /* Determine whether the number of iterations in loop has already
2718*e4b17023SJohn Marino been computed. */
2719*e4b17023SJohn Marino res = loop->nb_iterations;
2720*e4b17023SJohn Marino if (res)
2721*e4b17023SJohn Marino return res;
2722*e4b17023SJohn Marino
2723*e4b17023SJohn Marino may_be_zero = NULL_TREE;
2724*e4b17023SJohn Marino
2725*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
2726*e4b17023SJohn Marino fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2727*e4b17023SJohn Marino
2728*e4b17023SJohn Marino res = chrec_dont_know;
2729*e4b17023SJohn Marino exit = single_exit (loop);
2730*e4b17023SJohn Marino
2731*e4b17023SJohn Marino if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2732*e4b17023SJohn Marino {
2733*e4b17023SJohn Marino may_be_zero = niter_desc.may_be_zero;
2734*e4b17023SJohn Marino res = niter_desc.niter;
2735*e4b17023SJohn Marino }
2736*e4b17023SJohn Marino
2737*e4b17023SJohn Marino if (res == chrec_dont_know
2738*e4b17023SJohn Marino || !may_be_zero
2739*e4b17023SJohn Marino || integer_zerop (may_be_zero))
2740*e4b17023SJohn Marino ;
2741*e4b17023SJohn Marino else if (integer_nonzerop (may_be_zero))
2742*e4b17023SJohn Marino res = build_int_cst (TREE_TYPE (res), 0);
2743*e4b17023SJohn Marino
2744*e4b17023SJohn Marino else if (COMPARISON_CLASS_P (may_be_zero))
2745*e4b17023SJohn Marino res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2746*e4b17023SJohn Marino build_int_cst (TREE_TYPE (res), 0), res);
2747*e4b17023SJohn Marino else
2748*e4b17023SJohn Marino res = chrec_dont_know;
2749*e4b17023SJohn Marino
2750*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_SCEV))
2751*e4b17023SJohn Marino {
2752*e4b17023SJohn Marino fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2753*e4b17023SJohn Marino print_generic_expr (dump_file, res, 0);
2754*e4b17023SJohn Marino fprintf (dump_file, "))\n");
2755*e4b17023SJohn Marino }
2756*e4b17023SJohn Marino
2757*e4b17023SJohn Marino loop->nb_iterations = res;
2758*e4b17023SJohn Marino return res;
2759*e4b17023SJohn Marino }
2760*e4b17023SJohn Marino
2761*e4b17023SJohn Marino /* Returns the number of executions of the exit condition of LOOP,
2762*e4b17023SJohn Marino i.e., the number by one higher than number_of_latch_executions.
2763*e4b17023SJohn Marino Note that unlike number_of_latch_executions, this number does
2764*e4b17023SJohn Marino not necessarily fit in the unsigned variant of the type of
2765*e4b17023SJohn Marino the control variable -- if the number of iterations is a constant,
2766*e4b17023SJohn Marino we return chrec_dont_know if adding one to number_of_latch_executions
2767*e4b17023SJohn Marino overflows; however, in case the number of iterations is symbolic
2768*e4b17023SJohn Marino expression, the caller is responsible for dealing with this
2769*e4b17023SJohn Marino the possible overflow. */
2770*e4b17023SJohn Marino
2771*e4b17023SJohn Marino tree
number_of_exit_cond_executions(struct loop * loop)2772*e4b17023SJohn Marino number_of_exit_cond_executions (struct loop *loop)
2773*e4b17023SJohn Marino {
2774*e4b17023SJohn Marino tree ret = number_of_latch_executions (loop);
2775*e4b17023SJohn Marino tree type = chrec_type (ret);
2776*e4b17023SJohn Marino
2777*e4b17023SJohn Marino if (chrec_contains_undetermined (ret))
2778*e4b17023SJohn Marino return ret;
2779*e4b17023SJohn Marino
2780*e4b17023SJohn Marino ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2781*e4b17023SJohn Marino if (TREE_CODE (ret) == INTEGER_CST
2782*e4b17023SJohn Marino && TREE_OVERFLOW (ret))
2783*e4b17023SJohn Marino return chrec_dont_know;
2784*e4b17023SJohn Marino
2785*e4b17023SJohn Marino return ret;
2786*e4b17023SJohn Marino }
2787*e4b17023SJohn Marino
2788*e4b17023SJohn Marino /* One of the drivers for testing the scalar evolutions analysis.
2789*e4b17023SJohn Marino This function computes the number of iterations for all the loops
2790*e4b17023SJohn Marino from the EXIT_CONDITIONS array. */
2791*e4b17023SJohn Marino
2792*e4b17023SJohn Marino static void
number_of_iterations_for_all_loops(VEC (gimple,heap)** exit_conditions)2793*e4b17023SJohn Marino number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions)
2794*e4b17023SJohn Marino {
2795*e4b17023SJohn Marino unsigned int i;
2796*e4b17023SJohn Marino unsigned nb_chrec_dont_know_loops = 0;
2797*e4b17023SJohn Marino unsigned nb_static_loops = 0;
2798*e4b17023SJohn Marino gimple cond;
2799*e4b17023SJohn Marino
2800*e4b17023SJohn Marino FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
2801*e4b17023SJohn Marino {
2802*e4b17023SJohn Marino tree res = number_of_latch_executions (loop_containing_stmt (cond));
2803*e4b17023SJohn Marino if (chrec_contains_undetermined (res))
2804*e4b17023SJohn Marino nb_chrec_dont_know_loops++;
2805*e4b17023SJohn Marino else
2806*e4b17023SJohn Marino nb_static_loops++;
2807*e4b17023SJohn Marino }
2808*e4b17023SJohn Marino
2809*e4b17023SJohn Marino if (dump_file)
2810*e4b17023SJohn Marino {
2811*e4b17023SJohn Marino fprintf (dump_file, "\n(\n");
2812*e4b17023SJohn Marino fprintf (dump_file, "-----------------------------------------\n");
2813*e4b17023SJohn Marino fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2814*e4b17023SJohn Marino fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2815*e4b17023SJohn Marino fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2816*e4b17023SJohn Marino fprintf (dump_file, "-----------------------------------------\n");
2817*e4b17023SJohn Marino fprintf (dump_file, ")\n\n");
2818*e4b17023SJohn Marino
2819*e4b17023SJohn Marino print_loops (dump_file, 3);
2820*e4b17023SJohn Marino }
2821*e4b17023SJohn Marino }
2822*e4b17023SJohn Marino
2823*e4b17023SJohn Marino
2824*e4b17023SJohn Marino
2825*e4b17023SJohn Marino /* Counters for the stats. */
2826*e4b17023SJohn Marino
2827*e4b17023SJohn Marino struct chrec_stats
2828*e4b17023SJohn Marino {
2829*e4b17023SJohn Marino unsigned nb_chrecs;
2830*e4b17023SJohn Marino unsigned nb_affine;
2831*e4b17023SJohn Marino unsigned nb_affine_multivar;
2832*e4b17023SJohn Marino unsigned nb_higher_poly;
2833*e4b17023SJohn Marino unsigned nb_chrec_dont_know;
2834*e4b17023SJohn Marino unsigned nb_undetermined;
2835*e4b17023SJohn Marino };
2836*e4b17023SJohn Marino
2837*e4b17023SJohn Marino /* Reset the counters. */
2838*e4b17023SJohn Marino
2839*e4b17023SJohn Marino static inline void
reset_chrecs_counters(struct chrec_stats * stats)2840*e4b17023SJohn Marino reset_chrecs_counters (struct chrec_stats *stats)
2841*e4b17023SJohn Marino {
2842*e4b17023SJohn Marino stats->nb_chrecs = 0;
2843*e4b17023SJohn Marino stats->nb_affine = 0;
2844*e4b17023SJohn Marino stats->nb_affine_multivar = 0;
2845*e4b17023SJohn Marino stats->nb_higher_poly = 0;
2846*e4b17023SJohn Marino stats->nb_chrec_dont_know = 0;
2847*e4b17023SJohn Marino stats->nb_undetermined = 0;
2848*e4b17023SJohn Marino }
2849*e4b17023SJohn Marino
2850*e4b17023SJohn Marino /* Dump the contents of a CHREC_STATS structure. */
2851*e4b17023SJohn Marino
2852*e4b17023SJohn Marino static void
dump_chrecs_stats(FILE * file,struct chrec_stats * stats)2853*e4b17023SJohn Marino dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2854*e4b17023SJohn Marino {
2855*e4b17023SJohn Marino fprintf (file, "\n(\n");
2856*e4b17023SJohn Marino fprintf (file, "-----------------------------------------\n");
2857*e4b17023SJohn Marino fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2858*e4b17023SJohn Marino fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2859*e4b17023SJohn Marino fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2860*e4b17023SJohn Marino stats->nb_higher_poly);
2861*e4b17023SJohn Marino fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2862*e4b17023SJohn Marino fprintf (file, "-----------------------------------------\n");
2863*e4b17023SJohn Marino fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2864*e4b17023SJohn Marino fprintf (file, "%d\twith undetermined coefficients\n",
2865*e4b17023SJohn Marino stats->nb_undetermined);
2866*e4b17023SJohn Marino fprintf (file, "-----------------------------------------\n");
2867*e4b17023SJohn Marino fprintf (file, "%d\tchrecs in the scev database\n",
2868*e4b17023SJohn Marino (int) htab_elements (scalar_evolution_info));
2869*e4b17023SJohn Marino fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2870*e4b17023SJohn Marino fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2871*e4b17023SJohn Marino fprintf (file, "-----------------------------------------\n");
2872*e4b17023SJohn Marino fprintf (file, ")\n\n");
2873*e4b17023SJohn Marino }
2874*e4b17023SJohn Marino
2875*e4b17023SJohn Marino /* Gather statistics about CHREC. */
2876*e4b17023SJohn Marino
2877*e4b17023SJohn Marino static void
gather_chrec_stats(tree chrec,struct chrec_stats * stats)2878*e4b17023SJohn Marino gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2879*e4b17023SJohn Marino {
2880*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2881*e4b17023SJohn Marino {
2882*e4b17023SJohn Marino fprintf (dump_file, "(classify_chrec ");
2883*e4b17023SJohn Marino print_generic_expr (dump_file, chrec, 0);
2884*e4b17023SJohn Marino fprintf (dump_file, "\n");
2885*e4b17023SJohn Marino }
2886*e4b17023SJohn Marino
2887*e4b17023SJohn Marino stats->nb_chrecs++;
2888*e4b17023SJohn Marino
2889*e4b17023SJohn Marino if (chrec == NULL_TREE)
2890*e4b17023SJohn Marino {
2891*e4b17023SJohn Marino stats->nb_undetermined++;
2892*e4b17023SJohn Marino return;
2893*e4b17023SJohn Marino }
2894*e4b17023SJohn Marino
2895*e4b17023SJohn Marino switch (TREE_CODE (chrec))
2896*e4b17023SJohn Marino {
2897*e4b17023SJohn Marino case POLYNOMIAL_CHREC:
2898*e4b17023SJohn Marino if (evolution_function_is_affine_p (chrec))
2899*e4b17023SJohn Marino {
2900*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2901*e4b17023SJohn Marino fprintf (dump_file, " affine_univariate\n");
2902*e4b17023SJohn Marino stats->nb_affine++;
2903*e4b17023SJohn Marino }
2904*e4b17023SJohn Marino else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2905*e4b17023SJohn Marino {
2906*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2907*e4b17023SJohn Marino fprintf (dump_file, " affine_multivariate\n");
2908*e4b17023SJohn Marino stats->nb_affine_multivar++;
2909*e4b17023SJohn Marino }
2910*e4b17023SJohn Marino else
2911*e4b17023SJohn Marino {
2912*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2913*e4b17023SJohn Marino fprintf (dump_file, " higher_degree_polynomial\n");
2914*e4b17023SJohn Marino stats->nb_higher_poly++;
2915*e4b17023SJohn Marino }
2916*e4b17023SJohn Marino
2917*e4b17023SJohn Marino break;
2918*e4b17023SJohn Marino
2919*e4b17023SJohn Marino default:
2920*e4b17023SJohn Marino break;
2921*e4b17023SJohn Marino }
2922*e4b17023SJohn Marino
2923*e4b17023SJohn Marino if (chrec_contains_undetermined (chrec))
2924*e4b17023SJohn Marino {
2925*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2926*e4b17023SJohn Marino fprintf (dump_file, " undetermined\n");
2927*e4b17023SJohn Marino stats->nb_undetermined++;
2928*e4b17023SJohn Marino }
2929*e4b17023SJohn Marino
2930*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2931*e4b17023SJohn Marino fprintf (dump_file, ")\n");
2932*e4b17023SJohn Marino }
2933*e4b17023SJohn Marino
2934*e4b17023SJohn Marino /* One of the drivers for testing the scalar evolutions analysis.
2935*e4b17023SJohn Marino This function analyzes the scalar evolution of all the scalars
2936*e4b17023SJohn Marino defined as loop phi nodes in one of the loops from the
2937*e4b17023SJohn Marino EXIT_CONDITIONS array.
2938*e4b17023SJohn Marino
2939*e4b17023SJohn Marino TODO Optimization: A loop is in canonical form if it contains only
2940*e4b17023SJohn Marino a single scalar loop phi node. All the other scalars that have an
2941*e4b17023SJohn Marino evolution in the loop are rewritten in function of this single
2942*e4b17023SJohn Marino index. This allows the parallelization of the loop. */
2943*e4b17023SJohn Marino
2944*e4b17023SJohn Marino static void
analyze_scalar_evolution_for_all_loop_phi_nodes(VEC (gimple,heap)** exit_conditions)2945*e4b17023SJohn Marino analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions)
2946*e4b17023SJohn Marino {
2947*e4b17023SJohn Marino unsigned int i;
2948*e4b17023SJohn Marino struct chrec_stats stats;
2949*e4b17023SJohn Marino gimple cond, phi;
2950*e4b17023SJohn Marino gimple_stmt_iterator psi;
2951*e4b17023SJohn Marino
2952*e4b17023SJohn Marino reset_chrecs_counters (&stats);
2953*e4b17023SJohn Marino
2954*e4b17023SJohn Marino FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
2955*e4b17023SJohn Marino {
2956*e4b17023SJohn Marino struct loop *loop;
2957*e4b17023SJohn Marino basic_block bb;
2958*e4b17023SJohn Marino tree chrec;
2959*e4b17023SJohn Marino
2960*e4b17023SJohn Marino loop = loop_containing_stmt (cond);
2961*e4b17023SJohn Marino bb = loop->header;
2962*e4b17023SJohn Marino
2963*e4b17023SJohn Marino for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2964*e4b17023SJohn Marino {
2965*e4b17023SJohn Marino phi = gsi_stmt (psi);
2966*e4b17023SJohn Marino if (is_gimple_reg (PHI_RESULT (phi)))
2967*e4b17023SJohn Marino {
2968*e4b17023SJohn Marino chrec = instantiate_parameters
2969*e4b17023SJohn Marino (loop,
2970*e4b17023SJohn Marino analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2971*e4b17023SJohn Marino
2972*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2973*e4b17023SJohn Marino gather_chrec_stats (chrec, &stats);
2974*e4b17023SJohn Marino }
2975*e4b17023SJohn Marino }
2976*e4b17023SJohn Marino }
2977*e4b17023SJohn Marino
2978*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
2979*e4b17023SJohn Marino dump_chrecs_stats (dump_file, &stats);
2980*e4b17023SJohn Marino }
2981*e4b17023SJohn Marino
2982*e4b17023SJohn Marino /* Callback for htab_traverse, gathers information on chrecs in the
2983*e4b17023SJohn Marino hashtable. */
2984*e4b17023SJohn Marino
2985*e4b17023SJohn Marino static int
gather_stats_on_scev_database_1(void ** slot,void * stats)2986*e4b17023SJohn Marino gather_stats_on_scev_database_1 (void **slot, void *stats)
2987*e4b17023SJohn Marino {
2988*e4b17023SJohn Marino struct scev_info_str *entry = (struct scev_info_str *) *slot;
2989*e4b17023SJohn Marino
2990*e4b17023SJohn Marino gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2991*e4b17023SJohn Marino
2992*e4b17023SJohn Marino return 1;
2993*e4b17023SJohn Marino }
2994*e4b17023SJohn Marino
2995*e4b17023SJohn Marino /* Classify the chrecs of the whole database. */
2996*e4b17023SJohn Marino
2997*e4b17023SJohn Marino void
gather_stats_on_scev_database(void)2998*e4b17023SJohn Marino gather_stats_on_scev_database (void)
2999*e4b17023SJohn Marino {
3000*e4b17023SJohn Marino struct chrec_stats stats;
3001*e4b17023SJohn Marino
3002*e4b17023SJohn Marino if (!dump_file)
3003*e4b17023SJohn Marino return;
3004*e4b17023SJohn Marino
3005*e4b17023SJohn Marino reset_chrecs_counters (&stats);
3006*e4b17023SJohn Marino
3007*e4b17023SJohn Marino htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
3008*e4b17023SJohn Marino &stats);
3009*e4b17023SJohn Marino
3010*e4b17023SJohn Marino dump_chrecs_stats (dump_file, &stats);
3011*e4b17023SJohn Marino }
3012*e4b17023SJohn Marino
3013*e4b17023SJohn Marino
3014*e4b17023SJohn Marino
3015*e4b17023SJohn Marino /* Initializer. */
3016*e4b17023SJohn Marino
3017*e4b17023SJohn Marino static void
initialize_scalar_evolutions_analyzer(void)3018*e4b17023SJohn Marino initialize_scalar_evolutions_analyzer (void)
3019*e4b17023SJohn Marino {
3020*e4b17023SJohn Marino /* The elements below are unique. */
3021*e4b17023SJohn Marino if (chrec_dont_know == NULL_TREE)
3022*e4b17023SJohn Marino {
3023*e4b17023SJohn Marino chrec_not_analyzed_yet = NULL_TREE;
3024*e4b17023SJohn Marino chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3025*e4b17023SJohn Marino chrec_known = make_node (SCEV_KNOWN);
3026*e4b17023SJohn Marino TREE_TYPE (chrec_dont_know) = void_type_node;
3027*e4b17023SJohn Marino TREE_TYPE (chrec_known) = void_type_node;
3028*e4b17023SJohn Marino }
3029*e4b17023SJohn Marino }
3030*e4b17023SJohn Marino
3031*e4b17023SJohn Marino /* Initialize the analysis of scalar evolutions for LOOPS. */
3032*e4b17023SJohn Marino
3033*e4b17023SJohn Marino void
scev_initialize(void)3034*e4b17023SJohn Marino scev_initialize (void)
3035*e4b17023SJohn Marino {
3036*e4b17023SJohn Marino loop_iterator li;
3037*e4b17023SJohn Marino struct loop *loop;
3038*e4b17023SJohn Marino
3039*e4b17023SJohn Marino
3040*e4b17023SJohn Marino scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
3041*e4b17023SJohn Marino del_scev_info);
3042*e4b17023SJohn Marino
3043*e4b17023SJohn Marino initialize_scalar_evolutions_analyzer ();
3044*e4b17023SJohn Marino
3045*e4b17023SJohn Marino FOR_EACH_LOOP (li, loop, 0)
3046*e4b17023SJohn Marino {
3047*e4b17023SJohn Marino loop->nb_iterations = NULL_TREE;
3048*e4b17023SJohn Marino }
3049*e4b17023SJohn Marino }
3050*e4b17023SJohn Marino
3051*e4b17023SJohn Marino /* Cleans up the information cached by the scalar evolutions analysis
3052*e4b17023SJohn Marino in the hash table. */
3053*e4b17023SJohn Marino
3054*e4b17023SJohn Marino void
scev_reset_htab(void)3055*e4b17023SJohn Marino scev_reset_htab (void)
3056*e4b17023SJohn Marino {
3057*e4b17023SJohn Marino if (!scalar_evolution_info)
3058*e4b17023SJohn Marino return;
3059*e4b17023SJohn Marino
3060*e4b17023SJohn Marino htab_empty (scalar_evolution_info);
3061*e4b17023SJohn Marino }
3062*e4b17023SJohn Marino
3063*e4b17023SJohn Marino /* Cleans up the information cached by the scalar evolutions analysis
3064*e4b17023SJohn Marino in the hash table and in the loop->nb_iterations. */
3065*e4b17023SJohn Marino
3066*e4b17023SJohn Marino void
scev_reset(void)3067*e4b17023SJohn Marino scev_reset (void)
3068*e4b17023SJohn Marino {
3069*e4b17023SJohn Marino loop_iterator li;
3070*e4b17023SJohn Marino struct loop *loop;
3071*e4b17023SJohn Marino
3072*e4b17023SJohn Marino scev_reset_htab ();
3073*e4b17023SJohn Marino
3074*e4b17023SJohn Marino if (!current_loops)
3075*e4b17023SJohn Marino return;
3076*e4b17023SJohn Marino
3077*e4b17023SJohn Marino FOR_EACH_LOOP (li, loop, 0)
3078*e4b17023SJohn Marino {
3079*e4b17023SJohn Marino loop->nb_iterations = NULL_TREE;
3080*e4b17023SJohn Marino }
3081*e4b17023SJohn Marino }
3082*e4b17023SJohn Marino
3083*e4b17023SJohn Marino /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3084*e4b17023SJohn Marino respect to WRTO_LOOP and returns its base and step in IV if possible
3085*e4b17023SJohn Marino (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3086*e4b17023SJohn Marino and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3087*e4b17023SJohn Marino invariant in LOOP. Otherwise we require it to be an integer constant.
3088*e4b17023SJohn Marino
3089*e4b17023SJohn Marino IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3090*e4b17023SJohn Marino because it is computed in signed arithmetics). Consequently, adding an
3091*e4b17023SJohn Marino induction variable
3092*e4b17023SJohn Marino
3093*e4b17023SJohn Marino for (i = IV->base; ; i += IV->step)
3094*e4b17023SJohn Marino
3095*e4b17023SJohn Marino is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3096*e4b17023SJohn Marino false for the type of the induction variable, or you can prove that i does
3097*e4b17023SJohn Marino not wrap by some other argument. Otherwise, this might introduce undefined
3098*e4b17023SJohn Marino behavior, and
3099*e4b17023SJohn Marino
3100*e4b17023SJohn Marino for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3101*e4b17023SJohn Marino
3102*e4b17023SJohn Marino must be used instead. */
3103*e4b17023SJohn Marino
3104*e4b17023SJohn Marino bool
simple_iv(struct loop * wrto_loop,struct loop * use_loop,tree op,affine_iv * iv,bool allow_nonconstant_step)3105*e4b17023SJohn Marino simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3106*e4b17023SJohn Marino affine_iv *iv, bool allow_nonconstant_step)
3107*e4b17023SJohn Marino {
3108*e4b17023SJohn Marino tree type, ev;
3109*e4b17023SJohn Marino bool folded_casts;
3110*e4b17023SJohn Marino
3111*e4b17023SJohn Marino iv->base = NULL_TREE;
3112*e4b17023SJohn Marino iv->step = NULL_TREE;
3113*e4b17023SJohn Marino iv->no_overflow = false;
3114*e4b17023SJohn Marino
3115*e4b17023SJohn Marino type = TREE_TYPE (op);
3116*e4b17023SJohn Marino if (!POINTER_TYPE_P (type)
3117*e4b17023SJohn Marino && !INTEGRAL_TYPE_P (type))
3118*e4b17023SJohn Marino return false;
3119*e4b17023SJohn Marino
3120*e4b17023SJohn Marino ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3121*e4b17023SJohn Marino &folded_casts);
3122*e4b17023SJohn Marino if (chrec_contains_undetermined (ev)
3123*e4b17023SJohn Marino || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3124*e4b17023SJohn Marino return false;
3125*e4b17023SJohn Marino
3126*e4b17023SJohn Marino if (tree_does_not_contain_chrecs (ev))
3127*e4b17023SJohn Marino {
3128*e4b17023SJohn Marino iv->base = ev;
3129*e4b17023SJohn Marino iv->step = build_int_cst (TREE_TYPE (ev), 0);
3130*e4b17023SJohn Marino iv->no_overflow = true;
3131*e4b17023SJohn Marino return true;
3132*e4b17023SJohn Marino }
3133*e4b17023SJohn Marino
3134*e4b17023SJohn Marino if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3135*e4b17023SJohn Marino || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3136*e4b17023SJohn Marino return false;
3137*e4b17023SJohn Marino
3138*e4b17023SJohn Marino iv->step = CHREC_RIGHT (ev);
3139*e4b17023SJohn Marino if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3140*e4b17023SJohn Marino || tree_contains_chrecs (iv->step, NULL))
3141*e4b17023SJohn Marino return false;
3142*e4b17023SJohn Marino
3143*e4b17023SJohn Marino iv->base = CHREC_LEFT (ev);
3144*e4b17023SJohn Marino if (tree_contains_chrecs (iv->base, NULL))
3145*e4b17023SJohn Marino return false;
3146*e4b17023SJohn Marino
3147*e4b17023SJohn Marino iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
3148*e4b17023SJohn Marino
3149*e4b17023SJohn Marino return true;
3150*e4b17023SJohn Marino }
3151*e4b17023SJohn Marino
3152*e4b17023SJohn Marino /* Runs the analysis of scalar evolutions. */
3153*e4b17023SJohn Marino
3154*e4b17023SJohn Marino void
scev_analysis(void)3155*e4b17023SJohn Marino scev_analysis (void)
3156*e4b17023SJohn Marino {
3157*e4b17023SJohn Marino VEC(gimple,heap) *exit_conditions;
3158*e4b17023SJohn Marino
3159*e4b17023SJohn Marino exit_conditions = VEC_alloc (gimple, heap, 37);
3160*e4b17023SJohn Marino select_loops_exit_conditions (&exit_conditions);
3161*e4b17023SJohn Marino
3162*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_STATS))
3163*e4b17023SJohn Marino analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
3164*e4b17023SJohn Marino
3165*e4b17023SJohn Marino number_of_iterations_for_all_loops (&exit_conditions);
3166*e4b17023SJohn Marino VEC_free (gimple, heap, exit_conditions);
3167*e4b17023SJohn Marino }
3168*e4b17023SJohn Marino
3169*e4b17023SJohn Marino /* Finalize the scalar evolution analysis. */
3170*e4b17023SJohn Marino
3171*e4b17023SJohn Marino void
scev_finalize(void)3172*e4b17023SJohn Marino scev_finalize (void)
3173*e4b17023SJohn Marino {
3174*e4b17023SJohn Marino if (!scalar_evolution_info)
3175*e4b17023SJohn Marino return;
3176*e4b17023SJohn Marino htab_delete (scalar_evolution_info);
3177*e4b17023SJohn Marino scalar_evolution_info = NULL;
3178*e4b17023SJohn Marino }
3179*e4b17023SJohn Marino
3180*e4b17023SJohn Marino /* Returns true if the expression EXPR is considered to be too expensive
3181*e4b17023SJohn Marino for scev_const_prop. */
3182*e4b17023SJohn Marino
3183*e4b17023SJohn Marino bool
expression_expensive_p(tree expr)3184*e4b17023SJohn Marino expression_expensive_p (tree expr)
3185*e4b17023SJohn Marino {
3186*e4b17023SJohn Marino enum tree_code code;
3187*e4b17023SJohn Marino
3188*e4b17023SJohn Marino if (is_gimple_val (expr))
3189*e4b17023SJohn Marino return false;
3190*e4b17023SJohn Marino
3191*e4b17023SJohn Marino code = TREE_CODE (expr);
3192*e4b17023SJohn Marino if (code == TRUNC_DIV_EXPR
3193*e4b17023SJohn Marino || code == CEIL_DIV_EXPR
3194*e4b17023SJohn Marino || code == FLOOR_DIV_EXPR
3195*e4b17023SJohn Marino || code == ROUND_DIV_EXPR
3196*e4b17023SJohn Marino || code == TRUNC_MOD_EXPR
3197*e4b17023SJohn Marino || code == CEIL_MOD_EXPR
3198*e4b17023SJohn Marino || code == FLOOR_MOD_EXPR
3199*e4b17023SJohn Marino || code == ROUND_MOD_EXPR
3200*e4b17023SJohn Marino || code == EXACT_DIV_EXPR)
3201*e4b17023SJohn Marino {
3202*e4b17023SJohn Marino /* Division by power of two is usually cheap, so we allow it.
3203*e4b17023SJohn Marino Forbid anything else. */
3204*e4b17023SJohn Marino if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3205*e4b17023SJohn Marino return true;
3206*e4b17023SJohn Marino }
3207*e4b17023SJohn Marino
3208*e4b17023SJohn Marino switch (TREE_CODE_CLASS (code))
3209*e4b17023SJohn Marino {
3210*e4b17023SJohn Marino case tcc_binary:
3211*e4b17023SJohn Marino case tcc_comparison:
3212*e4b17023SJohn Marino if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3213*e4b17023SJohn Marino return true;
3214*e4b17023SJohn Marino
3215*e4b17023SJohn Marino /* Fallthru. */
3216*e4b17023SJohn Marino case tcc_unary:
3217*e4b17023SJohn Marino return expression_expensive_p (TREE_OPERAND (expr, 0));
3218*e4b17023SJohn Marino
3219*e4b17023SJohn Marino default:
3220*e4b17023SJohn Marino return true;
3221*e4b17023SJohn Marino }
3222*e4b17023SJohn Marino }
3223*e4b17023SJohn Marino
3224*e4b17023SJohn Marino /* Replace ssa names for that scev can prove they are constant by the
3225*e4b17023SJohn Marino appropriate constants. Also perform final value replacement in loops,
3226*e4b17023SJohn Marino in case the replacement expressions are cheap.
3227*e4b17023SJohn Marino
3228*e4b17023SJohn Marino We only consider SSA names defined by phi nodes; rest is left to the
3229*e4b17023SJohn Marino ordinary constant propagation pass. */
3230*e4b17023SJohn Marino
3231*e4b17023SJohn Marino unsigned int
scev_const_prop(void)3232*e4b17023SJohn Marino scev_const_prop (void)
3233*e4b17023SJohn Marino {
3234*e4b17023SJohn Marino basic_block bb;
3235*e4b17023SJohn Marino tree name, type, ev;
3236*e4b17023SJohn Marino gimple phi, ass;
3237*e4b17023SJohn Marino struct loop *loop, *ex_loop;
3238*e4b17023SJohn Marino bitmap ssa_names_to_remove = NULL;
3239*e4b17023SJohn Marino unsigned i;
3240*e4b17023SJohn Marino loop_iterator li;
3241*e4b17023SJohn Marino gimple_stmt_iterator psi;
3242*e4b17023SJohn Marino
3243*e4b17023SJohn Marino if (number_of_loops () <= 1)
3244*e4b17023SJohn Marino return 0;
3245*e4b17023SJohn Marino
3246*e4b17023SJohn Marino FOR_EACH_BB (bb)
3247*e4b17023SJohn Marino {
3248*e4b17023SJohn Marino loop = bb->loop_father;
3249*e4b17023SJohn Marino
3250*e4b17023SJohn Marino for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3251*e4b17023SJohn Marino {
3252*e4b17023SJohn Marino phi = gsi_stmt (psi);
3253*e4b17023SJohn Marino name = PHI_RESULT (phi);
3254*e4b17023SJohn Marino
3255*e4b17023SJohn Marino if (!is_gimple_reg (name))
3256*e4b17023SJohn Marino continue;
3257*e4b17023SJohn Marino
3258*e4b17023SJohn Marino type = TREE_TYPE (name);
3259*e4b17023SJohn Marino
3260*e4b17023SJohn Marino if (!POINTER_TYPE_P (type)
3261*e4b17023SJohn Marino && !INTEGRAL_TYPE_P (type))
3262*e4b17023SJohn Marino continue;
3263*e4b17023SJohn Marino
3264*e4b17023SJohn Marino ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3265*e4b17023SJohn Marino if (!is_gimple_min_invariant (ev)
3266*e4b17023SJohn Marino || !may_propagate_copy (name, ev))
3267*e4b17023SJohn Marino continue;
3268*e4b17023SJohn Marino
3269*e4b17023SJohn Marino /* Replace the uses of the name. */
3270*e4b17023SJohn Marino if (name != ev)
3271*e4b17023SJohn Marino replace_uses_by (name, ev);
3272*e4b17023SJohn Marino
3273*e4b17023SJohn Marino if (!ssa_names_to_remove)
3274*e4b17023SJohn Marino ssa_names_to_remove = BITMAP_ALLOC (NULL);
3275*e4b17023SJohn Marino bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3276*e4b17023SJohn Marino }
3277*e4b17023SJohn Marino }
3278*e4b17023SJohn Marino
3279*e4b17023SJohn Marino /* Remove the ssa names that were replaced by constants. We do not
3280*e4b17023SJohn Marino remove them directly in the previous cycle, since this
3281*e4b17023SJohn Marino invalidates scev cache. */
3282*e4b17023SJohn Marino if (ssa_names_to_remove)
3283*e4b17023SJohn Marino {
3284*e4b17023SJohn Marino bitmap_iterator bi;
3285*e4b17023SJohn Marino
3286*e4b17023SJohn Marino EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3287*e4b17023SJohn Marino {
3288*e4b17023SJohn Marino gimple_stmt_iterator psi;
3289*e4b17023SJohn Marino name = ssa_name (i);
3290*e4b17023SJohn Marino phi = SSA_NAME_DEF_STMT (name);
3291*e4b17023SJohn Marino
3292*e4b17023SJohn Marino gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3293*e4b17023SJohn Marino psi = gsi_for_stmt (phi);
3294*e4b17023SJohn Marino remove_phi_node (&psi, true);
3295*e4b17023SJohn Marino }
3296*e4b17023SJohn Marino
3297*e4b17023SJohn Marino BITMAP_FREE (ssa_names_to_remove);
3298*e4b17023SJohn Marino scev_reset ();
3299*e4b17023SJohn Marino }
3300*e4b17023SJohn Marino
3301*e4b17023SJohn Marino /* Now the regular final value replacement. */
3302*e4b17023SJohn Marino FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
3303*e4b17023SJohn Marino {
3304*e4b17023SJohn Marino edge exit;
3305*e4b17023SJohn Marino tree def, rslt, niter;
3306*e4b17023SJohn Marino gimple_stmt_iterator bsi;
3307*e4b17023SJohn Marino
3308*e4b17023SJohn Marino /* If we do not know exact number of iterations of the loop, we cannot
3309*e4b17023SJohn Marino replace the final value. */
3310*e4b17023SJohn Marino exit = single_exit (loop);
3311*e4b17023SJohn Marino if (!exit)
3312*e4b17023SJohn Marino continue;
3313*e4b17023SJohn Marino
3314*e4b17023SJohn Marino niter = number_of_latch_executions (loop);
3315*e4b17023SJohn Marino if (niter == chrec_dont_know)
3316*e4b17023SJohn Marino continue;
3317*e4b17023SJohn Marino
3318*e4b17023SJohn Marino /* Ensure that it is possible to insert new statements somewhere. */
3319*e4b17023SJohn Marino if (!single_pred_p (exit->dest))
3320*e4b17023SJohn Marino split_loop_exit_edge (exit);
3321*e4b17023SJohn Marino bsi = gsi_after_labels (exit->dest);
3322*e4b17023SJohn Marino
3323*e4b17023SJohn Marino ex_loop = superloop_at_depth (loop,
3324*e4b17023SJohn Marino loop_depth (exit->dest->loop_father) + 1);
3325*e4b17023SJohn Marino
3326*e4b17023SJohn Marino for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3327*e4b17023SJohn Marino {
3328*e4b17023SJohn Marino phi = gsi_stmt (psi);
3329*e4b17023SJohn Marino rslt = PHI_RESULT (phi);
3330*e4b17023SJohn Marino def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3331*e4b17023SJohn Marino if (!is_gimple_reg (def))
3332*e4b17023SJohn Marino {
3333*e4b17023SJohn Marino gsi_next (&psi);
3334*e4b17023SJohn Marino continue;
3335*e4b17023SJohn Marino }
3336*e4b17023SJohn Marino
3337*e4b17023SJohn Marino if (!POINTER_TYPE_P (TREE_TYPE (def))
3338*e4b17023SJohn Marino && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3339*e4b17023SJohn Marino {
3340*e4b17023SJohn Marino gsi_next (&psi);
3341*e4b17023SJohn Marino continue;
3342*e4b17023SJohn Marino }
3343*e4b17023SJohn Marino
3344*e4b17023SJohn Marino def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
3345*e4b17023SJohn Marino def = compute_overall_effect_of_inner_loop (ex_loop, def);
3346*e4b17023SJohn Marino if (!tree_does_not_contain_chrecs (def)
3347*e4b17023SJohn Marino || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3348*e4b17023SJohn Marino /* Moving the computation from the loop may prolong life range
3349*e4b17023SJohn Marino of some ssa names, which may cause problems if they appear
3350*e4b17023SJohn Marino on abnormal edges. */
3351*e4b17023SJohn Marino || contains_abnormal_ssa_name_p (def)
3352*e4b17023SJohn Marino /* Do not emit expensive expressions. The rationale is that
3353*e4b17023SJohn Marino when someone writes a code like
3354*e4b17023SJohn Marino
3355*e4b17023SJohn Marino while (n > 45) n -= 45;
3356*e4b17023SJohn Marino
3357*e4b17023SJohn Marino he probably knows that n is not large, and does not want it
3358*e4b17023SJohn Marino to be turned into n %= 45. */
3359*e4b17023SJohn Marino || expression_expensive_p (def))
3360*e4b17023SJohn Marino {
3361*e4b17023SJohn Marino gsi_next (&psi);
3362*e4b17023SJohn Marino continue;
3363*e4b17023SJohn Marino }
3364*e4b17023SJohn Marino
3365*e4b17023SJohn Marino /* Eliminate the PHI node and replace it by a computation outside
3366*e4b17023SJohn Marino the loop. */
3367*e4b17023SJohn Marino def = unshare_expr (def);
3368*e4b17023SJohn Marino remove_phi_node (&psi, false);
3369*e4b17023SJohn Marino
3370*e4b17023SJohn Marino def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
3371*e4b17023SJohn Marino true, GSI_SAME_STMT);
3372*e4b17023SJohn Marino ass = gimple_build_assign (rslt, def);
3373*e4b17023SJohn Marino gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
3374*e4b17023SJohn Marino }
3375*e4b17023SJohn Marino }
3376*e4b17023SJohn Marino return 0;
3377*e4b17023SJohn Marino }
3378*e4b17023SJohn Marino
3379*e4b17023SJohn Marino #include "gt-tree-scalar-evolution.h"
3380