gcc/reorg.c

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