gcc/reorg.c

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