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