118334Speter/* Perform instruction reorganizations for delay slot filling.
290075Sobrien   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3169689Skan   1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
418334Speter   Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
518334Speter   Hacked by Michael Tiemann (tiemann@cygnus.com).
618334Speter
790075SobrienThis file is part of GCC.
818334Speter
990075SobrienGCC is free software; you can redistribute it and/or modify it under
1090075Sobrienthe terms of the GNU General Public License as published by the Free
1190075SobrienSoftware Foundation; either version 2, or (at your option) any later
1290075Sobrienversion.
1318334Speter
1490075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY
1590075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or
1690075SobrienFITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
1790075Sobrienfor more details.
1818334Speter
1918334SpeterYou should have received a copy of the GNU General Public License
2090075Sobrienalong with GCC; see the file COPYING.  If not, write to the Free
21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22169689Skan02110-1301, USA.  */
2318334Speter
2418334Speter/* Instruction reorganization pass.
2518334Speter
2618334Speter   This pass runs after register allocation and final jump
2718334Speter   optimization.  It should be the last pass to run before peephole.
2818334Speter   It serves primarily to fill delay slots of insns, typically branch
2918334Speter   and call insns.  Other insns typically involve more complicated
3018334Speter   interactions of data dependencies and resource constraints, and
3118334Speter   are better handled by scheduling before register allocation (by the
3218334Speter   function `schedule_insns').
3318334Speter
3418334Speter   The Branch Penalty is the number of extra cycles that are needed to
3518334Speter   execute a branch insn.  On an ideal machine, branches take a single
3618334Speter   cycle, and the Branch Penalty is 0.  Several RISC machines approach
3718334Speter   branch delays differently:
3818334Speter
39169689Skan   The MIPS has a single branch delay slot.  Most insns
4018334Speter   (except other branches) can be used to fill this slot.  When the
4118334Speter   slot is filled, two insns execute in two cycles, reducing the
4218334Speter   branch penalty to zero.
4318334Speter
4418334Speter   The SPARC always has a branch delay slot, but its effects can be
4518334Speter   annulled when the branch is not taken.  This means that failing to
4618334Speter   find other sources of insns, we can hoist an insn from the branch
4718334Speter   target that would only be safe to execute knowing that the branch
4818334Speter   is taken.
4918334Speter
5018334Speter   The HP-PA always has a branch delay slot.  For unconditional branches
5190075Sobrien   its effects can be annulled when the branch is taken.  The effects
5218334Speter   of the delay slot in a conditional branch can be nullified for forward
5318334Speter   taken branches, or for untaken backward branches.  This means
5418334Speter   we can hoist insns from the fall-through path for forward branches or
5518334Speter   steal insns from the target of backward branches.
5618334Speter
5752284Sobrien   The TMS320C3x and C4x have three branch delay slots.  When the three
5852284Sobrien   slots are filled, the branch penalty is zero.  Most insns can fill the
5952284Sobrien   delay slots except jump insns.
6052284Sobrien
6118334Speter   Three techniques for filling delay slots have been implemented so far:
6218334Speter
6318334Speter   (1) `fill_simple_delay_slots' is the simplest, most efficient way
6418334Speter   to fill delay slots.  This pass first looks for insns which come
6518334Speter   from before the branch and which are safe to execute after the
6618334Speter   branch.  Then it searches after the insn requiring delay slots or,
6718334Speter   in the case of a branch, for insns that are after the point at
6818334Speter   which the branch merges into the fallthrough code, if such a point
6918334Speter   exists.  When such insns are found, the branch penalty decreases
7018334Speter   and no code expansion takes place.
7118334Speter
7218334Speter   (2) `fill_eager_delay_slots' is more complicated: it is used for
7318334Speter   scheduling conditional jumps, or for scheduling jumps which cannot
7418334Speter   be filled using (1).  A machine need not have annulled jumps to use
7518334Speter   this strategy, but it helps (by keeping more options open).
7618334Speter   `fill_eager_delay_slots' tries to guess the direction the branch
7718334Speter   will go; if it guesses right 100% of the time, it can reduce the
7818334Speter   branch penalty as much as `fill_simple_delay_slots' does.  If it
79169689Skan   guesses wrong 100% of the time, it might as well schedule nops.  When
8018334Speter   `fill_eager_delay_slots' takes insns from the fall-through path of
8118334Speter   the jump, usually there is no code expansion; when it takes insns
8218334Speter   from the branch target, there is code expansion if it is not the
8318334Speter   only way to reach that target.
8418334Speter
8518334Speter   (3) `relax_delay_slots' uses a set of rules to simplify code that
8618334Speter   has been reorganized by (1) and (2).  It finds cases where
8718334Speter   conditional test can be eliminated, jumps can be threaded, extra
8818334Speter   insns can be eliminated, etc.  It is the job of (1) and (2) to do a
8918334Speter   good job of scheduling locally; `relax_delay_slots' takes care of
9018334Speter   making the various individual schedules work well together.  It is
9118334Speter   especially tuned to handle the control flow interactions of branch
9218334Speter   insns.  It does nothing for insns with delay slots that do not
9318334Speter   branch.
9418334Speter
9518334Speter   On machines that use CC0, we are very conservative.  We will not make
9618334Speter   a copy of an insn involving CC0 since we want to maintain a 1-1
9718334Speter   correspondence between the insn that sets and uses CC0.  The insns are
9818334Speter   allowed to be separated by placing an insn that sets CC0 (but not an insn
9918334Speter   that uses CC0; we could do this, but it doesn't seem worthwhile) in a
10018334Speter   delay slot.  In that case, we point each insn at the other with REG_CC_USER
10118334Speter   and REG_CC_SETTER notes.  Note that these restrictions affect very few
10218334Speter   machines because most RISC machines with delay slots will not use CC0
10318334Speter   (the RT is the only known exception at this point).
10418334Speter
10518334Speter   Not yet implemented:
10618334Speter
10718334Speter   The Acorn Risc Machine can conditionally execute most insns, so
10818334Speter   it is profitable to move single insns into a position to execute
10918334Speter   based on the condition code of the previous insn.
11018334Speter
11118334Speter   The HP-PA can conditionally nullify insns, providing a similar
11290075Sobrien   effect to the ARM, differing mostly in which insn is "in charge".  */
11318334Speter
11418334Speter#include "config.h"
11550397Sobrien#include "system.h"
116132718Skan#include "coretypes.h"
117132718Skan#include "tm.h"
11852284Sobrien#include "toplev.h"
11918334Speter#include "rtl.h"
12090075Sobrien#include "tm_p.h"
12150397Sobrien#include "expr.h"
12290075Sobrien#include "function.h"
12318334Speter#include "insn-config.h"
12418334Speter#include "conditions.h"
12518334Speter#include "hard-reg-set.h"
12618334Speter#include "basic-block.h"
12718334Speter#include "regs.h"
12818334Speter#include "recog.h"
12918334Speter#include "flags.h"
13018334Speter#include "output.h"
13118334Speter#include "obstack.h"
13218334Speter#include "insn-attr.h"
13352284Sobrien#include "resource.h"
13490075Sobrien#include "except.h"
13590075Sobrien#include "params.h"
136169689Skan#include "timevar.h"
137169689Skan#include "target.h"
138169689Skan#include "tree-pass.h"
13918334Speter
14018334Speter#ifdef DELAY_SLOTS
14118334Speter
14218334Speter#ifndef ANNUL_IFTRUE_SLOTS
14318334Speter#define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
14418334Speter#endif
14518334Speter#ifndef ANNUL_IFFALSE_SLOTS
14618334Speter#define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
14718334Speter#endif
14818334Speter
14918334Speter/* Insns which have delay slots that have not yet been filled.  */
15018334Speter
15118334Speterstatic struct obstack unfilled_slots_obstack;
15218334Speterstatic rtx *unfilled_firstobj;
15318334Speter
15418334Speter/* Define macros to refer to the first and last slot containing unfilled
15518334Speter   insns.  These are used because the list may move and its address
15618334Speter   should be recomputed at each use.  */
15718334Speter
15818334Speter#define unfilled_slots_base	\
15918334Speter  ((rtx *) obstack_base (&unfilled_slots_obstack))
16018334Speter
16118334Speter#define unfilled_slots_next	\
16218334Speter  ((rtx *) obstack_next_free (&unfilled_slots_obstack))
16318334Speter
16418334Speter/* Points to the label before the end of the function.  */
16518334Speterstatic rtx end_of_function_label;
16618334Speter
16718334Speter/* Mapping between INSN_UID's and position in the code since INSN_UID's do
16818334Speter   not always monotonically increase.  */
16918334Speterstatic int *uid_to_ruid;
17018334Speter
17118334Speter/* Highest valid index in `uid_to_ruid'.  */
17218334Speterstatic int max_uid;
17318334Speter
174132718Skanstatic int stop_search_p (rtx, int);
175132718Skanstatic int resource_conflicts_p (struct resources *, struct resources *);
176132718Skanstatic int insn_references_resource_p (rtx, struct resources *, int);
177132718Skanstatic int insn_sets_resource_p (rtx, struct resources *, int);
178132718Skanstatic rtx find_end_label (void);
179132718Skanstatic rtx emit_delay_sequence (rtx, rtx, int);
180132718Skanstatic rtx add_to_delay_list (rtx, rtx);
181132718Skanstatic rtx delete_from_delay_slot (rtx);
182132718Skanstatic void delete_scheduled_jump (rtx);
183132718Skanstatic void note_delay_statistics (int, int);
18490075Sobrien#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
185132718Skanstatic rtx optimize_skip (rtx);
18690075Sobrien#endif
187132718Skanstatic int get_jump_flags (rtx, rtx);
188132718Skanstatic int rare_destination (rtx);
189132718Skanstatic int mostly_true_jump (rtx, rtx);
190132718Skanstatic rtx get_branch_condition (rtx, rtx);
191132718Skanstatic int condition_dominates_p (rtx, rtx);
192132718Skanstatic int redirect_with_delay_slots_safe_p (rtx, rtx, rtx);
193132718Skanstatic int redirect_with_delay_list_safe_p (rtx, rtx, rtx);
194132718Skanstatic int check_annul_list_true_false (int, rtx);
195132718Skanstatic rtx steal_delay_list_from_target (rtx, rtx, rtx, rtx,
196132718Skan					 struct resources *,
197132718Skan					 struct resources *,
198132718Skan					 struct resources *,
199132718Skan					 int, int *, int *, rtx *);
200132718Skanstatic rtx steal_delay_list_from_fallthrough (rtx, rtx, rtx, rtx,
201132718Skan					      struct resources *,
202132718Skan					      struct resources *,
203132718Skan					      struct resources *,
204132718Skan					      int, int *, int *);
205132718Skanstatic void try_merge_delay_insns (rtx, rtx);
206132718Skanstatic rtx redundant_insn (rtx, rtx, rtx);
207132718Skanstatic int own_thread_p (rtx, rtx, int);
208132718Skanstatic void update_block (rtx, rtx);
209132718Skanstatic int reorg_redirect_jump (rtx, rtx);
210132718Skanstatic void update_reg_dead_notes (rtx, rtx);
211132718Skanstatic void fix_reg_dead_note (rtx, rtx);
212132718Skanstatic void update_reg_unused_notes (rtx, rtx);
213132718Skanstatic void fill_simple_delay_slots (int);
214132718Skanstatic rtx fill_slots_from_thread (rtx, rtx, rtx, rtx, int, int, int, int,
215132718Skan				   int *, rtx);
216132718Skanstatic void fill_eager_delay_slots (void);
217132718Skanstatic void relax_delay_slots (rtx);
21890075Sobrien#ifdef HAVE_return
219132718Skanstatic void make_return_insns (rtx);
22090075Sobrien#endif
22118334Speter
22218334Speter/* Return TRUE if this insn should stop the search for insn to fill delay
22318334Speter   slots.  LABELS_P indicates that labels should terminate the search.
22418334Speter   In all cases, jumps terminate the search.  */
22518334Speter
22618334Speterstatic int
227132718Skanstop_search_p (rtx insn, int labels_p)
22818334Speter{
22918334Speter  if (insn == 0)
23018334Speter    return 1;
23118334Speter
232122180Skan  /* If the insn can throw an exception that is caught within the function,
233122180Skan     it may effectively perform a jump from the viewpoint of the function.
234122180Skan     Therefore act like for a jump.  */
235122180Skan  if (can_throw_internal (insn))
236122180Skan    return 1;
237122180Skan
23818334Speter  switch (GET_CODE (insn))
23918334Speter    {
24018334Speter    case NOTE:
24118334Speter    case CALL_INSN:
24218334Speter      return 0;
24318334Speter
24418334Speter    case CODE_LABEL:
24518334Speter      return labels_p;
24618334Speter
24718334Speter    case JUMP_INSN:
24818334Speter    case BARRIER:
24918334Speter      return 1;
25018334Speter
25118334Speter    case INSN:
25218334Speter      /* OK unless it contains a delay slot or is an `asm' insn of some type.
25318334Speter	 We don't know anything about these.  */
25418334Speter      return (GET_CODE (PATTERN (insn)) == SEQUENCE
25518334Speter	      || GET_CODE (PATTERN (insn)) == ASM_INPUT
25618334Speter	      || asm_noperands (PATTERN (insn)) >= 0);
25718334Speter
25818334Speter    default:
259169689Skan      gcc_unreachable ();
26018334Speter    }
26118334Speter}
26218334Speter
26318334Speter/* Return TRUE if any resources are marked in both RES1 and RES2 or if either
26418334Speter   resource set contains a volatile memory reference.  Otherwise, return FALSE.  */
26518334Speter
26618334Speterstatic int
267132718Skanresource_conflicts_p (struct resources *res1, struct resources *res2)
26818334Speter{
26918334Speter  if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
27018334Speter      || (res1->unch_memory && res2->unch_memory)
27118334Speter      || res1->volatil || res2->volatil)
27218334Speter    return 1;
27318334Speter
27418334Speter#ifdef HARD_REG_SET
27518334Speter  return (res1->regs & res2->regs) != HARD_CONST (0);
27618334Speter#else
27718334Speter  {
27818334Speter    int i;
27918334Speter
28018334Speter    for (i = 0; i < HARD_REG_SET_LONGS; i++)
28118334Speter      if ((res1->regs[i] & res2->regs[i]) != 0)
28218334Speter	return 1;
28318334Speter    return 0;
28418334Speter  }
28518334Speter#endif
28618334Speter}
28718334Speter
28818334Speter/* Return TRUE if any resource marked in RES, a `struct resources', is
28950397Sobrien   referenced by INSN.  If INCLUDE_DELAYED_EFFECTS is set, return if the called
29018334Speter   routine is using those resources.
29118334Speter
29218334Speter   We compute this by computing all the resources referenced by INSN and
29318334Speter   seeing if this conflicts with RES.  It might be faster to directly check
29418334Speter   ourselves, and this is the way it used to work, but it means duplicating
29518334Speter   a large block of complex code.  */
29618334Speter
29718334Speterstatic int
298132718Skaninsn_references_resource_p (rtx insn, struct resources *res,
299132718Skan			    int include_delayed_effects)
30018334Speter{
30118334Speter  struct resources insn_res;
30218334Speter
30318334Speter  CLEAR_RESOURCE (&insn_res);
30418334Speter  mark_referenced_resources (insn, &insn_res, include_delayed_effects);
30518334Speter  return resource_conflicts_p (&insn_res, res);
30618334Speter}
30718334Speter
30818334Speter/* Return TRUE if INSN modifies resources that are marked in RES.
30950397Sobrien   INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
31018334Speter   included.   CC0 is only modified if it is explicitly set; see comments
31118334Speter   in front of mark_set_resources for details.  */
31218334Speter
31318334Speterstatic int
314132718Skaninsn_sets_resource_p (rtx insn, struct resources *res,
315132718Skan		      int include_delayed_effects)
31618334Speter{
31718334Speter  struct resources insn_sets;
31818334Speter
31918334Speter  CLEAR_RESOURCE (&insn_sets);
32018334Speter  mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
32118334Speter  return resource_conflicts_p (&insn_sets, res);
32218334Speter}
32318334Speter
324169689Skan/* Find a label at the end of the function or before a RETURN.  If there
325169689Skan   is none, try to make one.  If that fails, returns 0.
32618334Speter
327169689Skan   The property of such a label is that it is placed just before the
328169689Skan   epilogue or a bare RETURN insn, so that another bare RETURN can be
329169689Skan   turned into a jump to the label unconditionally.  In particular, the
330169689Skan   label cannot be placed before a RETURN insn with a filled delay slot.
331169689Skan
332169689Skan   ??? There may be a problem with the current implementation.  Suppose
333169689Skan   we start with a bare RETURN insn and call find_end_label.  It may set
334169689Skan   end_of_function_label just before the RETURN.  Suppose the machinery
335169689Skan   is able to fill the delay slot of the RETURN insn afterwards.  Then
336169689Skan   end_of_function_label is no longer valid according to the property
337169689Skan   described above and find_end_label will still return it unmodified.
338169689Skan   Note that this is probably mitigated by the following observation:
339169689Skan   once end_of_function_label is made, it is very likely the target of
340169689Skan   a jump, so filling the delay slot of the RETURN will be much more
341169689Skan   difficult.  */
342169689Skan
34318334Speterstatic rtx
344132718Skanfind_end_label (void)
34518334Speter{
34618334Speter  rtx insn;
34718334Speter
34818334Speter  /* If we found one previously, return it.  */
34918334Speter  if (end_of_function_label)
35018334Speter    return end_of_function_label;
35118334Speter
35218334Speter  /* Otherwise, see if there is a label at the end of the function.  If there
35318334Speter     is, it must be that RETURN insns aren't needed, so that is our return
35418334Speter     label and we don't have to do anything else.  */
35518334Speter
35618334Speter  insn = get_last_insn ();
357169689Skan  while (NOTE_P (insn)
358169689Skan	 || (NONJUMP_INSN_P (insn)
35918334Speter	     && (GET_CODE (PATTERN (insn)) == USE
36018334Speter		 || GET_CODE (PATTERN (insn)) == CLOBBER)))
36118334Speter    insn = PREV_INSN (insn);
36218334Speter
36390075Sobrien  /* When a target threads its epilogue we might already have a
36418334Speter     suitable return insn.  If so put a label before it for the
36518334Speter     end_of_function_label.  */
366169689Skan  if (BARRIER_P (insn)
367169689Skan      && JUMP_P (PREV_INSN (insn))
36818334Speter      && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
36918334Speter    {
37018334Speter      rtx temp = PREV_INSN (PREV_INSN (insn));
37118334Speter      end_of_function_label = gen_label_rtx ();
37218334Speter      LABEL_NUSES (end_of_function_label) = 0;
37318334Speter
374169689Skan      /* Put the label before an USE insns that may precede the RETURN insn.  */
37518334Speter      while (GET_CODE (temp) == USE)
37618334Speter	temp = PREV_INSN (temp);
37718334Speter
37818334Speter      emit_label_after (end_of_function_label, temp);
37918334Speter    }
38018334Speter
381169689Skan  else if (LABEL_P (insn))
38218334Speter    end_of_function_label = insn;
38318334Speter  else
38418334Speter    {
38518334Speter      end_of_function_label = gen_label_rtx ();
38618334Speter      LABEL_NUSES (end_of_function_label) = 0;
38790075Sobrien      /* If the basic block reorder pass moves the return insn to
38890075Sobrien	 some other place try to locate it again and put our
38990075Sobrien	 end_of_function_label there.  */
390169689Skan      while (insn && ! (JUMP_P (insn)
39190075Sobrien		        && (GET_CODE (PATTERN (insn)) == RETURN)))
39290075Sobrien	insn = PREV_INSN (insn);
39390075Sobrien      if (insn)
39418334Speter	{
39590075Sobrien	  insn = PREV_INSN (insn);
39690075Sobrien
39790075Sobrien	  /* Put the label before an USE insns that may proceed the
39890075Sobrien	     RETURN insn.  */
39990075Sobrien	  while (GET_CODE (insn) == USE)
40090075Sobrien	    insn = PREV_INSN (insn);
40190075Sobrien
40290075Sobrien	  emit_label_after (end_of_function_label, insn);
40318334Speter	}
40490075Sobrien      else
40590075Sobrien	{
406169689Skan#ifdef HAVE_epilogue
407169689Skan	  if (HAVE_epilogue
408169689Skan#ifdef HAVE_return
409169689Skan	      && ! HAVE_return
410169689Skan#endif
411169689Skan	      )
412169689Skan	    {
413169689Skan	      /* The RETURN insn has its delay slot filled so we cannot
414169689Skan		 emit the label just before it.  Since we already have
415169689Skan		 an epilogue and cannot emit a new RETURN, we cannot
416169689Skan		 emit the label at all.  */
417169689Skan	      end_of_function_label = NULL_RTX;
418169689Skan	      return end_of_function_label;
419169689Skan	    }
420169689Skan#endif /* HAVE_epilogue */
421169689Skan
42290075Sobrien	  /* Otherwise, make a new label and emit a RETURN and BARRIER,
42390075Sobrien	     if needed.  */
42490075Sobrien	  emit_label (end_of_function_label);
42590075Sobrien#ifdef HAVE_return
426169689Skan	  /* We don't bother trying to create a return insn if the
427169689Skan	     epilogue has filled delay-slots; we would have to try and
428169689Skan	     move the delay-slot fillers to the delay-slots for the new
429169689Skan	     return insn or in front of the new return insn.  */
430169689Skan	  if (current_function_epilogue_delay_list == NULL
431169689Skan	      && HAVE_return)
43290075Sobrien	    {
43390075Sobrien	      /* The return we make may have delay slots too.  */
43490075Sobrien	      rtx insn = gen_return ();
43590075Sobrien	      insn = emit_jump_insn (insn);
43690075Sobrien	      emit_barrier ();
43790075Sobrien	      if (num_delay_slots (insn) > 0)
43890075Sobrien		obstack_ptr_grow (&unfilled_slots_obstack, insn);
43990075Sobrien	    }
44018334Speter#endif
44190075Sobrien	}
44218334Speter    }
44318334Speter
44418334Speter  /* Show one additional use for this label so it won't go away until
44518334Speter     we are done.  */
44618334Speter  ++LABEL_NUSES (end_of_function_label);
44718334Speter
44818334Speter  return end_of_function_label;
44918334Speter}
45018334Speter
45118334Speter/* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
45218334Speter   the pattern of INSN with the SEQUENCE.
45318334Speter
45418334Speter   Chain the insns so that NEXT_INSN of each insn in the sequence points to
45518334Speter   the next and NEXT_INSN of the last insn in the sequence points to
45618334Speter   the first insn after the sequence.  Similarly for PREV_INSN.  This makes
45718334Speter   it easier to scan all insns.
45818334Speter
45918334Speter   Returns the SEQUENCE that replaces INSN.  */
46018334Speter
46118334Speterstatic rtx
462132718Skanemit_delay_sequence (rtx insn, rtx list, int length)
46318334Speter{
46490075Sobrien  int i = 1;
46590075Sobrien  rtx li;
46618334Speter  int had_barrier = 0;
46718334Speter
46850397Sobrien  /* Allocate the rtvec to hold the insns and the SEQUENCE.  */
46918334Speter  rtvec seqv = rtvec_alloc (length + 1);
47050397Sobrien  rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
47118334Speter  rtx seq_insn = make_insn_raw (seq);
47218334Speter  rtx first = get_insns ();
47318334Speter  rtx last = get_last_insn ();
47418334Speter
47550397Sobrien  /* Make a copy of the insn having delay slots.  */
47618334Speter  rtx delay_insn = copy_rtx (insn);
47718334Speter
47818334Speter  /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
47990075Sobrien     confuse further processing.  Update LAST in case it was the last insn.
48018334Speter     We will put the BARRIER back in later.  */
481169689Skan  if (NEXT_INSN (insn) && BARRIER_P (NEXT_INSN (insn)))
48218334Speter    {
48390075Sobrien      delete_related_insns (NEXT_INSN (insn));
48418334Speter      last = get_last_insn ();
48518334Speter      had_barrier = 1;
48618334Speter    }
48718334Speter
48818334Speter  /* Splice our SEQUENCE into the insn stream where INSN used to be.  */
48918334Speter  NEXT_INSN (seq_insn) = NEXT_INSN (insn);
49018334Speter  PREV_INSN (seq_insn) = PREV_INSN (insn);
49118334Speter
49250397Sobrien  if (insn != last)
49350397Sobrien    PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
49450397Sobrien
49550397Sobrien  if (insn != first)
49650397Sobrien    NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
49750397Sobrien
49850397Sobrien  /* Note the calls to set_new_first_and_last_insn must occur after
49950397Sobrien     SEQ_INSN has been completely spliced into the insn stream.
50050397Sobrien
50150397Sobrien     Otherwise CUR_INSN_UID will get set to an incorrect value because
50250397Sobrien     set_new_first_and_last_insn will not find SEQ_INSN in the chain.  */
50318334Speter  if (insn == last)
50418334Speter    set_new_first_and_last_insn (first, seq_insn);
50518334Speter
50618334Speter  if (insn == first)
50718334Speter    set_new_first_and_last_insn (seq_insn, last);
50818334Speter
50918334Speter  /* Build our SEQUENCE and rebuild the insn chain.  */
51018334Speter  XVECEXP (seq, 0, 0) = delay_insn;
51118334Speter  INSN_DELETED_P (delay_insn) = 0;
51218334Speter  PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
51318334Speter
51418334Speter  for (li = list; li; li = XEXP (li, 1), i++)
51518334Speter    {
51618334Speter      rtx tem = XEXP (li, 0);
51790075Sobrien      rtx note, next;
51818334Speter
51918334Speter      /* Show that this copy of the insn isn't deleted.  */
52018334Speter      INSN_DELETED_P (tem) = 0;
52118334Speter
52218334Speter      XVECEXP (seq, 0, i) = tem;
52318334Speter      PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
52418334Speter      NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
52518334Speter
526132718Skan      /* SPARC assembler, for instance, emit warning when debug info is output
527132718Skan         into the delay slot.  */
528132718Skan      if (INSN_LOCATOR (tem) && !INSN_LOCATOR (seq_insn))
529132718Skan	INSN_LOCATOR (seq_insn) = INSN_LOCATOR (tem);
530132718Skan      INSN_LOCATOR (tem) = 0;
531132718Skan
53290075Sobrien      for (note = REG_NOTES (tem); note; note = next)
53390075Sobrien	{
53490075Sobrien	  next = XEXP (note, 1);
53590075Sobrien	  switch (REG_NOTE_KIND (note))
53690075Sobrien	    {
53790075Sobrien	    case REG_DEAD:
53890075Sobrien	      /* Remove any REG_DEAD notes because we can't rely on them now
53990075Sobrien		 that the insn has been moved.  */
54090075Sobrien	      remove_note (tem, note);
54190075Sobrien	      break;
54290075Sobrien
54390075Sobrien	    case REG_LABEL:
54490075Sobrien	      /* Keep the label reference count up to date.  */
545169689Skan	      if (LABEL_P (XEXP (note, 0)))
54696263Sobrien		LABEL_NUSES (XEXP (note, 0)) ++;
54790075Sobrien	      break;
54890075Sobrien
54990075Sobrien	    default:
55090075Sobrien	      break;
55190075Sobrien	    }
55290075Sobrien	}
55318334Speter    }
55418334Speter
55518334Speter  NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
55618334Speter
55718334Speter  /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
55818334Speter     last insn in that SEQUENCE to point to us.  Similarly for the first
55918334Speter     insn in the following insn if it is a SEQUENCE.  */
56018334Speter
561169689Skan  if (PREV_INSN (seq_insn) && NONJUMP_INSN_P (PREV_INSN (seq_insn))
56218334Speter      && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
56318334Speter    NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
56418334Speter			XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
56518334Speter      = seq_insn;
56618334Speter
567169689Skan  if (NEXT_INSN (seq_insn) && NONJUMP_INSN_P (NEXT_INSN (seq_insn))
56818334Speter      && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
56918334Speter    PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
57090075Sobrien
57118334Speter  /* If there used to be a BARRIER, put it back.  */
57218334Speter  if (had_barrier)
57318334Speter    emit_barrier_after (seq_insn);
57418334Speter
575169689Skan  gcc_assert (i == length + 1);
57618334Speter
57718334Speter  return seq_insn;
57818334Speter}
57918334Speter
58018334Speter/* Add INSN to DELAY_LIST and return the head of the new list.  The list must
58118334Speter   be in the order in which the insns are to be executed.  */
58218334Speter
58318334Speterstatic rtx
584132718Skanadd_to_delay_list (rtx insn, rtx delay_list)
58518334Speter{
58618334Speter  /* If we have an empty list, just make a new list element.  If
58750397Sobrien     INSN has its block number recorded, clear it since we may
58818334Speter     be moving the insn to a new block.  */
58918334Speter
59018334Speter  if (delay_list == 0)
59118334Speter    {
59252284Sobrien      clear_hashed_info_for_insn (insn);
59350397Sobrien      return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
59418334Speter    }
59518334Speter
59618334Speter  /* Otherwise this must be an INSN_LIST.  Add INSN to the end of the
59718334Speter     list.  */
59818334Speter  XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
59918334Speter
60018334Speter  return delay_list;
60190075Sobrien}
60218334Speter
60352284Sobrien/* Delete INSN from the delay slot of the insn that it is in, which may
60452284Sobrien   produce an insn with no delay slots.  Return the new insn.  */
60518334Speter
60652284Sobrienstatic rtx
607132718Skandelete_from_delay_slot (rtx insn)
60818334Speter{
60918334Speter  rtx trial, seq_insn, seq, prev;
61018334Speter  rtx delay_list = 0;
61118334Speter  int i;
612169689Skan  int had_barrier = 0;
61318334Speter
61418334Speter  /* We first must find the insn containing the SEQUENCE with INSN in its
61518334Speter     delay slot.  Do this by finding an insn, TRIAL, where
61618334Speter     PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL.  */
61718334Speter
61818334Speter  for (trial = insn;
61918334Speter       PREV_INSN (NEXT_INSN (trial)) == trial;
62018334Speter       trial = NEXT_INSN (trial))
62118334Speter    ;
62218334Speter
62318334Speter  seq_insn = PREV_INSN (NEXT_INSN (trial));
62418334Speter  seq = PATTERN (seq_insn);
62518334Speter
626169689Skan  if (NEXT_INSN (seq_insn) && BARRIER_P (NEXT_INSN (seq_insn)))
627169689Skan    had_barrier = 1;
628169689Skan
62918334Speter  /* Create a delay list consisting of all the insns other than the one
63018334Speter     we are deleting (unless we were the only one).  */
63118334Speter  if (XVECLEN (seq, 0) > 2)
63218334Speter    for (i = 1; i < XVECLEN (seq, 0); i++)
63318334Speter      if (XVECEXP (seq, 0, i) != insn)
63418334Speter	delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
63518334Speter
63618334Speter  /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
63718334Speter     list, and rebuild the delay list if non-empty.  */
63818334Speter  prev = PREV_INSN (seq_insn);
63918334Speter  trial = XVECEXP (seq, 0, 0);
64090075Sobrien  delete_related_insns (seq_insn);
64118334Speter  add_insn_after (trial, prev);
64218334Speter
643169689Skan  /* If there was a barrier after the old SEQUENCE, remit it.  */
644169689Skan  if (had_barrier)
64518334Speter    emit_barrier_after (trial);
64618334Speter
64718334Speter  /* If there are any delay insns, remit them.  Otherwise clear the
64818334Speter     annul flag.  */
64918334Speter  if (delay_list)
65050397Sobrien    trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2);
651169689Skan  else if (INSN_P (trial))
65218334Speter    INSN_ANNULLED_BRANCH_P (trial) = 0;
65318334Speter
65418334Speter  INSN_FROM_TARGET_P (insn) = 0;
65518334Speter
65618334Speter  /* Show we need to fill this insn again.  */
65718334Speter  obstack_ptr_grow (&unfilled_slots_obstack, trial);
65852284Sobrien
65952284Sobrien  return trial;
66018334Speter}
66118334Speter
66218334Speter/* Delete INSN, a JUMP_INSN.  If it is a conditional jump, we must track down
66318334Speter   the insn that sets CC0 for it and delete it too.  */
66418334Speter
66518334Speterstatic void
666132718Skandelete_scheduled_jump (rtx insn)
66718334Speter{
66818334Speter  /* Delete the insn that sets cc0 for us.  On machines without cc0, we could
66918334Speter     delete the insn that sets the condition code, but it is hard to find it.
67018334Speter     Since this case is rare anyway, don't bother trying; there would likely
67118334Speter     be other insns that became dead anyway, which we wouldn't know to
67218334Speter     delete.  */
67318334Speter
67418334Speter#ifdef HAVE_cc0
67518334Speter  if (reg_mentioned_p (cc0_rtx, insn))
67618334Speter    {
67718334Speter      rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
67818334Speter
67918334Speter      /* If a reg-note was found, it points to an insn to set CC0.  This
68018334Speter	 insn is in the delay list of some other insn.  So delete it from
68118334Speter	 the delay list it was in.  */
68218334Speter      if (note)
68318334Speter	{
68418334Speter	  if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
68518334Speter	      && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
68618334Speter	    delete_from_delay_slot (XEXP (note, 0));
68718334Speter	}
68818334Speter      else
68918334Speter	{
69018334Speter	  /* The insn setting CC0 is our previous insn, but it may be in
69118334Speter	     a delay slot.  It will be the last insn in the delay slot, if
69218334Speter	     it is.  */
69318334Speter	  rtx trial = previous_insn (insn);
694169689Skan	  if (NOTE_P (trial))
69518334Speter	    trial = prev_nonnote_insn (trial);
69618334Speter	  if (sets_cc0_p (PATTERN (trial)) != 1
69790075Sobrien	      || FIND_REG_INC_NOTE (trial, NULL_RTX))
69818334Speter	    return;
69918334Speter	  if (PREV_INSN (NEXT_INSN (trial)) == trial)
70090075Sobrien	    delete_related_insns (trial);
70118334Speter	  else
70218334Speter	    delete_from_delay_slot (trial);
70318334Speter	}
70418334Speter    }
70518334Speter#endif
70618334Speter
70790075Sobrien  delete_related_insns (insn);
70818334Speter}
70918334Speter
71018334Speter/* Counters for delay-slot filling.  */
71118334Speter
71218334Speter#define NUM_REORG_FUNCTIONS 2
71318334Speter#define MAX_DELAY_HISTOGRAM 3
71418334Speter#define MAX_REORG_PASSES 2
71518334Speter
71618334Speterstatic int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
71718334Speter
71818334Speterstatic int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
71918334Speter
72018334Speterstatic int reorg_pass_number;
72118334Speter
72218334Speterstatic void
723132718Skannote_delay_statistics (int slots_filled, int index)
72418334Speter{
72518334Speter  num_insns_needing_delays[index][reorg_pass_number]++;
72618334Speter  if (slots_filled > MAX_DELAY_HISTOGRAM)
72718334Speter    slots_filled = MAX_DELAY_HISTOGRAM;
72818334Speter  num_filled_delays[index][slots_filled][reorg_pass_number]++;
72918334Speter}
73018334Speter
73118334Speter#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
73218334Speter
73318334Speter/* Optimize the following cases:
73418334Speter
73518334Speter   1.  When a conditional branch skips over only one instruction,
73618334Speter       use an annulling branch and put that insn in the delay slot.
73718334Speter       Use either a branch that annuls when the condition if true or
73818334Speter       invert the test with a branch that annuls when the condition is
73918334Speter       false.  This saves insns, since otherwise we must copy an insn
74018334Speter       from the L1 target.
74118334Speter
74218334Speter        (orig)		 (skip)		(otherwise)
74318334Speter	Bcc.n L1	Bcc',a L1	Bcc,a L1'
74418334Speter	insn		insn		insn2
74518334Speter      L1:	      L1:	      L1:
74618334Speter	insn2		insn2		insn2
74718334Speter	insn3		insn3	      L1':
74818334Speter					insn3
74918334Speter
75018334Speter   2.  When a conditional branch skips over only one instruction,
75118334Speter       and after that, it unconditionally branches somewhere else,
75218334Speter       perform the similar optimization. This saves executing the
75318334Speter       second branch in the case where the inverted condition is true.
75418334Speter
75518334Speter	Bcc.n L1	Bcc',a L2
75618334Speter	insn		insn
75718334Speter      L1:	      L1:
75818334Speter	Bra L2		Bra L2
75918334Speter
76018334Speter   INSN is a JUMP_INSN.
76118334Speter
76218334Speter   This should be expanded to skip over N insns, where N is the number
76318334Speter   of delay slots required.  */
76418334Speter
76518334Speterstatic rtx
766132718Skanoptimize_skip (rtx insn)
76718334Speter{
76890075Sobrien  rtx trial = next_nonnote_insn (insn);
76918334Speter  rtx next_trial = next_active_insn (trial);
77018334Speter  rtx delay_list = 0;
77118334Speter  int flags;
77218334Speter
77318334Speter  flags = get_jump_flags (insn, JUMP_LABEL (insn));
77418334Speter
77518334Speter  if (trial == 0
776169689Skan      || !NONJUMP_INSN_P (trial)
77718334Speter      || GET_CODE (PATTERN (trial)) == SEQUENCE
77818334Speter      || recog_memoized (trial) < 0
77918334Speter      || (! eligible_for_annul_false (insn, 0, trial, flags)
78096263Sobrien	  && ! eligible_for_annul_true (insn, 0, trial, flags))
78196263Sobrien      || can_throw_internal (trial))
78218334Speter    return 0;
78318334Speter
78418334Speter  /* There are two cases where we are just executing one insn (we assume
78518334Speter     here that a branch requires only one insn; this should be generalized
78618334Speter     at some point):  Where the branch goes around a single insn or where
78718334Speter     we have one insn followed by a branch to the same label we branch to.
78818334Speter     In both of these cases, inverting the jump and annulling the delay
78918334Speter     slot give the same effect in fewer insns.  */
79090075Sobrien  if ((next_trial == next_active_insn (JUMP_LABEL (insn))
79190075Sobrien       && ! (next_trial == 0 && current_function_epilogue_delay_list != 0))
79218334Speter      || (next_trial != 0
793169689Skan	  && JUMP_P (next_trial)
79418334Speter	  && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
79518334Speter	  && (simplejump_p (next_trial)
79618334Speter	      || GET_CODE (PATTERN (next_trial)) == RETURN)))
79718334Speter    {
79818334Speter      if (eligible_for_annul_false (insn, 0, trial, flags))
79918334Speter	{
80090075Sobrien	  if (invert_jump (insn, JUMP_LABEL (insn), 1))
80118334Speter	    INSN_FROM_TARGET_P (trial) = 1;
80218334Speter	  else if (! eligible_for_annul_true (insn, 0, trial, flags))
80318334Speter	    return 0;
80418334Speter	}
80518334Speter
80618334Speter      delay_list = add_to_delay_list (trial, NULL_RTX);
80718334Speter      next_trial = next_active_insn (trial);
80818334Speter      update_block (trial, trial);
80990075Sobrien      delete_related_insns (trial);
81018334Speter
81118334Speter      /* Also, if we are targeting an unconditional
81218334Speter	 branch, thread our jump to the target of that branch.  Don't
81318334Speter	 change this into a RETURN here, because it may not accept what
81418334Speter	 we have in the delay slot.  We'll fix this up later.  */
815169689Skan      if (next_trial && JUMP_P (next_trial)
81618334Speter	  && (simplejump_p (next_trial)
81718334Speter	      || GET_CODE (PATTERN (next_trial)) == RETURN))
81818334Speter	{
819169689Skan	  rtx target_label = JUMP_LABEL (next_trial);
82018334Speter	  if (target_label == 0)
82118334Speter	    target_label = find_end_label ();
82218334Speter
823169689Skan	  if (target_label)
824169689Skan	    {
825169689Skan	      /* Recompute the flags based on TARGET_LABEL since threading
826169689Skan		 the jump to TARGET_LABEL may change the direction of the
827169689Skan		 jump (which may change the circumstances in which the
828169689Skan		 delay slot is nullified).  */
829169689Skan	      flags = get_jump_flags (insn, target_label);
830169689Skan	      if (eligible_for_annul_true (insn, 0, trial, flags))
831169689Skan		reorg_redirect_jump (insn, target_label);
832169689Skan	    }
83318334Speter	}
83418334Speter
83518334Speter      INSN_ANNULLED_BRANCH_P (insn) = 1;
83618334Speter    }
83718334Speter
83818334Speter  return delay_list;
83918334Speter}
84018334Speter#endif
84118334Speter
84218334Speter/*  Encode and return branch direction and prediction information for
84318334Speter    INSN assuming it will jump to LABEL.
84418334Speter
84518334Speter    Non conditional branches return no direction information and
84618334Speter    are predicted as very likely taken.  */
84750397Sobrien
84818334Speterstatic int
849132718Skanget_jump_flags (rtx insn, rtx label)
85018334Speter{
85118334Speter  int flags;
85218334Speter
85318334Speter  /* get_jump_flags can be passed any insn with delay slots, these may
85418334Speter     be INSNs, CALL_INSNs, or JUMP_INSNs.  Only JUMP_INSNs have branch
85518334Speter     direction information, and only if they are conditional jumps.
85618334Speter
85718334Speter     If LABEL is zero, then there is no way to determine the branch
85818334Speter     direction.  */
859169689Skan  if (JUMP_P (insn)
86018334Speter      && (condjump_p (insn) || condjump_in_parallel_p (insn))
86118334Speter      && INSN_UID (insn) <= max_uid
86218334Speter      && label != 0
86318334Speter      && INSN_UID (label) <= max_uid)
86490075Sobrien    flags
86518334Speter      = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
86618334Speter	 ? ATTR_FLAG_forward : ATTR_FLAG_backward;
86718334Speter  /* No valid direction information.  */
86818334Speter  else
86918334Speter    flags = 0;
87090075Sobrien
87118334Speter  /* If insn is a conditional branch call mostly_true_jump to get
87290075Sobrien     determine the branch prediction.
87318334Speter
87418334Speter     Non conditional branches are predicted as very likely taken.  */
875169689Skan  if (JUMP_P (insn)
87618334Speter      && (condjump_p (insn) || condjump_in_parallel_p (insn)))
87718334Speter    {
87818334Speter      int prediction;
87918334Speter
88018334Speter      prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
88118334Speter      switch (prediction)
88218334Speter	{
88390075Sobrien	case 2:
88490075Sobrien	  flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
88590075Sobrien	  break;
88690075Sobrien	case 1:
88790075Sobrien	  flags |= ATTR_FLAG_likely;
88890075Sobrien	  break;
88990075Sobrien	case 0:
89090075Sobrien	  flags |= ATTR_FLAG_unlikely;
89190075Sobrien	  break;
89290075Sobrien	case -1:
89390075Sobrien	  flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
89490075Sobrien	  break;
89518334Speter
89690075Sobrien	default:
897169689Skan	  gcc_unreachable ();
89818334Speter	}
89918334Speter    }
90018334Speter  else
90118334Speter    flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
90218334Speter
90318334Speter  return flags;
90418334Speter}
90518334Speter
90618334Speter/* Return 1 if INSN is a destination that will be branched to rarely (the
90718334Speter   return point of a function); return 2 if DEST will be branched to very
90818334Speter   rarely (a call to a function that doesn't return).  Otherwise,
90918334Speter   return 0.  */
91018334Speter
91118334Speterstatic int
912132718Skanrare_destination (rtx insn)
91318334Speter{
91418334Speter  int jump_count = 0;
91518334Speter  rtx next;
91618334Speter
91718334Speter  for (; insn; insn = next)
91818334Speter    {
919169689Skan      if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
92018334Speter	insn = XVECEXP (PATTERN (insn), 0, 0);
92118334Speter
92218334Speter      next = NEXT_INSN (insn);
92318334Speter
92418334Speter      switch (GET_CODE (insn))
92518334Speter	{
92618334Speter	case CODE_LABEL:
92718334Speter	  return 0;
92818334Speter	case BARRIER:
92990075Sobrien	  /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN.  We
93018334Speter	     don't scan past JUMP_INSNs, so any barrier we find here must
93118334Speter	     have been after a CALL_INSN and hence mean the call doesn't
93218334Speter	     return.  */
93318334Speter	  return 2;
93418334Speter	case JUMP_INSN:
93518334Speter	  if (GET_CODE (PATTERN (insn)) == RETURN)
93618334Speter	    return 1;
93718334Speter	  else if (simplejump_p (insn)
93818334Speter		   && jump_count++ < 10)
93918334Speter	    next = JUMP_LABEL (insn);
94018334Speter	  else
94118334Speter	    return 0;
94250397Sobrien
94350397Sobrien	default:
94450397Sobrien	  break;
94518334Speter	}
94618334Speter    }
94718334Speter
94818334Speter  /* If we got here it means we hit the end of the function.  So this
94918334Speter     is an unlikely destination.  */
95018334Speter
95118334Speter  return 1;
95218334Speter}
95318334Speter
95418334Speter/* Return truth value of the statement that this branch
95518334Speter   is mostly taken.  If we think that the branch is extremely likely
95618334Speter   to be taken, we return 2.  If the branch is slightly more likely to be
95718334Speter   taken, return 1.  If the branch is slightly less likely to be taken,
95818334Speter   return 0 and if the branch is highly unlikely to be taken, return -1.
95918334Speter
960117395Skan   CONDITION, if nonzero, is the condition that JUMP_INSN is testing.  */
96118334Speter
96218334Speterstatic int
963132718Skanmostly_true_jump (rtx jump_insn, rtx condition)
96418334Speter{
96518334Speter  rtx target_label = JUMP_LABEL (jump_insn);
966169689Skan  rtx note;
967169689Skan  int rare_dest, rare_fallthrough;
96818334Speter
96950397Sobrien  /* If branch probabilities are available, then use that number since it
97050397Sobrien     always gives a correct answer.  */
97190075Sobrien  note = find_reg_note (jump_insn, REG_BR_PROB, 0);
97290075Sobrien  if (note)
97350397Sobrien    {
97490075Sobrien      int prob = INTVAL (XEXP (note, 0));
97550397Sobrien
97690075Sobrien      if (prob >= REG_BR_PROB_BASE * 9 / 10)
97790075Sobrien	return 2;
97890075Sobrien      else if (prob >= REG_BR_PROB_BASE / 2)
97990075Sobrien	return 1;
98090075Sobrien      else if (prob >= REG_BR_PROB_BASE / 10)
98190075Sobrien	return 0;
98290075Sobrien      else
98390075Sobrien	return -1;
98450397Sobrien    }
98550397Sobrien
98618334Speter  /* Look at the relative rarities of the fallthrough and destination.  If
98750397Sobrien     they differ, we can predict the branch that way.  */
988169689Skan  rare_dest = rare_destination (target_label);
989169689Skan  rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
99018334Speter
99118334Speter  switch (rare_fallthrough - rare_dest)
99218334Speter    {
99318334Speter    case -2:
99418334Speter      return -1;
99518334Speter    case -1:
99618334Speter      return 0;
99718334Speter    case 0:
99818334Speter      break;
99918334Speter    case 1:
100018334Speter      return 1;
100118334Speter    case 2:
100218334Speter      return 2;
100318334Speter    }
100418334Speter
100590075Sobrien  /* If we couldn't figure out what this jump was, assume it won't be
100618334Speter     taken.  This should be rare.  */
100718334Speter  if (condition == 0)
100818334Speter    return 0;
100918334Speter
101018334Speter  /* Predict backward branches usually take, forward branches usually not.  If
101118334Speter     we don't know whether this is forward or backward, assume the branch
101218334Speter     will be taken, since most are.  */
101318334Speter  return (target_label == 0 || INSN_UID (jump_insn) > max_uid
101418334Speter	  || INSN_UID (target_label) > max_uid
101518334Speter	  || (uid_to_ruid[INSN_UID (jump_insn)]
101690075Sobrien	      > uid_to_ruid[INSN_UID (target_label)]));
101718334Speter}
101818334Speter
101918334Speter/* Return the condition under which INSN will branch to TARGET.  If TARGET
102018334Speter   is zero, return the condition under which INSN will return.  If INSN is
102118334Speter   an unconditional branch, return const_true_rtx.  If INSN isn't a simple
102218334Speter   type of jump, or it doesn't go to TARGET, return 0.  */
102318334Speter
102418334Speterstatic rtx
1025132718Skanget_branch_condition (rtx insn, rtx target)
102618334Speter{
102718334Speter  rtx pat = PATTERN (insn);
102818334Speter  rtx src;
102990075Sobrien
103018334Speter  if (condjump_in_parallel_p (insn))
103118334Speter    pat = XVECEXP (pat, 0, 0);
103218334Speter
103318334Speter  if (GET_CODE (pat) == RETURN)
103418334Speter    return target == 0 ? const_true_rtx : 0;
103518334Speter
103618334Speter  else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
103718334Speter    return 0;
103818334Speter
103918334Speter  src = SET_SRC (pat);
104018334Speter  if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
104118334Speter    return const_true_rtx;
104218334Speter
104318334Speter  else if (GET_CODE (src) == IF_THEN_ELSE
104418334Speter	   && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
104518334Speter	       || (GET_CODE (XEXP (src, 1)) == LABEL_REF
104618334Speter		   && XEXP (XEXP (src, 1), 0) == target))
104718334Speter	   && XEXP (src, 2) == pc_rtx)
104818334Speter    return XEXP (src, 0);
104918334Speter
105018334Speter  else if (GET_CODE (src) == IF_THEN_ELSE
105118334Speter	   && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
105218334Speter	       || (GET_CODE (XEXP (src, 2)) == LABEL_REF
105318334Speter		   && XEXP (XEXP (src, 2), 0) == target))
105418334Speter	   && XEXP (src, 1) == pc_rtx)
105596263Sobrien    {
105696263Sobrien      enum rtx_code rev;
105796263Sobrien      rev = reversed_comparison_code (XEXP (src, 0), insn);
105896263Sobrien      if (rev != UNKNOWN)
105996263Sobrien	return gen_rtx_fmt_ee (rev, GET_MODE (XEXP (src, 0)),
106096263Sobrien			       XEXP (XEXP (src, 0), 0),
106196263Sobrien			       XEXP (XEXP (src, 0), 1));
106296263Sobrien    }
106318334Speter
106418334Speter  return 0;
106518334Speter}
106618334Speter
1067117395Skan/* Return nonzero if CONDITION is more strict than the condition of
106818334Speter   INSN, i.e., if INSN will always branch if CONDITION is true.  */
106918334Speter
107018334Speterstatic int
1071132718Skancondition_dominates_p (rtx condition, rtx insn)
107218334Speter{
107318334Speter  rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
107418334Speter  enum rtx_code code = GET_CODE (condition);
107518334Speter  enum rtx_code other_code;
107618334Speter
107718334Speter  if (rtx_equal_p (condition, other_condition)
107818334Speter      || other_condition == const_true_rtx)
107918334Speter    return 1;
108018334Speter
108118334Speter  else if (condition == const_true_rtx || other_condition == 0)
108218334Speter    return 0;
108318334Speter
108418334Speter  other_code = GET_CODE (other_condition);
108518334Speter  if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
108618334Speter      || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
108718334Speter      || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
108818334Speter    return 0;
108918334Speter
109018334Speter  return comparison_dominates_p (code, other_code);
109118334Speter}
109218334Speter
1093117395Skan/* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
109418334Speter   any insns already in the delay slot of JUMP.  */
109518334Speter
109618334Speterstatic int
1097132718Skanredirect_with_delay_slots_safe_p (rtx jump, rtx newlabel, rtx seq)
109818334Speter{
109950397Sobrien  int flags, i;
110018334Speter  rtx pat = PATTERN (seq);
110118334Speter
110218334Speter  /* Make sure all the delay slots of this jump would still
110318334Speter     be valid after threading the jump.  If they are still
1104117395Skan     valid, then return nonzero.  */
110518334Speter
110618334Speter  flags = get_jump_flags (jump, newlabel);
110718334Speter  for (i = 1; i < XVECLEN (pat, 0); i++)
110818334Speter    if (! (
110918334Speter#ifdef ANNUL_IFFALSE_SLOTS
111018334Speter	   (INSN_ANNULLED_BRANCH_P (jump)
111118334Speter	    && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
111218334Speter	   ? eligible_for_annul_false (jump, i - 1,
111318334Speter				       XVECEXP (pat, 0, i), flags) :
111418334Speter#endif
111518334Speter#ifdef ANNUL_IFTRUE_SLOTS
111618334Speter	   (INSN_ANNULLED_BRANCH_P (jump)
111718334Speter	    && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
111818334Speter	   ? eligible_for_annul_true (jump, i - 1,
111918334Speter				      XVECEXP (pat, 0, i), flags) :
112018334Speter#endif
112190075Sobrien	   eligible_for_delay (jump, i - 1, XVECEXP (pat, 0, i), flags)))
112218334Speter      break;
112318334Speter
112418334Speter  return (i == XVECLEN (pat, 0));
112518334Speter}
112618334Speter
1127117395Skan/* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
112818334Speter   any insns we wish to place in the delay slot of JUMP.  */
112918334Speter
113018334Speterstatic int
1131132718Skanredirect_with_delay_list_safe_p (rtx jump, rtx newlabel, rtx delay_list)
113218334Speter{
113318334Speter  int flags, i;
113418334Speter  rtx li;
113518334Speter
113618334Speter  /* Make sure all the insns in DELAY_LIST would still be
113718334Speter     valid after threading the jump.  If they are still
1138117395Skan     valid, then return nonzero.  */
113918334Speter
114018334Speter  flags = get_jump_flags (jump, newlabel);
114118334Speter  for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++)
114218334Speter    if (! (
114318334Speter#ifdef ANNUL_IFFALSE_SLOTS
114418334Speter	   (INSN_ANNULLED_BRANCH_P (jump)
114518334Speter	    && INSN_FROM_TARGET_P (XEXP (li, 0)))
114618334Speter	   ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) :
114718334Speter#endif
114818334Speter#ifdef ANNUL_IFTRUE_SLOTS
114918334Speter	   (INSN_ANNULLED_BRANCH_P (jump)
115018334Speter	    && ! INSN_FROM_TARGET_P (XEXP (li, 0)))
115118334Speter	   ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) :
115218334Speter#endif
115318334Speter	   eligible_for_delay (jump, i, XEXP (li, 0), flags)))
115418334Speter      break;
115518334Speter
115618334Speter  return (li == NULL);
115718334Speter}
115818334Speter
115952284Sobrien/* DELAY_LIST is a list of insns that have already been placed into delay
116052284Sobrien   slots.  See if all of them have the same annulling status as ANNUL_TRUE_P.
116152284Sobrien   If not, return 0; otherwise return 1.  */
116252284Sobrien
116352284Sobrienstatic int
1164132718Skancheck_annul_list_true_false (int annul_true_p, rtx delay_list)
116552284Sobrien{
116652284Sobrien  rtx temp;
116752284Sobrien
116852284Sobrien  if (delay_list)
116952284Sobrien    {
117052284Sobrien      for (temp = delay_list; temp; temp = XEXP (temp, 1))
117190075Sobrien	{
117290075Sobrien	  rtx trial = XEXP (temp, 0);
117390075Sobrien
117490075Sobrien	  if ((annul_true_p && INSN_FROM_TARGET_P (trial))
117552284Sobrien	      || (!annul_true_p && !INSN_FROM_TARGET_P (trial)))
117652284Sobrien	    return 0;
117790075Sobrien	}
117852284Sobrien    }
117952284Sobrien
118052284Sobrien  return 1;
118152284Sobrien}
118218334Speter
118318334Speter/* INSN branches to an insn whose pattern SEQ is a SEQUENCE.  Given that
118418334Speter   the condition tested by INSN is CONDITION and the resources shown in
118518334Speter   OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
118618334Speter   from SEQ's delay list, in addition to whatever insns it may execute
118718334Speter   (in DELAY_LIST).   SETS and NEEDED are denote resources already set and
118818334Speter   needed while searching for delay slot insns.  Return the concatenated
118918334Speter   delay list if possible, otherwise, return 0.
119018334Speter
119118334Speter   SLOTS_TO_FILL is the total number of slots required by INSN, and
119218334Speter   PSLOTS_FILLED points to the number filled so far (also the number of
119318334Speter   insns in DELAY_LIST).  It is updated with the number that have been
119418334Speter   filled from the SEQUENCE, if any.
119518334Speter
1196117395Skan   PANNUL_P points to a nonzero value if we already know that we need
119718334Speter   to annul INSN.  If this routine determines that annulling is needed,
1198117395Skan   it may set that value nonzero.
119918334Speter
120018334Speter   PNEW_THREAD points to a location that is to receive the place at which
120118334Speter   execution should continue.  */
120218334Speter
120318334Speterstatic rtx
1204132718Skansteal_delay_list_from_target (rtx insn, rtx condition, rtx seq,
1205132718Skan			      rtx delay_list, struct resources *sets,
1206132718Skan			      struct resources *needed,
1207132718Skan			      struct resources *other_needed,
1208132718Skan			      int slots_to_fill, int *pslots_filled,
1209132718Skan			      int *pannul_p, rtx *pnew_thread)
121018334Speter{
121118334Speter  rtx temp;
121218334Speter  int slots_remaining = slots_to_fill - *pslots_filled;
121318334Speter  int total_slots_filled = *pslots_filled;
121418334Speter  rtx new_delay_list = 0;
121518334Speter  int must_annul = *pannul_p;
121652284Sobrien  int used_annul = 0;
121718334Speter  int i;
121852284Sobrien  struct resources cc_set;
121918334Speter
122018334Speter  /* We can't do anything if there are more delay slots in SEQ than we
122118334Speter     can handle, or if we don't know that it will be a taken branch.
122218334Speter     We know that it will be a taken branch if it is either an unconditional
122318334Speter     branch or a conditional branch with a stricter branch condition.
122418334Speter
122518334Speter     Also, exit if the branch has more than one set, since then it is computing
122618334Speter     other results that can't be ignored, e.g. the HPPA mov&branch instruction.
122718334Speter     ??? It may be possible to move other sets into INSN in addition to
122852284Sobrien     moving the instructions in the delay slots.
122918334Speter
123052284Sobrien     We can not steal the delay list if one of the instructions in the
123190075Sobrien     current delay_list modifies the condition codes and the jump in the
123252284Sobrien     sequence is a conditional jump. We can not do this because we can
123352284Sobrien     not change the direction of the jump because the condition codes
123490075Sobrien     will effect the direction of the jump in the sequence.  */
123552284Sobrien
123652284Sobrien  CLEAR_RESOURCE (&cc_set);
123752284Sobrien  for (temp = delay_list; temp; temp = XEXP (temp, 1))
123852284Sobrien    {
123952284Sobrien      rtx trial = XEXP (temp, 0);
124052284Sobrien
124190075Sobrien      mark_set_resources (trial, &cc_set, 0, MARK_SRC_DEST_CALL);
124252284Sobrien      if (insn_references_resource_p (XVECEXP (seq , 0, 0), &cc_set, 0))
124390075Sobrien	return delay_list;
124452284Sobrien    }
124552284Sobrien
124618334Speter  if (XVECLEN (seq, 0) - 1 > slots_remaining
124718334Speter      || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))
124818334Speter      || ! single_set (XVECEXP (seq, 0, 0)))
124918334Speter    return delay_list;
125018334Speter
125190075Sobrien#ifdef MD_CAN_REDIRECT_BRANCH
125290075Sobrien  /* On some targets, branches with delay slots can have a limited
125390075Sobrien     displacement.  Give the back end a chance to tell us we can't do
125490075Sobrien     this.  */
125590075Sobrien  if (! MD_CAN_REDIRECT_BRANCH (insn, XVECEXP (seq, 0, 0)))
125690075Sobrien    return delay_list;
125790075Sobrien#endif
125890075Sobrien
125918334Speter  for (i = 1; i < XVECLEN (seq, 0); i++)
126018334Speter    {
126118334Speter      rtx trial = XVECEXP (seq, 0, i);
126218334Speter      int flags;
126318334Speter
126418334Speter      if (insn_references_resource_p (trial, sets, 0)
126518334Speter	  || insn_sets_resource_p (trial, needed, 0)
126618334Speter	  || insn_sets_resource_p (trial, sets, 0)
126718334Speter#ifdef HAVE_cc0
126818334Speter	  /* If TRIAL sets CC0, we can't copy it, so we can't steal this
126918334Speter	     delay list.  */
127018334Speter	  || find_reg_note (trial, REG_CC_USER, NULL_RTX)
127118334Speter#endif
127218334Speter	  /* If TRIAL is from the fallthrough code of an annulled branch insn
127318334Speter	     in SEQ, we cannot use it.  */
127418334Speter	  || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
127518334Speter	      && ! INSN_FROM_TARGET_P (trial)))
127618334Speter	return delay_list;
127718334Speter
127818334Speter      /* If this insn was already done (usually in a previous delay slot),
127918334Speter	 pretend we put it in our delay slot.  */
128018334Speter      if (redundant_insn (trial, insn, new_delay_list))
128118334Speter	continue;
128218334Speter
128318334Speter      /* We will end up re-vectoring this branch, so compute flags
128418334Speter	 based on jumping to the new label.  */
128518334Speter      flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
128618334Speter
128718334Speter      if (! must_annul
128818334Speter	  && ((condition == const_true_rtx
128918334Speter	       || (! insn_sets_resource_p (trial, other_needed, 0)
1290169689Skan		   && ! may_trap_or_fault_p (PATTERN (trial)))))
129118334Speter	  ? eligible_for_delay (insn, total_slots_filled, trial, flags)
129252284Sobrien	  : (must_annul || (delay_list == NULL && new_delay_list == NULL))
129352284Sobrien	     && (must_annul = 1,
129452284Sobrien	         check_annul_list_true_false (0, delay_list)
129552284Sobrien	         && check_annul_list_true_false (0, new_delay_list)
129652284Sobrien	         && eligible_for_annul_false (insn, total_slots_filled,
129752284Sobrien					      trial, flags)))
129818334Speter	{
129952284Sobrien	  if (must_annul)
130052284Sobrien	    used_annul = 1;
130118334Speter	  temp = copy_rtx (trial);
130218334Speter	  INSN_FROM_TARGET_P (temp) = 1;
130318334Speter	  new_delay_list = add_to_delay_list (temp, new_delay_list);
130418334Speter	  total_slots_filled++;
130518334Speter
130618334Speter	  if (--slots_remaining == 0)
130718334Speter	    break;
130818334Speter	}
130918334Speter      else
131018334Speter	return delay_list;
131118334Speter    }
131218334Speter
131318334Speter  /* Show the place to which we will be branching.  */
131418334Speter  *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
131518334Speter
131618334Speter  /* Add any new insns to the delay list and update the count of the
131718334Speter     number of slots filled.  */
131818334Speter  *pslots_filled = total_slots_filled;
131952284Sobrien  if (used_annul)
132052284Sobrien    *pannul_p = 1;
132118334Speter
132218334Speter  if (delay_list == 0)
132318334Speter    return new_delay_list;
132418334Speter
132518334Speter  for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
132618334Speter    delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
132718334Speter
132818334Speter  return delay_list;
132918334Speter}
133018334Speter
133190075Sobrien/* Similar to steal_delay_list_from_target except that SEQ is on the
133218334Speter   fallthrough path of INSN.  Here we only do something if the delay insn
133318334Speter   of SEQ is an unconditional branch.  In that case we steal its delay slot
133418334Speter   for INSN since unconditional branches are much easier to fill.  */
133518334Speter
133618334Speterstatic rtx
1337132718Skansteal_delay_list_from_fallthrough (rtx insn, rtx condition, rtx seq,
1338132718Skan				   rtx delay_list, struct resources *sets,
1339132718Skan				   struct resources *needed,
1340132718Skan				   struct resources *other_needed,
1341132718Skan				   int slots_to_fill, int *pslots_filled,
1342132718Skan				   int *pannul_p)
134318334Speter{
134418334Speter  int i;
134518334Speter  int flags;
134652284Sobrien  int must_annul = *pannul_p;
134752284Sobrien  int used_annul = 0;
134818334Speter
134918334Speter  flags = get_jump_flags (insn, JUMP_LABEL (insn));
135018334Speter
135118334Speter  /* We can't do anything if SEQ's delay insn isn't an
135218334Speter     unconditional branch.  */
135318334Speter
135418334Speter  if (! simplejump_p (XVECEXP (seq, 0, 0))
135518334Speter      && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
135618334Speter    return delay_list;
135718334Speter
135818334Speter  for (i = 1; i < XVECLEN (seq, 0); i++)
135918334Speter    {
136018334Speter      rtx trial = XVECEXP (seq, 0, i);
136118334Speter
136218334Speter      /* If TRIAL sets CC0, stealing it will move it too far from the use
136318334Speter	 of CC0.  */
136418334Speter      if (insn_references_resource_p (trial, sets, 0)
136518334Speter	  || insn_sets_resource_p (trial, needed, 0)
136618334Speter	  || insn_sets_resource_p (trial, sets, 0)
136718334Speter#ifdef HAVE_cc0
136818334Speter	  || sets_cc0_p (PATTERN (trial))
136918334Speter#endif
137018334Speter	  )
137118334Speter
137218334Speter	break;
137318334Speter
137418334Speter      /* If this insn was already done, we don't need it.  */
137518334Speter      if (redundant_insn (trial, insn, delay_list))
137618334Speter	{
137718334Speter	  delete_from_delay_slot (trial);
137818334Speter	  continue;
137918334Speter	}
138018334Speter
138152284Sobrien      if (! must_annul
138218334Speter	  && ((condition == const_true_rtx
138318334Speter	       || (! insn_sets_resource_p (trial, other_needed, 0)
1384169689Skan		   && ! may_trap_or_fault_p (PATTERN (trial)))))
138518334Speter	  ? eligible_for_delay (insn, *pslots_filled, trial, flags)
138652284Sobrien	  : (must_annul || delay_list == NULL) && (must_annul = 1,
138752284Sobrien	     check_annul_list_true_false (1, delay_list)
138852284Sobrien	     && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
138918334Speter	{
139052284Sobrien	  if (must_annul)
139152284Sobrien	    used_annul = 1;
139218334Speter	  delete_from_delay_slot (trial);
139318334Speter	  delay_list = add_to_delay_list (trial, delay_list);
139418334Speter
139518334Speter	  if (++(*pslots_filled) == slots_to_fill)
139618334Speter	    break;
139718334Speter	}
139818334Speter      else
139918334Speter	break;
140018334Speter    }
140118334Speter
140252284Sobrien  if (used_annul)
140352284Sobrien    *pannul_p = 1;
140418334Speter  return delay_list;
140518334Speter}
140618334Speter
140718334Speter/* Try merging insns starting at THREAD which match exactly the insns in
140818334Speter   INSN's delay list.
140918334Speter
141018334Speter   If all insns were matched and the insn was previously annulling, the
141118334Speter   annul bit will be cleared.
141218334Speter
141318334Speter   For each insn that is merged, if the branch is or will be non-annulling,
141418334Speter   we delete the merged insn.  */
141518334Speter
141618334Speterstatic void
1417132718Skantry_merge_delay_insns (rtx insn, rtx thread)
141818334Speter{
141918334Speter  rtx trial, next_trial;
142018334Speter  rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
142118334Speter  int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
142218334Speter  int slot_number = 1;
142318334Speter  int num_slots = XVECLEN (PATTERN (insn), 0);
142418334Speter  rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
142518334Speter  struct resources set, needed;
142618334Speter  rtx merged_insns = 0;
142718334Speter  int i;
142818334Speter  int flags;
142918334Speter
143018334Speter  flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
143118334Speter
143218334Speter  CLEAR_RESOURCE (&needed);
143318334Speter  CLEAR_RESOURCE (&set);
143418334Speter
143518334Speter  /* If this is not an annulling branch, take into account anything needed in
143652284Sobrien     INSN's delay slot.  This prevents two increments from being incorrectly
143718334Speter     folded into one.  If we are annulling, this would be the correct
143818334Speter     thing to do.  (The alternative, looking at things set in NEXT_TO_MATCH
143918334Speter     will essentially disable this optimization.  This method is somewhat of
144018334Speter     a kludge, but I don't see a better way.)  */
144118334Speter  if (! annul_p)
144290075Sobrien    for (i = 1 ; i < num_slots; i++)
144352284Sobrien      if (XVECEXP (PATTERN (insn), 0, i))
144490075Sobrien	mark_referenced_resources (XVECEXP (PATTERN (insn), 0, i), &needed, 1);
144518334Speter
144618334Speter  for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
144718334Speter    {
144818334Speter      rtx pat = PATTERN (trial);
144918334Speter      rtx oldtrial = trial;
145018334Speter
145118334Speter      next_trial = next_nonnote_insn (trial);
145218334Speter
145318334Speter      /* TRIAL must be a CALL_INSN or INSN.  Skip USE and CLOBBER.  */
1454169689Skan      if (NONJUMP_INSN_P (trial)
145518334Speter	  && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
145618334Speter	continue;
145718334Speter
145818334Speter      if (GET_CODE (next_to_match) == GET_CODE (trial)
145918334Speter#ifdef HAVE_cc0
146018334Speter	  /* We can't share an insn that sets cc0.  */
146118334Speter	  && ! sets_cc0_p (pat)
146218334Speter#endif
146318334Speter	  && ! insn_references_resource_p (trial, &set, 1)
146418334Speter	  && ! insn_sets_resource_p (trial, &set, 1)
146518334Speter	  && ! insn_sets_resource_p (trial, &needed, 1)
146618334Speter	  && (trial = try_split (pat, trial, 0)) != 0
146718334Speter	  /* Update next_trial, in case try_split succeeded.  */
146818334Speter	  && (next_trial = next_nonnote_insn (trial))
146918334Speter	  /* Likewise THREAD.  */
147018334Speter	  && (thread = oldtrial == thread ? trial : thread)
147118334Speter	  && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
147218334Speter	  /* Have to test this condition if annul condition is different
147318334Speter	     from (and less restrictive than) non-annulling one.  */
147418334Speter	  && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
147518334Speter	{
147618334Speter
147718334Speter	  if (! annul_p)
147818334Speter	    {
147918334Speter	      update_block (trial, thread);
148018334Speter	      if (trial == thread)
148118334Speter		thread = next_active_insn (thread);
148218334Speter
148390075Sobrien	      delete_related_insns (trial);
148418334Speter	      INSN_FROM_TARGET_P (next_to_match) = 0;
148518334Speter	    }
148618334Speter	  else
148750397Sobrien	    merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns);
148818334Speter
148918334Speter	  if (++slot_number == num_slots)
149018334Speter	    break;
149118334Speter
149218334Speter	  next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
149318334Speter	}
149418334Speter
149590075Sobrien      mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
149618334Speter      mark_referenced_resources (trial, &needed, 1);
149718334Speter    }
149818334Speter
149918334Speter  /* See if we stopped on a filled insn.  If we did, try to see if its
150018334Speter     delay slots match.  */
150118334Speter  if (slot_number != num_slots
1502169689Skan      && trial && NONJUMP_INSN_P (trial)
150318334Speter      && GET_CODE (PATTERN (trial)) == SEQUENCE
150418334Speter      && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
150518334Speter    {
150618334Speter      rtx pat = PATTERN (trial);
150718334Speter      rtx filled_insn = XVECEXP (pat, 0, 0);
150818334Speter
150918334Speter      /* Account for resources set/needed by the filled insn.  */
151090075Sobrien      mark_set_resources (filled_insn, &set, 0, MARK_SRC_DEST_CALL);
151118334Speter      mark_referenced_resources (filled_insn, &needed, 1);
151218334Speter
151318334Speter      for (i = 1; i < XVECLEN (pat, 0); i++)
151418334Speter	{
151518334Speter	  rtx dtrial = XVECEXP (pat, 0, i);
151618334Speter
151718334Speter	  if (! insn_references_resource_p (dtrial, &set, 1)
151818334Speter	      && ! insn_sets_resource_p (dtrial, &set, 1)
151918334Speter	      && ! insn_sets_resource_p (dtrial, &needed, 1)
152018334Speter#ifdef HAVE_cc0
152118334Speter	      && ! sets_cc0_p (PATTERN (dtrial))
152218334Speter#endif
152318334Speter	      && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
152418334Speter	      && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
152518334Speter	    {
152618334Speter	      if (! annul_p)
152718334Speter		{
152852284Sobrien		  rtx new;
152952284Sobrien
153018334Speter		  update_block (dtrial, thread);
153152284Sobrien		  new = delete_from_delay_slot (dtrial);
153252284Sobrien	          if (INSN_DELETED_P (thread))
153352284Sobrien		    thread = new;
153418334Speter		  INSN_FROM_TARGET_P (next_to_match) = 0;
153518334Speter		}
153618334Speter	      else
153750397Sobrien		merged_insns = gen_rtx_INSN_LIST (SImode, dtrial,
153850397Sobrien						  merged_insns);
153918334Speter
154018334Speter	      if (++slot_number == num_slots)
154118334Speter		break;
154218334Speter
154318334Speter	      next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
154418334Speter	    }
154552284Sobrien	  else
154652284Sobrien	    {
154752284Sobrien	      /* Keep track of the set/referenced resources for the delay
154852284Sobrien		 slots of any trial insns we encounter.  */
154990075Sobrien	      mark_set_resources (dtrial, &set, 0, MARK_SRC_DEST_CALL);
155090075Sobrien	      mark_referenced_resources (dtrial, &needed, 1);
155152284Sobrien	    }
155218334Speter	}
155318334Speter    }
155418334Speter
155518334Speter  /* If all insns in the delay slot have been matched and we were previously
155618334Speter     annulling the branch, we need not any more.  In that case delete all the
155750397Sobrien     merged insns.  Also clear the INSN_FROM_TARGET_P bit of each insn in
155818334Speter     the delay list so that we know that it isn't only being used at the
155918334Speter     target.  */
156018334Speter  if (slot_number == num_slots && annul_p)
156118334Speter    {
156218334Speter      for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
156318334Speter	{
156418334Speter	  if (GET_MODE (merged_insns) == SImode)
156518334Speter	    {
156652284Sobrien	      rtx new;
156752284Sobrien
156818334Speter	      update_block (XEXP (merged_insns, 0), thread);
156952284Sobrien	      new = delete_from_delay_slot (XEXP (merged_insns, 0));
157052284Sobrien	      if (INSN_DELETED_P (thread))
157152284Sobrien		thread = new;
157218334Speter	    }
157318334Speter	  else
157418334Speter	    {
157518334Speter	      update_block (XEXP (merged_insns, 0), thread);
157690075Sobrien	      delete_related_insns (XEXP (merged_insns, 0));
157718334Speter	    }
157818334Speter	}
157918334Speter
158018334Speter      INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
158118334Speter
158218334Speter      for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
158318334Speter	INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
158418334Speter    }
158518334Speter}
158618334Speter
158718334Speter/* See if INSN is redundant with an insn in front of TARGET.  Often this
158818334Speter   is called when INSN is a candidate for a delay slot of TARGET.
158918334Speter   DELAY_LIST are insns that will be placed in delay slots of TARGET in front
159018334Speter   of INSN.  Often INSN will be redundant with an insn in a delay slot of
159118334Speter   some previous insn.  This happens when we have a series of branches to the
159218334Speter   same label; in that case the first insn at the target might want to go
159318334Speter   into each of the delay slots.
159418334Speter
159518334Speter   If we are not careful, this routine can take up a significant fraction
159618334Speter   of the total compilation time (4%), but only wins rarely.  Hence we
159718334Speter   speed this routine up by making two passes.  The first pass goes back
1598132718Skan   until it hits a label and sees if it finds an insn with an identical
159918334Speter   pattern.  Only in this (relatively rare) event does it check for
160018334Speter   data conflicts.
160118334Speter
160218334Speter   We do not split insns we encounter.  This could cause us not to find a
160318334Speter   redundant insn, but the cost of splitting seems greater than the possible
160418334Speter   gain in rare cases.  */
160518334Speter
160618334Speterstatic rtx
1607132718Skanredundant_insn (rtx insn, rtx target, rtx delay_list)
160818334Speter{
160918334Speter  rtx target_main = target;
161018334Speter  rtx ipat = PATTERN (insn);
161118334Speter  rtx trial, pat;
161218334Speter  struct resources needed, set;
161318334Speter  int i;
161490075Sobrien  unsigned insns_to_search;
161518334Speter
161650397Sobrien  /* If INSN has any REG_UNUSED notes, it can't match anything since we
161750397Sobrien     are allowed to not actually assign to such a register.  */
161850397Sobrien  if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0)
161950397Sobrien    return 0;
162050397Sobrien
162118334Speter  /* Scan backwards looking for a match.  */
162290075Sobrien  for (trial = PREV_INSN (target),
162390075Sobrien	 insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH;
162490075Sobrien       trial && insns_to_search > 0;
162590075Sobrien       trial = PREV_INSN (trial), --insns_to_search)
162618334Speter    {
1627169689Skan      if (LABEL_P (trial))
162818334Speter	return 0;
162918334Speter
163090075Sobrien      if (! INSN_P (trial))
163118334Speter	continue;
163218334Speter
163318334Speter      pat = PATTERN (trial);
163418334Speter      if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
163518334Speter	continue;
163618334Speter
163718334Speter      if (GET_CODE (pat) == SEQUENCE)
163818334Speter	{
163918334Speter	  /* Stop for a CALL and its delay slots because it is difficult to
164018334Speter	     track its resource needs correctly.  */
1641169689Skan	  if (CALL_P (XVECEXP (pat, 0, 0)))
164218334Speter	    return 0;
164318334Speter
164418334Speter	  /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
164590075Sobrien	     slots because it is difficult to track its resource needs
164618334Speter	     correctly.  */
164718334Speter
164818334Speter#ifdef INSN_SETS_ARE_DELAYED
164918334Speter	  if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
165090075Sobrien	    return 0;
165118334Speter#endif
165218334Speter
165318334Speter#ifdef INSN_REFERENCES_ARE_DELAYED
165418334Speter	  if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
165590075Sobrien	    return 0;
165618334Speter#endif
165718334Speter
165818334Speter	  /* See if any of the insns in the delay slot match, updating
165918334Speter	     resource requirements as we go.  */
166018334Speter	  for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
166118334Speter	    if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
166250397Sobrien		&& rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat)
166350397Sobrien		&& ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX))
166418334Speter	      break;
166518334Speter
166618334Speter	  /* If found a match, exit this loop early.  */
166718334Speter	  if (i > 0)
166818334Speter	    break;
166918334Speter	}
167018334Speter
167150397Sobrien      else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)
167250397Sobrien	       && ! find_reg_note (trial, REG_UNUSED, NULL_RTX))
167318334Speter	break;
167418334Speter    }
167518334Speter
167618334Speter  /* If we didn't find an insn that matches, return 0.  */
167718334Speter  if (trial == 0)
167818334Speter    return 0;
167918334Speter
168018334Speter  /* See what resources this insn sets and needs.  If they overlap, or
168118334Speter     if this insn references CC0, it can't be redundant.  */
168218334Speter
168318334Speter  CLEAR_RESOURCE (&needed);
168418334Speter  CLEAR_RESOURCE (&set);
168590075Sobrien  mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
168618334Speter  mark_referenced_resources (insn, &needed, 1);
168718334Speter
168818334Speter  /* If TARGET is a SEQUENCE, get the main insn.  */
1689169689Skan  if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE)
169018334Speter    target_main = XVECEXP (PATTERN (target), 0, 0);
169118334Speter
169218334Speter  if (resource_conflicts_p (&needed, &set)
169318334Speter#ifdef HAVE_cc0
169418334Speter      || reg_mentioned_p (cc0_rtx, ipat)
169518334Speter#endif
169618334Speter      /* The insn requiring the delay may not set anything needed or set by
169718334Speter	 INSN.  */
169818334Speter      || insn_sets_resource_p (target_main, &needed, 1)
169918334Speter      || insn_sets_resource_p (target_main, &set, 1))
170018334Speter    return 0;
170118334Speter
170218334Speter  /* Insns we pass may not set either NEEDED or SET, so merge them for
170318334Speter     simpler tests.  */
170418334Speter  needed.memory |= set.memory;
170518334Speter  needed.unch_memory |= set.unch_memory;
170618334Speter  IOR_HARD_REG_SET (needed.regs, set.regs);
170718334Speter
170818334Speter  /* This insn isn't redundant if it conflicts with an insn that either is
170918334Speter     or will be in a delay slot of TARGET.  */
171018334Speter
171118334Speter  while (delay_list)
171218334Speter    {
171318334Speter      if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
171418334Speter	return 0;
171518334Speter      delay_list = XEXP (delay_list, 1);
171618334Speter    }
171718334Speter
1718169689Skan  if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE)
171918334Speter    for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
172018334Speter      if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
172118334Speter	return 0;
172218334Speter
172318334Speter  /* Scan backwards until we reach a label or an insn that uses something
172418334Speter     INSN sets or sets something insn uses or sets.  */
172518334Speter
172690075Sobrien  for (trial = PREV_INSN (target),
172790075Sobrien	 insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH;
1728169689Skan       trial && !LABEL_P (trial) && insns_to_search > 0;
172990075Sobrien       trial = PREV_INSN (trial), --insns_to_search)
173018334Speter    {
1731169689Skan      if (!INSN_P (trial))
173218334Speter	continue;
173318334Speter
173418334Speter      pat = PATTERN (trial);
173518334Speter      if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
173618334Speter	continue;
173718334Speter
173818334Speter      if (GET_CODE (pat) == SEQUENCE)
173918334Speter	{
174018334Speter	  /* If this is a CALL_INSN and its delay slots, it is hard to track
174118334Speter	     the resource needs properly, so give up.  */
1742169689Skan	  if (CALL_P (XVECEXP (pat, 0, 0)))
174318334Speter	    return 0;
174418334Speter
174550397Sobrien	  /* If this is an INSN or JUMP_INSN with delayed effects, it
174618334Speter	     is hard to track the resource needs properly, so give up.  */
174718334Speter
174818334Speter#ifdef INSN_SETS_ARE_DELAYED
174918334Speter	  if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
175090075Sobrien	    return 0;
175118334Speter#endif
175218334Speter
175318334Speter#ifdef INSN_REFERENCES_ARE_DELAYED
175418334Speter	  if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
175590075Sobrien	    return 0;
175618334Speter#endif
175718334Speter
175818334Speter	  /* See if any of the insns in the delay slot match, updating
175918334Speter	     resource requirements as we go.  */
176018334Speter	  for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
176118334Speter	    {
176218334Speter	      rtx candidate = XVECEXP (pat, 0, i);
176318334Speter
176418334Speter	      /* If an insn will be annulled if the branch is false, it isn't
176518334Speter		 considered as a possible duplicate insn.  */
176618334Speter	      if (rtx_equal_p (PATTERN (candidate), ipat)
176718334Speter		  && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
176818334Speter			&& INSN_FROM_TARGET_P (candidate)))
176918334Speter		{
177018334Speter		  /* Show that this insn will be used in the sequel.  */
177118334Speter		  INSN_FROM_TARGET_P (candidate) = 0;
177218334Speter		  return candidate;
177318334Speter		}
177418334Speter
177518334Speter	      /* Unless this is an annulled insn from the target of a branch,
177618334Speter		 we must stop if it sets anything needed or set by INSN.  */
177718334Speter	      if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
177818334Speter		   || ! INSN_FROM_TARGET_P (candidate))
177918334Speter		  && insn_sets_resource_p (candidate, &needed, 1))
178018334Speter		return 0;
178118334Speter	    }
178218334Speter
178390075Sobrien	  /* If the insn requiring the delay slot conflicts with INSN, we
178418334Speter	     must stop.  */
178518334Speter	  if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
178618334Speter	    return 0;
178718334Speter	}
178818334Speter      else
178918334Speter	{
179018334Speter	  /* See if TRIAL is the same as INSN.  */
179118334Speter	  pat = PATTERN (trial);
179218334Speter	  if (rtx_equal_p (pat, ipat))
179318334Speter	    return trial;
179418334Speter
179518334Speter	  /* Can't go any further if TRIAL conflicts with INSN.  */
179618334Speter	  if (insn_sets_resource_p (trial, &needed, 1))
179718334Speter	    return 0;
179818334Speter	}
179918334Speter    }
180018334Speter
180118334Speter  return 0;
180218334Speter}
180318334Speter
1804117395Skan/* Return 1 if THREAD can only be executed in one way.  If LABEL is nonzero,
180518334Speter   it is the target of the branch insn being scanned.  If ALLOW_FALLTHROUGH
1806117395Skan   is nonzero, we are allowed to fall into this thread; otherwise, we are
180718334Speter   not.
180818334Speter
180918334Speter   If LABEL is used more than one or we pass a label other than LABEL before
181018334Speter   finding an active insn, we do not own this thread.  */
181118334Speter
181218334Speterstatic int
1813132718Skanown_thread_p (rtx thread, rtx label, int allow_fallthrough)
181418334Speter{
181518334Speter  rtx active_insn;
181618334Speter  rtx insn;
181718334Speter
181818334Speter  /* We don't own the function end.  */
181918334Speter  if (thread == 0)
182018334Speter    return 0;
182118334Speter
182218334Speter  /* Get the first active insn, or THREAD, if it is an active insn.  */
182318334Speter  active_insn = next_active_insn (PREV_INSN (thread));
182418334Speter
182518334Speter  for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
1826169689Skan    if (LABEL_P (insn)
182718334Speter	&& (insn != label || LABEL_NUSES (insn) != 1))
182818334Speter      return 0;
182918334Speter
183018334Speter  if (allow_fallthrough)
183118334Speter    return 1;
183218334Speter
183318334Speter  /* Ensure that we reach a BARRIER before any insn or label.  */
183418334Speter  for (insn = prev_nonnote_insn (thread);
1835169689Skan       insn == 0 || !BARRIER_P (insn);
183618334Speter       insn = prev_nonnote_insn (insn))
183718334Speter    if (insn == 0
1838169689Skan	|| LABEL_P (insn)
1839169689Skan	|| (NONJUMP_INSN_P (insn)
184018334Speter	    && GET_CODE (PATTERN (insn)) != USE
184118334Speter	    && GET_CODE (PATTERN (insn)) != CLOBBER))
184218334Speter      return 0;
184318334Speter
184418334Speter  return 1;
184518334Speter}
184618334Speter
184718334Speter/* Called when INSN is being moved from a location near the target of a jump.
184818334Speter   We leave a marker of the form (use (INSN)) immediately in front
184918334Speter   of WHERE for mark_target_live_regs.  These markers will be deleted when
185018334Speter   reorg finishes.
185118334Speter
185218334Speter   We used to try to update the live status of registers if WHERE is at
185318334Speter   the start of a basic block, but that can't work since we may remove a
185418334Speter   BARRIER in relax_delay_slots.  */
185518334Speter
185618334Speterstatic void
1857132718Skanupdate_block (rtx insn, rtx where)
185818334Speter{
185990075Sobrien  /* Ignore if this was in a delay slot and it came from the target of
186018334Speter     a branch.  */
186118334Speter  if (INSN_FROM_TARGET_P (insn))
186218334Speter    return;
186318334Speter
186450397Sobrien  emit_insn_before (gen_rtx_USE (VOIDmode, insn), where);
186518334Speter
186618334Speter  /* INSN might be making a value live in a block where it didn't use to
186718334Speter     be.  So recompute liveness information for this block.  */
186818334Speter
186952284Sobrien  incr_ticks_for_insn (insn);
187018334Speter}
187118334Speter
187218334Speter/* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
187318334Speter   the basic block containing the jump.  */
187418334Speter
187518334Speterstatic int
1876132718Skanreorg_redirect_jump (rtx jump, rtx nlabel)
187718334Speter{
187852284Sobrien  incr_ticks_for_insn (jump);
187990075Sobrien  return redirect_jump (jump, nlabel, 1);
188018334Speter}
188118334Speter
188218334Speter/* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
188318334Speter   We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
188418334Speter   that reference values used in INSN.  If we find one, then we move the
188518334Speter   REG_DEAD note to INSN.
188618334Speter
1887169689Skan   This is needed to handle the case where a later insn (after INSN) has a
188818334Speter   REG_DEAD note for a register used by INSN, and this later insn subsequently
188918334Speter   gets moved before a CODE_LABEL because it is a redundant insn.  In this
189018334Speter   case, mark_target_live_regs may be confused into thinking the register
189118334Speter   is dead because it sees a REG_DEAD note immediately before a CODE_LABEL.  */
189218334Speter
189318334Speterstatic void
1894132718Skanupdate_reg_dead_notes (rtx insn, rtx delayed_insn)
189518334Speter{
189618334Speter  rtx p, link, next;
189718334Speter
189818334Speter  for (p = next_nonnote_insn (insn); p != delayed_insn;
189918334Speter       p = next_nonnote_insn (p))
190018334Speter    for (link = REG_NOTES (p); link; link = next)
190118334Speter      {
190218334Speter	next = XEXP (link, 1);
190318334Speter
190418334Speter	if (REG_NOTE_KIND (link) != REG_DEAD
1905169689Skan	    || !REG_P (XEXP (link, 0)))
190618334Speter	  continue;
190718334Speter
190818334Speter	if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
190918334Speter	  {
191018334Speter	    /* Move the REG_DEAD note from P to INSN.  */
191118334Speter	    remove_note (p, link);
191218334Speter	    XEXP (link, 1) = REG_NOTES (insn);
191318334Speter	    REG_NOTES (insn) = link;
191418334Speter	  }
191518334Speter      }
191618334Speter}
191718334Speter
191850397Sobrien/* Called when an insn redundant with start_insn is deleted.  If there
191950397Sobrien   is a REG_DEAD note for the target of start_insn between start_insn
192050397Sobrien   and stop_insn, then the REG_DEAD note needs to be deleted since the
192150397Sobrien   value no longer dies there.
192250397Sobrien
192350397Sobrien   If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
192450397Sobrien   confused into thinking the register is dead.  */
192550397Sobrien
192650397Sobrienstatic void
1927132718Skanfix_reg_dead_note (rtx start_insn, rtx stop_insn)
192850397Sobrien{
192950397Sobrien  rtx p, link, next;
193050397Sobrien
193150397Sobrien  for (p = next_nonnote_insn (start_insn); p != stop_insn;
193250397Sobrien       p = next_nonnote_insn (p))
193350397Sobrien    for (link = REG_NOTES (p); link; link = next)
193450397Sobrien      {
193550397Sobrien	next = XEXP (link, 1);
193650397Sobrien
193750397Sobrien	if (REG_NOTE_KIND (link) != REG_DEAD
1938169689Skan	    || !REG_P (XEXP (link, 0)))
193950397Sobrien	  continue;
194050397Sobrien
194150397Sobrien	if (reg_set_p (XEXP (link, 0), PATTERN (start_insn)))
194250397Sobrien	  {
194350397Sobrien	    remove_note (p, link);
194450397Sobrien	    return;
194550397Sobrien	  }
194650397Sobrien      }
194750397Sobrien}
194850397Sobrien
194918334Speter/* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
195018334Speter
195118334Speter   This handles the case of udivmodXi4 instructions which optimize their
195218334Speter   output depending on whether any REG_UNUSED notes are present.
195318334Speter   we must make sure that INSN calculates as many results as REDUNDANT_INSN
195418334Speter   does.  */
195518334Speter
195618334Speterstatic void
1957132718Skanupdate_reg_unused_notes (rtx insn, rtx redundant_insn)
195818334Speter{
195950397Sobrien  rtx link, next;
196018334Speter
196118334Speter  for (link = REG_NOTES (insn); link; link = next)
196218334Speter    {
196318334Speter      next = XEXP (link, 1);
196418334Speter
196518334Speter      if (REG_NOTE_KIND (link) != REG_UNUSED
1966169689Skan	  || !REG_P (XEXP (link, 0)))
196718334Speter	continue;
196818334Speter
196918334Speter      if (! find_regno_note (redundant_insn, REG_UNUSED,
197018334Speter			     REGNO (XEXP (link, 0))))
197118334Speter	remove_note (insn, link);
197218334Speter    }
197318334Speter}
197418334Speter
197518334Speter/* Scan a function looking for insns that need a delay slot and find insns to
197618334Speter   put into the delay slot.
197718334Speter
1978117395Skan   NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such
197918334Speter   as calls).  We do these first since we don't want jump insns (that are
198018334Speter   easier to fill) to get the only insns that could be used for non-jump insns.
198118334Speter   When it is zero, only try to fill JUMP_INSNs.
198218334Speter
198318334Speter   When slots are filled in this manner, the insns (including the
198418334Speter   delay_insn) are put together in a SEQUENCE rtx.  In this fashion,
198518334Speter   it is possible to tell whether a delay slot has really been filled
198618334Speter   or not.  `final' knows how to deal with this, by communicating
198718334Speter   through FINAL_SEQUENCE.  */
198818334Speter
198918334Speterstatic void
1990132718Skanfill_simple_delay_slots (int non_jumps_p)
199118334Speter{
199290075Sobrien  rtx insn, pat, trial, next_trial;
199390075Sobrien  int i;
199418334Speter  int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
199518334Speter  struct resources needed, set;
199650397Sobrien  int slots_to_fill, slots_filled;
199718334Speter  rtx delay_list;
199818334Speter
199918334Speter  for (i = 0; i < num_unfilled_slots; i++)
200018334Speter    {
200118334Speter      int flags;
200218334Speter      /* Get the next insn to fill.  If it has already had any slots assigned,
200318334Speter	 we can't do anything with it.  Maybe we'll improve this later.  */
200418334Speter
200518334Speter      insn = unfilled_slots_base[i];
200618334Speter      if (insn == 0
200718334Speter	  || INSN_DELETED_P (insn)
2008169689Skan	  || (NONJUMP_INSN_P (insn)
200918334Speter	      && GET_CODE (PATTERN (insn)) == SEQUENCE)
2010169689Skan	  || (JUMP_P (insn) && non_jumps_p)
2011169689Skan	  || (!JUMP_P (insn) && ! non_jumps_p))
201218334Speter	continue;
201390075Sobrien
201490075Sobrien      /* It may have been that this insn used to need delay slots, but
201590075Sobrien	 now doesn't; ignore in that case.  This can happen, for example,
201690075Sobrien	 on the HP PA RISC, where the number of delay slots depends on
201790075Sobrien	 what insns are nearby.  */
201818334Speter      slots_to_fill = num_delay_slots (insn);
201950397Sobrien
202050397Sobrien      /* Some machine description have defined instructions to have
202150397Sobrien	 delay slots only in certain circumstances which may depend on
202250397Sobrien	 nearby insns (which change due to reorg's actions).
202350397Sobrien
202450397Sobrien	 For example, the PA port normally has delay slots for unconditional
202550397Sobrien	 jumps.
202650397Sobrien
202750397Sobrien	 However, the PA port claims such jumps do not have a delay slot
202850397Sobrien	 if they are immediate successors of certain CALL_INSNs.  This
202950397Sobrien	 allows the port to favor filling the delay slot of the call with
203050397Sobrien	 the unconditional jump.  */
203118334Speter      if (slots_to_fill == 0)
203250397Sobrien	continue;
203318334Speter
203418334Speter      /* This insn needs, or can use, some delay slots.  SLOTS_TO_FILL
203518334Speter	 says how many.  After initialization, first try optimizing
203618334Speter
203718334Speter	 call _foo		call _foo
203818334Speter	 nop			add %o7,.-L1,%o7
203918334Speter	 b,a L1
204018334Speter	 nop
204118334Speter
204218334Speter	 If this case applies, the delay slot of the call is filled with
204318334Speter	 the unconditional jump.  This is done first to avoid having the
204418334Speter	 delay slot of the call filled in the backward scan.  Also, since
204518334Speter	 the unconditional jump is likely to also have a delay slot, that
204618334Speter	 insn must exist when it is subsequently scanned.
204718334Speter
204818334Speter	 This is tried on each insn with delay slots as some machines
204990075Sobrien	 have insns which perform calls, but are not represented as
205018334Speter	 CALL_INSNs.  */
205118334Speter
205218334Speter      slots_filled = 0;
205318334Speter      delay_list = 0;
205418334Speter
2055169689Skan      if (JUMP_P (insn))
205690075Sobrien	flags = get_jump_flags (insn, JUMP_LABEL (insn));
205790075Sobrien      else
205890075Sobrien	flags = get_jump_flags (insn, NULL_RTX);
205990075Sobrien
206018334Speter      if ((trial = next_active_insn (insn))
2061169689Skan	  && JUMP_P (trial)
206218334Speter	  && simplejump_p (trial)
206318334Speter	  && eligible_for_delay (insn, slots_filled, trial, flags)
206496263Sobrien	  && no_labels_between_p (insn, trial)
206596263Sobrien	  && ! can_throw_internal (trial))
206618334Speter	{
206718334Speter	  rtx *tmp;
206818334Speter	  slots_filled++;
206918334Speter	  delay_list = add_to_delay_list (trial, delay_list);
207018334Speter
207118334Speter	  /* TRIAL may have had its delay slot filled, then unfilled.  When
207218334Speter	     the delay slot is unfilled, TRIAL is placed back on the unfilled
207318334Speter	     slots obstack.  Unfortunately, it is placed on the end of the
207418334Speter	     obstack, not in its original location.  Therefore, we must search
207518334Speter	     from entry i + 1 to the end of the unfilled slots obstack to
207618334Speter	     try and find TRIAL.  */
207718334Speter	  tmp = &unfilled_slots_base[i + 1];
207818334Speter	  while (*tmp != trial && tmp != unfilled_slots_next)
207918334Speter	    tmp++;
208018334Speter
208118334Speter	  /* Remove the unconditional jump from consideration for delay slot
208290075Sobrien	     filling and unthread it.  */
208318334Speter	  if (*tmp == trial)
208418334Speter	    *tmp = 0;
208518334Speter	  {
208618334Speter	    rtx next = NEXT_INSN (trial);
208718334Speter	    rtx prev = PREV_INSN (trial);
208818334Speter	    if (prev)
208918334Speter	      NEXT_INSN (prev) = next;
209018334Speter	    if (next)
209118334Speter	      PREV_INSN (next) = prev;
209218334Speter	  }
209318334Speter	}
209418334Speter
209518334Speter      /* Now, scan backwards from the insn to search for a potential
209618334Speter	 delay-slot candidate.  Stop searching when a label or jump is hit.
209718334Speter
209818334Speter	 For each candidate, if it is to go into the delay slot (moved
209918334Speter	 forward in execution sequence), it must not need or set any resources
210018334Speter	 that were set by later insns and must not set any resources that
210118334Speter	 are needed for those insns.
210290075Sobrien
210318334Speter	 The delay slot insn itself sets resources unless it is a call
210418334Speter	 (in which case the called routine, not the insn itself, is doing
210518334Speter	 the setting).  */
210618334Speter
210718334Speter      if (slots_filled < slots_to_fill)
210818334Speter	{
210918334Speter	  CLEAR_RESOURCE (&needed);
211018334Speter	  CLEAR_RESOURCE (&set);
211190075Sobrien	  mark_set_resources (insn, &set, 0, MARK_SRC_DEST);
211218334Speter	  mark_referenced_resources (insn, &needed, 0);
211318334Speter
211418334Speter	  for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
211518334Speter	       trial = next_trial)
211618334Speter	    {
211718334Speter	      next_trial = prev_nonnote_insn (trial);
211818334Speter
211918334Speter	      /* This must be an INSN or CALL_INSN.  */
212018334Speter	      pat = PATTERN (trial);
212118334Speter
212218334Speter	      /* USE and CLOBBER at this level was just for flow; ignore it.  */
212318334Speter	      if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
212418334Speter		continue;
212518334Speter
212690075Sobrien	      /* Check for resource conflict first, to avoid unnecessary
212718334Speter		 splitting.  */
212818334Speter	      if (! insn_references_resource_p (trial, &set, 1)
212918334Speter		  && ! insn_sets_resource_p (trial, &set, 1)
213018334Speter		  && ! insn_sets_resource_p (trial, &needed, 1)
213118334Speter#ifdef HAVE_cc0
213218334Speter		  /* Can't separate set of cc0 from its use.  */
213390075Sobrien		  && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
213418334Speter#endif
213596263Sobrien		  && ! can_throw_internal (trial))
213618334Speter		{
213718334Speter		  trial = try_split (pat, trial, 1);
213818334Speter		  next_trial = prev_nonnote_insn (trial);
213918334Speter		  if (eligible_for_delay (insn, slots_filled, trial, flags))
214018334Speter		    {
214118334Speter		      /* In this case, we are searching backward, so if we
214218334Speter			 find insns to put on the delay list, we want
214318334Speter			 to put them at the head, rather than the
214418334Speter			 tail, of the list.  */
214518334Speter
214618334Speter		      update_reg_dead_notes (trial, insn);
214750397Sobrien		      delay_list = gen_rtx_INSN_LIST (VOIDmode,
214850397Sobrien						      trial, delay_list);
214918334Speter		      update_block (trial, trial);
215090075Sobrien		      delete_related_insns (trial);
215118334Speter		      if (slots_to_fill == ++slots_filled)
215218334Speter			break;
215318334Speter		      continue;
215418334Speter		    }
215518334Speter		}
215618334Speter
215790075Sobrien	      mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
215818334Speter	      mark_referenced_resources (trial, &needed, 1);
215918334Speter	    }
216018334Speter	}
216118334Speter
216218334Speter      /* If all needed slots haven't been filled, we come here.  */
216318334Speter
216418334Speter      /* Try to optimize case of jumping around a single insn.  */
216518334Speter#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
216618334Speter      if (slots_filled != slots_to_fill
216718334Speter	  && delay_list == 0
2168169689Skan	  && JUMP_P (insn)
216918334Speter	  && (condjump_p (insn) || condjump_in_parallel_p (insn)))
217018334Speter	{
217118334Speter	  delay_list = optimize_skip (insn);
217218334Speter	  if (delay_list)
217318334Speter	    slots_filled += 1;
217418334Speter	}
217518334Speter#endif
217618334Speter
217718334Speter      /* Try to get insns from beyond the insn needing the delay slot.
217818334Speter	 These insns can neither set or reference resources set in insns being
217918334Speter	 skipped, cannot set resources in the insn being skipped, and, if this
218018334Speter	 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
218118334Speter	 call might not return).
218218334Speter
218318334Speter	 There used to be code which continued past the target label if
218418334Speter	 we saw all uses of the target label.  This code did not work,
218518334Speter	 because it failed to account for some instructions which were
218618334Speter	 both annulled and marked as from the target.  This can happen as a
218718334Speter	 result of optimize_skip.  Since this code was redundant with
218818334Speter	 fill_eager_delay_slots anyways, it was just deleted.  */
218918334Speter
219018334Speter      if (slots_filled != slots_to_fill
219190075Sobrien	  /* If this instruction could throw an exception which is
219290075Sobrien	     caught in the same function, then it's not safe to fill
219390075Sobrien	     the delay slot with an instruction from beyond this
219490075Sobrien	     point.  For example, consider:
219590075Sobrien
219690075Sobrien               int i = 2;
219790075Sobrien
219890075Sobrien	       try {
219990075Sobrien                 f();
220090075Sobrien	         i = 3;
220190075Sobrien               } catch (...) {}
220290075Sobrien
220390075Sobrien               return i;
220490075Sobrien
220590075Sobrien	     Even though `i' is a local variable, we must be sure not
220690075Sobrien	     to put `i = 3' in the delay slot if `f' might throw an
220790075Sobrien	     exception.
220890075Sobrien
220990075Sobrien	     Presumably, we should also check to see if we could get
221090075Sobrien	     back to this function via `setjmp'.  */
221196263Sobrien	  && ! can_throw_internal (insn)
2212169689Skan	  && (!JUMP_P (insn)
221318334Speter	      || ((condjump_p (insn) || condjump_in_parallel_p (insn))
221490075Sobrien		  && ! simplejump_p (insn)
221590075Sobrien		  && JUMP_LABEL (insn) != 0)))
221618334Speter	{
221790075Sobrien	  /* Invariant: If insn is a JUMP_INSN, the insn's jump
221890075Sobrien	     label.  Otherwise, zero.  */
221918334Speter	  rtx target = 0;
222018334Speter	  int maybe_never = 0;
222190075Sobrien	  rtx pat, trial_delay;
222218334Speter
222318334Speter	  CLEAR_RESOURCE (&needed);
222418334Speter	  CLEAR_RESOURCE (&set);
222518334Speter
2226169689Skan	  if (CALL_P (insn))
222718334Speter	    {
222890075Sobrien	      mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
222918334Speter	      mark_referenced_resources (insn, &needed, 1);
223018334Speter	      maybe_never = 1;
223118334Speter	    }
223290075Sobrien	  else
223318334Speter	    {
223490075Sobrien	      mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
223518334Speter	      mark_referenced_resources (insn, &needed, 1);
2236169689Skan	      if (JUMP_P (insn))
223718334Speter		target = JUMP_LABEL (insn);
223818334Speter	    }
223918334Speter
224090075Sobrien	  if (target == 0)
224190075Sobrien	    for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
224290075Sobrien	      {
224390075Sobrien		next_trial = next_nonnote_insn (trial);
224418334Speter
2245169689Skan		if (LABEL_P (trial)
2246169689Skan		    || BARRIER_P (trial))
224790075Sobrien		  break;
224818334Speter
224990075Sobrien		/* We must have an INSN, JUMP_INSN, or CALL_INSN.  */
225090075Sobrien		pat = PATTERN (trial);
225118334Speter
225290075Sobrien		/* Stand-alone USE and CLOBBER are just for flow.  */
225390075Sobrien		if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
225490075Sobrien		  continue;
225518334Speter
225690075Sobrien		/* If this already has filled delay slots, get the insn needing
225790075Sobrien		   the delay slots.  */
225890075Sobrien		if (GET_CODE (pat) == SEQUENCE)
225990075Sobrien		  trial_delay = XVECEXP (pat, 0, 0);
226090075Sobrien		else
226190075Sobrien		  trial_delay = trial;
226218334Speter
226390075Sobrien		/* Stop our search when seeing an unconditional jump.  */
2264169689Skan		if (JUMP_P (trial_delay))
226590075Sobrien		  break;
226618334Speter
226790075Sobrien		/* See if we have a resource problem before we try to
226890075Sobrien		   split.  */
226990075Sobrien		if (GET_CODE (pat) != SEQUENCE
227090075Sobrien		    && ! insn_references_resource_p (trial, &set, 1)
227190075Sobrien		    && ! insn_sets_resource_p (trial, &set, 1)
227290075Sobrien		    && ! insn_sets_resource_p (trial, &needed, 1)
227318334Speter#ifdef HAVE_cc0
227490075Sobrien		    && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
227518334Speter#endif
2276169689Skan		    && ! (maybe_never && may_trap_or_fault_p (pat))
227790075Sobrien		    && (trial = try_split (pat, trial, 0))
227896263Sobrien		    && eligible_for_delay (insn, slots_filled, trial, flags)
227996263Sobrien		    && ! can_throw_internal(trial))
228090075Sobrien		  {
228190075Sobrien		    next_trial = next_nonnote_insn (trial);
228290075Sobrien		    delay_list = add_to_delay_list (trial, delay_list);
228318334Speter
228418334Speter#ifdef HAVE_cc0
228590075Sobrien		    if (reg_mentioned_p (cc0_rtx, pat))
228690075Sobrien		      link_cc0_insns (trial);
228718334Speter#endif
228818334Speter
228990075Sobrien		    delete_related_insns (trial);
229090075Sobrien		    if (slots_to_fill == ++slots_filled)
229190075Sobrien		      break;
229290075Sobrien		    continue;
229390075Sobrien		  }
229418334Speter
229590075Sobrien		mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
229690075Sobrien		mark_referenced_resources (trial, &needed, 1);
229718334Speter
229890075Sobrien		/* Ensure we don't put insns between the setting of cc and the
229990075Sobrien		   comparison by moving a setting of cc into an earlier delay
230090075Sobrien		   slot since these insns could clobber the condition code.  */
230190075Sobrien		set.cc = 1;
230218334Speter
230390075Sobrien		/* If this is a call or jump, we might not get here.  */
2304169689Skan		if (CALL_P (trial_delay)
2305169689Skan		    || JUMP_P (trial_delay))
230690075Sobrien		  maybe_never = 1;
230790075Sobrien	      }
230818334Speter
230918334Speter	  /* If there are slots left to fill and our search was stopped by an
231018334Speter	     unconditional branch, try the insn at the branch target.  We can
231190075Sobrien	     redirect the branch if it works.
231218334Speter
231318334Speter	     Don't do this if the insn at the branch target is a branch.  */
231418334Speter	  if (slots_to_fill != slots_filled
231518334Speter	      && trial
2316169689Skan	      && JUMP_P (trial)
231718334Speter	      && simplejump_p (trial)
231818334Speter	      && (target == 0 || JUMP_LABEL (trial) == target)
231918334Speter	      && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2320169689Skan	      && ! (NONJUMP_INSN_P (next_trial)
232118334Speter		    && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2322169689Skan	      && !JUMP_P (next_trial)
232318334Speter	      && ! insn_references_resource_p (next_trial, &set, 1)
232418334Speter	      && ! insn_sets_resource_p (next_trial, &set, 1)
232518334Speter	      && ! insn_sets_resource_p (next_trial, &needed, 1)
232618334Speter#ifdef HAVE_cc0
232718334Speter	      && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
232818334Speter#endif
2329169689Skan	      && ! (maybe_never && may_trap_or_fault_p (PATTERN (next_trial)))
233018334Speter	      && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
233196263Sobrien	      && eligible_for_delay (insn, slots_filled, next_trial, flags)
233296263Sobrien	      && ! can_throw_internal (trial))
233318334Speter	    {
2334132718Skan	      /* See comment in relax_delay_slots about necessity of using
2335132718Skan		 next_real_insn here.  */
2336132718Skan	      rtx new_label = next_real_insn (next_trial);
233718334Speter
233818334Speter	      if (new_label != 0)
233918334Speter		new_label = get_label_before (new_label);
234018334Speter	      else
234118334Speter		new_label = find_end_label ();
234218334Speter
2343169689Skan	      if (new_label)
2344169689Skan	        {
2345169689Skan		  delay_list
2346169689Skan		    = add_to_delay_list (copy_rtx (next_trial), delay_list);
2347169689Skan		  slots_filled++;
2348169689Skan		  reorg_redirect_jump (trial, new_label);
234918334Speter
2350169689Skan		  /* If we merged because we both jumped to the same place,
2351169689Skan		     redirect the original insn also.  */
2352169689Skan		  if (target)
2353169689Skan		    reorg_redirect_jump (insn, new_label);
2354169689Skan		}
235518334Speter	    }
235618334Speter	}
235718334Speter
235850397Sobrien      /* If this is an unconditional jump, then try to get insns from the
235950397Sobrien	 target of the jump.  */
2360169689Skan      if (JUMP_P (insn)
236150397Sobrien	  && simplejump_p (insn)
236250397Sobrien	  && slots_filled != slots_to_fill)
236350397Sobrien	delay_list
236450397Sobrien	  = fill_slots_from_thread (insn, const_true_rtx,
236550397Sobrien				    next_active_insn (JUMP_LABEL (insn)),
236650397Sobrien				    NULL, 1, 1,
236750397Sobrien				    own_thread_p (JUMP_LABEL (insn),
236850397Sobrien						  JUMP_LABEL (insn), 0),
236950397Sobrien				    slots_to_fill, &slots_filled,
237050397Sobrien				    delay_list);
237150397Sobrien
237218334Speter      if (delay_list)
237318334Speter	unfilled_slots_base[i]
237450397Sobrien	  = emit_delay_sequence (insn, delay_list, slots_filled);
237518334Speter
237618334Speter      if (slots_to_fill == slots_filled)
237718334Speter	unfilled_slots_base[i] = 0;
237818334Speter
237918334Speter      note_delay_statistics (slots_filled, 0);
238018334Speter    }
238118334Speter
238218334Speter#ifdef DELAY_SLOTS_FOR_EPILOGUE
238318334Speter  /* See if the epilogue needs any delay slots.  Try to fill them if so.
238490075Sobrien     The only thing we can do is scan backwards from the end of the
238518334Speter     function.  If we did this in a previous pass, it is incorrect to do it
238618334Speter     again.  */
238718334Speter  if (current_function_epilogue_delay_list)
238818334Speter    return;
238918334Speter
239018334Speter  slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
239118334Speter  if (slots_to_fill == 0)
239218334Speter    return;
239318334Speter
239418334Speter  slots_filled = 0;
239518334Speter  CLEAR_RESOURCE (&set);
239618334Speter
239718334Speter  /* The frame pointer and stack pointer are needed at the beginning of
239818334Speter     the epilogue, so instructions setting them can not be put in the
239918334Speter     epilogue delay slot.  However, everything else needed at function
240018334Speter     end is safe, so we don't want to use end_of_function_needs here.  */
240118334Speter  CLEAR_RESOURCE (&needed);
240218334Speter  if (frame_pointer_needed)
240318334Speter    {
240418334Speter      SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
240518334Speter#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
240618334Speter      SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
240718334Speter#endif
240852284Sobrien      if (! EXIT_IGNORE_STACK
240952284Sobrien	  || current_function_sp_is_unchanging)
241018334Speter	SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
241118334Speter    }
241218334Speter  else
241318334Speter    SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
241418334Speter
241550397Sobrien#ifdef EPILOGUE_USES
241690075Sobrien  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
241750397Sobrien    {
241850397Sobrien      if (EPILOGUE_USES (i))
241950397Sobrien	SET_HARD_REG_BIT (needed.regs, i);
242050397Sobrien    }
242150397Sobrien#endif
242250397Sobrien
242318334Speter  for (trial = get_last_insn (); ! stop_search_p (trial, 1);
242418334Speter       trial = PREV_INSN (trial))
242518334Speter    {
2426169689Skan      if (NOTE_P (trial))
242718334Speter	continue;
242818334Speter      pat = PATTERN (trial);
242918334Speter      if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
243018334Speter	continue;
243118334Speter
243218334Speter      if (! insn_references_resource_p (trial, &set, 1)
243318334Speter	  && ! insn_sets_resource_p (trial, &needed, 1)
243418334Speter	  && ! insn_sets_resource_p (trial, &set, 1)
243518334Speter#ifdef HAVE_cc0
243618334Speter	  /* Don't want to mess with cc0 here.  */
243718334Speter	  && ! reg_mentioned_p (cc0_rtx, pat)
243818334Speter#endif
243996263Sobrien	  && ! can_throw_internal (trial))
244018334Speter	{
244118334Speter	  trial = try_split (pat, trial, 1);
244218334Speter	  if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
244318334Speter	    {
244418334Speter	      /* Here as well we are searching backward, so put the
244518334Speter		 insns we find on the head of the list.  */
244618334Speter
244718334Speter	      current_function_epilogue_delay_list
244850397Sobrien		= gen_rtx_INSN_LIST (VOIDmode, trial,
244950397Sobrien				     current_function_epilogue_delay_list);
245052284Sobrien	      mark_end_of_function_resources (trial, 1);
245118334Speter	      update_block (trial, trial);
245290075Sobrien	      delete_related_insns (trial);
245318334Speter
245418334Speter	      /* Clear deleted bit so final.c will output the insn.  */
245518334Speter	      INSN_DELETED_P (trial) = 0;
245618334Speter
245718334Speter	      if (slots_to_fill == ++slots_filled)
245818334Speter		break;
245918334Speter	      continue;
246018334Speter	    }
246118334Speter	}
246218334Speter
246390075Sobrien      mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
246418334Speter      mark_referenced_resources (trial, &needed, 1);
246518334Speter    }
246618334Speter
246718334Speter  note_delay_statistics (slots_filled, 0);
246818334Speter#endif
246918334Speter}
247018334Speter
247118334Speter/* Try to find insns to place in delay slots.
247218334Speter
247318334Speter   INSN is the jump needing SLOTS_TO_FILL delay slots.  It tests CONDITION
247418334Speter   or is an unconditional branch if CONDITION is const_true_rtx.
247518334Speter   *PSLOTS_FILLED is updated with the number of slots that we have filled.
247618334Speter
247718334Speter   THREAD is a flow-of-control, either the insns to be executed if the
247818334Speter   branch is true or if the branch is false, THREAD_IF_TRUE says which.
247918334Speter
248018334Speter   OPPOSITE_THREAD is the thread in the opposite direction.  It is used
248118334Speter   to see if any potential delay slot insns set things needed there.
248218334Speter
2483117395Skan   LIKELY is nonzero if it is extremely likely that the branch will be
248418334Speter   taken and THREAD_IF_TRUE is set.  This is used for the branch at the
248518334Speter   end of a loop back up to the top.
248618334Speter
248718334Speter   OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
248818334Speter   thread.  I.e., it is the fallthrough code of our jump or the target of the
248918334Speter   jump when we are the only jump going there.
249018334Speter
249118334Speter   If OWN_THREAD is false, it must be the "true" thread of a jump.  In that
249218334Speter   case, we can only take insns from the head of the thread for our delay
249318334Speter   slot.  We then adjust the jump to point after the insns we have taken.  */
249418334Speter
249518334Speterstatic rtx
2496132718Skanfill_slots_from_thread (rtx insn, rtx condition, rtx thread,
2497132718Skan			rtx opposite_thread, int likely, int thread_if_true,
2498132718Skan			int own_thread, int slots_to_fill,
2499132718Skan			int *pslots_filled, rtx delay_list)
250018334Speter{
250118334Speter  rtx new_thread;
250218334Speter  struct resources opposite_needed, set, needed;
250318334Speter  rtx trial;
250418334Speter  int lose = 0;
250518334Speter  int must_annul = 0;
250618334Speter  int flags;
250718334Speter
250818334Speter  /* Validate our arguments.  */
2509169689Skan  gcc_assert(condition != const_true_rtx || thread_if_true);
2510169689Skan  gcc_assert(own_thread || thread_if_true);
251118334Speter
251218334Speter  flags = get_jump_flags (insn, JUMP_LABEL (insn));
251318334Speter
251418334Speter  /* If our thread is the end of subroutine, we can't get any delay
251518334Speter     insns from that.  */
251618334Speter  if (thread == 0)
251790075Sobrien    return delay_list;
251818334Speter
251918334Speter  /* If this is an unconditional branch, nothing is needed at the
252018334Speter     opposite thread.  Otherwise, compute what is needed there.  */
252118334Speter  if (condition == const_true_rtx)
252218334Speter    CLEAR_RESOURCE (&opposite_needed);
252318334Speter  else
252452284Sobrien    mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed);
252518334Speter
252618334Speter  /* If the insn at THREAD can be split, do it here to avoid having to
252718334Speter     update THREAD and NEW_THREAD if it is done in the loop below.  Also
252818334Speter     initialize NEW_THREAD.  */
252918334Speter
253018334Speter  new_thread = thread = try_split (PATTERN (thread), thread, 0);
253118334Speter
253218334Speter  /* Scan insns at THREAD.  We are looking for an insn that can be removed
253318334Speter     from THREAD (it neither sets nor references resources that were set
253418334Speter     ahead of it and it doesn't set anything needs by the insns ahead of
253518334Speter     it) and that either can be placed in an annulling insn or aren't
253618334Speter     needed at OPPOSITE_THREAD.  */
253718334Speter
253818334Speter  CLEAR_RESOURCE (&needed);
253918334Speter  CLEAR_RESOURCE (&set);
254018334Speter
254118334Speter  /* If we do not own this thread, we must stop as soon as we find
254218334Speter     something that we can't put in a delay slot, since all we can do
254318334Speter     is branch into THREAD at a later point.  Therefore, labels stop
254418334Speter     the search if this is not the `true' thread.  */
254518334Speter
254618334Speter  for (trial = thread;
254718334Speter       ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
254818334Speter       trial = next_nonnote_insn (trial))
254918334Speter    {
255018334Speter      rtx pat, old_trial;
255118334Speter
255218334Speter      /* If we have passed a label, we no longer own this thread.  */
2553169689Skan      if (LABEL_P (trial))
255418334Speter	{
255518334Speter	  own_thread = 0;
255618334Speter	  continue;
255718334Speter	}
255818334Speter
255918334Speter      pat = PATTERN (trial);
256018334Speter      if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
256118334Speter	continue;
256218334Speter
256318334Speter      /* If TRIAL conflicts with the insns ahead of it, we lose.  Also,
256418334Speter	 don't separate or copy insns that set and use CC0.  */
256518334Speter      if (! insn_references_resource_p (trial, &set, 1)
256618334Speter	  && ! insn_sets_resource_p (trial, &set, 1)
256718334Speter	  && ! insn_sets_resource_p (trial, &needed, 1)
256818334Speter#ifdef HAVE_cc0
256918334Speter	  && ! (reg_mentioned_p (cc0_rtx, pat)
257018334Speter		&& (! own_thread || ! sets_cc0_p (pat)))
257118334Speter#endif
257296263Sobrien	  && ! can_throw_internal (trial))
257318334Speter	{
257418334Speter	  rtx prior_insn;
257518334Speter
257618334Speter	  /* If TRIAL is redundant with some insn before INSN, we don't
257718334Speter	     actually need to add it to the delay list; we can merely pretend
257818334Speter	     we did.  */
257950397Sobrien	  if ((prior_insn = redundant_insn (trial, insn, delay_list)))
258018334Speter	    {
258150397Sobrien	      fix_reg_dead_note (prior_insn, insn);
258218334Speter	      if (own_thread)
258318334Speter		{
258418334Speter		  update_block (trial, thread);
258518334Speter		  if (trial == thread)
258618334Speter		    {
258718334Speter		      thread = next_active_insn (thread);
258818334Speter		      if (new_thread == trial)
258918334Speter			new_thread = thread;
259018334Speter		    }
259118334Speter
259290075Sobrien		  delete_related_insns (trial);
259318334Speter		}
259418334Speter	      else
259518334Speter		{
259618334Speter		  update_reg_unused_notes (prior_insn, trial);
259718334Speter		  new_thread = next_active_insn (trial);
259818334Speter		}
259918334Speter
260018334Speter	      continue;
260118334Speter	    }
260218334Speter
260318334Speter	  /* There are two ways we can win:  If TRIAL doesn't set anything
260418334Speter	     needed at the opposite thread and can't trap, or if it can
260518334Speter	     go into an annulled delay slot.  */
260652284Sobrien	  if (!must_annul
260752284Sobrien	      && (condition == const_true_rtx
260852284Sobrien	          || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2609169689Skan		      && ! may_trap_or_fault_p (pat))))
261018334Speter	    {
261118334Speter	      old_trial = trial;
261218334Speter	      trial = try_split (pat, trial, 0);
261318334Speter	      if (new_thread == old_trial)
261418334Speter		new_thread = trial;
261518334Speter	      if (thread == old_trial)
261618334Speter		thread = trial;
261718334Speter	      pat = PATTERN (trial);
261818334Speter	      if (eligible_for_delay (insn, *pslots_filled, trial, flags))
261918334Speter		goto winner;
262018334Speter	    }
262118334Speter	  else if (0
262218334Speter#ifdef ANNUL_IFTRUE_SLOTS
262318334Speter		   || ! thread_if_true
262418334Speter#endif
262518334Speter#ifdef ANNUL_IFFALSE_SLOTS
262618334Speter		   || thread_if_true
262718334Speter#endif
262818334Speter		   )
262918334Speter	    {
263018334Speter	      old_trial = trial;
263118334Speter	      trial = try_split (pat, trial, 0);
263218334Speter	      if (new_thread == old_trial)
263318334Speter		new_thread = trial;
263418334Speter	      if (thread == old_trial)
263518334Speter		thread = trial;
263618334Speter	      pat = PATTERN (trial);
263752284Sobrien	      if ((must_annul || delay_list == NULL) && (thread_if_true
263852284Sobrien		   ? check_annul_list_true_false (0, delay_list)
263952284Sobrien		     && eligible_for_annul_false (insn, *pslots_filled, trial, flags)
264052284Sobrien		   : check_annul_list_true_false (1, delay_list)
264152284Sobrien		     && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
264218334Speter		{
264318334Speter		  rtx temp;
264418334Speter
264518334Speter		  must_annul = 1;
264618334Speter		winner:
264718334Speter
264818334Speter#ifdef HAVE_cc0
264918334Speter		  if (reg_mentioned_p (cc0_rtx, pat))
265018334Speter		    link_cc0_insns (trial);
265118334Speter#endif
265218334Speter
265318334Speter		  /* If we own this thread, delete the insn.  If this is the
265418334Speter		     destination of a branch, show that a basic block status
265518334Speter		     may have been updated.  In any case, mark the new
265618334Speter		     starting point of this thread.  */
265718334Speter		  if (own_thread)
265818334Speter		    {
265990075Sobrien		      rtx note;
266090075Sobrien
266118334Speter		      update_block (trial, thread);
266250397Sobrien		      if (trial == thread)
266350397Sobrien			{
266450397Sobrien			  thread = next_active_insn (thread);
266550397Sobrien			  if (new_thread == trial)
266650397Sobrien			    new_thread = thread;
266750397Sobrien			}
266890075Sobrien
266990075Sobrien		      /* We are moving this insn, not deleting it.  We must
267090075Sobrien			 temporarily increment the use count on any referenced
267190075Sobrien			 label lest it be deleted by delete_related_insns.  */
267290075Sobrien		      note = find_reg_note (trial, REG_LABEL, 0);
267396263Sobrien		      /* REG_LABEL could be NOTE_INSN_DELETED_LABEL too.  */
2674169689Skan		      if (note && LABEL_P (XEXP (note, 0)))
267590075Sobrien			LABEL_NUSES (XEXP (note, 0))++;
267690075Sobrien
267790075Sobrien		      delete_related_insns (trial);
267890075Sobrien
2679169689Skan		      if (note && LABEL_P (XEXP (note, 0)))
268090075Sobrien			LABEL_NUSES (XEXP (note, 0))--;
268118334Speter		    }
268218334Speter		  else
268318334Speter		    new_thread = next_active_insn (trial);
268418334Speter
268518334Speter		  temp = own_thread ? trial : copy_rtx (trial);
268618334Speter		  if (thread_if_true)
268718334Speter		    INSN_FROM_TARGET_P (temp) = 1;
268818334Speter
268918334Speter		  delay_list = add_to_delay_list (temp, delay_list);
269018334Speter
269118334Speter		  if (slots_to_fill == ++(*pslots_filled))
269218334Speter		    {
269318334Speter		      /* Even though we have filled all the slots, we
269418334Speter			 may be branching to a location that has a
269518334Speter			 redundant insn.  Skip any if so.  */
269618334Speter		      while (new_thread && ! own_thread
269718334Speter			     && ! insn_sets_resource_p (new_thread, &set, 1)
269818334Speter			     && ! insn_sets_resource_p (new_thread, &needed, 1)
269918334Speter			     && ! insn_references_resource_p (new_thread,
270018334Speter							      &set, 1)
270150397Sobrien			     && (prior_insn
270250397Sobrien				 = redundant_insn (new_thread, insn,
270350397Sobrien						   delay_list)))
270450397Sobrien			{
270550397Sobrien			  /* We know we do not own the thread, so no need
270650397Sobrien			     to call update_block and delete_insn.  */
270750397Sobrien			  fix_reg_dead_note (prior_insn, insn);
270850397Sobrien			  update_reg_unused_notes (prior_insn, new_thread);
270950397Sobrien			  new_thread = next_active_insn (new_thread);
271050397Sobrien			}
271118334Speter		      break;
271218334Speter		    }
271318334Speter
271418334Speter		  continue;
271518334Speter		}
271618334Speter	    }
271718334Speter	}
271818334Speter
271918334Speter      /* This insn can't go into a delay slot.  */
272018334Speter      lose = 1;
272190075Sobrien      mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
272218334Speter      mark_referenced_resources (trial, &needed, 1);
272318334Speter
272418334Speter      /* Ensure we don't put insns between the setting of cc and the comparison
272518334Speter	 by moving a setting of cc into an earlier delay slot since these insns
272618334Speter	 could clobber the condition code.  */
272718334Speter      set.cc = 1;
272818334Speter
272918334Speter      /* If this insn is a register-register copy and the next insn has
273018334Speter	 a use of our destination, change it to use our source.  That way,
273118334Speter	 it will become a candidate for our delay slot the next time
273218334Speter	 through this loop.  This case occurs commonly in loops that
273318334Speter	 scan a list.
273418334Speter
273518334Speter	 We could check for more complex cases than those tested below,
273618334Speter	 but it doesn't seem worth it.  It might also be a good idea to try
273718334Speter	 to swap the two insns.  That might do better.
273818334Speter
273918334Speter	 We can't do this if the next insn modifies our destination, because
274018334Speter	 that would make the replacement into the insn invalid.  We also can't
274118334Speter	 do this if it modifies our source, because it might be an earlyclobber
274218334Speter	 operand.  This latter test also prevents updating the contents of
2743132718Skan	 a PRE_INC.  We also can't do this if there's overlap of source and
2744132718Skan	 destination.  Overlap may happen for larger-than-register-size modes.  */
274518334Speter
2746169689Skan      if (NONJUMP_INSN_P (trial) && GET_CODE (pat) == SET
2747169689Skan	  && REG_P (SET_SRC (pat))
2748169689Skan	  && REG_P (SET_DEST (pat))
2749132718Skan	  && !reg_overlap_mentioned_p (SET_DEST (pat), SET_SRC (pat)))
275018334Speter	{
275118334Speter	  rtx next = next_nonnote_insn (trial);
275218334Speter
2753169689Skan	  if (next && NONJUMP_INSN_P (next)
275418334Speter	      && GET_CODE (PATTERN (next)) != USE
275518334Speter	      && ! reg_set_p (SET_DEST (pat), next)
275618334Speter	      && ! reg_set_p (SET_SRC (pat), next)
275790075Sobrien	      && reg_referenced_p (SET_DEST (pat), PATTERN (next))
275890075Sobrien	      && ! modified_in_p (SET_DEST (pat), next))
275918334Speter	    validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
276018334Speter	}
276118334Speter    }
276218334Speter
276318334Speter  /* If we stopped on a branch insn that has delay slots, see if we can
276418334Speter     steal some of the insns in those slots.  */
2765169689Skan  if (trial && NONJUMP_INSN_P (trial)
276618334Speter      && GET_CODE (PATTERN (trial)) == SEQUENCE
2767169689Skan      && JUMP_P (XVECEXP (PATTERN (trial), 0, 0)))
276818334Speter    {
276918334Speter      /* If this is the `true' thread, we will want to follow the jump,
277018334Speter	 so we can only do this if we have taken everything up to here.  */
277152284Sobrien      if (thread_if_true && trial == new_thread)
277290075Sobrien	{
277390075Sobrien	  delay_list
277490075Sobrien	    = steal_delay_list_from_target (insn, condition, PATTERN (trial),
277590075Sobrien					    delay_list, &set, &needed,
277690075Sobrien					    &opposite_needed, slots_to_fill,
277790075Sobrien					    pslots_filled, &must_annul,
277890075Sobrien					    &new_thread);
277990075Sobrien	  /* If we owned the thread and are told that it branched
278090075Sobrien	     elsewhere, make sure we own the thread at the new location.  */
278190075Sobrien	  if (own_thread && trial != new_thread)
278290075Sobrien	    own_thread = own_thread_p (new_thread, new_thread, 0);
278390075Sobrien	}
278418334Speter      else if (! thread_if_true)
278518334Speter	delay_list
278618334Speter	  = steal_delay_list_from_fallthrough (insn, condition,
278718334Speter					       PATTERN (trial),
278818334Speter					       delay_list, &set, &needed,
278918334Speter					       &opposite_needed, slots_to_fill,
279018334Speter					       pslots_filled, &must_annul);
279118334Speter    }
279218334Speter
279318334Speter  /* If we haven't found anything for this delay slot and it is very
279418334Speter     likely that the branch will be taken, see if the insn at our target
279518334Speter     increments or decrements a register with an increment that does not
279618334Speter     depend on the destination register.  If so, try to place the opposite
279718334Speter     arithmetic insn after the jump insn and put the arithmetic insn in the
279818334Speter     delay slot.  If we can't do this, return.  */
279950397Sobrien  if (delay_list == 0 && likely && new_thread
2800169689Skan      && NONJUMP_INSN_P (new_thread)
280150397Sobrien      && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
280250397Sobrien      && asm_noperands (PATTERN (new_thread)) < 0)
280318334Speter    {
280418334Speter      rtx pat = PATTERN (new_thread);
280518334Speter      rtx dest;
280618334Speter      rtx src;
280718334Speter
280818334Speter      trial = new_thread;
280918334Speter      pat = PATTERN (trial);
281018334Speter
2811169689Skan      if (!NONJUMP_INSN_P (trial)
281296263Sobrien	  || GET_CODE (pat) != SET
281396263Sobrien	  || ! eligible_for_delay (insn, 0, trial, flags)
281496263Sobrien	  || can_throw_internal (trial))
281518334Speter	return 0;
281618334Speter
281718334Speter      dest = SET_DEST (pat), src = SET_SRC (pat);
281818334Speter      if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
281918334Speter	  && rtx_equal_p (XEXP (src, 0), dest)
2820169689Skan	  && (!FLOAT_MODE_P (GET_MODE (src))
2821169689Skan	      || flag_unsafe_math_optimizations)
282290075Sobrien	  && ! reg_overlap_mentioned_p (dest, XEXP (src, 1))
282390075Sobrien	  && ! side_effects_p (pat))
282418334Speter	{
282518334Speter	  rtx other = XEXP (src, 1);
282618334Speter	  rtx new_arith;
282718334Speter	  rtx ninsn;
282818334Speter
282918334Speter	  /* If this is a constant adjustment, use the same code with
283018334Speter	     the negated constant.  Otherwise, reverse the sense of the
283118334Speter	     arithmetic.  */
283218334Speter	  if (GET_CODE (other) == CONST_INT)
283350397Sobrien	    new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
283450397Sobrien					negate_rtx (GET_MODE (src), other));
283518334Speter	  else
283650397Sobrien	    new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
283750397Sobrien					GET_MODE (src), dest, other);
283818334Speter
283950397Sobrien	  ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith),
284018334Speter				   insn);
284118334Speter
284218334Speter	  if (recog_memoized (ninsn) < 0
284352284Sobrien	      || (extract_insn (ninsn), ! constrain_operands (1)))
284418334Speter	    {
284590075Sobrien	      delete_related_insns (ninsn);
284618334Speter	      return 0;
284718334Speter	    }
284818334Speter
284918334Speter	  if (own_thread)
285018334Speter	    {
285118334Speter	      update_block (trial, thread);
285250397Sobrien	      if (trial == thread)
285350397Sobrien		{
285450397Sobrien		  thread = next_active_insn (thread);
285550397Sobrien		  if (new_thread == trial)
285650397Sobrien		    new_thread = thread;
285750397Sobrien		}
285890075Sobrien	      delete_related_insns (trial);
285918334Speter	    }
286018334Speter	  else
286118334Speter	    new_thread = next_active_insn (trial);
286218334Speter
286318334Speter	  ninsn = own_thread ? trial : copy_rtx (trial);
286418334Speter	  if (thread_if_true)
286518334Speter	    INSN_FROM_TARGET_P (ninsn) = 1;
286618334Speter
286718334Speter	  delay_list = add_to_delay_list (ninsn, NULL_RTX);
286818334Speter	  (*pslots_filled)++;
286918334Speter	}
287018334Speter    }
287118334Speter
287218334Speter  if (delay_list && must_annul)
287318334Speter    INSN_ANNULLED_BRANCH_P (insn) = 1;
287418334Speter
287518334Speter  /* If we are to branch into the middle of this thread, find an appropriate
287618334Speter     label or make a new one if none, and redirect INSN to it.  If we hit the
287718334Speter     end of the function, use the end-of-function label.  */
287818334Speter  if (new_thread != thread)
287918334Speter    {
288018334Speter      rtx label;
288118334Speter
2882169689Skan      gcc_assert (thread_if_true);
288318334Speter
2884169689Skan      if (new_thread && JUMP_P (new_thread)
288518334Speter	  && (simplejump_p (new_thread)
288618334Speter	      || GET_CODE (PATTERN (new_thread)) == RETURN)
288718334Speter	  && redirect_with_delay_list_safe_p (insn,
288818334Speter					      JUMP_LABEL (new_thread),
288918334Speter					      delay_list))
289018334Speter	new_thread = follow_jumps (JUMP_LABEL (new_thread));
289118334Speter
289218334Speter      if (new_thread == 0)
289318334Speter	label = find_end_label ();
2894169689Skan      else if (LABEL_P (new_thread))
289518334Speter	label = new_thread;
289618334Speter      else
289718334Speter	label = get_label_before (new_thread);
289818334Speter
2899169689Skan      if (label)
2900169689Skan	reorg_redirect_jump (insn, label);
290118334Speter    }
290218334Speter
290318334Speter  return delay_list;
290418334Speter}
290518334Speter
290618334Speter/* Make another attempt to find insns to place in delay slots.
290718334Speter
290818334Speter   We previously looked for insns located in front of the delay insn
290918334Speter   and, for non-jump delay insns, located behind the delay insn.
291018334Speter
291118334Speter   Here only try to schedule jump insns and try to move insns from either
291218334Speter   the target or the following insns into the delay slot.  If annulling is
291318334Speter   supported, we will be likely to do this.  Otherwise, we can do this only
291418334Speter   if safe.  */
291518334Speter
291618334Speterstatic void
2917132718Skanfill_eager_delay_slots (void)
291818334Speter{
291990075Sobrien  rtx insn;
292090075Sobrien  int i;
292118334Speter  int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
292218334Speter
292318334Speter  for (i = 0; i < num_unfilled_slots; i++)
292418334Speter    {
292518334Speter      rtx condition;
292618334Speter      rtx target_label, insn_at_target, fallthrough_insn;
292718334Speter      rtx delay_list = 0;
292818334Speter      int own_target;
292918334Speter      int own_fallthrough;
293018334Speter      int prediction, slots_to_fill, slots_filled;
293118334Speter
293218334Speter      insn = unfilled_slots_base[i];
293318334Speter      if (insn == 0
293418334Speter	  || INSN_DELETED_P (insn)
2935169689Skan	  || !JUMP_P (insn)
293618334Speter	  || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
293718334Speter	continue;
293818334Speter
293918334Speter      slots_to_fill = num_delay_slots (insn);
294050397Sobrien      /* Some machine description have defined instructions to have
294150397Sobrien	 delay slots only in certain circumstances which may depend on
294250397Sobrien	 nearby insns (which change due to reorg's actions).
294350397Sobrien
2944132718Skan	 For example, the PA port normally has delay slots for unconditional
294550397Sobrien	 jumps.
294650397Sobrien
294750397Sobrien	 However, the PA port claims such jumps do not have a delay slot
294850397Sobrien	 if they are immediate successors of certain CALL_INSNs.  This
294950397Sobrien	 allows the port to favor filling the delay slot of the call with
295050397Sobrien	 the unconditional jump.  */
295118334Speter      if (slots_to_fill == 0)
295290075Sobrien	continue;
295318334Speter
295418334Speter      slots_filled = 0;
295518334Speter      target_label = JUMP_LABEL (insn);
295618334Speter      condition = get_branch_condition (insn, target_label);
295718334Speter
295818334Speter      if (condition == 0)
295918334Speter	continue;
296018334Speter
296118334Speter      /* Get the next active fallthrough and target insns and see if we own
296218334Speter	 them.  Then see whether the branch is likely true.  We don't need
296318334Speter	 to do a lot of this for unconditional branches.  */
296418334Speter
296518334Speter      insn_at_target = next_active_insn (target_label);
296618334Speter      own_target = own_thread_p (target_label, target_label, 0);
296718334Speter
296818334Speter      if (condition == const_true_rtx)
296918334Speter	{
297018334Speter	  own_fallthrough = 0;
297118334Speter	  fallthrough_insn = 0;
297218334Speter	  prediction = 2;
297318334Speter	}
297418334Speter      else
297518334Speter	{
297618334Speter	  fallthrough_insn = next_active_insn (insn);
297718334Speter	  own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
297818334Speter	  prediction = mostly_true_jump (insn, condition);
297918334Speter	}
298018334Speter
298118334Speter      /* If this insn is expected to branch, first try to get insns from our
298290075Sobrien	 target, then our fallthrough insns.  If it is not expected to branch,
298318334Speter	 try the other order.  */
298418334Speter
298518334Speter      if (prediction > 0)
298618334Speter	{
298718334Speter	  delay_list
298818334Speter	    = fill_slots_from_thread (insn, condition, insn_at_target,
298918334Speter				      fallthrough_insn, prediction == 2, 1,
299050397Sobrien				      own_target,
299150397Sobrien				      slots_to_fill, &slots_filled, delay_list);
299218334Speter
299318334Speter	  if (delay_list == 0 && own_fallthrough)
299418334Speter	    {
299518334Speter	      /* Even though we didn't find anything for delay slots,
299618334Speter		 we might have found a redundant insn which we deleted
299718334Speter		 from the thread that was filled.  So we have to recompute
299818334Speter		 the next insn at the target.  */
299918334Speter	      target_label = JUMP_LABEL (insn);
300018334Speter	      insn_at_target = next_active_insn (target_label);
300118334Speter
300218334Speter	      delay_list
300318334Speter		= fill_slots_from_thread (insn, condition, fallthrough_insn,
300418334Speter					  insn_at_target, 0, 0,
300550397Sobrien					  own_fallthrough,
300650397Sobrien					  slots_to_fill, &slots_filled,
300750397Sobrien					  delay_list);
300818334Speter	    }
300918334Speter	}
301018334Speter      else
301118334Speter	{
301218334Speter	  if (own_fallthrough)
301318334Speter	    delay_list
301418334Speter	      = fill_slots_from_thread (insn, condition, fallthrough_insn,
301518334Speter					insn_at_target, 0, 0,
301650397Sobrien					own_fallthrough,
301750397Sobrien					slots_to_fill, &slots_filled,
301850397Sobrien					delay_list);
301918334Speter
302018334Speter	  if (delay_list == 0)
302118334Speter	    delay_list
302218334Speter	      = fill_slots_from_thread (insn, condition, insn_at_target,
302318334Speter					next_active_insn (insn), 0, 1,
302450397Sobrien					own_target,
302550397Sobrien					slots_to_fill, &slots_filled,
302650397Sobrien					delay_list);
302718334Speter	}
302818334Speter
302918334Speter      if (delay_list)
303018334Speter	unfilled_slots_base[i]
303150397Sobrien	  = emit_delay_sequence (insn, delay_list, slots_filled);
303218334Speter
303318334Speter      if (slots_to_fill == slots_filled)
303418334Speter	unfilled_slots_base[i] = 0;
303518334Speter
303618334Speter      note_delay_statistics (slots_filled, 1);
303718334Speter    }
303818334Speter}
303918334Speter
304018334Speter/* Once we have tried two ways to fill a delay slot, make a pass over the
304118334Speter   code to try to improve the results and to do such things as more jump
304218334Speter   threading.  */
304318334Speter
304418334Speterstatic void
3045132718Skanrelax_delay_slots (rtx first)
304618334Speter{
304790075Sobrien  rtx insn, next, pat;
304890075Sobrien  rtx trial, delay_insn, target_label;
304918334Speter
305018334Speter  /* Look at every JUMP_INSN and see if we can improve it.  */
305118334Speter  for (insn = first; insn; insn = next)
305218334Speter    {
305318334Speter      rtx other;
305418334Speter
305518334Speter      next = next_active_insn (insn);
305618334Speter
305718334Speter      /* If this is a jump insn, see if it now jumps to a jump, jumps to
305818334Speter	 the next insn, or jumps to a label that is not the last of a
305918334Speter	 group of consecutive labels.  */
3060169689Skan      if (JUMP_P (insn)
306118334Speter	  && (condjump_p (insn) || condjump_in_parallel_p (insn))
306218334Speter	  && (target_label = JUMP_LABEL (insn)) != 0)
306318334Speter	{
3064169689Skan	  target_label = skip_consecutive_labels (follow_jumps (target_label));
306518334Speter	  if (target_label == 0)
306618334Speter	    target_label = find_end_label ();
306718334Speter
3068169689Skan	  if (target_label && next_active_insn (target_label) == next
306918334Speter	      && ! condjump_in_parallel_p (insn))
307018334Speter	    {
307118334Speter	      delete_jump (insn);
307218334Speter	      continue;
307318334Speter	    }
307418334Speter
3075169689Skan	  if (target_label && target_label != JUMP_LABEL (insn))
307618334Speter	    reorg_redirect_jump (insn, target_label);
307718334Speter
3078169689Skan	  /* See if this jump conditionally branches around an unconditional
3079169689Skan	     jump.  If so, invert this jump and point it to the target of the
308018334Speter	     second jump.  */
3081169689Skan	  if (next && JUMP_P (next)
3082169689Skan	      && any_condjump_p (insn)
308318334Speter	      && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3084169689Skan	      && target_label
308518334Speter	      && next_active_insn (target_label) == next_active_insn (next)
308618334Speter	      && no_labels_between_p (insn, next))
308718334Speter	    {
308818334Speter	      rtx label = JUMP_LABEL (next);
308918334Speter
309018334Speter	      /* Be careful how we do this to avoid deleting code or
309118334Speter		 labels that are momentarily dead.  See similar optimization
309218334Speter		 in jump.c.
309318334Speter
309418334Speter		 We also need to ensure we properly handle the case when
309518334Speter		 invert_jump fails.  */
309618334Speter
309718334Speter	      ++LABEL_NUSES (target_label);
309818334Speter	      if (label)
309918334Speter		++LABEL_NUSES (label);
310018334Speter
310190075Sobrien	      if (invert_jump (insn, label, 1))
310218334Speter		{
310390075Sobrien		  delete_related_insns (next);
310418334Speter		  next = insn;
310518334Speter		}
310618334Speter
310718334Speter	      if (label)
310818334Speter		--LABEL_NUSES (label);
310918334Speter
311018334Speter	      if (--LABEL_NUSES (target_label) == 0)
311190075Sobrien		delete_related_insns (target_label);
311218334Speter
311318334Speter	      continue;
311418334Speter	    }
311518334Speter	}
311690075Sobrien
311718334Speter      /* If this is an unconditional jump and the previous insn is a
311818334Speter	 conditional jump, try reversing the condition of the previous
311918334Speter	 insn and swapping our targets.  The next pass might be able to
312018334Speter	 fill the slots.
312118334Speter
312218334Speter	 Don't do this if we expect the conditional branch to be true, because
312318334Speter	 we would then be making the more common case longer.  */
312418334Speter
3125169689Skan      if (JUMP_P (insn)
312618334Speter	  && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
312718334Speter	  && (other = prev_active_insn (insn)) != 0
3128169689Skan	  && any_condjump_p (other)
312918334Speter	  && no_labels_between_p (other, insn)
313052284Sobrien	  && 0 > mostly_true_jump (other,
313118334Speter				   get_branch_condition (other,
313218334Speter							 JUMP_LABEL (other))))
313318334Speter	{
313418334Speter	  rtx other_target = JUMP_LABEL (other);
313518334Speter	  target_label = JUMP_LABEL (insn);
313618334Speter
313790075Sobrien	  if (invert_jump (other, target_label, 0))
313818334Speter	    reorg_redirect_jump (insn, other_target);
313918334Speter	}
314018334Speter
314118334Speter      /* Now look only at cases where we have filled a delay slot.  */
3142169689Skan      if (!NONJUMP_INSN_P (insn)
314318334Speter	  || GET_CODE (PATTERN (insn)) != SEQUENCE)
314418334Speter	continue;
314518334Speter
314618334Speter      pat = PATTERN (insn);
314718334Speter      delay_insn = XVECEXP (pat, 0, 0);
314818334Speter
314918334Speter      /* See if the first insn in the delay slot is redundant with some
315018334Speter	 previous insn.  Remove it from the delay slot if so; then set up
315118334Speter	 to reprocess this insn.  */
315218334Speter      if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
315318334Speter	{
315418334Speter	  delete_from_delay_slot (XVECEXP (pat, 0, 1));
315518334Speter	  next = prev_active_insn (next);
315618334Speter	  continue;
315718334Speter	}
315818334Speter
315952284Sobrien      /* See if we have a RETURN insn with a filled delay slot followed
316052284Sobrien	 by a RETURN insn with an unfilled a delay slot.  If so, we can delete
3161169689Skan	 the first RETURN (but not its delay insn).  This gives the same
316252284Sobrien	 effect in fewer instructions.
316352284Sobrien
316452284Sobrien	 Only do so if optimizing for size since this results in slower, but
316552284Sobrien	 smaller code.  */
316652284Sobrien      if (optimize_size
316752284Sobrien	  && GET_CODE (PATTERN (delay_insn)) == RETURN
316852284Sobrien	  && next
3169169689Skan	  && JUMP_P (next)
317052284Sobrien	  && GET_CODE (PATTERN (next)) == RETURN)
317152284Sobrien	{
3172117395Skan	  rtx after;
317352284Sobrien	  int i;
317452284Sobrien
317552284Sobrien	  /* Delete the RETURN and just execute the delay list insns.
317652284Sobrien
317752284Sobrien	     We do this by deleting the INSN containing the SEQUENCE, then
317852284Sobrien	     re-emitting the insns separately, and then deleting the RETURN.
317952284Sobrien	     This allows the count of the jump target to be properly
318052284Sobrien	     decremented.  */
318152284Sobrien
318252284Sobrien	  /* Clear the from target bit, since these insns are no longer
318352284Sobrien	     in delay slots.  */
318452284Sobrien	  for (i = 0; i < XVECLEN (pat, 0); i++)
318552284Sobrien	    INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
318652284Sobrien
318752284Sobrien	  trial = PREV_INSN (insn);
318890075Sobrien	  delete_related_insns (insn);
3189169689Skan	  gcc_assert (GET_CODE (pat) == SEQUENCE);
3190117395Skan	  after = trial;
3191117395Skan	  for (i = 0; i < XVECLEN (pat, 0); i++)
3192117395Skan	    {
3193117395Skan	      rtx this_insn = XVECEXP (pat, 0, i);
3194117395Skan	      add_insn_after (this_insn, after);
3195117395Skan	      after = this_insn;
3196117395Skan	    }
319752284Sobrien	  delete_scheduled_jump (delay_insn);
319852284Sobrien	  continue;
319952284Sobrien	}
320052284Sobrien
320118334Speter      /* Now look only at the cases where we have a filled JUMP_INSN.  */
3202169689Skan      if (!JUMP_P (XVECEXP (PATTERN (insn), 0, 0))
320318334Speter	  || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
320418334Speter		|| condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
320518334Speter	continue;
320618334Speter
320718334Speter      target_label = JUMP_LABEL (delay_insn);
320818334Speter
320918334Speter      if (target_label)
321018334Speter	{
321118334Speter	  /* If this jump goes to another unconditional jump, thread it, but
321218334Speter	     don't convert a jump into a RETURN here.  */
3213169689Skan	  trial = skip_consecutive_labels (follow_jumps (target_label));
3214169689Skan	  if (trial == 0)
321518334Speter	    trial = find_end_label ();
321618334Speter
3217169689Skan	  if (trial && trial != target_label
321818334Speter	      && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
321918334Speter	    {
322018334Speter	      reorg_redirect_jump (delay_insn, trial);
322118334Speter	      target_label = trial;
322218334Speter	    }
322318334Speter
322418334Speter	  /* If the first insn at TARGET_LABEL is redundant with a previous
322518334Speter	     insn, redirect the jump to the following insn process again.  */
322618334Speter	  trial = next_active_insn (target_label);
322718334Speter	  if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
322896263Sobrien	      && redundant_insn (trial, insn, 0)
322996263Sobrien	      && ! can_throw_internal (trial))
323018334Speter	    {
323150397Sobrien	      /* Figure out where to emit the special USE insn so we don't
323250397Sobrien		 later incorrectly compute register live/death info.  */
3233169689Skan	      rtx tmp = next_active_insn (trial);
323450397Sobrien	      if (tmp == 0)
323550397Sobrien		tmp = find_end_label ();
323650397Sobrien
3237169689Skan	      if (tmp)
3238169689Skan	        {
3239169689Skan		  /* Insert the special USE insn and update dataflow info.  */
3240169689Skan		  update_block (trial, tmp);
324150397Sobrien
3242169689Skan		  /* Now emit a label before the special USE insn, and
3243169689Skan		     redirect our jump to the new label.  */
3244169689Skan		  target_label = get_label_before (PREV_INSN (tmp));
3245169689Skan		  reorg_redirect_jump (delay_insn, target_label);
3246169689Skan		  next = insn;
3247169689Skan		  continue;
3248169689Skan		}
324918334Speter	    }
325018334Speter
325118334Speter	  /* Similarly, if it is an unconditional jump with one insn in its
325218334Speter	     delay list and that insn is redundant, thread the jump.  */
325318334Speter	  if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
325418334Speter	      && XVECLEN (PATTERN (trial), 0) == 2
3255169689Skan	      && JUMP_P (XVECEXP (PATTERN (trial), 0, 0))
325618334Speter	      && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
325718334Speter		  || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
325818334Speter	      && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
325918334Speter	    {
326018334Speter	      target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
326118334Speter	      if (target_label == 0)
326218334Speter		target_label = find_end_label ();
326318334Speter
3264169689Skan	      if (target_label
3265169689Skan	          && redirect_with_delay_slots_safe_p (delay_insn, target_label,
3266169689Skan						       insn))
326718334Speter		{
326818334Speter		  reorg_redirect_jump (delay_insn, target_label);
326918334Speter		  next = insn;
327018334Speter		  continue;
327118334Speter		}
327218334Speter	    }
327318334Speter	}
327418334Speter
327518334Speter      if (! INSN_ANNULLED_BRANCH_P (delay_insn)
327618334Speter	  && prev_active_insn (target_label) == insn
327718334Speter	  && ! condjump_in_parallel_p (delay_insn)
327818334Speter#ifdef HAVE_cc0
327918334Speter	  /* If the last insn in the delay slot sets CC0 for some insn,
328018334Speter	     various code assumes that it is in a delay slot.  We could
328118334Speter	     put it back where it belonged and delete the register notes,
328218334Speter	     but it doesn't seem worthwhile in this uncommon case.  */
328318334Speter	  && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
328418334Speter			      REG_CC_USER, NULL_RTX)
328518334Speter#endif
328618334Speter	  )
328718334Speter	{
3288117395Skan	  rtx after;
328918334Speter	  int i;
329018334Speter
329118334Speter	  /* All this insn does is execute its delay list and jump to the
329218334Speter	     following insn.  So delete the jump and just execute the delay
329318334Speter	     list insns.
329418334Speter
329518334Speter	     We do this by deleting the INSN containing the SEQUENCE, then
329618334Speter	     re-emitting the insns separately, and then deleting the jump.
329718334Speter	     This allows the count of the jump target to be properly
329818334Speter	     decremented.  */
329918334Speter
330018334Speter	  /* Clear the from target bit, since these insns are no longer
330118334Speter	     in delay slots.  */
330218334Speter	  for (i = 0; i < XVECLEN (pat, 0); i++)
330318334Speter	    INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
330418334Speter
330518334Speter	  trial = PREV_INSN (insn);
330690075Sobrien	  delete_related_insns (insn);
3307169689Skan	  gcc_assert (GET_CODE (pat) == SEQUENCE);
3308117395Skan	  after = trial;
3309117395Skan	  for (i = 0; i < XVECLEN (pat, 0); i++)
3310117395Skan	    {
3311117395Skan	      rtx this_insn = XVECEXP (pat, 0, i);
3312117395Skan	      add_insn_after (this_insn, after);
3313117395Skan	      after = this_insn;
3314117395Skan	    }
331518334Speter	  delete_scheduled_jump (delay_insn);
331618334Speter	  continue;
331718334Speter	}
331818334Speter
331918334Speter      /* See if this is an unconditional jump around a single insn which is
332018334Speter	 identical to the one in its delay slot.  In this case, we can just
332118334Speter	 delete the branch and the insn in its delay slot.  */
3322169689Skan      if (next && NONJUMP_INSN_P (next)
332318334Speter	  && prev_label (next_active_insn (next)) == target_label
332418334Speter	  && simplejump_p (insn)
332518334Speter	  && XVECLEN (pat, 0) == 2
332618334Speter	  && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
332718334Speter	{
332890075Sobrien	  delete_related_insns (insn);
332918334Speter	  continue;
333018334Speter	}
333118334Speter
3332169689Skan      /* See if this jump (with its delay slots) conditionally branches
3333169689Skan	 around an unconditional jump (without delay slots).  If so, invert
3334169689Skan	 this jump and point it to the target of the second jump.  We cannot
3335169689Skan	 do this for annulled jumps, though.  Again, don't convert a jump to
3336169689Skan	 a RETURN here.  */
333718334Speter      if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3338169689Skan	  && any_condjump_p (delay_insn)
3339169689Skan	  && next && JUMP_P (next)
334018334Speter	  && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
334118334Speter	  && next_active_insn (target_label) == next_active_insn (next)
334218334Speter	  && no_labels_between_p (insn, next))
334318334Speter	{
334418334Speter	  rtx label = JUMP_LABEL (next);
334518334Speter	  rtx old_label = JUMP_LABEL (delay_insn);
334618334Speter
334718334Speter	  if (label == 0)
334818334Speter	    label = find_end_label ();
334918334Speter
335090075Sobrien	  /* find_end_label can generate a new label. Check this first.  */
3351169689Skan	  if (label
3352169689Skan	      && no_labels_between_p (insn, next)
335390075Sobrien	      && redirect_with_delay_slots_safe_p (delay_insn, label, insn))
335418334Speter	    {
335518334Speter	      /* Be careful how we do this to avoid deleting code or labels
335618334Speter		 that are momentarily dead.  See similar optimization in
335718334Speter		 jump.c  */
335818334Speter	      if (old_label)
335918334Speter		++LABEL_NUSES (old_label);
336018334Speter
336190075Sobrien	      if (invert_jump (delay_insn, label, 1))
336218334Speter		{
336318334Speter		  int i;
336418334Speter
336518334Speter		  /* Must update the INSN_FROM_TARGET_P bits now that
336618334Speter		     the branch is reversed, so that mark_target_live_regs
336718334Speter		     will handle the delay slot insn correctly.  */
336818334Speter		  for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
336918334Speter		    {
337018334Speter		      rtx slot = XVECEXP (PATTERN (insn), 0, i);
337118334Speter		      INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
337218334Speter		    }
337318334Speter
337490075Sobrien		  delete_related_insns (next);
337518334Speter		  next = insn;
337618334Speter		}
337718334Speter
337818334Speter	      if (old_label && --LABEL_NUSES (old_label) == 0)
337990075Sobrien		delete_related_insns (old_label);
338018334Speter	      continue;
338118334Speter	    }
338218334Speter	}
338318334Speter
338418334Speter      /* If we own the thread opposite the way this insn branches, see if we
338518334Speter	 can merge its delay slots with following insns.  */
338618334Speter      if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
338718334Speter	  && own_thread_p (NEXT_INSN (insn), 0, 1))
338818334Speter	try_merge_delay_insns (insn, next);
338918334Speter      else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
339018334Speter	       && own_thread_p (target_label, target_label, 0))
339118334Speter	try_merge_delay_insns (insn, next_active_insn (target_label));
339218334Speter
339318334Speter      /* If we get here, we haven't deleted INSN.  But we may have deleted
339418334Speter	 NEXT, so recompute it.  */
339518334Speter      next = next_active_insn (insn);
339618334Speter    }
339718334Speter}
339818334Speter
339918334Speter#ifdef HAVE_return
340018334Speter
340118334Speter/* Look for filled jumps to the end of function label.  We can try to convert
340218334Speter   them into RETURN insns if the insns in the delay slot are valid for the
340318334Speter   RETURN as well.  */
340418334Speter
340518334Speterstatic void
3406132718Skanmake_return_insns (rtx first)
340718334Speter{
340818334Speter  rtx insn, jump_insn, pat;
340918334Speter  rtx real_return_label = end_of_function_label;
341018334Speter  int slots, i;
341118334Speter
3412117395Skan#ifdef DELAY_SLOTS_FOR_EPILOGUE
3413117395Skan  /* If a previous pass filled delay slots in the epilogue, things get a
3414117395Skan     bit more complicated, as those filler insns would generally (without
3415117395Skan     data flow analysis) have to be executed after any existing branch
3416117395Skan     delay slot filler insns.  It is also unknown whether such a
3417117395Skan     transformation would actually be profitable.  Note that the existing
3418117395Skan     code only cares for branches with (some) filled delay slots.  */
3419117395Skan  if (current_function_epilogue_delay_list != NULL)
3420117395Skan    return;
3421117395Skan#endif
3422117395Skan
342318334Speter  /* See if there is a RETURN insn in the function other than the one we
342418334Speter     made for END_OF_FUNCTION_LABEL.  If so, set up anything we can't change
342518334Speter     into a RETURN to jump to it.  */
342618334Speter  for (insn = first; insn; insn = NEXT_INSN (insn))
3427169689Skan    if (JUMP_P (insn) && GET_CODE (PATTERN (insn)) == RETURN)
342818334Speter      {
342918334Speter	real_return_label = get_label_before (insn);
343018334Speter	break;
343118334Speter      }
343290075Sobrien
343318334Speter  /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
343418334Speter     was equal to END_OF_FUNCTION_LABEL.  */
343518334Speter  LABEL_NUSES (real_return_label)++;
343618334Speter
343718334Speter  /* Clear the list of insns to fill so we can use it.  */
343818334Speter  obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
343918334Speter
344018334Speter  for (insn = first; insn; insn = NEXT_INSN (insn))
344118334Speter    {
344218334Speter      int flags;
344318334Speter
344418334Speter      /* Only look at filled JUMP_INSNs that go to the end of function
344518334Speter	 label.  */
3446169689Skan      if (!NONJUMP_INSN_P (insn)
344718334Speter	  || GET_CODE (PATTERN (insn)) != SEQUENCE
3448169689Skan	  || !JUMP_P (XVECEXP (PATTERN (insn), 0, 0))
344918334Speter	  || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
345018334Speter	continue;
345118334Speter
345218334Speter      pat = PATTERN (insn);
345318334Speter      jump_insn = XVECEXP (pat, 0, 0);
345418334Speter
345518334Speter      /* If we can't make the jump into a RETURN, try to redirect it to the best
345618334Speter	 RETURN and go on to the next insn.  */
345718334Speter      if (! reorg_redirect_jump (jump_insn, NULL_RTX))
345818334Speter	{
345918334Speter	  /* Make sure redirecting the jump will not invalidate the delay
346018334Speter	     slot insns.  */
346118334Speter	  if (redirect_with_delay_slots_safe_p (jump_insn,
346218334Speter						real_return_label,
346318334Speter						insn))
346418334Speter	    reorg_redirect_jump (jump_insn, real_return_label);
346518334Speter	  continue;
346618334Speter	}
346718334Speter
346818334Speter      /* See if this RETURN can accept the insns current in its delay slot.
346918334Speter	 It can if it has more or an equal number of slots and the contents
347018334Speter	 of each is valid.  */
347118334Speter
347218334Speter      flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
347318334Speter      slots = num_delay_slots (jump_insn);
347418334Speter      if (slots >= XVECLEN (pat, 0) - 1)
347518334Speter	{
347618334Speter	  for (i = 1; i < XVECLEN (pat, 0); i++)
347718334Speter	    if (! (
347818334Speter#ifdef ANNUL_IFFALSE_SLOTS
347918334Speter		   (INSN_ANNULLED_BRANCH_P (jump_insn)
348018334Speter		    && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
348118334Speter		   ? eligible_for_annul_false (jump_insn, i - 1,
348218334Speter					       XVECEXP (pat, 0, i), flags) :
348318334Speter#endif
348418334Speter#ifdef ANNUL_IFTRUE_SLOTS
348518334Speter		   (INSN_ANNULLED_BRANCH_P (jump_insn)
348618334Speter		    && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
348718334Speter		   ? eligible_for_annul_true (jump_insn, i - 1,
348818334Speter					      XVECEXP (pat, 0, i), flags) :
348918334Speter#endif
349090075Sobrien		   eligible_for_delay (jump_insn, i - 1,
349190075Sobrien				       XVECEXP (pat, 0, i), flags)))
349218334Speter	      break;
349318334Speter	}
349418334Speter      else
349518334Speter	i = 0;
349618334Speter
349718334Speter      if (i == XVECLEN (pat, 0))
349818334Speter	continue;
349918334Speter
350018334Speter      /* We have to do something with this insn.  If it is an unconditional
350118334Speter	 RETURN, delete the SEQUENCE and output the individual insns,
350218334Speter	 followed by the RETURN.  Then set things up so we try to find
350318334Speter	 insns for its delay slots, if it needs some.  */
350418334Speter      if (GET_CODE (PATTERN (jump_insn)) == RETURN)
350518334Speter	{
350618334Speter	  rtx prev = PREV_INSN (insn);
350718334Speter
350890075Sobrien	  delete_related_insns (insn);
350918334Speter	  for (i = 1; i < XVECLEN (pat, 0); i++)
351018334Speter	    prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
351118334Speter
351218334Speter	  insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
351318334Speter	  emit_barrier_after (insn);
351418334Speter
351518334Speter	  if (slots)
351618334Speter	    obstack_ptr_grow (&unfilled_slots_obstack, insn);
351718334Speter	}
351818334Speter      else
351918334Speter	/* It is probably more efficient to keep this with its current
352018334Speter	   delay slot as a branch to a RETURN.  */
352118334Speter	reorg_redirect_jump (jump_insn, real_return_label);
352218334Speter    }
352318334Speter
352418334Speter  /* Now delete REAL_RETURN_LABEL if we never used it.  Then try to fill any
352518334Speter     new delay slots we have created.  */
352618334Speter  if (--LABEL_NUSES (real_return_label) == 0)
352790075Sobrien    delete_related_insns (real_return_label);
352818334Speter
352950397Sobrien  fill_simple_delay_slots (1);
353050397Sobrien  fill_simple_delay_slots (0);
353118334Speter}
353218334Speter#endif
353318334Speter
353418334Speter/* Try to find insns to place in delay slots.  */
353518334Speter
353618334Spetervoid
3537169689Skandbr_schedule (rtx first)
353818334Speter{
353918334Speter  rtx insn, next, epilogue_insn = 0;
354018334Speter  int i;
354118334Speter
354290075Sobrien  /* If the current function has no insns other than the prologue and
354318334Speter     epilogue, then do not try to fill any delay slots.  */
3544169689Skan  if (n_basic_blocks == NUM_FIXED_BLOCKS)
354518334Speter    return;
354618334Speter
354718334Speter  /* Find the highest INSN_UID and allocate and initialize our map from
354818334Speter     INSN_UID's to position in code.  */
354918334Speter  for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
355018334Speter    {
355118334Speter      if (INSN_UID (insn) > max_uid)
355218334Speter	max_uid = INSN_UID (insn);
3553169689Skan      if (NOTE_P (insn)
355418334Speter	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
355518334Speter	epilogue_insn = insn;
355618334Speter    }
355718334Speter
3558132718Skan  uid_to_ruid = xmalloc ((max_uid + 1) * sizeof (int));
355918334Speter  for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
356018334Speter    uid_to_ruid[INSN_UID (insn)] = i;
356190075Sobrien
356218334Speter  /* Initialize the list of insns that need filling.  */
356318334Speter  if (unfilled_firstobj == 0)
356418334Speter    {
356518334Speter      gcc_obstack_init (&unfilled_slots_obstack);
3566132718Skan      unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0);
356718334Speter    }
356818334Speter
356918334Speter  for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
357018334Speter    {
357118334Speter      rtx target;
357218334Speter
357318334Speter      INSN_ANNULLED_BRANCH_P (insn) = 0;
357418334Speter      INSN_FROM_TARGET_P (insn) = 0;
357518334Speter
357618334Speter      /* Skip vector tables.  We can't get attributes for them.  */
3577169689Skan      if (JUMP_P (insn)
357818334Speter	  && (GET_CODE (PATTERN (insn)) == ADDR_VEC
357918334Speter	      || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
358018334Speter	continue;
358190075Sobrien
358218334Speter      if (num_delay_slots (insn) > 0)
358318334Speter	obstack_ptr_grow (&unfilled_slots_obstack, insn);
358418334Speter
358518334Speter      /* Ensure all jumps go to the last of a set of consecutive labels.  */
3586169689Skan      if (JUMP_P (insn)
358718334Speter	  && (condjump_p (insn) || condjump_in_parallel_p (insn))
358818334Speter	  && JUMP_LABEL (insn) != 0
3589169689Skan	  && ((target = skip_consecutive_labels (JUMP_LABEL (insn)))
359018334Speter	      != JUMP_LABEL (insn)))
359190075Sobrien	redirect_jump (insn, target, 1);
359218334Speter    }
359318334Speter
359452284Sobrien  init_resource_info (epilogue_insn);
359518334Speter
359618334Speter  /* Show we haven't computed an end-of-function label yet.  */
359718334Speter  end_of_function_label = 0;
359818334Speter
359918334Speter  /* Initialize the statistics for this function.  */
3600132718Skan  memset (num_insns_needing_delays, 0, sizeof num_insns_needing_delays);
3601132718Skan  memset (num_filled_delays, 0, sizeof num_filled_delays);
360218334Speter
360318334Speter  /* Now do the delay slot filling.  Try everything twice in case earlier
360418334Speter     changes make more slots fillable.  */
360518334Speter
360618334Speter  for (reorg_pass_number = 0;
360718334Speter       reorg_pass_number < MAX_REORG_PASSES;
360818334Speter       reorg_pass_number++)
360918334Speter    {
361050397Sobrien      fill_simple_delay_slots (1);
361150397Sobrien      fill_simple_delay_slots (0);
361250397Sobrien      fill_eager_delay_slots ();
361318334Speter      relax_delay_slots (first);
361418334Speter    }
361518334Speter
361618334Speter  /* Delete any USE insns made by update_block; subsequent passes don't need
361718334Speter     them or know how to deal with them.  */
361818334Speter  for (insn = first; insn; insn = next)
361918334Speter    {
362018334Speter      next = NEXT_INSN (insn);
362118334Speter
3622169689Skan      if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE
362390075Sobrien	  && INSN_P (XEXP (PATTERN (insn), 0)))
362490075Sobrien	next = delete_related_insns (insn);
362518334Speter    }
362618334Speter
362718334Speter  /* If we made an end of function label, indicate that it is now
362818334Speter     safe to delete it by undoing our prior adjustment to LABEL_NUSES.
362918334Speter     If it is now unused, delete it.  */
363018334Speter  if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
363190075Sobrien    delete_related_insns (end_of_function_label);
363218334Speter
363318334Speter#ifdef HAVE_return
363418334Speter  if (HAVE_return && end_of_function_label != 0)
363518334Speter    make_return_insns (first);
363618334Speter#endif
363718334Speter
363818334Speter  obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
363918334Speter
364018334Speter  /* It is not clear why the line below is needed, but it does seem to be.  */
3641132718Skan  unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0);
364218334Speter
3643169689Skan  if (dump_file)
364418334Speter    {
364590075Sobrien      int i, j, need_comma;
364690075Sobrien      int total_delay_slots[MAX_DELAY_HISTOGRAM + 1];
364790075Sobrien      int total_annul_slots[MAX_DELAY_HISTOGRAM + 1];
364818334Speter
364918334Speter      for (reorg_pass_number = 0;
365018334Speter	   reorg_pass_number < MAX_REORG_PASSES;
365118334Speter	   reorg_pass_number++)
365218334Speter	{
3653169689Skan	  fprintf (dump_file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
365418334Speter	  for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
365518334Speter	    {
365618334Speter	      need_comma = 0;
3657169689Skan	      fprintf (dump_file, ";; Reorg function #%d\n", i);
365818334Speter
3659169689Skan	      fprintf (dump_file, ";; %d insns needing delay slots\n;; ",
366018334Speter		       num_insns_needing_delays[i][reorg_pass_number]);
366118334Speter
366290075Sobrien	      for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
366318334Speter		if (num_filled_delays[i][j][reorg_pass_number])
366418334Speter		  {
366518334Speter		    if (need_comma)
3666169689Skan		      fprintf (dump_file, ", ");
366718334Speter		    need_comma = 1;
3668169689Skan		    fprintf (dump_file, "%d got %d delays",
366918334Speter			     num_filled_delays[i][j][reorg_pass_number], j);
367018334Speter		  }
3671169689Skan	      fprintf (dump_file, "\n");
367218334Speter	    }
367318334Speter	}
3674132718Skan      memset (total_delay_slots, 0, sizeof total_delay_slots);
3675132718Skan      memset (total_annul_slots, 0, sizeof total_annul_slots);
367690075Sobrien      for (insn = first; insn; insn = NEXT_INSN (insn))
367790075Sobrien	{
367890075Sobrien	  if (! INSN_DELETED_P (insn)
3679169689Skan	      && NONJUMP_INSN_P (insn)
368090075Sobrien	      && GET_CODE (PATTERN (insn)) != USE
368190075Sobrien	      && GET_CODE (PATTERN (insn)) != CLOBBER)
368290075Sobrien	    {
368390075Sobrien	      if (GET_CODE (PATTERN (insn)) == SEQUENCE)
368490075Sobrien		{
368590075Sobrien		  j = XVECLEN (PATTERN (insn), 0) - 1;
368690075Sobrien		  if (j > MAX_DELAY_HISTOGRAM)
368790075Sobrien		    j = MAX_DELAY_HISTOGRAM;
368890075Sobrien		  if (INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (insn), 0, 0)))
368990075Sobrien		    total_annul_slots[j]++;
369090075Sobrien		  else
369190075Sobrien		    total_delay_slots[j]++;
369290075Sobrien		}
369390075Sobrien	      else if (num_delay_slots (insn) > 0)
369490075Sobrien		total_delay_slots[0]++;
369590075Sobrien	    }
369690075Sobrien	}
3697169689Skan      fprintf (dump_file, ";; Reorg totals: ");
369890075Sobrien      need_comma = 0;
369990075Sobrien      for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
370090075Sobrien	{
370190075Sobrien	  if (total_delay_slots[j])
370290075Sobrien	    {
370390075Sobrien	      if (need_comma)
3704169689Skan		fprintf (dump_file, ", ");
370590075Sobrien	      need_comma = 1;
3706169689Skan	      fprintf (dump_file, "%d got %d delays", total_delay_slots[j], j);
370790075Sobrien	    }
370890075Sobrien	}
3709169689Skan      fprintf (dump_file, "\n");
371090075Sobrien#if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
3711169689Skan      fprintf (dump_file, ";; Reorg annuls: ");
371290075Sobrien      need_comma = 0;
371390075Sobrien      for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
371490075Sobrien	{
371590075Sobrien	  if (total_annul_slots[j])
371690075Sobrien	    {
371790075Sobrien	      if (need_comma)
3718169689Skan		fprintf (dump_file, ", ");
371990075Sobrien	      need_comma = 1;
3720169689Skan	      fprintf (dump_file, "%d got %d delays", total_annul_slots[j], j);
372190075Sobrien	    }
372290075Sobrien	}
3723169689Skan      fprintf (dump_file, "\n");
372490075Sobrien#endif
3725169689Skan      fprintf (dump_file, "\n");
372618334Speter    }
372750397Sobrien
372850397Sobrien  /* For all JUMP insns, fill in branch prediction notes, so that during
372950397Sobrien     assembler output a target can set branch prediction bits in the code.
373050397Sobrien     We have to do this now, as up until this point the destinations of
373150397Sobrien     JUMPS can be moved around and changed, but past right here that cannot
373250397Sobrien     happen.  */
373350397Sobrien  for (insn = first; insn; insn = NEXT_INSN (insn))
373450397Sobrien    {
373550397Sobrien      int pred_flags;
373650397Sobrien
3737169689Skan      if (NONJUMP_INSN_P (insn))
373890075Sobrien	{
373952284Sobrien	  rtx pat = PATTERN (insn);
374052284Sobrien
374152284Sobrien	  if (GET_CODE (pat) == SEQUENCE)
374252284Sobrien	    insn = XVECEXP (pat, 0, 0);
374352284Sobrien	}
3744169689Skan      if (!JUMP_P (insn))
374550397Sobrien	continue;
374650397Sobrien
374750397Sobrien      pred_flags = get_jump_flags (insn, JUMP_LABEL (insn));
374850397Sobrien      REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED,
374950397Sobrien					    GEN_INT (pred_flags),
375050397Sobrien					    REG_NOTES (insn));
375150397Sobrien    }
375252284Sobrien  free_resource_info ();
375390075Sobrien  free (uid_to_ruid);
3754132718Skan#ifdef DELAY_SLOTS_FOR_EPILOGUE
3755132718Skan  /* SPARC assembler, for instance, emit warning when debug info is output
3756132718Skan     into the delay slot.  */
3757132718Skan  {
3758132718Skan    rtx link;
3759132718Skan
3760132718Skan    for (link = current_function_epilogue_delay_list;
3761132718Skan         link;
3762132718Skan         link = XEXP (link, 1))
3763132718Skan      INSN_LOCATOR (XEXP (link, 0)) = 0;
3764132718Skan  }
3765132718Skan#endif
376618334Speter}
376718334Speter#endif /* DELAY_SLOTS */
3768169689Skan
3769169689Skanstatic bool
3770169689Skangate_handle_delay_slots (void)
3771169689Skan{
3772169689Skan#ifdef DELAY_SLOTS
3773169689Skan  return flag_delayed_branch;
3774169689Skan#else
3775169689Skan  return 0;
3776169689Skan#endif
3777169689Skan}
3778169689Skan
3779169689Skan/* Run delay slot optimization.  */
3780169689Skanstatic unsigned int
3781169689Skanrest_of_handle_delay_slots (void)
3782169689Skan{
3783169689Skan#ifdef DELAY_SLOTS
3784169689Skan  dbr_schedule (get_insns ());
3785169689Skan#endif
3786169689Skan  return 0;
3787169689Skan}
3788169689Skan
3789169689Skanstruct tree_opt_pass pass_delay_slots =
3790169689Skan{
3791169689Skan  "dbr",                                /* name */
3792169689Skan  gate_handle_delay_slots,              /* gate */
3793169689Skan  rest_of_handle_delay_slots,           /* execute */
3794169689Skan  NULL,                                 /* sub */
3795169689Skan  NULL,                                 /* next */
3796169689Skan  0,                                    /* static_pass_number */
3797169689Skan  TV_DBR_SCHED,                         /* tv_id */
3798169689Skan  0,                                    /* properties_required */
3799169689Skan  0,                                    /* properties_provided */
3800169689Skan  0,                                    /* properties_destroyed */
3801169689Skan  0,                                    /* todo_flags_start */
3802169689Skan  TODO_dump_func |
3803169689Skan  TODO_ggc_collect,                     /* todo_flags_finish */
3804169689Skan  'd'                                   /* letter */
3805169689Skan};
3806169689Skan
3807169689Skan/* Machine dependent reorg pass.  */
3808169689Skanstatic bool
3809169689Skangate_handle_machine_reorg (void)
3810169689Skan{
3811169689Skan  return targetm.machine_dependent_reorg != 0;
3812169689Skan}
3813169689Skan
3814169689Skan
3815169689Skanstatic unsigned int
3816169689Skanrest_of_handle_machine_reorg (void)
3817169689Skan{
3818169689Skan  targetm.machine_dependent_reorg ();
3819169689Skan  return 0;
3820169689Skan}
3821169689Skan
3822169689Skanstruct tree_opt_pass pass_machine_reorg =
3823169689Skan{
3824169689Skan  "mach",                               /* name */
3825169689Skan  gate_handle_machine_reorg,            /* gate */
3826169689Skan  rest_of_handle_machine_reorg,         /* execute */
3827169689Skan  NULL,                                 /* sub */
3828169689Skan  NULL,                                 /* next */
3829169689Skan  0,                                    /* static_pass_number */
3830169689Skan  TV_MACH_DEP,                          /* tv_id */
3831169689Skan  0,                                    /* properties_required */
3832169689Skan  0,                                    /* properties_provided */
3833169689Skan  0,                                    /* properties_destroyed */
3834169689Skan  0,                                    /* todo_flags_start */
3835169689Skan  TODO_dump_func |
3836169689Skan  TODO_ggc_collect,                     /* todo_flags_finish */
3837169689Skan  'M'                                   /* letter */
3838169689Skan};
3839169689Skan
3840