gcc/tree-ssa-loop-niter.c

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