gcc/reorg.c

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