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