gcc/tree-chrec.c

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