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"
42 /* Extended folder for chrecs. */
44 /* Determines whether CST is not a constant evolution. */
47 is_not_constant_evolution (tree cst
)
49 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
52 /* Fold CODE for a polynomial function and a constant. */
55 chrec_fold_poly_cst (enum tree_code code
,
62 gcc_assert (TREE_CODE (poly
) == POLYNOMIAL_CHREC
);
63 gcc_assert (!is_not_constant_evolution (cst
));
68 return build_polynomial_chrec
69 (CHREC_VARIABLE (poly
),
70 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
74 return build_polynomial_chrec
75 (CHREC_VARIABLE (poly
),
76 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
80 return build_polynomial_chrec
81 (CHREC_VARIABLE (poly
),
82 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
83 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
86 return chrec_dont_know
;
90 /* Fold the addition of two polynomial functions. */
93 chrec_fold_plus_poly_poly (enum tree_code code
,
102 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
103 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
106 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
107 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
108 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
109 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
111 if (code
== PLUS_EXPR
)
112 return build_polynomial_chrec
113 (CHREC_VARIABLE (poly1
),
114 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
115 CHREC_RIGHT (poly1
));
117 return build_polynomial_chrec
118 (CHREC_VARIABLE (poly1
),
119 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
120 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
121 build_int_cst_type (type
, -1)));
124 if (CHREC_VARIABLE (poly0
) > CHREC_VARIABLE (poly1
))
126 if (code
== PLUS_EXPR
)
127 return build_polynomial_chrec
128 (CHREC_VARIABLE (poly0
),
129 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
130 CHREC_RIGHT (poly0
));
132 return build_polynomial_chrec
133 (CHREC_VARIABLE (poly0
),
134 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
135 CHREC_RIGHT (poly0
));
138 if (code
== PLUS_EXPR
)
140 left
= chrec_fold_plus
141 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
142 right
= chrec_fold_plus
143 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
147 left
= chrec_fold_minus
148 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
149 right
= chrec_fold_minus
150 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
153 if (chrec_zerop (right
))
156 return build_polynomial_chrec
157 (CHREC_VARIABLE (poly0
), left
, right
);
162 /* Fold the multiplication of two polynomial functions. */
165 chrec_fold_multiply_poly_poly (tree type
,
171 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
172 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
174 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
175 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
176 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
177 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
178 /* poly0 is a constant wrt. poly1. */
179 return build_polynomial_chrec
180 (CHREC_VARIABLE (poly1
),
181 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
182 CHREC_RIGHT (poly1
));
184 if (CHREC_VARIABLE (poly1
) < CHREC_VARIABLE (poly0
))
185 /* poly1 is a constant wrt. poly0. */
186 return build_polynomial_chrec
187 (CHREC_VARIABLE (poly0
),
188 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
189 CHREC_RIGHT (poly0
));
191 /* poly0 and poly1 are two polynomials in the same variable,
192 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
194 build_polynomial_chrec
195 (CHREC_VARIABLE (poly0
),
196 build_polynomial_chrec
197 (CHREC_VARIABLE (poly0
),
200 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
)),
202 /* "a*d + b*c + b*d". */
204 (type
, chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
)),
208 chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_LEFT (poly1
)),
209 chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
))))),
213 (type
, build_int_cst (NULL_TREE
, 2),
214 chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
))));
217 /* When the operands are automatically_generated_chrec_p, the fold has
218 to respect the semantics of the operands. */
221 chrec_fold_automatically_generated_operands (tree op0
,
224 if (op0
== chrec_dont_know
225 || op1
== chrec_dont_know
)
226 return chrec_dont_know
;
228 if (op0
== chrec_known
229 || op1
== chrec_known
)
232 if (op0
== chrec_not_analyzed_yet
233 || op1
== chrec_not_analyzed_yet
)
234 return chrec_not_analyzed_yet
;
236 /* The default case produces a safe result. */
237 return chrec_dont_know
;
240 /* Fold the addition of two chrecs. */
243 chrec_fold_plus_1 (enum tree_code code
,
248 if (automatically_generated_chrec_p (op0
)
249 || automatically_generated_chrec_p (op1
))
250 return chrec_fold_automatically_generated_operands (op0
, op1
);
252 switch (TREE_CODE (op0
))
254 case POLYNOMIAL_CHREC
:
255 switch (TREE_CODE (op1
))
257 case POLYNOMIAL_CHREC
:
258 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
261 if (code
== PLUS_EXPR
)
262 return build_polynomial_chrec
263 (CHREC_VARIABLE (op0
),
264 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
267 return build_polynomial_chrec
268 (CHREC_VARIABLE (op0
),
269 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
274 switch (TREE_CODE (op1
))
276 case POLYNOMIAL_CHREC
:
277 if (code
== PLUS_EXPR
)
278 return build_polynomial_chrec
279 (CHREC_VARIABLE (op1
),
280 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
283 return build_polynomial_chrec
284 (CHREC_VARIABLE (op1
),
285 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
286 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
287 build_int_cst_type (type
, -1)));
292 if ((tree_contains_chrecs (op0
, &size
)
293 || tree_contains_chrecs (op1
, &size
))
294 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
295 return build2 (code
, type
, op0
, op1
);
296 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
297 return fold_build2 (code
, type
, op0
, op1
);
299 return chrec_dont_know
;
305 /* Fold the addition of two chrecs. */
308 chrec_fold_plus (tree type
,
312 if (integer_zerop (op0
))
314 if (integer_zerop (op1
))
317 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
320 /* Fold the subtraction of two chrecs. */
323 chrec_fold_minus (tree type
,
327 if (integer_zerop (op1
))
330 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
333 /* Fold the multiplication of two chrecs. */
336 chrec_fold_multiply (tree type
,
340 if (automatically_generated_chrec_p (op0
)
341 || automatically_generated_chrec_p (op1
))
342 return chrec_fold_automatically_generated_operands (op0
, op1
);
344 switch (TREE_CODE (op0
))
346 case POLYNOMIAL_CHREC
:
347 switch (TREE_CODE (op1
))
349 case POLYNOMIAL_CHREC
:
350 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
353 if (integer_onep (op1
))
355 if (integer_zerop (op1
))
356 return build_int_cst_type (type
, 0);
358 return build_polynomial_chrec
359 (CHREC_VARIABLE (op0
),
360 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
361 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
365 if (integer_onep (op0
))
368 if (integer_zerop (op0
))
369 return build_int_cst_type (type
, 0);
371 switch (TREE_CODE (op1
))
373 case POLYNOMIAL_CHREC
:
374 return build_polynomial_chrec
375 (CHREC_VARIABLE (op1
),
376 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
377 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
380 if (integer_onep (op1
))
382 if (integer_zerop (op1
))
383 return build_int_cst_type (type
, 0);
384 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
393 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
394 calculation overflows, otherwise return C(n,k) with type TYPE. */
397 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
399 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
400 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
404 /* Handle the most frequent cases. */
406 return build_int_cst (type
, 1);
408 return fold_convert (type
, n
);
410 /* Check that k <= n. */
411 if (TREE_INT_CST_HIGH (n
) == 0
412 && TREE_INT_CST_LOW (n
) < k
)
416 lnum
= TREE_INT_CST_LOW (n
);
417 hnum
= TREE_INT_CST_HIGH (n
);
419 /* Denominator = 2. */
423 /* Index = Numerator-1. */
427 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
435 /* Numerator = Numerator*Index = n*(n-1). */
436 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
439 for (i
= 3; i
<= k
; i
++)
445 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
450 /* Numerator *= Index. */
451 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
454 /* Denominator *= i. */
455 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
458 /* Result = Numerator / Denominator. */
459 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
460 &lres
, &hres
, &ldum
, &hdum
);
462 res
= build_int_cst_wide (type
, lres
, hres
);
463 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
466 /* Helper function. Use the Newton's interpolating formula for
467 evaluating the value of the evolution function. */
470 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
472 tree arg0
, arg1
, binomial_n_k
;
473 tree type
= TREE_TYPE (chrec
);
475 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
476 && CHREC_VARIABLE (chrec
) > var
)
477 chrec
= CHREC_LEFT (chrec
);
479 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
480 && CHREC_VARIABLE (chrec
) == var
)
482 arg0
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
483 if (arg0
== chrec_dont_know
)
484 return chrec_dont_know
;
485 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
487 return chrec_dont_know
;
488 arg1
= fold_build2 (MULT_EXPR
, type
,
489 CHREC_LEFT (chrec
), binomial_n_k
);
490 return chrec_fold_plus (type
, arg0
, arg1
);
493 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
495 return chrec_dont_know
;
497 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
500 /* Evaluates "CHREC (X)" when the varying variable is VAR.
501 Example: Given the following parameters,
507 The result is given by the Newton's interpolating formula:
508 3 * \binom{10}{0} + 4 * \binom{10}{1}.
512 chrec_apply (unsigned var
,
516 tree type
= chrec_type (chrec
);
517 tree res
= chrec_dont_know
;
519 if (automatically_generated_chrec_p (chrec
)
520 || automatically_generated_chrec_p (x
)
522 /* When the symbols are defined in an outer loop, it is possible
523 to symbolically compute the apply, since the symbols are
524 constants with respect to the varying loop. */
525 || chrec_contains_symbols_defined_in_loop (chrec
, var
)
526 || chrec_contains_symbols (x
))
527 return chrec_dont_know
;
529 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
530 fprintf (dump_file
, "(chrec_apply \n");
532 if (evolution_function_is_affine_p (chrec
))
534 /* "{a, +, b} (x)" -> "a + b*x". */
535 if (TREE_CODE (CHREC_LEFT (chrec
)) == INTEGER_CST
536 && integer_zerop (CHREC_LEFT (chrec
)))
537 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
540 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
),
541 chrec_fold_multiply (type
,
542 CHREC_RIGHT (chrec
), x
));
545 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
548 else if (TREE_CODE (x
) == INTEGER_CST
549 && tree_int_cst_sgn (x
) == 1)
550 /* testsuite/.../ssa-chrec-38.c. */
551 res
= chrec_evaluate (var
, chrec
, x
, 0);
554 res
= chrec_dont_know
;
556 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
558 fprintf (dump_file
, " (varying_loop = %d\n", var
);
559 fprintf (dump_file
, ")\n (chrec = ");
560 print_generic_expr (dump_file
, chrec
, 0);
561 fprintf (dump_file
, ")\n (x = ");
562 print_generic_expr (dump_file
, x
, 0);
563 fprintf (dump_file
, ")\n (res = ");
564 print_generic_expr (dump_file
, res
, 0);
565 fprintf (dump_file
, "))\n");
571 /* Replaces the initial condition in CHREC with INIT_COND. */
574 chrec_replace_initial_condition (tree chrec
,
577 if (automatically_generated_chrec_p (chrec
))
580 switch (TREE_CODE (chrec
))
582 case POLYNOMIAL_CHREC
:
583 return build_polynomial_chrec
584 (CHREC_VARIABLE (chrec
),
585 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
586 CHREC_RIGHT (chrec
));
593 /* Returns the initial condition of a given CHREC. */
596 initial_condition (tree chrec
)
598 if (automatically_generated_chrec_p (chrec
))
601 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
602 return initial_condition (CHREC_LEFT (chrec
));
607 /* Returns a univariate function that represents the evolution in
608 LOOP_NUM. Mask the evolution of any other loop. */
611 hide_evolution_in_other_loops_than_loop (tree chrec
,
614 if (automatically_generated_chrec_p (chrec
))
617 switch (TREE_CODE (chrec
))
619 case POLYNOMIAL_CHREC
:
620 if (CHREC_VARIABLE (chrec
) == loop_num
)
621 return build_polynomial_chrec
623 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
625 CHREC_RIGHT (chrec
));
627 else if (CHREC_VARIABLE (chrec
) < loop_num
)
628 /* There is no evolution in this loop. */
629 return initial_condition (chrec
);
632 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
640 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
641 true, otherwise returns the initial condition in LOOP_NUM. */
644 chrec_component_in_loop_num (tree chrec
,
650 if (automatically_generated_chrec_p (chrec
))
653 switch (TREE_CODE (chrec
))
655 case POLYNOMIAL_CHREC
:
656 if (CHREC_VARIABLE (chrec
) == loop_num
)
659 component
= CHREC_RIGHT (chrec
);
661 component
= CHREC_LEFT (chrec
);
663 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
664 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
668 return build_polynomial_chrec
670 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
676 else if (CHREC_VARIABLE (chrec
) < loop_num
)
677 /* There is no evolution part in this loop. */
681 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
693 /* Returns the evolution part in LOOP_NUM. Example: the call
694 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
698 evolution_part_in_loop_num (tree chrec
,
701 return chrec_component_in_loop_num (chrec
, loop_num
, true);
704 /* Returns the initial condition in LOOP_NUM. Example: the call
705 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
709 initial_condition_in_loop_num (tree chrec
,
712 return chrec_component_in_loop_num (chrec
, loop_num
, false);
715 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
716 This function is essentially used for setting the evolution to
717 chrec_dont_know, for example after having determined that it is
718 impossible to say how many times a loop will execute. */
721 reset_evolution_in_loop (unsigned loop_num
,
725 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
726 && CHREC_VARIABLE (chrec
) > loop_num
)
729 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
730 reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
), new_evol
),
731 reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
), new_evol
));
733 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
734 && CHREC_VARIABLE (chrec
) == loop_num
)
735 chrec
= CHREC_LEFT (chrec
);
737 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
740 /* Merges two evolution functions that were found by following two
741 alternate paths of a conditional expression. */
744 chrec_merge (tree chrec1
,
747 if (chrec1
== chrec_dont_know
748 || chrec2
== chrec_dont_know
)
749 return chrec_dont_know
;
751 if (chrec1
== chrec_known
752 || chrec2
== chrec_known
)
755 if (chrec1
== chrec_not_analyzed_yet
)
757 if (chrec2
== chrec_not_analyzed_yet
)
760 if (operand_equal_p (chrec1
, chrec2
, 0))
763 return chrec_dont_know
;
770 /* Helper function for is_multivariate_chrec. */
773 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
775 if (chrec
== NULL_TREE
)
778 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
780 if (CHREC_VARIABLE (chrec
) != rec_var
)
783 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
784 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
790 /* Determine whether the given chrec is multivariate or not. */
793 is_multivariate_chrec (tree chrec
)
795 if (chrec
== NULL_TREE
)
798 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
799 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
800 CHREC_VARIABLE (chrec
))
801 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
802 CHREC_VARIABLE (chrec
)));
807 /* Determines whether the chrec contains symbolic names or not. */
810 chrec_contains_symbols (tree chrec
)
812 if (chrec
== NULL_TREE
)
815 if (TREE_CODE (chrec
) == SSA_NAME
816 || TREE_CODE (chrec
) == VAR_DECL
817 || TREE_CODE (chrec
) == PARM_DECL
818 || TREE_CODE (chrec
) == FUNCTION_DECL
819 || TREE_CODE (chrec
) == LABEL_DECL
820 || TREE_CODE (chrec
) == RESULT_DECL
821 || TREE_CODE (chrec
) == FIELD_DECL
)
824 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
827 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
831 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
835 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
843 /* Determines whether the chrec contains undetermined coefficients. */
846 chrec_contains_undetermined (tree chrec
)
848 if (chrec
== chrec_dont_know
849 || chrec
== chrec_not_analyzed_yet
850 || chrec
== NULL_TREE
)
853 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
856 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
860 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
864 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
872 /* Determines whether the tree EXPR contains chrecs, and increment
873 SIZE if it is not a NULL pointer by an estimation of the depth of
877 tree_contains_chrecs (tree expr
, int *size
)
879 if (expr
== NULL_TREE
)
885 if (tree_is_chrec (expr
))
888 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
891 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
895 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
899 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
907 /* Determine whether the given tree is an affine multivariate
911 evolution_function_is_affine_multivariate_p (tree chrec
)
913 if (chrec
== NULL_TREE
)
916 switch (TREE_CODE (chrec
))
918 case POLYNOMIAL_CHREC
:
919 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
921 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
925 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
926 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
927 != CHREC_VARIABLE (chrec
)
928 && evolution_function_is_affine_multivariate_p
929 (CHREC_RIGHT (chrec
)))
937 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
938 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
939 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
940 && evolution_function_is_affine_multivariate_p
941 (CHREC_LEFT (chrec
)))
952 /* Determine whether the given tree is a function in zero or one
956 evolution_function_is_univariate_p (tree chrec
)
958 if (chrec
== NULL_TREE
)
961 switch (TREE_CODE (chrec
))
963 case POLYNOMIAL_CHREC
:
964 switch (TREE_CODE (CHREC_LEFT (chrec
)))
966 case POLYNOMIAL_CHREC
:
967 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
969 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
977 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
979 case POLYNOMIAL_CHREC
:
980 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
982 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
995 /* Returns the number of variables of CHREC. Example: the call
996 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
999 nb_vars_in_chrec (tree chrec
)
1001 if (chrec
== NULL_TREE
)
1004 switch (TREE_CODE (chrec
))
1006 case POLYNOMIAL_CHREC
:
1007 return 1 + nb_vars_in_chrec
1008 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1017 /* Convert CHREC to TYPE. The following is rule is always true:
1018 TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
1019 (CHREC_RIGHT (chrec)). An example of what could happen when adding
1020 two chrecs and the type of the CHREC_RIGHT is different than
1023 {(uint) 0, +, (uchar) 10} +
1024 {(uint) 0, +, (uchar) 250}
1026 that would produce a wrong result if CHREC_RIGHT is not (uint):
1028 {(uint) 0, +, (uchar) 4}
1032 {(uint) 0, +, (uint) 260}
1036 chrec_convert (tree type
,
1041 if (automatically_generated_chrec_p (chrec
))
1044 ct
= chrec_type (chrec
);
1048 if (TYPE_PRECISION (ct
) < TYPE_PRECISION (type
))
1049 return count_ev_in_wider_type (type
, chrec
);
1051 switch (TREE_CODE (chrec
))
1053 case POLYNOMIAL_CHREC
:
1054 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1055 chrec_convert (type
,
1056 CHREC_LEFT (chrec
)),
1057 chrec_convert (type
,
1058 CHREC_RIGHT (chrec
)));
1062 tree res
= fold_convert (type
, chrec
);
1064 /* Don't propagate overflows. */
1065 TREE_OVERFLOW (res
) = 0;
1066 if (CONSTANT_CLASS_P (res
))
1067 TREE_CONSTANT_OVERFLOW (res
) = 0;
1069 /* But reject constants that don't fit in their type after conversion.
1070 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1071 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1072 and can cause problems later when computing niters of loops. Note
1073 that we don't do the check before converting because we don't want
1074 to reject conversions of negative chrecs to unsigned types. */
1075 if (TREE_CODE (res
) == INTEGER_CST
1076 && TREE_CODE (type
) == INTEGER_TYPE
1077 && !int_fits_type_p (res
, type
))
1078 res
= chrec_dont_know
;
1085 /* Returns the type of the chrec. */
1088 chrec_type (tree chrec
)
1090 if (automatically_generated_chrec_p (chrec
))
1093 return TREE_TYPE (chrec
);