gcc/tree-ssa-loop-niter.c

   1 /* Functions to determine/estimate number of iterations of a loop.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "cfgloop.h"
  35 #include "tree-pass.h"
  36 #include "ggc.h"
  37 #include "tree-chrec.h"
  38 #include "tree-scalar-evolution.h"
  39 #include "tree-data-ref.h"
  40 #include "params.h"
  41 #include "flags.h"
  42 #include "tree-inline.h"
  43
  44 #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
  45
  46
  47 /*
  48
  49    Analysis of number of iterations of an affine exit test.
  50
  51 */
  52
  53 /* Returns true if ARG is either NULL_TREE or constant zero.  Unlike
  54    integer_zerop, it does not care about overflow flags.  */
  55
  56 bool
  57 zero_p (tree arg)
  58 {
  59   if (!arg)
  60     return true;
  61
  62   if (TREE_CODE (arg) != INTEGER_CST)
  63     return false;
  64
  65   return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
  66 }
  67
  68 /* Returns true if ARG a nonzero constant.  Unlike integer_nonzerop, it does
  69    not care about overflow flags.  */
  70
  71 static bool
  72 nonzero_p (tree arg)
  73 {
  74   if (!arg)
  75     return false;
  76
  77   if (TREE_CODE (arg) != INTEGER_CST)
  78     return false;
  79
  80   return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
  81 }
  82
  83 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
  84
  85 static tree
  86 inverse (tree x, tree mask)
  87 {
  88   tree type = TREE_TYPE (x);
  89   tree rslt;
  90   unsigned ctr = tree_floor_log2 (mask);
  91
  92   if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
  93     {
  94       unsigned HOST_WIDE_INT ix;
  95       unsigned HOST_WIDE_INT imask;
  96       unsigned HOST_WIDE_INT irslt = 1;
  97
  98       gcc_assert (cst_and_fits_in_hwi (x));
  99       gcc_assert (cst_and_fits_in_hwi (mask));
 100
 101       ix = int_cst_value (x);
 102       imask = int_cst_value (mask);
 103
 104       for (; ctr; ctr--)
 105         {
 106           irslt *= ix;
 107           ix *= ix;
 108         }
 109       irslt &= imask;
 110
 111       rslt = build_int_cst_type (type, irslt);
 112     }
 113   else
 114     {
 115       rslt = build_int_cst_type (type, 1);
 116       for (; ctr; ctr--)
 117         {
 118           rslt = fold_binary_to_constant (MULT_EXPR, type, rslt, x);
 119           x = fold_binary_to_constant (MULT_EXPR, type, x, x);
 120         }
 121       rslt = fold_binary_to_constant (BIT_AND_EXPR, type, rslt, mask);
 122     }
 123
 124   return rslt;
 125 }
 126
 127 /* Determine the number of iterations according to condition (for staying
 128    inside loop) which compares two induction variables using comparison
 129    operator CODE.  The induction variable on left side of the comparison
 130    has base BASE0 and step STEP0. the right-hand side one has base
 131    BASE1 and step STEP1.  Both induction variables must have type TYPE,
 132    which must be an integer or pointer type.  STEP0 and STEP1 must be
 133    constants (or NULL_TREE, which is interpreted as constant zero).
 134
 135    The results (number of iterations and assumptions as described in
 136    comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
 137    In case we are unable to determine number of iterations, contents of
 138    this structure is unchanged.  */
 139
 140 static void
 141 number_of_iterations_cond (tree type, tree base0, tree step0,
 142                            enum tree_code code, tree base1, tree step1,
 143                            struct tree_niter_desc *niter)
 144 {
 145   tree step, delta, mmin, mmax;
 146   tree may_xform, bound, s, d, tmp;
 147   bool was_sharp = false;
 148   tree assumption;
 149   tree assumptions = boolean_true_node;
 150   tree noloop_assumptions = boolean_false_node;
 151   tree niter_type, signed_niter_type;
 152   tree bits;
 153
 154   /* The meaning of these assumptions is this:
 155      if !assumptions
 156        then the rest of information does not have to be valid
 157      if noloop_assumptions then the loop does not have to roll
 158        (but it is only conservative approximation, i.e. it only says that
 159        if !noloop_assumptions, then the loop does not end before the computed
 160        number of iterations)  */
 161
 162   /* Make < comparison from > ones.  */
 163   if (code == GE_EXPR
 164       || code == GT_EXPR)
 165     {
 166       SWAP (base0, base1);
 167       SWAP (step0, step1);
 168       code = swap_tree_comparison (code);
 169     }
 170
 171   /* We can handle the case when neither of the sides of the comparison is
 172      invariant, provided that the test is NE_EXPR.  This rarely occurs in
 173      practice, but it is simple enough to manage.  */
 174   if (!zero_p (step0) && !zero_p (step1))
 175     {
 176       if (code != NE_EXPR)
 177         return;
 178
 179       step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1);
 180       step1 = NULL_TREE;
 181     }
 182
 183   /* If the result is a constant,  the loop is weird.  More precise handling
 184      would be possible, but the situation is not common enough to waste time
 185      on it.  */
 186   if (zero_p (step0) && zero_p (step1))
 187     return;
 188
 189   /* Ignore loops of while (i-- < 10) type.  */
 190   if (code != NE_EXPR)
 191     {
 192       if (step0 && tree_int_cst_sign_bit (step0))
 193         return;
 194
 195       if (!zero_p (step1) && !tree_int_cst_sign_bit (step1))
 196         return;
 197     }
 198
 199   if (POINTER_TYPE_P (type))
 200     {
 201       /* We assume pointer arithmetic never overflows.  */
 202       mmin = mmax = NULL_TREE;
 203     }
 204   else
 205     {
 206       mmin = TYPE_MIN_VALUE (type);
 207       mmax = TYPE_MAX_VALUE (type);
 208     }
 209
 210   /* Some more condition normalization.  We must record some assumptions
 211      due to overflows.  */
 212
 213   if (code == LT_EXPR)
 214     {
 215       /* We want to take care only of <=; this is easy,
 216          as in cases the overflow would make the transformation unsafe the loop
 217          does not roll.  Seemingly it would make more sense to want to take
 218          care of <, as NE is more similar to it, but the problem is that here
 219          the transformation would be more difficult due to possibly infinite
 220          loops.  */
 221       if (zero_p (step0))
 222         {
 223           if (mmax)
 224             assumption = fold_build2 (EQ_EXPR, boolean_type_node, base0, mmax);
 225           else
 226             assumption = boolean_false_node;
 227           if (nonzero_p (assumption))
 228             goto zero_iter;
 229           base0 = fold_build2 (PLUS_EXPR, type, base0,
 230                                build_int_cst_type (type, 1));
 231         }
 232       else
 233         {
 234           if (mmin)
 235             assumption = fold_build2 (EQ_EXPR, boolean_type_node, base1, mmin);
 236           else
 237             assumption = boolean_false_node;
 238           if (nonzero_p (assumption))
 239             goto zero_iter;
 240           base1 = fold_build2 (MINUS_EXPR, type, base1,
 241                                build_int_cst_type (type, 1));
 242         }
 243       noloop_assumptions = assumption;
 244       code = LE_EXPR;
 245
 246       /* It will be useful to be able to tell the difference once more in
 247          <= -> != reduction.  */
 248       was_sharp = true;
 249     }
 250
 251   /* Take care of trivially infinite loops.  */
 252   if (code != NE_EXPR)
 253     {
 254       if (zero_p (step0)
 255           && mmin
 256           && operand_equal_p (base0, mmin, 0))
 257         return;
 258       if (zero_p (step1)
 259           && mmax
 260           && operand_equal_p (base1, mmax, 0))
 261         return;
 262     }
 263
 264   /* If we can we want to take care of NE conditions instead of size
 265      comparisons, as they are much more friendly (most importantly
 266      this takes care of special handling of loops with step 1).  We can
 267      do it if we first check that upper bound is greater or equal to
 268      lower bound, their difference is constant c modulo step and that
 269      there is not an overflow.  */
 270   if (code != NE_EXPR)
 271     {
 272       if (zero_p (step0))
 273         step = fold_unary_to_constant (NEGATE_EXPR, type, step1);
 274       else
 275         step = step0;
 276       delta = build2 (MINUS_EXPR, type, base1, base0);
 277       delta = fold_build2 (FLOOR_MOD_EXPR, type, delta, step);
 278       may_xform = boolean_false_node;
 279
 280       if (TREE_CODE (delta) == INTEGER_CST)
 281         {
 282           tmp = fold_binary_to_constant (MINUS_EXPR, type, step,
 283                                          build_int_cst_type (type, 1));
 284           if (was_sharp
 285               && operand_equal_p (delta, tmp, 0))
 286             {
 287               /* A special case.  We have transformed condition of type
 288                  for (i = 0; i < 4; i += 4)
 289                  into
 290                  for (i = 0; i <= 3; i += 4)
 291                  obviously if the test for overflow during that transformation
 292                  passed, we cannot overflow here.  Most importantly any
 293                  loop with sharp end condition and step 1 falls into this
 294                  category, so handling this case specially is definitely
 295                  worth the troubles.  */
 296               may_xform = boolean_true_node;
 297             }
 298           else if (zero_p (step0))
 299             {
 300               if (!mmin)
 301                 may_xform = boolean_true_node;
 302               else
 303                 {
 304                   bound = fold_binary_to_constant (PLUS_EXPR, type,
 305                                                    mmin, step);
 306                   bound = fold_binary_to_constant (MINUS_EXPR, type,
 307                                                    bound, delta);
 308                   may_xform = fold_build2 (LE_EXPR, boolean_type_node,
 309                                            bound, base0);
 310                 }
 311             }
 312           else
 313             {
 314               if (!mmax)
 315                 may_xform = boolean_true_node;
 316               else
 317                 {
 318                   bound = fold_binary_to_constant (MINUS_EXPR, type,
 319                                                    mmax, step);
 320                   bound = fold_binary_to_constant (PLUS_EXPR, type,
 321                                                    bound, delta);
 322                   may_xform = fold_build2 (LE_EXPR, boolean_type_node,
 323                                            base1, bound);
 324                 }
 325             }
 326         }
 327
 328       if (!zero_p (may_xform))
 329         {
 330           /* We perform the transformation always provided that it is not
 331              completely senseless.  This is OK, as we would need this assumption
 332              to determine the number of iterations anyway.  */
 333           if (!nonzero_p (may_xform))
 334             assumptions = may_xform;
 335
 336           if (zero_p (step0))
 337             {
 338               base0 = fold_build2 (PLUS_EXPR, type, base0, delta);
 339               base0 = fold_build2 (MINUS_EXPR, type, base0, step);
 340             }
 341           else
 342             {
 343               base1 = fold_build2 (MINUS_EXPR, type, base1, delta);
 344               base1 = fold_build2 (PLUS_EXPR, type, base1, step);
 345             }
 346
 347           assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, base1);
 348           noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
 349                                             noloop_assumptions, assumption);
 350           code = NE_EXPR;
 351         }
 352     }
 353
 354   /* Count the number of iterations.  */
 355   niter_type = unsigned_type_for (type);
 356   signed_niter_type = signed_type_for (type);
 357
 358   if (code == NE_EXPR)
 359     {
 360       /* Everything we do here is just arithmetics modulo size of mode.  This
 361          makes us able to do more involved computations of number of iterations
 362          than in other cases.  First transform the condition into shape
 363          s * i <> c, with s positive.  */
 364       base1 = fold_build2 (MINUS_EXPR, type, base1, base0);
 365       base0 = NULL_TREE;
 366       if (!zero_p (step1))
 367         step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
 368       step1 = NULL_TREE;
 369       if (tree_int_cst_sign_bit (fold_convert (signed_niter_type, step0)))
 370         {
 371           step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
 372           base1 = fold_build1 (NEGATE_EXPR, type, base1);
 373         }
 374
 375       base1 = fold_convert (niter_type, base1);
 376       step0 = fold_convert (niter_type, step0);
 377
 378       /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
 379          is infinite.  Otherwise, the number of iterations is
 380          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
 381       bits = num_ending_zeros (step0);
 382       d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
 383                                    build_int_cst_type (niter_type, 1), bits);
 384       s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, step0, bits);
 385
 386       bound = build_low_bits_mask (niter_type,
 387                                    (TYPE_PRECISION (niter_type)
 388                                     - tree_low_cst (bits, 1)));
 389
 390       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, base1, d);
 391       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
 392                                 assumption,
 393                                 build_int_cst (niter_type, 0));
 394       assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 395                                  assumptions, assumption);
 396
 397       tmp = fold_build2 (EXACT_DIV_EXPR, niter_type, base1, d);
 398       tmp = fold_build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound));
 399       niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
 400     }
 401   else
 402     {
 403       if (zero_p (step1))
 404         /* Condition in shape a + s * i <= b
 405            We must know that b + s does not overflow and a <= b + s and then we
 406            can compute number of iterations as (b + s - a) / s.  (It might
 407            seem that we in fact could be more clever about testing the b + s
 408            overflow condition using some information about b - a mod s,
 409            but it was already taken into account during LE -> NE transform).  */
 410         {
 411           if (mmax)
 412             {
 413               bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0);
 414               assumption = fold_build2 (LE_EXPR, boolean_type_node,
 415                                         base1, bound);
 416               assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 417                                          assumptions, assumption);
 418             }
 419
 420           step = step0;
 421           tmp = fold_build2 (PLUS_EXPR, type, base1, step0);
 422           assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, tmp);
 423           delta = fold_build2 (PLUS_EXPR, type, base1, step);
 424           delta = fold_build2 (MINUS_EXPR, type, delta, base0);
 425           delta = fold_convert (niter_type, delta);
 426         }
 427       else
 428         {
 429           /* Condition in shape a <= b - s * i
 430              We must know that a - s does not overflow and a - s <= b and then
 431              we can again compute number of iterations as (b - (a - s)) / s.  */
 432           if (mmin)
 433             {
 434               bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
 435               assumption = fold_build2 (LE_EXPR, boolean_type_node,
 436                                         bound, base0);
 437               assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 438                                          assumptions, assumption);
 439             }
 440           step = fold_build1 (NEGATE_EXPR, type, step1);
 441           tmp = fold_build2 (PLUS_EXPR, type, base0, step1);
 442           assumption = fold_build2 (GT_EXPR, boolean_type_node, tmp, base1);
 443           delta = fold_build2 (MINUS_EXPR, type, base0, step);
 444           delta = fold_build2 (MINUS_EXPR, type, base1, delta);
 445           delta = fold_convert (niter_type, delta);
 446         }
 447       noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
 448                                         noloop_assumptions, assumption);
 449       delta = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta,
 450                            fold_convert (niter_type, step));
 451       niter->niter = delta;
 452     }
 453
 454   niter->assumptions = assumptions;
 455   niter->may_be_zero = noloop_assumptions;
 456   return;
 457
 458 zero_iter:
 459   niter->assumptions = boolean_true_node;
 460   niter->may_be_zero = boolean_true_node;
 461   niter->niter = build_int_cst_type (type, 0);
 462   return;
 463 }
 464
 465
 466 /* Similar to number_of_iterations_cond, but only handles the special
 467    case of loops with step 1 or -1.  The meaning of the arguments
 468    is the same as in number_of_iterations_cond.  The function
 469    returns true if the special case was recognized, false otherwise.  */
 470
 471 static bool
 472 number_of_iterations_special (tree type, tree base0, tree step0,
 473                               enum tree_code code, tree base1, tree step1,
 474                               struct tree_niter_desc *niter)
 475 {
 476   tree niter_type = unsigned_type_for (type), mmax, mmin;
 477
 478   /* Make < comparison from > ones.  */
 479   if (code == GE_EXPR
 480       || code == GT_EXPR)
 481     {
 482       SWAP (base0, base1);
 483       SWAP (step0, step1);
 484       code = swap_tree_comparison (code);
 485     }
 486
 487   switch (code)
 488     {
 489     case NE_EXPR:
 490       if (zero_p (step0))
 491         {
 492           if (zero_p (step1))
 493             return false;
 494           SWAP (base0, base1);
 495           SWAP (step0, step1);
 496         }
 497       else if (!zero_p (step1))
 498         return false;
 499
 500       if (integer_onep (step0))
 501         {
 502           /* for (i = base0; i != base1; i++)  */
 503           niter->assumptions = boolean_true_node;
 504           niter->may_be_zero = boolean_false_node;
 505           niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
 506           niter->additional_info = boolean_true_node;
 507         }
 508       else if (integer_all_onesp (step0))
 509         {
 510           /* for (i = base0; i != base1; i--)  */
 511           niter->assumptions = boolean_true_node;
 512           niter->may_be_zero = boolean_false_node;
 513           niter->niter = fold_build2 (MINUS_EXPR, type, base0, base1);
 514         }
 515       else
 516         return false;
 517
 518       break;
 519
 520     case LT_EXPR:
 521       if ((step0 && integer_onep (step0) && zero_p (step1))
 522           || (step1 && integer_all_onesp (step1) && zero_p (step0)))
 523         {
 524           /* for (i = base0; i < base1; i++)
 525
 526              or
 527
 528              for (i = base1; i > base0; i--).
 529
 530              In both cases # of iterations is base1 - base0.  */
 531
 532           niter->assumptions = boolean_true_node;
 533           niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
 534                                             base0, base1);
 535           niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
 536         }
 537       else
 538         return false;
 539       break;
 540
 541     case LE_EXPR:
 542       if (POINTER_TYPE_P (type))
 543         {
 544           /* We assume pointer arithmetic never overflows.  */
 545           mmin = mmax = NULL_TREE;
 546         }
 547       else
 548         {
 549           mmin = TYPE_MIN_VALUE (type);
 550           mmax = TYPE_MAX_VALUE (type);
 551         }
 552
 553       if (step0 && integer_onep (step0) && zero_p (step1))
 554         {
 555           /* for (i = base0; i <= base1; i++)  */
 556           if (mmax)
 557             niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
 558                                               base1, mmax);
 559           else
 560             niter->assumptions = boolean_true_node;
 561           base1 = fold_build2 (PLUS_EXPR, type, base1,
 562                                build_int_cst_type (type, 1));
 563         }
 564       else if (step1 && integer_all_onesp (step1) && zero_p (step0))
 565         {
 566           /* for (i = base1; i >= base0; i--)  */
 567           if (mmin)
 568             niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
 569                                               base0, mmin);
 570           else
 571             niter->assumptions = boolean_true_node;
 572           base0 = fold_build2 (MINUS_EXPR, type, base0,
 573                                build_int_cst_type (type, 1));
 574         }
 575       else
 576         return false;
 577
 578       niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
 579                                         base0, base1);
 580       niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
 581       break;
 582
 583     default:
 584       gcc_unreachable ();
 585     }
 586
 587   niter->niter = fold_convert (niter_type, niter->niter);
 588   niter->additional_info = boolean_true_node;
 589   return true;
 590 }
 591
 592 /* Substitute NEW for OLD in EXPR and fold the result.  */
 593
 594 static tree
 595 simplify_replace_tree (tree expr, tree old, tree new)
 596 {
 597   unsigned i, n;
 598   tree ret = NULL_TREE, e, se;
 599
 600   if (!expr)
 601     return NULL_TREE;
 602
 603   if (expr == old
 604       || operand_equal_p (expr, old, 0))
 605     return unshare_expr (new);
 606
 607   if (!EXPR_P (expr))
 608     return expr;
 609
 610   n = TREE_CODE_LENGTH (TREE_CODE (expr));
 611   for (i = 0; i < n; i++)
 612     {
 613       e = TREE_OPERAND (expr, i);
 614       se = simplify_replace_tree (e, old, new);
 615       if (e == se)
 616         continue;
 617
 618       if (!ret)
 619         ret = copy_node (expr);
 620
 621       TREE_OPERAND (ret, i) = se;
 622     }
 623
 624   return (ret ? fold (ret) : expr);
 625 }
 626
 627 /* Expand definitions of ssa names in EXPR as long as they are simple
 628    enough, and return the new expression.  */
 629
 630 tree
 631 expand_simple_operations (tree expr)
 632 {
 633   unsigned i, n;
 634   tree ret = NULL_TREE, e, ee, stmt;
 635   enum tree_code code = TREE_CODE (expr);
 636
 637   if (is_gimple_min_invariant (expr))
 638     return expr;
 639
 640   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
 641     {
 642       n = TREE_CODE_LENGTH (code);
 643       for (i = 0; i < n; i++)
 644         {
 645           e = TREE_OPERAND (expr, i);
 646           ee = expand_simple_operations (e);
 647           if (e == ee)
 648             continue;
 649
 650           if (!ret)
 651             ret = copy_node (expr);
 652
 653           TREE_OPERAND (ret, i) = ee;
 654         }
 655
 656       return (ret ? fold (ret) : expr);
 657     }
 658
 659   if (TREE_CODE (expr) != SSA_NAME)
 660     return expr;
 661
 662   stmt = SSA_NAME_DEF_STMT (expr);
 663   if (TREE_CODE (stmt) != MODIFY_EXPR)
 664     return expr;
 665
 666   e = TREE_OPERAND (stmt, 1);
 667   if (/* Casts are simple.  */
 668       TREE_CODE (e) != NOP_EXPR
 669       && TREE_CODE (e) != CONVERT_EXPR
 670       /* Copies are simple.  */
 671       && TREE_CODE (e) != SSA_NAME
 672       /* Assignments of invariants are simple.  */
 673       && !is_gimple_min_invariant (e)
 674       /* And increments and decrements by a constant are simple.  */
 675       && !((TREE_CODE (e) == PLUS_EXPR
 676             || TREE_CODE (e) == MINUS_EXPR)
 677            && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
 678     return expr;
 679
 680   return expand_simple_operations (e);
 681 }
 682
 683 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
 684    expression (or EXPR unchanged, if no simplification was possible).  */
 685
 686 static tree
 687 tree_simplify_using_condition_1 (tree cond, tree expr)
 688 {
 689   bool changed;
 690   tree e, te, e0, e1, e2, notcond;
 691   enum tree_code code = TREE_CODE (expr);
 692
 693   if (code == INTEGER_CST)
 694     return expr;
 695
 696   if (code == TRUTH_OR_EXPR
 697       || code == TRUTH_AND_EXPR
 698       || code == COND_EXPR)
 699     {
 700       changed = false;
 701
 702       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
 703       if (TREE_OPERAND (expr, 0) != e0)
 704         changed = true;
 705
 706       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
 707       if (TREE_OPERAND (expr, 1) != e1)
 708         changed = true;
 709
 710       if (code == COND_EXPR)
 711         {
 712           e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
 713           if (TREE_OPERAND (expr, 2) != e2)
 714             changed = true;
 715         }
 716       else
 717         e2 = NULL_TREE;
 718
 719       if (changed)
 720         {
 721           if (code == COND_EXPR)
 722             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
 723           else
 724             expr = fold_build2 (code, boolean_type_node, e0, e1);
 725         }
 726
 727       return expr;
 728     }
 729
 730   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
 731      propagation, and vice versa.  Fold does not handle this, since it is
 732      considered too expensive.  */
 733   if (TREE_CODE (cond) == EQ_EXPR)
 734     {
 735       e0 = TREE_OPERAND (cond, 0);
 736       e1 = TREE_OPERAND (cond, 1);
 737
 738       /* We know that e0 == e1.  Check whether we cannot simplify expr
 739          using this fact.  */
 740       e = simplify_replace_tree (expr, e0, e1);
 741       if (zero_p (e) || nonzero_p (e))
 742         return e;
 743
 744       e = simplify_replace_tree (expr, e1, e0);
 745       if (zero_p (e) || nonzero_p (e))
 746         return e;
 747     }
 748   if (TREE_CODE (expr) == EQ_EXPR)
 749     {
 750       e0 = TREE_OPERAND (expr, 0);
 751       e1 = TREE_OPERAND (expr, 1);
 752
 753       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
 754       e = simplify_replace_tree (cond, e0, e1);
 755       if (zero_p (e))
 756         return e;
 757       e = simplify_replace_tree (cond, e1, e0);
 758       if (zero_p (e))
 759         return e;
 760     }
 761   if (TREE_CODE (expr) == NE_EXPR)
 762     {
 763       e0 = TREE_OPERAND (expr, 0);
 764       e1 = TREE_OPERAND (expr, 1);
 765
 766       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
 767       e = simplify_replace_tree (cond, e0, e1);
 768       if (zero_p (e))
 769         return boolean_true_node;
 770       e = simplify_replace_tree (cond, e1, e0);
 771       if (zero_p (e))
 772         return boolean_true_node;
 773     }
 774
 775   te = expand_simple_operations (expr);
 776
 777   /* Check whether COND ==> EXPR.  */
 778   notcond = invert_truthvalue (cond);
 779   e = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
 780   if (nonzero_p (e))
 781     return e;
 782
 783   /* Check whether COND ==> not EXPR.  */
 784   e = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, cond, te);
 785   if (zero_p (e))
 786     return e;
 787
 788   return expr;
 789 }
 790
 791 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
 792    expression (or EXPR unchanged, if no simplification was possible).
 793    Wrapper around tree_simplify_using_condition_1 that ensures that chains
 794    of simple operations in definitions of ssa names in COND are expanded,
 795    so that things like casts or incrementing the value of the bound before
 796    the loop do not cause us to fail.  */
 797
 798 static tree
 799 tree_simplify_using_condition (tree cond, tree expr)
 800 {
 801   cond = expand_simple_operations (cond);
 802
 803   return tree_simplify_using_condition_1 (cond, expr);
 804 }
 805
 806 /* Tries to simplify EXPR using the conditions on entry to LOOP.
 807    Record the conditions used for simplification to CONDS_USED.
 808    Returns the simplified expression (or EXPR unchanged, if no
 809    simplification was possible).*/
 810
 811 static tree
 812 simplify_using_initial_conditions (struct loop *loop, tree expr,
 813                                    tree *conds_used)
 814 {
 815   edge e;
 816   basic_block bb;
 817   tree exp, cond;
 818
 819   if (TREE_CODE (expr) == INTEGER_CST)
 820     return expr;
 821
 822   for (bb = loop->header;
 823        bb != ENTRY_BLOCK_PTR;
 824        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 825     {
 826       if (!single_pred_p (bb))
 827         continue;
 828       e = single_pred_edge (bb);
 829
 830       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
 831         continue;
 832
 833       cond = COND_EXPR_COND (last_stmt (e->src));
 834       if (e->flags & EDGE_FALSE_VALUE)
 835         cond = invert_truthvalue (cond);
 836       exp = tree_simplify_using_condition (cond, expr);
 837
 838       if (exp != expr)
 839         *conds_used = fold_build2 (TRUTH_AND_EXPR,
 840                                    boolean_type_node,
 841                                    *conds_used,
 842                                    cond);
 843
 844       expr = exp;
 845     }
 846
 847   return expr;
 848 }
 849
 850 /* Tries to simplify EXPR using the evolutions of the loop invariants
 851    in the superloops of LOOP.  Returns the simplified expression
 852    (or EXPR unchanged, if no simplification was possible).  */
 853
 854 static tree
 855 simplify_using_outer_evolutions (struct loop *loop, tree expr)
 856 {
 857   enum tree_code code = TREE_CODE (expr);
 858   bool changed;
 859   tree e, e0, e1, e2;
 860
 861   if (is_gimple_min_invariant (expr))
 862     return expr;
 863
 864   if (code == TRUTH_OR_EXPR
 865       || code == TRUTH_AND_EXPR
 866       || code == COND_EXPR)
 867     {
 868       changed = false;
 869
 870       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
 871       if (TREE_OPERAND (expr, 0) != e0)
 872         changed = true;
 873
 874       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
 875       if (TREE_OPERAND (expr, 1) != e1)
 876         changed = true;
 877
 878       if (code == COND_EXPR)
 879         {
 880           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
 881           if (TREE_OPERAND (expr, 2) != e2)
 882             changed = true;
 883         }
 884       else
 885         e2 = NULL_TREE;
 886
 887       if (changed)
 888         {
 889           if (code == COND_EXPR)
 890             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
 891           else
 892             expr = fold_build2 (code, boolean_type_node, e0, e1);
 893         }
 894
 895       return expr;
 896     }
 897
 898   e = instantiate_parameters (loop, expr);
 899   if (is_gimple_min_invariant (e))
 900     return e;
 901
 902   return expr;
 903 }
 904
 905 /* Stores description of number of iterations of LOOP derived from
 906    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
 907    useful information could be derived (and fields of NITER has
 908    meaning described in comments at struct tree_niter_desc
 909    declaration), false otherwise.  */
 910
 911 bool
 912 number_of_iterations_exit (struct loop *loop, edge exit,
 913                            struct tree_niter_desc *niter)
 914 {
 915   tree stmt, cond, type;
 916   tree op0, base0, step0;
 917   tree op1, base1, step1;
 918   enum tree_code code;
 919
 920   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
 921     return false;
 922
 923   niter->assumptions = boolean_false_node;
 924   stmt = last_stmt (exit->src);
 925   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
 926     return false;
 927
 928   /* We want the condition for staying inside loop.  */
 929   cond = COND_EXPR_COND (stmt);
 930   if (exit->flags & EDGE_TRUE_VALUE)
 931     cond = invert_truthvalue (cond);
 932
 933   code = TREE_CODE (cond);
 934   switch (code)
 935     {
 936     case GT_EXPR:
 937     case GE_EXPR:
 938     case NE_EXPR:
 939     case LT_EXPR:
 940     case LE_EXPR:
 941       break;
 942
 943     default:
 944       return false;
 945     }
 946
 947   op0 = TREE_OPERAND (cond, 0);
 948   op1 = TREE_OPERAND (cond, 1);
 949   type = TREE_TYPE (op0);
 950
 951   if (TREE_CODE (type) != INTEGER_TYPE
 952       && !POINTER_TYPE_P (type))
 953     return false;
 954
 955   if (!simple_iv (loop, stmt, op0, &base0, &step0, false))
 956     return false;
 957   if (!simple_iv (loop, stmt, op1, &base1, &step1, false))
 958     return false;
 959
 960   niter->niter = NULL_TREE;
 961
 962   /* Handle common special cases first, so that we do not need to use
 963      generic (and slow) analysis very often.  */
 964   if (!number_of_iterations_special (type, base0, step0, code, base1, step1,
 965                                      niter))
 966     {
 967
 968       number_of_iterations_cond (type, base0, step0, code, base1, step1,
 969                                  niter);
 970
 971       if (!niter->niter)
 972         return false;
 973     }
 974
 975   if (optimize >= 3)
 976     {
 977       niter->assumptions = simplify_using_outer_evolutions (loop,
 978                                                             niter->assumptions);
 979       niter->may_be_zero = simplify_using_outer_evolutions (loop,
 980                                                             niter->may_be_zero);
 981       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
 982     }
 983
 984   niter->additional_info = boolean_true_node;
 985   niter->assumptions
 986           = simplify_using_initial_conditions (loop,
 987                                                niter->assumptions,
 988                                                &niter->additional_info);
 989   niter->may_be_zero
 990           = simplify_using_initial_conditions (loop,
 991                                                niter->may_be_zero,
 992                                                &niter->additional_info);
 993   return integer_onep (niter->assumptions);
 994 }
 995
 996 /* Try to determine the number of iterations of LOOP.  If we succeed,
 997    expression giving number of iterations is returned and *EXIT is
 998    set to the edge from that the information is obtained.  Otherwise
 999    chrec_dont_know is returned.  */
1000
1001 tree
1002 find_loop_niter (struct loop *loop, edge *exit)
1003 {
1004   unsigned n_exits, i;
1005   edge *exits = get_loop_exit_edges (loop, &n_exits);
1006   edge ex;
1007   tree niter = NULL_TREE, aniter;
1008   struct tree_niter_desc desc;
1009
1010   *exit = NULL;
1011   for (i = 0; i < n_exits; i++)
1012     {
1013       ex = exits[i];
1014       if (!just_once_each_iteration_p (loop, ex->src))
1015         continue;
1016
1017       if (!number_of_iterations_exit (loop, ex, &desc))
1018         continue;
1019
1020       if (nonzero_p (desc.may_be_zero))
1021         {
1022           /* We exit in the first iteration through this exit.
1023              We won't find anything better.  */
1024           niter = build_int_cst_type (unsigned_type_node, 0);
1025           *exit = ex;
1026           break;
1027         }
1028
1029       if (!zero_p (desc.may_be_zero))
1030         continue;
1031
1032       aniter = desc.niter;
1033
1034       if (!niter)
1035         {
1036           /* Nothing recorded yet.  */
1037           niter = aniter;
1038           *exit = ex;
1039           continue;
1040         }
1041
1042       /* Prefer constants, the lower the better.  */
1043       if (TREE_CODE (aniter) != INTEGER_CST)
1044         continue;
1045
1046       if (TREE_CODE (niter) != INTEGER_CST)
1047         {
1048           niter = aniter;
1049           *exit = ex;
1050           continue;
1051         }
1052
1053       if (tree_int_cst_lt (aniter, niter))
1054         {
1055           niter = aniter;
1056           *exit = ex;
1057           continue;
1058         }
1059     }
1060   free (exits);
1061
1062   return niter ? niter : chrec_dont_know;
1063 }
1064
1065 /*
1066
1067    Analysis of a number of iterations of a loop by a brute-force evaluation.
1068
1069 */
1070
1071 /* Bound on the number of iterations we try to evaluate.  */
1072
1073 #define MAX_ITERATIONS_TO_TRACK \
1074   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1075
1076 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1077    result by a chain of operations such that all but exactly one of their
1078    operands are constants.  */
1079
1080 static tree
1081 chain_of_csts_start (struct loop *loop, tree x)
1082 {
1083   tree stmt = SSA_NAME_DEF_STMT (x);
1084   tree use;
1085   basic_block bb = bb_for_stmt (stmt);
1086
1087   if (!bb
1088       || !flow_bb_inside_loop_p (loop, bb))
1089     return NULL_TREE;
1090
1091   if (TREE_CODE (stmt) == PHI_NODE)
1092     {
1093       if (bb == loop->header)
1094         return stmt;
1095
1096       return NULL_TREE;
1097     }
1098
1099   if (TREE_CODE (stmt) != MODIFY_EXPR)
1100     return NULL_TREE;
1101
1102   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1103     return NULL_TREE;
1104   if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1105     return NULL_TREE;
1106
1107   use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1108   if (use == NULL_USE_OPERAND_P)
1109     return NULL_TREE;
1110
1111   return chain_of_csts_start (loop, use);
1112 }
1113
1114 /* Determines whether the expression X is derived from a result of a phi node
1115    in header of LOOP such that
1116
1117    * the derivation of X consists only from operations with constants
1118    * the initial value of the phi node is constant
1119    * the value of the phi node in the next iteration can be derived from the
1120      value in the current iteration by a chain of operations with constants.
1121
1122    If such phi node exists, it is returned.  If X is a constant, X is returned
1123    unchanged.  Otherwise NULL_TREE is returned.  */
1124
1125 static tree
1126 get_base_for (struct loop *loop, tree x)
1127 {
1128   tree phi, init, next;
1129
1130   if (is_gimple_min_invariant (x))
1131     return x;
1132
1133   phi = chain_of_csts_start (loop, x);
1134   if (!phi)
1135     return NULL_TREE;
1136
1137   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1138   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1139
1140   if (TREE_CODE (next) != SSA_NAME)
1141     return NULL_TREE;
1142
1143   if (!is_gimple_min_invariant (init))
1144     return NULL_TREE;
1145
1146   if (chain_of_csts_start (loop, next) != phi)
1147     return NULL_TREE;
1148
1149   return phi;
1150 }
1151
1152 /* Given an expression X, then
1153
1154    * if BASE is NULL_TREE, X must be a constant and we return X.
1155    * otherwise X is a SSA name, whose value in the considered loop is derived
1156      by a chain of operations with constant from a result of a phi node in
1157      the header of the loop.  Then we return value of X when the value of the
1158      result of this phi node is given by the constant BASE.  */
1159
1160 static tree
1161 get_val_for (tree x, tree base)
1162 {
1163   tree stmt, nx, val;
1164   use_operand_p op;
1165   ssa_op_iter iter;
1166
1167   if (!x)
1168     return base;
1169
1170   stmt = SSA_NAME_DEF_STMT (x);
1171   if (TREE_CODE (stmt) == PHI_NODE)
1172     return base;
1173
1174   FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
1175     {
1176       nx = USE_FROM_PTR (op);
1177       val = get_val_for (nx, base);
1178       SET_USE (op, val);
1179       val = fold (TREE_OPERAND (stmt, 1));
1180       SET_USE (op, nx);
1181       /* only iterate loop once.  */
1182       return val;
1183     }
1184
1185   /* Should never reach here.  */
1186   gcc_unreachable();
1187 }
1188
1189 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1190    by brute force -- i.e. by determining the value of the operands of the
1191    condition at EXIT in first few iterations of the loop (assuming that
1192    these values are constant) and determining the first one in that the
1193    condition is not satisfied.  Returns the constant giving the number
1194    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
1195
1196 tree
1197 loop_niter_by_eval (struct loop *loop, edge exit)
1198 {
1199   tree cond, cnd, acnd;
1200   tree op[2], val[2], next[2], aval[2], phi[2];
1201   unsigned i, j;
1202   enum tree_code cmp;
1203
1204   cond = last_stmt (exit->src);
1205   if (!cond || TREE_CODE (cond) != COND_EXPR)
1206     return chrec_dont_know;
1207
1208   cnd = COND_EXPR_COND (cond);
1209   if (exit->flags & EDGE_TRUE_VALUE)
1210     cnd = invert_truthvalue (cnd);
1211
1212   cmp = TREE_CODE (cnd);
1213   switch (cmp)
1214     {
1215     case EQ_EXPR:
1216     case NE_EXPR:
1217     case GT_EXPR:
1218     case GE_EXPR:
1219     case LT_EXPR:
1220     case LE_EXPR:
1221       for (j = 0; j < 2; j++)
1222         op[j] = TREE_OPERAND (cnd, j);
1223       break;
1224
1225     default:
1226       return chrec_dont_know;
1227     }
1228
1229   for (j = 0; j < 2; j++)
1230     {
1231       phi[j] = get_base_for (loop, op[j]);
1232       if (!phi[j])
1233         return chrec_dont_know;
1234     }
1235
1236   for (j = 0; j < 2; j++)
1237     {
1238       if (TREE_CODE (phi[j]) == PHI_NODE)
1239         {
1240           val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1241           next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1242         }
1243       else
1244         {
1245           val[j] = phi[j];
1246           next[j] = NULL_TREE;
1247           op[j] = NULL_TREE;
1248         }
1249     }
1250
1251   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1252     {
1253       for (j = 0; j < 2; j++)
1254         aval[j] = get_val_for (op[j], val[j]);
1255
1256       acnd = fold_build2 (cmp, boolean_type_node, aval[0], aval[1]);
1257       if (zero_p (acnd))
1258         {
1259           if (dump_file && (dump_flags & TDF_DETAILS))
1260             fprintf (dump_file,
1261                      "Proved that loop %d iterates %d times using brute force.\n",
1262                      loop->num, i);
1263           return build_int_cst (unsigned_type_node, i);
1264         }
1265
1266       for (j = 0; j < 2; j++)
1267         val[j] = get_val_for (next[j], val[j]);
1268     }
1269
1270   return chrec_dont_know;
1271 }
1272
1273 /* Finds the exit of the LOOP by that the loop exits after a constant
1274    number of iterations and stores the exit edge to *EXIT.  The constant
1275    giving the number of iterations of LOOP is returned.  The number of
1276    iterations is determined using loop_niter_by_eval (i.e. by brute force
1277    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1278    determines the number of iterations, chrec_dont_know is returned.  */
1279
1280 tree
1281 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1282 {
1283   unsigned n_exits, i;
1284   edge *exits = get_loop_exit_edges (loop, &n_exits);
1285   edge ex;
1286   tree niter = NULL_TREE, aniter;
1287
1288   *exit = NULL;
1289   for (i = 0; i < n_exits; i++)
1290     {
1291       ex = exits[i];
1292       if (!just_once_each_iteration_p (loop, ex->src))
1293         continue;
1294
1295       aniter = loop_niter_by_eval (loop, ex);
1296       if (chrec_contains_undetermined (aniter))
1297         continue;
1298
1299       if (niter
1300           && !tree_int_cst_lt (aniter, niter))
1301         continue;
1302
1303       niter = aniter;
1304       *exit = ex;
1305     }
1306   free (exits);
1307
1308   return niter ? niter : chrec_dont_know;
1309 }
1310
1311 /*
1312
1313    Analysis of upper bounds on number of iterations of a loop.
1314
1315 */
1316
1317 /* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1318    additional condition ADDITIONAL is recorded with the bound.  */
1319
1320 void
1321 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1322 {
1323   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1324
1325   if (dump_file && (dump_flags & TDF_DETAILS))
1326     {
1327       fprintf (dump_file, "Statements after ");
1328       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1329       fprintf (dump_file, " are executed at most ");
1330       print_generic_expr (dump_file, bound, TDF_SLIM);
1331       fprintf (dump_file, " times in loop %d.\n", loop->num);
1332     }
1333
1334   elt->bound = bound;
1335   elt->at_stmt = at_stmt;
1336   elt->additional = additional;
1337   elt->next = loop->bounds;
1338   loop->bounds = elt;
1339 }
1340
1341 /* Records estimates on numbers of iterations of LOOP.  */
1342
1343 static void
1344 estimate_numbers_of_iterations_loop (struct loop *loop)
1345 {
1346   edge *exits;
1347   tree niter, type;
1348   unsigned i, n_exits;
1349   struct tree_niter_desc niter_desc;
1350
1351   /* Give up if we already have tried to compute an estimation.  */
1352   if (loop->estimated_nb_iterations == chrec_dont_know
1353       /* Or when we already have an estimation.  */
1354       || (loop->estimated_nb_iterations != NULL_TREE
1355           && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
1356     return;
1357   else
1358     loop->estimated_nb_iterations = chrec_dont_know;
1359
1360   exits = get_loop_exit_edges (loop, &n_exits);
1361   for (i = 0; i < n_exits; i++)
1362     {
1363       if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
1364         continue;
1365
1366       niter = niter_desc.niter;
1367       type = TREE_TYPE (niter);
1368       if (!zero_p (niter_desc.may_be_zero)
1369           && !nonzero_p (niter_desc.may_be_zero))
1370         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1371                         build_int_cst_type (type, 0),
1372                         niter);
1373       record_estimate (loop, niter,
1374                        niter_desc.additional_info,
1375                        last_stmt (exits[i]->src));
1376     }
1377   free (exits);
1378
1379   /* Analyzes the bounds of arrays accessed in the loop.  */
1380   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1381     {
1382       varray_type datarefs;
1383       VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
1384       find_data_references_in_loop (loop, &datarefs);
1385       free_data_refs (datarefs);
1386     }
1387 }
1388
1389 /* Records estimates on numbers of iterations of LOOPS.  */
1390
1391 void
1392 estimate_numbers_of_iterations (struct loops *loops)
1393 {
1394   unsigned i;
1395   struct loop *loop;
1396
1397   for (i = 1; i < loops->num; i++)
1398     {
1399       loop = loops->parray[i];
1400       if (loop)
1401         estimate_numbers_of_iterations_loop (loop);
1402     }
1403 }
1404
1405 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1406    If neither of these relations can be proved, returns 2.  */
1407
1408 static int
1409 compare_trees (tree a, tree b)
1410 {
1411   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1412   tree type;
1413
1414   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1415     type = typea;
1416   else
1417     type = typeb;
1418
1419   a = fold_convert (type, a);
1420   b = fold_convert (type, b);
1421
1422   if (nonzero_p (fold_build2 (EQ_EXPR, boolean_type_node, a, b)))
1423     return 0;
1424   if (nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, a, b)))
1425     return 1;
1426   if (nonzero_p (fold_build2 (GT_EXPR, boolean_type_node, a, b)))
1427     return -1;
1428
1429   return 2;
1430 }
1431
1432 /* Returns true if statement S1 dominates statement S2.  */
1433
1434 static bool
1435 stmt_dominates_stmt_p (tree s1, tree s2)
1436 {
1437   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1438
1439   if (!bb1
1440       || s1 == s2)
1441     return true;
1442
1443   if (bb1 == bb2)
1444     {
1445       block_stmt_iterator bsi;
1446
1447       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1448         if (bsi_stmt (bsi) == s1)
1449           return true;
1450
1451       return false;
1452     }
1453
1454   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1455 }
1456
1457 /* Return true when it is possible to prove that the induction
1458    variable does not wrap: vary outside the type specified bounds.
1459    Checks whether BOUND < VALID_NITER that means in the context of iv
1460    conversion that all the iterations in the loop are safe: not
1461    producing wraps.
1462
1463    The statement NITER_BOUND->AT_STMT is executed at most
1464    NITER_BOUND->BOUND times in the loop.
1465
1466    NITER_BOUND->ADDITIONAL is the additional condition recorded for
1467    operands of the bound.  This is useful in the following case,
1468    created by loop header copying:
1469
1470    i = 0;
1471    if (n > 0)
1472      do
1473        {
1474          something;
1475        } while (++i < n)
1476
1477    If the n > 0 condition is taken into account, the number of iterations of the
1478    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1479    assumption "n > 0" says us that the value of the number of iterations is at
1480    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1481
1482 static bool
1483 proved_non_wrapping_p (tree at_stmt,
1484                        struct nb_iter_bound *niter_bound,
1485                        tree new_type,
1486                        tree valid_niter)
1487 {
1488   tree cond;
1489   tree bound = niter_bound->bound;
1490
1491   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
1492     bound = fold_convert (unsigned_type_for (new_type), bound);
1493   else
1494     valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
1495
1496   /* After the statement niter_bound->at_stmt we know that anything is
1497      executed at most BOUND times.  */
1498   if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
1499     cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
1500
1501   /* Before the statement niter_bound->at_stmt we know that anything
1502      is executed at most BOUND + 1 times.  */
1503   else
1504     cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
1505
1506   if (nonzero_p (cond))
1507     return true;
1508
1509   /* Try taking additional conditions into account.  */
1510   cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1511                       invert_truthvalue (niter_bound->additional),
1512                       cond);
1513
1514   if (nonzero_p (cond))
1515     return true;
1516
1517   return false;
1518 }
1519
1520 /* Checks whether it is correct to count the induction variable BASE +
1521    STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1522    numbers of iterations of a LOOP.  If it is possible, return the
1523    value of step of the induction variable in the NEW_TYPE, otherwise
1524    return NULL_TREE.  */
1525
1526 static tree
1527 convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
1528                        tree at_stmt)
1529 {
1530   struct nb_iter_bound *bound;
1531   tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
1532   tree delta, step_abs;
1533   tree unsigned_type, valid_niter;
1534
1535   /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
1536      is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
1537      keep the values of the induction variable unchanged: 100, 84, 68,
1538      ...
1539
1540      Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1541      to {(uint)100, +, (uint)3}.
1542
1543      Before returning the new step, verify that the number of
1544      iterations is less than DELTA / STEP_ABS (i.e. in the previous
1545      example (256 - 100) / 3) such that the iv does not wrap (in which
1546      case the operations are too difficult to be represented and
1547      handled: the values of the iv should be taken modulo 256 in the
1548      wider type; this is not implemented).  */
1549   base_in_new_type = fold_convert (new_type, base);
1550   base_plus_step_in_new_type =
1551     fold_convert (new_type,
1552                   fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
1553   step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
1554                                   base_plus_step_in_new_type,
1555                                   base_in_new_type);
1556
1557   if (TREE_CODE (step_in_new_type) != INTEGER_CST)
1558     return NULL_TREE;
1559
1560   switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
1561     {
1562     case -1:
1563       {
1564         tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
1565         delta = fold_build2 (MINUS_EXPR, new_type, extreme,
1566                              base_in_new_type);
1567         step_abs = step_in_new_type;
1568         break;
1569       }
1570
1571     case 1:
1572       {
1573         tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
1574         delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
1575                              extreme);
1576         step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
1577         break;
1578       }
1579
1580     case 0:
1581       return step_in_new_type;
1582
1583     default:
1584       return NULL_TREE;
1585     }
1586
1587   unsigned_type = unsigned_type_for (new_type);
1588   delta = fold_convert (unsigned_type, delta);
1589   step_abs = fold_convert (unsigned_type, step_abs);
1590   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1591                              delta, step_abs);
1592
1593   estimate_numbers_of_iterations_loop (loop);
1594   for (bound = loop->bounds; bound; bound = bound->next)
1595     if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
1596       return step_in_new_type;
1597
1598   /* Fail when the loop has no bound estimations, or when no bound can
1599      be used for verifying the conversion.  */
1600   return NULL_TREE;
1601 }
1602
1603 /* Return false only when the induction variable BASE + STEP * I is
1604    known to not overflow: i.e. when the number of iterations is small
1605    enough with respect to the step and initial condition in order to
1606    keep the evolution confined in TYPEs bounds.  Return true when the
1607    iv is known to overflow or when the property is not computable.
1608
1609    Initialize INIT_IS_MAX to true when the evolution goes from
1610    INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case, not
1611    defined when the function returns true.  */
1612
1613 bool
1614 scev_probably_wraps_p (tree type, tree base, tree step,
1615                        tree at_stmt, struct loop *loop,
1616                        bool *init_is_max)
1617 {
1618   struct nb_iter_bound *bound;
1619   tree delta, step_abs;
1620   tree unsigned_type, valid_niter;
1621   tree base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
1622
1623   switch (compare_trees (base_plus_step, base))
1624     {
1625     case -1:
1626       {
1627         tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
1628         delta = fold_build2 (MINUS_EXPR, type, extreme, base);
1629         step_abs = step;
1630         *init_is_max = false;
1631         break;
1632       }
1633
1634     case 1:
1635       {
1636         tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
1637         delta = fold_build2 (MINUS_EXPR, type, base, extreme);
1638         step_abs = fold_build1 (NEGATE_EXPR, type, step);
1639         *init_is_max = true;
1640         break;
1641       }
1642
1643     case 0:
1644       /* This means step is equal to 0.  This should not happen.  It
1645          could happen in convert step, but not here.  Safely answer
1646          don't know as in the default case.  */
1647
1648     default:
1649       return true;
1650     }
1651
1652   /* If AT_STMT represents a cast operation, we may not be able to
1653      take advantage of the undefinedness of signed type evolutions.
1654      See PR 21959 for a test case.  Essentially, given a cast
1655      operation
1656                 unsigned char i;
1657                 signed char i.0;
1658                 ...
1659                 i.0_6 = (signed char) i_2;
1660                 if (i.0_6 < 0)
1661                   ...
1662
1663      where i_2 and i.0_6 have the scev {0, +, 1}, we would consider
1664      i_2 to wrap around, but not i.0_6, because it is of a signed
1665      type.  This causes VRP to erroneously fold the predicate above
1666      because it thinks that i.0_6 cannot be negative.  */
1667   if (TREE_CODE (at_stmt) == MODIFY_EXPR)
1668     {
1669       tree rhs = TREE_OPERAND (at_stmt, 1);
1670       tree outer_t = TREE_TYPE (rhs);
1671
1672       if (!TYPE_UNSIGNED (outer_t)
1673           && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
1674         {
1675           tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
1676
1677           /* If the inner type is unsigned and its size and/or
1678              precision are smaller to that of the outer type, then the
1679              expression may wrap around.  */
1680           if (TYPE_UNSIGNED (inner_t)
1681               && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
1682                   || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
1683             return true;
1684         }
1685     }
1686
1687   /* After having set INIT_IS_MAX, we can return false: when not using
1688      wrapping arithmetic, signed types don't wrap.  */
1689   if (!flag_wrapv && !TYPE_UNSIGNED (type))
1690     return false;
1691
1692   unsigned_type = unsigned_type_for (type);
1693   delta = fold_convert (unsigned_type, delta);
1694   step_abs = fold_convert (unsigned_type, step_abs);
1695   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
1696
1697   estimate_numbers_of_iterations_loop (loop);
1698   for (bound = loop->bounds; bound; bound = bound->next)
1699     if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
1700       return false;
1701
1702   /* At this point we still don't have a proof that the iv does not
1703      overflow: give up.  */
1704   return true;
1705 }
1706
1707 /* Return the conversion to NEW_TYPE of the STEP of an induction
1708    variable BASE + STEP * I at AT_STMT.  */
1709
1710 tree
1711 convert_step (struct loop *loop, tree new_type, tree base, tree step,
1712               tree at_stmt)
1713 {
1714   tree base_type = TREE_TYPE (base);
1715
1716   /* When not using wrapping arithmetic, signed types don't wrap.  */
1717   if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
1718     return fold_convert (new_type, step);
1719
1720   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
1721     return convert_step_widening (loop, new_type, base, step, at_stmt);
1722
1723   return fold_convert (new_type, step);
1724 }
1725
1726 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
1727
1728 static void
1729 free_numbers_of_iterations_estimates_loop (struct loop *loop)
1730 {
1731   struct nb_iter_bound *bound, *next;
1732
1733   for (bound = loop->bounds; bound; bound = next)
1734     {
1735       next = bound->next;
1736       free (bound);
1737     }
1738
1739   loop->bounds = NULL;
1740 }
1741
1742 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
1743
1744 void
1745 free_numbers_of_iterations_estimates (struct loops *loops)
1746 {
1747   unsigned i;
1748   struct loop *loop;
1749
1750   for (i = 1; i < loops->num; i++)
1751     {
1752       loop = loops->parray[i];
1753       if (loop)
1754         free_numbers_of_iterations_estimates_loop (loop);
1755     }
1756 }
1757
1758 /* Substitute value VAL for ssa name NAME inside expressions held
1759    at LOOP.  */
1760
1761 void
1762 substitute_in_loop_info (struct loop *loop, tree name, tree val)
1763 {
1764   struct nb_iter_bound *bound;
1765
1766   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
1767   loop->estimated_nb_iterations
1768           = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
1769   for (bound = loop->bounds; bound; bound = bound->next)
1770     {
1771       bound->bound = simplify_replace_tree (bound->bound, name, val);
1772       bound->additional = simplify_replace_tree (bound->additional, name, val);
1773     }
1774 }