1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
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"
36 #include "tree-flow.h"
37 #include "tree-chrec.h"
38 #include "tree-pass.h"
40 #include "tree-scalar-evolution.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 return chrec_dont_know
;
538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
539 fprintf (dump_file
, "(chrec_apply \n");
541 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
542 x
= build_real_from_int_cst (type
, x
);
544 if (evolution_function_is_affine_p (chrec
))
546 /* "{a, +, b} (x)" -> "a + b*x". */
547 x
= chrec_convert (type
, x
, NULL_TREE
);
548 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
549 if (!integer_zerop (CHREC_LEFT (chrec
)))
550 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
553 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
556 else if (TREE_CODE (x
) == INTEGER_CST
557 && tree_int_cst_sgn (x
) == 1)
558 /* testsuite/.../ssa-chrec-38.c. */
559 res
= chrec_evaluate (var
, chrec
, x
, 0);
561 res
= chrec_dont_know
;
563 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
565 fprintf (dump_file
, " (varying_loop = %d\n", var
);
566 fprintf (dump_file
, ")\n (chrec = ");
567 print_generic_expr (dump_file
, chrec
, 0);
568 fprintf (dump_file
, ")\n (x = ");
569 print_generic_expr (dump_file
, x
, 0);
570 fprintf (dump_file
, ")\n (res = ");
571 print_generic_expr (dump_file
, res
, 0);
572 fprintf (dump_file
, "))\n");
578 /* Replaces the initial condition in CHREC with INIT_COND. */
581 chrec_replace_initial_condition (tree chrec
,
584 if (automatically_generated_chrec_p (chrec
))
587 switch (TREE_CODE (chrec
))
589 case POLYNOMIAL_CHREC
:
590 return build_polynomial_chrec
591 (CHREC_VARIABLE (chrec
),
592 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
593 CHREC_RIGHT (chrec
));
600 /* Returns the initial condition of a given CHREC. */
603 initial_condition (tree chrec
)
605 if (automatically_generated_chrec_p (chrec
))
608 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
609 return initial_condition (CHREC_LEFT (chrec
));
614 /* Returns a univariate function that represents the evolution in
615 LOOP_NUM. Mask the evolution of any other loop. */
618 hide_evolution_in_other_loops_than_loop (tree chrec
,
621 if (automatically_generated_chrec_p (chrec
))
624 switch (TREE_CODE (chrec
))
626 case POLYNOMIAL_CHREC
:
627 if (CHREC_VARIABLE (chrec
) == loop_num
)
628 return build_polynomial_chrec
630 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
632 CHREC_RIGHT (chrec
));
634 else if (CHREC_VARIABLE (chrec
) < loop_num
)
635 /* There is no evolution in this loop. */
636 return initial_condition (chrec
);
639 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
647 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
648 true, otherwise returns the initial condition in LOOP_NUM. */
651 chrec_component_in_loop_num (tree chrec
,
657 if (automatically_generated_chrec_p (chrec
))
660 switch (TREE_CODE (chrec
))
662 case POLYNOMIAL_CHREC
:
663 if (CHREC_VARIABLE (chrec
) == loop_num
)
666 component
= CHREC_RIGHT (chrec
);
668 component
= CHREC_LEFT (chrec
);
670 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
671 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
675 return build_polynomial_chrec
677 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
683 else if (CHREC_VARIABLE (chrec
) < loop_num
)
684 /* There is no evolution part in this loop. */
688 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
700 /* Returns the evolution part in LOOP_NUM. Example: the call
701 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
705 evolution_part_in_loop_num (tree chrec
,
708 return chrec_component_in_loop_num (chrec
, loop_num
, true);
711 /* Returns the initial condition in LOOP_NUM. Example: the call
712 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
716 initial_condition_in_loop_num (tree chrec
,
719 return chrec_component_in_loop_num (chrec
, loop_num
, false);
722 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
723 This function is essentially used for setting the evolution to
724 chrec_dont_know, for example after having determined that it is
725 impossible to say how many times a loop will execute. */
728 reset_evolution_in_loop (unsigned loop_num
,
732 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
733 && CHREC_VARIABLE (chrec
) > loop_num
)
735 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
737 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
739 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
740 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
744 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
745 && CHREC_VARIABLE (chrec
) == loop_num
)
746 chrec
= CHREC_LEFT (chrec
);
748 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
751 /* Merges two evolution functions that were found by following two
752 alternate paths of a conditional expression. */
755 chrec_merge (tree chrec1
,
758 if (chrec1
== chrec_dont_know
759 || chrec2
== chrec_dont_know
)
760 return chrec_dont_know
;
762 if (chrec1
== chrec_known
763 || chrec2
== chrec_known
)
766 if (chrec1
== chrec_not_analyzed_yet
)
768 if (chrec2
== chrec_not_analyzed_yet
)
771 if (operand_equal_p (chrec1
, chrec2
, 0))
774 return chrec_dont_know
;
781 /* Helper function for is_multivariate_chrec. */
784 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
786 if (chrec
== NULL_TREE
)
789 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
791 if (CHREC_VARIABLE (chrec
) != rec_var
)
794 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
795 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
801 /* Determine whether the given chrec is multivariate or not. */
804 is_multivariate_chrec (tree chrec
)
806 if (chrec
== NULL_TREE
)
809 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
810 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
811 CHREC_VARIABLE (chrec
))
812 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
813 CHREC_VARIABLE (chrec
)));
818 /* Determines whether the chrec contains symbolic names or not. */
821 chrec_contains_symbols (tree chrec
)
823 if (chrec
== NULL_TREE
)
826 if (TREE_CODE (chrec
) == SSA_NAME
827 || TREE_CODE (chrec
) == VAR_DECL
828 || TREE_CODE (chrec
) == PARM_DECL
829 || TREE_CODE (chrec
) == FUNCTION_DECL
830 || TREE_CODE (chrec
) == LABEL_DECL
831 || TREE_CODE (chrec
) == RESULT_DECL
832 || TREE_CODE (chrec
) == FIELD_DECL
)
835 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
838 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
842 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
846 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
854 /* Determines whether the chrec contains undetermined coefficients. */
857 chrec_contains_undetermined (tree chrec
)
859 if (chrec
== chrec_dont_know
860 || chrec
== chrec_not_analyzed_yet
861 || chrec
== NULL_TREE
)
864 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
867 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
871 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
875 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
883 /* Determines whether the tree EXPR contains chrecs, and increment
884 SIZE if it is not a NULL pointer by an estimation of the depth of
888 tree_contains_chrecs (tree expr
, int *size
)
890 if (expr
== NULL_TREE
)
896 if (tree_is_chrec (expr
))
899 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
902 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
906 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
910 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
918 /* Recursive helper function. */
921 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
923 if (evolution_function_is_constant_p (chrec
))
926 if (TREE_CODE (chrec
) == SSA_NAME
927 && expr_invariant_in_loop_p (current_loops
->parray
[loopnum
],
931 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
933 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
934 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
936 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
942 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
945 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
950 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
962 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
965 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
967 if (evolution_function_is_constant_p (chrec
))
970 if (current_loops
!= NULL
)
971 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
976 /* Determine whether the given tree is an affine multivariate
980 evolution_function_is_affine_multivariate_p (tree chrec
)
982 if (chrec
== NULL_TREE
)
985 switch (TREE_CODE (chrec
))
987 case POLYNOMIAL_CHREC
:
988 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
990 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
994 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
995 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
996 != CHREC_VARIABLE (chrec
)
997 && evolution_function_is_affine_multivariate_p
998 (CHREC_RIGHT (chrec
)))
1006 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
1007 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1008 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1009 && evolution_function_is_affine_multivariate_p
1010 (CHREC_LEFT (chrec
)))
1021 /* Determine whether the given tree is a function in zero or one
1025 evolution_function_is_univariate_p (tree chrec
)
1027 if (chrec
== NULL_TREE
)
1030 switch (TREE_CODE (chrec
))
1032 case POLYNOMIAL_CHREC
:
1033 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1035 case POLYNOMIAL_CHREC
:
1036 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1038 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1046 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1048 case POLYNOMIAL_CHREC
:
1049 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1051 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1064 /* Returns the number of variables of CHREC. Example: the call
1065 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1068 nb_vars_in_chrec (tree chrec
)
1070 if (chrec
== NULL_TREE
)
1073 switch (TREE_CODE (chrec
))
1075 case POLYNOMIAL_CHREC
:
1076 return 1 + nb_vars_in_chrec
1077 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1086 /* Convert CHREC to TYPE. When the analyzer knows the context in
1087 which the CHREC is built, it sets AT_STMT to the statement that
1088 contains the definition of the analyzed variable, otherwise the
1089 conversion is less accurate: the information is used for
1090 determining a more accurate estimation of the number of iterations.
1091 By default AT_STMT could be safely set to NULL_TREE.
1093 The following rule is always true: TREE_TYPE (chrec) ==
1094 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1095 An example of what could happen when adding two chrecs and the type
1096 of the CHREC_RIGHT is different than CHREC_LEFT is:
1098 {(uint) 0, +, (uchar) 10} +
1099 {(uint) 0, +, (uchar) 250}
1101 that would produce a wrong result if CHREC_RIGHT is not (uint):
1103 {(uint) 0, +, (uchar) 4}
1107 {(uint) 0, +, (uint) 260}
1111 chrec_convert (tree type
, tree chrec
, tree at_stmt
)
1115 if (automatically_generated_chrec_p (chrec
))
1118 ct
= chrec_type (chrec
);
1122 if (evolution_function_is_affine_p (chrec
))
1126 struct loop
*loop
= current_loops
->parray
[CHREC_VARIABLE (chrec
)];
1128 base
= instantiate_parameters (loop
, CHREC_LEFT (chrec
));
1129 step
= instantiate_parameters (loop
, CHREC_RIGHT (chrec
));
1131 /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1132 when it is not possible to prove that the scev does not wrap.
1133 See PR22236, where a sequence 1, 2, ..., 255 has to be
1134 converted to signed char, but this would wrap:
1135 1, 2, ..., 127, -128, ... The result should not be
1136 {(schar)1, +, (schar)1}_x, but instead, we should keep the
1137 conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
1138 if (scev_probably_wraps_p (type
, base
, step
, at_stmt
, loop
,
1140 goto failed_to_convert
;
1142 step
= convert_step (loop
, type
, base
, step
, at_stmt
);
1146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1148 fprintf (dump_file
, "(failed conversion:");
1149 fprintf (dump_file
, "\n type: ");
1150 print_generic_expr (dump_file
, type
, 0);
1151 fprintf (dump_file
, "\n base: ");
1152 print_generic_expr (dump_file
, base
, 0);
1153 fprintf (dump_file
, "\n step: ");
1154 print_generic_expr (dump_file
, step
, 0);
1155 fprintf (dump_file
, "\n estimated_nb_iterations: ");
1156 print_generic_expr (dump_file
, loop
->estimated_nb_iterations
, 0);
1157 fprintf (dump_file
, "\n)\n");
1160 return fold_convert (type
, chrec
);
1163 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1164 chrec_convert (type
, CHREC_LEFT (chrec
),
1169 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1170 return chrec_dont_know
;
1172 res
= fold_convert (type
, chrec
);
1174 /* Don't propagate overflows. */
1175 if (CONSTANT_CLASS_P (res
))
1177 TREE_CONSTANT_OVERFLOW (res
) = 0;
1178 TREE_OVERFLOW (res
) = 0;
1181 /* But reject constants that don't fit in their type after conversion.
1182 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1183 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1184 and can cause problems later when computing niters of loops. Note
1185 that we don't do the check before converting because we don't want
1186 to reject conversions of negative chrecs to unsigned types. */
1187 if (TREE_CODE (res
) == INTEGER_CST
1188 && TREE_CODE (type
) == INTEGER_TYPE
1189 && !int_fits_type_p (res
, type
))
1190 res
= chrec_dont_know
;
1195 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1196 chrec if something else than what chrec_convert would do happens, NULL_TREE
1200 chrec_convert_aggressive (tree type
, tree chrec
)
1202 tree inner_type
, left
, right
, lc
, rc
;
1204 if (automatically_generated_chrec_p (chrec
)
1205 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1208 inner_type
= TREE_TYPE (chrec
);
1209 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1212 left
= CHREC_LEFT (chrec
);
1213 right
= CHREC_RIGHT (chrec
);
1214 lc
= chrec_convert_aggressive (type
, left
);
1216 lc
= chrec_convert (type
, left
, NULL_TREE
);
1217 rc
= chrec_convert_aggressive (type
, right
);
1219 rc
= chrec_convert (type
, right
, NULL_TREE
);
1221 /* Ada creates sub-types where TYPE_MIN_VALUE/TYPE_MAX_VALUE do not
1222 cover the entire range of values allowed by TYPE_PRECISION.
1224 We do not want to optimize away conversions to such types. Long
1225 term I'd rather see the Ada front-end fixed. */
1226 if (INTEGRAL_TYPE_P (type
))
1230 t
= upper_bound_in_type (type
, inner_type
);
1231 if (! TYPE_MAX_VALUE (type
)
1232 || ! operand_equal_p (TYPE_MAX_VALUE (type
), t
, 0))
1235 t
= lower_bound_in_type (type
, inner_type
);
1236 if (! TYPE_MIN_VALUE (type
)
1237 || ! operand_equal_p (TYPE_MIN_VALUE (type
), t
, 0))
1241 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1244 /* Returns the type of the chrec. */
1247 chrec_type (tree chrec
)
1249 if (automatically_generated_chrec_p (chrec
))
1252 return TREE_TYPE (chrec
);
1255 /* Returns true when CHREC0 == CHREC1. */
1258 eq_evolutions_p (tree chrec0
,
1261 if (chrec0
== NULL_TREE
1262 || chrec1
== NULL_TREE
1263 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1266 if (chrec0
== chrec1
)
1269 switch (TREE_CODE (chrec0
))
1272 return integer_zerop (fold (build2 (MINUS_EXPR
, TREE_TYPE (chrec0
),
1274 case POLYNOMIAL_CHREC
:
1275 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1276 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1277 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));