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