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 88217 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : tree type,
50 : tree poly0,
51 : tree poly1)
52 : {
53 88217 : tree left, right;
54 88217 : class loop *loop0 = get_chrec_loop (poly0);
55 88217 : class loop *loop1 = get_chrec_loop (poly1);
56 :
57 88217 : gcc_assert (poly0);
58 88217 : gcc_assert (poly1);
59 88217 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
60 88217 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
61 88217 : if (POINTER_TYPE_P (chrec_type (poly0)))
62 866 : gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
63 : && useless_type_conversion_p (type, chrec_type (poly0)));
64 : else
65 87351 : 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 88217 : 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 87921 : 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 87319 : if (loop0 != loop1)
106 : {
107 : /* It still can happen if we are not in loop-closed SSA form. */
108 32 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
109 32 : return chrec_dont_know;
110 : }
111 :
112 87287 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
113 : {
114 32628 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
115 32628 : left = chrec_fold_plus
116 32628 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 32628 : right = chrec_fold_plus
118 32628 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : }
120 : else
121 : {
122 54659 : left = chrec_fold_minus
123 54659 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 54659 : right = chrec_fold_minus
125 54659 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : }
127 :
128 87287 : if (chrec_zerop (right))
129 : return left;
130 : else
131 32892 : return build_polynomial_chrec
132 32892 : (CHREC_VARIABLE (poly0), left, right);
133 : }
134 :
135 :
136 :
137 : /* Fold the multiplication of two polynomial functions. */
138 :
139 : static inline tree
140 40243 : chrec_fold_multiply_poly_poly (tree type,
141 : tree poly0,
142 : tree poly1)
143 : {
144 40243 : tree t0, t1, t2;
145 40243 : int var;
146 40243 : class loop *loop0 = get_chrec_loop (poly0);
147 40243 : class loop *loop1 = get_chrec_loop (poly1);
148 :
149 40243 : gcc_assert (poly0);
150 40243 : gcc_assert (poly1);
151 40243 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
152 40243 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
153 40243 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
154 : && useless_type_conversion_p (type, chrec_type (poly1)));
155 :
156 : /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
157 : {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
158 : {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
159 40243 : if (flow_loop_nested_p (loop0, loop1))
160 : /* poly0 is a constant wrt. poly1. */
161 0 : return build_polynomial_chrec
162 0 : (CHREC_VARIABLE (poly1),
163 0 : chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
164 0 : CHREC_RIGHT (poly1));
165 :
166 40243 : if (flow_loop_nested_p (loop1, loop0))
167 : /* poly1 is a constant wrt. poly0. */
168 0 : return build_polynomial_chrec
169 0 : (CHREC_VARIABLE (poly0),
170 0 : chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
171 0 : CHREC_RIGHT (poly0));
172 :
173 40243 : if (loop0 != loop1)
174 : {
175 : /* It still can happen if we are not in loop-closed SSA form. */
176 0 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
177 0 : return chrec_dont_know;
178 : }
179 :
180 : /* poly0 and poly1 are two polynomials in the same variable,
181 : {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
182 :
183 : /* "a*c". */
184 40243 : t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
185 :
186 : /* "a*d + b*c". */
187 40243 : t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
188 120729 : t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
189 40243 : CHREC_RIGHT (poly0),
190 40243 : CHREC_LEFT (poly1)));
191 : /* "b*d". */
192 40243 : t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
193 : /* "a*d + b*c + b*d". */
194 40243 : t1 = chrec_fold_plus (type, t1, t2);
195 : /* "2*b*d". */
196 80486 : t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
197 33 : ? build_real (type, dconst2)
198 40210 : : build_int_cst (type, 2), t2);
199 :
200 40243 : var = CHREC_VARIABLE (poly0);
201 40243 : return build_polynomial_chrec (var, t0,
202 40243 : build_polynomial_chrec (var, t1, t2));
203 : }
204 :
205 : /* When the operands are automatically_generated_chrec_p, the fold has
206 : to respect the semantics of the operands. */
207 :
208 : static inline tree
209 5853846 : chrec_fold_automatically_generated_operands (tree op0,
210 : tree op1)
211 : {
212 5853846 : if (op0 == chrec_dont_know
213 949118 : || op1 == chrec_dont_know)
214 : return chrec_dont_know;
215 :
216 0 : if (op0 == chrec_known
217 0 : || op1 == chrec_known)
218 : return chrec_known;
219 :
220 0 : if (op0 == chrec_not_analyzed_yet
221 0 : || op1 == chrec_not_analyzed_yet)
222 0 : return chrec_not_analyzed_yet;
223 :
224 : /* The default case produces a safe result. */
225 : return chrec_dont_know;
226 : }
227 :
228 : /* Fold the addition of two chrecs. */
229 :
230 : static tree
231 30409986 : chrec_fold_plus_1 (enum tree_code code, tree type,
232 : tree op0, tree op1)
233 : {
234 60819972 : if (automatically_generated_chrec_p (op0)
235 30409986 : || automatically_generated_chrec_p (op1))
236 0 : return chrec_fold_automatically_generated_operands (op0, op1);
237 :
238 30409986 : switch (TREE_CODE (op0))
239 : {
240 9704156 : case POLYNOMIAL_CHREC:
241 9704156 : gcc_checking_assert
242 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
243 9704156 : switch (TREE_CODE (op1))
244 : {
245 88217 : case POLYNOMIAL_CHREC:
246 88217 : gcc_checking_assert
247 : (!chrec_contains_symbols_defined_in_loop (op1,
248 : CHREC_VARIABLE (op1)));
249 88217 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
250 :
251 161911 : CASE_CONVERT:
252 161911 : if (tree_contains_chrecs (op1, NULL))
253 : {
254 : /* We can strip sign-conversions to signed by performing the
255 : operation in unsigned. */
256 688 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
257 688 : if (INTEGRAL_TYPE_P (type)
258 688 : && INTEGRAL_TYPE_P (optype)
259 663 : && tree_nop_conversion_p (type, optype)
260 879 : && TYPE_UNSIGNED (optype))
261 : {
262 73 : tree tem = chrec_convert (optype, op0, NULL);
263 73 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
264 16 : return chrec_convert (type,
265 : chrec_fold_plus_1 (code, optype,
266 : tem,
267 16 : TREE_OPERAND
268 : (op1, 0)),
269 16 : NULL);
270 : }
271 672 : return chrec_dont_know;
272 : }
273 : /* FALLTHRU */
274 :
275 9615251 : default:
276 9615251 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
277 8837792 : return build_polynomial_chrec
278 8837792 : (CHREC_VARIABLE (op0),
279 8837792 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
280 17675584 : CHREC_RIGHT (op0));
281 : else
282 777459 : return build_polynomial_chrec
283 777459 : (CHREC_VARIABLE (op0),
284 777459 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
285 1554918 : CHREC_RIGHT (op0));
286 : }
287 :
288 2898452 : CASE_CONVERT:
289 2898452 : if (tree_contains_chrecs (op0, NULL))
290 : {
291 : /* We can strip sign-conversions to signed by performing the
292 : operation in unsigned. */
293 41416 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
294 41416 : if (INTEGRAL_TYPE_P (type)
295 40016 : && INTEGRAL_TYPE_P (optype)
296 36005 : && tree_nop_conversion_p (type, optype)
297 67725 : && TYPE_UNSIGNED (optype))
298 52550 : return chrec_convert (type,
299 : chrec_fold_plus_1 (code, optype,
300 26275 : TREE_OPERAND (op0, 0),
301 : chrec_convert (optype,
302 : op1, NULL)),
303 26275 : NULL);
304 15141 : return chrec_dont_know;
305 : }
306 : /* FALLTHRU */
307 :
308 20664414 : default:
309 20664414 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
310 20664414 : switch (TREE_CODE (op1))
311 : {
312 3084830 : case POLYNOMIAL_CHREC:
313 3084830 : gcc_checking_assert
314 : (!chrec_contains_symbols_defined_in_loop (op1,
315 : CHREC_VARIABLE (op1)));
316 3084830 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
317 3017674 : return build_polynomial_chrec
318 3017674 : (CHREC_VARIABLE (op1),
319 3017674 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
320 6035348 : CHREC_RIGHT (op1));
321 : else
322 67156 : return build_polynomial_chrec
323 134312 : (CHREC_VARIABLE (op1),
324 67156 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
325 67156 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
326 67156 : SCALAR_FLOAT_TYPE_P (type)
327 4 : ? build_real (type, dconstm1)
328 134308 : : build_int_cst_type (type, -1)));
329 :
330 2133333 : CASE_CONVERT:
331 2133333 : if (tree_contains_chrecs (op1, NULL))
332 : {
333 : /* We can strip sign-conversions to signed by performing the
334 : operation in unsigned. */
335 60249 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
336 60249 : if (INTEGRAL_TYPE_P (type)
337 22092 : && INTEGRAL_TYPE_P (optype)
338 22092 : && tree_nop_conversion_p (type, optype)
339 78226 : && TYPE_UNSIGNED (optype))
340 17977 : return chrec_convert (type,
341 : chrec_fold_plus_1 (code, optype,
342 : chrec_convert (optype,
343 : op0,
344 : NULL),
345 17977 : TREE_OPERAND (op1, 0)),
346 17977 : NULL);
347 42272 : return chrec_dont_know;
348 : }
349 : /* FALLTHRU */
350 :
351 17519335 : default:
352 17519335 : {
353 17519335 : int size = 0;
354 17519335 : if ((tree_contains_chrecs (op0, &size)
355 17519335 : || tree_contains_chrecs (op1, &size))
356 17519335 : && size < param_scev_max_expr_size)
357 0 : return build2 (code, type, op0, op1);
358 17519335 : else if (size < param_scev_max_expr_size)
359 : {
360 17519235 : if (code == POINTER_PLUS_EXPR)
361 3475879 : return fold_build_pointer_plus (fold_convert (type, op0),
362 : op1);
363 : else
364 14043356 : return fold_build2 (code, type,
365 : fold_convert (type, op0),
366 : fold_convert (type, op1));
367 : }
368 : else
369 100 : return chrec_dont_know;
370 : }
371 : }
372 : }
373 : }
374 :
375 : /* Fold the addition of two chrecs. */
376 :
377 : tree
378 36645347 : chrec_fold_plus (tree type,
379 : tree op0,
380 : tree op1)
381 : {
382 36645347 : enum tree_code code;
383 70370695 : if (automatically_generated_chrec_p (op0)
384 36645347 : || automatically_generated_chrec_p (op1))
385 3574025 : return chrec_fold_automatically_generated_operands (op0, op1);
386 :
387 33071322 : if (integer_zerop (op0))
388 4065773 : return chrec_convert (type, op1, NULL);
389 29005549 : if (integer_zerop (op1))
390 1848761 : return chrec_convert (type, op0, NULL);
391 :
392 27156788 : if (POINTER_TYPE_P (type))
393 : code = POINTER_PLUS_EXPR;
394 : else
395 20774470 : code = PLUS_EXPR;
396 :
397 27156788 : return chrec_fold_plus_1 (code, type, op0, op1);
398 : }
399 :
400 : /* Fold the subtraction of two chrecs. */
401 :
402 : tree
403 4022363 : chrec_fold_minus (tree type,
404 : tree op0,
405 : tree op1)
406 : {
407 7466653 : if (automatically_generated_chrec_p (op0)
408 4022363 : || automatically_generated_chrec_p (op1))
409 715766 : return chrec_fold_automatically_generated_operands (op0, op1);
410 :
411 3306597 : if (integer_zerop (op1))
412 : return op0;
413 :
414 3208930 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
415 : }
416 :
417 : /* Fold the multiplication of two chrecs. */
418 :
419 : tree
420 21411503 : chrec_fold_multiply (tree type,
421 : tree op0,
422 : tree op1)
423 : {
424 21411939 : if (automatically_generated_chrec_p (op0)
425 20005283 : || automatically_generated_chrec_p (op1))
426 1564055 : return chrec_fold_automatically_generated_operands (op0, op1);
427 :
428 19847884 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
429 15894826 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
430 : std::swap (op0, op1);
431 :
432 19847884 : switch (TREE_CODE (op0))
433 : {
434 4147641 : case POLYNOMIAL_CHREC:
435 4147641 : gcc_checking_assert
436 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
437 4147641 : switch (TREE_CODE (op1))
438 : {
439 40243 : case POLYNOMIAL_CHREC:
440 40243 : gcc_checking_assert
441 : (!chrec_contains_symbols_defined_in_loop (op1,
442 : CHREC_VARIABLE (op1)));
443 40243 : return chrec_fold_multiply_poly_poly (type, op0, op1);
444 :
445 57967 : CASE_CONVERT:
446 57967 : if (tree_contains_chrecs (op1, NULL))
447 : {
448 : /* We can strip sign-conversions to signed by performing the
449 : operation in unsigned. */
450 219 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
451 219 : if (INTEGRAL_TYPE_P (type)
452 219 : && INTEGRAL_TYPE_P (optype)
453 219 : && tree_nop_conversion_p (type, optype)
454 235 : && TYPE_UNSIGNED (optype))
455 : {
456 16 : tree tem = chrec_convert (optype, op0, NULL);
457 16 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
458 16 : return chrec_convert (type,
459 : chrec_fold_multiply (optype, tem,
460 16 : TREE_OPERAND
461 : (op1, 0)),
462 16 : NULL);
463 : }
464 203 : return chrec_dont_know;
465 : }
466 : /* FALLTHRU */
467 :
468 4107179 : default:
469 4107179 : if (integer_onep (op1))
470 : return op0;
471 4106728 : if (integer_zerop (op1))
472 410 : return build_int_cst (type, 0);
473 :
474 : /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
475 : same sign or CHREC_LEFT is zero then folding the multiply into
476 : the addition does not have the same behavior on overflow.
477 : Using unsigned arithmetic in that case causes too many performance
478 : regressions, but catch the constant case where the multiplication
479 : of the step overflows. */
480 4106318 : if (INTEGRAL_TYPE_P (type)
481 4106125 : && TYPE_OVERFLOW_UNDEFINED (type)
482 1062834 : && !integer_zerop (CHREC_LEFT (op0))
483 605989 : && TREE_CODE (op1) == INTEGER_CST
484 4535960 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
485 : {
486 337272 : wi::overflow_type ovf = wi::OVF_NONE;
487 337272 : wide_int res
488 337272 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
489 674544 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
490 337272 : if (ovf != wi::OVF_NONE)
491 : {
492 36 : tree utype = unsigned_type_for (type);
493 36 : tree uop1 = chrec_convert_rhs (utype, op1);
494 36 : tree uleft0 = chrec_convert_rhs (utype, CHREC_LEFT (op0));
495 36 : tree uright0 = chrec_convert_rhs (utype, CHREC_RIGHT (op0));
496 36 : tree left = chrec_fold_multiply (utype, uleft0, uop1);
497 36 : tree right = chrec_fold_multiply (utype, uright0, uop1);
498 36 : tree tem = build_polynomial_chrec (CHREC_VARIABLE (op0),
499 : left, right);
500 36 : return chrec_convert_rhs (type, tem);
501 : }
502 337272 : }
503 4106282 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
504 4106282 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
505 4106282 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
506 : }
507 :
508 4697128 : CASE_CONVERT:
509 4697128 : if (tree_contains_chrecs (op0, NULL))
510 : {
511 : /* We can strip sign-conversions to signed by performing the
512 : operation in unsigned. */
513 54142 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
514 54142 : if (INTEGRAL_TYPE_P (type)
515 54142 : && INTEGRAL_TYPE_P (optype)
516 54142 : && tree_nop_conversion_p (type, optype)
517 65597 : && TYPE_UNSIGNED (optype))
518 22860 : return chrec_convert (type,
519 : chrec_fold_multiply (optype,
520 11430 : TREE_OPERAND (op0, 0),
521 : chrec_convert (optype,
522 : op1,
523 : NULL)),
524 11430 : NULL);
525 42712 : return chrec_dont_know;
526 : }
527 : /* FALLTHRU */
528 :
529 15646101 : default:
530 15646101 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
531 15646101 : if (integer_onep (op0))
532 : return op1;
533 :
534 10661733 : if (integer_zerop (op0))
535 2305470 : return build_int_cst (type, 0);
536 :
537 8356263 : switch (TREE_CODE (op1))
538 : {
539 0 : case POLYNOMIAL_CHREC:
540 0 : gcc_unreachable ();
541 :
542 992687 : CASE_CONVERT:
543 992687 : if (tree_contains_chrecs (op1, NULL))
544 : return chrec_fold_multiply (type, op1, op0);
545 : /* FALLTHRU */
546 :
547 8355827 : default:
548 8355827 : if (integer_onep (op1))
549 : return op0;
550 8290886 : if (integer_zerop (op1))
551 1527 : return build_int_cst (type, 0);
552 8289359 : return fold_build2 (MULT_EXPR, type, op0, op1);
553 : }
554 : }
555 : }
556 :
557 :
558 :
559 : /* Operations. */
560 :
561 : /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
562 : calculation overflows, otherwise return C(n,k) with type TYPE. */
563 :
564 : static tree
565 11784 : tree_fold_binomial (tree type, tree n, unsigned int k)
566 : {
567 11784 : wi::overflow_type overflow;
568 11784 : unsigned int i;
569 :
570 : /* Handle the most frequent cases. */
571 11784 : if (k == 0)
572 3903 : return build_int_cst (type, 1);
573 7881 : if (k == 1)
574 3903 : return fold_convert (type, n);
575 :
576 3978 : widest_int num = wi::to_widest (n);
577 :
578 : /* Check that k <= n. */
579 3978 : if (wi::ltu_p (num, k))
580 : return NULL_TREE;
581 :
582 : /* Denominator = 2. */
583 3919 : widest_int denom = 2;
584 :
585 : /* Index = Numerator-1. */
586 3919 : widest_int idx = num - 1;
587 :
588 : /* Numerator = Numerator*Index = n*(n-1). */
589 3919 : num = wi::smul (num, idx, &overflow);
590 3919 : if (overflow)
591 : return NULL_TREE;
592 :
593 3925 : for (i = 3; i <= k; i++)
594 : {
595 : /* Index--. */
596 6 : --idx;
597 :
598 : /* Numerator *= Index. */
599 6 : num = wi::smul (num, idx, &overflow);
600 6 : if (overflow)
601 : return NULL_TREE;
602 :
603 : /* Denominator *= i. */
604 6 : denom *= i;
605 : }
606 :
607 : /* Result = Numerator / Denominator. */
608 3919 : num = wi::udiv_trunc (num, denom);
609 3919 : if (! wi::fits_to_tree_p (num, type))
610 : return NULL_TREE;
611 3909 : return wide_int_to_tree (type, num);
612 7897 : }
613 :
614 : /* Helper function. Use the Newton's interpolating formula for
615 : evaluating the value of the evolution function.
616 : The result may be in an unsigned type of CHREC. */
617 :
618 : static tree
619 11931 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
620 : {
621 11931 : tree arg0, arg1, binomial_n_k;
622 11931 : tree type = TREE_TYPE (chrec);
623 11931 : class loop *var_loop = get_loop (cfun, var);
624 :
625 11931 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
626 11931 : && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
627 0 : chrec = CHREC_LEFT (chrec);
628 :
629 : /* The formula associates the expression and thus we have to make
630 : sure to not introduce undefined overflow. */
631 11931 : tree ctype = type;
632 11931 : if (INTEGRAL_TYPE_P (type)
633 11931 : && ! TYPE_OVERFLOW_WRAPS (type))
634 11613 : ctype = unsigned_type_for (type);
635 :
636 11931 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
637 11931 : && CHREC_VARIABLE (chrec) == var)
638 : {
639 7959 : arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
640 7959 : if (arg1 == chrec_dont_know)
641 : return chrec_dont_know;
642 7812 : binomial_n_k = tree_fold_binomial (ctype, n, k);
643 7812 : if (!binomial_n_k)
644 0 : return chrec_dont_know;
645 7812 : tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
646 7812 : arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
647 7812 : return chrec_fold_plus (ctype, arg0, arg1);
648 : }
649 :
650 3972 : binomial_n_k = tree_fold_binomial (ctype, n, k);
651 3972 : if (!binomial_n_k)
652 69 : return chrec_dont_know;
653 :
654 3903 : return fold_build2 (MULT_EXPR, ctype,
655 : chrec_convert (ctype, chrec, NULL), binomial_n_k);
656 : }
657 :
658 : /* Evaluates "CHREC (X)" when the varying variable is VAR.
659 : Example: Given the following parameters,
660 :
661 : var = 1
662 : chrec = {3, +, 4}_1
663 : x = 10
664 :
665 : The result is given by the Newton's interpolating formula:
666 : 3 * \binom{10}{0} + 4 * \binom{10}{1}.
667 : */
668 :
669 : tree
670 896871 : chrec_apply (unsigned var,
671 : tree chrec,
672 : tree x)
673 : {
674 896871 : tree type = chrec_type (chrec);
675 896871 : tree res = chrec_dont_know;
676 :
677 1793742 : if (automatically_generated_chrec_p (chrec)
678 1003247 : || automatically_generated_chrec_p (x)
679 :
680 : /* When the symbols are defined in an outer loop, it is possible
681 : to symbolically compute the apply, since the symbols are
682 : constants with respect to the varying loop. */
683 896871 : || chrec_contains_symbols_defined_in_loop (chrec, var))
684 106376 : return chrec_dont_know;
685 :
686 790495 : if (dump_file && (dump_flags & TDF_SCEV))
687 0 : fprintf (dump_file, "(chrec_apply \n");
688 :
689 790495 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
690 124 : x = build_real_from_int_cst (type, x);
691 :
692 790495 : switch (TREE_CODE (chrec))
693 : {
694 789092 : case POLYNOMIAL_CHREC:
695 789092 : if (evolution_function_is_affine_p (chrec))
696 : {
697 783839 : tree chrecr = CHREC_RIGHT (chrec);
698 783839 : tree chrecl = CHREC_LEFT (chrec);
699 783839 : if (CHREC_VARIABLE (chrec) != var)
700 526 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
701 : chrec_apply (var, chrecl, x),
702 : chrec_apply (var, chrecr, x));
703 :
704 : /* "{a, +, a}" (x-1) -> "a*x". */
705 783313 : else if (operand_equal_p (chrecl, chrecr)
706 136015 : && TREE_CODE (x) == PLUS_EXPR
707 7053 : && integer_all_onesp (TREE_OPERAND (x, 1))
708 6793 : && !POINTER_TYPE_P (type)
709 790095 : && TYPE_PRECISION (TREE_TYPE (x))
710 6782 : >= TYPE_PRECISION (type))
711 : {
712 : /* We know the number of iterations can't be negative. */
713 4929 : res = build_int_cst (TREE_TYPE (x), 1);
714 4929 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
715 4929 : res = chrec_convert_rhs (type, res, NULL);
716 4929 : res = chrec_fold_multiply (type, chrecr, res);
717 : }
718 : /* "{a, +, b} (x)" -> "a + b*x". */
719 : else
720 : {
721 : /* The overall increment might not fit in a signed type so
722 : use an unsigned computation to get at the final value
723 : and avoid undefined signed overflow. */
724 778384 : tree utype = TREE_TYPE (chrecr);
725 778384 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
726 686079 : utype = unsigned_type_for (TREE_TYPE (chrecr));
727 778384 : res = chrec_convert_rhs (utype, x, NULL);
728 778384 : res = chrec_fold_multiply (utype,
729 : chrec_convert (utype, chrecr, NULL),
730 : res);
731 : /* When the resulting increment fits the original type
732 : do the increment in it. */
733 778384 : if (TREE_CODE (res) == INTEGER_CST
734 778384 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
735 : {
736 400962 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
737 400962 : res = chrec_fold_plus (type, chrecl, res);
738 : }
739 : else
740 : {
741 377422 : res = chrec_fold_plus (utype,
742 : chrec_convert (utype, chrecl, NULL),
743 : res);
744 377422 : res = chrec_convert (type, res, NULL);
745 : }
746 : }
747 : }
748 5253 : else if (TREE_CODE (x) == INTEGER_CST
749 5253 : && tree_int_cst_sgn (x) == 1)
750 : /* testsuite/.../ssa-chrec-38.c. */
751 3972 : res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
752 : else
753 1281 : res = chrec_dont_know;
754 : break;
755 :
756 246 : CASE_CONVERT:
757 246 : res = chrec_convert (TREE_TYPE (chrec),
758 246 : chrec_apply (var, TREE_OPERAND (chrec, 0), x),
759 : NULL);
760 246 : break;
761 :
762 : default:
763 : res = chrec;
764 : break;
765 : }
766 :
767 790495 : if (dump_file && (dump_flags & TDF_SCEV))
768 : {
769 0 : fprintf (dump_file, " (varying_loop = %d", var);
770 0 : fprintf (dump_file, ")\n (chrec = ");
771 0 : print_generic_expr (dump_file, chrec);
772 0 : fprintf (dump_file, ")\n (x = ");
773 0 : print_generic_expr (dump_file, x);
774 0 : fprintf (dump_file, ")\n (res = ");
775 0 : print_generic_expr (dump_file, res);
776 0 : fprintf (dump_file, "))\n");
777 : }
778 :
779 : return res;
780 : }
781 :
782 : /* For a given CHREC and an induction variable map IV_MAP that maps
783 : (loop->num, expr) for every loop number of the current_loops an
784 : expression, calls chrec_apply when the expression is not NULL. */
785 :
786 : tree
787 888 : chrec_apply_map (tree chrec, vec<tree> iv_map)
788 : {
789 888 : int i;
790 888 : tree expr;
791 :
792 9821 : FOR_EACH_VEC_ELT (iv_map, i, expr)
793 8933 : if (expr)
794 1591 : chrec = chrec_apply (i, chrec, expr);
795 :
796 888 : return chrec;
797 : }
798 :
799 : /* Replaces the initial condition in CHREC with INIT_COND. */
800 :
801 : tree
802 2285840 : chrec_replace_initial_condition (tree chrec,
803 : tree init_cond)
804 : {
805 2285840 : if (automatically_generated_chrec_p (chrec))
806 : return chrec;
807 :
808 2285840 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
809 :
810 2285840 : switch (TREE_CODE (chrec))
811 : {
812 1153191 : case POLYNOMIAL_CHREC:
813 1153191 : return build_polynomial_chrec
814 1153191 : (CHREC_VARIABLE (chrec),
815 1153191 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
816 2306382 : CHREC_RIGHT (chrec));
817 :
818 : default:
819 : return init_cond;
820 : }
821 : }
822 :
823 : /* Returns the initial condition of a given CHREC. */
824 :
825 : tree
826 11145682 : initial_condition (tree chrec)
827 : {
828 18313065 : if (automatically_generated_chrec_p (chrec))
829 : return chrec;
830 :
831 17084898 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
832 7167383 : return initial_condition (CHREC_LEFT (chrec));
833 : else
834 : return chrec;
835 : }
836 :
837 : /* Returns a univariate function that represents the evolution in
838 : LOOP_NUM. Mask the evolution of any other loop. */
839 :
840 : tree
841 47907278 : hide_evolution_in_other_loops_than_loop (tree chrec,
842 : unsigned loop_num)
843 : {
844 47909931 : class loop *loop = get_loop (cfun, loop_num), *chloop;
845 47909931 : if (automatically_generated_chrec_p (chrec))
846 : return chrec;
847 :
848 47909931 : switch (TREE_CODE (chrec))
849 : {
850 2474124 : case POLYNOMIAL_CHREC:
851 2474124 : chloop = get_chrec_loop (chrec);
852 :
853 2474124 : if (chloop == loop)
854 2001758 : return build_polynomial_chrec
855 2001758 : (loop_num,
856 2001758 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
857 : loop_num),
858 4003516 : CHREC_RIGHT (chrec));
859 :
860 472366 : else if (flow_loop_nested_p (chloop, loop))
861 : /* There is no evolution in this loop. */
862 469713 : return initial_condition (chrec);
863 :
864 2653 : else if (flow_loop_nested_p (loop, chloop))
865 2653 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
866 2653 : loop_num);
867 :
868 : else
869 0 : return chrec_dont_know;
870 :
871 : default:
872 : return chrec;
873 : }
874 : }
875 :
876 : /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
877 : true, otherwise returns the initial condition in LOOP_NUM. */
878 :
879 : static tree
880 42392355 : chrec_component_in_loop_num (tree chrec,
881 : unsigned loop_num,
882 : bool right)
883 : {
884 42392355 : tree component;
885 42392355 : class loop *loop = get_loop (cfun, loop_num), *chloop;
886 :
887 42392355 : if (automatically_generated_chrec_p (chrec))
888 : return chrec;
889 :
890 41164188 : switch (TREE_CODE (chrec))
891 : {
892 35510682 : case POLYNOMIAL_CHREC:
893 35510682 : chloop = get_chrec_loop (chrec);
894 :
895 35510682 : if (chloop == loop)
896 : {
897 34178051 : if (right)
898 17396462 : component = CHREC_RIGHT (chrec);
899 : else
900 16781589 : component = CHREC_LEFT (chrec);
901 :
902 34178051 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
903 34178051 : || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
904 : return component;
905 :
906 : else
907 0 : return build_polynomial_chrec
908 0 : (loop_num,
909 0 : chrec_component_in_loop_num (CHREC_LEFT (chrec),
910 : loop_num,
911 : right),
912 0 : component);
913 : }
914 :
915 1332631 : else if (flow_loop_nested_p (chloop, loop))
916 : /* There is no evolution part in this loop. */
917 : return NULL_TREE;
918 :
919 : else
920 : {
921 1332631 : gcc_assert (flow_loop_nested_p (loop, chloop));
922 1332631 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
923 : loop_num,
924 1332631 : right);
925 : }
926 :
927 5653506 : default:
928 5653506 : if (right)
929 : return NULL_TREE;
930 : else
931 : return chrec;
932 : }
933 : }
934 :
935 : /* Returns the evolution part in LOOP_NUM. Example: the call
936 : evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
937 : {1, +, 2}_1 */
938 :
939 : tree
940 23430144 : evolution_part_in_loop_num (tree chrec,
941 : unsigned loop_num)
942 : {
943 23430144 : return chrec_component_in_loop_num (chrec, loop_num, true);
944 : }
945 :
946 : /* Returns the initial condition in LOOP_NUM. Example: the call
947 : initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
948 : {0, +, 1}_1 */
949 :
950 : tree
951 17629580 : initial_condition_in_loop_num (tree chrec,
952 : unsigned loop_num)
953 : {
954 17629580 : return chrec_component_in_loop_num (chrec, loop_num, false);
955 : }
956 :
957 : /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
958 : This function is essentially used for setting the evolution to
959 : chrec_dont_know, for example after having determined that it is
960 : impossible to say how many times a loop will execute. */
961 :
962 : tree
963 0 : reset_evolution_in_loop (unsigned loop_num,
964 : tree chrec,
965 : tree new_evol)
966 : {
967 0 : class loop *loop = get_loop (cfun, loop_num);
968 :
969 0 : if (POINTER_TYPE_P (chrec_type (chrec)))
970 0 : gcc_assert (ptrofftype_p (chrec_type (new_evol)));
971 : else
972 0 : gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
973 :
974 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
975 0 : && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
976 : {
977 0 : tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
978 : new_evol);
979 0 : tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
980 : new_evol);
981 0 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
982 : }
983 :
984 0 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
985 0 : && CHREC_VARIABLE (chrec) == loop_num)
986 0 : chrec = CHREC_LEFT (chrec);
987 :
988 0 : return build_polynomial_chrec (loop_num, chrec, new_evol);
989 : }
990 :
991 : /* Merges two evolution functions that were found by following two
992 : alternate paths of a conditional expression. */
993 :
994 : tree
995 16316778 : chrec_merge (tree chrec1,
996 : tree chrec2)
997 : {
998 16316778 : if (chrec1 == chrec_dont_know
999 16316778 : || chrec2 == chrec_dont_know)
1000 : return chrec_dont_know;
1001 :
1002 13669522 : if (chrec1 == chrec_known
1003 13669522 : || chrec2 == chrec_known)
1004 : return chrec_known;
1005 :
1006 13669522 : if (chrec1 == chrec_not_analyzed_yet)
1007 : return chrec2;
1008 2873794 : if (chrec2 == chrec_not_analyzed_yet)
1009 : return chrec1;
1010 :
1011 2873794 : if (eq_evolutions_p (chrec1, chrec2))
1012 : return chrec1;
1013 :
1014 2316506 : return chrec_dont_know;
1015 : }
1016 :
1017 :
1018 :
1019 : /* Observers. */
1020 :
1021 : /* Helper function for is_multivariate_chrec. */
1022 :
1023 : static bool
1024 0 : is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
1025 : {
1026 0 : if (chrec == NULL_TREE)
1027 : return false;
1028 :
1029 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1030 : {
1031 0 : if (CHREC_VARIABLE (chrec) != rec_var)
1032 : return true;
1033 : else
1034 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
1035 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
1036 : }
1037 : else
1038 : return false;
1039 : }
1040 :
1041 : /* Determine whether the given chrec is multivariate or not. */
1042 :
1043 : bool
1044 0 : is_multivariate_chrec (const_tree chrec)
1045 : {
1046 0 : if (chrec == NULL_TREE)
1047 : return false;
1048 :
1049 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1050 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
1051 0 : CHREC_VARIABLE (chrec))
1052 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
1053 0 : CHREC_VARIABLE (chrec)));
1054 : else
1055 : return false;
1056 : }
1057 :
1058 : /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
1059 : NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
1060 :
1061 : static bool
1062 37320510 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1063 : class loop *loop)
1064 : {
1065 37320510 : int i, n;
1066 :
1067 37320510 : if (chrec == NULL_TREE)
1068 : return false;
1069 :
1070 37320510 : if (TREE_CODE (chrec) == SSA_NAME
1071 : || VAR_P (chrec)
1072 : || TREE_CODE (chrec) == POLY_INT_CST
1073 : || TREE_CODE (chrec) == PARM_DECL
1074 : || TREE_CODE (chrec) == FUNCTION_DECL
1075 : || TREE_CODE (chrec) == LABEL_DECL
1076 : || TREE_CODE (chrec) == RESULT_DECL
1077 : || TREE_CODE (chrec) == FIELD_DECL)
1078 : return true;
1079 :
1080 31624969 : if (loop != NULL
1081 600 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1082 31625171 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1083 : return true;
1084 :
1085 31624969 : if (visited.add (chrec))
1086 : return false;
1087 :
1088 30993821 : n = TREE_OPERAND_LENGTH (chrec);
1089 79790034 : for (i = 0; i < n; i++)
1090 21744678 : if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
1091 : return true;
1092 : return false;
1093 : }
1094 :
1095 : /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
1096 : CHREC contains any chrec which is invariant wrto the loop (nest), in other
1097 : words, chrec defined by outer loops of loop, so from LOOP's point of view,
1098 : the chrec is considered as a SYMBOL. */
1099 :
1100 : bool
1101 15575832 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1102 : {
1103 15575832 : hash_set<const_tree> visited;
1104 15575832 : return chrec_contains_symbols (chrec, visited, loop);
1105 15575832 : }
1106 :
1107 : /* Return true when CHREC contains symbolic names defined in
1108 : LOOP_NB. */
1109 :
1110 : static bool
1111 335531516 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1112 : hash_set<const_tree> &visited)
1113 : {
1114 335531516 : int i, n;
1115 :
1116 335531516 : if (chrec == NULL_TREE)
1117 : return false;
1118 :
1119 335395919 : if (is_gimple_min_invariant (chrec))
1120 : return false;
1121 :
1122 198159789 : if (TREE_CODE (chrec) == SSA_NAME)
1123 : {
1124 71741295 : gimple *def;
1125 71741295 : loop_p def_loop, loop;
1126 :
1127 71741295 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1128 : return false;
1129 :
1130 67379241 : def = SSA_NAME_DEF_STMT (chrec);
1131 67379241 : def_loop = loop_containing_stmt (def);
1132 67379241 : loop = get_loop (cfun, loop_nb);
1133 :
1134 67379241 : if (def_loop == NULL)
1135 : return false;
1136 :
1137 67379241 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1138 4445963 : return true;
1139 :
1140 : return false;
1141 : }
1142 :
1143 126418494 : if (visited.add (chrec))
1144 : return false;
1145 :
1146 126376624 : n = TREE_OPERAND_LENGTH (chrec);
1147 462555025 : for (i = 0; i < n; i++)
1148 211120312 : if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1149 : loop_nb, visited))
1150 : return true;
1151 : return false;
1152 : }
1153 :
1154 : /* Return true when CHREC contains symbolic names defined in
1155 : LOOP_NB. */
1156 :
1157 : bool
1158 124411204 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1159 : {
1160 124411204 : hash_set<const_tree> visited;
1161 124411204 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1162 124411204 : }
1163 :
1164 : /* Determines whether the chrec contains undetermined coefficients. */
1165 :
1166 : static bool
1167 224646391 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1168 : {
1169 224646391 : int i, n;
1170 :
1171 224646391 : if (chrec == chrec_dont_know)
1172 : return true;
1173 :
1174 201819659 : if (chrec == NULL_TREE)
1175 : return false;
1176 :
1177 201457854 : if (visited.add (chrec))
1178 : return false;
1179 :
1180 188383415 : n = TREE_OPERAND_LENGTH (chrec);
1181 500472596 : for (i = 0; i < n; i++)
1182 123706951 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1183 : return true;
1184 : return false;
1185 : }
1186 :
1187 : bool
1188 100939440 : chrec_contains_undetermined (const_tree chrec)
1189 : {
1190 100939440 : hash_set<const_tree> visited;
1191 100939440 : return chrec_contains_undetermined (chrec, visited);
1192 100939440 : }
1193 :
1194 : /* Determines whether the tree EXPR contains chrecs, and increment
1195 : SIZE if it is not a NULL pointer by an estimation of the depth of
1196 : the tree. */
1197 :
1198 : static bool
1199 433090181 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1200 : {
1201 433090181 : int i, n;
1202 :
1203 433090181 : if (expr == NULL_TREE)
1204 : return false;
1205 :
1206 432000617 : if (size)
1207 76299844 : (*size)++;
1208 :
1209 432374493 : if (tree_is_chrec (expr))
1210 : return true;
1211 :
1212 409338105 : if (visited.add (expr))
1213 : return false;
1214 :
1215 406800530 : n = TREE_OPERAND_LENGTH (expr);
1216 1022017214 : for (i = 0; i < n; i++)
1217 208711891 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1218 : return true;
1219 : return false;
1220 : }
1221 :
1222 : bool
1223 224378290 : tree_contains_chrecs (const_tree expr, int *size)
1224 : {
1225 224378290 : hash_set<const_tree> visited;
1226 224378290 : return tree_contains_chrecs (expr, size, visited);
1227 224378290 : }
1228 :
1229 :
1230 : /* Recursive helper function. */
1231 :
1232 : static bool
1233 45817443 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1234 : {
1235 91634886 : if (evolution_function_is_constant_p (chrec))
1236 : return true;
1237 :
1238 9938601 : if (TREE_CODE (chrec) == SSA_NAME
1239 9938601 : && (loopnum == 0
1240 2191128 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1241 2168290 : return true;
1242 :
1243 7770311 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1244 : {
1245 6101800 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1246 132343 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1247 132343 : get_chrec_loop (chrec))
1248 3246 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1249 : loopnum)
1250 6105046 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1251 : loopnum))
1252 6098554 : return false;
1253 : return true;
1254 : }
1255 :
1256 1668511 : switch (TREE_OPERAND_LENGTH (chrec))
1257 : {
1258 936925 : case 2:
1259 936925 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1260 : loopnum))
1261 : return false;
1262 : /* FALLTHRU */
1263 :
1264 1604243 : case 1:
1265 1604243 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1266 : loopnum))
1267 : return false;
1268 : return true;
1269 :
1270 : default:
1271 : return false;
1272 : }
1273 : }
1274 :
1275 : /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1276 :
1277 : bool
1278 30840449 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1279 : {
1280 30840449 : return evolution_function_is_invariant_rec_p (chrec, loopnum);
1281 : }
1282 :
1283 : /* Determine whether the given tree is an affine multivariate
1284 : evolution. */
1285 :
1286 : bool
1287 6760413 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1288 : {
1289 6760413 : if (chrec == NULL_TREE)
1290 : return false;
1291 :
1292 6760413 : switch (TREE_CODE (chrec))
1293 : {
1294 6214667 : case POLYNOMIAL_CHREC:
1295 6214667 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1296 : {
1297 6113641 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1298 : return true;
1299 : else
1300 : {
1301 203 : if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1302 203 : && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1303 203 : != CHREC_VARIABLE (chrec)
1304 203 : && evolution_function_is_affine_multivariate_p
1305 0 : (CHREC_RIGHT (chrec), loopnum))
1306 : return true;
1307 : else
1308 203 : return false;
1309 : }
1310 : }
1311 : else
1312 : {
1313 101026 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1314 101026 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1315 100985 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1316 202011 : && evolution_function_is_affine_multivariate_p
1317 100985 : (CHREC_LEFT (chrec), loopnum))
1318 : return true;
1319 : else
1320 41 : return false;
1321 : }
1322 :
1323 : default:
1324 : return false;
1325 : }
1326 : }
1327 :
1328 : /* Determine whether the given tree is a function in zero or one
1329 : variables with respect to loop specified by LOOPNUM. Note only positive
1330 : LOOPNUM stands for a real loop. */
1331 :
1332 : bool
1333 3460037 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1334 : {
1335 3460037 : if (chrec == NULL_TREE)
1336 : return true;
1337 :
1338 3460037 : tree sub_chrec;
1339 3460037 : switch (TREE_CODE (chrec))
1340 : {
1341 3460034 : case POLYNOMIAL_CHREC:
1342 3460034 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1343 : {
1344 31405 : case POLYNOMIAL_CHREC:
1345 31405 : sub_chrec = CHREC_LEFT (chrec);
1346 31405 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1347 31405 : && (loopnum <= 0
1348 5041 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1349 18 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1350 18 : get_chrec_loop (sub_chrec))))
1351 31393 : return false;
1352 12 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1353 : return false;
1354 : break;
1355 :
1356 3428629 : default:
1357 3428629 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1358 : return false;
1359 : break;
1360 : }
1361 :
1362 3428641 : switch (TREE_CODE (CHREC_RIGHT (chrec)))
1363 : {
1364 0 : case POLYNOMIAL_CHREC:
1365 0 : sub_chrec = CHREC_RIGHT (chrec);
1366 0 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1367 0 : && (loopnum <= 0
1368 0 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1369 0 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1370 0 : get_chrec_loop (sub_chrec))))
1371 0 : return false;
1372 0 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1373 : return false;
1374 : break;
1375 :
1376 3428641 : default:
1377 3428641 : if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1378 : return false;
1379 : break;
1380 : }
1381 : return true;
1382 :
1383 : default:
1384 : return true;
1385 : }
1386 : }
1387 :
1388 : /* Returns the number of variables of CHREC. Example: the call
1389 : nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1390 :
1391 : unsigned
1392 3369916 : nb_vars_in_chrec (tree chrec)
1393 : {
1394 6739832 : if (chrec == NULL_TREE)
1395 : return 0;
1396 :
1397 6739832 : switch (TREE_CODE (chrec))
1398 : {
1399 3369916 : case POLYNOMIAL_CHREC:
1400 3369916 : return 1 + nb_vars_in_chrec
1401 3369916 : (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1402 :
1403 : default:
1404 : return 0;
1405 : }
1406 : }
1407 :
1408 : /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1409 : the scev corresponds to. AT_STMT is the statement at that the scev is
1410 : evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1411 : that the rules for overflow of the given language apply (e.g., that signed
1412 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1413 : unnecessary tests, but also to enforce that the result follows them.
1414 : FROM is the source variable converted if it's not NULL. Returns true if
1415 : the conversion succeeded, false otherwise. */
1416 :
1417 : bool
1418 7401446 : convert_affine_scev (class loop *loop, tree type,
1419 : tree *base, tree *step, gimple *at_stmt,
1420 : bool use_overflow_semantics, tree from)
1421 : {
1422 7401446 : tree ct = TREE_TYPE (*step);
1423 7401446 : bool enforce_overflow_semantics;
1424 7401446 : bool must_check_src_overflow, must_check_rslt_overflow;
1425 7401446 : tree new_base, new_step;
1426 7401446 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1427 :
1428 : /* In general,
1429 : (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1430 : but we must check some assumptions.
1431 :
1432 : 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1433 : of CT is smaller than the precision of TYPE. For example, when we
1434 : cast unsigned char [254, +, 1] to unsigned, the values on left side
1435 : are 254, 255, 0, 1, ..., but those on the right side are
1436 : 254, 255, 256, 257, ...
1437 : 2) In case that we must also preserve the fact that signed ivs do not
1438 : overflow, we must additionally check that the new iv does not wrap.
1439 : For example, unsigned char [125, +, 1] casted to signed char could
1440 : become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1441 : which would confuse optimizers that assume that this does not
1442 : happen. */
1443 7401446 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1444 :
1445 16847042 : enforce_overflow_semantics = (use_overflow_semantics
1446 7401446 : && nowrap_type_p (type));
1447 2422389 : if (enforce_overflow_semantics)
1448 : {
1449 : /* We can avoid checking whether the result overflows in the following
1450 : cases:
1451 :
1452 : -- must_check_src_overflow is true, and the range of TYPE is superset
1453 : of the range of CT -- i.e., in all cases except if CT signed and
1454 : TYPE unsigned.
1455 : -- both CT and TYPE have the same precision and signedness, and we
1456 : verify instead that the source does not overflow (this may be
1457 : easier than verifying it for the result, as we may use the
1458 : information about the semantics of overflow in CT). */
1459 2422389 : if (must_check_src_overflow)
1460 : {
1461 441876 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1462 : must_check_rslt_overflow = true;
1463 : else
1464 : must_check_rslt_overflow = false;
1465 : }
1466 1980513 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1467 1980513 : && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1468 : {
1469 : must_check_rslt_overflow = false;
1470 : must_check_src_overflow = true;
1471 : }
1472 : else
1473 : must_check_rslt_overflow = true;
1474 : }
1475 : else
1476 : must_check_rslt_overflow = false;
1477 :
1478 7023207 : if (must_check_src_overflow
1479 7401446 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1480 : use_overflow_semantics))
1481 : return false;
1482 :
1483 6621475 : new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1484 : /* The step must be sign extended, regardless of the signedness
1485 : of CT and TYPE. This only needs to be handled specially when
1486 : CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1487 : (with values 100, 99, 98, ...) from becoming signed or unsigned
1488 : [100, +, 255] with values 100, 355, ...; the sign-extension is
1489 : performed by default when CT is signed. */
1490 6621475 : new_step = *step;
1491 6621475 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1492 : {
1493 122247 : tree signed_ct = signed_type_for (ct);
1494 122247 : new_step = chrec_convert (signed_ct, new_step, at_stmt,
1495 : use_overflow_semantics);
1496 : }
1497 6621475 : new_step = chrec_convert (step_type, new_step, at_stmt,
1498 : use_overflow_semantics);
1499 :
1500 13242950 : if (automatically_generated_chrec_p (new_base)
1501 2014668 : || automatically_generated_chrec_p (new_step))
1502 : return false;
1503 :
1504 6621217 : if (must_check_rslt_overflow
1505 : /* Note that in this case we cannot use the fact that signed variables
1506 : do not overflow, as this is what we are verifying for the new iv. */
1507 6621217 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1508 : at_stmt, loop, false))
1509 : return false;
1510 :
1511 5386778 : *base = new_base;
1512 5386778 : *step = new_step;
1513 5386778 : return true;
1514 : }
1515 :
1516 :
1517 : /* Convert CHREC for the right hand side of a CHREC.
1518 : The increment for a pointer type is always sizetype. */
1519 :
1520 : tree
1521 31214759 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1522 : {
1523 31214759 : if (POINTER_TYPE_P (type))
1524 5922525 : type = sizetype;
1525 :
1526 31214759 : return chrec_convert (type, chrec, at_stmt);
1527 : }
1528 :
1529 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1530 : which the CHREC is built, it sets AT_STMT to the statement that
1531 : contains the definition of the analyzed variable, otherwise the
1532 : conversion is less accurate: the information is used for
1533 : determining a more accurate estimation of the number of iterations.
1534 : By default AT_STMT could be safely set to NULL_TREE.
1535 :
1536 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1537 : the rules for overflow of the given language apply (e.g., that signed
1538 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1539 : unnecessary tests, but also to enforce that the result follows them.
1540 :
1541 : FROM is the source variable converted if it's not NULL. */
1542 :
1543 : static tree
1544 156040489 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1545 : bool use_overflow_semantics, tree from)
1546 : {
1547 156040489 : tree ct, res;
1548 156040489 : tree base, step;
1549 156040489 : class loop *loop;
1550 :
1551 269677451 : if (automatically_generated_chrec_p (chrec))
1552 : return chrec;
1553 :
1554 154762065 : ct = chrec_type (chrec);
1555 154762065 : if (useless_type_conversion_p (type, ct))
1556 : return chrec;
1557 :
1558 41125103 : if (!evolution_function_is_affine_p (chrec))
1559 35093900 : goto keep_cast;
1560 :
1561 6031203 : loop = get_chrec_loop (chrec);
1562 6031203 : base = CHREC_LEFT (chrec);
1563 6031203 : step = CHREC_RIGHT (chrec);
1564 :
1565 6031203 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1566 : use_overflow_semantics, from))
1567 4509614 : return build_polynomial_chrec (loop->num, base, step);
1568 :
1569 : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1570 1521589 : keep_cast:
1571 : /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1572 : may be more expensive. We do want to perform this optimization here
1573 : though for canonicalization reasons. */
1574 36615489 : if (use_overflow_semantics
1575 35965549 : && (TREE_CODE (chrec) == PLUS_EXPR
1576 35965549 : || TREE_CODE (chrec) == MINUS_EXPR)
1577 3484511 : && TREE_CODE (type) == INTEGER_TYPE
1578 3440862 : && TREE_CODE (ct) == INTEGER_TYPE
1579 3440816 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1580 36781414 : && TYPE_OVERFLOW_UNDEFINED (ct))
1581 60632 : res = fold_build2 (TREE_CODE (chrec), type,
1582 : fold_convert (type, TREE_OPERAND (chrec, 0)),
1583 : fold_convert (type, TREE_OPERAND (chrec, 1)));
1584 : /* Similar perform the trick that (signed char)((int)x + 2) can be
1585 : narrowed to (signed char)((unsigned char)x + 2). */
1586 36554857 : else if (use_overflow_semantics
1587 35904917 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1588 1551733 : && TREE_CODE (ct) == INTEGER_TYPE
1589 1539718 : && TREE_CODE (type) == INTEGER_TYPE
1590 1400573 : && TYPE_OVERFLOW_UNDEFINED (type)
1591 37709255 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1592 : {
1593 28770 : tree utype = unsigned_type_for (type);
1594 86310 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1595 28770 : fold_convert (utype,
1596 : CHREC_LEFT (chrec)),
1597 28770 : fold_convert (utype,
1598 : CHREC_RIGHT (chrec)));
1599 28770 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1600 : }
1601 : /* Similar perform the trick that (unsigned T)(base + step) can be
1602 : folded to ((unsigned T)x + (unsigned T)step). */
1603 36526087 : else if (use_overflow_semantics
1604 35876147 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1605 1522963 : && INTEGRAL_TYPE_P (ct)
1606 1511028 : && INTEGRAL_TYPE_P (type)
1607 1371883 : && TYPE_OVERFLOW_UNDEFINED (type)
1608 : /* Must be unsigned so we don't introduce any UB. */
1609 1125708 : && TYPE_UNSIGNED (type)
1610 : /* The outer type must at least as wide than the inner type so we
1611 : don't truncate when we fold and must the inner CHREC must be
1612 : non-wrapping so we don't change the behavior when folding to
1613 : a wider type. */
1614 0 : && TYPE_PRECISION (type) >= TYPE_PRECISION (ct)
1615 36526087 : && (!TYPE_UNSIGNED (ct)
1616 0 : || TYPE_PRECISION (type) == TYPE_PRECISION (ct)
1617 0 : || nonwrapping_chrec_p (chrec)))
1618 : {
1619 0 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1620 0 : fold_convert (type,
1621 : CHREC_LEFT (chrec)),
1622 0 : fold_convert (type,
1623 : CHREC_RIGHT (chrec)));
1624 0 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1625 : }
1626 : else
1627 36526087 : res = fold_convert (type, chrec);
1628 :
1629 : /* Don't propagate overflows. */
1630 36615489 : if (CONSTANT_CLASS_P (res))
1631 11871628 : TREE_OVERFLOW (res) = 0;
1632 :
1633 : /* But reject constants that don't fit in their type after conversion.
1634 : This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1635 : natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1636 : and can cause problems later when computing niters of loops. Note
1637 : that we don't do the check before converting because we don't want
1638 : to reject conversions of negative chrecs to unsigned types. */
1639 36615489 : if (TREE_CODE (res) == INTEGER_CST
1640 11871627 : && TREE_CODE (type) == INTEGER_TYPE
1641 11828666 : && !int_fits_type_p (res, type))
1642 365 : res = chrec_dont_know;
1643 :
1644 : return res;
1645 : }
1646 :
1647 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1648 : which the CHREC is built, it sets AT_STMT to the statement that
1649 : contains the definition of the analyzed variable, otherwise the
1650 : conversion is less accurate: the information is used for
1651 : determining a more accurate estimation of the number of iterations.
1652 : By default AT_STMT could be safely set to NULL_TREE.
1653 :
1654 : The following rule is always true: TREE_TYPE (chrec) ==
1655 : TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1656 : An example of what could happen when adding two chrecs and the type
1657 : of the CHREC_RIGHT is different than CHREC_LEFT is:
1658 :
1659 : {(uint) 0, +, (uchar) 10} +
1660 : {(uint) 0, +, (uchar) 250}
1661 :
1662 : that would produce a wrong result if CHREC_RIGHT is not (uint):
1663 :
1664 : {(uint) 0, +, (uchar) 4}
1665 :
1666 : instead of
1667 :
1668 : {(uint) 0, +, (uint) 260}
1669 :
1670 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1671 : the rules for overflow of the given language apply (e.g., that signed
1672 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1673 : unnecessary tests, but also to enforce that the result follows them.
1674 :
1675 : FROM is the source variable converted if it's not NULL. */
1676 :
1677 : tree
1678 156011719 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1679 : bool use_overflow_semantics, tree from)
1680 : {
1681 156011719 : return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1682 : }
1683 :
1684 : /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1685 : chrec if something else than what chrec_convert would do happens, NULL_TREE
1686 : otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1687 : if the result chrec may overflow. */
1688 :
1689 : tree
1690 8517639 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1691 : {
1692 8517639 : tree inner_type, left, right, lc, rc, rtype;
1693 :
1694 8517639 : gcc_assert (fold_conversions != NULL);
1695 :
1696 16542696 : if (automatically_generated_chrec_p (chrec)
1697 8517639 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1698 : return NULL_TREE;
1699 :
1700 644679 : inner_type = TREE_TYPE (chrec);
1701 644679 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1702 : return NULL_TREE;
1703 :
1704 561581 : if (useless_type_conversion_p (type, inner_type))
1705 : return NULL_TREE;
1706 :
1707 492582 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1708 : {
1709 491772 : tree base, step;
1710 491772 : class loop *loop;
1711 :
1712 491772 : loop = get_chrec_loop (chrec);
1713 491772 : base = CHREC_LEFT (chrec);
1714 491772 : step = CHREC_RIGHT (chrec);
1715 491772 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1716 2002 : return build_polynomial_chrec (loop->num, base, step);
1717 : }
1718 490580 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1719 :
1720 490580 : left = CHREC_LEFT (chrec);
1721 490580 : right = CHREC_RIGHT (chrec);
1722 490580 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1723 490580 : if (!lc)
1724 490580 : lc = chrec_convert (type, left, NULL);
1725 490580 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1726 490580 : if (!rc)
1727 489896 : rc = chrec_convert (rtype, right, NULL);
1728 :
1729 490580 : *fold_conversions = true;
1730 :
1731 490580 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1732 : }
1733 :
1734 : /* Returns true when CHREC0 == CHREC1. */
1735 :
1736 : bool
1737 13426948 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1738 : {
1739 13459490 : if (chrec0 == NULL_TREE
1740 13459490 : || chrec1 == NULL_TREE
1741 13459490 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1742 : return false;
1743 :
1744 12551936 : if (operand_equal_p (chrec0, chrec1, 0))
1745 : return true;
1746 :
1747 9381667 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1748 : return false;
1749 :
1750 9380473 : switch (TREE_CODE (chrec0))
1751 : {
1752 3883513 : case POLYNOMIAL_CHREC:
1753 3883513 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1754 3883176 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1755 4217229 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1756 :
1757 55752 : case PLUS_EXPR:
1758 55752 : case MULT_EXPR:
1759 55752 : case MINUS_EXPR:
1760 55752 : case POINTER_PLUS_EXPR:
1761 55752 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1762 55752 : TREE_OPERAND (chrec1, 0))
1763 97522 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1764 41770 : TREE_OPERAND (chrec1, 1));
1765 :
1766 32542 : CASE_CONVERT:
1767 32542 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1768 65084 : TREE_OPERAND (chrec1, 0));
1769 :
1770 : default:
1771 : return false;
1772 : }
1773 : }
1774 :
1775 : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1776 : EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1777 : which of these cases happens. */
1778 :
1779 : enum ev_direction
1780 3547235 : scev_direction (const_tree chrec)
1781 : {
1782 3547235 : const_tree step;
1783 :
1784 3547235 : if (!evolution_function_is_affine_p (chrec))
1785 : return EV_DIR_UNKNOWN;
1786 :
1787 3538485 : step = CHREC_RIGHT (chrec);
1788 3538485 : if (TREE_CODE (step) != INTEGER_CST)
1789 : return EV_DIR_UNKNOWN;
1790 :
1791 3352519 : if (tree_int_cst_sign_bit (step))
1792 : return EV_DIR_DECREASES;
1793 : else
1794 3013862 : return EV_DIR_GROWS;
1795 : }
1796 :
1797 : /* Iterates over all the components of SCEV, and calls CBCK. */
1798 :
1799 : void
1800 0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1801 : {
1802 0 : switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1803 : {
1804 0 : case 3:
1805 0 : for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1806 : /* FALLTHRU */
1807 :
1808 0 : case 2:
1809 0 : for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1810 : /* FALLTHRU */
1811 :
1812 0 : case 1:
1813 0 : for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1814 : /* FALLTHRU */
1815 :
1816 0 : default:
1817 0 : cbck (scev, data);
1818 0 : break;
1819 : }
1820 0 : }
1821 :
1822 : /* Returns true when the operation can be part of a linear
1823 : expression. */
1824 :
1825 : static inline bool
1826 34001 : operator_is_linear (tree scev)
1827 : {
1828 34001 : switch (TREE_CODE (scev))
1829 : {
1830 : case INTEGER_CST:
1831 : case POLYNOMIAL_CHREC:
1832 : case PLUS_EXPR:
1833 : case POINTER_PLUS_EXPR:
1834 : case MULT_EXPR:
1835 : case MINUS_EXPR:
1836 : case NEGATE_EXPR:
1837 : case SSA_NAME:
1838 : case NON_LVALUE_EXPR:
1839 : case BIT_NOT_EXPR:
1840 : CASE_CONVERT:
1841 : return true;
1842 :
1843 8 : default:
1844 8 : return false;
1845 : }
1846 : }
1847 :
1848 : /* Return true when SCEV is a linear expression. Linear expressions
1849 : can contain additions, substractions and multiplications.
1850 : Multiplications are restricted to constant scaling: "cst * x". */
1851 :
1852 : bool
1853 77813 : scev_is_linear_expression (tree scev)
1854 : {
1855 160178 : if (evolution_function_is_constant_p (scev))
1856 : return true;
1857 :
1858 34001 : if (scev == NULL
1859 34001 : || !operator_is_linear (scev))
1860 : return false;
1861 :
1862 33993 : if (TREE_CODE (scev) == MULT_EXPR)
1863 601 : return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1864 0 : && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1865 :
1866 33392 : if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1867 33392 : && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1868 : return false;
1869 :
1870 33192 : switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1871 : {
1872 0 : case 3:
1873 0 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1874 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1875 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1876 :
1877 24441 : case 2:
1878 24441 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1879 24441 : && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1880 :
1881 2276 : case 1:
1882 2276 : return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1883 :
1884 : case 0:
1885 : return true;
1886 :
1887 : default:
1888 : return false;
1889 : }
1890 : }
1891 :
1892 : /* Determines whether the expression CHREC contains only interger consts
1893 : in the right parts. */
1894 :
1895 : bool
1896 4313 : evolution_function_right_is_integer_cst (const_tree chrec)
1897 : {
1898 4313 : if (chrec == NULL_TREE)
1899 : return false;
1900 :
1901 4313 : switch (TREE_CODE (chrec))
1902 : {
1903 : case INTEGER_CST:
1904 : return true;
1905 :
1906 4313 : case POLYNOMIAL_CHREC:
1907 4313 : return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1908 4313 : && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1909 470 : || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1910 :
1911 0 : CASE_CONVERT:
1912 0 : return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1913 :
1914 : default:
1915 : return false;
1916 : }
1917 : }
|
