gcc/tree-chrec.c

   1 /* Chains of recurrences.
   2    Copyright (C) 2003-2014 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 "tree.h"
  30 #include "tree-pretty-print.h"
  31 #include "cfgloop.h"
  32 #include "predict.h"
  33 #include "vec.h"
  34 #include "hashtab.h"
  35 #include "hash-set.h"
  36 #include "machmode.h"
  37 #include "tm.h"
  38 #include "hard-reg-set.h"
  39 #include "input.h"
  40 #include "function.h"
  41 #include "dominance.h"
  42 #include "cfg.h"
  43 #include "basic-block.h"
  44 #include "gimple-expr.h"
  45 #include "tree-ssa-loop-ivopts.h"
  46 #include "tree-ssa-loop-niter.h"
  47 #include "tree-chrec.h"
  48 #include "dumpfile.h"
  49 #include "params.h"
  50 #include "tree-scalar-evolution.h"
  51
  52 /* Extended folder for chrecs.  */
  53
  54 /* Determines whether CST is not a constant evolution.  */
  55
  56 static inline bool
  57 is_not_constant_evolution (const_tree cst)
  58 {
  59   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
  60 }
  61
  62 /* Fold CODE for a polynomial function and a constant.  */
  63
  64 static inline tree
  65 chrec_fold_poly_cst (enum tree_code code,
  66                      tree type,
  67                      tree poly,
  68                      tree cst)
  69 {
  70   gcc_assert (poly);
  71   gcc_assert (cst);
  72   gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
  73   gcc_assert (!is_not_constant_evolution (cst));
  74   gcc_assert (type == chrec_type (poly));
  75
  76   switch (code)
  77     {
  78     case PLUS_EXPR:
  79       return build_polynomial_chrec
  80         (CHREC_VARIABLE (poly),
  81          chrec_fold_plus (type, CHREC_LEFT (poly), cst),
  82          CHREC_RIGHT (poly));
  83
  84     case MINUS_EXPR:
  85       return build_polynomial_chrec
  86         (CHREC_VARIABLE (poly),
  87          chrec_fold_minus (type, CHREC_LEFT (poly), cst),
  88          CHREC_RIGHT (poly));
  89
  90     case MULT_EXPR:
  91       return build_polynomial_chrec
  92         (CHREC_VARIABLE (poly),
  93          chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
  94          chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
  95
  96     default:
  97       return chrec_dont_know;
  98     }
  99 }
 100
 101 /* Fold the addition of two polynomial functions.  */
 102
 103 static inline tree
 104 chrec_fold_plus_poly_poly (enum tree_code code,
 105                            tree type,
 106                            tree poly0,
 107                            tree poly1)
 108 {
 109   tree left, right;
 110   struct loop *loop0 = get_chrec_loop (poly0);
 111   struct loop *loop1 = get_chrec_loop (poly1);
 112   tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
 113
 114   gcc_assert (poly0);
 115   gcc_assert (poly1);
 116   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
 117   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
 118   if (POINTER_TYPE_P (chrec_type (poly0)))
 119     gcc_assert (ptrofftype_p (chrec_type (poly1)));
 120   else
 121     gcc_assert (chrec_type (poly0) == chrec_type (poly1));
 122   gcc_assert (type == chrec_type (poly0));
 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_assert (chrec_type (poly0) == chrec_type (poly1));
 204   gcc_assert (type == chrec_type (poly0));
 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 static tree chrec_convert_1 (tree, tree, gimple, bool);
1173
1174 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1175    the scev corresponds to.  AT_STMT is the statement at that the scev is
1176    evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1177    the rules for overflow of the given language apply (e.g., that signed
1178    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1179    tests, but also to enforce that the result follows them.  Returns true if the
1180    conversion succeeded, false otherwise.  */
1181
1182 bool
1183 convert_affine_scev (struct loop *loop, tree type,
1184                      tree *base, tree *step, gimple at_stmt,
1185                      bool use_overflow_semantics)
1186 {
1187   tree ct = TREE_TYPE (*step);
1188   bool enforce_overflow_semantics;
1189   bool must_check_src_overflow, must_check_rslt_overflow;
1190   tree new_base, new_step;
1191   tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1192
1193   /* In general,
1194      (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1195      but we must check some assumptions.
1196
1197      1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1198         of CT is smaller than the precision of TYPE.  For example, when we
1199         cast unsigned char [254, +, 1] to unsigned, the values on left side
1200         are 254, 255, 0, 1, ..., but those on the right side are
1201         254, 255, 256, 257, ...
1202      2) In case that we must also preserve the fact that signed ivs do not
1203         overflow, we must additionally check that the new iv does not wrap.
1204         For example, unsigned char [125, +, 1] casted to signed char could
1205         become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1206         which would confuse optimizers that assume that this does not
1207         happen.  */
1208   must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1209
1210   enforce_overflow_semantics = (use_overflow_semantics
1211                                 && nowrap_type_p (type));
1212   if (enforce_overflow_semantics)
1213     {
1214       /* We can avoid checking whether the result overflows in the following
1215          cases:
1216
1217          -- must_check_src_overflow is true, and the range of TYPE is superset
1218             of the range of CT -- i.e., in all cases except if CT signed and
1219             TYPE unsigned.
1220          -- both CT and TYPE have the same precision and signedness, and we
1221             verify instead that the source does not overflow (this may be
1222             easier than verifying it for the result, as we may use the
1223             information about the semantics of overflow in CT).  */
1224       if (must_check_src_overflow)
1225         {
1226           if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1227             must_check_rslt_overflow = true;
1228           else
1229             must_check_rslt_overflow = false;
1230         }
1231       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1232                && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1233         {
1234           must_check_rslt_overflow = false;
1235           must_check_src_overflow = true;
1236         }
1237       else
1238         must_check_rslt_overflow = true;
1239     }
1240   else
1241     must_check_rslt_overflow = false;
1242
1243   if (must_check_src_overflow
1244       && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1245                                 use_overflow_semantics))
1246     return false;
1247
1248   new_base = chrec_convert_1 (type, *base, at_stmt,
1249                               use_overflow_semantics);
1250   /* The step must be sign extended, regardless of the signedness
1251      of CT and TYPE.  This only needs to be handled specially when
1252      CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1253      (with values 100, 99, 98, ...) from becoming signed or unsigned
1254      [100, +, 255] with values 100, 355, ...; the sign-extension is
1255      performed by default when CT is signed.  */
1256   new_step = *step;
1257   if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1258     {
1259       tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1260       new_step = chrec_convert_1 (signed_ct, new_step, at_stmt,
1261                                   use_overflow_semantics);
1262     }
1263   new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
1264
1265   if (automatically_generated_chrec_p (new_base)
1266       || automatically_generated_chrec_p (new_step))
1267     return false;
1268
1269   if (must_check_rslt_overflow
1270       /* Note that in this case we cannot use the fact that signed variables
1271          do not overflow, as this is what we are verifying for the new iv.  */
1272       && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1273     return false;
1274
1275   *base = new_base;
1276   *step = new_step;
1277   return true;
1278 }
1279 \f
1280
1281 /* Convert CHREC for the right hand side of a CHREC.
1282    The increment for a pointer type is always sizetype.  */
1283
1284 tree
1285 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
1286 {
1287   if (POINTER_TYPE_P (type))
1288     type = sizetype;
1289
1290   return chrec_convert (type, chrec, at_stmt);
1291 }
1292
1293 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1294    which the CHREC is built, it sets AT_STMT to the statement that
1295    contains the definition of the analyzed variable, otherwise the
1296    conversion is less accurate: the information is used for
1297    determining a more accurate estimation of the number of iterations.
1298    By default AT_STMT could be safely set to NULL_TREE.
1299
1300    The following rule is always true: TREE_TYPE (chrec) ==
1301    TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1302    An example of what could happen when adding two chrecs and the type
1303    of the CHREC_RIGHT is different than CHREC_LEFT is:
1304
1305    {(uint) 0, +, (uchar) 10} +
1306    {(uint) 0, +, (uchar) 250}
1307
1308    that would produce a wrong result if CHREC_RIGHT is not (uint):
1309
1310    {(uint) 0, +, (uchar) 4}
1311
1312    instead of
1313
1314    {(uint) 0, +, (uint) 260}
1315 */
1316
1317 tree
1318 chrec_convert (tree type, tree chrec, gimple at_stmt)
1319 {
1320   return chrec_convert_1 (type, chrec, at_stmt, true);
1321 }
1322
1323 /* Convert CHREC to TYPE.  When the analyzer knows the context in
1324    which the CHREC is built, it sets AT_STMT to the statement that
1325    contains the definition of the analyzed variable, otherwise the
1326    conversion is less accurate: the information is used for
1327    determining a more accurate estimation of the number of iterations.
1328    By default AT_STMT could be safely set to NULL_TREE.
1329
1330    USE_OVERFLOW_SEMANTICS is true if this function should assume that
1331    the rules for overflow of the given language apply (e.g., that signed
1332    arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1333    tests, but also to enforce that the result follows them.  */
1334
1335 static tree
1336 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
1337                  bool use_overflow_semantics)
1338 {
1339   tree ct, res;
1340   tree base, step;
1341   struct loop *loop;
1342
1343   if (automatically_generated_chrec_p (chrec))
1344     return chrec;
1345
1346   ct = chrec_type (chrec);
1347   if (ct == type)
1348     return chrec;
1349
1350   if (!evolution_function_is_affine_p (chrec))
1351     goto keep_cast;
1352
1353   loop = get_chrec_loop (chrec);
1354   base = CHREC_LEFT (chrec);
1355   step = CHREC_RIGHT (chrec);
1356
1357   if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1358                            use_overflow_semantics))
1359     return build_polynomial_chrec (loop->num, base, step);
1360
1361   /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1362 keep_cast:
1363   /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1364      may be more expensive.  We do want to perform this optimization here
1365      though for canonicalization reasons.  */
1366   if (use_overflow_semantics
1367       && (TREE_CODE (chrec) == PLUS_EXPR
1368           || TREE_CODE (chrec) == MINUS_EXPR)
1369       && TREE_CODE (type) == INTEGER_TYPE
1370       && TREE_CODE (ct) == INTEGER_TYPE
1371       && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1372       && TYPE_OVERFLOW_UNDEFINED (ct))
1373     res = fold_build2 (TREE_CODE (chrec), type,
1374                        fold_convert (type, TREE_OPERAND (chrec, 0)),
1375                        fold_convert (type, TREE_OPERAND (chrec, 1)));
1376   /* Similar perform the trick that (signed char)((int)x + 2) can be
1377      narrowed to (signed char)((unsigned char)x + 2).  */
1378   else if (use_overflow_semantics
1379            && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1380            && TREE_CODE (ct) == INTEGER_TYPE
1381            && TREE_CODE (type) == INTEGER_TYPE
1382            && TYPE_OVERFLOW_UNDEFINED (type)
1383            && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1384     {
1385       tree utype = unsigned_type_for (type);
1386       res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1387                                     fold_convert (utype,
1388                                                   CHREC_LEFT (chrec)),
1389                                     fold_convert (utype,
1390                                                   CHREC_RIGHT (chrec)));
1391       res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics);
1392     }
1393   else
1394     res = fold_convert (type, chrec);
1395
1396   /* Don't propagate overflows.  */
1397   if (CONSTANT_CLASS_P (res))
1398     TREE_OVERFLOW (res) = 0;
1399
1400   /* But reject constants that don't fit in their type after conversion.
1401      This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1402      natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1403      and can cause problems later when computing niters of loops.  Note
1404      that we don't do the check before converting because we don't want
1405      to reject conversions of negative chrecs to unsigned types.  */
1406   if (TREE_CODE (res) == INTEGER_CST
1407       && TREE_CODE (type) == INTEGER_TYPE
1408       && !int_fits_type_p (res, type))
1409     res = chrec_dont_know;
1410
1411   return res;
1412 }
1413
1414 /* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1415    chrec if something else than what chrec_convert would do happens, NULL_TREE
1416    otherwise.  */
1417
1418 tree
1419 chrec_convert_aggressive (tree type, tree chrec)
1420 {
1421   tree inner_type, left, right, lc, rc, rtype;
1422
1423   if (automatically_generated_chrec_p (chrec)
1424       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1425     return NULL_TREE;
1426
1427   inner_type = TREE_TYPE (chrec);
1428   if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1429     return NULL_TREE;
1430
1431   rtype = POINTER_TYPE_P (type) ? sizetype : type;
1432
1433   left = CHREC_LEFT (chrec);
1434   right = CHREC_RIGHT (chrec);
1435   lc = chrec_convert_aggressive (type, left);
1436   if (!lc)
1437     lc = chrec_convert (type, left, NULL);
1438   rc = chrec_convert_aggressive (rtype, right);
1439   if (!rc)
1440     rc = chrec_convert (rtype, right, NULL);
1441
1442   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1443 }
1444
1445 /* Returns true when CHREC0 == CHREC1.  */
1446
1447 bool
1448 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1449 {
1450   if (chrec0 == NULL_TREE
1451       || chrec1 == NULL_TREE
1452       || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1453     return false;
1454
1455   if (chrec0 == chrec1)
1456     return true;
1457
1458   switch (TREE_CODE (chrec0))
1459     {
1460     case INTEGER_CST:
1461       return operand_equal_p (chrec0, chrec1, 0);
1462
1463     case POLYNOMIAL_CHREC:
1464       return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1465               && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1466               && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1467
1468     case PLUS_EXPR:
1469     case MULT_EXPR:
1470     case MINUS_EXPR:
1471     case POINTER_PLUS_EXPR:
1472       return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1473                               TREE_OPERAND (chrec1, 0))
1474           && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1475                               TREE_OPERAND (chrec1, 1));
1476
1477     default:
1478       return false;
1479     }
1480 }
1481
1482 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1483    EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1484    which of these cases happens.  */
1485
1486 enum ev_direction
1487 scev_direction (const_tree chrec)
1488 {
1489   const_tree step;
1490
1491   if (!evolution_function_is_affine_p (chrec))
1492     return EV_DIR_UNKNOWN;
1493
1494   step = CHREC_RIGHT (chrec);
1495   if (TREE_CODE (step) != INTEGER_CST)
1496     return EV_DIR_UNKNOWN;
1497
1498   if (tree_int_cst_sign_bit (step))
1499     return EV_DIR_DECREASES;
1500   else
1501     return EV_DIR_GROWS;
1502 }
1503
1504 /* Iterates over all the components of SCEV, and calls CBCK.  */
1505
1506 void
1507 for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1508 {
1509   switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1510     {
1511     case 3:
1512       for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1513
1514     case 2:
1515       for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1516
1517     case 1:
1518       for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1519
1520     default:
1521       cbck (scev, data);
1522       break;
1523     }
1524 }
1525
1526 /* Returns true when the operation can be part of a linear
1527    expression.  */
1528
1529 static inline bool
1530 operator_is_linear (tree scev)
1531 {
1532   switch (TREE_CODE (scev))
1533     {
1534     case INTEGER_CST:
1535     case POLYNOMIAL_CHREC:
1536     case PLUS_EXPR:
1537     case POINTER_PLUS_EXPR:
1538     case MULT_EXPR:
1539     case MINUS_EXPR:
1540     case NEGATE_EXPR:
1541     case SSA_NAME:
1542     case NON_LVALUE_EXPR:
1543     case BIT_NOT_EXPR:
1544     CASE_CONVERT:
1545       return true;
1546
1547     default:
1548       return false;
1549     }
1550 }
1551
1552 /* Return true when SCEV is a linear expression.  Linear expressions
1553    can contain additions, substractions and multiplications.
1554    Multiplications are restricted to constant scaling: "cst * x".  */
1555
1556 bool
1557 scev_is_linear_expression (tree scev)
1558 {
1559   if (scev == NULL
1560       || !operator_is_linear (scev))
1561     return false;
1562
1563   if (TREE_CODE (scev) == MULT_EXPR)
1564     return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1565              && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1566
1567   if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1568       && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1569     return false;
1570
1571   switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1572     {
1573     case 3:
1574       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1575         && scev_is_linear_expression (TREE_OPERAND (scev, 1))
1576         && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1577
1578     case 2:
1579       return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1580         && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1581
1582     case 1:
1583       return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1584
1585     case 0:
1586       return true;
1587
1588     default:
1589       return false;
1590     }
1591 }
1592
1593 /* Determines whether the expression CHREC contains only interger consts
1594    in the right parts.  */
1595
1596 bool
1597 evolution_function_right_is_integer_cst (const_tree chrec)
1598 {
1599   if (chrec == NULL_TREE)
1600     return false;
1601
1602   switch (TREE_CODE (chrec))
1603     {
1604     case INTEGER_CST:
1605       return true;
1606
1607     case POLYNOMIAL_CHREC:
1608       return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1609         && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1610             || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1611
1612     CASE_CONVERT:
1613       return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1614
1615     default:
1616       return false;
1617     }
1618 }