OSDN Git Service

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