gcc/reorg.c

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