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       || chrec == chrec_not_analyzed_yet
 893       || chrec == NULL_TREE)
 894     return true;
 895
 896   n = TREE_OPERAND_LENGTH (chrec);
 897   for (i = 0; i < n; i++)
 898     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
 899       return true;
 900   return false;
 901 }
 902
 903 /* Determines whether the tree EXPR contains chrecs, and increment
 904    SIZE if it is not a NULL pointer by an estimation of the depth of
 905    the tree.  */
 906
 907 bool
 908 tree_contains_chrecs (tree expr, int *size)
 909 {
 910   int i, n;
 911
 912   if (expr == NULL_TREE)
 913     return false;
 914
 915   if (size)
 916     (*size)++;
 917
 918   if (tree_is_chrec (expr))
 919     return true;
 920
 921   n = TREE_OPERAND_LENGTH (expr);
 922   for (i = 0; i < n; i++)
 923     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
 924       return true;
 925   return false;
 926 }
 927
 928 /* Recursive helper function.  */
 929
 930 static bool
 931 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 932 {
 933   if (evolution_function_is_constant_p (chrec))
 934     return true;
 935
 936   if (TREE_CODE (chrec) == SSA_NAME
 937       && expr_invariant_in_loop_p (get_loop (loopnum), chrec))
 938     return true;
 939
 940   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 941     {
 942       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
 943           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
 944                                                      loopnum)
 945           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
 946                                                      loopnum))
 947         return false;
 948       return true;
 949     }
 950
 951   switch (TREE_OPERAND_LENGTH (chrec))
 952     {
 953     case 2:
 954       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
 955                                                   loopnum))
 956         return false;
 957
 958     case 1:
 959       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
 960                                                   loopnum))
 961         return false;
 962       return true;
 963
 964     default:
 965       return false;
 966     }
 967
 968   return false;
 969 }
 970
 971 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
 972
 973 bool
 974 evolution_function_is_invariant_p (tree chrec, int loopnum)
 975 {
 976   if (evolution_function_is_constant_p (chrec))
 977     return true;
 978
 979   if (current_loops != NULL)
 980     return evolution_function_is_invariant_rec_p (chrec, loopnum);
 981
 982   return false;
 983 }
 984
 985 /* Determine whether the given tree is an affine multivariate
 986    evolution.  */
 987
 988 bool
 989 evolution_function_is_affine_multivariate_p (tree chrec)
 990 {
 991   if (chrec == NULL_TREE)
 992     return false;
 993
 994   switch (TREE_CODE (chrec))
 995     {
 996     case POLYNOMIAL_CHREC:
 997       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 998         {
 999           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
1000             return true;
1001           else
1002             {
1003               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1004                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1005                      != CHREC_VARIABLE (chrec)
1006                   && evolution_function_is_affine_multivariate_p
1007                   (CHREC_RIGHT (chrec)))
1008                 return true;
1009               else
1010                 return false;
1011             }
1012         }
1013       else
1014         {
1015           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1016               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1017               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1018               && evolution_function_is_affine_multivariate_p
1019               (CHREC_LEFT (chrec)))
1020             return true;
1021           else
1022             return false;
1023         }
1024
1025     default:
1026       return false;
1027     }
1028 }
1029
1030 /* Determine whether the given tree is a function in zero or one
1031    variables.  */
1032
1033 bool
1034 evolution_function_is_univariate_p (tree chrec)
1035 {
1036   if (chrec == NULL_TREE)
1037     return true;
1038
1039   switch (TREE_CODE (chrec))
1040     {
1041     case POLYNOMIAL_CHREC:
1042       switch (TREE_CODE (CHREC_LEFT (chrec)))
1043         {
1044         case POLYNOMIAL_CHREC:
1045           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1046             return false;
1047           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1048             return false;
1049           break;
1050
1051         default:
1052           break;
1053         }
1054
1055       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1056         {
1057         case POLYNOMIAL_CHREC:
1058           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1059             return false;
1060           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1061             return false;
1062           break;
1063
1064         default:
1065           break;
1066         }
1067
1068     default:
1069       return true;
1070     }
1071 }
1072
1073 /* Returns the number of variables of CHREC.  Example: the call
1074    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1075
1076 unsigned
1077 nb_vars_in_chrec (tree chrec)
1078 {
1079   if (chrec == NULL_TREE)
1080     return 0;
1081
1082   switch (TREE_CODE (chrec))
1083     {
1084     case POLYNOMIAL_CHREC:
1085       return 1 + nb_vars_in_chrec
1086         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1087
1088     default:
1089       return 0;
1090     }
1091 }
1092
1093 /* Returns true if TYPE is a type in that we cannot directly perform
1094    arithmetics, even though it is a scalar type.  */
1095
1096 static bool
1097 avoid_arithmetics_in_type_p (tree type)
1098 {
1099   /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1100      in the subtype, but a base type must be used, and the result then can
1101      be casted to the subtype.  */
1102   if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1103     return true;
1104
1105   return false;
1106 }
1107
1108 static tree chrec_convert_1 (tree, tree, tree, bool);
1109
1110 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1111    the scev corresponds to.  AT_STMT is the statement at that the scev is
1112    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1113    the rules for overflow of the given language apply (e.g., that signed
1114    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1115    tests, but also to enforce that the result follows them.  Returns true if the
1116    conversion succeeded, false otherwise.  */
1117
1118 bool
1119 convert_affine_scev (struct loop *loop, tree type,
1120                      tree *base, tree *step, tree at_stmt,
1121                      bool use_overflow_semantics)
1122 {
1123   tree ct = TREE_TYPE (*step);
1124   bool enforce_overflow_semantics;
1125   bool must_check_src_overflow, must_check_rslt_overflow;
1126   tree new_base, new_step;
1127
1128   /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1129   if (avoid_arithmetics_in_type_p (type))
1130     return false;
1131
1132   /* In general,
1133      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1134      but we must check some assumptions.
1135
1136      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1137         of CT is smaller than the precision of TYPE.  For example, when we
1138         cast unsigned char [254, +, 1] to unsigned, the values on left side
1139         are 254, 255, 0, 1, ..., but those on the right side are
1140         254, 255, 256, 257, ...
1141      2) In case that we must also preserve the fact that signed ivs do not
1142         overflow, we must additionally check that the new iv does not wrap.
1143         For example, unsigned char [125, +, 1] casted to signed char could
1144         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1145         which would confuse optimizers that assume that this does not
1146         happen.  */
1147   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1148
1149   enforce_overflow_semantics = (use_overflow_semantics
1150                                 && nowrap_type_p (type));
1151   if (enforce_overflow_semantics)
1152     {
1153       /* We can avoid checking whether the result overflows in the following
1154          cases:
1155
1156          -- must_check_src_overflow is true, and the range of TYPE is superset
1157             of the range of CT -- i.e., in all cases except if CT signed and
1158             TYPE unsigned.
1159          -- both CT and TYPE have the same precision and signedness, and we
1160             verify instead that the source does not overflow (this may be
1161             easier than verifying it for the result, as we may use the
1162             information about the semantics of overflow in CT).  */
1163       if (must_check_src_overflow)
1164         {
1165           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1166             must_check_rslt_overflow = true;
1167           else
1168             must_check_rslt_overflow = false;
1169         }
1170       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1171                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1172         {
1173           must_check_rslt_overflow = false;
1174           must_check_src_overflow = true;
1175         }
1176       else
1177         must_check_rslt_overflow = true;
1178     }
1179   else
1180     must_check_rslt_overflow = false;
1181
1182   if (must_check_src_overflow
1183       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1184                                 use_overflow_semantics))
1185     return false;
1186
1187   new_base = chrec_convert_1 (type, *base, at_stmt,
1188                               use_overflow_semantics);
1189   /* The step must be sign extended, regardless of the signedness
1190      of CT and TYPE.  This only needs to be handled specially when
1191      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1192      (with values 100, 99, 98, ...) from becoming signed or unsigned
1193      [100, +, 255] with values 100, 355, ...; the sign-extension is
1194      performed by default when CT is signed.  */
1195   new_step = *step;
1196   if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1197     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1198                                 use_overflow_semantics);
1199   new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
1200
1201   if (automatically_generated_chrec_p (new_base)
1202       || automatically_generated_chrec_p (new_step))
1203     return false;
1204
1205   if (must_check_rslt_overflow
1206       /* Note that in this case we cannot use the fact that signed variables
1207          do not overflow, as this is what we are verifying for the new iv.  */
1208       && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1209     return false;
1210
1211   *base = new_base;
1212   *step = new_step;
1213   return true;
1214 }
1215 \f
1216
1217 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1218    which the CHREC is built, it sets AT_STMT to the statement that
1219    contains the definition of the analyzed variable, otherwise the
1220    conversion is less accurate: the information is used for
1221    determining a more accurate estimation of the number of iterations.
1222    By default AT_STMT could be safely set to NULL_TREE.
1223
1224    The following rule is always true: TREE_TYPE (chrec) ==
1225    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1226    An example of what could happen when adding two chrecs and the type
1227    of the CHREC_RIGHT is different than CHREC_LEFT is:
1228
1229    {(uint) 0, +, (uchar) 10} +
1230    {(uint) 0, +, (uchar) 250}
1231
1232    that would produce a wrong result if CHREC_RIGHT is not (uint):
1233
1234    {(uint) 0, +, (uchar) 4}
1235
1236    instead of
1237
1238    {(uint) 0, +, (uint) 260}
1239 */
1240
1241 tree
1242 chrec_convert (tree type, tree chrec, tree at_stmt)
1243 {
1244   return chrec_convert_1 (type, chrec, at_stmt, true);
1245 }
1246
1247 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1248    which the CHREC is built, it sets AT_STMT to the statement that
1249    contains the definition of the analyzed variable, otherwise the
1250    conversion is less accurate: the information is used for
1251    determining a more accurate estimation of the number of iterations.
1252    By default AT_STMT could be safely set to NULL_TREE.
1253
1254    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1255    the rules for overflow of the given language apply (e.g., that signed
1256    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1257    tests, but also to enforce that the result follows them.  */
1258
1259 static tree
1260 chrec_convert_1 (tree type, tree chrec, tree at_stmt,
1261                  bool use_overflow_semantics)
1262 {
1263   tree ct, res;
1264   tree base, step;
1265   struct loop *loop;
1266
1267   if (automatically_generated_chrec_p (chrec))
1268     return chrec;
1269
1270   ct = chrec_type (chrec);
1271   if (ct == type)
1272     return chrec;
1273
1274   if (!evolution_function_is_affine_p (chrec))
1275     goto keep_cast;
1276
1277   loop = get_chrec_loop (chrec);
1278   base = CHREC_LEFT (chrec);
1279   step = CHREC_RIGHT (chrec);
1280
1281   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1282                            use_overflow_semantics))
1283     return build_polynomial_chrec (loop->num, base, step);
1284
1285   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1286 keep_cast:
1287   res = fold_convert (type, chrec);
1288
1289   /* Don't propagate overflows.  */
1290   if (CONSTANT_CLASS_P (res))
1291     TREE_OVERFLOW (res) = 0;
1292
1293   /* But reject constants that don't fit in their type after conversion.
1294      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1295      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1296      and can cause problems later when computing niters of loops.  Note
1297      that we don't do the check before converting because we don't want
1298      to reject conversions of negative chrecs to unsigned types.  */
1299   if (TREE_CODE (res) == INTEGER_CST
1300       && TREE_CODE (type) == INTEGER_TYPE
1301       && !int_fits_type_p (res, type))
1302     res = chrec_dont_know;
1303
1304   return res;
1305 }
1306
1307 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1308    chrec if something else than what chrec_convert would do happens, NULL_TREE
1309    otherwise.  */
1310
1311 tree
1312 chrec_convert_aggressive (tree type, tree chrec)
1313 {
1314   tree inner_type, left, right, lc, rc;
1315
1316   if (automatically_generated_chrec_p (chrec)
1317       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1318     return NULL_TREE;
1319
1320   inner_type = TREE_TYPE (chrec);
1321   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1322     return NULL_TREE;
1323
1324   /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1325   if (avoid_arithmetics_in_type_p (type))
1326     return NULL_TREE;
1327
1328   left = CHREC_LEFT (chrec);
1329   right = CHREC_RIGHT (chrec);
1330   lc = chrec_convert_aggressive (type, left);
1331   if (!lc)
1332     lc = chrec_convert (type, left, NULL_TREE);
1333   rc = chrec_convert_aggressive (type, right);
1334   if (!rc)
1335     rc = chrec_convert (type, right, NULL_TREE);
1336
1337   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1338 }
1339
1340 /* Returns true when CHREC0 == CHREC1.  */
1341
1342 bool
1343 eq_evolutions_p (tree chrec0,
1344                  tree chrec1)
1345 {
1346   if (chrec0 == NULL_TREE
1347       || chrec1 == NULL_TREE
1348       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1349     return false;
1350
1351   if (chrec0 == chrec1)
1352     return true;
1353
1354   switch (TREE_CODE (chrec0))
1355     {
1356     case INTEGER_CST:
1357       return operand_equal_p (chrec0, chrec1, 0);
1358
1359     case POLYNOMIAL_CHREC:
1360       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1361               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1362               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1363     default:
1364       return false;
1365     }
1366 }
1367
1368 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1369    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1370    which of these cases happens.  */
1371
1372 enum ev_direction
1373 scev_direction (tree chrec)
1374 {
1375   tree step;
1376
1377   if (!evolution_function_is_affine_p (chrec))
1378     return EV_DIR_UNKNOWN;
1379
1380   step = CHREC_RIGHT (chrec);
1381   if (TREE_CODE (step) != INTEGER_CST)
1382     return EV_DIR_UNKNOWN;
1383
1384   if (tree_int_cst_sign_bit (step))
1385     return EV_DIR_DECREASES;
1386   else
1387     return EV_DIR_GROWS;
1388 }