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