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