1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file implements operations on chains of recurrences. Chains
23 of recurrences are used for modeling evolution functions of scalar
29 #include "coretypes.h"
33 #include "tree-pretty-print.h"
35 #include "tree-flow.h"
36 #include "tree-chrec.h"
37 #include "tree-pass.h"
40 #include "tree-scalar-evolution.h"
44 /* Extended folder for chrecs. */
46 /* Determines whether CST is not a constant evolution. */
49 is_not_constant_evolution (const_tree cst
)
51 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
54 /* Fold CODE for a polynomial function and a constant. */
57 chrec_fold_poly_cst (enum tree_code code
,
64 gcc_assert (TREE_CODE (poly
) == POLYNOMIAL_CHREC
);
65 gcc_assert (!is_not_constant_evolution (cst
));
66 gcc_assert (type
== chrec_type (poly
));
71 return build_polynomial_chrec
72 (CHREC_VARIABLE (poly
),
73 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
77 return build_polynomial_chrec
78 (CHREC_VARIABLE (poly
),
79 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
83 return build_polynomial_chrec
84 (CHREC_VARIABLE (poly
),
85 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
86 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
89 return chrec_dont_know
;
93 /* Fold the addition of two polynomial functions. */
96 chrec_fold_plus_poly_poly (enum tree_code code
,
102 struct loop
*loop0
= get_chrec_loop (poly0
);
103 struct loop
*loop1
= get_chrec_loop (poly1
);
104 tree rtype
= code
== POINTER_PLUS_EXPR
? sizetype
: type
;
108 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
109 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
110 if (POINTER_TYPE_P (chrec_type (poly0
)))
111 gcc_assert (chrec_type (poly1
) == sizetype
);
113 gcc_assert (chrec_type (poly0
) == chrec_type (poly1
));
114 gcc_assert (type
== chrec_type (poly0
));
117 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
118 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
119 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
120 if (flow_loop_nested_p (loop0
, loop1
))
122 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
123 return build_polynomial_chrec
124 (CHREC_VARIABLE (poly1
),
125 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
126 CHREC_RIGHT (poly1
));
128 return build_polynomial_chrec
129 (CHREC_VARIABLE (poly1
),
130 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
131 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
132 SCALAR_FLOAT_TYPE_P (type
)
133 ? build_real (type
, dconstm1
)
134 : build_int_cst_type (type
, -1)));
137 if (flow_loop_nested_p (loop1
, loop0
))
139 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
140 return build_polynomial_chrec
141 (CHREC_VARIABLE (poly0
),
142 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
143 CHREC_RIGHT (poly0
));
145 return build_polynomial_chrec
146 (CHREC_VARIABLE (poly0
),
147 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
148 CHREC_RIGHT (poly0
));
151 /* This function should never be called for chrecs of loops that
152 do not belong to the same loop nest. */
153 gcc_assert (loop0
== loop1
);
155 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
157 left
= chrec_fold_plus
158 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
159 right
= chrec_fold_plus
160 (rtype
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
164 left
= chrec_fold_minus
165 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
166 right
= chrec_fold_minus
167 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
170 if (chrec_zerop (right
))
173 return build_polynomial_chrec
174 (CHREC_VARIABLE (poly0
), left
, right
);
179 /* Fold the multiplication of two polynomial functions. */
182 chrec_fold_multiply_poly_poly (tree type
,
188 struct loop
*loop0
= get_chrec_loop (poly0
);
189 struct loop
*loop1
= get_chrec_loop (poly1
);
193 gcc_assert (TREE_CODE (poly0
) == POLYNOMIAL_CHREC
);
194 gcc_assert (TREE_CODE (poly1
) == POLYNOMIAL_CHREC
);
195 gcc_assert (chrec_type (poly0
) == chrec_type (poly1
));
196 gcc_assert (type
== chrec_type (poly0
));
198 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
199 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
200 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
201 if (flow_loop_nested_p (loop0
, loop1
))
202 /* poly0 is a constant wrt. poly1. */
203 return build_polynomial_chrec
204 (CHREC_VARIABLE (poly1
),
205 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
206 CHREC_RIGHT (poly1
));
208 if (flow_loop_nested_p (loop1
, loop0
))
209 /* poly1 is a constant wrt. poly0. */
210 return build_polynomial_chrec
211 (CHREC_VARIABLE (poly0
),
212 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
213 CHREC_RIGHT (poly0
));
215 gcc_assert (loop0
== loop1
);
217 /* poly0 and poly1 are two polynomials in the same variable,
218 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
221 t0
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
224 t1
= chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
));
225 t1
= chrec_fold_plus (type
, t1
, chrec_fold_multiply (type
,
227 CHREC_LEFT (poly1
)));
229 t2
= chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
230 /* "a*d + b*c + b*d". */
231 t1
= chrec_fold_plus (type
, t1
, t2
);
233 t2
= chrec_fold_multiply (type
, SCALAR_FLOAT_TYPE_P (type
)
234 ? build_real (type
, dconst2
)
235 : build_int_cst (type
, 2), t2
);
237 var
= CHREC_VARIABLE (poly0
);
238 return build_polynomial_chrec (var
, t0
,
239 build_polynomial_chrec (var
, t1
, t2
));
242 /* When the operands are automatically_generated_chrec_p, the fold has
243 to respect the semantics of the operands. */
246 chrec_fold_automatically_generated_operands (tree op0
,
249 if (op0
== chrec_dont_know
250 || op1
== chrec_dont_know
)
251 return chrec_dont_know
;
253 if (op0
== chrec_known
254 || op1
== chrec_known
)
257 if (op0
== chrec_not_analyzed_yet
258 || op1
== chrec_not_analyzed_yet
)
259 return chrec_not_analyzed_yet
;
261 /* The default case produces a safe result. */
262 return chrec_dont_know
;
265 /* Fold the addition of two chrecs. */
268 chrec_fold_plus_1 (enum tree_code code
, tree type
,
271 tree op1_type
= code
== POINTER_PLUS_EXPR
? sizetype
: type
;
273 if (automatically_generated_chrec_p (op0
)
274 || automatically_generated_chrec_p (op1
))
275 return chrec_fold_automatically_generated_operands (op0
, op1
);
277 switch (TREE_CODE (op0
))
279 case POLYNOMIAL_CHREC
:
280 switch (TREE_CODE (op1
))
282 case POLYNOMIAL_CHREC
:
283 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
286 if (tree_contains_chrecs (op1
, NULL
))
287 return chrec_dont_know
;
290 if (code
== PLUS_EXPR
|| code
== POINTER_PLUS_EXPR
)
291 return build_polynomial_chrec
292 (CHREC_VARIABLE (op0
),
293 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
296 return build_polynomial_chrec
297 (CHREC_VARIABLE (op0
),
298 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
303 if (tree_contains_chrecs (op0
, NULL
))
304 return chrec_dont_know
;
307 switch (TREE_CODE (op1
))
309 case POLYNOMIAL_CHREC
:
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
, &size
)
332 || tree_contains_chrecs (op1
, &size
))
333 && size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
334 return build2 (code
, type
, op0
, op1
);
335 else if (size
< PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE
))
336 return fold_build2 (code
, type
,
337 fold_convert (type
, op0
),
338 fold_convert (op1_type
, op1
));
340 return chrec_dont_know
;
346 /* Fold the addition of two chrecs. */
349 chrec_fold_plus (tree type
,
354 if (automatically_generated_chrec_p (op0
)
355 || automatically_generated_chrec_p (op1
))
356 return chrec_fold_automatically_generated_operands (op0
, op1
);
358 if (integer_zerop (op0
))
359 return chrec_convert (type
, op1
, NULL
);
360 if (integer_zerop (op1
))
361 return chrec_convert (type
, op0
, NULL
);
363 if (POINTER_TYPE_P (type
))
364 code
= POINTER_PLUS_EXPR
;
368 return chrec_fold_plus_1 (code
, type
, op0
, op1
);
371 /* Fold the subtraction of two chrecs. */
374 chrec_fold_minus (tree type
,
378 if (automatically_generated_chrec_p (op0
)
379 || automatically_generated_chrec_p (op1
))
380 return chrec_fold_automatically_generated_operands (op0
, op1
);
382 if (integer_zerop (op1
))
385 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
388 /* Fold the multiplication of two chrecs. */
391 chrec_fold_multiply (tree type
,
395 if (automatically_generated_chrec_p (op0
)
396 || automatically_generated_chrec_p (op1
))
397 return chrec_fold_automatically_generated_operands (op0
, op1
);
399 switch (TREE_CODE (op0
))
401 case POLYNOMIAL_CHREC
:
402 switch (TREE_CODE (op1
))
404 case POLYNOMIAL_CHREC
:
405 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
408 if (tree_contains_chrecs (op1
, NULL
))
409 return chrec_dont_know
;
412 if (integer_onep (op1
))
414 if (integer_zerop (op1
))
415 return build_int_cst (type
, 0);
417 return build_polynomial_chrec
418 (CHREC_VARIABLE (op0
),
419 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
420 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
424 if (tree_contains_chrecs (op0
, NULL
))
425 return chrec_dont_know
;
428 if (integer_onep (op0
))
431 if (integer_zerop (op0
))
432 return build_int_cst (type
, 0);
434 switch (TREE_CODE (op1
))
436 case POLYNOMIAL_CHREC
:
437 return build_polynomial_chrec
438 (CHREC_VARIABLE (op1
),
439 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
440 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
443 if (tree_contains_chrecs (op1
, NULL
))
444 return chrec_dont_know
;
447 if (integer_onep (op1
))
449 if (integer_zerop (op1
))
450 return build_int_cst (type
, 0);
451 return fold_build2 (MULT_EXPR
, type
, op0
, op1
);
460 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
461 calculation overflows, otherwise return C(n,k) with type TYPE. */
464 tree_fold_binomial (tree type
, tree n
, unsigned int k
)
466 unsigned HOST_WIDE_INT lidx
, lnum
, ldenom
, lres
, ldum
;
467 HOST_WIDE_INT hidx
, hnum
, hdenom
, hres
, hdum
;
471 /* Handle the most frequent cases. */
473 return build_int_cst (type
, 1);
475 return fold_convert (type
, n
);
477 /* Check that k <= n. */
478 if (TREE_INT_CST_HIGH (n
) == 0
479 && TREE_INT_CST_LOW (n
) < k
)
483 lnum
= TREE_INT_CST_LOW (n
);
484 hnum
= TREE_INT_CST_HIGH (n
);
486 /* Denominator = 2. */
490 /* Index = Numerator-1. */
494 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
502 /* Numerator = Numerator*Index = n*(n-1). */
503 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
506 for (i
= 3; i
<= k
; i
++)
512 lidx
= ~ (unsigned HOST_WIDE_INT
) 0;
517 /* Numerator *= Index. */
518 if (mul_double (lnum
, hnum
, lidx
, hidx
, &lnum
, &hnum
))
521 /* Denominator *= i. */
522 mul_double (ldenom
, hdenom
, i
, 0, &ldenom
, &hdenom
);
525 /* Result = Numerator / Denominator. */
526 div_and_round_double (EXACT_DIV_EXPR
, 1, lnum
, hnum
, ldenom
, hdenom
,
527 &lres
, &hres
, &ldum
, &hdum
);
529 res
= build_int_cst_wide (type
, lres
, hres
);
530 return int_fits_type_p (res
, type
) ? res
: NULL_TREE
;
533 /* Helper function. Use the Newton's interpolating formula for
534 evaluating the value of the evolution function. */
537 chrec_evaluate (unsigned var
, tree chrec
, tree n
, unsigned int k
)
539 tree arg0
, arg1
, binomial_n_k
;
540 tree type
= TREE_TYPE (chrec
);
541 struct loop
*var_loop
= get_loop (var
);
543 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
544 && flow_loop_nested_p (var_loop
, get_chrec_loop (chrec
)))
545 chrec
= CHREC_LEFT (chrec
);
547 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
548 && CHREC_VARIABLE (chrec
) == var
)
550 arg1
= chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
, k
+ 1);
551 if (arg1
== chrec_dont_know
)
552 return chrec_dont_know
;
553 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
555 return chrec_dont_know
;
556 arg0
= fold_build2 (MULT_EXPR
, type
,
557 CHREC_LEFT (chrec
), binomial_n_k
);
558 return chrec_fold_plus (type
, arg0
, arg1
);
561 binomial_n_k
= tree_fold_binomial (type
, n
, k
);
563 return chrec_dont_know
;
565 return fold_build2 (MULT_EXPR
, type
, chrec
, binomial_n_k
);
568 /* Evaluates "CHREC (X)" when the varying variable is VAR.
569 Example: Given the following parameters,
575 The result is given by the Newton's interpolating formula:
576 3 * \binom{10}{0} + 4 * \binom{10}{1}.
580 chrec_apply (unsigned var
,
584 tree type
= chrec_type (chrec
);
585 tree res
= chrec_dont_know
;
587 if (automatically_generated_chrec_p (chrec
)
588 || automatically_generated_chrec_p (x
)
590 /* When the symbols are defined in an outer loop, it is possible
591 to symbolically compute the apply, since the symbols are
592 constants with respect to the varying loop. */
593 || chrec_contains_symbols_defined_in_loop (chrec
, var
))
594 return chrec_dont_know
;
596 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
597 fprintf (dump_file
, "(chrec_apply \n");
599 if (TREE_CODE (x
) == INTEGER_CST
&& SCALAR_FLOAT_TYPE_P (type
))
600 x
= build_real_from_int_cst (type
, x
);
602 switch (TREE_CODE (chrec
))
604 case POLYNOMIAL_CHREC
:
605 if (evolution_function_is_affine_p (chrec
))
607 if (CHREC_VARIABLE (chrec
) != var
)
608 return build_polynomial_chrec
609 (CHREC_VARIABLE (chrec
),
610 chrec_apply (var
, CHREC_LEFT (chrec
), x
),
611 chrec_apply (var
, CHREC_RIGHT (chrec
), x
));
613 /* "{a, +, b} (x)" -> "a + b*x". */
614 x
= chrec_convert_rhs (type
, x
, NULL
);
615 res
= chrec_fold_multiply (TREE_TYPE (x
), CHREC_RIGHT (chrec
), x
);
616 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
), res
);
618 else if (TREE_CODE (x
) == INTEGER_CST
619 && tree_int_cst_sgn (x
) == 1)
620 /* testsuite/.../ssa-chrec-38.c. */
621 res
= chrec_evaluate (var
, chrec
, x
, 0);
623 res
= chrec_dont_know
;
627 res
= chrec_convert (TREE_TYPE (chrec
),
628 chrec_apply (var
, TREE_OPERAND (chrec
, 0), x
),
637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
639 fprintf (dump_file
, " (varying_loop = %d\n", var
);
640 fprintf (dump_file
, ")\n (chrec = ");
641 print_generic_expr (dump_file
, chrec
, 0);
642 fprintf (dump_file
, ")\n (x = ");
643 print_generic_expr (dump_file
, x
, 0);
644 fprintf (dump_file
, ")\n (res = ");
645 print_generic_expr (dump_file
, res
, 0);
646 fprintf (dump_file
, "))\n");
652 /* For a given CHREC and an induction variable map IV_MAP that maps
653 (loop->num, expr) for every loop number of the current_loops an
654 expression, calls chrec_apply when the expression is not NULL. */
657 chrec_apply_map (tree chrec
, VEC (tree
, heap
) *iv_map
)
662 for (i
= 0; VEC_iterate (tree
, iv_map
, i
, expr
); i
++)
664 chrec
= chrec_apply (i
, chrec
, expr
);
669 /* Replaces the initial condition in CHREC with INIT_COND. */
672 chrec_replace_initial_condition (tree chrec
,
675 if (automatically_generated_chrec_p (chrec
))
678 gcc_assert (chrec_type (chrec
) == chrec_type (init_cond
));
680 switch (TREE_CODE (chrec
))
682 case POLYNOMIAL_CHREC
:
683 return build_polynomial_chrec
684 (CHREC_VARIABLE (chrec
),
685 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
686 CHREC_RIGHT (chrec
));
693 /* Returns the initial condition of a given CHREC. */
696 initial_condition (tree chrec
)
698 if (automatically_generated_chrec_p (chrec
))
701 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
702 return initial_condition (CHREC_LEFT (chrec
));
707 /* Returns a univariate function that represents the evolution in
708 LOOP_NUM. Mask the evolution of any other loop. */
711 hide_evolution_in_other_loops_than_loop (tree chrec
,
714 struct loop
*loop
= get_loop (loop_num
), *chloop
;
715 if (automatically_generated_chrec_p (chrec
))
718 switch (TREE_CODE (chrec
))
720 case POLYNOMIAL_CHREC
:
721 chloop
= get_chrec_loop (chrec
);
724 return build_polynomial_chrec
726 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
728 CHREC_RIGHT (chrec
));
730 else if (flow_loop_nested_p (chloop
, loop
))
731 /* There is no evolution in this loop. */
732 return initial_condition (chrec
);
736 gcc_assert (flow_loop_nested_p (loop
, chloop
));
737 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
746 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
747 true, otherwise returns the initial condition in LOOP_NUM. */
750 chrec_component_in_loop_num (tree chrec
,
755 struct loop
*loop
= get_loop (loop_num
), *chloop
;
757 if (automatically_generated_chrec_p (chrec
))
760 switch (TREE_CODE (chrec
))
762 case POLYNOMIAL_CHREC
:
763 chloop
= get_chrec_loop (chrec
);
768 component
= CHREC_RIGHT (chrec
);
770 component
= CHREC_LEFT (chrec
);
772 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
773 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
777 return build_polynomial_chrec
779 chrec_component_in_loop_num (CHREC_LEFT (chrec
),
785 else if (flow_loop_nested_p (chloop
, loop
))
786 /* There is no evolution part in this loop. */
791 gcc_assert (flow_loop_nested_p (loop
, chloop
));
792 return chrec_component_in_loop_num (CHREC_LEFT (chrec
),
805 /* Returns the evolution part in LOOP_NUM. Example: the call
806 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
810 evolution_part_in_loop_num (tree chrec
,
813 return chrec_component_in_loop_num (chrec
, loop_num
, true);
816 /* Returns the initial condition in LOOP_NUM. Example: the call
817 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
821 initial_condition_in_loop_num (tree chrec
,
824 return chrec_component_in_loop_num (chrec
, loop_num
, false);
827 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
828 This function is essentially used for setting the evolution to
829 chrec_dont_know, for example after having determined that it is
830 impossible to say how many times a loop will execute. */
833 reset_evolution_in_loop (unsigned loop_num
,
837 struct loop
*loop
= get_loop (loop_num
);
839 if (POINTER_TYPE_P (chrec_type (chrec
)))
840 gcc_assert (sizetype
== chrec_type (new_evol
));
842 gcc_assert (chrec_type (chrec
) == chrec_type (new_evol
));
844 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
845 && flow_loop_nested_p (loop
, get_chrec_loop (chrec
)))
847 tree left
= reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
),
849 tree right
= reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
),
851 return build3 (POLYNOMIAL_CHREC
, TREE_TYPE (left
),
852 build_int_cst (NULL_TREE
, CHREC_VARIABLE (chrec
)),
856 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
857 && CHREC_VARIABLE (chrec
) == loop_num
)
858 chrec
= CHREC_LEFT (chrec
);
860 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
863 /* Merges two evolution functions that were found by following two
864 alternate paths of a conditional expression. */
867 chrec_merge (tree chrec1
,
870 if (chrec1
== chrec_dont_know
871 || chrec2
== chrec_dont_know
)
872 return chrec_dont_know
;
874 if (chrec1
== chrec_known
875 || chrec2
== chrec_known
)
878 if (chrec1
== chrec_not_analyzed_yet
)
880 if (chrec2
== chrec_not_analyzed_yet
)
883 if (eq_evolutions_p (chrec1
, chrec2
))
886 return chrec_dont_know
;
893 /* Helper function for is_multivariate_chrec. */
896 is_multivariate_chrec_rec (const_tree chrec
, unsigned int rec_var
)
898 if (chrec
== NULL_TREE
)
901 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
903 if (CHREC_VARIABLE (chrec
) != rec_var
)
906 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
907 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
913 /* Determine whether the given chrec is multivariate or not. */
916 is_multivariate_chrec (const_tree chrec
)
918 if (chrec
== NULL_TREE
)
921 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
922 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
923 CHREC_VARIABLE (chrec
))
924 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
925 CHREC_VARIABLE (chrec
)));
930 /* Determines whether the chrec contains symbolic names or not. */
933 chrec_contains_symbols (const_tree chrec
)
937 if (chrec
== NULL_TREE
)
940 if (TREE_CODE (chrec
) == SSA_NAME
941 || TREE_CODE (chrec
) == VAR_DECL
942 || TREE_CODE (chrec
) == PARM_DECL
943 || TREE_CODE (chrec
) == FUNCTION_DECL
944 || TREE_CODE (chrec
) == LABEL_DECL
945 || TREE_CODE (chrec
) == RESULT_DECL
946 || TREE_CODE (chrec
) == FIELD_DECL
)
949 n
= TREE_OPERAND_LENGTH (chrec
);
950 for (i
= 0; i
< n
; i
++)
951 if (chrec_contains_symbols (TREE_OPERAND (chrec
, i
)))
956 /* Determines whether the chrec contains undetermined coefficients. */
959 chrec_contains_undetermined (const_tree chrec
)
963 if (chrec
== chrec_dont_know
)
966 if (chrec
== NULL_TREE
)
969 n
= TREE_OPERAND_LENGTH (chrec
);
970 for (i
= 0; i
< n
; i
++)
971 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, i
)))
976 /* Determines whether the tree EXPR contains chrecs, and increment
977 SIZE if it is not a NULL pointer by an estimation of the depth of
981 tree_contains_chrecs (const_tree expr
, int *size
)
985 if (expr
== NULL_TREE
)
991 if (tree_is_chrec (expr
))
994 n
= TREE_OPERAND_LENGTH (expr
);
995 for (i
= 0; i
< n
; i
++)
996 if (tree_contains_chrecs (TREE_OPERAND (expr
, i
), size
))
1001 /* Recursive helper function. */
1004 evolution_function_is_invariant_rec_p (tree chrec
, int loopnum
)
1006 if (evolution_function_is_constant_p (chrec
))
1009 if (TREE_CODE (chrec
) == SSA_NAME
1011 || expr_invariant_in_loop_p (get_loop (loopnum
), chrec
)))
1014 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
1016 if (CHREC_VARIABLE (chrec
) == (unsigned) loopnum
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
)))
1123 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
1125 case POLYNOMIAL_CHREC
:
1126 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
1128 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
1141 /* Returns the number of variables of CHREC. Example: the call
1142 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1145 nb_vars_in_chrec (tree chrec
)
1147 if (chrec
== NULL_TREE
)
1150 switch (TREE_CODE (chrec
))
1152 case POLYNOMIAL_CHREC
:
1153 return 1 + nb_vars_in_chrec
1154 (initial_condition_in_loop_num (chrec
, CHREC_VARIABLE (chrec
)));
1161 static tree
chrec_convert_1 (tree
, tree
, gimple
, bool);
1163 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1164 the scev corresponds to. AT_STMT is the statement at that the scev is
1165 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1166 the rules for overflow of the given language apply (e.g., that signed
1167 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1168 tests, but also to enforce that the result follows them. Returns true if the
1169 conversion succeeded, false otherwise. */
1172 convert_affine_scev (struct loop
*loop
, tree type
,
1173 tree
*base
, tree
*step
, gimple at_stmt
,
1174 bool use_overflow_semantics
)
1176 tree ct
= TREE_TYPE (*step
);
1177 bool enforce_overflow_semantics
;
1178 bool must_check_src_overflow
, must_check_rslt_overflow
;
1179 tree new_base
, new_step
;
1180 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1183 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1184 but we must check some assumptions.
1186 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1187 of CT is smaller than the precision of TYPE. For example, when we
1188 cast unsigned char [254, +, 1] to unsigned, the values on left side
1189 are 254, 255, 0, 1, ..., but those on the right side are
1190 254, 255, 256, 257, ...
1191 2) In case that we must also preserve the fact that signed ivs do not
1192 overflow, we must additionally check that the new iv does not wrap.
1193 For example, unsigned char [125, +, 1] casted to signed char could
1194 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1195 which would confuse optimizers that assume that this does not
1197 must_check_src_overflow
= TYPE_PRECISION (ct
) < TYPE_PRECISION (type
);
1199 enforce_overflow_semantics
= (use_overflow_semantics
1200 && nowrap_type_p (type
));
1201 if (enforce_overflow_semantics
)
1203 /* We can avoid checking whether the result overflows in the following
1206 -- must_check_src_overflow is true, and the range of TYPE is superset
1207 of the range of CT -- i.e., in all cases except if CT signed and
1209 -- both CT and TYPE have the same precision and signedness, and we
1210 verify instead that the source does not overflow (this may be
1211 easier than verifying it for the result, as we may use the
1212 information about the semantics of overflow in CT). */
1213 if (must_check_src_overflow
)
1215 if (TYPE_UNSIGNED (type
) && !TYPE_UNSIGNED (ct
))
1216 must_check_rslt_overflow
= true;
1218 must_check_rslt_overflow
= false;
1220 else if (TYPE_UNSIGNED (ct
) == TYPE_UNSIGNED (type
)
1221 && TYPE_PRECISION (ct
) == TYPE_PRECISION (type
))
1223 must_check_rslt_overflow
= false;
1224 must_check_src_overflow
= true;
1227 must_check_rslt_overflow
= true;
1230 must_check_rslt_overflow
= false;
1232 if (must_check_src_overflow
1233 && scev_probably_wraps_p (*base
, *step
, at_stmt
, loop
,
1234 use_overflow_semantics
))
1237 new_base
= chrec_convert_1 (type
, *base
, at_stmt
,
1238 use_overflow_semantics
);
1239 /* The step must be sign extended, regardless of the signedness
1240 of CT and TYPE. This only needs to be handled specially when
1241 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1242 (with values 100, 99, 98, ...) from becoming signed or unsigned
1243 [100, +, 255] with values 100, 355, ...; the sign-extension is
1244 performed by default when CT is signed. */
1246 if (TYPE_PRECISION (step_type
) > TYPE_PRECISION (ct
) && TYPE_UNSIGNED (ct
))
1247 new_step
= chrec_convert_1 (signed_type_for (ct
), new_step
, at_stmt
,
1248 use_overflow_semantics
);
1249 new_step
= chrec_convert_1 (step_type
, new_step
, at_stmt
, use_overflow_semantics
);
1251 if (automatically_generated_chrec_p (new_base
)
1252 || automatically_generated_chrec_p (new_step
))
1255 if (must_check_rslt_overflow
1256 /* Note that in this case we cannot use the fact that signed variables
1257 do not overflow, as this is what we are verifying for the new iv. */
1258 && scev_probably_wraps_p (new_base
, new_step
, at_stmt
, loop
, false))
1267 /* Convert CHREC for the right hand side of a CHREC.
1268 The increment for a pointer type is always sizetype. */
1271 chrec_convert_rhs (tree type
, tree chrec
, gimple at_stmt
)
1273 if (POINTER_TYPE_P (type
))
1276 return chrec_convert (type
, chrec
, at_stmt
);
1279 /* Convert CHREC to TYPE. When the analyzer knows the context in
1280 which the CHREC is built, it sets AT_STMT to the statement that
1281 contains the definition of the analyzed variable, otherwise the
1282 conversion is less accurate: the information is used for
1283 determining a more accurate estimation of the number of iterations.
1284 By default AT_STMT could be safely set to NULL_TREE.
1286 The following rule is always true: TREE_TYPE (chrec) ==
1287 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1288 An example of what could happen when adding two chrecs and the type
1289 of the CHREC_RIGHT is different than CHREC_LEFT is:
1291 {(uint) 0, +, (uchar) 10} +
1292 {(uint) 0, +, (uchar) 250}
1294 that would produce a wrong result if CHREC_RIGHT is not (uint):
1296 {(uint) 0, +, (uchar) 4}
1300 {(uint) 0, +, (uint) 260}
1304 chrec_convert (tree type
, tree chrec
, gimple at_stmt
)
1306 return chrec_convert_1 (type
, chrec
, at_stmt
, true);
1309 /* Convert CHREC to TYPE. When the analyzer knows the context in
1310 which the CHREC is built, it sets AT_STMT to the statement that
1311 contains the definition of the analyzed variable, otherwise the
1312 conversion is less accurate: the information is used for
1313 determining a more accurate estimation of the number of iterations.
1314 By default AT_STMT could be safely set to NULL_TREE.
1316 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1317 the rules for overflow of the given language apply (e.g., that signed
1318 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1319 tests, but also to enforce that the result follows them. */
1322 chrec_convert_1 (tree type
, tree chrec
, gimple at_stmt
,
1323 bool use_overflow_semantics
)
1329 if (automatically_generated_chrec_p (chrec
))
1332 ct
= chrec_type (chrec
);
1336 if (!evolution_function_is_affine_p (chrec
))
1339 loop
= get_chrec_loop (chrec
);
1340 base
= CHREC_LEFT (chrec
);
1341 step
= CHREC_RIGHT (chrec
);
1343 if (convert_affine_scev (loop
, type
, &base
, &step
, at_stmt
,
1344 use_overflow_semantics
))
1345 return build_polynomial_chrec (loop
->num
, base
, step
);
1347 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1349 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1350 may be more expensive. We do want to perform this optimization here
1351 though for canonicalization reasons. */
1352 if (use_overflow_semantics
1353 && (TREE_CODE (chrec
) == PLUS_EXPR
1354 || TREE_CODE (chrec
) == MINUS_EXPR
)
1355 && TREE_CODE (type
) == INTEGER_TYPE
1356 && TREE_CODE (ct
) == INTEGER_TYPE
1357 && TYPE_PRECISION (type
) > TYPE_PRECISION (ct
)
1358 && TYPE_OVERFLOW_UNDEFINED (ct
))
1359 res
= fold_build2 (TREE_CODE (chrec
), type
,
1360 fold_convert (type
, TREE_OPERAND (chrec
, 0)),
1361 fold_convert (type
, TREE_OPERAND (chrec
, 1)));
1363 res
= fold_convert (type
, chrec
);
1365 /* Don't propagate overflows. */
1366 if (CONSTANT_CLASS_P (res
))
1367 TREE_OVERFLOW (res
) = 0;
1369 /* But reject constants that don't fit in their type after conversion.
1370 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1371 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1372 and can cause problems later when computing niters of loops. Note
1373 that we don't do the check before converting because we don't want
1374 to reject conversions of negative chrecs to unsigned types. */
1375 if (TREE_CODE (res
) == INTEGER_CST
1376 && TREE_CODE (type
) == INTEGER_TYPE
1377 && !int_fits_type_p (res
, type
))
1378 res
= chrec_dont_know
;
1383 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1384 chrec if something else than what chrec_convert would do happens, NULL_TREE
1388 chrec_convert_aggressive (tree type
, tree chrec
)
1390 tree inner_type
, left
, right
, lc
, rc
, rtype
;
1392 if (automatically_generated_chrec_p (chrec
)
1393 || TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1396 inner_type
= TREE_TYPE (chrec
);
1397 if (TYPE_PRECISION (type
) > TYPE_PRECISION (inner_type
))
1400 rtype
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1402 left
= CHREC_LEFT (chrec
);
1403 right
= CHREC_RIGHT (chrec
);
1404 lc
= chrec_convert_aggressive (type
, left
);
1406 lc
= chrec_convert (type
, left
, NULL
);
1407 rc
= chrec_convert_aggressive (rtype
, right
);
1409 rc
= chrec_convert (rtype
, right
, NULL
);
1411 return build_polynomial_chrec (CHREC_VARIABLE (chrec
), lc
, rc
);
1414 /* Returns true when CHREC0 == CHREC1. */
1417 eq_evolutions_p (const_tree chrec0
, const_tree chrec1
)
1419 if (chrec0
== NULL_TREE
1420 || chrec1
== NULL_TREE
1421 || TREE_CODE (chrec0
) != TREE_CODE (chrec1
))
1424 if (chrec0
== chrec1
)
1427 switch (TREE_CODE (chrec0
))
1430 return operand_equal_p (chrec0
, chrec1
, 0);
1432 case POLYNOMIAL_CHREC
:
1433 return (CHREC_VARIABLE (chrec0
) == CHREC_VARIABLE (chrec1
)
1434 && eq_evolutions_p (CHREC_LEFT (chrec0
), CHREC_LEFT (chrec1
))
1435 && eq_evolutions_p (CHREC_RIGHT (chrec0
), CHREC_RIGHT (chrec1
)));
1441 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1442 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1443 which of these cases happens. */
1446 scev_direction (const_tree chrec
)
1450 if (!evolution_function_is_affine_p (chrec
))
1451 return EV_DIR_UNKNOWN
;
1453 step
= CHREC_RIGHT (chrec
);
1454 if (TREE_CODE (step
) != INTEGER_CST
)
1455 return EV_DIR_UNKNOWN
;
1457 if (tree_int_cst_sign_bit (step
))
1458 return EV_DIR_DECREASES
;
1460 return EV_DIR_GROWS
;
1463 /* Iterates over all the components of SCEV, and calls CBCK. */
1466 for_each_scev_op (tree
*scev
, bool (*cbck
) (tree
*, void *), void *data
)
1468 switch (TREE_CODE_LENGTH (TREE_CODE (*scev
)))
1471 for_each_scev_op (&TREE_OPERAND (*scev
, 2), cbck
, data
);
1474 for_each_scev_op (&TREE_OPERAND (*scev
, 1), cbck
, data
);
1477 for_each_scev_op (&TREE_OPERAND (*scev
, 0), cbck
, data
);
1485 /* Returns true when the operation can be part of a linear
1489 operator_is_linear (tree scev
)
1491 switch (TREE_CODE (scev
))
1494 case POLYNOMIAL_CHREC
:
1496 case POINTER_PLUS_EXPR
:
1501 case NON_LVALUE_EXPR
:
1511 /* Return true when SCEV is a linear expression. Linear expressions
1512 can contain additions, substractions and multiplications.
1513 Multiplications are restricted to constant scaling: "cst * x". */
1516 scev_is_linear_expression (tree scev
)
1519 || !operator_is_linear (scev
))
1522 if (TREE_CODE (scev
) == MULT_EXPR
)
1523 return !(tree_contains_chrecs (TREE_OPERAND (scev
, 0), NULL
)
1524 && tree_contains_chrecs (TREE_OPERAND (scev
, 1), NULL
));
1526 if (TREE_CODE (scev
) == POLYNOMIAL_CHREC
1527 && !evolution_function_is_affine_multivariate_p (scev
, CHREC_VARIABLE (scev
)))
1530 switch (TREE_CODE_LENGTH (TREE_CODE (scev
)))
1533 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1534 && scev_is_linear_expression (TREE_OPERAND (scev
, 1))
1535 && scev_is_linear_expression (TREE_OPERAND (scev
, 2));
1538 return scev_is_linear_expression (TREE_OPERAND (scev
, 0))
1539 && scev_is_linear_expression (TREE_OPERAND (scev
, 1));
1542 return scev_is_linear_expression (TREE_OPERAND (scev
, 0));
1552 /* Determines whether the expression CHREC contains only interger consts
1553 in the right parts. */
1556 evolution_function_right_is_integer_cst (const_tree chrec
)
1558 if (chrec
== NULL_TREE
)
1561 switch (TREE_CODE (chrec
))
1566 case POLYNOMIAL_CHREC
:
1567 return TREE_CODE (CHREC_RIGHT (chrec
)) == INTEGER_CST
1568 && (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
1569 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec
)));
1572 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec
, 0));