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 88425 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : tree type,
50 : tree poly0,
51 : tree poly1)
52 : {
53 88425 : tree left, right;
54 88425 : class loop *loop0 = get_chrec_loop (poly0);
55 88425 : class loop *loop1 = get_chrec_loop (poly1);
56 88425 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
57 :
58 88425 : gcc_assert (poly0);
59 88425 : gcc_assert (poly1);
60 88425 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
61 88425 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
62 88425 : if (POINTER_TYPE_P (chrec_type (poly0)))
63 865 : gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
64 : && useless_type_conversion_p (type, chrec_type (poly0)));
65 : else
66 87560 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
67 : && useless_type_conversion_p (type, chrec_type (poly1)));
68 :
69 : /*
70 : {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
71 : {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
72 : {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
73 88425 : if (flow_loop_nested_p (loop0, loop1))
74 : {
75 296 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
76 232 : return build_polynomial_chrec
77 232 : (CHREC_VARIABLE (poly1),
78 232 : chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
79 464 : CHREC_RIGHT (poly1));
80 : else
81 64 : return build_polynomial_chrec
82 128 : (CHREC_VARIABLE (poly1),
83 64 : chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
84 64 : chrec_fold_multiply (type, CHREC_RIGHT (poly1),
85 64 : SCALAR_FLOAT_TYPE_P (type)
86 0 : ? build_real (type, dconstm1)
87 128 : : build_int_cst_type (type, -1)));
88 : }
89 :
90 88129 : if (flow_loop_nested_p (loop1, loop0))
91 : {
92 602 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
93 556 : return build_polynomial_chrec
94 556 : (CHREC_VARIABLE (poly0),
95 556 : chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
96 1112 : CHREC_RIGHT (poly0));
97 : else
98 46 : return build_polynomial_chrec
99 46 : (CHREC_VARIABLE (poly0),
100 46 : chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
101 92 : CHREC_RIGHT (poly0));
102 : }
103 :
104 : /* This function should never be called for chrecs of loops that
105 : do not belong to the same loop nest. */
106 87527 : if (loop0 != loop1)
107 : {
108 : /* It still can happen if we are not in loop-closed SSA form. */
109 32 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
110 32 : return chrec_dont_know;
111 : }
112 :
113 87495 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
114 : {
115 32784 : left = chrec_fold_plus
116 32784 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 32784 : right = chrec_fold_plus
118 32784 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : }
120 : else
121 : {
122 54711 : left = chrec_fold_minus
123 54711 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 54711 : right = chrec_fold_minus
125 54711 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : }
127 :
128 87495 : if (chrec_zerop (right))
129 : return left;
130 : else
131 33057 : return build_polynomial_chrec
132 33057 : (CHREC_VARIABLE (poly0), left, right);
133 : }
134 :
135 :
136 :
137 : /* Fold the multiplication of two polynomial functions. */
138 :
139 : static inline tree
140 40247 : chrec_fold_multiply_poly_poly (tree type,
141 : tree poly0,
142 : tree poly1)
143 : {
144 40247 : tree t0, t1, t2;
145 40247 : int var;
146 40247 : class loop *loop0 = get_chrec_loop (poly0);
147 40247 : class loop *loop1 = get_chrec_loop (poly1);
148 :
149 40247 : gcc_assert (poly0);
150 40247 : gcc_assert (poly1);
151 40247 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
152 40247 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
153 40247 : 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 40247 : 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 40247 : 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 40247 : 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 40247 : t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
185 :
186 : /* "a*d + b*c". */
187 40247 : t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
188 120741 : t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
189 40247 : CHREC_RIGHT (poly0),
190 40247 : CHREC_LEFT (poly1)));
191 : /* "b*d". */
192 40247 : t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
193 : /* "a*d + b*c + b*d". */
194 40247 : t1 = chrec_fold_plus (type, t1, t2);
195 : /* "2*b*d". */
196 80494 : t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
197 33 : ? build_real (type, dconst2)
198 40214 : : build_int_cst (type, 2), t2);
199 :
200 40247 : var = CHREC_VARIABLE (poly0);
201 40247 : return build_polynomial_chrec (var, t0,
202 40247 : 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 5853010 : chrec_fold_automatically_generated_operands (tree op0,
210 : tree op1)
211 : {
212 5853010 : if (op0 == chrec_dont_know
213 940940 : || 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 30469822 : chrec_fold_plus_1 (enum tree_code code, tree type,
232 : tree op0, tree op1)
233 : {
234 60939644 : if (automatically_generated_chrec_p (op0)
235 30469822 : || automatically_generated_chrec_p (op1))
236 0 : return chrec_fold_automatically_generated_operands (op0, op1);
237 :
238 30469822 : switch (TREE_CODE (op0))
239 : {
240 9711496 : case POLYNOMIAL_CHREC:
241 9711496 : gcc_checking_assert
242 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
243 9711496 : switch (TREE_CODE (op1))
244 : {
245 88425 : case POLYNOMIAL_CHREC:
246 88425 : gcc_checking_assert
247 : (!chrec_contains_symbols_defined_in_loop (op1,
248 : CHREC_VARIABLE (op1)));
249 88425 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
250 :
251 161547 : CASE_CONVERT:
252 161547 : if (tree_contains_chrecs (op1, NULL))
253 : {
254 : /* We can strip sign-conversions to signed by performing the
255 : operation in unsigned. */
256 694 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
257 694 : if (INTEGRAL_TYPE_P (type)
258 694 : && INTEGRAL_TYPE_P (optype)
259 669 : && tree_nop_conversion_p (type, optype)
260 894 : && TYPE_UNSIGNED (optype))
261 : {
262 81 : tree tem = chrec_convert (optype, op0, NULL);
263 81 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
264 24 : return chrec_convert (type,
265 : chrec_fold_plus_1 (code, optype,
266 : tem,
267 24 : TREE_OPERAND
268 : (op1, 0)),
269 24 : NULL);
270 : }
271 670 : return chrec_dont_know;
272 : }
273 : /* FALLTHRU */
274 :
275 9622377 : default:
276 9622377 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
277 8845186 : return build_polynomial_chrec
278 8845186 : (CHREC_VARIABLE (op0),
279 8845186 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
280 17690372 : CHREC_RIGHT (op0));
281 : else
282 777191 : return build_polynomial_chrec
283 777191 : (CHREC_VARIABLE (op0),
284 777191 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
285 1554382 : CHREC_RIGHT (op0));
286 : }
287 :
288 2892107 : CASE_CONVERT:
289 2892107 : if (tree_contains_chrecs (op0, NULL))
290 : {
291 : /* We can strip sign-conversions to signed by performing the
292 : operation in unsigned. */
293 41494 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
294 41494 : if (INTEGRAL_TYPE_P (type)
295 40094 : && INTEGRAL_TYPE_P (optype)
296 36083 : && tree_nop_conversion_p (type, optype)
297 67820 : && TYPE_UNSIGNED (optype))
298 52584 : return chrec_convert (type,
299 : chrec_fold_plus_1 (code, optype,
300 26292 : TREE_OPERAND (op0, 0),
301 : chrec_convert (optype,
302 : op1, NULL)),
303 26292 : NULL);
304 15202 : return chrec_dont_know;
305 : }
306 : /* FALLTHRU */
307 :
308 20716832 : default:
309 20716832 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
310 20716832 : switch (TREE_CODE (op1))
311 : {
312 3082965 : case POLYNOMIAL_CHREC:
313 3082965 : gcc_checking_assert
314 : (!chrec_contains_symbols_defined_in_loop (op1,
315 : CHREC_VARIABLE (op1)));
316 3082965 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
317 3016344 : return build_polynomial_chrec
318 3016344 : (CHREC_VARIABLE (op1),
319 3016344 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
320 6032688 : CHREC_RIGHT (op1));
321 : else
322 66621 : return build_polynomial_chrec
323 133242 : (CHREC_VARIABLE (op1),
324 66621 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
325 66621 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
326 66621 : SCALAR_FLOAT_TYPE_P (type)
327 4 : ? build_real (type, dconstm1)
328 133238 : : build_int_cst_type (type, -1)));
329 :
330 2139548 : CASE_CONVERT:
331 2139548 : if (tree_contains_chrecs (op1, NULL))
332 : {
333 : /* We can strip sign-conversions to signed by performing the
334 : operation in unsigned. */
335 78919 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
336 78919 : if (INTEGRAL_TYPE_P (type)
337 22157 : && INTEGRAL_TYPE_P (optype)
338 22157 : && tree_nop_conversion_p (type, optype)
339 96947 : && TYPE_UNSIGNED (optype))
340 18028 : return chrec_convert (type,
341 : chrec_fold_plus_1 (code, optype,
342 : chrec_convert (optype,
343 : op0,
344 : NULL),
345 18028 : TREE_OPERAND (op1, 0)),
346 18028 : NULL);
347 60891 : return chrec_dont_know;
348 : }
349 : /* FALLTHRU */
350 :
351 17554948 : default:
352 17554948 : {
353 17554948 : int size = 0;
354 17554948 : if ((tree_contains_chrecs (op0, &size)
355 17554948 : || tree_contains_chrecs (op1, &size))
356 17554948 : && size < param_scev_max_expr_size)
357 0 : return build2 (code, type, op0, op1);
358 17554948 : else if (size < param_scev_max_expr_size)
359 : {
360 17554848 : if (code == POINTER_PLUS_EXPR)
361 3487230 : return fold_build_pointer_plus (fold_convert (type, op0),
362 : op1);
363 : else
364 14067618 : 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 36700251 : chrec_fold_plus (tree type,
379 : tree op0,
380 : tree op1)
381 : {
382 36700251 : enum tree_code code;
383 70485306 : if (automatically_generated_chrec_p (op0)
384 36700251 : || automatically_generated_chrec_p (op1))
385 3568502 : return chrec_fold_automatically_generated_operands (op0, op1);
386 :
387 33131749 : if (integer_zerop (op0))
388 4058092 : return chrec_convert (type, op1, NULL);
389 29073657 : if (integer_zerop (op1))
390 1843436 : return chrec_convert (type, op0, NULL);
391 :
392 27230221 : if (POINTER_TYPE_P (type))
393 : code = POINTER_PLUS_EXPR;
394 : else
395 20818717 : code = PLUS_EXPR;
396 :
397 27230221 : return chrec_fold_plus_1 (code, type, op0, op1);
398 : }
399 :
400 : /* Fold the subtraction of two chrecs. */
401 :
402 : tree
403 4015647 : chrec_fold_minus (tree type,
404 : tree op0,
405 : tree op1)
406 : {
407 7440235 : if (automatically_generated_chrec_p (op0)
408 4015647 : || automatically_generated_chrec_p (op1))
409 723357 : return chrec_fold_automatically_generated_operands (op0, op1);
410 :
411 3292290 : if (integer_zerop (op1))
412 : return op0;
413 :
414 3195257 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
415 : }
416 :
417 : /* Fold the multiplication of two chrecs. */
418 :
419 : tree
420 21180277 : chrec_fold_multiply (tree type,
421 : tree op0,
422 : tree op1)
423 : {
424 21180701 : if (automatically_generated_chrec_p (op0)
425 19774886 : || automatically_generated_chrec_p (op1))
426 1561151 : return chrec_fold_automatically_generated_operands (op0, op1);
427 :
428 19619550 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
429 15685948 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
430 : std::swap (op0, op1);
431 :
432 19619550 : switch (TREE_CODE (op0))
433 : {
434 4124788 : case POLYNOMIAL_CHREC:
435 4124788 : gcc_checking_assert
436 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
437 4124788 : switch (TREE_CODE (op1))
438 : {
439 40247 : case POLYNOMIAL_CHREC:
440 40247 : gcc_checking_assert
441 : (!chrec_contains_symbols_defined_in_loop (op1,
442 : CHREC_VARIABLE (op1)));
443 40247 : return chrec_fold_multiply_poly_poly (type, op0, op1);
444 :
445 57923 : CASE_CONVERT:
446 57923 : if (tree_contains_chrecs (op1, NULL))
447 : {
448 : /* We can strip sign-conversions to signed by performing the
449 : operation in unsigned. */
450 218 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
451 218 : if (INTEGRAL_TYPE_P (type)
452 218 : && INTEGRAL_TYPE_P (optype)
453 218 : && tree_nop_conversion_p (type, optype)
454 233 : && TYPE_UNSIGNED (optype))
455 : {
456 15 : tree tem = chrec_convert (optype, op0, NULL);
457 15 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
458 15 : return chrec_convert (type,
459 : chrec_fold_multiply (optype, tem,
460 15 : TREE_OPERAND
461 : (op1, 0)),
462 15 : NULL);
463 : }
464 203 : return chrec_dont_know;
465 : }
466 : /* FALLTHRU */
467 :
468 4084323 : default:
469 4084323 : if (integer_onep (op1))
470 : return op0;
471 4083872 : 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 4083462 : if (INTEGRAL_TYPE_P (type)
481 4083269 : && TYPE_OVERFLOW_UNDEFINED (type)
482 1048402 : && !integer_zerop (CHREC_LEFT (op0))
483 597956 : && TREE_CODE (op1) == INTEGER_CST
484 4510470 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
485 : {
486 336525 : wi::overflow_type ovf = wi::OVF_NONE;
487 336525 : wide_int res
488 336525 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
489 673050 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
490 336525 : 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 336525 : }
503 4083426 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
504 4083426 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
505 4083426 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
506 : }
507 :
508 4665879 : CASE_CONVERT:
509 4665879 : if (tree_contains_chrecs (op0, NULL))
510 : {
511 : /* We can strip sign-conversions to signed by performing the
512 : operation in unsigned. */
513 54535 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
514 54535 : if (INTEGRAL_TYPE_P (type)
515 54535 : && INTEGRAL_TYPE_P (optype)
516 54535 : && tree_nop_conversion_p (type, optype)
517 65972 : && TYPE_UNSIGNED (optype))
518 22824 : return chrec_convert (type,
519 : chrec_fold_multiply (optype,
520 11412 : TREE_OPERAND (op0, 0),
521 : chrec_convert (optype,
522 : op1,
523 : NULL)),
524 11412 : NULL);
525 43123 : return chrec_dont_know;
526 : }
527 : /* FALLTHRU */
528 :
529 15440227 : default:
530 15440227 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
531 15440227 : if (integer_onep (op0))
532 : return op1;
533 :
534 10477180 : if (integer_zerop (op0))
535 2292580 : return build_int_cst (type, 0);
536 :
537 8184600 : switch (TREE_CODE (op1))
538 : {
539 0 : case POLYNOMIAL_CHREC:
540 0 : gcc_unreachable ();
541 :
542 827848 : CASE_CONVERT:
543 827848 : if (tree_contains_chrecs (op1, NULL))
544 : return chrec_fold_multiply (type, op1, op0);
545 : /* FALLTHRU */
546 :
547 8184176 : default:
548 8184176 : if (integer_onep (op1))
549 : return op0;
550 8119243 : if (integer_zerop (op1))
551 1606 : return build_int_cst (type, 0);
552 8117637 : 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 11757 : tree_fold_binomial (tree type, tree n, unsigned int k)
566 : {
567 11757 : wi::overflow_type overflow;
568 11757 : unsigned int i;
569 :
570 : /* Handle the most frequent cases. */
571 11757 : if (k == 0)
572 3894 : return build_int_cst (type, 1);
573 7863 : if (k == 1)
574 3894 : return fold_convert (type, n);
575 :
576 3969 : widest_int num = wi::to_widest (n);
577 :
578 : /* Check that k <= n. */
579 3969 : if (wi::ltu_p (num, k))
580 : return NULL_TREE;
581 :
582 : /* Denominator = 2. */
583 3910 : widest_int denom = 2;
584 :
585 : /* Index = Numerator-1. */
586 3910 : widest_int idx = num - 1;
587 :
588 : /* Numerator = Numerator*Index = n*(n-1). */
589 3910 : num = wi::smul (num, idx, &overflow);
590 3910 : if (overflow)
591 : return NULL_TREE;
592 :
593 3916 : 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 3910 : num = wi::udiv_trunc (num, denom);
609 3910 : if (! wi::fits_to_tree_p (num, type))
610 : return NULL_TREE;
611 3900 : return wide_int_to_tree (type, num);
612 7879 : }
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 11904 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
620 : {
621 11904 : tree arg0, arg1, binomial_n_k;
622 11904 : tree type = TREE_TYPE (chrec);
623 11904 : class loop *var_loop = get_loop (cfun, var);
624 :
625 11904 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
626 11904 : && 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 11904 : tree ctype = type;
632 11904 : if (INTEGRAL_TYPE_P (type)
633 11904 : && ! TYPE_OVERFLOW_WRAPS (type))
634 11586 : ctype = unsigned_type_for (type);
635 :
636 11904 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
637 11904 : && CHREC_VARIABLE (chrec) == var)
638 : {
639 7941 : arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
640 7941 : if (arg1 == chrec_dont_know)
641 : return chrec_dont_know;
642 7794 : binomial_n_k = tree_fold_binomial (ctype, n, k);
643 7794 : if (!binomial_n_k)
644 0 : return chrec_dont_know;
645 7794 : tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
646 7794 : arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
647 7794 : return chrec_fold_plus (ctype, arg0, arg1);
648 : }
649 :
650 3963 : binomial_n_k = tree_fold_binomial (ctype, n, k);
651 3963 : if (!binomial_n_k)
652 69 : return chrec_dont_know;
653 :
654 3894 : 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 896238 : chrec_apply (unsigned var,
671 : tree chrec,
672 : tree x)
673 : {
674 896238 : tree type = chrec_type (chrec);
675 896238 : tree res = chrec_dont_know;
676 :
677 1792476 : if (automatically_generated_chrec_p (chrec)
678 1001751 : || 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 896238 : || chrec_contains_symbols_defined_in_loop (chrec, var))
684 105513 : return chrec_dont_know;
685 :
686 790725 : if (dump_file && (dump_flags & TDF_SCEV))
687 0 : fprintf (dump_file, "(chrec_apply \n");
688 :
689 790725 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
690 124 : x = build_real_from_int_cst (type, x);
691 :
692 790725 : switch (TREE_CODE (chrec))
693 : {
694 789322 : case POLYNOMIAL_CHREC:
695 789322 : if (evolution_function_is_affine_p (chrec))
696 : {
697 784078 : tree chrecr = CHREC_RIGHT (chrec);
698 784078 : tree chrecl = CHREC_LEFT (chrec);
699 784078 : 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 783552 : else if (operand_equal_p (chrecl, chrecr)
706 135357 : && TREE_CODE (x) == PLUS_EXPR
707 6342 : && integer_all_onesp (TREE_OPERAND (x, 1))
708 6082 : && !POINTER_TYPE_P (type)
709 789623 : && TYPE_PRECISION (TREE_TYPE (x))
710 6071 : >= TYPE_PRECISION (type))
711 : {
712 : /* We know the number of iterations can't be negative. */
713 4219 : res = build_int_cst (TREE_TYPE (x), 1);
714 4219 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
715 4219 : res = chrec_convert_rhs (type, res, NULL);
716 4219 : 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 779333 : tree utype = TREE_TYPE (chrecr);
725 779333 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
726 686198 : utype = unsigned_type_for (TREE_TYPE (chrecr));
727 779333 : res = chrec_convert_rhs (utype, x, NULL);
728 779333 : 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 779333 : if (TREE_CODE (res) == INTEGER_CST
734 779333 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
735 : {
736 401428 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
737 401428 : res = chrec_fold_plus (type, chrecl, res);
738 : }
739 : else
740 : {
741 377905 : res = chrec_fold_plus (utype,
742 : chrec_convert (utype, chrecl, NULL),
743 : res);
744 377905 : res = chrec_convert (type, res, NULL);
745 : }
746 : }
747 : }
748 5244 : else if (TREE_CODE (x) == INTEGER_CST
749 5244 : && tree_int_cst_sgn (x) == 1)
750 : /* testsuite/.../ssa-chrec-38.c. */
751 3963 : 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 790725 : 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 2281117 : chrec_replace_initial_condition (tree chrec,
803 : tree init_cond)
804 : {
805 2281117 : if (automatically_generated_chrec_p (chrec))
806 : return chrec;
807 :
808 2281117 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
809 :
810 2281117 : switch (TREE_CODE (chrec))
811 : {
812 1150817 : case POLYNOMIAL_CHREC:
813 1150817 : return build_polynomial_chrec
814 1150817 : (CHREC_VARIABLE (chrec),
815 1150817 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
816 2301634 : 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 11170915 : initial_condition (tree chrec)
827 : {
828 18320312 : if (automatically_generated_chrec_p (chrec))
829 : return chrec;
830 :
831 17080182 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
832 7149397 : 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 47898362 : hide_evolution_in_other_loops_than_loop (tree chrec,
842 : unsigned loop_num)
843 : {
844 47900991 : class loop *loop = get_loop (cfun, loop_num), *chloop;
845 47900991 : if (automatically_generated_chrec_p (chrec))
846 : return chrec;
847 :
848 47900991 : switch (TREE_CODE (chrec))
849 : {
850 2479263 : case POLYNOMIAL_CHREC:
851 2479263 : chloop = get_chrec_loop (chrec);
852 :
853 2479263 : if (chloop == loop)
854 2006658 : return build_polynomial_chrec
855 2006658 : (loop_num,
856 2006658 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
857 : loop_num),
858 4013316 : CHREC_RIGHT (chrec));
859 :
860 472605 : else if (flow_loop_nested_p (chloop, loop))
861 : /* There is no evolution in this loop. */
862 469976 : return initial_condition (chrec);
863 :
864 2629 : else if (flow_loop_nested_p (loop, chloop))
865 2629 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
866 2629 : 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 42091987 : chrec_component_in_loop_num (tree chrec,
881 : unsigned loop_num,
882 : bool right)
883 : {
884 42091987 : tree component;
885 42091987 : class loop *loop = get_loop (cfun, loop_num), *chloop;
886 :
887 42091987 : if (automatically_generated_chrec_p (chrec))
888 : return chrec;
889 :
890 40851857 : switch (TREE_CODE (chrec))
891 : {
892 35174609 : case POLYNOMIAL_CHREC:
893 35174609 : chloop = get_chrec_loop (chrec);
894 :
895 35174609 : if (chloop == loop)
896 : {
897 33842918 : if (right)
898 17216981 : component = CHREC_RIGHT (chrec);
899 : else
900 16625937 : component = CHREC_LEFT (chrec);
901 :
902 33842918 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
903 33842918 : || 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 1331691 : 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 1331691 : gcc_assert (flow_loop_nested_p (loop, chloop));
922 1331691 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
923 : loop_num,
924 1331691 : right);
925 : }
926 :
927 5677248 : default:
928 5677248 : 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 23285612 : evolution_part_in_loop_num (tree chrec,
941 : unsigned loop_num)
942 : {
943 23285612 : 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 17474684 : initial_condition_in_loop_num (tree chrec,
952 : unsigned loop_num)
953 : {
954 17474684 : 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 16300553 : chrec_merge (tree chrec1,
996 : tree chrec2)
997 : {
998 16300553 : if (chrec1 == chrec_dont_know
999 16300553 : || chrec2 == chrec_dont_know)
1000 : return chrec_dont_know;
1001 :
1002 13661102 : if (chrec1 == chrec_known
1003 13661102 : || chrec2 == chrec_known)
1004 : return chrec_known;
1005 :
1006 13661102 : if (chrec1 == chrec_not_analyzed_yet)
1007 : return chrec2;
1008 2836077 : if (chrec2 == chrec_not_analyzed_yet)
1009 : return chrec1;
1010 :
1011 2836077 : if (eq_evolutions_p (chrec1, chrec2))
1012 : return chrec1;
1013 :
1014 2290766 : 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 37232455 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1063 : class loop *loop)
1064 : {
1065 37232455 : int i, n;
1066 :
1067 37232455 : if (chrec == NULL_TREE)
1068 : return false;
1069 :
1070 37232455 : 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 31581855 : if (loop != NULL
1081 600 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1082 31582057 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1083 : return true;
1084 :
1085 31581855 : if (visited.add (chrec))
1086 : return false;
1087 :
1088 30954670 : n = TREE_OPERAND_LENGTH (chrec);
1089 79702385 : for (i = 0; i < n; i++)
1090 21716142 : 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 15516313 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1102 : {
1103 15516313 : hash_set<const_tree> visited;
1104 15516313 : return chrec_contains_symbols (chrec, visited, loop);
1105 15516313 : }
1106 :
1107 : /* Return true when CHREC contains symbolic names defined in
1108 : LOOP_NB. */
1109 :
1110 : static bool
1111 335213077 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1112 : hash_set<const_tree> &visited)
1113 : {
1114 335213077 : int i, n;
1115 :
1116 335213077 : if (chrec == NULL_TREE)
1117 : return false;
1118 :
1119 335076335 : if (is_gimple_min_invariant (chrec))
1120 : return false;
1121 :
1122 197990988 : if (TREE_CODE (chrec) == SSA_NAME)
1123 : {
1124 71741282 : gimple *def;
1125 71741282 : loop_p def_loop, loop;
1126 :
1127 71741282 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1128 : return false;
1129 :
1130 67392382 : def = SSA_NAME_DEF_STMT (chrec);
1131 67392382 : def_loop = loop_containing_stmt (def);
1132 67392382 : loop = get_loop (cfun, loop_nb);
1133 :
1134 67392382 : if (def_loop == NULL)
1135 : return false;
1136 :
1137 67392382 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1138 4399118 : return true;
1139 :
1140 : return false;
1141 : }
1142 :
1143 126249706 : if (visited.add (chrec))
1144 : return false;
1145 :
1146 126210489 : n = TREE_OPERAND_LENGTH (chrec);
1147 462042908 : for (i = 0; i < n; i++)
1148 210940143 : 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 124272934 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1159 : {
1160 124272934 : hash_set<const_tree> visited;
1161 124272934 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1162 124272934 : }
1163 :
1164 : /* Determines whether the chrec contains undetermined coefficients. */
1165 :
1166 : static bool
1167 224466238 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1168 : {
1169 224466238 : int i, n;
1170 :
1171 224466238 : if (chrec == chrec_dont_know)
1172 : return true;
1173 :
1174 201578252 : if (chrec == NULL_TREE)
1175 : return false;
1176 :
1177 201216926 : if (visited.add (chrec))
1178 : return false;
1179 :
1180 188187129 : n = TREE_OPERAND_LENGTH (chrec);
1181 499865829 : for (i = 0; i < n; i++)
1182 123492746 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1183 : return true;
1184 : return false;
1185 : }
1186 :
1187 : bool
1188 100973492 : chrec_contains_undetermined (const_tree chrec)
1189 : {
1190 100973492 : hash_set<const_tree> visited;
1191 100973492 : return chrec_contains_undetermined (chrec, visited);
1192 100973492 : }
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 432188752 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1200 : {
1201 432188752 : int i, n;
1202 :
1203 432188752 : if (expr == NULL_TREE)
1204 : return false;
1205 :
1206 431099303 : if (size)
1207 76235490 : (*size)++;
1208 :
1209 431495422 : if (tree_is_chrec (expr))
1210 : return true;
1211 :
1212 408424523 : if (visited.add (expr))
1213 : return false;
1214 :
1215 405983509 : n = TREE_OPERAND_LENGTH (expr);
1216 1019873919 : for (i = 0; i < n; i++)
1217 208225237 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1218 : return true;
1219 : return false;
1220 : }
1221 :
1222 : bool
1223 223963515 : tree_contains_chrecs (const_tree expr, int *size)
1224 : {
1225 223963515 : hash_set<const_tree> visited;
1226 223963515 : return tree_contains_chrecs (expr, size, visited);
1227 223963515 : }
1228 :
1229 :
1230 : /* Recursive helper function. */
1231 :
1232 : static bool
1233 45941453 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1234 : {
1235 91882906 : if (evolution_function_is_constant_p (chrec))
1236 : return true;
1237 :
1238 9967441 : if (TREE_CODE (chrec) == SSA_NAME
1239 9967441 : && (loopnum == 0
1240 2224205 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1241 2201089 : return true;
1242 :
1243 7766352 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1244 : {
1245 6108040 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1246 132481 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1247 132481 : get_chrec_loop (chrec))
1248 3246 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1249 : loopnum)
1250 6111286 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1251 : loopnum))
1252 6104794 : return false;
1253 : return true;
1254 : }
1255 :
1256 1658312 : switch (TREE_OPERAND_LENGTH (chrec))
1257 : {
1258 983255 : case 2:
1259 983255 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1260 : loopnum))
1261 : return false;
1262 : /* FALLTHRU */
1263 :
1264 1591629 : case 1:
1265 1591629 : 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 30917631 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1279 : {
1280 30917631 : 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 6768643 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1288 : {
1289 6768643 : if (chrec == NULL_TREE)
1290 : return false;
1291 :
1292 6768643 : switch (TREE_CODE (chrec))
1293 : {
1294 6221223 : case POLYNOMIAL_CHREC:
1295 6221223 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1296 : {
1297 6120089 : 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 101134 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1314 101134 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1315 101093 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1316 202227 : && evolution_function_is_affine_multivariate_p
1317 101093 : (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 3465147 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1334 : {
1335 3465147 : if (chrec == NULL_TREE)
1336 : return true;
1337 :
1338 3465147 : tree sub_chrec;
1339 3465147 : switch (TREE_CODE (chrec))
1340 : {
1341 3465144 : case POLYNOMIAL_CHREC:
1342 3465144 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1343 : {
1344 31441 : case POLYNOMIAL_CHREC:
1345 31441 : sub_chrec = CHREC_LEFT (chrec);
1346 31441 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1347 31441 : && (loopnum <= 0
1348 5077 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1349 18 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1350 18 : get_chrec_loop (sub_chrec))))
1351 31429 : return false;
1352 12 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1353 : return false;
1354 : break;
1355 :
1356 3433703 : default:
1357 3433703 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1358 : return false;
1359 : break;
1360 : }
1361 :
1362 3433715 : 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 3433715 : default:
1377 3433715 : 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 3374628 : nb_vars_in_chrec (tree chrec)
1393 : {
1394 6749256 : if (chrec == NULL_TREE)
1395 : return 0;
1396 :
1397 6749256 : switch (TREE_CODE (chrec))
1398 : {
1399 3374628 : case POLYNOMIAL_CHREC:
1400 3374628 : return 1 + nb_vars_in_chrec
1401 3374628 : (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 7436342 : 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 7436342 : tree ct = TREE_TYPE (*step);
1423 7436342 : bool enforce_overflow_semantics;
1424 7436342 : bool must_check_src_overflow, must_check_rslt_overflow;
1425 7436342 : tree new_base, new_step;
1426 7436342 : 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 7436342 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1444 :
1445 16927888 : enforce_overflow_semantics = (use_overflow_semantics
1446 7436342 : && nowrap_type_p (type));
1447 2432444 : 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 2432444 : if (must_check_src_overflow)
1460 : {
1461 440461 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1462 : must_check_rslt_overflow = true;
1463 : else
1464 : must_check_rslt_overflow = false;
1465 : }
1466 1991983 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1467 1991983 : && 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 7059102 : if (must_check_src_overflow
1479 7436342 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1480 : use_overflow_semantics))
1481 : return false;
1482 :
1483 6617594 : 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 6617594 : new_step = *step;
1491 6617594 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1492 : {
1493 125348 : tree signed_ct = signed_type_for (ct);
1494 125348 : new_step = chrec_convert (signed_ct, new_step, at_stmt,
1495 : use_overflow_semantics);
1496 : }
1497 6617594 : new_step = chrec_convert (step_type, new_step, at_stmt,
1498 : use_overflow_semantics);
1499 :
1500 13235188 : if (automatically_generated_chrec_p (new_base)
1501 2067486 : || automatically_generated_chrec_p (new_step))
1502 : return false;
1503 :
1504 6617336 : 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 6617336 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1508 : at_stmt, loop, false))
1509 : return false;
1510 :
1511 5368856 : *base = new_base;
1512 5368856 : *step = new_step;
1513 5368856 : 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 31150143 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1522 : {
1523 31150143 : if (POINTER_TYPE_P (type))
1524 5954208 : type = sizetype;
1525 :
1526 31150143 : 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 155650708 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1545 : bool use_overflow_semantics, tree from)
1546 : {
1547 155650708 : tree ct, res;
1548 155650708 : tree base, step;
1549 155650708 : class loop *loop;
1550 :
1551 269235676 : if (automatically_generated_chrec_p (chrec))
1552 : return chrec;
1553 :
1554 154373340 : ct = chrec_type (chrec);
1555 154373340 : if (useless_type_conversion_p (type, ct))
1556 : return chrec;
1557 :
1558 40788372 : if (!evolution_function_is_affine_p (chrec))
1559 34723159 : goto keep_cast;
1560 :
1561 6065213 : loop = get_chrec_loop (chrec);
1562 6065213 : base = CHREC_LEFT (chrec);
1563 6065213 : step = CHREC_RIGHT (chrec);
1564 :
1565 6065213 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1566 : use_overflow_semantics, from))
1567 4495883 : return build_polynomial_chrec (loop->num, base, step);
1568 :
1569 : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1570 1569330 : 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 36292489 : if (use_overflow_semantics
1575 35646968 : && (TREE_CODE (chrec) == PLUS_EXPR
1576 35646968 : || TREE_CODE (chrec) == MINUS_EXPR)
1577 3479085 : && TREE_CODE (type) == INTEGER_TYPE
1578 3434473 : && TREE_CODE (ct) == INTEGER_TYPE
1579 3434427 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1580 36457841 : && TYPE_OVERFLOW_UNDEFINED (ct))
1581 60196 : 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 36232293 : else if (use_overflow_semantics
1587 35586772 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1588 1599750 : && TREE_CODE (ct) == INTEGER_TYPE
1589 1586916 : && TREE_CODE (type) == INTEGER_TYPE
1590 1448277 : && TYPE_OVERFLOW_UNDEFINED (type)
1591 37393880 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1592 : {
1593 28711 : tree utype = unsigned_type_for (type);
1594 86133 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1595 28711 : fold_convert (utype,
1596 : CHREC_LEFT (chrec)),
1597 28711 : fold_convert (utype,
1598 : CHREC_RIGHT (chrec)));
1599 28711 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1600 : }
1601 : else
1602 36203582 : res = fold_convert (type, chrec);
1603 :
1604 : /* Don't propagate overflows. */
1605 36292489 : if (CONSTANT_CLASS_P (res))
1606 11872324 : TREE_OVERFLOW (res) = 0;
1607 :
1608 : /* But reject constants that don't fit in their type after conversion.
1609 : This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1610 : natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1611 : and can cause problems later when computing niters of loops. Note
1612 : that we don't do the check before converting because we don't want
1613 : to reject conversions of negative chrecs to unsigned types. */
1614 36292489 : if (TREE_CODE (res) == INTEGER_CST
1615 11872323 : && TREE_CODE (type) == INTEGER_TYPE
1616 11829305 : && !int_fits_type_p (res, type))
1617 365 : res = chrec_dont_know;
1618 :
1619 : return res;
1620 : }
1621 :
1622 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1623 : which the CHREC is built, it sets AT_STMT to the statement that
1624 : contains the definition of the analyzed variable, otherwise the
1625 : conversion is less accurate: the information is used for
1626 : determining a more accurate estimation of the number of iterations.
1627 : By default AT_STMT could be safely set to NULL_TREE.
1628 :
1629 : The following rule is always true: TREE_TYPE (chrec) ==
1630 : TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1631 : An example of what could happen when adding two chrecs and the type
1632 : of the CHREC_RIGHT is different than CHREC_LEFT is:
1633 :
1634 : {(uint) 0, +, (uchar) 10} +
1635 : {(uint) 0, +, (uchar) 250}
1636 :
1637 : that would produce a wrong result if CHREC_RIGHT is not (uint):
1638 :
1639 : {(uint) 0, +, (uchar) 4}
1640 :
1641 : instead of
1642 :
1643 : {(uint) 0, +, (uint) 260}
1644 :
1645 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1646 : the rules for overflow of the given language apply (e.g., that signed
1647 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1648 : unnecessary tests, but also to enforce that the result follows them.
1649 :
1650 : FROM is the source variable converted if it's not NULL. */
1651 :
1652 : tree
1653 155621997 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1654 : bool use_overflow_semantics, tree from)
1655 : {
1656 155621997 : return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1657 : }
1658 :
1659 : /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1660 : chrec if something else than what chrec_convert would do happens, NULL_TREE
1661 : otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1662 : if the result chrec may overflow. */
1663 :
1664 : tree
1665 8476327 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1666 : {
1667 8476327 : tree inner_type, left, right, lc, rc, rtype;
1668 :
1669 8476327 : gcc_assert (fold_conversions != NULL);
1670 :
1671 16454887 : if (automatically_generated_chrec_p (chrec)
1672 8476327 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1673 : return NULL_TREE;
1674 :
1675 653469 : inner_type = TREE_TYPE (chrec);
1676 653469 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1677 : return NULL_TREE;
1678 :
1679 567352 : if (useless_type_conversion_p (type, inner_type))
1680 : return NULL_TREE;
1681 :
1682 497767 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1683 : {
1684 496957 : tree base, step;
1685 496957 : class loop *loop;
1686 :
1687 496957 : loop = get_chrec_loop (chrec);
1688 496957 : base = CHREC_LEFT (chrec);
1689 496957 : step = CHREC_RIGHT (chrec);
1690 496957 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1691 2118 : return build_polynomial_chrec (loop->num, base, step);
1692 : }
1693 495649 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1694 :
1695 495649 : left = CHREC_LEFT (chrec);
1696 495649 : right = CHREC_RIGHT (chrec);
1697 495649 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1698 495649 : if (!lc)
1699 495649 : lc = chrec_convert (type, left, NULL);
1700 495649 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1701 495649 : if (!rc)
1702 494965 : rc = chrec_convert (rtype, right, NULL);
1703 :
1704 495649 : *fold_conversions = true;
1705 :
1706 495649 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1707 : }
1708 :
1709 : /* Returns true when CHREC0 == CHREC1. */
1710 :
1711 : bool
1712 13393484 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1713 : {
1714 13425878 : if (chrec0 == NULL_TREE
1715 13425878 : || chrec1 == NULL_TREE
1716 13425878 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1717 : return false;
1718 :
1719 12526567 : if (operand_equal_p (chrec0, chrec1, 0))
1720 : return true;
1721 :
1722 9368959 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1723 : return false;
1724 :
1725 9367867 : switch (TREE_CODE (chrec0))
1726 : {
1727 3888434 : case POLYNOMIAL_CHREC:
1728 3888434 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1729 3888097 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1730 4222484 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1731 :
1732 56484 : case PLUS_EXPR:
1733 56484 : case MULT_EXPR:
1734 56484 : case MINUS_EXPR:
1735 56484 : case POINTER_PLUS_EXPR:
1736 56484 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1737 56484 : TREE_OPERAND (chrec1, 0))
1738 98630 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1739 42146 : TREE_OPERAND (chrec1, 1));
1740 :
1741 32394 : CASE_CONVERT:
1742 32394 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1743 64788 : TREE_OPERAND (chrec1, 0));
1744 :
1745 : default:
1746 : return false;
1747 : }
1748 : }
1749 :
1750 : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1751 : EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1752 : which of these cases happens. */
1753 :
1754 : enum ev_direction
1755 3571424 : scev_direction (const_tree chrec)
1756 : {
1757 3571424 : const_tree step;
1758 :
1759 3571424 : if (!evolution_function_is_affine_p (chrec))
1760 : return EV_DIR_UNKNOWN;
1761 :
1762 3562654 : step = CHREC_RIGHT (chrec);
1763 3562654 : if (TREE_CODE (step) != INTEGER_CST)
1764 : return EV_DIR_UNKNOWN;
1765 :
1766 3356681 : if (tree_int_cst_sign_bit (step))
1767 : return EV_DIR_DECREASES;
1768 : else
1769 3021330 : return EV_DIR_GROWS;
1770 : }
1771 :
1772 : /* Iterates over all the components of SCEV, and calls CBCK. */
1773 :
1774 : void
1775 0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1776 : {
1777 0 : switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1778 : {
1779 0 : case 3:
1780 0 : for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1781 : /* FALLTHRU */
1782 :
1783 0 : case 2:
1784 0 : for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1785 : /* FALLTHRU */
1786 :
1787 0 : case 1:
1788 0 : for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1789 : /* FALLTHRU */
1790 :
1791 0 : default:
1792 0 : cbck (scev, data);
1793 0 : break;
1794 : }
1795 0 : }
1796 :
1797 : /* Returns true when the operation can be part of a linear
1798 : expression. */
1799 :
1800 : static inline bool
1801 34009 : operator_is_linear (tree scev)
1802 : {
1803 34009 : switch (TREE_CODE (scev))
1804 : {
1805 : case INTEGER_CST:
1806 : case POLYNOMIAL_CHREC:
1807 : case PLUS_EXPR:
1808 : case POINTER_PLUS_EXPR:
1809 : case MULT_EXPR:
1810 : case MINUS_EXPR:
1811 : case NEGATE_EXPR:
1812 : case SSA_NAME:
1813 : case NON_LVALUE_EXPR:
1814 : case BIT_NOT_EXPR:
1815 : CASE_CONVERT:
1816 : return true;
1817 :
1818 10 : default:
1819 10 : return false;
1820 : }
1821 : }
1822 :
1823 : /* Return true when SCEV is a linear expression. Linear expressions
1824 : can contain additions, substractions and multiplications.
1825 : Multiplications are restricted to constant scaling: "cst * x". */
1826 :
1827 : bool
1828 77835 : scev_is_linear_expression (tree scev)
1829 : {
1830 160222 : if (evolution_function_is_constant_p (scev))
1831 : return true;
1832 :
1833 34009 : if (scev == NULL
1834 34009 : || !operator_is_linear (scev))
1835 : return false;
1836 :
1837 33999 : if (TREE_CODE (scev) == MULT_EXPR)
1838 601 : return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1839 0 : && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1840 :
1841 33398 : if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1842 33398 : && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1843 : return false;
1844 :
1845 33198 : switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1846 : {
1847 0 : case 3:
1848 0 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1849 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1850 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1851 :
1852 24446 : case 2:
1853 24446 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1854 24446 : && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1855 :
1856 2276 : case 1:
1857 2276 : return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1858 :
1859 : case 0:
1860 : return true;
1861 :
1862 : default:
1863 : return false;
1864 : }
1865 : }
1866 :
1867 : /* Determines whether the expression CHREC contains only interger consts
1868 : in the right parts. */
1869 :
1870 : bool
1871 4316 : evolution_function_right_is_integer_cst (const_tree chrec)
1872 : {
1873 4316 : if (chrec == NULL_TREE)
1874 : return false;
1875 :
1876 4316 : switch (TREE_CODE (chrec))
1877 : {
1878 : case INTEGER_CST:
1879 : return true;
1880 :
1881 4316 : case POLYNOMIAL_CHREC:
1882 4316 : return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1883 4316 : && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1884 470 : || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1885 :
1886 0 : CASE_CONVERT:
1887 0 : return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1888 :
1889 : default:
1890 : return false;
1891 : }
1892 : }
|
