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