gcc/reorg.c

   1 /* Perform instruction reorganizations for delay slot filling.
   2    Copyright (C) 1992, 93, 94, 95, 96, 97, 1998 Free Software Foundation, Inc.
   3    Contributed by Richard Kenner (kenner@vlsi1.ultra.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, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 /* Instruction reorganization pass.
  24
  25    This pass runs after register allocation and final jump
  26    optimization.  It should be the last pass to run before peephole.
  27    It serves primarily to fill delay slots of insns, typically branch
  28    and call insns.  Other insns typically involve more complicated
  29    interactions of data dependencies and resource constraints, and
  30    are better handled by scheduling before register allocation (by the
  31    function `schedule_insns').
  32
  33    The Branch Penalty is the number of extra cycles that are needed to
  34    execute a branch insn.  On an ideal machine, branches take a single
  35    cycle, and the Branch Penalty is 0.  Several RISC machines approach
  36    branch delays differently:
  37
  38    The MIPS and AMD 29000 have a single branch delay slot.  Most insns
  39    (except other branches) can be used to fill this slot.  When the
  40    slot is filled, two insns execute in two cycles, reducing the
  41    branch penalty to zero.
  42
  43    The Motorola 88000 conditionally exposes its branch delay slot,
  44    so code is shorter when it is turned off, but will run faster
  45    when useful insns are scheduled there.
  46
  47    The IBM ROMP has two forms of branch and call insns, both with and
  48    without a delay slot.  Much like the 88k, insns not using the delay
  49    slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
  50
  51    The SPARC always has a branch delay slot, but its effects can be
  52    annulled when the branch is not taken.  This means that failing to
  53    find other sources of insns, we can hoist an insn from the branch
  54    target that would only be safe to execute knowing that the branch
  55    is taken.
  56
  57    The HP-PA always has a branch delay slot.  For unconditional branches
  58    its effects can be annulled when the branch is taken.  The effects
  59    of the delay slot in a conditional branch can be nullified for forward
  60    taken branches, or for untaken backward branches.  This means
  61    we can hoist insns from the fall-through path for forward branches or
  62    steal insns from the target of backward branches.
  63
  64    Three techniques for filling delay slots have been implemented so far:
  65
  66    (1) `fill_simple_delay_slots' is the simplest, most efficient way
  67    to fill delay slots.  This pass first looks for insns which come
  68    from before the branch and which are safe to execute after the
  69    branch.  Then it searches after the insn requiring delay slots or,
  70    in the case of a branch, for insns that are after the point at
  71    which the branch merges into the fallthrough code, if such a point
  72    exists.  When such insns are found, the branch penalty decreases
  73    and no code expansion takes place.
  74
  75    (2) `fill_eager_delay_slots' is more complicated: it is used for
  76    scheduling conditional jumps, or for scheduling jumps which cannot
  77    be filled using (1).  A machine need not have annulled jumps to use
  78    this strategy, but it helps (by keeping more options open).
  79    `fill_eager_delay_slots' tries to guess the direction the branch
  80    will go; if it guesses right 100% of the time, it can reduce the
  81    branch penalty as much as `fill_simple_delay_slots' does.  If it
  82    guesses wrong 100% of the time, it might as well schedule nops (or
  83    on the m88k, unexpose the branch slot).  When
  84    `fill_eager_delay_slots' takes insns from the fall-through path of
  85    the jump, usually there is no code expansion; when it takes insns
  86    from the branch target, there is code expansion if it is not the
  87    only way to reach that target.
  88
  89    (3) `relax_delay_slots' uses a set of rules to simplify code that
  90    has been reorganized by (1) and (2).  It finds cases where
  91    conditional test can be eliminated, jumps can be threaded, extra
  92    insns can be eliminated, etc.  It is the job of (1) and (2) to do a
  93    good job of scheduling locally; `relax_delay_slots' takes care of
  94    making the various individual schedules work well together.  It is
  95    especially tuned to handle the control flow interactions of branch
  96    insns.  It does nothing for insns with delay slots that do not
  97    branch.
  98
  99    On machines that use CC0, we are very conservative.  We will not make
 100    a copy of an insn involving CC0 since we want to maintain a 1-1
 101    correspondence between the insn that sets and uses CC0.  The insns are
 102    allowed to be separated by placing an insn that sets CC0 (but not an insn
 103    that uses CC0; we could do this, but it doesn't seem worthwhile) in a
 104    delay slot.  In that case, we point each insn at the other with REG_CC_USER
 105    and REG_CC_SETTER notes.  Note that these restrictions affect very few
 106    machines because most RISC machines with delay slots will not use CC0
 107    (the RT is the only known exception at this point).
 108
 109    Not yet implemented:
 110
 111    The Acorn Risc Machine can conditionally execute most insns, so
 112    it is profitable to move single insns into a position to execute
 113    based on the condition code of the previous insn.
 114
 115    The HP-PA can conditionally nullify insns, providing a similar
 116    effect to the ARM, differing mostly in which insn is "in charge".   */
 117
 118 #include "config.h"
 119 #include "system.h"
 120 #include "rtl.h"
 121 #include "expr.h"
 122 #include "insn-config.h"
 123 #include "conditions.h"
 124 #include "hard-reg-set.h"
 125 #include "basic-block.h"
 126 #include "regs.h"
 127 #include "insn-flags.h"
 128 #include "recog.h"
 129 #include "flags.h"
 130 #include "output.h"
 131 #include "obstack.h"
 132 #include "insn-attr.h"
 133
 134 /* Import list of registers used as spill regs from reload.  */
 135 extern HARD_REG_SET used_spill_regs;
 136
 137 /* Import highest label used in function at end of reload.  */
 138 extern int max_label_num_after_reload;
 139
 140
 141 #ifdef DELAY_SLOTS
 142
 143 #define obstack_chunk_alloc xmalloc
 144 #define obstack_chunk_free free
 145
 146 #ifndef ANNUL_IFTRUE_SLOTS
 147 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
 148 #endif
 149 #ifndef ANNUL_IFFALSE_SLOTS
 150 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
 151 #endif
 152
 153 /* Insns which have delay slots that have not yet been filled.  */
 154
 155 static struct obstack unfilled_slots_obstack;
 156 static rtx *unfilled_firstobj;
 157
 158 /* Define macros to refer to the first and last slot containing unfilled
 159    insns.  These are used because the list may move and its address
 160    should be recomputed at each use.  */
 161
 162 #define unfilled_slots_base     \
 163   ((rtx *) obstack_base (&unfilled_slots_obstack))
 164
 165 #define unfilled_slots_next     \
 166   ((rtx *) obstack_next_free (&unfilled_slots_obstack))
 167
 168 /* This structure is used to indicate which hardware resources are set or
 169    needed by insns so far.  */
 170
 171 struct resources
 172 {
 173   char memory;                  /* Insn sets or needs a memory location.  */
 174   char unch_memory;             /* Insn sets of needs a "unchanging" MEM.  */
 175   char volatil;                 /* Insn sets or needs a volatile memory loc.  */
 176   char cc;                      /* Insn sets or needs the condition codes.  */
 177   HARD_REG_SET regs;            /* Which registers are set or needed.  */
 178 };
 179
 180 /* Macro to clear all resources.  */
 181 #define CLEAR_RESOURCE(RES)     \
 182  do { (RES)->memory = (RES)->unch_memory = (RES)->volatil = (RES)->cc = 0; \
 183       CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
 184
 185 /* Indicates what resources are required at the beginning of the epilogue.  */
 186 static struct resources start_of_epilogue_needs;
 187
 188 /* Indicates what resources are required at function end.  */
 189 static struct resources end_of_function_needs;
 190
 191 /* Points to the label before the end of the function.  */
 192 static rtx end_of_function_label;
 193
 194 /* This structure is used to record liveness information at the targets or
 195    fallthrough insns of branches.  We will most likely need the information
 196    at targets again, so save them in a hash table rather than recomputing them
 197    each time.  */
 198
 199 struct target_info
 200 {
 201   int uid;                      /* INSN_UID of target.  */
 202   struct target_info *next;     /* Next info for same hash bucket.  */
 203   HARD_REG_SET live_regs;       /* Registers live at target.  */
 204   int block;                    /* Basic block number containing target.  */
 205   int bb_tick;                  /* Generation count of basic block info.  */
 206 };
 207
 208 #define TARGET_HASH_PRIME 257
 209
 210 /* Define the hash table itself.  */
 211 static struct target_info **target_hash_table;
 212
 213 /* For each basic block, we maintain a generation number of its basic
 214    block info, which is updated each time we move an insn from the
 215    target of a jump.  This is the generation number indexed by block
 216    number.  */
 217
 218 static int *bb_ticks;
 219
 220 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
 221    not always monotonically increase.  */
 222 static int *uid_to_ruid;
 223
 224 /* Highest valid index in `uid_to_ruid'.  */
 225 static int max_uid;
 226
 227 static void mark_referenced_resources PROTO((rtx, struct resources *, int));
 228 static void mark_set_resources  PROTO((rtx, struct resources *, int, int));
 229 static int stop_search_p        PROTO((rtx, int));
 230 static int resource_conflicts_p PROTO((struct resources *,
 231                                        struct resources *));
 232 static int insn_references_resource_p PROTO((rtx, struct resources *, int));
 233 static int insn_sets_resource_p PROTO((rtx, struct resources *, int));
 234 static rtx find_end_label       PROTO((void));
 235 static rtx emit_delay_sequence  PROTO((rtx, rtx, int));
 236 static rtx add_to_delay_list    PROTO((rtx, rtx));
 237 static void delete_from_delay_slot PROTO((rtx));
 238 static void delete_scheduled_jump PROTO((rtx));
 239 static void note_delay_statistics PROTO((int, int));
 240 static rtx optimize_skip        PROTO((rtx));
 241 static int get_jump_flags PROTO((rtx, rtx));
 242 static int rare_destination PROTO((rtx));
 243 static int mostly_true_jump     PROTO((rtx, rtx));
 244 static rtx get_branch_condition PROTO((rtx, rtx));
 245 static int condition_dominates_p PROTO((rtx, rtx));
 246 static rtx steal_delay_list_from_target PROTO((rtx, rtx, rtx, rtx,
 247                                                struct resources *,
 248                                                struct resources *,
 249                                                struct resources *,
 250                                                int, int *, int *, rtx *));
 251 static rtx steal_delay_list_from_fallthrough PROTO((rtx, rtx, rtx, rtx,
 252                                                     struct resources *,
 253                                                     struct resources *,
 254                                                     struct resources *,
 255                                                     int, int *, int *));
 256 static void try_merge_delay_insns PROTO((rtx, rtx));
 257 static rtx redundant_insn       PROTO((rtx, rtx, rtx));
 258 static int own_thread_p         PROTO((rtx, rtx, int));
 259 static int find_basic_block     PROTO((rtx));
 260 static void update_block        PROTO((rtx, rtx));
 261 static int reorg_redirect_jump PROTO((rtx, rtx));
 262 static void update_reg_dead_notes PROTO((rtx, rtx));
 263 static void fix_reg_dead_note PROTO((rtx, rtx));
 264 static void update_reg_unused_notes PROTO((rtx, rtx));
 265 static void update_live_status  PROTO((rtx, rtx));
 266 static rtx next_insn_no_annul   PROTO((rtx));
 267 static rtx find_dead_or_set_registers PROTO ((rtx, struct resources *, rtx *,
 268                                               int, struct resources,
 269                                               struct resources));
 270 static void mark_target_live_regs PROTO((rtx, struct resources *));
 271 static void fill_simple_delay_slots PROTO((int));
 272 static rtx fill_slots_from_thread PROTO((rtx, rtx, rtx, rtx, int, int,
 273                                          int, int, int *, rtx));
 274 static void fill_eager_delay_slots PROTO((void));
 275 static void relax_delay_slots   PROTO((rtx));
 276 static void make_return_insns   PROTO((rtx));
 277 static int redirect_with_delay_slots_safe_p PROTO ((rtx, rtx, rtx));
 278 static int redirect_with_delay_list_safe_p PROTO ((rtx, rtx, rtx));
 279 \f
 280 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
 281    which resources are references by the insn.  If INCLUDE_DELAYED_EFFECTS
 282    is TRUE, resources used by the called routine will be included for
 283    CALL_INSNs.  */
 284
 285 static void
 286 mark_referenced_resources (x, res, include_delayed_effects)
 287      register rtx x;
 288      register struct resources *res;
 289      register int include_delayed_effects;
 290 {
 291   register enum rtx_code code = GET_CODE (x);
 292   register int i, j;
 293   register char *format_ptr;
 294
 295   /* Handle leaf items for which we set resource flags.  Also, special-case
 296      CALL, SET and CLOBBER operators.  */
 297   switch (code)
 298     {
 299     case CONST:
 300     case CONST_INT:
 301     case CONST_DOUBLE:
 302     case PC:
 303     case SYMBOL_REF:
 304     case LABEL_REF:
 305       return;
 306
 307     case SUBREG:
 308       if (GET_CODE (SUBREG_REG (x)) != REG)
 309         mark_referenced_resources (SUBREG_REG (x), res, 0);
 310       else
 311         {
 312           int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
 313           int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
 314           for (i = regno; i < last_regno; i++)
 315             SET_HARD_REG_BIT (res->regs, i);
 316         }
 317       return;
 318
 319     case REG:
 320       for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
 321         SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
 322       return;
 323
 324     case MEM:
 325       /* If this memory shouldn't change, it really isn't referencing
 326          memory.  */
 327       if (RTX_UNCHANGING_P (x))
 328         res->unch_memory = 1;
 329       else
 330         res->memory = 1;
 331       res->volatil = MEM_VOLATILE_P (x);
 332
 333       /* Mark registers used to access memory.  */
 334       mark_referenced_resources (XEXP (x, 0), res, 0);
 335       return;
 336
 337     case CC0:
 338       res->cc = 1;
 339       return;
 340
 341     case UNSPEC_VOLATILE:
 342     case ASM_INPUT:
 343     case TRAP_IF:
 344       /* Traditional asm's are always volatile.  */
 345       res->volatil = 1;
 346       return;
 347
 348     case ASM_OPERANDS:
 349       res->volatil = MEM_VOLATILE_P (x);
 350
 351       /* For all ASM_OPERANDS, we must traverse the vector of input operands.
 352          We can not just fall through here since then we would be confused
 353          by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
 354          traditional asms unlike their normal usage.  */
 355
 356       for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
 357         mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
 358       return;
 359
 360     case CALL:
 361       /* The first operand will be a (MEM (xxx)) but doesn't really reference
 362          memory.  The second operand may be referenced, though.  */
 363       mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
 364       mark_referenced_resources (XEXP (x, 1), res, 0);
 365       return;
 366
 367     case SET:
 368       /* Usually, the first operand of SET is set, not referenced.  But
 369          registers used to access memory are referenced.  SET_DEST is
 370          also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT.  */
 371
 372       mark_referenced_resources (SET_SRC (x), res, 0);
 373
 374       x = SET_DEST (x);
 375       if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
 376         mark_referenced_resources (x, res, 0);
 377       else if (GET_CODE (x) == SUBREG)
 378         x = SUBREG_REG (x);
 379       if (GET_CODE (x) == MEM)
 380         mark_referenced_resources (XEXP (x, 0), res, 0);
 381       return;
 382
 383     case CLOBBER:
 384       return;
 385
 386     case CALL_INSN:
 387       if (include_delayed_effects)
 388         {
 389           /* A CALL references memory, the frame pointer if it exists, the
 390              stack pointer, any global registers and any registers given in
 391              USE insns immediately in front of the CALL.
 392
 393              However, we may have moved some of the parameter loading insns
 394              into the delay slot of this CALL.  If so, the USE's for them
 395              don't count and should be skipped.  */
 396           rtx insn = PREV_INSN (x);
 397           rtx sequence = 0;
 398           int seq_size = 0;
 399           rtx next = NEXT_INSN (x);
 400           int i;
 401
 402           /* If we are part of a delay slot sequence, point at the SEQUENCE.  */
 403           if (NEXT_INSN (insn) != x)
 404             {
 405               next = NEXT_INSN (NEXT_INSN (insn));
 406               sequence = PATTERN (NEXT_INSN (insn));
 407               seq_size = XVECLEN (sequence, 0);
 408               if (GET_CODE (sequence) != SEQUENCE)
 409                 abort ();
 410             }
 411
 412           res->memory = 1;
 413           SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
 414           if (frame_pointer_needed)
 415             {
 416               SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
 417 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 418               SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM);
 419 #endif
 420             }
 421
 422           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 423             if (global_regs[i])
 424               SET_HARD_REG_BIT (res->regs, i);
 425
 426           /* Check for a NOTE_INSN_SETJMP.  If it exists, then we must
 427              assume that this call can need any register.
 428
 429              This is done to be more conservative about how we handle setjmp.
 430              We assume that they both use and set all registers.  Using all
 431              registers ensures that a register will not be considered dead
 432              just because it crosses a setjmp call.  A register should be
 433              considered dead only if the setjmp call returns non-zero.  */
 434           if (next && GET_CODE (next) == NOTE
 435               && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
 436             SET_HARD_REG_SET (res->regs);
 437
 438           {
 439             rtx link;
 440
 441             for (link = CALL_INSN_FUNCTION_USAGE (x);
 442                  link;
 443                  link = XEXP (link, 1))
 444               if (GET_CODE (XEXP (link, 0)) == USE)
 445                 {
 446                   for (i = 1; i < seq_size; i++)
 447                     {
 448                       rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
 449                       if (GET_CODE (slot_pat) == SET
 450                           && rtx_equal_p (SET_DEST (slot_pat),
 451                                           SET_DEST (XEXP (link, 0))))
 452                         break;
 453                     }
 454                   if (i >= seq_size)
 455                     mark_referenced_resources (SET_DEST (XEXP (link, 0)),
 456                                                res, 0);
 457                 }
 458           }
 459         }
 460
 461       /* ... fall through to other INSN processing ...  */
 462
 463     case INSN:
 464     case JUMP_INSN:
 465
 466 #ifdef INSN_REFERENCES_ARE_DELAYED
 467       if (! include_delayed_effects
 468           && INSN_REFERENCES_ARE_DELAYED (x))
 469         return;
 470 #endif
 471
 472       /* No special processing, just speed up.  */
 473       mark_referenced_resources (PATTERN (x), res, include_delayed_effects);
 474       return;
 475
 476     default:
 477       break;
 478     }
 479
 480   /* Process each sub-expression and flag what it needs.  */
 481   format_ptr = GET_RTX_FORMAT (code);
 482   for (i = 0; i < GET_RTX_LENGTH (code); i++)
 483     switch (*format_ptr++)
 484       {
 485       case 'e':
 486         mark_referenced_resources (XEXP (x, i), res, include_delayed_effects);
 487         break;
 488
 489       case 'E':
 490         for (j = 0; j < XVECLEN (x, i); j++)
 491           mark_referenced_resources (XVECEXP (x, i, j), res,
 492                                      include_delayed_effects);
 493         break;
 494       }
 495 }
 496 \f
 497 /* Given X, a part of an insn, and a pointer to a `struct resource',
 498    RES, indicate which resources are modified by the insn. If
 499    INCLUDE_DELAYED_EFFECTS is nonzero, also mark resources potentially
 500    set by the called routine.
 501
 502    If IN_DEST is nonzero, it means we are inside a SET.  Otherwise,
 503    objects are being referenced instead of set.
 504
 505    We never mark the insn as modifying the condition code unless it explicitly
 506    SETs CC0 even though this is not totally correct.  The reason for this is
 507    that we require a SET of CC0 to immediately precede the reference to CC0.
 508    So if some other insn sets CC0 as a side-effect, we know it cannot affect
 509    our computation and thus may be placed in a delay slot.   */
 510
 511 static void
 512 mark_set_resources (x, res, in_dest, include_delayed_effects)
 513      register rtx x;
 514      register struct resources *res;
 515      int in_dest;
 516      int include_delayed_effects;
 517 {
 518   register enum rtx_code code;
 519   register int i, j;
 520   register char *format_ptr;
 521
 522  restart:
 523
 524   code = GET_CODE (x);
 525
 526   switch (code)
 527     {
 528     case NOTE:
 529     case BARRIER:
 530     case CODE_LABEL:
 531     case USE:
 532     case CONST_INT:
 533     case CONST_DOUBLE:
 534     case LABEL_REF:
 535     case SYMBOL_REF:
 536     case CONST:
 537     case PC:
 538       /* These don't set any resources.  */
 539       return;
 540
 541     case CC0:
 542       if (in_dest)
 543         res->cc = 1;
 544       return;
 545
 546     case CALL_INSN:
 547       /* Called routine modifies the condition code, memory, any registers
 548          that aren't saved across calls, global registers and anything
 549          explicitly CLOBBERed immediately after the CALL_INSN.  */
 550
 551       if (include_delayed_effects)
 552         {
 553           rtx next = NEXT_INSN (x);
 554           rtx prev = PREV_INSN (x);
 555           rtx link;
 556
 557           res->cc = res->memory = 1;
 558           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 559             if (call_used_regs[i] || global_regs[i])
 560               SET_HARD_REG_BIT (res->regs, i);
 561
 562           /* If X is part of a delay slot sequence, then NEXT should be
 563              the first insn after the sequence.  */
 564           if (NEXT_INSN (prev) != x)
 565             next = NEXT_INSN (NEXT_INSN (prev));
 566
 567           for (link = CALL_INSN_FUNCTION_USAGE (x);
 568                link; link = XEXP (link, 1))
 569             if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 570               mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1, 0);
 571
 572           /* Check for a NOTE_INSN_SETJMP.  If it exists, then we must
 573              assume that this call can clobber any register.  */
 574           if (next && GET_CODE (next) == NOTE
 575               && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
 576             SET_HARD_REG_SET (res->regs);
 577         }
 578
 579       /* ... and also what it's RTL says it modifies, if anything.  */
 580
 581     case JUMP_INSN:
 582     case INSN:
 583
 584         /* An insn consisting of just a CLOBBER (or USE) is just for flow
 585            and doesn't actually do anything, so we ignore it.  */
 586
 587 #ifdef INSN_SETS_ARE_DELAYED
 588       if (! include_delayed_effects
 589           && INSN_SETS_ARE_DELAYED (x))
 590         return;
 591 #endif
 592
 593       x = PATTERN (x);
 594       if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
 595         goto restart;
 596       return;
 597
 598     case SET:
 599       /* If the source of a SET is a CALL, this is actually done by
 600          the called routine.  So only include it if we are to include the
 601          effects of the calling routine.  */
 602
 603       mark_set_resources (SET_DEST (x), res,
 604                           (include_delayed_effects
 605                            || GET_CODE (SET_SRC (x)) != CALL),
 606                           0);
 607
 608       mark_set_resources (SET_SRC (x), res, 0, 0);
 609       return;
 610
 611     case CLOBBER:
 612       mark_set_resources (XEXP (x, 0), res, 1, 0);
 613       return;
 614
 615     case SEQUENCE:
 616       for (i = 0; i < XVECLEN (x, 0); i++)
 617         if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0))
 618                && INSN_FROM_TARGET_P (XVECEXP (x, 0, i))))
 619           mark_set_resources (XVECEXP (x, 0, i), res, 0,
 620                               include_delayed_effects);
 621       return;
 622
 623     case POST_INC:
 624     case PRE_INC:
 625     case POST_DEC:
 626     case PRE_DEC:
 627       mark_set_resources (XEXP (x, 0), res, 1, 0);
 628       return;
 629
 630     case ZERO_EXTRACT:
 631       mark_set_resources (XEXP (x, 0), res, in_dest, 0);
 632       mark_set_resources (XEXP (x, 1), res, 0, 0);
 633       mark_set_resources (XEXP (x, 2), res, 0, 0);
 634       return;
 635
 636     case MEM:
 637       if (in_dest)
 638         {
 639           res->memory = 1;
 640           res->unch_memory = RTX_UNCHANGING_P (x);
 641           res->volatil = MEM_VOLATILE_P (x);
 642         }
 643
 644       mark_set_resources (XEXP (x, 0), res, 0, 0);
 645       return;
 646
 647     case SUBREG:
 648       if (in_dest)
 649         {
 650           if (GET_CODE (SUBREG_REG (x)) != REG)
 651             mark_set_resources (SUBREG_REG (x), res,
 652                                 in_dest, include_delayed_effects);
 653           else
 654             {
 655               int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
 656               int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
 657               for (i = regno; i < last_regno; i++)
 658                 SET_HARD_REG_BIT (res->regs, i);
 659             }
 660         }
 661       return;
 662
 663     case REG:
 664       if (in_dest)
 665         for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
 666           SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
 667       return;
 668
 669     default:
 670       break;
 671     }
 672
 673   /* Process each sub-expression and flag what it needs.  */
 674   format_ptr = GET_RTX_FORMAT (code);
 675   for (i = 0; i < GET_RTX_LENGTH (code); i++)
 676     switch (*format_ptr++)
 677       {
 678       case 'e':
 679         mark_set_resources (XEXP (x, i), res, in_dest, include_delayed_effects);
 680         break;
 681
 682       case 'E':
 683         for (j = 0; j < XVECLEN (x, i); j++)
 684           mark_set_resources (XVECEXP (x, i, j), res, in_dest,
 685                               include_delayed_effects);
 686         break;
 687       }
 688 }
 689 \f
 690 /* Return TRUE if this insn should stop the search for insn to fill delay
 691    slots.  LABELS_P indicates that labels should terminate the search.
 692    In all cases, jumps terminate the search.  */
 693
 694 static int
 695 stop_search_p (insn, labels_p)
 696      rtx insn;
 697      int labels_p;
 698 {
 699   if (insn == 0)
 700     return 1;
 701
 702   switch (GET_CODE (insn))
 703     {
 704     case NOTE:
 705     case CALL_INSN:
 706       return 0;
 707
 708     case CODE_LABEL:
 709       return labels_p;
 710
 711     case JUMP_INSN:
 712     case BARRIER:
 713       return 1;
 714
 715     case INSN:
 716       /* OK unless it contains a delay slot or is an `asm' insn of some type.
 717          We don't know anything about these.  */
 718       return (GET_CODE (PATTERN (insn)) == SEQUENCE
 719               || GET_CODE (PATTERN (insn)) == ASM_INPUT
 720               || asm_noperands (PATTERN (insn)) >= 0);
 721
 722     default:
 723       abort ();
 724     }
 725 }
 726 \f
 727 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
 728    resource set contains a volatile memory reference.  Otherwise, return FALSE.  */
 729
 730 static int
 731 resource_conflicts_p (res1, res2)
 732      struct resources *res1, *res2;
 733 {
 734   if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
 735       || (res1->unch_memory && res2->unch_memory)
 736       || res1->volatil || res2->volatil)
 737     return 1;
 738
 739 #ifdef HARD_REG_SET
 740   return (res1->regs & res2->regs) != HARD_CONST (0);
 741 #else
 742   {
 743     int i;
 744
 745     for (i = 0; i < HARD_REG_SET_LONGS; i++)
 746       if ((res1->regs[i] & res2->regs[i]) != 0)
 747         return 1;
 748     return 0;
 749   }
 750 #endif
 751 }
 752
 753 /* Return TRUE if any resource marked in RES, a `struct resources', is
 754    referenced by INSN.  If INCLUDE_DELAYED_EFFECTS is set, return if the called
 755    routine is using those resources.
 756
 757    We compute this by computing all the resources referenced by INSN and
 758    seeing if this conflicts with RES.  It might be faster to directly check
 759    ourselves, and this is the way it used to work, but it means duplicating
 760    a large block of complex code.  */
 761
 762 static int
 763 insn_references_resource_p (insn, res, include_delayed_effects)
 764      register rtx insn;
 765      register struct resources *res;
 766      int include_delayed_effects;
 767 {
 768   struct resources insn_res;
 769
 770   CLEAR_RESOURCE (&insn_res);
 771   mark_referenced_resources (insn, &insn_res, include_delayed_effects);
 772   return resource_conflicts_p (&insn_res, res);
 773 }
 774
 775 /* Return TRUE if INSN modifies resources that are marked in RES.
 776    INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
 777    included.   CC0 is only modified if it is explicitly set; see comments
 778    in front of mark_set_resources for details.  */
 779
 780 static int
 781 insn_sets_resource_p (insn, res, include_delayed_effects)
 782      register rtx insn;
 783      register struct resources *res;
 784      int include_delayed_effects;
 785 {
 786   struct resources insn_sets;
 787
 788   CLEAR_RESOURCE (&insn_sets);
 789   mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
 790   return resource_conflicts_p (&insn_sets, res);
 791 }
 792 \f
 793 /* Find a label at the end of the function or before a RETURN.  If there is
 794    none, make one.  */
 795
 796 static rtx
 797 find_end_label ()
 798 {
 799   rtx insn;
 800
 801   /* If we found one previously, return it.  */
 802   if (end_of_function_label)
 803     return end_of_function_label;
 804
 805   /* Otherwise, see if there is a label at the end of the function.  If there
 806      is, it must be that RETURN insns aren't needed, so that is our return
 807      label and we don't have to do anything else.  */
 808
 809   insn = get_last_insn ();
 810   while (GET_CODE (insn) == NOTE
 811          || (GET_CODE (insn) == INSN
 812              && (GET_CODE (PATTERN (insn)) == USE
 813                  || GET_CODE (PATTERN (insn)) == CLOBBER)))
 814     insn = PREV_INSN (insn);
 815
 816   /* When a target threads its epilogue we might already have a
 817      suitable return insn.  If so put a label before it for the
 818      end_of_function_label.  */
 819   if (GET_CODE (insn) == BARRIER
 820       && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
 821       && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
 822     {
 823       rtx temp = PREV_INSN (PREV_INSN (insn));
 824       end_of_function_label = gen_label_rtx ();
 825       LABEL_NUSES (end_of_function_label) = 0;
 826
 827       /* Put the label before an USE insns that may proceed the RETURN insn.  */
 828       while (GET_CODE (temp) == USE)
 829         temp = PREV_INSN (temp);
 830
 831       emit_label_after (end_of_function_label, temp);
 832     }
 833
 834   else if (GET_CODE (insn) == CODE_LABEL)
 835     end_of_function_label = insn;
 836   else
 837     {
 838       /* Otherwise, make a new label and emit a RETURN and BARRIER,
 839          if needed.  */
 840       end_of_function_label = gen_label_rtx ();
 841       LABEL_NUSES (end_of_function_label) = 0;
 842       emit_label (end_of_function_label);
 843 #ifdef HAVE_return
 844       if (HAVE_return)
 845         {
 846           /* The return we make may have delay slots too.  */
 847           rtx insn = gen_return ();
 848           insn = emit_jump_insn (insn);
 849           emit_barrier ();
 850           if (num_delay_slots (insn) > 0)
 851             obstack_ptr_grow (&unfilled_slots_obstack, insn);
 852         }
 853 #endif
 854     }
 855
 856   /* Show one additional use for this label so it won't go away until
 857      we are done.  */
 858   ++LABEL_NUSES (end_of_function_label);
 859
 860   return end_of_function_label;
 861 }
 862 \f
 863 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
 864    the pattern of INSN with the SEQUENCE.
 865
 866    Chain the insns so that NEXT_INSN of each insn in the sequence points to
 867    the next and NEXT_INSN of the last insn in the sequence points to
 868    the first insn after the sequence.  Similarly for PREV_INSN.  This makes
 869    it easier to scan all insns.
 870
 871    Returns the SEQUENCE that replaces INSN.  */
 872
 873 static rtx
 874 emit_delay_sequence (insn, list, length)
 875      rtx insn;
 876      rtx list;
 877      int length;
 878 {
 879   register int i = 1;
 880   register rtx li;
 881   int had_barrier = 0;
 882
 883   /* Allocate the rtvec to hold the insns and the SEQUENCE.  */
 884   rtvec seqv = rtvec_alloc (length + 1);
 885   rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
 886   rtx seq_insn = make_insn_raw (seq);
 887   rtx first = get_insns ();
 888   rtx last = get_last_insn ();
 889
 890   /* Make a copy of the insn having delay slots.  */
 891   rtx delay_insn = copy_rtx (insn);
 892
 893   /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
 894      confuse further processing.  Update LAST in case it was the last insn.
 895      We will put the BARRIER back in later.  */
 896   if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
 897     {
 898       delete_insn (NEXT_INSN (insn));
 899       last = get_last_insn ();
 900       had_barrier = 1;
 901     }
 902
 903   /* Splice our SEQUENCE into the insn stream where INSN used to be.  */
 904   NEXT_INSN (seq_insn) = NEXT_INSN (insn);
 905   PREV_INSN (seq_insn) = PREV_INSN (insn);
 906
 907   if (insn != last)
 908     PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
 909
 910   if (insn != first)
 911     NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
 912
 913   /* Note the calls to set_new_first_and_last_insn must occur after
 914      SEQ_INSN has been completely spliced into the insn stream.
 915
 916      Otherwise CUR_INSN_UID will get set to an incorrect value because
 917      set_new_first_and_last_insn will not find SEQ_INSN in the chain.  */
 918   if (insn == last)
 919     set_new_first_and_last_insn (first, seq_insn);
 920
 921   if (insn == first)
 922     set_new_first_and_last_insn (seq_insn, last);
 923
 924   /* Build our SEQUENCE and rebuild the insn chain.  */
 925   XVECEXP (seq, 0, 0) = delay_insn;
 926   INSN_DELETED_P (delay_insn) = 0;
 927   PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
 928
 929   for (li = list; li; li = XEXP (li, 1), i++)
 930     {
 931       rtx tem = XEXP (li, 0);
 932       rtx note;
 933
 934       /* Show that this copy of the insn isn't deleted.  */
 935       INSN_DELETED_P (tem) = 0;
 936
 937       XVECEXP (seq, 0, i) = tem;
 938       PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
 939       NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
 940
 941       /* Remove any REG_DEAD notes because we can't rely on them now
 942          that the insn has been moved.  */
 943       for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
 944         if (REG_NOTE_KIND (note) == REG_DEAD)
 945           XEXP (note, 0) = const0_rtx;
 946     }
 947
 948   NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
 949
 950   /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
 951      last insn in that SEQUENCE to point to us.  Similarly for the first
 952      insn in the following insn if it is a SEQUENCE.  */
 953
 954   if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
 955       && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
 956     NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
 957                         XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
 958       = seq_insn;
 959
 960   if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
 961       && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
 962     PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
 963
 964   /* If there used to be a BARRIER, put it back.  */
 965   if (had_barrier)
 966     emit_barrier_after (seq_insn);
 967
 968   if (i != length + 1)
 969     abort ();
 970
 971   return seq_insn;
 972 }
 973
 974 /* Add INSN to DELAY_LIST and return the head of the new list.  The list must
 975    be in the order in which the insns are to be executed.  */
 976
 977 static rtx
 978 add_to_delay_list (insn, delay_list)
 979      rtx insn;
 980      rtx delay_list;
 981 {
 982   /* If we have an empty list, just make a new list element.  If
 983      INSN has it's block number recorded, clear it since we may
 984      be moving the insn to a new block.  */
 985
 986   if (delay_list == 0)
 987     {
 988       struct target_info *tinfo;
 989
 990       for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME];
 991            tinfo; tinfo = tinfo->next)
 992         if (tinfo->uid == INSN_UID (insn))
 993           break;
 994
 995       if (tinfo)
 996         tinfo->block = -1;
 997
 998       return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
 999     }
1000
1001   /* Otherwise this must be an INSN_LIST.  Add INSN to the end of the
1002      list.  */
1003   XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
1004
1005   return delay_list;
1006 }
1007 \f
1008 /* Delete INSN from the delay slot of the insn that it is in.  This may
1009    produce an insn without anything in its delay slots.  */
1010
1011 static void
1012 delete_from_delay_slot (insn)
1013      rtx insn;
1014 {
1015   rtx trial, seq_insn, seq, prev;
1016   rtx delay_list = 0;
1017   int i;
1018
1019   /* We first must find the insn containing the SEQUENCE with INSN in its
1020      delay slot.  Do this by finding an insn, TRIAL, where
1021      PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL.  */
1022
1023   for (trial = insn;
1024        PREV_INSN (NEXT_INSN (trial)) == trial;
1025        trial = NEXT_INSN (trial))
1026     ;
1027
1028   seq_insn = PREV_INSN (NEXT_INSN (trial));
1029   seq = PATTERN (seq_insn);
1030
1031   /* Create a delay list consisting of all the insns other than the one
1032      we are deleting (unless we were the only one).  */
1033   if (XVECLEN (seq, 0) > 2)
1034     for (i = 1; i < XVECLEN (seq, 0); i++)
1035       if (XVECEXP (seq, 0, i) != insn)
1036         delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
1037
1038   /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
1039      list, and rebuild the delay list if non-empty.  */
1040   prev = PREV_INSN (seq_insn);
1041   trial = XVECEXP (seq, 0, 0);
1042   delete_insn (seq_insn);
1043   add_insn_after (trial, prev);
1044
1045   if (GET_CODE (trial) == JUMP_INSN
1046       && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
1047     emit_barrier_after (trial);
1048
1049   /* If there are any delay insns, remit them.  Otherwise clear the
1050      annul flag.  */
1051   if (delay_list)
1052     trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2);
1053   else
1054     INSN_ANNULLED_BRANCH_P (trial) = 0;
1055
1056   INSN_FROM_TARGET_P (insn) = 0;
1057
1058   /* Show we need to fill this insn again.  */
1059   obstack_ptr_grow (&unfilled_slots_obstack, trial);
1060 }
1061 \f
1062 /* Delete INSN, a JUMP_INSN.  If it is a conditional jump, we must track down
1063    the insn that sets CC0 for it and delete it too.  */
1064
1065 static void
1066 delete_scheduled_jump (insn)
1067      rtx insn;
1068 {
1069   /* Delete the insn that sets cc0 for us.  On machines without cc0, we could
1070      delete the insn that sets the condition code, but it is hard to find it.
1071      Since this case is rare anyway, don't bother trying; there would likely
1072      be other insns that became dead anyway, which we wouldn't know to
1073      delete.  */
1074
1075 #ifdef HAVE_cc0
1076   if (reg_mentioned_p (cc0_rtx, insn))
1077     {
1078       rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
1079
1080       /* If a reg-note was found, it points to an insn to set CC0.  This
1081          insn is in the delay list of some other insn.  So delete it from
1082          the delay list it was in.  */
1083       if (note)
1084         {
1085           if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
1086               && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
1087             delete_from_delay_slot (XEXP (note, 0));
1088         }
1089       else
1090         {
1091           /* The insn setting CC0 is our previous insn, but it may be in
1092              a delay slot.  It will be the last insn in the delay slot, if
1093              it is.  */
1094           rtx trial = previous_insn (insn);
1095           if (GET_CODE (trial) == NOTE)
1096             trial = prev_nonnote_insn (trial);
1097           if (sets_cc0_p (PATTERN (trial)) != 1
1098               || FIND_REG_INC_NOTE (trial, 0))
1099             return;
1100           if (PREV_INSN (NEXT_INSN (trial)) == trial)
1101             delete_insn (trial);
1102           else
1103             delete_from_delay_slot (trial);
1104         }
1105     }
1106 #endif
1107
1108   delete_insn (insn);
1109 }
1110 \f
1111 /* Counters for delay-slot filling.  */
1112
1113 #define NUM_REORG_FUNCTIONS 2
1114 #define MAX_DELAY_HISTOGRAM 3
1115 #define MAX_REORG_PASSES 2
1116
1117 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
1118
1119 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
1120
1121 static int reorg_pass_number;
1122
1123 static void
1124 note_delay_statistics (slots_filled, index)
1125      int slots_filled, index;
1126 {
1127   num_insns_needing_delays[index][reorg_pass_number]++;
1128   if (slots_filled > MAX_DELAY_HISTOGRAM)
1129     slots_filled = MAX_DELAY_HISTOGRAM;
1130   num_filled_delays[index][slots_filled][reorg_pass_number]++;
1131 }
1132 \f
1133 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
1134
1135 /* Optimize the following cases:
1136
1137    1.  When a conditional branch skips over only one instruction,
1138        use an annulling branch and put that insn in the delay slot.
1139        Use either a branch that annuls when the condition if true or
1140        invert the test with a branch that annuls when the condition is
1141        false.  This saves insns, since otherwise we must copy an insn
1142        from the L1 target.
1143
1144         (orig)           (skip)         (otherwise)
1145         Bcc.n L1        Bcc',a L1       Bcc,a L1'
1146         insn            insn            insn2
1147       L1:             L1:             L1:
1148         insn2           insn2           insn2
1149         insn3           insn3         L1':
1150                                         insn3
1151
1152    2.  When a conditional branch skips over only one instruction,
1153        and after that, it unconditionally branches somewhere else,
1154        perform the similar optimization. This saves executing the
1155        second branch in the case where the inverted condition is true.
1156
1157         Bcc.n L1        Bcc',a L2
1158         insn            insn
1159       L1:             L1:
1160         Bra L2          Bra L2
1161
1162    INSN is a JUMP_INSN.
1163
1164    This should be expanded to skip over N insns, where N is the number
1165    of delay slots required.  */
1166
1167 static rtx
1168 optimize_skip (insn)
1169      register rtx insn;
1170 {
1171   register rtx trial = next_nonnote_insn (insn);
1172   rtx next_trial = next_active_insn (trial);
1173   rtx delay_list = 0;
1174   rtx target_label;
1175   int flags;
1176
1177   flags = get_jump_flags (insn, JUMP_LABEL (insn));
1178
1179   if (trial == 0
1180       || GET_CODE (trial) != INSN
1181       || GET_CODE (PATTERN (trial)) == SEQUENCE
1182       || recog_memoized (trial) < 0
1183       || (! eligible_for_annul_false (insn, 0, trial, flags)
1184           && ! eligible_for_annul_true (insn, 0, trial, flags)))
1185     return 0;
1186
1187   /* There are two cases where we are just executing one insn (we assume
1188      here that a branch requires only one insn; this should be generalized
1189      at some point):  Where the branch goes around a single insn or where
1190      we have one insn followed by a branch to the same label we branch to.
1191      In both of these cases, inverting the jump and annulling the delay
1192      slot give the same effect in fewer insns.  */
1193   if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
1194       || (next_trial != 0
1195           && GET_CODE (next_trial) == JUMP_INSN
1196           && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
1197           && (simplejump_p (next_trial)
1198               || GET_CODE (PATTERN (next_trial)) == RETURN)))
1199     {
1200       if (eligible_for_annul_false (insn, 0, trial, flags))
1201         {
1202           if (invert_jump (insn, JUMP_LABEL (insn)))
1203             INSN_FROM_TARGET_P (trial) = 1;
1204           else if (! eligible_for_annul_true (insn, 0, trial, flags))
1205             return 0;
1206         }
1207
1208       delay_list = add_to_delay_list (trial, NULL_RTX);
1209       next_trial = next_active_insn (trial);
1210       update_block (trial, trial);
1211       delete_insn (trial);
1212
1213       /* Also, if we are targeting an unconditional
1214          branch, thread our jump to the target of that branch.  Don't
1215          change this into a RETURN here, because it may not accept what
1216          we have in the delay slot.  We'll fix this up later.  */
1217       if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1218           && (simplejump_p (next_trial)
1219               || GET_CODE (PATTERN (next_trial)) == RETURN))
1220         {
1221           target_label = JUMP_LABEL (next_trial);
1222           if (target_label == 0)
1223             target_label = find_end_label ();
1224
1225           /* Recompute the flags based on TARGET_LABEL since threading
1226              the jump to TARGET_LABEL may change the direction of the
1227              jump (which may change the circumstances in which the
1228              delay slot is nullified).  */
1229           flags = get_jump_flags (insn, target_label);
1230           if (eligible_for_annul_true (insn, 0, trial, flags))
1231             reorg_redirect_jump (insn, target_label);
1232         }
1233
1234       INSN_ANNULLED_BRANCH_P (insn) = 1;
1235     }
1236
1237   return delay_list;
1238 }
1239 #endif
1240 \f
1241
1242 /*  Encode and return branch direction and prediction information for
1243     INSN assuming it will jump to LABEL.
1244
1245     Non conditional branches return no direction information and
1246     are predicted as very likely taken.  */
1247
1248 static int
1249 get_jump_flags (insn, label)
1250      rtx insn, label;
1251 {
1252   int flags;
1253
1254   /* get_jump_flags can be passed any insn with delay slots, these may
1255      be INSNs, CALL_INSNs, or JUMP_INSNs.  Only JUMP_INSNs have branch
1256      direction information, and only if they are conditional jumps.
1257
1258      If LABEL is zero, then there is no way to determine the branch
1259      direction.  */
1260   if (GET_CODE (insn) == JUMP_INSN
1261       && (condjump_p (insn) || condjump_in_parallel_p (insn))
1262       && INSN_UID (insn) <= max_uid
1263       && label != 0
1264       && INSN_UID (label) <= max_uid)
1265     flags
1266       = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
1267          ? ATTR_FLAG_forward : ATTR_FLAG_backward;
1268   /* No valid direction information.  */
1269   else
1270     flags = 0;
1271
1272   /* If insn is a conditional branch call mostly_true_jump to get
1273      determine the branch prediction.
1274
1275      Non conditional branches are predicted as very likely taken.  */
1276   if (GET_CODE (insn) == JUMP_INSN
1277       && (condjump_p (insn) || condjump_in_parallel_p (insn)))
1278     {
1279       int prediction;
1280
1281       prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
1282       switch (prediction)
1283         {
1284           case 2:
1285             flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
1286             break;
1287           case 1:
1288             flags |= ATTR_FLAG_likely;
1289             break;
1290           case 0:
1291             flags |= ATTR_FLAG_unlikely;
1292             break;
1293           case -1:
1294             flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
1295             break;
1296
1297           default:
1298             abort();
1299         }
1300     }
1301   else
1302     flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
1303
1304   return flags;
1305 }
1306
1307 /* Return 1 if INSN is a destination that will be branched to rarely (the
1308    return point of a function); return 2 if DEST will be branched to very
1309    rarely (a call to a function that doesn't return).  Otherwise,
1310    return 0.  */
1311
1312 static int
1313 rare_destination (insn)
1314      rtx insn;
1315 {
1316   int jump_count = 0;
1317   rtx next;
1318
1319   for (; insn; insn = next)
1320     {
1321       if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE)
1322         insn = XVECEXP (PATTERN (insn), 0, 0);
1323
1324       next = NEXT_INSN (insn);
1325
1326       switch (GET_CODE (insn))
1327         {
1328         case CODE_LABEL:
1329           return 0;
1330         case BARRIER:
1331           /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN.  We
1332              don't scan past JUMP_INSNs, so any barrier we find here must
1333              have been after a CALL_INSN and hence mean the call doesn't
1334              return.  */
1335           return 2;
1336         case JUMP_INSN:
1337           if (GET_CODE (PATTERN (insn)) == RETURN)
1338             return 1;
1339           else if (simplejump_p (insn)
1340                    && jump_count++ < 10)
1341             next = JUMP_LABEL (insn);
1342           else
1343             return 0;
1344
1345         default:
1346           break;
1347         }
1348     }
1349
1350   /* If we got here it means we hit the end of the function.  So this
1351      is an unlikely destination.  */
1352
1353   return 1;
1354 }
1355
1356 /* Return truth value of the statement that this branch
1357    is mostly taken.  If we think that the branch is extremely likely
1358    to be taken, we return 2.  If the branch is slightly more likely to be
1359    taken, return 1.  If the branch is slightly less likely to be taken,
1360    return 0 and if the branch is highly unlikely to be taken, return -1.
1361
1362    CONDITION, if non-zero, is the condition that JUMP_INSN is testing.  */
1363
1364 static int
1365 mostly_true_jump (jump_insn, condition)
1366      rtx jump_insn, condition;
1367 {
1368   rtx target_label = JUMP_LABEL (jump_insn);
1369   rtx insn;
1370   int rare_dest = rare_destination (target_label);
1371   int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
1372
1373   /* If branch probabilities are available, then use that number since it
1374      always gives a correct answer.  */
1375   if (flag_branch_probabilities)
1376     {
1377       rtx note = find_reg_note (jump_insn, REG_BR_PROB, 0);;
1378       if (note)
1379         {
1380           int prob = XINT (note, 0);
1381
1382           if (prob >= REG_BR_PROB_BASE * 9 / 10)
1383             return 2;
1384           else if (prob >= REG_BR_PROB_BASE / 2)
1385             return 1;
1386           else if (prob >= REG_BR_PROB_BASE / 10)
1387             return 0;
1388           else
1389             return -1;
1390         }
1391     }
1392
1393   /* If this is a branch outside a loop, it is highly unlikely.  */
1394   if (GET_CODE (PATTERN (jump_insn)) == SET
1395       && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
1396       && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
1397            && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
1398           || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
1399               && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
1400     return -1;
1401
1402   if (target_label)
1403     {
1404       /* If this is the test of a loop, it is very likely true.  We scan
1405          backwards from the target label.  If we find a NOTE_INSN_LOOP_BEG
1406          before the next real insn, we assume the branch is to the top of
1407          the loop.  */
1408       for (insn = PREV_INSN (target_label);
1409            insn && GET_CODE (insn) == NOTE;
1410            insn = PREV_INSN (insn))
1411         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1412           return 2;
1413
1414       /* If this is a jump to the test of a loop, it is likely true.  We scan
1415          forwards from the target label.  If we find a NOTE_INSN_LOOP_VTOP
1416          before the next real insn, we assume the branch is to the loop branch
1417          test.  */
1418       for (insn = NEXT_INSN (target_label);
1419            insn && GET_CODE (insn) == NOTE;
1420            insn = PREV_INSN (insn))
1421         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
1422           return 1;
1423     }
1424
1425   /* Look at the relative rarities of the fallthrough and destination.  If
1426      they differ, we can predict the branch that way.  */
1427
1428   switch (rare_fallthrough - rare_dest)
1429     {
1430     case -2:
1431       return -1;
1432     case -1:
1433       return 0;
1434     case 0:
1435       break;
1436     case 1:
1437       return 1;
1438     case 2:
1439       return 2;
1440     }
1441
1442   /* If we couldn't figure out what this jump was, assume it won't be
1443      taken.  This should be rare.  */
1444   if (condition == 0)
1445     return 0;
1446
1447   /* EQ tests are usually false and NE tests are usually true.  Also,
1448      most quantities are positive, so we can make the appropriate guesses
1449      about signed comparisons against zero.  */
1450   switch (GET_CODE (condition))
1451     {
1452     case CONST_INT:
1453       /* Unconditional branch.  */
1454       return 1;
1455     case EQ:
1456       return 0;
1457     case NE:
1458       return 1;
1459     case LE:
1460     case LT:
1461       if (XEXP (condition, 1) == const0_rtx)
1462         return 0;
1463       break;
1464     case GE:
1465     case GT:
1466       if (XEXP (condition, 1) == const0_rtx)
1467         return 1;
1468       break;
1469
1470     default:
1471       break;
1472     }
1473
1474   /* Predict backward branches usually take, forward branches usually not.  If
1475      we don't know whether this is forward or backward, assume the branch
1476      will be taken, since most are.  */
1477   return (target_label == 0 || INSN_UID (jump_insn) > max_uid
1478           || INSN_UID (target_label) > max_uid
1479           || (uid_to_ruid[INSN_UID (jump_insn)]
1480               > uid_to_ruid[INSN_UID (target_label)]));;
1481 }
1482
1483 /* Return the condition under which INSN will branch to TARGET.  If TARGET
1484    is zero, return the condition under which INSN will return.  If INSN is
1485    an unconditional branch, return const_true_rtx.  If INSN isn't a simple
1486    type of jump, or it doesn't go to TARGET, return 0.  */
1487
1488 static rtx
1489 get_branch_condition (insn, target)
1490      rtx insn;
1491      rtx target;
1492 {
1493   rtx pat = PATTERN (insn);
1494   rtx src;
1495
1496   if (condjump_in_parallel_p (insn))
1497     pat = XVECEXP (pat, 0, 0);
1498
1499   if (GET_CODE (pat) == RETURN)
1500     return target == 0 ? const_true_rtx : 0;
1501
1502   else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1503     return 0;
1504
1505   src = SET_SRC (pat);
1506   if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1507     return const_true_rtx;
1508
1509   else if (GET_CODE (src) == IF_THEN_ELSE
1510            && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1511                || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1512                    && XEXP (XEXP (src, 1), 0) == target))
1513            && XEXP (src, 2) == pc_rtx)
1514     return XEXP (src, 0);
1515
1516   else if (GET_CODE (src) == IF_THEN_ELSE
1517            && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1518                || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1519                    && XEXP (XEXP (src, 2), 0) == target))
1520            && XEXP (src, 1) == pc_rtx)
1521     return gen_rtx_fmt_ee (reverse_condition (GET_CODE (XEXP (src, 0))),
1522                            GET_MODE (XEXP (src, 0)),
1523                            XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1524
1525   return 0;
1526 }
1527
1528 /* Return non-zero if CONDITION is more strict than the condition of
1529    INSN, i.e., if INSN will always branch if CONDITION is true.  */
1530
1531 static int
1532 condition_dominates_p (condition, insn)
1533      rtx condition;
1534      rtx insn;
1535 {
1536   rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1537   enum rtx_code code = GET_CODE (condition);
1538   enum rtx_code other_code;
1539
1540   if (rtx_equal_p (condition, other_condition)
1541       || other_condition == const_true_rtx)
1542     return 1;
1543
1544   else if (condition == const_true_rtx || other_condition == 0)
1545     return 0;
1546
1547   other_code = GET_CODE (other_condition);
1548   if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1549       || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1550       || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1551     return 0;
1552
1553   return comparison_dominates_p (code, other_code);
1554 }
1555
1556 /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
1557    any insns already in the delay slot of JUMP.  */
1558
1559 static int
1560 redirect_with_delay_slots_safe_p (jump, newlabel, seq)
1561      rtx jump, newlabel, seq;
1562 {
1563   int flags, i;
1564   rtx pat = PATTERN (seq);
1565
1566   /* Make sure all the delay slots of this jump would still
1567      be valid after threading the jump.  If they are still
1568      valid, then return non-zero.  */
1569
1570   flags = get_jump_flags (jump, newlabel);
1571   for (i = 1; i < XVECLEN (pat, 0); i++)
1572     if (! (
1573 #ifdef ANNUL_IFFALSE_SLOTS
1574            (INSN_ANNULLED_BRANCH_P (jump)
1575             && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1576            ? eligible_for_annul_false (jump, i - 1,
1577                                        XVECEXP (pat, 0, i), flags) :
1578 #endif
1579 #ifdef ANNUL_IFTRUE_SLOTS
1580            (INSN_ANNULLED_BRANCH_P (jump)
1581             && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1582            ? eligible_for_annul_true (jump, i - 1,
1583                                       XVECEXP (pat, 0, i), flags) :
1584 #endif
1585            eligible_for_delay (jump, i -1, XVECEXP (pat, 0, i), flags)))
1586       break;
1587
1588   return (i == XVECLEN (pat, 0));
1589 }
1590
1591 /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
1592    any insns we wish to place in the delay slot of JUMP.  */
1593
1594 static int
1595 redirect_with_delay_list_safe_p (jump, newlabel, delay_list)
1596      rtx jump, newlabel, delay_list;
1597 {
1598   int flags, i;
1599   rtx li;
1600
1601   /* Make sure all the insns in DELAY_LIST would still be
1602      valid after threading the jump.  If they are still
1603      valid, then return non-zero.  */
1604
1605   flags = get_jump_flags (jump, newlabel);
1606   for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++)
1607     if (! (
1608 #ifdef ANNUL_IFFALSE_SLOTS
1609            (INSN_ANNULLED_BRANCH_P (jump)
1610             && INSN_FROM_TARGET_P (XEXP (li, 0)))
1611            ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) :
1612 #endif
1613 #ifdef ANNUL_IFTRUE_SLOTS
1614            (INSN_ANNULLED_BRANCH_P (jump)
1615             && ! INSN_FROM_TARGET_P (XEXP (li, 0)))
1616            ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) :
1617 #endif
1618            eligible_for_delay (jump, i, XEXP (li, 0), flags)))
1619       break;
1620
1621   return (li == NULL);
1622 }
1623
1624 \f
1625 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE.  Given that
1626    the condition tested by INSN is CONDITION and the resources shown in
1627    OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1628    from SEQ's delay list, in addition to whatever insns it may execute
1629    (in DELAY_LIST).   SETS and NEEDED are denote resources already set and
1630    needed while searching for delay slot insns.  Return the concatenated
1631    delay list if possible, otherwise, return 0.
1632
1633    SLOTS_TO_FILL is the total number of slots required by INSN, and
1634    PSLOTS_FILLED points to the number filled so far (also the number of
1635    insns in DELAY_LIST).  It is updated with the number that have been
1636    filled from the SEQUENCE, if any.
1637
1638    PANNUL_P points to a non-zero value if we already know that we need
1639    to annul INSN.  If this routine determines that annulling is needed,
1640    it may set that value non-zero.
1641
1642    PNEW_THREAD points to a location that is to receive the place at which
1643    execution should continue.  */
1644
1645 static rtx
1646 steal_delay_list_from_target (insn, condition, seq, delay_list,
1647                               sets, needed, other_needed,
1648                               slots_to_fill, pslots_filled, pannul_p,
1649                               pnew_thread)
1650      rtx insn, condition;
1651      rtx seq;
1652      rtx delay_list;
1653      struct resources *sets, *needed, *other_needed;
1654      int slots_to_fill;
1655      int *pslots_filled;
1656      int *pannul_p;
1657      rtx *pnew_thread;
1658 {
1659   rtx temp;
1660   int slots_remaining = slots_to_fill - *pslots_filled;
1661   int total_slots_filled = *pslots_filled;
1662   rtx new_delay_list = 0;
1663   int must_annul = *pannul_p;
1664   int i;
1665
1666   /* We can't do anything if there are more delay slots in SEQ than we
1667      can handle, or if we don't know that it will be a taken branch.
1668      We know that it will be a taken branch if it is either an unconditional
1669      branch or a conditional branch with a stricter branch condition.
1670
1671      Also, exit if the branch has more than one set, since then it is computing
1672      other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1673      ??? It may be possible to move other sets into INSN in addition to
1674      moving the instructions in the delay slots.  */
1675
1676   if (XVECLEN (seq, 0) - 1 > slots_remaining
1677       || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))
1678       || ! single_set (XVECEXP (seq, 0, 0)))
1679     return delay_list;
1680
1681   for (i = 1; i < XVECLEN (seq, 0); i++)
1682     {
1683       rtx trial = XVECEXP (seq, 0, i);
1684       int flags;
1685
1686       if (insn_references_resource_p (trial, sets, 0)
1687           || insn_sets_resource_p (trial, needed, 0)
1688           || insn_sets_resource_p (trial, sets, 0)
1689 #ifdef HAVE_cc0
1690           /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1691              delay list.  */
1692           || find_reg_note (trial, REG_CC_USER, NULL_RTX)
1693 #endif
1694           /* If TRIAL is from the fallthrough code of an annulled branch insn
1695              in SEQ, we cannot use it.  */
1696           || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1697               && ! INSN_FROM_TARGET_P (trial)))
1698         return delay_list;
1699
1700       /* If this insn was already done (usually in a previous delay slot),
1701          pretend we put it in our delay slot.  */
1702       if (redundant_insn (trial, insn, new_delay_list))
1703         continue;
1704
1705       /* We will end up re-vectoring this branch, so compute flags
1706          based on jumping to the new label.  */
1707       flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
1708
1709       if (! must_annul
1710           && ((condition == const_true_rtx
1711                || (! insn_sets_resource_p (trial, other_needed, 0)
1712                    && ! may_trap_p (PATTERN (trial)))))
1713           ? eligible_for_delay (insn, total_slots_filled, trial, flags)
1714           : (must_annul = 1,
1715              eligible_for_annul_false (insn, total_slots_filled, trial, flags)))
1716         {
1717           temp = copy_rtx (trial);
1718           INSN_FROM_TARGET_P (temp) = 1;
1719           new_delay_list = add_to_delay_list (temp, new_delay_list);
1720           total_slots_filled++;
1721
1722           if (--slots_remaining == 0)
1723             break;
1724         }
1725       else
1726         return delay_list;
1727     }
1728
1729   /* Show the place to which we will be branching.  */
1730   *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1731
1732   /* Add any new insns to the delay list and update the count of the
1733      number of slots filled.  */
1734   *pslots_filled = total_slots_filled;
1735   *pannul_p = must_annul;
1736
1737   if (delay_list == 0)
1738     return new_delay_list;
1739
1740   for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1741     delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1742
1743   return delay_list;
1744 }
1745 \f
1746 /* Similar to steal_delay_list_from_target except that SEQ is on the
1747    fallthrough path of INSN.  Here we only do something if the delay insn
1748    of SEQ is an unconditional branch.  In that case we steal its delay slot
1749    for INSN since unconditional branches are much easier to fill.  */
1750
1751 static rtx
1752 steal_delay_list_from_fallthrough (insn, condition, seq,
1753                                    delay_list, sets, needed, other_needed,
1754                                    slots_to_fill, pslots_filled, pannul_p)
1755      rtx insn, condition;
1756      rtx seq;
1757      rtx delay_list;
1758      struct resources *sets, *needed, *other_needed;
1759      int slots_to_fill;
1760      int *pslots_filled;
1761      int *pannul_p;
1762 {
1763   int i;
1764   int flags;
1765
1766   flags = get_jump_flags (insn, JUMP_LABEL (insn));
1767
1768   /* We can't do anything if SEQ's delay insn isn't an
1769      unconditional branch.  */
1770
1771   if (! simplejump_p (XVECEXP (seq, 0, 0))
1772       && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1773     return delay_list;
1774
1775   for (i = 1; i < XVECLEN (seq, 0); i++)
1776     {
1777       rtx trial = XVECEXP (seq, 0, i);
1778
1779       /* If TRIAL sets CC0, stealing it will move it too far from the use
1780          of CC0.  */
1781       if (insn_references_resource_p (trial, sets, 0)
1782           || insn_sets_resource_p (trial, needed, 0)
1783           || insn_sets_resource_p (trial, sets, 0)
1784 #ifdef HAVE_cc0
1785           || sets_cc0_p (PATTERN (trial))
1786 #endif
1787           )
1788
1789         break;
1790
1791       /* If this insn was already done, we don't need it.  */
1792       if (redundant_insn (trial, insn, delay_list))
1793         {
1794           delete_from_delay_slot (trial);
1795           continue;
1796         }
1797
1798       if (! *pannul_p
1799           && ((condition == const_true_rtx
1800                || (! insn_sets_resource_p (trial, other_needed, 0)
1801                    && ! may_trap_p (PATTERN (trial)))))
1802           ? eligible_for_delay (insn, *pslots_filled, trial, flags)
1803           : (*pannul_p = 1,
1804              eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
1805         {
1806           delete_from_delay_slot (trial);
1807           delay_list = add_to_delay_list (trial, delay_list);
1808
1809           if (++(*pslots_filled) == slots_to_fill)
1810             break;
1811         }
1812       else
1813         break;
1814     }
1815
1816   return delay_list;
1817 }
1818 \f
1819 /* Try merging insns starting at THREAD which match exactly the insns in
1820    INSN's delay list.
1821
1822    If all insns were matched and the insn was previously annulling, the
1823    annul bit will be cleared.
1824
1825    For each insn that is merged, if the branch is or will be non-annulling,
1826    we delete the merged insn.  */
1827
1828 static void
1829 try_merge_delay_insns (insn, thread)
1830      rtx insn, thread;
1831 {
1832   rtx trial, next_trial;
1833   rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1834   int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1835   int slot_number = 1;
1836   int num_slots = XVECLEN (PATTERN (insn), 0);
1837   rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1838   struct resources set, needed;
1839   rtx merged_insns = 0;
1840   int i;
1841   int flags;
1842
1843   flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
1844
1845   CLEAR_RESOURCE (&needed);
1846   CLEAR_RESOURCE (&set);
1847
1848   /* If this is not an annulling branch, take into account anything needed in
1849      NEXT_TO_MATCH.  This prevents two increments from being incorrectly
1850      folded into one.  If we are annulling, this would be the correct
1851      thing to do.  (The alternative, looking at things set in NEXT_TO_MATCH
1852      will essentially disable this optimization.  This method is somewhat of
1853      a kludge, but I don't see a better way.)  */
1854   if (! annul_p)
1855     mark_referenced_resources (next_to_match, &needed, 1);
1856
1857   for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1858     {
1859       rtx pat = PATTERN (trial);
1860       rtx oldtrial = trial;
1861
1862       next_trial = next_nonnote_insn (trial);
1863
1864       /* TRIAL must be a CALL_INSN or INSN.  Skip USE and CLOBBER.  */
1865       if (GET_CODE (trial) == INSN
1866           && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1867         continue;
1868
1869       if (GET_CODE (next_to_match) == GET_CODE (trial)
1870 #ifdef HAVE_cc0
1871           /* We can't share an insn that sets cc0.  */
1872           && ! sets_cc0_p (pat)
1873 #endif
1874           && ! insn_references_resource_p (trial, &set, 1)
1875           && ! insn_sets_resource_p (trial, &set, 1)
1876           && ! insn_sets_resource_p (trial, &needed, 1)
1877           && (trial = try_split (pat, trial, 0)) != 0
1878           /* Update next_trial, in case try_split succeeded.  */
1879           && (next_trial = next_nonnote_insn (trial))
1880           /* Likewise THREAD.  */
1881           && (thread = oldtrial == thread ? trial : thread)
1882           && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1883           /* Have to test this condition if annul condition is different
1884              from (and less restrictive than) non-annulling one.  */
1885           && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
1886         {
1887
1888           if (! annul_p)
1889             {
1890               update_block (trial, thread);
1891               if (trial == thread)
1892                 thread = next_active_insn (thread);
1893
1894               delete_insn (trial);
1895               INSN_FROM_TARGET_P (next_to_match) = 0;
1896             }
1897           else
1898             merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns);
1899
1900           if (++slot_number == num_slots)
1901             break;
1902
1903           next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1904           if (! annul_p)
1905             mark_referenced_resources (next_to_match, &needed, 1);
1906         }
1907
1908       mark_set_resources (trial, &set, 0, 1);
1909       mark_referenced_resources (trial, &needed, 1);
1910     }
1911
1912   /* See if we stopped on a filled insn.  If we did, try to see if its
1913      delay slots match.  */
1914   if (slot_number != num_slots
1915       && trial && GET_CODE (trial) == INSN
1916       && GET_CODE (PATTERN (trial)) == SEQUENCE
1917       && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1918     {
1919       rtx pat = PATTERN (trial);
1920       rtx filled_insn = XVECEXP (pat, 0, 0);
1921
1922       /* Account for resources set/needed by the filled insn.  */
1923       mark_set_resources (filled_insn, &set, 0, 1);
1924       mark_referenced_resources (filled_insn, &needed, 1);
1925
1926       for (i = 1; i < XVECLEN (pat, 0); i++)
1927         {
1928           rtx dtrial = XVECEXP (pat, 0, i);
1929
1930           if (! insn_references_resource_p (dtrial, &set, 1)
1931               && ! insn_sets_resource_p (dtrial, &set, 1)
1932               && ! insn_sets_resource_p (dtrial, &needed, 1)
1933 #ifdef HAVE_cc0
1934               && ! sets_cc0_p (PATTERN (dtrial))
1935 #endif
1936               && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1937               && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
1938             {
1939               if (! annul_p)
1940                 {
1941                   update_block (dtrial, thread);
1942                   delete_from_delay_slot (dtrial);
1943                   INSN_FROM_TARGET_P (next_to_match) = 0;
1944                 }
1945               else
1946                 merged_insns = gen_rtx_INSN_LIST (SImode, dtrial,
1947                                                   merged_insns);
1948
1949               if (++slot_number == num_slots)
1950                 break;
1951
1952               next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1953             }
1954         }
1955     }
1956
1957   /* If all insns in the delay slot have been matched and we were previously
1958      annulling the branch, we need not any more.  In that case delete all the
1959      merged insns.  Also clear the INSN_FROM_TARGET_P bit of each insn in
1960      the delay list so that we know that it isn't only being used at the
1961      target.  */
1962   if (slot_number == num_slots && annul_p)
1963     {
1964       for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1965         {
1966           if (GET_MODE (merged_insns) == SImode)
1967             {
1968               update_block (XEXP (merged_insns, 0), thread);
1969               delete_from_delay_slot (XEXP (merged_insns, 0));
1970             }
1971           else
1972             {
1973               update_block (XEXP (merged_insns, 0), thread);
1974               delete_insn (XEXP (merged_insns, 0));
1975             }
1976         }
1977
1978       INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1979
1980       for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1981         INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1982     }
1983 }
1984 \f
1985 /* See if INSN is redundant with an insn in front of TARGET.  Often this
1986    is called when INSN is a candidate for a delay slot of TARGET.
1987    DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1988    of INSN.  Often INSN will be redundant with an insn in a delay slot of
1989    some previous insn.  This happens when we have a series of branches to the
1990    same label; in that case the first insn at the target might want to go
1991    into each of the delay slots.
1992
1993    If we are not careful, this routine can take up a significant fraction
1994    of the total compilation time (4%), but only wins rarely.  Hence we
1995    speed this routine up by making two passes.  The first pass goes back
1996    until it hits a label and sees if it find an insn with an identical
1997    pattern.  Only in this (relatively rare) event does it check for
1998    data conflicts.
1999
2000    We do not split insns we encounter.  This could cause us not to find a
2001    redundant insn, but the cost of splitting seems greater than the possible
2002    gain in rare cases.  */
2003
2004 static rtx
2005 redundant_insn (insn, target, delay_list)
2006      rtx insn;
2007      rtx target;
2008      rtx delay_list;
2009 {
2010   rtx target_main = target;
2011   rtx ipat = PATTERN (insn);
2012   rtx trial, pat;
2013   struct resources needed, set;
2014   int i;
2015
2016   /* If INSN has any REG_UNUSED notes, it can't match anything since we
2017      are allowed to not actually assign to such a register.  */
2018   if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0)
2019     return 0;
2020
2021   /* Scan backwards looking for a match.  */
2022   for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
2023     {
2024       if (GET_CODE (trial) == CODE_LABEL)
2025         return 0;
2026
2027       if (GET_RTX_CLASS (GET_CODE (trial)) != 'i')
2028         continue;
2029
2030       pat = PATTERN (trial);
2031       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2032         continue;
2033
2034       if (GET_CODE (pat) == SEQUENCE)
2035         {
2036           /* Stop for a CALL and its delay slots because it is difficult to
2037              track its resource needs correctly.  */
2038           if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2039             return 0;
2040
2041           /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
2042              slots because it is difficult to track its resource needs
2043              correctly.  */
2044
2045 #ifdef INSN_SETS_ARE_DELAYED
2046           if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2047             return 0;
2048 #endif
2049
2050 #ifdef INSN_REFERENCES_ARE_DELAYED
2051           if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2052             return 0;
2053 #endif
2054
2055           /* See if any of the insns in the delay slot match, updating
2056              resource requirements as we go.  */
2057           for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2058             if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
2059                 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat)
2060                 && ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX))
2061               break;
2062
2063           /* If found a match, exit this loop early.  */
2064           if (i > 0)
2065             break;
2066         }
2067
2068       else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)
2069                && ! find_reg_note (trial, REG_UNUSED, NULL_RTX))
2070         break;
2071     }
2072
2073   /* If we didn't find an insn that matches, return 0.  */
2074   if (trial == 0)
2075     return 0;
2076
2077   /* See what resources this insn sets and needs.  If they overlap, or
2078      if this insn references CC0, it can't be redundant.  */
2079
2080   CLEAR_RESOURCE (&needed);
2081   CLEAR_RESOURCE (&set);
2082   mark_set_resources (insn, &set, 0, 1);
2083   mark_referenced_resources (insn, &needed, 1);
2084
2085   /* If TARGET is a SEQUENCE, get the main insn.  */
2086   if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2087     target_main = XVECEXP (PATTERN (target), 0, 0);
2088
2089   if (resource_conflicts_p (&needed, &set)
2090 #ifdef HAVE_cc0
2091       || reg_mentioned_p (cc0_rtx, ipat)
2092 #endif
2093       /* The insn requiring the delay may not set anything needed or set by
2094          INSN.  */
2095       || insn_sets_resource_p (target_main, &needed, 1)
2096       || insn_sets_resource_p (target_main, &set, 1))
2097     return 0;
2098
2099   /* Insns we pass may not set either NEEDED or SET, so merge them for
2100      simpler tests.  */
2101   needed.memory |= set.memory;
2102   needed.unch_memory |= set.unch_memory;
2103   IOR_HARD_REG_SET (needed.regs, set.regs);
2104
2105   /* This insn isn't redundant if it conflicts with an insn that either is
2106      or will be in a delay slot of TARGET.  */
2107
2108   while (delay_list)
2109     {
2110       if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
2111         return 0;
2112       delay_list = XEXP (delay_list, 1);
2113     }
2114
2115   if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2116     for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
2117       if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
2118         return 0;
2119
2120   /* Scan backwards until we reach a label or an insn that uses something
2121      INSN sets or sets something insn uses or sets.  */
2122
2123   for (trial = PREV_INSN (target);
2124        trial && GET_CODE (trial) != CODE_LABEL;
2125        trial = PREV_INSN (trial))
2126     {
2127       if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
2128           && GET_CODE (trial) != JUMP_INSN)
2129         continue;
2130
2131       pat = PATTERN (trial);
2132       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2133         continue;
2134
2135       if (GET_CODE (pat) == SEQUENCE)
2136         {
2137           /* If this is a CALL_INSN and its delay slots, it is hard to track
2138              the resource needs properly, so give up.  */
2139           if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2140             return 0;
2141
2142           /* If this is an INSN or JUMP_INSN with delayed effects, it
2143              is hard to track the resource needs properly, so give up.  */
2144
2145 #ifdef INSN_SETS_ARE_DELAYED
2146           if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2147             return 0;
2148 #endif
2149
2150 #ifdef INSN_REFERENCES_ARE_DELAYED
2151           if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2152             return 0;
2153 #endif
2154
2155           /* See if any of the insns in the delay slot match, updating
2156              resource requirements as we go.  */
2157           for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2158             {
2159               rtx candidate = XVECEXP (pat, 0, i);
2160
2161               /* If an insn will be annulled if the branch is false, it isn't
2162                  considered as a possible duplicate insn.  */
2163               if (rtx_equal_p (PATTERN (candidate), ipat)
2164                   && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2165                         && INSN_FROM_TARGET_P (candidate)))
2166                 {
2167                   /* Show that this insn will be used in the sequel.  */
2168                   INSN_FROM_TARGET_P (candidate) = 0;
2169                   return candidate;
2170                 }
2171
2172               /* Unless this is an annulled insn from the target of a branch,
2173                  we must stop if it sets anything needed or set by INSN.  */
2174               if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2175                    || ! INSN_FROM_TARGET_P (candidate))
2176                   && insn_sets_resource_p (candidate, &needed, 1))
2177                 return 0;
2178             }
2179
2180
2181           /* If the insn requiring the delay slot conflicts with INSN, we
2182              must stop.  */
2183           if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
2184             return 0;
2185         }
2186       else
2187         {
2188           /* See if TRIAL is the same as INSN.  */
2189           pat = PATTERN (trial);
2190           if (rtx_equal_p (pat, ipat))
2191             return trial;
2192
2193           /* Can't go any further if TRIAL conflicts with INSN.  */
2194           if (insn_sets_resource_p (trial, &needed, 1))
2195             return 0;
2196         }
2197     }
2198
2199   return 0;
2200 }
2201 \f
2202 /* Return 1 if THREAD can only be executed in one way.  If LABEL is non-zero,
2203    it is the target of the branch insn being scanned.  If ALLOW_FALLTHROUGH
2204    is non-zero, we are allowed to fall into this thread; otherwise, we are
2205    not.
2206
2207    If LABEL is used more than one or we pass a label other than LABEL before
2208    finding an active insn, we do not own this thread.  */
2209
2210 static int
2211 own_thread_p (thread, label, allow_fallthrough)
2212      rtx thread;
2213      rtx label;
2214      int allow_fallthrough;
2215 {
2216   rtx active_insn;
2217   rtx insn;
2218
2219   /* We don't own the function end.  */
2220   if (thread == 0)
2221     return 0;
2222
2223   /* Get the first active insn, or THREAD, if it is an active insn.  */
2224   active_insn = next_active_insn (PREV_INSN (thread));
2225
2226   for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
2227     if (GET_CODE (insn) == CODE_LABEL
2228         && (insn != label || LABEL_NUSES (insn) != 1))
2229       return 0;
2230
2231   if (allow_fallthrough)
2232     return 1;
2233
2234   /* Ensure that we reach a BARRIER before any insn or label.  */
2235   for (insn = prev_nonnote_insn (thread);
2236        insn == 0 || GET_CODE (insn) != BARRIER;
2237        insn = prev_nonnote_insn (insn))
2238     if (insn == 0
2239         || GET_CODE (insn) == CODE_LABEL
2240         || (GET_CODE (insn) == INSN
2241             && GET_CODE (PATTERN (insn)) != USE
2242             && GET_CODE (PATTERN (insn)) != CLOBBER))
2243       return 0;
2244
2245   return 1;
2246 }
2247 \f
2248 /* Find the number of the basic block that starts closest to INSN.  Return -1
2249    if we couldn't find such a basic block.  */
2250
2251 static int
2252 find_basic_block (insn)
2253      rtx insn;
2254 {
2255   int i;
2256
2257   /* Scan backwards to the previous BARRIER.  Then see if we can find a
2258      label that starts a basic block.  Return the basic block number.  */
2259
2260   for (insn = prev_nonnote_insn (insn);
2261        insn && GET_CODE (insn) != BARRIER;
2262        insn = prev_nonnote_insn (insn))
2263     ;
2264
2265   /* The start of the function is basic block zero.  */
2266   if (insn == 0)
2267     return 0;
2268
2269   /* See if any of the upcoming CODE_LABELs start a basic block.  If we reach
2270      anything other than a CODE_LABEL or note, we can't find this code.  */
2271   for (insn = next_nonnote_insn (insn);
2272        insn && GET_CODE (insn) == CODE_LABEL;
2273        insn = next_nonnote_insn (insn))
2274     {
2275       for (i = 0; i < n_basic_blocks; i++)
2276         if (insn == basic_block_head[i])
2277           return i;
2278     }
2279
2280   return -1;
2281 }
2282 \f
2283 /* Called when INSN is being moved from a location near the target of a jump.
2284    We leave a marker of the form (use (INSN)) immediately in front
2285    of WHERE for mark_target_live_regs.  These markers will be deleted when
2286    reorg finishes.
2287
2288    We used to try to update the live status of registers if WHERE is at
2289    the start of a basic block, but that can't work since we may remove a
2290    BARRIER in relax_delay_slots.  */
2291
2292 static void
2293 update_block (insn, where)
2294      rtx insn;
2295      rtx where;
2296 {
2297   int b;
2298
2299   /* Ignore if this was in a delay slot and it came from the target of
2300      a branch.  */
2301   if (INSN_FROM_TARGET_P (insn))
2302     return;
2303
2304   emit_insn_before (gen_rtx_USE (VOIDmode, insn), where);
2305
2306   /* INSN might be making a value live in a block where it didn't use to
2307      be.  So recompute liveness information for this block.  */
2308
2309   b = find_basic_block (insn);
2310   if (b != -1)
2311     bb_ticks[b]++;
2312 }
2313
2314 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
2315    the basic block containing the jump.  */
2316
2317 static int
2318 reorg_redirect_jump (jump, nlabel)
2319      rtx jump;
2320      rtx nlabel;
2321 {
2322   int b = find_basic_block (jump);
2323
2324   if (b != -1)
2325     bb_ticks[b]++;
2326
2327   return redirect_jump (jump, nlabel);
2328 }
2329
2330 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
2331    We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
2332    that reference values used in INSN.  If we find one, then we move the
2333    REG_DEAD note to INSN.
2334
2335    This is needed to handle the case where an later insn (after INSN) has a
2336    REG_DEAD note for a register used by INSN, and this later insn subsequently
2337    gets moved before a CODE_LABEL because it is a redundant insn.  In this
2338    case, mark_target_live_regs may be confused into thinking the register
2339    is dead because it sees a REG_DEAD note immediately before a CODE_LABEL.  */
2340
2341 static void
2342 update_reg_dead_notes (insn, delayed_insn)
2343      rtx insn, delayed_insn;
2344 {
2345   rtx p, link, next;
2346
2347   for (p = next_nonnote_insn (insn); p != delayed_insn;
2348        p = next_nonnote_insn (p))
2349     for (link = REG_NOTES (p); link; link = next)
2350       {
2351         next = XEXP (link, 1);
2352
2353         if (REG_NOTE_KIND (link) != REG_DEAD
2354             || GET_CODE (XEXP (link, 0)) != REG)
2355           continue;
2356
2357         if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
2358           {
2359             /* Move the REG_DEAD note from P to INSN.  */
2360             remove_note (p, link);
2361             XEXP (link, 1) = REG_NOTES (insn);
2362             REG_NOTES (insn) = link;
2363           }
2364       }
2365 }
2366
2367 /* Called when an insn redundant with start_insn is deleted.  If there
2368    is a REG_DEAD note for the target of start_insn between start_insn
2369    and stop_insn, then the REG_DEAD note needs to be deleted since the
2370    value no longer dies there.
2371
2372    If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
2373    confused into thinking the register is dead.  */
2374
2375 static void
2376 fix_reg_dead_note (start_insn, stop_insn)
2377      rtx start_insn, stop_insn;
2378 {
2379   rtx p, link, next;
2380
2381   for (p = next_nonnote_insn (start_insn); p != stop_insn;
2382        p = next_nonnote_insn (p))
2383     for (link = REG_NOTES (p); link; link = next)
2384       {
2385         next = XEXP (link, 1);
2386
2387         if (REG_NOTE_KIND (link) != REG_DEAD
2388             || GET_CODE (XEXP (link, 0)) != REG)
2389           continue;
2390
2391         if (reg_set_p (XEXP (link, 0), PATTERN (start_insn)))
2392           {
2393             remove_note (p, link);
2394             return;
2395           }
2396       }
2397 }
2398
2399 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
2400
2401    This handles the case of udivmodXi4 instructions which optimize their
2402    output depending on whether any REG_UNUSED notes are present.
2403    we must make sure that INSN calculates as many results as REDUNDANT_INSN
2404    does.  */
2405
2406 static void
2407 update_reg_unused_notes (insn, redundant_insn)
2408      rtx insn, redundant_insn;
2409 {
2410   rtx link, next;
2411
2412   for (link = REG_NOTES (insn); link; link = next)
2413     {
2414       next = XEXP (link, 1);
2415
2416       if (REG_NOTE_KIND (link) != REG_UNUSED
2417           || GET_CODE (XEXP (link, 0)) != REG)
2418         continue;
2419
2420       if (! find_regno_note (redundant_insn, REG_UNUSED,
2421                              REGNO (XEXP (link, 0))))
2422         remove_note (insn, link);
2423     }
2424 }
2425 \f
2426 /* Marks registers possibly live at the current place being scanned by
2427    mark_target_live_regs.  Used only by next two function.    */
2428
2429 static HARD_REG_SET current_live_regs;
2430
2431 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
2432    Also only used by the next two functions.  */
2433
2434 static HARD_REG_SET pending_dead_regs;
2435
2436 /* Utility function called from mark_target_live_regs via note_stores.
2437    It deadens any CLOBBERed registers and livens any SET registers.  */
2438
2439 static void
2440 update_live_status (dest, x)
2441      rtx dest;
2442      rtx x;
2443 {
2444   int first_regno, last_regno;
2445   int i;
2446
2447   if (GET_CODE (dest) != REG
2448       && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
2449     return;
2450
2451   if (GET_CODE (dest) == SUBREG)
2452     first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
2453   else
2454     first_regno = REGNO (dest);
2455
2456   last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
2457
2458   if (GET_CODE (x) == CLOBBER)
2459     for (i = first_regno; i < last_regno; i++)
2460       CLEAR_HARD_REG_BIT (current_live_regs, i);
2461   else
2462     for (i = first_regno; i < last_regno; i++)
2463       {
2464         SET_HARD_REG_BIT (current_live_regs, i);
2465         CLEAR_HARD_REG_BIT (pending_dead_regs, i);
2466       }
2467 }
2468
2469 /* Similar to next_insn, but ignores insns in the delay slots of
2470    an annulled branch.  */
2471
2472 static rtx
2473 next_insn_no_annul (insn)
2474      rtx insn;
2475 {
2476   if (insn)
2477     {
2478       /* If INSN is an annulled branch, skip any insns from the target
2479          of the branch.  */
2480       if (INSN_ANNULLED_BRANCH_P (insn)
2481           && NEXT_INSN (PREV_INSN (insn)) != insn)
2482         while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
2483           insn = NEXT_INSN (insn);
2484
2485       insn = NEXT_INSN (insn);
2486       if (insn && GET_CODE (insn) == INSN
2487           && GET_CODE (PATTERN (insn)) == SEQUENCE)
2488         insn = XVECEXP (PATTERN (insn), 0, 0);
2489     }
2490
2491   return insn;
2492 }
2493 \f
2494 /* A subroutine of mark_target_live_regs.  Search forward from TARGET
2495    looking for registers that are set before they are used.  These are dead.
2496    Stop after passing a few conditional jumps, and/or a small
2497    number of unconditional branches.  */
2498
2499 static rtx
2500 find_dead_or_set_registers (target, res, jump_target, jump_count, set, needed)
2501      rtx target;
2502      struct resources *res;
2503      rtx *jump_target;
2504      int jump_count;
2505      struct resources set, needed;
2506 {
2507   HARD_REG_SET scratch;
2508   rtx insn, next;
2509   rtx jump_insn = 0;
2510   int i;
2511
2512   for (insn = target; insn; insn = next)
2513     {
2514       rtx this_jump_insn = insn;
2515
2516       next = NEXT_INSN (insn);
2517       switch (GET_CODE (insn))
2518         {
2519         case CODE_LABEL:
2520           /* After a label, any pending dead registers that weren't yet
2521              used can be made dead.  */
2522           AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2523           AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2524           CLEAR_HARD_REG_SET (pending_dead_regs);
2525
2526           if (CODE_LABEL_NUMBER (insn) < max_label_num_after_reload)
2527             {
2528               /* All spill registers are dead at a label, so kill all of the
2529                  ones that aren't needed also.  */
2530               COPY_HARD_REG_SET (scratch, used_spill_regs);
2531               AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2532               AND_COMPL_HARD_REG_SET (res->regs, scratch);
2533             }
2534           continue;
2535
2536         case BARRIER:
2537         case NOTE:
2538           continue;
2539
2540         case INSN:
2541           if (GET_CODE (PATTERN (insn)) == USE)
2542             {
2543               /* If INSN is a USE made by update_block, we care about the
2544                  underlying insn.  Any registers set by the underlying insn
2545                  are live since the insn is being done somewhere else.  */
2546               if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2547                 mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1);
2548
2549               /* All other USE insns are to be ignored.  */
2550               continue;
2551             }
2552           else if (GET_CODE (PATTERN (insn)) == CLOBBER)
2553             continue;
2554           else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2555             {
2556               /* An unconditional jump can be used to fill the delay slot
2557                  of a call, so search for a JUMP_INSN in any position.  */
2558               for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2559                 {
2560                   this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
2561                   if (GET_CODE (this_jump_insn) == JUMP_INSN)
2562                     break;
2563                 }
2564             }
2565
2566         default:
2567           break;
2568         }
2569
2570       if (GET_CODE (this_jump_insn) == JUMP_INSN)
2571         {
2572           if (jump_count++ < 10)
2573             {
2574               if (simplejump_p (this_jump_insn)
2575                   || GET_CODE (PATTERN (this_jump_insn)) == RETURN)
2576                 {
2577                   next = JUMP_LABEL (this_jump_insn);
2578                   if (jump_insn == 0)
2579                     {
2580                       jump_insn = insn;
2581                       if (jump_target)
2582                         *jump_target = JUMP_LABEL (this_jump_insn);
2583                     }
2584                 }
2585               else if (condjump_p (this_jump_insn)
2586                        || condjump_in_parallel_p (this_jump_insn))
2587                 {
2588                   struct resources target_set, target_res;
2589                   struct resources fallthrough_res;
2590
2591                   /* We can handle conditional branches here by following
2592                      both paths, and then IOR the results of the two paths
2593                      together, which will give us registers that are dead
2594                      on both paths.  Since this is expensive, we give it
2595                      a much higher cost than unconditional branches.  The
2596                      cost was chosen so that we will follow at most 1
2597                      conditional branch.  */
2598
2599                   jump_count += 4;
2600                   if (jump_count >= 10)
2601                     break;
2602
2603                   mark_referenced_resources (insn, &needed, 1);
2604
2605                   /* For an annulled branch, mark_set_resources ignores slots
2606                      filled by instructions from the target.  This is correct
2607                      if the branch is not taken.  Since we are following both
2608                      paths from the branch, we must also compute correct info
2609                      if the branch is taken.  We do this by inverting all of
2610                      the INSN_FROM_TARGET_P bits, calling mark_set_resources,
2611                      and then inverting the INSN_FROM_TARGET_P bits again.  */
2612
2613                   if (GET_CODE (PATTERN (insn)) == SEQUENCE
2614                       && INSN_ANNULLED_BRANCH_P (this_jump_insn))
2615                     {
2616                       for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
2617                         INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
2618                           = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
2619
2620                       target_set = set;
2621                       mark_set_resources (insn, &target_set, 0, 1);
2622
2623                       for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
2624                         INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
2625                           = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
2626
2627                       mark_set_resources (insn, &set, 0, 1);
2628                     }
2629                   else
2630                     {
2631                       mark_set_resources (insn, &set, 0, 1);
2632                       target_set = set;
2633                     }
2634
2635                   target_res = *res;
2636                   COPY_HARD_REG_SET (scratch, target_set.regs);
2637                   AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2638                   AND_COMPL_HARD_REG_SET (target_res.regs, scratch);
2639
2640                   fallthrough_res = *res;
2641                   COPY_HARD_REG_SET (scratch, set.regs);
2642                   AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2643                   AND_COMPL_HARD_REG_SET (fallthrough_res.regs, scratch);
2644
2645                   find_dead_or_set_registers (JUMP_LABEL (this_jump_insn),
2646                                               &target_res, 0, jump_count,
2647                                               target_set, needed);
2648                   find_dead_or_set_registers (next,
2649                                               &fallthrough_res, 0, jump_count,
2650                                               set, needed);
2651                   IOR_HARD_REG_SET (fallthrough_res.regs, target_res.regs);
2652                   AND_HARD_REG_SET (res->regs, fallthrough_res.regs);
2653                   break;
2654                 }
2655               else
2656                 break;
2657             }
2658           else
2659             {
2660               /* Don't try this optimization if we expired our jump count
2661                  above, since that would mean there may be an infinite loop
2662                  in the function being compiled.  */
2663               jump_insn = 0;
2664               break;
2665             }
2666         }
2667
2668       mark_referenced_resources (insn, &needed, 1);
2669       mark_set_resources (insn, &set, 0, 1);
2670
2671       COPY_HARD_REG_SET (scratch, set.regs);
2672       AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2673       AND_COMPL_HARD_REG_SET (res->regs, scratch);
2674     }
2675
2676   return jump_insn;
2677 }
2678
2679 /* Set the resources that are live at TARGET.
2680
2681    If TARGET is zero, we refer to the end of the current function and can
2682    return our precomputed value.
2683
2684    Otherwise, we try to find out what is live by consulting the basic block
2685    information.  This is tricky, because we must consider the actions of
2686    reload and jump optimization, which occur after the basic block information
2687    has been computed.
2688
2689    Accordingly, we proceed as follows::
2690
2691    We find the previous BARRIER and look at all immediately following labels
2692    (with no intervening active insns) to see if any of them start a basic
2693    block.  If we hit the start of the function first, we use block 0.
2694
2695    Once we have found a basic block and a corresponding first insns, we can
2696    accurately compute the live status from basic_block_live_regs and
2697    reg_renumber.  (By starting at a label following a BARRIER, we are immune
2698    to actions taken by reload and jump.)  Then we scan all insns between
2699    that point and our target.  For each CLOBBER (or for call-clobbered regs
2700    when we pass a CALL_INSN), mark the appropriate registers are dead.  For
2701    a SET, mark them as live.
2702
2703    We have to be careful when using REG_DEAD notes because they are not
2704    updated by such things as find_equiv_reg.  So keep track of registers
2705    marked as dead that haven't been assigned to, and mark them dead at the
2706    next CODE_LABEL since reload and jump won't propagate values across labels.
2707
2708    If we cannot find the start of a basic block (should be a very rare
2709    case, if it can happen at all), mark everything as potentially live.
2710
2711    Next, scan forward from TARGET looking for things set or clobbered
2712    before they are used.  These are not live.
2713
2714    Because we can be called many times on the same target, save our results
2715    in a hash table indexed by INSN_UID.  */
2716
2717 static void
2718 mark_target_live_regs (target, res)
2719      rtx target;
2720      struct resources *res;
2721 {
2722   int b = -1;
2723   int i;
2724   struct target_info *tinfo;
2725   rtx insn;
2726   rtx jump_insn = 0;
2727   rtx jump_target;
2728   HARD_REG_SET scratch;
2729   struct resources set, needed;
2730
2731   /* Handle end of function.  */
2732   if (target == 0)
2733     {
2734       *res = end_of_function_needs;
2735       return;
2736     }
2737
2738   /* We have to assume memory is needed, but the CC isn't.  */
2739   res->memory = 1;
2740   res->volatil = res->unch_memory = 0;
2741   res->cc = 0;
2742
2743   /* See if we have computed this value already.  */
2744   for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2745        tinfo; tinfo = tinfo->next)
2746     if (tinfo->uid == INSN_UID (target))
2747       break;
2748
2749   /* Start by getting the basic block number.  If we have saved information,
2750      we can get it from there unless the insn at the start of the basic block
2751      has been deleted.  */
2752   if (tinfo && tinfo->block != -1
2753       && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
2754     b = tinfo->block;
2755
2756   if (b == -1)
2757     b = find_basic_block (target);
2758
2759   if (tinfo)
2760     {
2761       /* If the information is up-to-date, use it.  Otherwise, we will
2762          update it below.  */
2763       if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
2764         {
2765           COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
2766           return;
2767         }
2768     }
2769   else
2770     {
2771       /* Allocate a place to put our results and chain it into the
2772          hash table.  */
2773       tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
2774       tinfo->uid = INSN_UID (target);
2775       tinfo->block = b;
2776       tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2777       target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
2778     }
2779
2780   CLEAR_HARD_REG_SET (pending_dead_regs);
2781
2782   /* If we found a basic block, get the live registers from it and update
2783      them with anything set or killed between its start and the insn before
2784      TARGET.  Otherwise, we must assume everything is live.  */
2785   if (b != -1)
2786     {
2787       regset regs_live = basic_block_live_at_start[b];
2788       int j;
2789       int regno;
2790       rtx start_insn, stop_insn;
2791
2792       /* Compute hard regs live at start of block -- this is the real hard regs
2793          marked live, plus live pseudo regs that have been renumbered to
2794          hard regs.  */
2795
2796       REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live);
2797
2798       EXECUTE_IF_SET_IN_REG_SET
2799         (regs_live, FIRST_PSEUDO_REGISTER, i,
2800          {
2801            if ((regno = reg_renumber[i]) >= 0)
2802              for (j = regno;
2803                   j < regno + HARD_REGNO_NREGS (regno,
2804                                                 PSEUDO_REGNO_MODE (i));
2805                   j++)
2806                SET_HARD_REG_BIT (current_live_regs, j);
2807          });
2808
2809       /* Get starting and ending insn, handling the case where each might
2810          be a SEQUENCE.  */
2811       start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2812       stop_insn = target;
2813
2814       if (GET_CODE (start_insn) == INSN
2815           && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2816         start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2817
2818       if (GET_CODE (stop_insn) == INSN
2819           && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2820         stop_insn = next_insn (PREV_INSN (stop_insn));
2821
2822       for (insn = start_insn; insn != stop_insn;
2823            insn = next_insn_no_annul (insn))
2824         {
2825           rtx link;
2826           rtx real_insn = insn;
2827
2828           /* If this insn is from the target of a branch, it isn't going to
2829              be used in the sequel.  If it is used in both cases, this
2830              test will not be true.  */
2831           if (INSN_FROM_TARGET_P (insn))
2832             continue;
2833
2834           /* If this insn is a USE made by update_block, we care about the
2835              underlying insn.  */
2836           if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2837               && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2838               real_insn = XEXP (PATTERN (insn), 0);
2839
2840           if (GET_CODE (real_insn) == CALL_INSN)
2841             {
2842               /* CALL clobbers all call-used regs that aren't fixed except
2843                  sp, ap, and fp.  Do this before setting the result of the
2844                  call live.  */
2845               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2846                 if (call_used_regs[i]
2847                     && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2848                     && i != ARG_POINTER_REGNUM
2849 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2850                     && i != HARD_FRAME_POINTER_REGNUM
2851 #endif
2852 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2853                     && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2854 #endif
2855 #ifdef PIC_OFFSET_TABLE_REGNUM
2856                     && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2857 #endif
2858                     )
2859                   CLEAR_HARD_REG_BIT (current_live_regs, i);
2860
2861               /* A CALL_INSN sets any global register live, since it may
2862                  have been modified by the call.  */
2863               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2864                 if (global_regs[i])
2865                   SET_HARD_REG_BIT (current_live_regs, i);
2866             }
2867
2868           /* Mark anything killed in an insn to be deadened at the next
2869              label.  Ignore USE insns; the only REG_DEAD notes will be for
2870              parameters.  But they might be early.  A CALL_INSN will usually
2871              clobber registers used for parameters.  It isn't worth bothering
2872              with the unlikely case when it won't.  */
2873           if ((GET_CODE (real_insn) == INSN
2874                && GET_CODE (PATTERN (real_insn)) != USE
2875                && GET_CODE (PATTERN (real_insn)) != CLOBBER)
2876               || GET_CODE (real_insn) == JUMP_INSN
2877               || GET_CODE (real_insn) == CALL_INSN)
2878             {
2879               for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2880                 if (REG_NOTE_KIND (link) == REG_DEAD
2881                     && GET_CODE (XEXP (link, 0)) == REG
2882                     && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2883                   {
2884                     int first_regno = REGNO (XEXP (link, 0));
2885                     int last_regno
2886                       = (first_regno
2887                          + HARD_REGNO_NREGS (first_regno,
2888                                              GET_MODE (XEXP (link, 0))));
2889
2890                     for (i = first_regno; i < last_regno; i++)
2891                       SET_HARD_REG_BIT (pending_dead_regs, i);
2892                   }
2893
2894               note_stores (PATTERN (real_insn), update_live_status);
2895
2896               /* If any registers were unused after this insn, kill them.
2897                  These notes will always be accurate.  */
2898               for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2899                 if (REG_NOTE_KIND (link) == REG_UNUSED
2900                     && GET_CODE (XEXP (link, 0)) == REG
2901                     && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2902                   {
2903                     int first_regno = REGNO (XEXP (link, 0));
2904                     int last_regno
2905                       = (first_regno
2906                          + HARD_REGNO_NREGS (first_regno,
2907                                              GET_MODE (XEXP (link, 0))));
2908
2909                     for (i = first_regno; i < last_regno; i++)
2910                       CLEAR_HARD_REG_BIT (current_live_regs, i);
2911                   }
2912             }
2913
2914           else if (GET_CODE (real_insn) == CODE_LABEL)
2915             {
2916               /* A label clobbers the pending dead registers since neither
2917                  reload nor jump will propagate a value across a label.  */
2918               AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2919               CLEAR_HARD_REG_SET (pending_dead_regs);
2920             }
2921
2922           /* The beginning of the epilogue corresponds to the end of the
2923              RTL chain when there are no epilogue insns.  Certain resources
2924              are implicitly required at that point.  */
2925           else if (GET_CODE (real_insn) == NOTE
2926                    && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG)
2927             IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs);
2928         }
2929
2930       COPY_HARD_REG_SET (res->regs, current_live_regs);
2931       tinfo->block = b;
2932       tinfo->bb_tick = bb_ticks[b];
2933     }
2934   else
2935     /* We didn't find the start of a basic block.  Assume everything
2936        in use.  This should happen only extremely rarely.  */
2937     SET_HARD_REG_SET (res->regs);
2938
2939   CLEAR_RESOURCE (&set);
2940   CLEAR_RESOURCE (&needed);
2941
2942   jump_insn = find_dead_or_set_registers (target, res, &jump_target, 0,
2943                                           set, needed);
2944
2945   /* If we hit an unconditional branch, we have another way of finding out
2946      what is live: we can see what is live at the branch target and include
2947      anything used but not set before the branch.  The only things that are
2948      live are those that are live using the above test and the test below.  */
2949
2950   if (jump_insn)
2951     {
2952       struct resources new_resources;
2953       rtx stop_insn = next_active_insn (jump_insn);
2954
2955       mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2956       CLEAR_RESOURCE (&set);
2957       CLEAR_RESOURCE (&needed);
2958
2959       /* Include JUMP_INSN in the needed registers.  */
2960       for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2961         {
2962           mark_referenced_resources (insn, &needed, 1);
2963
2964           COPY_HARD_REG_SET (scratch, needed.regs);
2965           AND_COMPL_HARD_REG_SET (scratch, set.regs);
2966           IOR_HARD_REG_SET (new_resources.regs, scratch);
2967
2968           mark_set_resources (insn, &set, 0, 1);
2969         }
2970
2971       AND_HARD_REG_SET (res->regs, new_resources.regs);
2972     }
2973
2974   COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2975 }
2976 \f
2977 /* Scan a function looking for insns that need a delay slot and find insns to
2978    put into the delay slot.
2979
2980    NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2981    as calls).  We do these first since we don't want jump insns (that are
2982    easier to fill) to get the only insns that could be used for non-jump insns.
2983    When it is zero, only try to fill JUMP_INSNs.
2984
2985    When slots are filled in this manner, the insns (including the
2986    delay_insn) are put together in a SEQUENCE rtx.  In this fashion,
2987    it is possible to tell whether a delay slot has really been filled
2988    or not.  `final' knows how to deal with this, by communicating
2989    through FINAL_SEQUENCE.  */
2990
2991 static void
2992 fill_simple_delay_slots (non_jumps_p)
2993      int non_jumps_p;
2994 {
2995   register rtx insn, pat, trial, next_trial;
2996   register int i;
2997   int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2998   struct resources needed, set;
2999   int slots_to_fill, slots_filled;
3000   rtx delay_list;
3001
3002   for (i = 0; i < num_unfilled_slots; i++)
3003     {
3004       int flags;
3005       /* Get the next insn to fill.  If it has already had any slots assigned,
3006          we can't do anything with it.  Maybe we'll improve this later.  */
3007
3008       insn = unfilled_slots_base[i];
3009       if (insn == 0
3010           || INSN_DELETED_P (insn)
3011           || (GET_CODE (insn) == INSN
3012               && GET_CODE (PATTERN (insn)) == SEQUENCE)
3013           || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
3014           || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
3015         continue;
3016
3017       if (GET_CODE (insn) == JUMP_INSN)
3018         flags = get_jump_flags (insn, JUMP_LABEL (insn));
3019       else
3020         flags = get_jump_flags (insn, NULL_RTX);
3021       slots_to_fill = num_delay_slots (insn);
3022       if (slots_to_fill == 0)
3023         abort ();
3024
3025       /* This insn needs, or can use, some delay slots.  SLOTS_TO_FILL
3026          says how many.  After initialization, first try optimizing
3027
3028          call _foo              call _foo
3029          nop                    add %o7,.-L1,%o7
3030          b,a L1
3031          nop
3032
3033          If this case applies, the delay slot of the call is filled with
3034          the unconditional jump.  This is done first to avoid having the
3035          delay slot of the call filled in the backward scan.  Also, since
3036          the unconditional jump is likely to also have a delay slot, that
3037          insn must exist when it is subsequently scanned.
3038
3039          This is tried on each insn with delay slots as some machines
3040          have insns which perform calls, but are not represented as
3041          CALL_INSNs.  */
3042
3043       slots_filled = 0;
3044       delay_list = 0;
3045
3046       if ((trial = next_active_insn (insn))
3047           && GET_CODE (trial) == JUMP_INSN
3048           && simplejump_p (trial)
3049           && eligible_for_delay (insn, slots_filled, trial, flags)
3050           && no_labels_between_p (insn, trial))
3051         {
3052           rtx *tmp;
3053           slots_filled++;
3054           delay_list = add_to_delay_list (trial, delay_list);
3055
3056           /* TRIAL may have had its delay slot filled, then unfilled.  When
3057              the delay slot is unfilled, TRIAL is placed back on the unfilled
3058              slots obstack.  Unfortunately, it is placed on the end of the
3059              obstack, not in its original location.  Therefore, we must search
3060              from entry i + 1 to the end of the unfilled slots obstack to
3061              try and find TRIAL.  */
3062           tmp = &unfilled_slots_base[i + 1];
3063           while (*tmp != trial && tmp != unfilled_slots_next)
3064             tmp++;
3065
3066           /* Remove the unconditional jump from consideration for delay slot
3067              filling and unthread it.   */
3068           if (*tmp == trial)
3069             *tmp = 0;
3070           {
3071             rtx next = NEXT_INSN (trial);
3072             rtx prev = PREV_INSN (trial);
3073             if (prev)
3074               NEXT_INSN (prev) = next;
3075             if (next)
3076               PREV_INSN (next) = prev;
3077           }
3078         }
3079
3080       /* Now, scan backwards from the insn to search for a potential
3081          delay-slot candidate.  Stop searching when a label or jump is hit.
3082
3083          For each candidate, if it is to go into the delay slot (moved
3084          forward in execution sequence), it must not need or set any resources
3085          that were set by later insns and must not set any resources that
3086          are needed for those insns.
3087
3088          The delay slot insn itself sets resources unless it is a call
3089          (in which case the called routine, not the insn itself, is doing
3090          the setting).  */
3091
3092       if (slots_filled < slots_to_fill)
3093         {
3094           CLEAR_RESOURCE (&needed);
3095           CLEAR_RESOURCE (&set);
3096           mark_set_resources (insn, &set, 0, 0);
3097           mark_referenced_resources (insn, &needed, 0);
3098
3099           for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
3100                trial = next_trial)
3101             {
3102               next_trial = prev_nonnote_insn (trial);
3103
3104               /* This must be an INSN or CALL_INSN.  */
3105               pat = PATTERN (trial);
3106
3107               /* USE and CLOBBER at this level was just for flow; ignore it.  */
3108               if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3109                 continue;
3110
3111               /* Check for resource conflict first, to avoid unnecessary
3112                  splitting.  */
3113               if (! insn_references_resource_p (trial, &set, 1)
3114                   && ! insn_sets_resource_p (trial, &set, 1)
3115                   && ! insn_sets_resource_p (trial, &needed, 1)
3116 #ifdef HAVE_cc0
3117                   /* Can't separate set of cc0 from its use.  */
3118                   && ! (reg_mentioned_p (cc0_rtx, pat)
3119                         && ! sets_cc0_p (cc0_rtx, pat))
3120 #endif
3121                   )
3122                 {
3123                   trial = try_split (pat, trial, 1);
3124                   next_trial = prev_nonnote_insn (trial);
3125                   if (eligible_for_delay (insn, slots_filled, trial, flags))
3126                     {
3127                       /* In this case, we are searching backward, so if we
3128                          find insns to put on the delay list, we want
3129                          to put them at the head, rather than the
3130                          tail, of the list.  */
3131
3132                       update_reg_dead_notes (trial, insn);
3133                       delay_list = gen_rtx_INSN_LIST (VOIDmode,
3134                                                       trial, delay_list);
3135                       update_block (trial, trial);
3136                       delete_insn (trial);
3137                       if (slots_to_fill == ++slots_filled)
3138                         break;
3139                       continue;
3140                     }
3141                 }
3142
3143               mark_set_resources (trial, &set, 0, 1);
3144               mark_referenced_resources (trial, &needed, 1);
3145             }
3146         }
3147
3148       /* If all needed slots haven't been filled, we come here.  */
3149
3150       /* Try to optimize case of jumping around a single insn.  */
3151 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
3152       if (slots_filled != slots_to_fill
3153           && delay_list == 0
3154           && GET_CODE (insn) == JUMP_INSN
3155           && (condjump_p (insn) || condjump_in_parallel_p (insn)))
3156         {
3157           delay_list = optimize_skip (insn);
3158           if (delay_list)
3159             slots_filled += 1;
3160         }
3161 #endif
3162
3163       /* Try to get insns from beyond the insn needing the delay slot.
3164          These insns can neither set or reference resources set in insns being
3165          skipped, cannot set resources in the insn being skipped, and, if this
3166          is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
3167          call might not return).
3168
3169          There used to be code which continued past the target label if
3170          we saw all uses of the target label.  This code did not work,
3171          because it failed to account for some instructions which were
3172          both annulled and marked as from the target.  This can happen as a
3173          result of optimize_skip.  Since this code was redundant with
3174          fill_eager_delay_slots anyways, it was just deleted.  */
3175
3176       if (slots_filled != slots_to_fill
3177           && (GET_CODE (insn) != JUMP_INSN
3178               || ((condjump_p (insn) || condjump_in_parallel_p (insn))
3179                    && ! simplejump_p (insn)
3180                    && JUMP_LABEL (insn) != 0)))
3181         {
3182           rtx target = 0;
3183           int maybe_never = 0;
3184           struct resources needed_at_jump;
3185
3186           CLEAR_RESOURCE (&needed);
3187           CLEAR_RESOURCE (&set);
3188
3189           if (GET_CODE (insn) == CALL_INSN)
3190             {
3191               mark_set_resources (insn, &set, 0, 1);
3192               mark_referenced_resources (insn, &needed, 1);
3193               maybe_never = 1;
3194             }
3195           else
3196             {
3197               mark_set_resources (insn, &set, 0, 1);
3198               mark_referenced_resources (insn, &needed, 1);
3199               if (GET_CODE (insn) == JUMP_INSN)
3200                 target = JUMP_LABEL (insn);
3201             }
3202
3203           for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
3204             {
3205               rtx pat, trial_delay;
3206
3207               next_trial = next_nonnote_insn (trial);
3208
3209               if (GET_CODE (trial) == CODE_LABEL
3210                   || GET_CODE (trial) == BARRIER)
3211                 break;
3212
3213               /* We must have an INSN, JUMP_INSN, or CALL_INSN.  */
3214               pat = PATTERN (trial);
3215
3216               /* Stand-alone USE and CLOBBER are just for flow.  */
3217               if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3218                 continue;
3219
3220               /* If this already has filled delay slots, get the insn needing
3221                  the delay slots.  */
3222               if (GET_CODE (pat) == SEQUENCE)
3223                 trial_delay = XVECEXP (pat, 0, 0);
3224               else
3225                 trial_delay = trial;
3226
3227               /* If this is a jump insn to our target, indicate that we have
3228                  seen another jump to it.  If we aren't handling a conditional
3229                  jump, stop our search. Otherwise, compute the needs at its
3230                  target and add them to NEEDED.  */
3231               if (GET_CODE (trial_delay) == JUMP_INSN)
3232                 {
3233                   if (target == 0)
3234                     break;
3235                   else if (JUMP_LABEL (trial_delay) != target)
3236                     {
3237                       mark_target_live_regs
3238                         (next_active_insn (JUMP_LABEL (trial_delay)),
3239                          &needed_at_jump);
3240                       needed.memory |= needed_at_jump.memory;
3241                       needed.unch_memory |= needed_at_jump.unch_memory;
3242                       IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
3243                     }
3244                 }
3245
3246               /* See if we have a resource problem before we try to
3247                  split.   */
3248               if (target == 0
3249                   && GET_CODE (pat) != SEQUENCE
3250                   && ! insn_references_resource_p (trial, &set, 1)
3251                   && ! insn_sets_resource_p (trial, &set, 1)
3252                   && ! insn_sets_resource_p (trial, &needed, 1)
3253 #ifdef HAVE_cc0
3254                   && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
3255 #endif
3256                   && ! (maybe_never && may_trap_p (pat))
3257                   && (trial = try_split (pat, trial, 0))
3258                   && eligible_for_delay (insn, slots_filled, trial, flags))
3259                 {
3260                   next_trial = next_nonnote_insn (trial);
3261                   delay_list = add_to_delay_list (trial, delay_list);
3262
3263 #ifdef HAVE_cc0
3264                   if (reg_mentioned_p (cc0_rtx, pat))
3265                     link_cc0_insns (trial);
3266 #endif
3267
3268                   delete_insn (trial);
3269                   if (slots_to_fill == ++slots_filled)
3270                     break;
3271                   continue;
3272                 }
3273
3274               mark_set_resources (trial, &set, 0, 1);
3275               mark_referenced_resources (trial, &needed, 1);
3276
3277               /* Ensure we don't put insns between the setting of cc and the
3278                  comparison by moving a setting of cc into an earlier delay
3279                  slot since these insns could clobber the condition code.  */
3280               set.cc = 1;
3281
3282               /* If this is a call or jump, we might not get here.  */
3283               if (GET_CODE (trial_delay) == CALL_INSN
3284                   || GET_CODE (trial_delay) == JUMP_INSN)
3285                 maybe_never = 1;
3286             }
3287
3288           /* If there are slots left to fill and our search was stopped by an
3289              unconditional branch, try the insn at the branch target.  We can
3290              redirect the branch if it works.
3291
3292              Don't do this if the insn at the branch target is a branch.  */
3293           if (slots_to_fill != slots_filled
3294               && trial
3295               && GET_CODE (trial) == JUMP_INSN
3296               && simplejump_p (trial)
3297               && (target == 0 || JUMP_LABEL (trial) == target)
3298               && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
3299               && ! (GET_CODE (next_trial) == INSN
3300                     && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
3301               && GET_CODE (next_trial) != JUMP_INSN
3302               && ! insn_references_resource_p (next_trial, &set, 1)
3303               && ! insn_sets_resource_p (next_trial, &set, 1)
3304               && ! insn_sets_resource_p (next_trial, &needed, 1)
3305 #ifdef HAVE_cc0
3306               && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
3307 #endif
3308               && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
3309               && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
3310               && eligible_for_delay (insn, slots_filled, next_trial, flags))
3311             {
3312               rtx new_label = next_active_insn (next_trial);
3313
3314               if (new_label != 0)
3315                 new_label = get_label_before (new_label);
3316               else
3317                 new_label = find_end_label ();
3318
3319               delay_list
3320                 = add_to_delay_list (copy_rtx (next_trial), delay_list);
3321               slots_filled++;
3322               reorg_redirect_jump (trial, new_label);
3323
3324               /* If we merged because we both jumped to the same place,
3325                  redirect the original insn also.  */
3326               if (target)
3327                 reorg_redirect_jump (insn, new_label);
3328             }
3329         }
3330
3331       /* If this is an unconditional jump, then try to get insns from the
3332          target of the jump.  */
3333       if (GET_CODE (insn) == JUMP_INSN
3334           && simplejump_p (insn)
3335           && slots_filled != slots_to_fill)
3336         delay_list
3337           = fill_slots_from_thread (insn, const_true_rtx,
3338                                     next_active_insn (JUMP_LABEL (insn)),
3339                                     NULL, 1, 1,
3340                                     own_thread_p (JUMP_LABEL (insn),
3341                                                   JUMP_LABEL (insn), 0),
3342                                     slots_to_fill, &slots_filled,
3343                                     delay_list);
3344
3345       if (delay_list)
3346         unfilled_slots_base[i]
3347           = emit_delay_sequence (insn, delay_list, slots_filled);
3348
3349       if (slots_to_fill == slots_filled)
3350         unfilled_slots_base[i] = 0;
3351
3352       note_delay_statistics (slots_filled, 0);
3353     }
3354
3355 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3356   /* See if the epilogue needs any delay slots.  Try to fill them if so.
3357      The only thing we can do is scan backwards from the end of the
3358      function.  If we did this in a previous pass, it is incorrect to do it
3359      again.  */
3360   if (current_function_epilogue_delay_list)
3361     return;
3362
3363   slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
3364   if (slots_to_fill == 0)
3365     return;
3366
3367   slots_filled = 0;
3368   CLEAR_RESOURCE (&set);
3369
3370   /* The frame pointer and stack pointer are needed at the beginning of
3371      the epilogue, so instructions setting them can not be put in the
3372      epilogue delay slot.  However, everything else needed at function
3373      end is safe, so we don't want to use end_of_function_needs here.  */
3374   CLEAR_RESOURCE (&needed);
3375   if (frame_pointer_needed)
3376     {
3377       SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
3378 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3379       SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
3380 #endif
3381 #ifdef EXIT_IGNORE_STACK
3382       if (! EXIT_IGNORE_STACK)
3383 #endif
3384         SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3385     }
3386   else
3387     SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3388
3389 #ifdef EPILOGUE_USES
3390   for (i = 0; i <FIRST_PSEUDO_REGISTER; i++)
3391     {
3392       if (EPILOGUE_USES (i))
3393         SET_HARD_REG_BIT (needed.regs, i);
3394     }
3395 #endif
3396
3397   for (trial = get_last_insn (); ! stop_search_p (trial, 1);
3398        trial = PREV_INSN (trial))
3399     {
3400       if (GET_CODE (trial) == NOTE)
3401         continue;
3402       pat = PATTERN (trial);
3403       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3404         continue;
3405
3406       if (! insn_references_resource_p (trial, &set, 1)
3407           && ! insn_sets_resource_p (trial, &needed, 1)
3408           && ! insn_sets_resource_p (trial, &set, 1)
3409 #ifdef HAVE_cc0
3410           /* Don't want to mess with cc0 here.  */
3411           && ! reg_mentioned_p (cc0_rtx, pat)
3412 #endif
3413           )
3414         {
3415           trial = try_split (pat, trial, 1);
3416           if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
3417             {
3418               /* Here as well we are searching backward, so put the
3419                  insns we find on the head of the list.  */
3420
3421               current_function_epilogue_delay_list
3422                 = gen_rtx_INSN_LIST (VOIDmode, trial,
3423                                      current_function_epilogue_delay_list);
3424               mark_referenced_resources (trial, &end_of_function_needs, 1);
3425               update_block (trial, trial);
3426               delete_insn (trial);
3427
3428               /* Clear deleted bit so final.c will output the insn.  */
3429               INSN_DELETED_P (trial) = 0;
3430
3431               if (slots_to_fill == ++slots_filled)
3432                 break;
3433               continue;
3434             }
3435         }
3436
3437       mark_set_resources (trial, &set, 0, 1);
3438       mark_referenced_resources (trial, &needed, 1);
3439     }
3440
3441   note_delay_statistics (slots_filled, 0);
3442 #endif
3443 }
3444 \f
3445 /* Try to find insns to place in delay slots.
3446
3447    INSN is the jump needing SLOTS_TO_FILL delay slots.  It tests CONDITION
3448    or is an unconditional branch if CONDITION is const_true_rtx.
3449    *PSLOTS_FILLED is updated with the number of slots that we have filled.
3450
3451    THREAD is a flow-of-control, either the insns to be executed if the
3452    branch is true or if the branch is false, THREAD_IF_TRUE says which.
3453
3454    OPPOSITE_THREAD is the thread in the opposite direction.  It is used
3455    to see if any potential delay slot insns set things needed there.
3456
3457    LIKELY is non-zero if it is extremely likely that the branch will be
3458    taken and THREAD_IF_TRUE is set.  This is used for the branch at the
3459    end of a loop back up to the top.
3460
3461    OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
3462    thread.  I.e., it is the fallthrough code of our jump or the target of the
3463    jump when we are the only jump going there.
3464
3465    If OWN_THREAD is false, it must be the "true" thread of a jump.  In that
3466    case, we can only take insns from the head of the thread for our delay
3467    slot.  We then adjust the jump to point after the insns we have taken.  */
3468
3469 static rtx
3470 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
3471                         thread_if_true, own_thread,
3472                         slots_to_fill, pslots_filled, delay_list)
3473      rtx insn;
3474      rtx condition;
3475      rtx thread, opposite_thread;
3476      int likely;
3477      int thread_if_true;
3478      int own_thread;
3479      int slots_to_fill, *pslots_filled;
3480      rtx delay_list;
3481 {
3482   rtx new_thread;
3483   struct resources opposite_needed, set, needed;
3484   rtx trial;
3485   int lose = 0;
3486   int must_annul = 0;
3487   int flags;
3488
3489   /* Validate our arguments.  */
3490   if ((condition == const_true_rtx && ! thread_if_true)
3491       || (! own_thread && ! thread_if_true))
3492     abort ();
3493
3494   flags = get_jump_flags (insn, JUMP_LABEL (insn));
3495
3496   /* If our thread is the end of subroutine, we can't get any delay
3497      insns from that.  */
3498   if (thread == 0)
3499       return delay_list;
3500
3501   /* If this is an unconditional branch, nothing is needed at the
3502      opposite thread.  Otherwise, compute what is needed there.  */
3503   if (condition == const_true_rtx)
3504     CLEAR_RESOURCE (&opposite_needed);
3505   else
3506     mark_target_live_regs (opposite_thread, &opposite_needed);
3507
3508   /* If the insn at THREAD can be split, do it here to avoid having to
3509      update THREAD and NEW_THREAD if it is done in the loop below.  Also
3510      initialize NEW_THREAD.  */
3511
3512   new_thread = thread = try_split (PATTERN (thread), thread, 0);
3513
3514   /* Scan insns at THREAD.  We are looking for an insn that can be removed
3515      from THREAD (it neither sets nor references resources that were set
3516      ahead of it and it doesn't set anything needs by the insns ahead of
3517      it) and that either can be placed in an annulling insn or aren't
3518      needed at OPPOSITE_THREAD.  */
3519
3520   CLEAR_RESOURCE (&needed);
3521   CLEAR_RESOURCE (&set);
3522
3523   /* If we do not own this thread, we must stop as soon as we find
3524      something that we can't put in a delay slot, since all we can do
3525      is branch into THREAD at a later point.  Therefore, labels stop
3526      the search if this is not the `true' thread.  */
3527
3528   for (trial = thread;
3529        ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
3530        trial = next_nonnote_insn (trial))
3531     {
3532       rtx pat, old_trial;
3533
3534       /* If we have passed a label, we no longer own this thread.  */
3535       if (GET_CODE (trial) == CODE_LABEL)
3536         {
3537           own_thread = 0;
3538           continue;
3539         }
3540
3541       pat = PATTERN (trial);
3542       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3543         continue;
3544
3545       /* If TRIAL conflicts with the insns ahead of it, we lose.  Also,
3546          don't separate or copy insns that set and use CC0.  */
3547       if (! insn_references_resource_p (trial, &set, 1)
3548           && ! insn_sets_resource_p (trial, &set, 1)
3549           && ! insn_sets_resource_p (trial, &needed, 1)
3550 #ifdef HAVE_cc0
3551           && ! (reg_mentioned_p (cc0_rtx, pat)
3552                 && (! own_thread || ! sets_cc0_p (pat)))
3553 #endif
3554           )
3555         {
3556           rtx prior_insn;
3557
3558           /* If TRIAL is redundant with some insn before INSN, we don't
3559              actually need to add it to the delay list; we can merely pretend
3560              we did.  */
3561           if ((prior_insn = redundant_insn (trial, insn, delay_list)))
3562             {
3563               fix_reg_dead_note (prior_insn, insn);
3564               if (own_thread)
3565                 {
3566                   update_block (trial, thread);
3567                   if (trial == thread)
3568                     {
3569                       thread = next_active_insn (thread);
3570                       if (new_thread == trial)
3571                         new_thread = thread;
3572                     }
3573
3574                   delete_insn (trial);
3575                 }
3576               else
3577                 {
3578                   update_reg_unused_notes (prior_insn, trial);
3579                   new_thread = next_active_insn (trial);
3580                 }
3581
3582               continue;
3583             }
3584
3585           /* There are two ways we can win:  If TRIAL doesn't set anything
3586              needed at the opposite thread and can't trap, or if it can
3587              go into an annulled delay slot.  */
3588           if (condition == const_true_rtx
3589               || (! insn_sets_resource_p (trial, &opposite_needed, 1)
3590                   && ! may_trap_p (pat)))
3591             {
3592               old_trial = trial;
3593               trial = try_split (pat, trial, 0);
3594               if (new_thread == old_trial)
3595                 new_thread = trial;
3596               if (thread == old_trial)
3597                 thread = trial;
3598               pat = PATTERN (trial);
3599               if (eligible_for_delay (insn, *pslots_filled, trial, flags))
3600                 goto winner;
3601             }
3602           else if (0
3603 #ifdef ANNUL_IFTRUE_SLOTS
3604                    || ! thread_if_true
3605 #endif
3606 #ifdef ANNUL_IFFALSE_SLOTS
3607                    || thread_if_true
3608 #endif
3609                    )
3610             {
3611               old_trial = trial;
3612               trial = try_split (pat, trial, 0);
3613               if (new_thread == old_trial)
3614                 new_thread = trial;
3615               if (thread == old_trial)
3616                 thread = trial;
3617               pat = PATTERN (trial);
3618               if ((thread_if_true
3619                    ? eligible_for_annul_false (insn, *pslots_filled, trial, flags)
3620                    : eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
3621                 {
3622                   rtx temp;
3623
3624                   must_annul = 1;
3625                 winner:
3626
3627 #ifdef HAVE_cc0
3628                   if (reg_mentioned_p (cc0_rtx, pat))
3629                     link_cc0_insns (trial);
3630 #endif
3631
3632                   /* If we own this thread, delete the insn.  If this is the
3633                      destination of a branch, show that a basic block status
3634                      may have been updated.  In any case, mark the new
3635                      starting point of this thread.  */
3636                   if (own_thread)
3637                     {
3638                       update_block (trial, thread);
3639                       if (trial == thread)
3640                         {
3641                           thread = next_active_insn (thread);
3642                           if (new_thread == trial)
3643                             new_thread = thread;
3644                         }
3645                       delete_insn (trial);
3646                     }
3647                   else
3648                     new_thread = next_active_insn (trial);
3649
3650                   temp = own_thread ? trial : copy_rtx (trial);
3651                   if (thread_if_true)
3652                     INSN_FROM_TARGET_P (temp) = 1;
3653
3654                   delay_list = add_to_delay_list (temp, delay_list);
3655
3656                   mark_set_resources (trial, &opposite_needed, 0, 1);
3657
3658                   if (slots_to_fill == ++(*pslots_filled))
3659                     {
3660                       /* Even though we have filled all the slots, we
3661                          may be branching to a location that has a
3662                          redundant insn.  Skip any if so.  */
3663                       while (new_thread && ! own_thread
3664                              && ! insn_sets_resource_p (new_thread, &set, 1)
3665                              && ! insn_sets_resource_p (new_thread, &needed, 1)
3666                              && ! insn_references_resource_p (new_thread,
3667                                                               &set, 1)
3668                              && (prior_insn
3669                                  = redundant_insn (new_thread, insn,
3670                                                    delay_list)))
3671                         {
3672                           /* We know we do not own the thread, so no need
3673                              to call update_block and delete_insn.  */
3674                           fix_reg_dead_note (prior_insn, insn);
3675                           update_reg_unused_notes (prior_insn, new_thread);
3676                           new_thread = next_active_insn (new_thread);
3677                         }
3678                       break;
3679                     }
3680
3681                   continue;
3682                 }
3683             }
3684         }
3685
3686       /* This insn can't go into a delay slot.  */
3687       lose = 1;
3688       mark_set_resources (trial, &set, 0, 1);
3689       mark_referenced_resources (trial, &needed, 1);
3690
3691       /* Ensure we don't put insns between the setting of cc and the comparison
3692          by moving a setting of cc into an earlier delay slot since these insns
3693          could clobber the condition code.  */
3694       set.cc = 1;
3695
3696       /* If this insn is a register-register copy and the next insn has
3697          a use of our destination, change it to use our source.  That way,
3698          it will become a candidate for our delay slot the next time
3699          through this loop.  This case occurs commonly in loops that
3700          scan a list.
3701
3702          We could check for more complex cases than those tested below,
3703          but it doesn't seem worth it.  It might also be a good idea to try
3704          to swap the two insns.  That might do better.
3705
3706          We can't do this if the next insn modifies our destination, because
3707          that would make the replacement into the insn invalid.  We also can't
3708          do this if it modifies our source, because it might be an earlyclobber
3709          operand.  This latter test also prevents updating the contents of
3710          a PRE_INC.  */
3711
3712       if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
3713           && GET_CODE (SET_SRC (pat)) == REG
3714           && GET_CODE (SET_DEST (pat)) == REG)
3715         {
3716           rtx next = next_nonnote_insn (trial);
3717
3718           if (next && GET_CODE (next) == INSN
3719               && GET_CODE (PATTERN (next)) != USE
3720               && ! reg_set_p (SET_DEST (pat), next)
3721               && ! reg_set_p (SET_SRC (pat), next)
3722               && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
3723             validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
3724         }
3725     }
3726
3727   /* If we stopped on a branch insn that has delay slots, see if we can
3728      steal some of the insns in those slots.  */
3729   if (trial && GET_CODE (trial) == INSN
3730       && GET_CODE (PATTERN (trial)) == SEQUENCE
3731       && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
3732     {
3733       /* If this is the `true' thread, we will want to follow the jump,
3734          so we can only do this if we have taken everything up to here.  */
3735       if (thread_if_true && trial == new_thread
3736           && ! insn_references_resource_p (XVECEXP (PATTERN (trial), 0, 0),
3737                                            &opposite_needed, 0))
3738         delay_list
3739           = steal_delay_list_from_target (insn, condition, PATTERN (trial),
3740                                           delay_list, &set, &needed,
3741                                           &opposite_needed, slots_to_fill,
3742                                           pslots_filled, &must_annul,
3743                                           &new_thread);
3744       else if (! thread_if_true)
3745         delay_list
3746           = steal_delay_list_from_fallthrough (insn, condition,
3747                                                PATTERN (trial),
3748                                                delay_list, &set, &needed,
3749                                                &opposite_needed, slots_to_fill,
3750                                                pslots_filled, &must_annul);
3751     }
3752
3753   /* If we haven't found anything for this delay slot and it is very
3754      likely that the branch will be taken, see if the insn at our target
3755      increments or decrements a register with an increment that does not
3756      depend on the destination register.  If so, try to place the opposite
3757      arithmetic insn after the jump insn and put the arithmetic insn in the
3758      delay slot.  If we can't do this, return.  */
3759   if (delay_list == 0 && likely && new_thread
3760       && GET_CODE (new_thread) == INSN
3761       && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
3762       && asm_noperands (PATTERN (new_thread)) < 0)
3763     {
3764       rtx pat = PATTERN (new_thread);
3765       rtx dest;
3766       rtx src;
3767
3768       trial = new_thread;
3769       pat = PATTERN (trial);
3770
3771       if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
3772           || ! eligible_for_delay (insn, 0, trial, flags))
3773         return 0;
3774
3775       dest = SET_DEST (pat), src = SET_SRC (pat);
3776       if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
3777           && rtx_equal_p (XEXP (src, 0), dest)
3778           && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
3779         {
3780           rtx other = XEXP (src, 1);
3781           rtx new_arith;
3782           rtx ninsn;
3783
3784           /* If this is a constant adjustment, use the same code with
3785              the negated constant.  Otherwise, reverse the sense of the
3786              arithmetic.  */
3787           if (GET_CODE (other) == CONST_INT)
3788             new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
3789                                         negate_rtx (GET_MODE (src), other));
3790           else
3791             new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
3792                                         GET_MODE (src), dest, other);
3793
3794           ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith),
3795                                    insn);
3796
3797           if (recog_memoized (ninsn) < 0
3798               || (insn_extract (ninsn),
3799                   ! constrain_operands (INSN_CODE (ninsn), 1)))
3800             {
3801               delete_insn (ninsn);
3802               return 0;
3803             }
3804
3805           if (own_thread)
3806             {
3807               update_block (trial, thread);
3808               if (trial == thread)
3809                 {
3810                   thread = next_active_insn (thread);
3811                   if (new_thread == trial)
3812                     new_thread = thread;
3813                 }
3814               delete_insn (trial);
3815             }
3816           else
3817             new_thread = next_active_insn (trial);
3818
3819           ninsn = own_thread ? trial : copy_rtx (trial);
3820           if (thread_if_true)
3821             INSN_FROM_TARGET_P (ninsn) = 1;
3822
3823           delay_list = add_to_delay_list (ninsn, NULL_RTX);
3824           (*pslots_filled)++;
3825         }
3826     }
3827
3828   if (delay_list && must_annul)
3829     INSN_ANNULLED_BRANCH_P (insn) = 1;
3830
3831   /* If we are to branch into the middle of this thread, find an appropriate
3832      label or make a new one if none, and redirect INSN to it.  If we hit the
3833      end of the function, use the end-of-function label.  */
3834   if (new_thread != thread)
3835     {
3836       rtx label;
3837
3838       if (! thread_if_true)
3839         abort ();
3840
3841       if (new_thread && GET_CODE (new_thread) == JUMP_INSN
3842           && (simplejump_p (new_thread)
3843               || GET_CODE (PATTERN (new_thread)) == RETURN)
3844           && redirect_with_delay_list_safe_p (insn,
3845                                               JUMP_LABEL (new_thread),
3846                                               delay_list))
3847         new_thread = follow_jumps (JUMP_LABEL (new_thread));
3848
3849       if (new_thread == 0)
3850         label = find_end_label ();
3851       else if (GET_CODE (new_thread) == CODE_LABEL)
3852         label = new_thread;
3853       else
3854         label = get_label_before (new_thread);
3855
3856       reorg_redirect_jump (insn, label);
3857     }
3858
3859   return delay_list;
3860 }
3861 \f
3862 /* Make another attempt to find insns to place in delay slots.
3863
3864    We previously looked for insns located in front of the delay insn
3865    and, for non-jump delay insns, located behind the delay insn.
3866
3867    Here only try to schedule jump insns and try to move insns from either
3868    the target or the following insns into the delay slot.  If annulling is
3869    supported, we will be likely to do this.  Otherwise, we can do this only
3870    if safe.  */
3871
3872 static void
3873 fill_eager_delay_slots ()
3874 {
3875   register rtx insn;
3876   register int i;
3877   int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3878
3879   for (i = 0; i < num_unfilled_slots; i++)
3880     {
3881       rtx condition;
3882       rtx target_label, insn_at_target, fallthrough_insn;
3883       rtx delay_list = 0;
3884       int own_target;
3885       int own_fallthrough;
3886       int prediction, slots_to_fill, slots_filled;
3887
3888       insn = unfilled_slots_base[i];
3889       if (insn == 0
3890           || INSN_DELETED_P (insn)
3891           || GET_CODE (insn) != JUMP_INSN
3892           || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
3893         continue;
3894
3895       slots_to_fill = num_delay_slots (insn);
3896       if (slots_to_fill == 0)
3897         abort ();
3898
3899       slots_filled = 0;
3900       target_label = JUMP_LABEL (insn);
3901       condition = get_branch_condition (insn, target_label);
3902
3903       if (condition == 0)
3904         continue;
3905
3906       /* Get the next active fallthrough and target insns and see if we own
3907          them.  Then see whether the branch is likely true.  We don't need
3908          to do a lot of this for unconditional branches.  */
3909
3910       insn_at_target = next_active_insn (target_label);
3911       own_target = own_thread_p (target_label, target_label, 0);
3912
3913       if (condition == const_true_rtx)
3914         {
3915           own_fallthrough = 0;
3916           fallthrough_insn = 0;
3917           prediction = 2;
3918         }
3919       else
3920         {
3921           fallthrough_insn = next_active_insn (insn);
3922           own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
3923           prediction = mostly_true_jump (insn, condition);
3924         }
3925
3926       /* If this insn is expected to branch, first try to get insns from our
3927          target, then our fallthrough insns.  If it is not, expected to branch,
3928          try the other order.  */
3929
3930       if (prediction > 0)
3931         {
3932           delay_list
3933             = fill_slots_from_thread (insn, condition, insn_at_target,
3934                                       fallthrough_insn, prediction == 2, 1,
3935                                       own_target,
3936                                       slots_to_fill, &slots_filled, delay_list);
3937
3938           if (delay_list == 0 && own_fallthrough)
3939             {
3940               /* Even though we didn't find anything for delay slots,
3941                  we might have found a redundant insn which we deleted
3942                  from the thread that was filled.  So we have to recompute
3943                  the next insn at the target.  */
3944               target_label = JUMP_LABEL (insn);
3945               insn_at_target = next_active_insn (target_label);
3946
3947               delay_list
3948                 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3949                                           insn_at_target, 0, 0,
3950                                           own_fallthrough,
3951                                           slots_to_fill, &slots_filled,
3952                                           delay_list);
3953             }
3954         }
3955       else
3956         {
3957           if (own_fallthrough)
3958             delay_list
3959               = fill_slots_from_thread (insn, condition, fallthrough_insn,
3960                                         insn_at_target, 0, 0,
3961                                         own_fallthrough,
3962                                         slots_to_fill, &slots_filled,
3963                                         delay_list);
3964
3965           if (delay_list == 0)
3966             delay_list
3967               = fill_slots_from_thread (insn, condition, insn_at_target,
3968                                         next_active_insn (insn), 0, 1,
3969                                         own_target,
3970                                         slots_to_fill, &slots_filled,
3971                                         delay_list);
3972         }
3973
3974       if (delay_list)
3975         unfilled_slots_base[i]
3976           = emit_delay_sequence (insn, delay_list, slots_filled);
3977
3978       if (slots_to_fill == slots_filled)
3979         unfilled_slots_base[i] = 0;
3980
3981       note_delay_statistics (slots_filled, 1);
3982     }
3983 }
3984 \f
3985 /* Once we have tried two ways to fill a delay slot, make a pass over the
3986    code to try to improve the results and to do such things as more jump
3987    threading.  */
3988
3989 static void
3990 relax_delay_slots (first)
3991      rtx first;
3992 {
3993   register rtx insn, next, pat;
3994   register rtx trial, delay_insn, target_label;
3995
3996   /* Look at every JUMP_INSN and see if we can improve it.  */
3997   for (insn = first; insn; insn = next)
3998     {
3999       rtx other;
4000
4001       next = next_active_insn (insn);
4002
4003       /* If this is a jump insn, see if it now jumps to a jump, jumps to
4004          the next insn, or jumps to a label that is not the last of a
4005          group of consecutive labels.  */
4006       if (GET_CODE (insn) == JUMP_INSN
4007           && (condjump_p (insn) || condjump_in_parallel_p (insn))
4008           && (target_label = JUMP_LABEL (insn)) != 0)
4009         {
4010           target_label = follow_jumps (target_label);
4011           target_label = prev_label (next_active_insn (target_label));
4012
4013           if (target_label == 0)
4014             target_label = find_end_label ();
4015
4016           if (next_active_insn (target_label) == next
4017               && ! condjump_in_parallel_p (insn))
4018             {
4019               delete_jump (insn);
4020               continue;
4021             }
4022
4023           if (target_label != JUMP_LABEL (insn))
4024             reorg_redirect_jump (insn, target_label);
4025
4026           /* See if this jump branches around a unconditional jump.
4027              If so, invert this jump and point it to the target of the
4028              second jump.  */
4029           if (next && GET_CODE (next) == JUMP_INSN
4030               && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
4031               && next_active_insn (target_label) == next_active_insn (next)
4032               && no_labels_between_p (insn, next))
4033             {
4034               rtx label = JUMP_LABEL (next);
4035
4036               /* Be careful how we do this to avoid deleting code or
4037                  labels that are momentarily dead.  See similar optimization
4038                  in jump.c.
4039
4040                  We also need to ensure we properly handle the case when
4041                  invert_jump fails.  */
4042
4043               ++LABEL_NUSES (target_label);
4044               if (label)
4045                 ++LABEL_NUSES (label);
4046
4047               if (invert_jump (insn, label))
4048                 {
4049                   delete_insn (next);
4050                   next = insn;
4051                 }
4052
4053               if (label)
4054                 --LABEL_NUSES (label);
4055
4056               if (--LABEL_NUSES (target_label) == 0)
4057                 delete_insn (target_label);
4058
4059               continue;
4060             }
4061         }
4062
4063       /* If this is an unconditional jump and the previous insn is a
4064          conditional jump, try reversing the condition of the previous
4065          insn and swapping our targets.  The next pass might be able to
4066          fill the slots.
4067
4068          Don't do this if we expect the conditional branch to be true, because
4069          we would then be making the more common case longer.  */
4070
4071       if (GET_CODE (insn) == JUMP_INSN
4072           && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
4073           && (other = prev_active_insn (insn)) != 0
4074           && (condjump_p (other) || condjump_in_parallel_p (other))
4075           && no_labels_between_p (other, insn)
4076           && 0 < mostly_true_jump (other,
4077                                    get_branch_condition (other,
4078                                                          JUMP_LABEL (other))))
4079         {
4080           rtx other_target = JUMP_LABEL (other);
4081           target_label = JUMP_LABEL (insn);
4082
4083           /* Increment the count of OTHER_TARGET, so it doesn't get deleted
4084              as we move the label.  */
4085           if (other_target)
4086             ++LABEL_NUSES (other_target);
4087
4088           if (invert_jump (other, target_label))
4089             reorg_redirect_jump (insn, other_target);
4090
4091           if (other_target)
4092             --LABEL_NUSES (other_target);
4093         }
4094
4095       /* Now look only at cases where we have filled a delay slot.  */
4096       if (GET_CODE (insn) != INSN
4097           || GET_CODE (PATTERN (insn)) != SEQUENCE)
4098         continue;
4099
4100       pat = PATTERN (insn);
4101       delay_insn = XVECEXP (pat, 0, 0);
4102
4103       /* See if the first insn in the delay slot is redundant with some
4104          previous insn.  Remove it from the delay slot if so; then set up
4105          to reprocess this insn.  */
4106       if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
4107         {
4108           delete_from_delay_slot (XVECEXP (pat, 0, 1));
4109           next = prev_active_insn (next);
4110           continue;
4111         }
4112
4113       /* Now look only at the cases where we have a filled JUMP_INSN.  */
4114       if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4115           || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
4116                 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
4117         continue;
4118
4119       target_label = JUMP_LABEL (delay_insn);
4120
4121       if (target_label)
4122         {
4123           /* If this jump goes to another unconditional jump, thread it, but
4124              don't convert a jump into a RETURN here.  */
4125           trial = follow_jumps (target_label);
4126           /* We use next_real_insn instead of next_active_insn, so that
4127              the special USE insns emitted by reorg won't be ignored.
4128              If they are ignored, then they will get deleted if target_label
4129              is now unreachable, and that would cause mark_target_live_regs
4130              to fail.  */
4131           trial = prev_label (next_real_insn (trial));
4132           if (trial == 0 && target_label != 0)
4133             trial = find_end_label ();
4134
4135           if (trial != target_label
4136               && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
4137             {
4138               reorg_redirect_jump (delay_insn, trial);
4139               target_label = trial;
4140             }
4141
4142           /* If the first insn at TARGET_LABEL is redundant with a previous
4143              insn, redirect the jump to the following insn process again.  */
4144           trial = next_active_insn (target_label);
4145           if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
4146               && redundant_insn (trial, insn, 0))
4147             {
4148               rtx tmp;
4149
4150               /* Figure out where to emit the special USE insn so we don't
4151                  later incorrectly compute register live/death info.  */
4152               tmp = next_active_insn (trial);
4153               if (tmp == 0)
4154                 tmp = find_end_label ();
4155
4156               /* Insert the special USE insn and update dataflow info.  */
4157               update_block (trial, tmp);
4158
4159               /* Now emit a label before the special USE insn, and
4160                  redirect our jump to the new label.  */
4161               target_label = get_label_before (PREV_INSN (tmp));
4162               reorg_redirect_jump (delay_insn, target_label);
4163               next = insn;
4164               continue;
4165             }
4166
4167           /* Similarly, if it is an unconditional jump with one insn in its
4168              delay list and that insn is redundant, thread the jump.  */
4169           if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
4170               && XVECLEN (PATTERN (trial), 0) == 2
4171               && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
4172               && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
4173                   || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
4174               && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
4175             {
4176               target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
4177               if (target_label == 0)
4178                 target_label = find_end_label ();
4179
4180               if (redirect_with_delay_slots_safe_p (delay_insn, target_label,
4181                                                     insn))
4182                 {
4183                   reorg_redirect_jump (delay_insn, target_label);
4184                   next = insn;
4185                   continue;
4186                 }
4187             }
4188         }
4189
4190       if (! INSN_ANNULLED_BRANCH_P (delay_insn)
4191           && prev_active_insn (target_label) == insn
4192           && ! condjump_in_parallel_p (delay_insn)
4193 #ifdef HAVE_cc0
4194           /* If the last insn in the delay slot sets CC0 for some insn,
4195              various code assumes that it is in a delay slot.  We could
4196              put it back where it belonged and delete the register notes,
4197              but it doesn't seem worthwhile in this uncommon case.  */
4198           && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
4199                               REG_CC_USER, NULL_RTX)
4200 #endif
4201           )
4202         {
4203           int i;
4204
4205           /* All this insn does is execute its delay list and jump to the
4206              following insn.  So delete the jump and just execute the delay
4207              list insns.
4208
4209              We do this by deleting the INSN containing the SEQUENCE, then
4210              re-emitting the insns separately, and then deleting the jump.
4211              This allows the count of the jump target to be properly
4212              decremented.  */
4213
4214           /* Clear the from target bit, since these insns are no longer
4215              in delay slots.  */
4216           for (i = 0; i < XVECLEN (pat, 0); i++)
4217             INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
4218
4219           trial = PREV_INSN (insn);
4220           delete_insn (insn);
4221           emit_insn_after (pat, trial);
4222           delete_scheduled_jump (delay_insn);
4223           continue;
4224         }
4225
4226       /* See if this is an unconditional jump around a single insn which is
4227          identical to the one in its delay slot.  In this case, we can just
4228          delete the branch and the insn in its delay slot.  */
4229       if (next && GET_CODE (next) == INSN
4230           && prev_label (next_active_insn (next)) == target_label
4231           && simplejump_p (insn)
4232           && XVECLEN (pat, 0) == 2
4233           && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
4234         {
4235           delete_insn (insn);
4236           continue;
4237         }
4238
4239       /* See if this jump (with its delay slots) branches around another
4240          jump (without delay slots).  If so, invert this jump and point
4241          it to the target of the second jump.  We cannot do this for
4242          annulled jumps, though.  Again, don't convert a jump to a RETURN
4243          here.  */
4244       if (! INSN_ANNULLED_BRANCH_P (delay_insn)
4245           && next && GET_CODE (next) == JUMP_INSN
4246           && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
4247           && next_active_insn (target_label) == next_active_insn (next)
4248           && no_labels_between_p (insn, next))
4249         {
4250           rtx label = JUMP_LABEL (next);
4251           rtx old_label = JUMP_LABEL (delay_insn);
4252
4253           if (label == 0)
4254             label = find_end_label ();
4255
4256           if (redirect_with_delay_slots_safe_p (delay_insn, label, insn))
4257             {
4258               /* Be careful how we do this to avoid deleting code or labels
4259                  that are momentarily dead.  See similar optimization in
4260                  jump.c  */
4261               if (old_label)
4262                 ++LABEL_NUSES (old_label);
4263
4264               if (invert_jump (delay_insn, label))
4265                 {
4266                   int i;
4267
4268                   /* Must update the INSN_FROM_TARGET_P bits now that
4269                      the branch is reversed, so that mark_target_live_regs
4270                      will handle the delay slot insn correctly.  */
4271                   for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
4272                     {
4273                       rtx slot = XVECEXP (PATTERN (insn), 0, i);
4274                       INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
4275                     }
4276
4277                   delete_insn (next);
4278                   next = insn;
4279                 }
4280
4281               if (old_label && --LABEL_NUSES (old_label) == 0)
4282                 delete_insn (old_label);
4283               continue;
4284             }
4285         }
4286
4287       /* If we own the thread opposite the way this insn branches, see if we
4288          can merge its delay slots with following insns.  */
4289       if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4290           && own_thread_p (NEXT_INSN (insn), 0, 1))
4291         try_merge_delay_insns (insn, next);
4292       else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4293                && own_thread_p (target_label, target_label, 0))
4294         try_merge_delay_insns (insn, next_active_insn (target_label));
4295
4296       /* If we get here, we haven't deleted INSN.  But we may have deleted
4297          NEXT, so recompute it.  */
4298       next = next_active_insn (insn);
4299     }
4300 }
4301 \f
4302 #ifdef HAVE_return
4303
4304 /* Look for filled jumps to the end of function label.  We can try to convert
4305    them into RETURN insns if the insns in the delay slot are valid for the
4306    RETURN as well.  */
4307
4308 static void
4309 make_return_insns (first)
4310      rtx first;
4311 {
4312   rtx insn, jump_insn, pat;
4313   rtx real_return_label = end_of_function_label;
4314   int slots, i;
4315
4316   /* See if there is a RETURN insn in the function other than the one we
4317      made for END_OF_FUNCTION_LABEL.  If so, set up anything we can't change
4318      into a RETURN to jump to it.  */
4319   for (insn = first; insn; insn = NEXT_INSN (insn))
4320     if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
4321       {
4322         real_return_label = get_label_before (insn);
4323         break;
4324       }
4325
4326   /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
4327      was equal to END_OF_FUNCTION_LABEL.  */
4328   LABEL_NUSES (real_return_label)++;
4329
4330   /* Clear the list of insns to fill so we can use it.  */
4331   obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4332
4333   for (insn = first; insn; insn = NEXT_INSN (insn))
4334     {
4335       int flags;
4336
4337       /* Only look at filled JUMP_INSNs that go to the end of function
4338          label.  */
4339       if (GET_CODE (insn) != INSN
4340           || GET_CODE (PATTERN (insn)) != SEQUENCE
4341           || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4342           || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
4343         continue;
4344
4345       pat = PATTERN (insn);
4346       jump_insn = XVECEXP (pat, 0, 0);
4347
4348       /* If we can't make the jump into a RETURN, try to redirect it to the best
4349          RETURN and go on to the next insn.  */
4350       if (! reorg_redirect_jump (jump_insn, NULL_RTX))
4351         {
4352           /* Make sure redirecting the jump will not invalidate the delay
4353              slot insns.  */
4354           if (redirect_with_delay_slots_safe_p (jump_insn,
4355                                                 real_return_label,
4356                                                 insn))
4357             reorg_redirect_jump (jump_insn, real_return_label);
4358           continue;
4359         }
4360
4361       /* See if this RETURN can accept the insns current in its delay slot.
4362          It can if it has more or an equal number of slots and the contents
4363          of each is valid.  */
4364
4365       flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
4366       slots = num_delay_slots (jump_insn);
4367       if (slots >= XVECLEN (pat, 0) - 1)
4368         {
4369           for (i = 1; i < XVECLEN (pat, 0); i++)
4370             if (! (
4371 #ifdef ANNUL_IFFALSE_SLOTS
4372                    (INSN_ANNULLED_BRANCH_P (jump_insn)
4373                     && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4374                    ? eligible_for_annul_false (jump_insn, i - 1,
4375                                                XVECEXP (pat, 0, i), flags) :
4376 #endif
4377 #ifdef ANNUL_IFTRUE_SLOTS
4378                    (INSN_ANNULLED_BRANCH_P (jump_insn)
4379                     && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4380                    ? eligible_for_annul_true (jump_insn, i - 1,
4381                                               XVECEXP (pat, 0, i), flags) :
4382 #endif
4383                    eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i), flags)))
4384               break;
4385         }
4386       else
4387         i = 0;
4388
4389       if (i == XVECLEN (pat, 0))
4390         continue;
4391
4392       /* We have to do something with this insn.  If it is an unconditional
4393          RETURN, delete the SEQUENCE and output the individual insns,
4394          followed by the RETURN.  Then set things up so we try to find
4395          insns for its delay slots, if it needs some.  */
4396       if (GET_CODE (PATTERN (jump_insn)) == RETURN)
4397         {
4398           rtx prev = PREV_INSN (insn);
4399
4400           delete_insn (insn);
4401           for (i = 1; i < XVECLEN (pat, 0); i++)
4402             prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
4403
4404           insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
4405           emit_barrier_after (insn);
4406
4407           if (slots)
4408             obstack_ptr_grow (&unfilled_slots_obstack, insn);
4409         }
4410       else
4411         /* It is probably more efficient to keep this with its current
4412            delay slot as a branch to a RETURN.  */
4413         reorg_redirect_jump (jump_insn, real_return_label);
4414     }
4415
4416   /* Now delete REAL_RETURN_LABEL if we never used it.  Then try to fill any
4417      new delay slots we have created.  */
4418   if (--LABEL_NUSES (real_return_label) == 0)
4419     delete_insn (real_return_label);
4420
4421   fill_simple_delay_slots (1);
4422   fill_simple_delay_slots (0);
4423 }
4424 #endif
4425 \f
4426 /* Try to find insns to place in delay slots.  */
4427
4428 void
4429 dbr_schedule (first, file)
4430      rtx first;
4431      FILE *file;
4432 {
4433   rtx insn, next, epilogue_insn = 0;
4434   int i;
4435 #if 0
4436   int old_flag_no_peephole = flag_no_peephole;
4437
4438   /* Execute `final' once in prescan mode to delete any insns that won't be
4439      used.  Don't let final try to do any peephole optimization--it will
4440      ruin dataflow information for this pass.  */
4441
4442   flag_no_peephole = 1;
4443   final (first, 0, NO_DEBUG, 1, 1);
4444   flag_no_peephole = old_flag_no_peephole;
4445 #endif
4446
4447   /* If the current function has no insns other than the prologue and
4448      epilogue, then do not try to fill any delay slots.  */
4449   if (n_basic_blocks == 0)
4450     return;
4451
4452   /* Find the highest INSN_UID and allocate and initialize our map from
4453      INSN_UID's to position in code.  */
4454   for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
4455     {
4456       if (INSN_UID (insn) > max_uid)
4457         max_uid = INSN_UID (insn);
4458       if (GET_CODE (insn) == NOTE
4459           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
4460         epilogue_insn = insn;
4461     }
4462
4463   uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
4464   for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
4465     uid_to_ruid[INSN_UID (insn)] = i;
4466
4467   /* Initialize the list of insns that need filling.  */
4468   if (unfilled_firstobj == 0)
4469     {
4470       gcc_obstack_init (&unfilled_slots_obstack);
4471       unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4472     }
4473
4474   for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
4475     {
4476       rtx target;
4477
4478       INSN_ANNULLED_BRANCH_P (insn) = 0;
4479       INSN_FROM_TARGET_P (insn) = 0;
4480
4481       /* Skip vector tables.  We can't get attributes for them.  */
4482       if (GET_CODE (insn) == JUMP_INSN
4483           && (GET_CODE (PATTERN (insn)) == ADDR_VEC
4484               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
4485         continue;
4486
4487       if (num_delay_slots (insn) > 0)
4488         obstack_ptr_grow (&unfilled_slots_obstack, insn);
4489
4490       /* Ensure all jumps go to the last of a set of consecutive labels.  */
4491       if (GET_CODE (insn) == JUMP_INSN
4492           && (condjump_p (insn) || condjump_in_parallel_p (insn))
4493           && JUMP_LABEL (insn) != 0
4494           && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
4495               != JUMP_LABEL (insn)))
4496         redirect_jump (insn, target);
4497     }
4498
4499   /* Indicate what resources are required to be valid at the end of the current
4500      function.  The condition code never is and memory always is.  If the
4501      frame pointer is needed, it is and so is the stack pointer unless
4502      EXIT_IGNORE_STACK is non-zero.  If the frame pointer is not needed, the
4503      stack pointer is.  Registers used to return the function value are
4504      needed.  Registers holding global variables are needed.  */
4505
4506   end_of_function_needs.cc = 0;
4507   end_of_function_needs.memory = 1;
4508   end_of_function_needs.unch_memory = 0;
4509   CLEAR_HARD_REG_SET (end_of_function_needs.regs);
4510
4511   if (frame_pointer_needed)
4512     {
4513       SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
4514 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4515       SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM);
4516 #endif
4517 #ifdef EXIT_IGNORE_STACK
4518       if (! EXIT_IGNORE_STACK)
4519 #endif
4520         SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4521     }
4522   else
4523     SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4524
4525   if (current_function_return_rtx != 0)
4526     mark_referenced_resources (current_function_return_rtx,
4527                                &end_of_function_needs, 1);
4528
4529   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4530     if (global_regs[i]
4531 #ifdef EPILOGUE_USES
4532         || EPILOGUE_USES (i)
4533 #endif
4534         )
4535       SET_HARD_REG_BIT (end_of_function_needs.regs, i);
4536
4537   /* The registers required to be live at the end of the function are
4538      represented in the flow information as being dead just prior to
4539      reaching the end of the function.  For example, the return of a value
4540      might be represented by a USE of the return register immediately
4541      followed by an unconditional jump to the return label where the
4542      return label is the end of the RTL chain.  The end of the RTL chain
4543      is then taken to mean that the return register is live.
4544
4545      This sequence is no longer maintained when epilogue instructions are
4546      added to the RTL chain.  To reconstruct the original meaning, the
4547      start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
4548      point where these registers become live (start_of_epilogue_needs).
4549      If epilogue instructions are present, the registers set by those
4550      instructions won't have been processed by flow.  Thus, those
4551      registers are additionally required at the end of the RTL chain
4552      (end_of_function_needs).  */
4553
4554   start_of_epilogue_needs = end_of_function_needs;
4555
4556   while ((epilogue_insn = next_nonnote_insn (epilogue_insn)))
4557     mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1);
4558
4559   /* Show we haven't computed an end-of-function label yet.  */
4560   end_of_function_label = 0;
4561
4562   /* Allocate and initialize the tables used by mark_target_live_regs.  */
4563   target_hash_table
4564     = (struct target_info **) alloca ((TARGET_HASH_PRIME
4565                                        * sizeof (struct target_info *)));
4566   bzero ((char *) target_hash_table,
4567          TARGET_HASH_PRIME * sizeof (struct target_info *));
4568
4569   bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
4570   bzero ((char *) bb_ticks, n_basic_blocks * sizeof (int));
4571
4572   /* Initialize the statistics for this function.  */
4573   bzero ((char *) num_insns_needing_delays, sizeof num_insns_needing_delays);
4574   bzero ((char *) num_filled_delays, sizeof num_filled_delays);
4575
4576   /* Now do the delay slot filling.  Try everything twice in case earlier
4577      changes make more slots fillable.  */
4578
4579   for (reorg_pass_number = 0;
4580        reorg_pass_number < MAX_REORG_PASSES;
4581        reorg_pass_number++)
4582     {
4583       fill_simple_delay_slots (1);
4584       fill_simple_delay_slots (0);
4585       fill_eager_delay_slots ();
4586       relax_delay_slots (first);
4587     }
4588
4589   /* Delete any USE insns made by update_block; subsequent passes don't need
4590      them or know how to deal with them.  */
4591   for (insn = first; insn; insn = next)
4592     {
4593       next = NEXT_INSN (insn);
4594
4595       if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
4596           && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
4597         next = delete_insn (insn);
4598     }
4599
4600   /* If we made an end of function label, indicate that it is now
4601      safe to delete it by undoing our prior adjustment to LABEL_NUSES.
4602      If it is now unused, delete it.  */
4603   if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
4604     delete_insn (end_of_function_label);
4605
4606 #ifdef HAVE_return
4607   if (HAVE_return && end_of_function_label != 0)
4608     make_return_insns (first);
4609 #endif
4610
4611   obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4612
4613   /* It is not clear why the line below is needed, but it does seem to be.  */
4614   unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4615
4616   /* Reposition the prologue and epilogue notes in case we moved the
4617      prologue/epilogue insns.  */
4618   reposition_prologue_and_epilogue_notes (first);
4619
4620   if (file)
4621     {
4622       register int i, j, need_comma;
4623
4624       for (reorg_pass_number = 0;
4625            reorg_pass_number < MAX_REORG_PASSES;
4626            reorg_pass_number++)
4627         {
4628           fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
4629           for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
4630             {
4631               need_comma = 0;
4632               fprintf (file, ";; Reorg function #%d\n", i);
4633
4634               fprintf (file, ";; %d insns needing delay slots\n;; ",
4635                        num_insns_needing_delays[i][reorg_pass_number]);
4636
4637               for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
4638                 if (num_filled_delays[i][j][reorg_pass_number])
4639                   {
4640                     if (need_comma)
4641                       fprintf (file, ", ");
4642                     need_comma = 1;
4643                     fprintf (file, "%d got %d delays",
4644                              num_filled_delays[i][j][reorg_pass_number], j);
4645                   }
4646               fprintf (file, "\n");
4647             }
4648         }
4649     }
4650
4651   /* For all JUMP insns, fill in branch prediction notes, so that during
4652      assembler output a target can set branch prediction bits in the code.
4653      We have to do this now, as up until this point the destinations of
4654      JUMPS can be moved around and changed, but past right here that cannot
4655      happen.  */
4656   for (insn = first; insn; insn = NEXT_INSN (insn))
4657     {
4658       int pred_flags;
4659
4660       if (GET_CODE (insn) != JUMP_INSN)
4661         continue;
4662
4663       pred_flags = get_jump_flags (insn, JUMP_LABEL (insn));
4664       REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED,
4665                                             GEN_INT (pred_flags),
4666                                             REG_NOTES (insn));
4667     }
4668 }
4669 #endif /* DELAY_SLOTS */