OSDN Git Service

2007-05-21 Andrew Pinski <andrew_pinski@playstation.sony.com>
[pf3gnuchains/gcc-fork.git] / gcc / tree-chrec.c
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>
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 "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"
41
42 \f
43
44 /* Extended folder for chrecs.  */
45
46 /* Determines whether CST is not a constant evolution.  */
47
48 static inline bool
49 is_not_constant_evolution (tree cst)
50 {
51   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
52 }
53
54 /* Fold CODE for a polynomial function and a constant.  */
55
56 static inline tree 
57 chrec_fold_poly_cst (enum tree_code code, 
58                      tree type, 
59                      tree poly, 
60                      tree cst)
61 {
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));
67
68   switch (code)
69     {
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));
75       
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));
81       
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));
87       
88     default:
89       return chrec_dont_know;
90     }
91 }
92
93 /* Fold the addition of two polynomial functions.  */
94
95 static inline tree 
96 chrec_fold_plus_poly_poly (enum tree_code code, 
97                            tree type, 
98                            tree poly0, 
99                            tree poly1)
100 {
101   tree left, right;
102   struct loop *loop0 = get_chrec_loop (poly0);
103   struct loop *loop1 = get_chrec_loop (poly1);
104
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   gcc_assert (chrec_type (poly0) == chrec_type (poly1));
110   gcc_assert (type == chrec_type (poly0));
111   
112   /*
113     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
114     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
115     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
116   if (flow_loop_nested_p (loop0, loop1))
117     {
118       if (code == PLUS_EXPR)
119         return build_polynomial_chrec 
120           (CHREC_VARIABLE (poly1), 
121            chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
122            CHREC_RIGHT (poly1));
123       else
124         return build_polynomial_chrec 
125           (CHREC_VARIABLE (poly1), 
126            chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
127            chrec_fold_multiply (type, CHREC_RIGHT (poly1), 
128                                 SCALAR_FLOAT_TYPE_P (type)
129                                 ? build_real (type, dconstm1)
130                                 : build_int_cst_type (type, -1)));
131     }
132   
133   if (flow_loop_nested_p (loop1, loop0))
134     {
135       if (code == PLUS_EXPR)
136         return build_polynomial_chrec 
137           (CHREC_VARIABLE (poly0), 
138            chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
139            CHREC_RIGHT (poly0));
140       else
141         return build_polynomial_chrec 
142           (CHREC_VARIABLE (poly0), 
143            chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
144            CHREC_RIGHT (poly0));
145     }
146  
147   /* This function should never be called for chrecs of loops that
148      do not belong to the same loop nest.  */
149   gcc_assert (loop0 == loop1);
150
151   if (code == PLUS_EXPR)
152     {
153       left = chrec_fold_plus 
154         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
155       right = chrec_fold_plus 
156         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
157     }
158   else
159     {
160       left = chrec_fold_minus 
161         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
162       right = chrec_fold_minus 
163         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
164     }
165
166   if (chrec_zerop (right))
167     return left;
168   else
169     return build_polynomial_chrec 
170       (CHREC_VARIABLE (poly0), left, right); 
171 }
172
173 \f
174
175 /* Fold the multiplication of two polynomial functions.  */
176
177 static inline tree 
178 chrec_fold_multiply_poly_poly (tree type, 
179                                tree poly0, 
180                                tree poly1)
181 {
182   tree t0, t1, t2;
183   int var;
184   struct loop *loop0 = get_chrec_loop (poly0);
185   struct loop *loop1 = get_chrec_loop (poly1);
186
187   gcc_assert (poly0);
188   gcc_assert (poly1);
189   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
190   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
191   gcc_assert (chrec_type (poly0) == chrec_type (poly1));
192   gcc_assert (type == chrec_type (poly0));
193   
194   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
195      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
196      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
197   if (flow_loop_nested_p (loop0, loop1))
198     /* poly0 is a constant wrt. poly1.  */
199     return build_polynomial_chrec 
200       (CHREC_VARIABLE (poly1), 
201        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
202        CHREC_RIGHT (poly1));
203   
204   if (flow_loop_nested_p (loop1, loop0))
205     /* poly1 is a constant wrt. poly0.  */
206     return build_polynomial_chrec 
207       (CHREC_VARIABLE (poly0), 
208        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
209        CHREC_RIGHT (poly0));
210  
211   gcc_assert (loop0 == loop1);
212
213   /* poly0 and poly1 are two polynomials in the same variable,
214      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
215       
216   /* "a*c".  */
217   t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
218
219   /* "a*d + b*c + b*d".  */
220   t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
221   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
222                                                        CHREC_RIGHT (poly0),
223                                                        CHREC_LEFT (poly1)));
224   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
225                                                        CHREC_RIGHT (poly0),
226                                                        CHREC_RIGHT (poly1)));
227   /* "2*b*d".  */
228   t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
229   t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
230                             ? build_real (type, dconst2)
231                             : build_int_cst (type, 2), t2);
232
233   var = CHREC_VARIABLE (poly0);
234   return build_polynomial_chrec (var, t0,
235                                  build_polynomial_chrec (var, t1, t2));
236 }
237
238 /* When the operands are automatically_generated_chrec_p, the fold has
239    to respect the semantics of the operands.  */
240
241 static inline tree 
242 chrec_fold_automatically_generated_operands (tree op0, 
243                                              tree op1)
244 {
245   if (op0 == chrec_dont_know
246       || op1 == chrec_dont_know)
247     return chrec_dont_know;
248   
249   if (op0 == chrec_known
250       || op1 == chrec_known)
251     return chrec_known;
252   
253   if (op0 == chrec_not_analyzed_yet
254       || op1 == chrec_not_analyzed_yet)
255     return chrec_not_analyzed_yet;
256   
257   /* The default case produces a safe result.  */
258   return chrec_dont_know;
259 }
260
261 /* Fold the addition of two chrecs.  */
262
263 static tree
264 chrec_fold_plus_1 (enum tree_code code, tree type, 
265                    tree op0, tree op1)
266 {
267   if (automatically_generated_chrec_p (op0)
268       || automatically_generated_chrec_p (op1))
269     return chrec_fold_automatically_generated_operands (op0, op1);
270   
271   switch (TREE_CODE (op0))
272     {
273     case POLYNOMIAL_CHREC:
274       switch (TREE_CODE (op1))
275         {
276         case POLYNOMIAL_CHREC:
277           return chrec_fold_plus_poly_poly (code, type, op0, op1);
278
279         default:
280           if (code == PLUS_EXPR)
281             return build_polynomial_chrec 
282               (CHREC_VARIABLE (op0), 
283                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
284                CHREC_RIGHT (op0));
285           else
286             return build_polynomial_chrec 
287               (CHREC_VARIABLE (op0), 
288                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
289                CHREC_RIGHT (op0));
290         }
291
292     default:
293       switch (TREE_CODE (op1))
294         {
295         case POLYNOMIAL_CHREC:
296           if (code == PLUS_EXPR)
297             return build_polynomial_chrec 
298               (CHREC_VARIABLE (op1), 
299                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
300                CHREC_RIGHT (op1));
301           else
302             return build_polynomial_chrec 
303               (CHREC_VARIABLE (op1), 
304                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
305                chrec_fold_multiply (type, CHREC_RIGHT (op1), 
306                                     SCALAR_FLOAT_TYPE_P (type)
307                                     ? build_real (type, dconstm1)
308                                     : build_int_cst_type (type, -1)));
309
310         default:
311           {
312             int size = 0;
313             if ((tree_contains_chrecs (op0, &size)
314                  || tree_contains_chrecs (op1, &size))
315                 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
316               return build2 (code, type, op0, op1);
317             else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
318               return fold_build2 (code, type,
319                                   fold_convert (type, op0),
320                                   fold_convert (type, op1));
321             else
322               return chrec_dont_know;
323           }
324         }
325     }
326 }
327
328 /* Fold the addition of two chrecs.  */
329
330 tree
331 chrec_fold_plus (tree type, 
332                  tree op0,
333                  tree op1)
334 {
335   if (automatically_generated_chrec_p (op0)
336       || automatically_generated_chrec_p (op1))
337     return chrec_fold_automatically_generated_operands (op0, op1);
338
339   if (integer_zerop (op0))
340     return op1;
341   if (integer_zerop (op1))
342     return op0;
343   
344   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
345 }
346
347 /* Fold the subtraction of two chrecs.  */
348
349 tree 
350 chrec_fold_minus (tree type, 
351                   tree op0, 
352                   tree op1)
353 {
354   if (automatically_generated_chrec_p (op0)
355       || automatically_generated_chrec_p (op1))
356     return chrec_fold_automatically_generated_operands (op0, op1);
357
358   if (integer_zerop (op1))
359     return op0;
360   
361   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
362 }
363
364 /* Fold the multiplication of two chrecs.  */
365
366 tree
367 chrec_fold_multiply (tree type, 
368                      tree op0,
369                      tree op1)
370 {
371   if (automatically_generated_chrec_p (op0)
372       || automatically_generated_chrec_p (op1))
373     return chrec_fold_automatically_generated_operands (op0, op1);
374   
375   switch (TREE_CODE (op0))
376     {
377     case POLYNOMIAL_CHREC:
378       switch (TREE_CODE (op1))
379         {
380         case POLYNOMIAL_CHREC:
381           return chrec_fold_multiply_poly_poly (type, op0, op1);
382           
383         default:
384           if (integer_onep (op1))
385             return op0;
386           if (integer_zerop (op1))
387             return build_int_cst (type, 0);
388           
389           return build_polynomial_chrec 
390             (CHREC_VARIABLE (op0), 
391              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
392              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
393         }
394       
395     default:
396       if (integer_onep (op0))
397         return op1;
398       
399       if (integer_zerop (op0))
400         return build_int_cst (type, 0);
401       
402       switch (TREE_CODE (op1))
403         {
404         case POLYNOMIAL_CHREC:
405           return build_polynomial_chrec 
406             (CHREC_VARIABLE (op1), 
407              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
408              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
409           
410         default:
411           if (integer_onep (op1))
412             return op0;
413           if (integer_zerop (op1))
414             return build_int_cst (type, 0);
415           return fold_build2 (MULT_EXPR, type, op0, op1);
416         }
417     }
418 }
419
420 \f
421
422 /* Operations.  */
423
424 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
425    calculation overflows, otherwise return C(n,k) with type TYPE.  */
426
427 static tree 
428 tree_fold_binomial (tree type, tree n, unsigned int k)
429 {
430   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
431   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
432   unsigned int i;
433   tree res;
434
435   /* Handle the most frequent cases.  */
436   if (k == 0)
437     return build_int_cst (type, 1);
438   if (k == 1)
439     return fold_convert (type, n);
440
441   /* Check that k <= n.  */
442   if (TREE_INT_CST_HIGH (n) == 0
443       && TREE_INT_CST_LOW (n) < k)
444     return NULL_TREE;
445
446   /* Numerator = n.  */
447   lnum = TREE_INT_CST_LOW (n);
448   hnum = TREE_INT_CST_HIGH (n);
449
450   /* Denominator = 2.  */
451   ldenom = 2;
452   hdenom = 0;
453
454   /* Index = Numerator-1.  */
455   if (lnum == 0)
456     {
457       hidx = hnum - 1;
458       lidx = ~ (unsigned HOST_WIDE_INT) 0;
459     }
460   else
461     {
462       hidx = hnum;
463       lidx = lnum - 1;
464     }
465
466   /* Numerator = Numerator*Index = n*(n-1).  */
467   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
468     return NULL_TREE;
469
470   for (i = 3; i <= k; i++)
471     {
472       /* Index--.  */
473       if (lidx == 0)
474         {
475           hidx--;
476           lidx = ~ (unsigned HOST_WIDE_INT) 0;
477         }
478       else
479         lidx--;
480
481       /* Numerator *= Index.  */
482       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
483         return NULL_TREE;
484
485       /* Denominator *= i.  */
486       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
487     }
488
489   /* Result = Numerator / Denominator.  */
490   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
491                         &lres, &hres, &ldum, &hdum);
492
493   res = build_int_cst_wide (type, lres, hres);
494   return int_fits_type_p (res, type) ? res : NULL_TREE;
495 }
496
497 /* Helper function.  Use the Newton's interpolating formula for
498    evaluating the value of the evolution function.  */
499
500 static tree 
501 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
502 {
503   tree arg0, arg1, binomial_n_k;
504   tree type = TREE_TYPE (chrec);
505   struct loop *var_loop = get_loop (var);
506
507   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
508          && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
509     chrec = CHREC_LEFT (chrec);
510
511   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
512       && CHREC_VARIABLE (chrec) == var)
513     {
514       arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
515       if (arg0 == chrec_dont_know)
516         return chrec_dont_know;
517       binomial_n_k = tree_fold_binomial (type, n, k);
518       if (!binomial_n_k)
519         return chrec_dont_know;
520       arg1 = fold_build2 (MULT_EXPR, type,
521                           CHREC_LEFT (chrec), binomial_n_k);
522       return chrec_fold_plus (type, arg0, arg1);
523     }
524
525   binomial_n_k = tree_fold_binomial (type, n, k);
526   if (!binomial_n_k)
527     return chrec_dont_know;
528   
529   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
530 }
531
532 /* Evaluates "CHREC (X)" when the varying variable is VAR.  
533    Example:  Given the following parameters, 
534    
535    var = 1
536    chrec = {3, +, 4}_1
537    x = 10
538    
539    The result is given by the Newton's interpolating formula: 
540    3 * \binom{10}{0} + 4 * \binom{10}{1}.
541 */
542
543 tree 
544 chrec_apply (unsigned var,
545              tree chrec, 
546              tree x)
547 {
548   tree type = chrec_type (chrec);
549   tree res = chrec_dont_know;
550
551   if (automatically_generated_chrec_p (chrec)
552       || automatically_generated_chrec_p (x)
553
554       /* When the symbols are defined in an outer loop, it is possible
555          to symbolically compute the apply, since the symbols are
556          constants with respect to the varying loop.  */
557       || chrec_contains_symbols_defined_in_loop (chrec, var))
558     return chrec_dont_know;
559  
560   if (dump_file && (dump_flags & TDF_DETAILS))
561     fprintf (dump_file, "(chrec_apply \n");
562
563   if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
564     x = build_real_from_int_cst (type, x);
565
566   if (evolution_function_is_affine_p (chrec))
567     {
568       /* "{a, +, b} (x)"  ->  "a + b*x".  */
569       x = chrec_convert (type, x, NULL_TREE);
570       res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
571       if (!integer_zerop (CHREC_LEFT (chrec)))
572         res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
573     }
574   
575   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
576     res = chrec;
577   
578   else if (TREE_CODE (x) == INTEGER_CST
579            && tree_int_cst_sgn (x) == 1)
580     /* testsuite/.../ssa-chrec-38.c.  */
581     res = chrec_evaluate (var, chrec, x, 0);
582   else
583     res = chrec_dont_know;
584   
585   if (dump_file && (dump_flags & TDF_DETAILS))
586     {
587       fprintf (dump_file, "  (varying_loop = %d\n", var);
588       fprintf (dump_file, ")\n  (chrec = ");
589       print_generic_expr (dump_file, chrec, 0);
590       fprintf (dump_file, ")\n  (x = ");
591       print_generic_expr (dump_file, x, 0);
592       fprintf (dump_file, ")\n  (res = ");
593       print_generic_expr (dump_file, res, 0);
594       fprintf (dump_file, "))\n");
595     }
596   
597   return res;
598 }
599
600 /* Replaces the initial condition in CHREC with INIT_COND.  */
601
602 tree 
603 chrec_replace_initial_condition (tree chrec, 
604                                  tree init_cond)
605 {
606   if (automatically_generated_chrec_p (chrec))
607     return chrec;
608
609   gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
610
611   switch (TREE_CODE (chrec))
612     {
613     case POLYNOMIAL_CHREC:
614       return build_polynomial_chrec 
615         (CHREC_VARIABLE (chrec),
616          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
617          CHREC_RIGHT (chrec));
618       
619     default:
620       return init_cond;
621     }
622 }
623
624 /* Returns the initial condition of a given CHREC.  */
625
626 tree 
627 initial_condition (tree chrec)
628 {
629   if (automatically_generated_chrec_p (chrec))
630     return chrec;
631   
632   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
633     return initial_condition (CHREC_LEFT (chrec));
634   else
635     return chrec;
636 }
637
638 /* Returns a univariate function that represents the evolution in
639    LOOP_NUM.  Mask the evolution of any other loop.  */
640
641 tree 
642 hide_evolution_in_other_loops_than_loop (tree chrec, 
643                                          unsigned loop_num)
644 {
645   struct loop *loop = get_loop (loop_num), *chloop;
646   if (automatically_generated_chrec_p (chrec))
647     return chrec;
648   
649   switch (TREE_CODE (chrec))
650     {
651     case POLYNOMIAL_CHREC:
652       chloop = get_chrec_loop (chrec);
653
654       if (chloop == loop)
655         return build_polynomial_chrec 
656           (loop_num, 
657            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
658                                                     loop_num), 
659            CHREC_RIGHT (chrec));
660       
661       else if (flow_loop_nested_p (chloop, loop))
662         /* There is no evolution in this loop.  */
663         return initial_condition (chrec);
664       
665       else
666         {
667           gcc_assert (flow_loop_nested_p (loop, chloop));
668           return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
669                                                           loop_num);
670         }
671       
672     default:
673       return chrec;
674     }
675 }
676
677 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
678    true, otherwise returns the initial condition in LOOP_NUM.  */
679
680 static tree 
681 chrec_component_in_loop_num (tree chrec, 
682                              unsigned loop_num,
683                              bool right)
684 {
685   tree component;
686   struct loop *loop = get_loop (loop_num), *chloop;
687
688   if (automatically_generated_chrec_p (chrec))
689     return chrec;
690   
691   switch (TREE_CODE (chrec))
692     {
693     case POLYNOMIAL_CHREC:
694       chloop = get_chrec_loop (chrec);
695
696       if (chloop == loop)
697         {
698           if (right)
699             component = CHREC_RIGHT (chrec);
700           else
701             component = CHREC_LEFT (chrec);
702
703           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
704               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
705             return component;
706           
707           else
708             return build_polynomial_chrec
709               (loop_num, 
710                chrec_component_in_loop_num (CHREC_LEFT (chrec), 
711                                             loop_num, 
712                                             right), 
713                component);
714         }
715       
716       else if (flow_loop_nested_p (chloop, loop))
717         /* There is no evolution part in this loop.  */
718         return NULL_TREE;
719       
720       else
721         {
722           gcc_assert (flow_loop_nested_p (loop, chloop));
723           return chrec_component_in_loop_num (CHREC_LEFT (chrec), 
724                                               loop_num, 
725                                               right);
726         }
727       
728      default:
729       if (right)
730         return NULL_TREE;
731       else
732         return chrec;
733     }
734 }
735
736 /* Returns the evolution part in LOOP_NUM.  Example: the call
737    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns 
738    {1, +, 2}_1  */
739
740 tree 
741 evolution_part_in_loop_num (tree chrec, 
742                             unsigned loop_num)
743 {
744   return chrec_component_in_loop_num (chrec, loop_num, true);
745 }
746
747 /* Returns the initial condition in LOOP_NUM.  Example: the call
748    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns 
749    {0, +, 1}_1  */
750
751 tree 
752 initial_condition_in_loop_num (tree chrec, 
753                                unsigned loop_num)
754 {
755   return chrec_component_in_loop_num (chrec, loop_num, false);
756 }
757
758 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
759    This function is essentially used for setting the evolution to
760    chrec_dont_know, for example after having determined that it is
761    impossible to say how many times a loop will execute.  */
762
763 tree 
764 reset_evolution_in_loop (unsigned loop_num,
765                          tree chrec, 
766                          tree new_evol)
767 {
768   struct loop *loop = get_loop (loop_num);
769
770   gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
771
772   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
773       && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
774     {
775       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
776                                            new_evol);
777       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
778                                             new_evol);
779       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
780                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
781                      left, right);
782     }
783
784   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
785          && CHREC_VARIABLE (chrec) == loop_num)
786     chrec = CHREC_LEFT (chrec);
787   
788   return build_polynomial_chrec (loop_num, chrec, new_evol);
789 }
790
791 /* Merges two evolution functions that were found by following two
792    alternate paths of a conditional expression.  */
793
794 tree
795 chrec_merge (tree chrec1, 
796              tree chrec2)
797 {
798   if (chrec1 == chrec_dont_know
799       || chrec2 == chrec_dont_know)
800     return chrec_dont_know;
801
802   if (chrec1 == chrec_known 
803       || chrec2 == chrec_known)
804     return chrec_known;
805
806   if (chrec1 == chrec_not_analyzed_yet)
807     return chrec2;
808   if (chrec2 == chrec_not_analyzed_yet)
809     return chrec1;
810
811   if (eq_evolutions_p (chrec1, chrec2))
812     return chrec1;
813
814   return chrec_dont_know;
815 }
816
817 \f
818
819 /* Observers.  */
820
821 /* Helper function for is_multivariate_chrec.  */
822
823 static bool 
824 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
825 {
826   if (chrec == NULL_TREE)
827     return false;
828   
829   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
830     {
831       if (CHREC_VARIABLE (chrec) != rec_var)
832         return true;
833       else
834         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) 
835                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
836     }
837   else
838     return false;
839 }
840
841 /* Determine whether the given chrec is multivariate or not.  */
842
843 bool 
844 is_multivariate_chrec (tree chrec)
845 {
846   if (chrec == NULL_TREE)
847     return false;
848   
849   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
850     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), 
851                                        CHREC_VARIABLE (chrec))
852             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), 
853                                           CHREC_VARIABLE (chrec)));
854   else
855     return false;
856 }
857
858 /* Determines whether the chrec contains symbolic names or not.  */
859
860 bool 
861 chrec_contains_symbols (tree chrec)
862 {
863   int i, n;
864
865   if (chrec == NULL_TREE)
866     return false;
867   
868   if (TREE_CODE (chrec) == SSA_NAME
869       || TREE_CODE (chrec) == VAR_DECL
870       || TREE_CODE (chrec) == PARM_DECL
871       || TREE_CODE (chrec) == FUNCTION_DECL
872       || TREE_CODE (chrec) == LABEL_DECL
873       || TREE_CODE (chrec) == RESULT_DECL
874       || TREE_CODE (chrec) == FIELD_DECL)
875     return true;
876
877   n = TREE_OPERAND_LENGTH (chrec);
878   for (i = 0; i < n; i++)
879     if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
880       return true;
881   return false;
882 }
883
884 /* Determines whether the chrec contains undetermined coefficients.  */
885
886 bool 
887 chrec_contains_undetermined (tree chrec)
888 {
889   int i, n;
890
891   if (chrec == chrec_dont_know)
892     return true;
893
894   if (chrec == NULL_TREE)
895     return false;
896
897   n = TREE_OPERAND_LENGTH (chrec);
898   for (i = 0; i < n; i++)
899     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
900       return true;
901   return false;
902 }
903
904 /* Determines whether the tree EXPR contains chrecs, and increment
905    SIZE if it is not a NULL pointer by an estimation of the depth of
906    the tree.  */
907
908 bool
909 tree_contains_chrecs (tree expr, int *size)
910 {
911   int i, n;
912
913   if (expr == NULL_TREE)
914     return false;
915
916   if (size)
917     (*size)++;
918   
919   if (tree_is_chrec (expr))
920     return true;
921
922   n = TREE_OPERAND_LENGTH (expr);
923   for (i = 0; i < n; i++)
924     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
925       return true;
926   return false;
927 }
928
929 /* Recursive helper function.  */
930
931 static bool
932 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
933 {
934   if (evolution_function_is_constant_p (chrec))
935     return true;
936
937   if (TREE_CODE (chrec) == SSA_NAME 
938       && expr_invariant_in_loop_p (get_loop (loopnum), chrec))
939     return true;
940
941   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
942     {
943       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
944           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
945                                                      loopnum)
946           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
947                                                      loopnum))
948         return false;
949       return true;
950     }
951
952   switch (TREE_OPERAND_LENGTH (chrec))
953     {
954     case 2:
955       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
956                                                   loopnum))
957         return false;
958       
959     case 1:
960       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
961                                                   loopnum))
962         return false;
963       return true;
964
965     default:
966       return false;
967     }
968
969   return false;
970 }
971
972 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
973
974 bool
975 evolution_function_is_invariant_p (tree chrec, int loopnum)
976 {
977   if (evolution_function_is_constant_p (chrec))
978     return true;
979   
980   if (current_loops != NULL)
981     return evolution_function_is_invariant_rec_p (chrec, loopnum);
982
983   return false;
984 }
985
986 /* Determine whether the given tree is an affine multivariate
987    evolution.  */
988
989 bool 
990 evolution_function_is_affine_multivariate_p (tree chrec, int loopnum)
991 {
992   if (chrec == NULL_TREE)
993     return false;
994   
995   switch (TREE_CODE (chrec))
996     {
997     case POLYNOMIAL_CHREC:
998       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
999         {
1000           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1001             return true;
1002           else
1003             {
1004               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1005                   && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 
1006                      != CHREC_VARIABLE (chrec)
1007                   && evolution_function_is_affine_multivariate_p 
1008                   (CHREC_RIGHT (chrec), loopnum))
1009                 return true;
1010               else
1011                 return false;
1012             }
1013         }
1014       else
1015         {
1016           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1017               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1018               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1019               && evolution_function_is_affine_multivariate_p 
1020               (CHREC_LEFT (chrec), loopnum))
1021             return true;
1022           else
1023             return false;
1024         }
1025       
1026     default:
1027       return false;
1028     }
1029 }
1030
1031 /* Determine whether the given tree is a function in zero or one 
1032    variables.  */
1033
1034 bool
1035 evolution_function_is_univariate_p (tree chrec)
1036 {
1037   if (chrec == NULL_TREE)
1038     return true;
1039   
1040   switch (TREE_CODE (chrec))
1041     {
1042     case POLYNOMIAL_CHREC:
1043       switch (TREE_CODE (CHREC_LEFT (chrec)))
1044         {
1045         case POLYNOMIAL_CHREC:
1046           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1047             return false;
1048           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1049             return false;
1050           break;
1051           
1052         default:
1053           break;
1054         }
1055       
1056       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1057         {
1058         case POLYNOMIAL_CHREC:
1059           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1060             return false;
1061           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1062             return false;
1063           break;
1064           
1065         default:
1066           break;          
1067         }
1068       
1069     default:
1070       return true;
1071     }
1072 }
1073
1074 /* Returns the number of variables of CHREC.  Example: the call
1075    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1076
1077 unsigned 
1078 nb_vars_in_chrec (tree chrec)
1079 {
1080   if (chrec == NULL_TREE)
1081     return 0;
1082
1083   switch (TREE_CODE (chrec))
1084     {
1085     case POLYNOMIAL_CHREC:
1086       return 1 + nb_vars_in_chrec 
1087         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1088
1089     default:
1090       return 0;
1091     }
1092 }
1093
1094 /* Returns true if TYPE is a type in that we cannot directly perform
1095    arithmetics, even though it is a scalar type.  */
1096
1097 static bool
1098 avoid_arithmetics_in_type_p (tree type)
1099 {
1100   /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1101      in the subtype, but a base type must be used, and the result then can
1102      be casted to the subtype.  */
1103   if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1104     return true;
1105
1106   return false;
1107 }
1108
1109 static tree chrec_convert_1 (tree, tree, tree, bool);
1110
1111 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1112    the scev corresponds to.  AT_STMT is the statement at that the scev is
1113    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1114    the rules for overflow of the given language apply (e.g., that signed
1115    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1116    tests, but also to enforce that the result follows them.  Returns true if the
1117    conversion succeeded, false otherwise.  */
1118
1119 bool
1120 convert_affine_scev (struct loop *loop, tree type,
1121                      tree *base, tree *step, tree at_stmt,
1122                      bool use_overflow_semantics)
1123 {
1124   tree ct = TREE_TYPE (*step);
1125   bool enforce_overflow_semantics;
1126   bool must_check_src_overflow, must_check_rslt_overflow;
1127   tree new_base, new_step;
1128
1129   /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1130   if (avoid_arithmetics_in_type_p (type))
1131     return false;
1132
1133   /* In general,
1134      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1135      but we must check some assumptions.
1136      
1137      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1138         of CT is smaller than the precision of TYPE.  For example, when we
1139         cast unsigned char [254, +, 1] to unsigned, the values on left side
1140         are 254, 255, 0, 1, ..., but those on the right side are
1141         254, 255, 256, 257, ...
1142      2) In case that we must also preserve the fact that signed ivs do not
1143         overflow, we must additionally check that the new iv does not wrap.
1144         For example, unsigned char [125, +, 1] casted to signed char could
1145         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1146         which would confuse optimizers that assume that this does not
1147         happen.  */
1148   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1149
1150   enforce_overflow_semantics = (use_overflow_semantics
1151                                 && nowrap_type_p (type));
1152   if (enforce_overflow_semantics)
1153     {
1154       /* We can avoid checking whether the result overflows in the following
1155          cases:
1156
1157          -- must_check_src_overflow is true, and the range of TYPE is superset
1158             of the range of CT -- i.e., in all cases except if CT signed and
1159             TYPE unsigned.
1160          -- both CT and TYPE have the same precision and signedness, and we
1161             verify instead that the source does not overflow (this may be
1162             easier than verifying it for the result, as we may use the
1163             information about the semantics of overflow in CT).  */
1164       if (must_check_src_overflow)
1165         {
1166           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1167             must_check_rslt_overflow = true;
1168           else
1169             must_check_rslt_overflow = false;
1170         }
1171       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1172                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1173         {
1174           must_check_rslt_overflow = false;
1175           must_check_src_overflow = true;
1176         }
1177       else
1178         must_check_rslt_overflow = true;
1179     }
1180   else
1181     must_check_rslt_overflow = false;
1182
1183   if (must_check_src_overflow
1184       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1185                                 use_overflow_semantics))
1186     return false;
1187
1188   new_base = chrec_convert_1 (type, *base, at_stmt,
1189                               use_overflow_semantics);
1190   /* The step must be sign extended, regardless of the signedness
1191      of CT and TYPE.  This only needs to be handled specially when
1192      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1193      (with values 100, 99, 98, ...) from becoming signed or unsigned
1194      [100, +, 255] with values 100, 355, ...; the sign-extension is 
1195      performed by default when CT is signed.  */
1196   new_step = *step;
1197   if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1198     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1199                                 use_overflow_semantics);
1200   new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
1201
1202   if (automatically_generated_chrec_p (new_base)
1203       || automatically_generated_chrec_p (new_step))
1204     return false;
1205
1206   if (must_check_rslt_overflow
1207       /* Note that in this case we cannot use the fact that signed variables
1208          do not overflow, as this is what we are verifying for the new iv.  */
1209       && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1210     return false;
1211
1212   *base = new_base;
1213   *step = new_step;
1214   return true;
1215 }
1216 \f
1217
1218 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1219    which the CHREC is built, it sets AT_STMT to the statement that
1220    contains the definition of the analyzed variable, otherwise the
1221    conversion is less accurate: the information is used for
1222    determining a more accurate estimation of the number of iterations.
1223    By default AT_STMT could be safely set to NULL_TREE.
1224
1225    The following rule is always true: TREE_TYPE (chrec) ==
1226    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1227    An example of what could happen when adding two chrecs and the type
1228    of the CHREC_RIGHT is different than CHREC_LEFT is:
1229    
1230    {(uint) 0, +, (uchar) 10} +
1231    {(uint) 0, +, (uchar) 250}
1232    
1233    that would produce a wrong result if CHREC_RIGHT is not (uint):
1234    
1235    {(uint) 0, +, (uchar) 4}
1236
1237    instead of
1238
1239    {(uint) 0, +, (uint) 260}
1240 */
1241
1242 tree 
1243 chrec_convert (tree type, tree chrec, tree at_stmt)
1244 {
1245   return chrec_convert_1 (type, chrec, at_stmt, true);
1246 }
1247
1248 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1249    which the CHREC is built, it sets AT_STMT to the statement that
1250    contains the definition of the analyzed variable, otherwise the
1251    conversion is less accurate: the information is used for
1252    determining a more accurate estimation of the number of iterations.
1253    By default AT_STMT could be safely set to NULL_TREE.
1254  
1255    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1256    the rules for overflow of the given language apply (e.g., that signed
1257    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1258    tests, but also to enforce that the result follows them.  */
1259
1260 static tree 
1261 chrec_convert_1 (tree type, tree chrec, tree at_stmt,
1262                  bool use_overflow_semantics)
1263 {
1264   tree ct, res;
1265   tree base, step;
1266   struct loop *loop;
1267
1268   if (automatically_generated_chrec_p (chrec))
1269     return chrec;
1270   
1271   ct = chrec_type (chrec);
1272   if (ct == type)
1273     return chrec;
1274
1275   if (!evolution_function_is_affine_p (chrec))
1276     goto keep_cast;
1277
1278   loop = get_chrec_loop (chrec);
1279   base = CHREC_LEFT (chrec);
1280   step = CHREC_RIGHT (chrec);
1281
1282   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1283                            use_overflow_semantics))
1284     return build_polynomial_chrec (loop->num, base, step);
1285
1286   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1287 keep_cast:
1288   res = fold_convert (type, chrec);
1289
1290   /* Don't propagate overflows.  */
1291   if (CONSTANT_CLASS_P (res))
1292     TREE_OVERFLOW (res) = 0;
1293
1294   /* But reject constants that don't fit in their type after conversion.
1295      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1296      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1297      and can cause problems later when computing niters of loops.  Note
1298      that we don't do the check before converting because we don't want
1299      to reject conversions of negative chrecs to unsigned types.  */
1300   if (TREE_CODE (res) == INTEGER_CST
1301       && TREE_CODE (type) == INTEGER_TYPE
1302       && !int_fits_type_p (res, type))
1303     res = chrec_dont_know;
1304
1305   return res;
1306 }
1307
1308 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1309    chrec if something else than what chrec_convert would do happens, NULL_TREE
1310    otherwise.  */
1311
1312 tree
1313 chrec_convert_aggressive (tree type, tree chrec)
1314 {
1315   tree inner_type, left, right, lc, rc;
1316
1317   if (automatically_generated_chrec_p (chrec)
1318       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1319     return NULL_TREE;
1320
1321   inner_type = TREE_TYPE (chrec);
1322   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1323     return NULL_TREE;
1324
1325   /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1326   if (avoid_arithmetics_in_type_p (type))
1327     return NULL_TREE;
1328
1329   left = CHREC_LEFT (chrec);
1330   right = CHREC_RIGHT (chrec);
1331   lc = chrec_convert_aggressive (type, left);
1332   if (!lc)
1333     lc = chrec_convert (type, left, NULL_TREE);
1334   rc = chrec_convert_aggressive (type, right);
1335   if (!rc)
1336     rc = chrec_convert (type, right, NULL_TREE);
1337  
1338   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1339 }
1340
1341 /* Returns true when CHREC0 == CHREC1.  */
1342
1343 bool 
1344 eq_evolutions_p (tree chrec0, 
1345                  tree chrec1)
1346 {
1347   if (chrec0 == NULL_TREE
1348       || chrec1 == NULL_TREE
1349       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1350     return false;
1351
1352   if (chrec0 == chrec1)
1353     return true;
1354
1355   switch (TREE_CODE (chrec0))
1356     {
1357     case INTEGER_CST:
1358       return operand_equal_p (chrec0, chrec1, 0);
1359
1360     case POLYNOMIAL_CHREC:
1361       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1362               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1363               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1364     default:
1365       return false;
1366     }  
1367 }
1368
1369 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1370    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1371    which of these cases happens.  */
1372
1373 enum ev_direction
1374 scev_direction (tree chrec)
1375 {
1376   tree step;
1377
1378   if (!evolution_function_is_affine_p (chrec))
1379     return EV_DIR_UNKNOWN;
1380
1381   step = CHREC_RIGHT (chrec);
1382   if (TREE_CODE (step) != INTEGER_CST)
1383     return EV_DIR_UNKNOWN;
1384
1385   if (tree_int_cst_sign_bit (step))
1386     return EV_DIR_DECREASES;
1387   else
1388     return EV_DIR_GROWS;
1389 }