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 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
 628    expression (or EXPR unchanged, if no simplification was possible).*/
 629
 630 static tree
 631 tree_simplify_using_condition (tree cond, tree expr)
 632 {
 633   bool changed;
 634   tree e, e0, e1, e2, notcond;
 635   enum tree_code code = TREE_CODE (expr);
 636
 637   if (code == INTEGER_CST)
 638     return expr;
 639
 640   if (code == TRUTH_OR_EXPR
 641       || code == TRUTH_AND_EXPR
 642       || code == COND_EXPR)
 643     {
 644       changed = false;
 645
 646       e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
 647       if (TREE_OPERAND (expr, 0) != e0)
 648         changed = true;
 649
 650       e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
 651       if (TREE_OPERAND (expr, 1) != e1)
 652         changed = true;
 653
 654       if (code == COND_EXPR)
 655         {
 656           e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
 657           if (TREE_OPERAND (expr, 2) != e2)
 658             changed = true;
 659         }
 660       else
 661         e2 = NULL_TREE;
 662
 663       if (changed)
 664         {
 665           if (code == COND_EXPR)
 666             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
 667           else
 668             expr = fold_build2 (code, boolean_type_node, e0, e1);
 669         }
 670
 671       return expr;
 672     }
 673
 674   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
 675      propagation, and vice versa.  Fold does not handle this, since it is
 676      considered too expensive.  */
 677   if (TREE_CODE (cond) == EQ_EXPR)
 678     {
 679       e0 = TREE_OPERAND (cond, 0);
 680       e1 = TREE_OPERAND (cond, 1);
 681
 682       /* We know that e0 == e1.  Check whether we cannot simplify expr
 683          using this fact.  */
 684       e = simplify_replace_tree (expr, e0, e1);
 685       if (zero_p (e) || nonzero_p (e))
 686         return e;
 687
 688       e = simplify_replace_tree (expr, e1, e0);
 689       if (zero_p (e) || nonzero_p (e))
 690         return e;
 691     }
 692   if (TREE_CODE (expr) == EQ_EXPR)
 693     {
 694       e0 = TREE_OPERAND (expr, 0);
 695       e1 = TREE_OPERAND (expr, 1);
 696
 697       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
 698       e = simplify_replace_tree (cond, e0, e1);
 699       if (zero_p (e))
 700         return e;
 701       e = simplify_replace_tree (cond, e1, e0);
 702       if (zero_p (e))
 703         return e;
 704     }
 705   if (TREE_CODE (expr) == NE_EXPR)
 706     {
 707       e0 = TREE_OPERAND (expr, 0);
 708       e1 = TREE_OPERAND (expr, 1);
 709
 710       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
 711       e = simplify_replace_tree (cond, e0, e1);
 712       if (zero_p (e))
 713         return boolean_true_node;
 714       e = simplify_replace_tree (cond, e1, e0);
 715       if (zero_p (e))
 716         return boolean_true_node;
 717     }
 718
 719   /* Check whether COND ==> EXPR.  */
 720   notcond = invert_truthvalue (cond);
 721   e = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
 722                    notcond, expr);
 723   if (nonzero_p (e))
 724     return e;
 725
 726   /* Check whether COND ==> not EXPR.  */
 727   e = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 728                    cond, expr);
 729   if (zero_p (e))
 730     return e;
 731
 732   return expr;
 733 }
 734
 735 /* Tries to simplify EXPR using the conditions on entry to LOOP.
 736    Record the conditions used for simplification to CONDS_USED.
 737    Returns the simplified expression (or EXPR unchanged, if no
 738    simplification was possible).*/
 739
 740 static tree
 741 simplify_using_initial_conditions (struct loop *loop, tree expr,
 742                                    tree *conds_used)
 743 {
 744   edge e;
 745   basic_block bb;
 746   tree exp, cond;
 747
 748   if (TREE_CODE (expr) == INTEGER_CST)
 749     return expr;
 750
 751   for (bb = loop->header;
 752        bb != ENTRY_BLOCK_PTR;
 753        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 754     {
 755       if (!single_pred_p (bb))
 756         continue;
 757       e = single_pred_edge (bb);
 758
 759       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
 760         continue;
 761
 762       cond = COND_EXPR_COND (last_stmt (e->src));
 763       if (e->flags & EDGE_FALSE_VALUE)
 764         cond = invert_truthvalue (cond);
 765       exp = tree_simplify_using_condition (cond, expr);
 766
 767       if (exp != expr)
 768         *conds_used = fold_build2 (TRUTH_AND_EXPR,
 769                                    boolean_type_node,
 770                                    *conds_used,
 771                                    cond);
 772
 773       expr = exp;
 774     }
 775
 776   return expr;
 777 }
 778
 779 /* Tries to simplify EXPR using the evolutions of the loop invariants
 780    in the superloops of LOOP.  Returns the simplified expression
 781    (or EXPR unchanged, if no simplification was possible).  */
 782
 783 static tree
 784 simplify_using_outer_evolutions (struct loop *loop, tree expr)
 785 {
 786   enum tree_code code = TREE_CODE (expr);
 787   bool changed;
 788   tree e, e0, e1, e2;
 789
 790   if (is_gimple_min_invariant (expr))
 791     return expr;
 792
 793   if (code == TRUTH_OR_EXPR
 794       || code == TRUTH_AND_EXPR
 795       || code == COND_EXPR)
 796     {
 797       changed = false;
 798
 799       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
 800       if (TREE_OPERAND (expr, 0) != e0)
 801         changed = true;
 802
 803       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
 804       if (TREE_OPERAND (expr, 1) != e1)
 805         changed = true;
 806
 807       if (code == COND_EXPR)
 808         {
 809           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
 810           if (TREE_OPERAND (expr, 2) != e2)
 811             changed = true;
 812         }
 813       else
 814         e2 = NULL_TREE;
 815
 816       if (changed)
 817         {
 818           if (code == COND_EXPR)
 819             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
 820           else
 821             expr = fold_build2 (code, boolean_type_node, e0, e1);
 822         }
 823
 824       return expr;
 825     }
 826
 827   e = instantiate_parameters (loop, expr);
 828   if (is_gimple_min_invariant (e))
 829     return e;
 830
 831   return expr;
 832 }
 833
 834 /* Stores description of number of iterations of LOOP derived from
 835    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
 836    useful information could be derived (and fields of NITER has
 837    meaning described in comments at struct tree_niter_desc
 838    declaration), false otherwise.  */
 839
 840 bool
 841 number_of_iterations_exit (struct loop *loop, edge exit,
 842                            struct tree_niter_desc *niter)
 843 {
 844   tree stmt, cond, type;
 845   tree op0, base0, step0;
 846   tree op1, base1, step1;
 847   enum tree_code code;
 848
 849   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
 850     return false;
 851
 852   niter->assumptions = boolean_false_node;
 853   stmt = last_stmt (exit->src);
 854   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
 855     return false;
 856
 857   /* We want the condition for staying inside loop.  */
 858   cond = COND_EXPR_COND (stmt);
 859   if (exit->flags & EDGE_TRUE_VALUE)
 860     cond = invert_truthvalue (cond);
 861
 862   code = TREE_CODE (cond);
 863   switch (code)
 864     {
 865     case GT_EXPR:
 866     case GE_EXPR:
 867     case NE_EXPR:
 868     case LT_EXPR:
 869     case LE_EXPR:
 870       break;
 871
 872     default:
 873       return false;
 874     }
 875
 876   op0 = TREE_OPERAND (cond, 0);
 877   op1 = TREE_OPERAND (cond, 1);
 878   type = TREE_TYPE (op0);
 879
 880   if (TREE_CODE (type) != INTEGER_TYPE
 881       && !POINTER_TYPE_P (type))
 882     return false;
 883
 884   if (!simple_iv (loop, stmt, op0, &base0, &step0))
 885     return false;
 886   if (!simple_iv (loop, stmt, op1, &base1, &step1))
 887     return false;
 888
 889   niter->niter = NULL_TREE;
 890
 891   /* Handle common special cases first, so that we do not need to use
 892      generic (and slow) analysis very often.  */
 893   if (!number_of_iterations_special (type, base0, step0, code, base1, step1,
 894                                      niter))
 895     {
 896
 897       number_of_iterations_cond (type, base0, step0, code, base1, step1,
 898                                  niter);
 899
 900       if (!niter->niter)
 901         return false;
 902     }
 903
 904   if (optimize >= 3)
 905     {
 906       niter->assumptions = simplify_using_outer_evolutions (loop,
 907                                                             niter->assumptions);
 908       niter->may_be_zero = simplify_using_outer_evolutions (loop,
 909                                                             niter->may_be_zero);
 910       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
 911     }
 912
 913   niter->additional_info = boolean_true_node;
 914   niter->assumptions
 915           = simplify_using_initial_conditions (loop,
 916                                                niter->assumptions,
 917                                                &niter->additional_info);
 918   niter->may_be_zero
 919           = simplify_using_initial_conditions (loop,
 920                                                niter->may_be_zero,
 921                                                &niter->additional_info);
 922   return integer_onep (niter->assumptions);
 923 }
 924
 925 /* Try to determine the number of iterations of LOOP.  If we succeed,
 926    expression giving number of iterations is returned and *EXIT is
 927    set to the edge from that the information is obtained.  Otherwise
 928    chrec_dont_know is returned.  */
 929
 930 tree
 931 find_loop_niter (struct loop *loop, edge *exit)
 932 {
 933   unsigned n_exits, i;
 934   edge *exits = get_loop_exit_edges (loop, &n_exits);
 935   edge ex;
 936   tree niter = NULL_TREE, aniter;
 937   struct tree_niter_desc desc;
 938
 939   *exit = NULL;
 940   for (i = 0; i < n_exits; i++)
 941     {
 942       ex = exits[i];
 943       if (!just_once_each_iteration_p (loop, ex->src))
 944         continue;
 945
 946       if (!number_of_iterations_exit (loop, ex, &desc))
 947         continue;
 948
 949       if (nonzero_p (desc.may_be_zero))
 950         {
 951           /* We exit in the first iteration through this exit.
 952              We won't find anything better.  */
 953           niter = build_int_cst_type (unsigned_type_node, 0);
 954           *exit = ex;
 955           break;
 956         }
 957
 958       if (!zero_p (desc.may_be_zero))
 959         continue;
 960
 961       aniter = desc.niter;
 962
 963       if (!niter)
 964         {
 965           /* Nothing recorded yet.  */
 966           niter = aniter;
 967           *exit = ex;
 968           continue;
 969         }
 970
 971       /* Prefer constants, the lower the better.  */
 972       if (TREE_CODE (aniter) != INTEGER_CST)
 973         continue;
 974
 975       if (TREE_CODE (niter) != INTEGER_CST)
 976         {
 977           niter = aniter;
 978           *exit = ex;
 979           continue;
 980         }
 981
 982       if (tree_int_cst_lt (aniter, niter))
 983         {
 984           niter = aniter;
 985           *exit = ex;
 986           continue;
 987         }
 988     }
 989   free (exits);
 990
 991   return niter ? niter : chrec_dont_know;
 992 }
 993
 994 /*
 995
 996    Analysis of a number of iterations of a loop by a brute-force evaluation.
 997
 998 */
 999
1000 /* Bound on the number of iterations we try to evaluate.  */
1001
1002 #define MAX_ITERATIONS_TO_TRACK \
1003   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1004
1005 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1006    result by a chain of operations such that all but exactly one of their
1007    operands are constants.  */
1008
1009 static tree
1010 chain_of_csts_start (struct loop *loop, tree x)
1011 {
1012   tree stmt = SSA_NAME_DEF_STMT (x);
1013   basic_block bb = bb_for_stmt (stmt);
1014   use_optype uses;
1015
1016   if (!bb
1017       || !flow_bb_inside_loop_p (loop, bb))
1018     return NULL_TREE;
1019
1020   if (TREE_CODE (stmt) == PHI_NODE)
1021     {
1022       if (bb == loop->header)
1023         return stmt;
1024
1025       return NULL_TREE;
1026     }
1027
1028   if (TREE_CODE (stmt) != MODIFY_EXPR)
1029     return NULL_TREE;
1030
1031   get_stmt_operands (stmt);
1032   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
1033     return NULL_TREE;
1034   if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
1035     return NULL_TREE;
1036   if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
1037     return NULL_TREE;
1038   if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
1039     return NULL_TREE;
1040   uses = STMT_USE_OPS (stmt);
1041   if (NUM_USES (uses) != 1)
1042     return NULL_TREE;
1043
1044   return chain_of_csts_start (loop, USE_OP (uses, 0));
1045 }
1046
1047 /* Determines whether the expression X is derived from a result of a phi node
1048    in header of LOOP such that
1049
1050    * the derivation of X consists only from operations with constants
1051    * the initial value of the phi node is constant
1052    * the value of the phi node in the next iteration can be derived from the
1053      value in the current iteration by a chain of operations with constants.
1054
1055    If such phi node exists, it is returned.  If X is a constant, X is returned
1056    unchanged.  Otherwise NULL_TREE is returned.  */
1057
1058 static tree
1059 get_base_for (struct loop *loop, tree x)
1060 {
1061   tree phi, init, next;
1062
1063   if (is_gimple_min_invariant (x))
1064     return x;
1065
1066   phi = chain_of_csts_start (loop, x);
1067   if (!phi)
1068     return NULL_TREE;
1069
1070   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1071   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1072
1073   if (TREE_CODE (next) != SSA_NAME)
1074     return NULL_TREE;
1075
1076   if (!is_gimple_min_invariant (init))
1077     return NULL_TREE;
1078
1079   if (chain_of_csts_start (loop, next) != phi)
1080     return NULL_TREE;
1081
1082   return phi;
1083 }
1084
1085 /* Given an expression X, then
1086
1087    * if BASE is NULL_TREE, X must be a constant and we return X.
1088    * otherwise X is a SSA name, whose value in the considered loop is derived
1089      by a chain of operations with constant from a result of a phi node in
1090      the header of the loop.  Then we return value of X when the value of the
1091      result of this phi node is given by the constant BASE.  */
1092
1093 static tree
1094 get_val_for (tree x, tree base)
1095 {
1096   tree stmt, nx, val;
1097   use_optype uses;
1098   use_operand_p op;
1099
1100   if (!x)
1101     return base;
1102
1103   stmt = SSA_NAME_DEF_STMT (x);
1104   if (TREE_CODE (stmt) == PHI_NODE)
1105     return base;
1106
1107   uses = STMT_USE_OPS (stmt);
1108   op = USE_OP_PTR (uses, 0);
1109
1110   nx = USE_FROM_PTR (op);
1111   val = get_val_for (nx, base);
1112   SET_USE (op, val);
1113   val = fold (TREE_OPERAND (stmt, 1));
1114   SET_USE (op, nx);
1115
1116   return val;
1117 }
1118
1119 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1120    by brute force -- i.e. by determining the value of the operands of the
1121    condition at EXIT in first few iterations of the loop (assuming that
1122    these values are constant) and determining the first one in that the
1123    condition is not satisfied.  Returns the constant giving the number
1124    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
1125
1126 tree
1127 loop_niter_by_eval (struct loop *loop, edge exit)
1128 {
1129   tree cond, cnd, acnd;
1130   tree op[2], val[2], next[2], aval[2], phi[2];
1131   unsigned i, j;
1132   enum tree_code cmp;
1133
1134   cond = last_stmt (exit->src);
1135   if (!cond || TREE_CODE (cond) != COND_EXPR)
1136     return chrec_dont_know;
1137
1138   cnd = COND_EXPR_COND (cond);
1139   if (exit->flags & EDGE_TRUE_VALUE)
1140     cnd = invert_truthvalue (cnd);
1141
1142   cmp = TREE_CODE (cnd);
1143   switch (cmp)
1144     {
1145     case EQ_EXPR:
1146     case NE_EXPR:
1147     case GT_EXPR:
1148     case GE_EXPR:
1149     case LT_EXPR:
1150     case LE_EXPR:
1151       for (j = 0; j < 2; j++)
1152         op[j] = TREE_OPERAND (cnd, j);
1153       break;
1154
1155     default:
1156       return chrec_dont_know;
1157     }
1158
1159   for (j = 0; j < 2; j++)
1160     {
1161       phi[j] = get_base_for (loop, op[j]);
1162       if (!phi[j])
1163         return chrec_dont_know;
1164     }
1165
1166   for (j = 0; j < 2; j++)
1167     {
1168       if (TREE_CODE (phi[j]) == PHI_NODE)
1169         {
1170           val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1171           next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1172         }
1173       else
1174         {
1175           val[j] = phi[j];
1176           next[j] = NULL_TREE;
1177           op[j] = NULL_TREE;
1178         }
1179     }
1180
1181   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1182     {
1183       for (j = 0; j < 2; j++)
1184         aval[j] = get_val_for (op[j], val[j]);
1185
1186       acnd = fold_build2 (cmp, boolean_type_node, aval[0], aval[1]);
1187       if (zero_p (acnd))
1188         {
1189           if (dump_file && (dump_flags & TDF_DETAILS))
1190             fprintf (dump_file,
1191                      "Proved that loop %d iterates %d times using brute force.\n",
1192                      loop->num, i);
1193           return build_int_cst (unsigned_type_node, i);
1194         }
1195
1196       for (j = 0; j < 2; j++)
1197         val[j] = get_val_for (next[j], val[j]);
1198     }
1199
1200   return chrec_dont_know;
1201 }
1202
1203 /* Finds the exit of the LOOP by that the loop exits after a constant
1204    number of iterations and stores the exit edge to *EXIT.  The constant
1205    giving the number of iterations of LOOP is returned.  The number of
1206    iterations is determined using loop_niter_by_eval (i.e. by brute force
1207    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1208    determines the number of iterations, chrec_dont_know is returned.  */
1209
1210 tree
1211 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1212 {
1213   unsigned n_exits, i;
1214   edge *exits = get_loop_exit_edges (loop, &n_exits);
1215   edge ex;
1216   tree niter = NULL_TREE, aniter;
1217
1218   *exit = NULL;
1219   for (i = 0; i < n_exits; i++)
1220     {
1221       ex = exits[i];
1222       if (!just_once_each_iteration_p (loop, ex->src))
1223         continue;
1224
1225       aniter = loop_niter_by_eval (loop, ex);
1226       if (chrec_contains_undetermined (aniter))
1227         continue;
1228
1229       if (niter
1230           && !tree_int_cst_lt (aniter, niter))
1231         continue;
1232
1233       niter = aniter;
1234       *exit = ex;
1235     }
1236   free (exits);
1237
1238   return niter ? niter : chrec_dont_know;
1239 }
1240
1241 /*
1242
1243    Analysis of upper bounds on number of iterations of a loop.
1244
1245 */
1246
1247 /* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1248    additional condition ADDITIONAL is recorded with the bound.  */
1249
1250 void
1251 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1252 {
1253   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1254
1255   if (dump_file && (dump_flags & TDF_DETAILS))
1256     {
1257       fprintf (dump_file, "Statements after ");
1258       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1259       fprintf (dump_file, " are executed at most ");
1260       print_generic_expr (dump_file, bound, TDF_SLIM);
1261       fprintf (dump_file, " times in loop %d.\n", loop->num);
1262     }
1263
1264   elt->bound = bound;
1265   elt->at_stmt = at_stmt;
1266   elt->additional = additional;
1267   elt->next = loop->bounds;
1268   loop->bounds = elt;
1269 }
1270
1271 /* Records estimates on numbers of iterations of LOOP.  */
1272
1273 static void
1274 estimate_numbers_of_iterations_loop (struct loop *loop)
1275 {
1276   edge *exits;
1277   tree niter, type;
1278   unsigned i, n_exits;
1279   struct tree_niter_desc niter_desc;
1280
1281   exits = get_loop_exit_edges (loop, &n_exits);
1282   for (i = 0; i < n_exits; i++)
1283     {
1284       if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
1285         continue;
1286
1287       niter = niter_desc.niter;
1288       type = TREE_TYPE (niter);
1289       if (!zero_p (niter_desc.may_be_zero)
1290           && !nonzero_p (niter_desc.may_be_zero))
1291         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1292                         build_int_cst_type (type, 0),
1293                         niter);
1294       record_estimate (loop, niter,
1295                        niter_desc.additional_info,
1296                        last_stmt (exits[i]->src));
1297     }
1298   free (exits);
1299
1300   /* Analyzes the bounds of arrays accessed in the loop.  */
1301   if (loop->estimated_nb_iterations == NULL_TREE)
1302     {
1303       varray_type datarefs;
1304       VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
1305       find_data_references_in_loop (loop, &datarefs);
1306       free_data_refs (datarefs);
1307     }
1308 }
1309
1310 /* Records estimates on numbers of iterations of LOOPS.  */
1311
1312 void
1313 estimate_numbers_of_iterations (struct loops *loops)
1314 {
1315   unsigned i;
1316   struct loop *loop;
1317
1318   for (i = 1; i < loops->num; i++)
1319     {
1320       loop = loops->parray[i];
1321       if (loop)
1322         estimate_numbers_of_iterations_loop (loop);
1323     }
1324 }
1325
1326 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1327    If neither of these relations can be proved, returns 2.  */
1328
1329 static int
1330 compare_trees (tree a, tree b)
1331 {
1332   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1333   tree type;
1334
1335   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1336     type = typea;
1337   else
1338     type = typeb;
1339
1340   a = fold_convert (type, a);
1341   b = fold_convert (type, b);
1342
1343   if (nonzero_p (fold_build2 (EQ_EXPR, boolean_type_node, a, b)))
1344     return 0;
1345   if (nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, a, b)))
1346     return 1;
1347   if (nonzero_p (fold_build2 (GT_EXPR, boolean_type_node, a, b)))
1348     return -1;
1349
1350   return 2;
1351 }
1352
1353 /* Returns true if statement S1 dominates statement S2.  */
1354
1355 static bool
1356 stmt_dominates_stmt_p (tree s1, tree s2)
1357 {
1358   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1359
1360   if (!bb1
1361       || s1 == s2)
1362     return true;
1363
1364   if (bb1 == bb2)
1365     {
1366       block_stmt_iterator bsi;
1367
1368       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1369         if (bsi_stmt (bsi) == s1)
1370           return true;
1371
1372       return false;
1373     }
1374
1375   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1376 }
1377
1378 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1379    at AT_STMT in wider TYPE, using the fact that statement OF is executed at
1380    most BOUND times in the loop.  If it is possible, return the value of step
1381    of the induction variable in the TYPE, otherwise return NULL_TREE.
1382
1383    ADDITIONAL is the additional condition recorded for operands of the bound.
1384    This is useful in the following case, created by loop header copying:
1385
1386    i = 0;
1387    if (n > 0)
1388      do
1389        {
1390          something;
1391        } while (++i < n)
1392
1393    If the n > 0 condition is taken into account, the number of iterations of the
1394    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1395    assumption "n > 0" says us that the value of the number of iterations is at
1396    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1397
1398 static tree
1399 can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
1400                                   tree at_stmt,
1401                                   tree bound,
1402                                   tree additional,
1403                                   tree of)
1404 {
1405   tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
1406   tree valid_niter, extreme, unsigned_type, delta, bound_type;
1407   tree cond;
1408
1409   b = fold_convert (type, base);
1410   bplusstep = fold_convert (type,
1411                             fold_build2 (PLUS_EXPR, inner_type, base, step));
1412   new_step = fold_build2 (MINUS_EXPR, type, bplusstep, b);
1413   if (TREE_CODE (new_step) != INTEGER_CST)
1414     return NULL_TREE;
1415
1416   switch (compare_trees (bplusstep, b))
1417     {
1418     case -1:
1419       extreme = upper_bound_in_type (type, inner_type);
1420       delta = fold_build2 (MINUS_EXPR, type, extreme, b);
1421       new_step_abs = new_step;
1422       break;
1423
1424     case 1:
1425       extreme = lower_bound_in_type (type, inner_type);
1426       new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step);
1427       delta = fold_build2 (MINUS_EXPR, type, b, extreme);
1428       break;
1429
1430     case 0:
1431       return new_step;
1432
1433     default:
1434       return NULL_TREE;
1435     }
1436
1437   unsigned_type = unsigned_type_for (type);
1438   delta = fold_convert (unsigned_type, delta);
1439   new_step_abs = fold_convert (unsigned_type, new_step_abs);
1440   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1441                              delta, new_step_abs);
1442
1443   bound_type = TREE_TYPE (bound);
1444   if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
1445     bound = fold_convert (unsigned_type, bound);
1446   else
1447     valid_niter = fold_convert (bound_type, valid_niter);
1448
1449   if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
1450     {
1451       /* After the statement OF we know that anything is executed at most
1452          BOUND times.  */
1453       cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
1454     }
1455   else
1456     {
1457       /* Before the statement OF we know that anything is executed at most
1458          BOUND + 1 times.  */
1459       cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
1460     }
1461
1462   if (nonzero_p (cond))
1463     return new_step;
1464
1465   /* Try taking additional conditions into account.  */
1466   cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1467                       invert_truthvalue (additional),
1468                       cond);
1469   if (nonzero_p (cond))
1470     return new_step;
1471
1472   return NULL_TREE;
1473 }
1474
1475 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1476    at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
1477    LOOP.  If it is possible, return the value of step of the induction variable
1478    in the TYPE, otherwise return NULL_TREE.  */
1479
1480 tree
1481 can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
1482                             tree at_stmt)
1483 {
1484   struct nb_iter_bound *bound;
1485   tree new_step;
1486
1487   for (bound = loop->bounds; bound; bound = bound->next)
1488     {
1489       new_step = can_count_iv_in_wider_type_bound (type, base, step,
1490                                                    at_stmt,
1491                                                    bound->bound,
1492                                                    bound->additional,
1493                                                    bound->at_stmt);
1494
1495       if (new_step)
1496         return new_step;
1497     }
1498
1499   return NULL_TREE;
1500 }
1501
1502 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
1503
1504 static void
1505 free_numbers_of_iterations_estimates_loop (struct loop *loop)
1506 {
1507   struct nb_iter_bound *bound, *next;
1508
1509   for (bound = loop->bounds; bound; bound = next)
1510     {
1511       next = bound->next;
1512       free (bound);
1513     }
1514
1515   loop->bounds = NULL;
1516 }
1517
1518 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
1519
1520 void
1521 free_numbers_of_iterations_estimates (struct loops *loops)
1522 {
1523   unsigned i;
1524   struct loop *loop;
1525
1526   for (i = 1; i < loops->num; i++)
1527     {
1528       loop = loops->parray[i];
1529       if (loop)
1530         free_numbers_of_iterations_estimates_loop (loop);
1531     }
1532 }