gcc/tree-chrec.c

   1 /* Chains of recurrences.
   2    Copyright (C) 2003-2021 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   return false;
1153 }
1154
1155 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1156
1157 bool
1158 evolution_function_is_invariant_p (tree chrec, int loopnum)
1159 {
1160   return evolution_function_is_invariant_rec_p (chrec, loopnum);
1161 }
1162
1163 /* Determine whether the given tree is an affine multivariate
1164    evolution.  */
1165
1166 bool
1167 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1168 {
1169   if (chrec == NULL_TREE)
1170     return false;
1171
1172   switch (TREE_CODE (chrec))
1173     {
1174     case POLYNOMIAL_CHREC:
1175       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1176         {
1177           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1178             return true;
1179           else
1180             {
1181               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1182                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1183                      != CHREC_VARIABLE (chrec)
1184                   && evolution_function_is_affine_multivariate_p
1185                   (CHREC_RIGHT (chrec), loopnum))
1186                 return true;
1187               else
1188                 return false;
1189             }
1190         }
1191       else
1192         {
1193           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1194               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1195               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1196               && evolution_function_is_affine_multivariate_p
1197               (CHREC_LEFT (chrec), loopnum))
1198             return true;
1199           else
1200             return false;
1201         }
1202
1203     default:
1204       return false;
1205     }
1206 }
1207
1208 /* Determine whether the given tree is a function in zero or one
1209    variables with respect to loop specified by LOOPNUM.  Note only positive
1210    LOOPNUM stands for a real loop.  */
1211
1212 bool
1213 evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1214 {
1215   if (chrec == NULL_TREE)
1216     return true;
1217
1218   tree sub_chrec;
1219   switch (TREE_CODE (chrec))
1220     {
1221     case POLYNOMIAL_CHREC:
1222       switch (TREE_CODE (CHREC_LEFT (chrec)))
1223         {
1224         case POLYNOMIAL_CHREC:
1225           sub_chrec = CHREC_LEFT (chrec);
1226           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1227               && (loopnum <= 0
1228                   || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1229                   || flow_loop_nested_p (get_loop (cfun, loopnum),
1230                                          get_chrec_loop (sub_chrec))))
1231             return false;
1232           if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1233             return false;
1234           break;
1235
1236         default:
1237           if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1238             return false;
1239           break;
1240         }
1241
1242       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1243         {
1244         case POLYNOMIAL_CHREC:
1245           sub_chrec = CHREC_RIGHT (chrec);
1246           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1247               && (loopnum <= 0
1248                   || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1249                   || flow_loop_nested_p (get_loop (cfun, loopnum),
1250                                          get_chrec_loop (sub_chrec))))
1251             return false;
1252           if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1253             return false;
1254           break;
1255
1256         default:
1257           if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1258             return false;
1259           break;
1260         }
1261       return true;
1262
1263     default:
1264       return true;
1265     }
1266 }
1267
1268 /* Returns the number of variables of CHREC.  Example: the call
1269    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1270
1271 unsigned
1272 nb_vars_in_chrec (tree chrec)
1273 {
1274   if (chrec == NULL_TREE)
1275     return 0;
1276
1277   switch (TREE_CODE (chrec))
1278     {
1279     case POLYNOMIAL_CHREC:
1280       return 1 + nb_vars_in_chrec
1281         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1282
1283     default:
1284       return 0;
1285     }
1286 }
1287
1288 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1289    the scev corresponds to.  AT_STMT is the statement at that the scev is
1290    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume
1291    that the rules for overflow of the given language apply (e.g., that signed
1292    arithmetics in C does not overflow) -- i.e., to use them to avoid
1293    unnecessary tests, but also to enforce that the result follows them.
1294    FROM is the source variable converted if it's not NULL.  Returns true if
1295    the conversion succeeded, false otherwise.  */
1296
1297 bool
1298 convert_affine_scev (class loop *loop, tree type,
1299                      tree *base, tree *step, gimple *at_stmt,
1300                      bool use_overflow_semantics, tree from)
1301 {
1302   tree ct = TREE_TYPE (*step);
1303   bool enforce_overflow_semantics;
1304   bool must_check_src_overflow, must_check_rslt_overflow;
1305   tree new_base, new_step;
1306   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1307
1308   /* In general,
1309      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1310      but we must check some assumptions.
1311
1312      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1313         of CT is smaller than the precision of TYPE.  For example, when we
1314         cast unsigned char [254, +, 1] to unsigned, the values on left side
1315         are 254, 255, 0, 1, ..., but those on the right side are
1316         254, 255, 256, 257, ...
1317      2) In case that we must also preserve the fact that signed ivs do not
1318         overflow, we must additionally check that the new iv does not wrap.
1319         For example, unsigned char [125, +, 1] casted to signed char could
1320         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1321         which would confuse optimizers that assume that this does not
1322         happen.  */
1323   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1324
1325   enforce_overflow_semantics = (use_overflow_semantics
1326                                 && nowrap_type_p (type));
1327   if (enforce_overflow_semantics)
1328     {
1329       /* We can avoid checking whether the result overflows in the following
1330          cases:
1331
1332          -- must_check_src_overflow is true, and the range of TYPE is superset
1333             of the range of CT -- i.e., in all cases except if CT signed and
1334             TYPE unsigned.
1335          -- both CT and TYPE have the same precision and signedness, and we
1336             verify instead that the source does not overflow (this may be
1337             easier than verifying it for the result, as we may use the
1338             information about the semantics of overflow in CT).  */
1339       if (must_check_src_overflow)
1340         {
1341           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1342             must_check_rslt_overflow = true;
1343           else
1344             must_check_rslt_overflow = false;
1345         }
1346       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1347                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1348         {
1349           must_check_rslt_overflow = false;
1350           must_check_src_overflow = true;
1351         }
1352       else
1353         must_check_rslt_overflow = true;
1354     }
1355   else
1356     must_check_rslt_overflow = false;
1357
1358   if (must_check_src_overflow
1359       && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1360                                 use_overflow_semantics))
1361     return false;
1362
1363   new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1364   /* The step must be sign extended, regardless of the signedness
1365      of CT and TYPE.  This only needs to be handled specially when
1366      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1367      (with values 100, 99, 98, ...) from becoming signed or unsigned
1368      [100, +, 255] with values 100, 355, ...; the sign-extension is
1369      performed by default when CT is signed.  */
1370   new_step = *step;
1371   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1372     {
1373       tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1374       new_step = chrec_convert (signed_ct, new_step, at_stmt,
1375                                 use_overflow_semantics);
1376     }
1377   new_step = chrec_convert (step_type, new_step, at_stmt,
1378                             use_overflow_semantics);
1379
1380   if (automatically_generated_chrec_p (new_base)
1381       || automatically_generated_chrec_p (new_step))
1382     return false;
1383
1384   if (must_check_rslt_overflow
1385       /* Note that in this case we cannot use the fact that signed variables
1386          do not overflow, as this is what we are verifying for the new iv.  */
1387       && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1388                                 at_stmt, loop, false))
1389     return false;
1390
1391   *base = new_base;
1392   *step = new_step;
1393   return true;
1394 }
1395 \f
1396
1397 /* Convert CHREC for the right hand side of a CHREC.
1398    The increment for a pointer type is always sizetype.  */
1399
1400 tree
1401 chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1402 {
1403   if (POINTER_TYPE_P (type))
1404     type = sizetype;
1405
1406   return chrec_convert (type, chrec, at_stmt);
1407 }
1408
1409 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1410    which the CHREC is built, it sets AT_STMT to the statement that
1411    contains the definition of the analyzed variable, otherwise the
1412    conversion is less accurate: the information is used for
1413    determining a more accurate estimation of the number of iterations.
1414    By default AT_STMT could be safely set to NULL_TREE.
1415
1416    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1417    the rules for overflow of the given language apply (e.g., that signed
1418    arithmetics in C does not overflow) -- i.e., to use them to avoid
1419    unnecessary tests, but also to enforce that the result follows them.
1420
1421    FROM is the source variable converted if it's not NULL.  */
1422
1423 static tree
1424 chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1425                  bool use_overflow_semantics, tree from)
1426 {
1427   tree ct, res;
1428   tree base, step;
1429   class loop *loop;
1430
1431   if (automatically_generated_chrec_p (chrec))
1432     return chrec;
1433
1434   ct = chrec_type (chrec);
1435   if (useless_type_conversion_p (type, ct))
1436     return chrec;
1437
1438   if (!evolution_function_is_affine_p (chrec))
1439     goto keep_cast;
1440
1441   loop = get_chrec_loop (chrec);
1442   base = CHREC_LEFT (chrec);
1443   step = CHREC_RIGHT (chrec);
1444
1445   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1446                            use_overflow_semantics, from))
1447     return build_polynomial_chrec (loop->num, base, step);
1448
1449   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1450 keep_cast:
1451   /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1452      may be more expensive.  We do want to perform this optimization here
1453      though for canonicalization reasons.  */
1454   if (use_overflow_semantics
1455       && (TREE_CODE (chrec) == PLUS_EXPR
1456           || TREE_CODE (chrec) == MINUS_EXPR)
1457       && TREE_CODE (type) == INTEGER_TYPE
1458       && TREE_CODE (ct) == INTEGER_TYPE
1459       && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1460       && TYPE_OVERFLOW_UNDEFINED (ct))
1461     res = fold_build2 (TREE_CODE (chrec), type,
1462                        fold_convert (type, TREE_OPERAND (chrec, 0)),
1463                        fold_convert (type, TREE_OPERAND (chrec, 1)));
1464   /* Similar perform the trick that (signed char)((int)x + 2) can be
1465      narrowed to (signed char)((unsigned char)x + 2).  */
1466   else if (use_overflow_semantics
1467            && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1468            && TREE_CODE (ct) == INTEGER_TYPE
1469            && TREE_CODE (type) == INTEGER_TYPE
1470            && TYPE_OVERFLOW_UNDEFINED (type)
1471            && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1472     {
1473       tree utype = unsigned_type_for (type);
1474       res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1475                                     fold_convert (utype,
1476                                                   CHREC_LEFT (chrec)),
1477                                     fold_convert (utype,
1478                                                   CHREC_RIGHT (chrec)));
1479       res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1480     }
1481   else
1482     res = fold_convert (type, chrec);
1483
1484   /* Don't propagate overflows.  */
1485   if (CONSTANT_CLASS_P (res))
1486     TREE_OVERFLOW (res) = 0;
1487
1488   /* But reject constants that don't fit in their type after conversion.
1489      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1490      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1491      and can cause problems later when computing niters of loops.  Note
1492      that we don't do the check before converting because we don't want
1493      to reject conversions of negative chrecs to unsigned types.  */
1494   if (TREE_CODE (res) == INTEGER_CST
1495       && TREE_CODE (type) == INTEGER_TYPE
1496       && !int_fits_type_p (res, type))
1497     res = chrec_dont_know;
1498
1499   return res;
1500 }
1501
1502 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1503    which the CHREC is built, it sets AT_STMT to the statement that
1504    contains the definition of the analyzed variable, otherwise the
1505    conversion is less accurate: the information is used for
1506    determining a more accurate estimation of the number of iterations.
1507    By default AT_STMT could be safely set to NULL_TREE.
1508
1509    The following rule is always true: TREE_TYPE (chrec) ==
1510    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1511    An example of what could happen when adding two chrecs and the type
1512    of the CHREC_RIGHT is different than CHREC_LEFT is:
1513
1514    {(uint) 0, +, (uchar) 10} +
1515    {(uint) 0, +, (uchar) 250}
1516
1517    that would produce a wrong result if CHREC_RIGHT is not (uint):
1518
1519    {(uint) 0, +, (uchar) 4}
1520
1521    instead of
1522
1523    {(uint) 0, +, (uint) 260}
1524
1525    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1526    the rules for overflow of the given language apply (e.g., that signed
1527    arithmetics in C does not overflow) -- i.e., to use them to avoid
1528    unnecessary tests, but also to enforce that the result follows them.
1529
1530    FROM is the source variable converted if it's not NULL.  */
1531
1532 tree
1533 chrec_convert (tree type, tree chrec, gimple *at_stmt,
1534                bool use_overflow_semantics, tree from)
1535 {
1536   return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1537 }
1538
1539 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1540    chrec if something else than what chrec_convert would do happens, NULL_TREE
1541    otherwise.  This function set TRUE to variable pointed by FOLD_CONVERSIONS
1542    if the result chrec may overflow.  */
1543
1544 tree
1545 chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1546 {
1547   tree inner_type, left, right, lc, rc, rtype;
1548
1549   gcc_assert (fold_conversions != NULL);
1550
1551   if (automatically_generated_chrec_p (chrec)
1552       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1553     return NULL_TREE;
1554
1555   inner_type = TREE_TYPE (chrec);
1556   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1557     return NULL_TREE;
1558
1559   if (useless_type_conversion_p (type, inner_type))
1560     return NULL_TREE;
1561
1562   if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1563     {
1564       tree base, step;
1565       class loop *loop;
1566
1567       loop = get_chrec_loop (chrec);
1568       base = CHREC_LEFT (chrec);
1569       step = CHREC_RIGHT (chrec);
1570       if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1571         return build_polynomial_chrec (loop->num, base, step);
1572     }
1573   rtype = POINTER_TYPE_P (type) ? sizetype : type;
1574
1575   left = CHREC_LEFT (chrec);
1576   right = CHREC_RIGHT (chrec);
1577   lc = chrec_convert_aggressive (type, left, fold_conversions);
1578   if (!lc)
1579     lc = chrec_convert (type, left, NULL);
1580   rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1581   if (!rc)
1582     rc = chrec_convert (rtype, right, NULL);
1583
1584   *fold_conversions = true;
1585
1586   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1587 }
1588
1589 /* Returns true when CHREC0 == CHREC1.  */
1590
1591 bool
1592 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1593 {
1594   if (chrec0 == NULL_TREE
1595       || chrec1 == NULL_TREE
1596       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1597     return false;
1598
1599   if (chrec0 == chrec1)
1600     return true;
1601
1602   if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1603     return false;
1604
1605   switch (TREE_CODE (chrec0))
1606     {
1607     case POLYNOMIAL_CHREC:
1608       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1609               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1610               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1611
1612     case PLUS_EXPR:
1613     case MULT_EXPR:
1614     case MINUS_EXPR:
1615     case POINTER_PLUS_EXPR:
1616       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1617                               TREE_OPERAND (chrec1, 0))
1618           && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1619                               TREE_OPERAND (chrec1, 1));
1620
1621     CASE_CONVERT:
1622       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1623                               TREE_OPERAND (chrec1, 0));
1624
1625     default:
1626       return operand_equal_p (chrec0, chrec1, 0);
1627     }
1628 }
1629
1630 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1631    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1632    which of these cases happens.  */
1633
1634 enum ev_direction
1635 scev_direction (const_tree chrec)
1636 {
1637   const_tree step;
1638
1639   if (!evolution_function_is_affine_p (chrec))
1640     return EV_DIR_UNKNOWN;
1641
1642   step = CHREC_RIGHT (chrec);
1643   if (TREE_CODE (step) != INTEGER_CST)
1644     return EV_DIR_UNKNOWN;
1645
1646   if (tree_int_cst_sign_bit (step))
1647     return EV_DIR_DECREASES;
1648   else
1649     return EV_DIR_GROWS;
1650 }
1651
1652 /* Iterates over all the components of SCEV, and calls CBCK.  */
1653
1654 void
1655 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1656 {
1657   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1658     {
1659     case 3:
1660       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1661       /* FALLTHRU */
1662
1663     case 2:
1664       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1665       /* FALLTHRU */
1666
1667     case 1:
1668       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1669       /* FALLTHRU */
1670
1671     default:
1672       cbck (scev, data);
1673       break;
1674     }
1675 }
1676
1677 /* Returns true when the operation can be part of a linear
1678    expression.  */
1679
1680 static inline bool
1681 operator_is_linear (tree scev)
1682 {
1683   switch (TREE_CODE (scev))
1684     {
1685     case INTEGER_CST:
1686     case POLYNOMIAL_CHREC:
1687     case PLUS_EXPR:
1688     case POINTER_PLUS_EXPR:
1689     case MULT_EXPR:
1690     case MINUS_EXPR:
1691     case NEGATE_EXPR:
1692     case SSA_NAME:
1693     case NON_LVALUE_EXPR:
1694     case BIT_NOT_EXPR:
1695     CASE_CONVERT:
1696       return true;
1697
1698     default:
1699       return false;
1700     }
1701 }
1702
1703 /* Return true when SCEV is a linear expression.  Linear expressions
1704    can contain additions, substractions and multiplications.
1705    Multiplications are restricted to constant scaling: "cst * x".  */
1706
1707 bool
1708 scev_is_linear_expression (tree scev)
1709 {
1710   if (evolution_function_is_constant_p (scev))
1711     return true;
1712
1713   if (scev == NULL
1714       || !operator_is_linear (scev))
1715     return false;
1716
1717   if (TREE_CODE (scev) == MULT_EXPR)
1718     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1719              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1720
1721   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1722       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1723     return false;
1724
1725   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1726     {
1727     case 3:
1728       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1729         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1730         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1731
1732     case 2:
1733       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1734         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1735
1736     case 1:
1737       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1738
1739     case 0:
1740       return true;
1741
1742     default:
1743       return false;
1744     }
1745 }
1746
1747 /* Determines whether the expression CHREC contains only interger consts
1748    in the right parts.  */
1749
1750 bool
1751 evolution_function_right_is_integer_cst (const_tree chrec)
1752 {
1753   if (chrec == NULL_TREE)
1754     return false;
1755
1756   switch (TREE_CODE (chrec))
1757     {
1758     case INTEGER_CST:
1759       return true;
1760
1761     case POLYNOMIAL_CHREC:
1762       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1763         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1764             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1765
1766     CASE_CONVERT:
1767       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1768
1769     default:
1770       return false;
1771     }
1772 }