1 /* Chains of recurrences.
2 Copyright (C) 2003-2016 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. */
152 gcc_assert (loop0
== loop1
);
154 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
156 left
= chrec_fold_plus
157 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
158 right
= chrec_fold_plus
159 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
163 left
= chrec_fold_minus
164 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
165 right
= chrec_fold_minus
166 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
169 if (chrec_zerop (right
))
172 return build_polynomial_chrec
173 (CHREC_VARIABLE (poly0
), left
, right
);
178 /* Fold the multiplication of two polynomial functions. */
181 chrec_fold_multiply_poly_poly (tree type
,
187 struct loop
*loop0
= get_chrec_loop (poly0
);
188 struct loop
*loop1
= get_chrec_loop (poly1
);
192 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
193 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
194 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
195 && useless_type_conversion_p (type
, chrec_type (poly1
)));
197 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
198 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
199 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
200 if (flow_loop_nested_p (loop0
, loop1
))
201 /* poly0 is a constant wrt. poly1. */
202 return build_polynomial_chrec
203 (CHREC_VARIABLE (poly1
),
204 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
205 CHREC_RIGHT (poly1
));
207 if (flow_loop_nested_p (loop1
, loop0
))
208 /* poly1 is a constant wrt. poly0. */
209 return build_polynomial_chrec
210 (CHREC_VARIABLE (poly0
),
211 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
212 CHREC_RIGHT (poly0
));
214 gcc_assert (loop0
== loop1
);
216 /* poly0 and poly1 are two polynomials in the same variable,
217 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
220 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
223 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
224 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
226 CHREC_LEFT (poly1
)));
228 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
229 /* "a*d + b*c + b*d". */
230 t1
= chrec_fold_plus (type
, t1
, t2
);
232 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
233 ? build_real (type
, dconst2
)
234 : build_int_cst (type
, 2), t2
);
236 var
= CHREC_VARIABLE (poly0
);
237 return build_polynomial_chrec (var
, t0
,
238 build_polynomial_chrec (var
, t1
, t2
));
241 /* When the operands are automatically_generated_chrec_p, the fold has
242 to respect the semantics of the operands. */
245 chrec_fold_automatically_generated_operands (tree op0
,
248 if (op0
== chrec_dont_know
249 || op1
== chrec_dont_know
)
250 return chrec_dont_know
;
252 if (op0
== chrec_known
253 || op1
== chrec_known
)
256 if (op0
== chrec_not_analyzed_yet
257 || op1
== chrec_not_analyzed_yet
)
258 return chrec_not_analyzed_yet
;
260 /* The default case produces a safe result. */
261 return chrec_dont_know
;
264 /* Fold the addition of two chrecs. */
267 chrec_fold_plus_1 (enum tree_code code
, tree type
,
270 if (automatically_generated_chrec_p (op0
)
271 || automatically_generated_chrec_p (op1
))
272 return chrec_fold_automatically_generated_operands (op0
, op1
);
274 switch (TREE_CODE (op0
))
276 case POLYNOMIAL_CHREC
:
278 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
279 switch (TREE_CODE (op1
))
281 case POLYNOMIAL_CHREC
:
283 (!chrec_contains_symbols_defined_in_loop (op1
,
284 CHREC_VARIABLE (op1
)));
285 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
288 if (tree_contains_chrecs (op1
, NULL
))
289 return chrec_dont_know
;
292 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
293 return build_polynomial_chrec
294 (CHREC_VARIABLE (op0
),
295 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
298 return build_polynomial_chrec
299 (CHREC_VARIABLE (op0
),
300 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
305 if (tree_contains_chrecs (op0
, NULL
))
306 return chrec_dont_know
;
309 switch (TREE_CODE (op1
))
311 case POLYNOMIAL_CHREC
:
313 (!chrec_contains_symbols_defined_in_loop (op1
,
314 CHREC_VARIABLE (op1
)));
315 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
316 return build_polynomial_chrec
317 (CHREC_VARIABLE (op1
),
318 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
321 return build_polynomial_chrec
322 (CHREC_VARIABLE (op1
),
323 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
324 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
325 SCALAR_FLOAT_TYPE_P (type
)
326 ? build_real (type
, dconstm1
)
327 : build_int_cst_type (type
, -1)));
330 if (tree_contains_chrecs (op1
, NULL
))
331 return chrec_dont_know
;
336 if ((tree_contains_chrecs (op0
, &size
)
337 || tree_contains_chrecs (op1
, &size
))
338 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
339 return build2 (code
, type
, op0
, op1
);
340 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
342 if (code
== POINTER_PLUS_EXPR
)
343 return fold_build_pointer_plus (fold_convert (type
, op0
),
346 return fold_build2 (code
, type
,
347 fold_convert (type
, op0
),
348 fold_convert (type
, op1
));
351 return chrec_dont_know
;
357 /* Fold the addition of two chrecs. */
360 chrec_fold_plus (tree type
,
365 if (automatically_generated_chrec_p (op0
)
366 || automatically_generated_chrec_p (op1
))
367 return chrec_fold_automatically_generated_operands (op0
, op1
);
369 if (integer_zerop (op0
))
370 return chrec_convert (type
, op1
, NULL
);
371 if (integer_zerop (op1
))
372 return chrec_convert (type
, op0
, NULL
);
374 if (POINTER_TYPE_P (type
))
375 code
= POINTER_PLUS_EXPR
;
379 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
382 /* Fold the subtraction of two chrecs. */
385 chrec_fold_minus (tree type
,
389 if (automatically_generated_chrec_p (op0
)
390 || automatically_generated_chrec_p (op1
))
391 return chrec_fold_automatically_generated_operands (op0
, op1
);
393 if (integer_zerop (op1
))
396 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
399 /* Fold the multiplication of two chrecs. */
402 chrec_fold_multiply (tree type
,
406 if (automatically_generated_chrec_p (op0
)
407 || automatically_generated_chrec_p (op1
))
408 return chrec_fold_automatically_generated_operands (op0
, op1
);
410 switch (TREE_CODE (op0
))
412 case POLYNOMIAL_CHREC
:
414 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
415 switch (TREE_CODE (op1
))
417 case POLYNOMIAL_CHREC
:
419 (!chrec_contains_symbols_defined_in_loop (op1
,
420 CHREC_VARIABLE (op1
)));
421 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
424 if (tree_contains_chrecs (op1
, NULL
))
425 return chrec_dont_know
;
428 if (integer_onep (op1
))
430 if (integer_zerop (op1
))
431 return build_int_cst (type
, 0);
433 return build_polynomial_chrec
434 (CHREC_VARIABLE (op0
),
435 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
436 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
440 if (tree_contains_chrecs (op0
, NULL
))
441 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
;
466 if (integer_onep (op1
))
468 if (integer_zerop (op1
))
469 return build_int_cst (type
, 0);
470 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
479 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
480 calculation overflows, otherwise return C(n,k) with type TYPE. */
483 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
488 /* Handle the most frequent cases. */
490 return build_int_cst (type
, 1);
492 return fold_convert (type
, n
);
494 widest_int num
= wi::to_widest (n
);
496 /* Check that k <= n. */
497 if (wi::ltu_p (num
, k
))
500 /* Denominator = 2. */
501 widest_int denom
= 2;
503 /* Index = Numerator-1. */
504 widest_int idx
= num
- 1;
506 /* Numerator = Numerator*Index = n*(n-1). */
507 num
= wi::smul (num
, idx
, &overflow
);
511 for (i
= 3; i
<= k
; i
++)
516 /* Numerator *= Index. */
517 num
= wi::smul (num
, idx
, &overflow
);
521 /* Denominator *= i. */
525 /* Result = Numerator / Denominator. */
526 num
= wi::udiv_trunc (num
, denom
);
527 if (! wi::fits_to_tree_p (num
, type
))
529 return wide_int_to_tree (type
, num
);
532 /* Helper function. Use the Newton's interpolating formula for
533 evaluating the value of the evolution function. */
536 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
538 tree arg0
, arg1
, binomial_n_k
;
539 tree type
= TREE_TYPE (chrec
);
540 struct loop
*var_loop
= get_loop (cfun
, var
);
542 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
543 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
544 chrec
= CHREC_LEFT (chrec
);
546 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
547 && CHREC_VARIABLE (chrec
) == var
)
549 arg1
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
550 if (arg1
== chrec_dont_know
)
551 return chrec_dont_know
;
552 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
554 return chrec_dont_know
;
555 arg0
= fold_build2 (MULT_EXPR
, type
,
556 CHREC_LEFT (chrec
), binomial_n_k
);
557 return chrec_fold_plus (type
, arg0
, arg1
);
560 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
562 return chrec_dont_know
;
564 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
567 /* Evaluates "CHREC (X)" when the varying variable is VAR.
568 Example: Given the following parameters,
574 The result is given by the Newton's interpolating formula:
575 3 * \binom{10}{0} + 4 * \binom{10}{1}.
579 chrec_apply (unsigned var
,
583 tree type
= chrec_type (chrec
);
584 tree res
= chrec_dont_know
;
586 if (automatically_generated_chrec_p (chrec
)
587 || automatically_generated_chrec_p (x
)
589 /* When the symbols are defined in an outer loop, it is possible
590 to symbolically compute the apply, since the symbols are
591 constants with respect to the varying loop. */
592 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
593 return chrec_dont_know
;
595 if (dump_file
&& (dump_flags
& TDF_SCEV
))
596 fprintf (dump_file
, "(chrec_apply \n");
598 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
599 x
= build_real_from_int_cst (type
, x
);
601 switch (TREE_CODE (chrec
))
603 case POLYNOMIAL_CHREC
:
604 if (evolution_function_is_affine_p (chrec
))
606 if (CHREC_VARIABLE (chrec
) != var
)
607 return build_polynomial_chrec
608 (CHREC_VARIABLE (chrec
),
609 chrec_apply (var
, CHREC_LEFT (chrec
), x
),
610 chrec_apply (var
, CHREC_RIGHT (chrec
), x
));
612 /* "{a, +, b} (x)" -> "a + b*x". */
613 x
= chrec_convert_rhs (type
, x
, NULL
);
614 res
= chrec_fold_multiply (TREE_TYPE (x
), CHREC_RIGHT (chrec
), x
);
615 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
617 else if (TREE_CODE (x
) == INTEGER_CST
618 && tree_int_cst_sgn (x
) == 1)
619 /* testsuite/.../ssa-chrec-38.c. */
620 res
= chrec_evaluate (var
, chrec
, x
, 0);
622 res
= chrec_dont_know
;
626 res
= chrec_convert (TREE_TYPE (chrec
),
627 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
636 if (dump_file
&& (dump_flags
& TDF_SCEV
))
638 fprintf (dump_file
, " (varying_loop = %d\n", var
);
639 fprintf (dump_file
, ")\n (chrec = ");
640 print_generic_expr (dump_file
, chrec
, 0);
641 fprintf (dump_file
, ")\n (x = ");
642 print_generic_expr (dump_file
, x
, 0);
643 fprintf (dump_file
, ")\n (res = ");
644 print_generic_expr (dump_file
, res
, 0);
645 fprintf (dump_file
, "))\n");
651 /* For a given CHREC and an induction variable map IV_MAP that maps
652 (loop->num, expr) for every loop number of the current_loops an
653 expression, calls chrec_apply when the expression is not NULL. */
656 chrec_apply_map (tree chrec
, vec
<tree
> iv_map
)
661 FOR_EACH_VEC_ELT (iv_map
, i
, expr
)
663 chrec
= chrec_apply (i
, chrec
, expr
);
668 /* Replaces the initial condition in CHREC with INIT_COND. */
671 chrec_replace_initial_condition (tree chrec
,
674 if (automatically_generated_chrec_p (chrec
))
677 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
679 switch (TREE_CODE (chrec
))
681 case POLYNOMIAL_CHREC
:
682 return build_polynomial_chrec
683 (CHREC_VARIABLE (chrec
),
684 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
685 CHREC_RIGHT (chrec
));
692 /* Returns the initial condition of a given CHREC. */
695 initial_condition (tree chrec
)
697 if (automatically_generated_chrec_p (chrec
))
700 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
701 return initial_condition (CHREC_LEFT (chrec
));
706 /* Returns a univariate function that represents the evolution in
707 LOOP_NUM. Mask the evolution of any other loop. */
710 hide_evolution_in_other_loops_than_loop (tree chrec
,
713 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
714 if (automatically_generated_chrec_p (chrec
))
717 switch (TREE_CODE (chrec
))
719 case POLYNOMIAL_CHREC
:
720 chloop
= get_chrec_loop (chrec
);
723 return build_polynomial_chrec
725 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
727 CHREC_RIGHT (chrec
));
729 else if (flow_loop_nested_p (chloop
, loop
))
730 /* There is no evolution in this loop. */
731 return initial_condition (chrec
);
733 else if (flow_loop_nested_p (loop
, chloop
))
734 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
738 return chrec_dont_know
;
745 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
746 true, otherwise returns the initial condition in LOOP_NUM. */
749 chrec_component_in_loop_num (tree chrec
,
754 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
756 if (automatically_generated_chrec_p (chrec
))
759 switch (TREE_CODE (chrec
))
761 case POLYNOMIAL_CHREC
:
762 chloop
= get_chrec_loop (chrec
);
767 component
= CHREC_RIGHT (chrec
);
769 component
= CHREC_LEFT (chrec
);
771 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
772 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
776 return build_polynomial_chrec
778 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
784 else if (flow_loop_nested_p (chloop
, loop
))
785 /* There is no evolution part in this loop. */
790 gcc_assert (flow_loop_nested_p (loop
, chloop
));
791 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
804 /* Returns the evolution part in LOOP_NUM. Example: the call
805 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
809 evolution_part_in_loop_num (tree chrec
,
812 return chrec_component_in_loop_num (chrec
, loop_num
, true);
815 /* Returns the initial condition in LOOP_NUM. Example: the call
816 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
820 initial_condition_in_loop_num (tree chrec
,
823 return chrec_component_in_loop_num (chrec
, loop_num
, false);
826 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
827 This function is essentially used for setting the evolution to
828 chrec_dont_know, for example after having determined that it is
829 impossible to say how many times a loop will execute. */
832 reset_evolution_in_loop (unsigned loop_num
,
836 struct loop
*loop
= get_loop (cfun
, loop_num
);
838 if (POINTER_TYPE_P (chrec_type (chrec
)))
839 gcc_assert (ptrofftype_p (chrec_type (new_evol
)));
841 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
843 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
844 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
846 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
848 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
850 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
851 CHREC_VAR (chrec
), left
, right
);
854 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
855 && CHREC_VARIABLE (chrec
) == loop_num
)
856 chrec
= CHREC_LEFT (chrec
);
858 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
861 /* Merges two evolution functions that were found by following two
862 alternate paths of a conditional expression. */
865 chrec_merge (tree chrec1
,
868 if (chrec1
== chrec_dont_know
869 || chrec2
== chrec_dont_know
)
870 return chrec_dont_know
;
872 if (chrec1
== chrec_known
873 || chrec2
== chrec_known
)
876 if (chrec1
== chrec_not_analyzed_yet
)
878 if (chrec2
== chrec_not_analyzed_yet
)
881 if (eq_evolutions_p (chrec1
, chrec2
))
884 return chrec_dont_know
;
891 /* Helper function for is_multivariate_chrec. */
894 is_multivariate_chrec_rec (const_tree chrec
, unsigned int rec_var
)
896 if (chrec
== NULL_TREE
)
899 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
901 if (CHREC_VARIABLE (chrec
) != rec_var
)
904 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
905 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
911 /* Determine whether the given chrec is multivariate or not. */
914 is_multivariate_chrec (const_tree chrec
)
916 if (chrec
== NULL_TREE
)
919 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
920 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
921 CHREC_VARIABLE (chrec
))
922 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
923 CHREC_VARIABLE (chrec
)));
928 /* Determines whether the chrec contains symbolic names or not. */
931 chrec_contains_symbols (const_tree chrec
)
935 if (chrec
== NULL_TREE
)
938 if (TREE_CODE (chrec
) == SSA_NAME
939 || TREE_CODE (chrec
) == VAR_DECL
940 || TREE_CODE (chrec
) == PARM_DECL
941 || TREE_CODE (chrec
) == FUNCTION_DECL
942 || TREE_CODE (chrec
) == LABEL_DECL
943 || TREE_CODE (chrec
) == RESULT_DECL
944 || TREE_CODE (chrec
) == FIELD_DECL
)
947 n
= TREE_OPERAND_LENGTH (chrec
);
948 for (i
= 0; i
< n
; i
++)
949 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
)))
954 /* Determines whether the chrec contains undetermined coefficients. */
957 chrec_contains_undetermined (const_tree chrec
)
961 if (chrec
== chrec_dont_know
)
964 if (chrec
== NULL_TREE
)
967 n
= TREE_OPERAND_LENGTH (chrec
);
968 for (i
= 0; i
< n
; i
++)
969 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
)))
974 /* Determines whether the tree EXPR contains chrecs, and increment
975 SIZE if it is not a NULL pointer by an estimation of the depth of
979 tree_contains_chrecs (const_tree expr
, int *size
)
983 if (expr
== NULL_TREE
)
989 if (tree_is_chrec (expr
))
992 n
= TREE_OPERAND_LENGTH (expr
);
993 for (i
= 0; i
< n
; i
++)
994 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
))
999 /* Recursive helper function. */
1002 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1004 if (evolution_function_is_constant_p (chrec
))
1007 if (TREE_CODE (chrec
) == SSA_NAME
1009 || expr_invariant_in_loop_p (get_loop (cfun
, loopnum
), chrec
)))
1012 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1014 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
1015 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1016 get_chrec_loop (chrec
))
1017 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
1019 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
1025 switch (TREE_OPERAND_LENGTH (chrec
))
1028 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
1033 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1045 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1048 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1050 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1053 /* Determine whether the given tree is an affine multivariate
1057 evolution_function_is_affine_multivariate_p (const_tree chrec
, int loopnum
)
1059 if (chrec
== NULL_TREE
)
1062 switch (TREE_CODE (chrec
))
1064 case POLYNOMIAL_CHREC
:
1065 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
), loopnum
))
1067 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
))
1071 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1072 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1073 != CHREC_VARIABLE (chrec
)
1074 && evolution_function_is_affine_multivariate_p
1075 (CHREC_RIGHT (chrec
), loopnum
))
1083 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
)
1084 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1085 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1086 && evolution_function_is_affine_multivariate_p
1087 (CHREC_LEFT (chrec
), loopnum
))
1098 /* Determine whether the given tree is a function in zero or one
1102 evolution_function_is_univariate_p (const_tree chrec
)
1104 if (chrec
== NULL_TREE
)
1107 switch (TREE_CODE (chrec
))
1109 case POLYNOMIAL_CHREC
:
1110 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1112 case POLYNOMIAL_CHREC
:
1113 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1115 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1120 if (tree_contains_chrecs (CHREC_LEFT (chrec
), NULL
))
1125 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1127 case POLYNOMIAL_CHREC
:
1128 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1130 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1135 if (tree_contains_chrecs (CHREC_RIGHT (chrec
), NULL
))
1145 /* Returns the number of variables of CHREC. Example: the call
1146 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1149 nb_vars_in_chrec (tree chrec
)
1151 if (chrec
== NULL_TREE
)
1154 switch (TREE_CODE (chrec
))
1156 case POLYNOMIAL_CHREC
:
1157 return 1 + nb_vars_in_chrec
1158 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1165 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1166 the scev corresponds to. AT_STMT is the statement at that the scev is
1167 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1168 the rules for overflow of the given language apply (e.g., that signed
1169 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1170 tests, but also to enforce that the result follows them. Returns true if the
1171 conversion succeeded, false otherwise. */
1174 convert_affine_scev (struct loop
*loop
, tree type
,
1175 tree
*base
, tree
*step
, gimple
*at_stmt
,
1176 bool use_overflow_semantics
)
1178 tree ct
= TREE_TYPE (*step
);
1179 bool enforce_overflow_semantics
;
1180 bool must_check_src_overflow
, must_check_rslt_overflow
;
1181 tree new_base
, new_step
;
1182 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1185 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1186 but we must check some assumptions.
1188 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1189 of CT is smaller than the precision of TYPE. For example, when we
1190 cast unsigned char [254, +, 1] to unsigned, the values on left side
1191 are 254, 255, 0, 1, ..., but those on the right side are
1192 254, 255, 256, 257, ...
1193 2) In case that we must also preserve the fact that signed ivs do not
1194 overflow, we must additionally check that the new iv does not wrap.
1195 For example, unsigned char [125, +, 1] casted to signed char could
1196 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1197 which would confuse optimizers that assume that this does not
1199 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1201 enforce_overflow_semantics
= (use_overflow_semantics
1202 && nowrap_type_p (type
));
1203 if (enforce_overflow_semantics
)
1205 /* We can avoid checking whether the result overflows in the following
1208 -- must_check_src_overflow is true, and the range of TYPE is superset
1209 of the range of CT -- i.e., in all cases except if CT signed and
1211 -- both CT and TYPE have the same precision and signedness, and we
1212 verify instead that the source does not overflow (this may be
1213 easier than verifying it for the result, as we may use the
1214 information about the semantics of overflow in CT). */
1215 if (must_check_src_overflow
)
1217 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1218 must_check_rslt_overflow
= true;
1220 must_check_rslt_overflow
= false;
1222 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1223 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1225 must_check_rslt_overflow
= false;
1226 must_check_src_overflow
= true;
1229 must_check_rslt_overflow
= true;
1232 must_check_rslt_overflow
= false;
1234 if (must_check_src_overflow
1235 && scev_probably_wraps_p (*base
, *step
, at_stmt
, loop
,
1236 use_overflow_semantics
))
1239 new_base
= chrec_convert (type
, *base
, at_stmt
, use_overflow_semantics
);
1240 /* The step must be sign extended, regardless of the signedness
1241 of CT and TYPE. This only needs to be handled specially when
1242 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1243 (with values 100, 99, 98, ...) from becoming signed or unsigned
1244 [100, +, 255] with values 100, 355, ...; the sign-extension is
1245 performed by default when CT is signed. */
1247 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1249 tree signed_ct
= build_nonstandard_integer_type (TYPE_PRECISION (ct
), 0);
1250 new_step
= chrec_convert (signed_ct
, new_step
, at_stmt
,
1251 use_overflow_semantics
);
1253 new_step
= chrec_convert (step_type
, new_step
, at_stmt
,
1254 use_overflow_semantics
);
1256 if (automatically_generated_chrec_p (new_base
)
1257 || automatically_generated_chrec_p (new_step
))
1260 if (must_check_rslt_overflow
1261 /* Note that in this case we cannot use the fact that signed variables
1262 do not overflow, as this is what we are verifying for the new iv. */
1263 && scev_probably_wraps_p (new_base
, new_step
, at_stmt
, loop
, false))
1272 /* Convert CHREC for the right hand side of a CHREC.
1273 The increment for a pointer type is always sizetype. */
1276 chrec_convert_rhs (tree type
, tree chrec
, gimple
*at_stmt
)
1278 if (POINTER_TYPE_P (type
))
1281 return chrec_convert (type
, chrec
, at_stmt
);
1284 /* Convert CHREC to TYPE. When the analyzer knows the context in
1285 which the CHREC is built, it sets AT_STMT to the statement that
1286 contains the definition of the analyzed variable, otherwise the
1287 conversion is less accurate: the information is used for
1288 determining a more accurate estimation of the number of iterations.
1289 By default AT_STMT could be safely set to NULL_TREE.
1291 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1292 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 unnecessary
1294 tests, but also to enforce that the result follows them. */
1297 chrec_convert_1 (tree type
, tree chrec
, gimple
*at_stmt
,
1298 bool use_overflow_semantics
)
1304 if (automatically_generated_chrec_p (chrec
))
1307 ct
= chrec_type (chrec
);
1308 if (useless_type_conversion_p (type
, ct
))
1311 if (!evolution_function_is_affine_p (chrec
))
1314 loop
= get_chrec_loop (chrec
);
1315 base
= CHREC_LEFT (chrec
);
1316 step
= CHREC_RIGHT (chrec
);
1318 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1319 use_overflow_semantics
))
1320 return build_polynomial_chrec (loop
->num
, base
, step
);
1322 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1324 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1325 may be more expensive. We do want to perform this optimization here
1326 though for canonicalization reasons. */
1327 if (use_overflow_semantics
1328 && (TREE_CODE (chrec
) == PLUS_EXPR
1329 || TREE_CODE (chrec
) == MINUS_EXPR
)
1330 && TREE_CODE (type
) == INTEGER_TYPE
1331 && TREE_CODE (ct
) == INTEGER_TYPE
1332 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1333 && TYPE_OVERFLOW_UNDEFINED (ct
))
1334 res
= fold_build2 (TREE_CODE (chrec
), type
,
1335 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1336 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1337 /* Similar perform the trick that (signed char)((int)x + 2) can be
1338 narrowed to (signed char)((unsigned char)x + 2). */
1339 else if (use_overflow_semantics
1340 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1341 && TREE_CODE (ct
) == INTEGER_TYPE
1342 && TREE_CODE (type
) == INTEGER_TYPE
1343 && TYPE_OVERFLOW_UNDEFINED (type
)
1344 && TYPE_PRECISION (type
) < TYPE_PRECISION (ct
))
1346 tree utype
= unsigned_type_for (type
);
1347 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1348 fold_convert (utype
,
1349 CHREC_LEFT (chrec
)),
1350 fold_convert (utype
,
1351 CHREC_RIGHT (chrec
)));
1352 res
= chrec_convert_1 (type
, res
, at_stmt
, use_overflow_semantics
);
1355 res
= fold_convert (type
, chrec
);
1357 /* Don't propagate overflows. */
1358 if (CONSTANT_CLASS_P (res
))
1359 TREE_OVERFLOW (res
) = 0;
1361 /* But reject constants that don't fit in their type after conversion.
1362 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1363 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1364 and can cause problems later when computing niters of loops. Note
1365 that we don't do the check before converting because we don't want
1366 to reject conversions of negative chrecs to unsigned types. */
1367 if (TREE_CODE (res
) == INTEGER_CST
1368 && TREE_CODE (type
) == INTEGER_TYPE
1369 && !int_fits_type_p (res
, type
))
1370 res
= chrec_dont_know
;
1375 /* Convert CHREC to TYPE. When the analyzer knows the context in
1376 which the CHREC is built, it sets AT_STMT to the statement that
1377 contains the definition of the analyzed variable, otherwise the
1378 conversion is less accurate: the information is used for
1379 determining a more accurate estimation of the number of iterations.
1380 By default AT_STMT could be safely set to NULL_TREE.
1382 The following rule is always true: TREE_TYPE (chrec) ==
1383 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1384 An example of what could happen when adding two chrecs and the type
1385 of the CHREC_RIGHT is different than CHREC_LEFT is:
1387 {(uint) 0, +, (uchar) 10} +
1388 {(uint) 0, +, (uchar) 250}
1390 that would produce a wrong result if CHREC_RIGHT is not (uint):
1392 {(uint) 0, +, (uchar) 4}
1396 {(uint) 0, +, (uint) 260}
1398 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1399 the rules for overflow of the given language apply (e.g., that signed
1400 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1401 tests, but also to enforce that the result follows them. */
1404 chrec_convert (tree type
, tree chrec
, gimple
*at_stmt
,
1405 bool use_overflow_semantics
)
1407 return chrec_convert_1 (type
, chrec
, at_stmt
, use_overflow_semantics
);
1410 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1411 chrec if something else than what chrec_convert would do happens, NULL_TREE
1412 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1413 if the result chrec may overflow. */
1416 chrec_convert_aggressive (tree type
, tree chrec
, bool *fold_conversions
)
1418 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1420 gcc_assert (fold_conversions
!= NULL
);
1422 if (automatically_generated_chrec_p (chrec
)
1423 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1426 inner_type
= TREE_TYPE (chrec
);
1427 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1430 if (useless_type_conversion_p (type
, inner_type
))
1433 if (!*fold_conversions
&& evolution_function_is_affine_p (chrec
))
1438 loop
= get_chrec_loop (chrec
);
1439 base
= CHREC_LEFT (chrec
);
1440 step
= CHREC_RIGHT (chrec
);
1441 if (convert_affine_scev (loop
, type
, &base
, &step
, NULL
, true))
1442 return build_polynomial_chrec (loop
->num
, base
, step
);
1444 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1446 left
= CHREC_LEFT (chrec
);
1447 right
= CHREC_RIGHT (chrec
);
1448 lc
= chrec_convert_aggressive (type
, left
, fold_conversions
);
1450 lc
= chrec_convert (type
, left
, NULL
);
1451 rc
= chrec_convert_aggressive (rtype
, right
, fold_conversions
);
1453 rc
= chrec_convert (rtype
, right
, NULL
);
1455 *fold_conversions
= true;
1457 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1460 /* Returns true when CHREC0 == CHREC1. */
1463 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1465 if (chrec0
== NULL_TREE
1466 || chrec1
== NULL_TREE
1467 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1470 if (chrec0
== chrec1
)
1473 if (! types_compatible_p (TREE_TYPE (chrec0
), TREE_TYPE (chrec1
)))
1476 switch (TREE_CODE (chrec0
))
1478 case POLYNOMIAL_CHREC
:
1479 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1480 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1481 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1486 case POINTER_PLUS_EXPR
:
1487 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1488 TREE_OPERAND (chrec1
, 0))
1489 && eq_evolutions_p (TREE_OPERAND (chrec0
, 1),
1490 TREE_OPERAND (chrec1
, 1));
1493 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1494 TREE_OPERAND (chrec1
, 0));
1497 return operand_equal_p (chrec0
, chrec1
, 0);
1501 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1502 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1503 which of these cases happens. */
1506 scev_direction (const_tree chrec
)
1510 if (!evolution_function_is_affine_p (chrec
))
1511 return EV_DIR_UNKNOWN
;
1513 step
= CHREC_RIGHT (chrec
);
1514 if (TREE_CODE (step
) != INTEGER_CST
)
1515 return EV_DIR_UNKNOWN
;
1517 if (tree_int_cst_sign_bit (step
))
1518 return EV_DIR_DECREASES
;
1520 return EV_DIR_GROWS
;
1523 /* Iterates over all the components of SCEV, and calls CBCK. */
1526 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1528 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1531 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1534 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1537 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1545 /* Returns true when the operation can be part of a linear
1549 operator_is_linear (tree scev
)
1551 switch (TREE_CODE (scev
))
1554 case POLYNOMIAL_CHREC
:
1556 case POINTER_PLUS_EXPR
:
1561 case NON_LVALUE_EXPR
:
1571 /* Return true when SCEV is a linear expression. Linear expressions
1572 can contain additions, substractions and multiplications.
1573 Multiplications are restricted to constant scaling: "cst * x". */
1576 scev_is_linear_expression (tree scev
)
1579 || !operator_is_linear (scev
))
1582 if (TREE_CODE (scev
) == MULT_EXPR
)
1583 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1584 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1586 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1587 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1590 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1593 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1594 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1595 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1598 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1599 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1602 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1612 /* Determines whether the expression CHREC contains only interger consts
1613 in the right parts. */
1616 evolution_function_right_is_integer_cst (const_tree chrec
)
1618 if (chrec
== NULL_TREE
)
1621 switch (TREE_CODE (chrec
))
1626 case POLYNOMIAL_CHREC
:
1627 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1628 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1629 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1632 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));