1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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
,
102 struct loop
*loop0
= get_chrec_loop (poly0
);
103 struct loop
*loop1
= get_chrec_loop (poly1
);
107 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
108 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
109 gcc_assert (chrec_type (poly0
) == chrec_type (poly1
));
110 gcc_assert (type
== chrec_type (poly0
));
113 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
114 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
115 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
116 if (flow_loop_nested_p (loop0
, loop1
))
118 if (code
== PLUS_EXPR
)
119 return build_polynomial_chrec
120 (CHREC_VARIABLE (poly1
),
121 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
122 CHREC_RIGHT (poly1
));
124 return build_polynomial_chrec
125 (CHREC_VARIABLE (poly1
),
126 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
127 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
128 SCALAR_FLOAT_TYPE_P (type
)
129 ? build_real (type
, dconstm1
)
130 : build_int_cst_type (type
, -1)));
133 if (flow_loop_nested_p (loop1
, loop0
))
135 if (code
== PLUS_EXPR
)
136 return build_polynomial_chrec
137 (CHREC_VARIABLE (poly0
),
138 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
139 CHREC_RIGHT (poly0
));
141 return build_polynomial_chrec
142 (CHREC_VARIABLE (poly0
),
143 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
144 CHREC_RIGHT (poly0
));
147 /* This function should never be called for chrecs of loops that
148 do not belong to the same loop nest. */
149 gcc_assert (loop0
== loop1
);
151 if (code
== PLUS_EXPR
)
153 left
= chrec_fold_plus
154 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
155 right
= chrec_fold_plus
156 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
160 left
= chrec_fold_minus
161 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
162 right
= chrec_fold_minus
163 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
166 if (chrec_zerop (right
))
169 return build_polynomial_chrec
170 (CHREC_VARIABLE (poly0
), left
, right
);
175 /* Fold the multiplication of two polynomial functions. */
178 chrec_fold_multiply_poly_poly (tree type
,
184 struct loop
*loop0
= get_chrec_loop (poly0
);
185 struct loop
*loop1
= get_chrec_loop (poly1
);
189 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
190 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
191 gcc_assert (chrec_type (poly0
) == chrec_type (poly1
));
192 gcc_assert (type
== chrec_type (poly0
));
194 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
195 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
196 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
197 if (flow_loop_nested_p (loop0
, loop1
))
198 /* poly0 is a constant wrt. poly1. */
199 return build_polynomial_chrec
200 (CHREC_VARIABLE (poly1
),
201 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
202 CHREC_RIGHT (poly1
));
204 if (flow_loop_nested_p (loop1
, loop0
))
205 /* poly1 is a constant wrt. poly0. */
206 return build_polynomial_chrec
207 (CHREC_VARIABLE (poly0
),
208 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
209 CHREC_RIGHT (poly0
));
211 gcc_assert (loop0
== loop1
);
213 /* poly0 and poly1 are two polynomials in the same variable,
214 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
217 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
219 /* "a*d + b*c + b*d". */
220 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
221 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
223 CHREC_LEFT (poly1
)));
224 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
226 CHREC_RIGHT (poly1
)));
228 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
229 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
230 ? build_real (type
, dconst2
)
231 : build_int_cst (type
, 2), t2
);
233 var
= CHREC_VARIABLE (poly0
);
234 return build_polynomial_chrec (var
, t0
,
235 build_polynomial_chrec (var
, t1
, t2
));
238 /* When the operands are automatically_generated_chrec_p, the fold has
239 to respect the semantics of the operands. */
242 chrec_fold_automatically_generated_operands (tree op0
,
245 if (op0
== chrec_dont_know
246 || op1
== chrec_dont_know
)
247 return chrec_dont_know
;
249 if (op0
== chrec_known
250 || op1
== chrec_known
)
253 if (op0
== chrec_not_analyzed_yet
254 || op1
== chrec_not_analyzed_yet
)
255 return chrec_not_analyzed_yet
;
257 /* The default case produces a safe result. */
258 return chrec_dont_know
;
261 /* Fold the addition of two chrecs. */
264 chrec_fold_plus_1 (enum tree_code code
, tree type
,
267 if (automatically_generated_chrec_p (op0
)
268 || automatically_generated_chrec_p (op1
))
269 return chrec_fold_automatically_generated_operands (op0
, op1
);
271 switch (TREE_CODE (op0
))
273 case POLYNOMIAL_CHREC
:
274 switch (TREE_CODE (op1
))
276 case POLYNOMIAL_CHREC
:
277 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
280 if (code
== PLUS_EXPR
)
281 return build_polynomial_chrec
282 (CHREC_VARIABLE (op0
),
283 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
286 return build_polynomial_chrec
287 (CHREC_VARIABLE (op0
),
288 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
293 switch (TREE_CODE (op1
))
295 case POLYNOMIAL_CHREC
:
296 if (code
== PLUS_EXPR
)
297 return build_polynomial_chrec
298 (CHREC_VARIABLE (op1
),
299 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
302 return build_polynomial_chrec
303 (CHREC_VARIABLE (op1
),
304 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
305 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
306 SCALAR_FLOAT_TYPE_P (type
)
307 ? build_real (type
, dconstm1
)
308 : build_int_cst_type (type
, -1)));
313 if ((tree_contains_chrecs (op0
, &size
)
314 || tree_contains_chrecs (op1
, &size
))
315 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
316 return build2 (code
, type
, op0
, op1
);
317 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
318 return fold_build2 (code
, type
,
319 fold_convert (type
, op0
),
320 fold_convert (type
, op1
));
322 return chrec_dont_know
;
328 /* Fold the addition of two chrecs. */
331 chrec_fold_plus (tree type
,
335 if (automatically_generated_chrec_p (op0
)
336 || automatically_generated_chrec_p (op1
))
337 return chrec_fold_automatically_generated_operands (op0
, op1
);
339 if (integer_zerop (op0
))
341 if (integer_zerop (op1
))
344 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
347 /* Fold the subtraction of two chrecs. */
350 chrec_fold_minus (tree type
,
354 if (automatically_generated_chrec_p (op0
)
355 || automatically_generated_chrec_p (op1
))
356 return chrec_fold_automatically_generated_operands (op0
, op1
);
358 if (integer_zerop (op1
))
361 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
364 /* Fold the multiplication of two chrecs. */
367 chrec_fold_multiply (tree type
,
371 if (automatically_generated_chrec_p (op0
)
372 || automatically_generated_chrec_p (op1
))
373 return chrec_fold_automatically_generated_operands (op0
, op1
);
375 switch (TREE_CODE (op0
))
377 case POLYNOMIAL_CHREC
:
378 switch (TREE_CODE (op1
))
380 case POLYNOMIAL_CHREC
:
381 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
384 if (integer_onep (op1
))
386 if (integer_zerop (op1
))
387 return build_int_cst (type
, 0);
389 return build_polynomial_chrec
390 (CHREC_VARIABLE (op0
),
391 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
392 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
396 if (integer_onep (op0
))
399 if (integer_zerop (op0
))
400 return build_int_cst (type
, 0);
402 switch (TREE_CODE (op1
))
404 case POLYNOMIAL_CHREC
:
405 return build_polynomial_chrec
406 (CHREC_VARIABLE (op1
),
407 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
408 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
411 if (integer_onep (op1
))
413 if (integer_zerop (op1
))
414 return build_int_cst (type
, 0);
415 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
424 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
425 calculation overflows, otherwise return C(n,k) with type TYPE. */
428 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
430 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
431 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
435 /* Handle the most frequent cases. */
437 return build_int_cst (type
, 1);
439 return fold_convert (type
, n
);
441 /* Check that k <= n. */
442 if (TREE_INT_CST_HIGH (n
) == 0
443 && TREE_INT_CST_LOW (n
) < k
)
447 lnum
= TREE_INT_CST_LOW (n
);
448 hnum
= TREE_INT_CST_HIGH (n
);
450 /* Denominator = 2. */
454 /* Index = Numerator-1. */
458 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
466 /* Numerator = Numerator*Index = n*(n-1). */
467 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
470 for (i
= 3; i
<= k
; i
++)
476 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
481 /* Numerator *= Index. */
482 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
485 /* Denominator *= i. */
486 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
489 /* Result = Numerator / Denominator. */
490 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
491 &lres
, &hres
, &ldum
, &hdum
);
493 res
= build_int_cst_wide (type
, lres
, hres
);
494 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
497 /* Helper function. Use the Newton's interpolating formula for
498 evaluating the value of the evolution function. */
501 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
503 tree arg0
, arg1
, binomial_n_k
;
504 tree type
= TREE_TYPE (chrec
);
505 struct loop
*var_loop
= get_loop (var
);
507 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
508 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
509 chrec
= CHREC_LEFT (chrec
);
511 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
512 && CHREC_VARIABLE (chrec
) == var
)
514 arg0
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
515 if (arg0
== chrec_dont_know
)
516 return chrec_dont_know
;
517 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
519 return chrec_dont_know
;
520 arg1
= fold_build2 (MULT_EXPR
, type
,
521 CHREC_LEFT (chrec
), binomial_n_k
);
522 return chrec_fold_plus (type
, arg0
, arg1
);
525 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
527 return chrec_dont_know
;
529 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
532 /* Evaluates "CHREC (X)" when the varying variable is VAR.
533 Example: Given the following parameters,
539 The result is given by the Newton's interpolating formula:
540 3 * \binom{10}{0} + 4 * \binom{10}{1}.
544 chrec_apply (unsigned var
,
548 tree type
= chrec_type (chrec
);
549 tree res
= chrec_dont_know
;
551 if (automatically_generated_chrec_p (chrec
)
552 || automatically_generated_chrec_p (x
)
554 /* When the symbols are defined in an outer loop, it is possible
555 to symbolically compute the apply, since the symbols are
556 constants with respect to the varying loop. */
557 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
558 return chrec_dont_know
;
560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
561 fprintf (dump_file
, "(chrec_apply \n");
563 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
564 x
= build_real_from_int_cst (type
, x
);
566 if (evolution_function_is_affine_p (chrec
))
568 /* "{a, +, b} (x)" -> "a + b*x". */
569 x
= chrec_convert (type
, x
, NULL_TREE
);
570 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
571 if (!integer_zerop (CHREC_LEFT (chrec
)))
572 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
575 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
578 else if (TREE_CODE (x
) == INTEGER_CST
579 && tree_int_cst_sgn (x
) == 1)
580 /* testsuite/.../ssa-chrec-38.c. */
581 res
= chrec_evaluate (var
, chrec
, x
, 0);
583 res
= chrec_dont_know
;
585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
587 fprintf (dump_file
, " (varying_loop = %d\n", var
);
588 fprintf (dump_file
, ")\n (chrec = ");
589 print_generic_expr (dump_file
, chrec
, 0);
590 fprintf (dump_file
, ")\n (x = ");
591 print_generic_expr (dump_file
, x
, 0);
592 fprintf (dump_file
, ")\n (res = ");
593 print_generic_expr (dump_file
, res
, 0);
594 fprintf (dump_file
, "))\n");
600 /* Replaces the initial condition in CHREC with INIT_COND. */
603 chrec_replace_initial_condition (tree chrec
,
606 if (automatically_generated_chrec_p (chrec
))
609 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
611 switch (TREE_CODE (chrec
))
613 case POLYNOMIAL_CHREC
:
614 return build_polynomial_chrec
615 (CHREC_VARIABLE (chrec
),
616 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
617 CHREC_RIGHT (chrec
));
624 /* Returns the initial condition of a given CHREC. */
627 initial_condition (tree chrec
)
629 if (automatically_generated_chrec_p (chrec
))
632 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
633 return initial_condition (CHREC_LEFT (chrec
));
638 /* Returns a univariate function that represents the evolution in
639 LOOP_NUM. Mask the evolution of any other loop. */
642 hide_evolution_in_other_loops_than_loop (tree chrec
,
645 struct loop
*loop
= get_loop (loop_num
), *chloop
;
646 if (automatically_generated_chrec_p (chrec
))
649 switch (TREE_CODE (chrec
))
651 case POLYNOMIAL_CHREC
:
652 chloop
= get_chrec_loop (chrec
);
655 return build_polynomial_chrec
657 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
659 CHREC_RIGHT (chrec
));
661 else if (flow_loop_nested_p (chloop
, loop
))
662 /* There is no evolution in this loop. */
663 return initial_condition (chrec
);
667 gcc_assert (flow_loop_nested_p (loop
, chloop
));
668 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
677 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
678 true, otherwise returns the initial condition in LOOP_NUM. */
681 chrec_component_in_loop_num (tree chrec
,
686 struct loop
*loop
= get_loop (loop_num
), *chloop
;
688 if (automatically_generated_chrec_p (chrec
))
691 switch (TREE_CODE (chrec
))
693 case POLYNOMIAL_CHREC
:
694 chloop
= get_chrec_loop (chrec
);
699 component
= CHREC_RIGHT (chrec
);
701 component
= CHREC_LEFT (chrec
);
703 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
704 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
708 return build_polynomial_chrec
710 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
716 else if (flow_loop_nested_p (chloop
, loop
))
717 /* There is no evolution part in this loop. */
722 gcc_assert (flow_loop_nested_p (loop
, chloop
));
723 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
736 /* Returns the evolution part in LOOP_NUM. Example: the call
737 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
741 evolution_part_in_loop_num (tree chrec
,
744 return chrec_component_in_loop_num (chrec
, loop_num
, true);
747 /* Returns the initial condition in LOOP_NUM. Example: the call
748 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
752 initial_condition_in_loop_num (tree chrec
,
755 return chrec_component_in_loop_num (chrec
, loop_num
, false);
758 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
759 This function is essentially used for setting the evolution to
760 chrec_dont_know, for example after having determined that it is
761 impossible to say how many times a loop will execute. */
764 reset_evolution_in_loop (unsigned loop_num
,
768 struct loop
*loop
= get_loop (loop_num
);
770 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
772 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
773 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
775 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
777 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
779 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
780 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
784 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
785 && CHREC_VARIABLE (chrec
) == loop_num
)
786 chrec
= CHREC_LEFT (chrec
);
788 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
791 /* Merges two evolution functions that were found by following two
792 alternate paths of a conditional expression. */
795 chrec_merge (tree chrec1
,
798 if (chrec1
== chrec_dont_know
799 || chrec2
== chrec_dont_know
)
800 return chrec_dont_know
;
802 if (chrec1
== chrec_known
803 || chrec2
== chrec_known
)
806 if (chrec1
== chrec_not_analyzed_yet
)
808 if (chrec2
== chrec_not_analyzed_yet
)
811 if (eq_evolutions_p (chrec1
, chrec2
))
814 return chrec_dont_know
;
821 /* Helper function for is_multivariate_chrec. */
824 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
826 if (chrec
== NULL_TREE
)
829 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
831 if (CHREC_VARIABLE (chrec
) != rec_var
)
834 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
835 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
841 /* Determine whether the given chrec is multivariate or not. */
844 is_multivariate_chrec (tree chrec
)
846 if (chrec
== NULL_TREE
)
849 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
850 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
851 CHREC_VARIABLE (chrec
))
852 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
853 CHREC_VARIABLE (chrec
)));
858 /* Determines whether the chrec contains symbolic names or not. */
861 chrec_contains_symbols (tree chrec
)
863 if (chrec
== NULL_TREE
)
866 if (TREE_CODE (chrec
) == SSA_NAME
867 || TREE_CODE (chrec
) == VAR_DECL
868 || TREE_CODE (chrec
) == PARM_DECL
869 || TREE_CODE (chrec
) == FUNCTION_DECL
870 || TREE_CODE (chrec
) == LABEL_DECL
871 || TREE_CODE (chrec
) == RESULT_DECL
872 || TREE_CODE (chrec
) == FIELD_DECL
)
875 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
878 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
882 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
886 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
894 /* Determines whether the chrec contains undetermined coefficients. */
897 chrec_contains_undetermined (tree chrec
)
899 if (chrec
== chrec_dont_know
900 || chrec
== chrec_not_analyzed_yet
901 || chrec
== NULL_TREE
)
904 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
907 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
911 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
915 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
923 /* Determines whether the tree EXPR contains chrecs, and increment
924 SIZE if it is not a NULL pointer by an estimation of the depth of
928 tree_contains_chrecs (tree expr
, int *size
)
930 if (expr
== NULL_TREE
)
936 if (tree_is_chrec (expr
))
939 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
942 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2), size
))
946 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1), size
))
950 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0), size
))
958 /* Recursive helper function. */
961 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
963 if (evolution_function_is_constant_p (chrec
))
966 if (TREE_CODE (chrec
) == SSA_NAME
967 && expr_invariant_in_loop_p (get_loop (loopnum
), chrec
))
970 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
972 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
973 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
975 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
981 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
984 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
989 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1001 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1004 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1006 if (evolution_function_is_constant_p (chrec
))
1009 if (current_loops
!= NULL
)
1010 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1015 /* Determine whether the given tree is an affine multivariate
1019 evolution_function_is_affine_multivariate_p (tree chrec
)
1021 if (chrec
== NULL_TREE
)
1024 switch (TREE_CODE (chrec
))
1026 case POLYNOMIAL_CHREC
:
1027 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
1029 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
1033 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1034 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1035 != CHREC_VARIABLE (chrec
)
1036 && evolution_function_is_affine_multivariate_p
1037 (CHREC_RIGHT (chrec
)))
1045 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
1046 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1047 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1048 && evolution_function_is_affine_multivariate_p
1049 (CHREC_LEFT (chrec
)))
1060 /* Determine whether the given tree is a function in zero or one
1064 evolution_function_is_univariate_p (tree chrec
)
1066 if (chrec
== NULL_TREE
)
1069 switch (TREE_CODE (chrec
))
1071 case POLYNOMIAL_CHREC
:
1072 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1074 case POLYNOMIAL_CHREC
:
1075 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1077 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1085 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1087 case POLYNOMIAL_CHREC
:
1088 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1090 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1103 /* Returns the number of variables of CHREC. Example: the call
1104 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1107 nb_vars_in_chrec (tree chrec
)
1109 if (chrec
== NULL_TREE
)
1112 switch (TREE_CODE (chrec
))
1114 case POLYNOMIAL_CHREC
:
1115 return 1 + nb_vars_in_chrec
1116 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1123 /* Returns true if TYPE is a type in that we cannot directly perform
1124 arithmetics, even though it is a scalar type. */
1127 avoid_arithmetics_in_type_p (tree type
)
1129 /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1130 in the subtype, but a base type must be used, and the result then can
1131 be casted to the subtype. */
1132 if (TREE_CODE (type
) == INTEGER_TYPE
&& TREE_TYPE (type
) != NULL_TREE
)
1138 static tree
chrec_convert_1 (tree
, tree
, tree
, bool);
1140 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1141 the scev corresponds to. AT_STMT is the statement at that the scev is
1142 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1143 the rules for overflow of the given language apply (e.g., that signed
1144 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1145 tests, but also to enforce that the result follows them. Returns true if the
1146 conversion succeeded, false otherwise. */
1149 convert_affine_scev (struct loop
*loop
, tree type
,
1150 tree
*base
, tree
*step
, tree at_stmt
,
1151 bool use_overflow_semantics
)
1153 tree ct
= TREE_TYPE (*step
);
1154 bool enforce_overflow_semantics
;
1155 bool must_check_src_overflow
, must_check_rslt_overflow
;
1156 tree new_base
, new_step
;
1158 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1159 if (avoid_arithmetics_in_type_p (type
))
1163 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1164 but we must check some assumptions.
1166 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1167 of CT is smaller than the precision of TYPE. For example, when we
1168 cast unsigned char [254, +, 1] to unsigned, the values on left side
1169 are 254, 255, 0, 1, ..., but those on the right side are
1170 254, 255, 256, 257, ...
1171 2) In case that we must also preserve the fact that signed ivs do not
1172 overflow, we must additionally check that the new iv does not wrap.
1173 For example, unsigned char [125, +, 1] casted to signed char could
1174 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1175 which would confuse optimizers that assume that this does not
1177 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1179 enforce_overflow_semantics
= (use_overflow_semantics
1180 && nowrap_type_p (type
));
1181 if (enforce_overflow_semantics
)
1183 /* We can avoid checking whether the result overflows in the following
1186 -- must_check_src_overflow is true, and the range of TYPE is superset
1187 of the range of CT -- i.e., in all cases except if CT signed and
1189 -- both CT and TYPE have the same precision and signedness, and we
1190 verify instead that the source does not overflow (this may be
1191 easier than verifying it for the result, as we may use the
1192 information about the semantics of overflow in CT). */
1193 if (must_check_src_overflow
)
1195 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1196 must_check_rslt_overflow
= true;
1198 must_check_rslt_overflow
= false;
1200 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1201 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1203 must_check_rslt_overflow
= false;
1204 must_check_src_overflow
= true;
1207 must_check_rslt_overflow
= true;
1210 must_check_rslt_overflow
= false;
1212 if (must_check_src_overflow
1213 && scev_probably_wraps_p (*base
, *step
, at_stmt
, loop
,
1214 use_overflow_semantics
))
1217 new_base
= chrec_convert_1 (type
, *base
, at_stmt
,
1218 use_overflow_semantics
);
1219 /* The step must be sign extended, regardless of the signedness
1220 of CT and TYPE. This only needs to be handled specially when
1221 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1222 (with values 100, 99, 98, ...) from becoming signed or unsigned
1223 [100, +, 255] with values 100, 355, ...; the sign-extension is
1224 performed by default when CT is signed. */
1226 if (TYPE_PRECISION (type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1227 new_step
= chrec_convert_1 (signed_type_for (ct
), new_step
, at_stmt
,
1228 use_overflow_semantics
);
1229 new_step
= chrec_convert_1 (type
, new_step
, at_stmt
, use_overflow_semantics
);
1231 if (automatically_generated_chrec_p (new_base
)
1232 || automatically_generated_chrec_p (new_step
))
1235 if (must_check_rslt_overflow
1236 /* Note that in this case we cannot use the fact that signed variables
1237 do not overflow, as this is what we are verifying for the new iv. */
1238 && scev_probably_wraps_p (new_base
, new_step
, at_stmt
, loop
, false))
1247 /* Convert CHREC to TYPE. When the analyzer knows the context in
1248 which the CHREC is built, it sets AT_STMT to the statement that
1249 contains the definition of the analyzed variable, otherwise the
1250 conversion is less accurate: the information is used for
1251 determining a more accurate estimation of the number of iterations.
1252 By default AT_STMT could be safely set to NULL_TREE.
1254 The following rule is always true: TREE_TYPE (chrec) ==
1255 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1256 An example of what could happen when adding two chrecs and the type
1257 of the CHREC_RIGHT is different than CHREC_LEFT is:
1259 {(uint) 0, +, (uchar) 10} +
1260 {(uint) 0, +, (uchar) 250}
1262 that would produce a wrong result if CHREC_RIGHT is not (uint):
1264 {(uint) 0, +, (uchar) 4}
1268 {(uint) 0, +, (uint) 260}
1272 chrec_convert (tree type
, tree chrec
, tree at_stmt
)
1274 return chrec_convert_1 (type
, chrec
, at_stmt
, true);
1277 /* Convert CHREC to TYPE. When the analyzer knows the context in
1278 which the CHREC is built, it sets AT_STMT to the statement that
1279 contains the definition of the analyzed variable, otherwise the
1280 conversion is less accurate: the information is used for
1281 determining a more accurate estimation of the number of iterations.
1282 By default AT_STMT could be safely set to NULL_TREE.
1284 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1285 the rules for overflow of the given language apply (e.g., that signed
1286 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1287 tests, but also to enforce that the result follows them. */
1290 chrec_convert_1 (tree type
, tree chrec
, tree at_stmt
,
1291 bool use_overflow_semantics
)
1297 if (automatically_generated_chrec_p (chrec
))
1300 ct
= chrec_type (chrec
);
1304 if (!evolution_function_is_affine_p (chrec
))
1307 loop
= get_chrec_loop (chrec
);
1308 base
= CHREC_LEFT (chrec
);
1309 step
= CHREC_RIGHT (chrec
);
1311 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1312 use_overflow_semantics
))
1313 return build_polynomial_chrec (loop
->num
, base
, step
);
1315 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1317 res
= fold_convert (type
, chrec
);
1319 /* Don't propagate overflows. */
1320 if (CONSTANT_CLASS_P (res
))
1321 TREE_OVERFLOW (res
) = 0;
1323 /* But reject constants that don't fit in their type after conversion.
1324 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1325 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1326 and can cause problems later when computing niters of loops. Note
1327 that we don't do the check before converting because we don't want
1328 to reject conversions of negative chrecs to unsigned types. */
1329 if (TREE_CODE (res
) == INTEGER_CST
1330 && TREE_CODE (type
) == INTEGER_TYPE
1331 && !int_fits_type_p (res
, type
))
1332 res
= chrec_dont_know
;
1337 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1338 chrec if something else than what chrec_convert would do happens, NULL_TREE
1342 chrec_convert_aggressive (tree type
, tree chrec
)
1344 tree inner_type
, left
, right
, lc
, rc
;
1346 if (automatically_generated_chrec_p (chrec
)
1347 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1350 inner_type
= TREE_TYPE (chrec
);
1351 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1354 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1355 if (avoid_arithmetics_in_type_p (type
))
1358 left
= CHREC_LEFT (chrec
);
1359 right
= CHREC_RIGHT (chrec
);
1360 lc
= chrec_convert_aggressive (type
, left
);
1362 lc
= chrec_convert (type
, left
, NULL_TREE
);
1363 rc
= chrec_convert_aggressive (type
, right
);
1365 rc
= chrec_convert (type
, right
, NULL_TREE
);
1367 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1370 /* Returns true when CHREC0 == CHREC1. */
1373 eq_evolutions_p (tree chrec0
,
1376 if (chrec0
== NULL_TREE
1377 || chrec1
== NULL_TREE
1378 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1381 if (chrec0
== chrec1
)
1384 switch (TREE_CODE (chrec0
))
1387 return operand_equal_p (chrec0
, chrec1
, 0);
1389 case POLYNOMIAL_CHREC
:
1390 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1391 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1392 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1398 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1399 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1400 which of these cases happens. */
1403 scev_direction (tree chrec
)
1407 if (!evolution_function_is_affine_p (chrec
))
1408 return EV_DIR_UNKNOWN
;
1410 step
= CHREC_RIGHT (chrec
);
1411 if (TREE_CODE (step
) != INTEGER_CST
)
1412 return EV_DIR_UNKNOWN
;
1414 if (tree_int_cst_sign_bit (step
))
1415 return EV_DIR_DECREASES
;
1417 return EV_DIR_GROWS
;