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 (evolution_function_is_affine_p (chrec))
 543     {
 544       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 545       if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
 546           && integer_zerop (CHREC_LEFT (chrec)))
 547         res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
 548
 549       else
 550         res = chrec_fold_plus (type, CHREC_LEFT (chrec),
 551                                chrec_fold_multiply (type,
 552                                                     CHREC_RIGHT (chrec), x));
 553     }
 554
 555   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 556     res = chrec;
 557
 558   else if (TREE_CODE (x) == INTEGER_CST
 559            && tree_int_cst_sgn (x) == 1)
 560     /* testsuite/.../ssa-chrec-38.c.  */
 561     res = chrec_evaluate (var, chrec, x, 0);
 562
 563   else
 564     res = chrec_dont_know;
 565
 566   if (dump_file && (dump_flags & TDF_DETAILS))
 567     {
 568       fprintf (dump_file, "  (varying_loop = %d\n", var);
 569       fprintf (dump_file, ")\n  (chrec = ");
 570       print_generic_expr (dump_file, chrec, 0);
 571       fprintf (dump_file, ")\n  (x = ");
 572       print_generic_expr (dump_file, x, 0);
 573       fprintf (dump_file, ")\n  (res = ");
 574       print_generic_expr (dump_file, res, 0);
 575       fprintf (dump_file, "))\n");
 576     }
 577
 578   return res;
 579 }
 580
 581 /* Replaces the initial condition in CHREC with INIT_COND.  */
 582
 583 tree
 584 chrec_replace_initial_condition (tree chrec,
 585                                  tree init_cond)
 586 {
 587   if (automatically_generated_chrec_p (chrec))
 588     return chrec;
 589
 590   switch (TREE_CODE (chrec))
 591     {
 592     case POLYNOMIAL_CHREC:
 593       return build_polynomial_chrec
 594         (CHREC_VARIABLE (chrec),
 595          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 596          CHREC_RIGHT (chrec));
 597
 598     default:
 599       return init_cond;
 600     }
 601 }
 602
 603 /* Returns the initial condition of a given CHREC.  */
 604
 605 tree
 606 initial_condition (tree chrec)
 607 {
 608   if (automatically_generated_chrec_p (chrec))
 609     return chrec;
 610
 611   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 612     return initial_condition (CHREC_LEFT (chrec));
 613   else
 614     return chrec;
 615 }
 616
 617 /* Returns a univariate function that represents the evolution in
 618    LOOP_NUM.  Mask the evolution of any other loop.  */
 619
 620 tree
 621 hide_evolution_in_other_loops_than_loop (tree chrec,
 622                                          unsigned loop_num)
 623 {
 624   if (automatically_generated_chrec_p (chrec))
 625     return chrec;
 626
 627   switch (TREE_CODE (chrec))
 628     {
 629     case POLYNOMIAL_CHREC:
 630       if (CHREC_VARIABLE (chrec) == loop_num)
 631         return build_polynomial_chrec
 632           (loop_num,
 633            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 634                                                     loop_num),
 635            CHREC_RIGHT (chrec));
 636
 637       else if (CHREC_VARIABLE (chrec) < loop_num)
 638         /* There is no evolution in this loop.  */
 639         return initial_condition (chrec);
 640
 641       else
 642         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 643                                                         loop_num);
 644
 645     default:
 646       return chrec;
 647     }
 648 }
 649
 650 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 651    true, otherwise returns the initial condition in LOOP_NUM.  */
 652
 653 static tree
 654 chrec_component_in_loop_num (tree chrec,
 655                              unsigned loop_num,
 656                              bool right)
 657 {
 658   tree component;
 659
 660   if (automatically_generated_chrec_p (chrec))
 661     return chrec;
 662
 663   switch (TREE_CODE (chrec))
 664     {
 665     case POLYNOMIAL_CHREC:
 666       if (CHREC_VARIABLE (chrec) == loop_num)
 667         {
 668           if (right)
 669             component = CHREC_RIGHT (chrec);
 670           else
 671             component = CHREC_LEFT (chrec);
 672
 673           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 674               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 675             return component;
 676
 677           else
 678             return build_polynomial_chrec
 679               (loop_num,
 680                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 681                                             loop_num,
 682                                             right),
 683                component);
 684         }
 685
 686       else if (CHREC_VARIABLE (chrec) < loop_num)
 687         /* There is no evolution part in this loop.  */
 688         return NULL_TREE;
 689
 690       else
 691         return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 692                                             loop_num,
 693                                             right);
 694
 695      default:
 696       if (right)
 697         return NULL_TREE;
 698       else
 699         return chrec;
 700     }
 701 }
 702
 703 /* Returns the evolution part in LOOP_NUM.  Example: the call
 704    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 705    {1, +, 2}_1  */
 706
 707 tree
 708 evolution_part_in_loop_num (tree chrec,
 709                             unsigned loop_num)
 710 {
 711   return chrec_component_in_loop_num (chrec, loop_num, true);
 712 }
 713
 714 /* Returns the initial condition in LOOP_NUM.  Example: the call
 715    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 716    {0, +, 1}_1  */
 717
 718 tree
 719 initial_condition_in_loop_num (tree chrec,
 720                                unsigned loop_num)
 721 {
 722   return chrec_component_in_loop_num (chrec, loop_num, false);
 723 }
 724
 725 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 726    This function is essentially used for setting the evolution to
 727    chrec_dont_know, for example after having determined that it is
 728    impossible to say how many times a loop will execute.  */
 729
 730 tree
 731 reset_evolution_in_loop (unsigned loop_num,
 732                          tree chrec,
 733                          tree new_evol)
 734 {
 735   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 736       && CHREC_VARIABLE (chrec) > loop_num)
 737     {
 738       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 739                                            new_evol);
 740       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 741                                             new_evol);
 742       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
 743                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 744                      left, right);
 745     }
 746
 747   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 748          && CHREC_VARIABLE (chrec) == loop_num)
 749     chrec = CHREC_LEFT (chrec);
 750
 751   return build_polynomial_chrec (loop_num, chrec, new_evol);
 752 }
 753
 754 /* Merges two evolution functions that were found by following two
 755    alternate paths of a conditional expression.  */
 756
 757 tree
 758 chrec_merge (tree chrec1,
 759              tree chrec2)
 760 {
 761   if (chrec1 == chrec_dont_know
 762       || chrec2 == chrec_dont_know)
 763     return chrec_dont_know;
 764
 765   if (chrec1 == chrec_known
 766       || chrec2 == chrec_known)
 767     return chrec_known;
 768
 769   if (chrec1 == chrec_not_analyzed_yet)
 770     return chrec2;
 771   if (chrec2 == chrec_not_analyzed_yet)
 772     return chrec1;
 773
 774   if (operand_equal_p (chrec1, chrec2, 0))
 775     return chrec1;
 776
 777   return chrec_dont_know;
 778 }
 779
 780 \f
 781
 782 /* Observers.  */
 783
 784 /* Helper function for is_multivariate_chrec.  */
 785
 786 static bool
 787 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 788 {
 789   if (chrec == NULL_TREE)
 790     return false;
 791
 792   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 793     {
 794       if (CHREC_VARIABLE (chrec) != rec_var)
 795         return true;
 796       else
 797         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 798                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 799     }
 800   else
 801     return false;
 802 }
 803
 804 /* Determine whether the given chrec is multivariate or not.  */
 805
 806 bool
 807 is_multivariate_chrec (tree chrec)
 808 {
 809   if (chrec == NULL_TREE)
 810     return false;
 811
 812   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 813     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 814                                        CHREC_VARIABLE (chrec))
 815             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 816                                           CHREC_VARIABLE (chrec)));
 817   else
 818     return false;
 819 }
 820
 821 /* Determines whether the chrec contains symbolic names or not.  */
 822
 823 bool
 824 chrec_contains_symbols (tree chrec)
 825 {
 826   if (chrec == NULL_TREE)
 827     return false;
 828
 829   if (TREE_CODE (chrec) == SSA_NAME
 830       || TREE_CODE (chrec) == VAR_DECL
 831       || TREE_CODE (chrec) == PARM_DECL
 832       || TREE_CODE (chrec) == FUNCTION_DECL
 833       || TREE_CODE (chrec) == LABEL_DECL
 834       || TREE_CODE (chrec) == RESULT_DECL
 835       || TREE_CODE (chrec) == FIELD_DECL)
 836     return true;
 837
 838   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 839     {
 840     case 3:
 841       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 842         return true;
 843
 844     case 2:
 845       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 846         return true;
 847
 848     case 1:
 849       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 850         return true;
 851
 852     default:
 853       return false;
 854     }
 855 }
 856
 857 /* Determines whether the chrec contains undetermined coefficients.  */
 858
 859 bool
 860 chrec_contains_undetermined (tree chrec)
 861 {
 862   if (chrec == chrec_dont_know
 863       || chrec == chrec_not_analyzed_yet
 864       || chrec == NULL_TREE)
 865     return true;
 866
 867   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 868     {
 869     case 3:
 870       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 871         return true;
 872
 873     case 2:
 874       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 875         return true;
 876
 877     case 1:
 878       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 879         return true;
 880
 881     default:
 882       return false;
 883     }
 884 }
 885
 886 /* Determines whether the tree EXPR contains chrecs, and increment
 887    SIZE if it is not a NULL pointer by an estimation of the depth of
 888    the tree.  */
 889
 890 bool
 891 tree_contains_chrecs (tree expr, int *size)
 892 {
 893   if (expr == NULL_TREE)
 894     return false;
 895
 896   if (size)
 897     (*size)++;
 898
 899   if (tree_is_chrec (expr))
 900     return true;
 901
 902   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 903     {
 904     case 3:
 905       if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
 906         return true;
 907
 908     case 2:
 909       if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
 910         return true;
 911
 912     case 1:
 913       if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
 914         return true;
 915
 916     default:
 917       return false;
 918     }
 919 }
 920
 921 /* Recursive helper function.  */
 922
 923 static bool
 924 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 925 {
 926   if (evolution_function_is_constant_p (chrec))
 927     return true;
 928
 929   if (TREE_CODE (chrec) == SSA_NAME
 930       && expr_invariant_in_loop_p (current_loops->parray[loopnum],
 931                                    chrec))
 932     return true;
 933
 934   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 935       && CHREC_VARIABLE (chrec) == (unsigned) loopnum)
 936     return false;
 937
 938   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 939     {
 940     case 2:
 941       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
 942                                                   loopnum))
 943         return false;
 944
 945     case 1:
 946       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
 947                                                   loopnum))
 948         return false;
 949       return true;
 950
 951     default:
 952       return false;
 953     }
 954
 955   return false;
 956 }
 957
 958 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
 959
 960 bool
 961 evolution_function_is_invariant_p (tree chrec, int loopnum)
 962 {
 963   if (evolution_function_is_constant_p (chrec))
 964     return true;
 965
 966   if (current_loops != NULL)
 967     return evolution_function_is_invariant_rec_p (chrec, loopnum);
 968
 969   return false;
 970 }
 971
 972 /* Determine whether the given tree is an affine multivariate
 973    evolution.  */
 974
 975 bool
 976 evolution_function_is_affine_multivariate_p (tree chrec)
 977 {
 978   if (chrec == NULL_TREE)
 979     return false;
 980
 981   switch (TREE_CODE (chrec))
 982     {
 983     case POLYNOMIAL_CHREC:
 984       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 985         {
 986           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 987             return true;
 988           else
 989             {
 990               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
 991                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
 992                      != CHREC_VARIABLE (chrec)
 993                   && evolution_function_is_affine_multivariate_p
 994                   (CHREC_RIGHT (chrec)))
 995                 return true;
 996               else
 997                 return false;
 998             }
 999         }
1000       else
1001         {
1002           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1003               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1004               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1005               && evolution_function_is_affine_multivariate_p
1006               (CHREC_LEFT (chrec)))
1007             return true;
1008           else
1009             return false;
1010         }
1011
1012     default:
1013       return false;
1014     }
1015 }
1016
1017 /* Determine whether the given tree is a function in zero or one
1018    variables.  */
1019
1020 bool
1021 evolution_function_is_univariate_p (tree chrec)
1022 {
1023   if (chrec == NULL_TREE)
1024     return true;
1025
1026   switch (TREE_CODE (chrec))
1027     {
1028     case POLYNOMIAL_CHREC:
1029       switch (TREE_CODE (CHREC_LEFT (chrec)))
1030         {
1031         case POLYNOMIAL_CHREC:
1032           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1033             return false;
1034           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1035             return false;
1036           break;
1037
1038         default:
1039           break;
1040         }
1041
1042       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1043         {
1044         case POLYNOMIAL_CHREC:
1045           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1046             return false;
1047           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1048             return false;
1049           break;
1050
1051         default:
1052           break;
1053         }
1054
1055     default:
1056       return true;
1057     }
1058 }
1059
1060 /* Returns the number of variables of CHREC.  Example: the call
1061    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1062
1063 unsigned
1064 nb_vars_in_chrec (tree chrec)
1065 {
1066   if (chrec == NULL_TREE)
1067     return 0;
1068
1069   switch (TREE_CODE (chrec))
1070     {
1071     case POLYNOMIAL_CHREC:
1072       return 1 + nb_vars_in_chrec
1073         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1074
1075     default:
1076       return 0;
1077     }
1078 }
1079
1080 \f
1081
1082 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1083    which the CHREC is built, it sets AT_STMT to the statement that
1084    contains the definition of the analyzed variable, otherwise the
1085    conversion is less accurate: the information is used for
1086    determining a more accurate estimation of the number of iterations.
1087    By default AT_STMT could be safely set to NULL_TREE.
1088
1089    The following rule is always true: TREE_TYPE (chrec) ==
1090    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1091    An example of what could happen when adding two chrecs and the type
1092    of the CHREC_RIGHT is different than CHREC_LEFT is:
1093
1094    {(uint) 0, +, (uchar) 10} +
1095    {(uint) 0, +, (uchar) 250}
1096
1097    that would produce a wrong result if CHREC_RIGHT is not (uint):
1098
1099    {(uint) 0, +, (uchar) 4}
1100
1101    instead of
1102
1103    {(uint) 0, +, (uint) 260}
1104 */
1105
1106 tree
1107 chrec_convert (tree type, tree chrec, tree at_stmt)
1108 {
1109   tree ct, res;
1110
1111   if (automatically_generated_chrec_p (chrec))
1112     return chrec;
1113
1114   ct = chrec_type (chrec);
1115   if (ct == type)
1116     return chrec;
1117
1118   if (evolution_function_is_affine_p (chrec))
1119     {
1120       tree step;
1121       bool dummy;
1122
1123       /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
1124          when it is not possible to prove that the scev does not wrap.
1125          See PR22236, where a sequence 1, 2, ..., 255 has to be
1126          converted to signed char, but this would wrap:
1127          1, 2, ..., 127, -128, ...  The result should not be
1128          {(schar)1, +, (schar)1}_x, but instead, we should keep the
1129          conversion: (schar) {(uchar)1, +, (uchar)1}_x.  */
1130       if (scev_probably_wraps_p (type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
1131                                  at_stmt,
1132                                  current_loops->parray[CHREC_VARIABLE (chrec)],
1133                                  &dummy, &dummy))
1134         return fold_convert (type, chrec);
1135
1136       step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)], type,
1137                            CHREC_LEFT (chrec), CHREC_RIGHT (chrec), at_stmt);
1138       if (!step)
1139         return fold_convert (type, chrec);
1140
1141       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1142                                      chrec_convert (type, CHREC_LEFT (chrec),
1143                                                     at_stmt),
1144                                      step);
1145     }
1146
1147   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1148     return chrec_dont_know;
1149
1150   res = fold_convert (type, chrec);
1151
1152   /* Don't propagate overflows.  */
1153   if (CONSTANT_CLASS_P (res))
1154     {
1155       TREE_CONSTANT_OVERFLOW (res) = 0;
1156       TREE_OVERFLOW (res) = 0;
1157     }
1158
1159   /* But reject constants that don't fit in their type after conversion.
1160      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1161      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1162      and can cause problems later when computing niters of loops.  Note
1163      that we don't do the check before converting because we don't want
1164      to reject conversions of negative chrecs to unsigned types.  */
1165   if (TREE_CODE (res) == INTEGER_CST
1166       && TREE_CODE (type) == INTEGER_TYPE
1167       && !int_fits_type_p (res, type))
1168     res = chrec_dont_know;
1169
1170   return res;
1171 }
1172
1173 /* Returns the type of the chrec.  */
1174
1175 tree
1176 chrec_type (tree chrec)
1177 {
1178   if (automatically_generated_chrec_p (chrec))
1179     return NULL_TREE;
1180
1181   return TREE_TYPE (chrec);
1182 }