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 /* Fold the addition of two polynomial functions. */
47 chrec_fold_plus_poly_poly (enum tree_code code
,
53 struct loop
*loop0
= get_chrec_loop (poly0
);
54 struct loop
*loop1
= get_chrec_loop (poly1
);
55 tree rtype
= code
== POINTER_PLUS_EXPR
? chrec_type (poly1
) : type
;
59 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
60 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
61 if (POINTER_TYPE_P (chrec_type (poly0
)))
62 gcc_checking_assert (ptrofftype_p (chrec_type (poly1
))
63 && useless_type_conversion_p (type
, chrec_type (poly0
)));
65 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
66 && useless_type_conversion_p (type
, chrec_type (poly1
)));
69 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
70 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
71 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
72 if (flow_loop_nested_p (loop0
, loop1
))
74 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
75 return build_polynomial_chrec
76 (CHREC_VARIABLE (poly1
),
77 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
80 return build_polynomial_chrec
81 (CHREC_VARIABLE (poly1
),
82 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
83 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
84 SCALAR_FLOAT_TYPE_P (type
)
85 ? build_real (type
, dconstm1
)
86 : build_int_cst_type (type
, -1)));
89 if (flow_loop_nested_p (loop1
, loop0
))
91 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
92 return build_polynomial_chrec
93 (CHREC_VARIABLE (poly0
),
94 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
97 return build_polynomial_chrec
98 (CHREC_VARIABLE (poly0
),
99 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
100 CHREC_RIGHT (poly0
));
103 /* This function should never be called for chrecs of loops that
104 do not belong to the same loop nest. */
107 /* It still can happen if we are not in loop-closed SSA form. */
108 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
109 return chrec_dont_know
;
112 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
114 left
= chrec_fold_plus
115 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
116 right
= chrec_fold_plus
117 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
121 left
= chrec_fold_minus
122 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
123 right
= chrec_fold_minus
124 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
127 if (chrec_zerop (right
))
130 return build_polynomial_chrec
131 (CHREC_VARIABLE (poly0
), left
, right
);
136 /* Fold the multiplication of two polynomial functions. */
139 chrec_fold_multiply_poly_poly (tree type
,
145 struct loop
*loop0
= get_chrec_loop (poly0
);
146 struct loop
*loop1
= get_chrec_loop (poly1
);
150 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
151 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
152 gcc_checking_assert (useless_type_conversion_p (type
, chrec_type (poly0
))
153 && useless_type_conversion_p (type
, chrec_type (poly1
)));
155 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
156 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
157 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
158 if (flow_loop_nested_p (loop0
, loop1
))
159 /* poly0 is a constant wrt. poly1. */
160 return build_polynomial_chrec
161 (CHREC_VARIABLE (poly1
),
162 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
163 CHREC_RIGHT (poly1
));
165 if (flow_loop_nested_p (loop1
, loop0
))
166 /* poly1 is a constant wrt. poly0. */
167 return build_polynomial_chrec
168 (CHREC_VARIABLE (poly0
),
169 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
170 CHREC_RIGHT (poly0
));
174 /* It still can happen if we are not in loop-closed SSA form. */
175 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA
));
176 return chrec_dont_know
;
179 /* poly0 and poly1 are two polynomials in the same variable,
180 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
183 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
186 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
187 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
189 CHREC_LEFT (poly1
)));
191 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
192 /* "a*d + b*c + b*d". */
193 t1
= chrec_fold_plus (type
, t1
, t2
);
195 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
196 ? build_real (type
, dconst2
)
197 : build_int_cst (type
, 2), t2
);
199 var
= CHREC_VARIABLE (poly0
);
200 return build_polynomial_chrec (var
, t0
,
201 build_polynomial_chrec (var
, t1
, t2
));
204 /* When the operands are automatically_generated_chrec_p, the fold has
205 to respect the semantics of the operands. */
208 chrec_fold_automatically_generated_operands (tree op0
,
211 if (op0
== chrec_dont_know
212 || op1
== chrec_dont_know
)
213 return chrec_dont_know
;
215 if (op0
== chrec_known
216 || op1
== chrec_known
)
219 if (op0
== chrec_not_analyzed_yet
220 || op1
== chrec_not_analyzed_yet
)
221 return chrec_not_analyzed_yet
;
223 /* The default case produces a safe result. */
224 return chrec_dont_know
;
227 /* Fold the addition of two chrecs. */
230 chrec_fold_plus_1 (enum tree_code code
, tree type
,
233 if (automatically_generated_chrec_p (op0
)
234 || automatically_generated_chrec_p (op1
))
235 return chrec_fold_automatically_generated_operands (op0
, op1
);
237 switch (TREE_CODE (op0
))
239 case POLYNOMIAL_CHREC
:
241 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
242 switch (TREE_CODE (op1
))
244 case POLYNOMIAL_CHREC
:
246 (!chrec_contains_symbols_defined_in_loop (op1
,
247 CHREC_VARIABLE (op1
)));
248 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
252 /* We can strip sign-conversions to signed by performing the
253 operation in unsigned. */
254 tree optype
= TREE_TYPE (TREE_OPERAND (op1
, 0));
255 if (INTEGRAL_TYPE_P (type
)
256 && INTEGRAL_TYPE_P (optype
)
257 && tree_nop_conversion_p (type
, optype
)
258 && TYPE_UNSIGNED (optype
))
259 return chrec_convert (type
,
260 chrec_fold_plus_1 (code
, optype
,
261 chrec_convert (optype
,
263 TREE_OPERAND (op1
, 0)),
265 if (tree_contains_chrecs (op1
, NULL
))
266 return chrec_dont_know
;
271 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
272 return build_polynomial_chrec
273 (CHREC_VARIABLE (op0
),
274 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
277 return build_polynomial_chrec
278 (CHREC_VARIABLE (op0
),
279 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
285 /* We can strip sign-conversions to signed by performing the
286 operation in unsigned. */
287 tree optype
= TREE_TYPE (TREE_OPERAND (op0
, 0));
288 if (INTEGRAL_TYPE_P (type
)
289 && INTEGRAL_TYPE_P (optype
)
290 && tree_nop_conversion_p (type
, optype
)
291 && TYPE_UNSIGNED (optype
))
292 return chrec_convert (type
,
293 chrec_fold_plus_1 (code
, optype
,
294 TREE_OPERAND (op0
, 0),
295 chrec_convert (optype
,
298 if (tree_contains_chrecs (op0
, NULL
))
299 return chrec_dont_know
;
304 switch (TREE_CODE (op1
))
306 case POLYNOMIAL_CHREC
:
308 (!chrec_contains_symbols_defined_in_loop (op1
,
309 CHREC_VARIABLE (op1
)));
310 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
311 return build_polynomial_chrec
312 (CHREC_VARIABLE (op1
),
313 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
316 return build_polynomial_chrec
317 (CHREC_VARIABLE (op1
),
318 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
319 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
320 SCALAR_FLOAT_TYPE_P (type
)
321 ? build_real (type
, dconstm1
)
322 : build_int_cst_type (type
, -1)));
325 if (tree_contains_chrecs (op1
, NULL
))
326 return chrec_dont_know
;
331 if (tree_contains_chrecs (op0
, NULL
)
332 || tree_contains_chrecs (op1
, NULL
))
333 return build2 (code
, type
, op0
, op1
);
336 if (code
== POINTER_PLUS_EXPR
)
337 return fold_build_pointer_plus (fold_convert (type
, op0
),
340 return fold_build2 (code
, type
,
341 fold_convert (type
, op0
),
342 fold_convert (type
, op1
));
349 /* Fold the addition of two chrecs. */
352 chrec_fold_plus (tree type
,
357 if (automatically_generated_chrec_p (op0
)
358 || automatically_generated_chrec_p (op1
))
359 return chrec_fold_automatically_generated_operands (op0
, op1
);
361 if (integer_zerop (op0
))
362 return chrec_convert (type
, op1
, NULL
);
363 if (integer_zerop (op1
))
364 return chrec_convert (type
, op0
, NULL
);
366 if (POINTER_TYPE_P (type
))
367 code
= POINTER_PLUS_EXPR
;
371 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
374 /* Fold the subtraction of two chrecs. */
377 chrec_fold_minus (tree type
,
381 if (automatically_generated_chrec_p (op0
)
382 || automatically_generated_chrec_p (op1
))
383 return chrec_fold_automatically_generated_operands (op0
, op1
);
385 if (integer_zerop (op1
))
388 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
391 /* Fold the multiplication of two chrecs. */
394 chrec_fold_multiply (tree type
,
398 if (automatically_generated_chrec_p (op0
)
399 || automatically_generated_chrec_p (op1
))
400 return chrec_fold_automatically_generated_operands (op0
, op1
);
402 switch (TREE_CODE (op0
))
404 case POLYNOMIAL_CHREC
:
406 (!chrec_contains_symbols_defined_in_loop (op0
, CHREC_VARIABLE (op0
)));
407 switch (TREE_CODE (op1
))
409 case POLYNOMIAL_CHREC
:
411 (!chrec_contains_symbols_defined_in_loop (op1
,
412 CHREC_VARIABLE (op1
)));
413 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
416 if (tree_contains_chrecs (op1
, NULL
))
417 return chrec_dont_know
;
421 if (integer_onep (op1
))
423 if (integer_zerop (op1
))
424 return build_int_cst (type
, 0);
426 return build_polynomial_chrec
427 (CHREC_VARIABLE (op0
),
428 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
429 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
433 if (tree_contains_chrecs (op0
, NULL
))
434 return chrec_dont_know
;
438 if (integer_onep (op0
))
441 if (integer_zerop (op0
))
442 return build_int_cst (type
, 0);
444 switch (TREE_CODE (op1
))
446 case POLYNOMIAL_CHREC
:
448 (!chrec_contains_symbols_defined_in_loop (op1
,
449 CHREC_VARIABLE (op1
)));
450 return build_polynomial_chrec
451 (CHREC_VARIABLE (op1
),
452 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
453 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
456 if (tree_contains_chrecs (op1
, NULL
))
457 return chrec_dont_know
;
461 if (integer_onep (op1
))
463 if (integer_zerop (op1
))
464 return build_int_cst (type
, 0);
465 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
474 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
475 calculation overflows, otherwise return C(n,k) with type TYPE. */
478 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
480 wi::overflow_type overflow
;
483 /* Handle the most frequent cases. */
485 return build_int_cst (type
, 1);
487 return fold_convert (type
, n
);
489 widest_int num
= wi::to_widest (n
);
491 /* Check that k <= n. */
492 if (wi::ltu_p (num
, k
))
495 /* Denominator = 2. */
496 widest_int denom
= 2;
498 /* Index = Numerator-1. */
499 widest_int idx
= num
- 1;
501 /* Numerator = Numerator*Index = n*(n-1). */
502 num
= wi::smul (num
, idx
, &overflow
);
506 for (i
= 3; i
<= k
; i
++)
511 /* Numerator *= Index. */
512 num
= wi::smul (num
, idx
, &overflow
);
516 /* Denominator *= i. */
520 /* Result = Numerator / Denominator. */
521 num
= wi::udiv_trunc (num
, denom
);
522 if (! wi::fits_to_tree_p (num
, type
))
524 return wide_int_to_tree (type
, num
);
527 /* Helper function. Use the Newton's interpolating formula for
528 evaluating the value of the evolution function.
529 The result may be in an unsigned type of CHREC. */
532 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
534 tree arg0
, arg1
, binomial_n_k
;
535 tree type
= TREE_TYPE (chrec
);
536 struct loop
*var_loop
= get_loop (cfun
, var
);
538 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
539 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
540 chrec
= CHREC_LEFT (chrec
);
542 /* The formula associates the expression and thus we have to make
543 sure to not introduce undefined overflow. */
545 if (INTEGRAL_TYPE_P (type
)
546 && ! TYPE_OVERFLOW_WRAPS (type
))
547 ctype
= unsigned_type_for (type
);
549 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
550 && CHREC_VARIABLE (chrec
) == var
)
552 arg1
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
553 if (arg1
== chrec_dont_know
)
554 return chrec_dont_know
;
555 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
557 return chrec_dont_know
;
558 tree l
= chrec_convert (ctype
, CHREC_LEFT (chrec
), NULL
);
559 arg0
= fold_build2 (MULT_EXPR
, ctype
, l
, binomial_n_k
);
560 return chrec_fold_plus (ctype
, arg0
, arg1
);
563 binomial_n_k
= tree_fold_binomial (ctype
, n
, k
);
565 return chrec_dont_know
;
567 return fold_build2 (MULT_EXPR
, ctype
,
568 chrec_convert (ctype
, chrec
, NULL
), binomial_n_k
);
571 /* Evaluates "CHREC (X)" when the varying variable is VAR.
572 Example: Given the following parameters,
578 The result is given by the Newton's interpolating formula:
579 3 * \binom{10}{0} + 4 * \binom{10}{1}.
583 chrec_apply (unsigned var
,
587 tree type
= chrec_type (chrec
);
588 tree res
= chrec_dont_know
;
590 if (automatically_generated_chrec_p (chrec
)
591 || automatically_generated_chrec_p (x
)
593 /* When the symbols are defined in an outer loop, it is possible
594 to symbolically compute the apply, since the symbols are
595 constants with respect to the varying loop. */
596 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
597 return chrec_dont_know
;
599 if (dump_file
&& (dump_flags
& TDF_SCEV
))
600 fprintf (dump_file
, "(chrec_apply \n");
602 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
603 x
= build_real_from_int_cst (type
, x
);
605 switch (TREE_CODE (chrec
))
607 case POLYNOMIAL_CHREC
:
608 if (evolution_function_is_affine_p (chrec
))
610 if (CHREC_VARIABLE (chrec
) != var
)
611 return build_polynomial_chrec
612 (CHREC_VARIABLE (chrec
),
613 chrec_apply (var
, CHREC_LEFT (chrec
), x
),
614 chrec_apply (var
, CHREC_RIGHT (chrec
), x
));
616 /* "{a, +, b} (x)" -> "a + b*x". */
617 x
= chrec_convert_rhs (type
, x
, NULL
);
618 res
= chrec_fold_multiply (TREE_TYPE (x
), CHREC_RIGHT (chrec
), x
);
619 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
621 else if (TREE_CODE (x
) == INTEGER_CST
622 && tree_int_cst_sgn (x
) == 1)
623 /* testsuite/.../ssa-chrec-38.c. */
624 res
= chrec_convert (type
, chrec_evaluate (var
, chrec
, x
, 0), NULL
);
626 res
= chrec_dont_know
;
630 res
= chrec_convert (TREE_TYPE (chrec
),
631 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
640 if (dump_file
&& (dump_flags
& TDF_SCEV
))
642 fprintf (dump_file
, " (varying_loop = %d\n", var
);
643 fprintf (dump_file
, ")\n (chrec = ");
644 print_generic_expr (dump_file
, chrec
);
645 fprintf (dump_file
, ")\n (x = ");
646 print_generic_expr (dump_file
, x
);
647 fprintf (dump_file
, ")\n (res = ");
648 print_generic_expr (dump_file
, res
);
649 fprintf (dump_file
, "))\n");
655 /* For a given CHREC and an induction variable map IV_MAP that maps
656 (loop->num, expr) for every loop number of the current_loops an
657 expression, calls chrec_apply when the expression is not NULL. */
660 chrec_apply_map (tree chrec
, vec
<tree
> iv_map
)
665 FOR_EACH_VEC_ELT (iv_map
, i
, expr
)
667 chrec
= chrec_apply (i
, chrec
, expr
);
672 /* Replaces the initial condition in CHREC with INIT_COND. */
675 chrec_replace_initial_condition (tree chrec
,
678 if (automatically_generated_chrec_p (chrec
))
681 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
683 switch (TREE_CODE (chrec
))
685 case POLYNOMIAL_CHREC
:
686 return build_polynomial_chrec
687 (CHREC_VARIABLE (chrec
),
688 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
689 CHREC_RIGHT (chrec
));
696 /* Returns the initial condition of a given CHREC. */
699 initial_condition (tree chrec
)
701 if (automatically_generated_chrec_p (chrec
))
704 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
705 return initial_condition (CHREC_LEFT (chrec
));
710 /* Returns a univariate function that represents the evolution in
711 LOOP_NUM. Mask the evolution of any other loop. */
714 hide_evolution_in_other_loops_than_loop (tree chrec
,
717 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
718 if (automatically_generated_chrec_p (chrec
))
721 switch (TREE_CODE (chrec
))
723 case POLYNOMIAL_CHREC
:
724 chloop
= get_chrec_loop (chrec
);
727 return build_polynomial_chrec
729 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
731 CHREC_RIGHT (chrec
));
733 else if (flow_loop_nested_p (chloop
, loop
))
734 /* There is no evolution in this loop. */
735 return initial_condition (chrec
);
737 else if (flow_loop_nested_p (loop
, chloop
))
738 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
742 return chrec_dont_know
;
749 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
750 true, otherwise returns the initial condition in LOOP_NUM. */
753 chrec_component_in_loop_num (tree chrec
,
758 struct loop
*loop
= get_loop (cfun
, loop_num
), *chloop
;
760 if (automatically_generated_chrec_p (chrec
))
763 switch (TREE_CODE (chrec
))
765 case POLYNOMIAL_CHREC
:
766 chloop
= get_chrec_loop (chrec
);
771 component
= CHREC_RIGHT (chrec
);
773 component
= CHREC_LEFT (chrec
);
775 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
776 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
780 return build_polynomial_chrec
782 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
788 else if (flow_loop_nested_p (chloop
, loop
))
789 /* There is no evolution part in this loop. */
794 gcc_assert (flow_loop_nested_p (loop
, chloop
));
795 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
808 /* Returns the evolution part in LOOP_NUM. Example: the call
809 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
813 evolution_part_in_loop_num (tree chrec
,
816 return chrec_component_in_loop_num (chrec
, loop_num
, true);
819 /* Returns the initial condition in LOOP_NUM. Example: the call
820 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
824 initial_condition_in_loop_num (tree chrec
,
827 return chrec_component_in_loop_num (chrec
, loop_num
, false);
830 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
831 This function is essentially used for setting the evolution to
832 chrec_dont_know, for example after having determined that it is
833 impossible to say how many times a loop will execute. */
836 reset_evolution_in_loop (unsigned loop_num
,
840 struct loop
*loop
= get_loop (cfun
, loop_num
);
842 if (POINTER_TYPE_P (chrec_type (chrec
)))
843 gcc_assert (ptrofftype_p (chrec_type (new_evol
)));
845 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
847 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
848 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
850 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
852 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
854 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), left
, right
);
857 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
858 && CHREC_VARIABLE (chrec
) == loop_num
)
859 chrec
= CHREC_LEFT (chrec
);
861 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
864 /* Merges two evolution functions that were found by following two
865 alternate paths of a conditional expression. */
868 chrec_merge (tree chrec1
,
871 if (chrec1
== chrec_dont_know
872 || chrec2
== chrec_dont_know
)
873 return chrec_dont_know
;
875 if (chrec1
== chrec_known
876 || chrec2
== chrec_known
)
879 if (chrec1
== chrec_not_analyzed_yet
)
881 if (chrec2
== chrec_not_analyzed_yet
)
884 if (eq_evolutions_p (chrec1
, chrec2
))
887 return chrec_dont_know
;
894 /* Helper function for is_multivariate_chrec. */
897 is_multivariate_chrec_rec (const_tree chrec
, unsigned int rec_var
)
899 if (chrec
== NULL_TREE
)
902 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
904 if (CHREC_VARIABLE (chrec
) != rec_var
)
907 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
908 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
914 /* Determine whether the given chrec is multivariate or not. */
917 is_multivariate_chrec (const_tree chrec
)
919 if (chrec
== NULL_TREE
)
922 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
923 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
924 CHREC_VARIABLE (chrec
))
925 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
926 CHREC_VARIABLE (chrec
)));
931 /* Determines whether the chrec contains symbolic names or not. */
934 chrec_contains_symbols (const_tree chrec
)
938 if (chrec
== NULL_TREE
)
941 if (TREE_CODE (chrec
) == SSA_NAME
943 || TREE_CODE (chrec
) == POLY_INT_CST
944 || TREE_CODE (chrec
) == PARM_DECL
945 || TREE_CODE (chrec
) == FUNCTION_DECL
946 || TREE_CODE (chrec
) == LABEL_DECL
947 || TREE_CODE (chrec
) == RESULT_DECL
948 || TREE_CODE (chrec
) == FIELD_DECL
)
951 n
= TREE_OPERAND_LENGTH (chrec
);
952 for (i
= 0; i
< n
; i
++)
953 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
)))
958 /* Determines whether the chrec contains undetermined coefficients. */
961 chrec_contains_undetermined (const_tree chrec
)
965 if (chrec
== chrec_dont_know
)
968 if (chrec
== NULL_TREE
)
971 n
= TREE_OPERAND_LENGTH (chrec
);
972 for (i
= 0; i
< n
; i
++)
973 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
)))
978 /* Determines whether the tree EXPR contains chrecs, and increment
979 SIZE if it is not a NULL pointer by an estimation of the depth of
983 tree_contains_chrecs (const_tree expr
, int *size
)
987 if (expr
== NULL_TREE
)
993 if (tree_is_chrec (expr
))
996 n
= TREE_OPERAND_LENGTH (expr
);
997 for (i
= 0; i
< n
; i
++)
998 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
))
1003 /* Recursive helper function. */
1006 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1008 if (evolution_function_is_constant_p (chrec
))
1011 if (TREE_CODE (chrec
) == SSA_NAME
1013 || expr_invariant_in_loop_p (get_loop (cfun
, loopnum
), chrec
)))
1016 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1018 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
1019 || flow_loop_nested_p (get_loop (cfun
, loopnum
),
1020 get_chrec_loop (chrec
))
1021 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
),
1023 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
),
1029 switch (TREE_OPERAND_LENGTH (chrec
))
1032 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 1),
1038 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec
, 0),
1050 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1053 evolution_function_is_invariant_p (tree chrec
, int loopnum
)
1055 return evolution_function_is_invariant_rec_p (chrec
, loopnum
);
1058 /* Determine whether the given tree is an affine multivariate
1062 evolution_function_is_affine_multivariate_p (const_tree chrec
, int loopnum
)
1064 if (chrec
== NULL_TREE
)
1067 switch (TREE_CODE (chrec
))
1069 case POLYNOMIAL_CHREC
:
1070 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec
), loopnum
))
1072 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
))
1076 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
1077 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
1078 != CHREC_VARIABLE (chrec
)
1079 && evolution_function_is_affine_multivariate_p
1080 (CHREC_RIGHT (chrec
), loopnum
))
1088 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec
), loopnum
)
1089 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
1090 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
1091 && evolution_function_is_affine_multivariate_p
1092 (CHREC_LEFT (chrec
), loopnum
))
1103 /* Determine whether the given tree is a function in zero or one
1107 evolution_function_is_univariate_p (const_tree chrec
)
1109 if (chrec
== NULL_TREE
)
1112 switch (TREE_CODE (chrec
))
1114 case POLYNOMIAL_CHREC
:
1115 switch (TREE_CODE (CHREC_LEFT (chrec
)))
1117 case POLYNOMIAL_CHREC
:
1118 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
1120 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
1125 if (tree_contains_chrecs (CHREC_LEFT (chrec
), NULL
))
1130 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1132 case POLYNOMIAL_CHREC
:
1133 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1135 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1140 if (tree_contains_chrecs (CHREC_RIGHT (chrec
), NULL
))
1151 /* Returns the number of variables of CHREC. Example: the call
1152 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1155 nb_vars_in_chrec (tree chrec
)
1157 if (chrec
== NULL_TREE
)
1160 switch (TREE_CODE (chrec
))
1162 case POLYNOMIAL_CHREC
:
1163 return 1 + nb_vars_in_chrec
1164 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1171 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1172 the scev corresponds to. AT_STMT is the statement at that the scev is
1173 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1174 that the rules for overflow of the given language apply (e.g., that signed
1175 arithmetics in C does not overflow) -- i.e., to use them to avoid
1176 unnecessary tests, but also to enforce that the result follows them.
1177 FROM is the source variable converted if it's not NULL. Returns true if
1178 the conversion succeeded, false otherwise. */
1181 convert_affine_scev (struct loop
*loop
, tree type
,
1182 tree
*base
, tree
*step
, gimple
*at_stmt
,
1183 bool use_overflow_semantics
, tree from
)
1185 tree ct
= TREE_TYPE (*step
);
1186 bool enforce_overflow_semantics
;
1187 bool must_check_src_overflow
, must_check_rslt_overflow
;
1188 tree new_base
, new_step
;
1189 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1192 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1193 but we must check some assumptions.
1195 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1196 of CT is smaller than the precision of TYPE. For example, when we
1197 cast unsigned char [254, +, 1] to unsigned, the values on left side
1198 are 254, 255, 0, 1, ..., but those on the right side are
1199 254, 255, 256, 257, ...
1200 2) In case that we must also preserve the fact that signed ivs do not
1201 overflow, we must additionally check that the new iv does not wrap.
1202 For example, unsigned char [125, +, 1] casted to signed char could
1203 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1204 which would confuse optimizers that assume that this does not
1206 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1208 enforce_overflow_semantics
= (use_overflow_semantics
1209 && nowrap_type_p (type
));
1210 if (enforce_overflow_semantics
)
1212 /* We can avoid checking whether the result overflows in the following
1215 -- must_check_src_overflow is true, and the range of TYPE is superset
1216 of the range of CT -- i.e., in all cases except if CT signed and
1218 -- both CT and TYPE have the same precision and signedness, and we
1219 verify instead that the source does not overflow (this may be
1220 easier than verifying it for the result, as we may use the
1221 information about the semantics of overflow in CT). */
1222 if (must_check_src_overflow
)
1224 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1225 must_check_rslt_overflow
= true;
1227 must_check_rslt_overflow
= false;
1229 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1230 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1232 must_check_rslt_overflow
= false;
1233 must_check_src_overflow
= true;
1236 must_check_rslt_overflow
= true;
1239 must_check_rslt_overflow
= false;
1241 if (must_check_src_overflow
1242 && scev_probably_wraps_p (from
, *base
, *step
, at_stmt
, loop
,
1243 use_overflow_semantics
))
1246 new_base
= chrec_convert (type
, *base
, at_stmt
, use_overflow_semantics
);
1247 /* The step must be sign extended, regardless of the signedness
1248 of CT and TYPE. This only needs to be handled specially when
1249 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1250 (with values 100, 99, 98, ...) from becoming signed or unsigned
1251 [100, +, 255] with values 100, 355, ...; the sign-extension is
1252 performed by default when CT is signed. */
1254 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1256 tree signed_ct
= build_nonstandard_integer_type (TYPE_PRECISION (ct
), 0);
1257 new_step
= chrec_convert (signed_ct
, new_step
, at_stmt
,
1258 use_overflow_semantics
);
1260 new_step
= chrec_convert (step_type
, new_step
, at_stmt
,
1261 use_overflow_semantics
);
1263 if (automatically_generated_chrec_p (new_base
)
1264 || automatically_generated_chrec_p (new_step
))
1267 if (must_check_rslt_overflow
1268 /* Note that in this case we cannot use the fact that signed variables
1269 do not overflow, as this is what we are verifying for the new iv. */
1270 && scev_probably_wraps_p (NULL_TREE
, new_base
, new_step
,
1271 at_stmt
, loop
, false))
1280 /* Convert CHREC for the right hand side of a CHREC.
1281 The increment for a pointer type is always sizetype. */
1284 chrec_convert_rhs (tree type
, tree chrec
, gimple
*at_stmt
)
1286 if (POINTER_TYPE_P (type
))
1289 return chrec_convert (type
, chrec
, at_stmt
);
1292 /* Convert CHREC to TYPE. When the analyzer knows the context in
1293 which the CHREC is built, it sets AT_STMT to the statement that
1294 contains the definition of the analyzed variable, otherwise the
1295 conversion is less accurate: the information is used for
1296 determining a more accurate estimation of the number of iterations.
1297 By default AT_STMT could be safely set to NULL_TREE.
1299 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1300 the rules for overflow of the given language apply (e.g., that signed
1301 arithmetics in C does not overflow) -- i.e., to use them to avoid
1302 unnecessary tests, but also to enforce that the result follows them.
1304 FROM is the source variable converted if it's not NULL. */
1307 chrec_convert_1 (tree type
, tree chrec
, gimple
*at_stmt
,
1308 bool use_overflow_semantics
, tree from
)
1314 if (automatically_generated_chrec_p (chrec
))
1317 ct
= chrec_type (chrec
);
1318 if (useless_type_conversion_p (type
, ct
))
1321 if (!evolution_function_is_affine_p (chrec
))
1324 loop
= get_chrec_loop (chrec
);
1325 base
= CHREC_LEFT (chrec
);
1326 step
= CHREC_RIGHT (chrec
);
1328 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1329 use_overflow_semantics
, from
))
1330 return build_polynomial_chrec (loop
->num
, base
, step
);
1332 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1334 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1335 may be more expensive. We do want to perform this optimization here
1336 though for canonicalization reasons. */
1337 if (use_overflow_semantics
1338 && (TREE_CODE (chrec
) == PLUS_EXPR
1339 || TREE_CODE (chrec
) == MINUS_EXPR
)
1340 && TREE_CODE (type
) == INTEGER_TYPE
1341 && TREE_CODE (ct
) == INTEGER_TYPE
1342 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1343 && TYPE_OVERFLOW_UNDEFINED (ct
))
1344 res
= fold_build2 (TREE_CODE (chrec
), type
,
1345 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1346 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1347 /* Similar perform the trick that (signed char)((int)x + 2) can be
1348 narrowed to (signed char)((unsigned char)x + 2). */
1349 else if (use_overflow_semantics
1350 && TREE_CODE (chrec
) == POLYNOMIAL_CHREC
1351 && TREE_CODE (ct
) == INTEGER_TYPE
1352 && TREE_CODE (type
) == INTEGER_TYPE
1353 && TYPE_OVERFLOW_UNDEFINED (type
)
1354 && TYPE_PRECISION (type
) < TYPE_PRECISION (ct
))
1356 tree utype
= unsigned_type_for (type
);
1357 res
= build_polynomial_chrec (CHREC_VARIABLE (chrec
),
1358 fold_convert (utype
,
1359 CHREC_LEFT (chrec
)),
1360 fold_convert (utype
,
1361 CHREC_RIGHT (chrec
)));
1362 res
= chrec_convert_1 (type
, res
, at_stmt
, use_overflow_semantics
, from
);
1365 res
= fold_convert (type
, chrec
);
1367 /* Don't propagate overflows. */
1368 if (CONSTANT_CLASS_P (res
))
1369 TREE_OVERFLOW (res
) = 0;
1371 /* But reject constants that don't fit in their type after conversion.
1372 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1373 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1374 and can cause problems later when computing niters of loops. Note
1375 that we don't do the check before converting because we don't want
1376 to reject conversions of negative chrecs to unsigned types. */
1377 if (TREE_CODE (res
) == INTEGER_CST
1378 && TREE_CODE (type
) == INTEGER_TYPE
1379 && !int_fits_type_p (res
, type
))
1380 res
= chrec_dont_know
;
1385 /* Convert CHREC to TYPE. When the analyzer knows the context in
1386 which the CHREC is built, it sets AT_STMT to the statement that
1387 contains the definition of the analyzed variable, otherwise the
1388 conversion is less accurate: the information is used for
1389 determining a more accurate estimation of the number of iterations.
1390 By default AT_STMT could be safely set to NULL_TREE.
1392 The following rule is always true: TREE_TYPE (chrec) ==
1393 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1394 An example of what could happen when adding two chrecs and the type
1395 of the CHREC_RIGHT is different than CHREC_LEFT is:
1397 {(uint) 0, +, (uchar) 10} +
1398 {(uint) 0, +, (uchar) 250}
1400 that would produce a wrong result if CHREC_RIGHT is not (uint):
1402 {(uint) 0, +, (uchar) 4}
1406 {(uint) 0, +, (uint) 260}
1408 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1409 the rules for overflow of the given language apply (e.g., that signed
1410 arithmetics in C does not overflow) -- i.e., to use them to avoid
1411 unnecessary tests, but also to enforce that the result follows them.
1413 FROM is the source variable converted if it's not NULL. */
1416 chrec_convert (tree type
, tree chrec
, gimple
*at_stmt
,
1417 bool use_overflow_semantics
, tree from
)
1419 return chrec_convert_1 (type
, chrec
, at_stmt
, use_overflow_semantics
, from
);
1422 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1423 chrec if something else than what chrec_convert would do happens, NULL_TREE
1424 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1425 if the result chrec may overflow. */
1428 chrec_convert_aggressive (tree type
, tree chrec
, bool *fold_conversions
)
1430 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1432 gcc_assert (fold_conversions
!= NULL
);
1434 if (automatically_generated_chrec_p (chrec
)
1435 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1438 inner_type
= TREE_TYPE (chrec
);
1439 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1442 if (useless_type_conversion_p (type
, inner_type
))
1445 if (!*fold_conversions
&& evolution_function_is_affine_p (chrec
))
1450 loop
= get_chrec_loop (chrec
);
1451 base
= CHREC_LEFT (chrec
);
1452 step
= CHREC_RIGHT (chrec
);
1453 if (convert_affine_scev (loop
, type
, &base
, &step
, NULL
, true))
1454 return build_polynomial_chrec (loop
->num
, base
, step
);
1456 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1458 left
= CHREC_LEFT (chrec
);
1459 right
= CHREC_RIGHT (chrec
);
1460 lc
= chrec_convert_aggressive (type
, left
, fold_conversions
);
1462 lc
= chrec_convert (type
, left
, NULL
);
1463 rc
= chrec_convert_aggressive (rtype
, right
, fold_conversions
);
1465 rc
= chrec_convert (rtype
, right
, NULL
);
1467 *fold_conversions
= true;
1469 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1472 /* Returns true when CHREC0 == CHREC1. */
1475 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1477 if (chrec0
== NULL_TREE
1478 || chrec1
== NULL_TREE
1479 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1482 if (chrec0
== chrec1
)
1485 if (! types_compatible_p (TREE_TYPE (chrec0
), TREE_TYPE (chrec1
)))
1488 switch (TREE_CODE (chrec0
))
1490 case POLYNOMIAL_CHREC
:
1491 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1492 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1493 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1498 case POINTER_PLUS_EXPR
:
1499 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1500 TREE_OPERAND (chrec1
, 0))
1501 && eq_evolutions_p (TREE_OPERAND (chrec0
, 1),
1502 TREE_OPERAND (chrec1
, 1));
1505 return eq_evolutions_p (TREE_OPERAND (chrec0
, 0),
1506 TREE_OPERAND (chrec1
, 0));
1509 return operand_equal_p (chrec0
, chrec1
, 0);
1513 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1514 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1515 which of these cases happens. */
1518 scev_direction (const_tree chrec
)
1522 if (!evolution_function_is_affine_p (chrec
))
1523 return EV_DIR_UNKNOWN
;
1525 step
= CHREC_RIGHT (chrec
);
1526 if (TREE_CODE (step
) != INTEGER_CST
)
1527 return EV_DIR_UNKNOWN
;
1529 if (tree_int_cst_sign_bit (step
))
1530 return EV_DIR_DECREASES
;
1532 return EV_DIR_GROWS
;
1535 /* Iterates over all the components of SCEV, and calls CBCK. */
1538 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1540 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1543 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1547 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1551 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1560 /* Returns true when the operation can be part of a linear
1564 operator_is_linear (tree scev
)
1566 switch (TREE_CODE (scev
))
1569 case POLYNOMIAL_CHREC
:
1571 case POINTER_PLUS_EXPR
:
1576 case NON_LVALUE_EXPR
:
1586 /* Return true when SCEV is a linear expression. Linear expressions
1587 can contain additions, substractions and multiplications.
1588 Multiplications are restricted to constant scaling: "cst * x". */
1591 scev_is_linear_expression (tree scev
)
1593 if (evolution_function_is_constant_p (scev
))
1597 || !operator_is_linear (scev
))
1600 if (TREE_CODE (scev
) == MULT_EXPR
)
1601 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1602 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1604 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1605 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1608 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1611 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1612 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1613 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1616 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1617 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1620 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1630 /* Determines whether the expression CHREC contains only interger consts
1631 in the right parts. */
1634 evolution_function_right_is_integer_cst (const_tree chrec
)
1636 if (chrec
== NULL_TREE
)
1639 switch (TREE_CODE (chrec
))
1644 case POLYNOMIAL_CHREC
:
1645 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1646 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1647 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1650 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));