gcc/doloop.c

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