gcc/tree-chrec.c

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