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"
44 /* Extended folder for chrecs. */
46 /* Determines whether CST is not a constant evolution. */
49 is_not_constant_evolution (tree cst
)
51 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
54 /* Fold CODE for a polynomial function and a constant. */
57 chrec_fold_poly_cst (enum tree_code code
,
64 gcc_assert (TREE_CODE (poly
) == POLYNOMIAL_CHREC
);
65 gcc_assert (!is_not_constant_evolution (cst
));
70 return build_polynomial_chrec
71 (CHREC_VARIABLE (poly
),
72 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
76 return build_polynomial_chrec
77 (CHREC_VARIABLE (poly
),
78 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
82 return build_polynomial_chrec
83 (CHREC_VARIABLE (poly
),
84 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
85 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
88 return chrec_dont_know
;
92 /* Fold the addition of two polynomial functions. */
95 chrec_fold_plus_poly_poly (enum tree_code code
,
104 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
105 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
108 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
109 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
110 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
111 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
113 if (code
== PLUS_EXPR
)
114 return build_polynomial_chrec
115 (CHREC_VARIABLE (poly1
),
116 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
117 CHREC_RIGHT (poly1
));
119 return build_polynomial_chrec
120 (CHREC_VARIABLE (poly1
),
121 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
122 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
123 SCALAR_FLOAT_TYPE_P (type
)
124 ? build_real (type
, dconstm1
)
125 : build_int_cst_type (type
, -1)));
128 if (CHREC_VARIABLE (poly0
) > CHREC_VARIABLE (poly1
))
130 if (code
== PLUS_EXPR
)
131 return build_polynomial_chrec
132 (CHREC_VARIABLE (poly0
),
133 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
134 CHREC_RIGHT (poly0
));
136 return build_polynomial_chrec
137 (CHREC_VARIABLE (poly0
),
138 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
139 CHREC_RIGHT (poly0
));
142 if (code
== PLUS_EXPR
)
144 left
= chrec_fold_plus
145 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
146 right
= chrec_fold_plus
147 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
151 left
= chrec_fold_minus
152 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
153 right
= chrec_fold_minus
154 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
157 if (chrec_zerop (right
))
160 return build_polynomial_chrec
161 (CHREC_VARIABLE (poly0
), left
, right
);
166 /* Fold the multiplication of two polynomial functions. */
169 chrec_fold_multiply_poly_poly (tree type
,
178 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
179 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
181 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
182 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
183 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
184 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
185 /* poly0 is a constant wrt. poly1. */
186 return build_polynomial_chrec
187 (CHREC_VARIABLE (poly1
),
188 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
189 CHREC_RIGHT (poly1
));
191 if (CHREC_VARIABLE (poly1
) < CHREC_VARIABLE (poly0
))
192 /* poly1 is a constant wrt. poly0. */
193 return build_polynomial_chrec
194 (CHREC_VARIABLE (poly0
),
195 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
196 CHREC_RIGHT (poly0
));
198 /* poly0 and poly1 are two polynomials in the same variable,
199 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
202 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
204 /* "a*d + b*c + b*d". */
205 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
206 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
208 CHREC_LEFT (poly1
)));
209 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
211 CHREC_RIGHT (poly1
)));
213 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
214 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
215 ? build_real (type
, dconst2
)
216 : build_int_cst_type (type
, 2), t2
);
218 var
= CHREC_VARIABLE (poly0
);
219 return build_polynomial_chrec (var
, t0
,
220 build_polynomial_chrec (var
, t1
, t2
));
223 /* When the operands are automatically_generated_chrec_p, the fold has
224 to respect the semantics of the operands. */
227 chrec_fold_automatically_generated_operands (tree op0
,
230 if (op0
== chrec_dont_know
231 || op1
== chrec_dont_know
)
232 return chrec_dont_know
;
234 if (op0
== chrec_known
235 || op1
== chrec_known
)
238 if (op0
== chrec_not_analyzed_yet
239 || op1
== chrec_not_analyzed_yet
)
240 return chrec_not_analyzed_yet
;
242 /* The default case produces a safe result. */
243 return chrec_dont_know
;
246 /* Fold the addition of two chrecs. */
249 chrec_fold_plus_1 (enum tree_code code
,
254 if (automatically_generated_chrec_p (op0
)
255 || automatically_generated_chrec_p (op1
))
256 return chrec_fold_automatically_generated_operands (op0
, op1
);
258 switch (TREE_CODE (op0
))
260 case POLYNOMIAL_CHREC
:
261 switch (TREE_CODE (op1
))
263 case POLYNOMIAL_CHREC
:
264 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
267 if (code
== PLUS_EXPR
)
268 return build_polynomial_chrec
269 (CHREC_VARIABLE (op0
),
270 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
273 return build_polynomial_chrec
274 (CHREC_VARIABLE (op0
),
275 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
280 switch (TREE_CODE (op1
))
282 case POLYNOMIAL_CHREC
:
283 if (code
== PLUS_EXPR
)
284 return build_polynomial_chrec
285 (CHREC_VARIABLE (op1
),
286 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
289 return build_polynomial_chrec
290 (CHREC_VARIABLE (op1
),
291 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
292 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
293 SCALAR_FLOAT_TYPE_P (type
)
294 ? build_real (type
, dconstm1
)
295 : build_int_cst_type (type
, -1)));
300 if ((tree_contains_chrecs (op0
, &size
)
301 || tree_contains_chrecs (op1
, &size
))
302 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
303 return build2 (code
, type
, op0
, op1
);
304 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
305 return fold_build2 (code
, type
,
306 fold_convert (type
, op0
),
307 fold_convert (type
, op1
));
309 return chrec_dont_know
;
315 /* Fold the addition of two chrecs. */
318 chrec_fold_plus (tree type
,
322 if (integer_zerop (op0
))
324 if (integer_zerop (op1
))
327 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
330 /* Fold the subtraction of two chrecs. */
333 chrec_fold_minus (tree type
,
337 if (integer_zerop (op1
))
340 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
343 /* Fold the multiplication of two chrecs. */
346 chrec_fold_multiply (tree type
,
350 if (automatically_generated_chrec_p (op0
)
351 || automatically_generated_chrec_p (op1
))
352 return chrec_fold_automatically_generated_operands (op0
, op1
);
354 switch (TREE_CODE (op0
))
356 case POLYNOMIAL_CHREC
:
357 switch (TREE_CODE (op1
))
359 case POLYNOMIAL_CHREC
:
360 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
363 if (integer_onep (op1
))
365 if (integer_zerop (op1
))
366 return build_int_cst_type (type
, 0);
368 return build_polynomial_chrec
369 (CHREC_VARIABLE (op0
),
370 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
371 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
375 if (integer_onep (op0
))
378 if (integer_zerop (op0
))
379 return build_int_cst_type (type
, 0);
381 switch (TREE_CODE (op1
))
383 case POLYNOMIAL_CHREC
:
384 return build_polynomial_chrec
385 (CHREC_VARIABLE (op1
),
386 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
387 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
390 if (integer_onep (op1
))
392 if (integer_zerop (op1
))
393 return build_int_cst_type (type
, 0);
394 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
403 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
404 calculation overflows, otherwise return C(n,k) with type TYPE. */
407 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
409 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
410 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
414 /* Handle the most frequent cases. */
416 return build_int_cst (type
, 1);
418 return fold_convert (type
, n
);
420 /* Check that k <= n. */
421 if (TREE_INT_CST_HIGH (n
) == 0
422 && TREE_INT_CST_LOW (n
) < k
)
426 lnum
= TREE_INT_CST_LOW (n
);
427 hnum
= TREE_INT_CST_HIGH (n
);
429 /* Denominator = 2. */
433 /* Index = Numerator-1. */
437 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
445 /* Numerator = Numerator*Index = n*(n-1). */
446 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
449 for (i
= 3; i
<= k
; i
++)
455 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
460 /* Numerator *= Index. */
461 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
464 /* Denominator *= i. */
465 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
468 /* Result = Numerator / Denominator. */
469 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
470 &lres
, &hres
, &ldum
, &hdum
);
472 res
= build_int_cst_wide (type
, lres
, hres
);
473 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
476 /* Helper function. Use the Newton's interpolating formula for
477 evaluating the value of the evolution function. */
480 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
482 tree arg0
, arg1
, binomial_n_k
;
483 tree type
= TREE_TYPE (chrec
);
485 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
486 && CHREC_VARIABLE (chrec
) > var
)
487 chrec
= CHREC_LEFT (chrec
);
489 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
490 && CHREC_VARIABLE (chrec
) == var
)
492 arg0
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
493 if (arg0
== chrec_dont_know
)
494 return chrec_dont_know
;
495 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
497 return chrec_dont_know
;
498 arg1
= fold_build2 (MULT_EXPR
, type
,
499 CHREC_LEFT (chrec
), binomial_n_k
);
500 return chrec_fold_plus (type
, arg0
, arg1
);
503 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
505 return chrec_dont_know
;
507 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
510 /* Evaluates "CHREC (X)" when the varying variable is VAR.
511 Example: Given the following parameters,
517 The result is given by the Newton's interpolating formula:
518 3 * \binom{10}{0} + 4 * \binom{10}{1}.
522 chrec_apply (unsigned var
,
526 tree type
= chrec_type (chrec
);
527 tree res
= chrec_dont_know
;
529 if (automatically_generated_chrec_p (chrec
)
530 || automatically_generated_chrec_p (x
)
532 /* When the symbols are defined in an outer loop, it is possible
533 to symbolically compute the apply, since the symbols are
534 constants with respect to the varying loop. */
535 || chrec_contains_symbols_defined_in_loop (chrec
, var
)
536 || chrec_contains_symbols (x
))
537 return chrec_dont_know
;
539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
540 fprintf (dump_file
, "(chrec_apply \n");
542 if (evolution_function_is_affine_p (chrec
))
544 /* "{a, +, b} (x)" -> "a + b*x". */
545 if (TREE_CODE (CHREC_LEFT (chrec
)) == INTEGER_CST
546 && integer_zerop (CHREC_LEFT (chrec
)))
547 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
550 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
),
551 chrec_fold_multiply (type
,
552 CHREC_RIGHT (chrec
), x
));
555 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
558 else if (TREE_CODE (x
) == INTEGER_CST
559 && tree_int_cst_sgn (x
) == 1)
560 /* testsuite/.../ssa-chrec-38.c. */
561 res
= chrec_evaluate (var
, chrec
, x
, 0);
564 res
= chrec_dont_know
;
566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
568 fprintf (dump_file
, " (varying_loop = %d\n", var
);
569 fprintf (dump_file
, ")\n (chrec = ");
570 print_generic_expr (dump_file
, chrec
, 0);
571 fprintf (dump_file
, ")\n (x = ");
572 print_generic_expr (dump_file
, x
, 0);
573 fprintf (dump_file
, ")\n (res = ");
574 print_generic_expr (dump_file
, res
, 0);
575 fprintf (dump_file
, "))\n");
581 /* Replaces the initial condition in CHREC with INIT_COND. */
584 chrec_replace_initial_condition (tree chrec
,
587 if (automatically_generated_chrec_p (chrec
))
590 switch (TREE_CODE (chrec
))
592 case POLYNOMIAL_CHREC
:
593 return build_polynomial_chrec
594 (CHREC_VARIABLE (chrec
),
595 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
596 CHREC_RIGHT (chrec
));
603 /* Returns the initial condition of a given CHREC. */
606 initial_condition (tree chrec
)
608 if (automatically_generated_chrec_p (chrec
))
611 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
612 return initial_condition (CHREC_LEFT (chrec
));
617 /* Returns a univariate function that represents the evolution in
618 LOOP_NUM. Mask the evolution of any other loop. */
621 hide_evolution_in_other_loops_than_loop (tree chrec
,
624 if (automatically_generated_chrec_p (chrec
))
627 switch (TREE_CODE (chrec
))
629 case POLYNOMIAL_CHREC
:
630 if (CHREC_VARIABLE (chrec
) == loop_num
)
631 return build_polynomial_chrec
633 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
635 CHREC_RIGHT (chrec
));
637 else if (CHREC_VARIABLE (chrec
) < loop_num
)
638 /* There is no evolution in this loop. */
639 return initial_condition (chrec
);
642 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
650 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
651 true, otherwise returns the initial condition in LOOP_NUM. */
654 chrec_component_in_loop_num (tree chrec
,
660 if (automatically_generated_chrec_p (chrec
))
663 switch (TREE_CODE (chrec
))
665 case POLYNOMIAL_CHREC
:
666 if (CHREC_VARIABLE (chrec
) == loop_num
)
669 component
= CHREC_RIGHT (chrec
);
671 component
= CHREC_LEFT (chrec
);
673 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
674 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
678 return build_polynomial_chrec
680 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
686 else if (CHREC_VARIABLE (chrec
) < loop_num
)
687 /* There is no evolution part in this loop. */
691 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
703 /* Returns the evolution part in LOOP_NUM. Example: the call
704 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
708 evolution_part_in_loop_num (tree chrec
,
711 return chrec_component_in_loop_num (chrec
, loop_num
, true);
714 /* Returns the initial condition in LOOP_NUM. Example: the call
715 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
719 initial_condition_in_loop_num (tree chrec
,
722 return chrec_component_in_loop_num (chrec
, loop_num
, false);
725 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
726 This function is essentially used for setting the evolution to
727 chrec_dont_know, for example after having determined that it is
728 impossible to say how many times a loop will execute. */
731 reset_evolution_in_loop (unsigned loop_num
,
735 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
736 && CHREC_VARIABLE (chrec
) > loop_num
)
738 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
740 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
742 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
743 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
747 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
748 && CHREC_VARIABLE (chrec
) == loop_num
)
749 chrec
= CHREC_LEFT (chrec
);
751 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
754 /* Merges two evolution functions that were found by following two
755 alternate paths of a conditional expression. */
758 chrec_merge (tree chrec1
,
761 if (chrec1
== chrec_dont_know
762 || chrec2
== chrec_dont_know
)
763 return chrec_dont_know
;
765 if (chrec1
== chrec_known
766 || chrec2
== chrec_known
)
769 if (chrec1
== chrec_not_analyzed_yet
)
771 if (chrec2
== chrec_not_analyzed_yet
)
774 if (operand_equal_p (chrec1
, chrec2
, 0))
777 return chrec_dont_know
;
784 /* Helper function for is_multivariate_chrec. */
787 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
789 if (chrec
== NULL_TREE
)
792 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
794 if (CHREC_VARIABLE (chrec
) != rec_var
)
797 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
798 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
804 /* Determine whether the given chrec is multivariate or not. */
807 is_multivariate_chrec (tree chrec
)
809 if (chrec
== NULL_TREE
)
812 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
813 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
814 CHREC_VARIABLE (chrec
))
815 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
816 CHREC_VARIABLE (chrec
)));
821 /* Determines whether the chrec contains symbolic names or not. */
824 chrec_contains_symbols (tree chrec
)
826 if (chrec
== NULL_TREE
)
829 if (TREE_CODE (chrec
) == SSA_NAME
830 || TREE_CODE (chrec
) == VAR_DECL
831 || TREE_CODE (chrec
) == PARM_DECL
832 || TREE_CODE (chrec
) == FUNCTION_DECL
833 || TREE_CODE (chrec
) == LABEL_DECL
834 || TREE_CODE (chrec
) == RESULT_DECL
835 || TREE_CODE (chrec
) == FIELD_DECL
)
838 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
841 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
845 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
849 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
857 /* Determines whether the chrec contains undetermined coefficients. */
860 chrec_contains_undetermined (tree chrec
)
862 if (chrec
== chrec_dont_know
863 || chrec
== chrec_not_analyzed_yet
864 || chrec
== NULL_TREE
)
867 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
870 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
874 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
878 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
886 /* Determines whether the tree EXPR contains chrecs, and increment
887 SIZE if it is not a NULL pointer by an estimation of the depth of
891 tree_contains_chrecs (tree expr
, int *size
)
893 if (expr
== NULL_TREE
)
899 if (tree_is_chrec (expr
))
902 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
905 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
909 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
913 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
921 /* Recursive helper function. */
924 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
926 if (evolution_function_is_constant_p (chrec
))
929 if (TREE_CODE (chrec
) == SSA_NAME
930 && expr_invariant_in_loop_p (current_loops
->parray
[loopnum
],
934 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
935 && CHREC_VARIABLE (chrec
) == (unsigned) loopnum
)
938 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
941 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
946 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
958 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
961 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
963 if (evolution_function_is_constant_p (chrec
))
966 if (current_loops
!= NULL
)
967 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
972 /* Determine whether the given tree is an affine multivariate
976 evolution_function_is_affine_multivariate_p (tree chrec
)
978 if (chrec
== NULL_TREE
)
981 switch (TREE_CODE (chrec
))
983 case POLYNOMIAL_CHREC
:
984 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
986 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
990 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
991 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
992 != CHREC_VARIABLE (chrec
)
993 && evolution_function_is_affine_multivariate_p
994 (CHREC_RIGHT (chrec
)))
1002 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
1003 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1004 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1005 && evolution_function_is_affine_multivariate_p
1006 (CHREC_LEFT (chrec
)))
1017 /* Determine whether the given tree is a function in zero or one
1021 evolution_function_is_univariate_p (tree chrec
)
1023 if (chrec
== NULL_TREE
)
1026 switch (TREE_CODE (chrec
))
1028 case POLYNOMIAL_CHREC
:
1029 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1031 case POLYNOMIAL_CHREC
:
1032 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1034 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1042 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1044 case POLYNOMIAL_CHREC
:
1045 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1047 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1060 /* Returns the number of variables of CHREC. Example: the call
1061 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1064 nb_vars_in_chrec (tree chrec
)
1066 if (chrec
== NULL_TREE
)
1069 switch (TREE_CODE (chrec
))
1071 case POLYNOMIAL_CHREC
:
1072 return 1 + nb_vars_in_chrec
1073 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1082 /* Convert CHREC to TYPE. When the analyzer knows the context in
1083 which the CHREC is built, it sets AT_STMT to the statement that
1084 contains the definition of the analyzed variable, otherwise the
1085 conversion is less accurate: the information is used for
1086 determining a more accurate estimation of the number of iterations.
1087 By default AT_STMT could be safely set to NULL_TREE.
1089 The following rule is always true: TREE_TYPE (chrec) ==
1090 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1091 An example of what could happen when adding two chrecs and the type
1092 of the CHREC_RIGHT is different than CHREC_LEFT is:
1094 {(uint) 0, +, (uchar) 10} +
1095 {(uint) 0, +, (uchar) 250}
1097 that would produce a wrong result if CHREC_RIGHT is not (uint):
1099 {(uint) 0, +, (uchar) 4}
1103 {(uint) 0, +, (uint) 260}
1107 chrec_convert (tree type
, tree chrec
, tree at_stmt
)
1111 if (automatically_generated_chrec_p (chrec
))
1114 ct
= chrec_type (chrec
);
1118 if (evolution_function_is_affine_p (chrec
))
1123 /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1124 when it is not possible to prove that the scev does not wrap.
1125 See PR22236, where a sequence 1, 2, ..., 255 has to be
1126 converted to signed char, but this would wrap:
1127 1, 2, ..., 127, -128, ... The result should not be
1128 {(schar)1, +, (schar)1}_x, but instead, we should keep the
1129 conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
1130 if (scev_probably_wraps_p (type
, CHREC_LEFT (chrec
), CHREC_RIGHT (chrec
),
1132 current_loops
->parray
[CHREC_VARIABLE (chrec
)],
1134 return fold_convert (type
, chrec
);
1136 step
= convert_step (current_loops
->parray
[CHREC_VARIABLE (chrec
)], type
,
1137 CHREC_LEFT (chrec
), CHREC_RIGHT (chrec
), at_stmt
);
1139 return fold_convert (type
, chrec
);
1141 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1142 chrec_convert (type
, CHREC_LEFT (chrec
),
1147 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1148 return chrec_dont_know
;
1150 res
= fold_convert (type
, chrec
);
1152 /* Don't propagate overflows. */
1153 if (CONSTANT_CLASS_P (res
))
1155 TREE_CONSTANT_OVERFLOW (res
) = 0;
1156 TREE_OVERFLOW (res
) = 0;
1159 /* But reject constants that don't fit in their type after conversion.
1160 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1161 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1162 and can cause problems later when computing niters of loops. Note
1163 that we don't do the check before converting because we don't want
1164 to reject conversions of negative chrecs to unsigned types. */
1165 if (TREE_CODE (res
) == INTEGER_CST
1166 && TREE_CODE (type
) == INTEGER_TYPE
1167 && !int_fits_type_p (res
, type
))
1168 res
= chrec_dont_know
;
1173 /* Returns the type of the chrec. */
1176 chrec_type (tree chrec
)
1178 if (automatically_generated_chrec_p (chrec
))
1181 return TREE_TYPE (chrec
);