gcc/reorg.c

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