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           || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1015                                                      loopnum)
1016           || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1017                                                      loopnum))
1018         return false;
1019       return true;
1020     }
1021
1022   switch (TREE_OPERAND_LENGTH (chrec))
1023     {
1024     case 2:
1025       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1026                                                   loopnum))
1027         return false;
1028
1029     case 1:
1030       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1031                                                   loopnum))
1032         return false;
1033       return true;
1034
1035     default:
1036       return false;
1037     }
1038
1039   return false;
1040 }
1041
1042 /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1043
1044 bool
1045 evolution_function_is_invariant_p (tree chrec, int loopnum)
1046 {
1047   return evolution_function_is_invariant_rec_p (chrec, loopnum);
1048 }
1049
1050 /* Determine whether the given tree is an affine multivariate
1051    evolution.  */
1052
1053 bool
1054 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1055 {
1056   if (chrec == NULL_TREE)
1057     return false;
1058
1059   switch (TREE_CODE (chrec))
1060     {
1061     case POLYNOMIAL_CHREC:
1062       if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1063         {
1064           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1065             return true;
1066           else
1067             {
1068               if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1069                   && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1070                      != CHREC_VARIABLE (chrec)
1071                   && evolution_function_is_affine_multivariate_p
1072                   (CHREC_RIGHT (chrec), loopnum))
1073                 return true;
1074               else
1075                 return false;
1076             }
1077         }
1078       else
1079         {
1080           if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1081               && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1082               && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1083               && evolution_function_is_affine_multivariate_p
1084               (CHREC_LEFT (chrec), loopnum))
1085             return true;
1086           else
1087             return false;
1088         }
1089
1090     default:
1091       return false;
1092     }
1093 }
1094
1095 /* Determine whether the given tree is a function in zero or one
1096    variables.  */
1097
1098 bool
1099 evolution_function_is_univariate_p (const_tree chrec)
1100 {
1101   if (chrec == NULL_TREE)
1102     return true;
1103
1104   switch (TREE_CODE (chrec))
1105     {
1106     case POLYNOMIAL_CHREC:
1107       switch (TREE_CODE (CHREC_LEFT (chrec)))
1108         {
1109         case POLYNOMIAL_CHREC:
1110           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1111             return false;
1112           if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1113             return false;
1114           break;
1115
1116         default:
1117           break;
1118         }
1119
1120       switch (TREE_CODE (CHREC_RIGHT (chrec)))
1121         {
1122         case POLYNOMIAL_CHREC:
1123           if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1124             return false;
1125           if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1126             return false;
1127           break;
1128
1129         default:
1130           break;
1131         }
1132
1133     default:
1134       return true;
1135     }
1136 }
1137
1138 /* Returns the number of variables of CHREC.  Example: the call
1139    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1140
1141 unsigned
1142 nb_vars_in_chrec (tree chrec)
1143 {
1144   if (chrec == NULL_TREE)
1145     return 0;
1146
1147   switch (TREE_CODE (chrec))
1148     {
1149     case POLYNOMIAL_CHREC:
1150       return 1 + nb_vars_in_chrec
1151         (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1152
1153     default:
1154       return 0;
1155     }
1156 }
1157
1158 static tree chrec_convert_1 (tree, tree, gimple, bool);
1159
1160 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1161    the scev corresponds to.  AT_STMT is the statement at that the scev is
1162    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1163    the rules for overflow of the given language apply (e.g., that signed
1164    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1165    tests, but also to enforce that the result follows them.  Returns true if the
1166    conversion succeeded, false otherwise.  */
1167
1168 bool
1169 convert_affine_scev (struct loop *loop, tree type,
1170                      tree *base, tree *step, gimple at_stmt,
1171                      bool use_overflow_semantics)
1172 {
1173   tree ct = TREE_TYPE (*step);
1174   bool enforce_overflow_semantics;
1175   bool must_check_src_overflow, must_check_rslt_overflow;
1176   tree new_base, new_step;
1177   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1178
1179   /* In general,
1180      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1181      but we must check some assumptions.
1182
1183      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1184         of CT is smaller than the precision of TYPE.  For example, when we
1185         cast unsigned char [254, +, 1] to unsigned, the values on left side
1186         are 254, 255, 0, 1, ..., but those on the right side are
1187         254, 255, 256, 257, ...
1188      2) In case that we must also preserve the fact that signed ivs do not
1189         overflow, we must additionally check that the new iv does not wrap.
1190         For example, unsigned char [125, +, 1] casted to signed char could
1191         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1192         which would confuse optimizers that assume that this does not
1193         happen.  */
1194   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1195
1196   enforce_overflow_semantics = (use_overflow_semantics
1197                                 && nowrap_type_p (type));
1198   if (enforce_overflow_semantics)
1199     {
1200       /* We can avoid checking whether the result overflows in the following
1201          cases:
1202
1203          -- must_check_src_overflow is true, and the range of TYPE is superset
1204             of the range of CT -- i.e., in all cases except if CT signed and
1205             TYPE unsigned.
1206          -- both CT and TYPE have the same precision and signedness, and we
1207             verify instead that the source does not overflow (this may be
1208             easier than verifying it for the result, as we may use the
1209             information about the semantics of overflow in CT).  */
1210       if (must_check_src_overflow)
1211         {
1212           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1213             must_check_rslt_overflow = true;
1214           else
1215             must_check_rslt_overflow = false;
1216         }
1217       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1218                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1219         {
1220           must_check_rslt_overflow = false;
1221           must_check_src_overflow = true;
1222         }
1223       else
1224         must_check_rslt_overflow = true;
1225     }
1226   else
1227     must_check_rslt_overflow = false;
1228
1229   if (must_check_src_overflow
1230       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1231                                 use_overflow_semantics))
1232     return false;
1233
1234   new_base = chrec_convert_1 (type, *base, at_stmt,
1235                               use_overflow_semantics);
1236   /* The step must be sign extended, regardless of the signedness
1237      of CT and TYPE.  This only needs to be handled specially when
1238      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1239      (with values 100, 99, 98, ...) from becoming signed or unsigned
1240      [100, +, 255] with values 100, 355, ...; the sign-extension is
1241      performed by default when CT is signed.  */
1242   new_step = *step;
1243   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1244     {
1245       tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1246       new_step = chrec_convert_1 (signed_ct, new_step, at_stmt,
1247                                   use_overflow_semantics);
1248     }
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
1437     case PLUS_EXPR:
1438     case MULT_EXPR:
1439     case MINUS_EXPR:
1440     case POINTER_PLUS_EXPR:
1441       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1442                               TREE_OPERAND (chrec1, 0))
1443           && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1444                               TREE_OPERAND (chrec1, 1));
1445
1446     default:
1447       return false;
1448     }
1449 }
1450
1451 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1452    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1453    which of these cases happens.  */
1454
1455 enum ev_direction
1456 scev_direction (const_tree chrec)
1457 {
1458   const_tree step;
1459
1460   if (!evolution_function_is_affine_p (chrec))
1461     return EV_DIR_UNKNOWN;
1462
1463   step = CHREC_RIGHT (chrec);
1464   if (TREE_CODE (step) != INTEGER_CST)
1465     return EV_DIR_UNKNOWN;
1466
1467   if (tree_int_cst_sign_bit (step))
1468     return EV_DIR_DECREASES;
1469   else
1470     return EV_DIR_GROWS;
1471 }
1472
1473 /* Iterates over all the components of SCEV, and calls CBCK.  */
1474
1475 void
1476 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1477 {
1478   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1479     {
1480     case 3:
1481       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1482
1483     case 2:
1484       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1485
1486     case 1:
1487       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1488
1489     default:
1490       cbck (scev, data);
1491       break;
1492     }
1493 }
1494
1495 /* Returns true when the operation can be part of a linear
1496    expression.  */
1497
1498 static inline bool
1499 operator_is_linear (tree scev)
1500 {
1501   switch (TREE_CODE (scev))
1502     {
1503     case INTEGER_CST:
1504     case POLYNOMIAL_CHREC:
1505     case PLUS_EXPR:
1506     case POINTER_PLUS_EXPR:
1507     case MULT_EXPR:
1508     case MINUS_EXPR:
1509     case NEGATE_EXPR:
1510     case SSA_NAME:
1511     case NON_LVALUE_EXPR:
1512     case BIT_NOT_EXPR:
1513     CASE_CONVERT:
1514       return true;
1515
1516     default:
1517       return false;
1518     }
1519 }
1520
1521 /* Return true when SCEV is a linear expression.  Linear expressions
1522    can contain additions, substractions and multiplications.
1523    Multiplications are restricted to constant scaling: "cst * x".  */
1524
1525 bool
1526 scev_is_linear_expression (tree scev)
1527 {
1528   if (scev == NULL
1529       || !operator_is_linear (scev))
1530     return false;
1531
1532   if (TREE_CODE (scev) == MULT_EXPR)
1533     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1534              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1535
1536   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1537       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1538     return false;
1539
1540   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1541     {
1542     case 3:
1543       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1544         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1545         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1546
1547     case 2:
1548       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1549         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1550
1551     case 1:
1552       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1553
1554     case 0:
1555       return true;
1556
1557     default:
1558       return false;
1559     }
1560 }
1561
1562 /* Determines whether the expression CHREC contains only interger consts
1563    in the right parts.  */
1564
1565 bool
1566 evolution_function_right_is_integer_cst (const_tree chrec)
1567 {
1568   if (chrec == NULL_TREE)
1569     return false;
1570
1571   switch (TREE_CODE (chrec))
1572     {
1573     case INTEGER_CST:
1574       return true;
1575
1576     case POLYNOMIAL_CHREC:
1577       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1578         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1579             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1580
1581     CASE_CONVERT:
1582       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1583
1584     default:
1585       return false;
1586     }
1587 }