|
0
|
1 /* Chains of recurrences.
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
|
|
|
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 /* This file implements operations on chains of recurrences. Chains
|
|
|
23 of recurrences are used for modeling evolution functions of scalar
|
|
|
24 variables.
|
|
|
25 */
|
|
|
26
|
|
|
27 #include "config.h"
|
|
|
28 #include "system.h"
|
|
|
29 #include "coretypes.h"
|
|
|
30 #include "tm.h"
|
|
|
31 #include "ggc.h"
|
|
|
32 #include "tree.h"
|
|
|
33 #include "real.h"
|
|
|
34 #include "diagnostic.h"
|
|
|
35 #include "cfgloop.h"
|
|
|
36 #include "tree-flow.h"
|
|
|
37 #include "tree-chrec.h"
|
|
|
38 #include "tree-pass.h"
|
|
|
39 #include "params.h"
|
|
|
40 #include "tree-scalar-evolution.h"
|
|
|
41
|
|
|
42
|
|
|
43
|
|
|
44 /* Extended folder for chrecs. */
|
|
|
45
|
|
|
46 /* Determines whether CST is not a constant evolution. */
|
|
|
47
|
|
|
48 static inline bool
|
|
|
49 is_not_constant_evolution (const_tree cst)
|
|
|
50 {
|
|
|
51 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
|
|
|
52 }
|
|
|
53
|
|
|
54 /* Fold CODE for a polynomial function and a constant. */
|
|
|
55
|
|
|
56 static inline tree
|
|
|
57 chrec_fold_poly_cst (enum tree_code code,
|
|
|
58 tree type,
|
|
|
59 tree poly,
|
|
|
60 tree cst)
|
|
|
61 {
|
|
|
62 gcc_assert (poly);
|
|
|
63 gcc_assert (cst);
|
|
|
64 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
|
|
|
65 gcc_assert (!is_not_constant_evolution (cst));
|
|
|
66 gcc_assert (type == chrec_type (poly));
|
|
|
67
|
|
|
68 switch (code)
|
|
|
69 {
|
|
|
70 case PLUS_EXPR:
|
|
|
71 return build_polynomial_chrec
|
|
|
72 (CHREC_VARIABLE (poly),
|
|
|
73 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
|
|
|
74 CHREC_RIGHT (poly));
|
|
|
75
|
|
|
76 case MINUS_EXPR:
|
|
|
77 return build_polynomial_chrec
|
|
|
78 (CHREC_VARIABLE (poly),
|
|
|
79 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
|
|
|
80 CHREC_RIGHT (poly));
|
|
|
81
|
|
|
82 case MULT_EXPR:
|
|
|
83 return build_polynomial_chrec
|
|
|
84 (CHREC_VARIABLE (poly),
|
|
|
85 chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
|
|
|
86 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
|
|
|
87
|
|
|
88 default:
|
|
|
89 return chrec_dont_know;
|
|
|
90 }
|
|
|
91 }
|
|
|
92
|
|
|
93 /* Fold the addition of two polynomial functions. */
|
|
|
94
|
|
|
95 static inline tree
|
|
|
96 chrec_fold_plus_poly_poly (enum tree_code code,
|
|
|
97 tree type,
|
|
|
98 tree poly0,
|
|
|
99 tree poly1)
|
|
|
100 {
|
|
|
101 tree left, right;
|
|
|
102 struct loop *loop0 = get_chrec_loop (poly0);
|
|
|
103 struct loop *loop1 = get_chrec_loop (poly1);
|
|
|
104 tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type;
|
|
|
105
|
|
|
106 gcc_assert (poly0);
|
|
|
107 gcc_assert (poly1);
|
|
|
108 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
|
|
|
109 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
|
|
|
110 if (POINTER_TYPE_P (chrec_type (poly0)))
|
|
|
111 gcc_assert (chrec_type (poly1) == sizetype);
|
|
|
112 else
|
|
|
113 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
|
|
|
114 gcc_assert (type == chrec_type (poly0));
|
|
|
115
|
|
|
116 /*
|
|
|
117 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
|
|
|
118 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
|
|
|
119 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
|
|
|
120 if (flow_loop_nested_p (loop0, loop1))
|
|
|
121 {
|
|
|
122 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
|
|
123 return build_polynomial_chrec
|
|
|
124 (CHREC_VARIABLE (poly1),
|
|
|
125 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
|
|
|
126 CHREC_RIGHT (poly1));
|
|
|
127 else
|
|
|
128 return build_polynomial_chrec
|
|
|
129 (CHREC_VARIABLE (poly1),
|
|
|
130 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
|
|
|
131 chrec_fold_multiply (type, CHREC_RIGHT (poly1),
|
|
|
132 SCALAR_FLOAT_TYPE_P (type)
|
|
|
133 ? build_real (type, dconstm1)
|
|
|
134 : build_int_cst_type (type, -1)));
|
|
|
135 }
|
|
|
136
|
|
|
137 if (flow_loop_nested_p (loop1, loop0))
|
|
|
138 {
|
|
|
139 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
|
|
140 return build_polynomial_chrec
|
|
|
141 (CHREC_VARIABLE (poly0),
|
|
|
142 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
|
|
|
143 CHREC_RIGHT (poly0));
|
|
|
144 else
|
|
|
145 return build_polynomial_chrec
|
|
|
146 (CHREC_VARIABLE (poly0),
|
|
|
147 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
|
|
|
148 CHREC_RIGHT (poly0));
|
|
|
149 }
|
|
|
150
|
|
|
151 /* This function should never be called for chrecs of loops that
|
|
|
152 do not belong to the same loop nest. */
|
|
|
153 gcc_assert (loop0 == loop1);
|
|
|
154
|
|
|
155 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
|
|
156 {
|
|
|
157 left = chrec_fold_plus
|
|
|
158 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
|
|
|
159 right = chrec_fold_plus
|
|
|
160 (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
|
|
|
161 }
|
|
|
162 else
|
|
|
163 {
|
|
|
164 left = chrec_fold_minus
|
|
|
165 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
|
|
|
166 right = chrec_fold_minus
|
|
|
167 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
|
|
|
168 }
|
|
|
169
|
|
|
170 if (chrec_zerop (right))
|
|
|
171 return left;
|
|
|
172 else
|
|
|
173 return build_polynomial_chrec
|
|
|
174 (CHREC_VARIABLE (poly0), left, right);
|
|
|
175 }
|
|
|
176
|
|
|
177
|
|
|
178
|
|
|
179 /* Fold the multiplication of two polynomial functions. */
|
|
|
180
|
|
|
181 static inline tree
|
|
|
182 chrec_fold_multiply_poly_poly (tree type,
|
|
|
183 tree poly0,
|
|
|
184 tree poly1)
|
|
|
185 {
|
|
|
186 tree t0, t1, t2;
|
|
|
187 int var;
|
|
|
188 struct loop *loop0 = get_chrec_loop (poly0);
|
|
|
189 struct loop *loop1 = get_chrec_loop (poly1);
|
|
|
190
|
|
|
191 gcc_assert (poly0);
|
|
|
192 gcc_assert (poly1);
|
|
|
193 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
|
|
|
194 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
|
|
|
195 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
|
|
|
196 gcc_assert (type == chrec_type (poly0));
|
|
|
197
|
|
|
198 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
|
|
|
199 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
|
|
|
200 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
|
|
|
201 if (flow_loop_nested_p (loop0, loop1))
|
|
|
202 /* poly0 is a constant wrt. poly1. */
|
|
|
203 return build_polynomial_chrec
|
|
|
204 (CHREC_VARIABLE (poly1),
|
|
|
205 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
|
|
|
206 CHREC_RIGHT (poly1));
|
|
|
207
|
|
|
208 if (flow_loop_nested_p (loop1, loop0))
|
|
|
209 /* poly1 is a constant wrt. poly0. */
|
|
|
210 return build_polynomial_chrec
|
|
|
211 (CHREC_VARIABLE (poly0),
|
|
|
212 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
|
|
|
213 CHREC_RIGHT (poly0));
|
|
|
214
|
|
|
215 gcc_assert (loop0 == loop1);
|
|
|
216
|
|
|
217 /* poly0 and poly1 are two polynomials in the same variable,
|
|
|
218 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
|
|
|
219
|
|
|
220 /* "a*c". */
|
|
|
221 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
|
|
|
222
|
|
|
223 /* "a*d + b*c + b*d". */
|
|
|
224 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
|
|
|
225 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
|
|
|
226 CHREC_RIGHT (poly0),
|
|
|
227 CHREC_LEFT (poly1)));
|
|
|
228 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
|
|
|
229 CHREC_RIGHT (poly0),
|
|
|
230 CHREC_RIGHT (poly1)));
|
|
|
231 /* "2*b*d". */
|
|
|
232 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
|
|
|
233 t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
|
|
|
234 ? build_real (type, dconst2)
|
|
|
235 : build_int_cst (type, 2), t2);
|
|
|
236
|
|
|
237 var = CHREC_VARIABLE (poly0);
|
|
|
238 return build_polynomial_chrec (var, t0,
|
|
|
239 build_polynomial_chrec (var, t1, t2));
|
|
|
240 }
|
|
|
241
|
|
|
242 /* When the operands are automatically_generated_chrec_p, the fold has
|
|
|
243 to respect the semantics of the operands. */
|
|
|
244
|
|
|
245 static inline tree
|
|
|
246 chrec_fold_automatically_generated_operands (tree op0,
|
|
|
247 tree op1)
|
|
|
248 {
|
|
|
249 if (op0 == chrec_dont_know
|
|
|
250 || op1 == chrec_dont_know)
|
|
|
251 return chrec_dont_know;
|
|
|
252
|
|
|
253 if (op0 == chrec_known
|
|
|
254 || op1 == chrec_known)
|
|
|
255 return chrec_known;
|
|
|
256
|
|
|
257 if (op0 == chrec_not_analyzed_yet
|
|
|
258 || op1 == chrec_not_analyzed_yet)
|
|
|
259 return chrec_not_analyzed_yet;
|
|
|
260
|
|
|
261 /* The default case produces a safe result. */
|
|
|
262 return chrec_dont_know;
|
|
|
263 }
|
|
|
264
|
|
|
265 /* Fold the addition of two chrecs. */
|
|
|
266
|
|
|
267 static tree
|
|
|
268 chrec_fold_plus_1 (enum tree_code code, tree type,
|
|
|
269 tree op0, tree op1)
|
|
|
270 {
|
|
|
271 tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
|
|
|
272
|
|
|
273 if (automatically_generated_chrec_p (op0)
|
|
|
274 || automatically_generated_chrec_p (op1))
|
|
|
275 return chrec_fold_automatically_generated_operands (op0, op1);
|
|
|
276
|
|
|
277 switch (TREE_CODE (op0))
|
|
|
278 {
|
|
|
279 case POLYNOMIAL_CHREC:
|
|
|
280 switch (TREE_CODE (op1))
|
|
|
281 {
|
|
|
282 case POLYNOMIAL_CHREC:
|
|
|
283 return chrec_fold_plus_poly_poly (code, type, op0, op1);
|
|
|
284
|
|
|
285 default:
|
|
|
286 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
|
|
287 return build_polynomial_chrec
|
|
|
288 (CHREC_VARIABLE (op0),
|
|
|
289 chrec_fold_plus (type, CHREC_LEFT (op0), op1),
|
|
|
290 CHREC_RIGHT (op0));
|
|
|
291 else
|
|
|
292 return build_polynomial_chrec
|
|
|
293 (CHREC_VARIABLE (op0),
|
|
|
294 chrec_fold_minus (type, CHREC_LEFT (op0), op1),
|
|
|
295 CHREC_RIGHT (op0));
|
|
|
296 }
|
|
|
297
|
|
|
298 default:
|
|
|
299 switch (TREE_CODE (op1))
|
|
|
300 {
|
|
|
301 case POLYNOMIAL_CHREC:
|
|
|
302 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
|
|
303 return build_polynomial_chrec
|
|
|
304 (CHREC_VARIABLE (op1),
|
|
|
305 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
|
|
|
306 CHREC_RIGHT (op1));
|
|
|
307 else
|
|
|
308 return build_polynomial_chrec
|
|
|
309 (CHREC_VARIABLE (op1),
|
|
|
310 chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
|
|
|
311 chrec_fold_multiply (type, CHREC_RIGHT (op1),
|
|
|
312 SCALAR_FLOAT_TYPE_P (type)
|
|
|
313 ? build_real (type, dconstm1)
|
|
|
314 : build_int_cst_type (type, -1)));
|
|
|
315
|
|
|
316 default:
|
|
|
317 {
|
|
|
318 int size = 0;
|
|
|
319 if ((tree_contains_chrecs (op0, &size)
|
|
|
320 || tree_contains_chrecs (op1, &size))
|
|
|
321 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
|
|
|
322 return build2 (code, type, op0, op1);
|
|
|
323 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
|
|
|
324 return fold_build2 (code, type,
|
|
|
325 fold_convert (type, op0),
|
|
|
326 fold_convert (op1_type, op1));
|
|
|
327 else
|
|
|
328 return chrec_dont_know;
|
|
|
329 }
|
|
|
330 }
|
|
|
331 }
|
|
|
332 }
|
|
|
333
|
|
|
334 /* Fold the addition of two chrecs. */
|
|
|
335
|
|
|
336 tree
|
|
|
337 chrec_fold_plus (tree type,
|
|
|
338 tree op0,
|
|
|
339 tree op1)
|
|
|
340 {
|
|
|
341 enum tree_code code;
|
|
|
342 if (automatically_generated_chrec_p (op0)
|
|
|
343 || automatically_generated_chrec_p (op1))
|
|
|
344 return chrec_fold_automatically_generated_operands (op0, op1);
|
|
|
345
|
|
|
346 if (integer_zerop (op0))
|
|
|
347 return chrec_convert (type, op1, NULL);
|
|
|
348 if (integer_zerop (op1))
|
|
|
349 return chrec_convert (type, op0, NULL);
|
|
|
350
|
|
|
351 if (POINTER_TYPE_P (type))
|
|
|
352 code = POINTER_PLUS_EXPR;
|
|
|
353 else
|
|
|
354 code = PLUS_EXPR;
|
|
|
355
|
|
|
356 return chrec_fold_plus_1 (code, type, op0, op1);
|
|
|
357 }
|
|
|
358
|
|
|
359 /* Fold the subtraction of two chrecs. */
|
|
|
360
|
|
|
361 tree
|
|
|
362 chrec_fold_minus (tree type,
|
|
|
363 tree op0,
|
|
|
364 tree op1)
|
|
|
365 {
|
|
|
366 if (automatically_generated_chrec_p (op0)
|
|
|
367 || automatically_generated_chrec_p (op1))
|
|
|
368 return chrec_fold_automatically_generated_operands (op0, op1);
|
|
|
369
|
|
|
370 if (integer_zerop (op1))
|
|
|
371 return op0;
|
|
|
372
|
|
|
373 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
|
|
|
374 }
|
|
|
375
|
|
|
376 /* Fold the multiplication of two chrecs. */
|
|
|
377
|
|
|
378 tree
|
|
|
379 chrec_fold_multiply (tree type,
|
|
|
380 tree op0,
|
|
|
381 tree op1)
|
|
|
382 {
|
|
|
383 if (automatically_generated_chrec_p (op0)
|
|
|
384 || automatically_generated_chrec_p (op1))
|
|
|
385 return chrec_fold_automatically_generated_operands (op0, op1);
|
|
|
386
|
|
|
387 switch (TREE_CODE (op0))
|
|
|
388 {
|
|
|
389 case POLYNOMIAL_CHREC:
|
|
|
390 switch (TREE_CODE (op1))
|
|
|
391 {
|
|
|
392 case POLYNOMIAL_CHREC:
|
|
|
393 return chrec_fold_multiply_poly_poly (type, op0, op1);
|
|
|
394
|
|
|
395 default:
|
|
|
396 if (integer_onep (op1))
|
|
|
397 return op0;
|
|
|
398 if (integer_zerop (op1))
|
|
|
399 return build_int_cst (type, 0);
|
|
|
400
|
|
|
401 return build_polynomial_chrec
|
|
|
402 (CHREC_VARIABLE (op0),
|
|
|
403 chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
|
|
|
404 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
|
|
|
405 }
|
|
|
406
|
|
|
407 default:
|
|
|
408 if (integer_onep (op0))
|
|
|
409 return op1;
|
|
|
410
|
|
|
411 if (integer_zerop (op0))
|
|
|
412 return build_int_cst (type, 0);
|
|
|
413
|
|
|
414 switch (TREE_CODE (op1))
|
|
|
415 {
|
|
|
416 case POLYNOMIAL_CHREC:
|
|
|
417 return build_polynomial_chrec
|
|
|
418 (CHREC_VARIABLE (op1),
|
|
|
419 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
|
|
|
420 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
|
|
|
421
|
|
|
422 default:
|
|
|
423 if (integer_onep (op1))
|
|
|
424 return op0;
|
|
|
425 if (integer_zerop (op1))
|
|
|
426 return build_int_cst (type, 0);
|
|
|
427 return fold_build2 (MULT_EXPR, type, op0, op1);
|
|
|
428 }
|
|
|
429 }
|
|
|
430 }
|
|
|
431
|
|
|
432
|
|
|
433
|
|
|
434 /* Operations. */
|
|
|
435
|
|
|
436 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
|
|
|
437 calculation overflows, otherwise return C(n,k) with type TYPE. */
|
|
|
438
|
|
|
439 static tree
|
|
|
440 tree_fold_binomial (tree type, tree n, unsigned int k)
|
|
|
441 {
|
|
|
442 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
|
|
|
443 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
|
|
|
444 unsigned int i;
|
|
|
445 tree res;
|
|
|
446
|
|
|
447 /* Handle the most frequent cases. */
|
|
|
448 if (k == 0)
|
|
|
449 return build_int_cst (type, 1);
|
|
|
450 if (k == 1)
|
|
|
451 return fold_convert (type, n);
|
|
|
452
|
|
|
453 /* Check that k <= n. */
|
|
|
454 if (TREE_INT_CST_HIGH (n) == 0
|
|
|
455 && TREE_INT_CST_LOW (n) < k)
|
|
|
456 return NULL_TREE;
|
|
|
457
|
|
|
458 /* Numerator = n. */
|
|
|
459 lnum = TREE_INT_CST_LOW (n);
|
|
|
460 hnum = TREE_INT_CST_HIGH (n);
|
|
|
461
|
|
|
462 /* Denominator = 2. */
|
|
|
463 ldenom = 2;
|
|
|
464 hdenom = 0;
|
|
|
465
|
|
|
466 /* Index = Numerator-1. */
|
|
|
467 if (lnum == 0)
|
|
|
468 {
|
|
|
469 hidx = hnum - 1;
|
|
|
470 lidx = ~ (unsigned HOST_WIDE_INT) 0;
|
|
|
471 }
|
|
|
472 else
|
|
|
473 {
|
|
|
474 hidx = hnum;
|
|
|
475 lidx = lnum - 1;
|
|
|
476 }
|
|
|
477
|
|
|
478 /* Numerator = Numerator*Index = n*(n-1). */
|
|
|
479 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
|
|
|
480 return NULL_TREE;
|
|
|
481
|
|
|
482 for (i = 3; i <= k; i++)
|
|
|
483 {
|
|
|
484 /* Index--. */
|
|
|
485 if (lidx == 0)
|
|
|
486 {
|
|
|
487 hidx--;
|
|
|
488 lidx = ~ (unsigned HOST_WIDE_INT) 0;
|
|
|
489 }
|
|
|
490 else
|
|
|
491 lidx--;
|
|
|
492
|
|
|
493 /* Numerator *= Index. */
|
|
|
494 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
|
|
|
495 return NULL_TREE;
|
|
|
496
|
|
|
497 /* Denominator *= i. */
|
|
|
498 mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
|
|
|
499 }
|
|
|
500
|
|
|
501 /* Result = Numerator / Denominator. */
|
|
|
502 div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
|
|
|
503 &lres, &hres, &ldum, &hdum);
|
|
|
504
|
|
|
505 res = build_int_cst_wide (type, lres, hres);
|
|
|
506 return int_fits_type_p (res, type) ? res : NULL_TREE;
|
|
|
507 }
|
|
|
508
|
|
|
509 /* Helper function. Use the Newton's interpolating formula for
|
|
|
510 evaluating the value of the evolution function. */
|
|
|
511
|
|
|
512 static tree
|
|
|
513 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
|
|
|
514 {
|
|
|
515 tree arg0, arg1, binomial_n_k;
|
|
|
516 tree type = TREE_TYPE (chrec);
|
|
|
517 struct loop *var_loop = get_loop (var);
|
|
|
518
|
|
|
519 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
|
|
520 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
|
|
|
521 chrec = CHREC_LEFT (chrec);
|
|
|
522
|
|
|
523 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
|
|
524 && CHREC_VARIABLE (chrec) == var)
|
|
|
525 {
|
|
|
526 arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
|
|
|
527 if (arg1 == chrec_dont_know)
|
|
|
528 return chrec_dont_know;
|
|
|
529 binomial_n_k = tree_fold_binomial (type, n, k);
|
|
|
530 if (!binomial_n_k)
|
|
|
531 return chrec_dont_know;
|
|
|
532 arg0 = fold_build2 (MULT_EXPR, type,
|
|
|
533 CHREC_LEFT (chrec), binomial_n_k);
|
|
|
534 return chrec_fold_plus (type, arg0, arg1);
|
|
|
535 }
|
|
|
536
|
|
|
537 binomial_n_k = tree_fold_binomial (type, n, k);
|
|
|
538 if (!binomial_n_k)
|
|
|
539 return chrec_dont_know;
|
|
|
540
|
|
|
541 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
|
|
|
542 }
|
|
|
543
|
|
|
544 /* Evaluates "CHREC (X)" when the varying variable is VAR.
|
|
|
545 Example: Given the following parameters,
|
|
|
546
|
|
|
547 var = 1
|
|
|
548 chrec = {3, +, 4}_1
|
|
|
549 x = 10
|
|
|
550
|
|
|
551 The result is given by the Newton's interpolating formula:
|
|
|
552 3 * \binom{10}{0} + 4 * \binom{10}{1}.
|
|
|
553 */
|
|
|
554
|
|
|
555 tree
|
|
|
556 chrec_apply (unsigned var,
|
|
|
557 tree chrec,
|
|
|
558 tree x)
|
|
|
559 {
|
|
|
560 tree type = chrec_type (chrec);
|
|
|
561 tree res = chrec_dont_know;
|
|
|
562
|
|
|
563 if (automatically_generated_chrec_p (chrec)
|
|
|
564 || automatically_generated_chrec_p (x)
|
|
|
565
|
|
|
566 /* When the symbols are defined in an outer loop, it is possible
|
|
|
567 to symbolically compute the apply, since the symbols are
|
|
|
568 constants with respect to the varying loop. */
|
|
|
569 || chrec_contains_symbols_defined_in_loop (chrec, var))
|
|
|
570 return chrec_dont_know;
|
|
|
571
|
|
|
572 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
573 fprintf (dump_file, "(chrec_apply \n");
|
|
|
574
|
|
|
575 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
|
|
|
576 x = build_real_from_int_cst (type, x);
|
|
|
577
|
|
|
578 if (evolution_function_is_affine_p (chrec))
|
|
|
579 {
|
|
|
580 /* "{a, +, b} (x)" -> "a + b*x". */
|
|
|
581 x = chrec_convert_rhs (type, x, NULL);
|
|
|
582 res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
|
|
|
583 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
|
|
|
584 }
|
|
|
585
|
|
|
586 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
|
|
|
587 res = chrec;
|
|
|
588
|
|
|
589 else if (TREE_CODE (x) == INTEGER_CST
|
|
|
590 && tree_int_cst_sgn (x) == 1)
|
|
|
591 /* testsuite/.../ssa-chrec-38.c. */
|
|
|
592 res = chrec_evaluate (var, chrec, x, 0);
|
|
|
593 else
|
|
|
594 res = chrec_dont_know;
|
|
|
595
|
|
|
596 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
597 {
|
|
|
598 fprintf (dump_file, " (varying_loop = %d\n", var);
|
|
|
599 fprintf (dump_file, ")\n (chrec = ");
|
|
|
600 print_generic_expr (dump_file, chrec, 0);
|
|
|
601 fprintf (dump_file, ")\n (x = ");
|
|
|
602 print_generic_expr (dump_file, x, 0);
|
|
|
603 fprintf (dump_file, ")\n (res = ");
|
|
|
604 print_generic_expr (dump_file, res, 0);
|
|
|
605 fprintf (dump_file, "))\n");
|
|
|
606 }
|
|
|
607
|
|
|
608 return res;
|
|
|
609 }
|
|
|
610
|
|
|
611 /* Replaces the initial condition in CHREC with INIT_COND. */
|
|
|
612
|
|
|
613 tree
|
|
|
614 chrec_replace_initial_condition (tree chrec,
|
|
|
615 tree init_cond)
|
|
|
616 {
|
|
|
617 if (automatically_generated_chrec_p (chrec))
|
|
|
618 return chrec;
|
|
|
619
|
|
|
620 gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
|
|
|
621
|
|
|
622 switch (TREE_CODE (chrec))
|
|
|
623 {
|
|
|
624 case POLYNOMIAL_CHREC:
|
|
|
625 return build_polynomial_chrec
|
|
|
626 (CHREC_VARIABLE (chrec),
|
|
|
627 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
|
|
|
628 CHREC_RIGHT (chrec));
|
|
|
629
|
|
|
630 default:
|
|
|
631 return init_cond;
|
|
|
632 }
|
|
|
633 }
|
|
|
634
|
|
|
635 /* Returns the initial condition of a given CHREC. */
|
|
|
636
|
|
|
637 tree
|
|
|
638 initial_condition (tree chrec)
|
|
|
639 {
|
|
|
640 if (automatically_generated_chrec_p (chrec))
|
|
|
641 return chrec;
|
|
|
642
|
|
|
643 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
|
|
644 return initial_condition (CHREC_LEFT (chrec));
|
|
|
645 else
|
|
|
646 return chrec;
|
|
|
647 }
|
|
|
648
|
|
|
649 /* Returns a univariate function that represents the evolution in
|
|
|
650 LOOP_NUM. Mask the evolution of any other loop. */
|
|
|
651
|
|
|
652 tree
|
|
|
653 hide_evolution_in_other_loops_than_loop (tree chrec,
|
|
|
654 unsigned loop_num)
|
|
|
655 {
|
|
|
656 struct loop *loop = get_loop (loop_num), *chloop;
|
|
|
657 if (automatically_generated_chrec_p (chrec))
|
|
|
658 return chrec;
|
|
|
659
|
|
|
660 switch (TREE_CODE (chrec))
|
|
|
661 {
|
|
|
662 case POLYNOMIAL_CHREC:
|
|
|
663 chloop = get_chrec_loop (chrec);
|
|
|
664
|
|
|
665 if (chloop == loop)
|
|
|
666 return build_polynomial_chrec
|
|
|
667 (loop_num,
|
|
|
668 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
|
|
|
669 loop_num),
|
|
|
670 CHREC_RIGHT (chrec));
|
|
|
671
|
|
|
672 else if (flow_loop_nested_p (chloop, loop))
|
|
|
673 /* There is no evolution in this loop. */
|
|
|
674 return initial_condition (chrec);
|
|
|
675
|
|
|
676 else
|
|
|
677 {
|
|
|
678 gcc_assert (flow_loop_nested_p (loop, chloop));
|
|
|
679 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
|
|
|
680 loop_num);
|
|
|
681 }
|
|
|
682
|
|
|
683 default:
|
|
|
684 return chrec;
|
|
|
685 }
|
|
|
686 }
|
|
|
687
|
|
|
688 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
|
|
|
689 true, otherwise returns the initial condition in LOOP_NUM. */
|
|
|
690
|
|
|
691 static tree
|
|
|
692 chrec_component_in_loop_num (tree chrec,
|
|
|
693 unsigned loop_num,
|
|
|
694 bool right)
|
|
|
695 {
|
|
|
696 tree component;
|
|
|
697 struct loop *loop = get_loop (loop_num), *chloop;
|
|
|
698
|
|
|
699 if (automatically_generated_chrec_p (chrec))
|
|
|
700 return chrec;
|
|
|
701
|
|
|
702 switch (TREE_CODE (chrec))
|
|
|
703 {
|
|
|
704 case POLYNOMIAL_CHREC:
|
|
|
705 chloop = get_chrec_loop (chrec);
|
|
|
706
|
|
|
707 if (chloop == loop)
|
|
|
708 {
|
|
|
709 if (right)
|
|
|
710 component = CHREC_RIGHT (chrec);
|
|
|
711 else
|
|
|
712 component = CHREC_LEFT (chrec);
|
|
|
713
|
|
|
714 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
|
|
|
715 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
|
|
|
716 return component;
|
|
|
717
|
|
|
718 else
|
|
|
719 return build_polynomial_chrec
|
|
|
720 (loop_num,
|
|
|
721 chrec_component_in_loop_num (CHREC_LEFT (chrec),
|
|
|
722 loop_num,
|
|
|
723 right),
|
|
|
724 component);
|
|
|
725 }
|
|
|
726
|
|
|
727 else if (flow_loop_nested_p (chloop, loop))
|
|
|
728 /* There is no evolution part in this loop. */
|
|
|
729 return NULL_TREE;
|
|
|
730
|
|
|
731 else
|
|
|
732 {
|
|
|
733 gcc_assert (flow_loop_nested_p (loop, chloop));
|
|
|
734 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
|
|
|
735 loop_num,
|
|
|
736 right);
|
|
|
737 }
|
|
|
738
|
|
|
739 default:
|
|
|
740 if (right)
|
|
|
741 return NULL_TREE;
|
|
|
742 else
|
|
|
743 return chrec;
|
|
|
744 }
|
|
|
745 }
|
|
|
746
|
|
|
747 /* Returns the evolution part in LOOP_NUM. Example: the call
|
|
|
748 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
|
|
|
749 {1, +, 2}_1 */
|
|
|
750
|
|
|
751 tree
|
|
|
752 evolution_part_in_loop_num (tree chrec,
|
|
|
753 unsigned loop_num)
|
|
|
754 {
|
|
|
755 return chrec_component_in_loop_num (chrec, loop_num, true);
|
|
|
756 }
|
|
|
757
|
|
|
758 /* Returns the initial condition in LOOP_NUM. Example: the call
|
|
|
759 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
|
|
|
760 {0, +, 1}_1 */
|
|
|
761
|
|
|
762 tree
|
|
|
763 initial_condition_in_loop_num (tree chrec,
|
|
|
764 unsigned loop_num)
|
|
|
765 {
|
|
|
766 return chrec_component_in_loop_num (chrec, loop_num, false);
|
|
|
767 }
|
|
|
768
|
|
|
769 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
|
|
|
770 This function is essentially used for setting the evolution to
|
|
|
771 chrec_dont_know, for example after having determined that it is
|
|
|
772 impossible to say how many times a loop will execute. */
|
|
|
773
|
|
|
774 tree
|
|
|
775 reset_evolution_in_loop (unsigned loop_num,
|
|
|
776 tree chrec,
|
|
|
777 tree new_evol)
|
|
|
778 {
|
|
|
779 struct loop *loop = get_loop (loop_num);
|
|
|
780
|
|
|
781 if (POINTER_TYPE_P (chrec_type (chrec)))
|
|
|
782 gcc_assert (sizetype == chrec_type (new_evol));
|
|
|
783 else
|
|
|
784 gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
|
|
|
785
|
|
|
786 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
|
|
787 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
|
|
|
788 {
|
|
|
789 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
|
|
|
790 new_evol);
|
|
|
791 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
|
|
|
792 new_evol);
|
|
|
793 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
|
|
|
794 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
|
|
|
795 left, right);
|
|
|
796 }
|
|
|
797
|
|
|
798 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
|
|
799 && CHREC_VARIABLE (chrec) == loop_num)
|
|
|
800 chrec = CHREC_LEFT (chrec);
|
|
|
801
|
|
|
802 return build_polynomial_chrec (loop_num, chrec, new_evol);
|
|
|
803 }
|
|
|
804
|
|
|
805 /* Merges two evolution functions that were found by following two
|
|
|
806 alternate paths of a conditional expression. */
|
|
|
807
|
|
|
808 tree
|
|
|
809 chrec_merge (tree chrec1,
|
|
|
810 tree chrec2)
|
|
|
811 {
|
|
|
812 if (chrec1 == chrec_dont_know
|
|
|
813 || chrec2 == chrec_dont_know)
|
|
|
814 return chrec_dont_know;
|
|
|
815
|
|
|
816 if (chrec1 == chrec_known
|
|
|
817 || chrec2 == chrec_known)
|
|
|
818 return chrec_known;
|
|
|
819
|
|
|
820 if (chrec1 == chrec_not_analyzed_yet)
|
|
|
821 return chrec2;
|
|
|
822 if (chrec2 == chrec_not_analyzed_yet)
|
|
|
823 return chrec1;
|
|
|
824
|
|
|
825 if (eq_evolutions_p (chrec1, chrec2))
|
|
|
826 return chrec1;
|
|
|
827
|
|
|
828 return chrec_dont_know;
|
|
|
829 }
|
|
|
830
|
|
|
831
|
|
|
832
|
|
|
833 /* Observers. */
|
|
|
834
|
|
|
835 /* Helper function for is_multivariate_chrec. */
|
|
|
836
|
|
|
837 static bool
|
|
|
838 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
|
|
|
839 {
|
|
|
840 if (chrec == NULL_TREE)
|
|
|
841 return false;
|
|
|
842
|
|
|
843 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
|
|
844 {
|
|
|
845 if (CHREC_VARIABLE (chrec) != rec_var)
|
|
|
846 return true;
|
|
|
847 else
|
|
|
848 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
|
|
|
849 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
|
|
|
850 }
|
|
|
851 else
|
|
|
852 return false;
|
|
|
853 }
|
|
|
854
|
|
|
855 /* Determine whether the given chrec is multivariate or not. */
|
|
|
856
|
|
|
857 bool
|
|
|
858 is_multivariate_chrec (const_tree chrec)
|
|
|
859 {
|
|
|
860 if (chrec == NULL_TREE)
|
|
|
861 return false;
|
|
|
862
|
|
|
863 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
|
|
864 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
|
|
|
865 CHREC_VARIABLE (chrec))
|
|
|
866 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
|
|
|
867 CHREC_VARIABLE (chrec)));
|
|
|
868 else
|
|
|
869 return false;
|
|
|
870 }
|
|
|
871
|
|
|
872 /* Determines whether the chrec contains symbolic names or not. */
|
|
|
873
|
|
|
874 bool
|
|
|
875 chrec_contains_symbols (const_tree chrec)
|
|
|
876 {
|
|
|
877 int i, n;
|
|
|
878
|
|
|
879 if (chrec == NULL_TREE)
|
|
|
880 return false;
|
|
|
881
|
|
|
882 if (TREE_CODE (chrec) == SSA_NAME
|
|
|
883 || TREE_CODE (chrec) == VAR_DECL
|
|
|
884 || TREE_CODE (chrec) == PARM_DECL
|
|
|
885 || TREE_CODE (chrec) == FUNCTION_DECL
|
|
|
886 || TREE_CODE (chrec) == LABEL_DECL
|
|
|
887 || TREE_CODE (chrec) == RESULT_DECL
|
|
|
888 || TREE_CODE (chrec) == FIELD_DECL)
|
|
|
889 return true;
|
|
|
890
|
|
|
891 n = TREE_OPERAND_LENGTH (chrec);
|
|
|
892 for (i = 0; i < n; i++)
|
|
|
893 if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
|
|
|
894 return true;
|
|
|
895 return false;
|
|
|
896 }
|
|
|
897
|
|
|
898 /* Determines whether the chrec contains undetermined coefficients. */
|
|
|
899
|
|
|
900 bool
|
|
|
901 chrec_contains_undetermined (const_tree chrec)
|
|
|
902 {
|
|
|
903 int i, n;
|
|
|
904
|
|
|
905 if (chrec == chrec_dont_know)
|
|
|
906 return true;
|
|
|
907
|
|
|
908 if (chrec == NULL_TREE)
|
|
|
909 return false;
|
|
|
910
|
|
|
911 n = TREE_OPERAND_LENGTH (chrec);
|
|
|
912 for (i = 0; i < n; i++)
|
|
|
913 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
|
|
|
914 return true;
|
|
|
915 return false;
|
|
|
916 }
|
|
|
917
|
|
|
918 /* Determines whether the tree EXPR contains chrecs, and increment
|
|
|
919 SIZE if it is not a NULL pointer by an estimation of the depth of
|
|
|
920 the tree. */
|
|
|
921
|
|
|
922 bool
|
|
|
923 tree_contains_chrecs (const_tree expr, int *size)
|
|
|
924 {
|
|
|
925 int i, n;
|
|
|
926
|
|
|
927 if (expr == NULL_TREE)
|
|
|
928 return false;
|
|
|
929
|
|
|
930 if (size)
|
|
|
931 (*size)++;
|
|
|
932
|
|
|
933 if (tree_is_chrec (expr))
|
|
|
934 return true;
|
|
|
935
|
|
|
936 n = TREE_OPERAND_LENGTH (expr);
|
|
|
937 for (i = 0; i < n; i++)
|
|
|
938 if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
|
|
|
939 return true;
|
|
|
940 return false;
|
|
|
941 }
|
|
|
942
|
|
|
943 /* Recursive helper function. */
|
|
|
944
|
|
|
945 static bool
|
|
|
946 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
|
|
|
947 {
|
|
|
948 if (evolution_function_is_constant_p (chrec))
|
|
|
949 return true;
|
|
|
950
|
|
|
951 if (TREE_CODE (chrec) == SSA_NAME
|
|
|
952 && (loopnum == 0
|
|
|
953 || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
|
|
|
954 return true;
|
|
|
955
|
|
|
956 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
|
|
957 {
|
|
|
958 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
|
|
|
959 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
|
|
|
960 loopnum)
|
|
|
961 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
|
|
|
962 loopnum))
|
|
|
963 return false;
|
|
|
964 return true;
|
|
|
965 }
|
|
|
966
|
|
|
967 switch (TREE_OPERAND_LENGTH (chrec))
|
|
|
968 {
|
|
|
969 case 2:
|
|
|
970 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
|
|
|
971 loopnum))
|
|
|
972 return false;
|
|
|
973
|
|
|
974 case 1:
|
|
|
975 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
|
|
|
976 loopnum))
|
|
|
977 return false;
|
|
|
978 return true;
|
|
|
979
|
|
|
980 default:
|
|
|
981 return false;
|
|
|
982 }
|
|
|
983
|
|
|
984 return false;
|
|
|
985 }
|
|
|
986
|
|
|
987 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
|
|
|
988
|
|
|
989 bool
|
|
|
990 evolution_function_is_invariant_p (tree chrec, int loopnum)
|
|
|
991 {
|
|
|
992 return evolution_function_is_invariant_rec_p (chrec, loopnum);
|
|
|
993 }
|
|
|
994
|
|
|
995 /* Determine whether the given tree is an affine multivariate
|
|
|
996 evolution. */
|
|
|
997
|
|
|
998 bool
|
|
|
999 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
|
|
|
1000 {
|
|
|
1001 if (chrec == NULL_TREE)
|
|
|
1002 return false;
|
|
|
1003
|
|
|
1004 switch (TREE_CODE (chrec))
|
|
|
1005 {
|
|
|
1006 case POLYNOMIAL_CHREC:
|
|
|
1007 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
|
|
|
1008 {
|
|
|
1009 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
|
|
|
1010 return true;
|
|
|
1011 else
|
|
|
1012 {
|
|
|
1013 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
|
|
|
1014 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
|
|
|
1015 != CHREC_VARIABLE (chrec)
|
|
|
1016 && evolution_function_is_affine_multivariate_p
|
|
|
1017 (CHREC_RIGHT (chrec), loopnum))
|
|
|
1018 return true;
|
|
|
1019 else
|
|
|
1020 return false;
|
|
|
1021 }
|
|
|
1022 }
|
|
|
1023 else
|
|
|
1024 {
|
|
|
1025 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
|
|
|
1026 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
|
|
|
1027 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
|
|
|
1028 && evolution_function_is_affine_multivariate_p
|
|
|
1029 (CHREC_LEFT (chrec), loopnum))
|
|
|
1030 return true;
|
|
|
1031 else
|
|
|
1032 return false;
|
|
|
1033 }
|
|
|
1034
|
|
|
1035 default:
|
|
|
1036 return false;
|
|
|
1037 }
|
|
|
1038 }
|
|
|
1039
|
|
|
1040 /* Determine whether the given tree is a function in zero or one
|
|
|
1041 variables. */
|
|
|
1042
|
|
|
1043 bool
|
|
|
1044 evolution_function_is_univariate_p (const_tree chrec)
|
|
|
1045 {
|
|
|
1046 if (chrec == NULL_TREE)
|
|
|
1047 return true;
|
|
|
1048
|
|
|
1049 switch (TREE_CODE (chrec))
|
|
|
1050 {
|
|
|
1051 case POLYNOMIAL_CHREC:
|
|
|
1052 switch (TREE_CODE (CHREC_LEFT (chrec)))
|
|
|
1053 {
|
|
|
1054 case POLYNOMIAL_CHREC:
|
|
|
1055 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
|
|
|
1056 return false;
|
|
|
1057 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
|
|
|
1058 return false;
|
|
|
1059 break;
|
|
|
1060
|
|
|
1061 default:
|
|
|
1062 break;
|
|
|
1063 }
|
|
|
1064
|
|
|
1065 switch (TREE_CODE (CHREC_RIGHT (chrec)))
|
|
|
1066 {
|
|
|
1067 case POLYNOMIAL_CHREC:
|
|
|
1068 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
|
|
|
1069 return false;
|
|
|
1070 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
|
|
|
1071 return false;
|
|
|
1072 break;
|
|
|
1073
|
|
|
1074 default:
|
|
|
1075 break;
|
|
|
1076 }
|
|
|
1077
|
|
|
1078 default:
|
|
|
1079 return true;
|
|
|
1080 }
|
|
|
1081 }
|
|
|
1082
|
|
|
1083 /* Returns the number of variables of CHREC. Example: the call
|
|
|
1084 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
|
|
|
1085
|
|
|
1086 unsigned
|
|
|
1087 nb_vars_in_chrec (tree chrec)
|
|
|
1088 {
|
|
|
1089 if (chrec == NULL_TREE)
|
|
|
1090 return 0;
|
|
|
1091
|
|
|
1092 switch (TREE_CODE (chrec))
|
|
|
1093 {
|
|
|
1094 case POLYNOMIAL_CHREC:
|
|
|
1095 return 1 + nb_vars_in_chrec
|
|
|
1096 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
|
|
|
1097
|
|
|
1098 default:
|
|
|
1099 return 0;
|
|
|
1100 }
|
|
|
1101 }
|
|
|
1102
|
|
|
1103 /* Returns true if TYPE is a type in that we cannot directly perform
|
|
|
1104 arithmetics, even though it is a scalar type. */
|
|
|
1105
|
|
|
1106 static bool
|
|
|
1107 avoid_arithmetics_in_type_p (const_tree type)
|
|
|
1108 {
|
|
|
1109 /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
|
|
|
1110 in the subtype, but a base type must be used, and the result then can
|
|
|
1111 be casted to the subtype. */
|
|
|
1112 if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
|
|
|
1113 return true;
|
|
|
1114
|
|
|
1115 return false;
|
|
|
1116 }
|
|
|
1117
|
|
|
1118 static tree chrec_convert_1 (tree, tree, gimple, bool);
|
|
|
1119
|
|
|
1120 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
|
|
|
1121 the scev corresponds to. AT_STMT is the statement at that the scev is
|
|
|
1122 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
|
|
|
1123 the rules for overflow of the given language apply (e.g., that signed
|
|
|
1124 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
|
|
|
1125 tests, but also to enforce that the result follows them. Returns true if the
|
|
|
1126 conversion succeeded, false otherwise. */
|
|
|
1127
|
|
|
1128 bool
|
|
|
1129 convert_affine_scev (struct loop *loop, tree type,
|
|
|
1130 tree *base, tree *step, gimple at_stmt,
|
|
|
1131 bool use_overflow_semantics)
|
|
|
1132 {
|
|
|
1133 tree ct = TREE_TYPE (*step);
|
|
|
1134 bool enforce_overflow_semantics;
|
|
|
1135 bool must_check_src_overflow, must_check_rslt_overflow;
|
|
|
1136 tree new_base, new_step;
|
|
|
1137 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
|
|
|
1138
|
|
|
1139 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
|
|
|
1140 if (avoid_arithmetics_in_type_p (type))
|
|
|
1141 return false;
|
|
|
1142
|
|
|
1143 /* In general,
|
|
|
1144 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
|
|
|
1145 but we must check some assumptions.
|
|
|
1146
|
|
|
1147 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
|
|
|
1148 of CT is smaller than the precision of TYPE. For example, when we
|
|
|
1149 cast unsigned char [254, +, 1] to unsigned, the values on left side
|
|
|
1150 are 254, 255, 0, 1, ..., but those on the right side are
|
|
|
1151 254, 255, 256, 257, ...
|
|
|
1152 2) In case that we must also preserve the fact that signed ivs do not
|
|
|
1153 overflow, we must additionally check that the new iv does not wrap.
|
|
|
1154 For example, unsigned char [125, +, 1] casted to signed char could
|
|
|
1155 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
|
|
|
1156 which would confuse optimizers that assume that this does not
|
|
|
1157 happen. */
|
|
|
1158 must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
|
|
|
1159
|
|
|
1160 enforce_overflow_semantics = (use_overflow_semantics
|
|
|
1161 && nowrap_type_p (type));
|
|
|
1162 if (enforce_overflow_semantics)
|
|
|
1163 {
|
|
|
1164 /* We can avoid checking whether the result overflows in the following
|
|
|
1165 cases:
|
|
|
1166
|
|
|
1167 -- must_check_src_overflow is true, and the range of TYPE is superset
|
|
|
1168 of the range of CT -- i.e., in all cases except if CT signed and
|
|
|
1169 TYPE unsigned.
|
|
|
1170 -- both CT and TYPE have the same precision and signedness, and we
|
|
|
1171 verify instead that the source does not overflow (this may be
|
|
|
1172 easier than verifying it for the result, as we may use the
|
|
|
1173 information about the semantics of overflow in CT). */
|
|
|
1174 if (must_check_src_overflow)
|
|
|
1175 {
|
|
|
1176 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
|
|
|
1177 must_check_rslt_overflow = true;
|
|
|
1178 else
|
|
|
1179 must_check_rslt_overflow = false;
|
|
|
1180 }
|
|
|
1181 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
|
|
|
1182 && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
|
|
|
1183 {
|
|
|
1184 must_check_rslt_overflow = false;
|
|
|
1185 must_check_src_overflow = true;
|
|
|
1186 }
|
|
|
1187 else
|
|
|
1188 must_check_rslt_overflow = true;
|
|
|
1189 }
|
|
|
1190 else
|
|
|
1191 must_check_rslt_overflow = false;
|
|
|
1192
|
|
|
1193 if (must_check_src_overflow
|
|
|
1194 && scev_probably_wraps_p (*base, *step, at_stmt, loop,
|
|
|
1195 use_overflow_semantics))
|
|
|
1196 return false;
|
|
|
1197
|
|
|
1198 new_base = chrec_convert_1 (type, *base, at_stmt,
|
|
|
1199 use_overflow_semantics);
|
|
|
1200 /* The step must be sign extended, regardless of the signedness
|
|
|
1201 of CT and TYPE. This only needs to be handled specially when
|
|
|
1202 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
|
|
|
1203 (with values 100, 99, 98, ...) from becoming signed or unsigned
|
|
|
1204 [100, +, 255] with values 100, 355, ...; the sign-extension is
|
|
|
1205 performed by default when CT is signed. */
|
|
|
1206 new_step = *step;
|
|
|
1207 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
|
|
|
1208 new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
|
|
|
1209 use_overflow_semantics);
|
|
|
1210 new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
|
|
|
1211
|
|
|
1212 if (automatically_generated_chrec_p (new_base)
|
|
|
1213 || automatically_generated_chrec_p (new_step))
|
|
|
1214 return false;
|
|
|
1215
|
|
|
1216 if (must_check_rslt_overflow
|
|
|
1217 /* Note that in this case we cannot use the fact that signed variables
|
|
|
1218 do not overflow, as this is what we are verifying for the new iv. */
|
|
|
1219 && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
|
|
|
1220 return false;
|
|
|
1221
|
|
|
1222 *base = new_base;
|
|
|
1223 *step = new_step;
|
|
|
1224 return true;
|
|
|
1225 }
|
|
|
1226
|
|
|
1227
|
|
|
1228 /* Convert CHREC for the right hand side of a CREC.
|
|
|
1229 The increment for a pointer type is always sizetype. */
|
|
|
1230 tree
|
|
|
1231 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
|
|
|
1232 {
|
|
|
1233 if (POINTER_TYPE_P (type))
|
|
|
1234 type = sizetype;
|
|
|
1235 return chrec_convert (type, chrec, at_stmt);
|
|
|
1236 }
|
|
|
1237
|
|
|
1238 /* Convert CHREC to TYPE. When the analyzer knows the context in
|
|
|
1239 which the CHREC is built, it sets AT_STMT to the statement that
|
|
|
1240 contains the definition of the analyzed variable, otherwise the
|
|
|
1241 conversion is less accurate: the information is used for
|
|
|
1242 determining a more accurate estimation of the number of iterations.
|
|
|
1243 By default AT_STMT could be safely set to NULL_TREE.
|
|
|
1244
|
|
|
1245 The following rule is always true: TREE_TYPE (chrec) ==
|
|
|
1246 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
|
|
|
1247 An example of what could happen when adding two chrecs and the type
|
|
|
1248 of the CHREC_RIGHT is different than CHREC_LEFT is:
|
|
|
1249
|
|
|
1250 {(uint) 0, +, (uchar) 10} +
|
|
|
1251 {(uint) 0, +, (uchar) 250}
|
|
|
1252
|
|
|
1253 that would produce a wrong result if CHREC_RIGHT is not (uint):
|
|
|
1254
|
|
|
1255 {(uint) 0, +, (uchar) 4}
|
|
|
1256
|
|
|
1257 instead of
|
|
|
1258
|
|
|
1259 {(uint) 0, +, (uint) 260}
|
|
|
1260 */
|
|
|
1261
|
|
|
1262 tree
|
|
|
1263 chrec_convert (tree type, tree chrec, gimple at_stmt)
|
|
|
1264 {
|
|
|
1265 return chrec_convert_1 (type, chrec, at_stmt, true);
|
|
|
1266 }
|
|
|
1267
|
|
|
1268 /* Convert CHREC to TYPE. When the analyzer knows the context in
|
|
|
1269 which the CHREC is built, it sets AT_STMT to the statement that
|
|
|
1270 contains the definition of the analyzed variable, otherwise the
|
|
|
1271 conversion is less accurate: the information is used for
|
|
|
1272 determining a more accurate estimation of the number of iterations.
|
|
|
1273 By default AT_STMT could be safely set to NULL_TREE.
|
|
|
1274
|
|
|
1275 USE_OVERFLOW_SEMANTICS is true if this function should assume that
|
|
|
1276 the rules for overflow of the given language apply (e.g., that signed
|
|
|
1277 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
|
|
|
1278 tests, but also to enforce that the result follows them. */
|
|
|
1279
|
|
|
1280 static tree
|
|
|
1281 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
|
|
|
1282 bool use_overflow_semantics)
|
|
|
1283 {
|
|
|
1284 tree ct, res;
|
|
|
1285 tree base, step;
|
|
|
1286 struct loop *loop;
|
|
|
1287
|
|
|
1288 if (automatically_generated_chrec_p (chrec))
|
|
|
1289 return chrec;
|
|
|
1290
|
|
|
1291 ct = chrec_type (chrec);
|
|
|
1292 if (ct == type)
|
|
|
1293 return chrec;
|
|
|
1294
|
|
|
1295 if (!evolution_function_is_affine_p (chrec))
|
|
|
1296 goto keep_cast;
|
|
|
1297
|
|
|
1298 loop = get_chrec_loop (chrec);
|
|
|
1299 base = CHREC_LEFT (chrec);
|
|
|
1300 step = CHREC_RIGHT (chrec);
|
|
|
1301
|
|
|
1302 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
|
|
|
1303 use_overflow_semantics))
|
|
|
1304 return build_polynomial_chrec (loop->num, base, step);
|
|
|
1305
|
|
|
1306 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
|
|
|
1307 keep_cast:
|
|
|
1308 res = fold_convert (type, chrec);
|
|
|
1309
|
|
|
1310 /* Don't propagate overflows. */
|
|
|
1311 if (CONSTANT_CLASS_P (res))
|
|
|
1312 TREE_OVERFLOW (res) = 0;
|
|
|
1313
|
|
|
1314 /* But reject constants that don't fit in their type after conversion.
|
|
|
1315 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
|
|
|
1316 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
|
|
|
1317 and can cause problems later when computing niters of loops. Note
|
|
|
1318 that we don't do the check before converting because we don't want
|
|
|
1319 to reject conversions of negative chrecs to unsigned types. */
|
|
|
1320 if (TREE_CODE (res) == INTEGER_CST
|
|
|
1321 && TREE_CODE (type) == INTEGER_TYPE
|
|
|
1322 && !int_fits_type_p (res, type))
|
|
|
1323 res = chrec_dont_know;
|
|
|
1324
|
|
|
1325 return res;
|
|
|
1326 }
|
|
|
1327
|
|
|
1328 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
|
|
|
1329 chrec if something else than what chrec_convert would do happens, NULL_TREE
|
|
|
1330 otherwise. */
|
|
|
1331
|
|
|
1332 tree
|
|
|
1333 chrec_convert_aggressive (tree type, tree chrec)
|
|
|
1334 {
|
|
|
1335 tree inner_type, left, right, lc, rc, rtype;
|
|
|
1336
|
|
|
1337 if (automatically_generated_chrec_p (chrec)
|
|
|
1338 || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
|
|
|
1339 return NULL_TREE;
|
|
|
1340
|
|
|
1341 inner_type = TREE_TYPE (chrec);
|
|
|
1342 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
|
|
|
1343 return NULL_TREE;
|
|
|
1344
|
|
|
1345 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
|
|
|
1346 if (avoid_arithmetics_in_type_p (type))
|
|
|
1347 return NULL_TREE;
|
|
|
1348
|
|
|
1349 rtype = POINTER_TYPE_P (type) ? sizetype : type;
|
|
|
1350
|
|
|
1351 left = CHREC_LEFT (chrec);
|
|
|
1352 right = CHREC_RIGHT (chrec);
|
|
|
1353 lc = chrec_convert_aggressive (type, left);
|
|
|
1354 if (!lc)
|
|
|
1355 lc = chrec_convert (type, left, NULL);
|
|
|
1356 rc = chrec_convert_aggressive (rtype, right);
|
|
|
1357 if (!rc)
|
|
|
1358 rc = chrec_convert (rtype, right, NULL);
|
|
|
1359
|
|
|
1360 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
|
|
|
1361 }
|
|
|
1362
|
|
|
1363 /* Returns true when CHREC0 == CHREC1. */
|
|
|
1364
|
|
|
1365 bool
|
|
|
1366 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
|
|
|
1367 {
|
|
|
1368 if (chrec0 == NULL_TREE
|
|
|
1369 || chrec1 == NULL_TREE
|
|
|
1370 || TREE_CODE (chrec0) != TREE_CODE (chrec1))
|
|
|
1371 return false;
|
|
|
1372
|
|
|
1373 if (chrec0 == chrec1)
|
|
|
1374 return true;
|
|
|
1375
|
|
|
1376 switch (TREE_CODE (chrec0))
|
|
|
1377 {
|
|
|
1378 case INTEGER_CST:
|
|
|
1379 return operand_equal_p (chrec0, chrec1, 0);
|
|
|
1380
|
|
|
1381 case POLYNOMIAL_CHREC:
|
|
|
1382 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
|
|
|
1383 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
|
|
|
1384 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
|
|
|
1385 default:
|
|
|
1386 return false;
|
|
|
1387 }
|
|
|
1388 }
|
|
|
1389
|
|
|
1390 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
|
|
|
1391 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
|
|
|
1392 which of these cases happens. */
|
|
|
1393
|
|
|
1394 enum ev_direction
|
|
|
1395 scev_direction (const_tree chrec)
|
|
|
1396 {
|
|
|
1397 const_tree step;
|
|
|
1398
|
|
|
1399 if (!evolution_function_is_affine_p (chrec))
|
|
|
1400 return EV_DIR_UNKNOWN;
|
|
|
1401
|
|
|
1402 step = CHREC_RIGHT (chrec);
|
|
|
1403 if (TREE_CODE (step) != INTEGER_CST)
|
|
|
1404 return EV_DIR_UNKNOWN;
|
|
|
1405
|
|
|
1406 if (tree_int_cst_sign_bit (step))
|
|
|
1407 return EV_DIR_DECREASES;
|
|
|
1408 else
|
|
|
1409 return EV_DIR_GROWS;
|
|
|
1410 }
|
|
|
1411
|
|
|
1412 /* Iterates over all the components of SCEV, and calls CBCK. */
|
|
|
1413
|
|
|
1414 void
|
|
|
1415 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
|
|
|
1416 {
|
|
|
1417 switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
|
|
|
1418 {
|
|
|
1419 case 3:
|
|
|
1420 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
|
|
|
1421
|
|
|
1422 case 2:
|
|
|
1423 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
|
|
|
1424
|
|
|
1425 case 1:
|
|
|
1426 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
|
|
|
1427
|
|
|
1428 default:
|
|
|
1429 cbck (scev, data);
|
|
|
1430 break;
|
|
|
1431 }
|
|
|
1432 }
|
|
|
1433
|
|
|
1434 /* Returns true when the operation can be part of a linear
|
|
|
1435 expression. */
|
|
|
1436
|
|
|
1437 static inline bool
|
|
|
1438 operator_is_linear (tree scev)
|
|
|
1439 {
|
|
|
1440 switch (TREE_CODE (scev))
|
|
|
1441 {
|
|
|
1442 case INTEGER_CST:
|
|
|
1443 case POLYNOMIAL_CHREC:
|
|
|
1444 case PLUS_EXPR:
|
|
|
1445 case POINTER_PLUS_EXPR:
|
|
|
1446 case MULT_EXPR:
|
|
|
1447 case MINUS_EXPR:
|
|
|
1448 case NEGATE_EXPR:
|
|
|
1449 case SSA_NAME:
|
|
|
1450 case NON_LVALUE_EXPR:
|
|
|
1451 CASE_CONVERT:
|
|
|
1452 return true;
|
|
|
1453
|
|
|
1454 default:
|
|
|
1455 return false;
|
|
|
1456 }
|
|
|
1457 }
|
|
|
1458
|
|
|
1459 /* Return true when SCEV is a linear expression. Linear expressions
|
|
|
1460 can contain additions, substractions and multiplications.
|
|
|
1461 Multiplications are restricted to constant scaling: "cst * x". */
|
|
|
1462
|
|
|
1463 bool
|
|
|
1464 scev_is_linear_expression (tree scev)
|
|
|
1465 {
|
|
|
1466 if (scev == NULL
|
|
|
1467 || !operator_is_linear (scev))
|
|
|
1468 return false;
|
|
|
1469
|
|
|
1470 if (TREE_CODE (scev) == MULT_EXPR)
|
|
|
1471 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
|
|
|
1472 && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
|
|
|
1473
|
|
|
1474 switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
|
|
|
1475 {
|
|
|
1476 case 3:
|
|
|
1477 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
|
|
|
1478 && scev_is_linear_expression (TREE_OPERAND (scev, 1))
|
|
|
1479 && scev_is_linear_expression (TREE_OPERAND (scev, 2));
|
|
|
1480
|
|
|
1481 case 2:
|
|
|
1482 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
|
|
|
1483 && scev_is_linear_expression (TREE_OPERAND (scev, 1));
|
|
|
1484
|
|
|
1485 case 1:
|
|
|
1486 return scev_is_linear_expression (TREE_OPERAND (scev, 0));
|
|
|
1487
|
|
|
1488 case 0:
|
|
|
1489 return true;
|
|
|
1490
|
|
|
1491 default:
|
|
|
1492 return false;
|
|
|
1493 }
|
|
|
1494 }
|
