gcc/tree-chrec.c

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