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