1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
5 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
6 Hacked by Michael Tiemann (tiemann@cygnus.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction reorganization pass.
26 This pass runs after register allocation and final jump
27 optimization. It should be the last pass to run before peephole.
28 It serves primarily to fill delay slots of insns, typically branch
29 and call insns. Other insns typically involve more complicated
30 interactions of data dependencies and resource constraints, and
31 are better handled by scheduling before register allocation (by the
32 function `schedule_insns').
34 The Branch Penalty is the number of extra cycles that are needed to
35 execute a branch insn. On an ideal machine, branches take a single
36 cycle, and the Branch Penalty is 0. Several RISC machines approach
37 branch delays differently:
39 The MIPS has a single branch delay slot. Most insns
40 (except other branches) can be used to fill this slot. When the
41 slot is filled, two insns execute in two cycles, reducing the
42 branch penalty to zero.
44 The SPARC always has a branch delay slot, but its effects can be
45 annulled when the branch is not taken. This means that failing to
46 find other sources of insns, we can hoist an insn from the branch
47 target that would only be safe to execute knowing that the branch
50 The HP-PA always has a branch delay slot. For unconditional branches
51 its effects can be annulled when the branch is taken. The effects
52 of the delay slot in a conditional branch can be nullified for forward
53 taken branches, or for untaken backward branches. This means
54 we can hoist insns from the fall-through path for forward branches or
55 steal insns from the target of backward branches.
57 The TMS320C3x and C4x have three branch delay slots. When the three
58 slots are filled, the branch penalty is zero. Most insns can fill the
59 delay slots except jump insns.
61 Three techniques for filling delay slots have been implemented so far:
63 (1) `fill_simple_delay_slots' is the simplest, most efficient way
64 to fill delay slots. This pass first looks for insns which come
65 from before the branch and which are safe to execute after the
66 branch. Then it searches after the insn requiring delay slots or,
67 in the case of a branch, for insns that are after the point at
68 which the branch merges into the fallthrough code, if such a point
69 exists. When such insns are found, the branch penalty decreases
70 and no code expansion takes place.
72 (2) `fill_eager_delay_slots' is more complicated: it is used for
73 scheduling conditional jumps, or for scheduling jumps which cannot
74 be filled using (1). A machine need not have annulled jumps to use
75 this strategy, but it helps (by keeping more options open).
76 `fill_eager_delay_slots' tries to guess the direction the branch
77 will go; if it guesses right 100% of the time, it can reduce the
78 branch penalty as much as `fill_simple_delay_slots' does. If it
79 guesses wrong 100% of the time, it might as well schedule nops. When
80 `fill_eager_delay_slots' takes insns from the fall-through path of
81 the jump, usually there is no code expansion; when it takes insns
82 from the branch target, there is code expansion if it is not the
83 only way to reach that target.
85 (3) `relax_delay_slots' uses a set of rules to simplify code that
86 has been reorganized by (1) and (2). It finds cases where
87 conditional test can be eliminated, jumps can be threaded, extra
88 insns can be eliminated, etc. It is the job of (1) and (2) to do a
89 good job of scheduling locally; `relax_delay_slots' takes care of
90 making the various individual schedules work well together. It is
91 especially tuned to handle the control flow interactions of branch
92 insns. It does nothing for insns with delay slots that do not
95 On machines that use CC0, we are very conservative. We will not make
96 a copy of an insn involving CC0 since we want to maintain a 1-1
97 correspondence between the insn that sets and uses CC0. The insns are
98 allowed to be separated by placing an insn that sets CC0 (but not an insn
99 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
100 delay slot. In that case, we point each insn at the other with REG_CC_USER
101 and REG_CC_SETTER notes. Note that these restrictions affect very few
102 machines because most RISC machines with delay slots will not use CC0
103 (the RT is the only known exception at this point).
107 The Acorn Risc Machine can conditionally execute most insns, so
108 it is profitable to move single insns into a position to execute
109 based on the condition code of the previous insn.
111 The HP-PA can conditionally nullify insns, providing a similar
112 effect to the ARM, differing mostly in which insn is "in charge". */
116 #include "coretypes.h"
122 #include "function.h"
123 #include "insn-config.h"
124 #include "conditions.h"
125 #include "hard-reg-set.h"
126 #include "basic-block.h"
132 #include "insn-attr.h"
133 #include "resource.h"
138 #include "tree-pass.h"
142 #ifndef ANNUL_IFTRUE_SLOTS
143 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
145 #ifndef ANNUL_IFFALSE_SLOTS
146 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
149 /* Insns which have delay slots that have not yet been filled. */
151 static struct obstack unfilled_slots_obstack
;
152 static rtx
*unfilled_firstobj
;
154 /* Define macros to refer to the first and last slot containing unfilled
155 insns. These are used because the list may move and its address
156 should be recomputed at each use. */
158 #define unfilled_slots_base \
159 ((rtx *) obstack_base (&unfilled_slots_obstack))
161 #define unfilled_slots_next \
162 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
164 /* Points to the label before the end of the function. */
165 static rtx end_of_function_label
;
167 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
168 not always monotonically increase. */
169 static int *uid_to_ruid
;
171 /* Highest valid index in `uid_to_ruid'. */
174 static int stop_search_p (rtx
, int);
175 static int resource_conflicts_p (struct resources
*, struct resources
*);
176 static int insn_references_resource_p (rtx
, struct resources
*, int);
177 static int insn_sets_resource_p (rtx
, struct resources
*, int);
178 static rtx
find_end_label (void);
179 static rtx
emit_delay_sequence (rtx
, rtx
, int);
180 static rtx
add_to_delay_list (rtx
, rtx
);
181 static rtx
delete_from_delay_slot (rtx
);
182 static void delete_scheduled_jump (rtx
);
183 static void note_delay_statistics (int, int);
184 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
185 static rtx
optimize_skip (rtx
);
187 static int get_jump_flags (rtx
, rtx
);
188 static int rare_destination (rtx
);
189 static int mostly_true_jump (rtx
, rtx
);
190 static rtx
get_branch_condition (rtx
, rtx
);
191 static int condition_dominates_p (rtx
, rtx
);
192 static int redirect_with_delay_slots_safe_p (rtx
, rtx
, rtx
);
193 static int redirect_with_delay_list_safe_p (rtx
, rtx
, rtx
);
194 static int check_annul_list_true_false (int, rtx
);
195 static rtx
steal_delay_list_from_target (rtx
, rtx
, rtx
, rtx
,
199 int, int *, int *, rtx
*);
200 static rtx
steal_delay_list_from_fallthrough (rtx
, rtx
, rtx
, rtx
,
205 static void try_merge_delay_insns (rtx
, rtx
);
206 static rtx
redundant_insn (rtx
, rtx
, rtx
);
207 static int own_thread_p (rtx
, rtx
, int);
208 static void update_block (rtx
, rtx
);
209 static int reorg_redirect_jump (rtx
, rtx
);
210 static void update_reg_dead_notes (rtx
, rtx
);
211 static void fix_reg_dead_note (rtx
, rtx
);
212 static void update_reg_unused_notes (rtx
, rtx
);
213 static void fill_simple_delay_slots (int);
214 static rtx
fill_slots_from_thread (rtx
, rtx
, rtx
, rtx
,
217 static void fill_eager_delay_slots (void);
218 static void relax_delay_slots (rtx
);
220 static void make_return_insns (rtx
);
223 /* Return TRUE if this insn should stop the search for insn to fill delay
224 slots. LABELS_P indicates that labels should terminate the search.
225 In all cases, jumps terminate the search. */
228 stop_search_p (rtx insn
, int labels_p
)
233 /* If the insn can throw an exception that is caught within the function,
234 it may effectively perform a jump from the viewpoint of the function.
235 Therefore act like for a jump. */
236 if (can_throw_internal (insn
))
239 switch (GET_CODE (insn
))
253 /* OK unless it contains a delay slot or is an `asm' insn of some type.
254 We don't know anything about these. */
255 return (GET_CODE (PATTERN (insn
)) == SEQUENCE
256 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
257 || asm_noperands (PATTERN (insn
)) >= 0);
264 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
265 resource set contains a volatile memory reference. Otherwise, return FALSE. */
268 resource_conflicts_p (struct resources
*res1
, struct resources
*res2
)
270 if ((res1
->cc
&& res2
->cc
) || (res1
->memory
&& res2
->memory
)
271 || (res1
->unch_memory
&& res2
->unch_memory
)
272 || res1
->volatil
|| res2
->volatil
)
276 return (res1
->regs
& res2
->regs
) != HARD_CONST (0);
281 for (i
= 0; i
< HARD_REG_SET_LONGS
; i
++)
282 if ((res1
->regs
[i
] & res2
->regs
[i
]) != 0)
289 /* Return TRUE if any resource marked in RES, a `struct resources', is
290 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
291 routine is using those resources.
293 We compute this by computing all the resources referenced by INSN and
294 seeing if this conflicts with RES. It might be faster to directly check
295 ourselves, and this is the way it used to work, but it means duplicating
296 a large block of complex code. */
299 insn_references_resource_p (rtx insn
, struct resources
*res
,
300 int include_delayed_effects
)
302 struct resources insn_res
;
304 CLEAR_RESOURCE (&insn_res
);
305 mark_referenced_resources (insn
, &insn_res
, include_delayed_effects
);
306 return resource_conflicts_p (&insn_res
, res
);
309 /* Return TRUE if INSN modifies resources that are marked in RES.
310 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
311 included. CC0 is only modified if it is explicitly set; see comments
312 in front of mark_set_resources for details. */
315 insn_sets_resource_p (rtx insn
, struct resources
*res
,
316 int include_delayed_effects
)
318 struct resources insn_sets
;
320 CLEAR_RESOURCE (&insn_sets
);
321 mark_set_resources (insn
, &insn_sets
, 0, include_delayed_effects
);
322 return resource_conflicts_p (&insn_sets
, res
);
325 /* Find a label at the end of the function or before a RETURN. If there
326 is none, try to make one. If that fails, returns 0.
328 The property of such a label is that it is placed just before the
329 epilogue or a bare RETURN insn, so that another bare RETURN can be
330 turned into a jump to the label unconditionally. In particular, the
331 label cannot be placed before a RETURN insn with a filled delay slot.
333 ??? There may be a problem with the current implementation. Suppose
334 we start with a bare RETURN insn and call find_end_label. It may set
335 end_of_function_label just before the RETURN. Suppose the machinery
336 is able to fill the delay slot of the RETURN insn afterwards. Then
337 end_of_function_label is no longer valid according to the property
338 described above and find_end_label will still return it unmodified.
339 Note that this is probably mitigated by the following observation:
340 once end_of_function_label is made, it is very likely the target of
341 a jump, so filling the delay slot of the RETURN will be much more
345 find_end_label (void)
349 /* If we found one previously, return it. */
350 if (end_of_function_label
)
351 return end_of_function_label
;
353 /* Otherwise, see if there is a label at the end of the function. If there
354 is, it must be that RETURN insns aren't needed, so that is our return
355 label and we don't have to do anything else. */
357 insn
= get_last_insn ();
359 || (NONJUMP_INSN_P (insn
)
360 && (GET_CODE (PATTERN (insn
)) == USE
361 || GET_CODE (PATTERN (insn
)) == CLOBBER
)))
362 insn
= PREV_INSN (insn
);
364 /* When a target threads its epilogue we might already have a
365 suitable return insn. If so put a label before it for the
366 end_of_function_label. */
368 && JUMP_P (PREV_INSN (insn
))
369 && GET_CODE (PATTERN (PREV_INSN (insn
))) == RETURN
)
371 rtx temp
= PREV_INSN (PREV_INSN (insn
));
372 end_of_function_label
= gen_label_rtx ();
373 LABEL_NUSES (end_of_function_label
) = 0;
375 /* Put the label before an USE insns that may precede the RETURN insn. */
376 while (GET_CODE (temp
) == USE
)
377 temp
= PREV_INSN (temp
);
379 emit_label_after (end_of_function_label
, temp
);
382 else if (LABEL_P (insn
))
383 end_of_function_label
= insn
;
386 end_of_function_label
= gen_label_rtx ();
387 LABEL_NUSES (end_of_function_label
) = 0;
388 /* If the basic block reorder pass moves the return insn to
389 some other place try to locate it again and put our
390 end_of_function_label there. */
391 while (insn
&& ! (JUMP_P (insn
)
392 && (GET_CODE (PATTERN (insn
)) == RETURN
)))
393 insn
= PREV_INSN (insn
);
396 insn
= PREV_INSN (insn
);
398 /* Put the label before an USE insns that may proceed the
400 while (GET_CODE (insn
) == USE
)
401 insn
= PREV_INSN (insn
);
403 emit_label_after (end_of_function_label
, insn
);
414 /* The RETURN insn has its delay slot filled so we cannot
415 emit the label just before it. Since we already have
416 an epilogue and cannot emit a new RETURN, we cannot
417 emit the label at all. */
418 end_of_function_label
= NULL_RTX
;
419 return end_of_function_label
;
421 #endif /* HAVE_epilogue */
423 /* Otherwise, make a new label and emit a RETURN and BARRIER,
425 emit_label (end_of_function_label
);
427 /* We don't bother trying to create a return insn if the
428 epilogue has filled delay-slots; we would have to try and
429 move the delay-slot fillers to the delay-slots for the new
430 return insn or in front of the new return insn. */
431 if (crtl
->epilogue_delay_list
== NULL
434 /* The return we make may have delay slots too. */
435 rtx insn
= gen_return ();
436 insn
= emit_jump_insn (insn
);
438 if (num_delay_slots (insn
) > 0)
439 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
445 /* Show one additional use for this label so it won't go away until
447 ++LABEL_NUSES (end_of_function_label
);
449 return end_of_function_label
;
452 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
453 the pattern of INSN with the SEQUENCE.
455 Chain the insns so that NEXT_INSN of each insn in the sequence points to
456 the next and NEXT_INSN of the last insn in the sequence points to
457 the first insn after the sequence. Similarly for PREV_INSN. This makes
458 it easier to scan all insns.
460 Returns the SEQUENCE that replaces INSN. */
463 emit_delay_sequence (rtx insn
, rtx list
, int length
)
469 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
470 rtvec seqv
= rtvec_alloc (length
+ 1);
471 rtx seq
= gen_rtx_SEQUENCE (VOIDmode
, seqv
);
472 rtx seq_insn
= make_insn_raw (seq
);
473 rtx first
= get_insns ();
474 rtx last
= get_last_insn ();
476 /* Make a copy of the insn having delay slots. */
477 rtx delay_insn
= copy_rtx (insn
);
479 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
480 confuse further processing. Update LAST in case it was the last insn.
481 We will put the BARRIER back in later. */
482 if (NEXT_INSN (insn
) && BARRIER_P (NEXT_INSN (insn
)))
484 delete_related_insns (NEXT_INSN (insn
));
485 last
= get_last_insn ();
489 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
490 NEXT_INSN (seq_insn
) = NEXT_INSN (insn
);
491 PREV_INSN (seq_insn
) = PREV_INSN (insn
);
494 PREV_INSN (NEXT_INSN (seq_insn
)) = seq_insn
;
497 NEXT_INSN (PREV_INSN (seq_insn
)) = seq_insn
;
499 /* Note the calls to set_new_first_and_last_insn must occur after
500 SEQ_INSN has been completely spliced into the insn stream.
502 Otherwise CUR_INSN_UID will get set to an incorrect value because
503 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */
505 set_new_first_and_last_insn (first
, seq_insn
);
508 set_new_first_and_last_insn (seq_insn
, last
);
510 /* Build our SEQUENCE and rebuild the insn chain. */
511 XVECEXP (seq
, 0, 0) = delay_insn
;
512 INSN_DELETED_P (delay_insn
) = 0;
513 PREV_INSN (delay_insn
) = PREV_INSN (seq_insn
);
515 INSN_LOCATOR (seq_insn
) = INSN_LOCATOR (delay_insn
);
517 for (li
= list
; li
; li
= XEXP (li
, 1), i
++)
519 rtx tem
= XEXP (li
, 0);
522 /* Show that this copy of the insn isn't deleted. */
523 INSN_DELETED_P (tem
) = 0;
525 XVECEXP (seq
, 0, i
) = tem
;
526 PREV_INSN (tem
) = XVECEXP (seq
, 0, i
- 1);
527 NEXT_INSN (XVECEXP (seq
, 0, i
- 1)) = tem
;
529 /* SPARC assembler, for instance, emit warning when debug info is output
530 into the delay slot. */
531 if (INSN_LOCATOR (tem
) && !INSN_LOCATOR (seq_insn
))
532 INSN_LOCATOR (seq_insn
) = INSN_LOCATOR (tem
);
533 INSN_LOCATOR (tem
) = 0;
535 for (note
= REG_NOTES (tem
); note
; note
= next
)
537 next
= XEXP (note
, 1);
538 switch (REG_NOTE_KIND (note
))
541 /* Remove any REG_DEAD notes because we can't rely on them now
542 that the insn has been moved. */
543 remove_note (tem
, note
);
546 case REG_LABEL_OPERAND
:
547 case REG_LABEL_TARGET
:
548 /* Keep the label reference count up to date. */
549 if (LABEL_P (XEXP (note
, 0)))
550 LABEL_NUSES (XEXP (note
, 0)) ++;
559 NEXT_INSN (XVECEXP (seq
, 0, length
)) = NEXT_INSN (seq_insn
);
561 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
562 last insn in that SEQUENCE to point to us. Similarly for the first
563 insn in the following insn if it is a SEQUENCE. */
565 if (PREV_INSN (seq_insn
) && NONJUMP_INSN_P (PREV_INSN (seq_insn
))
566 && GET_CODE (PATTERN (PREV_INSN (seq_insn
))) == SEQUENCE
)
567 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn
)), 0,
568 XVECLEN (PATTERN (PREV_INSN (seq_insn
)), 0) - 1))
571 if (NEXT_INSN (seq_insn
) && NONJUMP_INSN_P (NEXT_INSN (seq_insn
))
572 && GET_CODE (PATTERN (NEXT_INSN (seq_insn
))) == SEQUENCE
)
573 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn
)), 0, 0)) = seq_insn
;
575 /* If there used to be a BARRIER, put it back. */
577 emit_barrier_after (seq_insn
);
579 gcc_assert (i
== length
+ 1);
584 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
585 be in the order in which the insns are to be executed. */
588 add_to_delay_list (rtx insn
, rtx delay_list
)
590 /* If we have an empty list, just make a new list element. If
591 INSN has its block number recorded, clear it since we may
592 be moving the insn to a new block. */
596 clear_hashed_info_for_insn (insn
);
597 return gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
600 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
602 XEXP (delay_list
, 1) = add_to_delay_list (insn
, XEXP (delay_list
, 1));
607 /* Delete INSN from the delay slot of the insn that it is in, which may
608 produce an insn with no delay slots. Return the new insn. */
611 delete_from_delay_slot (rtx insn
)
613 rtx trial
, seq_insn
, seq
, prev
;
618 /* We first must find the insn containing the SEQUENCE with INSN in its
619 delay slot. Do this by finding an insn, TRIAL, where
620 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
623 PREV_INSN (NEXT_INSN (trial
)) == trial
;
624 trial
= NEXT_INSN (trial
))
627 seq_insn
= PREV_INSN (NEXT_INSN (trial
));
628 seq
= PATTERN (seq_insn
);
630 if (NEXT_INSN (seq_insn
) && BARRIER_P (NEXT_INSN (seq_insn
)))
633 /* Create a delay list consisting of all the insns other than the one
634 we are deleting (unless we were the only one). */
635 if (XVECLEN (seq
, 0) > 2)
636 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
637 if (XVECEXP (seq
, 0, i
) != insn
)
638 delay_list
= add_to_delay_list (XVECEXP (seq
, 0, i
), delay_list
);
640 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
641 list, and rebuild the delay list if non-empty. */
642 prev
= PREV_INSN (seq_insn
);
643 trial
= XVECEXP (seq
, 0, 0);
644 delete_related_insns (seq_insn
);
645 add_insn_after (trial
, prev
, NULL
);
647 /* If there was a barrier after the old SEQUENCE, remit it. */
649 emit_barrier_after (trial
);
651 /* If there are any delay insns, remit them. Otherwise clear the
654 trial
= emit_delay_sequence (trial
, delay_list
, XVECLEN (seq
, 0) - 2);
655 else if (INSN_P (trial
))
656 INSN_ANNULLED_BRANCH_P (trial
) = 0;
658 INSN_FROM_TARGET_P (insn
) = 0;
660 /* Show we need to fill this insn again. */
661 obstack_ptr_grow (&unfilled_slots_obstack
, trial
);
666 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
667 the insn that sets CC0 for it and delete it too. */
670 delete_scheduled_jump (rtx insn
)
672 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
673 delete the insn that sets the condition code, but it is hard to find it.
674 Since this case is rare anyway, don't bother trying; there would likely
675 be other insns that became dead anyway, which we wouldn't know to
679 if (reg_mentioned_p (cc0_rtx
, insn
))
681 rtx note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
683 /* If a reg-note was found, it points to an insn to set CC0. This
684 insn is in the delay list of some other insn. So delete it from
685 the delay list it was in. */
688 if (! FIND_REG_INC_NOTE (XEXP (note
, 0), NULL_RTX
)
689 && sets_cc0_p (PATTERN (XEXP (note
, 0))) == 1)
690 delete_from_delay_slot (XEXP (note
, 0));
694 /* The insn setting CC0 is our previous insn, but it may be in
695 a delay slot. It will be the last insn in the delay slot, if
697 rtx trial
= previous_insn (insn
);
699 trial
= prev_nonnote_insn (trial
);
700 if (sets_cc0_p (PATTERN (trial
)) != 1
701 || FIND_REG_INC_NOTE (trial
, NULL_RTX
))
703 if (PREV_INSN (NEXT_INSN (trial
)) == trial
)
704 delete_related_insns (trial
);
706 delete_from_delay_slot (trial
);
711 delete_related_insns (insn
);
714 /* Counters for delay-slot filling. */
716 #define NUM_REORG_FUNCTIONS 2
717 #define MAX_DELAY_HISTOGRAM 3
718 #define MAX_REORG_PASSES 2
720 static int num_insns_needing_delays
[NUM_REORG_FUNCTIONS
][MAX_REORG_PASSES
];
722 static int num_filled_delays
[NUM_REORG_FUNCTIONS
][MAX_DELAY_HISTOGRAM
+1][MAX_REORG_PASSES
];
724 static int reorg_pass_number
;
727 note_delay_statistics (int slots_filled
, int index
)
729 num_insns_needing_delays
[index
][reorg_pass_number
]++;
730 if (slots_filled
> MAX_DELAY_HISTOGRAM
)
731 slots_filled
= MAX_DELAY_HISTOGRAM
;
732 num_filled_delays
[index
][slots_filled
][reorg_pass_number
]++;
735 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
737 /* Optimize the following cases:
739 1. When a conditional branch skips over only one instruction,
740 use an annulling branch and put that insn in the delay slot.
741 Use either a branch that annuls when the condition if true or
742 invert the test with a branch that annuls when the condition is
743 false. This saves insns, since otherwise we must copy an insn
746 (orig) (skip) (otherwise)
747 Bcc.n L1 Bcc',a L1 Bcc,a L1'
754 2. When a conditional branch skips over only one instruction,
755 and after that, it unconditionally branches somewhere else,
756 perform the similar optimization. This saves executing the
757 second branch in the case where the inverted condition is true.
766 This should be expanded to skip over N insns, where N is the number
767 of delay slots required. */
770 optimize_skip (rtx insn
)
772 rtx trial
= next_nonnote_insn (insn
);
773 rtx next_trial
= next_active_insn (trial
);
777 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
780 || !NONJUMP_INSN_P (trial
)
781 || GET_CODE (PATTERN (trial
)) == SEQUENCE
782 || recog_memoized (trial
) < 0
783 || (! eligible_for_annul_false (insn
, 0, trial
, flags
)
784 && ! eligible_for_annul_true (insn
, 0, trial
, flags
))
785 || can_throw_internal (trial
))
788 /* There are two cases where we are just executing one insn (we assume
789 here that a branch requires only one insn; this should be generalized
790 at some point): Where the branch goes around a single insn or where
791 we have one insn followed by a branch to the same label we branch to.
792 In both of these cases, inverting the jump and annulling the delay
793 slot give the same effect in fewer insns. */
794 if ((next_trial
== next_active_insn (JUMP_LABEL (insn
))
795 && ! (next_trial
== 0 && crtl
->epilogue_delay_list
!= 0))
797 && JUMP_P (next_trial
)
798 && JUMP_LABEL (insn
) == JUMP_LABEL (next_trial
)
799 && (simplejump_p (next_trial
)
800 || GET_CODE (PATTERN (next_trial
)) == RETURN
)))
802 if (eligible_for_annul_false (insn
, 0, trial
, flags
))
804 if (invert_jump (insn
, JUMP_LABEL (insn
), 1))
805 INSN_FROM_TARGET_P (trial
) = 1;
806 else if (! eligible_for_annul_true (insn
, 0, trial
, flags
))
810 delay_list
= add_to_delay_list (trial
, NULL_RTX
);
811 next_trial
= next_active_insn (trial
);
812 update_block (trial
, trial
);
813 delete_related_insns (trial
);
815 /* Also, if we are targeting an unconditional
816 branch, thread our jump to the target of that branch. Don't
817 change this into a RETURN here, because it may not accept what
818 we have in the delay slot. We'll fix this up later. */
819 if (next_trial
&& JUMP_P (next_trial
)
820 && (simplejump_p (next_trial
)
821 || GET_CODE (PATTERN (next_trial
)) == RETURN
))
823 rtx target_label
= JUMP_LABEL (next_trial
);
824 if (target_label
== 0)
825 target_label
= find_end_label ();
829 /* Recompute the flags based on TARGET_LABEL since threading
830 the jump to TARGET_LABEL may change the direction of the
831 jump (which may change the circumstances in which the
832 delay slot is nullified). */
833 flags
= get_jump_flags (insn
, target_label
);
834 if (eligible_for_annul_true (insn
, 0, trial
, flags
))
835 reorg_redirect_jump (insn
, target_label
);
839 INSN_ANNULLED_BRANCH_P (insn
) = 1;
846 /* Encode and return branch direction and prediction information for
847 INSN assuming it will jump to LABEL.
849 Non conditional branches return no direction information and
850 are predicted as very likely taken. */
853 get_jump_flags (rtx insn
, rtx label
)
857 /* get_jump_flags can be passed any insn with delay slots, these may
858 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
859 direction information, and only if they are conditional jumps.
861 If LABEL is zero, then there is no way to determine the branch
864 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
865 && INSN_UID (insn
) <= max_uid
867 && INSN_UID (label
) <= max_uid
)
869 = (uid_to_ruid
[INSN_UID (label
)] > uid_to_ruid
[INSN_UID (insn
)])
870 ? ATTR_FLAG_forward
: ATTR_FLAG_backward
;
871 /* No valid direction information. */
875 /* If insn is a conditional branch call mostly_true_jump to get
876 determine the branch prediction.
878 Non conditional branches are predicted as very likely taken. */
880 && (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
884 prediction
= mostly_true_jump (insn
, get_branch_condition (insn
, label
));
888 flags
|= (ATTR_FLAG_very_likely
| ATTR_FLAG_likely
);
891 flags
|= ATTR_FLAG_likely
;
894 flags
|= ATTR_FLAG_unlikely
;
897 flags
|= (ATTR_FLAG_very_unlikely
| ATTR_FLAG_unlikely
);
905 flags
|= (ATTR_FLAG_very_likely
| ATTR_FLAG_likely
);
910 /* Return 1 if INSN is a destination that will be branched to rarely (the
911 return point of a function); return 2 if DEST will be branched to very
912 rarely (a call to a function that doesn't return). Otherwise,
916 rare_destination (rtx insn
)
921 for (; insn
; insn
= next
)
923 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
924 insn
= XVECEXP (PATTERN (insn
), 0, 0);
926 next
= NEXT_INSN (insn
);
928 switch (GET_CODE (insn
))
933 /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We
934 don't scan past JUMP_INSNs, so any barrier we find here must
935 have been after a CALL_INSN and hence mean the call doesn't
939 if (GET_CODE (PATTERN (insn
)) == RETURN
)
941 else if (simplejump_p (insn
)
942 && jump_count
++ < 10)
943 next
= JUMP_LABEL (insn
);
952 /* If we got here it means we hit the end of the function. So this
953 is an unlikely destination. */
958 /* Return truth value of the statement that this branch
959 is mostly taken. If we think that the branch is extremely likely
960 to be taken, we return 2. If the branch is slightly more likely to be
961 taken, return 1. If the branch is slightly less likely to be taken,
962 return 0 and if the branch is highly unlikely to be taken, return -1.
964 CONDITION, if nonzero, is the condition that JUMP_INSN is testing. */
967 mostly_true_jump (rtx jump_insn
, rtx condition
)
969 rtx target_label
= JUMP_LABEL (jump_insn
);
971 int rare_dest
, rare_fallthrough
;
973 /* If branch probabilities are available, then use that number since it
974 always gives a correct answer. */
975 note
= find_reg_note (jump_insn
, REG_BR_PROB
, 0);
978 int prob
= INTVAL (XEXP (note
, 0));
980 if (prob
>= REG_BR_PROB_BASE
* 9 / 10)
982 else if (prob
>= REG_BR_PROB_BASE
/ 2)
984 else if (prob
>= REG_BR_PROB_BASE
/ 10)
990 /* Look at the relative rarities of the fallthrough and destination. If
991 they differ, we can predict the branch that way. */
992 rare_dest
= rare_destination (target_label
);
993 rare_fallthrough
= rare_destination (NEXT_INSN (jump_insn
));
995 switch (rare_fallthrough
- rare_dest
)
1009 /* If we couldn't figure out what this jump was, assume it won't be
1010 taken. This should be rare. */
1014 /* Predict backward branches usually take, forward branches usually not. If
1015 we don't know whether this is forward or backward, assume the branch
1016 will be taken, since most are. */
1017 return (target_label
== 0 || INSN_UID (jump_insn
) > max_uid
1018 || INSN_UID (target_label
) > max_uid
1019 || (uid_to_ruid
[INSN_UID (jump_insn
)]
1020 > uid_to_ruid
[INSN_UID (target_label
)]));
1023 /* Return the condition under which INSN will branch to TARGET. If TARGET
1024 is zero, return the condition under which INSN will return. If INSN is
1025 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1026 type of jump, or it doesn't go to TARGET, return 0. */
1029 get_branch_condition (rtx insn
, rtx target
)
1031 rtx pat
= PATTERN (insn
);
1034 if (condjump_in_parallel_p (insn
))
1035 pat
= XVECEXP (pat
, 0, 0);
1037 if (GET_CODE (pat
) == RETURN
)
1038 return target
== 0 ? const_true_rtx
: 0;
1040 else if (GET_CODE (pat
) != SET
|| SET_DEST (pat
) != pc_rtx
)
1043 src
= SET_SRC (pat
);
1044 if (GET_CODE (src
) == LABEL_REF
&& XEXP (src
, 0) == target
)
1045 return const_true_rtx
;
1047 else if (GET_CODE (src
) == IF_THEN_ELSE
1048 && ((target
== 0 && GET_CODE (XEXP (src
, 1)) == RETURN
)
1049 || (GET_CODE (XEXP (src
, 1)) == LABEL_REF
1050 && XEXP (XEXP (src
, 1), 0) == target
))
1051 && XEXP (src
, 2) == pc_rtx
)
1052 return XEXP (src
, 0);
1054 else if (GET_CODE (src
) == IF_THEN_ELSE
1055 && ((target
== 0 && GET_CODE (XEXP (src
, 2)) == RETURN
)
1056 || (GET_CODE (XEXP (src
, 2)) == LABEL_REF
1057 && XEXP (XEXP (src
, 2), 0) == target
))
1058 && XEXP (src
, 1) == pc_rtx
)
1061 rev
= reversed_comparison_code (XEXP (src
, 0), insn
);
1063 return gen_rtx_fmt_ee (rev
, GET_MODE (XEXP (src
, 0)),
1064 XEXP (XEXP (src
, 0), 0),
1065 XEXP (XEXP (src
, 0), 1));
1071 /* Return nonzero if CONDITION is more strict than the condition of
1072 INSN, i.e., if INSN will always branch if CONDITION is true. */
1075 condition_dominates_p (rtx condition
, rtx insn
)
1077 rtx other_condition
= get_branch_condition (insn
, JUMP_LABEL (insn
));
1078 enum rtx_code code
= GET_CODE (condition
);
1079 enum rtx_code other_code
;
1081 if (rtx_equal_p (condition
, other_condition
)
1082 || other_condition
== const_true_rtx
)
1085 else if (condition
== const_true_rtx
|| other_condition
== 0)
1088 other_code
= GET_CODE (other_condition
);
1089 if (GET_RTX_LENGTH (code
) != 2 || GET_RTX_LENGTH (other_code
) != 2
1090 || ! rtx_equal_p (XEXP (condition
, 0), XEXP (other_condition
, 0))
1091 || ! rtx_equal_p (XEXP (condition
, 1), XEXP (other_condition
, 1)))
1094 return comparison_dominates_p (code
, other_code
);
1097 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1098 any insns already in the delay slot of JUMP. */
1101 redirect_with_delay_slots_safe_p (rtx jump
, rtx newlabel
, rtx seq
)
1104 rtx pat
= PATTERN (seq
);
1106 /* Make sure all the delay slots of this jump would still
1107 be valid after threading the jump. If they are still
1108 valid, then return nonzero. */
1110 flags
= get_jump_flags (jump
, newlabel
);
1111 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
1113 #ifdef ANNUL_IFFALSE_SLOTS
1114 (INSN_ANNULLED_BRANCH_P (jump
)
1115 && INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1116 ? eligible_for_annul_false (jump
, i
- 1,
1117 XVECEXP (pat
, 0, i
), flags
) :
1119 #ifdef ANNUL_IFTRUE_SLOTS
1120 (INSN_ANNULLED_BRANCH_P (jump
)
1121 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1122 ? eligible_for_annul_true (jump
, i
- 1,
1123 XVECEXP (pat
, 0, i
), flags
) :
1125 eligible_for_delay (jump
, i
- 1, XVECEXP (pat
, 0, i
), flags
)))
1128 return (i
== XVECLEN (pat
, 0));
1131 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1132 any insns we wish to place in the delay slot of JUMP. */
1135 redirect_with_delay_list_safe_p (rtx jump
, rtx newlabel
, rtx delay_list
)
1140 /* Make sure all the insns in DELAY_LIST would still be
1141 valid after threading the jump. If they are still
1142 valid, then return nonzero. */
1144 flags
= get_jump_flags (jump
, newlabel
);
1145 for (li
= delay_list
, i
= 0; li
; li
= XEXP (li
, 1), i
++)
1147 #ifdef ANNUL_IFFALSE_SLOTS
1148 (INSN_ANNULLED_BRANCH_P (jump
)
1149 && INSN_FROM_TARGET_P (XEXP (li
, 0)))
1150 ? eligible_for_annul_false (jump
, i
, XEXP (li
, 0), flags
) :
1152 #ifdef ANNUL_IFTRUE_SLOTS
1153 (INSN_ANNULLED_BRANCH_P (jump
)
1154 && ! INSN_FROM_TARGET_P (XEXP (li
, 0)))
1155 ? eligible_for_annul_true (jump
, i
, XEXP (li
, 0), flags
) :
1157 eligible_for_delay (jump
, i
, XEXP (li
, 0), flags
)))
1160 return (li
== NULL
);
1163 /* DELAY_LIST is a list of insns that have already been placed into delay
1164 slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
1165 If not, return 0; otherwise return 1. */
1168 check_annul_list_true_false (int annul_true_p
, rtx delay_list
)
1174 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1176 rtx trial
= XEXP (temp
, 0);
1178 if ((annul_true_p
&& INSN_FROM_TARGET_P (trial
))
1179 || (!annul_true_p
&& !INSN_FROM_TARGET_P (trial
)))
1187 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1188 the condition tested by INSN is CONDITION and the resources shown in
1189 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1190 from SEQ's delay list, in addition to whatever insns it may execute
1191 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1192 needed while searching for delay slot insns. Return the concatenated
1193 delay list if possible, otherwise, return 0.
1195 SLOTS_TO_FILL is the total number of slots required by INSN, and
1196 PSLOTS_FILLED points to the number filled so far (also the number of
1197 insns in DELAY_LIST). It is updated with the number that have been
1198 filled from the SEQUENCE, if any.
1200 PANNUL_P points to a nonzero value if we already know that we need
1201 to annul INSN. If this routine determines that annulling is needed,
1202 it may set that value nonzero.
1204 PNEW_THREAD points to a location that is to receive the place at which
1205 execution should continue. */
1208 steal_delay_list_from_target (rtx insn
, rtx condition
, rtx seq
,
1209 rtx delay_list
, struct resources
*sets
,
1210 struct resources
*needed
,
1211 struct resources
*other_needed
,
1212 int slots_to_fill
, int *pslots_filled
,
1213 int *pannul_p
, rtx
*pnew_thread
)
1216 int slots_remaining
= slots_to_fill
- *pslots_filled
;
1217 int total_slots_filled
= *pslots_filled
;
1218 rtx new_delay_list
= 0;
1219 int must_annul
= *pannul_p
;
1222 struct resources cc_set
;
1224 /* We can't do anything if there are more delay slots in SEQ than we
1225 can handle, or if we don't know that it will be a taken branch.
1226 We know that it will be a taken branch if it is either an unconditional
1227 branch or a conditional branch with a stricter branch condition.
1229 Also, exit if the branch has more than one set, since then it is computing
1230 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1231 ??? It may be possible to move other sets into INSN in addition to
1232 moving the instructions in the delay slots.
1234 We can not steal the delay list if one of the instructions in the
1235 current delay_list modifies the condition codes and the jump in the
1236 sequence is a conditional jump. We can not do this because we can
1237 not change the direction of the jump because the condition codes
1238 will effect the direction of the jump in the sequence. */
1240 CLEAR_RESOURCE (&cc_set
);
1241 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1243 rtx trial
= XEXP (temp
, 0);
1245 mark_set_resources (trial
, &cc_set
, 0, MARK_SRC_DEST_CALL
);
1246 if (insn_references_resource_p (XVECEXP (seq
, 0, 0), &cc_set
, 0))
1250 if (XVECLEN (seq
, 0) - 1 > slots_remaining
1251 || ! condition_dominates_p (condition
, XVECEXP (seq
, 0, 0))
1252 || ! single_set (XVECEXP (seq
, 0, 0)))
1255 #ifdef MD_CAN_REDIRECT_BRANCH
1256 /* On some targets, branches with delay slots can have a limited
1257 displacement. Give the back end a chance to tell us we can't do
1259 if (! MD_CAN_REDIRECT_BRANCH (insn
, XVECEXP (seq
, 0, 0)))
1263 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
1265 rtx trial
= XVECEXP (seq
, 0, i
);
1268 if (insn_references_resource_p (trial
, sets
, 0)
1269 || insn_sets_resource_p (trial
, needed
, 0)
1270 || insn_sets_resource_p (trial
, sets
, 0)
1272 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1274 || find_reg_note (trial
, REG_CC_USER
, NULL_RTX
)
1276 /* If TRIAL is from the fallthrough code of an annulled branch insn
1277 in SEQ, we cannot use it. */
1278 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq
, 0, 0))
1279 && ! INSN_FROM_TARGET_P (trial
)))
1282 /* If this insn was already done (usually in a previous delay slot),
1283 pretend we put it in our delay slot. */
1284 if (redundant_insn (trial
, insn
, new_delay_list
))
1287 /* We will end up re-vectoring this branch, so compute flags
1288 based on jumping to the new label. */
1289 flags
= get_jump_flags (insn
, JUMP_LABEL (XVECEXP (seq
, 0, 0)));
1292 && ((condition
== const_true_rtx
1293 || (! insn_sets_resource_p (trial
, other_needed
, 0)
1294 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1295 ? eligible_for_delay (insn
, total_slots_filled
, trial
, flags
)
1296 : (must_annul
|| (delay_list
== NULL
&& new_delay_list
== NULL
))
1298 check_annul_list_true_false (0, delay_list
)
1299 && check_annul_list_true_false (0, new_delay_list
)
1300 && eligible_for_annul_false (insn
, total_slots_filled
,
1305 temp
= copy_rtx (trial
);
1306 INSN_FROM_TARGET_P (temp
) = 1;
1307 new_delay_list
= add_to_delay_list (temp
, new_delay_list
);
1308 total_slots_filled
++;
1310 if (--slots_remaining
== 0)
1317 /* Show the place to which we will be branching. */
1318 *pnew_thread
= next_active_insn (JUMP_LABEL (XVECEXP (seq
, 0, 0)));
1320 /* Add any new insns to the delay list and update the count of the
1321 number of slots filled. */
1322 *pslots_filled
= total_slots_filled
;
1326 if (delay_list
== 0)
1327 return new_delay_list
;
1329 for (temp
= new_delay_list
; temp
; temp
= XEXP (temp
, 1))
1330 delay_list
= add_to_delay_list (XEXP (temp
, 0), delay_list
);
1335 /* Similar to steal_delay_list_from_target except that SEQ is on the
1336 fallthrough path of INSN. Here we only do something if the delay insn
1337 of SEQ is an unconditional branch. In that case we steal its delay slot
1338 for INSN since unconditional branches are much easier to fill. */
1341 steal_delay_list_from_fallthrough (rtx insn
, rtx condition
, rtx seq
,
1342 rtx delay_list
, struct resources
*sets
,
1343 struct resources
*needed
,
1344 struct resources
*other_needed
,
1345 int slots_to_fill
, int *pslots_filled
,
1350 int must_annul
= *pannul_p
;
1353 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
1355 /* We can't do anything if SEQ's delay insn isn't an
1356 unconditional branch. */
1358 if (! simplejump_p (XVECEXP (seq
, 0, 0))
1359 && GET_CODE (PATTERN (XVECEXP (seq
, 0, 0))) != RETURN
)
1362 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
1364 rtx trial
= XVECEXP (seq
, 0, i
);
1366 /* If TRIAL sets CC0, stealing it will move it too far from the use
1368 if (insn_references_resource_p (trial
, sets
, 0)
1369 || insn_sets_resource_p (trial
, needed
, 0)
1370 || insn_sets_resource_p (trial
, sets
, 0)
1372 || sets_cc0_p (PATTERN (trial
))
1378 /* If this insn was already done, we don't need it. */
1379 if (redundant_insn (trial
, insn
, delay_list
))
1381 delete_from_delay_slot (trial
);
1386 && ((condition
== const_true_rtx
1387 || (! insn_sets_resource_p (trial
, other_needed
, 0)
1388 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1389 ? eligible_for_delay (insn
, *pslots_filled
, trial
, flags
)
1390 : (must_annul
|| delay_list
== NULL
) && (must_annul
= 1,
1391 check_annul_list_true_false (1, delay_list
)
1392 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
1396 delete_from_delay_slot (trial
);
1397 delay_list
= add_to_delay_list (trial
, delay_list
);
1399 if (++(*pslots_filled
) == slots_to_fill
)
1411 /* Try merging insns starting at THREAD which match exactly the insns in
1414 If all insns were matched and the insn was previously annulling, the
1415 annul bit will be cleared.
1417 For each insn that is merged, if the branch is or will be non-annulling,
1418 we delete the merged insn. */
1421 try_merge_delay_insns (rtx insn
, rtx thread
)
1423 rtx trial
, next_trial
;
1424 rtx delay_insn
= XVECEXP (PATTERN (insn
), 0, 0);
1425 int annul_p
= INSN_ANNULLED_BRANCH_P (delay_insn
);
1426 int slot_number
= 1;
1427 int num_slots
= XVECLEN (PATTERN (insn
), 0);
1428 rtx next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1429 struct resources set
, needed
;
1430 rtx merged_insns
= 0;
1434 flags
= get_jump_flags (delay_insn
, JUMP_LABEL (delay_insn
));
1436 CLEAR_RESOURCE (&needed
);
1437 CLEAR_RESOURCE (&set
);
1439 /* If this is not an annulling branch, take into account anything needed in
1440 INSN's delay slot. This prevents two increments from being incorrectly
1441 folded into one. If we are annulling, this would be the correct
1442 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1443 will essentially disable this optimization. This method is somewhat of
1444 a kludge, but I don't see a better way.) */
1446 for (i
= 1 ; i
< num_slots
; i
++)
1447 if (XVECEXP (PATTERN (insn
), 0, i
))
1448 mark_referenced_resources (XVECEXP (PATTERN (insn
), 0, i
), &needed
, 1);
1450 for (trial
= thread
; !stop_search_p (trial
, 1); trial
= next_trial
)
1452 rtx pat
= PATTERN (trial
);
1453 rtx oldtrial
= trial
;
1455 next_trial
= next_nonnote_insn (trial
);
1457 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1458 if (NONJUMP_INSN_P (trial
)
1459 && (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
))
1462 if (GET_CODE (next_to_match
) == GET_CODE (trial
)
1464 /* We can't share an insn that sets cc0. */
1465 && ! sets_cc0_p (pat
)
1467 && ! insn_references_resource_p (trial
, &set
, 1)
1468 && ! insn_sets_resource_p (trial
, &set
, 1)
1469 && ! insn_sets_resource_p (trial
, &needed
, 1)
1470 && (trial
= try_split (pat
, trial
, 0)) != 0
1471 /* Update next_trial, in case try_split succeeded. */
1472 && (next_trial
= next_nonnote_insn (trial
))
1473 /* Likewise THREAD. */
1474 && (thread
= oldtrial
== thread
? trial
: thread
)
1475 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (trial
))
1476 /* Have to test this condition if annul condition is different
1477 from (and less restrictive than) non-annulling one. */
1478 && eligible_for_delay (delay_insn
, slot_number
- 1, trial
, flags
))
1483 update_block (trial
, thread
);
1484 if (trial
== thread
)
1485 thread
= next_active_insn (thread
);
1487 delete_related_insns (trial
);
1488 INSN_FROM_TARGET_P (next_to_match
) = 0;
1491 merged_insns
= gen_rtx_INSN_LIST (VOIDmode
, trial
, merged_insns
);
1493 if (++slot_number
== num_slots
)
1496 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1499 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
1500 mark_referenced_resources (trial
, &needed
, 1);
1503 /* See if we stopped on a filled insn. If we did, try to see if its
1504 delay slots match. */
1505 if (slot_number
!= num_slots
1506 && trial
&& NONJUMP_INSN_P (trial
)
1507 && GET_CODE (PATTERN (trial
)) == SEQUENCE
1508 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial
), 0, 0)))
1510 rtx pat
= PATTERN (trial
);
1511 rtx filled_insn
= XVECEXP (pat
, 0, 0);
1513 /* Account for resources set/needed by the filled insn. */
1514 mark_set_resources (filled_insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1515 mark_referenced_resources (filled_insn
, &needed
, 1);
1517 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
1519 rtx dtrial
= XVECEXP (pat
, 0, i
);
1521 if (! insn_references_resource_p (dtrial
, &set
, 1)
1522 && ! insn_sets_resource_p (dtrial
, &set
, 1)
1523 && ! insn_sets_resource_p (dtrial
, &needed
, 1)
1525 && ! sets_cc0_p (PATTERN (dtrial
))
1527 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (dtrial
))
1528 && eligible_for_delay (delay_insn
, slot_number
- 1, dtrial
, flags
))
1534 update_block (dtrial
, thread
);
1535 new = delete_from_delay_slot (dtrial
);
1536 if (INSN_DELETED_P (thread
))
1538 INSN_FROM_TARGET_P (next_to_match
) = 0;
1541 merged_insns
= gen_rtx_INSN_LIST (SImode
, dtrial
,
1544 if (++slot_number
== num_slots
)
1547 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1551 /* Keep track of the set/referenced resources for the delay
1552 slots of any trial insns we encounter. */
1553 mark_set_resources (dtrial
, &set
, 0, MARK_SRC_DEST_CALL
);
1554 mark_referenced_resources (dtrial
, &needed
, 1);
1559 /* If all insns in the delay slot have been matched and we were previously
1560 annulling the branch, we need not any more. In that case delete all the
1561 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1562 the delay list so that we know that it isn't only being used at the
1564 if (slot_number
== num_slots
&& annul_p
)
1566 for (; merged_insns
; merged_insns
= XEXP (merged_insns
, 1))
1568 if (GET_MODE (merged_insns
) == SImode
)
1572 update_block (XEXP (merged_insns
, 0), thread
);
1573 new = delete_from_delay_slot (XEXP (merged_insns
, 0));
1574 if (INSN_DELETED_P (thread
))
1579 update_block (XEXP (merged_insns
, 0), thread
);
1580 delete_related_insns (XEXP (merged_insns
, 0));
1584 INSN_ANNULLED_BRANCH_P (delay_insn
) = 0;
1586 for (i
= 0; i
< XVECLEN (PATTERN (insn
), 0); i
++)
1587 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn
), 0, i
)) = 0;
1591 /* See if INSN is redundant with an insn in front of TARGET. Often this
1592 is called when INSN is a candidate for a delay slot of TARGET.
1593 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1594 of INSN. Often INSN will be redundant with an insn in a delay slot of
1595 some previous insn. This happens when we have a series of branches to the
1596 same label; in that case the first insn at the target might want to go
1597 into each of the delay slots.
1599 If we are not careful, this routine can take up a significant fraction
1600 of the total compilation time (4%), but only wins rarely. Hence we
1601 speed this routine up by making two passes. The first pass goes back
1602 until it hits a label and sees if it finds an insn with an identical
1603 pattern. Only in this (relatively rare) event does it check for
1606 We do not split insns we encounter. This could cause us not to find a
1607 redundant insn, but the cost of splitting seems greater than the possible
1608 gain in rare cases. */
1611 redundant_insn (rtx insn
, rtx target
, rtx delay_list
)
1613 rtx target_main
= target
;
1614 rtx ipat
= PATTERN (insn
);
1616 struct resources needed
, set
;
1618 unsigned insns_to_search
;
1620 /* If INSN has any REG_UNUSED notes, it can't match anything since we
1621 are allowed to not actually assign to such a register. */
1622 if (find_reg_note (insn
, REG_UNUSED
, NULL_RTX
) != 0)
1625 /* Scan backwards looking for a match. */
1626 for (trial
= PREV_INSN (target
),
1627 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1628 trial
&& insns_to_search
> 0;
1629 trial
= PREV_INSN (trial
), --insns_to_search
)
1631 if (LABEL_P (trial
))
1634 if (! INSN_P (trial
))
1637 pat
= PATTERN (trial
);
1638 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1641 if (GET_CODE (pat
) == SEQUENCE
)
1643 /* Stop for a CALL and its delay slots because it is difficult to
1644 track its resource needs correctly. */
1645 if (CALL_P (XVECEXP (pat
, 0, 0)))
1648 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1649 slots because it is difficult to track its resource needs
1652 #ifdef INSN_SETS_ARE_DELAYED
1653 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1657 #ifdef INSN_REFERENCES_ARE_DELAYED
1658 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1662 /* See if any of the insns in the delay slot match, updating
1663 resource requirements as we go. */
1664 for (i
= XVECLEN (pat
, 0) - 1; i
> 0; i
--)
1665 if (GET_CODE (XVECEXP (pat
, 0, i
)) == GET_CODE (insn
)
1666 && rtx_equal_p (PATTERN (XVECEXP (pat
, 0, i
)), ipat
)
1667 && ! find_reg_note (XVECEXP (pat
, 0, i
), REG_UNUSED
, NULL_RTX
))
1670 /* If found a match, exit this loop early. */
1675 else if (GET_CODE (trial
) == GET_CODE (insn
) && rtx_equal_p (pat
, ipat
)
1676 && ! find_reg_note (trial
, REG_UNUSED
, NULL_RTX
))
1680 /* If we didn't find an insn that matches, return 0. */
1684 /* See what resources this insn sets and needs. If they overlap, or
1685 if this insn references CC0, it can't be redundant. */
1687 CLEAR_RESOURCE (&needed
);
1688 CLEAR_RESOURCE (&set
);
1689 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1690 mark_referenced_resources (insn
, &needed
, 1);
1692 /* If TARGET is a SEQUENCE, get the main insn. */
1693 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1694 target_main
= XVECEXP (PATTERN (target
), 0, 0);
1696 if (resource_conflicts_p (&needed
, &set
)
1698 || reg_mentioned_p (cc0_rtx
, ipat
)
1700 /* The insn requiring the delay may not set anything needed or set by
1702 || insn_sets_resource_p (target_main
, &needed
, 1)
1703 || insn_sets_resource_p (target_main
, &set
, 1))
1706 /* Insns we pass may not set either NEEDED or SET, so merge them for
1708 needed
.memory
|= set
.memory
;
1709 needed
.unch_memory
|= set
.unch_memory
;
1710 IOR_HARD_REG_SET (needed
.regs
, set
.regs
);
1712 /* This insn isn't redundant if it conflicts with an insn that either is
1713 or will be in a delay slot of TARGET. */
1717 if (insn_sets_resource_p (XEXP (delay_list
, 0), &needed
, 1))
1719 delay_list
= XEXP (delay_list
, 1);
1722 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1723 for (i
= 1; i
< XVECLEN (PATTERN (target
), 0); i
++)
1724 if (insn_sets_resource_p (XVECEXP (PATTERN (target
), 0, i
), &needed
, 1))
1727 /* Scan backwards until we reach a label or an insn that uses something
1728 INSN sets or sets something insn uses or sets. */
1730 for (trial
= PREV_INSN (target
),
1731 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1732 trial
&& !LABEL_P (trial
) && insns_to_search
> 0;
1733 trial
= PREV_INSN (trial
), --insns_to_search
)
1735 if (!INSN_P (trial
))
1738 pat
= PATTERN (trial
);
1739 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1742 if (GET_CODE (pat
) == SEQUENCE
)
1744 /* If this is a CALL_INSN and its delay slots, it is hard to track
1745 the resource needs properly, so give up. */
1746 if (CALL_P (XVECEXP (pat
, 0, 0)))
1749 /* If this is an INSN or JUMP_INSN with delayed effects, it
1750 is hard to track the resource needs properly, so give up. */
1752 #ifdef INSN_SETS_ARE_DELAYED
1753 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1757 #ifdef INSN_REFERENCES_ARE_DELAYED
1758 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1762 /* See if any of the insns in the delay slot match, updating
1763 resource requirements as we go. */
1764 for (i
= XVECLEN (pat
, 0) - 1; i
> 0; i
--)
1766 rtx candidate
= XVECEXP (pat
, 0, i
);
1768 /* If an insn will be annulled if the branch is false, it isn't
1769 considered as a possible duplicate insn. */
1770 if (rtx_equal_p (PATTERN (candidate
), ipat
)
1771 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat
, 0, 0))
1772 && INSN_FROM_TARGET_P (candidate
)))
1774 /* Show that this insn will be used in the sequel. */
1775 INSN_FROM_TARGET_P (candidate
) = 0;
1779 /* Unless this is an annulled insn from the target of a branch,
1780 we must stop if it sets anything needed or set by INSN. */
1781 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat
, 0, 0))
1782 || ! INSN_FROM_TARGET_P (candidate
))
1783 && insn_sets_resource_p (candidate
, &needed
, 1))
1787 /* If the insn requiring the delay slot conflicts with INSN, we
1789 if (insn_sets_resource_p (XVECEXP (pat
, 0, 0), &needed
, 1))
1794 /* See if TRIAL is the same as INSN. */
1795 pat
= PATTERN (trial
);
1796 if (rtx_equal_p (pat
, ipat
))
1799 /* Can't go any further if TRIAL conflicts with INSN. */
1800 if (insn_sets_resource_p (trial
, &needed
, 1))
1808 /* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero,
1809 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1810 is nonzero, we are allowed to fall into this thread; otherwise, we are
1813 If LABEL is used more than one or we pass a label other than LABEL before
1814 finding an active insn, we do not own this thread. */
1817 own_thread_p (rtx thread
, rtx label
, int allow_fallthrough
)
1822 /* We don't own the function end. */
1826 /* Get the first active insn, or THREAD, if it is an active insn. */
1827 active_insn
= next_active_insn (PREV_INSN (thread
));
1829 for (insn
= thread
; insn
!= active_insn
; insn
= NEXT_INSN (insn
))
1831 && (insn
!= label
|| LABEL_NUSES (insn
) != 1))
1834 if (allow_fallthrough
)
1837 /* Ensure that we reach a BARRIER before any insn or label. */
1838 for (insn
= prev_nonnote_insn (thread
);
1839 insn
== 0 || !BARRIER_P (insn
);
1840 insn
= prev_nonnote_insn (insn
))
1843 || (NONJUMP_INSN_P (insn
)
1844 && GET_CODE (PATTERN (insn
)) != USE
1845 && GET_CODE (PATTERN (insn
)) != CLOBBER
))
1851 /* Called when INSN is being moved from a location near the target of a jump.
1852 We leave a marker of the form (use (INSN)) immediately in front
1853 of WHERE for mark_target_live_regs. These markers will be deleted when
1856 We used to try to update the live status of registers if WHERE is at
1857 the start of a basic block, but that can't work since we may remove a
1858 BARRIER in relax_delay_slots. */
1861 update_block (rtx insn
, rtx where
)
1863 /* Ignore if this was in a delay slot and it came from the target of
1865 if (INSN_FROM_TARGET_P (insn
))
1868 emit_insn_before (gen_rtx_USE (VOIDmode
, insn
), where
);
1870 /* INSN might be making a value live in a block where it didn't use to
1871 be. So recompute liveness information for this block. */
1873 incr_ticks_for_insn (insn
);
1876 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
1877 the basic block containing the jump. */
1880 reorg_redirect_jump (rtx jump
, rtx nlabel
)
1882 incr_ticks_for_insn (jump
);
1883 return redirect_jump (jump
, nlabel
, 1);
1886 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
1887 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
1888 that reference values used in INSN. If we find one, then we move the
1889 REG_DEAD note to INSN.
1891 This is needed to handle the case where a later insn (after INSN) has a
1892 REG_DEAD note for a register used by INSN, and this later insn subsequently
1893 gets moved before a CODE_LABEL because it is a redundant insn. In this
1894 case, mark_target_live_regs may be confused into thinking the register
1895 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
1898 update_reg_dead_notes (rtx insn
, rtx delayed_insn
)
1902 for (p
= next_nonnote_insn (insn
); p
!= delayed_insn
;
1903 p
= next_nonnote_insn (p
))
1904 for (link
= REG_NOTES (p
); link
; link
= next
)
1906 next
= XEXP (link
, 1);
1908 if (REG_NOTE_KIND (link
) != REG_DEAD
1909 || !REG_P (XEXP (link
, 0)))
1912 if (reg_referenced_p (XEXP (link
, 0), PATTERN (insn
)))
1914 /* Move the REG_DEAD note from P to INSN. */
1915 remove_note (p
, link
);
1916 XEXP (link
, 1) = REG_NOTES (insn
);
1917 REG_NOTES (insn
) = link
;
1922 /* Called when an insn redundant with start_insn is deleted. If there
1923 is a REG_DEAD note for the target of start_insn between start_insn
1924 and stop_insn, then the REG_DEAD note needs to be deleted since the
1925 value no longer dies there.
1927 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
1928 confused into thinking the register is dead. */
1931 fix_reg_dead_note (rtx start_insn
, rtx stop_insn
)
1935 for (p
= next_nonnote_insn (start_insn
); p
!= stop_insn
;
1936 p
= next_nonnote_insn (p
))
1937 for (link
= REG_NOTES (p
); link
; link
= next
)
1939 next
= XEXP (link
, 1);
1941 if (REG_NOTE_KIND (link
) != REG_DEAD
1942 || !REG_P (XEXP (link
, 0)))
1945 if (reg_set_p (XEXP (link
, 0), PATTERN (start_insn
)))
1947 remove_note (p
, link
);
1953 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
1955 This handles the case of udivmodXi4 instructions which optimize their
1956 output depending on whether any REG_UNUSED notes are present.
1957 we must make sure that INSN calculates as many results as REDUNDANT_INSN
1961 update_reg_unused_notes (rtx insn
, rtx redundant_insn
)
1965 for (link
= REG_NOTES (insn
); link
; link
= next
)
1967 next
= XEXP (link
, 1);
1969 if (REG_NOTE_KIND (link
) != REG_UNUSED
1970 || !REG_P (XEXP (link
, 0)))
1973 if (! find_regno_note (redundant_insn
, REG_UNUSED
,
1974 REGNO (XEXP (link
, 0))))
1975 remove_note (insn
, link
);
1979 /* Return the label before INSN, or put a new label there. */
1982 get_label_before (rtx insn
)
1986 /* Find an existing label at this point
1987 or make a new one if there is none. */
1988 label
= prev_nonnote_insn (insn
);
1990 if (label
== 0 || !LABEL_P (label
))
1992 rtx prev
= PREV_INSN (insn
);
1994 label
= gen_label_rtx ();
1995 emit_label_after (label
, prev
);
1996 LABEL_NUSES (label
) = 0;
2001 /* Scan a function looking for insns that need a delay slot and find insns to
2002 put into the delay slot.
2004 NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such
2005 as calls). We do these first since we don't want jump insns (that are
2006 easier to fill) to get the only insns that could be used for non-jump insns.
2007 When it is zero, only try to fill JUMP_INSNs.
2009 When slots are filled in this manner, the insns (including the
2010 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2011 it is possible to tell whether a delay slot has really been filled
2012 or not. `final' knows how to deal with this, by communicating
2013 through FINAL_SEQUENCE. */
2016 fill_simple_delay_slots (int non_jumps_p
)
2018 rtx insn
, pat
, trial
, next_trial
;
2020 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
2021 struct resources needed
, set
;
2022 int slots_to_fill
, slots_filled
;
2025 for (i
= 0; i
< num_unfilled_slots
; i
++)
2028 /* Get the next insn to fill. If it has already had any slots assigned,
2029 we can't do anything with it. Maybe we'll improve this later. */
2031 insn
= unfilled_slots_base
[i
];
2033 || INSN_DELETED_P (insn
)
2034 || (NONJUMP_INSN_P (insn
)
2035 && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
2036 || (JUMP_P (insn
) && non_jumps_p
)
2037 || (!JUMP_P (insn
) && ! non_jumps_p
))
2040 /* It may have been that this insn used to need delay slots, but
2041 now doesn't; ignore in that case. This can happen, for example,
2042 on the HP PA RISC, where the number of delay slots depends on
2043 what insns are nearby. */
2044 slots_to_fill
= num_delay_slots (insn
);
2046 /* Some machine description have defined instructions to have
2047 delay slots only in certain circumstances which may depend on
2048 nearby insns (which change due to reorg's actions).
2050 For example, the PA port normally has delay slots for unconditional
2053 However, the PA port claims such jumps do not have a delay slot
2054 if they are immediate successors of certain CALL_INSNs. This
2055 allows the port to favor filling the delay slot of the call with
2056 the unconditional jump. */
2057 if (slots_to_fill
== 0)
2060 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2061 says how many. After initialization, first try optimizing
2064 nop add %o7,.-L1,%o7
2068 If this case applies, the delay slot of the call is filled with
2069 the unconditional jump. This is done first to avoid having the
2070 delay slot of the call filled in the backward scan. Also, since
2071 the unconditional jump is likely to also have a delay slot, that
2072 insn must exist when it is subsequently scanned.
2074 This is tried on each insn with delay slots as some machines
2075 have insns which perform calls, but are not represented as
2082 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2084 flags
= get_jump_flags (insn
, NULL_RTX
);
2086 if ((trial
= next_active_insn (insn
))
2088 && simplejump_p (trial
)
2089 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2090 && no_labels_between_p (insn
, trial
)
2091 && ! can_throw_internal (trial
))
2095 delay_list
= add_to_delay_list (trial
, delay_list
);
2097 /* TRIAL may have had its delay slot filled, then unfilled. When
2098 the delay slot is unfilled, TRIAL is placed back on the unfilled
2099 slots obstack. Unfortunately, it is placed on the end of the
2100 obstack, not in its original location. Therefore, we must search
2101 from entry i + 1 to the end of the unfilled slots obstack to
2102 try and find TRIAL. */
2103 tmp
= &unfilled_slots_base
[i
+ 1];
2104 while (*tmp
!= trial
&& tmp
!= unfilled_slots_next
)
2107 /* Remove the unconditional jump from consideration for delay slot
2108 filling and unthread it. */
2112 rtx next
= NEXT_INSN (trial
);
2113 rtx prev
= PREV_INSN (trial
);
2115 NEXT_INSN (prev
) = next
;
2117 PREV_INSN (next
) = prev
;
2121 /* Now, scan backwards from the insn to search for a potential
2122 delay-slot candidate. Stop searching when a label or jump is hit.
2124 For each candidate, if it is to go into the delay slot (moved
2125 forward in execution sequence), it must not need or set any resources
2126 that were set by later insns and must not set any resources that
2127 are needed for those insns.
2129 The delay slot insn itself sets resources unless it is a call
2130 (in which case the called routine, not the insn itself, is doing
2133 if (slots_filled
< slots_to_fill
)
2135 CLEAR_RESOURCE (&needed
);
2136 CLEAR_RESOURCE (&set
);
2137 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST
);
2138 mark_referenced_resources (insn
, &needed
, 0);
2140 for (trial
= prev_nonnote_insn (insn
); ! stop_search_p (trial
, 1);
2143 next_trial
= prev_nonnote_insn (trial
);
2145 /* This must be an INSN or CALL_INSN. */
2146 pat
= PATTERN (trial
);
2148 /* USE and CLOBBER at this level was just for flow; ignore it. */
2149 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2152 /* Check for resource conflict first, to avoid unnecessary
2154 if (! insn_references_resource_p (trial
, &set
, 1)
2155 && ! insn_sets_resource_p (trial
, &set
, 1)
2156 && ! insn_sets_resource_p (trial
, &needed
, 1)
2158 /* Can't separate set of cc0 from its use. */
2159 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2161 && ! can_throw_internal (trial
))
2163 trial
= try_split (pat
, trial
, 1);
2164 next_trial
= prev_nonnote_insn (trial
);
2165 if (eligible_for_delay (insn
, slots_filled
, trial
, flags
))
2167 /* In this case, we are searching backward, so if we
2168 find insns to put on the delay list, we want
2169 to put them at the head, rather than the
2170 tail, of the list. */
2172 update_reg_dead_notes (trial
, insn
);
2173 delay_list
= gen_rtx_INSN_LIST (VOIDmode
,
2175 update_block (trial
, trial
);
2176 delete_related_insns (trial
);
2177 if (slots_to_fill
== ++slots_filled
)
2183 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2184 mark_referenced_resources (trial
, &needed
, 1);
2188 /* If all needed slots haven't been filled, we come here. */
2190 /* Try to optimize case of jumping around a single insn. */
2191 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2192 if (slots_filled
!= slots_to_fill
2195 && (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
2197 delay_list
= optimize_skip (insn
);
2203 /* Try to get insns from beyond the insn needing the delay slot.
2204 These insns can neither set or reference resources set in insns being
2205 skipped, cannot set resources in the insn being skipped, and, if this
2206 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2207 call might not return).
2209 There used to be code which continued past the target label if
2210 we saw all uses of the target label. This code did not work,
2211 because it failed to account for some instructions which were
2212 both annulled and marked as from the target. This can happen as a
2213 result of optimize_skip. Since this code was redundant with
2214 fill_eager_delay_slots anyways, it was just deleted. */
2216 if (slots_filled
!= slots_to_fill
2217 /* If this instruction could throw an exception which is
2218 caught in the same function, then it's not safe to fill
2219 the delay slot with an instruction from beyond this
2220 point. For example, consider:
2231 Even though `i' is a local variable, we must be sure not
2232 to put `i = 3' in the delay slot if `f' might throw an
2235 Presumably, we should also check to see if we could get
2236 back to this function via `setjmp'. */
2237 && ! can_throw_internal (insn
)
2239 || ((condjump_p (insn
) || condjump_in_parallel_p (insn
))
2240 && ! simplejump_p (insn
)
2241 && JUMP_LABEL (insn
) != 0)))
2243 /* Invariant: If insn is a JUMP_INSN, the insn's jump
2244 label. Otherwise, zero. */
2246 int maybe_never
= 0;
2247 rtx pat
, trial_delay
;
2249 CLEAR_RESOURCE (&needed
);
2250 CLEAR_RESOURCE (&set
);
2254 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2255 mark_referenced_resources (insn
, &needed
, 1);
2260 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2261 mark_referenced_resources (insn
, &needed
, 1);
2263 target
= JUMP_LABEL (insn
);
2267 for (trial
= next_nonnote_insn (insn
); trial
; trial
= next_trial
)
2269 next_trial
= next_nonnote_insn (trial
);
2272 || BARRIER_P (trial
))
2275 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
2276 pat
= PATTERN (trial
);
2278 /* Stand-alone USE and CLOBBER are just for flow. */
2279 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2282 /* If this already has filled delay slots, get the insn needing
2284 if (GET_CODE (pat
) == SEQUENCE
)
2285 trial_delay
= XVECEXP (pat
, 0, 0);
2287 trial_delay
= trial
;
2289 /* Stop our search when seeing an unconditional jump. */
2290 if (JUMP_P (trial_delay
))
2293 /* See if we have a resource problem before we try to
2295 if (GET_CODE (pat
) != SEQUENCE
2296 && ! insn_references_resource_p (trial
, &set
, 1)
2297 && ! insn_sets_resource_p (trial
, &set
, 1)
2298 && ! insn_sets_resource_p (trial
, &needed
, 1)
2300 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2302 && ! (maybe_never
&& may_trap_or_fault_p (pat
))
2303 && (trial
= try_split (pat
, trial
, 0))
2304 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2305 && ! can_throw_internal(trial
))
2307 next_trial
= next_nonnote_insn (trial
);
2308 delay_list
= add_to_delay_list (trial
, delay_list
);
2311 if (reg_mentioned_p (cc0_rtx
, pat
))
2312 link_cc0_insns (trial
);
2315 delete_related_insns (trial
);
2316 if (slots_to_fill
== ++slots_filled
)
2321 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2322 mark_referenced_resources (trial
, &needed
, 1);
2324 /* Ensure we don't put insns between the setting of cc and the
2325 comparison by moving a setting of cc into an earlier delay
2326 slot since these insns could clobber the condition code. */
2329 /* If this is a call or jump, we might not get here. */
2330 if (CALL_P (trial_delay
)
2331 || JUMP_P (trial_delay
))
2335 /* If there are slots left to fill and our search was stopped by an
2336 unconditional branch, try the insn at the branch target. We can
2337 redirect the branch if it works.
2339 Don't do this if the insn at the branch target is a branch. */
2340 if (slots_to_fill
!= slots_filled
2343 && simplejump_p (trial
)
2344 && (target
== 0 || JUMP_LABEL (trial
) == target
)
2345 && (next_trial
= next_active_insn (JUMP_LABEL (trial
))) != 0
2346 && ! (NONJUMP_INSN_P (next_trial
)
2347 && GET_CODE (PATTERN (next_trial
)) == SEQUENCE
)
2348 && !JUMP_P (next_trial
)
2349 && ! insn_references_resource_p (next_trial
, &set
, 1)
2350 && ! insn_sets_resource_p (next_trial
, &set
, 1)
2351 && ! insn_sets_resource_p (next_trial
, &needed
, 1)
2353 && ! reg_mentioned_p (cc0_rtx
, PATTERN (next_trial
))
2355 && ! (maybe_never
&& may_trap_or_fault_p (PATTERN (next_trial
)))
2356 && (next_trial
= try_split (PATTERN (next_trial
), next_trial
, 0))
2357 && eligible_for_delay (insn
, slots_filled
, next_trial
, flags
)
2358 && ! can_throw_internal (trial
))
2360 /* See comment in relax_delay_slots about necessity of using
2361 next_real_insn here. */
2362 rtx new_label
= next_real_insn (next_trial
);
2365 new_label
= get_label_before (new_label
);
2367 new_label
= find_end_label ();
2372 = add_to_delay_list (copy_rtx (next_trial
), delay_list
);
2374 reorg_redirect_jump (trial
, new_label
);
2376 /* If we merged because we both jumped to the same place,
2377 redirect the original insn also. */
2379 reorg_redirect_jump (insn
, new_label
);
2384 /* If this is an unconditional jump, then try to get insns from the
2385 target of the jump. */
2387 && simplejump_p (insn
)
2388 && slots_filled
!= slots_to_fill
)
2390 = fill_slots_from_thread (insn
, const_true_rtx
,
2391 next_active_insn (JUMP_LABEL (insn
)),
2393 own_thread_p (JUMP_LABEL (insn
),
2394 JUMP_LABEL (insn
), 0),
2395 slots_to_fill
, &slots_filled
,
2399 unfilled_slots_base
[i
]
2400 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
2402 if (slots_to_fill
== slots_filled
)
2403 unfilled_slots_base
[i
] = 0;
2405 note_delay_statistics (slots_filled
, 0);
2408 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2409 /* See if the epilogue needs any delay slots. Try to fill them if so.
2410 The only thing we can do is scan backwards from the end of the
2411 function. If we did this in a previous pass, it is incorrect to do it
2413 if (crtl
->epilogue_delay_list
)
2416 slots_to_fill
= DELAY_SLOTS_FOR_EPILOGUE
;
2417 if (slots_to_fill
== 0)
2421 CLEAR_RESOURCE (&set
);
2423 /* The frame pointer and stack pointer are needed at the beginning of
2424 the epilogue, so instructions setting them can not be put in the
2425 epilogue delay slot. However, everything else needed at function
2426 end is safe, so we don't want to use end_of_function_needs here. */
2427 CLEAR_RESOURCE (&needed
);
2428 if (frame_pointer_needed
)
2430 SET_HARD_REG_BIT (needed
.regs
, FRAME_POINTER_REGNUM
);
2431 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2432 SET_HARD_REG_BIT (needed
.regs
, HARD_FRAME_POINTER_REGNUM
);
2434 if (! EXIT_IGNORE_STACK
2435 || current_function_sp_is_unchanging
)
2436 SET_HARD_REG_BIT (needed
.regs
, STACK_POINTER_REGNUM
);
2439 SET_HARD_REG_BIT (needed
.regs
, STACK_POINTER_REGNUM
);
2441 #ifdef EPILOGUE_USES
2442 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2444 if (EPILOGUE_USES (i
))
2445 SET_HARD_REG_BIT (needed
.regs
, i
);
2449 for (trial
= get_last_insn (); ! stop_search_p (trial
, 1);
2450 trial
= PREV_INSN (trial
))
2454 pat
= PATTERN (trial
);
2455 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2458 if (! insn_references_resource_p (trial
, &set
, 1)
2459 && ! insn_sets_resource_p (trial
, &needed
, 1)
2460 && ! insn_sets_resource_p (trial
, &set
, 1)
2462 /* Don't want to mess with cc0 here. */
2463 && ! reg_mentioned_p (cc0_rtx
, pat
)
2465 && ! can_throw_internal (trial
))
2467 trial
= try_split (pat
, trial
, 1);
2468 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial
, slots_filled
))
2470 /* Here as well we are searching backward, so put the
2471 insns we find on the head of the list. */
2473 crtl
->epilogue_delay_list
2474 = gen_rtx_INSN_LIST (VOIDmode
, trial
,
2475 crtl
->epilogue_delay_list
);
2476 mark_end_of_function_resources (trial
, 1);
2477 update_block (trial
, trial
);
2478 delete_related_insns (trial
);
2480 /* Clear deleted bit so final.c will output the insn. */
2481 INSN_DELETED_P (trial
) = 0;
2483 if (slots_to_fill
== ++slots_filled
)
2489 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2490 mark_referenced_resources (trial
, &needed
, 1);
2493 note_delay_statistics (slots_filled
, 0);
2497 /* Follow any unconditional jump at LABEL;
2498 return the ultimate label reached by any such chain of jumps.
2499 Return null if the chain ultimately leads to a return instruction.
2500 If LABEL is not followed by a jump, return LABEL.
2501 If the chain loops or we can't find end, return LABEL,
2502 since that tells caller to avoid changing the insn. */
2505 follow_jumps (rtx label
)
2514 && (insn
= next_active_insn (value
)) != 0
2516 && ((JUMP_LABEL (insn
) != 0 && any_uncondjump_p (insn
)
2517 && onlyjump_p (insn
))
2518 || GET_CODE (PATTERN (insn
)) == RETURN
)
2519 && (next
= NEXT_INSN (insn
))
2520 && BARRIER_P (next
));
2525 /* If we have found a cycle, make the insn jump to itself. */
2526 if (JUMP_LABEL (insn
) == label
)
2529 tem
= next_active_insn (JUMP_LABEL (insn
));
2530 if (tem
&& (GET_CODE (PATTERN (tem
)) == ADDR_VEC
2531 || GET_CODE (PATTERN (tem
)) == ADDR_DIFF_VEC
))
2534 value
= JUMP_LABEL (insn
);
2541 /* Try to find insns to place in delay slots.
2543 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2544 or is an unconditional branch if CONDITION is const_true_rtx.
2545 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2547 THREAD is a flow-of-control, either the insns to be executed if the
2548 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2550 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2551 to see if any potential delay slot insns set things needed there.
2553 LIKELY is nonzero if it is extremely likely that the branch will be
2554 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2555 end of a loop back up to the top.
2557 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2558 thread. I.e., it is the fallthrough code of our jump or the target of the
2559 jump when we are the only jump going there.
2561 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2562 case, we can only take insns from the head of the thread for our delay
2563 slot. We then adjust the jump to point after the insns we have taken. */
2566 fill_slots_from_thread (rtx insn
, rtx condition
, rtx thread
,
2567 rtx opposite_thread
, int likely
, int thread_if_true
,
2568 int own_thread
, int slots_to_fill
,
2569 int *pslots_filled
, rtx delay_list
)
2572 struct resources opposite_needed
, set
, needed
;
2578 /* Validate our arguments. */
2579 gcc_assert(condition
!= const_true_rtx
|| thread_if_true
);
2580 gcc_assert(own_thread
|| thread_if_true
);
2582 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2584 /* If our thread is the end of subroutine, we can't get any delay
2589 /* If this is an unconditional branch, nothing is needed at the
2590 opposite thread. Otherwise, compute what is needed there. */
2591 if (condition
== const_true_rtx
)
2592 CLEAR_RESOURCE (&opposite_needed
);
2594 mark_target_live_regs (get_insns (), opposite_thread
, &opposite_needed
);
2596 /* If the insn at THREAD can be split, do it here to avoid having to
2597 update THREAD and NEW_THREAD if it is done in the loop below. Also
2598 initialize NEW_THREAD. */
2600 new_thread
= thread
= try_split (PATTERN (thread
), thread
, 0);
2602 /* Scan insns at THREAD. We are looking for an insn that can be removed
2603 from THREAD (it neither sets nor references resources that were set
2604 ahead of it and it doesn't set anything needs by the insns ahead of
2605 it) and that either can be placed in an annulling insn or aren't
2606 needed at OPPOSITE_THREAD. */
2608 CLEAR_RESOURCE (&needed
);
2609 CLEAR_RESOURCE (&set
);
2611 /* If we do not own this thread, we must stop as soon as we find
2612 something that we can't put in a delay slot, since all we can do
2613 is branch into THREAD at a later point. Therefore, labels stop
2614 the search if this is not the `true' thread. */
2616 for (trial
= thread
;
2617 ! stop_search_p (trial
, ! thread_if_true
) && (! lose
|| own_thread
);
2618 trial
= next_nonnote_insn (trial
))
2622 /* If we have passed a label, we no longer own this thread. */
2623 if (LABEL_P (trial
))
2629 pat
= PATTERN (trial
);
2630 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2633 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2634 don't separate or copy insns that set and use CC0. */
2635 if (! insn_references_resource_p (trial
, &set
, 1)
2636 && ! insn_sets_resource_p (trial
, &set
, 1)
2637 && ! insn_sets_resource_p (trial
, &needed
, 1)
2639 && ! (reg_mentioned_p (cc0_rtx
, pat
)
2640 && (! own_thread
|| ! sets_cc0_p (pat
)))
2642 && ! can_throw_internal (trial
))
2646 /* If TRIAL is redundant with some insn before INSN, we don't
2647 actually need to add it to the delay list; we can merely pretend
2649 if ((prior_insn
= redundant_insn (trial
, insn
, delay_list
)))
2651 fix_reg_dead_note (prior_insn
, insn
);
2654 update_block (trial
, thread
);
2655 if (trial
== thread
)
2657 thread
= next_active_insn (thread
);
2658 if (new_thread
== trial
)
2659 new_thread
= thread
;
2662 delete_related_insns (trial
);
2666 update_reg_unused_notes (prior_insn
, trial
);
2667 new_thread
= next_active_insn (trial
);
2673 /* There are two ways we can win: If TRIAL doesn't set anything
2674 needed at the opposite thread and can't trap, or if it can
2675 go into an annulled delay slot. */
2677 && (condition
== const_true_rtx
2678 || (! insn_sets_resource_p (trial
, &opposite_needed
, 1)
2679 && ! may_trap_or_fault_p (pat
))))
2682 trial
= try_split (pat
, trial
, 0);
2683 if (new_thread
== old_trial
)
2685 if (thread
== old_trial
)
2687 pat
= PATTERN (trial
);
2688 if (eligible_for_delay (insn
, *pslots_filled
, trial
, flags
))
2692 #ifdef ANNUL_IFTRUE_SLOTS
2695 #ifdef ANNUL_IFFALSE_SLOTS
2701 trial
= try_split (pat
, trial
, 0);
2702 if (new_thread
== old_trial
)
2704 if (thread
== old_trial
)
2706 pat
= PATTERN (trial
);
2707 if ((must_annul
|| delay_list
== NULL
) && (thread_if_true
2708 ? check_annul_list_true_false (0, delay_list
)
2709 && eligible_for_annul_false (insn
, *pslots_filled
, trial
, flags
)
2710 : check_annul_list_true_false (1, delay_list
)
2711 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
2719 if (reg_mentioned_p (cc0_rtx
, pat
))
2720 link_cc0_insns (trial
);
2723 /* If we own this thread, delete the insn. If this is the
2724 destination of a branch, show that a basic block status
2725 may have been updated. In any case, mark the new
2726 starting point of this thread. */
2731 update_block (trial
, thread
);
2732 if (trial
== thread
)
2734 thread
= next_active_insn (thread
);
2735 if (new_thread
== trial
)
2736 new_thread
= thread
;
2739 /* We are moving this insn, not deleting it. We must
2740 temporarily increment the use count on any referenced
2741 label lest it be deleted by delete_related_insns. */
2742 for (note
= REG_NOTES (trial
);
2744 note
= XEXP (note
, 1))
2745 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2746 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2748 /* REG_LABEL_OPERAND could be
2749 NOTE_INSN_DELETED_LABEL too. */
2750 if (LABEL_P (XEXP (note
, 0)))
2751 LABEL_NUSES (XEXP (note
, 0))++;
2753 gcc_assert (REG_NOTE_KIND (note
)
2754 == REG_LABEL_OPERAND
);
2756 if (JUMP_P (trial
) && JUMP_LABEL (trial
))
2757 LABEL_NUSES (JUMP_LABEL (trial
))++;
2759 delete_related_insns (trial
);
2761 for (note
= REG_NOTES (trial
);
2763 note
= XEXP (note
, 1))
2764 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2765 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2767 /* REG_LABEL_OPERAND could be
2768 NOTE_INSN_DELETED_LABEL too. */
2769 if (LABEL_P (XEXP (note
, 0)))
2770 LABEL_NUSES (XEXP (note
, 0))--;
2772 gcc_assert (REG_NOTE_KIND (note
)
2773 == REG_LABEL_OPERAND
);
2775 if (JUMP_P (trial
) && JUMP_LABEL (trial
))
2776 LABEL_NUSES (JUMP_LABEL (trial
))--;
2779 new_thread
= next_active_insn (trial
);
2781 temp
= own_thread
? trial
: copy_rtx (trial
);
2783 INSN_FROM_TARGET_P (temp
) = 1;
2785 delay_list
= add_to_delay_list (temp
, delay_list
);
2787 if (slots_to_fill
== ++(*pslots_filled
))
2789 /* Even though we have filled all the slots, we
2790 may be branching to a location that has a
2791 redundant insn. Skip any if so. */
2792 while (new_thread
&& ! own_thread
2793 && ! insn_sets_resource_p (new_thread
, &set
, 1)
2794 && ! insn_sets_resource_p (new_thread
, &needed
, 1)
2795 && ! insn_references_resource_p (new_thread
,
2798 = redundant_insn (new_thread
, insn
,
2801 /* We know we do not own the thread, so no need
2802 to call update_block and delete_insn. */
2803 fix_reg_dead_note (prior_insn
, insn
);
2804 update_reg_unused_notes (prior_insn
, new_thread
);
2805 new_thread
= next_active_insn (new_thread
);
2815 /* This insn can't go into a delay slot. */
2817 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2818 mark_referenced_resources (trial
, &needed
, 1);
2820 /* Ensure we don't put insns between the setting of cc and the comparison
2821 by moving a setting of cc into an earlier delay slot since these insns
2822 could clobber the condition code. */
2825 /* If this insn is a register-register copy and the next insn has
2826 a use of our destination, change it to use our source. That way,
2827 it will become a candidate for our delay slot the next time
2828 through this loop. This case occurs commonly in loops that
2831 We could check for more complex cases than those tested below,
2832 but it doesn't seem worth it. It might also be a good idea to try
2833 to swap the two insns. That might do better.
2835 We can't do this if the next insn modifies our destination, because
2836 that would make the replacement into the insn invalid. We also can't
2837 do this if it modifies our source, because it might be an earlyclobber
2838 operand. This latter test also prevents updating the contents of
2839 a PRE_INC. We also can't do this if there's overlap of source and
2840 destination. Overlap may happen for larger-than-register-size modes. */
2842 if (NONJUMP_INSN_P (trial
) && GET_CODE (pat
) == SET
2843 && REG_P (SET_SRC (pat
))
2844 && REG_P (SET_DEST (pat
))
2845 && !reg_overlap_mentioned_p (SET_DEST (pat
), SET_SRC (pat
)))
2847 rtx next
= next_nonnote_insn (trial
);
2849 if (next
&& NONJUMP_INSN_P (next
)
2850 && GET_CODE (PATTERN (next
)) != USE
2851 && ! reg_set_p (SET_DEST (pat
), next
)
2852 && ! reg_set_p (SET_SRC (pat
), next
)
2853 && reg_referenced_p (SET_DEST (pat
), PATTERN (next
))
2854 && ! modified_in_p (SET_DEST (pat
), next
))
2855 validate_replace_rtx (SET_DEST (pat
), SET_SRC (pat
), next
);
2859 /* If we stopped on a branch insn that has delay slots, see if we can
2860 steal some of the insns in those slots. */
2861 if (trial
&& NONJUMP_INSN_P (trial
)
2862 && GET_CODE (PATTERN (trial
)) == SEQUENCE
2863 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0)))
2865 /* If this is the `true' thread, we will want to follow the jump,
2866 so we can only do this if we have taken everything up to here. */
2867 if (thread_if_true
&& trial
== new_thread
)
2870 = steal_delay_list_from_target (insn
, condition
, PATTERN (trial
),
2871 delay_list
, &set
, &needed
,
2872 &opposite_needed
, slots_to_fill
,
2873 pslots_filled
, &must_annul
,
2875 /* If we owned the thread and are told that it branched
2876 elsewhere, make sure we own the thread at the new location. */
2877 if (own_thread
&& trial
!= new_thread
)
2878 own_thread
= own_thread_p (new_thread
, new_thread
, 0);
2880 else if (! thread_if_true
)
2882 = steal_delay_list_from_fallthrough (insn
, condition
,
2884 delay_list
, &set
, &needed
,
2885 &opposite_needed
, slots_to_fill
,
2886 pslots_filled
, &must_annul
);
2889 /* If we haven't found anything for this delay slot and it is very
2890 likely that the branch will be taken, see if the insn at our target
2891 increments or decrements a register with an increment that does not
2892 depend on the destination register. If so, try to place the opposite
2893 arithmetic insn after the jump insn and put the arithmetic insn in the
2894 delay slot. If we can't do this, return. */
2895 if (delay_list
== 0 && likely
&& new_thread
2896 && NONJUMP_INSN_P (new_thread
)
2897 && GET_CODE (PATTERN (new_thread
)) != ASM_INPUT
2898 && asm_noperands (PATTERN (new_thread
)) < 0)
2900 rtx pat
= PATTERN (new_thread
);
2905 pat
= PATTERN (trial
);
2907 if (!NONJUMP_INSN_P (trial
)
2908 || GET_CODE (pat
) != SET
2909 || ! eligible_for_delay (insn
, 0, trial
, flags
)
2910 || can_throw_internal (trial
))
2913 dest
= SET_DEST (pat
), src
= SET_SRC (pat
);
2914 if ((GET_CODE (src
) == PLUS
|| GET_CODE (src
) == MINUS
)
2915 && rtx_equal_p (XEXP (src
, 0), dest
)
2916 && (!FLOAT_MODE_P (GET_MODE (src
))
2917 || flag_unsafe_math_optimizations
)
2918 && ! reg_overlap_mentioned_p (dest
, XEXP (src
, 1))
2919 && ! side_effects_p (pat
))
2921 rtx other
= XEXP (src
, 1);
2925 /* If this is a constant adjustment, use the same code with
2926 the negated constant. Otherwise, reverse the sense of the
2928 if (GET_CODE (other
) == CONST_INT
)
2929 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
), GET_MODE (src
), dest
,
2930 negate_rtx (GET_MODE (src
), other
));
2932 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
) == PLUS
? MINUS
: PLUS
,
2933 GET_MODE (src
), dest
, other
);
2935 ninsn
= emit_insn_after (gen_rtx_SET (VOIDmode
, dest
, new_arith
),
2938 if (recog_memoized (ninsn
) < 0
2939 || (extract_insn (ninsn
), ! constrain_operands (1)))
2941 delete_related_insns (ninsn
);
2947 update_block (trial
, thread
);
2948 if (trial
== thread
)
2950 thread
= next_active_insn (thread
);
2951 if (new_thread
== trial
)
2952 new_thread
= thread
;
2954 delete_related_insns (trial
);
2957 new_thread
= next_active_insn (trial
);
2959 ninsn
= own_thread
? trial
: copy_rtx (trial
);
2961 INSN_FROM_TARGET_P (ninsn
) = 1;
2963 delay_list
= add_to_delay_list (ninsn
, NULL_RTX
);
2968 if (delay_list
&& must_annul
)
2969 INSN_ANNULLED_BRANCH_P (insn
) = 1;
2971 /* If we are to branch into the middle of this thread, find an appropriate
2972 label or make a new one if none, and redirect INSN to it. If we hit the
2973 end of the function, use the end-of-function label. */
2974 if (new_thread
!= thread
)
2978 gcc_assert (thread_if_true
);
2980 if (new_thread
&& JUMP_P (new_thread
)
2981 && (simplejump_p (new_thread
)
2982 || GET_CODE (PATTERN (new_thread
)) == RETURN
)
2983 && redirect_with_delay_list_safe_p (insn
,
2984 JUMP_LABEL (new_thread
),
2986 new_thread
= follow_jumps (JUMP_LABEL (new_thread
));
2988 if (new_thread
== 0)
2989 label
= find_end_label ();
2990 else if (LABEL_P (new_thread
))
2993 label
= get_label_before (new_thread
);
2996 reorg_redirect_jump (insn
, label
);
3002 /* Make another attempt to find insns to place in delay slots.
3004 We previously looked for insns located in front of the delay insn
3005 and, for non-jump delay insns, located behind the delay insn.
3007 Here only try to schedule jump insns and try to move insns from either
3008 the target or the following insns into the delay slot. If annulling is
3009 supported, we will be likely to do this. Otherwise, we can do this only
3013 fill_eager_delay_slots (void)
3017 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
3019 for (i
= 0; i
< num_unfilled_slots
; i
++)
3022 rtx target_label
, insn_at_target
, fallthrough_insn
;
3025 int own_fallthrough
;
3026 int prediction
, slots_to_fill
, slots_filled
;
3028 insn
= unfilled_slots_base
[i
];
3030 || INSN_DELETED_P (insn
)
3032 || ! (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
3035 slots_to_fill
= num_delay_slots (insn
);
3036 /* Some machine description have defined instructions to have
3037 delay slots only in certain circumstances which may depend on
3038 nearby insns (which change due to reorg's actions).
3040 For example, the PA port normally has delay slots for unconditional
3043 However, the PA port claims such jumps do not have a delay slot
3044 if they are immediate successors of certain CALL_INSNs. This
3045 allows the port to favor filling the delay slot of the call with
3046 the unconditional jump. */
3047 if (slots_to_fill
== 0)
3051 target_label
= JUMP_LABEL (insn
);
3052 condition
= get_branch_condition (insn
, target_label
);
3057 /* Get the next active fallthrough and target insns and see if we own
3058 them. Then see whether the branch is likely true. We don't need
3059 to do a lot of this for unconditional branches. */
3061 insn_at_target
= next_active_insn (target_label
);
3062 own_target
= own_thread_p (target_label
, target_label
, 0);
3064 if (condition
== const_true_rtx
)
3066 own_fallthrough
= 0;
3067 fallthrough_insn
= 0;
3072 fallthrough_insn
= next_active_insn (insn
);
3073 own_fallthrough
= own_thread_p (NEXT_INSN (insn
), NULL_RTX
, 1);
3074 prediction
= mostly_true_jump (insn
, condition
);
3077 /* If this insn is expected to branch, first try to get insns from our
3078 target, then our fallthrough insns. If it is not expected to branch,
3079 try the other order. */
3084 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
3085 fallthrough_insn
, prediction
== 2, 1,
3087 slots_to_fill
, &slots_filled
, delay_list
);
3089 if (delay_list
== 0 && own_fallthrough
)
3091 /* Even though we didn't find anything for delay slots,
3092 we might have found a redundant insn which we deleted
3093 from the thread that was filled. So we have to recompute
3094 the next insn at the target. */
3095 target_label
= JUMP_LABEL (insn
);
3096 insn_at_target
= next_active_insn (target_label
);
3099 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
3100 insn_at_target
, 0, 0,
3102 slots_to_fill
, &slots_filled
,
3108 if (own_fallthrough
)
3110 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
3111 insn_at_target
, 0, 0,
3113 slots_to_fill
, &slots_filled
,
3116 if (delay_list
== 0)
3118 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
3119 next_active_insn (insn
), 0, 1,
3121 slots_to_fill
, &slots_filled
,
3126 unfilled_slots_base
[i
]
3127 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
3129 if (slots_to_fill
== slots_filled
)
3130 unfilled_slots_base
[i
] = 0;
3132 note_delay_statistics (slots_filled
, 1);
3136 static void delete_computation (rtx insn
);
3138 /* Recursively delete prior insns that compute the value (used only by INSN
3139 which the caller is deleting) stored in the register mentioned by NOTE
3140 which is a REG_DEAD note associated with INSN. */
3143 delete_prior_computation (rtx note
, rtx insn
)
3146 rtx reg
= XEXP (note
, 0);
3148 for (our_prev
= prev_nonnote_insn (insn
);
3149 our_prev
&& (NONJUMP_INSN_P (our_prev
)
3150 || CALL_P (our_prev
));
3151 our_prev
= prev_nonnote_insn (our_prev
))
3153 rtx pat
= PATTERN (our_prev
);
3155 /* If we reach a CALL which is not calling a const function
3156 or the callee pops the arguments, then give up. */
3157 if (CALL_P (our_prev
)
3158 && (! RTL_CONST_CALL_P (our_prev
)
3159 || GET_CODE (pat
) != SET
|| GET_CODE (SET_SRC (pat
)) != CALL
))
3162 /* If we reach a SEQUENCE, it is too complex to try to
3163 do anything with it, so give up. We can be run during
3164 and after reorg, so SEQUENCE rtl can legitimately show
3166 if (GET_CODE (pat
) == SEQUENCE
)
3169 if (GET_CODE (pat
) == USE
3170 && NONJUMP_INSN_P (XEXP (pat
, 0)))
3171 /* reorg creates USEs that look like this. We leave them
3172 alone because reorg needs them for its own purposes. */
3175 if (reg_set_p (reg
, pat
))
3177 if (side_effects_p (pat
) && !CALL_P (our_prev
))
3180 if (GET_CODE (pat
) == PARALLEL
)
3182 /* If we find a SET of something else, we can't
3187 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3189 rtx part
= XVECEXP (pat
, 0, i
);
3191 if (GET_CODE (part
) == SET
3192 && SET_DEST (part
) != reg
)
3196 if (i
== XVECLEN (pat
, 0))
3197 delete_computation (our_prev
);
3199 else if (GET_CODE (pat
) == SET
3200 && REG_P (SET_DEST (pat
)))
3202 int dest_regno
= REGNO (SET_DEST (pat
));
3203 int dest_endregno
= END_REGNO (SET_DEST (pat
));
3204 int regno
= REGNO (reg
);
3205 int endregno
= END_REGNO (reg
);
3207 if (dest_regno
>= regno
3208 && dest_endregno
<= endregno
)
3209 delete_computation (our_prev
);
3211 /* We may have a multi-word hard register and some, but not
3212 all, of the words of the register are needed in subsequent
3213 insns. Write REG_UNUSED notes for those parts that were not
3215 else if (dest_regno
<= regno
3216 && dest_endregno
>= endregno
)
3220 REG_NOTES (our_prev
)
3221 = gen_rtx_EXPR_LIST (REG_UNUSED
, reg
,
3222 REG_NOTES (our_prev
));
3224 for (i
= dest_regno
; i
< dest_endregno
; i
++)
3225 if (! find_regno_note (our_prev
, REG_UNUSED
, i
))
3228 if (i
== dest_endregno
)
3229 delete_computation (our_prev
);
3236 /* If PAT references the register that dies here, it is an
3237 additional use. Hence any prior SET isn't dead. However, this
3238 insn becomes the new place for the REG_DEAD note. */
3239 if (reg_overlap_mentioned_p (reg
, pat
))
3241 XEXP (note
, 1) = REG_NOTES (our_prev
);
3242 REG_NOTES (our_prev
) = note
;
3248 /* Delete INSN and recursively delete insns that compute values used only
3249 by INSN. This uses the REG_DEAD notes computed during flow analysis.
3250 If we are running before flow.c, we need do nothing since flow.c will
3251 delete dead code. We also can't know if the registers being used are
3252 dead or not at this point.
3254 Otherwise, look at all our REG_DEAD notes. If a previous insn does
3255 nothing other than set a register that dies in this insn, we can delete
3258 On machines with CC0, if CC0 is used in this insn, we may be able to
3259 delete the insn that set it. */
3262 delete_computation (rtx insn
)
3267 if (reg_referenced_p (cc0_rtx
, PATTERN (insn
)))
3269 rtx prev
= prev_nonnote_insn (insn
);
3270 /* We assume that at this stage
3271 CC's are always set explicitly
3272 and always immediately before the jump that
3273 will use them. So if the previous insn
3274 exists to set the CC's, delete it
3275 (unless it performs auto-increments, etc.). */
3276 if (prev
&& NONJUMP_INSN_P (prev
)
3277 && sets_cc0_p (PATTERN (prev
)))
3279 if (sets_cc0_p (PATTERN (prev
)) > 0
3280 && ! side_effects_p (PATTERN (prev
)))
3281 delete_computation (prev
);
3283 /* Otherwise, show that cc0 won't be used. */
3284 REG_NOTES (prev
) = gen_rtx_EXPR_LIST (REG_UNUSED
,
3285 cc0_rtx
, REG_NOTES (prev
));
3290 for (note
= REG_NOTES (insn
); note
; note
= next
)
3292 next
= XEXP (note
, 1);
3294 if (REG_NOTE_KIND (note
) != REG_DEAD
3295 /* Verify that the REG_NOTE is legitimate. */
3296 || !REG_P (XEXP (note
, 0)))
3299 delete_prior_computation (note
, insn
);
3302 delete_related_insns (insn
);
3305 /* If all INSN does is set the pc, delete it,
3306 and delete the insn that set the condition codes for it
3307 if that's what the previous thing was. */
3310 delete_jump (rtx insn
)
3312 rtx set
= single_set (insn
);
3314 if (set
&& GET_CODE (SET_DEST (set
)) == PC
)
3315 delete_computation (insn
);
3319 /* Once we have tried two ways to fill a delay slot, make a pass over the
3320 code to try to improve the results and to do such things as more jump
3324 relax_delay_slots (rtx first
)
3326 rtx insn
, next
, pat
;
3327 rtx trial
, delay_insn
, target_label
;
3329 /* Look at every JUMP_INSN and see if we can improve it. */
3330 for (insn
= first
; insn
; insn
= next
)
3334 next
= next_active_insn (insn
);
3336 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3337 the next insn, or jumps to a label that is not the last of a
3338 group of consecutive labels. */
3340 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3341 && (target_label
= JUMP_LABEL (insn
)) != 0)
3343 target_label
= skip_consecutive_labels (follow_jumps (target_label
));
3344 if (target_label
== 0)
3345 target_label
= find_end_label ();
3347 if (target_label
&& next_active_insn (target_label
) == next
3348 && ! condjump_in_parallel_p (insn
))
3354 if (target_label
&& target_label
!= JUMP_LABEL (insn
))
3355 reorg_redirect_jump (insn
, target_label
);
3357 /* See if this jump conditionally branches around an unconditional
3358 jump. If so, invert this jump and point it to the target of the
3360 if (next
&& JUMP_P (next
)
3361 && any_condjump_p (insn
)
3362 && (simplejump_p (next
) || GET_CODE (PATTERN (next
)) == RETURN
)
3364 && next_active_insn (target_label
) == next_active_insn (next
)
3365 && no_labels_between_p (insn
, next
))
3367 rtx label
= JUMP_LABEL (next
);
3369 /* Be careful how we do this to avoid deleting code or
3370 labels that are momentarily dead. See similar optimization
3373 We also need to ensure we properly handle the case when
3374 invert_jump fails. */
3376 ++LABEL_NUSES (target_label
);
3378 ++LABEL_NUSES (label
);
3380 if (invert_jump (insn
, label
, 1))
3382 delete_related_insns (next
);
3387 --LABEL_NUSES (label
);
3389 if (--LABEL_NUSES (target_label
) == 0)
3390 delete_related_insns (target_label
);
3396 /* If this is an unconditional jump and the previous insn is a
3397 conditional jump, try reversing the condition of the previous
3398 insn and swapping our targets. The next pass might be able to
3401 Don't do this if we expect the conditional branch to be true, because
3402 we would then be making the more common case longer. */
3405 && (simplejump_p (insn
) || GET_CODE (PATTERN (insn
)) == RETURN
)
3406 && (other
= prev_active_insn (insn
)) != 0
3407 && any_condjump_p (other
)
3408 && no_labels_between_p (other
, insn
)
3409 && 0 > mostly_true_jump (other
,
3410 get_branch_condition (other
,
3411 JUMP_LABEL (other
))))
3413 rtx other_target
= JUMP_LABEL (other
);
3414 target_label
= JUMP_LABEL (insn
);
3416 if (invert_jump (other
, target_label
, 0))
3417 reorg_redirect_jump (insn
, other_target
);
3420 /* Now look only at cases where we have filled a delay slot. */
3421 if (!NONJUMP_INSN_P (insn
)
3422 || GET_CODE (PATTERN (insn
)) != SEQUENCE
)
3425 pat
= PATTERN (insn
);
3426 delay_insn
= XVECEXP (pat
, 0, 0);
3428 /* See if the first insn in the delay slot is redundant with some
3429 previous insn. Remove it from the delay slot if so; then set up
3430 to reprocess this insn. */
3431 if (redundant_insn (XVECEXP (pat
, 0, 1), delay_insn
, 0))
3433 delete_from_delay_slot (XVECEXP (pat
, 0, 1));
3434 next
= prev_active_insn (next
);
3438 /* See if we have a RETURN insn with a filled delay slot followed
3439 by a RETURN insn with an unfilled a delay slot. If so, we can delete
3440 the first RETURN (but not its delay insn). This gives the same
3441 effect in fewer instructions.
3443 Only do so if optimizing for size since this results in slower, but
3446 && GET_CODE (PATTERN (delay_insn
)) == RETURN
3449 && GET_CODE (PATTERN (next
)) == RETURN
)
3454 /* Delete the RETURN and just execute the delay list insns.
3456 We do this by deleting the INSN containing the SEQUENCE, then
3457 re-emitting the insns separately, and then deleting the RETURN.
3458 This allows the count of the jump target to be properly
3461 /* Clear the from target bit, since these insns are no longer
3463 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3464 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3466 trial
= PREV_INSN (insn
);
3467 delete_related_insns (insn
);
3468 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3470 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3472 rtx this_insn
= XVECEXP (pat
, 0, i
);
3473 add_insn_after (this_insn
, after
, NULL
);
3476 delete_scheduled_jump (delay_insn
);
3480 /* Now look only at the cases where we have a filled JUMP_INSN. */
3481 if (!JUMP_P (XVECEXP (PATTERN (insn
), 0, 0))
3482 || ! (condjump_p (XVECEXP (PATTERN (insn
), 0, 0))
3483 || condjump_in_parallel_p (XVECEXP (PATTERN (insn
), 0, 0))))
3486 target_label
= JUMP_LABEL (delay_insn
);
3490 /* If this jump goes to another unconditional jump, thread it, but
3491 don't convert a jump into a RETURN here. */
3492 trial
= skip_consecutive_labels (follow_jumps (target_label
));
3494 trial
= find_end_label ();
3496 if (trial
&& trial
!= target_label
3497 && redirect_with_delay_slots_safe_p (delay_insn
, trial
, insn
))
3499 reorg_redirect_jump (delay_insn
, trial
);
3500 target_label
= trial
;
3503 /* If the first insn at TARGET_LABEL is redundant with a previous
3504 insn, redirect the jump to the following insn process again. */
3505 trial
= next_active_insn (target_label
);
3506 if (trial
&& GET_CODE (PATTERN (trial
)) != SEQUENCE
3507 && redundant_insn (trial
, insn
, 0)
3508 && ! can_throw_internal (trial
))
3510 /* Figure out where to emit the special USE insn so we don't
3511 later incorrectly compute register live/death info. */
3512 rtx tmp
= next_active_insn (trial
);
3514 tmp
= find_end_label ();
3518 /* Insert the special USE insn and update dataflow info. */
3519 update_block (trial
, tmp
);
3521 /* Now emit a label before the special USE insn, and
3522 redirect our jump to the new label. */
3523 target_label
= get_label_before (PREV_INSN (tmp
));
3524 reorg_redirect_jump (delay_insn
, target_label
);
3530 /* Similarly, if it is an unconditional jump with one insn in its
3531 delay list and that insn is redundant, thread the jump. */
3532 if (trial
&& GET_CODE (PATTERN (trial
)) == SEQUENCE
3533 && XVECLEN (PATTERN (trial
), 0) == 2
3534 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0))
3535 && (simplejump_p (XVECEXP (PATTERN (trial
), 0, 0))
3536 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial
), 0, 0))) == RETURN
)
3537 && redundant_insn (XVECEXP (PATTERN (trial
), 0, 1), insn
, 0))
3539 target_label
= JUMP_LABEL (XVECEXP (PATTERN (trial
), 0, 0));
3540 if (target_label
== 0)
3541 target_label
= find_end_label ();
3544 && redirect_with_delay_slots_safe_p (delay_insn
, target_label
,
3547 reorg_redirect_jump (delay_insn
, target_label
);
3554 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3555 && prev_active_insn (target_label
) == insn
3556 && ! condjump_in_parallel_p (delay_insn
)
3558 /* If the last insn in the delay slot sets CC0 for some insn,
3559 various code assumes that it is in a delay slot. We could
3560 put it back where it belonged and delete the register notes,
3561 but it doesn't seem worthwhile in this uncommon case. */
3562 && ! find_reg_note (XVECEXP (pat
, 0, XVECLEN (pat
, 0) - 1),
3563 REG_CC_USER
, NULL_RTX
)
3570 /* All this insn does is execute its delay list and jump to the
3571 following insn. So delete the jump and just execute the delay
3574 We do this by deleting the INSN containing the SEQUENCE, then
3575 re-emitting the insns separately, and then deleting the jump.
3576 This allows the count of the jump target to be properly
3579 /* Clear the from target bit, since these insns are no longer
3581 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3582 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3584 trial
= PREV_INSN (insn
);
3585 delete_related_insns (insn
);
3586 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3588 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3590 rtx this_insn
= XVECEXP (pat
, 0, i
);
3591 add_insn_after (this_insn
, after
, NULL
);
3594 delete_scheduled_jump (delay_insn
);
3598 /* See if this is an unconditional jump around a single insn which is
3599 identical to the one in its delay slot. In this case, we can just
3600 delete the branch and the insn in its delay slot. */
3601 if (next
&& NONJUMP_INSN_P (next
)
3602 && prev_label (next_active_insn (next
)) == target_label
3603 && simplejump_p (insn
)
3604 && XVECLEN (pat
, 0) == 2
3605 && rtx_equal_p (PATTERN (next
), PATTERN (XVECEXP (pat
, 0, 1))))
3607 delete_related_insns (insn
);
3611 /* See if this jump (with its delay slots) conditionally branches
3612 around an unconditional jump (without delay slots). If so, invert
3613 this jump and point it to the target of the second jump. We cannot
3614 do this for annulled jumps, though. Again, don't convert a jump to
3616 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3617 && any_condjump_p (delay_insn
)
3618 && next
&& JUMP_P (next
)
3619 && (simplejump_p (next
) || GET_CODE (PATTERN (next
)) == RETURN
)
3620 && next_active_insn (target_label
) == next_active_insn (next
)
3621 && no_labels_between_p (insn
, next
))
3623 rtx label
= JUMP_LABEL (next
);
3624 rtx old_label
= JUMP_LABEL (delay_insn
);
3627 label
= find_end_label ();
3629 /* find_end_label can generate a new label. Check this first. */
3631 && no_labels_between_p (insn
, next
)
3632 && redirect_with_delay_slots_safe_p (delay_insn
, label
, insn
))
3634 /* Be careful how we do this to avoid deleting code or labels
3635 that are momentarily dead. See similar optimization in
3638 ++LABEL_NUSES (old_label
);
3640 if (invert_jump (delay_insn
, label
, 1))
3644 /* Must update the INSN_FROM_TARGET_P bits now that
3645 the branch is reversed, so that mark_target_live_regs
3646 will handle the delay slot insn correctly. */
3647 for (i
= 1; i
< XVECLEN (PATTERN (insn
), 0); i
++)
3649 rtx slot
= XVECEXP (PATTERN (insn
), 0, i
);
3650 INSN_FROM_TARGET_P (slot
) = ! INSN_FROM_TARGET_P (slot
);
3653 delete_related_insns (next
);
3657 if (old_label
&& --LABEL_NUSES (old_label
) == 0)
3658 delete_related_insns (old_label
);
3663 /* If we own the thread opposite the way this insn branches, see if we
3664 can merge its delay slots with following insns. */
3665 if (INSN_FROM_TARGET_P (XVECEXP (pat
, 0, 1))
3666 && own_thread_p (NEXT_INSN (insn
), 0, 1))
3667 try_merge_delay_insns (insn
, next
);
3668 else if (! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, 1))
3669 && own_thread_p (target_label
, target_label
, 0))
3670 try_merge_delay_insns (insn
, next_active_insn (target_label
));
3672 /* If we get here, we haven't deleted INSN. But we may have deleted
3673 NEXT, so recompute it. */
3674 next
= next_active_insn (insn
);
3680 /* Look for filled jumps to the end of function label. We can try to convert
3681 them into RETURN insns if the insns in the delay slot are valid for the
3685 make_return_insns (rtx first
)
3687 rtx insn
, jump_insn
, pat
;
3688 rtx real_return_label
= end_of_function_label
;
3691 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3692 /* If a previous pass filled delay slots in the epilogue, things get a
3693 bit more complicated, as those filler insns would generally (without
3694 data flow analysis) have to be executed after any existing branch
3695 delay slot filler insns. It is also unknown whether such a
3696 transformation would actually be profitable. Note that the existing
3697 code only cares for branches with (some) filled delay slots. */
3698 if (crtl
->epilogue_delay_list
!= NULL
)
3702 /* See if there is a RETURN insn in the function other than the one we
3703 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3704 into a RETURN to jump to it. */
3705 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3706 if (JUMP_P (insn
) && GET_CODE (PATTERN (insn
)) == RETURN
)
3708 real_return_label
= get_label_before (insn
);
3712 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3713 was equal to END_OF_FUNCTION_LABEL. */
3714 LABEL_NUSES (real_return_label
)++;
3716 /* Clear the list of insns to fill so we can use it. */
3717 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3719 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3723 /* Only look at filled JUMP_INSNs that go to the end of function
3725 if (!NONJUMP_INSN_P (insn
)
3726 || GET_CODE (PATTERN (insn
)) != SEQUENCE
3727 || !JUMP_P (XVECEXP (PATTERN (insn
), 0, 0))
3728 || JUMP_LABEL (XVECEXP (PATTERN (insn
), 0, 0)) != end_of_function_label
)
3731 pat
= PATTERN (insn
);
3732 jump_insn
= XVECEXP (pat
, 0, 0);
3734 /* If we can't make the jump into a RETURN, try to redirect it to the best
3735 RETURN and go on to the next insn. */
3736 if (! reorg_redirect_jump (jump_insn
, NULL_RTX
))
3738 /* Make sure redirecting the jump will not invalidate the delay
3740 if (redirect_with_delay_slots_safe_p (jump_insn
,
3743 reorg_redirect_jump (jump_insn
, real_return_label
);
3747 /* See if this RETURN can accept the insns current in its delay slot.
3748 It can if it has more or an equal number of slots and the contents
3749 of each is valid. */
3751 flags
= get_jump_flags (jump_insn
, JUMP_LABEL (jump_insn
));
3752 slots
= num_delay_slots (jump_insn
);
3753 if (slots
>= XVECLEN (pat
, 0) - 1)
3755 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3757 #ifdef ANNUL_IFFALSE_SLOTS
3758 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3759 && INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
3760 ? eligible_for_annul_false (jump_insn
, i
- 1,
3761 XVECEXP (pat
, 0, i
), flags
) :
3763 #ifdef ANNUL_IFTRUE_SLOTS
3764 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3765 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
3766 ? eligible_for_annul_true (jump_insn
, i
- 1,
3767 XVECEXP (pat
, 0, i
), flags
) :
3769 eligible_for_delay (jump_insn
, i
- 1,
3770 XVECEXP (pat
, 0, i
), flags
)))
3776 if (i
== XVECLEN (pat
, 0))
3779 /* We have to do something with this insn. If it is an unconditional
3780 RETURN, delete the SEQUENCE and output the individual insns,
3781 followed by the RETURN. Then set things up so we try to find
3782 insns for its delay slots, if it needs some. */
3783 if (GET_CODE (PATTERN (jump_insn
)) == RETURN
)
3785 rtx prev
= PREV_INSN (insn
);
3787 delete_related_insns (insn
);
3788 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3789 prev
= emit_insn_after (PATTERN (XVECEXP (pat
, 0, i
)), prev
);
3791 insn
= emit_jump_insn_after (PATTERN (jump_insn
), prev
);
3792 emit_barrier_after (insn
);
3795 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3798 /* It is probably more efficient to keep this with its current
3799 delay slot as a branch to a RETURN. */
3800 reorg_redirect_jump (jump_insn
, real_return_label
);
3803 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3804 new delay slots we have created. */
3805 if (--LABEL_NUSES (real_return_label
) == 0)
3806 delete_related_insns (real_return_label
);
3808 fill_simple_delay_slots (1);
3809 fill_simple_delay_slots (0);
3813 /* Try to find insns to place in delay slots. */
3816 dbr_schedule (rtx first
)
3818 rtx insn
, next
, epilogue_insn
= 0;
3821 /* If the current function has no insns other than the prologue and
3822 epilogue, then do not try to fill any delay slots. */
3823 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
3826 /* Find the highest INSN_UID and allocate and initialize our map from
3827 INSN_UID's to position in code. */
3828 for (max_uid
= 0, insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3830 if (INSN_UID (insn
) > max_uid
)
3831 max_uid
= INSN_UID (insn
);
3833 && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3834 epilogue_insn
= insn
;
3837 uid_to_ruid
= xmalloc ((max_uid
+ 1) * sizeof (int));
3838 for (i
= 0, insn
= first
; insn
; i
++, insn
= NEXT_INSN (insn
))
3839 uid_to_ruid
[INSN_UID (insn
)] = i
;
3841 /* Initialize the list of insns that need filling. */
3842 if (unfilled_firstobj
== 0)
3844 gcc_obstack_init (&unfilled_slots_obstack
);
3845 unfilled_firstobj
= obstack_alloc (&unfilled_slots_obstack
, 0);
3848 for (insn
= next_active_insn (first
); insn
; insn
= next_active_insn (insn
))
3852 INSN_ANNULLED_BRANCH_P (insn
) = 0;
3853 INSN_FROM_TARGET_P (insn
) = 0;
3855 /* Skip vector tables. We can't get attributes for them. */
3857 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
3858 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
3861 if (num_delay_slots (insn
) > 0)
3862 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3864 /* Ensure all jumps go to the last of a set of consecutive labels. */
3866 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3867 && JUMP_LABEL (insn
) != 0
3868 && ((target
= skip_consecutive_labels (JUMP_LABEL (insn
)))
3869 != JUMP_LABEL (insn
)))
3870 redirect_jump (insn
, target
, 1);
3873 init_resource_info (epilogue_insn
);
3875 /* Show we haven't computed an end-of-function label yet. */
3876 end_of_function_label
= 0;
3878 /* Initialize the statistics for this function. */
3879 memset (num_insns_needing_delays
, 0, sizeof num_insns_needing_delays
);
3880 memset (num_filled_delays
, 0, sizeof num_filled_delays
);
3882 /* Now do the delay slot filling. Try everything twice in case earlier
3883 changes make more slots fillable. */
3885 for (reorg_pass_number
= 0;
3886 reorg_pass_number
< MAX_REORG_PASSES
;
3887 reorg_pass_number
++)
3889 fill_simple_delay_slots (1);
3890 fill_simple_delay_slots (0);
3891 fill_eager_delay_slots ();
3892 relax_delay_slots (first
);
3895 /* If we made an end of function label, indicate that it is now
3896 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3897 If it is now unused, delete it. */
3898 if (end_of_function_label
&& --LABEL_NUSES (end_of_function_label
) == 0)
3899 delete_related_insns (end_of_function_label
);
3902 if (HAVE_return
&& end_of_function_label
!= 0)
3903 make_return_insns (first
);
3906 /* Delete any USE insns made by update_block; subsequent passes don't need
3907 them or know how to deal with them. */
3908 for (insn
= first
; insn
; insn
= next
)
3910 next
= NEXT_INSN (insn
);
3912 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == USE
3913 && INSN_P (XEXP (PATTERN (insn
), 0)))
3914 next
= delete_related_insns (insn
);
3917 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3919 /* It is not clear why the line below is needed, but it does seem to be. */
3920 unfilled_firstobj
= obstack_alloc (&unfilled_slots_obstack
, 0);
3924 int i
, j
, need_comma
;
3925 int total_delay_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3926 int total_annul_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3928 for (reorg_pass_number
= 0;
3929 reorg_pass_number
< MAX_REORG_PASSES
;
3930 reorg_pass_number
++)
3932 fprintf (dump_file
, ";; Reorg pass #%d:\n", reorg_pass_number
+ 1);
3933 for (i
= 0; i
< NUM_REORG_FUNCTIONS
; i
++)
3936 fprintf (dump_file
, ";; Reorg function #%d\n", i
);
3938 fprintf (dump_file
, ";; %d insns needing delay slots\n;; ",
3939 num_insns_needing_delays
[i
][reorg_pass_number
]);
3941 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3942 if (num_filled_delays
[i
][j
][reorg_pass_number
])
3945 fprintf (dump_file
, ", ");
3947 fprintf (dump_file
, "%d got %d delays",
3948 num_filled_delays
[i
][j
][reorg_pass_number
], j
);
3950 fprintf (dump_file
, "\n");
3953 memset (total_delay_slots
, 0, sizeof total_delay_slots
);
3954 memset (total_annul_slots
, 0, sizeof total_annul_slots
);
3955 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3957 if (! INSN_DELETED_P (insn
)
3958 && NONJUMP_INSN_P (insn
)
3959 && GET_CODE (PATTERN (insn
)) != USE
3960 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3962 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
3964 j
= XVECLEN (PATTERN (insn
), 0) - 1;
3965 if (j
> MAX_DELAY_HISTOGRAM
)
3966 j
= MAX_DELAY_HISTOGRAM
;
3967 if (INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (insn
), 0, 0)))
3968 total_annul_slots
[j
]++;
3970 total_delay_slots
[j
]++;
3972 else if (num_delay_slots (insn
) > 0)
3973 total_delay_slots
[0]++;
3976 fprintf (dump_file
, ";; Reorg totals: ");
3978 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3980 if (total_delay_slots
[j
])
3983 fprintf (dump_file
, ", ");
3985 fprintf (dump_file
, "%d got %d delays", total_delay_slots
[j
], j
);
3988 fprintf (dump_file
, "\n");
3989 #if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
3990 fprintf (dump_file
, ";; Reorg annuls: ");
3992 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3994 if (total_annul_slots
[j
])
3997 fprintf (dump_file
, ", ");
3999 fprintf (dump_file
, "%d got %d delays", total_annul_slots
[j
], j
);
4002 fprintf (dump_file
, "\n");
4004 fprintf (dump_file
, "\n");
4007 /* For all JUMP insns, fill in branch prediction notes, so that during
4008 assembler output a target can set branch prediction bits in the code.
4009 We have to do this now, as up until this point the destinations of
4010 JUMPS can be moved around and changed, but past right here that cannot
4012 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
4016 if (NONJUMP_INSN_P (insn
))
4018 rtx pat
= PATTERN (insn
);
4020 if (GET_CODE (pat
) == SEQUENCE
)
4021 insn
= XVECEXP (pat
, 0, 0);
4026 pred_flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
4027 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_BR_PRED
,
4028 GEN_INT (pred_flags
),
4031 free_resource_info ();
4033 #ifdef DELAY_SLOTS_FOR_EPILOGUE
4034 /* SPARC assembler, for instance, emit warning when debug info is output
4035 into the delay slot. */
4039 for (link
= crtl
->epilogue_delay_list
;
4041 link
= XEXP (link
, 1))
4042 INSN_LOCATOR (XEXP (link
, 0)) = 0;
4047 #endif /* DELAY_SLOTS */
4050 gate_handle_delay_slots (void)
4053 return flag_delayed_branch
;
4059 /* Run delay slot optimization. */
4061 rest_of_handle_delay_slots (void)
4064 dbr_schedule (get_insns ());
4069 struct rtl_opt_pass pass_delay_slots
=
4074 gate_handle_delay_slots
, /* gate */
4075 rest_of_handle_delay_slots
, /* execute */
4078 0, /* static_pass_number */
4079 TV_DBR_SCHED
, /* tv_id */
4080 0, /* properties_required */
4081 0, /* properties_provided */
4082 0, /* properties_destroyed */
4083 0, /* todo_flags_start */
4085 TODO_ggc_collect
/* todo_flags_finish */
4089 /* Machine dependent reorg pass. */
4091 gate_handle_machine_reorg (void)
4093 return targetm
.machine_dependent_reorg
!= 0;
4098 rest_of_handle_machine_reorg (void)
4100 targetm
.machine_dependent_reorg ();
4104 struct rtl_opt_pass pass_machine_reorg
=
4109 gate_handle_machine_reorg
, /* gate */
4110 rest_of_handle_machine_reorg
, /* execute */
4113 0, /* static_pass_number */
4114 TV_MACH_DEP
, /* tv_id */
4115 0, /* properties_required */
4116 0, /* properties_provided */
4117 0, /* properties_destroyed */
4118 0, /* todo_flags_start */
4120 TODO_ggc_collect
/* todo_flags_finish */