gcc/reorg.c

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