gcc/reorg.c

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