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. */
23 #include "insn-attr.h"
27 /* Instruction reorganization pass.
29 This pass runs after register allocation and final jump
30 optimization. It should be the last pass to run before peephole.
31 It serves primarily to fill delay slots of insns, typically branch
32 and call insns. Other insns typically involve more complicated
33 interractions of data dependencies and resource constraints, and
34 are better handled by scheduling before register allocation (by the
35 function `schedule_insns').
37 The Branch Penalty is the number of extra cycles that are needed to
38 execute a branch insn. On an ideal machine, branches take a single
39 cycle, and the Branch Penalty is 0. Several RISC machines approach
40 branch delays differently:
42 The MIPS and AMD 29000 have a single branch delay slot. Most insns
43 (except other branches) can be used to fill this slot. When the
44 slot is filled, two insns execute in two cycles, reducing the
45 branch penalty to zero.
47 The Motorola 88000 conditionally exposes its branch delay slot,
48 so code is shorter when it is turned off, but will run faster
49 when useful insns are scheduled there.
51 The IBM ROMP has two forms of branch and call insns, both with and
52 without a delay slot. Much like the 88k, insns not using the delay
53 slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
55 The SPARC always has a branch delay slot, but its effects can be
56 annulled when the branch is not taken. This means that failing to
57 find other sources of insns, we can hoist an insn from the branch
58 target that would only be safe to execute knowing that the branch
61 Three techniques for filling delay slots have been implemented so far:
63 (1) `fill_simple_delay_slots' is the simplest, most efficient way
64 to fill delay slots. This pass first looks for insns which come
65 from before the branch and which are safe to execute after the
66 branch. Then it searches after the insn requiring delay slots or,
67 in the case of a branch, for insns that are after the point at
68 which the branch merges into the fallthrough code, if such a point
69 exists. When such insns are found, the branch penalty decreases
70 and no code expansion takes place.
72 (2) `fill_eager_delay_slots' is more complicated: it is used for
73 scheduling conditional jumps, or for scheduling jumps which cannot
74 be filled using (1). A machine need not have annulled jumps to use
75 this strategy, but it helps (by keeping more options open).
76 `fill_eager_delay_slots' tries to guess the direction the branch
77 will go; if it guesses right 100% of the time, it can reduce the
78 branch penalty as much as `fill_eager_delay_slots' does. If it
79 guesses wrong 100% of the time, it might as well schedule nops (or
80 on the m88k, unexpose the branch slot). When
81 `fill_eager_delay_slots' takes insns from the fall-through path of
82 the jump, usually there is no code expansion; when it takes insns
83 from the branch target, there is code expansion if it is not the
84 only way to reach that target.
86 (3) `relax_delay_slots' uses a set of rules to simplify code that
87 has been reorganized by (1) and (2). It finds cases where
88 conditional test can be eliminated, jumps can be threaded, extra
89 insns can be eliminated, etc. It is the job of (1) and (2) to do a
90 good job of scheduling locally; `relax_delay_slots' takes care of
91 making the various individual schedules work well together. It is
92 especially tuned to handle the control flow interactions of branch
93 insns. It does nothing for insns with delay slots that do not
96 On machines that use CC0, we are very conservative. We will not make
97 a copy of an insn involving CC0 since we want to maintain a 1-1
98 correspondence between the insn that sets and uses CC0. The insns are
99 allowed to be separated by placing an insn that sets CC0 (but not an insn
100 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
101 delay slot. In that case, we point each insn at the other with REG_CC_USER
102 and REG_CC_SETTER notes. Note that these restrictions affect very few
103 machines because most RISC machines with delay slots will not use CC0
104 (the RT is the only known exception at this point).
108 The Acorn Risc Machine can conditionally execute most insns, so
109 it is profitable to move single insns into a position to execute
110 based on the condition code of the previous insn.
112 The HP-PA can conditionally nullify insns, providing a similar
113 effect to the ARM, differing mostly in which insn is "in charge". */
118 #include "insn-config.h"
119 #include "conditions.h"
120 #include "hard-reg-set.h"
121 #include "basic-block.h"
123 #include "insn-flags.h"
129 #define obstack_chunk_alloc xmalloc
130 #define obstack_chunk_free free
132 extern int xmalloc ();
135 #ifndef ANNUL_IFTRUE_SLOTS
136 #define eligible_for_annul_true(INSN, SLOTS, TRIAL) 0
138 #ifndef ANNUL_IFFALSE_SLOTS
139 #define eligible_for_annul_false(INSN, SLOTS, TRIAL) 0
142 /* Insns which have delay slots that have not yet been filled. */
144 static struct obstack unfilled_slots_obstack;
145 static rtx *unfilled_firstobj;
147 /* Define macros to refer to the first and last slot containing unfilled
148 insns. These are used because the list may move and its address
149 should be recomputed at each use. */
151 #define unfilled_slots_base \
152 ((rtx *) obstack_base (&unfilled_slots_obstack))
154 #define unfilled_slots_next \
155 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
157 /* This structure is used to indicate which hardware resources are set or
158 needed by insns so far. */
162 char memory; /* Insn sets or needs a memory location. */
163 char volatil; /* Insn sets or needs a volatile memory loc. */
164 char cc; /* Insn sets or needs the condition codes. */
165 HARD_REG_SET regs; /* Which registers are set or needed. */
168 /* Macro to clear all resources. */
169 #define CLEAR_RESOURCE(RES) \
170 do { (RES)->memory = (RES)->volatil = (RES)->cc = 0; \
171 CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
173 /* Indicates what resources are required at function end. */
174 static struct resources end_of_function_needs;
176 /* Points to the label before the end of the function. */
177 static rtx end_of_function_label;
179 /* This structure is used to record livness information at the targets or
180 fallthrough insns of branches. We will most likely need the information
181 at targets again, so save them in a hash table rather than recomputing them
186 int uid; /* INSN_UID of target. */
187 struct target_info *next; /* Next info for same hash bucket. */
188 HARD_REG_SET live_regs; /* Registers live at target. */
189 int block; /* Basic block number containing target. */
190 int bb_tick; /* Generation count of basic block info. */
193 #define TARGET_HASH_PRIME 257
195 /* Define the hash table itself. */
196 static struct target_info **target_hash_table;
198 /* For each basic block, we maintain a generation number of its basic
199 block info, which is updated each time we move an insn from the
200 target of a jump. This is the generation number indexed by block
203 static int *bb_ticks;
205 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
206 not always monotonically increase. */
207 static int *uid_to_ruid;
209 /* Highest valid index in `uid_to_ruid'. */
212 /* Forward references: */
214 static int redundant_insn_p ();
215 static void update_block ();
217 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
218 which resources are references by the insn. If INCLUDE_CALLED_ROUTINE
219 is TRUE, resources used by the called routine will be included for
223 mark_referenced_resources (x, res, include_called_routine)
225 register struct resources *res;
226 register int include_called_routine;
228 register enum rtx_code code = GET_CODE (x);
230 register char *format_ptr;
232 /* Handle leaf items for which we set resource flags. Also, special-case
233 CALL, SET and CLOBBER operators. */
245 if (GET_CODE (SUBREG_REG (x)) != REG)
246 mark_referenced_resources (SUBREG_REG (x), res, 0);
249 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
250 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
251 for (i = regno; i < last_regno; i++)
252 SET_HARD_REG_BIT (res->regs, i);
257 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
258 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
262 /* If this memory shouldn't change, it really isn't referencing
264 if (! RTX_UNCHANGING_P (x))
266 res->volatil = MEM_VOLATILE_P (x);
268 /* Mark registers used to access memory. */
269 mark_referenced_resources (XEXP (x, 0), res, 0);
276 case UNSPEC_VOLATILE:
278 /* Traditional asm's are always volatile. */
283 res->volatil = MEM_VOLATILE_P (x);
285 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
286 We can not just fall through here since then we would be confused
287 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
288 traditional asms unlike their normal usage. */
290 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
291 mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
295 /* The first operand will be a (MEM (xxx)) but doesn't really reference
296 memory. The second operand may be referenced, though. */
297 mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
298 mark_referenced_resources (XEXP (x, 1), res, 0);
302 /* Usually, the first operand of SET is set, not referenced. But
303 registers used to access memory are referenced. SET_DEST is
304 also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
306 mark_referenced_resources (SET_SRC (x), res, 0);
309 if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
310 mark_referenced_resources (x, res, 0);
311 else if (GET_CODE (x) == SUBREG)
313 if (GET_CODE (x) == MEM)
314 mark_referenced_resources (XEXP (x, 0), res, 0);
321 if (include_called_routine)
323 /* A CALL references memory, the frame pointer if it exists, the
324 stack pointer, any global registers and any registers given in
325 USE insns immediately in front of the CALL.
327 However, we may have moved some of the parameter loading insns
328 into the delay slot of this CALL. If so, the USE's for them
329 don't count and should be skipped. */
330 rtx insn = PREV_INSN (x);
335 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
336 if (NEXT_INSN (insn) != x)
338 sequence = PATTERN (NEXT_INSN (insn));
339 seq_size = XVECLEN (sequence, 0);
340 if (GET_CODE (sequence) != SEQUENCE)
345 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
346 if (frame_pointer_needed)
347 SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
349 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
351 SET_HARD_REG_BIT (res->regs, i);
353 /* Skip any labels between the CALL_INSN and possible USE insns. */
354 while (GET_CODE (insn) == CODE_LABEL)
355 insn = PREV_INSN (insn);
357 for ( ; (insn && GET_CODE (insn) == INSN
358 && GET_CODE (PATTERN (insn)) == USE);
359 insn = PREV_INSN (insn))
361 for (i = 1; i < seq_size; i++)
363 rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
364 if (GET_CODE (slot_pat) == SET
365 && rtx_equal_p (SET_DEST (slot_pat),
366 XEXP (PATTERN (insn), 0)))
370 mark_referenced_resources (XEXP (PATTERN (insn), 0), res, 0);
374 /* ... fall through to other INSN procesing ... */
378 /* No special processing, just speed up. */
379 mark_referenced_resources (PATTERN (x), res, include_called_routine);
383 /* Process each sub-expression and flag what it needs. */
384 format_ptr = GET_RTX_FORMAT (code);
385 for (i = 0; i < GET_RTX_LENGTH (code); i++)
386 switch (*format_ptr++)
389 mark_referenced_resources (XEXP (x, i), res, include_called_routine);
393 for (j = 0; j < XVECLEN (x, i); j++)
394 mark_referenced_resources (XVECEXP (x, i, j), res,
395 include_called_routine);
400 /* Given an insn, INSN, and a pointer to a `struct resource', RES, indicate
401 which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
402 is TRUE, also mark resources potentially set by the called routine.
404 We never mark the insn as modifying the condition code unless it explicitly
405 SETs CC0 even though this is not totally correct. The reason for this is
406 that we require a SET of CC0 to immediately preceed the reference to CC0.
407 So if some other insn sets CC0 as a side-effect, we know it cannot affect
408 our computation and thus may be placed in a delay slot. */
411 mark_set_resources (insn, res, include_called_routine)
413 register struct resources *res;
414 int include_called_routine;
418 switch (GET_CODE (insn))
423 /* These don't set any resources. */
427 /* Called routine modifies the condition code, memory, any registers
428 that aren't saved across calls, global registers and anything
429 explicitly CLOBBERed immediately after the CALL_INSN. */
431 if (include_called_routine)
433 rtx next = NEXT_INSN (insn);
435 res->cc = res->memory = 1;
436 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
437 if (call_used_regs[i] || global_regs[i])
438 SET_HARD_REG_BIT (res->regs, i);
440 /* Skip any possible labels between the CALL_INSN and CLOBBERs. */
441 while (GET_CODE (next) == CODE_LABEL)
442 next = NEXT_INSN (next);
444 for (; (next && GET_CODE (next) == INSN
445 && GET_CODE (PATTERN (next)) == CLOBBER);
446 next = NEXT_INSN (next))
447 mark_referenced_resources (XEXP (PATTERN (next), 0), res, 0);
450 /* ... and also what it's RTL says it modifies, if anything. */
455 register rtx body = PATTERN (insn);
458 /* An insn consisting of just a CLOBBER (or USE) is
459 just for flow and doesn't actually do anything, so we don't check
462 If the source of a SET is a CALL, this is actually done by
463 the called routine. So only include it if we are to include the
464 effects of the calling routine. */
466 if (GET_CODE (body) == SET
467 && (include_called_routine || GET_CODE (SET_SRC (body)) != CALL))
468 mark_referenced_resources (SET_DEST (body), res, 0);
469 else if (GET_CODE (body) == PARALLEL)
471 for (i = 0; i < XVECLEN (body, 0); i++)
472 if ((GET_CODE (XVECEXP (body, 0, i)) == SET
473 && (include_called_routine
474 || GET_CODE (SET_SRC (XVECEXP (body, 0, i))) != CALL))
475 || GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
476 mark_referenced_resources (SET_DEST (XVECEXP (body, 0, i)),
479 else if (GET_CODE (body) == SEQUENCE)
480 for (i = 0; i < XVECLEN (body, 0); i++)
481 if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (body, 0, 0))
482 && INSN_FROM_TARGET_P (XVECEXP (body, 0, i))))
483 mark_set_resources (XVECEXP (body, 0, i), res,
484 include_called_routine);
487 /* If any register are incremented or decremented in an address,
488 they are set here. */
489 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
490 if (REG_NOTE_KIND (note) == REG_INC)
491 mark_referenced_resources (XEXP (note, 0), res, 0);
495 /* An insn that has a PRE_DEC on SP will not have a REG_INC note.
496 Until we fix this correctly, consider all insns as modifying
497 SP on such machines. So far, we don't have delay slot scheduling
498 on any machines with PUSH_ROUNDING. */
499 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
509 /* Return TRUE if this insn should stop the search for insn to fill delay
510 slots. LABELS_P indicates that labels should terminate the search.
511 In all cases, jumps terminate the search. */
514 stop_search_p (insn, labels_p)
521 switch (GET_CODE (insn))
535 /* OK unless it contains a delay slot or is an `asm' insn of some type.
536 We don't know anything about these. */
537 return (GET_CODE (PATTERN (insn)) == SEQUENCE
538 || GET_CODE (PATTERN (insn)) == ASM_INPUT
539 || asm_noperands (PATTERN (insn)) >= 0);
546 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
547 resource set contains a volatile memory reference. Otherwise, return FALSE. */
550 resource_conflicts_p (res1, res2)
551 struct resources *res1, *res2;
553 if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
554 || res1->volatil || res2->volatil)
558 return (res1->regs & res2->regs) != HARD_CONST (0);
563 for (i = 0; i < HARD_REG_SET_LONGS; i++)
564 if ((res1->regs[i] & res2->regs[i]) != 0)
571 /* Return TRUE if any resource marked in RES, a `struct resources', is
572 referenced by INSN. If INCLUDE_CALLED_ROUTINE is set, return if the called
573 routine is using those resources.
575 We compute this by computing all the resources referenced by INSN and
576 seeing if this conflicts with RES. It might be faster to directly check
577 ourselves, and this is the way it used to work, but it means duplicating
578 a large block of complex code. */
581 insn_references_resource_p (insn, res, include_called_routine)
583 register struct resources *res;
584 int include_called_routine;
586 struct resources insn_res;
588 CLEAR_RESOURCE (&insn_res);
589 mark_referenced_resources (insn, &insn_res, include_called_routine);
590 return resource_conflicts_p (&insn_res, res);
593 /* Return TRUE if INSN modifies resources that are marked in RES.
594 INCLUDE_CALLED_ROUTINE is set if the actions of that routine should be
595 included. CC0 is only modified if it is explicitly set; see comments
596 in front of mark_set_resources for details. */
599 insn_sets_resource_p (insn, res, include_called_routine)
601 register struct resources *res;
602 int include_called_routine;
604 struct resources insn_sets;
606 CLEAR_RESOURCE (&insn_sets);
607 mark_set_resources (insn, &insn_sets, include_called_routine);
608 return resource_conflicts_p (&insn_sets, res);
611 /* Find a label at the end of the function or before a RETURN. If there is
619 /* If we found one previously, return it. */
620 if (end_of_function_label)
621 return end_of_function_label;
623 /* Otherwise, see if there is a label at the end of the function. If there
624 is, it must be that RETURN insns aren't needed, so that is our return
625 label and we don't have to do anything else. */
627 insn = get_last_insn ();
628 while (GET_CODE (insn) == NOTE
629 || (GET_CODE (insn) == INSN
630 && (GET_CODE (PATTERN (insn)) == USE
631 || GET_CODE (PATTERN (insn)) == CLOBBER)))
632 insn = PREV_INSN (insn);
634 if (GET_CODE (insn) == CODE_LABEL)
635 end_of_function_label = insn;
638 /* Otherwise, make a new label and emit a RETURN and BARRIER,
640 end_of_function_label = gen_label_rtx ();
641 LABEL_NUSES (end_of_function_label) = 0;
642 emit_label (end_of_function_label);
646 emit_jump_insn (gen_return ());
652 /* Show one additional use for this label so it won't go away until
654 ++LABEL_NUSES (end_of_function_label);
656 return end_of_function_label;
659 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
660 the pattern of INSN with the SEQUENCE.
662 Chain the insns so that NEXT_INSN of each insn in the sequence points to
663 the next and NEXT_INSN of the last insn in the sequence points to
664 the first insn after the sequence. Similarly for PREV_INSN. This makes
665 it easier to scan all insns.
667 Returns the SEQUENCE that replaces INSN. */
670 emit_delay_sequence (insn, list, length, avail)
680 /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
681 rtvec seqv = rtvec_alloc (length + 1);
682 rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
683 rtx seq_insn = make_insn_raw (seq);
684 rtx first = get_insns ();
685 rtx last = get_last_insn ();
687 /* Make a copy of the insn having delay slots. */
688 rtx delay_insn = copy_rtx (insn);
690 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
691 confuse further processing. Update LAST in case it was the last insn.
692 We will put the BARRIER back in later. */
693 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
695 delete_insn (NEXT_INSN (insn));
696 last = get_last_insn ();
700 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
701 NEXT_INSN (seq_insn) = NEXT_INSN (insn);
702 PREV_INSN (seq_insn) = PREV_INSN (insn);
705 set_new_first_and_last_insn (first, seq_insn);
707 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
710 set_new_first_and_last_insn (seq_insn, last);
712 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
714 /* Build our SEQUENCE and rebuild the insn chain. */
715 XVECEXP (seq, 0, 0) = delay_insn;
716 INSN_DELETED_P (delay_insn) = 0;
717 PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
719 for (li = list; li; li = XEXP (li, 1), i++)
721 rtx tem = XEXP (li, 0);
724 /* Show that this copy of the insn isn't deleted. */
725 INSN_DELETED_P (tem) = 0;
727 XVECEXP (seq, 0, i) = tem;
728 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
729 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
731 /* Remove any REG_DEAD notes because we can't rely on them now
732 that the insn has been moved. */
733 for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
734 if (REG_NOTE_KIND (note) == REG_DEAD)
735 XEXP (note, 0) = const0_rtx;
738 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
740 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
741 last insn in that SEQUENCE to point to us. Similarly for the first
742 insn in the following insn if it is a SEQUENCE. */
744 if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
745 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
746 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
747 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
750 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
751 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
752 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
754 /* If there used to be a BARRIER, put it back. */
756 emit_barrier_after (seq_insn);
764 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
765 be in the order in which the insns are to be executed. */
768 add_to_delay_list (insn, delay_list)
772 /* If we have an empty list, just make a new list element. */
774 return gen_rtx (INSN_LIST, VOIDmode, insn, 0);
776 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
778 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
784 /* INSN uses CC0 and is being moved into a delay slot. Set up REG_CC_SETTER
785 and REG_CC_USER notes so we can find it. */
788 link_cc0_insns (insn)
791 rtx user = next_nonnote_insn (insn);
793 if (GET_CODE (user) == INSN && GET_CODE (PATTERN (user)) == SEQUENCE)
794 user = XVECEXP (PATTERN (user), 0, 0);
796 REG_NOTES (user) = gen_rtx (INSN_LIST, REG_CC_SETTER, insn,
798 REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_CC_USER, user, REG_NOTES (insn));
802 /* Delete INSN from the the delay slot of the insn that it is in. This may
803 produce an insn without anything in its delay slots. */
806 delete_from_delay_slot (insn)
809 rtx trial, seq_insn, seq, prev;
813 /* We first must find the insn containing the SEQUENCE with INSN in its
814 delay slot. Do this by finding an insn, TRIAL, where
815 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
818 PREV_INSN (NEXT_INSN (trial)) == trial;
819 trial = NEXT_INSN (trial))
822 seq_insn = PREV_INSN (NEXT_INSN (trial));
823 seq = PATTERN (seq_insn);
825 /* Create a delay list consisting of all the insns other than the one
826 we are deleting (unless we were the only one). */
827 if (XVECLEN (seq, 0) > 2)
828 for (i = 1; i < XVECLEN (seq, 0); i++)
829 if (XVECEXP (seq, 0, i) != insn)
830 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
832 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
833 list, and rebuild the delay list if non-empty. */
834 prev = PREV_INSN (seq_insn);
835 trial = XVECEXP (seq, 0, 0);
836 delete_insn (seq_insn);
837 add_insn_after (trial, prev);
839 if (GET_CODE (trial) == JUMP_INSN
840 && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
841 emit_barrier_after (trial);
843 /* If there are any delay insns, remit them. Otherwise clear the
846 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2, 0);
848 INSN_ANNULLED_BRANCH_P (trial) = 0;
850 INSN_FROM_TARGET_P (insn) = 0;
852 /* Show we need to fill this insn again. */
853 obstack_ptr_grow (&unfilled_slots_obstack, trial);
856 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
857 the insn that sets CC0 for it and delete it too. */
860 delete_scheduled_jump (insn)
863 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
864 delete the insn that sets the condition code, but it is hard to find it.
865 Since this case is rare anyway, don't bother trying; there would likely
866 be other insns that became dead anyway, which we wouldn't know to
870 if (reg_mentioned_p (cc0_rtx, insn))
872 rtx note = find_reg_note (insn, REG_CC_SETTER, 0);
874 /* If a reg-note was found, it points to an insn to set CC0. This
875 insn is in the delay list of some other insn. So delete it from
876 the delay list it was in. */
879 if (! FIND_REG_INC_NOTE (XEXP (note, 0), 0)
880 && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
881 delete_from_delay_slot (XEXP (note, 0));
885 /* The insn setting CC0 is our previous insn, but it may be in
886 a delay slot. It will be the last insn in the delay slot, if
888 rtx trial = previous_insn (insn);
889 if (GET_CODE (trial) == NOTE)
890 trial = prev_nonnote_insn (trial);
891 if (sets_cc0_p (PATTERN (trial)) != 1
892 || FIND_REG_INC_NOTE (trial, 0))
894 if (PREV_INSN (NEXT_INSN (trial)) == trial)
897 delete_from_delay_slot (trial);
905 /* Counters for delay-slot filling. */
907 #define NUM_REORG_FUNCTIONS 2
908 #define MAX_DELAY_HISTOGRAM 3
909 #define MAX_REORG_PASSES 2
911 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
913 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
915 static int reorg_pass_number;
918 note_delay_statistics (slots_filled, index)
919 int slots_filled, index;
921 num_insns_needing_delays[index][reorg_pass_number]++;
922 if (slots_filled > MAX_DELAY_HISTOGRAM)
923 slots_filled = MAX_DELAY_HISTOGRAM;
924 num_filled_delays[index][slots_filled][reorg_pass_number]++;
927 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
929 /* Optimize the following cases:
931 1. When a conditional branch skips over only one instruction,
932 use an annulling branch and put that insn in the delay slot.
933 Use either a branch that annulls when the condition if true or
934 invert the test with a branch that annulls when the condition is
935 false. This saves insns, since otherwise we must copy an insn
938 (orig) (skip) (otherwise)
939 Bcc.n L1 Bcc',a L1 Bcc,a L1'
946 2. When a conditional branch skips over only one instruction,
947 and after that, it unconditionally branches somewhere else,
948 perform the similar optimization. This saves executing the
949 second branch in the case where the inverted condition is true.
958 This should be expanded to skip over N insns, where N is the number
959 of delay slots required. */
965 register rtx trial = next_nonnote_insn (insn);
966 rtx next_trial = next_active_insn (trial);
971 || GET_CODE (trial) != INSN
972 || GET_CODE (PATTERN (trial)) == SEQUENCE
973 || recog_memoized (trial) < 0
974 || (! eligible_for_annul_false (insn, 0, trial)
975 && ! eligible_for_annul_true (insn, 0, trial)))
978 /* There are two cases where we are just executing one insn (we assume
979 here that a branch requires only one insn; this should be generalized
980 at some point): Where the branch goes around a single insn or where
981 we have one insn followed by a branch to the same label we branch to.
982 In both of these cases, inverting the jump and annulling the delay
983 slot give the same effect in fewer insns. */
984 if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
986 && GET_CODE (next_trial) == JUMP_INSN
987 && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
988 && (simplejump_p (next_trial)
989 || GET_CODE (PATTERN (next_trial)) == RETURN)))
991 if (eligible_for_annul_false (insn, 0, trial))
993 if (invert_jump (insn, JUMP_LABEL (insn)))
994 INSN_FROM_TARGET_P (trial) = 1;
995 else if (! eligible_for_annul_true (insn, 0, trial))
999 delay_list = add_to_delay_list (trial, 0);
1000 next_trial = next_active_insn (trial);
1001 update_block (trial, trial);
1002 delete_insn (trial);
1004 /* Also, if we are targeting an unconditional
1005 branch, thread our jump to the target of that branch. Don't
1006 change this into a RETURN here, because it may not accept what
1007 we have in the delay slot. We'll fix this up later. */
1008 if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1009 && (simplejump_p (next_trial)
1010 || GET_CODE (PATTERN (next_trial)) == RETURN))
1012 target_label = JUMP_LABEL (next_trial);
1013 if (target_label == 0)
1014 target_label = find_end_label ();
1015 redirect_jump (insn, target_label);
1018 INSN_ANNULLED_BRANCH_P (insn) = 1;
1025 /* Return truth value of the statement that this branch
1026 is mostly taken. If we think that the branch is extremely likely
1027 to be taken, we return 2. If the branch is slightly more likely to be
1028 taken, return 1. Otherwise, return 0.
1030 CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */
1033 mostly_true_jump (jump_insn, condition)
1034 rtx jump_insn, condition;
1036 rtx target_label = JUMP_LABEL (jump_insn);
1039 /* If this is a conditional return insn, assume it won't return. */
1040 if (target_label == 0)
1043 /* If TARGET_LABEL has no jumps between it and the end of the function,
1044 this is essentially a conditional return, so predict it as false. */
1045 for (insn = NEXT_INSN (target_label);
1046 insn && GET_CODE (insn) != JUMP_INSN;
1047 insn = NEXT_INSN (insn))
1053 /* If this is the test of a loop, it is very likely true. We scan backwards
1054 from the target label. If we find a NOTE_INSN_LOOP_BEG before the next
1055 real insn, we assume the branch is to the top of the loop. */
1056 for (insn = PREV_INSN (target_label);
1057 insn && GET_CODE (insn) == NOTE;
1058 insn = PREV_INSN (insn))
1059 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1062 /* If we couldn't figure out what this jump was, assume it won't be
1063 taken. This should be rare. */
1067 /* EQ tests are usually false and NE tests are usually true. Also,
1068 most quantities are positive, so we can make the appropriate guesses
1069 about signed comparisons against zero. */
1070 switch (GET_CODE (condition))
1073 /* Unconditional branch. */
1081 if (XEXP (condition, 1) == const0_rtx)
1086 if (XEXP (condition, 1) == const0_rtx)
1091 /* Predict backward branches usually take, forward branches usually not. If
1092 we don't know whether this is forward or backward, assume the branch
1093 will be taken, since most are. */
1094 return (INSN_UID (jump_insn) > max_uid || INSN_UID (target_label) > max_uid
1095 || (uid_to_ruid[INSN_UID (jump_insn)]
1096 > uid_to_ruid[INSN_UID (target_label)]));;
1099 /* Return the condition under which INSN will branch to TARGET. If TARGET
1100 is zero, return the condition under which INSN will return. If INSN is
1101 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1102 type of jump, or it doesn't go to TARGET, return 0. */
1105 get_branch_condition (insn, target)
1109 rtx pat = PATTERN (insn);
1112 if (GET_CODE (pat) == RETURN)
1113 return target == 0 ? const_true_rtx : 0;
1115 else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1118 src = SET_SRC (pat);
1119 if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1120 return const_true_rtx;
1122 else if (GET_CODE (src) == IF_THEN_ELSE
1123 && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1124 || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1125 && XEXP (XEXP (src, 1), 0) == target))
1126 && XEXP (src, 2) == pc_rtx)
1127 return XEXP (src, 0);
1129 else if (GET_CODE (src) == IF_THEN_ELSE
1130 && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1131 || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1132 && XEXP (XEXP (src, 2), 0) == target))
1133 && XEXP (src, 1) == pc_rtx)
1134 return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
1135 GET_MODE (XEXP (src, 0)),
1136 XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1139 /* Return non-zero if CONDITION is more strict than the condition of
1140 INSN, i.e., if INSN will always branch if CONDITION is true. */
1143 condition_dominates_p (condition, insn)
1147 rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1148 enum rtx_code code = GET_CODE (condition);
1149 enum rtx_code other_code;
1151 if (rtx_equal_p (condition, other_condition)
1152 || other_condition == const_true_rtx)
1155 else if (condition == const_true_rtx || other_condition == 0)
1158 other_code = GET_CODE (other_condition);
1159 if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1160 || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1161 || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1164 return comparison_dominates_p (code, other_code);
1167 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1168 the condition tested by INSN is CONDITION and the resources shown in
1169 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1170 from SEQ's delay list, in addition to whatever insns it may execute
1171 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1172 needed while searching for delay slot insns. Return the concatenated
1173 delay list if possible, otherwise, return 0.
1175 SLOTS_TO_FILL is the total number of slots required by INSN, and
1176 PSLOTS_FILLED points to the number filled so far (also the number of
1177 insns in DELAY_LIST). It is updated with the number that have been
1178 filled from the SEQUENCE, if any.
1180 PANNUL_P points to a non-zero value if we already know that we need
1181 to annul INSN. If this routine determines that annulling is needed,
1182 it may set that value non-zero.
1184 PNEW_THREAD points to a location that is to receive the place at which
1185 execution should continue. */
1188 steal_delay_list_from_target (insn, condition, seq, delay_list,
1189 sets, needed, other_needed,
1190 slots_to_fill, pslots_filled, pannul_p,
1192 rtx insn, condition;
1195 struct resources *sets, *needed, *other_needed;
1202 int slots_remaining = slots_to_fill - *pslots_filled;
1203 int total_slots_filled = *pslots_filled;
1204 rtx new_delay_list = 0;
1205 int must_annul = *pannul_p;
1208 /* We can't do anything if there are more delay slots in SEQ than we
1209 can handle, or if we don't know that it will be a taken branch.
1211 We know that it will be a taken branch if it is either an unconditional
1212 branch or a conditional branch with a stricter branch condition. */
1214 if (XVECLEN (seq, 0) - 1 > slots_remaining
1215 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0)))
1218 for (i = 1; i < XVECLEN (seq, 0); i++)
1220 rtx trial = XVECEXP (seq, 0, i);
1222 if (insn_references_resource_p (trial, sets, 0)
1223 || insn_sets_resource_p (trial, needed, 0)
1224 || insn_sets_resource_p (trial, sets, 0)
1226 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1228 || find_reg_note (trial, REG_CC_USER, 0)
1230 /* If TRIAL is from the fallthrough code of an annulled branch insn
1231 in SEQ, we cannot use it. */
1232 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1233 && ! INSN_FROM_TARGET_P (trial)))
1236 /* If this insn was already done (usually in a previous delay slot),
1237 pretend we put it in our delay slot. */
1238 if (redundant_insn_p (trial, insn, new_delay_list))
1242 && ((condition == const_true_rtx
1243 || (! insn_sets_resource_p (trial, other_needed, 0)
1244 && ! may_trap_p (PATTERN (trial)))))
1245 ? eligible_for_delay (insn, total_slots_filled, trial)
1247 eligible_for_annul_false (insn, total_slots_filled, trial)))
1249 temp = copy_rtx (trial);
1250 INSN_FROM_TARGET_P (temp) = 1;
1251 new_delay_list = add_to_delay_list (temp, new_delay_list);
1252 total_slots_filled++;
1254 if (--slots_remaining == 0)
1261 /* Show the place to which we will be branching. */
1262 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1264 /* Add any new insns to the delay list and update the count of the
1265 number of slots filled. */
1266 *pslots_filled = total_slots_filled;
1267 *pannul_p = must_annul;
1269 if (delay_list == 0)
1270 return new_delay_list;
1272 for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1273 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1278 /* Similar to steal_delay_list_from_target except that SEQ is on the
1279 fallthrough path of INSN. Here we only do something if the delay insn
1280 of SEQ is an unconditional branch. In that case we steal its delay slot
1281 for INSN since unconditional branches are much easier to fill. */
1284 steal_delay_list_from_fallthrough (insn, condition, seq,
1285 delay_list, sets, needed, other_needed,
1286 slots_to_fill, pslots_filled, pannul_p)
1287 rtx insn, condition;
1290 struct resources *sets, *needed, *other_needed;
1297 /* We can't do anything if SEQ's delay insn isn't an
1298 unconditional branch. */
1300 if (! simplejump_p (XVECEXP (seq, 0, 0))
1301 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1304 for (i = 1; i < XVECLEN (seq, 0); i++)
1306 rtx trial = XVECEXP (seq, 0, i);
1308 /* If TRIAL sets CC0, stealing it will move it too far from the use
1310 if (insn_references_resource_p (trial, sets, 0)
1311 || insn_sets_resource_p (trial, needed, 0)
1312 || insn_sets_resource_p (trial, sets, 0)
1314 || sets_cc0_p (PATTERN (trial))
1320 /* If this insn was already done, we don't need it. */
1321 if (redundant_insn_p (trial, insn, delay_list))
1323 delete_from_delay_slot (trial);
1328 && ((condition == const_true_rtx
1329 || (! insn_sets_resource_p (trial, other_needed, 0)
1330 && ! may_trap_p (PATTERN (trial)))))
1331 ? eligible_for_delay (insn, *pslots_filled, trial)
1333 eligible_for_annul_true (insn, *pslots_filled, trial)))
1335 delete_from_delay_slot (trial);
1336 delay_list = add_to_delay_list (trial, delay_list);
1338 if (++(*pslots_filled) == slots_to_fill)
1348 /* Try merging insns starting at THREAD which match exactly the insns in
1351 If all insns were matched and the insn was previously annulling, the
1352 annul bit will be cleared.
1354 For each insn that is merged, if the branch is or will be non-annulling,
1355 we delete the merged insn. */
1358 try_merge_delay_insns (insn, thread)
1361 rtx trial, next_trial;
1362 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1363 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1364 int slot_number = 1;
1365 int num_slots = XVECLEN (PATTERN (insn), 0);
1366 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1367 struct resources set, needed;
1368 rtx merged_insns = 0;
1371 CLEAR_RESOURCE (&needed);
1372 CLEAR_RESOURCE (&set);
1374 /* If this is not an annulling branch, take into account anything needed in
1375 NEXT_TO_MATCH. This prevents two increments from being incorrectly
1376 folded into one. If we are annulling, this would be the correct
1377 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1378 will essentially disable this optimization. This method is somewhat of
1379 a kludge, but I don't see a better way.) */
1381 mark_referenced_resources (next_to_match, &needed, 1);
1383 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1385 rtx pat = PATTERN (trial);
1387 next_trial = next_nonnote_insn (trial);
1389 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1390 if (GET_CODE (trial) == INSN
1391 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1394 if (GET_CODE (next_to_match) == GET_CODE (trial)
1396 /* We can't share an insn that sets cc0. */
1397 && ! sets_cc0_p (pat)
1399 && ! insn_references_resource_p (trial, &set, 1)
1400 && ! insn_sets_resource_p (trial, &set, 1)
1401 && ! insn_sets_resource_p (trial, &needed, 1)
1402 && (trial = try_split (pat, trial, 0)) != 0
1403 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1404 /* Have to test this condition if annul condition is different
1405 from (and less restrictive than) non-annulling one. */
1406 && eligible_for_delay (delay_insn, slot_number - 1, trial))
1408 next_trial = next_nonnote_insn (trial);
1412 update_block (trial, thread);
1413 delete_insn (trial);
1414 INSN_FROM_TARGET_P (next_to_match) = 0;
1417 merged_insns = gen_rtx (INSN_LIST, VOIDmode, trial, merged_insns);
1419 if (++slot_number == num_slots)
1422 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1424 mark_referenced_resources (next_to_match, &needed, 1);
1427 mark_set_resources (trial, &set, 1);
1428 mark_referenced_resources (trial, &needed, 1);
1431 /* See if we stopped on a filled insn. If we did, try to see if its
1432 delay slots match. */
1433 if (slot_number != num_slots
1434 && trial && GET_CODE (trial) == INSN
1435 && GET_CODE (PATTERN (trial)) == SEQUENCE
1436 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1438 rtx pat = PATTERN (trial);
1440 for (i = 1; i < XVECLEN (pat, 0); i++)
1442 rtx dtrial = XVECEXP (pat, 0, i);
1444 if (! insn_references_resource_p (dtrial, &set, 1)
1445 && ! insn_sets_resource_p (dtrial, &set, 1)
1446 && ! insn_sets_resource_p (dtrial, &needed, 1)
1448 && ! sets_cc0_p (PATTERN (dtrial))
1450 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1451 && eligible_for_delay (delay_insn, slot_number - 1, dtrial))
1455 update_block (dtrial, thread);
1456 delete_from_delay_slot (dtrial);
1457 INSN_FROM_TARGET_P (next_to_match) = 0;
1460 merged_insns = gen_rtx (INSN_LIST, SImode, dtrial,
1463 if (++slot_number == num_slots)
1466 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1471 /* If all insns in the delay slot have been matched and we were previously
1472 annulling the branch, we need not any more. In that case delete all the
1473 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn the
1474 the delay list so that we know that it isn't only being used at the
1476 if (next_to_match == 0 && annul_p)
1478 for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1480 if (GET_MODE (merged_insns) == SImode)
1482 update_block (XEXP (merged_insns, 0), thread);
1483 delete_from_delay_slot (XEXP (merged_insns, 0));
1487 update_block (XEXP (merged_insns, 0), thread);
1488 delete_insn (XEXP (merged_insns, 0));
1492 INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1494 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1495 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1499 /* See if INSN is redundant with an insn in front of TARGET. Often this
1500 is called when INSN is a candidate for a delay slot of TARGET.
1501 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1502 of INSN. Often INSN will be redundant with an insn in a delay slot of
1503 some previous insn. This happens when we have a series of branches to the
1504 same label; in that case the first insn at the target might want to go
1505 into each of the delay slots.
1507 If we are not careful, this routine can take up a significant fraction
1508 of the total compilation time (4%), but only wins rarely. Hence we
1509 speed this routine up by making two passes. The first pass goes back
1510 until it hits a label and sees if it find an insn with an identical
1511 pattern. Only in this (relatively rare) event does it check for
1514 We do not split insns we encounter. This could cause us not to find a
1515 redundant insn, but the cost of splitting seems greater than the possible
1516 gain in rare cases. */
1519 redundant_insn_p (insn, target, delay_list)
1524 rtx target_main = target;
1525 rtx ipat = PATTERN (insn);
1527 struct resources needed, set;
1530 /* Scan backwards looking for a match. */
1531 for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
1533 if (GET_CODE (trial) == CODE_LABEL)
1536 if (GET_CODE (trial) != INSN && GET_CODE (trial) != JUMP_INSN
1537 && GET_CODE (trial) != JUMP_INSN)
1540 pat = PATTERN (trial);
1541 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1544 if (GET_CODE (pat) == SEQUENCE)
1546 /* Stop for a CALL and its delay slots because it difficult to track
1547 its resource needs correctly. */
1548 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1551 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1552 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
1553 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat))
1556 /* If found a match, exit this loop early. */
1561 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat))
1565 /* If we didn't find an insn that matches, return 0. */
1569 /* See what resources this insn sets and needs. If they overlap, or
1570 if this insn references CC0, it can't be redundant. */
1572 CLEAR_RESOURCE (&needed);
1573 CLEAR_RESOURCE (&set);
1574 mark_set_resources (insn, &set, 1);
1575 mark_referenced_resources (insn, &needed, 1);
1577 /* If TARGET is a SEQUENCE, get the main insn. */
1578 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1579 target_main = XVECEXP (PATTERN (target), 0, 0);
1581 if (resource_conflicts_p (&needed, &set)
1583 || reg_mentioned_p (cc0_rtx, ipat)
1585 /* The insn requiring the delay may not set anything needed or set by
1587 || insn_sets_resource_p (target_main, &needed, 1)
1588 || insn_sets_resource_p (target_main, &set, 1))
1591 /* Insns we pass may not set either NEEDED or SET, so merge them for
1593 needed.memory |= set.memory;
1594 IOR_HARD_REG_SET (needed.regs, set.regs);
1596 /* This insn isn't redundant if it conflicts with an insn that either is
1597 or will be in a delay slot of TARGET. */
1601 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
1603 delay_list = XEXP (delay_list, 1);
1606 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1607 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
1608 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
1611 /* Scan backwards until we reach a label or an insn that uses something
1612 INSN sets or sets something insn uses or sets. */
1614 for (trial = PREV_INSN (target);
1615 trial && GET_CODE (trial) != CODE_LABEL;
1616 trial = PREV_INSN (trial))
1618 if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
1619 && GET_CODE (trial) != JUMP_INSN)
1622 pat = PATTERN (trial);
1623 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1626 if (GET_CODE (pat) == SEQUENCE)
1628 /* If this is a CALL_INSN and its delay slots, it is hard to track
1629 the resource needs properly, so give up. */
1630 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1633 /* See if any of the insns in the delay slot match, updating
1634 resource requirements as we go. */
1635 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1637 rtx candidate = XVECEXP (pat, 0, i);
1639 /* If an insn will be annulled if the branch is false, it isn't
1640 considered as a possible duplicate insn. */
1641 if (rtx_equal_p (PATTERN (candidate), ipat)
1642 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1643 && INSN_FROM_TARGET_P (candidate)))
1645 /* Show that this insn will be used in the sequel. */
1646 INSN_FROM_TARGET_P (candidate) = 0;
1650 /* Unless this is an annulled insn from the target of a branch,
1651 we must stop if it sets anything needed or set by INSN. */
1652 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1653 || ! INSN_FROM_TARGET_P (candidate))
1654 && insn_sets_resource_p (candidate, &needed, 1))
1659 /* If the insn requiring the delay slot conflicts with INSN, we
1661 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
1666 /* See if TRIAL is the same as INSN. */
1667 pat = PATTERN (trial);
1668 if (rtx_equal_p (pat, ipat))
1671 /* Can't go any further if TRIAL conflicts with INSN. */
1672 if (insn_sets_resource_p (trial, &needed, 1))
1680 /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero,
1681 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1682 is non-zero, we are allowed to fall into this thread; otherwise, we are
1685 If LABEL is used more than one or we pass a label other than LABEL before
1686 finding an active insn, we do not own this thread. */
1689 own_thread_p (thread, label, allow_fallthrough)
1692 int allow_fallthrough;
1697 /* We don't own the function end. */
1701 /* Get the first active insn, or THREAD, if it is an active insn. */
1702 active_insn = next_active_insn (PREV_INSN (thread));
1704 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
1705 if (GET_CODE (insn) == CODE_LABEL
1706 && (insn != label || LABEL_NUSES (insn) != 1))
1709 if (allow_fallthrough)
1712 /* Ensure that we reach a BARRIER before any insn or label. */
1713 for (insn = prev_nonnote_insn (thread);
1714 insn == 0 || GET_CODE (insn) != BARRIER;
1715 insn = prev_nonnote_insn (insn))
1717 || GET_CODE (insn) == CODE_LABEL
1718 || (GET_CODE (insn) == INSN
1719 && GET_CODE (PATTERN (insn)) != USE
1720 && GET_CODE (PATTERN (insn)) != CLOBBER))
1726 /* Find the number of the basic block that starts closest to INSN. Return -1
1727 if we couldn't find such a basic block. */
1730 find_basic_block (insn)
1735 /* Scan backwards to the previous BARRIER. Then see if we can find a
1736 label that starts a basic block. Return the basic block number. */
1738 for (insn = prev_nonnote_insn (insn);
1739 insn && GET_CODE (insn) != BARRIER;
1740 insn = prev_nonnote_insn (insn))
1743 /* The start of the function is basic block zero. */
1747 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
1748 anything other than a CODE_LABEL or note, we can't find this code. */
1749 for (insn = next_nonnote_insn (insn);
1750 insn && GET_CODE (insn) == CODE_LABEL;
1751 insn = next_nonnote_insn (insn))
1753 for (i = 0; i < n_basic_blocks; i++)
1754 if (insn == basic_block_head[i])
1761 /* Called when INSN is being moved from a location near the target of a jump.
1762 We leave a marker of the form (use (INSN)) immediately in front
1763 of WHERE for mark_target_live_regs. These markers will be deleted when
1766 We used to try to update the live status of registers if WHERE is at
1767 the start of a basic block, but that can't work since we may remove a
1768 BARRIER in relax_delay_slots. */
1771 update_block (insn, where)
1777 /* Ignore if this was in a delay slot and it came from the target of
1779 if (INSN_FROM_TARGET_P (insn))
1782 emit_insn_before (gen_rtx (USE, VOIDmode, insn), where);
1784 /* INSN might be making a value live in a block where it didn't use to
1785 be. So recompute liveness information for this block. */
1787 b = find_basic_block (insn);
1792 /* Marks registers possibly live at the current place being scanned by
1793 mark_target_live_regs. Used only by next two function. */
1795 static HARD_REG_SET current_live_regs;
1797 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
1798 Also only used by the next two functions. */
1800 static HARD_REG_SET pending_dead_regs;
1802 /* Utility function called from mark_target_live_regs via note_stores.
1803 It deadens any CLOBBERed registers and livens any SET registers. */
1806 update_live_status (dest, x)
1810 int first_regno, last_regno;
1813 if (GET_CODE (dest) != REG
1814 && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
1817 if (GET_CODE (dest) == SUBREG)
1818 first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1820 first_regno = REGNO (dest);
1822 last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1824 if (GET_CODE (x) == CLOBBER)
1825 for (i = first_regno; i < last_regno; i++)
1826 CLEAR_HARD_REG_BIT (current_live_regs, i);
1828 for (i = first_regno; i < last_regno; i++)
1830 SET_HARD_REG_BIT (current_live_regs, i);
1831 CLEAR_HARD_REG_BIT (pending_dead_regs, i);
1835 /* Similar to next_insn, but ignores insns in the delay slots of
1836 an annulled branch. */
1839 next_insn_no_annul (insn)
1844 /* If INSN is an annulled branch, skip any insns from the target
1846 if (INSN_ANNULLED_BRANCH_P (insn)
1847 && NEXT_INSN (PREV_INSN (insn)) != insn)
1848 while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
1849 insn = NEXT_INSN (insn);
1851 insn = NEXT_INSN (insn);
1852 if (insn && GET_CODE (insn) == INSN
1853 && GET_CODE (PATTERN (insn)) == SEQUENCE)
1854 insn = XVECEXP (PATTERN (insn), 0, 0);
1860 /* Set the resources that are live at TARGET.
1862 If TARGET is zero, we refer to the end of the current function and can
1863 return our precomputed value.
1865 Otherwise, we try to find out what is live by consulting the basic block
1866 information. This is tricky, because we must consider the actions of
1867 reload and jump optimization, which occur after the basic block information
1870 Accordingly, we proceed as follows::
1872 We find the previous BARRIER and look at all immediately following labels
1873 (with no intervening active insns) to see if any of them start a basic
1874 block. If we hit the start of the function first, we use block 0.
1876 Once we have found a basic block and a corresponding first insns, we can
1877 accurately compute the live status from basic_block_live_regs and
1878 reg_renumber. (By starting at a label following a BARRIER, we are immune
1879 to actions taken by reload and jump.) Then we scan all insns between
1880 that point and our target. For each CLOBBER (or for call-clobbered regs
1881 when we pass a CALL_INSN), mark the appropriate registers are dead. For
1882 a SET, mark them as live.
1884 We have to be careful when using REG_DEAD notes because they are not
1885 updated by such things as find_equiv_reg. So keep track of registers
1886 marked as dead that haven't been assigned to, and mark them dead at the
1887 next CODE_LABEL since reload and jump won't propagate values across labels.
1889 If we cannot find the start of a basic block (should be a very rare
1890 case, if it can happen at all), mark everything as potentially live.
1892 Next, scan forward from TARGET looking for things set or clobbered
1893 before they are used. These are not live.
1895 Because we can be called many times on the same target, save our results
1896 in a hash table indexed by INSN_UID. */
1899 mark_target_live_regs (target, res)
1901 struct resources *res;
1905 struct target_info *tinfo;
1908 HARD_REG_SET scratch;
1909 struct resources set, needed;
1912 /* Handle end of function. */
1915 *res = end_of_function_needs;
1919 /* We have to assume memory is needed, but the CC isn't. */
1924 /* See if we have computed this value already. */
1925 for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1926 tinfo; tinfo = tinfo->next)
1927 if (tinfo->uid == INSN_UID (target))
1930 /* Start by getting the basic block number. If we have saved information,
1931 we can get it from there unless the insn at the start of the basic block
1932 has been deleted. */
1933 if (tinfo && tinfo->block != -1
1934 && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
1938 b = find_basic_block (target);
1942 /* If the information is up-to-date, use it. Otherwise, we will
1944 if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
1946 COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
1952 /* Allocate a place to put our results and chain it into the
1954 tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
1955 tinfo->uid = INSN_UID (target);
1957 tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1958 target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
1961 CLEAR_HARD_REG_SET (pending_dead_regs);
1963 /* If we found a basic block, get the live registers from it and update
1964 them with anything set or killed between its start and the insn before
1965 TARGET. Otherwise, we must assume everything is live. */
1968 regset regs_live = basic_block_live_at_start[b];
1971 rtx start_insn, stop_insn;
1973 /* Compute hard regs live at start of block -- this is the real hard regs
1974 marked live, plus live pseudo regs that have been renumbered to
1978 current_live_regs = *regs_live;
1980 COPY_HARD_REG_SET (current_live_regs, regs_live);
1983 for (offset = 0, i = 0; offset < regset_size; offset++)
1985 if (regs_live[offset] == 0)
1986 i += HOST_BITS_PER_INT;
1988 for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
1989 if ((regs_live[offset] & bit)
1990 && (regno = reg_renumber[i]) >= 0)
1992 j < regno + HARD_REGNO_NREGS (regno,
1993 PSEUDO_REGNO_MODE (i));
1995 SET_HARD_REG_BIT (current_live_regs, j);
1998 /* Get starting and ending insn, handling the case where each might
2000 start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2003 if (GET_CODE (start_insn) == INSN
2004 && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2005 start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2007 if (GET_CODE (stop_insn) == INSN
2008 && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2009 stop_insn = next_insn (PREV_INSN (stop_insn));
2011 for (insn = start_insn; insn != stop_insn;
2012 insn = next_insn_no_annul (insn))
2015 rtx real_insn = insn;
2017 /* If this insn is from the target of a branch, it isn't going to
2018 be used in the sequel. If it is used in both cases, this
2019 test will not be true. */
2020 if (INSN_FROM_TARGET_P (insn))
2023 /* If this insn is a USE made by update_block, we care about the
2025 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2026 && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
2027 || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN
2028 || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN))
2029 real_insn = XEXP (PATTERN (insn), 0);
2031 if (GET_CODE (real_insn) == CALL_INSN)
2033 /* CALL clobbers all call-used regs that aren't fixed except
2034 sp, ap, and fp. Do this before setting the result of the
2036 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2037 if (call_used_regs[i]
2038 && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2039 && i != ARG_POINTER_REGNUM
2040 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2041 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2043 #ifdef PIC_OFFSET_TABLE_REGNUM
2044 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2047 CLEAR_HARD_REG_BIT (current_live_regs, i);
2049 /* A CALL_INSN sets any global register live, since it may
2050 have been modified by the call. */
2051 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2053 SET_HARD_REG_BIT (current_live_regs, i);
2056 /* Mark anything killed in an insn to be deadened at the next
2057 label. Ignore USE insns; the only REG_DEAD notes will be for
2058 parameters. But they might be early. A CALL_INSN will usually
2059 clobber registers used for parameters. It isn't worth bothering
2060 with the unlikely case when it won't. */
2061 if ((GET_CODE (real_insn) == INSN
2062 && GET_CODE (PATTERN (real_insn)) != USE)
2063 || GET_CODE (real_insn) == JUMP_INSN
2064 || GET_CODE (real_insn) == CALL_INSN)
2066 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2067 if (REG_NOTE_KIND (link) == REG_DEAD
2068 && GET_CODE (XEXP (link, 0)) == REG
2069 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2071 int first_regno = REGNO (XEXP (link, 0));
2074 + HARD_REGNO_NREGS (first_regno,
2075 GET_MODE (XEXP (link, 0))));
2077 for (i = first_regno; i < last_regno; i++)
2078 SET_HARD_REG_BIT (pending_dead_regs, i);
2081 note_stores (PATTERN (real_insn), update_live_status);
2083 /* If any registers were unused after this insn, kill them.
2084 These notes will always be accurate. */
2085 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2086 if (REG_NOTE_KIND (link) == REG_UNUSED
2087 && GET_CODE (XEXP (link, 0)) == REG
2088 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2090 int first_regno = REGNO (XEXP (link, 0));
2093 + HARD_REGNO_NREGS (first_regno,
2094 GET_MODE (XEXP (link, 0))));
2096 for (i = first_regno; i < last_regno; i++)
2097 CLEAR_HARD_REG_BIT (current_live_regs, i);
2101 if (GET_CODE (real_insn) == CODE_LABEL)
2103 /* A label clobbers the pending dead registers since neither
2104 reload nor jump will propagate a value across a label. */
2105 AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2106 CLEAR_HARD_REG_SET (pending_dead_regs);
2110 COPY_HARD_REG_SET (res->regs, current_live_regs);
2112 tinfo->bb_tick = bb_ticks[b];
2115 /* We didn't find the start of a basic block. Assume everything
2116 in use. This should happen only extremely rarely. */
2117 SET_HARD_REG_SET (res->regs);
2119 /* Now step forward from TARGET looking for registers that are set before
2120 they are used. These are dead. If we pass a label, any pending dead
2121 registers that weren't yet used can be made dead. Stop when we pass a
2122 conditional JUMP_INSN; follow the first few unconditional branches. */
2124 CLEAR_RESOURCE (&set);
2125 CLEAR_RESOURCE (&needed);
2127 for (insn = target; insn; insn = next)
2129 rtx main_insn = insn;
2131 next = NEXT_INSN (insn);
2132 switch (GET_CODE (insn))
2135 AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2136 AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2137 CLEAR_HARD_REG_SET (pending_dead_regs);
2145 if (GET_CODE (PATTERN (insn)) == USE
2146 || GET_CODE (PATTERN (insn)) == CLOBBER)
2148 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2149 main_insn = XVECEXP (PATTERN (insn), 0, 0);
2152 if (GET_CODE (main_insn) == JUMP_INSN)
2154 if (jump_count++ < 10
2155 && (simplejump_p (main_insn)
2156 || GET_CODE (PATTERN (main_insn)) == RETURN))
2158 next = next_active_insn (JUMP_LABEL (main_insn));
2166 mark_referenced_resources (insn, &needed, 1);
2167 mark_set_resources (insn, &set, 1);
2169 COPY_HARD_REG_SET (scratch, set.regs);
2170 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2171 AND_COMPL_HARD_REG_SET (res->regs, scratch);
2174 /* If we hit an unconditional branch, we have another way of finding out
2175 what is live: we can see what is live at the branch target and include
2176 anything used but not set before the branch. The only things that are
2177 live are those that are live using the above test and the test below.
2179 Don't try this if we expired our jump count above, since that would
2180 mean there may be an infinite loop in the function being compiled. */
2182 if (jump_insn && jump_count < 10)
2184 rtx jump_target = (GET_CODE (jump_insn) == INSN
2185 ? JUMP_LABEL (XVECEXP (PATTERN (jump_insn), 0, 0))
2186 : JUMP_LABEL (jump_insn));
2187 struct resources new_resources;
2188 rtx stop_insn = next_active_insn (jump_insn);
2190 mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2191 CLEAR_RESOURCE (&set);
2192 CLEAR_RESOURCE (&needed);
2194 /* Include JUMP_INSN in the needed registers. */
2195 for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2197 mark_referenced_resources (insn, &needed, 1);
2199 COPY_HARD_REG_SET (scratch, needed.regs);
2200 AND_COMPL_HARD_REG_SET (scratch, set.regs);
2201 IOR_HARD_REG_SET (new_resources.regs, scratch);
2203 mark_set_resources (insn, &set, 1);
2206 AND_HARD_REG_SET (res->regs, new_resources.regs);
2209 COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2212 /* Scan a function looking for insns that need a delay slot and find insns to
2213 put into the delay slot.
2215 NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2216 as calls). We do these first since we don't want jump insns (that are
2217 easier to fill) to get the only insns that could be used for non-jump insns.
2218 When it is zero, only try to fill JUMP_INSNs.
2220 When slots are filled in this manner, the insns (including the
2221 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2222 it is possible to tell whether a delay slot has really been filled
2223 or not. `final' knows how to deal with this, by communicating
2224 through FINAL_SEQUENCE. */
2227 fill_simple_delay_slots (first, non_jumps_p)
2230 register rtx insn, pat, trial, next_trial;
2232 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2233 struct resources needed, set;
2234 register int slots_to_fill, slots_filled;
2237 for (i = 0; i < num_unfilled_slots; i++)
2239 /* Get the next insn to fill. If it has already had any slots assigned,
2240 we can't do anything with it. Maybe we'll improve this later. */
2242 insn = unfilled_slots_base[i];
2244 || INSN_DELETED_P (insn)
2245 || (GET_CODE (insn) == INSN
2246 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2247 || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2248 || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2251 slots_to_fill = num_delay_slots (insn);
2252 if (slots_to_fill == 0)
2255 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2256 says how many. After initialization, scan backwards from the
2257 insn to search for a potential delay-slot candidate. Stop
2258 searching when a label or jump is hit.
2260 For each candidate, if it is to go into the delay slot (moved
2261 forward in execution sequence), it must not need or set any resources
2262 that were set by later insns and must not set any resources that
2263 are needed for those insns.
2265 The delay slot insn itself sets resources unless it is a call
2266 (in which case the called routine, not the insn itself, is doing
2271 CLEAR_RESOURCE (&needed);
2272 CLEAR_RESOURCE (&set);
2273 mark_set_resources (insn, &set, 0);
2274 mark_referenced_resources (insn, &needed, 0);
2276 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2279 next_trial = prev_nonnote_insn (trial);
2281 /* This must be an INSN or CALL_INSN. */
2282 pat = PATTERN (trial);
2284 /* USE and CLOBBER at this level was just for flow; ignore it. */
2285 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2288 /* Check for resource conflict first, to avoid unnecessary
2290 if (! insn_references_resource_p (trial, &set, 1)
2291 && ! insn_sets_resource_p (trial, &set, 1)
2292 && ! insn_sets_resource_p (trial, &needed, 1)
2294 /* Can't separate set of cc0 from its use. */
2295 && ! (reg_mentioned_p (cc0_rtx, pat)
2296 && ! sets_cc0_p (cc0_rtx, pat))
2300 trial = try_split (pat, trial, 1);
2301 next_trial = prev_nonnote_insn (trial);
2302 if (eligible_for_delay (insn, slots_filled, trial))
2304 /* In this case, we are searching backward, so if we
2305 find insns to put on the delay list, we want
2306 to put them at the head, rather than the
2307 tail, of the list. */
2309 delay_list = gen_rtx (INSN_LIST, VOIDmode,
2311 update_block (trial, trial);
2312 delete_insn (trial);
2313 if (slots_to_fill == ++slots_filled)
2319 mark_set_resources (trial, &set, 1);
2320 mark_referenced_resources (trial, &needed, 1);
2323 if (slots_filled == slots_to_fill)
2326 /* If all needed slots haven't been filled, we come here. */
2328 /* Try to optimize case of jumping around a single insn. */
2329 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2330 else if (delay_list == 0
2331 && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
2333 delay_list = optimize_skip (insn);
2339 /* @@ This would be a good place to optimize:
2342 nop add %o7,.-L1,%o7
2348 /* Try to get insns from beyond the insn needing the delay slot.
2349 These insns can neither set or reference resources set in insns being
2350 skipped, cannot set resources in the insn being skipped, and, if this
2351 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2352 call might not return).
2354 If this is a conditional jump, see if it merges back to us early
2355 enough for us to pick up insns from the merge point. Don't do
2356 this if there is another branch to our label unless we pass all of
2359 Another similar merge is if we jump to the same place that a
2360 later unconditional jump branches to. In that case, we don't
2361 care about the number of uses of our label. */
2363 else if (GET_CODE (insn) != JUMP_INSN
2364 || (condjump_p (insn) && ! simplejump_p (insn)
2365 && JUMP_LABEL (insn) != 0))
2368 int maybe_never = 0;
2369 int passed_label = 0;
2371 struct resources needed_at_jump;
2373 CLEAR_RESOURCE (&needed);
2374 CLEAR_RESOURCE (&set);
2376 if (GET_CODE (insn) == CALL_INSN)
2378 mark_set_resources (insn, &set, 1);
2379 mark_referenced_resources (insn, &needed, 1);
2382 else if (GET_CODE (insn) == JUMP_INSN)
2384 /* Get our target and show how many more uses we want to
2385 see before we hit the label. */
2386 target = JUMP_LABEL (insn);
2387 target_uses = LABEL_NUSES (target) - 1;
2390 for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2392 rtx pat, trial_delay;
2394 next_trial = next_nonnote_insn (trial);
2396 if (GET_CODE (trial) == CODE_LABEL)
2400 /* If this is our target, see if we have seen all its uses.
2401 If so, indicate we have passed our target and ignore it.
2402 All other labels cause us to stop our search. */
2403 if (trial == target && target_uses == 0)
2411 else if (GET_CODE (trial) == BARRIER)
2414 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
2415 pat = PATTERN (trial);
2417 /* Stand-alone USE and CLOBBER are just for flow. */
2418 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2421 /* If this already has filled delay slots, get the insn needing
2423 if (GET_CODE (pat) == SEQUENCE)
2424 trial_delay = XVECEXP (pat, 0, 0);
2426 trial_delay = trial;
2428 /* If this is a jump insn to our target, indicate that we have
2429 seen another jump to it. If we aren't handling a conditional
2430 jump, stop our search. Otherwise, compute the needs at its
2431 target and add them to NEEDED. */
2432 if (GET_CODE (trial_delay) == JUMP_INSN)
2436 else if (JUMP_LABEL (trial_delay) == target)
2440 mark_target_live_regs
2441 (next_active_insn (JUMP_LABEL (trial_delay)),
2443 needed.memory |= needed_at_jump.memory;
2444 IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
2448 /* See if we have a resource problem before we try to
2451 && GET_CODE (pat) != SEQUENCE
2452 && ! insn_references_resource_p (trial, &set, 1)
2453 && ! insn_sets_resource_p (trial, &set, 1)
2454 && ! insn_sets_resource_p (trial, &needed, 1)
2456 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2458 && ! (maybe_never && may_trap_p (pat))
2459 && (trial = try_split (pat, trial, 0))
2460 && eligible_for_delay (insn, slots_filled, trial))
2462 next_trial = next_nonnote_insn (trial);
2463 delay_list = add_to_delay_list (trial, delay_list);
2466 if (reg_mentioned_p (cc0_rtx, pat))
2467 link_cc0_insns (trial);
2471 update_block (trial, trial);
2472 delete_insn (trial);
2473 if (slots_to_fill == ++slots_filled)
2478 mark_set_resources (trial, &set, 1);
2479 mark_referenced_resources (trial, &needed, 1);
2481 /* Ensure we don't put insns between the setting of cc and the
2482 comparison by moving a setting of cc into an earlier delay
2483 slot since these insns could clobber the condition code. */
2486 /* If this is a call or jump, we might not get here. */
2487 if (GET_CODE (trial) == CALL_INSN
2488 || GET_CODE (trial) == JUMP_INSN)
2492 /* If there are slots left to fill and our search was stopped by an
2493 unconditional branch, try the insn at the branch target. We can
2494 redirect the branch if it works. */
2495 if (slots_to_fill != slots_filled
2497 && GET_CODE (trial) == JUMP_INSN
2498 && simplejump_p (trial)
2499 && (target == 0 || JUMP_LABEL (trial) == target)
2500 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2501 && ! (GET_CODE (next_trial) == INSN
2502 && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2503 && ! insn_references_resource_p (next_trial, &set, 1)
2504 && ! insn_sets_resource_p (next_trial, &set, 1)
2505 && ! insn_sets_resource_p (next_trial, &needed, 1)
2507 && ! (reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2508 && ! sets_cc0_p (PATTERN (next_trial)))
2510 && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2511 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2512 && eligible_for_delay (insn, slots_filled, next_trial))
2514 rtx new_label = next_active_insn (next_trial);
2517 new_label = get_label_before (new_label);
2520 = add_to_delay_list (copy_rtx (next_trial), delay_list);
2522 redirect_jump (trial, new_label);
2524 /* If we merged because we both jumped to the same place,
2525 redirect the original insn also. */
2527 redirect_jump (insn, new_label);
2532 unfilled_slots_base[i]
2533 = emit_delay_sequence (insn, delay_list,
2534 slots_filled, slots_to_fill);
2536 if (slots_to_fill == slots_filled)
2537 unfilled_slots_base[i] = 0;
2539 note_delay_statistics (slots_filled, 0);
2542 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2543 /* See if the epilogue needs any delay slots. Try to fill them if so.
2544 The only thing we can do is scan backwards from the end of the
2545 function. If we did this in a previous pass, it is incorrect to do it
2547 if (current_function_epilogue_delay_list)
2550 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2551 if (slots_to_fill == 0)
2555 CLEAR_RESOURCE (&needed);
2556 CLEAR_RESOURCE (&set);
2558 for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2559 trial = PREV_INSN (trial))
2561 if (GET_CODE (trial) == NOTE)
2563 pat = PATTERN (trial);
2564 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2567 if (! insn_references_resource_p (trial, &set, 1)
2568 && ! insn_sets_resource_p (trial, &needed, 1)
2570 /* Don't want to mess with cc0 here. */
2571 && ! reg_mentioned_p (cc0_rtx, pat)
2575 trial = try_split (pat, trial, 1);
2576 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2578 /* Here as well we are searching backward, so put the
2579 insns we find on the head of the list. */
2581 current_function_epilogue_delay_list
2582 = gen_rtx (INSN_LIST, VOIDmode, trial,
2583 current_function_epilogue_delay_list);
2584 mark_referenced_resources (trial, &end_of_function_needs, 1);
2585 update_block (trial, trial);
2586 delete_insn (trial);
2588 /* Clear deleted bit so final.c will output the insn. */
2589 INSN_DELETED_P (trial) = 0;
2591 if (slots_to_fill == ++slots_filled)
2597 mark_set_resources (trial, &set, 1);
2598 mark_referenced_resources (trial, &needed, 1);
2601 note_delay_statistics (slots_filled, 0);
2605 /* Try to find insns to place in delay slots.
2607 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2608 or is an unconditional branch if CONDITION is const_true_rtx.
2609 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2611 THREAD is a flow-of-control, either the insns to be executed if the
2612 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2614 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2615 to see if any potential delay slot insns set things needed there.
2617 LIKELY is non-zero if it is extremely likely that the branch will be
2618 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2619 end of a loop back up to the top.
2621 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2622 thread. I.e., it is the fallthrough code of our jump or the target of the
2623 jump when we are the only jump going there.
2625 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2626 case, we can only take insns from the head of the thread for our delay
2627 slot. We then adjust the jump to point after the insns we have taken. */
2630 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
2631 thread_if_true, own_thread, own_opposite_thread,
2632 slots_to_fill, pslots_filled)
2635 rtx thread, opposite_thread;
2638 int own_thread, own_opposite_thread;
2639 int slots_to_fill, *pslots_filled;
2643 struct resources opposite_needed, set, needed;
2648 /* Validate our arguments. */
2649 if ((condition == const_true_rtx && ! thread_if_true)
2650 || (! own_thread && ! thread_if_true))
2653 /* If our thread is the end of subroutine, we can't get any delay
2658 /* If this is an unconditional branch, nothing is needed at the
2659 opposite thread. Otherwise, compute what is needed there. */
2660 if (condition == const_true_rtx)
2661 CLEAR_RESOURCE (&opposite_needed);
2663 mark_target_live_regs (opposite_thread, &opposite_needed);
2665 /* If the insn at THREAD can be split, do it here to avoid having to
2666 update THREAD and NEW_THREAD if it is done in the loop below. Also
2667 initialize NEW_THREAD. */
2669 new_thread = thread = try_split (PATTERN (thread), thread, 0);
2671 /* Scan insns at THREAD. We are looking for an insn that can be removed
2672 from THREAD (it neither sets nor references resources that were set
2673 ahead of it and it doesn't set anything needs by the insns ahead of
2674 it) and that either can be placed in an annulling insn or aren't
2675 needed at OPPOSITE_THREAD. */
2677 CLEAR_RESOURCE (&needed);
2678 CLEAR_RESOURCE (&set);
2680 /* If we do not own this thread, we must stop as soon as we find
2681 something that we can't put in a delay slot, since all we can do
2682 is branch into THREAD at a later point. Therefore, labels stop
2683 the search if this is not the `true' thread. */
2685 for (trial = thread;
2686 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2687 trial = next_nonnote_insn (trial))
2691 /* If we have passed a label, we no longer own this thread. */
2692 if (GET_CODE (trial) == CODE_LABEL)
2698 pat = PATTERN (trial);
2699 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2702 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2703 don't separate or copy insns that set and use CC0. */
2704 if (! insn_references_resource_p (trial, &set, 1)
2705 && ! insn_sets_resource_p (trial, &set, 1)
2706 && ! insn_sets_resource_p (trial, &needed, 1)
2708 && ! (reg_mentioned_p (cc0_rtx, pat)
2709 && (! own_thread || ! sets_cc0_p (pat)))
2713 /* If TRIAL is redundant with some insn before INSN, we don't
2714 actually need to add it to the delay list; we can merely pretend
2716 if (redundant_insn_p (trial, insn, delay_list))
2720 update_block (trial, thread);
2721 delete_insn (trial);
2724 new_thread = next_active_insn (trial);
2729 /* There are two ways we can win: If TRIAL doesn't set anything
2730 needed at the opposite thread and can't trap, or if it can
2731 go into an annulled delay slot. */
2732 if (condition == const_true_rtx
2733 || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2734 && ! may_trap_p (pat)))
2736 trial = try_split (pat, trial, 0);
2737 pat = PATTERN (trial);
2738 if (eligible_for_delay (insn, *pslots_filled, trial))
2742 #ifdef ANNUL_IFTRUE_SLOTS
2745 #ifdef ANNUL_IFFALSE_SLOTS
2750 trial = try_split (pat, trial, 0);
2751 pat = PATTERN (trial);
2753 ? eligible_for_annul_false (insn, *pslots_filled, trial)
2754 : eligible_for_annul_true (insn, *pslots_filled, trial)))
2762 if (reg_mentioned_p (cc0_rtx, pat))
2763 link_cc0_insns (trial);
2766 /* If we own this thread, delete the insn. If this is the
2767 destination of a branch, show that a basic block status
2768 may have been updated. In any case, mark the new
2769 starting point of this thread. */
2772 update_block (trial, thread);
2773 delete_insn (trial);
2776 new_thread = next_active_insn (trial);
2778 temp = own_thread ? trial : copy_rtx (trial);
2780 INSN_FROM_TARGET_P (temp) = 1;
2782 delay_list = add_to_delay_list (temp, delay_list);
2784 if (slots_to_fill == ++(*pslots_filled))
2786 /* Even though we have filled all the slots, we
2787 may be branching to a location that has a
2788 redundant insn. Skip any if so. */
2789 while (new_thread && ! own_thread
2790 && ! insn_sets_resource_p (new_thread, &set, 1)
2791 && ! insn_sets_resource_p (new_thread, &needed, 1)
2792 && ! insn_references_resource_p (new_thread,
2794 && redundant_insn_p (new_thread, insn,
2796 new_thread = next_active_insn (new_thread);
2805 /* This insn can't go into a delay slot. */
2807 mark_set_resources (trial, &set, 1);
2808 mark_referenced_resources (trial, &needed, 1);
2810 /* Ensure we don't put insns between the setting of cc and the comparison
2811 by moving a setting of cc into an earlier delay slot since these insns
2812 could clobber the condition code. */
2815 /* If this insn is a register-register copy and the next insn has
2816 a use of our destination, change it to use our source. That way,
2817 it will become a candidate for our delay slot the next time
2818 through this loop. This case occurs commonly in loops that
2821 We could check for more complex cases than those tested below,
2822 but it doesn't seem worth it. It might also be a good idea to try
2823 to swap the two insns. That might do better.
2825 We can't do this if the next insn modifies our source, because that
2826 would make the replacement into the insn invalid. This also
2827 prevents updating the contents of a PRE_INC. */
2829 if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2830 && GET_CODE (SET_SRC (pat)) == REG
2831 && GET_CODE (SET_DEST (pat)) == REG)
2833 rtx next = next_nonnote_insn (trial);
2835 if (next && GET_CODE (next) == INSN
2836 && GET_CODE (PATTERN (next)) != USE
2837 && ! reg_set_p (SET_DEST (pat), next)
2838 && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
2839 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2843 /* If we stopped on a branch insn that has delay slots, see if we can
2844 steal some of the insns in those slots. */
2845 if (trial && GET_CODE (trial) == INSN
2846 && GET_CODE (PATTERN (trial)) == SEQUENCE
2847 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2849 /* If this is the `true' thread, we will want to follow the jump,
2850 so we can only do this if we have taken everything up to here. */
2851 if (thread_if_true && trial == new_thread)
2853 = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2854 delay_list, &set, &needed,
2855 &opposite_needed, slots_to_fill,
2856 pslots_filled, &must_annul,
2858 else if (! thread_if_true)
2860 = steal_delay_list_from_fallthrough (insn, condition,
2862 delay_list, &set, &needed,
2863 &opposite_needed, slots_to_fill,
2864 pslots_filled, &must_annul);
2867 /* If we haven't found anything for this delay slot and it is very
2868 likely that the branch will be taken, see if the insn at our target
2869 increments or decrements a register with an increment that does not
2870 depend on the destination register. If so, try to place the opposite
2871 arithmetic insn after the jump insn and put the arithmetic insn in the
2872 delay slot. If we can't do this, return. */
2873 if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
2875 rtx pat = PATTERN (new_thread);
2880 pat = PATTERN (trial);
2882 if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
2883 || ! eligible_for_delay (insn, 0, trial))
2886 dest = SET_DEST (pat), src = SET_SRC (pat);
2887 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2888 && rtx_equal_p (XEXP (src, 0), dest)
2889 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
2891 rtx other = XEXP (src, 1);
2895 /* If this is a constant adjustment, use the same code with
2896 the negated constant. Otherwise, reverse the sense of the
2898 if (GET_CODE (other) == CONST_INT)
2899 new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest,
2900 negate_rtx (GET_MODE (src), other));
2902 new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS,
2903 GET_MODE (src), dest, other);
2905 ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith),
2908 if (recog_memoized (ninsn) < 0
2909 || (insn_extract (ninsn),
2910 ! constrain_operands (INSN_CODE (ninsn), 1)))
2912 delete_insn (ninsn);
2918 update_block (trial, thread);
2919 delete_insn (trial);
2922 new_thread = next_active_insn (trial);
2924 ninsn = own_thread ? trial : copy_rtx (trial);
2926 INSN_FROM_TARGET_P (ninsn) = 1;
2928 delay_list = add_to_delay_list (ninsn, 0);
2933 if (delay_list && must_annul)
2934 INSN_ANNULLED_BRANCH_P (insn) = 1;
2936 /* If we are to branch into the middle of this thread, find an appropriate
2937 label or make a new one if none, and redirect INSN to it. If we hit the
2938 end of the function, use the end-of-function label. */
2939 if (new_thread != thread)
2943 if (! thread_if_true)
2946 if (new_thread && GET_CODE (new_thread) == JUMP_INSN
2947 && (simplejump_p (new_thread)
2948 || GET_CODE (PATTERN (new_thread)) == RETURN))
2949 new_thread = follow_jumps (JUMP_LABEL (new_thread), 1);
2951 if (new_thread == 0)
2952 label = find_end_label ();
2953 else if (GET_CODE (new_thread) == CODE_LABEL)
2956 label = get_label_before (new_thread);
2958 redirect_jump (insn, label);
2964 /* Make another attempt to find insns to place in delay slots.
2966 We previously looked for insns located in front of the delay insn
2967 and, for non-jump delay insns, located behind the delay insn.
2969 Here only try to schedule jump insns and try to move insns from either
2970 the target or the following insns into the delay slot. If annulling is
2971 supported, we will be likely to do this. Otherwise, we can do this only
2975 fill_eager_delay_slots (first)
2980 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2982 for (i = 0; i < num_unfilled_slots; i++)
2985 rtx target_label, insn_at_target, fallthrough_insn;
2988 int own_fallthrough;
2989 int prediction, slots_to_fill, slots_filled;
2991 insn = unfilled_slots_base[i];
2993 || INSN_DELETED_P (insn)
2994 || GET_CODE (insn) != JUMP_INSN
2995 || ! condjump_p (insn))
2998 slots_to_fill = num_delay_slots (insn);
2999 if (slots_to_fill == 0)
3003 target_label = JUMP_LABEL (insn);
3004 condition = get_branch_condition (insn, target_label);
3009 /* Get the next active fallthough and target insns and see if we own
3010 them. Then see whether the branch is likely true. We don't need
3011 to do a lot of this for unconditional branches. */
3013 insn_at_target = next_active_insn (target_label);
3014 own_target = own_thread_p (target_label, target_label, 0);
3016 if (condition == const_true_rtx)
3018 own_fallthrough = 0;
3019 fallthrough_insn = 0;
3024 fallthrough_insn = next_active_insn (insn);
3025 own_fallthrough = own_thread_p (NEXT_INSN (insn), 0, 1);
3026 prediction = mostly_true_jump (insn, condition);
3029 /* If this insn is expected to branch, first try to get insns from our
3030 target, then our fallthrough insns. If it is not, expected to branch,
3031 try the other order. */
3036 = fill_slots_from_thread (insn, condition, insn_at_target,
3037 fallthrough_insn, prediction == 2, 1,
3038 own_target, own_fallthrough,
3039 slots_to_fill, &slots_filled);
3041 if (delay_list == 0 && own_fallthrough)
3043 /* Even though we didn't find anything for delay slots,
3044 we might have found a redundant insn which we deleted
3045 from the thread that was filled. So we have to recompute
3046 the next insn at the target. */
3047 target_label = JUMP_LABEL (insn);
3048 insn_at_target = next_active_insn (target_label);
3051 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3052 insn_at_target, 0, 0,
3053 own_fallthrough, own_target,
3054 slots_to_fill, &slots_filled);
3059 if (own_fallthrough)
3061 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3062 insn_at_target, 0, 0,
3063 own_fallthrough, own_target,
3064 slots_to_fill, &slots_filled);
3066 if (delay_list == 0)
3068 = fill_slots_from_thread (insn, condition, insn_at_target,
3069 next_active_insn (insn), 0, 1,
3070 own_target, own_fallthrough,
3071 slots_to_fill, &slots_filled);
3075 unfilled_slots_base[i]
3076 = emit_delay_sequence (insn, delay_list,
3077 slots_filled, slots_to_fill);
3079 if (slots_to_fill == slots_filled)
3080 unfilled_slots_base[i] = 0;
3082 note_delay_statistics (slots_filled, 1);
3086 /* Once we have tried two ways to fill a delay slot, make a pass over the
3087 code to try to improve the results and to do such things as more jump
3091 relax_delay_slots (first)
3094 register rtx insn, next, pat;
3095 register rtx trial, delay_insn, target_label;
3097 /* Look at every JUMP_INSN and see if we can improve it. */
3098 for (insn = first; insn; insn = next)
3102 next = next_active_insn (insn);
3104 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3105 the next insn, or jumps to a label that is not the last of a
3106 group of consecutive labels. */
3107 if (GET_CODE (insn) == JUMP_INSN
3108 && (target_label = JUMP_LABEL (insn)) != 0)
3110 target_label = follow_jumps (target_label, 1);
3111 target_label = prev_label (next_active_insn (target_label));
3113 if (target_label == 0)
3114 target_label = find_end_label ();
3116 if (next_active_insn (target_label) == next)
3122 if (target_label != JUMP_LABEL (insn))
3123 redirect_jump (insn, target_label);
3125 /* See if this jump branches around a unconditional jump.
3126 If so, invert this jump and point it to the target of the
3128 if (next && GET_CODE (next) == JUMP_INSN
3129 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3130 && next_active_insn (target_label) == next_active_insn (next)
3131 && no_labels_between_p (insn, next))
3133 rtx label = JUMP_LABEL (next);
3135 /* Be careful how we do this to avoid deleting code or
3136 labels that are momentarily dead. See similar optimization
3139 We also need to ensure we properly handle the case when
3140 invert_jump fails. */
3142 ++LABEL_NUSES (target_label);
3144 ++LABEL_NUSES (label);
3146 if (invert_jump (insn, label))
3153 --LABEL_NUSES (label);
3155 if (--LABEL_NUSES (target_label) == 0)
3156 delete_insn (target_label);
3162 /* If this is an unconditional jump and the previous insn is a
3163 conditional jump, try reversing the condition of the previous
3164 insn and swapping our targets. The next pass might be able to
3167 Don't do this if we expect the conditional branch to be true, because
3168 we would then be making the more common case longer. */
3170 if (GET_CODE (insn) == JUMP_INSN
3171 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3172 && (other = prev_active_insn (insn)) != 0
3173 && condjump_p (other)
3174 && no_labels_between_p (other, insn)
3175 && ! mostly_true_jump (other,
3176 get_branch_condition (other,
3177 JUMP_LABEL (other))))
3179 rtx other_target = JUMP_LABEL (other);
3181 /* Increment the count of OTHER_TARGET, so it doesn't get deleted
3182 as we move the label. */
3184 ++LABEL_NUSES (other_target);
3186 if (invert_jump (other, target_label))
3187 redirect_jump (insn, other_target);
3190 --LABEL_NUSES (other_target);
3193 /* Now look only at cases where we have filled a delay slot. */
3194 if (GET_CODE (insn) != INSN
3195 || GET_CODE (PATTERN (insn)) != SEQUENCE)
3198 pat = PATTERN (insn);
3199 delay_insn = XVECEXP (pat, 0, 0);
3201 /* See if the first insn in the delay slot is redundant with some
3202 previous insn. Remove it from the delay slot if so; then set up
3203 to reprocess this insn. */
3204 if (redundant_insn_p (XVECEXP (pat, 0, 1), delay_insn, 0))
3206 delete_from_delay_slot (XVECEXP (pat, 0, 1));
3207 next = prev_active_insn (next);
3211 /* Now look only at the cases where we have a filled JUMP_INSN. */
3212 if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3213 || ! condjump_p (XVECEXP (PATTERN (insn), 0, 0)))
3216 target_label = JUMP_LABEL (delay_insn);
3220 /* If this jump goes to another unconditional jump, thread it, but
3221 don't convert a jump into a RETURN here. */
3222 trial = follow_jumps (target_label, 1);
3223 trial = prev_label (next_active_insn (trial));
3224 if (trial == 0 && target_label != 0)
3225 trial = find_end_label ();
3227 if (trial != target_label)
3229 redirect_jump (delay_insn, trial);
3230 target_label = trial;
3233 /* If the first insn at TARGET_LABEL is redundant with a previous
3234 insn, redirect the jump to the following insn process again. */
3235 trial = next_active_insn (target_label);
3236 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3237 && redundant_insn_p (trial, insn, 0))
3239 trial = next_active_insn (trial);
3241 target_label = find_end_label ();
3243 target_label = get_label_before (trial);
3244 redirect_jump (delay_insn, target_label);
3249 /* Similarly, if it is an unconditional jump with one insn in its
3250 delay list and that insn is redundant, thread the jump. */
3251 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3252 && XVECLEN (PATTERN (trial), 0) == 2
3253 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3254 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3255 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3256 && redundant_insn_p (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3258 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3259 if (target_label == 0)
3260 target_label = find_end_label ();
3261 redirect_jump (delay_insn, target_label);
3267 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3268 && prev_active_insn (target_label) == insn
3270 /* If the last insn in the delay slot sets CC0 for some insn,
3271 various code assumes that it is in a delay slot. We could
3272 put it back where it belonged and delete the register notes,
3273 but it doesn't seem worhwhile in this uncommon case. */
3274 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3279 /* All this insn does is execute its delay list and jump to the
3280 following insn. So delete the jump and just execute the delay
3283 We do this by deleting the INSN containing the SEQUENCE, then
3284 re-emitting the insns separately, and then deleting the jump.
3285 This allows the count of the jump target to be properly
3288 trial = PREV_INSN (insn);
3290 emit_insn_after (pat, trial);
3291 delete_scheduled_jump (delay_insn);
3295 /* See if this jump (with its delay slots) branches around another
3296 jump (without delay slots). If so, invert this jump and point
3297 it to the target of the second jump. We cannot do this for
3298 annulled jumps, though. Again, don't convert a jump to a RETURN
3300 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3301 && next && GET_CODE (next) == JUMP_INSN
3302 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3303 && next_active_insn (target_label) == next_active_insn (next)
3304 && no_labels_between_p (insn, next))
3306 rtx label = JUMP_LABEL (next);
3307 rtx old_label = JUMP_LABEL (delay_insn);
3310 label = find_end_label ();
3312 /* Be careful how we do this to avoid deleting code or labels
3313 that are momentarily dead. See similar optimization in jump.c */
3315 ++LABEL_NUSES (old_label);
3317 if (invert_jump (delay_insn, label))
3323 if (old_label && --LABEL_NUSES (old_label) == 0)
3324 delete_insn (old_label);
3328 /* If we own the thread opposite the way this insn branches, see if we
3329 can merge its delay slots with following insns. */
3330 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3331 && own_thread_p (NEXT_INSN (insn), 0, 1))
3332 try_merge_delay_insns (insn, next);
3333 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3334 && own_thread_p (target_label, target_label, 0))
3335 try_merge_delay_insns (insn, next_active_insn (target_label));
3337 /* If we get here, we haven't deleted INSN. But we may have deleted
3338 NEXT, so recompute it. */
3339 next = next_active_insn (insn);
3345 /* Look for filled jumps to the end of function label. We can try to convert
3346 them into RETURN insns if the insns in the delay slot are valid for the
3350 make_return_insns (first)
3353 rtx insn, jump_insn, pat;
3354 rtx real_return_label = end_of_function_label;
3357 /* See if there is a RETURN insn in the function other than the one we
3358 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3359 into a RETURN to jump to it. */
3360 for (insn = first; insn; insn = NEXT_INSN (insn))
3361 if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3363 real_return_label = get_label_before (insn);
3367 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3368 was equal to END_OF_FUNCTION_LABEL. */
3369 LABEL_NUSES (real_return_label)++;
3371 /* Clear the list of insns to fill so we can use it. */
3372 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3374 for (insn = first; insn; insn = NEXT_INSN (insn))
3376 /* Only look at filled JUMP_INSNs that go to the end of function
3378 if (GET_CODE (insn) != INSN
3379 || GET_CODE (PATTERN (insn)) != SEQUENCE
3380 || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3381 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3384 pat = PATTERN (insn);
3385 jump_insn = XVECEXP (pat, 0, 0);
3387 /* If we can't make the jump into a RETURN, redirect it to the best
3388 RETURN and go on to the next insn. */
3389 if (! redirect_jump (jump_insn, 0))
3391 redirect_jump (jump_insn, real_return_label);
3395 /* See if this RETURN can accept the insns current in its delay slot.
3396 It can if it has more or an equal number of slots and the contents
3397 of each is valid. */
3399 slots = num_delay_slots (jump_insn);
3400 if (slots >= XVECLEN (pat, 0) - 1)
3402 for (i = 1; i < XVECLEN (pat, 0); i++)
3404 #ifdef ANNUL_IFFALSE_SLOTS
3405 (INSN_ANNULLED_BRANCH_P (jump_insn)
3406 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3407 ? eligible_for_annul_false (jump_insn, i - 1,
3408 XVECEXP (pat, 0, i)) :
3410 #ifdef ANNUL_IFTRUE_SLOTS
3411 (INSN_ANNULLED_BRANCH_P (jump_insn)
3412 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3413 ? eligible_for_annul_true (jump_insn, i - 1,
3414 XVECEXP (pat, 0, i)) :
3416 eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i))))
3422 if (i == XVECLEN (pat, 0))
3425 /* We have to do something with this insn. If it is an unconditional
3426 RETURN, delete the SEQUENCE and output the individual insns,
3427 followed by the RETURN. Then set things up so we try to find
3428 insns for its delay slots, if it needs some. */
3429 if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3431 rtx prev = PREV_INSN (insn);
3434 for (i = 1; i < XVECLEN (pat, 0); i++)
3435 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3437 insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3438 emit_barrier_after (insn);
3441 obstack_ptr_grow (&unfilled_slots_obstack, insn);
3444 /* It is probably more efficient to keep this with its current
3445 delay slot as a branch to a RETURN. */
3446 redirect_jump (jump_insn, real_return_label);
3449 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3450 new delay slots we have created. */
3451 if (--LABEL_NUSES (real_return_label) == 0)
3452 delete_insn (real_return_label);
3454 fill_simple_delay_slots (first, 1);
3455 fill_simple_delay_slots (first, 0);
3459 /* Try to find insns to place in delay slots. */
3462 dbr_schedule (first, file)
3469 int old_flag_no_peephole = flag_no_peephole;
3471 /* Execute `final' once in prescan mode to delete any insns that won't be
3472 used. Don't let final try to do any peephole optimization--it will
3473 ruin dataflow information for this pass. */
3475 flag_no_peephole = 1;
3476 final (first, 0, NO_DEBUG, 1, 1);
3477 flag_no_peephole = old_flag_no_peephole;
3480 /* Find the highest INSN_UID and allocate and initialize our map from
3481 INSN_UID's to position in code. */
3482 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3483 if (INSN_UID (insn) > max_uid)
3484 max_uid = INSN_UID (insn);
3486 uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
3487 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3488 uid_to_ruid[INSN_UID (insn)] = i;
3490 /* Initialize the list of insns that need filling. */
3491 if (unfilled_firstobj == 0)
3493 gcc_obstack_init (&unfilled_slots_obstack);
3494 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3497 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3501 INSN_ANNULLED_BRANCH_P (insn) = 0;
3502 INSN_FROM_TARGET_P (insn) = 0;
3504 /* Skip vector tables. We can't get attributes for them. */
3505 if (GET_CODE (insn) == JUMP_INSN
3506 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3507 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3510 if (num_delay_slots (insn) > 0)
3511 obstack_ptr_grow (&unfilled_slots_obstack, insn);
3513 /* Ensure all jumps go to the last of a set of consecutive labels. */
3514 if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn)
3515 && JUMP_LABEL (insn) != 0
3516 && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
3517 != JUMP_LABEL (insn)))
3518 redirect_jump (insn, target);
3521 /* Indicate what resources are required to be valid at the end of the current
3522 function. The condition code never is and memory always is. If the
3523 frame pointer is needed, it is and so is the stack pointer unless
3524 EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
3525 stack pointer is. In addition, registers used to return the function
3526 value are needed. */
3528 end_of_function_needs.cc = 0;
3529 end_of_function_needs.memory = 1;
3530 CLEAR_HARD_REG_SET (end_of_function_needs.regs);
3532 if (frame_pointer_needed)
3534 SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
3535 #ifdef EXIT_IGNORE_STACK
3536 if (! EXIT_IGNORE_STACK)
3538 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3541 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3543 if (current_function_return_rtx != 0
3544 && GET_CODE (current_function_return_rtx) == REG)
3545 mark_referenced_resources (current_function_return_rtx,
3546 &end_of_function_needs, 0);
3548 /* Show we haven't computed an end-of-function label yet. */
3549 end_of_function_label = 0;
3551 /* Allocate and initialize the tables used by mark_target_live_regs. */
3553 = (struct target_info **) alloca ((TARGET_HASH_PRIME
3554 * sizeof (struct target_info *)));
3555 bzero (target_hash_table, TARGET_HASH_PRIME * sizeof (struct target_info *));
3557 bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
3558 bzero (bb_ticks, n_basic_blocks * sizeof (int));
3560 /* Initialize the statistics for this function. */
3561 bzero (num_insns_needing_delays, sizeof num_insns_needing_delays);
3562 bzero (num_filled_delays, sizeof num_filled_delays);
3564 /* Now do the delay slot filling. Try everything twice in case earlier
3565 changes make more slots fillable. */
3567 for (reorg_pass_number = 0;
3568 reorg_pass_number < MAX_REORG_PASSES;
3569 reorg_pass_number++)
3571 fill_simple_delay_slots (first, 1);
3572 fill_simple_delay_slots (first, 0);
3573 fill_eager_delay_slots (first);
3574 relax_delay_slots (first);
3577 /* Delete any USE insns made by update_block; subsequent passes don't need
3578 them or know how to deal with them. */
3579 for (insn = first; insn; insn = next)
3581 next = NEXT_INSN (insn);
3583 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3584 && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
3585 || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN
3586 || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN))
3587 next = delete_insn (insn);
3590 /* If we made an end of function label, indicate that it is now
3591 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3592 If it is now unused, delete it. */
3593 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3594 delete_insn (end_of_function_label);
3597 if (HAVE_return && end_of_function_label != 0)
3598 make_return_insns (first);
3601 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3603 /* It is not clear why the line below is needed, but it does seem to be. */
3604 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3608 register int i, j, need_comma;
3610 for (reorg_pass_number = 0;
3611 reorg_pass_number < MAX_REORG_PASSES;
3612 reorg_pass_number++)
3614 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3615 for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3618 fprintf (file, ";; Reorg function #%d\n", i);
3620 fprintf (file, ";; %d insns needing delay slots\n;; ",
3621 num_insns_needing_delays[i][reorg_pass_number]);
3623 for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
3624 if (num_filled_delays[i][j][reorg_pass_number])
3627 fprintf (file, ", ");
3629 fprintf (file, "%d got %d delays",
3630 num_filled_delays[i][j][reorg_pass_number], j);
3632 fprintf (file, "\n");
3637 #endif /* DELAY_SLOTS */