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