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 initial value is 0, the loop
 365          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 = gen_sequence ();
 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 = gen_sequence ();
 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   int neg_inc;
 556   rtx diff;
 557   rtx sequence;
 558   rtx iterations;
 559   rtx initial_value;
 560   rtx final_value;
 561   rtx increment;
 562   int unsigned_p;
 563   enum rtx_code comparison_code;
 564
 565   increment = loop_info->increment;
 566   initial_value = loop_info->initial_value;
 567   final_value = loop_info->final_value;
 568
 569   neg_inc = 0;
 570   abs_inc = INTVAL (increment);
 571   if (abs_inc < 0)
 572     {
 573       abs_inc = -abs_inc;
 574       neg_inc = 1;
 575     }
 576
 577   comparison_code = loop_info->comparison_code;
 578   unsigned_p = (comparison_code == LTU
 579                 || comparison_code == LEU
 580                 || comparison_code == GTU
 581                 || comparison_code == GEU
 582                 || comparison_code == NE);
 583
 584   /* The number of iterations (prior to any loop unrolling) is given by:
 585
 586        n = (abs (final - initial) + abs_inc - 1) / abs_inc.
 587
 588      However, it is possible for the summation to overflow, and a
 589      safer method is:
 590
 591        n = abs (final - initial) / abs_inc;
 592        n += (abs (final - initial) % abs_inc) != 0;
 593
 594      If the loop has been unrolled, then the loop body has been
 595      preconditioned to iterate a multiple of unroll_number times.  If
 596      abs_inc is != 1, the full calculation is
 597
 598        t1 = abs_inc * unroll_number;
 599        n = abs (final - initial) / t1;
 600        n += (abs (final - initial) % t1) > t1 - abs_inc;
 601
 602      The division and modulo operations can be avoided by requiring
 603      that the increment is a power of 2 (precondition_loop_p enforces
 604      this requirement).  Nevertheless, the RTX_COSTS should be checked
 605      to see if a fast divmod is available.  */
 606
 607   start_sequence ();
 608   /* abs (final - initial)  */
 609   diff = expand_simple_binop (mode, MINUS,
 610                               copy_rtx (neg_inc ? initial_value : final_value),
 611                               copy_rtx (neg_inc ? final_value : initial_value),
 612                               NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
 613
 614   /* Some code transformations can result in code akin to
 615
 616           tmp = i + 1;
 617           ...
 618           goto scan_start;
 619         top:
 620           tmp = tmp + 1;
 621         scan_start:
 622           i = tmp;
 623           if (i < n) goto top;
 624
 625      We'll have already detected this form of loop in scan_loop,
 626      and set loop->top and loop->scan_start appropriately.
 627
 628      In this situation, we skip the increment the first time through
 629      the loop, which results in an incorrect estimate of the number
 630      of iterations.  Adjust the difference to compensate.  */
 631   /* ??? Logically, it would seem this belongs in loop_iterations.
 632      However, this causes regressions e.g. on x86 execute/20011008-3.c,
 633      so I do not believe we've properly characterized the exact nature
 634      of the problem.  In the meantime, this fixes execute/20011126-2.c
 635      on ia64 and some Ada front end miscompilation on ppc.  */
 636
 637   if (loop->scan_start)
 638     {
 639       rtx iteration_var = loop_info->iteration_var;
 640       struct loop_ivs *ivs = LOOP_IVS (loop);
 641       struct iv_class *bl;
 642
 643       if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
 644         bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
 645       else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
 646         {
 647           struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
 648           bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
 649         }
 650       else
 651         /* Iteration var must be an induction variable to get here.  */
 652         abort ();
 653
 654       if (INSN_UID (bl->biv->insn) < max_uid_for_loop
 655           && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
 656         {
 657           if (loop_dump_stream)
 658             fprintf (loop_dump_stream,
 659                  "Doloop: Basic induction var skips initial incr.\n");
 660
 661           diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
 662                                       unsigned_p, OPTAB_LIB_WIDEN);
 663         }
 664     }
 665
 666   if (abs_inc * loop_info->unroll_number != 1)
 667     {
 668       int shift_count;
 669       rtx extra;
 670       rtx label;
 671       unsigned HOST_WIDE_INT limit;
 672
 673       shift_count = exact_log2 (abs_inc * loop_info->unroll_number);
 674       if (shift_count < 0)
 675         abort ();
 676
 677       /* abs (final - initial) / (abs_inc * unroll_number)  */
 678       iterations = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
 679                                         diff, GEN_INT (shift_count),
 680                                         NULL_RTX, 1,
 681                                         OPTAB_LIB_WIDEN);
 682
 683       if (abs_inc != 1)
 684         {
 685           /* abs (final - initial) % (abs_inc * unroll_number)  */
 686           rtx count = GEN_INT (abs_inc * loop_info->unroll_number - 1);
 687           extra = expand_simple_binop (GET_MODE (iterations), AND,
 688                                        diff, count, NULL_RTX, 1,
 689                                        OPTAB_LIB_WIDEN);
 690
 691           /* If (abs (final - initial) % (abs_inc * unroll_number)
 692                <= abs_inc * (unroll - 1)),
 693              jump past following increment instruction.  */
 694           label = gen_label_rtx ();
 695           limit = abs_inc * (loop_info->unroll_number - 1);
 696           emit_cmp_and_jump_insns (extra, GEN_INT (limit),
 697                                    limit == 0 ? EQ : LEU, NULL_RTX,
 698                                    GET_MODE (extra), 0, label);
 699           JUMP_LABEL (get_last_insn ()) = label;
 700           LABEL_NUSES (label)++;
 701
 702           /* Increment the iteration count by one.  */
 703           iterations = expand_simple_binop (GET_MODE (iterations), PLUS,
 704                                             iterations, GEN_INT (1),
 705                                             iterations, 1,
 706                                             OPTAB_LIB_WIDEN);
 707
 708           emit_label (label);
 709         }
 710     }
 711   else
 712     iterations = diff;
 713
 714   /* If there is a NOTE_INSN_LOOP_VTOP, we have a `for' or `while'
 715      style loop, with a loop exit test at the start.  Thus, we can
 716      assume that the loop condition was true when the loop was
 717      entered.
 718
 719      `do-while' loops require special treatment since the exit test is
 720      not executed before the start of the loop.  We need to determine
 721      if the loop will terminate after the first pass and to limit the
 722      iteration count to one if necessary.  */
 723   if (! loop->vtop)
 724     {
 725       rtx label;
 726
 727       if (loop_dump_stream)
 728         fprintf (loop_dump_stream, "Doloop: Do-while loop.\n");
 729
 730       /* A `do-while' loop must iterate at least once.  If the
 731          iteration count is bogus, we set the iteration count to 1.
 732          Note that if the loop has been unrolled, then the loop body
 733          is guaranteed to execute at least once.  */
 734       if (loop_info->unroll_number == 1)
 735         {
 736           /*  Emit insns to test if the loop will immediately
 737               terminate and to set the iteration count to 1 if true.  */
 738           label = gen_label_rtx();
 739           emit_cmp_and_jump_insns (copy_rtx (initial_value),
 740                                    copy_rtx (loop_info->comparison_value),
 741                                    comparison_code, NULL_RTX, mode, 0,
 742                                    label);
 743           JUMP_LABEL (get_last_insn ()) = label;
 744           LABEL_NUSES (label)++;
 745           emit_move_insn (iterations, const1_rtx);
 746           emit_label (label);
 747         }
 748     }
 749
 750   sequence = gen_sequence ();
 751   end_sequence ();
 752   emit_insn_before (sequence, loop->start);
 753
 754   return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 755                         start_label, condition);
 756 }
 757
 758
 759 /* This is the main entry point.  Process loop described by LOOP
 760    validating that the loop is suitable for conversion to use a low
 761    overhead looping instruction, replacing the jump insn where
 762    suitable.  We distinguish between loops with compile-time bounds
 763    and those with run-time bounds.  Information from LOOP is used to
 764    compute the number of iterations and to determine whether the loop
 765    is a candidate for this optimization.  Returns non-zero if loop
 766    successfully modified.  */
 767 int
 768 doloop_optimize (loop)
 769      const struct loop *loop;
 770 {
 771   struct loop_info *loop_info = LOOP_INFO (loop);
 772   rtx initial_value;
 773   rtx final_value;
 774   rtx increment;
 775   rtx jump_insn;
 776   enum machine_mode mode;
 777   unsigned HOST_WIDE_INT n_iterations;
 778   unsigned HOST_WIDE_INT n_iterations_max;
 779   rtx doloop_seq, doloop_pat, doloop_reg;
 780   rtx iterations;
 781   rtx iterations_max;
 782   rtx start_label;
 783   rtx condition;
 784
 785   if (loop_dump_stream)
 786     fprintf (loop_dump_stream,
 787              "Doloop: Processing loop %d, enclosed levels %d.\n",
 788              loop->num, loop->level);
 789
 790   jump_insn = prev_nonnote_insn (loop->end);
 791
 792   /* Check that loop is a candidate for a low-overhead looping insn.  */
 793   if (! doloop_valid_p (loop, jump_insn))
 794     return 0;
 795
 796   /* Determine if the loop can be safely, and profitably,
 797      preconditioned.  While we don't precondition the loop in a loop
 798      unrolling sense, this test ensures that the loop is well behaved
 799      and that the increment is a constant integer.  */
 800   if (! precondition_loop_p (loop, &initial_value, &final_value,
 801                              &increment, &mode))
 802     {
 803       if (loop_dump_stream)
 804         fprintf (loop_dump_stream,
 805                  "Doloop: Cannot precondition loop.\n");
 806       return 0;
 807     }
 808
 809   /* Determine or estimate the maximum number of loop iterations.  */
 810   n_iterations = loop_info->n_iterations;
 811   if (n_iterations)
 812     {
 813       /* This is the simple case where the initial and final loop
 814          values are constants.  */
 815       n_iterations_max = n_iterations;
 816     }
 817   else
 818     {
 819       int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0;
 820
 821       /* This is the harder case where the initial and final loop
 822          values may not be constants.  */
 823       n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg);
 824
 825       if (! n_iterations_max)
 826         {
 827           /* We have something like `for (i = 0; i < 10; i--)'.  */
 828           if (loop_dump_stream)
 829             fprintf (loop_dump_stream,
 830                      "Doloop: Not normal loop.\n");
 831           return 0;
 832         }
 833     }
 834
 835   /* Account for loop unrolling in the iteration count.  This will
 836      have no effect if loop_iterations could not determine the number
 837      of iterations.  */
 838   n_iterations /= loop_info->unroll_number;
 839   n_iterations_max /= loop_info->unroll_number;
 840
 841   if (n_iterations && n_iterations < 3)
 842     {
 843       if (loop_dump_stream)
 844         fprintf (loop_dump_stream,
 845                  "Doloop: Too few iterations (%ld) to be profitable.\n",
 846                  (long int) n_iterations);
 847       return 0;
 848     }
 849
 850   iterations = GEN_INT (n_iterations);
 851   iterations_max = GEN_INT (n_iterations_max);
 852
 853   /* Generate looping insn.  If the pattern FAILs then give up trying
 854      to modify the loop since there is some aspect the back-end does
 855      not like.  */
 856   start_label = gen_label_rtx ();
 857   doloop_reg = gen_reg_rtx (mode);
 858   doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 859                                GEN_INT (loop->level), start_label);
 860   if (! doloop_seq && mode != word_mode)
 861     {
 862       PUT_MODE (doloop_reg, word_mode);
 863       doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
 864                                    GEN_INT (loop->level), start_label);
 865     }
 866   if (! doloop_seq)
 867     {
 868       if (loop_dump_stream)
 869         fprintf (loop_dump_stream,
 870                  "Doloop: Target unwilling to use doloop pattern!\n");
 871       return 0;
 872     }
 873
 874   /* A raw define_insn may yield a plain pattern.  If a sequence
 875      was involved, the last must be the jump instruction.  */
 876   if (GET_CODE (doloop_seq) == SEQUENCE)
 877     {
 878       doloop_pat = XVECEXP (doloop_seq, 0, XVECLEN (doloop_seq, 0) - 1);
 879       if (GET_CODE (doloop_pat) == JUMP_INSN)
 880         doloop_pat = PATTERN (doloop_pat);
 881       else
 882         doloop_pat = NULL_RTX;
 883     }
 884   else
 885     doloop_pat = doloop_seq;
 886
 887   if (! doloop_pat
 888       || ! (condition = doloop_condition_get (doloop_pat)))
 889     {
 890       if (loop_dump_stream)
 891         fprintf (loop_dump_stream,
 892                  "Doloop: Unrecognizable doloop pattern!\n");
 893       return 0;
 894     }
 895
 896   if (n_iterations != 0)
 897     /* Handle the simpler case, where we know the iteration count at
 898        compile time.  */
 899     return doloop_modify (loop, iterations, iterations_max, doloop_seq,
 900                           start_label, condition);
 901   else
 902     /* Handle the harder case, where we must add additional runtime tests.  */
 903     return doloop_modify_runtime (loop, iterations_max, doloop_seq,
 904                                   start_label, mode, condition);
 905 }
 906
 907 #endif /* HAVE_doloop_end */