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