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