gcc/tree-chrec.c

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