gcc/tree-chrec.c

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