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