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