]>
Commit | Line | Data |
---|---|---|
c8a2ab6d | 1 | /* Chains of recurrences. |
1a9dddad | 2 | Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. |
c8a2ab6d SP |
3 | Contributed by Sebastian Pop <s.pop@laposte.net> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 2, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING. If not, write to the Free | |
366ccddb KC |
19 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
20 | 02110-1301, USA. */ | |
c8a2ab6d SP |
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" | |
c8a2ab6d SP |
31 | #include "ggc.h" |
32 | #include "tree.h" | |
7e0923cd | 33 | #include "real.h" |
c8a2ab6d SP |
34 | #include "diagnostic.h" |
35 | #include "varray.h" | |
1e8552eb SP |
36 | #include "cfgloop.h" |
37 | #include "tree-flow.h" | |
c8a2ab6d SP |
38 | #include "tree-chrec.h" |
39 | #include "tree-pass.h" | |
2412d35c | 40 | #include "params.h" |
c8a2ab6d | 41 | |
c8a2ab6d SP |
42 | \f |
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 (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 | { | |
1e128c5f GB |
62 | gcc_assert (poly); |
63 | gcc_assert (cst); | |
64 | gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC); | |
65 | gcc_assert (!is_not_constant_evolution (cst)); | |
c8a2ab6d SP |
66 | |
67 | switch (code) | |
68 | { | |
69 | case PLUS_EXPR: | |
70 | return build_polynomial_chrec | |
71 | (CHREC_VARIABLE (poly), | |
72 | chrec_fold_plus (type, CHREC_LEFT (poly), cst), | |
73 | CHREC_RIGHT (poly)); | |
74 | ||
75 | case MINUS_EXPR: | |
76 | return build_polynomial_chrec | |
77 | (CHREC_VARIABLE (poly), | |
78 | chrec_fold_minus (type, CHREC_LEFT (poly), cst), | |
79 | CHREC_RIGHT (poly)); | |
80 | ||
81 | case MULT_EXPR: | |
82 | return build_polynomial_chrec | |
83 | (CHREC_VARIABLE (poly), | |
84 | chrec_fold_multiply (type, CHREC_LEFT (poly), cst), | |
85 | chrec_fold_multiply (type, CHREC_RIGHT (poly), cst)); | |
86 | ||
87 | default: | |
88 | return chrec_dont_know; | |
89 | } | |
90 | } | |
91 | ||
92 | /* Fold the addition of two polynomial functions. */ | |
93 | ||
94 | static inline tree | |
95 | chrec_fold_plus_poly_poly (enum tree_code code, | |
96 | tree type, | |
97 | tree poly0, | |
98 | tree poly1) | |
99 | { | |
100 | tree left, right; | |
1e128c5f GB |
101 | |
102 | gcc_assert (poly0); | |
103 | gcc_assert (poly1); | |
104 | gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); | |
105 | gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); | |
c8a2ab6d SP |
106 | |
107 | /* | |
108 | {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, | |
109 | {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, | |
110 | {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ | |
111 | if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) | |
112 | { | |
113 | if (code == PLUS_EXPR) | |
114 | return build_polynomial_chrec | |
115 | (CHREC_VARIABLE (poly1), | |
116 | chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)), | |
117 | CHREC_RIGHT (poly1)); | |
118 | else | |
119 | return build_polynomial_chrec | |
120 | (CHREC_VARIABLE (poly1), | |
121 | chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)), | |
122 | chrec_fold_multiply (type, CHREC_RIGHT (poly1), | |
7e0923cd SP |
123 | SCALAR_FLOAT_TYPE_P (type) |
124 | ? build_real (type, dconstm1) | |
125 | : build_int_cst_type (type, -1))); | |
c8a2ab6d SP |
126 | } |
127 | ||
128 | if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1)) | |
129 | { | |
130 | if (code == PLUS_EXPR) | |
131 | return build_polynomial_chrec | |
132 | (CHREC_VARIABLE (poly0), | |
133 | chrec_fold_plus (type, CHREC_LEFT (poly0), poly1), | |
134 | CHREC_RIGHT (poly0)); | |
135 | else | |
136 | return build_polynomial_chrec | |
137 | (CHREC_VARIABLE (poly0), | |
138 | chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), | |
139 | CHREC_RIGHT (poly0)); | |
140 | } | |
141 | ||
142 | if (code == PLUS_EXPR) | |
143 | { | |
144 | left = chrec_fold_plus | |
145 | (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); | |
146 | right = chrec_fold_plus | |
147 | (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); | |
148 | } | |
149 | else | |
150 | { | |
151 | left = chrec_fold_minus | |
152 | (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); | |
153 | right = chrec_fold_minus | |
154 | (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); | |
155 | } | |
156 | ||
157 | if (chrec_zerop (right)) | |
158 | return left; | |
159 | else | |
160 | return build_polynomial_chrec | |
161 | (CHREC_VARIABLE (poly0), left, right); | |
162 | } | |
163 | ||
164 | \f | |
165 | ||
166 | /* Fold the multiplication of two polynomial functions. */ | |
167 | ||
168 | static inline tree | |
169 | chrec_fold_multiply_poly_poly (tree type, | |
170 | tree poly0, | |
171 | tree poly1) | |
172 | { | |
2c5f025d ZD |
173 | tree t0, t1, t2; |
174 | int var; | |
175 | ||
1e128c5f GB |
176 | gcc_assert (poly0); |
177 | gcc_assert (poly1); | |
178 | gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); | |
179 | gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); | |
c8a2ab6d SP |
180 | |
181 | /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, | |
182 | {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, | |
183 | {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ | |
184 | if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) | |
185 | /* poly0 is a constant wrt. poly1. */ | |
186 | return build_polynomial_chrec | |
187 | (CHREC_VARIABLE (poly1), | |
188 | chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), | |
189 | CHREC_RIGHT (poly1)); | |
190 | ||
191 | if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0)) | |
192 | /* poly1 is a constant wrt. poly0. */ | |
193 | return build_polynomial_chrec | |
194 | (CHREC_VARIABLE (poly0), | |
195 | chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), | |
196 | CHREC_RIGHT (poly0)); | |
197 | ||
198 | /* poly0 and poly1 are two polynomials in the same variable, | |
199 | {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ | |
c8a2ab6d | 200 | |
2c5f025d ZD |
201 | /* "a*c". */ |
202 | t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); | |
203 | ||
204 | /* "a*d + b*c + b*d". */ | |
205 | t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); | |
206 | t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, | |
207 | CHREC_RIGHT (poly0), | |
208 | CHREC_LEFT (poly1))); | |
209 | t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, | |
210 | CHREC_RIGHT (poly0), | |
211 | CHREC_RIGHT (poly1))); | |
212 | /* "2*b*d". */ | |
213 | t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); | |
7e0923cd SP |
214 | t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type) |
215 | ? build_real (type, dconst2) | |
216 | : build_int_cst_type (type, 2), t2); | |
2c5f025d ZD |
217 | |
218 | var = CHREC_VARIABLE (poly0); | |
219 | return build_polynomial_chrec (var, t0, | |
220 | build_polynomial_chrec (var, t1, t2)); | |
c8a2ab6d SP |
221 | } |
222 | ||
223 | /* When the operands are automatically_generated_chrec_p, the fold has | |
224 | to respect the semantics of the operands. */ | |
225 | ||
226 | static inline tree | |
227 | chrec_fold_automatically_generated_operands (tree op0, | |
228 | tree op1) | |
229 | { | |
230 | if (op0 == chrec_dont_know | |
231 | || op1 == chrec_dont_know) | |
232 | return chrec_dont_know; | |
233 | ||
234 | if (op0 == chrec_known | |
235 | || op1 == chrec_known) | |
236 | return chrec_known; | |
237 | ||
238 | if (op0 == chrec_not_analyzed_yet | |
239 | || op1 == chrec_not_analyzed_yet) | |
240 | return chrec_not_analyzed_yet; | |
241 | ||
8c27b7d4 | 242 | /* The default case produces a safe result. */ |
c8a2ab6d SP |
243 | return chrec_dont_know; |
244 | } | |
245 | ||
246 | /* Fold the addition of two chrecs. */ | |
247 | ||
248 | static tree | |
249 | chrec_fold_plus_1 (enum tree_code code, | |
250 | tree type, | |
251 | tree op0, | |
252 | tree op1) | |
253 | { | |
254 | if (automatically_generated_chrec_p (op0) | |
255 | || automatically_generated_chrec_p (op1)) | |
256 | return chrec_fold_automatically_generated_operands (op0, op1); | |
257 | ||
258 | switch (TREE_CODE (op0)) | |
259 | { | |
260 | case POLYNOMIAL_CHREC: | |
261 | switch (TREE_CODE (op1)) | |
262 | { | |
263 | case POLYNOMIAL_CHREC: | |
264 | return chrec_fold_plus_poly_poly (code, type, op0, op1); | |
265 | ||
266 | default: | |
267 | if (code == PLUS_EXPR) | |
268 | return build_polynomial_chrec | |
269 | (CHREC_VARIABLE (op0), | |
270 | chrec_fold_plus (type, CHREC_LEFT (op0), op1), | |
271 | CHREC_RIGHT (op0)); | |
272 | else | |
273 | return build_polynomial_chrec | |
274 | (CHREC_VARIABLE (op0), | |
275 | chrec_fold_minus (type, CHREC_LEFT (op0), op1), | |
276 | CHREC_RIGHT (op0)); | |
277 | } | |
278 | ||
279 | default: | |
280 | switch (TREE_CODE (op1)) | |
281 | { | |
282 | case POLYNOMIAL_CHREC: | |
283 | if (code == PLUS_EXPR) | |
284 | return build_polynomial_chrec | |
285 | (CHREC_VARIABLE (op1), | |
286 | chrec_fold_plus (type, op0, CHREC_LEFT (op1)), | |
287 | CHREC_RIGHT (op1)); | |
288 | else | |
289 | return build_polynomial_chrec | |
290 | (CHREC_VARIABLE (op1), | |
291 | chrec_fold_minus (type, op0, CHREC_LEFT (op1)), | |
7e0923cd SP |
292 | chrec_fold_multiply (type, CHREC_RIGHT (op1), |
293 | SCALAR_FLOAT_TYPE_P (type) | |
294 | ? build_real (type, dconstm1) | |
295 | : build_int_cst_type (type, -1))); | |
c8a2ab6d SP |
296 | |
297 | default: | |
2412d35c SP |
298 | { |
299 | int size = 0; | |
300 | if ((tree_contains_chrecs (op0, &size) | |
301 | || tree_contains_chrecs (op1, &size)) | |
302 | && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) | |
303 | return build2 (code, type, op0, op1); | |
304 | else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) | |
1c1205fb RG |
305 | return fold_build2 (code, type, |
306 | fold_convert (type, op0), | |
307 | fold_convert (type, op1)); | |
2412d35c SP |
308 | else |
309 | return chrec_dont_know; | |
310 | } | |
c8a2ab6d SP |
311 | } |
312 | } | |
313 | } | |
314 | ||
315 | /* Fold the addition of two chrecs. */ | |
316 | ||
317 | tree | |
318 | chrec_fold_plus (tree type, | |
319 | tree op0, | |
320 | tree op1) | |
321 | { | |
322 | if (integer_zerop (op0)) | |
323 | return op1; | |
324 | if (integer_zerop (op1)) | |
325 | return op0; | |
326 | ||
327 | return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1); | |
328 | } | |
329 | ||
330 | /* Fold the subtraction of two chrecs. */ | |
331 | ||
332 | tree | |
333 | chrec_fold_minus (tree type, | |
334 | tree op0, | |
335 | tree op1) | |
336 | { | |
337 | if (integer_zerop (op1)) | |
338 | return op0; | |
339 | ||
340 | return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); | |
341 | } | |
342 | ||
343 | /* Fold the multiplication of two chrecs. */ | |
344 | ||
345 | tree | |
346 | chrec_fold_multiply (tree type, | |
347 | tree op0, | |
348 | tree op1) | |
349 | { | |
350 | if (automatically_generated_chrec_p (op0) | |
351 | || automatically_generated_chrec_p (op1)) | |
352 | return chrec_fold_automatically_generated_operands (op0, op1); | |
353 | ||
354 | switch (TREE_CODE (op0)) | |
355 | { | |
356 | case POLYNOMIAL_CHREC: | |
357 | switch (TREE_CODE (op1)) | |
358 | { | |
359 | case POLYNOMIAL_CHREC: | |
360 | return chrec_fold_multiply_poly_poly (type, op0, op1); | |
361 | ||
362 | default: | |
363 | if (integer_onep (op1)) | |
364 | return op0; | |
365 | if (integer_zerop (op1)) | |
e6845c23 | 366 | return build_int_cst_type (type, 0); |
c8a2ab6d SP |
367 | |
368 | return build_polynomial_chrec | |
369 | (CHREC_VARIABLE (op0), | |
370 | chrec_fold_multiply (type, CHREC_LEFT (op0), op1), | |
371 | chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); | |
372 | } | |
373 | ||
374 | default: | |
375 | if (integer_onep (op0)) | |
376 | return op1; | |
377 | ||
378 | if (integer_zerop (op0)) | |
e6845c23 | 379 | return build_int_cst_type (type, 0); |
c8a2ab6d SP |
380 | |
381 | switch (TREE_CODE (op1)) | |
382 | { | |
383 | case POLYNOMIAL_CHREC: | |
384 | return build_polynomial_chrec | |
385 | (CHREC_VARIABLE (op1), | |
386 | chrec_fold_multiply (type, CHREC_LEFT (op1), op0), | |
387 | chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); | |
388 | ||
389 | default: | |
390 | if (integer_onep (op1)) | |
391 | return op0; | |
392 | if (integer_zerop (op1)) | |
e6845c23 | 393 | return build_int_cst_type (type, 0); |
2412d35c | 394 | return fold_build2 (MULT_EXPR, type, op0, op1); |
c8a2ab6d SP |
395 | } |
396 | } | |
397 | } | |
398 | ||
399 | \f | |
400 | ||
401 | /* Operations. */ | |
402 | ||
1a9dddad RS |
403 | /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate |
404 | calculation overflows, otherwise return C(n,k) with type TYPE. */ | |
405 | ||
c8a2ab6d | 406 | static tree |
1a9dddad | 407 | tree_fold_binomial (tree type, tree n, unsigned int k) |
c8a2ab6d | 408 | { |
1a9dddad RS |
409 | unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; |
410 | HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum; | |
411 | unsigned int i; | |
412 | tree res; | |
413 | ||
414 | /* Handle the most frequent cases. */ | |
415 | if (k == 0) | |
416 | return build_int_cst (type, 1); | |
417 | if (k == 1) | |
418 | return fold_convert (type, n); | |
419 | ||
420 | /* Check that k <= n. */ | |
421 | if (TREE_INT_CST_HIGH (n) == 0 | |
422 | && TREE_INT_CST_LOW (n) < k) | |
423 | return NULL_TREE; | |
424 | ||
425 | /* Numerator = n. */ | |
426 | lnum = TREE_INT_CST_LOW (n); | |
427 | hnum = TREE_INT_CST_HIGH (n); | |
428 | ||
429 | /* Denominator = 2. */ | |
430 | ldenom = 2; | |
431 | hdenom = 0; | |
432 | ||
433 | /* Index = Numerator-1. */ | |
434 | if (lnum == 0) | |
435 | { | |
436 | hidx = hnum - 1; | |
437 | lidx = ~ (unsigned HOST_WIDE_INT) 0; | |
438 | } | |
c8a2ab6d | 439 | else |
1a9dddad RS |
440 | { |
441 | hidx = hnum; | |
442 | lidx = lnum - 1; | |
443 | } | |
c8a2ab6d | 444 | |
1a9dddad RS |
445 | /* Numerator = Numerator*Index = n*(n-1). */ |
446 | if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) | |
447 | return NULL_TREE; | |
c8a2ab6d | 448 | |
1a9dddad RS |
449 | for (i = 3; i <= k; i++) |
450 | { | |
451 | /* Index--. */ | |
452 | if (lidx == 0) | |
453 | { | |
454 | hidx--; | |
455 | lidx = ~ (unsigned HOST_WIDE_INT) 0; | |
456 | } | |
457 | else | |
458 | lidx--; | |
459 | ||
460 | /* Numerator *= Index. */ | |
461 | if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) | |
462 | return NULL_TREE; | |
463 | ||
464 | /* Denominator *= i. */ | |
465 | mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom); | |
466 | } | |
467 | ||
468 | /* Result = Numerator / Denominator. */ | |
469 | div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom, | |
470 | &lres, &hres, &ldum, &hdum); | |
471 | ||
472 | res = build_int_cst_wide (type, lres, hres); | |
473 | return int_fits_type_p (res, type) ? res : NULL_TREE; | |
c8a2ab6d SP |
474 | } |
475 | ||
476 | /* Helper function. Use the Newton's interpolating formula for | |
477 | evaluating the value of the evolution function. */ | |
478 | ||
479 | static tree | |
1a9dddad | 480 | chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) |
c8a2ab6d | 481 | { |
1a9dddad RS |
482 | tree arg0, arg1, binomial_n_k; |
483 | tree type = TREE_TYPE (chrec); | |
484 | ||
485 | while (TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
486 | && CHREC_VARIABLE (chrec) > var) | |
487 | chrec = CHREC_LEFT (chrec); | |
488 | ||
489 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
490 | && CHREC_VARIABLE (chrec) == var) | |
c8a2ab6d | 491 | { |
1a9dddad RS |
492 | arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1); |
493 | if (arg0 == chrec_dont_know) | |
494 | return chrec_dont_know; | |
495 | binomial_n_k = tree_fold_binomial (type, n, k); | |
496 | if (!binomial_n_k) | |
497 | return chrec_dont_know; | |
2412d35c SP |
498 | arg1 = fold_build2 (MULT_EXPR, type, |
499 | CHREC_LEFT (chrec), binomial_n_k); | |
1a9dddad | 500 | return chrec_fold_plus (type, arg0, arg1); |
c8a2ab6d | 501 | } |
1a9dddad RS |
502 | |
503 | binomial_n_k = tree_fold_binomial (type, n, k); | |
504 | if (!binomial_n_k) | |
505 | return chrec_dont_know; | |
506 | ||
2412d35c | 507 | return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k); |
c8a2ab6d SP |
508 | } |
509 | ||
510 | /* Evaluates "CHREC (X)" when the varying variable is VAR. | |
511 | Example: Given the following parameters, | |
512 | ||
513 | var = 1 | |
514 | chrec = {3, +, 4}_1 | |
515 | x = 10 | |
516 | ||
517 | The result is given by the Newton's interpolating formula: | |
518 | 3 * \binom{10}{0} + 4 * \binom{10}{1}. | |
519 | */ | |
520 | ||
521 | tree | |
522 | chrec_apply (unsigned var, | |
523 | tree chrec, | |
524 | tree x) | |
525 | { | |
526 | tree type = chrec_type (chrec); | |
527 | tree res = chrec_dont_know; | |
528 | ||
529 | if (automatically_generated_chrec_p (chrec) | |
530 | || automatically_generated_chrec_p (x) | |
531 | ||
532 | /* When the symbols are defined in an outer loop, it is possible | |
533 | to symbolically compute the apply, since the symbols are | |
534 | constants with respect to the varying loop. */ | |
535 | || chrec_contains_symbols_defined_in_loop (chrec, var) | |
536 | || chrec_contains_symbols (x)) | |
537 | return chrec_dont_know; | |
538 | ||
539 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
540 | fprintf (dump_file, "(chrec_apply \n"); | |
541 | ||
3c0c8f9d SP |
542 | if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) |
543 | x = build_real_from_int_cst (type, x); | |
544 | ||
c8a2ab6d SP |
545 | if (evolution_function_is_affine_p (chrec)) |
546 | { | |
547 | /* "{a, +, b} (x)" -> "a + b*x". */ | |
548 | if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST | |
549 | && integer_zerop (CHREC_LEFT (chrec))) | |
550 | res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x); | |
551 | ||
552 | else | |
553 | res = chrec_fold_plus (type, CHREC_LEFT (chrec), | |
554 | chrec_fold_multiply (type, | |
555 | CHREC_RIGHT (chrec), x)); | |
556 | } | |
557 | ||
558 | else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) | |
559 | res = chrec; | |
560 | ||
561 | else if (TREE_CODE (x) == INTEGER_CST | |
562 | && tree_int_cst_sgn (x) == 1) | |
563 | /* testsuite/.../ssa-chrec-38.c. */ | |
1a9dddad | 564 | res = chrec_evaluate (var, chrec, x, 0); |
c8a2ab6d SP |
565 | |
566 | else | |
567 | res = chrec_dont_know; | |
568 | ||
569 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
570 | { | |
571 | fprintf (dump_file, " (varying_loop = %d\n", var); | |
572 | fprintf (dump_file, ")\n (chrec = "); | |
573 | print_generic_expr (dump_file, chrec, 0); | |
574 | fprintf (dump_file, ")\n (x = "); | |
575 | print_generic_expr (dump_file, x, 0); | |
576 | fprintf (dump_file, ")\n (res = "); | |
577 | print_generic_expr (dump_file, res, 0); | |
578 | fprintf (dump_file, "))\n"); | |
579 | } | |
580 | ||
581 | return res; | |
582 | } | |
583 | ||
584 | /* Replaces the initial condition in CHREC with INIT_COND. */ | |
585 | ||
586 | tree | |
587 | chrec_replace_initial_condition (tree chrec, | |
588 | tree init_cond) | |
589 | { | |
590 | if (automatically_generated_chrec_p (chrec)) | |
591 | return chrec; | |
592 | ||
593 | switch (TREE_CODE (chrec)) | |
594 | { | |
595 | case POLYNOMIAL_CHREC: | |
596 | return build_polynomial_chrec | |
597 | (CHREC_VARIABLE (chrec), | |
598 | chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), | |
599 | CHREC_RIGHT (chrec)); | |
600 | ||
601 | default: | |
602 | return init_cond; | |
603 | } | |
604 | } | |
605 | ||
606 | /* Returns the initial condition of a given CHREC. */ | |
607 | ||
608 | tree | |
609 | initial_condition (tree chrec) | |
610 | { | |
611 | if (automatically_generated_chrec_p (chrec)) | |
612 | return chrec; | |
613 | ||
614 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) | |
615 | return initial_condition (CHREC_LEFT (chrec)); | |
616 | else | |
617 | return chrec; | |
618 | } | |
619 | ||
620 | /* Returns a univariate function that represents the evolution in | |
621 | LOOP_NUM. Mask the evolution of any other loop. */ | |
622 | ||
623 | tree | |
624 | hide_evolution_in_other_loops_than_loop (tree chrec, | |
625 | unsigned loop_num) | |
626 | { | |
627 | if (automatically_generated_chrec_p (chrec)) | |
628 | return chrec; | |
629 | ||
630 | switch (TREE_CODE (chrec)) | |
631 | { | |
632 | case POLYNOMIAL_CHREC: | |
633 | if (CHREC_VARIABLE (chrec) == loop_num) | |
634 | return build_polynomial_chrec | |
635 | (loop_num, | |
636 | hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), | |
637 | loop_num), | |
638 | CHREC_RIGHT (chrec)); | |
639 | ||
640 | else if (CHREC_VARIABLE (chrec) < loop_num) | |
641 | /* There is no evolution in this loop. */ | |
642 | return initial_condition (chrec); | |
643 | ||
644 | else | |
645 | return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), | |
646 | loop_num); | |
647 | ||
648 | default: | |
649 | return chrec; | |
650 | } | |
651 | } | |
652 | ||
6775f1f3 IR |
653 | /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is |
654 | true, otherwise returns the initial condition in LOOP_NUM. */ | |
c8a2ab6d | 655 | |
6775f1f3 IR |
656 | static tree |
657 | chrec_component_in_loop_num (tree chrec, | |
658 | unsigned loop_num, | |
659 | bool right) | |
c8a2ab6d | 660 | { |
6775f1f3 IR |
661 | tree component; |
662 | ||
c8a2ab6d SP |
663 | if (automatically_generated_chrec_p (chrec)) |
664 | return chrec; | |
665 | ||
666 | switch (TREE_CODE (chrec)) | |
667 | { | |
668 | case POLYNOMIAL_CHREC: | |
669 | if (CHREC_VARIABLE (chrec) == loop_num) | |
670 | { | |
6775f1f3 IR |
671 | if (right) |
672 | component = CHREC_RIGHT (chrec); | |
673 | else | |
674 | component = CHREC_LEFT (chrec); | |
675 | ||
c8a2ab6d SP |
676 | if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC |
677 | || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) | |
6775f1f3 | 678 | return component; |
c8a2ab6d SP |
679 | |
680 | else | |
681 | return build_polynomial_chrec | |
682 | (loop_num, | |
6775f1f3 IR |
683 | chrec_component_in_loop_num (CHREC_LEFT (chrec), |
684 | loop_num, | |
685 | right), | |
686 | component); | |
c8a2ab6d SP |
687 | } |
688 | ||
689 | else if (CHREC_VARIABLE (chrec) < loop_num) | |
690 | /* There is no evolution part in this loop. */ | |
691 | return NULL_TREE; | |
692 | ||
693 | else | |
6775f1f3 IR |
694 | return chrec_component_in_loop_num (CHREC_LEFT (chrec), |
695 | loop_num, | |
696 | right); | |
c8a2ab6d | 697 | |
6775f1f3 IR |
698 | default: |
699 | if (right) | |
700 | return NULL_TREE; | |
701 | else | |
702 | return chrec; | |
c8a2ab6d SP |
703 | } |
704 | } | |
705 | ||
6775f1f3 | 706 | /* Returns the evolution part in LOOP_NUM. Example: the call |
86df10e3 | 707 | evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns |
6775f1f3 IR |
708 | {1, +, 2}_1 */ |
709 | ||
710 | tree | |
711 | evolution_part_in_loop_num (tree chrec, | |
712 | unsigned loop_num) | |
713 | { | |
714 | return chrec_component_in_loop_num (chrec, loop_num, true); | |
715 | } | |
716 | ||
717 | /* Returns the initial condition in LOOP_NUM. Example: the call | |
86df10e3 | 718 | initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns |
6775f1f3 IR |
719 | {0, +, 1}_1 */ |
720 | ||
721 | tree | |
722 | initial_condition_in_loop_num (tree chrec, | |
723 | unsigned loop_num) | |
724 | { | |
725 | return chrec_component_in_loop_num (chrec, loop_num, false); | |
726 | } | |
727 | ||
c8a2ab6d SP |
728 | /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. |
729 | This function is essentially used for setting the evolution to | |
730 | chrec_dont_know, for example after having determined that it is | |
731 | impossible to say how many times a loop will execute. */ | |
732 | ||
733 | tree | |
734 | reset_evolution_in_loop (unsigned loop_num, | |
735 | tree chrec, | |
736 | tree new_evol) | |
737 | { | |
738 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
739 | && CHREC_VARIABLE (chrec) > loop_num) | |
6be74c4f JJ |
740 | { |
741 | tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), | |
742 | new_evol); | |
743 | tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), | |
744 | new_evol); | |
745 | return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), | |
746 | build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)), | |
747 | left, right); | |
748 | } | |
749 | ||
c8a2ab6d SP |
750 | while (TREE_CODE (chrec) == POLYNOMIAL_CHREC |
751 | && CHREC_VARIABLE (chrec) == loop_num) | |
752 | chrec = CHREC_LEFT (chrec); | |
753 | ||
754 | return build_polynomial_chrec (loop_num, chrec, new_evol); | |
755 | } | |
756 | ||
757 | /* Merges two evolution functions that were found by following two | |
758 | alternate paths of a conditional expression. */ | |
759 | ||
760 | tree | |
761 | chrec_merge (tree chrec1, | |
762 | tree chrec2) | |
763 | { | |
764 | if (chrec1 == chrec_dont_know | |
765 | || chrec2 == chrec_dont_know) | |
766 | return chrec_dont_know; | |
767 | ||
768 | if (chrec1 == chrec_known | |
769 | || chrec2 == chrec_known) | |
770 | return chrec_known; | |
771 | ||
772 | if (chrec1 == chrec_not_analyzed_yet) | |
773 | return chrec2; | |
774 | if (chrec2 == chrec_not_analyzed_yet) | |
775 | return chrec1; | |
776 | ||
777 | if (operand_equal_p (chrec1, chrec2, 0)) | |
778 | return chrec1; | |
779 | ||
780 | return chrec_dont_know; | |
781 | } | |
782 | ||
783 | \f | |
784 | ||
785 | /* Observers. */ | |
786 | ||
787 | /* Helper function for is_multivariate_chrec. */ | |
788 | ||
789 | static bool | |
790 | is_multivariate_chrec_rec (tree chrec, unsigned int rec_var) | |
791 | { | |
792 | if (chrec == NULL_TREE) | |
793 | return false; | |
794 | ||
795 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) | |
796 | { | |
797 | if (CHREC_VARIABLE (chrec) != rec_var) | |
798 | return true; | |
799 | else | |
800 | return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) | |
801 | || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var)); | |
802 | } | |
803 | else | |
804 | return false; | |
805 | } | |
806 | ||
807 | /* Determine whether the given chrec is multivariate or not. */ | |
808 | ||
809 | bool | |
810 | is_multivariate_chrec (tree chrec) | |
811 | { | |
812 | if (chrec == NULL_TREE) | |
813 | return false; | |
814 | ||
815 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) | |
816 | return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), | |
817 | CHREC_VARIABLE (chrec)) | |
818 | || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), | |
819 | CHREC_VARIABLE (chrec))); | |
820 | else | |
821 | return false; | |
822 | } | |
823 | ||
824 | /* Determines whether the chrec contains symbolic names or not. */ | |
825 | ||
826 | bool | |
827 | chrec_contains_symbols (tree chrec) | |
828 | { | |
829 | if (chrec == NULL_TREE) | |
830 | return false; | |
831 | ||
832 | if (TREE_CODE (chrec) == SSA_NAME | |
833 | || TREE_CODE (chrec) == VAR_DECL | |
834 | || TREE_CODE (chrec) == PARM_DECL | |
835 | || TREE_CODE (chrec) == FUNCTION_DECL | |
836 | || TREE_CODE (chrec) == LABEL_DECL | |
837 | || TREE_CODE (chrec) == RESULT_DECL | |
838 | || TREE_CODE (chrec) == FIELD_DECL) | |
839 | return true; | |
840 | ||
841 | switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) | |
842 | { | |
843 | case 3: | |
844 | if (chrec_contains_symbols (TREE_OPERAND (chrec, 2))) | |
845 | return true; | |
846 | ||
847 | case 2: | |
848 | if (chrec_contains_symbols (TREE_OPERAND (chrec, 1))) | |
849 | return true; | |
850 | ||
851 | case 1: | |
852 | if (chrec_contains_symbols (TREE_OPERAND (chrec, 0))) | |
853 | return true; | |
854 | ||
855 | default: | |
856 | return false; | |
857 | } | |
858 | } | |
859 | ||
860 | /* Determines whether the chrec contains undetermined coefficients. */ | |
861 | ||
862 | bool | |
863 | chrec_contains_undetermined (tree chrec) | |
864 | { | |
865 | if (chrec == chrec_dont_know | |
866 | || chrec == chrec_not_analyzed_yet | |
867 | || chrec == NULL_TREE) | |
868 | return true; | |
869 | ||
870 | switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) | |
871 | { | |
872 | case 3: | |
873 | if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2))) | |
874 | return true; | |
875 | ||
876 | case 2: | |
877 | if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1))) | |
878 | return true; | |
879 | ||
880 | case 1: | |
881 | if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0))) | |
882 | return true; | |
883 | ||
884 | default: | |
885 | return false; | |
886 | } | |
887 | } | |
888 | ||
2412d35c SP |
889 | /* Determines whether the tree EXPR contains chrecs, and increment |
890 | SIZE if it is not a NULL pointer by an estimation of the depth of | |
891 | the tree. */ | |
c8a2ab6d SP |
892 | |
893 | bool | |
2412d35c | 894 | tree_contains_chrecs (tree expr, int *size) |
c8a2ab6d SP |
895 | { |
896 | if (expr == NULL_TREE) | |
897 | return false; | |
2412d35c SP |
898 | |
899 | if (size) | |
900 | (*size)++; | |
c8a2ab6d SP |
901 | |
902 | if (tree_is_chrec (expr)) | |
903 | return true; | |
2412d35c | 904 | |
c8a2ab6d SP |
905 | switch (TREE_CODE_LENGTH (TREE_CODE (expr))) |
906 | { | |
907 | case 3: | |
2412d35c | 908 | if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size)) |
c8a2ab6d SP |
909 | return true; |
910 | ||
911 | case 2: | |
2412d35c | 912 | if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size)) |
c8a2ab6d SP |
913 | return true; |
914 | ||
915 | case 1: | |
2412d35c | 916 | if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size)) |
c8a2ab6d SP |
917 | return true; |
918 | ||
919 | default: | |
920 | return false; | |
921 | } | |
922 | } | |
923 | ||
1e8552eb SP |
924 | /* Recursive helper function. */ |
925 | ||
926 | static bool | |
927 | evolution_function_is_invariant_rec_p (tree chrec, int loopnum) | |
928 | { | |
929 | if (evolution_function_is_constant_p (chrec)) | |
930 | return true; | |
931 | ||
932 | if (TREE_CODE (chrec) == SSA_NAME | |
933 | && expr_invariant_in_loop_p (current_loops->parray[loopnum], | |
934 | chrec)) | |
935 | return true; | |
936 | ||
937 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC | |
938 | && CHREC_VARIABLE (chrec) == (unsigned) loopnum) | |
939 | return false; | |
940 | ||
941 | switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) | |
942 | { | |
943 | case 2: | |
944 | if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), | |
945 | loopnum)) | |
946 | return false; | |
947 | ||
948 | case 1: | |
949 | if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), | |
950 | loopnum)) | |
951 | return false; | |
952 | return true; | |
953 | ||
954 | default: | |
955 | return false; | |
956 | } | |
957 | ||
958 | return false; | |
959 | } | |
960 | ||
961 | /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ | |
962 | ||
963 | bool | |
964 | evolution_function_is_invariant_p (tree chrec, int loopnum) | |
965 | { | |
966 | if (evolution_function_is_constant_p (chrec)) | |
967 | return true; | |
968 | ||
969 | if (current_loops != NULL) | |
970 | return evolution_function_is_invariant_rec_p (chrec, loopnum); | |
971 | ||
972 | return false; | |
973 | } | |
974 | ||
c8a2ab6d SP |
975 | /* Determine whether the given tree is an affine multivariate |
976 | evolution. */ | |
977 | ||
978 | bool | |
979 | evolution_function_is_affine_multivariate_p (tree chrec) | |
980 | { | |
981 | if (chrec == NULL_TREE) | |
982 | return false; | |
983 | ||
984 | switch (TREE_CODE (chrec)) | |
985 | { | |
986 | case POLYNOMIAL_CHREC: | |
987 | if (evolution_function_is_constant_p (CHREC_LEFT (chrec))) | |
988 | { | |
989 | if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))) | |
990 | return true; | |
991 | else | |
992 | { | |
993 | if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC | |
994 | && CHREC_VARIABLE (CHREC_RIGHT (chrec)) | |
995 | != CHREC_VARIABLE (chrec) | |
996 | && evolution_function_is_affine_multivariate_p | |
997 | (CHREC_RIGHT (chrec))) | |
998 | return true; | |
999 | else | |
1000 | return false; | |
1001 | } | |
1002 | } | |
1003 | else | |
1004 | { | |
1005 | if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)) | |
1006 | && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC | |
1007 | && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) | |
1008 | && evolution_function_is_affine_multivariate_p | |
1009 | (CHREC_LEFT (chrec))) | |
1010 | return true; | |
1011 | else | |
1012 | return false; | |
1013 | } | |
1014 | ||
1015 | default: | |
1016 | return false; | |
1017 | } | |
1018 | } | |
1019 | ||
1020 | /* Determine whether the given tree is a function in zero or one | |
1021 | variables. */ | |
1022 | ||
1023 | bool | |
1024 | evolution_function_is_univariate_p (tree chrec) | |
1025 | { | |
1026 | if (chrec == NULL_TREE) | |
1027 | return true; | |
1028 | ||
1029 | switch (TREE_CODE (chrec)) | |
1030 | { | |
1031 | case POLYNOMIAL_CHREC: | |
1032 | switch (TREE_CODE (CHREC_LEFT (chrec))) | |
1033 | { | |
1034 | case POLYNOMIAL_CHREC: | |
1035 | if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec))) | |
1036 | return false; | |
1037 | if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) | |
1038 | return false; | |
1039 | break; | |
1040 | ||
1041 | default: | |
1042 | break; | |
1043 | } | |
1044 | ||
1045 | switch (TREE_CODE (CHREC_RIGHT (chrec))) | |
1046 | { | |
1047 | case POLYNOMIAL_CHREC: | |
1048 | if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec))) | |
1049 | return false; | |
1050 | if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) | |
1051 | return false; | |
1052 | break; | |
1053 | ||
1054 | default: | |
1055 | break; | |
1056 | } | |
1057 | ||
1058 | default: | |
1059 | return true; | |
1060 | } | |
1061 | } | |
1062 | ||
86df10e3 SP |
1063 | /* Returns the number of variables of CHREC. Example: the call |
1064 | nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ | |
1065 | ||
1066 | unsigned | |
1067 | nb_vars_in_chrec (tree chrec) | |
1068 | { | |
1069 | if (chrec == NULL_TREE) | |
1070 | return 0; | |
1071 | ||
1072 | switch (TREE_CODE (chrec)) | |
1073 | { | |
1074 | case POLYNOMIAL_CHREC: | |
1075 | return 1 + nb_vars_in_chrec | |
1076 | (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); | |
1077 | ||
1078 | default: | |
1079 | return 0; | |
1080 | } | |
1081 | } | |
1082 | ||
c8a2ab6d SP |
1083 | \f |
1084 | ||
1e8552eb SP |
1085 | /* Convert CHREC to TYPE. When the analyzer knows the context in |
1086 | which the CHREC is built, it sets AT_STMT to the statement that | |
1087 | contains the definition of the analyzed variable, otherwise the | |
1088 | conversion is less accurate: the information is used for | |
1089 | determining a more accurate estimation of the number of iterations. | |
1090 | By default AT_STMT could be safely set to NULL_TREE. | |
1091 | ||
1092 | The following rule is always true: TREE_TYPE (chrec) == | |
1093 | TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). | |
1094 | An example of what could happen when adding two chrecs and the type | |
1095 | of the CHREC_RIGHT is different than CHREC_LEFT is: | |
c4cdbeb4 EB |
1096 | |
1097 | {(uint) 0, +, (uchar) 10} + | |
1098 | {(uint) 0, +, (uchar) 250} | |
1099 | ||
1100 | that would produce a wrong result if CHREC_RIGHT is not (uint): | |
1101 | ||
1102 | {(uint) 0, +, (uchar) 4} | |
1103 | ||
1104 | instead of | |
1105 | ||
1106 | {(uint) 0, +, (uint) 260} | |
1107 | */ | |
c8a2ab6d SP |
1108 | |
1109 | tree | |
1e8552eb | 1110 | chrec_convert (tree type, tree chrec, tree at_stmt) |
c8a2ab6d | 1111 | { |
1e8552eb SP |
1112 | tree ct, res; |
1113 | ||
c8a2ab6d SP |
1114 | if (automatically_generated_chrec_p (chrec)) |
1115 | return chrec; | |
1116 | ||
1117 | ct = chrec_type (chrec); | |
1118 | if (ct == type) | |
1119 | return chrec; | |
1120 | ||
1e8552eb | 1121 | if (evolution_function_is_affine_p (chrec)) |
c8a2ab6d | 1122 | { |
d7770457 SP |
1123 | tree step; |
1124 | bool dummy; | |
1125 | ||
1126 | /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x | |
1127 | when it is not possible to prove that the scev does not wrap. | |
1128 | See PR22236, where a sequence 1, 2, ..., 255 has to be | |
1129 | converted to signed char, but this would wrap: | |
1130 | 1, 2, ..., 127, -128, ... The result should not be | |
1131 | {(schar)1, +, (schar)1}_x, but instead, we should keep the | |
1132 | conversion: (schar) {(uchar)1, +, (uchar)1}_x. */ | |
1133 | if (scev_probably_wraps_p (type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec), | |
1134 | at_stmt, | |
1135 | current_loops->parray[CHREC_VARIABLE (chrec)], | |
1136 | &dummy, &dummy)) | |
1137 | return fold_convert (type, chrec); | |
1138 | ||
1139 | step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)], type, | |
1140 | CHREC_LEFT (chrec), CHREC_RIGHT (chrec), at_stmt); | |
1e8552eb SP |
1141 | if (!step) |
1142 | return fold_convert (type, chrec); | |
1143 | ||
c8a2ab6d | 1144 | return build_polynomial_chrec (CHREC_VARIABLE (chrec), |
1e8552eb SP |
1145 | chrec_convert (type, CHREC_LEFT (chrec), |
1146 | at_stmt), | |
1147 | step); | |
1148 | } | |
c8a2ab6d | 1149 | |
1e8552eb SP |
1150 | if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) |
1151 | return chrec_dont_know; | |
c8a2ab6d | 1152 | |
1e8552eb | 1153 | res = fold_convert (type, chrec); |
c4cdbeb4 | 1154 | |
1e8552eb SP |
1155 | /* Don't propagate overflows. */ |
1156 | if (CONSTANT_CLASS_P (res)) | |
1157 | { | |
1158 | TREE_CONSTANT_OVERFLOW (res) = 0; | |
1159 | TREE_OVERFLOW (res) = 0; | |
c8a2ab6d | 1160 | } |
1e8552eb SP |
1161 | |
1162 | /* But reject constants that don't fit in their type after conversion. | |
1163 | This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the | |
1164 | natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, | |
1165 | and can cause problems later when computing niters of loops. Note | |
1166 | that we don't do the check before converting because we don't want | |
1167 | to reject conversions of negative chrecs to unsigned types. */ | |
1168 | if (TREE_CODE (res) == INTEGER_CST | |
1169 | && TREE_CODE (type) == INTEGER_TYPE | |
1170 | && !int_fits_type_p (res, type)) | |
1171 | res = chrec_dont_know; | |
1172 | ||
1173 | return res; | |
c8a2ab6d SP |
1174 | } |
1175 | ||
1176 | /* Returns the type of the chrec. */ | |
1177 | ||
1178 | tree | |
1179 | chrec_type (tree chrec) | |
1180 | { | |
1181 | if (automatically_generated_chrec_p (chrec)) | |
1182 | return NULL_TREE; | |
1183 | ||
1184 | return TREE_TYPE (chrec); | |
1185 | } |