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