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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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 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_expr_nonnegative_p (step0))
 193         return;
 194
 195       if (!zero_p (step1) && tree_expr_nonnegative_p (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_expr_nonnegative_p (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 /* Tries to simplify EXPR using the evolutions of the loop invariants
 466    in the superloops of LOOP.  Returns the simplified expression
 467    (or EXPR unchanged, if no simplification was possible).  */
 468
 469 static tree
 470 simplify_using_outer_evolutions (struct loop *loop, tree expr)
 471 {
 472   enum tree_code code = TREE_CODE (expr);
 473   bool changed;
 474   tree e, e0, e1, e2;
 475
 476   if (is_gimple_min_invariant (expr))
 477     return expr;
 478
 479   if (code == TRUTH_OR_EXPR
 480       || code == TRUTH_AND_EXPR
 481       || code == COND_EXPR)
 482     {
 483       changed = false;
 484
 485       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
 486       if (TREE_OPERAND (expr, 0) != e0)
 487         changed = true;
 488
 489       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
 490       if (TREE_OPERAND (expr, 1) != e1)
 491         changed = true;
 492
 493       if (code == COND_EXPR)
 494         {
 495           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
 496           if (TREE_OPERAND (expr, 2) != e2)
 497             changed = true;
 498         }
 499       else
 500         e2 = NULL_TREE;
 501
 502       if (changed)
 503         {
 504           if (code == COND_EXPR)
 505             expr = build3 (code, boolean_type_node, e0, e1, e2);
 506           else
 507             expr = build2 (code, boolean_type_node, e0, e1);
 508           expr = fold (expr);
 509         }
 510
 511       return expr;
 512     }
 513
 514   e = instantiate_parameters (loop, expr);
 515   if (is_gimple_min_invariant (e))
 516     return e;
 517
 518   return expr;
 519 }
 520
 521 /* Substitute NEW for OLD in EXPR and fold the result.  */
 522
 523 static tree
 524 simplify_replace_tree (tree expr, tree old, tree new)
 525 {
 526   unsigned i, n;
 527   tree ret = NULL_TREE, e, se;
 528
 529   if (!expr)
 530     return NULL_TREE;
 531
 532   if (expr == old
 533       || operand_equal_p (expr, old, 0))
 534     return unshare_expr (new);
 535
 536   if (!EXPR_P (expr))
 537     return expr;
 538
 539   n = TREE_CODE_LENGTH (TREE_CODE (expr));
 540   for (i = 0; i < n; i++)
 541     {
 542       e = TREE_OPERAND (expr, i);
 543       se = simplify_replace_tree (e, old, new);
 544       if (e == se)
 545         continue;
 546
 547       if (!ret)
 548         ret = copy_node (expr);
 549
 550       TREE_OPERAND (ret, i) = se;
 551     }
 552
 553   return (ret ? fold (ret) : expr);
 554 }
 555
 556 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
 557    expression (or EXPR unchanged, if no simplification was possible).*/
 558
 559 static tree
 560 tree_simplify_using_condition (tree cond, tree expr)
 561 {
 562   bool changed;
 563   tree e, e0, e1, e2, notcond;
 564   enum tree_code code = TREE_CODE (expr);
 565
 566   if (code == INTEGER_CST)
 567     return expr;
 568
 569   if (code == TRUTH_OR_EXPR
 570       || code == TRUTH_AND_EXPR
 571       || code == COND_EXPR)
 572     {
 573       changed = false;
 574
 575       e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
 576       if (TREE_OPERAND (expr, 0) != e0)
 577         changed = true;
 578
 579       e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
 580       if (TREE_OPERAND (expr, 1) != e1)
 581         changed = true;
 582
 583       if (code == COND_EXPR)
 584         {
 585           e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
 586           if (TREE_OPERAND (expr, 2) != e2)
 587             changed = true;
 588         }
 589       else
 590         e2 = NULL_TREE;
 591
 592       if (changed)
 593         {
 594           if (code == COND_EXPR)
 595             expr = build3 (code, boolean_type_node, e0, e1, e2);
 596           else
 597             expr = build2 (code, boolean_type_node, e0, e1);
 598           expr = fold (expr);
 599         }
 600
 601       return expr;
 602     }
 603
 604   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
 605      propagation, and vice versa.  Fold does not handle this, since it is
 606      considered too expensive.  */
 607   if (TREE_CODE (cond) == EQ_EXPR)
 608     {
 609       e0 = TREE_OPERAND (cond, 0);
 610       e1 = TREE_OPERAND (cond, 1);
 611
 612       /* We know that e0 == e1.  Check whether we cannot simplify expr
 613          using this fact.  */
 614       e = simplify_replace_tree (expr, e0, e1);
 615       if (zero_p (e) || nonzero_p (e))
 616         return e;
 617
 618       e = simplify_replace_tree (expr, e1, e0);
 619       if (zero_p (e) || nonzero_p (e))
 620         return e;
 621     }
 622   if (TREE_CODE (expr) == EQ_EXPR)
 623     {
 624       e0 = TREE_OPERAND (expr, 0);
 625       e1 = TREE_OPERAND (expr, 1);
 626
 627       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
 628       e = simplify_replace_tree (cond, e0, e1);
 629       if (zero_p (e))
 630         return e;
 631       e = simplify_replace_tree (cond, e1, e0);
 632       if (zero_p (e))
 633         return e;
 634     }
 635   if (TREE_CODE (expr) == NE_EXPR)
 636     {
 637       e0 = TREE_OPERAND (expr, 0);
 638       e1 = TREE_OPERAND (expr, 1);
 639
 640       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
 641       e = simplify_replace_tree (cond, e0, e1);
 642       if (zero_p (e))
 643         return boolean_true_node;
 644       e = simplify_replace_tree (cond, e1, e0);
 645       if (zero_p (e))
 646         return boolean_true_node;
 647     }
 648
 649   /* Check whether COND ==> EXPR.  */
 650   notcond = invert_truthvalue (cond);
 651   e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
 652                    notcond, expr));
 653   if (nonzero_p (e))
 654     return e;
 655
 656   /* Check whether COND ==> not EXPR.  */
 657   e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
 658                    cond, expr));
 659   if (zero_p (e))
 660     return e;
 661
 662   return expr;
 663 }
 664
 665 /* Tries to simplify EXPR using the conditions on entry to LOOP.
 666    Record the conditions used for simplification to CONDS_USED.
 667    Returns the simplified expression (or EXPR unchanged, if no
 668    simplification was possible).*/
 669
 670 static tree
 671 simplify_using_initial_conditions (struct loop *loop, tree expr,
 672                                    tree *conds_used)
 673 {
 674   edge e;
 675   basic_block bb;
 676   tree exp, cond;
 677
 678   if (TREE_CODE (expr) == INTEGER_CST)
 679     return expr;
 680
 681   for (bb = loop->header;
 682        bb != ENTRY_BLOCK_PTR;
 683        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 684     {
 685       if (!single_pred_p (bb))
 686         continue;
 687       e = single_pred_edge (bb);
 688
 689       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
 690         continue;
 691
 692       cond = COND_EXPR_COND (last_stmt (e->src));
 693       if (e->flags & EDGE_FALSE_VALUE)
 694         cond = invert_truthvalue (cond);
 695       exp = tree_simplify_using_condition (cond, expr);
 696
 697       if (exp != expr)
 698         *conds_used = fold (build2 (TRUTH_AND_EXPR,
 699                                    boolean_type_node,
 700                                    *conds_used,
 701                                    cond));
 702
 703       expr = exp;
 704     }
 705
 706   return expr;
 707 }
 708
 709 /* Stores description of number of iterations of LOOP derived from
 710    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
 711    useful information could be derived (and fields of NITER has
 712    meaning described in comments at struct tree_niter_desc
 713    declaration), false otherwise.  */
 714
 715 bool
 716 number_of_iterations_exit (struct loop *loop, edge exit,
 717                            struct tree_niter_desc *niter)
 718 {
 719   tree stmt, cond, type;
 720   tree op0, base0, step0;
 721   tree op1, base1, step1;
 722   enum tree_code code;
 723
 724   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
 725     return false;
 726
 727   niter->assumptions = boolean_false_node;
 728   stmt = last_stmt (exit->src);
 729   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
 730     return false;
 731
 732   /* We want the condition for staying inside loop.  */
 733   cond = COND_EXPR_COND (stmt);
 734   if (exit->flags & EDGE_TRUE_VALUE)
 735     cond = invert_truthvalue (cond);
 736
 737   code = TREE_CODE (cond);
 738   switch (code)
 739     {
 740     case GT_EXPR:
 741     case GE_EXPR:
 742     case NE_EXPR:
 743     case LT_EXPR:
 744     case LE_EXPR:
 745       break;
 746
 747     default:
 748       return false;
 749     }
 750
 751   op0 = TREE_OPERAND (cond, 0);
 752   op1 = TREE_OPERAND (cond, 1);
 753   type = TREE_TYPE (op0);
 754
 755   if (TREE_CODE (type) != INTEGER_TYPE
 756       && !POINTER_TYPE_P (type))
 757     return false;
 758
 759   if (!simple_iv (loop, stmt, op0, &base0, &step0))
 760     return false;
 761   if (!simple_iv (loop, stmt, op1, &base1, &step1))
 762     return false;
 763
 764   niter->niter = NULL_TREE;
 765   number_of_iterations_cond (type, base0, step0, code, base1, step1,
 766                              niter);
 767   if (!niter->niter)
 768     return false;
 769
 770   niter->assumptions = simplify_using_outer_evolutions (loop,
 771                                                         niter->assumptions);
 772   niter->may_be_zero = simplify_using_outer_evolutions (loop,
 773                                                         niter->may_be_zero);
 774   niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
 775
 776   niter->additional_info = boolean_true_node;
 777   niter->assumptions
 778           = simplify_using_initial_conditions (loop,
 779                                                niter->assumptions,
 780                                                &niter->additional_info);
 781   niter->may_be_zero
 782           = simplify_using_initial_conditions (loop,
 783                                                niter->may_be_zero,
 784                                                &niter->additional_info);
 785   return integer_onep (niter->assumptions);
 786 }
 787
 788 /* Try to determine the number of iterations of LOOP.  If we succeed,
 789    expression giving number of iterations is returned and *EXIT is
 790    set to the edge from that the information is obtained.  Otherwise
 791    chrec_dont_know is returned.  */
 792
 793 tree
 794 find_loop_niter (struct loop *loop, edge *exit)
 795 {
 796   unsigned n_exits, i;
 797   edge *exits = get_loop_exit_edges (loop, &n_exits);
 798   edge ex;
 799   tree niter = NULL_TREE, aniter;
 800   struct tree_niter_desc desc;
 801
 802   *exit = NULL;
 803   for (i = 0; i < n_exits; i++)
 804     {
 805       ex = exits[i];
 806       if (!just_once_each_iteration_p (loop, ex->src))
 807         continue;
 808
 809       if (!number_of_iterations_exit (loop, ex, &desc))
 810         continue;
 811
 812       if (nonzero_p (desc.may_be_zero))
 813         {
 814           /* We exit in the first iteration through this exit.
 815              We won't find anything better.  */
 816           niter = build_int_cst_type (unsigned_type_node, 0);
 817           *exit = ex;
 818           break;
 819         }
 820
 821       if (!zero_p (desc.may_be_zero))
 822         continue;
 823
 824       aniter = desc.niter;
 825
 826       if (!niter)
 827         {
 828           /* Nothing recorded yet.  */
 829           niter = aniter;
 830           *exit = ex;
 831           continue;
 832         }
 833
 834       /* Prefer constants, the lower the better.  */
 835       if (TREE_CODE (aniter) != INTEGER_CST)
 836         continue;
 837
 838       if (TREE_CODE (niter) != INTEGER_CST)
 839         {
 840           niter = aniter;
 841           *exit = ex;
 842           continue;
 843         }
 844
 845       if (tree_int_cst_lt (aniter, niter))
 846         {
 847           niter = aniter;
 848           *exit = ex;
 849           continue;
 850         }
 851     }
 852   free (exits);
 853
 854   return niter ? niter : chrec_dont_know;
 855 }
 856
 857 /*
 858
 859    Analysis of a number of iterations of a loop by a brute-force evaluation.
 860
 861 */
 862
 863 /* Bound on the number of iterations we try to evaluate.  */
 864
 865 #define MAX_ITERATIONS_TO_TRACK \
 866   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
 867
 868 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
 869    result by a chain of operations such that all but exactly one of their
 870    operands are constants.  */
 871
 872 static tree
 873 chain_of_csts_start (struct loop *loop, tree x)
 874 {
 875   tree stmt = SSA_NAME_DEF_STMT (x);
 876   basic_block bb = bb_for_stmt (stmt);
 877   use_optype uses;
 878
 879   if (!bb
 880       || !flow_bb_inside_loop_p (loop, bb))
 881     return NULL_TREE;
 882
 883   if (TREE_CODE (stmt) == PHI_NODE)
 884     {
 885       if (bb == loop->header)
 886         return stmt;
 887
 888       return NULL_TREE;
 889     }
 890
 891   if (TREE_CODE (stmt) != MODIFY_EXPR)
 892     return NULL_TREE;
 893
 894   get_stmt_operands (stmt);
 895   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
 896     return NULL_TREE;
 897   if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
 898     return NULL_TREE;
 899   if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
 900     return NULL_TREE;
 901   if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
 902     return NULL_TREE;
 903   uses = STMT_USE_OPS (stmt);
 904   if (NUM_USES (uses) != 1)
 905     return NULL_TREE;
 906
 907   return chain_of_csts_start (loop, USE_OP (uses, 0));
 908 }
 909
 910 /* Determines whether the expression X is derived from a result of a phi node
 911    in header of LOOP such that
 912
 913    * the derivation of X consists only from operations with constants
 914    * the initial value of the phi node is constant
 915    * the value of the phi node in the next iteration can be derived from the
 916      value in the current iteration by a chain of operations with constants.
 917
 918    If such phi node exists, it is returned.  If X is a constant, X is returned
 919    unchanged.  Otherwise NULL_TREE is returned.  */
 920
 921 static tree
 922 get_base_for (struct loop *loop, tree x)
 923 {
 924   tree phi, init, next;
 925
 926   if (is_gimple_min_invariant (x))
 927     return x;
 928
 929   phi = chain_of_csts_start (loop, x);
 930   if (!phi)
 931     return NULL_TREE;
 932
 933   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
 934   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
 935
 936   if (TREE_CODE (next) != SSA_NAME)
 937     return NULL_TREE;
 938
 939   if (!is_gimple_min_invariant (init))
 940     return NULL_TREE;
 941
 942   if (chain_of_csts_start (loop, next) != phi)
 943     return NULL_TREE;
 944
 945   return phi;
 946 }
 947
 948 /* Given an expression X, then
 949
 950    * if BASE is NULL_TREE, X must be a constant and we return X.
 951    * otherwise X is a SSA name, whose value in the considered loop is derived
 952      by a chain of operations with constant from a result of a phi node in
 953      the header of the loop.  Then we return value of X when the value of the
 954      result of this phi node is given by the constant BASE.  */
 955
 956 static tree
 957 get_val_for (tree x, tree base)
 958 {
 959   tree stmt, nx, val;
 960   use_optype uses;
 961   use_operand_p op;
 962
 963   if (!x)
 964     return base;
 965
 966   stmt = SSA_NAME_DEF_STMT (x);
 967   if (TREE_CODE (stmt) == PHI_NODE)
 968     return base;
 969
 970   uses = STMT_USE_OPS (stmt);
 971   op = USE_OP_PTR (uses, 0);
 972
 973   nx = USE_FROM_PTR (op);
 974   val = get_val_for (nx, base);
 975   SET_USE (op, val);
 976   val = fold (TREE_OPERAND (stmt, 1));
 977   SET_USE (op, nx);
 978
 979   return val;
 980 }
 981
 982 /* Tries to count the number of iterations of LOOP till it exits by EXIT
 983    by brute force -- i.e. by determining the value of the operands of the
 984    condition at EXIT in first few iterations of the loop (assuming that
 985    these values are constant) and determining the first one in that the
 986    condition is not satisfied.  Returns the constant giving the number
 987    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
 988
 989 tree
 990 loop_niter_by_eval (struct loop *loop, edge exit)
 991 {
 992   tree cond, cnd, acnd;
 993   tree op[2], val[2], next[2], aval[2], phi[2];
 994   unsigned i, j;
 995   enum tree_code cmp;
 996
 997   cond = last_stmt (exit->src);
 998   if (!cond || TREE_CODE (cond) != COND_EXPR)
 999     return chrec_dont_know;
1000
1001   cnd = COND_EXPR_COND (cond);
1002   if (exit->flags & EDGE_TRUE_VALUE)
1003     cnd = invert_truthvalue (cnd);
1004
1005   cmp = TREE_CODE (cnd);
1006   switch (cmp)
1007     {
1008     case EQ_EXPR:
1009     case NE_EXPR:
1010     case GT_EXPR:
1011     case GE_EXPR:
1012     case LT_EXPR:
1013     case LE_EXPR:
1014       for (j = 0; j < 2; j++)
1015         op[j] = TREE_OPERAND (cnd, j);
1016       break;
1017
1018     default:
1019       return chrec_dont_know;
1020     }
1021
1022   for (j = 0; j < 2; j++)
1023     {
1024       phi[j] = get_base_for (loop, op[j]);
1025       if (!phi[j])
1026         return chrec_dont_know;
1027     }
1028
1029   for (j = 0; j < 2; j++)
1030     {
1031       if (TREE_CODE (phi[j]) == PHI_NODE)
1032         {
1033           val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1034           next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1035         }
1036       else
1037         {
1038           val[j] = phi[j];
1039           next[j] = NULL_TREE;
1040           op[j] = NULL_TREE;
1041         }
1042     }
1043
1044   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1045     {
1046       for (j = 0; j < 2; j++)
1047         aval[j] = get_val_for (op[j], val[j]);
1048
1049       acnd = fold (build2 (cmp, boolean_type_node, aval[0], aval[1]));
1050       if (zero_p (acnd))
1051         {
1052           if (dump_file && (dump_flags & TDF_DETAILS))
1053             fprintf (dump_file,
1054                      "Proved that loop %d iterates %d times using brute force.\n",
1055                      loop->num, i);
1056           return build_int_cst (unsigned_type_node, i);
1057         }
1058
1059       for (j = 0; j < 2; j++)
1060         val[j] = get_val_for (next[j], val[j]);
1061     }
1062
1063   return chrec_dont_know;
1064 }
1065
1066 /* Finds the exit of the LOOP by that the loop exits after a constant
1067    number of iterations and stores the exit edge to *EXIT.  The constant
1068    giving the number of iterations of LOOP is returned.  The number of
1069    iterations is determined using loop_niter_by_eval (i.e. by brute force
1070    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1071    determines the number of iterations, chrec_dont_know is returned.  */
1072
1073 tree
1074 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1075 {
1076   unsigned n_exits, i;
1077   edge *exits = get_loop_exit_edges (loop, &n_exits);
1078   edge ex;
1079   tree niter = NULL_TREE, aniter;
1080
1081   *exit = NULL;
1082   for (i = 0; i < n_exits; i++)
1083     {
1084       ex = exits[i];
1085       if (!just_once_each_iteration_p (loop, ex->src))
1086         continue;
1087
1088       aniter = loop_niter_by_eval (loop, ex);
1089       if (chrec_contains_undetermined (aniter))
1090         continue;
1091
1092       if (niter
1093           && !tree_int_cst_lt (aniter, niter))
1094         continue;
1095
1096       niter = aniter;
1097       *exit = ex;
1098     }
1099   free (exits);
1100
1101   return niter ? niter : chrec_dont_know;
1102 }
1103
1104 /*
1105
1106    Analysis of upper bounds on number of iterations of a loop.
1107
1108 */
1109
1110 /* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1111    additional condition ADDITIONAL is recorded with the bound.  */
1112
1113 void
1114 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1115 {
1116   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1117
1118   if (dump_file && (dump_flags & TDF_DETAILS))
1119     {
1120       fprintf (dump_file, "Statements after ");
1121       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1122       fprintf (dump_file, " are executed at most ");
1123       print_generic_expr (dump_file, bound, TDF_SLIM);
1124       fprintf (dump_file, " times in loop %d.\n", loop->num);
1125     }
1126
1127   elt->bound = bound;
1128   elt->at_stmt = at_stmt;
1129   elt->additional = additional;
1130   elt->next = loop->bounds;
1131   loop->bounds = elt;
1132 }
1133
1134 /* Records estimates on numbers of iterations of LOOP.  */
1135
1136 static void
1137 estimate_numbers_of_iterations_loop (struct loop *loop)
1138 {
1139   edge *exits;
1140   tree niter, type;
1141   unsigned i, n_exits;
1142   struct tree_niter_desc niter_desc;
1143
1144   exits = get_loop_exit_edges (loop, &n_exits);
1145   for (i = 0; i < n_exits; i++)
1146     {
1147       if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
1148         continue;
1149
1150       niter = niter_desc.niter;
1151       type = TREE_TYPE (niter);
1152       if (!zero_p (niter_desc.may_be_zero)
1153           && !nonzero_p (niter_desc.may_be_zero))
1154         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1155                         build_int_cst_type (type, 0),
1156                         niter);
1157       record_estimate (loop, niter,
1158                        niter_desc.additional_info,
1159                        last_stmt (exits[i]->src));
1160     }
1161   free (exits);
1162
1163   /* Analyzes the bounds of arrays accessed in the loop.  */
1164   if (loop->estimated_nb_iterations == NULL_TREE)
1165     {
1166       varray_type datarefs;
1167       VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
1168       find_data_references_in_loop (loop, &datarefs);
1169       free_data_refs (datarefs);
1170     }
1171 }
1172
1173 /* Records estimates on numbers of iterations of LOOPS.  */
1174
1175 void
1176 estimate_numbers_of_iterations (struct loops *loops)
1177 {
1178   unsigned i;
1179   struct loop *loop;
1180
1181   for (i = 1; i < loops->num; i++)
1182     {
1183       loop = loops->parray[i];
1184       if (loop)
1185         estimate_numbers_of_iterations_loop (loop);
1186     }
1187 }
1188
1189 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1190    If neither of these relations can be proved, returns 2.  */
1191
1192 static int
1193 compare_trees (tree a, tree b)
1194 {
1195   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1196   tree type;
1197
1198   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1199     type = typea;
1200   else
1201     type = typeb;
1202
1203   a = fold_convert (type, a);
1204   b = fold_convert (type, b);
1205
1206   if (nonzero_p (fold (build2 (EQ_EXPR, boolean_type_node, a, b))))
1207     return 0;
1208   if (nonzero_p (fold (build2 (LT_EXPR, boolean_type_node, a, b))))
1209     return 1;
1210   if (nonzero_p (fold (build2 (GT_EXPR, boolean_type_node, a, b))))
1211     return -1;
1212
1213   return 2;
1214 }
1215
1216 /* Returns true if statement S1 dominates statement S2.  */
1217
1218 static bool
1219 stmt_dominates_stmt_p (tree s1, tree s2)
1220 {
1221   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1222
1223   if (!bb1
1224       || s1 == s2)
1225     return true;
1226
1227   if (bb1 == bb2)
1228     {
1229       block_stmt_iterator bsi;
1230
1231       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1232         if (bsi_stmt (bsi) == s1)
1233           return true;
1234
1235       return false;
1236     }
1237
1238   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1239 }
1240
1241 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1242    at AT_STMT in wider TYPE, using the fact that statement OF is executed at
1243    most BOUND times in the loop.  If it is possible, return the value of step
1244    of the induction variable in the TYPE, otherwise return NULL_TREE.
1245
1246    ADDITIONAL is the additional condition recorded for operands of the bound.
1247    This is useful in the following case, created by loop header copying:
1248
1249    i = 0;
1250    if (n > 0)
1251      do
1252        {
1253          something;
1254        } while (++i < n)
1255
1256    If the n > 0 condition is taken into account, the number of iterations of the
1257    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1258    assumption "n > 0" says us that the value of the number of iterations is at
1259    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1260
1261 static tree
1262 can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
1263                                   tree at_stmt,
1264                                   tree bound,
1265                                   tree additional,
1266                                   tree of)
1267 {
1268   tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
1269   tree valid_niter, extreme, unsigned_type, delta, bound_type;
1270   tree cond;
1271
1272   b = fold_convert (type, base);
1273   bplusstep = fold_convert (type,
1274                             fold (build2 (PLUS_EXPR, inner_type, base, step)));
1275   new_step = fold (build2 (MINUS_EXPR, type, bplusstep, b));
1276   if (TREE_CODE (new_step) != INTEGER_CST)
1277     return NULL_TREE;
1278
1279   switch (compare_trees (bplusstep, b))
1280     {
1281     case -1:
1282       extreme = upper_bound_in_type (type, inner_type);
1283       delta = fold (build2 (MINUS_EXPR, type, extreme, b));
1284       new_step_abs = new_step;
1285       break;
1286
1287     case 1:
1288       extreme = lower_bound_in_type (type, inner_type);
1289       new_step_abs = fold (build1 (NEGATE_EXPR, type, new_step));
1290       delta = fold (build2 (MINUS_EXPR, type, b, extreme));
1291       break;
1292
1293     case 0:
1294       return new_step;
1295
1296     default:
1297       return NULL_TREE;
1298     }
1299
1300   unsigned_type = unsigned_type_for (type);
1301   delta = fold_convert (unsigned_type, delta);
1302   new_step_abs = fold_convert (unsigned_type, new_step_abs);
1303   valid_niter = fold (build2 (FLOOR_DIV_EXPR, unsigned_type,
1304                              delta, new_step_abs));
1305
1306   bound_type = TREE_TYPE (bound);
1307   if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
1308     bound = fold_convert (unsigned_type, bound);
1309   else
1310     valid_niter = fold_convert (bound_type, valid_niter);
1311
1312   if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
1313     {
1314       /* After the statement OF we know that anything is executed at most
1315          BOUND times.  */
1316       cond = build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
1317     }
1318   else
1319     {
1320       /* Before the statement OF we know that anything is executed at most
1321          BOUND + 1 times.  */
1322       cond = build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
1323     }
1324
1325   cond = fold (cond);
1326   if (nonzero_p (cond))
1327     return new_step;
1328
1329   /* Try taking additional conditions into account.  */
1330   cond = build2 (TRUTH_OR_EXPR, boolean_type_node,
1331                 invert_truthvalue (additional),
1332                 cond);
1333   cond = fold (cond);
1334   if (nonzero_p (cond))
1335     return new_step;
1336
1337   return NULL_TREE;
1338 }
1339
1340 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1341    at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
1342    LOOP.  If it is possible, return the value of step of the induction variable
1343    in the TYPE, otherwise return NULL_TREE.  */
1344
1345 tree
1346 can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
1347                             tree at_stmt)
1348 {
1349   struct nb_iter_bound *bound;
1350   tree new_step;
1351
1352   for (bound = loop->bounds; bound; bound = bound->next)
1353     {
1354       new_step = can_count_iv_in_wider_type_bound (type, base, step,
1355                                                    at_stmt,
1356                                                    bound->bound,
1357                                                    bound->additional,
1358                                                    bound->at_stmt);
1359
1360       if (new_step)
1361         return new_step;
1362     }
1363
1364   return NULL_TREE;
1365 }
1366
1367 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
1368
1369 static void
1370 free_numbers_of_iterations_estimates_loop (struct loop *loop)
1371 {
1372   struct nb_iter_bound *bound, *next;
1373
1374   for (bound = loop->bounds; bound; bound = next)
1375     {
1376       next = bound->next;
1377       free (bound);
1378     }
1379
1380   loop->bounds = NULL;
1381 }
1382
1383 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
1384
1385 void
1386 free_numbers_of_iterations_estimates (struct loops *loops)
1387 {
1388   unsigned i;
1389   struct loop *loop;
1390
1391   for (i = 1; i < loops->num; i++)
1392     {
1393       loop = loops->parray[i];
1394       if (loop)
1395         free_numbers_of_iterations_estimates_loop (loop);
1396     }
1397 }