gcc/tree-chrec.c

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