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