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"
33 #include "diagnostic.h"
35 #include "tree-chrec.h"
36 #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)));
291 if ((tree_contains_chrecs (op0
, &size
)
292 || tree_contains_chrecs (op1
, &size
))
293 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
294 return build2 (code
, type
, op0
, op1
);
295 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
296 return fold_build2 (code
, type
, op0
, op1
);
298 return chrec_dont_know
;
304 /* Fold the addition of two chrecs. */
307 chrec_fold_plus (tree type
,
311 if (integer_zerop (op0
))
313 if (integer_zerop (op1
))
316 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
319 /* Fold the subtraction of two chrecs. */
322 chrec_fold_minus (tree type
,
326 if (integer_zerop (op1
))
329 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
332 /* Fold the multiplication of two chrecs. */
335 chrec_fold_multiply (tree type
,
339 if (automatically_generated_chrec_p (op0
)
340 || automatically_generated_chrec_p (op1
))
341 return chrec_fold_automatically_generated_operands (op0
, op1
);
343 switch (TREE_CODE (op0
))
345 case POLYNOMIAL_CHREC
:
346 switch (TREE_CODE (op1
))
348 case POLYNOMIAL_CHREC
:
349 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
352 if (integer_onep (op1
))
354 if (integer_zerop (op1
))
355 return build_int_cst_type (type
, 0);
357 return build_polynomial_chrec
358 (CHREC_VARIABLE (op0
),
359 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
360 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
364 if (integer_onep (op0
))
367 if (integer_zerop (op0
))
368 return build_int_cst_type (type
, 0);
370 switch (TREE_CODE (op1
))
372 case POLYNOMIAL_CHREC
:
373 return build_polynomial_chrec
374 (CHREC_VARIABLE (op1
),
375 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
376 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
379 if (integer_onep (op1
))
381 if (integer_zerop (op1
))
382 return build_int_cst_type (type
, 0);
383 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
392 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
393 calculation overflows, otherwise return C(n,k) with type TYPE. */
396 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
398 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
399 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
403 /* Handle the most frequent cases. */
405 return build_int_cst (type
, 1);
407 return fold_convert (type
, n
);
409 /* Check that k <= n. */
410 if (TREE_INT_CST_HIGH (n
) == 0
411 && TREE_INT_CST_LOW (n
) < k
)
415 lnum
= TREE_INT_CST_LOW (n
);
416 hnum
= TREE_INT_CST_HIGH (n
);
418 /* Denominator = 2. */
422 /* Index = Numerator-1. */
426 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
434 /* Numerator = Numerator*Index = n*(n-1). */
435 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
438 for (i
= 3; i
<= k
; i
++)
444 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
449 /* Numerator *= Index. */
450 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
453 /* Denominator *= i. */
454 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
457 /* Result = Numerator / Denominator. */
458 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
459 &lres
, &hres
, &ldum
, &hdum
);
461 res
= build_int_cst_wide (type
, lres
, hres
);
462 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
465 /* Helper function. Use the Newton's interpolating formula for
466 evaluating the value of the evolution function. */
469 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
471 tree arg0
, arg1
, binomial_n_k
;
472 tree type
= TREE_TYPE (chrec
);
474 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
475 && CHREC_VARIABLE (chrec
) > var
)
476 chrec
= CHREC_LEFT (chrec
);
478 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
479 && CHREC_VARIABLE (chrec
) == var
)
481 arg0
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
482 if (arg0
== chrec_dont_know
)
483 return chrec_dont_know
;
484 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
486 return chrec_dont_know
;
487 arg1
= fold_build2 (MULT_EXPR
, type
,
488 CHREC_LEFT (chrec
), binomial_n_k
);
489 return chrec_fold_plus (type
, arg0
, arg1
);
492 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
494 return chrec_dont_know
;
496 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
499 /* Evaluates "CHREC (X)" when the varying variable is VAR.
500 Example: Given the following parameters,
506 The result is given by the Newton's interpolating formula:
507 3 * \binom{10}{0} + 4 * \binom{10}{1}.
511 chrec_apply (unsigned var
,
515 tree type
= chrec_type (chrec
);
516 tree res
= chrec_dont_know
;
518 if (automatically_generated_chrec_p (chrec
)
519 || automatically_generated_chrec_p (x
)
521 /* When the symbols are defined in an outer loop, it is possible
522 to symbolically compute the apply, since the symbols are
523 constants with respect to the varying loop. */
524 || chrec_contains_symbols_defined_in_loop (chrec
, var
)
525 || chrec_contains_symbols (x
))
526 return chrec_dont_know
;
528 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
529 fprintf (dump_file
, "(chrec_apply \n");
531 if (evolution_function_is_affine_p (chrec
))
533 /* "{a, +, b} (x)" -> "a + b*x". */
534 if (TREE_CODE (CHREC_LEFT (chrec
)) == INTEGER_CST
535 && integer_zerop (CHREC_LEFT (chrec
)))
536 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
539 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
),
540 chrec_fold_multiply (type
,
541 CHREC_RIGHT (chrec
), x
));
544 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
547 else if (TREE_CODE (x
) == INTEGER_CST
548 && tree_int_cst_sgn (x
) == 1)
549 /* testsuite/.../ssa-chrec-38.c. */
550 res
= chrec_evaluate (var
, chrec
, x
, 0);
553 res
= chrec_dont_know
;
555 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
557 fprintf (dump_file
, " (varying_loop = %d\n", var
);
558 fprintf (dump_file
, ")\n (chrec = ");
559 print_generic_expr (dump_file
, chrec
, 0);
560 fprintf (dump_file
, ")\n (x = ");
561 print_generic_expr (dump_file
, x
, 0);
562 fprintf (dump_file
, ")\n (res = ");
563 print_generic_expr (dump_file
, res
, 0);
564 fprintf (dump_file
, "))\n");
570 /* Replaces the initial condition in CHREC with INIT_COND. */
573 chrec_replace_initial_condition (tree chrec
,
576 if (automatically_generated_chrec_p (chrec
))
579 switch (TREE_CODE (chrec
))
581 case POLYNOMIAL_CHREC
:
582 return build_polynomial_chrec
583 (CHREC_VARIABLE (chrec
),
584 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
585 CHREC_RIGHT (chrec
));
592 /* Returns the initial condition of a given CHREC. */
595 initial_condition (tree chrec
)
597 if (automatically_generated_chrec_p (chrec
))
600 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
601 return initial_condition (CHREC_LEFT (chrec
));
606 /* Returns a univariate function that represents the evolution in
607 LOOP_NUM. Mask the evolution of any other loop. */
610 hide_evolution_in_other_loops_than_loop (tree chrec
,
613 if (automatically_generated_chrec_p (chrec
))
616 switch (TREE_CODE (chrec
))
618 case POLYNOMIAL_CHREC
:
619 if (CHREC_VARIABLE (chrec
) == loop_num
)
620 return build_polynomial_chrec
622 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
624 CHREC_RIGHT (chrec
));
626 else if (CHREC_VARIABLE (chrec
) < loop_num
)
627 /* There is no evolution in this loop. */
628 return initial_condition (chrec
);
631 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
639 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
640 true, otherwise returns the initial condition in LOOP_NUM. */
643 chrec_component_in_loop_num (tree chrec
,
649 if (automatically_generated_chrec_p (chrec
))
652 switch (TREE_CODE (chrec
))
654 case POLYNOMIAL_CHREC
:
655 if (CHREC_VARIABLE (chrec
) == loop_num
)
658 component
= CHREC_RIGHT (chrec
);
660 component
= CHREC_LEFT (chrec
);
662 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
663 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
667 return build_polynomial_chrec
669 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
675 else if (CHREC_VARIABLE (chrec
) < loop_num
)
676 /* There is no evolution part in this loop. */
680 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
692 /* Returns the evolution part in LOOP_NUM. Example: the call
693 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
697 evolution_part_in_loop_num (tree chrec
,
700 return chrec_component_in_loop_num (chrec
, loop_num
, true);
703 /* Returns the initial condition in LOOP_NUM. Example: the call
704 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
708 initial_condition_in_loop_num (tree chrec
,
711 return chrec_component_in_loop_num (chrec
, loop_num
, false);
714 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
715 This function is essentially used for setting the evolution to
716 chrec_dont_know, for example after having determined that it is
717 impossible to say how many times a loop will execute. */
720 reset_evolution_in_loop (unsigned loop_num
,
724 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
725 && CHREC_VARIABLE (chrec
) > loop_num
)
728 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
729 reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
), new_evol
),
730 reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
), new_evol
));
732 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
733 && CHREC_VARIABLE (chrec
) == loop_num
)
734 chrec
= CHREC_LEFT (chrec
);
736 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
739 /* Merges two evolution functions that were found by following two
740 alternate paths of a conditional expression. */
743 chrec_merge (tree chrec1
,
746 if (chrec1
== chrec_dont_know
747 || chrec2
== chrec_dont_know
)
748 return chrec_dont_know
;
750 if (chrec1
== chrec_known
751 || chrec2
== chrec_known
)
754 if (chrec1
== chrec_not_analyzed_yet
)
756 if (chrec2
== chrec_not_analyzed_yet
)
759 if (operand_equal_p (chrec1
, chrec2
, 0))
762 return chrec_dont_know
;
769 /* Helper function for is_multivariate_chrec. */
772 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
774 if (chrec
== NULL_TREE
)
777 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
779 if (CHREC_VARIABLE (chrec
) != rec_var
)
782 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
783 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
789 /* Determine whether the given chrec is multivariate or not. */
792 is_multivariate_chrec (tree chrec
)
794 if (chrec
== NULL_TREE
)
797 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
798 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
799 CHREC_VARIABLE (chrec
))
800 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
801 CHREC_VARIABLE (chrec
)));
806 /* Determines whether the chrec contains symbolic names or not. */
809 chrec_contains_symbols (tree chrec
)
811 if (chrec
== NULL_TREE
)
814 if (TREE_CODE (chrec
) == SSA_NAME
815 || TREE_CODE (chrec
) == VAR_DECL
816 || TREE_CODE (chrec
) == PARM_DECL
817 || TREE_CODE (chrec
) == FUNCTION_DECL
818 || TREE_CODE (chrec
) == LABEL_DECL
819 || TREE_CODE (chrec
) == RESULT_DECL
820 || TREE_CODE (chrec
) == FIELD_DECL
)
823 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
826 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
830 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
834 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
842 /* Determines whether the chrec contains undetermined coefficients. */
845 chrec_contains_undetermined (tree chrec
)
847 if (chrec
== chrec_dont_know
848 || chrec
== chrec_not_analyzed_yet
849 || chrec
== NULL_TREE
)
852 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
855 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
859 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
863 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
871 /* Determines whether the tree EXPR contains chrecs, and increment
872 SIZE if it is not a NULL pointer by an estimation of the depth of
876 tree_contains_chrecs (tree expr
, int *size
)
878 if (expr
== NULL_TREE
)
884 if (tree_is_chrec (expr
))
887 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
890 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
894 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
898 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
906 /* Determine whether the given tree is an affine multivariate
910 evolution_function_is_affine_multivariate_p (tree chrec
)
912 if (chrec
== NULL_TREE
)
915 switch (TREE_CODE (chrec
))
917 case POLYNOMIAL_CHREC
:
918 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
920 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
924 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
925 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
926 != CHREC_VARIABLE (chrec
)
927 && evolution_function_is_affine_multivariate_p
928 (CHREC_RIGHT (chrec
)))
936 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
937 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
938 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
939 && evolution_function_is_affine_multivariate_p
940 (CHREC_LEFT (chrec
)))
951 /* Determine whether the given tree is a function in zero or one
955 evolution_function_is_univariate_p (tree chrec
)
957 if (chrec
== NULL_TREE
)
960 switch (TREE_CODE (chrec
))
962 case POLYNOMIAL_CHREC
:
963 switch (TREE_CODE (CHREC_LEFT (chrec
)))
965 case POLYNOMIAL_CHREC
:
966 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
968 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
976 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
978 case POLYNOMIAL_CHREC
:
979 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
981 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
994 /* Returns the number of variables of CHREC. Example: the call
995 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
998 nb_vars_in_chrec (tree chrec
)
1000 if (chrec
== NULL_TREE
)
1003 switch (TREE_CODE (chrec
))
1005 case POLYNOMIAL_CHREC
:
1006 return 1 + nb_vars_in_chrec
1007 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1016 /* Convert CHREC to TYPE. The following is rule is always true:
1017 TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
1018 (CHREC_RIGHT (chrec)). An example of what could happen when adding
1019 two chrecs and the type of the CHREC_RIGHT is different than
1022 {(uint) 0, +, (uchar) 10} +
1023 {(uint) 0, +, (uchar) 250}
1025 that would produce a wrong result if CHREC_RIGHT is not (uint):
1027 {(uint) 0, +, (uchar) 4}
1031 {(uint) 0, +, (uint) 260}
1035 chrec_convert (tree type
,
1040 if (automatically_generated_chrec_p (chrec
))
1043 ct
= chrec_type (chrec
);
1047 if (TYPE_PRECISION (ct
) < TYPE_PRECISION (type
))
1048 return count_ev_in_wider_type (type
, chrec
);
1050 switch (TREE_CODE (chrec
))
1052 case POLYNOMIAL_CHREC
:
1053 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1054 chrec_convert (type
,
1055 CHREC_LEFT (chrec
)),
1056 chrec_convert (type
,
1057 CHREC_RIGHT (chrec
)));
1061 tree res
= fold_convert (type
, chrec
);
1063 /* Don't propagate overflows. */
1064 if (CONSTANT_CLASS_P (res
))
1066 TREE_CONSTANT_OVERFLOW (res
) = 0;
1067 TREE_OVERFLOW (res
) = 0;
1070 /* But reject constants that don't fit in their type after conversion.
1071 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1072 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1073 and can cause problems later when computing niters of loops. Note
1074 that we don't do the check before converting because we don't want
1075 to reject conversions of negative chrecs to unsigned types. */
1076 if (TREE_CODE (res
) == INTEGER_CST
1077 && TREE_CODE (type
) == INTEGER_TYPE
1078 && !int_fits_type_p (res
, type
))
1079 res
= chrec_dont_know
;
1086 /* Returns the type of the chrec. */
1089 chrec_type (tree chrec
)
1091 if (automatically_generated_chrec_p (chrec
))
1094 return TREE_TYPE (chrec
);