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