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 "flags.h"
  26 #include "expr.h"
  27 #include "loop.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "tm_p.h"
  31
  32
  33 /* This module is used to modify loops with a determinable number of
  34    iterations to use special low-overhead looping instructions.
  35
  36    It first validates whether the loop is well behaved and has a
  37    determinable number of iterations (either at compile or run-time).
  38    It then modifies the loop to use a low-overhead looping pattern as
  39    follows:
  40
  41    1. A pseudo register is allocated as the loop iteration counter.
  42
  43    2. The number of loop iterations is calculated and is stored
  44       in the loop counter.
  45
  46    3. At the end of the loop, the jump insn is replaced by the
  47       doloop_end pattern.  The compare must remain because it might be
  48       used elsewhere.  If the loop-variable or condition register are
  49       used elsewhere, they will be eliminated by flow.
  50
  51    4. An optional doloop_begin pattern is inserted at the top of the
  52       loop.
  53 */
  54
  55
  56 #ifdef HAVE_doloop_end
  57
  58 static rtx doloop_condition_get
  59   PARAMS ((rtx));
  60 static unsigned HOST_WIDE_INT doloop_iterations_max
  61   PARAMS ((const struct loop_info *, enum machine_mode, int));
  62 static int doloop_valid_p
  63   PARAMS ((const struct loop *, rtx));
  64 static int doloop_modify
  65   PARAMS ((const struct loop *, rtx, rtx, rtx, rtx, rtx));
  66 static int doloop_modify_runtime
  67   PARAMS ((const struct loop *, rtx, rtx, rtx, enum machine_mode, rtx));
  68
  69
  70 /* Return the loop termination condition for PATTERN or zero
  71    if it is not a decrement and branch jump insn.  */
  72 static rtx
  73 doloop_condition_get (pattern)
  74      rtx pattern;
  75 {
  76   rtx cmp;
  77   rtx inc;
  78   rtx reg;
  79   rtx condition;
  80
  81   /* The canonical doloop pattern we expect is:
  82
  83      (parallel [(set (pc) (if_then_else (condition)
  84                                         (label_ref (label))
  85                                         (pc)))
  86                 (set (reg) (plus (reg) (const_int -1)))
  87                 (additional clobbers and uses)])
  88
  89      Some machines (IA-64) make the decrement conditional on
  90      the condition as well, so we don't bother verifying the
  91      actual decrement.  In summary, the branch must be the
  92      first entry of the parallel (also required by jump.c),
  93      and the second entry of the parallel must be a set of
  94      the loop counter register.  */
  95
  96   if (GET_CODE (pattern) != PARALLEL)
  97     return 0;
  98
  99   cmp = XVECEXP (pattern, 0, 0);
 100   inc = XVECEXP (pattern, 0, 1);
 101
 102   /* Check for (set (reg) (something)).  */
 103   if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
 104     return 0;
 105
 106   /* Extract loop counter register.  */
 107   reg = SET_DEST (inc);
 108
 109   /* Check for (set (pc) (if_then_else (condition)
 110                                        (label_ref (label))
 111                                        (pc))).  */
 112   if (GET_CODE (cmp) != SET
 113       || SET_DEST (cmp) != pc_rtx
 114       || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
 115       || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
 116       || XEXP (SET_SRC (cmp), 2) != pc_rtx)
 117     return 0;
 118
 119   /* Extract loop termination condition.  */
 120   condition = XEXP (SET_SRC (cmp), 0);
 121
 122   if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
 123       || GET_CODE (XEXP (condition, 1)) != CONST_INT)
 124     return 0;
 125
 126   if (XEXP (condition, 0) == reg)
 127     return condition;
 128
 129   if (GET_CODE (XEXP (condition, 0)) == PLUS
 130       && XEXP (XEXP (condition, 0), 0) == reg)
 131     return condition;
 132
 133   /* ??? If a machine uses a funny comparison, we could return a
 134      canonicalised form here.  */
 135
 136   return 0;
 137 }
 138
 139
 140 /* Return an estimate of the maximum number of loop iterations for the
 141    loop specified by LOOP or zero if the loop is not normal.
 142    MODE is the mode of the iteration count and NONNEG is non-zero if
 143    the the iteration count has been proved to be non-negative.  */
 144 static unsigned HOST_WIDE_INT
 145 doloop_iterations_max (loop_info, mode, nonneg)
 146      const struct loop_info *loop_info;
 147      enum machine_mode mode;
 148      int nonneg;
 149 {
 150   unsigned HOST_WIDE_INT n_iterations_max;
 151   enum rtx_code code;
 152   rtx min_value;
 153   rtx max_value;
 154   HOST_WIDE_INT abs_inc;
 155   int neg_inc;
 156
 157   neg_inc = 0;
 158   abs_inc = INTVAL (loop_info->increment);
 159   if (abs_inc < 0)
 160     {
 161       abs_inc = -abs_inc;
 162       neg_inc = 1;
 163     }
 164
 165   if (neg_inc)
 166     {
 167       code = swap_condition (loop_info->comparison_code);
 168       min_value = loop_info->final_equiv_value;
 169       max_value = loop_info->initial_equiv_value;
 170     }
 171   else
 172     {
 173       code = loop_info->comparison_code;
 174       min_value = loop_info->initial_equiv_value;
 175       max_value = loop_info->final_equiv_value;
 176     }
 177
 178   /* Since the loop has a VTOP, we know that the initial test will be
 179      true and thus the value of max_value should be greater than the
 180      value of min_value.  Thus the difference should always be positive
 181      and the code must be LT, LE, LTU, LEU, or NE.  Otherwise the loop is
 182      not normal, e.g., `for (i = 0; i < 10; i--)'.  */
 183   switch (code)
 184     {
 185     case LTU:
 186     case LEU:
 187       {
 188         unsigned HOST_WIDE_INT umax;
 189         unsigned HOST_WIDE_INT umin;
 190
 191         if (GET_CODE (min_value) == CONST_INT)
 192           umin = INTVAL (min_value);
 193         else
 194           umin = 0;
 195
 196         if (GET_CODE (max_value) == CONST_INT)
 197           umax = INTVAL (max_value);
 198         else
 199           umax = ((unsigned)2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 200
 201         n_iterations_max = umax - umin;
 202         break;
 203       }
 204
 205     case LT:
 206     case LE:
 207       {
 208         HOST_WIDE_INT smax;
 209         HOST_WIDE_INT smin;
 210
 211         if (GET_CODE (min_value) == CONST_INT)
 212           smin = INTVAL (min_value);
 213         else
 214           smin = -((unsigned)1 << (GET_MODE_BITSIZE (mode) - 1));
 215
 216         if (GET_CODE (max_value) == CONST_INT)
 217           smax = INTVAL (max_value);
 218         else
 219           smax = ((unsigned)1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 220
 221         n_iterations_max = smax - smin;
 222         break;
 223       }
 224
 225     case NE:
 226       if (GET_CODE (min_value) == CONST_INT
 227           && GET_CODE (max_value) == CONST_INT)
 228         n_iterations_max = INTVAL (max_value) - INTVAL (min_value);
 229       else
 230         /* We need to conservatively assume that we might have the maximum
 231            number of iterations without any additional knowledge.  */
 232         n_iterations_max = ((unsigned)2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 233       break;
 234
 235     default:
 236       return 0;
 237     }
 238
 239   n_iterations_max /= abs_inc;
 240
 241   /* If we know that the iteration count is non-negative then adjust
 242      n_iterations_max if it is so large that it appears negative.  */
 243   if (nonneg
 244       && n_iterations_max > ((unsigned)1 << (GET_MODE_BITSIZE (mode) - 1)))
 245     n_iterations_max = ((unsigned)1 << (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 || loop->exit_count)
 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   /* Emit the label that will delimit the top of the loop.
 418      This has to be done before the delete_insn call below, to prevent
 419      delete_insn from deleting too much.  */
 420   emit_label_after (start_label, loop->top ? loop->top : loop->start);
 421   LABEL_NUSES (start_label)++;
 422
 423   /* Discard original jump to continue loop.  The original compare
 424      result may still be live, so it cannot be discarded explicitly.  */
 425   delete_insn (jump_insn);
 426
 427   counter_reg = XEXP (condition, 0);
 428   if (GET_CODE (counter_reg) == PLUS)
 429     counter_reg = XEXP (counter_reg, 0);
 430
 431   start_sequence ();
 432
 433   count = iterations;
 434   decrement_count = 0;
 435   switch (GET_CODE (condition))
 436     {
 437     case NE:
 438       /* Currently only NE tests against zero and one are supported.  */
 439       if (XEXP (condition, 1) == const0_rtx)
 440         decrement_count = 1;
 441       else if (XEXP (condition, 1) != const1_rtx)
 442         abort ();
 443       break;
 444
 445     case GE:
 446       /* Currently only GE tests against zero are supported.  */
 447       if (XEXP (condition, 1) != const0_rtx)
 448         abort ();
 449
 450       /* The iteration count needs decrementing for a GE test.  */
 451       decrement_count = 1;
 452
 453       /* Determine if the iteration counter will be non-negative.
 454          Note that the maximum value loaded is iterations_max - 1.  */
 455       if ((unsigned HOST_WIDE_INT) INTVAL (iterations_max)
 456           <= ((unsigned)1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1)))
 457         nonneg = 1;
 458       break;
 459
 460       /* Abort if an invalid doloop pattern has been generated.  */
 461     default:
 462       abort();
 463     }
 464
 465   if (decrement_count)
 466     {
 467       if (GET_CODE (count) == CONST_INT)
 468         count = GEN_INT (INTVAL (count) - 1);
 469       else
 470         count = expand_binop (GET_MODE (counter_reg), sub_optab,
 471                               count, GEN_INT (1),
 472                               0, 0, OPTAB_LIB_WIDEN);
 473     }
 474
 475   /* Insert initialization of the count register into the loop header.  */
 476   convert_move (counter_reg, count, 1);
 477   sequence = gen_sequence ();
 478   end_sequence ();
 479   emit_insn_before (sequence, loop->start);
 480
 481   /* Some targets (eg, C4x) need to initialize special looping
 482      registers.  */
 483 #ifdef HAVE_doloop_begin
 484   {
 485     rtx init;
 486
 487     init = gen_doloop_begin (counter_reg,
 488                              GET_CODE (iterations) == CONST_INT
 489                              ? iterations : const0_rtx, iterations_max,
 490                              GEN_INT (loop->level));
 491     if (init)
 492       {
 493         start_sequence ();
 494         emit_insn (init);
 495         sequence = gen_sequence ();
 496         end_sequence ();
 497         emit_insn_after (sequence, loop->start);
 498       }
 499   }
 500 #endif
 501
 502   /* Insert the new low-overhead looping insn.  */
 503   emit_jump_insn_before (doloop_seq, loop->end);
 504   jump_insn = prev_nonnote_insn (loop->end);
 505   JUMP_LABEL (jump_insn) = start_label;
 506
 507   /* Add a REG_NONNEG note if the actual or estimated maximum number
 508      of iterations is non-negative.  */
 509   if (nonneg)
 510     {
 511       REG_NOTES (jump_insn)
 512         = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
 513     }
 514   return 1;
 515 }
 516
 517
 518 /* Handle the more complex case, where the bounds are not known at
 519    compile time.  In this case we generate a run_time calculation of
 520    the number of iterations.  We rely on the existence of a run-time
 521    guard to ensure that the loop executes at least once, i.e.,
 522    initial_value obeys the loop comparison condition.  If a guard is
 523    not present, we emit one.  The loop to modify is described by LOOP.
 524    ITERATIONS_MAX is a CONST_INT specifying the estimated maximum
 525    number of loop iterations.  DOLOOP_INSN is the low-overhead looping
 526    insn to insert.  Returns non-zero if loop successfully modified.  */
 527 static int
 528 doloop_modify_runtime (loop, iterations_max,
 529                        doloop_seq, start_label, mode, condition)
 530      const struct loop *loop;
 531      rtx iterations_max;
 532      rtx doloop_seq;
 533      rtx start_label;
 534      enum machine_mode mode;
 535      rtx condition;
 536 {
 537   const struct loop_info *loop_info = LOOP_INFO (loop);
 538   HOST_WIDE_INT abs_inc;
 539   int neg_inc;
 540   rtx diff;
 541   rtx sequence;
 542   rtx iterations;
 543   rtx initial_value;
 544   rtx final_value;
 545   rtx increment;
 546   int unsigned_p;
 547   enum rtx_code comparison_code;
 548
 549   increment = loop_info->increment;
 550   initial_value = loop_info->initial_value;
 551   final_value = loop_info->final_value;
 552
 553   neg_inc = 0;
 554   abs_inc = INTVAL (increment);
 555   if (abs_inc < 0)
 556     {
 557       abs_inc = -abs_inc;
 558       neg_inc = 1;
 559     }
 560
 561   comparison_code = loop_info->comparison_code;
 562   unsigned_p = (comparison_code == LTU
 563                 || comparison_code == LEU
 564                 || comparison_code == GTU
 565                 || comparison_code == GEU
 566                 || comparison_code == NE);
 567
 568   /* The number of iterations (prior to any loop unrolling) is given by:
 569      (abs (final - initial) + abs_inc - 1) / abs_inc.
 570
 571      However, it is possible for the summation to overflow, and a
 572      safer method is:
 573
 574      abs (final - initial) / abs_inc + (abs (final - initial) % abs_inc) != 0
 575
 576      If the loop has been unrolled, then the loop body has been
 577      preconditioned to iterate a multiple of unroll_number times.
 578      The number of iterations of the loop body is simply:
 579      abs (final - initial) / (abs_inc * unroll_number).
 580
 581      The division and modulo operations can be avoided by requiring
 582      that the increment is a power of 2 (precondition_loop_p enforces
 583      this requirement).  Nevertheless, the RTX_COSTS should be checked
 584      to see if a fast divmod is available.  */
 585
 586   start_sequence ();
 587   /* abs (final - initial)  */
 588   diff = expand_binop (mode, sub_optab,
 589                        copy_rtx (neg_inc ? initial_value : final_value),
 590                        copy_rtx (neg_inc ? final_value : initial_value),
 591                        NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 592
 593   if (loop_info->unroll_number == 1)
 594     {
 595       if (abs_inc != 1)
 596         {
 597           int shift_count;
 598           rtx extra;
 599           rtx label;
 600
 601           shift_count = exact_log2 (abs_inc);
 602           if (shift_count < 0)
 603             abort ();
 604
 605           /* abs (final - initial) / abs_inc  */
 606           iterations = expand_binop (GET_MODE (diff), lshr_optab,
 607                                      diff, GEN_INT (shift_count),
 608                                      NULL_RTX, 1,
 609                                      OPTAB_LIB_WIDEN);
 610
 611           /* abs (final - initial) % abs_inc  */
 612           extra = expand_binop (GET_MODE (iterations), and_optab,
 613                                 diff, GEN_INT (abs_inc - 1),
 614                                 NULL_RTX, 1,
 615                                 OPTAB_LIB_WIDEN);
 616
 617           /* If (abs (final - initial) % abs_inc == 0) jump past
 618              following increment instruction.  */
 619           label = gen_label_rtx();
 620           emit_cmp_and_jump_insns (extra, const0_rtx, EQ, NULL_RTX,
 621                                    GET_MODE (extra), 0, 0, label);
 622           JUMP_LABEL (get_last_insn ()) = label;
 623           LABEL_NUSES (label)++;
 624
 625           /* Increment the iteration count by one.  */
 626           iterations = expand_binop (GET_MODE (iterations), add_optab,
 627                                      iterations, GEN_INT (1),
 628                                      iterations, 1,
 629                                      OPTAB_LIB_WIDEN);
 630
 631           emit_label (label);
 632         }
 633       else
 634         iterations = diff;
 635     }
 636   else
 637     {
 638       int shift_count;
 639
 640       /* precondition_loop_p has preconditioned the loop so that the
 641          iteration count of the loop body is always a power of 2.
 642          Since we won't get an overflow calculating the loop count,
 643          the code we emit is simpler.  */
 644       shift_count = exact_log2 (loop_info->unroll_number * abs_inc);
 645       if (shift_count < 0)
 646         abort ();
 647
 648       iterations = expand_binop (GET_MODE (diff), lshr_optab,
 649                                  diff, GEN_INT (shift_count),
 650                                  NULL_RTX, 1,
 651                                  OPTAB_LIB_WIDEN);
 652     }
 653
 654
 655   /* If there is a NOTE_INSN_LOOP_VTOP, we have a `for' or `while'
 656      style loop, with a loop exit test at the start.  Thus, we can
 657      assume that the loop condition was true when the loop was
 658      entered.
 659
 660      `do-while' loops require special treatment since the exit test is
 661      not executed before the start of the loop.  We need to determine
 662      if the loop will terminate after the first pass and to limit the
 663      iteration count to one if necessary.  */
 664   if (! loop->vtop)
 665     {
 666       rtx label;
 667
 668       if (loop_dump_stream)
 669         fprintf (loop_dump_stream, "Doloop: Do-while loop.\n");
 670
 671       /* A `do-while' loop must iterate at least once.  If the
 672          iteration count is bogus, we set the iteration count to 1.
 673          Note that if the loop has been unrolled, then the loop body
 674          is guaranteed to execute at least once.  */
 675       if (loop_info->unroll_number == 1)
 676         {
 677           /*  Emit insns to test if the loop will immediately
 678               terminate and to set the iteration count to 1 if true.  */
 679           label = gen_label_rtx();
 680           emit_cmp_and_jump_insns (copy_rtx (initial_value),
 681                                    copy_rtx (loop_info->comparison_value),
 682                                    comparison_code, NULL_RTX, mode, 0, 0,
 683                                    label);
 684           JUMP_LABEL (get_last_insn ()) = label;
 685           LABEL_NUSES (label)++;
 686           emit_move_insn (iterations, const1_rtx);
 687           emit_label (label);
 688         }
 689     }
 690
 691   sequence = gen_sequence ();
 692   end_sequence ();
 693   emit_insn_before (sequence, loop->start);
 694
 695   return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 696                         start_label, condition);
 697 }
 698
 699
 700 /* This is the main entry point.  Process loop described by LOOP
 701    validating that the loop is suitable for conversion to use a low
 702    overhead looping instruction, replacing the jump insn where
 703    suitable.  We distinguish between loops with compile-time bounds
 704    and those with run-time bounds.  Information from LOOP is used to
 705    compute the number of iterations and to determine whether the loop
 706    is a candidate for this optimization.  Returns non-zero if loop
 707    successfully modified.  */
 708 int
 709 doloop_optimize (loop)
 710      const struct loop *loop;
 711 {
 712   struct loop_info *loop_info = LOOP_INFO (loop);
 713   rtx initial_value;
 714   rtx final_value;
 715   rtx increment;
 716   rtx jump_insn;
 717   enum machine_mode mode;
 718   unsigned HOST_WIDE_INT n_iterations;
 719   unsigned HOST_WIDE_INT n_iterations_max;
 720   rtx doloop_seq, doloop_pat, doloop_reg;
 721   rtx iterations;
 722   rtx iterations_max;
 723   rtx start_label;
 724   rtx condition;
 725
 726   if (loop_dump_stream)
 727     fprintf (loop_dump_stream,
 728              "Doloop: Processing loop %d, enclosed levels %d.\n",
 729              loop->num, loop->level);
 730
 731   jump_insn = prev_nonnote_insn (loop->end);
 732
 733   /* Check that loop is a candidate for a low-overhead looping insn.  */
 734   if (! doloop_valid_p (loop, jump_insn))
 735     return 0;
 736
 737   /* Determine if the loop can be safely, and profitably,
 738      preconditioned.  While we don't precondition the loop in a loop
 739      unrolling sense, this test ensures that the loop is well behaved
 740      and that the increment is a constant integer.  */
 741   if (! precondition_loop_p (loop, &initial_value, &final_value,
 742                              &increment, &mode))
 743     {
 744       if (loop_dump_stream)
 745         fprintf (loop_dump_stream,
 746                  "Doloop: Cannot precondition loop.\n");
 747       return 0;
 748     }
 749
 750   /* Determine or estimate the maximum number of loop iterations.  */
 751   n_iterations = loop_info->n_iterations;
 752   if (n_iterations)
 753     {
 754       /* This is the simple case where the initial and final loop
 755          values are constants.  */
 756       n_iterations_max = n_iterations;
 757     }
 758   else
 759     {
 760       int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0;
 761
 762       /* This is the harder case where the initial and final loop
 763          values may not be constants.  */
 764       n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg);
 765
 766       if (! n_iterations_max)
 767         {
 768           /* We have something like `for (i = 0; i < 10; i--)'.  */
 769           if (loop_dump_stream)
 770             fprintf (loop_dump_stream,
 771                      "Doloop: Not normal loop.\n");
 772           return 0;
 773         }
 774     }
 775
 776   /* Account for loop unrolling in the iteration count.  This will
 777      have no effect if loop_iterations could not determine the number
 778      of iterations.  */
 779   n_iterations /= loop_info->unroll_number;
 780   n_iterations_max /= loop_info->unroll_number;
 781
 782   if (n_iterations && n_iterations < 3)
 783     {
 784       if (loop_dump_stream)
 785         fprintf (loop_dump_stream,
 786                  "Doloop: Too few iterations (%ld) to be profitable.\n",
 787                  (long int) n_iterations);
 788       return 0;
 789     }
 790
 791   iterations = GEN_INT (n_iterations);
 792   iterations_max = GEN_INT (n_iterations_max);
 793
 794   /* Generate looping insn.  If the pattern FAILs then give up trying
 795      to modify the loop since there is some aspect the back-end does
 796      not like.  */
 797   start_label = gen_label_rtx ();
 798   doloop_reg = gen_reg_rtx (mode);
 799   doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 800                                GEN_INT (loop->level), start_label);
 801   if (! doloop_seq && mode != word_mode)
 802     {
 803       PUT_MODE (doloop_reg, word_mode);
 804       doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 805                                    GEN_INT (loop->level), start_label);
 806     }
 807   if (! doloop_seq)
 808     {
 809       if (loop_dump_stream)
 810         fprintf (loop_dump_stream,
 811                  "Doloop: Target unwilling to use doloop pattern!\n");
 812       return 0;
 813     }
 814
 815   /* A raw define_insn may yield a plain pattern.  If a sequence
 816      was involved, the last must be the jump instruction.  */
 817   if (GET_CODE (doloop_seq) == SEQUENCE)
 818     {
 819       doloop_pat = XVECEXP (doloop_seq, 0, XVECLEN (doloop_seq, 0) - 1);
 820       if (GET_CODE (doloop_pat) == JUMP_INSN)
 821         doloop_pat = PATTERN (doloop_pat);
 822       else
 823         doloop_pat = NULL_RTX;
 824     }
 825   else
 826     doloop_pat = doloop_seq;
 827
 828   if (! doloop_pat
 829       || ! (condition = doloop_condition_get (doloop_pat)))
 830     {
 831       if (loop_dump_stream)
 832         fprintf (loop_dump_stream,
 833                  "Doloop: Unrecognizable doloop pattern!\n");
 834       return 0;
 835     }
 836
 837   if (n_iterations != 0)
 838     /* Handle the simpler case, where we know the iteration count at
 839        compile time.  */
 840     return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 841                           start_label, condition);
 842   else
 843     /* Handle the harder case, where we must add additional runtime tests.  */
 844     return doloop_modify_runtime (loop, iterations_max, doloop_seq,
 845                                   start_label, mode, condition);
 846 }
 847
 848 #endif /* HAVE_doloop_end */