gcc/tree-chrec.c

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