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 in LOOP_NUM.  Example: the call
 587    get_evolution_in_loop (1, {{0, +, 1}_1, +, 2}_1) returns
 588    {1, +, 2}_1  */
 589
 590 tree
 591 evolution_part_in_loop_num (tree chrec,
 592                             unsigned loop_num)
 593 {
 594   if (automatically_generated_chrec_p (chrec))
 595     return chrec;
 596
 597   switch (TREE_CODE (chrec))
 598     {
 599     case POLYNOMIAL_CHREC:
 600       if (CHREC_VARIABLE (chrec) == loop_num)
 601         {
 602           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 603               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 604             return CHREC_RIGHT (chrec);
 605
 606           else
 607             return build_polynomial_chrec
 608               (loop_num,
 609                evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num),
 610                CHREC_RIGHT (chrec));
 611         }
 612
 613       else if (CHREC_VARIABLE (chrec) < loop_num)
 614         /* There is no evolution part in this loop.  */
 615         return NULL_TREE;
 616
 617       else
 618         return evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num);
 619
 620     default:
 621       return NULL_TREE;
 622     }
 623 }
 624
 625 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 626    This function is essentially used for setting the evolution to
 627    chrec_dont_know, for example after having determined that it is
 628    impossible to say how many times a loop will execute.  */
 629
 630 tree
 631 reset_evolution_in_loop (unsigned loop_num,
 632                          tree chrec,
 633                          tree new_evol)
 634 {
 635   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 636       && CHREC_VARIABLE (chrec) > loop_num)
 637     return build
 638       (TREE_CODE (chrec),
 639        build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 640        reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
 641        reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
 642
 643   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 644          && CHREC_VARIABLE (chrec) == loop_num)
 645     chrec = CHREC_LEFT (chrec);
 646
 647   return build_polynomial_chrec (loop_num, chrec, new_evol);
 648 }
 649
 650 /* Merges two evolution functions that were found by following two
 651    alternate paths of a conditional expression.  */
 652
 653 tree
 654 chrec_merge (tree chrec1,
 655              tree chrec2)
 656 {
 657   if (chrec1 == chrec_dont_know
 658       || chrec2 == chrec_dont_know)
 659     return chrec_dont_know;
 660
 661   if (chrec1 == chrec_known
 662       || chrec2 == chrec_known)
 663     return chrec_known;
 664
 665   if (chrec1 == chrec_not_analyzed_yet)
 666     return chrec2;
 667   if (chrec2 == chrec_not_analyzed_yet)
 668     return chrec1;
 669
 670   if (operand_equal_p (chrec1, chrec2, 0))
 671     return chrec1;
 672
 673   return chrec_dont_know;
 674 }
 675
 676 \f
 677
 678 /* Observers.  */
 679
 680 /* Helper function for is_multivariate_chrec.  */
 681
 682 static bool
 683 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 684 {
 685   if (chrec == NULL_TREE)
 686     return false;
 687
 688   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 689     {
 690       if (CHREC_VARIABLE (chrec) != rec_var)
 691         return true;
 692       else
 693         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 694                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 695     }
 696   else
 697     return false;
 698 }
 699
 700 /* Determine whether the given chrec is multivariate or not.  */
 701
 702 bool
 703 is_multivariate_chrec (tree chrec)
 704 {
 705   if (chrec == NULL_TREE)
 706     return false;
 707
 708   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 709     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 710                                        CHREC_VARIABLE (chrec))
 711             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 712                                           CHREC_VARIABLE (chrec)));
 713   else
 714     return false;
 715 }
 716
 717 /* Determines whether the chrec contains symbolic names or not.  */
 718
 719 bool
 720 chrec_contains_symbols (tree chrec)
 721 {
 722   if (chrec == NULL_TREE)
 723     return false;
 724
 725   if (TREE_CODE (chrec) == SSA_NAME
 726       || TREE_CODE (chrec) == VAR_DECL
 727       || TREE_CODE (chrec) == PARM_DECL
 728       || TREE_CODE (chrec) == FUNCTION_DECL
 729       || TREE_CODE (chrec) == LABEL_DECL
 730       || TREE_CODE (chrec) == RESULT_DECL
 731       || TREE_CODE (chrec) == FIELD_DECL)
 732     return true;
 733
 734   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 735     {
 736     case 3:
 737       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 738         return true;
 739
 740     case 2:
 741       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 742         return true;
 743
 744     case 1:
 745       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 746         return true;
 747
 748     default:
 749       return false;
 750     }
 751 }
 752
 753 /* Determines whether the chrec contains undetermined coefficients.  */
 754
 755 bool
 756 chrec_contains_undetermined (tree chrec)
 757 {
 758   if (chrec == chrec_dont_know
 759       || chrec == chrec_not_analyzed_yet
 760       || chrec == NULL_TREE)
 761     return true;
 762
 763   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 764     {
 765     case 3:
 766       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 767         return true;
 768
 769     case 2:
 770       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 771         return true;
 772
 773     case 1:
 774       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 775         return true;
 776
 777     default:
 778       return false;
 779     }
 780 }
 781
 782 /* Determines whether the tree EXPR contains chrecs.  */
 783
 784 bool
 785 tree_contains_chrecs (tree expr)
 786 {
 787   if (expr == NULL_TREE)
 788     return false;
 789
 790   if (tree_is_chrec (expr))
 791     return true;
 792
 793   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 794     {
 795     case 3:
 796       if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
 797         return true;
 798
 799     case 2:
 800       if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
 801         return true;
 802
 803     case 1:
 804       if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
 805         return true;
 806
 807     default:
 808       return false;
 809     }
 810 }
 811
 812 /* Determine whether the given tree is an affine multivariate
 813    evolution.  */
 814
 815 bool
 816 evolution_function_is_affine_multivariate_p (tree chrec)
 817 {
 818   if (chrec == NULL_TREE)
 819     return false;
 820
 821   switch (TREE_CODE (chrec))
 822     {
 823     case POLYNOMIAL_CHREC:
 824       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 825         {
 826           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 827             return true;
 828           else
 829             {
 830               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
 831                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
 832                      != CHREC_VARIABLE (chrec)
 833                   && evolution_function_is_affine_multivariate_p
 834                   (CHREC_RIGHT (chrec)))
 835                 return true;
 836               else
 837                 return false;
 838             }
 839         }
 840       else
 841         {
 842           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
 843               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
 844               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
 845               && evolution_function_is_affine_multivariate_p
 846               (CHREC_LEFT (chrec)))
 847             return true;
 848           else
 849             return false;
 850         }
 851
 852     default:
 853       return false;
 854     }
 855 }
 856
 857 /* Determine whether the given tree is a function in zero or one
 858    variables.  */
 859
 860 bool
 861 evolution_function_is_univariate_p (tree chrec)
 862 {
 863   if (chrec == NULL_TREE)
 864     return true;
 865
 866   switch (TREE_CODE (chrec))
 867     {
 868     case POLYNOMIAL_CHREC:
 869       switch (TREE_CODE (CHREC_LEFT (chrec)))
 870         {
 871         case POLYNOMIAL_CHREC:
 872           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
 873             return false;
 874           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
 875             return false;
 876           break;
 877
 878         default:
 879           break;
 880         }
 881
 882       switch (TREE_CODE (CHREC_RIGHT (chrec)))
 883         {
 884         case POLYNOMIAL_CHREC:
 885           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
 886             return false;
 887           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
 888             return false;
 889           break;
 890
 891         default:
 892           break;
 893         }
 894
 895     default:
 896       return true;
 897     }
 898 }
 899
 900 \f
 901
 902 /* Convert the initial condition of chrec to type.  */
 903
 904 tree
 905 chrec_convert (tree type,
 906                tree chrec)
 907 {
 908   tree ct;
 909
 910   if (automatically_generated_chrec_p (chrec))
 911     return chrec;
 912
 913   ct = chrec_type (chrec);
 914   if (ct == type)
 915     return chrec;
 916
 917   if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
 918     return count_ev_in_wider_type (type, chrec);
 919
 920   switch (TREE_CODE (chrec))
 921     {
 922     case POLYNOMIAL_CHREC:
 923       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
 924                                      chrec_convert (type,
 925                                                     CHREC_LEFT (chrec)),
 926                                      chrec_convert (type,
 927                                                     CHREC_RIGHT (chrec)));
 928
 929     default:
 930       {
 931         tree res = convert (type, chrec);
 932
 933         /* Don't propagate overflows.  */
 934         TREE_OVERFLOW (res) = 0;
 935         if (TREE_CODE_CLASS (TREE_CODE (res)) == 'c')
 936           TREE_CONSTANT_OVERFLOW (res) = 0;
 937         return res;
 938       }
 939     }
 940 }
 941
 942 /* Returns the type of the chrec.  */
 943
 944 tree
 945 chrec_type (tree chrec)
 946 {
 947   if (automatically_generated_chrec_p (chrec))
 948     return NULL_TREE;
 949
 950   return TREE_TYPE (chrec);
 951 }
 952
 953 extern void initialize_scalar_evolutions_analyzer (void);
 954
 955 /* Initializer.  */
 956
 957 void
 958 initialize_scalar_evolutions_analyzer (void)
 959 {
 960   /* The elements below are unique.  */
 961   if (chrec_dont_know == NULL_TREE)
 962     {
 963       chrec_not_analyzed_yet = NULL_TREE;
 964       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
 965       chrec_known = make_node (SCEV_KNOWN);
 966       TREE_TYPE (chrec_dont_know) = NULL_TREE;
 967       TREE_TYPE (chrec_known) = NULL_TREE;
 968     }
 969 }