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 "errors.h"
  32 #include "ggc.h"
  33 #include "tree.h"
  34 #include "diagnostic.h"
  35 #include "varray.h"
  36 #include "tree-chrec.h"
  37 #include "tree-pass.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           if (tree_contains_chrecs (op0)
 290               || tree_contains_chrecs (op1))
 291             return build (code, type, op0, op1);
 292           else
 293             return fold (build (code, type, op0, op1));
 294         }
 295     }
 296 }
 297
 298 /* Fold the addition of two chrecs.  */
 299
 300 tree
 301 chrec_fold_plus (tree type,
 302                  tree op0,
 303                  tree op1)
 304 {
 305   if (integer_zerop (op0))
 306     return op1;
 307   if (integer_zerop (op1))
 308     return op0;
 309
 310   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
 311 }
 312
 313 /* Fold the subtraction of two chrecs.  */
 314
 315 tree
 316 chrec_fold_minus (tree type,
 317                   tree op0,
 318                   tree op1)
 319 {
 320   if (integer_zerop (op1))
 321     return op0;
 322
 323   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
 324 }
 325
 326 /* Fold the multiplication of two chrecs.  */
 327
 328 tree
 329 chrec_fold_multiply (tree type,
 330                      tree op0,
 331                      tree op1)
 332 {
 333   if (automatically_generated_chrec_p (op0)
 334       || automatically_generated_chrec_p (op1))
 335     return chrec_fold_automatically_generated_operands (op0, op1);
 336
 337   switch (TREE_CODE (op0))
 338     {
 339     case POLYNOMIAL_CHREC:
 340       switch (TREE_CODE (op1))
 341         {
 342         case POLYNOMIAL_CHREC:
 343           return chrec_fold_multiply_poly_poly (type, op0, op1);
 344
 345         default:
 346           if (integer_onep (op1))
 347             return op0;
 348           if (integer_zerop (op1))
 349             return build_int_cst_type (type, 0);
 350
 351           return build_polynomial_chrec
 352             (CHREC_VARIABLE (op0),
 353              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
 354              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 355         }
 356
 357     default:
 358       if (integer_onep (op0))
 359         return op1;
 360
 361       if (integer_zerop (op0))
 362         return build_int_cst_type (type, 0);
 363
 364       switch (TREE_CODE (op1))
 365         {
 366         case POLYNOMIAL_CHREC:
 367           return build_polynomial_chrec
 368             (CHREC_VARIABLE (op1),
 369              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 370              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 371
 372         default:
 373           if (integer_onep (op1))
 374             return op0;
 375           if (integer_zerop (op1))
 376             return build_int_cst_type (type, 0);
 377           return fold (build (MULT_EXPR, type, op0, op1));
 378         }
 379     }
 380 }
 381
 382 \f
 383
 384 /* Operations.  */
 385
 386 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
 387    calculation overflows, otherwise return C(n,k) with type TYPE.  */
 388
 389 static tree
 390 tree_fold_binomial (tree type, tree n, unsigned int k)
 391 {
 392   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
 393   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
 394   unsigned int i;
 395   tree res;
 396
 397   /* Handle the most frequent cases.  */
 398   if (k == 0)
 399     return build_int_cst (type, 1);
 400   if (k == 1)
 401     return fold_convert (type, n);
 402
 403   /* Check that k <= n.  */
 404   if (TREE_INT_CST_HIGH (n) == 0
 405       && TREE_INT_CST_LOW (n) < k)
 406     return NULL_TREE;
 407
 408   /* Numerator = n.  */
 409   lnum = TREE_INT_CST_LOW (n);
 410   hnum = TREE_INT_CST_HIGH (n);
 411
 412   /* Denominator = 2.  */
 413   ldenom = 2;
 414   hdenom = 0;
 415
 416   /* Index = Numerator-1.  */
 417   if (lnum == 0)
 418     {
 419       hidx = hnum - 1;
 420       lidx = ~ (unsigned HOST_WIDE_INT) 0;
 421     }
 422   else
 423     {
 424       hidx = hnum;
 425       lidx = lnum - 1;
 426     }
 427
 428   /* Numerator = Numerator*Index = n*(n-1).  */
 429   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 430     return NULL_TREE;
 431
 432   for (i = 3; i <= k; i++)
 433     {
 434       /* Index--.  */
 435       if (lidx == 0)
 436         {
 437           hidx--;
 438           lidx = ~ (unsigned HOST_WIDE_INT) 0;
 439         }
 440       else
 441         lidx--;
 442
 443       /* Numerator *= Index.  */
 444       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 445         return NULL_TREE;
 446
 447       /* Denominator *= i.  */
 448       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
 449     }
 450
 451   /* Result = Numerator / Denominator.  */
 452   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
 453                         &lres, &hres, &ldum, &hdum);
 454
 455   res = build_int_cst_wide (type, lres, hres);
 456   return int_fits_type_p (res, type) ? res : NULL_TREE;
 457 }
 458
 459 /* Helper function.  Use the Newton's interpolating formula for
 460    evaluating the value of the evolution function.  */
 461
 462 static tree
 463 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 464 {
 465   tree arg0, arg1, binomial_n_k;
 466   tree type = TREE_TYPE (chrec);
 467
 468   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 469          && CHREC_VARIABLE (chrec) > var)
 470     chrec = CHREC_LEFT (chrec);
 471
 472   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 473       && CHREC_VARIABLE (chrec) == var)
 474     {
 475       arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
 476       if (arg0 == chrec_dont_know)
 477         return chrec_dont_know;
 478       binomial_n_k = tree_fold_binomial (type, n, k);
 479       if (!binomial_n_k)
 480         return chrec_dont_know;
 481       arg1 = fold (build2 (MULT_EXPR, type,
 482                            CHREC_LEFT (chrec), binomial_n_k));
 483       return chrec_fold_plus (type, arg0, arg1);
 484     }
 485
 486   binomial_n_k = tree_fold_binomial (type, n, k);
 487   if (!binomial_n_k)
 488     return chrec_dont_know;
 489
 490   return fold (build2 (MULT_EXPR, type, chrec, binomial_n_k));
 491 }
 492
 493 /* Evaluates "CHREC (X)" when the varying variable is VAR.
 494    Example:  Given the following parameters,
 495
 496    var = 1
 497    chrec = {3, +, 4}_1
 498    x = 10
 499
 500    The result is given by the Newton's interpolating formula:
 501    3 * \binom{10}{0} + 4 * \binom{10}{1}.
 502 */
 503
 504 tree
 505 chrec_apply (unsigned var,
 506              tree chrec,
 507              tree x)
 508 {
 509   tree type = chrec_type (chrec);
 510   tree res = chrec_dont_know;
 511
 512   if (automatically_generated_chrec_p (chrec)
 513       || automatically_generated_chrec_p (x)
 514
 515       /* When the symbols are defined in an outer loop, it is possible
 516          to symbolically compute the apply, since the symbols are
 517          constants with respect to the varying loop.  */
 518       || chrec_contains_symbols_defined_in_loop (chrec, var)
 519       || chrec_contains_symbols (x))
 520     return chrec_dont_know;
 521
 522   if (dump_file && (dump_flags & TDF_DETAILS))
 523     fprintf (dump_file, "(chrec_apply \n");
 524
 525   if (evolution_function_is_affine_p (chrec))
 526     {
 527       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 528       if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
 529           && integer_zerop (CHREC_LEFT (chrec)))
 530         res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
 531
 532       else
 533         res = chrec_fold_plus (type, CHREC_LEFT (chrec),
 534                                chrec_fold_multiply (type,
 535                                                     CHREC_RIGHT (chrec), x));
 536     }
 537
 538   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 539     res = chrec;
 540
 541   else if (TREE_CODE (x) == INTEGER_CST
 542            && tree_int_cst_sgn (x) == 1)
 543     /* testsuite/.../ssa-chrec-38.c.  */
 544     res = chrec_evaluate (var, chrec, x, 0);
 545
 546   else
 547     res = chrec_dont_know;
 548
 549   if (dump_file && (dump_flags & TDF_DETAILS))
 550     {
 551       fprintf (dump_file, "  (varying_loop = %d\n", var);
 552       fprintf (dump_file, ")\n  (chrec = ");
 553       print_generic_expr (dump_file, chrec, 0);
 554       fprintf (dump_file, ")\n  (x = ");
 555       print_generic_expr (dump_file, x, 0);
 556       fprintf (dump_file, ")\n  (res = ");
 557       print_generic_expr (dump_file, res, 0);
 558       fprintf (dump_file, "))\n");
 559     }
 560
 561   return res;
 562 }
 563
 564 /* Replaces the initial condition in CHREC with INIT_COND.  */
 565
 566 tree
 567 chrec_replace_initial_condition (tree chrec,
 568                                  tree init_cond)
 569 {
 570   if (automatically_generated_chrec_p (chrec))
 571     return chrec;
 572
 573   switch (TREE_CODE (chrec))
 574     {
 575     case POLYNOMIAL_CHREC:
 576       return build_polynomial_chrec
 577         (CHREC_VARIABLE (chrec),
 578          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 579          CHREC_RIGHT (chrec));
 580
 581     default:
 582       return init_cond;
 583     }
 584 }
 585
 586 /* Returns the initial condition of a given CHREC.  */
 587
 588 tree
 589 initial_condition (tree chrec)
 590 {
 591   if (automatically_generated_chrec_p (chrec))
 592     return chrec;
 593
 594   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 595     return initial_condition (CHREC_LEFT (chrec));
 596   else
 597     return chrec;
 598 }
 599
 600 /* Returns a univariate function that represents the evolution in
 601    LOOP_NUM.  Mask the evolution of any other loop.  */
 602
 603 tree
 604 hide_evolution_in_other_loops_than_loop (tree chrec,
 605                                          unsigned loop_num)
 606 {
 607   if (automatically_generated_chrec_p (chrec))
 608     return chrec;
 609
 610   switch (TREE_CODE (chrec))
 611     {
 612     case POLYNOMIAL_CHREC:
 613       if (CHREC_VARIABLE (chrec) == loop_num)
 614         return build_polynomial_chrec
 615           (loop_num,
 616            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 617                                                     loop_num),
 618            CHREC_RIGHT (chrec));
 619
 620       else if (CHREC_VARIABLE (chrec) < loop_num)
 621         /* There is no evolution in this loop.  */
 622         return initial_condition (chrec);
 623
 624       else
 625         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 626                                                         loop_num);
 627
 628     default:
 629       return chrec;
 630     }
 631 }
 632
 633 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 634    true, otherwise returns the initial condition in LOOP_NUM.  */
 635
 636 static tree
 637 chrec_component_in_loop_num (tree chrec,
 638                              unsigned loop_num,
 639                              bool right)
 640 {
 641   tree component;
 642
 643   if (automatically_generated_chrec_p (chrec))
 644     return chrec;
 645
 646   switch (TREE_CODE (chrec))
 647     {
 648     case POLYNOMIAL_CHREC:
 649       if (CHREC_VARIABLE (chrec) == loop_num)
 650         {
 651           if (right)
 652             component = CHREC_RIGHT (chrec);
 653           else
 654             component = CHREC_LEFT (chrec);
 655
 656           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 657               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 658             return component;
 659
 660           else
 661             return build_polynomial_chrec
 662               (loop_num,
 663                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 664                                             loop_num,
 665                                             right),
 666                component);
 667         }
 668
 669       else if (CHREC_VARIABLE (chrec) < loop_num)
 670         /* There is no evolution part in this loop.  */
 671         return NULL_TREE;
 672
 673       else
 674         return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 675                                             loop_num,
 676                                             right);
 677
 678      default:
 679       if (right)
 680         return NULL_TREE;
 681       else
 682         return chrec;
 683     }
 684 }
 685
 686 /* Returns the evolution part in LOOP_NUM.  Example: the call
 687    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 688    {1, +, 2}_1  */
 689
 690 tree
 691 evolution_part_in_loop_num (tree chrec,
 692                             unsigned loop_num)
 693 {
 694   return chrec_component_in_loop_num (chrec, loop_num, true);
 695 }
 696
 697 /* Returns the initial condition in LOOP_NUM.  Example: the call
 698    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 699    {0, +, 1}_1  */
 700
 701 tree
 702 initial_condition_in_loop_num (tree chrec,
 703                                unsigned loop_num)
 704 {
 705   return chrec_component_in_loop_num (chrec, loop_num, false);
 706 }
 707
 708 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 709    This function is essentially used for setting the evolution to
 710    chrec_dont_know, for example after having determined that it is
 711    impossible to say how many times a loop will execute.  */
 712
 713 tree
 714 reset_evolution_in_loop (unsigned loop_num,
 715                          tree chrec,
 716                          tree new_evol)
 717 {
 718   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 719       && CHREC_VARIABLE (chrec) > loop_num)
 720     return build
 721       (TREE_CODE (chrec),
 722        build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 723        reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
 724        reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
 725
 726   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 727          && CHREC_VARIABLE (chrec) == loop_num)
 728     chrec = CHREC_LEFT (chrec);
 729
 730   return build_polynomial_chrec (loop_num, chrec, new_evol);
 731 }
 732
 733 /* Merges two evolution functions that were found by following two
 734    alternate paths of a conditional expression.  */
 735
 736 tree
 737 chrec_merge (tree chrec1,
 738              tree chrec2)
 739 {
 740   if (chrec1 == chrec_dont_know
 741       || chrec2 == chrec_dont_know)
 742     return chrec_dont_know;
 743
 744   if (chrec1 == chrec_known
 745       || chrec2 == chrec_known)
 746     return chrec_known;
 747
 748   if (chrec1 == chrec_not_analyzed_yet)
 749     return chrec2;
 750   if (chrec2 == chrec_not_analyzed_yet)
 751     return chrec1;
 752
 753   if (operand_equal_p (chrec1, chrec2, 0))
 754     return chrec1;
 755
 756   return chrec_dont_know;
 757 }
 758
 759 \f
 760
 761 /* Observers.  */
 762
 763 /* Helper function for is_multivariate_chrec.  */
 764
 765 static bool
 766 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 767 {
 768   if (chrec == NULL_TREE)
 769     return false;
 770
 771   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 772     {
 773       if (CHREC_VARIABLE (chrec) != rec_var)
 774         return true;
 775       else
 776         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 777                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 778     }
 779   else
 780     return false;
 781 }
 782
 783 /* Determine whether the given chrec is multivariate or not.  */
 784
 785 bool
 786 is_multivariate_chrec (tree chrec)
 787 {
 788   if (chrec == NULL_TREE)
 789     return false;
 790
 791   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 792     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 793                                        CHREC_VARIABLE (chrec))
 794             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 795                                           CHREC_VARIABLE (chrec)));
 796   else
 797     return false;
 798 }
 799
 800 /* Determines whether the chrec contains symbolic names or not.  */
 801
 802 bool
 803 chrec_contains_symbols (tree chrec)
 804 {
 805   if (chrec == NULL_TREE)
 806     return false;
 807
 808   if (TREE_CODE (chrec) == SSA_NAME
 809       || TREE_CODE (chrec) == VAR_DECL
 810       || TREE_CODE (chrec) == PARM_DECL
 811       || TREE_CODE (chrec) == FUNCTION_DECL
 812       || TREE_CODE (chrec) == LABEL_DECL
 813       || TREE_CODE (chrec) == RESULT_DECL
 814       || TREE_CODE (chrec) == FIELD_DECL)
 815     return true;
 816
 817   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 818     {
 819     case 3:
 820       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 821         return true;
 822
 823     case 2:
 824       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 825         return true;
 826
 827     case 1:
 828       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 829         return true;
 830
 831     default:
 832       return false;
 833     }
 834 }
 835
 836 /* Determines whether the chrec contains undetermined coefficients.  */
 837
 838 bool
 839 chrec_contains_undetermined (tree chrec)
 840 {
 841   if (chrec == chrec_dont_know
 842       || chrec == chrec_not_analyzed_yet
 843       || chrec == NULL_TREE)
 844     return true;
 845
 846   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 847     {
 848     case 3:
 849       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 850         return true;
 851
 852     case 2:
 853       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 854         return true;
 855
 856     case 1:
 857       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 858         return true;
 859
 860     default:
 861       return false;
 862     }
 863 }
 864
 865 /* Determines whether the tree EXPR contains chrecs.  */
 866
 867 bool
 868 tree_contains_chrecs (tree expr)
 869 {
 870   if (expr == NULL_TREE)
 871     return false;
 872
 873   if (tree_is_chrec (expr))
 874     return true;
 875
 876   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 877     {
 878     case 3:
 879       if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
 880         return true;
 881
 882     case 2:
 883       if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
 884         return true;
 885
 886     case 1:
 887       if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
 888         return true;
 889
 890     default:
 891       return false;
 892     }
 893 }
 894
 895 /* Determine whether the given tree is an affine multivariate
 896    evolution.  */
 897
 898 bool
 899 evolution_function_is_affine_multivariate_p (tree chrec)
 900 {
 901   if (chrec == NULL_TREE)
 902     return false;
 903
 904   switch (TREE_CODE (chrec))
 905     {
 906     case POLYNOMIAL_CHREC:
 907       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 908         {
 909           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 910             return true;
 911           else
 912             {
 913               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
 914                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
 915                      != CHREC_VARIABLE (chrec)
 916                   && evolution_function_is_affine_multivariate_p
 917                   (CHREC_RIGHT (chrec)))
 918                 return true;
 919               else
 920                 return false;
 921             }
 922         }
 923       else
 924         {
 925           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
 926               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
 927               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
 928               && evolution_function_is_affine_multivariate_p
 929               (CHREC_LEFT (chrec)))
 930             return true;
 931           else
 932             return false;
 933         }
 934
 935     default:
 936       return false;
 937     }
 938 }
 939
 940 /* Determine whether the given tree is a function in zero or one
 941    variables.  */
 942
 943 bool
 944 evolution_function_is_univariate_p (tree chrec)
 945 {
 946   if (chrec == NULL_TREE)
 947     return true;
 948
 949   switch (TREE_CODE (chrec))
 950     {
 951     case POLYNOMIAL_CHREC:
 952       switch (TREE_CODE (CHREC_LEFT (chrec)))
 953         {
 954         case POLYNOMIAL_CHREC:
 955           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
 956             return false;
 957           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
 958             return false;
 959           break;
 960
 961         default:
 962           break;
 963         }
 964
 965       switch (TREE_CODE (CHREC_RIGHT (chrec)))
 966         {
 967         case POLYNOMIAL_CHREC:
 968           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
 969             return false;
 970           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
 971             return false;
 972           break;
 973
 974         default:
 975           break;
 976         }
 977
 978     default:
 979       return true;
 980     }
 981 }
 982
 983 /* Returns the number of variables of CHREC.  Example: the call
 984    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
 985
 986 unsigned
 987 nb_vars_in_chrec (tree chrec)
 988 {
 989   if (chrec == NULL_TREE)
 990     return 0;
 991
 992   switch (TREE_CODE (chrec))
 993     {
 994     case POLYNOMIAL_CHREC:
 995       return 1 + nb_vars_in_chrec
 996         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
 997
 998     default:
 999       return 0;
1000     }
1001 }
1002
1003 \f
1004
1005 /* Convert the initial condition of chrec to type.  */
1006
1007 tree
1008 chrec_convert (tree type,
1009                tree chrec)
1010 {
1011   tree ct;
1012
1013   if (automatically_generated_chrec_p (chrec))
1014     return chrec;
1015
1016   ct = chrec_type (chrec);
1017   if (ct == type)
1018     return chrec;
1019
1020   if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
1021     return count_ev_in_wider_type (type, chrec);
1022
1023   switch (TREE_CODE (chrec))
1024     {
1025     case POLYNOMIAL_CHREC:
1026       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1027                                      chrec_convert (type,
1028                                                     CHREC_LEFT (chrec)),
1029                                      chrec_convert (type,
1030                                                     CHREC_RIGHT (chrec)));
1031
1032     default:
1033       {
1034         tree res = fold_convert (type, chrec);
1035
1036         /* Don't propagate overflows.  */
1037         TREE_OVERFLOW (res) = 0;
1038         if (CONSTANT_CLASS_P (res))
1039           TREE_CONSTANT_OVERFLOW (res) = 0;
1040         return res;
1041       }
1042     }
1043 }
1044
1045 /* Returns the type of the chrec.  */
1046
1047 tree
1048 chrec_type (tree chrec)
1049 {
1050   if (automatically_generated_chrec_p (chrec))
1051     return NULL_TREE;
1052
1053   return TREE_TYPE (chrec);
1054 }