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