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