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, op0, op1);
 297             else
 298               return chrec_dont_know;
 299           }
 300         }
 301     }
 302 }
 303
 304 /* Fold the addition of two chrecs.  */
 305
 306 tree
 307 chrec_fold_plus (tree type,
 308                  tree op0,
 309                  tree op1)
 310 {
 311   if (integer_zerop (op0))
 312     return op1;
 313   if (integer_zerop (op1))
 314     return op0;
 315
 316   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
 317 }
 318
 319 /* Fold the subtraction of two chrecs.  */
 320
 321 tree
 322 chrec_fold_minus (tree type,
 323                   tree op0,
 324                   tree op1)
 325 {
 326   if (integer_zerop (op1))
 327     return op0;
 328
 329   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
 330 }
 331
 332 /* Fold the multiplication of two chrecs.  */
 333
 334 tree
 335 chrec_fold_multiply (tree type,
 336                      tree op0,
 337                      tree op1)
 338 {
 339   if (automatically_generated_chrec_p (op0)
 340       || automatically_generated_chrec_p (op1))
 341     return chrec_fold_automatically_generated_operands (op0, op1);
 342
 343   switch (TREE_CODE (op0))
 344     {
 345     case POLYNOMIAL_CHREC:
 346       switch (TREE_CODE (op1))
 347         {
 348         case POLYNOMIAL_CHREC:
 349           return chrec_fold_multiply_poly_poly (type, op0, op1);
 350
 351         default:
 352           if (integer_onep (op1))
 353             return op0;
 354           if (integer_zerop (op1))
 355             return build_int_cst_type (type, 0);
 356
 357           return build_polynomial_chrec
 358             (CHREC_VARIABLE (op0),
 359              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
 360              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 361         }
 362
 363     default:
 364       if (integer_onep (op0))
 365         return op1;
 366
 367       if (integer_zerop (op0))
 368         return build_int_cst_type (type, 0);
 369
 370       switch (TREE_CODE (op1))
 371         {
 372         case POLYNOMIAL_CHREC:
 373           return build_polynomial_chrec
 374             (CHREC_VARIABLE (op1),
 375              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 376              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 377
 378         default:
 379           if (integer_onep (op1))
 380             return op0;
 381           if (integer_zerop (op1))
 382             return build_int_cst_type (type, 0);
 383           return fold_build2 (MULT_EXPR, type, op0, op1);
 384         }
 385     }
 386 }
 387
 388 \f
 389
 390 /* Operations.  */
 391
 392 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
 393    calculation overflows, otherwise return C(n,k) with type TYPE.  */
 394
 395 static tree
 396 tree_fold_binomial (tree type, tree n, unsigned int k)
 397 {
 398   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
 399   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
 400   unsigned int i;
 401   tree res;
 402
 403   /* Handle the most frequent cases.  */
 404   if (k == 0)
 405     return build_int_cst (type, 1);
 406   if (k == 1)
 407     return fold_convert (type, n);
 408
 409   /* Check that k <= n.  */
 410   if (TREE_INT_CST_HIGH (n) == 0
 411       && TREE_INT_CST_LOW (n) < k)
 412     return NULL_TREE;
 413
 414   /* Numerator = n.  */
 415   lnum = TREE_INT_CST_LOW (n);
 416   hnum = TREE_INT_CST_HIGH (n);
 417
 418   /* Denominator = 2.  */
 419   ldenom = 2;
 420   hdenom = 0;
 421
 422   /* Index = Numerator-1.  */
 423   if (lnum == 0)
 424     {
 425       hidx = hnum - 1;
 426       lidx = ~ (unsigned HOST_WIDE_INT) 0;
 427     }
 428   else
 429     {
 430       hidx = hnum;
 431       lidx = lnum - 1;
 432     }
 433
 434   /* Numerator = Numerator*Index = n*(n-1).  */
 435   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 436     return NULL_TREE;
 437
 438   for (i = 3; i <= k; i++)
 439     {
 440       /* Index--.  */
 441       if (lidx == 0)
 442         {
 443           hidx--;
 444           lidx = ~ (unsigned HOST_WIDE_INT) 0;
 445         }
 446       else
 447         lidx--;
 448
 449       /* Numerator *= Index.  */
 450       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 451         return NULL_TREE;
 452
 453       /* Denominator *= i.  */
 454       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
 455     }
 456
 457   /* Result = Numerator / Denominator.  */
 458   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
 459                         &lres, &hres, &ldum, &hdum);
 460
 461   res = build_int_cst_wide (type, lres, hres);
 462   return int_fits_type_p (res, type) ? res : NULL_TREE;
 463 }
 464
 465 /* Helper function.  Use the Newton's interpolating formula for
 466    evaluating the value of the evolution function.  */
 467
 468 static tree
 469 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 470 {
 471   tree arg0, arg1, binomial_n_k;
 472   tree type = TREE_TYPE (chrec);
 473
 474   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 475          && CHREC_VARIABLE (chrec) > var)
 476     chrec = CHREC_LEFT (chrec);
 477
 478   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 479       && CHREC_VARIABLE (chrec) == var)
 480     {
 481       arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
 482       if (arg0 == chrec_dont_know)
 483         return chrec_dont_know;
 484       binomial_n_k = tree_fold_binomial (type, n, k);
 485       if (!binomial_n_k)
 486         return chrec_dont_know;
 487       arg1 = fold_build2 (MULT_EXPR, type,
 488                           CHREC_LEFT (chrec), binomial_n_k);
 489       return chrec_fold_plus (type, arg0, arg1);
 490     }
 491
 492   binomial_n_k = tree_fold_binomial (type, n, k);
 493   if (!binomial_n_k)
 494     return chrec_dont_know;
 495
 496   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
 497 }
 498
 499 /* Evaluates "CHREC (X)" when the varying variable is VAR.
 500    Example:  Given the following parameters,
 501
 502    var = 1
 503    chrec = {3, +, 4}_1
 504    x = 10
 505
 506    The result is given by the Newton's interpolating formula:
 507    3 * \binom{10}{0} + 4 * \binom{10}{1}.
 508 */
 509
 510 tree
 511 chrec_apply (unsigned var,
 512              tree chrec,
 513              tree x)
 514 {
 515   tree type = chrec_type (chrec);
 516   tree res = chrec_dont_know;
 517
 518   if (automatically_generated_chrec_p (chrec)
 519       || automatically_generated_chrec_p (x)
 520
 521       /* When the symbols are defined in an outer loop, it is possible
 522          to symbolically compute the apply, since the symbols are
 523          constants with respect to the varying loop.  */
 524       || chrec_contains_symbols_defined_in_loop (chrec, var)
 525       || chrec_contains_symbols (x))
 526     return chrec_dont_know;
 527
 528   if (dump_file && (dump_flags & TDF_DETAILS))
 529     fprintf (dump_file, "(chrec_apply \n");
 530
 531   if (evolution_function_is_affine_p (chrec))
 532     {
 533       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 534       if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
 535           && integer_zerop (CHREC_LEFT (chrec)))
 536         res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
 537
 538       else
 539         res = chrec_fold_plus (type, CHREC_LEFT (chrec),
 540                                chrec_fold_multiply (type,
 541                                                     CHREC_RIGHT (chrec), x));
 542     }
 543
 544   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 545     res = chrec;
 546
 547   else if (TREE_CODE (x) == INTEGER_CST
 548            && tree_int_cst_sgn (x) == 1)
 549     /* testsuite/.../ssa-chrec-38.c.  */
 550     res = chrec_evaluate (var, chrec, x, 0);
 551
 552   else
 553     res = chrec_dont_know;
 554
 555   if (dump_file && (dump_flags & TDF_DETAILS))
 556     {
 557       fprintf (dump_file, "  (varying_loop = %d\n", var);
 558       fprintf (dump_file, ")\n  (chrec = ");
 559       print_generic_expr (dump_file, chrec, 0);
 560       fprintf (dump_file, ")\n  (x = ");
 561       print_generic_expr (dump_file, x, 0);
 562       fprintf (dump_file, ")\n  (res = ");
 563       print_generic_expr (dump_file, res, 0);
 564       fprintf (dump_file, "))\n");
 565     }
 566
 567   return res;
 568 }
 569
 570 /* Replaces the initial condition in CHREC with INIT_COND.  */
 571
 572 tree
 573 chrec_replace_initial_condition (tree chrec,
 574                                  tree init_cond)
 575 {
 576   if (automatically_generated_chrec_p (chrec))
 577     return chrec;
 578
 579   switch (TREE_CODE (chrec))
 580     {
 581     case POLYNOMIAL_CHREC:
 582       return build_polynomial_chrec
 583         (CHREC_VARIABLE (chrec),
 584          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 585          CHREC_RIGHT (chrec));
 586
 587     default:
 588       return init_cond;
 589     }
 590 }
 591
 592 /* Returns the initial condition of a given CHREC.  */
 593
 594 tree
 595 initial_condition (tree chrec)
 596 {
 597   if (automatically_generated_chrec_p (chrec))
 598     return chrec;
 599
 600   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 601     return initial_condition (CHREC_LEFT (chrec));
 602   else
 603     return chrec;
 604 }
 605
 606 /* Returns a univariate function that represents the evolution in
 607    LOOP_NUM.  Mask the evolution of any other loop.  */
 608
 609 tree
 610 hide_evolution_in_other_loops_than_loop (tree chrec,
 611                                          unsigned loop_num)
 612 {
 613   if (automatically_generated_chrec_p (chrec))
 614     return chrec;
 615
 616   switch (TREE_CODE (chrec))
 617     {
 618     case POLYNOMIAL_CHREC:
 619       if (CHREC_VARIABLE (chrec) == loop_num)
 620         return build_polynomial_chrec
 621           (loop_num,
 622            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 623                                                     loop_num),
 624            CHREC_RIGHT (chrec));
 625
 626       else if (CHREC_VARIABLE (chrec) < loop_num)
 627         /* There is no evolution in this loop.  */
 628         return initial_condition (chrec);
 629
 630       else
 631         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 632                                                         loop_num);
 633
 634     default:
 635       return chrec;
 636     }
 637 }
 638
 639 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 640    true, otherwise returns the initial condition in LOOP_NUM.  */
 641
 642 static tree
 643 chrec_component_in_loop_num (tree chrec,
 644                              unsigned loop_num,
 645                              bool right)
 646 {
 647   tree component;
 648
 649   if (automatically_generated_chrec_p (chrec))
 650     return chrec;
 651
 652   switch (TREE_CODE (chrec))
 653     {
 654     case POLYNOMIAL_CHREC:
 655       if (CHREC_VARIABLE (chrec) == loop_num)
 656         {
 657           if (right)
 658             component = CHREC_RIGHT (chrec);
 659           else
 660             component = CHREC_LEFT (chrec);
 661
 662           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 663               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 664             return component;
 665
 666           else
 667             return build_polynomial_chrec
 668               (loop_num,
 669                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 670                                             loop_num,
 671                                             right),
 672                component);
 673         }
 674
 675       else if (CHREC_VARIABLE (chrec) < loop_num)
 676         /* There is no evolution part in this loop.  */
 677         return NULL_TREE;
 678
 679       else
 680         return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 681                                             loop_num,
 682                                             right);
 683
 684      default:
 685       if (right)
 686         return NULL_TREE;
 687       else
 688         return chrec;
 689     }
 690 }
 691
 692 /* Returns the evolution part in LOOP_NUM.  Example: the call
 693    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 694    {1, +, 2}_1  */
 695
 696 tree
 697 evolution_part_in_loop_num (tree chrec,
 698                             unsigned loop_num)
 699 {
 700   return chrec_component_in_loop_num (chrec, loop_num, true);
 701 }
 702
 703 /* Returns the initial condition in LOOP_NUM.  Example: the call
 704    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 705    {0, +, 1}_1  */
 706
 707 tree
 708 initial_condition_in_loop_num (tree chrec,
 709                                unsigned loop_num)
 710 {
 711   return chrec_component_in_loop_num (chrec, loop_num, false);
 712 }
 713
 714 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 715    This function is essentially used for setting the evolution to
 716    chrec_dont_know, for example after having determined that it is
 717    impossible to say how many times a loop will execute.  */
 718
 719 tree
 720 reset_evolution_in_loop (unsigned loop_num,
 721                          tree chrec,
 722                          tree new_evol)
 723 {
 724   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 725       && CHREC_VARIABLE (chrec) > loop_num)
 726     return build2
 727       (TREE_CODE (chrec),
 728        build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 729        reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
 730        reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
 731
 732   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 733          && CHREC_VARIABLE (chrec) == loop_num)
 734     chrec = CHREC_LEFT (chrec);
 735
 736   return build_polynomial_chrec (loop_num, chrec, new_evol);
 737 }
 738
 739 /* Merges two evolution functions that were found by following two
 740    alternate paths of a conditional expression.  */
 741
 742 tree
 743 chrec_merge (tree chrec1,
 744              tree chrec2)
 745 {
 746   if (chrec1 == chrec_dont_know
 747       || chrec2 == chrec_dont_know)
 748     return chrec_dont_know;
 749
 750   if (chrec1 == chrec_known
 751       || chrec2 == chrec_known)
 752     return chrec_known;
 753
 754   if (chrec1 == chrec_not_analyzed_yet)
 755     return chrec2;
 756   if (chrec2 == chrec_not_analyzed_yet)
 757     return chrec1;
 758
 759   if (operand_equal_p (chrec1, chrec2, 0))
 760     return chrec1;
 761
 762   return chrec_dont_know;
 763 }
 764
 765 \f
 766
 767 /* Observers.  */
 768
 769 /* Helper function for is_multivariate_chrec.  */
 770
 771 static bool
 772 is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 773 {
 774   if (chrec == NULL_TREE)
 775     return false;
 776
 777   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 778     {
 779       if (CHREC_VARIABLE (chrec) != rec_var)
 780         return true;
 781       else
 782         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 783                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 784     }
 785   else
 786     return false;
 787 }
 788
 789 /* Determine whether the given chrec is multivariate or not.  */
 790
 791 bool
 792 is_multivariate_chrec (tree chrec)
 793 {
 794   if (chrec == NULL_TREE)
 795     return false;
 796
 797   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 798     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 799                                        CHREC_VARIABLE (chrec))
 800             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 801                                           CHREC_VARIABLE (chrec)));
 802   else
 803     return false;
 804 }
 805
 806 /* Determines whether the chrec contains symbolic names or not.  */
 807
 808 bool
 809 chrec_contains_symbols (tree chrec)
 810 {
 811   if (chrec == NULL_TREE)
 812     return false;
 813
 814   if (TREE_CODE (chrec) == SSA_NAME
 815       || TREE_CODE (chrec) == VAR_DECL
 816       || TREE_CODE (chrec) == PARM_DECL
 817       || TREE_CODE (chrec) == FUNCTION_DECL
 818       || TREE_CODE (chrec) == LABEL_DECL
 819       || TREE_CODE (chrec) == RESULT_DECL
 820       || TREE_CODE (chrec) == FIELD_DECL)
 821     return true;
 822
 823   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 824     {
 825     case 3:
 826       if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
 827         return true;
 828
 829     case 2:
 830       if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
 831         return true;
 832
 833     case 1:
 834       if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
 835         return true;
 836
 837     default:
 838       return false;
 839     }
 840 }
 841
 842 /* Determines whether the chrec contains undetermined coefficients.  */
 843
 844 bool
 845 chrec_contains_undetermined (tree chrec)
 846 {
 847   if (chrec == chrec_dont_know
 848       || chrec == chrec_not_analyzed_yet
 849       || chrec == NULL_TREE)
 850     return true;
 851
 852   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
 853     {
 854     case 3:
 855       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
 856         return true;
 857
 858     case 2:
 859       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
 860         return true;
 861
 862     case 1:
 863       if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
 864         return true;
 865
 866     default:
 867       return false;
 868     }
 869 }
 870
 871 /* Determines whether the tree EXPR contains chrecs, and increment
 872    SIZE if it is not a NULL pointer by an estimation of the depth of
 873    the tree.  */
 874
 875 bool
 876 tree_contains_chrecs (tree expr, int *size)
 877 {
 878   if (expr == NULL_TREE)
 879     return false;
 880
 881   if (size)
 882     (*size)++;
 883
 884   if (tree_is_chrec (expr))
 885     return true;
 886
 887   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 888     {
 889     case 3:
 890       if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
 891         return true;
 892
 893     case 2:
 894       if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
 895         return true;
 896
 897     case 1:
 898       if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
 899         return true;
 900
 901     default:
 902       return false;
 903     }
 904 }
 905
 906 /* Determine whether the given tree is an affine multivariate
 907    evolution.  */
 908
 909 bool
 910 evolution_function_is_affine_multivariate_p (tree chrec)
 911 {
 912   if (chrec == NULL_TREE)
 913     return false;
 914
 915   switch (TREE_CODE (chrec))
 916     {
 917     case POLYNOMIAL_CHREC:
 918       if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
 919         {
 920           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
 921             return true;
 922           else
 923             {
 924               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
 925                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
 926                      != CHREC_VARIABLE (chrec)
 927                   && evolution_function_is_affine_multivariate_p
 928                   (CHREC_RIGHT (chrec)))
 929                 return true;
 930               else
 931                 return false;
 932             }
 933         }
 934       else
 935         {
 936           if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
 937               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
 938               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
 939               && evolution_function_is_affine_multivariate_p
 940               (CHREC_LEFT (chrec)))
 941             return true;
 942           else
 943             return false;
 944         }
 945
 946     default:
 947       return false;
 948     }
 949 }
 950
 951 /* Determine whether the given tree is a function in zero or one
 952    variables.  */
 953
 954 bool
 955 evolution_function_is_univariate_p (tree chrec)
 956 {
 957   if (chrec == NULL_TREE)
 958     return true;
 959
 960   switch (TREE_CODE (chrec))
 961     {
 962     case POLYNOMIAL_CHREC:
 963       switch (TREE_CODE (CHREC_LEFT (chrec)))
 964         {
 965         case POLYNOMIAL_CHREC:
 966           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
 967             return false;
 968           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
 969             return false;
 970           break;
 971
 972         default:
 973           break;
 974         }
 975
 976       switch (TREE_CODE (CHREC_RIGHT (chrec)))
 977         {
 978         case POLYNOMIAL_CHREC:
 979           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
 980             return false;
 981           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
 982             return false;
 983           break;
 984
 985         default:
 986           break;
 987         }
 988
 989     default:
 990       return true;
 991     }
 992 }
 993
 994 /* Returns the number of variables of CHREC.  Example: the call
 995    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
 996
 997 unsigned
 998 nb_vars_in_chrec (tree chrec)
 999 {
1000   if (chrec == NULL_TREE)
1001     return 0;
1002
1003   switch (TREE_CODE (chrec))
1004     {
1005     case POLYNOMIAL_CHREC:
1006       return 1 + nb_vars_in_chrec
1007         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1008
1009     default:
1010       return 0;
1011     }
1012 }
1013
1014 \f
1015
1016 /* Convert CHREC to TYPE.  The following is rule is always true:
1017    TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
1018    (CHREC_RIGHT (chrec)).  An example of what could happen when adding
1019    two chrecs and the type of the CHREC_RIGHT is different than
1020    CHREC_LEFT is:
1021
1022    {(uint) 0, +, (uchar) 10} +
1023    {(uint) 0, +, (uchar) 250}
1024
1025    that would produce a wrong result if CHREC_RIGHT is not (uint):
1026
1027    {(uint) 0, +, (uchar) 4}
1028
1029    instead of
1030
1031    {(uint) 0, +, (uint) 260}
1032 */
1033
1034 tree
1035 chrec_convert (tree type,
1036                tree chrec)
1037 {
1038   tree ct;
1039
1040   if (automatically_generated_chrec_p (chrec))
1041     return chrec;
1042
1043   ct = chrec_type (chrec);
1044   if (ct == type)
1045     return chrec;
1046
1047   if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
1048     return count_ev_in_wider_type (type, chrec);
1049
1050   switch (TREE_CODE (chrec))
1051     {
1052     case POLYNOMIAL_CHREC:
1053       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1054                                      chrec_convert (type,
1055                                                     CHREC_LEFT (chrec)),
1056                                      chrec_convert (type,
1057                                                     CHREC_RIGHT (chrec)));
1058
1059     default:
1060       {
1061         tree res = fold_convert (type, chrec);
1062
1063         /* Don't propagate overflows.  */
1064         if (CONSTANT_CLASS_P (res))
1065           {
1066             TREE_CONSTANT_OVERFLOW (res) = 0;
1067             TREE_OVERFLOW (res) = 0;
1068           }
1069
1070         /* But reject constants that don't fit in their type after conversion.
1071            This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1072            natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1073            and can cause problems later when computing niters of loops.  Note
1074            that we don't do the check before converting because we don't want
1075            to reject conversions of negative chrecs to unsigned types.  */
1076         if (TREE_CODE (res) == INTEGER_CST
1077             && TREE_CODE (type) == INTEGER_TYPE
1078             && !int_fits_type_p (res, type))
1079           res = chrec_dont_know;
1080
1081         return res;
1082       }
1083     }
1084 }
1085
1086 /* Returns the type of the chrec.  */
1087
1088 tree
1089 chrec_type (tree chrec)
1090 {
1091   if (automatically_generated_chrec_p (chrec))
1092     return NULL_TREE;
1093
1094   return TREE_TYPE (chrec);
1095 }