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 /* For a given CHREC and an induction variable map IV_MAP that maps
 636    (loop->num, expr) for every loop number of the current_loops an
 637    expression, calls chrec_apply when the expression is not NULL.  */
 638
 639 tree
 640 chrec_apply_map (tree chrec, VEC (tree, heap) *iv_map)
 641 {
 642   int i;
 643   tree expr;
 644
 645   for (i = 0; VEC_iterate (tree, iv_map, i, expr); i++)
 646     if (expr)
 647       chrec = chrec_apply (i, chrec, expr);
 648
 649   return chrec;
 650 }
 651
 652 /* Replaces the initial condition in CHREC with INIT_COND.  */
 653
 654 tree
 655 chrec_replace_initial_condition (tree chrec,
 656                                  tree init_cond)
 657 {
 658   if (automatically_generated_chrec_p (chrec))
 659     return chrec;
 660
 661   gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
 662
 663   switch (TREE_CODE (chrec))
 664     {
 665     case POLYNOMIAL_CHREC:
 666       return build_polynomial_chrec
 667         (CHREC_VARIABLE (chrec),
 668          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 669          CHREC_RIGHT (chrec));
 670
 671     default:
 672       return init_cond;
 673     }
 674 }
 675
 676 /* Returns the initial condition of a given CHREC.  */
 677
 678 tree
 679 initial_condition (tree chrec)
 680 {
 681   if (automatically_generated_chrec_p (chrec))
 682     return chrec;
 683
 684   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 685     return initial_condition (CHREC_LEFT (chrec));
 686   else
 687     return chrec;
 688 }
 689
 690 /* Returns a univariate function that represents the evolution in
 691    LOOP_NUM.  Mask the evolution of any other loop.  */
 692
 693 tree
 694 hide_evolution_in_other_loops_than_loop (tree chrec,
 695                                          unsigned loop_num)
 696 {
 697   struct loop *loop = get_loop (loop_num), *chloop;
 698   if (automatically_generated_chrec_p (chrec))
 699     return chrec;
 700
 701   switch (TREE_CODE (chrec))
 702     {
 703     case POLYNOMIAL_CHREC:
 704       chloop = get_chrec_loop (chrec);
 705
 706       if (chloop == loop)
 707         return build_polynomial_chrec
 708           (loop_num,
 709            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 710                                                     loop_num),
 711            CHREC_RIGHT (chrec));
 712
 713       else if (flow_loop_nested_p (chloop, loop))
 714         /* There is no evolution in this loop.  */
 715         return initial_condition (chrec);
 716
 717       else
 718         {
 719           gcc_assert (flow_loop_nested_p (loop, chloop));
 720           return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 721                                                           loop_num);
 722         }
 723
 724     default:
 725       return chrec;
 726     }
 727 }
 728
 729 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 730    true, otherwise returns the initial condition in LOOP_NUM.  */
 731
 732 static tree
 733 chrec_component_in_loop_num (tree chrec,
 734                              unsigned loop_num,
 735                              bool right)
 736 {
 737   tree component;
 738   struct loop *loop = get_loop (loop_num), *chloop;
 739
 740   if (automatically_generated_chrec_p (chrec))
 741     return chrec;
 742
 743   switch (TREE_CODE (chrec))
 744     {
 745     case POLYNOMIAL_CHREC:
 746       chloop = get_chrec_loop (chrec);
 747
 748       if (chloop == loop)
 749         {
 750           if (right)
 751             component = CHREC_RIGHT (chrec);
 752           else
 753             component = CHREC_LEFT (chrec);
 754
 755           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 756               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 757             return component;
 758
 759           else
 760             return build_polynomial_chrec
 761               (loop_num,
 762                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 763                                             loop_num,
 764                                             right),
 765                component);
 766         }
 767
 768       else if (flow_loop_nested_p (chloop, loop))
 769         /* There is no evolution part in this loop.  */
 770         return NULL_TREE;
 771
 772       else
 773         {
 774           gcc_assert (flow_loop_nested_p (loop, chloop));
 775           return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 776                                               loop_num,
 777                                               right);
 778         }
 779
 780      default:
 781       if (right)
 782         return NULL_TREE;
 783       else
 784         return chrec;
 785     }
 786 }
 787
 788 /* Returns the evolution part in LOOP_NUM.  Example: the call
 789    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 790    {1, +, 2}_1  */
 791
 792 tree
 793 evolution_part_in_loop_num (tree chrec,
 794                             unsigned loop_num)
 795 {
 796   return chrec_component_in_loop_num (chrec, loop_num, true);
 797 }
 798
 799 /* Returns the initial condition in LOOP_NUM.  Example: the call
 800    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 801    {0, +, 1}_1  */
 802
 803 tree
 804 initial_condition_in_loop_num (tree chrec,
 805                                unsigned loop_num)
 806 {
 807   return chrec_component_in_loop_num (chrec, loop_num, false);
 808 }
 809
 810 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 811    This function is essentially used for setting the evolution to
 812    chrec_dont_know, for example after having determined that it is
 813    impossible to say how many times a loop will execute.  */
 814
 815 tree
 816 reset_evolution_in_loop (unsigned loop_num,
 817                          tree chrec,
 818                          tree new_evol)
 819 {
 820   struct loop *loop = get_loop (loop_num);
 821
 822   if (POINTER_TYPE_P (chrec_type (chrec)))
 823     gcc_assert (sizetype == chrec_type (new_evol));
 824   else
 825     gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
 826
 827   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 828       && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
 829     {
 830       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 831                                            new_evol);
 832       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 833                                             new_evol);
 834       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
 835                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 836                      left, right);
 837     }
 838
 839   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 840          && CHREC_VARIABLE (chrec) == loop_num)
 841     chrec = CHREC_LEFT (chrec);
 842
 843   return build_polynomial_chrec (loop_num, chrec, new_evol);
 844 }
 845
 846 /* Merges two evolution functions that were found by following two
 847    alternate paths of a conditional expression.  */
 848
 849 tree
 850 chrec_merge (tree chrec1,
 851              tree chrec2)
 852 {
 853   if (chrec1 == chrec_dont_know
 854       || chrec2 == chrec_dont_know)
 855     return chrec_dont_know;
 856
 857   if (chrec1 == chrec_known
 858       || chrec2 == chrec_known)
 859     return chrec_known;
 860
 861   if (chrec1 == chrec_not_analyzed_yet)
 862     return chrec2;
 863   if (chrec2 == chrec_not_analyzed_yet)
 864     return chrec1;
 865
 866   if (eq_evolutions_p (chrec1, chrec2))
 867     return chrec1;
 868
 869   return chrec_dont_know;
 870 }
 871
 872 \f
 873
 874 /* Observers.  */
 875
 876 /* Helper function for is_multivariate_chrec.  */
 877
 878 static bool
 879 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
 880 {
 881   if (chrec == NULL_TREE)
 882     return false;
 883
 884   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 885     {
 886       if (CHREC_VARIABLE (chrec) != rec_var)
 887         return true;
 888       else
 889         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 890                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 891     }
 892   else
 893     return false;
 894 }
 895
 896 /* Determine whether the given chrec is multivariate or not.  */
 897
 898 bool
 899 is_multivariate_chrec (const_tree chrec)
 900 {
 901   if (chrec == NULL_TREE)
 902     return false;
 903
 904   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 905     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 906                                        CHREC_VARIABLE (chrec))
 907             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 908                                           CHREC_VARIABLE (chrec)));
 909   else
 910     return false;
 911 }
 912
 913 /* Determines whether the chrec contains symbolic names or not.  */
 914
 915 bool
 916 chrec_contains_symbols (const_tree chrec)
 917 {
 918   int i, n;
 919
 920   if (chrec == NULL_TREE)
 921     return false;
 922
 923   if (TREE_CODE (chrec) == SSA_NAME
 924       || TREE_CODE (chrec) == VAR_DECL
 925       || TREE_CODE (chrec) == PARM_DECL
 926       || TREE_CODE (chrec) == FUNCTION_DECL
 927       || TREE_CODE (chrec) == LABEL_DECL
 928       || TREE_CODE (chrec) == RESULT_DECL
 929       || TREE_CODE (chrec) == FIELD_DECL)
 930     return true;
 931
 932   n = TREE_OPERAND_LENGTH (chrec);
 933   for (i = 0; i < n; i++)
 934     if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
 935       return true;
 936   return false;
 937 }
 938
 939 /* Determines whether the chrec contains undetermined coefficients.  */
 940
 941 bool
 942 chrec_contains_undetermined (const_tree chrec)
 943 {
 944   int i, n;
 945
 946   if (chrec == chrec_dont_know)
 947     return true;
 948
 949   if (chrec == NULL_TREE)
 950     return false;
 951
 952   n = TREE_OPERAND_LENGTH (chrec);
 953   for (i = 0; i < n; i++)
 954     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
 955       return true;
 956   return false;
 957 }
 958
 959 /* Determines whether the tree EXPR contains chrecs, and increment
 960    SIZE if it is not a NULL pointer by an estimation of the depth of
 961    the tree.  */
 962
 963 bool
 964 tree_contains_chrecs (const_tree expr, int *size)
 965 {
 966   int i, n;
 967
 968   if (expr == NULL_TREE)
 969     return false;
 970
 971   if (size)
 972     (*size)++;
 973
 974   if (tree_is_chrec (expr))
 975     return true;
 976
 977   n = TREE_OPERAND_LENGTH (expr);
 978   for (i = 0; i < n; i++)
 979     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
 980       return true;
 981   return false;
 982 }
 983
 984 /* Recursive helper function.  */
 985
 986 static bool
 987 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 988 {
 989   if (evolution_function_is_constant_p (chrec))
 990     return true;
 991
 992   if (TREE_CODE (chrec) == SSA_NAME
 993       && (loopnum == 0
 994           || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
 995     return true;
 996
 997   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 998     {
 999       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1000           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1001                                                      loopnum)
1002           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1003                                                      loopnum))
1004         return false;
1005       return true;
1006     }
1007
1008   switch (TREE_OPERAND_LENGTH (chrec))
1009     {
1010     case 2:
1011       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1012                                                   loopnum))
1013         return false;
1014
1015     case 1:
1016       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1017                                                   loopnum))
1018         return false;
1019       return true;
1020
1021     default:
1022       return false;
1023     }
1024
1025   return false;
1026 }
1027
1028 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1029
1030 bool
1031 evolution_function_is_invariant_p (tree chrec, int loopnum)
1032 {
1033   return evolution_function_is_invariant_rec_p (chrec, loopnum);
1034 }
1035
1036 /* Determine whether the given tree is an affine multivariate
1037    evolution.  */
1038
1039 bool
1040 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1041 {
1042   if (chrec == NULL_TREE)
1043     return false;
1044
1045   switch (TREE_CODE (chrec))
1046     {
1047     case POLYNOMIAL_CHREC:
1048       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1049         {
1050           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1051             return true;
1052           else
1053             {
1054               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1055                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1056                      != CHREC_VARIABLE (chrec)
1057                   && evolution_function_is_affine_multivariate_p
1058                   (CHREC_RIGHT (chrec), loopnum))
1059                 return true;
1060               else
1061                 return false;
1062             }
1063         }
1064       else
1065         {
1066           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1067               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1068               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1069               && evolution_function_is_affine_multivariate_p
1070               (CHREC_LEFT (chrec), loopnum))
1071             return true;
1072           else
1073             return false;
1074         }
1075
1076     default:
1077       return false;
1078     }
1079 }
1080
1081 /* Determine whether the given tree is a function in zero or one
1082    variables.  */
1083
1084 bool
1085 evolution_function_is_univariate_p (const_tree chrec)
1086 {
1087   if (chrec == NULL_TREE)
1088     return true;
1089
1090   switch (TREE_CODE (chrec))
1091     {
1092     case POLYNOMIAL_CHREC:
1093       switch (TREE_CODE (CHREC_LEFT (chrec)))
1094         {
1095         case POLYNOMIAL_CHREC:
1096           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1097             return false;
1098           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1099             return false;
1100           break;
1101
1102         default:
1103           break;
1104         }
1105
1106       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1107         {
1108         case POLYNOMIAL_CHREC:
1109           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1110             return false;
1111           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1112             return false;
1113           break;
1114
1115         default:
1116           break;
1117         }
1118
1119     default:
1120       return true;
1121     }
1122 }
1123
1124 /* Returns the number of variables of CHREC.  Example: the call
1125    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1126
1127 unsigned
1128 nb_vars_in_chrec (tree chrec)
1129 {
1130   if (chrec == NULL_TREE)
1131     return 0;
1132
1133   switch (TREE_CODE (chrec))
1134     {
1135     case POLYNOMIAL_CHREC:
1136       return 1 + nb_vars_in_chrec
1137         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1138
1139     default:
1140       return 0;
1141     }
1142 }
1143
1144 static tree chrec_convert_1 (tree, tree, gimple, bool);
1145
1146 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1147    the scev corresponds to.  AT_STMT is the statement at that the scev is
1148    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1149    the rules for overflow of the given language apply (e.g., that signed
1150    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1151    tests, but also to enforce that the result follows them.  Returns true if the
1152    conversion succeeded, false otherwise.  */
1153
1154 bool
1155 convert_affine_scev (struct loop *loop, tree type,
1156                      tree *base, tree *step, gimple at_stmt,
1157                      bool use_overflow_semantics)
1158 {
1159   tree ct = TREE_TYPE (*step);
1160   bool enforce_overflow_semantics;
1161   bool must_check_src_overflow, must_check_rslt_overflow;
1162   tree new_base, new_step;
1163   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1164
1165   /* In general,
1166      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1167      but we must check some assumptions.
1168
1169      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1170         of CT is smaller than the precision of TYPE.  For example, when we
1171         cast unsigned char [254, +, 1] to unsigned, the values on left side
1172         are 254, 255, 0, 1, ..., but those on the right side are
1173         254, 255, 256, 257, ...
1174      2) In case that we must also preserve the fact that signed ivs do not
1175         overflow, we must additionally check that the new iv does not wrap.
1176         For example, unsigned char [125, +, 1] casted to signed char could
1177         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1178         which would confuse optimizers that assume that this does not
1179         happen.  */
1180   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1181
1182   enforce_overflow_semantics = (use_overflow_semantics
1183                                 && nowrap_type_p (type));
1184   if (enforce_overflow_semantics)
1185     {
1186       /* We can avoid checking whether the result overflows in the following
1187          cases:
1188
1189          -- must_check_src_overflow is true, and the range of TYPE is superset
1190             of the range of CT -- i.e., in all cases except if CT signed and
1191             TYPE unsigned.
1192          -- both CT and TYPE have the same precision and signedness, and we
1193             verify instead that the source does not overflow (this may be
1194             easier than verifying it for the result, as we may use the
1195             information about the semantics of overflow in CT).  */
1196       if (must_check_src_overflow)
1197         {
1198           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1199             must_check_rslt_overflow = true;
1200           else
1201             must_check_rslt_overflow = false;
1202         }
1203       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1204                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1205         {
1206           must_check_rslt_overflow = false;
1207           must_check_src_overflow = true;
1208         }
1209       else
1210         must_check_rslt_overflow = true;
1211     }
1212   else
1213     must_check_rslt_overflow = false;
1214
1215   if (must_check_src_overflow
1216       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1217                                 use_overflow_semantics))
1218     return false;
1219
1220   new_base = chrec_convert_1 (type, *base, at_stmt,
1221                               use_overflow_semantics);
1222   /* The step must be sign extended, regardless of the signedness
1223      of CT and TYPE.  This only needs to be handled specially when
1224      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1225      (with values 100, 99, 98, ...) from becoming signed or unsigned
1226      [100, +, 255] with values 100, 355, ...; the sign-extension is
1227      performed by default when CT is signed.  */
1228   new_step = *step;
1229   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1230     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1231                                 use_overflow_semantics);
1232   new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
1233
1234   if (automatically_generated_chrec_p (new_base)
1235       || automatically_generated_chrec_p (new_step))
1236     return false;
1237
1238   if (must_check_rslt_overflow
1239       /* Note that in this case we cannot use the fact that signed variables
1240          do not overflow, as this is what we are verifying for the new iv.  */
1241       && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1242     return false;
1243
1244   *base = new_base;
1245   *step = new_step;
1246   return true;
1247 }
1248 \f
1249
1250 /* Convert CHREC for the right hand side of a CHREC.
1251    The increment for a pointer type is always sizetype.  */
1252
1253 tree
1254 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
1255 {
1256   if (POINTER_TYPE_P (type))
1257     type = sizetype;
1258
1259   return chrec_convert (type, chrec, at_stmt);
1260 }
1261
1262 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1263    which the CHREC is built, it sets AT_STMT to the statement that
1264    contains the definition of the analyzed variable, otherwise the
1265    conversion is less accurate: the information is used for
1266    determining a more accurate estimation of the number of iterations.
1267    By default AT_STMT could be safely set to NULL_TREE.
1268
1269    The following rule is always true: TREE_TYPE (chrec) ==
1270    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1271    An example of what could happen when adding two chrecs and the type
1272    of the CHREC_RIGHT is different than CHREC_LEFT is:
1273
1274    {(uint) 0, +, (uchar) 10} +
1275    {(uint) 0, +, (uchar) 250}
1276
1277    that would produce a wrong result if CHREC_RIGHT is not (uint):
1278
1279    {(uint) 0, +, (uchar) 4}
1280
1281    instead of
1282
1283    {(uint) 0, +, (uint) 260}
1284 */
1285
1286 tree
1287 chrec_convert (tree type, tree chrec, gimple at_stmt)
1288 {
1289   return chrec_convert_1 (type, chrec, at_stmt, true);
1290 }
1291
1292 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1293    which the CHREC is built, it sets AT_STMT to the statement that
1294    contains the definition of the analyzed variable, otherwise the
1295    conversion is less accurate: the information is used for
1296    determining a more accurate estimation of the number of iterations.
1297    By default AT_STMT could be safely set to NULL_TREE.
1298
1299    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1300    the rules for overflow of the given language apply (e.g., that signed
1301    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1302    tests, but also to enforce that the result follows them.  */
1303
1304 static tree
1305 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
1306                  bool use_overflow_semantics)
1307 {
1308   tree ct, res;
1309   tree base, step;
1310   struct loop *loop;
1311
1312   if (automatically_generated_chrec_p (chrec))
1313     return chrec;
1314
1315   ct = chrec_type (chrec);
1316   if (ct == type)
1317     return chrec;
1318
1319   if (!evolution_function_is_affine_p (chrec))
1320     goto keep_cast;
1321
1322   loop = get_chrec_loop (chrec);
1323   base = CHREC_LEFT (chrec);
1324   step = CHREC_RIGHT (chrec);
1325
1326   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1327                            use_overflow_semantics))
1328     return build_polynomial_chrec (loop->num, base, step);
1329
1330   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1331 keep_cast:
1332   /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1333      may be more expensive.  We do want to perform this optimization here
1334      though for canonicalization reasons.  */
1335   if (use_overflow_semantics
1336       && (TREE_CODE (chrec) == PLUS_EXPR
1337           || TREE_CODE (chrec) == MINUS_EXPR)
1338       && TREE_CODE (type) == INTEGER_TYPE
1339       && TREE_CODE (ct) == INTEGER_TYPE
1340       && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1341       && TYPE_OVERFLOW_UNDEFINED (ct))
1342     res = fold_build2 (TREE_CODE (chrec), type,
1343                        fold_convert (type, TREE_OPERAND (chrec, 0)),
1344                        fold_convert (type, TREE_OPERAND (chrec, 1)));
1345   else
1346     res = fold_convert (type, chrec);
1347
1348   /* Don't propagate overflows.  */
1349   if (CONSTANT_CLASS_P (res))
1350     TREE_OVERFLOW (res) = 0;
1351
1352   /* But reject constants that don't fit in their type after conversion.
1353      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1354      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1355      and can cause problems later when computing niters of loops.  Note
1356      that we don't do the check before converting because we don't want
1357      to reject conversions of negative chrecs to unsigned types.  */
1358   if (TREE_CODE (res) == INTEGER_CST
1359       && TREE_CODE (type) == INTEGER_TYPE
1360       && !int_fits_type_p (res, type))
1361     res = chrec_dont_know;
1362
1363   return res;
1364 }
1365
1366 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1367    chrec if something else than what chrec_convert would do happens, NULL_TREE
1368    otherwise.  */
1369
1370 tree
1371 chrec_convert_aggressive (tree type, tree chrec)
1372 {
1373   tree inner_type, left, right, lc, rc, rtype;
1374
1375   if (automatically_generated_chrec_p (chrec)
1376       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1377     return NULL_TREE;
1378
1379   inner_type = TREE_TYPE (chrec);
1380   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1381     return NULL_TREE;
1382
1383   rtype = POINTER_TYPE_P (type) ? sizetype : type;
1384
1385   left = CHREC_LEFT (chrec);
1386   right = CHREC_RIGHT (chrec);
1387   lc = chrec_convert_aggressive (type, left);
1388   if (!lc)
1389     lc = chrec_convert (type, left, NULL);
1390   rc = chrec_convert_aggressive (rtype, right);
1391   if (!rc)
1392     rc = chrec_convert (rtype, right, NULL);
1393
1394   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1395 }
1396
1397 /* Returns true when CHREC0 == CHREC1.  */
1398
1399 bool
1400 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1401 {
1402   if (chrec0 == NULL_TREE
1403       || chrec1 == NULL_TREE
1404       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1405     return false;
1406
1407   if (chrec0 == chrec1)
1408     return true;
1409
1410   switch (TREE_CODE (chrec0))
1411     {
1412     case INTEGER_CST:
1413       return operand_equal_p (chrec0, chrec1, 0);
1414
1415     case POLYNOMIAL_CHREC:
1416       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1417               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1418               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1419     default:
1420       return false;
1421     }
1422 }
1423
1424 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1425    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1426    which of these cases happens.  */
1427
1428 enum ev_direction
1429 scev_direction (const_tree chrec)
1430 {
1431   const_tree step;
1432
1433   if (!evolution_function_is_affine_p (chrec))
1434     return EV_DIR_UNKNOWN;
1435
1436   step = CHREC_RIGHT (chrec);
1437   if (TREE_CODE (step) != INTEGER_CST)
1438     return EV_DIR_UNKNOWN;
1439
1440   if (tree_int_cst_sign_bit (step))
1441     return EV_DIR_DECREASES;
1442   else
1443     return EV_DIR_GROWS;
1444 }
1445
1446 /* Iterates over all the components of SCEV, and calls CBCK.  */
1447
1448 void
1449 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1450 {
1451   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1452     {
1453     case 3:
1454       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1455
1456     case 2:
1457       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1458
1459     case 1:
1460       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1461
1462     default:
1463       cbck (scev, data);
1464       break;
1465     }
1466 }
1467
1468 /* Returns true when the operation can be part of a linear
1469    expression.  */
1470
1471 static inline bool
1472 operator_is_linear (tree scev)
1473 {
1474   switch (TREE_CODE (scev))
1475     {
1476     case INTEGER_CST:
1477     case POLYNOMIAL_CHREC:
1478     case PLUS_EXPR:
1479     case POINTER_PLUS_EXPR:
1480     case MULT_EXPR:
1481     case MINUS_EXPR:
1482     case NEGATE_EXPR:
1483     case SSA_NAME:
1484     case NON_LVALUE_EXPR:
1485     case BIT_NOT_EXPR:
1486     CASE_CONVERT:
1487       return true;
1488
1489     default:
1490       return false;
1491     }
1492 }
1493
1494 /* Return true when SCEV is a linear expression.  Linear expressions
1495    can contain additions, substractions and multiplications.
1496    Multiplications are restricted to constant scaling: "cst * x".  */
1497
1498 bool
1499 scev_is_linear_expression (tree scev)
1500 {
1501   if (scev == NULL
1502       || !operator_is_linear (scev))
1503     return false;
1504
1505   if (TREE_CODE (scev) == MULT_EXPR)
1506     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1507              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1508
1509   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1510       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1511     return false;
1512
1513   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1514     {
1515     case 3:
1516       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1517         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1518         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1519
1520     case 2:
1521       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1522         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1523
1524     case 1:
1525       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1526
1527     case 0:
1528       return true;
1529
1530     default:
1531       return false;
1532     }
1533 }
1534
1535 /* Determines whether the expression CHREC contains only interger consts
1536    in the right parts.  */
1537
1538 bool
1539 evolution_function_right_is_integer_cst (const_tree chrec)
1540 {
1541   if (chrec == NULL_TREE)
1542     return false;
1543
1544   switch (TREE_CODE (chrec))
1545     {
1546     case INTEGER_CST:
1547       return true;
1548
1549     case POLYNOMIAL_CHREC:
1550       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1551         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1552             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1553
1554     CASE_CONVERT:
1555       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1556
1557     default:
1558       return false;
1559     }
1560 }
1561