1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
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 2, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file implements operations on chains of recurrences. Chains
23 of recurrences are used for modeling evolution functions of scalar
29 #include "coretypes.h"
34 #include "diagnostic.h"
36 #include "tree-chrec.h"
37 #include "tree-pass.h"
41 /* Extended folder for chrecs. */
43 /* Determines whether CST is not a constant evolution. */
46 is_not_constant_evolution (tree cst)
48 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
51 /* Fold CODE for a polynomial function and a constant. */
54 chrec_fold_poly_cst (enum tree_code code,
61 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
62 gcc_assert (!is_not_constant_evolution (cst));
67 return build_polynomial_chrec
68 (CHREC_VARIABLE (poly),
69 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
73 return build_polynomial_chrec
74 (CHREC_VARIABLE (poly),
75 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
79 return build_polynomial_chrec
80 (CHREC_VARIABLE (poly),
81 chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
82 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
85 return chrec_dont_know;
89 /* Fold the addition of two polynomial functions. */
92 chrec_fold_plus_poly_poly (enum tree_code code,
101 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
102 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
105 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
106 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
107 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
108 if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
110 if (code == PLUS_EXPR)
111 return build_polynomial_chrec
112 (CHREC_VARIABLE (poly1),
113 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
114 CHREC_RIGHT (poly1));
116 return build_polynomial_chrec
117 (CHREC_VARIABLE (poly1),
118 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
119 chrec_fold_multiply (type, CHREC_RIGHT (poly1),
120 build_int_cst_type (type, -1)));
123 if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
125 if (code == PLUS_EXPR)
126 return build_polynomial_chrec
127 (CHREC_VARIABLE (poly0),
128 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
129 CHREC_RIGHT (poly0));
131 return build_polynomial_chrec
132 (CHREC_VARIABLE (poly0),
133 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
134 CHREC_RIGHT (poly0));
137 if (code == PLUS_EXPR)
139 left = chrec_fold_plus
140 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
141 right = chrec_fold_plus
142 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
146 left = chrec_fold_minus
147 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
148 right = chrec_fold_minus
149 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
152 if (chrec_zerop (right))
155 return build_polynomial_chrec
156 (CHREC_VARIABLE (poly0), left, right);
161 /* Fold the multiplication of two polynomial functions. */
164 chrec_fold_multiply_poly_poly (tree type,
170 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
171 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
173 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
174 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
175 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
176 if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
177 /* poly0 is a constant wrt. poly1. */
178 return build_polynomial_chrec
179 (CHREC_VARIABLE (poly1),
180 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
181 CHREC_RIGHT (poly1));
183 if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
184 /* poly1 is a constant wrt. poly0. */
185 return build_polynomial_chrec
186 (CHREC_VARIABLE (poly0),
187 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
188 CHREC_RIGHT (poly0));
190 /* poly0 and poly1 are two polynomials in the same variable,
191 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
193 build_polynomial_chrec
194 (CHREC_VARIABLE (poly0),
195 build_polynomial_chrec
196 (CHREC_VARIABLE (poly0),
199 chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)),
201 /* "a*d + b*c + b*d". */
203 (type, chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)),
207 chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_LEFT (poly1)),
208 chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))))),
212 (type, build_int_cst (NULL_TREE, 2),
213 chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))));
216 /* When the operands are automatically_generated_chrec_p, the fold has
217 to respect the semantics of the operands. */
220 chrec_fold_automatically_generated_operands (tree op0,
223 if (op0 == chrec_dont_know
224 || op1 == chrec_dont_know)
225 return chrec_dont_know;
227 if (op0 == chrec_known
228 || op1 == chrec_known)
231 if (op0 == chrec_not_analyzed_yet
232 || op1 == chrec_not_analyzed_yet)
233 return chrec_not_analyzed_yet;
235 /* The default case produces a safe result. */
236 return chrec_dont_know;
239 /* Fold the addition of two chrecs. */
242 chrec_fold_plus_1 (enum tree_code code,
247 if (automatically_generated_chrec_p (op0)
248 || automatically_generated_chrec_p (op1))
249 return chrec_fold_automatically_generated_operands (op0, op1);
251 switch (TREE_CODE (op0))
253 case POLYNOMIAL_CHREC:
254 switch (TREE_CODE (op1))
256 case POLYNOMIAL_CHREC:
257 return chrec_fold_plus_poly_poly (code, type, op0, op1);
260 if (code == PLUS_EXPR)
261 return build_polynomial_chrec
262 (CHREC_VARIABLE (op0),
263 chrec_fold_plus (type, CHREC_LEFT (op0), op1),
266 return build_polynomial_chrec
267 (CHREC_VARIABLE (op0),
268 chrec_fold_minus (type, CHREC_LEFT (op0), op1),
273 switch (TREE_CODE (op1))
275 case POLYNOMIAL_CHREC:
276 if (code == PLUS_EXPR)
277 return build_polynomial_chrec
278 (CHREC_VARIABLE (op1),
279 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
282 return build_polynomial_chrec
283 (CHREC_VARIABLE (op1),
284 chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
285 chrec_fold_multiply (type, CHREC_RIGHT (op1),
286 build_int_cst_type (type, -1)));
289 if (tree_contains_chrecs (op0)
290 || tree_contains_chrecs (op1))
291 return build (code, type, op0, op1);
293 return fold (build (code, type, op0, op1));
298 /* Fold the addition of two chrecs. */
301 chrec_fold_plus (tree type,
305 if (integer_zerop (op0))
307 if (integer_zerop (op1))
310 return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
313 /* Fold the subtraction of two chrecs. */
316 chrec_fold_minus (tree type,
320 if (integer_zerop (op1))
323 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
326 /* Fold the multiplication of two chrecs. */
329 chrec_fold_multiply (tree type,
333 if (automatically_generated_chrec_p (op0)
334 || automatically_generated_chrec_p (op1))
335 return chrec_fold_automatically_generated_operands (op0, op1);
337 switch (TREE_CODE (op0))
339 case POLYNOMIAL_CHREC:
340 switch (TREE_CODE (op1))
342 case POLYNOMIAL_CHREC:
343 return chrec_fold_multiply_poly_poly (type, op0, op1);
346 if (integer_onep (op1))
348 if (integer_zerop (op1))
349 return build_int_cst_type (type, 0);
351 return build_polynomial_chrec
352 (CHREC_VARIABLE (op0),
353 chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
354 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
358 if (integer_onep (op0))
361 if (integer_zerop (op0))
362 return build_int_cst_type (type, 0);
364 switch (TREE_CODE (op1))
366 case POLYNOMIAL_CHREC:
367 return build_polynomial_chrec
368 (CHREC_VARIABLE (op1),
369 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
370 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
373 if (integer_onep (op1))
375 if (integer_zerop (op1))
376 return build_int_cst_type (type, 0);
377 return fold (build (MULT_EXPR, type, op0, op1));
386 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
387 calculation overflows, otherwise return C(n,k) with type TYPE. */
390 tree_fold_binomial (tree type, tree n, unsigned int k)
392 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
393 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
397 /* Handle the most frequent cases. */
399 return build_int_cst (type, 1);
401 return fold_convert (type, n);
403 /* Check that k <= n. */
404 if (TREE_INT_CST_HIGH (n) == 0
405 && TREE_INT_CST_LOW (n) < k)
409 lnum = TREE_INT_CST_LOW (n);
410 hnum = TREE_INT_CST_HIGH (n);
412 /* Denominator = 2. */
416 /* Index = Numerator-1. */
420 lidx = ~ (unsigned HOST_WIDE_INT) 0;
428 /* Numerator = Numerator*Index = n*(n-1). */
429 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
432 for (i = 3; i <= k; i++)
438 lidx = ~ (unsigned HOST_WIDE_INT) 0;
443 /* Numerator *= Index. */
444 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
447 /* Denominator *= i. */
448 mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
451 /* Result = Numerator / Denominator. */
452 div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
453 &lres, &hres, &ldum, &hdum);
455 res = build_int_cst_wide (type, lres, hres);
456 return int_fits_type_p (res, type) ? res : NULL_TREE;
459 /* Helper function. Use the Newton's interpolating formula for
460 evaluating the value of the evolution function. */
463 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
465 tree arg0, arg1, binomial_n_k;
466 tree type = TREE_TYPE (chrec);
468 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
469 && CHREC_VARIABLE (chrec) > var)
470 chrec = CHREC_LEFT (chrec);
472 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
473 && CHREC_VARIABLE (chrec) == var)
475 arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
476 if (arg0 == chrec_dont_know)
477 return chrec_dont_know;
478 binomial_n_k = tree_fold_binomial (type, n, k);
480 return chrec_dont_know;
481 arg1 = fold (build2 (MULT_EXPR, type,
482 CHREC_LEFT (chrec), binomial_n_k));
483 return chrec_fold_plus (type, arg0, arg1);
486 binomial_n_k = tree_fold_binomial (type, n, k);
488 return chrec_dont_know;
490 return fold (build2 (MULT_EXPR, type, chrec, binomial_n_k));
493 /* Evaluates "CHREC (X)" when the varying variable is VAR.
494 Example: Given the following parameters,
500 The result is given by the Newton's interpolating formula:
501 3 * \binom{10}{0} + 4 * \binom{10}{1}.
505 chrec_apply (unsigned var,
509 tree type = chrec_type (chrec);
510 tree res = chrec_dont_know;
512 if (automatically_generated_chrec_p (chrec)
513 || automatically_generated_chrec_p (x)
515 /* When the symbols are defined in an outer loop, it is possible
516 to symbolically compute the apply, since the symbols are
517 constants with respect to the varying loop. */
518 || chrec_contains_symbols_defined_in_loop (chrec, var)
519 || chrec_contains_symbols (x))
520 return chrec_dont_know;
522 if (dump_file && (dump_flags & TDF_DETAILS))
523 fprintf (dump_file, "(chrec_apply \n");
525 if (evolution_function_is_affine_p (chrec))
527 /* "{a, +, b} (x)" -> "a + b*x". */
528 if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
529 && integer_zerop (CHREC_LEFT (chrec)))
530 res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
533 res = chrec_fold_plus (type, CHREC_LEFT (chrec),
534 chrec_fold_multiply (type,
535 CHREC_RIGHT (chrec), x));
538 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
541 else if (TREE_CODE (x) == INTEGER_CST
542 && tree_int_cst_sgn (x) == 1)
543 /* testsuite/.../ssa-chrec-38.c. */
544 res = chrec_evaluate (var, chrec, x, 0);
547 res = chrec_dont_know;
549 if (dump_file && (dump_flags & TDF_DETAILS))
551 fprintf (dump_file, " (varying_loop = %d\n", var);
552 fprintf (dump_file, ")\n (chrec = ");
553 print_generic_expr (dump_file, chrec, 0);
554 fprintf (dump_file, ")\n (x = ");
555 print_generic_expr (dump_file, x, 0);
556 fprintf (dump_file, ")\n (res = ");
557 print_generic_expr (dump_file, res, 0);
558 fprintf (dump_file, "))\n");
564 /* Replaces the initial condition in CHREC with INIT_COND. */
567 chrec_replace_initial_condition (tree chrec,
570 if (automatically_generated_chrec_p (chrec))
573 switch (TREE_CODE (chrec))
575 case POLYNOMIAL_CHREC:
576 return build_polynomial_chrec
577 (CHREC_VARIABLE (chrec),
578 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
579 CHREC_RIGHT (chrec));
586 /* Returns the initial condition of a given CHREC. */
589 initial_condition (tree chrec)
591 if (automatically_generated_chrec_p (chrec))
594 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
595 return initial_condition (CHREC_LEFT (chrec));
600 /* Returns a univariate function that represents the evolution in
601 LOOP_NUM. Mask the evolution of any other loop. */
604 hide_evolution_in_other_loops_than_loop (tree chrec,
607 if (automatically_generated_chrec_p (chrec))
610 switch (TREE_CODE (chrec))
612 case POLYNOMIAL_CHREC:
613 if (CHREC_VARIABLE (chrec) == loop_num)
614 return build_polynomial_chrec
616 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
618 CHREC_RIGHT (chrec));
620 else if (CHREC_VARIABLE (chrec) < loop_num)
621 /* There is no evolution in this loop. */
622 return initial_condition (chrec);
625 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
633 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
634 true, otherwise returns the initial condition in LOOP_NUM. */
637 chrec_component_in_loop_num (tree chrec,
643 if (automatically_generated_chrec_p (chrec))
646 switch (TREE_CODE (chrec))
648 case POLYNOMIAL_CHREC:
649 if (CHREC_VARIABLE (chrec) == loop_num)
652 component = CHREC_RIGHT (chrec);
654 component = CHREC_LEFT (chrec);
656 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
657 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
661 return build_polynomial_chrec
663 chrec_component_in_loop_num (CHREC_LEFT (chrec),
669 else if (CHREC_VARIABLE (chrec) < loop_num)
670 /* There is no evolution part in this loop. */
674 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
686 /* Returns the evolution part in LOOP_NUM. Example: the call
687 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
691 evolution_part_in_loop_num (tree chrec,
694 return chrec_component_in_loop_num (chrec, loop_num, true);
697 /* Returns the initial condition in LOOP_NUM. Example: the call
698 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
702 initial_condition_in_loop_num (tree chrec,
705 return chrec_component_in_loop_num (chrec, loop_num, false);
708 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
709 This function is essentially used for setting the evolution to
710 chrec_dont_know, for example after having determined that it is
711 impossible to say how many times a loop will execute. */
714 reset_evolution_in_loop (unsigned loop_num,
718 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
719 && CHREC_VARIABLE (chrec) > loop_num)
722 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
723 reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
724 reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
726 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
727 && CHREC_VARIABLE (chrec) == loop_num)
728 chrec = CHREC_LEFT (chrec);
730 return build_polynomial_chrec (loop_num, chrec, new_evol);
733 /* Merges two evolution functions that were found by following two
734 alternate paths of a conditional expression. */
737 chrec_merge (tree chrec1,
740 if (chrec1 == chrec_dont_know
741 || chrec2 == chrec_dont_know)
742 return chrec_dont_know;
744 if (chrec1 == chrec_known
745 || chrec2 == chrec_known)
748 if (chrec1 == chrec_not_analyzed_yet)
750 if (chrec2 == chrec_not_analyzed_yet)
753 if (operand_equal_p (chrec1, chrec2, 0))
756 return chrec_dont_know;
763 /* Helper function for is_multivariate_chrec. */
766 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
768 if (chrec == NULL_TREE)
771 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
773 if (CHREC_VARIABLE (chrec) != rec_var)
776 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
777 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
783 /* Determine whether the given chrec is multivariate or not. */
786 is_multivariate_chrec (tree chrec)
788 if (chrec == NULL_TREE)
791 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
792 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
793 CHREC_VARIABLE (chrec))
794 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
795 CHREC_VARIABLE (chrec)));
800 /* Determines whether the chrec contains symbolic names or not. */
803 chrec_contains_symbols (tree chrec)
805 if (chrec == NULL_TREE)
808 if (TREE_CODE (chrec) == SSA_NAME
809 || TREE_CODE (chrec) == VAR_DECL
810 || TREE_CODE (chrec) == PARM_DECL
811 || TREE_CODE (chrec) == FUNCTION_DECL
812 || TREE_CODE (chrec) == LABEL_DECL
813 || TREE_CODE (chrec) == RESULT_DECL
814 || TREE_CODE (chrec) == FIELD_DECL)
817 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
820 if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
824 if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
828 if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
836 /* Determines whether the chrec contains undetermined coefficients. */
839 chrec_contains_undetermined (tree chrec)
841 if (chrec == chrec_dont_know
842 || chrec == chrec_not_analyzed_yet
843 || chrec == NULL_TREE)
846 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
849 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
853 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
857 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
865 /* Determines whether the tree EXPR contains chrecs. */
868 tree_contains_chrecs (tree expr)
870 if (expr == NULL_TREE)
873 if (tree_is_chrec (expr))
876 switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
879 if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
883 if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
887 if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
895 /* Determine whether the given tree is an affine multivariate
899 evolution_function_is_affine_multivariate_p (tree chrec)
901 if (chrec == NULL_TREE)
904 switch (TREE_CODE (chrec))
906 case POLYNOMIAL_CHREC:
907 if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
909 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
913 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
914 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
915 != CHREC_VARIABLE (chrec)
916 && evolution_function_is_affine_multivariate_p
917 (CHREC_RIGHT (chrec)))
925 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
926 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
927 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
928 && evolution_function_is_affine_multivariate_p
929 (CHREC_LEFT (chrec)))
940 /* Determine whether the given tree is a function in zero or one
944 evolution_function_is_univariate_p (tree chrec)
946 if (chrec == NULL_TREE)
949 switch (TREE_CODE (chrec))
951 case POLYNOMIAL_CHREC:
952 switch (TREE_CODE (CHREC_LEFT (chrec)))
954 case POLYNOMIAL_CHREC:
955 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
957 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
965 switch (TREE_CODE (CHREC_RIGHT (chrec)))
967 case POLYNOMIAL_CHREC:
968 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
970 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
983 /* Returns the number of variables of CHREC. Example: the call
984 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
987 nb_vars_in_chrec (tree chrec)
989 if (chrec == NULL_TREE)
992 switch (TREE_CODE (chrec))
994 case POLYNOMIAL_CHREC:
995 return 1 + nb_vars_in_chrec
996 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1005 /* Convert the initial condition of chrec to type. */
1008 chrec_convert (tree type,
1013 if (automatically_generated_chrec_p (chrec))
1016 ct = chrec_type (chrec);
1020 if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
1021 return count_ev_in_wider_type (type, chrec);
1023 switch (TREE_CODE (chrec))
1025 case POLYNOMIAL_CHREC:
1026 return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1027 chrec_convert (type,
1028 CHREC_LEFT (chrec)),
1029 chrec_convert (type,
1030 CHREC_RIGHT (chrec)));
1034 tree res = fold_convert (type, chrec);
1036 /* Don't propagate overflows. */
1037 TREE_OVERFLOW (res) = 0;
1038 if (CONSTANT_CLASS_P (res))
1039 TREE_CONSTANT_OVERFLOW (res) = 0;
1045 /* Returns the type of the chrec. */
1048 chrec_type (tree chrec)
1050 if (automatically_generated_chrec_p (chrec))
1053 return TREE_TYPE (chrec);