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