gcc/doloop.c

   1 /* Perform doloop optimizations
   2    Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   3    Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 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 "toplev.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 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 = ((unsigned) 2 << (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 = -((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1));
 216
 217         if (GET_CODE (max_value) == CONST_INT)
 218           smax = INTVAL (max_value);
 219         else
 220           smax = ((unsigned) 1 << (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 = ((unsigned) 2 << (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
 245       && n_iterations_max > ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)))
 246     n_iterations_max = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
 247
 248   return n_iterations_max;
 249 }
 250
 251
 252 /* Return non-zero if the loop specified by LOOP is suitable for
 253    the use of special low-overhead looping instructions.  */
 254 static int
 255 doloop_valid_p (loop, jump_insn)
 256      const struct loop *loop;
 257      rtx jump_insn;
 258 {
 259   const struct loop_info *loop_info = LOOP_INFO (loop);
 260
 261   /* The loop must have a conditional jump at the end.  */
 262   if (! any_condjump_p (jump_insn)
 263       || ! onlyjump_p (jump_insn))
 264     {
 265       if (loop_dump_stream)
 266         fprintf (loop_dump_stream,
 267                  "Doloop: Invalid jump at loop end.\n");
 268       return 0;
 269     }
 270
 271   /* Give up if a loop has been completely unrolled.  */
 272   if (loop_info->n_iterations == loop_info->unroll_number)
 273     {
 274       if (loop_dump_stream)
 275         fprintf (loop_dump_stream,
 276                  "Doloop: Loop completely unrolled.\n");
 277       return 0;
 278     }
 279
 280   /* The loop must have a single exit target.  A break or return
 281      statement within a loop will generate multiple loop exits.
 282      Another example of a loop that currently generates multiple exit
 283      targets is for (i = 0; i < (foo ? 8 : 4); i++) { }.  */
 284   if (loop_info->has_multiple_exit_targets || loop->exit_count)
 285     {
 286       if (loop_dump_stream)
 287         fprintf (loop_dump_stream,
 288                  "Doloop: Loop has multiple exit targets.\n");
 289       return 0;
 290     }
 291
 292   /* An indirect jump may jump out of the loop.  */
 293   if (loop_info->has_indirect_jump)
 294     {
 295       if (loop_dump_stream)
 296         fprintf (loop_dump_stream,
 297                  "Doloop: Indirect jump in function.\n");
 298       return 0;
 299     }
 300
 301   /* A called function may clobber any special registers required for
 302      low-overhead looping.  */
 303   if (loop_info->has_call)
 304     {
 305       if (loop_dump_stream)
 306         fprintf (loop_dump_stream,
 307                  "Doloop: Function call in loop.\n");
 308       return 0;
 309     }
 310
 311   /* Some targets (eg, PPC) use the count register for branch on table
 312      instructions.  ??? This should be a target specific check.  */
 313   if (loop_info->has_tablejump)
 314     {
 315       if (loop_dump_stream)
 316         fprintf (loop_dump_stream,
 317                  "Doloop: Computed branch in the loop.\n");
 318       return 0;
 319     }
 320
 321   if (! loop_info->increment)
 322     {
 323       if (loop_dump_stream)
 324         fprintf (loop_dump_stream,
 325                  "Doloop: Could not determine iteration info.\n");
 326       return 0;
 327     }
 328
 329   if (GET_CODE (loop_info->increment) != CONST_INT)
 330     {
 331       if (loop_dump_stream)
 332         fprintf (loop_dump_stream,
 333                  "Doloop: Increment not an integer constant.\n");
 334       return 0;
 335     }
 336
 337   /* There is no guarantee that a NE loop will terminate if the
 338      absolute increment is not unity.  ??? We could compute this
 339      condition at run-time and have an additional jump around the loop
 340      to ensure an infinite loop.  */
 341   if (loop_info->comparison_code == NE
 342       && INTVAL (loop_info->increment) != -1
 343       && INTVAL (loop_info->increment) != 1)
 344     {
 345       if (loop_dump_stream)
 346         fprintf (loop_dump_stream,
 347                  "Doloop: NE loop with non-unity increment.\n");
 348       return 0;
 349     }
 350
 351   /* Check for loops that may not terminate under special conditions.  */
 352   if (! loop_info->n_iterations
 353       && ((loop_info->comparison_code == LEU
 354            && INTVAL (loop_info->increment) > 0)
 355           || (loop_info->comparison_code == GEU
 356               && INTVAL (loop_info->increment) < 0)
 357           || (loop_info->comparison_code == LTU
 358               && INTVAL (loop_info->increment) > 1)
 359           || (loop_info->comparison_code == GTU
 360               && INTVAL (loop_info->increment) < -1)))
 361     {
 362       /* If the comparison is LEU and the comparison value is UINT_MAX
 363          then the loop will not terminate.  Similarly, if the
 364          comparison code is GEU and the comparison value is 0, the
 365          loop will not terminate.
 366
 367          If the absolute increment is not 1, the loop can be infinite
 368          even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
 369
 370          Note that with LE and GE, the loop behaviour is undefined
 371          (C++ standard section 5 clause 5) if an overflow occurs, say
 372          between INT_MAX and INT_MAX + 1.  We thus don't have to worry
 373          about these two cases.
 374
 375          ??? We could compute these conditions at run-time and have a
 376          additional jump around the loop to ensure an infinite loop.
 377          However, it is very unlikely that this is the intended
 378          behaviour of the loop and checking for these rare boundary
 379          conditions would pessimize all other code.
 380
 381          If the loop is executed only a few times an extra check to
 382          restart the loop could use up most of the benefits of using a
 383          count register loop.  Note however, that normally, this
 384          restart branch would never execute, so it could be predicted
 385          well by the CPU.  We should generate the pessimistic code by
 386          default, and have an option, e.g. -funsafe-loops that would
 387          enable count-register loops in this case.  */
 388       if (loop_dump_stream)
 389         fprintf (loop_dump_stream,
 390                  "Doloop: Possible infinite iteration case ignored.\n");
 391     }
 392
 393   return 1;
 394 }
 395
 396
 397 /* Modify the loop to use the low-overhead looping insn where LOOP
 398    describes the loop, ITERATIONS is an RTX containing the desired
 399    number of loop iterations, ITERATIONS_MAX is a CONST_INT specifying
 400    the maximum number of loop iterations, and DOLOOP_INSN is the
 401    low-overhead looping insn to emit at the end of the loop.  This
 402    returns non-zero if it was successful.  */
 403 static int
 404 doloop_modify (loop, iterations, iterations_max,
 405                doloop_seq, start_label, condition)
 406      const struct loop *loop;
 407      rtx iterations;
 408      rtx iterations_max;
 409      rtx doloop_seq;
 410      rtx start_label;
 411      rtx condition;
 412 {
 413   rtx counter_reg;
 414   rtx count;
 415   rtx sequence;
 416   rtx jump_insn;
 417   int nonneg = 0;
 418   int decrement_count;
 419
 420   jump_insn = prev_nonnote_insn (loop->end);
 421
 422   if (loop_dump_stream)
 423     {
 424       fprintf (loop_dump_stream, "Doloop: Inserting doloop pattern (");
 425       if (GET_CODE (iterations) == CONST_INT)
 426         fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
 427                  INTVAL (iterations));
 428       else
 429         fputs ("runtime", loop_dump_stream);
 430       fputs (" iterations).", loop_dump_stream);
 431     }
 432
 433   /* Emit the label that will delimit the top of the loop.
 434      This has to be done before the delete_insn call below, to prevent
 435      delete_insn from deleting too much.  */
 436   emit_label_after (start_label, loop->top ? loop->top : loop->start);
 437   LABEL_NUSES (start_label)++;
 438
 439   /* Discard original jump to continue loop.  The original compare
 440      result may still be live, so it cannot be discarded explicitly.  */
 441   delete_related_insns (jump_insn);
 442
 443   counter_reg = XEXP (condition, 0);
 444   if (GET_CODE (counter_reg) == PLUS)
 445     counter_reg = XEXP (counter_reg, 0);
 446
 447   start_sequence ();
 448
 449   count = iterations;
 450   decrement_count = 0;
 451   switch (GET_CODE (condition))
 452     {
 453     case NE:
 454       /* Currently only NE tests against zero and one are supported.  */
 455       if (XEXP (condition, 1) == const0_rtx)
 456         decrement_count = 1;
 457       else if (XEXP (condition, 1) != const1_rtx)
 458         abort ();
 459       break;
 460
 461     case GE:
 462       /* Currently only GE tests against zero are supported.  */
 463       if (XEXP (condition, 1) != const0_rtx)
 464         abort ();
 465
 466       /* The iteration count needs decrementing for a GE test.  */
 467       decrement_count = 1;
 468
 469       /* Determine if the iteration counter will be non-negative.
 470          Note that the maximum value loaded is iterations_max - 1.  */
 471       if ((unsigned HOST_WIDE_INT) INTVAL (iterations_max)
 472           <= ((unsigned) 1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1)))
 473         nonneg = 1;
 474       break;
 475
 476       /* Abort if an invalid doloop pattern has been generated.  */
 477     default:
 478       abort ();
 479     }
 480
 481   if (decrement_count)
 482     {
 483       if (GET_CODE (count) == CONST_INT)
 484         count = GEN_INT (INTVAL (count) - 1);
 485       else
 486         count = expand_simple_binop (GET_MODE (counter_reg), MINUS,
 487                                      count, GEN_INT (1),
 488                                      0, 0, OPTAB_LIB_WIDEN);
 489     }
 490
 491   /* Insert initialization of the count register into the loop header.  */
 492   convert_move (counter_reg, count, 1);
 493   sequence = get_insns ();
 494   end_sequence ();
 495   emit_insn_before (sequence, loop->start);
 496
 497   /* Some targets (eg, C4x) need to initialize special looping
 498      registers.  */
 499 #ifdef HAVE_doloop_begin
 500   {
 501     rtx init;
 502
 503     init = gen_doloop_begin (counter_reg,
 504                              GET_CODE (iterations) == CONST_INT
 505                              ? iterations : const0_rtx, iterations_max,
 506                              GEN_INT (loop->level));
 507     if (init)
 508       {
 509         start_sequence ();
 510         emit_insn (init);
 511         sequence = get_insns ();
 512         end_sequence ();
 513         emit_insn_after (sequence, loop->start);
 514       }
 515   }
 516 #endif
 517
 518   /* Insert the new low-overhead looping insn.  */
 519   emit_jump_insn_before (doloop_seq, loop->end);
 520   jump_insn = prev_nonnote_insn (loop->end);
 521   JUMP_LABEL (jump_insn) = start_label;
 522
 523   /* Add a REG_NONNEG note if the actual or estimated maximum number
 524      of iterations is non-negative.  */
 525   if (nonneg)
 526     {
 527       REG_NOTES (jump_insn)
 528         = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
 529     }
 530   return 1;
 531 }
 532
 533
 534 /* Handle the more complex case, where the bounds are not known at
 535    compile time.  In this case we generate a run_time calculation of
 536    the number of iterations.  We rely on the existence of a run-time
 537    guard to ensure that the loop executes at least once, i.e.,
 538    initial_value obeys the loop comparison condition.  If a guard is
 539    not present, we emit one.  The loop to modify is described by LOOP.
 540    ITERATIONS_MAX is a CONST_INT specifying the estimated maximum
 541    number of loop iterations.  DOLOOP_INSN is the low-overhead looping
 542    insn to insert.  Returns non-zero if loop successfully modified.  */
 543 static int
 544 doloop_modify_runtime (loop, iterations_max,
 545                        doloop_seq, start_label, mode, condition)
 546      const struct loop *loop;
 547      rtx iterations_max;
 548      rtx doloop_seq;
 549      rtx start_label;
 550      enum machine_mode mode;
 551      rtx condition;
 552 {
 553   const struct loop_info *loop_info = LOOP_INFO (loop);
 554   HOST_WIDE_INT abs_inc;
 555   HOST_WIDE_INT abs_loop_inc;
 556   int neg_inc;
 557   rtx diff;
 558   rtx sequence;
 559   rtx iterations;
 560   rtx initial_value;
 561   rtx final_value;
 562   rtx increment;
 563   int unsigned_p;
 564   enum rtx_code comparison_code;
 565
 566   increment = loop_info->increment;
 567   initial_value = loop_info->initial_value;
 568   final_value = loop_info->final_value;
 569
 570   neg_inc = 0;
 571   abs_inc = INTVAL (increment);
 572   if (abs_inc < 0)
 573     {
 574       abs_inc = -abs_inc;
 575       neg_inc = 1;
 576     }
 577
 578   comparison_code = loop_info->comparison_code;
 579   unsigned_p = (comparison_code == LTU
 580                 || comparison_code == LEU
 581                 || comparison_code == GTU
 582                 || comparison_code == GEU
 583                 || comparison_code == NE);
 584
 585   /* The number of iterations (prior to any loop unrolling) is given by:
 586
 587        n = (abs (final - initial) + abs_inc - 1) / abs_inc.
 588
 589      However, it is possible for the summation to overflow, and a
 590      safer method is:
 591
 592        n = abs (final - initial) / abs_inc;
 593        n += (abs (final - initial) % abs_inc) != 0;
 594
 595      But when abs_inc is a power of two, the summation won't overflow
 596      except in cases where the loop never terminates.  So we don't
 597      need to use this more costly calculation.
 598
 599      If the loop has been unrolled, the full calculation is
 600
 601        t1 = abs_inc * unroll_number;            increment per loop
 602        n = abs (final - initial) / t1;          full loops
 603        n += (abs (final - initial) % t1) != 0;  partial loop
 604
 605      However, in certain cases the unrolled loop will be preconditioned
 606      by emitting copies of the loop body with conditional branches,
 607      so that the unrolled loop is always a full loop and thus needs
 608      no exit tests.  In this case we don't want to add the partial
 609      loop count.  As above, when t1 is a power of two we don't need to
 610      worry about overflow.
 611
 612      The division and modulo operations can be avoided by requiring
 613      that the increment is a power of 2 (precondition_loop_p enforces
 614      this requirement).  Nevertheless, the RTX_COSTS should be checked
 615      to see if a fast divmod is available.  */
 616
 617   start_sequence ();
 618   /* abs (final - initial)  */
 619   diff = expand_simple_binop (mode, MINUS,
 620                               copy_rtx (neg_inc ? initial_value : final_value),
 621                               copy_rtx (neg_inc ? final_value : initial_value),
 622                               NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 623
 624   /* Some code transformations can result in code akin to
 625
 626           tmp = i + 1;
 627           ...
 628           goto scan_start;
 629         top:
 630           tmp = tmp + 1;
 631         scan_start:
 632           i = tmp;
 633           if (i < n) goto top;
 634
 635      We'll have already detected this form of loop in scan_loop,
 636      and set loop->top and loop->scan_start appropriately.
 637
 638      In this situation, we skip the increment the first time through
 639      the loop, which results in an incorrect estimate of the number
 640      of iterations.  Adjust the difference to compensate.  */
 641   /* ??? Logically, it would seem this belongs in loop_iterations.
 642      However, this causes regressions e.g. on x86 execute/20011008-3.c,
 643      so I do not believe we've properly characterized the exact nature
 644      of the problem.  In the meantime, this fixes execute/20011126-2.c
 645      on ia64 and some Ada front end miscompilation on ppc.  */
 646
 647   if (loop->scan_start)
 648     {
 649       rtx iteration_var = loop_info->iteration_var;
 650       struct loop_ivs *ivs = LOOP_IVS (loop);
 651       struct iv_class *bl;
 652
 653       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
 654         bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
 655       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
 656         {
 657           struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
 658           bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
 659         }
 660       else
 661         /* Iteration var must be an induction variable to get here.  */
 662         abort ();
 663
 664       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
 665           && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
 666         {
 667           if (loop_dump_stream)
 668             fprintf (loop_dump_stream,
 669                  "Doloop: Basic induction var skips initial incr.\n");
 670
 671           diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
 672                                       unsigned_p, OPTAB_LIB_WIDEN);
 673         }
 674     }
 675
 676   abs_loop_inc = abs_inc * loop_info->unroll_number;
 677   if (abs_loop_inc != 1)
 678     {
 679       int shift_count;
 680
 681       shift_count = exact_log2 (abs_loop_inc);
 682       if (shift_count < 0)
 683         abort ();
 684
 685       if (!loop_info->preconditioned)
 686         diff = expand_simple_binop (GET_MODE (diff), PLUS,
 687                                     diff, GEN_INT (abs_loop_inc - 1),
 688                                     diff, 1, OPTAB_LIB_WIDEN);
 689
 690       /* (abs (final - initial) + abs_inc * unroll_number - 1)
 691          / (abs_inc * unroll_number)  */
 692       diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
 693                                   diff, GEN_INT (shift_count),
 694                                   diff, 1, OPTAB_LIB_WIDEN);
 695     }
 696   iterations = diff;
 697
 698   /* If there is a NOTE_INSN_LOOP_VTOP, we have a `for' or `while'
 699      style loop, with a loop exit test at the start.  Thus, we can
 700      assume that the loop condition was true when the loop was
 701      entered.
 702
 703      `do-while' loops require special treatment since the exit test is
 704      not executed before the start of the loop.  We need to determine
 705      if the loop will terminate after the first pass and to limit the
 706      iteration count to one if necessary.  */
 707   if (! loop->vtop)
 708     {
 709       if (loop_dump_stream)
 710         fprintf (loop_dump_stream, "Doloop: Do-while loop.\n");
 711
 712       /* A `do-while' loop must iterate at least once.  For code like
 713          i = initial; do { ... } while (++i < final);
 714          we will calculate a bogus iteration count if initial > final.
 715          So detect this and set the iteration count to 1.
 716          Note that if the loop has been unrolled, then the loop body
 717          is guaranteed to execute at least once.  Also, when the
 718          comparison is NE, our calculated count will be OK.  */
 719       if (loop_info->unroll_number == 1 && comparison_code != NE)
 720         {
 721           rtx label;
 722
 723           /*  Emit insns to test if the loop will immediately
 724               terminate and to set the iteration count to 1 if true.  */
 725           label = gen_label_rtx();
 726           emit_cmp_and_jump_insns (copy_rtx (initial_value),
 727                                    copy_rtx (loop_info->comparison_value),
 728                                    comparison_code, NULL_RTX, mode, 0,
 729                                    label);
 730           JUMP_LABEL (get_last_insn ()) = label;
 731           LABEL_NUSES (label)++;
 732           emit_move_insn (iterations, const1_rtx);
 733           emit_label (label);
 734         }
 735     }
 736
 737   sequence = get_insns ();
 738   end_sequence ();
 739   emit_insn_before (sequence, loop->start);
 740
 741   return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 742                         start_label, condition);
 743 }
 744
 745
 746 /* This is the main entry point.  Process loop described by LOOP
 747    validating that the loop is suitable for conversion to use a low
 748    overhead looping instruction, replacing the jump insn where
 749    suitable.  We distinguish between loops with compile-time bounds
 750    and those with run-time bounds.  Information from LOOP is used to
 751    compute the number of iterations and to determine whether the loop
 752    is a candidate for this optimization.  Returns non-zero if loop
 753    successfully modified.  */
 754 int
 755 doloop_optimize (loop)
 756      const struct loop *loop;
 757 {
 758   struct loop_info *loop_info = LOOP_INFO (loop);
 759   rtx initial_value;
 760   rtx final_value;
 761   rtx increment;
 762   rtx jump_insn;
 763   enum machine_mode mode;
 764   unsigned HOST_WIDE_INT n_iterations;
 765   unsigned HOST_WIDE_INT n_iterations_max;
 766   rtx doloop_seq, doloop_pat, doloop_reg;
 767   rtx iterations;
 768   rtx iterations_max;
 769   rtx start_label;
 770   rtx condition;
 771
 772   if (loop_dump_stream)
 773     fprintf (loop_dump_stream,
 774              "Doloop: Processing loop %d, enclosed levels %d.\n",
 775              loop->num, loop->level);
 776
 777   jump_insn = prev_nonnote_insn (loop->end);
 778
 779   /* Check that loop is a candidate for a low-overhead looping insn.  */
 780   if (! doloop_valid_p (loop, jump_insn))
 781     return 0;
 782
 783   /* Determine if the loop can be safely, and profitably,
 784      preconditioned.  While we don't precondition the loop in a loop
 785      unrolling sense, this test ensures that the loop is well behaved
 786      and that the increment is a constant integer.  */
 787   if (! precondition_loop_p (loop, &initial_value, &final_value,
 788                              &increment, &mode))
 789     {
 790       if (loop_dump_stream)
 791         fprintf (loop_dump_stream,
 792                  "Doloop: Cannot precondition loop.\n");
 793       return 0;
 794     }
 795
 796   /* Determine or estimate the maximum number of loop iterations.  */
 797   n_iterations = loop_info->n_iterations;
 798   if (n_iterations)
 799     {
 800       /* This is the simple case where the initial and final loop
 801          values are constants.  */
 802       n_iterations_max = n_iterations;
 803     }
 804   else
 805     {
 806       int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0;
 807
 808       /* This is the harder case where the initial and final loop
 809          values may not be constants.  */
 810       n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg);
 811
 812       if (! n_iterations_max)
 813         {
 814           /* We have something like `for (i = 0; i < 10; i--)'.  */
 815           if (loop_dump_stream)
 816             fprintf (loop_dump_stream,
 817                      "Doloop: Not normal loop.\n");
 818           return 0;
 819         }
 820     }
 821
 822   /* Account for loop unrolling in the iteration count.  This will
 823      have no effect if loop_iterations could not determine the number
 824      of iterations.  */
 825   n_iterations /= loop_info->unroll_number;
 826   n_iterations_max /= loop_info->unroll_number;
 827
 828   if (n_iterations && n_iterations < 3)
 829     {
 830       if (loop_dump_stream)
 831         fprintf (loop_dump_stream,
 832                  "Doloop: Too few iterations (%ld) to be profitable.\n",
 833                  (long int) n_iterations);
 834       return 0;
 835     }
 836
 837   iterations = GEN_INT (n_iterations);
 838   iterations_max = GEN_INT (n_iterations_max);
 839
 840   /* Generate looping insn.  If the pattern FAILs then give up trying
 841      to modify the loop since there is some aspect the back-end does
 842      not like.  */
 843   start_label = gen_label_rtx ();
 844   doloop_reg = gen_reg_rtx (mode);
 845   doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 846                                GEN_INT (loop->level), start_label);
 847   if (! doloop_seq && mode != word_mode)
 848     {
 849       PUT_MODE (doloop_reg, word_mode);
 850       doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 851                                    GEN_INT (loop->level), start_label);
 852     }
 853   if (! doloop_seq)
 854     {
 855       if (loop_dump_stream)
 856         fprintf (loop_dump_stream,
 857                  "Doloop: Target unwilling to use doloop pattern!\n");
 858       return 0;
 859     }
 860
 861   /* If multiple instructions were created, the last must be the
 862      jump instruction.  Also, a raw define_insn may yield a plain
 863      pattern.  */
 864   doloop_pat = doloop_seq;
 865   if (INSN_P (doloop_pat))
 866     {
 867       while (NEXT_INSN (doloop_pat) != NULL_RTX)
 868         doloop_pat = NEXT_INSN (doloop_pat);
 869       if (GET_CODE (doloop_pat) == JUMP_INSN)
 870         doloop_pat = PATTERN (doloop_pat);
 871       else
 872         doloop_pat = NULL_RTX;
 873     }
 874
 875   if (! doloop_pat
 876       || ! (condition = doloop_condition_get (doloop_pat)))
 877     {
 878       if (loop_dump_stream)
 879         fprintf (loop_dump_stream,
 880                  "Doloop: Unrecognizable doloop pattern!\n");
 881       return 0;
 882     }
 883
 884   if (n_iterations != 0)
 885     /* Handle the simpler case, where we know the iteration count at
 886        compile time.  */
 887     return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 888                           start_label, condition);
 889   else
 890     /* Handle the harder case, where we must add additional runtime tests.  */
 891     return doloop_modify_runtime (loop, iterations_max, doloop_seq,
 892                                   start_label, mode, condition);
 893 }
 894
 895 #endif /* HAVE_doloop_end */