gcc/reorg.c

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