gcc/tree-chrec.c

   1 /* Chains of recurrences.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   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 "tree-pretty-print.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 "flags.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         CASE_CONVERT:
 286           if (tree_contains_chrecs (op1, NULL))
 287             return chrec_dont_know;
 288
 289         default:
 290           if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 291             return build_polynomial_chrec
 292               (CHREC_VARIABLE (op0),
 293                chrec_fold_plus (type, CHREC_LEFT (op0), op1),
 294                CHREC_RIGHT (op0));
 295           else
 296             return build_polynomial_chrec
 297               (CHREC_VARIABLE (op0),
 298                chrec_fold_minus (type, CHREC_LEFT (op0), op1),
 299                CHREC_RIGHT (op0));
 300         }
 301
 302     CASE_CONVERT:
 303       if (tree_contains_chrecs (op0, NULL))
 304         return chrec_dont_know;
 305
 306     default:
 307       switch (TREE_CODE (op1))
 308         {
 309         case POLYNOMIAL_CHREC:
 310           if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
 311             return build_polynomial_chrec
 312               (CHREC_VARIABLE (op1),
 313                chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
 314                CHREC_RIGHT (op1));
 315           else
 316             return build_polynomial_chrec
 317               (CHREC_VARIABLE (op1),
 318                chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
 319                chrec_fold_multiply (type, CHREC_RIGHT (op1),
 320                                     SCALAR_FLOAT_TYPE_P (type)
 321                                     ? build_real (type, dconstm1)
 322                                     : build_int_cst_type (type, -1)));
 323
 324         CASE_CONVERT:
 325           if (tree_contains_chrecs (op1, NULL))
 326             return chrec_dont_know;
 327
 328         default:
 329           {
 330             int size = 0;
 331             if ((tree_contains_chrecs (op0, &size)
 332                  || tree_contains_chrecs (op1, &size))
 333                 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 334               return build2 (code, type, op0, op1);
 335             else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 336               return fold_build2 (code, type,
 337                                   fold_convert (type, op0),
 338                                   fold_convert (op1_type, op1));
 339             else
 340               return chrec_dont_know;
 341           }
 342         }
 343     }
 344 }
 345
 346 /* Fold the addition of two chrecs.  */
 347
 348 tree
 349 chrec_fold_plus (tree type,
 350                  tree op0,
 351                  tree op1)
 352 {
 353   enum tree_code code;
 354   if (automatically_generated_chrec_p (op0)
 355       || automatically_generated_chrec_p (op1))
 356     return chrec_fold_automatically_generated_operands (op0, op1);
 357
 358   if (integer_zerop (op0))
 359     return chrec_convert (type, op1, NULL);
 360   if (integer_zerop (op1))
 361     return chrec_convert (type, op0, NULL);
 362
 363   if (POINTER_TYPE_P (type))
 364     code = POINTER_PLUS_EXPR;
 365   else
 366     code = PLUS_EXPR;
 367
 368   return chrec_fold_plus_1 (code, type, op0, op1);
 369 }
 370
 371 /* Fold the subtraction of two chrecs.  */
 372
 373 tree
 374 chrec_fold_minus (tree type,
 375                   tree op0,
 376                   tree op1)
 377 {
 378   if (automatically_generated_chrec_p (op0)
 379       || automatically_generated_chrec_p (op1))
 380     return chrec_fold_automatically_generated_operands (op0, op1);
 381
 382   if (integer_zerop (op1))
 383     return op0;
 384
 385   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
 386 }
 387
 388 /* Fold the multiplication of two chrecs.  */
 389
 390 tree
 391 chrec_fold_multiply (tree type,
 392                      tree op0,
 393                      tree op1)
 394 {
 395   if (automatically_generated_chrec_p (op0)
 396       || automatically_generated_chrec_p (op1))
 397     return chrec_fold_automatically_generated_operands (op0, op1);
 398
 399   switch (TREE_CODE (op0))
 400     {
 401     case POLYNOMIAL_CHREC:
 402       switch (TREE_CODE (op1))
 403         {
 404         case POLYNOMIAL_CHREC:
 405           return chrec_fold_multiply_poly_poly (type, op0, op1);
 406
 407         CASE_CONVERT:
 408           if (tree_contains_chrecs (op1, NULL))
 409             return chrec_dont_know;
 410
 411         default:
 412           if (integer_onep (op1))
 413             return op0;
 414           if (integer_zerop (op1))
 415             return build_int_cst (type, 0);
 416
 417           return build_polynomial_chrec
 418             (CHREC_VARIABLE (op0),
 419              chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
 420              chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 421         }
 422
 423     CASE_CONVERT:
 424       if (tree_contains_chrecs (op0, NULL))
 425         return chrec_dont_know;
 426
 427     default:
 428       if (integer_onep (op0))
 429         return op1;
 430
 431       if (integer_zerop (op0))
 432         return build_int_cst (type, 0);
 433
 434       switch (TREE_CODE (op1))
 435         {
 436         case POLYNOMIAL_CHREC:
 437           return build_polynomial_chrec
 438             (CHREC_VARIABLE (op1),
 439              chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 440              chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 441
 442         CASE_CONVERT:
 443           if (tree_contains_chrecs (op1, NULL))
 444             return chrec_dont_know;
 445
 446         default:
 447           if (integer_onep (op1))
 448             return op0;
 449           if (integer_zerop (op1))
 450             return build_int_cst (type, 0);
 451           return fold_build2 (MULT_EXPR, type, op0, op1);
 452         }
 453     }
 454 }
 455
 456 \f
 457
 458 /* Operations.  */
 459
 460 /* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
 461    calculation overflows, otherwise return C(n,k) with type TYPE.  */
 462
 463 static tree
 464 tree_fold_binomial (tree type, tree n, unsigned int k)
 465 {
 466   unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
 467   HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
 468   unsigned int i;
 469   tree res;
 470
 471   /* Handle the most frequent cases.  */
 472   if (k == 0)
 473     return build_int_cst (type, 1);
 474   if (k == 1)
 475     return fold_convert (type, n);
 476
 477   /* Check that k <= n.  */
 478   if (TREE_INT_CST_HIGH (n) == 0
 479       && TREE_INT_CST_LOW (n) < k)
 480     return NULL_TREE;
 481
 482   /* Numerator = n.  */
 483   lnum = TREE_INT_CST_LOW (n);
 484   hnum = TREE_INT_CST_HIGH (n);
 485
 486   /* Denominator = 2.  */
 487   ldenom = 2;
 488   hdenom = 0;
 489
 490   /* Index = Numerator-1.  */
 491   if (lnum == 0)
 492     {
 493       hidx = hnum - 1;
 494       lidx = ~ (unsigned HOST_WIDE_INT) 0;
 495     }
 496   else
 497     {
 498       hidx = hnum;
 499       lidx = lnum - 1;
 500     }
 501
 502   /* Numerator = Numerator*Index = n*(n-1).  */
 503   if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 504     return NULL_TREE;
 505
 506   for (i = 3; i <= k; i++)
 507     {
 508       /* Index--.  */
 509       if (lidx == 0)
 510         {
 511           hidx--;
 512           lidx = ~ (unsigned HOST_WIDE_INT) 0;
 513         }
 514       else
 515         lidx--;
 516
 517       /* Numerator *= Index.  */
 518       if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
 519         return NULL_TREE;
 520
 521       /* Denominator *= i.  */
 522       mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
 523     }
 524
 525   /* Result = Numerator / Denominator.  */
 526   div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
 527                         &lres, &hres, &ldum, &hdum);
 528
 529   res = build_int_cst_wide (type, lres, hres);
 530   return int_fits_type_p (res, type) ? res : NULL_TREE;
 531 }
 532
 533 /* Helper function.  Use the Newton's interpolating formula for
 534    evaluating the value of the evolution function.  */
 535
 536 static tree
 537 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 538 {
 539   tree arg0, arg1, binomial_n_k;
 540   tree type = TREE_TYPE (chrec);
 541   struct loop *var_loop = get_loop (var);
 542
 543   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 544          && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
 545     chrec = CHREC_LEFT (chrec);
 546
 547   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 548       && CHREC_VARIABLE (chrec) == var)
 549     {
 550       arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
 551       if (arg1 == chrec_dont_know)
 552         return chrec_dont_know;
 553       binomial_n_k = tree_fold_binomial (type, n, k);
 554       if (!binomial_n_k)
 555         return chrec_dont_know;
 556       arg0 = fold_build2 (MULT_EXPR, type,
 557                           CHREC_LEFT (chrec), binomial_n_k);
 558       return chrec_fold_plus (type, arg0, arg1);
 559     }
 560
 561   binomial_n_k = tree_fold_binomial (type, n, k);
 562   if (!binomial_n_k)
 563     return chrec_dont_know;
 564
 565   return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
 566 }
 567
 568 /* Evaluates "CHREC (X)" when the varying variable is VAR.
 569    Example:  Given the following parameters,
 570
 571    var = 1
 572    chrec = {3, +, 4}_1
 573    x = 10
 574
 575    The result is given by the Newton's interpolating formula:
 576    3 * \binom{10}{0} + 4 * \binom{10}{1}.
 577 */
 578
 579 tree
 580 chrec_apply (unsigned var,
 581              tree chrec,
 582              tree x)
 583 {
 584   tree type = chrec_type (chrec);
 585   tree res = chrec_dont_know;
 586
 587   if (automatically_generated_chrec_p (chrec)
 588       || automatically_generated_chrec_p (x)
 589
 590       /* When the symbols are defined in an outer loop, it is possible
 591          to symbolically compute the apply, since the symbols are
 592          constants with respect to the varying loop.  */
 593       || chrec_contains_symbols_defined_in_loop (chrec, var))
 594     return chrec_dont_know;
 595
 596   if (dump_file && (dump_flags & TDF_DETAILS))
 597     fprintf (dump_file, "(chrec_apply \n");
 598
 599   if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
 600     x = build_real_from_int_cst (type, x);
 601
 602   switch (TREE_CODE (chrec))
 603     {
 604     case POLYNOMIAL_CHREC:
 605       if (evolution_function_is_affine_p (chrec))
 606         {
 607           if (CHREC_VARIABLE (chrec) != var)
 608             return build_polynomial_chrec
 609               (CHREC_VARIABLE (chrec),
 610                chrec_apply (var, CHREC_LEFT (chrec), x),
 611                chrec_apply (var, CHREC_RIGHT (chrec), x));
 612
 613           /* "{a, +, b} (x)"  ->  "a + b*x".  */
 614           x = chrec_convert_rhs (type, x, NULL);
 615           res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
 616           res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
 617         }
 618       else if (TREE_CODE (x) == INTEGER_CST
 619                && tree_int_cst_sgn (x) == 1)
 620         /* testsuite/.../ssa-chrec-38.c.  */
 621         res = chrec_evaluate (var, chrec, x, 0);
 622       else
 623         res = chrec_dont_know;
 624       break;
 625
 626     CASE_CONVERT:
 627       res = chrec_convert (TREE_TYPE (chrec),
 628                            chrec_apply (var, TREE_OPERAND (chrec, 0), x),
 629                            NULL);
 630       break;
 631
 632     default:
 633       res = chrec;
 634       break;
 635     }
 636
 637   if (dump_file && (dump_flags & TDF_DETAILS))
 638     {
 639       fprintf (dump_file, "  (varying_loop = %d\n", var);
 640       fprintf (dump_file, ")\n  (chrec = ");
 641       print_generic_expr (dump_file, chrec, 0);
 642       fprintf (dump_file, ")\n  (x = ");
 643       print_generic_expr (dump_file, x, 0);
 644       fprintf (dump_file, ")\n  (res = ");
 645       print_generic_expr (dump_file, res, 0);
 646       fprintf (dump_file, "))\n");
 647     }
 648
 649   return res;
 650 }
 651
 652 /* For a given CHREC and an induction variable map IV_MAP that maps
 653    (loop->num, expr) for every loop number of the current_loops an
 654    expression, calls chrec_apply when the expression is not NULL.  */
 655
 656 tree
 657 chrec_apply_map (tree chrec, VEC (tree, heap) *iv_map)
 658 {
 659   int i;
 660   tree expr;
 661
 662   FOR_EACH_VEC_ELT (tree, iv_map, i, expr)
 663     if (expr)
 664       chrec = chrec_apply (i, chrec, expr);
 665
 666   return chrec;
 667 }
 668
 669 /* Replaces the initial condition in CHREC with INIT_COND.  */
 670
 671 tree
 672 chrec_replace_initial_condition (tree chrec,
 673                                  tree init_cond)
 674 {
 675   if (automatically_generated_chrec_p (chrec))
 676     return chrec;
 677
 678   gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
 679
 680   switch (TREE_CODE (chrec))
 681     {
 682     case POLYNOMIAL_CHREC:
 683       return build_polynomial_chrec
 684         (CHREC_VARIABLE (chrec),
 685          chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
 686          CHREC_RIGHT (chrec));
 687
 688     default:
 689       return init_cond;
 690     }
 691 }
 692
 693 /* Returns the initial condition of a given CHREC.  */
 694
 695 tree
 696 initial_condition (tree chrec)
 697 {
 698   if (automatically_generated_chrec_p (chrec))
 699     return chrec;
 700
 701   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 702     return initial_condition (CHREC_LEFT (chrec));
 703   else
 704     return chrec;
 705 }
 706
 707 /* Returns a univariate function that represents the evolution in
 708    LOOP_NUM.  Mask the evolution of any other loop.  */
 709
 710 tree
 711 hide_evolution_in_other_loops_than_loop (tree chrec,
 712                                          unsigned loop_num)
 713 {
 714   struct loop *loop = get_loop (loop_num), *chloop;
 715   if (automatically_generated_chrec_p (chrec))
 716     return chrec;
 717
 718   switch (TREE_CODE (chrec))
 719     {
 720     case POLYNOMIAL_CHREC:
 721       chloop = get_chrec_loop (chrec);
 722
 723       if (chloop == loop)
 724         return build_polynomial_chrec
 725           (loop_num,
 726            hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 727                                                     loop_num),
 728            CHREC_RIGHT (chrec));
 729
 730       else if (flow_loop_nested_p (chloop, loop))
 731         /* There is no evolution in this loop.  */
 732         return initial_condition (chrec);
 733
 734       else
 735         {
 736           gcc_assert (flow_loop_nested_p (loop, chloop));
 737           return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
 738                                                           loop_num);
 739         }
 740
 741     default:
 742       return chrec;
 743     }
 744 }
 745
 746 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
 747    true, otherwise returns the initial condition in LOOP_NUM.  */
 748
 749 static tree
 750 chrec_component_in_loop_num (tree chrec,
 751                              unsigned loop_num,
 752                              bool right)
 753 {
 754   tree component;
 755   struct loop *loop = get_loop (loop_num), *chloop;
 756
 757   if (automatically_generated_chrec_p (chrec))
 758     return chrec;
 759
 760   switch (TREE_CODE (chrec))
 761     {
 762     case POLYNOMIAL_CHREC:
 763       chloop = get_chrec_loop (chrec);
 764
 765       if (chloop == loop)
 766         {
 767           if (right)
 768             component = CHREC_RIGHT (chrec);
 769           else
 770             component = CHREC_LEFT (chrec);
 771
 772           if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
 773               || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
 774             return component;
 775
 776           else
 777             return build_polynomial_chrec
 778               (loop_num,
 779                chrec_component_in_loop_num (CHREC_LEFT (chrec),
 780                                             loop_num,
 781                                             right),
 782                component);
 783         }
 784
 785       else if (flow_loop_nested_p (chloop, loop))
 786         /* There is no evolution part in this loop.  */
 787         return NULL_TREE;
 788
 789       else
 790         {
 791           gcc_assert (flow_loop_nested_p (loop, chloop));
 792           return chrec_component_in_loop_num (CHREC_LEFT (chrec),
 793                                               loop_num,
 794                                               right);
 795         }
 796
 797      default:
 798       if (right)
 799         return NULL_TREE;
 800       else
 801         return chrec;
 802     }
 803 }
 804
 805 /* Returns the evolution part in LOOP_NUM.  Example: the call
 806    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
 807    {1, +, 2}_1  */
 808
 809 tree
 810 evolution_part_in_loop_num (tree chrec,
 811                             unsigned loop_num)
 812 {
 813   return chrec_component_in_loop_num (chrec, loop_num, true);
 814 }
 815
 816 /* Returns the initial condition in LOOP_NUM.  Example: the call
 817    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
 818    {0, +, 1}_1  */
 819
 820 tree
 821 initial_condition_in_loop_num (tree chrec,
 822                                unsigned loop_num)
 823 {
 824   return chrec_component_in_loop_num (chrec, loop_num, false);
 825 }
 826
 827 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
 828    This function is essentially used for setting the evolution to
 829    chrec_dont_know, for example after having determined that it is
 830    impossible to say how many times a loop will execute.  */
 831
 832 tree
 833 reset_evolution_in_loop (unsigned loop_num,
 834                          tree chrec,
 835                          tree new_evol)
 836 {
 837   struct loop *loop = get_loop (loop_num);
 838
 839   if (POINTER_TYPE_P (chrec_type (chrec)))
 840     gcc_assert (sizetype == chrec_type (new_evol));
 841   else
 842     gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
 843
 844   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 845       && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
 846     {
 847       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
 848                                            new_evol);
 849       tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
 850                                             new_evol);
 851       return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
 852                      build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
 853                      left, right);
 854     }
 855
 856   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 857          && CHREC_VARIABLE (chrec) == loop_num)
 858     chrec = CHREC_LEFT (chrec);
 859
 860   return build_polynomial_chrec (loop_num, chrec, new_evol);
 861 }
 862
 863 /* Merges two evolution functions that were found by following two
 864    alternate paths of a conditional expression.  */
 865
 866 tree
 867 chrec_merge (tree chrec1,
 868              tree chrec2)
 869 {
 870   if (chrec1 == chrec_dont_know
 871       || chrec2 == chrec_dont_know)
 872     return chrec_dont_know;
 873
 874   if (chrec1 == chrec_known
 875       || chrec2 == chrec_known)
 876     return chrec_known;
 877
 878   if (chrec1 == chrec_not_analyzed_yet)
 879     return chrec2;
 880   if (chrec2 == chrec_not_analyzed_yet)
 881     return chrec1;
 882
 883   if (eq_evolutions_p (chrec1, chrec2))
 884     return chrec1;
 885
 886   return chrec_dont_know;
 887 }
 888
 889 \f
 890
 891 /* Observers.  */
 892
 893 /* Helper function for is_multivariate_chrec.  */
 894
 895 static bool
 896 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
 897 {
 898   if (chrec == NULL_TREE)
 899     return false;
 900
 901   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 902     {
 903       if (CHREC_VARIABLE (chrec) != rec_var)
 904         return true;
 905       else
 906         return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
 907                 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
 908     }
 909   else
 910     return false;
 911 }
 912
 913 /* Determine whether the given chrec is multivariate or not.  */
 914
 915 bool
 916 is_multivariate_chrec (const_tree chrec)
 917 {
 918   if (chrec == NULL_TREE)
 919     return false;
 920
 921   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
 922     return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
 923                                        CHREC_VARIABLE (chrec))
 924             || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
 925                                           CHREC_VARIABLE (chrec)));
 926   else
 927     return false;
 928 }
 929
 930 /* Determines whether the chrec contains symbolic names or not.  */
 931
 932 bool
 933 chrec_contains_symbols (const_tree chrec)
 934 {
 935   int i, n;
 936
 937   if (chrec == NULL_TREE)
 938     return false;
 939
 940   if (TREE_CODE (chrec) == SSA_NAME
 941       || TREE_CODE (chrec) == VAR_DECL
 942       || TREE_CODE (chrec) == PARM_DECL
 943       || TREE_CODE (chrec) == FUNCTION_DECL
 944       || TREE_CODE (chrec) == LABEL_DECL
 945       || TREE_CODE (chrec) == RESULT_DECL
 946       || TREE_CODE (chrec) == FIELD_DECL)
 947     return true;
 948
 949   n = TREE_OPERAND_LENGTH (chrec);
 950   for (i = 0; i < n; i++)
 951     if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
 952       return true;
 953   return false;
 954 }
 955
 956 /* Determines whether the chrec contains undetermined coefficients.  */
 957
 958 bool
 959 chrec_contains_undetermined (const_tree chrec)
 960 {
 961   int i, n;
 962
 963   if (chrec == chrec_dont_know)
 964     return true;
 965
 966   if (chrec == NULL_TREE)
 967     return false;
 968
 969   n = TREE_OPERAND_LENGTH (chrec);
 970   for (i = 0; i < n; i++)
 971     if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
 972       return true;
 973   return false;
 974 }
 975
 976 /* Determines whether the tree EXPR contains chrecs, and increment
 977    SIZE if it is not a NULL pointer by an estimation of the depth of
 978    the tree.  */
 979
 980 bool
 981 tree_contains_chrecs (const_tree expr, int *size)
 982 {
 983   int i, n;
 984
 985   if (expr == NULL_TREE)
 986     return false;
 987
 988   if (size)
 989     (*size)++;
 990
 991   if (tree_is_chrec (expr))
 992     return true;
 993
 994   n = TREE_OPERAND_LENGTH (expr);
 995   for (i = 0; i < n; i++)
 996     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
 997       return true;
 998   return false;
 999 }
1000
1001 /* Recursive helper function.  */
1002
1003 static bool
1004 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1005 {
1006   if (evolution_function_is_constant_p (chrec))
1007     return true;
1008
1009   if (TREE_CODE (chrec) == SSA_NAME
1010       && (loopnum == 0
1011           || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
1012     return true;
1013
1014   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1015     {
1016       if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1017           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1018                                                      loopnum)
1019           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1020                                                      loopnum))
1021         return false;
1022       return true;
1023     }
1024
1025   switch (TREE_OPERAND_LENGTH (chrec))
1026     {
1027     case 2:
1028       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1029                                                   loopnum))
1030         return false;
1031
1032     case 1:
1033       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1034                                                   loopnum))
1035         return false;
1036       return true;
1037
1038     default:
1039       return false;
1040     }
1041
1042   return false;
1043 }
1044
1045 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1046
1047 bool
1048 evolution_function_is_invariant_p (tree chrec, int loopnum)
1049 {
1050   return evolution_function_is_invariant_rec_p (chrec, loopnum);
1051 }
1052
1053 /* Determine whether the given tree is an affine multivariate
1054    evolution.  */
1055
1056 bool
1057 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1058 {
1059   if (chrec == NULL_TREE)
1060     return false;
1061
1062   switch (TREE_CODE (chrec))
1063     {
1064     case POLYNOMIAL_CHREC:
1065       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1066         {
1067           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1068             return true;
1069           else
1070             {
1071               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1072                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1073                      != CHREC_VARIABLE (chrec)
1074                   && evolution_function_is_affine_multivariate_p
1075                   (CHREC_RIGHT (chrec), loopnum))
1076                 return true;
1077               else
1078                 return false;
1079             }
1080         }
1081       else
1082         {
1083           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1084               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1085               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1086               && evolution_function_is_affine_multivariate_p
1087               (CHREC_LEFT (chrec), loopnum))
1088             return true;
1089           else
1090             return false;
1091         }
1092
1093     default:
1094       return false;
1095     }
1096 }
1097
1098 /* Determine whether the given tree is a function in zero or one
1099    variables.  */
1100
1101 bool
1102 evolution_function_is_univariate_p (const_tree chrec)
1103 {
1104   if (chrec == NULL_TREE)
1105     return true;
1106
1107   switch (TREE_CODE (chrec))
1108     {
1109     case POLYNOMIAL_CHREC:
1110       switch (TREE_CODE (CHREC_LEFT (chrec)))
1111         {
1112         case POLYNOMIAL_CHREC:
1113           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1114             return false;
1115           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1116             return false;
1117           break;
1118
1119         default:
1120           break;
1121         }
1122
1123       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1124         {
1125         case POLYNOMIAL_CHREC:
1126           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1127             return false;
1128           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1129             return false;
1130           break;
1131
1132         default:
1133           break;
1134         }
1135
1136     default:
1137       return true;
1138     }
1139 }
1140
1141 /* Returns the number of variables of CHREC.  Example: the call
1142    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1143
1144 unsigned
1145 nb_vars_in_chrec (tree chrec)
1146 {
1147   if (chrec == NULL_TREE)
1148     return 0;
1149
1150   switch (TREE_CODE (chrec))
1151     {
1152     case POLYNOMIAL_CHREC:
1153       return 1 + nb_vars_in_chrec
1154         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1155
1156     default:
1157       return 0;
1158     }
1159 }
1160
1161 static tree chrec_convert_1 (tree, tree, gimple, bool);
1162
1163 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1164    the scev corresponds to.  AT_STMT is the statement at that the scev is
1165    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1166    the rules for overflow of the given language apply (e.g., that signed
1167    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1168    tests, but also to enforce that the result follows them.  Returns true if the
1169    conversion succeeded, false otherwise.  */
1170
1171 bool
1172 convert_affine_scev (struct loop *loop, tree type,
1173                      tree *base, tree *step, gimple at_stmt,
1174                      bool use_overflow_semantics)
1175 {
1176   tree ct = TREE_TYPE (*step);
1177   bool enforce_overflow_semantics;
1178   bool must_check_src_overflow, must_check_rslt_overflow;
1179   tree new_base, new_step;
1180   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1181
1182   /* In general,
1183      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1184      but we must check some assumptions.
1185
1186      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1187         of CT is smaller than the precision of TYPE.  For example, when we
1188         cast unsigned char [254, +, 1] to unsigned, the values on left side
1189         are 254, 255, 0, 1, ..., but those on the right side are
1190         254, 255, 256, 257, ...
1191      2) In case that we must also preserve the fact that signed ivs do not
1192         overflow, we must additionally check that the new iv does not wrap.
1193         For example, unsigned char [125, +, 1] casted to signed char could
1194         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1195         which would confuse optimizers that assume that this does not
1196         happen.  */
1197   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1198
1199   enforce_overflow_semantics = (use_overflow_semantics
1200                                 && nowrap_type_p (type));
1201   if (enforce_overflow_semantics)
1202     {
1203       /* We can avoid checking whether the result overflows in the following
1204          cases:
1205
1206          -- must_check_src_overflow is true, and the range of TYPE is superset
1207             of the range of CT -- i.e., in all cases except if CT signed and
1208             TYPE unsigned.
1209          -- both CT and TYPE have the same precision and signedness, and we
1210             verify instead that the source does not overflow (this may be
1211             easier than verifying it for the result, as we may use the
1212             information about the semantics of overflow in CT).  */
1213       if (must_check_src_overflow)
1214         {
1215           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1216             must_check_rslt_overflow = true;
1217           else
1218             must_check_rslt_overflow = false;
1219         }
1220       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1221                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1222         {
1223           must_check_rslt_overflow = false;
1224           must_check_src_overflow = true;
1225         }
1226       else
1227         must_check_rslt_overflow = true;
1228     }
1229   else
1230     must_check_rslt_overflow = false;
1231
1232   if (must_check_src_overflow
1233       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1234                                 use_overflow_semantics))
1235     return false;
1236
1237   new_base = chrec_convert_1 (type, *base, at_stmt,
1238                               use_overflow_semantics);
1239   /* The step must be sign extended, regardless of the signedness
1240      of CT and TYPE.  This only needs to be handled specially when
1241      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1242      (with values 100, 99, 98, ...) from becoming signed or unsigned
1243      [100, +, 255] with values 100, 355, ...; the sign-extension is
1244      performed by default when CT is signed.  */
1245   new_step = *step;
1246   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1247     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1248                                 use_overflow_semantics);
1249   new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
1250
1251   if (automatically_generated_chrec_p (new_base)
1252       || automatically_generated_chrec_p (new_step))
1253     return false;
1254
1255   if (must_check_rslt_overflow
1256       /* Note that in this case we cannot use the fact that signed variables
1257          do not overflow, as this is what we are verifying for the new iv.  */
1258       && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1259     return false;
1260
1261   *base = new_base;
1262   *step = new_step;
1263   return true;
1264 }
1265 \f
1266
1267 /* Convert CHREC for the right hand side of a CHREC.
1268    The increment for a pointer type is always sizetype.  */
1269
1270 tree
1271 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
1272 {
1273   if (POINTER_TYPE_P (type))
1274     type = sizetype;
1275
1276   return chrec_convert (type, chrec, at_stmt);
1277 }
1278
1279 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1280    which the CHREC is built, it sets AT_STMT to the statement that
1281    contains the definition of the analyzed variable, otherwise the
1282    conversion is less accurate: the information is used for
1283    determining a more accurate estimation of the number of iterations.
1284    By default AT_STMT could be safely set to NULL_TREE.
1285
1286    The following rule is always true: TREE_TYPE (chrec) ==
1287    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1288    An example of what could happen when adding two chrecs and the type
1289    of the CHREC_RIGHT is different than CHREC_LEFT is:
1290
1291    {(uint) 0, +, (uchar) 10} +
1292    {(uint) 0, +, (uchar) 250}
1293
1294    that would produce a wrong result if CHREC_RIGHT is not (uint):
1295
1296    {(uint) 0, +, (uchar) 4}
1297
1298    instead of
1299
1300    {(uint) 0, +, (uint) 260}
1301 */
1302
1303 tree
1304 chrec_convert (tree type, tree chrec, gimple at_stmt)
1305 {
1306   return chrec_convert_1 (type, chrec, at_stmt, true);
1307 }
1308
1309 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1310    which the CHREC is built, it sets AT_STMT to the statement that
1311    contains the definition of the analyzed variable, otherwise the
1312    conversion is less accurate: the information is used for
1313    determining a more accurate estimation of the number of iterations.
1314    By default AT_STMT could be safely set to NULL_TREE.
1315
1316    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1317    the rules for overflow of the given language apply (e.g., that signed
1318    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1319    tests, but also to enforce that the result follows them.  */
1320
1321 static tree
1322 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
1323                  bool use_overflow_semantics)
1324 {
1325   tree ct, res;
1326   tree base, step;
1327   struct loop *loop;
1328
1329   if (automatically_generated_chrec_p (chrec))
1330     return chrec;
1331
1332   ct = chrec_type (chrec);
1333   if (ct == type)
1334     return chrec;
1335
1336   if (!evolution_function_is_affine_p (chrec))
1337     goto keep_cast;
1338
1339   loop = get_chrec_loop (chrec);
1340   base = CHREC_LEFT (chrec);
1341   step = CHREC_RIGHT (chrec);
1342
1343   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1344                            use_overflow_semantics))
1345     return build_polynomial_chrec (loop->num, base, step);
1346
1347   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1348 keep_cast:
1349   /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1350      may be more expensive.  We do want to perform this optimization here
1351      though for canonicalization reasons.  */
1352   if (use_overflow_semantics
1353       && (TREE_CODE (chrec) == PLUS_EXPR
1354           || TREE_CODE (chrec) == MINUS_EXPR)
1355       && TREE_CODE (type) == INTEGER_TYPE
1356       && TREE_CODE (ct) == INTEGER_TYPE
1357       && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1358       && TYPE_OVERFLOW_UNDEFINED (ct))
1359     res = fold_build2 (TREE_CODE (chrec), type,
1360                        fold_convert (type, TREE_OPERAND (chrec, 0)),
1361                        fold_convert (type, TREE_OPERAND (chrec, 1)));
1362   else
1363     res = fold_convert (type, chrec);
1364
1365   /* Don't propagate overflows.  */
1366   if (CONSTANT_CLASS_P (res))
1367     TREE_OVERFLOW (res) = 0;
1368
1369   /* But reject constants that don't fit in their type after conversion.
1370      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1371      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1372      and can cause problems later when computing niters of loops.  Note
1373      that we don't do the check before converting because we don't want
1374      to reject conversions of negative chrecs to unsigned types.  */
1375   if (TREE_CODE (res) == INTEGER_CST
1376       && TREE_CODE (type) == INTEGER_TYPE
1377       && !int_fits_type_p (res, type))
1378     res = chrec_dont_know;
1379
1380   return res;
1381 }
1382
1383 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1384    chrec if something else than what chrec_convert would do happens, NULL_TREE
1385    otherwise.  */
1386
1387 tree
1388 chrec_convert_aggressive (tree type, tree chrec)
1389 {
1390   tree inner_type, left, right, lc, rc, rtype;
1391
1392   if (automatically_generated_chrec_p (chrec)
1393       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1394     return NULL_TREE;
1395
1396   inner_type = TREE_TYPE (chrec);
1397   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1398     return NULL_TREE;
1399
1400   rtype = POINTER_TYPE_P (type) ? sizetype : type;
1401
1402   left = CHREC_LEFT (chrec);
1403   right = CHREC_RIGHT (chrec);
1404   lc = chrec_convert_aggressive (type, left);
1405   if (!lc)
1406     lc = chrec_convert (type, left, NULL);
1407   rc = chrec_convert_aggressive (rtype, right);
1408   if (!rc)
1409     rc = chrec_convert (rtype, right, NULL);
1410
1411   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1412 }
1413
1414 /* Returns true when CHREC0 == CHREC1.  */
1415
1416 bool
1417 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1418 {
1419   if (chrec0 == NULL_TREE
1420       || chrec1 == NULL_TREE
1421       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1422     return false;
1423
1424   if (chrec0 == chrec1)
1425     return true;
1426
1427   switch (TREE_CODE (chrec0))
1428     {
1429     case INTEGER_CST:
1430       return operand_equal_p (chrec0, chrec1, 0);
1431
1432     case POLYNOMIAL_CHREC:
1433       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1434               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1435               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1436     default:
1437       return false;
1438     }
1439 }
1440
1441 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1442    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1443    which of these cases happens.  */
1444
1445 enum ev_direction
1446 scev_direction (const_tree chrec)
1447 {
1448   const_tree step;
1449
1450   if (!evolution_function_is_affine_p (chrec))
1451     return EV_DIR_UNKNOWN;
1452
1453   step = CHREC_RIGHT (chrec);
1454   if (TREE_CODE (step) != INTEGER_CST)
1455     return EV_DIR_UNKNOWN;
1456
1457   if (tree_int_cst_sign_bit (step))
1458     return EV_DIR_DECREASES;
1459   else
1460     return EV_DIR_GROWS;
1461 }
1462
1463 /* Iterates over all the components of SCEV, and calls CBCK.  */
1464
1465 void
1466 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1467 {
1468   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1469     {
1470     case 3:
1471       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1472
1473     case 2:
1474       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1475
1476     case 1:
1477       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1478
1479     default:
1480       cbck (scev, data);
1481       break;
1482     }
1483 }
1484
1485 /* Returns true when the operation can be part of a linear
1486    expression.  */
1487
1488 static inline bool
1489 operator_is_linear (tree scev)
1490 {
1491   switch (TREE_CODE (scev))
1492     {
1493     case INTEGER_CST:
1494     case POLYNOMIAL_CHREC:
1495     case PLUS_EXPR:
1496     case POINTER_PLUS_EXPR:
1497     case MULT_EXPR:
1498     case MINUS_EXPR:
1499     case NEGATE_EXPR:
1500     case SSA_NAME:
1501     case NON_LVALUE_EXPR:
1502     case BIT_NOT_EXPR:
1503     CASE_CONVERT:
1504       return true;
1505
1506     default:
1507       return false;
1508     }
1509 }
1510
1511 /* Return true when SCEV is a linear expression.  Linear expressions
1512    can contain additions, substractions and multiplications.
1513    Multiplications are restricted to constant scaling: "cst * x".  */
1514
1515 bool
1516 scev_is_linear_expression (tree scev)
1517 {
1518   if (scev == NULL
1519       || !operator_is_linear (scev))
1520     return false;
1521
1522   if (TREE_CODE (scev) == MULT_EXPR)
1523     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1524              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1525
1526   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1527       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1528     return false;
1529
1530   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1531     {
1532     case 3:
1533       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1534         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1535         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1536
1537     case 2:
1538       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1539         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1540
1541     case 1:
1542       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1543
1544     case 0:
1545       return true;
1546
1547     default:
1548       return false;
1549     }
1550 }
1551
1552 /* Determines whether the expression CHREC contains only interger consts
1553    in the right parts.  */
1554
1555 bool
1556 evolution_function_right_is_integer_cst (const_tree chrec)
1557 {
1558   if (chrec == NULL_TREE)
1559     return false;
1560
1561   switch (TREE_CODE (chrec))
1562     {
1563     case INTEGER_CST:
1564       return true;
1565
1566     case POLYNOMIAL_CHREC:
1567       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1568         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1569             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1570
1571     CASE_CONVERT:
1572       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1573
1574     default:
1575       return false;
1576     }
1577 }
1578