gcc/tree-chrec.cc

   1 /* Chains of recurrences.
   2    Copyright (C) 2003-2023 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                    && !POINTER_TYPE_P (type)
 627                    && TYPE_PRECISION (TREE_TYPE (x))
 628                       >= TYPE_PRECISION (type))
 629             {
 630               /* We know the number of iterations can't be negative.
 631                  So {a, +, a} (x-1) -> "a*x".  */
 632               res = build_int_cst (TREE_TYPE (x), 1);
 633               res = chrec_fold_plus (TREE_TYPE (x), x, res);
 634               res = chrec_convert_rhs (type, res, NULL);
 635               res = chrec_fold_multiply (type, chrecr, res);
 636             }
 637           else
 638             {
 639               res = chrec_convert_rhs (TREE_TYPE (chrecr), x, NULL);
 640               res = chrec_fold_multiply (TREE_TYPE (chrecr), chrecr, res);
 641               res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
 642             }
 643         }
 644       else if (TREE_CODE (x) == INTEGER_CST
 645                && tree_int_cst_sgn (x) == 1)
 646         /* testsuite/.../ssa-chrec-38.c.  */
 647         res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
 648       else
 649         res = chrec_dont_know;
 650       break;
 651
 652     CASE_CONVERT:
 653       res = chrec_convert (TREE_TYPE (chrec),
 654                            chrec_apply (var, TREE_OPERAND (chrec, 0), x),
 655                            NULL);
 656       break;
 657
 658     default:
 659       res = chrec;
 660       break;
 661     }
 662
 663   if (dump_file && (dump_flags & TDF_SCEV))
 664     {
 665       fprintf (dump_file, "  (varying_loop = %d", var);
 666       fprintf (dump_file, ")\n  (chrec = ");
 667       print_generic_expr (dump_file, chrec);
 668       fprintf (dump_file, ")\n  (x = ");
 669       print_generic_expr (dump_file, x);
 670       fprintf (dump_file, ")\n  (res = ");
 671       print_generic_expr (dump_file, res);
 672       fprintf (dump_file, "))\n");
 673     }
 674
 675   return res;
 676 }
 677
 678 /* For a given CHREC and an induction variable map IV_MAP that maps
 679    (loop->num, expr) for every loop number of the current_loops an
 680    expression, calls chrec_apply when the expression is not NULL.  */
 681
 682 tree
 683 chrec_apply_map (tree chrec, vec<tree> iv_map)
 684 {
 685   int i;
 686   tree expr;
 687
 688   FOR_EACH_VEC_ELT (iv_map, i, expr)
 689     if (expr)
 690       chrec = chrec_apply (i, chrec, expr);
 691
 692   return chrec;
 693 }
 694
 695 /* Replaces the initial condition in CHREC with INIT_COND.  */
 696
 697 tree
 698 chrec_replace_initial_condition (tree chrec,
 699                                  tree init_cond)
 700 {
 701   if (automatically_generated_chrec_p (chrec))
 702     return chrec;
 703
 704   gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
 705
 706   switch (TREE_CODE (chrec))
 707     {
 708     case POLYNOMIAL_CHREC:
 709       return build_polynomial_chrec
 710         (CHREC_VARIABLE (chrec),
 711          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 712          CHREC_RIGHT (chrec));
 713
 714     default:
 715       return init_cond;
 716     }
 717 }
 718
 719 /* Returns the initial condition of a given CHREC.  */
 720
 721 tree
 722 initial_condition (tree chrec)
 723 {
 724   if (automatically_generated_chrec_p (chrec))
 725     return chrec;
 726
 727   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 728     return initial_condition (CHREC_LEFT (chrec));
 729   else
 730     return chrec;
 731 }
 732
 733 /* Returns a univariate function that represents the evolution in
 734    LOOP_NUM.  Mask the evolution of any other loop.  */
 735
 736 tree
 737 hide_evolution_in_other_loops_than_loop (tree chrec,
 738                                          unsigned loop_num)
 739 {
 740   class loop *loop = get_loop (cfun, loop_num), *chloop;
 741   if (automatically_generated_chrec_p (chrec))
 742     return chrec;
 743
 744   switch (TREE_CODE (chrec))
 745     {
 746     case POLYNOMIAL_CHREC:
 747       chloop = get_chrec_loop (chrec);
 748
 749       if (chloop == loop)
 750         return build_polynomial_chrec
 751           (loop_num,
 752            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 753                                                     loop_num),
 754            CHREC_RIGHT (chrec));
 755
 756       else if (flow_loop_nested_p (chloop, loop))
 757         /* There is no evolution in this loop.  */
 758         return initial_condition (chrec);
 759
 760       else if (flow_loop_nested_p (loop, chloop))
 761         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 762                                                         loop_num);
 763
 764       else
 765         return chrec_dont_know;
 766
 767     default:
 768       return chrec;
 769     }
 770 }
 771
 772 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 773    true, otherwise returns the initial condition in LOOP_NUM.  */
 774
 775 static tree
 776 chrec_component_in_loop_num (tree chrec,
 777                              unsigned loop_num,
 778                              bool right)
 779 {
 780   tree component;
 781   class loop *loop = get_loop (cfun, loop_num), *chloop;
 782
 783   if (automatically_generated_chrec_p (chrec))
 784     return chrec;
 785
 786   switch (TREE_CODE (chrec))
 787     {
 788     case POLYNOMIAL_CHREC:
 789       chloop = get_chrec_loop (chrec);
 790
 791       if (chloop == loop)
 792         {
 793           if (right)
 794             component = CHREC_RIGHT (chrec);
 795           else
 796             component = CHREC_LEFT (chrec);
 797
 798           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 799               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 800             return component;
 801
 802           else
 803             return build_polynomial_chrec
 804               (loop_num,
 805                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 806                                             loop_num,
 807                                             right),
 808                component);
 809         }
 810
 811       else if (flow_loop_nested_p (chloop, loop))
 812         /* There is no evolution part in this loop.  */
 813         return NULL_TREE;
 814
 815       else
 816         {
 817           gcc_assert (flow_loop_nested_p (loop, chloop));
 818           return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 819                                               loop_num,
 820                                               right);
 821         }
 822
 823      default:
 824       if (right)
 825         return NULL_TREE;
 826       else
 827         return chrec;
 828     }
 829 }
 830
 831 /* Returns the evolution part in LOOP_NUM.  Example: the call
 832    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 833    {1, +, 2}_1  */
 834
 835 tree
 836 evolution_part_in_loop_num (tree chrec,
 837                             unsigned loop_num)
 838 {
 839   return chrec_component_in_loop_num (chrec, loop_num, true);
 840 }
 841
 842 /* Returns the initial condition in LOOP_NUM.  Example: the call
 843    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 844    {0, +, 1}_1  */
 845
 846 tree
 847 initial_condition_in_loop_num (tree chrec,
 848                                unsigned loop_num)
 849 {
 850   return chrec_component_in_loop_num (chrec, loop_num, false);
 851 }
 852
 853 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 854    This function is essentially used for setting the evolution to
 855    chrec_dont_know, for example after having determined that it is
 856    impossible to say how many times a loop will execute.  */
 857
 858 tree
 859 reset_evolution_in_loop (unsigned loop_num,
 860                          tree chrec,
 861                          tree new_evol)
 862 {
 863   class loop *loop = get_loop (cfun, loop_num);
 864
 865   if (POINTER_TYPE_P (chrec_type (chrec)))
 866     gcc_assert (ptrofftype_p (chrec_type (new_evol)));
 867   else
 868     gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
 869
 870   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 871       && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
 872     {
 873       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 874                                            new_evol);
 875       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 876                                             new_evol);
 877       return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
 878     }
 879
 880   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 881          && CHREC_VARIABLE (chrec) == loop_num)
 882     chrec = CHREC_LEFT (chrec);
 883
 884   return build_polynomial_chrec (loop_num, chrec, new_evol);
 885 }
 886
 887 /* Merges two evolution functions that were found by following two
 888    alternate paths of a conditional expression.  */
 889
 890 tree
 891 chrec_merge (tree chrec1,
 892              tree chrec2)
 893 {
 894   if (chrec1 == chrec_dont_know
 895       || chrec2 == chrec_dont_know)
 896     return chrec_dont_know;
 897
 898   if (chrec1 == chrec_known
 899       || chrec2 == chrec_known)
 900     return chrec_known;
 901
 902   if (chrec1 == chrec_not_analyzed_yet)
 903     return chrec2;
 904   if (chrec2 == chrec_not_analyzed_yet)
 905     return chrec1;
 906
 907   if (eq_evolutions_p (chrec1, chrec2))
 908     return chrec1;
 909
 910   return chrec_dont_know;
 911 }
 912
 913 \f
 914
 915 /* Observers.  */
 916
 917 /* Helper function for is_multivariate_chrec.  */
 918
 919 static bool
 920 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
 921 {
 922   if (chrec == NULL_TREE)
 923     return false;
 924
 925   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 926     {
 927       if (CHREC_VARIABLE (chrec) != rec_var)
 928         return true;
 929       else
 930         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 931                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 932     }
 933   else
 934     return false;
 935 }
 936
 937 /* Determine whether the given chrec is multivariate or not.  */
 938
 939 bool
 940 is_multivariate_chrec (const_tree chrec)
 941 {
 942   if (chrec == NULL_TREE)
 943     return false;
 944
 945   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 946     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 947                                        CHREC_VARIABLE (chrec))
 948             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 949                                           CHREC_VARIABLE (chrec)));
 950   else
 951     return false;
 952 }
 953
 954 /* Determines whether the chrec contains symbolic names or not.  If LOOP isn't
 955    NULL, we also consider chrec wrto outer loops of LOOP as symbol.  */
 956
 957 static bool
 958 chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
 959                         class loop *loop)
 960 {
 961   int i, n;
 962
 963   if (chrec == NULL_TREE)
 964     return false;
 965
 966   if (TREE_CODE (chrec) == SSA_NAME
 967       || VAR_P (chrec)
 968       || TREE_CODE (chrec) == POLY_INT_CST
 969       || TREE_CODE (chrec) == PARM_DECL
 970       || TREE_CODE (chrec) == FUNCTION_DECL
 971       || TREE_CODE (chrec) == LABEL_DECL
 972       || TREE_CODE (chrec) == RESULT_DECL
 973       || TREE_CODE (chrec) == FIELD_DECL)
 974     return true;
 975
 976   if (loop != NULL
 977       && TREE_CODE (chrec) == POLYNOMIAL_CHREC
 978       && flow_loop_nested_p (get_chrec_loop (chrec), loop))
 979     return true;
 980
 981   if (visited.add (chrec))
 982     return false;
 983
 984   n = TREE_OPERAND_LENGTH (chrec);
 985   for (i = 0; i < n; i++)
 986     if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
 987       return true;
 988   return false;
 989 }
 990
 991 /* Return true if CHREC contains any symbols.  If LOOP is not NULL, check if
 992    CHREC contains any chrec which is invariant wrto the loop (nest), in other
 993    words, chrec defined by outer loops of loop, so from LOOP's point of view,
 994    the chrec is considered as a SYMBOL.  */
 995
 996 bool
 997 chrec_contains_symbols (const_tree chrec, class loop* loop)
 998 {
 999   hash_set<const_tree> visited;
1000   return chrec_contains_symbols (chrec, visited, loop);
1001 }
1002
1003 /* Return true when CHREC contains symbolic names defined in
1004    LOOP_NB.  */
1005
1006 static bool
1007 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1008                                         hash_set<const_tree> &visited)
1009 {
1010   int i, n;
1011
1012   if (chrec == NULL_TREE)
1013     return false;
1014
1015   if (is_gimple_min_invariant (chrec))
1016     return false;
1017
1018   if (TREE_CODE (chrec) == SSA_NAME)
1019     {
1020       gimple *def;
1021       loop_p def_loop, loop;
1022
1023       if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1024         return false;
1025
1026       def = SSA_NAME_DEF_STMT (chrec);
1027       def_loop = loop_containing_stmt (def);
1028       loop = get_loop (cfun, loop_nb);
1029
1030       if (def_loop == NULL)
1031         return false;
1032
1033       if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1034         return true;
1035
1036       return false;
1037     }
1038
1039   if (visited.add (chrec))
1040     return false;
1041
1042   n = TREE_OPERAND_LENGTH (chrec);
1043   for (i = 0; i < n; i++)
1044     if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1045                                                 loop_nb, visited))
1046       return true;
1047   return false;
1048 }
1049
1050 /* Return true when CHREC contains symbolic names defined in
1051    LOOP_NB.  */
1052
1053 bool
1054 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1055 {
1056   hash_set<const_tree> visited;
1057   return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1058 }
1059
1060 /* Determines whether the chrec contains undetermined coefficients.  */
1061
1062 static bool
1063 chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1064 {
1065   int i, n;
1066
1067   if (chrec == chrec_dont_know)
1068     return true;
1069
1070   if (chrec == NULL_TREE)
1071     return false;
1072
1073   if (visited.add (chrec))
1074     return false;
1075
1076   n = TREE_OPERAND_LENGTH (chrec);
1077   for (i = 0; i < n; i++)
1078     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1079       return true;
1080   return false;
1081 }
1082
1083 bool
1084 chrec_contains_undetermined (const_tree chrec)
1085 {
1086   hash_set<const_tree> visited;
1087   return chrec_contains_undetermined (chrec, visited);
1088 }
1089
1090 /* Determines whether the tree EXPR contains chrecs, and increment
1091    SIZE if it is not a NULL pointer by an estimation of the depth of
1092    the tree.  */
1093
1094 static bool
1095 tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1096 {
1097   int i, n;
1098
1099   if (expr == NULL_TREE)
1100     return false;
1101
1102   if (size)
1103     (*size)++;
1104
1105   if (tree_is_chrec (expr))
1106     return true;
1107
1108   if (visited.add (expr))
1109     return false;
1110
1111   n = TREE_OPERAND_LENGTH (expr);
1112   for (i = 0; i < n; i++)
1113     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1114       return true;
1115   return false;
1116 }
1117
1118 bool
1119 tree_contains_chrecs (const_tree expr, int *size)
1120 {
1121   hash_set<const_tree> visited;
1122   return tree_contains_chrecs (expr, size, visited);
1123 }
1124
1125
1126 /* Recursive helper function.  */
1127
1128 static bool
1129 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1130 {
1131   if (evolution_function_is_constant_p (chrec))
1132     return true;
1133
1134   if (TREE_CODE (chrec) == SSA_NAME
1135       && (loopnum == 0
1136           || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1137     return true;
1138
1139   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1140     {
1141       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1142           || flow_loop_nested_p (get_loop (cfun, loopnum),
1143                                  get_chrec_loop (chrec))
1144           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1145                                                      loopnum)
1146           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1147                                                      loopnum))
1148         return false;
1149       return true;
1150     }
1151
1152   switch (TREE_OPERAND_LENGTH (chrec))
1153     {
1154     case 2:
1155       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1156                                                   loopnum))
1157         return false;
1158       /* FALLTHRU */
1159
1160     case 1:
1161       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1162                                                   loopnum))
1163         return false;
1164       return true;
1165
1166     default:
1167       return false;
1168     }
1169 }
1170
1171 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1172
1173 bool
1174 evolution_function_is_invariant_p (tree chrec, int loopnum)
1175 {
1176   return evolution_function_is_invariant_rec_p (chrec, loopnum);
1177 }
1178
1179 /* Determine whether the given tree is an affine multivariate
1180    evolution.  */
1181
1182 bool
1183 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1184 {
1185   if (chrec == NULL_TREE)
1186     return false;
1187
1188   switch (TREE_CODE (chrec))
1189     {
1190     case POLYNOMIAL_CHREC:
1191       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1192         {
1193           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1194             return true;
1195           else
1196             {
1197               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1198                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1199                      != CHREC_VARIABLE (chrec)
1200                   && evolution_function_is_affine_multivariate_p
1201                   (CHREC_RIGHT (chrec), loopnum))
1202                 return true;
1203               else
1204                 return false;
1205             }
1206         }
1207       else
1208         {
1209           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1210               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1211               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1212               && evolution_function_is_affine_multivariate_p
1213               (CHREC_LEFT (chrec), loopnum))
1214             return true;
1215           else
1216             return false;
1217         }
1218
1219     default:
1220       return false;
1221     }
1222 }
1223
1224 /* Determine whether the given tree is a function in zero or one
1225    variables with respect to loop specified by LOOPNUM.  Note only positive
1226    LOOPNUM stands for a real loop.  */
1227
1228 bool
1229 evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1230 {
1231   if (chrec == NULL_TREE)
1232     return true;
1233
1234   tree sub_chrec;
1235   switch (TREE_CODE (chrec))
1236     {
1237     case POLYNOMIAL_CHREC:
1238       switch (TREE_CODE (CHREC_LEFT (chrec)))
1239         {
1240         case POLYNOMIAL_CHREC:
1241           sub_chrec = CHREC_LEFT (chrec);
1242           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1243               && (loopnum <= 0
1244                   || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1245                   || flow_loop_nested_p (get_loop (cfun, loopnum),
1246                                          get_chrec_loop (sub_chrec))))
1247             return false;
1248           if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1249             return false;
1250           break;
1251
1252         default:
1253           if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1254             return false;
1255           break;
1256         }
1257
1258       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1259         {
1260         case POLYNOMIAL_CHREC:
1261           sub_chrec = CHREC_RIGHT (chrec);
1262           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1263               && (loopnum <= 0
1264                   || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1265                   || flow_loop_nested_p (get_loop (cfun, loopnum),
1266                                          get_chrec_loop (sub_chrec))))
1267             return false;
1268           if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1269             return false;
1270           break;
1271
1272         default:
1273           if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1274             return false;
1275           break;
1276         }
1277       return true;
1278
1279     default:
1280       return true;
1281     }
1282 }
1283
1284 /* Returns the number of variables of CHREC.  Example: the call
1285    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1286
1287 unsigned
1288 nb_vars_in_chrec (tree chrec)
1289 {
1290   if (chrec == NULL_TREE)
1291     return 0;
1292
1293   switch (TREE_CODE (chrec))
1294     {
1295     case POLYNOMIAL_CHREC:
1296       return 1 + nb_vars_in_chrec
1297         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1298
1299     default:
1300       return 0;
1301     }
1302 }
1303
1304 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1305    the scev corresponds to.  AT_STMT is the statement at that the scev is
1306    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume
1307    that the rules for overflow of the given language apply (e.g., that signed
1308    arithmetics in C does not overflow) -- i.e., to use them to avoid
1309    unnecessary tests, but also to enforce that the result follows them.
1310    FROM is the source variable converted if it's not NULL.  Returns true if
1311    the conversion succeeded, false otherwise.  */
1312
1313 bool
1314 convert_affine_scev (class loop *loop, tree type,
1315                      tree *base, tree *step, gimple *at_stmt,
1316                      bool use_overflow_semantics, tree from)
1317 {
1318   tree ct = TREE_TYPE (*step);
1319   bool enforce_overflow_semantics;
1320   bool must_check_src_overflow, must_check_rslt_overflow;
1321   tree new_base, new_step;
1322   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1323
1324   /* In general,
1325      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1326      but we must check some assumptions.
1327
1328      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1329         of CT is smaller than the precision of TYPE.  For example, when we
1330         cast unsigned char [254, +, 1] to unsigned, the values on left side
1331         are 254, 255, 0, 1, ..., but those on the right side are
1332         254, 255, 256, 257, ...
1333      2) In case that we must also preserve the fact that signed ivs do not
1334         overflow, we must additionally check that the new iv does not wrap.
1335         For example, unsigned char [125, +, 1] casted to signed char could
1336         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1337         which would confuse optimizers that assume that this does not
1338         happen.  */
1339   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1340
1341   enforce_overflow_semantics = (use_overflow_semantics
1342                                 && nowrap_type_p (type));
1343   if (enforce_overflow_semantics)
1344     {
1345       /* We can avoid checking whether the result overflows in the following
1346          cases:
1347
1348          -- must_check_src_overflow is true, and the range of TYPE is superset
1349             of the range of CT -- i.e., in all cases except if CT signed and
1350             TYPE unsigned.
1351          -- both CT and TYPE have the same precision and signedness, and we
1352             verify instead that the source does not overflow (this may be
1353             easier than verifying it for the result, as we may use the
1354             information about the semantics of overflow in CT).  */
1355       if (must_check_src_overflow)
1356         {
1357           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1358             must_check_rslt_overflow = true;
1359           else
1360             must_check_rslt_overflow = false;
1361         }
1362       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1363                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1364         {
1365           must_check_rslt_overflow = false;
1366           must_check_src_overflow = true;
1367         }
1368       else
1369         must_check_rslt_overflow = true;
1370     }
1371   else
1372     must_check_rslt_overflow = false;
1373
1374   if (must_check_src_overflow
1375       && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1376                                 use_overflow_semantics))
1377     return false;
1378
1379   new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1380   /* The step must be sign extended, regardless of the signedness
1381      of CT and TYPE.  This only needs to be handled specially when
1382      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1383      (with values 100, 99, 98, ...) from becoming signed or unsigned
1384      [100, +, 255] with values 100, 355, ...; the sign-extension is
1385      performed by default when CT is signed.  */
1386   new_step = *step;
1387   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1388     {
1389       tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1390       new_step = chrec_convert (signed_ct, new_step, at_stmt,
1391                                 use_overflow_semantics);
1392     }
1393   new_step = chrec_convert (step_type, new_step, at_stmt,
1394                             use_overflow_semantics);
1395
1396   if (automatically_generated_chrec_p (new_base)
1397       || automatically_generated_chrec_p (new_step))
1398     return false;
1399
1400   if (must_check_rslt_overflow
1401       /* Note that in this case we cannot use the fact that signed variables
1402          do not overflow, as this is what we are verifying for the new iv.  */
1403       && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1404                                 at_stmt, loop, false))
1405     return false;
1406
1407   *base = new_base;
1408   *step = new_step;
1409   return true;
1410 }
1411 \f
1412
1413 /* Convert CHREC for the right hand side of a CHREC.
1414    The increment for a pointer type is always sizetype.  */
1415
1416 tree
1417 chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1418 {
1419   if (POINTER_TYPE_P (type))
1420     type = sizetype;
1421
1422   return chrec_convert (type, chrec, at_stmt);
1423 }
1424
1425 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1426    which the CHREC is built, it sets AT_STMT to the statement that
1427    contains the definition of the analyzed variable, otherwise the
1428    conversion is less accurate: the information is used for
1429    determining a more accurate estimation of the number of iterations.
1430    By default AT_STMT could be safely set to NULL_TREE.
1431
1432    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1433    the rules for overflow of the given language apply (e.g., that signed
1434    arithmetics in C does not overflow) -- i.e., to use them to avoid
1435    unnecessary tests, but also to enforce that the result follows them.
1436
1437    FROM is the source variable converted if it's not NULL.  */
1438
1439 static tree
1440 chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1441                  bool use_overflow_semantics, tree from)
1442 {
1443   tree ct, res;
1444   tree base, step;
1445   class loop *loop;
1446
1447   if (automatically_generated_chrec_p (chrec))
1448     return chrec;
1449
1450   ct = chrec_type (chrec);
1451   if (useless_type_conversion_p (type, ct))
1452     return chrec;
1453
1454   if (!evolution_function_is_affine_p (chrec))
1455     goto keep_cast;
1456
1457   loop = get_chrec_loop (chrec);
1458   base = CHREC_LEFT (chrec);
1459   step = CHREC_RIGHT (chrec);
1460
1461   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1462                            use_overflow_semantics, from))
1463     return build_polynomial_chrec (loop->num, base, step);
1464
1465   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1466 keep_cast:
1467   /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1468      may be more expensive.  We do want to perform this optimization here
1469      though for canonicalization reasons.  */
1470   if (use_overflow_semantics
1471       && (TREE_CODE (chrec) == PLUS_EXPR
1472           || TREE_CODE (chrec) == MINUS_EXPR)
1473       && TREE_CODE (type) == INTEGER_TYPE
1474       && TREE_CODE (ct) == INTEGER_TYPE
1475       && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1476       && TYPE_OVERFLOW_UNDEFINED (ct))
1477     res = fold_build2 (TREE_CODE (chrec), type,
1478                        fold_convert (type, TREE_OPERAND (chrec, 0)),
1479                        fold_convert (type, TREE_OPERAND (chrec, 1)));
1480   /* Similar perform the trick that (signed char)((int)x + 2) can be
1481      narrowed to (signed char)((unsigned char)x + 2).  */
1482   else if (use_overflow_semantics
1483            && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1484            && TREE_CODE (ct) == INTEGER_TYPE
1485            && TREE_CODE (type) == INTEGER_TYPE
1486            && TYPE_OVERFLOW_UNDEFINED (type)
1487            && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1488     {
1489       tree utype = unsigned_type_for (type);
1490       res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1491                                     fold_convert (utype,
1492                                                   CHREC_LEFT (chrec)),
1493                                     fold_convert (utype,
1494                                                   CHREC_RIGHT (chrec)));
1495       res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1496     }
1497   else
1498     res = fold_convert (type, chrec);
1499
1500   /* Don't propagate overflows.  */
1501   if (CONSTANT_CLASS_P (res))
1502     TREE_OVERFLOW (res) = 0;
1503
1504   /* But reject constants that don't fit in their type after conversion.
1505      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1506      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1507      and can cause problems later when computing niters of loops.  Note
1508      that we don't do the check before converting because we don't want
1509      to reject conversions of negative chrecs to unsigned types.  */
1510   if (TREE_CODE (res) == INTEGER_CST
1511       && TREE_CODE (type) == INTEGER_TYPE
1512       && !int_fits_type_p (res, type))
1513     res = chrec_dont_know;
1514
1515   return res;
1516 }
1517
1518 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1519    which the CHREC is built, it sets AT_STMT to the statement that
1520    contains the definition of the analyzed variable, otherwise the
1521    conversion is less accurate: the information is used for
1522    determining a more accurate estimation of the number of iterations.
1523    By default AT_STMT could be safely set to NULL_TREE.
1524
1525    The following rule is always true: TREE_TYPE (chrec) ==
1526    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1527    An example of what could happen when adding two chrecs and the type
1528    of the CHREC_RIGHT is different than CHREC_LEFT is:
1529
1530    {(uint) 0, +, (uchar) 10} +
1531    {(uint) 0, +, (uchar) 250}
1532
1533    that would produce a wrong result if CHREC_RIGHT is not (uint):
1534
1535    {(uint) 0, +, (uchar) 4}
1536
1537    instead of
1538
1539    {(uint) 0, +, (uint) 260}
1540
1541    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1542    the rules for overflow of the given language apply (e.g., that signed
1543    arithmetics in C does not overflow) -- i.e., to use them to avoid
1544    unnecessary tests, but also to enforce that the result follows them.
1545
1546    FROM is the source variable converted if it's not NULL.  */
1547
1548 tree
1549 chrec_convert (tree type, tree chrec, gimple *at_stmt,
1550                bool use_overflow_semantics, tree from)
1551 {
1552   return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1553 }
1554
1555 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1556    chrec if something else than what chrec_convert would do happens, NULL_TREE
1557    otherwise.  This function set TRUE to variable pointed by FOLD_CONVERSIONS
1558    if the result chrec may overflow.  */
1559
1560 tree
1561 chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1562 {
1563   tree inner_type, left, right, lc, rc, rtype;
1564
1565   gcc_assert (fold_conversions != NULL);
1566
1567   if (automatically_generated_chrec_p (chrec)
1568       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1569     return NULL_TREE;
1570
1571   inner_type = TREE_TYPE (chrec);
1572   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1573     return NULL_TREE;
1574
1575   if (useless_type_conversion_p (type, inner_type))
1576     return NULL_TREE;
1577
1578   if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1579     {
1580       tree base, step;
1581       class loop *loop;
1582
1583       loop = get_chrec_loop (chrec);
1584       base = CHREC_LEFT (chrec);
1585       step = CHREC_RIGHT (chrec);
1586       if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1587         return build_polynomial_chrec (loop->num, base, step);
1588     }
1589   rtype = POINTER_TYPE_P (type) ? sizetype : type;
1590
1591   left = CHREC_LEFT (chrec);
1592   right = CHREC_RIGHT (chrec);
1593   lc = chrec_convert_aggressive (type, left, fold_conversions);
1594   if (!lc)
1595     lc = chrec_convert (type, left, NULL);
1596   rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1597   if (!rc)
1598     rc = chrec_convert (rtype, right, NULL);
1599
1600   *fold_conversions = true;
1601
1602   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1603 }
1604
1605 /* Returns true when CHREC0 == CHREC1.  */
1606
1607 bool
1608 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1609 {
1610   if (chrec0 == NULL_TREE
1611       || chrec1 == NULL_TREE
1612       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1613     return false;
1614
1615   if (chrec0 == chrec1)
1616     return true;
1617
1618   if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1619     return false;
1620
1621   switch (TREE_CODE (chrec0))
1622     {
1623     case POLYNOMIAL_CHREC:
1624       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1625               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1626               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1627
1628     case PLUS_EXPR:
1629     case MULT_EXPR:
1630     case MINUS_EXPR:
1631     case POINTER_PLUS_EXPR:
1632       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1633                               TREE_OPERAND (chrec1, 0))
1634           && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1635                               TREE_OPERAND (chrec1, 1));
1636
1637     CASE_CONVERT:
1638       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1639                               TREE_OPERAND (chrec1, 0));
1640
1641     default:
1642       return operand_equal_p (chrec0, chrec1, 0);
1643     }
1644 }
1645
1646 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1647    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1648    which of these cases happens.  */
1649
1650 enum ev_direction
1651 scev_direction (const_tree chrec)
1652 {
1653   const_tree step;
1654
1655   if (!evolution_function_is_affine_p (chrec))
1656     return EV_DIR_UNKNOWN;
1657
1658   step = CHREC_RIGHT (chrec);
1659   if (TREE_CODE (step) != INTEGER_CST)
1660     return EV_DIR_UNKNOWN;
1661
1662   if (tree_int_cst_sign_bit (step))
1663     return EV_DIR_DECREASES;
1664   else
1665     return EV_DIR_GROWS;
1666 }
1667
1668 /* Iterates over all the components of SCEV, and calls CBCK.  */
1669
1670 void
1671 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1672 {
1673   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1674     {
1675     case 3:
1676       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1677       /* FALLTHRU */
1678
1679     case 2:
1680       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1681       /* FALLTHRU */
1682
1683     case 1:
1684       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1685       /* FALLTHRU */
1686
1687     default:
1688       cbck (scev, data);
1689       break;
1690     }
1691 }
1692
1693 /* Returns true when the operation can be part of a linear
1694    expression.  */
1695
1696 static inline bool
1697 operator_is_linear (tree scev)
1698 {
1699   switch (TREE_CODE (scev))
1700     {
1701     case INTEGER_CST:
1702     case POLYNOMIAL_CHREC:
1703     case PLUS_EXPR:
1704     case POINTER_PLUS_EXPR:
1705     case MULT_EXPR:
1706     case MINUS_EXPR:
1707     case NEGATE_EXPR:
1708     case SSA_NAME:
1709     case NON_LVALUE_EXPR:
1710     case BIT_NOT_EXPR:
1711     CASE_CONVERT:
1712       return true;
1713
1714     default:
1715       return false;
1716     }
1717 }
1718
1719 /* Return true when SCEV is a linear expression.  Linear expressions
1720    can contain additions, substractions and multiplications.
1721    Multiplications are restricted to constant scaling: "cst * x".  */
1722
1723 bool
1724 scev_is_linear_expression (tree scev)
1725 {
1726   if (evolution_function_is_constant_p (scev))
1727     return true;
1728
1729   if (scev == NULL
1730       || !operator_is_linear (scev))
1731     return false;
1732
1733   if (TREE_CODE (scev) == MULT_EXPR)
1734     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1735              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1736
1737   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1738       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1739     return false;
1740
1741   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1742     {
1743     case 3:
1744       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1745         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1746         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1747
1748     case 2:
1749       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1750         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1751
1752     case 1:
1753       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1754
1755     case 0:
1756       return true;
1757
1758     default:
1759       return false;
1760     }
1761 }
1762
1763 /* Determines whether the expression CHREC contains only interger consts
1764    in the right parts.  */
1765
1766 bool
1767 evolution_function_right_is_integer_cst (const_tree chrec)
1768 {
1769   if (chrec == NULL_TREE)
1770     return false;
1771
1772   switch (TREE_CODE (chrec))
1773     {
1774     case INTEGER_CST:
1775       return true;
1776
1777     case POLYNOMIAL_CHREC:
1778       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1779         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1780             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1781
1782     CASE_CONVERT:
1783       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1784
1785     default:
1786       return false;
1787     }
1788 }