gcc/tree-chrec.c

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