gcc/tree-chrec.c

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