gcc/tree-chrec.c

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