gcc/reorg.c

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