gcc/reorg.c

   1 /* Perform instruction reorganizations for delay slot filling.
   2    Copyright (C) 1992 Free Software Foundation, Inc.
   3    Contributed by Richard Kenner (kenner@nyu.edu).
   4    Hacked by Michael Tiemann (tiemann@cygnus.com).
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21
  22
  23 #include "insn-attr.h"
  24
  25 #ifdef DELAY_SLOTS
  26
  27 /* Instruction reorganization pass.
  28
  29    This pass runs after register allocation and final jump
  30    optimization.  It should be the last pass to run before peephole.
  31    It serves primarily to fill delay slots of insns, typically branch
  32    and call insns.  Other insns typically involve more complicated
  33    interractions of data dependencies and resource constraints, and
  34    are better handled by scheduling before register allocation (by the
  35    function `schedule_insns').
  36
  37    The Branch Penalty is the number of extra cycles that are needed to
  38    execute a branch insn.  On an ideal machine, branches take a single
  39    cycle, and the Branch Penalty is 0.  Several RISC machines approach
  40    branch delays differently:
  41
  42    The MIPS and AMD 29000 have a single branch delay slot.  Most insns
  43    (except other branches) can be used to fill this slot.  When the
  44    slot is filled, two insns execute in two cycles, reducing the
  45    branch penalty to zero.
  46
  47    The Motorola 88000 conditionally exposes its branch delay slot,
  48    so code is shorter when it is turned off, but will run faster
  49    when useful insns are scheduled there.
  50
  51    The IBM ROMP has two forms of branch and call insns, both with and
  52    without a delay slot.  Much like the 88k, insns not using the delay
  53    slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
  54
  55    The SPARC always has a branch delay slot, but its effects can be
  56    annulled when the branch is not taken.  This means that failing to
  57    find other sources of insns, we can hoist an insn from the branch
  58    target that would only be safe to execute knowing that the branch
  59    is taken.
  60
  61    Three techniques for filling delay slots have been implemented so far:
  62
  63    (1) `fill_simple_delay_slots' is the simplest, most efficient way
  64    to fill delay slots.  This pass first looks for insns which come
  65    from before the branch and which are safe to execute after the
  66    branch.  Then it searches after the insn requiring delay slots or,
  67    in the case of a branch, for insns that are after the point at
  68    which the branch merges into the fallthrough code, if such a point
  69    exists.  When such insns are found, the branch penalty decreases
  70    and no code expansion takes place.
  71
  72    (2) `fill_eager_delay_slots' is more complicated: it is used for
  73    scheduling conditional jumps, or for scheduling jumps which cannot
  74    be filled using (1).  A machine need not have annulled jumps to use
  75    this strategy, but it helps (by keeping more options open).
  76    `fill_eager_delay_slots' tries to guess the direction the branch
  77    will go; if it guesses right 100% of the time, it can reduce the
  78    branch penalty as much as `fill_eager_delay_slots' does.  If it
  79    guesses wrong 100% of the time, it might as well schedule nops (or
  80    on the m88k, unexpose the branch slot).  When
  81    `fill_eager_delay_slots' takes insns from the fall-through path of
  82    the jump, usually there is no code expansion; when it takes insns
  83    from the branch target, there is code expansion if it is not the
  84    only way to reach that target.
  85
  86    (3) `relax_delay_slots' uses a set of rules to simplify code that
  87    has been reorganized by (1) and (2).  It finds cases where
  88    conditional test can be eliminated, jumps can be threaded, extra
  89    insns can be eliminated, etc.  It is the job of (1) and (2) to do a
  90    good job of scheduling locally; `relax_delay_slots' takes care of
  91    making the various individual schedules work well together.  It is
  92    especially tuned to handle the control flow interactions of branch
  93    insns.  It does nothing for insns with delay slots that do not
  94    branch.
  95
  96    On machines that use CC0, we are very conservative.  We will not make
  97    a copy of an insn involving CC0 since we want to maintain a 1-1
  98    correspondance between the insn that sets and uses CC0.  The insns are
  99    allowed to be separated by placing an insn that sets CC0 (but not an insn
 100    that uses CC0; we could do this, but it doesn't seem worthwhile) in a
 101    delay slot.  In that case, we point each insn at the other with REG_CC_USER
 102    and REG_CC_SETTER notes.  Note that these restrictions affect very few
 103    machines because most RISC machines with delay slots will not use CC0
 104    (the RT is the only known exception at this point).
 105
 106    Not yet implemented:
 107
 108    The Acorn Risc Machine can conditionally execute most insns, so
 109    it is profitable to move single insns into a position to execute
 110    based on the condition code of the previous insn.
 111
 112    The HP-PA can conditionally nullify insns, providing a similar
 113    effect to the ARM, differing mostly in which insn is "in charge".   */
 114
 115 #include <stdio.h>
 116 #include "config.h"
 117 #include "rtl.h"
 118 #include "insn-config.h"
 119 #include "conditions.h"
 120 #include "hard-reg-set.h"
 121 #include "basic-block.h"
 122 #include "regs.h"
 123 #include "insn-flags.h"
 124 #include "recog.h"
 125 #include "flags.h"
 126 #include "output.h"
 127 #include "obstack.h"
 128
 129 #define obstack_chunk_alloc xmalloc
 130 #define obstack_chunk_free free
 131
 132 extern int xmalloc ();
 133 extern void free ();
 134
 135 #ifndef ANNUL_IFTRUE_SLOTS
 136 #define eligible_for_annul_true(INSN, SLOTS, TRIAL) 0
 137 #endif
 138 #ifndef ANNUL_IFFALSE_SLOTS
 139 #define eligible_for_annul_false(INSN, SLOTS, TRIAL) 0
 140 #endif
 141
 142 /* Insns which have delay slots that have not yet been filled.  */
 143
 144 static struct obstack unfilled_slots_obstack;
 145 static rtx *unfilled_firstobj;
 146
 147 /* Define macros to refer to the first and last slot containing unfilled
 148    insns.  These are used because the list may move and its address
 149    should be recomputed at each use.  */
 150
 151 #define unfilled_slots_base     \
 152   ((rtx *) obstack_base (&unfilled_slots_obstack))
 153
 154 #define unfilled_slots_next     \
 155   ((rtx *) obstack_next_free (&unfilled_slots_obstack))
 156
 157 /* This structure is used to indicate which hardware resources are set or
 158    needed by insns so far.  */
 159
 160 struct resources
 161 {
 162   char memory;                  /* Insn sets or needs a memory location.  */
 163   char volatil;                 /* Insn sets or needs a volatile memory loc. */
 164   char cc;                      /* Insn sets or needs the condition codes.  */
 165   HARD_REG_SET regs;            /* Which registers are set or needed.  */
 166 };
 167
 168 /* Macro to clear all resources.  */
 169 #define CLEAR_RESOURCE(RES)     \
 170  do { (RES)->memory = (RES)->volatil = (RES)->cc = 0;   \
 171       CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
 172
 173 /* Indicates what resources are required at function end.  */
 174 static struct resources end_of_function_needs;
 175
 176 /* Points to the label before the end of the function.  */
 177 static rtx end_of_function_label;
 178
 179 /* This structure is used to record livness information at the targets or
 180    fallthrough insns of branches.  We will most likely need the information
 181    at targets again, so save them in a hash table rather than recomputing them
 182    each time.  */
 183
 184 struct target_info
 185 {
 186   int uid;                      /* INSN_UID of target.  */
 187   struct target_info *next;     /* Next info for same hash bucket.  */
 188   HARD_REG_SET live_regs;       /* Registers live at target.  */
 189   int block;                    /* Basic block number containing target.  */
 190   int bb_tick;                  /* Generation count of basic block info.  */
 191 };
 192
 193 #define TARGET_HASH_PRIME 257
 194
 195 /* Define the hash table itself.  */
 196 static struct target_info **target_hash_table;
 197
 198 /* For each basic block, we maintain a generation number of its basic
 199    block info, which is updated each time we move an insn from the
 200    target of a jump.  This is the generation number indexed by block
 201    number.  */
 202
 203 static int *bb_ticks;
 204
 205 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
 206    not always monotonically increase.  */
 207 static int *uid_to_ruid;
 208
 209 /* Highest valid index in `uid_to_ruid'.  */
 210 static int max_uid;
 211
 212 /* Forward references: */
 213
 214 static int redundant_insn_p ();
 215 static void update_block ();
 216 \f
 217 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
 218    which resources are references by the insn.  If INCLUDE_CALLED_ROUTINE
 219    is TRUE, resources used by the called routine will be included for
 220    CALL_INSNs.  */
 221
 222 static void
 223 mark_referenced_resources (x, res, include_called_routine)
 224      register rtx x;
 225      register struct resources *res;
 226      register int include_called_routine;
 227 {
 228   register enum rtx_code code = GET_CODE (x);
 229   register int i, j;
 230   register char *format_ptr;
 231
 232   /* Handle leaf items for which we set resource flags.  Also, special-case
 233      CALL, SET and CLOBBER operators.  */
 234   switch (code)
 235     {
 236     case CONST:
 237     case CONST_INT:
 238     case CONST_DOUBLE:
 239     case PC:
 240     case SYMBOL_REF:
 241     case LABEL_REF:
 242       return;
 243
 244     case SUBREG:
 245       if (GET_CODE (SUBREG_REG (x)) != REG)
 246         mark_referenced_resources (SUBREG_REG (x), res, 0);
 247       else
 248         {
 249           int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
 250           int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
 251           for (i = regno; i < last_regno; i++)
 252             SET_HARD_REG_BIT (res->regs, i);
 253         }
 254       return;
 255
 256     case REG:
 257       for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
 258         SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
 259       return;
 260
 261     case MEM:
 262       /* If this memory shouldn't change, it really isn't referencing
 263          memory.  */
 264       if (! RTX_UNCHANGING_P (x))
 265         res->memory = 1;
 266       res->volatil = MEM_VOLATILE_P (x);
 267
 268       /* Mark registers used to access memory.  */
 269       mark_referenced_resources (XEXP (x, 0), res, 0);
 270       return;
 271
 272     case CC0:
 273       res->cc = 1;
 274       return;
 275
 276     case UNSPEC_VOLATILE:
 277     case ASM_INPUT:
 278       /* Traditional asm's are always volatile.  */
 279       res->volatil = 1;
 280       return;
 281
 282     case ASM_OPERANDS:
 283       res->volatil = MEM_VOLATILE_P (x);
 284
 285       /* For all ASM_OPERANDS, we must traverse the vector of input operands.
 286          We can not just fall through here since then we would be confused
 287          by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
 288          traditional asms unlike their normal usage.  */
 289
 290       for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
 291         mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
 292       return;
 293
 294     case CALL:
 295       /* The first operand will be a (MEM (xxx)) but doesn't really reference
 296          memory.  The second operand may be referenced, though.  */
 297       mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
 298       mark_referenced_resources (XEXP (x, 1), res, 0);
 299       return;
 300
 301     case SET:
 302       /* Usually, the first operand of SET is set, not referenced.  But
 303          registers used to access memory are referenced.  SET_DEST is
 304          also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT.  */
 305
 306       mark_referenced_resources (SET_SRC (x), res, 0);
 307
 308       x = SET_DEST (x);
 309       if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
 310         mark_referenced_resources (x, res, 0);
 311       else if (GET_CODE (x) == SUBREG)
 312         x = SUBREG_REG (x);
 313       if (GET_CODE (x) == MEM)
 314         mark_referenced_resources (XEXP (x, 0), res, 0);
 315       return;
 316
 317     case CLOBBER:
 318       return;
 319
 320     case CALL_INSN:
 321       if (include_called_routine)
 322         {
 323           /* A CALL references memory, the frame pointer if it exists, the
 324              stack pointer, any global registers and any registers given in
 325              USE insns immediately in front of the CALL.
 326
 327              However, we may have moved some of the parameter loading insns
 328              into the delay slot of this CALL.  If so, the USE's for them
 329              don't count and should be skipped.  */
 330           rtx insn = PREV_INSN (x);
 331           rtx sequence = 0;
 332           int seq_size = 0;
 333           int i;
 334
 335           /* If we are part of a delay slot sequence, point at the SEQUENCE. */
 336           if (NEXT_INSN (insn) != x)
 337             {
 338               sequence = PATTERN (NEXT_INSN (insn));
 339               seq_size = XVECLEN (sequence, 0);
 340               if (GET_CODE (sequence) != SEQUENCE)
 341                 abort ();
 342             }
 343
 344           res->memory = 1;
 345           SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
 346           if (frame_pointer_needed)
 347             SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
 348
 349           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 350             if (global_regs[i])
 351               SET_HARD_REG_BIT (res->regs, i);
 352
 353           /* Skip any labels between the CALL_INSN and possible USE insns.  */
 354           while (GET_CODE (insn) == CODE_LABEL)
 355             insn = PREV_INSN (insn);
 356
 357           for ( ; (insn && GET_CODE (insn) == INSN
 358                    && GET_CODE (PATTERN (insn)) == USE);
 359                insn = PREV_INSN (insn))
 360             {
 361               for (i = 1; i < seq_size; i++)
 362                 {
 363                   rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
 364                   if (GET_CODE (slot_pat) == SET
 365                       && rtx_equal_p (SET_DEST (slot_pat),
 366                                       XEXP (PATTERN (insn), 0)))
 367                     break;
 368                 }
 369               if (i >= seq_size)
 370                 mark_referenced_resources (XEXP (PATTERN (insn), 0), res, 0);
 371             }
 372         }
 373
 374       /* ... fall through to other INSN procesing ... */
 375
 376     case INSN:
 377     case JUMP_INSN:
 378       /* No special processing, just speed up.  */
 379       mark_referenced_resources (PATTERN (x), res, include_called_routine);
 380       return;
 381     }
 382
 383   /* Process each sub-expression and flag what it needs.  */
 384   format_ptr = GET_RTX_FORMAT (code);
 385   for (i = 0; i < GET_RTX_LENGTH (code); i++)
 386     switch (*format_ptr++)
 387       {
 388       case 'e':
 389         mark_referenced_resources (XEXP (x, i), res, include_called_routine);
 390         break;
 391
 392       case 'E':
 393         for (j = 0; j < XVECLEN (x, i); j++)
 394           mark_referenced_resources (XVECEXP (x, i, j), res,
 395                                      include_called_routine);
 396         break;
 397       }
 398 }
 399 \f
 400 /* Given an insn, INSN, and a pointer to a `struct resource', RES, indicate
 401    which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
 402    is TRUE, also mark resources potentially set by the called routine.
 403
 404    We never mark the insn as modifying the condition code unless it explicitly
 405    SETs CC0 even though this is not totally correct.  The reason for this is
 406    that we require a SET of CC0 to immediately preceed the reference to CC0.
 407    So if some other insn sets CC0 as a side-effect, we know it cannot affect
 408    our computation and thus may be placed in a delay slot.   */
 409
 410 static void
 411 mark_set_resources (insn, res, include_called_routine)
 412      register rtx insn;
 413      register struct resources *res;
 414      int include_called_routine;
 415 {
 416   register int i;
 417
 418   switch (GET_CODE (insn))
 419     {
 420     case NOTE:
 421     case BARRIER:
 422     case CODE_LABEL:
 423       /* These don't set any resources.  */
 424       return;
 425
 426     case CALL_INSN:
 427       /* Called routine modifies the condition code, memory, any registers
 428          that aren't saved across calls, global registers and anything
 429          explicitly CLOBBERed immediately after the CALL_INSN.  */
 430
 431       if (include_called_routine)
 432         {
 433           rtx next = NEXT_INSN (insn);
 434
 435           res->cc = res->memory = 1;
 436           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 437             if (call_used_regs[i] || global_regs[i])
 438               SET_HARD_REG_BIT (res->regs, i);
 439
 440           /* Skip any possible labels between the CALL_INSN and CLOBBERs.  */
 441           while (GET_CODE (next) == CODE_LABEL)
 442             next = NEXT_INSN (next);
 443
 444           for (; (next && GET_CODE (next) == INSN
 445                   && GET_CODE (PATTERN (next)) == CLOBBER);
 446                next = NEXT_INSN (next))
 447             mark_referenced_resources (XEXP (PATTERN (next), 0), res, 0);
 448         }
 449
 450       /* ... and also what it's RTL says it modifies, if anything.  */
 451
 452     case JUMP_INSN:
 453     case INSN:
 454       {
 455         register rtx body = PATTERN (insn);
 456         register rtx note;
 457
 458         /* An insn consisting of just a CLOBBER (or USE) is
 459            just for flow and doesn't actually do anything, so we don't check
 460            for it.
 461
 462            If the source of a SET is a CALL, this is actually done by
 463            the called routine.  So only include it if we are to include the
 464            effects of the calling routine.  */
 465
 466         if (GET_CODE (body) == SET
 467             && (include_called_routine || GET_CODE (SET_SRC (body)) != CALL))
 468           mark_referenced_resources (SET_DEST (body), res, 0);
 469         else if (GET_CODE (body) == PARALLEL)
 470           {
 471             for (i = 0; i < XVECLEN (body, 0); i++)
 472               if ((GET_CODE (XVECEXP (body, 0, i)) == SET
 473                    && (include_called_routine
 474                        || GET_CODE (SET_SRC (XVECEXP (body, 0, i))) != CALL))
 475                   || GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
 476                 mark_referenced_resources (SET_DEST (XVECEXP (body, 0, i)),
 477                                            res, 0);
 478           }
 479         else if (GET_CODE (body) == SEQUENCE)
 480           for (i = 0; i < XVECLEN (body, 0); i++)
 481             if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (body, 0, 0))
 482                    && INSN_FROM_TARGET_P (XVECEXP (body, 0, i))))
 483               mark_set_resources (XVECEXP (body, 0, i), res,
 484                                   include_called_routine);
 485
 486 #ifdef AUTO_INC_DEC
 487         /* If any register are incremented or decremented in an address,
 488            they are set here.  */
 489         for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 490           if (REG_NOTE_KIND (note) == REG_INC)
 491             mark_referenced_resources (XEXP (note, 0), res, 0);
 492 #endif
 493
 494 #ifdef PUSH_ROUNDING
 495         /* An insn that has a PRE_DEC on SP will not have a REG_INC note.
 496            Until we fix this correctly, consider all insns as modifying
 497            SP on such machines.  So far, we don't have delay slot scheduling
 498            on any machines with PUSH_ROUNDING.  */
 499         SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
 500 #endif
 501         return;
 502       }
 503
 504     default:
 505       abort ();
 506     }
 507 }
 508 \f
 509 /* Return TRUE if this insn should stop the search for insn to fill delay
 510    slots.  LABELS_P indicates that labels should terminate the search.
 511    In all cases, jumps terminate the search.  */
 512
 513 static int
 514 stop_search_p (insn, labels_p)
 515      rtx insn;
 516      int labels_p;
 517 {
 518   if (insn == 0)
 519     return 1;
 520
 521   switch (GET_CODE (insn))
 522     {
 523     case NOTE:
 524     case CALL_INSN:
 525       return 0;
 526
 527     case CODE_LABEL:
 528       return labels_p;
 529
 530     case JUMP_INSN:
 531     case BARRIER:
 532       return 1;
 533
 534     case INSN:
 535       /* OK unless it contains a delay slot or is an `asm' insn of some type.
 536          We don't know anything about these.  */
 537       return (GET_CODE (PATTERN (insn)) == SEQUENCE
 538               || GET_CODE (PATTERN (insn)) == ASM_INPUT
 539               || asm_noperands (PATTERN (insn)) >= 0);
 540
 541     default:
 542       abort ();
 543     }
 544 }
 545 \f
 546 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
 547    resource set contains a volatile memory reference.  Otherwise, return FALSE.  */
 548
 549 static int
 550 resource_conflicts_p (res1, res2)
 551      struct resources *res1, *res2;
 552 {
 553   if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
 554       || res1->volatil || res2->volatil)
 555     return 1;
 556
 557 #ifdef HARD_REG_SET
 558   return (res1->regs & res2->regs) != HARD_CONST (0);
 559 #else
 560   {
 561     int i;
 562
 563     for (i = 0; i < HARD_REG_SET_LONGS; i++)
 564       if ((res1->regs[i] & res2->regs[i]) != 0)
 565         return 1;
 566     return 0;
 567   }
 568 #endif
 569 }
 570
 571 /* Return TRUE if any resource marked in RES, a `struct resources', is
 572    referenced by INSN.  If INCLUDE_CALLED_ROUTINE is set, return if the called
 573    routine is using those resources.
 574
 575    We compute this by computing all the resources referenced by INSN and
 576    seeing if this conflicts with RES.  It might be faster to directly check
 577    ourselves, and this is the way it used to work, but it means duplicating
 578    a large block of complex code.  */
 579
 580 static int
 581 insn_references_resource_p (insn, res, include_called_routine)
 582      register rtx insn;
 583      register struct resources *res;
 584      int include_called_routine;
 585 {
 586   struct resources insn_res;
 587
 588   CLEAR_RESOURCE (&insn_res);
 589   mark_referenced_resources (insn, &insn_res, include_called_routine);
 590   return resource_conflicts_p (&insn_res, res);
 591 }
 592
 593 /* Return TRUE if INSN modifies resources that are marked in RES.
 594    INCLUDE_CALLED_ROUTINE is set if the actions of that routine should be
 595    included.   CC0 is only modified if it is explicitly set; see comments
 596    in front of mark_set_resources for details.  */
 597
 598 static int
 599 insn_sets_resource_p (insn, res, include_called_routine)
 600      register rtx insn;
 601      register struct resources *res;
 602      int include_called_routine;
 603 {
 604   struct resources insn_sets;
 605
 606   CLEAR_RESOURCE (&insn_sets);
 607   mark_set_resources (insn, &insn_sets, include_called_routine);
 608   return resource_conflicts_p (&insn_sets, res);
 609 }
 610 \f
 611 /* Find a label at the end of the function or before a RETURN.  If there is
 612    none, make one.  */
 613
 614 static rtx
 615 find_end_label ()
 616 {
 617   rtx insn;
 618
 619   /* If we found one previously, return it.  */
 620   if (end_of_function_label)
 621     return end_of_function_label;
 622
 623   /* Otherwise, see if there is a label at the end of the function.  If there
 624      is, it must be that RETURN insns aren't needed, so that is our return
 625      label and we don't have to do anything else.  */
 626
 627   insn = get_last_insn ();
 628   while (GET_CODE (insn) == NOTE
 629          || (GET_CODE (insn) == INSN
 630              && (GET_CODE (PATTERN (insn)) == USE
 631                  || GET_CODE (PATTERN (insn)) == CLOBBER)))
 632     insn = PREV_INSN (insn);
 633
 634   if (GET_CODE (insn) == CODE_LABEL)
 635    end_of_function_label = insn;
 636   else
 637     {
 638       /* Otherwise, make a new label and emit a RETURN and BARRIER,
 639          if needed.  */
 640       end_of_function_label = gen_label_rtx ();
 641       LABEL_NUSES (end_of_function_label) = 0;
 642       emit_label (end_of_function_label);
 643 #ifdef HAVE_return
 644       if (HAVE_return)
 645         {
 646           emit_jump_insn (gen_return ());
 647           emit_barrier ();
 648         }
 649 #endif
 650     }
 651
 652   /* Show one additional use for this label so it won't go away until
 653      we are done.  */
 654   ++LABEL_NUSES (end_of_function_label);
 655
 656   return end_of_function_label;
 657 }
 658 \f
 659 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
 660    the pattern of INSN with the SEQUENCE.
 661
 662    Chain the insns so that NEXT_INSN of each insn in the sequence points to
 663    the next and NEXT_INSN of the last insn in the sequence points to
 664    the first insn after the sequence.  Similarly for PREV_INSN.  This makes
 665    it easier to scan all insns.
 666
 667    Returns the SEQUENCE that replaces INSN.  */
 668
 669 static rtx
 670 emit_delay_sequence (insn, list, length, avail)
 671      rtx insn;
 672      rtx list;
 673      int length;
 674      int avail;
 675 {
 676   register int i = 1;
 677   register rtx li;
 678   int had_barrier = 0;
 679
 680   /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
 681   rtvec seqv = rtvec_alloc (length + 1);
 682   rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
 683   rtx seq_insn = make_insn_raw (seq);
 684   rtx first = get_insns ();
 685   rtx last = get_last_insn ();
 686
 687   /* Make a copy of the insn having delay slots. */
 688   rtx delay_insn = copy_rtx (insn);
 689
 690   /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
 691      confuse further processing.  Update LAST in case it was the last insn.
 692      We will put the BARRIER back in later.  */
 693   if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
 694     {
 695       delete_insn (NEXT_INSN (insn));
 696       last = get_last_insn ();
 697       had_barrier = 1;
 698     }
 699
 700   /* Splice our SEQUENCE into the insn stream where INSN used to be.  */
 701   NEXT_INSN (seq_insn) = NEXT_INSN (insn);
 702   PREV_INSN (seq_insn) = PREV_INSN (insn);
 703
 704   if (insn == last)
 705     set_new_first_and_last_insn (first, seq_insn);
 706   else
 707     PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
 708
 709   if (insn == first)
 710     set_new_first_and_last_insn (seq_insn, last);
 711   else
 712     NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
 713
 714   /* Build our SEQUENCE and rebuild the insn chain.  */
 715   XVECEXP (seq, 0, 0) = delay_insn;
 716   INSN_DELETED_P (delay_insn) = 0;
 717   PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
 718
 719   for (li = list; li; li = XEXP (li, 1), i++)
 720     {
 721       rtx tem = XEXP (li, 0);
 722       rtx note;
 723
 724       /* Show that this copy of the insn isn't deleted.  */
 725       INSN_DELETED_P (tem) = 0;
 726
 727       XVECEXP (seq, 0, i) = tem;
 728       PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
 729       NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
 730
 731       /* Remove any REG_DEAD notes because we can't rely on them now
 732          that the insn has been moved.  */
 733       for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
 734         if (REG_NOTE_KIND (note) == REG_DEAD)
 735           XEXP (note, 0) = const0_rtx;
 736     }
 737
 738   NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
 739
 740   /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
 741      last insn in that SEQUENCE to point to us.  Similarly for the first
 742      insn in the following insn if it is a SEQUENCE.  */
 743
 744   if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
 745       && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
 746     NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
 747                         XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
 748       = seq_insn;
 749
 750   if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
 751       && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
 752     PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
 753
 754   /* If there used to be a BARRIER, put it back.  */
 755   if (had_barrier)
 756     emit_barrier_after (seq_insn);
 757
 758   if (i != length + 1)
 759     abort ();
 760
 761   return seq_insn;
 762 }
 763
 764 /* Add INSN to DELAY_LIST and return the head of the new list.  The list must
 765    be in the order in which the insns are to be executed.  */
 766
 767 static rtx
 768 add_to_delay_list (insn, delay_list)
 769      rtx insn;
 770      rtx delay_list;
 771 {
 772   /* If we have an empty list, just make a new list element.  */
 773   if (delay_list == 0)
 774     return gen_rtx (INSN_LIST, VOIDmode, insn, 0);
 775
 776   /* Otherwise this must be an INSN_LIST.  Add INSN to the end of the
 777      list.  */
 778   XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
 779
 780   return delay_list;
 781 }
 782
 783 #ifdef HAVE_cc0
 784 /* INSN uses CC0 and is being moved into a delay slot.  Set up REG_CC_SETTER
 785    and REG_CC_USER notes so we can find it.  */
 786
 787 static void
 788 link_cc0_insns (insn)
 789      rtx insn;
 790 {
 791   rtx user = next_nonnote_insn (insn);
 792
 793   if (GET_CODE (user) == INSN && GET_CODE (PATTERN (user)) == SEQUENCE)
 794     user = XVECEXP (PATTERN (user), 0, 0);
 795
 796   REG_NOTES (user) = gen_rtx (INSN_LIST, REG_CC_SETTER, insn,
 797                               REG_NOTES (user));
 798   REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_CC_USER, user, REG_NOTES (insn));
 799 }
 800 #endif
 801 \f
 802 /* Delete INSN from the the delay slot of the insn that it is in.  This may
 803    produce an insn without anything in its delay slots.  */
 804
 805 static void
 806 delete_from_delay_slot (insn)
 807      rtx insn;
 808 {
 809   rtx trial, seq_insn, seq, prev;
 810   rtx delay_list = 0;
 811   int i;
 812
 813   /* We first must find the insn containing the SEQUENCE with INSN in its
 814      delay slot.  Do this by finding an insn, TRIAL, where
 815      PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL.  */
 816
 817   for (trial = insn;
 818        PREV_INSN (NEXT_INSN (trial)) == trial;
 819        trial = NEXT_INSN (trial))
 820     ;
 821
 822   seq_insn = PREV_INSN (NEXT_INSN (trial));
 823   seq = PATTERN (seq_insn);
 824
 825   /* Create a delay list consisting of all the insns other than the one
 826      we are deleting (unless we were the only one).  */
 827   if (XVECLEN (seq, 0) > 2)
 828     for (i = 1; i < XVECLEN (seq, 0); i++)
 829       if (XVECEXP (seq, 0, i) != insn)
 830         delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
 831
 832   /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
 833      list, and rebuild the delay list if non-empty.  */
 834   prev = PREV_INSN (seq_insn);
 835   trial = XVECEXP (seq, 0, 0);
 836   delete_insn (seq_insn);
 837   add_insn_after (trial, prev);
 838
 839   if (GET_CODE (trial) == JUMP_INSN
 840       && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
 841     emit_barrier_after (trial);
 842
 843   /* If there are any delay insns, remit them.  Otherwise clear the
 844      annul flag.  */
 845   if (delay_list)
 846     trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2, 0);
 847   else
 848     INSN_ANNULLED_BRANCH_P (trial) = 0;
 849
 850   INSN_FROM_TARGET_P (insn) = 0;
 851
 852   /* Show we need to fill this insn again.  */
 853   obstack_ptr_grow (&unfilled_slots_obstack, trial);
 854 }
 855 \f
 856 /* Delete INSN, a JUMP_INSN.  If it is a conditional jump, we must track down
 857    the insn that sets CC0 for it and delete it too.  */
 858
 859 static void
 860 delete_scheduled_jump (insn)
 861      rtx insn;
 862 {
 863   /* Delete the insn that sets cc0 for us.  On machines without cc0, we could
 864      delete the insn that sets the condition code, but it is hard to find it.
 865      Since this case is rare anyway, don't bother trying; there would likely
 866      be other insns that became dead anyway, which we wouldn't know to
 867      delete.  */
 868
 869 #ifdef HAVE_cc0
 870   if (reg_mentioned_p (cc0_rtx, insn))
 871     {
 872       rtx note = find_reg_note (insn, REG_CC_SETTER, 0);
 873
 874       /* If a reg-note was found, it points to an insn to set CC0.  This
 875          insn is in the delay list of some other insn.  So delete it from
 876          the delay list it was in.  */
 877       if (note)
 878         {
 879           if (! FIND_REG_INC_NOTE (XEXP (note, 0), 0)
 880               && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
 881             delete_from_delay_slot (XEXP (note, 0));
 882         }
 883       else
 884         {
 885           /* The insn setting CC0 is our previous insn, but it may be in
 886              a delay slot.  It will be the last insn in the delay slot, if
 887              it is.  */
 888           rtx trial = previous_insn (insn);
 889           if (GET_CODE (trial) == NOTE)
 890             trial = prev_nonnote_insn (trial);
 891           if (sets_cc0_p (PATTERN (trial)) != 1
 892               || FIND_REG_INC_NOTE (trial, 0))
 893             return;
 894           if (PREV_INSN (NEXT_INSN (trial)) == trial)
 895             delete_insn (trial);
 896           else
 897             delete_from_delay_slot (trial);
 898         }
 899     }
 900 #endif
 901
 902   delete_insn (insn);
 903 }
 904 \f
 905 /* Counters for delay-slot filling.  */
 906
 907 #define NUM_REORG_FUNCTIONS 2
 908 #define MAX_DELAY_HISTOGRAM 3
 909 #define MAX_REORG_PASSES 2
 910
 911 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
 912
 913 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
 914
 915 static int reorg_pass_number;
 916
 917 static void
 918 note_delay_statistics (slots_filled, index)
 919      int slots_filled, index;
 920 {
 921   num_insns_needing_delays[index][reorg_pass_number]++;
 922   if (slots_filled > MAX_DELAY_HISTOGRAM)
 923     slots_filled = MAX_DELAY_HISTOGRAM;
 924   num_filled_delays[index][slots_filled][reorg_pass_number]++;
 925 }
 926 \f
 927 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
 928
 929 /* Optimize the following cases:
 930
 931    1.  When a conditional branch skips over only one instruction,
 932        use an annulling branch and put that insn in the delay slot.
 933        Use either a branch that annulls when the condition if true or
 934        invert the test with a branch that annulls when the condition is
 935        false.  This saves insns, since otherwise we must copy an insn
 936        from the L1 target.
 937
 938         (orig)           (skip)         (otherwise)
 939         Bcc.n L1        Bcc',a L1       Bcc,a L1'
 940         insn            insn            insn2
 941       L1:             L1:             L1:
 942         insn2           insn2           insn2
 943         insn3           insn3         L1':
 944                                         insn3
 945
 946    2.  When a conditional branch skips over only one instruction,
 947        and after that, it unconditionally branches somewhere else,
 948        perform the similar optimization. This saves executing the
 949        second branch in the case where the inverted condition is true.
 950
 951         Bcc.n L1        Bcc',a L2
 952         insn            insn
 953       L1:             L1:
 954         Bra L2          Bra L2
 955
 956    INSN is a JUMP_INSN.
 957
 958    This should be expanded to skip over N insns, where N is the number
 959    of delay slots required.  */
 960
 961 static rtx
 962 optimize_skip (insn)
 963      register rtx insn;
 964 {
 965   register rtx trial = next_nonnote_insn (insn);
 966   rtx next_trial = next_active_insn (trial);
 967   rtx delay_list = 0;
 968   rtx target_label;
 969
 970   if (trial == 0
 971       || GET_CODE (trial) != INSN
 972       || GET_CODE (PATTERN (trial)) == SEQUENCE
 973       || recog_memoized (trial) < 0
 974       || (! eligible_for_annul_false (insn, 0, trial)
 975           && ! eligible_for_annul_true (insn, 0, trial)))
 976     return 0;
 977
 978   /* There are two cases where we are just executing one insn (we assume
 979      here that a branch requires only one insn; this should be generalized
 980      at some point):  Where the branch goes around a single insn or where
 981      we have one insn followed by a branch to the same label we branch to.
 982      In both of these cases, inverting the jump and annulling the delay
 983      slot give the same effect in fewer insns.  */
 984   if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
 985       || (next_trial != 0
 986           && GET_CODE (next_trial) == JUMP_INSN
 987           && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
 988           && (simplejump_p (next_trial)
 989               || GET_CODE (PATTERN (next_trial)) == RETURN)))
 990     {
 991       if (eligible_for_annul_false (insn, 0, trial))
 992         {
 993           if (invert_jump (insn, JUMP_LABEL (insn)))
 994             INSN_FROM_TARGET_P (trial) = 1;
 995           else if (! eligible_for_annul_true (insn, 0, trial))
 996             return 0;
 997         }
 998
 999       delay_list = add_to_delay_list (trial, 0);
1000       next_trial = next_active_insn (trial);
1001       update_block (trial, trial);
1002       delete_insn (trial);
1003
1004       /* Also, if we are targeting an unconditional
1005          branch, thread our jump to the target of that branch.  Don't
1006          change this into a RETURN here, because it may not accept what
1007          we have in the delay slot.  We'll fix this up later.  */
1008       if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1009           && (simplejump_p (next_trial)
1010               || GET_CODE (PATTERN (next_trial)) == RETURN))
1011         {
1012           target_label = JUMP_LABEL (next_trial);
1013           if (target_label == 0)
1014             target_label = find_end_label ();
1015           redirect_jump (insn, target_label);
1016         }
1017
1018       INSN_ANNULLED_BRANCH_P (insn) = 1;
1019     }
1020
1021   return delay_list;
1022 }
1023 #endif
1024 \f
1025 /* Return truth value of the statement that this branch
1026    is mostly taken.  If we think that the branch is extremely likely
1027    to be taken, we return 2.  If the branch is slightly more likely to be
1028    taken, return 1.  Otherwise, return 0.
1029
1030    CONDITION, if non-zero, is the condition that JUMP_INSN is testing.  */
1031
1032 static int
1033 mostly_true_jump (jump_insn, condition)
1034      rtx jump_insn, condition;
1035 {
1036   rtx target_label = JUMP_LABEL (jump_insn);
1037   rtx insn;
1038
1039   /* If this is a conditional return insn, assume it won't return.  */
1040   if (target_label == 0)
1041     return 0;
1042
1043   /* If TARGET_LABEL has no jumps between it and the end of the function,
1044      this is essentially a conditional return, so predict it as false.  */
1045   for (insn = NEXT_INSN (target_label);
1046        insn && GET_CODE (insn) != JUMP_INSN;
1047        insn = NEXT_INSN (insn))
1048     ;
1049
1050   if (insn == 0)
1051     return 0;
1052
1053   /* If this is the test of a loop, it is very likely true.  We scan backwards
1054      from the target label.  If we find a NOTE_INSN_LOOP_BEG before the next
1055      real insn, we assume the branch is to the top of the loop.  */
1056   for (insn = PREV_INSN (target_label);
1057        insn && GET_CODE (insn) == NOTE;
1058        insn = PREV_INSN (insn))
1059     if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1060       return 2;
1061
1062   /* If we couldn't figure out what this jump was, assume it won't be
1063      taken.  This should be rare.  */
1064   if (condition == 0)
1065     return 0;
1066
1067   /* EQ tests are usually false and NE tests are usually true.  Also,
1068      most quantities are positive, so we can make the appropriate guesses
1069      about signed comparisons against zero.  */
1070   switch (GET_CODE (condition))
1071     {
1072     case CONST_INT:
1073       /* Unconditional branch.  */
1074       return 1;
1075     case EQ:
1076       return 0;
1077     case NE:
1078       return 1;
1079     case LE:
1080     case LT:
1081       if (XEXP (condition, 1) == const0_rtx)
1082         return 0;
1083       break;
1084     case GE:
1085     case GT:
1086       if (XEXP (condition, 1) == const0_rtx)
1087         return 1;
1088       break;
1089     }
1090
1091   /* Predict backward branches usually take, forward branches usually not.  If
1092      we don't know whether this is forward or backward, assume the branch
1093      will be taken, since most are.  */
1094   return (INSN_UID (jump_insn) > max_uid || INSN_UID (target_label) > max_uid
1095           || (uid_to_ruid[INSN_UID (jump_insn)]
1096               > uid_to_ruid[INSN_UID (target_label)]));;
1097 }
1098
1099 /* Return the condition under which INSN will branch to TARGET.  If TARGET
1100    is zero, return the condition under which INSN will return.  If INSN is
1101    an unconditional branch, return const_true_rtx.  If INSN isn't a simple
1102    type of jump, or it doesn't go to TARGET, return 0.  */
1103
1104 static rtx
1105 get_branch_condition (insn, target)
1106      rtx insn;
1107      rtx target;
1108 {
1109   rtx pat = PATTERN (insn);
1110   rtx src;
1111
1112   if (GET_CODE (pat) == RETURN)
1113     return target == 0 ? const_true_rtx : 0;
1114
1115   else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1116     return 0;
1117
1118   src = SET_SRC (pat);
1119   if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1120     return const_true_rtx;
1121
1122   else if (GET_CODE (src) == IF_THEN_ELSE
1123            && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1124                || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1125                    && XEXP (XEXP (src, 1), 0) == target))
1126            && XEXP (src, 2) == pc_rtx)
1127     return XEXP (src, 0);
1128
1129   else if (GET_CODE (src) == IF_THEN_ELSE
1130            && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1131                || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1132                    && XEXP (XEXP (src, 2), 0) == target))
1133            && XEXP (src, 1) == pc_rtx)
1134     return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
1135                     GET_MODE (XEXP (src, 0)),
1136                     XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1137 }
1138
1139 /* Return non-zero if CONDITION is more strict than the condition of
1140    INSN, i.e., if INSN will always branch if CONDITION is true.  */
1141
1142 static int
1143 condition_dominates_p (condition, insn)
1144      rtx condition;
1145      rtx insn;
1146 {
1147   rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1148   enum rtx_code code = GET_CODE (condition);
1149   enum rtx_code other_code;
1150
1151   if (rtx_equal_p (condition, other_condition)
1152       || other_condition == const_true_rtx)
1153     return 1;
1154
1155   else if (condition == const_true_rtx || other_condition == 0)
1156     return 0;
1157
1158   other_code = GET_CODE (other_condition);
1159   if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1160       || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1161       || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1162     return 0;
1163
1164   return comparison_dominates_p (code, other_code);
1165 }
1166 \f
1167 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE.  Given that
1168    the condition tested by INSN is CONDITION and the resources shown in
1169    OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1170    from SEQ's delay list, in addition to whatever insns it may execute
1171    (in DELAY_LIST).   SETS and NEEDED are denote resources already set and
1172    needed while searching for delay slot insns.  Return the concatenated
1173    delay list if possible, otherwise, return 0.
1174
1175    SLOTS_TO_FILL is the total number of slots required by INSN, and
1176    PSLOTS_FILLED points to the number filled so far (also the number of
1177    insns in DELAY_LIST).  It is updated with the number that have been
1178    filled from the SEQUENCE, if any.
1179
1180    PANNUL_P points to a non-zero value if we already know that we need
1181    to annul INSN.  If this routine determines that annulling is needed,
1182    it may set that value non-zero.
1183
1184    PNEW_THREAD points to a location that is to receive the place at which
1185    execution should continue.  */
1186
1187 static rtx
1188 steal_delay_list_from_target (insn, condition, seq, delay_list,
1189                               sets, needed, other_needed,
1190                               slots_to_fill, pslots_filled, pannul_p,
1191                               pnew_thread)
1192      rtx insn, condition;
1193      rtx seq;
1194      rtx delay_list;
1195      struct resources *sets, *needed, *other_needed;
1196      int slots_to_fill;
1197      int *pslots_filled;
1198      int *pannul_p;
1199      rtx *pnew_thread;
1200 {
1201   rtx temp;
1202   int slots_remaining = slots_to_fill - *pslots_filled;
1203   int total_slots_filled = *pslots_filled;
1204   rtx new_delay_list = 0;
1205   int must_annul = *pannul_p;
1206   int i;
1207
1208   /* We can't do anything if there are more delay slots in SEQ than we
1209      can handle, or if we don't know that it will be a taken branch.
1210
1211      We know that it will be a taken branch if it is either an unconditional
1212      branch or a conditional branch with a stricter branch condition.  */
1213
1214   if (XVECLEN (seq, 0) - 1 > slots_remaining
1215       || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0)))
1216     return delay_list;
1217
1218   for (i = 1; i < XVECLEN (seq, 0); i++)
1219     {
1220       rtx trial = XVECEXP (seq, 0, i);
1221
1222       if (insn_references_resource_p (trial, sets, 0)
1223           || insn_sets_resource_p (trial, needed, 0)
1224           || insn_sets_resource_p (trial, sets, 0)
1225 #ifdef HAVE_cc0
1226           /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1227              delay list.  */
1228           || find_reg_note (trial, REG_CC_USER, 0)
1229 #endif
1230           /* If TRIAL is from the fallthrough code of an annulled branch insn
1231              in SEQ, we cannot use it.  */
1232           || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1233               && ! INSN_FROM_TARGET_P (trial)))
1234         return delay_list;
1235
1236       /* If this insn was already done (usually in a previous delay slot),
1237          pretend we put it in our delay slot.  */
1238       if (redundant_insn_p (trial, insn, new_delay_list))
1239         continue;
1240
1241       if (! must_annul
1242           && ((condition == const_true_rtx
1243                || (! insn_sets_resource_p (trial, other_needed, 0)
1244                    && ! may_trap_p (PATTERN (trial)))))
1245           ? eligible_for_delay (insn, total_slots_filled, trial)
1246           : (must_annul = 1,
1247              eligible_for_annul_false (insn, total_slots_filled, trial)))
1248         {
1249           temp = copy_rtx (trial);
1250           INSN_FROM_TARGET_P (temp) = 1;
1251           new_delay_list = add_to_delay_list (temp, new_delay_list);
1252           total_slots_filled++;
1253
1254           if (--slots_remaining == 0)
1255             break;
1256         }
1257       else
1258         return delay_list;
1259     }
1260
1261   /* Show the place to which we will be branching.  */
1262   *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1263
1264   /* Add any new insns to the delay list and update the count of the
1265      number of slots filled.  */
1266   *pslots_filled = total_slots_filled;
1267   *pannul_p = must_annul;
1268
1269   if (delay_list == 0)
1270     return new_delay_list;
1271
1272   for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1273     delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1274
1275   return delay_list;
1276 }
1277 \f
1278 /* Similar to steal_delay_list_from_target except that SEQ is on the
1279    fallthrough path of INSN.  Here we only do something if the delay insn
1280    of SEQ is an unconditional branch.  In that case we steal its delay slot
1281    for INSN since unconditional branches are much easier to fill.  */
1282
1283 static rtx
1284 steal_delay_list_from_fallthrough (insn, condition, seq,
1285                                    delay_list, sets, needed, other_needed,
1286                                    slots_to_fill, pslots_filled, pannul_p)
1287      rtx insn, condition;
1288      rtx seq;
1289      rtx delay_list;
1290      struct resources *sets, *needed, *other_needed;
1291      int slots_to_fill;
1292      int *pslots_filled;
1293      int *pannul_p;
1294 {
1295   int i;
1296
1297   /* We can't do anything if SEQ's delay insn isn't an
1298      unconditional branch.  */
1299
1300   if (! simplejump_p (XVECEXP (seq, 0, 0))
1301       && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1302     return delay_list;
1303
1304   for (i = 1; i < XVECLEN (seq, 0); i++)
1305     {
1306       rtx trial = XVECEXP (seq, 0, i);
1307
1308       /* If TRIAL sets CC0, stealing it will move it too far from the use
1309          of CC0.  */
1310       if (insn_references_resource_p (trial, sets, 0)
1311           || insn_sets_resource_p (trial, needed, 0)
1312           || insn_sets_resource_p (trial, sets, 0)
1313 #ifdef HAVE_cc0
1314           || sets_cc0_p (PATTERN (trial))
1315 #endif
1316           )
1317
1318         break;
1319
1320       /* If this insn was already done, we don't need it.  */
1321       if (redundant_insn_p (trial, insn, delay_list))
1322         {
1323           delete_from_delay_slot (trial);
1324           continue;
1325         }
1326
1327       if (! *pannul_p
1328           && ((condition == const_true_rtx
1329                || (! insn_sets_resource_p (trial, other_needed, 0)
1330                    && ! may_trap_p (PATTERN (trial)))))
1331           ? eligible_for_delay (insn, *pslots_filled, trial)
1332           : (*pannul_p = 1,
1333              eligible_for_annul_true (insn, *pslots_filled, trial)))
1334         {
1335           delete_from_delay_slot (trial);
1336           delay_list = add_to_delay_list (trial, delay_list);
1337
1338           if (++(*pslots_filled) == slots_to_fill)
1339             break;
1340         }
1341       else
1342         break;
1343     }
1344
1345   return delay_list;
1346 }
1347 \f
1348 /* Try merging insns starting at THREAD which match exactly the insns in
1349    INSN's delay list.
1350
1351    If all insns were matched and the insn was previously annulling, the
1352    annul bit will be cleared.
1353
1354    For each insn that is merged, if the branch is or will be non-annulling,
1355    we delete the merged insn.  */
1356
1357 static void
1358 try_merge_delay_insns (insn, thread)
1359      rtx insn, thread;
1360 {
1361   rtx trial, next_trial;
1362   rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1363   int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1364   int slot_number = 1;
1365   int num_slots = XVECLEN (PATTERN (insn), 0);
1366   rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1367   struct resources set, needed;
1368   rtx merged_insns = 0;
1369   int i;
1370
1371   CLEAR_RESOURCE (&needed);
1372   CLEAR_RESOURCE (&set);
1373
1374   /* If this is not an annulling branch, take into account anything needed in
1375      NEXT_TO_MATCH.  This prevents two increments from being incorrectly
1376      folded into one.  If we are annulling, this would be the correct
1377      thing to do.  (The alternative, looking at things set in NEXT_TO_MATCH
1378      will essentially disable this optimization.  This method is somewhat of
1379      a kludge, but I don't see a better way.)  */
1380   if (! annul_p)
1381     mark_referenced_resources (next_to_match, &needed, 1);
1382
1383   for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1384     {
1385       rtx pat = PATTERN (trial);
1386
1387       next_trial = next_nonnote_insn (trial);
1388
1389       /* TRIAL must be a CALL_INSN or INSN.  Skip USE and CLOBBER.  */
1390       if (GET_CODE (trial) == INSN
1391           && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1392         continue;
1393
1394       if (GET_CODE (next_to_match) == GET_CODE (trial)
1395 #ifdef HAVE_cc0
1396           /* We can't share an insn that sets cc0.  */
1397           && ! sets_cc0_p (pat)
1398 #endif
1399           && ! insn_references_resource_p (trial, &set, 1)
1400           && ! insn_sets_resource_p (trial, &set, 1)
1401           && ! insn_sets_resource_p (trial, &needed, 1)
1402           && (trial = try_split (pat, trial, 0)) != 0
1403           && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1404           /* Have to test this condition if annul condition is different
1405              from (and less restrictive than) non-annulling one.  */
1406           && eligible_for_delay (delay_insn, slot_number - 1, trial))
1407         {
1408           next_trial = next_nonnote_insn (trial);
1409
1410           if (! annul_p)
1411             {
1412               update_block (trial, thread);
1413               delete_insn (trial);
1414               INSN_FROM_TARGET_P (next_to_match) = 0;
1415             }
1416           else
1417             merged_insns = gen_rtx (INSN_LIST, VOIDmode, trial, merged_insns);
1418
1419           if (++slot_number == num_slots)
1420             break;
1421
1422           next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1423           if (! annul_p)
1424             mark_referenced_resources (next_to_match, &needed, 1);
1425         }
1426
1427       mark_set_resources (trial, &set, 1);
1428       mark_referenced_resources (trial, &needed, 1);
1429     }
1430
1431   /* See if we stopped on a filled insn.  If we did, try to see if its
1432      delay slots match.  */
1433   if (slot_number != num_slots
1434       && trial && GET_CODE (trial) == INSN
1435       && GET_CODE (PATTERN (trial)) == SEQUENCE
1436       && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1437     {
1438       rtx pat = PATTERN (trial);
1439
1440       for (i = 1; i < XVECLEN (pat, 0); i++)
1441         {
1442           rtx dtrial = XVECEXP (pat, 0, i);
1443
1444           if (! insn_references_resource_p (dtrial, &set, 1)
1445               && ! insn_sets_resource_p (dtrial, &set, 1)
1446               && ! insn_sets_resource_p (dtrial, &needed, 1)
1447 #ifdef HAVE_cc0
1448               && ! sets_cc0_p (PATTERN (dtrial))
1449 #endif
1450               && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1451               && eligible_for_delay (delay_insn, slot_number - 1, dtrial))
1452             {
1453               if (! annul_p)
1454                 {
1455                   update_block (dtrial, thread);
1456                   delete_from_delay_slot (dtrial);
1457                   INSN_FROM_TARGET_P (next_to_match) = 0;
1458                 }
1459               else
1460                 merged_insns = gen_rtx (INSN_LIST, SImode, dtrial,
1461                                         merged_insns);
1462
1463               if (++slot_number == num_slots)
1464                 break;
1465
1466               next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1467             }
1468         }
1469     }
1470
1471   /* If all insns in the delay slot have been matched and we were previously
1472      annulling the branch, we need not any more.  In that case delete all the
1473      merged insns.  Also clear the INSN_FROM_TARGET_P bit of each insn the
1474      the delay list so that we know that it isn't only being used at the
1475      target.  */
1476   if (next_to_match == 0 && annul_p)
1477     {
1478       for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1479         {
1480           if (GET_MODE (merged_insns) == SImode)
1481             {
1482               update_block (XEXP (merged_insns, 0), thread);
1483               delete_from_delay_slot (XEXP (merged_insns, 0));
1484             }
1485           else
1486             {
1487               update_block (XEXP (merged_insns, 0), thread);
1488               delete_insn (XEXP (merged_insns, 0));
1489             }
1490         }
1491
1492       INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1493
1494       for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1495         INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1496     }
1497 }
1498 \f
1499 /* See if INSN is redundant with an insn in front of TARGET.  Often this
1500    is called when INSN is a candidate for a delay slot of TARGET.
1501    DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1502    of INSN.  Often INSN will be redundant with an insn in a delay slot of
1503    some previous insn.  This happens when we have a series of branches to the
1504    same label; in that case the first insn at the target might want to go
1505    into each of the delay slots.
1506
1507    If we are not careful, this routine can take up a significant fraction
1508    of the total compilation time (4%), but only wins rarely.  Hence we
1509    speed this routine up by making two passes.  The first pass goes back
1510    until it hits a label and sees if it find an insn with an identical
1511    pattern.  Only in this (relatively rare) event does it check for
1512    data conflicts.
1513
1514    We do not split insns we encounter.  This could cause us not to find a
1515    redundant insn, but the cost of splitting seems greater than the possible
1516    gain in rare cases.  */
1517
1518 static int
1519 redundant_insn_p (insn, target, delay_list)
1520      rtx insn;
1521      rtx target;
1522      rtx delay_list;
1523 {
1524   rtx target_main = target;
1525   rtx ipat = PATTERN (insn);
1526   rtx trial, pat;
1527   struct resources needed, set;
1528   int i;
1529
1530   /* Scan backwards looking for a match.  */
1531   for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
1532     {
1533       if (GET_CODE (trial) == CODE_LABEL)
1534         return 0;
1535
1536       if (GET_CODE (trial) != INSN && GET_CODE (trial) != JUMP_INSN
1537           && GET_CODE (trial) != JUMP_INSN)
1538         continue;
1539
1540       pat = PATTERN (trial);
1541       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1542         continue;
1543
1544       if (GET_CODE (pat) == SEQUENCE)
1545         {
1546           /* Stop for a CALL and its delay slots because it difficult to track
1547              its resource needs correctly.  */
1548           if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1549             return 0;
1550
1551           for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1552             if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
1553                 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat))
1554               break;
1555
1556           /* If found a match, exit this loop early.  */
1557           if (i > 0)
1558             break;
1559         }
1560
1561       else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat))
1562         break;
1563     }
1564
1565   /* If we didn't find an insn that matches, return 0.  */
1566   if (trial == 0)
1567     return 0;
1568
1569   /* See what resources this insn sets and needs.  If they overlap, or
1570      if this insn references CC0, it can't be redundant.  */
1571
1572   CLEAR_RESOURCE (&needed);
1573   CLEAR_RESOURCE (&set);
1574   mark_set_resources (insn, &set, 1);
1575   mark_referenced_resources (insn, &needed, 1);
1576
1577   /* If TARGET is a SEQUENCE, get the main insn.  */
1578   if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1579     target_main = XVECEXP (PATTERN (target), 0, 0);
1580
1581   if (resource_conflicts_p (&needed, &set)
1582 #ifdef HAVE_cc0
1583       || reg_mentioned_p (cc0_rtx, ipat)
1584 #endif
1585       /* The insn requiring the delay may not set anything needed or set by
1586          INSN.  */
1587       || insn_sets_resource_p (target_main, &needed, 1)
1588       || insn_sets_resource_p (target_main, &set, 1))
1589     return 0;
1590
1591   /* Insns we pass may not set either NEEDED or SET, so merge them for
1592      simpler tests.  */
1593   needed.memory |= set.memory;
1594   IOR_HARD_REG_SET (needed.regs, set.regs);
1595
1596   /* This insn isn't redundant if it conflicts with an insn that either is
1597      or will be in a delay slot of TARGET.  */
1598
1599   while (delay_list)
1600     {
1601       if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
1602         return 0;
1603       delay_list = XEXP (delay_list, 1);
1604     }
1605
1606   if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1607     for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
1608       if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
1609         return 0;
1610
1611   /* Scan backwards until we reach a label or an insn that uses something
1612      INSN sets or sets something insn uses or sets.  */
1613
1614   for (trial = PREV_INSN (target);
1615        trial && GET_CODE (trial) != CODE_LABEL;
1616        trial = PREV_INSN (trial))
1617     {
1618       if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
1619           && GET_CODE (trial) != JUMP_INSN)
1620         continue;
1621
1622       pat = PATTERN (trial);
1623       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1624         continue;
1625
1626       if (GET_CODE (pat) == SEQUENCE)
1627         {
1628           /* If this is a CALL_INSN and its delay slots, it is hard to track
1629              the resource needs properly, so give up.  */
1630           if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1631             return 0;
1632
1633           /* See if any of the insns in the delay slot match, updating
1634              resource requirements as we go.  */
1635           for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1636             {
1637               rtx candidate = XVECEXP (pat, 0, i);
1638
1639               /* If an insn will be annulled if the branch is false, it isn't
1640                  considered as a possible duplicate insn.  */
1641               if (rtx_equal_p (PATTERN (candidate), ipat)
1642                   && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1643                         && INSN_FROM_TARGET_P (candidate)))
1644                 {
1645                   /* Show that this insn will be used in the sequel.  */
1646                   INSN_FROM_TARGET_P (candidate) = 0;
1647                   return 1;
1648                 }
1649
1650               /* Unless this is an annulled insn from the target of a branch,
1651                  we must stop if it sets anything needed or set by INSN.  */
1652               if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1653                    || ! INSN_FROM_TARGET_P (candidate))
1654                   && insn_sets_resource_p (candidate, &needed, 1))
1655                 return 0;
1656             }
1657
1658
1659           /* If the insn requiring the delay slot conflicts with INSN, we
1660              must stop.  */
1661           if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
1662             return 0;
1663         }
1664       else
1665         {
1666           /* See if TRIAL is the same as INSN.  */
1667           pat = PATTERN (trial);
1668           if (rtx_equal_p (pat, ipat))
1669             return 1;
1670
1671           /* Can't go any further if TRIAL conflicts with INSN.  */
1672           if (insn_sets_resource_p (trial, &needed, 1))
1673             return 0;
1674         }
1675     }
1676
1677   return 0;
1678 }
1679 \f
1680 /* Return 1 if THREAD can only be executed in one way.  If LABEL is non-zero,
1681    it is the target of the branch insn being scanned.  If ALLOW_FALLTHROUGH
1682    is non-zero, we are allowed to fall into this thread; otherwise, we are
1683    not.
1684
1685    If LABEL is used more than one or we pass a label other than LABEL before
1686    finding an active insn, we do not own this thread.  */
1687
1688 static int
1689 own_thread_p (thread, label, allow_fallthrough)
1690      rtx thread;
1691      rtx label;
1692      int allow_fallthrough;
1693 {
1694   rtx active_insn;
1695   rtx insn;
1696
1697   /* We don't own the function end.  */
1698   if (thread == 0)
1699     return 0;
1700
1701   /* Get the first active insn, or THREAD, if it is an active insn.  */
1702   active_insn = next_active_insn (PREV_INSN (thread));
1703
1704   for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
1705     if (GET_CODE (insn) == CODE_LABEL
1706         && (insn != label || LABEL_NUSES (insn) != 1))
1707       return 0;
1708
1709   if (allow_fallthrough)
1710     return 1;
1711
1712   /* Ensure that we reach a BARRIER before any insn or label.  */
1713   for (insn = prev_nonnote_insn (thread);
1714        insn == 0 || GET_CODE (insn) != BARRIER;
1715        insn = prev_nonnote_insn (insn))
1716     if (insn == 0
1717         || GET_CODE (insn) == CODE_LABEL
1718         || (GET_CODE (insn) == INSN
1719             && GET_CODE (PATTERN (insn)) != USE
1720             && GET_CODE (PATTERN (insn)) != CLOBBER))
1721       return 0;
1722
1723   return 1;
1724 }
1725 \f
1726 /* Find the number of the basic block that starts closest to INSN.  Return -1
1727    if we couldn't find such a basic block.  */
1728
1729 static int
1730 find_basic_block (insn)
1731      rtx insn;
1732 {
1733   int i;
1734
1735   /* Scan backwards to the previous BARRIER.  Then see if we can find a
1736      label that starts a basic block.  Return the basic block number.  */
1737
1738   for (insn = prev_nonnote_insn (insn);
1739        insn && GET_CODE (insn) != BARRIER;
1740        insn = prev_nonnote_insn (insn))
1741     ;
1742
1743   /* The start of the function is basic block zero.  */
1744   if (insn == 0)
1745     return 0;
1746
1747   /* See if any of the upcoming CODE_LABELs start a basic block.  If we reach
1748      anything other than a CODE_LABEL or note, we can't find this code.  */
1749   for (insn = next_nonnote_insn (insn);
1750        insn && GET_CODE (insn) == CODE_LABEL;
1751        insn = next_nonnote_insn (insn))
1752     {
1753       for (i = 0; i < n_basic_blocks; i++)
1754         if (insn == basic_block_head[i])
1755           return i;
1756     }
1757
1758   return -1;
1759 }
1760 \f
1761 /* Used for communication between the following two routines, contains
1762    the block number that insn was in.  */
1763
1764 static int current_block_number;
1765
1766 /* Called via note_stores from update_block_status.  It marks the
1767    registers set in this insn as live at the start of the block whose
1768    number is in current_block_number.  */
1769
1770 static void
1771 update_block_from_store (dest, x)
1772      rtx dest;
1773      rtx x;
1774 {
1775   int first_regno, last_regno;
1776   int offset = 0;
1777   int i;
1778
1779   if (GET_CODE (x) != SET
1780       || (GET_CODE (dest) != REG && (GET_CODE (dest) != SUBREG
1781                                      || GET_CODE (SUBREG_REG (dest)) != REG)))
1782     return;
1783
1784   if (GET_CODE (dest) == SUBREG)
1785     first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1786   else
1787     first_regno = REGNO (dest);
1788
1789   last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1790   for (i = first_regno; i < last_regno; i++)
1791     basic_block_live_at_start[current_block_number][i / HOST_BITS_PER_INT]
1792       |= (1 << (i % HOST_BITS_PER_INT));
1793 }
1794
1795 /* Called when INSN is being moved from a location near the target of a jump.
1796    If WHERE is the first active insn at the start of its basic block, we can
1797    just mark the registers set in INSN as live at the start of the basic block
1798    that starts immediately before INSN.
1799
1800    Otherwise, we leave a marker of the form (use (INSN)) immediately in front
1801    of WHERE for mark_target_live_regs.  These markers will be deleted when
1802    reorg finishes.  */
1803
1804 static void
1805 update_block (insn, where)
1806      rtx insn;
1807      rtx where;
1808 {
1809   /* Ignore if this was in a delay slot and it came from the target of
1810      a branch.  */
1811   if (INSN_FROM_TARGET_P (insn))
1812     return;
1813
1814   current_block_number = find_basic_block (insn);
1815   if (current_block_number == -1)
1816     return;
1817
1818   if (where == next_active_insn (basic_block_head[current_block_number]))
1819     note_stores (PATTERN (insn), update_block_from_store);
1820   else
1821     emit_insn_before (gen_rtx (USE, VOIDmode, insn), where);
1822
1823   /* INSN might be making a value live in a block where it didn't use to
1824      be.  So recompute liveness information for this block.  */
1825   bb_ticks[current_block_number]++;
1826 }
1827 \f
1828 /* Marks registers possibly live at the current place being scanned by
1829    mark_target_live_regs.  Used only by next two function.    */
1830
1831 static HARD_REG_SET current_live_regs;
1832
1833 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
1834    Also only used by the next two functions.  */
1835
1836 static HARD_REG_SET pending_dead_regs;
1837
1838 /* Utility function called from mark_target_live_regs via note_stores.
1839    It deadens any CLOBBERed registers and livens any SET registers.  */
1840
1841 static void
1842 update_live_status (dest, x)
1843      rtx dest;
1844      rtx x;
1845 {
1846   int first_regno, last_regno;
1847   int i;
1848
1849   if (GET_CODE (dest) != REG
1850       && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
1851     return;
1852
1853   if (GET_CODE (dest) == SUBREG)
1854     first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1855   else
1856     first_regno = REGNO (dest);
1857
1858   last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1859
1860   if (GET_CODE (x) == CLOBBER)
1861     for (i = first_regno; i < last_regno; i++)
1862       CLEAR_HARD_REG_BIT (current_live_regs, i);
1863   else
1864     for (i = first_regno; i < last_regno; i++)
1865       {
1866         SET_HARD_REG_BIT (current_live_regs, i);
1867         CLEAR_HARD_REG_BIT (pending_dead_regs, i);
1868       }
1869 }
1870
1871 /* Similar to next_insn, but ignores insns in the delay slots of
1872    an annulled branch.  */
1873
1874 static rtx
1875 next_insn_no_annul (insn)
1876      rtx insn;
1877 {
1878   if (insn)
1879     {
1880       /* If INSN is an annulled branch, skip any insns from the target
1881          of the branch.  */
1882       if (INSN_ANNULLED_BRANCH_P (insn)
1883           && NEXT_INSN (PREV_INSN (insn)) != insn)
1884         while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
1885           insn = NEXT_INSN (insn);
1886
1887       insn = NEXT_INSN (insn);
1888       if (insn && GET_CODE (insn) == INSN
1889           && GET_CODE (PATTERN (insn)) == SEQUENCE)
1890         insn = XVECEXP (PATTERN (insn), 0, 0);
1891     }
1892
1893   return insn;
1894 }
1895 \f
1896 /* Set the resources that are live at TARGET.
1897
1898    If TARGET is zero, we refer to the end of the current function and can
1899    return our precomputed value.
1900
1901    Otherwise, we try to find out what is live by consulting the basic block
1902    information.  This is tricky, because we must consider the actions of
1903    reload and jump optimization, which occur after the basic block information
1904    has been computed.
1905
1906    Accordingly, we proceed as follows::
1907
1908    We find the previous BARRIER and look at all immediately following labels
1909    (with no intervening active insns) to see if any of them start a basic
1910    block.  If we hit the start of the function first, we use block 0.
1911
1912    Once we have found a basic block and a corresponding first insns, we can
1913    accurately compute the live status from basic_block_live_regs and
1914    reg_renumber.  (By starting at a label following a BARRIER, we are immune
1915    to actions taken by reload and jump.)  Then we scan all insns between
1916    that point and our target.  For each CLOBBER (or for call-clobbered regs
1917    when we pass a CALL_INSN), mark the appropriate registers are dead.  For
1918    a SET, mark them as live.
1919
1920    We have to be careful when using REG_DEAD notes because they are not
1921    updated by such things as find_equiv_reg.  So keep track of registers
1922    marked as dead that haven't been assigned to, and mark them dead at the
1923    next CODE_LABEL since reload and jump won't propagate values across labels.
1924
1925    If we cannot find the start of a basic block (should be a very rare
1926    case, if it can happen at all), mark everything as potentially live.
1927
1928    Next, scan forward from TARGET looking for things set or clobbered
1929    before they are used.  These are not live.
1930
1931    Because we can be called many times on the same target, save our results
1932    in a hash table indexed by INSN_UID.  */
1933
1934 static void
1935 mark_target_live_regs (target, res)
1936      rtx target;
1937      struct resources *res;
1938 {
1939   int b = -1;
1940   int i;
1941   struct target_info *tinfo;
1942   rtx insn, next;
1943   rtx jump_insn = 0;
1944   HARD_REG_SET scratch;
1945   struct resources set, needed;
1946   int jump_count = 0;
1947
1948   /* Handle end of function.  */
1949   if (target == 0)
1950     {
1951       *res = end_of_function_needs;
1952       return;
1953     }
1954
1955   /* We have to assume memory is needed, but the CC isn't.  */
1956   res->memory = 1;
1957   res->volatil = 0;
1958   res->cc = 0;
1959
1960   /* See if we have computed this value already.  */
1961   for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1962        tinfo; tinfo = tinfo->next)
1963     if (tinfo->uid == INSN_UID (target))
1964       break;
1965
1966   /* Start by getting the basic block number.  If we have saved information,
1967      we can get it from there unless the insn at the start of the basic block
1968      has been deleted.  */
1969   if (tinfo && tinfo->block != -1
1970       && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
1971     b = tinfo->block;
1972
1973   if (b == -1)
1974     b = find_basic_block (target);
1975
1976   if (tinfo)
1977     {
1978       /* If the information is up-to-date, use it.  Otherwise, we will
1979          update it below.  */
1980       if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
1981         {
1982           COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
1983           return;
1984         }
1985     }
1986   else
1987     {
1988       /* Allocate a place to put our results and chain it into the
1989          hash table.  */
1990       tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
1991       tinfo->uid = INSN_UID (target);
1992       tinfo->block = b;
1993       tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1994       target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
1995     }
1996
1997   CLEAR_HARD_REG_SET (pending_dead_regs);
1998
1999   /* If we found a basic block, get the live registers from it and update
2000      them with anything set or killed between its start and the insn before
2001      TARGET.  Otherwise, we must assume everything is live.  */
2002   if (b != -1)
2003     {
2004       regset regs_live = basic_block_live_at_start[b];
2005       int offset, bit, j;
2006       int regno;
2007       rtx start_insn, stop_insn;
2008
2009       /* Compute hard regs live at start of block -- this is the real hard regs
2010          marked live, plus live pseudo regs that have been renumbered to
2011          hard regs.  */
2012
2013 #ifdef HARD_REG_SET
2014       current_live_regs = *regs_live;
2015 #else
2016       COPY_HARD_REG_SET (current_live_regs, regs_live);
2017 #endif
2018
2019       for (offset = 0, i = 0; offset < regset_size; offset++)
2020         {
2021           if (regs_live[offset] == 0)
2022             i += HOST_BITS_PER_INT;
2023           else
2024             for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
2025               if ((regs_live[offset] & bit)
2026                   && (regno = reg_renumber[i]) >= 0)
2027                 for (j = regno;
2028                      j < regno + HARD_REGNO_NREGS (regno,
2029                                                    PSEUDO_REGNO_MODE (i));
2030                      j++)
2031                   SET_HARD_REG_BIT (current_live_regs, j);
2032         }
2033
2034       /* Get starting and ending insn, handling the case where each might
2035          be a SEQUENCE.  */
2036       start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2037       stop_insn = target;
2038
2039       if (GET_CODE (start_insn) == INSN
2040           && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2041         start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2042
2043       if (GET_CODE (stop_insn) == INSN
2044           && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2045         stop_insn = next_insn (PREV_INSN (stop_insn));
2046
2047       for (insn = start_insn; insn != stop_insn;
2048            insn = next_insn_no_annul (insn))
2049         {
2050           rtx link;
2051           rtx real_insn = insn;
2052
2053           /* If this insn is from the target of a branch, it isn't going to
2054              be used in the sequel.  If it is used in both cases, this
2055              test will not be true.  */
2056           if (INSN_FROM_TARGET_P (insn))
2057             continue;
2058
2059           /* If this insn is a USE made by update_block, we care about the
2060              underlying insn.  */
2061           if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2062               && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
2063                   || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN
2064                   || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN))
2065               real_insn = XEXP (PATTERN (insn), 0);
2066
2067           if (GET_CODE (real_insn) == CALL_INSN)
2068             {
2069               /* CALL clobbers all call-used regs that aren't fixed except
2070                  sp, ap, and fp.  Do this before setting the result of the
2071                  call live.  */
2072               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2073                 if (call_used_regs[i]
2074                     && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2075                     && i != ARG_POINTER_REGNUM
2076 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2077                     && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2078 #endif
2079 #ifdef PIC_OFFSET_TABLE_REGNUM
2080                     && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2081 #endif
2082                     )
2083                   CLEAR_HARD_REG_BIT (current_live_regs, i);
2084             }
2085
2086           /* Mark anything killed in an insn to be deadened at the next
2087              label.  Ignore USE insns; the only REG_DEAD notes will be for
2088              parameters.  But they might be early.  A CALL_INSN will usually
2089              clobber registers used for parameters.  It isn't worth bothering
2090              with the unlikely case when it won't.  */
2091           if ((GET_CODE (real_insn) == INSN
2092                && GET_CODE (PATTERN (real_insn)) != USE)
2093               || GET_CODE (real_insn) == JUMP_INSN
2094               || GET_CODE (real_insn) == CALL_INSN)
2095             {
2096               for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2097                 if (REG_NOTE_KIND (link) == REG_DEAD
2098                     && GET_CODE (XEXP (link, 0)) == REG
2099                     && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2100                   {
2101                     int first_regno = REGNO (XEXP (link, 0));
2102                     int last_regno
2103                       = (first_regno
2104                          + HARD_REGNO_NREGS (first_regno,
2105                                              GET_MODE (XEXP (link, 0))));
2106
2107                     for (i = first_regno; i < last_regno; i++)
2108                       SET_HARD_REG_BIT (pending_dead_regs, i);
2109                   }
2110
2111               note_stores (PATTERN (real_insn), update_live_status);
2112
2113               /* If any registers were unused after this insn, kill them.
2114                  These notes will always be accurate.  */
2115               for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2116                 if (REG_NOTE_KIND (link) == REG_UNUSED
2117                     && GET_CODE (XEXP (link, 0)) == REG
2118                     && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2119                   {
2120                     int first_regno = REGNO (XEXP (link, 0));
2121                     int last_regno
2122                       = (first_regno
2123                          + HARD_REGNO_NREGS (first_regno,
2124                                              GET_MODE (XEXP (link, 0))));
2125
2126                     for (i = first_regno; i < last_regno; i++)
2127                       CLEAR_HARD_REG_BIT (current_live_regs, i);
2128                   }
2129             }
2130
2131           if (GET_CODE (real_insn) == CODE_LABEL)
2132             {
2133               /* A label clobbers the pending dead registers since neither
2134                  reload nor jump will propagate a value across a label.  */
2135               AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2136               CLEAR_HARD_REG_SET (pending_dead_regs);
2137             }
2138         }
2139
2140       COPY_HARD_REG_SET (res->regs, current_live_regs);
2141       tinfo->block = b;
2142       tinfo->bb_tick = bb_ticks[b];
2143     }
2144   else
2145     /* We didn't find the start of a basic block.  Assume everything
2146        in use.  This should happen only extremely rarely.  */
2147     SET_HARD_REG_SET (res->regs);
2148
2149   /* Now step forward from TARGET looking for registers that are set before
2150      they are used.  These are dead.  If we pass a label, any pending dead
2151      registers that weren't yet used can be made dead.  Stop when we pass a
2152      conditional JUMP_INSN; follow the first few unconditional branches.  */
2153
2154   CLEAR_RESOURCE (&set);
2155   CLEAR_RESOURCE (&needed);
2156
2157   for (insn = target; insn; insn = next)
2158     {
2159       rtx main_insn = insn;
2160
2161       next = NEXT_INSN (insn);
2162       switch (GET_CODE (insn))
2163         {
2164         case CODE_LABEL:
2165           AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2166           AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2167           CLEAR_HARD_REG_SET (pending_dead_regs);
2168           continue;
2169
2170         case BARRIER:
2171         case NOTE:
2172           continue;
2173
2174         case INSN:
2175           if (GET_CODE (PATTERN (insn)) == USE
2176               || GET_CODE (PATTERN (insn)) == CLOBBER)
2177             continue;
2178           if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2179             main_insn = XVECEXP (PATTERN (insn), 0, 0);
2180         }
2181
2182       if (GET_CODE (main_insn) == JUMP_INSN)
2183         {
2184           if (jump_count++ < 10
2185               && (simplejump_p (main_insn)
2186                   || GET_CODE (PATTERN (main_insn)) == RETURN))
2187             {
2188               next = next_active_insn (JUMP_LABEL (main_insn));
2189               if (jump_insn == 0)
2190                 jump_insn = insn;
2191             }
2192           else
2193             break;
2194         }
2195
2196       mark_referenced_resources (insn, &needed, 1);
2197       mark_set_resources (insn, &set, 1);
2198
2199       COPY_HARD_REG_SET (scratch, set.regs);
2200       AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2201       AND_COMPL_HARD_REG_SET (res->regs, scratch);
2202     }
2203
2204   /* If we hit an unconditional branch, we have another way of finding out
2205      what is live: we can see what is live at the branch target and include
2206      anything used but not set before the branch.  The only things that are
2207      live are those that are live using the above test and the test below.
2208
2209      Don't try this if we expired our jump count above, since that would
2210      mean there may be an infinite loop in the function being compiled.  */
2211
2212   if (jump_insn && jump_count < 10)
2213     {
2214       rtx jump_target = (GET_CODE (jump_insn) == INSN
2215                          ? JUMP_LABEL (XVECEXP (PATTERN (jump_insn), 0, 0))
2216                          : JUMP_LABEL (jump_insn));
2217       struct resources new_resources;
2218       rtx stop_insn = next_active_insn (jump_insn);
2219
2220       mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2221       CLEAR_RESOURCE (&set);
2222       CLEAR_RESOURCE (&needed);
2223
2224       /* Include JUMP_INSN in the needed registers.  */
2225       for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2226         {
2227           mark_referenced_resources (insn, &needed, 1);
2228
2229           COPY_HARD_REG_SET (scratch, needed.regs);
2230           AND_COMPL_HARD_REG_SET (scratch, set.regs);
2231           IOR_HARD_REG_SET (new_resources.regs, scratch);
2232
2233           mark_set_resources (insn, &set, 1);
2234         }
2235
2236       AND_HARD_REG_SET (res->regs, new_resources.regs);
2237     }
2238
2239   COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2240 }
2241 \f
2242 /* Scan a function looking for insns that need a delay slot and find insns to
2243    put into the delay slot.
2244
2245    NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2246    as calls).  We do these first since we don't want jump insns (that are
2247    easier to fill) to get the only insns that could be used for non-jump insns.
2248    When it is zero, only try to fill JUMP_INSNs.
2249
2250    When slots are filled in this manner, the insns (including the
2251    delay_insn) are put together in a SEQUENCE rtx.  In this fashion,
2252    it is possible to tell whether a delay slot has really been filled
2253    or not.  `final' knows how to deal with this, by communicating
2254    through FINAL_SEQUENCE.  */
2255
2256 static void
2257 fill_simple_delay_slots (first, non_jumps_p)
2258      rtx first;
2259 {
2260   register rtx insn, pat, trial, next_trial;
2261   register int i;
2262   int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2263   struct resources needed, set;
2264   register int slots_to_fill, slots_filled;
2265   rtx delay_list;
2266
2267   for (i = 0; i < num_unfilled_slots; i++)
2268     {
2269       /* Get the next insn to fill.  If it has already had any slots assigned,
2270          we can't do anything with it.  Maybe we'll improve this later.  */
2271
2272       insn = unfilled_slots_base[i];
2273       if (insn == 0
2274           || INSN_DELETED_P (insn)
2275           || (GET_CODE (insn) == INSN
2276               && GET_CODE (PATTERN (insn)) == SEQUENCE)
2277           || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2278           || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2279         continue;
2280
2281       slots_to_fill = num_delay_slots (insn);
2282       if (slots_to_fill == 0)
2283         abort ();
2284
2285       /* This insn needs, or can use, some delay slots.  SLOTS_TO_FILL
2286          says how many.  After initialization, scan backwards from the
2287          insn to search for a potential delay-slot candidate.  Stop
2288          searching when a label or jump is hit.
2289
2290          For each candidate, if it is to go into the delay slot (moved
2291          forward in execution sequence), it must not need or set any resources
2292          that were set by later insns and must not set any resources that
2293          are needed for those insns.
2294
2295          The delay slot insn itself sets resources unless it is a call
2296          (in which case the called routine, not the insn itself, is doing
2297          the setting).  */
2298
2299       slots_filled = 0;
2300       delay_list = 0;
2301       CLEAR_RESOURCE (&needed);
2302       CLEAR_RESOURCE (&set);
2303       mark_set_resources (insn, &set, 0);
2304       mark_referenced_resources (insn, &needed, 0);
2305
2306       for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2307            trial = next_trial)
2308         {
2309           next_trial = prev_nonnote_insn (trial);
2310
2311           /* This must be an INSN or CALL_INSN.  */
2312           pat = PATTERN (trial);
2313
2314           /* USE and CLOBBER at this level was just for flow; ignore it.  */
2315           if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2316             continue;
2317
2318           /* Check for resource conflict first, to avoid unnecessary
2319              splitting.  */
2320           if (! insn_references_resource_p (trial, &set, 1)
2321               && ! insn_sets_resource_p (trial, &set, 1)
2322               && ! insn_sets_resource_p (trial, &needed, 1)
2323 #ifdef HAVE_cc0
2324               /* Can't separate set of cc0 from its use.  */
2325               && ! (reg_mentioned_p (cc0_rtx, pat)
2326                     && ! sets_cc0_p (cc0_rtx, pat))
2327 #endif
2328               )
2329             {
2330               trial = try_split (pat, trial, 1);
2331               next_trial = prev_nonnote_insn (trial);
2332               if (eligible_for_delay (insn, slots_filled, trial))
2333                 {
2334                   /* In this case, we are searching backward, so if we
2335                      find insns to put on the delay list, we want
2336                      to put them at the head, rather than the
2337                      tail, of the list.  */
2338
2339                   delay_list = gen_rtx (INSN_LIST, VOIDmode,
2340                                         trial, delay_list);
2341                   update_block (trial, trial);
2342                   delete_insn (trial);
2343                   if (slots_to_fill == ++slots_filled)
2344                     break;
2345                   continue;
2346                 }
2347             }
2348
2349           mark_set_resources (trial, &set, 1);
2350           mark_referenced_resources (trial, &needed, 1);
2351         }
2352
2353       if (slots_filled == slots_to_fill)
2354         /* happy.  */ ;
2355
2356       /* If all needed slots haven't been filled, we come here.  */
2357
2358       /* Try to optimize case of jumping around a single insn.  */
2359 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2360       else if (delay_list == 0
2361                && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
2362         {
2363           delay_list = optimize_skip (insn);
2364           if (delay_list)
2365             slots_filled += 1;
2366         }
2367 #endif
2368
2369       /* @@ This would be a good place to optimize:
2370
2371          call _foo              call _foo
2372          nop                    add %o7,.-L1,%o7
2373          b,a L1
2374          nop
2375
2376          Someday... */
2377
2378       /* Try to get insns from beyond the insn needing the delay slot.
2379          These insns can neither set or reference resources set in insns being
2380          skipped, cannot set resources in the insn being skipped, and, if this
2381          is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2382          call might not return).
2383
2384          If this is a conditional jump, see if it merges back to us early
2385          enough for us to pick up insns from the merge point.  Don't do
2386          this if there is another branch to our label unless we pass all of
2387          them.
2388
2389          Another similar merge is if we jump to the same place that a
2390          later unconditional jump branches to.  In that case, we don't
2391          care about the number of uses of our label.  */
2392
2393       else if (GET_CODE (insn) != JUMP_INSN
2394                || (condjump_p (insn) && ! simplejump_p (insn)
2395                    && JUMP_LABEL (insn) != 0))
2396         {
2397           rtx target = 0;
2398           int maybe_never = 0;
2399           int passed_label = 0;
2400           int target_uses;
2401           struct resources needed_at_jump;
2402
2403           CLEAR_RESOURCE (&needed);
2404           CLEAR_RESOURCE (&set);
2405
2406           if (GET_CODE (insn) == CALL_INSN)
2407             {
2408               mark_set_resources (insn, &set, 1);
2409               mark_referenced_resources (insn, &needed, 1);
2410               maybe_never = 1;
2411             }
2412           else if (GET_CODE (insn) == JUMP_INSN)
2413             {
2414               /* Get our target and show how many more uses we want to
2415                  see before we hit the label.  */
2416               target = JUMP_LABEL (insn);
2417               target_uses = LABEL_NUSES (target) - 1;
2418             }
2419
2420           for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2421             {
2422               rtx pat, trial_delay;
2423
2424               next_trial = next_nonnote_insn (trial);
2425
2426               if (GET_CODE (trial) == CODE_LABEL)
2427                 {
2428                   passed_label = 1;
2429
2430                   /* If this is our target, see if we have seen all its uses.
2431                      If so, indicate we have passed our target and ignore it.
2432                      All other labels cause us to stop our search.  */
2433                   if (trial == target && target_uses == 0)
2434                     {
2435                       target = 0;
2436                       continue;
2437                     }
2438                   else
2439                     break;
2440                 }
2441               else if (GET_CODE (trial) == BARRIER)
2442                 break;
2443
2444               /* We must have an INSN, JUMP_INSN, or CALL_INSN.  */
2445               pat = PATTERN (trial);
2446
2447               /* Stand-alone USE and CLOBBER are just for flow.  */
2448               if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2449                 continue;
2450
2451               /* If this already has filled delay slots, get the insn needing
2452                  the delay slots.  */
2453               if (GET_CODE (pat) == SEQUENCE)
2454                 trial_delay = XVECEXP (pat, 0, 0);
2455               else
2456                 trial_delay = trial;
2457
2458               /* If this is a jump insn to our target, indicate that we have
2459                  seen another jump to it.  If we aren't handling a conditional
2460                  jump, stop our search. Otherwise, compute the needs at its
2461                  target and add them to NEEDED.  */
2462               if (GET_CODE (trial_delay) == JUMP_INSN)
2463                 {
2464                   if (target == 0)
2465                     break;
2466                   else if (JUMP_LABEL (trial_delay) == target)
2467                     target_uses--;
2468                   else
2469                     {
2470                       mark_target_live_regs
2471                         (next_active_insn (JUMP_LABEL (trial_delay)),
2472                          &needed_at_jump);
2473                       needed.memory |= needed_at_jump.memory;
2474                       IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
2475                     }
2476                 }
2477
2478               /* See if we have a resource problem before we try to
2479                  split.   */
2480               if (target == 0
2481                   && GET_CODE (pat) != SEQUENCE
2482                   && ! insn_references_resource_p (trial, &set, 1)
2483                   && ! insn_sets_resource_p (trial, &set, 1)
2484                   && ! insn_sets_resource_p (trial, &needed, 1)
2485 #ifdef HAVE_cc0
2486                   && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2487 #endif
2488                   && ! (maybe_never && may_trap_p (pat))
2489                   && (trial = try_split (pat, trial, 0))
2490                   && eligible_for_delay (insn, slots_filled, trial))
2491                 {
2492                   next_trial = next_nonnote_insn (trial);
2493                   delay_list = add_to_delay_list (trial, delay_list);
2494
2495 #ifdef HAVE_cc0
2496                   if (reg_mentioned_p (cc0_rtx, pat))
2497                     link_cc0_insns (trial);
2498 #endif
2499
2500                   if (passed_label)
2501                     update_block (trial, trial);
2502                   delete_insn (trial);
2503                   if (slots_to_fill == ++slots_filled)
2504                     break;
2505                   continue;
2506                 }
2507
2508               mark_set_resources (trial, &set, 1);
2509               mark_referenced_resources (trial, &needed, 1);
2510
2511               /* Ensure we don't put insns between the setting of cc and the
2512                  comparison by moving a setting of cc into an earlier delay
2513                  slot since these insns could clobber the condition code.  */
2514               set.cc = 1;
2515
2516               /* If this is a call or jump, we might not get here.  */
2517               if (GET_CODE (trial) == CALL_INSN
2518                   || GET_CODE (trial) == JUMP_INSN)
2519                 maybe_never = 1;
2520             }
2521
2522           /* If there are slots left to fill and our search was stopped by an
2523              unconditional branch, try the insn at the branch target.  We can
2524              redirect the branch if it works.  */
2525           if (slots_to_fill != slots_filled
2526               && trial
2527               && GET_CODE (trial) == JUMP_INSN
2528               && simplejump_p (trial)
2529               && (target == 0 || JUMP_LABEL (trial) == target)
2530               && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2531               && ! (GET_CODE (next_trial) == INSN
2532                     && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2533               && ! insn_references_resource_p (next_trial, &set, 1)
2534               && ! insn_sets_resource_p (next_trial, &set, 1)
2535               && ! insn_sets_resource_p (next_trial, &needed, 1)
2536 #ifdef HAVE_cc0
2537               && ! (reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2538                     && ! sets_cc0_p (PATTERN (next_trial)))
2539 #endif
2540               && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2541               && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2542               && eligible_for_delay (insn, slots_filled, next_trial))
2543             {
2544               rtx new_label = next_active_insn (next_trial);
2545
2546               if (new_label != 0)
2547                 new_label = get_label_before (new_label);
2548
2549               delay_list
2550                 = add_to_delay_list (copy_rtx (next_trial), delay_list);
2551               slots_filled++;
2552               redirect_jump (trial, new_label);
2553
2554               /* If we merged because we both jumped to the same place,
2555                  redirect the original insn also.  */
2556               if (target)
2557                 redirect_jump (insn, new_label);
2558             }
2559         }
2560
2561       if (delay_list)
2562         unfilled_slots_base[i]
2563           = emit_delay_sequence (insn, delay_list,
2564                                  slots_filled, slots_to_fill);
2565
2566       if (slots_to_fill == slots_filled)
2567         unfilled_slots_base[i] = 0;
2568
2569       note_delay_statistics (slots_filled, 0);
2570     }
2571
2572 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2573   /* See if the epilogue needs any delay slots.  Try to fill them if so.
2574      The only thing we can do is scan backwards from the end of the
2575      function.  If we did this in a previous pass, it is incorrect to do it
2576      again.  */
2577   if (current_function_epilogue_delay_list)
2578     return;
2579
2580   slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2581   if (slots_to_fill == 0)
2582     return;
2583
2584   slots_filled = 0;
2585   CLEAR_RESOURCE (&needed);
2586   CLEAR_RESOURCE (&set);
2587
2588   for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2589        trial = PREV_INSN (trial))
2590     {
2591       if (GET_CODE (trial) == NOTE)
2592         continue;
2593       pat = PATTERN (trial);
2594       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2595         continue;
2596
2597       if (! insn_references_resource_p (trial, &set, 1)
2598           && ! insn_sets_resource_p (trial, &needed, 1)
2599 #ifdef HAVE_cc0
2600           /* Don't want to mess with cc0 here.  */
2601           && ! reg_mentioned_p (cc0_rtx, pat)
2602 #endif
2603           )
2604         {
2605           trial = try_split (pat, trial, 1);
2606           if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2607             {
2608               /* Here as well we are searching backward, so put the
2609                  insns we find on the head of the list.  */
2610
2611               current_function_epilogue_delay_list
2612                 = gen_rtx (INSN_LIST, VOIDmode, trial,
2613                            current_function_epilogue_delay_list);
2614               mark_referenced_resources (trial, &end_of_function_needs, 1);
2615               update_block (trial, trial);
2616               delete_insn (trial);
2617
2618               /* Clear deleted bit so final.c will output the insn.  */
2619               INSN_DELETED_P (trial) = 0;
2620
2621               if (slots_to_fill == ++slots_filled)
2622                 break;
2623               continue;
2624             }
2625         }
2626
2627       mark_set_resources (trial, &set, 1);
2628       mark_referenced_resources (trial, &needed, 1);
2629     }
2630
2631   note_delay_statistics (slots_filled, 0);
2632 #endif
2633 }
2634 \f
2635 /* Try to find insns to place in delay slots.
2636
2637    INSN is the jump needing SLOTS_TO_FILL delay slots.  It tests CONDITION
2638    or is an unconditional branch if CONDITION is const_true_rtx.
2639    *PSLOTS_FILLED is updated with the number of slots that we have filled.
2640
2641    THREAD is a flow-of-control, either the insns to be executed if the
2642    branch is true or if the branch is false, THREAD_IF_TRUE says which.
2643
2644    OPPOSITE_THREAD is the thread in the opposite direction.  It is used
2645    to see if any potential delay slot insns set things needed there.
2646
2647    LIKELY is non-zero if it is extremely likely that the branch will be
2648    taken and THREAD_IF_TRUE is set.  This is used for the branch at the
2649    end of a loop back up to the top.
2650
2651    OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2652    thread.  I.e., it is the fallthrough code of our jump or the target of the
2653    jump when we are the only jump going there.
2654
2655    If OWN_THREAD is false, it must be the "true" thread of a jump.  In that
2656    case, we can only take insns from the head of the thread for our delay
2657    slot.  We then adjust the jump to point after the insns we have taken.  */
2658
2659 static rtx
2660 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
2661                         thread_if_true, own_thread, own_opposite_thread,
2662                         slots_to_fill, pslots_filled)
2663      rtx insn;
2664      rtx condition;
2665      rtx thread, opposite_thread;
2666      int likely;
2667      int thread_if_true;
2668      int own_thread, own_opposite_thread;
2669      int slots_to_fill, *pslots_filled;
2670 {
2671   rtx new_thread = thread;
2672   rtx delay_list = 0;
2673   struct resources opposite_needed, set, needed;
2674   rtx trial;
2675   int lose = 0;
2676   int must_annul = 0;
2677
2678   /* Validate our arguments.  */
2679   if ((condition == const_true_rtx && ! thread_if_true)
2680       || (! own_thread && ! thread_if_true))
2681     abort ();
2682
2683   /* If our thread is the end of subroutine, we can't get any delay
2684      insns from that.  */
2685   if (thread == 0)
2686     return 0;
2687
2688   /* If this is an unconditional branch, nothing is needed at the
2689      opposite thread.  Otherwise, compute what is needed there.  */
2690   if (condition == const_true_rtx)
2691     CLEAR_RESOURCE (&opposite_needed);
2692   else
2693     mark_target_live_regs (opposite_thread, &opposite_needed);
2694
2695   /* Scan insns at THREAD.  We are looking for an insn that can be removed
2696      from THREAD (it neither sets nor references resources that were set
2697      ahead of it and it doesn't set anything needs by the insns ahead of
2698      it) and that either can be placed in an annulling insn or aren't
2699      needed at OPPOSITE_THREAD.  */
2700
2701   CLEAR_RESOURCE (&needed);
2702   CLEAR_RESOURCE (&set);
2703
2704   /* If we do not own this thread, we must stop as soon as we find
2705      something that we can't put in a delay slot, since all we can do
2706      is branch into THREAD at a later point.  Therefore, labels stop
2707      the search if this is not the `true' thread.  */
2708
2709   for (trial = thread;
2710        ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2711        trial = next_nonnote_insn (trial))
2712     {
2713       rtx pat;
2714
2715       /* If we have passed a label, we no longer own this thread.  */
2716       if (GET_CODE (trial) == CODE_LABEL)
2717         {
2718           own_thread = 0;
2719           continue;
2720         }
2721
2722       pat = PATTERN (trial);
2723       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2724         continue;
2725
2726       /* If TRIAL conflicts with the insns ahead of it, we lose.  Also,
2727          don't separate or copy insns that set and use CC0.  */
2728       if (! insn_references_resource_p (trial, &set, 1)
2729           && ! insn_sets_resource_p (trial, &set, 1)
2730           && ! insn_sets_resource_p (trial, &needed, 1)
2731 #ifdef HAVE_cc0
2732           && ! (reg_mentioned_p (cc0_rtx, pat)
2733                 && (! own_thread || ! sets_cc0_p (pat)))
2734 #endif
2735           )
2736         {
2737           /* If TRIAL is redundant with some insn before INSN, we don't
2738              actually need to add it to the delay list; we can merely pretend
2739              we did.  */
2740           if (redundant_insn_p (trial, insn, delay_list))
2741             {
2742               if (own_thread)
2743                 {
2744                   update_block (trial, thread);
2745                   delete_insn (trial);
2746                 }
2747               else
2748                 new_thread = next_active_insn (trial);
2749
2750               continue;
2751             }
2752
2753           /* There are two ways we can win:  If TRIAL doesn't set anything
2754              needed at the opposite thread and can't trap, or if it can
2755              go into an annulled delay slot.  */
2756           if (condition == const_true_rtx
2757               || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2758                   && ! may_trap_p (pat)))
2759             {
2760               trial = try_split (pat, trial, 0);
2761               pat = PATTERN (trial);
2762               if (eligible_for_delay (insn, *pslots_filled, trial))
2763                 goto winner;
2764             }
2765           else if (0
2766 #ifdef ANNUL_IFTRUE_SLOTS
2767                    || ! thread_if_true
2768 #endif
2769 #ifdef ANNUL_IFFALSE_SLOTS
2770                    || thread_if_true
2771 #endif
2772                    )
2773             {
2774               trial = try_split (pat, trial, 0);
2775               pat = PATTERN (trial);
2776               if ((thread_if_true
2777                    ? eligible_for_annul_false (insn, *pslots_filled, trial)
2778                    : eligible_for_annul_true (insn, *pslots_filled, trial)))
2779                 {
2780                   rtx temp;
2781
2782                   must_annul = 1;
2783                 winner:
2784
2785 #ifdef HAVE_cc0
2786                   if (reg_mentioned_p (cc0_rtx, pat))
2787                     link_cc0_insns (trial);
2788 #endif
2789
2790                   /* If we own this thread, delete the insn.  If this is the
2791                      destination of a branch, show that a basic block status
2792                      may have been updated.  In any case, mark the new
2793                      starting point of this thread.  */
2794                   if (own_thread)
2795                     {
2796                       update_block (trial, thread);
2797                       delete_insn (trial);
2798                     }
2799                   else
2800                     new_thread = next_active_insn (trial);
2801
2802                   temp = own_thread ? trial : copy_rtx (trial);
2803                   if (thread_if_true)
2804                     INSN_FROM_TARGET_P (temp) = 1;
2805
2806                   delay_list = add_to_delay_list (temp, delay_list);
2807
2808                   if (slots_to_fill == ++(*pslots_filled))
2809                     {
2810                       /* Even though we have filled all the slots, we
2811                          may be branching to a location that has a
2812                          redundant insn.  Skip any if so.  */
2813                       while (new_thread && ! own_thread
2814                              && ! insn_sets_resource_p (new_thread, &set, 1)
2815                              && ! insn_sets_resource_p (new_thread, &needed, 1)
2816                              && ! insn_references_resource_p (new_thread,
2817                                                               &set, 1)
2818                              && redundant_insn_p (new_thread, insn,
2819                                                   delay_list))
2820                         new_thread = next_active_insn (new_thread);
2821                       break;
2822                     }
2823
2824                   continue;
2825                 }
2826             }
2827         }
2828
2829       /* This insn can't go into a delay slot.  */
2830       lose = 1;
2831       mark_set_resources (trial, &set, 1);
2832       mark_referenced_resources (trial, &needed, 1);
2833
2834       /* Ensure we don't put insns between the setting of cc and the comparison
2835          by moving a setting of cc into an earlier delay slot since these insns
2836          could clobber the condition code.  */
2837       set.cc = 1;
2838
2839       /* If this insn is a register-register copy and the next insn has
2840          a use of our destination, change it to use our source.  That way,
2841          it will become a candidate for our delay slot the next time
2842          through this loop.  This case occurs commonly in loops that
2843          scan a list.
2844
2845          We could check for more complex cases than those tested below,
2846          but it doesn't seem worth it.  It might also be a good idea to try
2847          to swap the two insns.  That might do better.  */
2848
2849       if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2850           && GET_CODE (SET_SRC (pat)) == REG
2851           && GET_CODE (SET_DEST (pat)) == REG)
2852         {
2853           rtx next = next_nonnote_insn (trial);
2854           int our_dest = REGNO (SET_DEST (pat));
2855
2856           if (next && GET_CODE (next) == INSN
2857               && GET_CODE (PATTERN (next)) == SET
2858               && GET_CODE (SET_DEST (PATTERN (next))) == REG
2859               && REGNO (SET_DEST (PATTERN (next))) != our_dest
2860               && refers_to_regno_p (our_dest, our_dest + 1,
2861                                     SET_SRC (PATTERN (next)), 0))
2862             validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2863         }
2864     }
2865
2866   /* If we stopped on a branch insn that has delay slots, see if we can
2867      steal some of the insns in those slots.  */
2868   if (trial && GET_CODE (trial) == INSN
2869       && GET_CODE (PATTERN (trial)) == SEQUENCE
2870       && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2871     {
2872       /* If this is the `true' thread, we will want to follow the jump,
2873          so we can only do this if we have taken everything up to here.  */
2874       if (thread_if_true && trial == new_thread)
2875         delay_list
2876           = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2877                                           delay_list, &set, &needed,
2878                                           &opposite_needed, slots_to_fill,
2879                                           pslots_filled, &must_annul,
2880                                           &new_thread);
2881       else if (! thread_if_true)
2882         delay_list
2883           = steal_delay_list_from_fallthrough (insn, condition,
2884                                                PATTERN (trial),
2885                                                delay_list, &set, &needed,
2886                                                &opposite_needed, slots_to_fill,
2887                                                pslots_filled, &must_annul);
2888     }
2889
2890   /* If we haven't found anything for this delay slot and it is very
2891      likely that the branch will be taken, see if the insn at our target
2892      increments or decrements a register.  If so, try to place the opposite
2893      arithmetic insn after the jump insn and put the arithmetic insn in the
2894      delay slot.  If we can't do this, return.  */
2895   if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
2896     {
2897       rtx pat = PATTERN (new_thread);
2898       rtx dest;
2899       rtx src;
2900
2901       trial = try_split (pat, new_thread, 0);
2902       pat = PATTERN (trial);
2903
2904       if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
2905           || ! eligible_for_delay (insn, 0, trial))
2906         return 0;
2907
2908       dest = SET_DEST (pat), src = SET_SRC (pat);
2909       if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2910           && rtx_equal_p (XEXP (src, 0), dest))
2911         {
2912           rtx other = XEXP (src, 1);
2913           rtx new_arith;
2914           rtx ninsn;
2915
2916           /* If this is a constant adjustment, use the same code with
2917              the negated constant.  Otherwise, reverse the sense of the
2918              arithmetic.  */
2919           if (GET_CODE (other) == CONST_INT)
2920             new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest,
2921                                  negate_rtx (GET_MODE (src), other));
2922           else
2923             new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS,
2924                                  GET_MODE (src), dest, other);
2925
2926           ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith),
2927                                    insn);
2928
2929           if (recog_memoized (ninsn) < 0
2930               || (insn_extract (ninsn),
2931                   ! constrain_operands (INSN_CODE (ninsn), 1)))
2932             {
2933               delete_insn (ninsn);
2934               return 0;
2935             }
2936
2937           if (own_thread)
2938             {
2939               update_block (trial, thread);
2940               delete_insn (trial);
2941             }
2942           else
2943             new_thread = next_active_insn (trial);
2944
2945           ninsn = own_thread ? trial : copy_rtx (trial);
2946           if (thread_if_true)
2947             INSN_FROM_TARGET_P (ninsn) = 1;
2948
2949           delay_list = add_to_delay_list (ninsn, 0);
2950           (*pslots_filled)++;
2951         }
2952     }
2953
2954   if (delay_list && must_annul)
2955     INSN_ANNULLED_BRANCH_P (insn) = 1;
2956
2957   /* If we are to branch into the middle of this thread, find an appropriate
2958      label or make a new one if none, and redirect INSN to it.  If we hit the
2959      end of the function, use the end-of-function label.  */
2960   if (new_thread != thread)
2961     {
2962       rtx label;
2963
2964       if (! thread_if_true)
2965         abort ();
2966
2967       if (new_thread && GET_CODE (new_thread) == JUMP_INSN
2968           && (simplejump_p (new_thread)
2969               || GET_CODE (PATTERN (new_thread)) == RETURN))
2970         new_thread = follow_jumps (JUMP_LABEL (new_thread), 1);
2971
2972       if (new_thread == 0)
2973         label = find_end_label ();
2974       else if (GET_CODE (new_thread) == CODE_LABEL)
2975         label = new_thread;
2976       else
2977         label = get_label_before (new_thread);
2978
2979       redirect_jump (insn, label);
2980     }
2981
2982   return delay_list;
2983 }
2984 \f
2985 /* Make another attempt to find insns to place in delay slots.
2986
2987    We previously looked for insns located in front of the delay insn
2988    and, for non-jump delay insns, located behind the delay insn.
2989
2990    Here only try to schedule jump insns and try to move insns from either
2991    the target or the following insns into the delay slot.  If annulling is
2992    supported, we will be likely to do this.  Otherwise, we can do this only
2993    if safe.  */
2994
2995 static void
2996 fill_eager_delay_slots (first)
2997      rtx first;
2998 {
2999   register rtx insn;
3000   register int i;
3001   int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3002
3003   for (i = 0; i < num_unfilled_slots; i++)
3004     {
3005       rtx condition;
3006       rtx target_label, insn_at_target, fallthrough_insn;
3007       rtx delay_list = 0;
3008       int own_target;
3009       int own_fallthrough;
3010       int prediction, slots_to_fill, slots_filled;
3011
3012       insn = unfilled_slots_base[i];
3013       if (insn == 0
3014           || INSN_DELETED_P (insn)
3015           || GET_CODE (insn) != JUMP_INSN
3016           || ! condjump_p (insn))
3017         continue;
3018
3019       slots_to_fill = num_delay_slots (insn);
3020       if (slots_to_fill == 0)
3021         abort ();
3022
3023       slots_filled = 0;
3024       target_label = JUMP_LABEL (insn);
3025       condition = get_branch_condition (insn, target_label);
3026
3027       if (condition == 0)
3028         continue;
3029
3030       /* Get the next active fallthough and target insns and see if we own
3031          them.  Then see whether the branch is likely true.  We don't need
3032          to do a lot of this for unconditional branches.  */
3033
3034       insn_at_target = next_active_insn (target_label);
3035       own_target = own_thread_p (target_label, target_label, 0);
3036
3037       if (condition == const_true_rtx)
3038         {
3039           own_fallthrough = 0;
3040           fallthrough_insn = 0;
3041           prediction = 2;
3042         }
3043       else
3044         {
3045           fallthrough_insn = next_active_insn (insn);
3046           own_fallthrough = own_thread_p (NEXT_INSN (insn), 0, 1);
3047           prediction = mostly_true_jump (insn, condition);
3048         }
3049
3050       /* If this insn is expected to branch, first try to get insns from our
3051          target, then our fallthrough insns.  If it is not, expected to branch,
3052          try the other order.  */
3053
3054       if (prediction)
3055         {
3056           delay_list
3057             = fill_slots_from_thread (insn, condition, insn_at_target,
3058                                       fallthrough_insn, prediction == 2, 1,
3059                                       own_target, own_fallthrough,
3060                                       slots_to_fill, &slots_filled);
3061
3062           if (delay_list == 0 && own_fallthrough)
3063             {
3064               /* Even though we didn't find anything for delay slots,
3065                  we might have found a redundant insn which we deleted
3066                  from the thread that was filled.  So we have to recompute
3067                  the next insn at the target.  */
3068               target_label = JUMP_LABEL (insn);
3069               insn_at_target = next_active_insn (target_label);
3070
3071               delay_list
3072                 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3073                                           insn_at_target, 0, 0,
3074                                           own_fallthrough, own_target,
3075                                           slots_to_fill, &slots_filled);
3076             }
3077         }
3078       else
3079         {
3080           if (own_fallthrough)
3081             delay_list
3082               = fill_slots_from_thread (insn, condition, fallthrough_insn,
3083                                         insn_at_target, 0, 0,
3084                                         own_fallthrough, own_target,
3085                                         slots_to_fill, &slots_filled);
3086
3087           if (delay_list == 0)
3088             delay_list
3089               = fill_slots_from_thread (insn, condition, insn_at_target,
3090                                         next_active_insn (insn), 0, 1,
3091                                         own_target, own_fallthrough,
3092                                         slots_to_fill, &slots_filled);
3093         }
3094
3095       if (delay_list)
3096         unfilled_slots_base[i]
3097           = emit_delay_sequence (insn, delay_list,
3098                                  slots_filled, slots_to_fill);
3099
3100       if (slots_to_fill == slots_filled)
3101         unfilled_slots_base[i] = 0;
3102
3103       note_delay_statistics (slots_filled, 1);
3104     }
3105 }
3106 \f
3107 /* Once we have tried two ways to fill a delay slot, make a pass over the
3108    code to try to improve the results and to do such things as more jump
3109    threading.  */
3110
3111 static void
3112 relax_delay_slots (first)
3113      rtx first;
3114 {
3115   register rtx insn, next, pat;
3116   register rtx trial, delay_insn, target_label;
3117
3118   /* Look at every JUMP_INSN and see if we can improve it.  */
3119   for (insn = first; insn; insn = next)
3120     {
3121       rtx other;
3122
3123       next = next_active_insn (insn);
3124
3125       /* If this is a jump insn, see if it now jumps to a jump, jumps to
3126          the next insn, or jumps to a label that is not the last of a
3127          group of consecutive labels.  */
3128       if (GET_CODE (insn) == JUMP_INSN
3129           && (target_label = JUMP_LABEL (insn)) != 0)
3130         {
3131           target_label = follow_jumps (target_label, 1);
3132           target_label = prev_label (next_active_insn (target_label));
3133
3134           if (next_active_insn (target_label) == next)
3135             {
3136               delete_jump (insn);
3137               continue;
3138             }
3139
3140           if (target_label != JUMP_LABEL (insn))
3141             redirect_jump (insn,
3142                            target_label ? target_label : find_end_label ());
3143
3144           /* See if this jump branches around a unconditional jump.
3145              If so, invert this jump and point it to the target of the
3146              second jump.  */
3147           if (next && GET_CODE (next) == JUMP_INSN
3148               && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3149               && next_active_insn (target_label) == next_active_insn (next)
3150               && no_labels_between_p (insn, next))
3151             {
3152               rtx label = JUMP_LABEL (next);
3153
3154               /* Be careful how we do this to avoid deleting code or
3155                  labels that are momentarily dead.  See similar optimization
3156                  in jump.c.
3157
3158                  We also need to ensure we properly handle the case when
3159                  invert_jump fails.  */
3160
3161               ++LABEL_NUSES (target_label);
3162               if (label)
3163                 ++LABEL_NUSES (label);
3164
3165               if (invert_jump (insn, label))
3166                 {
3167                   delete_insn (next);
3168                   next = insn;
3169                 }
3170
3171               if (label)
3172                 --LABEL_NUSES (label);
3173
3174               if (--LABEL_NUSES (target_label) == 0)
3175                 delete_insn (target_label);
3176
3177               continue;
3178             }
3179         }
3180
3181       /* If this is an unconditional jump and the previous insn is a
3182          conditional jump, try reversing the condition of the previous
3183          insn and swapping our targets.  The next pass might be able to
3184          fill the slots.
3185
3186          Don't do this if we expect the conditional branch to be true, because
3187          we would then be making the more common case longer.  */
3188
3189       if (GET_CODE (insn) == JUMP_INSN
3190           && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3191           && (other = prev_active_insn (insn)) != 0
3192           && condjump_p (other)
3193           && no_labels_between_p (other, insn)
3194           && ! mostly_true_jump (other,
3195                                  get_branch_condition (other,
3196                                                        JUMP_LABEL (other))))
3197         {
3198           rtx other_target = JUMP_LABEL (other);
3199
3200           /* Increment the count of OTHER_TARGET, so it doesn't get deleted
3201              as we move the label.  */
3202           if (other_target)
3203             ++LABEL_NUSES (other_target);
3204
3205           if (invert_jump (other, target_label))
3206             redirect_jump (insn, other_target);
3207
3208           if (other_target)
3209             --LABEL_NUSES (other_target);
3210         }
3211
3212       /* Now look only at cases where we have filled a delay slot.  */
3213       if (GET_CODE (insn) != INSN
3214           || GET_CODE (PATTERN (insn)) != SEQUENCE)
3215         continue;
3216
3217       pat = PATTERN (insn);
3218       delay_insn = XVECEXP (pat, 0, 0);
3219
3220       /* See if the first insn in the delay slot is redundant with some
3221          previous insn.  Remove it from the delay slot if so; then set up
3222          to reprocess this insn.  */
3223       if (redundant_insn_p (XVECEXP (pat, 0, 1), delay_insn, 0))
3224         {
3225           delete_from_delay_slot (XVECEXP (pat, 0, 1));
3226           next = prev_active_insn (next);
3227           continue;
3228         }
3229
3230       /* Now look only at the cases where we have a filled JUMP_INSN.  */
3231       if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3232           || ! condjump_p (XVECEXP (PATTERN (insn), 0, 0)))
3233         continue;
3234
3235       target_label = JUMP_LABEL (delay_insn);
3236
3237       if (target_label)
3238         {
3239           /* If this jump goes to another unconditional jump, thread it, but
3240              don't convert a jump into a RETURN here.  */
3241           trial = follow_jumps (target_label, 1);
3242           trial = prev_label (next_active_insn (trial));
3243           if (trial == 0 && target_label != 0)
3244             trial = find_end_label ();
3245
3246           if (trial != target_label)
3247             {
3248               redirect_jump (delay_insn, trial);
3249               target_label = trial;
3250             }
3251
3252           /* If the first insn at TARGET_LABEL is redundant with a previous
3253              insn, redirect the jump to the following insn process again.  */
3254           trial = next_active_insn (target_label);
3255           if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3256               && redundant_insn_p (trial, insn, 0))
3257             {
3258               trial = next_active_insn (trial);
3259               if (trial == 0)
3260                 target_label = find_end_label ();
3261               else
3262                 target_label = get_label_before (trial);
3263               redirect_jump (delay_insn, target_label);
3264               next = insn;
3265               continue;
3266             }
3267
3268           /* Similarly, if it is an unconditional jump with one insn in its
3269              delay list and that insn is redundant, thread the jump.  */
3270           if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3271               && XVECLEN (PATTERN (trial), 0) == 2
3272               && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3273               && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3274                   || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3275               && redundant_insn_p (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3276             {
3277               target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3278               if (target_label == 0)
3279                 target_label = find_end_label ();
3280               redirect_jump (delay_insn, target_label);
3281               next = insn;
3282               continue;
3283             }
3284         }
3285
3286       if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3287           && prev_active_insn (target_label) == insn
3288 #ifdef HAVE_cc0
3289           /* If the last insn in the delay slot sets CC0 for some insn,
3290              various code assumes that it is in a delay slot.  We could
3291              put it back where it belonged and delete the register notes,
3292              but it doesn't seem worhwhile in this uncommon case.  */
3293           && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3294                               REG_CC_USER, 0)
3295 #endif
3296           )
3297         {
3298           /* All this insn does is execute its delay list and jump to the
3299              following insn.  So delete the jump and just execute the delay
3300              list insns.
3301
3302              We do this by deleting the INSN containing the SEQUENCE, then
3303              re-emitting the insns separately, and then deleting the jump.
3304              This allows the count of the jump target to be properly
3305              decremented.  */
3306
3307           trial = PREV_INSN (insn);
3308           delete_insn (insn);
3309           emit_insn_after (pat, trial);
3310           delete_scheduled_jump (delay_insn);
3311           continue;
3312         }
3313
3314       /* See if this jump (with its delay slots) branches around another
3315          jump (without delay slots).  If so, invert this jump and point
3316          it to the target of the second jump.  We cannot do this for
3317          annulled jumps, though.  Again, don't convert a jump to a RETURN
3318          here.  */
3319       if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3320           && next && GET_CODE (next) == JUMP_INSN
3321           && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3322           && next_active_insn (target_label) == next_active_insn (next)
3323           && no_labels_between_p (insn, next))
3324         {
3325           rtx label = JUMP_LABEL (next);
3326           rtx old_label = JUMP_LABEL (delay_insn);
3327
3328           if (label == 0)
3329             label = find_end_label ();
3330
3331           /* Be careful how we do this to avoid deleting code or labels
3332              that are momentarily dead.  See similar optimization in jump.c  */
3333           if (old_label)
3334             ++LABEL_NUSES (old_label);
3335
3336           if (invert_jump (delay_insn, label))
3337             {
3338               delete_insn (next);
3339               next = insn;
3340             }
3341
3342           if (old_label && --LABEL_NUSES (old_label) == 0)
3343             delete_insn (old_label);
3344           continue;
3345         }
3346
3347       /* If we own the thread opposite the way this insn branches, see if we
3348          can merge its delay slots with following insns.  */
3349       if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3350           && own_thread_p (NEXT_INSN (insn), 0, 1))
3351         try_merge_delay_insns (insn, next);
3352       else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3353                && own_thread_p (target_label, target_label, 0))
3354         try_merge_delay_insns (insn, next_active_insn (target_label));
3355
3356       /* If we get here, we haven't deleted INSN.  But we may have deleted
3357          NEXT, so recompute it.  */
3358       next = next_active_insn (insn);
3359     }
3360 }
3361 \f
3362 #ifdef HAVE_return
3363
3364 /* Look for filled jumps to the end of function label.  We can try to convert
3365    them into RETURN insns if the insns in the delay slot are valid for the
3366    RETURN as well.  */
3367
3368 static void
3369 make_return_insns (first)
3370      rtx first;
3371 {
3372   rtx insn, jump_insn, pat;
3373   rtx real_return_label = end_of_function_label;
3374   int slots, i;
3375
3376   /* See if there is a RETURN insn in the function other than the one we
3377      made for END_OF_FUNCTION_LABEL.  If so, set up anything we can't change
3378      into a RETURN to jump to it.  */
3379   for (insn = first; insn; insn = NEXT_INSN (insn))
3380     if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3381       {
3382         real_return_label = get_label_before (insn);
3383         break;
3384       }
3385
3386   /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3387      was equal to END_OF_FUNCTION_LABEL.  */
3388   LABEL_NUSES (real_return_label)++;
3389
3390   /* Clear the list of insns to fill so we can use it.  */
3391   obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3392
3393   for (insn = first; insn; insn = NEXT_INSN (insn))
3394     {
3395       /* Only look at filled JUMP_INSNs that go to the end of function
3396          label.  */
3397       if (GET_CODE (insn) != INSN
3398           || GET_CODE (PATTERN (insn)) != SEQUENCE
3399           || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3400           || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3401         continue;
3402
3403       pat = PATTERN (insn);
3404       jump_insn = XVECEXP (pat, 0, 0);
3405
3406       /* If we can't make the jump into a RETURN, redirect it to the best
3407          RETURN and go on to the next insn.  */
3408       if (! redirect_jump (jump_insn, 0))
3409         {
3410           redirect_jump (jump_insn, real_return_label);
3411           continue;
3412         }
3413
3414       /* See if this RETURN can accept the insns current in its delay slot.
3415          It can if it has more or an equal number of slots and the contents
3416          of each is valid.  */
3417
3418       slots = num_delay_slots (jump_insn);
3419       if (slots >= XVECLEN (pat, 0) - 1)
3420         {
3421           for (i = 1; i < XVECLEN (pat, 0); i++)
3422             if (! (
3423 #ifdef ANNUL_IFFALSE_SLOTS
3424                    (INSN_ANNULLED_BRANCH_P (jump_insn)
3425                     && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3426                    ? eligible_for_annul_false (jump_insn, i - 1,
3427                                                XVECEXP (pat, 0, i)) :
3428 #endif
3429 #ifdef ANNUL_IFTRUE_SLOTS
3430                    (INSN_ANNULLED_BRANCH_P (jump_insn)
3431                     && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3432                    ? eligible_for_annul_true (jump_insn, i - 1,
3433                                               XVECEXP (pat, 0, i)) :
3434 #endif
3435                    eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i))))
3436               break;
3437         }
3438       else
3439         i = 0;
3440
3441       if (i == XVECLEN (pat, 0))
3442         continue;
3443
3444       /* We have to do something with this insn.  If it is an unconditional
3445          RETURN, delete the SEQUENCE and output the individual insns,
3446          followed by the RETURN.  Then set things up so we try to find
3447          insns for its delay slots, if it needs some.  */
3448       if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3449         {
3450           rtx prev = PREV_INSN (insn);
3451
3452           delete_insn (insn);
3453           for (i = 1; i < XVECLEN (pat, 0); i++)
3454             prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3455
3456           insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3457           emit_barrier_after (insn);
3458
3459           if (slots)
3460             obstack_ptr_grow (&unfilled_slots_obstack, insn);
3461         }
3462       else
3463         /* It is probably more efficient to keep this with its current
3464            delay slot as a branch to a RETURN.  */
3465         redirect_jump (jump_insn, real_return_label);
3466     }
3467
3468   /* Now delete REAL_RETURN_LABEL if we never used it.  Then try to fill any
3469      new delay slots we have created.  */
3470   if (--LABEL_NUSES (real_return_label) == 0)
3471     delete_insn (real_return_label);
3472
3473   fill_simple_delay_slots (first, 1);
3474   fill_simple_delay_slots (first, 0);
3475 }
3476 #endif
3477 \f
3478 /* Try to find insns to place in delay slots.  */
3479
3480 void
3481 dbr_schedule (first, file)
3482      rtx first;
3483      FILE *file;
3484 {
3485   rtx insn, next;
3486   int i;
3487 #if 0
3488   int old_flag_no_peephole = flag_no_peephole;
3489
3490   /* Execute `final' once in prescan mode to delete any insns that won't be
3491      used.  Don't let final try to do any peephole optimization--it will
3492      ruin dataflow information for this pass.  */
3493
3494   flag_no_peephole = 1;
3495   final (first, 0, NO_DEBUG, 1, 1);
3496   flag_no_peephole = old_flag_no_peephole;
3497 #endif
3498
3499   /* Find the highest INSN_UID and allocate and initialize our map from
3500      INSN_UID's to position in code.  */
3501   for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3502     if (INSN_UID (insn) > max_uid)
3503       max_uid = INSN_UID (insn);
3504
3505   uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
3506   for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3507     uid_to_ruid[INSN_UID (insn)] = i;
3508
3509   /* Initialize the list of insns that need filling.  */
3510   if (unfilled_firstobj == 0)
3511     {
3512       gcc_obstack_init (&unfilled_slots_obstack);
3513       unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3514     }
3515
3516   for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3517     {
3518       rtx target;
3519
3520       INSN_ANNULLED_BRANCH_P (insn) = 0;
3521       INSN_FROM_TARGET_P (insn) = 0;
3522
3523       /* Skip vector tables.  We can't get attributes for them.  */
3524       if (GET_CODE (insn) == JUMP_INSN
3525           && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3526               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3527         continue;
3528
3529       if (num_delay_slots (insn) > 0)
3530         obstack_ptr_grow (&unfilled_slots_obstack, insn);
3531
3532       /* Ensure all jumps go to the last of a set of consecutive labels.  */
3533       if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn)
3534           && JUMP_LABEL (insn) != 0
3535           && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
3536               != JUMP_LABEL (insn)))
3537         redirect_jump (insn, target);
3538     }
3539
3540   /* Indicate what resources are required to be valid at the end of the current
3541      function.  The condition code never is and memory always is.  If the
3542      frame pointer is needed, it is and so is the stack pointer unless
3543      EXIT_IGNORE_STACK is non-zero.  If the frame pointer is not needed, the
3544      stack pointer is.  In addition, registers used to return the function
3545      value are needed.  */
3546
3547   end_of_function_needs.cc = 0;
3548   end_of_function_needs.memory = 1;
3549   CLEAR_HARD_REG_SET (end_of_function_needs.regs);
3550
3551   if (frame_pointer_needed)
3552     {
3553       SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
3554 #ifdef EXIT_IGNORE_STACK
3555       if (! EXIT_IGNORE_STACK)
3556 #endif
3557         SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3558     }
3559   else
3560     SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3561
3562   if (current_function_return_rtx != 0
3563       && GET_CODE (current_function_return_rtx) == REG)
3564     mark_referenced_resources (current_function_return_rtx,
3565                                &end_of_function_needs, 0);
3566
3567   /* Show we haven't computed an end-of-function label yet.  */
3568   end_of_function_label = 0;
3569
3570   /* Allocate and initialize the tables used by mark_target_live_regs.  */
3571   target_hash_table
3572     = (struct target_info **) alloca ((TARGET_HASH_PRIME
3573                                        * sizeof (struct target_info *)));
3574   bzero (target_hash_table, TARGET_HASH_PRIME * sizeof (struct target_info *));
3575
3576   bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
3577   bzero (bb_ticks, n_basic_blocks * sizeof (int));
3578
3579   /* Initialize the statistics for this function.  */
3580   bzero (num_insns_needing_delays, sizeof num_insns_needing_delays);
3581   bzero (num_filled_delays, sizeof num_filled_delays);
3582
3583   /* Now do the delay slot filling.  Try everything twice in case earlier
3584      changes make more slots fillable.  */
3585
3586   for (reorg_pass_number = 0;
3587        reorg_pass_number < MAX_REORG_PASSES;
3588        reorg_pass_number++)
3589     {
3590       fill_simple_delay_slots (first, 1);
3591       fill_simple_delay_slots (first, 0);
3592       fill_eager_delay_slots (first);
3593       relax_delay_slots (first);
3594     }
3595
3596   /* Delete any USE insns made by update_block; subsequent passes don't need
3597      them or know how to deal with them.  */
3598   for (insn = first; insn; insn = next)
3599     {
3600       next = NEXT_INSN (insn);
3601
3602       if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3603           && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
3604               || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN
3605               || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN))
3606         next = delete_insn (insn);
3607     }
3608
3609   /* If we made an end of function label, indicate that it is now
3610      safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3611      If it is now unused, delete it.  */
3612   if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3613     delete_insn (end_of_function_label);
3614
3615 #ifdef HAVE_return
3616   if (HAVE_return && end_of_function_label != 0)
3617     make_return_insns (first);
3618 #endif
3619
3620   obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3621
3622   /* It is not clear why the line below is needed, but it does seem to be.  */
3623   unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3624
3625   if (file)
3626     {
3627       register int i, j, need_comma;
3628
3629       for (reorg_pass_number = 0;
3630            reorg_pass_number < MAX_REORG_PASSES;
3631            reorg_pass_number++)
3632         {
3633           fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3634           for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3635             {
3636               need_comma = 0;
3637               fprintf (file, ";; Reorg function #%d\n", i);
3638
3639               fprintf (file, ";; %d insns needing delay slots\n;; ",
3640                        num_insns_needing_delays[i][reorg_pass_number]);
3641
3642               for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
3643                 if (num_filled_delays[i][j][reorg_pass_number])
3644                   {
3645                     if (need_comma)
3646                       fprintf (file, ", ");
3647                     need_comma = 1;
3648                     fprintf (file, "%d got %d delays",
3649                              num_filled_delays[i][j][reorg_pass_number], j);
3650                   }
3651               fprintf (file, "\n");
3652             }
3653         }
3654     }
3655 }
3656 #endif /* DELAY_SLOTS */