2015-03-02 Hristian Kirtchev <kirtchev@adacore.com>
[official-gcc.git] / gcc / tree-chrec.c
blob84ba30e4e92ba353fbc20437e1d3032227cfd1bb
1 /* Chains of recurrences.
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
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.
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.
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/>. */
21 /* This file implements operations on chains of recurrences. Chains
22 of recurrences are used for modeling evolution functions of scalar
23 variables.
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "hash-set.h"
30 #include "machmode.h"
31 #include "vec.h"
32 #include "double-int.h"
33 #include "input.h"
34 #include "alias.h"
35 #include "symtab.h"
36 #include "options.h"
37 #include "wide-int.h"
38 #include "inchash.h"
39 #include "real.h"
40 #include "tree.h"
41 #include "fold-const.h"
42 #include "tree-pretty-print.h"
43 #include "cfgloop.h"
44 #include "predict.h"
45 #include "tm.h"
46 #include "hard-reg-set.h"
47 #include "input.h"
48 #include "function.h"
49 #include "dominance.h"
50 #include "cfg.h"
51 #include "basic-block.h"
52 #include "gimple-expr.h"
53 #include "tree-ssa-loop-ivopts.h"
54 #include "tree-ssa-loop-niter.h"
55 #include "tree-chrec.h"
56 #include "dumpfile.h"
57 #include "params.h"
58 #include "tree-scalar-evolution.h"
60 /* Extended folder for chrecs. */
62 /* Determines whether CST is not a constant evolution. */
64 static inline bool
65 is_not_constant_evolution (const_tree cst)
67 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
70 /* Fold CODE for a polynomial function and a constant. */
72 static inline tree
73 chrec_fold_poly_cst (enum tree_code code,
74 tree type,
75 tree poly,
76 tree cst)
78 gcc_assert (poly);
79 gcc_assert (cst);
80 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
81 gcc_assert (!is_not_constant_evolution (cst));
82 gcc_assert (type == chrec_type (poly));
84 switch (code)
86 case PLUS_EXPR:
87 return build_polynomial_chrec
88 (CHREC_VARIABLE (poly),
89 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
90 CHREC_RIGHT (poly));
92 case MINUS_EXPR:
93 return build_polynomial_chrec
94 (CHREC_VARIABLE (poly),
95 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
96 CHREC_RIGHT (poly));
98 case MULT_EXPR:
99 return build_polynomial_chrec
100 (CHREC_VARIABLE (poly),
101 chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
102 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
104 default:
105 return chrec_dont_know;
109 /* Fold the addition of two polynomial functions. */
111 static inline tree
112 chrec_fold_plus_poly_poly (enum tree_code code,
113 tree type,
114 tree poly0,
115 tree poly1)
117 tree left, right;
118 struct loop *loop0 = get_chrec_loop (poly0);
119 struct loop *loop1 = get_chrec_loop (poly1);
120 tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
122 gcc_assert (poly0);
123 gcc_assert (poly1);
124 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
125 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
126 if (POINTER_TYPE_P (chrec_type (poly0)))
127 gcc_assert (ptrofftype_p (chrec_type (poly1)));
128 else
129 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
130 gcc_assert (type == chrec_type (poly0));
133 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
134 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
135 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
136 if (flow_loop_nested_p (loop0, loop1))
138 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
139 return build_polynomial_chrec
140 (CHREC_VARIABLE (poly1),
141 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
142 CHREC_RIGHT (poly1));
143 else
144 return build_polynomial_chrec
145 (CHREC_VARIABLE (poly1),
146 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
147 chrec_fold_multiply (type, CHREC_RIGHT (poly1),
148 SCALAR_FLOAT_TYPE_P (type)
149 ? build_real (type, dconstm1)
150 : build_int_cst_type (type, -1)));
153 if (flow_loop_nested_p (loop1, loop0))
155 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
156 return build_polynomial_chrec
157 (CHREC_VARIABLE (poly0),
158 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
159 CHREC_RIGHT (poly0));
160 else
161 return build_polynomial_chrec
162 (CHREC_VARIABLE (poly0),
163 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
164 CHREC_RIGHT (poly0));
167 /* This function should never be called for chrecs of loops that
168 do not belong to the same loop nest. */
169 gcc_assert (loop0 == loop1);
171 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
173 left = chrec_fold_plus
174 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
175 right = chrec_fold_plus
176 (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
178 else
180 left = chrec_fold_minus
181 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
182 right = chrec_fold_minus
183 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
186 if (chrec_zerop (right))
187 return left;
188 else
189 return build_polynomial_chrec
190 (CHREC_VARIABLE (poly0), left, right);
195 /* Fold the multiplication of two polynomial functions. */
197 static inline tree
198 chrec_fold_multiply_poly_poly (tree type,
199 tree poly0,
200 tree poly1)
202 tree t0, t1, t2;
203 int var;
204 struct loop *loop0 = get_chrec_loop (poly0);
205 struct loop *loop1 = get_chrec_loop (poly1);
207 gcc_assert (poly0);
208 gcc_assert (poly1);
209 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
210 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
211 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
212 gcc_assert (type == chrec_type (poly0));
214 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
215 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
216 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
217 if (flow_loop_nested_p (loop0, loop1))
218 /* poly0 is a constant wrt. poly1. */
219 return build_polynomial_chrec
220 (CHREC_VARIABLE (poly1),
221 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
222 CHREC_RIGHT (poly1));
224 if (flow_loop_nested_p (loop1, loop0))
225 /* poly1 is a constant wrt. poly0. */
226 return build_polynomial_chrec
227 (CHREC_VARIABLE (poly0),
228 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
229 CHREC_RIGHT (poly0));
231 gcc_assert (loop0 == loop1);
233 /* poly0 and poly1 are two polynomials in the same variable,
234 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
236 /* "a*c". */
237 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
239 /* "a*d + b*c". */
240 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
241 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
242 CHREC_RIGHT (poly0),
243 CHREC_LEFT (poly1)));
244 /* "b*d". */
245 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
246 /* "a*d + b*c + b*d". */
247 t1 = chrec_fold_plus (type, t1, t2);
248 /* "2*b*d". */
249 t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
250 ? build_real (type, dconst2)
251 : build_int_cst (type, 2), t2);
253 var = CHREC_VARIABLE (poly0);
254 return build_polynomial_chrec (var, t0,
255 build_polynomial_chrec (var, t1, t2));
258 /* When the operands are automatically_generated_chrec_p, the fold has
259 to respect the semantics of the operands. */
261 static inline tree
262 chrec_fold_automatically_generated_operands (tree op0,
263 tree op1)
265 if (op0 == chrec_dont_know
266 || op1 == chrec_dont_know)
267 return chrec_dont_know;
269 if (op0 == chrec_known
270 || op1 == chrec_known)
271 return chrec_known;
273 if (op0 == chrec_not_analyzed_yet
274 || op1 == chrec_not_analyzed_yet)
275 return chrec_not_analyzed_yet;
277 /* The default case produces a safe result. */
278 return chrec_dont_know;
281 /* Fold the addition of two chrecs. */
283 static tree
284 chrec_fold_plus_1 (enum tree_code code, tree type,
285 tree op0, tree op1)
287 if (automatically_generated_chrec_p (op0)
288 || automatically_generated_chrec_p (op1))
289 return chrec_fold_automatically_generated_operands (op0, op1);
291 switch (TREE_CODE (op0))
293 case POLYNOMIAL_CHREC:
294 gcc_checking_assert
295 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
296 switch (TREE_CODE (op1))
298 case POLYNOMIAL_CHREC:
299 gcc_checking_assert
300 (!chrec_contains_symbols_defined_in_loop (op1,
301 CHREC_VARIABLE (op1)));
302 return chrec_fold_plus_poly_poly (code, type, op0, op1);
304 CASE_CONVERT:
305 if (tree_contains_chrecs (op1, NULL))
306 return chrec_dont_know;
308 default:
309 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
310 return build_polynomial_chrec
311 (CHREC_VARIABLE (op0),
312 chrec_fold_plus (type, CHREC_LEFT (op0), op1),
313 CHREC_RIGHT (op0));
314 else
315 return build_polynomial_chrec
316 (CHREC_VARIABLE (op0),
317 chrec_fold_minus (type, CHREC_LEFT (op0), op1),
318 CHREC_RIGHT (op0));
321 CASE_CONVERT:
322 if (tree_contains_chrecs (op0, NULL))
323 return chrec_dont_know;
325 default:
326 switch (TREE_CODE (op1))
328 case POLYNOMIAL_CHREC:
329 gcc_checking_assert
330 (!chrec_contains_symbols_defined_in_loop (op1,
331 CHREC_VARIABLE (op1)));
332 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
333 return build_polynomial_chrec
334 (CHREC_VARIABLE (op1),
335 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
336 CHREC_RIGHT (op1));
337 else
338 return build_polynomial_chrec
339 (CHREC_VARIABLE (op1),
340 chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
341 chrec_fold_multiply (type, CHREC_RIGHT (op1),
342 SCALAR_FLOAT_TYPE_P (type)
343 ? build_real (type, dconstm1)
344 : build_int_cst_type (type, -1)));
346 CASE_CONVERT:
347 if (tree_contains_chrecs (op1, NULL))
348 return chrec_dont_know;
350 default:
352 int size = 0;
353 if ((tree_contains_chrecs (op0, &size)
354 || tree_contains_chrecs (op1, &size))
355 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
356 return build2 (code, type, op0, op1);
357 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
359 if (code == POINTER_PLUS_EXPR)
360 return fold_build_pointer_plus (fold_convert (type, op0),
361 op1);
362 else
363 return fold_build2 (code, type,
364 fold_convert (type, op0),
365 fold_convert (type, op1));
367 else
368 return chrec_dont_know;
374 /* Fold the addition of two chrecs. */
376 tree
377 chrec_fold_plus (tree type,
378 tree op0,
379 tree op1)
381 enum tree_code code;
382 if (automatically_generated_chrec_p (op0)
383 || automatically_generated_chrec_p (op1))
384 return chrec_fold_automatically_generated_operands (op0, op1);
386 if (integer_zerop (op0))
387 return chrec_convert (type, op1, NULL);
388 if (integer_zerop (op1))
389 return chrec_convert (type, op0, NULL);
391 if (POINTER_TYPE_P (type))
392 code = POINTER_PLUS_EXPR;
393 else
394 code = PLUS_EXPR;
396 return chrec_fold_plus_1 (code, type, op0, op1);
399 /* Fold the subtraction of two chrecs. */
401 tree
402 chrec_fold_minus (tree type,
403 tree op0,
404 tree op1)
406 if (automatically_generated_chrec_p (op0)
407 || automatically_generated_chrec_p (op1))
408 return chrec_fold_automatically_generated_operands (op0, op1);
410 if (integer_zerop (op1))
411 return op0;
413 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
416 /* Fold the multiplication of two chrecs. */
418 tree
419 chrec_fold_multiply (tree type,
420 tree op0,
421 tree op1)
423 if (automatically_generated_chrec_p (op0)
424 || automatically_generated_chrec_p (op1))
425 return chrec_fold_automatically_generated_operands (op0, op1);
427 switch (TREE_CODE (op0))
429 case POLYNOMIAL_CHREC:
430 gcc_checking_assert
431 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
432 switch (TREE_CODE (op1))
434 case POLYNOMIAL_CHREC:
435 gcc_checking_assert
436 (!chrec_contains_symbols_defined_in_loop (op1,
437 CHREC_VARIABLE (op1)));
438 return chrec_fold_multiply_poly_poly (type, op0, op1);
440 CASE_CONVERT:
441 if (tree_contains_chrecs (op1, NULL))
442 return chrec_dont_know;
444 default:
445 if (integer_onep (op1))
446 return op0;
447 if (integer_zerop (op1))
448 return build_int_cst (type, 0);
450 return build_polynomial_chrec
451 (CHREC_VARIABLE (op0),
452 chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
453 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
456 CASE_CONVERT:
457 if (tree_contains_chrecs (op0, NULL))
458 return chrec_dont_know;
460 default:
461 if (integer_onep (op0))
462 return op1;
464 if (integer_zerop (op0))
465 return build_int_cst (type, 0);
467 switch (TREE_CODE (op1))
469 case POLYNOMIAL_CHREC:
470 gcc_checking_assert
471 (!chrec_contains_symbols_defined_in_loop (op1,
472 CHREC_VARIABLE (op1)));
473 return build_polynomial_chrec
474 (CHREC_VARIABLE (op1),
475 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
476 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
478 CASE_CONVERT:
479 if (tree_contains_chrecs (op1, NULL))
480 return chrec_dont_know;
482 default:
483 if (integer_onep (op1))
484 return op0;
485 if (integer_zerop (op1))
486 return build_int_cst (type, 0);
487 return fold_build2 (MULT_EXPR, type, op0, op1);
494 /* Operations. */
496 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
497 calculation overflows, otherwise return C(n,k) with type TYPE. */
499 static tree
500 tree_fold_binomial (tree type, tree n, unsigned int k)
502 bool overflow;
503 unsigned int i;
504 tree res;
506 /* Handle the most frequent cases. */
507 if (k == 0)
508 return build_int_cst (type, 1);
509 if (k == 1)
510 return fold_convert (type, n);
512 /* Check that k <= n. */
513 if (wi::ltu_p (n, k))
514 return NULL_TREE;
516 /* Denominator = 2. */
517 wide_int denom = wi::two (TYPE_PRECISION (TREE_TYPE (n)));
519 /* Index = Numerator-1. */
520 wide_int idx = wi::sub (n, 1);
522 /* Numerator = Numerator*Index = n*(n-1). */
523 wide_int num = wi::smul (n, idx, &overflow);
524 if (overflow)
525 return NULL_TREE;
527 for (i = 3; i <= k; i++)
529 /* Index--. */
530 --idx;
532 /* Numerator *= Index. */
533 num = wi::smul (num, idx, &overflow);
534 if (overflow)
535 return NULL_TREE;
537 /* Denominator *= i. */
538 denom *= i;
541 /* Result = Numerator / Denominator. */
542 wide_int di_res = wi::udiv_trunc (num, denom);
543 res = wide_int_to_tree (type, di_res);
544 return int_fits_type_p (res, type) ? res : NULL_TREE;
547 /* Helper function. Use the Newton's interpolating formula for
548 evaluating the value of the evolution function. */
550 static tree
551 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
553 tree arg0, arg1, binomial_n_k;
554 tree type = TREE_TYPE (chrec);
555 struct loop *var_loop = get_loop (cfun, var);
557 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
558 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
559 chrec = CHREC_LEFT (chrec);
561 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
562 && CHREC_VARIABLE (chrec) == var)
564 arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
565 if (arg1 == chrec_dont_know)
566 return chrec_dont_know;
567 binomial_n_k = tree_fold_binomial (type, n, k);
568 if (!binomial_n_k)
569 return chrec_dont_know;
570 arg0 = fold_build2 (MULT_EXPR, type,
571 CHREC_LEFT (chrec), binomial_n_k);
572 return chrec_fold_plus (type, arg0, arg1);
575 binomial_n_k = tree_fold_binomial (type, n, k);
576 if (!binomial_n_k)
577 return chrec_dont_know;
579 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
582 /* Evaluates "CHREC (X)" when the varying variable is VAR.
583 Example: Given the following parameters,
585 var = 1
586 chrec = {3, +, 4}_1
587 x = 10
589 The result is given by the Newton's interpolating formula:
590 3 * \binom{10}{0} + 4 * \binom{10}{1}.
593 tree
594 chrec_apply (unsigned var,
595 tree chrec,
596 tree x)
598 tree type = chrec_type (chrec);
599 tree res = chrec_dont_know;
601 if (automatically_generated_chrec_p (chrec)
602 || automatically_generated_chrec_p (x)
604 /* When the symbols are defined in an outer loop, it is possible
605 to symbolically compute the apply, since the symbols are
606 constants with respect to the varying loop. */
607 || chrec_contains_symbols_defined_in_loop (chrec, var))
608 return chrec_dont_know;
610 if (dump_file && (dump_flags & TDF_SCEV))
611 fprintf (dump_file, "(chrec_apply \n");
613 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
614 x = build_real_from_int_cst (type, x);
616 switch (TREE_CODE (chrec))
618 case POLYNOMIAL_CHREC:
619 if (evolution_function_is_affine_p (chrec))
621 if (CHREC_VARIABLE (chrec) != var)
622 return build_polynomial_chrec
623 (CHREC_VARIABLE (chrec),
624 chrec_apply (var, CHREC_LEFT (chrec), x),
625 chrec_apply (var, CHREC_RIGHT (chrec), x));
627 /* "{a, +, b} (x)" -> "a + b*x". */
628 x = chrec_convert_rhs (type, x, NULL);
629 res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
630 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
632 else if (TREE_CODE (x) == INTEGER_CST
633 && tree_int_cst_sgn (x) == 1)
634 /* testsuite/.../ssa-chrec-38.c. */
635 res = chrec_evaluate (var, chrec, x, 0);
636 else
637 res = chrec_dont_know;
638 break;
640 CASE_CONVERT:
641 res = chrec_convert (TREE_TYPE (chrec),
642 chrec_apply (var, TREE_OPERAND (chrec, 0), x),
643 NULL);
644 break;
646 default:
647 res = chrec;
648 break;
651 if (dump_file && (dump_flags & TDF_SCEV))
653 fprintf (dump_file, " (varying_loop = %d\n", var);
654 fprintf (dump_file, ")\n (chrec = ");
655 print_generic_expr (dump_file, chrec, 0);
656 fprintf (dump_file, ")\n (x = ");
657 print_generic_expr (dump_file, x, 0);
658 fprintf (dump_file, ")\n (res = ");
659 print_generic_expr (dump_file, res, 0);
660 fprintf (dump_file, "))\n");
663 return res;
666 /* For a given CHREC and an induction variable map IV_MAP that maps
667 (loop->num, expr) for every loop number of the current_loops an
668 expression, calls chrec_apply when the expression is not NULL. */
670 tree
671 chrec_apply_map (tree chrec, vec<tree> iv_map)
673 int i;
674 tree expr;
676 FOR_EACH_VEC_ELT (iv_map, i, expr)
677 if (expr)
678 chrec = chrec_apply (i, chrec, expr);
680 return chrec;
683 /* Replaces the initial condition in CHREC with INIT_COND. */
685 tree
686 chrec_replace_initial_condition (tree chrec,
687 tree init_cond)
689 if (automatically_generated_chrec_p (chrec))
690 return chrec;
692 gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
694 switch (TREE_CODE (chrec))
696 case POLYNOMIAL_CHREC:
697 return build_polynomial_chrec
698 (CHREC_VARIABLE (chrec),
699 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
700 CHREC_RIGHT (chrec));
702 default:
703 return init_cond;
707 /* Returns the initial condition of a given CHREC. */
709 tree
710 initial_condition (tree chrec)
712 if (automatically_generated_chrec_p (chrec))
713 return chrec;
715 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
716 return initial_condition (CHREC_LEFT (chrec));
717 else
718 return chrec;
721 /* Returns a univariate function that represents the evolution in
722 LOOP_NUM. Mask the evolution of any other loop. */
724 tree
725 hide_evolution_in_other_loops_than_loop (tree chrec,
726 unsigned loop_num)
728 struct loop *loop = get_loop (cfun, loop_num), *chloop;
729 if (automatically_generated_chrec_p (chrec))
730 return chrec;
732 switch (TREE_CODE (chrec))
734 case POLYNOMIAL_CHREC:
735 chloop = get_chrec_loop (chrec);
737 if (chloop == loop)
738 return build_polynomial_chrec
739 (loop_num,
740 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
741 loop_num),
742 CHREC_RIGHT (chrec));
744 else if (flow_loop_nested_p (chloop, loop))
745 /* There is no evolution in this loop. */
746 return initial_condition (chrec);
748 else
750 gcc_assert (flow_loop_nested_p (loop, chloop));
751 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
752 loop_num);
755 default:
756 return chrec;
760 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
761 true, otherwise returns the initial condition in LOOP_NUM. */
763 static tree
764 chrec_component_in_loop_num (tree chrec,
765 unsigned loop_num,
766 bool right)
768 tree component;
769 struct loop *loop = get_loop (cfun, loop_num), *chloop;
771 if (automatically_generated_chrec_p (chrec))
772 return chrec;
774 switch (TREE_CODE (chrec))
776 case POLYNOMIAL_CHREC:
777 chloop = get_chrec_loop (chrec);
779 if (chloop == loop)
781 if (right)
782 component = CHREC_RIGHT (chrec);
783 else
784 component = CHREC_LEFT (chrec);
786 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
787 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
788 return component;
790 else
791 return build_polynomial_chrec
792 (loop_num,
793 chrec_component_in_loop_num (CHREC_LEFT (chrec),
794 loop_num,
795 right),
796 component);
799 else if (flow_loop_nested_p (chloop, loop))
800 /* There is no evolution part in this loop. */
801 return NULL_TREE;
803 else
805 gcc_assert (flow_loop_nested_p (loop, chloop));
806 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
807 loop_num,
808 right);
811 default:
812 if (right)
813 return NULL_TREE;
814 else
815 return chrec;
819 /* Returns the evolution part in LOOP_NUM. Example: the call
820 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
821 {1, +, 2}_1 */
823 tree
824 evolution_part_in_loop_num (tree chrec,
825 unsigned loop_num)
827 return chrec_component_in_loop_num (chrec, loop_num, true);
830 /* Returns the initial condition in LOOP_NUM. Example: the call
831 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
832 {0, +, 1}_1 */
834 tree
835 initial_condition_in_loop_num (tree chrec,
836 unsigned loop_num)
838 return chrec_component_in_loop_num (chrec, loop_num, false);
841 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
842 This function is essentially used for setting the evolution to
843 chrec_dont_know, for example after having determined that it is
844 impossible to say how many times a loop will execute. */
846 tree
847 reset_evolution_in_loop (unsigned loop_num,
848 tree chrec,
849 tree new_evol)
851 struct loop *loop = get_loop (cfun, loop_num);
853 if (POINTER_TYPE_P (chrec_type (chrec)))
854 gcc_assert (ptrofftype_p (chrec_type (new_evol)));
855 else
856 gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
858 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
859 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
861 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
862 new_evol);
863 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
864 new_evol);
865 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
866 CHREC_VAR (chrec), left, right);
869 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
870 && CHREC_VARIABLE (chrec) == loop_num)
871 chrec = CHREC_LEFT (chrec);
873 return build_polynomial_chrec (loop_num, chrec, new_evol);
876 /* Merges two evolution functions that were found by following two
877 alternate paths of a conditional expression. */
879 tree
880 chrec_merge (tree chrec1,
881 tree chrec2)
883 if (chrec1 == chrec_dont_know
884 || chrec2 == chrec_dont_know)
885 return chrec_dont_know;
887 if (chrec1 == chrec_known
888 || chrec2 == chrec_known)
889 return chrec_known;
891 if (chrec1 == chrec_not_analyzed_yet)
892 return chrec2;
893 if (chrec2 == chrec_not_analyzed_yet)
894 return chrec1;
896 if (eq_evolutions_p (chrec1, chrec2))
897 return chrec1;
899 return chrec_dont_know;
904 /* Observers. */
906 /* Helper function for is_multivariate_chrec. */
908 static bool
909 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
911 if (chrec == NULL_TREE)
912 return false;
914 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
916 if (CHREC_VARIABLE (chrec) != rec_var)
917 return true;
918 else
919 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
920 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
922 else
923 return false;
926 /* Determine whether the given chrec is multivariate or not. */
928 bool
929 is_multivariate_chrec (const_tree chrec)
931 if (chrec == NULL_TREE)
932 return false;
934 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
935 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
936 CHREC_VARIABLE (chrec))
937 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
938 CHREC_VARIABLE (chrec)));
939 else
940 return false;
943 /* Determines whether the chrec contains symbolic names or not. */
945 bool
946 chrec_contains_symbols (const_tree chrec)
948 int i, n;
950 if (chrec == NULL_TREE)
951 return false;
953 if (TREE_CODE (chrec) == SSA_NAME
954 || TREE_CODE (chrec) == VAR_DECL
955 || TREE_CODE (chrec) == PARM_DECL
956 || TREE_CODE (chrec) == FUNCTION_DECL
957 || TREE_CODE (chrec) == LABEL_DECL
958 || TREE_CODE (chrec) == RESULT_DECL
959 || TREE_CODE (chrec) == FIELD_DECL)
960 return true;
962 n = TREE_OPERAND_LENGTH (chrec);
963 for (i = 0; i < n; i++)
964 if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
965 return true;
966 return false;
969 /* Determines whether the chrec contains undetermined coefficients. */
971 bool
972 chrec_contains_undetermined (const_tree chrec)
974 int i, n;
976 if (chrec == chrec_dont_know)
977 return true;
979 if (chrec == NULL_TREE)
980 return false;
982 n = TREE_OPERAND_LENGTH (chrec);
983 for (i = 0; i < n; i++)
984 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
985 return true;
986 return false;
989 /* Determines whether the tree EXPR contains chrecs, and increment
990 SIZE if it is not a NULL pointer by an estimation of the depth of
991 the tree. */
993 bool
994 tree_contains_chrecs (const_tree expr, int *size)
996 int i, n;
998 if (expr == NULL_TREE)
999 return false;
1001 if (size)
1002 (*size)++;
1004 if (tree_is_chrec (expr))
1005 return true;
1007 n = TREE_OPERAND_LENGTH (expr);
1008 for (i = 0; i < n; i++)
1009 if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
1010 return true;
1011 return false;
1014 /* Recursive helper function. */
1016 static bool
1017 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1019 if (evolution_function_is_constant_p (chrec))
1020 return true;
1022 if (TREE_CODE (chrec) == SSA_NAME
1023 && (loopnum == 0
1024 || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1025 return true;
1027 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1029 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1030 || flow_loop_nested_p (get_loop (cfun, loopnum),
1031 get_chrec_loop (chrec))
1032 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1033 loopnum)
1034 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1035 loopnum))
1036 return false;
1037 return true;
1040 switch (TREE_OPERAND_LENGTH (chrec))
1042 case 2:
1043 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1044 loopnum))
1045 return false;
1047 case 1:
1048 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1049 loopnum))
1050 return false;
1051 return true;
1053 default:
1054 return false;
1057 return false;
1060 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1062 bool
1063 evolution_function_is_invariant_p (tree chrec, int loopnum)
1065 return evolution_function_is_invariant_rec_p (chrec, loopnum);
1068 /* Determine whether the given tree is an affine multivariate
1069 evolution. */
1071 bool
1072 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1074 if (chrec == NULL_TREE)
1075 return false;
1077 switch (TREE_CODE (chrec))
1079 case POLYNOMIAL_CHREC:
1080 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1082 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1083 return true;
1084 else
1086 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1087 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1088 != CHREC_VARIABLE (chrec)
1089 && evolution_function_is_affine_multivariate_p
1090 (CHREC_RIGHT (chrec), loopnum))
1091 return true;
1092 else
1093 return false;
1096 else
1098 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1099 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1100 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1101 && evolution_function_is_affine_multivariate_p
1102 (CHREC_LEFT (chrec), loopnum))
1103 return true;
1104 else
1105 return false;
1108 default:
1109 return false;
1113 /* Determine whether the given tree is a function in zero or one
1114 variables. */
1116 bool
1117 evolution_function_is_univariate_p (const_tree chrec)
1119 if (chrec == NULL_TREE)
1120 return true;
1122 switch (TREE_CODE (chrec))
1124 case POLYNOMIAL_CHREC:
1125 switch (TREE_CODE (CHREC_LEFT (chrec)))
1127 case POLYNOMIAL_CHREC:
1128 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1129 return false;
1130 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1131 return false;
1132 break;
1134 default:
1135 if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1136 return false;
1137 break;
1140 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1142 case POLYNOMIAL_CHREC:
1143 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1144 return false;
1145 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1146 return false;
1147 break;
1149 default:
1150 if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1151 return false;
1152 break;
1155 default:
1156 return true;
1160 /* Returns the number of variables of CHREC. Example: the call
1161 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1163 unsigned
1164 nb_vars_in_chrec (tree chrec)
1166 if (chrec == NULL_TREE)
1167 return 0;
1169 switch (TREE_CODE (chrec))
1171 case POLYNOMIAL_CHREC:
1172 return 1 + nb_vars_in_chrec
1173 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1175 default:
1176 return 0;
1180 static tree chrec_convert_1 (tree, tree, gimple, bool);
1182 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1183 the scev corresponds to. AT_STMT is the statement at that the scev is
1184 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1185 the rules for overflow of the given language apply (e.g., that signed
1186 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1187 tests, but also to enforce that the result follows them. Returns true if the
1188 conversion succeeded, false otherwise. */
1190 bool
1191 convert_affine_scev (struct loop *loop, tree type,
1192 tree *base, tree *step, gimple at_stmt,
1193 bool use_overflow_semantics)
1195 tree ct = TREE_TYPE (*step);
1196 bool enforce_overflow_semantics;
1197 bool must_check_src_overflow, must_check_rslt_overflow;
1198 tree new_base, new_step;
1199 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1201 /* In general,
1202 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1203 but we must check some assumptions.
1205 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1206 of CT is smaller than the precision of TYPE. For example, when we
1207 cast unsigned char [254, +, 1] to unsigned, the values on left side
1208 are 254, 255, 0, 1, ..., but those on the right side are
1209 254, 255, 256, 257, ...
1210 2) In case that we must also preserve the fact that signed ivs do not
1211 overflow, we must additionally check that the new iv does not wrap.
1212 For example, unsigned char [125, +, 1] casted to signed char could
1213 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1214 which would confuse optimizers that assume that this does not
1215 happen. */
1216 must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1218 enforce_overflow_semantics = (use_overflow_semantics
1219 && nowrap_type_p (type));
1220 if (enforce_overflow_semantics)
1222 /* We can avoid checking whether the result overflows in the following
1223 cases:
1225 -- must_check_src_overflow is true, and the range of TYPE is superset
1226 of the range of CT -- i.e., in all cases except if CT signed and
1227 TYPE unsigned.
1228 -- both CT and TYPE have the same precision and signedness, and we
1229 verify instead that the source does not overflow (this may be
1230 easier than verifying it for the result, as we may use the
1231 information about the semantics of overflow in CT). */
1232 if (must_check_src_overflow)
1234 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1235 must_check_rslt_overflow = true;
1236 else
1237 must_check_rslt_overflow = false;
1239 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1240 && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1242 must_check_rslt_overflow = false;
1243 must_check_src_overflow = true;
1245 else
1246 must_check_rslt_overflow = true;
1248 else
1249 must_check_rslt_overflow = false;
1251 if (must_check_src_overflow
1252 && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1253 use_overflow_semantics))
1254 return false;
1256 new_base = chrec_convert_1 (type, *base, at_stmt,
1257 use_overflow_semantics);
1258 /* The step must be sign extended, regardless of the signedness
1259 of CT and TYPE. This only needs to be handled specially when
1260 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1261 (with values 100, 99, 98, ...) from becoming signed or unsigned
1262 [100, +, 255] with values 100, 355, ...; the sign-extension is
1263 performed by default when CT is signed. */
1264 new_step = *step;
1265 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1267 tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1268 new_step = chrec_convert_1 (signed_ct, new_step, at_stmt,
1269 use_overflow_semantics);
1271 new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
1273 if (automatically_generated_chrec_p (new_base)
1274 || automatically_generated_chrec_p (new_step))
1275 return false;
1277 if (must_check_rslt_overflow
1278 /* Note that in this case we cannot use the fact that signed variables
1279 do not overflow, as this is what we are verifying for the new iv. */
1280 && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1281 return false;
1283 *base = new_base;
1284 *step = new_step;
1285 return true;
1289 /* Convert CHREC for the right hand side of a CHREC.
1290 The increment for a pointer type is always sizetype. */
1292 tree
1293 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
1295 if (POINTER_TYPE_P (type))
1296 type = sizetype;
1298 return chrec_convert (type, chrec, at_stmt);
1301 /* Convert CHREC to TYPE. When the analyzer knows the context in
1302 which the CHREC is built, it sets AT_STMT to the statement that
1303 contains the definition of the analyzed variable, otherwise the
1304 conversion is less accurate: the information is used for
1305 determining a more accurate estimation of the number of iterations.
1306 By default AT_STMT could be safely set to NULL_TREE.
1308 The following rule is always true: TREE_TYPE (chrec) ==
1309 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1310 An example of what could happen when adding two chrecs and the type
1311 of the CHREC_RIGHT is different than CHREC_LEFT is:
1313 {(uint) 0, +, (uchar) 10} +
1314 {(uint) 0, +, (uchar) 250}
1316 that would produce a wrong result if CHREC_RIGHT is not (uint):
1318 {(uint) 0, +, (uchar) 4}
1320 instead of
1322 {(uint) 0, +, (uint) 260}
1325 tree
1326 chrec_convert (tree type, tree chrec, gimple at_stmt)
1328 return chrec_convert_1 (type, chrec, at_stmt, true);
1331 /* Convert CHREC to TYPE. When the analyzer knows the context in
1332 which the CHREC is built, it sets AT_STMT to the statement that
1333 contains the definition of the analyzed variable, otherwise the
1334 conversion is less accurate: the information is used for
1335 determining a more accurate estimation of the number of iterations.
1336 By default AT_STMT could be safely set to NULL_TREE.
1338 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1339 the rules for overflow of the given language apply (e.g., that signed
1340 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1341 tests, but also to enforce that the result follows them. */
1343 static tree
1344 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
1345 bool use_overflow_semantics)
1347 tree ct, res;
1348 tree base, step;
1349 struct loop *loop;
1351 if (automatically_generated_chrec_p (chrec))
1352 return chrec;
1354 ct = chrec_type (chrec);
1355 if (ct == type)
1356 return chrec;
1358 if (!evolution_function_is_affine_p (chrec))
1359 goto keep_cast;
1361 loop = get_chrec_loop (chrec);
1362 base = CHREC_LEFT (chrec);
1363 step = CHREC_RIGHT (chrec);
1365 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1366 use_overflow_semantics))
1367 return build_polynomial_chrec (loop->num, base, step);
1369 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1370 keep_cast:
1371 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1372 may be more expensive. We do want to perform this optimization here
1373 though for canonicalization reasons. */
1374 if (use_overflow_semantics
1375 && (TREE_CODE (chrec) == PLUS_EXPR
1376 || TREE_CODE (chrec) == MINUS_EXPR)
1377 && TREE_CODE (type) == INTEGER_TYPE
1378 && TREE_CODE (ct) == INTEGER_TYPE
1379 && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1380 && TYPE_OVERFLOW_UNDEFINED (ct))
1381 res = fold_build2 (TREE_CODE (chrec), type,
1382 fold_convert (type, TREE_OPERAND (chrec, 0)),
1383 fold_convert (type, TREE_OPERAND (chrec, 1)));
1384 /* Similar perform the trick that (signed char)((int)x + 2) can be
1385 narrowed to (signed char)((unsigned char)x + 2). */
1386 else if (use_overflow_semantics
1387 && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1388 && TREE_CODE (ct) == INTEGER_TYPE
1389 && TREE_CODE (type) == INTEGER_TYPE
1390 && TYPE_OVERFLOW_UNDEFINED (type)
1391 && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1393 tree utype = unsigned_type_for (type);
1394 res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1395 fold_convert (utype,
1396 CHREC_LEFT (chrec)),
1397 fold_convert (utype,
1398 CHREC_RIGHT (chrec)));
1399 res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics);
1401 else
1402 res = fold_convert (type, chrec);
1404 /* Don't propagate overflows. */
1405 if (CONSTANT_CLASS_P (res))
1406 TREE_OVERFLOW (res) = 0;
1408 /* But reject constants that don't fit in their type after conversion.
1409 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1410 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1411 and can cause problems later when computing niters of loops. Note
1412 that we don't do the check before converting because we don't want
1413 to reject conversions of negative chrecs to unsigned types. */
1414 if (TREE_CODE (res) == INTEGER_CST
1415 && TREE_CODE (type) == INTEGER_TYPE
1416 && !int_fits_type_p (res, type))
1417 res = chrec_dont_know;
1419 return res;
1422 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1423 chrec if something else than what chrec_convert would do happens, NULL_TREE
1424 otherwise. */
1426 tree
1427 chrec_convert_aggressive (tree type, tree chrec)
1429 tree inner_type, left, right, lc, rc, rtype;
1431 if (automatically_generated_chrec_p (chrec)
1432 || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1433 return NULL_TREE;
1435 inner_type = TREE_TYPE (chrec);
1436 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1437 return NULL_TREE;
1439 rtype = POINTER_TYPE_P (type) ? sizetype : type;
1441 left = CHREC_LEFT (chrec);
1442 right = CHREC_RIGHT (chrec);
1443 lc = chrec_convert_aggressive (type, left);
1444 if (!lc)
1445 lc = chrec_convert (type, left, NULL);
1446 rc = chrec_convert_aggressive (rtype, right);
1447 if (!rc)
1448 rc = chrec_convert (rtype, right, NULL);
1450 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1453 /* Returns true when CHREC0 == CHREC1. */
1455 bool
1456 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1458 if (chrec0 == NULL_TREE
1459 || chrec1 == NULL_TREE
1460 || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1461 return false;
1463 if (chrec0 == chrec1)
1464 return true;
1466 switch (TREE_CODE (chrec0))
1468 case INTEGER_CST:
1469 return operand_equal_p (chrec0, chrec1, 0);
1471 case POLYNOMIAL_CHREC:
1472 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1473 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1474 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1476 case PLUS_EXPR:
1477 case MULT_EXPR:
1478 case MINUS_EXPR:
1479 case POINTER_PLUS_EXPR:
1480 return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1481 TREE_OPERAND (chrec1, 0))
1482 && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1483 TREE_OPERAND (chrec1, 1));
1485 default:
1486 return false;
1490 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1491 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1492 which of these cases happens. */
1494 enum ev_direction
1495 scev_direction (const_tree chrec)
1497 const_tree step;
1499 if (!evolution_function_is_affine_p (chrec))
1500 return EV_DIR_UNKNOWN;
1502 step = CHREC_RIGHT (chrec);
1503 if (TREE_CODE (step) != INTEGER_CST)
1504 return EV_DIR_UNKNOWN;
1506 if (tree_int_cst_sign_bit (step))
1507 return EV_DIR_DECREASES;
1508 else
1509 return EV_DIR_GROWS;
1512 /* Iterates over all the components of SCEV, and calls CBCK. */
1514 void
1515 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1517 switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1519 case 3:
1520 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1522 case 2:
1523 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1525 case 1:
1526 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1528 default:
1529 cbck (scev, data);
1530 break;
1534 /* Returns true when the operation can be part of a linear
1535 expression. */
1537 static inline bool
1538 operator_is_linear (tree scev)
1540 switch (TREE_CODE (scev))
1542 case INTEGER_CST:
1543 case POLYNOMIAL_CHREC:
1544 case PLUS_EXPR:
1545 case POINTER_PLUS_EXPR:
1546 case MULT_EXPR:
1547 case MINUS_EXPR:
1548 case NEGATE_EXPR:
1549 case SSA_NAME:
1550 case NON_LVALUE_EXPR:
1551 case BIT_NOT_EXPR:
1552 CASE_CONVERT:
1553 return true;
1555 default:
1556 return false;
1560 /* Return true when SCEV is a linear expression. Linear expressions
1561 can contain additions, substractions and multiplications.
1562 Multiplications are restricted to constant scaling: "cst * x". */
1564 bool
1565 scev_is_linear_expression (tree scev)
1567 if (scev == NULL
1568 || !operator_is_linear (scev))
1569 return false;
1571 if (TREE_CODE (scev) == MULT_EXPR)
1572 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1573 && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1575 if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1576 && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1577 return false;
1579 switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1581 case 3:
1582 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1583 && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1584 && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1586 case 2:
1587 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1588 && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1590 case 1:
1591 return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1593 case 0:
1594 return true;
1596 default:
1597 return false;
1601 /* Determines whether the expression CHREC contains only interger consts
1602 in the right parts. */
1604 bool
1605 evolution_function_right_is_integer_cst (const_tree chrec)
1607 if (chrec == NULL_TREE)
1608 return false;
1610 switch (TREE_CODE (chrec))
1612 case INTEGER_CST:
1613 return true;
1615 case POLYNOMIAL_CHREC:
1616 return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1617 && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1618 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1620 CASE_CONVERT:
1621 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1623 default:
1624 return false;