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