gcc/reorg.c

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