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