gcc/tree-chrec.c

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