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, 51 Franklin Street, Fifth Floor, 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"
37 #include "tree-flow.h"
38 #include "tree-chrec.h"
39 #include "tree-pass.h"
41 #include "tree-scalar-evolution.h"
45 /* Extended folder for chrecs. */
47 /* Determines whether CST is not a constant evolution. */
50 is_not_constant_evolution (tree cst
)
52 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
55 /* Fold CODE for a polynomial function and a constant. */
58 chrec_fold_poly_cst (enum tree_code code
,
65 gcc_assert (TREE_CODE (poly
) == POLYNOMIAL_CHREC
);
66 gcc_assert (!is_not_constant_evolution (cst
));
71 return build_polynomial_chrec
72 (CHREC_VARIABLE (poly
),
73 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
77 return build_polynomial_chrec
78 (CHREC_VARIABLE (poly
),
79 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
83 return build_polynomial_chrec
84 (CHREC_VARIABLE (poly
),
85 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
86 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
89 return chrec_dont_know
;
93 /* Fold the addition of two polynomial functions. */
96 chrec_fold_plus_poly_poly (enum tree_code code
,
105 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
106 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
109 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
110 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
111 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
112 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
114 if (code
== PLUS_EXPR
)
115 return build_polynomial_chrec
116 (CHREC_VARIABLE (poly1
),
117 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
118 CHREC_RIGHT (poly1
));
120 return build_polynomial_chrec
121 (CHREC_VARIABLE (poly1
),
122 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
123 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
124 SCALAR_FLOAT_TYPE_P (type
)
125 ? build_real (type
, dconstm1
)
126 : build_int_cst_type (type
, -1)));
129 if (CHREC_VARIABLE (poly0
) > CHREC_VARIABLE (poly1
))
131 if (code
== PLUS_EXPR
)
132 return build_polynomial_chrec
133 (CHREC_VARIABLE (poly0
),
134 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
135 CHREC_RIGHT (poly0
));
137 return build_polynomial_chrec
138 (CHREC_VARIABLE (poly0
),
139 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
140 CHREC_RIGHT (poly0
));
143 if (code
== PLUS_EXPR
)
145 left
= chrec_fold_plus
146 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
147 right
= chrec_fold_plus
148 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
152 left
= chrec_fold_minus
153 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
154 right
= chrec_fold_minus
155 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
158 if (chrec_zerop (right
))
161 return build_polynomial_chrec
162 (CHREC_VARIABLE (poly0
), left
, right
);
167 /* Fold the multiplication of two polynomial functions. */
170 chrec_fold_multiply_poly_poly (tree type
,
179 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
180 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
182 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
183 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
184 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
185 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
186 /* poly0 is a constant wrt. poly1. */
187 return build_polynomial_chrec
188 (CHREC_VARIABLE (poly1
),
189 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
190 CHREC_RIGHT (poly1
));
192 if (CHREC_VARIABLE (poly1
) < CHREC_VARIABLE (poly0
))
193 /* poly1 is a constant wrt. poly0. */
194 return build_polynomial_chrec
195 (CHREC_VARIABLE (poly0
),
196 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
197 CHREC_RIGHT (poly0
));
199 /* poly0 and poly1 are two polynomials in the same variable,
200 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
203 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
205 /* "a*d + b*c + b*d". */
206 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
207 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
209 CHREC_LEFT (poly1
)));
210 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
212 CHREC_RIGHT (poly1
)));
214 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
215 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
216 ? build_real (type
, dconst2
)
217 : build_int_cst_type (type
, 2), t2
);
219 var
= CHREC_VARIABLE (poly0
);
220 return build_polynomial_chrec (var
, t0
,
221 build_polynomial_chrec (var
, t1
, t2
));
224 /* When the operands are automatically_generated_chrec_p, the fold has
225 to respect the semantics of the operands. */
228 chrec_fold_automatically_generated_operands (tree op0
,
231 if (op0
== chrec_dont_know
232 || op1
== chrec_dont_know
)
233 return chrec_dont_know
;
235 if (op0
== chrec_known
236 || op1
== chrec_known
)
239 if (op0
== chrec_not_analyzed_yet
240 || op1
== chrec_not_analyzed_yet
)
241 return chrec_not_analyzed_yet
;
243 /* The default case produces a safe result. */
244 return chrec_dont_know
;
247 /* Fold the addition of two chrecs. */
250 chrec_fold_plus_1 (enum tree_code code
,
255 if (automatically_generated_chrec_p (op0
)
256 || automatically_generated_chrec_p (op1
))
257 return chrec_fold_automatically_generated_operands (op0
, op1
);
259 switch (TREE_CODE (op0
))
261 case POLYNOMIAL_CHREC
:
262 switch (TREE_CODE (op1
))
264 case POLYNOMIAL_CHREC
:
265 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
268 if (code
== PLUS_EXPR
)
269 return build_polynomial_chrec
270 (CHREC_VARIABLE (op0
),
271 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
274 return build_polynomial_chrec
275 (CHREC_VARIABLE (op0
),
276 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
281 switch (TREE_CODE (op1
))
283 case POLYNOMIAL_CHREC
:
284 if (code
== PLUS_EXPR
)
285 return build_polynomial_chrec
286 (CHREC_VARIABLE (op1
),
287 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
290 return build_polynomial_chrec
291 (CHREC_VARIABLE (op1
),
292 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
293 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
294 SCALAR_FLOAT_TYPE_P (type
)
295 ? build_real (type
, dconstm1
)
296 : build_int_cst_type (type
, -1)));
301 if ((tree_contains_chrecs (op0
, &size
)
302 || tree_contains_chrecs (op1
, &size
))
303 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
304 return build2 (code
, type
, op0
, op1
);
305 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
306 return fold_build2 (code
, type
,
307 fold_convert (type
, op0
),
308 fold_convert (type
, op1
));
310 return chrec_dont_know
;
316 /* Fold the addition of two chrecs. */
319 chrec_fold_plus (tree type
,
323 if (integer_zerop (op0
))
325 if (integer_zerop (op1
))
328 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
331 /* Fold the subtraction of two chrecs. */
334 chrec_fold_minus (tree type
,
338 if (integer_zerop (op1
))
341 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
344 /* Fold the multiplication of two chrecs. */
347 chrec_fold_multiply (tree type
,
351 if (automatically_generated_chrec_p (op0
)
352 || automatically_generated_chrec_p (op1
))
353 return chrec_fold_automatically_generated_operands (op0
, op1
);
355 switch (TREE_CODE (op0
))
357 case POLYNOMIAL_CHREC
:
358 switch (TREE_CODE (op1
))
360 case POLYNOMIAL_CHREC
:
361 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
364 if (integer_onep (op1
))
366 if (integer_zerop (op1
))
367 return build_int_cst_type (type
, 0);
369 return build_polynomial_chrec
370 (CHREC_VARIABLE (op0
),
371 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
372 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
376 if (integer_onep (op0
))
379 if (integer_zerop (op0
))
380 return build_int_cst_type (type
, 0);
382 switch (TREE_CODE (op1
))
384 case POLYNOMIAL_CHREC
:
385 return build_polynomial_chrec
386 (CHREC_VARIABLE (op1
),
387 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
388 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
391 if (integer_onep (op1
))
393 if (integer_zerop (op1
))
394 return build_int_cst_type (type
, 0);
395 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
404 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
405 calculation overflows, otherwise return C(n,k) with type TYPE. */
408 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
410 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
411 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
415 /* Handle the most frequent cases. */
417 return build_int_cst (type
, 1);
419 return fold_convert (type
, n
);
421 /* Check that k <= n. */
422 if (TREE_INT_CST_HIGH (n
) == 0
423 && TREE_INT_CST_LOW (n
) < k
)
427 lnum
= TREE_INT_CST_LOW (n
);
428 hnum
= TREE_INT_CST_HIGH (n
);
430 /* Denominator = 2. */
434 /* Index = Numerator-1. */
438 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
446 /* Numerator = Numerator*Index = n*(n-1). */
447 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
450 for (i
= 3; i
<= k
; i
++)
456 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
461 /* Numerator *= Index. */
462 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
465 /* Denominator *= i. */
466 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
469 /* Result = Numerator / Denominator. */
470 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
471 &lres
, &hres
, &ldum
, &hdum
);
473 res
= build_int_cst_wide (type
, lres
, hres
);
474 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
477 /* Helper function. Use the Newton's interpolating formula for
478 evaluating the value of the evolution function. */
481 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
483 tree arg0
, arg1
, binomial_n_k
;
484 tree type
= TREE_TYPE (chrec
);
486 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
487 && CHREC_VARIABLE (chrec
) > var
)
488 chrec
= CHREC_LEFT (chrec
);
490 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
491 && CHREC_VARIABLE (chrec
) == var
)
493 arg0
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
494 if (arg0
== chrec_dont_know
)
495 return chrec_dont_know
;
496 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
498 return chrec_dont_know
;
499 arg1
= fold_build2 (MULT_EXPR
, type
,
500 CHREC_LEFT (chrec
), binomial_n_k
);
501 return chrec_fold_plus (type
, arg0
, arg1
);
504 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
506 return chrec_dont_know
;
508 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
511 /* Evaluates "CHREC (X)" when the varying variable is VAR.
512 Example: Given the following parameters,
518 The result is given by the Newton's interpolating formula:
519 3 * \binom{10}{0} + 4 * \binom{10}{1}.
523 chrec_apply (unsigned var
,
527 tree type
= chrec_type (chrec
);
528 tree res
= chrec_dont_know
;
530 if (automatically_generated_chrec_p (chrec
)
531 || automatically_generated_chrec_p (x
)
533 /* When the symbols are defined in an outer loop, it is possible
534 to symbolically compute the apply, since the symbols are
535 constants with respect to the varying loop. */
536 || chrec_contains_symbols_defined_in_loop (chrec
, var
)
537 || chrec_contains_symbols (x
))
538 return chrec_dont_know
;
540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
541 fprintf (dump_file
, "(chrec_apply \n");
543 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
544 x
= build_real_from_int_cst (type
, x
);
546 if (evolution_function_is_affine_p (chrec
))
548 /* "{a, +, b} (x)" -> "a + b*x". */
549 if (TREE_CODE (CHREC_LEFT (chrec
)) == INTEGER_CST
550 && integer_zerop (CHREC_LEFT (chrec
)))
551 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
554 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
),
555 chrec_fold_multiply (type
,
556 CHREC_RIGHT (chrec
), x
));
559 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
562 else if (TREE_CODE (x
) == INTEGER_CST
563 && tree_int_cst_sgn (x
) == 1)
564 /* testsuite/.../ssa-chrec-38.c. */
565 res
= chrec_evaluate (var
, chrec
, x
, 0);
568 res
= chrec_dont_know
;
570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
572 fprintf (dump_file
, " (varying_loop = %d\n", var
);
573 fprintf (dump_file
, ")\n (chrec = ");
574 print_generic_expr (dump_file
, chrec
, 0);
575 fprintf (dump_file
, ")\n (x = ");
576 print_generic_expr (dump_file
, x
, 0);
577 fprintf (dump_file
, ")\n (res = ");
578 print_generic_expr (dump_file
, res
, 0);
579 fprintf (dump_file
, "))\n");
585 /* Replaces the initial condition in CHREC with INIT_COND. */
588 chrec_replace_initial_condition (tree chrec
,
591 if (automatically_generated_chrec_p (chrec
))
594 switch (TREE_CODE (chrec
))
596 case POLYNOMIAL_CHREC
:
597 return build_polynomial_chrec
598 (CHREC_VARIABLE (chrec
),
599 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
600 CHREC_RIGHT (chrec
));
607 /* Returns the initial condition of a given CHREC. */
610 initial_condition (tree chrec
)
612 if (automatically_generated_chrec_p (chrec
))
615 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
616 return initial_condition (CHREC_LEFT (chrec
));
621 /* Returns a univariate function that represents the evolution in
622 LOOP_NUM. Mask the evolution of any other loop. */
625 hide_evolution_in_other_loops_than_loop (tree chrec
,
628 if (automatically_generated_chrec_p (chrec
))
631 switch (TREE_CODE (chrec
))
633 case POLYNOMIAL_CHREC
:
634 if (CHREC_VARIABLE (chrec
) == loop_num
)
635 return build_polynomial_chrec
637 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
639 CHREC_RIGHT (chrec
));
641 else if (CHREC_VARIABLE (chrec
) < loop_num
)
642 /* There is no evolution in this loop. */
643 return initial_condition (chrec
);
646 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
654 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
655 true, otherwise returns the initial condition in LOOP_NUM. */
658 chrec_component_in_loop_num (tree chrec
,
664 if (automatically_generated_chrec_p (chrec
))
667 switch (TREE_CODE (chrec
))
669 case POLYNOMIAL_CHREC
:
670 if (CHREC_VARIABLE (chrec
) == loop_num
)
673 component
= CHREC_RIGHT (chrec
);
675 component
= CHREC_LEFT (chrec
);
677 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
678 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
682 return build_polynomial_chrec
684 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
690 else if (CHREC_VARIABLE (chrec
) < loop_num
)
691 /* There is no evolution part in this loop. */
695 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
707 /* Returns the evolution part in LOOP_NUM. Example: the call
708 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
712 evolution_part_in_loop_num (tree chrec
,
715 return chrec_component_in_loop_num (chrec
, loop_num
, true);
718 /* Returns the initial condition in LOOP_NUM. Example: the call
719 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
723 initial_condition_in_loop_num (tree chrec
,
726 return chrec_component_in_loop_num (chrec
, loop_num
, false);
729 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
730 This function is essentially used for setting the evolution to
731 chrec_dont_know, for example after having determined that it is
732 impossible to say how many times a loop will execute. */
735 reset_evolution_in_loop (unsigned loop_num
,
739 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
740 && CHREC_VARIABLE (chrec
) > loop_num
)
742 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
744 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
746 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
747 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
751 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
752 && CHREC_VARIABLE (chrec
) == loop_num
)
753 chrec
= CHREC_LEFT (chrec
);
755 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
758 /* Merges two evolution functions that were found by following two
759 alternate paths of a conditional expression. */
762 chrec_merge (tree chrec1
,
765 if (chrec1
== chrec_dont_know
766 || chrec2
== chrec_dont_know
)
767 return chrec_dont_know
;
769 if (chrec1
== chrec_known
770 || chrec2
== chrec_known
)
773 if (chrec1
== chrec_not_analyzed_yet
)
775 if (chrec2
== chrec_not_analyzed_yet
)
778 if (operand_equal_p (chrec1
, chrec2
, 0))
781 return chrec_dont_know
;
788 /* Helper function for is_multivariate_chrec. */
791 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
793 if (chrec
== NULL_TREE
)
796 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
798 if (CHREC_VARIABLE (chrec
) != rec_var
)
801 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
802 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
808 /* Determine whether the given chrec is multivariate or not. */
811 is_multivariate_chrec (tree chrec
)
813 if (chrec
== NULL_TREE
)
816 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
817 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
818 CHREC_VARIABLE (chrec
))
819 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
820 CHREC_VARIABLE (chrec
)));
825 /* Determines whether the chrec contains symbolic names or not. */
828 chrec_contains_symbols (tree chrec
)
830 if (chrec
== NULL_TREE
)
833 if (TREE_CODE (chrec
) == SSA_NAME
834 || TREE_CODE (chrec
) == VAR_DECL
835 || TREE_CODE (chrec
) == PARM_DECL
836 || TREE_CODE (chrec
) == FUNCTION_DECL
837 || TREE_CODE (chrec
) == LABEL_DECL
838 || TREE_CODE (chrec
) == RESULT_DECL
839 || TREE_CODE (chrec
) == FIELD_DECL
)
842 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
845 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
849 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
853 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
861 /* Determines whether the chrec contains undetermined coefficients. */
864 chrec_contains_undetermined (tree chrec
)
866 if (chrec
== chrec_dont_know
867 || chrec
== chrec_not_analyzed_yet
868 || chrec
== NULL_TREE
)
871 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
874 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
878 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
882 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
890 /* Determines whether the tree EXPR contains chrecs, and increment
891 SIZE if it is not a NULL pointer by an estimation of the depth of
895 tree_contains_chrecs (tree expr
, int *size
)
897 if (expr
== NULL_TREE
)
903 if (tree_is_chrec (expr
))
906 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
909 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
913 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
917 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
925 /* Recursive helper function. */
928 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
930 if (evolution_function_is_constant_p (chrec
))
933 if (TREE_CODE (chrec
) == SSA_NAME
934 && expr_invariant_in_loop_p (current_loops
->parray
[loopnum
],
938 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
940 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
941 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
943 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
949 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
952 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
957 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
969 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
972 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
974 if (evolution_function_is_constant_p (chrec
))
977 if (current_loops
!= NULL
)
978 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
983 /* Determine whether the given tree is an affine multivariate
987 evolution_function_is_affine_multivariate_p (tree chrec
)
989 if (chrec
== NULL_TREE
)
992 switch (TREE_CODE (chrec
))
994 case POLYNOMIAL_CHREC
:
995 if (evolution_function_is_invariant_p (CHREC_LEFT (chrec
),
996 CHREC_VARIABLE (chrec
)))
998 if (evolution_function_is_invariant_p (CHREC_RIGHT (chrec
),
999 CHREC_VARIABLE (chrec
)))
1003 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1004 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1005 != CHREC_VARIABLE (chrec
)
1006 && evolution_function_is_affine_multivariate_p
1007 (CHREC_RIGHT (chrec
)))
1015 if (evolution_function_is_invariant_p (CHREC_RIGHT (chrec
),
1016 CHREC_VARIABLE (chrec
))
1017 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1018 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1019 && evolution_function_is_affine_multivariate_p
1020 (CHREC_LEFT (chrec
)))
1031 /* Determine whether the given tree is a function in zero or one
1035 evolution_function_is_univariate_p (tree chrec
)
1037 if (chrec
== NULL_TREE
)
1040 switch (TREE_CODE (chrec
))
1042 case POLYNOMIAL_CHREC
:
1043 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1045 case POLYNOMIAL_CHREC
:
1046 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1048 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1056 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1058 case POLYNOMIAL_CHREC
:
1059 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1061 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1074 /* Returns the number of variables of CHREC. Example: the call
1075 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1078 nb_vars_in_chrec (tree chrec
)
1080 if (chrec
== NULL_TREE
)
1083 switch (TREE_CODE (chrec
))
1085 case POLYNOMIAL_CHREC
:
1086 return 1 + nb_vars_in_chrec
1087 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1096 /* Convert CHREC to TYPE. When the analyzer knows the context in
1097 which the CHREC is built, it sets AT_STMT to the statement that
1098 contains the definition of the analyzed variable, otherwise the
1099 conversion is less accurate: the information is used for
1100 determining a more accurate estimation of the number of iterations.
1101 By default AT_STMT could be safely set to NULL_TREE.
1103 The following rule is always true: TREE_TYPE (chrec) ==
1104 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1105 An example of what could happen when adding two chrecs and the type
1106 of the CHREC_RIGHT is different than CHREC_LEFT is:
1108 {(uint) 0, +, (uchar) 10} +
1109 {(uint) 0, +, (uchar) 250}
1111 that would produce a wrong result if CHREC_RIGHT is not (uint):
1113 {(uint) 0, +, (uchar) 4}
1117 {(uint) 0, +, (uint) 260}
1121 chrec_convert (tree type
, tree chrec
, tree at_stmt
)
1125 if (automatically_generated_chrec_p (chrec
))
1128 ct
= chrec_type (chrec
);
1132 if (evolution_function_is_affine_p (chrec
))
1136 struct loop
*loop
= current_loops
->parray
[CHREC_VARIABLE (chrec
)];
1138 base
= instantiate_parameters (loop
, CHREC_LEFT (chrec
));
1139 step
= instantiate_parameters (loop
, CHREC_RIGHT (chrec
));
1141 /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1142 when it is not possible to prove that the scev does not wrap.
1143 See PR22236, where a sequence 1, 2, ..., 255 has to be
1144 converted to signed char, but this would wrap:
1145 1, 2, ..., 127, -128, ... The result should not be
1146 {(schar)1, +, (schar)1}_x, but instead, we should keep the
1147 conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
1148 if (scev_probably_wraps_p (type
, base
, step
, at_stmt
, loop
,
1150 goto failed_to_convert
;
1152 step
= convert_step (loop
, type
, base
, step
, at_stmt
);
1156 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1158 fprintf (dump_file
, "(failed conversion:");
1159 fprintf (dump_file
, "\n type: ");
1160 print_generic_expr (dump_file
, type
, 0);
1161 fprintf (dump_file
, "\n base: ");
1162 print_generic_expr (dump_file
, base
, 0);
1163 fprintf (dump_file
, "\n step: ");
1164 print_generic_expr (dump_file
, step
, 0);
1165 fprintf (dump_file
, "\n estimated_nb_iterations: ");
1166 print_generic_expr (dump_file
, loop
->estimated_nb_iterations
, 0);
1167 fprintf (dump_file
, "\n)\n");
1170 return fold_convert (type
, chrec
);
1173 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1174 chrec_convert (type
, CHREC_LEFT (chrec
),
1179 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1180 return chrec_dont_know
;
1182 res
= fold_convert (type
, chrec
);
1184 /* Don't propagate overflows. */
1185 if (CONSTANT_CLASS_P (res
))
1187 TREE_CONSTANT_OVERFLOW (res
) = 0;
1188 TREE_OVERFLOW (res
) = 0;
1191 /* But reject constants that don't fit in their type after conversion.
1192 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1193 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1194 and can cause problems later when computing niters of loops. Note
1195 that we don't do the check before converting because we don't want
1196 to reject conversions of negative chrecs to unsigned types. */
1197 if (TREE_CODE (res
) == INTEGER_CST
1198 && TREE_CODE (type
) == INTEGER_TYPE
1199 && !int_fits_type_p (res
, type
))
1200 res
= chrec_dont_know
;
1205 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1206 chrec if something else than what chrec_convert would do happens, NULL_TREE
1210 chrec_convert_aggressive (tree type
, tree chrec
)
1212 tree inner_type
, left
, right
, lc
, rc
;
1214 if (automatically_generated_chrec_p (chrec
)
1215 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1218 inner_type
= TREE_TYPE (chrec
);
1219 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1222 left
= CHREC_LEFT (chrec
);
1223 right
= CHREC_RIGHT (chrec
);
1224 lc
= chrec_convert_aggressive (type
, left
);
1226 lc
= chrec_convert (type
, left
, NULL_TREE
);
1227 rc
= chrec_convert_aggressive (type
, right
);
1229 rc
= chrec_convert (type
, right
, NULL_TREE
);
1231 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1234 /* Returns the type of the chrec. */
1237 chrec_type (tree chrec
)
1239 if (automatically_generated_chrec_p (chrec
))
1242 return TREE_TYPE (chrec
);
1245 /* Returns true when CHREC0 == CHREC1. */
1248 eq_evolutions_p (tree chrec0
,
1251 if (chrec0
== NULL_TREE
1252 || chrec1
== NULL_TREE
1253 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1256 if (chrec0
== chrec1
)
1259 switch (TREE_CODE (chrec0
))
1262 return integer_zerop (fold (build2 (MINUS_EXPR
, TREE_TYPE (chrec0
),
1264 case POLYNOMIAL_CHREC
:
1265 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1266 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1267 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));