gcc/reorg.c

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