gcc/tree-ssa-loop-niter.c

   1 /* Functions to determine/estimate number of iterations of a loop.
   2    Copyright (C) 2004 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 number of zeros at the end of binary representation of X.
  84
  85    ??? Use ffs if available?  */
  86
  87 static tree
  88 num_ending_zeros (tree x)
  89 {
  90   unsigned HOST_WIDE_INT fr, nfr;
  91   unsigned num, abits;
  92   tree type = TREE_TYPE (x);
  93
  94   if (TREE_INT_CST_LOW (x) == 0)
  95     {
  96       num = HOST_BITS_PER_WIDE_INT;
  97       fr = TREE_INT_CST_HIGH (x);
  98     }
  99   else
 100     {
 101       num = 0;
 102       fr = TREE_INT_CST_LOW (x);
 103     }
 104
 105   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
 106     {
 107       nfr = fr >> abits;
 108       if (nfr << abits == fr)
 109         {
 110           num += abits;
 111           fr = nfr;
 112         }
 113     }
 114
 115   if (num > TYPE_PRECISION (type))
 116     num = TYPE_PRECISION (type);
 117
 118   return build_int_cst_type (type, num);
 119 }
 120
 121 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
 122
 123 static tree
 124 inverse (tree x, tree mask)
 125 {
 126   tree type = TREE_TYPE (x);
 127   tree rslt;
 128   unsigned ctr = tree_floor_log2 (mask);
 129
 130   if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
 131     {
 132       unsigned HOST_WIDE_INT ix;
 133       unsigned HOST_WIDE_INT imask;
 134       unsigned HOST_WIDE_INT irslt = 1;
 135
 136       gcc_assert (cst_and_fits_in_hwi (x));
 137       gcc_assert (cst_and_fits_in_hwi (mask));
 138
 139       ix = int_cst_value (x);
 140       imask = int_cst_value (mask);
 141
 142       for (; ctr; ctr--)
 143         {
 144           irslt *= ix;
 145           ix *= ix;
 146         }
 147       irslt &= imask;
 148
 149       rslt = build_int_cst_type (type, irslt);
 150     }
 151   else
 152     {
 153       rslt = build_int_cst_type (type, 1);
 154       for (; ctr; ctr--)
 155         {
 156           rslt = fold_binary_to_constant (MULT_EXPR, type, rslt, x);
 157           x = fold_binary_to_constant (MULT_EXPR, type, x, x);
 158         }
 159       rslt = fold_binary_to_constant (BIT_AND_EXPR, type, rslt, mask);
 160     }
 161
 162   return rslt;
 163 }
 164
 165 /* Determine the number of iterations according to condition (for staying
 166    inside loop) which compares two induction variables using comparison
 167    operator CODE.  The induction variable on left side of the comparison
 168    has base BASE0 and step STEP0. the right-hand side one has base
 169    BASE1 and step STEP1.  Both induction variables must have type TYPE,
 170    which must be an integer or pointer type.  STEP0 and STEP1 must be
 171    constants (or NULL_TREE, which is interpreted as constant zero).
 172
 173    The results (number of iterations and assumptions as described in
 174    comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
 175    In case we are unable to determine number of iterations, contents of
 176    this structure is unchanged.  */
 177
 178 void
 179 number_of_iterations_cond (tree type, tree base0, tree step0,
 180                            enum tree_code code, tree base1, tree step1,
 181                            struct tree_niter_desc *niter)
 182 {
 183   tree step, delta, mmin, mmax;
 184   tree may_xform, bound, s, d, tmp;
 185   bool was_sharp = false;
 186   tree assumption;
 187   tree assumptions = boolean_true_node;
 188   tree noloop_assumptions = boolean_false_node;
 189   tree niter_type, signed_niter_type;
 190   tree bits;
 191
 192   /* The meaning of these assumptions is this:
 193      if !assumptions
 194        then the rest of information does not have to be valid
 195      if noloop_assumptions then the loop does not have to roll
 196        (but it is only conservative approximation, i.e. it only says that
 197        if !noloop_assumptions, then the loop does not end before the computed
 198        number of iterations)  */
 199
 200   /* Make < comparison from > ones.  */
 201   if (code == GE_EXPR
 202       || code == GT_EXPR)
 203     {
 204       SWAP (base0, base1);
 205       SWAP (step0, step1);
 206       code = swap_tree_comparison (code);
 207     }
 208
 209   /* We can handle the case when neither of the sides of the comparison is
 210      invariant, provided that the test is NE_EXPR.  This rarely occurs in
 211      practice, but it is simple enough to manage.  */
 212   if (!zero_p (step0) && !zero_p (step1))
 213     {
 214       if (code != NE_EXPR)
 215         return;
 216
 217       step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1);
 218       step1 = NULL_TREE;
 219     }
 220
 221   /* If the result is a constant,  the loop is weird.  More precise handling
 222      would be possible, but the situation is not common enough to waste time
 223      on it.  */
 224   if (zero_p (step0) && zero_p (step1))
 225     return;
 226
 227   /* Ignore loops of while (i-- < 10) type.  */
 228   if (code != NE_EXPR)
 229     {
 230       if (step0 && !tree_expr_nonnegative_p (step0))
 231         return;
 232
 233       if (!zero_p (step1) && tree_expr_nonnegative_p (step1))
 234         return;
 235     }
 236
 237   if (POINTER_TYPE_P (type))
 238     {
 239       /* We assume pointer arithmetic never overflows.  */
 240       mmin = mmax = NULL_TREE;
 241     }
 242   else
 243     {
 244       mmin = TYPE_MIN_VALUE (type);
 245       mmax = TYPE_MAX_VALUE (type);
 246     }
 247
 248   /* Some more condition normalization.  We must record some assumptions
 249      due to overflows.  */
 250
 251   if (code == LT_EXPR)
 252     {
 253       /* We want to take care only of <=; this is easy,
 254          as in cases the overflow would make the transformation unsafe the loop
 255          does not roll.  Seemingly it would make more sense to want to take
 256          care of <, as NE is more similar to it, but the problem is that here
 257          the transformation would be more difficult due to possibly infinite
 258          loops.  */
 259       if (zero_p (step0))
 260         {
 261           if (mmax)
 262             assumption = fold (build2 (EQ_EXPR, boolean_type_node, base0, mmax));
 263           else
 264             assumption = boolean_false_node;
 265           if (nonzero_p (assumption))
 266             goto zero_iter;
 267           base0 = fold (build2 (PLUS_EXPR, type, base0,
 268                                 build_int_cst_type (type, 1)));
 269         }
 270       else
 271         {
 272           if (mmin)
 273             assumption = fold (build2 (EQ_EXPR, boolean_type_node, base1, mmin));
 274           else
 275             assumption = boolean_false_node;
 276           if (nonzero_p (assumption))
 277             goto zero_iter;
 278           base1 = fold (build2 (MINUS_EXPR, type, base1,
 279                                 build_int_cst_type (type, 1)));
 280         }
 281       noloop_assumptions = assumption;
 282       code = LE_EXPR;
 283
 284       /* It will be useful to be able to tell the difference once more in
 285          <= -> != reduction.  */
 286       was_sharp = true;
 287     }
 288
 289   /* Take care of trivially infinite loops.  */
 290   if (code != NE_EXPR)
 291     {
 292       if (zero_p (step0)
 293           && mmin
 294           && operand_equal_p (base0, mmin, 0))
 295         return;
 296       if (zero_p (step1)
 297           && mmax
 298           && operand_equal_p (base1, mmax, 0))
 299         return;
 300     }
 301
 302   /* If we can we want to take care of NE conditions instead of size
 303      comparisons, as they are much more friendly (most importantly
 304      this takes care of special handling of loops with step 1).  We can
 305      do it if we first check that upper bound is greater or equal to
 306      lower bound, their difference is constant c modulo step and that
 307      there is not an overflow.  */
 308   if (code != NE_EXPR)
 309     {
 310       if (zero_p (step0))
 311         step = fold_unary_to_constant (NEGATE_EXPR, type, step1);
 312       else
 313         step = step0;
 314       delta = build2 (MINUS_EXPR, type, base1, base0);
 315       delta = fold (build2 (FLOOR_MOD_EXPR, type, delta, step));
 316       may_xform = boolean_false_node;
 317
 318       if (TREE_CODE (delta) == INTEGER_CST)
 319         {
 320           tmp = fold_binary_to_constant (MINUS_EXPR, type, step,
 321                                          build_int_cst_type (type, 1));
 322           if (was_sharp
 323               && operand_equal_p (delta, tmp, 0))
 324             {
 325               /* A special case.  We have transformed condition of type
 326                  for (i = 0; i < 4; i += 4)
 327                  into
 328                  for (i = 0; i <= 3; i += 4)
 329                  obviously if the test for overflow during that transformation
 330                  passed, we cannot overflow here.  Most importantly any
 331                  loop with sharp end condition and step 1 falls into this
 332                  category, so handling this case specially is definitely
 333                  worth the troubles.  */
 334               may_xform = boolean_true_node;
 335             }
 336           else if (zero_p (step0))
 337             {
 338               if (!mmin)
 339                 may_xform = boolean_true_node;
 340               else
 341                 {
 342                   bound = fold_binary_to_constant (PLUS_EXPR, type,
 343                                                    mmin, step);
 344                   bound = fold_binary_to_constant (MINUS_EXPR, type,
 345                                                    bound, delta);
 346                   may_xform = fold (build2 (LE_EXPR, boolean_type_node,
 347                                            bound, base0));
 348                 }
 349             }
 350           else
 351             {
 352               if (!mmax)
 353                 may_xform = boolean_true_node;
 354               else
 355                 {
 356                   bound = fold_binary_to_constant (MINUS_EXPR, type,
 357                                                    mmax, step);
 358                   bound = fold_binary_to_constant (PLUS_EXPR, type,
 359                                                    bound, delta);
 360                   may_xform = fold (build2 (LE_EXPR, boolean_type_node,
 361                                            base1, bound));
 362                 }
 363             }
 364         }
 365
 366       if (!zero_p (may_xform))
 367         {
 368           /* We perform the transformation always provided that it is not
 369              completely senseless.  This is OK, as we would need this assumption
 370              to determine the number of iterations anyway.  */
 371           if (!nonzero_p (may_xform))
 372             assumptions = may_xform;
 373
 374           if (zero_p (step0))
 375             {
 376               base0 = fold (build2 (PLUS_EXPR, type, base0, delta));
 377               base0 = fold (build2 (MINUS_EXPR, type, base0, step));
 378             }
 379           else
 380             {
 381               base1 = fold (build2 (MINUS_EXPR, type, base1, delta));
 382               base1 = fold (build2 (PLUS_EXPR, type, base1, step));
 383             }
 384
 385           assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, base1));
 386           noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
 387                                             noloop_assumptions, assumption));
 388           code = NE_EXPR;
 389         }
 390     }
 391
 392   /* Count the number of iterations.  */
 393   niter_type = unsigned_type_for (type);
 394   signed_niter_type = signed_type_for (type);
 395
 396   if (code == NE_EXPR)
 397     {
 398       /* Everything we do here is just arithmetics modulo size of mode.  This
 399          makes us able to do more involved computations of number of iterations
 400          than in other cases.  First transform the condition into shape
 401          s * i <> c, with s positive.  */
 402       base1 = fold (build2 (MINUS_EXPR, type, base1, base0));
 403       base0 = NULL_TREE;
 404       if (!zero_p (step1))
 405         step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
 406       step1 = NULL_TREE;
 407       if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
 408         {
 409           step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
 410           base1 = fold (build1 (NEGATE_EXPR, type, base1));
 411         }
 412
 413       base1 = fold_convert (niter_type, base1);
 414       step0 = fold_convert (niter_type, step0);
 415
 416       /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
 417          is infinite.  Otherwise, the number of iterations is
 418          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
 419       bits = num_ending_zeros (step0);
 420       d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
 421                                    build_int_cst_type (niter_type, 1), bits);
 422       s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, step0, bits);
 423
 424       bound = build_low_bits_mask (niter_type,
 425                                    (TYPE_PRECISION (niter_type)
 426                                     - tree_low_cst (bits, 1)));
 427
 428       assumption = fold (build2 (FLOOR_MOD_EXPR, niter_type, base1, d));
 429       assumption = fold (build2 (EQ_EXPR, boolean_type_node,
 430                                  assumption,
 431                                  build_int_cst (niter_type, 0)));
 432       assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
 433                                   assumptions, assumption));
 434
 435       tmp = fold (build2 (EXACT_DIV_EXPR, niter_type, base1, d));
 436       tmp = fold (build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
 437       niter->niter = fold (build2 (BIT_AND_EXPR, niter_type, tmp, bound));
 438     }
 439   else
 440     {
 441       if (zero_p (step1))
 442         /* Condition in shape a + s * i <= b
 443            We must know that b + s does not overflow and a <= b + s and then we
 444            can compute number of iterations as (b + s - a) / s.  (It might
 445            seem that we in fact could be more clever about testing the b + s
 446            overflow condition using some information about b - a mod s,
 447            but it was already taken into account during LE -> NE transform).  */
 448         {
 449           if (mmax)
 450             {
 451               bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0);
 452               assumption = fold (build2 (LE_EXPR, boolean_type_node,
 453                                          base1, bound));
 454               assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
 455                                           assumptions, assumption));
 456             }
 457
 458           step = step0;
 459           tmp = fold (build2 (PLUS_EXPR, type, base1, step0));
 460           assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, tmp));
 461           delta = fold (build2 (PLUS_EXPR, type, base1, step));
 462           delta = fold (build2 (MINUS_EXPR, type, delta, base0));
 463           delta = fold_convert (niter_type, delta);
 464         }
 465       else
 466         {
 467           /* Condition in shape a <= b - s * i
 468              We must know that a - s does not overflow and a - s <= b and then
 469              we can again compute number of iterations as (b - (a - s)) / s.  */
 470           if (mmin)
 471             {
 472               bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
 473               assumption = fold (build2 (LE_EXPR, boolean_type_node,
 474                                         bound, base0));
 475               assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
 476                                          assumptions, assumption));
 477             }
 478           step = fold (build1 (NEGATE_EXPR, type, step1));
 479           tmp = fold (build2 (PLUS_EXPR, type, base0, step1));
 480           assumption = fold (build2 (GT_EXPR, boolean_type_node, tmp, base1));
 481           delta = fold (build2 (MINUS_EXPR, type, base0, step));
 482           delta = fold (build2 (MINUS_EXPR, type, base1, delta));
 483           delta = fold_convert (niter_type, delta);
 484         }
 485       noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
 486                                         noloop_assumptions, assumption));
 487       delta = fold (build2 (FLOOR_DIV_EXPR, niter_type, delta,
 488                             fold_convert (niter_type, step)));
 489       niter->niter = delta;
 490     }
 491
 492   niter->assumptions = assumptions;
 493   niter->may_be_zero = noloop_assumptions;
 494   return;
 495
 496 zero_iter:
 497   niter->assumptions = boolean_true_node;
 498   niter->may_be_zero = boolean_true_node;
 499   niter->niter = build_int_cst_type (type, 0);
 500   return;
 501 }
 502
 503 /* Tries to simplify EXPR using the evolutions of the loop invariants
 504    in the superloops of LOOP.  Returns the simplified expression
 505    (or EXPR unchanged, if no simplification was possible).  */
 506
 507 static tree
 508 simplify_using_outer_evolutions (struct loop *loop, tree expr)
 509 {
 510   enum tree_code code = TREE_CODE (expr);
 511   bool changed;
 512   tree e, e0, e1, e2;
 513
 514   if (is_gimple_min_invariant (expr))
 515     return expr;
 516
 517   if (code == TRUTH_OR_EXPR
 518       || code == TRUTH_AND_EXPR
 519       || code == COND_EXPR)
 520     {
 521       changed = false;
 522
 523       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
 524       if (TREE_OPERAND (expr, 0) != e0)
 525         changed = true;
 526
 527       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
 528       if (TREE_OPERAND (expr, 1) != e1)
 529         changed = true;
 530
 531       if (code == COND_EXPR)
 532         {
 533           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
 534           if (TREE_OPERAND (expr, 2) != e2)
 535             changed = true;
 536         }
 537       else
 538         e2 = NULL_TREE;
 539
 540       if (changed)
 541         {
 542           if (code == COND_EXPR)
 543             expr = build3 (code, boolean_type_node, e0, e1, e2);
 544           else
 545             expr = build2 (code, boolean_type_node, e0, e1);
 546           expr = fold (expr);
 547         }
 548
 549       return expr;
 550     }
 551
 552   e = instantiate_parameters (loop, expr);
 553   if (is_gimple_min_invariant (e))
 554     return e;
 555
 556   return expr;
 557 }
 558
 559 /* Substitute NEW for OLD in EXPR and fold the result.  */
 560
 561 static tree
 562 simplify_replace_tree (tree expr, tree old, tree new)
 563 {
 564   unsigned i, n;
 565   tree ret = NULL_TREE, e, se;
 566
 567   if (!expr)
 568     return NULL_TREE;
 569
 570   if (expr == old
 571       || operand_equal_p (expr, old, 0))
 572     return unshare_expr (new);
 573
 574   if (!EXPR_P (expr))
 575     return expr;
 576
 577   n = TREE_CODE_LENGTH (TREE_CODE (expr));
 578   for (i = 0; i < n; i++)
 579     {
 580       e = TREE_OPERAND (expr, i);
 581       se = simplify_replace_tree (e, old, new);
 582       if (e == se)
 583         continue;
 584
 585       if (!ret)
 586         ret = copy_node (expr);
 587
 588       TREE_OPERAND (ret, i) = se;
 589     }
 590
 591   return (ret ? fold (ret) : expr);
 592 }
 593
 594 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
 595    expression (or EXPR unchanged, if no simplification was possible).*/
 596
 597 static tree
 598 tree_simplify_using_condition (tree cond, tree expr)
 599 {
 600   bool changed;
 601   tree e, e0, e1, e2, notcond;
 602   enum tree_code code = TREE_CODE (expr);
 603
 604   if (code == INTEGER_CST)
 605     return expr;
 606
 607   if (code == TRUTH_OR_EXPR
 608       || code == TRUTH_AND_EXPR
 609       || code == COND_EXPR)
 610     {
 611       changed = false;
 612
 613       e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
 614       if (TREE_OPERAND (expr, 0) != e0)
 615         changed = true;
 616
 617       e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
 618       if (TREE_OPERAND (expr, 1) != e1)
 619         changed = true;
 620
 621       if (code == COND_EXPR)
 622         {
 623           e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
 624           if (TREE_OPERAND (expr, 2) != e2)
 625             changed = true;
 626         }
 627       else
 628         e2 = NULL_TREE;
 629
 630       if (changed)
 631         {
 632           if (code == COND_EXPR)
 633             expr = build3 (code, boolean_type_node, e0, e1, e2);
 634           else
 635             expr = build2 (code, boolean_type_node, e0, e1);
 636           expr = fold (expr);
 637         }
 638
 639       return expr;
 640     }
 641
 642   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
 643      propagation, and vice versa.  Fold does not handle this, since it is
 644      considered too expensive.  */
 645   if (TREE_CODE (cond) == EQ_EXPR)
 646     {
 647       e0 = TREE_OPERAND (cond, 0);
 648       e1 = TREE_OPERAND (cond, 1);
 649
 650       /* We know that e0 == e1.  Check whether we cannot simplify expr
 651          using this fact.  */
 652       e = simplify_replace_tree (expr, e0, e1);
 653       if (zero_p (e) || nonzero_p (e))
 654         return e;
 655
 656       e = simplify_replace_tree (expr, e1, e0);
 657       if (zero_p (e) || nonzero_p (e))
 658         return e;
 659     }
 660   if (TREE_CODE (expr) == EQ_EXPR)
 661     {
 662       e0 = TREE_OPERAND (expr, 0);
 663       e1 = TREE_OPERAND (expr, 1);
 664
 665       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
 666       e = simplify_replace_tree (cond, e0, e1);
 667       if (zero_p (e))
 668         return e;
 669       e = simplify_replace_tree (cond, e1, e0);
 670       if (zero_p (e))
 671         return e;
 672     }
 673   if (TREE_CODE (expr) == NE_EXPR)
 674     {
 675       e0 = TREE_OPERAND (expr, 0);
 676       e1 = TREE_OPERAND (expr, 1);
 677
 678       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
 679       e = simplify_replace_tree (cond, e0, e1);
 680       if (zero_p (e))
 681         return boolean_true_node;
 682       e = simplify_replace_tree (cond, e1, e0);
 683       if (zero_p (e))
 684         return boolean_true_node;
 685     }
 686
 687   /* Check whether COND ==> EXPR.  */
 688   notcond = invert_truthvalue (cond);
 689   e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
 690                    notcond, expr));
 691   if (nonzero_p (e))
 692     return e;
 693
 694   /* Check whether COND ==> not EXPR.  */
 695   e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
 696                    cond, expr));
 697   if (zero_p (e))
 698     return e;
 699
 700   return expr;
 701 }
 702
 703 /* Tries to simplify EXPR using the conditions on entry to LOOP.
 704    Record the conditions used for simplification to CONDS_USED.
 705    Returns the simplified expression (or EXPR unchanged, if no
 706    simplification was possible).*/
 707
 708 static tree
 709 simplify_using_initial_conditions (struct loop *loop, tree expr,
 710                                    tree *conds_used)
 711 {
 712   edge e;
 713   basic_block bb;
 714   tree exp, cond;
 715
 716   if (TREE_CODE (expr) == INTEGER_CST)
 717     return expr;
 718
 719   for (bb = loop->header;
 720        bb != ENTRY_BLOCK_PTR;
 721        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 722     {
 723       e = EDGE_PRED (bb, 0);
 724       if (EDGE_COUNT (bb->preds) > 1)
 725         continue;
 726
 727       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
 728         continue;
 729
 730       cond = COND_EXPR_COND (last_stmt (e->src));
 731       if (e->flags & EDGE_FALSE_VALUE)
 732         cond = invert_truthvalue (cond);
 733       exp = tree_simplify_using_condition (cond, expr);
 734
 735       if (exp != expr)
 736         *conds_used = fold (build2 (TRUTH_AND_EXPR,
 737                                    boolean_type_node,
 738                                    *conds_used,
 739                                    cond));
 740
 741       expr = exp;
 742     }
 743
 744   return expr;
 745 }
 746
 747 /* Stores description of number of iterations of LOOP derived from
 748    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
 749    useful information could be derived (and fields of NITER has
 750    meaning described in comments at struct tree_niter_desc
 751    declaration), false otherwise.  */
 752
 753 bool
 754 number_of_iterations_exit (struct loop *loop, edge exit,
 755                            struct tree_niter_desc *niter)
 756 {
 757   tree stmt, cond, type;
 758   tree op0, base0, step0;
 759   tree op1, base1, step1;
 760   enum tree_code code;
 761
 762   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
 763     return false;
 764
 765   niter->assumptions = boolean_false_node;
 766   stmt = last_stmt (exit->src);
 767   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
 768     return false;
 769
 770   /* We want the condition for staying inside loop.  */
 771   cond = COND_EXPR_COND (stmt);
 772   if (exit->flags & EDGE_TRUE_VALUE)
 773     cond = invert_truthvalue (cond);
 774
 775   code = TREE_CODE (cond);
 776   switch (code)
 777     {
 778     case GT_EXPR:
 779     case GE_EXPR:
 780     case NE_EXPR:
 781     case LT_EXPR:
 782     case LE_EXPR:
 783       break;
 784
 785     default:
 786       return false;
 787     }
 788
 789   op0 = TREE_OPERAND (cond, 0);
 790   op1 = TREE_OPERAND (cond, 1);
 791   type = TREE_TYPE (op0);
 792
 793   if (TREE_CODE (type) != INTEGER_TYPE
 794       && !POINTER_TYPE_P (type))
 795     return false;
 796
 797   if (!simple_iv (loop, stmt, op0, &base0, &step0))
 798     return false;
 799   if (!simple_iv (loop, stmt, op1, &base1, &step1))
 800     return false;
 801
 802   niter->niter = NULL_TREE;
 803   number_of_iterations_cond (type, base0, step0, code, base1, step1,
 804                              niter);
 805   if (!niter->niter)
 806     return false;
 807
 808   niter->assumptions = simplify_using_outer_evolutions (loop,
 809                                                         niter->assumptions);
 810   niter->may_be_zero = simplify_using_outer_evolutions (loop,
 811                                                         niter->may_be_zero);
 812   niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
 813
 814   niter->additional_info = boolean_true_node;
 815   niter->assumptions
 816           = simplify_using_initial_conditions (loop,
 817                                                niter->assumptions,
 818                                                &niter->additional_info);
 819   niter->may_be_zero
 820           = simplify_using_initial_conditions (loop,
 821                                                niter->may_be_zero,
 822                                                &niter->additional_info);
 823   return integer_onep (niter->assumptions);
 824 }
 825
 826 /*
 827
 828    Analysis of a number of iterations of a loop by a brute-force evaluation.
 829
 830 */
 831
 832 /* Bound on the number of iterations we try to evaluate.  */
 833
 834 #define MAX_ITERATIONS_TO_TRACK \
 835   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
 836
 837 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
 838    result by a chain of operations such that all but exactly one of their
 839    operands are constants.  */
 840
 841 static tree
 842 chain_of_csts_start (struct loop *loop, tree x)
 843 {
 844   tree stmt = SSA_NAME_DEF_STMT (x);
 845   basic_block bb = bb_for_stmt (stmt);
 846   use_optype uses;
 847
 848   if (!bb
 849       || !flow_bb_inside_loop_p (loop, bb))
 850     return NULL_TREE;
 851
 852   if (TREE_CODE (stmt) == PHI_NODE)
 853     {
 854       if (bb == loop->header)
 855         return stmt;
 856
 857       return NULL_TREE;
 858     }
 859
 860   if (TREE_CODE (stmt) != MODIFY_EXPR)
 861     return NULL_TREE;
 862
 863   get_stmt_operands (stmt);
 864   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
 865     return NULL_TREE;
 866   if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
 867     return NULL_TREE;
 868   if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
 869     return NULL_TREE;
 870   if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
 871     return NULL_TREE;
 872   uses = STMT_USE_OPS (stmt);
 873   if (NUM_USES (uses) != 1)
 874     return NULL_TREE;
 875
 876   return chain_of_csts_start (loop, USE_OP (uses, 0));
 877 }
 878
 879 /* Determines whether the expression X is derived from a result of a phi node
 880    in header of LOOP such that
 881
 882    * the derivation of X consists only from operations with constants
 883    * the initial value of the phi node is constant
 884    * the value of the phi node in the next iteration can be derived from the
 885      value in the current iteration by a chain of operations with constants.
 886
 887    If such phi node exists, it is returned.  If X is a constant, X is returned
 888    unchanged.  Otherwise NULL_TREE is returned.  */
 889
 890 static tree
 891 get_base_for (struct loop *loop, tree x)
 892 {
 893   tree phi, init, next;
 894
 895   if (is_gimple_min_invariant (x))
 896     return x;
 897
 898   phi = chain_of_csts_start (loop, x);
 899   if (!phi)
 900     return NULL_TREE;
 901
 902   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
 903   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
 904
 905   if (TREE_CODE (next) != SSA_NAME)
 906     return NULL_TREE;
 907
 908   if (!is_gimple_min_invariant (init))
 909     return NULL_TREE;
 910
 911   if (chain_of_csts_start (loop, next) != phi)
 912     return NULL_TREE;
 913
 914   return phi;
 915 }
 916
 917 /* Given an expression X, then
 918
 919    * if BASE is NULL_TREE, X must be a constant and we return X.
 920    * otherwise X is a SSA name, whose value in the considered loop is derived
 921      by a chain of operations with constant from a result of a phi node in
 922      the header of the loop.  Then we return value of X when the value of the
 923      result of this phi node is given by the constant BASE.  */
 924
 925 static tree
 926 get_val_for (tree x, tree base)
 927 {
 928   tree stmt, nx, val;
 929   use_optype uses;
 930   use_operand_p op;
 931
 932   if (!x)
 933     return base;
 934
 935   stmt = SSA_NAME_DEF_STMT (x);
 936   if (TREE_CODE (stmt) == PHI_NODE)
 937     return base;
 938
 939   uses = STMT_USE_OPS (stmt);
 940   op = USE_OP_PTR (uses, 0);
 941
 942   nx = USE_FROM_PTR (op);
 943   val = get_val_for (nx, base);
 944   SET_USE (op, val);
 945   val = fold (TREE_OPERAND (stmt, 1));
 946   SET_USE (op, nx);
 947
 948   return val;
 949 }
 950
 951 /* Tries to count the number of iterations of LOOP till it exits by EXIT
 952    by brute force -- i.e. by determining the value of the operands of the
 953    condition at EXIT in first few iterations of the loop (assuming that
 954    these values are constant) and determining the first one in that the
 955    condition is not satisfied.  Returns the constant giving the number
 956    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
 957
 958 tree
 959 loop_niter_by_eval (struct loop *loop, edge exit)
 960 {
 961   tree cond, cnd, acnd;
 962   tree op[2], val[2], next[2], aval[2], phi[2];
 963   unsigned i, j;
 964   enum tree_code cmp;
 965
 966   cond = last_stmt (exit->src);
 967   if (!cond || TREE_CODE (cond) != COND_EXPR)
 968     return chrec_dont_know;
 969
 970   cnd = COND_EXPR_COND (cond);
 971   if (exit->flags & EDGE_TRUE_VALUE)
 972     cnd = invert_truthvalue (cnd);
 973
 974   cmp = TREE_CODE (cnd);
 975   switch (cmp)
 976     {
 977     case EQ_EXPR:
 978     case NE_EXPR:
 979     case GT_EXPR:
 980     case GE_EXPR:
 981     case LT_EXPR:
 982     case LE_EXPR:
 983       for (j = 0; j < 2; j++)
 984         op[j] = TREE_OPERAND (cnd, j);
 985       break;
 986
 987     default:
 988       return chrec_dont_know;
 989     }
 990
 991   for (j = 0; j < 2; j++)
 992     {
 993       phi[j] = get_base_for (loop, op[j]);
 994       if (!phi[j])
 995         return chrec_dont_know;
 996     }
 997
 998   for (j = 0; j < 2; j++)
 999     {
1000       if (TREE_CODE (phi[j]) == PHI_NODE)
1001         {
1002           val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1003           next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1004         }
1005       else
1006         {
1007           val[j] = phi[j];
1008           next[j] = NULL_TREE;
1009           op[j] = NULL_TREE;
1010         }
1011     }
1012
1013   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1014     {
1015       for (j = 0; j < 2; j++)
1016         aval[j] = get_val_for (op[j], val[j]);
1017
1018       acnd = fold (build2 (cmp, boolean_type_node, aval[0], aval[1]));
1019       if (zero_p (acnd))
1020         {
1021           if (dump_file && (dump_flags & TDF_DETAILS))
1022             fprintf (dump_file,
1023                      "Proved that loop %d iterates %d times using brute force.\n",
1024                      loop->num, i);
1025           return build_int_cst (unsigned_type_node, i);
1026         }
1027
1028       for (j = 0; j < 2; j++)
1029         val[j] = get_val_for (next[j], val[j]);
1030     }
1031
1032   return chrec_dont_know;
1033 }
1034
1035 /* Finds the exit of the LOOP by that the loop exits after a constant
1036    number of iterations and stores the exit edge to *EXIT.  The constant
1037    giving the number of iterations of LOOP is returned.  The number of
1038    iterations is determined using loop_niter_by_eval (i.e. by brute force
1039    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1040    determines the number of iterations, chrec_dont_know is returned.  */
1041
1042 tree
1043 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1044 {
1045   unsigned n_exits, i;
1046   edge *exits = get_loop_exit_edges (loop, &n_exits);
1047   edge ex;
1048   tree niter = NULL_TREE, aniter;
1049
1050   *exit = NULL;
1051   for (i = 0; i < n_exits; i++)
1052     {
1053       ex = exits[i];
1054       if (!just_once_each_iteration_p (loop, ex->src))
1055         continue;
1056
1057       aniter = loop_niter_by_eval (loop, ex);
1058       if (chrec_contains_undetermined (aniter)
1059           || TREE_CODE (aniter) != INTEGER_CST)
1060         continue;
1061
1062       if (niter
1063           && !nonzero_p (fold (build2 (LT_EXPR, boolean_type_node,
1064                                              aniter, niter))))
1065         continue;
1066
1067       niter = aniter;
1068       *exit = ex;
1069     }
1070   free (exits);
1071
1072   return niter ? niter : chrec_dont_know;
1073 }
1074
1075 /*
1076
1077    Analysis of upper bounds on number of iterations of a loop.
1078
1079 */
1080
1081 /* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1082    additional condition ADDITIONAL is recorded with the bound.  */
1083
1084 void
1085 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1086 {
1087   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1088
1089   if (dump_file && (dump_flags & TDF_DETAILS))
1090     {
1091       fprintf (dump_file, "Statements after ");
1092       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1093       fprintf (dump_file, " are executed at most ");
1094       print_generic_expr (dump_file, bound, TDF_SLIM);
1095       fprintf (dump_file, " times in loop %d.\n", loop->num);
1096     }
1097
1098   elt->bound = bound;
1099   elt->at_stmt = at_stmt;
1100   elt->additional = additional;
1101   elt->next = loop->bounds;
1102   loop->bounds = elt;
1103 }
1104
1105 /* Records estimates on numbers of iterations of LOOP.  */
1106
1107 static void
1108 estimate_numbers_of_iterations_loop (struct loop *loop)
1109 {
1110   edge *exits;
1111   tree niter, type;
1112   unsigned i, n_exits;
1113   struct tree_niter_desc niter_desc;
1114
1115   exits = get_loop_exit_edges (loop, &n_exits);
1116   for (i = 0; i < n_exits; i++)
1117     {
1118       if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
1119         continue;
1120
1121       niter = niter_desc.niter;
1122       type = TREE_TYPE (niter);
1123       if (!zero_p (niter_desc.may_be_zero)
1124           && !nonzero_p (niter_desc.may_be_zero))
1125         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1126                         build_int_cst_type (type, 0),
1127                         niter);
1128       record_estimate (loop, niter,
1129                        niter_desc.additional_info,
1130                        last_stmt (exits[i]->src));
1131     }
1132   free (exits);
1133
1134   /* Analyzes the bounds of arrays accessed in the loop.  */
1135   if (loop->estimated_nb_iterations == NULL_TREE)
1136     {
1137       varray_type datarefs;
1138       VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
1139       find_data_references_in_loop (loop, &datarefs);
1140       free_data_refs (datarefs);
1141     }
1142 }
1143
1144 /* Records estimates on numbers of iterations of LOOPS.  */
1145
1146 void
1147 estimate_numbers_of_iterations (struct loops *loops)
1148 {
1149   unsigned i;
1150   struct loop *loop;
1151
1152   for (i = 1; i < loops->num; i++)
1153     {
1154       loop = loops->parray[i];
1155       if (loop)
1156         estimate_numbers_of_iterations_loop (loop);
1157     }
1158 }
1159
1160 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1161    If neither of these relations can be proved, returns 2.  */
1162
1163 static int
1164 compare_trees (tree a, tree b)
1165 {
1166   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1167   tree type;
1168
1169   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1170     type = typea;
1171   else
1172     type = typeb;
1173
1174   a = fold_convert (type, a);
1175   b = fold_convert (type, b);
1176
1177   if (nonzero_p (fold (build2 (EQ_EXPR, boolean_type_node, a, b))))
1178     return 0;
1179   if (nonzero_p (fold (build2 (LT_EXPR, boolean_type_node, a, b))))
1180     return 1;
1181   if (nonzero_p (fold (build2 (GT_EXPR, boolean_type_node, a, b))))
1182     return -1;
1183
1184   return 2;
1185 }
1186
1187 /* Returns true if statement S1 dominates statement S2.  */
1188
1189 static bool
1190 stmt_dominates_stmt_p (tree s1, tree s2)
1191 {
1192   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1193
1194   if (!bb1
1195       || s1 == s2)
1196     return true;
1197
1198   if (bb1 == bb2)
1199     {
1200       block_stmt_iterator bsi;
1201
1202       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1203         if (bsi_stmt (bsi) == s1)
1204           return true;
1205
1206       return false;
1207     }
1208
1209   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1210 }
1211
1212 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1213    at AT_STMT in wider TYPE, using the fact that statement OF is executed at
1214    most BOUND times in the loop.  If it is possible, return the value of step
1215    of the induction variable in the TYPE, otherwise return NULL_TREE.
1216
1217    ADDITIONAL is the additional condition recorded for operands of the bound.
1218    This is useful in the following case, created by loop header copying:
1219
1220    i = 0;
1221    if (n > 0)
1222      do
1223        {
1224          something;
1225        } while (++i < n)
1226
1227    If the n > 0 condition is taken into account, the number of iterations of the
1228    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1229    assumption "n > 0" says us that the value of the number of iterations is at
1230    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1231
1232 static tree
1233 can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
1234                                   tree at_stmt,
1235                                   tree bound,
1236                                   tree additional,
1237                                   tree of)
1238 {
1239   tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
1240   tree valid_niter, extreme, unsigned_type, delta, bound_type;
1241   tree cond;
1242
1243   b = fold_convert (type, base);
1244   bplusstep = fold_convert (type,
1245                             fold (build2 (PLUS_EXPR, inner_type, base, step)));
1246   new_step = fold (build2 (MINUS_EXPR, type, bplusstep, b));
1247   if (TREE_CODE (new_step) != INTEGER_CST)
1248     return NULL_TREE;
1249
1250   switch (compare_trees (bplusstep, b))
1251     {
1252     case -1:
1253       extreme = upper_bound_in_type (type, inner_type);
1254       delta = fold (build2 (MINUS_EXPR, type, extreme, b));
1255       new_step_abs = new_step;
1256       break;
1257
1258     case 1:
1259       extreme = lower_bound_in_type (type, inner_type);
1260       new_step_abs = fold (build1 (NEGATE_EXPR, type, new_step));
1261       delta = fold (build2 (MINUS_EXPR, type, b, extreme));
1262       break;
1263
1264     case 0:
1265       return new_step;
1266
1267     default:
1268       return NULL_TREE;
1269     }
1270
1271   unsigned_type = unsigned_type_for (type);
1272   delta = fold_convert (unsigned_type, delta);
1273   new_step_abs = fold_convert (unsigned_type, new_step_abs);
1274   valid_niter = fold (build2 (FLOOR_DIV_EXPR, unsigned_type,
1275                              delta, new_step_abs));
1276
1277   bound_type = TREE_TYPE (bound);
1278   if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
1279     bound = fold_convert (unsigned_type, bound);
1280   else
1281     valid_niter = fold_convert (bound_type, valid_niter);
1282
1283   if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
1284     {
1285       /* After the statement OF we know that anything is executed at most
1286          BOUND times.  */
1287       cond = build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
1288     }
1289   else
1290     {
1291       /* Before the statement OF we know that anything is executed at most
1292          BOUND + 1 times.  */
1293       cond = build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
1294     }
1295
1296   cond = fold (cond);
1297   if (nonzero_p (cond))
1298     return new_step;
1299
1300   /* Try taking additional conditions into account.  */
1301   cond = build2 (TRUTH_OR_EXPR, boolean_type_node,
1302                 invert_truthvalue (additional),
1303                 cond);
1304   cond = fold (cond);
1305   if (nonzero_p (cond))
1306     return new_step;
1307
1308   return NULL_TREE;
1309 }
1310
1311 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1312    at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
1313    LOOP.  If it is possible, return the value of step of the induction variable
1314    in the TYPE, otherwise return NULL_TREE.  */
1315
1316 tree
1317 can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
1318                             tree at_stmt)
1319 {
1320   struct nb_iter_bound *bound;
1321   tree new_step;
1322
1323   for (bound = loop->bounds; bound; bound = bound->next)
1324     {
1325       new_step = can_count_iv_in_wider_type_bound (type, base, step,
1326                                                    at_stmt,
1327                                                    bound->bound,
1328                                                    bound->additional,
1329                                                    bound->at_stmt);
1330
1331       if (new_step)
1332         return new_step;
1333     }
1334
1335   return NULL_TREE;
1336 }
1337
1338 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
1339
1340 static void
1341 free_numbers_of_iterations_estimates_loop (struct loop *loop)
1342 {
1343   struct nb_iter_bound *bound, *next;
1344
1345   for (bound = loop->bounds; bound; bound = next)
1346     {
1347       next = bound->next;
1348       free (bound);
1349     }
1350
1351   loop->bounds = NULL;
1352 }
1353
1354 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
1355
1356 void
1357 free_numbers_of_iterations_estimates (struct loops *loops)
1358 {
1359   unsigned i;
1360   struct loop *loop;
1361
1362   for (i = 1; i < loops->num; i++)
1363     {
1364       loop = loops->parray[i];
1365       if (loop)
1366         free_numbers_of_iterations_estimates_loop (loop);
1367     }
1368 }