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 87658 : chrec_fold_plus_poly_poly (enum tree_code code,
49 : tree type,
50 : tree poly0,
51 : tree poly1)
52 : {
53 87658 : tree left, right;
54 87658 : class loop *loop0 = get_chrec_loop (poly0);
55 87658 : class loop *loop1 = get_chrec_loop (poly1);
56 :
57 87658 : gcc_assert (poly0);
58 87658 : gcc_assert (poly1);
59 87658 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
60 87658 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
61 87658 : 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 86792 : 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 87658 : if (flow_loop_nested_p (loop0, loop1))
73 : {
74 296 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
75 232 : return build_polynomial_chrec
76 232 : (CHREC_VARIABLE (poly1),
77 232 : chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
78 464 : CHREC_RIGHT (poly1));
79 : else
80 64 : return build_polynomial_chrec
81 128 : (CHREC_VARIABLE (poly1),
82 64 : chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
83 64 : chrec_fold_multiply (type, CHREC_RIGHT (poly1),
84 64 : SCALAR_FLOAT_TYPE_P (type)
85 0 : ? build_real (type, dconstm1)
86 128 : : build_int_cst_type (type, -1)));
87 : }
88 :
89 87362 : if (flow_loop_nested_p (loop1, loop0))
90 : {
91 602 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
92 556 : return build_polynomial_chrec
93 556 : (CHREC_VARIABLE (poly0),
94 556 : chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
95 1112 : CHREC_RIGHT (poly0));
96 : else
97 46 : return build_polynomial_chrec
98 46 : (CHREC_VARIABLE (poly0),
99 46 : chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
100 92 : CHREC_RIGHT (poly0));
101 : }
102 :
103 : /* This function should never be called for chrecs of loops that
104 : do not belong to the same loop nest. */
105 86760 : 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 86722 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
113 : {
114 31764 : tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
115 31764 : left = chrec_fold_plus
116 31764 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117 31764 : right = chrec_fold_plus
118 31764 : (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119 : }
120 : else
121 : {
122 54958 : left = chrec_fold_minus
123 54958 : (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124 54958 : right = chrec_fold_minus
125 54958 : (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126 : }
127 :
128 86722 : 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 32429 : else if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
137 21557 : && TREE_CODE (right) == INTEGER_CST
138 35354 : && TREE_OVERFLOW (right))
139 5 : return chrec_dont_know;
140 : else
141 32544 : return build_polynomial_chrec
142 32544 : (CHREC_VARIABLE (poly0), left, right);
143 : }
144 :
145 :
146 :
147 : /* Fold the multiplication of two polynomial functions. */
148 :
149 : static inline tree
150 40341 : chrec_fold_multiply_poly_poly (tree type,
151 : tree poly0,
152 : tree poly1)
153 : {
154 40341 : tree t0, t1, t2;
155 40341 : int var;
156 40341 : class loop *loop0 = get_chrec_loop (poly0);
157 40341 : class loop *loop1 = get_chrec_loop (poly1);
158 :
159 40341 : gcc_assert (poly0);
160 40341 : gcc_assert (poly1);
161 40341 : gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
162 40341 : gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
163 40341 : 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 40341 : 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 40341 : 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 40341 : 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 40341 : t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
195 :
196 : /* "a*d + b*c". */
197 40341 : t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
198 121023 : t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
199 40341 : CHREC_RIGHT (poly0),
200 40341 : CHREC_LEFT (poly1)));
201 : /* "b*d". */
202 40341 : t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
203 : /* "a*d + b*c + b*d". */
204 40341 : t1 = chrec_fold_plus (type, t1, t2);
205 : /* "2*b*d". */
206 80682 : t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
207 33 : ? build_real (type, dconst2)
208 40308 : : build_int_cst (type, 2), t2);
209 :
210 40341 : var = CHREC_VARIABLE (poly0);
211 40341 : return build_polynomial_chrec (var, t0,
212 40341 : 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 5856255 : chrec_fold_automatically_generated_operands (tree op0,
220 : tree op1)
221 : {
222 5856255 : if (op0 == chrec_dont_know
223 948132 : || 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 30949900 : chrec_fold_plus_1 (enum tree_code code, tree type,
242 : tree op0, tree op1)
243 : {
244 61899800 : if (automatically_generated_chrec_p (op0)
245 30949900 : || automatically_generated_chrec_p (op1))
246 0 : return chrec_fold_automatically_generated_operands (op0, op1);
247 :
248 30949900 : switch (TREE_CODE (op0))
249 : {
250 9699050 : case POLYNOMIAL_CHREC:
251 9699050 : gcc_checking_assert
252 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
253 9699050 : switch (TREE_CODE (op1))
254 : {
255 87658 : case POLYNOMIAL_CHREC:
256 87658 : gcc_checking_assert
257 : (!chrec_contains_symbols_defined_in_loop (op1,
258 : CHREC_VARIABLE (op1)));
259 87658 : return chrec_fold_plus_poly_poly (code, type, op0, op1);
260 :
261 162612 : CASE_CONVERT:
262 162612 : if (tree_contains_chrecs (op1, NULL))
263 : {
264 : /* We can strip sign-conversions to signed by performing the
265 : operation in unsigned. */
266 673 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
267 673 : if (INTEGRAL_TYPE_P (type)
268 673 : && INTEGRAL_TYPE_P (optype)
269 648 : && tree_nop_conversion_p (type, optype)
270 862 : && TYPE_UNSIGNED (optype))
271 : {
272 71 : tree tem = chrec_convert (optype, op0, NULL);
273 71 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
274 16 : return chrec_convert (type,
275 : chrec_fold_plus_1 (code, optype,
276 : tem,
277 16 : TREE_OPERAND
278 : (op1, 0)),
279 16 : NULL);
280 : }
281 657 : return chrec_dont_know;
282 : }
283 : /* FALLTHRU */
284 :
285 9610719 : default:
286 9610719 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
287 8831010 : return build_polynomial_chrec
288 8831010 : (CHREC_VARIABLE (op0),
289 8831010 : chrec_fold_plus (type, CHREC_LEFT (op0), op1),
290 17662020 : CHREC_RIGHT (op0));
291 : else
292 779709 : return build_polynomial_chrec
293 779709 : (CHREC_VARIABLE (op0),
294 779709 : chrec_fold_minus (type, CHREC_LEFT (op0), op1),
295 1559418 : CHREC_RIGHT (op0));
296 : }
297 :
298 3245371 : CASE_CONVERT:
299 3245371 : if (tree_contains_chrecs (op0, NULL))
300 : {
301 : /* We can strip sign-conversions to signed by performing the
302 : operation in unsigned. */
303 40617 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
304 40617 : if (INTEGRAL_TYPE_P (type)
305 39220 : && INTEGRAL_TYPE_P (optype)
306 35183 : && tree_nop_conversion_p (type, optype)
307 66000 : && TYPE_UNSIGNED (optype))
308 50698 : return chrec_convert (type,
309 : chrec_fold_plus_1 (code, optype,
310 25349 : TREE_OPERAND (op0, 0),
311 : chrec_convert (optype,
312 : op1, NULL)),
313 25349 : NULL);
314 15268 : return chrec_dont_know;
315 : }
316 : /* FALLTHRU */
317 :
318 21210233 : default:
319 21210233 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
320 21210233 : switch (TREE_CODE (op1))
321 : {
322 3098535 : case POLYNOMIAL_CHREC:
323 3098535 : gcc_checking_assert
324 : (!chrec_contains_symbols_defined_in_loop (op1,
325 : CHREC_VARIABLE (op1)));
326 3098535 : if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
327 3031429 : return build_polynomial_chrec
328 3031429 : (CHREC_VARIABLE (op1),
329 3031429 : chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
330 6062858 : CHREC_RIGHT (op1));
331 : else
332 67106 : return build_polynomial_chrec
333 134212 : (CHREC_VARIABLE (op1),
334 67106 : chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
335 67106 : chrec_fold_multiply (type, CHREC_RIGHT (op1),
336 67106 : SCALAR_FLOAT_TYPE_P (type)
337 4 : ? build_real (type, dconstm1)
338 134208 : : build_int_cst_type (type, -1)));
339 :
340 2313456 : CASE_CONVERT:
341 2313456 : if (tree_contains_chrecs (op1, NULL))
342 : {
343 : /* We can strip sign-conversions to signed by performing the
344 : operation in unsigned. */
345 56070 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
346 56070 : if (INTEGRAL_TYPE_P (type)
347 21151 : && INTEGRAL_TYPE_P (optype)
348 21151 : && tree_nop_conversion_p (type, optype)
349 73031 : && TYPE_UNSIGNED (optype))
350 16961 : return chrec_convert (type,
351 : chrec_fold_plus_1 (code, optype,
352 : chrec_convert (optype,
353 : op0,
354 : NULL),
355 16961 : TREE_OPERAND (op1, 0)),
356 16961 : NULL);
357 39109 : return chrec_dont_know;
358 : }
359 : /* FALLTHRU */
360 :
361 18055628 : default:
362 18055628 : {
363 18055628 : int size = 0;
364 18055628 : if ((tree_contains_chrecs (op0, &size)
365 18055628 : || tree_contains_chrecs (op1, &size))
366 18055628 : && size < param_scev_max_expr_size)
367 0 : return build2 (code, type, op0, op1);
368 18055628 : else if (size < param_scev_max_expr_size)
369 : {
370 18055527 : if (code == POINTER_PLUS_EXPR)
371 3462242 : return fold_build_pointer_plus (fold_convert (type, op0),
372 : op1);
373 : else
374 14593285 : return fold_build2 (code, type,
375 : fold_convert (type, op0),
376 : fold_convert (type, op1));
377 : }
378 : else
379 101 : return chrec_dont_know;
380 : }
381 : }
382 : }
383 : }
384 :
385 : /* Fold the addition of two chrecs. */
386 :
387 : tree
388 37169827 : chrec_fold_plus (tree type,
389 : tree op0,
390 : tree op1)
391 : {
392 37169827 : enum tree_code code;
393 71421857 : if (automatically_generated_chrec_p (op0)
394 37169827 : || automatically_generated_chrec_p (op1))
395 3572342 : return chrec_fold_automatically_generated_operands (op0, op1);
396 :
397 33597485 : if (integer_zerop (op0))
398 4060131 : return chrec_convert (type, op1, NULL);
399 29537354 : if (integer_zerop (op1))
400 1856712 : return chrec_convert (type, op0, NULL);
401 :
402 27680642 : if (POINTER_TYPE_P (type))
403 : code = POINTER_PLUS_EXPR;
404 : else
405 21318023 : code = PLUS_EXPR;
406 :
407 27680642 : return chrec_fold_plus_1 (code, type, op0, op1);
408 : }
409 :
410 : /* Fold the subtraction of two chrecs. */
411 :
412 : tree
413 4042421 : chrec_fold_minus (tree type,
414 : tree op0,
415 : tree op1)
416 : {
417 7503296 : if (automatically_generated_chrec_p (op0)
418 4042421 : || automatically_generated_chrec_p (op1))
419 717596 : return chrec_fold_automatically_generated_operands (op0, op1);
420 :
421 3324825 : if (integer_zerop (op1))
422 : return op0;
423 :
424 3226932 : return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
425 : }
426 :
427 : /* Fold the multiplication of two chrecs. */
428 :
429 : tree
430 21686551 : chrec_fold_multiply (tree type,
431 : tree op0,
432 : tree op1)
433 : {
434 21686975 : if (automatically_generated_chrec_p (op0)
435 20278195 : || automatically_generated_chrec_p (op1))
436 1566317 : return chrec_fold_automatically_generated_operands (op0, op1);
437 :
438 20120658 : if (TREE_CODE (op0) != POLYNOMIAL_CHREC
439 16175434 : && TREE_CODE (op1) == POLYNOMIAL_CHREC)
440 : std::swap (op0, op1);
441 :
442 20120658 : switch (TREE_CODE (op0))
443 : {
444 4141333 : case POLYNOMIAL_CHREC:
445 4141333 : gcc_checking_assert
446 : (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
447 4141333 : switch (TREE_CODE (op1))
448 : {
449 40341 : case POLYNOMIAL_CHREC:
450 40341 : gcc_checking_assert
451 : (!chrec_contains_symbols_defined_in_loop (op1,
452 : CHREC_VARIABLE (op1)));
453 40341 : return chrec_fold_multiply_poly_poly (type, op0, op1);
454 :
455 63559 : CASE_CONVERT:
456 63559 : if (tree_contains_chrecs (op1, NULL))
457 : {
458 : /* We can strip sign-conversions to signed by performing the
459 : operation in unsigned. */
460 219 : tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
461 219 : if (INTEGRAL_TYPE_P (type)
462 219 : && INTEGRAL_TYPE_P (optype)
463 219 : && tree_nop_conversion_p (type, optype)
464 235 : && TYPE_UNSIGNED (optype))
465 : {
466 16 : tree tem = chrec_convert (optype, op0, NULL);
467 16 : if (TREE_CODE (tem) == POLYNOMIAL_CHREC)
468 16 : return chrec_convert (type,
469 : chrec_fold_multiply (optype, tem,
470 16 : TREE_OPERAND
471 : (op1, 0)),
472 16 : NULL);
473 : }
474 203 : return chrec_dont_know;
475 : }
476 : /* FALLTHRU */
477 :
478 4100773 : default:
479 4100773 : if (integer_onep (op1))
480 : return op0;
481 4100322 : 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 4099912 : if (INTEGRAL_TYPE_P (type)
491 4099719 : && TYPE_OVERFLOW_UNDEFINED (type)
492 1063904 : && !integer_zerop (CHREC_LEFT (op0))
493 605751 : && TREE_CODE (op1) == INTEGER_CST
494 4529002 : && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST)
495 : {
496 337137 : wi::overflow_type ovf = wi::OVF_NONE;
497 337137 : wide_int res
498 337137 : = wi::mul (wi::to_wide (CHREC_RIGHT (op0)),
499 674274 : wi::to_wide (op1), TYPE_SIGN (type), &ovf);
500 337137 : 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 337137 : }
513 4099876 : tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
514 4099876 : tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
515 4099876 : return build_polynomial_chrec (CHREC_VARIABLE (op0), left, right);
516 : }
517 :
518 4630880 : CASE_CONVERT:
519 4630880 : if (tree_contains_chrecs (op0, NULL))
520 : {
521 : /* We can strip sign-conversions to signed by performing the
522 : operation in unsigned. */
523 52897 : tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
524 52897 : if (INTEGRAL_TYPE_P (type)
525 52897 : && INTEGRAL_TYPE_P (optype)
526 52897 : && tree_nop_conversion_p (type, optype)
527 64702 : && TYPE_UNSIGNED (optype))
528 23560 : return chrec_convert (type,
529 : chrec_fold_multiply (optype,
530 11780 : TREE_OPERAND (op0, 0),
531 : chrec_convert (optype,
532 : op1,
533 : NULL)),
534 11780 : NULL);
535 41117 : return chrec_dont_know;
536 : }
537 : /* FALLTHRU */
538 :
539 15926428 : default:
540 15926428 : gcc_checking_assert (!tree_contains_chrecs (op0, NULL));
541 15926428 : if (integer_onep (op0))
542 : return op1;
543 :
544 10960583 : if (integer_zerop (op0))
545 2304451 : return build_int_cst (type, 0);
546 :
547 8656132 : switch (TREE_CODE (op1))
548 : {
549 0 : case POLYNOMIAL_CHREC:
550 0 : gcc_unreachable ();
551 :
552 1348113 : CASE_CONVERT:
553 1348113 : if (tree_contains_chrecs (op1, NULL))
554 : return chrec_fold_multiply (type, op1, op0);
555 : /* FALLTHRU */
556 :
557 8655708 : default:
558 8655708 : if (integer_onep (op1))
559 : return op0;
560 8590649 : if (integer_zerop (op1))
561 1465 : return build_int_cst (type, 0);
562 8589184 : 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 11826 : tree_fold_binomial (tree type, tree n, unsigned int k)
576 : {
577 11826 : wi::overflow_type overflow;
578 11826 : unsigned int i;
579 :
580 : /* Handle the most frequent cases. */
581 11826 : if (k == 0)
582 3917 : return build_int_cst (type, 1);
583 7909 : if (k == 1)
584 3917 : return fold_convert (type, n);
585 :
586 3992 : widest_int num = wi::to_widest (n);
587 :
588 : /* Check that k <= n. */
589 3992 : if (wi::ltu_p (num, k))
590 : return NULL_TREE;
591 :
592 : /* Denominator = 2. */
593 3933 : widest_int denom = 2;
594 :
595 : /* Index = Numerator-1. */
596 3933 : widest_int idx = num - 1;
597 :
598 : /* Numerator = Numerator*Index = n*(n-1). */
599 3933 : num = wi::smul (num, idx, &overflow);
600 3933 : if (overflow)
601 : return NULL_TREE;
602 :
603 3939 : 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 3933 : num = wi::udiv_trunc (num, denom);
619 3933 : if (! wi::fits_to_tree_p (num, type))
620 : return NULL_TREE;
621 3923 : return wide_int_to_tree (type, num);
622 7925 : }
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 11973 : chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
630 : {
631 11973 : tree arg0, arg1, binomial_n_k;
632 11973 : tree type = TREE_TYPE (chrec);
633 11973 : class loop *var_loop = get_loop (cfun, var);
634 :
635 11973 : while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
636 11973 : && 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 11973 : tree ctype = type;
642 11973 : if (INTEGRAL_TYPE_P (type)
643 11973 : && ! TYPE_OVERFLOW_WRAPS (type))
644 11655 : ctype = unsigned_type_for (type);
645 :
646 11973 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
647 11973 : && CHREC_VARIABLE (chrec) == var)
648 : {
649 7987 : arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
650 7987 : if (arg1 == chrec_dont_know)
651 : return chrec_dont_know;
652 7840 : binomial_n_k = tree_fold_binomial (ctype, n, k);
653 7840 : if (!binomial_n_k)
654 0 : return chrec_dont_know;
655 7840 : tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
656 7840 : arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
657 7840 : return chrec_fold_plus (ctype, arg0, arg1);
658 : }
659 :
660 3986 : binomial_n_k = tree_fold_binomial (ctype, n, k);
661 3986 : if (!binomial_n_k)
662 69 : return chrec_dont_know;
663 :
664 3917 : 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 893592 : chrec_apply (unsigned var,
681 : tree chrec,
682 : tree x)
683 : {
684 893592 : tree type = chrec_type (chrec);
685 893592 : tree res = chrec_dont_know;
686 :
687 1787184 : if (automatically_generated_chrec_p (chrec)
688 1001053 : || 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 893592 : || chrec_contains_symbols_defined_in_loop (chrec, var))
694 107461 : return chrec_dont_know;
695 :
696 786131 : if (dump_file && (dump_flags & TDF_SCEV))
697 0 : fprintf (dump_file, "(chrec_apply \n");
698 :
699 786131 : if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
700 124 : x = build_real_from_int_cst (type, x);
701 :
702 786131 : switch (TREE_CODE (chrec))
703 : {
704 784728 : case POLYNOMIAL_CHREC:
705 784728 : if (evolution_function_is_affine_p (chrec))
706 : {
707 779455 : tree chrecr = CHREC_RIGHT (chrec);
708 779455 : tree chrecl = CHREC_LEFT (chrec);
709 779455 : 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 778929 : else if (operand_equal_p (chrecl, chrecr)
716 136280 : && TREE_CODE (x) == PLUS_EXPR
717 6984 : && integer_all_onesp (TREE_OPERAND (x, 1))
718 6711 : && !POINTER_TYPE_P (type)
719 785629 : && TYPE_PRECISION (TREE_TYPE (x))
720 6700 : >= TYPE_PRECISION (type))
721 : {
722 : /* We know the number of iterations can't be negative. */
723 4859 : res = build_int_cst (TREE_TYPE (x), 1);
724 4859 : res = chrec_fold_plus (TREE_TYPE (x), x, res);
725 4859 : res = chrec_convert_rhs (type, res, NULL);
726 4859 : 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 774070 : tree utype = TREE_TYPE (chrecr);
735 774070 : if (INTEGRAL_TYPE_P (utype) && !TYPE_OVERFLOW_WRAPS (utype))
736 681567 : utype = unsigned_type_for (TREE_TYPE (chrecr));
737 774070 : res = chrec_convert_rhs (utype, x, NULL);
738 774070 : 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 774070 : if (TREE_CODE (res) == INTEGER_CST
744 774070 : && int_fits_type_p (res, TREE_TYPE (chrecr)))
745 : {
746 399020 : res = chrec_convert (TREE_TYPE (chrecr), res, NULL);
747 399020 : res = chrec_fold_plus (type, chrecl, res);
748 : }
749 : else
750 : {
751 375050 : res = chrec_fold_plus (utype,
752 : chrec_convert (utype, chrecl, NULL),
753 : res);
754 375050 : res = chrec_convert (type, res, NULL);
755 : }
756 : }
757 : }
758 5273 : else if (TREE_CODE (x) == INTEGER_CST
759 5273 : && tree_int_cst_sgn (x) == 1)
760 : /* testsuite/.../ssa-chrec-38.c. */
761 3986 : res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
762 : else
763 1287 : res = chrec_dont_know;
764 : break;
765 :
766 246 : CASE_CONVERT:
767 246 : res = chrec_convert (TREE_TYPE (chrec),
768 246 : chrec_apply (var, TREE_OPERAND (chrec, 0), x),
769 : NULL);
770 246 : break;
771 :
772 : default:
773 : res = chrec;
774 : break;
775 : }
776 :
777 786131 : if (dump_file && (dump_flags & TDF_SCEV))
778 : {
779 0 : fprintf (dump_file, " (varying_loop = %d", var);
780 0 : fprintf (dump_file, ")\n (chrec = ");
781 0 : print_generic_expr (dump_file, chrec);
782 0 : fprintf (dump_file, ")\n (x = ");
783 0 : print_generic_expr (dump_file, x);
784 0 : fprintf (dump_file, ")\n (res = ");
785 0 : print_generic_expr (dump_file, res);
786 0 : fprintf (dump_file, "))\n");
787 : }
788 :
789 : return res;
790 : }
791 :
792 : /* For a given CHREC and an induction variable map IV_MAP that maps
793 : (loop->num, expr) for every loop number of the current_loops an
794 : expression, calls chrec_apply when the expression is not NULL. */
795 :
796 : tree
797 888 : chrec_apply_map (tree chrec, vec<tree> iv_map)
798 : {
799 888 : int i;
800 888 : tree expr;
801 :
802 9821 : FOR_EACH_VEC_ELT (iv_map, i, expr)
803 8933 : if (expr)
804 1591 : chrec = chrec_apply (i, chrec, expr);
805 :
806 888 : return chrec;
807 : }
808 :
809 : /* Replaces the initial condition in CHREC with INIT_COND. */
810 :
811 : tree
812 2280992 : chrec_replace_initial_condition (tree chrec,
813 : tree init_cond)
814 : {
815 2280992 : if (automatically_generated_chrec_p (chrec))
816 : return chrec;
817 :
818 2280992 : gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
819 :
820 2280992 : switch (TREE_CODE (chrec))
821 : {
822 1150767 : case POLYNOMIAL_CHREC:
823 1150767 : return build_polynomial_chrec
824 1150767 : (CHREC_VARIABLE (chrec),
825 1150767 : chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
826 2301534 : 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 11165286 : initial_condition (tree chrec)
837 : {
838 18339669 : if (automatically_generated_chrec_p (chrec))
839 : return chrec;
840 :
841 17103813 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
842 7174383 : 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 48014865 : hide_evolution_in_other_loops_than_loop (tree chrec,
852 : unsigned loop_num)
853 : {
854 48017604 : class loop *loop = get_loop (cfun, loop_num), *chloop;
855 48017604 : if (automatically_generated_chrec_p (chrec))
856 : return chrec;
857 :
858 48017604 : switch (TREE_CODE (chrec))
859 : {
860 2466238 : case POLYNOMIAL_CHREC:
861 2466238 : chloop = get_chrec_loop (chrec);
862 :
863 2466238 : if (chloop == loop)
864 1995070 : return build_polynomial_chrec
865 1995070 : (loop_num,
866 1995070 : hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
867 : loop_num),
868 3990140 : CHREC_RIGHT (chrec));
869 :
870 471168 : else if (flow_loop_nested_p (chloop, loop))
871 : /* There is no evolution in this loop. */
872 468429 : return initial_condition (chrec);
873 :
874 2739 : else if (flow_loop_nested_p (loop, chloop))
875 2739 : return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
876 2739 : 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 42463247 : chrec_component_in_loop_num (tree chrec,
891 : unsigned loop_num,
892 : bool right)
893 : {
894 42463247 : tree component;
895 42463247 : class loop *loop = get_loop (cfun, loop_num), *chloop;
896 :
897 42463247 : if (automatically_generated_chrec_p (chrec))
898 : return chrec;
899 :
900 41227391 : switch (TREE_CODE (chrec))
901 : {
902 35579489 : case POLYNOMIAL_CHREC:
903 35579489 : chloop = get_chrec_loop (chrec);
904 :
905 35579489 : if (chloop == loop)
906 : {
907 34247549 : if (right)
908 17438005 : component = CHREC_RIGHT (chrec);
909 : else
910 16809544 : component = CHREC_LEFT (chrec);
911 :
912 34247549 : if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
913 34247549 : || 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 1331940 : 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 1331940 : gcc_assert (flow_loop_nested_p (loop, chloop));
932 1331940 : return chrec_component_in_loop_num (CHREC_LEFT (chrec),
933 : loop_num,
934 1331940 : right);
935 : }
936 :
937 5647902 : default:
938 5647902 : if (right)
939 : return NULL_TREE;
940 : else
941 : 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 23478698 : evolution_part_in_loop_num (tree chrec,
951 : unsigned loop_num)
952 : {
953 23478698 : 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 17652609 : initial_condition_in_loop_num (tree chrec,
962 : unsigned loop_num)
963 : {
964 17652609 : 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 16304852 : chrec_merge (tree chrec1,
1006 : tree chrec2)
1007 : {
1008 16304852 : if (chrec1 == chrec_dont_know
1009 16304852 : || chrec2 == chrec_dont_know)
1010 : return chrec_dont_know;
1011 :
1012 13658705 : if (chrec1 == chrec_known
1013 13658705 : || chrec2 == chrec_known)
1014 : return chrec_known;
1015 :
1016 13658705 : if (chrec1 == chrec_not_analyzed_yet)
1017 : return chrec2;
1018 2873636 : if (chrec2 == chrec_not_analyzed_yet)
1019 : return chrec1;
1020 :
1021 2873636 : if (eq_evolutions_p (chrec1, chrec2))
1022 : return chrec1;
1023 :
1024 2319503 : 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 37350501 : chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
1073 : class loop *loop)
1074 : {
1075 37350501 : int i, n;
1076 :
1077 37350501 : if (chrec == NULL_TREE)
1078 : return false;
1079 :
1080 37350501 : 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 31635688 : if (loop != NULL
1091 600 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1092 31635890 : && flow_loop_nested_p (get_chrec_loop (chrec), loop))
1093 : return true;
1094 :
1095 31635688 : if (visited.add (chrec))
1096 : return false;
1097 :
1098 31002380 : n = TREE_OPERAND_LENGTH (chrec);
1099 79807715 : for (i = 0; i < n; i++)
1100 21754891 : 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 15595610 : chrec_contains_symbols (const_tree chrec, class loop* loop)
1112 : {
1113 15595610 : hash_set<const_tree> visited;
1114 15595610 : return chrec_contains_symbols (chrec, visited, loop);
1115 15595610 : }
1116 :
1117 : /* Return true when CHREC contains symbolic names defined in
1118 : LOOP_NB. */
1119 :
1120 : static bool
1121 338200987 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1122 : hash_set<const_tree> &visited)
1123 : {
1124 338200987 : int i, n;
1125 :
1126 338200987 : if (chrec == NULL_TREE)
1127 : return false;
1128 :
1129 338065519 : if (is_gimple_min_invariant (chrec))
1130 : return false;
1131 :
1132 199822293 : if (TREE_CODE (chrec) == SSA_NAME)
1133 : {
1134 72126710 : gimple *def;
1135 72126710 : loop_p def_loop, loop;
1136 :
1137 72126710 : if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1138 : return false;
1139 :
1140 67763147 : def = SSA_NAME_DEF_STMT (chrec);
1141 67763147 : def_loop = loop_containing_stmt (def);
1142 67763147 : loop = get_loop (cfun, loop_nb);
1143 :
1144 67763147 : if (def_loop == NULL)
1145 : return false;
1146 :
1147 67763147 : if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1148 4457853 : return true;
1149 :
1150 : return false;
1151 : }
1152 :
1153 127695583 : if (visited.add (chrec))
1154 : return false;
1155 :
1156 127653608 : n = TREE_OPERAND_LENGTH (chrec);
1157 467067910 : for (i = 0; i < n; i++)
1158 213072666 : 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 125128321 : chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1169 : {
1170 125128321 : hash_set<const_tree> visited;
1171 125128321 : return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1172 125128321 : }
1173 :
1174 : /* Determines whether the chrec contains undetermined coefficients. */
1175 :
1176 : static bool
1177 225859149 : chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1178 : {
1179 225859149 : int i, n;
1180 :
1181 225859149 : if (chrec == chrec_dont_know)
1182 : return true;
1183 :
1184 203110065 : if (chrec == NULL_TREE)
1185 : return false;
1186 :
1187 202747565 : if (visited.add (chrec))
1188 : return false;
1189 :
1190 189451912 : n = TREE_OPERAND_LENGTH (chrec);
1191 503352943 : for (i = 0; i < n; i++)
1192 124450301 : if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1193 : return true;
1194 : return false;
1195 : }
1196 :
1197 : bool
1198 101408848 : chrec_contains_undetermined (const_tree chrec)
1199 : {
1200 101408848 : hash_set<const_tree> visited;
1201 101408848 : return chrec_contains_undetermined (chrec, visited);
1202 101408848 : }
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 444805702 : tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1210 : {
1211 444805702 : int i, n;
1212 :
1213 444805702 : if (expr == NULL_TREE)
1214 : return false;
1215 :
1216 443714603 : if (size)
1217 79321459 : (*size)++;
1218 :
1219 444078561 : if (tree_is_chrec (expr))
1220 : return true;
1221 :
1222 420801965 : if (visited.add (expr))
1223 : return false;
1224 :
1225 418285497 : n = TREE_OPERAND_LENGTH (expr);
1226 1052780589 : for (i = 0; i < n; i++)
1227 216495885 : if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1228 : return true;
1229 : return false;
1230 : }
1231 :
1232 : bool
1233 228309817 : tree_contains_chrecs (const_tree expr, int *size)
1234 : {
1235 228309817 : hash_set<const_tree> visited;
1236 228309817 : return tree_contains_chrecs (expr, size, visited);
1237 228309817 : }
1238 :
1239 :
1240 : /* Recursive helper function. */
1241 :
1242 : static bool
1243 45771746 : evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1244 : {
1245 91543492 : if (evolution_function_is_constant_p (chrec))
1246 : return true;
1247 :
1248 9904184 : if (TREE_CODE (chrec) == SSA_NAME
1249 9904184 : && (loopnum == 0
1250 2165068 : || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1251 2142202 : return true;
1252 :
1253 7761982 : if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1254 : {
1255 6112089 : if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1256 132355 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1257 132355 : get_chrec_loop (chrec))
1258 3246 : || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1259 : loopnum)
1260 6115335 : || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1261 : loopnum))
1262 6108843 : return false;
1263 : return true;
1264 : }
1265 :
1266 1649893 : switch (TREE_OPERAND_LENGTH (chrec))
1267 : {
1268 922221 : case 2:
1269 922221 : if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1270 : loopnum))
1271 : return false;
1272 : /* FALLTHRU */
1273 :
1274 1584791 : case 1:
1275 1584791 : 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 30811960 : evolution_function_is_invariant_p (tree chrec, int loopnum)
1289 : {
1290 30811960 : 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 6767365 : evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1298 : {
1299 6767365 : if (chrec == NULL_TREE)
1300 : return false;
1301 :
1302 6767365 : switch (TREE_CODE (chrec))
1303 : {
1304 6223141 : case POLYNOMIAL_CHREC:
1305 6223141 : if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1306 : {
1307 6122115 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1308 : return true;
1309 : else
1310 : {
1311 203 : if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1312 203 : && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1313 203 : != CHREC_VARIABLE (chrec)
1314 203 : && evolution_function_is_affine_multivariate_p
1315 0 : (CHREC_RIGHT (chrec), loopnum))
1316 : return true;
1317 : else
1318 203 : return false;
1319 : }
1320 : }
1321 : else
1322 : {
1323 101026 : if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1324 101026 : && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1325 100985 : && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1326 202011 : && evolution_function_is_affine_multivariate_p
1327 100985 : (CHREC_LEFT (chrec), loopnum))
1328 : return true;
1329 : else
1330 41 : 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 3455903 : evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1344 : {
1345 3455903 : if (chrec == NULL_TREE)
1346 : return true;
1347 :
1348 3455903 : tree sub_chrec;
1349 3455903 : switch (TREE_CODE (chrec))
1350 : {
1351 3455900 : case POLYNOMIAL_CHREC:
1352 3455900 : switch (TREE_CODE (CHREC_LEFT (chrec)))
1353 : {
1354 31405 : case POLYNOMIAL_CHREC:
1355 31405 : sub_chrec = CHREC_LEFT (chrec);
1356 31405 : if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1357 31405 : && (loopnum <= 0
1358 5041 : || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1359 18 : || flow_loop_nested_p (get_loop (cfun, loopnum),
1360 18 : get_chrec_loop (sub_chrec))))
1361 31393 : return false;
1362 12 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1363 : return false;
1364 : break;
1365 :
1366 3424495 : default:
1367 3424495 : if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1368 : return false;
1369 : break;
1370 : }
1371 :
1372 3424507 : 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 0 : return false;
1382 0 : if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1383 : return false;
1384 : break;
1385 :
1386 3424507 : default:
1387 3424507 : if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1388 : 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 3366808 : nb_vars_in_chrec (tree chrec)
1403 : {
1404 6733616 : if (chrec == NULL_TREE)
1405 : return 0;
1406 :
1407 6733616 : switch (TREE_CODE (chrec))
1408 : {
1409 3366808 : case POLYNOMIAL_CHREC:
1410 3366808 : return 1 + nb_vars_in_chrec
1411 3366808 : (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1412 :
1413 : default:
1414 : return 0;
1415 : }
1416 : }
1417 :
1418 : /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1419 : the scev corresponds to. AT_STMT is the statement at that the scev is
1420 : evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1421 : that the rules for overflow of the given language apply (e.g., that signed
1422 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1423 : unnecessary tests, but also to enforce that the result follows them.
1424 : FROM is the source variable converted if it's not NULL. Returns true if
1425 : the conversion succeeded, false otherwise. */
1426 :
1427 : bool
1428 7364102 : convert_affine_scev (class loop *loop, tree type,
1429 : tree *base, tree *step, gimple *at_stmt,
1430 : bool use_overflow_semantics, tree from)
1431 : {
1432 7364102 : tree ct = TREE_TYPE (*step);
1433 7364102 : bool enforce_overflow_semantics;
1434 7364102 : bool must_check_src_overflow, must_check_rslt_overflow;
1435 7364102 : tree new_base, new_step;
1436 7364102 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1437 :
1438 : /* In general,
1439 : (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1440 : but we must check some assumptions.
1441 :
1442 : 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1443 : of CT is smaller than the precision of TYPE. For example, when we
1444 : cast unsigned char [254, +, 1] to unsigned, the values on left side
1445 : are 254, 255, 0, 1, ..., but those on the right side are
1446 : 254, 255, 256, 257, ...
1447 : 2) In case that we must also preserve the fact that signed ivs do not
1448 : overflow, we must additionally check that the new iv does not wrap.
1449 : For example, unsigned char [125, +, 1] casted to signed char could
1450 : become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1451 : which would confuse optimizers that assume that this does not
1452 : happen. */
1453 7364102 : must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1454 :
1455 16756937 : enforce_overflow_semantics = (use_overflow_semantics
1456 7364102 : && nowrap_type_p (type));
1457 2400029 : if (enforce_overflow_semantics)
1458 : {
1459 : /* We can avoid checking whether the result overflows in the following
1460 : cases:
1461 :
1462 : -- must_check_src_overflow is true, and the range of TYPE is superset
1463 : of the range of CT -- i.e., in all cases except if CT signed and
1464 : TYPE unsigned.
1465 : -- both CT and TYPE have the same precision and signedness, and we
1466 : verify instead that the source does not overflow (this may be
1467 : easier than verifying it for the result, as we may use the
1468 : information about the semantics of overflow in CT). */
1469 2400029 : if (must_check_src_overflow)
1470 : {
1471 444064 : if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1472 : must_check_rslt_overflow = true;
1473 : else
1474 : must_check_rslt_overflow = false;
1475 : }
1476 1955965 : else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1477 1955965 : && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1478 : {
1479 : must_check_rslt_overflow = false;
1480 : must_check_src_overflow = true;
1481 : }
1482 : else
1483 : must_check_rslt_overflow = true;
1484 : }
1485 : else
1486 : must_check_rslt_overflow = false;
1487 :
1488 6992806 : if (must_check_src_overflow
1489 7364102 : && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1490 : use_overflow_semantics))
1491 : return false;
1492 :
1493 6600814 : new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1494 : /* The step must be sign extended, regardless of the signedness
1495 : of CT and TYPE. This only needs to be handled specially when
1496 : CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1497 : (with values 100, 99, 98, ...) from becoming signed or unsigned
1498 : [100, +, 255] with values 100, 355, ...; the sign-extension is
1499 : performed by default when CT is signed. */
1500 6600814 : new_step = *step;
1501 6600814 : if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1502 : {
1503 125047 : tree signed_ct = signed_type_for (ct);
1504 125047 : new_step = chrec_convert (signed_ct, new_step, at_stmt,
1505 : use_overflow_semantics);
1506 : }
1507 6600814 : new_step = chrec_convert (step_type, new_step, at_stmt,
1508 : use_overflow_semantics);
1509 :
1510 13201628 : if (automatically_generated_chrec_p (new_base)
1511 1981760 : || automatically_generated_chrec_p (new_step))
1512 : return false;
1513 :
1514 6600554 : if (must_check_rslt_overflow
1515 : /* Note that in this case we cannot use the fact that signed variables
1516 : do not overflow, as this is what we are verifying for the new iv. */
1517 6600554 : && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1518 : at_stmt, loop, false))
1519 : return false;
1520 :
1521 5382342 : *base = new_base;
1522 5382342 : *step = new_step;
1523 5382342 : return true;
1524 : }
1525 :
1526 :
1527 : /* Convert CHREC for the right hand side of a CHREC.
1528 : The increment for a pointer type is always sizetype. */
1529 :
1530 : tree
1531 31892536 : chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1532 : {
1533 31892536 : if (POINTER_TYPE_P (type))
1534 5912410 : type = sizetype;
1535 :
1536 31892536 : return chrec_convert (type, chrec, at_stmt);
1537 : }
1538 :
1539 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1540 : which the CHREC is built, it sets AT_STMT to the statement that
1541 : contains the definition of the analyzed variable, otherwise the
1542 : conversion is less accurate: the information is used for
1543 : determining a more accurate estimation of the number of iterations.
1544 : By default AT_STMT could be safely set to NULL_TREE.
1545 :
1546 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1547 : the rules for overflow of the given language apply (e.g., that signed
1548 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1549 : unnecessary tests, but also to enforce that the result follows them.
1550 :
1551 : FROM is the source variable converted if it's not NULL. */
1552 :
1553 : static tree
1554 158774995 : chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1555 : bool use_overflow_semantics, tree from)
1556 : {
1557 158774995 : tree ct, res;
1558 158774995 : tree base, step;
1559 158774995 : class loop *loop;
1560 :
1561 274117829 : if (automatically_generated_chrec_p (chrec))
1562 : return chrec;
1563 :
1564 157498413 : ct = chrec_type (chrec);
1565 157498413 : if (useless_type_conversion_p (type, ct))
1566 : return chrec;
1567 :
1568 42155579 : if (!evolution_function_is_affine_p (chrec))
1569 36149972 : goto keep_cast;
1570 :
1571 6005607 : loop = get_chrec_loop (chrec);
1572 6005607 : base = CHREC_LEFT (chrec);
1573 6005607 : step = CHREC_RIGHT (chrec);
1574 :
1575 6005607 : if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1576 : use_overflow_semantics, from))
1577 4511075 : return build_polynomial_chrec (loop->num, base, step);
1578 :
1579 : /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1580 1494532 : keep_cast:
1581 : /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1582 : may be more expensive. We do want to perform this optimization here
1583 : though for canonicalization reasons. */
1584 37644504 : if (use_overflow_semantics
1585 37001672 : && (TREE_CODE (chrec) == PLUS_EXPR
1586 37001672 : || TREE_CODE (chrec) == MINUS_EXPR)
1587 3484775 : && TREE_CODE (type) == INTEGER_TYPE
1588 3438860 : && TREE_CODE (ct) == INTEGER_TYPE
1589 3438814 : && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1590 37811456 : && TYPE_OVERFLOW_UNDEFINED (ct))
1591 61713 : res = fold_build2 (TREE_CODE (chrec), type,
1592 : fold_convert (type, TREE_OPERAND (chrec, 0)),
1593 : fold_convert (type, TREE_OPERAND (chrec, 1)));
1594 : /* Similar perform the trick that (signed char)((int)x + 2) can be
1595 : narrowed to (signed char)((unsigned char)x + 2). */
1596 37582791 : else if (use_overflow_semantics
1597 36939959 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1598 1524704 : && TREE_CODE (ct) == INTEGER_TYPE
1599 1512616 : && TREE_CODE (type) == INTEGER_TYPE
1600 1376357 : && TYPE_OVERFLOW_UNDEFINED (type)
1601 38722659 : && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1602 : {
1603 28629 : tree utype = unsigned_type_for (type);
1604 85887 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1605 28629 : fold_convert (utype,
1606 : CHREC_LEFT (chrec)),
1607 28629 : fold_convert (utype,
1608 : CHREC_RIGHT (chrec)));
1609 28629 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1610 : }
1611 : /* Similar perform the trick that (unsigned T)(base + step) can be
1612 : folded to ((unsigned T)x + (unsigned T)step). */
1613 37554162 : else if (use_overflow_semantics
1614 36911330 : && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1615 1496075 : && INTEGRAL_TYPE_P (ct)
1616 1484067 : && INTEGRAL_TYPE_P (type)
1617 1347808 : && TYPE_OVERFLOW_UNDEFINED (type)
1618 : /* Must be unsigned so we don't introduce any UB. */
1619 1111319 : && TYPE_UNSIGNED (type)
1620 : /* The outer type must at least as wide than the inner type so we
1621 : don't truncate when we fold and must the inner CHREC must be
1622 : non-wrapping so we don't change the behavior when folding to
1623 : a wider type. */
1624 0 : && TYPE_PRECISION (type) >= TYPE_PRECISION (ct)
1625 37554162 : && (!TYPE_UNSIGNED (ct)
1626 0 : || TYPE_PRECISION (type) == TYPE_PRECISION (ct)
1627 0 : || nonwrapping_chrec_p (chrec)))
1628 : {
1629 0 : res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1630 0 : fold_convert (type,
1631 : CHREC_LEFT (chrec)),
1632 0 : fold_convert (type,
1633 : CHREC_RIGHT (chrec)));
1634 0 : res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1635 : }
1636 : else
1637 37554162 : res = fold_convert (type, chrec);
1638 :
1639 : /* Don't propagate overflows. */
1640 37644504 : if (CONSTANT_CLASS_P (res))
1641 11866248 : TREE_OVERFLOW (res) = 0;
1642 :
1643 : /* But reject constants that don't fit in their type after conversion.
1644 : This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1645 : natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1646 : and can cause problems later when computing niters of loops. Note
1647 : that we don't do the check before converting because we don't want
1648 : to reject conversions of negative chrecs to unsigned types. */
1649 37644504 : if (TREE_CODE (res) == INTEGER_CST
1650 11866247 : && TREE_CODE (type) == INTEGER_TYPE
1651 11822874 : && !int_fits_type_p (res, type))
1652 369 : res = chrec_dont_know;
1653 :
1654 : return res;
1655 : }
1656 :
1657 : /* Convert CHREC to TYPE. When the analyzer knows the context in
1658 : which the CHREC is built, it sets AT_STMT to the statement that
1659 : contains the definition of the analyzed variable, otherwise the
1660 : conversion is less accurate: the information is used for
1661 : determining a more accurate estimation of the number of iterations.
1662 : By default AT_STMT could be safely set to NULL_TREE.
1663 :
1664 : The following rule is always true: TREE_TYPE (chrec) ==
1665 : TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1666 : An example of what could happen when adding two chrecs and the type
1667 : of the CHREC_RIGHT is different than CHREC_LEFT is:
1668 :
1669 : {(uint) 0, +, (uchar) 10} +
1670 : {(uint) 0, +, (uchar) 250}
1671 :
1672 : that would produce a wrong result if CHREC_RIGHT is not (uint):
1673 :
1674 : {(uint) 0, +, (uchar) 4}
1675 :
1676 : instead of
1677 :
1678 : {(uint) 0, +, (uint) 260}
1679 :
1680 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
1681 : the rules for overflow of the given language apply (e.g., that signed
1682 : arithmetics in C does not overflow) -- i.e., to use them to avoid
1683 : unnecessary tests, but also to enforce that the result follows them.
1684 :
1685 : FROM is the source variable converted if it's not NULL. */
1686 :
1687 : tree
1688 158746366 : chrec_convert (tree type, tree chrec, gimple *at_stmt,
1689 : bool use_overflow_semantics, tree from)
1690 : {
1691 158746366 : return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1692 : }
1693 :
1694 : /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1695 : chrec if something else than what chrec_convert would do happens, NULL_TREE
1696 : otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1697 : if the result chrec may overflow. */
1698 :
1699 : tree
1700 8870942 : chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1701 : {
1702 8870942 : tree inner_type, left, right, lc, rc, rtype;
1703 :
1704 8870942 : gcc_assert (fold_conversions != NULL);
1705 :
1706 17255014 : if (automatically_generated_chrec_p (chrec)
1707 8870942 : || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1708 : return NULL_TREE;
1709 :
1710 641135 : inner_type = TREE_TYPE (chrec);
1711 641135 : if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1712 : return NULL_TREE;
1713 :
1714 561168 : if (useless_type_conversion_p (type, inner_type))
1715 : return NULL_TREE;
1716 :
1717 486870 : if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1718 : {
1719 486060 : tree base, step;
1720 486060 : class loop *loop;
1721 :
1722 486060 : loop = get_chrec_loop (chrec);
1723 486060 : base = CHREC_LEFT (chrec);
1724 486060 : step = CHREC_RIGHT (chrec);
1725 486060 : if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1726 2124 : return build_polynomial_chrec (loop->num, base, step);
1727 : }
1728 484746 : rtype = POINTER_TYPE_P (type) ? sizetype : type;
1729 :
1730 484746 : left = CHREC_LEFT (chrec);
1731 484746 : right = CHREC_RIGHT (chrec);
1732 484746 : lc = chrec_convert_aggressive (type, left, fold_conversions);
1733 484746 : if (!lc)
1734 484746 : lc = chrec_convert (type, left, NULL);
1735 484746 : rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1736 484746 : if (!rc)
1737 484062 : rc = chrec_convert (rtype, right, NULL);
1738 :
1739 484746 : *fold_conversions = true;
1740 :
1741 484746 : return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1742 : }
1743 :
1744 : /* Returns true when CHREC0 == CHREC1. */
1745 :
1746 : bool
1747 13439071 : eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1748 : {
1749 13471673 : if (chrec0 == NULL_TREE
1750 13471673 : || chrec1 == NULL_TREE
1751 13471673 : || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1752 : return false;
1753 :
1754 12562539 : if (operand_equal_p (chrec0, chrec1, 0))
1755 : return true;
1756 :
1757 9383146 : if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1758 : return false;
1759 :
1760 9381941 : switch (TREE_CODE (chrec0))
1761 : {
1762 3887393 : case POLYNOMIAL_CHREC:
1763 3887393 : return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1764 3887056 : && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1765 4228586 : && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1766 :
1767 54972 : case PLUS_EXPR:
1768 54972 : case MULT_EXPR:
1769 54972 : case MINUS_EXPR:
1770 54972 : case POINTER_PLUS_EXPR:
1771 54972 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1772 54972 : TREE_OPERAND (chrec1, 0))
1773 95930 : && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1774 40958 : TREE_OPERAND (chrec1, 1));
1775 :
1776 32602 : CASE_CONVERT:
1777 32602 : return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1778 65204 : TREE_OPERAND (chrec1, 0));
1779 :
1780 : default:
1781 : return false;
1782 : }
1783 : }
1784 :
1785 : /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1786 : EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1787 : which of these cases happens. */
1788 :
1789 : enum ev_direction
1790 3558988 : scev_direction (const_tree chrec)
1791 : {
1792 3558988 : const_tree step;
1793 :
1794 3558988 : if (!evolution_function_is_affine_p (chrec))
1795 : return EV_DIR_UNKNOWN;
1796 :
1797 3550193 : step = CHREC_RIGHT (chrec);
1798 3550193 : if (TREE_CODE (step) != INTEGER_CST)
1799 : return EV_DIR_UNKNOWN;
1800 :
1801 3361930 : if (tree_int_cst_sign_bit (step))
1802 : return EV_DIR_DECREASES;
1803 : else
1804 3020407 : return EV_DIR_GROWS;
1805 : }
1806 :
1807 : /* Iterates over all the components of SCEV, and calls CBCK. */
1808 :
1809 : void
1810 0 : for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1811 : {
1812 0 : switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1813 : {
1814 0 : case 3:
1815 0 : for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1816 : /* FALLTHRU */
1817 :
1818 0 : case 2:
1819 0 : for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1820 : /* FALLTHRU */
1821 :
1822 0 : case 1:
1823 0 : for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1824 : /* FALLTHRU */
1825 :
1826 0 : default:
1827 0 : cbck (scev, data);
1828 0 : break;
1829 : }
1830 0 : }
1831 :
1832 : /* Returns true when the operation can be part of a linear
1833 : expression. */
1834 :
1835 : static inline bool
1836 33999 : operator_is_linear (tree scev)
1837 : {
1838 33999 : switch (TREE_CODE (scev))
1839 : {
1840 : case INTEGER_CST:
1841 : case POLYNOMIAL_CHREC:
1842 : case PLUS_EXPR:
1843 : case POINTER_PLUS_EXPR:
1844 : case MULT_EXPR:
1845 : case MINUS_EXPR:
1846 : case NEGATE_EXPR:
1847 : case SSA_NAME:
1848 : case NON_LVALUE_EXPR:
1849 : case BIT_NOT_EXPR:
1850 : CASE_CONVERT:
1851 : return true;
1852 :
1853 8 : default:
1854 8 : return false;
1855 : }
1856 : }
1857 :
1858 : /* Return true when SCEV is a linear expression. Linear expressions
1859 : can contain additions, substractions and multiplications.
1860 : Multiplications are restricted to constant scaling: "cst * x". */
1861 :
1862 : bool
1863 77812 : scev_is_linear_expression (tree scev)
1864 : {
1865 160176 : if (evolution_function_is_constant_p (scev))
1866 : return true;
1867 :
1868 33999 : if (scev == NULL
1869 33999 : || !operator_is_linear (scev))
1870 : return false;
1871 :
1872 33991 : if (TREE_CODE (scev) == MULT_EXPR)
1873 601 : return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1874 0 : && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1875 :
1876 33390 : if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1877 33390 : && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1878 : return false;
1879 :
1880 33190 : switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1881 : {
1882 0 : case 3:
1883 0 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1884 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1885 0 : && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1886 :
1887 24441 : case 2:
1888 24441 : return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1889 24441 : && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1890 :
1891 2276 : case 1:
1892 2276 : return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1893 :
1894 : case 0:
1895 : return true;
1896 :
1897 : default:
1898 : return false;
1899 : }
1900 : }
1901 :
1902 : /* Determines whether the expression CHREC contains only integer consts
1903 : in the right parts. */
1904 :
1905 : bool
1906 4313 : evolution_function_right_is_integer_cst (const_tree chrec)
1907 : {
1908 4313 : if (chrec == NULL_TREE)
1909 : return false;
1910 :
1911 4313 : switch (TREE_CODE (chrec))
1912 : {
1913 : case INTEGER_CST:
1914 : return true;
1915 :
1916 4313 : case POLYNOMIAL_CHREC:
1917 4313 : return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1918 4313 : && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1919 470 : || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1920 :
1921 0 : CASE_CONVERT:
1922 0 : return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1923 :
1924 : default:
1925 : return false;
1926 : }
1927 : }
|
