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 The TMS320C3x and C4x have three branch delay slots. When the three
65 slots are filled, the branch penalty is zero. Most insns can fill the
66 delay slots except jump insns.
68 Three techniques for filling delay slots have been implemented so far:
70 (1) `fill_simple_delay_slots' is the simplest, most efficient way
71 to fill delay slots. This pass first looks for insns which come
72 from before the branch and which are safe to execute after the
73 branch. Then it searches after the insn requiring delay slots or,
74 in the case of a branch, for insns that are after the point at
75 which the branch merges into the fallthrough code, if such a point
76 exists. When such insns are found, the branch penalty decreases
77 and no code expansion takes place.
79 (2) `fill_eager_delay_slots' is more complicated: it is used for
80 scheduling conditional jumps, or for scheduling jumps which cannot
81 be filled using (1). A machine need not have annulled jumps to use
82 this strategy, but it helps (by keeping more options open).
83 `fill_eager_delay_slots' tries to guess the direction the branch
84 will go; if it guesses right 100% of the time, it can reduce the
85 branch penalty as much as `fill_simple_delay_slots' does. If it
86 guesses wrong 100% of the time, it might as well schedule nops (or
87 on the m88k, unexpose the branch slot). When
88 `fill_eager_delay_slots' takes insns from the fall-through path of
89 the jump, usually there is no code expansion; when it takes insns
90 from the branch target, there is code expansion if it is not the
91 only way to reach that target.
93 (3) `relax_delay_slots' uses a set of rules to simplify code that
94 has been reorganized by (1) and (2). It finds cases where
95 conditional test can be eliminated, jumps can be threaded, extra
96 insns can be eliminated, etc. It is the job of (1) and (2) to do a
97 good job of scheduling locally; `relax_delay_slots' takes care of
98 making the various individual schedules work well together. It is
99 especially tuned to handle the control flow interactions of branch
100 insns. It does nothing for insns with delay slots that do not
103 On machines that use CC0, we are very conservative. We will not make
104 a copy of an insn involving CC0 since we want to maintain a 1-1
105 correspondence between the insn that sets and uses CC0. The insns are
106 allowed to be separated by placing an insn that sets CC0 (but not an insn
107 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
108 delay slot. In that case, we point each insn at the other with REG_CC_USER
109 and REG_CC_SETTER notes. Note that these restrictions affect very few
110 machines because most RISC machines with delay slots will not use CC0
111 (the RT is the only known exception at this point).
115 The Acorn Risc Machine can conditionally execute most insns, so
116 it is profitable to move single insns into a position to execute
117 based on the condition code of the previous insn.
119 The HP-PA can conditionally nullify insns, providing a similar
120 effect to the ARM, differing mostly in which insn is "in charge". */
126 #include "insn-config.h"
127 #include "conditions.h"
128 #include "hard-reg-set.h"
129 #include "basic-block.h"
131 #include "insn-flags.h"
136 #include "insn-attr.h"
141 #define obstack_chunk_alloc xmalloc
142 #define obstack_chunk_free free
144 #ifndef ANNUL_IFTRUE_SLOTS
145 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
147 #ifndef ANNUL_IFFALSE_SLOTS
148 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
151 /* Insns which have delay slots that have not yet been filled. */
153 static struct obstack unfilled_slots_obstack;
154 static rtx *unfilled_firstobj;
156 /* Define macros to refer to the first and last slot containing unfilled
157 insns. These are used because the list may move and its address
158 should be recomputed at each use. */
160 #define unfilled_slots_base \
161 ((rtx *) obstack_base (&unfilled_slots_obstack))
163 #define unfilled_slots_next \
164 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
166 /* This structure is used to indicate which hardware resources are set or
167 needed by insns so far. */
171 char memory; /* Insn sets or needs a memory location. */
172 char unch_memory; /* Insn sets of needs a "unchanging" MEM. */
173 char volatil; /* Insn sets or needs a volatile memory loc. */
174 char cc; /* Insn sets or needs the condition codes. */
175 HARD_REG_SET regs; /* Which registers are set or needed. */
178 /* Macro to clear all resources. */
179 #define CLEAR_RESOURCE(RES) \
180 do { (RES)->memory = (RES)->unch_memory = (RES)->volatil = (RES)->cc = 0; \
181 CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
183 /* Indicates what resources are required at the beginning of the epilogue. */
184 static struct resources start_of_epilogue_needs;
186 /* Indicates what resources are required at function end. */
187 static struct resources end_of_function_needs;
189 /* Points to the label before the end of the function. */
190 static rtx end_of_function_label;
192 /* This structure is used to record liveness information at the targets or
193 fallthrough insns of branches. We will most likely need the information
194 at targets again, so save them in a hash table rather than recomputing them
199 int uid; /* INSN_UID of target. */
200 struct target_info *next; /* Next info for same hash bucket. */
201 HARD_REG_SET live_regs; /* Registers live at target. */
202 int block; /* Basic block number containing target. */
203 int bb_tick; /* Generation count of basic block info. */
206 #define TARGET_HASH_PRIME 257
208 /* Define the hash table itself. */
209 static struct target_info **target_hash_table;
211 /* For each basic block, we maintain a generation number of its basic
212 block info, which is updated each time we move an insn from the
213 target of a jump. This is the generation number indexed by block
216 static int *bb_ticks;
218 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
219 not always monotonically increase. */
220 static int *uid_to_ruid;
222 /* Highest valid index in `uid_to_ruid'. */
225 static void mark_referenced_resources PROTO((rtx, struct resources *, int));
226 static void mark_set_resources PROTO((rtx, struct resources *, int, int));
227 static int stop_search_p PROTO((rtx, int));
228 static int resource_conflicts_p PROTO((struct resources *,
229 struct resources *));
230 static int insn_references_resource_p PROTO((rtx, struct resources *, int));
231 static int insn_sets_resource_p PROTO((rtx, struct resources *, int));
232 static rtx find_end_label PROTO((void));
233 static rtx emit_delay_sequence PROTO((rtx, rtx, int));
234 static rtx add_to_delay_list PROTO((rtx, rtx));
235 static rtx delete_from_delay_slot PROTO((rtx));
236 static void delete_scheduled_jump PROTO((rtx));
237 static void note_delay_statistics PROTO((int, int));
238 static rtx optimize_skip PROTO((rtx));
239 static int get_jump_flags PROTO((rtx, rtx));
240 static int rare_destination PROTO((rtx));
241 static int mostly_true_jump PROTO((rtx, rtx));
242 static rtx get_branch_condition PROTO((rtx, rtx));
243 static int condition_dominates_p PROTO((rtx, rtx));
244 static rtx steal_delay_list_from_target PROTO((rtx, rtx, rtx, rtx,
248 int, int *, int *, rtx *));
249 static rtx steal_delay_list_from_fallthrough PROTO((rtx, rtx, rtx, rtx,
254 static void try_merge_delay_insns PROTO((rtx, rtx));
255 static rtx redundant_insn PROTO((rtx, rtx, rtx));
256 static int own_thread_p PROTO((rtx, rtx, int));
257 static int find_basic_block PROTO((rtx));
258 static void update_block PROTO((rtx, rtx));
259 static int reorg_redirect_jump PROTO((rtx, rtx));
260 static void update_reg_dead_notes PROTO((rtx, rtx));
261 static void fix_reg_dead_note PROTO((rtx, rtx));
262 static void update_reg_unused_notes PROTO((rtx, rtx));
263 static void update_live_status PROTO((rtx, rtx));
264 static rtx next_insn_no_annul PROTO((rtx));
265 static rtx find_dead_or_set_registers PROTO ((rtx, struct resources *, rtx *,
266 int, struct resources,
268 static void mark_target_live_regs PROTO((rtx, struct resources *));
269 static void fill_simple_delay_slots PROTO((int));
270 static rtx fill_slots_from_thread PROTO((rtx, rtx, rtx, rtx, int, int,
271 int, int, int *, rtx));
272 static void fill_eager_delay_slots PROTO((void));
273 static void relax_delay_slots PROTO((rtx));
274 static void make_return_insns PROTO((rtx));
275 static int redirect_with_delay_slots_safe_p PROTO ((rtx, rtx, rtx));
276 static int redirect_with_delay_list_safe_p PROTO ((rtx, rtx, rtx));
278 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
279 which resources are references by the insn. If INCLUDE_DELAYED_EFFECTS
280 is TRUE, resources used by the called routine will be included for
284 mark_referenced_resources (x, res, include_delayed_effects)
286 register struct resources *res;
287 register int include_delayed_effects;
289 register enum rtx_code code = GET_CODE (x);
291 register char *format_ptr;
293 /* Handle leaf items for which we set resource flags. Also, special-case
294 CALL, SET and CLOBBER operators. */
306 if (GET_CODE (SUBREG_REG (x)) != REG)
307 mark_referenced_resources (SUBREG_REG (x), res, 0);
310 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
311 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
312 for (i = regno; i < last_regno; i++)
313 SET_HARD_REG_BIT (res->regs, i);
318 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
319 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
323 /* If this memory shouldn't change, it really isn't referencing
325 if (RTX_UNCHANGING_P (x))
326 res->unch_memory = 1;
329 res->volatil = MEM_VOLATILE_P (x);
331 /* Mark registers used to access memory. */
332 mark_referenced_resources (XEXP (x, 0), res, 0);
339 case UNSPEC_VOLATILE:
341 /* Traditional asm's are always volatile. */
350 res->volatil = MEM_VOLATILE_P (x);
352 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
353 We can not just fall through here since then we would be confused
354 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
355 traditional asms unlike their normal usage. */
357 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
358 mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
362 /* The first operand will be a (MEM (xxx)) but doesn't really reference
363 memory. The second operand may be referenced, though. */
364 mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
365 mark_referenced_resources (XEXP (x, 1), res, 0);
369 /* Usually, the first operand of SET is set, not referenced. But
370 registers used to access memory are referenced. SET_DEST is
371 also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
373 mark_referenced_resources (SET_SRC (x), res, 0);
376 if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
377 mark_referenced_resources (x, res, 0);
378 else if (GET_CODE (x) == SUBREG)
380 if (GET_CODE (x) == MEM)
381 mark_referenced_resources (XEXP (x, 0), res, 0);
388 if (include_delayed_effects)
390 /* A CALL references memory, the frame pointer if it exists, the
391 stack pointer, any global registers and any registers given in
392 USE insns immediately in front of the CALL.
394 However, we may have moved some of the parameter loading insns
395 into the delay slot of this CALL. If so, the USE's for them
396 don't count and should be skipped. */
397 rtx insn = PREV_INSN (x);
400 rtx next = NEXT_INSN (x);
403 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
404 if (NEXT_INSN (insn) != x)
406 next = NEXT_INSN (NEXT_INSN (insn));
407 sequence = PATTERN (NEXT_INSN (insn));
408 seq_size = XVECLEN (sequence, 0);
409 if (GET_CODE (sequence) != SEQUENCE)
414 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
415 if (frame_pointer_needed)
417 SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
418 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
419 SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM);
423 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
425 SET_HARD_REG_BIT (res->regs, i);
427 /* Check for a NOTE_INSN_SETJMP. If it exists, then we must
428 assume that this call can need any register.
430 This is done to be more conservative about how we handle setjmp.
431 We assume that they both use and set all registers. Using all
432 registers ensures that a register will not be considered dead
433 just because it crosses a setjmp call. A register should be
434 considered dead only if the setjmp call returns non-zero. */
435 if (next && GET_CODE (next) == NOTE
436 && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
437 SET_HARD_REG_SET (res->regs);
442 for (link = CALL_INSN_FUNCTION_USAGE (x);
444 link = XEXP (link, 1))
445 if (GET_CODE (XEXP (link, 0)) == USE)
447 for (i = 1; i < seq_size; i++)
449 rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
450 if (GET_CODE (slot_pat) == SET
451 && rtx_equal_p (SET_DEST (slot_pat),
452 SET_DEST (XEXP (link, 0))))
456 mark_referenced_resources (SET_DEST (XEXP (link, 0)),
462 /* ... fall through to other INSN processing ... */
467 #ifdef INSN_REFERENCES_ARE_DELAYED
468 if (! include_delayed_effects
469 && INSN_REFERENCES_ARE_DELAYED (x))
473 /* No special processing, just speed up. */
474 mark_referenced_resources (PATTERN (x), res, include_delayed_effects);
481 /* Process each sub-expression and flag what it needs. */
482 format_ptr = GET_RTX_FORMAT (code);
483 for (i = 0; i < GET_RTX_LENGTH (code); i++)
484 switch (*format_ptr++)
487 mark_referenced_resources (XEXP (x, i), res, include_delayed_effects);
491 for (j = 0; j < XVECLEN (x, i); j++)
492 mark_referenced_resources (XVECEXP (x, i, j), res,
493 include_delayed_effects);
498 /* Given X, a part of an insn, and a pointer to a `struct resource',
499 RES, indicate which resources are modified by the insn. If
500 INCLUDE_DELAYED_EFFECTS is nonzero, also mark resources potentially
501 set by the called routine.
503 If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
504 objects are being referenced instead of set.
506 We never mark the insn as modifying the condition code unless it explicitly
507 SETs CC0 even though this is not totally correct. The reason for this is
508 that we require a SET of CC0 to immediately precede the reference to CC0.
509 So if some other insn sets CC0 as a side-effect, we know it cannot affect
510 our computation and thus may be placed in a delay slot. */
513 mark_set_resources (x, res, in_dest, include_delayed_effects)
515 register struct resources *res;
517 int include_delayed_effects;
519 register enum rtx_code code;
521 register char *format_ptr;
539 /* These don't set any resources. */
548 /* Called routine modifies the condition code, memory, any registers
549 that aren't saved across calls, global registers and anything
550 explicitly CLOBBERed immediately after the CALL_INSN. */
552 if (include_delayed_effects)
554 rtx next = NEXT_INSN (x);
555 rtx prev = PREV_INSN (x);
558 res->cc = res->memory = 1;
559 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
560 if (call_used_regs[i] || global_regs[i])
561 SET_HARD_REG_BIT (res->regs, i);
563 /* If X is part of a delay slot sequence, then NEXT should be
564 the first insn after the sequence. */
565 if (NEXT_INSN (prev) != x)
566 next = NEXT_INSN (NEXT_INSN (prev));
568 for (link = CALL_INSN_FUNCTION_USAGE (x);
569 link; link = XEXP (link, 1))
570 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
571 mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1, 0);
573 /* Check for a NOTE_INSN_SETJMP. If it exists, then we must
574 assume that this call can clobber any register. */
575 if (next && GET_CODE (next) == NOTE
576 && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP)
577 SET_HARD_REG_SET (res->regs);
580 /* ... and also what its RTL says it modifies, if anything. */
585 /* An insn consisting of just a CLOBBER (or USE) is just for flow
586 and doesn't actually do anything, so we ignore it. */
588 #ifdef INSN_SETS_ARE_DELAYED
589 if (! include_delayed_effects
590 && INSN_SETS_ARE_DELAYED (x))
595 if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
600 /* If the source of a SET is a CALL, this is actually done by
601 the called routine. So only include it if we are to include the
602 effects of the calling routine. */
604 mark_set_resources (SET_DEST (x), res,
605 (include_delayed_effects
606 || GET_CODE (SET_SRC (x)) != CALL),
609 mark_set_resources (SET_SRC (x), res, 0, 0);
613 mark_set_resources (XEXP (x, 0), res, 1, 0);
617 for (i = 0; i < XVECLEN (x, 0); i++)
618 if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0))
619 && INSN_FROM_TARGET_P (XVECEXP (x, 0, i))))
620 mark_set_resources (XVECEXP (x, 0, i), res, 0,
621 include_delayed_effects);
628 mark_set_resources (XEXP (x, 0), res, 1, 0);
632 mark_set_resources (XEXP (x, 0), res, in_dest, 0);
633 mark_set_resources (XEXP (x, 1), res, 0, 0);
634 mark_set_resources (XEXP (x, 2), res, 0, 0);
641 res->unch_memory = RTX_UNCHANGING_P (x);
642 res->volatil = MEM_VOLATILE_P (x);
645 mark_set_resources (XEXP (x, 0), res, 0, 0);
651 if (GET_CODE (SUBREG_REG (x)) != REG)
652 mark_set_resources (SUBREG_REG (x), res,
653 in_dest, include_delayed_effects);
656 int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
657 int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
658 for (i = regno; i < last_regno; i++)
659 SET_HARD_REG_BIT (res->regs, i);
666 for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
667 SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
674 /* Process each sub-expression and flag what it needs. */
675 format_ptr = GET_RTX_FORMAT (code);
676 for (i = 0; i < GET_RTX_LENGTH (code); i++)
677 switch (*format_ptr++)
680 mark_set_resources (XEXP (x, i), res, in_dest, include_delayed_effects);
684 for (j = 0; j < XVECLEN (x, i); j++)
685 mark_set_resources (XVECEXP (x, i, j), res, in_dest,
686 include_delayed_effects);
691 /* Return TRUE if this insn should stop the search for insn to fill delay
692 slots. LABELS_P indicates that labels should terminate the search.
693 In all cases, jumps terminate the search. */
696 stop_search_p (insn, labels_p)
703 switch (GET_CODE (insn))
717 /* OK unless it contains a delay slot or is an `asm' insn of some type.
718 We don't know anything about these. */
719 return (GET_CODE (PATTERN (insn)) == SEQUENCE
720 || GET_CODE (PATTERN (insn)) == ASM_INPUT
721 || asm_noperands (PATTERN (insn)) >= 0);
728 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
729 resource set contains a volatile memory reference. Otherwise, return FALSE. */
732 resource_conflicts_p (res1, res2)
733 struct resources *res1, *res2;
735 if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
736 || (res1->unch_memory && res2->unch_memory)
737 || res1->volatil || res2->volatil)
741 return (res1->regs & res2->regs) != HARD_CONST (0);
746 for (i = 0; i < HARD_REG_SET_LONGS; i++)
747 if ((res1->regs[i] & res2->regs[i]) != 0)
754 /* Return TRUE if any resource marked in RES, a `struct resources', is
755 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
756 routine is using those resources.
758 We compute this by computing all the resources referenced by INSN and
759 seeing if this conflicts with RES. It might be faster to directly check
760 ourselves, and this is the way it used to work, but it means duplicating
761 a large block of complex code. */
764 insn_references_resource_p (insn, res, include_delayed_effects)
766 register struct resources *res;
767 int include_delayed_effects;
769 struct resources insn_res;
771 CLEAR_RESOURCE (&insn_res);
772 mark_referenced_resources (insn, &insn_res, include_delayed_effects);
773 return resource_conflicts_p (&insn_res, res);
776 /* Return TRUE if INSN modifies resources that are marked in RES.
777 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
778 included. CC0 is only modified if it is explicitly set; see comments
779 in front of mark_set_resources for details. */
782 insn_sets_resource_p (insn, res, include_delayed_effects)
784 register struct resources *res;
785 int include_delayed_effects;
787 struct resources insn_sets;
789 CLEAR_RESOURCE (&insn_sets);
790 mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
791 return resource_conflicts_p (&insn_sets, res);
794 /* Find a label at the end of the function or before a RETURN. If there is
802 /* If we found one previously, return it. */
803 if (end_of_function_label)
804 return end_of_function_label;
806 /* Otherwise, see if there is a label at the end of the function. If there
807 is, it must be that RETURN insns aren't needed, so that is our return
808 label and we don't have to do anything else. */
810 insn = get_last_insn ();
811 while (GET_CODE (insn) == NOTE
812 || (GET_CODE (insn) == INSN
813 && (GET_CODE (PATTERN (insn)) == USE
814 || GET_CODE (PATTERN (insn)) == CLOBBER)))
815 insn = PREV_INSN (insn);
817 /* When a target threads its epilogue we might already have a
818 suitable return insn. If so put a label before it for the
819 end_of_function_label. */
820 if (GET_CODE (insn) == BARRIER
821 && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
822 && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
824 rtx temp = PREV_INSN (PREV_INSN (insn));
825 end_of_function_label = gen_label_rtx ();
826 LABEL_NUSES (end_of_function_label) = 0;
828 /* Put the label before an USE insns that may proceed the RETURN insn. */
829 while (GET_CODE (temp) == USE)
830 temp = PREV_INSN (temp);
832 emit_label_after (end_of_function_label, temp);
835 else if (GET_CODE (insn) == CODE_LABEL)
836 end_of_function_label = insn;
839 /* Otherwise, make a new label and emit a RETURN and BARRIER,
841 end_of_function_label = gen_label_rtx ();
842 LABEL_NUSES (end_of_function_label) = 0;
843 emit_label (end_of_function_label);
847 /* The return we make may have delay slots too. */
848 rtx insn = gen_return ();
849 insn = emit_jump_insn (insn);
851 if (num_delay_slots (insn) > 0)
852 obstack_ptr_grow (&unfilled_slots_obstack, insn);
857 /* Show one additional use for this label so it won't go away until
859 ++LABEL_NUSES (end_of_function_label);
861 return end_of_function_label;
864 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
865 the pattern of INSN with the SEQUENCE.
867 Chain the insns so that NEXT_INSN of each insn in the sequence points to
868 the next and NEXT_INSN of the last insn in the sequence points to
869 the first insn after the sequence. Similarly for PREV_INSN. This makes
870 it easier to scan all insns.
872 Returns the SEQUENCE that replaces INSN. */
875 emit_delay_sequence (insn, list, length)
884 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
885 rtvec seqv = rtvec_alloc (length + 1);
886 rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
887 rtx seq_insn = make_insn_raw (seq);
888 rtx first = get_insns ();
889 rtx last = get_last_insn ();
891 /* Make a copy of the insn having delay slots. */
892 rtx delay_insn = copy_rtx (insn);
894 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
895 confuse further processing. Update LAST in case it was the last insn.
896 We will put the BARRIER back in later. */
897 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
899 delete_insn (NEXT_INSN (insn));
900 last = get_last_insn ();
904 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
905 NEXT_INSN (seq_insn) = NEXT_INSN (insn);
906 PREV_INSN (seq_insn) = PREV_INSN (insn);
909 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
912 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
914 /* Note the calls to set_new_first_and_last_insn must occur after
915 SEQ_INSN has been completely spliced into the insn stream.
917 Otherwise CUR_INSN_UID will get set to an incorrect value because
918 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */
920 set_new_first_and_last_insn (first, seq_insn);
923 set_new_first_and_last_insn (seq_insn, last);
925 /* Build our SEQUENCE and rebuild the insn chain. */
926 XVECEXP (seq, 0, 0) = delay_insn;
927 INSN_DELETED_P (delay_insn) = 0;
928 PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
930 for (li = list; li; li = XEXP (li, 1), i++)
932 rtx tem = XEXP (li, 0);
935 /* Show that this copy of the insn isn't deleted. */
936 INSN_DELETED_P (tem) = 0;
938 XVECEXP (seq, 0, i) = tem;
939 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
940 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
942 /* Remove any REG_DEAD notes because we can't rely on them now
943 that the insn has been moved. */
944 for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
945 if (REG_NOTE_KIND (note) == REG_DEAD)
946 XEXP (note, 0) = const0_rtx;
949 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
951 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
952 last insn in that SEQUENCE to point to us. Similarly for the first
953 insn in the following insn if it is a SEQUENCE. */
955 if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
956 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
957 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
958 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
961 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
962 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
963 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
965 /* If there used to be a BARRIER, put it back. */
967 emit_barrier_after (seq_insn);
975 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
976 be in the order in which the insns are to be executed. */
979 add_to_delay_list (insn, delay_list)
983 /* If we have an empty list, just make a new list element. If
984 INSN has its block number recorded, clear it since we may
985 be moving the insn to a new block. */
989 struct target_info *tinfo;
991 for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME];
992 tinfo; tinfo = tinfo->next)
993 if (tinfo->uid == INSN_UID (insn))
999 return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
1002 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
1004 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
1009 /* Delete INSN from the delay slot of the insn that it is in. This may
1010 produce an insn without anything in its delay slots. */
1013 delete_from_delay_slot (insn)
1016 rtx trial, seq_insn, seq, prev;
1020 /* We first must find the insn containing the SEQUENCE with INSN in its
1021 delay slot. Do this by finding an insn, TRIAL, where
1022 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
1025 PREV_INSN (NEXT_INSN (trial)) == trial;
1026 trial = NEXT_INSN (trial))
1029 seq_insn = PREV_INSN (NEXT_INSN (trial));
1030 seq = PATTERN (seq_insn);
1032 /* Create a delay list consisting of all the insns other than the one
1033 we are deleting (unless we were the only one). */
1034 if (XVECLEN (seq, 0) > 2)
1035 for (i = 1; i < XVECLEN (seq, 0); i++)
1036 if (XVECEXP (seq, 0, i) != insn)
1037 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
1039 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
1040 list, and rebuild the delay list if non-empty. */
1041 prev = PREV_INSN (seq_insn);
1042 trial = XVECEXP (seq, 0, 0);
1043 delete_insn (seq_insn);
1044 add_insn_after (trial, prev);
1046 if (GET_CODE (trial) == JUMP_INSN
1047 && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
1048 emit_barrier_after (trial);
1050 /* If there are any delay insns, remit them. Otherwise clear the
1053 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2);
1055 INSN_ANNULLED_BRANCH_P (trial) = 0;
1057 INSN_FROM_TARGET_P (insn) = 0;
1059 /* Show we need to fill this insn again. */
1060 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);
1627 /* DELAY_LIST is a list of insns that have already been placed into delay
1628 slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
1629 If not, return 0; otherwise return 1. */
1632 check_annul_list_true_false (annul_true_p, delay_list)
1640 for (temp = delay_list; temp; temp = XEXP (temp, 1))
1642 rtx trial = XEXP (temp, 0);
1644 if ((annul_true_p && INSN_FROM_TARGET_P (trial))
1645 || (!annul_true_p && !INSN_FROM_TARGET_P (trial)))
1653 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1654 the condition tested by INSN is CONDITION and the resources shown in
1655 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1656 from SEQ's delay list, in addition to whatever insns it may execute
1657 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1658 needed while searching for delay slot insns. Return the concatenated
1659 delay list if possible, otherwise, return 0.
1661 SLOTS_TO_FILL is the total number of slots required by INSN, and
1662 PSLOTS_FILLED points to the number filled so far (also the number of
1663 insns in DELAY_LIST). It is updated with the number that have been
1664 filled from the SEQUENCE, if any.
1666 PANNUL_P points to a non-zero value if we already know that we need
1667 to annul INSN. If this routine determines that annulling is needed,
1668 it may set that value non-zero.
1670 PNEW_THREAD points to a location that is to receive the place at which
1671 execution should continue. */
1674 steal_delay_list_from_target (insn, condition, seq, delay_list,
1675 sets, needed, other_needed,
1676 slots_to_fill, pslots_filled, pannul_p,
1678 rtx insn, condition;
1681 struct resources *sets, *needed, *other_needed;
1688 int slots_remaining = slots_to_fill - *pslots_filled;
1689 int total_slots_filled = *pslots_filled;
1690 rtx new_delay_list = 0;
1691 int must_annul = *pannul_p;
1694 struct resources cc_set;
1696 /* We can't do anything if there are more delay slots in SEQ than we
1697 can handle, or if we don't know that it will be a taken branch.
1698 We know that it will be a taken branch if it is either an unconditional
1699 branch or a conditional branch with a stricter branch condition.
1701 Also, exit if the branch has more than one set, since then it is computing
1702 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1703 ??? It may be possible to move other sets into INSN in addition to
1704 moving the instructions in the delay slots.
1706 We can not steal the delay list if one of the instructions in the
1707 current delay_list modifies the condition codes and the jump in the
1708 sequence is a conditional jump. We can not do this because we can
1709 not change the direction of the jump because the condition codes
1710 will effect the direction of the jump in the sequence. */
1712 CLEAR_RESOURCE (&cc_set);
1713 for (temp = delay_list; temp; temp = XEXP (temp, 1))
1715 rtx trial = XEXP (temp, 0);
1717 mark_set_resources (trial, &cc_set, 0, 1);
1718 if (insn_references_resource_p (XVECEXP (seq , 0, 0), &cc_set, 0))
1722 if (XVECLEN (seq, 0) - 1 > slots_remaining
1723 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))
1724 || ! single_set (XVECEXP (seq, 0, 0)))
1727 for (i = 1; i < XVECLEN (seq, 0); i++)
1729 rtx trial = XVECEXP (seq, 0, i);
1732 if (insn_references_resource_p (trial, sets, 0)
1733 || insn_sets_resource_p (trial, needed, 0)
1734 || insn_sets_resource_p (trial, sets, 0)
1736 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1738 || find_reg_note (trial, REG_CC_USER, NULL_RTX)
1740 /* If TRIAL is from the fallthrough code of an annulled branch insn
1741 in SEQ, we cannot use it. */
1742 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1743 && ! INSN_FROM_TARGET_P (trial)))
1746 /* If this insn was already done (usually in a previous delay slot),
1747 pretend we put it in our delay slot. */
1748 if (redundant_insn (trial, insn, new_delay_list))
1751 /* We will end up re-vectoring this branch, so compute flags
1752 based on jumping to the new label. */
1753 flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
1756 && ((condition == const_true_rtx
1757 || (! insn_sets_resource_p (trial, other_needed, 0)
1758 && ! may_trap_p (PATTERN (trial)))))
1759 ? eligible_for_delay (insn, total_slots_filled, trial, flags)
1760 : (must_annul || (delay_list == NULL && new_delay_list == NULL))
1762 check_annul_list_true_false (0, delay_list)
1763 && check_annul_list_true_false (0, new_delay_list)
1764 && eligible_for_annul_false (insn, total_slots_filled,
1769 temp = copy_rtx (trial);
1770 INSN_FROM_TARGET_P (temp) = 1;
1771 new_delay_list = add_to_delay_list (temp, new_delay_list);
1772 total_slots_filled++;
1774 if (--slots_remaining == 0)
1781 /* Show the place to which we will be branching. */
1782 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1784 /* Add any new insns to the delay list and update the count of the
1785 number of slots filled. */
1786 *pslots_filled = total_slots_filled;
1790 if (delay_list == 0)
1791 return new_delay_list;
1793 for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1794 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1799 /* Similar to steal_delay_list_from_target except that SEQ is on the
1800 fallthrough path of INSN. Here we only do something if the delay insn
1801 of SEQ is an unconditional branch. In that case we steal its delay slot
1802 for INSN since unconditional branches are much easier to fill. */
1805 steal_delay_list_from_fallthrough (insn, condition, seq,
1806 delay_list, sets, needed, other_needed,
1807 slots_to_fill, pslots_filled, pannul_p)
1808 rtx insn, condition;
1811 struct resources *sets, *needed, *other_needed;
1818 int must_annul = *pannul_p;
1821 flags = get_jump_flags (insn, JUMP_LABEL (insn));
1823 /* We can't do anything if SEQ's delay insn isn't an
1824 unconditional branch. */
1826 if (! simplejump_p (XVECEXP (seq, 0, 0))
1827 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1830 for (i = 1; i < XVECLEN (seq, 0); i++)
1832 rtx trial = XVECEXP (seq, 0, i);
1834 /* If TRIAL sets CC0, stealing it will move it too far from the use
1836 if (insn_references_resource_p (trial, sets, 0)
1837 || insn_sets_resource_p (trial, needed, 0)
1838 || insn_sets_resource_p (trial, sets, 0)
1840 || sets_cc0_p (PATTERN (trial))
1846 /* If this insn was already done, we don't need it. */
1847 if (redundant_insn (trial, insn, delay_list))
1849 delete_from_delay_slot (trial);
1854 && ((condition == const_true_rtx
1855 || (! insn_sets_resource_p (trial, other_needed, 0)
1856 && ! may_trap_p (PATTERN (trial)))))
1857 ? eligible_for_delay (insn, *pslots_filled, trial, flags)
1858 : (must_annul || delay_list == NULL) && (must_annul = 1,
1859 check_annul_list_true_false (1, delay_list)
1860 && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
1864 delete_from_delay_slot (trial);
1865 delay_list = add_to_delay_list (trial, delay_list);
1867 if (++(*pslots_filled) == slots_to_fill)
1880 /* Try merging insns starting at THREAD which match exactly the insns in
1883 If all insns were matched and the insn was previously annulling, the
1884 annul bit will be cleared.
1886 For each insn that is merged, if the branch is or will be non-annulling,
1887 we delete the merged insn. */
1890 try_merge_delay_insns (insn, thread)
1893 rtx trial, next_trial;
1894 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1895 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1896 int slot_number = 1;
1897 int num_slots = XVECLEN (PATTERN (insn), 0);
1898 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1899 struct resources set, needed;
1900 rtx merged_insns = 0;
1904 flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
1906 CLEAR_RESOURCE (&needed);
1907 CLEAR_RESOURCE (&set);
1909 /* If this is not an annulling branch, take into account anything needed in
1910 INSN's delay slot. This prevents two increments from being incorrectly
1911 folded into one. If we are annulling, this would be the correct
1912 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1913 will essentially disable this optimization. This method is somewhat of
1914 a kludge, but I don't see a better way.) */
1916 for (i = 1 ; i < num_slots ; i++)
1917 if (XVECEXP (PATTERN (insn), 0, i))
1918 mark_referenced_resources (XVECEXP (PATTERN (insn), 0, i), &needed, 1);
1920 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1922 rtx pat = PATTERN (trial);
1923 rtx oldtrial = trial;
1925 next_trial = next_nonnote_insn (trial);
1927 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1928 if (GET_CODE (trial) == INSN
1929 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1932 if (GET_CODE (next_to_match) == GET_CODE (trial)
1934 /* We can't share an insn that sets cc0. */
1935 && ! sets_cc0_p (pat)
1937 && ! insn_references_resource_p (trial, &set, 1)
1938 && ! insn_sets_resource_p (trial, &set, 1)
1939 && ! insn_sets_resource_p (trial, &needed, 1)
1940 && (trial = try_split (pat, trial, 0)) != 0
1941 /* Update next_trial, in case try_split succeeded. */
1942 && (next_trial = next_nonnote_insn (trial))
1943 /* Likewise THREAD. */
1944 && (thread = oldtrial == thread ? trial : thread)
1945 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1946 /* Have to test this condition if annul condition is different
1947 from (and less restrictive than) non-annulling one. */
1948 && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
1953 update_block (trial, thread);
1954 if (trial == thread)
1955 thread = next_active_insn (thread);
1957 delete_insn (trial);
1958 INSN_FROM_TARGET_P (next_to_match) = 0;
1961 merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns);
1963 if (++slot_number == num_slots)
1966 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1969 mark_set_resources (trial, &set, 0, 1);
1970 mark_referenced_resources (trial, &needed, 1);
1973 /* See if we stopped on a filled insn. If we did, try to see if its
1974 delay slots match. */
1975 if (slot_number != num_slots
1976 && trial && GET_CODE (trial) == INSN
1977 && GET_CODE (PATTERN (trial)) == SEQUENCE
1978 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1980 rtx pat = PATTERN (trial);
1981 rtx filled_insn = XVECEXP (pat, 0, 0);
1983 /* Account for resources set/needed by the filled insn. */
1984 mark_set_resources (filled_insn, &set, 0, 1);
1985 mark_referenced_resources (filled_insn, &needed, 1);
1987 for (i = 1; i < XVECLEN (pat, 0); i++)
1989 rtx dtrial = XVECEXP (pat, 0, i);
1991 if (! insn_references_resource_p (dtrial, &set, 1)
1992 && ! insn_sets_resource_p (dtrial, &set, 1)
1993 && ! insn_sets_resource_p (dtrial, &needed, 1)
1995 && ! sets_cc0_p (PATTERN (dtrial))
1997 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1998 && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
2004 update_block (dtrial, thread);
2005 new = delete_from_delay_slot (dtrial);
2006 if (INSN_DELETED_P (thread))
2008 INSN_FROM_TARGET_P (next_to_match) = 0;
2011 merged_insns = gen_rtx_INSN_LIST (SImode, dtrial,
2014 if (++slot_number == num_slots)
2017 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
2021 /* Keep track of the set/referenced resources for the delay
2022 slots of any trial insns we encounter. */
2023 mark_set_resources (dtrial, &set, 0, 1);
2024 mark_referenced_resources (dtrial, &needed, 1);
2029 /* If all insns in the delay slot have been matched and we were previously
2030 annulling the branch, we need not any more. In that case delete all the
2031 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
2032 the delay list so that we know that it isn't only being used at the
2034 if (slot_number == num_slots && annul_p)
2036 for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
2038 if (GET_MODE (merged_insns) == SImode)
2042 update_block (XEXP (merged_insns, 0), thread);
2043 new = delete_from_delay_slot (XEXP (merged_insns, 0));
2044 if (INSN_DELETED_P (thread))
2049 update_block (XEXP (merged_insns, 0), thread);
2050 delete_insn (XEXP (merged_insns, 0));
2054 INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
2056 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2057 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
2061 /* See if INSN is redundant with an insn in front of TARGET. Often this
2062 is called when INSN is a candidate for a delay slot of TARGET.
2063 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
2064 of INSN. Often INSN will be redundant with an insn in a delay slot of
2065 some previous insn. This happens when we have a series of branches to the
2066 same label; in that case the first insn at the target might want to go
2067 into each of the delay slots.
2069 If we are not careful, this routine can take up a significant fraction
2070 of the total compilation time (4%), but only wins rarely. Hence we
2071 speed this routine up by making two passes. The first pass goes back
2072 until it hits a label and sees if it find an insn with an identical
2073 pattern. Only in this (relatively rare) event does it check for
2076 We do not split insns we encounter. This could cause us not to find a
2077 redundant insn, but the cost of splitting seems greater than the possible
2078 gain in rare cases. */
2081 redundant_insn (insn, target, delay_list)
2086 rtx target_main = target;
2087 rtx ipat = PATTERN (insn);
2089 struct resources needed, set;
2092 /* If INSN has any REG_UNUSED notes, it can't match anything since we
2093 are allowed to not actually assign to such a register. */
2094 if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0)
2097 /* Scan backwards looking for a match. */
2098 for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
2100 if (GET_CODE (trial) == CODE_LABEL)
2103 if (GET_RTX_CLASS (GET_CODE (trial)) != 'i')
2106 pat = PATTERN (trial);
2107 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2110 if (GET_CODE (pat) == SEQUENCE)
2112 /* Stop for a CALL and its delay slots because it is difficult to
2113 track its resource needs correctly. */
2114 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2117 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
2118 slots because it is difficult to track its resource needs
2121 #ifdef INSN_SETS_ARE_DELAYED
2122 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2126 #ifdef INSN_REFERENCES_ARE_DELAYED
2127 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2131 /* See if any of the insns in the delay slot match, updating
2132 resource requirements as we go. */
2133 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2134 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
2135 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat)
2136 && ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX))
2139 /* If found a match, exit this loop early. */
2144 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)
2145 && ! find_reg_note (trial, REG_UNUSED, NULL_RTX))
2149 /* If we didn't find an insn that matches, return 0. */
2153 /* See what resources this insn sets and needs. If they overlap, or
2154 if this insn references CC0, it can't be redundant. */
2156 CLEAR_RESOURCE (&needed);
2157 CLEAR_RESOURCE (&set);
2158 mark_set_resources (insn, &set, 0, 1);
2159 mark_referenced_resources (insn, &needed, 1);
2161 /* If TARGET is a SEQUENCE, get the main insn. */
2162 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2163 target_main = XVECEXP (PATTERN (target), 0, 0);
2165 if (resource_conflicts_p (&needed, &set)
2167 || reg_mentioned_p (cc0_rtx, ipat)
2169 /* The insn requiring the delay may not set anything needed or set by
2171 || insn_sets_resource_p (target_main, &needed, 1)
2172 || insn_sets_resource_p (target_main, &set, 1))
2175 /* Insns we pass may not set either NEEDED or SET, so merge them for
2177 needed.memory |= set.memory;
2178 needed.unch_memory |= set.unch_memory;
2179 IOR_HARD_REG_SET (needed.regs, set.regs);
2181 /* This insn isn't redundant if it conflicts with an insn that either is
2182 or will be in a delay slot of TARGET. */
2186 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
2188 delay_list = XEXP (delay_list, 1);
2191 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
2192 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
2193 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
2196 /* Scan backwards until we reach a label or an insn that uses something
2197 INSN sets or sets something insn uses or sets. */
2199 for (trial = PREV_INSN (target);
2200 trial && GET_CODE (trial) != CODE_LABEL;
2201 trial = PREV_INSN (trial))
2203 if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
2204 && GET_CODE (trial) != JUMP_INSN)
2207 pat = PATTERN (trial);
2208 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2211 if (GET_CODE (pat) == SEQUENCE)
2213 /* If this is a CALL_INSN and its delay slots, it is hard to track
2214 the resource needs properly, so give up. */
2215 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
2218 /* If this is an INSN or JUMP_INSN with delayed effects, it
2219 is hard to track the resource needs properly, so give up. */
2221 #ifdef INSN_SETS_ARE_DELAYED
2222 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2226 #ifdef INSN_REFERENCES_ARE_DELAYED
2227 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
2231 /* See if any of the insns in the delay slot match, updating
2232 resource requirements as we go. */
2233 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
2235 rtx candidate = XVECEXP (pat, 0, i);
2237 /* If an insn will be annulled if the branch is false, it isn't
2238 considered as a possible duplicate insn. */
2239 if (rtx_equal_p (PATTERN (candidate), ipat)
2240 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2241 && INSN_FROM_TARGET_P (candidate)))
2243 /* Show that this insn will be used in the sequel. */
2244 INSN_FROM_TARGET_P (candidate) = 0;
2248 /* Unless this is an annulled insn from the target of a branch,
2249 we must stop if it sets anything needed or set by INSN. */
2250 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
2251 || ! INSN_FROM_TARGET_P (candidate))
2252 && insn_sets_resource_p (candidate, &needed, 1))
2257 /* If the insn requiring the delay slot conflicts with INSN, we
2259 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
2264 /* See if TRIAL is the same as INSN. */
2265 pat = PATTERN (trial);
2266 if (rtx_equal_p (pat, ipat))
2269 /* Can't go any further if TRIAL conflicts with INSN. */
2270 if (insn_sets_resource_p (trial, &needed, 1))
2278 /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero,
2279 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
2280 is non-zero, we are allowed to fall into this thread; otherwise, we are
2283 If LABEL is used more than one or we pass a label other than LABEL before
2284 finding an active insn, we do not own this thread. */
2287 own_thread_p (thread, label, allow_fallthrough)
2290 int allow_fallthrough;
2295 /* We don't own the function end. */
2299 /* Get the first active insn, or THREAD, if it is an active insn. */
2300 active_insn = next_active_insn (PREV_INSN (thread));
2302 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
2303 if (GET_CODE (insn) == CODE_LABEL
2304 && (insn != label || LABEL_NUSES (insn) != 1))
2307 if (allow_fallthrough)
2310 /* Ensure that we reach a BARRIER before any insn or label. */
2311 for (insn = prev_nonnote_insn (thread);
2312 insn == 0 || GET_CODE (insn) != BARRIER;
2313 insn = prev_nonnote_insn (insn))
2315 || GET_CODE (insn) == CODE_LABEL
2316 || (GET_CODE (insn) == INSN
2317 && GET_CODE (PATTERN (insn)) != USE
2318 && GET_CODE (PATTERN (insn)) != CLOBBER))
2324 /* Find the number of the basic block that starts closest to INSN. Return -1
2325 if we couldn't find such a basic block. */
2328 find_basic_block (insn)
2333 /* Scan backwards to the previous BARRIER. Then see if we can find a
2334 label that starts a basic block. Return the basic block number. */
2336 for (insn = prev_nonnote_insn (insn);
2337 insn && GET_CODE (insn) != BARRIER;
2338 insn = prev_nonnote_insn (insn))
2341 /* The start of the function is basic block zero. */
2345 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
2346 anything other than a CODE_LABEL or note, we can't find this code. */
2347 for (insn = next_nonnote_insn (insn);
2348 insn && GET_CODE (insn) == CODE_LABEL;
2349 insn = next_nonnote_insn (insn))
2351 for (i = 0; i < n_basic_blocks; i++)
2352 if (insn == basic_block_head[i])
2359 /* Called when INSN is being moved from a location near the target of a jump.
2360 We leave a marker of the form (use (INSN)) immediately in front
2361 of WHERE for mark_target_live_regs. These markers will be deleted when
2364 We used to try to update the live status of registers if WHERE is at
2365 the start of a basic block, but that can't work since we may remove a
2366 BARRIER in relax_delay_slots. */
2369 update_block (insn, where)
2375 /* Ignore if this was in a delay slot and it came from the target of
2377 if (INSN_FROM_TARGET_P (insn))
2380 emit_insn_before (gen_rtx_USE (VOIDmode, insn), where);
2382 /* INSN might be making a value live in a block where it didn't use to
2383 be. So recompute liveness information for this block. */
2385 b = find_basic_block (insn);
2390 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
2391 the basic block containing the jump. */
2394 reorg_redirect_jump (jump, nlabel)
2398 int b = find_basic_block (jump);
2403 return redirect_jump (jump, nlabel);
2406 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
2407 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
2408 that reference values used in INSN. If we find one, then we move the
2409 REG_DEAD note to INSN.
2411 This is needed to handle the case where an later insn (after INSN) has a
2412 REG_DEAD note for a register used by INSN, and this later insn subsequently
2413 gets moved before a CODE_LABEL because it is a redundant insn. In this
2414 case, mark_target_live_regs may be confused into thinking the register
2415 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
2418 update_reg_dead_notes (insn, delayed_insn)
2419 rtx insn, delayed_insn;
2423 for (p = next_nonnote_insn (insn); p != delayed_insn;
2424 p = next_nonnote_insn (p))
2425 for (link = REG_NOTES (p); link; link = next)
2427 next = XEXP (link, 1);
2429 if (REG_NOTE_KIND (link) != REG_DEAD
2430 || GET_CODE (XEXP (link, 0)) != REG)
2433 if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
2435 /* Move the REG_DEAD note from P to INSN. */
2436 remove_note (p, link);
2437 XEXP (link, 1) = REG_NOTES (insn);
2438 REG_NOTES (insn) = link;
2443 /* Called when an insn redundant with start_insn is deleted. If there
2444 is a REG_DEAD note for the target of start_insn between start_insn
2445 and stop_insn, then the REG_DEAD note needs to be deleted since the
2446 value no longer dies there.
2448 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
2449 confused into thinking the register is dead. */
2452 fix_reg_dead_note (start_insn, stop_insn)
2453 rtx start_insn, stop_insn;
2457 for (p = next_nonnote_insn (start_insn); p != stop_insn;
2458 p = next_nonnote_insn (p))
2459 for (link = REG_NOTES (p); link; link = next)
2461 next = XEXP (link, 1);
2463 if (REG_NOTE_KIND (link) != REG_DEAD
2464 || GET_CODE (XEXP (link, 0)) != REG)
2467 if (reg_set_p (XEXP (link, 0), PATTERN (start_insn)))
2469 remove_note (p, link);
2475 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
2477 This handles the case of udivmodXi4 instructions which optimize their
2478 output depending on whether any REG_UNUSED notes are present.
2479 we must make sure that INSN calculates as many results as REDUNDANT_INSN
2483 update_reg_unused_notes (insn, redundant_insn)
2484 rtx insn, redundant_insn;
2488 for (link = REG_NOTES (insn); link; link = next)
2490 next = XEXP (link, 1);
2492 if (REG_NOTE_KIND (link) != REG_UNUSED
2493 || GET_CODE (XEXP (link, 0)) != REG)
2496 if (! find_regno_note (redundant_insn, REG_UNUSED,
2497 REGNO (XEXP (link, 0))))
2498 remove_note (insn, link);
2502 /* Marks registers possibly live at the current place being scanned by
2503 mark_target_live_regs. Used only by next two function. */
2505 static HARD_REG_SET current_live_regs;
2507 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
2508 Also only used by the next two functions. */
2510 static HARD_REG_SET pending_dead_regs;
2512 /* Utility function called from mark_target_live_regs via note_stores.
2513 It deadens any CLOBBERed registers and livens any SET registers. */
2516 update_live_status (dest, x)
2520 int first_regno, last_regno;
2523 if (GET_CODE (dest) != REG
2524 && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
2527 if (GET_CODE (dest) == SUBREG)
2528 first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
2530 first_regno = REGNO (dest);
2532 last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
2534 if (GET_CODE (x) == CLOBBER)
2535 for (i = first_regno; i < last_regno; i++)
2536 CLEAR_HARD_REG_BIT (current_live_regs, i);
2538 for (i = first_regno; i < last_regno; i++)
2540 SET_HARD_REG_BIT (current_live_regs, i);
2541 CLEAR_HARD_REG_BIT (pending_dead_regs, i);
2545 /* Similar to next_insn, but ignores insns in the delay slots of
2546 an annulled branch. */
2549 next_insn_no_annul (insn)
2554 /* If INSN is an annulled branch, skip any insns from the target
2556 if (INSN_ANNULLED_BRANCH_P (insn)
2557 && NEXT_INSN (PREV_INSN (insn)) != insn)
2558 while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
2559 insn = NEXT_INSN (insn);
2561 insn = NEXT_INSN (insn);
2562 if (insn && GET_CODE (insn) == INSN
2563 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2564 insn = XVECEXP (PATTERN (insn), 0, 0);
2570 /* A subroutine of mark_target_live_regs. Search forward from TARGET
2571 looking for registers that are set before they are used. These are dead.
2572 Stop after passing a few conditional jumps, and/or a small
2573 number of unconditional branches. */
2576 find_dead_or_set_registers (target, res, jump_target, jump_count, set, needed)
2578 struct resources *res;
2581 struct resources set, needed;
2583 HARD_REG_SET scratch;
2588 for (insn = target; insn; insn = next)
2590 rtx this_jump_insn = insn;
2592 next = NEXT_INSN (insn);
2593 switch (GET_CODE (insn))
2596 /* After a label, any pending dead registers that weren't yet
2597 used can be made dead. */
2598 AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2599 AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2600 CLEAR_HARD_REG_SET (pending_dead_regs);
2609 if (GET_CODE (PATTERN (insn)) == USE)
2611 /* If INSN is a USE made by update_block, we care about the
2612 underlying insn. Any registers set by the underlying insn
2613 are live since the insn is being done somewhere else. */
2614 if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2615 mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1);
2617 /* All other USE insns are to be ignored. */
2620 else if (GET_CODE (PATTERN (insn)) == CLOBBER)
2622 else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2624 /* An unconditional jump can be used to fill the delay slot
2625 of a call, so search for a JUMP_INSN in any position. */
2626 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2628 this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
2629 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2638 if (GET_CODE (this_jump_insn) == JUMP_INSN)
2640 if (jump_count++ < 10)
2642 if (simplejump_p (this_jump_insn)
2643 || GET_CODE (PATTERN (this_jump_insn)) == RETURN)
2645 next = JUMP_LABEL (this_jump_insn);
2650 *jump_target = JUMP_LABEL (this_jump_insn);
2653 else if (condjump_p (this_jump_insn)
2654 || condjump_in_parallel_p (this_jump_insn))
2656 struct resources target_set, target_res;
2657 struct resources fallthrough_res;
2659 /* We can handle conditional branches here by following
2660 both paths, and then IOR the results of the two paths
2661 together, which will give us registers that are dead
2662 on both paths. Since this is expensive, we give it
2663 a much higher cost than unconditional branches. The
2664 cost was chosen so that we will follow at most 1
2665 conditional branch. */
2668 if (jump_count >= 10)
2671 mark_referenced_resources (insn, &needed, 1);
2673 /* For an annulled branch, mark_set_resources ignores slots
2674 filled by instructions from the target. This is correct
2675 if the branch is not taken. Since we are following both
2676 paths from the branch, we must also compute correct info
2677 if the branch is taken. We do this by inverting all of
2678 the INSN_FROM_TARGET_P bits, calling mark_set_resources,
2679 and then inverting the INSN_FROM_TARGET_P bits again. */
2681 if (GET_CODE (PATTERN (insn)) == SEQUENCE
2682 && INSN_ANNULLED_BRANCH_P (this_jump_insn))
2684 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
2685 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
2686 = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
2689 mark_set_resources (insn, &target_set, 0, 1);
2691 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
2692 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
2693 = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
2695 mark_set_resources (insn, &set, 0, 1);
2699 mark_set_resources (insn, &set, 0, 1);
2704 COPY_HARD_REG_SET (scratch, target_set.regs);
2705 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2706 AND_COMPL_HARD_REG_SET (target_res.regs, scratch);
2708 fallthrough_res = *res;
2709 COPY_HARD_REG_SET (scratch, set.regs);
2710 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2711 AND_COMPL_HARD_REG_SET (fallthrough_res.regs, scratch);
2713 find_dead_or_set_registers (JUMP_LABEL (this_jump_insn),
2714 &target_res, 0, jump_count,
2715 target_set, needed);
2716 find_dead_or_set_registers (next,
2717 &fallthrough_res, 0, jump_count,
2719 IOR_HARD_REG_SET (fallthrough_res.regs, target_res.regs);
2720 AND_HARD_REG_SET (res->regs, fallthrough_res.regs);
2728 /* Don't try this optimization if we expired our jump count
2729 above, since that would mean there may be an infinite loop
2730 in the function being compiled. */
2736 mark_referenced_resources (insn, &needed, 1);
2737 mark_set_resources (insn, &set, 0, 1);
2739 COPY_HARD_REG_SET (scratch, set.regs);
2740 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2741 AND_COMPL_HARD_REG_SET (res->regs, scratch);
2747 /* Set the resources that are live at TARGET.
2749 If TARGET is zero, we refer to the end of the current function and can
2750 return our precomputed value.
2752 Otherwise, we try to find out what is live by consulting the basic block
2753 information. This is tricky, because we must consider the actions of
2754 reload and jump optimization, which occur after the basic block information
2757 Accordingly, we proceed as follows::
2759 We find the previous BARRIER and look at all immediately following labels
2760 (with no intervening active insns) to see if any of them start a basic
2761 block. If we hit the start of the function first, we use block 0.
2763 Once we have found a basic block and a corresponding first insns, we can
2764 accurately compute the live status from basic_block_live_regs and
2765 reg_renumber. (By starting at a label following a BARRIER, we are immune
2766 to actions taken by reload and jump.) Then we scan all insns between
2767 that point and our target. For each CLOBBER (or for call-clobbered regs
2768 when we pass a CALL_INSN), mark the appropriate registers are dead. For
2769 a SET, mark them as live.
2771 We have to be careful when using REG_DEAD notes because they are not
2772 updated by such things as find_equiv_reg. So keep track of registers
2773 marked as dead that haven't been assigned to, and mark them dead at the
2774 next CODE_LABEL since reload and jump won't propagate values across labels.
2776 If we cannot find the start of a basic block (should be a very rare
2777 case, if it can happen at all), mark everything as potentially live.
2779 Next, scan forward from TARGET looking for things set or clobbered
2780 before they are used. These are not live.
2782 Because we can be called many times on the same target, save our results
2783 in a hash table indexed by INSN_UID. */
2786 mark_target_live_regs (target, res)
2788 struct resources *res;
2792 struct target_info *tinfo;
2796 HARD_REG_SET scratch;
2797 struct resources set, needed;
2799 /* Handle end of function. */
2802 *res = end_of_function_needs;
2806 /* We have to assume memory is needed, but the CC isn't. */
2808 res->volatil = res->unch_memory = 0;
2811 /* See if we have computed this value already. */
2812 for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2813 tinfo; tinfo = tinfo->next)
2814 if (tinfo->uid == INSN_UID (target))
2817 /* Start by getting the basic block number. If we have saved information,
2818 we can get it from there unless the insn at the start of the basic block
2819 has been deleted. */
2820 if (tinfo && tinfo->block != -1
2821 && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
2825 b = find_basic_block (target);
2829 /* If the information is up-to-date, use it. Otherwise, we will
2831 if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
2833 COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
2839 /* Allocate a place to put our results and chain it into the
2841 tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
2842 tinfo->uid = INSN_UID (target);
2844 tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
2845 target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
2848 CLEAR_HARD_REG_SET (pending_dead_regs);
2850 /* If we found a basic block, get the live registers from it and update
2851 them with anything set or killed between its start and the insn before
2852 TARGET. Otherwise, we must assume everything is live. */
2855 regset regs_live = basic_block_live_at_start[b];
2858 rtx start_insn, stop_insn;
2860 /* Compute hard regs live at start of block -- this is the real hard regs
2861 marked live, plus live pseudo regs that have been renumbered to
2864 REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live);
2866 EXECUTE_IF_SET_IN_REG_SET
2867 (regs_live, FIRST_PSEUDO_REGISTER, i,
2869 if ((regno = reg_renumber[i]) >= 0)
2871 j < regno + HARD_REGNO_NREGS (regno,
2872 PSEUDO_REGNO_MODE (i));
2874 SET_HARD_REG_BIT (current_live_regs, j);
2877 /* Get starting and ending insn, handling the case where each might
2879 start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2882 if (GET_CODE (start_insn) == INSN
2883 && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2884 start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2886 if (GET_CODE (stop_insn) == INSN
2887 && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2888 stop_insn = next_insn (PREV_INSN (stop_insn));
2890 for (insn = start_insn; insn != stop_insn;
2891 insn = next_insn_no_annul (insn))
2894 rtx real_insn = insn;
2896 /* If this insn is from the target of a branch, it isn't going to
2897 be used in the sequel. If it is used in both cases, this
2898 test will not be true. */
2899 if (INSN_FROM_TARGET_P (insn))
2902 /* If this insn is a USE made by update_block, we care about the
2904 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2905 && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
2906 real_insn = XEXP (PATTERN (insn), 0);
2908 if (GET_CODE (real_insn) == CALL_INSN)
2910 /* CALL clobbers all call-used regs that aren't fixed except
2911 sp, ap, and fp. Do this before setting the result of the
2913 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2914 if (call_used_regs[i]
2915 && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2916 && i != ARG_POINTER_REGNUM
2917 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2918 && i != HARD_FRAME_POINTER_REGNUM
2920 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2921 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2923 #ifdef PIC_OFFSET_TABLE_REGNUM
2924 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2927 CLEAR_HARD_REG_BIT (current_live_regs, i);
2929 /* A CALL_INSN sets any global register live, since it may
2930 have been modified by the call. */
2931 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2933 SET_HARD_REG_BIT (current_live_regs, i);
2936 /* Mark anything killed in an insn to be deadened at the next
2937 label. Ignore USE insns; the only REG_DEAD notes will be for
2938 parameters. But they might be early. A CALL_INSN will usually
2939 clobber registers used for parameters. It isn't worth bothering
2940 with the unlikely case when it won't. */
2941 if ((GET_CODE (real_insn) == INSN
2942 && GET_CODE (PATTERN (real_insn)) != USE
2943 && GET_CODE (PATTERN (real_insn)) != CLOBBER)
2944 || GET_CODE (real_insn) == JUMP_INSN
2945 || GET_CODE (real_insn) == CALL_INSN)
2947 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2948 if (REG_NOTE_KIND (link) == REG_DEAD
2949 && GET_CODE (XEXP (link, 0)) == REG
2950 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2952 int first_regno = REGNO (XEXP (link, 0));
2955 + HARD_REGNO_NREGS (first_regno,
2956 GET_MODE (XEXP (link, 0))));
2958 for (i = first_regno; i < last_regno; i++)
2959 SET_HARD_REG_BIT (pending_dead_regs, i);
2962 note_stores (PATTERN (real_insn), update_live_status);
2964 /* If any registers were unused after this insn, kill them.
2965 These notes will always be accurate. */
2966 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2967 if (REG_NOTE_KIND (link) == REG_UNUSED
2968 && GET_CODE (XEXP (link, 0)) == REG
2969 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2971 int first_regno = REGNO (XEXP (link, 0));
2974 + HARD_REGNO_NREGS (first_regno,
2975 GET_MODE (XEXP (link, 0))));
2977 for (i = first_regno; i < last_regno; i++)
2978 CLEAR_HARD_REG_BIT (current_live_regs, i);
2982 else if (GET_CODE (real_insn) == CODE_LABEL)
2984 /* A label clobbers the pending dead registers since neither
2985 reload nor jump will propagate a value across a label. */
2986 AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2987 CLEAR_HARD_REG_SET (pending_dead_regs);
2990 /* The beginning of the epilogue corresponds to the end of the
2991 RTL chain when there are no epilogue insns. Certain resources
2992 are implicitly required at that point. */
2993 else if (GET_CODE (real_insn) == NOTE
2994 && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG)
2995 IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs);
2998 COPY_HARD_REG_SET (res->regs, current_live_regs);
3000 tinfo->bb_tick = bb_ticks[b];
3003 /* We didn't find the start of a basic block. Assume everything
3004 in use. This should happen only extremely rarely. */
3005 SET_HARD_REG_SET (res->regs);
3007 CLEAR_RESOURCE (&set);
3008 CLEAR_RESOURCE (&needed);
3010 jump_insn = find_dead_or_set_registers (target, res, &jump_target, 0,
3013 /* If we hit an unconditional branch, we have another way of finding out
3014 what is live: we can see what is live at the branch target and include
3015 anything used but not set before the branch. The only things that are
3016 live are those that are live using the above test and the test below. */
3020 struct resources new_resources;
3021 rtx stop_insn = next_active_insn (jump_insn);
3023 mark_target_live_regs (next_active_insn (jump_target), &new_resources);
3024 CLEAR_RESOURCE (&set);
3025 CLEAR_RESOURCE (&needed);
3027 /* Include JUMP_INSN in the needed registers. */
3028 for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
3030 mark_referenced_resources (insn, &needed, 1);
3032 COPY_HARD_REG_SET (scratch, needed.regs);
3033 AND_COMPL_HARD_REG_SET (scratch, set.regs);
3034 IOR_HARD_REG_SET (new_resources.regs, scratch);
3036 mark_set_resources (insn, &set, 0, 1);
3039 AND_HARD_REG_SET (res->regs, new_resources.regs);
3042 COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
3045 /* Scan a function looking for insns that need a delay slot and find insns to
3046 put into the delay slot.
3048 NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
3049 as calls). We do these first since we don't want jump insns (that are
3050 easier to fill) to get the only insns that could be used for non-jump insns.
3051 When it is zero, only try to fill JUMP_INSNs.
3053 When slots are filled in this manner, the insns (including the
3054 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
3055 it is possible to tell whether a delay slot has really been filled
3056 or not. `final' knows how to deal with this, by communicating
3057 through FINAL_SEQUENCE. */
3060 fill_simple_delay_slots (non_jumps_p)
3063 register rtx insn, pat, trial, next_trial;
3065 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3066 struct resources needed, set;
3067 int slots_to_fill, slots_filled;
3070 for (i = 0; i < num_unfilled_slots; i++)
3073 /* Get the next insn to fill. If it has already had any slots assigned,
3074 we can't do anything with it. Maybe we'll improve this later. */
3076 insn = unfilled_slots_base[i];
3078 || INSN_DELETED_P (insn)
3079 || (GET_CODE (insn) == INSN
3080 && GET_CODE (PATTERN (insn)) == SEQUENCE)
3081 || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
3082 || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
3085 if (GET_CODE (insn) == JUMP_INSN)
3086 flags = get_jump_flags (insn, JUMP_LABEL (insn));
3088 flags = get_jump_flags (insn, NULL_RTX);
3089 slots_to_fill = num_delay_slots (insn);
3091 /* Some machine description have defined instructions to have
3092 delay slots only in certain circumstances which may depend on
3093 nearby insns (which change due to reorg's actions).
3095 For example, the PA port normally has delay slots for unconditional
3098 However, the PA port claims such jumps do not have a delay slot
3099 if they are immediate successors of certain CALL_INSNs. This
3100 allows the port to favor filling the delay slot of the call with
3101 the unconditional jump. */
3102 if (slots_to_fill == 0)
3105 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
3106 says how many. After initialization, first try optimizing
3109 nop add %o7,.-L1,%o7
3113 If this case applies, the delay slot of the call is filled with
3114 the unconditional jump. This is done first to avoid having the
3115 delay slot of the call filled in the backward scan. Also, since
3116 the unconditional jump is likely to also have a delay slot, that
3117 insn must exist when it is subsequently scanned.
3119 This is tried on each insn with delay slots as some machines
3120 have insns which perform calls, but are not represented as
3126 if ((trial = next_active_insn (insn))
3127 && GET_CODE (trial) == JUMP_INSN
3128 && simplejump_p (trial)
3129 && eligible_for_delay (insn, slots_filled, trial, flags)
3130 && no_labels_between_p (insn, trial))
3134 delay_list = add_to_delay_list (trial, delay_list);
3136 /* TRIAL may have had its delay slot filled, then unfilled. When
3137 the delay slot is unfilled, TRIAL is placed back on the unfilled
3138 slots obstack. Unfortunately, it is placed on the end of the
3139 obstack, not in its original location. Therefore, we must search
3140 from entry i + 1 to the end of the unfilled slots obstack to
3141 try and find TRIAL. */
3142 tmp = &unfilled_slots_base[i + 1];
3143 while (*tmp != trial && tmp != unfilled_slots_next)
3146 /* Remove the unconditional jump from consideration for delay slot
3147 filling and unthread it. */
3151 rtx next = NEXT_INSN (trial);
3152 rtx prev = PREV_INSN (trial);
3154 NEXT_INSN (prev) = next;
3156 PREV_INSN (next) = prev;
3160 /* Now, scan backwards from the insn to search for a potential
3161 delay-slot candidate. Stop searching when a label or jump is hit.
3163 For each candidate, if it is to go into the delay slot (moved
3164 forward in execution sequence), it must not need or set any resources
3165 that were set by later insns and must not set any resources that
3166 are needed for those insns.
3168 The delay slot insn itself sets resources unless it is a call
3169 (in which case the called routine, not the insn itself, is doing
3172 if (slots_filled < slots_to_fill)
3174 CLEAR_RESOURCE (&needed);
3175 CLEAR_RESOURCE (&set);
3176 mark_set_resources (insn, &set, 0, 0);
3177 mark_referenced_resources (insn, &needed, 0);
3179 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
3182 next_trial = prev_nonnote_insn (trial);
3184 /* This must be an INSN or CALL_INSN. */
3185 pat = PATTERN (trial);
3187 /* USE and CLOBBER at this level was just for flow; ignore it. */
3188 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3191 /* Check for resource conflict first, to avoid unnecessary
3193 if (! insn_references_resource_p (trial, &set, 1)
3194 && ! insn_sets_resource_p (trial, &set, 1)
3195 && ! insn_sets_resource_p (trial, &needed, 1)
3197 /* Can't separate set of cc0 from its use. */
3198 && ! (reg_mentioned_p (cc0_rtx, pat)
3199 && ! sets_cc0_p (cc0_rtx, pat))
3203 trial = try_split (pat, trial, 1);
3204 next_trial = prev_nonnote_insn (trial);
3205 if (eligible_for_delay (insn, slots_filled, trial, flags))
3207 /* In this case, we are searching backward, so if we
3208 find insns to put on the delay list, we want
3209 to put them at the head, rather than the
3210 tail, of the list. */
3212 update_reg_dead_notes (trial, insn);
3213 delay_list = gen_rtx_INSN_LIST (VOIDmode,
3215 update_block (trial, trial);
3216 delete_insn (trial);
3217 if (slots_to_fill == ++slots_filled)
3223 mark_set_resources (trial, &set, 0, 1);
3224 mark_referenced_resources (trial, &needed, 1);
3228 /* If all needed slots haven't been filled, we come here. */
3230 /* Try to optimize case of jumping around a single insn. */
3231 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
3232 if (slots_filled != slots_to_fill
3234 && GET_CODE (insn) == JUMP_INSN
3235 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
3237 delay_list = optimize_skip (insn);
3243 /* Try to get insns from beyond the insn needing the delay slot.
3244 These insns can neither set or reference resources set in insns being
3245 skipped, cannot set resources in the insn being skipped, and, if this
3246 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
3247 call might not return).
3249 There used to be code which continued past the target label if
3250 we saw all uses of the target label. This code did not work,
3251 because it failed to account for some instructions which were
3252 both annulled and marked as from the target. This can happen as a
3253 result of optimize_skip. Since this code was redundant with
3254 fill_eager_delay_slots anyways, it was just deleted. */
3256 if (slots_filled != slots_to_fill
3257 && (GET_CODE (insn) != JUMP_INSN
3258 || ((condjump_p (insn) || condjump_in_parallel_p (insn))
3259 && ! simplejump_p (insn)
3260 && JUMP_LABEL (insn) != 0)))
3263 int maybe_never = 0;
3264 struct resources needed_at_jump;
3266 CLEAR_RESOURCE (&needed);
3267 CLEAR_RESOURCE (&set);
3269 if (GET_CODE (insn) == CALL_INSN)
3271 mark_set_resources (insn, &set, 0, 1);
3272 mark_referenced_resources (insn, &needed, 1);
3277 mark_set_resources (insn, &set, 0, 1);
3278 mark_referenced_resources (insn, &needed, 1);
3279 if (GET_CODE (insn) == JUMP_INSN)
3280 target = JUMP_LABEL (insn);
3283 for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
3285 rtx pat, trial_delay;
3287 next_trial = next_nonnote_insn (trial);
3289 if (GET_CODE (trial) == CODE_LABEL
3290 || GET_CODE (trial) == BARRIER)
3293 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
3294 pat = PATTERN (trial);
3296 /* Stand-alone USE and CLOBBER are just for flow. */
3297 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3300 /* If this already has filled delay slots, get the insn needing
3302 if (GET_CODE (pat) == SEQUENCE)
3303 trial_delay = XVECEXP (pat, 0, 0);
3305 trial_delay = trial;
3307 /* If this is a jump insn to our target, indicate that we have
3308 seen another jump to it. If we aren't handling a conditional
3309 jump, stop our search. Otherwise, compute the needs at its
3310 target and add them to NEEDED. */
3311 if (GET_CODE (trial_delay) == JUMP_INSN)
3315 else if (JUMP_LABEL (trial_delay) != target)
3317 mark_target_live_regs
3318 (next_active_insn (JUMP_LABEL (trial_delay)),
3320 needed.memory |= needed_at_jump.memory;
3321 needed.unch_memory |= needed_at_jump.unch_memory;
3322 IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
3326 /* See if we have a resource problem before we try to
3329 && GET_CODE (pat) != SEQUENCE
3330 && ! insn_references_resource_p (trial, &set, 1)
3331 && ! insn_sets_resource_p (trial, &set, 1)
3332 && ! insn_sets_resource_p (trial, &needed, 1)
3334 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
3336 && ! (maybe_never && may_trap_p (pat))
3337 && (trial = try_split (pat, trial, 0))
3338 && eligible_for_delay (insn, slots_filled, trial, flags))
3340 next_trial = next_nonnote_insn (trial);
3341 delay_list = add_to_delay_list (trial, delay_list);
3344 if (reg_mentioned_p (cc0_rtx, pat))
3345 link_cc0_insns (trial);
3348 delete_insn (trial);
3349 if (slots_to_fill == ++slots_filled)
3354 mark_set_resources (trial, &set, 0, 1);
3355 mark_referenced_resources (trial, &needed, 1);
3357 /* Ensure we don't put insns between the setting of cc and the
3358 comparison by moving a setting of cc into an earlier delay
3359 slot since these insns could clobber the condition code. */
3362 /* If this is a call or jump, we might not get here. */
3363 if (GET_CODE (trial_delay) == CALL_INSN
3364 || GET_CODE (trial_delay) == JUMP_INSN)
3368 /* If there are slots left to fill and our search was stopped by an
3369 unconditional branch, try the insn at the branch target. We can
3370 redirect the branch if it works.
3372 Don't do this if the insn at the branch target is a branch. */
3373 if (slots_to_fill != slots_filled
3375 && GET_CODE (trial) == JUMP_INSN
3376 && simplejump_p (trial)
3377 && (target == 0 || JUMP_LABEL (trial) == target)
3378 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
3379 && ! (GET_CODE (next_trial) == INSN
3380 && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
3381 && GET_CODE (next_trial) != JUMP_INSN
3382 && ! insn_references_resource_p (next_trial, &set, 1)
3383 && ! insn_sets_resource_p (next_trial, &set, 1)
3384 && ! insn_sets_resource_p (next_trial, &needed, 1)
3386 && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
3388 && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
3389 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
3390 && eligible_for_delay (insn, slots_filled, next_trial, flags))
3392 rtx new_label = next_active_insn (next_trial);
3395 new_label = get_label_before (new_label);
3397 new_label = find_end_label ();
3400 = add_to_delay_list (copy_rtx (next_trial), delay_list);
3402 reorg_redirect_jump (trial, new_label);
3404 /* If we merged because we both jumped to the same place,
3405 redirect the original insn also. */
3407 reorg_redirect_jump (insn, new_label);
3411 /* If this is an unconditional jump, then try to get insns from the
3412 target of the jump. */
3413 if (GET_CODE (insn) == JUMP_INSN
3414 && simplejump_p (insn)
3415 && slots_filled != slots_to_fill)
3417 = fill_slots_from_thread (insn, const_true_rtx,
3418 next_active_insn (JUMP_LABEL (insn)),
3420 own_thread_p (JUMP_LABEL (insn),
3421 JUMP_LABEL (insn), 0),
3422 slots_to_fill, &slots_filled,
3426 unfilled_slots_base[i]
3427 = emit_delay_sequence (insn, delay_list, slots_filled);
3429 if (slots_to_fill == slots_filled)
3430 unfilled_slots_base[i] = 0;
3432 note_delay_statistics (slots_filled, 0);
3435 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3436 /* See if the epilogue needs any delay slots. Try to fill them if so.
3437 The only thing we can do is scan backwards from the end of the
3438 function. If we did this in a previous pass, it is incorrect to do it
3440 if (current_function_epilogue_delay_list)
3443 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
3444 if (slots_to_fill == 0)
3448 CLEAR_RESOURCE (&set);
3450 /* The frame pointer and stack pointer are needed at the beginning of
3451 the epilogue, so instructions setting them can not be put in the
3452 epilogue delay slot. However, everything else needed at function
3453 end is safe, so we don't want to use end_of_function_needs here. */
3454 CLEAR_RESOURCE (&needed);
3455 if (frame_pointer_needed)
3457 SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
3458 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3459 SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
3461 #ifdef EXIT_IGNORE_STACK
3462 if (! EXIT_IGNORE_STACK
3463 || current_function_sp_is_unchanging)
3465 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3468 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
3470 #ifdef EPILOGUE_USES
3471 for (i = 0; i <FIRST_PSEUDO_REGISTER; i++)
3473 if (EPILOGUE_USES (i))
3474 SET_HARD_REG_BIT (needed.regs, i);
3478 for (trial = get_last_insn (); ! stop_search_p (trial, 1);
3479 trial = PREV_INSN (trial))
3481 if (GET_CODE (trial) == NOTE)
3483 pat = PATTERN (trial);
3484 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3487 if (! insn_references_resource_p (trial, &set, 1)
3488 && ! insn_sets_resource_p (trial, &needed, 1)
3489 && ! insn_sets_resource_p (trial, &set, 1)
3491 /* Don't want to mess with cc0 here. */
3492 && ! reg_mentioned_p (cc0_rtx, pat)
3496 trial = try_split (pat, trial, 1);
3497 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
3499 /* Here as well we are searching backward, so put the
3500 insns we find on the head of the list. */
3502 current_function_epilogue_delay_list
3503 = gen_rtx_INSN_LIST (VOIDmode, trial,
3504 current_function_epilogue_delay_list);
3505 mark_referenced_resources (trial, &end_of_function_needs, 1);
3506 update_block (trial, trial);
3507 delete_insn (trial);
3509 /* Clear deleted bit so final.c will output the insn. */
3510 INSN_DELETED_P (trial) = 0;
3512 if (slots_to_fill == ++slots_filled)
3518 mark_set_resources (trial, &set, 0, 1);
3519 mark_referenced_resources (trial, &needed, 1);
3522 note_delay_statistics (slots_filled, 0);
3526 /* Try to find insns to place in delay slots.
3528 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
3529 or is an unconditional branch if CONDITION is const_true_rtx.
3530 *PSLOTS_FILLED is updated with the number of slots that we have filled.
3532 THREAD is a flow-of-control, either the insns to be executed if the
3533 branch is true or if the branch is false, THREAD_IF_TRUE says which.
3535 OPPOSITE_THREAD is the thread in the opposite direction. It is used
3536 to see if any potential delay slot insns set things needed there.
3538 LIKELY is non-zero if it is extremely likely that the branch will be
3539 taken and THREAD_IF_TRUE is set. This is used for the branch at the
3540 end of a loop back up to the top.
3542 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
3543 thread. I.e., it is the fallthrough code of our jump or the target of the
3544 jump when we are the only jump going there.
3546 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
3547 case, we can only take insns from the head of the thread for our delay
3548 slot. We then adjust the jump to point after the insns we have taken. */
3551 fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
3552 thread_if_true, own_thread,
3553 slots_to_fill, pslots_filled, delay_list)
3556 rtx thread, opposite_thread;
3560 int slots_to_fill, *pslots_filled;
3564 struct resources opposite_needed, set, needed;
3570 /* Validate our arguments. */
3571 if ((condition == const_true_rtx && ! thread_if_true)
3572 || (! own_thread && ! thread_if_true))
3575 flags = get_jump_flags (insn, JUMP_LABEL (insn));
3577 /* If our thread is the end of subroutine, we can't get any delay
3582 /* If this is an unconditional branch, nothing is needed at the
3583 opposite thread. Otherwise, compute what is needed there. */
3584 if (condition == const_true_rtx)
3585 CLEAR_RESOURCE (&opposite_needed);
3587 mark_target_live_regs (opposite_thread, &opposite_needed);
3589 /* If the insn at THREAD can be split, do it here to avoid having to
3590 update THREAD and NEW_THREAD if it is done in the loop below. Also
3591 initialize NEW_THREAD. */
3593 new_thread = thread = try_split (PATTERN (thread), thread, 0);
3595 /* Scan insns at THREAD. We are looking for an insn that can be removed
3596 from THREAD (it neither sets nor references resources that were set
3597 ahead of it and it doesn't set anything needs by the insns ahead of
3598 it) and that either can be placed in an annulling insn or aren't
3599 needed at OPPOSITE_THREAD. */
3601 CLEAR_RESOURCE (&needed);
3602 CLEAR_RESOURCE (&set);
3604 /* If we do not own this thread, we must stop as soon as we find
3605 something that we can't put in a delay slot, since all we can do
3606 is branch into THREAD at a later point. Therefore, labels stop
3607 the search if this is not the `true' thread. */
3609 for (trial = thread;
3610 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
3611 trial = next_nonnote_insn (trial))
3615 /* If we have passed a label, we no longer own this thread. */
3616 if (GET_CODE (trial) == CODE_LABEL)
3622 pat = PATTERN (trial);
3623 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
3626 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
3627 don't separate or copy insns that set and use CC0. */
3628 if (! insn_references_resource_p (trial, &set, 1)
3629 && ! insn_sets_resource_p (trial, &set, 1)
3630 && ! insn_sets_resource_p (trial, &needed, 1)
3632 && ! (reg_mentioned_p (cc0_rtx, pat)
3633 && (! own_thread || ! sets_cc0_p (pat)))
3639 /* If TRIAL is redundant with some insn before INSN, we don't
3640 actually need to add it to the delay list; we can merely pretend
3642 if ((prior_insn = redundant_insn (trial, insn, delay_list)))
3644 fix_reg_dead_note (prior_insn, insn);
3647 update_block (trial, thread);
3648 if (trial == thread)
3650 thread = next_active_insn (thread);
3651 if (new_thread == trial)
3652 new_thread = thread;
3655 delete_insn (trial);
3659 update_reg_unused_notes (prior_insn, trial);
3660 new_thread = next_active_insn (trial);
3666 /* There are two ways we can win: If TRIAL doesn't set anything
3667 needed at the opposite thread and can't trap, or if it can
3668 go into an annulled delay slot. */
3670 && (condition == const_true_rtx
3671 || (! insn_sets_resource_p (trial, &opposite_needed, 1)
3672 && ! may_trap_p (pat))))
3675 trial = try_split (pat, trial, 0);
3676 if (new_thread == old_trial)
3678 if (thread == old_trial)
3680 pat = PATTERN (trial);
3681 if (eligible_for_delay (insn, *pslots_filled, trial, flags))
3685 #ifdef ANNUL_IFTRUE_SLOTS
3688 #ifdef ANNUL_IFFALSE_SLOTS
3694 trial = try_split (pat, trial, 0);
3695 if (new_thread == old_trial)
3697 if (thread == old_trial)
3699 pat = PATTERN (trial);
3700 if ((must_annul || delay_list == NULL) && (thread_if_true
3701 ? check_annul_list_true_false (0, delay_list)
3702 && eligible_for_annul_false (insn, *pslots_filled, trial, flags)
3703 : check_annul_list_true_false (1, delay_list)
3704 && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
3712 if (reg_mentioned_p (cc0_rtx, pat))
3713 link_cc0_insns (trial);
3716 /* If we own this thread, delete the insn. If this is the
3717 destination of a branch, show that a basic block status
3718 may have been updated. In any case, mark the new
3719 starting point of this thread. */
3722 update_block (trial, thread);
3723 if (trial == thread)
3725 thread = next_active_insn (thread);
3726 if (new_thread == trial)
3727 new_thread = thread;
3729 delete_insn (trial);
3732 new_thread = next_active_insn (trial);
3734 temp = own_thread ? trial : copy_rtx (trial);
3736 INSN_FROM_TARGET_P (temp) = 1;
3738 delay_list = add_to_delay_list (temp, delay_list);
3740 if (slots_to_fill == ++(*pslots_filled))
3742 /* Even though we have filled all the slots, we
3743 may be branching to a location that has a
3744 redundant insn. Skip any if so. */
3745 while (new_thread && ! own_thread
3746 && ! insn_sets_resource_p (new_thread, &set, 1)
3747 && ! insn_sets_resource_p (new_thread, &needed, 1)
3748 && ! insn_references_resource_p (new_thread,
3751 = redundant_insn (new_thread, insn,
3754 /* We know we do not own the thread, so no need
3755 to call update_block and delete_insn. */
3756 fix_reg_dead_note (prior_insn, insn);
3757 update_reg_unused_notes (prior_insn, new_thread);
3758 new_thread = next_active_insn (new_thread);
3768 /* This insn can't go into a delay slot. */
3770 mark_set_resources (trial, &set, 0, 1);
3771 mark_referenced_resources (trial, &needed, 1);
3773 /* Ensure we don't put insns between the setting of cc and the comparison
3774 by moving a setting of cc into an earlier delay slot since these insns
3775 could clobber the condition code. */
3778 /* If this insn is a register-register copy and the next insn has
3779 a use of our destination, change it to use our source. That way,
3780 it will become a candidate for our delay slot the next time
3781 through this loop. This case occurs commonly in loops that
3784 We could check for more complex cases than those tested below,
3785 but it doesn't seem worth it. It might also be a good idea to try
3786 to swap the two insns. That might do better.
3788 We can't do this if the next insn modifies our destination, because
3789 that would make the replacement into the insn invalid. We also can't
3790 do this if it modifies our source, because it might be an earlyclobber
3791 operand. This latter test also prevents updating the contents of
3794 if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
3795 && GET_CODE (SET_SRC (pat)) == REG
3796 && GET_CODE (SET_DEST (pat)) == REG)
3798 rtx next = next_nonnote_insn (trial);
3800 if (next && GET_CODE (next) == INSN
3801 && GET_CODE (PATTERN (next)) != USE
3802 && ! reg_set_p (SET_DEST (pat), next)
3803 && ! reg_set_p (SET_SRC (pat), next)
3804 && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
3805 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
3809 /* If we stopped on a branch insn that has delay slots, see if we can
3810 steal some of the insns in those slots. */
3811 if (trial && GET_CODE (trial) == INSN
3812 && GET_CODE (PATTERN (trial)) == SEQUENCE
3813 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
3815 /* If this is the `true' thread, we will want to follow the jump,
3816 so we can only do this if we have taken everything up to here. */
3817 if (thread_if_true && trial == new_thread)
3819 = steal_delay_list_from_target (insn, condition, PATTERN (trial),
3820 delay_list, &set, &needed,
3821 &opposite_needed, slots_to_fill,
3822 pslots_filled, &must_annul,
3824 else if (! thread_if_true)
3826 = steal_delay_list_from_fallthrough (insn, condition,
3828 delay_list, &set, &needed,
3829 &opposite_needed, slots_to_fill,
3830 pslots_filled, &must_annul);
3833 /* If we haven't found anything for this delay slot and it is very
3834 likely that the branch will be taken, see if the insn at our target
3835 increments or decrements a register with an increment that does not
3836 depend on the destination register. If so, try to place the opposite
3837 arithmetic insn after the jump insn and put the arithmetic insn in the
3838 delay slot. If we can't do this, return. */
3839 if (delay_list == 0 && likely && new_thread
3840 && GET_CODE (new_thread) == INSN
3841 && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
3842 && asm_noperands (PATTERN (new_thread)) < 0)
3844 rtx pat = PATTERN (new_thread);
3849 pat = PATTERN (trial);
3851 if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
3852 || ! eligible_for_delay (insn, 0, trial, flags))
3855 dest = SET_DEST (pat), src = SET_SRC (pat);
3856 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
3857 && rtx_equal_p (XEXP (src, 0), dest)
3858 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
3860 rtx other = XEXP (src, 1);
3864 /* If this is a constant adjustment, use the same code with
3865 the negated constant. Otherwise, reverse the sense of the
3867 if (GET_CODE (other) == CONST_INT)
3868 new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
3869 negate_rtx (GET_MODE (src), other));
3871 new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
3872 GET_MODE (src), dest, other);
3874 ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith),
3877 if (recog_memoized (ninsn) < 0
3878 || (extract_insn (ninsn), ! constrain_operands (1)))
3880 delete_insn (ninsn);
3886 update_block (trial, thread);
3887 if (trial == thread)
3889 thread = next_active_insn (thread);
3890 if (new_thread == trial)
3891 new_thread = thread;
3893 delete_insn (trial);
3896 new_thread = next_active_insn (trial);
3898 ninsn = own_thread ? trial : copy_rtx (trial);
3900 INSN_FROM_TARGET_P (ninsn) = 1;
3902 delay_list = add_to_delay_list (ninsn, NULL_RTX);
3907 if (delay_list && must_annul)
3908 INSN_ANNULLED_BRANCH_P (insn) = 1;
3910 /* If we are to branch into the middle of this thread, find an appropriate
3911 label or make a new one if none, and redirect INSN to it. If we hit the
3912 end of the function, use the end-of-function label. */
3913 if (new_thread != thread)
3917 if (! thread_if_true)
3920 if (new_thread && GET_CODE (new_thread) == JUMP_INSN
3921 && (simplejump_p (new_thread)
3922 || GET_CODE (PATTERN (new_thread)) == RETURN)
3923 && redirect_with_delay_list_safe_p (insn,
3924 JUMP_LABEL (new_thread),
3926 new_thread = follow_jumps (JUMP_LABEL (new_thread));
3928 if (new_thread == 0)
3929 label = find_end_label ();
3930 else if (GET_CODE (new_thread) == CODE_LABEL)
3933 label = get_label_before (new_thread);
3935 reorg_redirect_jump (insn, label);
3941 /* Make another attempt to find insns to place in delay slots.
3943 We previously looked for insns located in front of the delay insn
3944 and, for non-jump delay insns, located behind the delay insn.
3946 Here only try to schedule jump insns and try to move insns from either
3947 the target or the following insns into the delay slot. If annulling is
3948 supported, we will be likely to do this. Otherwise, we can do this only
3952 fill_eager_delay_slots ()
3956 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
3958 for (i = 0; i < num_unfilled_slots; i++)
3961 rtx target_label, insn_at_target, fallthrough_insn;
3964 int own_fallthrough;
3965 int prediction, slots_to_fill, slots_filled;
3967 insn = unfilled_slots_base[i];
3969 || INSN_DELETED_P (insn)
3970 || GET_CODE (insn) != JUMP_INSN
3971 || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
3974 slots_to_fill = num_delay_slots (insn);
3975 /* Some machine description have defined instructions to have
3976 delay slots only in certain circumstances which may depend on
3977 nearby insns (which change due to reorg's actions).
3979 For example, the PA port normally has delay slots for unconditional
3982 However, the PA port claims such jumps do not have a delay slot
3983 if they are immediate successors of certain CALL_INSNs. This
3984 allows the port to favor filling the delay slot of the call with
3985 the unconditional jump. */
3986 if (slots_to_fill == 0)
3990 target_label = JUMP_LABEL (insn);
3991 condition = get_branch_condition (insn, target_label);
3996 /* Get the next active fallthrough and target insns and see if we own
3997 them. Then see whether the branch is likely true. We don't need
3998 to do a lot of this for unconditional branches. */
4000 insn_at_target = next_active_insn (target_label);
4001 own_target = own_thread_p (target_label, target_label, 0);
4003 if (condition == const_true_rtx)
4005 own_fallthrough = 0;
4006 fallthrough_insn = 0;
4011 fallthrough_insn = next_active_insn (insn);
4012 own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
4013 prediction = mostly_true_jump (insn, condition);
4016 /* If this insn is expected to branch, first try to get insns from our
4017 target, then our fallthrough insns. If it is not, expected to branch,
4018 try the other order. */
4023 = fill_slots_from_thread (insn, condition, insn_at_target,
4024 fallthrough_insn, prediction == 2, 1,
4026 slots_to_fill, &slots_filled, delay_list);
4028 if (delay_list == 0 && own_fallthrough)
4030 /* Even though we didn't find anything for delay slots,
4031 we might have found a redundant insn which we deleted
4032 from the thread that was filled. So we have to recompute
4033 the next insn at the target. */
4034 target_label = JUMP_LABEL (insn);
4035 insn_at_target = next_active_insn (target_label);
4038 = fill_slots_from_thread (insn, condition, fallthrough_insn,
4039 insn_at_target, 0, 0,
4041 slots_to_fill, &slots_filled,
4047 if (own_fallthrough)
4049 = fill_slots_from_thread (insn, condition, fallthrough_insn,
4050 insn_at_target, 0, 0,
4052 slots_to_fill, &slots_filled,
4055 if (delay_list == 0)
4057 = fill_slots_from_thread (insn, condition, insn_at_target,
4058 next_active_insn (insn), 0, 1,
4060 slots_to_fill, &slots_filled,
4065 unfilled_slots_base[i]
4066 = emit_delay_sequence (insn, delay_list, slots_filled);
4068 if (slots_to_fill == slots_filled)
4069 unfilled_slots_base[i] = 0;
4071 note_delay_statistics (slots_filled, 1);
4075 /* Once we have tried two ways to fill a delay slot, make a pass over the
4076 code to try to improve the results and to do such things as more jump
4080 relax_delay_slots (first)
4083 register rtx insn, next, pat;
4084 register rtx trial, delay_insn, target_label;
4086 /* Look at every JUMP_INSN and see if we can improve it. */
4087 for (insn = first; insn; insn = next)
4091 next = next_active_insn (insn);
4093 /* If this is a jump insn, see if it now jumps to a jump, jumps to
4094 the next insn, or jumps to a label that is not the last of a
4095 group of consecutive labels. */
4096 if (GET_CODE (insn) == JUMP_INSN
4097 && (condjump_p (insn) || condjump_in_parallel_p (insn))
4098 && (target_label = JUMP_LABEL (insn)) != 0)
4100 target_label = follow_jumps (target_label);
4101 target_label = prev_label (next_active_insn (target_label));
4103 if (target_label == 0)
4104 target_label = find_end_label ();
4106 if (next_active_insn (target_label) == next
4107 && ! condjump_in_parallel_p (insn))
4113 if (target_label != JUMP_LABEL (insn))
4114 reorg_redirect_jump (insn, target_label);
4116 /* See if this jump branches around a unconditional jump.
4117 If so, invert this jump and point it to the target of the
4119 if (next && GET_CODE (next) == JUMP_INSN
4120 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
4121 && next_active_insn (target_label) == next_active_insn (next)
4122 && no_labels_between_p (insn, next))
4124 rtx label = JUMP_LABEL (next);
4126 /* Be careful how we do this to avoid deleting code or
4127 labels that are momentarily dead. See similar optimization
4130 We also need to ensure we properly handle the case when
4131 invert_jump fails. */
4133 ++LABEL_NUSES (target_label);
4135 ++LABEL_NUSES (label);
4137 if (invert_jump (insn, label))
4144 --LABEL_NUSES (label);
4146 if (--LABEL_NUSES (target_label) == 0)
4147 delete_insn (target_label);
4153 /* If this is an unconditional jump and the previous insn is a
4154 conditional jump, try reversing the condition of the previous
4155 insn and swapping our targets. The next pass might be able to
4158 Don't do this if we expect the conditional branch to be true, because
4159 we would then be making the more common case longer. */
4161 if (GET_CODE (insn) == JUMP_INSN
4162 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
4163 && (other = prev_active_insn (insn)) != 0
4164 && (condjump_p (other) || condjump_in_parallel_p (other))
4165 && no_labels_between_p (other, insn)
4166 && 0 > mostly_true_jump (other,
4167 get_branch_condition (other,
4168 JUMP_LABEL (other))))
4170 rtx other_target = JUMP_LABEL (other);
4171 target_label = JUMP_LABEL (insn);
4173 /* Increment the count of OTHER_TARGET, so it doesn't get deleted
4174 as we move the label. */
4176 ++LABEL_NUSES (other_target);
4178 if (invert_jump (other, target_label))
4179 reorg_redirect_jump (insn, other_target);
4182 --LABEL_NUSES (other_target);
4185 /* Now look only at cases where we have filled a delay slot. */
4186 if (GET_CODE (insn) != INSN
4187 || GET_CODE (PATTERN (insn)) != SEQUENCE)
4190 pat = PATTERN (insn);
4191 delay_insn = XVECEXP (pat, 0, 0);
4193 /* See if the first insn in the delay slot is redundant with some
4194 previous insn. Remove it from the delay slot if so; then set up
4195 to reprocess this insn. */
4196 if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
4198 delete_from_delay_slot (XVECEXP (pat, 0, 1));
4199 next = prev_active_insn (next);
4203 /* Now look only at the cases where we have a filled JUMP_INSN. */
4204 if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4205 || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
4206 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
4209 target_label = JUMP_LABEL (delay_insn);
4213 /* If this jump goes to another unconditional jump, thread it, but
4214 don't convert a jump into a RETURN here. */
4215 trial = follow_jumps (target_label);
4216 /* We use next_real_insn instead of next_active_insn, so that
4217 the special USE insns emitted by reorg won't be ignored.
4218 If they are ignored, then they will get deleted if target_label
4219 is now unreachable, and that would cause mark_target_live_regs
4221 trial = prev_label (next_real_insn (trial));
4222 if (trial == 0 && target_label != 0)
4223 trial = find_end_label ();
4225 if (trial != target_label
4226 && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
4228 reorg_redirect_jump (delay_insn, trial);
4229 target_label = trial;
4232 /* If the first insn at TARGET_LABEL is redundant with a previous
4233 insn, redirect the jump to the following insn process again. */
4234 trial = next_active_insn (target_label);
4235 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
4236 && redundant_insn (trial, insn, 0))
4240 /* Figure out where to emit the special USE insn so we don't
4241 later incorrectly compute register live/death info. */
4242 tmp = next_active_insn (trial);
4244 tmp = find_end_label ();
4246 /* Insert the special USE insn and update dataflow info. */
4247 update_block (trial, tmp);
4249 /* Now emit a label before the special USE insn, and
4250 redirect our jump to the new label. */
4251 target_label = get_label_before (PREV_INSN (tmp));
4252 reorg_redirect_jump (delay_insn, target_label);
4257 /* Similarly, if it is an unconditional jump with one insn in its
4258 delay list and that insn is redundant, thread the jump. */
4259 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
4260 && XVECLEN (PATTERN (trial), 0) == 2
4261 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
4262 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
4263 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
4264 && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
4266 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
4267 if (target_label == 0)
4268 target_label = find_end_label ();
4270 if (redirect_with_delay_slots_safe_p (delay_insn, target_label,
4273 reorg_redirect_jump (delay_insn, target_label);
4280 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
4281 && prev_active_insn (target_label) == insn
4282 && ! condjump_in_parallel_p (delay_insn)
4284 /* If the last insn in the delay slot sets CC0 for some insn,
4285 various code assumes that it is in a delay slot. We could
4286 put it back where it belonged and delete the register notes,
4287 but it doesn't seem worthwhile in this uncommon case. */
4288 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
4289 REG_CC_USER, NULL_RTX)
4295 /* All this insn does is execute its delay list and jump to the
4296 following insn. So delete the jump and just execute the delay
4299 We do this by deleting the INSN containing the SEQUENCE, then
4300 re-emitting the insns separately, and then deleting the jump.
4301 This allows the count of the jump target to be properly
4304 /* Clear the from target bit, since these insns are no longer
4306 for (i = 0; i < XVECLEN (pat, 0); i++)
4307 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
4309 trial = PREV_INSN (insn);
4311 emit_insn_after (pat, trial);
4312 delete_scheduled_jump (delay_insn);
4316 /* See if this is an unconditional jump around a single insn which is
4317 identical to the one in its delay slot. In this case, we can just
4318 delete the branch and the insn in its delay slot. */
4319 if (next && GET_CODE (next) == INSN
4320 && prev_label (next_active_insn (next)) == target_label
4321 && simplejump_p (insn)
4322 && XVECLEN (pat, 0) == 2
4323 && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
4329 /* See if this jump (with its delay slots) branches around another
4330 jump (without delay slots). If so, invert this jump and point
4331 it to the target of the second jump. We cannot do this for
4332 annulled jumps, though. Again, don't convert a jump to a RETURN
4334 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
4335 && next && GET_CODE (next) == JUMP_INSN
4336 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
4337 && next_active_insn (target_label) == next_active_insn (next)
4338 && no_labels_between_p (insn, next))
4340 rtx label = JUMP_LABEL (next);
4341 rtx old_label = JUMP_LABEL (delay_insn);
4344 label = find_end_label ();
4346 if (redirect_with_delay_slots_safe_p (delay_insn, label, insn))
4348 /* Be careful how we do this to avoid deleting code or labels
4349 that are momentarily dead. See similar optimization in
4352 ++LABEL_NUSES (old_label);
4354 if (invert_jump (delay_insn, label))
4358 /* Must update the INSN_FROM_TARGET_P bits now that
4359 the branch is reversed, so that mark_target_live_regs
4360 will handle the delay slot insn correctly. */
4361 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
4363 rtx slot = XVECEXP (PATTERN (insn), 0, i);
4364 INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
4371 if (old_label && --LABEL_NUSES (old_label) == 0)
4372 delete_insn (old_label);
4377 /* If we own the thread opposite the way this insn branches, see if we
4378 can merge its delay slots with following insns. */
4379 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4380 && own_thread_p (NEXT_INSN (insn), 0, 1))
4381 try_merge_delay_insns (insn, next);
4382 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
4383 && own_thread_p (target_label, target_label, 0))
4384 try_merge_delay_insns (insn, next_active_insn (target_label));
4386 /* If we get here, we haven't deleted INSN. But we may have deleted
4387 NEXT, so recompute it. */
4388 next = next_active_insn (insn);
4394 /* Look for filled jumps to the end of function label. We can try to convert
4395 them into RETURN insns if the insns in the delay slot are valid for the
4399 make_return_insns (first)
4402 rtx insn, jump_insn, pat;
4403 rtx real_return_label = end_of_function_label;
4406 /* See if there is a RETURN insn in the function other than the one we
4407 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
4408 into a RETURN to jump to it. */
4409 for (insn = first; insn; insn = NEXT_INSN (insn))
4410 if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
4412 real_return_label = get_label_before (insn);
4416 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
4417 was equal to END_OF_FUNCTION_LABEL. */
4418 LABEL_NUSES (real_return_label)++;
4420 /* Clear the list of insns to fill so we can use it. */
4421 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4423 for (insn = first; insn; insn = NEXT_INSN (insn))
4427 /* Only look at filled JUMP_INSNs that go to the end of function
4429 if (GET_CODE (insn) != INSN
4430 || GET_CODE (PATTERN (insn)) != SEQUENCE
4431 || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
4432 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
4435 pat = PATTERN (insn);
4436 jump_insn = XVECEXP (pat, 0, 0);
4438 /* If we can't make the jump into a RETURN, try to redirect it to the best
4439 RETURN and go on to the next insn. */
4440 if (! reorg_redirect_jump (jump_insn, NULL_RTX))
4442 /* Make sure redirecting the jump will not invalidate the delay
4444 if (redirect_with_delay_slots_safe_p (jump_insn,
4447 reorg_redirect_jump (jump_insn, real_return_label);
4451 /* See if this RETURN can accept the insns current in its delay slot.
4452 It can if it has more or an equal number of slots and the contents
4453 of each is valid. */
4455 flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
4456 slots = num_delay_slots (jump_insn);
4457 if (slots >= XVECLEN (pat, 0) - 1)
4459 for (i = 1; i < XVECLEN (pat, 0); i++)
4461 #ifdef ANNUL_IFFALSE_SLOTS
4462 (INSN_ANNULLED_BRANCH_P (jump_insn)
4463 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4464 ? eligible_for_annul_false (jump_insn, i - 1,
4465 XVECEXP (pat, 0, i), flags) :
4467 #ifdef ANNUL_IFTRUE_SLOTS
4468 (INSN_ANNULLED_BRANCH_P (jump_insn)
4469 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
4470 ? eligible_for_annul_true (jump_insn, i - 1,
4471 XVECEXP (pat, 0, i), flags) :
4473 eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i), flags)))
4479 if (i == XVECLEN (pat, 0))
4482 /* We have to do something with this insn. If it is an unconditional
4483 RETURN, delete the SEQUENCE and output the individual insns,
4484 followed by the RETURN. Then set things up so we try to find
4485 insns for its delay slots, if it needs some. */
4486 if (GET_CODE (PATTERN (jump_insn)) == RETURN)
4488 rtx prev = PREV_INSN (insn);
4491 for (i = 1; i < XVECLEN (pat, 0); i++)
4492 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
4494 insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
4495 emit_barrier_after (insn);
4498 obstack_ptr_grow (&unfilled_slots_obstack, insn);
4501 /* It is probably more efficient to keep this with its current
4502 delay slot as a branch to a RETURN. */
4503 reorg_redirect_jump (jump_insn, real_return_label);
4506 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
4507 new delay slots we have created. */
4508 if (--LABEL_NUSES (real_return_label) == 0)
4509 delete_insn (real_return_label);
4511 fill_simple_delay_slots (1);
4512 fill_simple_delay_slots (0);
4516 /* Try to find insns to place in delay slots. */
4519 dbr_schedule (first, file)
4523 rtx insn, next, epilogue_insn = 0;
4526 int old_flag_no_peephole = flag_no_peephole;
4528 /* Execute `final' once in prescan mode to delete any insns that won't be
4529 used. Don't let final try to do any peephole optimization--it will
4530 ruin dataflow information for this pass. */
4532 flag_no_peephole = 1;
4533 final (first, 0, NO_DEBUG, 1, 1);
4534 flag_no_peephole = old_flag_no_peephole;
4537 /* If the current function has no insns other than the prologue and
4538 epilogue, then do not try to fill any delay slots. */
4539 if (n_basic_blocks == 0)
4542 /* Find the highest INSN_UID and allocate and initialize our map from
4543 INSN_UID's to position in code. */
4544 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
4546 if (INSN_UID (insn) > max_uid)
4547 max_uid = INSN_UID (insn);
4548 if (GET_CODE (insn) == NOTE
4549 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
4550 epilogue_insn = insn;
4553 uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int));
4554 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
4555 uid_to_ruid[INSN_UID (insn)] = i;
4557 /* Initialize the list of insns that need filling. */
4558 if (unfilled_firstobj == 0)
4560 gcc_obstack_init (&unfilled_slots_obstack);
4561 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4564 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
4568 INSN_ANNULLED_BRANCH_P (insn) = 0;
4569 INSN_FROM_TARGET_P (insn) = 0;
4571 /* Skip vector tables. We can't get attributes for them. */
4572 if (GET_CODE (insn) == JUMP_INSN
4573 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
4574 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
4577 if (num_delay_slots (insn) > 0)
4578 obstack_ptr_grow (&unfilled_slots_obstack, insn);
4580 /* Ensure all jumps go to the last of a set of consecutive labels. */
4581 if (GET_CODE (insn) == JUMP_INSN
4582 && (condjump_p (insn) || condjump_in_parallel_p (insn))
4583 && JUMP_LABEL (insn) != 0
4584 && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
4585 != JUMP_LABEL (insn)))
4586 redirect_jump (insn, target);
4589 /* Indicate what resources are required to be valid at the end of the current
4590 function. The condition code never is and memory always is. If the
4591 frame pointer is needed, it is and so is the stack pointer unless
4592 EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
4593 stack pointer is. Registers used to return the function value are
4594 needed. Registers holding global variables are needed. */
4596 end_of_function_needs.cc = 0;
4597 end_of_function_needs.memory = 1;
4598 end_of_function_needs.unch_memory = 0;
4599 CLEAR_HARD_REG_SET (end_of_function_needs.regs);
4601 if (frame_pointer_needed)
4603 SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
4604 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4605 SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM);
4607 #ifdef EXIT_IGNORE_STACK
4608 if (! EXIT_IGNORE_STACK
4609 || current_function_sp_is_unchanging)
4611 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4614 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
4616 if (current_function_return_rtx != 0)
4617 mark_referenced_resources (current_function_return_rtx,
4618 &end_of_function_needs, 1);
4620 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4622 #ifdef EPILOGUE_USES
4623 || EPILOGUE_USES (i)
4626 SET_HARD_REG_BIT (end_of_function_needs.regs, i);
4628 /* The registers required to be live at the end of the function are
4629 represented in the flow information as being dead just prior to
4630 reaching the end of the function. For example, the return of a value
4631 might be represented by a USE of the return register immediately
4632 followed by an unconditional jump to the return label where the
4633 return label is the end of the RTL chain. The end of the RTL chain
4634 is then taken to mean that the return register is live.
4636 This sequence is no longer maintained when epilogue instructions are
4637 added to the RTL chain. To reconstruct the original meaning, the
4638 start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
4639 point where these registers become live (start_of_epilogue_needs).
4640 If epilogue instructions are present, the registers set by those
4641 instructions won't have been processed by flow. Thus, those
4642 registers are additionally required at the end of the RTL chain
4643 (end_of_function_needs). */
4645 start_of_epilogue_needs = end_of_function_needs;
4647 while ((epilogue_insn = next_nonnote_insn (epilogue_insn)))
4648 mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1);
4650 /* Show we haven't computed an end-of-function label yet. */
4651 end_of_function_label = 0;
4653 /* Allocate and initialize the tables used by mark_target_live_regs. */
4655 = (struct target_info **) alloca ((TARGET_HASH_PRIME
4656 * sizeof (struct target_info *)));
4657 bzero ((char *) target_hash_table,
4658 TARGET_HASH_PRIME * sizeof (struct target_info *));
4660 bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
4661 bzero ((char *) bb_ticks, n_basic_blocks * sizeof (int));
4663 /* Initialize the statistics for this function. */
4664 bzero ((char *) num_insns_needing_delays, sizeof num_insns_needing_delays);
4665 bzero ((char *) num_filled_delays, sizeof num_filled_delays);
4667 /* Now do the delay slot filling. Try everything twice in case earlier
4668 changes make more slots fillable. */
4670 for (reorg_pass_number = 0;
4671 reorg_pass_number < MAX_REORG_PASSES;
4672 reorg_pass_number++)
4674 fill_simple_delay_slots (1);
4675 fill_simple_delay_slots (0);
4676 fill_eager_delay_slots ();
4677 relax_delay_slots (first);
4680 /* Delete any USE insns made by update_block; subsequent passes don't need
4681 them or know how to deal with them. */
4682 for (insn = first; insn; insn = next)
4684 next = NEXT_INSN (insn);
4686 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
4687 && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
4688 next = delete_insn (insn);
4691 /* If we made an end of function label, indicate that it is now
4692 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
4693 If it is now unused, delete it. */
4694 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
4695 delete_insn (end_of_function_label);
4698 if (HAVE_return && end_of_function_label != 0)
4699 make_return_insns (first);
4702 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
4704 /* It is not clear why the line below is needed, but it does seem to be. */
4705 unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
4707 /* Reposition the prologue and epilogue notes in case we moved the
4708 prologue/epilogue insns. */
4709 reposition_prologue_and_epilogue_notes (first);
4713 register int i, j, need_comma;
4715 for (reorg_pass_number = 0;
4716 reorg_pass_number < MAX_REORG_PASSES;
4717 reorg_pass_number++)
4719 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
4720 for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
4723 fprintf (file, ";; Reorg function #%d\n", i);
4725 fprintf (file, ";; %d insns needing delay slots\n;; ",
4726 num_insns_needing_delays[i][reorg_pass_number]);
4728 for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
4729 if (num_filled_delays[i][j][reorg_pass_number])
4732 fprintf (file, ", ");
4734 fprintf (file, "%d got %d delays",
4735 num_filled_delays[i][j][reorg_pass_number], j);
4737 fprintf (file, "\n");
4742 /* For all JUMP insns, fill in branch prediction notes, so that during
4743 assembler output a target can set branch prediction bits in the code.
4744 We have to do this now, as up until this point the destinations of
4745 JUMPS can be moved around and changed, but past right here that cannot
4747 for (insn = first; insn; insn = NEXT_INSN (insn))
4751 if (GET_CODE (insn) == INSN)
4753 rtx pat = PATTERN (insn);
4755 if (GET_CODE (pat) == SEQUENCE)
4756 insn = XVECEXP (pat, 0, 0);
4758 if (GET_CODE (insn) != JUMP_INSN)
4761 pred_flags = get_jump_flags (insn, JUMP_LABEL (insn));
4762 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED,
4763 GEN_INT (pred_flags),
4767 #endif /* DELAY_SLOTS */