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