1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
3 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
4 Hacked by Michael Tiemann (tiemann@cygnus.com).
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
22 /* Instruction reorganization pass.
24 This pass runs after register allocation and final jump
25 optimization. It should be the last pass to run before peephole.
26 It serves primarily to fill delay slots of insns, typically branch
27 and call insns. Other insns typically involve more complicated
28 interactions of data dependencies and resource constraints, and
29 are better handled by scheduling before register allocation (by the
30 function `schedule_insns').
32 The Branch Penalty is the number of extra cycles that are needed to
33 execute a branch insn. On an ideal machine, branches take a single
34 cycle, and the Branch Penalty is 0. Several RISC machines approach
35 branch delays differently:
37 The MIPS and AMD 29000 have a single branch delay slot. Most insns
38 (except other branches) can be used to fill this slot. When the
39 slot is filled, two insns execute in two cycles, reducing the
40 branch penalty to zero.
42 The Motorola 88000 conditionally exposes its branch delay slot,
43 so code is shorter when it is turned off, but will run faster
44 when useful insns are scheduled there.
46 The IBM ROMP has two forms of branch and call insns, both with and
47 without a delay slot. Much like the 88k, insns not using the delay
48 slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
50 The SPARC always has a branch delay slot, but its effects can be
51 annulled when the branch is not taken. This means that failing to
52 find other sources of insns, we can hoist an insn from the branch
53 target that would only be safe to execute knowing that the branch
56 The HP-PA always has a branch delay slot. For unconditional branches
57 its effects can be annulled when the branch is taken. The effects
58 of the delay slot in a conditional branch can be nullified for forward
59 taken branches, or for untaken backward branches. This means
60 we can hoist insns from the fall-through path for forward branches or
61 steal insns from the target of backward branches.
63 Three techniques for filling delay slots have been implemented so far:
65 (1) `fill_simple_delay_slots' is the simplest, most efficient way
66 to fill delay slots. This pass first looks for insns which come
67 from before the branch and which are safe to execute after the
68 branch. Then it searches after the insn requiring delay slots or,
69 in the case of a branch, for insns that are after the point at
70 which the branch merges into the fallthrough code, if such a point
71 exists. When such insns are found, the branch penalty decreases
72 and no code expansion takes place.
74 (2) `fill_eager_delay_slots' is more complicated: it is used for
75 scheduling conditional jumps, or for scheduling jumps which cannot
76 be filled using (1). A machine need not have annulled jumps to use
77 this strategy, but it helps (by keeping more options open).
78 `fill_eager_delay_slots' tries to guess the direction the branch
79 will go; if it guesses right 100% of the time, it can reduce the
80 branch penalty as much as `fill_simple_delay_slots' does. If it
81 guesses wrong 100% of the time, it might as well schedule nops (or
82 on the m88k, unexpose the branch slot). When
83 `fill_eager_delay_slots' takes insns from the fall-through path of
84 the jump, usually there is no code expansion; when it takes insns
85 from the branch target, there is code expansion if it is not the
86 only way to reach that target.
88 (3) `relax_delay_slots' uses a set of rules to simplify code that
89 has been reorganized by (1) and (2). It finds cases where
90 conditional test can be eliminated, jumps can be threaded, extra
91 insns can be eliminated, etc. It is the job of (1) and (2) to do a
92 good job of scheduling locally; `relax_delay_slots' takes care of
93 making the various individual schedules work well together. It is
94 especially tuned to handle the control flow interactions of branch
95 insns. It does nothing for insns with delay slots that do not
98 On machines that use CC0, we are very conservative. We will not make
99 a copy of an insn involving CC0 since we want to maintain a 1-1
100 correspondence between the insn that sets and uses CC0. The insns are
101 allowed to be separated by placing an insn that sets CC0 (but not an insn
102 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
103 delay slot. In that case, we point each insn at the other with REG_CC_USER
104 and REG_CC_SETTER notes. Note that these restrictions affect very few
105 machines because most RISC machines with delay slots will not use CC0
106 (the RT is the only known exception at this point).
110 The Acorn Risc Machine can conditionally execute most insns, so
111 it is profitable to move single insns into a position to execute
112 based on the condition code of the previous insn.
114 The HP-PA can conditionally nullify insns, providing a similar
115 effect to the ARM, differing mostly in which insn is "in charge". */
120 #include "insn-config.h"
121 #include "conditions.h"
122 #include "hard-reg-set.h"
123 #include "basic-block.h"
125 #include "insn-flags.h"
130 #include "insn-attr.h"
134 #define obstack_chunk_alloc xmalloc
135 #define obstack_chunk_free free
137 #ifndef ANNUL_IFTRUE_SLOTS
138 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
140 #ifndef ANNUL_IFFALSE_SLOTS
141 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
144 /* Insns which have delay slots that have not yet been filled. */
146 static struct obstack unfilled_slots_obstack;
147 static rtx *unfilled_firstobj;
149 /* Define macros to refer to the first and last slot containing unfilled
150 insns. These are used because the list may move and its address
151 should be recomputed at each use. */
153 #define unfilled_slots_base \
154 ((rtx *) obstack_base (&unfilled_slots_obstack))
156 #define unfilled_slots_next \
157 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
159 /* This structure is used to indicate which hardware resources are set or
160 needed by insns so far. */
164 char memory; /* Insn sets or needs a memory location. */
165 char volatil; /* Insn sets or needs a volatile memory loc. */
166 char cc; /* Insn sets or needs the condition codes. */
167 HARD_REG_SET regs; /* Which registers are set or needed. */
170 /* Macro to clear all resources. */
171 #define CLEAR_RESOURCE(RES) \
172 do { (RES)->memory = (RES)->volatil = (RES)->cc = 0; \
173 CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
175 /* Indicates what resources are required at the beginning of the epilogue. */
176 static struct resources start_of_epilogue_needs;
178 /* Indicates what resources are required at function end. */
179 static struct resources end_of_function_needs;
181 /* Points to the label before the end of the function. */
182 static rtx end_of_function_label;
184 /* This structure is used to record liveness information at the targets or
185 fallthrough insns of branches. We will most likely need the information
186 at targets again, so save them in a hash table rather than recomputing them
191 int uid; /* INSN_UID of target. */
192 struct target_info *next; /* Next info for same hash bucket. */
193 HARD_REG_SET live_regs; /* Registers live at target. */
194 int block; /* Basic block number containing target. */
195 int bb_tick; /* Generation count of basic block info. */
198 #define TARGET_HASH_PRIME 257
200 /* Define the hash table itself. */
201 static struct target_info **target_hash_table;
203 /* For each basic block, we maintain a generation number of its basic
204 block info, which is updated each time we move an insn from the
205 target of a jump. This is the generation number indexed by block
208 static int *bb_ticks;
210 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
211 not always monotonically increase. */
212 static int *uid_to_ruid;
214 /* Highest valid index in `uid_to_ruid'. */
217 static void mark_referenced_resources PROTO((rtx, struct resources *, int));
218 static void mark_set_resources PROTO((rtx, struct resources *, int, int));
219 static int stop_search_p PROTO((rtx, int));
220 static int resource_conflicts_p PROTO((struct resources *,
221 struct resources *));
222 static int insn_references_resource_p PROTO((rtx, struct resources *, int));
223 static int insn_sets_resources_p PROTO((rtx, struct resources *, int));
224 static rtx find_end_label PROTO((void));
225 static rtx emit_delay_sequence PROTO((rtx, rtx, int, int));
226 static rtx add_to_delay_list PROTO((rtx, rtx));
227 static void delete_from_delay_slot PROTO((rtx));
228 static void delete_scheduled_jump PROTO((rtx));
229 static void note_delay_statistics PROTO((int, int));
230 static rtx optimize_skip PROTO((rtx));
231 static int get_jump_flags PROTO((rtx, rtx));
232 static int rare_destination PROTO((rtx));
233 static int mostly_true_jump PROTO((rtx, rtx));
234 static rtx get_branch_condition PROTO((rtx, rtx));
235 static int condition_dominates_p PROTO((rtx, rtx));
236 static rtx steal_delay_list_from_target PROTO((rtx, rtx, rtx, rtx,
240 int, int *, int *, rtx *));
241 static rtx steal_delay_list_from_fallthrough PROTO((rtx, rtx, rtx, rtx,
246 static void try_merge_delay_insns PROTO((rtx, rtx));
247 static rtx redundant_insn PROTO((rtx, rtx, rtx));
248 static int own_thread_p PROTO((rtx, rtx, int));
249 static int find_basic_block PROTO((rtx));
250 static void update_block PROTO((rtx, rtx));
251 static int reorg_redirect_jump PROTO((rtx, rtx));
252 static void update_reg_dead_notes PROTO((rtx, rtx));
253 static void update_reg_unused_notes PROTO((rtx, rtx));
254 static void update_live_status PROTO((rtx, rtx));
255 static rtx next_insn_no_annul PROTO((rtx));
256 static void mark_target_live_regs PROTO((rtx, struct resources *));
257 static void fill_simple_delay_slots PROTO((rtx, int));
258 static rtx fill_slots_from_thread PROTO((rtx, rtx, rtx, rtx, int, int,
259 int, int, int, int *));
260 static void fill_eager_delay_slots PROTO((rtx));
261 static void relax_delay_slots PROTO((rtx));
262 static void make_return_insns PROTO((rtx));
263 static int redirect_with_delay_slots_safe_p PROTO ((rtx, rtx, rtx));
264 static int redirect_with_delay_list_safe_p PROTO ((rtx, rtx, rtx));
266 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
267 which resources are references by the insn. If INCLUDE_CALLED_ROUTINE
268 is TRUE, resources used by the called routine will be included for
272 mark_referenced_resources (x, res, include_delayed_effects)
274 register struct resources *res;
275 register int include_delayed_effects;
277 register enum rtx_code code = GET_CODE (x);
279 register char *format_ptr;
281 /* Handle leaf items for which we set resource flags. Also, special-case
282 CALL, SET and CLOBBER operators. */
294 if (GET_CODE (SUBREG_REG (x)) != REG)
295 mark_referenced_resources (SUBREG_REG (x), res, 0);
298 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
299 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
300 for (i = regno; i < last_regno; i++)
301 SET_HARD_REG_BIT (res->regs, i);
306 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
307 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
311 /* If this memory shouldn't change, it really isn't referencing
313 if (! RTX_UNCHANGING_P (x))
315 res->volatil = MEM_VOLATILE_P (x);
317 /* Mark registers used to access memory. */
318 mark_referenced_resources (XEXP (x, 0), res, 0);
325 case UNSPEC_VOLATILE:
327 /* Traditional asm's are always volatile. */
332 res->volatil = MEM_VOLATILE_P (x);
334 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
335 We can not just fall through here since then we would be confused
336 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
337 traditional asms unlike their normal usage. */
339 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
340 mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
344 /* The first operand will be a (MEM (xxx)) but doesn't really reference
345 memory. The second operand may be referenced, though. */
346 mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
347 mark_referenced_resources (XEXP (x, 1), res, 0);
351 /* Usually, the first operand of SET is set, not referenced. But
352 registers used to access memory are referenced. SET_DEST is
353 also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
355 mark_referenced_resources (SET_SRC (x), res, 0);
358 if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
359 mark_referenced_resources (x, res, 0);
360 else if (GET_CODE (x) == SUBREG)
362 if (GET_CODE (x) == MEM)
363 mark_referenced_resources (XEXP (x, 0), res, 0);
370 if (include_delayed_effects)
372 /* A CALL references memory, the frame pointer if it exists, the
373 stack pointer, any global registers and any registers given in
374 USE insns immediately in front of the CALL.
376 However, we may have moved some of the parameter loading insns
377 into the delay slot of this CALL. If so, the USE's for them
378 don't count and should be skipped. */
379 rtx insn = PREV_INSN (x);
382 rtx next = NEXT_INSN (x);
385 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
386 if (NEXT_INSN (insn) != x)
388 next = NEXT_INSN (NEXT_INSN (insn));
389 sequence = PATTERN (NEXT_INSN (insn));
390 seq_size = XVECLEN (sequence, 0);
391 if (GET_CODE (sequence) != SEQUENCE)
396 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
397 if (frame_pointer_needed)
399 SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
400 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
401 SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM);
405 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
407 SET_HARD_REG_BIT (res->regs, i);
409 /* Check for a NOTE_INSN_SETJMP. If it exists, then we must
410 assume that this call can need any register.
412 This is done to be more conservative about how we handle setjmp.
413 We assume that they both use and set all registers. Using all
414 registers ensures that a register will not be considered dead
415 just because it crosses a setjmp call. A register should be
416 considered dead only if the setjmp call returns non-zero. */
417 if (next && GET_CODE (next) == NOTE
418 && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
419 SET_HARD_REG_SET (res->regs);
424 for (link = CALL_INSN_FUNCTION_USAGE (x);
426 link = XEXP (link, 1))
427 if (GET_CODE (XEXP (link, 0)) == USE)
429 for (i = 1; i < seq_size; i++)
431 rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
432 if (GET_CODE (slot_pat) == SET
433 && rtx_equal_p (SET_DEST (slot_pat),
434 SET_DEST (XEXP (link, 0))))
438 mark_referenced_resources (SET_DEST (XEXP (link, 0)),
444 /* ... fall through to other INSN processing ... */
449 #ifdef INSN_REFERENCES_ARE_DELAYED
450 if (! include_delayed_effects
451 && INSN_REFERENCES_ARE_DELAYED (x))
455 /* No special processing, just speed up. */
456 mark_referenced_resources (PATTERN (x), res, include_delayed_effects);
460 /* Process each sub-expression and flag what it needs. */
461 format_ptr = GET_RTX_FORMAT (code);
462 for (i = 0; i < GET_RTX_LENGTH (code); i++)
463 switch (*format_ptr++)
466 mark_referenced_resources (XEXP (x, i), res, include_delayed_effects);
470 for (j = 0; j < XVECLEN (x, i); j++)
471 mark_referenced_resources (XVECEXP (x, i, j), res,
472 include_delayed_effects);
477 /* Given X, a part of an insn, and a pointer to a `struct resource', RES,
478 indicate which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
479 is nonzero, also mark resources potentially set by the called routine.
481 If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
482 objects are being referenced instead of set.
484 We never mark the insn as modifying the condition code unless it explicitly
485 SETs CC0 even though this is not totally correct. The reason for this is
486 that we require a SET of CC0 to immediately precede the reference to CC0.
487 So if some other insn sets CC0 as a side-effect, we know it cannot affect
488 our computation and thus may be placed in a delay slot. */
491 mark_set_resources (x, res, in_dest, include_delayed_effects)
493 register struct resources *res;
495 int include_delayed_effects;
497 register enum rtx_code code;
499 register char *format_ptr;
517 /* These don't set any resources. */
526 /* Called routine modifies the condition code, memory, any registers
527 that aren't saved across calls, global registers and anything
528 explicitly CLOBBERed immediately after the CALL_INSN. */
530 if (include_delayed_effects)
532 rtx next = NEXT_INSN (x);
533 rtx prev = PREV_INSN (x);
536 res->cc = res->memory = 1;
537 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
538 if (call_used_regs[i] || global_regs[i])
539 SET_HARD_REG_BIT (res->regs, i);
541 /* If X is part of a delay slot sequence, then NEXT should be
542 the first insn after the sequence. */
543 if (NEXT_INSN (prev) != x)
544 next = NEXT_INSN (NEXT_INSN (prev));
546 for (link = CALL_INSN_FUNCTION_USAGE (x);
547 link; link = XEXP (link, 1))
548 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
549 mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1, 0);
551 /* Check for a NOTE_INSN_SETJMP. If it exists, then we must
552 assume that this call can clobber any register. */
553 if (next && GET_CODE (next) == NOTE
554 && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
555 SET_HARD_REG_SET (res->regs);
558 /* ... and also what it's RTL says it modifies, if anything. */
563 /* An insn consisting of just a CLOBBER (or USE) is just for flow
564 and doesn't actually do anything, so we ignore it. */
566 #ifdef INSN_SETS_ARE_DELAYED
567 if (! include_delayed_effects
568 && INSN_SETS_ARE_DELAYED (x))
573 if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
578 /* If the source of a SET is a CALL, this is actually done by
579 the called routine. So only include it if we are to include the
580 effects of the calling routine. */
582 mark_set_resources (SET_DEST (x), res,
583 (include_delayed_effects
584 || GET_CODE (SET_SRC (x)) != CALL),
587 mark_set_resources (SET_SRC (x), res, 0, 0);
591 mark_set_resources (XEXP (x, 0), res, 1, 0);
595 for (i = 0; i < XVECLEN (x, 0); i++)
596 if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0))
597 && INSN_FROM_TARGET_P (XVECEXP (x, 0, i))))
598 mark_set_resources (XVECEXP (x, 0, i), res, 0,
599 include_delayed_effects);
606 mark_set_resources (XEXP (x, 0), res, 1, 0);
610 mark_set_resources (XEXP (x, 0), res, in_dest, 0);
611 mark_set_resources (XEXP (x, 1), res, 0, 0);
612 mark_set_resources (XEXP (x, 2), res, 0, 0);
619 res->volatil = MEM_VOLATILE_P (x);
622 mark_set_resources (XEXP (x, 0), res, 0, 0);
628 if (GET_CODE (SUBREG_REG (x)) != REG)
629 mark_set_resources (SUBREG_REG (x), res,
630 in_dest, include_delayed_effects);
633 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
634 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
635 for (i = regno; i < last_regno; i++)
636 SET_HARD_REG_BIT (res->regs, i);
643 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
644 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
648 /* Process each sub-expression and flag what it needs. */
649 format_ptr = GET_RTX_FORMAT (code);
650 for (i = 0; i < GET_RTX_LENGTH (code); i++)
651 switch (*format_ptr++)
654 mark_set_resources (XEXP (x, i), res, in_dest, include_delayed_effects);
658 for (j = 0; j < XVECLEN (x, i); j++)
659 mark_set_resources (XVECEXP (x, i, j), res, in_dest,
660 include_delayed_effects);
665 /* Return TRUE if this insn should stop the search for insn to fill delay
666 slots. LABELS_P indicates that labels should terminate the search.
667 In all cases, jumps terminate the search. */
670 stop_search_p (insn, labels_p)
677 switch (GET_CODE (insn))
691 /* OK unless it contains a delay slot or is an `asm' insn of some type.
692 We don't know anything about these. */
693 return (GET_CODE (PATTERN (insn)) == SEQUENCE
694 || GET_CODE (PATTERN (insn)) == ASM_INPUT
695 || asm_noperands (PATTERN (insn)) >= 0);
702 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
703 resource set contains a volatile memory reference. Otherwise, return FALSE. */
706 resource_conflicts_p (res1, res2)
707 struct resources *res1, *res2;
709 if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
710 || res1->volatil || res2->volatil)
714 return (res1->regs & res2->regs) != HARD_CONST (0);
719 for (i = 0; i < HARD_REG_SET_LONGS; i++)
720 if ((res1->regs[i] & res2->regs[i]) != 0)
727 /* Return TRUE if any resource marked in RES, a `struct resources', is
728 referenced by INSN. If INCLUDE_CALLED_ROUTINE is set, return if the called
729 routine is using those resources.
731 We compute this by computing all the resources referenced by INSN and
732 seeing if this conflicts with RES. It might be faster to directly check
733 ourselves, and this is the way it used to work, but it means duplicating
734 a large block of complex code. */
737 insn_references_resource_p (insn, res, include_delayed_effects)
739 register struct resources *res;
740 int include_delayed_effects;
742 struct resources insn_res;
744 CLEAR_RESOURCE (&insn_res);
745 mark_referenced_resources (insn, &insn_res, include_delayed_effects);
746 return resource_conflicts_p (&insn_res, res);
749 /* Return TRUE if INSN modifies resources that are marked in RES.
750 INCLUDE_CALLED_ROUTINE is set if the actions of that routine should be
751 included. CC0 is only modified if it is explicitly set; see comments
752 in front of mark_set_resources for details. */
755 insn_sets_resource_p (insn, res, include_delayed_effects)
757 register struct resources *res;
758 int include_delayed_effects;
760 struct resources insn_sets;
762 CLEAR_RESOURCE (&insn_sets);
763 mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
764 return resource_conflicts_p (&insn_sets, res);
767 /* Find a label at the end of the function or before a RETURN. If there is
775 /* If we found one previously, return it. */
776 if (end_of_function_label)
777 return end_of_function_label;
779 /* Otherwise, see if there is a label at the end of the function. If there
780 is, it must be that RETURN insns aren't needed, so that is our return
781 label and we don't have to do anything else. */
783 insn = get_last_insn ();
784 while (GET_CODE (insn) == NOTE
785 || (GET_CODE (insn) == INSN
786 && (GET_CODE (PATTERN (insn)) == USE
787 || GET_CODE (PATTERN (insn)) == CLOBBER)))
788 insn = PREV_INSN (insn);
790 /* When a target threads its epilogue we might already have a
791 suitable return insn. If so put a label before it for the
792 end_of_function_label. */
793 if (GET_CODE (insn) == BARRIER
794 && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
795 && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
797 rtx temp = PREV_INSN (PREV_INSN (insn));
798 end_of_function_label = gen_label_rtx ();
799 LABEL_NUSES (end_of_function_label) = 0;
801 /* Put the label before an USE insns that may proceed the RETURN insn. */
802 while (GET_CODE (temp) == USE)
803 temp = PREV_INSN (temp);
805 emit_label_after (end_of_function_label, temp);
808 else if (GET_CODE (insn) == CODE_LABEL)
809 end_of_function_label = insn;
812 /* Otherwise, make a new label and emit a RETURN and BARRIER,
814 end_of_function_label = gen_label_rtx ();
815 LABEL_NUSES (end_of_function_label) = 0;
816 emit_label (end_of_function_label);
820 /* The return we make may have delay slots too. */
821 rtx insn = gen_return ();
822 insn = emit_jump_insn (insn);
824 if (num_delay_slots (insn) > 0)
825 obstack_ptr_grow (&unfilled_slots_obstack, insn);
830 /* Show one additional use for this label so it won't go away until
832 ++LABEL_NUSES (end_of_function_label);
834 return end_of_function_label;
837 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
838 the pattern of INSN with the SEQUENCE.
840 Chain the insns so that NEXT_INSN of each insn in the sequence points to
841 the next and NEXT_INSN of the last insn in the sequence points to
842 the first insn after the sequence. Similarly for PREV_INSN. This makes
843 it easier to scan all insns.
845 Returns the SEQUENCE that replaces INSN. */
848 emit_delay_sequence (insn, list, length, avail)
858 /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
859 rtvec seqv = rtvec_alloc (length + 1);
860 rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
861 rtx seq_insn = make_insn_raw (seq);
862 rtx first = get_insns ();
863 rtx last = get_last_insn ();
865 /* Make a copy of the insn having delay slots. */
866 rtx delay_insn = copy_rtx (insn);
868 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
869 confuse further processing. Update LAST in case it was the last insn.
870 We will put the BARRIER back in later. */
871 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
873 delete_insn (NEXT_INSN (insn));
874 last = get_last_insn ();
878 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
879 NEXT_INSN (seq_insn) = NEXT_INSN (insn);
880 PREV_INSN (seq_insn) = PREV_INSN (insn);
883 set_new_first_and_last_insn (first, seq_insn);
885 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
888 set_new_first_and_last_insn (seq_insn, last);
890 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
892 /* Build our SEQUENCE and rebuild the insn chain. */
893 XVECEXP (seq, 0, 0) = delay_insn;
894 INSN_DELETED_P (delay_insn) = 0;
895 PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
897 for (li = list; li; li = XEXP (li, 1), i++)
899 rtx tem = XEXP (li, 0);
902 /* Show that this copy of the insn isn't deleted. */
903 INSN_DELETED_P (tem) = 0;
905 XVECEXP (seq, 0, i) = tem;
906 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
907 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
909 /* Remove any REG_DEAD notes because we can't rely on them now
910 that the insn has been moved. */
911 for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
912 if (REG_NOTE_KIND (note) == REG_DEAD)
913 XEXP (note, 0) = const0_rtx;
916 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
918 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
919 last insn in that SEQUENCE to point to us. Similarly for the first
920 insn in the following insn if it is a SEQUENCE. */
922 if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
923 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
924 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
925 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
928 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
929 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
930 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
932 /* If there used to be a BARRIER, put it back. */
934 emit_barrier_after (seq_insn);
942 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
943 be in the order in which the insns are to be executed. */
946 add_to_delay_list (insn, delay_list)
950 /* If we have an empty list, just make a new list element. If
951 INSN has it's block number recorded, clear it since we may
952 be moving the insn to a new block. */
956 struct target_info *tinfo;
958 for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME];
959 tinfo; tinfo = tinfo->next)
960 if (tinfo->uid == INSN_UID (insn))
966 return gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
969 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
971 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
976 /* Delete INSN from the the delay slot of the insn that it is in. This may
977 produce an insn without anything in its delay slots. */
980 delete_from_delay_slot (insn)
983 rtx trial, seq_insn, seq, prev;
987 /* We first must find the insn containing the SEQUENCE with INSN in its
988 delay slot. Do this by finding an insn, TRIAL, where
989 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
992 PREV_INSN (NEXT_INSN (trial)) == trial;
993 trial = NEXT_INSN (trial))
996 seq_insn = PREV_INSN (NEXT_INSN (trial));
997 seq = PATTERN (seq_insn);
999 /* Create a delay list consisting of all the insns other than the one
1000 we are deleting (unless we were the only one). */
1001 if (XVECLEN (seq, 0) > 2)
1002 for (i = 1; i < XVECLEN (seq, 0); i++)
1003 if (XVECEXP (seq, 0, i) != insn)
1004 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
1006 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
1007 list, and rebuild the delay list if non-empty. */
1008 prev = PREV_INSN (seq_insn);
1009 trial = XVECEXP (seq, 0, 0);
1010 delete_insn (seq_insn);
1011 add_insn_after (trial, prev);
1013 if (GET_CODE (trial) == JUMP_INSN
1014 && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
1015 emit_barrier_after (trial);
1017 /* If there are any delay insns, remit them. Otherwise clear the
1020 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2, 0);
1022 INSN_ANNULLED_BRANCH_P (trial) = 0;
1024 INSN_FROM_TARGET_P (insn) = 0;
1026 /* Show we need to fill this insn again. */
1027 obstack_ptr_grow (&unfilled_slots_obstack, trial);
1030 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
1031 the insn that sets CC0 for it and delete it too. */
1034 delete_scheduled_jump (insn)
1037 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
1038 delete the insn that sets the condition code, but it is hard to find it.
1039 Since this case is rare anyway, don't bother trying; there would likely
1040 be other insns that became dead anyway, which we wouldn't know to
1044 if (reg_mentioned_p (cc0_rtx, insn))
1046 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
1048 /* If a reg-note was found, it points to an insn to set CC0. This
1049 insn is in the delay list of some other insn. So delete it from
1050 the delay list it was in. */
1053 if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
1054 && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
1055 delete_from_delay_slot (XEXP (note, 0));
1059 /* The insn setting CC0 is our previous insn, but it may be in
1060 a delay slot. It will be the last insn in the delay slot, if
1062 rtx trial = previous_insn (insn);
1063 if (GET_CODE (trial) == NOTE)
1064 trial = prev_nonnote_insn (trial);
1065 if (sets_cc0_p (PATTERN (trial)) != 1
1066 || FIND_REG_INC_NOTE (trial, 0))
1068 if (PREV_INSN (NEXT_INSN (trial)) == trial)
1069 delete_insn (trial);
1071 delete_from_delay_slot (trial);
1079 /* Counters for delay-slot filling. */
1081 #define NUM_REORG_FUNCTIONS 2
1082 #define MAX_DELAY_HISTOGRAM 3
1083 #define MAX_REORG_PASSES 2
1085 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
1087 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
1089 static int reorg_pass_number;
1092 note_delay_statistics (slots_filled, index)
1093 int slots_filled, index;
1095 num_insns_needing_delays[index][reorg_pass_number]++;
1096 if (slots_filled > MAX_DELAY_HISTOGRAM)
1097 slots_filled = MAX_DELAY_HISTOGRAM;
1098 num_filled_delays[index][slots_filled][reorg_pass_number]++;
1101 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
1103 /* Optimize the following cases:
1105 1. When a conditional branch skips over only one instruction,
1106 use an annulling branch and put that insn in the delay slot.
1107 Use either a branch that annuls when the condition if true or
1108 invert the test with a branch that annuls when the condition is
1109 false. This saves insns, since otherwise we must copy an insn
1112 (orig) (skip) (otherwise)
1113 Bcc.n L1 Bcc',a L1 Bcc,a L1'
1120 2. When a conditional branch skips over only one instruction,
1121 and after that, it unconditionally branches somewhere else,
1122 perform the similar optimization. This saves executing the
1123 second branch in the case where the inverted condition is true.
1130 INSN is a JUMP_INSN.
1132 This should be expanded to skip over N insns, where N is the number
1133 of delay slots required. */
1136 optimize_skip (insn)
1139 register rtx trial = next_nonnote_insn (insn);
1140 rtx next_trial = next_active_insn (trial);
1145 flags = get_jump_flags (insn, JUMP_LABEL (insn));
1148 || GET_CODE (trial) != INSN
1149 || GET_CODE (PATTERN (trial)) == SEQUENCE
1150 || recog_memoized (trial) < 0
1151 || (! eligible_for_annul_false (insn, 0, trial, flags)
1152 && ! eligible_for_annul_true (insn, 0, trial, flags)))
1155 /* There are two cases where we are just executing one insn (we assume
1156 here that a branch requires only one insn; this should be generalized
1157 at some point): Where the branch goes around a single insn or where
1158 we have one insn followed by a branch to the same label we branch to.
1159 In both of these cases, inverting the jump and annulling the delay
1160 slot give the same effect in fewer insns. */
1161 if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
1163 && GET_CODE (next_trial) == JUMP_INSN
1164 && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
1165 && (simplejump_p (next_trial)
1166 || GET_CODE (PATTERN (next_trial)) == RETURN)))
1168 if (eligible_for_annul_false (insn, 0, trial, flags))
1170 if (invert_jump (insn, JUMP_LABEL (insn)))
1171 INSN_FROM_TARGET_P (trial) = 1;
1172 else if (! eligible_for_annul_true (insn, 0, trial, flags))
1176 delay_list = add_to_delay_list (trial, NULL_RTX);
1177 next_trial = next_active_insn (trial);
1178 update_block (trial, trial);
1179 delete_insn (trial);
1181 /* Also, if we are targeting an unconditional
1182 branch, thread our jump to the target of that branch. Don't
1183 change this into a RETURN here, because it may not accept what
1184 we have in the delay slot. We'll fix this up later. */
1185 if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1186 && (simplejump_p (next_trial)
1187 || GET_CODE (PATTERN (next_trial)) == RETURN))
1189 target_label = JUMP_LABEL (next_trial);
1190 if (target_label == 0)
1191 target_label = find_end_label ();
1193 /* Recompute the flags based on TARGET_LABEL since threading
1194 the jump to TARGET_LABEL may change the direction of the
1195 jump (which may change the circumstances in which the
1196 delay slot is nullified). */
1197 flags = get_jump_flags (insn, target_label);
1198 if (eligible_for_annul_true (insn, 0, trial, flags))
1199 reorg_redirect_jump (insn, target_label);
1202 INSN_ANNULLED_BRANCH_P (insn) = 1;
1210 /* Encode and return branch direction and prediction information for
1211 INSN assuming it will jump to LABEL.
1213 Non conditional branches return no direction information and
1214 are predicted as very likely taken. */
1216 get_jump_flags (insn, label)
1221 /* get_jump_flags can be passed any insn with delay slots, these may
1222 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
1223 direction information, and only if they are conditional jumps.
1225 If LABEL is zero, then there is no way to determine the branch
1227 if (GET_CODE (insn) == JUMP_INSN
1228 && (condjump_p (insn) || condjump_in_parallel_p (insn))
1229 && INSN_UID (insn) <= max_uid
1231 && INSN_UID (label) <= max_uid)
1233 = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
1234 ? ATTR_FLAG_forward : ATTR_FLAG_backward;
1235 /* No valid direction information. */
1239 /* If insn is a conditional branch call mostly_true_jump to get
1240 determine the branch prediction.
1242 Non conditional branches are predicted as very likely taken. */
1243 if (GET_CODE (insn) == JUMP_INSN
1244 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
1248 prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
1252 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
1255 flags |= ATTR_FLAG_likely;
1258 flags |= ATTR_FLAG_unlikely;
1261 flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
1269 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
1274 /* Return 1 if INSN is a destination that will be branched to rarely (the
1275 return point of a function); return 2 if DEST will be branched to very
1276 rarely (a call to a function that doesn't return). Otherwise,
1280 rare_destination (insn)
1286 for (; insn; insn = next)
1288 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE)
1289 insn = XVECEXP (PATTERN (insn), 0, 0);
1291 next = NEXT_INSN (insn);
1293 switch (GET_CODE (insn))
1298 /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We
1299 don't scan past JUMP_INSNs, so any barrier we find here must
1300 have been after a CALL_INSN and hence mean the call doesn't
1304 if (GET_CODE (PATTERN (insn)) == RETURN)
1306 else if (simplejump_p (insn)
1307 && jump_count++ < 10)
1308 next = JUMP_LABEL (insn);
1314 /* If we got here it means we hit the end of the function. So this
1315 is an unlikely destination. */
1320 /* Return truth value of the statement that this branch
1321 is mostly taken. If we think that the branch is extremely likely
1322 to be taken, we return 2. If the branch is slightly more likely to be
1323 taken, return 1. If the branch is slightly less likely to be taken,
1324 return 0 and if the branch is highly unlikely to be taken, return -1.
1326 CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */
1329 mostly_true_jump (jump_insn, condition)
1330 rtx jump_insn, condition;
1332 rtx target_label = JUMP_LABEL (jump_insn);
1334 int rare_dest = rare_destination (target_label);
1335 int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
1337 /* If this is a branch outside a loop, it is highly unlikely. */
1338 if (GET_CODE (PATTERN (jump_insn)) == SET
1339 && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
1340 && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
1341 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
1342 || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
1343 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
1348 /* If this is the test of a loop, it is very likely true. We scan
1349 backwards from the target label. If we find a NOTE_INSN_LOOP_BEG
1350 before the next real insn, we assume the branch is to the top of
1352 for (insn = PREV_INSN (target_label);
1353 insn && GET_CODE (insn) == NOTE;
1354 insn = PREV_INSN (insn))
1355 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1358 /* If this is a jump to the test of a loop, it is likely true. We scan
1359 forwards from the target label. If we find a NOTE_INSN_LOOP_VTOP
1360 before the next real insn, we assume the branch is to the loop branch
1362 for (insn = NEXT_INSN (target_label);
1363 insn && GET_CODE (insn) == NOTE;
1364 insn = PREV_INSN (insn))
1365 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
1369 /* Look at the relative rarities of the fallthough and destination. If
1370 they differ, we can predict the branch that way. */
1372 switch (rare_fallthrough - rare_dest)
1386 /* If we couldn't figure out what this jump was, assume it won't be
1387 taken. This should be rare. */
1391 /* EQ tests are usually false and NE tests are usually true. Also,
1392 most quantities are positive, so we can make the appropriate guesses
1393 about signed comparisons against zero. */
1394 switch (GET_CODE (condition))
1397 /* Unconditional branch. */
1405 if (XEXP (condition, 1) == const0_rtx)
1410 if (XEXP (condition, 1) == const0_rtx)
1415 /* Predict backward branches usually take, forward branches usually not. If
1416 we don't know whether this is forward or backward, assume the branch
1417 will be taken, since most are. */
1418 return (target_label == 0 || INSN_UID (jump_insn) > max_uid
1419 || INSN_UID (target_label) > max_uid
1420 || (uid_to_ruid[INSN_UID (jump_insn)]
1421 > uid_to_ruid[INSN_UID (target_label)]));;
1424 /* Return the condition under which INSN will branch to TARGET. If TARGET
1425 is zero, return the condition under which INSN will return. If INSN is
1426 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1427 type of jump, or it doesn't go to TARGET, return 0. */
1430 get_branch_condition (insn, target)
1434 rtx pat = PATTERN (insn);
1437 if (condjump_in_parallel_p (insn))
1438 pat = XVECEXP (pat, 0, 0);
1440 if (GET_CODE (pat) == RETURN)
1441 return target == 0 ? const_true_rtx : 0;
1443 else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1446 src = SET_SRC (pat);
1447 if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1448 return const_true_rtx;
1450 else if (GET_CODE (src) == IF_THEN_ELSE
1451 && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1452 || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1453 && XEXP (XEXP (src, 1), 0) == target))
1454 && XEXP (src, 2) == pc_rtx)
1455 return XEXP (src, 0);
1457 else if (GET_CODE (src) == IF_THEN_ELSE
1458 && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1459 || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1460 && XEXP (XEXP (src, 2), 0) == target))
1461 && XEXP (src, 1) == pc_rtx)
1462 return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
1463 GET_MODE (XEXP (src, 0)),
1464 XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1469 /* Return non-zero if CONDITION is more strict than the condition of
1470 INSN, i.e., if INSN will always branch if CONDITION is true. */
1473 condition_dominates_p (condition, insn)
1477 rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1478 enum rtx_code code = GET_CODE (condition);
1479 enum rtx_code other_code;
1481 if (rtx_equal_p (condition, other_condition)
1482 || other_condition == const_true_rtx)
1485 else if (condition == const_true_rtx || other_condition == 0)
1488 other_code = GET_CODE (other_condition);
1489 if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1490 || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1491 || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1494 return comparison_dominates_p (code, other_code);
1497 /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
1498 any insns already in the delay slot of JUMP. */
1501 redirect_with_delay_slots_safe_p (jump, newlabel, seq)
1502 rtx jump, newlabel, seq;
1504 int flags, slots, i;
1505 rtx pat = PATTERN (seq);
1507 /* Make sure all the delay slots of this jump would still
1508 be valid after threading the jump. If they are still
1509 valid, then return non-zero. */
1511 flags = get_jump_flags (jump, newlabel);
1512 for (i = 1; i < XVECLEN (pat, 0); i++)
1514 #ifdef ANNUL_IFFALSE_SLOTS
1515 (INSN_ANNULLED_BRANCH_P (jump)
1516 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1517 ? eligible_for_annul_false (jump, i - 1,
1518 XVECEXP (pat, 0, i), flags) :
1520 #ifdef ANNUL_IFTRUE_SLOTS
1521 (INSN_ANNULLED_BRANCH_P (jump)
1522 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1523 ? eligible_for_annul_true (jump, i - 1,
1524 XVECEXP (pat, 0, i), flags) :
1526 eligible_for_delay (jump, i -1, XVECEXP (pat, 0, i), flags)))
1529 return (i == XVECLEN (pat, 0));
1532 /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
1533 any insns we wish to place in the delay slot of JUMP. */
1536 redirect_with_delay_list_safe_p (jump, newlabel, delay_list)
1537 rtx jump, newlabel, delay_list;
1542 /* Make sure all the insns in DELAY_LIST would still be
1543 valid after threading the jump. If they are still
1544 valid, then return non-zero. */
1546 flags = get_jump_flags (jump, newlabel);
1547 for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++)
1549 #ifdef ANNUL_IFFALSE_SLOTS
1550 (INSN_ANNULLED_BRANCH_P (jump)
1551 && INSN_FROM_TARGET_P (XEXP (li, 0)))
1552 ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) :
1554 #ifdef ANNUL_IFTRUE_SLOTS
1555 (INSN_ANNULLED_BRANCH_P (jump)
1556 && ! INSN_FROM_TARGET_P (XEXP (li, 0)))
1557 ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) :
1559 eligible_for_delay (jump, i, XEXP (li, 0), flags)))
1562 return (li == NULL);
1566 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1567 the condition tested by INSN is CONDITION and the resources shown in
1568 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1569 from SEQ's delay list, in addition to whatever insns it may execute
1570 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1571 needed while searching for delay slot insns. Return the concatenated
1572 delay list if possible, otherwise, return 0.
1574 SLOTS_TO_FILL is the total number of slots required by INSN, and
1575 PSLOTS_FILLED points to the number filled so far (also the number of
1576 insns in DELAY_LIST). It is updated with the number that have been
1577 filled from the SEQUENCE, if any.
1579 PANNUL_P points to a non-zero value if we already know that we need
1580 to annul INSN. If this routine determines that annulling is needed,
1581 it may set that value non-zero.
1583 PNEW_THREAD points to a location that is to receive the place at which
1584 execution should continue. */
1587 steal_delay_list_from_target (insn, condition, seq, delay_list,
1588 sets, needed, other_needed,
1589 slots_to_fill, pslots_filled, pannul_p,
1591 rtx insn, condition;
1594 struct resources *sets, *needed, *other_needed;
1601 int slots_remaining = slots_to_fill - *pslots_filled;
1602 int total_slots_filled = *pslots_filled;
1603 rtx new_delay_list = 0;
1604 int must_annul = *pannul_p;
1607 /* We can't do anything if there are more delay slots in SEQ than we
1608 can handle, or if we don't know that it will be a taken branch.
1609 We know that it will be a taken branch if it is either an unconditional
1610 branch or a conditional branch with a stricter branch condition.
1612 Also, exit if the branch has more than one set, since then it is computing
1613 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1614 ??? It may be possible to move other sets into INSN in addition to
1615 moving the instructions in the delay slots. */
1617 if (XVECLEN (seq, 0) - 1 > slots_remaining
1618 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))
1619 || ! single_set (XVECEXP (seq, 0, 0)))
1622 for (i = 1; i < XVECLEN (seq, 0); i++)
1624 rtx trial = XVECEXP (seq, 0, i);
1627 if (insn_references_resource_p (trial, sets, 0)
1628 || insn_sets_resource_p (trial, needed, 0)
1629 || insn_sets_resource_p (trial, sets, 0)
1631 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1633 || find_reg_note (trial, REG_CC_USER, NULL_RTX)
1635 /* If TRIAL is from the fallthrough code of an annulled branch insn
1636 in SEQ, we cannot use it. */
1637 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1638 && ! INSN_FROM_TARGET_P (trial)))
1641 /* If this insn was already done (usually in a previous delay slot),
1642 pretend we put it in our delay slot. */
1643 if (redundant_insn (trial, insn, new_delay_list))
1646 /* We will end up re-vectoring this branch, so compute flags
1647 based on jumping to the new label. */
1648 flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
1651 && ((condition == const_true_rtx
1652 || (! insn_sets_resource_p (trial, other_needed, 0)
1653 && ! may_trap_p (PATTERN (trial)))))
1654 ? eligible_for_delay (insn, total_slots_filled, trial, flags)
1656 eligible_for_annul_false (insn, total_slots_filled, trial, flags)))
1658 temp = copy_rtx (trial);
1659 INSN_FROM_TARGET_P (temp) = 1;
1660 new_delay_list = add_to_delay_list (temp, new_delay_list);
1661 total_slots_filled++;
1663 if (--slots_remaining == 0)
1670 /* Show the place to which we will be branching. */
1671 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1673 /* Add any new insns to the delay list and update the count of the
1674 number of slots filled. */
1675 *pslots_filled = total_slots_filled;
1676 *pannul_p = must_annul;
1678 if (delay_list == 0)
1679 return new_delay_list;
1681 for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1682 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1687 /* Similar to steal_delay_list_from_target except that SEQ is on the
1688 fallthrough path of INSN. Here we only do something if the delay insn
1689 of SEQ is an unconditional branch. In that case we steal its delay slot
1690 for INSN since unconditional branches are much easier to fill. */
1693 steal_delay_list_from_fallthrough (insn, condition, seq,
1694 delay_list, sets, needed, other_needed,
1695 slots_to_fill, pslots_filled, pannul_p)
1696 rtx insn, condition;
1699 struct resources *sets, *needed, *other_needed;
1707 flags = get_jump_flags (insn, JUMP_LABEL (insn));
1709 /* We can't do anything if SEQ's delay insn isn't an
1710 unconditional branch. */
1712 if (! simplejump_p (XVECEXP (seq, 0, 0))
1713 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1716 for (i = 1; i < XVECLEN (seq, 0); i++)
1718 rtx trial = XVECEXP (seq, 0, i);
1720 /* If TRIAL sets CC0, stealing it will move it too far from the use
1722 if (insn_references_resource_p (trial, sets, 0)
1723 || insn_sets_resource_p (trial, needed, 0)
1724 || insn_sets_resource_p (trial, sets, 0)
1726 || sets_cc0_p (PATTERN (trial))
1732 /* If this insn was already done, we don't need it. */
1733 if (redundant_insn (trial, insn, delay_list))
1735 delete_from_delay_slot (trial);
1740 && ((condition == const_true_rtx
1741 || (! insn_sets_resource_p (trial, other_needed, 0)
1742 && ! may_trap_p (PATTERN (trial)))))
1743 ? eligible_for_delay (insn, *pslots_filled, trial, flags)
1745 eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
1747 delete_from_delay_slot (trial);
1748 delay_list = add_to_delay_list (trial, delay_list);
1750 if (++(*pslots_filled) == slots_to_fill)
1760 /* Try merging insns starting at THREAD which match exactly the insns in
1763 If all insns were matched and the insn was previously annulling, the
1764 annul bit will be cleared.
1766 For each insn that is merged, if the branch is or will be non-annulling,
1767 we delete the merged insn. */
1770 try_merge_delay_insns (insn, thread)
1773 rtx trial, next_trial;
1774 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1775 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1776 int slot_number = 1;
1777 int num_slots = XVECLEN (PATTERN (insn), 0);
1778 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1779 struct resources set, needed;
1780 rtx merged_insns = 0;
1784 flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
1786 CLEAR_RESOURCE (&needed);
1787 CLEAR_RESOURCE (&set);
1789 /* If this is not an annulling branch, take into account anything needed in
1790 NEXT_TO_MATCH. This prevents two increments from being incorrectly
1791 folded into one. If we are annulling, this would be the correct
1792 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1793 will essentially disable this optimization. This method is somewhat of
1794 a kludge, but I don't see a better way.) */
1796 mark_referenced_resources (next_to_match, &needed, 1);
1798 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1800 rtx pat = PATTERN (trial);
1801 rtx oldtrial = trial;
1803 next_trial = next_nonnote_insn (trial);
1805 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1806 if (GET_CODE (trial) == INSN
1807 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1810 if (GET_CODE (next_to_match) == GET_CODE (trial)
1812 /* We can't share an insn that sets cc0. */
1813 && ! sets_cc0_p (pat)
1815 && ! insn_references_resource_p (trial, &set, 1)
1816 && ! insn_sets_resource_p (trial, &set, 1)
1817 && ! insn_sets_resource_p (trial, &needed, 1)
1818 && (trial = try_split (pat, trial, 0)) != 0
1819 /* Update next_trial, in case try_split succeeded. */
1820 && (next_trial = next_nonnote_insn (trial))
1821 /* Likewise THREAD. */
1822 && (thread = oldtrial == thread ? trial : thread)
1823 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1824 /* Have to test this condition if annul condition is different
1825 from (and less restrictive than) non-annulling one. */
1826 && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
1831 update_block (trial, thread);
1832 if (trial == thread)
1833 thread = next_active_insn (thread);
1835 delete_insn (trial);
1836 INSN_FROM_TARGET_P (next_to_match) = 0;
1839 merged_insns = gen_rtx (INSN_LIST, VOIDmode, trial, merged_insns);
1841 if (++slot_number == num_slots)
1844 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1846 mark_referenced_resources (next_to_match, &needed, 1);
1849 mark_set_resources (trial, &set, 0, 1);
1850 mark_referenced_resources (trial, &needed, 1);
1853 /* See if we stopped on a filled insn. If we did, try to see if its
1854 delay slots match. */
1855 if (slot_number != num_slots
1856 && trial && GET_CODE (trial) == INSN
1857 && GET_CODE (PATTERN (trial)) == SEQUENCE
1858 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1860 rtx pat = PATTERN (trial);
1861 rtx filled_insn = XVECEXP (pat, 0, 0);
1863 /* Account for resources set/needed by the filled insn. */
1864 mark_set_resources (filled_insn, &set, 0, 1);
1865 mark_referenced_resources (filled_insn, &needed, 1);
1867 for (i = 1; i < XVECLEN (pat, 0); i++)
1869 rtx dtrial = XVECEXP (pat, 0, i);
1871 if (! insn_references_resource_p (dtrial, &set, 1)
1872 && ! insn_sets_resource_p (dtrial, &set, 1)
1873 && ! insn_sets_resource_p (dtrial, &needed, 1)
1875 && ! sets_cc0_p (PATTERN (dtrial))
1877 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1878 && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
1882 update_block (dtrial, thread);
1883 delete_from_delay_slot (dtrial);
1884 INSN_FROM_TARGET_P (next_to_match) = 0;
1887 merged_insns = gen_rtx (INSN_LIST, SImode, dtrial,
1890 if (++slot_number == num_slots)
1893 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1898 /* If all insns in the delay slot have been matched and we were previously
1899 annulling the branch, we need not any more. In that case delete all the
1900 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn the
1901 the delay list so that we know that it isn't only being used at the
1903 if (slot_number == num_slots && annul_p)
1905 for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1907 if (GET_MODE (merged_insns) == SImode)
1909 update_block (XEXP (merged_insns, 0), thread);
1910 delete_from_delay_slot (XEXP (merged_insns, 0));
1914 update_block (XEXP (merged_insns, 0), thread);
1915 delete_insn (XEXP (merged_insns, 0));
1919 INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1921 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1922 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1926 /* See if INSN is redundant with an insn in front of TARGET. Often this
1927 is called when INSN is a candidate for a delay slot of TARGET.
1928 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1929 of INSN. Often INSN will be redundant with an insn in a delay slot of
1930 some previous insn. This happens when we have a series of branches to the
1931 same label; in that case the first insn at the target might want to go
1932 into each of the delay slots.
1934 If we are not careful, this routine can take up a significant fraction
1935 of the total compilation time (4%), but only wins rarely. Hence we
1936 speed this routine up by making two passes. The first pass goes back
1937 until it hits a label and sees if it find an insn with an identical
1938 pattern. Only in this (relatively rare) event does it check for
1941 We do not split insns we encounter. This could cause us not to find a
1942 redundant insn, but the cost of splitting seems greater than the possible
1943 gain in rare cases. */
1946 redundant_insn (insn, target, delay_list)
1951 rtx target_main = target;
1952 rtx ipat = PATTERN (insn);
1954 struct resources needed, set;
1957 /* Scan backwards looking for a match. */
1958 for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
1960 if (GET_CODE (trial) == CODE_LABEL)
1963 if (GET_RTX_CLASS (GET_CODE (trial)) != 'i')
1966 pat = PATTERN (trial);
1967 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1970 if (GET_CODE (pat) == SEQUENCE)
1972 /* Stop for a CALL and its delay slots because it is difficult to
1973 track its resource needs correctly. */
1974 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1977 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1978 slots because it is difficult to track its resource needs
1981 #ifdef INSN_SETS_ARE_DELAYED
1982 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
1986 #ifdef INSN_REFERENCES_ARE_DELAYED
1987 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
1991 /* See if any of the insns in the delay slot match, updating
1992 resource requirements as we go. */
1993 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1994 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
1995 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat))
1998 /* If found a match, exit this loop early. */
2003 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat))
2007 /* If we didn't find an insn that matches, return 0. */
2011 /* See what resources this insn sets and needs. If they overlap, or
2012 if this insn references CC0, it can't be redundant. */
2014 CLEAR_RESOURCE (&needed);
2015 CLEAR_RESOURCE (&set);
2016 mark_set_resources (insn, &set, 0, 1);
2017 mark_referenced_resources (insn, &needed, 1);
2019 /* If TARGET is a SEQUENCE, get the main insn. */
2020 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2021 target_main = XVECEXP (PATTERN (target), 0, 0);
2023 if (resource_conflicts_p (&needed, &set)
2025 || reg_mentioned_p (cc0_rtx, ipat)
2027 /* The insn requiring the delay may not set anything needed or set by
2029 || insn_sets_resource_p (target_main, &needed, 1)
2030 || insn_sets_resource_p (target_main, &set, 1))
2033 /* Insns we pass may not set either NEEDED or SET, so merge them for
2035 needed.memory |= set.memory;
2036 IOR_HARD_REG_SET (needed.regs, set.regs);
2038 /* This insn isn't redundant if it conflicts with an insn that either is
2039 or will be in a delay slot of TARGET. */
2043 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
2045 delay_list = XEXP (delay_list, 1);
2048 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2049 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
2050 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
2053 /* Scan backwards until we reach a label or an insn that uses something
2054 INSN sets or sets something insn uses or sets. */
2056 for (trial = PREV_INSN (target);
2057 trial && GET_CODE (trial) != CODE_LABEL;
2058 trial = PREV_INSN (trial))
2060 if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
2061 && GET_CODE (trial) != JUMP_INSN)
2064 pat = PATTERN (trial);
2065 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2068 if (GET_CODE (pat) == SEQUENCE)
2070 /* If this is a CALL_INSN and its delay slots, it is hard to track
2071 the resource needs properly, so give up. */
2072 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2075 /* If this this is an INSN or JUMP_INSN with delayed effects, it
2076 is hard to track the resource needs properly, so give up. */
2078 #ifdef INSN_SETS_ARE_DELAYED
2079 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2083 #ifdef INSN_REFERENCES_ARE_DELAYED
2084 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2088 /* See if any of the insns in the delay slot match, updating
2089 resource requirements as we go. */
2090 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2092 rtx candidate = XVECEXP (pat, 0, i);
2094 /* If an insn will be annulled if the branch is false, it isn't
2095 considered as a possible duplicate insn. */
2096 if (rtx_equal_p (PATTERN (candidate), ipat)
2097 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2098 && INSN_FROM_TARGET_P (candidate)))
2100 /* Show that this insn will be used in the sequel. */
2101 INSN_FROM_TARGET_P (candidate) = 0;
2105 /* Unless this is an annulled insn from the target of a branch,
2106 we must stop if it sets anything needed or set by INSN. */
2107 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2108 || ! INSN_FROM_TARGET_P (candidate))
2109 && insn_sets_resource_p (candidate, &needed, 1))
2114 /* If the insn requiring the delay slot conflicts with INSN, we
2116 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
2121 /* See if TRIAL is the same as INSN. */
2122 pat = PATTERN (trial);
2123 if (rtx_equal_p (pat, ipat))
2126 /* Can't go any further if TRIAL conflicts with INSN. */
2127 if (insn_sets_resource_p (trial, &needed, 1))
2135 /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero,
2136 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
2137 is non-zero, we are allowed to fall into this thread; otherwise, we are
2140 If LABEL is used more than one or we pass a label other than LABEL before
2141 finding an active insn, we do not own this thread. */
2144 own_thread_p (thread, label, allow_fallthrough)
2147 int allow_fallthrough;
2152 /* We don't own the function end. */
2156 /* Get the first active insn, or THREAD, if it is an active insn. */
2157 active_insn = next_active_insn (PREV_INSN (thread));
2159 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
2160 if (GET_CODE (insn) == CODE_LABEL
2161 && (insn != label || LABEL_NUSES (insn) != 1))
2164 if (allow_fallthrough)
2167 /* Ensure that we reach a BARRIER before any insn or label. */
2168 for (insn = prev_nonnote_insn (thread);
2169 insn == 0 || GET_CODE (insn) != BARRIER;
2170 insn = prev_nonnote_insn (insn))
2172 || GET_CODE (insn) == CODE_LABEL
2173 || (GET_CODE (insn) == INSN
2174 && GET_CODE (PATTERN (insn)) != USE
2175 && GET_CODE (PATTERN (insn)) != CLOBBER))
2181 /* Find the number of the basic block that starts closest to INSN. Return -1
2182 if we couldn't find such a basic block. */
2185 find_basic_block (insn)
2190 /* Scan backwards to the previous BARRIER. Then see if we can find a
2191 label that starts a basic block. Return the basic block number. */
2193 for (insn = prev_nonnote_insn (insn);
2194 insn && GET_CODE (insn) != BARRIER;
2195 insn = prev_nonnote_insn (insn))
2198 /* The start of the function is basic block zero. */
2202 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
2203 anything other than a CODE_LABEL or note, we can't find this code. */
2204 for (insn = next_nonnote_insn (insn);
2205 insn && GET_CODE (insn) == CODE_LABEL;
2206 insn = next_nonnote_insn (insn))
2208 for (i = 0; i < n_basic_blocks; i++)
2209 if (insn == basic_block_head[i])
2216 /* Called when INSN is being moved from a location near the target of a jump.
2217 We leave a marker of the form (use (INSN)) immediately in front
2218 of WHERE for mark_target_live_regs. These markers will be deleted when
2221 We used to try to update the live status of registers if WHERE is at
2222 the start of a basic block, but that can't work since we may remove a
2223 BARRIER in relax_delay_slots. */
2226 update_block (insn, where)
2232 /* Ignore if this was in a delay slot and it came from the target of
2234 if (INSN_FROM_TARGET_P (insn))
2237 emit_insn_before (gen_rtx (USE, VOIDmode, insn), where);
2239 /* INSN might be making a value live in a block where it didn't use to
2240 be. So recompute liveness information for this block. */
2242 b = find_basic_block (insn);
2247 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
2248 the basic block containing the jump. */
2251 reorg_redirect_jump (jump, nlabel)
2255 int b = find_basic_block (jump);
2260 return redirect_jump (jump, nlabel);
2263 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
2264 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
2265 that reference values used in INSN. If we find one, then we move the
2266 REG_DEAD note to INSN.
2268 This is needed to handle the case where an later insn (after INSN) has a
2269 REG_DEAD note for a register used by INSN, and this later insn subsequently
2270 gets moved before a CODE_LABEL because it is a redundant insn. In this
2271 case, mark_target_live_regs may be confused into thinking the register
2272 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
2275 update_reg_dead_notes (insn, delayed_insn)
2276 rtx insn, delayed_insn;
2280 for (p = next_nonnote_insn (insn); p != delayed_insn;
2281 p = next_nonnote_insn (p))
2282 for (link = REG_NOTES (p); link; link = next)
2284 next = XEXP (link, 1);
2286 if (REG_NOTE_KIND (link) != REG_DEAD
2287 || GET_CODE (XEXP (link, 0)) != REG)
2290 if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
2292 /* Move the REG_DEAD note from P to INSN. */
2293 remove_note (p, link);
2294 XEXP (link, 1) = REG_NOTES (insn);
2295 REG_NOTES (insn) = link;
2300 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
2302 This handles the case of udivmodXi4 instructions which optimize their
2303 output depending on whether any REG_UNUSED notes are present.
2304 we must make sure that INSN calculates as many results as REDUNDANT_INSN
2308 update_reg_unused_notes (insn, redundant_insn)
2309 rtx insn, redundant_insn;
2313 for (link = REG_NOTES (insn); link; link = next)
2315 next = XEXP (link, 1);
2317 if (REG_NOTE_KIND (link) != REG_UNUSED
2318 || GET_CODE (XEXP (link, 0)) != REG)
2321 if (! find_regno_note (redundant_insn, REG_UNUSED,
2322 REGNO (XEXP (link, 0))))
2323 remove_note (insn, link);
2327 /* Marks registers possibly live at the current place being scanned by
2328 mark_target_live_regs. Used only by next two function. */
2330 static HARD_REG_SET current_live_regs;
2332 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
2333 Also only used by the next two functions. */
2335 static HARD_REG_SET pending_dead_regs;
2337 /* Utility function called from mark_target_live_regs via note_stores.
2338 It deadens any CLOBBERed registers and livens any SET registers. */
2341 update_live_status (dest, x)
2345 int first_regno, last_regno;
2348 if (GET_CODE (dest) != REG
2349 && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
2352 if (GET_CODE (dest) == SUBREG)
2353 first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
2355 first_regno = REGNO (dest);
2357 last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
2359 if (GET_CODE (x) == CLOBBER)
2360 for (i = first_regno; i < last_regno; i++)
2361 CLEAR_HARD_REG_BIT (current_live_regs, i);
2363 for (i = first_regno; i < last_regno; i++)
2365 SET_HARD_REG_BIT (current_live_regs, i);
2366 CLEAR_HARD_REG_BIT (pending_dead_regs, i);
2370 /* Similar to next_insn, but ignores insns in the delay slots of
2371 an annulled branch. */
2374 next_insn_no_annul (insn)
2379 /* If INSN is an annulled branch, skip any insns from the target
2381 if (INSN_ANNULLED_BRANCH_P (insn)
2382 && NEXT_INSN (PREV_INSN (insn)) != insn)
2383 while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
2384 insn = NEXT_INSN (insn);
2386 insn = NEXT_INSN (insn);
2387 if (insn && GET_CODE (insn) == INSN
2388 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2389 insn = XVECEXP (PATTERN (insn), 0, 0);
2395 /* Set the resources that are live at TARGET.
2397 If TARGET is zero, we refer to the end of the current function and can
2398 return our precomputed value.
2400 Otherwise, we try to find out what is live by consulting the basic block
2401 information. This is tricky, because we must consider the actions of
2402 reload and jump optimization, which occur after the basic block information
2405 Accordingly, we proceed as follows::
2407 We find the previous BARRIER and look at all immediately following labels
2408 (with no intervening active insns) to see if any of them start a basic
2409 block. If we hit the start of the function first, we use block 0.
2411 Once we have found a basic block and a corresponding first insns, we can
2412 accurately compute the live status from basic_block_live_regs and
2413 reg_renumber. (By starting at a label following a BARRIER, we are immune
2414 to actions taken by reload and jump.) Then we scan all insns between
2415 that point and our target. For each CLOBBER (or for call-clobbered regs
2416 when we pass a CALL_INSN), mark the appropriate registers are dead. For
2417 a SET, mark them as live.
2419 We have to be careful when using REG_DEAD notes because they are not
2420 updated by such things as find_equiv_reg. So keep track of registers
2421 marked as dead that haven't been assigned to, and mark them dead at the
2422 next CODE_LABEL since reload and jump won't propagate values across labels.
2424 If we cannot find the start of a basic block (should be a very rare
2425 case, if it can happen at all), mark everything as potentially live.
2427 Next, scan forward from TARGET looking for things set or clobbered
2428 before they are used. These are not live.
2430 Because we can be called many times on the same target, save our results
2431 in a hash table indexed by INSN_UID. */
2434 mark_target_live_regs (target, res)
2436 struct resources *res;
2440 struct target_info *tinfo;
2444 HARD_REG_SET scratch;
2445 struct resources set, needed;
2448 /* Handle end of function. */
2451 *res = end_of_function_needs;
2455 /* We have to assume memory is needed, but the CC isn't. */
2460 /* See if we have computed this value already. */
2461 for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2462 tinfo; tinfo = tinfo->next)
2463 if (tinfo->uid == INSN_UID (target))
2466 /* Start by getting the basic block number. If we have saved information,
2467 we can get it from there unless the insn at the start of the basic block
2468 has been deleted. */
2469 if (tinfo && tinfo->block != -1
2470 && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
2474 b = find_basic_block (target);
2478 /* If the information is up-to-date, use it. Otherwise, we will
2480 if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
2482 COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
2488 /* Allocate a place to put our results and chain it into the
2490 tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
2491 tinfo->uid = INSN_UID (target);
2493 tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2494 target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
2497 CLEAR_HARD_REG_SET (pending_dead_regs);
2499 /* If we found a basic block, get the live registers from it and update
2500 them with anything set or killed between its start and the insn before
2501 TARGET. Otherwise, we must assume everything is live. */
2504 regset regs_live = basic_block_live_at_start[b];
2506 REGSET_ELT_TYPE bit;
2508 rtx start_insn, stop_insn;
2510 /* Compute hard regs live at start of block -- this is the real hard regs
2511 marked live, plus live pseudo regs that have been renumbered to
2515 current_live_regs = *regs_live;
2517 COPY_HARD_REG_SET (current_live_regs, regs_live);
2520 for (offset = 0, i = 0; offset < regset_size; offset++)
2522 if (regs_live[offset] == 0)
2523 i += REGSET_ELT_BITS;
2525 for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
2526 if ((regs_live[offset] & bit)
2527 && (regno = reg_renumber[i]) >= 0)
2529 j < regno + HARD_REGNO_NREGS (regno,
2530 PSEUDO_REGNO_MODE (i));
2532 SET_HARD_REG_BIT (current_live_regs, j);
2535 /* Get starting and ending insn, handling the case where each might
2537 start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2540 if (GET_CODE (start_insn) == INSN
2541 && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2542 start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2544 if (GET_CODE (stop_insn) == INSN
2545 && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2546 stop_insn = next_insn (PREV_INSN (stop_insn));
2548 for (insn = start_insn; insn != stop_insn;
2549 insn = next_insn_no_annul (insn))
2552 rtx real_insn = insn;
2554 /* If this insn is from the target of a branch, it isn't going to
2555 be used in the sequel. If it is used in both cases, this
2556 test will not be true. */
2557 if (INSN_FROM_TARGET_P (insn))
2560 /* If this insn is a USE made by update_block, we care about the
2562 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2563 && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2564 real_insn = XEXP (PATTERN (insn), 0);
2566 if (GET_CODE (real_insn) == CALL_INSN)
2568 /* CALL clobbers all call-used regs that aren't fixed except
2569 sp, ap, and fp. Do this before setting the result of the
2571 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2572 if (call_used_regs[i]
2573 && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2574 && i != ARG_POINTER_REGNUM
2575 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2576 && i != HARD_FRAME_POINTER_REGNUM
2578 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2579 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2581 #ifdef PIC_OFFSET_TABLE_REGNUM
2582 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2585 CLEAR_HARD_REG_BIT (current_live_regs, i);
2587 /* A CALL_INSN sets any global register live, since it may
2588 have been modified by the call. */
2589 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2591 SET_HARD_REG_BIT (current_live_regs, i);
2594 /* Mark anything killed in an insn to be deadened at the next
2595 label. Ignore USE insns; the only REG_DEAD notes will be for
2596 parameters. But they might be early. A CALL_INSN will usually
2597 clobber registers used for parameters. It isn't worth bothering
2598 with the unlikely case when it won't. */
2599 if ((GET_CODE (real_insn) == INSN
2600 && GET_CODE (PATTERN (real_insn)) != USE
2601 && GET_CODE (PATTERN (real_insn)) != CLOBBER)
2602 || GET_CODE (real_insn) == JUMP_INSN
2603 || GET_CODE (real_insn) == CALL_INSN)
2605 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2606 if (REG_NOTE_KIND (link) == REG_DEAD
2607 && GET_CODE (XEXP (link, 0)) == REG
2608 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2610 int first_regno = REGNO (XEXP (link, 0));
2613 + HARD_REGNO_NREGS (first_regno,
2614 GET_MODE (XEXP (link, 0))));
2616 for (i = first_regno; i < last_regno; i++)
2617 SET_HARD_REG_BIT (pending_dead_regs, i);
2620 note_stores (PATTERN (real_insn), update_live_status);
2622 /* If any registers were unused after this insn, kill them.
2623 These notes will always be accurate. */
2624 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2625 if (REG_NOTE_KIND (link) == REG_UNUSED
2626 && GET_CODE (XEXP (link, 0)) == REG
2627 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2629 int first_regno = REGNO (XEXP (link, 0));
2632 + HARD_REGNO_NREGS (first_regno,
2633 GET_MODE (XEXP (link, 0))));
2635 for (i = first_regno; i < last_regno; i++)
2636 CLEAR_HARD_REG_BIT (current_live_regs, i);
2640 else if (GET_CODE (real_insn) == CODE_LABEL)
2642 /* A label clobbers the pending dead registers since neither
2643 reload nor jump will propagate a value across a label. */
2644 AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2645 CLEAR_HARD_REG_SET (pending_dead_regs);
2648 /* The beginning of the epilogue corresponds to the end of the
2649 RTL chain when there are no epilogue insns. Certain resources
2650 are implicitly required at that point. */
2651 else if (GET_CODE (real_insn) == NOTE
2652 && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG)
2653 IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs);
2656 COPY_HARD_REG_SET (res->regs, current_live_regs);
2658 tinfo->bb_tick = bb_ticks[b];
2661 /* We didn't find the start of a basic block. Assume everything
2662 in use. This should happen only extremely rarely. */
2663 SET_HARD_REG_SET (res->regs);
2665 /* Now step forward from TARGET looking for registers that are set before
2666 they are used. These are dead. If we pass a label, any pending dead
2667 registers that weren't yet used can be made dead. Stop when we pass a
2668 conditional JUMP_INSN; follow the first few unconditional branches. */
2670 CLEAR_RESOURCE (&set);
2671 CLEAR_RESOURCE (&needed);
2673 for (insn = target; insn; insn = next)
2675 rtx this_jump_insn = insn;
2677 next = NEXT_INSN (insn);
2678 switch (GET_CODE (insn))
2681 AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2682 AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2683 CLEAR_HARD_REG_SET (pending_dead_regs);
2691 if (GET_CODE (PATTERN (insn)) == USE)
2693 /* If INSN is a USE made by update_block, we care about the
2694 underlying insn. Any registers set by the underlying insn
2695 are live since the insn is being done somewhere else. */
2696 if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2697 mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1);
2699 /* All other USE insns are to be ignored. */
2702 else if (GET_CODE (PATTERN (insn)) == CLOBBER)
2704 else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2706 /* An unconditional jump can be used to fill the delay slot
2707 of a call, so search for a JUMP_INSN in any position. */
2708 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2710 this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
2711 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2717 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2719 if (jump_count++ < 10
2720 && (simplejump_p (this_jump_insn)
2721 || GET_CODE (PATTERN (this_jump_insn)) == RETURN))
2723 next = next_active_insn (JUMP_LABEL (this_jump_insn));
2727 jump_target = JUMP_LABEL (this_jump_insn);
2734 mark_referenced_resources (insn, &needed, 1);
2735 mark_set_resources (insn, &set, 0, 1);
2737 COPY_HARD_REG_SET (scratch, set.regs);
2738 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2739 AND_COMPL_HARD_REG_SET (res->regs, scratch);
2742 /* If we hit an unconditional branch, we have another way of finding out
2743 what is live: we can see what is live at the branch target and include
2744 anything used but not set before the branch. The only things that are
2745 live are those that are live using the above test and the test below.
2747 Don't try this if we expired our jump count above, since that would
2748 mean there may be an infinite loop in the function being compiled. */
2750 if (jump_insn && jump_count < 10)
2752 struct resources new_resources;
2753 rtx stop_insn = next_active_insn (jump_insn);
2755 mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2756 CLEAR_RESOURCE (&set);
2757 CLEAR_RESOURCE (&needed);
2759 /* Include JUMP_INSN in the needed registers. */
2760 for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2762 mark_referenced_resources (insn, &needed, 1);
2764 COPY_HARD_REG_SET (scratch, needed.regs);
2765 AND_COMPL_HARD_REG_SET (scratch, set.regs);
2766 IOR_HARD_REG_SET (new_resources.regs, scratch);
2768 mark_set_resources (insn, &set, 0, 1);
2771 AND_HARD_REG_SET (res->regs, new_resources.regs);
2774 COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2777 /* Scan a function looking for insns that need a delay slot and find insns to
2778 put into the delay slot.
2780 NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2781 as calls). We do these first since we don't want jump insns (that are
2782 easier to fill) to get the only insns that could be used for non-jump insns.
2783 When it is zero, only try to fill JUMP_INSNs.
2785 When slots are filled in this manner, the insns (including the
2786 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2787 it is possible to tell whether a delay slot has really been filled
2788 or not. `final' knows how to deal with this, by communicating
2789 through FINAL_SEQUENCE. */
2792 fill_simple_delay_slots (first, non_jumps_p)
2796 register rtx insn, pat, trial, next_trial;
2798 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2799 struct resources needed, set;
2800 register int slots_to_fill, slots_filled;
2803 for (i = 0; i < num_unfilled_slots; i++)
2806 /* Get the next insn to fill. If it has already had any slots assigned,
2807 we can't do anything with it. Maybe we'll improve this later. */
2809 insn = unfilled_slots_base[i];
2811 || INSN_DELETED_P (insn)
2812 || (GET_CODE (insn) == INSN
2813 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2814 || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2815 || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2818 if (GET_CODE (insn) == JUMP_INSN)
2819 flags = get_jump_flags (insn, JUMP_LABEL (insn));
2821 flags = get_jump_flags (insn, NULL_RTX);
2822 slots_to_fill = num_delay_slots (insn);
2823 if (slots_to_fill == 0)
2826 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2827 says how many. After initialization, first try optimizing
2830 nop add %o7,.-L1,%o7
2834 If this case applies, the delay slot of the call is filled with
2835 the unconditional jump. This is done first to avoid having the
2836 delay slot of the call filled in the backward scan. Also, since
2837 the unconditional jump is likely to also have a delay slot, that
2838 insn must exist when it is subsequently scanned.
2840 This is tried on each insn with delay slots as some machines
2841 have insns which perform calls, but are not represented as
2847 if ((trial = next_active_insn (insn))
2848 && GET_CODE (trial) == JUMP_INSN
2849 && simplejump_p (trial)
2850 && eligible_for_delay (insn, slots_filled, trial, flags)
2851 && no_labels_between_p (insn, trial))
2854 delay_list = add_to_delay_list (trial, delay_list);
2855 /* Remove the unconditional jump from consideration for delay slot
2856 filling and unthread it. */
2857 if (unfilled_slots_base[i + 1] == trial)
2858 unfilled_slots_base[i + 1] = 0;
2860 rtx next = NEXT_INSN (trial);
2861 rtx prev = PREV_INSN (trial);
2863 NEXT_INSN (prev) = next;
2865 PREV_INSN (next) = prev;
2869 /* Now, scan backwards from the insn to search for a potential
2870 delay-slot candidate. Stop searching when a label or jump is hit.
2872 For each candidate, if it is to go into the delay slot (moved
2873 forward in execution sequence), it must not need or set any resources
2874 that were set by later insns and must not set any resources that
2875 are needed for those insns.
2877 The delay slot insn itself sets resources unless it is a call
2878 (in which case the called routine, not the insn itself, is doing
2881 if (slots_filled < slots_to_fill)
2883 CLEAR_RESOURCE (&needed);
2884 CLEAR_RESOURCE (&set);
2885 mark_set_resources (insn, &set, 0, 0);
2886 mark_referenced_resources (insn, &needed, 0);
2888 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2891 next_trial = prev_nonnote_insn (trial);
2893 /* This must be an INSN or CALL_INSN. */
2894 pat = PATTERN (trial);
2896 /* USE and CLOBBER at this level was just for flow; ignore it. */
2897 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2900 /* Check for resource conflict first, to avoid unnecessary
2902 if (! insn_references_resource_p (trial, &set, 1)
2903 && ! insn_sets_resource_p (trial, &set, 1)
2904 && ! insn_sets_resource_p (trial, &needed, 1)
2906 /* Can't separate set of cc0 from its use. */
2907 && ! (reg_mentioned_p (cc0_rtx, pat)
2908 && ! sets_cc0_p (cc0_rtx, pat))
2912 trial = try_split (pat, trial, 1);
2913 next_trial = prev_nonnote_insn (trial);
2914 if (eligible_for_delay (insn, slots_filled, trial, flags))
2916 /* In this case, we are searching backward, so if we
2917 find insns to put on the delay list, we want
2918 to put them at the head, rather than the
2919 tail, of the list. */
2921 update_reg_dead_notes (trial, insn);
2922 delay_list = gen_rtx (INSN_LIST, VOIDmode,
2924 update_block (trial, trial);
2925 delete_insn (trial);
2926 if (slots_to_fill == ++slots_filled)
2932 mark_set_resources (trial, &set, 0, 1);
2933 mark_referenced_resources (trial, &needed, 1);
2937 /* If all needed slots haven't been filled, we come here. */
2939 /* Try to optimize case of jumping around a single insn. */
2940 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2941 if (slots_filled != slots_to_fill
2943 && GET_CODE (insn) == JUMP_INSN
2944 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
2946 delay_list = optimize_skip (insn);
2952 /* Try to get insns from beyond the insn needing the delay slot.
2953 These insns can neither set or reference resources set in insns being
2954 skipped, cannot set resources in the insn being skipped, and, if this
2955 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2956 call might not return).
2958 If this is a conditional jump, see if it merges back to us early
2959 enough for us to pick up insns from the merge point. Don't do
2960 this if there is another branch to our label unless we pass all of
2963 Another similar merge is if we jump to the same place that a
2964 later unconditional jump branches to. In that case, we don't
2965 care about the number of uses of our label. */
2967 if (slots_filled != slots_to_fill
2968 && (GET_CODE (insn) != JUMP_INSN
2969 || ((condjump_p (insn) || condjump_in_parallel_p (insn))
2970 && ! simplejump_p (insn)
2971 && JUMP_LABEL (insn) != 0)))
2974 int maybe_never = 0;
2975 int passed_label = 0;
2977 struct resources needed_at_jump;
2979 CLEAR_RESOURCE (&needed);
2980 CLEAR_RESOURCE (&set);
2982 if (GET_CODE (insn) == CALL_INSN)
2984 mark_set_resources (insn, &set, 0, 1);
2985 mark_referenced_resources (insn, &needed, 1);
2990 mark_set_resources (insn, &set, 0, 1);
2991 mark_referenced_resources (insn, &needed, 1);
2992 if (GET_CODE (insn) == JUMP_INSN)
2994 /* Get our target and show how many more uses we want to
2995 see before we hit the label. */
2996 target = JUMP_LABEL (insn);
2997 target_uses = LABEL_NUSES (target) - 1;
3002 for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
3004 rtx pat, trial_delay;
3006 next_trial = next_nonnote_insn (trial);
3008 if (GET_CODE (trial) == CODE_LABEL)
3012 /* If this is our target, see if we have seen all its uses.
3013 If so, indicate we have passed our target and ignore it.
3014 All other labels cause us to stop our search. */
3015 if (trial == target && target_uses == 0)
3023 else if (GET_CODE (trial) == BARRIER)
3026 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
3027 pat = PATTERN (trial);
3029 /* Stand-alone USE and CLOBBER are just for flow. */
3030 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3033 /* If this already has filled delay slots, get the insn needing
3035 if (GET_CODE (pat) == SEQUENCE)
3036 trial_delay = XVECEXP (pat, 0, 0);
3038 trial_delay = trial;
3040 /* If this is a jump insn to our target, indicate that we have
3041 seen another jump to it. If we aren't handling a conditional
3042 jump, stop our search. Otherwise, compute the needs at its
3043 target and add them to NEEDED. */
3044 if (GET_CODE (trial_delay) == JUMP_INSN)
3048 else if (JUMP_LABEL (trial_delay) == target)
3052 mark_target_live_regs
3053 (next_active_insn (JUMP_LABEL (trial_delay)),
3055 needed.memory |= needed_at_jump.memory;
3056 IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
3060 /* See if we have a resource problem before we try to
3063 && GET_CODE (pat) != SEQUENCE
3064 && ! insn_references_resource_p (trial, &set, 1)
3065 && ! insn_sets_resource_p (trial, &set, 1)
3066 && ! insn_sets_resource_p (trial, &needed, 1)
3068 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
3070 && ! (maybe_never && may_trap_p (pat))
3071 && (trial = try_split (pat, trial, 0))
3072 && eligible_for_delay (insn, slots_filled, trial, flags))
3074 next_trial = next_nonnote_insn (trial);
3075 delay_list = add_to_delay_list (trial, delay_list);
3078 if (reg_mentioned_p (cc0_rtx, pat))
3079 link_cc0_insns (trial);
3083 update_block (trial, trial);
3084 delete_insn (trial);
3085 if (slots_to_fill == ++slots_filled)
3090 mark_set_resources (trial, &set, 0, 1);
3091 mark_referenced_resources (trial, &needed, 1);
3093 /* Ensure we don't put insns between the setting of cc and the
3094 comparison by moving a setting of cc into an earlier delay
3095 slot since these insns could clobber the condition code. */
3098 /* If this is a call or jump, we might not get here. */
3099 if (GET_CODE (trial) == CALL_INSN
3100 || GET_CODE (trial) == JUMP_INSN)
3104 /* If there are slots left to fill and our search was stopped by an
3105 unconditional branch, try the insn at the branch target. We can
3106 redirect the branch if it works. */
3107 if (slots_to_fill != slots_filled
3109 && GET_CODE (trial) == JUMP_INSN
3110 && simplejump_p (trial)
3111 && (target == 0 || JUMP_LABEL (trial) == target)
3112 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
3113 && ! (GET_CODE (next_trial) == INSN
3114 && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
3115 && ! insn_references_resource_p (next_trial, &set, 1)
3116 && ! insn_sets_resource_p (next_trial, &set, 1)
3117 && ! insn_sets_resource_p (next_trial, &needed, 1)
3119 && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
3121 && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
3122 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
3123 && eligible_for_delay (insn, slots_filled, next_trial, flags))
3125 rtx new_label = next_active_insn (next_trial);
3128 new_label = get_label_before (new_label);
3130 new_label = find_end_label ();
3133 = add_to_delay_list (copy_rtx (next_trial), delay_list);
3135 reorg_redirect_jump (trial, new_label);
3137 /* If we merged because we both jumped to the same place,
3138 redirect the original insn also. */
3140 reorg_redirect_jump (insn, new_label);
3145 unfilled_slots_base[i]
3146 = emit_delay_sequence (insn, delay_list,
3147 slots_filled, slots_to_fill);
3149 if (slots_to_fill == slots_filled)
3150 unfilled_slots_base[i] = 0;
3152 note_delay_statistics (slots_filled, 0);
3155 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3156 /* See if the epilogue needs any delay slots. Try to fill them if so.
3157 The only thing we can do is scan backwards from the end of the
3158 function. If we did this in a previous pass, it is incorrect to do it
3160 if (current_function_epilogue_delay_list)
3163 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
3164 if (slots_to_fill == 0)
3168 CLEAR_RESOURCE (&set);
3170 /* The frame pointer and stack pointer are needed at the beginning of
3171 the epilogue, so instructions setting them can not be put in the
3172 epilogue delay slot. However, everything else needed at function
3173 end is safe, so we don't want to use end_of_function_needs here. */
3174 CLEAR_RESOURCE (&needed);
3175 if (frame_pointer_needed)
3177 SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
3178 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3179 SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
3181 #ifdef EXIT_IGNORE_STACK
3182 if (! EXIT_IGNORE_STACK)
3184 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3187 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3189 for (trial = get_last_insn (); ! stop_search_p (trial, 1);
3190 trial = PREV_INSN (trial))
3192 if (GET_CODE (trial) == NOTE)
3194 pat = PATTERN (trial);
3195 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3198 if (! insn_references_resource_p (trial, &set, 1)
3199 && ! insn_sets_resource_p (trial, &needed, 1)
3200 && ! insn_sets_resource_p (trial, &set, 1)
3202 /* Don't want to mess with cc0 here. */
3203 && ! reg_mentioned_p (cc0_rtx, pat)
3207 trial = try_split (pat, trial, 1);
3208 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
3210 /* Here as well we are searching backward, so put the
3211 insns we find on the head of the list. */
3213 current_function_epilogue_delay_list
3214 = gen_rtx (INSN_LIST, VOIDmode, trial,
3215 current_function_epilogue_delay_list);
3216 mark_referenced_resources (trial, &end_of_function_needs, 1);
3217 update_block (trial, trial);
3218 delete_insn (trial);
3220 /* Clear deleted bit so final.c will output the insn. */
3221 INSN_DELETED_P (trial) = 0;
3223 if (slots_to_fill == ++slots_filled)
3229 mark_set_resources (trial, &set, 0, 1);
3230 mark_referenced_resources (trial, &needed, 1);
3233 note_delay_statistics (slots_filled, 0);
3237 /* Try to find insns to place in delay slots.
3239 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
3240 or is an unconditional branch if CONDITION is const_true_rtx.
3241 *PSLOTS_FILLED is updated with the number of slots that we have filled.
3243 THREAD is a flow-of-control, either the insns to be executed if the
3244 branch is true or if the branch is false, THREAD_IF_TRUE says which.
3246 OPPOSITE_THREAD is the thread in the opposite direction. It is used
3247 to see if any potential delay slot insns set things needed there.
3249 LIKELY is non-zero if it is extremely likely that the branch will be
3250 taken and THREAD_IF_TRUE is set. This is used for the branch at the
3251 end of a loop back up to the top.
3253 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
3254 thread. I.e., it is the fallthrough code of our jump or the target of the
3255 jump when we are the only jump going there.
3257 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
3258 case, we can only take insns from the head of the thread for our delay
3259 slot. We then adjust the jump to point after the insns we have taken. */
3262 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
3263 thread_if_true, own_thread, own_opposite_thread,
3264 slots_to_fill, pslots_filled)
3267 rtx thread, opposite_thread;
3270 int own_thread, own_opposite_thread;
3271 int slots_to_fill, *pslots_filled;
3275 struct resources opposite_needed, set, needed;
3281 /* Validate our arguments. */
3282 if ((condition == const_true_rtx && ! thread_if_true)
3283 || (! own_thread && ! thread_if_true))
3286 flags = get_jump_flags (insn, JUMP_LABEL (insn));
3288 /* If our thread is the end of subroutine, we can't get any delay
3293 /* If this is an unconditional branch, nothing is needed at the
3294 opposite thread. Otherwise, compute what is needed there. */
3295 if (condition == const_true_rtx)
3296 CLEAR_RESOURCE (&opposite_needed);
3298 mark_target_live_regs (opposite_thread, &opposite_needed);
3300 /* If the insn at THREAD can be split, do it here to avoid having to
3301 update THREAD and NEW_THREAD if it is done in the loop below. Also
3302 initialize NEW_THREAD. */
3304 new_thread = thread = try_split (PATTERN (thread), thread, 0);
3306 /* Scan insns at THREAD. We are looking for an insn that can be removed
3307 from THREAD (it neither sets nor references resources that were set
3308 ahead of it and it doesn't set anything needs by the insns ahead of
3309 it) and that either can be placed in an annulling insn or aren't
3310 needed at OPPOSITE_THREAD. */
3312 CLEAR_RESOURCE (&needed);
3313 CLEAR_RESOURCE (&set);
3315 /* If we do not own this thread, we must stop as soon as we find
3316 something that we can't put in a delay slot, since all we can do
3317 is branch into THREAD at a later point. Therefore, labels stop
3318 the search if this is not the `true' thread. */
3320 for (trial = thread;
3321 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
3322 trial = next_nonnote_insn (trial))
3326 /* If we have passed a label, we no longer own this thread. */
3327 if (GET_CODE (trial) == CODE_LABEL)
3333 pat = PATTERN (trial);
3334 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3337 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
3338 don't separate or copy insns that set and use CC0. */
3339 if (! insn_references_resource_p (trial, &set, 1)
3340 && ! insn_sets_resource_p (trial, &set, 1)
3341 && ! insn_sets_resource_p (trial, &needed, 1)
3343 && ! (reg_mentioned_p (cc0_rtx, pat)
3344 && (! own_thread || ! sets_cc0_p (pat)))
3350 /* If TRIAL is redundant with some insn before INSN, we don't
3351 actually need to add it to the delay list; we can merely pretend
3353 if (prior_insn = redundant_insn (trial, insn, delay_list))
3357 update_block (trial, thread);
3358 if (trial == thread)
3360 thread = next_active_insn (thread);
3361 if (new_thread == trial)
3362 new_thread = thread;
3365 delete_insn (trial);
3369 update_reg_unused_notes (prior_insn, trial);
3370 new_thread = next_active_insn (trial);
3376 /* There are two ways we can win: If TRIAL doesn't set anything
3377 needed at the opposite thread and can't trap, or if it can
3378 go into an annulled delay slot. */
3379 if (condition == const_true_rtx
3380 || (! insn_sets_resource_p (trial, &opposite_needed, 1)
3381 && ! may_trap_p (pat)))
3384 trial = try_split (pat, trial, 0);
3385 if (new_thread == old_trial)
3387 if (thread == old_trial)
3389 pat = PATTERN (trial);
3390 if (eligible_for_delay (insn, *pslots_filled, trial, flags))
3394 #ifdef ANNUL_IFTRUE_SLOTS
3397 #ifdef ANNUL_IFFALSE_SLOTS
3403 trial = try_split (pat, trial, 0);
3404 if (new_thread == old_trial)
3406 pat = PATTERN (trial);
3408 ? eligible_for_annul_false (insn, *pslots_filled, trial, flags)
3409 : eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
3417 if (reg_mentioned_p (cc0_rtx, pat))
3418 link_cc0_insns (trial);
3421 /* If we own this thread, delete the insn. If this is the
3422 destination of a branch, show that a basic block status
3423 may have been updated. In any case, mark the new
3424 starting point of this thread. */
3427 update_block (trial, thread);
3428 delete_insn (trial);
3431 new_thread = next_active_insn (trial);
3433 temp = own_thread ? trial : copy_rtx (trial);
3435 INSN_FROM_TARGET_P (temp) = 1;
3437 delay_list = add_to_delay_list (temp, delay_list);
3439 if (slots_to_fill == ++(*pslots_filled))
3441 /* Even though we have filled all the slots, we
3442 may be branching to a location that has a
3443 redundant insn. Skip any if so. */
3444 while (new_thread && ! own_thread
3445 && ! insn_sets_resource_p (new_thread, &set, 1)
3446 && ! insn_sets_resource_p (new_thread, &needed, 1)
3447 && ! insn_references_resource_p (new_thread,
3449 && redundant_insn (new_thread, insn, delay_list))
3450 new_thread = next_active_insn (new_thread);
3459 /* This insn can't go into a delay slot. */
3461 mark_set_resources (trial, &set, 0, 1);
3462 mark_referenced_resources (trial, &needed, 1);
3464 /* Ensure we don't put insns between the setting of cc and the comparison
3465 by moving a setting of cc into an earlier delay slot since these insns
3466 could clobber the condition code. */
3469 /* If this insn is a register-register copy and the next insn has
3470 a use of our destination, change it to use our source. That way,
3471 it will become a candidate for our delay slot the next time
3472 through this loop. This case occurs commonly in loops that
3475 We could check for more complex cases than those tested below,
3476 but it doesn't seem worth it. It might also be a good idea to try
3477 to swap the two insns. That might do better.
3479 We can't do this if the next insn modifies our destination, because
3480 that would make the replacement into the insn invalid. We also can't
3481 do this if it modifies our source, because it might be an earlyclobber
3482 operand. This latter test also prevents updating the contents of
3485 if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
3486 && GET_CODE (SET_SRC (pat)) == REG
3487 && GET_CODE (SET_DEST (pat)) == REG)
3489 rtx next = next_nonnote_insn (trial);
3491 if (next && GET_CODE (next) == INSN
3492 && GET_CODE (PATTERN (next)) != USE
3493 && ! reg_set_p (SET_DEST (pat), next)
3494 && ! reg_set_p (SET_SRC (pat), next)
3495 && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
3496 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
3500 /* If we stopped on a branch insn that has delay slots, see if we can
3501 steal some of the insns in those slots. */
3502 if (trial && GET_CODE (trial) == INSN
3503 && GET_CODE (PATTERN (trial)) == SEQUENCE
3504 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
3506 /* If this is the `true' thread, we will want to follow the jump,
3507 so we can only do this if we have taken everything up to here. */
3508 if (thread_if_true && trial == new_thread)
3510 = steal_delay_list_from_target (insn, condition, PATTERN (trial),
3511 delay_list, &set, &needed,
3512 &opposite_needed, slots_to_fill,
3513 pslots_filled, &must_annul,
3515 else if (! thread_if_true)
3517 = steal_delay_list_from_fallthrough (insn, condition,
3519 delay_list, &set, &needed,
3520 &opposite_needed, slots_to_fill,
3521 pslots_filled, &must_annul);
3524 /* If we haven't found anything for this delay slot and it is very
3525 likely that the branch will be taken, see if the insn at our target
3526 increments or decrements a register with an increment that does not
3527 depend on the destination register. If so, try to place the opposite
3528 arithmetic insn after the jump insn and put the arithmetic insn in the
3529 delay slot. If we can't do this, return. */
3530 if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
3532 rtx pat = PATTERN (new_thread);
3537 pat = PATTERN (trial);
3539 if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
3540 || ! eligible_for_delay (insn, 0, trial, flags))
3543 dest = SET_DEST (pat), src = SET_SRC (pat);
3544 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
3545 && rtx_equal_p (XEXP (src, 0), dest)
3546 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
3548 rtx other = XEXP (src, 1);
3552 /* If this is a constant adjustment, use the same code with
3553 the negated constant. Otherwise, reverse the sense of the
3555 if (GET_CODE (other) == CONST_INT)
3556 new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest,
3557 negate_rtx (GET_MODE (src), other));
3559 new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS,
3560 GET_MODE (src), dest, other);
3562 ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith),
3565 if (recog_memoized (ninsn) < 0
3566 || (insn_extract (ninsn),
3567 ! constrain_operands (INSN_CODE (ninsn), 1)))
3569 delete_insn (ninsn);
3575 update_block (trial, thread);
3576 delete_insn (trial);
3579 new_thread = next_active_insn (trial);
3581 ninsn = own_thread ? trial : copy_rtx (trial);
3583 INSN_FROM_TARGET_P (ninsn) = 1;
3585 delay_list = add_to_delay_list (ninsn, NULL_RTX);
3590 if (delay_list && must_annul)
3591 INSN_ANNULLED_BRANCH_P (insn) = 1;
3593 /* If we are to branch into the middle of this thread, find an appropriate
3594 label or make a new one if none, and redirect INSN to it. If we hit the
3595 end of the function, use the end-of-function label. */
3596 if (new_thread != thread)
3600 if (! thread_if_true)
3603 if (new_thread && GET_CODE (new_thread) == JUMP_INSN
3604 && (simplejump_p (new_thread)
3605 || GET_CODE (PATTERN (new_thread)) == RETURN)
3606 && redirect_with_delay_list_safe_p (insn,
3607 JUMP_LABEL (new_thread),
3609 new_thread = follow_jumps (JUMP_LABEL (new_thread));
3611 if (new_thread == 0)
3612 label = find_end_label ();
3613 else if (GET_CODE (new_thread) == CODE_LABEL)
3616 label = get_label_before (new_thread);
3618 reorg_redirect_jump (insn, label);
3624 /* Make another attempt to find insns to place in delay slots.
3626 We previously looked for insns located in front of the delay insn
3627 and, for non-jump delay insns, located behind the delay insn.
3629 Here only try to schedule jump insns and try to move insns from either
3630 the target or the following insns into the delay slot. If annulling is
3631 supported, we will be likely to do this. Otherwise, we can do this only
3635 fill_eager_delay_slots (first)
3640 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3642 for (i = 0; i < num_unfilled_slots; i++)
3645 rtx target_label, insn_at_target, fallthrough_insn;
3648 int own_fallthrough;
3649 int prediction, slots_to_fill, slots_filled;
3651 insn = unfilled_slots_base[i];
3653 || INSN_DELETED_P (insn)
3654 || GET_CODE (insn) != JUMP_INSN
3655 || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
3658 slots_to_fill = num_delay_slots (insn);
3659 if (slots_to_fill == 0)
3663 target_label = JUMP_LABEL (insn);
3664 condition = get_branch_condition (insn, target_label);
3669 /* Get the next active fallthough and target insns and see if we own
3670 them. Then see whether the branch is likely true. We don't need
3671 to do a lot of this for unconditional branches. */
3673 insn_at_target = next_active_insn (target_label);
3674 own_target = own_thread_p (target_label, target_label, 0);
3676 if (condition == const_true_rtx)
3678 own_fallthrough = 0;
3679 fallthrough_insn = 0;
3684 fallthrough_insn = next_active_insn (insn);
3685 own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
3686 prediction = mostly_true_jump (insn, condition);
3689 /* If this insn is expected to branch, first try to get insns from our
3690 target, then our fallthrough insns. If it is not, expected to branch,
3691 try the other order. */
3696 = fill_slots_from_thread (insn, condition, insn_at_target,
3697 fallthrough_insn, prediction == 2, 1,
3698 own_target, own_fallthrough,
3699 slots_to_fill, &slots_filled);
3701 if (delay_list == 0 && own_fallthrough)
3703 /* Even though we didn't find anything for delay slots,
3704 we might have found a redundant insn which we deleted
3705 from the thread that was filled. So we have to recompute
3706 the next insn at the target. */
3707 target_label = JUMP_LABEL (insn);
3708 insn_at_target = next_active_insn (target_label);
3711 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3712 insn_at_target, 0, 0,
3713 own_fallthrough, own_target,
3714 slots_to_fill, &slots_filled);
3719 if (own_fallthrough)
3721 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3722 insn_at_target, 0, 0,
3723 own_fallthrough, own_target,
3724 slots_to_fill, &slots_filled);
3726 if (delay_list == 0)
3728 = fill_slots_from_thread (insn, condition, insn_at_target,
3729 next_active_insn (insn), 0, 1,
3730 own_target, own_fallthrough,
3731 slots_to_fill, &slots_filled);
3735 unfilled_slots_base[i]
3736 = emit_delay_sequence (insn, delay_list,
3737 slots_filled, slots_to_fill);
3739 if (slots_to_fill == slots_filled)
3740 unfilled_slots_base[i] = 0;
3742 note_delay_statistics (slots_filled, 1);
3746 /* Once we have tried two ways to fill a delay slot, make a pass over the
3747 code to try to improve the results and to do such things as more jump
3751 relax_delay_slots (first)
3754 register rtx insn, next, pat;
3755 register rtx trial, delay_insn, target_label;
3757 /* Look at every JUMP_INSN and see if we can improve it. */
3758 for (insn = first; insn; insn = next)
3762 next = next_active_insn (insn);
3764 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3765 the next insn, or jumps to a label that is not the last of a
3766 group of consecutive labels. */
3767 if (GET_CODE (insn) == JUMP_INSN
3768 && (condjump_p (insn) || condjump_in_parallel_p (insn))
3769 && (target_label = JUMP_LABEL (insn)) != 0)
3771 target_label = follow_jumps (target_label);
3772 target_label = prev_label (next_active_insn (target_label));
3774 if (target_label == 0)
3775 target_label = find_end_label ();
3777 if (next_active_insn (target_label) == next
3778 && ! condjump_in_parallel_p (insn))
3784 if (target_label != JUMP_LABEL (insn))
3785 reorg_redirect_jump (insn, target_label);
3787 /* See if this jump branches around a unconditional jump.
3788 If so, invert this jump and point it to the target of the
3790 if (next && GET_CODE (next) == JUMP_INSN
3791 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3792 && next_active_insn (target_label) == next_active_insn (next)
3793 && no_labels_between_p (insn, next))
3795 rtx label = JUMP_LABEL (next);
3797 /* Be careful how we do this to avoid deleting code or
3798 labels that are momentarily dead. See similar optimization
3801 We also need to ensure we properly handle the case when
3802 invert_jump fails. */
3804 ++LABEL_NUSES (target_label);
3806 ++LABEL_NUSES (label);
3808 if (invert_jump (insn, label))
3815 --LABEL_NUSES (label);
3817 if (--LABEL_NUSES (target_label) == 0)
3818 delete_insn (target_label);
3824 /* If this is an unconditional jump and the previous insn is a
3825 conditional jump, try reversing the condition of the previous
3826 insn and swapping our targets. The next pass might be able to
3829 Don't do this if we expect the conditional branch to be true, because
3830 we would then be making the more common case longer. */
3832 if (GET_CODE (insn) == JUMP_INSN
3833 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3834 && (other = prev_active_insn (insn)) != 0
3835 && (condjump_p (other) || condjump_in_parallel_p (other))
3836 && no_labels_between_p (other, insn)
3837 && 0 < mostly_true_jump (other,
3838 get_branch_condition (other,
3839 JUMP_LABEL (other))))
3841 rtx other_target = JUMP_LABEL (other);
3842 target_label = JUMP_LABEL (insn);
3844 /* Increment the count of OTHER_TARGET, so it doesn't get deleted
3845 as we move the label. */
3847 ++LABEL_NUSES (other_target);
3849 if (invert_jump (other, target_label))
3850 reorg_redirect_jump (insn, other_target);
3853 --LABEL_NUSES (other_target);
3856 /* Now look only at cases where we have filled a delay slot. */
3857 if (GET_CODE (insn) != INSN
3858 || GET_CODE (PATTERN (insn)) != SEQUENCE)
3861 pat = PATTERN (insn);
3862 delay_insn = XVECEXP (pat, 0, 0);
3864 /* See if the first insn in the delay slot is redundant with some
3865 previous insn. Remove it from the delay slot if so; then set up
3866 to reprocess this insn. */
3867 if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
3869 delete_from_delay_slot (XVECEXP (pat, 0, 1));
3870 next = prev_active_insn (next);
3874 /* Now look only at the cases where we have a filled JUMP_INSN. */
3875 if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3876 || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
3877 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
3880 target_label = JUMP_LABEL (delay_insn);
3884 /* If this jump goes to another unconditional jump, thread it, but
3885 don't convert a jump into a RETURN here. */
3886 trial = follow_jumps (target_label);
3887 /* We use next_real_insn instead of next_active_insn, so that
3888 the special USE insns emitted by reorg won't be ignored.
3889 If they are ignored, then they will get deleted if target_label
3890 is now unreachable, and that would cause mark_target_live_regs
3892 trial = prev_label (next_real_insn (trial));
3893 if (trial == 0 && target_label != 0)
3894 trial = find_end_label ();
3896 if (trial != target_label
3897 && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
3899 reorg_redirect_jump (delay_insn, trial);
3900 target_label = trial;
3903 /* If the first insn at TARGET_LABEL is redundant with a previous
3904 insn, redirect the jump to the following insn process again. */
3905 trial = next_active_insn (target_label);
3906 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3907 && redundant_insn (trial, insn, 0))
3909 trial = next_active_insn (trial);
3911 target_label = find_end_label ();
3913 target_label = get_label_before (trial);
3914 reorg_redirect_jump (delay_insn, target_label);
3919 /* Similarly, if it is an unconditional jump with one insn in its
3920 delay list and that insn is redundant, thread the jump. */
3921 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3922 && XVECLEN (PATTERN (trial), 0) == 2
3923 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3924 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3925 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3926 && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3928 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3929 if (target_label == 0)
3930 target_label = find_end_label ();
3932 if (redirect_with_delay_slots_safe_p (delay_insn, target_label,
3935 reorg_redirect_jump (delay_insn, target_label);
3942 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3943 && prev_active_insn (target_label) == insn
3944 && ! condjump_in_parallel_p (delay_insn)
3946 /* If the last insn in the delay slot sets CC0 for some insn,
3947 various code assumes that it is in a delay slot. We could
3948 put it back where it belonged and delete the register notes,
3949 but it doesn't seem worthwhile in this uncommon case. */
3950 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3951 REG_CC_USER, NULL_RTX)
3957 /* All this insn does is execute its delay list and jump to the
3958 following insn. So delete the jump and just execute the delay
3961 We do this by deleting the INSN containing the SEQUENCE, then
3962 re-emitting the insns separately, and then deleting the jump.
3963 This allows the count of the jump target to be properly
3966 /* Clear the from target bit, since these insns are no longer
3968 for (i = 0; i < XVECLEN (pat, 0); i++)
3969 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3971 trial = PREV_INSN (insn);
3973 emit_insn_after (pat, trial);
3974 delete_scheduled_jump (delay_insn);
3978 /* See if this is an unconditional jump around a single insn which is
3979 identical to the one in its delay slot. In this case, we can just
3980 delete the branch and the insn in its delay slot. */
3981 if (next && GET_CODE (next) == INSN
3982 && prev_label (next_active_insn (next)) == target_label
3983 && simplejump_p (insn)
3984 && XVECLEN (pat, 0) == 2
3985 && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
3991 /* See if this jump (with its delay slots) branches around another
3992 jump (without delay slots). If so, invert this jump and point
3993 it to the target of the second jump. We cannot do this for
3994 annulled jumps, though. Again, don't convert a jump to a RETURN
3996 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3997 && next && GET_CODE (next) == JUMP_INSN
3998 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3999 && next_active_insn (target_label) == next_active_insn (next)
4000 && no_labels_between_p (insn, next))
4002 rtx label = JUMP_LABEL (next);
4003 rtx old_label = JUMP_LABEL (delay_insn);
4006 label = find_end_label ();
4008 if (redirect_with_delay_slots_safe_p (delay_insn, label, insn))
4010 /* Be careful how we do this to avoid deleting code or labels
4011 that are momentarily dead. See similar optimization in
4014 ++LABEL_NUSES (old_label);
4016 if (invert_jump (delay_insn, label))
4020 /* Must update the INSN_FROM_TARGET_P bits now that
4021 the branch is reversed, so that mark_target_live_regs
4022 will handle the delay slot insn correctly. */
4023 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
4025 rtx slot = XVECEXP (PATTERN (insn), 0, i);
4026 INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
4033 if (old_label && --LABEL_NUSES (old_label) == 0)
4034 delete_insn (old_label);
4039 /* If we own the thread opposite the way this insn branches, see if we
4040 can merge its delay slots with following insns. */
4041 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4042 && own_thread_p (NEXT_INSN (insn), 0, 1))
4043 try_merge_delay_insns (insn, next);
4044 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4045 && own_thread_p (target_label, target_label, 0))
4046 try_merge_delay_insns (insn, next_active_insn (target_label));
4048 /* If we get here, we haven't deleted INSN. But we may have deleted
4049 NEXT, so recompute it. */
4050 next = next_active_insn (insn);
4056 /* Look for filled jumps to the end of function label. We can try to convert
4057 them into RETURN insns if the insns in the delay slot are valid for the
4061 make_return_insns (first)
4064 rtx insn, jump_insn, pat;
4065 rtx real_return_label = end_of_function_label;
4068 /* See if there is a RETURN insn in the function other than the one we
4069 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
4070 into a RETURN to jump to it. */
4071 for (insn = first; insn; insn = NEXT_INSN (insn))
4072 if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
4074 real_return_label = get_label_before (insn);
4078 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
4079 was equal to END_OF_FUNCTION_LABEL. */
4080 LABEL_NUSES (real_return_label)++;
4082 /* Clear the list of insns to fill so we can use it. */
4083 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4085 for (insn = first; insn; insn = NEXT_INSN (insn))
4089 /* Only look at filled JUMP_INSNs that go to the end of function
4091 if (GET_CODE (insn) != INSN
4092 || GET_CODE (PATTERN (insn)) != SEQUENCE
4093 || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4094 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
4097 pat = PATTERN (insn);
4098 jump_insn = XVECEXP (pat, 0, 0);
4100 /* If we can't make the jump into a RETURN, try to redirect it to the best
4101 RETURN and go on to the next insn. */
4102 if (! reorg_redirect_jump (jump_insn, NULL_RTX))
4104 /* Make sure redirecting the jump will not invalidate the delay
4106 if (redirect_with_delay_slots_safe_p (jump_insn,
4109 reorg_redirect_jump (jump_insn, real_return_label);
4113 /* See if this RETURN can accept the insns current in its delay slot.
4114 It can if it has more or an equal number of slots and the contents
4115 of each is valid. */
4117 flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
4118 slots = num_delay_slots (jump_insn);
4119 if (slots >= XVECLEN (pat, 0) - 1)
4121 for (i = 1; i < XVECLEN (pat, 0); i++)
4123 #ifdef ANNUL_IFFALSE_SLOTS
4124 (INSN_ANNULLED_BRANCH_P (jump_insn)
4125 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4126 ? eligible_for_annul_false (jump_insn, i - 1,
4127 XVECEXP (pat, 0, i), flags) :
4129 #ifdef ANNUL_IFTRUE_SLOTS
4130 (INSN_ANNULLED_BRANCH_P (jump_insn)
4131 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4132 ? eligible_for_annul_true (jump_insn, i - 1,
4133 XVECEXP (pat, 0, i), flags) :
4135 eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i), flags)))
4141 if (i == XVECLEN (pat, 0))
4144 /* We have to do something with this insn. If it is an unconditional
4145 RETURN, delete the SEQUENCE and output the individual insns,
4146 followed by the RETURN. Then set things up so we try to find
4147 insns for its delay slots, if it needs some. */
4148 if (GET_CODE (PATTERN (jump_insn)) == RETURN)
4150 rtx prev = PREV_INSN (insn);
4153 for (i = 1; i < XVECLEN (pat, 0); i++)
4154 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
4156 insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
4157 emit_barrier_after (insn);
4160 obstack_ptr_grow (&unfilled_slots_obstack, insn);
4163 /* It is probably more efficient to keep this with its current
4164 delay slot as a branch to a RETURN. */
4165 reorg_redirect_jump (jump_insn, real_return_label);
4168 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
4169 new delay slots we have created. */
4170 if (--LABEL_NUSES (real_return_label) == 0)
4171 delete_insn (real_return_label);
4173 fill_simple_delay_slots (first, 1);
4174 fill_simple_delay_slots (first, 0);
4178 /* Try to find insns to place in delay slots. */
4181 dbr_schedule (first, file)
4185 rtx insn, next, epilogue_insn = 0;
4188 int old_flag_no_peephole = flag_no_peephole;
4190 /* Execute `final' once in prescan mode to delete any insns that won't be
4191 used. Don't let final try to do any peephole optimization--it will
4192 ruin dataflow information for this pass. */
4194 flag_no_peephole = 1;
4195 final (first, 0, NO_DEBUG, 1, 1);
4196 flag_no_peephole = old_flag_no_peephole;
4199 /* If the current function has no insns other than the prologue and
4200 epilogue, then do not try to fill any delay slots. */
4201 if (n_basic_blocks == 0)
4204 /* Find the highest INSN_UID and allocate and initialize our map from
4205 INSN_UID's to position in code. */
4206 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
4208 if (INSN_UID (insn) > max_uid)
4209 max_uid = INSN_UID (insn);
4210 if (GET_CODE (insn) == NOTE
4211 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
4212 epilogue_insn = insn;
4215 uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
4216 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
4217 uid_to_ruid[INSN_UID (insn)] = i;
4219 /* Initialize the list of insns that need filling. */
4220 if (unfilled_firstobj == 0)
4222 gcc_obstack_init (&unfilled_slots_obstack);
4223 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4226 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
4230 INSN_ANNULLED_BRANCH_P (insn) = 0;
4231 INSN_FROM_TARGET_P (insn) = 0;
4233 /* Skip vector tables. We can't get attributes for them. */
4234 if (GET_CODE (insn) == JUMP_INSN
4235 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
4236 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
4239 if (num_delay_slots (insn) > 0)
4240 obstack_ptr_grow (&unfilled_slots_obstack, insn);
4242 /* Ensure all jumps go to the last of a set of consecutive labels. */
4243 if (GET_CODE (insn) == JUMP_INSN
4244 && (condjump_p (insn) || condjump_in_parallel_p (insn))
4245 && JUMP_LABEL (insn) != 0
4246 && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
4247 != JUMP_LABEL (insn)))
4248 redirect_jump (insn, target);
4251 /* Indicate what resources are required to be valid at the end of the current
4252 function. The condition code never is and memory always is. If the
4253 frame pointer is needed, it is and so is the stack pointer unless
4254 EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
4255 stack pointer is. Registers used to return the function value are
4256 needed. Registers holding global variables are needed. */
4258 end_of_function_needs.cc = 0;
4259 end_of_function_needs.memory = 1;
4260 CLEAR_HARD_REG_SET (end_of_function_needs.regs);
4262 if (frame_pointer_needed)
4264 SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
4265 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4266 SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM);
4268 #ifdef EXIT_IGNORE_STACK
4269 if (! EXIT_IGNORE_STACK)
4271 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4274 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4276 if (current_function_return_rtx != 0
4277 && GET_CODE (current_function_return_rtx) == REG)
4278 mark_referenced_resources (current_function_return_rtx,
4279 &end_of_function_needs, 1);
4281 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4283 SET_HARD_REG_BIT (end_of_function_needs.regs, i);
4285 /* The registers required to be live at the end of the function are
4286 represented in the flow information as being dead just prior to
4287 reaching the end of the function. For example, the return of a value
4288 might be represented by a USE of the return register immediately
4289 followed by an unconditional jump to the return label where the
4290 return label is the end of the RTL chain. The end of the RTL chain
4291 is then taken to mean that the return register is live.
4293 This sequence is no longer maintained when epilogue instructions are
4294 added to the RTL chain. To reconstruct the original meaning, the
4295 start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
4296 point where these registers become live (start_of_epilogue_needs).
4297 If epilogue instructions are present, the registers set by those
4298 instructions won't have been processed by flow. Thus, those
4299 registers are additionally required at the end of the RTL chain
4300 (end_of_function_needs). */
4302 start_of_epilogue_needs = end_of_function_needs;
4304 while (epilogue_insn = next_nonnote_insn (epilogue_insn))
4305 mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1);
4307 /* Show we haven't computed an end-of-function label yet. */
4308 end_of_function_label = 0;
4310 /* Allocate and initialize the tables used by mark_target_live_regs. */
4312 = (struct target_info **) alloca ((TARGET_HASH_PRIME
4313 * sizeof (struct target_info *)));
4314 bzero ((char *) target_hash_table,
4315 TARGET_HASH_PRIME * sizeof (struct target_info *));
4317 bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
4318 bzero ((char *) bb_ticks, n_basic_blocks * sizeof (int));
4320 /* Initialize the statistics for this function. */
4321 bzero ((char *) num_insns_needing_delays, sizeof num_insns_needing_delays);
4322 bzero ((char *) num_filled_delays, sizeof num_filled_delays);
4324 /* Now do the delay slot filling. Try everything twice in case earlier
4325 changes make more slots fillable. */
4327 for (reorg_pass_number = 0;
4328 reorg_pass_number < MAX_REORG_PASSES;
4329 reorg_pass_number++)
4331 fill_simple_delay_slots (first, 1);
4332 fill_simple_delay_slots (first, 0);
4333 fill_eager_delay_slots (first);
4334 relax_delay_slots (first);
4337 /* Delete any USE insns made by update_block; subsequent passes don't need
4338 them or know how to deal with them. */
4339 for (insn = first; insn; insn = next)
4341 next = NEXT_INSN (insn);
4343 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
4344 && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
4345 next = delete_insn (insn);
4348 /* If we made an end of function label, indicate that it is now
4349 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
4350 If it is now unused, delete it. */
4351 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
4352 delete_insn (end_of_function_label);
4355 if (HAVE_return && end_of_function_label != 0)
4356 make_return_insns (first);
4359 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4361 /* It is not clear why the line below is needed, but it does seem to be. */
4362 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4364 /* Reposition the prologue and epilogue notes in case we moved the
4365 prologue/epilogue insns. */
4366 reposition_prologue_and_epilogue_notes (first);
4370 register int i, j, need_comma;
4372 for (reorg_pass_number = 0;
4373 reorg_pass_number < MAX_REORG_PASSES;
4374 reorg_pass_number++)
4376 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
4377 for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
4380 fprintf (file, ";; Reorg function #%d\n", i);
4382 fprintf (file, ";; %d insns needing delay slots\n;; ",
4383 num_insns_needing_delays[i][reorg_pass_number]);
4385 for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
4386 if (num_filled_delays[i][j][reorg_pass_number])
4389 fprintf (file, ", ");
4391 fprintf (file, "%d got %d delays",
4392 num_filled_delays[i][j][reorg_pass_number], j);
4394 fprintf (file, "\n");
4399 #endif /* DELAY_SLOTS */