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