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