1 /* Chains of recurrences.
2 Copyright (C) 2003-2024 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This file implements operations on chains of recurrences. Chains
22 of recurrences are used for modeling evolution functions of scalar
28 #include "coretypes.h"
31 #include "gimple-expr.h"
32 #include "tree-pretty-print.h"
33 #include "fold-const.h"
35 #include "tree-ssa-loop-ivopts.h"
36 #include "tree-ssa-loop-niter.h"
37 #include "tree-chrec.h"
39 #include "tree-ssa-loop.h"
41 #include "value-range.h"
42 #include "value-query.h"
43 #include "tree-scalar-evolution.h"
45 /* Extended folder for chrecs. */
47 /* Fold the addition of two polynomial functions. */
50 chrec_fold_plus_poly_poly (enum tree_code code
,
56 class loop
*loop0
= get_chrec_loop (poly0
);
57 class loop
*loop1
= get_chrec_loop (poly1
);
58 tree rtype
= code
== POINTER_PLUS_EXPR
? chrec_type (poly1
) : type
;
62 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
63 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
64 if (POINTER_TYPE_P (chrec_type (poly0
)))
65 gcc_checking_assert (ptrofftype_p (chrec_type (poly1
))
66 && useless_type_conversion_p (type
, chrec_type (poly0
)));
68 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
69 && useless_type_conversion_p (type
, chrec_type (poly1
)));
72 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
73 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
74 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
75 if (flow_loop_nested_p (loop0
, loop1
))
77 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
78 return build_polynomial_chrec
79 (CHREC_VARIABLE (poly1
),
80 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
83 return build_polynomial_chrec
84 (CHREC_VARIABLE (poly1
),
85 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
86 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
87 SCALAR_FLOAT_TYPE_P (type
)
88 ? build_real (type
, dconstm1
)
89 : build_int_cst_type (type
, -1)));
92 if (flow_loop_nested_p (loop1
, loop0
))
94 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
95 return build_polynomial_chrec
96 (CHREC_VARIABLE (poly0
),
97 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
100 return build_polynomial_chrec
101 (CHREC_VARIABLE (poly0
),
102 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
103 CHREC_RIGHT (poly0
));
106 /* This function should never be called for chrecs of loops that
107 do not belong to the same loop nest. */
110 /* It still can happen if we are not in loop-closed SSA form. */
111 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
112 return chrec_dont_know
;
115 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
117 left
= chrec_fold_plus
118 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
119 right
= chrec_fold_plus
120 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
124 left
= chrec_fold_minus
125 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
126 right
= chrec_fold_minus
127 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
130 if (chrec_zerop (right
))
133 return build_polynomial_chrec
134 (CHREC_VARIABLE (poly0
), left
, right
);
139 /* Fold the multiplication of two polynomial functions. */
142 chrec_fold_multiply_poly_poly (tree type
,
148 class loop
*loop0
= get_chrec_loop (poly0
);
149 class loop
*loop1
= get_chrec_loop (poly1
);
153 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
154 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
155 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
156 && useless_type_conversion_p (type
, chrec_type (poly1
)));
158 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
159 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
160 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
161 if (flow_loop_nested_p (loop0
, loop1
))
162 /* poly0 is a constant wrt. poly1. */
163 return build_polynomial_chrec
164 (CHREC_VARIABLE (poly1
),
165 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
166 CHREC_RIGHT (poly1
));
168 if (flow_loop_nested_p (loop1
, loop0
))
169 /* poly1 is a constant wrt. poly0. */
170 return build_polynomial_chrec
171 (CHREC_VARIABLE (poly0
),
172 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
173 CHREC_RIGHT (poly0
));
177 /* It still can happen if we are not in loop-closed SSA form. */
178 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
179 return chrec_dont_know
;
182 /* poly0 and poly1 are two polynomials in the same variable,
183 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
186 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
189 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
190 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
192 CHREC_LEFT (poly1
)));
194 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
195 /* "a*d + b*c + b*d". */
196 t1
= chrec_fold_plus (type
, t1
, t2
);
198 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
199 ? build_real (type
, dconst2
)
200 : build_int_cst (type
, 2), t2
);
202 var
= CHREC_VARIABLE (poly0
);
203 return build_polynomial_chrec (var
, t0
,
204 build_polynomial_chrec (var
, t1
, t2
));
207 /* When the operands are automatically_generated_chrec_p, the fold has
208 to respect the semantics of the operands. */
211 chrec_fold_automatically_generated_operands (tree op0
,
214 if (op0
== chrec_dont_know
215 || op1
== chrec_dont_know
)
216 return chrec_dont_know
;
218 if (op0
== chrec_known
219 || op1
== chrec_known
)
222 if (op0
== chrec_not_analyzed_yet
223 || op1
== chrec_not_analyzed_yet
)
224 return chrec_not_analyzed_yet
;
226 /* The default case produces a safe result. */
227 return chrec_dont_know
;
230 /* Fold the addition of two chrecs. */
233 chrec_fold_plus_1 (enum tree_code code
, tree type
,
236 if (automatically_generated_chrec_p (op0
)
237 || automatically_generated_chrec_p (op1
))
238 return chrec_fold_automatically_generated_operands (op0
, op1
);
240 switch (TREE_CODE (op0
))
242 case POLYNOMIAL_CHREC
:
244 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
245 switch (TREE_CODE (op1
))
247 case POLYNOMIAL_CHREC
:
249 (!chrec_contains_symbols_defined_in_loop (op1
,
250 CHREC_VARIABLE (op1
)));
251 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
255 /* We can strip sign-conversions to signed by performing the
256 operation in unsigned. */
257 tree optype
= TREE_TYPE (TREE_OPERAND (op1
, 0));
258 if (INTEGRAL_TYPE_P (type
)
259 && INTEGRAL_TYPE_P (optype
)
260 && tree_nop_conversion_p (type
, optype
)
261 && TYPE_UNSIGNED (optype
))
262 return chrec_convert (type
,
263 chrec_fold_plus_1 (code
, optype
,
264 chrec_convert (optype
,
266 TREE_OPERAND (op1
, 0)),
268 if (tree_contains_chrecs (op1
, NULL
))
269 return chrec_dont_know
;
274 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
275 return build_polynomial_chrec
276 (CHREC_VARIABLE (op0
),
277 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
280 return build_polynomial_chrec
281 (CHREC_VARIABLE (op0
),
282 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
288 /* We can strip sign-conversions to signed by performing the
289 operation in unsigned. */
290 tree optype
= TREE_TYPE (TREE_OPERAND (op0
, 0));
291 if (INTEGRAL_TYPE_P (type
)
292 && INTEGRAL_TYPE_P (optype
)
293 && tree_nop_conversion_p (type
, optype
)
294 && TYPE_UNSIGNED (optype
))
295 return chrec_convert (type
,
296 chrec_fold_plus_1 (code
, optype
,
297 TREE_OPERAND (op0
, 0),
298 chrec_convert (optype
,
301 if (tree_contains_chrecs (op0
, NULL
))
302 return chrec_dont_know
;
307 switch (TREE_CODE (op1
))
309 case POLYNOMIAL_CHREC
:
311 (!chrec_contains_symbols_defined_in_loop (op1
,
312 CHREC_VARIABLE (op1
)));
313 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
314 return build_polynomial_chrec
315 (CHREC_VARIABLE (op1
),
316 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
319 return build_polynomial_chrec
320 (CHREC_VARIABLE (op1
),
321 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
322 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
323 SCALAR_FLOAT_TYPE_P (type
)
324 ? build_real (type
, dconstm1
)
325 : build_int_cst_type (type
, -1)));
328 if (tree_contains_chrecs (op1
, NULL
))
329 return chrec_dont_know
;
335 if ((tree_contains_chrecs (op0
, &size
)
336 || tree_contains_chrecs (op1
, &size
))
337 && size
< param_scev_max_expr_size
)
338 return build2 (code
, type
, op0
, op1
);
339 else if (size
< param_scev_max_expr_size
)
341 if (code
== POINTER_PLUS_EXPR
)
342 return fold_build_pointer_plus (fold_convert (type
, op0
),
345 return fold_build2 (code
, type
,
346 fold_convert (type
, op0
),
347 fold_convert (type
, op1
));
350 return chrec_dont_know
;
356 /* Fold the addition of two chrecs. */
359 chrec_fold_plus (tree type
,
364 if (automatically_generated_chrec_p (op0
)
365 || automatically_generated_chrec_p (op1
))
366 return chrec_fold_automatically_generated_operands (op0
, op1
);
368 if (integer_zerop (op0
))
369 return chrec_convert (type
, op1
, NULL
);
370 if (integer_zerop (op1
))
371 return chrec_convert (type
, op0
, NULL
);
373 if (POINTER_TYPE_P (type
))
374 code
= POINTER_PLUS_EXPR
;
378 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
381 /* Fold the subtraction of two chrecs. */
384 chrec_fold_minus (tree type
,
388 if (automatically_generated_chrec_p (op0
)
389 || automatically_generated_chrec_p (op1
))
390 return chrec_fold_automatically_generated_operands (op0
, op1
);
392 if (integer_zerop (op1
))
395 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
398 /* Fold the multiplication of two chrecs. */
401 chrec_fold_multiply (tree type
,
405 if (automatically_generated_chrec_p (op0
)
406 || automatically_generated_chrec_p (op1
))
407 return chrec_fold_automatically_generated_operands (op0
, op1
);
409 if (TREE_CODE (op0
) != POLYNOMIAL_CHREC
410 && TREE_CODE (op1
) == POLYNOMIAL_CHREC
)
411 std::swap (op0
, op1
);
413 switch (TREE_CODE (op0
))
415 case POLYNOMIAL_CHREC
:
417 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
418 switch (TREE_CODE (op1
))
420 case POLYNOMIAL_CHREC
:
422 (!chrec_contains_symbols_defined_in_loop (op1
,
423 CHREC_VARIABLE (op1
)));
424 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
427 if (tree_contains_chrecs (op1
, NULL
))
428 return chrec_dont_know
;
432 if (integer_onep (op1
))
434 if (integer_zerop (op1
))
435 return build_int_cst (type
, 0);
437 /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
438 same sign or CHREC_LEFT is zero then folding the multiply into
439 the addition does not have the same behavior on overflow. Use
440 unsigned arithmetic in that case. */
442 if (!ANY_INTEGRAL_TYPE_P (type
)
443 || TYPE_OVERFLOW_WRAPS (type
)
444 || integer_zerop (CHREC_LEFT (op0
))
445 || (TREE_CODE (CHREC_LEFT (op0
)) == INTEGER_CST
446 && TREE_CODE (CHREC_RIGHT (op0
)) == INTEGER_CST
447 && (tree_int_cst_sgn (CHREC_LEFT (op0
))
448 == tree_int_cst_sgn (CHREC_RIGHT (op0
))))
449 || (get_range_query (cfun
)->range_of_expr (rl
, CHREC_LEFT (op0
))
450 && !rl
.undefined_p ()
451 && (rl
.nonpositive_p () || rl
.nonnegative_p ())
452 && get_range_query (cfun
)->range_of_expr (rr
,
454 && !rr
.undefined_p ()
455 && ((rl
.nonpositive_p () && rr
.nonpositive_p ())
456 || (rl
.nonnegative_p () && rr
.nonnegative_p ()))))
458 tree left
= chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
);
459 tree right
= chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
);
460 return build_polynomial_chrec (CHREC_VARIABLE (op0
), left
, right
);
464 tree utype
= unsigned_type_for (type
);
465 tree uop1
= chrec_convert_rhs (utype
, op1
);
466 tree uleft0
= chrec_convert_rhs (utype
, CHREC_LEFT (op0
));
467 tree uright0
= chrec_convert_rhs (utype
, CHREC_RIGHT (op0
));
468 tree left
= chrec_fold_multiply (utype
, uleft0
, uop1
);
469 tree right
= chrec_fold_multiply (utype
, uright0
, uop1
);
470 tree tem
= build_polynomial_chrec (CHREC_VARIABLE (op0
),
472 return chrec_convert_rhs (type
, tem
);
477 if (tree_contains_chrecs (op0
, NULL
))
478 return chrec_dont_know
;
482 if (integer_onep (op0
))
485 if (integer_zerop (op0
))
486 return build_int_cst (type
, 0);
488 switch (TREE_CODE (op1
))
490 case POLYNOMIAL_CHREC
:
494 if (tree_contains_chrecs (op1
, NULL
))
495 return chrec_dont_know
;
499 if (integer_onep (op1
))
501 if (integer_zerop (op1
))
502 return build_int_cst (type
, 0);
503 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
512 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
513 calculation overflows, otherwise return C(n,k) with type TYPE. */
516 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
518 wi::overflow_type overflow
;
521 /* Handle the most frequent cases. */
523 return build_int_cst (type
, 1);
525 return fold_convert (type
, n
);
527 widest_int num
= wi::to_widest (n
);
529 /* Check that k <= n. */
530 if (wi::ltu_p (num
, k
))
533 /* Denominator = 2. */
534 widest_int denom
= 2;
536 /* Index = Numerator-1. */
537 widest_int idx
= num
- 1;
539 /* Numerator = Numerator*Index = n*(n-1). */
540 num
= wi::smul (num
, idx
, &overflow
);
544 for (i
= 3; i
<= k
; i
++)
549 /* Numerator *= Index. */
550 num
= wi::smul (num
, idx
, &overflow
);
554 /* Denominator *= i. */
558 /* Result = Numerator / Denominator. */
559 num
= wi::udiv_trunc (num
, denom
);
560 if (! wi::fits_to_tree_p (num
, type
))
562 return wide_int_to_tree (type
, num
);
565 /* Helper function. Use the Newton's interpolating formula for
566 evaluating the value of the evolution function.
567 The result may be in an unsigned type of CHREC. */
570 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
572 tree arg0
, arg1
, binomial_n_k
;
573 tree type
= TREE_TYPE (chrec
);
574 class loop
*var_loop
= get_loop (cfun
, var
);
576 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
577 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
578 chrec
= CHREC_LEFT (chrec
);
580 /* The formula associates the expression and thus we have to make
581 sure to not introduce undefined overflow. */
583 if (INTEGRAL_TYPE_P (type
)
584 && ! TYPE_OVERFLOW_WRAPS (type
))
585 ctype
= unsigned_type_for (type
);
587 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
588 && CHREC_VARIABLE (chrec
) == var
)
590 arg1
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
591 if (arg1
== chrec_dont_know
)
592 return chrec_dont_know
;
593 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
595 return chrec_dont_know
;
596 tree l
= chrec_convert (ctype
, CHREC_LEFT (chrec
), NULL
);
597 arg0
= fold_build2 (MULT_EXPR
, ctype
, l
, binomial_n_k
);
598 return chrec_fold_plus (ctype
, arg0
, arg1
);
601 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
603 return chrec_dont_know
;
605 return fold_build2 (MULT_EXPR
, ctype
,
606 chrec_convert (ctype
, chrec
, NULL
), binomial_n_k
);
609 /* Evaluates "CHREC (X)" when the varying variable is VAR.
610 Example: Given the following parameters,
616 The result is given by the Newton's interpolating formula:
617 3 * \binom{10}{0} + 4 * \binom{10}{1}.
621 chrec_apply (unsigned var
,
625 tree type
= chrec_type (chrec
);
626 tree res
= chrec_dont_know
;
628 if (automatically_generated_chrec_p (chrec
)
629 || automatically_generated_chrec_p (x
)
631 /* When the symbols are defined in an outer loop, it is possible
632 to symbolically compute the apply, since the symbols are
633 constants with respect to the varying loop. */
634 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
635 return chrec_dont_know
;
637 if (dump_file
&& (dump_flags
& TDF_SCEV
))
638 fprintf (dump_file
, "(chrec_apply \n");
640 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
641 x
= build_real_from_int_cst (type
, x
);
643 switch (TREE_CODE (chrec
))
645 case POLYNOMIAL_CHREC
:
646 if (evolution_function_is_affine_p (chrec
))
648 tree chrecr
= CHREC_RIGHT (chrec
);
649 tree chrecl
= CHREC_LEFT (chrec
);
650 if (CHREC_VARIABLE (chrec
) != var
)
651 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
652 chrec_apply (var
, chrecl
, x
),
653 chrec_apply (var
, chrecr
, x
));
655 /* "{a, +, a}" (x-1) -> "a*x". */
656 else if (operand_equal_p (chrecl
, chrecr
)
657 && TREE_CODE (x
) == PLUS_EXPR
658 && integer_all_onesp (TREE_OPERAND (x
, 1))
659 && !POINTER_TYPE_P (type
)
660 && TYPE_PRECISION (TREE_TYPE (x
))
661 >= TYPE_PRECISION (type
))
663 /* We know the number of iterations can't be negative. */
664 res
= build_int_cst (TREE_TYPE (x
), 1);
665 res
= chrec_fold_plus (TREE_TYPE (x
), x
, res
);
666 res
= chrec_convert_rhs (type
, res
, NULL
);
667 res
= chrec_fold_multiply (type
, chrecr
, res
);
669 /* "{a, +, b} (x)" -> "a + b*x". */
672 /* The overall increment might not fit in a signed type so
673 use an unsigned computation to get at the final value
674 and avoid undefined signed overflow. */
675 tree utype
= TREE_TYPE (chrecr
);
676 if (INTEGRAL_TYPE_P (utype
) && !TYPE_OVERFLOW_WRAPS (utype
))
677 utype
= unsigned_type_for (TREE_TYPE (chrecr
));
678 res
= chrec_convert_rhs (utype
, x
, NULL
);
679 res
= chrec_fold_multiply (utype
,
680 chrec_convert (utype
, chrecr
, NULL
),
682 /* When the resulting increment fits the original type
683 do the increment in it. */
684 if (TREE_CODE (res
) == INTEGER_CST
685 && int_fits_type_p (res
, TREE_TYPE (chrecr
)))
687 res
= chrec_convert (TREE_TYPE (chrecr
), res
, NULL
);
688 res
= chrec_fold_plus (type
, chrecl
, res
);
692 res
= chrec_fold_plus (utype
,
693 chrec_convert (utype
, chrecl
, NULL
),
695 res
= chrec_convert (type
, res
, NULL
);
699 else if (TREE_CODE (x
) == INTEGER_CST
700 && tree_int_cst_sgn (x
) == 1)
701 /* testsuite/.../ssa-chrec-38.c. */
702 res
= chrec_convert (type
, chrec_evaluate (var
, chrec
, x
, 0), NULL
);
704 res
= chrec_dont_know
;
708 res
= chrec_convert (TREE_TYPE (chrec
),
709 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
718 if (dump_file
&& (dump_flags
& TDF_SCEV
))
720 fprintf (dump_file
, " (varying_loop = %d", var
);
721 fprintf (dump_file
, ")\n (chrec = ");
722 print_generic_expr (dump_file
, chrec
);
723 fprintf (dump_file
, ")\n (x = ");
724 print_generic_expr (dump_file
, x
);
725 fprintf (dump_file
, ")\n (res = ");
726 print_generic_expr (dump_file
, res
);
727 fprintf (dump_file
, "))\n");
733 /* For a given CHREC and an induction variable map IV_MAP that maps
734 (loop->num, expr) for every loop number of the current_loops an
735 expression, calls chrec_apply when the expression is not NULL. */
738 chrec_apply_map (tree chrec
, vec
<tree
> iv_map
)
743 FOR_EACH_VEC_ELT (iv_map
, i
, expr
)
745 chrec
= chrec_apply (i
, chrec
, expr
);
750 /* Replaces the initial condition in CHREC with INIT_COND. */
753 chrec_replace_initial_condition (tree chrec
,
756 if (automatically_generated_chrec_p (chrec
))
759 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
761 switch (TREE_CODE (chrec
))
763 case POLYNOMIAL_CHREC
:
764 return build_polynomial_chrec
765 (CHREC_VARIABLE (chrec
),
766 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
767 CHREC_RIGHT (chrec
));
774 /* Returns the initial condition of a given CHREC. */
777 initial_condition (tree chrec
)
779 if (automatically_generated_chrec_p (chrec
))
782 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
783 return initial_condition (CHREC_LEFT (chrec
));
788 /* Returns a univariate function that represents the evolution in
789 LOOP_NUM. Mask the evolution of any other loop. */
792 hide_evolution_in_other_loops_than_loop (tree chrec
,
795 class loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
796 if (automatically_generated_chrec_p (chrec
))
799 switch (TREE_CODE (chrec
))
801 case POLYNOMIAL_CHREC
:
802 chloop
= get_chrec_loop (chrec
);
805 return build_polynomial_chrec
807 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
809 CHREC_RIGHT (chrec
));
811 else if (flow_loop_nested_p (chloop
, loop
))
812 /* There is no evolution in this loop. */
813 return initial_condition (chrec
);
815 else if (flow_loop_nested_p (loop
, chloop
))
816 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
820 return chrec_dont_know
;
827 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
828 true, otherwise returns the initial condition in LOOP_NUM. */
831 chrec_component_in_loop_num (tree chrec
,
836 class loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
838 if (automatically_generated_chrec_p (chrec
))
841 switch (TREE_CODE (chrec
))
843 case POLYNOMIAL_CHREC
:
844 chloop
= get_chrec_loop (chrec
);
849 component
= CHREC_RIGHT (chrec
);
851 component
= CHREC_LEFT (chrec
);
853 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
854 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
858 return build_polynomial_chrec
860 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
866 else if (flow_loop_nested_p (chloop
, loop
))
867 /* There is no evolution part in this loop. */
872 gcc_assert (flow_loop_nested_p (loop
, chloop
));
873 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
886 /* Returns the evolution part in LOOP_NUM. Example: the call
887 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
891 evolution_part_in_loop_num (tree chrec
,
894 return chrec_component_in_loop_num (chrec
, loop_num
, true);
897 /* Returns the initial condition in LOOP_NUM. Example: the call
898 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
902 initial_condition_in_loop_num (tree chrec
,
905 return chrec_component_in_loop_num (chrec
, loop_num
, false);
908 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
909 This function is essentially used for setting the evolution to
910 chrec_dont_know, for example after having determined that it is
911 impossible to say how many times a loop will execute. */
914 reset_evolution_in_loop (unsigned loop_num
,
918 class loop
*loop
= get_loop (cfun
, loop_num
);
920 if (POINTER_TYPE_P (chrec_type (chrec
)))
921 gcc_assert (ptrofftype_p (chrec_type (new_evol
)));
923 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
925 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
926 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
928 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
930 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
932 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), left
, right
);
935 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
936 && CHREC_VARIABLE (chrec
) == loop_num
)
937 chrec
= CHREC_LEFT (chrec
);
939 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
942 /* Merges two evolution functions that were found by following two
943 alternate paths of a conditional expression. */
946 chrec_merge (tree chrec1
,
949 if (chrec1
== chrec_dont_know
950 || chrec2
== chrec_dont_know
)
951 return chrec_dont_know
;
953 if (chrec1
== chrec_known
954 || chrec2
== chrec_known
)
957 if (chrec1
== chrec_not_analyzed_yet
)
959 if (chrec2
== chrec_not_analyzed_yet
)
962 if (eq_evolutions_p (chrec1
, chrec2
))
965 return chrec_dont_know
;
972 /* Helper function for is_multivariate_chrec. */
975 is_multivariate_chrec_rec (const_tree chrec
, unsigned int rec_var
)
977 if (chrec
== NULL_TREE
)
980 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
982 if (CHREC_VARIABLE (chrec
) != rec_var
)
985 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
986 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
992 /* Determine whether the given chrec is multivariate or not. */
995 is_multivariate_chrec (const_tree chrec
)
997 if (chrec
== NULL_TREE
)
1000 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1001 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
1002 CHREC_VARIABLE (chrec
))
1003 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
1004 CHREC_VARIABLE (chrec
)));
1009 /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
1010 NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
1013 chrec_contains_symbols (const_tree chrec
, hash_set
<const_tree
> &visited
,
1018 if (chrec
== NULL_TREE
)
1021 if (TREE_CODE (chrec
) == SSA_NAME
1023 || TREE_CODE (chrec
) == POLY_INT_CST
1024 || TREE_CODE (chrec
) == PARM_DECL
1025 || TREE_CODE (chrec
) == FUNCTION_DECL
1026 || TREE_CODE (chrec
) == LABEL_DECL
1027 || TREE_CODE (chrec
) == RESULT_DECL
1028 || TREE_CODE (chrec
) == FIELD_DECL
)
1032 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1033 && flow_loop_nested_p (get_chrec_loop (chrec
), loop
))
1036 if (visited
.add (chrec
))
1039 n
= TREE_OPERAND_LENGTH (chrec
);
1040 for (i
= 0; i
< n
; i
++)
1041 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
), visited
, loop
))
1046 /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
1047 CHREC contains any chrec which is invariant wrto the loop (nest), in other
1048 words, chrec defined by outer loops of loop, so from LOOP's point of view,
1049 the chrec is considered as a SYMBOL. */
1052 chrec_contains_symbols (const_tree chrec
, class loop
* loop
)
1054 hash_set
<const_tree
> visited
;
1055 return chrec_contains_symbols (chrec
, visited
, loop
);
1058 /* Return true when CHREC contains symbolic names defined in
1062 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
,
1063 hash_set
<const_tree
> &visited
)
1067 if (chrec
== NULL_TREE
)
1070 if (is_gimple_min_invariant (chrec
))
1073 if (TREE_CODE (chrec
) == SSA_NAME
)
1076 loop_p def_loop
, loop
;
1078 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
1081 def
= SSA_NAME_DEF_STMT (chrec
);
1082 def_loop
= loop_containing_stmt (def
);
1083 loop
= get_loop (cfun
, loop_nb
);
1085 if (def_loop
== NULL
)
1088 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
1094 if (visited
.add (chrec
))
1097 n
= TREE_OPERAND_LENGTH (chrec
);
1098 for (i
= 0; i
< n
; i
++)
1099 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
1105 /* Return true when CHREC contains symbolic names defined in
1109 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
1111 hash_set
<const_tree
> visited
;
1112 return chrec_contains_symbols_defined_in_loop (chrec
, loop_nb
, visited
);
1115 /* Determines whether the chrec contains undetermined coefficients. */
1118 chrec_contains_undetermined (const_tree chrec
, hash_set
<const_tree
> &visited
)
1122 if (chrec
== chrec_dont_know
)
1125 if (chrec
== NULL_TREE
)
1128 if (visited
.add (chrec
))
1131 n
= TREE_OPERAND_LENGTH (chrec
);
1132 for (i
= 0; i
< n
; i
++)
1133 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
), visited
))
1139 chrec_contains_undetermined (const_tree chrec
)
1141 hash_set
<const_tree
> visited
;
1142 return chrec_contains_undetermined (chrec
, visited
);
1145 /* Determines whether the tree EXPR contains chrecs, and increment
1146 SIZE if it is not a NULL pointer by an estimation of the depth of
1150 tree_contains_chrecs (const_tree expr
, int *size
, hash_set
<const_tree
> &visited
)
1154 if (expr
== NULL_TREE
)
1160 if (tree_is_chrec (expr
))
1163 if (visited
.add (expr
))
1166 n
= TREE_OPERAND_LENGTH (expr
);
1167 for (i
= 0; i
< n
; i
++)
1168 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
, visited
))
1174 tree_contains_chrecs (const_tree expr
, int *size
)
1176 hash_set
<const_tree
> visited
;
1177 return tree_contains_chrecs (expr
, size
, visited
);
1181 /* Recursive helper function. */
1184 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1186 if (evolution_function_is_constant_p (chrec
))
1189 if (TREE_CODE (chrec
) == SSA_NAME
1191 || expr_invariant_in_loop_p (get_loop (cfun
, loopnum
), chrec
)))
1194 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1196 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
1197 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1198 get_chrec_loop (chrec
))
1199 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
1201 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
1207 switch (TREE_OPERAND_LENGTH (chrec
))
1210 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
1216 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1226 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1229 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1231 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1234 /* Determine whether the given tree is an affine multivariate
1238 evolution_function_is_affine_multivariate_p (const_tree chrec
, int loopnum
)
1240 if (chrec
== NULL_TREE
)
1243 switch (TREE_CODE (chrec
))
1245 case POLYNOMIAL_CHREC
:
1246 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
), loopnum
))
1248 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
))
1252 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1253 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1254 != CHREC_VARIABLE (chrec
)
1255 && evolution_function_is_affine_multivariate_p
1256 (CHREC_RIGHT (chrec
), loopnum
))
1264 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
)
1265 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1266 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1267 && evolution_function_is_affine_multivariate_p
1268 (CHREC_LEFT (chrec
), loopnum
))
1279 /* Determine whether the given tree is a function in zero or one
1280 variables with respect to loop specified by LOOPNUM. Note only positive
1281 LOOPNUM stands for a real loop. */
1284 evolution_function_is_univariate_p (const_tree chrec
, int loopnum
)
1286 if (chrec
== NULL_TREE
)
1290 switch (TREE_CODE (chrec
))
1292 case POLYNOMIAL_CHREC
:
1293 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1295 case POLYNOMIAL_CHREC
:
1296 sub_chrec
= CHREC_LEFT (chrec
);
1297 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (sub_chrec
)
1299 || CHREC_VARIABLE (sub_chrec
) == (unsigned) loopnum
1300 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1301 get_chrec_loop (sub_chrec
))))
1303 if (!evolution_function_is_univariate_p (sub_chrec
, loopnum
))
1308 if (tree_contains_chrecs (CHREC_LEFT (chrec
), NULL
))
1313 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1315 case POLYNOMIAL_CHREC
:
1316 sub_chrec
= CHREC_RIGHT (chrec
);
1317 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (sub_chrec
)
1319 || CHREC_VARIABLE (sub_chrec
) == (unsigned) loopnum
1320 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1321 get_chrec_loop (sub_chrec
))))
1323 if (!evolution_function_is_univariate_p (sub_chrec
, loopnum
))
1328 if (tree_contains_chrecs (CHREC_RIGHT (chrec
), NULL
))
1339 /* Returns the number of variables of CHREC. Example: the call
1340 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1343 nb_vars_in_chrec (tree chrec
)
1345 if (chrec
== NULL_TREE
)
1348 switch (TREE_CODE (chrec
))
1350 case POLYNOMIAL_CHREC
:
1351 return 1 + nb_vars_in_chrec
1352 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1359 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1360 the scev corresponds to. AT_STMT is the statement at that the scev is
1361 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1362 that the rules for overflow of the given language apply (e.g., that signed
1363 arithmetics in C does not overflow) -- i.e., to use them to avoid
1364 unnecessary tests, but also to enforce that the result follows them.
1365 FROM is the source variable converted if it's not NULL. Returns true if
1366 the conversion succeeded, false otherwise. */
1369 convert_affine_scev (class loop
*loop
, tree type
,
1370 tree
*base
, tree
*step
, gimple
*at_stmt
,
1371 bool use_overflow_semantics
, tree from
)
1373 tree ct
= TREE_TYPE (*step
);
1374 bool enforce_overflow_semantics
;
1375 bool must_check_src_overflow
, must_check_rslt_overflow
;
1376 tree new_base
, new_step
;
1377 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1380 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1381 but we must check some assumptions.
1383 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1384 of CT is smaller than the precision of TYPE. For example, when we
1385 cast unsigned char [254, +, 1] to unsigned, the values on left side
1386 are 254, 255, 0, 1, ..., but those on the right side are
1387 254, 255, 256, 257, ...
1388 2) In case that we must also preserve the fact that signed ivs do not
1389 overflow, we must additionally check that the new iv does not wrap.
1390 For example, unsigned char [125, +, 1] casted to signed char could
1391 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1392 which would confuse optimizers that assume that this does not
1394 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1396 enforce_overflow_semantics
= (use_overflow_semantics
1397 && nowrap_type_p (type
));
1398 if (enforce_overflow_semantics
)
1400 /* We can avoid checking whether the result overflows in the following
1403 -- must_check_src_overflow is true, and the range of TYPE is superset
1404 of the range of CT -- i.e., in all cases except if CT signed and
1406 -- both CT and TYPE have the same precision and signedness, and we
1407 verify instead that the source does not overflow (this may be
1408 easier than verifying it for the result, as we may use the
1409 information about the semantics of overflow in CT). */
1410 if (must_check_src_overflow
)
1412 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1413 must_check_rslt_overflow
= true;
1415 must_check_rslt_overflow
= false;
1417 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1418 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1420 must_check_rslt_overflow
= false;
1421 must_check_src_overflow
= true;
1424 must_check_rslt_overflow
= true;
1427 must_check_rslt_overflow
= false;
1429 if (must_check_src_overflow
1430 && scev_probably_wraps_p (from
, *base
, *step
, at_stmt
, loop
,
1431 use_overflow_semantics
))
1434 new_base
= chrec_convert (type
, *base
, at_stmt
, use_overflow_semantics
);
1435 /* The step must be sign extended, regardless of the signedness
1436 of CT and TYPE. This only needs to be handled specially when
1437 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1438 (with values 100, 99, 98, ...) from becoming signed or unsigned
1439 [100, +, 255] with values 100, 355, ...; the sign-extension is
1440 performed by default when CT is signed. */
1442 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1444 tree signed_ct
= build_nonstandard_integer_type (TYPE_PRECISION (ct
), 0);
1445 new_step
= chrec_convert (signed_ct
, new_step
, at_stmt
,
1446 use_overflow_semantics
);
1448 new_step
= chrec_convert (step_type
, new_step
, at_stmt
,
1449 use_overflow_semantics
);
1451 if (automatically_generated_chrec_p (new_base
)
1452 || automatically_generated_chrec_p (new_step
))
1455 if (must_check_rslt_overflow
1456 /* Note that in this case we cannot use the fact that signed variables
1457 do not overflow, as this is what we are verifying for the new iv. */
1458 && scev_probably_wraps_p (NULL_TREE
, new_base
, new_step
,
1459 at_stmt
, loop
, false))
1468 /* Convert CHREC for the right hand side of a CHREC.
1469 The increment for a pointer type is always sizetype. */
1472 chrec_convert_rhs (tree type
, tree chrec
, gimple
*at_stmt
)
1474 if (POINTER_TYPE_P (type
))
1477 return chrec_convert (type
, chrec
, at_stmt
);
1480 /* Convert CHREC to TYPE. When the analyzer knows the context in
1481 which the CHREC is built, it sets AT_STMT to the statement that
1482 contains the definition of the analyzed variable, otherwise the
1483 conversion is less accurate: the information is used for
1484 determining a more accurate estimation of the number of iterations.
1485 By default AT_STMT could be safely set to NULL_TREE.
1487 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1488 the rules for overflow of the given language apply (e.g., that signed
1489 arithmetics in C does not overflow) -- i.e., to use them to avoid
1490 unnecessary tests, but also to enforce that the result follows them.
1492 FROM is the source variable converted if it's not NULL. */
1495 chrec_convert_1 (tree type
, tree chrec
, gimple
*at_stmt
,
1496 bool use_overflow_semantics
, tree from
)
1502 if (automatically_generated_chrec_p (chrec
))
1505 ct
= chrec_type (chrec
);
1506 if (useless_type_conversion_p (type
, ct
))
1509 if (!evolution_function_is_affine_p (chrec
))
1512 loop
= get_chrec_loop (chrec
);
1513 base
= CHREC_LEFT (chrec
);
1514 step
= CHREC_RIGHT (chrec
);
1516 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1517 use_overflow_semantics
, from
))
1518 return build_polynomial_chrec (loop
->num
, base
, step
);
1520 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1522 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1523 may be more expensive. We do want to perform this optimization here
1524 though for canonicalization reasons. */
1525 if (use_overflow_semantics
1526 && (TREE_CODE (chrec
) == PLUS_EXPR
1527 || TREE_CODE (chrec
) == MINUS_EXPR
)
1528 && TREE_CODE (type
) == INTEGER_TYPE
1529 && TREE_CODE (ct
) == INTEGER_TYPE
1530 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1531 && TYPE_OVERFLOW_UNDEFINED (ct
))
1532 res
= fold_build2 (TREE_CODE (chrec
), type
,
1533 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1534 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1535 /* Similar perform the trick that (signed char)((int)x + 2) can be
1536 narrowed to (signed char)((unsigned char)x + 2). */
1537 else if (use_overflow_semantics
1538 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1539 && TREE_CODE (ct
) == INTEGER_TYPE
1540 && TREE_CODE (type
) == INTEGER_TYPE
1541 && TYPE_OVERFLOW_UNDEFINED (type
)
1542 && TYPE_PRECISION (type
) < TYPE_PRECISION (ct
))
1544 tree utype
= unsigned_type_for (type
);
1545 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1546 fold_convert (utype
,
1547 CHREC_LEFT (chrec
)),
1548 fold_convert (utype
,
1549 CHREC_RIGHT (chrec
)));
1550 res
= chrec_convert_1 (type
, res
, at_stmt
, use_overflow_semantics
, from
);
1553 res
= fold_convert (type
, chrec
);
1555 /* Don't propagate overflows. */
1556 if (CONSTANT_CLASS_P (res
))
1557 TREE_OVERFLOW (res
) = 0;
1559 /* But reject constants that don't fit in their type after conversion.
1560 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1561 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1562 and can cause problems later when computing niters of loops. Note
1563 that we don't do the check before converting because we don't want
1564 to reject conversions of negative chrecs to unsigned types. */
1565 if (TREE_CODE (res
) == INTEGER_CST
1566 && TREE_CODE (type
) == INTEGER_TYPE
1567 && !int_fits_type_p (res
, type
))
1568 res
= chrec_dont_know
;
1573 /* Convert CHREC to TYPE. When the analyzer knows the context in
1574 which the CHREC is built, it sets AT_STMT to the statement that
1575 contains the definition of the analyzed variable, otherwise the
1576 conversion is less accurate: the information is used for
1577 determining a more accurate estimation of the number of iterations.
1578 By default AT_STMT could be safely set to NULL_TREE.
1580 The following rule is always true: TREE_TYPE (chrec) ==
1581 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1582 An example of what could happen when adding two chrecs and the type
1583 of the CHREC_RIGHT is different than CHREC_LEFT is:
1585 {(uint) 0, +, (uchar) 10} +
1586 {(uint) 0, +, (uchar) 250}
1588 that would produce a wrong result if CHREC_RIGHT is not (uint):
1590 {(uint) 0, +, (uchar) 4}
1594 {(uint) 0, +, (uint) 260}
1596 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1597 the rules for overflow of the given language apply (e.g., that signed
1598 arithmetics in C does not overflow) -- i.e., to use them to avoid
1599 unnecessary tests, but also to enforce that the result follows them.
1601 FROM is the source variable converted if it's not NULL. */
1604 chrec_convert (tree type
, tree chrec
, gimple
*at_stmt
,
1605 bool use_overflow_semantics
, tree from
)
1607 return chrec_convert_1 (type
, chrec
, at_stmt
, use_overflow_semantics
, from
);
1610 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1611 chrec if something else than what chrec_convert would do happens, NULL_TREE
1612 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1613 if the result chrec may overflow. */
1616 chrec_convert_aggressive (tree type
, tree chrec
, bool *fold_conversions
)
1618 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1620 gcc_assert (fold_conversions
!= NULL
);
1622 if (automatically_generated_chrec_p (chrec
)
1623 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1626 inner_type
= TREE_TYPE (chrec
);
1627 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1630 if (useless_type_conversion_p (type
, inner_type
))
1633 if (!*fold_conversions
&& evolution_function_is_affine_p (chrec
))
1638 loop
= get_chrec_loop (chrec
);
1639 base
= CHREC_LEFT (chrec
);
1640 step
= CHREC_RIGHT (chrec
);
1641 if (convert_affine_scev (loop
, type
, &base
, &step
, NULL
, true))
1642 return build_polynomial_chrec (loop
->num
, base
, step
);
1644 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1646 left
= CHREC_LEFT (chrec
);
1647 right
= CHREC_RIGHT (chrec
);
1648 lc
= chrec_convert_aggressive (type
, left
, fold_conversions
);
1650 lc
= chrec_convert (type
, left
, NULL
);
1651 rc
= chrec_convert_aggressive (rtype
, right
, fold_conversions
);
1653 rc
= chrec_convert (rtype
, right
, NULL
);
1655 *fold_conversions
= true;
1657 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1660 /* Returns true when CHREC0 == CHREC1. */
1663 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1665 if (chrec0
== NULL_TREE
1666 || chrec1
== NULL_TREE
1667 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1670 if (chrec0
== chrec1
)
1673 if (! types_compatible_p (TREE_TYPE (chrec0
), TREE_TYPE (chrec1
)))
1676 switch (TREE_CODE (chrec0
))
1678 case POLYNOMIAL_CHREC
:
1679 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1680 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1681 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1686 case POINTER_PLUS_EXPR
:
1687 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1688 TREE_OPERAND (chrec1
, 0))
1689 && eq_evolutions_p (TREE_OPERAND (chrec0
, 1),
1690 TREE_OPERAND (chrec1
, 1));
1693 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1694 TREE_OPERAND (chrec1
, 0));
1697 return operand_equal_p (chrec0
, chrec1
, 0);
1701 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1702 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1703 which of these cases happens. */
1706 scev_direction (const_tree chrec
)
1710 if (!evolution_function_is_affine_p (chrec
))
1711 return EV_DIR_UNKNOWN
;
1713 step
= CHREC_RIGHT (chrec
);
1714 if (TREE_CODE (step
) != INTEGER_CST
)
1715 return EV_DIR_UNKNOWN
;
1717 if (tree_int_cst_sign_bit (step
))
1718 return EV_DIR_DECREASES
;
1720 return EV_DIR_GROWS
;
1723 /* Iterates over all the components of SCEV, and calls CBCK. */
1726 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1728 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1731 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1735 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1739 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1748 /* Returns true when the operation can be part of a linear
1752 operator_is_linear (tree scev
)
1754 switch (TREE_CODE (scev
))
1757 case POLYNOMIAL_CHREC
:
1759 case POINTER_PLUS_EXPR
:
1764 case NON_LVALUE_EXPR
:
1774 /* Return true when SCEV is a linear expression. Linear expressions
1775 can contain additions, substractions and multiplications.
1776 Multiplications are restricted to constant scaling: "cst * x". */
1779 scev_is_linear_expression (tree scev
)
1781 if (evolution_function_is_constant_p (scev
))
1785 || !operator_is_linear (scev
))
1788 if (TREE_CODE (scev
) == MULT_EXPR
)
1789 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1790 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1792 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1793 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1796 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1799 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1800 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1801 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1804 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1805 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1808 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1818 /* Determines whether the expression CHREC contains only interger consts
1819 in the right parts. */
1822 evolution_function_right_is_integer_cst (const_tree chrec
)
1824 if (chrec
== NULL_TREE
)
1827 switch (TREE_CODE (chrec
))
1832 case POLYNOMIAL_CHREC
:
1833 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1834 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1835 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1838 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));