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