1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992 Free Software Foundation, Inc.
3 Contributed by Richard Kenner (kenner@nyu.edu).
4 Hacked by Michael Tiemann (tiemann@cygnus.com).
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
22 /* Instruction reorganization pass.
24 This pass runs after register allocation and final jump
25 optimization. It should be the last pass to run before peephole.
26 It serves primarily to fill delay slots of insns, typically branch
27 and call insns. Other insns typically involve more complicated
28 interactions of data dependencies and resource constraints, and
29 are better handled by scheduling before register allocation (by the
30 function `schedule_insns').
32 The Branch Penalty is the number of extra cycles that are needed to
33 execute a branch insn. On an ideal machine, branches take a single
34 cycle, and the Branch Penalty is 0. Several RISC machines approach
35 branch delays differently:
37 The MIPS and AMD 29000 have a single branch delay slot. Most insns
38 (except other branches) can be used to fill this slot. When the
39 slot is filled, two insns execute in two cycles, reducing the
40 branch penalty to zero.
42 The Motorola 88000 conditionally exposes its branch delay slot,
43 so code is shorter when it is turned off, but will run faster
44 when useful insns are scheduled there.
46 The IBM ROMP has two forms of branch and call insns, both with and
47 without a delay slot. Much like the 88k, insns not using the delay
48 slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
50 The SPARC always has a branch delay slot, but its effects can be
51 annulled when the branch is not taken. This means that failing to
52 find other sources of insns, we can hoist an insn from the branch
53 target that would only be safe to execute knowing that the branch
56 Three techniques for filling delay slots have been implemented so far:
58 (1) `fill_simple_delay_slots' is the simplest, most efficient way
59 to fill delay slots. This pass first looks for insns which come
60 from before the branch and which are safe to execute after the
61 branch. Then it searches after the insn requiring delay slots or,
62 in the case of a branch, for insns that are after the point at
63 which the branch merges into the fallthrough code, if such a point
64 exists. When such insns are found, the branch penalty decreases
65 and no code expansion takes place.
67 (2) `fill_eager_delay_slots' is more complicated: it is used for
68 scheduling conditional jumps, or for scheduling jumps which cannot
69 be filled using (1). A machine need not have annulled jumps to use
70 this strategy, but it helps (by keeping more options open).
71 `fill_eager_delay_slots' tries to guess the direction the branch
72 will go; if it guesses right 100% of the time, it can reduce the
73 branch penalty as much as `fill_eager_delay_slots' does. If it
74 guesses wrong 100% of the time, it might as well schedule nops (or
75 on the m88k, unexpose the branch slot). When
76 `fill_eager_delay_slots' takes insns from the fall-through path of
77 the jump, usually there is no code expansion; when it takes insns
78 from the branch target, there is code expansion if it is not the
79 only way to reach that target.
81 (3) `relax_delay_slots' uses a set of rules to simplify code that
82 has been reorganized by (1) and (2). It finds cases where
83 conditional test can be eliminated, jumps can be threaded, extra
84 insns can be eliminated, etc. It is the job of (1) and (2) to do a
85 good job of scheduling locally; `relax_delay_slots' takes care of
86 making the various individual schedules work well together. It is
87 especially tuned to handle the control flow interactions of branch
88 insns. It does nothing for insns with delay slots that do not
91 On machines that use CC0, we are very conservative. We will not make
92 a copy of an insn involving CC0 since we want to maintain a 1-1
93 correspondence between the insn that sets and uses CC0. The insns are
94 allowed to be separated by placing an insn that sets CC0 (but not an insn
95 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
96 delay slot. In that case, we point each insn at the other with REG_CC_USER
97 and REG_CC_SETTER notes. Note that these restrictions affect very few
98 machines because most RISC machines with delay slots will not use CC0
99 (the RT is the only known exception at this point).
103 The Acorn Risc Machine can conditionally execute most insns, so
104 it is profitable to move single insns into a position to execute
105 based on the condition code of the previous insn.
107 The HP-PA can conditionally nullify insns, providing a similar
108 effect to the ARM, differing mostly in which insn is "in charge". */
113 #include "insn-config.h"
114 #include "conditions.h"
115 #include "hard-reg-set.h"
116 #include "basic-block.h"
118 #include "insn-flags.h"
123 #include "insn-attr.h"
127 #define obstack_chunk_alloc xmalloc
128 #define obstack_chunk_free free
130 #ifndef ANNUL_IFTRUE_SLOTS
131 #define eligible_for_annul_true(INSN, SLOTS, TRIAL) 0
133 #ifndef ANNUL_IFFALSE_SLOTS
134 #define eligible_for_annul_false(INSN, SLOTS, TRIAL) 0
137 /* Insns which have delay slots that have not yet been filled. */
139 static struct obstack unfilled_slots_obstack;
140 static rtx *unfilled_firstobj;
142 /* Define macros to refer to the first and last slot containing unfilled
143 insns. These are used because the list may move and its address
144 should be recomputed at each use. */
146 #define unfilled_slots_base \
147 ((rtx *) obstack_base (&unfilled_slots_obstack))
149 #define unfilled_slots_next \
150 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
152 /* This structure is used to indicate which hardware resources are set or
153 needed by insns so far. */
157 char memory; /* Insn sets or needs a memory location. */
158 char volatil; /* Insn sets or needs a volatile memory loc. */
159 char cc; /* Insn sets or needs the condition codes. */
160 HARD_REG_SET regs; /* Which registers are set or needed. */
163 /* Macro to clear all resources. */
164 #define CLEAR_RESOURCE(RES) \
165 do { (RES)->memory = (RES)->volatil = (RES)->cc = 0; \
166 CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
168 /* Indicates what resources are required at function end. */
169 static struct resources end_of_function_needs;
171 /* Points to the label before the end of the function. */
172 static rtx end_of_function_label;
174 /* This structure is used to record liveness information at the targets or
175 fallthrough insns of branches. We will most likely need the information
176 at targets again, so save them in a hash table rather than recomputing them
181 int uid; /* INSN_UID of target. */
182 struct target_info *next; /* Next info for same hash bucket. */
183 HARD_REG_SET live_regs; /* Registers live at target. */
184 int block; /* Basic block number containing target. */
185 int bb_tick; /* Generation count of basic block info. */
188 #define TARGET_HASH_PRIME 257
190 /* Define the hash table itself. */
191 static struct target_info **target_hash_table;
193 /* For each basic block, we maintain a generation number of its basic
194 block info, which is updated each time we move an insn from the
195 target of a jump. This is the generation number indexed by block
198 static int *bb_ticks;
200 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
201 not always monotonically increase. */
202 static int *uid_to_ruid;
204 /* Highest valid index in `uid_to_ruid'. */
207 /* Forward references: */
209 static int redundant_insn_p ();
210 static void update_block ();
212 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
213 which resources are references by the insn. If INCLUDE_CALLED_ROUTINE
214 is TRUE, resources used by the called routine will be included for
218 mark_referenced_resources (x, res, include_called_routine)
220 register struct resources *res;
221 register int include_called_routine;
223 register enum rtx_code code = GET_CODE (x);
225 register char *format_ptr;
227 /* Handle leaf items for which we set resource flags. Also, special-case
228 CALL, SET and CLOBBER operators. */
240 if (GET_CODE (SUBREG_REG (x)) != REG)
241 mark_referenced_resources (SUBREG_REG (x), res, 0);
244 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
245 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
246 for (i = regno; i < last_regno; i++)
247 SET_HARD_REG_BIT (res->regs, i);
252 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
253 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
257 /* If this memory shouldn't change, it really isn't referencing
259 if (! RTX_UNCHANGING_P (x))
261 res->volatil = MEM_VOLATILE_P (x);
263 /* Mark registers used to access memory. */
264 mark_referenced_resources (XEXP (x, 0), res, 0);
271 case UNSPEC_VOLATILE:
273 /* Traditional asm's are always volatile. */
278 res->volatil = MEM_VOLATILE_P (x);
280 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
281 We can not just fall through here since then we would be confused
282 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
283 traditional asms unlike their normal usage. */
285 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
286 mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
290 /* The first operand will be a (MEM (xxx)) but doesn't really reference
291 memory. The second operand may be referenced, though. */
292 mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
293 mark_referenced_resources (XEXP (x, 1), res, 0);
297 /* Usually, the first operand of SET is set, not referenced. But
298 registers used to access memory are referenced. SET_DEST is
299 also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
301 mark_referenced_resources (SET_SRC (x), res, 0);
304 if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
305 mark_referenced_resources (x, res, 0);
306 else if (GET_CODE (x) == SUBREG)
308 if (GET_CODE (x) == MEM)
309 mark_referenced_resources (XEXP (x, 0), res, 0);
316 if (include_called_routine)
318 /* A CALL references memory, the frame pointer if it exists, the
319 stack pointer, any global registers and any registers given in
320 USE insns immediately in front of the CALL.
322 However, we may have moved some of the parameter loading insns
323 into the delay slot of this CALL. If so, the USE's for them
324 don't count and should be skipped. */
325 rtx insn = PREV_INSN (x);
330 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
331 if (NEXT_INSN (insn) != x)
333 sequence = PATTERN (NEXT_INSN (insn));
334 seq_size = XVECLEN (sequence, 0);
335 if (GET_CODE (sequence) != SEQUENCE)
340 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
341 if (frame_pointer_needed)
342 SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
344 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
346 SET_HARD_REG_BIT (res->regs, i);
348 /* Skip any labels between the CALL_INSN and possible USE insns. */
349 while (GET_CODE (insn) == CODE_LABEL)
350 insn = PREV_INSN (insn);
352 for ( ; (insn && GET_CODE (insn) == INSN
353 && GET_CODE (PATTERN (insn)) == USE);
354 insn = PREV_INSN (insn))
356 for (i = 1; i < seq_size; i++)
358 rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
359 if (GET_CODE (slot_pat) == SET
360 && rtx_equal_p (SET_DEST (slot_pat),
361 XEXP (PATTERN (insn), 0)))
365 mark_referenced_resources (XEXP (PATTERN (insn), 0), res, 0);
369 /* ... fall through to other INSN processing ... */
373 /* No special processing, just speed up. */
374 mark_referenced_resources (PATTERN (x), res, include_called_routine);
378 /* Process each sub-expression and flag what it needs. */
379 format_ptr = GET_RTX_FORMAT (code);
380 for (i = 0; i < GET_RTX_LENGTH (code); i++)
381 switch (*format_ptr++)
384 mark_referenced_resources (XEXP (x, i), res, include_called_routine);
388 for (j = 0; j < XVECLEN (x, i); j++)
389 mark_referenced_resources (XVECEXP (x, i, j), res,
390 include_called_routine);
395 /* Given X, a part of an insn, and a pointer to a `struct resource', RES,
396 indicate which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
397 is nonzero, also mark resources potentially set by the called routine.
399 If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
400 objects are being referenced instead of set.
402 We never mark the insn as modifying the condition code unless it explicitly
403 SETs CC0 even though this is not totally correct. The reason for this is
404 that we require a SET of CC0 to immediately precede the reference to CC0.
405 So if some other insn sets CC0 as a side-effect, we know it cannot affect
406 our computation and thus may be placed in a delay slot. */
409 mark_set_resources (x, res, in_dest, include_called_routine)
411 register struct resources *res;
413 int include_called_routine;
415 register enum rtx_code code;
417 register char *format_ptr;
435 /* These don't set any resources. */
444 /* Called routine modifies the condition code, memory, any registers
445 that aren't saved across calls, global registers and anything
446 explicitly CLOBBERed immediately after the CALL_INSN. */
448 if (include_called_routine)
450 rtx next = NEXT_INSN (x);
452 res->cc = res->memory = 1;
453 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
454 if (call_used_regs[i] || global_regs[i])
455 SET_HARD_REG_BIT (res->regs, i);
457 /* Skip any possible labels between the CALL_INSN and CLOBBERs. */
458 while (GET_CODE (next) == CODE_LABEL)
459 next = NEXT_INSN (next);
461 for (; (next && GET_CODE (next) == INSN
462 && GET_CODE (PATTERN (next)) == CLOBBER);
463 next = NEXT_INSN (next))
464 mark_set_resources (XEXP (PATTERN (next), 0), res, 1, 0);
467 /* ... and also what it's RTL says it modifies, if anything. */
472 /* An insn consisting of just a CLOBBER (or USE) is just for flow
473 and doesn't actually do anything, so we ignore it. */
476 if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
481 /* If the source of a SET is a CALL, this is actually done by
482 the called routine. So only include it if we are to include the
483 effects of the calling routine. */
485 mark_set_resources (SET_DEST (x), res,
486 (include_called_routine
487 || GET_CODE (SET_SRC (x)) != CALL),
490 mark_set_resources (SET_SRC (x), res, 0, 0);
494 mark_set_resources (XEXP (x, 0), res, 1, 0);
498 for (i = 0; i < XVECLEN (x, 0); i++)
499 if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0))
500 && INSN_FROM_TARGET_P (XVECEXP (x, 0, i))))
501 mark_set_resources (XVECEXP (x, 0, i), res, 0,
502 include_called_routine);
509 mark_set_resources (XEXP (x, 0), res, 1, 0);
513 mark_set_resources (XEXP (x, 0), res, in_dest, 0);
514 mark_set_resources (XEXP (x, 1), res, 0, 0);
515 mark_set_resources (XEXP (x, 2), res, 0, 0);
522 res->volatil = MEM_VOLATILE_P (x);
525 mark_set_resources (XEXP (x, 0), res, 0, 0);
530 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
531 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
535 /* Process each sub-expression and flag what it needs. */
536 format_ptr = GET_RTX_FORMAT (code);
537 for (i = 0; i < GET_RTX_LENGTH (code); i++)
538 switch (*format_ptr++)
541 mark_set_resources (XEXP (x, i), res, in_dest, include_called_routine);
545 for (j = 0; j < XVECLEN (x, i); j++)
546 mark_set_resources (XVECEXP (x, i, j), res, in_dest,
547 include_called_routine);
552 /* Return TRUE if this insn should stop the search for insn to fill delay
553 slots. LABELS_P indicates that labels should terminate the search.
554 In all cases, jumps terminate the search. */
557 stop_search_p (insn, labels_p)
564 switch (GET_CODE (insn))
578 /* OK unless it contains a delay slot or is an `asm' insn of some type.
579 We don't know anything about these. */
580 return (GET_CODE (PATTERN (insn)) == SEQUENCE
581 || GET_CODE (PATTERN (insn)) == ASM_INPUT
582 || asm_noperands (PATTERN (insn)) >= 0);
589 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
590 resource set contains a volatile memory reference. Otherwise, return FALSE. */
593 resource_conflicts_p (res1, res2)
594 struct resources *res1, *res2;
596 if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
597 || res1->volatil || res2->volatil)
601 return (res1->regs & res2->regs) != HARD_CONST (0);
606 for (i = 0; i < HARD_REG_SET_LONGS; i++)
607 if ((res1->regs[i] & res2->regs[i]) != 0)
614 /* Return TRUE if any resource marked in RES, a `struct resources', is
615 referenced by INSN. If INCLUDE_CALLED_ROUTINE is set, return if the called
616 routine is using those resources.
618 We compute this by computing all the resources referenced by INSN and
619 seeing if this conflicts with RES. It might be faster to directly check
620 ourselves, and this is the way it used to work, but it means duplicating
621 a large block of complex code. */
624 insn_references_resource_p (insn, res, include_called_routine)
626 register struct resources *res;
627 int include_called_routine;
629 struct resources insn_res;
631 CLEAR_RESOURCE (&insn_res);
632 mark_referenced_resources (insn, &insn_res, include_called_routine);
633 return resource_conflicts_p (&insn_res, res);
636 /* Return TRUE if INSN modifies resources that are marked in RES.
637 INCLUDE_CALLED_ROUTINE is set if the actions of that routine should be
638 included. CC0 is only modified if it is explicitly set; see comments
639 in front of mark_set_resources for details. */
642 insn_sets_resource_p (insn, res, include_called_routine)
644 register struct resources *res;
645 int include_called_routine;
647 struct resources insn_sets;
649 CLEAR_RESOURCE (&insn_sets);
650 mark_set_resources (insn, &insn_sets, 0, include_called_routine);
651 return resource_conflicts_p (&insn_sets, res);
654 /* Find a label at the end of the function or before a RETURN. If there is
662 /* If we found one previously, return it. */
663 if (end_of_function_label)
664 return end_of_function_label;
666 /* Otherwise, see if there is a label at the end of the function. If there
667 is, it must be that RETURN insns aren't needed, so that is our return
668 label and we don't have to do anything else. */
670 insn = get_last_insn ();
671 while (GET_CODE (insn) == NOTE
672 || (GET_CODE (insn) == INSN
673 && (GET_CODE (PATTERN (insn)) == USE
674 || GET_CODE (PATTERN (insn)) == CLOBBER)))
675 insn = PREV_INSN (insn);
677 if (GET_CODE (insn) == CODE_LABEL)
678 end_of_function_label = insn;
681 /* Otherwise, make a new label and emit a RETURN and BARRIER,
683 end_of_function_label = gen_label_rtx ();
684 LABEL_NUSES (end_of_function_label) = 0;
685 emit_label (end_of_function_label);
689 emit_jump_insn (gen_return ());
695 /* Show one additional use for this label so it won't go away until
697 ++LABEL_NUSES (end_of_function_label);
699 return end_of_function_label;
702 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
703 the pattern of INSN with the SEQUENCE.
705 Chain the insns so that NEXT_INSN of each insn in the sequence points to
706 the next and NEXT_INSN of the last insn in the sequence points to
707 the first insn after the sequence. Similarly for PREV_INSN. This makes
708 it easier to scan all insns.
710 Returns the SEQUENCE that replaces INSN. */
713 emit_delay_sequence (insn, list, length, avail)
723 /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
724 rtvec seqv = rtvec_alloc (length + 1);
725 rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
726 rtx seq_insn = make_insn_raw (seq);
727 rtx first = get_insns ();
728 rtx last = get_last_insn ();
730 /* Make a copy of the insn having delay slots. */
731 rtx delay_insn = copy_rtx (insn);
733 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
734 confuse further processing. Update LAST in case it was the last insn.
735 We will put the BARRIER back in later. */
736 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
738 delete_insn (NEXT_INSN (insn));
739 last = get_last_insn ();
743 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
744 NEXT_INSN (seq_insn) = NEXT_INSN (insn);
745 PREV_INSN (seq_insn) = PREV_INSN (insn);
748 set_new_first_and_last_insn (first, seq_insn);
750 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
753 set_new_first_and_last_insn (seq_insn, last);
755 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
757 /* Build our SEQUENCE and rebuild the insn chain. */
758 XVECEXP (seq, 0, 0) = delay_insn;
759 INSN_DELETED_P (delay_insn) = 0;
760 PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
762 for (li = list; li; li = XEXP (li, 1), i++)
764 rtx tem = XEXP (li, 0);
767 /* Show that this copy of the insn isn't deleted. */
768 INSN_DELETED_P (tem) = 0;
770 XVECEXP (seq, 0, i) = tem;
771 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
772 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
774 /* Remove any REG_DEAD notes because we can't rely on them now
775 that the insn has been moved. */
776 for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
777 if (REG_NOTE_KIND (note) == REG_DEAD)
778 XEXP (note, 0) = const0_rtx;
781 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
783 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
784 last insn in that SEQUENCE to point to us. Similarly for the first
785 insn in the following insn if it is a SEQUENCE. */
787 if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
788 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
789 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
790 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
793 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
794 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
795 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
797 /* If there used to be a BARRIER, put it back. */
799 emit_barrier_after (seq_insn);
807 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
808 be in the order in which the insns are to be executed. */
811 add_to_delay_list (insn, delay_list)
815 /* If we have an empty list, just make a new list element. */
817 return gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
819 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
821 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
826 /* Delete INSN from the the delay slot of the insn that it is in. This may
827 produce an insn without anything in its delay slots. */
830 delete_from_delay_slot (insn)
833 rtx trial, seq_insn, seq, prev;
837 /* We first must find the insn containing the SEQUENCE with INSN in its
838 delay slot. Do this by finding an insn, TRIAL, where
839 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
842 PREV_INSN (NEXT_INSN (trial)) == trial;
843 trial = NEXT_INSN (trial))
846 seq_insn = PREV_INSN (NEXT_INSN (trial));
847 seq = PATTERN (seq_insn);
849 /* Create a delay list consisting of all the insns other than the one
850 we are deleting (unless we were the only one). */
851 if (XVECLEN (seq, 0) > 2)
852 for (i = 1; i < XVECLEN (seq, 0); i++)
853 if (XVECEXP (seq, 0, i) != insn)
854 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
856 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
857 list, and rebuild the delay list if non-empty. */
858 prev = PREV_INSN (seq_insn);
859 trial = XVECEXP (seq, 0, 0);
860 delete_insn (seq_insn);
861 add_insn_after (trial, prev);
863 if (GET_CODE (trial) == JUMP_INSN
864 && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
865 emit_barrier_after (trial);
867 /* If there are any delay insns, remit them. Otherwise clear the
870 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2, 0);
872 INSN_ANNULLED_BRANCH_P (trial) = 0;
874 INSN_FROM_TARGET_P (insn) = 0;
876 /* Show we need to fill this insn again. */
877 obstack_ptr_grow (&unfilled_slots_obstack, trial);
880 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
881 the insn that sets CC0 for it and delete it too. */
884 delete_scheduled_jump (insn)
887 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
888 delete the insn that sets the condition code, but it is hard to find it.
889 Since this case is rare anyway, don't bother trying; there would likely
890 be other insns that became dead anyway, which we wouldn't know to
894 if (reg_mentioned_p (cc0_rtx, insn))
896 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
898 /* If a reg-note was found, it points to an insn to set CC0. This
899 insn is in the delay list of some other insn. So delete it from
900 the delay list it was in. */
903 if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
904 && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
905 delete_from_delay_slot (XEXP (note, 0));
909 /* The insn setting CC0 is our previous insn, but it may be in
910 a delay slot. It will be the last insn in the delay slot, if
912 rtx trial = previous_insn (insn);
913 if (GET_CODE (trial) == NOTE)
914 trial = prev_nonnote_insn (trial);
915 if (sets_cc0_p (PATTERN (trial)) != 1
916 || FIND_REG_INC_NOTE (trial, 0))
918 if (PREV_INSN (NEXT_INSN (trial)) == trial)
921 delete_from_delay_slot (trial);
929 /* Counters for delay-slot filling. */
931 #define NUM_REORG_FUNCTIONS 2
932 #define MAX_DELAY_HISTOGRAM 3
933 #define MAX_REORG_PASSES 2
935 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
937 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
939 static int reorg_pass_number;
942 note_delay_statistics (slots_filled, index)
943 int slots_filled, index;
945 num_insns_needing_delays[index][reorg_pass_number]++;
946 if (slots_filled > MAX_DELAY_HISTOGRAM)
947 slots_filled = MAX_DELAY_HISTOGRAM;
948 num_filled_delays[index][slots_filled][reorg_pass_number]++;
951 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
953 /* Optimize the following cases:
955 1. When a conditional branch skips over only one instruction,
956 use an annulling branch and put that insn in the delay slot.
957 Use either a branch that annuls when the condition if true or
958 invert the test with a branch that annuls when the condition is
959 false. This saves insns, since otherwise we must copy an insn
962 (orig) (skip) (otherwise)
963 Bcc.n L1 Bcc',a L1 Bcc,a L1'
970 2. When a conditional branch skips over only one instruction,
971 and after that, it unconditionally branches somewhere else,
972 perform the similar optimization. This saves executing the
973 second branch in the case where the inverted condition is true.
982 This should be expanded to skip over N insns, where N is the number
983 of delay slots required. */
989 register rtx trial = next_nonnote_insn (insn);
990 rtx next_trial = next_active_insn (trial);
995 || GET_CODE (trial) != INSN
996 || GET_CODE (PATTERN (trial)) == SEQUENCE
997 || recog_memoized (trial) < 0
998 || (! eligible_for_annul_false (insn, 0, trial)
999 && ! eligible_for_annul_true (insn, 0, trial)))
1002 /* There are two cases where we are just executing one insn (we assume
1003 here that a branch requires only one insn; this should be generalized
1004 at some point): Where the branch goes around a single insn or where
1005 we have one insn followed by a branch to the same label we branch to.
1006 In both of these cases, inverting the jump and annulling the delay
1007 slot give the same effect in fewer insns. */
1008 if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
1010 && GET_CODE (next_trial) == JUMP_INSN
1011 && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
1012 && (simplejump_p (next_trial)
1013 || GET_CODE (PATTERN (next_trial)) == RETURN)))
1015 if (eligible_for_annul_false (insn, 0, trial))
1017 if (invert_jump (insn, JUMP_LABEL (insn)))
1018 INSN_FROM_TARGET_P (trial) = 1;
1019 else if (! eligible_for_annul_true (insn, 0, trial))
1023 delay_list = add_to_delay_list (trial, NULL_RTX);
1024 next_trial = next_active_insn (trial);
1025 update_block (trial, trial);
1026 delete_insn (trial);
1028 /* Also, if we are targeting an unconditional
1029 branch, thread our jump to the target of that branch. Don't
1030 change this into a RETURN here, because it may not accept what
1031 we have in the delay slot. We'll fix this up later. */
1032 if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1033 && (simplejump_p (next_trial)
1034 || GET_CODE (PATTERN (next_trial)) == RETURN))
1036 target_label = JUMP_LABEL (next_trial);
1037 if (target_label == 0)
1038 target_label = find_end_label ();
1039 redirect_jump (insn, target_label);
1042 INSN_ANNULLED_BRANCH_P (insn) = 1;
1049 /* Return truth value of the statement that this branch
1050 is mostly taken. If we think that the branch is extremely likely
1051 to be taken, we return 2. If the branch is slightly more likely to be
1052 taken, return 1. Otherwise, return 0.
1054 CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */
1057 mostly_true_jump (jump_insn, condition)
1058 rtx jump_insn, condition;
1060 rtx target_label = JUMP_LABEL (jump_insn);
1063 /* If this is a conditional return insn, assume it won't return. */
1064 if (target_label == 0)
1067 /* If TARGET_LABEL has no jumps between it and the end of the function,
1068 this is essentially a conditional return, so predict it as false. */
1069 for (insn = NEXT_INSN (target_label);
1070 insn && GET_CODE (insn) != JUMP_INSN;
1071 insn = NEXT_INSN (insn))
1077 /* If this is the test of a loop, it is very likely true. We scan backwards
1078 from the target label. If we find a NOTE_INSN_LOOP_BEG before the next
1079 real insn, we assume the branch is to the top of the loop. */
1080 for (insn = PREV_INSN (target_label);
1081 insn && GET_CODE (insn) == NOTE;
1082 insn = PREV_INSN (insn))
1083 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1086 /* If we couldn't figure out what this jump was, assume it won't be
1087 taken. This should be rare. */
1091 /* EQ tests are usually false and NE tests are usually true. Also,
1092 most quantities are positive, so we can make the appropriate guesses
1093 about signed comparisons against zero. */
1094 switch (GET_CODE (condition))
1097 /* Unconditional branch. */
1105 if (XEXP (condition, 1) == const0_rtx)
1110 if (XEXP (condition, 1) == const0_rtx)
1115 /* Predict backward branches usually take, forward branches usually not. If
1116 we don't know whether this is forward or backward, assume the branch
1117 will be taken, since most are. */
1118 return (INSN_UID (jump_insn) > max_uid || INSN_UID (target_label) > max_uid
1119 || (uid_to_ruid[INSN_UID (jump_insn)]
1120 > uid_to_ruid[INSN_UID (target_label)]));;
1123 /* Return the condition under which INSN will branch to TARGET. If TARGET
1124 is zero, return the condition under which INSN will return. If INSN is
1125 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1126 type of jump, or it doesn't go to TARGET, return 0. */
1129 get_branch_condition (insn, target)
1133 rtx pat = PATTERN (insn);
1136 if (GET_CODE (pat) == RETURN)
1137 return target == 0 ? const_true_rtx : 0;
1139 else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1142 src = SET_SRC (pat);
1143 if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1144 return const_true_rtx;
1146 else if (GET_CODE (src) == IF_THEN_ELSE
1147 && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1148 || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1149 && XEXP (XEXP (src, 1), 0) == target))
1150 && XEXP (src, 2) == pc_rtx)
1151 return XEXP (src, 0);
1153 else if (GET_CODE (src) == IF_THEN_ELSE
1154 && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1155 || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1156 && XEXP (XEXP (src, 2), 0) == target))
1157 && XEXP (src, 1) == pc_rtx)
1158 return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
1159 GET_MODE (XEXP (src, 0)),
1160 XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1165 /* Return non-zero if CONDITION is more strict than the condition of
1166 INSN, i.e., if INSN will always branch if CONDITION is true. */
1169 condition_dominates_p (condition, insn)
1173 rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1174 enum rtx_code code = GET_CODE (condition);
1175 enum rtx_code other_code;
1177 if (rtx_equal_p (condition, other_condition)
1178 || other_condition == const_true_rtx)
1181 else if (condition == const_true_rtx || other_condition == 0)
1184 other_code = GET_CODE (other_condition);
1185 if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1186 || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1187 || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1190 return comparison_dominates_p (code, other_code);
1193 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1194 the condition tested by INSN is CONDITION and the resources shown in
1195 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1196 from SEQ's delay list, in addition to whatever insns it may execute
1197 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1198 needed while searching for delay slot insns. Return the concatenated
1199 delay list if possible, otherwise, return 0.
1201 SLOTS_TO_FILL is the total number of slots required by INSN, and
1202 PSLOTS_FILLED points to the number filled so far (also the number of
1203 insns in DELAY_LIST). It is updated with the number that have been
1204 filled from the SEQUENCE, if any.
1206 PANNUL_P points to a non-zero value if we already know that we need
1207 to annul INSN. If this routine determines that annulling is needed,
1208 it may set that value non-zero.
1210 PNEW_THREAD points to a location that is to receive the place at which
1211 execution should continue. */
1214 steal_delay_list_from_target (insn, condition, seq, delay_list,
1215 sets, needed, other_needed,
1216 slots_to_fill, pslots_filled, pannul_p,
1218 rtx insn, condition;
1221 struct resources *sets, *needed, *other_needed;
1228 int slots_remaining = slots_to_fill - *pslots_filled;
1229 int total_slots_filled = *pslots_filled;
1230 rtx new_delay_list = 0;
1231 int must_annul = *pannul_p;
1234 /* We can't do anything if there are more delay slots in SEQ than we
1235 can handle, or if we don't know that it will be a taken branch.
1237 We know that it will be a taken branch if it is either an unconditional
1238 branch or a conditional branch with a stricter branch condition. */
1240 if (XVECLEN (seq, 0) - 1 > slots_remaining
1241 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0)))
1244 for (i = 1; i < XVECLEN (seq, 0); i++)
1246 rtx trial = XVECEXP (seq, 0, i);
1248 if (insn_references_resource_p (trial, sets, 0)
1249 || insn_sets_resource_p (trial, needed, 0)
1250 || insn_sets_resource_p (trial, sets, 0)
1252 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1254 || find_reg_note (trial, REG_CC_USER, NULL_RTX)
1256 /* If TRIAL is from the fallthrough code of an annulled branch insn
1257 in SEQ, we cannot use it. */
1258 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1259 && ! INSN_FROM_TARGET_P (trial)))
1262 /* If this insn was already done (usually in a previous delay slot),
1263 pretend we put it in our delay slot. */
1264 if (redundant_insn_p (trial, insn, new_delay_list))
1268 && ((condition == const_true_rtx
1269 || (! insn_sets_resource_p (trial, other_needed, 0)
1270 && ! may_trap_p (PATTERN (trial)))))
1271 ? eligible_for_delay (insn, total_slots_filled, trial)
1273 eligible_for_annul_false (insn, total_slots_filled, trial)))
1275 temp = copy_rtx (trial);
1276 INSN_FROM_TARGET_P (temp) = 1;
1277 new_delay_list = add_to_delay_list (temp, new_delay_list);
1278 total_slots_filled++;
1280 if (--slots_remaining == 0)
1287 /* Show the place to which we will be branching. */
1288 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1290 /* Add any new insns to the delay list and update the count of the
1291 number of slots filled. */
1292 *pslots_filled = total_slots_filled;
1293 *pannul_p = must_annul;
1295 if (delay_list == 0)
1296 return new_delay_list;
1298 for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1299 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1304 /* Similar to steal_delay_list_from_target except that SEQ is on the
1305 fallthrough path of INSN. Here we only do something if the delay insn
1306 of SEQ is an unconditional branch. In that case we steal its delay slot
1307 for INSN since unconditional branches are much easier to fill. */
1310 steal_delay_list_from_fallthrough (insn, condition, seq,
1311 delay_list, sets, needed, other_needed,
1312 slots_to_fill, pslots_filled, pannul_p)
1313 rtx insn, condition;
1316 struct resources *sets, *needed, *other_needed;
1323 /* We can't do anything if SEQ's delay insn isn't an
1324 unconditional branch. */
1326 if (! simplejump_p (XVECEXP (seq, 0, 0))
1327 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1330 for (i = 1; i < XVECLEN (seq, 0); i++)
1332 rtx trial = XVECEXP (seq, 0, i);
1334 /* If TRIAL sets CC0, stealing it will move it too far from the use
1336 if (insn_references_resource_p (trial, sets, 0)
1337 || insn_sets_resource_p (trial, needed, 0)
1338 || insn_sets_resource_p (trial, sets, 0)
1340 || sets_cc0_p (PATTERN (trial))
1346 /* If this insn was already done, we don't need it. */
1347 if (redundant_insn_p (trial, insn, delay_list))
1349 delete_from_delay_slot (trial);
1354 && ((condition == const_true_rtx
1355 || (! insn_sets_resource_p (trial, other_needed, 0)
1356 && ! may_trap_p (PATTERN (trial)))))
1357 ? eligible_for_delay (insn, *pslots_filled, trial)
1359 eligible_for_annul_true (insn, *pslots_filled, trial)))
1361 delete_from_delay_slot (trial);
1362 delay_list = add_to_delay_list (trial, delay_list);
1364 if (++(*pslots_filled) == slots_to_fill)
1374 /* Try merging insns starting at THREAD which match exactly the insns in
1377 If all insns were matched and the insn was previously annulling, the
1378 annul bit will be cleared.
1380 For each insn that is merged, if the branch is or will be non-annulling,
1381 we delete the merged insn. */
1384 try_merge_delay_insns (insn, thread)
1387 rtx trial, next_trial;
1388 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1389 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1390 int slot_number = 1;
1391 int num_slots = XVECLEN (PATTERN (insn), 0);
1392 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1393 struct resources set, needed;
1394 rtx merged_insns = 0;
1397 CLEAR_RESOURCE (&needed);
1398 CLEAR_RESOURCE (&set);
1400 /* If this is not an annulling branch, take into account anything needed in
1401 NEXT_TO_MATCH. This prevents two increments from being incorrectly
1402 folded into one. If we are annulling, this would be the correct
1403 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1404 will essentially disable this optimization. This method is somewhat of
1405 a kludge, but I don't see a better way.) */
1407 mark_referenced_resources (next_to_match, &needed, 1);
1409 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1411 rtx pat = PATTERN (trial);
1413 next_trial = next_nonnote_insn (trial);
1415 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1416 if (GET_CODE (trial) == INSN
1417 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1420 if (GET_CODE (next_to_match) == GET_CODE (trial)
1422 /* We can't share an insn that sets cc0. */
1423 && ! sets_cc0_p (pat)
1425 && ! insn_references_resource_p (trial, &set, 1)
1426 && ! insn_sets_resource_p (trial, &set, 1)
1427 && ! insn_sets_resource_p (trial, &needed, 1)
1428 && (trial = try_split (pat, trial, 0)) != 0
1429 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1430 /* Have to test this condition if annul condition is different
1431 from (and less restrictive than) non-annulling one. */
1432 && eligible_for_delay (delay_insn, slot_number - 1, trial))
1434 next_trial = next_nonnote_insn (trial);
1438 update_block (trial, thread);
1439 delete_insn (trial);
1440 INSN_FROM_TARGET_P (next_to_match) = 0;
1443 merged_insns = gen_rtx (INSN_LIST, VOIDmode, trial, merged_insns);
1445 if (++slot_number == num_slots)
1448 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1450 mark_referenced_resources (next_to_match, &needed, 1);
1453 mark_set_resources (trial, &set, 0, 1);
1454 mark_referenced_resources (trial, &needed, 1);
1457 /* See if we stopped on a filled insn. If we did, try to see if its
1458 delay slots match. */
1459 if (slot_number != num_slots
1460 && trial && GET_CODE (trial) == INSN
1461 && GET_CODE (PATTERN (trial)) == SEQUENCE
1462 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1464 rtx pat = PATTERN (trial);
1466 for (i = 1; i < XVECLEN (pat, 0); i++)
1468 rtx dtrial = XVECEXP (pat, 0, i);
1470 if (! insn_references_resource_p (dtrial, &set, 1)
1471 && ! insn_sets_resource_p (dtrial, &set, 1)
1472 && ! insn_sets_resource_p (dtrial, &needed, 1)
1474 && ! sets_cc0_p (PATTERN (dtrial))
1476 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1477 && eligible_for_delay (delay_insn, slot_number - 1, dtrial))
1481 update_block (dtrial, thread);
1482 delete_from_delay_slot (dtrial);
1483 INSN_FROM_TARGET_P (next_to_match) = 0;
1486 merged_insns = gen_rtx (INSN_LIST, SImode, dtrial,
1489 if (++slot_number == num_slots)
1492 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1497 /* If all insns in the delay slot have been matched and we were previously
1498 annulling the branch, we need not any more. In that case delete all the
1499 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn the
1500 the delay list so that we know that it isn't only being used at the
1502 if (next_to_match == 0 && annul_p)
1504 for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1506 if (GET_MODE (merged_insns) == SImode)
1508 update_block (XEXP (merged_insns, 0), thread);
1509 delete_from_delay_slot (XEXP (merged_insns, 0));
1513 update_block (XEXP (merged_insns, 0), thread);
1514 delete_insn (XEXP (merged_insns, 0));
1518 INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1520 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1521 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1525 /* See if INSN is redundant with an insn in front of TARGET. Often this
1526 is called when INSN is a candidate for a delay slot of TARGET.
1527 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1528 of INSN. Often INSN will be redundant with an insn in a delay slot of
1529 some previous insn. This happens when we have a series of branches to the
1530 same label; in that case the first insn at the target might want to go
1531 into each of the delay slots.
1533 If we are not careful, this routine can take up a significant fraction
1534 of the total compilation time (4%), but only wins rarely. Hence we
1535 speed this routine up by making two passes. The first pass goes back
1536 until it hits a label and sees if it find an insn with an identical
1537 pattern. Only in this (relatively rare) event does it check for
1540 We do not split insns we encounter. This could cause us not to find a
1541 redundant insn, but the cost of splitting seems greater than the possible
1542 gain in rare cases. */
1545 redundant_insn_p (insn, target, delay_list)
1550 rtx target_main = target;
1551 rtx ipat = PATTERN (insn);
1553 struct resources needed, set;
1556 /* Scan backwards looking for a match. */
1557 for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
1559 if (GET_CODE (trial) == CODE_LABEL)
1562 if (GET_CODE (trial) != INSN && GET_CODE (trial) != JUMP_INSN
1563 && GET_CODE (trial) != JUMP_INSN)
1566 pat = PATTERN (trial);
1567 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1570 if (GET_CODE (pat) == SEQUENCE)
1572 /* Stop for a CALL and its delay slots because it difficult to track
1573 its resource needs correctly. */
1574 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1577 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1578 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
1579 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat))
1582 /* If found a match, exit this loop early. */
1587 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat))
1591 /* If we didn't find an insn that matches, return 0. */
1595 /* See what resources this insn sets and needs. If they overlap, or
1596 if this insn references CC0, it can't be redundant. */
1598 CLEAR_RESOURCE (&needed);
1599 CLEAR_RESOURCE (&set);
1600 mark_set_resources (insn, &set, 0, 1);
1601 mark_referenced_resources (insn, &needed, 1);
1603 /* If TARGET is a SEQUENCE, get the main insn. */
1604 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1605 target_main = XVECEXP (PATTERN (target), 0, 0);
1607 if (resource_conflicts_p (&needed, &set)
1609 || reg_mentioned_p (cc0_rtx, ipat)
1611 /* The insn requiring the delay may not set anything needed or set by
1613 || insn_sets_resource_p (target_main, &needed, 1)
1614 || insn_sets_resource_p (target_main, &set, 1))
1617 /* Insns we pass may not set either NEEDED or SET, so merge them for
1619 needed.memory |= set.memory;
1620 IOR_HARD_REG_SET (needed.regs, set.regs);
1622 /* This insn isn't redundant if it conflicts with an insn that either is
1623 or will be in a delay slot of TARGET. */
1627 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
1629 delay_list = XEXP (delay_list, 1);
1632 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1633 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
1634 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
1637 /* Scan backwards until we reach a label or an insn that uses something
1638 INSN sets or sets something insn uses or sets. */
1640 for (trial = PREV_INSN (target);
1641 trial && GET_CODE (trial) != CODE_LABEL;
1642 trial = PREV_INSN (trial))
1644 if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
1645 && GET_CODE (trial) != JUMP_INSN)
1648 pat = PATTERN (trial);
1649 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1652 if (GET_CODE (pat) == SEQUENCE)
1654 /* If this is a CALL_INSN and its delay slots, it is hard to track
1655 the resource needs properly, so give up. */
1656 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1659 /* See if any of the insns in the delay slot match, updating
1660 resource requirements as we go. */
1661 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1663 rtx candidate = XVECEXP (pat, 0, i);
1665 /* If an insn will be annulled if the branch is false, it isn't
1666 considered as a possible duplicate insn. */
1667 if (rtx_equal_p (PATTERN (candidate), ipat)
1668 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1669 && INSN_FROM_TARGET_P (candidate)))
1671 /* Show that this insn will be used in the sequel. */
1672 INSN_FROM_TARGET_P (candidate) = 0;
1676 /* Unless this is an annulled insn from the target of a branch,
1677 we must stop if it sets anything needed or set by INSN. */
1678 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1679 || ! INSN_FROM_TARGET_P (candidate))
1680 && insn_sets_resource_p (candidate, &needed, 1))
1685 /* If the insn requiring the delay slot conflicts with INSN, we
1687 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
1692 /* See if TRIAL is the same as INSN. */
1693 pat = PATTERN (trial);
1694 if (rtx_equal_p (pat, ipat))
1697 /* Can't go any further if TRIAL conflicts with INSN. */
1698 if (insn_sets_resource_p (trial, &needed, 1))
1706 /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero,
1707 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1708 is non-zero, we are allowed to fall into this thread; otherwise, we are
1711 If LABEL is used more than one or we pass a label other than LABEL before
1712 finding an active insn, we do not own this thread. */
1715 own_thread_p (thread, label, allow_fallthrough)
1718 int allow_fallthrough;
1723 /* We don't own the function end. */
1727 /* Get the first active insn, or THREAD, if it is an active insn. */
1728 active_insn = next_active_insn (PREV_INSN (thread));
1730 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
1731 if (GET_CODE (insn) == CODE_LABEL
1732 && (insn != label || LABEL_NUSES (insn) != 1))
1735 if (allow_fallthrough)
1738 /* Ensure that we reach a BARRIER before any insn or label. */
1739 for (insn = prev_nonnote_insn (thread);
1740 insn == 0 || GET_CODE (insn) != BARRIER;
1741 insn = prev_nonnote_insn (insn))
1743 || GET_CODE (insn) == CODE_LABEL
1744 || (GET_CODE (insn) == INSN
1745 && GET_CODE (PATTERN (insn)) != USE
1746 && GET_CODE (PATTERN (insn)) != CLOBBER))
1752 /* Find the number of the basic block that starts closest to INSN. Return -1
1753 if we couldn't find such a basic block. */
1756 find_basic_block (insn)
1761 /* Scan backwards to the previous BARRIER. Then see if we can find a
1762 label that starts a basic block. Return the basic block number. */
1764 for (insn = prev_nonnote_insn (insn);
1765 insn && GET_CODE (insn) != BARRIER;
1766 insn = prev_nonnote_insn (insn))
1769 /* The start of the function is basic block zero. */
1773 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
1774 anything other than a CODE_LABEL or note, we can't find this code. */
1775 for (insn = next_nonnote_insn (insn);
1776 insn && GET_CODE (insn) == CODE_LABEL;
1777 insn = next_nonnote_insn (insn))
1779 for (i = 0; i < n_basic_blocks; i++)
1780 if (insn == basic_block_head[i])
1787 /* Called when INSN is being moved from a location near the target of a jump.
1788 We leave a marker of the form (use (INSN)) immediately in front
1789 of WHERE for mark_target_live_regs. These markers will be deleted when
1792 We used to try to update the live status of registers if WHERE is at
1793 the start of a basic block, but that can't work since we may remove a
1794 BARRIER in relax_delay_slots. */
1797 update_block (insn, where)
1803 /* Ignore if this was in a delay slot and it came from the target of
1805 if (INSN_FROM_TARGET_P (insn))
1808 emit_insn_before (gen_rtx (USE, VOIDmode, insn), where);
1810 /* INSN might be making a value live in a block where it didn't use to
1811 be. So recompute liveness information for this block. */
1813 b = find_basic_block (insn);
1818 /* Marks registers possibly live at the current place being scanned by
1819 mark_target_live_regs. Used only by next two function. */
1821 static HARD_REG_SET current_live_regs;
1823 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
1824 Also only used by the next two functions. */
1826 static HARD_REG_SET pending_dead_regs;
1828 /* Utility function called from mark_target_live_regs via note_stores.
1829 It deadens any CLOBBERed registers and livens any SET registers. */
1832 update_live_status (dest, x)
1836 int first_regno, last_regno;
1839 if (GET_CODE (dest) != REG
1840 && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
1843 if (GET_CODE (dest) == SUBREG)
1844 first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1846 first_regno = REGNO (dest);
1848 last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1850 if (GET_CODE (x) == CLOBBER)
1851 for (i = first_regno; i < last_regno; i++)
1852 CLEAR_HARD_REG_BIT (current_live_regs, i);
1854 for (i = first_regno; i < last_regno; i++)
1856 SET_HARD_REG_BIT (current_live_regs, i);
1857 CLEAR_HARD_REG_BIT (pending_dead_regs, i);
1861 /* Similar to next_insn, but ignores insns in the delay slots of
1862 an annulled branch. */
1865 next_insn_no_annul (insn)
1870 /* If INSN is an annulled branch, skip any insns from the target
1872 if (INSN_ANNULLED_BRANCH_P (insn)
1873 && NEXT_INSN (PREV_INSN (insn)) != insn)
1874 while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
1875 insn = NEXT_INSN (insn);
1877 insn = NEXT_INSN (insn);
1878 if (insn && GET_CODE (insn) == INSN
1879 && GET_CODE (PATTERN (insn)) == SEQUENCE)
1880 insn = XVECEXP (PATTERN (insn), 0, 0);
1886 /* Set the resources that are live at TARGET.
1888 If TARGET is zero, we refer to the end of the current function and can
1889 return our precomputed value.
1891 Otherwise, we try to find out what is live by consulting the basic block
1892 information. This is tricky, because we must consider the actions of
1893 reload and jump optimization, which occur after the basic block information
1896 Accordingly, we proceed as follows::
1898 We find the previous BARRIER and look at all immediately following labels
1899 (with no intervening active insns) to see if any of them start a basic
1900 block. If we hit the start of the function first, we use block 0.
1902 Once we have found a basic block and a corresponding first insns, we can
1903 accurately compute the live status from basic_block_live_regs and
1904 reg_renumber. (By starting at a label following a BARRIER, we are immune
1905 to actions taken by reload and jump.) Then we scan all insns between
1906 that point and our target. For each CLOBBER (or for call-clobbered regs
1907 when we pass a CALL_INSN), mark the appropriate registers are dead. For
1908 a SET, mark them as live.
1910 We have to be careful when using REG_DEAD notes because they are not
1911 updated by such things as find_equiv_reg. So keep track of registers
1912 marked as dead that haven't been assigned to, and mark them dead at the
1913 next CODE_LABEL since reload and jump won't propagate values across labels.
1915 If we cannot find the start of a basic block (should be a very rare
1916 case, if it can happen at all), mark everything as potentially live.
1918 Next, scan forward from TARGET looking for things set or clobbered
1919 before they are used. These are not live.
1921 Because we can be called many times on the same target, save our results
1922 in a hash table indexed by INSN_UID. */
1925 mark_target_live_regs (target, res)
1927 struct resources *res;
1931 struct target_info *tinfo;
1935 HARD_REG_SET scratch;
1936 struct resources set, needed;
1939 /* Handle end of function. */
1942 *res = end_of_function_needs;
1946 /* We have to assume memory is needed, but the CC isn't. */
1951 /* See if we have computed this value already. */
1952 for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1953 tinfo; tinfo = tinfo->next)
1954 if (tinfo->uid == INSN_UID (target))
1957 /* Start by getting the basic block number. If we have saved information,
1958 we can get it from there unless the insn at the start of the basic block
1959 has been deleted. */
1960 if (tinfo && tinfo->block != -1
1961 && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
1965 b = find_basic_block (target);
1969 /* If the information is up-to-date, use it. Otherwise, we will
1971 if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
1973 COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
1979 /* Allocate a place to put our results and chain it into the
1981 tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
1982 tinfo->uid = INSN_UID (target);
1984 tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1985 target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
1988 CLEAR_HARD_REG_SET (pending_dead_regs);
1990 /* If we found a basic block, get the live registers from it and update
1991 them with anything set or killed between its start and the insn before
1992 TARGET. Otherwise, we must assume everything is live. */
1995 regset regs_live = basic_block_live_at_start[b];
1997 REGSET_ELT_TYPE bit;
1999 rtx start_insn, stop_insn;
2001 /* Compute hard regs live at start of block -- this is the real hard regs
2002 marked live, plus live pseudo regs that have been renumbered to
2006 current_live_regs = *regs_live;
2008 COPY_HARD_REG_SET (current_live_regs, regs_live);
2011 for (offset = 0, i = 0; offset < regset_size; offset++)
2013 if (regs_live[offset] == 0)
2014 i += REGSET_ELT_BITS;
2016 for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
2017 if ((regs_live[offset] & bit)
2018 && (regno = reg_renumber[i]) >= 0)
2020 j < regno + HARD_REGNO_NREGS (regno,
2021 PSEUDO_REGNO_MODE (i));
2023 SET_HARD_REG_BIT (current_live_regs, j);
2026 /* Get starting and ending insn, handling the case where each might
2028 start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2031 if (GET_CODE (start_insn) == INSN
2032 && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2033 start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2035 if (GET_CODE (stop_insn) == INSN
2036 && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2037 stop_insn = next_insn (PREV_INSN (stop_insn));
2039 for (insn = start_insn; insn != stop_insn;
2040 insn = next_insn_no_annul (insn))
2043 rtx real_insn = insn;
2045 /* If this insn is from the target of a branch, it isn't going to
2046 be used in the sequel. If it is used in both cases, this
2047 test will not be true. */
2048 if (INSN_FROM_TARGET_P (insn))
2051 /* If this insn is a USE made by update_block, we care about the
2053 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2054 && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
2055 || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN
2056 || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN))
2057 real_insn = XEXP (PATTERN (insn), 0);
2059 if (GET_CODE (real_insn) == CALL_INSN)
2061 /* CALL clobbers all call-used regs that aren't fixed except
2062 sp, ap, and fp. Do this before setting the result of the
2064 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2065 if (call_used_regs[i]
2066 && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2067 && i != ARG_POINTER_REGNUM
2068 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2069 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2071 #ifdef PIC_OFFSET_TABLE_REGNUM
2072 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2075 CLEAR_HARD_REG_BIT (current_live_regs, i);
2077 /* A CALL_INSN sets any global register live, since it may
2078 have been modified by the call. */
2079 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2081 SET_HARD_REG_BIT (current_live_regs, i);
2084 /* Mark anything killed in an insn to be deadened at the next
2085 label. Ignore USE insns; the only REG_DEAD notes will be for
2086 parameters. But they might be early. A CALL_INSN will usually
2087 clobber registers used for parameters. It isn't worth bothering
2088 with the unlikely case when it won't. */
2089 if ((GET_CODE (real_insn) == INSN
2090 && GET_CODE (PATTERN (real_insn)) != USE)
2091 || GET_CODE (real_insn) == JUMP_INSN
2092 || GET_CODE (real_insn) == CALL_INSN)
2094 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2095 if (REG_NOTE_KIND (link) == REG_DEAD
2096 && GET_CODE (XEXP (link, 0)) == REG
2097 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2099 int first_regno = REGNO (XEXP (link, 0));
2102 + HARD_REGNO_NREGS (first_regno,
2103 GET_MODE (XEXP (link, 0))));
2105 for (i = first_regno; i < last_regno; i++)
2106 SET_HARD_REG_BIT (pending_dead_regs, i);
2109 note_stores (PATTERN (real_insn), update_live_status);
2111 /* If any registers were unused after this insn, kill them.
2112 These notes will always be accurate. */
2113 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2114 if (REG_NOTE_KIND (link) == REG_UNUSED
2115 && GET_CODE (XEXP (link, 0)) == REG
2116 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2118 int first_regno = REGNO (XEXP (link, 0));
2121 + HARD_REGNO_NREGS (first_regno,
2122 GET_MODE (XEXP (link, 0))));
2124 for (i = first_regno; i < last_regno; i++)
2125 CLEAR_HARD_REG_BIT (current_live_regs, i);
2129 if (GET_CODE (real_insn) == CODE_LABEL)
2131 /* A label clobbers the pending dead registers since neither
2132 reload nor jump will propagate a value across a label. */
2133 AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2134 CLEAR_HARD_REG_SET (pending_dead_regs);
2138 COPY_HARD_REG_SET (res->regs, current_live_regs);
2140 tinfo->bb_tick = bb_ticks[b];
2143 /* We didn't find the start of a basic block. Assume everything
2144 in use. This should happen only extremely rarely. */
2145 SET_HARD_REG_SET (res->regs);
2147 /* Now step forward from TARGET looking for registers that are set before
2148 they are used. These are dead. If we pass a label, any pending dead
2149 registers that weren't yet used can be made dead. Stop when we pass a
2150 conditional JUMP_INSN; follow the first few unconditional branches. */
2152 CLEAR_RESOURCE (&set);
2153 CLEAR_RESOURCE (&needed);
2155 for (insn = target; insn; insn = next)
2157 rtx this_jump_insn = insn;
2159 next = NEXT_INSN (insn);
2160 switch (GET_CODE (insn))
2163 AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2164 AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2165 CLEAR_HARD_REG_SET (pending_dead_regs);
2173 if (GET_CODE (PATTERN (insn)) == USE
2174 || GET_CODE (PATTERN (insn)) == CLOBBER)
2176 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2178 /* An unconditional jump can be used to fill the delay slot
2179 of a call, so search for a JUMP_INSN in any position. */
2180 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2182 this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
2183 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2189 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2191 if (jump_count++ < 10
2192 && (simplejump_p (this_jump_insn)
2193 || GET_CODE (PATTERN (this_jump_insn)) == RETURN))
2195 next = next_active_insn (JUMP_LABEL (this_jump_insn));
2199 jump_target = JUMP_LABEL (this_jump_insn);
2206 mark_referenced_resources (insn, &needed, 1);
2207 mark_set_resources (insn, &set, 0, 1);
2209 COPY_HARD_REG_SET (scratch, set.regs);
2210 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2211 AND_COMPL_HARD_REG_SET (res->regs, scratch);
2214 /* If we hit an unconditional branch, we have another way of finding out
2215 what is live: we can see what is live at the branch target and include
2216 anything used but not set before the branch. The only things that are
2217 live are those that are live using the above test and the test below.
2219 Don't try this if we expired our jump count above, since that would
2220 mean there may be an infinite loop in the function being compiled. */
2222 if (jump_insn && jump_count < 10)
2224 struct resources new_resources;
2225 rtx stop_insn = next_active_insn (jump_insn);
2227 mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2228 CLEAR_RESOURCE (&set);
2229 CLEAR_RESOURCE (&needed);
2231 /* Include JUMP_INSN in the needed registers. */
2232 for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2234 mark_referenced_resources (insn, &needed, 1);
2236 COPY_HARD_REG_SET (scratch, needed.regs);
2237 AND_COMPL_HARD_REG_SET (scratch, set.regs);
2238 IOR_HARD_REG_SET (new_resources.regs, scratch);
2240 mark_set_resources (insn, &set, 0, 1);
2243 AND_HARD_REG_SET (res->regs, new_resources.regs);
2246 COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2249 /* Scan a function looking for insns that need a delay slot and find insns to
2250 put into the delay slot.
2252 NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2253 as calls). We do these first since we don't want jump insns (that are
2254 easier to fill) to get the only insns that could be used for non-jump insns.
2255 When it is zero, only try to fill JUMP_INSNs.
2257 When slots are filled in this manner, the insns (including the
2258 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2259 it is possible to tell whether a delay slot has really been filled
2260 or not. `final' knows how to deal with this, by communicating
2261 through FINAL_SEQUENCE. */
2264 fill_simple_delay_slots (first, non_jumps_p)
2267 register rtx insn, pat, trial, next_trial;
2269 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2270 struct resources needed, set;
2271 register int slots_to_fill, slots_filled;
2274 for (i = 0; i < num_unfilled_slots; i++)
2276 /* Get the next insn to fill. If it has already had any slots assigned,
2277 we can't do anything with it. Maybe we'll improve this later. */
2279 insn = unfilled_slots_base[i];
2281 || INSN_DELETED_P (insn)
2282 || (GET_CODE (insn) == INSN
2283 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2284 || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2285 || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2288 slots_to_fill = num_delay_slots (insn);
2289 if (slots_to_fill == 0)
2292 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2293 says how many. After initialization, first try optimizing
2296 nop add %o7,.-L1,%o7
2300 If this case applies, the delay slot of the call is filled with
2301 the unconditional jump. This is done first to avoid having the
2302 delay slot of the call filled in the backward scan. Also, since
2303 the unconditional jump is likely to also have a delay slot, that
2304 insn must exist when it is subsequently scanned. */
2309 if (GET_CODE (insn) == CALL_INSN
2310 && (trial = next_active_insn (insn))
2311 && GET_CODE (trial) == JUMP_INSN
2312 && simplejump_p (trial)
2313 && eligible_for_delay (insn, slots_filled, trial)
2314 && no_labels_between_p (insn, trial))
2317 delay_list = add_to_delay_list (trial, delay_list);
2318 /* Remove the unconditional jump from consideration for delay slot
2319 filling and unthread it. */
2320 if (unfilled_slots_base[i + 1] == trial)
2321 unfilled_slots_base[i + 1] = 0;
2323 rtx next = NEXT_INSN (trial);
2324 rtx prev = PREV_INSN (trial);
2326 NEXT_INSN (prev) = next;
2328 PREV_INSN (next) = prev;
2332 /* Now, scan backwards from the insn to search for a potential
2333 delay-slot candidate. Stop searching when a label or jump is hit.
2335 For each candidate, if it is to go into the delay slot (moved
2336 forward in execution sequence), it must not need or set any resources
2337 that were set by later insns and must not set any resources that
2338 are needed for those insns.
2340 The delay slot insn itself sets resources unless it is a call
2341 (in which case the called routine, not the insn itself, is doing
2344 if (slots_filled < slots_to_fill)
2346 CLEAR_RESOURCE (&needed);
2347 CLEAR_RESOURCE (&set);
2348 mark_set_resources (insn, &set, 0, 0);
2349 mark_referenced_resources (insn, &needed, 0);
2351 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2354 next_trial = prev_nonnote_insn (trial);
2356 /* This must be an INSN or CALL_INSN. */
2357 pat = PATTERN (trial);
2359 /* USE and CLOBBER at this level was just for flow; ignore it. */
2360 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2363 /* Check for resource conflict first, to avoid unnecessary
2365 if (! insn_references_resource_p (trial, &set, 1)
2366 && ! insn_sets_resource_p (trial, &set, 1)
2367 && ! insn_sets_resource_p (trial, &needed, 1)
2369 /* Can't separate set of cc0 from its use. */
2370 && ! (reg_mentioned_p (cc0_rtx, pat)
2371 && ! sets_cc0_p (cc0_rtx, pat))
2375 trial = try_split (pat, trial, 1);
2376 next_trial = prev_nonnote_insn (trial);
2377 if (eligible_for_delay (insn, slots_filled, trial))
2379 /* In this case, we are searching backward, so if we
2380 find insns to put on the delay list, we want
2381 to put them at the head, rather than the
2382 tail, of the list. */
2384 delay_list = gen_rtx (INSN_LIST, VOIDmode,
2386 update_block (trial, trial);
2387 delete_insn (trial);
2388 if (slots_to_fill == ++slots_filled)
2394 mark_set_resources (trial, &set, 0, 1);
2395 mark_referenced_resources (trial, &needed, 1);
2399 /* If all needed slots haven't been filled, we come here. */
2401 /* Try to optimize case of jumping around a single insn. */
2402 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2403 if (slots_filled != slots_to_fill
2405 && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
2407 delay_list = optimize_skip (insn);
2413 /* Try to get insns from beyond the insn needing the delay slot.
2414 These insns can neither set or reference resources set in insns being
2415 skipped, cannot set resources in the insn being skipped, and, if this
2416 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2417 call might not return).
2419 If this is a conditional jump, see if it merges back to us early
2420 enough for us to pick up insns from the merge point. Don't do
2421 this if there is another branch to our label unless we pass all of
2424 Another similar merge is if we jump to the same place that a
2425 later unconditional jump branches to. In that case, we don't
2426 care about the number of uses of our label. */
2428 if (slots_filled != slots_to_fill
2429 && (GET_CODE (insn) != JUMP_INSN
2430 || (condjump_p (insn) && ! simplejump_p (insn)
2431 && JUMP_LABEL (insn) != 0)))
2434 int maybe_never = 0;
2435 int passed_label = 0;
2437 struct resources needed_at_jump;
2439 CLEAR_RESOURCE (&needed);
2440 CLEAR_RESOURCE (&set);
2442 if (GET_CODE (insn) == CALL_INSN)
2444 mark_set_resources (insn, &set, 0, 1);
2445 mark_referenced_resources (insn, &needed, 1);
2450 mark_set_resources (insn, &set, 0, 0);
2451 mark_referenced_resources (insn, &needed, 0);
2452 if (GET_CODE (insn) == JUMP_INSN)
2454 /* Get our target and show how many more uses we want to
2455 see before we hit the label. */
2456 target = JUMP_LABEL (insn);
2457 target_uses = LABEL_NUSES (target) - 1;
2462 for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2464 rtx pat, trial_delay;
2466 next_trial = next_nonnote_insn (trial);
2468 if (GET_CODE (trial) == CODE_LABEL)
2472 /* If this is our target, see if we have seen all its uses.
2473 If so, indicate we have passed our target and ignore it.
2474 All other labels cause us to stop our search. */
2475 if (trial == target && target_uses == 0)
2483 else if (GET_CODE (trial) == BARRIER)
2486 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
2487 pat = PATTERN (trial);
2489 /* Stand-alone USE and CLOBBER are just for flow. */
2490 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2493 /* If this already has filled delay slots, get the insn needing
2495 if (GET_CODE (pat) == SEQUENCE)
2496 trial_delay = XVECEXP (pat, 0, 0);
2498 trial_delay = trial;
2500 /* If this is a jump insn to our target, indicate that we have
2501 seen another jump to it. If we aren't handling a conditional
2502 jump, stop our search. Otherwise, compute the needs at its
2503 target and add them to NEEDED. */
2504 if (GET_CODE (trial_delay) == JUMP_INSN)
2508 else if (JUMP_LABEL (trial_delay) == target)
2512 mark_target_live_regs
2513 (next_active_insn (JUMP_LABEL (trial_delay)),
2515 needed.memory |= needed_at_jump.memory;
2516 IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
2520 /* See if we have a resource problem before we try to
2523 && GET_CODE (pat) != SEQUENCE
2524 && ! insn_references_resource_p (trial, &set, 1)
2525 && ! insn_sets_resource_p (trial, &set, 1)
2526 && ! insn_sets_resource_p (trial, &needed, 1)
2528 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2530 && ! (maybe_never && may_trap_p (pat))
2531 && (trial = try_split (pat, trial, 0))
2532 && eligible_for_delay (insn, slots_filled, trial))
2534 next_trial = next_nonnote_insn (trial);
2535 delay_list = add_to_delay_list (trial, delay_list);
2538 if (reg_mentioned_p (cc0_rtx, pat))
2539 link_cc0_insns (trial);
2543 update_block (trial, trial);
2544 delete_insn (trial);
2545 if (slots_to_fill == ++slots_filled)
2550 mark_set_resources (trial, &set, 0, 1);
2551 mark_referenced_resources (trial, &needed, 1);
2553 /* Ensure we don't put insns between the setting of cc and the
2554 comparison by moving a setting of cc into an earlier delay
2555 slot since these insns could clobber the condition code. */
2558 /* If this is a call or jump, we might not get here. */
2559 if (GET_CODE (trial) == CALL_INSN
2560 || GET_CODE (trial) == JUMP_INSN)
2564 /* If there are slots left to fill and our search was stopped by an
2565 unconditional branch, try the insn at the branch target. We can
2566 redirect the branch if it works. */
2567 if (slots_to_fill != slots_filled
2569 && GET_CODE (trial) == JUMP_INSN
2570 && simplejump_p (trial)
2571 && (target == 0 || JUMP_LABEL (trial) == target)
2572 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2573 && ! (GET_CODE (next_trial) == INSN
2574 && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2575 && ! insn_references_resource_p (next_trial, &set, 1)
2576 && ! insn_sets_resource_p (next_trial, &set, 1)
2577 && ! insn_sets_resource_p (next_trial, &needed, 1)
2579 && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2581 && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2582 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2583 && eligible_for_delay (insn, slots_filled, next_trial))
2585 rtx new_label = next_active_insn (next_trial);
2588 new_label = get_label_before (new_label);
2591 = add_to_delay_list (copy_rtx (next_trial), delay_list);
2593 redirect_jump (trial, new_label);
2595 /* If we merged because we both jumped to the same place,
2596 redirect the original insn also. */
2598 redirect_jump (insn, new_label);
2603 unfilled_slots_base[i]
2604 = emit_delay_sequence (insn, delay_list,
2605 slots_filled, slots_to_fill);
2607 if (slots_to_fill == slots_filled)
2608 unfilled_slots_base[i] = 0;
2610 note_delay_statistics (slots_filled, 0);
2613 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2614 /* See if the epilogue needs any delay slots. Try to fill them if so.
2615 The only thing we can do is scan backwards from the end of the
2616 function. If we did this in a previous pass, it is incorrect to do it
2618 if (current_function_epilogue_delay_list)
2621 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2622 if (slots_to_fill == 0)
2626 CLEAR_RESOURCE (&needed);
2627 CLEAR_RESOURCE (&set);
2629 for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2630 trial = PREV_INSN (trial))
2632 if (GET_CODE (trial) == NOTE)
2634 pat = PATTERN (trial);
2635 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2638 if (! insn_references_resource_p (trial, &set, 1)
2639 && ! insn_sets_resource_p (trial, &needed, 1)
2641 /* Don't want to mess with cc0 here. */
2642 && ! reg_mentioned_p (cc0_rtx, pat)
2646 trial = try_split (pat, trial, 1);
2647 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2649 /* Here as well we are searching backward, so put the
2650 insns we find on the head of the list. */
2652 current_function_epilogue_delay_list
2653 = gen_rtx (INSN_LIST, VOIDmode, trial,
2654 current_function_epilogue_delay_list);
2655 mark_referenced_resources (trial, &end_of_function_needs, 1);
2656 update_block (trial, trial);
2657 delete_insn (trial);
2659 /* Clear deleted bit so final.c will output the insn. */
2660 INSN_DELETED_P (trial) = 0;
2662 if (slots_to_fill == ++slots_filled)
2668 mark_set_resources (trial, &set, 0, 1);
2669 mark_referenced_resources (trial, &needed, 1);
2672 note_delay_statistics (slots_filled, 0);
2676 /* Try to find insns to place in delay slots.
2678 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2679 or is an unconditional branch if CONDITION is const_true_rtx.
2680 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2682 THREAD is a flow-of-control, either the insns to be executed if the
2683 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2685 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2686 to see if any potential delay slot insns set things needed there.
2688 LIKELY is non-zero if it is extremely likely that the branch will be
2689 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2690 end of a loop back up to the top.
2692 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2693 thread. I.e., it is the fallthrough code of our jump or the target of the
2694 jump when we are the only jump going there.
2696 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2697 case, we can only take insns from the head of the thread for our delay
2698 slot. We then adjust the jump to point after the insns we have taken. */
2701 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
2702 thread_if_true, own_thread, own_opposite_thread,
2703 slots_to_fill, pslots_filled)
2706 rtx thread, opposite_thread;
2709 int own_thread, own_opposite_thread;
2710 int slots_to_fill, *pslots_filled;
2714 struct resources opposite_needed, set, needed;
2719 /* Validate our arguments. */
2720 if ((condition == const_true_rtx && ! thread_if_true)
2721 || (! own_thread && ! thread_if_true))
2724 /* If our thread is the end of subroutine, we can't get any delay
2729 /* If this is an unconditional branch, nothing is needed at the
2730 opposite thread. Otherwise, compute what is needed there. */
2731 if (condition == const_true_rtx)
2732 CLEAR_RESOURCE (&opposite_needed);
2734 mark_target_live_regs (opposite_thread, &opposite_needed);
2736 /* If the insn at THREAD can be split, do it here to avoid having to
2737 update THREAD and NEW_THREAD if it is done in the loop below. Also
2738 initialize NEW_THREAD. */
2740 new_thread = thread = try_split (PATTERN (thread), thread, 0);
2742 /* Scan insns at THREAD. We are looking for an insn that can be removed
2743 from THREAD (it neither sets nor references resources that were set
2744 ahead of it and it doesn't set anything needs by the insns ahead of
2745 it) and that either can be placed in an annulling insn or aren't
2746 needed at OPPOSITE_THREAD. */
2748 CLEAR_RESOURCE (&needed);
2749 CLEAR_RESOURCE (&set);
2751 /* If we do not own this thread, we must stop as soon as we find
2752 something that we can't put in a delay slot, since all we can do
2753 is branch into THREAD at a later point. Therefore, labels stop
2754 the search if this is not the `true' thread. */
2756 for (trial = thread;
2757 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2758 trial = next_nonnote_insn (trial))
2762 /* If we have passed a label, we no longer own this thread. */
2763 if (GET_CODE (trial) == CODE_LABEL)
2769 pat = PATTERN (trial);
2770 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2773 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2774 don't separate or copy insns that set and use CC0. */
2775 if (! insn_references_resource_p (trial, &set, 1)
2776 && ! insn_sets_resource_p (trial, &set, 1)
2777 && ! insn_sets_resource_p (trial, &needed, 1)
2779 && ! (reg_mentioned_p (cc0_rtx, pat)
2780 && (! own_thread || ! sets_cc0_p (pat)))
2784 /* If TRIAL is redundant with some insn before INSN, we don't
2785 actually need to add it to the delay list; we can merely pretend
2787 if (redundant_insn_p (trial, insn, delay_list))
2791 update_block (trial, thread);
2792 delete_insn (trial);
2795 new_thread = next_active_insn (trial);
2800 /* There are two ways we can win: If TRIAL doesn't set anything
2801 needed at the opposite thread and can't trap, or if it can
2802 go into an annulled delay slot. */
2803 if (condition == const_true_rtx
2804 || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2805 && ! may_trap_p (pat)))
2807 trial = try_split (pat, trial, 0);
2808 pat = PATTERN (trial);
2809 if (eligible_for_delay (insn, *pslots_filled, trial))
2813 #ifdef ANNUL_IFTRUE_SLOTS
2816 #ifdef ANNUL_IFFALSE_SLOTS
2821 trial = try_split (pat, trial, 0);
2822 pat = PATTERN (trial);
2824 ? eligible_for_annul_false (insn, *pslots_filled, trial)
2825 : eligible_for_annul_true (insn, *pslots_filled, trial)))
2833 if (reg_mentioned_p (cc0_rtx, pat))
2834 link_cc0_insns (trial);
2837 /* If we own this thread, delete the insn. If this is the
2838 destination of a branch, show that a basic block status
2839 may have been updated. In any case, mark the new
2840 starting point of this thread. */
2843 update_block (trial, thread);
2844 delete_insn (trial);
2847 new_thread = next_active_insn (trial);
2849 temp = own_thread ? trial : copy_rtx (trial);
2851 INSN_FROM_TARGET_P (temp) = 1;
2853 delay_list = add_to_delay_list (temp, delay_list);
2855 if (slots_to_fill == ++(*pslots_filled))
2857 /* Even though we have filled all the slots, we
2858 may be branching to a location that has a
2859 redundant insn. Skip any if so. */
2860 while (new_thread && ! own_thread
2861 && ! insn_sets_resource_p (new_thread, &set, 1)
2862 && ! insn_sets_resource_p (new_thread, &needed, 1)
2863 && ! insn_references_resource_p (new_thread,
2865 && redundant_insn_p (new_thread, insn,
2867 new_thread = next_active_insn (new_thread);
2876 /* This insn can't go into a delay slot. */
2878 mark_set_resources (trial, &set, 0, 1);
2879 mark_referenced_resources (trial, &needed, 1);
2881 /* Ensure we don't put insns between the setting of cc and the comparison
2882 by moving a setting of cc into an earlier delay slot since these insns
2883 could clobber the condition code. */
2886 /* If this insn is a register-register copy and the next insn has
2887 a use of our destination, change it to use our source. That way,
2888 it will become a candidate for our delay slot the next time
2889 through this loop. This case occurs commonly in loops that
2892 We could check for more complex cases than those tested below,
2893 but it doesn't seem worth it. It might also be a good idea to try
2894 to swap the two insns. That might do better.
2896 We can't do this if the next insn modifies our source, because that
2897 would make the replacement into the insn invalid. This also
2898 prevents updating the contents of a PRE_INC. */
2900 if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2901 && GET_CODE (SET_SRC (pat)) == REG
2902 && GET_CODE (SET_DEST (pat)) == REG)
2904 rtx next = next_nonnote_insn (trial);
2906 if (next && GET_CODE (next) == INSN
2907 && GET_CODE (PATTERN (next)) != USE
2908 && ! reg_set_p (SET_DEST (pat), next)
2909 && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
2910 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2914 /* If we stopped on a branch insn that has delay slots, see if we can
2915 steal some of the insns in those slots. */
2916 if (trial && GET_CODE (trial) == INSN
2917 && GET_CODE (PATTERN (trial)) == SEQUENCE
2918 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2920 /* If this is the `true' thread, we will want to follow the jump,
2921 so we can only do this if we have taken everything up to here. */
2922 if (thread_if_true && trial == new_thread)
2924 = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2925 delay_list, &set, &needed,
2926 &opposite_needed, slots_to_fill,
2927 pslots_filled, &must_annul,
2929 else if (! thread_if_true)
2931 = steal_delay_list_from_fallthrough (insn, condition,
2933 delay_list, &set, &needed,
2934 &opposite_needed, slots_to_fill,
2935 pslots_filled, &must_annul);
2938 /* If we haven't found anything for this delay slot and it is very
2939 likely that the branch will be taken, see if the insn at our target
2940 increments or decrements a register with an increment that does not
2941 depend on the destination register. If so, try to place the opposite
2942 arithmetic insn after the jump insn and put the arithmetic insn in the
2943 delay slot. If we can't do this, return. */
2944 if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
2946 rtx pat = PATTERN (new_thread);
2951 pat = PATTERN (trial);
2953 if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
2954 || ! eligible_for_delay (insn, 0, trial))
2957 dest = SET_DEST (pat), src = SET_SRC (pat);
2958 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2959 && rtx_equal_p (XEXP (src, 0), dest)
2960 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
2962 rtx other = XEXP (src, 1);
2966 /* If this is a constant adjustment, use the same code with
2967 the negated constant. Otherwise, reverse the sense of the
2969 if (GET_CODE (other) == CONST_INT)
2970 new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest,
2971 negate_rtx (GET_MODE (src), other));
2973 new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS,
2974 GET_MODE (src), dest, other);
2976 ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith),
2979 if (recog_memoized (ninsn) < 0
2980 || (insn_extract (ninsn),
2981 ! constrain_operands (INSN_CODE (ninsn), 1)))
2983 delete_insn (ninsn);
2989 update_block (trial, thread);
2990 delete_insn (trial);
2993 new_thread = next_active_insn (trial);
2995 ninsn = own_thread ? trial : copy_rtx (trial);
2997 INSN_FROM_TARGET_P (ninsn) = 1;
2999 delay_list = add_to_delay_list (ninsn, NULL_RTX);
3004 if (delay_list && must_annul)
3005 INSN_ANNULLED_BRANCH_P (insn) = 1;
3007 /* If we are to branch into the middle of this thread, find an appropriate
3008 label or make a new one if none, and redirect INSN to it. If we hit the
3009 end of the function, use the end-of-function label. */
3010 if (new_thread != thread)
3014 if (! thread_if_true)
3017 if (new_thread && GET_CODE (new_thread) == JUMP_INSN
3018 && (simplejump_p (new_thread)
3019 || GET_CODE (PATTERN (new_thread)) == RETURN))
3020 new_thread = follow_jumps (JUMP_LABEL (new_thread));
3022 if (new_thread == 0)
3023 label = find_end_label ();
3024 else if (GET_CODE (new_thread) == CODE_LABEL)
3027 label = get_label_before (new_thread);
3029 redirect_jump (insn, label);
3035 /* Make another attempt to find insns to place in delay slots.
3037 We previously looked for insns located in front of the delay insn
3038 and, for non-jump delay insns, located behind the delay insn.
3040 Here only try to schedule jump insns and try to move insns from either
3041 the target or the following insns into the delay slot. If annulling is
3042 supported, we will be likely to do this. Otherwise, we can do this only
3046 fill_eager_delay_slots (first)
3051 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3053 for (i = 0; i < num_unfilled_slots; i++)
3056 rtx target_label, insn_at_target, fallthrough_insn;
3059 int own_fallthrough;
3060 int prediction, slots_to_fill, slots_filled;
3062 insn = unfilled_slots_base[i];
3064 || INSN_DELETED_P (insn)
3065 || GET_CODE (insn) != JUMP_INSN
3066 || ! condjump_p (insn))
3069 slots_to_fill = num_delay_slots (insn);
3070 if (slots_to_fill == 0)
3074 target_label = JUMP_LABEL (insn);
3075 condition = get_branch_condition (insn, target_label);
3080 /* Get the next active fallthough and target insns and see if we own
3081 them. Then see whether the branch is likely true. We don't need
3082 to do a lot of this for unconditional branches. */
3084 insn_at_target = next_active_insn (target_label);
3085 own_target = own_thread_p (target_label, target_label, 0);
3087 if (condition == const_true_rtx)
3089 own_fallthrough = 0;
3090 fallthrough_insn = 0;
3095 fallthrough_insn = next_active_insn (insn);
3096 own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
3097 prediction = mostly_true_jump (insn, condition);
3100 /* If this insn is expected to branch, first try to get insns from our
3101 target, then our fallthrough insns. If it is not, expected to branch,
3102 try the other order. */
3107 = fill_slots_from_thread (insn, condition, insn_at_target,
3108 fallthrough_insn, prediction == 2, 1,
3109 own_target, own_fallthrough,
3110 slots_to_fill, &slots_filled);
3112 if (delay_list == 0 && own_fallthrough)
3114 /* Even though we didn't find anything for delay slots,
3115 we might have found a redundant insn which we deleted
3116 from the thread that was filled. So we have to recompute
3117 the next insn at the target. */
3118 target_label = JUMP_LABEL (insn);
3119 insn_at_target = next_active_insn (target_label);
3122 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3123 insn_at_target, 0, 0,
3124 own_fallthrough, own_target,
3125 slots_to_fill, &slots_filled);
3130 if (own_fallthrough)
3132 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3133 insn_at_target, 0, 0,
3134 own_fallthrough, own_target,
3135 slots_to_fill, &slots_filled);
3137 if (delay_list == 0)
3139 = fill_slots_from_thread (insn, condition, insn_at_target,
3140 next_active_insn (insn), 0, 1,
3141 own_target, own_fallthrough,
3142 slots_to_fill, &slots_filled);
3146 unfilled_slots_base[i]
3147 = emit_delay_sequence (insn, delay_list,
3148 slots_filled, slots_to_fill);
3150 if (slots_to_fill == slots_filled)
3151 unfilled_slots_base[i] = 0;
3153 note_delay_statistics (slots_filled, 1);
3157 /* Once we have tried two ways to fill a delay slot, make a pass over the
3158 code to try to improve the results and to do such things as more jump
3162 relax_delay_slots (first)
3165 register rtx insn, next, pat;
3166 register rtx trial, delay_insn, target_label;
3168 /* Look at every JUMP_INSN and see if we can improve it. */
3169 for (insn = first; insn; insn = next)
3173 next = next_active_insn (insn);
3175 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3176 the next insn, or jumps to a label that is not the last of a
3177 group of consecutive labels. */
3178 if (GET_CODE (insn) == JUMP_INSN
3179 && (target_label = JUMP_LABEL (insn)) != 0)
3181 target_label = follow_jumps (target_label);
3182 target_label = prev_label (next_active_insn (target_label));
3184 if (target_label == 0)
3185 target_label = find_end_label ();
3187 if (next_active_insn (target_label) == next)
3193 if (target_label != JUMP_LABEL (insn))
3194 redirect_jump (insn, target_label);
3196 /* See if this jump branches around a unconditional jump.
3197 If so, invert this jump and point it to the target of the
3199 if (next && GET_CODE (next) == JUMP_INSN
3200 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3201 && next_active_insn (target_label) == next_active_insn (next)
3202 && no_labels_between_p (insn, next))
3204 rtx label = JUMP_LABEL (next);
3206 /* Be careful how we do this to avoid deleting code or
3207 labels that are momentarily dead. See similar optimization
3210 We also need to ensure we properly handle the case when
3211 invert_jump fails. */
3213 ++LABEL_NUSES (target_label);
3215 ++LABEL_NUSES (label);
3217 if (invert_jump (insn, label))
3224 --LABEL_NUSES (label);
3226 if (--LABEL_NUSES (target_label) == 0)
3227 delete_insn (target_label);
3233 /* If this is an unconditional jump and the previous insn is a
3234 conditional jump, try reversing the condition of the previous
3235 insn and swapping our targets. The next pass might be able to
3238 Don't do this if we expect the conditional branch to be true, because
3239 we would then be making the more common case longer. */
3241 if (GET_CODE (insn) == JUMP_INSN
3242 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3243 && (other = prev_active_insn (insn)) != 0
3244 && condjump_p (other)
3245 && no_labels_between_p (other, insn)
3246 && ! mostly_true_jump (other,
3247 get_branch_condition (other,
3248 JUMP_LABEL (other))))
3250 rtx other_target = JUMP_LABEL (other);
3252 /* Increment the count of OTHER_TARGET, so it doesn't get deleted
3253 as we move the label. */
3255 ++LABEL_NUSES (other_target);
3257 if (invert_jump (other, target_label))
3258 redirect_jump (insn, other_target);
3261 --LABEL_NUSES (other_target);
3264 /* Now look only at cases where we have filled a delay slot. */
3265 if (GET_CODE (insn) != INSN
3266 || GET_CODE (PATTERN (insn)) != SEQUENCE)
3269 pat = PATTERN (insn);
3270 delay_insn = XVECEXP (pat, 0, 0);
3272 /* See if the first insn in the delay slot is redundant with some
3273 previous insn. Remove it from the delay slot if so; then set up
3274 to reprocess this insn. */
3275 if (redundant_insn_p (XVECEXP (pat, 0, 1), delay_insn, 0))
3277 delete_from_delay_slot (XVECEXP (pat, 0, 1));
3278 next = prev_active_insn (next);
3282 /* Now look only at the cases where we have a filled JUMP_INSN. */
3283 if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3284 || ! condjump_p (XVECEXP (PATTERN (insn), 0, 0)))
3287 target_label = JUMP_LABEL (delay_insn);
3291 /* If this jump goes to another unconditional jump, thread it, but
3292 don't convert a jump into a RETURN here. */
3293 trial = follow_jumps (target_label);
3294 trial = prev_label (next_active_insn (trial));
3295 if (trial == 0 && target_label != 0)
3296 trial = find_end_label ();
3298 if (trial != target_label)
3300 redirect_jump (delay_insn, trial);
3301 target_label = trial;
3304 /* If the first insn at TARGET_LABEL is redundant with a previous
3305 insn, redirect the jump to the following insn process again. */
3306 trial = next_active_insn (target_label);
3307 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3308 && redundant_insn_p (trial, insn, 0))
3310 trial = next_active_insn (trial);
3312 target_label = find_end_label ();
3314 target_label = get_label_before (trial);
3315 redirect_jump (delay_insn, target_label);
3320 /* Similarly, if it is an unconditional jump with one insn in its
3321 delay list and that insn is redundant, thread the jump. */
3322 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3323 && XVECLEN (PATTERN (trial), 0) == 2
3324 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3325 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3326 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3327 && redundant_insn_p (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3329 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3330 if (target_label == 0)
3331 target_label = find_end_label ();
3332 redirect_jump (delay_insn, target_label);
3338 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3339 && prev_active_insn (target_label) == insn
3341 /* If the last insn in the delay slot sets CC0 for some insn,
3342 various code assumes that it is in a delay slot. We could
3343 put it back where it belonged and delete the register notes,
3344 but it doesn't seem worthwhile in this uncommon case. */
3345 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3346 REG_CC_USER, NULL_RTX)
3352 /* All this insn does is execute its delay list and jump to the
3353 following insn. So delete the jump and just execute the delay
3356 We do this by deleting the INSN containing the SEQUENCE, then
3357 re-emitting the insns separately, and then deleting the jump.
3358 This allows the count of the jump target to be properly
3361 /* Clear the from target bit, since these insns are no longer
3363 for (i = 0; i < XVECLEN (pat, 0); i++)
3364 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3366 trial = PREV_INSN (insn);
3368 emit_insn_after (pat, trial);
3369 delete_scheduled_jump (delay_insn);
3373 /* See if this jump (with its delay slots) branches around another
3374 jump (without delay slots). If so, invert this jump and point
3375 it to the target of the second jump. We cannot do this for
3376 annulled jumps, though. Again, don't convert a jump to a RETURN
3378 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3379 && next && GET_CODE (next) == JUMP_INSN
3380 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3381 && next_active_insn (target_label) == next_active_insn (next)
3382 && no_labels_between_p (insn, next))
3384 rtx label = JUMP_LABEL (next);
3385 rtx old_label = JUMP_LABEL (delay_insn);
3388 label = find_end_label ();
3390 /* Be careful how we do this to avoid deleting code or labels
3391 that are momentarily dead. See similar optimization in jump.c */
3393 ++LABEL_NUSES (old_label);
3395 if (invert_jump (delay_insn, label))
3401 if (old_label && --LABEL_NUSES (old_label) == 0)
3402 delete_insn (old_label);
3406 /* If we own the thread opposite the way this insn branches, see if we
3407 can merge its delay slots with following insns. */
3408 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3409 && own_thread_p (NEXT_INSN (insn), 0, 1))
3410 try_merge_delay_insns (insn, next);
3411 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3412 && own_thread_p (target_label, target_label, 0))
3413 try_merge_delay_insns (insn, next_active_insn (target_label));
3415 /* If we get here, we haven't deleted INSN. But we may have deleted
3416 NEXT, so recompute it. */
3417 next = next_active_insn (insn);
3423 /* Look for filled jumps to the end of function label. We can try to convert
3424 them into RETURN insns if the insns in the delay slot are valid for the
3428 make_return_insns (first)
3431 rtx insn, jump_insn, pat;
3432 rtx real_return_label = end_of_function_label;
3435 /* See if there is a RETURN insn in the function other than the one we
3436 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3437 into a RETURN to jump to it. */
3438 for (insn = first; insn; insn = NEXT_INSN (insn))
3439 if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3441 real_return_label = get_label_before (insn);
3445 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3446 was equal to END_OF_FUNCTION_LABEL. */
3447 LABEL_NUSES (real_return_label)++;
3449 /* Clear the list of insns to fill so we can use it. */
3450 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3452 for (insn = first; insn; insn = NEXT_INSN (insn))
3454 /* Only look at filled JUMP_INSNs that go to the end of function
3456 if (GET_CODE (insn) != INSN
3457 || GET_CODE (PATTERN (insn)) != SEQUENCE
3458 || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3459 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3462 pat = PATTERN (insn);
3463 jump_insn = XVECEXP (pat, 0, 0);
3465 /* If we can't make the jump into a RETURN, redirect it to the best
3466 RETURN and go on to the next insn. */
3467 if (! redirect_jump (jump_insn, NULL_RTX))
3469 redirect_jump (jump_insn, real_return_label);
3473 /* See if this RETURN can accept the insns current in its delay slot.
3474 It can if it has more or an equal number of slots and the contents
3475 of each is valid. */
3477 slots = num_delay_slots (jump_insn);
3478 if (slots >= XVECLEN (pat, 0) - 1)
3480 for (i = 1; i < XVECLEN (pat, 0); i++)
3482 #ifdef ANNUL_IFFALSE_SLOTS
3483 (INSN_ANNULLED_BRANCH_P (jump_insn)
3484 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3485 ? eligible_for_annul_false (jump_insn, i - 1,
3486 XVECEXP (pat, 0, i)) :
3488 #ifdef ANNUL_IFTRUE_SLOTS
3489 (INSN_ANNULLED_BRANCH_P (jump_insn)
3490 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3491 ? eligible_for_annul_true (jump_insn, i - 1,
3492 XVECEXP (pat, 0, i)) :
3494 eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i))))
3500 if (i == XVECLEN (pat, 0))
3503 /* We have to do something with this insn. If it is an unconditional
3504 RETURN, delete the SEQUENCE and output the individual insns,
3505 followed by the RETURN. Then set things up so we try to find
3506 insns for its delay slots, if it needs some. */
3507 if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3509 rtx prev = PREV_INSN (insn);
3512 for (i = 1; i < XVECLEN (pat, 0); i++)
3513 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3515 insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3516 emit_barrier_after (insn);
3519 obstack_ptr_grow (&unfilled_slots_obstack, insn);
3522 /* It is probably more efficient to keep this with its current
3523 delay slot as a branch to a RETURN. */
3524 redirect_jump (jump_insn, real_return_label);
3527 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3528 new delay slots we have created. */
3529 if (--LABEL_NUSES (real_return_label) == 0)
3530 delete_insn (real_return_label);
3532 fill_simple_delay_slots (first, 1);
3533 fill_simple_delay_slots (first, 0);
3537 /* Try to find insns to place in delay slots. */
3540 dbr_schedule (first, file)
3547 int old_flag_no_peephole = flag_no_peephole;
3549 /* Execute `final' once in prescan mode to delete any insns that won't be
3550 used. Don't let final try to do any peephole optimization--it will
3551 ruin dataflow information for this pass. */
3553 flag_no_peephole = 1;
3554 final (first, 0, NO_DEBUG, 1, 1);
3555 flag_no_peephole = old_flag_no_peephole;
3558 /* Find the highest INSN_UID and allocate and initialize our map from
3559 INSN_UID's to position in code. */
3560 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3561 if (INSN_UID (insn) > max_uid)
3562 max_uid = INSN_UID (insn);
3564 uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
3565 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3566 uid_to_ruid[INSN_UID (insn)] = i;
3568 /* Initialize the list of insns that need filling. */
3569 if (unfilled_firstobj == 0)
3571 gcc_obstack_init (&unfilled_slots_obstack);
3572 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3575 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3579 INSN_ANNULLED_BRANCH_P (insn) = 0;
3580 INSN_FROM_TARGET_P (insn) = 0;
3582 /* Skip vector tables. We can't get attributes for them. */
3583 if (GET_CODE (insn) == JUMP_INSN
3584 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3585 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3588 if (num_delay_slots (insn) > 0)
3589 obstack_ptr_grow (&unfilled_slots_obstack, insn);
3591 /* Ensure all jumps go to the last of a set of consecutive labels. */
3592 if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn)
3593 && JUMP_LABEL (insn) != 0
3594 && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
3595 != JUMP_LABEL (insn)))
3596 redirect_jump (insn, target);
3599 /* Indicate what resources are required to be valid at the end of the current
3600 function. The condition code never is and memory always is. If the
3601 frame pointer is needed, it is and so is the stack pointer unless
3602 EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
3603 stack pointer is. Registers used to return the function value are
3604 needed. Registers holding global variables are needed. */
3606 end_of_function_needs.cc = 0;
3607 end_of_function_needs.memory = 1;
3608 CLEAR_HARD_REG_SET (end_of_function_needs.regs);
3610 if (frame_pointer_needed)
3612 SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
3613 #ifdef EXIT_IGNORE_STACK
3614 if (! EXIT_IGNORE_STACK)
3616 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3619 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3621 if (current_function_return_rtx != 0
3622 && GET_CODE (current_function_return_rtx) == REG)
3623 mark_referenced_resources (current_function_return_rtx,
3624 &end_of_function_needs, 0);
3626 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3628 SET_HARD_REG_BIT (end_of_function_needs.regs, i);
3630 /* Show we haven't computed an end-of-function label yet. */
3631 end_of_function_label = 0;
3633 /* Allocate and initialize the tables used by mark_target_live_regs. */
3635 = (struct target_info **) alloca ((TARGET_HASH_PRIME
3636 * sizeof (struct target_info *)));
3637 bzero (target_hash_table, TARGET_HASH_PRIME * sizeof (struct target_info *));
3639 bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
3640 bzero (bb_ticks, n_basic_blocks * sizeof (int));
3642 /* Initialize the statistics for this function. */
3643 bzero (num_insns_needing_delays, sizeof num_insns_needing_delays);
3644 bzero (num_filled_delays, sizeof num_filled_delays);
3646 /* Now do the delay slot filling. Try everything twice in case earlier
3647 changes make more slots fillable. */
3649 for (reorg_pass_number = 0;
3650 reorg_pass_number < MAX_REORG_PASSES;
3651 reorg_pass_number++)
3653 fill_simple_delay_slots (first, 1);
3654 fill_simple_delay_slots (first, 0);
3655 fill_eager_delay_slots (first);
3656 relax_delay_slots (first);
3659 /* Delete any USE insns made by update_block; subsequent passes don't need
3660 them or know how to deal with them. */
3661 for (insn = first; insn; insn = next)
3663 next = NEXT_INSN (insn);
3665 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3666 && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
3667 || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN
3668 || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN))
3669 next = delete_insn (insn);
3672 /* If we made an end of function label, indicate that it is now
3673 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3674 If it is now unused, delete it. */
3675 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3676 delete_insn (end_of_function_label);
3679 if (HAVE_return && end_of_function_label != 0)
3680 make_return_insns (first);
3683 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3685 /* It is not clear why the line below is needed, but it does seem to be. */
3686 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3688 /* Reposition the prologue and epilogue notes in case we moved the
3689 prologue/epilogue insns. */
3690 reposition_prologue_and_epilogue_notes (first);
3694 register int i, j, need_comma;
3696 for (reorg_pass_number = 0;
3697 reorg_pass_number < MAX_REORG_PASSES;
3698 reorg_pass_number++)
3700 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3701 for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3704 fprintf (file, ";; Reorg function #%d\n", i);
3706 fprintf (file, ";; %d insns needing delay slots\n;; ",
3707 num_insns_needing_delays[i][reorg_pass_number]);
3709 for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
3710 if (num_filled_delays[i][j][reorg_pass_number])
3713 fprintf (file, ", ");
3715 fprintf (file, "%d got %d delays",
3716 num_filled_delays[i][j][reorg_pass_number], j);
3718 fprintf (file, "\n");
3723 #endif /* DELAY_SLOTS */