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