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