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