gcc/reorg.c

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