OSDN Git Service

PR tree-optimization/22236
[pf3gnuchains/gcc-fork.git] / gcc / tree-chrec.c
1 /* Chains of recurrences.
2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <s.pop@laposte.net>
4
5 This file is part of GCC.
6
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.
11
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.
16
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.  */
21
22 /* This file implements operations on chains of recurrences.  Chains
23    of recurrences are used for modeling evolution functions of scalar
24    variables.
25 */
26
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 "diagnostic.h"
34 #include "varray.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
41 \f
42
43 /* Extended folder for chrecs.  */
44
45 /* Determines whether CST is not a constant evolution.  */
46
47 static inline bool
48 is_not_constant_evolution (tree cst)
49 {
50   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
51 }
52
53 /* Fold CODE for a polynomial function and a constant.  */
54
55 static inline tree 
56 chrec_fold_poly_cst (enum tree_code code, 
57                      tree type, 
58                      tree poly, 
59                      tree cst)
60 {
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   
66   switch (code)
67     {
68     case PLUS_EXPR:
69       return build_polynomial_chrec 
70         (CHREC_VARIABLE (poly), 
71          chrec_fold_plus (type, CHREC_LEFT (poly), cst),
72          CHREC_RIGHT (poly));
73       
74     case MINUS_EXPR:
75       return build_polynomial_chrec 
76         (CHREC_VARIABLE (poly), 
77          chrec_fold_minus (type, CHREC_LEFT (poly), cst),
78          CHREC_RIGHT (poly));
79       
80     case MULT_EXPR:
81       return build_polynomial_chrec 
82         (CHREC_VARIABLE (poly), 
83          chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
84          chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
85       
86     default:
87       return chrec_dont_know;
88     }
89 }
90
91 /* Fold the addition of two polynomial functions.  */
92
93 static inline tree 
94 chrec_fold_plus_poly_poly (enum tree_code code, 
95                            tree type, 
96                            tree poly0, 
97                            tree poly1)
98 {
99   tree left, right;
100
101   gcc_assert (poly0);
102   gcc_assert (poly1);
103   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
104   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
105   
106   /*
107     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
108     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
109     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
110   if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
111     {
112       if (code == PLUS_EXPR)
113         return build_polynomial_chrec 
114           (CHREC_VARIABLE (poly1), 
115            chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
116            CHREC_RIGHT (poly1));
117       else
118         return build_polynomial_chrec 
119           (CHREC_VARIABLE (poly1), 
120            chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
121            chrec_fold_multiply (type, CHREC_RIGHT (poly1), 
122                                 build_int_cst_type (type, -1)));
123     }
124   
125   if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
126     {
127       if (code == PLUS_EXPR)
128         return build_polynomial_chrec 
129           (CHREC_VARIABLE (poly0), 
130            chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
131            CHREC_RIGHT (poly0));
132       else
133         return build_polynomial_chrec 
134           (CHREC_VARIABLE (poly0), 
135            chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
136            CHREC_RIGHT (poly0));
137     }
138   
139   if (code == PLUS_EXPR)
140     {
141       left = chrec_fold_plus 
142         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
143       right = chrec_fold_plus 
144         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
145     }
146   else
147     {
148       left = chrec_fold_minus 
149         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
150       right = chrec_fold_minus 
151         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
152     }
153
154   if (chrec_zerop (right))
155     return left;
156   else
157     return build_polynomial_chrec 
158       (CHREC_VARIABLE (poly0), left, right); 
159 }
160
161 \f
162
163 /* Fold the multiplication of two polynomial functions.  */
164
165 static inline tree 
166 chrec_fold_multiply_poly_poly (tree type, 
167                                tree poly0, 
168                                tree poly1)
169 {
170   tree t0, t1, t2;
171   int var;
172
173   gcc_assert (poly0);
174   gcc_assert (poly1);
175   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
176   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
177   
178   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
179      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
180      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
181   if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
182     /* poly0 is a constant wrt. poly1.  */
183     return build_polynomial_chrec 
184       (CHREC_VARIABLE (poly1), 
185        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
186        CHREC_RIGHT (poly1));
187   
188   if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
189     /* poly1 is a constant wrt. poly0.  */
190     return build_polynomial_chrec 
191       (CHREC_VARIABLE (poly0), 
192        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
193        CHREC_RIGHT (poly0));
194   
195   /* poly0 and poly1 are two polynomials in the same variable,
196      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
197       
198   /* "a*c".  */
199   t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
200
201   /* "a*d + b*c + b*d".  */
202   t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
203   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
204                                                        CHREC_RIGHT (poly0),
205                                                        CHREC_LEFT (poly1)));
206   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
207                                                        CHREC_RIGHT (poly0),
208                                                        CHREC_RIGHT (poly1)));
209   /* "2*b*d".  */
210   t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
211   t2 = chrec_fold_multiply (type, build_int_cst_type (type, 2), t2);
212
213   var = CHREC_VARIABLE (poly0);
214   return build_polynomial_chrec (var, t0,
215                                  build_polynomial_chrec (var, t1, t2));
216 }
217
218 /* When the operands are automatically_generated_chrec_p, the fold has
219    to respect the semantics of the operands.  */
220
221 static inline tree 
222 chrec_fold_automatically_generated_operands (tree op0, 
223                                              tree op1)
224 {
225   if (op0 == chrec_dont_know
226       || op1 == chrec_dont_know)
227     return chrec_dont_know;
228   
229   if (op0 == chrec_known
230       || op1 == chrec_known)
231     return chrec_known;
232   
233   if (op0 == chrec_not_analyzed_yet
234       || op1 == chrec_not_analyzed_yet)
235     return chrec_not_analyzed_yet;
236   
237   /* The default case produces a safe result.  */
238   return chrec_dont_know;
239 }
240
241 /* Fold the addition of two chrecs.  */
242
243 static tree
244 chrec_fold_plus_1 (enum tree_code code, 
245                    tree type, 
246                    tree op0,
247                    tree op1)
248 {
249   if (automatically_generated_chrec_p (op0)
250       || automatically_generated_chrec_p (op1))
251     return chrec_fold_automatically_generated_operands (op0, op1);
252   
253   switch (TREE_CODE (op0))
254     {
255     case POLYNOMIAL_CHREC:
256       switch (TREE_CODE (op1))
257         {
258         case POLYNOMIAL_CHREC:
259           return chrec_fold_plus_poly_poly (code, type, op0, op1);
260
261         default:
262           if (code == PLUS_EXPR)
263             return build_polynomial_chrec 
264               (CHREC_VARIABLE (op0), 
265                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
266                CHREC_RIGHT (op0));
267           else
268             return build_polynomial_chrec 
269               (CHREC_VARIABLE (op0), 
270                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
271                CHREC_RIGHT (op0));
272         }
273
274     default:
275       switch (TREE_CODE (op1))
276         {
277         case POLYNOMIAL_CHREC:
278           if (code == PLUS_EXPR)
279             return build_polynomial_chrec 
280               (CHREC_VARIABLE (op1), 
281                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
282                CHREC_RIGHT (op1));
283           else
284             return build_polynomial_chrec 
285               (CHREC_VARIABLE (op1), 
286                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
287                chrec_fold_multiply (type, CHREC_RIGHT (op1),
288                                     build_int_cst_type (type, -1)));
289
290         default:
291           {
292             int size = 0;
293             if ((tree_contains_chrecs (op0, &size)
294                  || tree_contains_chrecs (op1, &size))
295                 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
296               return build2 (code, type, op0, op1);
297             else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
298               return fold_build2 (code, type,
299                                   fold_convert (type, op0),
300                                   fold_convert (type, op1));
301             else
302               return chrec_dont_know;
303           }
304         }
305     }
306 }
307
308 /* Fold the addition of two chrecs.  */
309
310 tree
311 chrec_fold_plus (tree type, 
312                  tree op0,
313                  tree op1)
314 {
315   if (integer_zerop (op0))
316     return op1;
317   if (integer_zerop (op1))
318     return op0;
319   
320   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
321 }
322
323 /* Fold the subtraction of two chrecs.  */
324
325 tree 
326 chrec_fold_minus (tree type, 
327                   tree op0, 
328                   tree op1)
329 {
330   if (integer_zerop (op1))
331     return op0;
332   
333   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
334 }
335
336 /* Fold the multiplication of two chrecs.  */
337
338 tree
339 chrec_fold_multiply (tree type, 
340                      tree op0,
341                      tree op1)
342 {
343   if (automatically_generated_chrec_p (op0)
344       || automatically_generated_chrec_p (op1))
345     return chrec_fold_automatically_generated_operands (op0, op1);
346   
347   switch (TREE_CODE (op0))
348     {
349     case POLYNOMIAL_CHREC:
350       switch (TREE_CODE (op1))
351         {
352         case POLYNOMIAL_CHREC:
353           return chrec_fold_multiply_poly_poly (type, op0, op1);
354           
355         default:
356           if (integer_onep (op1))
357             return op0;
358           if (integer_zerop (op1))
359             return build_int_cst_type (type, 0);
360           
361           return build_polynomial_chrec 
362             (CHREC_VARIABLE (op0), 
363              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
364              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
365         }
366       
367     default:
368       if (integer_onep (op0))
369         return op1;
370       
371       if (integer_zerop (op0))
372         return build_int_cst_type (type, 0);
373       
374       switch (TREE_CODE (op1))
375         {
376         case POLYNOMIAL_CHREC:
377           return build_polynomial_chrec 
378             (CHREC_VARIABLE (op1), 
379              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
380              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
381           
382         default:
383           if (integer_onep (op1))
384             return op0;
385           if (integer_zerop (op1))
386             return build_int_cst_type (type, 0);
387           return fold_build2 (MULT_EXPR, type, op0, op1);
388         }
389     }
390 }
391
392 \f
393
394 /* Operations.  */
395
396 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
397    calculation overflows, otherwise return C(n,k) with type TYPE.  */
398
399 static tree 
400 tree_fold_binomial (tree type, tree n, unsigned int k)
401 {
402   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
403   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
404   unsigned int i;
405   tree res;
406
407   /* Handle the most frequent cases.  */
408   if (k == 0)
409     return build_int_cst (type, 1);
410   if (k == 1)
411     return fold_convert (type, n);
412
413   /* Check that k <= n.  */
414   if (TREE_INT_CST_HIGH (n) == 0
415       && TREE_INT_CST_LOW (n) < k)
416     return NULL_TREE;
417
418   /* Numerator = n.  */
419   lnum = TREE_INT_CST_LOW (n);
420   hnum = TREE_INT_CST_HIGH (n);
421
422   /* Denominator = 2.  */
423   ldenom = 2;
424   hdenom = 0;
425
426   /* Index = Numerator-1.  */
427   if (lnum == 0)
428     {
429       hidx = hnum - 1;
430       lidx = ~ (unsigned HOST_WIDE_INT) 0;
431     }
432   else
433     {
434       hidx = hnum;
435       lidx = lnum - 1;
436     }
437
438   /* Numerator = Numerator*Index = n*(n-1).  */
439   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
440     return NULL_TREE;
441
442   for (i = 3; i <= k; i++)
443     {
444       /* Index--.  */
445       if (lidx == 0)
446         {
447           hidx--;
448           lidx = ~ (unsigned HOST_WIDE_INT) 0;
449         }
450       else
451         lidx--;
452
453       /* Numerator *= Index.  */
454       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
455         return NULL_TREE;
456
457       /* Denominator *= i.  */
458       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
459     }
460
461   /* Result = Numerator / Denominator.  */
462   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
463                         &lres, &hres, &ldum, &hdum);
464
465   res = build_int_cst_wide (type, lres, hres);
466   return int_fits_type_p (res, type) ? res : NULL_TREE;
467 }
468
469 /* Helper function.  Use the Newton's interpolating formula for
470    evaluating the value of the evolution function.  */
471
472 static tree 
473 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
474 {
475   tree arg0, arg1, binomial_n_k;
476   tree type = TREE_TYPE (chrec);
477
478   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
479          && CHREC_VARIABLE (chrec) > var)
480     chrec = CHREC_LEFT (chrec);
481
482   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
483       && CHREC_VARIABLE (chrec) == var)
484     {
485       arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
486       if (arg0 == chrec_dont_know)
487         return chrec_dont_know;
488       binomial_n_k = tree_fold_binomial (type, n, k);
489       if (!binomial_n_k)
490         return chrec_dont_know;
491       arg1 = fold_build2 (MULT_EXPR, type,
492                           CHREC_LEFT (chrec), binomial_n_k);
493       return chrec_fold_plus (type, arg0, arg1);
494     }
495
496   binomial_n_k = tree_fold_binomial (type, n, k);
497   if (!binomial_n_k)
498     return chrec_dont_know;
499   
500   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
501 }
502
503 /* Evaluates "CHREC (X)" when the varying variable is VAR.  
504    Example:  Given the following parameters, 
505    
506    var = 1
507    chrec = {3, +, 4}_1
508    x = 10
509    
510    The result is given by the Newton's interpolating formula: 
511    3 * \binom{10}{0} + 4 * \binom{10}{1}.
512 */
513
514 tree 
515 chrec_apply (unsigned var,
516              tree chrec, 
517              tree x)
518 {
519   tree type = chrec_type (chrec);
520   tree res = chrec_dont_know;
521
522   if (automatically_generated_chrec_p (chrec)
523       || automatically_generated_chrec_p (x)
524
525       /* When the symbols are defined in an outer loop, it is possible
526          to symbolically compute the apply, since the symbols are
527          constants with respect to the varying loop.  */
528       || chrec_contains_symbols_defined_in_loop (chrec, var)
529       || chrec_contains_symbols (x))
530     return chrec_dont_know;
531   
532   if (dump_file && (dump_flags & TDF_DETAILS))
533     fprintf (dump_file, "(chrec_apply \n");
534
535   if (evolution_function_is_affine_p (chrec))
536     {
537       /* "{a, +, b} (x)"  ->  "a + b*x".  */
538       if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
539           && integer_zerop (CHREC_LEFT (chrec)))
540         res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
541       
542       else
543         res = chrec_fold_plus (type, CHREC_LEFT (chrec), 
544                                chrec_fold_multiply (type, 
545                                                     CHREC_RIGHT (chrec), x));
546     }
547   
548   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
549     res = chrec;
550   
551   else if (TREE_CODE (x) == INTEGER_CST
552            && tree_int_cst_sgn (x) == 1)
553     /* testsuite/.../ssa-chrec-38.c.  */
554     res = chrec_evaluate (var, chrec, x, 0);
555
556   else
557     res = chrec_dont_know;
558   
559   if (dump_file && (dump_flags & TDF_DETAILS))
560     {
561       fprintf (dump_file, "  (varying_loop = %d\n", var);
562       fprintf (dump_file, ")\n  (chrec = ");
563       print_generic_expr (dump_file, chrec, 0);
564       fprintf (dump_file, ")\n  (x = ");
565       print_generic_expr (dump_file, x, 0);
566       fprintf (dump_file, ")\n  (res = ");
567       print_generic_expr (dump_file, res, 0);
568       fprintf (dump_file, "))\n");
569     }
570   
571   return res;
572 }
573
574 /* Replaces the initial condition in CHREC with INIT_COND.  */
575
576 tree 
577 chrec_replace_initial_condition (tree chrec, 
578                                  tree init_cond)
579 {
580   if (automatically_generated_chrec_p (chrec))
581     return chrec;
582   
583   switch (TREE_CODE (chrec))
584     {
585     case POLYNOMIAL_CHREC:
586       return build_polynomial_chrec 
587         (CHREC_VARIABLE (chrec),
588          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
589          CHREC_RIGHT (chrec));
590       
591     default:
592       return init_cond;
593     }
594 }
595
596 /* Returns the initial condition of a given CHREC.  */
597
598 tree 
599 initial_condition (tree chrec)
600 {
601   if (automatically_generated_chrec_p (chrec))
602     return chrec;
603   
604   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
605     return initial_condition (CHREC_LEFT (chrec));
606   else
607     return chrec;
608 }
609
610 /* Returns a univariate function that represents the evolution in
611    LOOP_NUM.  Mask the evolution of any other loop.  */
612
613 tree 
614 hide_evolution_in_other_loops_than_loop (tree chrec, 
615                                          unsigned loop_num)
616 {
617   if (automatically_generated_chrec_p (chrec))
618     return chrec;
619   
620   switch (TREE_CODE (chrec))
621     {
622     case POLYNOMIAL_CHREC:
623       if (CHREC_VARIABLE (chrec) == loop_num)
624         return build_polynomial_chrec 
625           (loop_num, 
626            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
627                                                     loop_num), 
628            CHREC_RIGHT (chrec));
629       
630       else if (CHREC_VARIABLE (chrec) < loop_num)
631         /* There is no evolution in this loop.  */
632         return initial_condition (chrec);
633       
634       else
635         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
636                                                         loop_num);
637       
638     default:
639       return chrec;
640     }
641 }
642
643 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
644    true, otherwise returns the initial condition in LOOP_NUM.  */
645
646 static tree 
647 chrec_component_in_loop_num (tree chrec, 
648                              unsigned loop_num,
649                              bool right)
650 {
651   tree component;
652
653   if (automatically_generated_chrec_p (chrec))
654     return chrec;
655   
656   switch (TREE_CODE (chrec))
657     {
658     case POLYNOMIAL_CHREC:
659       if (CHREC_VARIABLE (chrec) == loop_num)
660         {
661           if (right)
662             component = CHREC_RIGHT (chrec);
663           else
664             component = CHREC_LEFT (chrec);
665
666           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
667               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
668             return component;
669           
670           else
671             return build_polynomial_chrec
672               (loop_num, 
673                chrec_component_in_loop_num (CHREC_LEFT (chrec), 
674                                             loop_num, 
675                                             right), 
676                component);
677         }
678       
679       else if (CHREC_VARIABLE (chrec) < loop_num)
680         /* There is no evolution part in this loop.  */
681         return NULL_TREE;
682       
683       else
684         return chrec_component_in_loop_num (CHREC_LEFT (chrec), 
685                                             loop_num, 
686                                             right);
687       
688      default:
689       if (right)
690         return NULL_TREE;
691       else
692         return chrec;
693     }
694 }
695
696 /* Returns the evolution part in LOOP_NUM.  Example: the call
697    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns 
698    {1, +, 2}_1  */
699
700 tree 
701 evolution_part_in_loop_num (tree chrec, 
702                             unsigned loop_num)
703 {
704   return chrec_component_in_loop_num (chrec, loop_num, true);
705 }
706
707 /* Returns the initial condition in LOOP_NUM.  Example: the call
708    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns 
709    {0, +, 1}_1  */
710
711 tree 
712 initial_condition_in_loop_num (tree chrec, 
713                                unsigned loop_num)
714 {
715   return chrec_component_in_loop_num (chrec, loop_num, false);
716 }
717
718 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
719    This function is essentially used for setting the evolution to
720    chrec_dont_know, for example after having determined that it is
721    impossible to say how many times a loop will execute.  */
722
723 tree 
724 reset_evolution_in_loop (unsigned loop_num,
725                          tree chrec, 
726                          tree new_evol)
727 {
728   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
729       && CHREC_VARIABLE (chrec) > loop_num)
730     {
731       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
732                                            new_evol);
733       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
734                                             new_evol);
735       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
736                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
737                      left, right);
738     }
739
740   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
741          && CHREC_VARIABLE (chrec) == loop_num)
742     chrec = CHREC_LEFT (chrec);
743   
744   return build_polynomial_chrec (loop_num, chrec, new_evol);
745 }
746
747 /* Merges two evolution functions that were found by following two
748    alternate paths of a conditional expression.  */
749
750 tree
751 chrec_merge (tree chrec1, 
752              tree chrec2)
753 {
754   if (chrec1 == chrec_dont_know
755       || chrec2 == chrec_dont_know)
756     return chrec_dont_know;
757
758   if (chrec1 == chrec_known 
759       || chrec2 == chrec_known)
760     return chrec_known;
761
762   if (chrec1 == chrec_not_analyzed_yet)
763     return chrec2;
764   if (chrec2 == chrec_not_analyzed_yet)
765     return chrec1;
766
767   if (operand_equal_p (chrec1, chrec2, 0))
768     return chrec1;
769
770   return chrec_dont_know;
771 }
772
773 \f
774
775 /* Observers.  */
776
777 /* Helper function for is_multivariate_chrec.  */
778
779 static bool 
780 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
781 {
782   if (chrec == NULL_TREE)
783     return false;
784   
785   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
786     {
787       if (CHREC_VARIABLE (chrec) != rec_var)
788         return true;
789       else
790         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) 
791                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
792     }
793   else
794     return false;
795 }
796
797 /* Determine whether the given chrec is multivariate or not.  */
798
799 bool 
800 is_multivariate_chrec (tree chrec)
801 {
802   if (chrec == NULL_TREE)
803     return false;
804   
805   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
806     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), 
807                                        CHREC_VARIABLE (chrec))
808             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), 
809                                           CHREC_VARIABLE (chrec)));
810   else
811     return false;
812 }
813
814 /* Determines whether the chrec contains symbolic names or not.  */
815
816 bool 
817 chrec_contains_symbols (tree chrec)
818 {
819   if (chrec == NULL_TREE)
820     return false;
821   
822   if (TREE_CODE (chrec) == SSA_NAME
823       || TREE_CODE (chrec) == VAR_DECL
824       || TREE_CODE (chrec) == PARM_DECL
825       || TREE_CODE (chrec) == FUNCTION_DECL
826       || TREE_CODE (chrec) == LABEL_DECL
827       || TREE_CODE (chrec) == RESULT_DECL
828       || TREE_CODE (chrec) == FIELD_DECL)
829     return true;
830   
831   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
832     {
833     case 3:
834       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
835         return true;
836       
837     case 2:
838       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
839         return true;
840       
841     case 1:
842       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
843         return true;
844       
845     default:
846       return false;
847     }
848 }
849
850 /* Determines whether the chrec contains undetermined coefficients.  */
851
852 bool 
853 chrec_contains_undetermined (tree chrec)
854 {
855   if (chrec == chrec_dont_know
856       || chrec == chrec_not_analyzed_yet
857       || chrec == NULL_TREE)
858     return true;
859   
860   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
861     {
862     case 3:
863       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
864         return true;
865       
866     case 2:
867       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
868         return true;
869       
870     case 1:
871       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
872         return true;
873       
874     default:
875       return false;
876     }
877 }
878
879 /* Determines whether the tree EXPR contains chrecs, and increment
880    SIZE if it is not a NULL pointer by an estimation of the depth of
881    the tree.  */
882
883 bool
884 tree_contains_chrecs (tree expr, int *size)
885 {
886   if (expr == NULL_TREE)
887     return false;
888
889   if (size)
890     (*size)++;
891   
892   if (tree_is_chrec (expr))
893     return true;
894
895   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
896     {
897     case 3:
898       if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
899         return true;
900       
901     case 2:
902       if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
903         return true;
904       
905     case 1:
906       if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
907         return true;
908       
909     default:
910       return false;
911     }
912 }
913
914 /* Recursive helper function.  */
915
916 static bool
917 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
918 {
919   if (evolution_function_is_constant_p (chrec))
920     return true;
921
922   if (TREE_CODE (chrec) == SSA_NAME 
923       && expr_invariant_in_loop_p (current_loops->parray[loopnum],
924                                    chrec))
925     return true;
926
927   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
928       && CHREC_VARIABLE (chrec) == (unsigned) loopnum)
929     return false;
930
931   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
932     {
933     case 2:
934       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
935                                                   loopnum))
936         return false;
937       
938     case 1:
939       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
940                                                   loopnum))
941         return false;
942       return true;
943
944     default:
945       return false;
946     }
947
948   return false;
949 }
950
951 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
952
953 bool
954 evolution_function_is_invariant_p (tree chrec, int loopnum)
955 {
956   if (evolution_function_is_constant_p (chrec))
957     return true;
958   
959   if (current_loops != NULL)
960     return evolution_function_is_invariant_rec_p (chrec, loopnum);
961
962   return false;
963 }
964
965 /* Determine whether the given tree is an affine multivariate
966    evolution.  */
967
968 bool 
969 evolution_function_is_affine_multivariate_p (tree chrec)
970 {
971   if (chrec == NULL_TREE)
972     return false;
973   
974   switch (TREE_CODE (chrec))
975     {
976     case POLYNOMIAL_CHREC:
977       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
978         {
979           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
980             return true;
981           else
982             {
983               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
984                   && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 
985                      != CHREC_VARIABLE (chrec)
986                   && evolution_function_is_affine_multivariate_p 
987                   (CHREC_RIGHT (chrec)))
988                 return true;
989               else
990                 return false;
991             }
992         }
993       else
994         {
995           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
996               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
997               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
998               && evolution_function_is_affine_multivariate_p 
999               (CHREC_LEFT (chrec)))
1000             return true;
1001           else
1002             return false;
1003         }
1004       
1005     default:
1006       return false;
1007     }
1008 }
1009
1010 /* Determine whether the given tree is a function in zero or one 
1011    variables.  */
1012
1013 bool
1014 evolution_function_is_univariate_p (tree chrec)
1015 {
1016   if (chrec == NULL_TREE)
1017     return true;
1018   
1019   switch (TREE_CODE (chrec))
1020     {
1021     case POLYNOMIAL_CHREC:
1022       switch (TREE_CODE (CHREC_LEFT (chrec)))
1023         {
1024         case POLYNOMIAL_CHREC:
1025           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1026             return false;
1027           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1028             return false;
1029           break;
1030           
1031         default:
1032           break;
1033         }
1034       
1035       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1036         {
1037         case POLYNOMIAL_CHREC:
1038           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1039             return false;
1040           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1041             return false;
1042           break;
1043           
1044         default:
1045           break;          
1046         }
1047       
1048     default:
1049       return true;
1050     }
1051 }
1052
1053 /* Returns the number of variables of CHREC.  Example: the call
1054    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1055
1056 unsigned 
1057 nb_vars_in_chrec (tree chrec)
1058 {
1059   if (chrec == NULL_TREE)
1060     return 0;
1061
1062   switch (TREE_CODE (chrec))
1063     {
1064     case POLYNOMIAL_CHREC:
1065       return 1 + nb_vars_in_chrec 
1066         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1067
1068     default:
1069       return 0;
1070     }
1071 }
1072
1073 \f
1074
1075 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1076    which the CHREC is built, it sets AT_STMT to the statement that
1077    contains the definition of the analyzed variable, otherwise the
1078    conversion is less accurate: the information is used for
1079    determining a more accurate estimation of the number of iterations.
1080    By default AT_STMT could be safely set to NULL_TREE.
1081
1082    The following rule is always true: TREE_TYPE (chrec) ==
1083    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1084    An example of what could happen when adding two chrecs and the type
1085    of the CHREC_RIGHT is different than CHREC_LEFT is:
1086    
1087    {(uint) 0, +, (uchar) 10} +
1088    {(uint) 0, +, (uchar) 250}
1089    
1090    that would produce a wrong result if CHREC_RIGHT is not (uint):
1091    
1092    {(uint) 0, +, (uchar) 4}
1093
1094    instead of
1095
1096    {(uint) 0, +, (uint) 260}
1097 */
1098
1099 tree 
1100 chrec_convert (tree type, tree chrec, tree at_stmt)
1101 {
1102   tree ct, res;
1103
1104   if (automatically_generated_chrec_p (chrec))
1105     return chrec;
1106   
1107   ct = chrec_type (chrec);
1108   if (ct == type)
1109     return chrec;
1110
1111   if (evolution_function_is_affine_p (chrec))
1112     {
1113       tree step;
1114       bool dummy;
1115
1116       /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1117          when it is not possible to prove that the scev does not wrap.
1118          See PR22236, where a sequence 1, 2, ..., 255 has to be
1119          converted to signed char, but this would wrap: 
1120          1, 2, ..., 127, -128, ...  The result should not be
1121          {(schar)1, +, (schar)1}_x, but instead, we should keep the
1122          conversion: (schar) {(uchar)1, +, (uchar)1}_x.  */
1123       if (scev_probably_wraps_p (type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
1124                                  at_stmt,
1125                                  current_loops->parray[CHREC_VARIABLE (chrec)],
1126                                  &dummy, &dummy))
1127         return fold_convert (type, chrec);
1128
1129       step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)], type,
1130                            CHREC_LEFT (chrec), CHREC_RIGHT (chrec), at_stmt);
1131       if (!step)
1132         return fold_convert (type, chrec);
1133
1134       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1135                                      chrec_convert (type, CHREC_LEFT (chrec),
1136                                                     at_stmt),
1137                                      step);
1138     }
1139
1140   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1141     return chrec_dont_know;
1142
1143   res = fold_convert (type, chrec);
1144
1145   /* Don't propagate overflows.  */
1146   if (CONSTANT_CLASS_P (res))
1147     {
1148       TREE_CONSTANT_OVERFLOW (res) = 0;
1149       TREE_OVERFLOW (res) = 0;
1150     }
1151
1152   /* But reject constants that don't fit in their type after conversion.
1153      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1154      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1155      and can cause problems later when computing niters of loops.  Note
1156      that we don't do the check before converting because we don't want
1157      to reject conversions of negative chrecs to unsigned types.  */
1158   if (TREE_CODE (res) == INTEGER_CST
1159       && TREE_CODE (type) == INTEGER_TYPE
1160       && !int_fits_type_p (res, type))
1161     res = chrec_dont_know;
1162
1163   return res;
1164 }
1165
1166 /* Returns the type of the chrec.  */
1167
1168 tree 
1169 chrec_type (tree chrec)
1170 {
1171   if (automatically_generated_chrec_p (chrec))
1172     return NULL_TREE;
1173   
1174   return TREE_TYPE (chrec);
1175 }