* invoke.texi (mstringop-strategy): Add missing "byte_loop" value.
[official-gcc.git] / gcc / tree-chrec.c
blob01d0bf9217ae3cd648fc94d6ff627f05c409a5b9
1 /* Chains of recurrences.
2 Copyright (C) 2003, 2004, 2005, 2006 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
22 /* This file implements operations on chains of recurrences. Chains
23 of recurrences are used for modeling evolution functions of scalar
24 variables.
27 #include "config.h"
28 #include "system.h"
29 #include "coretypes.h"
30 #include "tm.h"
31 #include "ggc.h"
32 #include "tree.h"
33 #include "real.h"
34 #include "diagnostic.h"
35 #include "cfgloop.h"
36 #include "tree-flow.h"
37 #include "tree-chrec.h"
38 #include "tree-pass.h"
39 #include "params.h"
40 #include "tree-scalar-evolution.h"
44 /* Extended folder for chrecs. */
46 /* Determines whether CST is not a constant evolution. */
48 static inline bool
49 is_not_constant_evolution (tree cst)
51 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
54 /* Fold CODE for a polynomial function and a constant. */
56 static inline tree
57 chrec_fold_poly_cst (enum tree_code code,
58 tree type,
59 tree poly,
60 tree cst)
62 gcc_assert (poly);
63 gcc_assert (cst);
64 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
65 gcc_assert (!is_not_constant_evolution (cst));
66 gcc_assert (type == chrec_type (poly));
68 switch (code)
70 case PLUS_EXPR:
71 return build_polynomial_chrec
72 (CHREC_VARIABLE (poly),
73 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
74 CHREC_RIGHT (poly));
76 case MINUS_EXPR:
77 return build_polynomial_chrec
78 (CHREC_VARIABLE (poly),
79 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
80 CHREC_RIGHT (poly));
82 case MULT_EXPR:
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));
88 default:
89 return chrec_dont_know;
93 /* Fold the addition of two polynomial functions. */
95 static inline tree
96 chrec_fold_plus_poly_poly (enum tree_code code,
97 tree type,
98 tree poly0,
99 tree poly1)
101 tree left, right;
103 gcc_assert (poly0);
104 gcc_assert (poly1);
105 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
106 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
107 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
108 gcc_assert (type == chrec_type (poly0));
111 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
112 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
113 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
114 if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
116 if (code == PLUS_EXPR)
117 return build_polynomial_chrec
118 (CHREC_VARIABLE (poly1),
119 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
120 CHREC_RIGHT (poly1));
121 else
122 return build_polynomial_chrec
123 (CHREC_VARIABLE (poly1),
124 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
125 chrec_fold_multiply (type, CHREC_RIGHT (poly1),
126 SCALAR_FLOAT_TYPE_P (type)
127 ? build_real (type, dconstm1)
128 : build_int_cst_type (type, -1)));
131 if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
133 if (code == PLUS_EXPR)
134 return build_polynomial_chrec
135 (CHREC_VARIABLE (poly0),
136 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
137 CHREC_RIGHT (poly0));
138 else
139 return build_polynomial_chrec
140 (CHREC_VARIABLE (poly0),
141 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
142 CHREC_RIGHT (poly0));
145 if (code == PLUS_EXPR)
147 left = chrec_fold_plus
148 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
149 right = chrec_fold_plus
150 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
152 else
154 left = chrec_fold_minus
155 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
156 right = chrec_fold_minus
157 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
160 if (chrec_zerop (right))
161 return left;
162 else
163 return build_polynomial_chrec
164 (CHREC_VARIABLE (poly0), left, right);
169 /* Fold the multiplication of two polynomial functions. */
171 static inline tree
172 chrec_fold_multiply_poly_poly (tree type,
173 tree poly0,
174 tree poly1)
176 tree t0, t1, t2;
177 int var;
179 gcc_assert (poly0);
180 gcc_assert (poly1);
181 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
182 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
183 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
184 gcc_assert (type == chrec_type (poly0));
186 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
187 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
188 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
189 if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
190 /* poly0 is a constant wrt. poly1. */
191 return build_polynomial_chrec
192 (CHREC_VARIABLE (poly1),
193 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
194 CHREC_RIGHT (poly1));
196 if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
197 /* poly1 is a constant wrt. poly0. */
198 return build_polynomial_chrec
199 (CHREC_VARIABLE (poly0),
200 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
201 CHREC_RIGHT (poly0));
203 /* poly0 and poly1 are two polynomials in the same variable,
204 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
206 /* "a*c". */
207 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
209 /* "a*d + b*c + b*d". */
210 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
211 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
212 CHREC_RIGHT (poly0),
213 CHREC_LEFT (poly1)));
214 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
215 CHREC_RIGHT (poly0),
216 CHREC_RIGHT (poly1)));
217 /* "2*b*d". */
218 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
219 t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
220 ? build_real (type, dconst2)
221 : build_int_cst (type, 2), t2);
223 var = CHREC_VARIABLE (poly0);
224 return build_polynomial_chrec (var, t0,
225 build_polynomial_chrec (var, t1, t2));
228 /* When the operands are automatically_generated_chrec_p, the fold has
229 to respect the semantics of the operands. */
231 static inline tree
232 chrec_fold_automatically_generated_operands (tree op0,
233 tree op1)
235 if (op0 == chrec_dont_know
236 || op1 == chrec_dont_know)
237 return chrec_dont_know;
239 if (op0 == chrec_known
240 || op1 == chrec_known)
241 return chrec_known;
243 if (op0 == chrec_not_analyzed_yet
244 || op1 == chrec_not_analyzed_yet)
245 return chrec_not_analyzed_yet;
247 /* The default case produces a safe result. */
248 return chrec_dont_know;
251 /* Fold the addition of two chrecs. */
253 static tree
254 chrec_fold_plus_1 (enum tree_code code, tree type,
255 tree op0, tree op1)
257 if (automatically_generated_chrec_p (op0)
258 || automatically_generated_chrec_p (op1))
259 return chrec_fold_automatically_generated_operands (op0, op1);
261 switch (TREE_CODE (op0))
263 case POLYNOMIAL_CHREC:
264 switch (TREE_CODE (op1))
266 case POLYNOMIAL_CHREC:
267 return chrec_fold_plus_poly_poly (code, type, op0, op1);
269 default:
270 if (code == PLUS_EXPR)
271 return build_polynomial_chrec
272 (CHREC_VARIABLE (op0),
273 chrec_fold_plus (type, CHREC_LEFT (op0), op1),
274 CHREC_RIGHT (op0));
275 else
276 return build_polynomial_chrec
277 (CHREC_VARIABLE (op0),
278 chrec_fold_minus (type, CHREC_LEFT (op0), op1),
279 CHREC_RIGHT (op0));
282 default:
283 switch (TREE_CODE (op1))
285 case POLYNOMIAL_CHREC:
286 if (code == PLUS_EXPR)
287 return build_polynomial_chrec
288 (CHREC_VARIABLE (op1),
289 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
290 CHREC_RIGHT (op1));
291 else
292 return build_polynomial_chrec
293 (CHREC_VARIABLE (op1),
294 chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
295 chrec_fold_multiply (type, CHREC_RIGHT (op1),
296 SCALAR_FLOAT_TYPE_P (type)
297 ? build_real (type, dconstm1)
298 : build_int_cst_type (type, -1)));
300 default:
302 int size = 0;
303 if ((tree_contains_chrecs (op0, &size)
304 || tree_contains_chrecs (op1, &size))
305 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
306 return build2 (code, type, op0, op1);
307 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
308 return fold_build2 (code, type,
309 fold_convert (type, op0),
310 fold_convert (type, op1));
311 else
312 return chrec_dont_know;
318 /* Fold the addition of two chrecs. */
320 tree
321 chrec_fold_plus (tree type,
322 tree op0,
323 tree op1)
325 if (automatically_generated_chrec_p (op0)
326 || automatically_generated_chrec_p (op1))
327 return chrec_fold_automatically_generated_operands (op0, op1);
329 if (integer_zerop (op0))
330 return op1;
331 if (integer_zerop (op1))
332 return op0;
334 return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
337 /* Fold the subtraction of two chrecs. */
339 tree
340 chrec_fold_minus (tree type,
341 tree op0,
342 tree op1)
344 if (automatically_generated_chrec_p (op0)
345 || automatically_generated_chrec_p (op1))
346 return chrec_fold_automatically_generated_operands (op0, op1);
348 if (integer_zerop (op1))
349 return op0;
351 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
354 /* Fold the multiplication of two chrecs. */
356 tree
357 chrec_fold_multiply (tree type,
358 tree op0,
359 tree op1)
361 if (automatically_generated_chrec_p (op0)
362 || automatically_generated_chrec_p (op1))
363 return chrec_fold_automatically_generated_operands (op0, op1);
365 switch (TREE_CODE (op0))
367 case POLYNOMIAL_CHREC:
368 switch (TREE_CODE (op1))
370 case POLYNOMIAL_CHREC:
371 return chrec_fold_multiply_poly_poly (type, op0, op1);
373 default:
374 if (integer_onep (op1))
375 return op0;
376 if (integer_zerop (op1))
377 return build_int_cst (type, 0);
379 return build_polynomial_chrec
380 (CHREC_VARIABLE (op0),
381 chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
382 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
385 default:
386 if (integer_onep (op0))
387 return op1;
389 if (integer_zerop (op0))
390 return build_int_cst (type, 0);
392 switch (TREE_CODE (op1))
394 case POLYNOMIAL_CHREC:
395 return build_polynomial_chrec
396 (CHREC_VARIABLE (op1),
397 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
398 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
400 default:
401 if (integer_onep (op1))
402 return op0;
403 if (integer_zerop (op1))
404 return build_int_cst (type, 0);
405 return fold_build2 (MULT_EXPR, type, op0, op1);
412 /* Operations. */
414 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
415 calculation overflows, otherwise return C(n,k) with type TYPE. */
417 static tree
418 tree_fold_binomial (tree type, tree n, unsigned int k)
420 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
421 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
422 unsigned int i;
423 tree res;
425 /* Handle the most frequent cases. */
426 if (k == 0)
427 return build_int_cst (type, 1);
428 if (k == 1)
429 return fold_convert (type, n);
431 /* Check that k <= n. */
432 if (TREE_INT_CST_HIGH (n) == 0
433 && TREE_INT_CST_LOW (n) < k)
434 return NULL_TREE;
436 /* Numerator = n. */
437 lnum = TREE_INT_CST_LOW (n);
438 hnum = TREE_INT_CST_HIGH (n);
440 /* Denominator = 2. */
441 ldenom = 2;
442 hdenom = 0;
444 /* Index = Numerator-1. */
445 if (lnum == 0)
447 hidx = hnum - 1;
448 lidx = ~ (unsigned HOST_WIDE_INT) 0;
450 else
452 hidx = hnum;
453 lidx = lnum - 1;
456 /* Numerator = Numerator*Index = n*(n-1). */
457 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
458 return NULL_TREE;
460 for (i = 3; i <= k; i++)
462 /* Index--. */
463 if (lidx == 0)
465 hidx--;
466 lidx = ~ (unsigned HOST_WIDE_INT) 0;
468 else
469 lidx--;
471 /* Numerator *= Index. */
472 if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
473 return NULL_TREE;
475 /* Denominator *= i. */
476 mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
479 /* Result = Numerator / Denominator. */
480 div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
481 &lres, &hres, &ldum, &hdum);
483 res = build_int_cst_wide (type, lres, hres);
484 return int_fits_type_p (res, type) ? res : NULL_TREE;
487 /* Helper function. Use the Newton's interpolating formula for
488 evaluating the value of the evolution function. */
490 static tree
491 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
493 tree arg0, arg1, binomial_n_k;
494 tree type = TREE_TYPE (chrec);
496 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
497 && CHREC_VARIABLE (chrec) > var)
498 chrec = CHREC_LEFT (chrec);
500 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
501 && CHREC_VARIABLE (chrec) == var)
503 arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
504 if (arg0 == chrec_dont_know)
505 return chrec_dont_know;
506 binomial_n_k = tree_fold_binomial (type, n, k);
507 if (!binomial_n_k)
508 return chrec_dont_know;
509 arg1 = fold_build2 (MULT_EXPR, type,
510 CHREC_LEFT (chrec), binomial_n_k);
511 return chrec_fold_plus (type, arg0, arg1);
514 binomial_n_k = tree_fold_binomial (type, n, k);
515 if (!binomial_n_k)
516 return chrec_dont_know;
518 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
521 /* Evaluates "CHREC (X)" when the varying variable is VAR.
522 Example: Given the following parameters,
524 var = 1
525 chrec = {3, +, 4}_1
526 x = 10
528 The result is given by the Newton's interpolating formula:
529 3 * \binom{10}{0} + 4 * \binom{10}{1}.
532 tree
533 chrec_apply (unsigned var,
534 tree chrec,
535 tree x)
537 tree type = chrec_type (chrec);
538 tree res = chrec_dont_know;
540 if (automatically_generated_chrec_p (chrec)
541 || automatically_generated_chrec_p (x)
543 /* When the symbols are defined in an outer loop, it is possible
544 to symbolically compute the apply, since the symbols are
545 constants with respect to the varying loop. */
546 || chrec_contains_symbols_defined_in_loop (chrec, var))
547 return chrec_dont_know;
549 if (dump_file && (dump_flags & TDF_DETAILS))
550 fprintf (dump_file, "(chrec_apply \n");
552 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
553 x = build_real_from_int_cst (type, x);
555 if (evolution_function_is_affine_p (chrec))
557 /* "{a, +, b} (x)" -> "a + b*x". */
558 x = chrec_convert (type, x, NULL_TREE);
559 res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
560 if (!integer_zerop (CHREC_LEFT (chrec)))
561 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
564 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
565 res = chrec;
567 else if (TREE_CODE (x) == INTEGER_CST
568 && tree_int_cst_sgn (x) == 1)
569 /* testsuite/.../ssa-chrec-38.c. */
570 res = chrec_evaluate (var, chrec, x, 0);
571 else
572 res = chrec_dont_know;
574 if (dump_file && (dump_flags & TDF_DETAILS))
576 fprintf (dump_file, " (varying_loop = %d\n", var);
577 fprintf (dump_file, ")\n (chrec = ");
578 print_generic_expr (dump_file, chrec, 0);
579 fprintf (dump_file, ")\n (x = ");
580 print_generic_expr (dump_file, x, 0);
581 fprintf (dump_file, ")\n (res = ");
582 print_generic_expr (dump_file, res, 0);
583 fprintf (dump_file, "))\n");
586 return res;
589 /* Replaces the initial condition in CHREC with INIT_COND. */
591 tree
592 chrec_replace_initial_condition (tree chrec,
593 tree init_cond)
595 if (automatically_generated_chrec_p (chrec))
596 return chrec;
598 gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
600 switch (TREE_CODE (chrec))
602 case POLYNOMIAL_CHREC:
603 return build_polynomial_chrec
604 (CHREC_VARIABLE (chrec),
605 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
606 CHREC_RIGHT (chrec));
608 default:
609 return init_cond;
613 /* Returns the initial condition of a given CHREC. */
615 tree
616 initial_condition (tree chrec)
618 if (automatically_generated_chrec_p (chrec))
619 return chrec;
621 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
622 return initial_condition (CHREC_LEFT (chrec));
623 else
624 return chrec;
627 /* Returns a univariate function that represents the evolution in
628 LOOP_NUM. Mask the evolution of any other loop. */
630 tree
631 hide_evolution_in_other_loops_than_loop (tree chrec,
632 unsigned loop_num)
634 if (automatically_generated_chrec_p (chrec))
635 return chrec;
637 switch (TREE_CODE (chrec))
639 case POLYNOMIAL_CHREC:
640 if (CHREC_VARIABLE (chrec) == loop_num)
641 return build_polynomial_chrec
642 (loop_num,
643 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
644 loop_num),
645 CHREC_RIGHT (chrec));
647 else if (CHREC_VARIABLE (chrec) < loop_num)
648 /* There is no evolution in this loop. */
649 return initial_condition (chrec);
651 else
652 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
653 loop_num);
655 default:
656 return chrec;
660 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
661 true, otherwise returns the initial condition in LOOP_NUM. */
663 static tree
664 chrec_component_in_loop_num (tree chrec,
665 unsigned loop_num,
666 bool right)
668 tree component;
670 if (automatically_generated_chrec_p (chrec))
671 return chrec;
673 switch (TREE_CODE (chrec))
675 case POLYNOMIAL_CHREC:
676 if (CHREC_VARIABLE (chrec) == loop_num)
678 if (right)
679 component = CHREC_RIGHT (chrec);
680 else
681 component = CHREC_LEFT (chrec);
683 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
684 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
685 return component;
687 else
688 return build_polynomial_chrec
689 (loop_num,
690 chrec_component_in_loop_num (CHREC_LEFT (chrec),
691 loop_num,
692 right),
693 component);
696 else if (CHREC_VARIABLE (chrec) < loop_num)
697 /* There is no evolution part in this loop. */
698 return NULL_TREE;
700 else
701 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
702 loop_num,
703 right);
705 default:
706 if (right)
707 return NULL_TREE;
708 else
709 return chrec;
713 /* Returns the evolution part in LOOP_NUM. Example: the call
714 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
715 {1, +, 2}_1 */
717 tree
718 evolution_part_in_loop_num (tree chrec,
719 unsigned loop_num)
721 return chrec_component_in_loop_num (chrec, loop_num, true);
724 /* Returns the initial condition in LOOP_NUM. Example: the call
725 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
726 {0, +, 1}_1 */
728 tree
729 initial_condition_in_loop_num (tree chrec,
730 unsigned loop_num)
732 return chrec_component_in_loop_num (chrec, loop_num, false);
735 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
736 This function is essentially used for setting the evolution to
737 chrec_dont_know, for example after having determined that it is
738 impossible to say how many times a loop will execute. */
740 tree
741 reset_evolution_in_loop (unsigned loop_num,
742 tree chrec,
743 tree new_evol)
745 gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
747 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
748 && CHREC_VARIABLE (chrec) > loop_num)
750 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
751 new_evol);
752 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
753 new_evol);
754 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
755 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
756 left, right);
759 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
760 && CHREC_VARIABLE (chrec) == loop_num)
761 chrec = CHREC_LEFT (chrec);
763 return build_polynomial_chrec (loop_num, chrec, new_evol);
766 /* Merges two evolution functions that were found by following two
767 alternate paths of a conditional expression. */
769 tree
770 chrec_merge (tree chrec1,
771 tree chrec2)
773 if (chrec1 == chrec_dont_know
774 || chrec2 == chrec_dont_know)
775 return chrec_dont_know;
777 if (chrec1 == chrec_known
778 || chrec2 == chrec_known)
779 return chrec_known;
781 if (chrec1 == chrec_not_analyzed_yet)
782 return chrec2;
783 if (chrec2 == chrec_not_analyzed_yet)
784 return chrec1;
786 if (eq_evolutions_p (chrec1, chrec2))
787 return chrec1;
789 return chrec_dont_know;
794 /* Observers. */
796 /* Helper function for is_multivariate_chrec. */
798 static bool
799 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
801 if (chrec == NULL_TREE)
802 return false;
804 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
806 if (CHREC_VARIABLE (chrec) != rec_var)
807 return true;
808 else
809 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
810 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
812 else
813 return false;
816 /* Determine whether the given chrec is multivariate or not. */
818 bool
819 is_multivariate_chrec (tree chrec)
821 if (chrec == NULL_TREE)
822 return false;
824 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
825 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
826 CHREC_VARIABLE (chrec))
827 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
828 CHREC_VARIABLE (chrec)));
829 else
830 return false;
833 /* Determines whether the chrec contains symbolic names or not. */
835 bool
836 chrec_contains_symbols (tree chrec)
838 if (chrec == NULL_TREE)
839 return false;
841 if (TREE_CODE (chrec) == SSA_NAME
842 || TREE_CODE (chrec) == VAR_DECL
843 || TREE_CODE (chrec) == PARM_DECL
844 || TREE_CODE (chrec) == FUNCTION_DECL
845 || TREE_CODE (chrec) == LABEL_DECL
846 || TREE_CODE (chrec) == RESULT_DECL
847 || TREE_CODE (chrec) == FIELD_DECL)
848 return true;
850 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
852 case 3:
853 if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
854 return true;
856 case 2:
857 if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
858 return true;
860 case 1:
861 if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
862 return true;
864 default:
865 return false;
869 /* Determines whether the chrec contains undetermined coefficients. */
871 bool
872 chrec_contains_undetermined (tree chrec)
874 if (chrec == chrec_dont_know
875 || chrec == chrec_not_analyzed_yet
876 || chrec == NULL_TREE)
877 return true;
879 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
881 case 3:
882 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
883 return true;
885 case 2:
886 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
887 return true;
889 case 1:
890 if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
891 return true;
893 default:
894 return false;
898 /* Determines whether the tree EXPR contains chrecs, and increment
899 SIZE if it is not a NULL pointer by an estimation of the depth of
900 the tree. */
902 bool
903 tree_contains_chrecs (tree expr, int *size)
905 if (expr == NULL_TREE)
906 return false;
908 if (size)
909 (*size)++;
911 if (tree_is_chrec (expr))
912 return true;
914 switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
916 case 3:
917 if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
918 return true;
920 case 2:
921 if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
922 return true;
924 case 1:
925 if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
926 return true;
928 default:
929 return false;
933 /* Recursive helper function. */
935 static bool
936 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
938 if (evolution_function_is_constant_p (chrec))
939 return true;
941 if (TREE_CODE (chrec) == SSA_NAME
942 && expr_invariant_in_loop_p (get_loop (loopnum), chrec))
943 return true;
945 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
947 if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
948 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
949 loopnum)
950 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
951 loopnum))
952 return false;
953 return true;
956 switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
958 case 2:
959 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
960 loopnum))
961 return false;
963 case 1:
964 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
965 loopnum))
966 return false;
967 return true;
969 default:
970 return false;
973 return false;
976 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
978 bool
979 evolution_function_is_invariant_p (tree chrec, int loopnum)
981 if (evolution_function_is_constant_p (chrec))
982 return true;
984 if (current_loops != NULL)
985 return evolution_function_is_invariant_rec_p (chrec, loopnum);
987 return false;
990 /* Determine whether the given tree is an affine multivariate
991 evolution. */
993 bool
994 evolution_function_is_affine_multivariate_p (tree chrec)
996 if (chrec == NULL_TREE)
997 return false;
999 switch (TREE_CODE (chrec))
1001 case POLYNOMIAL_CHREC:
1002 if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
1004 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
1005 return true;
1006 else
1008 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1009 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1010 != CHREC_VARIABLE (chrec)
1011 && evolution_function_is_affine_multivariate_p
1012 (CHREC_RIGHT (chrec)))
1013 return true;
1014 else
1015 return false;
1018 else
1020 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1021 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1022 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1023 && evolution_function_is_affine_multivariate_p
1024 (CHREC_LEFT (chrec)))
1025 return true;
1026 else
1027 return false;
1030 default:
1031 return false;
1035 /* Determine whether the given tree is a function in zero or one
1036 variables. */
1038 bool
1039 evolution_function_is_univariate_p (tree chrec)
1041 if (chrec == NULL_TREE)
1042 return true;
1044 switch (TREE_CODE (chrec))
1046 case POLYNOMIAL_CHREC:
1047 switch (TREE_CODE (CHREC_LEFT (chrec)))
1049 case POLYNOMIAL_CHREC:
1050 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1051 return false;
1052 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1053 return false;
1054 break;
1056 default:
1057 break;
1060 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1062 case POLYNOMIAL_CHREC:
1063 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1064 return false;
1065 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1066 return false;
1067 break;
1069 default:
1070 break;
1073 default:
1074 return true;
1078 /* Returns the number of variables of CHREC. Example: the call
1079 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1081 unsigned
1082 nb_vars_in_chrec (tree chrec)
1084 if (chrec == NULL_TREE)
1085 return 0;
1087 switch (TREE_CODE (chrec))
1089 case POLYNOMIAL_CHREC:
1090 return 1 + nb_vars_in_chrec
1091 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1093 default:
1094 return 0;
1098 /* Returns true if TYPE is a type in that we cannot directly perform
1099 arithmetics, even though it is a scalar type. */
1101 static bool
1102 avoid_arithmetics_in_type_p (tree type)
1104 /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1105 in the subtype, but a base type must be used, and the result then can
1106 be casted to the subtype. */
1107 if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1108 return true;
1110 return false;
1113 static tree chrec_convert_1 (tree, tree, tree, bool);
1115 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1116 the scev corresponds to. AT_STMT is the statement at that the scev is
1117 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
1118 the rules for overflow of the given language apply (e.g., that signed
1119 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1120 tests, but also to enforce that the result follows them. Returns true if the
1121 conversion succeeded, false otherwise. */
1123 bool
1124 convert_affine_scev (struct loop *loop, tree type,
1125 tree *base, tree *step, tree at_stmt,
1126 bool use_overflow_semantics)
1128 tree ct = TREE_TYPE (*step);
1129 bool enforce_overflow_semantics;
1130 bool must_check_src_overflow, must_check_rslt_overflow;
1131 tree new_base, new_step;
1133 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1134 if (avoid_arithmetics_in_type_p (type))
1135 return false;
1137 /* In general,
1138 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1139 but we must check some assumptions.
1141 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1142 of CT is smaller than the precision of TYPE. For example, when we
1143 cast unsigned char [254, +, 1] to unsigned, the values on left side
1144 are 254, 255, 0, 1, ..., but those on the right side are
1145 254, 255, 256, 257, ...
1146 2) In case that we must also preserve the fact that signed ivs do not
1147 overflow, we must additionally check that the new iv does not wrap.
1148 For example, unsigned char [125, +, 1] casted to signed char could
1149 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1150 which would confuse optimizers that assume that this does not
1151 happen. */
1152 must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1154 enforce_overflow_semantics = (use_overflow_semantics
1155 && nowrap_type_p (type));
1156 if (enforce_overflow_semantics)
1158 /* We can avoid checking whether the result overflows in the following
1159 cases:
1161 -- must_check_src_overflow is true, and the range of TYPE is superset
1162 of the range of CT -- i.e., in all cases except if CT signed and
1163 TYPE unsigned.
1164 -- both CT and TYPE have the same precision and signedness, and we
1165 verify instead that the source does not overflow (this may be
1166 easier than verifying it for the result, as we may use the
1167 information about the semantics of overflow in CT). */
1168 if (must_check_src_overflow)
1170 if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1171 must_check_rslt_overflow = true;
1172 else
1173 must_check_rslt_overflow = false;
1175 else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1176 && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1178 must_check_rslt_overflow = false;
1179 must_check_src_overflow = true;
1181 else
1182 must_check_rslt_overflow = true;
1184 else
1185 must_check_rslt_overflow = false;
1187 if (must_check_src_overflow
1188 && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1189 use_overflow_semantics))
1190 return false;
1192 new_base = chrec_convert_1 (type, *base, at_stmt,
1193 use_overflow_semantics);
1194 /* The step must be sign extended, regardless of the signedness
1195 of CT and TYPE. This only needs to be handled specially when
1196 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1197 (with values 100, 99, 98, ...) from becoming signed or unsigned
1198 [100, +, 255] with values 100, 355, ...; the sign-extension is
1199 performed by default when CT is signed. */
1200 new_step = *step;
1201 if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1202 new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1203 use_overflow_semantics);
1204 new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
1206 if (automatically_generated_chrec_p (new_base)
1207 || automatically_generated_chrec_p (new_step))
1208 return false;
1210 if (must_check_rslt_overflow
1211 /* Note that in this case we cannot use the fact that signed variables
1212 do not overflow, as this is what we are verifying for the new iv. */
1213 && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1214 return false;
1216 *base = new_base;
1217 *step = new_step;
1218 return true;
1222 /* Convert CHREC to TYPE. When the analyzer knows the context in
1223 which the CHREC is built, it sets AT_STMT to the statement that
1224 contains the definition of the analyzed variable, otherwise the
1225 conversion is less accurate: the information is used for
1226 determining a more accurate estimation of the number of iterations.
1227 By default AT_STMT could be safely set to NULL_TREE.
1229 The following rule is always true: TREE_TYPE (chrec) ==
1230 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1231 An example of what could happen when adding two chrecs and the type
1232 of the CHREC_RIGHT is different than CHREC_LEFT is:
1234 {(uint) 0, +, (uchar) 10} +
1235 {(uint) 0, +, (uchar) 250}
1237 that would produce a wrong result if CHREC_RIGHT is not (uint):
1239 {(uint) 0, +, (uchar) 4}
1241 instead of
1243 {(uint) 0, +, (uint) 260}
1246 tree
1247 chrec_convert (tree type, tree chrec, tree at_stmt)
1249 return chrec_convert_1 (type, chrec, at_stmt, true);
1252 /* Convert CHREC to TYPE. When the analyzer knows the context in
1253 which the CHREC is built, it sets AT_STMT to the statement that
1254 contains the definition of the analyzed variable, otherwise the
1255 conversion is less accurate: the information is used for
1256 determining a more accurate estimation of the number of iterations.
1257 By default AT_STMT could be safely set to NULL_TREE.
1259 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1260 the rules for overflow of the given language apply (e.g., that signed
1261 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1262 tests, but also to enforce that the result follows them. */
1264 static tree
1265 chrec_convert_1 (tree type, tree chrec, tree at_stmt,
1266 bool use_overflow_semantics)
1268 tree ct, res;
1269 tree base, step;
1270 struct loop *loop;
1272 if (automatically_generated_chrec_p (chrec))
1273 return chrec;
1275 ct = chrec_type (chrec);
1276 if (ct == type)
1277 return chrec;
1279 if (!evolution_function_is_affine_p (chrec))
1280 goto keep_cast;
1282 loop = get_chrec_loop (chrec);
1283 base = CHREC_LEFT (chrec);
1284 step = CHREC_RIGHT (chrec);
1286 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1287 use_overflow_semantics))
1288 return build_polynomial_chrec (loop->num, base, step);
1290 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1291 keep_cast:
1292 res = fold_convert (type, chrec);
1294 /* Don't propagate overflows. */
1295 if (CONSTANT_CLASS_P (res))
1297 TREE_CONSTANT_OVERFLOW (res) = 0;
1298 TREE_OVERFLOW (res) = 0;
1301 /* But reject constants that don't fit in their type after conversion.
1302 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1303 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1304 and can cause problems later when computing niters of loops. Note
1305 that we don't do the check before converting because we don't want
1306 to reject conversions of negative chrecs to unsigned types. */
1307 if (TREE_CODE (res) == INTEGER_CST
1308 && TREE_CODE (type) == INTEGER_TYPE
1309 && !int_fits_type_p (res, type))
1310 res = chrec_dont_know;
1312 return res;
1315 /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1316 chrec if something else than what chrec_convert would do happens, NULL_TREE
1317 otherwise. */
1319 tree
1320 chrec_convert_aggressive (tree type, tree chrec)
1322 tree inner_type, left, right, lc, rc;
1324 if (automatically_generated_chrec_p (chrec)
1325 || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1326 return NULL_TREE;
1328 inner_type = TREE_TYPE (chrec);
1329 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1330 return NULL_TREE;
1332 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1333 if (avoid_arithmetics_in_type_p (type))
1334 return NULL_TREE;
1336 left = CHREC_LEFT (chrec);
1337 right = CHREC_RIGHT (chrec);
1338 lc = chrec_convert_aggressive (type, left);
1339 if (!lc)
1340 lc = chrec_convert (type, left, NULL_TREE);
1341 rc = chrec_convert_aggressive (type, right);
1342 if (!rc)
1343 rc = chrec_convert (type, right, NULL_TREE);
1345 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1348 /* Returns true when CHREC0 == CHREC1. */
1350 bool
1351 eq_evolutions_p (tree chrec0,
1352 tree chrec1)
1354 if (chrec0 == NULL_TREE
1355 || chrec1 == NULL_TREE
1356 || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1357 return false;
1359 if (chrec0 == chrec1)
1360 return true;
1362 switch (TREE_CODE (chrec0))
1364 case INTEGER_CST:
1365 return operand_equal_p (chrec0, chrec1, 0);
1367 case POLYNOMIAL_CHREC:
1368 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1369 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1370 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1371 default:
1372 return false;
1376 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1377 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1378 which of these cases happens. */
1380 enum ev_direction
1381 scev_direction (tree chrec)
1383 tree step;
1385 if (!evolution_function_is_affine_p (chrec))
1386 return EV_DIR_UNKNOWN;
1388 step = CHREC_RIGHT (chrec);
1389 if (TREE_CODE (step) != INTEGER_CST)
1390 return EV_DIR_UNKNOWN;
1392 if (tree_int_cst_sign_bit (step))
1393 return EV_DIR_DECREASES;
1394 else
1395 return EV_DIR_GROWS;