gcc/reorg.c

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