1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
34 #include "diagnostic.h"
36 #include "tree-chrec.h"
37 #include "tree-pass.h"
40 /* This part will be removed once the merging is finished. */
44 /* The following trees are unique elements. Thus the comparison of
45 another element to these elements should be done on the pointer to
46 these trees, and not on their value. */
48 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
49 tree chrec_not_analyzed_yet
;
51 /* Reserved to the cases where the analyzer has detected an
52 undecidable property at compile time. */
55 /* When the analyzer has detected that a property will never
56 happen, then it qualifies it with chrec_known. */
59 /* Empty hook. Will be replaced by the main function from
60 tree-scalar-evolution.c. */
63 count_ev_in_wider_type (tree foo ATTRIBUTE_UNUSED
,
64 tree bar ATTRIBUTE_UNUSED
)
69 /* Empty hook. Will be replaced by the main function from
70 tree-scalar-evolution.c. */
73 chrec_contains_symbols_defined_in_loop (tree chrec ATTRIBUTE_UNUSED
,
74 unsigned loop_nb ATTRIBUTE_UNUSED
)
82 /* Extended folder for chrecs. */
84 /* Determines whether CST is not a constant evolution. */
87 is_not_constant_evolution (tree cst
)
89 return (TREE_CODE (cst
) == POLYNOMIAL_CHREC
);
92 /* Fold CODE for a polynomial function and a constant. */
95 chrec_fold_poly_cst (enum tree_code code
,
100 #if defined ENABLE_CHECKING
101 if (poly
== NULL_TREE
103 || TREE_CODE (poly
) != POLYNOMIAL_CHREC
104 || is_not_constant_evolution (cst
))
111 return build_polynomial_chrec
112 (CHREC_VARIABLE (poly
),
113 chrec_fold_plus (type
, CHREC_LEFT (poly
), cst
),
117 return build_polynomial_chrec
118 (CHREC_VARIABLE (poly
),
119 chrec_fold_minus (type
, CHREC_LEFT (poly
), cst
),
123 return build_polynomial_chrec
124 (CHREC_VARIABLE (poly
),
125 chrec_fold_multiply (type
, CHREC_LEFT (poly
), cst
),
126 chrec_fold_multiply (type
, CHREC_RIGHT (poly
), cst
));
129 return chrec_dont_know
;
133 /* Fold the addition of two polynomial functions. */
136 chrec_fold_plus_poly_poly (enum tree_code code
,
143 #if defined ENABLE_CHECKING
144 if (poly0
== NULL_TREE
145 || poly1
== NULL_TREE
146 || TREE_CODE (poly0
) != POLYNOMIAL_CHREC
147 || TREE_CODE (poly1
) != POLYNOMIAL_CHREC
)
152 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
153 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
154 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
155 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
157 if (code
== PLUS_EXPR
)
158 return build_polynomial_chrec
159 (CHREC_VARIABLE (poly1
),
160 chrec_fold_plus (type
, poly0
, CHREC_LEFT (poly1
)),
161 CHREC_RIGHT (poly1
));
163 return build_polynomial_chrec
164 (CHREC_VARIABLE (poly1
),
165 chrec_fold_minus (type
, poly0
, CHREC_LEFT (poly1
)),
166 chrec_fold_multiply (type
, CHREC_RIGHT (poly1
),
167 convert (type
, integer_minus_one_node
)));
170 if (CHREC_VARIABLE (poly0
) > CHREC_VARIABLE (poly1
))
172 if (code
== PLUS_EXPR
)
173 return build_polynomial_chrec
174 (CHREC_VARIABLE (poly0
),
175 chrec_fold_plus (type
, CHREC_LEFT (poly0
), poly1
),
176 CHREC_RIGHT (poly0
));
178 return build_polynomial_chrec
179 (CHREC_VARIABLE (poly0
),
180 chrec_fold_minus (type
, CHREC_LEFT (poly0
), poly1
),
181 CHREC_RIGHT (poly0
));
184 if (code
== PLUS_EXPR
)
186 left
= chrec_fold_plus
187 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
188 right
= chrec_fold_plus
189 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
193 left
= chrec_fold_minus
194 (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
));
195 right
= chrec_fold_minus
196 (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
));
199 if (chrec_zerop (right
))
202 return build_polynomial_chrec
203 (CHREC_VARIABLE (poly0
), left
, right
);
208 /* Fold the multiplication of two polynomial functions. */
211 chrec_fold_multiply_poly_poly (tree type
,
215 #if defined ENABLE_CHECKING
216 if (poly0
== NULL_TREE
217 || poly1
== NULL_TREE
218 || TREE_CODE (poly0
) != POLYNOMIAL_CHREC
219 || TREE_CODE (poly1
) != POLYNOMIAL_CHREC
)
223 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
224 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
225 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
226 if (CHREC_VARIABLE (poly0
) < CHREC_VARIABLE (poly1
))
227 /* poly0 is a constant wrt. poly1. */
228 return build_polynomial_chrec
229 (CHREC_VARIABLE (poly1
),
230 chrec_fold_multiply (type
, CHREC_LEFT (poly1
), poly0
),
231 CHREC_RIGHT (poly1
));
233 if (CHREC_VARIABLE (poly1
) < CHREC_VARIABLE (poly0
))
234 /* poly1 is a constant wrt. poly0. */
235 return build_polynomial_chrec
236 (CHREC_VARIABLE (poly0
),
237 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), poly1
),
238 CHREC_RIGHT (poly0
));
240 /* poly0 and poly1 are two polynomials in the same variable,
241 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
243 build_polynomial_chrec
244 (CHREC_VARIABLE (poly0
),
245 build_polynomial_chrec
246 (CHREC_VARIABLE (poly0
),
249 chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_LEFT (poly1
)),
251 /* "a*d + b*c + b*d". */
253 (type
, chrec_fold_multiply (type
, CHREC_LEFT (poly0
), CHREC_RIGHT (poly1
)),
257 chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_LEFT (poly1
)),
258 chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
))))),
262 (type
, build_int_2 (2, 0),
263 chrec_fold_multiply (type
, CHREC_RIGHT (poly0
), CHREC_RIGHT (poly1
))));
266 /* When the operands are automatically_generated_chrec_p, the fold has
267 to respect the semantics of the operands. */
270 chrec_fold_automatically_generated_operands (tree op0
,
273 if (op0
== chrec_dont_know
274 || op1
== chrec_dont_know
)
275 return chrec_dont_know
;
277 if (op0
== chrec_known
278 || op1
== chrec_known
)
281 if (op0
== chrec_not_analyzed_yet
282 || op1
== chrec_not_analyzed_yet
)
283 return chrec_not_analyzed_yet
;
285 /* The default case produces a safe result. */
286 return chrec_dont_know
;
289 /* Fold the addition of two chrecs. */
292 chrec_fold_plus_1 (enum tree_code code
,
297 if (automatically_generated_chrec_p (op0
)
298 || automatically_generated_chrec_p (op1
))
299 return chrec_fold_automatically_generated_operands (op0
, op1
);
301 switch (TREE_CODE (op0
))
303 case POLYNOMIAL_CHREC
:
304 switch (TREE_CODE (op1
))
306 case POLYNOMIAL_CHREC
:
307 return chrec_fold_plus_poly_poly (code
, type
, op0
, op1
);
310 if (code
== PLUS_EXPR
)
311 return build_polynomial_chrec
312 (CHREC_VARIABLE (op0
),
313 chrec_fold_plus (type
, CHREC_LEFT (op0
), op1
),
316 return build_polynomial_chrec
317 (CHREC_VARIABLE (op0
),
318 chrec_fold_minus (type
, CHREC_LEFT (op0
), op1
),
323 switch (TREE_CODE (op1
))
325 case POLYNOMIAL_CHREC
:
326 if (code
== PLUS_EXPR
)
327 return build_polynomial_chrec
328 (CHREC_VARIABLE (op1
),
329 chrec_fold_plus (type
, op0
, CHREC_LEFT (op1
)),
332 return build_polynomial_chrec
333 (CHREC_VARIABLE (op1
),
334 chrec_fold_minus (type
, op0
, CHREC_LEFT (op1
)),
335 chrec_fold_multiply (type
, CHREC_RIGHT (op1
),
337 integer_minus_one_node
)));
340 if (tree_contains_chrecs (op0
)
341 || tree_contains_chrecs (op1
))
342 return build (code
, type
, op0
, op1
);
344 return fold (build (code
, type
, op0
, op1
));
349 /* Fold the addition of two chrecs. */
352 chrec_fold_plus (tree type
,
356 if (integer_zerop (op0
))
358 if (integer_zerop (op1
))
361 return chrec_fold_plus_1 (PLUS_EXPR
, type
, op0
, op1
);
364 /* Fold the subtraction of two chrecs. */
367 chrec_fold_minus (tree type
,
371 if (integer_zerop (op1
))
374 return chrec_fold_plus_1 (MINUS_EXPR
, type
, op0
, op1
);
377 /* Fold the multiplication of two chrecs. */
380 chrec_fold_multiply (tree type
,
384 if (automatically_generated_chrec_p (op0
)
385 || automatically_generated_chrec_p (op1
))
386 return chrec_fold_automatically_generated_operands (op0
, op1
);
388 switch (TREE_CODE (op0
))
390 case POLYNOMIAL_CHREC
:
391 switch (TREE_CODE (op1
))
393 case POLYNOMIAL_CHREC
:
394 return chrec_fold_multiply_poly_poly (type
, op0
, op1
);
397 if (integer_onep (op1
))
399 if (integer_zerop (op1
))
400 return convert (type
, integer_zero_node
);
402 return build_polynomial_chrec
403 (CHREC_VARIABLE (op0
),
404 chrec_fold_multiply (type
, CHREC_LEFT (op0
), op1
),
405 chrec_fold_multiply (type
, CHREC_RIGHT (op0
), op1
));
409 if (integer_onep (op0
))
412 if (integer_zerop (op0
))
413 return convert (type
, integer_zero_node
);
415 switch (TREE_CODE (op1
))
417 case POLYNOMIAL_CHREC
:
418 return build_polynomial_chrec
419 (CHREC_VARIABLE (op1
),
420 chrec_fold_multiply (type
, CHREC_LEFT (op1
), op0
),
421 chrec_fold_multiply (type
, CHREC_RIGHT (op1
), op0
));
424 if (integer_onep (op1
))
426 if (integer_zerop (op1
))
427 return convert (type
, integer_zero_node
);
428 return fold (build (MULT_EXPR
, type
, op0
, op1
));
440 tree_fold_factorial (tree f
)
442 if (tree_int_cst_sgn (f
) <= 0)
443 return integer_one_node
;
446 (build (MULT_EXPR
, integer_type_node
, f
,
447 tree_fold_factorial (fold (build (MINUS_EXPR
, integer_type_node
,
448 f
, integer_one_node
)))));
451 /* The binomial coefficient. */
454 tree_fold_binomial (tree n
,
458 (build (EXACT_DIV_EXPR
, integer_type_node
, tree_fold_factorial (n
),
459 fold (build (MULT_EXPR
, integer_type_node
,
460 tree_fold_factorial (k
),
462 (fold (build (MINUS_EXPR
, integer_type_node
,
466 /* Helper function. Use the Newton's interpolating formula for
467 evaluating the value of the evolution function. */
470 chrec_evaluate (unsigned var
,
475 tree type
= chrec_type (chrec
);
476 tree binomial_n_k
= tree_fold_binomial (n
, k
);
478 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
480 if (CHREC_VARIABLE (chrec
) > var
)
481 return chrec_evaluate (var
, CHREC_LEFT (chrec
), n
, k
);
483 if (CHREC_VARIABLE (chrec
) == var
)
484 return chrec_fold_plus
486 fold (build (MULT_EXPR
, type
, binomial_n_k
, CHREC_LEFT (chrec
))),
487 chrec_evaluate (var
, CHREC_RIGHT (chrec
), n
,
488 fold (build (PLUS_EXPR
, type
, k
, integer_one_node
))));
490 return fold (build (MULT_EXPR
, type
, binomial_n_k
, chrec
));
493 return fold (build (MULT_EXPR
, type
, binomial_n_k
, chrec
));
496 /* Evaluates "CHREC (X)" when the varying variable is VAR.
497 Example: Given the following parameters,
503 The result is given by the Newton's interpolating formula:
504 3 * \binom{10}{0} + 4 * \binom{10}{1}.
508 chrec_apply (unsigned var
,
512 tree type
= chrec_type (chrec
);
513 tree res
= chrec_dont_know
;
515 if (automatically_generated_chrec_p (chrec
)
516 || automatically_generated_chrec_p (x
)
518 /* When the symbols are defined in an outer loop, it is possible
519 to symbolically compute the apply, since the symbols are
520 constants with respect to the varying loop. */
521 || chrec_contains_symbols_defined_in_loop (chrec
, var
)
522 || chrec_contains_symbols (x
))
523 return chrec_dont_know
;
525 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
526 fprintf (dump_file
, "(chrec_apply \n");
528 if (evolution_function_is_affine_p (chrec
))
530 /* "{a, +, b} (x)" -> "a + b*x". */
531 if (TREE_CODE (CHREC_LEFT (chrec
)) == INTEGER_CST
532 && integer_zerop (CHREC_LEFT (chrec
)))
533 res
= chrec_fold_multiply (type
, CHREC_RIGHT (chrec
), x
);
536 res
= chrec_fold_plus (type
, CHREC_LEFT (chrec
),
537 chrec_fold_multiply (type
,
538 CHREC_RIGHT (chrec
), x
));
541 else if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
544 else if (TREE_CODE (x
) == INTEGER_CST
545 && tree_int_cst_sgn (x
) == 1)
546 /* testsuite/.../ssa-chrec-38.c. */
547 res
= chrec_evaluate (var
, chrec
, x
, integer_zero_node
);
550 res
= chrec_dont_know
;
552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
554 fprintf (dump_file
, " (varying_loop = %d\n", var
);
555 fprintf (dump_file
, ")\n (chrec = ");
556 print_generic_expr (dump_file
, chrec
, 0);
557 fprintf (dump_file
, ")\n (x = ");
558 print_generic_expr (dump_file
, x
, 0);
559 fprintf (dump_file
, ")\n (res = ");
560 print_generic_expr (dump_file
, res
, 0);
561 fprintf (dump_file
, "))\n");
567 /* Replaces the initial condition in CHREC with INIT_COND. */
570 chrec_replace_initial_condition (tree chrec
,
573 if (automatically_generated_chrec_p (chrec
))
576 switch (TREE_CODE (chrec
))
578 case POLYNOMIAL_CHREC
:
579 return build_polynomial_chrec
580 (CHREC_VARIABLE (chrec
),
581 chrec_replace_initial_condition (CHREC_LEFT (chrec
), init_cond
),
582 CHREC_RIGHT (chrec
));
589 /* Returns the initial condition of a given CHREC. */
592 initial_condition (tree chrec
)
594 if (automatically_generated_chrec_p (chrec
))
597 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
598 return initial_condition (CHREC_LEFT (chrec
));
603 /* Returns a univariate function that represents the evolution in
604 LOOP_NUM. Mask the evolution of any other loop. */
607 hide_evolution_in_other_loops_than_loop (tree chrec
,
610 if (automatically_generated_chrec_p (chrec
))
613 switch (TREE_CODE (chrec
))
615 case POLYNOMIAL_CHREC
:
616 if (CHREC_VARIABLE (chrec
) == loop_num
)
617 return build_polynomial_chrec
619 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
621 CHREC_RIGHT (chrec
));
623 else if (CHREC_VARIABLE (chrec
) < loop_num
)
624 /* There is no evolution in this loop. */
625 return initial_condition (chrec
);
628 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec
),
636 /* Returns the evolution part in LOOP_NUM. Example: the call
637 get_evolution_in_loop (1, {{0, +, 1}_1, +, 2}_1) returns
641 evolution_part_in_loop_num (tree chrec
,
644 if (automatically_generated_chrec_p (chrec
))
647 switch (TREE_CODE (chrec
))
649 case POLYNOMIAL_CHREC
:
650 if (CHREC_VARIABLE (chrec
) == loop_num
)
652 if (TREE_CODE (CHREC_LEFT (chrec
)) != POLYNOMIAL_CHREC
653 || CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
))
654 return CHREC_RIGHT (chrec
);
657 return build_polynomial_chrec
659 evolution_part_in_loop_num (CHREC_LEFT (chrec
), loop_num
),
660 CHREC_RIGHT (chrec
));
663 else if (CHREC_VARIABLE (chrec
) < loop_num
)
664 /* There is no evolution part in this loop. */
668 return evolution_part_in_loop_num (CHREC_LEFT (chrec
), loop_num
);
675 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
676 This function is essentially used for setting the evolution to
677 chrec_dont_know, for example after having determined that it is
678 impossible to say how many times a loop will execute. */
681 reset_evolution_in_loop (unsigned loop_num
,
685 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
686 && CHREC_VARIABLE (chrec
) > loop_num
)
689 build_int_2 (CHREC_VARIABLE (chrec
), 0),
690 reset_evolution_in_loop (loop_num
, CHREC_LEFT (chrec
), new_evol
),
691 reset_evolution_in_loop (loop_num
, CHREC_RIGHT (chrec
), new_evol
));
693 while (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
694 && CHREC_VARIABLE (chrec
) == loop_num
)
695 chrec
= CHREC_LEFT (chrec
);
697 return build_polynomial_chrec (loop_num
, chrec
, new_evol
);
700 /* Merges two evolution functions that were found by following two
701 alternate paths of a conditional expression. */
704 chrec_merge (tree chrec1
,
707 if (chrec1
== chrec_dont_know
708 || chrec2
== chrec_dont_know
)
709 return chrec_dont_know
;
711 if (chrec1
== chrec_known
712 || chrec2
== chrec_known
)
715 if (chrec1
== chrec_not_analyzed_yet
)
717 if (chrec2
== chrec_not_analyzed_yet
)
720 if (operand_equal_p (chrec1
, chrec2
, 0))
723 return chrec_dont_know
;
730 /* Helper function for is_multivariate_chrec. */
733 is_multivariate_chrec_rec (tree chrec
, unsigned int rec_var
)
735 if (chrec
== NULL_TREE
)
738 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
740 if (CHREC_VARIABLE (chrec
) != rec_var
)
743 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
), rec_var
)
744 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
), rec_var
));
750 /* Determine whether the given chrec is multivariate or not. */
753 is_multivariate_chrec (tree chrec
)
755 if (chrec
== NULL_TREE
)
758 if (TREE_CODE (chrec
) == POLYNOMIAL_CHREC
)
759 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec
),
760 CHREC_VARIABLE (chrec
))
761 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec
),
762 CHREC_VARIABLE (chrec
)));
767 /* Determines whether the chrec contains symbolic names or not. */
770 chrec_contains_symbols (tree chrec
)
772 if (chrec
== NULL_TREE
)
775 if (TREE_CODE (chrec
) == SSA_NAME
776 || TREE_CODE (chrec
) == VAR_DECL
777 || TREE_CODE (chrec
) == PARM_DECL
778 || TREE_CODE (chrec
) == FUNCTION_DECL
779 || TREE_CODE (chrec
) == LABEL_DECL
780 || TREE_CODE (chrec
) == RESULT_DECL
781 || TREE_CODE (chrec
) == FIELD_DECL
)
784 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
787 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 2)))
791 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 1)))
795 if (chrec_contains_symbols (TREE_OPERAND (chrec
, 0)))
803 /* Determines whether the chrec contains undetermined coefficients. */
806 chrec_contains_undetermined (tree chrec
)
808 if (chrec
== chrec_dont_know
809 || chrec
== chrec_not_analyzed_yet
810 || chrec
== NULL_TREE
)
813 switch (TREE_CODE_LENGTH (TREE_CODE (chrec
)))
816 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 2)))
820 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 1)))
824 if (chrec_contains_undetermined (TREE_OPERAND (chrec
, 0)))
832 /* Determines whether the tree EXPR contains chrecs. */
835 tree_contains_chrecs (tree expr
)
837 if (expr
== NULL_TREE
)
840 if (tree_is_chrec (expr
))
843 switch (TREE_CODE_LENGTH (TREE_CODE (expr
)))
846 if (tree_contains_chrecs (TREE_OPERAND (expr
, 2)))
850 if (tree_contains_chrecs (TREE_OPERAND (expr
, 1)))
854 if (tree_contains_chrecs (TREE_OPERAND (expr
, 0)))
862 /* Determine whether the given tree is an affine multivariate
866 evolution_function_is_affine_multivariate_p (tree chrec
)
868 if (chrec
== NULL_TREE
)
871 switch (TREE_CODE (chrec
))
873 case POLYNOMIAL_CHREC
:
874 if (evolution_function_is_constant_p (CHREC_LEFT (chrec
)))
876 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
880 if (TREE_CODE (CHREC_RIGHT (chrec
)) == POLYNOMIAL_CHREC
881 && CHREC_VARIABLE (CHREC_RIGHT (chrec
))
882 != CHREC_VARIABLE (chrec
)
883 && evolution_function_is_affine_multivariate_p
884 (CHREC_RIGHT (chrec
)))
892 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
))
893 && TREE_CODE (CHREC_LEFT (chrec
)) == POLYNOMIAL_CHREC
894 && CHREC_VARIABLE (CHREC_LEFT (chrec
)) != CHREC_VARIABLE (chrec
)
895 && evolution_function_is_affine_multivariate_p
896 (CHREC_LEFT (chrec
)))
907 /* Determine whether the given tree is a function in zero or one
911 evolution_function_is_univariate_p (tree chrec
)
913 if (chrec
== NULL_TREE
)
916 switch (TREE_CODE (chrec
))
918 case POLYNOMIAL_CHREC
:
919 switch (TREE_CODE (CHREC_LEFT (chrec
)))
921 case POLYNOMIAL_CHREC
:
922 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_LEFT (chrec
)))
924 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec
)))
932 switch (TREE_CODE (CHREC_RIGHT (chrec
)))
934 case POLYNOMIAL_CHREC
:
935 if (CHREC_VARIABLE (chrec
) != CHREC_VARIABLE (CHREC_RIGHT (chrec
)))
937 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec
)))
952 /* Convert the initial condition of chrec to type. */
955 chrec_convert (tree type
,
960 if (automatically_generated_chrec_p (chrec
))
963 ct
= chrec_type (chrec
);
967 if (TYPE_PRECISION (ct
) < TYPE_PRECISION (type
))
968 return count_ev_in_wider_type (type
, chrec
);
970 switch (TREE_CODE (chrec
))
972 case POLYNOMIAL_CHREC
:
973 return build_polynomial_chrec (CHREC_VARIABLE (chrec
),
977 CHREC_RIGHT (chrec
)));
981 tree res
= convert (type
, chrec
);
983 /* Don't propagate overflows. */
984 TREE_OVERFLOW (res
) = 0;
985 if (TREE_CODE_CLASS (TREE_CODE (res
)) == 'c')
986 TREE_CONSTANT_OVERFLOW (res
) = 0;
992 /* Returns the type of the chrec. */
995 chrec_type (tree chrec
)
997 if (automatically_generated_chrec_p (chrec
))
1000 return TREE_TYPE (chrec
);
1003 extern void initialize_scalar_evolutions_analyzer (void);
1008 initialize_scalar_evolutions_analyzer (void)
1010 /* The elements below are unique. */
1011 if (chrec_dont_know
== NULL_TREE
)
1013 chrec_not_analyzed_yet
= NULL_TREE
;
1014 chrec_dont_know
= make_node (SCEV_NOT_KNOWN
);
1015 chrec_known
= make_node (SCEV_KNOWN
);
1016 TREE_TYPE (chrec_dont_know
) = NULL_TREE
;
1017 TREE_TYPE (chrec_known
) = NULL_TREE
;