gcc/tree-chrec.c

   1 /* Chains of recurrences.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <s.pop@laposte.net>
   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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* This file implements operations on chains of recurrences.  Chains
  23    of recurrences are used for modeling evolution functions of scalar
  24    variables.
  25 */
  26
  27 #include "config.h"
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "tm.h"
  31 #include "ggc.h"
  32 #include "tree.h"
  33 #include "real.h"
  34 #include "diagnostic.h"
  35 #include "varray.h"
  36 #include "cfgloop.h"
  37 #include "tree-flow.h"
  38 #include "tree-chrec.h"
  39 #include "tree-pass.h"
  40 #include "params.h"
  41 #include "tree-scalar-evolution.h"
  42
  43 \f
  44
  45 /* Extended folder for chrecs.  */
  46
  47 /* Determines whether CST is not a constant evolution.  */
  48
  49 static inline bool
  50 is_not_constant_evolution (tree cst)
  51 {
  52   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
  53 }
  54
  55 /* Fold CODE for a polynomial function and a constant.  */
  56
  57 static inline tree
  58 chrec_fold_poly_cst (enum tree_code code,
  59                      tree type,
  60                      tree poly,
  61                      tree cst)
  62 {
  63   gcc_assert (poly);
  64   gcc_assert (cst);
  65   gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
  66   gcc_assert (!is_not_constant_evolution (cst));
  67
  68   switch (code)
  69     {
  70     case PLUS_EXPR:
  71       return build_polynomial_chrec
  72         (CHREC_VARIABLE (poly),
  73          chrec_fold_plus (type, CHREC_LEFT (poly), cst),
  74          CHREC_RIGHT (poly));
  75
  76     case MINUS_EXPR:
  77       return build_polynomial_chrec
  78         (CHREC_VARIABLE (poly),
  79          chrec_fold_minus (type, CHREC_LEFT (poly), cst),
  80          CHREC_RIGHT (poly));
  81
  82     case MULT_EXPR:
  83       return build_polynomial_chrec
  84         (CHREC_VARIABLE (poly),
  85          chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
  86          chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
  87
  88     default:
  89       return chrec_dont_know;
  90     }
  91 }
  92
  93 /* Fold the addition of two polynomial functions.  */
  94
  95 static inline tree
  96 chrec_fold_plus_poly_poly (enum tree_code code,
  97                            tree type,
  98                            tree poly0,
  99                            tree poly1)
 100 {
 101   tree left, right;
 102
 103   gcc_assert (poly0);
 104   gcc_assert (poly1);
 105   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
 106   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
 107
 108   /*
 109     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
 110     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
 111     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
 112   if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
 113     {
 114       if (code == PLUS_EXPR)
 115         return build_polynomial_chrec
 116           (CHREC_VARIABLE (poly1),
 117            chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
 118            CHREC_RIGHT (poly1));
 119       else
 120         return build_polynomial_chrec
 121           (CHREC_VARIABLE (poly1),
 122            chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
 123            chrec_fold_multiply (type, CHREC_RIGHT (poly1),
 124                                 SCALAR_FLOAT_TYPE_P (type)
 125                                 ? build_real (type, dconstm1)
 126                                 : build_int_cst_type (type, -1)));
 127     }
 128
 129   if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
 130     {
 131       if (code == PLUS_EXPR)
 132         return build_polynomial_chrec
 133           (CHREC_VARIABLE (poly0),
 134            chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
 135            CHREC_RIGHT (poly0));
 136       else
 137         return build_polynomial_chrec
 138           (CHREC_VARIABLE (poly0),
 139            chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
 140            CHREC_RIGHT (poly0));
 141     }
 142
 143   if (code == PLUS_EXPR)
 144     {
 145       left = chrec_fold_plus
 146         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 147       right = chrec_fold_plus
 148         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 149     }
 150   else
 151     {
 152       left = chrec_fold_minus
 153         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 154       right = chrec_fold_minus
 155         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 156     }
 157
 158   if (chrec_zerop (right))
 159     return left;
 160   else
 161     return build_polynomial_chrec
 162       (CHREC_VARIABLE (poly0), left, right);
 163 }
 164
 165 \f
 166
 167 /* Fold the multiplication of two polynomial functions.  */
 168
 169 static inline tree
 170 chrec_fold_multiply_poly_poly (tree type,
 171                                tree poly0,
 172                                tree poly1)
 173 {
 174   tree t0, t1, t2;
 175   int var;
 176
 177   gcc_assert (poly0);
 178   gcc_assert (poly1);
 179   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
 180   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
 181
 182   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
 183      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
 184      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
 185   if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
 186     /* poly0 is a constant wrt. poly1.  */
 187     return build_polynomial_chrec
 188       (CHREC_VARIABLE (poly1),
 189        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
 190        CHREC_RIGHT (poly1));
 191
 192   if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
 193     /* poly1 is a constant wrt. poly0.  */
 194     return build_polynomial_chrec
 195       (CHREC_VARIABLE (poly0),
 196        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
 197        CHREC_RIGHT (poly0));
 198
 199   /* poly0 and poly1 are two polynomials in the same variable,
 200      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
 201
 202   /* "a*c".  */
 203   t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 204
 205   /* "a*d + b*c + b*d".  */
 206   t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
 207   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
 208                                                        CHREC_RIGHT (poly0),
 209                                                        CHREC_LEFT (poly1)));
 210   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
 211                                                        CHREC_RIGHT (poly0),
 212                                                        CHREC_RIGHT (poly1)));
 213   /* "2*b*d".  */
 214   t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 215   t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
 216                             ? build_real (type, dconst2)
 217                             : build_int_cst_type (type, 2), t2);
 218
 219   var = CHREC_VARIABLE (poly0);
 220   return build_polynomial_chrec (var, t0,
 221                                  build_polynomial_chrec (var, t1, t2));
 222 }
 223
 224 /* When the operands are automatically_generated_chrec_p, the fold has
 225    to respect the semantics of the operands.  */
 226
 227 static inline tree
 228 chrec_fold_automatically_generated_operands (tree op0,
 229                                              tree op1)
 230 {
 231   if (op0 == chrec_dont_know
 232       || op1 == chrec_dont_know)
 233     return chrec_dont_know;
 234
 235   if (op0 == chrec_known
 236       || op1 == chrec_known)
 237     return chrec_known;
 238
 239   if (op0 == chrec_not_analyzed_yet
 240       || op1 == chrec_not_analyzed_yet)
 241     return chrec_not_analyzed_yet;
 242
 243   /* The default case produces a safe result.  */
 244   return chrec_dont_know;
 245 }
 246
 247 /* Fold the addition of two chrecs.  */
 248
 249 static tree
 250 chrec_fold_plus_1 (enum tree_code code,
 251                    tree type,
 252                    tree op0,
 253                    tree op1)
 254 {
 255   if (automatically_generated_chrec_p (op0)
 256       || automatically_generated_chrec_p (op1))
 257     return chrec_fold_automatically_generated_operands (op0, op1);
 258
 259   switch (TREE_CODE (op0))
 260     {
 261     case POLYNOMIAL_CHREC:
 262       switch (TREE_CODE (op1))
 263         {
 264         case POLYNOMIAL_CHREC:
 265           return chrec_fold_plus_poly_poly (code, type, op0, op1);
 266
 267         default:
 268           if (code == PLUS_EXPR)
 269             return build_polynomial_chrec
 270               (CHREC_VARIABLE (op0),
 271                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
 272                CHREC_RIGHT (op0));
 273           else
 274             return build_polynomial_chrec
 275               (CHREC_VARIABLE (op0),
 276                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
 277                CHREC_RIGHT (op0));
 278         }
 279
 280     default:
 281       switch (TREE_CODE (op1))
 282         {
 283         case POLYNOMIAL_CHREC:
 284           if (code == PLUS_EXPR)
 285             return build_polynomial_chrec
 286               (CHREC_VARIABLE (op1),
 287                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
 288                CHREC_RIGHT (op1));
 289           else
 290             return build_polynomial_chrec
 291               (CHREC_VARIABLE (op1),
 292                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
 293                chrec_fold_multiply (type, CHREC_RIGHT (op1),
 294                                     SCALAR_FLOAT_TYPE_P (type)
 295                                     ? build_real (type, dconstm1)
 296                                     : build_int_cst_type (type, -1)));
 297
 298         default:
 299           {
 300             int size = 0;
 301             if ((tree_contains_chrecs (op0, &size)
 302                  || tree_contains_chrecs (op1, &size))
 303                 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 304               return build2 (code, type, op0, op1);
 305             else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 306               return fold_build2 (code, type,
 307                                   fold_convert (type, op0),
 308                                   fold_convert (type, op1));
 309             else
 310               return chrec_dont_know;
 311           }
 312         }
 313     }
 314 }
 315
 316 /* Fold the addition of two chrecs.  */
 317
 318 tree
 319 chrec_fold_plus (tree type,
 320                  tree op0,
 321                  tree op1)
 322 {
 323   if (integer_zerop (op0))
 324     return op1;
 325   if (integer_zerop (op1))
 326     return op0;
 327
 328   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
 329 }
 330
 331 /* Fold the subtraction of two chrecs.  */
 332
 333 tree
 334 chrec_fold_minus (tree type,
 335                   tree op0,
 336                   tree op1)
 337 {
 338   if (integer_zerop (op1))
 339     return op0;
 340
 341   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
 342 }
 343
 344 /* Fold the multiplication of two chrecs.  */
 345
 346 tree
 347 chrec_fold_multiply (tree type,
 348                      tree op0,
 349                      tree op1)
 350 {
 351   if (automatically_generated_chrec_p (op0)
 352       || automatically_generated_chrec_p (op1))
 353     return chrec_fold_automatically_generated_operands (op0, op1);
 354
 355   switch (TREE_CODE (op0))
 356     {
 357     case POLYNOMIAL_CHREC:
 358       switch (TREE_CODE (op1))
 359         {
 360         case POLYNOMIAL_CHREC:
 361           return chrec_fold_multiply_poly_poly (type, op0, op1);
 362
 363         default:
 364           if (integer_onep (op1))
 365             return op0;
 366           if (integer_zerop (op1))
 367             return build_int_cst_type (type, 0);
 368
 369           return build_polynomial_chrec
 370             (CHREC_VARIABLE (op0),
 371              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
 372              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 373         }
 374
 375     default:
 376       if (integer_onep (op0))
 377         return op1;
 378
 379       if (integer_zerop (op0))
 380         return build_int_cst_type (type, 0);
 381
 382       switch (TREE_CODE (op1))
 383         {
 384         case POLYNOMIAL_CHREC:
 385           return build_polynomial_chrec
 386             (CHREC_VARIABLE (op1),
 387              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 388              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 389
 390         default:
 391           if (integer_onep (op1))
 392             return op0;
 393           if (integer_zerop (op1))
 394             return build_int_cst_type (type, 0);
 395           return fold_build2 (MULT_EXPR, type, op0, op1);
 396         }
 397     }
 398 }
 399
 400 \f
 401
 402 /* Operations.  */
 403
 404 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
 405    calculation overflows, otherwise return C(n,k) with type TYPE.  */
 406
 407 static tree
 408 tree_fold_binomial (tree type, tree n, unsigned int k)
 409 {
 410   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
 411   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
 412   unsigned int i;
 413   tree res;
 414
 415   /* Handle the most frequent cases.  */
 416   if (k == 0)
 417     return build_int_cst (type, 1);
 418   if (k == 1)
 419     return fold_convert (type, n);
 420
 421   /* Check that k <= n.  */
 422   if (TREE_INT_CST_HIGH (n) == 0
 423       && TREE_INT_CST_LOW (n) < k)
 424     return NULL_TREE;
 425
 426   /* Numerator = n.  */
 427   lnum = TREE_INT_CST_LOW (n);
 428   hnum = TREE_INT_CST_HIGH (n);
 429
 430   /* Denominator = 2.  */
 431   ldenom = 2;
 432   hdenom = 0;
 433
 434   /* Index = Numerator-1.  */
 435   if (lnum == 0)
 436     {
 437       hidx = hnum - 1;
 438       lidx = ~ (unsigned HOST_WIDE_INT) 0;
 439     }
 440   else
 441     {
 442       hidx = hnum;
 443       lidx = lnum - 1;
 444     }
 445
 446   /* Numerator = Numerator*Index = n*(n-1).  */
 447   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 448     return NULL_TREE;
 449
 450   for (i = 3; i <= k; i++)
 451     {
 452       /* Index--.  */
 453       if (lidx == 0)
 454         {
 455           hidx--;
 456           lidx = ~ (unsigned HOST_WIDE_INT) 0;
 457         }
 458       else
 459         lidx--;
 460
 461       /* Numerator *= Index.  */
 462       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 463         return NULL_TREE;
 464
 465       /* Denominator *= i.  */
 466       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
 467     }
 468
 469   /* Result = Numerator / Denominator.  */
 470   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
 471                         &lres, &hres, &ldum, &hdum);
 472
 473   res = build_int_cst_wide (type, lres, hres);
 474   return int_fits_type_p (res, type) ? res : NULL_TREE;
 475 }
 476
 477 /* Helper function.  Use the Newton's interpolating formula for
 478    evaluating the value of the evolution function.  */
 479
 480 static tree
 481 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 482 {
 483   tree arg0, arg1, binomial_n_k;
 484   tree type = TREE_TYPE (chrec);
 485
 486   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 487          && CHREC_VARIABLE (chrec) > var)
 488     chrec = CHREC_LEFT (chrec);
 489
 490   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 491       && CHREC_VARIABLE (chrec) == var)
 492     {
 493       arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
 494       if (arg0 == chrec_dont_know)
 495         return chrec_dont_know;
 496       binomial_n_k = tree_fold_binomial (type, n, k);
 497       if (!binomial_n_k)
 498         return chrec_dont_know;
 499       arg1 = fold_build2 (MULT_EXPR, type,
 500                           CHREC_LEFT (chrec), binomial_n_k);
 501       return chrec_fold_plus (type, arg0, arg1);
 502     }
 503
 504   binomial_n_k = tree_fold_binomial (type, n, k);
 505   if (!binomial_n_k)
 506     return chrec_dont_know;
 507
 508   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
 509 }
 510
 511 /* Evaluates "CHREC (X)" when the varying variable is VAR.
 512    Example:  Given the following parameters,
 513
 514    var = 1
 515    chrec = {3, +, 4}_1
 516    x = 10
 517
 518    The result is given by the Newton's interpolating formula:
 519    3 * \binom{10}{0} + 4 * \binom{10}{1}.
 520 */
 521
 522 tree
 523 chrec_apply (unsigned var,
 524              tree chrec,
 525              tree x)
 526 {
 527   tree type = chrec_type (chrec);
 528   tree res = chrec_dont_know;
 529
 530   if (automatically_generated_chrec_p (chrec)
 531       || automatically_generated_chrec_p (x)
 532
 533       /* When the symbols are defined in an outer loop, it is possible
 534          to symbolically compute the apply, since the symbols are
 535          constants with respect to the varying loop.  */
 536       || chrec_contains_symbols_defined_in_loop (chrec, var)
 537       || chrec_contains_symbols (x))
 538     return chrec_dont_know;
 539
 540   if (dump_file && (dump_flags & TDF_DETAILS))
 541     fprintf (dump_file, "(chrec_apply \n");
 542
 543   if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
 544     x = build_real_from_int_cst (type, x);
 545
 546   if (evolution_function_is_affine_p (chrec))
 547     {
 548       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 549       if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
 550           && integer_zerop (CHREC_LEFT (chrec)))
 551         res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
 552
 553       else
 554         res = chrec_fold_plus (type, CHREC_LEFT (chrec),
 555                                chrec_fold_multiply (type,
 556                                                     CHREC_RIGHT (chrec), x));
 557     }
 558
 559   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 560     res = chrec;
 561
 562   else if (TREE_CODE (x) == INTEGER_CST
 563            && tree_int_cst_sgn (x) == 1)
 564     /* testsuite/.../ssa-chrec-38.c.  */
 565     res = chrec_evaluate (var, chrec, x, 0);
 566
 567   else
 568     res = chrec_dont_know;
 569
 570   if (dump_file && (dump_flags & TDF_DETAILS))
 571     {
 572       fprintf (dump_file, "  (varying_loop = %d\n", var);
 573       fprintf (dump_file, ")\n  (chrec = ");
 574       print_generic_expr (dump_file, chrec, 0);
 575       fprintf (dump_file, ")\n  (x = ");
 576       print_generic_expr (dump_file, x, 0);
 577       fprintf (dump_file, ")\n  (res = ");
 578       print_generic_expr (dump_file, res, 0);
 579       fprintf (dump_file, "))\n");
 580     }
 581
 582   return res;
 583 }
 584
 585 /* Replaces the initial condition in CHREC with INIT_COND.  */
 586
 587 tree
 588 chrec_replace_initial_condition (tree chrec,
 589                                  tree init_cond)
 590 {
 591   if (automatically_generated_chrec_p (chrec))
 592     return chrec;
 593
 594   switch (TREE_CODE (chrec))
 595     {
 596     case POLYNOMIAL_CHREC:
 597       return build_polynomial_chrec
 598         (CHREC_VARIABLE (chrec),
 599          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 600          CHREC_RIGHT (chrec));
 601
 602     default:
 603       return init_cond;
 604     }
 605 }
 606
 607 /* Returns the initial condition of a given CHREC.  */
 608
 609 tree
 610 initial_condition (tree chrec)
 611 {
 612   if (automatically_generated_chrec_p (chrec))
 613     return chrec;
 614
 615   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 616     return initial_condition (CHREC_LEFT (chrec));
 617   else
 618     return chrec;
 619 }
 620
 621 /* Returns a univariate function that represents the evolution in
 622    LOOP_NUM.  Mask the evolution of any other loop.  */
 623
 624 tree
 625 hide_evolution_in_other_loops_than_loop (tree chrec,
 626                                          unsigned loop_num)
 627 {
 628   if (automatically_generated_chrec_p (chrec))
 629     return chrec;
 630
 631   switch (TREE_CODE (chrec))
 632     {
 633     case POLYNOMIAL_CHREC:
 634       if (CHREC_VARIABLE (chrec) == loop_num)
 635         return build_polynomial_chrec
 636           (loop_num,
 637            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 638                                                     loop_num),
 639            CHREC_RIGHT (chrec));
 640
 641       else if (CHREC_VARIABLE (chrec) < loop_num)
 642         /* There is no evolution in this loop.  */
 643         return initial_condition (chrec);
 644
 645       else
 646         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 647                                                         loop_num);
 648
 649     default:
 650       return chrec;
 651     }
 652 }
 653
 654 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 655    true, otherwise returns the initial condition in LOOP_NUM.  */
 656
 657 static tree
 658 chrec_component_in_loop_num (tree chrec,
 659                              unsigned loop_num,
 660                              bool right)
 661 {
 662   tree component;
 663
 664   if (automatically_generated_chrec_p (chrec))
 665     return chrec;
 666
 667   switch (TREE_CODE (chrec))
 668     {
 669     case POLYNOMIAL_CHREC:
 670       if (CHREC_VARIABLE (chrec) == loop_num)
 671         {
 672           if (right)
 673             component = CHREC_RIGHT (chrec);
 674           else
 675             component = CHREC_LEFT (chrec);
 676
 677           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 678               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 679             return component;
 680
 681           else
 682             return build_polynomial_chrec
 683               (loop_num,
 684                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 685                                             loop_num,
 686                                             right),
 687                component);
 688         }
 689
 690       else if (CHREC_VARIABLE (chrec) < loop_num)
 691         /* There is no evolution part in this loop.  */
 692         return NULL_TREE;
 693
 694       else
 695         return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 696                                             loop_num,
 697                                             right);
 698
 699      default:
 700       if (right)
 701         return NULL_TREE;
 702       else
 703         return chrec;
 704     }
 705 }
 706
 707 /* Returns the evolution part in LOOP_NUM.  Example: the call
 708    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 709    {1, +, 2}_1  */
 710
 711 tree
 712 evolution_part_in_loop_num (tree chrec,
 713                             unsigned loop_num)
 714 {
 715   return chrec_component_in_loop_num (chrec, loop_num, true);
 716 }
 717
 718 /* Returns the initial condition in LOOP_NUM.  Example: the call
 719    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 720    {0, +, 1}_1  */
 721
 722 tree
 723 initial_condition_in_loop_num (tree chrec,
 724                                unsigned loop_num)
 725 {
 726   return chrec_component_in_loop_num (chrec, loop_num, false);
 727 }
 728
 729 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 730    This function is essentially used for setting the evolution to
 731    chrec_dont_know, for example after having determined that it is
 732    impossible to say how many times a loop will execute.  */
 733
 734 tree
 735 reset_evolution_in_loop (unsigned loop_num,
 736                          tree chrec,
 737                          tree new_evol)
 738 {
 739   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 740       && CHREC_VARIABLE (chrec) > loop_num)
 741     {
 742       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 743                                            new_evol);
 744       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 745                                             new_evol);
 746       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
 747                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 748                      left, right);
 749     }
 750
 751   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 752          && CHREC_VARIABLE (chrec) == loop_num)
 753     chrec = CHREC_LEFT (chrec);
 754
 755   return build_polynomial_chrec (loop_num, chrec, new_evol);
 756 }
 757
 758 /* Merges two evolution functions that were found by following two
 759    alternate paths of a conditional expression.  */
 760
 761 tree
 762 chrec_merge (tree chrec1,
 763              tree chrec2)
 764 {
 765   if (chrec1 == chrec_dont_know
 766       || chrec2 == chrec_dont_know)
 767     return chrec_dont_know;
 768
 769   if (chrec1 == chrec_known
 770       || chrec2 == chrec_known)
 771     return chrec_known;
 772
 773   if (chrec1 == chrec_not_analyzed_yet)
 774     return chrec2;
 775   if (chrec2 == chrec_not_analyzed_yet)
 776     return chrec1;
 777
 778   if (operand_equal_p (chrec1, chrec2, 0))
 779     return chrec1;
 780
 781   return chrec_dont_know;
 782 }
 783
 784 \f
 785
 786 /* Observers.  */
 787
 788 /* Helper function for is_multivariate_chrec.  */
 789
 790 static bool
 791 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 792 {
 793   if (chrec == NULL_TREE)
 794     return false;
 795
 796   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 797     {
 798       if (CHREC_VARIABLE (chrec) != rec_var)
 799         return true;
 800       else
 801         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 802                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 803     }
 804   else
 805     return false;
 806 }
 807
 808 /* Determine whether the given chrec is multivariate or not.  */
 809
 810 bool
 811 is_multivariate_chrec (tree chrec)
 812 {
 813   if (chrec == NULL_TREE)
 814     return false;
 815
 816   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 817     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 818                                        CHREC_VARIABLE (chrec))
 819             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 820                                           CHREC_VARIABLE (chrec)));
 821   else
 822     return false;
 823 }
 824
 825 /* Determines whether the chrec contains symbolic names or not.  */
 826
 827 bool
 828 chrec_contains_symbols (tree chrec)
 829 {
 830   if (chrec == NULL_TREE)
 831     return false;
 832
 833   if (TREE_CODE (chrec) == SSA_NAME
 834       || TREE_CODE (chrec) == VAR_DECL
 835       || TREE_CODE (chrec) == PARM_DECL
 836       || TREE_CODE (chrec) == FUNCTION_DECL
 837       || TREE_CODE (chrec) == LABEL_DECL
 838       || TREE_CODE (chrec) == RESULT_DECL
 839       || TREE_CODE (chrec) == FIELD_DECL)
 840     return true;
 841
 842   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 843     {
 844     case 3:
 845       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 846         return true;
 847
 848     case 2:
 849       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 850         return true;
 851
 852     case 1:
 853       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 854         return true;
 855
 856     default:
 857       return false;
 858     }
 859 }
 860
 861 /* Determines whether the chrec contains undetermined coefficients.  */
 862
 863 bool
 864 chrec_contains_undetermined (tree chrec)
 865 {
 866   if (chrec == chrec_dont_know
 867       || chrec == chrec_not_analyzed_yet
 868       || chrec == NULL_TREE)
 869     return true;
 870
 871   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 872     {
 873     case 3:
 874       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 875         return true;
 876
 877     case 2:
 878       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 879         return true;
 880
 881     case 1:
 882       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 883         return true;
 884
 885     default:
 886       return false;
 887     }
 888 }
 889
 890 /* Determines whether the tree EXPR contains chrecs, and increment
 891    SIZE if it is not a NULL pointer by an estimation of the depth of
 892    the tree.  */
 893
 894 bool
 895 tree_contains_chrecs (tree expr, int *size)
 896 {
 897   if (expr == NULL_TREE)
 898     return false;
 899
 900   if (size)
 901     (*size)++;
 902
 903   if (tree_is_chrec (expr))
 904     return true;
 905
 906   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 907     {
 908     case 3:
 909       if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
 910         return true;
 911
 912     case 2:
 913       if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
 914         return true;
 915
 916     case 1:
 917       if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
 918         return true;
 919
 920     default:
 921       return false;
 922     }
 923 }
 924
 925 /* Recursive helper function.  */
 926
 927 static bool
 928 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 929 {
 930   if (evolution_function_is_constant_p (chrec))
 931     return true;
 932
 933   if (TREE_CODE (chrec) == SSA_NAME
 934       && expr_invariant_in_loop_p (current_loops->parray[loopnum],
 935                                    chrec))
 936     return true;
 937
 938   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 939       && CHREC_VARIABLE (chrec) == (unsigned) loopnum)
 940     return false;
 941
 942   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 943     {
 944     case 2:
 945       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
 946                                                   loopnum))
 947         return false;
 948
 949     case 1:
 950       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
 951                                                   loopnum))
 952         return false;
 953       return true;
 954
 955     default:
 956       return false;
 957     }
 958
 959   return false;
 960 }
 961
 962 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
 963
 964 bool
 965 evolution_function_is_invariant_p (tree chrec, int loopnum)
 966 {
 967   if (evolution_function_is_constant_p (chrec))
 968     return true;
 969
 970   if (current_loops != NULL)
 971     return evolution_function_is_invariant_rec_p (chrec, loopnum);
 972
 973   return false;
 974 }
 975
 976 /* Determine whether the given tree is an affine multivariate
 977    evolution.  */
 978
 979 bool
 980 evolution_function_is_affine_multivariate_p (tree chrec)
 981 {
 982   if (chrec == NULL_TREE)
 983     return false;
 984
 985   switch (TREE_CODE (chrec))
 986     {
 987     case POLYNOMIAL_CHREC:
 988       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 989         {
 990           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 991             return true;
 992           else
 993             {
 994               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
 995                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
 996                      != CHREC_VARIABLE (chrec)
 997                   && evolution_function_is_affine_multivariate_p
 998                   (CHREC_RIGHT (chrec)))
 999                 return true;
1000               else
1001                 return false;
1002             }
1003         }
1004       else
1005         {
1006           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1007               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1008               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1009               && evolution_function_is_affine_multivariate_p
1010               (CHREC_LEFT (chrec)))
1011             return true;
1012           else
1013             return false;
1014         }
1015
1016     default:
1017       return false;
1018     }
1019 }
1020
1021 /* Determine whether the given tree is a function in zero or one
1022    variables.  */
1023
1024 bool
1025 evolution_function_is_univariate_p (tree chrec)
1026 {
1027   if (chrec == NULL_TREE)
1028     return true;
1029
1030   switch (TREE_CODE (chrec))
1031     {
1032     case POLYNOMIAL_CHREC:
1033       switch (TREE_CODE (CHREC_LEFT (chrec)))
1034         {
1035         case POLYNOMIAL_CHREC:
1036           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1037             return false;
1038           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1039             return false;
1040           break;
1041
1042         default:
1043           break;
1044         }
1045
1046       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1047         {
1048         case POLYNOMIAL_CHREC:
1049           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1050             return false;
1051           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1052             return false;
1053           break;
1054
1055         default:
1056           break;
1057         }
1058
1059     default:
1060       return true;
1061     }
1062 }
1063
1064 /* Returns the number of variables of CHREC.  Example: the call
1065    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1066
1067 unsigned
1068 nb_vars_in_chrec (tree chrec)
1069 {
1070   if (chrec == NULL_TREE)
1071     return 0;
1072
1073   switch (TREE_CODE (chrec))
1074     {
1075     case POLYNOMIAL_CHREC:
1076       return 1 + nb_vars_in_chrec
1077         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1078
1079     default:
1080       return 0;
1081     }
1082 }
1083
1084 \f
1085
1086 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1087    which the CHREC is built, it sets AT_STMT to the statement that
1088    contains the definition of the analyzed variable, otherwise the
1089    conversion is less accurate: the information is used for
1090    determining a more accurate estimation of the number of iterations.
1091    By default AT_STMT could be safely set to NULL_TREE.
1092
1093    The following rule is always true: TREE_TYPE (chrec) ==
1094    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1095    An example of what could happen when adding two chrecs and the type
1096    of the CHREC_RIGHT is different than CHREC_LEFT is:
1097
1098    {(uint) 0, +, (uchar) 10} +
1099    {(uint) 0, +, (uchar) 250}
1100
1101    that would produce a wrong result if CHREC_RIGHT is not (uint):
1102
1103    {(uint) 0, +, (uchar) 4}
1104
1105    instead of
1106
1107    {(uint) 0, +, (uint) 260}
1108 */
1109
1110 tree
1111 chrec_convert (tree type, tree chrec, tree at_stmt)
1112 {
1113   tree ct, res;
1114
1115   if (automatically_generated_chrec_p (chrec))
1116     return chrec;
1117
1118   ct = chrec_type (chrec);
1119   if (ct == type)
1120     return chrec;
1121
1122   if (evolution_function_is_affine_p (chrec))
1123     {
1124       tree base, step;
1125       bool dummy;
1126       struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
1127
1128       base = instantiate_parameters (loop, CHREC_LEFT (chrec));
1129       step = instantiate_parameters (loop, CHREC_RIGHT (chrec));
1130
1131       /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1132          when it is not possible to prove that the scev does not wrap.
1133          See PR22236, where a sequence 1, 2, ..., 255 has to be
1134          converted to signed char, but this would wrap:
1135          1, 2, ..., 127, -128, ...  The result should not be
1136          {(schar)1, +, (schar)1}_x, but instead, we should keep the
1137          conversion: (schar) {(uchar)1, +, (uchar)1}_x.  */
1138       if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
1139                                  &dummy, &dummy))
1140         goto failed_to_convert;
1141
1142       step = convert_step (loop, type, base, step, at_stmt);
1143       if (!step)
1144         {
1145         failed_to_convert:;
1146           if (dump_file && (dump_flags & TDF_DETAILS))
1147             {
1148               fprintf (dump_file, "(failed conversion:");
1149               fprintf (dump_file, "\n  type: ");
1150               print_generic_expr (dump_file, type, 0);
1151               fprintf (dump_file, "\n  base: ");
1152               print_generic_expr (dump_file, base, 0);
1153               fprintf (dump_file, "\n  step: ");
1154               print_generic_expr (dump_file, step, 0);
1155               fprintf (dump_file, "\n  estimated_nb_iterations: ");
1156               print_generic_expr (dump_file, loop->estimated_nb_iterations, 0);
1157               fprintf (dump_file, "\n)\n");
1158             }
1159
1160           /* Directly convert to "don't know": no worth dealing with
1161              difficult cases.  */
1162           return chrec_dont_know;
1163         }
1164
1165       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1166                                      chrec_convert (type, CHREC_LEFT (chrec),
1167                                                     at_stmt),
1168                                      step);
1169     }
1170
1171   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1172     return chrec_dont_know;
1173
1174   res = fold_convert (type, chrec);
1175
1176   /* Don't propagate overflows.  */
1177   if (CONSTANT_CLASS_P (res))
1178     {
1179       TREE_CONSTANT_OVERFLOW (res) = 0;
1180       TREE_OVERFLOW (res) = 0;
1181     }
1182
1183   /* But reject constants that don't fit in their type after conversion.
1184      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1185      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1186      and can cause problems later when computing niters of loops.  Note
1187      that we don't do the check before converting because we don't want
1188      to reject conversions of negative chrecs to unsigned types.  */
1189   if (TREE_CODE (res) == INTEGER_CST
1190       && TREE_CODE (type) == INTEGER_TYPE
1191       && !int_fits_type_p (res, type))
1192     res = chrec_dont_know;
1193
1194   return res;
1195 }
1196
1197 /* Returns the type of the chrec.  */
1198
1199 tree
1200 chrec_type (tree chrec)
1201 {
1202   if (automatically_generated_chrec_p (chrec))
1203     return NULL_TREE;
1204
1205   return TREE_TYPE (chrec);
1206 }