Line data Source code
1 : /* Chains of recurrences.
2 : Copyright (C) 2003-2026 Free Software Foundation, Inc.
3 : Contributed by Sebastian Pop <pop@cri.ensmp.fr>
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 3, 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 COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : /* This file implements operations on chains of recurrences. Chains
22 : of recurrences are used for modeling evolution functions of scalar
23 : variables.
24 : */
25 :
26 : #include "config.h"
27 : #include "system.h"
28 : #include "coretypes.h"
29 : #include "backend.h"
30 : #include "tree.h"
31 : #include "gimple-expr.h"
32 : #include "tree-pretty-print.h"
33 : #include "fold-const.h"
34 : #include "cfgloop.h"
35 : #include "tree-ssa-loop-ivopts.h"
36 : #include "tree-ssa-loop-niter.h"
37 : #include "tree-chrec.h"
38 : #include "gimple.h"
39 : #include "tree-ssa-loop.h"
40 : #include "dumpfile.h"
41 : #include "tree-scalar-evolution.h"
42 :
43 : /* Extended folder for chrecs. */
44 :
45 : /* Fold the addition of two polynomial functions. */
46 :
47 : static inline tree
48 87554 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : tree type,
50 : tree poly0,
51 : tree poly1)
52 : {
53 87554 : tree left, right;
54 87554 : class loop *loop0 = get_chrec_loop (poly0);
55 87554 : class loop *loop1 = get_chrec_loop (poly1);
56 :
57 87554 : gcc_assert (poly0);
58 87554 : gcc_assert (poly1);
59 87554 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
60 87554 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
61 87554 : if (POINTER_TYPE_P (chrec_type (poly0)))
62 868 : gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
63 : && useless_type_conversion_p (type, chrec_type (poly0)));
64 : else
65 86686 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
66 : && useless_type_conversion_p (type, chrec_type (poly1)));
67 :
68 : /*
69 : {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
70 : {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
71 : {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
72 87554 : if (flow_loop_nested_p (loop0, loop1))
73 : {
74 296 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
75 232 : return build_polynomial_chrec
76 232 : (CHREC_VARIABLE (poly1),
77 232 : chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
78 464 : CHREC_RIGHT (poly1));
79 : else
80 64 : return build_polynomial_chrec
81 128 : (CHREC_VARIABLE (poly1),
82 64 : chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
83 64 : chrec_fold_multiply (type, CHREC_RIGHT (poly1),
84 64 : SCALAR_FLOAT_TYPE_P (type)
85 0 : ? build_real (type, dconstm1)
86 128 : : build_int_cst_type (type, -1)));
87 : }
88 :
89 87258 : if (flow_loop_nested_p (loop1, loop0))
90 : {
91 602 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
92 556 : return build_polynomial_chrec
93 556 : (CHREC_VARIABLE (poly0),
94 556 : chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
95 1112 : CHREC_RIGHT (poly0));
96 : else
97 46 : return build_polynomial_chrec
98 46 : (CHREC_VARIABLE (poly0),
99 46 : chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
100 92 : CHREC_RIGHT (poly0));
101 : }
102 :
103 : /* This function should never be called for chrecs of loops that
104 : do not belong to the same loop nest. */
105 86656 : if (loop0 != loop1)
106 : {
107 : /* It still can happen if we are not in loop-closed SSA form. */
108 38 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
109 38 : return chrec_dont_know;
110 : }
111 :
112 86618 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
113 : {
114 31445 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
115 31445 : left = chrec_fold_plus
116 31445 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 31445 : right = chrec_fold_plus
118 31445 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : }
120 : else
121 : {
122 55173 : left = chrec_fold_minus
123 55173 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 55173 : right = chrec_fold_minus
125 55173 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : }
127 :
128 86618 : if (chrec_zerop (right))
129 : return left;
130 : /* When we have an evolution in a non-wrapping type and in the process of
131 : accumulating CHREC_RIGHT there was overflow this indicates in the
132 : association that happened in accumulating the CHRECs clearly involved UB.
133 : Avoid this. When accumulating two CHRECs we basically turn
134 : (a + INCR1) + INCR2 into a + (INCR1 + INCR2) which is not always valid.
135 : Note this check only catches few invalid cases. */
136 32540 : else if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
137 20935 : && TREE_CODE (right) == INTEGER_CST
138 35462 : && TREE_OVERFLOW (right))
139 5 : return chrec_dont_know;
140 : else
141 32657 : return build_polynomial_chrec
142 32657 : (CHREC_VARIABLE (poly0), left, right);
143 : }
144 :
145 :
146 :
147 : /* Fold the multiplication of two polynomial functions. */
148 :
149 : static inline tree
150 40565 : chrec_fold_multiply_poly_poly (tree type,
151 : tree poly0,
152 : tree poly1)
153 : {
154 40565 : tree t0, t1, t2;
155 40565 : int var;
156 40565 : class loop *loop0 = get_chrec_loop (poly0);
157 40565 : class loop *loop1 = get_chrec_loop (poly1);
158 :
159 40565 : gcc_assert (poly0);
160 40565 : gcc_assert (poly1);
161 40565 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
162 40565 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
163 40565 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
164 : && useless_type_conversion_p (type, chrec_type (poly1)));
165 :
166 : /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
167 : {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
168 : {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
169 40565 : if (flow_loop_nested_p (loop0, loop1))
170 : /* poly0 is a constant wrt. poly1. */
171 0 : return build_polynomial_chrec
172 0 : (CHREC_VARIABLE (poly1),
173 0 : chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
174 0 : CHREC_RIGHT (poly1));
175 :
176 40565 : if (flow_loop_nested_p (loop1, loop0))
177 : /* poly1 is a constant wrt. poly0. */
178 0 : return build_polynomial_chrec
179 0 : (CHREC_VARIABLE (poly0),
180 0 : chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
181 0 : CHREC_RIGHT (poly0));
182 :
183 40565 : if (loop0 != loop1)
184 : {
185 : /* It still can happen if we are not in loop-closed SSA form. */
186 0 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
187 0 : return chrec_dont_know;
188 : }
189 :
190 : /* poly0 and poly1 are two polynomials in the same variable,
191 : {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
192 :
193 : /* "a*c". */
194 40565 : t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
195 :
196 : /* "a*d + b*c". */
197 40565 : t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
198 121695 : t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
199 40565 : CHREC_RIGHT (poly0),
200 40565 : CHREC_LEFT (poly1)));
201 : /* "b*d". */
202 40565 : t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
203 : /* "a*d + b*c + b*d". */
204 40565 : t1 = chrec_fold_plus (type, t1, t2);
205 : /* "2*b*d". */
206 81130 : t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
207 39 : ? build_real (type, dconst2)
208 40526 : : build_int_cst (type, 2), t2);
209 :
210 40565 : var = CHREC_VARIABLE (poly0);
211 40565 : return build_polynomial_chrec (var, t0,
212 40565 : build_polynomial_chrec (var, t1, t2));
213 : }
214 :
215 : /* When the operands are automatically_generated_chrec_p, the fold has
216 : to respect the semantics of the operands. */
217 :
218 : static inline tree
219 6031828 : chrec_fold_automatically_generated_operands (tree op0,
220 : tree op1)
221 : {
222 6031828 : if (op0 == chrec_dont_know
223 1001477 : || op1 == chrec_dont_know)
224 : return chrec_dont_know;
225 :
226 0 : if (op0 == chrec_known
227 0 : || op1 == chrec_known)
228 : return chrec_known;
229 :
230 0 : if (op0 == chrec_not_analyzed_yet
231 0 : || op1 == chrec_not_analyzed_yet)
232 0 : return chrec_not_analyzed_yet;
233 :
234 : /* The default case produces a safe result. */
235 : return chrec_dont_know;
236 : }
237 :
238 : /* Fold the addition of two chrecs. */
239 :
240 : static tree
241 30889254 : chrec_fold_plus_1 (enum tree_code code, tree type,
242 : tree op0, tree op1)
243 : {
244 61778508 : if (automatically_generated_chrec_p (op0)
245 30889254 : || automatically_generated_chrec_p (op1))
246 0 : return chrec_fold_automatically_generated_operands (op0, op1);
247 :
248 30889254 : switch (TREE_CODE (op0))
249 : {
250 9853078 : case POLYNOMIAL_CHREC:
251 9853078 : gcc_checking_assert
252 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
253 9853078 : switch (TREE_CODE (op1))
254 : {
255 87554 : case POLYNOMIAL_CHREC:
256 87554 : gcc_checking_assert
257 : (!chrec_contains_symbols_defined_in_loop (op1,
258 : CHREC_VARIABLE (op1)));
259 87554 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
260 :
261 240149 : CASE_CONVERT:
262 240149 : if (tree_contains_chrecs (op1, NULL))
263 : {
264 : /* We can strip sign-conversions to signed by performing the
265 : operation in unsigned. */
266 697 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
267 697 : if (INTEGRAL_TYPE_P (type)
268 697 : && INTEGRAL_TYPE_P (optype)
269 672 : && tree_nop_conversion_p (type, optype)
270 896 : && TYPE_UNSIGNED (optype))
271 : {
272 79 : tree tem = chrec_convert (optype, op0, NULL);
273 79 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
274 15 : return chrec_convert (type,
275 : chrec_fold_plus_1 (code, optype,
276 : tem,
277 15 : TREE_OPERAND
278 : (op1, 0)),
279 15 : NULL);
280 : }
281 682 : return chrec_dont_know;
282 : }
283 : /* FALLTHRU */
284 :
285 9764827 : default:
286 9764827 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
287 8980184 : return build_polynomial_chrec
288 8980184 : (CHREC_VARIABLE (op0),
289 8980184 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
290 17960368 : CHREC_RIGHT (op0));
291 : else
292 784643 : return build_polynomial_chrec
293 784643 : (CHREC_VARIABLE (op0),
294 784643 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
295 1569286 : CHREC_RIGHT (op0));
296 : }
297 :
298 3126331 : CASE_CONVERT:
299 3126331 : if (tree_contains_chrecs (op0, NULL))
300 : {
301 : /* We can strip sign-conversions to signed by performing the
302 : operation in unsigned. */
303 76865 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
304 76865 : if (INTEGRAL_TYPE_P (type)
305 75438 : && INTEGRAL_TYPE_P (optype)
306 71400 : && tree_nop_conversion_p (type, optype)
307 138088 : && TYPE_UNSIGNED (optype))
308 122378 : return chrec_convert (type,
309 : chrec_fold_plus_1 (code, optype,
310 61189 : TREE_OPERAND (op0, 0),
311 : chrec_convert (optype,
312 : op1, NULL)),
313 61189 : NULL);
314 15676 : return chrec_dont_know;
315 : }
316 : /* FALLTHRU */
317 :
318 20959311 : default:
319 20959311 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
320 20959311 : switch (TREE_CODE (op1))
321 : {
322 3085473 : case POLYNOMIAL_CHREC:
323 3085473 : gcc_checking_assert
324 : (!chrec_contains_symbols_defined_in_loop (op1,
325 : CHREC_VARIABLE (op1)));
326 3085473 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
327 3014346 : return build_polynomial_chrec
328 3014346 : (CHREC_VARIABLE (op1),
329 3014346 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
330 6028692 : CHREC_RIGHT (op1));
331 : else
332 71127 : return build_polynomial_chrec
333 142254 : (CHREC_VARIABLE (op1),
334 71127 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
335 71127 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
336 71127 : SCALAR_FLOAT_TYPE_P (type)
337 34 : ? build_real (type, dconstm1)
338 142220 : : build_int_cst_type (type, -1)));
339 :
340 2339294 : CASE_CONVERT:
341 2339294 : if (tree_contains_chrecs (op1, NULL))
342 : {
343 : /* We can strip sign-conversions to signed by performing the
344 : operation in unsigned. */
345 59942 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
346 59942 : if (INTEGRAL_TYPE_P (type)
347 21076 : && INTEGRAL_TYPE_P (optype)
348 21076 : && tree_nop_conversion_p (type, optype)
349 76857 : && TYPE_UNSIGNED (optype))
350 16915 : return chrec_convert (type,
351 : chrec_fold_plus_1 (code, optype,
352 : chrec_convert (optype,
353 : op0,
354 : NULL),
355 16915 : TREE_OPERAND (op1, 0)),
356 16915 : NULL);
357 43027 : return chrec_dont_know;
358 : }
359 : /* FALLTHRU */
360 :
361 17813896 : default:
362 17813896 : {
363 17813896 : int size = 0;
364 17813896 : if ((tree_contains_chrecs (op0, &size)
365 17813896 : || tree_contains_chrecs (op1, &size))
366 17813896 : && size < param_scev_max_expr_size)
367 0 : return build2 (code, type, op0, op1);
368 17813896 : else if (size < param_scev_max_expr_size)
369 : {
370 17813794 : if (code == POINTER_PLUS_EXPR)
371 3397279 : return fold_build_pointer_plus (fold_convert (type, op0),
372 : op1);
373 : else
374 14416515 : return fold_build2 (code, type,
375 : fold_convert (type, op0),
376 : fold_convert (type, op1));
377 : }
378 : else
379 102 : return chrec_dont_know;
380 : }
381 : }
382 : }
383 : }
384 :
385 : /* Fold the addition of two chrecs. */
386 :
387 : tree
388 37208329 : chrec_fold_plus (tree type,
389 : tree op0,
390 : tree op1)
391 : {
392 37208329 : enum tree_code code;
393 71407868 : if (automatically_generated_chrec_p (op0)
394 37208329 : || automatically_generated_chrec_p (op1))
395 3708740 : return chrec_fold_automatically_generated_operands (op0, op1);
396 :
397 33499589 : if (integer_zerop (op0))
398 4065027 : return chrec_convert (type, op1, NULL);
399 29434562 : if (integer_zerop (op1))
400 1879749 : return chrec_convert (type, op0, NULL);
401 :
402 27554813 : if (POINTER_TYPE_P (type))
403 : code = POINTER_PLUS_EXPR;
404 : else
405 21237375 : code = PLUS_EXPR;
406 :
407 27554813 : return chrec_fold_plus_1 (code, type, op0, op1);
408 : }
409 :
410 : /* Fold the subtraction of two chrecs. */
411 :
412 : tree
413 4119143 : chrec_fold_minus (tree type,
414 : tree op0,
415 : tree op1)
416 : {
417 7617422 : if (automatically_generated_chrec_p (op0)
418 4119143 : || automatically_generated_chrec_p (op1))
419 765073 : return chrec_fold_automatically_generated_operands (op0, op1);
420 :
421 3354070 : if (integer_zerop (op1))
422 : return op0;
423 :
424 3256322 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
425 : }
426 :
427 : /* Fold the multiplication of two chrecs. */
428 :
429 : tree
430 21630192 : chrec_fold_multiply (tree type,
431 : tree op0,
432 : tree op1)
433 : {
434 21630781 : if (automatically_generated_chrec_p (op0)
435 20230084 : || automatically_generated_chrec_p (op1))
436 1558015 : return chrec_fold_automatically_generated_operands (op0, op1);
437 :
438 20072766 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
439 16072319 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
440 : std::swap (op0, op1);
441 :
442 20072766 : switch (TREE_CODE (op0))
443 : {
444 4194934 : case POLYNOMIAL_CHREC:
445 4194934 : gcc_checking_assert
446 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
447 4194934 : switch (TREE_CODE (op1))
448 : {
449 40565 : case POLYNOMIAL_CHREC:
450 40565 : gcc_checking_assert
451 : (!chrec_contains_symbols_defined_in_loop (op1,
452 : CHREC_VARIABLE (op1)));
453 40565 : return chrec_fold_multiply_poly_poly (type, op0, op1);
454 :
455 60335 : CASE_CONVERT:
456 60335 : if (tree_contains_chrecs (op1, NULL))
457 : {
458 : /* We can strip sign-conversions to signed by performing the
459 : operation in unsigned. */
460 224 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
461 224 : if (INTEGRAL_TYPE_P (type)
462 224 : && INTEGRAL_TYPE_P (optype)
463 224 : && tree_nop_conversion_p (type, optype)
464 242 : && TYPE_UNSIGNED (optype))
465 : {
466 18 : tree tem = chrec_convert (optype, op0, NULL);
467 18 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
468 18 : return chrec_convert (type,
469 : chrec_fold_multiply (optype, tem,
470 18 : TREE_OPERAND
471 : (op1, 0)),
472 18 : NULL);
473 : }
474 206 : return chrec_dont_know;
475 : }
476 : /* FALLTHRU */
477 :
478 4154145 : default:
479 4154145 : if (integer_onep (op1))
480 : return op0;
481 4153694 : if (integer_zerop (op1))
482 410 : return build_int_cst (type, 0);
483 :
484 : /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
485 : same sign or CHREC_LEFT is zero then folding the multiply into
486 : the addition does not have the same behavior on overflow.
487 : Using unsigned arithmetic in that case causes too many performance
488 : regressions, but catch the constant case where the multiplication
489 : of the step overflows. */
490 4153284 : if (INTEGRAL_TYPE_P (type)
491 4153055 : && TYPE_OVERFLOW_UNDEFINED (type)
492 1073916 : && !integer_zerop (CHREC_LEFT (op0))
493 612736 : && TREE_CODE (op1) == INTEGER_CST
494 4586699 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
495 : {
496 339928 : wi::overflow_type ovf = wi::OVF_NONE;
497 339928 : wide_int res
498 339928 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
499 679856 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
500 339928 : if (ovf != wi::OVF_NONE)
501 : {
502 36 : tree utype = unsigned_type_for (type);
503 36 : tree uop1 = chrec_convert_rhs (utype, op1);
504 36 : tree uleft0 = chrec_convert_rhs (utype, CHREC_LEFT (op0));
505 36 : tree uright0 = chrec_convert_rhs (utype, CHREC_RIGHT (op0));
506 36 : tree left = chrec_fold_multiply (utype, uleft0, uop1);
507 36 : tree right = chrec_fold_multiply (utype, uright0, uop1);
508 36 : tree tem = build_polynomial_chrec (CHREC_VARIABLE (op0),
509 : left, right);
510 36 : return chrec_convert_rhs (type, tem);
511 : }
512 339928 : }
513 4153248 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
514 4153248 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
515 4153248 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
516 : }
517 :
518 4704374 : CASE_CONVERT:
519 4704374 : if (tree_contains_chrecs (op0, NULL))
520 : {
521 : /* We can strip sign-conversions to signed by performing the
522 : operation in unsigned. */
523 73419 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
524 73419 : if (INTEGRAL_TYPE_P (type)
525 73418 : && INTEGRAL_TYPE_P (optype)
526 73418 : && tree_nop_conversion_p (type, optype)
527 85738 : && TYPE_UNSIGNED (optype))
528 24588 : return chrec_convert (type,
529 : chrec_fold_multiply (optype,
530 12294 : TREE_OPERAND (op0, 0),
531 : chrec_convert (optype,
532 : op1,
533 : NULL)),
534 12294 : NULL);
535 61125 : return chrec_dont_know;
536 : }
537 : /* FALLTHRU */
538 :
539 15804413 : default:
540 15804413 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
541 15804413 : if (integer_onep (op0))
542 : return op1;
543 :
544 10753270 : if (integer_zerop (op0))
545 2338040 : return build_int_cst (type, 0);
546 :
547 8415230 : switch (TREE_CODE (op1))
548 : {
549 0 : case POLYNOMIAL_CHREC:
550 0 : gcc_unreachable ();
551 :
552 1014330 : CASE_CONVERT:
553 1014330 : if (tree_contains_chrecs (op1, NULL))
554 : return chrec_fold_multiply (type, op1, op0);
555 : /* FALLTHRU */
556 :
557 8414641 : default:
558 8414641 : if (integer_onep (op1))
559 : return op0;
560 8349919 : if (integer_zerop (op1))
561 1449 : return build_int_cst (type, 0);
562 8348470 : return fold_build2 (MULT_EXPR, type, op0, op1);
563 : }
564 : }
565 : }
566 :
567 :
568 :
569 : /* Operations. */
570 :
571 : /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
572 : calculation overflows, otherwise return C(n,k) with type TYPE. */
573 :
574 : static tree
575 11847 : tree_fold_binomial (tree type, tree n, unsigned int k)
576 : {
577 11847 : wi::overflow_type overflow;
578 11847 : unsigned int i;
579 :
580 : /* Handle the most frequent cases. */
581 11847 : if (k == 0)
582 3924 : return build_int_cst (type, 1);
583 7923 : if (k == 1)
584 3924 : return fold_convert (type, n);
585 :
586 3999 : widest_int num = wi::to_widest (n);
587 :
588 : /* Check that k <= n. */
589 3999 : if (wi::ltu_p (num, k))
590 : return NULL_TREE;
591 :
592 : /* Denominator = 2. */
593 3940 : widest_int denom = 2;
594 :
595 : /* Index = Numerator-1. */
596 3940 : widest_int idx = num - 1;
597 :
598 : /* Numerator = Numerator*Index = n*(n-1). */
599 3940 : num = wi::smul (num, idx, &overflow);
600 3940 : if (overflow)
601 : return NULL_TREE;
602 :
603 3946 : for (i = 3; i <= k; i++)
604 : {
605 : /* Index--. */
606 6 : --idx;
607 :
608 : /* Numerator *= Index. */
609 6 : num = wi::smul (num, idx, &overflow);
610 6 : if (overflow)
611 : return NULL_TREE;
612 :
613 : /* Denominator *= i. */
614 6 : denom *= i;
615 : }
616 :
617 : /* Result = Numerator / Denominator. */
618 3940 : num = wi::udiv_trunc (num, denom);
619 3940 : if (! wi::fits_to_tree_p (num, type))
620 : return NULL_TREE;
621 3930 : return wide_int_to_tree (type, num);
622 3999 : }
623 :
624 : /* Helper function. Use the Newton's interpolating formula for
625 : evaluating the value of the evolution function.
626 : The result may be in an unsigned type of CHREC. */
627 :
628 : static tree
629 11994 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
630 : {
631 11994 : tree arg0, arg1, binomial_n_k;
632 11994 : tree type = TREE_TYPE (chrec);
633 11994 : class loop *var_loop = get_loop (cfun, var);
634 :
635 11994 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
636 11994 : && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
637 0 : chrec = CHREC_LEFT (chrec);
638 :
639 : /* The formula associates the expression and thus we have to make
640 : sure to not introduce undefined overflow. */
641 11994 : tree ctype = type;
642 11994 : if (INTEGRAL_TYPE_P (type)
643 11994 : && ! TYPE_OVERFLOW_WRAPS (type))
644 11658 : ctype = unsigned_type_for (type);
645 :
646 11994 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
647 11994 : && CHREC_VARIABLE (chrec) == var)
648 : {
649 8001 : arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
650 8001 : if (arg1 == chrec_dont_know)
651 : return chrec_dont_know;
652 7854 : binomial_n_k = tree_fold_binomial (ctype, n, k);
653 7854 : if (!binomial_n_k)
654 0 : return chrec_dont_know;
655 7854 : tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
656 7854 : arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
657 7854 : return chrec_fold_plus (ctype, arg0, arg1);
658 : }
659 :
660 3993 : binomial_n_k = tree_fold_binomial (ctype, n, k);
661 3993 : if (!binomial_n_k)
662 69 : return chrec_dont_know;
663 :
664 3924 : return fold_build2 (MULT_EXPR, ctype,
665 : chrec_convert (ctype, chrec, NULL), binomial_n_k);
666 : }
667 :
668 : /* Evaluates "CHREC (X)" when the varying variable is VAR.
669 : Example: Given the following parameters,
670 :
671 : var = 1
672 : chrec = {3, +, 4}_1
673 : x = 10
674 :
675 : The result is given by the Newton's interpolating formula:
676 : 3 * \binom{10}{0} + 4 * \binom{10}{1}.
677 : */
678 :
679 : tree
680 903664 : chrec_apply (unsigned var,
681 : tree chrec,
682 : tree x)
683 : {
684 903664 : tree type = chrec_type (chrec);
685 903664 : tree res = chrec_dont_know;
686 :
687 1807328 : if (automatically_generated_chrec_p (chrec)
688 1023668 : || automatically_generated_chrec_p (x)
689 :
690 : /* When the symbols are defined in an outer loop, it is possible
691 : to symbolically compute the apply, since the symbols are
692 : constants with respect to the varying loop. */
693 903664 : || chrec_contains_symbols_defined_in_loop (chrec, var))
694 120004 : return chrec_dont_know;
695 :
696 783660 : if (dump_file && (dump_flags & TDF_SCEV))
697 0 : fprintf (dump_file, "(chrec_apply \n");
698 :
699 783660 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
700 122 : x = build_real_from_int_cst (type, x);
701 :
702 783660 : switch (TREE_CODE (chrec))
703 : {
704 782255 : case POLYNOMIAL_CHREC:
705 782255 : if (evolution_function_is_affine_p (chrec))
706 : {
707 776954 : tree chrecr = CHREC_RIGHT (chrec);
708 776954 : tree chrecl = CHREC_LEFT (chrec);
709 776954 : if (CHREC_VARIABLE (chrec) != var)
710 526 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
711 : chrec_apply (var, chrecl, x),
712 : chrec_apply (var, chrecr, x));
713 :
714 : /* "{a, +, a}" (x-1) -> "a*x". */
715 776428 : else if (operand_equal_p (chrecl, chrecr)
716 138385 : && TREE_CODE (x) == PLUS_EXPR
717 6919 : && integer_all_onesp (TREE_OPERAND (x, 1))
718 6666 : && !POINTER_TYPE_P (type)
719 783083 : && TYPE_PRECISION (TREE_TYPE (x))
720 6655 : >= TYPE_PRECISION (type))
721 : {
722 : /* We know the number of iterations can't be negative. */
723 4823 : res = build_int_cst (TREE_TYPE (x), 1);
724 4823 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
725 4823 : res = chrec_convert_rhs (type, res, NULL);
726 4823 : res = chrec_fold_multiply (type, chrecr, res);
727 : }
728 : /* "{a, +, b} (x)" -> "a + b*x". */
729 : else
730 : {
731 : /* The overall increment might not fit in a signed type so
732 : use an unsigned computation to get at the final value
733 : and avoid undefined signed overflow. */
734 771605 : tree utype = TREE_TYPE (chrecr);
735 771605 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
736 684733 : utype = unsigned_type_for (TREE_TYPE (chrecr));
737 771605 : res = chrec_convert_rhs (utype, x, NULL);
738 771605 : res = chrec_fold_multiply (utype,
739 : chrec_convert (utype, chrecr, NULL),
740 : res);
741 : /* When the resulting increment fits the original type
742 : do the increment in it. */
743 771605 : if (TREE_CODE (res) == INTEGER_CST
744 771605 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
745 : {
746 401291 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
747 401291 : res = chrec_fold_plus (type, chrecl, res);
748 : }
749 : else
750 : {
751 370314 : res = chrec_fold_plus (utype,
752 : chrec_convert (utype, chrecl, NULL),
753 : res);
754 370314 : res = chrec_convert (type, res, NULL);
755 : }
756 : }
757 : }
758 5301 : else if (TREE_CODE (x) == INTEGER_CST
759 5301 : && tree_int_cst_sgn (x) == 1)
760 : /* testsuite/.../ssa-chrec-38.c. */
761 3993 : res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
762 : else
763 1308 : res = chrec_dont_know;
764 : break;
765 :
766 247 : CASE_CONVERT:
767 247 : res = chrec_convert (TREE_TYPE (chrec),
768 247 : chrec_apply (var, TREE_OPERAND (chrec, 0), x),
769 : NULL);
770 247 : break;
771 :
772 : default:
773 : res = chrec;
774 : break;
775 : }
776 :
777 783660 : if (dump_file && (dump_flags & TDF_SCEV))
778 : {
779 0 : fprintf (dump_file, " (varying_loop = %d", var);
780 0 : fprintf (dump_file, ")\n (chrec = ");
781 0 : print_generic_expr (dump_file, chrec);
782 0 : fprintf (dump_file, ")\n (x = ");
783 0 : print_generic_expr (dump_file, x);
784 0 : fprintf (dump_file, ")\n (res = ");
785 0 : print_generic_expr (dump_file, res);
786 0 : fprintf (dump_file, "))\n");
787 : }
788 :
789 : return res;
790 : }
791 :
792 : /* For a given CHREC and an induction variable map IV_MAP that maps
793 : (loop->num, expr) for every loop number of the current_loops an
794 : expression, calls chrec_apply when the expression is not NULL. */
795 :
796 : tree
797 888 : chrec_apply_map (tree chrec, vec<tree> iv_map)
798 : {
799 888 : int i;
800 888 : tree expr;
801 :
802 9822 : FOR_EACH_VEC_ELT (iv_map, i, expr)
803 8934 : if (expr)
804 1592 : chrec = chrec_apply (i, chrec, expr);
805 :
806 888 : return chrec;
807 : }
808 :
809 : /* Replaces the initial condition in CHREC with INIT_COND. */
810 :
811 : tree
812 2351374 : chrec_replace_initial_condition (tree chrec,
813 : tree init_cond)
814 : {
815 2351374 : if (automatically_generated_chrec_p (chrec))
816 : return chrec;
817 :
818 2351374 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
819 :
820 2351374 : switch (TREE_CODE (chrec))
821 : {
822 1186121 : case POLYNOMIAL_CHREC:
823 1186121 : return build_polynomial_chrec
824 1186121 : (CHREC_VARIABLE (chrec),
825 1186121 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
826 2372242 : CHREC_RIGHT (chrec));
827 :
828 : default:
829 : return init_cond;
830 : }
831 : }
832 :
833 : /* Returns the initial condition of a given CHREC. */
834 :
835 : tree
836 11107849 : initial_condition (tree chrec)
837 : {
838 18160832 : if (automatically_generated_chrec_p (chrec))
839 : return chrec;
840 :
841 16881313 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
842 7052983 : return initial_condition (CHREC_LEFT (chrec));
843 : else
844 : return chrec;
845 : }
846 :
847 : /* Returns a univariate function that represents the evolution in
848 : LOOP_NUM. Mask the evolution of any other loop. */
849 :
850 : tree
851 48997019 : hide_evolution_in_other_loops_than_loop (tree chrec,
852 : unsigned loop_num)
853 : {
854 48999521 : class loop *loop = get_loop (cfun, loop_num), *chloop;
855 48999521 : if (automatically_generated_chrec_p (chrec))
856 : return chrec;
857 :
858 48999521 : switch (TREE_CODE (chrec))
859 : {
860 2574671 : case POLYNOMIAL_CHREC:
861 2574671 : chloop = get_chrec_loop (chrec);
862 :
863 2574671 : if (chloop == loop)
864 2111985 : return build_polynomial_chrec
865 2111985 : (loop_num,
866 2111985 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
867 : loop_num),
868 4223970 : CHREC_RIGHT (chrec));
869 :
870 462686 : else if (flow_loop_nested_p (chloop, loop))
871 : /* There is no evolution in this loop. */
872 460184 : return initial_condition (chrec);
873 :
874 2502 : else if (flow_loop_nested_p (loop, chloop))
875 2502 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
876 2502 : loop_num);
877 :
878 : else
879 0 : return chrec_dont_know;
880 :
881 : default:
882 : return chrec;
883 : }
884 : }
885 :
886 : /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
887 : true, otherwise returns the initial condition in LOOP_NUM. */
888 :
889 : static tree
890 40404547 : chrec_component_in_loop_num (tree chrec,
891 : unsigned loop_num,
892 : bool right)
893 : {
894 41587075 : tree component;
895 41587075 : class loop *loop = get_loop (cfun, loop_num), *chloop;
896 :
897 41587075 : if (automatically_generated_chrec_p (chrec))
898 : return chrec;
899 :
900 40307556 : switch (TREE_CODE (chrec))
901 : {
902 34719660 : case POLYNOMIAL_CHREC:
903 34719660 : chloop = get_chrec_loop (chrec);
904 :
905 34719660 : if (chloop == loop)
906 : {
907 33537132 : if (right)
908 17085173 : component = CHREC_RIGHT (chrec);
909 : else
910 16451959 : component = CHREC_LEFT (chrec);
911 :
912 33537132 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
913 33537132 : || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
914 : return component;
915 :
916 : else
917 0 : return build_polynomial_chrec
918 0 : (loop_num,
919 0 : chrec_component_in_loop_num (CHREC_LEFT (chrec),
920 : loop_num,
921 : right),
922 0 : component);
923 : }
924 :
925 1182528 : else if (flow_loop_nested_p (chloop, loop))
926 : /* There is no evolution part in this loop. */
927 : return NULL_TREE;
928 :
929 : else
930 : {
931 1182528 : gcc_assert (flow_loop_nested_p (loop, chloop));
932 1182528 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
933 : loop_num,
934 1182528 : right);
935 : }
936 :
937 5587896 : default:
938 5587896 : if (right)
939 : return NULL_TREE;
940 : else
941 869536 : return chrec;
942 : }
943 : }
944 :
945 : /* Returns the evolution part in LOOP_NUM. Example: the call
946 : evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
947 : {1, +, 2}_1 */
948 :
949 : tree
950 23083052 : evolution_part_in_loop_num (tree chrec,
951 : unsigned loop_num)
952 : {
953 23083052 : return chrec_component_in_loop_num (chrec, loop_num, true);
954 : }
955 :
956 : /* Returns the initial condition in LOOP_NUM. Example: the call
957 : initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
958 : {0, +, 1}_1 */
959 :
960 : tree
961 17321495 : initial_condition_in_loop_num (tree chrec,
962 : unsigned loop_num)
963 : {
964 17321495 : return chrec_component_in_loop_num (chrec, loop_num, false);
965 : }
966 :
967 : /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
968 : This function is essentially used for setting the evolution to
969 : chrec_dont_know, for example after having determined that it is
970 : impossible to say how many times a loop will execute. */
971 :
972 : tree
973 0 : reset_evolution_in_loop (unsigned loop_num,
974 : tree chrec,
975 : tree new_evol)
976 : {
977 0 : class loop *loop = get_loop (cfun, loop_num);
978 :
979 0 : if (POINTER_TYPE_P (chrec_type (chrec)))
980 0 : gcc_assert (ptrofftype_p (chrec_type (new_evol)));
981 : else
982 0 : gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
983 :
984 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
985 0 : && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
986 : {
987 0 : tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
988 : new_evol);
989 0 : tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
990 : new_evol);
991 0 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
992 : }
993 :
994 0 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
995 0 : && CHREC_VARIABLE (chrec) == loop_num)
996 0 : chrec = CHREC_LEFT (chrec);
997 :
998 0 : return build_polynomial_chrec (loop_num, chrec, new_evol);
999 : }
1000 :
1001 : /* Merges two evolution functions that were found by following two
1002 : alternate paths of a conditional expression. */
1003 :
1004 : tree
1005 16985333 : chrec_merge (tree chrec1,
1006 : tree chrec2)
1007 : {
1008 16985333 : if (chrec1 == chrec_dont_know
1009 16985333 : || chrec2 == chrec_dont_know)
1010 : return chrec_dont_know;
1011 :
1012 14159792 : if (chrec1 == chrec_known
1013 14159792 : || chrec2 == chrec_known)
1014 : return chrec_known;
1015 :
1016 14159792 : if (chrec1 == chrec_not_analyzed_yet)
1017 : return chrec2;
1018 3026907 : if (chrec2 == chrec_not_analyzed_yet)
1019 : return chrec1;
1020 :
1021 3026907 : if (eq_evolutions_p (chrec1, chrec2))
1022 : return chrec1;
1023 :
1024 2423321 : return chrec_dont_know;
1025 : }
1026 :
1027 :
1028 :
1029 : /* Observers. */
1030 :
1031 : /* Helper function for is_multivariate_chrec. */
1032 :
1033 : static bool
1034 0 : is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
1035 : {
1036 0 : if (chrec == NULL_TREE)
1037 : return false;
1038 :
1039 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1040 : {
1041 0 : if (CHREC_VARIABLE (chrec) != rec_var)
1042 : return true;
1043 : else
1044 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
1045 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
1046 : }
1047 : else
1048 : return false;
1049 : }
1050 :
1051 : /* Determine whether the given chrec is multivariate or not. */
1052 :
1053 : bool
1054 0 : is_multivariate_chrec (const_tree chrec)
1055 : {
1056 0 : if (chrec == NULL_TREE)
1057 : return false;
1058 :
1059 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1060 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
1061 0 : CHREC_VARIABLE (chrec))
1062 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
1063 0 : CHREC_VARIABLE (chrec)));
1064 : else
1065 : return false;
1066 : }
1067 :
1068 : /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
1069 : NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
1070 :
1071 : static bool
1072 37689091 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1073 : class loop *loop)
1074 : {
1075 37689091 : int i, n;
1076 :
1077 37689091 : if (chrec == NULL_TREE)
1078 : return false;
1079 :
1080 37689091 : if (TREE_CODE (chrec) == SSA_NAME
1081 : || VAR_P (chrec)
1082 : || TREE_CODE (chrec) == POLY_INT_CST
1083 : || TREE_CODE (chrec) == PARM_DECL
1084 : || TREE_CODE (chrec) == FUNCTION_DECL
1085 : || TREE_CODE (chrec) == LABEL_DECL
1086 : || TREE_CODE (chrec) == RESULT_DECL
1087 : || TREE_CODE (chrec) == FIELD_DECL)
1088 : return true;
1089 :
1090 31893114 : if (loop != NULL
1091 600 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1092 31893316 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1093 : return true;
1094 :
1095 31893114 : if (visited.add (chrec))
1096 : return false;
1097 :
1098 31245709 : n = TREE_OPERAND_LENGTH (chrec);
1099 80457885 : for (i = 0; i < n; i++)
1100 21926735 : if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
1101 : return true;
1102 : return false;
1103 : }
1104 :
1105 : /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
1106 : CHREC contains any chrec which is invariant wrto the loop (nest), in other
1107 : words, chrec defined by outer loops of loop, so from LOOP's point of view,
1108 : the chrec is considered as a SYMBOL. */
1109 :
1110 : bool
1111 15762356 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1112 : {
1113 15762356 : hash_set<const_tree> visited;
1114 15762356 : return chrec_contains_symbols (chrec, visited, loop);
1115 15762356 : }
1116 :
1117 : /* Return true when CHREC contains symbolic names defined in
1118 : LOOP_NB. */
1119 :
1120 : static bool
1121 342091736 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1122 : hash_set<const_tree> &visited)
1123 : {
1124 342091736 : int i, n;
1125 :
1126 342091736 : if (chrec == NULL_TREE)
1127 : return false;
1128 :
1129 341944569 : if (is_gimple_min_invariant (chrec))
1130 : return false;
1131 :
1132 202014823 : if (TREE_CODE (chrec) == SSA_NAME)
1133 : {
1134 72762554 : gimple *def;
1135 72762554 : loop_p def_loop, loop;
1136 :
1137 72762554 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1138 : return false;
1139 :
1140 68404572 : def = SSA_NAME_DEF_STMT (chrec);
1141 68404572 : def_loop = loop_containing_stmt (def);
1142 68404572 : loop = get_loop (cfun, loop_nb);
1143 :
1144 68404572 : if (def_loop == NULL)
1145 : return false;
1146 :
1147 68404572 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1148 4205375 : return true;
1149 :
1150 : return false;
1151 : }
1152 :
1153 129252269 : if (visited.add (chrec))
1154 : return false;
1155 :
1156 129207802 : n = TREE_OPERAND_LENGTH (chrec);
1157 472676320 : for (i = 0; i < n; i++)
1158 215610213 : if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1159 : loop_nb, visited))
1160 : return true;
1161 : return false;
1162 : }
1163 :
1164 : /* Return true when CHREC contains symbolic names defined in
1165 : LOOP_NB. */
1166 :
1167 : bool
1168 126481523 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1169 : {
1170 126481523 : hash_set<const_tree> visited;
1171 126481523 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1172 126481523 : }
1173 :
1174 : /* Determines whether the chrec contains undetermined coefficients. */
1175 :
1176 : static bool
1177 230160951 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1178 : {
1179 230160951 : int i, n;
1180 :
1181 230160951 : if (chrec == chrec_dont_know)
1182 : return true;
1183 :
1184 206796004 : if (chrec == NULL_TREE)
1185 : return false;
1186 :
1187 206415564 : if (visited.add (chrec))
1188 : return false;
1189 :
1190 193007355 : n = TREE_OPERAND_LENGTH (chrec);
1191 513130762 : for (i = 0; i < n; i++)
1192 127117301 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1193 : return true;
1194 : return false;
1195 : }
1196 :
1197 : bool
1198 103043650 : chrec_contains_undetermined (const_tree chrec)
1199 : {
1200 103043650 : hash_set<const_tree> visited;
1201 103043650 : return chrec_contains_undetermined (chrec, visited);
1202 103043650 : }
1203 :
1204 : /* Determines whether the tree EXPR contains chrecs, and increment
1205 : SIZE if it is not a NULL pointer by an estimation of the depth of
1206 : the tree. */
1207 :
1208 : static bool
1209 443884547 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1210 : {
1211 443884547 : int i, n;
1212 :
1213 443884547 : if (expr == NULL_TREE)
1214 : return false;
1215 :
1216 442730086 : if (size)
1217 78068153 : (*size)++;
1218 :
1219 442730086 : if (tree_is_chrec (expr))
1220 : return true;
1221 :
1222 419309756 : if (visited.add (expr))
1223 : return false;
1224 :
1225 416760496 : n = TREE_OPERAND_LENGTH (expr);
1226 1047597366 : for (i = 0; i < n; i++)
1227 214458296 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1228 : return true;
1229 : return false;
1230 : }
1231 :
1232 : bool
1233 229426251 : tree_contains_chrecs (const_tree expr, int *size)
1234 : {
1235 229426251 : hash_set<const_tree> visited;
1236 229426251 : return tree_contains_chrecs (expr, size, visited);
1237 229426251 : }
1238 :
1239 :
1240 : /* Recursive helper function. */
1241 :
1242 : static bool
1243 44312340 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1244 : {
1245 92503940 : if (evolution_function_is_constant_p (chrec))
1246 : return true;
1247 :
1248 10386154 : if (TREE_CODE (chrec) == SSA_NAME
1249 10386154 : && (loopnum == 0
1250 2259544 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1251 : return true;
1252 :
1253 8156679 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1254 : {
1255 6141940 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1256 134950 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1257 134950 : get_chrec_loop (chrec))
1258 3264 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1259 : loopnum)
1260 6145204 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1261 : loopnum))
1262 6138676 : return false;
1263 : return true;
1264 : }
1265 :
1266 2014739 : switch (TREE_OPERAND_LENGTH (chrec))
1267 : {
1268 936550 : case 2:
1269 936550 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1270 : loopnum))
1271 : return false;
1272 : /* FALLTHRU */
1273 :
1274 1939630 : case 1:
1275 1939630 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1276 : loopnum))
1277 : return false;
1278 : return true;
1279 :
1280 : default:
1281 : return false;
1282 : }
1283 : }
1284 :
1285 : /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1286 :
1287 : bool
1288 30861536 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1289 : {
1290 30861536 : return evolution_function_is_invariant_rec_p (chrec, loopnum);
1291 : }
1292 :
1293 : /* Determine whether the given tree is an affine multivariate
1294 : evolution. */
1295 :
1296 : bool
1297 6811890 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1298 : {
1299 6811890 : if (chrec == NULL_TREE)
1300 : return false;
1301 :
1302 6811890 : switch (TREE_CODE (chrec))
1303 : {
1304 6253863 : case POLYNOMIAL_CHREC:
1305 6253863 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1306 : {
1307 6152573 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1308 : return true;
1309 : else
1310 : {
1311 210 : if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1312 210 : && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1313 210 : != CHREC_VARIABLE (chrec)
1314 210 : && evolution_function_is_affine_multivariate_p
1315 0 : (CHREC_RIGHT (chrec), loopnum))
1316 : return true;
1317 : else
1318 210 : return false;
1319 : }
1320 : }
1321 : else
1322 : {
1323 101290 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1324 101290 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1325 101237 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1326 202527 : && evolution_function_is_affine_multivariate_p
1327 101237 : (CHREC_LEFT (chrec), loopnum))
1328 101237 : return true;
1329 : else
1330 : return false;
1331 : }
1332 :
1333 : default:
1334 : return false;
1335 : }
1336 : }
1337 :
1338 : /* Determine whether the given tree is a function in zero or one
1339 : variables with respect to loop specified by LOOPNUM. Note only positive
1340 : LOOPNUM stands for a real loop. */
1341 :
1342 : bool
1343 3460431 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1344 : {
1345 3460431 : if (chrec == NULL_TREE)
1346 : return true;
1347 :
1348 3460431 : tree sub_chrec;
1349 3460431 : switch (TREE_CODE (chrec))
1350 : {
1351 3460428 : case POLYNOMIAL_CHREC:
1352 3460428 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1353 : {
1354 31478 : case POLYNOMIAL_CHREC:
1355 31478 : sub_chrec = CHREC_LEFT (chrec);
1356 31478 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1357 31478 : && (loopnum <= 0
1358 5105 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1359 19 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1360 19 : get_chrec_loop (sub_chrec))))
1361 : return false;
1362 12 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1363 : return false;
1364 : break;
1365 :
1366 3428950 : default:
1367 3428950 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1368 : return false;
1369 : break;
1370 : }
1371 :
1372 3428962 : switch (TREE_CODE (CHREC_RIGHT (chrec)))
1373 : {
1374 0 : case POLYNOMIAL_CHREC:
1375 0 : sub_chrec = CHREC_RIGHT (chrec);
1376 0 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1377 0 : && (loopnum <= 0
1378 0 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1379 0 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1380 0 : get_chrec_loop (sub_chrec))))
1381 : return false;
1382 0 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1383 : return false;
1384 : break;
1385 :
1386 3428962 : default:
1387 3428962 : if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1388 0 : return false;
1389 : break;
1390 : }
1391 : return true;
1392 :
1393 : default:
1394 : return true;
1395 : }
1396 : }
1397 :
1398 : /* Returns the number of variables of CHREC. Example: the call
1399 : nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1400 :
1401 : unsigned
1402 3371906 : nb_vars_in_chrec (tree chrec)
1403 : {
1404 6743812 : if (chrec == NULL_TREE)
1405 : return 0;
1406 :
1407 6743812 : switch (TREE_CODE (chrec))
1408 : {
1409 3371906 : case POLYNOMIAL_CHREC:
1410 3371906 : return 1 + nb_vars_in_chrec
1411 3371906 : (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1412 :
1413 : default:
1414 : return 0;
1415 : }
1416 : }
1417 :
1418 : /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1419 : the scev corresponds to. AT_STMT is the statement at that the scev is
1420 : evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1421 : that the rules for overflow of the given language apply (e.g., that signed
1422 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1423 : unnecessary tests, but also to enforce that the result follows them.
1424 : FROM is the source variable converted if it's not NULL. Returns true if
1425 : the conversion succeeded, false otherwise. */
1426 :
1427 : bool
1428 7770094 : convert_affine_scev (class loop *loop, tree type,
1429 : tree *base, tree *step, gimple *at_stmt,
1430 : bool use_overflow_semantics, tree from)
1431 : {
1432 7770094 : tree ct = TREE_TYPE (*step);
1433 7770094 : bool enforce_overflow_semantics;
1434 7770094 : bool must_check_src_overflow, must_check_rslt_overflow;
1435 7770094 : tree new_base, new_step;
1436 7770094 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1437 :
1438 : /* In general,
1439 : (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1440 : but we must check some assumptions.
1441 :
1442 : 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1443 : of CT is smaller than the precision of TYPE. For example, when we
1444 : cast unsigned char [254, +, 1] to unsigned, the values on left side
1445 : are 254, 255, 0, 1, ..., but those on the right side are
1446 : 254, 255, 256, 257, ...
1447 : 2) In case that we must also preserve the fact that signed ivs do not
1448 : overflow, we must additionally check that the new iv does not wrap.
1449 : For example, unsigned char [125, +, 1] casted to signed char could
1450 : become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1451 : which would confuse optimizers that assume that this does not
1452 : happen. */
1453 7770094 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1454 :
1455 17869203 : enforce_overflow_semantics = (use_overflow_semantics
1456 7770094 : && nowrap_type_p (type));
1457 2740260 : if (enforce_overflow_semantics)
1458 : {
1459 : /* We can avoid checking whether the result overflows in the following
1460 : cases:
1461 :
1462 : -- must_check_src_overflow is true, and the range of TYPE is superset
1463 : of the range of CT -- i.e., in all cases except if CT signed and
1464 : TYPE unsigned.
1465 : -- both CT and TYPE have the same precision and signedness, and we
1466 : verify instead that the source does not overflow (this may be
1467 : easier than verifying it for the result, as we may use the
1468 : information about the semantics of overflow in CT). */
1469 2740260 : if (must_check_src_overflow)
1470 : {
1471 444629 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1472 : must_check_rslt_overflow = true;
1473 : else
1474 : must_check_rslt_overflow = false;
1475 : }
1476 2295631 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1477 2295631 : && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1478 : {
1479 : must_check_rslt_overflow = false;
1480 : must_check_src_overflow = true;
1481 : }
1482 : else
1483 : must_check_rslt_overflow = true;
1484 : }
1485 : else
1486 : must_check_rslt_overflow = false;
1487 :
1488 7358849 : if (must_check_src_overflow
1489 7770094 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1490 : use_overflow_semantics))
1491 : return false;
1492 :
1493 6954460 : new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1494 : /* The step must be sign extended, regardless of the signedness
1495 : of CT and TYPE. This only needs to be handled specially when
1496 : CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1497 : (with values 100, 99, 98, ...) from becoming signed or unsigned
1498 : [100, +, 255] with values 100, 355, ...; the sign-extension is
1499 : performed by default when CT is signed. */
1500 6954460 : new_step = *step;
1501 6954460 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1502 : {
1503 138632 : tree signed_ct = signed_type_for (ct);
1504 138632 : new_step = chrec_convert (signed_ct, new_step, at_stmt,
1505 : use_overflow_semantics);
1506 : }
1507 6954460 : new_step = chrec_convert (step_type, new_step, at_stmt,
1508 : use_overflow_semantics);
1509 :
1510 13904984 : if (automatically_generated_chrec_p (new_base)
1511 14720356 : || automatically_generated_chrec_p (new_step))
1512 : return false;
1513 :
1514 6950262 : if (must_check_rslt_overflow
1515 : /* Note that in this case we cannot use the fact that signed variables
1516 : do not overflow, as this is what we are verifying for the new iv. */
1517 6950262 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1518 : at_stmt, loop, false))
1519 : return false;
1520 :
1521 5503933 : *base = new_base;
1522 5503933 : *step = new_step;
1523 5503933 : return true;
1524 : }
1525 :
1526 :
1527 : /* Convert CHREC for the right hand side of a CHREC.
1528 : The increment for a pointer type is always sizetype. */
1529 :
1530 : tree
1531 31749811 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1532 : {
1533 31749811 : if (POINTER_TYPE_P (type))
1534 5865582 : type = sizetype;
1535 :
1536 31749811 : return chrec_convert (type, chrec, at_stmt);
1537 : }
1538 :
1539 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1540 : which the CHREC is built, it sets AT_STMT to the statement that
1541 : contains the definition of the analyzed variable, otherwise the
1542 : conversion is less accurate: the information is used for
1543 : determining a more accurate estimation of the number of iterations.
1544 : By default AT_STMT could be safely set to NULL_TREE.
1545 :
1546 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1547 : the rules for overflow of the given language apply (e.g., that signed
1548 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1549 : unnecessary tests, but also to enforce that the result follows them.
1550 :
1551 : FROM is the source variable converted if it's not NULL. */
1552 :
1553 : static tree
1554 159883227 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1555 : bool use_overflow_semantics, tree from)
1556 : {
1557 159883227 : tree ct, res;
1558 159883227 : tree base, step;
1559 159883227 : class loop *loop;
1560 :
1561 159883227 : if (automatically_generated_chrec_p (chrec))
1562 : return chrec;
1563 :
1564 158506870 : ct = chrec_type (chrec);
1565 158506870 : if (useless_type_conversion_p (type, ct))
1566 : return chrec;
1567 :
1568 43090061 : if (!evolution_function_is_affine_p (chrec))
1569 36745728 : goto keep_cast;
1570 :
1571 6344333 : loop = get_chrec_loop (chrec);
1572 6344333 : base = CHREC_LEFT (chrec);
1573 6344333 : step = CHREC_RIGHT (chrec);
1574 :
1575 6344333 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1576 : use_overflow_semantics, from))
1577 4621849 : return build_polynomial_chrec (loop->num, base, step);
1578 :
1579 : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1580 1722484 : keep_cast:
1581 : /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1582 : may be more expensive. We do want to perform this optimization here
1583 : though for canonicalization reasons. */
1584 38468212 : if (use_overflow_semantics
1585 37810345 : && (TREE_CODE (chrec) == PLUS_EXPR
1586 37810345 : || TREE_CODE (chrec) == MINUS_EXPR)
1587 3682052 : && TREE_CODE (type) == INTEGER_TYPE
1588 3575079 : && TREE_CODE (ct) == INTEGER_TYPE
1589 3575033 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1590 38618261 : && TYPE_OVERFLOW_UNDEFINED (ct))
1591 47288 : res = fold_build2 (TREE_CODE (chrec), type,
1592 : fold_convert (type, TREE_OPERAND (chrec, 0)),
1593 : fold_convert (type, TREE_OPERAND (chrec, 1)));
1594 : /* Similar perform the trick that (signed char)((int)x + 2) can be
1595 : narrowed to (signed char)((unsigned char)x + 2). */
1596 38420924 : else if (use_overflow_semantics
1597 37763057 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1598 1760135 : && TREE_CODE (ct) == INTEGER_TYPE
1599 1747917 : && TREE_CODE (type) == INTEGER_TYPE
1600 1590557 : && TYPE_OVERFLOW_UNDEFINED (type)
1601 39765607 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1602 : {
1603 31467 : tree utype = unsigned_type_for (type);
1604 94401 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1605 31467 : fold_convert (utype,
1606 : CHREC_LEFT (chrec)),
1607 31467 : fold_convert (utype,
1608 : CHREC_RIGHT (chrec)));
1609 31467 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1610 : }
1611 : /* Similar perform the trick that (unsigned T)(base + step) can be
1612 : folded to ((unsigned T)x + (unsigned T)step). */
1613 38389457 : else if (use_overflow_semantics
1614 37731590 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1615 1728668 : && INTEGRAL_TYPE_P (ct)
1616 1716535 : && INTEGRAL_TYPE_P (type)
1617 1559185 : && TYPE_OVERFLOW_UNDEFINED (type)
1618 : /* Must be unsigned so we don't introduce any UB. */
1619 1313311 : && TYPE_UNSIGNED (type)
1620 : /* The outer type must at least as wide than the inner type so we
1621 : don't truncate when we fold and must the inner CHREC must be
1622 : non-wrapping so we don't change the behavior when folding to
1623 : a wider type. */
1624 0 : && TYPE_PRECISION (type) >= TYPE_PRECISION (ct)
1625 38389457 : && (!TYPE_UNSIGNED (ct)
1626 0 : || TYPE_PRECISION (type) == TYPE_PRECISION (ct)
1627 0 : || nonwrapping_chrec_p (chrec)))
1628 : {
1629 0 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1630 0 : fold_convert (type,
1631 : CHREC_LEFT (chrec)),
1632 0 : fold_convert (type,
1633 : CHREC_RIGHT (chrec)));
1634 0 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1635 : }
1636 : else
1637 38389457 : res = fold_convert (type, chrec);
1638 :
1639 : /* Don't propagate overflows. */
1640 38468212 : if (CONSTANT_CLASS_P (res))
1641 12195657 : TREE_OVERFLOW (res) = 0;
1642 :
1643 : /* But reject constants that don't fit in their type after conversion.
1644 : This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1645 : natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1646 : and can cause problems later when computing niters of loops. Note
1647 : that we don't do the check before converting because we don't want
1648 : to reject conversions of negative chrecs to unsigned types. */
1649 38468212 : if (TREE_CODE (res) == INTEGER_CST
1650 12195657 : && TREE_CODE (type) == INTEGER_TYPE
1651 12177256 : && !int_fits_type_p (res, type))
1652 4518 : res = chrec_dont_know;
1653 :
1654 : return res;
1655 : }
1656 :
1657 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1658 : which the CHREC is built, it sets AT_STMT to the statement that
1659 : contains the definition of the analyzed variable, otherwise the
1660 : conversion is less accurate: the information is used for
1661 : determining a more accurate estimation of the number of iterations.
1662 : By default AT_STMT could be safely set to NULL_TREE.
1663 :
1664 : The following rule is always true: TREE_TYPE (chrec) ==
1665 : TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1666 : An example of what could happen when adding two chrecs and the type
1667 : of the CHREC_RIGHT is different than CHREC_LEFT is:
1668 :
1669 : {(uint) 0, +, (uchar) 10} +
1670 : {(uint) 0, +, (uchar) 250}
1671 :
1672 : that would produce a wrong result if CHREC_RIGHT is not (uint):
1673 :
1674 : {(uint) 0, +, (uchar) 4}
1675 :
1676 : instead of
1677 :
1678 : {(uint) 0, +, (uint) 260}
1679 :
1680 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1681 : the rules for overflow of the given language apply (e.g., that signed
1682 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1683 : unnecessary tests, but also to enforce that the result follows them.
1684 :
1685 : FROM is the source variable converted if it's not NULL. */
1686 :
1687 : tree
1688 159851760 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1689 : bool use_overflow_semantics, tree from)
1690 : {
1691 159851760 : return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1692 : }
1693 :
1694 : /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1695 : chrec if something else than what chrec_convert would do happens, NULL_TREE
1696 : otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1697 : if the result chrec may overflow. */
1698 :
1699 : tree
1700 8947351 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1701 : {
1702 8947351 : tree inner_type, left, right, lc, rc, rtype;
1703 :
1704 8947351 : gcc_assert (fold_conversions != NULL);
1705 :
1706 8947351 : if (automatically_generated_chrec_p (chrec)
1707 8947351 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1708 : return NULL_TREE;
1709 :
1710 699923 : inner_type = TREE_TYPE (chrec);
1711 699923 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1712 : return NULL_TREE;
1713 :
1714 612275 : if (useless_type_conversion_p (type, inner_type))
1715 : return NULL_TREE;
1716 :
1717 543766 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1718 : {
1719 542958 : tree base, step;
1720 542958 : class loop *loop;
1721 :
1722 542958 : loop = get_chrec_loop (chrec);
1723 542958 : base = CHREC_LEFT (chrec);
1724 542958 : step = CHREC_RIGHT (chrec);
1725 542958 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1726 2584 : return build_polynomial_chrec (loop->num, base, step);
1727 : }
1728 541182 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1729 :
1730 541182 : left = CHREC_LEFT (chrec);
1731 541182 : right = CHREC_RIGHT (chrec);
1732 541182 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1733 541182 : if (!lc)
1734 541182 : lc = chrec_convert (type, left, NULL);
1735 541182 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1736 541182 : if (!rc)
1737 540500 : rc = chrec_convert (rtype, right, NULL);
1738 :
1739 541182 : *fold_conversions = true;
1740 :
1741 541182 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1742 : }
1743 :
1744 : /* Returns true when CHREC0 == CHREC1. */
1745 :
1746 : bool
1747 13619553 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1748 : {
1749 13647457 : if (chrec0 == NULL_TREE
1750 13647457 : || chrec1 == NULL_TREE
1751 13647457 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1752 : return false;
1753 :
1754 12704289 : if (operand_equal_p (chrec0, chrec1, 0))
1755 : return true;
1756 :
1757 9451851 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1758 : return false;
1759 :
1760 9450581 : switch (TREE_CODE (chrec0))
1761 : {
1762 3885422 : case POLYNOMIAL_CHREC:
1763 3885422 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1764 3885043 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1765 4221463 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1766 :
1767 55109 : case PLUS_EXPR:
1768 55109 : case MULT_EXPR:
1769 55109 : case MINUS_EXPR:
1770 55109 : case POINTER_PLUS_EXPR:
1771 55109 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1772 55109 : TREE_OPERAND (chrec1, 0))
1773 96182 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1774 41073 : TREE_OPERAND (chrec1, 1));
1775 :
1776 27904 : CASE_CONVERT:
1777 27904 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1778 55808 : TREE_OPERAND (chrec1, 0));
1779 :
1780 : default:
1781 : return false;
1782 : }
1783 : }
1784 :
1785 : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1786 : EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1787 : which of these cases happens. */
1788 :
1789 : enum ev_direction
1790 3113050 : scev_direction (const_tree chrec)
1791 : {
1792 3113050 : const_tree step;
1793 :
1794 3113050 : if (!evolution_function_is_affine_p (chrec))
1795 : return EV_DIR_UNKNOWN;
1796 :
1797 3107794 : step = CHREC_RIGHT (chrec);
1798 3107794 : if (TREE_CODE (step) != INTEGER_CST)
1799 : return EV_DIR_UNKNOWN;
1800 :
1801 3014892 : if (tree_int_cst_sign_bit (step))
1802 : return EV_DIR_DECREASES;
1803 : else
1804 2713273 : return EV_DIR_GROWS;
1805 : }
1806 :
1807 : /* Iterates over all the components of SCEV, and calls CBCK. */
1808 :
1809 : void
1810 0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1811 : {
1812 0 : switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1813 : {
1814 0 : case 3:
1815 0 : for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1816 : /* FALLTHRU */
1817 :
1818 0 : case 2:
1819 0 : for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1820 : /* FALLTHRU */
1821 :
1822 0 : case 1:
1823 0 : for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1824 : /* FALLTHRU */
1825 :
1826 0 : default:
1827 0 : cbck (scev, data);
1828 0 : break;
1829 : }
1830 0 : }
1831 :
1832 : /* Returns true when the operation can be part of a linear
1833 : expression. */
1834 :
1835 : static inline bool
1836 34297 : operator_is_linear (tree scev)
1837 : {
1838 34297 : switch (TREE_CODE (scev))
1839 : {
1840 : case INTEGER_CST:
1841 : case POLYNOMIAL_CHREC:
1842 : case PLUS_EXPR:
1843 : case POINTER_PLUS_EXPR:
1844 : case MULT_EXPR:
1845 : case MINUS_EXPR:
1846 : case NEGATE_EXPR:
1847 : case SSA_NAME:
1848 : case NON_LVALUE_EXPR:
1849 : case BIT_NOT_EXPR:
1850 : CASE_CONVERT:
1851 : return true;
1852 :
1853 8 : default:
1854 8 : return false;
1855 : }
1856 : }
1857 :
1858 : /* Return true when SCEV is a linear expression. Linear expressions
1859 : can contain additions, substractions and multiplications.
1860 : Multiplications are restricted to constant scaling: "cst * x". */
1861 :
1862 : bool
1863 78071 : scev_is_linear_expression (tree scev)
1864 : {
1865 160808 : if (evolution_function_is_constant_p (scev))
1866 : return true;
1867 :
1868 34297 : if (scev == NULL
1869 34297 : || !operator_is_linear (scev))
1870 : return false;
1871 :
1872 34289 : if (TREE_CODE (scev) == MULT_EXPR)
1873 670 : return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1874 0 : && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1875 :
1876 33619 : if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1877 33619 : && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1878 : return false;
1879 :
1880 33409 : switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1881 : {
1882 0 : case 3:
1883 0 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1884 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1885 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1886 :
1887 24563 : case 2:
1888 24563 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1889 24563 : && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1890 :
1891 2333 : case 1:
1892 2333 : return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1893 :
1894 : case 0:
1895 : return true;
1896 :
1897 : default:
1898 : return false;
1899 : }
1900 : }
1901 :
1902 : /* Determines whether the expression CHREC contains only integer consts
1903 : in the right parts. */
1904 :
1905 : bool
1906 4307 : evolution_function_right_is_integer_cst (const_tree chrec)
1907 : {
1908 4307 : if (chrec == NULL_TREE)
1909 : return false;
1910 :
1911 4307 : switch (TREE_CODE (chrec))
1912 : {
1913 : case INTEGER_CST:
1914 : return true;
1915 :
1916 4307 : case POLYNOMIAL_CHREC:
1917 4307 : return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1918 4307 : && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1919 470 : || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1920 :
1921 0 : CASE_CONVERT:
1922 0 : return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1923 :
1924 : default:
1925 : return false;
1926 : }
1927 : }
|
