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