1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992, 93, 94, 95, 96, 97, 1998 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, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
23 /* Instruction reorganization pass.
25 This pass runs after register allocation and final jump
26 optimization. It should be the last pass to run before peephole.
27 It serves primarily to fill delay slots of insns, typically branch
28 and call insns. Other insns typically involve more complicated
29 interactions of data dependencies and resource constraints, and
30 are better handled by scheduling before register allocation (by the
31 function `schedule_insns').
33 The Branch Penalty is the number of extra cycles that are needed to
34 execute a branch insn. On an ideal machine, branches take a single
35 cycle, and the Branch Penalty is 0. Several RISC machines approach
36 branch delays differently:
38 The MIPS and AMD 29000 have a single branch delay slot. Most insns
39 (except other branches) can be used to fill this slot. When the
40 slot is filled, two insns execute in two cycles, reducing the
41 branch penalty to zero.
43 The Motorola 88000 conditionally exposes its branch delay slot,
44 so code is shorter when it is turned off, but will run faster
45 when useful insns are scheduled there.
47 The IBM ROMP has two forms of branch and call insns, both with and
48 without a delay slot. Much like the 88k, insns not using the delay
49 slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
51 The SPARC always has a branch delay slot, but its effects can be
52 annulled when the branch is not taken. This means that failing to
53 find other sources of insns, we can hoist an insn from the branch
54 target that would only be safe to execute knowing that the branch
57 The HP-PA always has a branch delay slot. For unconditional branches
58 its effects can be annulled when the branch is taken. The effects
59 of the delay slot in a conditional branch can be nullified for forward
60 taken branches, or for untaken backward branches. This means
61 we can hoist insns from the fall-through path for forward branches or
62 steal insns from the target of backward branches.
64 Three techniques for filling delay slots have been implemented so far:
66 (1) `fill_simple_delay_slots' is the simplest, most efficient way
67 to fill delay slots. This pass first looks for insns which come
68 from before the branch and which are safe to execute after the
69 branch. Then it searches after the insn requiring delay slots or,
70 in the case of a branch, for insns that are after the point at
71 which the branch merges into the fallthrough code, if such a point
72 exists. When such insns are found, the branch penalty decreases
73 and no code expansion takes place.
75 (2) `fill_eager_delay_slots' is more complicated: it is used for
76 scheduling conditional jumps, or for scheduling jumps which cannot
77 be filled using (1). A machine need not have annulled jumps to use
78 this strategy, but it helps (by keeping more options open).
79 `fill_eager_delay_slots' tries to guess the direction the branch
80 will go; if it guesses right 100% of the time, it can reduce the
81 branch penalty as much as `fill_simple_delay_slots' does. If it
82 guesses wrong 100% of the time, it might as well schedule nops (or
83 on the m88k, unexpose the branch slot). When
84 `fill_eager_delay_slots' takes insns from the fall-through path of
85 the jump, usually there is no code expansion; when it takes insns
86 from the branch target, there is code expansion if it is not the
87 only way to reach that target.
89 (3) `relax_delay_slots' uses a set of rules to simplify code that
90 has been reorganized by (1) and (2). It finds cases where
91 conditional test can be eliminated, jumps can be threaded, extra
92 insns can be eliminated, etc. It is the job of (1) and (2) to do a
93 good job of scheduling locally; `relax_delay_slots' takes care of
94 making the various individual schedules work well together. It is
95 especially tuned to handle the control flow interactions of branch
96 insns. It does nothing for insns with delay slots that do not
99 On machines that use CC0, we are very conservative. We will not make
100 a copy of an insn involving CC0 since we want to maintain a 1-1
101 correspondence between the insn that sets and uses CC0. The insns are
102 allowed to be separated by placing an insn that sets CC0 (but not an insn
103 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
104 delay slot. In that case, we point each insn at the other with REG_CC_USER
105 and REG_CC_SETTER notes. Note that these restrictions affect very few
106 machines because most RISC machines with delay slots will not use CC0
107 (the RT is the only known exception at this point).
111 The Acorn Risc Machine can conditionally execute most insns, so
112 it is profitable to move single insns into a position to execute
113 based on the condition code of the previous insn.
115 The HP-PA can conditionally nullify insns, providing a similar
116 effect to the ARM, differing mostly in which insn is "in charge". */
122 #include "insn-config.h"
123 #include "conditions.h"
124 #include "hard-reg-set.h"
125 #include "basic-block.h"
127 #include "insn-flags.h"
132 #include "insn-attr.h"
134 /* Import list of registers used as spill regs from reload. */
135 extern HARD_REG_SET used_spill_regs;
137 /* Import highest label used in function at end of reload. */
138 extern int max_label_num_after_reload;
143 #define obstack_chunk_alloc xmalloc
144 #define obstack_chunk_free free
146 #ifndef ANNUL_IFTRUE_SLOTS
147 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
149 #ifndef ANNUL_IFFALSE_SLOTS
150 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
153 /* Insns which have delay slots that have not yet been filled. */
155 static struct obstack unfilled_slots_obstack;
156 static rtx *unfilled_firstobj;
158 /* Define macros to refer to the first and last slot containing unfilled
159 insns. These are used because the list may move and its address
160 should be recomputed at each use. */
162 #define unfilled_slots_base \
163 ((rtx *) obstack_base (&unfilled_slots_obstack))
165 #define unfilled_slots_next \
166 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
168 /* This structure is used to indicate which hardware resources are set or
169 needed by insns so far. */
173 char memory; /* Insn sets or needs a memory location. */
174 char unch_memory; /* Insn sets of needs a "unchanging" MEM. */
175 char volatil; /* Insn sets or needs a volatile memory loc. */
176 char cc; /* Insn sets or needs the condition codes. */
177 HARD_REG_SET regs; /* Which registers are set or needed. */
180 /* Macro to clear all resources. */
181 #define CLEAR_RESOURCE(RES) \
182 do { (RES)->memory = (RES)->unch_memory = (RES)->volatil = (RES)->cc = 0; \
183 CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
185 /* Indicates what resources are required at the beginning of the epilogue. */
186 static struct resources start_of_epilogue_needs;
188 /* Indicates what resources are required at function end. */
189 static struct resources end_of_function_needs;
191 /* Points to the label before the end of the function. */
192 static rtx end_of_function_label;
194 /* This structure is used to record liveness information at the targets or
195 fallthrough insns of branches. We will most likely need the information
196 at targets again, so save them in a hash table rather than recomputing them
201 int uid; /* INSN_UID of target. */
202 struct target_info *next; /* Next info for same hash bucket. */
203 HARD_REG_SET live_regs; /* Registers live at target. */
204 int block; /* Basic block number containing target. */
205 int bb_tick; /* Generation count of basic block info. */
208 #define TARGET_HASH_PRIME 257
210 /* Define the hash table itself. */
211 static struct target_info **target_hash_table;
213 /* For each basic block, we maintain a generation number of its basic
214 block info, which is updated each time we move an insn from the
215 target of a jump. This is the generation number indexed by block
218 static int *bb_ticks;
220 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
221 not always monotonically increase. */
222 static int *uid_to_ruid;
224 /* Highest valid index in `uid_to_ruid'. */
227 static void mark_referenced_resources PROTO((rtx, struct resources *, int));
228 static void mark_set_resources PROTO((rtx, struct resources *, int, int));
229 static int stop_search_p PROTO((rtx, int));
230 static int resource_conflicts_p PROTO((struct resources *,
231 struct resources *));
232 static int insn_references_resource_p PROTO((rtx, struct resources *, int));
233 static int insn_sets_resource_p PROTO((rtx, struct resources *, int));
234 static rtx find_end_label PROTO((void));
235 static rtx emit_delay_sequence PROTO((rtx, rtx, int));
236 static rtx add_to_delay_list PROTO((rtx, rtx));
237 static void delete_from_delay_slot PROTO((rtx));
238 static void delete_scheduled_jump PROTO((rtx));
239 static void note_delay_statistics PROTO((int, int));
240 static rtx optimize_skip PROTO((rtx));
241 static int get_jump_flags PROTO((rtx, rtx));
242 static int rare_destination PROTO((rtx));
243 static int mostly_true_jump PROTO((rtx, rtx));
244 static rtx get_branch_condition PROTO((rtx, rtx));
245 static int condition_dominates_p PROTO((rtx, rtx));
246 static rtx steal_delay_list_from_target PROTO((rtx, rtx, rtx, rtx,
250 int, int *, int *, rtx *));
251 static rtx steal_delay_list_from_fallthrough PROTO((rtx, rtx, rtx, rtx,
256 static void try_merge_delay_insns PROTO((rtx, rtx));
257 static rtx redundant_insn PROTO((rtx, rtx, rtx));
258 static int own_thread_p PROTO((rtx, rtx, int));
259 static int find_basic_block PROTO((rtx));
260 static void update_block PROTO((rtx, rtx));
261 static int reorg_redirect_jump PROTO((rtx, rtx));
262 static void update_reg_dead_notes PROTO((rtx, rtx));
263 static void fix_reg_dead_note PROTO((rtx, rtx));
264 static void update_reg_unused_notes PROTO((rtx, rtx));
265 static void update_live_status PROTO((rtx, rtx));
266 static rtx next_insn_no_annul PROTO((rtx));
267 static rtx find_dead_or_set_registers PROTO ((rtx, struct resources *, rtx *,
268 int, struct resources,
270 static void mark_target_live_regs PROTO((rtx, struct resources *));
271 static void fill_simple_delay_slots PROTO((int));
272 static rtx fill_slots_from_thread PROTO((rtx, rtx, rtx, rtx, int, int,
273 int, int, int *, rtx));
274 static void fill_eager_delay_slots PROTO((void));
275 static void relax_delay_slots PROTO((rtx));
276 static void make_return_insns PROTO((rtx));
277 static int redirect_with_delay_slots_safe_p PROTO ((rtx, rtx, rtx));
278 static int redirect_with_delay_list_safe_p PROTO ((rtx, rtx, rtx));
280 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
281 which resources are references by the insn. If INCLUDE_DELAYED_EFFECTS
282 is TRUE, resources used by the called routine will be included for
286 mark_referenced_resources (x, res, include_delayed_effects)
288 register struct resources *res;
289 register int include_delayed_effects;
291 register enum rtx_code code = GET_CODE (x);
293 register char *format_ptr;
295 /* Handle leaf items for which we set resource flags. Also, special-case
296 CALL, SET and CLOBBER operators. */
308 if (GET_CODE (SUBREG_REG (x)) != REG)
309 mark_referenced_resources (SUBREG_REG (x), res, 0);
312 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
313 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
314 for (i = regno; i < last_regno; i++)
315 SET_HARD_REG_BIT (res->regs, i);
320 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
321 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
325 /* If this memory shouldn't change, it really isn't referencing
327 if (RTX_UNCHANGING_P (x))
328 res->unch_memory = 1;
331 res->volatil = MEM_VOLATILE_P (x);
333 /* Mark registers used to access memory. */
334 mark_referenced_resources (XEXP (x, 0), res, 0);
341 case UNSPEC_VOLATILE:
343 /* Traditional asm's are always volatile. */
352 res->volatil = MEM_VOLATILE_P (x);
354 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
355 We can not just fall through here since then we would be confused
356 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
357 traditional asms unlike their normal usage. */
359 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
360 mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
364 /* The first operand will be a (MEM (xxx)) but doesn't really reference
365 memory. The second operand may be referenced, though. */
366 mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
367 mark_referenced_resources (XEXP (x, 1), res, 0);
371 /* Usually, the first operand of SET is set, not referenced. But
372 registers used to access memory are referenced. SET_DEST is
373 also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
375 mark_referenced_resources (SET_SRC (x), res, 0);
378 if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
379 mark_referenced_resources (x, res, 0);
380 else if (GET_CODE (x) == SUBREG)
382 if (GET_CODE (x) == MEM)
383 mark_referenced_resources (XEXP (x, 0), res, 0);
390 if (include_delayed_effects)
392 /* A CALL references memory, the frame pointer if it exists, the
393 stack pointer, any global registers and any registers given in
394 USE insns immediately in front of the CALL.
396 However, we may have moved some of the parameter loading insns
397 into the delay slot of this CALL. If so, the USE's for them
398 don't count and should be skipped. */
399 rtx insn = PREV_INSN (x);
402 rtx next = NEXT_INSN (x);
405 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
406 if (NEXT_INSN (insn) != x)
408 next = NEXT_INSN (NEXT_INSN (insn));
409 sequence = PATTERN (NEXT_INSN (insn));
410 seq_size = XVECLEN (sequence, 0);
411 if (GET_CODE (sequence) != SEQUENCE)
416 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
417 if (frame_pointer_needed)
419 SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
420 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
421 SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM);
425 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
427 SET_HARD_REG_BIT (res->regs, i);
429 /* Check for a NOTE_INSN_SETJMP. If it exists, then we must
430 assume that this call can need any register.
432 This is done to be more conservative about how we handle setjmp.
433 We assume that they both use and set all registers. Using all
434 registers ensures that a register will not be considered dead
435 just because it crosses a setjmp call. A register should be
436 considered dead only if the setjmp call returns non-zero. */
437 if (next && GET_CODE (next) == NOTE
438 && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
439 SET_HARD_REG_SET (res->regs);
444 for (link = CALL_INSN_FUNCTION_USAGE (x);
446 link = XEXP (link, 1))
447 if (GET_CODE (XEXP (link, 0)) == USE)
449 for (i = 1; i < seq_size; i++)
451 rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
452 if (GET_CODE (slot_pat) == SET
453 && rtx_equal_p (SET_DEST (slot_pat),
454 SET_DEST (XEXP (link, 0))))
458 mark_referenced_resources (SET_DEST (XEXP (link, 0)),
464 /* ... fall through to other INSN processing ... */
469 #ifdef INSN_REFERENCES_ARE_DELAYED
470 if (! include_delayed_effects
471 && INSN_REFERENCES_ARE_DELAYED (x))
475 /* No special processing, just speed up. */
476 mark_referenced_resources (PATTERN (x), res, include_delayed_effects);
483 /* Process each sub-expression and flag what it needs. */
484 format_ptr = GET_RTX_FORMAT (code);
485 for (i = 0; i < GET_RTX_LENGTH (code); i++)
486 switch (*format_ptr++)
489 mark_referenced_resources (XEXP (x, i), res, include_delayed_effects);
493 for (j = 0; j < XVECLEN (x, i); j++)
494 mark_referenced_resources (XVECEXP (x, i, j), res,
495 include_delayed_effects);
500 /* Given X, a part of an insn, and a pointer to a `struct resource',
501 RES, indicate which resources are modified by the insn. If
502 INCLUDE_DELAYED_EFFECTS is nonzero, also mark resources potentially
503 set by the called routine.
505 If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
506 objects are being referenced instead of set.
508 We never mark the insn as modifying the condition code unless it explicitly
509 SETs CC0 even though this is not totally correct. The reason for this is
510 that we require a SET of CC0 to immediately precede the reference to CC0.
511 So if some other insn sets CC0 as a side-effect, we know it cannot affect
512 our computation and thus may be placed in a delay slot. */
515 mark_set_resources (x, res, in_dest, include_delayed_effects)
517 register struct resources *res;
519 int include_delayed_effects;
521 register enum rtx_code code;
523 register char *format_ptr;
541 /* These don't set any resources. */
550 /* Called routine modifies the condition code, memory, any registers
551 that aren't saved across calls, global registers and anything
552 explicitly CLOBBERed immediately after the CALL_INSN. */
554 if (include_delayed_effects)
556 rtx next = NEXT_INSN (x);
557 rtx prev = PREV_INSN (x);
560 res->cc = res->memory = 1;
561 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
562 if (call_used_regs[i] || global_regs[i])
563 SET_HARD_REG_BIT (res->regs, i);
565 /* If X is part of a delay slot sequence, then NEXT should be
566 the first insn after the sequence. */
567 if (NEXT_INSN (prev) != x)
568 next = NEXT_INSN (NEXT_INSN (prev));
570 for (link = CALL_INSN_FUNCTION_USAGE (x);
571 link; link = XEXP (link, 1))
572 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
573 mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1, 0);
575 /* Check for a NOTE_INSN_SETJMP. If it exists, then we must
576 assume that this call can clobber any register. */
577 if (next && GET_CODE (next) == NOTE
578 && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
579 SET_HARD_REG_SET (res->regs);
582 /* ... and also what its RTL says it modifies, if anything. */
587 /* An insn consisting of just a CLOBBER (or USE) is just for flow
588 and doesn't actually do anything, so we ignore it. */
590 #ifdef INSN_SETS_ARE_DELAYED
591 if (! include_delayed_effects
592 && INSN_SETS_ARE_DELAYED (x))
597 if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
602 /* If the source of a SET is a CALL, this is actually done by
603 the called routine. So only include it if we are to include the
604 effects of the calling routine. */
606 mark_set_resources (SET_DEST (x), res,
607 (include_delayed_effects
608 || GET_CODE (SET_SRC (x)) != CALL),
611 mark_set_resources (SET_SRC (x), res, 0, 0);
615 mark_set_resources (XEXP (x, 0), res, 1, 0);
619 for (i = 0; i < XVECLEN (x, 0); i++)
620 if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0))
621 && INSN_FROM_TARGET_P (XVECEXP (x, 0, i))))
622 mark_set_resources (XVECEXP (x, 0, i), res, 0,
623 include_delayed_effects);
630 mark_set_resources (XEXP (x, 0), res, 1, 0);
634 mark_set_resources (XEXP (x, 0), res, in_dest, 0);
635 mark_set_resources (XEXP (x, 1), res, 0, 0);
636 mark_set_resources (XEXP (x, 2), res, 0, 0);
643 res->unch_memory = RTX_UNCHANGING_P (x);
644 res->volatil = MEM_VOLATILE_P (x);
647 mark_set_resources (XEXP (x, 0), res, 0, 0);
653 if (GET_CODE (SUBREG_REG (x)) != REG)
654 mark_set_resources (SUBREG_REG (x), res,
655 in_dest, include_delayed_effects);
658 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
659 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
660 for (i = regno; i < last_regno; i++)
661 SET_HARD_REG_BIT (res->regs, i);
668 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
669 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
676 /* Process each sub-expression and flag what it needs. */
677 format_ptr = GET_RTX_FORMAT (code);
678 for (i = 0; i < GET_RTX_LENGTH (code); i++)
679 switch (*format_ptr++)
682 mark_set_resources (XEXP (x, i), res, in_dest, include_delayed_effects);
686 for (j = 0; j < XVECLEN (x, i); j++)
687 mark_set_resources (XVECEXP (x, i, j), res, in_dest,
688 include_delayed_effects);
693 /* Return TRUE if this insn should stop the search for insn to fill delay
694 slots. LABELS_P indicates that labels should terminate the search.
695 In all cases, jumps terminate the search. */
698 stop_search_p (insn, labels_p)
705 switch (GET_CODE (insn))
719 /* OK unless it contains a delay slot or is an `asm' insn of some type.
720 We don't know anything about these. */
721 return (GET_CODE (PATTERN (insn)) == SEQUENCE
722 || GET_CODE (PATTERN (insn)) == ASM_INPUT
723 || asm_noperands (PATTERN (insn)) >= 0);
730 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
731 resource set contains a volatile memory reference. Otherwise, return FALSE. */
734 resource_conflicts_p (res1, res2)
735 struct resources *res1, *res2;
737 if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
738 || (res1->unch_memory && res2->unch_memory)
739 || res1->volatil || res2->volatil)
743 return (res1->regs & res2->regs) != HARD_CONST (0);
748 for (i = 0; i < HARD_REG_SET_LONGS; i++)
749 if ((res1->regs[i] & res2->regs[i]) != 0)
756 /* Return TRUE if any resource marked in RES, a `struct resources', is
757 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
758 routine is using those resources.
760 We compute this by computing all the resources referenced by INSN and
761 seeing if this conflicts with RES. It might be faster to directly check
762 ourselves, and this is the way it used to work, but it means duplicating
763 a large block of complex code. */
766 insn_references_resource_p (insn, res, include_delayed_effects)
768 register struct resources *res;
769 int include_delayed_effects;
771 struct resources insn_res;
773 CLEAR_RESOURCE (&insn_res);
774 mark_referenced_resources (insn, &insn_res, include_delayed_effects);
775 return resource_conflicts_p (&insn_res, res);
778 /* Return TRUE if INSN modifies resources that are marked in RES.
779 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
780 included. CC0 is only modified if it is explicitly set; see comments
781 in front of mark_set_resources for details. */
784 insn_sets_resource_p (insn, res, include_delayed_effects)
786 register struct resources *res;
787 int include_delayed_effects;
789 struct resources insn_sets;
791 CLEAR_RESOURCE (&insn_sets);
792 mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
793 return resource_conflicts_p (&insn_sets, res);
796 /* Find a label at the end of the function or before a RETURN. If there is
804 /* If we found one previously, return it. */
805 if (end_of_function_label)
806 return end_of_function_label;
808 /* Otherwise, see if there is a label at the end of the function. If there
809 is, it must be that RETURN insns aren't needed, so that is our return
810 label and we don't have to do anything else. */
812 insn = get_last_insn ();
813 while (GET_CODE (insn) == NOTE
814 || (GET_CODE (insn) == INSN
815 && (GET_CODE (PATTERN (insn)) == USE
816 || GET_CODE (PATTERN (insn)) == CLOBBER)))
817 insn = PREV_INSN (insn);
819 /* When a target threads its epilogue we might already have a
820 suitable return insn. If so put a label before it for the
821 end_of_function_label. */
822 if (GET_CODE (insn) == BARRIER
823 && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
824 && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
826 rtx temp = PREV_INSN (PREV_INSN (insn));
827 end_of_function_label = gen_label_rtx ();
828 LABEL_NUSES (end_of_function_label) = 0;
830 /* Put the label before an USE insns that may proceed the RETURN insn. */
831 while (GET_CODE (temp) == USE)
832 temp = PREV_INSN (temp);
834 emit_label_after (end_of_function_label, temp);
837 else if (GET_CODE (insn) == CODE_LABEL)
838 end_of_function_label = insn;
841 /* Otherwise, make a new label and emit a RETURN and BARRIER,
843 end_of_function_label = gen_label_rtx ();
844 LABEL_NUSES (end_of_function_label) = 0;
845 emit_label (end_of_function_label);
849 /* The return we make may have delay slots too. */
850 rtx insn = gen_return ();
851 insn = emit_jump_insn (insn);
853 if (num_delay_slots (insn) > 0)
854 obstack_ptr_grow (&unfilled_slots_obstack, insn);
859 /* Show one additional use for this label so it won't go away until
861 ++LABEL_NUSES (end_of_function_label);
863 return end_of_function_label;
866 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
867 the pattern of INSN with the SEQUENCE.
869 Chain the insns so that NEXT_INSN of each insn in the sequence points to
870 the next and NEXT_INSN of the last insn in the sequence points to
871 the first insn after the sequence. Similarly for PREV_INSN. This makes
872 it easier to scan all insns.
874 Returns the SEQUENCE that replaces INSN. */
877 emit_delay_sequence (insn, list, length)
886 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
887 rtvec seqv = rtvec_alloc (length + 1);
888 rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
889 rtx seq_insn = make_insn_raw (seq);
890 rtx first = get_insns ();
891 rtx last = get_last_insn ();
893 /* Make a copy of the insn having delay slots. */
894 rtx delay_insn = copy_rtx (insn);
896 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
897 confuse further processing. Update LAST in case it was the last insn.
898 We will put the BARRIER back in later. */
899 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
901 delete_insn (NEXT_INSN (insn));
902 last = get_last_insn ();
906 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
907 NEXT_INSN (seq_insn) = NEXT_INSN (insn);
908 PREV_INSN (seq_insn) = PREV_INSN (insn);
911 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
914 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
916 /* Note the calls to set_new_first_and_last_insn must occur after
917 SEQ_INSN has been completely spliced into the insn stream.
919 Otherwise CUR_INSN_UID will get set to an incorrect value because
920 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */
922 set_new_first_and_last_insn (first, seq_insn);
925 set_new_first_and_last_insn (seq_insn, last);
927 /* Build our SEQUENCE and rebuild the insn chain. */
928 XVECEXP (seq, 0, 0) = delay_insn;
929 INSN_DELETED_P (delay_insn) = 0;
930 PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
932 for (li = list; li; li = XEXP (li, 1), i++)
934 rtx tem = XEXP (li, 0);
937 /* Show that this copy of the insn isn't deleted. */
938 INSN_DELETED_P (tem) = 0;
940 XVECEXP (seq, 0, i) = tem;
941 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
942 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
944 /* Remove any REG_DEAD notes because we can't rely on them now
945 that the insn has been moved. */
946 for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
947 if (REG_NOTE_KIND (note) == REG_DEAD)
948 XEXP (note, 0) = const0_rtx;
951 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
953 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
954 last insn in that SEQUENCE to point to us. Similarly for the first
955 insn in the following insn if it is a SEQUENCE. */
957 if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
958 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
959 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
960 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
963 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
964 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
965 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
967 /* If there used to be a BARRIER, put it back. */
969 emit_barrier_after (seq_insn);
977 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
978 be in the order in which the insns are to be executed. */
981 add_to_delay_list (insn, delay_list)
985 /* If we have an empty list, just make a new list element. If
986 INSN has its block number recorded, clear it since we may
987 be moving the insn to a new block. */
991 struct target_info *tinfo;
993 for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME];
994 tinfo; tinfo = tinfo->next)
995 if (tinfo->uid == INSN_UID (insn))
1001 return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
1004 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
1006 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
1011 /* Delete INSN from the delay slot of the insn that it is in. This may
1012 produce an insn without anything in its delay slots. */
1015 delete_from_delay_slot (insn)
1018 rtx trial, seq_insn, seq, prev;
1022 /* We first must find the insn containing the SEQUENCE with INSN in its
1023 delay slot. Do this by finding an insn, TRIAL, where
1024 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
1027 PREV_INSN (NEXT_INSN (trial)) == trial;
1028 trial = NEXT_INSN (trial))
1031 seq_insn = PREV_INSN (NEXT_INSN (trial));
1032 seq = PATTERN (seq_insn);
1034 /* Create a delay list consisting of all the insns other than the one
1035 we are deleting (unless we were the only one). */
1036 if (XVECLEN (seq, 0) > 2)
1037 for (i = 1; i < XVECLEN (seq, 0); i++)
1038 if (XVECEXP (seq, 0, i) != insn)
1039 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
1041 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
1042 list, and rebuild the delay list if non-empty. */
1043 prev = PREV_INSN (seq_insn);
1044 trial = XVECEXP (seq, 0, 0);
1045 delete_insn (seq_insn);
1046 add_insn_after (trial, prev);
1048 if (GET_CODE (trial) == JUMP_INSN
1049 && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
1050 emit_barrier_after (trial);
1052 /* If there are any delay insns, remit them. Otherwise clear the
1055 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2);
1057 INSN_ANNULLED_BRANCH_P (trial) = 0;
1059 INSN_FROM_TARGET_P (insn) = 0;
1061 /* Show we need to fill this insn again. */
1062 obstack_ptr_grow (&unfilled_slots_obstack, trial);
1065 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
1066 the insn that sets CC0 for it and delete it too. */
1069 delete_scheduled_jump (insn)
1072 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
1073 delete the insn that sets the condition code, but it is hard to find it.
1074 Since this case is rare anyway, don't bother trying; there would likely
1075 be other insns that became dead anyway, which we wouldn't know to
1079 if (reg_mentioned_p (cc0_rtx, insn))
1081 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
1083 /* If a reg-note was found, it points to an insn to set CC0. This
1084 insn is in the delay list of some other insn. So delete it from
1085 the delay list it was in. */
1088 if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
1089 && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
1090 delete_from_delay_slot (XEXP (note, 0));
1094 /* The insn setting CC0 is our previous insn, but it may be in
1095 a delay slot. It will be the last insn in the delay slot, if
1097 rtx trial = previous_insn (insn);
1098 if (GET_CODE (trial) == NOTE)
1099 trial = prev_nonnote_insn (trial);
1100 if (sets_cc0_p (PATTERN (trial)) != 1
1101 || FIND_REG_INC_NOTE (trial, 0))
1103 if (PREV_INSN (NEXT_INSN (trial)) == trial)
1104 delete_insn (trial);
1106 delete_from_delay_slot (trial);
1114 /* Counters for delay-slot filling. */
1116 #define NUM_REORG_FUNCTIONS 2
1117 #define MAX_DELAY_HISTOGRAM 3
1118 #define MAX_REORG_PASSES 2
1120 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
1122 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
1124 static int reorg_pass_number;
1127 note_delay_statistics (slots_filled, index)
1128 int slots_filled, index;
1130 num_insns_needing_delays[index][reorg_pass_number]++;
1131 if (slots_filled > MAX_DELAY_HISTOGRAM)
1132 slots_filled = MAX_DELAY_HISTOGRAM;
1133 num_filled_delays[index][slots_filled][reorg_pass_number]++;
1136 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
1138 /* Optimize the following cases:
1140 1. When a conditional branch skips over only one instruction,
1141 use an annulling branch and put that insn in the delay slot.
1142 Use either a branch that annuls when the condition if true or
1143 invert the test with a branch that annuls when the condition is
1144 false. This saves insns, since otherwise we must copy an insn
1147 (orig) (skip) (otherwise)
1148 Bcc.n L1 Bcc',a L1 Bcc,a L1'
1155 2. When a conditional branch skips over only one instruction,
1156 and after that, it unconditionally branches somewhere else,
1157 perform the similar optimization. This saves executing the
1158 second branch in the case where the inverted condition is true.
1165 INSN is a JUMP_INSN.
1167 This should be expanded to skip over N insns, where N is the number
1168 of delay slots required. */
1171 optimize_skip (insn)
1174 register rtx trial = next_nonnote_insn (insn);
1175 rtx next_trial = next_active_insn (trial);
1180 flags = get_jump_flags (insn, JUMP_LABEL (insn));
1183 || GET_CODE (trial) != INSN
1184 || GET_CODE (PATTERN (trial)) == SEQUENCE
1185 || recog_memoized (trial) < 0
1186 || (! eligible_for_annul_false (insn, 0, trial, flags)
1187 && ! eligible_for_annul_true (insn, 0, trial, flags)))
1190 /* There are two cases where we are just executing one insn (we assume
1191 here that a branch requires only one insn; this should be generalized
1192 at some point): Where the branch goes around a single insn or where
1193 we have one insn followed by a branch to the same label we branch to.
1194 In both of these cases, inverting the jump and annulling the delay
1195 slot give the same effect in fewer insns. */
1196 if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
1198 && GET_CODE (next_trial) == JUMP_INSN
1199 && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
1200 && (simplejump_p (next_trial)
1201 || GET_CODE (PATTERN (next_trial)) == RETURN)))
1203 if (eligible_for_annul_false (insn, 0, trial, flags))
1205 if (invert_jump (insn, JUMP_LABEL (insn)))
1206 INSN_FROM_TARGET_P (trial) = 1;
1207 else if (! eligible_for_annul_true (insn, 0, trial, flags))
1211 delay_list = add_to_delay_list (trial, NULL_RTX);
1212 next_trial = next_active_insn (trial);
1213 update_block (trial, trial);
1214 delete_insn (trial);
1216 /* Also, if we are targeting an unconditional
1217 branch, thread our jump to the target of that branch. Don't
1218 change this into a RETURN here, because it may not accept what
1219 we have in the delay slot. We'll fix this up later. */
1220 if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1221 && (simplejump_p (next_trial)
1222 || GET_CODE (PATTERN (next_trial)) == RETURN))
1224 target_label = JUMP_LABEL (next_trial);
1225 if (target_label == 0)
1226 target_label = find_end_label ();
1228 /* Recompute the flags based on TARGET_LABEL since threading
1229 the jump to TARGET_LABEL may change the direction of the
1230 jump (which may change the circumstances in which the
1231 delay slot is nullified). */
1232 flags = get_jump_flags (insn, target_label);
1233 if (eligible_for_annul_true (insn, 0, trial, flags))
1234 reorg_redirect_jump (insn, target_label);
1237 INSN_ANNULLED_BRANCH_P (insn) = 1;
1245 /* Encode and return branch direction and prediction information for
1246 INSN assuming it will jump to LABEL.
1248 Non conditional branches return no direction information and
1249 are predicted as very likely taken. */
1252 get_jump_flags (insn, label)
1257 /* get_jump_flags can be passed any insn with delay slots, these may
1258 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
1259 direction information, and only if they are conditional jumps.
1261 If LABEL is zero, then there is no way to determine the branch
1263 if (GET_CODE (insn) == JUMP_INSN
1264 && (condjump_p (insn) || condjump_in_parallel_p (insn))
1265 && INSN_UID (insn) <= max_uid
1267 && INSN_UID (label) <= max_uid)
1269 = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
1270 ? ATTR_FLAG_forward : ATTR_FLAG_backward;
1271 /* No valid direction information. */
1275 /* If insn is a conditional branch call mostly_true_jump to get
1276 determine the branch prediction.
1278 Non conditional branches are predicted as very likely taken. */
1279 if (GET_CODE (insn) == JUMP_INSN
1280 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
1284 prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
1288 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
1291 flags |= ATTR_FLAG_likely;
1294 flags |= ATTR_FLAG_unlikely;
1297 flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
1305 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
1310 /* Return 1 if INSN is a destination that will be branched to rarely (the
1311 return point of a function); return 2 if DEST will be branched to very
1312 rarely (a call to a function that doesn't return). Otherwise,
1316 rare_destination (insn)
1322 for (; insn; insn = next)
1324 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE)
1325 insn = XVECEXP (PATTERN (insn), 0, 0);
1327 next = NEXT_INSN (insn);
1329 switch (GET_CODE (insn))
1334 /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We
1335 don't scan past JUMP_INSNs, so any barrier we find here must
1336 have been after a CALL_INSN and hence mean the call doesn't
1340 if (GET_CODE (PATTERN (insn)) == RETURN)
1342 else if (simplejump_p (insn)
1343 && jump_count++ < 10)
1344 next = JUMP_LABEL (insn);
1353 /* If we got here it means we hit the end of the function. So this
1354 is an unlikely destination. */
1359 /* Return truth value of the statement that this branch
1360 is mostly taken. If we think that the branch is extremely likely
1361 to be taken, we return 2. If the branch is slightly more likely to be
1362 taken, return 1. If the branch is slightly less likely to be taken,
1363 return 0 and if the branch is highly unlikely to be taken, return -1.
1365 CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */
1368 mostly_true_jump (jump_insn, condition)
1369 rtx jump_insn, condition;
1371 rtx target_label = JUMP_LABEL (jump_insn);
1373 int rare_dest = rare_destination (target_label);
1374 int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
1376 /* If branch probabilities are available, then use that number since it
1377 always gives a correct answer. */
1378 if (flag_branch_probabilities)
1380 rtx note = find_reg_note (jump_insn, REG_BR_PROB, 0);;
1383 int prob = XINT (note, 0);
1385 if (prob >= REG_BR_PROB_BASE * 9 / 10)
1387 else if (prob >= REG_BR_PROB_BASE / 2)
1389 else if (prob >= REG_BR_PROB_BASE / 10)
1396 /* If this is a branch outside a loop, it is highly unlikely. */
1397 if (GET_CODE (PATTERN (jump_insn)) == SET
1398 && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
1399 && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
1400 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
1401 || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
1402 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
1407 /* If this is the test of a loop, it is very likely true. We scan
1408 backwards from the target label. If we find a NOTE_INSN_LOOP_BEG
1409 before the next real insn, we assume the branch is to the top of
1411 for (insn = PREV_INSN (target_label);
1412 insn && GET_CODE (insn) == NOTE;
1413 insn = PREV_INSN (insn))
1414 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1417 /* If this is a jump to the test of a loop, it is likely true. We scan
1418 forwards from the target label. If we find a NOTE_INSN_LOOP_VTOP
1419 before the next real insn, we assume the branch is to the loop branch
1421 for (insn = NEXT_INSN (target_label);
1422 insn && GET_CODE (insn) == NOTE;
1423 insn = PREV_INSN (insn))
1424 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
1428 /* Look at the relative rarities of the fallthrough and destination. If
1429 they differ, we can predict the branch that way. */
1431 switch (rare_fallthrough - rare_dest)
1445 /* If we couldn't figure out what this jump was, assume it won't be
1446 taken. This should be rare. */
1450 /* EQ tests are usually false and NE tests are usually true. Also,
1451 most quantities are positive, so we can make the appropriate guesses
1452 about signed comparisons against zero. */
1453 switch (GET_CODE (condition))
1456 /* Unconditional branch. */
1464 if (XEXP (condition, 1) == const0_rtx)
1469 if (XEXP (condition, 1) == const0_rtx)
1477 /* Predict backward branches usually take, forward branches usually not. If
1478 we don't know whether this is forward or backward, assume the branch
1479 will be taken, since most are. */
1480 return (target_label == 0 || INSN_UID (jump_insn) > max_uid
1481 || INSN_UID (target_label) > max_uid
1482 || (uid_to_ruid[INSN_UID (jump_insn)]
1483 > uid_to_ruid[INSN_UID (target_label)]));;
1486 /* Return the condition under which INSN will branch to TARGET. If TARGET
1487 is zero, return the condition under which INSN will return. If INSN is
1488 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1489 type of jump, or it doesn't go to TARGET, return 0. */
1492 get_branch_condition (insn, target)
1496 rtx pat = PATTERN (insn);
1499 if (condjump_in_parallel_p (insn))
1500 pat = XVECEXP (pat, 0, 0);
1502 if (GET_CODE (pat) == RETURN)
1503 return target == 0 ? const_true_rtx : 0;
1505 else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1508 src = SET_SRC (pat);
1509 if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1510 return const_true_rtx;
1512 else if (GET_CODE (src) == IF_THEN_ELSE
1513 && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1514 || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1515 && XEXP (XEXP (src, 1), 0) == target))
1516 && XEXP (src, 2) == pc_rtx)
1517 return XEXP (src, 0);
1519 else if (GET_CODE (src) == IF_THEN_ELSE
1520 && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1521 || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1522 && XEXP (XEXP (src, 2), 0) == target))
1523 && XEXP (src, 1) == pc_rtx)
1524 return gen_rtx_fmt_ee (reverse_condition (GET_CODE (XEXP (src, 0))),
1525 GET_MODE (XEXP (src, 0)),
1526 XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1531 /* Return non-zero if CONDITION is more strict than the condition of
1532 INSN, i.e., if INSN will always branch if CONDITION is true. */
1535 condition_dominates_p (condition, insn)
1539 rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1540 enum rtx_code code = GET_CODE (condition);
1541 enum rtx_code other_code;
1543 if (rtx_equal_p (condition, other_condition)
1544 || other_condition == const_true_rtx)
1547 else if (condition == const_true_rtx || other_condition == 0)
1550 other_code = GET_CODE (other_condition);
1551 if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1552 || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1553 || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1556 return comparison_dominates_p (code, other_code);
1559 /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
1560 any insns already in the delay slot of JUMP. */
1563 redirect_with_delay_slots_safe_p (jump, newlabel, seq)
1564 rtx jump, newlabel, seq;
1567 rtx pat = PATTERN (seq);
1569 /* Make sure all the delay slots of this jump would still
1570 be valid after threading the jump. If they are still
1571 valid, then return non-zero. */
1573 flags = get_jump_flags (jump, newlabel);
1574 for (i = 1; i < XVECLEN (pat, 0); i++)
1576 #ifdef ANNUL_IFFALSE_SLOTS
1577 (INSN_ANNULLED_BRANCH_P (jump)
1578 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1579 ? eligible_for_annul_false (jump, i - 1,
1580 XVECEXP (pat, 0, i), flags) :
1582 #ifdef ANNUL_IFTRUE_SLOTS
1583 (INSN_ANNULLED_BRANCH_P (jump)
1584 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1585 ? eligible_for_annul_true (jump, i - 1,
1586 XVECEXP (pat, 0, i), flags) :
1588 eligible_for_delay (jump, i -1, XVECEXP (pat, 0, i), flags)))
1591 return (i == XVECLEN (pat, 0));
1594 /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
1595 any insns we wish to place in the delay slot of JUMP. */
1598 redirect_with_delay_list_safe_p (jump, newlabel, delay_list)
1599 rtx jump, newlabel, delay_list;
1604 /* Make sure all the insns in DELAY_LIST would still be
1605 valid after threading the jump. If they are still
1606 valid, then return non-zero. */
1608 flags = get_jump_flags (jump, newlabel);
1609 for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++)
1611 #ifdef ANNUL_IFFALSE_SLOTS
1612 (INSN_ANNULLED_BRANCH_P (jump)
1613 && INSN_FROM_TARGET_P (XEXP (li, 0)))
1614 ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) :
1616 #ifdef ANNUL_IFTRUE_SLOTS
1617 (INSN_ANNULLED_BRANCH_P (jump)
1618 && ! INSN_FROM_TARGET_P (XEXP (li, 0)))
1619 ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) :
1621 eligible_for_delay (jump, i, XEXP (li, 0), flags)))
1624 return (li == NULL);
1628 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1629 the condition tested by INSN is CONDITION and the resources shown in
1630 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1631 from SEQ's delay list, in addition to whatever insns it may execute
1632 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1633 needed while searching for delay slot insns. Return the concatenated
1634 delay list if possible, otherwise, return 0.
1636 SLOTS_TO_FILL is the total number of slots required by INSN, and
1637 PSLOTS_FILLED points to the number filled so far (also the number of
1638 insns in DELAY_LIST). It is updated with the number that have been
1639 filled from the SEQUENCE, if any.
1641 PANNUL_P points to a non-zero value if we already know that we need
1642 to annul INSN. If this routine determines that annulling is needed,
1643 it may set that value non-zero.
1645 PNEW_THREAD points to a location that is to receive the place at which
1646 execution should continue. */
1649 steal_delay_list_from_target (insn, condition, seq, delay_list,
1650 sets, needed, other_needed,
1651 slots_to_fill, pslots_filled, pannul_p,
1653 rtx insn, condition;
1656 struct resources *sets, *needed, *other_needed;
1663 int slots_remaining = slots_to_fill - *pslots_filled;
1664 int total_slots_filled = *pslots_filled;
1665 rtx new_delay_list = 0;
1666 int must_annul = *pannul_p;
1669 /* We can't do anything if there are more delay slots in SEQ than we
1670 can handle, or if we don't know that it will be a taken branch.
1671 We know that it will be a taken branch if it is either an unconditional
1672 branch or a conditional branch with a stricter branch condition.
1674 Also, exit if the branch has more than one set, since then it is computing
1675 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1676 ??? It may be possible to move other sets into INSN in addition to
1677 moving the instructions in the delay slots. */
1679 if (XVECLEN (seq, 0) - 1 > slots_remaining
1680 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))
1681 || ! single_set (XVECEXP (seq, 0, 0)))
1684 for (i = 1; i < XVECLEN (seq, 0); i++)
1686 rtx trial = XVECEXP (seq, 0, i);
1689 if (insn_references_resource_p (trial, sets, 0)
1690 || insn_sets_resource_p (trial, needed, 0)
1691 || insn_sets_resource_p (trial, sets, 0)
1693 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1695 || find_reg_note (trial, REG_CC_USER, NULL_RTX)
1697 /* If TRIAL is from the fallthrough code of an annulled branch insn
1698 in SEQ, we cannot use it. */
1699 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1700 && ! INSN_FROM_TARGET_P (trial)))
1703 /* If this insn was already done (usually in a previous delay slot),
1704 pretend we put it in our delay slot. */
1705 if (redundant_insn (trial, insn, new_delay_list))
1708 /* We will end up re-vectoring this branch, so compute flags
1709 based on jumping to the new label. */
1710 flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
1713 && ((condition == const_true_rtx
1714 || (! insn_sets_resource_p (trial, other_needed, 0)
1715 && ! may_trap_p (PATTERN (trial)))))
1716 ? eligible_for_delay (insn, total_slots_filled, trial, flags)
1718 eligible_for_annul_false (insn, total_slots_filled, trial, flags)))
1720 temp = copy_rtx (trial);
1721 INSN_FROM_TARGET_P (temp) = 1;
1722 new_delay_list = add_to_delay_list (temp, new_delay_list);
1723 total_slots_filled++;
1725 if (--slots_remaining == 0)
1732 /* Show the place to which we will be branching. */
1733 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1735 /* Add any new insns to the delay list and update the count of the
1736 number of slots filled. */
1737 *pslots_filled = total_slots_filled;
1738 *pannul_p = must_annul;
1740 if (delay_list == 0)
1741 return new_delay_list;
1743 for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1744 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1749 /* Similar to steal_delay_list_from_target except that SEQ is on the
1750 fallthrough path of INSN. Here we only do something if the delay insn
1751 of SEQ is an unconditional branch. In that case we steal its delay slot
1752 for INSN since unconditional branches are much easier to fill. */
1755 steal_delay_list_from_fallthrough (insn, condition, seq,
1756 delay_list, sets, needed, other_needed,
1757 slots_to_fill, pslots_filled, pannul_p)
1758 rtx insn, condition;
1761 struct resources *sets, *needed, *other_needed;
1769 flags = get_jump_flags (insn, JUMP_LABEL (insn));
1771 /* We can't do anything if SEQ's delay insn isn't an
1772 unconditional branch. */
1774 if (! simplejump_p (XVECEXP (seq, 0, 0))
1775 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1778 for (i = 1; i < XVECLEN (seq, 0); i++)
1780 rtx trial = XVECEXP (seq, 0, i);
1782 /* If TRIAL sets CC0, stealing it will move it too far from the use
1784 if (insn_references_resource_p (trial, sets, 0)
1785 || insn_sets_resource_p (trial, needed, 0)
1786 || insn_sets_resource_p (trial, sets, 0)
1788 || sets_cc0_p (PATTERN (trial))
1794 /* If this insn was already done, we don't need it. */
1795 if (redundant_insn (trial, insn, delay_list))
1797 delete_from_delay_slot (trial);
1802 && ((condition == const_true_rtx
1803 || (! insn_sets_resource_p (trial, other_needed, 0)
1804 && ! may_trap_p (PATTERN (trial)))))
1805 ? eligible_for_delay (insn, *pslots_filled, trial, flags)
1807 eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
1809 delete_from_delay_slot (trial);
1810 delay_list = add_to_delay_list (trial, delay_list);
1812 if (++(*pslots_filled) == slots_to_fill)
1822 /* Try merging insns starting at THREAD which match exactly the insns in
1825 If all insns were matched and the insn was previously annulling, the
1826 annul bit will be cleared.
1828 For each insn that is merged, if the branch is or will be non-annulling,
1829 we delete the merged insn. */
1832 try_merge_delay_insns (insn, thread)
1835 rtx trial, next_trial;
1836 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1837 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1838 int slot_number = 1;
1839 int num_slots = XVECLEN (PATTERN (insn), 0);
1840 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1841 struct resources set, needed;
1842 rtx merged_insns = 0;
1846 flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
1848 CLEAR_RESOURCE (&needed);
1849 CLEAR_RESOURCE (&set);
1851 /* If this is not an annulling branch, take into account anything needed in
1852 NEXT_TO_MATCH. This prevents two increments from being incorrectly
1853 folded into one. If we are annulling, this would be the correct
1854 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1855 will essentially disable this optimization. This method is somewhat of
1856 a kludge, but I don't see a better way.) */
1858 mark_referenced_resources (next_to_match, &needed, 1);
1860 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1862 rtx pat = PATTERN (trial);
1863 rtx oldtrial = trial;
1865 next_trial = next_nonnote_insn (trial);
1867 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1868 if (GET_CODE (trial) == INSN
1869 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1872 if (GET_CODE (next_to_match) == GET_CODE (trial)
1874 /* We can't share an insn that sets cc0. */
1875 && ! sets_cc0_p (pat)
1877 && ! insn_references_resource_p (trial, &set, 1)
1878 && ! insn_sets_resource_p (trial, &set, 1)
1879 && ! insn_sets_resource_p (trial, &needed, 1)
1880 && (trial = try_split (pat, trial, 0)) != 0
1881 /* Update next_trial, in case try_split succeeded. */
1882 && (next_trial = next_nonnote_insn (trial))
1883 /* Likewise THREAD. */
1884 && (thread = oldtrial == thread ? trial : thread)
1885 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1886 /* Have to test this condition if annul condition is different
1887 from (and less restrictive than) non-annulling one. */
1888 && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
1893 update_block (trial, thread);
1894 if (trial == thread)
1895 thread = next_active_insn (thread);
1897 delete_insn (trial);
1898 INSN_FROM_TARGET_P (next_to_match) = 0;
1901 merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns);
1903 if (++slot_number == num_slots)
1906 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1908 mark_referenced_resources (next_to_match, &needed, 1);
1911 mark_set_resources (trial, &set, 0, 1);
1912 mark_referenced_resources (trial, &needed, 1);
1915 /* See if we stopped on a filled insn. If we did, try to see if its
1916 delay slots match. */
1917 if (slot_number != num_slots
1918 && trial && GET_CODE (trial) == INSN
1919 && GET_CODE (PATTERN (trial)) == SEQUENCE
1920 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1922 rtx pat = PATTERN (trial);
1923 rtx filled_insn = XVECEXP (pat, 0, 0);
1925 /* Account for resources set/needed by the filled insn. */
1926 mark_set_resources (filled_insn, &set, 0, 1);
1927 mark_referenced_resources (filled_insn, &needed, 1);
1929 for (i = 1; i < XVECLEN (pat, 0); i++)
1931 rtx dtrial = XVECEXP (pat, 0, i);
1933 if (! insn_references_resource_p (dtrial, &set, 1)
1934 && ! insn_sets_resource_p (dtrial, &set, 1)
1935 && ! insn_sets_resource_p (dtrial, &needed, 1)
1937 && ! sets_cc0_p (PATTERN (dtrial))
1939 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1940 && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
1944 update_block (dtrial, thread);
1945 delete_from_delay_slot (dtrial);
1946 INSN_FROM_TARGET_P (next_to_match) = 0;
1949 merged_insns = gen_rtx_INSN_LIST (SImode, dtrial,
1952 if (++slot_number == num_slots)
1955 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1960 /* If all insns in the delay slot have been matched and we were previously
1961 annulling the branch, we need not any more. In that case delete all the
1962 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1963 the delay list so that we know that it isn't only being used at the
1965 if (slot_number == num_slots && annul_p)
1967 for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1969 if (GET_MODE (merged_insns) == SImode)
1971 update_block (XEXP (merged_insns, 0), thread);
1972 delete_from_delay_slot (XEXP (merged_insns, 0));
1976 update_block (XEXP (merged_insns, 0), thread);
1977 delete_insn (XEXP (merged_insns, 0));
1981 INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1983 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1984 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1988 /* See if INSN is redundant with an insn in front of TARGET. Often this
1989 is called when INSN is a candidate for a delay slot of TARGET.
1990 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1991 of INSN. Often INSN will be redundant with an insn in a delay slot of
1992 some previous insn. This happens when we have a series of branches to the
1993 same label; in that case the first insn at the target might want to go
1994 into each of the delay slots.
1996 If we are not careful, this routine can take up a significant fraction
1997 of the total compilation time (4%), but only wins rarely. Hence we
1998 speed this routine up by making two passes. The first pass goes back
1999 until it hits a label and sees if it find an insn with an identical
2000 pattern. Only in this (relatively rare) event does it check for
2003 We do not split insns we encounter. This could cause us not to find a
2004 redundant insn, but the cost of splitting seems greater than the possible
2005 gain in rare cases. */
2008 redundant_insn (insn, target, delay_list)
2013 rtx target_main = target;
2014 rtx ipat = PATTERN (insn);
2016 struct resources needed, set;
2019 /* If INSN has any REG_UNUSED notes, it can't match anything since we
2020 are allowed to not actually assign to such a register. */
2021 if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0)
2024 /* Scan backwards looking for a match. */
2025 for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
2027 if (GET_CODE (trial) == CODE_LABEL)
2030 if (GET_RTX_CLASS (GET_CODE (trial)) != 'i')
2033 pat = PATTERN (trial);
2034 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2037 if (GET_CODE (pat) == SEQUENCE)
2039 /* Stop for a CALL and its delay slots because it is difficult to
2040 track its resource needs correctly. */
2041 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2044 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
2045 slots because it is difficult to track its resource needs
2048 #ifdef INSN_SETS_ARE_DELAYED
2049 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2053 #ifdef INSN_REFERENCES_ARE_DELAYED
2054 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2058 /* See if any of the insns in the delay slot match, updating
2059 resource requirements as we go. */
2060 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2061 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
2062 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat)
2063 && ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX))
2066 /* If found a match, exit this loop early. */
2071 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)
2072 && ! find_reg_note (trial, REG_UNUSED, NULL_RTX))
2076 /* If we didn't find an insn that matches, return 0. */
2080 /* See what resources this insn sets and needs. If they overlap, or
2081 if this insn references CC0, it can't be redundant. */
2083 CLEAR_RESOURCE (&needed);
2084 CLEAR_RESOURCE (&set);
2085 mark_set_resources (insn, &set, 0, 1);
2086 mark_referenced_resources (insn, &needed, 1);
2088 /* If TARGET is a SEQUENCE, get the main insn. */
2089 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2090 target_main = XVECEXP (PATTERN (target), 0, 0);
2092 if (resource_conflicts_p (&needed, &set)
2094 || reg_mentioned_p (cc0_rtx, ipat)
2096 /* The insn requiring the delay may not set anything needed or set by
2098 || insn_sets_resource_p (target_main, &needed, 1)
2099 || insn_sets_resource_p (target_main, &set, 1))
2102 /* Insns we pass may not set either NEEDED or SET, so merge them for
2104 needed.memory |= set.memory;
2105 needed.unch_memory |= set.unch_memory;
2106 IOR_HARD_REG_SET (needed.regs, set.regs);
2108 /* This insn isn't redundant if it conflicts with an insn that either is
2109 or will be in a delay slot of TARGET. */
2113 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
2115 delay_list = XEXP (delay_list, 1);
2118 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2119 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
2120 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
2123 /* Scan backwards until we reach a label or an insn that uses something
2124 INSN sets or sets something insn uses or sets. */
2126 for (trial = PREV_INSN (target);
2127 trial && GET_CODE (trial) != CODE_LABEL;
2128 trial = PREV_INSN (trial))
2130 if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
2131 && GET_CODE (trial) != JUMP_INSN)
2134 pat = PATTERN (trial);
2135 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2138 if (GET_CODE (pat) == SEQUENCE)
2140 /* If this is a CALL_INSN and its delay slots, it is hard to track
2141 the resource needs properly, so give up. */
2142 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2145 /* If this is an INSN or JUMP_INSN with delayed effects, it
2146 is hard to track the resource needs properly, so give up. */
2148 #ifdef INSN_SETS_ARE_DELAYED
2149 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2153 #ifdef INSN_REFERENCES_ARE_DELAYED
2154 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2158 /* See if any of the insns in the delay slot match, updating
2159 resource requirements as we go. */
2160 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2162 rtx candidate = XVECEXP (pat, 0, i);
2164 /* If an insn will be annulled if the branch is false, it isn't
2165 considered as a possible duplicate insn. */
2166 if (rtx_equal_p (PATTERN (candidate), ipat)
2167 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2168 && INSN_FROM_TARGET_P (candidate)))
2170 /* Show that this insn will be used in the sequel. */
2171 INSN_FROM_TARGET_P (candidate) = 0;
2175 /* Unless this is an annulled insn from the target of a branch,
2176 we must stop if it sets anything needed or set by INSN. */
2177 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2178 || ! INSN_FROM_TARGET_P (candidate))
2179 && insn_sets_resource_p (candidate, &needed, 1))
2184 /* If the insn requiring the delay slot conflicts with INSN, we
2186 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
2191 /* See if TRIAL is the same as INSN. */
2192 pat = PATTERN (trial);
2193 if (rtx_equal_p (pat, ipat))
2196 /* Can't go any further if TRIAL conflicts with INSN. */
2197 if (insn_sets_resource_p (trial, &needed, 1))
2205 /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero,
2206 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
2207 is non-zero, we are allowed to fall into this thread; otherwise, we are
2210 If LABEL is used more than one or we pass a label other than LABEL before
2211 finding an active insn, we do not own this thread. */
2214 own_thread_p (thread, label, allow_fallthrough)
2217 int allow_fallthrough;
2222 /* We don't own the function end. */
2226 /* Get the first active insn, or THREAD, if it is an active insn. */
2227 active_insn = next_active_insn (PREV_INSN (thread));
2229 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
2230 if (GET_CODE (insn) == CODE_LABEL
2231 && (insn != label || LABEL_NUSES (insn) != 1))
2234 if (allow_fallthrough)
2237 /* Ensure that we reach a BARRIER before any insn or label. */
2238 for (insn = prev_nonnote_insn (thread);
2239 insn == 0 || GET_CODE (insn) != BARRIER;
2240 insn = prev_nonnote_insn (insn))
2242 || GET_CODE (insn) == CODE_LABEL
2243 || (GET_CODE (insn) == INSN
2244 && GET_CODE (PATTERN (insn)) != USE
2245 && GET_CODE (PATTERN (insn)) != CLOBBER))
2251 /* Find the number of the basic block that starts closest to INSN. Return -1
2252 if we couldn't find such a basic block. */
2255 find_basic_block (insn)
2260 /* Scan backwards to the previous BARRIER. Then see if we can find a
2261 label that starts a basic block. Return the basic block number. */
2263 for (insn = prev_nonnote_insn (insn);
2264 insn && GET_CODE (insn) != BARRIER;
2265 insn = prev_nonnote_insn (insn))
2268 /* The start of the function is basic block zero. */
2272 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
2273 anything other than a CODE_LABEL or note, we can't find this code. */
2274 for (insn = next_nonnote_insn (insn);
2275 insn && GET_CODE (insn) == CODE_LABEL;
2276 insn = next_nonnote_insn (insn))
2278 for (i = 0; i < n_basic_blocks; i++)
2279 if (insn == basic_block_head[i])
2286 /* Called when INSN is being moved from a location near the target of a jump.
2287 We leave a marker of the form (use (INSN)) immediately in front
2288 of WHERE for mark_target_live_regs. These markers will be deleted when
2291 We used to try to update the live status of registers if WHERE is at
2292 the start of a basic block, but that can't work since we may remove a
2293 BARRIER in relax_delay_slots. */
2296 update_block (insn, where)
2302 /* Ignore if this was in a delay slot and it came from the target of
2304 if (INSN_FROM_TARGET_P (insn))
2307 emit_insn_before (gen_rtx_USE (VOIDmode, insn), where);
2309 /* INSN might be making a value live in a block where it didn't use to
2310 be. So recompute liveness information for this block. */
2312 b = find_basic_block (insn);
2317 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
2318 the basic block containing the jump. */
2321 reorg_redirect_jump (jump, nlabel)
2325 int b = find_basic_block (jump);
2330 return redirect_jump (jump, nlabel);
2333 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
2334 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
2335 that reference values used in INSN. If we find one, then we move the
2336 REG_DEAD note to INSN.
2338 This is needed to handle the case where an later insn (after INSN) has a
2339 REG_DEAD note for a register used by INSN, and this later insn subsequently
2340 gets moved before a CODE_LABEL because it is a redundant insn. In this
2341 case, mark_target_live_regs may be confused into thinking the register
2342 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
2345 update_reg_dead_notes (insn, delayed_insn)
2346 rtx insn, delayed_insn;
2350 for (p = next_nonnote_insn (insn); p != delayed_insn;
2351 p = next_nonnote_insn (p))
2352 for (link = REG_NOTES (p); link; link = next)
2354 next = XEXP (link, 1);
2356 if (REG_NOTE_KIND (link) != REG_DEAD
2357 || GET_CODE (XEXP (link, 0)) != REG)
2360 if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
2362 /* Move the REG_DEAD note from P to INSN. */
2363 remove_note (p, link);
2364 XEXP (link, 1) = REG_NOTES (insn);
2365 REG_NOTES (insn) = link;
2370 /* Called when an insn redundant with start_insn is deleted. If there
2371 is a REG_DEAD note for the target of start_insn between start_insn
2372 and stop_insn, then the REG_DEAD note needs to be deleted since the
2373 value no longer dies there.
2375 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
2376 confused into thinking the register is dead. */
2379 fix_reg_dead_note (start_insn, stop_insn)
2380 rtx start_insn, stop_insn;
2384 for (p = next_nonnote_insn (start_insn); p != stop_insn;
2385 p = next_nonnote_insn (p))
2386 for (link = REG_NOTES (p); link; link = next)
2388 next = XEXP (link, 1);
2390 if (REG_NOTE_KIND (link) != REG_DEAD
2391 || GET_CODE (XEXP (link, 0)) != REG)
2394 if (reg_set_p (XEXP (link, 0), PATTERN (start_insn)))
2396 remove_note (p, link);
2402 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
2404 This handles the case of udivmodXi4 instructions which optimize their
2405 output depending on whether any REG_UNUSED notes are present.
2406 we must make sure that INSN calculates as many results as REDUNDANT_INSN
2410 update_reg_unused_notes (insn, redundant_insn)
2411 rtx insn, redundant_insn;
2415 for (link = REG_NOTES (insn); link; link = next)
2417 next = XEXP (link, 1);
2419 if (REG_NOTE_KIND (link) != REG_UNUSED
2420 || GET_CODE (XEXP (link, 0)) != REG)
2423 if (! find_regno_note (redundant_insn, REG_UNUSED,
2424 REGNO (XEXP (link, 0))))
2425 remove_note (insn, link);
2429 /* Marks registers possibly live at the current place being scanned by
2430 mark_target_live_regs. Used only by next two function. */
2432 static HARD_REG_SET current_live_regs;
2434 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
2435 Also only used by the next two functions. */
2437 static HARD_REG_SET pending_dead_regs;
2439 /* Utility function called from mark_target_live_regs via note_stores.
2440 It deadens any CLOBBERed registers and livens any SET registers. */
2443 update_live_status (dest, x)
2447 int first_regno, last_regno;
2450 if (GET_CODE (dest) != REG
2451 && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
2454 if (GET_CODE (dest) == SUBREG)
2455 first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
2457 first_regno = REGNO (dest);
2459 last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
2461 if (GET_CODE (x) == CLOBBER)
2462 for (i = first_regno; i < last_regno; i++)
2463 CLEAR_HARD_REG_BIT (current_live_regs, i);
2465 for (i = first_regno; i < last_regno; i++)
2467 SET_HARD_REG_BIT (current_live_regs, i);
2468 CLEAR_HARD_REG_BIT (pending_dead_regs, i);
2472 /* Similar to next_insn, but ignores insns in the delay slots of
2473 an annulled branch. */
2476 next_insn_no_annul (insn)
2481 /* If INSN is an annulled branch, skip any insns from the target
2483 if (INSN_ANNULLED_BRANCH_P (insn)
2484 && NEXT_INSN (PREV_INSN (insn)) != insn)
2485 while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
2486 insn = NEXT_INSN (insn);
2488 insn = NEXT_INSN (insn);
2489 if (insn && GET_CODE (insn) == INSN
2490 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2491 insn = XVECEXP (PATTERN (insn), 0, 0);
2497 /* A subroutine of mark_target_live_regs. Search forward from TARGET
2498 looking for registers that are set before they are used. These are dead.
2499 Stop after passing a few conditional jumps, and/or a small
2500 number of unconditional branches. */
2503 find_dead_or_set_registers (target, res, jump_target, jump_count, set, needed)
2505 struct resources *res;
2508 struct resources set, needed;
2510 HARD_REG_SET scratch;
2515 for (insn = target; insn; insn = next)
2517 rtx this_jump_insn = insn;
2519 next = NEXT_INSN (insn);
2520 switch (GET_CODE (insn))
2523 /* After a label, any pending dead registers that weren't yet
2524 used can be made dead. */
2525 AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2526 AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2527 CLEAR_HARD_REG_SET (pending_dead_regs);
2529 if (CODE_LABEL_NUMBER (insn) < max_label_num_after_reload)
2531 /* All spill registers are dead at a label, so kill all of the
2532 ones that aren't needed also. */
2533 COPY_HARD_REG_SET (scratch, used_spill_regs);
2534 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2535 AND_COMPL_HARD_REG_SET (res->regs, scratch);
2544 if (GET_CODE (PATTERN (insn)) == USE)
2546 /* If INSN is a USE made by update_block, we care about the
2547 underlying insn. Any registers set by the underlying insn
2548 are live since the insn is being done somewhere else. */
2549 if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2550 mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1);
2552 /* All other USE insns are to be ignored. */
2555 else if (GET_CODE (PATTERN (insn)) == CLOBBER)
2557 else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2559 /* An unconditional jump can be used to fill the delay slot
2560 of a call, so search for a JUMP_INSN in any position. */
2561 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2563 this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
2564 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2573 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2575 if (jump_count++ < 10)
2577 if (simplejump_p (this_jump_insn)
2578 || GET_CODE (PATTERN (this_jump_insn)) == RETURN)
2580 next = JUMP_LABEL (this_jump_insn);
2585 *jump_target = JUMP_LABEL (this_jump_insn);
2588 else if (condjump_p (this_jump_insn)
2589 || condjump_in_parallel_p (this_jump_insn))
2591 struct resources target_set, target_res;
2592 struct resources fallthrough_res;
2594 /* We can handle conditional branches here by following
2595 both paths, and then IOR the results of the two paths
2596 together, which will give us registers that are dead
2597 on both paths. Since this is expensive, we give it
2598 a much higher cost than unconditional branches. The
2599 cost was chosen so that we will follow at most 1
2600 conditional branch. */
2603 if (jump_count >= 10)
2606 mark_referenced_resources (insn, &needed, 1);
2608 /* For an annulled branch, mark_set_resources ignores slots
2609 filled by instructions from the target. This is correct
2610 if the branch is not taken. Since we are following both
2611 paths from the branch, we must also compute correct info
2612 if the branch is taken. We do this by inverting all of
2613 the INSN_FROM_TARGET_P bits, calling mark_set_resources,
2614 and then inverting the INSN_FROM_TARGET_P bits again. */
2616 if (GET_CODE (PATTERN (insn)) == SEQUENCE
2617 && INSN_ANNULLED_BRANCH_P (this_jump_insn))
2619 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
2620 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
2621 = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
2624 mark_set_resources (insn, &target_set, 0, 1);
2626 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
2627 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
2628 = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
2630 mark_set_resources (insn, &set, 0, 1);
2634 mark_set_resources (insn, &set, 0, 1);
2639 COPY_HARD_REG_SET (scratch, target_set.regs);
2640 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2641 AND_COMPL_HARD_REG_SET (target_res.regs, scratch);
2643 fallthrough_res = *res;
2644 COPY_HARD_REG_SET (scratch, set.regs);
2645 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2646 AND_COMPL_HARD_REG_SET (fallthrough_res.regs, scratch);
2648 find_dead_or_set_registers (JUMP_LABEL (this_jump_insn),
2649 &target_res, 0, jump_count,
2650 target_set, needed);
2651 find_dead_or_set_registers (next,
2652 &fallthrough_res, 0, jump_count,
2654 IOR_HARD_REG_SET (fallthrough_res.regs, target_res.regs);
2655 AND_HARD_REG_SET (res->regs, fallthrough_res.regs);
2663 /* Don't try this optimization if we expired our jump count
2664 above, since that would mean there may be an infinite loop
2665 in the function being compiled. */
2671 mark_referenced_resources (insn, &needed, 1);
2672 mark_set_resources (insn, &set, 0, 1);
2674 COPY_HARD_REG_SET (scratch, set.regs);
2675 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2676 AND_COMPL_HARD_REG_SET (res->regs, scratch);
2682 /* Set the resources that are live at TARGET.
2684 If TARGET is zero, we refer to the end of the current function and can
2685 return our precomputed value.
2687 Otherwise, we try to find out what is live by consulting the basic block
2688 information. This is tricky, because we must consider the actions of
2689 reload and jump optimization, which occur after the basic block information
2692 Accordingly, we proceed as follows::
2694 We find the previous BARRIER and look at all immediately following labels
2695 (with no intervening active insns) to see if any of them start a basic
2696 block. If we hit the start of the function first, we use block 0.
2698 Once we have found a basic block and a corresponding first insns, we can
2699 accurately compute the live status from basic_block_live_regs and
2700 reg_renumber. (By starting at a label following a BARRIER, we are immune
2701 to actions taken by reload and jump.) Then we scan all insns between
2702 that point and our target. For each CLOBBER (or for call-clobbered regs
2703 when we pass a CALL_INSN), mark the appropriate registers are dead. For
2704 a SET, mark them as live.
2706 We have to be careful when using REG_DEAD notes because they are not
2707 updated by such things as find_equiv_reg. So keep track of registers
2708 marked as dead that haven't been assigned to, and mark them dead at the
2709 next CODE_LABEL since reload and jump won't propagate values across labels.
2711 If we cannot find the start of a basic block (should be a very rare
2712 case, if it can happen at all), mark everything as potentially live.
2714 Next, scan forward from TARGET looking for things set or clobbered
2715 before they are used. These are not live.
2717 Because we can be called many times on the same target, save our results
2718 in a hash table indexed by INSN_UID. */
2721 mark_target_live_regs (target, res)
2723 struct resources *res;
2727 struct target_info *tinfo;
2731 HARD_REG_SET scratch;
2732 struct resources set, needed;
2734 /* Handle end of function. */
2737 *res = end_of_function_needs;
2741 /* We have to assume memory is needed, but the CC isn't. */
2743 res->volatil = res->unch_memory = 0;
2746 /* See if we have computed this value already. */
2747 for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2748 tinfo; tinfo = tinfo->next)
2749 if (tinfo->uid == INSN_UID (target))
2752 /* Start by getting the basic block number. If we have saved information,
2753 we can get it from there unless the insn at the start of the basic block
2754 has been deleted. */
2755 if (tinfo && tinfo->block != -1
2756 && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
2760 b = find_basic_block (target);
2764 /* If the information is up-to-date, use it. Otherwise, we will
2766 if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
2768 COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
2774 /* Allocate a place to put our results and chain it into the
2776 tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
2777 tinfo->uid = INSN_UID (target);
2779 tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2780 target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
2783 CLEAR_HARD_REG_SET (pending_dead_regs);
2785 /* If we found a basic block, get the live registers from it and update
2786 them with anything set or killed between its start and the insn before
2787 TARGET. Otherwise, we must assume everything is live. */
2790 regset regs_live = basic_block_live_at_start[b];
2793 rtx start_insn, stop_insn;
2795 /* Compute hard regs live at start of block -- this is the real hard regs
2796 marked live, plus live pseudo regs that have been renumbered to
2799 REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live);
2801 EXECUTE_IF_SET_IN_REG_SET
2802 (regs_live, FIRST_PSEUDO_REGISTER, i,
2804 if ((regno = reg_renumber[i]) >= 0)
2806 j < regno + HARD_REGNO_NREGS (regno,
2807 PSEUDO_REGNO_MODE (i));
2809 SET_HARD_REG_BIT (current_live_regs, j);
2812 /* Get starting and ending insn, handling the case where each might
2814 start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2817 if (GET_CODE (start_insn) == INSN
2818 && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2819 start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2821 if (GET_CODE (stop_insn) == INSN
2822 && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2823 stop_insn = next_insn (PREV_INSN (stop_insn));
2825 for (insn = start_insn; insn != stop_insn;
2826 insn = next_insn_no_annul (insn))
2829 rtx real_insn = insn;
2831 /* If this insn is from the target of a branch, it isn't going to
2832 be used in the sequel. If it is used in both cases, this
2833 test will not be true. */
2834 if (INSN_FROM_TARGET_P (insn))
2837 /* If this insn is a USE made by update_block, we care about the
2839 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2840 && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2841 real_insn = XEXP (PATTERN (insn), 0);
2843 if (GET_CODE (real_insn) == CALL_INSN)
2845 /* CALL clobbers all call-used regs that aren't fixed except
2846 sp, ap, and fp. Do this before setting the result of the
2848 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2849 if (call_used_regs[i]
2850 && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2851 && i != ARG_POINTER_REGNUM
2852 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2853 && i != HARD_FRAME_POINTER_REGNUM
2855 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2856 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2858 #ifdef PIC_OFFSET_TABLE_REGNUM
2859 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2862 CLEAR_HARD_REG_BIT (current_live_regs, i);
2864 /* A CALL_INSN sets any global register live, since it may
2865 have been modified by the call. */
2866 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2868 SET_HARD_REG_BIT (current_live_regs, i);
2871 /* Mark anything killed in an insn to be deadened at the next
2872 label. Ignore USE insns; the only REG_DEAD notes will be for
2873 parameters. But they might be early. A CALL_INSN will usually
2874 clobber registers used for parameters. It isn't worth bothering
2875 with the unlikely case when it won't. */
2876 if ((GET_CODE (real_insn) == INSN
2877 && GET_CODE (PATTERN (real_insn)) != USE
2878 && GET_CODE (PATTERN (real_insn)) != CLOBBER)
2879 || GET_CODE (real_insn) == JUMP_INSN
2880 || GET_CODE (real_insn) == CALL_INSN)
2882 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2883 if (REG_NOTE_KIND (link) == REG_DEAD
2884 && GET_CODE (XEXP (link, 0)) == REG
2885 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2887 int first_regno = REGNO (XEXP (link, 0));
2890 + HARD_REGNO_NREGS (first_regno,
2891 GET_MODE (XEXP (link, 0))));
2893 for (i = first_regno; i < last_regno; i++)
2894 SET_HARD_REG_BIT (pending_dead_regs, i);
2897 note_stores (PATTERN (real_insn), update_live_status);
2899 /* If any registers were unused after this insn, kill them.
2900 These notes will always be accurate. */
2901 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2902 if (REG_NOTE_KIND (link) == REG_UNUSED
2903 && GET_CODE (XEXP (link, 0)) == REG
2904 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2906 int first_regno = REGNO (XEXP (link, 0));
2909 + HARD_REGNO_NREGS (first_regno,
2910 GET_MODE (XEXP (link, 0))));
2912 for (i = first_regno; i < last_regno; i++)
2913 CLEAR_HARD_REG_BIT (current_live_regs, i);
2917 else if (GET_CODE (real_insn) == CODE_LABEL)
2919 /* A label clobbers the pending dead registers since neither
2920 reload nor jump will propagate a value across a label. */
2921 AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2922 CLEAR_HARD_REG_SET (pending_dead_regs);
2925 /* The beginning of the epilogue corresponds to the end of the
2926 RTL chain when there are no epilogue insns. Certain resources
2927 are implicitly required at that point. */
2928 else if (GET_CODE (real_insn) == NOTE
2929 && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG)
2930 IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs);
2933 COPY_HARD_REG_SET (res->regs, current_live_regs);
2935 tinfo->bb_tick = bb_ticks[b];
2938 /* We didn't find the start of a basic block. Assume everything
2939 in use. This should happen only extremely rarely. */
2940 SET_HARD_REG_SET (res->regs);
2942 CLEAR_RESOURCE (&set);
2943 CLEAR_RESOURCE (&needed);
2945 jump_insn = find_dead_or_set_registers (target, res, &jump_target, 0,
2948 /* If we hit an unconditional branch, we have another way of finding out
2949 what is live: we can see what is live at the branch target and include
2950 anything used but not set before the branch. The only things that are
2951 live are those that are live using the above test and the test below. */
2955 struct resources new_resources;
2956 rtx stop_insn = next_active_insn (jump_insn);
2958 mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2959 CLEAR_RESOURCE (&set);
2960 CLEAR_RESOURCE (&needed);
2962 /* Include JUMP_INSN in the needed registers. */
2963 for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2965 mark_referenced_resources (insn, &needed, 1);
2967 COPY_HARD_REG_SET (scratch, needed.regs);
2968 AND_COMPL_HARD_REG_SET (scratch, set.regs);
2969 IOR_HARD_REG_SET (new_resources.regs, scratch);
2971 mark_set_resources (insn, &set, 0, 1);
2974 AND_HARD_REG_SET (res->regs, new_resources.regs);
2977 COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2980 /* Scan a function looking for insns that need a delay slot and find insns to
2981 put into the delay slot.
2983 NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2984 as calls). We do these first since we don't want jump insns (that are
2985 easier to fill) to get the only insns that could be used for non-jump insns.
2986 When it is zero, only try to fill JUMP_INSNs.
2988 When slots are filled in this manner, the insns (including the
2989 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2990 it is possible to tell whether a delay slot has really been filled
2991 or not. `final' knows how to deal with this, by communicating
2992 through FINAL_SEQUENCE. */
2995 fill_simple_delay_slots (non_jumps_p)
2998 register rtx insn, pat, trial, next_trial;
3000 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3001 struct resources needed, set;
3002 int slots_to_fill, slots_filled;
3005 for (i = 0; i < num_unfilled_slots; i++)
3008 /* Get the next insn to fill. If it has already had any slots assigned,
3009 we can't do anything with it. Maybe we'll improve this later. */
3011 insn = unfilled_slots_base[i];
3013 || INSN_DELETED_P (insn)
3014 || (GET_CODE (insn) == INSN
3015 && GET_CODE (PATTERN (insn)) == SEQUENCE)
3016 || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
3017 || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
3020 if (GET_CODE (insn) == JUMP_INSN)
3021 flags = get_jump_flags (insn, JUMP_LABEL (insn));
3023 flags = get_jump_flags (insn, NULL_RTX);
3024 slots_to_fill = num_delay_slots (insn);
3025 if (slots_to_fill == 0)
3028 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
3029 says how many. After initialization, first try optimizing
3032 nop add %o7,.-L1,%o7
3036 If this case applies, the delay slot of the call is filled with
3037 the unconditional jump. This is done first to avoid having the
3038 delay slot of the call filled in the backward scan. Also, since
3039 the unconditional jump is likely to also have a delay slot, that
3040 insn must exist when it is subsequently scanned.
3042 This is tried on each insn with delay slots as some machines
3043 have insns which perform calls, but are not represented as
3049 if ((trial = next_active_insn (insn))
3050 && GET_CODE (trial) == JUMP_INSN
3051 && simplejump_p (trial)
3052 && eligible_for_delay (insn, slots_filled, trial, flags)
3053 && no_labels_between_p (insn, trial))
3057 delay_list = add_to_delay_list (trial, delay_list);
3059 /* TRIAL may have had its delay slot filled, then unfilled. When
3060 the delay slot is unfilled, TRIAL is placed back on the unfilled
3061 slots obstack. Unfortunately, it is placed on the end of the
3062 obstack, not in its original location. Therefore, we must search
3063 from entry i + 1 to the end of the unfilled slots obstack to
3064 try and find TRIAL. */
3065 tmp = &unfilled_slots_base[i + 1];
3066 while (*tmp != trial && tmp != unfilled_slots_next)
3069 /* Remove the unconditional jump from consideration for delay slot
3070 filling and unthread it. */
3074 rtx next = NEXT_INSN (trial);
3075 rtx prev = PREV_INSN (trial);
3077 NEXT_INSN (prev) = next;
3079 PREV_INSN (next) = prev;
3083 /* Now, scan backwards from the insn to search for a potential
3084 delay-slot candidate. Stop searching when a label or jump is hit.
3086 For each candidate, if it is to go into the delay slot (moved
3087 forward in execution sequence), it must not need or set any resources
3088 that were set by later insns and must not set any resources that
3089 are needed for those insns.
3091 The delay slot insn itself sets resources unless it is a call
3092 (in which case the called routine, not the insn itself, is doing
3095 if (slots_filled < slots_to_fill)
3097 CLEAR_RESOURCE (&needed);
3098 CLEAR_RESOURCE (&set);
3099 mark_set_resources (insn, &set, 0, 0);
3100 mark_referenced_resources (insn, &needed, 0);
3102 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
3105 next_trial = prev_nonnote_insn (trial);
3107 /* This must be an INSN or CALL_INSN. */
3108 pat = PATTERN (trial);
3110 /* USE and CLOBBER at this level was just for flow; ignore it. */
3111 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3114 /* Check for resource conflict first, to avoid unnecessary
3116 if (! insn_references_resource_p (trial, &set, 1)
3117 && ! insn_sets_resource_p (trial, &set, 1)
3118 && ! insn_sets_resource_p (trial, &needed, 1)
3120 /* Can't separate set of cc0 from its use. */
3121 && ! (reg_mentioned_p (cc0_rtx, pat)
3122 && ! sets_cc0_p (cc0_rtx, pat))
3126 trial = try_split (pat, trial, 1);
3127 next_trial = prev_nonnote_insn (trial);
3128 if (eligible_for_delay (insn, slots_filled, trial, flags))
3130 /* In this case, we are searching backward, so if we
3131 find insns to put on the delay list, we want
3132 to put them at the head, rather than the
3133 tail, of the list. */
3135 update_reg_dead_notes (trial, insn);
3136 delay_list = gen_rtx_INSN_LIST (VOIDmode,
3138 update_block (trial, trial);
3139 delete_insn (trial);
3140 if (slots_to_fill == ++slots_filled)
3146 mark_set_resources (trial, &set, 0, 1);
3147 mark_referenced_resources (trial, &needed, 1);
3151 /* If all needed slots haven't been filled, we come here. */
3153 /* Try to optimize case of jumping around a single insn. */
3154 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
3155 if (slots_filled != slots_to_fill
3157 && GET_CODE (insn) == JUMP_INSN
3158 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
3160 delay_list = optimize_skip (insn);
3166 /* Try to get insns from beyond the insn needing the delay slot.
3167 These insns can neither set or reference resources set in insns being
3168 skipped, cannot set resources in the insn being skipped, and, if this
3169 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
3170 call might not return).
3172 There used to be code which continued past the target label if
3173 we saw all uses of the target label. This code did not work,
3174 because it failed to account for some instructions which were
3175 both annulled and marked as from the target. This can happen as a
3176 result of optimize_skip. Since this code was redundant with
3177 fill_eager_delay_slots anyways, it was just deleted. */
3179 if (slots_filled != slots_to_fill
3180 && (GET_CODE (insn) != JUMP_INSN
3181 || ((condjump_p (insn) || condjump_in_parallel_p (insn))
3182 && ! simplejump_p (insn)
3183 && JUMP_LABEL (insn) != 0)))
3186 int maybe_never = 0;
3187 struct resources needed_at_jump;
3189 CLEAR_RESOURCE (&needed);
3190 CLEAR_RESOURCE (&set);
3192 if (GET_CODE (insn) == CALL_INSN)
3194 mark_set_resources (insn, &set, 0, 1);
3195 mark_referenced_resources (insn, &needed, 1);
3200 mark_set_resources (insn, &set, 0, 1);
3201 mark_referenced_resources (insn, &needed, 1);
3202 if (GET_CODE (insn) == JUMP_INSN)
3203 target = JUMP_LABEL (insn);
3206 for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
3208 rtx pat, trial_delay;
3210 next_trial = next_nonnote_insn (trial);
3212 if (GET_CODE (trial) == CODE_LABEL
3213 || GET_CODE (trial) == BARRIER)
3216 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
3217 pat = PATTERN (trial);
3219 /* Stand-alone USE and CLOBBER are just for flow. */
3220 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3223 /* If this already has filled delay slots, get the insn needing
3225 if (GET_CODE (pat) == SEQUENCE)
3226 trial_delay = XVECEXP (pat, 0, 0);
3228 trial_delay = trial;
3230 /* If this is a jump insn to our target, indicate that we have
3231 seen another jump to it. If we aren't handling a conditional
3232 jump, stop our search. Otherwise, compute the needs at its
3233 target and add them to NEEDED. */
3234 if (GET_CODE (trial_delay) == JUMP_INSN)
3238 else if (JUMP_LABEL (trial_delay) != target)
3240 mark_target_live_regs
3241 (next_active_insn (JUMP_LABEL (trial_delay)),
3243 needed.memory |= needed_at_jump.memory;
3244 needed.unch_memory |= needed_at_jump.unch_memory;
3245 IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
3249 /* See if we have a resource problem before we try to
3252 && GET_CODE (pat) != SEQUENCE
3253 && ! insn_references_resource_p (trial, &set, 1)
3254 && ! insn_sets_resource_p (trial, &set, 1)
3255 && ! insn_sets_resource_p (trial, &needed, 1)
3257 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
3259 && ! (maybe_never && may_trap_p (pat))
3260 && (trial = try_split (pat, trial, 0))
3261 && eligible_for_delay (insn, slots_filled, trial, flags))
3263 next_trial = next_nonnote_insn (trial);
3264 delay_list = add_to_delay_list (trial, delay_list);
3267 if (reg_mentioned_p (cc0_rtx, pat))
3268 link_cc0_insns (trial);
3271 delete_insn (trial);
3272 if (slots_to_fill == ++slots_filled)
3277 mark_set_resources (trial, &set, 0, 1);
3278 mark_referenced_resources (trial, &needed, 1);
3280 /* Ensure we don't put insns between the setting of cc and the
3281 comparison by moving a setting of cc into an earlier delay
3282 slot since these insns could clobber the condition code. */
3285 /* If this is a call or jump, we might not get here. */
3286 if (GET_CODE (trial_delay) == CALL_INSN
3287 || GET_CODE (trial_delay) == JUMP_INSN)
3291 /* If there are slots left to fill and our search was stopped by an
3292 unconditional branch, try the insn at the branch target. We can
3293 redirect the branch if it works.
3295 Don't do this if the insn at the branch target is a branch. */
3296 if (slots_to_fill != slots_filled
3298 && GET_CODE (trial) == JUMP_INSN
3299 && simplejump_p (trial)
3300 && (target == 0 || JUMP_LABEL (trial) == target)
3301 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
3302 && ! (GET_CODE (next_trial) == INSN
3303 && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
3304 && GET_CODE (next_trial) != JUMP_INSN
3305 && ! insn_references_resource_p (next_trial, &set, 1)
3306 && ! insn_sets_resource_p (next_trial, &set, 1)
3307 && ! insn_sets_resource_p (next_trial, &needed, 1)
3309 && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
3311 && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
3312 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
3313 && eligible_for_delay (insn, slots_filled, next_trial, flags))
3315 rtx new_label = next_active_insn (next_trial);
3318 new_label = get_label_before (new_label);
3320 new_label = find_end_label ();
3323 = add_to_delay_list (copy_rtx (next_trial), delay_list);
3325 reorg_redirect_jump (trial, new_label);
3327 /* If we merged because we both jumped to the same place,
3328 redirect the original insn also. */
3330 reorg_redirect_jump (insn, new_label);
3334 /* If this is an unconditional jump, then try to get insns from the
3335 target of the jump. */
3336 if (GET_CODE (insn) == JUMP_INSN
3337 && simplejump_p (insn)
3338 && slots_filled != slots_to_fill)
3340 = fill_slots_from_thread (insn, const_true_rtx,
3341 next_active_insn (JUMP_LABEL (insn)),
3343 own_thread_p (JUMP_LABEL (insn),
3344 JUMP_LABEL (insn), 0),
3345 slots_to_fill, &slots_filled,
3349 unfilled_slots_base[i]
3350 = emit_delay_sequence (insn, delay_list, slots_filled);
3352 if (slots_to_fill == slots_filled)
3353 unfilled_slots_base[i] = 0;
3355 note_delay_statistics (slots_filled, 0);
3358 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3359 /* See if the epilogue needs any delay slots. Try to fill them if so.
3360 The only thing we can do is scan backwards from the end of the
3361 function. If we did this in a previous pass, it is incorrect to do it
3363 if (current_function_epilogue_delay_list)
3366 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
3367 if (slots_to_fill == 0)
3371 CLEAR_RESOURCE (&set);
3373 /* The frame pointer and stack pointer are needed at the beginning of
3374 the epilogue, so instructions setting them can not be put in the
3375 epilogue delay slot. However, everything else needed at function
3376 end is safe, so we don't want to use end_of_function_needs here. */
3377 CLEAR_RESOURCE (&needed);
3378 if (frame_pointer_needed)
3380 SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
3381 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3382 SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
3384 #ifdef EXIT_IGNORE_STACK
3385 if (! EXIT_IGNORE_STACK)
3387 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3390 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3392 #ifdef EPILOGUE_USES
3393 for (i = 0; i <FIRST_PSEUDO_REGISTER; i++)
3395 if (EPILOGUE_USES (i))
3396 SET_HARD_REG_BIT (needed.regs, i);
3400 for (trial = get_last_insn (); ! stop_search_p (trial, 1);
3401 trial = PREV_INSN (trial))
3403 if (GET_CODE (trial) == NOTE)
3405 pat = PATTERN (trial);
3406 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3409 if (! insn_references_resource_p (trial, &set, 1)
3410 && ! insn_sets_resource_p (trial, &needed, 1)
3411 && ! insn_sets_resource_p (trial, &set, 1)
3413 /* Don't want to mess with cc0 here. */
3414 && ! reg_mentioned_p (cc0_rtx, pat)
3418 trial = try_split (pat, trial, 1);
3419 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
3421 /* Here as well we are searching backward, so put the
3422 insns we find on the head of the list. */
3424 current_function_epilogue_delay_list
3425 = gen_rtx_INSN_LIST (VOIDmode, trial,
3426 current_function_epilogue_delay_list);
3427 mark_referenced_resources (trial, &end_of_function_needs, 1);
3428 update_block (trial, trial);
3429 delete_insn (trial);
3431 /* Clear deleted bit so final.c will output the insn. */
3432 INSN_DELETED_P (trial) = 0;
3434 if (slots_to_fill == ++slots_filled)
3440 mark_set_resources (trial, &set, 0, 1);
3441 mark_referenced_resources (trial, &needed, 1);
3444 note_delay_statistics (slots_filled, 0);
3448 /* Try to find insns to place in delay slots.
3450 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
3451 or is an unconditional branch if CONDITION is const_true_rtx.
3452 *PSLOTS_FILLED is updated with the number of slots that we have filled.
3454 THREAD is a flow-of-control, either the insns to be executed if the
3455 branch is true or if the branch is false, THREAD_IF_TRUE says which.
3457 OPPOSITE_THREAD is the thread in the opposite direction. It is used
3458 to see if any potential delay slot insns set things needed there.
3460 LIKELY is non-zero if it is extremely likely that the branch will be
3461 taken and THREAD_IF_TRUE is set. This is used for the branch at the
3462 end of a loop back up to the top.
3464 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
3465 thread. I.e., it is the fallthrough code of our jump or the target of the
3466 jump when we are the only jump going there.
3468 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
3469 case, we can only take insns from the head of the thread for our delay
3470 slot. We then adjust the jump to point after the insns we have taken. */
3473 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
3474 thread_if_true, own_thread,
3475 slots_to_fill, pslots_filled, delay_list)
3478 rtx thread, opposite_thread;
3482 int slots_to_fill, *pslots_filled;
3486 struct resources opposite_needed, set, needed;
3492 /* Validate our arguments. */
3493 if ((condition == const_true_rtx && ! thread_if_true)
3494 || (! own_thread && ! thread_if_true))
3497 flags = get_jump_flags (insn, JUMP_LABEL (insn));
3499 /* If our thread is the end of subroutine, we can't get any delay
3504 /* If this is an unconditional branch, nothing is needed at the
3505 opposite thread. Otherwise, compute what is needed there. */
3506 if (condition == const_true_rtx)
3507 CLEAR_RESOURCE (&opposite_needed);
3509 mark_target_live_regs (opposite_thread, &opposite_needed);
3511 /* If the insn at THREAD can be split, do it here to avoid having to
3512 update THREAD and NEW_THREAD if it is done in the loop below. Also
3513 initialize NEW_THREAD. */
3515 new_thread = thread = try_split (PATTERN (thread), thread, 0);
3517 /* Scan insns at THREAD. We are looking for an insn that can be removed
3518 from THREAD (it neither sets nor references resources that were set
3519 ahead of it and it doesn't set anything needs by the insns ahead of
3520 it) and that either can be placed in an annulling insn or aren't
3521 needed at OPPOSITE_THREAD. */
3523 CLEAR_RESOURCE (&needed);
3524 CLEAR_RESOURCE (&set);
3526 /* If we do not own this thread, we must stop as soon as we find
3527 something that we can't put in a delay slot, since all we can do
3528 is branch into THREAD at a later point. Therefore, labels stop
3529 the search if this is not the `true' thread. */
3531 for (trial = thread;
3532 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
3533 trial = next_nonnote_insn (trial))
3537 /* If we have passed a label, we no longer own this thread. */
3538 if (GET_CODE (trial) == CODE_LABEL)
3544 pat = PATTERN (trial);
3545 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3548 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
3549 don't separate or copy insns that set and use CC0. */
3550 if (! insn_references_resource_p (trial, &set, 1)
3551 && ! insn_sets_resource_p (trial, &set, 1)
3552 && ! insn_sets_resource_p (trial, &needed, 1)
3554 && ! (reg_mentioned_p (cc0_rtx, pat)
3555 && (! own_thread || ! sets_cc0_p (pat)))
3561 /* If TRIAL is redundant with some insn before INSN, we don't
3562 actually need to add it to the delay list; we can merely pretend
3564 if ((prior_insn = redundant_insn (trial, insn, delay_list)))
3566 fix_reg_dead_note (prior_insn, insn);
3569 update_block (trial, thread);
3570 if (trial == thread)
3572 thread = next_active_insn (thread);
3573 if (new_thread == trial)
3574 new_thread = thread;
3577 delete_insn (trial);
3581 update_reg_unused_notes (prior_insn, trial);
3582 new_thread = next_active_insn (trial);
3588 /* There are two ways we can win: If TRIAL doesn't set anything
3589 needed at the opposite thread and can't trap, or if it can
3590 go into an annulled delay slot. */
3591 if (condition == const_true_rtx
3592 || (! insn_sets_resource_p (trial, &opposite_needed, 1)
3593 && ! may_trap_p (pat)))
3596 trial = try_split (pat, trial, 0);
3597 if (new_thread == old_trial)
3599 if (thread == old_trial)
3601 pat = PATTERN (trial);
3602 if (eligible_for_delay (insn, *pslots_filled, trial, flags))
3606 #ifdef ANNUL_IFTRUE_SLOTS
3609 #ifdef ANNUL_IFFALSE_SLOTS
3615 trial = try_split (pat, trial, 0);
3616 if (new_thread == old_trial)
3618 if (thread == old_trial)
3620 pat = PATTERN (trial);
3622 ? eligible_for_annul_false (insn, *pslots_filled, trial, flags)
3623 : eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
3631 if (reg_mentioned_p (cc0_rtx, pat))
3632 link_cc0_insns (trial);
3635 /* If we own this thread, delete the insn. If this is the
3636 destination of a branch, show that a basic block status
3637 may have been updated. In any case, mark the new
3638 starting point of this thread. */
3641 update_block (trial, thread);
3642 if (trial == thread)
3644 thread = next_active_insn (thread);
3645 if (new_thread == trial)
3646 new_thread = thread;
3648 delete_insn (trial);
3651 new_thread = next_active_insn (trial);
3653 temp = own_thread ? trial : copy_rtx (trial);
3655 INSN_FROM_TARGET_P (temp) = 1;
3657 delay_list = add_to_delay_list (temp, delay_list);
3659 mark_set_resources (trial, &opposite_needed, 0, 1);
3661 if (slots_to_fill == ++(*pslots_filled))
3663 /* Even though we have filled all the slots, we
3664 may be branching to a location that has a
3665 redundant insn. Skip any if so. */
3666 while (new_thread && ! own_thread
3667 && ! insn_sets_resource_p (new_thread, &set, 1)
3668 && ! insn_sets_resource_p (new_thread, &needed, 1)
3669 && ! insn_references_resource_p (new_thread,
3672 = redundant_insn (new_thread, insn,
3675 /* We know we do not own the thread, so no need
3676 to call update_block and delete_insn. */
3677 fix_reg_dead_note (prior_insn, insn);
3678 update_reg_unused_notes (prior_insn, new_thread);
3679 new_thread = next_active_insn (new_thread);
3689 /* This insn can't go into a delay slot. */
3691 mark_set_resources (trial, &set, 0, 1);
3692 mark_referenced_resources (trial, &needed, 1);
3694 /* Ensure we don't put insns between the setting of cc and the comparison
3695 by moving a setting of cc into an earlier delay slot since these insns
3696 could clobber the condition code. */
3699 /* If this insn is a register-register copy and the next insn has
3700 a use of our destination, change it to use our source. That way,
3701 it will become a candidate for our delay slot the next time
3702 through this loop. This case occurs commonly in loops that
3705 We could check for more complex cases than those tested below,
3706 but it doesn't seem worth it. It might also be a good idea to try
3707 to swap the two insns. That might do better.
3709 We can't do this if the next insn modifies our destination, because
3710 that would make the replacement into the insn invalid. We also can't
3711 do this if it modifies our source, because it might be an earlyclobber
3712 operand. This latter test also prevents updating the contents of
3715 if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
3716 && GET_CODE (SET_SRC (pat)) == REG
3717 && GET_CODE (SET_DEST (pat)) == REG)
3719 rtx next = next_nonnote_insn (trial);
3721 if (next && GET_CODE (next) == INSN
3722 && GET_CODE (PATTERN (next)) != USE
3723 && ! reg_set_p (SET_DEST (pat), next)
3724 && ! reg_set_p (SET_SRC (pat), next)
3725 && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
3726 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
3730 /* If we stopped on a branch insn that has delay slots, see if we can
3731 steal some of the insns in those slots. */
3732 if (trial && GET_CODE (trial) == INSN
3733 && GET_CODE (PATTERN (trial)) == SEQUENCE
3734 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
3736 /* If this is the `true' thread, we will want to follow the jump,
3737 so we can only do this if we have taken everything up to here. */
3738 if (thread_if_true && trial == new_thread
3739 && ! insn_references_resource_p (XVECEXP (PATTERN (trial), 0, 0),
3740 &opposite_needed, 0))
3742 = steal_delay_list_from_target (insn, condition, PATTERN (trial),
3743 delay_list, &set, &needed,
3744 &opposite_needed, slots_to_fill,
3745 pslots_filled, &must_annul,
3747 else if (! thread_if_true)
3749 = steal_delay_list_from_fallthrough (insn, condition,
3751 delay_list, &set, &needed,
3752 &opposite_needed, slots_to_fill,
3753 pslots_filled, &must_annul);
3756 /* If we haven't found anything for this delay slot and it is very
3757 likely that the branch will be taken, see if the insn at our target
3758 increments or decrements a register with an increment that does not
3759 depend on the destination register. If so, try to place the opposite
3760 arithmetic insn after the jump insn and put the arithmetic insn in the
3761 delay slot. If we can't do this, return. */
3762 if (delay_list == 0 && likely && new_thread
3763 && GET_CODE (new_thread) == INSN
3764 && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
3765 && asm_noperands (PATTERN (new_thread)) < 0)
3767 rtx pat = PATTERN (new_thread);
3772 pat = PATTERN (trial);
3774 if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
3775 || ! eligible_for_delay (insn, 0, trial, flags))
3778 dest = SET_DEST (pat), src = SET_SRC (pat);
3779 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
3780 && rtx_equal_p (XEXP (src, 0), dest)
3781 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
3783 rtx other = XEXP (src, 1);
3787 /* If this is a constant adjustment, use the same code with
3788 the negated constant. Otherwise, reverse the sense of the
3790 if (GET_CODE (other) == CONST_INT)
3791 new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
3792 negate_rtx (GET_MODE (src), other));
3794 new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
3795 GET_MODE (src), dest, other);
3797 ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith),
3800 if (recog_memoized (ninsn) < 0
3801 || (insn_extract (ninsn),
3802 ! constrain_operands (INSN_CODE (ninsn), 1)))
3804 delete_insn (ninsn);
3810 update_block (trial, thread);
3811 if (trial == thread)
3813 thread = next_active_insn (thread);
3814 if (new_thread == trial)
3815 new_thread = thread;
3817 delete_insn (trial);
3820 new_thread = next_active_insn (trial);
3822 ninsn = own_thread ? trial : copy_rtx (trial);
3824 INSN_FROM_TARGET_P (ninsn) = 1;
3826 delay_list = add_to_delay_list (ninsn, NULL_RTX);
3831 if (delay_list && must_annul)
3832 INSN_ANNULLED_BRANCH_P (insn) = 1;
3834 /* If we are to branch into the middle of this thread, find an appropriate
3835 label or make a new one if none, and redirect INSN to it. If we hit the
3836 end of the function, use the end-of-function label. */
3837 if (new_thread != thread)
3841 if (! thread_if_true)
3844 if (new_thread && GET_CODE (new_thread) == JUMP_INSN
3845 && (simplejump_p (new_thread)
3846 || GET_CODE (PATTERN (new_thread)) == RETURN)
3847 && redirect_with_delay_list_safe_p (insn,
3848 JUMP_LABEL (new_thread),
3850 new_thread = follow_jumps (JUMP_LABEL (new_thread));
3852 if (new_thread == 0)
3853 label = find_end_label ();
3854 else if (GET_CODE (new_thread) == CODE_LABEL)
3857 label = get_label_before (new_thread);
3859 reorg_redirect_jump (insn, label);
3865 /* Make another attempt to find insns to place in delay slots.
3867 We previously looked for insns located in front of the delay insn
3868 and, for non-jump delay insns, located behind the delay insn.
3870 Here only try to schedule jump insns and try to move insns from either
3871 the target or the following insns into the delay slot. If annulling is
3872 supported, we will be likely to do this. Otherwise, we can do this only
3876 fill_eager_delay_slots ()
3880 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3882 for (i = 0; i < num_unfilled_slots; i++)
3885 rtx target_label, insn_at_target, fallthrough_insn;
3888 int own_fallthrough;
3889 int prediction, slots_to_fill, slots_filled;
3891 insn = unfilled_slots_base[i];
3893 || INSN_DELETED_P (insn)
3894 || GET_CODE (insn) != JUMP_INSN
3895 || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
3898 slots_to_fill = num_delay_slots (insn);
3899 if (slots_to_fill == 0)
3903 target_label = JUMP_LABEL (insn);
3904 condition = get_branch_condition (insn, target_label);
3909 /* Get the next active fallthrough and target insns and see if we own
3910 them. Then see whether the branch is likely true. We don't need
3911 to do a lot of this for unconditional branches. */
3913 insn_at_target = next_active_insn (target_label);
3914 own_target = own_thread_p (target_label, target_label, 0);
3916 if (condition == const_true_rtx)
3918 own_fallthrough = 0;
3919 fallthrough_insn = 0;
3924 fallthrough_insn = next_active_insn (insn);
3925 own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
3926 prediction = mostly_true_jump (insn, condition);
3929 /* If this insn is expected to branch, first try to get insns from our
3930 target, then our fallthrough insns. If it is not, expected to branch,
3931 try the other order. */
3936 = fill_slots_from_thread (insn, condition, insn_at_target,
3937 fallthrough_insn, prediction == 2, 1,
3939 slots_to_fill, &slots_filled, delay_list);
3941 if (delay_list == 0 && own_fallthrough)
3943 /* Even though we didn't find anything for delay slots,
3944 we might have found a redundant insn which we deleted
3945 from the thread that was filled. So we have to recompute
3946 the next insn at the target. */
3947 target_label = JUMP_LABEL (insn);
3948 insn_at_target = next_active_insn (target_label);
3951 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3952 insn_at_target, 0, 0,
3954 slots_to_fill, &slots_filled,
3960 if (own_fallthrough)
3962 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3963 insn_at_target, 0, 0,
3965 slots_to_fill, &slots_filled,
3968 if (delay_list == 0)
3970 = fill_slots_from_thread (insn, condition, insn_at_target,
3971 next_active_insn (insn), 0, 1,
3973 slots_to_fill, &slots_filled,
3978 unfilled_slots_base[i]
3979 = emit_delay_sequence (insn, delay_list, slots_filled);
3981 if (slots_to_fill == slots_filled)
3982 unfilled_slots_base[i] = 0;
3984 note_delay_statistics (slots_filled, 1);
3988 /* Once we have tried two ways to fill a delay slot, make a pass over the
3989 code to try to improve the results and to do such things as more jump
3993 relax_delay_slots (first)
3996 register rtx insn, next, pat;
3997 register rtx trial, delay_insn, target_label;
3999 /* Look at every JUMP_INSN and see if we can improve it. */
4000 for (insn = first; insn; insn = next)
4004 next = next_active_insn (insn);
4006 /* If this is a jump insn, see if it now jumps to a jump, jumps to
4007 the next insn, or jumps to a label that is not the last of a
4008 group of consecutive labels. */
4009 if (GET_CODE (insn) == JUMP_INSN
4010 && (condjump_p (insn) || condjump_in_parallel_p (insn))
4011 && (target_label = JUMP_LABEL (insn)) != 0)
4013 target_label = follow_jumps (target_label);
4014 target_label = prev_label (next_active_insn (target_label));
4016 if (target_label == 0)
4017 target_label = find_end_label ();
4019 if (next_active_insn (target_label) == next
4020 && ! condjump_in_parallel_p (insn))
4026 if (target_label != JUMP_LABEL (insn))
4027 reorg_redirect_jump (insn, target_label);
4029 /* See if this jump branches around a unconditional jump.
4030 If so, invert this jump and point it to the target of the
4032 if (next && GET_CODE (next) == JUMP_INSN
4033 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
4034 && next_active_insn (target_label) == next_active_insn (next)
4035 && no_labels_between_p (insn, next))
4037 rtx label = JUMP_LABEL (next);
4039 /* Be careful how we do this to avoid deleting code or
4040 labels that are momentarily dead. See similar optimization
4043 We also need to ensure we properly handle the case when
4044 invert_jump fails. */
4046 ++LABEL_NUSES (target_label);
4048 ++LABEL_NUSES (label);
4050 if (invert_jump (insn, label))
4057 --LABEL_NUSES (label);
4059 if (--LABEL_NUSES (target_label) == 0)
4060 delete_insn (target_label);
4066 /* If this is an unconditional jump and the previous insn is a
4067 conditional jump, try reversing the condition of the previous
4068 insn and swapping our targets. The next pass might be able to
4071 Don't do this if we expect the conditional branch to be true, because
4072 we would then be making the more common case longer. */
4074 if (GET_CODE (insn) == JUMP_INSN
4075 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
4076 && (other = prev_active_insn (insn)) != 0
4077 && (condjump_p (other) || condjump_in_parallel_p (other))
4078 && no_labels_between_p (other, insn)
4079 && 0 < mostly_true_jump (other,
4080 get_branch_condition (other,
4081 JUMP_LABEL (other))))
4083 rtx other_target = JUMP_LABEL (other);
4084 target_label = JUMP_LABEL (insn);
4086 /* Increment the count of OTHER_TARGET, so it doesn't get deleted
4087 as we move the label. */
4089 ++LABEL_NUSES (other_target);
4091 if (invert_jump (other, target_label))
4092 reorg_redirect_jump (insn, other_target);
4095 --LABEL_NUSES (other_target);
4098 /* Now look only at cases where we have filled a delay slot. */
4099 if (GET_CODE (insn) != INSN
4100 || GET_CODE (PATTERN (insn)) != SEQUENCE)
4103 pat = PATTERN (insn);
4104 delay_insn = XVECEXP (pat, 0, 0);
4106 /* See if the first insn in the delay slot is redundant with some
4107 previous insn. Remove it from the delay slot if so; then set up
4108 to reprocess this insn. */
4109 if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
4111 delete_from_delay_slot (XVECEXP (pat, 0, 1));
4112 next = prev_active_insn (next);
4116 /* Now look only at the cases where we have a filled JUMP_INSN. */
4117 if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4118 || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
4119 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
4122 target_label = JUMP_LABEL (delay_insn);
4126 /* If this jump goes to another unconditional jump, thread it, but
4127 don't convert a jump into a RETURN here. */
4128 trial = follow_jumps (target_label);
4129 /* We use next_real_insn instead of next_active_insn, so that
4130 the special USE insns emitted by reorg won't be ignored.
4131 If they are ignored, then they will get deleted if target_label
4132 is now unreachable, and that would cause mark_target_live_regs
4134 trial = prev_label (next_real_insn (trial));
4135 if (trial == 0 && target_label != 0)
4136 trial = find_end_label ();
4138 if (trial != target_label
4139 && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
4141 reorg_redirect_jump (delay_insn, trial);
4142 target_label = trial;
4145 /* If the first insn at TARGET_LABEL is redundant with a previous
4146 insn, redirect the jump to the following insn process again. */
4147 trial = next_active_insn (target_label);
4148 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
4149 && redundant_insn (trial, insn, 0))
4153 /* Figure out where to emit the special USE insn so we don't
4154 later incorrectly compute register live/death info. */
4155 tmp = next_active_insn (trial);
4157 tmp = find_end_label ();
4159 /* Insert the special USE insn and update dataflow info. */
4160 update_block (trial, tmp);
4162 /* Now emit a label before the special USE insn, and
4163 redirect our jump to the new label. */
4164 target_label = get_label_before (PREV_INSN (tmp));
4165 reorg_redirect_jump (delay_insn, target_label);
4170 /* Similarly, if it is an unconditional jump with one insn in its
4171 delay list and that insn is redundant, thread the jump. */
4172 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
4173 && XVECLEN (PATTERN (trial), 0) == 2
4174 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
4175 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
4176 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
4177 && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
4179 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
4180 if (target_label == 0)
4181 target_label = find_end_label ();
4183 if (redirect_with_delay_slots_safe_p (delay_insn, target_label,
4186 reorg_redirect_jump (delay_insn, target_label);
4193 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
4194 && prev_active_insn (target_label) == insn
4195 && ! condjump_in_parallel_p (delay_insn)
4197 /* If the last insn in the delay slot sets CC0 for some insn,
4198 various code assumes that it is in a delay slot. We could
4199 put it back where it belonged and delete the register notes,
4200 but it doesn't seem worthwhile in this uncommon case. */
4201 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
4202 REG_CC_USER, NULL_RTX)
4208 /* All this insn does is execute its delay list and jump to the
4209 following insn. So delete the jump and just execute the delay
4212 We do this by deleting the INSN containing the SEQUENCE, then
4213 re-emitting the insns separately, and then deleting the jump.
4214 This allows the count of the jump target to be properly
4217 /* Clear the from target bit, since these insns are no longer
4219 for (i = 0; i < XVECLEN (pat, 0); i++)
4220 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
4222 trial = PREV_INSN (insn);
4224 emit_insn_after (pat, trial);
4225 delete_scheduled_jump (delay_insn);
4229 /* See if this is an unconditional jump around a single insn which is
4230 identical to the one in its delay slot. In this case, we can just
4231 delete the branch and the insn in its delay slot. */
4232 if (next && GET_CODE (next) == INSN
4233 && prev_label (next_active_insn (next)) == target_label
4234 && simplejump_p (insn)
4235 && XVECLEN (pat, 0) == 2
4236 && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
4242 /* See if this jump (with its delay slots) branches around another
4243 jump (without delay slots). If so, invert this jump and point
4244 it to the target of the second jump. We cannot do this for
4245 annulled jumps, though. Again, don't convert a jump to a RETURN
4247 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
4248 && next && GET_CODE (next) == JUMP_INSN
4249 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
4250 && next_active_insn (target_label) == next_active_insn (next)
4251 && no_labels_between_p (insn, next))
4253 rtx label = JUMP_LABEL (next);
4254 rtx old_label = JUMP_LABEL (delay_insn);
4257 label = find_end_label ();
4259 if (redirect_with_delay_slots_safe_p (delay_insn, label, insn))
4261 /* Be careful how we do this to avoid deleting code or labels
4262 that are momentarily dead. See similar optimization in
4265 ++LABEL_NUSES (old_label);
4267 if (invert_jump (delay_insn, label))
4271 /* Must update the INSN_FROM_TARGET_P bits now that
4272 the branch is reversed, so that mark_target_live_regs
4273 will handle the delay slot insn correctly. */
4274 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
4276 rtx slot = XVECEXP (PATTERN (insn), 0, i);
4277 INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
4284 if (old_label && --LABEL_NUSES (old_label) == 0)
4285 delete_insn (old_label);
4290 /* If we own the thread opposite the way this insn branches, see if we
4291 can merge its delay slots with following insns. */
4292 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4293 && own_thread_p (NEXT_INSN (insn), 0, 1))
4294 try_merge_delay_insns (insn, next);
4295 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4296 && own_thread_p (target_label, target_label, 0))
4297 try_merge_delay_insns (insn, next_active_insn (target_label));
4299 /* If we get here, we haven't deleted INSN. But we may have deleted
4300 NEXT, so recompute it. */
4301 next = next_active_insn (insn);
4307 /* Look for filled jumps to the end of function label. We can try to convert
4308 them into RETURN insns if the insns in the delay slot are valid for the
4312 make_return_insns (first)
4315 rtx insn, jump_insn, pat;
4316 rtx real_return_label = end_of_function_label;
4319 /* See if there is a RETURN insn in the function other than the one we
4320 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
4321 into a RETURN to jump to it. */
4322 for (insn = first; insn; insn = NEXT_INSN (insn))
4323 if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
4325 real_return_label = get_label_before (insn);
4329 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
4330 was equal to END_OF_FUNCTION_LABEL. */
4331 LABEL_NUSES (real_return_label)++;
4333 /* Clear the list of insns to fill so we can use it. */
4334 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4336 for (insn = first; insn; insn = NEXT_INSN (insn))
4340 /* Only look at filled JUMP_INSNs that go to the end of function
4342 if (GET_CODE (insn) != INSN
4343 || GET_CODE (PATTERN (insn)) != SEQUENCE
4344 || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4345 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
4348 pat = PATTERN (insn);
4349 jump_insn = XVECEXP (pat, 0, 0);
4351 /* If we can't make the jump into a RETURN, try to redirect it to the best
4352 RETURN and go on to the next insn. */
4353 if (! reorg_redirect_jump (jump_insn, NULL_RTX))
4355 /* Make sure redirecting the jump will not invalidate the delay
4357 if (redirect_with_delay_slots_safe_p (jump_insn,
4360 reorg_redirect_jump (jump_insn, real_return_label);
4364 /* See if this RETURN can accept the insns current in its delay slot.
4365 It can if it has more or an equal number of slots and the contents
4366 of each is valid. */
4368 flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
4369 slots = num_delay_slots (jump_insn);
4370 if (slots >= XVECLEN (pat, 0) - 1)
4372 for (i = 1; i < XVECLEN (pat, 0); i++)
4374 #ifdef ANNUL_IFFALSE_SLOTS
4375 (INSN_ANNULLED_BRANCH_P (jump_insn)
4376 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4377 ? eligible_for_annul_false (jump_insn, i - 1,
4378 XVECEXP (pat, 0, i), flags) :
4380 #ifdef ANNUL_IFTRUE_SLOTS
4381 (INSN_ANNULLED_BRANCH_P (jump_insn)
4382 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4383 ? eligible_for_annul_true (jump_insn, i - 1,
4384 XVECEXP (pat, 0, i), flags) :
4386 eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i), flags)))
4392 if (i == XVECLEN (pat, 0))
4395 /* We have to do something with this insn. If it is an unconditional
4396 RETURN, delete the SEQUENCE and output the individual insns,
4397 followed by the RETURN. Then set things up so we try to find
4398 insns for its delay slots, if it needs some. */
4399 if (GET_CODE (PATTERN (jump_insn)) == RETURN)
4401 rtx prev = PREV_INSN (insn);
4404 for (i = 1; i < XVECLEN (pat, 0); i++)
4405 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
4407 insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
4408 emit_barrier_after (insn);
4411 obstack_ptr_grow (&unfilled_slots_obstack, insn);
4414 /* It is probably more efficient to keep this with its current
4415 delay slot as a branch to a RETURN. */
4416 reorg_redirect_jump (jump_insn, real_return_label);
4419 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
4420 new delay slots we have created. */
4421 if (--LABEL_NUSES (real_return_label) == 0)
4422 delete_insn (real_return_label);
4424 fill_simple_delay_slots (1);
4425 fill_simple_delay_slots (0);
4429 /* Try to find insns to place in delay slots. */
4432 dbr_schedule (first, file)
4436 rtx insn, next, epilogue_insn = 0;
4439 int old_flag_no_peephole = flag_no_peephole;
4441 /* Execute `final' once in prescan mode to delete any insns that won't be
4442 used. Don't let final try to do any peephole optimization--it will
4443 ruin dataflow information for this pass. */
4445 flag_no_peephole = 1;
4446 final (first, 0, NO_DEBUG, 1, 1);
4447 flag_no_peephole = old_flag_no_peephole;
4450 /* If the current function has no insns other than the prologue and
4451 epilogue, then do not try to fill any delay slots. */
4452 if (n_basic_blocks == 0)
4455 /* Find the highest INSN_UID and allocate and initialize our map from
4456 INSN_UID's to position in code. */
4457 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
4459 if (INSN_UID (insn) > max_uid)
4460 max_uid = INSN_UID (insn);
4461 if (GET_CODE (insn) == NOTE
4462 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
4463 epilogue_insn = insn;
4466 uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
4467 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
4468 uid_to_ruid[INSN_UID (insn)] = i;
4470 /* Initialize the list of insns that need filling. */
4471 if (unfilled_firstobj == 0)
4473 gcc_obstack_init (&unfilled_slots_obstack);
4474 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4477 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
4481 INSN_ANNULLED_BRANCH_P (insn) = 0;
4482 INSN_FROM_TARGET_P (insn) = 0;
4484 /* Skip vector tables. We can't get attributes for them. */
4485 if (GET_CODE (insn) == JUMP_INSN
4486 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
4487 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
4490 if (num_delay_slots (insn) > 0)
4491 obstack_ptr_grow (&unfilled_slots_obstack, insn);
4493 /* Ensure all jumps go to the last of a set of consecutive labels. */
4494 if (GET_CODE (insn) == JUMP_INSN
4495 && (condjump_p (insn) || condjump_in_parallel_p (insn))
4496 && JUMP_LABEL (insn) != 0
4497 && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
4498 != JUMP_LABEL (insn)))
4499 redirect_jump (insn, target);
4502 /* Indicate what resources are required to be valid at the end of the current
4503 function. The condition code never is and memory always is. If the
4504 frame pointer is needed, it is and so is the stack pointer unless
4505 EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
4506 stack pointer is. Registers used to return the function value are
4507 needed. Registers holding global variables are needed. */
4509 end_of_function_needs.cc = 0;
4510 end_of_function_needs.memory = 1;
4511 end_of_function_needs.unch_memory = 0;
4512 CLEAR_HARD_REG_SET (end_of_function_needs.regs);
4514 if (frame_pointer_needed)
4516 SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
4517 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4518 SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM);
4520 #ifdef EXIT_IGNORE_STACK
4521 if (! EXIT_IGNORE_STACK)
4523 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4526 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4528 if (current_function_return_rtx != 0)
4529 mark_referenced_resources (current_function_return_rtx,
4530 &end_of_function_needs, 1);
4532 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4534 #ifdef EPILOGUE_USES
4535 || EPILOGUE_USES (i)
4538 SET_HARD_REG_BIT (end_of_function_needs.regs, i);
4540 /* The registers required to be live at the end of the function are
4541 represented in the flow information as being dead just prior to
4542 reaching the end of the function. For example, the return of a value
4543 might be represented by a USE of the return register immediately
4544 followed by an unconditional jump to the return label where the
4545 return label is the end of the RTL chain. The end of the RTL chain
4546 is then taken to mean that the return register is live.
4548 This sequence is no longer maintained when epilogue instructions are
4549 added to the RTL chain. To reconstruct the original meaning, the
4550 start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
4551 point where these registers become live (start_of_epilogue_needs).
4552 If epilogue instructions are present, the registers set by those
4553 instructions won't have been processed by flow. Thus, those
4554 registers are additionally required at the end of the RTL chain
4555 (end_of_function_needs). */
4557 start_of_epilogue_needs = end_of_function_needs;
4559 while ((epilogue_insn = next_nonnote_insn (epilogue_insn)))
4560 mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1);
4562 /* Show we haven't computed an end-of-function label yet. */
4563 end_of_function_label = 0;
4565 /* Allocate and initialize the tables used by mark_target_live_regs. */
4567 = (struct target_info **) alloca ((TARGET_HASH_PRIME
4568 * sizeof (struct target_info *)));
4569 bzero ((char *) target_hash_table,
4570 TARGET_HASH_PRIME * sizeof (struct target_info *));
4572 bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
4573 bzero ((char *) bb_ticks, n_basic_blocks * sizeof (int));
4575 /* Initialize the statistics for this function. */
4576 bzero ((char *) num_insns_needing_delays, sizeof num_insns_needing_delays);
4577 bzero ((char *) num_filled_delays, sizeof num_filled_delays);
4579 /* Now do the delay slot filling. Try everything twice in case earlier
4580 changes make more slots fillable. */
4582 for (reorg_pass_number = 0;
4583 reorg_pass_number < MAX_REORG_PASSES;
4584 reorg_pass_number++)
4586 fill_simple_delay_slots (1);
4587 fill_simple_delay_slots (0);
4588 fill_eager_delay_slots ();
4589 relax_delay_slots (first);
4592 /* Delete any USE insns made by update_block; subsequent passes don't need
4593 them or know how to deal with them. */
4594 for (insn = first; insn; insn = next)
4596 next = NEXT_INSN (insn);
4598 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
4599 && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
4600 next = delete_insn (insn);
4603 /* If we made an end of function label, indicate that it is now
4604 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
4605 If it is now unused, delete it. */
4606 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
4607 delete_insn (end_of_function_label);
4610 if (HAVE_return && end_of_function_label != 0)
4611 make_return_insns (first);
4614 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4616 /* It is not clear why the line below is needed, but it does seem to be. */
4617 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4619 /* Reposition the prologue and epilogue notes in case we moved the
4620 prologue/epilogue insns. */
4621 reposition_prologue_and_epilogue_notes (first);
4625 register int i, j, need_comma;
4627 for (reorg_pass_number = 0;
4628 reorg_pass_number < MAX_REORG_PASSES;
4629 reorg_pass_number++)
4631 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
4632 for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
4635 fprintf (file, ";; Reorg function #%d\n", i);
4637 fprintf (file, ";; %d insns needing delay slots\n;; ",
4638 num_insns_needing_delays[i][reorg_pass_number]);
4640 for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
4641 if (num_filled_delays[i][j][reorg_pass_number])
4644 fprintf (file, ", ");
4646 fprintf (file, "%d got %d delays",
4647 num_filled_delays[i][j][reorg_pass_number], j);
4649 fprintf (file, "\n");
4654 /* For all JUMP insns, fill in branch prediction notes, so that during
4655 assembler output a target can set branch prediction bits in the code.
4656 We have to do this now, as up until this point the destinations of
4657 JUMPS can be moved around and changed, but past right here that cannot
4659 for (insn = first; insn; insn = NEXT_INSN (insn))
4663 if (GET_CODE (insn) != JUMP_INSN)
4666 pred_flags = get_jump_flags (insn, JUMP_LABEL (insn));
4667 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED,
4668 GEN_INT (pred_flags),
4672 #endif /* DELAY_SLOTS */