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 #ifndef ANNUL_IFTRUE_SLOTS
 147 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
 148 #endif
 149 #ifndef ANNUL_IFFALSE_SLOTS
 150 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
 151 #endif
 152
 153 /* Insns which have delay slots that have not yet been filled.  */
 154
 155 static struct obstack unfilled_slots_obstack;
 156 static rtx *unfilled_firstobj;
 157
 158 /* Define macros to refer to the first and last slot containing unfilled
 159    insns.  These are used because the list may move and its address
 160    should be recomputed at each use.  */
 161
 162 #define unfilled_slots_base     \
 163   ((rtx *) obstack_base (&unfilled_slots_obstack))
 164
 165 #define unfilled_slots_next     \
 166   ((rtx *) obstack_next_free (&unfilled_slots_obstack))
 167
 168 /* Points to the label before the end of the function.  */
 169 static rtx end_of_function_label;
 170
 171 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
 172    not always monotonically increase.  */
 173 static int *uid_to_ruid;
 174
 175 /* Highest valid index in `uid_to_ruid'.  */
 176 static int max_uid;
 177
 178 static int stop_search_p                PARAMS ((rtx, int));
 179 static int resource_conflicts_p         PARAMS ((struct resources *,
 180                                                struct resources *));
 181 static int insn_references_resource_p   PARAMS ((rtx, struct resources *, int));
 182 static int insn_sets_resource_p         PARAMS ((rtx, struct resources *, int));
 183 static rtx find_end_label               PARAMS ((void));
 184 static rtx emit_delay_sequence          PARAMS ((rtx, rtx, int));
 185 static rtx add_to_delay_list            PARAMS ((rtx, rtx));
 186 static rtx delete_from_delay_slot       PARAMS ((rtx));
 187 static void delete_scheduled_jump       PARAMS ((rtx));
 188 static void note_delay_statistics       PARAMS ((int, int));
 189 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
 190 static rtx optimize_skip                PARAMS ((rtx));
 191 #endif
 192 static int get_jump_flags               PARAMS ((rtx, rtx));
 193 static int rare_destination             PARAMS ((rtx));
 194 static int mostly_true_jump             PARAMS ((rtx, rtx));
 195 static rtx get_branch_condition         PARAMS ((rtx, rtx));
 196 static int condition_dominates_p        PARAMS ((rtx, rtx));
 197 static int redirect_with_delay_slots_safe_p PARAMS ((rtx, rtx, rtx));
 198 static int redirect_with_delay_list_safe_p PARAMS ((rtx, rtx, rtx));
 199 static int check_annul_list_true_false  PARAMS ((int, rtx));
 200 static rtx steal_delay_list_from_target PARAMS ((rtx, rtx, rtx, rtx,
 201                                                struct resources *,
 202                                                struct resources *,
 203                                                struct resources *,
 204                                                int, int *, int *, rtx *));
 205 static rtx steal_delay_list_from_fallthrough PARAMS ((rtx, rtx, rtx, rtx,
 206                                                     struct resources *,
 207                                                     struct resources *,
 208                                                     struct resources *,
 209                                                     int, int *, int *));
 210 static void try_merge_delay_insns       PARAMS ((rtx, rtx));
 211 static rtx redundant_insn               PARAMS ((rtx, rtx, rtx));
 212 static int own_thread_p                 PARAMS ((rtx, rtx, int));
 213 static void update_block                PARAMS ((rtx, rtx));
 214 static int reorg_redirect_jump          PARAMS ((rtx, rtx));
 215 static void update_reg_dead_notes       PARAMS ((rtx, rtx));
 216 static void fix_reg_dead_note           PARAMS ((rtx, rtx));
 217 static void update_reg_unused_notes     PARAMS ((rtx, rtx));
 218 static void fill_simple_delay_slots     PARAMS ((int));
 219 static rtx fill_slots_from_thread       PARAMS ((rtx, rtx, rtx, rtx, int, int,
 220                                                int, int, int *, rtx));
 221 static void fill_eager_delay_slots      PARAMS ((void));
 222 static void relax_delay_slots           PARAMS ((rtx));
 223 #ifdef HAVE_return
 224 static void make_return_insns           PARAMS ((rtx));
 225 #endif
 226 \f
 227 /* Return TRUE if this insn should stop the search for insn to fill delay
 228    slots.  LABELS_P indicates that labels should terminate the search.
 229    In all cases, jumps terminate the search.  */
 230
 231 static int
 232 stop_search_p (insn, labels_p)
 233      rtx insn;
 234      int labels_p;
 235 {
 236   if (insn == 0)
 237     return 1;
 238
 239   switch (GET_CODE (insn))
 240     {
 241     case NOTE:
 242     case CALL_INSN:
 243       return 0;
 244
 245     case CODE_LABEL:
 246       return labels_p;
 247
 248     case JUMP_INSN:
 249     case BARRIER:
 250       return 1;
 251
 252     case INSN:
 253       /* OK unless it contains a delay slot or is an `asm' insn of some type.
 254          We don't know anything about these.  */
 255       return (GET_CODE (PATTERN (insn)) == SEQUENCE
 256               || GET_CODE (PATTERN (insn)) == ASM_INPUT
 257               || asm_noperands (PATTERN (insn)) >= 0);
 258
 259     default:
 260       abort ();
 261     }
 262 }
 263 \f
 264 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
 265    resource set contains a volatile memory reference.  Otherwise, return FALSE.  */
 266
 267 static int
 268 resource_conflicts_p (res1, res2)
 269      struct resources *res1, *res2;
 270 {
 271   if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
 272       || (res1->unch_memory && res2->unch_memory)
 273       || res1->volatil || res2->volatil)
 274     return 1;
 275
 276 #ifdef HARD_REG_SET
 277   return (res1->regs & res2->regs) != HARD_CONST (0);
 278 #else
 279   {
 280     int i;
 281
 282     for (i = 0; i < HARD_REG_SET_LONGS; i++)
 283       if ((res1->regs[i] & res2->regs[i]) != 0)
 284         return 1;
 285     return 0;
 286   }
 287 #endif
 288 }
 289
 290 /* Return TRUE if any resource marked in RES, a `struct resources', is
 291    referenced by INSN.  If INCLUDE_DELAYED_EFFECTS is set, return if the called
 292    routine is using those resources.
 293
 294    We compute this by computing all the resources referenced by INSN and
 295    seeing if this conflicts with RES.  It might be faster to directly check
 296    ourselves, and this is the way it used to work, but it means duplicating
 297    a large block of complex code.  */
 298
 299 static int
 300 insn_references_resource_p (insn, res, include_delayed_effects)
 301      rtx insn;
 302      struct resources *res;
 303      int include_delayed_effects;
 304 {
 305   struct resources insn_res;
 306
 307   CLEAR_RESOURCE (&insn_res);
 308   mark_referenced_resources (insn, &insn_res, include_delayed_effects);
 309   return resource_conflicts_p (&insn_res, res);
 310 }
 311
 312 /* Return TRUE if INSN modifies resources that are marked in RES.
 313    INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
 314    included.   CC0 is only modified if it is explicitly set; see comments
 315    in front of mark_set_resources for details.  */
 316
 317 static int
 318 insn_sets_resource_p (insn, res, include_delayed_effects)
 319      rtx insn;
 320      struct resources *res;
 321      int include_delayed_effects;
 322 {
 323   struct resources insn_sets;
 324
 325   CLEAR_RESOURCE (&insn_sets);
 326   mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
 327   return resource_conflicts_p (&insn_sets, res);
 328 }
 329 \f
 330 /* Find a label at the end of the function or before a RETURN.  If there is
 331    none, make one.  */
 332
 333 static rtx
 334 find_end_label ()
 335 {
 336   rtx insn;
 337
 338   /* If we found one previously, return it.  */
 339   if (end_of_function_label)
 340     return end_of_function_label;
 341
 342   /* Otherwise, see if there is a label at the end of the function.  If there
 343      is, it must be that RETURN insns aren't needed, so that is our return
 344      label and we don't have to do anything else.  */
 345
 346   insn = get_last_insn ();
 347   while (GET_CODE (insn) == NOTE
 348          || (GET_CODE (insn) == INSN
 349              && (GET_CODE (PATTERN (insn)) == USE
 350                  || GET_CODE (PATTERN (insn)) == CLOBBER)))
 351     insn = PREV_INSN (insn);
 352
 353   /* When a target threads its epilogue we might already have a
 354      suitable return insn.  If so put a label before it for the
 355      end_of_function_label.  */
 356   if (GET_CODE (insn) == BARRIER
 357       && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
 358       && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
 359     {
 360       rtx temp = PREV_INSN (PREV_INSN (insn));
 361       end_of_function_label = gen_label_rtx ();
 362       LABEL_NUSES (end_of_function_label) = 0;
 363
 364       /* Put the label before an USE insns that may proceed the RETURN insn.  */
 365       while (GET_CODE (temp) == USE)
 366         temp = PREV_INSN (temp);
 367
 368       emit_label_after (end_of_function_label, temp);
 369     }
 370
 371   else if (GET_CODE (insn) == CODE_LABEL)
 372     end_of_function_label = insn;
 373   else
 374     {
 375       end_of_function_label = gen_label_rtx ();
 376       LABEL_NUSES (end_of_function_label) = 0;
 377       /* If the basic block reorder pass moves the return insn to
 378          some other place try to locate it again and put our
 379          end_of_function_label there.  */
 380       while (insn && ! (GET_CODE (insn) == JUMP_INSN
 381                         && (GET_CODE (PATTERN (insn)) == RETURN)))
 382         insn = PREV_INSN (insn);
 383       if (insn)
 384         {
 385           insn = PREV_INSN (insn);
 386
 387           /* Put the label before an USE insns that may proceed the
 388              RETURN insn.  */
 389           while (GET_CODE (insn) == USE)
 390             insn = PREV_INSN (insn);
 391
 392           emit_label_after (end_of_function_label, insn);
 393         }
 394       else
 395         {
 396           /* Otherwise, make a new label and emit a RETURN and BARRIER,
 397              if needed.  */
 398           emit_label (end_of_function_label);
 399 #ifdef HAVE_return
 400           if (HAVE_return)
 401             {
 402               /* The return we make may have delay slots too.  */
 403               rtx insn = gen_return ();
 404               insn = emit_jump_insn (insn);
 405               emit_barrier ();
 406               if (num_delay_slots (insn) > 0)
 407                 obstack_ptr_grow (&unfilled_slots_obstack, insn);
 408             }
 409 #endif
 410         }
 411     }
 412
 413   /* Show one additional use for this label so it won't go away until
 414      we are done.  */
 415   ++LABEL_NUSES (end_of_function_label);
 416
 417   return end_of_function_label;
 418 }
 419 \f
 420 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
 421    the pattern of INSN with the SEQUENCE.
 422
 423    Chain the insns so that NEXT_INSN of each insn in the sequence points to
 424    the next and NEXT_INSN of the last insn in the sequence points to
 425    the first insn after the sequence.  Similarly for PREV_INSN.  This makes
 426    it easier to scan all insns.
 427
 428    Returns the SEQUENCE that replaces INSN.  */
 429
 430 static rtx
 431 emit_delay_sequence (insn, list, length)
 432      rtx insn;
 433      rtx list;
 434      int length;
 435 {
 436   int i = 1;
 437   rtx li;
 438   int had_barrier = 0;
 439
 440   /* Allocate the rtvec to hold the insns and the SEQUENCE.  */
 441   rtvec seqv = rtvec_alloc (length + 1);
 442   rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
 443   rtx seq_insn = make_insn_raw (seq);
 444   rtx first = get_insns ();
 445   rtx last = get_last_insn ();
 446
 447   /* Make a copy of the insn having delay slots.  */
 448   rtx delay_insn = copy_rtx (insn);
 449
 450   /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
 451      confuse further processing.  Update LAST in case it was the last insn.
 452      We will put the BARRIER back in later.  */
 453   if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
 454     {
 455       delete_related_insns (NEXT_INSN (insn));
 456       last = get_last_insn ();
 457       had_barrier = 1;
 458     }
 459
 460   /* Splice our SEQUENCE into the insn stream where INSN used to be.  */
 461   NEXT_INSN (seq_insn) = NEXT_INSN (insn);
 462   PREV_INSN (seq_insn) = PREV_INSN (insn);
 463
 464   if (insn != last)
 465     PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
 466
 467   if (insn != first)
 468     NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
 469
 470   /* Note the calls to set_new_first_and_last_insn must occur after
 471      SEQ_INSN has been completely spliced into the insn stream.
 472
 473      Otherwise CUR_INSN_UID will get set to an incorrect value because
 474      set_new_first_and_last_insn will not find SEQ_INSN in the chain.  */
 475   if (insn == last)
 476     set_new_first_and_last_insn (first, seq_insn);
 477
 478   if (insn == first)
 479     set_new_first_and_last_insn (seq_insn, last);
 480
 481   /* Build our SEQUENCE and rebuild the insn chain.  */
 482   XVECEXP (seq, 0, 0) = delay_insn;
 483   INSN_DELETED_P (delay_insn) = 0;
 484   PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
 485
 486   for (li = list; li; li = XEXP (li, 1), i++)
 487     {
 488       rtx tem = XEXP (li, 0);
 489       rtx note, next;
 490
 491       /* Show that this copy of the insn isn't deleted.  */
 492       INSN_DELETED_P (tem) = 0;
 493
 494       XVECEXP (seq, 0, i) = tem;
 495       PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
 496       NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
 497
 498       for (note = REG_NOTES (tem); note; note = next)
 499         {
 500           next = XEXP (note, 1);
 501           switch (REG_NOTE_KIND (note))
 502             {
 503             case REG_DEAD:
 504               /* Remove any REG_DEAD notes because we can't rely on them now
 505                  that the insn has been moved.  */
 506               remove_note (tem, note);
 507               break;
 508
 509             case REG_LABEL:
 510               /* Keep the label reference count up to date.  */
 511               if (GET_CODE (XEXP (note, 0)) == CODE_LABEL)
 512                 LABEL_NUSES (XEXP (note, 0)) ++;
 513               break;
 514
 515             default:
 516               break;
 517             }
 518         }
 519     }
 520
 521   NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
 522
 523   /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
 524      last insn in that SEQUENCE to point to us.  Similarly for the first
 525      insn in the following insn if it is a SEQUENCE.  */
 526
 527   if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
 528       && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
 529     NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
 530                         XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
 531       = seq_insn;
 532
 533   if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
 534       && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
 535     PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
 536
 537   /* If there used to be a BARRIER, put it back.  */
 538   if (had_barrier)
 539     emit_barrier_after (seq_insn);
 540
 541   if (i != length + 1)
 542     abort ();
 543
 544   return seq_insn;
 545 }
 546
 547 /* Add INSN to DELAY_LIST and return the head of the new list.  The list must
 548    be in the order in which the insns are to be executed.  */
 549
 550 static rtx
 551 add_to_delay_list (insn, delay_list)
 552      rtx insn;
 553      rtx delay_list;
 554 {
 555   /* If we have an empty list, just make a new list element.  If
 556      INSN has its block number recorded, clear it since we may
 557      be moving the insn to a new block.  */
 558
 559   if (delay_list == 0)
 560     {
 561       clear_hashed_info_for_insn (insn);
 562       return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
 563     }
 564
 565   /* Otherwise this must be an INSN_LIST.  Add INSN to the end of the
 566      list.  */
 567   XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
 568
 569   return delay_list;
 570 }
 571 \f
 572 /* Delete INSN from the delay slot of the insn that it is in, which may
 573    produce an insn with no delay slots.  Return the new insn.  */
 574
 575 static rtx
 576 delete_from_delay_slot (insn)
 577      rtx insn;
 578 {
 579   rtx trial, seq_insn, seq, prev;
 580   rtx delay_list = 0;
 581   int i;
 582
 583   /* We first must find the insn containing the SEQUENCE with INSN in its
 584      delay slot.  Do this by finding an insn, TRIAL, where
 585      PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL.  */
 586
 587   for (trial = insn;
 588        PREV_INSN (NEXT_INSN (trial)) == trial;
 589        trial = NEXT_INSN (trial))
 590     ;
 591
 592   seq_insn = PREV_INSN (NEXT_INSN (trial));
 593   seq = PATTERN (seq_insn);
 594
 595   /* Create a delay list consisting of all the insns other than the one
 596      we are deleting (unless we were the only one).  */
 597   if (XVECLEN (seq, 0) > 2)
 598     for (i = 1; i < XVECLEN (seq, 0); i++)
 599       if (XVECEXP (seq, 0, i) != insn)
 600         delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
 601
 602   /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
 603      list, and rebuild the delay list if non-empty.  */
 604   prev = PREV_INSN (seq_insn);
 605   trial = XVECEXP (seq, 0, 0);
 606   delete_related_insns (seq_insn);
 607   add_insn_after (trial, prev);
 608
 609   if (GET_CODE (trial) == JUMP_INSN
 610       && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
 611     emit_barrier_after (trial);
 612
 613   /* If there are any delay insns, remit them.  Otherwise clear the
 614      annul flag.  */
 615   if (delay_list)
 616     trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2);
 617   else if (GET_CODE (trial) == JUMP_INSN
 618            || GET_CODE (trial) == CALL_INSN
 619            || GET_CODE (trial) == INSN)
 620     INSN_ANNULLED_BRANCH_P (trial) = 0;
 621
 622   INSN_FROM_TARGET_P (insn) = 0;
 623
 624   /* Show we need to fill this insn again.  */
 625   obstack_ptr_grow (&unfilled_slots_obstack, trial);
 626
 627   return trial;
 628 }
 629 \f
 630 /* Delete INSN, a JUMP_INSN.  If it is a conditional jump, we must track down
 631    the insn that sets CC0 for it and delete it too.  */
 632
 633 static void
 634 delete_scheduled_jump (insn)
 635      rtx insn;
 636 {
 637   /* Delete the insn that sets cc0 for us.  On machines without cc0, we could
 638      delete the insn that sets the condition code, but it is hard to find it.
 639      Since this case is rare anyway, don't bother trying; there would likely
 640      be other insns that became dead anyway, which we wouldn't know to
 641      delete.  */
 642
 643 #ifdef HAVE_cc0
 644   if (reg_mentioned_p (cc0_rtx, insn))
 645     {
 646       rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
 647
 648       /* If a reg-note was found, it points to an insn to set CC0.  This
 649          insn is in the delay list of some other insn.  So delete it from
 650          the delay list it was in.  */
 651       if (note)
 652         {
 653           if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
 654               && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
 655             delete_from_delay_slot (XEXP (note, 0));
 656         }
 657       else
 658         {
 659           /* The insn setting CC0 is our previous insn, but it may be in
 660              a delay slot.  It will be the last insn in the delay slot, if
 661              it is.  */
 662           rtx trial = previous_insn (insn);
 663           if (GET_CODE (trial) == NOTE)
 664             trial = prev_nonnote_insn (trial);
 665           if (sets_cc0_p (PATTERN (trial)) != 1
 666               || FIND_REG_INC_NOTE (trial, NULL_RTX))
 667             return;
 668           if (PREV_INSN (NEXT_INSN (trial)) == trial)
 669             delete_related_insns (trial);
 670           else
 671             delete_from_delay_slot (trial);
 672         }
 673     }
 674 #endif
 675
 676   delete_related_insns (insn);
 677 }
 678 \f
 679 /* Counters for delay-slot filling.  */
 680
 681 #define NUM_REORG_FUNCTIONS 2
 682 #define MAX_DELAY_HISTOGRAM 3
 683 #define MAX_REORG_PASSES 2
 684
 685 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
 686
 687 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
 688
 689 static int reorg_pass_number;
 690
 691 static void
 692 note_delay_statistics (slots_filled, index)
 693      int slots_filled, index;
 694 {
 695   num_insns_needing_delays[index][reorg_pass_number]++;
 696   if (slots_filled > MAX_DELAY_HISTOGRAM)
 697     slots_filled = MAX_DELAY_HISTOGRAM;
 698   num_filled_delays[index][slots_filled][reorg_pass_number]++;
 699 }
 700 \f
 701 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
 702
 703 /* Optimize the following cases:
 704
 705    1.  When a conditional branch skips over only one instruction,
 706        use an annulling branch and put that insn in the delay slot.
 707        Use either a branch that annuls when the condition if true or
 708        invert the test with a branch that annuls when the condition is
 709        false.  This saves insns, since otherwise we must copy an insn
 710        from the L1 target.
 711
 712         (orig)           (skip)         (otherwise)
 713         Bcc.n L1        Bcc',a L1       Bcc,a L1'
 714         insn            insn            insn2
 715       L1:             L1:             L1:
 716         insn2           insn2           insn2
 717         insn3           insn3         L1':
 718                                         insn3
 719
 720    2.  When a conditional branch skips over only one instruction,
 721        and after that, it unconditionally branches somewhere else,
 722        perform the similar optimization. This saves executing the
 723        second branch in the case where the inverted condition is true.
 724
 725         Bcc.n L1        Bcc',a L2
 726         insn            insn
 727       L1:             L1:
 728         Bra L2          Bra L2
 729
 730    INSN is a JUMP_INSN.
 731
 732    This should be expanded to skip over N insns, where N is the number
 733    of delay slots required.  */
 734
 735 static rtx
 736 optimize_skip (insn)
 737      rtx insn;
 738 {
 739   rtx trial = next_nonnote_insn (insn);
 740   rtx next_trial = next_active_insn (trial);
 741   rtx delay_list = 0;
 742   rtx target_label;
 743   int flags;
 744
 745   flags = get_jump_flags (insn, JUMP_LABEL (insn));
 746
 747   if (trial == 0
 748       || GET_CODE (trial) != INSN
 749       || GET_CODE (PATTERN (trial)) == SEQUENCE
 750       || recog_memoized (trial) < 0
 751       || (! eligible_for_annul_false (insn, 0, trial, flags)
 752           && ! eligible_for_annul_true (insn, 0, trial, flags))
 753       || can_throw_internal (trial))
 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 nonzero, 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 nonzero 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 nonzero 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 nonzero.  */
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 nonzero 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 nonzero.  */
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 nonzero 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 nonzero.
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 nonzero,
1860    it is the target of the branch insn being scanned.  If ALLOW_FALLTHROUGH
1861    is nonzero, 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 nonzero 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           && ! can_throw_internal (trial))
2132         {
2133           rtx *tmp;
2134           slots_filled++;
2135           delay_list = add_to_delay_list (trial, delay_list);
2136
2137           /* TRIAL may have had its delay slot filled, then unfilled.  When
2138              the delay slot is unfilled, TRIAL is placed back on the unfilled
2139              slots obstack.  Unfortunately, it is placed on the end of the
2140              obstack, not in its original location.  Therefore, we must search
2141              from entry i + 1 to the end of the unfilled slots obstack to
2142              try and find TRIAL.  */
2143           tmp = &unfilled_slots_base[i + 1];
2144           while (*tmp != trial && tmp != unfilled_slots_next)
2145             tmp++;
2146
2147           /* Remove the unconditional jump from consideration for delay slot
2148              filling and unthread it.  */
2149           if (*tmp == trial)
2150             *tmp = 0;
2151           {
2152             rtx next = NEXT_INSN (trial);
2153             rtx prev = PREV_INSN (trial);
2154             if (prev)
2155               NEXT_INSN (prev) = next;
2156             if (next)
2157               PREV_INSN (next) = prev;
2158           }
2159         }
2160
2161       /* Now, scan backwards from the insn to search for a potential
2162          delay-slot candidate.  Stop searching when a label or jump is hit.
2163
2164          For each candidate, if it is to go into the delay slot (moved
2165          forward in execution sequence), it must not need or set any resources
2166          that were set by later insns and must not set any resources that
2167          are needed for those insns.
2168
2169          The delay slot insn itself sets resources unless it is a call
2170          (in which case the called routine, not the insn itself, is doing
2171          the setting).  */
2172
2173       if (slots_filled < slots_to_fill)
2174         {
2175           CLEAR_RESOURCE (&needed);
2176           CLEAR_RESOURCE (&set);
2177           mark_set_resources (insn, &set, 0, MARK_SRC_DEST);
2178           mark_referenced_resources (insn, &needed, 0);
2179
2180           for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2181                trial = next_trial)
2182             {
2183               next_trial = prev_nonnote_insn (trial);
2184
2185               /* This must be an INSN or CALL_INSN.  */
2186               pat = PATTERN (trial);
2187
2188               /* USE and CLOBBER at this level was just for flow; ignore it.  */
2189               if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2190                 continue;
2191
2192               /* Check for resource conflict first, to avoid unnecessary
2193                  splitting.  */
2194               if (! insn_references_resource_p (trial, &set, 1)
2195                   && ! insn_sets_resource_p (trial, &set, 1)
2196                   && ! insn_sets_resource_p (trial, &needed, 1)
2197 #ifdef HAVE_cc0
2198                   /* Can't separate set of cc0 from its use.  */
2199                   && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2200 #endif
2201                   && ! can_throw_internal (trial))
2202                 {
2203                   trial = try_split (pat, trial, 1);
2204                   next_trial = prev_nonnote_insn (trial);
2205                   if (eligible_for_delay (insn, slots_filled, trial, flags))
2206                     {
2207                       /* In this case, we are searching backward, so if we
2208                          find insns to put on the delay list, we want
2209                          to put them at the head, rather than the
2210                          tail, of the list.  */
2211
2212                       update_reg_dead_notes (trial, insn);
2213                       delay_list = gen_rtx_INSN_LIST (VOIDmode,
2214                                                       trial, delay_list);
2215                       update_block (trial, trial);
2216                       delete_related_insns (trial);
2217                       if (slots_to_fill == ++slots_filled)
2218                         break;
2219                       continue;
2220                     }
2221                 }
2222
2223               mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2224               mark_referenced_resources (trial, &needed, 1);
2225             }
2226         }
2227
2228       /* If all needed slots haven't been filled, we come here.  */
2229
2230       /* Try to optimize case of jumping around a single insn.  */
2231 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2232       if (slots_filled != slots_to_fill
2233           && delay_list == 0
2234           && GET_CODE (insn) == JUMP_INSN
2235           && (condjump_p (insn) || condjump_in_parallel_p (insn)))
2236         {
2237           delay_list = optimize_skip (insn);
2238           if (delay_list)
2239             slots_filled += 1;
2240         }
2241 #endif
2242
2243       /* Try to get insns from beyond the insn needing the delay slot.
2244          These insns can neither set or reference resources set in insns being
2245          skipped, cannot set resources in the insn being skipped, and, if this
2246          is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2247          call might not return).
2248
2249          There used to be code which continued past the target label if
2250          we saw all uses of the target label.  This code did not work,
2251          because it failed to account for some instructions which were
2252          both annulled and marked as from the target.  This can happen as a
2253          result of optimize_skip.  Since this code was redundant with
2254          fill_eager_delay_slots anyways, it was just deleted.  */
2255
2256       if (slots_filled != slots_to_fill
2257           /* If this instruction could throw an exception which is
2258              caught in the same function, then it's not safe to fill
2259              the delay slot with an instruction from beyond this
2260              point.  For example, consider:
2261
2262                int i = 2;
2263
2264                try {
2265                  f();
2266                  i = 3;
2267                } catch (...) {}
2268
2269                return i;
2270
2271              Even though `i' is a local variable, we must be sure not
2272              to put `i = 3' in the delay slot if `f' might throw an
2273              exception.
2274
2275              Presumably, we should also check to see if we could get
2276              back to this function via `setjmp'.  */
2277           && ! can_throw_internal (insn)
2278           && (GET_CODE (insn) != JUMP_INSN
2279               || ((condjump_p (insn) || condjump_in_parallel_p (insn))
2280                   && ! simplejump_p (insn)
2281                   && JUMP_LABEL (insn) != 0)))
2282         {
2283           /* Invariant: If insn is a JUMP_INSN, the insn's jump
2284              label.  Otherwise, zero.  */
2285           rtx target = 0;
2286           int maybe_never = 0;
2287           rtx pat, trial_delay;
2288
2289           CLEAR_RESOURCE (&needed);
2290           CLEAR_RESOURCE (&set);
2291
2292           if (GET_CODE (insn) == CALL_INSN)
2293             {
2294               mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
2295               mark_referenced_resources (insn, &needed, 1);
2296               maybe_never = 1;
2297             }
2298           else
2299             {
2300               mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
2301               mark_referenced_resources (insn, &needed, 1);
2302               if (GET_CODE (insn) == JUMP_INSN)
2303                 target = JUMP_LABEL (insn);
2304             }
2305
2306           if (target == 0)
2307             for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2308               {
2309                 next_trial = next_nonnote_insn (trial);
2310
2311                 if (GET_CODE (trial) == CODE_LABEL
2312                     || GET_CODE (trial) == BARRIER)
2313                   break;
2314
2315                 /* We must have an INSN, JUMP_INSN, or CALL_INSN.  */
2316                 pat = PATTERN (trial);
2317
2318                 /* Stand-alone USE and CLOBBER are just for flow.  */
2319                 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2320                   continue;
2321
2322                 /* If this already has filled delay slots, get the insn needing
2323                    the delay slots.  */
2324                 if (GET_CODE (pat) == SEQUENCE)
2325                   trial_delay = XVECEXP (pat, 0, 0);
2326                 else
2327                   trial_delay = trial;
2328
2329                 /* Stop our search when seeing an unconditional jump.  */
2330                 if (GET_CODE (trial_delay) == JUMP_INSN)
2331                   break;
2332
2333                 /* See if we have a resource problem before we try to
2334                    split.  */
2335                 if (GET_CODE (pat) != SEQUENCE
2336                     && ! insn_references_resource_p (trial, &set, 1)
2337                     && ! insn_sets_resource_p (trial, &set, 1)
2338                     && ! insn_sets_resource_p (trial, &needed, 1)
2339 #ifdef HAVE_cc0
2340                     && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2341 #endif
2342                     && ! (maybe_never && may_trap_p (pat))
2343                     && (trial = try_split (pat, trial, 0))
2344                     && eligible_for_delay (insn, slots_filled, trial, flags)
2345                     && ! can_throw_internal(trial))
2346                   {
2347                     next_trial = next_nonnote_insn (trial);
2348                     delay_list = add_to_delay_list (trial, delay_list);
2349
2350 #ifdef HAVE_cc0
2351                     if (reg_mentioned_p (cc0_rtx, pat))
2352                       link_cc0_insns (trial);
2353 #endif
2354
2355                     delete_related_insns (trial);
2356                     if (slots_to_fill == ++slots_filled)
2357                       break;
2358                     continue;
2359                   }
2360
2361                 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2362                 mark_referenced_resources (trial, &needed, 1);
2363
2364                 /* Ensure we don't put insns between the setting of cc and the
2365                    comparison by moving a setting of cc into an earlier delay
2366                    slot since these insns could clobber the condition code.  */
2367                 set.cc = 1;
2368
2369                 /* If this is a call or jump, we might not get here.  */
2370                 if (GET_CODE (trial_delay) == CALL_INSN
2371                     || GET_CODE (trial_delay) == JUMP_INSN)
2372                   maybe_never = 1;
2373               }
2374
2375           /* If there are slots left to fill and our search was stopped by an
2376              unconditional branch, try the insn at the branch target.  We can
2377              redirect the branch if it works.
2378
2379              Don't do this if the insn at the branch target is a branch.  */
2380           if (slots_to_fill != slots_filled
2381               && trial
2382               && GET_CODE (trial) == JUMP_INSN
2383               && simplejump_p (trial)
2384               && (target == 0 || JUMP_LABEL (trial) == target)
2385               && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2386               && ! (GET_CODE (next_trial) == INSN
2387                     && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2388               && GET_CODE (next_trial) != JUMP_INSN
2389               && ! insn_references_resource_p (next_trial, &set, 1)
2390               && ! insn_sets_resource_p (next_trial, &set, 1)
2391               && ! insn_sets_resource_p (next_trial, &needed, 1)
2392 #ifdef HAVE_cc0
2393               && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2394 #endif
2395               && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2396               && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2397               && eligible_for_delay (insn, slots_filled, next_trial, flags)
2398               && ! can_throw_internal (trial))
2399             {
2400               rtx new_label = next_active_insn (next_trial);
2401
2402               if (new_label != 0)
2403                 new_label = get_label_before (new_label);
2404               else
2405                 new_label = find_end_label ();
2406
2407               delay_list
2408                 = add_to_delay_list (copy_rtx (next_trial), delay_list);
2409               slots_filled++;
2410               reorg_redirect_jump (trial, new_label);
2411
2412               /* If we merged because we both jumped to the same place,
2413                  redirect the original insn also.  */
2414               if (target)
2415                 reorg_redirect_jump (insn, new_label);
2416             }
2417         }
2418
2419       /* If this is an unconditional jump, then try to get insns from the
2420          target of the jump.  */
2421       if (GET_CODE (insn) == JUMP_INSN
2422           && simplejump_p (insn)
2423           && slots_filled != slots_to_fill)
2424         delay_list
2425           = fill_slots_from_thread (insn, const_true_rtx,
2426                                     next_active_insn (JUMP_LABEL (insn)),
2427                                     NULL, 1, 1,
2428                                     own_thread_p (JUMP_LABEL (insn),
2429                                                   JUMP_LABEL (insn), 0),
2430                                     slots_to_fill, &slots_filled,
2431                                     delay_list);
2432
2433       if (delay_list)
2434         unfilled_slots_base[i]
2435           = emit_delay_sequence (insn, delay_list, slots_filled);
2436
2437       if (slots_to_fill == slots_filled)
2438         unfilled_slots_base[i] = 0;
2439
2440       note_delay_statistics (slots_filled, 0);
2441     }
2442
2443 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2444   /* See if the epilogue needs any delay slots.  Try to fill them if so.
2445      The only thing we can do is scan backwards from the end of the
2446      function.  If we did this in a previous pass, it is incorrect to do it
2447      again.  */
2448   if (current_function_epilogue_delay_list)
2449     return;
2450
2451   slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2452   if (slots_to_fill == 0)
2453     return;
2454
2455   slots_filled = 0;
2456   CLEAR_RESOURCE (&set);
2457
2458   /* The frame pointer and stack pointer are needed at the beginning of
2459      the epilogue, so instructions setting them can not be put in the
2460      epilogue delay slot.  However, everything else needed at function
2461      end is safe, so we don't want to use end_of_function_needs here.  */
2462   CLEAR_RESOURCE (&needed);
2463   if (frame_pointer_needed)
2464     {
2465       SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
2466 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2467       SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
2468 #endif
2469 #ifdef EXIT_IGNORE_STACK
2470       if (! EXIT_IGNORE_STACK
2471           || current_function_sp_is_unchanging)
2472 #endif
2473         SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
2474     }
2475   else
2476     SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
2477
2478 #ifdef EPILOGUE_USES
2479   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2480     {
2481       if (EPILOGUE_USES (i))
2482         SET_HARD_REG_BIT (needed.regs, i);
2483     }
2484 #endif
2485
2486   for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2487        trial = PREV_INSN (trial))
2488     {
2489       if (GET_CODE (trial) == NOTE)
2490         continue;
2491       pat = PATTERN (trial);
2492       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2493         continue;
2494
2495       if (! insn_references_resource_p (trial, &set, 1)
2496           && ! insn_sets_resource_p (trial, &needed, 1)
2497           && ! insn_sets_resource_p (trial, &set, 1)
2498 #ifdef HAVE_cc0
2499           /* Don't want to mess with cc0 here.  */
2500           && ! reg_mentioned_p (cc0_rtx, pat)
2501 #endif
2502           && ! can_throw_internal (trial))
2503         {
2504           trial = try_split (pat, trial, 1);
2505           if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2506             {
2507               /* Here as well we are searching backward, so put the
2508                  insns we find on the head of the list.  */
2509
2510               current_function_epilogue_delay_list
2511                 = gen_rtx_INSN_LIST (VOIDmode, trial,
2512                                      current_function_epilogue_delay_list);
2513               mark_end_of_function_resources (trial, 1);
2514               update_block (trial, trial);
2515               delete_related_insns (trial);
2516
2517               /* Clear deleted bit so final.c will output the insn.  */
2518               INSN_DELETED_P (trial) = 0;
2519
2520               if (slots_to_fill == ++slots_filled)
2521                 break;
2522               continue;
2523             }
2524         }
2525
2526       mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2527       mark_referenced_resources (trial, &needed, 1);
2528     }
2529
2530   note_delay_statistics (slots_filled, 0);
2531 #endif
2532 }
2533 \f
2534 /* Try to find insns to place in delay slots.
2535
2536    INSN is the jump needing SLOTS_TO_FILL delay slots.  It tests CONDITION
2537    or is an unconditional branch if CONDITION is const_true_rtx.
2538    *PSLOTS_FILLED is updated with the number of slots that we have filled.
2539
2540    THREAD is a flow-of-control, either the insns to be executed if the
2541    branch is true or if the branch is false, THREAD_IF_TRUE says which.
2542
2543    OPPOSITE_THREAD is the thread in the opposite direction.  It is used
2544    to see if any potential delay slot insns set things needed there.
2545
2546    LIKELY is nonzero if it is extremely likely that the branch will be
2547    taken and THREAD_IF_TRUE is set.  This is used for the branch at the
2548    end of a loop back up to the top.
2549
2550    OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2551    thread.  I.e., it is the fallthrough code of our jump or the target of the
2552    jump when we are the only jump going there.
2553
2554    If OWN_THREAD is false, it must be the "true" thread of a jump.  In that
2555    case, we can only take insns from the head of the thread for our delay
2556    slot.  We then adjust the jump to point after the insns we have taken.  */
2557
2558 static rtx
2559 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
2560                         thread_if_true, own_thread,
2561                         slots_to_fill, pslots_filled, delay_list)
2562      rtx insn;
2563      rtx condition;
2564      rtx thread, opposite_thread;
2565      int likely;
2566      int thread_if_true;
2567      int own_thread;
2568      int slots_to_fill, *pslots_filled;
2569      rtx delay_list;
2570 {
2571   rtx new_thread;
2572   struct resources opposite_needed, set, needed;
2573   rtx trial;
2574   int lose = 0;
2575   int must_annul = 0;
2576   int flags;
2577
2578   /* Validate our arguments.  */
2579   if ((condition == const_true_rtx && ! thread_if_true)
2580       || (! own_thread && ! thread_if_true))
2581     abort ();
2582
2583   flags = get_jump_flags (insn, JUMP_LABEL (insn));
2584
2585   /* If our thread is the end of subroutine, we can't get any delay
2586      insns from that.  */
2587   if (thread == 0)
2588     return delay_list;
2589
2590   /* If this is an unconditional branch, nothing is needed at the
2591      opposite thread.  Otherwise, compute what is needed there.  */
2592   if (condition == const_true_rtx)
2593     CLEAR_RESOURCE (&opposite_needed);
2594   else
2595     mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed);
2596
2597   /* If the insn at THREAD can be split, do it here to avoid having to
2598      update THREAD and NEW_THREAD if it is done in the loop below.  Also
2599      initialize NEW_THREAD.  */
2600
2601   new_thread = thread = try_split (PATTERN (thread), thread, 0);
2602
2603   /* Scan insns at THREAD.  We are looking for an insn that can be removed
2604      from THREAD (it neither sets nor references resources that were set
2605      ahead of it and it doesn't set anything needs by the insns ahead of
2606      it) and that either can be placed in an annulling insn or aren't
2607      needed at OPPOSITE_THREAD.  */
2608
2609   CLEAR_RESOURCE (&needed);
2610   CLEAR_RESOURCE (&set);
2611
2612   /* If we do not own this thread, we must stop as soon as we find
2613      something that we can't put in a delay slot, since all we can do
2614      is branch into THREAD at a later point.  Therefore, labels stop
2615      the search if this is not the `true' thread.  */
2616
2617   for (trial = thread;
2618        ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2619        trial = next_nonnote_insn (trial))
2620     {
2621       rtx pat, old_trial;
2622
2623       /* If we have passed a label, we no longer own this thread.  */
2624       if (GET_CODE (trial) == CODE_LABEL)
2625         {
2626           own_thread = 0;
2627           continue;
2628         }
2629
2630       pat = PATTERN (trial);
2631       if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2632         continue;
2633
2634       /* If TRIAL conflicts with the insns ahead of it, we lose.  Also,
2635          don't separate or copy insns that set and use CC0.  */
2636       if (! insn_references_resource_p (trial, &set, 1)
2637           && ! insn_sets_resource_p (trial, &set, 1)
2638           && ! insn_sets_resource_p (trial, &needed, 1)
2639 #ifdef HAVE_cc0
2640           && ! (reg_mentioned_p (cc0_rtx, pat)
2641                 && (! own_thread || ! sets_cc0_p (pat)))
2642 #endif
2643           && ! can_throw_internal (trial))
2644         {
2645           rtx prior_insn;
2646
2647           /* If TRIAL is redundant with some insn before INSN, we don't
2648              actually need to add it to the delay list; we can merely pretend
2649              we did.  */
2650           if ((prior_insn = redundant_insn (trial, insn, delay_list)))
2651             {
2652               fix_reg_dead_note (prior_insn, insn);
2653               if (own_thread)
2654                 {
2655                   update_block (trial, thread);
2656                   if (trial == thread)
2657                     {
2658                       thread = next_active_insn (thread);
2659                       if (new_thread == trial)
2660                         new_thread = thread;
2661                     }
2662
2663                   delete_related_insns (trial);
2664                 }
2665               else
2666                 {
2667                   update_reg_unused_notes (prior_insn, trial);
2668                   new_thread = next_active_insn (trial);
2669                 }
2670
2671               continue;
2672             }
2673
2674           /* There are two ways we can win:  If TRIAL doesn't set anything
2675              needed at the opposite thread and can't trap, or if it can
2676              go into an annulled delay slot.  */
2677           if (!must_annul
2678               && (condition == const_true_rtx
2679                   || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2680                       && ! may_trap_p (pat))))
2681             {
2682               old_trial = trial;
2683               trial = try_split (pat, trial, 0);
2684               if (new_thread == old_trial)
2685                 new_thread = trial;
2686               if (thread == old_trial)
2687                 thread = trial;
2688               pat = PATTERN (trial);
2689               if (eligible_for_delay (insn, *pslots_filled, trial, flags))
2690                 goto winner;
2691             }
2692           else if (0
2693 #ifdef ANNUL_IFTRUE_SLOTS
2694                    || ! thread_if_true
2695 #endif
2696 #ifdef ANNUL_IFFALSE_SLOTS
2697                    || thread_if_true
2698 #endif
2699                    )
2700             {
2701               old_trial = trial;
2702               trial = try_split (pat, trial, 0);
2703               if (new_thread == old_trial)
2704                 new_thread = trial;
2705               if (thread == old_trial)
2706                 thread = trial;
2707               pat = PATTERN (trial);
2708               if ((must_annul || delay_list == NULL) && (thread_if_true
2709                    ? check_annul_list_true_false (0, delay_list)
2710                      && eligible_for_annul_false (insn, *pslots_filled, trial, flags)
2711                    : check_annul_list_true_false (1, delay_list)
2712                      && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
2713                 {
2714                   rtx temp;
2715
2716                   must_annul = 1;
2717                 winner:
2718
2719 #ifdef HAVE_cc0
2720                   if (reg_mentioned_p (cc0_rtx, pat))
2721                     link_cc0_insns (trial);
2722 #endif
2723
2724                   /* If we own this thread, delete the insn.  If this is the
2725                      destination of a branch, show that a basic block status
2726                      may have been updated.  In any case, mark the new
2727                      starting point of this thread.  */
2728                   if (own_thread)
2729                     {
2730                       rtx note;
2731
2732                       update_block (trial, thread);
2733                       if (trial == thread)
2734                         {
2735                           thread = next_active_insn (thread);
2736                           if (new_thread == trial)
2737                             new_thread = thread;
2738                         }
2739
2740                       /* We are moving this insn, not deleting it.  We must
2741                          temporarily increment the use count on any referenced
2742                          label lest it be deleted by delete_related_insns.  */
2743                       note = find_reg_note (trial, REG_LABEL, 0);
2744                       /* REG_LABEL could be NOTE_INSN_DELETED_LABEL too.  */
2745                       if (note && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2746                         LABEL_NUSES (XEXP (note, 0))++;
2747
2748                       delete_related_insns (trial);
2749
2750                       if (note && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2751                         LABEL_NUSES (XEXP (note, 0))--;
2752                     }
2753                   else
2754                     new_thread = next_active_insn (trial);
2755
2756                   temp = own_thread ? trial : copy_rtx (trial);
2757                   if (thread_if_true)
2758                     INSN_FROM_TARGET_P (temp) = 1;
2759
2760                   delay_list = add_to_delay_list (temp, delay_list);
2761
2762                   if (slots_to_fill == ++(*pslots_filled))
2763                     {
2764                       /* Even though we have filled all the slots, we
2765                          may be branching to a location that has a
2766                          redundant insn.  Skip any if so.  */
2767                       while (new_thread && ! own_thread
2768                              && ! insn_sets_resource_p (new_thread, &set, 1)
2769                              && ! insn_sets_resource_p (new_thread, &needed, 1)
2770                              && ! insn_references_resource_p (new_thread,
2771                                                               &set, 1)
2772                              && (prior_insn
2773                                  = redundant_insn (new_thread, insn,
2774                                                    delay_list)))
2775                         {
2776                           /* We know we do not own the thread, so no need
2777                              to call update_block and delete_insn.  */
2778                           fix_reg_dead_note (prior_insn, insn);
2779                           update_reg_unused_notes (prior_insn, new_thread);
2780                           new_thread = next_active_insn (new_thread);
2781                         }
2782                       break;
2783                     }
2784
2785                   continue;
2786                 }
2787             }
2788         }
2789
2790       /* This insn can't go into a delay slot.  */
2791       lose = 1;
2792       mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2793       mark_referenced_resources (trial, &needed, 1);
2794
2795       /* Ensure we don't put insns between the setting of cc and the comparison
2796          by moving a setting of cc into an earlier delay slot since these insns
2797          could clobber the condition code.  */
2798       set.cc = 1;
2799
2800       /* If this insn is a register-register copy and the next insn has
2801          a use of our destination, change it to use our source.  That way,
2802          it will become a candidate for our delay slot the next time
2803          through this loop.  This case occurs commonly in loops that
2804          scan a list.
2805
2806          We could check for more complex cases than those tested below,
2807          but it doesn't seem worth it.  It might also be a good idea to try
2808          to swap the two insns.  That might do better.
2809
2810          We can't do this if the next insn modifies our destination, because
2811          that would make the replacement into the insn invalid.  We also can't
2812          do this if it modifies our source, because it might be an earlyclobber
2813          operand.  This latter test also prevents updating the contents of
2814          a PRE_INC.  */
2815
2816       if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2817           && GET_CODE (SET_SRC (pat)) == REG
2818           && GET_CODE (SET_DEST (pat)) == REG)
2819         {
2820           rtx next = next_nonnote_insn (trial);
2821
2822           if (next && GET_CODE (next) == INSN
2823               && GET_CODE (PATTERN (next)) != USE
2824               && ! reg_set_p (SET_DEST (pat), next)
2825               && ! reg_set_p (SET_SRC (pat), next)
2826               && reg_referenced_p (SET_DEST (pat), PATTERN (next))
2827               && ! modified_in_p (SET_DEST (pat), next))
2828             validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2829         }
2830     }
2831
2832   /* If we stopped on a branch insn that has delay slots, see if we can
2833      steal some of the insns in those slots.  */
2834   if (trial && GET_CODE (trial) == INSN
2835       && GET_CODE (PATTERN (trial)) == SEQUENCE
2836       && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2837     {
2838       /* If this is the `true' thread, we will want to follow the jump,
2839          so we can only do this if we have taken everything up to here.  */
2840       if (thread_if_true && trial == new_thread)
2841         {
2842           delay_list
2843             = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2844                                             delay_list, &set, &needed,
2845                                             &opposite_needed, slots_to_fill,
2846                                             pslots_filled, &must_annul,
2847                                             &new_thread);
2848           /* If we owned the thread and are told that it branched
2849              elsewhere, make sure we own the thread at the new location.  */
2850           if (own_thread && trial != new_thread)
2851             own_thread = own_thread_p (new_thread, new_thread, 0);
2852         }
2853       else if (! thread_if_true)
2854         delay_list
2855           = steal_delay_list_from_fallthrough (insn, condition,
2856                                                PATTERN (trial),
2857                                                delay_list, &set, &needed,
2858                                                &opposite_needed, slots_to_fill,
2859                                                pslots_filled, &must_annul);
2860     }
2861
2862   /* If we haven't found anything for this delay slot and it is very
2863      likely that the branch will be taken, see if the insn at our target
2864      increments or decrements a register with an increment that does not
2865      depend on the destination register.  If so, try to place the opposite
2866      arithmetic insn after the jump insn and put the arithmetic insn in the
2867      delay slot.  If we can't do this, return.  */
2868   if (delay_list == 0 && likely && new_thread
2869       && GET_CODE (new_thread) == INSN
2870       && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
2871       && asm_noperands (PATTERN (new_thread)) < 0)
2872     {
2873       rtx pat = PATTERN (new_thread);
2874       rtx dest;
2875       rtx src;
2876
2877       trial = new_thread;
2878       pat = PATTERN (trial);
2879
2880       if (GET_CODE (trial) != INSN
2881           || GET_CODE (pat) != SET
2882           || ! eligible_for_delay (insn, 0, trial, flags)
2883           || can_throw_internal (trial))
2884         return 0;
2885
2886       dest = SET_DEST (pat), src = SET_SRC (pat);
2887       if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2888           && rtx_equal_p (XEXP (src, 0), dest)
2889           && ! reg_overlap_mentioned_p (dest, XEXP (src, 1))
2890           && ! side_effects_p (pat))
2891         {
2892           rtx other = XEXP (src, 1);
2893           rtx new_arith;
2894           rtx ninsn;
2895
2896           /* If this is a constant adjustment, use the same code with
2897              the negated constant.  Otherwise, reverse the sense of the
2898              arithmetic.  */
2899           if (GET_CODE (other) == CONST_INT)
2900             new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
2901                                         negate_rtx (GET_MODE (src), other));
2902           else
2903             new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
2904                                         GET_MODE (src), dest, other);
2905
2906           ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith),
2907                                    insn);
2908
2909           if (recog_memoized (ninsn) < 0
2910               || (extract_insn (ninsn), ! constrain_operands (1)))
2911             {
2912               delete_related_insns (ninsn);
2913               return 0;
2914             }
2915
2916           if (own_thread)
2917             {
2918               update_block (trial, thread);
2919               if (trial == thread)
2920                 {
2921                   thread = next_active_insn (thread);
2922                   if (new_thread == trial)
2923                     new_thread = thread;
2924                 }
2925               delete_related_insns (trial);
2926             }
2927           else
2928             new_thread = next_active_insn (trial);
2929
2930           ninsn = own_thread ? trial : copy_rtx (trial);
2931           if (thread_if_true)
2932             INSN_FROM_TARGET_P (ninsn) = 1;
2933
2934           delay_list = add_to_delay_list (ninsn, NULL_RTX);
2935           (*pslots_filled)++;
2936         }
2937     }
2938
2939   if (delay_list && must_annul)
2940     INSN_ANNULLED_BRANCH_P (insn) = 1;
2941
2942   /* If we are to branch into the middle of this thread, find an appropriate
2943      label or make a new one if none, and redirect INSN to it.  If we hit the
2944      end of the function, use the end-of-function label.  */
2945   if (new_thread != thread)
2946     {
2947       rtx label;
2948
2949       if (! thread_if_true)
2950         abort ();
2951
2952       if (new_thread && GET_CODE (new_thread) == JUMP_INSN
2953           && (simplejump_p (new_thread)
2954               || GET_CODE (PATTERN (new_thread)) == RETURN)
2955           && redirect_with_delay_list_safe_p (insn,
2956                                               JUMP_LABEL (new_thread),
2957                                               delay_list))
2958         new_thread = follow_jumps (JUMP_LABEL (new_thread));
2959
2960       if (new_thread == 0)
2961         label = find_end_label ();
2962       else if (GET_CODE (new_thread) == CODE_LABEL)
2963         label = new_thread;
2964       else
2965         label = get_label_before (new_thread);
2966
2967       reorg_redirect_jump (insn, label);
2968     }
2969
2970   return delay_list;
2971 }
2972 \f
2973 /* Make another attempt to find insns to place in delay slots.
2974
2975    We previously looked for insns located in front of the delay insn
2976    and, for non-jump delay insns, located behind the delay insn.
2977
2978    Here only try to schedule jump insns and try to move insns from either
2979    the target or the following insns into the delay slot.  If annulling is
2980    supported, we will be likely to do this.  Otherwise, we can do this only
2981    if safe.  */
2982
2983 static void
2984 fill_eager_delay_slots ()
2985 {
2986   rtx insn;
2987   int i;
2988   int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2989
2990   for (i = 0; i < num_unfilled_slots; i++)
2991     {
2992       rtx condition;
2993       rtx target_label, insn_at_target, fallthrough_insn;
2994       rtx delay_list = 0;
2995       int own_target;
2996       int own_fallthrough;
2997       int prediction, slots_to_fill, slots_filled;
2998
2999       insn = unfilled_slots_base[i];
3000       if (insn == 0
3001           || INSN_DELETED_P (insn)
3002           || GET_CODE (insn) != JUMP_INSN
3003           || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
3004         continue;
3005
3006       slots_to_fill = num_delay_slots (insn);
3007       /* Some machine description have defined instructions to have
3008          delay slots only in certain circumstances which may depend on
3009          nearby insns (which change due to reorg's actions).
3010
3011          For example, the PA port normally has delay slots for unconditional
3012          jumps.
3013
3014          However, the PA port claims such jumps do not have a delay slot
3015          if they are immediate successors of certain CALL_INSNs.  This
3016          allows the port to favor filling the delay slot of the call with
3017          the unconditional jump.  */
3018       if (slots_to_fill == 0)
3019         continue;
3020
3021       slots_filled = 0;
3022       target_label = JUMP_LABEL (insn);
3023       condition = get_branch_condition (insn, target_label);
3024
3025       if (condition == 0)
3026         continue;
3027
3028       /* Get the next active fallthrough and target insns and see if we own
3029          them.  Then see whether the branch is likely true.  We don't need
3030          to do a lot of this for unconditional branches.  */
3031
3032       insn_at_target = next_active_insn (target_label);
3033       own_target = own_thread_p (target_label, target_label, 0);
3034
3035       if (condition == const_true_rtx)
3036         {
3037           own_fallthrough = 0;
3038           fallthrough_insn = 0;
3039           prediction = 2;
3040         }
3041       else
3042         {
3043           fallthrough_insn = next_active_insn (insn);
3044           own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
3045           prediction = mostly_true_jump (insn, condition);
3046         }
3047
3048       /* If this insn is expected to branch, first try to get insns from our
3049          target, then our fallthrough insns.  If it is not expected to branch,
3050          try the other order.  */
3051
3052       if (prediction > 0)
3053         {
3054           delay_list
3055             = fill_slots_from_thread (insn, condition, insn_at_target,
3056                                       fallthrough_insn, prediction == 2, 1,
3057                                       own_target,
3058                                       slots_to_fill, &slots_filled, delay_list);
3059
3060           if (delay_list == 0 && own_fallthrough)
3061             {
3062               /* Even though we didn't find anything for delay slots,
3063                  we might have found a redundant insn which we deleted
3064                  from the thread that was filled.  So we have to recompute
3065                  the next insn at the target.  */
3066               target_label = JUMP_LABEL (insn);
3067               insn_at_target = next_active_insn (target_label);
3068
3069               delay_list
3070                 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3071                                           insn_at_target, 0, 0,
3072                                           own_fallthrough,
3073                                           slots_to_fill, &slots_filled,
3074                                           delay_list);
3075             }
3076         }
3077       else
3078         {
3079           if (own_fallthrough)
3080             delay_list
3081               = fill_slots_from_thread (insn, condition, fallthrough_insn,
3082                                         insn_at_target, 0, 0,
3083                                         own_fallthrough,
3084                                         slots_to_fill, &slots_filled,
3085                                         delay_list);
3086
3087           if (delay_list == 0)
3088             delay_list
3089               = fill_slots_from_thread (insn, condition, insn_at_target,
3090                                         next_active_insn (insn), 0, 1,
3091                                         own_target,
3092                                         slots_to_fill, &slots_filled,
3093                                         delay_list);
3094         }
3095
3096       if (delay_list)
3097         unfilled_slots_base[i]
3098           = emit_delay_sequence (insn, delay_list, slots_filled);
3099
3100       if (slots_to_fill == slots_filled)
3101         unfilled_slots_base[i] = 0;
3102
3103       note_delay_statistics (slots_filled, 1);
3104     }
3105 }
3106 \f
3107 /* Once we have tried two ways to fill a delay slot, make a pass over the
3108    code to try to improve the results and to do such things as more jump
3109    threading.  */
3110
3111 static void
3112 relax_delay_slots (first)
3113      rtx first;
3114 {
3115   rtx insn, next, pat;
3116   rtx trial, delay_insn, target_label;
3117
3118   /* Look at every JUMP_INSN and see if we can improve it.  */
3119   for (insn = first; insn; insn = next)
3120     {
3121       rtx other;
3122
3123       next = next_active_insn (insn);
3124
3125       /* If this is a jump insn, see if it now jumps to a jump, jumps to
3126          the next insn, or jumps to a label that is not the last of a
3127          group of consecutive labels.  */
3128       if (GET_CODE (insn) == JUMP_INSN
3129           && (condjump_p (insn) || condjump_in_parallel_p (insn))
3130           && (target_label = JUMP_LABEL (insn)) != 0)
3131         {
3132           target_label = follow_jumps (target_label);
3133           target_label = prev_label (next_active_insn (target_label));
3134
3135           if (target_label == 0)
3136             target_label = find_end_label ();
3137
3138           if (next_active_insn (target_label) == next
3139               && ! condjump_in_parallel_p (insn))
3140             {
3141               delete_jump (insn);
3142               continue;
3143             }
3144
3145           if (target_label != JUMP_LABEL (insn))
3146             reorg_redirect_jump (insn, target_label);
3147
3148           /* See if this jump branches around an unconditional jump.
3149              If so, invert this jump and point it to the target of the
3150              second jump.  */
3151           if (next && GET_CODE (next) == JUMP_INSN
3152               && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3153               && next_active_insn (target_label) == next_active_insn (next)
3154               && no_labels_between_p (insn, next))
3155             {
3156               rtx label = JUMP_LABEL (next);
3157
3158               /* Be careful how we do this to avoid deleting code or
3159                  labels that are momentarily dead.  See similar optimization
3160                  in jump.c.
3161
3162                  We also need to ensure we properly handle the case when
3163                  invert_jump fails.  */
3164
3165               ++LABEL_NUSES (target_label);
3166               if (label)
3167                 ++LABEL_NUSES (label);
3168
3169               if (invert_jump (insn, label, 1))
3170                 {
3171                   delete_related_insns (next);
3172                   next = insn;
3173                 }
3174
3175               if (label)
3176                 --LABEL_NUSES (label);
3177
3178               if (--LABEL_NUSES (target_label) == 0)
3179                 delete_related_insns (target_label);
3180
3181               continue;
3182             }
3183         }
3184
3185       /* If this is an unconditional jump and the previous insn is a
3186          conditional jump, try reversing the condition of the previous
3187          insn and swapping our targets.  The next pass might be able to
3188          fill the slots.
3189
3190          Don't do this if we expect the conditional branch to be true, because
3191          we would then be making the more common case longer.  */
3192
3193       if (GET_CODE (insn) == JUMP_INSN
3194           && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3195           && (other = prev_active_insn (insn)) != 0
3196           && (condjump_p (other) || condjump_in_parallel_p (other))
3197           && no_labels_between_p (other, insn)
3198           && 0 > mostly_true_jump (other,
3199                                    get_branch_condition (other,
3200                                                          JUMP_LABEL (other))))
3201         {
3202           rtx other_target = JUMP_LABEL (other);
3203           target_label = JUMP_LABEL (insn);
3204
3205           if (invert_jump (other, target_label, 0))
3206             reorg_redirect_jump (insn, other_target);
3207         }
3208
3209       /* Now look only at cases where we have filled a delay slot.  */
3210       if (GET_CODE (insn) != INSN
3211           || GET_CODE (PATTERN (insn)) != SEQUENCE)
3212         continue;
3213
3214       pat = PATTERN (insn);
3215       delay_insn = XVECEXP (pat, 0, 0);
3216
3217       /* See if the first insn in the delay slot is redundant with some
3218          previous insn.  Remove it from the delay slot if so; then set up
3219          to reprocess this insn.  */
3220       if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
3221         {
3222           delete_from_delay_slot (XVECEXP (pat, 0, 1));
3223           next = prev_active_insn (next);
3224           continue;
3225         }
3226
3227       /* See if we have a RETURN insn with a filled delay slot followed
3228          by a RETURN insn with an unfilled a delay slot.  If so, we can delete
3229          the first RETURN (but not it's delay insn).  This gives the same
3230          effect in fewer instructions.
3231
3232          Only do so if optimizing for size since this results in slower, but
3233          smaller code.  */
3234       if (optimize_size
3235           && GET_CODE (PATTERN (delay_insn)) == RETURN
3236           && next
3237           && GET_CODE (next) == JUMP_INSN
3238           && GET_CODE (PATTERN (next)) == RETURN)
3239         {
3240           rtx after;
3241           int i;
3242
3243           /* Delete the RETURN and just execute the delay list insns.
3244
3245              We do this by deleting the INSN containing the SEQUENCE, then
3246              re-emitting the insns separately, and then deleting the RETURN.
3247              This allows the count of the jump target to be properly
3248              decremented.  */
3249
3250           /* Clear the from target bit, since these insns are no longer
3251              in delay slots.  */
3252           for (i = 0; i < XVECLEN (pat, 0); i++)
3253             INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3254
3255           trial = PREV_INSN (insn);
3256           delete_related_insns (insn);
3257           if (GET_CODE (pat) != SEQUENCE)
3258             abort ();
3259           after = trial;
3260           for (i = 0; i < XVECLEN (pat, 0); i++)
3261             {
3262               rtx this_insn = XVECEXP (pat, 0, i);
3263               add_insn_after (this_insn, after);
3264               after = this_insn;
3265             }
3266           delete_scheduled_jump (delay_insn);
3267           continue;
3268         }
3269
3270       /* Now look only at the cases where we have a filled JUMP_INSN.  */
3271       if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3272           || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
3273                 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
3274         continue;
3275
3276       target_label = JUMP_LABEL (delay_insn);
3277
3278       if (target_label)
3279         {
3280           /* If this jump goes to another unconditional jump, thread it, but
3281              don't convert a jump into a RETURN here.  */
3282           trial = follow_jumps (target_label);
3283           /* We use next_real_insn instead of next_active_insn, so that
3284              the special USE insns emitted by reorg won't be ignored.
3285              If they are ignored, then they will get deleted if target_label
3286              is now unreachable, and that would cause mark_target_live_regs
3287              to fail.  */
3288           trial = prev_label (next_real_insn (trial));
3289           if (trial == 0 && target_label != 0)
3290             trial = find_end_label ();
3291
3292           if (trial != target_label
3293               && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
3294             {
3295               reorg_redirect_jump (delay_insn, trial);
3296               target_label = trial;
3297             }
3298
3299           /* If the first insn at TARGET_LABEL is redundant with a previous
3300              insn, redirect the jump to the following insn process again.  */
3301           trial = next_active_insn (target_label);
3302           if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3303               && redundant_insn (trial, insn, 0)
3304               && ! can_throw_internal (trial))
3305             {
3306               rtx tmp;
3307
3308               /* Figure out where to emit the special USE insn so we don't
3309                  later incorrectly compute register live/death info.  */
3310               tmp = next_active_insn (trial);
3311               if (tmp == 0)
3312                 tmp = find_end_label ();
3313
3314               /* Insert the special USE insn and update dataflow info.  */
3315               update_block (trial, tmp);
3316
3317               /* Now emit a label before the special USE insn, and
3318                  redirect our jump to the new label.  */
3319               target_label = get_label_before (PREV_INSN (tmp));
3320               reorg_redirect_jump (delay_insn, target_label);
3321               next = insn;
3322               continue;
3323             }
3324
3325           /* Similarly, if it is an unconditional jump with one insn in its
3326              delay list and that insn is redundant, thread the jump.  */
3327           if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3328               && XVECLEN (PATTERN (trial), 0) == 2
3329               && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3330               && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3331                   || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3332               && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3333             {
3334               target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3335               if (target_label == 0)
3336                 target_label = find_end_label ();
3337
3338               if (redirect_with_delay_slots_safe_p (delay_insn, target_label,
3339                                                     insn))
3340                 {
3341                   reorg_redirect_jump (delay_insn, target_label);
3342                   next = insn;
3343                   continue;
3344                 }
3345             }
3346         }
3347
3348       if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3349           && prev_active_insn (target_label) == insn
3350           && ! condjump_in_parallel_p (delay_insn)
3351 #ifdef HAVE_cc0
3352           /* If the last insn in the delay slot sets CC0 for some insn,
3353              various code assumes that it is in a delay slot.  We could
3354              put it back where it belonged and delete the register notes,
3355              but it doesn't seem worthwhile in this uncommon case.  */
3356           && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3357                               REG_CC_USER, NULL_RTX)
3358 #endif
3359           )
3360         {
3361           rtx after;
3362           int i;
3363
3364           /* All this insn does is execute its delay list and jump to the
3365              following insn.  So delete the jump and just execute the delay
3366              list insns.
3367
3368              We do this by deleting the INSN containing the SEQUENCE, then
3369              re-emitting the insns separately, and then deleting the jump.
3370              This allows the count of the jump target to be properly
3371              decremented.  */
3372
3373           /* Clear the from target bit, since these insns are no longer
3374              in delay slots.  */
3375           for (i = 0; i < XVECLEN (pat, 0); i++)
3376             INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3377
3378           trial = PREV_INSN (insn);
3379           delete_related_insns (insn);
3380           if (GET_CODE (pat) != SEQUENCE)
3381             abort ();
3382           after = trial;
3383           for (i = 0; i < XVECLEN (pat, 0); i++)
3384             {
3385               rtx this_insn = XVECEXP (pat, 0, i);
3386               add_insn_after (this_insn, after);
3387               after = this_insn;
3388             }
3389           delete_scheduled_jump (delay_insn);
3390           continue;
3391         }
3392
3393       /* See if this is an unconditional jump around a single insn which is
3394          identical to the one in its delay slot.  In this case, we can just
3395          delete the branch and the insn in its delay slot.  */
3396       if (next && GET_CODE (next) == INSN
3397           && prev_label (next_active_insn (next)) == target_label
3398           && simplejump_p (insn)
3399           && XVECLEN (pat, 0) == 2
3400           && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
3401         {
3402           delete_related_insns (insn);
3403           continue;
3404         }
3405
3406       /* See if this jump (with its delay slots) branches around another
3407          jump (without delay slots).  If so, invert this jump and point
3408          it to the target of the second jump.  We cannot do this for
3409          annulled jumps, though.  Again, don't convert a jump to a RETURN
3410          here.  */
3411       if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3412           && next && GET_CODE (next) == JUMP_INSN
3413           && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3414           && next_active_insn (target_label) == next_active_insn (next)
3415           && no_labels_between_p (insn, next))
3416         {
3417           rtx label = JUMP_LABEL (next);
3418           rtx old_label = JUMP_LABEL (delay_insn);
3419
3420           if (label == 0)
3421             label = find_end_label ();
3422
3423           /* find_end_label can generate a new label. Check this first.  */
3424           if (no_labels_between_p (insn, next)
3425               && redirect_with_delay_slots_safe_p (delay_insn, label, insn))
3426             {
3427               /* Be careful how we do this to avoid deleting code or labels
3428                  that are momentarily dead.  See similar optimization in
3429                  jump.c  */
3430               if (old_label)
3431                 ++LABEL_NUSES (old_label);
3432
3433               if (invert_jump (delay_insn, label, 1))
3434                 {
3435                   int i;
3436
3437                   /* Must update the INSN_FROM_TARGET_P bits now that
3438                      the branch is reversed, so that mark_target_live_regs
3439                      will handle the delay slot insn correctly.  */
3440                   for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
3441                     {
3442                       rtx slot = XVECEXP (PATTERN (insn), 0, i);
3443                       INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
3444                     }
3445
3446                   delete_related_insns (next);
3447                   next = insn;
3448                 }
3449
3450               if (old_label && --LABEL_NUSES (old_label) == 0)
3451                 delete_related_insns (old_label);
3452               continue;
3453             }
3454         }
3455
3456       /* If we own the thread opposite the way this insn branches, see if we
3457          can merge its delay slots with following insns.  */
3458       if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3459           && own_thread_p (NEXT_INSN (insn), 0, 1))
3460         try_merge_delay_insns (insn, next);
3461       else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3462                && own_thread_p (target_label, target_label, 0))
3463         try_merge_delay_insns (insn, next_active_insn (target_label));
3464
3465       /* If we get here, we haven't deleted INSN.  But we may have deleted
3466          NEXT, so recompute it.  */
3467       next = next_active_insn (insn);
3468     }
3469 }
3470 \f
3471 #ifdef HAVE_return
3472
3473 /* Look for filled jumps to the end of function label.  We can try to convert
3474    them into RETURN insns if the insns in the delay slot are valid for the
3475    RETURN as well.  */
3476
3477 static void
3478 make_return_insns (first)
3479      rtx first;
3480 {
3481   rtx insn, jump_insn, pat;
3482   rtx real_return_label = end_of_function_label;
3483   int slots, i;
3484
3485 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3486   /* If a previous pass filled delay slots in the epilogue, things get a
3487      bit more complicated, as those filler insns would generally (without
3488      data flow analysis) have to be executed after any existing branch
3489      delay slot filler insns.  It is also unknown whether such a
3490      transformation would actually be profitable.  Note that the existing
3491      code only cares for branches with (some) filled delay slots.  */
3492   if (current_function_epilogue_delay_list != NULL)
3493     return;
3494 #endif
3495
3496   /* See if there is a RETURN insn in the function other than the one we
3497      made for END_OF_FUNCTION_LABEL.  If so, set up anything we can't change
3498      into a RETURN to jump to it.  */
3499   for (insn = first; insn; insn = NEXT_INSN (insn))
3500     if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3501       {
3502         real_return_label = get_label_before (insn);
3503         break;
3504       }
3505
3506   /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3507      was equal to END_OF_FUNCTION_LABEL.  */
3508   LABEL_NUSES (real_return_label)++;
3509
3510   /* Clear the list of insns to fill so we can use it.  */
3511   obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3512
3513   for (insn = first; insn; insn = NEXT_INSN (insn))
3514     {
3515       int flags;
3516
3517       /* Only look at filled JUMP_INSNs that go to the end of function
3518          label.  */
3519       if (GET_CODE (insn) != INSN
3520           || GET_CODE (PATTERN (insn)) != SEQUENCE
3521           || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3522           || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3523         continue;
3524
3525       pat = PATTERN (insn);
3526       jump_insn = XVECEXP (pat, 0, 0);
3527
3528       /* If we can't make the jump into a RETURN, try to redirect it to the best
3529          RETURN and go on to the next insn.  */
3530       if (! reorg_redirect_jump (jump_insn, NULL_RTX))
3531         {
3532           /* Make sure redirecting the jump will not invalidate the delay
3533              slot insns.  */
3534           if (redirect_with_delay_slots_safe_p (jump_insn,
3535                                                 real_return_label,
3536                                                 insn))
3537             reorg_redirect_jump (jump_insn, real_return_label);
3538           continue;
3539         }
3540
3541       /* See if this RETURN can accept the insns current in its delay slot.
3542          It can if it has more or an equal number of slots and the contents
3543          of each is valid.  */
3544
3545       flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
3546       slots = num_delay_slots (jump_insn);
3547       if (slots >= XVECLEN (pat, 0) - 1)
3548         {
3549           for (i = 1; i < XVECLEN (pat, 0); i++)
3550             if (! (
3551 #ifdef ANNUL_IFFALSE_SLOTS
3552                    (INSN_ANNULLED_BRANCH_P (jump_insn)
3553                     && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3554                    ? eligible_for_annul_false (jump_insn, i - 1,
3555                                                XVECEXP (pat, 0, i), flags) :
3556 #endif
3557 #ifdef ANNUL_IFTRUE_SLOTS
3558                    (INSN_ANNULLED_BRANCH_P (jump_insn)
3559                     && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3560                    ? eligible_for_annul_true (jump_insn, i - 1,
3561                                               XVECEXP (pat, 0, i), flags) :
3562 #endif
3563                    eligible_for_delay (jump_insn, i - 1,
3564                                        XVECEXP (pat, 0, i), flags)))
3565               break;
3566         }
3567       else
3568         i = 0;
3569
3570       if (i == XVECLEN (pat, 0))
3571         continue;
3572
3573       /* We have to do something with this insn.  If it is an unconditional
3574          RETURN, delete the SEQUENCE and output the individual insns,
3575          followed by the RETURN.  Then set things up so we try to find
3576          insns for its delay slots, if it needs some.  */
3577       if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3578         {
3579           rtx prev = PREV_INSN (insn);
3580
3581           delete_related_insns (insn);
3582           for (i = 1; i < XVECLEN (pat, 0); i++)
3583             prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3584
3585           insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3586           emit_barrier_after (insn);
3587
3588           if (slots)
3589             obstack_ptr_grow (&unfilled_slots_obstack, insn);
3590         }
3591       else
3592         /* It is probably more efficient to keep this with its current
3593            delay slot as a branch to a RETURN.  */
3594         reorg_redirect_jump (jump_insn, real_return_label);
3595     }
3596
3597   /* Now delete REAL_RETURN_LABEL if we never used it.  Then try to fill any
3598      new delay slots we have created.  */
3599   if (--LABEL_NUSES (real_return_label) == 0)
3600     delete_related_insns (real_return_label);
3601
3602   fill_simple_delay_slots (1);
3603   fill_simple_delay_slots (0);
3604 }
3605 #endif
3606 \f
3607 /* Try to find insns to place in delay slots.  */
3608
3609 void
3610 dbr_schedule (first, file)
3611      rtx first;
3612      FILE *file;
3613 {
3614   rtx insn, next, epilogue_insn = 0;
3615   int i;
3616 #if 0
3617   int old_flag_no_peephole = flag_no_peephole;
3618
3619   /* Execute `final' once in prescan mode to delete any insns that won't be
3620      used.  Don't let final try to do any peephole optimization--it will
3621      ruin dataflow information for this pass.  */
3622
3623   flag_no_peephole = 1;
3624   final (first, 0, NO_DEBUG, 1, 1);
3625   flag_no_peephole = old_flag_no_peephole;
3626 #endif
3627
3628   /* If the current function has no insns other than the prologue and
3629      epilogue, then do not try to fill any delay slots.  */
3630   if (n_basic_blocks == 0)
3631     return;
3632
3633   /* Find the highest INSN_UID and allocate and initialize our map from
3634      INSN_UID's to position in code.  */
3635   for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3636     {
3637       if (INSN_UID (insn) > max_uid)
3638         max_uid = INSN_UID (insn);
3639       if (GET_CODE (insn) == NOTE
3640           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
3641         epilogue_insn = insn;
3642     }
3643
3644   uid_to_ruid = (int *) xmalloc ((max_uid + 1) * sizeof (int));
3645   for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3646     uid_to_ruid[INSN_UID (insn)] = i;
3647
3648   /* Initialize the list of insns that need filling.  */
3649   if (unfilled_firstobj == 0)
3650     {
3651       gcc_obstack_init (&unfilled_slots_obstack);
3652       unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3653     }
3654
3655   for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3656     {
3657       rtx target;
3658
3659       INSN_ANNULLED_BRANCH_P (insn) = 0;
3660       INSN_FROM_TARGET_P (insn) = 0;
3661
3662       /* Skip vector tables.  We can't get attributes for them.  */
3663       if (GET_CODE (insn) == JUMP_INSN
3664           && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3665               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3666         continue;
3667
3668       if (num_delay_slots (insn) > 0)
3669         obstack_ptr_grow (&unfilled_slots_obstack, insn);
3670
3671       /* Ensure all jumps go to the last of a set of consecutive labels.  */
3672       if (GET_CODE (insn) == JUMP_INSN
3673           && (condjump_p (insn) || condjump_in_parallel_p (insn))
3674           && JUMP_LABEL (insn) != 0
3675           && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
3676               != JUMP_LABEL (insn)))
3677         redirect_jump (insn, target, 1);
3678     }
3679
3680   init_resource_info (epilogue_insn);
3681
3682   /* Show we haven't computed an end-of-function label yet.  */
3683   end_of_function_label = 0;
3684
3685   /* Initialize the statistics for this function.  */
3686   memset ((char *) num_insns_needing_delays, 0, sizeof num_insns_needing_delays);
3687   memset ((char *) num_filled_delays, 0, sizeof num_filled_delays);
3688
3689   /* Now do the delay slot filling.  Try everything twice in case earlier
3690      changes make more slots fillable.  */
3691
3692   for (reorg_pass_number = 0;
3693        reorg_pass_number < MAX_REORG_PASSES;
3694        reorg_pass_number++)
3695     {
3696       fill_simple_delay_slots (1);
3697       fill_simple_delay_slots (0);
3698       fill_eager_delay_slots ();
3699       relax_delay_slots (first);
3700     }
3701
3702   /* Delete any USE insns made by update_block; subsequent passes don't need
3703      them or know how to deal with them.  */
3704   for (insn = first; insn; insn = next)
3705     {
3706       next = NEXT_INSN (insn);
3707
3708       if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3709           && INSN_P (XEXP (PATTERN (insn), 0)))
3710         next = delete_related_insns (insn);
3711     }
3712
3713   /* If we made an end of function label, indicate that it is now
3714      safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3715      If it is now unused, delete it.  */
3716   if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3717     delete_related_insns (end_of_function_label);
3718
3719 #ifdef HAVE_return
3720   if (HAVE_return && end_of_function_label != 0)
3721     make_return_insns (first);
3722 #endif
3723
3724   obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3725
3726   /* It is not clear why the line below is needed, but it does seem to be.  */
3727   unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3728
3729   if (file)
3730     {
3731       int i, j, need_comma;
3732       int total_delay_slots[MAX_DELAY_HISTOGRAM + 1];
3733       int total_annul_slots[MAX_DELAY_HISTOGRAM + 1];
3734
3735       for (reorg_pass_number = 0;
3736            reorg_pass_number < MAX_REORG_PASSES;
3737            reorg_pass_number++)
3738         {
3739           fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3740           for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3741             {
3742               need_comma = 0;
3743               fprintf (file, ";; Reorg function #%d\n", i);
3744
3745               fprintf (file, ";; %d insns needing delay slots\n;; ",
3746                        num_insns_needing_delays[i][reorg_pass_number]);
3747
3748               for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3749                 if (num_filled_delays[i][j][reorg_pass_number])
3750                   {
3751                     if (need_comma)
3752                       fprintf (file, ", ");
3753                     need_comma = 1;
3754                     fprintf (file, "%d got %d delays",
3755                              num_filled_delays[i][j][reorg_pass_number], j);
3756                   }
3757               fprintf (file, "\n");
3758             }
3759         }
3760       memset ((char *) total_delay_slots, 0, sizeof total_delay_slots);
3761       memset ((char *) total_annul_slots, 0, sizeof total_annul_slots);
3762       for (insn = first; insn; insn = NEXT_INSN (insn))
3763         {
3764           if (! INSN_DELETED_P (insn)
3765               && GET_CODE (insn) == INSN
3766               && GET_CODE (PATTERN (insn)) != USE
3767               && GET_CODE (PATTERN (insn)) != CLOBBER)
3768             {
3769               if (GET_CODE (PATTERN (insn)) == SEQUENCE)
3770                 {
3771                   j = XVECLEN (PATTERN (insn), 0) - 1;
3772                   if (j > MAX_DELAY_HISTOGRAM)
3773                     j = MAX_DELAY_HISTOGRAM;
3774                   if (INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (insn), 0, 0)))
3775                     total_annul_slots[j]++;
3776                   else
3777                     total_delay_slots[j]++;
3778                 }
3779               else if (num_delay_slots (insn) > 0)
3780                 total_delay_slots[0]++;
3781             }
3782         }
3783       fprintf (file, ";; Reorg totals: ");
3784       need_comma = 0;
3785       for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3786         {
3787           if (total_delay_slots[j])
3788             {
3789               if (need_comma)
3790                 fprintf (file, ", ");
3791               need_comma = 1;
3792               fprintf (file, "%d got %d delays", total_delay_slots[j], j);
3793             }
3794         }
3795       fprintf (file, "\n");
3796 #if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
3797       fprintf (file, ";; Reorg annuls: ");
3798       need_comma = 0;
3799       for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3800         {
3801           if (total_annul_slots[j])
3802             {
3803               if (need_comma)
3804                 fprintf (file, ", ");
3805               need_comma = 1;
3806               fprintf (file, "%d got %d delays", total_annul_slots[j], j);
3807             }
3808         }
3809       fprintf (file, "\n");
3810 #endif
3811       fprintf (file, "\n");
3812     }
3813
3814   /* For all JUMP insns, fill in branch prediction notes, so that during
3815      assembler output a target can set branch prediction bits in the code.
3816      We have to do this now, as up until this point the destinations of
3817      JUMPS can be moved around and changed, but past right here that cannot
3818      happen.  */
3819   for (insn = first; insn; insn = NEXT_INSN (insn))
3820     {
3821       int pred_flags;
3822
3823       if (GET_CODE (insn) == INSN)
3824         {
3825           rtx pat = PATTERN (insn);
3826
3827           if (GET_CODE (pat) == SEQUENCE)
3828             insn = XVECEXP (pat, 0, 0);
3829         }
3830       if (GET_CODE (insn) != JUMP_INSN)
3831         continue;
3832
3833       pred_flags = get_jump_flags (insn, JUMP_LABEL (insn));
3834       REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED,
3835                                             GEN_INT (pred_flags),
3836                                             REG_NOTES (insn));
3837     }
3838   free_resource_info ();
3839   free (uid_to_ruid);
3840 }
3841 #endif /* DELAY_SLOTS */