gcc/reorg.c

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