gcc/tree-chrec.c

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