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