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
));
66 gcc_assert (type
== chrec_type (poly
));
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
);
107 gcc_assert (chrec_type (poly0
) == chrec_type (poly1
));
108 gcc_assert (type
== chrec_type (poly0
));
111 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
112 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
113 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
114 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
116 if (code
== PLUS_EXPR
)
117 return build_polynomial_chrec
118 (CHREC_VARIABLE (poly1
),
119 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
120 CHREC_RIGHT (poly1
));
122 return build_polynomial_chrec
123 (CHREC_VARIABLE (poly1
),
124 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
125 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
126 SCALAR_FLOAT_TYPE_P (type
)
127 ? build_real (type
, dconstm1
)
128 : build_int_cst_type (type
, -1)));
131 if (CHREC_VARIABLE (poly0
) > CHREC_VARIABLE (poly1
))
133 if (code
== PLUS_EXPR
)
134 return build_polynomial_chrec
135 (CHREC_VARIABLE (poly0
),
136 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
137 CHREC_RIGHT (poly0
));
139 return build_polynomial_chrec
140 (CHREC_VARIABLE (poly0
),
141 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
142 CHREC_RIGHT (poly0
));
145 if (code
== PLUS_EXPR
)
147 left
= chrec_fold_plus
148 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
149 right
= chrec_fold_plus
150 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
154 left
= chrec_fold_minus
155 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
156 right
= chrec_fold_minus
157 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
160 if (chrec_zerop (right
))
163 return build_polynomial_chrec
164 (CHREC_VARIABLE (poly0
), left
, right
);
169 /* Fold the multiplication of two polynomial functions. */
172 chrec_fold_multiply_poly_poly (tree type
,
181 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
182 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
183 gcc_assert (chrec_type (poly0
) == chrec_type (poly1
));
184 gcc_assert (type
== chrec_type (poly0
));
186 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
187 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
188 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
189 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
190 /* poly0 is a constant wrt. poly1. */
191 return build_polynomial_chrec
192 (CHREC_VARIABLE (poly1
),
193 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
194 CHREC_RIGHT (poly1
));
196 if (CHREC_VARIABLE (poly1
) < CHREC_VARIABLE (poly0
))
197 /* poly1 is a constant wrt. poly0. */
198 return build_polynomial_chrec
199 (CHREC_VARIABLE (poly0
),
200 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
201 CHREC_RIGHT (poly0
));
203 /* poly0 and poly1 are two polynomials in the same variable,
204 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
207 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
209 /* "a*d + b*c + b*d". */
210 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
211 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
213 CHREC_LEFT (poly1
)));
214 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
216 CHREC_RIGHT (poly1
)));
218 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
219 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
220 ? build_real (type
, dconst2
)
221 : build_int_cst_type (type
, 2), t2
);
223 var
= CHREC_VARIABLE (poly0
);
224 return build_polynomial_chrec (var
, t0
,
225 build_polynomial_chrec (var
, t1
, t2
));
228 /* When the operands are automatically_generated_chrec_p, the fold has
229 to respect the semantics of the operands. */
232 chrec_fold_automatically_generated_operands (tree op0
,
235 if (op0
== chrec_dont_know
236 || op1
== chrec_dont_know
)
237 return chrec_dont_know
;
239 if (op0
== chrec_known
240 || op1
== chrec_known
)
243 if (op0
== chrec_not_analyzed_yet
244 || op1
== chrec_not_analyzed_yet
)
245 return chrec_not_analyzed_yet
;
247 /* The default case produces a safe result. */
248 return chrec_dont_know
;
251 /* Fold the addition of two chrecs. */
254 chrec_fold_plus_1 (enum tree_code code
, tree type
,
257 if (automatically_generated_chrec_p (op0
)
258 || automatically_generated_chrec_p (op1
))
259 return chrec_fold_automatically_generated_operands (op0
, op1
);
261 switch (TREE_CODE (op0
))
263 case POLYNOMIAL_CHREC
:
264 switch (TREE_CODE (op1
))
266 case POLYNOMIAL_CHREC
:
267 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
270 if (code
== PLUS_EXPR
)
271 return build_polynomial_chrec
272 (CHREC_VARIABLE (op0
),
273 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
276 return build_polynomial_chrec
277 (CHREC_VARIABLE (op0
),
278 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
283 switch (TREE_CODE (op1
))
285 case POLYNOMIAL_CHREC
:
286 if (code
== PLUS_EXPR
)
287 return build_polynomial_chrec
288 (CHREC_VARIABLE (op1
),
289 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
292 return build_polynomial_chrec
293 (CHREC_VARIABLE (op1
),
294 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
295 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
296 SCALAR_FLOAT_TYPE_P (type
)
297 ? build_real (type
, dconstm1
)
298 : build_int_cst_type (type
, -1)));
303 if ((tree_contains_chrecs (op0
, &size
)
304 || tree_contains_chrecs (op1
, &size
))
305 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
306 return build2 (code
, type
, op0
, op1
);
307 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
308 return fold_build2 (code
, type
,
309 fold_convert (type
, op0
),
310 fold_convert (type
, op1
));
312 return chrec_dont_know
;
318 /* Fold the addition of two chrecs. */
321 chrec_fold_plus (tree type
,
325 if (automatically_generated_chrec_p (op0
)
326 || automatically_generated_chrec_p (op1
))
327 return chrec_fold_automatically_generated_operands (op0
, op1
);
329 if (integer_zerop (op0
))
331 if (integer_zerop (op1
))
334 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
337 /* Fold the subtraction of two chrecs. */
340 chrec_fold_minus (tree type
,
344 if (automatically_generated_chrec_p (op0
)
345 || automatically_generated_chrec_p (op1
))
346 return chrec_fold_automatically_generated_operands (op0
, op1
);
348 if (integer_zerop (op1
))
351 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
354 /* Fold the multiplication of two chrecs. */
357 chrec_fold_multiply (tree type
,
361 if (automatically_generated_chrec_p (op0
)
362 || automatically_generated_chrec_p (op1
))
363 return chrec_fold_automatically_generated_operands (op0
, op1
);
365 switch (TREE_CODE (op0
))
367 case POLYNOMIAL_CHREC
:
368 switch (TREE_CODE (op1
))
370 case POLYNOMIAL_CHREC
:
371 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
374 if (integer_onep (op1
))
376 if (integer_zerop (op1
))
377 return build_int_cst_type (type
, 0);
379 return build_polynomial_chrec
380 (CHREC_VARIABLE (op0
),
381 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
382 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
386 if (integer_onep (op0
))
389 if (integer_zerop (op0
))
390 return build_int_cst_type (type
, 0);
392 switch (TREE_CODE (op1
))
394 case POLYNOMIAL_CHREC
:
395 return build_polynomial_chrec
396 (CHREC_VARIABLE (op1
),
397 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
398 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
401 if (integer_onep (op1
))
403 if (integer_zerop (op1
))
404 return build_int_cst_type (type
, 0);
405 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
414 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
415 calculation overflows, otherwise return C(n,k) with type TYPE. */
418 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
420 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
421 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
425 /* Handle the most frequent cases. */
427 return build_int_cst (type
, 1);
429 return fold_convert (type
, n
);
431 /* Check that k <= n. */
432 if (TREE_INT_CST_HIGH (n
) == 0
433 && TREE_INT_CST_LOW (n
) < k
)
437 lnum
= TREE_INT_CST_LOW (n
);
438 hnum
= TREE_INT_CST_HIGH (n
);
440 /* Denominator = 2. */
444 /* Index = Numerator-1. */
448 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
456 /* Numerator = Numerator*Index = n*(n-1). */
457 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
460 for (i
= 3; i
<= k
; i
++)
466 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
471 /* Numerator *= Index. */
472 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
475 /* Denominator *= i. */
476 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
479 /* Result = Numerator / Denominator. */
480 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
481 &lres
, &hres
, &ldum
, &hdum
);
483 res
= build_int_cst_wide (type
, lres
, hres
);
484 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
487 /* Helper function. Use the Newton's interpolating formula for
488 evaluating the value of the evolution function. */
491 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
493 tree arg0
, arg1
, binomial_n_k
;
494 tree type
= TREE_TYPE (chrec
);
496 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
497 && CHREC_VARIABLE (chrec
) > var
)
498 chrec
= CHREC_LEFT (chrec
);
500 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
501 && CHREC_VARIABLE (chrec
) == var
)
503 arg0
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
504 if (arg0
== chrec_dont_know
)
505 return chrec_dont_know
;
506 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
508 return chrec_dont_know
;
509 arg1
= fold_build2 (MULT_EXPR
, type
,
510 CHREC_LEFT (chrec
), binomial_n_k
);
511 return chrec_fold_plus (type
, arg0
, arg1
);
514 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
516 return chrec_dont_know
;
518 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
521 /* Evaluates "CHREC (X)" when the varying variable is VAR.
522 Example: Given the following parameters,
528 The result is given by the Newton's interpolating formula:
529 3 * \binom{10}{0} + 4 * \binom{10}{1}.
533 chrec_apply (unsigned var
,
537 tree type
= chrec_type (chrec
);
538 tree res
= chrec_dont_know
;
540 if (automatically_generated_chrec_p (chrec
)
541 || automatically_generated_chrec_p (x
)
543 /* When the symbols are defined in an outer loop, it is possible
544 to symbolically compute the apply, since the symbols are
545 constants with respect to the varying loop. */
546 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
547 return chrec_dont_know
;
549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
550 fprintf (dump_file
, "(chrec_apply \n");
552 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
553 x
= build_real_from_int_cst (type
, x
);
555 if (evolution_function_is_affine_p (chrec
))
557 /* "{a, +, b} (x)" -> "a + b*x". */
558 x
= chrec_convert (type
, x
, NULL_TREE
);
559 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
560 if (!integer_zerop (CHREC_LEFT (chrec
)))
561 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
564 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
567 else if (TREE_CODE (x
) == INTEGER_CST
568 && tree_int_cst_sgn (x
) == 1)
569 /* testsuite/.../ssa-chrec-38.c. */
570 res
= chrec_evaluate (var
, chrec
, x
, 0);
572 res
= chrec_dont_know
;
574 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
576 fprintf (dump_file
, " (varying_loop = %d\n", var
);
577 fprintf (dump_file
, ")\n (chrec = ");
578 print_generic_expr (dump_file
, chrec
, 0);
579 fprintf (dump_file
, ")\n (x = ");
580 print_generic_expr (dump_file
, x
, 0);
581 fprintf (dump_file
, ")\n (res = ");
582 print_generic_expr (dump_file
, res
, 0);
583 fprintf (dump_file
, "))\n");
589 /* Replaces the initial condition in CHREC with INIT_COND. */
592 chrec_replace_initial_condition (tree chrec
,
595 if (automatically_generated_chrec_p (chrec
))
598 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
600 switch (TREE_CODE (chrec
))
602 case POLYNOMIAL_CHREC
:
603 return build_polynomial_chrec
604 (CHREC_VARIABLE (chrec
),
605 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
606 CHREC_RIGHT (chrec
));
613 /* Returns the initial condition of a given CHREC. */
616 initial_condition (tree chrec
)
618 if (automatically_generated_chrec_p (chrec
))
621 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
622 return initial_condition (CHREC_LEFT (chrec
));
627 /* Returns a univariate function that represents the evolution in
628 LOOP_NUM. Mask the evolution of any other loop. */
631 hide_evolution_in_other_loops_than_loop (tree chrec
,
634 if (automatically_generated_chrec_p (chrec
))
637 switch (TREE_CODE (chrec
))
639 case POLYNOMIAL_CHREC
:
640 if (CHREC_VARIABLE (chrec
) == loop_num
)
641 return build_polynomial_chrec
643 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
645 CHREC_RIGHT (chrec
));
647 else if (CHREC_VARIABLE (chrec
) < loop_num
)
648 /* There is no evolution in this loop. */
649 return initial_condition (chrec
);
652 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
660 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
661 true, otherwise returns the initial condition in LOOP_NUM. */
664 chrec_component_in_loop_num (tree chrec
,
670 if (automatically_generated_chrec_p (chrec
))
673 switch (TREE_CODE (chrec
))
675 case POLYNOMIAL_CHREC
:
676 if (CHREC_VARIABLE (chrec
) == loop_num
)
679 component
= CHREC_RIGHT (chrec
);
681 component
= CHREC_LEFT (chrec
);
683 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
684 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
688 return build_polynomial_chrec
690 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
696 else if (CHREC_VARIABLE (chrec
) < loop_num
)
697 /* There is no evolution part in this loop. */
701 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
713 /* Returns the evolution part in LOOP_NUM. Example: the call
714 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
718 evolution_part_in_loop_num (tree chrec
,
721 return chrec_component_in_loop_num (chrec
, loop_num
, true);
724 /* Returns the initial condition in LOOP_NUM. Example: the call
725 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
729 initial_condition_in_loop_num (tree chrec
,
732 return chrec_component_in_loop_num (chrec
, loop_num
, false);
735 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
736 This function is essentially used for setting the evolution to
737 chrec_dont_know, for example after having determined that it is
738 impossible to say how many times a loop will execute. */
741 reset_evolution_in_loop (unsigned loop_num
,
745 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
747 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
748 && CHREC_VARIABLE (chrec
) > loop_num
)
750 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
752 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
754 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
755 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
759 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
760 && CHREC_VARIABLE (chrec
) == loop_num
)
761 chrec
= CHREC_LEFT (chrec
);
763 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
766 /* Merges two evolution functions that were found by following two
767 alternate paths of a conditional expression. */
770 chrec_merge (tree chrec1
,
773 if (chrec1
== chrec_dont_know
774 || chrec2
== chrec_dont_know
)
775 return chrec_dont_know
;
777 if (chrec1
== chrec_known
778 || chrec2
== chrec_known
)
781 if (chrec1
== chrec_not_analyzed_yet
)
783 if (chrec2
== chrec_not_analyzed_yet
)
786 if (operand_equal_p (chrec1
, chrec2
, 0))
789 return chrec_dont_know
;
796 /* Helper function for is_multivariate_chrec. */
799 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
801 if (chrec
== NULL_TREE
)
804 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
806 if (CHREC_VARIABLE (chrec
) != rec_var
)
809 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
810 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
816 /* Determine whether the given chrec is multivariate or not. */
819 is_multivariate_chrec (tree chrec
)
821 if (chrec
== NULL_TREE
)
824 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
825 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
826 CHREC_VARIABLE (chrec
))
827 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
828 CHREC_VARIABLE (chrec
)));
833 /* Determines whether the chrec contains symbolic names or not. */
836 chrec_contains_symbols (tree chrec
)
838 if (chrec
== NULL_TREE
)
841 if (TREE_CODE (chrec
) == SSA_NAME
842 || TREE_CODE (chrec
) == VAR_DECL
843 || TREE_CODE (chrec
) == PARM_DECL
844 || TREE_CODE (chrec
) == FUNCTION_DECL
845 || TREE_CODE (chrec
) == LABEL_DECL
846 || TREE_CODE (chrec
) == RESULT_DECL
847 || TREE_CODE (chrec
) == FIELD_DECL
)
850 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
853 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
857 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
861 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
869 /* Determines whether the chrec contains undetermined coefficients. */
872 chrec_contains_undetermined (tree chrec
)
874 if (chrec
== chrec_dont_know
875 || chrec
== chrec_not_analyzed_yet
876 || chrec
== NULL_TREE
)
879 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
882 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
886 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
890 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
898 /* Determines whether the tree EXPR contains chrecs, and increment
899 SIZE if it is not a NULL pointer by an estimation of the depth of
903 tree_contains_chrecs (tree expr
, int *size
)
905 if (expr
== NULL_TREE
)
911 if (tree_is_chrec (expr
))
914 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
917 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
921 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
925 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
933 /* Recursive helper function. */
936 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
938 if (evolution_function_is_constant_p (chrec
))
941 if (TREE_CODE (chrec
) == SSA_NAME
942 && expr_invariant_in_loop_p (current_loops
->parray
[loopnum
],
946 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
948 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
949 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
951 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
957 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
960 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
965 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
977 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
980 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
982 if (evolution_function_is_constant_p (chrec
))
985 if (current_loops
!= NULL
)
986 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
991 /* Determine whether the given tree is an affine multivariate
995 evolution_function_is_affine_multivariate_p (tree chrec
)
997 if (chrec
== NULL_TREE
)
1000 switch (TREE_CODE (chrec
))
1002 case POLYNOMIAL_CHREC
:
1003 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
1005 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
1009 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1010 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1011 != CHREC_VARIABLE (chrec
)
1012 && evolution_function_is_affine_multivariate_p
1013 (CHREC_RIGHT (chrec
)))
1021 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
1022 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1023 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1024 && evolution_function_is_affine_multivariate_p
1025 (CHREC_LEFT (chrec
)))
1036 /* Determine whether the given tree is a function in zero or one
1040 evolution_function_is_univariate_p (tree chrec
)
1042 if (chrec
== NULL_TREE
)
1045 switch (TREE_CODE (chrec
))
1047 case POLYNOMIAL_CHREC
:
1048 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1050 case POLYNOMIAL_CHREC
:
1051 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1053 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1061 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1063 case POLYNOMIAL_CHREC
:
1064 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1066 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1079 /* Returns the number of variables of CHREC. Example: the call
1080 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1083 nb_vars_in_chrec (tree chrec
)
1085 if (chrec
== NULL_TREE
)
1088 switch (TREE_CODE (chrec
))
1090 case POLYNOMIAL_CHREC
:
1091 return 1 + nb_vars_in_chrec
1092 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1101 /* Convert CHREC to TYPE. When the analyzer knows the context in
1102 which the CHREC is built, it sets AT_STMT to the statement that
1103 contains the definition of the analyzed variable, otherwise the
1104 conversion is less accurate: the information is used for
1105 determining a more accurate estimation of the number of iterations.
1106 By default AT_STMT could be safely set to NULL_TREE.
1108 The following rule is always true: TREE_TYPE (chrec) ==
1109 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1110 An example of what could happen when adding two chrecs and the type
1111 of the CHREC_RIGHT is different than CHREC_LEFT is:
1113 {(uint) 0, +, (uchar) 10} +
1114 {(uint) 0, +, (uchar) 250}
1116 that would produce a wrong result if CHREC_RIGHT is not (uint):
1118 {(uint) 0, +, (uchar) 4}
1122 {(uint) 0, +, (uint) 260}
1126 chrec_convert (tree type
, tree chrec
, tree at_stmt
)
1130 if (automatically_generated_chrec_p (chrec
))
1133 ct
= chrec_type (chrec
);
1137 if (evolution_function_is_affine_p (chrec
))
1141 struct loop
*loop
= current_loops
->parray
[CHREC_VARIABLE (chrec
)];
1143 base
= instantiate_parameters (loop
, CHREC_LEFT (chrec
));
1144 step
= instantiate_parameters (loop
, CHREC_RIGHT (chrec
));
1146 /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1147 when it is not possible to prove that the scev does not wrap.
1148 See PR22236, where a sequence 1, 2, ..., 255 has to be
1149 converted to signed char, but this would wrap:
1150 1, 2, ..., 127, -128, ... The result should not be
1151 {(schar)1, +, (schar)1}_x, but instead, we should keep the
1152 conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
1153 if (scev_probably_wraps_p (type
, base
, step
, at_stmt
, loop
,
1155 goto failed_to_convert
;
1157 step
= convert_step (loop
, type
, base
, step
, at_stmt
);
1161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1163 fprintf (dump_file
, "(failed conversion:");
1164 fprintf (dump_file
, "\n type: ");
1165 print_generic_expr (dump_file
, type
, 0);
1166 fprintf (dump_file
, "\n base: ");
1167 print_generic_expr (dump_file
, base
, 0);
1168 fprintf (dump_file
, "\n step: ");
1169 print_generic_expr (dump_file
, step
, 0);
1170 fprintf (dump_file
, "\n estimated_nb_iterations: ");
1171 print_generic_expr (dump_file
, loop
->estimated_nb_iterations
, 0);
1172 fprintf (dump_file
, "\n)\n");
1175 return fold_convert (type
, chrec
);
1178 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1179 chrec_convert (type
, CHREC_LEFT (chrec
),
1184 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1185 return chrec_dont_know
;
1187 res
= fold_convert (type
, chrec
);
1189 /* Don't propagate overflows. */
1190 if (CONSTANT_CLASS_P (res
))
1192 TREE_CONSTANT_OVERFLOW (res
) = 0;
1193 TREE_OVERFLOW (res
) = 0;
1196 /* But reject constants that don't fit in their type after conversion.
1197 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1198 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1199 and can cause problems later when computing niters of loops. Note
1200 that we don't do the check before converting because we don't want
1201 to reject conversions of negative chrecs to unsigned types. */
1202 if (TREE_CODE (res
) == INTEGER_CST
1203 && TREE_CODE (type
) == INTEGER_TYPE
1204 && !int_fits_type_p (res
, type
))
1205 res
= chrec_dont_know
;
1210 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1211 chrec if something else than what chrec_convert would do happens, NULL_TREE
1215 chrec_convert_aggressive (tree type
, tree chrec
)
1217 tree inner_type
, left
, right
, lc
, rc
;
1219 if (automatically_generated_chrec_p (chrec
)
1220 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1223 inner_type
= TREE_TYPE (chrec
);
1224 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1227 left
= CHREC_LEFT (chrec
);
1228 right
= CHREC_RIGHT (chrec
);
1229 lc
= chrec_convert_aggressive (type
, left
);
1231 lc
= chrec_convert (type
, left
, NULL_TREE
);
1232 rc
= chrec_convert_aggressive (type
, right
);
1234 rc
= chrec_convert (type
, right
, NULL_TREE
);
1236 /* Ada creates sub-types where TYPE_MIN_VALUE/TYPE_MAX_VALUE do not
1237 cover the entire range of values allowed by TYPE_PRECISION.
1239 We do not want to optimize away conversions to such types. Long
1240 term I'd rather see the Ada front-end fixed. */
1241 if (INTEGRAL_TYPE_P (type
))
1245 t
= upper_bound_in_type (type
, inner_type
);
1246 if (! TYPE_MAX_VALUE (type
)
1247 || ! operand_equal_p (TYPE_MAX_VALUE (type
), t
, 0))
1250 t
= lower_bound_in_type (type
, inner_type
);
1251 if (! TYPE_MIN_VALUE (type
)
1252 || ! operand_equal_p (TYPE_MIN_VALUE (type
), t
, 0))
1256 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1259 /* Returns true when CHREC0 == CHREC1. */
1262 eq_evolutions_p (tree chrec0
,
1265 if (chrec0
== NULL_TREE
1266 || chrec1
== NULL_TREE
1267 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1270 if (chrec0
== chrec1
)
1273 switch (TREE_CODE (chrec0
))
1276 return operand_equal_p (chrec0
, chrec1
, 0);
1278 case POLYNOMIAL_CHREC
:
1279 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1280 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1281 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));