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