gcc/tree-chrec.c

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