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