gcc/doloop.c

   1 /* Perform doloop optimizations
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
   3    Free Software Foundation, Inc.
   4    Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "rtl.h"
  28 #include "flags.h"
  29 #include "expr.h"
  30 #include "loop.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "toplev.h"
  34 #include "tm_p.h"
  35 #include "cfgloop.h"
  36
  37
  38 /* This module is used to modify loops with a determinable number of
  39    iterations to use special low-overhead looping instructions.
  40
  41    It first validates whether the loop is well behaved and has a
  42    determinable number of iterations (either at compile or run-time).
  43    It then modifies the loop to use a low-overhead looping pattern as
  44    follows:
  45
  46    1. A pseudo register is allocated as the loop iteration counter.
  47
  48    2. The number of loop iterations is calculated and is stored
  49       in the loop counter.
  50
  51    3. At the end of the loop, the jump insn is replaced by the
  52       doloop_end pattern.  The compare must remain because it might be
  53       used elsewhere.  If the loop-variable or condition register are
  54       used elsewhere, they will be eliminated by flow.
  55
  56    4. An optional doloop_begin pattern is inserted at the top of the
  57       loop.
  58 */
  59
  60
  61 #ifdef HAVE_doloop_end
  62
  63 static rtx doloop_condition_get (rtx);
  64 static unsigned HOST_WIDE_INT doloop_iterations_max (const struct loop_info *,
  65                                                      enum machine_mode, int);
  66 static int doloop_valid_p (const struct loop *, rtx);
  67 static int doloop_modify (const struct loop *, rtx, rtx, rtx, rtx, rtx);
  68 static int doloop_modify_runtime (const struct loop *, rtx, rtx, rtx,
  69                                   enum machine_mode, rtx);
  70
  71
  72 /* Return the loop termination condition for PATTERN or zero
  73    if it is not a decrement and branch jump insn.  */
  74 static rtx
  75 doloop_condition_get (rtx pattern)
  76 {
  77   rtx cmp;
  78   rtx inc;
  79   rtx reg;
  80   rtx condition;
  81
  82   /* The canonical doloop pattern we expect is:
  83
  84      (parallel [(set (pc) (if_then_else (condition)
  85                                         (label_ref (label))
  86                                         (pc)))
  87                 (set (reg) (plus (reg) (const_int -1)))
  88                 (additional clobbers and uses)])
  89
  90      Some machines (IA-64) make the decrement conditional on
  91      the condition as well, so we don't bother verifying the
  92      actual decrement.  In summary, the branch must be the
  93      first entry of the parallel (also required by jump.c),
  94      and the second entry of the parallel must be a set of
  95      the loop counter register.  */
  96
  97   if (GET_CODE (pattern) != PARALLEL)
  98     return 0;
  99
 100   cmp = XVECEXP (pattern, 0, 0);
 101   inc = XVECEXP (pattern, 0, 1);
 102
 103   /* Check for (set (reg) (something)).  */
 104   if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
 105     return 0;
 106
 107   /* Extract loop counter register.  */
 108   reg = SET_DEST (inc);
 109
 110   /* Check for (set (pc) (if_then_else (condition)
 111                                        (label_ref (label))
 112                                        (pc))).  */
 113   if (GET_CODE (cmp) != SET
 114       || SET_DEST (cmp) != pc_rtx
 115       || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
 116       || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
 117       || XEXP (SET_SRC (cmp), 2) != pc_rtx)
 118     return 0;
 119
 120   /* Extract loop termination condition.  */
 121   condition = XEXP (SET_SRC (cmp), 0);
 122
 123   if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
 124       || GET_CODE (XEXP (condition, 1)) != CONST_INT)
 125     return 0;
 126
 127   if (XEXP (condition, 0) == reg)
 128     return condition;
 129
 130   if (GET_CODE (XEXP (condition, 0)) == PLUS
 131       && XEXP (XEXP (condition, 0), 0) == reg)
 132     return condition;
 133
 134   /* ??? If a machine uses a funny comparison, we could return a
 135      canonicalised form here.  */
 136
 137   return 0;
 138 }
 139
 140
 141 /* Return an estimate of the maximum number of loop iterations for the
 142    loop specified by LOOP or zero if the loop is not normal.
 143    MODE is the mode of the iteration count and NONNEG is nonzero if
 144    the iteration count has been proved to be non-negative.  */
 145 static unsigned HOST_WIDE_INT
 146 doloop_iterations_max (const struct loop_info *loop_info,
 147                        enum machine_mode mode, int nonneg)
 148 {
 149   unsigned HOST_WIDE_INT n_iterations_max;
 150   enum rtx_code code;
 151   rtx min_value;
 152   rtx max_value;
 153   HOST_WIDE_INT abs_inc;
 154   int neg_inc;
 155
 156   neg_inc = 0;
 157   abs_inc = INTVAL (loop_info->increment);
 158   if (abs_inc < 0)
 159     {
 160       abs_inc = -abs_inc;
 161       neg_inc = 1;
 162     }
 163
 164   if (neg_inc)
 165     {
 166       code = swap_condition (loop_info->comparison_code);
 167       min_value = loop_info->final_equiv_value;
 168       max_value = loop_info->initial_equiv_value;
 169     }
 170   else
 171     {
 172       code = loop_info->comparison_code;
 173       min_value = loop_info->initial_equiv_value;
 174       max_value = loop_info->final_equiv_value;
 175     }
 176
 177   /* Since the loop has a VTOP, we know that the initial test will be
 178      true and thus the value of max_value should be greater than the
 179      value of min_value.  Thus the difference should always be positive
 180      and the code must be LT, LE, LTU, LEU, or NE.  Otherwise the loop is
 181      not normal, e.g., `for (i = 0; i < 10; i--)'.  */
 182   switch (code)
 183     {
 184     case LTU:
 185     case LEU:
 186       {
 187         unsigned HOST_WIDE_INT umax;
 188         unsigned HOST_WIDE_INT umin;
 189
 190         if (GET_CODE (min_value) == CONST_INT)
 191           umin = INTVAL (min_value);
 192         else
 193           umin = 0;
 194
 195         if (GET_CODE (max_value) == CONST_INT)
 196           umax = INTVAL (max_value);
 197         else
 198           umax = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 199
 200         n_iterations_max = umax - umin;
 201         break;
 202       }
 203
 204     case LT:
 205     case LE:
 206       {
 207         HOST_WIDE_INT smax;
 208         HOST_WIDE_INT smin;
 209
 210         if (GET_CODE (min_value) == CONST_INT)
 211           smin = INTVAL (min_value);
 212         else
 213           smin = -((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1));
 214
 215         if (GET_CODE (max_value) == CONST_INT)
 216           smax = INTVAL (max_value);
 217         else
 218           smax = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 219
 220         n_iterations_max = smax - smin;
 221         break;
 222       }
 223
 224     case NE:
 225       if (GET_CODE (min_value) == CONST_INT
 226           && GET_CODE (max_value) == CONST_INT)
 227         n_iterations_max = INTVAL (max_value) - INTVAL (min_value);
 228       else
 229         /* We need to conservatively assume that we might have the maximum
 230            number of iterations without any additional knowledge.  */
 231         n_iterations_max = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 232       break;
 233
 234     default:
 235       return 0;
 236     }
 237
 238   n_iterations_max /= abs_inc;
 239
 240   /* If we know that the iteration count is non-negative then adjust
 241      n_iterations_max if it is so large that it appears negative.  */
 242   if (nonneg
 243       && n_iterations_max > ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)))
 244     n_iterations_max = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 245
 246   return n_iterations_max;
 247 }
 248
 249
 250 /* Return nonzero if the loop specified by LOOP is suitable for
 251    the use of special low-overhead looping instructions.  */
 252 static int
 253 doloop_valid_p (const struct loop *loop, rtx jump_insn)
 254 {
 255   const struct loop_info *loop_info = LOOP_INFO (loop);
 256
 257   /* The loop must have a conditional jump at the end.  */
 258   if (! any_condjump_p (jump_insn)
 259       || ! onlyjump_p (jump_insn))
 260     {
 261       if (loop_dump_stream)
 262         fprintf (loop_dump_stream,
 263                  "Doloop: Invalid jump at loop end.\n");
 264       return 0;
 265     }
 266
 267   /* Give up if a loop has been completely unrolled.  */
 268   if (loop_info->n_iterations == loop_info->unroll_number)
 269     {
 270       if (loop_dump_stream)
 271         fprintf (loop_dump_stream,
 272                  "Doloop: Loop completely unrolled.\n");
 273       return 0;
 274     }
 275
 276   /* The loop must have a single exit target.  A break or return
 277      statement within a loop will generate multiple loop exits.
 278      Another example of a loop that currently generates multiple exit
 279      targets is for (i = 0; i < (foo ? 8 : 4); i++) { }.  */
 280   if (loop_info->has_multiple_exit_targets || loop->exit_count)
 281     {
 282       if (loop_dump_stream)
 283         fprintf (loop_dump_stream,
 284                  "Doloop: Loop has multiple exit targets.\n");
 285       return 0;
 286     }
 287
 288   /* An indirect jump may jump out of the loop.  */
 289   if (loop_info->has_indirect_jump)
 290     {
 291       if (loop_dump_stream)
 292         fprintf (loop_dump_stream,
 293                  "Doloop: Indirect jump in function.\n");
 294       return 0;
 295     }
 296
 297   /* A called function may clobber any special registers required for
 298      low-overhead looping.  */
 299   if (loop_info->has_call)
 300     {
 301       if (loop_dump_stream)
 302         fprintf (loop_dump_stream,
 303                  "Doloop: Function call in loop.\n");
 304       return 0;
 305     }
 306
 307   /* Some targets (eg, PPC) use the count register for branch on table
 308      instructions.  ??? This should be a target specific check.  */
 309   if (loop_info->has_tablejump)
 310     {
 311       if (loop_dump_stream)
 312         fprintf (loop_dump_stream,
 313                  "Doloop: Computed branch in the loop.\n");
 314       return 0;
 315     }
 316
 317   if (! loop_info->increment)
 318     {
 319       if (loop_dump_stream)
 320         fprintf (loop_dump_stream,
 321                  "Doloop: Could not determine iteration info.\n");
 322       return 0;
 323     }
 324
 325   if (GET_CODE (loop_info->increment) != CONST_INT)
 326     {
 327       if (loop_dump_stream)
 328         fprintf (loop_dump_stream,
 329                  "Doloop: Increment not an integer constant.\n");
 330       return 0;
 331     }
 332
 333   /* There is no guarantee that a NE loop will terminate if the
 334      absolute increment is not unity.  ??? We could compute this
 335      condition at run-time and have an additional jump around the loop
 336      to ensure an infinite loop.  */
 337   if (loop_info->comparison_code == NE
 338       && !loop_info->preconditioned
 339       && INTVAL (loop_info->increment) != -1
 340       && INTVAL (loop_info->increment) != 1)
 341     {
 342       if (loop_dump_stream)
 343         fprintf (loop_dump_stream,
 344                  "Doloop: NE loop with non-unity increment.\n");
 345       return 0;
 346     }
 347
 348   /* Check for loops that may not terminate under special conditions.  */
 349   if (! loop_info->n_iterations
 350       && ((loop_info->comparison_code == LEU
 351            && INTVAL (loop_info->increment) > 0)
 352           || (loop_info->comparison_code == GEU
 353               && INTVAL (loop_info->increment) < 0)
 354           || (loop_info->comparison_code == LTU
 355               && INTVAL (loop_info->increment) > 1)
 356           || (loop_info->comparison_code == GTU
 357               && INTVAL (loop_info->increment) < -1)))
 358     {
 359       /* If the comparison is LEU and the comparison value is UINT_MAX
 360          then the loop will not terminate.  Similarly, if the
 361          comparison code is GEU and the comparison value is 0, the
 362          loop will not terminate.
 363
 364          If the absolute increment is not 1, the loop can be infinite
 365          even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
 366
 367          Note that with LE and GE, the loop behavior is undefined
 368          (C++ standard section 5 clause 5) if an overflow occurs, say
 369          between INT_MAX and INT_MAX + 1.  We thus don't have to worry
 370          about these two cases.
 371
 372          ??? We could compute these conditions at run-time and have a
 373          additional jump around the loop to ensure an infinite loop.
 374          However, it is very unlikely that this is the intended
 375          behavior of the loop and checking for these rare boundary
 376          conditions would pessimize all other code.
 377
 378          If the loop is executed only a few times an extra check to
 379          restart the loop could use up most of the benefits of using a
 380          count register loop.  Note however, that normally, this
 381          restart branch would never execute, so it could be predicted
 382          well by the CPU.  We should generate the pessimistic code by
 383          default, and have an option, e.g. -funsafe-loops that would
 384          enable count-register loops in this case.  */
 385       if (loop_dump_stream)
 386         fprintf (loop_dump_stream,
 387                  "Doloop: Possible infinite iteration case ignored.\n");
 388     }
 389
 390   return 1;
 391 }
 392
 393
 394 /* Modify the loop to use the low-overhead looping insn where LOOP
 395    describes the loop, ITERATIONS is an RTX containing the desired
 396    number of loop iterations, ITERATIONS_MAX is a CONST_INT specifying
 397    the maximum number of loop iterations, and DOLOOP_INSN is the
 398    low-overhead looping insn to emit at the end of the loop.  This
 399    returns nonzero if it was successful.  */
 400 static int
 401 doloop_modify (const struct loop *loop, rtx iterations, rtx iterations_max,
 402                rtx doloop_seq, rtx start_label, rtx condition)
 403 {
 404   rtx counter_reg;
 405   rtx count;
 406   rtx sequence;
 407   rtx jump_insn;
 408   int nonneg = 0;
 409   int decrement_count;
 410
 411   jump_insn = prev_nonnote_insn (loop->end);
 412
 413   if (loop_dump_stream)
 414     {
 415       fprintf (loop_dump_stream, "Doloop: Inserting doloop pattern (");
 416       if (GET_CODE (iterations) == CONST_INT)
 417         fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
 418                  INTVAL (iterations));
 419       else
 420         fputs ("runtime", loop_dump_stream);
 421       fputs (" iterations).", loop_dump_stream);
 422     }
 423
 424   /* Emit the label that will delimit the top of the loop.
 425      This has to be done before the delete_insn call below, to prevent
 426      delete_insn from deleting too much.  */
 427   emit_label_after (start_label, loop->top ? loop->top : loop->start);
 428   LABEL_NUSES (start_label)++;
 429
 430   /* Discard original jump to continue loop.  The original compare
 431      result may still be live, so it cannot be discarded explicitly.  */
 432   delete_related_insns (jump_insn);
 433
 434   counter_reg = XEXP (condition, 0);
 435   if (GET_CODE (counter_reg) == PLUS)
 436     counter_reg = XEXP (counter_reg, 0);
 437
 438   start_sequence ();
 439
 440   count = iterations;
 441   decrement_count = 0;
 442   switch (GET_CODE (condition))
 443     {
 444     case NE:
 445       /* Currently only NE tests against zero and one are supported.  */
 446       if (XEXP (condition, 1) == const0_rtx)
 447         decrement_count = 1;
 448       else if (XEXP (condition, 1) != const1_rtx)
 449         abort ();
 450       break;
 451
 452     case GE:
 453       /* Currently only GE tests against zero are supported.  */
 454       if (XEXP (condition, 1) != const0_rtx)
 455         abort ();
 456
 457       /* The iteration count needs decrementing for a GE test.  */
 458       decrement_count = 1;
 459
 460       /* Determine if the iteration counter will be non-negative.
 461          Note that the maximum value loaded is iterations_max - 1.  */
 462       if ((unsigned HOST_WIDE_INT) INTVAL (iterations_max)
 463           <= ((unsigned) 1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1)))
 464         nonneg = 1;
 465       break;
 466
 467       /* Abort if an invalid doloop pattern has been generated.  */
 468     default:
 469       abort ();
 470     }
 471
 472   if (decrement_count)
 473     {
 474       if (GET_CODE (count) == CONST_INT)
 475         count = GEN_INT (INTVAL (count) - 1);
 476       else
 477         count = expand_simple_binop (GET_MODE (counter_reg), MINUS,
 478                                      count, const1_rtx,
 479                                      0, 0, OPTAB_LIB_WIDEN);
 480     }
 481
 482   /* Insert initialization of the count register into the loop header.  */
 483   convert_move (counter_reg, count, 1);
 484   sequence = get_insns ();
 485   end_sequence ();
 486   emit_insn_before (sequence, loop->start);
 487
 488   /* Some targets (eg, C4x) need to initialize special looping
 489      registers.  */
 490 #ifdef HAVE_doloop_begin
 491   {
 492     rtx init;
 493
 494     init = gen_doloop_begin (counter_reg,
 495                              GET_CODE (iterations) == CONST_INT
 496                              ? iterations : const0_rtx, iterations_max,
 497                              GEN_INT (loop->level));
 498     if (init)
 499       {
 500         start_sequence ();
 501         emit_insn (init);
 502         sequence = get_insns ();
 503         end_sequence ();
 504         emit_insn_after (sequence, loop->start);
 505       }
 506   }
 507 #endif
 508
 509   /* Insert the new low-overhead looping insn.  */
 510   emit_jump_insn_before (doloop_seq, loop->end);
 511   jump_insn = prev_nonnote_insn (loop->end);
 512   JUMP_LABEL (jump_insn) = start_label;
 513
 514   /* Add a REG_NONNEG note if the actual or estimated maximum number
 515      of iterations is non-negative.  */
 516   if (nonneg)
 517     {
 518       REG_NOTES (jump_insn)
 519         = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
 520     }
 521   return 1;
 522 }
 523
 524
 525 /* Handle the more complex case, where the bounds are not known at
 526    compile time.  In this case we generate a run_time calculation of
 527    the number of iterations.  We rely on the existence of a run-time
 528    guard to ensure that the loop executes at least once, i.e.,
 529    initial_value obeys the loop comparison condition.  If a guard is
 530    not present, we emit one.  The loop to modify is described by LOOP.
 531    ITERATIONS_MAX is a CONST_INT specifying the estimated maximum
 532    number of loop iterations.  DOLOOP_INSN is the low-overhead looping
 533    insn to insert.  Returns nonzero if loop successfully modified.  */
 534 static int
 535 doloop_modify_runtime (const struct loop *loop, rtx iterations_max,
 536                        rtx doloop_seq, rtx start_label,
 537                        enum machine_mode mode, rtx condition)
 538 {
 539   const struct loop_info *loop_info = LOOP_INFO (loop);
 540   HOST_WIDE_INT abs_inc;
 541   HOST_WIDE_INT abs_loop_inc;
 542   int neg_inc;
 543   rtx diff;
 544   rtx sequence;
 545   rtx iterations;
 546   rtx initial_value;
 547   rtx final_value;
 548   rtx increment;
 549   int unsigned_p;
 550   enum rtx_code comparison_code;
 551
 552   increment = loop_info->increment;
 553   initial_value = loop_info->initial_value;
 554   final_value = loop_info->final_value;
 555
 556   neg_inc = 0;
 557   abs_inc = INTVAL (increment);
 558   if (abs_inc < 0)
 559     {
 560       abs_inc = -abs_inc;
 561       neg_inc = 1;
 562     }
 563
 564   comparison_code = loop_info->comparison_code;
 565   unsigned_p = (comparison_code == LTU
 566                 || comparison_code == LEU
 567                 || comparison_code == GTU
 568                 || comparison_code == GEU
 569                 || comparison_code == NE);
 570
 571   /* The number of iterations (prior to any loop unrolling) is given by:
 572
 573        n = (abs (final - initial) + abs_inc - 1) / abs_inc.
 574
 575      However, it is possible for the summation to overflow, and a
 576      safer method is:
 577
 578        n = abs (final - initial) / abs_inc;
 579        n += (abs (final - initial) % abs_inc) != 0;
 580
 581      But when abs_inc is a power of two, the summation won't overflow
 582      except in cases where the loop never terminates.  So we don't
 583      need to use this more costly calculation.
 584
 585      If the loop has been unrolled, the full calculation is
 586
 587        t1 = abs_inc * unroll_number;                    increment per loop
 588        n = (abs (final - initial) + abs_inc - 1) / t1;    full loops
 589        n += (abs (final - initial) + abs_inc - 1) % t1) >= abs_inc;
 590                                                           partial loop
 591      which works out to be equivalent to
 592
 593        n = (abs (final - initial) + t1 - 1) / t1;
 594
 595      In the case where the loop was preconditioned, a few iterations
 596      may have been executed earlier; but 'initial' was adjusted as they
 597      were executed, so we don't need anything special for that case here.
 598      As above, when t1 is a power of two we don't need to worry about
 599      overflow.
 600
 601      The division and modulo operations can be avoided by requiring
 602      that the increment is a power of 2 (precondition_loop_p enforces
 603      this requirement).  Nevertheless, the RTX_COSTS should be checked
 604      to see if a fast divmod is available.  */
 605
 606   start_sequence ();
 607   /* abs (final - initial)  */
 608   diff = expand_simple_binop (mode, MINUS,
 609                               copy_rtx (neg_inc ? initial_value : final_value),
 610                               copy_rtx (neg_inc ? final_value : initial_value),
 611                               NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 612
 613   /* Some code transformations can result in code akin to
 614
 615           tmp = i + 1;
 616           ...
 617           goto scan_start;
 618         top:
 619           tmp = tmp + 1;
 620         scan_start:
 621           i = tmp;
 622           if (i < n) goto top;
 623
 624      We'll have already detected this form of loop in scan_loop,
 625      and set loop->top and loop->scan_start appropriately.
 626
 627      In this situation, we skip the increment the first time through
 628      the loop, which results in an incorrect estimate of the number
 629      of iterations.  Adjust the difference to compensate.  */
 630   /* ??? Logically, it would seem this belongs in loop_iterations.
 631      However, this causes regressions e.g. on x86 execute/20011008-3.c,
 632      so I do not believe we've properly characterized the exact nature
 633      of the problem.  In the meantime, this fixes execute/20011126-2.c
 634      on ia64 and some Ada front end miscompilation on ppc.  */
 635
 636   if (loop->scan_start)
 637     {
 638       rtx iteration_var = loop_info->iteration_var;
 639       struct loop_ivs *ivs = LOOP_IVS (loop);
 640       struct iv_class *bl;
 641
 642       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
 643         bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
 644       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
 645         {
 646           struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
 647           bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
 648         }
 649       else
 650         /* Iteration var must be an induction variable to get here.  */
 651         abort ();
 652
 653       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
 654           && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
 655         {
 656           if (loop_dump_stream)
 657             fprintf (loop_dump_stream,
 658                  "Doloop: Basic induction var skips initial incr.\n");
 659
 660           diff = expand_simple_binop (mode, PLUS, diff, GEN_INT (abs_inc),
 661                                       diff, unsigned_p, OPTAB_LIB_WIDEN);
 662         }
 663     }
 664
 665   abs_loop_inc = abs_inc * loop_info->unroll_number;
 666   if (abs_loop_inc != 1)
 667     {
 668       int shift_count;
 669
 670       shift_count = exact_log2 (abs_loop_inc);
 671       if (shift_count < 0)
 672         abort ();
 673
 674       /* (abs (final - initial) + abs_inc * unroll_number - 1) */
 675       diff = expand_simple_binop (GET_MODE (diff), PLUS,
 676                                   diff, GEN_INT (abs_loop_inc - 1),
 677                                   diff, 1, OPTAB_LIB_WIDEN);
 678
 679       /* (abs (final - initial) + abs_inc * unroll_number - 1)
 680          / (abs_inc * unroll_number)  */
 681       diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
 682                                   diff, GEN_INT (shift_count),
 683                                   diff, 1, OPTAB_LIB_WIDEN);
 684     }
 685   iterations = diff;
 686
 687   /* If there is a NOTE_INSN_LOOP_VTOP, we have a `for' or `while'
 688      style loop, with a loop exit test at the start.  Thus, we can
 689      assume that the loop condition was true when the loop was
 690      entered.
 691
 692      `do-while' loops require special treatment since the exit test is
 693      not executed before the start of the loop.  We need to determine
 694      if the loop will terminate after the first pass and to limit the
 695      iteration count to one if necessary.  */
 696   if (! loop->vtop)
 697     {
 698       if (loop_dump_stream)
 699         fprintf (loop_dump_stream, "Doloop: Do-while loop.\n");
 700
 701       /* A `do-while' loop must iterate at least once.  For code like
 702          i = initial; do { ... } while (++i < final);
 703          we will calculate a bogus iteration count if initial > final.
 704          So detect this and set the iteration count to 1.
 705          Note that if the loop has been unrolled, then the loop body
 706          is guaranteed to execute at least once.  Also, when the
 707          comparison is NE, our calculated count will be OK.  */
 708       if (loop_info->unroll_number == 1 && comparison_code != NE)
 709         {
 710           rtx label;
 711
 712           /*  Emit insns to test if the loop will immediately
 713               terminate and to set the iteration count to 1 if true.  */
 714           label = gen_label_rtx();
 715           emit_cmp_and_jump_insns (copy_rtx (initial_value),
 716                                    copy_rtx (loop_info->comparison_value),
 717                                    comparison_code, NULL_RTX, mode, 0,
 718                                    label);
 719           JUMP_LABEL (get_last_insn ()) = label;
 720           LABEL_NUSES (label)++;
 721           emit_move_insn (iterations, const1_rtx);
 722           emit_label (label);
 723         }
 724     }
 725
 726   sequence = get_insns ();
 727   end_sequence ();
 728   emit_insn_before (sequence, loop->start);
 729
 730   return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 731                         start_label, condition);
 732 }
 733
 734
 735 /* This is the main entry point.  Process loop described by LOOP
 736    validating that the loop is suitable for conversion to use a low
 737    overhead looping instruction, replacing the jump insn where
 738    suitable.  We distinguish between loops with compile-time bounds
 739    and those with run-time bounds.  Information from LOOP is used to
 740    compute the number of iterations and to determine whether the loop
 741    is a candidate for this optimization.  Returns nonzero if loop
 742    successfully modified.  */
 743 int
 744 doloop_optimize (const struct loop *loop)
 745 {
 746   struct loop_info *loop_info = LOOP_INFO (loop);
 747   rtx initial_value;
 748   rtx final_value;
 749   rtx increment;
 750   rtx jump_insn;
 751   enum machine_mode mode;
 752   unsigned HOST_WIDE_INT n_iterations;
 753   unsigned HOST_WIDE_INT n_iterations_max;
 754   rtx doloop_seq, doloop_pat, doloop_reg;
 755   rtx iterations;
 756   rtx iterations_max;
 757   rtx start_label;
 758   rtx condition;
 759
 760   if (loop_dump_stream)
 761     fprintf (loop_dump_stream,
 762              "Doloop: Processing loop %d, enclosed levels %d.\n",
 763              loop->num, loop->level);
 764
 765   jump_insn = prev_nonnote_insn (loop->end);
 766
 767   /* Check that loop is a candidate for a low-overhead looping insn.  */
 768   if (! doloop_valid_p (loop, jump_insn))
 769     return 0;
 770
 771   /* Determine if the loop can be safely, and profitably,
 772      preconditioned.  While we don't precondition the loop in a loop
 773      unrolling sense, this test ensures that the loop is well behaved
 774      and that the increment is a constant integer.  */
 775   if (! precondition_loop_p (loop, &initial_value, &final_value,
 776                              &increment, &mode))
 777     {
 778       if (loop_dump_stream)
 779         fprintf (loop_dump_stream,
 780                  "Doloop: Cannot precondition loop.\n");
 781       return 0;
 782     }
 783
 784   /* Determine or estimate the maximum number of loop iterations.  */
 785   n_iterations = loop_info->n_iterations;
 786   if (n_iterations)
 787     {
 788       /* This is the simple case where the initial and final loop
 789          values are constants.  */
 790       n_iterations_max = n_iterations;
 791     }
 792   else
 793     {
 794       int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0;
 795
 796       /* This is the harder case where the initial and final loop
 797          values may not be constants.  */
 798       n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg);
 799
 800       if (! n_iterations_max)
 801         {
 802           /* We have something like `for (i = 0; i < 10; i--)'.  */
 803           if (loop_dump_stream)
 804             fprintf (loop_dump_stream,
 805                      "Doloop: Not normal loop.\n");
 806           return 0;
 807         }
 808     }
 809
 810   /* Account for loop unrolling in the iteration count.  This will
 811      have no effect if loop_iterations could not determine the number
 812      of iterations.  */
 813   n_iterations /= loop_info->unroll_number;
 814   n_iterations_max /= loop_info->unroll_number;
 815
 816   if (n_iterations && n_iterations < 3)
 817     {
 818       if (loop_dump_stream)
 819         fprintf (loop_dump_stream,
 820                  "Doloop: Too few iterations (%ld) to be profitable.\n",
 821                  (long int) n_iterations);
 822       return 0;
 823     }
 824
 825   iterations = GEN_INT (n_iterations);
 826   iterations_max = GEN_INT (n_iterations_max);
 827
 828   /* Generate looping insn.  If the pattern FAILs then give up trying
 829      to modify the loop since there is some aspect the back-end does
 830      not like.  */
 831   start_label = gen_label_rtx ();
 832   doloop_reg = gen_reg_rtx (mode);
 833   doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 834                                GEN_INT (loop->level), start_label);
 835   if (! doloop_seq && mode != word_mode)
 836     {
 837       PUT_MODE (doloop_reg, word_mode);
 838       doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 839                                    GEN_INT (loop->level), start_label);
 840     }
 841   if (! doloop_seq)
 842     {
 843       if (loop_dump_stream)
 844         fprintf (loop_dump_stream,
 845                  "Doloop: Target unwilling to use doloop pattern!\n");
 846       return 0;
 847     }
 848
 849   /* If multiple instructions were created, the last must be the
 850      jump instruction.  Also, a raw define_insn may yield a plain
 851      pattern.  */
 852   doloop_pat = doloop_seq;
 853   if (INSN_P (doloop_pat))
 854     {
 855       while (NEXT_INSN (doloop_pat) != NULL_RTX)
 856         doloop_pat = NEXT_INSN (doloop_pat);
 857       if (GET_CODE (doloop_pat) == JUMP_INSN)
 858         doloop_pat = PATTERN (doloop_pat);
 859       else
 860         doloop_pat = NULL_RTX;
 861     }
 862
 863   if (! doloop_pat
 864       || ! (condition = doloop_condition_get (doloop_pat)))
 865     {
 866       if (loop_dump_stream)
 867         fprintf (loop_dump_stream,
 868                  "Doloop: Unrecognizable doloop pattern!\n");
 869       return 0;
 870     }
 871
 872   if (n_iterations != 0)
 873     /* Handle the simpler case, where we know the iteration count at
 874        compile time.  */
 875     return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 876                           start_label, condition);
 877   else
 878     /* Handle the harder case, where we must add additional runtime tests.  */
 879     return doloop_modify_runtime (loop, iterations_max, doloop_seq,
 880                                   start_label, mode, condition);
 881 }
 882
 883 #endif /* HAVE_doloop_end */