gcc/tree-chrec.c

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