1 /* Chains of recurrences.
2 Copyright (C) 2003-2018 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"
40 #include "tree-scalar-evolution.h"
42 /* Extended folder for chrecs. */
44 /* Determines whether CST is not a constant evolution. */
47 is_not_constant_evolution (const_tree cst
)
49 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
52 /* Fold CODE for a polynomial function and a constant. */
55 chrec_fold_poly_cst (enum tree_code code
,
62 gcc_assert (TREE_CODE (poly
) == POLYNOMIAL_CHREC
);
63 gcc_checking_assert (!is_not_constant_evolution (cst
));
64 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly
)));
69 return build_polynomial_chrec
70 (CHREC_VARIABLE (poly
),
71 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
75 return build_polynomial_chrec
76 (CHREC_VARIABLE (poly
),
77 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
81 return build_polynomial_chrec
82 (CHREC_VARIABLE (poly
),
83 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
84 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
87 return chrec_dont_know
;
91 /* Fold the addition of two polynomial functions. */
94 chrec_fold_plus_poly_poly (enum tree_code code
,
100 struct loop
*loop0
= get_chrec_loop (poly0
);
101 struct loop
*loop1
= get_chrec_loop (poly1
);
102 tree rtype
= code
== POINTER_PLUS_EXPR
? chrec_type (poly1
) : type
;
106 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
107 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
108 if (POINTER_TYPE_P (chrec_type (poly0
)))
109 gcc_checking_assert (ptrofftype_p (chrec_type (poly1
))
110 && useless_type_conversion_p (type
, chrec_type (poly0
)));
112 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
113 && useless_type_conversion_p (type
, chrec_type (poly1
)));
116 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
117 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
118 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
119 if (flow_loop_nested_p (loop0
, loop1
))
121 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
122 return build_polynomial_chrec
123 (CHREC_VARIABLE (poly1
),
124 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
125 CHREC_RIGHT (poly1
));
127 return build_polynomial_chrec
128 (CHREC_VARIABLE (poly1
),
129 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
130 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
131 SCALAR_FLOAT_TYPE_P (type
)
132 ? build_real (type
, dconstm1
)
133 : build_int_cst_type (type
, -1)));
136 if (flow_loop_nested_p (loop1
, loop0
))
138 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
139 return build_polynomial_chrec
140 (CHREC_VARIABLE (poly0
),
141 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
142 CHREC_RIGHT (poly0
));
144 return build_polynomial_chrec
145 (CHREC_VARIABLE (poly0
),
146 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
147 CHREC_RIGHT (poly0
));
150 /* This function should never be called for chrecs of loops that
151 do not belong to the same loop nest. */
154 /* It still can happen if we are not in loop-closed SSA form. */
155 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
156 return chrec_dont_know
;
159 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
161 left
= chrec_fold_plus
162 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
163 right
= chrec_fold_plus
164 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
168 left
= chrec_fold_minus
169 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
170 right
= chrec_fold_minus
171 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
174 if (chrec_zerop (right
))
177 return build_polynomial_chrec
178 (CHREC_VARIABLE (poly0
), left
, right
);
183 /* Fold the multiplication of two polynomial functions. */
186 chrec_fold_multiply_poly_poly (tree type
,
192 struct loop
*loop0
= get_chrec_loop (poly0
);
193 struct loop
*loop1
= get_chrec_loop (poly1
);
197 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
198 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
199 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
200 && useless_type_conversion_p (type
, chrec_type (poly1
)));
202 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
203 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
204 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
205 if (flow_loop_nested_p (loop0
, loop1
))
206 /* poly0 is a constant wrt. poly1. */
207 return build_polynomial_chrec
208 (CHREC_VARIABLE (poly1
),
209 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
210 CHREC_RIGHT (poly1
));
212 if (flow_loop_nested_p (loop1
, loop0
))
213 /* poly1 is a constant wrt. poly0. */
214 return build_polynomial_chrec
215 (CHREC_VARIABLE (poly0
),
216 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
217 CHREC_RIGHT (poly0
));
221 /* It still can happen if we are not in loop-closed SSA form. */
222 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
223 return chrec_dont_know
;
226 /* poly0 and poly1 are two polynomials in the same variable,
227 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
230 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
233 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
234 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
236 CHREC_LEFT (poly1
)));
238 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
239 /* "a*d + b*c + b*d". */
240 t1
= chrec_fold_plus (type
, t1
, t2
);
242 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
243 ? build_real (type
, dconst2
)
244 : build_int_cst (type
, 2), t2
);
246 var
= CHREC_VARIABLE (poly0
);
247 return build_polynomial_chrec (var
, t0
,
248 build_polynomial_chrec (var
, t1
, t2
));
251 /* When the operands are automatically_generated_chrec_p, the fold has
252 to respect the semantics of the operands. */
255 chrec_fold_automatically_generated_operands (tree op0
,
258 if (op0
== chrec_dont_know
259 || op1
== chrec_dont_know
)
260 return chrec_dont_know
;
262 if (op0
== chrec_known
263 || op1
== chrec_known
)
266 if (op0
== chrec_not_analyzed_yet
267 || op1
== chrec_not_analyzed_yet
)
268 return chrec_not_analyzed_yet
;
270 /* The default case produces a safe result. */
271 return chrec_dont_know
;
274 /* Fold the addition of two chrecs. */
277 chrec_fold_plus_1 (enum tree_code code
, tree type
,
280 if (automatically_generated_chrec_p (op0
)
281 || automatically_generated_chrec_p (op1
))
282 return chrec_fold_automatically_generated_operands (op0
, op1
);
284 switch (TREE_CODE (op0
))
286 case POLYNOMIAL_CHREC
:
288 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
289 switch (TREE_CODE (op1
))
291 case POLYNOMIAL_CHREC
:
293 (!chrec_contains_symbols_defined_in_loop (op1
,
294 CHREC_VARIABLE (op1
)));
295 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
299 /* We can strip sign-conversions to signed by performing the
300 operation in unsigned. */
301 tree optype
= TREE_TYPE (TREE_OPERAND (op1
, 0));
302 if (INTEGRAL_TYPE_P (type
)
303 && INTEGRAL_TYPE_P (optype
)
304 && tree_nop_conversion_p (type
, optype
)
305 && TYPE_UNSIGNED (optype
))
306 return chrec_convert (type
,
307 chrec_fold_plus_1 (code
, optype
,
308 chrec_convert (optype
,
310 TREE_OPERAND (op1
, 0)),
312 if (tree_contains_chrecs (op1
, NULL
))
313 return chrec_dont_know
;
318 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
319 return build_polynomial_chrec
320 (CHREC_VARIABLE (op0
),
321 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
324 return build_polynomial_chrec
325 (CHREC_VARIABLE (op0
),
326 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
332 /* We can strip sign-conversions to signed by performing the
333 operation in unsigned. */
334 tree optype
= TREE_TYPE (TREE_OPERAND (op0
, 0));
335 if (INTEGRAL_TYPE_P (type
)
336 && INTEGRAL_TYPE_P (optype
)
337 && tree_nop_conversion_p (type
, optype
)
338 && TYPE_UNSIGNED (optype
))
339 return chrec_convert (type
,
340 chrec_fold_plus_1 (code
, optype
,
341 TREE_OPERAND (op0
, 0),
342 chrec_convert (optype
,
345 if (tree_contains_chrecs (op0
, NULL
))
346 return chrec_dont_know
;
351 switch (TREE_CODE (op1
))
353 case POLYNOMIAL_CHREC
:
355 (!chrec_contains_symbols_defined_in_loop (op1
,
356 CHREC_VARIABLE (op1
)));
357 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
358 return build_polynomial_chrec
359 (CHREC_VARIABLE (op1
),
360 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
363 return build_polynomial_chrec
364 (CHREC_VARIABLE (op1
),
365 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
366 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
367 SCALAR_FLOAT_TYPE_P (type
)
368 ? build_real (type
, dconstm1
)
369 : build_int_cst_type (type
, -1)));
372 if (tree_contains_chrecs (op1
, NULL
))
373 return chrec_dont_know
;
379 if ((tree_contains_chrecs (op0
, &size
)
380 || tree_contains_chrecs (op1
, &size
))
381 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
382 return build2 (code
, type
, op0
, op1
);
383 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
385 if (code
== POINTER_PLUS_EXPR
)
386 return fold_build_pointer_plus (fold_convert (type
, op0
),
389 return fold_build2 (code
, type
,
390 fold_convert (type
, op0
),
391 fold_convert (type
, op1
));
394 return chrec_dont_know
;
400 /* Fold the addition of two chrecs. */
403 chrec_fold_plus (tree type
,
408 if (automatically_generated_chrec_p (op0
)
409 || automatically_generated_chrec_p (op1
))
410 return chrec_fold_automatically_generated_operands (op0
, op1
);
412 if (integer_zerop (op0
))
413 return chrec_convert (type
, op1
, NULL
);
414 if (integer_zerop (op1
))
415 return chrec_convert (type
, op0
, NULL
);
417 if (POINTER_TYPE_P (type
))
418 code
= POINTER_PLUS_EXPR
;
422 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
425 /* Fold the subtraction of two chrecs. */
428 chrec_fold_minus (tree type
,
432 if (automatically_generated_chrec_p (op0
)
433 || automatically_generated_chrec_p (op1
))
434 return chrec_fold_automatically_generated_operands (op0
, op1
);
436 if (integer_zerop (op1
))
439 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
442 /* Fold the multiplication of two chrecs. */
445 chrec_fold_multiply (tree type
,
449 if (automatically_generated_chrec_p (op0
)
450 || automatically_generated_chrec_p (op1
))
451 return chrec_fold_automatically_generated_operands (op0
, op1
);
453 switch (TREE_CODE (op0
))
455 case POLYNOMIAL_CHREC
:
457 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
458 switch (TREE_CODE (op1
))
460 case POLYNOMIAL_CHREC
:
462 (!chrec_contains_symbols_defined_in_loop (op1
,
463 CHREC_VARIABLE (op1
)));
464 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
467 if (tree_contains_chrecs (op1
, NULL
))
468 return chrec_dont_know
;
472 if (integer_onep (op1
))
474 if (integer_zerop (op1
))
475 return build_int_cst (type
, 0);
477 return build_polynomial_chrec
478 (CHREC_VARIABLE (op0
),
479 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
480 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
484 if (tree_contains_chrecs (op0
, NULL
))
485 return chrec_dont_know
;
489 if (integer_onep (op0
))
492 if (integer_zerop (op0
))
493 return build_int_cst (type
, 0);
495 switch (TREE_CODE (op1
))
497 case POLYNOMIAL_CHREC
:
499 (!chrec_contains_symbols_defined_in_loop (op1
,
500 CHREC_VARIABLE (op1
)));
501 return build_polynomial_chrec
502 (CHREC_VARIABLE (op1
),
503 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
504 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
507 if (tree_contains_chrecs (op1
, NULL
))
508 return chrec_dont_know
;
512 if (integer_onep (op1
))
514 if (integer_zerop (op1
))
515 return build_int_cst (type
, 0);
516 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
525 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
526 calculation overflows, otherwise return C(n,k) with type TYPE. */
529 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
534 /* Handle the most frequent cases. */
536 return build_int_cst (type
, 1);
538 return fold_convert (type
, n
);
540 widest_int num
= wi::to_widest (n
);
542 /* Check that k <= n. */
543 if (wi::ltu_p (num
, k
))
546 /* Denominator = 2. */
547 widest_int denom
= 2;
549 /* Index = Numerator-1. */
550 widest_int idx
= num
- 1;
552 /* Numerator = Numerator*Index = n*(n-1). */
553 num
= wi::smul (num
, idx
, &overflow
);
557 for (i
= 3; i
<= k
; i
++)
562 /* Numerator *= Index. */
563 num
= wi::smul (num
, idx
, &overflow
);
567 /* Denominator *= i. */
571 /* Result = Numerator / Denominator. */
572 num
= wi::udiv_trunc (num
, denom
);
573 if (! wi::fits_to_tree_p (num
, type
))
575 return wide_int_to_tree (type
, num
);
578 /* Helper function. Use the Newton's interpolating formula for
579 evaluating the value of the evolution function.
580 The result may be in an unsigned type of CHREC. */
583 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
585 tree arg0
, arg1
, binomial_n_k
;
586 tree type
= TREE_TYPE (chrec
);
587 struct loop
*var_loop
= get_loop (cfun
, var
);
589 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
590 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
591 chrec
= CHREC_LEFT (chrec
);
593 /* The formula associates the expression and thus we have to make
594 sure to not introduce undefined overflow. */
596 if (INTEGRAL_TYPE_P (type
)
597 && ! TYPE_OVERFLOW_WRAPS (type
))
598 ctype
= unsigned_type_for (type
);
600 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
601 && CHREC_VARIABLE (chrec
) == var
)
603 arg1
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
604 if (arg1
== chrec_dont_know
)
605 return chrec_dont_know
;
606 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
608 return chrec_dont_know
;
609 tree l
= chrec_convert (ctype
, CHREC_LEFT (chrec
), NULL
);
610 arg0
= fold_build2 (MULT_EXPR
, ctype
, l
, binomial_n_k
);
611 return chrec_fold_plus (ctype
, arg0
, arg1
);
614 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
616 return chrec_dont_know
;
618 return fold_build2 (MULT_EXPR
, ctype
,
619 chrec_convert (ctype
, chrec
, NULL
), binomial_n_k
);
622 /* Evaluates "CHREC (X)" when the varying variable is VAR.
623 Example: Given the following parameters,
629 The result is given by the Newton's interpolating formula:
630 3 * \binom{10}{0} + 4 * \binom{10}{1}.
634 chrec_apply (unsigned var
,
638 tree type
= chrec_type (chrec
);
639 tree res
= chrec_dont_know
;
641 if (automatically_generated_chrec_p (chrec
)
642 || automatically_generated_chrec_p (x
)
644 /* When the symbols are defined in an outer loop, it is possible
645 to symbolically compute the apply, since the symbols are
646 constants with respect to the varying loop. */
647 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
648 return chrec_dont_know
;
650 if (dump_file
&& (dump_flags
& TDF_SCEV
))
651 fprintf (dump_file
, "(chrec_apply \n");
653 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
654 x
= build_real_from_int_cst (type
, x
);
656 switch (TREE_CODE (chrec
))
658 case POLYNOMIAL_CHREC
:
659 if (evolution_function_is_affine_p (chrec
))
661 if (CHREC_VARIABLE (chrec
) != var
)
662 return build_polynomial_chrec
663 (CHREC_VARIABLE (chrec
),
664 chrec_apply (var
, CHREC_LEFT (chrec
), x
),
665 chrec_apply (var
, CHREC_RIGHT (chrec
), x
));
667 /* "{a, +, b} (x)" -> "a + b*x". */
668 x
= chrec_convert_rhs (type
, x
, NULL
);
669 res
= chrec_fold_multiply (TREE_TYPE (x
), CHREC_RIGHT (chrec
), x
);
670 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
672 else if (TREE_CODE (x
) == INTEGER_CST
673 && tree_int_cst_sgn (x
) == 1)
674 /* testsuite/.../ssa-chrec-38.c. */
675 res
= chrec_convert (type
, chrec_evaluate (var
, chrec
, x
, 0), NULL
);
677 res
= chrec_dont_know
;
681 res
= chrec_convert (TREE_TYPE (chrec
),
682 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
691 if (dump_file
&& (dump_flags
& TDF_SCEV
))
693 fprintf (dump_file
, " (varying_loop = %d\n", var
);
694 fprintf (dump_file
, ")\n (chrec = ");
695 print_generic_expr (dump_file
, chrec
);
696 fprintf (dump_file
, ")\n (x = ");
697 print_generic_expr (dump_file
, x
);
698 fprintf (dump_file
, ")\n (res = ");
699 print_generic_expr (dump_file
, res
);
700 fprintf (dump_file
, "))\n");
706 /* For a given CHREC and an induction variable map IV_MAP that maps
707 (loop->num, expr) for every loop number of the current_loops an
708 expression, calls chrec_apply when the expression is not NULL. */
711 chrec_apply_map (tree chrec
, vec
<tree
> iv_map
)
716 FOR_EACH_VEC_ELT (iv_map
, i
, expr
)
718 chrec
= chrec_apply (i
, chrec
, expr
);
723 /* Replaces the initial condition in CHREC with INIT_COND. */
726 chrec_replace_initial_condition (tree chrec
,
729 if (automatically_generated_chrec_p (chrec
))
732 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
734 switch (TREE_CODE (chrec
))
736 case POLYNOMIAL_CHREC
:
737 return build_polynomial_chrec
738 (CHREC_VARIABLE (chrec
),
739 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
740 CHREC_RIGHT (chrec
));
747 /* Returns the initial condition of a given CHREC. */
750 initial_condition (tree chrec
)
752 if (automatically_generated_chrec_p (chrec
))
755 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
756 return initial_condition (CHREC_LEFT (chrec
));
761 /* Returns a univariate function that represents the evolution in
762 LOOP_NUM. Mask the evolution of any other loop. */
765 hide_evolution_in_other_loops_than_loop (tree chrec
,
768 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
769 if (automatically_generated_chrec_p (chrec
))
772 switch (TREE_CODE (chrec
))
774 case POLYNOMIAL_CHREC
:
775 chloop
= get_chrec_loop (chrec
);
778 return build_polynomial_chrec
780 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
782 CHREC_RIGHT (chrec
));
784 else if (flow_loop_nested_p (chloop
, loop
))
785 /* There is no evolution in this loop. */
786 return initial_condition (chrec
);
788 else if (flow_loop_nested_p (loop
, chloop
))
789 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
793 return chrec_dont_know
;
800 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
801 true, otherwise returns the initial condition in LOOP_NUM. */
804 chrec_component_in_loop_num (tree chrec
,
809 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
811 if (automatically_generated_chrec_p (chrec
))
814 switch (TREE_CODE (chrec
))
816 case POLYNOMIAL_CHREC
:
817 chloop
= get_chrec_loop (chrec
);
822 component
= CHREC_RIGHT (chrec
);
824 component
= CHREC_LEFT (chrec
);
826 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
827 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
831 return build_polynomial_chrec
833 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
839 else if (flow_loop_nested_p (chloop
, loop
))
840 /* There is no evolution part in this loop. */
845 gcc_assert (flow_loop_nested_p (loop
, chloop
));
846 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
859 /* Returns the evolution part in LOOP_NUM. Example: the call
860 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
864 evolution_part_in_loop_num (tree chrec
,
867 return chrec_component_in_loop_num (chrec
, loop_num
, true);
870 /* Returns the initial condition in LOOP_NUM. Example: the call
871 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
875 initial_condition_in_loop_num (tree chrec
,
878 return chrec_component_in_loop_num (chrec
, loop_num
, false);
881 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
882 This function is essentially used for setting the evolution to
883 chrec_dont_know, for example after having determined that it is
884 impossible to say how many times a loop will execute. */
887 reset_evolution_in_loop (unsigned loop_num
,
891 struct loop
*loop
= get_loop (cfun
, loop_num
);
893 if (POINTER_TYPE_P (chrec_type (chrec
)))
894 gcc_assert (ptrofftype_p (chrec_type (new_evol
)));
896 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
898 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
899 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
901 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
903 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
905 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), left
, right
);
908 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
909 && CHREC_VARIABLE (chrec
) == loop_num
)
910 chrec
= CHREC_LEFT (chrec
);
912 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
915 /* Merges two evolution functions that were found by following two
916 alternate paths of a conditional expression. */
919 chrec_merge (tree chrec1
,
922 if (chrec1
== chrec_dont_know
923 || chrec2
== chrec_dont_know
)
924 return chrec_dont_know
;
926 if (chrec1
== chrec_known
927 || chrec2
== chrec_known
)
930 if (chrec1
== chrec_not_analyzed_yet
)
932 if (chrec2
== chrec_not_analyzed_yet
)
935 if (eq_evolutions_p (chrec1
, chrec2
))
938 return chrec_dont_know
;
945 /* Helper function for is_multivariate_chrec. */
948 is_multivariate_chrec_rec (const_tree chrec
, unsigned int rec_var
)
950 if (chrec
== NULL_TREE
)
953 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
955 if (CHREC_VARIABLE (chrec
) != rec_var
)
958 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
959 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
965 /* Determine whether the given chrec is multivariate or not. */
968 is_multivariate_chrec (const_tree chrec
)
970 if (chrec
== NULL_TREE
)
973 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
974 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
975 CHREC_VARIABLE (chrec
))
976 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
977 CHREC_VARIABLE (chrec
)));
982 /* Determines whether the chrec contains symbolic names or not. */
985 chrec_contains_symbols (const_tree chrec
)
989 if (chrec
== NULL_TREE
)
992 if (TREE_CODE (chrec
) == SSA_NAME
994 || TREE_CODE (chrec
) == POLY_INT_CST
995 || TREE_CODE (chrec
) == PARM_DECL
996 || TREE_CODE (chrec
) == FUNCTION_DECL
997 || TREE_CODE (chrec
) == LABEL_DECL
998 || TREE_CODE (chrec
) == RESULT_DECL
999 || TREE_CODE (chrec
) == FIELD_DECL
)
1002 n
= TREE_OPERAND_LENGTH (chrec
);
1003 for (i
= 0; i
< n
; i
++)
1004 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
)))
1009 /* Determines whether the chrec contains undetermined coefficients. */
1012 chrec_contains_undetermined (const_tree chrec
)
1016 if (chrec
== chrec_dont_know
)
1019 if (chrec
== NULL_TREE
)
1022 n
= TREE_OPERAND_LENGTH (chrec
);
1023 for (i
= 0; i
< n
; i
++)
1024 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
)))
1029 /* Determines whether the tree EXPR contains chrecs, and increment
1030 SIZE if it is not a NULL pointer by an estimation of the depth of
1034 tree_contains_chrecs (const_tree expr
, int *size
)
1038 if (expr
== NULL_TREE
)
1044 if (tree_is_chrec (expr
))
1047 n
= TREE_OPERAND_LENGTH (expr
);
1048 for (i
= 0; i
< n
; i
++)
1049 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
))
1054 /* Recursive helper function. */
1057 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1059 if (evolution_function_is_constant_p (chrec
))
1062 if (TREE_CODE (chrec
) == SSA_NAME
1064 || expr_invariant_in_loop_p (get_loop (cfun
, loopnum
), chrec
)))
1067 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1069 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
1070 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1071 get_chrec_loop (chrec
))
1072 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
1074 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
1080 switch (TREE_OPERAND_LENGTH (chrec
))
1083 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
1089 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1101 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1104 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1106 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1109 /* Determine whether the given tree is an affine multivariate
1113 evolution_function_is_affine_multivariate_p (const_tree chrec
, int loopnum
)
1115 if (chrec
== NULL_TREE
)
1118 switch (TREE_CODE (chrec
))
1120 case POLYNOMIAL_CHREC
:
1121 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
), loopnum
))
1123 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
))
1127 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1128 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1129 != CHREC_VARIABLE (chrec
)
1130 && evolution_function_is_affine_multivariate_p
1131 (CHREC_RIGHT (chrec
), loopnum
))
1139 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
)
1140 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1141 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1142 && evolution_function_is_affine_multivariate_p
1143 (CHREC_LEFT (chrec
), loopnum
))
1154 /* Determine whether the given tree is a function in zero or one
1158 evolution_function_is_univariate_p (const_tree chrec
)
1160 if (chrec
== NULL_TREE
)
1163 switch (TREE_CODE (chrec
))
1165 case POLYNOMIAL_CHREC
:
1166 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1168 case POLYNOMIAL_CHREC
:
1169 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1171 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1176 if (tree_contains_chrecs (CHREC_LEFT (chrec
), NULL
))
1181 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1183 case POLYNOMIAL_CHREC
:
1184 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1186 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1191 if (tree_contains_chrecs (CHREC_RIGHT (chrec
), NULL
))
1202 /* Returns the number of variables of CHREC. Example: the call
1203 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1206 nb_vars_in_chrec (tree chrec
)
1208 if (chrec
== NULL_TREE
)
1211 switch (TREE_CODE (chrec
))
1213 case POLYNOMIAL_CHREC
:
1214 return 1 + nb_vars_in_chrec
1215 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1222 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1223 the scev corresponds to. AT_STMT is the statement at that the scev is
1224 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1225 that the rules for overflow of the given language apply (e.g., that signed
1226 arithmetics in C does not overflow) -- i.e., to use them to avoid
1227 unnecessary tests, but also to enforce that the result follows them.
1228 FROM is the source variable converted if it's not NULL. Returns true if
1229 the conversion succeeded, false otherwise. */
1232 convert_affine_scev (struct loop
*loop
, tree type
,
1233 tree
*base
, tree
*step
, gimple
*at_stmt
,
1234 bool use_overflow_semantics
, tree from
)
1236 tree ct
= TREE_TYPE (*step
);
1237 bool enforce_overflow_semantics
;
1238 bool must_check_src_overflow
, must_check_rslt_overflow
;
1239 tree new_base
, new_step
;
1240 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1243 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1244 but we must check some assumptions.
1246 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1247 of CT is smaller than the precision of TYPE. For example, when we
1248 cast unsigned char [254, +, 1] to unsigned, the values on left side
1249 are 254, 255, 0, 1, ..., but those on the right side are
1250 254, 255, 256, 257, ...
1251 2) In case that we must also preserve the fact that signed ivs do not
1252 overflow, we must additionally check that the new iv does not wrap.
1253 For example, unsigned char [125, +, 1] casted to signed char could
1254 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1255 which would confuse optimizers that assume that this does not
1257 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1259 enforce_overflow_semantics
= (use_overflow_semantics
1260 && nowrap_type_p (type
));
1261 if (enforce_overflow_semantics
)
1263 /* We can avoid checking whether the result overflows in the following
1266 -- must_check_src_overflow is true, and the range of TYPE is superset
1267 of the range of CT -- i.e., in all cases except if CT signed and
1269 -- both CT and TYPE have the same precision and signedness, and we
1270 verify instead that the source does not overflow (this may be
1271 easier than verifying it for the result, as we may use the
1272 information about the semantics of overflow in CT). */
1273 if (must_check_src_overflow
)
1275 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1276 must_check_rslt_overflow
= true;
1278 must_check_rslt_overflow
= false;
1280 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1281 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1283 must_check_rslt_overflow
= false;
1284 must_check_src_overflow
= true;
1287 must_check_rslt_overflow
= true;
1290 must_check_rslt_overflow
= false;
1292 if (must_check_src_overflow
1293 && scev_probably_wraps_p (from
, *base
, *step
, at_stmt
, loop
,
1294 use_overflow_semantics
))
1297 new_base
= chrec_convert (type
, *base
, at_stmt
, use_overflow_semantics
);
1298 /* The step must be sign extended, regardless of the signedness
1299 of CT and TYPE. This only needs to be handled specially when
1300 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1301 (with values 100, 99, 98, ...) from becoming signed or unsigned
1302 [100, +, 255] with values 100, 355, ...; the sign-extension is
1303 performed by default when CT is signed. */
1305 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1307 tree signed_ct
= build_nonstandard_integer_type (TYPE_PRECISION (ct
), 0);
1308 new_step
= chrec_convert (signed_ct
, new_step
, at_stmt
,
1309 use_overflow_semantics
);
1311 new_step
= chrec_convert (step_type
, new_step
, at_stmt
,
1312 use_overflow_semantics
);
1314 if (automatically_generated_chrec_p (new_base
)
1315 || automatically_generated_chrec_p (new_step
))
1318 if (must_check_rslt_overflow
1319 /* Note that in this case we cannot use the fact that signed variables
1320 do not overflow, as this is what we are verifying for the new iv. */
1321 && scev_probably_wraps_p (NULL_TREE
, new_base
, new_step
,
1322 at_stmt
, loop
, false))
1331 /* Convert CHREC for the right hand side of a CHREC.
1332 The increment for a pointer type is always sizetype. */
1335 chrec_convert_rhs (tree type
, tree chrec
, gimple
*at_stmt
)
1337 if (POINTER_TYPE_P (type
))
1340 return chrec_convert (type
, chrec
, at_stmt
);
1343 /* Convert CHREC to TYPE. When the analyzer knows the context in
1344 which the CHREC is built, it sets AT_STMT to the statement that
1345 contains the definition of the analyzed variable, otherwise the
1346 conversion is less accurate: the information is used for
1347 determining a more accurate estimation of the number of iterations.
1348 By default AT_STMT could be safely set to NULL_TREE.
1350 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1351 the rules for overflow of the given language apply (e.g., that signed
1352 arithmetics in C does not overflow) -- i.e., to use them to avoid
1353 unnecessary tests, but also to enforce that the result follows them.
1355 FROM is the source variable converted if it's not NULL. */
1358 chrec_convert_1 (tree type
, tree chrec
, gimple
*at_stmt
,
1359 bool use_overflow_semantics
, tree from
)
1365 if (automatically_generated_chrec_p (chrec
))
1368 ct
= chrec_type (chrec
);
1369 if (useless_type_conversion_p (type
, ct
))
1372 if (!evolution_function_is_affine_p (chrec
))
1375 loop
= get_chrec_loop (chrec
);
1376 base
= CHREC_LEFT (chrec
);
1377 step
= CHREC_RIGHT (chrec
);
1379 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1380 use_overflow_semantics
, from
))
1381 return build_polynomial_chrec (loop
->num
, base
, step
);
1383 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1385 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1386 may be more expensive. We do want to perform this optimization here
1387 though for canonicalization reasons. */
1388 if (use_overflow_semantics
1389 && (TREE_CODE (chrec
) == PLUS_EXPR
1390 || TREE_CODE (chrec
) == MINUS_EXPR
)
1391 && TREE_CODE (type
) == INTEGER_TYPE
1392 && TREE_CODE (ct
) == INTEGER_TYPE
1393 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1394 && TYPE_OVERFLOW_UNDEFINED (ct
))
1395 res
= fold_build2 (TREE_CODE (chrec
), type
,
1396 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1397 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1398 /* Similar perform the trick that (signed char)((int)x + 2) can be
1399 narrowed to (signed char)((unsigned char)x + 2). */
1400 else if (use_overflow_semantics
1401 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1402 && TREE_CODE (ct
) == INTEGER_TYPE
1403 && TREE_CODE (type
) == INTEGER_TYPE
1404 && TYPE_OVERFLOW_UNDEFINED (type
)
1405 && TYPE_PRECISION (type
) < TYPE_PRECISION (ct
))
1407 tree utype
= unsigned_type_for (type
);
1408 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1409 fold_convert (utype
,
1410 CHREC_LEFT (chrec
)),
1411 fold_convert (utype
,
1412 CHREC_RIGHT (chrec
)));
1413 res
= chrec_convert_1 (type
, res
, at_stmt
, use_overflow_semantics
, from
);
1416 res
= fold_convert (type
, chrec
);
1418 /* Don't propagate overflows. */
1419 if (CONSTANT_CLASS_P (res
))
1420 TREE_OVERFLOW (res
) = 0;
1422 /* But reject constants that don't fit in their type after conversion.
1423 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1424 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1425 and can cause problems later when computing niters of loops. Note
1426 that we don't do the check before converting because we don't want
1427 to reject conversions of negative chrecs to unsigned types. */
1428 if (TREE_CODE (res
) == INTEGER_CST
1429 && TREE_CODE (type
) == INTEGER_TYPE
1430 && !int_fits_type_p (res
, type
))
1431 res
= chrec_dont_know
;
1436 /* Convert CHREC to TYPE. When the analyzer knows the context in
1437 which the CHREC is built, it sets AT_STMT to the statement that
1438 contains the definition of the analyzed variable, otherwise the
1439 conversion is less accurate: the information is used for
1440 determining a more accurate estimation of the number of iterations.
1441 By default AT_STMT could be safely set to NULL_TREE.
1443 The following rule is always true: TREE_TYPE (chrec) ==
1444 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1445 An example of what could happen when adding two chrecs and the type
1446 of the CHREC_RIGHT is different than CHREC_LEFT is:
1448 {(uint) 0, +, (uchar) 10} +
1449 {(uint) 0, +, (uchar) 250}
1451 that would produce a wrong result if CHREC_RIGHT is not (uint):
1453 {(uint) 0, +, (uchar) 4}
1457 {(uint) 0, +, (uint) 260}
1459 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1460 the rules for overflow of the given language apply (e.g., that signed
1461 arithmetics in C does not overflow) -- i.e., to use them to avoid
1462 unnecessary tests, but also to enforce that the result follows them.
1464 FROM is the source variable converted if it's not NULL. */
1467 chrec_convert (tree type
, tree chrec
, gimple
*at_stmt
,
1468 bool use_overflow_semantics
, tree from
)
1470 return chrec_convert_1 (type
, chrec
, at_stmt
, use_overflow_semantics
, from
);
1473 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1474 chrec if something else than what chrec_convert would do happens, NULL_TREE
1475 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1476 if the result chrec may overflow. */
1479 chrec_convert_aggressive (tree type
, tree chrec
, bool *fold_conversions
)
1481 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1483 gcc_assert (fold_conversions
!= NULL
);
1485 if (automatically_generated_chrec_p (chrec
)
1486 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1489 inner_type
= TREE_TYPE (chrec
);
1490 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1493 if (useless_type_conversion_p (type
, inner_type
))
1496 if (!*fold_conversions
&& evolution_function_is_affine_p (chrec
))
1501 loop
= get_chrec_loop (chrec
);
1502 base
= CHREC_LEFT (chrec
);
1503 step
= CHREC_RIGHT (chrec
);
1504 if (convert_affine_scev (loop
, type
, &base
, &step
, NULL
, true))
1505 return build_polynomial_chrec (loop
->num
, base
, step
);
1507 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1509 left
= CHREC_LEFT (chrec
);
1510 right
= CHREC_RIGHT (chrec
);
1511 lc
= chrec_convert_aggressive (type
, left
, fold_conversions
);
1513 lc
= chrec_convert (type
, left
, NULL
);
1514 rc
= chrec_convert_aggressive (rtype
, right
, fold_conversions
);
1516 rc
= chrec_convert (rtype
, right
, NULL
);
1518 *fold_conversions
= true;
1520 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1523 /* Returns true when CHREC0 == CHREC1. */
1526 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1528 if (chrec0
== NULL_TREE
1529 || chrec1
== NULL_TREE
1530 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1533 if (chrec0
== chrec1
)
1536 if (! types_compatible_p (TREE_TYPE (chrec0
), TREE_TYPE (chrec1
)))
1539 switch (TREE_CODE (chrec0
))
1541 case POLYNOMIAL_CHREC
:
1542 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1543 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1544 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1549 case POINTER_PLUS_EXPR
:
1550 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1551 TREE_OPERAND (chrec1
, 0))
1552 && eq_evolutions_p (TREE_OPERAND (chrec0
, 1),
1553 TREE_OPERAND (chrec1
, 1));
1556 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1557 TREE_OPERAND (chrec1
, 0));
1560 return operand_equal_p (chrec0
, chrec1
, 0);
1564 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1565 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1566 which of these cases happens. */
1569 scev_direction (const_tree chrec
)
1573 if (!evolution_function_is_affine_p (chrec
))
1574 return EV_DIR_UNKNOWN
;
1576 step
= CHREC_RIGHT (chrec
);
1577 if (TREE_CODE (step
) != INTEGER_CST
)
1578 return EV_DIR_UNKNOWN
;
1580 if (tree_int_cst_sign_bit (step
))
1581 return EV_DIR_DECREASES
;
1583 return EV_DIR_GROWS
;
1586 /* Iterates over all the components of SCEV, and calls CBCK. */
1589 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1591 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1594 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1598 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1602 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1611 /* Returns true when the operation can be part of a linear
1615 operator_is_linear (tree scev
)
1617 switch (TREE_CODE (scev
))
1620 case POLYNOMIAL_CHREC
:
1622 case POINTER_PLUS_EXPR
:
1627 case NON_LVALUE_EXPR
:
1637 /* Return true when SCEV is a linear expression. Linear expressions
1638 can contain additions, substractions and multiplications.
1639 Multiplications are restricted to constant scaling: "cst * x". */
1642 scev_is_linear_expression (tree scev
)
1644 if (evolution_function_is_constant_p (scev
))
1648 || !operator_is_linear (scev
))
1651 if (TREE_CODE (scev
) == MULT_EXPR
)
1652 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1653 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1655 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1656 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1659 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1662 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1663 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1664 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1667 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1668 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1671 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1681 /* Determines whether the expression CHREC contains only interger consts
1682 in the right parts. */
1685 evolution_function_right_is_integer_cst (const_tree chrec
)
1687 if (chrec
== NULL_TREE
)
1690 switch (TREE_CODE (chrec
))
1695 case POLYNOMIAL_CHREC
:
1696 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1697 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1698 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1701 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));