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