gcc/reorg.c

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