* tree-ssa-loop-ivopts.c (struct cost_pair): Remove field inv_expr
[official-gcc.git] / gcc / tree-chrec.c
blob28c08e7115c3865790a771142563893f5b3284de
1 /* Chains of recurrences.
2 Copyright (C) 2003-2017 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 "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"
42 /* Extended folder for chrecs. */
44 /* Determines whether CST is not a constant evolution. */
46 static inline bool
47 is_not_constant_evolution (const_tree cst)
49 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
52 /* Fold CODE for a polynomial function and a constant. */
54 static inline tree
55 chrec_fold_poly_cst (enum tree_code code,
56 tree type,
57 tree poly,
58 tree cst)
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)));
66 switch (code)
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));
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));
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));
86 default:
87 return chrec_dont_know;
91 /* Fold the addition of two polynomial functions. */
93 static inline tree
94 chrec_fold_plus_poly_poly (enum tree_code code,
95 tree type,
96 tree poly0,
97 tree poly1)
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;
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)));
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))
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)));
136 if (flow_loop_nested_p (loop1, loop0))
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));
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)
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;
159 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
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));
166 else
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));
174 if (chrec_zerop (right))
175 return left;
176 else
177 return build_polynomial_chrec
178 (CHREC_VARIABLE (poly0), left, right);
183 /* Fold the multiplication of two polynomial functions. */
185 static inline tree
186 chrec_fold_multiply_poly_poly (tree type,
187 tree poly0,
188 tree poly1)
190 tree t0, t1, t2;
191 int var;
192 struct loop *loop0 = get_chrec_loop (poly0);
193 struct loop *loop1 = get_chrec_loop (poly1);
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)));
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));
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));
219 if (loop0 != loop1)
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;
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. */
229 /* "a*c". */
230 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
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);
246 var = CHREC_VARIABLE (poly0);
247 return build_polynomial_chrec (var, t0,
248 build_polynomial_chrec (var, t1, t2));
251 /* When the operands are automatically_generated_chrec_p, the fold has
252 to respect the semantics of the operands. */
254 static inline tree
255 chrec_fold_automatically_generated_operands (tree op0,
256 tree op1)
258 if (op0 == chrec_dont_know
259 || op1 == chrec_dont_know)
260 return chrec_dont_know;
262 if (op0 == chrec_known
263 || op1 == chrec_known)
264 return chrec_known;
266 if (op0 == chrec_not_analyzed_yet
267 || op1 == chrec_not_analyzed_yet)
268 return chrec_not_analyzed_yet;
270 /* The default case produces a safe result. */
271 return chrec_dont_know;
274 /* Fold the addition of two chrecs. */
276 static tree
277 chrec_fold_plus_1 (enum tree_code code, tree type,
278 tree op0, tree op1)
280 if (automatically_generated_chrec_p (op0)
281 || automatically_generated_chrec_p (op1))
282 return chrec_fold_automatically_generated_operands (op0, op1);
284 switch (TREE_CODE (op0))
286 case POLYNOMIAL_CHREC:
287 gcc_checking_assert
288 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
289 switch (TREE_CODE (op1))
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);
297 CASE_CONVERT:
298 if (tree_contains_chrecs (op1, NULL))
299 return chrec_dont_know;
300 /* FALLTHRU */
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));
315 CASE_CONVERT:
316 if (tree_contains_chrecs (op0, NULL))
317 return chrec_dont_know;
318 /* FALLTHRU */
320 default:
321 switch (TREE_CODE (op1))
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)));
341 CASE_CONVERT:
342 if (tree_contains_chrecs (op1, NULL))
343 return chrec_dont_know;
344 /* FALLTHRU */
346 default:
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))
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));
363 else
364 return chrec_dont_know;
370 /* Fold the addition of two chrecs. */
372 tree
373 chrec_fold_plus (tree type,
374 tree op0,
375 tree op1)
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);
382 if (integer_zerop (op0))
383 return chrec_convert (type, op1, NULL);
384 if (integer_zerop (op1))
385 return chrec_convert (type, op0, NULL);
387 if (POINTER_TYPE_P (type))
388 code = POINTER_PLUS_EXPR;
389 else
390 code = PLUS_EXPR;
392 return chrec_fold_plus_1 (code, type, op0, op1);
395 /* Fold the subtraction of two chrecs. */
397 tree
398 chrec_fold_minus (tree type,
399 tree op0,
400 tree op1)
402 if (automatically_generated_chrec_p (op0)
403 || automatically_generated_chrec_p (op1))
404 return chrec_fold_automatically_generated_operands (op0, op1);
406 if (integer_zerop (op1))
407 return op0;
409 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
412 /* Fold the multiplication of two chrecs. */
414 tree
415 chrec_fold_multiply (tree type,
416 tree op0,
417 tree op1)
419 if (automatically_generated_chrec_p (op0)
420 || automatically_generated_chrec_p (op1))
421 return chrec_fold_automatically_generated_operands (op0, op1);
423 switch (TREE_CODE (op0))
425 case POLYNOMIAL_CHREC:
426 gcc_checking_assert
427 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
428 switch (TREE_CODE (op1))
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);
436 CASE_CONVERT:
437 if (tree_contains_chrecs (op1, NULL))
438 return chrec_dont_know;
439 /* FALLTHRU */
441 default:
442 if (integer_onep (op1))
443 return op0;
444 if (integer_zerop (op1))
445 return build_int_cst (type, 0);
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));
453 CASE_CONVERT:
454 if (tree_contains_chrecs (op0, NULL))
455 return chrec_dont_know;
456 /* FALLTHRU */
458 default:
459 if (integer_onep (op0))
460 return op1;
462 if (integer_zerop (op0))
463 return build_int_cst (type, 0);
465 switch (TREE_CODE (op1))
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));
476 CASE_CONVERT:
477 if (tree_contains_chrecs (op1, NULL))
478 return chrec_dont_know;
479 /* FALLTHRU */
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);
493 /* Operations. */
495 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
496 calculation overflows, otherwise return C(n,k) with type TYPE. */
498 static tree
499 tree_fold_binomial (tree type, tree n, unsigned int k)
501 bool overflow;
502 unsigned int i;
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);
510 widest_int num = wi::to_widest (n);
512 /* Check that k <= n. */
513 if (wi::ltu_p (num, k))
514 return NULL_TREE;
516 /* Denominator = 2. */
517 widest_int denom = 2;
519 /* Index = Numerator-1. */
520 widest_int idx = num - 1;
522 /* Numerator = Numerator*Index = n*(n-1). */
523 num = wi::smul (num, 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 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);
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. */
552 static tree
553 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
555 tree arg0, arg1, binomial_n_k;
556 tree type = TREE_TYPE (chrec);
557 struct loop *var_loop = get_loop (cfun, var);
559 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
560 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
561 chrec = CHREC_LEFT (chrec);
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);
570 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
571 && CHREC_VARIABLE (chrec) == var)
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);
584 binomial_n_k = tree_fold_binomial (ctype, n, k);
585 if (!binomial_n_k)
586 return chrec_dont_know;
588 return fold_build2 (MULT_EXPR, ctype,
589 chrec_convert (ctype, chrec, NULL), binomial_n_k);
592 /* Evaluates "CHREC (X)" when the varying variable is VAR.
593 Example: Given the following parameters,
595 var = 1
596 chrec = {3, +, 4}_1
597 x = 10
599 The result is given by the Newton's interpolating formula:
600 3 * \binom{10}{0} + 4 * \binom{10}{1}.
603 tree
604 chrec_apply (unsigned var,
605 tree chrec,
606 tree x)
608 tree type = chrec_type (chrec);
609 tree res = chrec_dont_know;
611 if (automatically_generated_chrec_p (chrec)
612 || automatically_generated_chrec_p (x)
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;
620 if (dump_file && (dump_flags & TDF_SCEV))
621 fprintf (dump_file, "(chrec_apply \n");
623 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
624 x = build_real_from_int_cst (type, x);
626 switch (TREE_CODE (chrec))
628 case POLYNOMIAL_CHREC:
629 if (evolution_function_is_affine_p (chrec))
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));
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);
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;
650 CASE_CONVERT:
651 res = chrec_convert (TREE_TYPE (chrec),
652 chrec_apply (var, TREE_OPERAND (chrec, 0), x),
653 NULL);
654 break;
656 default:
657 res = chrec;
658 break;
661 if (dump_file && (dump_flags & TDF_SCEV))
663 fprintf (dump_file, " (varying_loop = %d\n", var);
664 fprintf (dump_file, ")\n (chrec = ");
665 print_generic_expr (dump_file, chrec, 0);
666 fprintf (dump_file, ")\n (x = ");
667 print_generic_expr (dump_file, x, 0);
668 fprintf (dump_file, ")\n (res = ");
669 print_generic_expr (dump_file, res, 0);
670 fprintf (dump_file, "))\n");
673 return res;
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. */
680 tree
681 chrec_apply_map (tree chrec, vec<tree> iv_map)
683 int i;
684 tree expr;
686 FOR_EACH_VEC_ELT (iv_map, i, expr)
687 if (expr)
688 chrec = chrec_apply (i, chrec, expr);
690 return chrec;
693 /* Replaces the initial condition in CHREC with INIT_COND. */
695 tree
696 chrec_replace_initial_condition (tree chrec,
697 tree init_cond)
699 if (automatically_generated_chrec_p (chrec))
700 return chrec;
702 gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
704 switch (TREE_CODE (chrec))
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));
712 default:
713 return init_cond;
717 /* Returns the initial condition of a given CHREC. */
719 tree
720 initial_condition (tree chrec)
722 if (automatically_generated_chrec_p (chrec))
723 return chrec;
725 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
726 return initial_condition (CHREC_LEFT (chrec));
727 else
728 return chrec;
731 /* Returns a univariate function that represents the evolution in
732 LOOP_NUM. Mask the evolution of any other loop. */
734 tree
735 hide_evolution_in_other_loops_than_loop (tree chrec,
736 unsigned loop_num)
738 struct loop *loop = get_loop (cfun, loop_num), *chloop;
739 if (automatically_generated_chrec_p (chrec))
740 return chrec;
742 switch (TREE_CODE (chrec))
744 case POLYNOMIAL_CHREC:
745 chloop = get_chrec_loop (chrec);
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));
754 else if (flow_loop_nested_p (chloop, loop))
755 /* There is no evolution in this loop. */
756 return initial_condition (chrec);
758 else if (flow_loop_nested_p (loop, chloop))
759 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
760 loop_num);
762 else
763 return chrec_dont_know;
765 default:
766 return chrec;
770 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
771 true, otherwise returns the initial condition in LOOP_NUM. */
773 static tree
774 chrec_component_in_loop_num (tree chrec,
775 unsigned loop_num,
776 bool right)
778 tree component;
779 struct loop *loop = get_loop (cfun, loop_num), *chloop;
781 if (automatically_generated_chrec_p (chrec))
782 return chrec;
784 switch (TREE_CODE (chrec))
786 case POLYNOMIAL_CHREC:
787 chloop = get_chrec_loop (chrec);
789 if (chloop == loop)
791 if (right)
792 component = CHREC_RIGHT (chrec);
793 else
794 component = CHREC_LEFT (chrec);
796 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
797 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
798 return component;
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);
809 else if (flow_loop_nested_p (chloop, loop))
810 /* There is no evolution part in this loop. */
811 return NULL_TREE;
813 else
815 gcc_assert (flow_loop_nested_p (loop, chloop));
816 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
817 loop_num,
818 right);
821 default:
822 if (right)
823 return NULL_TREE;
824 else
825 return chrec;
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 */
833 tree
834 evolution_part_in_loop_num (tree chrec,
835 unsigned loop_num)
837 return chrec_component_in_loop_num (chrec, loop_num, true);
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 */
844 tree
845 initial_condition_in_loop_num (tree chrec,
846 unsigned loop_num)
848 return chrec_component_in_loop_num (chrec, loop_num, false);
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. */
856 tree
857 reset_evolution_in_loop (unsigned loop_num,
858 tree chrec,
859 tree new_evol)
861 struct loop *loop = get_loop (cfun, loop_num);
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));
868 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
869 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
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 build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
876 CHREC_VAR (chrec), left, right);
879 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
880 && CHREC_VARIABLE (chrec) == loop_num)
881 chrec = CHREC_LEFT (chrec);
883 return build_polynomial_chrec (loop_num, chrec, new_evol);
886 /* Merges two evolution functions that were found by following two
887 alternate paths of a conditional expression. */
889 tree
890 chrec_merge (tree chrec1,
891 tree chrec2)
893 if (chrec1 == chrec_dont_know
894 || chrec2 == chrec_dont_know)
895 return chrec_dont_know;
897 if (chrec1 == chrec_known
898 || chrec2 == chrec_known)
899 return chrec_known;
901 if (chrec1 == chrec_not_analyzed_yet)
902 return chrec2;
903 if (chrec2 == chrec_not_analyzed_yet)
904 return chrec1;
906 if (eq_evolutions_p (chrec1, chrec2))
907 return chrec1;
909 return chrec_dont_know;
914 /* Observers. */
916 /* Helper function for is_multivariate_chrec. */
918 static bool
919 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
921 if (chrec == NULL_TREE)
922 return false;
924 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
926 if (CHREC_VARIABLE (chrec) != rec_var)
927 return true;
928 else
929 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
930 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
932 else
933 return false;
936 /* Determine whether the given chrec is multivariate or not. */
938 bool
939 is_multivariate_chrec (const_tree chrec)
941 if (chrec == NULL_TREE)
942 return false;
944 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
945 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
946 CHREC_VARIABLE (chrec))
947 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
948 CHREC_VARIABLE (chrec)));
949 else
950 return false;
953 /* Determines whether the chrec contains symbolic names or not. */
955 bool
956 chrec_contains_symbols (const_tree chrec)
958 int i, n;
960 if (chrec == NULL_TREE)
961 return false;
963 if (TREE_CODE (chrec) == SSA_NAME
964 || VAR_P (chrec)
965 || TREE_CODE (chrec) == PARM_DECL
966 || TREE_CODE (chrec) == FUNCTION_DECL
967 || TREE_CODE (chrec) == LABEL_DECL
968 || TREE_CODE (chrec) == RESULT_DECL
969 || TREE_CODE (chrec) == FIELD_DECL)
970 return true;
972 n = TREE_OPERAND_LENGTH (chrec);
973 for (i = 0; i < n; i++)
974 if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
975 return true;
976 return false;
979 /* Determines whether the chrec contains undetermined coefficients. */
981 bool
982 chrec_contains_undetermined (const_tree chrec)
984 int i, n;
986 if (chrec == chrec_dont_know)
987 return true;
989 if (chrec == NULL_TREE)
990 return false;
992 n = TREE_OPERAND_LENGTH (chrec);
993 for (i = 0; i < n; i++)
994 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
995 return true;
996 return false;
999 /* Determines whether the tree EXPR contains chrecs, and increment
1000 SIZE if it is not a NULL pointer by an estimation of the depth of
1001 the tree. */
1003 bool
1004 tree_contains_chrecs (const_tree expr, int *size)
1006 int i, n;
1008 if (expr == NULL_TREE)
1009 return false;
1011 if (size)
1012 (*size)++;
1014 if (tree_is_chrec (expr))
1015 return true;
1017 n = TREE_OPERAND_LENGTH (expr);
1018 for (i = 0; i < n; i++)
1019 if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
1020 return true;
1021 return false;
1024 /* Recursive helper function. */
1026 static bool
1027 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1029 if (evolution_function_is_constant_p (chrec))
1030 return true;
1032 if (TREE_CODE (chrec) == SSA_NAME
1033 && (loopnum == 0
1034 || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1035 return true;
1037 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1039 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1040 || flow_loop_nested_p (get_loop (cfun, loopnum),
1041 get_chrec_loop (chrec))
1042 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1043 loopnum)
1044 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1045 loopnum))
1046 return false;
1047 return true;
1050 switch (TREE_OPERAND_LENGTH (chrec))
1052 case 2:
1053 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1054 loopnum))
1055 return false;
1056 /* FALLTHRU */
1058 case 1:
1059 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1060 loopnum))
1061 return false;
1062 return true;
1064 default:
1065 return false;
1068 return false;
1071 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1073 bool
1074 evolution_function_is_invariant_p (tree chrec, int loopnum)
1076 return evolution_function_is_invariant_rec_p (chrec, loopnum);
1079 /* Determine whether the given tree is an affine multivariate
1080 evolution. */
1082 bool
1083 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1085 if (chrec == NULL_TREE)
1086 return false;
1088 switch (TREE_CODE (chrec))
1090 case POLYNOMIAL_CHREC:
1091 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1093 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1094 return true;
1095 else
1097 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1098 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1099 != CHREC_VARIABLE (chrec)
1100 && evolution_function_is_affine_multivariate_p
1101 (CHREC_RIGHT (chrec), loopnum))
1102 return true;
1103 else
1104 return false;
1107 else
1109 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1110 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1111 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1112 && evolution_function_is_affine_multivariate_p
1113 (CHREC_LEFT (chrec), loopnum))
1114 return true;
1115 else
1116 return false;
1119 default:
1120 return false;
1124 /* Determine whether the given tree is a function in zero or one
1125 variables. */
1127 bool
1128 evolution_function_is_univariate_p (const_tree chrec)
1130 if (chrec == NULL_TREE)
1131 return true;
1133 switch (TREE_CODE (chrec))
1135 case POLYNOMIAL_CHREC:
1136 switch (TREE_CODE (CHREC_LEFT (chrec)))
1138 case POLYNOMIAL_CHREC:
1139 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1140 return false;
1141 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1142 return false;
1143 break;
1145 default:
1146 if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1147 return false;
1148 break;
1151 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1153 case POLYNOMIAL_CHREC:
1154 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1155 return false;
1156 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1157 return false;
1158 break;
1160 default:
1161 if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1162 return false;
1163 break;
1166 default:
1167 return true;
1171 /* Returns the number of variables of CHREC. Example: the call
1172 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1174 unsigned
1175 nb_vars_in_chrec (tree chrec)
1177 if (chrec == NULL_TREE)
1178 return 0;
1180 switch (TREE_CODE (chrec))
1182 case POLYNOMIAL_CHREC:
1183 return 1 + nb_vars_in_chrec
1184 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1186 default:
1187 return 0;
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. */
1200 bool
1201 convert_affine_scev (struct loop *loop, tree type,
1202 tree *base, tree *step, gimple *at_stmt,
1203 bool use_overflow_semantics, tree from)
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;
1211 /* In general,
1212 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1213 but we must check some assumptions.
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);
1228 enforce_overflow_semantics = (use_overflow_semantics
1229 && nowrap_type_p (type));
1230 if (enforce_overflow_semantics)
1232 /* We can avoid checking whether the result overflows in the following
1233 cases:
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)
1244 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1245 must_check_rslt_overflow = true;
1246 else
1247 must_check_rslt_overflow = false;
1249 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1250 && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1252 must_check_rslt_overflow = false;
1253 must_check_src_overflow = true;
1255 else
1256 must_check_rslt_overflow = true;
1258 else
1259 must_check_rslt_overflow = false;
1261 if (must_check_src_overflow
1262 && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1263 use_overflow_semantics))
1264 return false;
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))
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);
1280 new_step = chrec_convert (step_type, new_step, at_stmt,
1281 use_overflow_semantics);
1283 if (automatically_generated_chrec_p (new_base)
1284 || automatically_generated_chrec_p (new_step))
1285 return false;
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;
1294 *base = new_base;
1295 *step = new_step;
1296 return true;
1300 /* Convert CHREC for the right hand side of a CHREC.
1301 The increment for a pointer type is always sizetype. */
1303 tree
1304 chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1306 if (POINTER_TYPE_P (type))
1307 type = sizetype;
1309 return chrec_convert (type, chrec, at_stmt);
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.
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.
1324 FROM is the source variable converted if it's not NULL. */
1326 static tree
1327 chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1328 bool use_overflow_semantics, tree from)
1330 tree ct, res;
1331 tree base, step;
1332 struct loop *loop;
1334 if (automatically_generated_chrec_p (chrec))
1335 return chrec;
1337 ct = chrec_type (chrec);
1338 if (useless_type_conversion_p (type, ct))
1339 return chrec;
1341 if (!evolution_function_is_affine_p (chrec))
1342 goto keep_cast;
1344 loop = get_chrec_loop (chrec);
1345 base = CHREC_LEFT (chrec);
1346 step = CHREC_RIGHT (chrec);
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);
1352 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1353 keep_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))
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);
1384 else
1385 res = fold_convert (type, chrec);
1387 /* Don't propagate overflows. */
1388 if (CONSTANT_CLASS_P (res))
1389 TREE_OVERFLOW (res) = 0;
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;
1402 return res;
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.
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:
1417 {(uint) 0, +, (uchar) 10} +
1418 {(uint) 0, +, (uchar) 250}
1420 that would produce a wrong result if CHREC_RIGHT is not (uint):
1422 {(uint) 0, +, (uchar) 4}
1424 instead of
1426 {(uint) 0, +, (uint) 260}
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.
1433 FROM is the source variable converted if it's not NULL. */
1435 tree
1436 chrec_convert (tree type, tree chrec, gimple *at_stmt,
1437 bool use_overflow_semantics, tree from)
1439 return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
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. */
1447 tree
1448 chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1450 tree inner_type, left, right, lc, rc, rtype;
1452 gcc_assert (fold_conversions != NULL);
1454 if (automatically_generated_chrec_p (chrec)
1455 || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1456 return NULL_TREE;
1458 inner_type = TREE_TYPE (chrec);
1459 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1460 return NULL_TREE;
1462 if (useless_type_conversion_p (type, inner_type))
1463 return NULL_TREE;
1465 if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1467 tree base, step;
1468 struct loop *loop;
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);
1476 rtype = POINTER_TYPE_P (type) ? sizetype : type;
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);
1487 *fold_conversions = true;
1489 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1492 /* Returns true when CHREC0 == CHREC1. */
1494 bool
1495 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1497 if (chrec0 == NULL_TREE
1498 || chrec1 == NULL_TREE
1499 || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1500 return false;
1502 if (chrec0 == chrec1)
1503 return true;
1505 if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1506 return false;
1508 switch (TREE_CODE (chrec0))
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)));
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));
1524 CASE_CONVERT:
1525 return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1526 TREE_OPERAND (chrec1, 0));
1528 default:
1529 return operand_equal_p (chrec0, chrec1, 0);
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. */
1537 enum ev_direction
1538 scev_direction (const_tree chrec)
1540 const_tree step;
1542 if (!evolution_function_is_affine_p (chrec))
1543 return EV_DIR_UNKNOWN;
1545 step = CHREC_RIGHT (chrec);
1546 if (TREE_CODE (step) != INTEGER_CST)
1547 return EV_DIR_UNKNOWN;
1549 if (tree_int_cst_sign_bit (step))
1550 return EV_DIR_DECREASES;
1551 else
1552 return EV_DIR_GROWS;
1555 /* Iterates over all the components of SCEV, and calls CBCK. */
1557 void
1558 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1560 switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1562 case 3:
1563 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1564 /* FALLTHRU */
1566 case 2:
1567 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1568 /* FALLTHRU */
1570 case 1:
1571 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1572 /* FALLTHRU */
1574 default:
1575 cbck (scev, data);
1576 break;
1580 /* Returns true when the operation can be part of a linear
1581 expression. */
1583 static inline bool
1584 operator_is_linear (tree scev)
1586 switch (TREE_CODE (scev))
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;
1601 default:
1602 return false;
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". */
1610 bool
1611 scev_is_linear_expression (tree scev)
1613 if (scev == NULL
1614 || !operator_is_linear (scev))
1615 return false;
1617 if (TREE_CODE (scev) == MULT_EXPR)
1618 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1619 && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1621 if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1622 && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1623 return false;
1625 switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1627 case 3:
1628 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1629 && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1630 && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1632 case 2:
1633 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1634 && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1636 case 1:
1637 return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1639 case 0:
1640 return true;
1642 default:
1643 return false;
1647 /* Determines whether the expression CHREC contains only interger consts
1648 in the right parts. */
1650 bool
1651 evolution_function_right_is_integer_cst (const_tree chrec)
1653 if (chrec == NULL_TREE)
1654 return false;
1656 switch (TREE_CODE (chrec))
1658 case INTEGER_CST:
1659 return true;
1661 case POLYNOMIAL_CHREC:
1662 return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1663 && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1664 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1666 CASE_CONVERT:
1667 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1669 default:
1670 return false;