gcc/tree-chrec.c

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