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