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 #if defined ENABLE_CHECKING
  60   if (poly == NULL_TREE
  61       || cst == NULL_TREE
  62       || TREE_CODE (poly) != POLYNOMIAL_CHREC
  63       || is_not_constant_evolution (cst))
  64     abort ();
  65 #endif
  66
  67   switch (code)
  68     {
  69     case PLUS_EXPR:
  70       return build_polynomial_chrec
  71         (CHREC_VARIABLE (poly),
  72          chrec_fold_plus (type, CHREC_LEFT (poly), cst),
  73          CHREC_RIGHT (poly));
  74
  75     case MINUS_EXPR:
  76       return build_polynomial_chrec
  77         (CHREC_VARIABLE (poly),
  78          chrec_fold_minus (type, CHREC_LEFT (poly), cst),
  79          CHREC_RIGHT (poly));
  80
  81     case MULT_EXPR:
  82       return build_polynomial_chrec
  83         (CHREC_VARIABLE (poly),
  84          chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
  85          chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
  86
  87     default:
  88       return chrec_dont_know;
  89     }
  90 }
  91
  92 /* Fold the addition of two polynomial functions.  */
  93
  94 static inline tree
  95 chrec_fold_plus_poly_poly (enum tree_code code,
  96                            tree type,
  97                            tree poly0,
  98                            tree poly1)
  99 {
 100   tree left, right;
 101
 102 #if defined ENABLE_CHECKING
 103   if (poly0 == NULL_TREE
 104       || poly1 == NULL_TREE
 105       || TREE_CODE (poly0) != POLYNOMIAL_CHREC
 106       || TREE_CODE (poly1) != POLYNOMIAL_CHREC)
 107     abort ();
 108 #endif
 109
 110   /*
 111     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
 112     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
 113     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
 114   if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
 115     {
 116       if (code == PLUS_EXPR)
 117         return build_polynomial_chrec
 118           (CHREC_VARIABLE (poly1),
 119            chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
 120            CHREC_RIGHT (poly1));
 121       else
 122         return build_polynomial_chrec
 123           (CHREC_VARIABLE (poly1),
 124            chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
 125            chrec_fold_multiply (type, CHREC_RIGHT (poly1),
 126                                 convert (type, integer_minus_one_node)));
 127     }
 128
 129   if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
 130     {
 131       if (code == PLUS_EXPR)
 132         return build_polynomial_chrec
 133           (CHREC_VARIABLE (poly0),
 134            chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
 135            CHREC_RIGHT (poly0));
 136       else
 137         return build_polynomial_chrec
 138           (CHREC_VARIABLE (poly0),
 139            chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
 140            CHREC_RIGHT (poly0));
 141     }
 142
 143   if (code == PLUS_EXPR)
 144     {
 145       left = chrec_fold_plus
 146         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 147       right = chrec_fold_plus
 148         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 149     }
 150   else
 151     {
 152       left = chrec_fold_minus
 153         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 154       right = chrec_fold_minus
 155         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 156     }
 157
 158   if (chrec_zerop (right))
 159     return left;
 160   else
 161     return build_polynomial_chrec
 162       (CHREC_VARIABLE (poly0), left, right);
 163 }
 164
 165 \f
 166
 167 /* Fold the multiplication of two polynomial functions.  */
 168
 169 static inline tree
 170 chrec_fold_multiply_poly_poly (tree type,
 171                                tree poly0,
 172                                tree poly1)
 173 {
 174 #if defined ENABLE_CHECKING
 175   if (poly0 == NULL_TREE
 176       || poly1 == NULL_TREE
 177       || TREE_CODE (poly0) != POLYNOMIAL_CHREC
 178       || TREE_CODE (poly1) != POLYNOMIAL_CHREC)
 179     abort ();
 180 #endif
 181
 182   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
 183      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
 184      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
 185   if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
 186     /* poly0 is a constant wrt. poly1.  */
 187     return build_polynomial_chrec
 188       (CHREC_VARIABLE (poly1),
 189        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
 190        CHREC_RIGHT (poly1));
 191
 192   if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
 193     /* poly1 is a constant wrt. poly0.  */
 194     return build_polynomial_chrec
 195       (CHREC_VARIABLE (poly0),
 196        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
 197        CHREC_RIGHT (poly0));
 198
 199   /* poly0 and poly1 are two polynomials in the same variable,
 200      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
 201   return
 202     build_polynomial_chrec
 203     (CHREC_VARIABLE (poly0),
 204      build_polynomial_chrec
 205      (CHREC_VARIABLE (poly0),
 206
 207       /* "a*c".  */
 208       chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)),
 209
 210       /* "a*d + b*c + b*d".  */
 211       chrec_fold_plus
 212       (type, chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)),
 213
 214        chrec_fold_plus
 215        (type,
 216         chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_LEFT (poly1)),
 217         chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))))),
 218
 219      /* "2*b*d".  */
 220      chrec_fold_multiply
 221      (type, build_int_cst (NULL_TREE, 2),
 222       chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))));
 223 }
 224
 225 /* When the operands are automatically_generated_chrec_p, the fold has
 226    to respect the semantics of the operands.  */
 227
 228 static inline tree
 229 chrec_fold_automatically_generated_operands (tree op0,
 230                                              tree op1)
 231 {
 232   if (op0 == chrec_dont_know
 233       || op1 == chrec_dont_know)
 234     return chrec_dont_know;
 235
 236   if (op0 == chrec_known
 237       || op1 == chrec_known)
 238     return chrec_known;
 239
 240   if (op0 == chrec_not_analyzed_yet
 241       || op1 == chrec_not_analyzed_yet)
 242     return chrec_not_analyzed_yet;
 243
 244   /* The default case produces a safe result. */
 245   return chrec_dont_know;
 246 }
 247
 248 /* Fold the addition of two chrecs.  */
 249
 250 static tree
 251 chrec_fold_plus_1 (enum tree_code code,
 252                    tree type,
 253                    tree op0,
 254                    tree op1)
 255 {
 256   if (automatically_generated_chrec_p (op0)
 257       || automatically_generated_chrec_p (op1))
 258     return chrec_fold_automatically_generated_operands (op0, op1);
 259
 260   switch (TREE_CODE (op0))
 261     {
 262     case POLYNOMIAL_CHREC:
 263       switch (TREE_CODE (op1))
 264         {
 265         case POLYNOMIAL_CHREC:
 266           return chrec_fold_plus_poly_poly (code, type, op0, op1);
 267
 268         default:
 269           if (code == PLUS_EXPR)
 270             return build_polynomial_chrec
 271               (CHREC_VARIABLE (op0),
 272                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
 273                CHREC_RIGHT (op0));
 274           else
 275             return build_polynomial_chrec
 276               (CHREC_VARIABLE (op0),
 277                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
 278                CHREC_RIGHT (op0));
 279         }
 280
 281     default:
 282       switch (TREE_CODE (op1))
 283         {
 284         case POLYNOMIAL_CHREC:
 285           if (code == PLUS_EXPR)
 286             return build_polynomial_chrec
 287               (CHREC_VARIABLE (op1),
 288                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
 289                CHREC_RIGHT (op1));
 290           else
 291             return build_polynomial_chrec
 292               (CHREC_VARIABLE (op1),
 293                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
 294                chrec_fold_multiply (type, CHREC_RIGHT (op1),
 295                                     convert (type,
 296                                              integer_minus_one_node)));
 297
 298         default:
 299           if (tree_contains_chrecs (op0)
 300               || tree_contains_chrecs (op1))
 301             return build (code, type, op0, op1);
 302           else
 303             return fold (build (code, type, op0, op1));
 304         }
 305     }
 306 }
 307
 308 /* Fold the addition of two chrecs.  */
 309
 310 tree
 311 chrec_fold_plus (tree type,
 312                  tree op0,
 313                  tree op1)
 314 {
 315   if (integer_zerop (op0))
 316     return op1;
 317   if (integer_zerop (op1))
 318     return op0;
 319
 320   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
 321 }
 322
 323 /* Fold the subtraction of two chrecs.  */
 324
 325 tree
 326 chrec_fold_minus (tree type,
 327                   tree op0,
 328                   tree op1)
 329 {
 330   if (integer_zerop (op1))
 331     return op0;
 332
 333   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
 334 }
 335
 336 /* Fold the multiplication of two chrecs.  */
 337
 338 tree
 339 chrec_fold_multiply (tree type,
 340                      tree op0,
 341                      tree op1)
 342 {
 343   if (automatically_generated_chrec_p (op0)
 344       || automatically_generated_chrec_p (op1))
 345     return chrec_fold_automatically_generated_operands (op0, op1);
 346
 347   switch (TREE_CODE (op0))
 348     {
 349     case POLYNOMIAL_CHREC:
 350       switch (TREE_CODE (op1))
 351         {
 352         case POLYNOMIAL_CHREC:
 353           return chrec_fold_multiply_poly_poly (type, op0, op1);
 354
 355         default:
 356           if (integer_onep (op1))
 357             return op0;
 358           if (integer_zerop (op1))
 359             return convert (type, integer_zero_node);
 360
 361           return build_polynomial_chrec
 362             (CHREC_VARIABLE (op0),
 363              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
 364              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 365         }
 366
 367     default:
 368       if (integer_onep (op0))
 369         return op1;
 370
 371       if (integer_zerop (op0))
 372         return convert (type, integer_zero_node);
 373
 374       switch (TREE_CODE (op1))
 375         {
 376         case POLYNOMIAL_CHREC:
 377           return build_polynomial_chrec
 378             (CHREC_VARIABLE (op1),
 379              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 380              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 381
 382         default:
 383           if (integer_onep (op1))
 384             return op0;
 385           if (integer_zerop (op1))
 386             return convert (type, integer_zero_node);
 387           return fold (build (MULT_EXPR, type, op0, op1));
 388         }
 389     }
 390 }
 391
 392 \f
 393
 394 /* Operations.  */
 395
 396 /* The factorial.  */
 397
 398 static tree
 399 tree_fold_factorial (tree f)
 400 {
 401   if (tree_int_cst_sgn (f) <= 0)
 402     return integer_one_node;
 403   else
 404     return fold
 405       (build (MULT_EXPR, integer_type_node, f,
 406               tree_fold_factorial (fold (build (MINUS_EXPR, integer_type_node,
 407                                                 f, integer_one_node)))));
 408 }
 409
 410 /* The binomial coefficient.  */
 411
 412 static tree
 413 tree_fold_binomial (tree n,
 414                     tree k)
 415 {
 416   return fold
 417     (build (EXACT_DIV_EXPR, integer_type_node, tree_fold_factorial (n),
 418             fold (build (MULT_EXPR, integer_type_node,
 419                          tree_fold_factorial (k),
 420                          tree_fold_factorial
 421                          (fold (build (MINUS_EXPR, integer_type_node,
 422                                        n, k)))))));
 423 }
 424
 425 /* Helper function.  Use the Newton's interpolating formula for
 426    evaluating the value of the evolution function.  */
 427
 428 static tree
 429 chrec_evaluate (unsigned var,
 430                 tree chrec,
 431                 tree n,
 432                 tree k)
 433 {
 434   tree type = chrec_type (chrec);
 435   tree binomial_n_k = tree_fold_binomial (n, k);
 436
 437   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 438     {
 439       if (CHREC_VARIABLE (chrec) > var)
 440         return chrec_evaluate (var, CHREC_LEFT (chrec), n, k);
 441
 442       if (CHREC_VARIABLE (chrec) == var)
 443         return chrec_fold_plus
 444           (type,
 445            fold (build (MULT_EXPR, type, binomial_n_k, CHREC_LEFT (chrec))),
 446            chrec_evaluate (var, CHREC_RIGHT (chrec), n,
 447                            fold (build (PLUS_EXPR, type, k, integer_one_node))));
 448
 449       return fold (build (MULT_EXPR, type, binomial_n_k, chrec));
 450     }
 451   else
 452     return fold (build (MULT_EXPR, type, binomial_n_k, chrec));
 453 }
 454
 455 /* Evaluates "CHREC (X)" when the varying variable is VAR.
 456    Example:  Given the following parameters,
 457
 458    var = 1
 459    chrec = {3, +, 4}_1
 460    x = 10
 461
 462    The result is given by the Newton's interpolating formula:
 463    3 * \binom{10}{0} + 4 * \binom{10}{1}.
 464 */
 465
 466 tree
 467 chrec_apply (unsigned var,
 468              tree chrec,
 469              tree x)
 470 {
 471   tree type = chrec_type (chrec);
 472   tree res = chrec_dont_know;
 473
 474   if (automatically_generated_chrec_p (chrec)
 475       || automatically_generated_chrec_p (x)
 476
 477       /* When the symbols are defined in an outer loop, it is possible
 478          to symbolically compute the apply, since the symbols are
 479          constants with respect to the varying loop.  */
 480       || chrec_contains_symbols_defined_in_loop (chrec, var)
 481       || chrec_contains_symbols (x))
 482     return chrec_dont_know;
 483
 484   if (dump_file && (dump_flags & TDF_DETAILS))
 485     fprintf (dump_file, "(chrec_apply \n");
 486
 487   if (evolution_function_is_affine_p (chrec))
 488     {
 489       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 490       if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
 491           && integer_zerop (CHREC_LEFT (chrec)))
 492         res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
 493
 494       else
 495         res = chrec_fold_plus (type, CHREC_LEFT (chrec),
 496                                chrec_fold_multiply (type,
 497                                                     CHREC_RIGHT (chrec), x));
 498     }
 499
 500   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 501     res = chrec;
 502
 503   else if (TREE_CODE (x) == INTEGER_CST
 504            && tree_int_cst_sgn (x) == 1)
 505     /* testsuite/.../ssa-chrec-38.c.  */
 506     res = chrec_evaluate (var, chrec, x, integer_zero_node);
 507
 508   else
 509     res = chrec_dont_know;
 510
 511   if (dump_file && (dump_flags & TDF_DETAILS))
 512     {
 513       fprintf (dump_file, "  (varying_loop = %d\n", var);
 514       fprintf (dump_file, ")\n  (chrec = ");
 515       print_generic_expr (dump_file, chrec, 0);
 516       fprintf (dump_file, ")\n  (x = ");
 517       print_generic_expr (dump_file, x, 0);
 518       fprintf (dump_file, ")\n  (res = ");
 519       print_generic_expr (dump_file, res, 0);
 520       fprintf (dump_file, "))\n");
 521     }
 522
 523   return res;
 524 }
 525
 526 /* Replaces the initial condition in CHREC with INIT_COND.  */
 527
 528 tree
 529 chrec_replace_initial_condition (tree chrec,
 530                                  tree init_cond)
 531 {
 532   if (automatically_generated_chrec_p (chrec))
 533     return chrec;
 534
 535   switch (TREE_CODE (chrec))
 536     {
 537     case POLYNOMIAL_CHREC:
 538       return build_polynomial_chrec
 539         (CHREC_VARIABLE (chrec),
 540          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 541          CHREC_RIGHT (chrec));
 542
 543     default:
 544       return init_cond;
 545     }
 546 }
 547
 548 /* Returns the initial condition of a given CHREC.  */
 549
 550 tree
 551 initial_condition (tree chrec)
 552 {
 553   if (automatically_generated_chrec_p (chrec))
 554     return chrec;
 555
 556   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 557     return initial_condition (CHREC_LEFT (chrec));
 558   else
 559     return chrec;
 560 }
 561
 562 /* Returns a univariate function that represents the evolution in
 563    LOOP_NUM.  Mask the evolution of any other loop.  */
 564
 565 tree
 566 hide_evolution_in_other_loops_than_loop (tree chrec,
 567                                          unsigned loop_num)
 568 {
 569   if (automatically_generated_chrec_p (chrec))
 570     return chrec;
 571
 572   switch (TREE_CODE (chrec))
 573     {
 574     case POLYNOMIAL_CHREC:
 575       if (CHREC_VARIABLE (chrec) == loop_num)
 576         return build_polynomial_chrec
 577           (loop_num,
 578            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 579                                                     loop_num),
 580            CHREC_RIGHT (chrec));
 581
 582       else if (CHREC_VARIABLE (chrec) < loop_num)
 583         /* There is no evolution in this loop.  */
 584         return initial_condition (chrec);
 585
 586       else
 587         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 588                                                         loop_num);
 589
 590     default:
 591       return chrec;
 592     }
 593 }
 594
 595 /* Returns the evolution part in LOOP_NUM.  Example: the call
 596    get_evolution_in_loop (1, {{0, +, 1}_1, +, 2}_1) returns
 597    {1, +, 2}_1  */
 598
 599 tree
 600 evolution_part_in_loop_num (tree chrec,
 601                             unsigned loop_num)
 602 {
 603   if (automatically_generated_chrec_p (chrec))
 604     return chrec;
 605
 606   switch (TREE_CODE (chrec))
 607     {
 608     case POLYNOMIAL_CHREC:
 609       if (CHREC_VARIABLE (chrec) == loop_num)
 610         {
 611           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 612               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 613             return CHREC_RIGHT (chrec);
 614
 615           else
 616             return build_polynomial_chrec
 617               (loop_num,
 618                evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num),
 619                CHREC_RIGHT (chrec));
 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 evolution_part_in_loop_num (CHREC_LEFT (chrec), loop_num);
 628
 629     default:
 630       return NULL_TREE;
 631     }
 632 }
 633
 634 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 635    This function is essentially used for setting the evolution to
 636    chrec_dont_know, for example after having determined that it is
 637    impossible to say how many times a loop will execute.  */
 638
 639 tree
 640 reset_evolution_in_loop (unsigned loop_num,
 641                          tree chrec,
 642                          tree new_evol)
 643 {
 644   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 645       && CHREC_VARIABLE (chrec) > loop_num)
 646     return build
 647       (TREE_CODE (chrec),
 648        build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 649        reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
 650        reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
 651
 652   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 653          && CHREC_VARIABLE (chrec) == loop_num)
 654     chrec = CHREC_LEFT (chrec);
 655
 656   return build_polynomial_chrec (loop_num, chrec, new_evol);
 657 }
 658
 659 /* Merges two evolution functions that were found by following two
 660    alternate paths of a conditional expression.  */
 661
 662 tree
 663 chrec_merge (tree chrec1,
 664              tree chrec2)
 665 {
 666   if (chrec1 == chrec_dont_know
 667       || chrec2 == chrec_dont_know)
 668     return chrec_dont_know;
 669
 670   if (chrec1 == chrec_known
 671       || chrec2 == chrec_known)
 672     return chrec_known;
 673
 674   if (chrec1 == chrec_not_analyzed_yet)
 675     return chrec2;
 676   if (chrec2 == chrec_not_analyzed_yet)
 677     return chrec1;
 678
 679   if (operand_equal_p (chrec1, chrec2, 0))
 680     return chrec1;
 681
 682   return chrec_dont_know;
 683 }
 684
 685 \f
 686
 687 /* Observers.  */
 688
 689 /* Helper function for is_multivariate_chrec.  */
 690
 691 static bool
 692 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 693 {
 694   if (chrec == NULL_TREE)
 695     return false;
 696
 697   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 698     {
 699       if (CHREC_VARIABLE (chrec) != rec_var)
 700         return true;
 701       else
 702         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 703                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 704     }
 705   else
 706     return false;
 707 }
 708
 709 /* Determine whether the given chrec is multivariate or not.  */
 710
 711 bool
 712 is_multivariate_chrec (tree chrec)
 713 {
 714   if (chrec == NULL_TREE)
 715     return false;
 716
 717   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 718     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 719                                        CHREC_VARIABLE (chrec))
 720             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 721                                           CHREC_VARIABLE (chrec)));
 722   else
 723     return false;
 724 }
 725
 726 /* Determines whether the chrec contains symbolic names or not.  */
 727
 728 bool
 729 chrec_contains_symbols (tree chrec)
 730 {
 731   if (chrec == NULL_TREE)
 732     return false;
 733
 734   if (TREE_CODE (chrec) == SSA_NAME
 735       || TREE_CODE (chrec) == VAR_DECL
 736       || TREE_CODE (chrec) == PARM_DECL
 737       || TREE_CODE (chrec) == FUNCTION_DECL
 738       || TREE_CODE (chrec) == LABEL_DECL
 739       || TREE_CODE (chrec) == RESULT_DECL
 740       || TREE_CODE (chrec) == FIELD_DECL)
 741     return true;
 742
 743   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 744     {
 745     case 3:
 746       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 747         return true;
 748
 749     case 2:
 750       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 751         return true;
 752
 753     case 1:
 754       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 755         return true;
 756
 757     default:
 758       return false;
 759     }
 760 }
 761
 762 /* Determines whether the chrec contains undetermined coefficients.  */
 763
 764 bool
 765 chrec_contains_undetermined (tree chrec)
 766 {
 767   if (chrec == chrec_dont_know
 768       || chrec == chrec_not_analyzed_yet
 769       || chrec == NULL_TREE)
 770     return true;
 771
 772   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 773     {
 774     case 3:
 775       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 776         return true;
 777
 778     case 2:
 779       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 780         return true;
 781
 782     case 1:
 783       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 784         return true;
 785
 786     default:
 787       return false;
 788     }
 789 }
 790
 791 /* Determines whether the tree EXPR contains chrecs.  */
 792
 793 bool
 794 tree_contains_chrecs (tree expr)
 795 {
 796   if (expr == NULL_TREE)
 797     return false;
 798
 799   if (tree_is_chrec (expr))
 800     return true;
 801
 802   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 803     {
 804     case 3:
 805       if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
 806         return true;
 807
 808     case 2:
 809       if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
 810         return true;
 811
 812     case 1:
 813       if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
 814         return true;
 815
 816     default:
 817       return false;
 818     }
 819 }
 820
 821 /* Determine whether the given tree is an affine multivariate
 822    evolution.  */
 823
 824 bool
 825 evolution_function_is_affine_multivariate_p (tree chrec)
 826 {
 827   if (chrec == NULL_TREE)
 828     return false;
 829
 830   switch (TREE_CODE (chrec))
 831     {
 832     case POLYNOMIAL_CHREC:
 833       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 834         {
 835           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 836             return true;
 837           else
 838             {
 839               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
 840                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
 841                      != CHREC_VARIABLE (chrec)
 842                   && evolution_function_is_affine_multivariate_p
 843                   (CHREC_RIGHT (chrec)))
 844                 return true;
 845               else
 846                 return false;
 847             }
 848         }
 849       else
 850         {
 851           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
 852               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
 853               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
 854               && evolution_function_is_affine_multivariate_p
 855               (CHREC_LEFT (chrec)))
 856             return true;
 857           else
 858             return false;
 859         }
 860
 861     default:
 862       return false;
 863     }
 864 }
 865
 866 /* Determine whether the given tree is a function in zero or one
 867    variables.  */
 868
 869 bool
 870 evolution_function_is_univariate_p (tree chrec)
 871 {
 872   if (chrec == NULL_TREE)
 873     return true;
 874
 875   switch (TREE_CODE (chrec))
 876     {
 877     case POLYNOMIAL_CHREC:
 878       switch (TREE_CODE (CHREC_LEFT (chrec)))
 879         {
 880         case POLYNOMIAL_CHREC:
 881           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
 882             return false;
 883           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
 884             return false;
 885           break;
 886
 887         default:
 888           break;
 889         }
 890
 891       switch (TREE_CODE (CHREC_RIGHT (chrec)))
 892         {
 893         case POLYNOMIAL_CHREC:
 894           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
 895             return false;
 896           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
 897             return false;
 898           break;
 899
 900         default:
 901           break;
 902         }
 903
 904     default:
 905       return true;
 906     }
 907 }
 908
 909 \f
 910
 911 /* Convert the initial condition of chrec to type.  */
 912
 913 tree
 914 chrec_convert (tree type,
 915                tree chrec)
 916 {
 917   tree ct;
 918
 919   if (automatically_generated_chrec_p (chrec))
 920     return chrec;
 921
 922   ct = chrec_type (chrec);
 923   if (ct == type)
 924     return chrec;
 925
 926   if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
 927     return count_ev_in_wider_type (type, chrec);
 928
 929   switch (TREE_CODE (chrec))
 930     {
 931     case POLYNOMIAL_CHREC:
 932       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
 933                                      chrec_convert (type,
 934                                                     CHREC_LEFT (chrec)),
 935                                      chrec_convert (type,
 936                                                     CHREC_RIGHT (chrec)));
 937
 938     default:
 939       {
 940         tree res = convert (type, chrec);
 941
 942         /* Don't propagate overflows.  */
 943         TREE_OVERFLOW (res) = 0;
 944         if (TREE_CODE_CLASS (TREE_CODE (res)) == 'c')
 945           TREE_CONSTANT_OVERFLOW (res) = 0;
 946         return res;
 947       }
 948     }
 949 }
 950
 951 /* Returns the type of the chrec.  */
 952
 953 tree
 954 chrec_type (tree chrec)
 955 {
 956   if (automatically_generated_chrec_p (chrec))
 957     return NULL_TREE;
 958
 959   return TREE_TYPE (chrec);
 960 }
 961
 962 extern void initialize_scalar_evolutions_analyzer (void);
 963
 964 /* Initializer.  */
 965
 966 void
 967 initialize_scalar_evolutions_analyzer (void)
 968 {
 969   /* The elements below are unique.  */
 970   if (chrec_dont_know == NULL_TREE)
 971     {
 972       chrec_not_analyzed_yet = NULL_TREE;
 973       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
 974       chrec_known = make_node (SCEV_KNOWN);
 975       TREE_TYPE (chrec_dont_know) = NULL_TREE;
 976       TREE_TYPE (chrec_known) = NULL_TREE;
 977     }
 978 }