1 /* Chains of recurrences.
2 Copyright (C) 2003-2015 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"
34 #include "fold-const.h"
35 #include "tree-pretty-print.h"
39 #include "hard-reg-set.h"
42 #include "dominance.h"
44 #include "basic-block.h"
45 #include "gimple-expr.h"
46 #include "tree-ssa-loop-ivopts.h"
47 #include "tree-ssa-loop-niter.h"
48 #include "tree-chrec.h"
51 #include "tree-scalar-evolution.h"
53 /* Extended folder for chrecs. */
55 /* Determines whether CST is not a constant evolution. */
58 is_not_constant_evolution (const_tree cst
)
60 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
63 /* Fold CODE for a polynomial function and a constant. */
66 chrec_fold_poly_cst (enum tree_code code
,
73 gcc_assert (TREE_CODE (poly
) == POLYNOMIAL_CHREC
);
74 gcc_checking_assert (!is_not_constant_evolution (cst
));
75 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly
)));
80 return build_polynomial_chrec
81 (CHREC_VARIABLE (poly
),
82 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
86 return build_polynomial_chrec
87 (CHREC_VARIABLE (poly
),
88 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
92 return build_polynomial_chrec
93 (CHREC_VARIABLE (poly
),
94 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
95 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
98 return chrec_dont_know
;
102 /* Fold the addition of two polynomial functions. */
105 chrec_fold_plus_poly_poly (enum tree_code code
,
111 struct loop
*loop0
= get_chrec_loop (poly0
);
112 struct loop
*loop1
= get_chrec_loop (poly1
);
113 tree rtype
= code
== POINTER_PLUS_EXPR
? chrec_type (poly1
) : type
;
117 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
118 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
119 if (POINTER_TYPE_P (chrec_type (poly0
)))
120 gcc_checking_assert (ptrofftype_p (chrec_type (poly1
))
121 && useless_type_conversion_p (type
, chrec_type (poly0
)));
123 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
124 && useless_type_conversion_p (type
, chrec_type (poly1
)));
127 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
128 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
129 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
130 if (flow_loop_nested_p (loop0
, loop1
))
132 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
133 return build_polynomial_chrec
134 (CHREC_VARIABLE (poly1
),
135 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
136 CHREC_RIGHT (poly1
));
138 return build_polynomial_chrec
139 (CHREC_VARIABLE (poly1
),
140 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
141 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
142 SCALAR_FLOAT_TYPE_P (type
)
143 ? build_real (type
, dconstm1
)
144 : build_int_cst_type (type
, -1)));
147 if (flow_loop_nested_p (loop1
, loop0
))
149 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
150 return build_polynomial_chrec
151 (CHREC_VARIABLE (poly0
),
152 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
153 CHREC_RIGHT (poly0
));
155 return build_polynomial_chrec
156 (CHREC_VARIABLE (poly0
),
157 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
158 CHREC_RIGHT (poly0
));
161 /* This function should never be called for chrecs of loops that
162 do not belong to the same loop nest. */
163 gcc_assert (loop0
== loop1
);
165 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
167 left
= chrec_fold_plus
168 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
169 right
= chrec_fold_plus
170 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
174 left
= chrec_fold_minus
175 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
176 right
= chrec_fold_minus
177 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
180 if (chrec_zerop (right
))
183 return build_polynomial_chrec
184 (CHREC_VARIABLE (poly0
), left
, right
);
189 /* Fold the multiplication of two polynomial functions. */
192 chrec_fold_multiply_poly_poly (tree type
,
198 struct loop
*loop0
= get_chrec_loop (poly0
);
199 struct loop
*loop1
= get_chrec_loop (poly1
);
203 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
204 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
205 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
206 && useless_type_conversion_p (type
, chrec_type (poly1
)));
208 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
209 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
210 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
211 if (flow_loop_nested_p (loop0
, loop1
))
212 /* poly0 is a constant wrt. poly1. */
213 return build_polynomial_chrec
214 (CHREC_VARIABLE (poly1
),
215 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
216 CHREC_RIGHT (poly1
));
218 if (flow_loop_nested_p (loop1
, loop0
))
219 /* poly1 is a constant wrt. poly0. */
220 return build_polynomial_chrec
221 (CHREC_VARIABLE (poly0
),
222 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
223 CHREC_RIGHT (poly0
));
225 gcc_assert (loop0
== loop1
);
227 /* poly0 and poly1 are two polynomials in the same variable,
228 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
231 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
234 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
235 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
237 CHREC_LEFT (poly1
)));
239 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
240 /* "a*d + b*c + b*d". */
241 t1
= chrec_fold_plus (type
, t1
, t2
);
243 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
244 ? build_real (type
, dconst2
)
245 : build_int_cst (type
, 2), t2
);
247 var
= CHREC_VARIABLE (poly0
);
248 return build_polynomial_chrec (var
, t0
,
249 build_polynomial_chrec (var
, t1
, t2
));
252 /* When the operands are automatically_generated_chrec_p, the fold has
253 to respect the semantics of the operands. */
256 chrec_fold_automatically_generated_operands (tree op0
,
259 if (op0
== chrec_dont_know
260 || op1
== chrec_dont_know
)
261 return chrec_dont_know
;
263 if (op0
== chrec_known
264 || op1
== chrec_known
)
267 if (op0
== chrec_not_analyzed_yet
268 || op1
== chrec_not_analyzed_yet
)
269 return chrec_not_analyzed_yet
;
271 /* The default case produces a safe result. */
272 return chrec_dont_know
;
275 /* Fold the addition of two chrecs. */
278 chrec_fold_plus_1 (enum tree_code code
, tree type
,
281 if (automatically_generated_chrec_p (op0
)
282 || automatically_generated_chrec_p (op1
))
283 return chrec_fold_automatically_generated_operands (op0
, op1
);
285 switch (TREE_CODE (op0
))
287 case POLYNOMIAL_CHREC
:
289 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
290 switch (TREE_CODE (op1
))
292 case POLYNOMIAL_CHREC
:
294 (!chrec_contains_symbols_defined_in_loop (op1
,
295 CHREC_VARIABLE (op1
)));
296 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
299 if (tree_contains_chrecs (op1
, NULL
))
300 return chrec_dont_know
;
303 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
304 return build_polynomial_chrec
305 (CHREC_VARIABLE (op0
),
306 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
309 return build_polynomial_chrec
310 (CHREC_VARIABLE (op0
),
311 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
316 if (tree_contains_chrecs (op0
, NULL
))
317 return chrec_dont_know
;
320 switch (TREE_CODE (op1
))
322 case POLYNOMIAL_CHREC
:
324 (!chrec_contains_symbols_defined_in_loop (op1
,
325 CHREC_VARIABLE (op1
)));
326 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
327 return build_polynomial_chrec
328 (CHREC_VARIABLE (op1
),
329 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
332 return build_polynomial_chrec
333 (CHREC_VARIABLE (op1
),
334 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
335 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
336 SCALAR_FLOAT_TYPE_P (type
)
337 ? build_real (type
, dconstm1
)
338 : build_int_cst_type (type
, -1)));
341 if (tree_contains_chrecs (op1
, NULL
))
342 return chrec_dont_know
;
347 if ((tree_contains_chrecs (op0
, &size
)
348 || tree_contains_chrecs (op1
, &size
))
349 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
350 return build2 (code
, type
, op0
, op1
);
351 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
353 if (code
== POINTER_PLUS_EXPR
)
354 return fold_build_pointer_plus (fold_convert (type
, op0
),
357 return fold_build2 (code
, type
,
358 fold_convert (type
, op0
),
359 fold_convert (type
, op1
));
362 return chrec_dont_know
;
368 /* Fold the addition of two chrecs. */
371 chrec_fold_plus (tree type
,
376 if (automatically_generated_chrec_p (op0
)
377 || automatically_generated_chrec_p (op1
))
378 return chrec_fold_automatically_generated_operands (op0
, op1
);
380 if (integer_zerop (op0
))
381 return chrec_convert (type
, op1
, NULL
);
382 if (integer_zerop (op1
))
383 return chrec_convert (type
, op0
, NULL
);
385 if (POINTER_TYPE_P (type
))
386 code
= POINTER_PLUS_EXPR
;
390 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
393 /* Fold the subtraction of two chrecs. */
396 chrec_fold_minus (tree type
,
400 if (automatically_generated_chrec_p (op0
)
401 || automatically_generated_chrec_p (op1
))
402 return chrec_fold_automatically_generated_operands (op0
, op1
);
404 if (integer_zerop (op1
))
407 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
410 /* Fold the multiplication of two chrecs. */
413 chrec_fold_multiply (tree type
,
417 if (automatically_generated_chrec_p (op0
)
418 || automatically_generated_chrec_p (op1
))
419 return chrec_fold_automatically_generated_operands (op0
, op1
);
421 switch (TREE_CODE (op0
))
423 case POLYNOMIAL_CHREC
:
425 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
426 switch (TREE_CODE (op1
))
428 case POLYNOMIAL_CHREC
:
430 (!chrec_contains_symbols_defined_in_loop (op1
,
431 CHREC_VARIABLE (op1
)));
432 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
435 if (tree_contains_chrecs (op1
, NULL
))
436 return chrec_dont_know
;
439 if (integer_onep (op1
))
441 if (integer_zerop (op1
))
442 return build_int_cst (type
, 0);
444 return build_polynomial_chrec
445 (CHREC_VARIABLE (op0
),
446 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
447 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
451 if (tree_contains_chrecs (op0
, NULL
))
452 return chrec_dont_know
;
455 if (integer_onep (op0
))
458 if (integer_zerop (op0
))
459 return build_int_cst (type
, 0);
461 switch (TREE_CODE (op1
))
463 case POLYNOMIAL_CHREC
:
465 (!chrec_contains_symbols_defined_in_loop (op1
,
466 CHREC_VARIABLE (op1
)));
467 return build_polynomial_chrec
468 (CHREC_VARIABLE (op1
),
469 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
470 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
473 if (tree_contains_chrecs (op1
, NULL
))
474 return chrec_dont_know
;
477 if (integer_onep (op1
))
479 if (integer_zerop (op1
))
480 return build_int_cst (type
, 0);
481 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
490 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
491 calculation overflows, otherwise return C(n,k) with type TYPE. */
494 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
500 /* Handle the most frequent cases. */
502 return build_int_cst (type
, 1);
504 return fold_convert (type
, n
);
506 /* Check that k <= n. */
507 if (wi::ltu_p (n
, k
))
510 /* Denominator = 2. */
511 wide_int denom
= wi::two (TYPE_PRECISION (TREE_TYPE (n
)));
513 /* Index = Numerator-1. */
514 wide_int idx
= wi::sub (n
, 1);
516 /* Numerator = Numerator*Index = n*(n-1). */
517 wide_int num
= wi::smul (n
, idx
, &overflow
);
521 for (i
= 3; i
<= k
; i
++)
526 /* Numerator *= Index. */
527 num
= wi::smul (num
, idx
, &overflow
);
531 /* Denominator *= i. */
535 /* Result = Numerator / Denominator. */
536 wide_int di_res
= wi::udiv_trunc (num
, denom
);
537 res
= wide_int_to_tree (type
, di_res
);
538 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
541 /* Helper function. Use the Newton's interpolating formula for
542 evaluating the value of the evolution function. */
545 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
547 tree arg0
, arg1
, binomial_n_k
;
548 tree type
= TREE_TYPE (chrec
);
549 struct loop
*var_loop
= get_loop (cfun
, var
);
551 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
552 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
553 chrec
= CHREC_LEFT (chrec
);
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 (type
, n
, k
);
563 return chrec_dont_know
;
564 arg0
= fold_build2 (MULT_EXPR
, type
,
565 CHREC_LEFT (chrec
), binomial_n_k
);
566 return chrec_fold_plus (type
, arg0
, arg1
);
569 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
571 return chrec_dont_know
;
573 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
576 /* Evaluates "CHREC (X)" when the varying variable is VAR.
577 Example: Given the following parameters,
583 The result is given by the Newton's interpolating formula:
584 3 * \binom{10}{0} + 4 * \binom{10}{1}.
588 chrec_apply (unsigned var
,
592 tree type
= chrec_type (chrec
);
593 tree res
= chrec_dont_know
;
595 if (automatically_generated_chrec_p (chrec
)
596 || automatically_generated_chrec_p (x
)
598 /* When the symbols are defined in an outer loop, it is possible
599 to symbolically compute the apply, since the symbols are
600 constants with respect to the varying loop. */
601 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
602 return chrec_dont_know
;
604 if (dump_file
&& (dump_flags
& TDF_SCEV
))
605 fprintf (dump_file
, "(chrec_apply \n");
607 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
608 x
= build_real_from_int_cst (type
, x
);
610 switch (TREE_CODE (chrec
))
612 case POLYNOMIAL_CHREC
:
613 if (evolution_function_is_affine_p (chrec
))
615 if (CHREC_VARIABLE (chrec
) != var
)
616 return build_polynomial_chrec
617 (CHREC_VARIABLE (chrec
),
618 chrec_apply (var
, CHREC_LEFT (chrec
), x
),
619 chrec_apply (var
, CHREC_RIGHT (chrec
), x
));
621 /* "{a, +, b} (x)" -> "a + b*x". */
622 x
= chrec_convert_rhs (type
, x
, NULL
);
623 res
= chrec_fold_multiply (TREE_TYPE (x
), CHREC_RIGHT (chrec
), x
);
624 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
626 else if (TREE_CODE (x
) == INTEGER_CST
627 && tree_int_cst_sgn (x
) == 1)
628 /* testsuite/.../ssa-chrec-38.c. */
629 res
= chrec_evaluate (var
, chrec
, x
, 0);
631 res
= chrec_dont_know
;
635 res
= chrec_convert (TREE_TYPE (chrec
),
636 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
645 if (dump_file
&& (dump_flags
& TDF_SCEV
))
647 fprintf (dump_file
, " (varying_loop = %d\n", var
);
648 fprintf (dump_file
, ")\n (chrec = ");
649 print_generic_expr (dump_file
, chrec
, 0);
650 fprintf (dump_file
, ")\n (x = ");
651 print_generic_expr (dump_file
, x
, 0);
652 fprintf (dump_file
, ")\n (res = ");
653 print_generic_expr (dump_file
, res
, 0);
654 fprintf (dump_file
, "))\n");
660 /* For a given CHREC and an induction variable map IV_MAP that maps
661 (loop->num, expr) for every loop number of the current_loops an
662 expression, calls chrec_apply when the expression is not NULL. */
665 chrec_apply_map (tree chrec
, vec
<tree
> iv_map
)
670 FOR_EACH_VEC_ELT (iv_map
, i
, expr
)
672 chrec
= chrec_apply (i
, chrec
, expr
);
677 /* Replaces the initial condition in CHREC with INIT_COND. */
680 chrec_replace_initial_condition (tree chrec
,
683 if (automatically_generated_chrec_p (chrec
))
686 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
688 switch (TREE_CODE (chrec
))
690 case POLYNOMIAL_CHREC
:
691 return build_polynomial_chrec
692 (CHREC_VARIABLE (chrec
),
693 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
694 CHREC_RIGHT (chrec
));
701 /* Returns the initial condition of a given CHREC. */
704 initial_condition (tree chrec
)
706 if (automatically_generated_chrec_p (chrec
))
709 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
710 return initial_condition (CHREC_LEFT (chrec
));
715 /* Returns a univariate function that represents the evolution in
716 LOOP_NUM. Mask the evolution of any other loop. */
719 hide_evolution_in_other_loops_than_loop (tree chrec
,
722 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
723 if (automatically_generated_chrec_p (chrec
))
726 switch (TREE_CODE (chrec
))
728 case POLYNOMIAL_CHREC
:
729 chloop
= get_chrec_loop (chrec
);
732 return build_polynomial_chrec
734 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
736 CHREC_RIGHT (chrec
));
738 else if (flow_loop_nested_p (chloop
, loop
))
739 /* There is no evolution in this loop. */
740 return initial_condition (chrec
);
744 gcc_assert (flow_loop_nested_p (loop
, chloop
));
745 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
754 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
755 true, otherwise returns the initial condition in LOOP_NUM. */
758 chrec_component_in_loop_num (tree chrec
,
763 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
765 if (automatically_generated_chrec_p (chrec
))
768 switch (TREE_CODE (chrec
))
770 case POLYNOMIAL_CHREC
:
771 chloop
= get_chrec_loop (chrec
);
776 component
= CHREC_RIGHT (chrec
);
778 component
= CHREC_LEFT (chrec
);
780 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
781 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
785 return build_polynomial_chrec
787 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
793 else if (flow_loop_nested_p (chloop
, loop
))
794 /* There is no evolution part in this loop. */
799 gcc_assert (flow_loop_nested_p (loop
, chloop
));
800 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
813 /* Returns the evolution part in LOOP_NUM. Example: the call
814 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
818 evolution_part_in_loop_num (tree chrec
,
821 return chrec_component_in_loop_num (chrec
, loop_num
, true);
824 /* Returns the initial condition in LOOP_NUM. Example: the call
825 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
829 initial_condition_in_loop_num (tree chrec
,
832 return chrec_component_in_loop_num (chrec
, loop_num
, false);
835 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
836 This function is essentially used for setting the evolution to
837 chrec_dont_know, for example after having determined that it is
838 impossible to say how many times a loop will execute. */
841 reset_evolution_in_loop (unsigned loop_num
,
845 struct loop
*loop
= get_loop (cfun
, loop_num
);
847 if (POINTER_TYPE_P (chrec_type (chrec
)))
848 gcc_assert (ptrofftype_p (chrec_type (new_evol
)));
850 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
852 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
853 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
855 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
857 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
859 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
860 CHREC_VAR (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. */
940 chrec_contains_symbols (const_tree chrec
)
944 if (chrec
== NULL_TREE
)
947 if (TREE_CODE (chrec
) == SSA_NAME
948 || TREE_CODE (chrec
) == VAR_DECL
949 || TREE_CODE (chrec
) == PARM_DECL
950 || TREE_CODE (chrec
) == FUNCTION_DECL
951 || TREE_CODE (chrec
) == LABEL_DECL
952 || TREE_CODE (chrec
) == RESULT_DECL
953 || TREE_CODE (chrec
) == FIELD_DECL
)
956 n
= TREE_OPERAND_LENGTH (chrec
);
957 for (i
= 0; i
< n
; i
++)
958 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
)))
963 /* Determines whether the chrec contains undetermined coefficients. */
966 chrec_contains_undetermined (const_tree chrec
)
970 if (chrec
== chrec_dont_know
)
973 if (chrec
== NULL_TREE
)
976 n
= TREE_OPERAND_LENGTH (chrec
);
977 for (i
= 0; i
< n
; i
++)
978 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
)))
983 /* Determines whether the tree EXPR contains chrecs, and increment
984 SIZE if it is not a NULL pointer by an estimation of the depth of
988 tree_contains_chrecs (const_tree expr
, int *size
)
992 if (expr
== NULL_TREE
)
998 if (tree_is_chrec (expr
))
1001 n
= TREE_OPERAND_LENGTH (expr
);
1002 for (i
= 0; i
< n
; i
++)
1003 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
))
1008 /* Recursive helper function. */
1011 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1013 if (evolution_function_is_constant_p (chrec
))
1016 if (TREE_CODE (chrec
) == SSA_NAME
1018 || expr_invariant_in_loop_p (get_loop (cfun
, loopnum
), chrec
)))
1021 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1023 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
1024 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1025 get_chrec_loop (chrec
))
1026 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
1028 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
1034 switch (TREE_OPERAND_LENGTH (chrec
))
1037 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
1042 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1054 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1057 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1059 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1062 /* Determine whether the given tree is an affine multivariate
1066 evolution_function_is_affine_multivariate_p (const_tree chrec
, int loopnum
)
1068 if (chrec
== NULL_TREE
)
1071 switch (TREE_CODE (chrec
))
1073 case POLYNOMIAL_CHREC
:
1074 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
), loopnum
))
1076 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
))
1080 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1081 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1082 != CHREC_VARIABLE (chrec
)
1083 && evolution_function_is_affine_multivariate_p
1084 (CHREC_RIGHT (chrec
), loopnum
))
1092 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
)
1093 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1094 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1095 && evolution_function_is_affine_multivariate_p
1096 (CHREC_LEFT (chrec
), loopnum
))
1107 /* Determine whether the given tree is a function in zero or one
1111 evolution_function_is_univariate_p (const_tree chrec
)
1113 if (chrec
== NULL_TREE
)
1116 switch (TREE_CODE (chrec
))
1118 case POLYNOMIAL_CHREC
:
1119 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1121 case POLYNOMIAL_CHREC
:
1122 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1124 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1129 if (tree_contains_chrecs (CHREC_LEFT (chrec
), NULL
))
1134 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1136 case POLYNOMIAL_CHREC
:
1137 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1139 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1144 if (tree_contains_chrecs (CHREC_RIGHT (chrec
), NULL
))
1154 /* Returns the number of variables of CHREC. Example: the call
1155 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1158 nb_vars_in_chrec (tree chrec
)
1160 if (chrec
== NULL_TREE
)
1163 switch (TREE_CODE (chrec
))
1165 case POLYNOMIAL_CHREC
:
1166 return 1 + nb_vars_in_chrec
1167 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1174 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1175 the scev corresponds to. AT_STMT is the statement at that the scev is
1176 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1177 the rules for overflow of the given language apply (e.g., that signed
1178 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1179 tests, but also to enforce that the result follows them. Returns true if the
1180 conversion succeeded, false otherwise. */
1183 convert_affine_scev (struct loop
*loop
, tree type
,
1184 tree
*base
, tree
*step
, gimple at_stmt
,
1185 bool use_overflow_semantics
)
1187 tree ct
= TREE_TYPE (*step
);
1188 bool enforce_overflow_semantics
;
1189 bool must_check_src_overflow
, must_check_rslt_overflow
;
1190 tree new_base
, new_step
;
1191 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1194 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1195 but we must check some assumptions.
1197 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1198 of CT is smaller than the precision of TYPE. For example, when we
1199 cast unsigned char [254, +, 1] to unsigned, the values on left side
1200 are 254, 255, 0, 1, ..., but those on the right side are
1201 254, 255, 256, 257, ...
1202 2) In case that we must also preserve the fact that signed ivs do not
1203 overflow, we must additionally check that the new iv does not wrap.
1204 For example, unsigned char [125, +, 1] casted to signed char could
1205 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1206 which would confuse optimizers that assume that this does not
1208 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1210 enforce_overflow_semantics
= (use_overflow_semantics
1211 && nowrap_type_p (type
));
1212 if (enforce_overflow_semantics
)
1214 /* We can avoid checking whether the result overflows in the following
1217 -- must_check_src_overflow is true, and the range of TYPE is superset
1218 of the range of CT -- i.e., in all cases except if CT signed and
1220 -- both CT and TYPE have the same precision and signedness, and we
1221 verify instead that the source does not overflow (this may be
1222 easier than verifying it for the result, as we may use the
1223 information about the semantics of overflow in CT). */
1224 if (must_check_src_overflow
)
1226 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1227 must_check_rslt_overflow
= true;
1229 must_check_rslt_overflow
= false;
1231 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1232 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1234 must_check_rslt_overflow
= false;
1235 must_check_src_overflow
= true;
1238 must_check_rslt_overflow
= true;
1241 must_check_rslt_overflow
= false;
1243 if (must_check_src_overflow
1244 && scev_probably_wraps_p (*base
, *step
, at_stmt
, loop
,
1245 use_overflow_semantics
))
1248 new_base
= chrec_convert (type
, *base
, at_stmt
, use_overflow_semantics
);
1249 /* The step must be sign extended, regardless of the signedness
1250 of CT and TYPE. This only needs to be handled specially when
1251 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1252 (with values 100, 99, 98, ...) from becoming signed or unsigned
1253 [100, +, 255] with values 100, 355, ...; the sign-extension is
1254 performed by default when CT is signed. */
1256 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1258 tree signed_ct
= build_nonstandard_integer_type (TYPE_PRECISION (ct
), 0);
1259 new_step
= chrec_convert (signed_ct
, new_step
, at_stmt
,
1260 use_overflow_semantics
);
1262 new_step
= chrec_convert (step_type
, new_step
, at_stmt
,
1263 use_overflow_semantics
);
1265 if (automatically_generated_chrec_p (new_base
)
1266 || automatically_generated_chrec_p (new_step
))
1269 if (must_check_rslt_overflow
1270 /* Note that in this case we cannot use the fact that signed variables
1271 do not overflow, as this is what we are verifying for the new iv. */
1272 && scev_probably_wraps_p (new_base
, new_step
, at_stmt
, loop
, false))
1281 /* Convert CHREC for the right hand side of a CHREC.
1282 The increment for a pointer type is always sizetype. */
1285 chrec_convert_rhs (tree type
, tree chrec
, gimple at_stmt
)
1287 if (POINTER_TYPE_P (type
))
1290 return chrec_convert (type
, chrec
, at_stmt
);
1293 /* Convert CHREC to TYPE. When the analyzer knows the context in
1294 which the CHREC is built, it sets AT_STMT to the statement that
1295 contains the definition of the analyzed variable, otherwise the
1296 conversion is less accurate: the information is used for
1297 determining a more accurate estimation of the number of iterations.
1298 By default AT_STMT could be safely set to NULL_TREE.
1300 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1301 the rules for overflow of the given language apply (e.g., that signed
1302 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1303 tests, but also to enforce that the result follows them. */
1306 chrec_convert_1 (tree type
, tree chrec
, gimple at_stmt
,
1307 bool use_overflow_semantics
)
1313 if (automatically_generated_chrec_p (chrec
))
1316 ct
= chrec_type (chrec
);
1317 if (useless_type_conversion_p (type
, ct
))
1320 if (!evolution_function_is_affine_p (chrec
))
1323 loop
= get_chrec_loop (chrec
);
1324 base
= CHREC_LEFT (chrec
);
1325 step
= CHREC_RIGHT (chrec
);
1327 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1328 use_overflow_semantics
))
1329 return build_polynomial_chrec (loop
->num
, base
, step
);
1331 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1333 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1334 may be more expensive. We do want to perform this optimization here
1335 though for canonicalization reasons. */
1336 if (use_overflow_semantics
1337 && (TREE_CODE (chrec
) == PLUS_EXPR
1338 || TREE_CODE (chrec
) == MINUS_EXPR
)
1339 && TREE_CODE (type
) == INTEGER_TYPE
1340 && TREE_CODE (ct
) == INTEGER_TYPE
1341 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1342 && TYPE_OVERFLOW_UNDEFINED (ct
))
1343 res
= fold_build2 (TREE_CODE (chrec
), type
,
1344 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1345 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1346 /* Similar perform the trick that (signed char)((int)x + 2) can be
1347 narrowed to (signed char)((unsigned char)x + 2). */
1348 else if (use_overflow_semantics
1349 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1350 && TREE_CODE (ct
) == INTEGER_TYPE
1351 && TREE_CODE (type
) == INTEGER_TYPE
1352 && TYPE_OVERFLOW_UNDEFINED (type
)
1353 && TYPE_PRECISION (type
) < TYPE_PRECISION (ct
))
1355 tree utype
= unsigned_type_for (type
);
1356 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1357 fold_convert (utype
,
1358 CHREC_LEFT (chrec
)),
1359 fold_convert (utype
,
1360 CHREC_RIGHT (chrec
)));
1361 res
= chrec_convert_1 (type
, res
, at_stmt
, use_overflow_semantics
);
1364 res
= fold_convert (type
, chrec
);
1366 /* Don't propagate overflows. */
1367 if (CONSTANT_CLASS_P (res
))
1368 TREE_OVERFLOW (res
) = 0;
1370 /* But reject constants that don't fit in their type after conversion.
1371 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1372 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1373 and can cause problems later when computing niters of loops. Note
1374 that we don't do the check before converting because we don't want
1375 to reject conversions of negative chrecs to unsigned types. */
1376 if (TREE_CODE (res
) == INTEGER_CST
1377 && TREE_CODE (type
) == INTEGER_TYPE
1378 && !int_fits_type_p (res
, type
))
1379 res
= chrec_dont_know
;
1384 /* Convert CHREC to TYPE. When the analyzer knows the context in
1385 which the CHREC is built, it sets AT_STMT to the statement that
1386 contains the definition of the analyzed variable, otherwise the
1387 conversion is less accurate: the information is used for
1388 determining a more accurate estimation of the number of iterations.
1389 By default AT_STMT could be safely set to NULL_TREE.
1391 The following rule is always true: TREE_TYPE (chrec) ==
1392 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1393 An example of what could happen when adding two chrecs and the type
1394 of the CHREC_RIGHT is different than CHREC_LEFT is:
1396 {(uint) 0, +, (uchar) 10} +
1397 {(uint) 0, +, (uchar) 250}
1399 that would produce a wrong result if CHREC_RIGHT is not (uint):
1401 {(uint) 0, +, (uchar) 4}
1405 {(uint) 0, +, (uint) 260}
1407 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1408 the rules for overflow of the given language apply (e.g., that signed
1409 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1410 tests, but also to enforce that the result follows them. */
1413 chrec_convert (tree type
, tree chrec
, gimple at_stmt
,
1414 bool use_overflow_semantics
)
1416 return chrec_convert_1 (type
, chrec
, at_stmt
, use_overflow_semantics
);
1419 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1420 chrec if something else than what chrec_convert would do happens, NULL_TREE
1421 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1422 if the result chrec may overflow. */
1425 chrec_convert_aggressive (tree type
, tree chrec
, bool *fold_conversions
)
1427 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1429 gcc_assert (fold_conversions
!= NULL
);
1431 if (automatically_generated_chrec_p (chrec
)
1432 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1435 inner_type
= TREE_TYPE (chrec
);
1436 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1439 if (useless_type_conversion_p (type
, inner_type
))
1442 if (!*fold_conversions
&& evolution_function_is_affine_p (chrec
))
1447 loop
= get_chrec_loop (chrec
);
1448 base
= CHREC_LEFT (chrec
);
1449 step
= CHREC_RIGHT (chrec
);
1450 if (convert_affine_scev (loop
, type
, &base
, &step
, NULL
, true))
1451 return build_polynomial_chrec (loop
->num
, base
, step
);
1453 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1455 left
= CHREC_LEFT (chrec
);
1456 right
= CHREC_RIGHT (chrec
);
1457 lc
= chrec_convert_aggressive (type
, left
, fold_conversions
);
1459 lc
= chrec_convert (type
, left
, NULL
);
1460 rc
= chrec_convert_aggressive (rtype
, right
, fold_conversions
);
1462 rc
= chrec_convert (rtype
, right
, NULL
);
1464 *fold_conversions
= true;
1466 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1469 /* Returns true when CHREC0 == CHREC1. */
1472 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1474 if (chrec0
== NULL_TREE
1475 || chrec1
== NULL_TREE
1476 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1479 if (chrec0
== chrec1
)
1482 switch (TREE_CODE (chrec0
))
1485 return operand_equal_p (chrec0
, chrec1
, 0);
1487 case POLYNOMIAL_CHREC
:
1488 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1489 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1490 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1495 case POINTER_PLUS_EXPR
:
1496 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1497 TREE_OPERAND (chrec1
, 0))
1498 && eq_evolutions_p (TREE_OPERAND (chrec0
, 1),
1499 TREE_OPERAND (chrec1
, 1));
1506 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1507 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1508 which of these cases happens. */
1511 scev_direction (const_tree chrec
)
1515 if (!evolution_function_is_affine_p (chrec
))
1516 return EV_DIR_UNKNOWN
;
1518 step
= CHREC_RIGHT (chrec
);
1519 if (TREE_CODE (step
) != INTEGER_CST
)
1520 return EV_DIR_UNKNOWN
;
1522 if (tree_int_cst_sign_bit (step
))
1523 return EV_DIR_DECREASES
;
1525 return EV_DIR_GROWS
;
1528 /* Iterates over all the components of SCEV, and calls CBCK. */
1531 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1533 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1536 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1539 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1542 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1550 /* Returns true when the operation can be part of a linear
1554 operator_is_linear (tree scev
)
1556 switch (TREE_CODE (scev
))
1559 case POLYNOMIAL_CHREC
:
1561 case POINTER_PLUS_EXPR
:
1566 case NON_LVALUE_EXPR
:
1576 /* Return true when SCEV is a linear expression. Linear expressions
1577 can contain additions, substractions and multiplications.
1578 Multiplications are restricted to constant scaling: "cst * x". */
1581 scev_is_linear_expression (tree scev
)
1584 || !operator_is_linear (scev
))
1587 if (TREE_CODE (scev
) == MULT_EXPR
)
1588 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1589 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1591 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1592 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1595 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1598 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1599 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1600 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1603 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1604 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1607 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1617 /* Determines whether the expression CHREC contains only interger consts
1618 in the right parts. */
1621 evolution_function_right_is_integer_cst (const_tree chrec
)
1623 if (chrec
== NULL_TREE
)
1626 switch (TREE_CODE (chrec
))
1631 case POLYNOMIAL_CHREC
:
1632 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1633 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1634 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1637 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));