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