gcc/reorg.c

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