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