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