1 /* Chains of recurrences.
2 Copyright (C) 2003-2019 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"
42 #include "tree-scalar-evolution.h"
44 /* Extended folder for chrecs. */
46 /* Fold the addition of two polynomial functions. */
49 chrec_fold_plus_poly_poly (enum tree_code code
,
55 class loop
*loop0
= get_chrec_loop (poly0
);
56 class loop
*loop1
= get_chrec_loop (poly1
);
57 tree rtype
= code
== POINTER_PLUS_EXPR
? chrec_type (poly1
) : type
;
61 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
62 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
63 if (POINTER_TYPE_P (chrec_type (poly0
)))
64 gcc_checking_assert (ptrofftype_p (chrec_type (poly1
))
65 && useless_type_conversion_p (type
, chrec_type (poly0
)));
67 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
68 && useless_type_conversion_p (type
, chrec_type (poly1
)));
71 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
72 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
73 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
74 if (flow_loop_nested_p (loop0
, loop1
))
76 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
77 return build_polynomial_chrec
78 (CHREC_VARIABLE (poly1
),
79 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
82 return build_polynomial_chrec
83 (CHREC_VARIABLE (poly1
),
84 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
85 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
86 SCALAR_FLOAT_TYPE_P (type
)
87 ? build_real (type
, dconstm1
)
88 : build_int_cst_type (type
, -1)));
91 if (flow_loop_nested_p (loop1
, loop0
))
93 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
94 return build_polynomial_chrec
95 (CHREC_VARIABLE (poly0
),
96 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
99 return build_polynomial_chrec
100 (CHREC_VARIABLE (poly0
),
101 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
102 CHREC_RIGHT (poly0
));
105 /* This function should never be called for chrecs of loops that
106 do not belong to the same loop nest. */
109 /* It still can happen if we are not in loop-closed SSA form. */
110 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
111 return chrec_dont_know
;
114 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
116 left
= chrec_fold_plus
117 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
118 right
= chrec_fold_plus
119 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
123 left
= chrec_fold_minus
124 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
125 right
= chrec_fold_minus
126 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
129 if (chrec_zerop (right
))
132 return build_polynomial_chrec
133 (CHREC_VARIABLE (poly0
), left
, right
);
138 /* Fold the multiplication of two polynomial functions. */
141 chrec_fold_multiply_poly_poly (tree type
,
147 class loop
*loop0
= get_chrec_loop (poly0
);
148 class loop
*loop1
= get_chrec_loop (poly1
);
152 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
153 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
154 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
155 && useless_type_conversion_p (type
, chrec_type (poly1
)));
157 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
158 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
159 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
160 if (flow_loop_nested_p (loop0
, loop1
))
161 /* poly0 is a constant wrt. poly1. */
162 return build_polynomial_chrec
163 (CHREC_VARIABLE (poly1
),
164 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
165 CHREC_RIGHT (poly1
));
167 if (flow_loop_nested_p (loop1
, loop0
))
168 /* poly1 is a constant wrt. poly0. */
169 return build_polynomial_chrec
170 (CHREC_VARIABLE (poly0
),
171 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
172 CHREC_RIGHT (poly0
));
176 /* It still can happen if we are not in loop-closed SSA form. */
177 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
178 return chrec_dont_know
;
181 /* poly0 and poly1 are two polynomials in the same variable,
182 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
185 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
188 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
189 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
191 CHREC_LEFT (poly1
)));
193 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
194 /* "a*d + b*c + b*d". */
195 t1
= chrec_fold_plus (type
, t1
, t2
);
197 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
198 ? build_real (type
, dconst2
)
199 : build_int_cst (type
, 2), t2
);
201 var
= CHREC_VARIABLE (poly0
);
202 return build_polynomial_chrec (var
, t0
,
203 build_polynomial_chrec (var
, t1
, t2
));
206 /* When the operands are automatically_generated_chrec_p, the fold has
207 to respect the semantics of the operands. */
210 chrec_fold_automatically_generated_operands (tree op0
,
213 if (op0
== chrec_dont_know
214 || op1
== chrec_dont_know
)
215 return chrec_dont_know
;
217 if (op0
== chrec_known
218 || op1
== chrec_known
)
221 if (op0
== chrec_not_analyzed_yet
222 || op1
== chrec_not_analyzed_yet
)
223 return chrec_not_analyzed_yet
;
225 /* The default case produces a safe result. */
226 return chrec_dont_know
;
229 /* Fold the addition of two chrecs. */
232 chrec_fold_plus_1 (enum tree_code code
, tree type
,
235 if (automatically_generated_chrec_p (op0
)
236 || automatically_generated_chrec_p (op1
))
237 return chrec_fold_automatically_generated_operands (op0
, op1
);
239 switch (TREE_CODE (op0
))
241 case POLYNOMIAL_CHREC
:
243 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
244 switch (TREE_CODE (op1
))
246 case POLYNOMIAL_CHREC
:
248 (!chrec_contains_symbols_defined_in_loop (op1
,
249 CHREC_VARIABLE (op1
)));
250 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
254 /* We can strip sign-conversions to signed by performing the
255 operation in unsigned. */
256 tree optype
= TREE_TYPE (TREE_OPERAND (op1
, 0));
257 if (INTEGRAL_TYPE_P (type
)
258 && INTEGRAL_TYPE_P (optype
)
259 && tree_nop_conversion_p (type
, optype
)
260 && TYPE_UNSIGNED (optype
))
261 return chrec_convert (type
,
262 chrec_fold_plus_1 (code
, optype
,
263 chrec_convert (optype
,
265 TREE_OPERAND (op1
, 0)),
267 if (tree_contains_chrecs (op1
, NULL
))
268 return chrec_dont_know
;
273 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
274 return build_polynomial_chrec
275 (CHREC_VARIABLE (op0
),
276 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
279 return build_polynomial_chrec
280 (CHREC_VARIABLE (op0
),
281 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
287 /* We can strip sign-conversions to signed by performing the
288 operation in unsigned. */
289 tree optype
= TREE_TYPE (TREE_OPERAND (op0
, 0));
290 if (INTEGRAL_TYPE_P (type
)
291 && INTEGRAL_TYPE_P (optype
)
292 && tree_nop_conversion_p (type
, optype
)
293 && TYPE_UNSIGNED (optype
))
294 return chrec_convert (type
,
295 chrec_fold_plus_1 (code
, optype
,
296 TREE_OPERAND (op0
, 0),
297 chrec_convert (optype
,
300 if (tree_contains_chrecs (op0
, NULL
))
301 return chrec_dont_know
;
306 switch (TREE_CODE (op1
))
308 case POLYNOMIAL_CHREC
:
310 (!chrec_contains_symbols_defined_in_loop (op1
,
311 CHREC_VARIABLE (op1
)));
312 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
313 return build_polynomial_chrec
314 (CHREC_VARIABLE (op1
),
315 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
318 return build_polynomial_chrec
319 (CHREC_VARIABLE (op1
),
320 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
321 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
322 SCALAR_FLOAT_TYPE_P (type
)
323 ? build_real (type
, dconstm1
)
324 : build_int_cst_type (type
, -1)));
327 if (tree_contains_chrecs (op1
, NULL
))
328 return chrec_dont_know
;
334 if ((tree_contains_chrecs (op0
, &size
)
335 || tree_contains_chrecs (op1
, &size
))
336 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
337 return build2 (code
, type
, op0
, op1
);
338 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
340 if (code
== POINTER_PLUS_EXPR
)
341 return fold_build_pointer_plus (fold_convert (type
, op0
),
344 return fold_build2 (code
, type
,
345 fold_convert (type
, op0
),
346 fold_convert (type
, op1
));
349 return chrec_dont_know
;
355 /* Fold the addition of two chrecs. */
358 chrec_fold_plus (tree type
,
363 if (automatically_generated_chrec_p (op0
)
364 || automatically_generated_chrec_p (op1
))
365 return chrec_fold_automatically_generated_operands (op0
, op1
);
367 if (integer_zerop (op0
))
368 return chrec_convert (type
, op1
, NULL
);
369 if (integer_zerop (op1
))
370 return chrec_convert (type
, op0
, NULL
);
372 if (POINTER_TYPE_P (type
))
373 code
= POINTER_PLUS_EXPR
;
377 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
380 /* Fold the subtraction of two chrecs. */
383 chrec_fold_minus (tree type
,
387 if (automatically_generated_chrec_p (op0
)
388 || automatically_generated_chrec_p (op1
))
389 return chrec_fold_automatically_generated_operands (op0
, op1
);
391 if (integer_zerop (op1
))
394 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
397 /* Fold the multiplication of two chrecs. */
400 chrec_fold_multiply (tree type
,
404 if (automatically_generated_chrec_p (op0
)
405 || automatically_generated_chrec_p (op1
))
406 return chrec_fold_automatically_generated_operands (op0
, op1
);
408 switch (TREE_CODE (op0
))
410 case POLYNOMIAL_CHREC
:
412 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
413 switch (TREE_CODE (op1
))
415 case POLYNOMIAL_CHREC
:
417 (!chrec_contains_symbols_defined_in_loop (op1
,
418 CHREC_VARIABLE (op1
)));
419 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
422 if (tree_contains_chrecs (op1
, NULL
))
423 return chrec_dont_know
;
427 if (integer_onep (op1
))
429 if (integer_zerop (op1
))
430 return build_int_cst (type
, 0);
432 return build_polynomial_chrec
433 (CHREC_VARIABLE (op0
),
434 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
435 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
439 if (tree_contains_chrecs (op0
, NULL
))
440 return chrec_dont_know
;
444 if (integer_onep (op0
))
447 if (integer_zerop (op0
))
448 return build_int_cst (type
, 0);
450 switch (TREE_CODE (op1
))
452 case POLYNOMIAL_CHREC
:
454 (!chrec_contains_symbols_defined_in_loop (op1
,
455 CHREC_VARIABLE (op1
)));
456 return build_polynomial_chrec
457 (CHREC_VARIABLE (op1
),
458 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
459 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
462 if (tree_contains_chrecs (op1
, NULL
))
463 return chrec_dont_know
;
467 if (integer_onep (op1
))
469 if (integer_zerop (op1
))
470 return build_int_cst (type
, 0);
471 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
480 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
481 calculation overflows, otherwise return C(n,k) with type TYPE. */
484 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
486 wi::overflow_type overflow
;
489 /* Handle the most frequent cases. */
491 return build_int_cst (type
, 1);
493 return fold_convert (type
, n
);
495 widest_int num
= wi::to_widest (n
);
497 /* Check that k <= n. */
498 if (wi::ltu_p (num
, k
))
501 /* Denominator = 2. */
502 widest_int denom
= 2;
504 /* Index = Numerator-1. */
505 widest_int idx
= num
- 1;
507 /* Numerator = Numerator*Index = n*(n-1). */
508 num
= wi::smul (num
, idx
, &overflow
);
512 for (i
= 3; i
<= k
; i
++)
517 /* Numerator *= Index. */
518 num
= wi::smul (num
, idx
, &overflow
);
522 /* Denominator *= i. */
526 /* Result = Numerator / Denominator. */
527 num
= wi::udiv_trunc (num
, denom
);
528 if (! wi::fits_to_tree_p (num
, type
))
530 return wide_int_to_tree (type
, num
);
533 /* Helper function. Use the Newton's interpolating formula for
534 evaluating the value of the evolution function.
535 The result may be in an unsigned type of CHREC. */
538 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
540 tree arg0
, arg1
, binomial_n_k
;
541 tree type
= TREE_TYPE (chrec
);
542 class loop
*var_loop
= get_loop (cfun
, var
);
544 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
545 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
546 chrec
= CHREC_LEFT (chrec
);
548 /* The formula associates the expression and thus we have to make
549 sure to not introduce undefined overflow. */
551 if (INTEGRAL_TYPE_P (type
)
552 && ! TYPE_OVERFLOW_WRAPS (type
))
553 ctype
= unsigned_type_for (type
);
555 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
556 && CHREC_VARIABLE (chrec
) == var
)
558 arg1
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
559 if (arg1
== chrec_dont_know
)
560 return chrec_dont_know
;
561 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
563 return chrec_dont_know
;
564 tree l
= chrec_convert (ctype
, CHREC_LEFT (chrec
), NULL
);
565 arg0
= fold_build2 (MULT_EXPR
, ctype
, l
, binomial_n_k
);
566 return chrec_fold_plus (ctype
, arg0
, arg1
);
569 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
571 return chrec_dont_know
;
573 return fold_build2 (MULT_EXPR
, ctype
,
574 chrec_convert (ctype
, chrec
, NULL
), binomial_n_k
);
577 /* Evaluates "CHREC (X)" when the varying variable is VAR.
578 Example: Given the following parameters,
584 The result is given by the Newton's interpolating formula:
585 3 * \binom{10}{0} + 4 * \binom{10}{1}.
589 chrec_apply (unsigned var
,
593 tree type
= chrec_type (chrec
);
594 tree res
= chrec_dont_know
;
596 if (automatically_generated_chrec_p (chrec
)
597 || automatically_generated_chrec_p (x
)
599 /* When the symbols are defined in an outer loop, it is possible
600 to symbolically compute the apply, since the symbols are
601 constants with respect to the varying loop. */
602 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
603 return chrec_dont_know
;
605 if (dump_file
&& (dump_flags
& TDF_SCEV
))
606 fprintf (dump_file
, "(chrec_apply \n");
608 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
609 x
= build_real_from_int_cst (type
, x
);
611 switch (TREE_CODE (chrec
))
613 case POLYNOMIAL_CHREC
:
614 if (evolution_function_is_affine_p (chrec
))
616 if (CHREC_VARIABLE (chrec
) != var
)
617 return build_polynomial_chrec
618 (CHREC_VARIABLE (chrec
),
619 chrec_apply (var
, CHREC_LEFT (chrec
), x
),
620 chrec_apply (var
, CHREC_RIGHT (chrec
), x
));
622 /* "{a, +, b} (x)" -> "a + b*x". */
623 x
= chrec_convert_rhs (type
, x
, NULL
);
624 res
= chrec_fold_multiply (TREE_TYPE (x
), CHREC_RIGHT (chrec
), x
);
625 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
627 else if (TREE_CODE (x
) == INTEGER_CST
628 && tree_int_cst_sgn (x
) == 1)
629 /* testsuite/.../ssa-chrec-38.c. */
630 res
= chrec_convert (type
, chrec_evaluate (var
, chrec
, x
, 0), NULL
);
632 res
= chrec_dont_know
;
636 res
= chrec_convert (TREE_TYPE (chrec
),
637 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
646 if (dump_file
&& (dump_flags
& TDF_SCEV
))
648 fprintf (dump_file
, " (varying_loop = %d\n", var
);
649 fprintf (dump_file
, ")\n (chrec = ");
650 print_generic_expr (dump_file
, chrec
);
651 fprintf (dump_file
, ")\n (x = ");
652 print_generic_expr (dump_file
, x
);
653 fprintf (dump_file
, ")\n (res = ");
654 print_generic_expr (dump_file
, res
);
655 fprintf (dump_file
, "))\n");
661 /* For a given CHREC and an induction variable map IV_MAP that maps
662 (loop->num, expr) for every loop number of the current_loops an
663 expression, calls chrec_apply when the expression is not NULL. */
666 chrec_apply_map (tree chrec
, vec
<tree
> iv_map
)
671 FOR_EACH_VEC_ELT (iv_map
, i
, expr
)
673 chrec
= chrec_apply (i
, chrec
, expr
);
678 /* Replaces the initial condition in CHREC with INIT_COND. */
681 chrec_replace_initial_condition (tree chrec
,
684 if (automatically_generated_chrec_p (chrec
))
687 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
689 switch (TREE_CODE (chrec
))
691 case POLYNOMIAL_CHREC
:
692 return build_polynomial_chrec
693 (CHREC_VARIABLE (chrec
),
694 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
695 CHREC_RIGHT (chrec
));
702 /* Returns the initial condition of a given CHREC. */
705 initial_condition (tree chrec
)
707 if (automatically_generated_chrec_p (chrec
))
710 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
711 return initial_condition (CHREC_LEFT (chrec
));
716 /* Returns a univariate function that represents the evolution in
717 LOOP_NUM. Mask the evolution of any other loop. */
720 hide_evolution_in_other_loops_than_loop (tree chrec
,
723 class loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
724 if (automatically_generated_chrec_p (chrec
))
727 switch (TREE_CODE (chrec
))
729 case POLYNOMIAL_CHREC
:
730 chloop
= get_chrec_loop (chrec
);
733 return build_polynomial_chrec
735 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
737 CHREC_RIGHT (chrec
));
739 else if (flow_loop_nested_p (chloop
, loop
))
740 /* There is no evolution in this loop. */
741 return initial_condition (chrec
);
743 else if (flow_loop_nested_p (loop
, chloop
))
744 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
748 return chrec_dont_know
;
755 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
756 true, otherwise returns the initial condition in LOOP_NUM. */
759 chrec_component_in_loop_num (tree chrec
,
764 class loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
766 if (automatically_generated_chrec_p (chrec
))
769 switch (TREE_CODE (chrec
))
771 case POLYNOMIAL_CHREC
:
772 chloop
= get_chrec_loop (chrec
);
777 component
= CHREC_RIGHT (chrec
);
779 component
= CHREC_LEFT (chrec
);
781 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
782 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
786 return build_polynomial_chrec
788 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
794 else if (flow_loop_nested_p (chloop
, loop
))
795 /* There is no evolution part in this loop. */
800 gcc_assert (flow_loop_nested_p (loop
, chloop
));
801 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
814 /* Returns the evolution part in LOOP_NUM. Example: the call
815 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
819 evolution_part_in_loop_num (tree chrec
,
822 return chrec_component_in_loop_num (chrec
, loop_num
, true);
825 /* Returns the initial condition in LOOP_NUM. Example: the call
826 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
830 initial_condition_in_loop_num (tree chrec
,
833 return chrec_component_in_loop_num (chrec
, loop_num
, false);
836 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
837 This function is essentially used for setting the evolution to
838 chrec_dont_know, for example after having determined that it is
839 impossible to say how many times a loop will execute. */
842 reset_evolution_in_loop (unsigned loop_num
,
846 class loop
*loop
= get_loop (cfun
, loop_num
);
848 if (POINTER_TYPE_P (chrec_type (chrec
)))
849 gcc_assert (ptrofftype_p (chrec_type (new_evol
)));
851 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
853 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
854 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
856 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
858 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
860 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), left
, right
);
863 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
864 && CHREC_VARIABLE (chrec
) == loop_num
)
865 chrec
= CHREC_LEFT (chrec
);
867 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
870 /* Merges two evolution functions that were found by following two
871 alternate paths of a conditional expression. */
874 chrec_merge (tree chrec1
,
877 if (chrec1
== chrec_dont_know
878 || chrec2
== chrec_dont_know
)
879 return chrec_dont_know
;
881 if (chrec1
== chrec_known
882 || chrec2
== chrec_known
)
885 if (chrec1
== chrec_not_analyzed_yet
)
887 if (chrec2
== chrec_not_analyzed_yet
)
890 if (eq_evolutions_p (chrec1
, chrec2
))
893 return chrec_dont_know
;
900 /* Helper function for is_multivariate_chrec. */
903 is_multivariate_chrec_rec (const_tree chrec
, unsigned int rec_var
)
905 if (chrec
== NULL_TREE
)
908 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
910 if (CHREC_VARIABLE (chrec
) != rec_var
)
913 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
914 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
920 /* Determine whether the given chrec is multivariate or not. */
923 is_multivariate_chrec (const_tree chrec
)
925 if (chrec
== NULL_TREE
)
928 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
929 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
930 CHREC_VARIABLE (chrec
))
931 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
932 CHREC_VARIABLE (chrec
)));
937 /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
938 NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
941 chrec_contains_symbols (const_tree chrec
, hash_set
<const_tree
> &visited
,
946 if (chrec
== NULL_TREE
)
949 if (TREE_CODE (chrec
) == SSA_NAME
951 || TREE_CODE (chrec
) == POLY_INT_CST
952 || TREE_CODE (chrec
) == PARM_DECL
953 || TREE_CODE (chrec
) == FUNCTION_DECL
954 || TREE_CODE (chrec
) == LABEL_DECL
955 || TREE_CODE (chrec
) == RESULT_DECL
956 || TREE_CODE (chrec
) == FIELD_DECL
)
960 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
961 && flow_loop_nested_p (get_chrec_loop (chrec
), loop
))
964 if (visited
.add (chrec
))
967 n
= TREE_OPERAND_LENGTH (chrec
);
968 for (i
= 0; i
< n
; i
++)
969 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
), visited
, loop
))
974 /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
975 CHREC contains any chrec which is invariant wrto the loop (nest), in other
976 words, chrec defined by outer loops of loop, so from LOOP's point of view,
977 the chrec is considered as a SYMBOL. */
980 chrec_contains_symbols (const_tree chrec
, class loop
* loop
)
982 hash_set
<const_tree
> visited
;
983 return chrec_contains_symbols (chrec
, visited
, loop
);
986 /* Return true when CHREC contains symbolic names defined in
990 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
,
991 hash_set
<const_tree
> &visited
)
995 if (chrec
== NULL_TREE
)
998 if (is_gimple_min_invariant (chrec
))
1001 if (TREE_CODE (chrec
) == SSA_NAME
)
1004 loop_p def_loop
, loop
;
1006 if (SSA_NAME_IS_DEFAULT_DEF (chrec
))
1009 def
= SSA_NAME_DEF_STMT (chrec
);
1010 def_loop
= loop_containing_stmt (def
);
1011 loop
= get_loop (cfun
, loop_nb
);
1013 if (def_loop
== NULL
)
1016 if (loop
== def_loop
|| flow_loop_nested_p (loop
, def_loop
))
1022 if (visited
.add (chrec
))
1025 n
= TREE_OPERAND_LENGTH (chrec
);
1026 for (i
= 0; i
< n
; i
++)
1027 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec
, i
),
1033 /* Return true when CHREC contains symbolic names defined in
1037 chrec_contains_symbols_defined_in_loop (const_tree chrec
, unsigned loop_nb
)
1039 hash_set
<const_tree
> visited
;
1040 return chrec_contains_symbols_defined_in_loop (chrec
, loop_nb
, visited
);
1043 /* Determines whether the chrec contains undetermined coefficients. */
1046 chrec_contains_undetermined (const_tree chrec
, hash_set
<const_tree
> &visited
)
1050 if (chrec
== chrec_dont_know
)
1053 if (chrec
== NULL_TREE
)
1056 if (visited
.add (chrec
))
1059 n
= TREE_OPERAND_LENGTH (chrec
);
1060 for (i
= 0; i
< n
; i
++)
1061 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
), visited
))
1067 chrec_contains_undetermined (const_tree chrec
)
1069 hash_set
<const_tree
> visited
;
1070 return chrec_contains_undetermined (chrec
, visited
);
1073 /* Determines whether the tree EXPR contains chrecs, and increment
1074 SIZE if it is not a NULL pointer by an estimation of the depth of
1078 tree_contains_chrecs (const_tree expr
, int *size
, hash_set
<const_tree
> &visited
)
1082 if (expr
== NULL_TREE
)
1088 if (tree_is_chrec (expr
))
1091 if (visited
.add (expr
))
1094 n
= TREE_OPERAND_LENGTH (expr
);
1095 for (i
= 0; i
< n
; i
++)
1096 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
, visited
))
1102 tree_contains_chrecs (const_tree expr
, int *size
)
1104 hash_set
<const_tree
> visited
;
1105 return tree_contains_chrecs (expr
, size
, visited
);
1109 /* Recursive helper function. */
1112 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1114 if (evolution_function_is_constant_p (chrec
))
1117 if (TREE_CODE (chrec
) == SSA_NAME
1119 || expr_invariant_in_loop_p (get_loop (cfun
, loopnum
), chrec
)))
1122 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1124 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
1125 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1126 get_chrec_loop (chrec
))
1127 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
1129 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
1135 switch (TREE_OPERAND_LENGTH (chrec
))
1138 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
1144 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1156 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1159 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1161 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1164 /* Determine whether the given tree is an affine multivariate
1168 evolution_function_is_affine_multivariate_p (const_tree chrec
, int loopnum
)
1170 if (chrec
== NULL_TREE
)
1173 switch (TREE_CODE (chrec
))
1175 case POLYNOMIAL_CHREC
:
1176 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
), loopnum
))
1178 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
))
1182 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1183 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1184 != CHREC_VARIABLE (chrec
)
1185 && evolution_function_is_affine_multivariate_p
1186 (CHREC_RIGHT (chrec
), loopnum
))
1194 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
)
1195 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1196 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1197 && evolution_function_is_affine_multivariate_p
1198 (CHREC_LEFT (chrec
), loopnum
))
1209 /* Determine whether the given tree is a function in zero or one
1210 variables with respect to loop specified by LOOPNUM. Note only positive
1211 LOOPNUM stands for a real loop. */
1214 evolution_function_is_univariate_p (const_tree chrec
, int loopnum
)
1216 if (chrec
== NULL_TREE
)
1220 switch (TREE_CODE (chrec
))
1222 case POLYNOMIAL_CHREC
:
1223 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1225 case POLYNOMIAL_CHREC
:
1226 sub_chrec
= CHREC_LEFT (chrec
);
1227 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (sub_chrec
)
1229 || CHREC_VARIABLE (sub_chrec
) == (unsigned) loopnum
1230 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1231 get_chrec_loop (sub_chrec
))))
1233 if (!evolution_function_is_univariate_p (sub_chrec
, loopnum
))
1238 if (tree_contains_chrecs (CHREC_LEFT (chrec
), NULL
))
1243 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1245 case POLYNOMIAL_CHREC
:
1246 sub_chrec
= CHREC_RIGHT (chrec
);
1247 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (sub_chrec
)
1249 || CHREC_VARIABLE (sub_chrec
) == (unsigned) loopnum
1250 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1251 get_chrec_loop (sub_chrec
))))
1253 if (!evolution_function_is_univariate_p (sub_chrec
, loopnum
))
1258 if (tree_contains_chrecs (CHREC_RIGHT (chrec
), NULL
))
1269 /* Returns the number of variables of CHREC. Example: the call
1270 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1273 nb_vars_in_chrec (tree chrec
)
1275 if (chrec
== NULL_TREE
)
1278 switch (TREE_CODE (chrec
))
1280 case POLYNOMIAL_CHREC
:
1281 return 1 + nb_vars_in_chrec
1282 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1289 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1290 the scev corresponds to. AT_STMT is the statement at that the scev is
1291 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1292 that the rules for overflow of the given language apply (e.g., that signed
1293 arithmetics in C does not overflow) -- i.e., to use them to avoid
1294 unnecessary tests, but also to enforce that the result follows them.
1295 FROM is the source variable converted if it's not NULL. Returns true if
1296 the conversion succeeded, false otherwise. */
1299 convert_affine_scev (class loop
*loop
, tree type
,
1300 tree
*base
, tree
*step
, gimple
*at_stmt
,
1301 bool use_overflow_semantics
, tree from
)
1303 tree ct
= TREE_TYPE (*step
);
1304 bool enforce_overflow_semantics
;
1305 bool must_check_src_overflow
, must_check_rslt_overflow
;
1306 tree new_base
, new_step
;
1307 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1310 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1311 but we must check some assumptions.
1313 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1314 of CT is smaller than the precision of TYPE. For example, when we
1315 cast unsigned char [254, +, 1] to unsigned, the values on left side
1316 are 254, 255, 0, 1, ..., but those on the right side are
1317 254, 255, 256, 257, ...
1318 2) In case that we must also preserve the fact that signed ivs do not
1319 overflow, we must additionally check that the new iv does not wrap.
1320 For example, unsigned char [125, +, 1] casted to signed char could
1321 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1322 which would confuse optimizers that assume that this does not
1324 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1326 enforce_overflow_semantics
= (use_overflow_semantics
1327 && nowrap_type_p (type
));
1328 if (enforce_overflow_semantics
)
1330 /* We can avoid checking whether the result overflows in the following
1333 -- must_check_src_overflow is true, and the range of TYPE is superset
1334 of the range of CT -- i.e., in all cases except if CT signed and
1336 -- both CT and TYPE have the same precision and signedness, and we
1337 verify instead that the source does not overflow (this may be
1338 easier than verifying it for the result, as we may use the
1339 information about the semantics of overflow in CT). */
1340 if (must_check_src_overflow
)
1342 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1343 must_check_rslt_overflow
= true;
1345 must_check_rslt_overflow
= false;
1347 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1348 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1350 must_check_rslt_overflow
= false;
1351 must_check_src_overflow
= true;
1354 must_check_rslt_overflow
= true;
1357 must_check_rslt_overflow
= false;
1359 if (must_check_src_overflow
1360 && scev_probably_wraps_p (from
, *base
, *step
, at_stmt
, loop
,
1361 use_overflow_semantics
))
1364 new_base
= chrec_convert (type
, *base
, at_stmt
, use_overflow_semantics
);
1365 /* The step must be sign extended, regardless of the signedness
1366 of CT and TYPE. This only needs to be handled specially when
1367 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1368 (with values 100, 99, 98, ...) from becoming signed or unsigned
1369 [100, +, 255] with values 100, 355, ...; the sign-extension is
1370 performed by default when CT is signed. */
1372 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1374 tree signed_ct
= build_nonstandard_integer_type (TYPE_PRECISION (ct
), 0);
1375 new_step
= chrec_convert (signed_ct
, new_step
, at_stmt
,
1376 use_overflow_semantics
);
1378 new_step
= chrec_convert (step_type
, new_step
, at_stmt
,
1379 use_overflow_semantics
);
1381 if (automatically_generated_chrec_p (new_base
)
1382 || automatically_generated_chrec_p (new_step
))
1385 if (must_check_rslt_overflow
1386 /* Note that in this case we cannot use the fact that signed variables
1387 do not overflow, as this is what we are verifying for the new iv. */
1388 && scev_probably_wraps_p (NULL_TREE
, new_base
, new_step
,
1389 at_stmt
, loop
, false))
1398 /* Convert CHREC for the right hand side of a CHREC.
1399 The increment for a pointer type is always sizetype. */
1402 chrec_convert_rhs (tree type
, tree chrec
, gimple
*at_stmt
)
1404 if (POINTER_TYPE_P (type
))
1407 return chrec_convert (type
, chrec
, at_stmt
);
1410 /* Convert CHREC to TYPE. When the analyzer knows the context in
1411 which the CHREC is built, it sets AT_STMT to the statement that
1412 contains the definition of the analyzed variable, otherwise the
1413 conversion is less accurate: the information is used for
1414 determining a more accurate estimation of the number of iterations.
1415 By default AT_STMT could be safely set to NULL_TREE.
1417 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1418 the rules for overflow of the given language apply (e.g., that signed
1419 arithmetics in C does not overflow) -- i.e., to use them to avoid
1420 unnecessary tests, but also to enforce that the result follows them.
1422 FROM is the source variable converted if it's not NULL. */
1425 chrec_convert_1 (tree type
, tree chrec
, gimple
*at_stmt
,
1426 bool use_overflow_semantics
, tree from
)
1432 if (automatically_generated_chrec_p (chrec
))
1435 ct
= chrec_type (chrec
);
1436 if (useless_type_conversion_p (type
, ct
))
1439 if (!evolution_function_is_affine_p (chrec
))
1442 loop
= get_chrec_loop (chrec
);
1443 base
= CHREC_LEFT (chrec
);
1444 step
= CHREC_RIGHT (chrec
);
1446 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1447 use_overflow_semantics
, from
))
1448 return build_polynomial_chrec (loop
->num
, base
, step
);
1450 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1452 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1453 may be more expensive. We do want to perform this optimization here
1454 though for canonicalization reasons. */
1455 if (use_overflow_semantics
1456 && (TREE_CODE (chrec
) == PLUS_EXPR
1457 || TREE_CODE (chrec
) == MINUS_EXPR
)
1458 && TREE_CODE (type
) == INTEGER_TYPE
1459 && TREE_CODE (ct
) == INTEGER_TYPE
1460 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1461 && TYPE_OVERFLOW_UNDEFINED (ct
))
1462 res
= fold_build2 (TREE_CODE (chrec
), type
,
1463 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1464 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1465 /* Similar perform the trick that (signed char)((int)x + 2) can be
1466 narrowed to (signed char)((unsigned char)x + 2). */
1467 else if (use_overflow_semantics
1468 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1469 && TREE_CODE (ct
) == INTEGER_TYPE
1470 && TREE_CODE (type
) == INTEGER_TYPE
1471 && TYPE_OVERFLOW_UNDEFINED (type
)
1472 && TYPE_PRECISION (type
) < TYPE_PRECISION (ct
))
1474 tree utype
= unsigned_type_for (type
);
1475 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1476 fold_convert (utype
,
1477 CHREC_LEFT (chrec
)),
1478 fold_convert (utype
,
1479 CHREC_RIGHT (chrec
)));
1480 res
= chrec_convert_1 (type
, res
, at_stmt
, use_overflow_semantics
, from
);
1483 res
= fold_convert (type
, chrec
);
1485 /* Don't propagate overflows. */
1486 if (CONSTANT_CLASS_P (res
))
1487 TREE_OVERFLOW (res
) = 0;
1489 /* But reject constants that don't fit in their type after conversion.
1490 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1491 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1492 and can cause problems later when computing niters of loops. Note
1493 that we don't do the check before converting because we don't want
1494 to reject conversions of negative chrecs to unsigned types. */
1495 if (TREE_CODE (res
) == INTEGER_CST
1496 && TREE_CODE (type
) == INTEGER_TYPE
1497 && !int_fits_type_p (res
, type
))
1498 res
= chrec_dont_know
;
1503 /* Convert CHREC to TYPE. When the analyzer knows the context in
1504 which the CHREC is built, it sets AT_STMT to the statement that
1505 contains the definition of the analyzed variable, otherwise the
1506 conversion is less accurate: the information is used for
1507 determining a more accurate estimation of the number of iterations.
1508 By default AT_STMT could be safely set to NULL_TREE.
1510 The following rule is always true: TREE_TYPE (chrec) ==
1511 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1512 An example of what could happen when adding two chrecs and the type
1513 of the CHREC_RIGHT is different than CHREC_LEFT is:
1515 {(uint) 0, +, (uchar) 10} +
1516 {(uint) 0, +, (uchar) 250}
1518 that would produce a wrong result if CHREC_RIGHT is not (uint):
1520 {(uint) 0, +, (uchar) 4}
1524 {(uint) 0, +, (uint) 260}
1526 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1527 the rules for overflow of the given language apply (e.g., that signed
1528 arithmetics in C does not overflow) -- i.e., to use them to avoid
1529 unnecessary tests, but also to enforce that the result follows them.
1531 FROM is the source variable converted if it's not NULL. */
1534 chrec_convert (tree type
, tree chrec
, gimple
*at_stmt
,
1535 bool use_overflow_semantics
, tree from
)
1537 return chrec_convert_1 (type
, chrec
, at_stmt
, use_overflow_semantics
, from
);
1540 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1541 chrec if something else than what chrec_convert would do happens, NULL_TREE
1542 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1543 if the result chrec may overflow. */
1546 chrec_convert_aggressive (tree type
, tree chrec
, bool *fold_conversions
)
1548 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1550 gcc_assert (fold_conversions
!= NULL
);
1552 if (automatically_generated_chrec_p (chrec
)
1553 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1556 inner_type
= TREE_TYPE (chrec
);
1557 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1560 if (useless_type_conversion_p (type
, inner_type
))
1563 if (!*fold_conversions
&& evolution_function_is_affine_p (chrec
))
1568 loop
= get_chrec_loop (chrec
);
1569 base
= CHREC_LEFT (chrec
);
1570 step
= CHREC_RIGHT (chrec
);
1571 if (convert_affine_scev (loop
, type
, &base
, &step
, NULL
, true))
1572 return build_polynomial_chrec (loop
->num
, base
, step
);
1574 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1576 left
= CHREC_LEFT (chrec
);
1577 right
= CHREC_RIGHT (chrec
);
1578 lc
= chrec_convert_aggressive (type
, left
, fold_conversions
);
1580 lc
= chrec_convert (type
, left
, NULL
);
1581 rc
= chrec_convert_aggressive (rtype
, right
, fold_conversions
);
1583 rc
= chrec_convert (rtype
, right
, NULL
);
1585 *fold_conversions
= true;
1587 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1590 /* Returns true when CHREC0 == CHREC1. */
1593 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1595 if (chrec0
== NULL_TREE
1596 || chrec1
== NULL_TREE
1597 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1600 if (chrec0
== chrec1
)
1603 if (! types_compatible_p (TREE_TYPE (chrec0
), TREE_TYPE (chrec1
)))
1606 switch (TREE_CODE (chrec0
))
1608 case POLYNOMIAL_CHREC
:
1609 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1610 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1611 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1616 case POINTER_PLUS_EXPR
:
1617 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1618 TREE_OPERAND (chrec1
, 0))
1619 && eq_evolutions_p (TREE_OPERAND (chrec0
, 1),
1620 TREE_OPERAND (chrec1
, 1));
1623 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1624 TREE_OPERAND (chrec1
, 0));
1627 return operand_equal_p (chrec0
, chrec1
, 0);
1631 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1632 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1633 which of these cases happens. */
1636 scev_direction (const_tree chrec
)
1640 if (!evolution_function_is_affine_p (chrec
))
1641 return EV_DIR_UNKNOWN
;
1643 step
= CHREC_RIGHT (chrec
);
1644 if (TREE_CODE (step
) != INTEGER_CST
)
1645 return EV_DIR_UNKNOWN
;
1647 if (tree_int_cst_sign_bit (step
))
1648 return EV_DIR_DECREASES
;
1650 return EV_DIR_GROWS
;
1653 /* Iterates over all the components of SCEV, and calls CBCK. */
1656 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1658 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1661 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1665 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1669 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1678 /* Returns true when the operation can be part of a linear
1682 operator_is_linear (tree scev
)
1684 switch (TREE_CODE (scev
))
1687 case POLYNOMIAL_CHREC
:
1689 case POINTER_PLUS_EXPR
:
1694 case NON_LVALUE_EXPR
:
1704 /* Return true when SCEV is a linear expression. Linear expressions
1705 can contain additions, substractions and multiplications.
1706 Multiplications are restricted to constant scaling: "cst * x". */
1709 scev_is_linear_expression (tree scev
)
1711 if (evolution_function_is_constant_p (scev
))
1715 || !operator_is_linear (scev
))
1718 if (TREE_CODE (scev
) == MULT_EXPR
)
1719 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1720 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1722 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1723 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1726 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1729 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1730 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1731 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1734 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1735 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1738 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1748 /* Determines whether the expression CHREC contains only interger consts
1749 in the right parts. */
1752 evolution_function_right_is_integer_cst (const_tree chrec
)
1754 if (chrec
== NULL_TREE
)
1757 switch (TREE_CODE (chrec
))
1762 case POLYNOMIAL_CHREC
:
1763 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1764 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1765 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1768 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));