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)
 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_constant_p (CHREC_LEFT (chrec)))
 999         {
1000           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
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)))
1009                 return true;
1010               else
1011                 return false;
1012             }
1013         }
1014       else
1015         {
1016           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
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)))
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 }