gcc/tree-chrec.c

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