gcc/reorg.c

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