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