gcc/tree-ssa-loop-niter.c

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