gcc/tree-chrec.c

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