gcc/tree-chrec.c

   1 /* Chains of recurrences.
   2    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 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 "cfgloop.h"
  36 #include "tree-flow.h"
  37 #include "tree-chrec.h"
  38 #include "tree-pass.h"
  39 #include "params.h"
  40 #include "tree-scalar-evolution.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     return chrec_dont_know;
 537
 538   if (dump_file && (dump_flags & TDF_DETAILS))
 539     fprintf (dump_file, "(chrec_apply \n");
 540
 541   if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
 542     x = build_real_from_int_cst (type, x);
 543
 544   if (evolution_function_is_affine_p (chrec))
 545     {
 546       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 547       x = chrec_convert (type, x, NULL_TREE);
 548       res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
 549       if (!integer_zerop (CHREC_LEFT (chrec)))
 550         res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
 551     }
 552
 553   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 554     res = chrec;
 555
 556   else if (TREE_CODE (x) == INTEGER_CST
 557            && tree_int_cst_sgn (x) == 1)
 558     /* testsuite/.../ssa-chrec-38.c.  */
 559     res = chrec_evaluate (var, chrec, x, 0);
 560   else
 561     res = chrec_dont_know;
 562
 563   if (dump_file && (dump_flags & TDF_DETAILS))
 564     {
 565       fprintf (dump_file, "  (varying_loop = %d\n", var);
 566       fprintf (dump_file, ")\n  (chrec = ");
 567       print_generic_expr (dump_file, chrec, 0);
 568       fprintf (dump_file, ")\n  (x = ");
 569       print_generic_expr (dump_file, x, 0);
 570       fprintf (dump_file, ")\n  (res = ");
 571       print_generic_expr (dump_file, res, 0);
 572       fprintf (dump_file, "))\n");
 573     }
 574
 575   return res;
 576 }
 577
 578 /* Replaces the initial condition in CHREC with INIT_COND.  */
 579
 580 tree
 581 chrec_replace_initial_condition (tree chrec,
 582                                  tree init_cond)
 583 {
 584   if (automatically_generated_chrec_p (chrec))
 585     return chrec;
 586
 587   switch (TREE_CODE (chrec))
 588     {
 589     case POLYNOMIAL_CHREC:
 590       return build_polynomial_chrec
 591         (CHREC_VARIABLE (chrec),
 592          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 593          CHREC_RIGHT (chrec));
 594
 595     default:
 596       return init_cond;
 597     }
 598 }
 599
 600 /* Returns the initial condition of a given CHREC.  */
 601
 602 tree
 603 initial_condition (tree chrec)
 604 {
 605   if (automatically_generated_chrec_p (chrec))
 606     return chrec;
 607
 608   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 609     return initial_condition (CHREC_LEFT (chrec));
 610   else
 611     return chrec;
 612 }
 613
 614 /* Returns a univariate function that represents the evolution in
 615    LOOP_NUM.  Mask the evolution of any other loop.  */
 616
 617 tree
 618 hide_evolution_in_other_loops_than_loop (tree chrec,
 619                                          unsigned loop_num)
 620 {
 621   if (automatically_generated_chrec_p (chrec))
 622     return chrec;
 623
 624   switch (TREE_CODE (chrec))
 625     {
 626     case POLYNOMIAL_CHREC:
 627       if (CHREC_VARIABLE (chrec) == loop_num)
 628         return build_polynomial_chrec
 629           (loop_num,
 630            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 631                                                     loop_num),
 632            CHREC_RIGHT (chrec));
 633
 634       else if (CHREC_VARIABLE (chrec) < loop_num)
 635         /* There is no evolution in this loop.  */
 636         return initial_condition (chrec);
 637
 638       else
 639         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 640                                                         loop_num);
 641
 642     default:
 643       return chrec;
 644     }
 645 }
 646
 647 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 648    true, otherwise returns the initial condition in LOOP_NUM.  */
 649
 650 static tree
 651 chrec_component_in_loop_num (tree chrec,
 652                              unsigned loop_num,
 653                              bool right)
 654 {
 655   tree component;
 656
 657   if (automatically_generated_chrec_p (chrec))
 658     return chrec;
 659
 660   switch (TREE_CODE (chrec))
 661     {
 662     case POLYNOMIAL_CHREC:
 663       if (CHREC_VARIABLE (chrec) == loop_num)
 664         {
 665           if (right)
 666             component = CHREC_RIGHT (chrec);
 667           else
 668             component = CHREC_LEFT (chrec);
 669
 670           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 671               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 672             return component;
 673
 674           else
 675             return build_polynomial_chrec
 676               (loop_num,
 677                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 678                                             loop_num,
 679                                             right),
 680                component);
 681         }
 682
 683       else if (CHREC_VARIABLE (chrec) < loop_num)
 684         /* There is no evolution part in this loop.  */
 685         return NULL_TREE;
 686
 687       else
 688         return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 689                                             loop_num,
 690                                             right);
 691
 692      default:
 693       if (right)
 694         return NULL_TREE;
 695       else
 696         return chrec;
 697     }
 698 }
 699
 700 /* Returns the evolution part in LOOP_NUM.  Example: the call
 701    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 702    {1, +, 2}_1  */
 703
 704 tree
 705 evolution_part_in_loop_num (tree chrec,
 706                             unsigned loop_num)
 707 {
 708   return chrec_component_in_loop_num (chrec, loop_num, true);
 709 }
 710
 711 /* Returns the initial condition in LOOP_NUM.  Example: the call
 712    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 713    {0, +, 1}_1  */
 714
 715 tree
 716 initial_condition_in_loop_num (tree chrec,
 717                                unsigned loop_num)
 718 {
 719   return chrec_component_in_loop_num (chrec, loop_num, false);
 720 }
 721
 722 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 723    This function is essentially used for setting the evolution to
 724    chrec_dont_know, for example after having determined that it is
 725    impossible to say how many times a loop will execute.  */
 726
 727 tree
 728 reset_evolution_in_loop (unsigned loop_num,
 729                          tree chrec,
 730                          tree new_evol)
 731 {
 732   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 733       && CHREC_VARIABLE (chrec) > loop_num)
 734     {
 735       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 736                                            new_evol);
 737       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 738                                             new_evol);
 739       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
 740                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 741                      left, right);
 742     }
 743
 744   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 745          && CHREC_VARIABLE (chrec) == loop_num)
 746     chrec = CHREC_LEFT (chrec);
 747
 748   return build_polynomial_chrec (loop_num, chrec, new_evol);
 749 }
 750
 751 /* Merges two evolution functions that were found by following two
 752    alternate paths of a conditional expression.  */
 753
 754 tree
 755 chrec_merge (tree chrec1,
 756              tree chrec2)
 757 {
 758   if (chrec1 == chrec_dont_know
 759       || chrec2 == chrec_dont_know)
 760     return chrec_dont_know;
 761
 762   if (chrec1 == chrec_known
 763       || chrec2 == chrec_known)
 764     return chrec_known;
 765
 766   if (chrec1 == chrec_not_analyzed_yet)
 767     return chrec2;
 768   if (chrec2 == chrec_not_analyzed_yet)
 769     return chrec1;
 770
 771   if (operand_equal_p (chrec1, chrec2, 0))
 772     return chrec1;
 773
 774   return chrec_dont_know;
 775 }
 776
 777 \f
 778
 779 /* Observers.  */
 780
 781 /* Helper function for is_multivariate_chrec.  */
 782
 783 static bool
 784 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 785 {
 786   if (chrec == NULL_TREE)
 787     return false;
 788
 789   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 790     {
 791       if (CHREC_VARIABLE (chrec) != rec_var)
 792         return true;
 793       else
 794         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 795                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 796     }
 797   else
 798     return false;
 799 }
 800
 801 /* Determine whether the given chrec is multivariate or not.  */
 802
 803 bool
 804 is_multivariate_chrec (tree chrec)
 805 {
 806   if (chrec == NULL_TREE)
 807     return false;
 808
 809   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 810     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 811                                        CHREC_VARIABLE (chrec))
 812             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 813                                           CHREC_VARIABLE (chrec)));
 814   else
 815     return false;
 816 }
 817
 818 /* Determines whether the chrec contains symbolic names or not.  */
 819
 820 bool
 821 chrec_contains_symbols (tree chrec)
 822 {
 823   if (chrec == NULL_TREE)
 824     return false;
 825
 826   if (TREE_CODE (chrec) == SSA_NAME
 827       || TREE_CODE (chrec) == VAR_DECL
 828       || TREE_CODE (chrec) == PARM_DECL
 829       || TREE_CODE (chrec) == FUNCTION_DECL
 830       || TREE_CODE (chrec) == LABEL_DECL
 831       || TREE_CODE (chrec) == RESULT_DECL
 832       || TREE_CODE (chrec) == FIELD_DECL)
 833     return true;
 834
 835   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 836     {
 837     case 3:
 838       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 839         return true;
 840
 841     case 2:
 842       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 843         return true;
 844
 845     case 1:
 846       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 847         return true;
 848
 849     default:
 850       return false;
 851     }
 852 }
 853
 854 /* Determines whether the chrec contains undetermined coefficients.  */
 855
 856 bool
 857 chrec_contains_undetermined (tree chrec)
 858 {
 859   if (chrec == chrec_dont_know
 860       || chrec == chrec_not_analyzed_yet
 861       || chrec == NULL_TREE)
 862     return true;
 863
 864   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 865     {
 866     case 3:
 867       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 868         return true;
 869
 870     case 2:
 871       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 872         return true;
 873
 874     case 1:
 875       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 876         return true;
 877
 878     default:
 879       return false;
 880     }
 881 }
 882
 883 /* Determines whether the tree EXPR contains chrecs, and increment
 884    SIZE if it is not a NULL pointer by an estimation of the depth of
 885    the tree.  */
 886
 887 bool
 888 tree_contains_chrecs (tree expr, int *size)
 889 {
 890   if (expr == NULL_TREE)
 891     return false;
 892
 893   if (size)
 894     (*size)++;
 895
 896   if (tree_is_chrec (expr))
 897     return true;
 898
 899   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 900     {
 901     case 3:
 902       if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
 903         return true;
 904
 905     case 2:
 906       if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
 907         return true;
 908
 909     case 1:
 910       if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
 911         return true;
 912
 913     default:
 914       return false;
 915     }
 916 }
 917
 918 /* Recursive helper function.  */
 919
 920 static bool
 921 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 922 {
 923   if (evolution_function_is_constant_p (chrec))
 924     return true;
 925
 926   if (TREE_CODE (chrec) == SSA_NAME
 927       && expr_invariant_in_loop_p (current_loops->parray[loopnum],
 928                                    chrec))
 929     return true;
 930
 931   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 932     {
 933       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
 934           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
 935                                                      loopnum)
 936           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
 937                                                      loopnum))
 938         return false;
 939       return true;
 940     }
 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           return fold_convert (type, chrec);
1161         }
1162
1163       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1164                                      chrec_convert (type, CHREC_LEFT (chrec),
1165                                                     at_stmt),
1166                                      step);
1167     }
1168
1169   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1170     return chrec_dont_know;
1171
1172   res = fold_convert (type, chrec);
1173
1174   /* Don't propagate overflows.  */
1175   if (CONSTANT_CLASS_P (res))
1176     {
1177       TREE_CONSTANT_OVERFLOW (res) = 0;
1178       TREE_OVERFLOW (res) = 0;
1179     }
1180
1181   /* But reject constants that don't fit in their type after conversion.
1182      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1183      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1184      and can cause problems later when computing niters of loops.  Note
1185      that we don't do the check before converting because we don't want
1186      to reject conversions of negative chrecs to unsigned types.  */
1187   if (TREE_CODE (res) == INTEGER_CST
1188       && TREE_CODE (type) == INTEGER_TYPE
1189       && !int_fits_type_p (res, type))
1190     res = chrec_dont_know;
1191
1192   return res;
1193 }
1194
1195 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1196    chrec if something else than what chrec_convert would do happens, NULL_TREE
1197    otherwise.  */
1198
1199 tree
1200 chrec_convert_aggressive (tree type, tree chrec)
1201 {
1202   tree inner_type, left, right, lc, rc;
1203
1204   if (automatically_generated_chrec_p (chrec)
1205       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1206     return NULL_TREE;
1207
1208   inner_type = TREE_TYPE (chrec);
1209   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1210     return NULL_TREE;
1211
1212   left = CHREC_LEFT (chrec);
1213   right = CHREC_RIGHT (chrec);
1214   lc = chrec_convert_aggressive (type, left);
1215   if (!lc)
1216     lc = chrec_convert (type, left, NULL_TREE);
1217   rc = chrec_convert_aggressive (type, right);
1218   if (!rc)
1219     rc = chrec_convert (type, right, NULL_TREE);
1220
1221   /* Ada creates sub-types where TYPE_MIN_VALUE/TYPE_MAX_VALUE do not
1222      cover the entire range of values allowed by TYPE_PRECISION.
1223
1224      We do not want to optimize away conversions to such types.  Long
1225      term I'd rather see the Ada front-end fixed.  */
1226   if (INTEGRAL_TYPE_P (type))
1227     {
1228       tree t;
1229
1230       t = upper_bound_in_type (type, inner_type);
1231       if (! TYPE_MAX_VALUE (type)
1232           || ! operand_equal_p (TYPE_MAX_VALUE (type), t, 0))
1233         return NULL_TREE;
1234
1235       t = lower_bound_in_type (type, inner_type);
1236       if (! TYPE_MIN_VALUE (type)
1237           || ! operand_equal_p (TYPE_MIN_VALUE (type), t, 0))
1238         return NULL_TREE;
1239     }
1240
1241   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1242 }
1243
1244 /* Returns the type of the chrec.  */
1245
1246 tree
1247 chrec_type (tree chrec)
1248 {
1249   if (automatically_generated_chrec_p (chrec))
1250     return NULL_TREE;
1251
1252   return TREE_TYPE (chrec);
1253 }
1254
1255 /* Returns true when CHREC0 == CHREC1.  */
1256
1257 bool
1258 eq_evolutions_p (tree chrec0,
1259                  tree chrec1)
1260 {
1261   if (chrec0 == NULL_TREE
1262       || chrec1 == NULL_TREE
1263       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1264     return false;
1265
1266   if (chrec0 == chrec1)
1267     return true;
1268
1269   switch (TREE_CODE (chrec0))
1270     {
1271     case INTEGER_CST:
1272       return integer_zerop (fold (build2 (MINUS_EXPR, TREE_TYPE (chrec0),
1273                                          chrec0, chrec1)));
1274     case POLYNOMIAL_CHREC:
1275       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1276               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1277               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1278     default:
1279       return false;
1280     }
1281 }
1282