2008-07-06 Kai Tietz <kai.tietz@onevision.com>
[official-gcc.git] / gcc / tree-chrec.c
blob295fb7920c922167649267ca629cf5d009fd814a
1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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
10 version.
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
15 for more details.
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
23 variables.
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "ggc.h"
31 #include "tree.h"
32 #include "real.h"
33 #include "diagnostic.h"
34 #include "cfgloop.h"
35 #include "tree-flow.h"
36 #include "tree-chrec.h"
37 #include "tree-pass.h"
38 #include "params.h"
39 #include "tree-scalar-evolution.h"
43 /* Extended folder for chrecs. */
45 /* Determines whether CST is not a constant evolution. */
47 static inline bool
48 is_not_constant_evolution (const_tree cst)
50 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
53 /* Fold CODE for a polynomial function and a constant. */
55 static inline tree
56 chrec_fold_poly_cst (enum tree_code code,
57 tree type,
58 tree poly,
59 tree cst)
61 gcc_assert (poly);
62 gcc_assert (cst);
63 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
64 gcc_assert (!is_not_constant_evolution (cst));
65 gcc_assert (type == chrec_type (poly));
67 switch (code)
69 case PLUS_EXPR:
70 return build_polynomial_chrec
71 (CHREC_VARIABLE (poly),
72 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
73 CHREC_RIGHT (poly));
75 case MINUS_EXPR:
76 return build_polynomial_chrec
77 (CHREC_VARIABLE (poly),
78 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
79 CHREC_RIGHT (poly));
81 case MULT_EXPR:
82 return build_polynomial_chrec
83 (CHREC_VARIABLE (poly),
84 chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
85 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
87 default:
88 return chrec_dont_know;
92 /* Fold the addition of two polynomial functions. */
94 static inline tree
95 chrec_fold_plus_poly_poly (enum tree_code code,
96 tree type,
97 tree poly0,
98 tree poly1)
100 tree left, right;
101 struct loop *loop0 = get_chrec_loop (poly0);
102 struct loop *loop1 = get_chrec_loop (poly1);
103 tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type;
105 gcc_assert (poly0);
106 gcc_assert (poly1);
107 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
108 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
109 if (POINTER_TYPE_P (chrec_type (poly0)))
110 gcc_assert (chrec_type (poly1) == sizetype);
111 else
112 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
113 gcc_assert (type == chrec_type (poly0));
116 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
117 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
118 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
119 if (flow_loop_nested_p (loop0, loop1))
121 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
122 return build_polynomial_chrec
123 (CHREC_VARIABLE (poly1),
124 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
125 CHREC_RIGHT (poly1));
126 else
127 return build_polynomial_chrec
128 (CHREC_VARIABLE (poly1),
129 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
130 chrec_fold_multiply (type, CHREC_RIGHT (poly1),
131 SCALAR_FLOAT_TYPE_P (type)
132 ? build_real (type, dconstm1)
133 : build_int_cst_type (type, -1)));
136 if (flow_loop_nested_p (loop1, loop0))
138 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
139 return build_polynomial_chrec
140 (CHREC_VARIABLE (poly0),
141 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
142 CHREC_RIGHT (poly0));
143 else
144 return build_polynomial_chrec
145 (CHREC_VARIABLE (poly0),
146 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
147 CHREC_RIGHT (poly0));
150 /* This function should never be called for chrecs of loops that
151 do not belong to the same loop nest. */
152 gcc_assert (loop0 == loop1);
154 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
156 left = chrec_fold_plus
157 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
158 right = chrec_fold_plus
159 (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
161 else
163 left = chrec_fold_minus
164 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
165 right = chrec_fold_minus
166 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
169 if (chrec_zerop (right))
170 return left;
171 else
172 return build_polynomial_chrec
173 (CHREC_VARIABLE (poly0), left, right);
178 /* Fold the multiplication of two polynomial functions. */
180 static inline tree
181 chrec_fold_multiply_poly_poly (tree type,
182 tree poly0,
183 tree poly1)
185 tree t0, t1, t2;
186 int var;
187 struct loop *loop0 = get_chrec_loop (poly0);
188 struct loop *loop1 = get_chrec_loop (poly1);
190 gcc_assert (poly0);
191 gcc_assert (poly1);
192 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
193 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
194 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
195 gcc_assert (type == chrec_type (poly0));
197 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
198 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
199 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
200 if (flow_loop_nested_p (loop0, loop1))
201 /* poly0 is a constant wrt. poly1. */
202 return build_polynomial_chrec
203 (CHREC_VARIABLE (poly1),
204 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
205 CHREC_RIGHT (poly1));
207 if (flow_loop_nested_p (loop1, loop0))
208 /* poly1 is a constant wrt. poly0. */
209 return build_polynomial_chrec
210 (CHREC_VARIABLE (poly0),
211 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
212 CHREC_RIGHT (poly0));
214 gcc_assert (loop0 == loop1);
216 /* poly0 and poly1 are two polynomials in the same variable,
217 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
219 /* "a*c". */
220 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
222 /* "a*d + b*c + b*d". */
223 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
224 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
225 CHREC_RIGHT (poly0),
226 CHREC_LEFT (poly1)));
227 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
228 CHREC_RIGHT (poly0),
229 CHREC_RIGHT (poly1)));
230 /* "2*b*d". */
231 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
232 t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
233 ? build_real (type, dconst2)
234 : build_int_cst (type, 2), t2);
236 var = CHREC_VARIABLE (poly0);
237 return build_polynomial_chrec (var, t0,
238 build_polynomial_chrec (var, t1, t2));
241 /* When the operands are automatically_generated_chrec_p, the fold has
242 to respect the semantics of the operands. */
244 static inline tree
245 chrec_fold_automatically_generated_operands (tree op0,
246 tree op1)
248 if (op0 == chrec_dont_know
249 || op1 == chrec_dont_know)
250 return chrec_dont_know;
252 if (op0 == chrec_known
253 || op1 == chrec_known)
254 return chrec_known;
256 if (op0 == chrec_not_analyzed_yet
257 || op1 == chrec_not_analyzed_yet)
258 return chrec_not_analyzed_yet;
260 /* The default case produces a safe result. */
261 return chrec_dont_know;
264 /* Fold the addition of two chrecs. */
266 static tree
267 chrec_fold_plus_1 (enum tree_code code, tree type,
268 tree op0, tree op1)
270 tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
272 if (automatically_generated_chrec_p (op0)
273 || automatically_generated_chrec_p (op1))
274 return chrec_fold_automatically_generated_operands (op0, op1);
276 switch (TREE_CODE (op0))
278 case POLYNOMIAL_CHREC:
279 switch (TREE_CODE (op1))
281 case POLYNOMIAL_CHREC:
282 return chrec_fold_plus_poly_poly (code, type, op0, op1);
284 default:
285 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
286 return build_polynomial_chrec
287 (CHREC_VARIABLE (op0),
288 chrec_fold_plus (type, CHREC_LEFT (op0), op1),
289 CHREC_RIGHT (op0));
290 else
291 return build_polynomial_chrec
292 (CHREC_VARIABLE (op0),
293 chrec_fold_minus (type, CHREC_LEFT (op0), op1),
294 CHREC_RIGHT (op0));
297 default:
298 switch (TREE_CODE (op1))
300 case POLYNOMIAL_CHREC:
301 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
302 return build_polynomial_chrec
303 (CHREC_VARIABLE (op1),
304 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
305 CHREC_RIGHT (op1));
306 else
307 return build_polynomial_chrec
308 (CHREC_VARIABLE (op1),
309 chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
310 chrec_fold_multiply (type, CHREC_RIGHT (op1),
311 SCALAR_FLOAT_TYPE_P (type)
312 ? build_real (type, dconstm1)
313 : build_int_cst_type (type, -1)));
315 default:
317 int size = 0;
318 if ((tree_contains_chrecs (op0, &size)
319 || tree_contains_chrecs (op1, &size))
320 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
321 return build2 (code, type, op0, op1);
322 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
323 return fold_build2 (code, type,
324 fold_convert (type, op0),
325 fold_convert (op1_type, op1));
326 else
327 return chrec_dont_know;
333 /* Fold the addition of two chrecs. */
335 tree
336 chrec_fold_plus (tree type,
337 tree op0,
338 tree op1)
340 enum tree_code code;
341 if (automatically_generated_chrec_p (op0)
342 || automatically_generated_chrec_p (op1))
343 return chrec_fold_automatically_generated_operands (op0, op1);
345 if (integer_zerop (op0))
346 return chrec_convert (type, op1, NULL_TREE);
347 if (integer_zerop (op1))
348 return chrec_convert (type, op0, NULL_TREE);
350 if (POINTER_TYPE_P (type))
351 code = POINTER_PLUS_EXPR;
352 else
353 code = PLUS_EXPR;
355 return chrec_fold_plus_1 (code, type, op0, op1);
358 /* Fold the subtraction of two chrecs. */
360 tree
361 chrec_fold_minus (tree type,
362 tree op0,
363 tree op1)
365 if (automatically_generated_chrec_p (op0)
366 || automatically_generated_chrec_p (op1))
367 return chrec_fold_automatically_generated_operands (op0, op1);
369 if (integer_zerop (op1))
370 return op0;
372 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
375 /* Fold the multiplication of two chrecs. */
377 tree
378 chrec_fold_multiply (tree type,
379 tree op0,
380 tree op1)
382 if (automatically_generated_chrec_p (op0)
383 || automatically_generated_chrec_p (op1))
384 return chrec_fold_automatically_generated_operands (op0, op1);
386 switch (TREE_CODE (op0))
388 case POLYNOMIAL_CHREC:
389 switch (TREE_CODE (op1))
391 case POLYNOMIAL_CHREC:
392 return chrec_fold_multiply_poly_poly (type, op0, op1);
394 default:
395 if (integer_onep (op1))
396 return op0;
397 if (integer_zerop (op1))
398 return build_int_cst (type, 0);
400 return build_polynomial_chrec
401 (CHREC_VARIABLE (op0),
402 chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
403 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
406 default:
407 if (integer_onep (op0))
408 return op1;
410 if (integer_zerop (op0))
411 return build_int_cst (type, 0);
413 switch (TREE_CODE (op1))
415 case POLYNOMIAL_CHREC:
416 return build_polynomial_chrec
417 (CHREC_VARIABLE (op1),
418 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
419 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
421 default:
422 if (integer_onep (op1))
423 return op0;
424 if (integer_zerop (op1))
425 return build_int_cst (type, 0);
426 return fold_build2 (MULT_EXPR, type, op0, op1);
433 /* Operations. */
435 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
436 calculation overflows, otherwise return C(n,k) with type TYPE. */
438 static tree
439 tree_fold_binomial (tree type, tree n, unsigned int k)
441 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
442 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
443 unsigned int i;
444 tree res;
446 /* Handle the most frequent cases. */
447 if (k == 0)
448 return build_int_cst (type, 1);
449 if (k == 1)
450 return fold_convert (type, n);
452 /* Check that k <= n. */
453 if (TREE_INT_CST_HIGH (n) == 0
454 && TREE_INT_CST_LOW (n) < k)
455 return NULL_TREE;
457 /* Numerator = n. */
458 lnum = TREE_INT_CST_LOW (n);
459 hnum = TREE_INT_CST_HIGH (n);
461 /* Denominator = 2. */
462 ldenom = 2;
463 hdenom = 0;
465 /* Index = Numerator-1. */
466 if (lnum == 0)
468 hidx = hnum - 1;
469 lidx = ~ (unsigned HOST_WIDE_INT) 0;
471 else
473 hidx = hnum;
474 lidx = lnum - 1;
477 /* Numerator = Numerator*Index = n*(n-1). */
478 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
479 return NULL_TREE;
481 for (i = 3; i <= k; i++)
483 /* Index--. */
484 if (lidx == 0)
486 hidx--;
487 lidx = ~ (unsigned HOST_WIDE_INT) 0;
489 else
490 lidx--;
492 /* Numerator *= Index. */
493 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
494 return NULL_TREE;
496 /* Denominator *= i. */
497 mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
500 /* Result = Numerator / Denominator. */
501 div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
502 &lres, &hres, &ldum, &hdum);
504 res = build_int_cst_wide (type, lres, hres);
505 return int_fits_type_p (res, type) ? res : NULL_TREE;
508 /* Helper function. Use the Newton's interpolating formula for
509 evaluating the value of the evolution function. */
511 static tree
512 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
514 tree arg0, arg1, binomial_n_k;
515 tree type = TREE_TYPE (chrec);
516 struct loop *var_loop = get_loop (var);
518 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
519 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
520 chrec = CHREC_LEFT (chrec);
522 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
523 && CHREC_VARIABLE (chrec) == var)
525 arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
526 if (arg1 == chrec_dont_know)
527 return chrec_dont_know;
528 binomial_n_k = tree_fold_binomial (type, n, k);
529 if (!binomial_n_k)
530 return chrec_dont_know;
531 arg0 = fold_build2 (MULT_EXPR, type,
532 CHREC_LEFT (chrec), binomial_n_k);
533 return chrec_fold_plus (type, arg0, arg1);
536 binomial_n_k = tree_fold_binomial (type, n, k);
537 if (!binomial_n_k)
538 return chrec_dont_know;
540 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
543 /* Evaluates "CHREC (X)" when the varying variable is VAR.
544 Example: Given the following parameters,
546 var = 1
547 chrec = {3, +, 4}_1
548 x = 10
550 The result is given by the Newton's interpolating formula:
551 3 * \binom{10}{0} + 4 * \binom{10}{1}.
554 tree
555 chrec_apply (unsigned var,
556 tree chrec,
557 tree x)
559 tree type = chrec_type (chrec);
560 tree res = chrec_dont_know;
562 if (automatically_generated_chrec_p (chrec)
563 || automatically_generated_chrec_p (x)
565 /* When the symbols are defined in an outer loop, it is possible
566 to symbolically compute the apply, since the symbols are
567 constants with respect to the varying loop. */
568 || chrec_contains_symbols_defined_in_loop (chrec, var))
569 return chrec_dont_know;
571 if (dump_file && (dump_flags & TDF_DETAILS))
572 fprintf (dump_file, "(chrec_apply \n");
574 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
575 x = build_real_from_int_cst (type, x);
577 if (evolution_function_is_affine_p (chrec))
579 /* "{a, +, b} (x)" -> "a + b*x". */
580 x = chrec_convert_rhs (type, x, NULL_TREE);
581 res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
582 if (!integer_zerop (CHREC_LEFT (chrec)))
583 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
586 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
587 res = chrec;
589 else if (TREE_CODE (x) == INTEGER_CST
590 && tree_int_cst_sgn (x) == 1)
591 /* testsuite/.../ssa-chrec-38.c. */
592 res = chrec_evaluate (var, chrec, x, 0);
593 else
594 res = chrec_dont_know;
596 if (dump_file && (dump_flags & TDF_DETAILS))
598 fprintf (dump_file, " (varying_loop = %d\n", var);
599 fprintf (dump_file, ")\n (chrec = ");
600 print_generic_expr (dump_file, chrec, 0);
601 fprintf (dump_file, ")\n (x = ");
602 print_generic_expr (dump_file, x, 0);
603 fprintf (dump_file, ")\n (res = ");
604 print_generic_expr (dump_file, res, 0);
605 fprintf (dump_file, "))\n");
608 return res;
611 /* Replaces the initial condition in CHREC with INIT_COND. */
613 tree
614 chrec_replace_initial_condition (tree chrec,
615 tree init_cond)
617 if (automatically_generated_chrec_p (chrec))
618 return chrec;
620 gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
622 switch (TREE_CODE (chrec))
624 case POLYNOMIAL_CHREC:
625 return build_polynomial_chrec
626 (CHREC_VARIABLE (chrec),
627 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
628 CHREC_RIGHT (chrec));
630 default:
631 return init_cond;
635 /* Returns the initial condition of a given CHREC. */
637 tree
638 initial_condition (tree chrec)
640 if (automatically_generated_chrec_p (chrec))
641 return chrec;
643 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
644 return initial_condition (CHREC_LEFT (chrec));
645 else
646 return chrec;
649 /* Returns a univariate function that represents the evolution in
650 LOOP_NUM. Mask the evolution of any other loop. */
652 tree
653 hide_evolution_in_other_loops_than_loop (tree chrec,
654 unsigned loop_num)
656 struct loop *loop = get_loop (loop_num), *chloop;
657 if (automatically_generated_chrec_p (chrec))
658 return chrec;
660 switch (TREE_CODE (chrec))
662 case POLYNOMIAL_CHREC:
663 chloop = get_chrec_loop (chrec);
665 if (chloop == loop)
666 return build_polynomial_chrec
667 (loop_num,
668 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
669 loop_num),
670 CHREC_RIGHT (chrec));
672 else if (flow_loop_nested_p (chloop, loop))
673 /* There is no evolution in this loop. */
674 return initial_condition (chrec);
676 else
678 gcc_assert (flow_loop_nested_p (loop, chloop));
679 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
680 loop_num);
683 default:
684 return chrec;
688 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
689 true, otherwise returns the initial condition in LOOP_NUM. */
691 static tree
692 chrec_component_in_loop_num (tree chrec,
693 unsigned loop_num,
694 bool right)
696 tree component;
697 struct loop *loop = get_loop (loop_num), *chloop;
699 if (automatically_generated_chrec_p (chrec))
700 return chrec;
702 switch (TREE_CODE (chrec))
704 case POLYNOMIAL_CHREC:
705 chloop = get_chrec_loop (chrec);
707 if (chloop == loop)
709 if (right)
710 component = CHREC_RIGHT (chrec);
711 else
712 component = CHREC_LEFT (chrec);
714 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
715 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
716 return component;
718 else
719 return build_polynomial_chrec
720 (loop_num,
721 chrec_component_in_loop_num (CHREC_LEFT (chrec),
722 loop_num,
723 right),
724 component);
727 else if (flow_loop_nested_p (chloop, loop))
728 /* There is no evolution part in this loop. */
729 return NULL_TREE;
731 else
733 gcc_assert (flow_loop_nested_p (loop, chloop));
734 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
735 loop_num,
736 right);
739 default:
740 if (right)
741 return NULL_TREE;
742 else
743 return chrec;
747 /* Returns the evolution part in LOOP_NUM. Example: the call
748 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
749 {1, +, 2}_1 */
751 tree
752 evolution_part_in_loop_num (tree chrec,
753 unsigned loop_num)
755 return chrec_component_in_loop_num (chrec, loop_num, true);
758 /* Returns the initial condition in LOOP_NUM. Example: the call
759 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
760 {0, +, 1}_1 */
762 tree
763 initial_condition_in_loop_num (tree chrec,
764 unsigned loop_num)
766 return chrec_component_in_loop_num (chrec, loop_num, false);
769 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
770 This function is essentially used for setting the evolution to
771 chrec_dont_know, for example after having determined that it is
772 impossible to say how many times a loop will execute. */
774 tree
775 reset_evolution_in_loop (unsigned loop_num,
776 tree chrec,
777 tree new_evol)
779 struct loop *loop = get_loop (loop_num);
781 if (POINTER_TYPE_P (chrec_type (chrec)))
782 gcc_assert (sizetype == chrec_type (new_evol));
783 else
784 gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
786 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
787 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
789 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
790 new_evol);
791 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
792 new_evol);
793 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
794 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
795 left, right);
798 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
799 && CHREC_VARIABLE (chrec) == loop_num)
800 chrec = CHREC_LEFT (chrec);
802 return build_polynomial_chrec (loop_num, chrec, new_evol);
805 /* Merges two evolution functions that were found by following two
806 alternate paths of a conditional expression. */
808 tree
809 chrec_merge (tree chrec1,
810 tree chrec2)
812 if (chrec1 == chrec_dont_know
813 || chrec2 == chrec_dont_know)
814 return chrec_dont_know;
816 if (chrec1 == chrec_known
817 || chrec2 == chrec_known)
818 return chrec_known;
820 if (chrec1 == chrec_not_analyzed_yet)
821 return chrec2;
822 if (chrec2 == chrec_not_analyzed_yet)
823 return chrec1;
825 if (eq_evolutions_p (chrec1, chrec2))
826 return chrec1;
828 return chrec_dont_know;
833 /* Observers. */
835 /* Helper function for is_multivariate_chrec. */
837 static bool
838 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
840 if (chrec == NULL_TREE)
841 return false;
843 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
845 if (CHREC_VARIABLE (chrec) != rec_var)
846 return true;
847 else
848 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
849 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
851 else
852 return false;
855 /* Determine whether the given chrec is multivariate or not. */
857 bool
858 is_multivariate_chrec (const_tree chrec)
860 if (chrec == NULL_TREE)
861 return false;
863 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
864 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
865 CHREC_VARIABLE (chrec))
866 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
867 CHREC_VARIABLE (chrec)));
868 else
869 return false;
872 /* Determines whether the chrec contains symbolic names or not. */
874 bool
875 chrec_contains_symbols (const_tree chrec)
877 int i, n;
879 if (chrec == NULL_TREE)
880 return false;
882 if (TREE_CODE (chrec) == SSA_NAME
883 || TREE_CODE (chrec) == VAR_DECL
884 || TREE_CODE (chrec) == PARM_DECL
885 || TREE_CODE (chrec) == FUNCTION_DECL
886 || TREE_CODE (chrec) == LABEL_DECL
887 || TREE_CODE (chrec) == RESULT_DECL
888 || TREE_CODE (chrec) == FIELD_DECL)
889 return true;
891 n = TREE_OPERAND_LENGTH (chrec);
892 for (i = 0; i < n; i++)
893 if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
894 return true;
895 return false;
898 /* Determines whether the chrec contains undetermined coefficients. */
900 bool
901 chrec_contains_undetermined (const_tree chrec)
903 int i, n;
905 if (chrec == chrec_dont_know)
906 return true;
908 if (chrec == NULL_TREE)
909 return false;
911 n = TREE_OPERAND_LENGTH (chrec);
912 for (i = 0; i < n; i++)
913 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
914 return true;
915 return false;
918 /* Determines whether the tree EXPR contains chrecs, and increment
919 SIZE if it is not a NULL pointer by an estimation of the depth of
920 the tree. */
922 bool
923 tree_contains_chrecs (const_tree expr, int *size)
925 int i, n;
927 if (expr == NULL_TREE)
928 return false;
930 if (size)
931 (*size)++;
933 if (tree_is_chrec (expr))
934 return true;
936 n = TREE_OPERAND_LENGTH (expr);
937 for (i = 0; i < n; i++)
938 if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
939 return true;
940 return false;
943 /* Recursive helper function. */
945 static bool
946 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
948 if (evolution_function_is_constant_p (chrec))
949 return true;
951 if (TREE_CODE (chrec) == SSA_NAME
952 && (loopnum == 0
953 || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
954 return true;
956 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
958 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
959 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
960 loopnum)
961 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
962 loopnum))
963 return false;
964 return true;
967 switch (TREE_OPERAND_LENGTH (chrec))
969 case 2:
970 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
971 loopnum))
972 return false;
974 case 1:
975 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
976 loopnum))
977 return false;
978 return true;
980 default:
981 return false;
984 return false;
987 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
989 bool
990 evolution_function_is_invariant_p (tree chrec, int loopnum)
992 return evolution_function_is_invariant_rec_p (chrec, loopnum);
995 /* Determine whether the given tree is an affine multivariate
996 evolution. */
998 bool
999 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1001 if (chrec == NULL_TREE)
1002 return false;
1004 switch (TREE_CODE (chrec))
1006 case POLYNOMIAL_CHREC:
1007 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1009 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1010 return true;
1011 else
1013 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1014 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1015 != CHREC_VARIABLE (chrec)
1016 && evolution_function_is_affine_multivariate_p
1017 (CHREC_RIGHT (chrec), loopnum))
1018 return true;
1019 else
1020 return false;
1023 else
1025 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1026 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1027 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1028 && evolution_function_is_affine_multivariate_p
1029 (CHREC_LEFT (chrec), loopnum))
1030 return true;
1031 else
1032 return false;
1035 default:
1036 return false;
1040 /* Determine whether the given tree is a function in zero or one
1041 variables. */
1043 bool
1044 evolution_function_is_univariate_p (const_tree chrec)
1046 if (chrec == NULL_TREE)
1047 return true;
1049 switch (TREE_CODE (chrec))
1051 case POLYNOMIAL_CHREC:
1052 switch (TREE_CODE (CHREC_LEFT (chrec)))
1054 case POLYNOMIAL_CHREC:
1055 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1056 return false;
1057 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1058 return false;
1059 break;
1061 default:
1062 break;
1065 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1067 case POLYNOMIAL_CHREC:
1068 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1069 return false;
1070 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1071 return false;
1072 break;
1074 default:
1075 break;
1078 default:
1079 return true;
1083 /* Returns the number of variables of CHREC. Example: the call
1084 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1086 unsigned
1087 nb_vars_in_chrec (tree chrec)
1089 if (chrec == NULL_TREE)
1090 return 0;
1092 switch (TREE_CODE (chrec))
1094 case POLYNOMIAL_CHREC:
1095 return 1 + nb_vars_in_chrec
1096 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1098 default:
1099 return 0;
1103 /* Returns true if TYPE is a type in that we cannot directly perform
1104 arithmetics, even though it is a scalar type. */
1106 static bool
1107 avoid_arithmetics_in_type_p (const_tree type)
1109 /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1110 in the subtype, but a base type must be used, and the result then can
1111 be casted to the subtype. */
1112 if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1113 return true;
1115 return false;
1118 static tree chrec_convert_1 (tree, tree, tree, bool);
1120 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1121 the scev corresponds to. AT_STMT is the statement at that the scev is
1122 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1123 the rules for overflow of the given language apply (e.g., that signed
1124 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1125 tests, but also to enforce that the result follows them. Returns true if the
1126 conversion succeeded, false otherwise. */
1128 bool
1129 convert_affine_scev (struct loop *loop, tree type,
1130 tree *base, tree *step, tree at_stmt,
1131 bool use_overflow_semantics)
1133 tree ct = TREE_TYPE (*step);
1134 bool enforce_overflow_semantics;
1135 bool must_check_src_overflow, must_check_rslt_overflow;
1136 tree new_base, new_step;
1137 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1139 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1140 if (avoid_arithmetics_in_type_p (type))
1141 return false;
1143 /* In general,
1144 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1145 but we must check some assumptions.
1147 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1148 of CT is smaller than the precision of TYPE. For example, when we
1149 cast unsigned char [254, +, 1] to unsigned, the values on left side
1150 are 254, 255, 0, 1, ..., but those on the right side are
1151 254, 255, 256, 257, ...
1152 2) In case that we must also preserve the fact that signed ivs do not
1153 overflow, we must additionally check that the new iv does not wrap.
1154 For example, unsigned char [125, +, 1] casted to signed char could
1155 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1156 which would confuse optimizers that assume that this does not
1157 happen. */
1158 must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1160 enforce_overflow_semantics = (use_overflow_semantics
1161 && nowrap_type_p (type));
1162 if (enforce_overflow_semantics)
1164 /* We can avoid checking whether the result overflows in the following
1165 cases:
1167 -- must_check_src_overflow is true, and the range of TYPE is superset
1168 of the range of CT -- i.e., in all cases except if CT signed and
1169 TYPE unsigned.
1170 -- both CT and TYPE have the same precision and signedness, and we
1171 verify instead that the source does not overflow (this may be
1172 easier than verifying it for the result, as we may use the
1173 information about the semantics of overflow in CT). */
1174 if (must_check_src_overflow)
1176 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1177 must_check_rslt_overflow = true;
1178 else
1179 must_check_rslt_overflow = false;
1181 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1182 && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1184 must_check_rslt_overflow = false;
1185 must_check_src_overflow = true;
1187 else
1188 must_check_rslt_overflow = true;
1190 else
1191 must_check_rslt_overflow = false;
1193 if (must_check_src_overflow
1194 && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1195 use_overflow_semantics))
1196 return false;
1198 new_base = chrec_convert_1 (type, *base, at_stmt,
1199 use_overflow_semantics);
1200 /* The step must be sign extended, regardless of the signedness
1201 of CT and TYPE. This only needs to be handled specially when
1202 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1203 (with values 100, 99, 98, ...) from becoming signed or unsigned
1204 [100, +, 255] with values 100, 355, ...; the sign-extension is
1205 performed by default when CT is signed. */
1206 new_step = *step;
1207 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1208 new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1209 use_overflow_semantics);
1210 new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
1212 if (automatically_generated_chrec_p (new_base)
1213 || automatically_generated_chrec_p (new_step))
1214 return false;
1216 if (must_check_rslt_overflow
1217 /* Note that in this case we cannot use the fact that signed variables
1218 do not overflow, as this is what we are verifying for the new iv. */
1219 && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1220 return false;
1222 *base = new_base;
1223 *step = new_step;
1224 return true;
1228 /* Convert CHREC for the right hand side of a CREC.
1229 The increment for a pointer type is always sizetype. */
1230 tree
1231 chrec_convert_rhs (tree type, tree chrec, tree at_stmt)
1233 if (POINTER_TYPE_P (type))
1234 type = sizetype;
1235 return chrec_convert (type, chrec, at_stmt);
1238 /* Convert CHREC to TYPE. When the analyzer knows the context in
1239 which the CHREC is built, it sets AT_STMT to the statement that
1240 contains the definition of the analyzed variable, otherwise the
1241 conversion is less accurate: the information is used for
1242 determining a more accurate estimation of the number of iterations.
1243 By default AT_STMT could be safely set to NULL_TREE.
1245 The following rule is always true: TREE_TYPE (chrec) ==
1246 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1247 An example of what could happen when adding two chrecs and the type
1248 of the CHREC_RIGHT is different than CHREC_LEFT is:
1250 {(uint) 0, +, (uchar) 10} +
1251 {(uint) 0, +, (uchar) 250}
1253 that would produce a wrong result if CHREC_RIGHT is not (uint):
1255 {(uint) 0, +, (uchar) 4}
1257 instead of
1259 {(uint) 0, +, (uint) 260}
1262 tree
1263 chrec_convert (tree type, tree chrec, tree at_stmt)
1265 return chrec_convert_1 (type, chrec, at_stmt, true);
1268 /* Convert CHREC to TYPE. When the analyzer knows the context in
1269 which the CHREC is built, it sets AT_STMT to the statement that
1270 contains the definition of the analyzed variable, otherwise the
1271 conversion is less accurate: the information is used for
1272 determining a more accurate estimation of the number of iterations.
1273 By default AT_STMT could be safely set to NULL_TREE.
1275 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1276 the rules for overflow of the given language apply (e.g., that signed
1277 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1278 tests, but also to enforce that the result follows them. */
1280 static tree
1281 chrec_convert_1 (tree type, tree chrec, tree at_stmt,
1282 bool use_overflow_semantics)
1284 tree ct, res;
1285 tree base, step;
1286 struct loop *loop;
1288 if (automatically_generated_chrec_p (chrec))
1289 return chrec;
1291 ct = chrec_type (chrec);
1292 if (ct == type)
1293 return chrec;
1295 if (!evolution_function_is_affine_p (chrec))
1296 goto keep_cast;
1298 loop = get_chrec_loop (chrec);
1299 base = CHREC_LEFT (chrec);
1300 step = CHREC_RIGHT (chrec);
1302 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1303 use_overflow_semantics))
1304 return build_polynomial_chrec (loop->num, base, step);
1306 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1307 keep_cast:
1308 res = fold_convert (type, chrec);
1310 /* Don't propagate overflows. */
1311 if (CONSTANT_CLASS_P (res))
1312 TREE_OVERFLOW (res) = 0;
1314 /* But reject constants that don't fit in their type after conversion.
1315 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1316 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1317 and can cause problems later when computing niters of loops. Note
1318 that we don't do the check before converting because we don't want
1319 to reject conversions of negative chrecs to unsigned types. */
1320 if (TREE_CODE (res) == INTEGER_CST
1321 && TREE_CODE (type) == INTEGER_TYPE
1322 && !int_fits_type_p (res, type))
1323 res = chrec_dont_know;
1325 return res;
1328 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1329 chrec if something else than what chrec_convert would do happens, NULL_TREE
1330 otherwise. */
1332 tree
1333 chrec_convert_aggressive (tree type, tree chrec)
1335 tree inner_type, left, right, lc, rc, rtype;
1337 if (automatically_generated_chrec_p (chrec)
1338 || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1339 return NULL_TREE;
1341 inner_type = TREE_TYPE (chrec);
1342 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1343 return NULL_TREE;
1345 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1346 if (avoid_arithmetics_in_type_p (type))
1347 return NULL_TREE;
1349 rtype = POINTER_TYPE_P (type) ? sizetype : type;
1351 left = CHREC_LEFT (chrec);
1352 right = CHREC_RIGHT (chrec);
1353 lc = chrec_convert_aggressive (type, left);
1354 if (!lc)
1355 lc = chrec_convert (type, left, NULL_TREE);
1356 rc = chrec_convert_aggressive (rtype, right);
1357 if (!rc)
1358 rc = chrec_convert (rtype, right, NULL_TREE);
1360 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1363 /* Returns true when CHREC0 == CHREC1. */
1365 bool
1366 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1368 if (chrec0 == NULL_TREE
1369 || chrec1 == NULL_TREE
1370 || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1371 return false;
1373 if (chrec0 == chrec1)
1374 return true;
1376 switch (TREE_CODE (chrec0))
1378 case INTEGER_CST:
1379 return operand_equal_p (chrec0, chrec1, 0);
1381 case POLYNOMIAL_CHREC:
1382 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1383 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1384 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1385 default:
1386 return false;
1390 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1391 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1392 which of these cases happens. */
1394 enum ev_direction
1395 scev_direction (const_tree chrec)
1397 const_tree step;
1399 if (!evolution_function_is_affine_p (chrec))
1400 return EV_DIR_UNKNOWN;
1402 step = CHREC_RIGHT (chrec);
1403 if (TREE_CODE (step) != INTEGER_CST)
1404 return EV_DIR_UNKNOWN;
1406 if (tree_int_cst_sign_bit (step))
1407 return EV_DIR_DECREASES;
1408 else
1409 return EV_DIR_GROWS;