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     {
 940       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
 941           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
 942                                                      loopnum)
 943           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
 944                                                      loopnum))
 945         return false;
 946       return true;
 947     }
 948
 949   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 950     {
 951     case 2:
 952       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
 953                                                   loopnum))
 954         return false;
 955
 956     case 1:
 957       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
 958                                                   loopnum))
 959         return false;
 960       return true;
 961
 962     default:
 963       return false;
 964     }
 965
 966   return false;
 967 }
 968
 969 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
 970
 971 bool
 972 evolution_function_is_invariant_p (tree chrec, int loopnum)
 973 {
 974   if (evolution_function_is_constant_p (chrec))
 975     return true;
 976
 977   if (current_loops != NULL)
 978     return evolution_function_is_invariant_rec_p (chrec, loopnum);
 979
 980   return false;
 981 }
 982
 983 /* Determine whether the given tree is an affine multivariate
 984    evolution.  */
 985
 986 bool
 987 evolution_function_is_affine_multivariate_p (tree chrec)
 988 {
 989   if (chrec == NULL_TREE)
 990     return false;
 991
 992   switch (TREE_CODE (chrec))
 993     {
 994     case POLYNOMIAL_CHREC:
 995       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 996         {
 997           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 998             return true;
 999           else
1000             {
1001               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1002                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1003                      != CHREC_VARIABLE (chrec)
1004                   && evolution_function_is_affine_multivariate_p
1005                   (CHREC_RIGHT (chrec)))
1006                 return true;
1007               else
1008                 return false;
1009             }
1010         }
1011       else
1012         {
1013           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1014               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1015               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1016               && evolution_function_is_affine_multivariate_p
1017               (CHREC_LEFT (chrec)))
1018             return true;
1019           else
1020             return false;
1021         }
1022
1023     default:
1024       return false;
1025     }
1026 }
1027
1028 /* Determine whether the given tree is a function in zero or one
1029    variables.  */
1030
1031 bool
1032 evolution_function_is_univariate_p (tree chrec)
1033 {
1034   if (chrec == NULL_TREE)
1035     return true;
1036
1037   switch (TREE_CODE (chrec))
1038     {
1039     case POLYNOMIAL_CHREC:
1040       switch (TREE_CODE (CHREC_LEFT (chrec)))
1041         {
1042         case POLYNOMIAL_CHREC:
1043           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1044             return false;
1045           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1046             return false;
1047           break;
1048
1049         default:
1050           break;
1051         }
1052
1053       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1054         {
1055         case POLYNOMIAL_CHREC:
1056           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1057             return false;
1058           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1059             return false;
1060           break;
1061
1062         default:
1063           break;
1064         }
1065
1066     default:
1067       return true;
1068     }
1069 }
1070
1071 /* Returns the number of variables of CHREC.  Example: the call
1072    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1073
1074 unsigned
1075 nb_vars_in_chrec (tree chrec)
1076 {
1077   if (chrec == NULL_TREE)
1078     return 0;
1079
1080   switch (TREE_CODE (chrec))
1081     {
1082     case POLYNOMIAL_CHREC:
1083       return 1 + nb_vars_in_chrec
1084         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1085
1086     default:
1087       return 0;
1088     }
1089 }
1090
1091 \f
1092
1093 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1094    which the CHREC is built, it sets AT_STMT to the statement that
1095    contains the definition of the analyzed variable, otherwise the
1096    conversion is less accurate: the information is used for
1097    determining a more accurate estimation of the number of iterations.
1098    By default AT_STMT could be safely set to NULL_TREE.
1099
1100    The following rule is always true: TREE_TYPE (chrec) ==
1101    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1102    An example of what could happen when adding two chrecs and the type
1103    of the CHREC_RIGHT is different than CHREC_LEFT is:
1104
1105    {(uint) 0, +, (uchar) 10} +
1106    {(uint) 0, +, (uchar) 250}
1107
1108    that would produce a wrong result if CHREC_RIGHT is not (uint):
1109
1110    {(uint) 0, +, (uchar) 4}
1111
1112    instead of
1113
1114    {(uint) 0, +, (uint) 260}
1115 */
1116
1117 tree
1118 chrec_convert (tree type, tree chrec, tree at_stmt)
1119 {
1120   tree ct, res;
1121
1122   if (automatically_generated_chrec_p (chrec))
1123     return chrec;
1124
1125   ct = chrec_type (chrec);
1126   if (ct == type)
1127     return chrec;
1128
1129   if (evolution_function_is_affine_p (chrec))
1130     {
1131       tree base, step;
1132       bool dummy;
1133       struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
1134
1135       base = instantiate_parameters (loop, CHREC_LEFT (chrec));
1136       step = instantiate_parameters (loop, CHREC_RIGHT (chrec));
1137
1138       /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1139          when it is not possible to prove that the scev does not wrap.
1140          See PR22236, where a sequence 1, 2, ..., 255 has to be
1141          converted to signed char, but this would wrap:
1142          1, 2, ..., 127, -128, ...  The result should not be
1143          {(schar)1, +, (schar)1}_x, but instead, we should keep the
1144          conversion: (schar) {(uchar)1, +, (uchar)1}_x.  */
1145       if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
1146                                  &dummy, &dummy))
1147         goto failed_to_convert;
1148
1149       step = convert_step (loop, type, base, step, at_stmt);
1150       if (!step)
1151         {
1152         failed_to_convert:;
1153           if (dump_file && (dump_flags & TDF_DETAILS))
1154             {
1155               fprintf (dump_file, "(failed conversion:");
1156               fprintf (dump_file, "\n  type: ");
1157               print_generic_expr (dump_file, type, 0);
1158               fprintf (dump_file, "\n  base: ");
1159               print_generic_expr (dump_file, base, 0);
1160               fprintf (dump_file, "\n  step: ");
1161               print_generic_expr (dump_file, step, 0);
1162               fprintf (dump_file, "\n  estimated_nb_iterations: ");
1163               print_generic_expr (dump_file, loop->estimated_nb_iterations, 0);
1164               fprintf (dump_file, "\n)\n");
1165             }
1166
1167           return fold_convert (type, chrec);
1168         }
1169
1170       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1171                                      chrec_convert (type, CHREC_LEFT (chrec),
1172                                                     at_stmt),
1173                                      step);
1174     }
1175
1176   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1177     return chrec_dont_know;
1178
1179   res = fold_convert (type, chrec);
1180
1181   /* Don't propagate overflows.  */
1182   if (CONSTANT_CLASS_P (res))
1183     {
1184       TREE_CONSTANT_OVERFLOW (res) = 0;
1185       TREE_OVERFLOW (res) = 0;
1186     }
1187
1188   /* But reject constants that don't fit in their type after conversion.
1189      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1190      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1191      and can cause problems later when computing niters of loops.  Note
1192      that we don't do the check before converting because we don't want
1193      to reject conversions of negative chrecs to unsigned types.  */
1194   if (TREE_CODE (res) == INTEGER_CST
1195       && TREE_CODE (type) == INTEGER_TYPE
1196       && !int_fits_type_p (res, type))
1197     res = chrec_dont_know;
1198
1199   return res;
1200 }
1201
1202 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1203    chrec if something else than what chrec_convert would do happens, NULL_TREE
1204    otherwise.  */
1205
1206 tree
1207 chrec_convert_aggressive (tree type, tree chrec)
1208 {
1209   tree inner_type, left, right, lc, rc;
1210
1211   if (automatically_generated_chrec_p (chrec)
1212       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1213     return NULL_TREE;
1214
1215   inner_type = TREE_TYPE (chrec);
1216   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1217     return NULL_TREE;
1218
1219   left = CHREC_LEFT (chrec);
1220   right = CHREC_RIGHT (chrec);
1221   lc = chrec_convert_aggressive (type, left);
1222   if (!lc)
1223     lc = chrec_convert (type, left, NULL_TREE);
1224   rc = chrec_convert_aggressive (type, right);
1225   if (!rc)
1226     rc = chrec_convert (type, right, NULL_TREE);
1227
1228   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1229 }
1230
1231 /* Returns the type of the chrec.  */
1232
1233 tree
1234 chrec_type (tree chrec)
1235 {
1236   if (automatically_generated_chrec_p (chrec))
1237     return NULL_TREE;
1238
1239   return TREE_TYPE (chrec);
1240 }