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 88218 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : tree type,
50 : tree poly0,
51 : tree poly1)
52 : {
53 88218 : tree left, right;
54 88218 : class loop *loop0 = get_chrec_loop (poly0);
55 88218 : class loop *loop1 = get_chrec_loop (poly1);
56 :
57 88218 : gcc_assert (poly0);
58 88218 : gcc_assert (poly1);
59 88218 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
60 88218 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
61 88218 : if (POINTER_TYPE_P (chrec_type (poly0)))
62 866 : gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
63 : && useless_type_conversion_p (type, chrec_type (poly0)));
64 : else
65 87352 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
66 : && useless_type_conversion_p (type, chrec_type (poly1)));
67 :
68 : /*
69 : {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
70 : {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
71 : {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
72 88218 : if (flow_loop_nested_p (loop0, loop1))
73 : {
74 300 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
75 236 : return build_polynomial_chrec
76 236 : (CHREC_VARIABLE (poly1),
77 236 : chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
78 472 : CHREC_RIGHT (poly1));
79 : else
80 64 : return build_polynomial_chrec
81 128 : (CHREC_VARIABLE (poly1),
82 64 : chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
83 64 : chrec_fold_multiply (type, CHREC_RIGHT (poly1),
84 64 : SCALAR_FLOAT_TYPE_P (type)
85 0 : ? build_real (type, dconstm1)
86 128 : : build_int_cst_type (type, -1)));
87 : }
88 :
89 87918 : if (flow_loop_nested_p (loop1, loop0))
90 : {
91 604 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
92 558 : return build_polynomial_chrec
93 558 : (CHREC_VARIABLE (poly0),
94 558 : chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
95 1116 : CHREC_RIGHT (poly0));
96 : else
97 46 : return build_polynomial_chrec
98 46 : (CHREC_VARIABLE (poly0),
99 46 : chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
100 92 : CHREC_RIGHT (poly0));
101 : }
102 :
103 : /* This function should never be called for chrecs of loops that
104 : do not belong to the same loop nest. */
105 87314 : if (loop0 != loop1)
106 : {
107 : /* It still can happen if we are not in loop-closed SSA form. */
108 38 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
109 38 : return chrec_dont_know;
110 : }
111 :
112 87276 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
113 : {
114 31923 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
115 31923 : left = chrec_fold_plus
116 31923 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 31923 : right = chrec_fold_plus
118 31923 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : }
120 : else
121 : {
122 55353 : left = chrec_fold_minus
123 55353 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 55353 : right = chrec_fold_minus
125 55353 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : }
127 :
128 87276 : if (chrec_zerop (right))
129 : return left;
130 : /* When we have an evolution in a non-wrapping type and in the process of
131 : accumulating CHREC_RIGHT there was overflow this indicates in the
132 : association that happened in accumulating the CHRECs clearly involved UB.
133 : Avoid this. When accumulating two CHRECs we basically turn
134 : (a + INCR1) + INCR2 into a + (INCR1 + INCR2) which is not always valid.
135 : Note this check only catches few invalid cases. */
136 32848 : else if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
137 21443 : && TREE_CODE (right) == INTEGER_CST
138 35799 : && TREE_OVERFLOW (right))
139 5 : return chrec_dont_know;
140 : else
141 32969 : return build_polynomial_chrec
142 32969 : (CHREC_VARIABLE (poly0), left, right);
143 : }
144 :
145 :
146 :
147 : /* Fold the multiplication of two polynomial functions. */
148 :
149 : static inline tree
150 40813 : chrec_fold_multiply_poly_poly (tree type,
151 : tree poly0,
152 : tree poly1)
153 : {
154 40813 : tree t0, t1, t2;
155 40813 : int var;
156 40813 : class loop *loop0 = get_chrec_loop (poly0);
157 40813 : class loop *loop1 = get_chrec_loop (poly1);
158 :
159 40813 : gcc_assert (poly0);
160 40813 : gcc_assert (poly1);
161 40813 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
162 40813 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
163 40813 : gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
164 : && useless_type_conversion_p (type, chrec_type (poly1)));
165 :
166 : /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
167 : {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
168 : {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
169 40813 : if (flow_loop_nested_p (loop0, loop1))
170 : /* poly0 is a constant wrt. poly1. */
171 0 : return build_polynomial_chrec
172 0 : (CHREC_VARIABLE (poly1),
173 0 : chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
174 0 : CHREC_RIGHT (poly1));
175 :
176 40813 : if (flow_loop_nested_p (loop1, loop0))
177 : /* poly1 is a constant wrt. poly0. */
178 0 : return build_polynomial_chrec
179 0 : (CHREC_VARIABLE (poly0),
180 0 : chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
181 0 : CHREC_RIGHT (poly0));
182 :
183 40813 : if (loop0 != loop1)
184 : {
185 : /* It still can happen if we are not in loop-closed SSA form. */
186 0 : gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
187 0 : return chrec_dont_know;
188 : }
189 :
190 : /* poly0 and poly1 are two polynomials in the same variable,
191 : {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
192 :
193 : /* "a*c". */
194 40813 : t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
195 :
196 : /* "a*d + b*c". */
197 40813 : t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
198 122439 : t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
199 40813 : CHREC_RIGHT (poly0),
200 40813 : CHREC_LEFT (poly1)));
201 : /* "b*d". */
202 40813 : t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
203 : /* "a*d + b*c + b*d". */
204 40813 : t1 = chrec_fold_plus (type, t1, t2);
205 : /* "2*b*d". */
206 81626 : t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
207 39 : ? build_real (type, dconst2)
208 40774 : : build_int_cst (type, 2), t2);
209 :
210 40813 : var = CHREC_VARIABLE (poly0);
211 40813 : return build_polynomial_chrec (var, t0,
212 40813 : build_polynomial_chrec (var, t1, t2));
213 : }
214 :
215 : /* When the operands are automatically_generated_chrec_p, the fold has
216 : to respect the semantics of the operands. */
217 :
218 : static inline tree
219 6255935 : chrec_fold_automatically_generated_operands (tree op0,
220 : tree op1)
221 : {
222 6255935 : if (op0 == chrec_dont_know
223 1030265 : || op1 == chrec_dont_know)
224 : return chrec_dont_know;
225 :
226 0 : if (op0 == chrec_known
227 0 : || op1 == chrec_known)
228 : return chrec_known;
229 :
230 0 : if (op0 == chrec_not_analyzed_yet
231 0 : || op1 == chrec_not_analyzed_yet)
232 0 : return chrec_not_analyzed_yet;
233 :
234 : /* The default case produces a safe result. */
235 : return chrec_dont_know;
236 : }
237 :
238 : /* Fold the addition of two chrecs. */
239 :
240 : static tree
241 31811648 : chrec_fold_plus_1 (enum tree_code code, tree type,
242 : tree op0, tree op1)
243 : {
244 63623296 : if (automatically_generated_chrec_p (op0)
245 31811648 : || automatically_generated_chrec_p (op1))
246 0 : return chrec_fold_automatically_generated_operands (op0, op1);
247 :
248 31811648 : switch (TREE_CODE (op0))
249 : {
250 10154809 : case POLYNOMIAL_CHREC:
251 10154809 : gcc_checking_assert
252 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
253 10154809 : switch (TREE_CODE (op1))
254 : {
255 88218 : case POLYNOMIAL_CHREC:
256 88218 : gcc_checking_assert
257 : (!chrec_contains_symbols_defined_in_loop (op1,
258 : CHREC_VARIABLE (op1)));
259 88218 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
260 :
261 241014 : CASE_CONVERT:
262 241014 : if (tree_contains_chrecs (op1, NULL))
263 : {
264 : /* We can strip sign-conversions to signed by performing the
265 : operation in unsigned. */
266 701 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
267 701 : if (INTEGRAL_TYPE_P (type)
268 701 : && INTEGRAL_TYPE_P (optype)
269 676 : && tree_nop_conversion_p (type, optype)
270 905 : && TYPE_UNSIGNED (optype))
271 : {
272 97 : tree tem = chrec_convert (optype, op0, NULL);
273 97 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
274 15 : return chrec_convert (type,
275 : chrec_fold_plus_1 (code, optype,
276 : tem,
277 15 : TREE_OPERAND
278 : (op1, 0)),
279 15 : NULL);
280 : }
281 686 : return chrec_dont_know;
282 : }
283 : /* FALLTHRU */
284 :
285 10065890 : default:
286 10065890 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
287 9263769 : return build_polynomial_chrec
288 9263769 : (CHREC_VARIABLE (op0),
289 9263769 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
290 18527538 : CHREC_RIGHT (op0));
291 : else
292 802121 : return build_polynomial_chrec
293 802121 : (CHREC_VARIABLE (op0),
294 802121 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
295 1604242 : CHREC_RIGHT (op0));
296 : }
297 :
298 3188483 : CASE_CONVERT:
299 3188483 : if (tree_contains_chrecs (op0, NULL))
300 : {
301 : /* We can strip sign-conversions to signed by performing the
302 : operation in unsigned. */
303 77319 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
304 77319 : if (INTEGRAL_TYPE_P (type)
305 75823 : && INTEGRAL_TYPE_P (optype)
306 71785 : && tree_nop_conversion_p (type, optype)
307 138775 : && TYPE_UNSIGNED (optype))
308 122844 : return chrec_convert (type,
309 : chrec_fold_plus_1 (code, optype,
310 61422 : TREE_OPERAND (op0, 0),
311 : chrec_convert (optype,
312 : op1, NULL)),
313 61422 : NULL);
314 15897 : return chrec_dont_know;
315 : }
316 : /* FALLTHRU */
317 :
318 21579520 : default:
319 21579520 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
320 21579520 : switch (TREE_CODE (op1))
321 : {
322 3256575 : case POLYNOMIAL_CHREC:
323 3256575 : gcc_checking_assert
324 : (!chrec_contains_symbols_defined_in_loop (op1,
325 : CHREC_VARIABLE (op1)));
326 3256575 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
327 3183209 : return build_polynomial_chrec
328 3183209 : (CHREC_VARIABLE (op1),
329 3183209 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
330 6366418 : CHREC_RIGHT (op1));
331 : else
332 73366 : return build_polynomial_chrec
333 146732 : (CHREC_VARIABLE (op1),
334 73366 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
335 73366 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
336 73366 : SCALAR_FLOAT_TYPE_P (type)
337 34 : ? build_real (type, dconstm1)
338 146698 : : build_int_cst_type (type, -1)));
339 :
340 2407997 : CASE_CONVERT:
341 2407997 : if (tree_contains_chrecs (op1, NULL))
342 : {
343 : /* We can strip sign-conversions to signed by performing the
344 : operation in unsigned. */
345 61234 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
346 61234 : if (INTEGRAL_TYPE_P (type)
347 21474 : && INTEGRAL_TYPE_P (optype)
348 21474 : && tree_nop_conversion_p (type, optype)
349 78612 : && TYPE_UNSIGNED (optype))
350 17378 : return chrec_convert (type,
351 : chrec_fold_plus_1 (code, optype,
352 : chrec_convert (optype,
353 : op0,
354 : NULL),
355 17378 : TREE_OPERAND (op1, 0)),
356 17378 : NULL);
357 43856 : return chrec_dont_know;
358 : }
359 : /* FALLTHRU */
360 :
361 18261711 : default:
362 18261711 : {
363 18261711 : int size = 0;
364 18261711 : if ((tree_contains_chrecs (op0, &size)
365 18261711 : || tree_contains_chrecs (op1, &size))
366 18261711 : && size < param_scev_max_expr_size)
367 0 : return build2 (code, type, op0, op1);
368 18261711 : else if (size < param_scev_max_expr_size)
369 : {
370 18261609 : if (code == POINTER_PLUS_EXPR)
371 3490794 : return fold_build_pointer_plus (fold_convert (type, op0),
372 : op1);
373 : else
374 14770815 : return fold_build2 (code, type,
375 : fold_convert (type, op0),
376 : fold_convert (type, op1));
377 : }
378 : else
379 102 : return chrec_dont_know;
380 : }
381 : }
382 : }
383 : }
384 :
385 : /* Fold the addition of two chrecs. */
386 :
387 : tree
388 38390481 : chrec_fold_plus (tree type,
389 : tree op0,
390 : tree op1)
391 : {
392 38390481 : enum tree_code code;
393 73695504 : if (automatically_generated_chrec_p (op0)
394 38390481 : || automatically_generated_chrec_p (op1))
395 3816715 : return chrec_fold_automatically_generated_operands (op0, op1);
396 :
397 34573766 : if (integer_zerop (op0))
398 4187323 : return chrec_convert (type, op1, NULL);
399 30386443 : if (integer_zerop (op1))
400 1972490 : return chrec_convert (type, op0, NULL);
401 :
402 28413953 : if (POINTER_TYPE_P (type))
403 : code = POINTER_PLUS_EXPR;
404 : else
405 21844650 : code = PLUS_EXPR;
406 :
407 28413953 : return chrec_fold_plus_1 (code, type, op0, op1);
408 : }
409 :
410 : /* Fold the subtraction of two chrecs. */
411 :
412 : tree
413 4173981 : chrec_fold_minus (tree type,
414 : tree op0,
415 : tree op1)
416 : {
417 7731780 : if (automatically_generated_chrec_p (op0)
418 4173981 : || automatically_generated_chrec_p (op1))
419 755150 : return chrec_fold_automatically_generated_operands (op0, op1);
420 :
421 3418831 : if (integer_zerop (op1))
422 : return op0;
423 :
424 3318880 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
425 : }
426 :
427 : /* Fold the multiplication of two chrecs. */
428 :
429 : tree
430 22278814 : chrec_fold_multiply (tree type,
431 : tree op0,
432 : tree op1)
433 : {
434 22279367 : if (automatically_generated_chrec_p (op0)
435 20755337 : || automatically_generated_chrec_p (op1))
436 1684070 : return chrec_fold_automatically_generated_operands (op0, op1);
437 :
438 20595297 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
439 16469183 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
440 : std::swap (op0, op1);
441 :
442 20595297 : switch (TREE_CODE (op0))
443 : {
444 4333454 : case POLYNOMIAL_CHREC:
445 4333454 : gcc_checking_assert
446 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
447 4333454 : switch (TREE_CODE (op1))
448 : {
449 40813 : case POLYNOMIAL_CHREC:
450 40813 : gcc_checking_assert
451 : (!chrec_contains_symbols_defined_in_loop (op1,
452 : CHREC_VARIABLE (op1)));
453 40813 : return chrec_fold_multiply_poly_poly (type, op0, op1);
454 :
455 60473 : CASE_CONVERT:
456 60473 : if (tree_contains_chrecs (op1, NULL))
457 : {
458 : /* We can strip sign-conversions to signed by performing the
459 : operation in unsigned. */
460 224 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
461 224 : if (INTEGRAL_TYPE_P (type)
462 224 : && INTEGRAL_TYPE_P (optype)
463 224 : && tree_nop_conversion_p (type, optype)
464 242 : && TYPE_UNSIGNED (optype))
465 : {
466 18 : tree tem = chrec_convert (optype, op0, NULL);
467 18 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
468 18 : return chrec_convert (type,
469 : chrec_fold_multiply (optype, tem,
470 18 : TREE_OPERAND
471 : (op1, 0)),
472 18 : NULL);
473 : }
474 206 : return chrec_dont_know;
475 : }
476 : /* FALLTHRU */
477 :
478 4292417 : default:
479 4292417 : if (integer_onep (op1))
480 : return op0;
481 4291966 : if (integer_zerop (op1))
482 410 : return build_int_cst (type, 0);
483 :
484 : /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
485 : same sign or CHREC_LEFT is zero then folding the multiply into
486 : the addition does not have the same behavior on overflow.
487 : Using unsigned arithmetic in that case causes too many performance
488 : regressions, but catch the constant case where the multiplication
489 : of the step overflows. */
490 4291556 : if (INTEGRAL_TYPE_P (type)
491 4291327 : && TYPE_OVERFLOW_UNDEFINED (type)
492 1127498 : && !integer_zerop (CHREC_LEFT (op0))
493 636466 : && TREE_CODE (op1) == INTEGER_CST
494 4739824 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
495 : {
496 350335 : wi::overflow_type ovf = wi::OVF_NONE;
497 350335 : wide_int res
498 350335 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
499 700670 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
500 350335 : if (ovf != wi::OVF_NONE)
501 : {
502 36 : tree utype = unsigned_type_for (type);
503 36 : tree uop1 = chrec_convert_rhs (utype, op1);
504 36 : tree uleft0 = chrec_convert_rhs (utype, CHREC_LEFT (op0));
505 36 : tree uright0 = chrec_convert_rhs (utype, CHREC_RIGHT (op0));
506 36 : tree left = chrec_fold_multiply (utype, uleft0, uop1);
507 36 : tree right = chrec_fold_multiply (utype, uright0, uop1);
508 36 : tree tem = build_polynomial_chrec (CHREC_VARIABLE (op0),
509 : left, right);
510 36 : return chrec_convert_rhs (type, tem);
511 : }
512 350335 : }
513 4291520 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
514 4291520 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
515 4291520 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
516 : }
517 :
518 4790644 : CASE_CONVERT:
519 4790644 : if (tree_contains_chrecs (op0, NULL))
520 : {
521 : /* We can strip sign-conversions to signed by performing the
522 : operation in unsigned. */
523 75908 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
524 75908 : if (INTEGRAL_TYPE_P (type)
525 75907 : && INTEGRAL_TYPE_P (optype)
526 75907 : && tree_nop_conversion_p (type, optype)
527 88362 : && TYPE_UNSIGNED (optype))
528 24846 : return chrec_convert (type,
529 : chrec_fold_multiply (optype,
530 12423 : TREE_OPERAND (op0, 0),
531 : chrec_convert (optype,
532 : op1,
533 : NULL)),
534 12423 : NULL);
535 63485 : return chrec_dont_know;
536 : }
537 : /* FALLTHRU */
538 :
539 16185935 : default:
540 16185935 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
541 16185935 : if (integer_onep (op0))
542 : return op1;
543 :
544 10991726 : if (integer_zerop (op0))
545 2419059 : return build_int_cst (type, 0);
546 :
547 8572667 : switch (TREE_CODE (op1))
548 : {
549 0 : case POLYNOMIAL_CHREC:
550 0 : gcc_unreachable ();
551 :
552 1028690 : CASE_CONVERT:
553 1028690 : if (tree_contains_chrecs (op1, NULL))
554 : return chrec_fold_multiply (type, op1, op0);
555 : /* FALLTHRU */
556 :
557 8572114 : default:
558 8572114 : if (integer_onep (op1))
559 : return op0;
560 8506401 : if (integer_zerop (op1))
561 1780 : return build_int_cst (type, 0);
562 8504621 : return fold_build2 (MULT_EXPR, type, op0, op1);
563 : }
564 : }
565 : }
566 :
567 :
568 :
569 : /* Operations. */
570 :
571 : /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
572 : calculation overflows, otherwise return C(n,k) with type TYPE. */
573 :
574 : static tree
575 11900 : tree_fold_binomial (tree type, tree n, unsigned int k)
576 : {
577 11900 : wi::overflow_type overflow;
578 11900 : unsigned int i;
579 :
580 : /* Handle the most frequent cases. */
581 11900 : if (k == 0)
582 3930 : return build_int_cst (type, 1);
583 7970 : if (k == 1)
584 3930 : return fold_convert (type, n);
585 :
586 4040 : widest_int num = wi::to_widest (n);
587 :
588 : /* Check that k <= n. */
589 4040 : if (wi::ltu_p (num, k))
590 : return NULL_TREE;
591 :
592 : /* Denominator = 2. */
593 3946 : widest_int denom = 2;
594 :
595 : /* Index = Numerator-1. */
596 3946 : widest_int idx = num - 1;
597 :
598 : /* Numerator = Numerator*Index = n*(n-1). */
599 3946 : num = wi::smul (num, idx, &overflow);
600 3946 : if (overflow)
601 : return NULL_TREE;
602 :
603 3952 : for (i = 3; i <= k; i++)
604 : {
605 : /* Index--. */
606 6 : --idx;
607 :
608 : /* Numerator *= Index. */
609 6 : num = wi::smul (num, idx, &overflow);
610 6 : if (overflow)
611 : return NULL_TREE;
612 :
613 : /* Denominator *= i. */
614 6 : denom *= i;
615 : }
616 :
617 : /* Result = Numerator / Denominator. */
618 3946 : num = wi::udiv_trunc (num, denom);
619 3946 : if (! wi::fits_to_tree_p (num, type))
620 : return NULL_TREE;
621 3936 : return wide_int_to_tree (type, num);
622 4040 : }
623 :
624 : /* Helper function. Use the Newton's interpolating formula for
625 : evaluating the value of the evolution function.
626 : The result may be in an unsigned type of CHREC. */
627 :
628 : static tree
629 12117 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
630 : {
631 12117 : tree arg0, arg1, binomial_n_k;
632 12117 : tree type = TREE_TYPE (chrec);
633 12117 : class loop *var_loop = get_loop (cfun, var);
634 :
635 12117 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
636 12117 : && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
637 0 : chrec = CHREC_LEFT (chrec);
638 :
639 : /* The formula associates the expression and thus we have to make
640 : sure to not introduce undefined overflow. */
641 12117 : tree ctype = type;
642 12117 : if (INTEGRAL_TYPE_P (type)
643 12117 : && ! TYPE_OVERFLOW_WRAPS (type))
644 11781 : ctype = unsigned_type_for (type);
645 :
646 12117 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
647 12117 : && CHREC_VARIABLE (chrec) == var)
648 : {
649 8083 : arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
650 8083 : if (arg1 == chrec_dont_know)
651 : return chrec_dont_know;
652 7866 : binomial_n_k = tree_fold_binomial (ctype, n, k);
653 7866 : if (!binomial_n_k)
654 0 : return chrec_dont_know;
655 7866 : tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
656 7866 : arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
657 7866 : return chrec_fold_plus (ctype, arg0, arg1);
658 : }
659 :
660 4034 : binomial_n_k = tree_fold_binomial (ctype, n, k);
661 4034 : if (!binomial_n_k)
662 104 : return chrec_dont_know;
663 :
664 3930 : return fold_build2 (MULT_EXPR, ctype,
665 : chrec_convert (ctype, chrec, NULL), binomial_n_k);
666 : }
667 :
668 : /* Evaluates "CHREC (X)" when the varying variable is VAR.
669 : Example: Given the following parameters,
670 :
671 : var = 1
672 : chrec = {3, +, 4}_1
673 : x = 10
674 :
675 : The result is given by the Newton's interpolating formula:
676 : 3 * \binom{10}{0} + 4 * \binom{10}{1}.
677 : */
678 :
679 : tree
680 924068 : chrec_apply (unsigned var,
681 : tree chrec,
682 : tree x)
683 : {
684 924068 : tree type = chrec_type (chrec);
685 924068 : tree res = chrec_dont_know;
686 :
687 1848136 : if (automatically_generated_chrec_p (chrec)
688 1046376 : || automatically_generated_chrec_p (x)
689 :
690 : /* When the symbols are defined in an outer loop, it is possible
691 : to symbolically compute the apply, since the symbols are
692 : constants with respect to the varying loop. */
693 924068 : || chrec_contains_symbols_defined_in_loop (chrec, var))
694 122308 : return chrec_dont_know;
695 :
696 801760 : if (dump_file && (dump_flags & TDF_SCEV))
697 0 : fprintf (dump_file, "(chrec_apply \n");
698 :
699 801760 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
700 122 : x = build_real_from_int_cst (type, x);
701 :
702 801760 : switch (TREE_CODE (chrec))
703 : {
704 800355 : case POLYNOMIAL_CHREC:
705 800355 : if (evolution_function_is_affine_p (chrec))
706 : {
707 795010 : tree chrecr = CHREC_RIGHT (chrec);
708 795010 : tree chrecl = CHREC_LEFT (chrec);
709 795010 : if (CHREC_VARIABLE (chrec) != var)
710 526 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
711 : chrec_apply (var, chrecl, x),
712 : chrec_apply (var, chrecr, x));
713 :
714 : /* "{a, +, a}" (x-1) -> "a*x". */
715 794484 : else if (operand_equal_p (chrecl, chrecr)
716 140401 : && TREE_CODE (x) == PLUS_EXPR
717 7242 : && integer_all_onesp (TREE_OPERAND (x, 1))
718 6979 : && !POINTER_TYPE_P (type)
719 801452 : && TYPE_PRECISION (TREE_TYPE (x))
720 6968 : >= TYPE_PRECISION (type))
721 : {
722 : /* We know the number of iterations can't be negative. */
723 5141 : res = build_int_cst (TREE_TYPE (x), 1);
724 5141 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
725 5141 : res = chrec_convert_rhs (type, res, NULL);
726 5141 : res = chrec_fold_multiply (type, chrecr, res);
727 : }
728 : /* "{a, +, b} (x)" -> "a + b*x". */
729 : else
730 : {
731 : /* The overall increment might not fit in a signed type so
732 : use an unsigned computation to get at the final value
733 : and avoid undefined signed overflow. */
734 789343 : tree utype = TREE_TYPE (chrecr);
735 789343 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
736 701497 : utype = unsigned_type_for (TREE_TYPE (chrecr));
737 789343 : res = chrec_convert_rhs (utype, x, NULL);
738 789343 : res = chrec_fold_multiply (utype,
739 : chrec_convert (utype, chrecr, NULL),
740 : res);
741 : /* When the resulting increment fits the original type
742 : do the increment in it. */
743 789343 : if (TREE_CODE (res) == INTEGER_CST
744 789343 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
745 : {
746 410672 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
747 410672 : res = chrec_fold_plus (type, chrecl, res);
748 : }
749 : else
750 : {
751 378671 : res = chrec_fold_plus (utype,
752 : chrec_convert (utype, chrecl, NULL),
753 : res);
754 378671 : res = chrec_convert (type, res, NULL);
755 : }
756 : }
757 : }
758 5345 : else if (TREE_CODE (x) == INTEGER_CST
759 5345 : && tree_int_cst_sgn (x) == 1)
760 : /* testsuite/.../ssa-chrec-38.c. */
761 4034 : res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
762 : else
763 1311 : res = chrec_dont_know;
764 : break;
765 :
766 247 : CASE_CONVERT:
767 247 : res = chrec_convert (TREE_TYPE (chrec),
768 247 : chrec_apply (var, TREE_OPERAND (chrec, 0), x),
769 : NULL);
770 247 : break;
771 :
772 : default:
773 : res = chrec;
774 : break;
775 : }
776 :
777 801760 : if (dump_file && (dump_flags & TDF_SCEV))
778 : {
779 0 : fprintf (dump_file, " (varying_loop = %d", var);
780 0 : fprintf (dump_file, ")\n (chrec = ");
781 0 : print_generic_expr (dump_file, chrec);
782 0 : fprintf (dump_file, ")\n (x = ");
783 0 : print_generic_expr (dump_file, x);
784 0 : fprintf (dump_file, ")\n (res = ");
785 0 : print_generic_expr (dump_file, res);
786 0 : fprintf (dump_file, "))\n");
787 : }
788 :
789 : return res;
790 : }
791 :
792 : /* For a given CHREC and an induction variable map IV_MAP that maps
793 : (loop->num, expr) for every loop number of the current_loops an
794 : expression, calls chrec_apply when the expression is not NULL. */
795 :
796 : tree
797 892 : chrec_apply_map (tree chrec, vec<tree> iv_map)
798 : {
799 892 : int i;
800 892 : tree expr;
801 :
802 9860 : FOR_EACH_VEC_ELT (iv_map, i, expr)
803 8968 : if (expr)
804 1596 : chrec = chrec_apply (i, chrec, expr);
805 :
806 892 : return chrec;
807 : }
808 :
809 : /* Replaces the initial condition in CHREC with INIT_COND. */
810 :
811 : tree
812 2381555 : chrec_replace_initial_condition (tree chrec,
813 : tree init_cond)
814 : {
815 2381555 : if (automatically_generated_chrec_p (chrec))
816 : return chrec;
817 :
818 2381555 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
819 :
820 2381555 : switch (TREE_CODE (chrec))
821 : {
822 1201279 : case POLYNOMIAL_CHREC:
823 1201279 : return build_polynomial_chrec
824 1201279 : (CHREC_VARIABLE (chrec),
825 1201279 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
826 2402558 : CHREC_RIGHT (chrec));
827 :
828 : default:
829 : return init_cond;
830 : }
831 : }
832 :
833 : /* Returns the initial condition of a given CHREC. */
834 :
835 : tree
836 11960535 : initial_condition (tree chrec)
837 : {
838 19311211 : if (automatically_generated_chrec_p (chrec))
839 : return chrec;
840 :
841 18015402 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
842 7350676 : return initial_condition (CHREC_LEFT (chrec));
843 : else
844 : return chrec;
845 : }
846 :
847 : /* Returns a univariate function that represents the evolution in
848 : LOOP_NUM. Mask the evolution of any other loop. */
849 :
850 : tree
851 50457954 : hide_evolution_in_other_loops_than_loop (tree chrec,
852 : unsigned loop_num)
853 : {
854 50460458 : class loop *loop = get_loop (cfun, loop_num), *chloop;
855 50460458 : if (automatically_generated_chrec_p (chrec))
856 : return chrec;
857 :
858 50460458 : switch (TREE_CODE (chrec))
859 : {
860 2595070 : case POLYNOMIAL_CHREC:
861 2595070 : chloop = get_chrec_loop (chrec);
862 :
863 2595070 : if (chloop == loop)
864 2122713 : return build_polynomial_chrec
865 2122713 : (loop_num,
866 2122713 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
867 : loop_num),
868 4245426 : CHREC_RIGHT (chrec));
869 :
870 472357 : else if (flow_loop_nested_p (chloop, loop))
871 : /* There is no evolution in this loop. */
872 469853 : return initial_condition (chrec);
873 :
874 2504 : else if (flow_loop_nested_p (loop, chloop))
875 2504 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
876 2504 : loop_num);
877 :
878 : else
879 0 : return chrec_dont_know;
880 :
881 : default:
882 : return chrec;
883 : }
884 : }
885 :
886 : /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
887 : true, otherwise returns the initial condition in LOOP_NUM. */
888 :
889 : static tree
890 42017797 : chrec_component_in_loop_num (tree chrec,
891 : unsigned loop_num,
892 : bool right)
893 : {
894 43362298 : tree component;
895 43362298 : class loop *loop = get_loop (cfun, loop_num), *chloop;
896 :
897 43362298 : if (automatically_generated_chrec_p (chrec))
898 : return chrec;
899 :
900 42066489 : switch (TREE_CODE (chrec))
901 : {
902 35743630 : case POLYNOMIAL_CHREC:
903 35743630 : chloop = get_chrec_loop (chrec);
904 :
905 35743630 : if (chloop == loop)
906 : {
907 34399129 : if (right)
908 17565813 : component = CHREC_RIGHT (chrec);
909 : else
910 16833316 : component = CHREC_LEFT (chrec);
911 :
912 34399129 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
913 34399129 : || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
914 : return component;
915 :
916 : else
917 0 : return build_polynomial_chrec
918 0 : (loop_num,
919 0 : chrec_component_in_loop_num (CHREC_LEFT (chrec),
920 : loop_num,
921 : right),
922 0 : component);
923 : }
924 :
925 1344501 : else if (flow_loop_nested_p (chloop, loop))
926 : /* There is no evolution part in this loop. */
927 : return NULL_TREE;
928 :
929 : else
930 : {
931 1344501 : gcc_assert (flow_loop_nested_p (loop, chloop));
932 1344501 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
933 : loop_num,
934 1344501 : right);
935 : }
936 :
937 6322859 : default:
938 6322859 : if (right)
939 : return NULL_TREE;
940 : else
941 887705 : return chrec;
942 : }
943 : }
944 :
945 : /* Returns the evolution part in LOOP_NUM. Example: the call
946 : evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
947 : {1, +, 2}_1 */
948 :
949 : tree
950 24296776 : evolution_part_in_loop_num (tree chrec,
951 : unsigned loop_num)
952 : {
953 24296776 : return chrec_component_in_loop_num (chrec, loop_num, true);
954 : }
955 :
956 : /* Returns the initial condition in LOOP_NUM. Example: the call
957 : initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
958 : {0, +, 1}_1 */
959 :
960 : tree
961 17721021 : initial_condition_in_loop_num (tree chrec,
962 : unsigned loop_num)
963 : {
964 17721021 : return chrec_component_in_loop_num (chrec, loop_num, false);
965 : }
966 :
967 : /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
968 : This function is essentially used for setting the evolution to
969 : chrec_dont_know, for example after having determined that it is
970 : impossible to say how many times a loop will execute. */
971 :
972 : tree
973 0 : reset_evolution_in_loop (unsigned loop_num,
974 : tree chrec,
975 : tree new_evol)
976 : {
977 0 : class loop *loop = get_loop (cfun, loop_num);
978 :
979 0 : if (POINTER_TYPE_P (chrec_type (chrec)))
980 0 : gcc_assert (ptrofftype_p (chrec_type (new_evol)));
981 : else
982 0 : gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
983 :
984 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
985 0 : && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
986 : {
987 0 : tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
988 : new_evol);
989 0 : tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
990 : new_evol);
991 0 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
992 : }
993 :
994 0 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
995 0 : && CHREC_VARIABLE (chrec) == loop_num)
996 0 : chrec = CHREC_LEFT (chrec);
997 :
998 0 : return build_polynomial_chrec (loop_num, chrec, new_evol);
999 : }
1000 :
1001 : /* Merges two evolution functions that were found by following two
1002 : alternate paths of a conditional expression. */
1003 :
1004 : tree
1005 17599643 : chrec_merge (tree chrec1,
1006 : tree chrec2)
1007 : {
1008 17599643 : if (chrec1 == chrec_dont_know
1009 17599643 : || chrec2 == chrec_dont_know)
1010 : return chrec_dont_know;
1011 :
1012 14688462 : if (chrec1 == chrec_known
1013 14688462 : || chrec2 == chrec_known)
1014 : return chrec_known;
1015 :
1016 14688462 : if (chrec1 == chrec_not_analyzed_yet)
1017 : return chrec2;
1018 3102948 : if (chrec2 == chrec_not_analyzed_yet)
1019 : return chrec1;
1020 :
1021 3102948 : if (eq_evolutions_p (chrec1, chrec2))
1022 : return chrec1;
1023 :
1024 2478100 : return chrec_dont_know;
1025 : }
1026 :
1027 :
1028 :
1029 : /* Observers. */
1030 :
1031 : /* Helper function for is_multivariate_chrec. */
1032 :
1033 : static bool
1034 0 : is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
1035 : {
1036 0 : if (chrec == NULL_TREE)
1037 : return false;
1038 :
1039 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1040 : {
1041 0 : if (CHREC_VARIABLE (chrec) != rec_var)
1042 : return true;
1043 : else
1044 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
1045 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
1046 : }
1047 : else
1048 : return false;
1049 : }
1050 :
1051 : /* Determine whether the given chrec is multivariate or not. */
1052 :
1053 : bool
1054 0 : is_multivariate_chrec (const_tree chrec)
1055 : {
1056 0 : if (chrec == NULL_TREE)
1057 : return false;
1058 :
1059 0 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1060 0 : return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
1061 0 : CHREC_VARIABLE (chrec))
1062 0 : || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
1063 0 : CHREC_VARIABLE (chrec)));
1064 : else
1065 : return false;
1066 : }
1067 :
1068 : /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
1069 : NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
1070 :
1071 : static bool
1072 38169874 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1073 : class loop *loop)
1074 : {
1075 38169874 : int i, n;
1076 :
1077 38169874 : if (chrec == NULL_TREE)
1078 : return false;
1079 :
1080 38169874 : if (TREE_CODE (chrec) == SSA_NAME
1081 : || VAR_P (chrec)
1082 : || TREE_CODE (chrec) == POLY_INT_CST
1083 : || TREE_CODE (chrec) == PARM_DECL
1084 : || TREE_CODE (chrec) == FUNCTION_DECL
1085 : || TREE_CODE (chrec) == LABEL_DECL
1086 : || TREE_CODE (chrec) == RESULT_DECL
1087 : || TREE_CODE (chrec) == FIELD_DECL)
1088 : return true;
1089 :
1090 32172930 : if (loop != NULL
1091 600 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1092 32173132 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1093 : return true;
1094 :
1095 32172930 : if (visited.add (chrec))
1096 : return false;
1097 :
1098 31509758 : n = TREE_OPERAND_LENGTH (chrec);
1099 81102151 : for (i = 0; i < n; i++)
1100 22134204 : if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
1101 : return true;
1102 : return false;
1103 : }
1104 :
1105 : /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
1106 : CHREC contains any chrec which is invariant wrto the loop (nest), in other
1107 : words, chrec defined by outer loops of loop, so from LOOP's point of view,
1108 : the chrec is considered as a SYMBOL. */
1109 :
1110 : bool
1111 16035670 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1112 : {
1113 16035670 : hash_set<const_tree> visited;
1114 16035670 : return chrec_contains_symbols (chrec, visited, loop);
1115 16035670 : }
1116 :
1117 : /* Return true when CHREC contains symbolic names defined in
1118 : LOOP_NB. */
1119 :
1120 : static bool
1121 350802406 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1122 : hash_set<const_tree> &visited)
1123 : {
1124 350802406 : int i, n;
1125 :
1126 350802406 : if (chrec == NULL_TREE)
1127 : return false;
1128 :
1129 350654629 : if (is_gimple_min_invariant (chrec))
1130 : return false;
1131 :
1132 207489783 : if (TREE_CODE (chrec) == SSA_NAME)
1133 : {
1134 75015867 : gimple *def;
1135 75015867 : loop_p def_loop, loop;
1136 :
1137 75015867 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1138 : return false;
1139 :
1140 70541539 : def = SSA_NAME_DEF_STMT (chrec);
1141 70541539 : def_loop = loop_containing_stmt (def);
1142 70541539 : loop = get_loop (cfun, loop_nb);
1143 :
1144 70541539 : if (def_loop == NULL)
1145 : return false;
1146 :
1147 70541539 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1148 4752655 : return true;
1149 :
1150 : return false;
1151 : }
1152 :
1153 132473916 : if (visited.add (chrec))
1154 : return false;
1155 :
1156 132429723 : n = TREE_OPERAND_LENGTH (chrec);
1157 483966870 : for (i = 0; i < n; i++)
1158 220489943 : if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1159 : loop_nb, visited))
1160 : return true;
1161 : return false;
1162 : }
1163 :
1164 : /* Return true when CHREC contains symbolic names defined in
1165 : LOOP_NB. */
1166 :
1167 : bool
1168 130312463 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1169 : {
1170 130312463 : hash_set<const_tree> visited;
1171 130312463 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1172 130312463 : }
1173 :
1174 : /* Determines whether the chrec contains undetermined coefficients. */
1175 :
1176 : static bool
1177 234519523 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1178 : {
1179 234519523 : int i, n;
1180 :
1181 234519523 : if (chrec == chrec_dont_know)
1182 : return true;
1183 :
1184 210720041 : if (chrec == NULL_TREE)
1185 : return false;
1186 :
1187 210324191 : if (visited.add (chrec))
1188 : return false;
1189 :
1190 196655585 : n = TREE_OPERAND_LENGTH (chrec);
1191 522536898 : for (i = 0; i < n; i++)
1192 129226996 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1193 : return true;
1194 : return false;
1195 : }
1196 :
1197 : bool
1198 105292527 : chrec_contains_undetermined (const_tree chrec)
1199 : {
1200 105292527 : hash_set<const_tree> visited;
1201 105292527 : return chrec_contains_undetermined (chrec, visited);
1202 105292527 : }
1203 :
1204 : /* Determines whether the tree EXPR contains chrecs, and increment
1205 : SIZE if it is not a NULL pointer by an estimation of the depth of
1206 : the tree. */
1207 :
1208 : static bool
1209 453308806 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1210 : {
1211 453308806 : int i, n;
1212 :
1213 453308806 : if (expr == NULL_TREE)
1214 : return false;
1215 :
1216 452104787 : if (size)
1217 79804154 : (*size)++;
1218 :
1219 452104787 : if (tree_is_chrec (expr))
1220 : return true;
1221 :
1222 428391209 : if (visited.add (expr))
1223 : return false;
1224 :
1225 425790975 : n = TREE_OPERAND_LENGTH (expr);
1226 1070148320 : for (i = 0; i < n; i++)
1227 218952496 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1228 : return true;
1229 : return false;
1230 : }
1231 :
1232 : bool
1233 234356310 : tree_contains_chrecs (const_tree expr, int *size)
1234 : {
1235 234356310 : hash_set<const_tree> visited;
1236 234356310 : return tree_contains_chrecs (expr, size, visited);
1237 234356310 : }
1238 :
1239 :
1240 : /* Recursive helper function. */
1241 :
1242 : static bool
1243 44875634 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1244 : {
1245 93668046 : if (evolution_function_is_constant_p (chrec))
1246 : return true;
1247 :
1248 10480745 : if (TREE_CODE (chrec) == SSA_NAME
1249 10480745 : && (loopnum == 0
1250 2302239 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1251 : return true;
1252 :
1253 8208786 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1254 : {
1255 6174909 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1256 135611 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1257 135611 : get_chrec_loop (chrec))
1258 3276 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1259 : loopnum)
1260 6178185 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1261 : loopnum))
1262 6171633 : return false;
1263 : return true;
1264 : }
1265 :
1266 2033877 : switch (TREE_OPERAND_LENGTH (chrec))
1267 : {
1268 945594 : case 2:
1269 945594 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1270 : loopnum))
1271 : return false;
1272 : /* FALLTHRU */
1273 :
1274 1958389 : case 1:
1275 1958389 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1276 : loopnum))
1277 : return false;
1278 : return true;
1279 :
1280 : default:
1281 : return false;
1282 : }
1283 : }
1284 :
1285 : /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1286 :
1287 : bool
1288 31350012 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1289 : {
1290 31350012 : return evolution_function_is_invariant_rec_p (chrec, loopnum);
1291 : }
1292 :
1293 : /* Determine whether the given tree is an affine multivariate
1294 : evolution. */
1295 :
1296 : bool
1297 6846227 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1298 : {
1299 6846227 : if (chrec == NULL_TREE)
1300 : return false;
1301 :
1302 6846227 : switch (TREE_CODE (chrec))
1303 : {
1304 6286738 : case POLYNOMIAL_CHREC:
1305 6286738 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1306 : {
1307 6185396 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1308 : return true;
1309 : else
1310 : {
1311 210 : if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1312 210 : && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1313 210 : != CHREC_VARIABLE (chrec)
1314 210 : && evolution_function_is_affine_multivariate_p
1315 0 : (CHREC_RIGHT (chrec), loopnum))
1316 : return true;
1317 : else
1318 210 : return false;
1319 : }
1320 : }
1321 : else
1322 : {
1323 101342 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1324 101342 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1325 101291 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1326 202633 : && evolution_function_is_affine_multivariate_p
1327 101291 : (CHREC_LEFT (chrec), loopnum))
1328 101291 : return true;
1329 : else
1330 : return false;
1331 : }
1332 :
1333 : default:
1334 : return false;
1335 : }
1336 : }
1337 :
1338 : /* Determine whether the given tree is a function in zero or one
1339 : variables with respect to loop specified by LOOPNUM. Note only positive
1340 : LOOPNUM stands for a real loop. */
1341 :
1342 : bool
1343 3468522 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1344 : {
1345 3468522 : if (chrec == NULL_TREE)
1346 : return true;
1347 :
1348 3468522 : tree sub_chrec;
1349 3468522 : switch (TREE_CODE (chrec))
1350 : {
1351 3468519 : case POLYNOMIAL_CHREC:
1352 3468519 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1353 : {
1354 31499 : case POLYNOMIAL_CHREC:
1355 31499 : sub_chrec = CHREC_LEFT (chrec);
1356 31499 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1357 31499 : && (loopnum <= 0
1358 5126 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1359 24 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1360 24 : get_chrec_loop (sub_chrec))))
1361 : return false;
1362 15 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1363 : return false;
1364 : break;
1365 :
1366 3437020 : default:
1367 3437020 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1368 : return false;
1369 : break;
1370 : }
1371 :
1372 3437035 : switch (TREE_CODE (CHREC_RIGHT (chrec)))
1373 : {
1374 0 : case POLYNOMIAL_CHREC:
1375 0 : sub_chrec = CHREC_RIGHT (chrec);
1376 0 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1377 0 : && (loopnum <= 0
1378 0 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1379 0 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1380 0 : get_chrec_loop (sub_chrec))))
1381 : return false;
1382 0 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1383 : return false;
1384 : break;
1385 :
1386 3437035 : default:
1387 3437035 : if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1388 0 : return false;
1389 : break;
1390 : }
1391 : return true;
1392 :
1393 : default:
1394 : return true;
1395 : }
1396 : }
1397 :
1398 : /* Returns the number of variables of CHREC. Example: the call
1399 : nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1400 :
1401 : unsigned
1402 3379846 : nb_vars_in_chrec (tree chrec)
1403 : {
1404 6759692 : if (chrec == NULL_TREE)
1405 : return 0;
1406 :
1407 6759692 : switch (TREE_CODE (chrec))
1408 : {
1409 3379846 : case POLYNOMIAL_CHREC:
1410 3379846 : return 1 + nb_vars_in_chrec
1411 3379846 : (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1412 :
1413 : default:
1414 : return 0;
1415 : }
1416 : }
1417 :
1418 : /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1419 : the scev corresponds to. AT_STMT is the statement at that the scev is
1420 : evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1421 : that the rules for overflow of the given language apply (e.g., that signed
1422 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1423 : unnecessary tests, but also to enforce that the result follows them.
1424 : FROM is the source variable converted if it's not NULL.
1425 : If NOWRAP_BOUND is nonzero, pass it on to scev_probably_wraps_p etc.
1426 : to have them determine the bound below which no wrapping occurs.
1427 : Most other functions just forward NOWRAP_BOUND, therefore it is not
1428 : documented everywhere.
1429 : The function returns true if the conversion succeeded, false otherwise. */
1430 :
1431 : bool
1432 7945064 : convert_affine_scev (class loop *loop, tree type,
1433 : tree *base, tree *step, gimple *at_stmt,
1434 : bool use_overflow_semantics, tree from,
1435 : tree *nowrap_bound)
1436 : {
1437 7945064 : tree ct = TREE_TYPE (*step);
1438 7945064 : bool enforce_overflow_semantics;
1439 7945064 : bool must_check_src_overflow, must_check_rslt_overflow;
1440 7945064 : tree new_base, new_step;
1441 7945064 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1442 :
1443 : /* In general,
1444 : (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1445 : but we must check some assumptions.
1446 :
1447 : 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1448 : of CT is smaller than the precision of TYPE. For example, when we
1449 : cast unsigned char [254, +, 1] to unsigned, the values on left side
1450 : are 254, 255, 0, 1, ..., but those on the right side are
1451 : 254, 255, 256, 257, ...
1452 : 2) In case that we must also preserve the fact that signed ivs do not
1453 : overflow, we must additionally check that the new iv does not wrap.
1454 : For example, unsigned char [125, +, 1] casted to signed char could
1455 : become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1456 : which would confuse optimizers that assume that this does not
1457 : happen. */
1458 7945064 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1459 :
1460 : /* MUST_CHECK_SRC_OVERFLOW implies chrec_convert_aggressive later
1461 : which can prove "no wrap" without assumptions. */
1462 7945064 : if (!must_check_src_overflow)
1463 5738107 : nowrap_bound = NULL;
1464 :
1465 18254843 : enforce_overflow_semantics = (use_overflow_semantics
1466 7945064 : && nowrap_type_p (type));
1467 2780852 : if (enforce_overflow_semantics)
1468 : {
1469 : /* We can avoid checking whether the result overflows in the following
1470 : cases:
1471 :
1472 : -- must_check_src_overflow is true, and the range of TYPE is superset
1473 : of the range of CT -- i.e., in all cases except if CT signed and
1474 : TYPE unsigned.
1475 : -- both CT and TYPE have the same precision and signedness, and we
1476 : verify instead that the source does not overflow (this may be
1477 : easier than verifying it for the result, as we may use the
1478 : information about the semantics of overflow in CT). */
1479 2780852 : if (must_check_src_overflow)
1480 : {
1481 455097 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1482 : must_check_rslt_overflow = true;
1483 : else
1484 : must_check_rslt_overflow = false;
1485 : }
1486 2325755 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1487 2325755 : && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1488 : {
1489 : must_check_rslt_overflow = false;
1490 : must_check_src_overflow = true;
1491 : }
1492 : else
1493 : must_check_rslt_overflow = true;
1494 : }
1495 : else
1496 : must_check_rslt_overflow = false;
1497 :
1498 7528927 : if (must_check_src_overflow
1499 7945064 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1500 : use_overflow_semantics, nowrap_bound))
1501 : return false;
1502 :
1503 7119216 : new_base = chrec_convert (type, *base, at_stmt, nowrap_bound,
1504 : use_overflow_semantics);
1505 : /* The step must be sign extended, regardless of the signedness
1506 : of CT and TYPE. This only needs to be handled specially when
1507 : CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1508 : (with values 100, 99, 98, ...) from becoming signed or unsigned
1509 : [100, +, 255] with values 100, 355, ...; the sign-extension is
1510 : performed by default when CT is signed. */
1511 7119216 : new_step = *step;
1512 7119216 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1513 : {
1514 153119 : tree signed_ct = signed_type_for (ct);
1515 153119 : new_step = chrec_convert (signed_ct, new_step, at_stmt, nowrap_bound,
1516 : use_overflow_semantics);
1517 : }
1518 7119216 : new_step = chrec_convert (step_type, new_step, at_stmt, nowrap_bound,
1519 : use_overflow_semantics);
1520 :
1521 14234173 : if (automatically_generated_chrec_p (new_base)
1522 15059759 : || automatically_generated_chrec_p (new_step))
1523 : return false;
1524 :
1525 7114695 : if (must_check_rslt_overflow
1526 : /* Note that in this case we cannot use the fact that signed variables
1527 : do not overflow, as this is what we are verifying for the new iv. */
1528 7114695 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1529 : at_stmt, loop, false, nowrap_bound))
1530 : return false;
1531 :
1532 5652048 : *base = new_base;
1533 5652048 : *step = new_step;
1534 5652048 : return true;
1535 : }
1536 :
1537 :
1538 : /* Convert CHREC for the right hand side of a CHREC.
1539 : The increment for a pointer type is always sizetype. */
1540 :
1541 : tree
1542 32578798 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt, tree *nowrap_bound)
1543 : {
1544 32578798 : if (POINTER_TYPE_P (type))
1545 5999731 : type = sizetype;
1546 :
1547 32578798 : return chrec_convert (type, chrec, at_stmt, nowrap_bound);
1548 : }
1549 :
1550 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1551 : which the CHREC is built, it sets AT_STMT to the statement that
1552 : contains the definition of the analyzed variable, otherwise the
1553 : conversion is less accurate: the information is used for
1554 : determining a more accurate estimation of the number of iterations.
1555 : By default AT_STMT could be safely set to NULL_TREE.
1556 :
1557 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1558 : the rules for overflow of the given language apply (e.g., that signed
1559 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1560 : unnecessary tests, but also to enforce that the result follows them.
1561 :
1562 : FROM is the source variable converted if it's not NULL. */
1563 :
1564 : static tree
1565 164290853 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1566 : tree *nowrap_bound, bool use_overflow_semantics, tree from)
1567 : {
1568 164290853 : tree ct, res;
1569 164290853 : tree base, step;
1570 164290853 : class loop *loop;
1571 :
1572 164290853 : if (automatically_generated_chrec_p (chrec))
1573 : return chrec;
1574 :
1575 162924687 : ct = chrec_type (chrec);
1576 162924687 : if (useless_type_conversion_p (type, ct))
1577 : return chrec;
1578 :
1579 44008415 : if (!evolution_function_is_affine_p (chrec))
1580 37486057 : goto keep_cast;
1581 :
1582 6522358 : loop = get_chrec_loop (chrec);
1583 6522358 : base = CHREC_LEFT (chrec);
1584 6522358 : step = CHREC_RIGHT (chrec);
1585 :
1586 6522358 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1587 : use_overflow_semantics, from, nowrap_bound))
1588 4770561 : return build_polynomial_chrec (loop->num, base, step);
1589 :
1590 : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1591 1751797 : keep_cast:
1592 : /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1593 : may be more expensive. We do want to perform this optimization here
1594 : though for canonicalization reasons. */
1595 39237854 : if (use_overflow_semantics
1596 38582297 : && (TREE_CODE (chrec) == PLUS_EXPR
1597 38582297 : || TREE_CODE (chrec) == MINUS_EXPR)
1598 3768896 : && TREE_CODE (type) == INTEGER_TYPE
1599 3662169 : && TREE_CODE (ct) == INTEGER_TYPE
1600 3662123 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1601 39400195 : && TYPE_OVERFLOW_UNDEFINED (ct))
1602 48718 : res = fold_build2 (TREE_CODE (chrec), type,
1603 : fold_convert (type, TREE_OPERAND (chrec, 0)),
1604 : fold_convert (type, TREE_OPERAND (chrec, 1)));
1605 : /* Similar perform the trick that (signed char)((int)x + 2) can be
1606 : narrowed to (signed char)((unsigned char)x + 2). */
1607 39189136 : else if (use_overflow_semantics
1608 38533579 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1609 1789669 : && TREE_CODE (ct) == INTEGER_TYPE
1610 1777201 : && TREE_CODE (type) == INTEGER_TYPE
1611 1618067 : && TYPE_OVERFLOW_UNDEFINED (type)
1612 40554167 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1613 : {
1614 35228 : tree utype = unsigned_type_for (type);
1615 105684 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1616 35228 : fold_convert (utype,
1617 : CHREC_LEFT (chrec)),
1618 35228 : fold_convert (utype,
1619 : CHREC_RIGHT (chrec)));
1620 35228 : res = chrec_convert_1 (type, res, at_stmt, nowrap_bound,
1621 : use_overflow_semantics, from);
1622 : }
1623 : /* Similar perform the trick that (unsigned T)(base + step) can be
1624 : folded to ((unsigned T)x + (unsigned T)step). */
1625 39153908 : else if (use_overflow_semantics
1626 38498351 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1627 1754441 : && INTEGRAL_TYPE_P (ct)
1628 1742302 : && INTEGRAL_TYPE_P (type)
1629 1583193 : && TYPE_OVERFLOW_UNDEFINED (type)
1630 : /* Must be unsigned so we don't introduce any UB. */
1631 1330142 : && TYPE_UNSIGNED (type)
1632 : /* The outer type must at least as wide than the inner type so we
1633 : don't truncate when we fold and must the inner CHREC must be
1634 : non-wrapping so we don't change the behavior when folding to
1635 : a wider type. */
1636 0 : && TYPE_PRECISION (type) >= TYPE_PRECISION (ct)
1637 39153908 : && (!TYPE_UNSIGNED (ct)
1638 0 : || TYPE_PRECISION (type) == TYPE_PRECISION (ct)
1639 0 : || nonwrapping_chrec_p (chrec)))
1640 : {
1641 0 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1642 0 : fold_convert (type,
1643 : CHREC_LEFT (chrec)),
1644 0 : fold_convert (type,
1645 : CHREC_RIGHT (chrec)));
1646 0 : res = chrec_convert_1 (type, res, at_stmt, nowrap_bound,
1647 : use_overflow_semantics, from);
1648 : }
1649 : else
1650 39153908 : res = fold_convert (type, chrec);
1651 :
1652 : /* Don't propagate overflows. */
1653 39237854 : if (CONSTANT_CLASS_P (res))
1654 12496975 : TREE_OVERFLOW (res) = 0;
1655 :
1656 : /* But reject constants that don't fit in their type after conversion.
1657 : This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1658 : natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1659 : and can cause problems later when computing niters of loops. Note
1660 : that we don't do the check before converting because we don't want
1661 : to reject conversions of negative chrecs to unsigned types. */
1662 39237854 : if (TREE_CODE (res) == INTEGER_CST
1663 12496975 : && TREE_CODE (type) == INTEGER_TYPE
1664 12476946 : && !int_fits_type_p (res, type))
1665 5021 : res = chrec_dont_know;
1666 :
1667 : return res;
1668 : }
1669 :
1670 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1671 : which the CHREC is built, it sets AT_STMT to the statement that
1672 : contains the definition of the analyzed variable, otherwise the
1673 : conversion is less accurate: the information is used for
1674 : determining a more accurate estimation of the number of iterations.
1675 : By default AT_STMT could be safely set to NULL_TREE.
1676 :
1677 : The following rule is always true: TREE_TYPE (chrec) ==
1678 : TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1679 : An example of what could happen when adding two chrecs and the type
1680 : of the CHREC_RIGHT is different than CHREC_LEFT is:
1681 :
1682 : {(uint) 0, +, (uchar) 10} +
1683 : {(uint) 0, +, (uchar) 250}
1684 :
1685 : that would produce a wrong result if CHREC_RIGHT is not (uint):
1686 :
1687 : {(uint) 0, +, (uchar) 4}
1688 :
1689 : instead of
1690 :
1691 : {(uint) 0, +, (uint) 260}
1692 :
1693 : If NOWRAP_BOUND is nonzero it is used to store the bound below which
1694 : no wrapping occurs. Here as well as in many other similar functions,
1695 : it is just passed through to other functions and thus not documented
1696 : everywhere.
1697 :
1698 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1699 : the rules for overflow of the given language apply (e.g., that signed
1700 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1701 : unnecessary tests, but also to enforce that the result follows them.
1702 :
1703 : FROM is the source variable converted if it's not NULL. */
1704 :
1705 : tree
1706 164255625 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1707 : tree *nowrap_bound, bool use_overflow_semantics, tree from)
1708 : {
1709 164255625 : return chrec_convert_1 (type, chrec, at_stmt, nowrap_bound,
1710 164255625 : use_overflow_semantics, from);
1711 : }
1712 :
1713 : /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1714 : chrec if something else than what chrec_convert would do happens, NULL_TREE
1715 : otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1716 : if the result chrec may overflow. */
1717 :
1718 : tree
1719 8976894 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1720 : {
1721 8976894 : tree inner_type, left, right, lc, rc, rtype;
1722 :
1723 8976894 : gcc_assert (fold_conversions != NULL);
1724 :
1725 8976894 : if (automatically_generated_chrec_p (chrec)
1726 8976894 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1727 : return NULL_TREE;
1728 :
1729 697672 : inner_type = TREE_TYPE (chrec);
1730 697672 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1731 : return NULL_TREE;
1732 :
1733 609861 : if (useless_type_conversion_p (type, inner_type))
1734 : return NULL_TREE;
1735 :
1736 541495 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1737 : {
1738 540691 : tree base, step;
1739 540691 : class loop *loop;
1740 :
1741 540691 : loop = get_chrec_loop (chrec);
1742 540691 : base = CHREC_LEFT (chrec);
1743 540691 : step = CHREC_RIGHT (chrec);
1744 540691 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1745 2680 : return build_polynomial_chrec (loop->num, base, step);
1746 : }
1747 538815 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1748 :
1749 538815 : left = CHREC_LEFT (chrec);
1750 538815 : right = CHREC_RIGHT (chrec);
1751 538815 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1752 538815 : if (!lc)
1753 538815 : lc = chrec_convert (type, left, NULL);
1754 538815 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1755 538815 : if (!rc)
1756 538137 : rc = chrec_convert (rtype, right, NULL);
1757 :
1758 538815 : *fold_conversions = true;
1759 :
1760 538815 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1761 : }
1762 :
1763 : /* Returns true when CHREC0 == CHREC1. */
1764 :
1765 : bool
1766 13769462 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1767 : {
1768 13802555 : if (chrec0 == NULL_TREE
1769 13802555 : || chrec1 == NULL_TREE
1770 13802555 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1771 : return false;
1772 :
1773 12823867 : if (operand_equal_p (chrec0, chrec1, 0))
1774 : return true;
1775 :
1776 9515557 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1777 : return false;
1778 :
1779 9513327 : switch (TREE_CODE (chrec0))
1780 : {
1781 3909251 : case POLYNOMIAL_CHREC:
1782 3909251 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1783 3908872 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1784 4260813 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1785 :
1786 55086 : case PLUS_EXPR:
1787 55086 : case MULT_EXPR:
1788 55086 : case MINUS_EXPR:
1789 55086 : case POINTER_PLUS_EXPR:
1790 55086 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1791 55086 : TREE_OPERAND (chrec1, 0))
1792 96149 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1793 41063 : TREE_OPERAND (chrec1, 1));
1794 :
1795 33093 : CASE_CONVERT:
1796 33093 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1797 66186 : TREE_OPERAND (chrec1, 0));
1798 :
1799 : default:
1800 : return false;
1801 : }
1802 : }
1803 :
1804 : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1805 : EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1806 : which of these cases happens. */
1807 :
1808 : enum ev_direction
1809 3333403 : scev_direction (const_tree chrec)
1810 : {
1811 3333403 : const_tree step;
1812 :
1813 3333403 : if (!evolution_function_is_affine_p (chrec))
1814 : return EV_DIR_UNKNOWN;
1815 :
1816 3327768 : step = CHREC_RIGHT (chrec);
1817 3327768 : if (TREE_CODE (step) != INTEGER_CST)
1818 : return EV_DIR_UNKNOWN;
1819 :
1820 3228188 : if (tree_int_cst_sign_bit (step))
1821 : return EV_DIR_DECREASES;
1822 : else
1823 2900339 : return EV_DIR_GROWS;
1824 : }
1825 :
1826 : /* Iterates over all the components of SCEV, and calls CBCK. */
1827 :
1828 : void
1829 0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1830 : {
1831 0 : switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1832 : {
1833 0 : case 3:
1834 0 : for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1835 : /* FALLTHRU */
1836 :
1837 0 : case 2:
1838 0 : for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1839 : /* FALLTHRU */
1840 :
1841 0 : case 1:
1842 0 : for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1843 : /* FALLTHRU */
1844 :
1845 0 : default:
1846 0 : cbck (scev, data);
1847 0 : break;
1848 : }
1849 0 : }
1850 :
1851 : /* Returns true when the operation can be part of a linear
1852 : expression. */
1853 :
1854 : static inline bool
1855 34371 : operator_is_linear (tree scev)
1856 : {
1857 34371 : switch (TREE_CODE (scev))
1858 : {
1859 : case INTEGER_CST:
1860 : case POLYNOMIAL_CHREC:
1861 : case PLUS_EXPR:
1862 : case POINTER_PLUS_EXPR:
1863 : case MULT_EXPR:
1864 : case MINUS_EXPR:
1865 : case NEGATE_EXPR:
1866 : case SSA_NAME:
1867 : case NON_LVALUE_EXPR:
1868 : case BIT_NOT_EXPR:
1869 : CASE_CONVERT:
1870 : return true;
1871 :
1872 8 : default:
1873 8 : return false;
1874 : }
1875 : }
1876 :
1877 : /* Return true when SCEV is a linear expression. Linear expressions
1878 : can contain additions, substractions and multiplications.
1879 : Multiplications are restricted to constant scaling: "cst * x". */
1880 :
1881 : bool
1882 78394 : scev_is_linear_expression (tree scev)
1883 : {
1884 161454 : if (evolution_function_is_constant_p (scev))
1885 : return true;
1886 :
1887 34371 : if (scev == NULL
1888 34371 : || !operator_is_linear (scev))
1889 : return false;
1890 :
1891 34363 : if (TREE_CODE (scev) == MULT_EXPR)
1892 670 : return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1893 0 : && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1894 :
1895 33693 : if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1896 33693 : && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1897 : return false;
1898 :
1899 33483 : switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1900 : {
1901 0 : case 3:
1902 0 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1903 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1904 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1905 :
1906 24663 : case 2:
1907 24663 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1908 24663 : && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1909 :
1910 2333 : case 1:
1911 2333 : return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1912 :
1913 : case 0:
1914 : return true;
1915 :
1916 : default:
1917 : return false;
1918 : }
1919 : }
1920 :
1921 : /* Determines whether the expression CHREC contains only integer consts
1922 : in the right parts. */
1923 :
1924 : bool
1925 4319 : evolution_function_right_is_integer_cst (const_tree chrec)
1926 : {
1927 4319 : if (chrec == NULL_TREE)
1928 : return false;
1929 :
1930 4319 : switch (TREE_CODE (chrec))
1931 : {
1932 : case INTEGER_CST:
1933 : return true;
1934 :
1935 4319 : case POLYNOMIAL_CHREC:
1936 4319 : return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1937 4319 : && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1938 470 : || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1939 :
1940 0 : CASE_CONVERT:
1941 0 : return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1942 :
1943 : default:
1944 : return false;
1945 : }
1946 : }
|