gcc/tree-chrec.c

   1 /* Chains of recurrences.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 "real.h"
  34 #include "diagnostic.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 #include "tree-scalar-evolution.h"
  41
  42 \f
  43
  44 /* Extended folder for chrecs.  */
  45
  46 /* Determines whether CST is not a constant evolution.  */
  47
  48 static inline bool
  49 is_not_constant_evolution (const_tree cst)
  50 {
  51   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
  52 }
  53
  54 /* Fold CODE for a polynomial function and a constant.  */
  55
  56 static inline tree
  57 chrec_fold_poly_cst (enum tree_code code,
  58                      tree type,
  59                      tree poly,
  60                      tree cst)
  61 {
  62   gcc_assert (poly);
  63   gcc_assert (cst);
  64   gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
  65   gcc_assert (!is_not_constant_evolution (cst));
  66   gcc_assert (type == chrec_type (poly));
  67
  68   switch (code)
  69     {
  70     case PLUS_EXPR:
  71       return build_polynomial_chrec
  72         (CHREC_VARIABLE (poly),
  73          chrec_fold_plus (type, CHREC_LEFT (poly), cst),
  74          CHREC_RIGHT (poly));
  75
  76     case MINUS_EXPR:
  77       return build_polynomial_chrec
  78         (CHREC_VARIABLE (poly),
  79          chrec_fold_minus (type, CHREC_LEFT (poly), cst),
  80          CHREC_RIGHT (poly));
  81
  82     case MULT_EXPR:
  83       return build_polynomial_chrec
  84         (CHREC_VARIABLE (poly),
  85          chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
  86          chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
  87
  88     default:
  89       return chrec_dont_know;
  90     }
  91 }
  92
  93 /* Fold the addition of two polynomial functions.  */
  94
  95 static inline tree
  96 chrec_fold_plus_poly_poly (enum tree_code code,
  97                            tree type,
  98                            tree poly0,
  99                            tree poly1)
 100 {
 101   tree left, right;
 102   struct loop *loop0 = get_chrec_loop (poly0);
 103   struct loop *loop1 = get_chrec_loop (poly1);
 104   tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type;
 105
 106   gcc_assert (poly0);
 107   gcc_assert (poly1);
 108   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
 109   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
 110   if (POINTER_TYPE_P (chrec_type (poly0)))
 111     gcc_assert (chrec_type (poly1) == sizetype);
 112   else
 113     gcc_assert (chrec_type (poly0) == chrec_type (poly1));
 114   gcc_assert (type == chrec_type (poly0));
 115
 116   /*
 117     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
 118     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
 119     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
 120   if (flow_loop_nested_p (loop0, loop1))
 121     {
 122       if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 123         return build_polynomial_chrec
 124           (CHREC_VARIABLE (poly1),
 125            chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
 126            CHREC_RIGHT (poly1));
 127       else
 128         return build_polynomial_chrec
 129           (CHREC_VARIABLE (poly1),
 130            chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
 131            chrec_fold_multiply (type, CHREC_RIGHT (poly1),
 132                                 SCALAR_FLOAT_TYPE_P (type)
 133                                 ? build_real (type, dconstm1)
 134                                 : build_int_cst_type (type, -1)));
 135     }
 136
 137   if (flow_loop_nested_p (loop1, loop0))
 138     {
 139       if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 140         return build_polynomial_chrec
 141           (CHREC_VARIABLE (poly0),
 142            chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
 143            CHREC_RIGHT (poly0));
 144       else
 145         return build_polynomial_chrec
 146           (CHREC_VARIABLE (poly0),
 147            chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
 148            CHREC_RIGHT (poly0));
 149     }
 150
 151   /* This function should never be called for chrecs of loops that
 152      do not belong to the same loop nest.  */
 153   gcc_assert (loop0 == loop1);
 154
 155   if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 156     {
 157       left = chrec_fold_plus
 158         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 159       right = chrec_fold_plus
 160         (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 161     }
 162   else
 163     {
 164       left = chrec_fold_minus
 165         (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 166       right = chrec_fold_minus
 167         (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 168     }
 169
 170   if (chrec_zerop (right))
 171     return left;
 172   else
 173     return build_polynomial_chrec
 174       (CHREC_VARIABLE (poly0), left, right);
 175 }
 176
 177 \f
 178
 179 /* Fold the multiplication of two polynomial functions.  */
 180
 181 static inline tree
 182 chrec_fold_multiply_poly_poly (tree type,
 183                                tree poly0,
 184                                tree poly1)
 185 {
 186   tree t0, t1, t2;
 187   int var;
 188   struct loop *loop0 = get_chrec_loop (poly0);
 189   struct loop *loop1 = get_chrec_loop (poly1);
 190
 191   gcc_assert (poly0);
 192   gcc_assert (poly1);
 193   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
 194   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
 195   gcc_assert (chrec_type (poly0) == chrec_type (poly1));
 196   gcc_assert (type == chrec_type (poly0));
 197
 198   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
 199      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
 200      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
 201   if (flow_loop_nested_p (loop0, loop1))
 202     /* poly0 is a constant wrt. poly1.  */
 203     return build_polynomial_chrec
 204       (CHREC_VARIABLE (poly1),
 205        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
 206        CHREC_RIGHT (poly1));
 207
 208   if (flow_loop_nested_p (loop1, loop0))
 209     /* poly1 is a constant wrt. poly0.  */
 210     return build_polynomial_chrec
 211       (CHREC_VARIABLE (poly0),
 212        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
 213        CHREC_RIGHT (poly0));
 214
 215   gcc_assert (loop0 == loop1);
 216
 217   /* poly0 and poly1 are two polynomials in the same variable,
 218      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
 219
 220   /* "a*c".  */
 221   t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
 222
 223   /* "a*d + b*c".  */
 224   t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
 225   t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
 226                                                        CHREC_RIGHT (poly0),
 227                                                        CHREC_LEFT (poly1)));
 228   /* "b*d".  */
 229   t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
 230   /* "a*d + b*c + b*d".  */
 231   t1 = chrec_fold_plus (type, t1, t2);
 232   /* "2*b*d".  */
 233   t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
 234                             ? build_real (type, dconst2)
 235                             : build_int_cst (type, 2), t2);
 236
 237   var = CHREC_VARIABLE (poly0);
 238   return build_polynomial_chrec (var, t0,
 239                                  build_polynomial_chrec (var, t1, t2));
 240 }
 241
 242 /* When the operands are automatically_generated_chrec_p, the fold has
 243    to respect the semantics of the operands.  */
 244
 245 static inline tree
 246 chrec_fold_automatically_generated_operands (tree op0,
 247                                              tree op1)
 248 {
 249   if (op0 == chrec_dont_know
 250       || op1 == chrec_dont_know)
 251     return chrec_dont_know;
 252
 253   if (op0 == chrec_known
 254       || op1 == chrec_known)
 255     return chrec_known;
 256
 257   if (op0 == chrec_not_analyzed_yet
 258       || op1 == chrec_not_analyzed_yet)
 259     return chrec_not_analyzed_yet;
 260
 261   /* The default case produces a safe result.  */
 262   return chrec_dont_know;
 263 }
 264
 265 /* Fold the addition of two chrecs.  */
 266
 267 static tree
 268 chrec_fold_plus_1 (enum tree_code code, tree type,
 269                    tree op0, tree op1)
 270 {
 271   tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
 272
 273   if (automatically_generated_chrec_p (op0)
 274       || automatically_generated_chrec_p (op1))
 275     return chrec_fold_automatically_generated_operands (op0, op1);
 276
 277   switch (TREE_CODE (op0))
 278     {
 279     case POLYNOMIAL_CHREC:
 280       switch (TREE_CODE (op1))
 281         {
 282         case POLYNOMIAL_CHREC:
 283           return chrec_fold_plus_poly_poly (code, type, op0, op1);
 284
 285         default:
 286           if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 287             return build_polynomial_chrec
 288               (CHREC_VARIABLE (op0),
 289                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
 290                CHREC_RIGHT (op0));
 291           else
 292             return build_polynomial_chrec
 293               (CHREC_VARIABLE (op0),
 294                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
 295                CHREC_RIGHT (op0));
 296         }
 297
 298     default:
 299       switch (TREE_CODE (op1))
 300         {
 301         case POLYNOMIAL_CHREC:
 302           if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 303             return build_polynomial_chrec
 304               (CHREC_VARIABLE (op1),
 305                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
 306                CHREC_RIGHT (op1));
 307           else
 308             return build_polynomial_chrec
 309               (CHREC_VARIABLE (op1),
 310                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
 311                chrec_fold_multiply (type, CHREC_RIGHT (op1),
 312                                     SCALAR_FLOAT_TYPE_P (type)
 313                                     ? build_real (type, dconstm1)
 314                                     : build_int_cst_type (type, -1)));
 315
 316         default:
 317           {
 318             int size = 0;
 319             if ((tree_contains_chrecs (op0, &size)
 320                  || tree_contains_chrecs (op1, &size))
 321                 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 322               return build2 (code, type, op0, op1);
 323             else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 324               return fold_build2 (code, type,
 325                                   fold_convert (type, op0),
 326                                   fold_convert (op1_type, op1));
 327             else
 328               return chrec_dont_know;
 329           }
 330         }
 331     }
 332 }
 333
 334 /* Fold the addition of two chrecs.  */
 335
 336 tree
 337 chrec_fold_plus (tree type,
 338                  tree op0,
 339                  tree op1)
 340 {
 341   enum tree_code code;
 342   if (automatically_generated_chrec_p (op0)
 343       || automatically_generated_chrec_p (op1))
 344     return chrec_fold_automatically_generated_operands (op0, op1);
 345
 346   if (integer_zerop (op0))
 347     return chrec_convert (type, op1, NULL);
 348   if (integer_zerop (op1))
 349     return chrec_convert (type, op0, NULL);
 350
 351   if (POINTER_TYPE_P (type))
 352     code = POINTER_PLUS_EXPR;
 353   else
 354     code = PLUS_EXPR;
 355
 356   return chrec_fold_plus_1 (code, type, op0, op1);
 357 }
 358
 359 /* Fold the subtraction of two chrecs.  */
 360
 361 tree
 362 chrec_fold_minus (tree type,
 363                   tree op0,
 364                   tree op1)
 365 {
 366   if (automatically_generated_chrec_p (op0)
 367       || automatically_generated_chrec_p (op1))
 368     return chrec_fold_automatically_generated_operands (op0, op1);
 369
 370   if (integer_zerop (op1))
 371     return op0;
 372
 373   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
 374 }
 375
 376 /* Fold the multiplication of two chrecs.  */
 377
 378 tree
 379 chrec_fold_multiply (tree type,
 380                      tree op0,
 381                      tree op1)
 382 {
 383   if (automatically_generated_chrec_p (op0)
 384       || automatically_generated_chrec_p (op1))
 385     return chrec_fold_automatically_generated_operands (op0, op1);
 386
 387   switch (TREE_CODE (op0))
 388     {
 389     case POLYNOMIAL_CHREC:
 390       switch (TREE_CODE (op1))
 391         {
 392         case POLYNOMIAL_CHREC:
 393           return chrec_fold_multiply_poly_poly (type, op0, op1);
 394
 395         default:
 396           if (integer_onep (op1))
 397             return op0;
 398           if (integer_zerop (op1))
 399             return build_int_cst (type, 0);
 400
 401           return build_polynomial_chrec
 402             (CHREC_VARIABLE (op0),
 403              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
 404              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 405         }
 406
 407     default:
 408       if (integer_onep (op0))
 409         return op1;
 410
 411       if (integer_zerop (op0))
 412         return build_int_cst (type, 0);
 413
 414       switch (TREE_CODE (op1))
 415         {
 416         case POLYNOMIAL_CHREC:
 417           return build_polynomial_chrec
 418             (CHREC_VARIABLE (op1),
 419              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 420              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 421
 422         default:
 423           if (integer_onep (op1))
 424             return op0;
 425           if (integer_zerop (op1))
 426             return build_int_cst (type, 0);
 427           return fold_build2 (MULT_EXPR, type, op0, op1);
 428         }
 429     }
 430 }
 431
 432 \f
 433
 434 /* Operations.  */
 435
 436 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
 437    calculation overflows, otherwise return C(n,k) with type TYPE.  */
 438
 439 static tree
 440 tree_fold_binomial (tree type, tree n, unsigned int k)
 441 {
 442   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
 443   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
 444   unsigned int i;
 445   tree res;
 446
 447   /* Handle the most frequent cases.  */
 448   if (k == 0)
 449     return build_int_cst (type, 1);
 450   if (k == 1)
 451     return fold_convert (type, n);
 452
 453   /* Check that k <= n.  */
 454   if (TREE_INT_CST_HIGH (n) == 0
 455       && TREE_INT_CST_LOW (n) < k)
 456     return NULL_TREE;
 457
 458   /* Numerator = n.  */
 459   lnum = TREE_INT_CST_LOW (n);
 460   hnum = TREE_INT_CST_HIGH (n);
 461
 462   /* Denominator = 2.  */
 463   ldenom = 2;
 464   hdenom = 0;
 465
 466   /* Index = Numerator-1.  */
 467   if (lnum == 0)
 468     {
 469       hidx = hnum - 1;
 470       lidx = ~ (unsigned HOST_WIDE_INT) 0;
 471     }
 472   else
 473     {
 474       hidx = hnum;
 475       lidx = lnum - 1;
 476     }
 477
 478   /* Numerator = Numerator*Index = n*(n-1).  */
 479   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 480     return NULL_TREE;
 481
 482   for (i = 3; i <= k; i++)
 483     {
 484       /* Index--.  */
 485       if (lidx == 0)
 486         {
 487           hidx--;
 488           lidx = ~ (unsigned HOST_WIDE_INT) 0;
 489         }
 490       else
 491         lidx--;
 492
 493       /* Numerator *= Index.  */
 494       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 495         return NULL_TREE;
 496
 497       /* Denominator *= i.  */
 498       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
 499     }
 500
 501   /* Result = Numerator / Denominator.  */
 502   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
 503                         &lres, &hres, &ldum, &hdum);
 504
 505   res = build_int_cst_wide (type, lres, hres);
 506   return int_fits_type_p (res, type) ? res : NULL_TREE;
 507 }
 508
 509 /* Helper function.  Use the Newton's interpolating formula for
 510    evaluating the value of the evolution function.  */
 511
 512 static tree
 513 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 514 {
 515   tree arg0, arg1, binomial_n_k;
 516   tree type = TREE_TYPE (chrec);
 517   struct loop *var_loop = get_loop (var);
 518
 519   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 520          && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
 521     chrec = CHREC_LEFT (chrec);
 522
 523   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 524       && CHREC_VARIABLE (chrec) == var)
 525     {
 526       arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
 527       if (arg1 == chrec_dont_know)
 528         return chrec_dont_know;
 529       binomial_n_k = tree_fold_binomial (type, n, k);
 530       if (!binomial_n_k)
 531         return chrec_dont_know;
 532       arg0 = fold_build2 (MULT_EXPR, type,
 533                           CHREC_LEFT (chrec), binomial_n_k);
 534       return chrec_fold_plus (type, arg0, arg1);
 535     }
 536
 537   binomial_n_k = tree_fold_binomial (type, n, k);
 538   if (!binomial_n_k)
 539     return chrec_dont_know;
 540
 541   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
 542 }
 543
 544 /* Evaluates "CHREC (X)" when the varying variable is VAR.
 545    Example:  Given the following parameters,
 546
 547    var = 1
 548    chrec = {3, +, 4}_1
 549    x = 10
 550
 551    The result is given by the Newton's interpolating formula:
 552    3 * \binom{10}{0} + 4 * \binom{10}{1}.
 553 */
 554
 555 tree
 556 chrec_apply (unsigned var,
 557              tree chrec,
 558              tree x)
 559 {
 560   tree type = chrec_type (chrec);
 561   tree res = chrec_dont_know;
 562
 563   if (automatically_generated_chrec_p (chrec)
 564       || automatically_generated_chrec_p (x)
 565
 566       /* When the symbols are defined in an outer loop, it is possible
 567          to symbolically compute the apply, since the symbols are
 568          constants with respect to the varying loop.  */
 569       || chrec_contains_symbols_defined_in_loop (chrec, var))
 570     return chrec_dont_know;
 571
 572   if (dump_file && (dump_flags & TDF_DETAILS))
 573     fprintf (dump_file, "(chrec_apply \n");
 574
 575   if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
 576     x = build_real_from_int_cst (type, x);
 577
 578   if (evolution_function_is_affine_p (chrec))
 579     {
 580       /* "{a, +, b} (x)"  ->  "a + b*x".  */
 581       x = chrec_convert_rhs (type, x, NULL);
 582       res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
 583       res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
 584     }
 585
 586   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 587     res = chrec;
 588
 589   else if (TREE_CODE (x) == INTEGER_CST
 590            && tree_int_cst_sgn (x) == 1)
 591     /* testsuite/.../ssa-chrec-38.c.  */
 592     res = chrec_evaluate (var, chrec, x, 0);
 593   else
 594     res = chrec_dont_know;
 595
 596   if (dump_file && (dump_flags & TDF_DETAILS))
 597     {
 598       fprintf (dump_file, "  (varying_loop = %d\n", var);
 599       fprintf (dump_file, ")\n  (chrec = ");
 600       print_generic_expr (dump_file, chrec, 0);
 601       fprintf (dump_file, ")\n  (x = ");
 602       print_generic_expr (dump_file, x, 0);
 603       fprintf (dump_file, ")\n  (res = ");
 604       print_generic_expr (dump_file, res, 0);
 605       fprintf (dump_file, "))\n");
 606     }
 607
 608   return res;
 609 }
 610
 611 /* Replaces the initial condition in CHREC with INIT_COND.  */
 612
 613 tree
 614 chrec_replace_initial_condition (tree chrec,
 615                                  tree init_cond)
 616 {
 617   if (automatically_generated_chrec_p (chrec))
 618     return chrec;
 619
 620   gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
 621
 622   switch (TREE_CODE (chrec))
 623     {
 624     case POLYNOMIAL_CHREC:
 625       return build_polynomial_chrec
 626         (CHREC_VARIABLE (chrec),
 627          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 628          CHREC_RIGHT (chrec));
 629
 630     default:
 631       return init_cond;
 632     }
 633 }
 634
 635 /* Returns the initial condition of a given CHREC.  */
 636
 637 tree
 638 initial_condition (tree chrec)
 639 {
 640   if (automatically_generated_chrec_p (chrec))
 641     return chrec;
 642
 643   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 644     return initial_condition (CHREC_LEFT (chrec));
 645   else
 646     return chrec;
 647 }
 648
 649 /* Returns a univariate function that represents the evolution in
 650    LOOP_NUM.  Mask the evolution of any other loop.  */
 651
 652 tree
 653 hide_evolution_in_other_loops_than_loop (tree chrec,
 654                                          unsigned loop_num)
 655 {
 656   struct loop *loop = get_loop (loop_num), *chloop;
 657   if (automatically_generated_chrec_p (chrec))
 658     return chrec;
 659
 660   switch (TREE_CODE (chrec))
 661     {
 662     case POLYNOMIAL_CHREC:
 663       chloop = get_chrec_loop (chrec);
 664
 665       if (chloop == loop)
 666         return build_polynomial_chrec
 667           (loop_num,
 668            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 669                                                     loop_num),
 670            CHREC_RIGHT (chrec));
 671
 672       else if (flow_loop_nested_p (chloop, loop))
 673         /* There is no evolution in this loop.  */
 674         return initial_condition (chrec);
 675
 676       else
 677         {
 678           gcc_assert (flow_loop_nested_p (loop, chloop));
 679           return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 680                                                           loop_num);
 681         }
 682
 683     default:
 684       return chrec;
 685     }
 686 }
 687
 688 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 689    true, otherwise returns the initial condition in LOOP_NUM.  */
 690
 691 static tree
 692 chrec_component_in_loop_num (tree chrec,
 693                              unsigned loop_num,
 694                              bool right)
 695 {
 696   tree component;
 697   struct loop *loop = get_loop (loop_num), *chloop;
 698
 699   if (automatically_generated_chrec_p (chrec))
 700     return chrec;
 701
 702   switch (TREE_CODE (chrec))
 703     {
 704     case POLYNOMIAL_CHREC:
 705       chloop = get_chrec_loop (chrec);
 706
 707       if (chloop == loop)
 708         {
 709           if (right)
 710             component = CHREC_RIGHT (chrec);
 711           else
 712             component = CHREC_LEFT (chrec);
 713
 714           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 715               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 716             return component;
 717
 718           else
 719             return build_polynomial_chrec
 720               (loop_num,
 721                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 722                                             loop_num,
 723                                             right),
 724                component);
 725         }
 726
 727       else if (flow_loop_nested_p (chloop, loop))
 728         /* There is no evolution part in this loop.  */
 729         return NULL_TREE;
 730
 731       else
 732         {
 733           gcc_assert (flow_loop_nested_p (loop, chloop));
 734           return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 735                                               loop_num,
 736                                               right);
 737         }
 738
 739      default:
 740       if (right)
 741         return NULL_TREE;
 742       else
 743         return chrec;
 744     }
 745 }
 746
 747 /* Returns the evolution part in LOOP_NUM.  Example: the call
 748    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 749    {1, +, 2}_1  */
 750
 751 tree
 752 evolution_part_in_loop_num (tree chrec,
 753                             unsigned loop_num)
 754 {
 755   return chrec_component_in_loop_num (chrec, loop_num, true);
 756 }
 757
 758 /* Returns the initial condition in LOOP_NUM.  Example: the call
 759    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 760    {0, +, 1}_1  */
 761
 762 tree
 763 initial_condition_in_loop_num (tree chrec,
 764                                unsigned loop_num)
 765 {
 766   return chrec_component_in_loop_num (chrec, loop_num, false);
 767 }
 768
 769 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 770    This function is essentially used for setting the evolution to
 771    chrec_dont_know, for example after having determined that it is
 772    impossible to say how many times a loop will execute.  */
 773
 774 tree
 775 reset_evolution_in_loop (unsigned loop_num,
 776                          tree chrec,
 777                          tree new_evol)
 778 {
 779   struct loop *loop = get_loop (loop_num);
 780
 781   if (POINTER_TYPE_P (chrec_type (chrec)))
 782     gcc_assert (sizetype == chrec_type (new_evol));
 783   else
 784     gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
 785
 786   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 787       && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
 788     {
 789       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 790                                            new_evol);
 791       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 792                                             new_evol);
 793       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
 794                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 795                      left, right);
 796     }
 797
 798   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 799          && CHREC_VARIABLE (chrec) == loop_num)
 800     chrec = CHREC_LEFT (chrec);
 801
 802   return build_polynomial_chrec (loop_num, chrec, new_evol);
 803 }
 804
 805 /* Merges two evolution functions that were found by following two
 806    alternate paths of a conditional expression.  */
 807
 808 tree
 809 chrec_merge (tree chrec1,
 810              tree chrec2)
 811 {
 812   if (chrec1 == chrec_dont_know
 813       || chrec2 == chrec_dont_know)
 814     return chrec_dont_know;
 815
 816   if (chrec1 == chrec_known
 817       || chrec2 == chrec_known)
 818     return chrec_known;
 819
 820   if (chrec1 == chrec_not_analyzed_yet)
 821     return chrec2;
 822   if (chrec2 == chrec_not_analyzed_yet)
 823     return chrec1;
 824
 825   if (eq_evolutions_p (chrec1, chrec2))
 826     return chrec1;
 827
 828   return chrec_dont_know;
 829 }
 830
 831 \f
 832
 833 /* Observers.  */
 834
 835 /* Helper function for is_multivariate_chrec.  */
 836
 837 static bool
 838 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
 839 {
 840   if (chrec == NULL_TREE)
 841     return false;
 842
 843   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 844     {
 845       if (CHREC_VARIABLE (chrec) != rec_var)
 846         return true;
 847       else
 848         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 849                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 850     }
 851   else
 852     return false;
 853 }
 854
 855 /* Determine whether the given chrec is multivariate or not.  */
 856
 857 bool
 858 is_multivariate_chrec (const_tree chrec)
 859 {
 860   if (chrec == NULL_TREE)
 861     return false;
 862
 863   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 864     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 865                                        CHREC_VARIABLE (chrec))
 866             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 867                                           CHREC_VARIABLE (chrec)));
 868   else
 869     return false;
 870 }
 871
 872 /* Determines whether the chrec contains symbolic names or not.  */
 873
 874 bool
 875 chrec_contains_symbols (const_tree chrec)
 876 {
 877   int i, n;
 878
 879   if (chrec == NULL_TREE)
 880     return false;
 881
 882   if (TREE_CODE (chrec) == SSA_NAME
 883       || TREE_CODE (chrec) == VAR_DECL
 884       || TREE_CODE (chrec) == PARM_DECL
 885       || TREE_CODE (chrec) == FUNCTION_DECL
 886       || TREE_CODE (chrec) == LABEL_DECL
 887       || TREE_CODE (chrec) == RESULT_DECL
 888       || TREE_CODE (chrec) == FIELD_DECL)
 889     return true;
 890
 891   n = TREE_OPERAND_LENGTH (chrec);
 892   for (i = 0; i < n; i++)
 893     if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
 894       return true;
 895   return false;
 896 }
 897
 898 /* Determines whether the chrec contains undetermined coefficients.  */
 899
 900 bool
 901 chrec_contains_undetermined (const_tree chrec)
 902 {
 903   int i, n;
 904
 905   if (chrec == chrec_dont_know)
 906     return true;
 907
 908   if (chrec == NULL_TREE)
 909     return false;
 910
 911   n = TREE_OPERAND_LENGTH (chrec);
 912   for (i = 0; i < n; i++)
 913     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
 914       return true;
 915   return false;
 916 }
 917
 918 /* Determines whether the tree EXPR contains chrecs, and increment
 919    SIZE if it is not a NULL pointer by an estimation of the depth of
 920    the tree.  */
 921
 922 bool
 923 tree_contains_chrecs (const_tree expr, int *size)
 924 {
 925   int i, n;
 926
 927   if (expr == NULL_TREE)
 928     return false;
 929
 930   if (size)
 931     (*size)++;
 932
 933   if (tree_is_chrec (expr))
 934     return true;
 935
 936   n = TREE_OPERAND_LENGTH (expr);
 937   for (i = 0; i < n; i++)
 938     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
 939       return true;
 940   return false;
 941 }
 942
 943 /* Recursive helper function.  */
 944
 945 static bool
 946 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 947 {
 948   if (evolution_function_is_constant_p (chrec))
 949     return true;
 950
 951   if (TREE_CODE (chrec) == SSA_NAME
 952       && (loopnum == 0
 953           || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
 954     return true;
 955
 956   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 957     {
 958       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
 959           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
 960                                                      loopnum)
 961           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
 962                                                      loopnum))
 963         return false;
 964       return true;
 965     }
 966
 967   switch (TREE_OPERAND_LENGTH (chrec))
 968     {
 969     case 2:
 970       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
 971                                                   loopnum))
 972         return false;
 973
 974     case 1:
 975       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
 976                                                   loopnum))
 977         return false;
 978       return true;
 979
 980     default:
 981       return false;
 982     }
 983
 984   return false;
 985 }
 986
 987 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
 988
 989 bool
 990 evolution_function_is_invariant_p (tree chrec, int loopnum)
 991 {
 992   return evolution_function_is_invariant_rec_p (chrec, loopnum);
 993 }
 994
 995 /* Determine whether the given tree is an affine multivariate
 996    evolution.  */
 997
 998 bool
 999 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1000 {
1001   if (chrec == NULL_TREE)
1002     return false;
1003
1004   switch (TREE_CODE (chrec))
1005     {
1006     case POLYNOMIAL_CHREC:
1007       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1008         {
1009           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1010             return true;
1011           else
1012             {
1013               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1014                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1015                      != CHREC_VARIABLE (chrec)
1016                   && evolution_function_is_affine_multivariate_p
1017                   (CHREC_RIGHT (chrec), loopnum))
1018                 return true;
1019               else
1020                 return false;
1021             }
1022         }
1023       else
1024         {
1025           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1026               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1027               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1028               && evolution_function_is_affine_multivariate_p
1029               (CHREC_LEFT (chrec), loopnum))
1030             return true;
1031           else
1032             return false;
1033         }
1034
1035     default:
1036       return false;
1037     }
1038 }
1039
1040 /* Determine whether the given tree is a function in zero or one
1041    variables.  */
1042
1043 bool
1044 evolution_function_is_univariate_p (const_tree chrec)
1045 {
1046   if (chrec == NULL_TREE)
1047     return true;
1048
1049   switch (TREE_CODE (chrec))
1050     {
1051     case POLYNOMIAL_CHREC:
1052       switch (TREE_CODE (CHREC_LEFT (chrec)))
1053         {
1054         case POLYNOMIAL_CHREC:
1055           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1056             return false;
1057           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1058             return false;
1059           break;
1060
1061         default:
1062           break;
1063         }
1064
1065       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1066         {
1067         case POLYNOMIAL_CHREC:
1068           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1069             return false;
1070           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1071             return false;
1072           break;
1073
1074         default:
1075           break;
1076         }
1077
1078     default:
1079       return true;
1080     }
1081 }
1082
1083 /* Returns the number of variables of CHREC.  Example: the call
1084    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1085
1086 unsigned
1087 nb_vars_in_chrec (tree chrec)
1088 {
1089   if (chrec == NULL_TREE)
1090     return 0;
1091
1092   switch (TREE_CODE (chrec))
1093     {
1094     case POLYNOMIAL_CHREC:
1095       return 1 + nb_vars_in_chrec
1096         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1097
1098     default:
1099       return 0;
1100     }
1101 }
1102
1103 static tree chrec_convert_1 (tree, tree, gimple, bool);
1104
1105 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1106    the scev corresponds to.  AT_STMT is the statement at that the scev is
1107    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1108    the rules for overflow of the given language apply (e.g., that signed
1109    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1110    tests, but also to enforce that the result follows them.  Returns true if the
1111    conversion succeeded, false otherwise.  */
1112
1113 bool
1114 convert_affine_scev (struct loop *loop, tree type,
1115                      tree *base, tree *step, gimple at_stmt,
1116                      bool use_overflow_semantics)
1117 {
1118   tree ct = TREE_TYPE (*step);
1119   bool enforce_overflow_semantics;
1120   bool must_check_src_overflow, must_check_rslt_overflow;
1121   tree new_base, new_step;
1122   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1123
1124   /* In general,
1125      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1126      but we must check some assumptions.
1127
1128      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1129         of CT is smaller than the precision of TYPE.  For example, when we
1130         cast unsigned char [254, +, 1] to unsigned, the values on left side
1131         are 254, 255, 0, 1, ..., but those on the right side are
1132         254, 255, 256, 257, ...
1133      2) In case that we must also preserve the fact that signed ivs do not
1134         overflow, we must additionally check that the new iv does not wrap.
1135         For example, unsigned char [125, +, 1] casted to signed char could
1136         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1137         which would confuse optimizers that assume that this does not
1138         happen.  */
1139   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1140
1141   enforce_overflow_semantics = (use_overflow_semantics
1142                                 && nowrap_type_p (type));
1143   if (enforce_overflow_semantics)
1144     {
1145       /* We can avoid checking whether the result overflows in the following
1146          cases:
1147
1148          -- must_check_src_overflow is true, and the range of TYPE is superset
1149             of the range of CT -- i.e., in all cases except if CT signed and
1150             TYPE unsigned.
1151          -- both CT and TYPE have the same precision and signedness, and we
1152             verify instead that the source does not overflow (this may be
1153             easier than verifying it for the result, as we may use the
1154             information about the semantics of overflow in CT).  */
1155       if (must_check_src_overflow)
1156         {
1157           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1158             must_check_rslt_overflow = true;
1159           else
1160             must_check_rslt_overflow = false;
1161         }
1162       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1163                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1164         {
1165           must_check_rslt_overflow = false;
1166           must_check_src_overflow = true;
1167         }
1168       else
1169         must_check_rslt_overflow = true;
1170     }
1171   else
1172     must_check_rslt_overflow = false;
1173
1174   if (must_check_src_overflow
1175       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1176                                 use_overflow_semantics))
1177     return false;
1178
1179   new_base = chrec_convert_1 (type, *base, at_stmt,
1180                               use_overflow_semantics);
1181   /* The step must be sign extended, regardless of the signedness
1182      of CT and TYPE.  This only needs to be handled specially when
1183      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1184      (with values 100, 99, 98, ...) from becoming signed or unsigned
1185      [100, +, 255] with values 100, 355, ...; the sign-extension is
1186      performed by default when CT is signed.  */
1187   new_step = *step;
1188   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1189     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1190                                 use_overflow_semantics);
1191   new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
1192
1193   if (automatically_generated_chrec_p (new_base)
1194       || automatically_generated_chrec_p (new_step))
1195     return false;
1196
1197   if (must_check_rslt_overflow
1198       /* Note that in this case we cannot use the fact that signed variables
1199          do not overflow, as this is what we are verifying for the new iv.  */
1200       && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1201     return false;
1202
1203   *base = new_base;
1204   *step = new_step;
1205   return true;
1206 }
1207 \f
1208
1209 /* Convert CHREC for the right hand side of a CREC.
1210    The increment for a pointer type is always sizetype.  */
1211 tree
1212 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
1213 {
1214   if (POINTER_TYPE_P (type))
1215    type = sizetype;
1216   return chrec_convert (type, chrec, at_stmt);
1217 }
1218
1219 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1220    which the CHREC is built, it sets AT_STMT to the statement that
1221    contains the definition of the analyzed variable, otherwise the
1222    conversion is less accurate: the information is used for
1223    determining a more accurate estimation of the number of iterations.
1224    By default AT_STMT could be safely set to NULL_TREE.
1225
1226    The following rule is always true: TREE_TYPE (chrec) ==
1227    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1228    An example of what could happen when adding two chrecs and the type
1229    of the CHREC_RIGHT is different than CHREC_LEFT is:
1230
1231    {(uint) 0, +, (uchar) 10} +
1232    {(uint) 0, +, (uchar) 250}
1233
1234    that would produce a wrong result if CHREC_RIGHT is not (uint):
1235
1236    {(uint) 0, +, (uchar) 4}
1237
1238    instead of
1239
1240    {(uint) 0, +, (uint) 260}
1241 */
1242
1243 tree
1244 chrec_convert (tree type, tree chrec, gimple at_stmt)
1245 {
1246   return chrec_convert_1 (type, chrec, at_stmt, true);
1247 }
1248
1249 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1250    which the CHREC is built, it sets AT_STMT to the statement that
1251    contains the definition of the analyzed variable, otherwise the
1252    conversion is less accurate: the information is used for
1253    determining a more accurate estimation of the number of iterations.
1254    By default AT_STMT could be safely set to NULL_TREE.
1255
1256    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1257    the rules for overflow of the given language apply (e.g., that signed
1258    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1259    tests, but also to enforce that the result follows them.  */
1260
1261 static tree
1262 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
1263                  bool use_overflow_semantics)
1264 {
1265   tree ct, res;
1266   tree base, step;
1267   struct loop *loop;
1268
1269   if (automatically_generated_chrec_p (chrec))
1270     return chrec;
1271
1272   ct = chrec_type (chrec);
1273   if (ct == type)
1274     return chrec;
1275
1276   if (!evolution_function_is_affine_p (chrec))
1277     goto keep_cast;
1278
1279   loop = get_chrec_loop (chrec);
1280   base = CHREC_LEFT (chrec);
1281   step = CHREC_RIGHT (chrec);
1282
1283   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1284                            use_overflow_semantics))
1285     return build_polynomial_chrec (loop->num, base, step);
1286
1287   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1288 keep_cast:
1289   res = fold_convert (type, chrec);
1290
1291   /* Don't propagate overflows.  */
1292   if (CONSTANT_CLASS_P (res))
1293     TREE_OVERFLOW (res) = 0;
1294
1295   /* But reject constants that don't fit in their type after conversion.
1296      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1297      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1298      and can cause problems later when computing niters of loops.  Note
1299      that we don't do the check before converting because we don't want
1300      to reject conversions of negative chrecs to unsigned types.  */
1301   if (TREE_CODE (res) == INTEGER_CST
1302       && TREE_CODE (type) == INTEGER_TYPE
1303       && !int_fits_type_p (res, type))
1304     res = chrec_dont_know;
1305
1306   return res;
1307 }
1308
1309 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1310    chrec if something else than what chrec_convert would do happens, NULL_TREE
1311    otherwise.  */
1312
1313 tree
1314 chrec_convert_aggressive (tree type, tree chrec)
1315 {
1316   tree inner_type, left, right, lc, rc, rtype;
1317
1318   if (automatically_generated_chrec_p (chrec)
1319       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1320     return NULL_TREE;
1321
1322   inner_type = TREE_TYPE (chrec);
1323   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1324     return NULL_TREE;
1325
1326   rtype = POINTER_TYPE_P (type) ? sizetype : type;
1327
1328   left = CHREC_LEFT (chrec);
1329   right = CHREC_RIGHT (chrec);
1330   lc = chrec_convert_aggressive (type, left);
1331   if (!lc)
1332     lc = chrec_convert (type, left, NULL);
1333   rc = chrec_convert_aggressive (rtype, right);
1334   if (!rc)
1335     rc = chrec_convert (rtype, right, NULL);
1336
1337   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1338 }
1339
1340 /* Returns true when CHREC0 == CHREC1.  */
1341
1342 bool
1343 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1344 {
1345   if (chrec0 == NULL_TREE
1346       || chrec1 == NULL_TREE
1347       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1348     return false;
1349
1350   if (chrec0 == chrec1)
1351     return true;
1352
1353   switch (TREE_CODE (chrec0))
1354     {
1355     case INTEGER_CST:
1356       return operand_equal_p (chrec0, chrec1, 0);
1357
1358     case POLYNOMIAL_CHREC:
1359       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1360               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1361               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1362     default:
1363       return false;
1364     }
1365 }
1366
1367 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1368    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1369    which of these cases happens.  */
1370
1371 enum ev_direction
1372 scev_direction (const_tree chrec)
1373 {
1374   const_tree step;
1375
1376   if (!evolution_function_is_affine_p (chrec))
1377     return EV_DIR_UNKNOWN;
1378
1379   step = CHREC_RIGHT (chrec);
1380   if (TREE_CODE (step) != INTEGER_CST)
1381     return EV_DIR_UNKNOWN;
1382
1383   if (tree_int_cst_sign_bit (step))
1384     return EV_DIR_DECREASES;
1385   else
1386     return EV_DIR_GROWS;
1387 }
1388
1389 /* Iterates over all the components of SCEV, and calls CBCK.  */
1390
1391 void
1392 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1393 {
1394   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1395     {
1396     case 3:
1397       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1398
1399     case 2:
1400       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1401
1402     case 1:
1403       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1404
1405     default:
1406       cbck (scev, data);
1407       break;
1408     }
1409 }
1410
1411 /* Returns true when the operation can be part of a linear
1412    expression.  */
1413
1414 static inline bool
1415 operator_is_linear (tree scev)
1416 {
1417   switch (TREE_CODE (scev))
1418     {
1419     case INTEGER_CST:
1420     case POLYNOMIAL_CHREC:
1421     case PLUS_EXPR:
1422     case POINTER_PLUS_EXPR:
1423     case MULT_EXPR:
1424     case MINUS_EXPR:
1425     case NEGATE_EXPR:
1426     case SSA_NAME:
1427     case NON_LVALUE_EXPR:
1428     CASE_CONVERT:
1429       return true;
1430
1431     default:
1432       return false;
1433     }
1434 }
1435
1436 /* Return true when SCEV is a linear expression.  Linear expressions
1437    can contain additions, substractions and multiplications.
1438    Multiplications are restricted to constant scaling: "cst * x".  */
1439
1440 bool
1441 scev_is_linear_expression (tree scev)
1442 {
1443   if (scev == NULL
1444       || !operator_is_linear (scev))
1445     return false;
1446
1447   if (TREE_CODE (scev) == MULT_EXPR)
1448     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1449              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1450
1451   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1452     {
1453     case 3:
1454       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1455         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1456         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1457
1458     case 2:
1459       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1460         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1461
1462     case 1:
1463       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1464
1465     case 0:
1466       return true;
1467
1468     default:
1469       return false;
1470     }
1471 }