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