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 CHREC to TYPE. The following is rule is always true:
1006 TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
1007 (CHREC_RIGHT (chrec)). An example of what could happen when adding
1008 two chrecs and the type of the CHREC_RIGHT is different than
1011 {(uint) 0, +, (uchar) 10} +
1012 {(uint) 0, +, (uchar) 250}
1014 that would produce a wrong result if CHREC_RIGHT is not (uint):
1016 {(uint) 0, +, (uchar) 4}
1020 {(uint) 0, +, (uint) 260}
1024 chrec_convert (tree type
,
1029 if (automatically_generated_chrec_p (chrec
))
1032 ct
= chrec_type (chrec
);
1036 if (TYPE_PRECISION (ct
) < TYPE_PRECISION (type
))
1037 return count_ev_in_wider_type (type
, chrec
);
1039 switch (TREE_CODE (chrec
))
1041 case POLYNOMIAL_CHREC
:
1042 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1043 chrec_convert (type
,
1044 CHREC_LEFT (chrec
)),
1045 chrec_convert (type
,
1046 CHREC_RIGHT (chrec
)));
1050 tree res
= fold_convert (type
, chrec
);
1052 /* Don't propagate overflows. */
1053 TREE_OVERFLOW (res
) = 0;
1054 if (CONSTANT_CLASS_P (res
))
1055 TREE_CONSTANT_OVERFLOW (res
) = 0;
1057 /* But reject constants that don't fit in their type after conversion.
1058 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1059 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1060 and can cause problems later when computing niters of loops. Note
1061 that we don't do the check before converting because we don't want
1062 to reject conversions of negative chrecs to unsigned types. */
1063 if (TREE_CODE (res
) == INTEGER_CST
1064 && TREE_CODE (type
) == INTEGER_TYPE
1065 && !int_fits_type_p (res
, type
))
1066 res
= chrec_dont_know
;
1073 /* Returns the type of the chrec. */
1076 chrec_type (tree chrec
)
1078 if (automatically_generated_chrec_p (chrec
))
1081 return TREE_TYPE (chrec
);