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