gcc/tree-chrec.c

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