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
,
174 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
175 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
177 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
178 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
179 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
180 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
181 /* poly0 is a constant wrt. poly1. */
182 return build_polynomial_chrec
183 (CHREC_VARIABLE (poly1
),
184 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
185 CHREC_RIGHT (poly1
));
187 if (CHREC_VARIABLE (poly1
) < CHREC_VARIABLE (poly0
))
188 /* poly1 is a constant wrt. poly0. */
189 return build_polynomial_chrec
190 (CHREC_VARIABLE (poly0
),
191 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
192 CHREC_RIGHT (poly0
));
194 /* poly0 and poly1 are two polynomials in the same variable,
195 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
198 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
200 /* "a*d + b*c + b*d". */
201 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
202 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
204 CHREC_LEFT (poly1
)));
205 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
207 CHREC_RIGHT (poly1
)));
209 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
210 t2
= chrec_fold_multiply (type
, build_int_cst_type (type
, 2), t2
);
212 var
= CHREC_VARIABLE (poly0
);
213 return build_polynomial_chrec (var
, t0
,
214 build_polynomial_chrec (var
, t1
, t2
));
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
)
728 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
730 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
732 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
733 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
737 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
738 && CHREC_VARIABLE (chrec
) == loop_num
)
739 chrec
= CHREC_LEFT (chrec
);
741 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
744 /* Merges two evolution functions that were found by following two
745 alternate paths of a conditional expression. */
748 chrec_merge (tree chrec1
,
751 if (chrec1
== chrec_dont_know
752 || chrec2
== chrec_dont_know
)
753 return chrec_dont_know
;
755 if (chrec1
== chrec_known
756 || chrec2
== chrec_known
)
759 if (chrec1
== chrec_not_analyzed_yet
)
761 if (chrec2
== chrec_not_analyzed_yet
)
764 if (operand_equal_p (chrec1
, chrec2
, 0))
767 return chrec_dont_know
;
774 /* Helper function for is_multivariate_chrec. */
777 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
779 if (chrec
== NULL_TREE
)
782 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
784 if (CHREC_VARIABLE (chrec
) != rec_var
)
787 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
788 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
794 /* Determine whether the given chrec is multivariate or not. */
797 is_multivariate_chrec (tree chrec
)
799 if (chrec
== NULL_TREE
)
802 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
803 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
804 CHREC_VARIABLE (chrec
))
805 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
806 CHREC_VARIABLE (chrec
)));
811 /* Determines whether the chrec contains symbolic names or not. */
814 chrec_contains_symbols (tree chrec
)
816 if (chrec
== NULL_TREE
)
819 if (TREE_CODE (chrec
) == SSA_NAME
820 || TREE_CODE (chrec
) == VAR_DECL
821 || TREE_CODE (chrec
) == PARM_DECL
822 || TREE_CODE (chrec
) == FUNCTION_DECL
823 || TREE_CODE (chrec
) == LABEL_DECL
824 || TREE_CODE (chrec
) == RESULT_DECL
825 || TREE_CODE (chrec
) == FIELD_DECL
)
828 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
831 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
835 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
839 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
847 /* Determines whether the chrec contains undetermined coefficients. */
850 chrec_contains_undetermined (tree chrec
)
852 if (chrec
== chrec_dont_know
853 || chrec
== chrec_not_analyzed_yet
854 || chrec
== NULL_TREE
)
857 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
860 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
864 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
868 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
876 /* Determines whether the tree EXPR contains chrecs, and increment
877 SIZE if it is not a NULL pointer by an estimation of the depth of
881 tree_contains_chrecs (tree expr
, int *size
)
883 if (expr
== NULL_TREE
)
889 if (tree_is_chrec (expr
))
892 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
895 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
899 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
903 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
911 /* Determine whether the given tree is an affine multivariate
915 evolution_function_is_affine_multivariate_p (tree chrec
)
917 if (chrec
== NULL_TREE
)
920 switch (TREE_CODE (chrec
))
922 case POLYNOMIAL_CHREC
:
923 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
925 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
929 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
930 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
931 != CHREC_VARIABLE (chrec
)
932 && evolution_function_is_affine_multivariate_p
933 (CHREC_RIGHT (chrec
)))
941 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
942 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
943 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
944 && evolution_function_is_affine_multivariate_p
945 (CHREC_LEFT (chrec
)))
956 /* Determine whether the given tree is a function in zero or one
960 evolution_function_is_univariate_p (tree chrec
)
962 if (chrec
== NULL_TREE
)
965 switch (TREE_CODE (chrec
))
967 case POLYNOMIAL_CHREC
:
968 switch (TREE_CODE (CHREC_LEFT (chrec
)))
970 case POLYNOMIAL_CHREC
:
971 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
973 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
981 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
983 case POLYNOMIAL_CHREC
:
984 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
986 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
999 /* Returns the number of variables of CHREC. Example: the call
1000 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1003 nb_vars_in_chrec (tree chrec
)
1005 if (chrec
== NULL_TREE
)
1008 switch (TREE_CODE (chrec
))
1010 case POLYNOMIAL_CHREC
:
1011 return 1 + nb_vars_in_chrec
1012 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1021 /* Convert CHREC to TYPE. The following is rule is always true:
1022 TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
1023 (CHREC_RIGHT (chrec)). An example of what could happen when adding
1024 two chrecs and the type of the CHREC_RIGHT is different than
1027 {(uint) 0, +, (uchar) 10} +
1028 {(uint) 0, +, (uchar) 250}
1030 that would produce a wrong result if CHREC_RIGHT is not (uint):
1032 {(uint) 0, +, (uchar) 4}
1036 {(uint) 0, +, (uint) 260}
1040 chrec_convert (tree type
,
1045 if (automatically_generated_chrec_p (chrec
))
1048 ct
= chrec_type (chrec
);
1052 if (TYPE_PRECISION (ct
) < TYPE_PRECISION (type
))
1053 return count_ev_in_wider_type (type
, chrec
);
1055 switch (TREE_CODE (chrec
))
1057 case POLYNOMIAL_CHREC
:
1058 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1059 chrec_convert (type
,
1060 CHREC_LEFT (chrec
)),
1061 chrec_convert (type
,
1062 CHREC_RIGHT (chrec
)));
1066 tree res
= fold_convert (type
, chrec
);
1068 /* Don't propagate overflows. */
1069 TREE_OVERFLOW (res
) = 0;
1070 if (CONSTANT_CLASS_P (res
))
1071 TREE_CONSTANT_OVERFLOW (res
) = 0;
1073 /* But reject constants that don't fit in their type after conversion.
1074 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1075 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1076 and can cause problems later when computing niters of loops. Note
1077 that we don't do the check before converting because we don't want
1078 to reject conversions of negative chrecs to unsigned types. */
1079 if (TREE_CODE (res
) == INTEGER_CST
1080 && TREE_CODE (type
) == INTEGER_TYPE
1081 && !int_fits_type_p (res
, type
))
1082 res
= chrec_dont_know
;
1089 /* Returns the type of the chrec. */
1092 chrec_type (tree chrec
)
1094 if (automatically_generated_chrec_p (chrec
))
1097 return TREE_TYPE (chrec
);