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