gcc/tree-chrec.cc

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