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