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