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 88370 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : tree type,
50 : tree poly0,
51 : tree poly1)
52 : {
53 88370 : tree left, right;
54 88370 : class loop *loop0 = get_chrec_loop (poly0);
55 88370 : class loop *loop1 = get_chrec_loop (poly1);
56 88370 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
57 :
58 88370 : gcc_assert (poly0);
59 88370 : gcc_assert (poly1);
60 88370 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
61 88370 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
62 88370 : 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 87505 : 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 88370 : 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 88074 : 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 87472 : 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 87440 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
114 : {
115 32770 : left = chrec_fold_plus
116 32770 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 32770 : right = chrec_fold_plus
118 32770 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : }
120 : else
121 : {
122 54670 : left = chrec_fold_minus
123 54670 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 54670 : right = chrec_fold_minus
125 54670 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : }
127 :
128 87440 : if (chrec_zerop (right))
129 : return left;
130 : else
131 33018 : return build_polynomial_chrec
132 33018 : (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 5844018 : chrec_fold_automatically_generated_operands (tree op0,
210 : tree op1)
211 : {
212 5844018 : if (op0 == chrec_dont_know
213 941565 : || 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 30523225 : chrec_fold_plus_1 (enum tree_code code, tree type,
232 : tree op0, tree op1)
233 : {
234 61046450 : if (automatically_generated_chrec_p (op0)
235 30523225 : || automatically_generated_chrec_p (op1))
236 0 : return chrec_fold_automatically_generated_operands (op0, op1);
237 :
238 30523225 : switch (TREE_CODE (op0))
239 : {
240 9720902 : case POLYNOMIAL_CHREC:
241 9720902 : gcc_checking_assert
242 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
243 9720902 : switch (TREE_CODE (op1))
244 : {
245 88370 : case POLYNOMIAL_CHREC:
246 88370 : gcc_checking_assert
247 : (!chrec_contains_symbols_defined_in_loop (op1,
248 : CHREC_VARIABLE (op1)));
249 88370 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
250 :
251 161520 : CASE_CONVERT:
252 161520 : if (tree_contains_chrecs (op1, NULL))
253 : {
254 : /* We can strip sign-conversions to signed by performing the
255 : operation in unsigned. */
256 686 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
257 686 : if (INTEGRAL_TYPE_P (type)
258 686 : && INTEGRAL_TYPE_P (optype)
259 661 : && tree_nop_conversion_p (type, optype)
260 878 : && 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 670 : return chrec_dont_know;
272 : }
273 : /* FALLTHRU */
274 :
275 9631846 : default:
276 9631846 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
277 8853683 : return build_polynomial_chrec
278 8853683 : (CHREC_VARIABLE (op0),
279 8853683 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
280 17707366 : CHREC_RIGHT (op0));
281 : else
282 778163 : return build_polynomial_chrec
283 778163 : (CHREC_VARIABLE (op0),
284 778163 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
285 1556326 : CHREC_RIGHT (op0));
286 : }
287 :
288 2894630 : CASE_CONVERT:
289 2894630 : if (tree_contains_chrecs (op0, NULL))
290 : {
291 : /* We can strip sign-conversions to signed by performing the
292 : operation in unsigned. */
293 41521 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
294 41521 : if (INTEGRAL_TYPE_P (type)
295 40121 : && INTEGRAL_TYPE_P (optype)
296 36110 : && tree_nop_conversion_p (type, optype)
297 67874 : && TYPE_UNSIGNED (optype))
298 52638 : return chrec_convert (type,
299 : chrec_fold_plus_1 (code, optype,
300 26319 : TREE_OPERAND (op0, 0),
301 : chrec_convert (optype,
302 : op1, NULL)),
303 26319 : NULL);
304 15202 : return chrec_dont_know;
305 : }
306 : /* FALLTHRU */
307 :
308 20760802 : default:
309 20760802 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
310 20760802 : switch (TREE_CODE (op1))
311 : {
312 3092156 : case POLYNOMIAL_CHREC:
313 3092156 : gcc_checking_assert
314 : (!chrec_contains_symbols_defined_in_loop (op1,
315 : CHREC_VARIABLE (op1)));
316 3092156 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
317 3025487 : return build_polynomial_chrec
318 3025487 : (CHREC_VARIABLE (op1),
319 3025487 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
320 6050974 : CHREC_RIGHT (op1));
321 : else
322 66669 : return build_polynomial_chrec
323 133338 : (CHREC_VARIABLE (op1),
324 66669 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
325 66669 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
326 66669 : SCALAR_FLOAT_TYPE_P (type)
327 4 : ? build_real (type, dconstm1)
328 133334 : : build_int_cst_type (type, -1)));
329 :
330 2159744 : CASE_CONVERT:
331 2159744 : if (tree_contains_chrecs (op1, NULL))
332 : {
333 : /* We can strip sign-conversions to signed by performing the
334 : operation in unsigned. */
335 85567 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
336 85567 : if (INTEGRAL_TYPE_P (type)
337 22157 : && INTEGRAL_TYPE_P (optype)
338 22157 : && tree_nop_conversion_p (type, optype)
339 103595 : && 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 67539 : return chrec_dont_know;
348 : }
349 : /* FALLTHRU */
350 :
351 17583079 : default:
352 17583079 : {
353 17583079 : int size = 0;
354 17583079 : if ((tree_contains_chrecs (op0, &size)
355 17583079 : || tree_contains_chrecs (op1, &size))
356 17583079 : && size < param_scev_max_expr_size)
357 0 : return build2 (code, type, op0, op1);
358 17583079 : else if (size < param_scev_max_expr_size)
359 : {
360 17582979 : if (code == POINTER_PLUS_EXPR)
361 3496029 : return fold_build_pointer_plus (fold_convert (type, op0),
362 : op1);
363 : else
364 14086950 : 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 36757608 : chrec_fold_plus (tree type,
379 : tree op0,
380 : tree op1)
381 : {
382 36757608 : enum tree_code code;
383 70599278 : if (automatically_generated_chrec_p (op0)
384 36757608 : || automatically_generated_chrec_p (op1))
385 3570809 : return chrec_fold_automatically_generated_operands (op0, op1);
386 :
387 33186799 : if (integer_zerop (op0))
388 4062103 : return chrec_convert (type, op1, NULL);
389 29124696 : if (integer_zerop (op1))
390 1849690 : return chrec_convert (type, op0, NULL);
391 :
392 27275006 : if (POINTER_TYPE_P (type))
393 : code = POINTER_PLUS_EXPR;
394 : else
395 20841014 : code = PLUS_EXPR;
396 :
397 27275006 : return chrec_fold_plus_1 (code, type, op0, op1);
398 : }
399 :
400 : /* Fold the subtraction of two chrecs. */
401 :
402 : tree
403 4008682 : chrec_fold_minus (tree type,
404 : tree op0,
405 : tree op1)
406 : {
407 7440503 : if (automatically_generated_chrec_p (op0)
408 4008682 : || automatically_generated_chrec_p (op1))
409 707913 : return chrec_fold_automatically_generated_operands (op0, op1);
410 :
411 3300769 : if (integer_zerop (op1))
412 : return op0;
413 :
414 3203856 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
415 : }
416 :
417 : /* Fold the multiplication of two chrecs. */
418 :
419 : tree
420 21369234 : chrec_fold_multiply (tree type,
421 : tree op0,
422 : tree op1)
423 : {
424 21369650 : if (automatically_generated_chrec_p (op0)
425 19959996 : || automatically_generated_chrec_p (op1))
426 1565296 : return chrec_fold_automatically_generated_operands (op0, op1);
427 :
428 19804354 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
429 15867784 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
430 : std::swap (op0, op1);
431 :
432 19804354 : switch (TREE_CODE (op0))
433 : {
434 4127757 : case POLYNOMIAL_CHREC:
435 4127757 : gcc_checking_assert
436 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
437 4127757 : 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 57969 : CASE_CONVERT:
446 57969 : 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 4087292 : default:
469 4087292 : if (integer_onep (op1))
470 : return op0;
471 4086841 : 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 4086431 : if (INTEGRAL_TYPE_P (type)
481 4086238 : && TYPE_OVERFLOW_UNDEFINED (type)
482 1048923 : && !integer_zerop (CHREC_LEFT (op0))
483 597956 : && TREE_CODE (op1) == INTEGER_CST
484 4513460 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
485 : {
486 336545 : wi::overflow_type ovf = wi::OVF_NONE;
487 336545 : wide_int res
488 336545 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
489 673090 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
490 336545 : 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 336545 : }
503 4086395 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
504 4086395 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
505 4086395 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
506 : }
507 :
508 4706664 : CASE_CONVERT:
509 4706664 : if (tree_contains_chrecs (op0, NULL))
510 : {
511 : /* We can strip sign-conversions to signed by performing the
512 : operation in unsigned. */
513 54555 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
514 54555 : if (INTEGRAL_TYPE_P (type)
515 54555 : && INTEGRAL_TYPE_P (optype)
516 54555 : && tree_nop_conversion_p (type, optype)
517 65992 : && 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 43143 : return chrec_dont_know;
526 : }
527 : /* FALLTHRU */
528 :
529 15622042 : default:
530 15622042 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
531 15622042 : if (integer_onep (op0))
532 : return op1;
533 :
534 10655305 : if (integer_zerop (op0))
535 2294929 : return build_int_cst (type, 0);
536 :
537 8360376 : switch (TREE_CODE (op1))
538 : {
539 0 : case POLYNOMIAL_CHREC:
540 0 : gcc_unreachable ();
541 :
542 999558 : CASE_CONVERT:
543 999558 : if (tree_contains_chrecs (op1, NULL))
544 : return chrec_fold_multiply (type, op1, op0);
545 : /* FALLTHRU */
546 :
547 8359960 : default:
548 8359960 : if (integer_onep (op1))
549 : return op0;
550 8295027 : if (integer_zerop (op1))
551 1606 : return build_int_cst (type, 0);
552 8293421 : 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 896367 : chrec_apply (unsigned var,
671 : tree chrec,
672 : tree x)
673 : {
674 896367 : tree type = chrec_type (chrec);
675 896367 : tree res = chrec_dont_know;
676 :
677 1792734 : if (automatically_generated_chrec_p (chrec)
678 1002284 : || 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 896367 : || chrec_contains_symbols_defined_in_loop (chrec, var))
684 105917 : return chrec_dont_know;
685 :
686 790450 : if (dump_file && (dump_flags & TDF_SCEV))
687 0 : fprintf (dump_file, "(chrec_apply \n");
688 :
689 790450 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
690 124 : x = build_real_from_int_cst (type, x);
691 :
692 790450 : switch (TREE_CODE (chrec))
693 : {
694 789047 : case POLYNOMIAL_CHREC:
695 789047 : if (evolution_function_is_affine_p (chrec))
696 : {
697 783794 : tree chrecr = CHREC_RIGHT (chrec);
698 783794 : tree chrecl = CHREC_LEFT (chrec);
699 783794 : 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 783268 : else if (operand_equal_p (chrecl, chrecr)
706 135275 : && TREE_CODE (x) == PLUS_EXPR
707 6336 : && integer_all_onesp (TREE_OPERAND (x, 1))
708 6076 : && !POINTER_TYPE_P (type)
709 789333 : && TYPE_PRECISION (TREE_TYPE (x))
710 6065 : >= TYPE_PRECISION (type))
711 : {
712 : /* We know the number of iterations can't be negative. */
713 4213 : res = build_int_cst (TREE_TYPE (x), 1);
714 4213 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
715 4213 : res = chrec_convert_rhs (type, res, NULL);
716 4213 : 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 779055 : tree utype = TREE_TYPE (chrecr);
725 779055 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
726 685923 : utype = unsigned_type_for (TREE_TYPE (chrecr));
727 779055 : res = chrec_convert_rhs (utype, x, NULL);
728 779055 : 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 779055 : if (TREE_CODE (res) == INTEGER_CST
734 779055 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
735 : {
736 401383 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
737 401383 : res = chrec_fold_plus (type, chrecl, res);
738 : }
739 : else
740 : {
741 377672 : res = chrec_fold_plus (utype,
742 : chrec_convert (utype, chrecl, NULL),
743 : res);
744 377672 : 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 790450 : 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 2299197 : chrec_replace_initial_condition (tree chrec,
803 : tree init_cond)
804 : {
805 2299197 : if (automatically_generated_chrec_p (chrec))
806 : return chrec;
807 :
808 2299197 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
809 :
810 2299197 : switch (TREE_CODE (chrec))
811 : {
812 1159889 : case POLYNOMIAL_CHREC:
813 1159889 : return build_polynomial_chrec
814 1159889 : (CHREC_VARIABLE (chrec),
815 1159889 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
816 2319778 : 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 11174202 : initial_condition (tree chrec)
827 : {
828 18326026 : if (automatically_generated_chrec_p (chrec))
829 : return chrec;
830 :
831 17081733 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
832 7151824 : 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 48024285 : hide_evolution_in_other_loops_than_loop (tree chrec,
842 : unsigned loop_num)
843 : {
844 48026942 : class loop *loop = get_loop (cfun, loop_num), *chloop;
845 48026942 : if (automatically_generated_chrec_p (chrec))
846 : return chrec;
847 :
848 48026942 : switch (TREE_CODE (chrec))
849 : {
850 2478958 : case POLYNOMIAL_CHREC:
851 2478958 : chloop = get_chrec_loop (chrec);
852 :
853 2478958 : if (chloop == loop)
854 2006331 : return build_polynomial_chrec
855 2006331 : (loop_num,
856 2006331 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
857 : loop_num),
858 4012662 : CHREC_RIGHT (chrec));
859 :
860 472627 : else if (flow_loop_nested_p (chloop, loop))
861 : /* There is no evolution in this loop. */
862 469970 : return initial_condition (chrec);
863 :
864 2657 : else if (flow_loop_nested_p (loop, chloop))
865 2657 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
866 2657 : 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 42112165 : chrec_component_in_loop_num (tree chrec,
881 : unsigned loop_num,
882 : bool right)
883 : {
884 42112165 : tree component;
885 42112165 : class loop *loop = get_loop (cfun, loop_num), *chloop;
886 :
887 42112165 : if (automatically_generated_chrec_p (chrec))
888 : return chrec;
889 :
890 40867872 : switch (TREE_CODE (chrec))
891 : {
892 35191045 : case POLYNOMIAL_CHREC:
893 35191045 : chloop = get_chrec_loop (chrec);
894 :
895 35191045 : if (chloop == loop)
896 : {
897 33859416 : if (right)
898 17232586 : component = CHREC_RIGHT (chrec);
899 : else
900 16626830 : component = CHREC_LEFT (chrec);
901 :
902 33859416 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
903 33859416 : || 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 1331629 : 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 1331629 : gcc_assert (flow_loop_nested_p (loop, chloop));
922 1331629 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
923 : loop_num,
924 1331629 : right);
925 : }
926 :
927 5676827 : default:
928 5676827 : 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 23304005 : evolution_part_in_loop_num (tree chrec,
941 : unsigned loop_num)
942 : {
943 23304005 : 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 17476531 : initial_condition_in_loop_num (tree chrec,
952 : unsigned loop_num)
953 : {
954 17476531 : 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 16301223 : chrec_merge (tree chrec1,
996 : tree chrec2)
997 : {
998 16301223 : if (chrec1 == chrec_dont_know
999 16301223 : || chrec2 == chrec_dont_know)
1000 : return chrec_dont_know;
1001 :
1002 13672270 : if (chrec1 == chrec_known
1003 13672270 : || chrec2 == chrec_known)
1004 : return chrec_known;
1005 :
1006 13672270 : if (chrec1 == chrec_not_analyzed_yet)
1007 : return chrec2;
1008 2840307 : if (chrec2 == chrec_not_analyzed_yet)
1009 : return chrec1;
1010 :
1011 2840307 : if (eq_evolutions_p (chrec1, chrec2))
1012 : return chrec1;
1013 :
1014 2294588 : 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 37177463 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1063 : class loop *loop)
1064 : {
1065 37177463 : int i, n;
1066 :
1067 37177463 : if (chrec == NULL_TREE)
1068 : return false;
1069 :
1070 37177463 : 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 31509567 : if (loop != NULL
1081 600 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1082 31509769 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1083 : return true;
1084 :
1085 31509567 : if (visited.add (chrec))
1086 : return false;
1087 :
1088 30881100 : n = TREE_OPERAND_LENGTH (chrec);
1089 79500588 : for (i = 0; i < n; i++)
1090 21671861 : 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 15505602 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1102 : {
1103 15505602 : hash_set<const_tree> visited;
1104 15505602 : return chrec_contains_symbols (chrec, visited, loop);
1105 15505602 : }
1106 :
1107 : /* Return true when CHREC contains symbolic names defined in
1108 : LOOP_NB. */
1109 :
1110 : static bool
1111 335822592 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1112 : hash_set<const_tree> &visited)
1113 : {
1114 335822592 : int i, n;
1115 :
1116 335822592 : if (chrec == NULL_TREE)
1117 : return false;
1118 :
1119 335685927 : if (is_gimple_min_invariant (chrec))
1120 : return false;
1121 :
1122 198410690 : if (TREE_CODE (chrec) == SSA_NAME)
1123 : {
1124 71814273 : gimple *def;
1125 71814273 : loop_p def_loop, loop;
1126 :
1127 71814273 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1128 : return false;
1129 :
1130 67475278 : def = SSA_NAME_DEF_STMT (chrec);
1131 67475278 : def_loop = loop_containing_stmt (def);
1132 67475278 : loop = get_loop (cfun, loop_nb);
1133 :
1134 67475278 : if (def_loop == NULL)
1135 : return false;
1136 :
1137 67475278 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1138 4398656 : return true;
1139 :
1140 : return false;
1141 : }
1142 :
1143 126596417 : if (visited.add (chrec))
1144 : return false;
1145 :
1146 126555640 : n = TREE_OPERAND_LENGTH (chrec);
1147 463146981 : for (i = 0; i < n; i++)
1148 211354343 : 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 124468249 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1159 : {
1160 124468249 : hash_set<const_tree> visited;
1161 124468249 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1162 124468249 : }
1163 :
1164 : /* Determines whether the chrec contains undetermined coefficients. */
1165 :
1166 : static bool
1167 224901745 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1168 : {
1169 224901745 : int i, n;
1170 :
1171 224901745 : if (chrec == chrec_dont_know)
1172 : return true;
1173 :
1174 202043415 : if (chrec == NULL_TREE)
1175 : return false;
1176 :
1177 201681226 : if (visited.add (chrec))
1178 : return false;
1179 :
1180 188636367 : n = TREE_OPERAND_LENGTH (chrec);
1181 501116993 : for (i = 0; i < n; i++)
1182 123845444 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1183 : return true;
1184 : return false;
1185 : }
1186 :
1187 : bool
1188 101056301 : chrec_contains_undetermined (const_tree chrec)
1189 : {
1190 101056301 : hash_set<const_tree> visited;
1191 101056301 : return chrec_contains_undetermined (chrec, visited);
1192 101056301 : }
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 434141199 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1200 : {
1201 434141199 : int i, n;
1202 :
1203 434141199 : if (expr == NULL_TREE)
1204 : return false;
1205 :
1206 433050001 : if (size)
1207 76494371 : (*size)++;
1208 :
1209 433453463 : if (tree_is_chrec (expr))
1210 : return true;
1211 :
1212 410343010 : if (visited.add (expr))
1213 : return false;
1214 :
1215 407812561 : n = TREE_OPERAND_LENGTH (expr);
1216 1024759243 : for (i = 0; i < n; i++)
1217 209459705 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1218 : return true;
1219 : return false;
1220 : }
1221 :
1222 : bool
1223 224681494 : tree_contains_chrecs (const_tree expr, int *size)
1224 : {
1225 224681494 : hash_set<const_tree> visited;
1226 224681494 : return tree_contains_chrecs (expr, size, visited);
1227 224681494 : }
1228 :
1229 :
1230 : /* Recursive helper function. */
1231 :
1232 : static bool
1233 45928756 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1234 : {
1235 91857512 : if (evolution_function_is_constant_p (chrec))
1236 : return true;
1237 :
1238 10004082 : if (TREE_CODE (chrec) == SSA_NAME
1239 10004082 : && (loopnum == 0
1240 2221653 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1241 2198411 : return true;
1242 :
1243 7805671 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1244 : {
1245 6098600 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1246 132421 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1247 132421 : get_chrec_loop (chrec))
1248 3246 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1249 : loopnum)
1250 6101846 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1251 : loopnum))
1252 6095354 : return false;
1253 : return true;
1254 : }
1255 :
1256 1707071 : switch (TREE_OPERAND_LENGTH (chrec))
1257 : {
1258 974614 : case 2:
1259 974614 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1260 : loopnum))
1261 : return false;
1262 : /* FALLTHRU */
1263 :
1264 1639823 : case 1:
1265 1639823 : 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 30883351 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1279 : {
1280 30883351 : 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 6758761 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1288 : {
1289 6758761 : if (chrec == NULL_TREE)
1290 : return false;
1291 :
1292 6758761 : switch (TREE_CODE (chrec))
1293 : {
1294 6212238 : case POLYNOMIAL_CHREC:
1295 6212238 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1296 : {
1297 6111128 : 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 101110 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1314 101110 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1315 101069 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1316 202179 : && evolution_function_is_affine_multivariate_p
1317 101069 : (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 3449471 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1334 : {
1335 3449471 : if (chrec == NULL_TREE)
1336 : return true;
1337 :
1338 3449471 : tree sub_chrec;
1339 3449471 : switch (TREE_CODE (chrec))
1340 : {
1341 3449468 : case POLYNOMIAL_CHREC:
1342 3449468 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1343 : {
1344 31433 : case POLYNOMIAL_CHREC:
1345 31433 : sub_chrec = CHREC_LEFT (chrec);
1346 31433 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1347 31433 : && (loopnum <= 0
1348 5069 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1349 18 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1350 18 : get_chrec_loop (sub_chrec))))
1351 31421 : return false;
1352 12 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1353 : return false;
1354 : break;
1355 :
1356 3418035 : default:
1357 3418035 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1358 : return false;
1359 : break;
1360 : }
1361 :
1362 3418047 : 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 3418047 : default:
1377 3418047 : 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 3358524 : nb_vars_in_chrec (tree chrec)
1393 : {
1394 6717048 : if (chrec == NULL_TREE)
1395 : return 0;
1396 :
1397 6717048 : switch (TREE_CODE (chrec))
1398 : {
1399 3358524 : case POLYNOMIAL_CHREC:
1400 3358524 : return 1 + nb_vars_in_chrec
1401 3358524 : (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 7460482 : 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 7460482 : tree ct = TREE_TYPE (*step);
1423 7460482 : bool enforce_overflow_semantics;
1424 7460482 : bool must_check_src_overflow, must_check_rslt_overflow;
1425 7460482 : tree new_base, new_step;
1426 7460482 : 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 7460482 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1444 :
1445 16978973 : enforce_overflow_semantics = (use_overflow_semantics
1446 7460482 : && nowrap_type_p (type));
1447 2434260 : 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 2434260 : if (must_check_src_overflow)
1460 : {
1461 440548 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1462 : must_check_rslt_overflow = true;
1463 : else
1464 : must_check_rslt_overflow = false;
1465 : }
1466 1993712 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1467 1993712 : && 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 7084231 : if (must_check_src_overflow
1479 7460482 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1480 : use_overflow_semantics))
1481 : return false;
1482 :
1483 6628787 : 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 6628787 : new_step = *step;
1491 6628787 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1492 : {
1493 126895 : tree signed_ct = signed_type_for (ct);
1494 126895 : new_step = chrec_convert (signed_ct, new_step, at_stmt,
1495 : use_overflow_semantics);
1496 : }
1497 6628787 : new_step = chrec_convert (step_type, new_step, at_stmt,
1498 : use_overflow_semantics);
1499 :
1500 13257574 : if (automatically_generated_chrec_p (new_base)
1501 2082205 : || automatically_generated_chrec_p (new_step))
1502 : return false;
1503 :
1504 6628529 : 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 6628529 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1508 : at_stmt, loop, false))
1509 : return false;
1510 :
1511 5378277 : *base = new_base;
1512 5378277 : *step = new_step;
1513 5378277 : 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 31334593 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1522 : {
1523 31334593 : if (POINTER_TYPE_P (type))
1524 5965222 : type = sizetype;
1525 :
1526 31334593 : 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 156532817 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1545 : bool use_overflow_semantics, tree from)
1546 : {
1547 156532817 : tree ct, res;
1548 156532817 : tree base, step;
1549 156532817 : class loop *loop;
1550 :
1551 270505384 : if (automatically_generated_chrec_p (chrec))
1552 : return chrec;
1553 :
1554 155256936 : ct = chrec_type (chrec);
1555 155256936 : if (useless_type_conversion_p (type, ct))
1556 : return chrec;
1557 :
1558 41284369 : if (!evolution_function_is_affine_p (chrec))
1559 35196582 : goto keep_cast;
1560 :
1561 6087787 : loop = get_chrec_loop (chrec);
1562 6087787 : base = CHREC_LEFT (chrec);
1563 6087787 : step = CHREC_RIGHT (chrec);
1564 :
1565 6087787 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1566 : use_overflow_semantics, from))
1567 4504295 : return build_polynomial_chrec (loop->num, base, step);
1568 :
1569 : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1570 1583492 : 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 36780074 : if (use_overflow_semantics
1575 36132517 : && (TREE_CODE (chrec) == PLUS_EXPR
1576 36132517 : || TREE_CODE (chrec) == MINUS_EXPR)
1577 3480467 : && TREE_CODE (type) == INTEGER_TYPE
1578 3436084 : && TREE_CODE (ct) == INTEGER_TYPE
1579 3436038 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1580 36945432 : && TYPE_OVERFLOW_UNDEFINED (ct))
1581 60202 : 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 36719872 : else if (use_overflow_semantics
1587 36072315 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1588 1614038 : && TREE_CODE (ct) == INTEGER_TYPE
1589 1601078 : && TREE_CODE (type) == INTEGER_TYPE
1590 1463065 : && TYPE_OVERFLOW_UNDEFINED (type)
1591 37882425 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1592 : {
1593 28714 : tree utype = unsigned_type_for (type);
1594 86142 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1595 28714 : fold_convert (utype,
1596 : CHREC_LEFT (chrec)),
1597 28714 : fold_convert (utype,
1598 : CHREC_RIGHT (chrec)));
1599 28714 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1600 : }
1601 : else
1602 36691158 : res = fold_convert (type, chrec);
1603 :
1604 : /* Don't propagate overflows. */
1605 36780074 : if (CONSTANT_CLASS_P (res))
1606 11895437 : 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 36780074 : if (TREE_CODE (res) == INTEGER_CST
1615 11895436 : && TREE_CODE (type) == INTEGER_TYPE
1616 11851852 : && !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 156504103 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1654 : bool use_overflow_semantics, tree from)
1655 : {
1656 156504103 : 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 8578121 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1666 : {
1667 8578121 : tree inner_type, left, right, lc, rc, rtype;
1668 :
1669 8578121 : gcc_assert (fold_conversions != NULL);
1670 :
1671 16657922 : if (automatically_generated_chrec_p (chrec)
1672 8578121 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1673 : return NULL_TREE;
1674 :
1675 654587 : inner_type = TREE_TYPE (chrec);
1676 654587 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1677 : return NULL_TREE;
1678 :
1679 567921 : if (useless_type_conversion_p (type, inner_type))
1680 : return NULL_TREE;
1681 :
1682 498320 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1683 : {
1684 497510 : tree base, step;
1685 497510 : class loop *loop;
1686 :
1687 497510 : loop = get_chrec_loop (chrec);
1688 497510 : base = CHREC_LEFT (chrec);
1689 497510 : step = CHREC_RIGHT (chrec);
1690 497510 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1691 2114 : return build_polynomial_chrec (loop->num, base, step);
1692 : }
1693 496206 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1694 :
1695 496206 : left = CHREC_LEFT (chrec);
1696 496206 : right = CHREC_RIGHT (chrec);
1697 496206 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1698 496206 : if (!lc)
1699 496206 : lc = chrec_convert (type, left, NULL);
1700 496206 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1701 496206 : if (!rc)
1702 495522 : rc = chrec_convert (rtype, right, NULL);
1703 :
1704 496206 : *fold_conversions = true;
1705 :
1706 496206 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1707 : }
1708 :
1709 : /* Returns true when CHREC0 == CHREC1. */
1710 :
1711 : bool
1712 13369672 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1713 : {
1714 13402346 : if (chrec0 == NULL_TREE
1715 13402346 : || chrec1 == NULL_TREE
1716 13402346 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1717 : return false;
1718 :
1719 12501937 : if (operand_equal_p (chrec0, chrec1, 0))
1720 : return true;
1721 :
1722 9341265 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1723 : return false;
1724 :
1725 9340095 : switch (TREE_CODE (chrec0))
1726 : {
1727 3873805 : case POLYNOMIAL_CHREC:
1728 3873805 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1729 3873468 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1730 4209059 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1731 :
1732 56485 : case PLUS_EXPR:
1733 56485 : case MULT_EXPR:
1734 56485 : case MINUS_EXPR:
1735 56485 : case POINTER_PLUS_EXPR:
1736 56485 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1737 56485 : TREE_OPERAND (chrec1, 0))
1738 98631 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1739 42146 : TREE_OPERAND (chrec1, 1));
1740 :
1741 32674 : CASE_CONVERT:
1742 32674 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1743 65348 : 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 3576299 : scev_direction (const_tree chrec)
1756 : {
1757 3576299 : const_tree step;
1758 :
1759 3576299 : if (!evolution_function_is_affine_p (chrec))
1760 : return EV_DIR_UNKNOWN;
1761 :
1762 3567529 : step = CHREC_RIGHT (chrec);
1763 3567529 : if (TREE_CODE (step) != INTEGER_CST)
1764 : return EV_DIR_UNKNOWN;
1765 :
1766 3361401 : if (tree_int_cst_sign_bit (step))
1767 : return EV_DIR_DECREASES;
1768 : else
1769 3024422 : 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 : }
|
