1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
5 Hacked by Michael Tiemann (tiemann@cygnus.com).
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
139 #ifndef ANNUL_IFTRUE_SLOTS
140 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
142 #ifndef ANNUL_IFFALSE_SLOTS
143 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
146 /* Insns which have delay slots that have not yet been filled. */
148 static struct obstack unfilled_slots_obstack;
149 static rtx *unfilled_firstobj;
151 /* Define macros to refer to the first and last slot containing unfilled
152 insns. These are used because the list may move and its address
153 should be recomputed at each use. */
155 #define unfilled_slots_base \
156 ((rtx *) obstack_base (&unfilled_slots_obstack))
158 #define unfilled_slots_next \
159 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
161 /* Points to the label before the end of the function. */
162 static rtx end_of_function_label;
164 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
165 not always monotonically increase. */
166 static int *uid_to_ruid;
168 /* Highest valid index in `uid_to_ruid'. */
171 static int stop_search_p (rtx, int);
172 static int resource_conflicts_p (struct resources *, struct resources *);
173 static int insn_references_resource_p (rtx, struct resources *, int);
174 static int insn_sets_resource_p (rtx, struct resources *, int);
175 static rtx find_end_label (void);
176 static rtx emit_delay_sequence (rtx, rtx, int);
177 static rtx add_to_delay_list (rtx, rtx);
178 static rtx delete_from_delay_slot (rtx);
179 static void delete_scheduled_jump (rtx);
180 static void note_delay_statistics (int, int);
181 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
182 static rtx optimize_skip (rtx);
184 static int get_jump_flags (rtx, rtx);
185 static int rare_destination (rtx);
186 static int mostly_true_jump (rtx, rtx);
187 static rtx get_branch_condition (rtx, rtx);
188 static int condition_dominates_p (rtx, rtx);
189 static int redirect_with_delay_slots_safe_p (rtx, rtx, rtx);
190 static int redirect_with_delay_list_safe_p (rtx, rtx, rtx);
191 static int check_annul_list_true_false (int, rtx);
192 static rtx steal_delay_list_from_target (rtx, rtx, rtx, rtx,
196 int, int *, int *, rtx *);
197 static rtx steal_delay_list_from_fallthrough (rtx, rtx, rtx, rtx,
202 static void try_merge_delay_insns (rtx, rtx);
203 static rtx redundant_insn (rtx, rtx, rtx);
204 static int own_thread_p (rtx, rtx, int);
205 static void update_block (rtx, rtx);
206 static int reorg_redirect_jump (rtx, rtx);
207 static void update_reg_dead_notes (rtx, rtx);
208 static void fix_reg_dead_note (rtx, rtx);
209 static void update_reg_unused_notes (rtx, rtx);
210 static void fill_simple_delay_slots (int);
211 static rtx fill_slots_from_thread (rtx, rtx, rtx, rtx, int, int, int, int,
213 static void fill_eager_delay_slots (void);
214 static void relax_delay_slots (rtx);
216 static void make_return_insns (rtx);
219 /* Return TRUE if this insn should stop the search for insn to fill delay
220 slots. LABELS_P indicates that labels should terminate the search.
221 In all cases, jumps terminate the search. */
224 stop_search_p (rtx insn, int labels_p)
229 /* If the insn can throw an exception that is caught within the function,
230 it may effectively perform a jump from the viewpoint of the function.
231 Therefore act like for a jump. */
232 if (can_throw_internal (insn))
235 switch (GET_CODE (insn))
249 /* OK unless it contains a delay slot or is an `asm' insn of some type.
250 We don't know anything about these. */
251 return (GET_CODE (PATTERN (insn)) == SEQUENCE
252 || GET_CODE (PATTERN (insn)) == ASM_INPUT
253 || asm_noperands (PATTERN (insn)) >= 0);
260 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
261 resource set contains a volatile memory reference. Otherwise, return FALSE. */
264 resource_conflicts_p (struct resources *res1, struct resources *res2)
266 if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
267 || (res1->unch_memory && res2->unch_memory)
268 || res1->volatil || res2->volatil)
272 return (res1->regs & res2->regs) != HARD_CONST (0);
277 for (i = 0; i < HARD_REG_SET_LONGS; i++)
278 if ((res1->regs[i] & res2->regs[i]) != 0)
285 /* Return TRUE if any resource marked in RES, a `struct resources', is
286 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
287 routine is using those resources.
289 We compute this by computing all the resources referenced by INSN and
290 seeing if this conflicts with RES. It might be faster to directly check
291 ourselves, and this is the way it used to work, but it means duplicating
292 a large block of complex code. */
295 insn_references_resource_p (rtx insn, struct resources *res,
296 int include_delayed_effects)
298 struct resources insn_res;
300 CLEAR_RESOURCE (&insn_res);
301 mark_referenced_resources (insn, &insn_res, include_delayed_effects);
302 return resource_conflicts_p (&insn_res, res);
305 /* Return TRUE if INSN modifies resources that are marked in RES.
306 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
307 included. CC0 is only modified if it is explicitly set; see comments
308 in front of mark_set_resources for details. */
311 insn_sets_resource_p (rtx insn, struct resources *res,
312 int include_delayed_effects)
314 struct resources insn_sets;
316 CLEAR_RESOURCE (&insn_sets);
317 mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
318 return resource_conflicts_p (&insn_sets, res);
321 /* Find a label at the end of the function or before a RETURN. If there
322 is none, try to make one. If that fails, returns 0.
324 The property of such a label is that it is placed just before the
325 epilogue or a bare RETURN insn, so that another bare RETURN can be
326 turned into a jump to the label unconditionally. In particular, the
327 label cannot be placed before a RETURN insn with a filled delay slot.
329 ??? There may be a problem with the current implementation. Suppose
330 we start with a bare RETURN insn and call find_end_label. It may set
331 end_of_function_label just before the RETURN. Suppose the machinery
332 is able to fill the delay slot of the RETURN insn afterwards. Then
333 end_of_function_label is no longer valid according to the property
334 described above and find_end_label will still return it unmodified.
335 Note that this is probably mitigated by the following observation:
336 once end_of_function_label is made, it is very likely the target of
337 a jump, so filling the delay slot of the RETURN will be much more
341 find_end_label (void)
345 /* If we found one previously, return it. */
346 if (end_of_function_label)
347 return end_of_function_label;
349 /* Otherwise, see if there is a label at the end of the function. If there
350 is, it must be that RETURN insns aren't needed, so that is our return
351 label and we don't have to do anything else. */
353 insn = get_last_insn ();
354 while (GET_CODE (insn) == NOTE
355 || (GET_CODE (insn) == INSN
356 && (GET_CODE (PATTERN (insn)) == USE
357 || GET_CODE (PATTERN (insn)) == CLOBBER)))
358 insn = PREV_INSN (insn);
360 /* When a target threads its epilogue we might already have a
361 suitable return insn. If so put a label before it for the
362 end_of_function_label. */
363 if (GET_CODE (insn) == BARRIER
364 && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
365 && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
367 rtx temp = PREV_INSN (PREV_INSN (insn));
368 end_of_function_label = gen_label_rtx ();
369 LABEL_NUSES (end_of_function_label) = 0;
371 /* Put the label before an USE insns that may precede the RETURN insn. */
372 while (GET_CODE (temp) == USE)
373 temp = PREV_INSN (temp);
375 emit_label_after (end_of_function_label, temp);
378 else if (GET_CODE (insn) == CODE_LABEL)
379 end_of_function_label = insn;
382 end_of_function_label = gen_label_rtx ();
383 LABEL_NUSES (end_of_function_label) = 0;
384 /* If the basic block reorder pass moves the return insn to
385 some other place try to locate it again and put our
386 end_of_function_label there. */
387 while (insn && ! (GET_CODE (insn) == JUMP_INSN
388 && (GET_CODE (PATTERN (insn)) == RETURN)))
389 insn = PREV_INSN (insn);
392 insn = PREV_INSN (insn);
394 /* Put the label before an USE insns that may proceed the
396 while (GET_CODE (insn) == USE)
397 insn = PREV_INSN (insn);
399 emit_label_after (end_of_function_label, insn);
410 /* The RETURN insn has its delay slot filled so we cannot
411 emit the label just before it. Since we already have
412 an epilogue and cannot emit a new RETURN, we cannot
413 emit the label at all. */
414 end_of_function_label = NULL_RTX;
415 return end_of_function_label;
417 #endif /* HAVE_epilogue */
419 /* Otherwise, make a new label and emit a RETURN and BARRIER,
421 emit_label (end_of_function_label);
425 /* The return we make may have delay slots too. */
426 rtx insn = gen_return ();
427 insn = emit_jump_insn (insn);
429 if (num_delay_slots (insn) > 0)
430 obstack_ptr_grow (&unfilled_slots_obstack, insn);
436 /* Show one additional use for this label so it won't go away until
438 ++LABEL_NUSES (end_of_function_label);
440 return end_of_function_label;
443 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
444 the pattern of INSN with the SEQUENCE.
446 Chain the insns so that NEXT_INSN of each insn in the sequence points to
447 the next and NEXT_INSN of the last insn in the sequence points to
448 the first insn after the sequence. Similarly for PREV_INSN. This makes
449 it easier to scan all insns.
451 Returns the SEQUENCE that replaces INSN. */
454 emit_delay_sequence (rtx insn, rtx list, int length)
460 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
461 rtvec seqv = rtvec_alloc (length + 1);
462 rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
463 rtx seq_insn = make_insn_raw (seq);
464 rtx first = get_insns ();
465 rtx last = get_last_insn ();
467 /* Make a copy of the insn having delay slots. */
468 rtx delay_insn = copy_rtx (insn);
470 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
471 confuse further processing. Update LAST in case it was the last insn.
472 We will put the BARRIER back in later. */
473 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
475 delete_related_insns (NEXT_INSN (insn));
476 last = get_last_insn ();
480 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
481 NEXT_INSN (seq_insn) = NEXT_INSN (insn);
482 PREV_INSN (seq_insn) = PREV_INSN (insn);
485 PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
488 NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
490 /* Note the calls to set_new_first_and_last_insn must occur after
491 SEQ_INSN has been completely spliced into the insn stream.
493 Otherwise CUR_INSN_UID will get set to an incorrect value because
494 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */
496 set_new_first_and_last_insn (first, seq_insn);
499 set_new_first_and_last_insn (seq_insn, last);
501 /* Build our SEQUENCE and rebuild the insn chain. */
502 XVECEXP (seq, 0, 0) = delay_insn;
503 INSN_DELETED_P (delay_insn) = 0;
504 PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
506 for (li = list; li; li = XEXP (li, 1), i++)
508 rtx tem = XEXP (li, 0);
511 /* Show that this copy of the insn isn't deleted. */
512 INSN_DELETED_P (tem) = 0;
514 XVECEXP (seq, 0, i) = tem;
515 PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
516 NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
518 /* SPARC assembler, for instance, emit warning when debug info is output
519 into the delay slot. */
520 if (INSN_LOCATOR (tem) && !INSN_LOCATOR (seq_insn))
521 INSN_LOCATOR (seq_insn) = INSN_LOCATOR (tem);
522 INSN_LOCATOR (tem) = 0;
524 for (note = REG_NOTES (tem); note; note = next)
526 next = XEXP (note, 1);
527 switch (REG_NOTE_KIND (note))
530 /* Remove any REG_DEAD notes because we can't rely on them now
531 that the insn has been moved. */
532 remove_note (tem, note);
536 /* Keep the label reference count up to date. */
537 if (GET_CODE (XEXP (note, 0)) == CODE_LABEL)
538 LABEL_NUSES (XEXP (note, 0)) ++;
547 NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
549 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
550 last insn in that SEQUENCE to point to us. Similarly for the first
551 insn in the following insn if it is a SEQUENCE. */
553 if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
554 && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
555 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
556 XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
559 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
560 && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
561 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
563 /* If there used to be a BARRIER, put it back. */
565 emit_barrier_after (seq_insn);
573 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
574 be in the order in which the insns are to be executed. */
577 add_to_delay_list (rtx insn, rtx delay_list)
579 /* If we have an empty list, just make a new list element. If
580 INSN has its block number recorded, clear it since we may
581 be moving the insn to a new block. */
585 clear_hashed_info_for_insn (insn);
586 return gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
589 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
591 XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
596 /* Delete INSN from the delay slot of the insn that it is in, which may
597 produce an insn with no delay slots. Return the new insn. */
600 delete_from_delay_slot (rtx insn)
602 rtx trial, seq_insn, seq, prev;
607 /* We first must find the insn containing the SEQUENCE with INSN in its
608 delay slot. Do this by finding an insn, TRIAL, where
609 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
612 PREV_INSN (NEXT_INSN (trial)) == trial;
613 trial = NEXT_INSN (trial))
616 seq_insn = PREV_INSN (NEXT_INSN (trial));
617 seq = PATTERN (seq_insn);
619 if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == BARRIER)
622 /* Create a delay list consisting of all the insns other than the one
623 we are deleting (unless we were the only one). */
624 if (XVECLEN (seq, 0) > 2)
625 for (i = 1; i < XVECLEN (seq, 0); i++)
626 if (XVECEXP (seq, 0, i) != insn)
627 delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
629 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
630 list, and rebuild the delay list if non-empty. */
631 prev = PREV_INSN (seq_insn);
632 trial = XVECEXP (seq, 0, 0);
633 delete_related_insns (seq_insn);
634 add_insn_after (trial, prev);
636 /* If there was a barrier after the old SEQUENCE, remit it. */
638 emit_barrier_after (trial);
640 /* If there are any delay insns, remit them. Otherwise clear the
643 trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2);
644 else if (GET_CODE (trial) == JUMP_INSN
645 || GET_CODE (trial) == CALL_INSN
646 || GET_CODE (trial) == INSN)
647 INSN_ANNULLED_BRANCH_P (trial) = 0;
649 INSN_FROM_TARGET_P (insn) = 0;
651 /* Show we need to fill this insn again. */
652 obstack_ptr_grow (&unfilled_slots_obstack, trial);
657 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
658 the insn that sets CC0 for it and delete it too. */
661 delete_scheduled_jump (rtx insn)
663 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
664 delete the insn that sets the condition code, but it is hard to find it.
665 Since this case is rare anyway, don't bother trying; there would likely
666 be other insns that became dead anyway, which we wouldn't know to
670 if (reg_mentioned_p (cc0_rtx, insn))
672 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
674 /* If a reg-note was found, it points to an insn to set CC0. This
675 insn is in the delay list of some other insn. So delete it from
676 the delay list it was in. */
679 if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
680 && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
681 delete_from_delay_slot (XEXP (note, 0));
685 /* The insn setting CC0 is our previous insn, but it may be in
686 a delay slot. It will be the last insn in the delay slot, if
688 rtx trial = previous_insn (insn);
689 if (GET_CODE (trial) == NOTE)
690 trial = prev_nonnote_insn (trial);
691 if (sets_cc0_p (PATTERN (trial)) != 1
692 || FIND_REG_INC_NOTE (trial, NULL_RTX))
694 if (PREV_INSN (NEXT_INSN (trial)) == trial)
695 delete_related_insns (trial);
697 delete_from_delay_slot (trial);
702 delete_related_insns (insn);
705 /* Counters for delay-slot filling. */
707 #define NUM_REORG_FUNCTIONS 2
708 #define MAX_DELAY_HISTOGRAM 3
709 #define MAX_REORG_PASSES 2
711 static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
713 static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
715 static int reorg_pass_number;
718 note_delay_statistics (int slots_filled, int index)
720 num_insns_needing_delays[index][reorg_pass_number]++;
721 if (slots_filled > MAX_DELAY_HISTOGRAM)
722 slots_filled = MAX_DELAY_HISTOGRAM;
723 num_filled_delays[index][slots_filled][reorg_pass_number]++;
726 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
728 /* Optimize the following cases:
730 1. When a conditional branch skips over only one instruction,
731 use an annulling branch and put that insn in the delay slot.
732 Use either a branch that annuls when the condition if true or
733 invert the test with a branch that annuls when the condition is
734 false. This saves insns, since otherwise we must copy an insn
737 (orig) (skip) (otherwise)
738 Bcc.n L1 Bcc',a L1 Bcc,a L1'
745 2. When a conditional branch skips over only one instruction,
746 and after that, it unconditionally branches somewhere else,
747 perform the similar optimization. This saves executing the
748 second branch in the case where the inverted condition is true.
757 This should be expanded to skip over N insns, where N is the number
758 of delay slots required. */
761 optimize_skip (rtx insn)
763 rtx trial = next_nonnote_insn (insn);
764 rtx next_trial = next_active_insn (trial);
768 flags = get_jump_flags (insn, JUMP_LABEL (insn));
771 || GET_CODE (trial) != INSN
772 || GET_CODE (PATTERN (trial)) == SEQUENCE
773 || recog_memoized (trial) < 0
774 || (! eligible_for_annul_false (insn, 0, trial, flags)
775 && ! eligible_for_annul_true (insn, 0, trial, flags))
776 || can_throw_internal (trial))
779 /* There are two cases where we are just executing one insn (we assume
780 here that a branch requires only one insn; this should be generalized
781 at some point): Where the branch goes around a single insn or where
782 we have one insn followed by a branch to the same label we branch to.
783 In both of these cases, inverting the jump and annulling the delay
784 slot give the same effect in fewer insns. */
785 if ((next_trial == next_active_insn (JUMP_LABEL (insn))
786 && ! (next_trial == 0 && current_function_epilogue_delay_list != 0))
788 && GET_CODE (next_trial) == JUMP_INSN
789 && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
790 && (simplejump_p (next_trial)
791 || GET_CODE (PATTERN (next_trial)) == RETURN)))
793 if (eligible_for_annul_false (insn, 0, trial, flags))
795 if (invert_jump (insn, JUMP_LABEL (insn), 1))
796 INSN_FROM_TARGET_P (trial) = 1;
797 else if (! eligible_for_annul_true (insn, 0, trial, flags))
801 delay_list = add_to_delay_list (trial, NULL_RTX);
802 next_trial = next_active_insn (trial);
803 update_block (trial, trial);
804 delete_related_insns (trial);
806 /* Also, if we are targeting an unconditional
807 branch, thread our jump to the target of that branch. Don't
808 change this into a RETURN here, because it may not accept what
809 we have in the delay slot. We'll fix this up later. */
810 if (next_trial && GET_CODE (next_trial) == JUMP_INSN
811 && (simplejump_p (next_trial)
812 || GET_CODE (PATTERN (next_trial)) == RETURN))
814 rtx target_label = JUMP_LABEL (next_trial);
815 if (target_label == 0)
816 target_label = find_end_label ();
820 /* Recompute the flags based on TARGET_LABEL since threading
821 the jump to TARGET_LABEL may change the direction of the
822 jump (which may change the circumstances in which the
823 delay slot is nullified). */
824 flags = get_jump_flags (insn, target_label);
825 if (eligible_for_annul_true (insn, 0, trial, flags))
826 reorg_redirect_jump (insn, target_label);
830 INSN_ANNULLED_BRANCH_P (insn) = 1;
837 /* Encode and return branch direction and prediction information for
838 INSN assuming it will jump to LABEL.
840 Non conditional branches return no direction information and
841 are predicted as very likely taken. */
844 get_jump_flags (rtx insn, rtx label)
848 /* get_jump_flags can be passed any insn with delay slots, these may
849 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
850 direction information, and only if they are conditional jumps.
852 If LABEL is zero, then there is no way to determine the branch
854 if (GET_CODE (insn) == JUMP_INSN
855 && (condjump_p (insn) || condjump_in_parallel_p (insn))
856 && INSN_UID (insn) <= max_uid
858 && INSN_UID (label) <= max_uid)
860 = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
861 ? ATTR_FLAG_forward : ATTR_FLAG_backward;
862 /* No valid direction information. */
866 /* If insn is a conditional branch call mostly_true_jump to get
867 determine the branch prediction.
869 Non conditional branches are predicted as very likely taken. */
870 if (GET_CODE (insn) == JUMP_INSN
871 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
875 prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
879 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
882 flags |= ATTR_FLAG_likely;
885 flags |= ATTR_FLAG_unlikely;
888 flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
896 flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
901 /* Return 1 if INSN is a destination that will be branched to rarely (the
902 return point of a function); return 2 if DEST will be branched to very
903 rarely (a call to a function that doesn't return). Otherwise,
907 rare_destination (rtx insn)
912 for (; insn; insn = next)
914 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE)
915 insn = XVECEXP (PATTERN (insn), 0, 0);
917 next = NEXT_INSN (insn);
919 switch (GET_CODE (insn))
924 /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We
925 don't scan past JUMP_INSNs, so any barrier we find here must
926 have been after a CALL_INSN and hence mean the call doesn't
930 if (GET_CODE (PATTERN (insn)) == RETURN)
932 else if (simplejump_p (insn)
933 && jump_count++ < 10)
934 next = JUMP_LABEL (insn);
943 /* If we got here it means we hit the end of the function. So this
944 is an unlikely destination. */
949 /* Return truth value of the statement that this branch
950 is mostly taken. If we think that the branch is extremely likely
951 to be taken, we return 2. If the branch is slightly more likely to be
952 taken, return 1. If the branch is slightly less likely to be taken,
953 return 0 and if the branch is highly unlikely to be taken, return -1.
955 CONDITION, if nonzero, is the condition that JUMP_INSN is testing. */
958 mostly_true_jump (rtx jump_insn, rtx condition)
960 rtx target_label = JUMP_LABEL (jump_insn);
962 int rare_dest = rare_destination (target_label);
963 int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
965 /* If branch probabilities are available, then use that number since it
966 always gives a correct answer. */
967 note = find_reg_note (jump_insn, REG_BR_PROB, 0);
970 int prob = INTVAL (XEXP (note, 0));
972 if (prob >= REG_BR_PROB_BASE * 9 / 10)
974 else if (prob >= REG_BR_PROB_BASE / 2)
976 else if (prob >= REG_BR_PROB_BASE / 10)
982 /* ??? Ought to use estimate_probability instead. */
984 /* If this is a branch outside a loop, it is highly unlikely. */
985 if (GET_CODE (PATTERN (jump_insn)) == SET
986 && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
987 && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
988 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
989 || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
990 && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
995 /* If this is the test of a loop, it is very likely true. We scan
996 backwards from the target label. If we find a NOTE_INSN_LOOP_BEG
997 before the next real insn, we assume the branch is to the top of
999 for (insn = PREV_INSN (target_label);
1000 insn && GET_CODE (insn) == NOTE;
1001 insn = PREV_INSN (insn))
1002 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1005 /* If this is a jump to the test of a loop, it is likely true. We scan
1006 forwards from the target label. If we find a NOTE_INSN_LOOP_VTOP
1007 before the next real insn, we assume the branch is to the loop branch
1009 for (insn = NEXT_INSN (target_label);
1010 insn && GET_CODE (insn) == NOTE;
1011 insn = PREV_INSN (insn))
1012 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
1016 /* Look at the relative rarities of the fallthrough and destination. If
1017 they differ, we can predict the branch that way. */
1019 switch (rare_fallthrough - rare_dest)
1033 /* If we couldn't figure out what this jump was, assume it won't be
1034 taken. This should be rare. */
1038 /* EQ tests are usually false and NE tests are usually true. Also,
1039 most quantities are positive, so we can make the appropriate guesses
1040 about signed comparisons against zero. */
1041 switch (GET_CODE (condition))
1044 /* Unconditional branch. */
1052 if (XEXP (condition, 1) == const0_rtx)
1057 if (XEXP (condition, 1) == const0_rtx)
1065 /* Predict backward branches usually take, forward branches usually not. If
1066 we don't know whether this is forward or backward, assume the branch
1067 will be taken, since most are. */
1068 return (target_label == 0 || INSN_UID (jump_insn) > max_uid
1069 || INSN_UID (target_label) > max_uid
1070 || (uid_to_ruid[INSN_UID (jump_insn)]
1071 > uid_to_ruid[INSN_UID (target_label)]));
1074 /* Return the condition under which INSN will branch to TARGET. If TARGET
1075 is zero, return the condition under which INSN will return. If INSN is
1076 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1077 type of jump, or it doesn't go to TARGET, return 0. */
1080 get_branch_condition (rtx insn, rtx target)
1082 rtx pat = PATTERN (insn);
1085 if (condjump_in_parallel_p (insn))
1086 pat = XVECEXP (pat, 0, 0);
1088 if (GET_CODE (pat) == RETURN)
1089 return target == 0 ? const_true_rtx : 0;
1091 else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1094 src = SET_SRC (pat);
1095 if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1096 return const_true_rtx;
1098 else if (GET_CODE (src) == IF_THEN_ELSE
1099 && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1100 || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1101 && XEXP (XEXP (src, 1), 0) == target))
1102 && XEXP (src, 2) == pc_rtx)
1103 return XEXP (src, 0);
1105 else if (GET_CODE (src) == IF_THEN_ELSE
1106 && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1107 || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1108 && XEXP (XEXP (src, 2), 0) == target))
1109 && XEXP (src, 1) == pc_rtx)
1112 rev = reversed_comparison_code (XEXP (src, 0), insn);
1114 return gen_rtx_fmt_ee (rev, GET_MODE (XEXP (src, 0)),
1115 XEXP (XEXP (src, 0), 0),
1116 XEXP (XEXP (src, 0), 1));
1122 /* Return nonzero if CONDITION is more strict than the condition of
1123 INSN, i.e., if INSN will always branch if CONDITION is true. */
1126 condition_dominates_p (rtx condition, rtx insn)
1128 rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1129 enum rtx_code code = GET_CODE (condition);
1130 enum rtx_code other_code;
1132 if (rtx_equal_p (condition, other_condition)
1133 || other_condition == const_true_rtx)
1136 else if (condition == const_true_rtx || other_condition == 0)
1139 other_code = GET_CODE (other_condition);
1140 if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1141 || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1142 || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1145 return comparison_dominates_p (code, other_code);
1148 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1149 any insns already in the delay slot of JUMP. */
1152 redirect_with_delay_slots_safe_p (rtx jump, rtx newlabel, rtx seq)
1155 rtx pat = PATTERN (seq);
1157 /* Make sure all the delay slots of this jump would still
1158 be valid after threading the jump. If they are still
1159 valid, then return nonzero. */
1161 flags = get_jump_flags (jump, newlabel);
1162 for (i = 1; i < XVECLEN (pat, 0); i++)
1164 #ifdef ANNUL_IFFALSE_SLOTS
1165 (INSN_ANNULLED_BRANCH_P (jump)
1166 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1167 ? eligible_for_annul_false (jump, i - 1,
1168 XVECEXP (pat, 0, i), flags) :
1170 #ifdef ANNUL_IFTRUE_SLOTS
1171 (INSN_ANNULLED_BRANCH_P (jump)
1172 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
1173 ? eligible_for_annul_true (jump, i - 1,
1174 XVECEXP (pat, 0, i), flags) :
1176 eligible_for_delay (jump, i - 1, XVECEXP (pat, 0, i), flags)))
1179 return (i == XVECLEN (pat, 0));
1182 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1183 any insns we wish to place in the delay slot of JUMP. */
1186 redirect_with_delay_list_safe_p (rtx jump, rtx newlabel, rtx delay_list)
1191 /* Make sure all the insns in DELAY_LIST would still be
1192 valid after threading the jump. If they are still
1193 valid, then return nonzero. */
1195 flags = get_jump_flags (jump, newlabel);
1196 for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++)
1198 #ifdef ANNUL_IFFALSE_SLOTS
1199 (INSN_ANNULLED_BRANCH_P (jump)
1200 && INSN_FROM_TARGET_P (XEXP (li, 0)))
1201 ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) :
1203 #ifdef ANNUL_IFTRUE_SLOTS
1204 (INSN_ANNULLED_BRANCH_P (jump)
1205 && ! INSN_FROM_TARGET_P (XEXP (li, 0)))
1206 ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) :
1208 eligible_for_delay (jump, i, XEXP (li, 0), flags)))
1211 return (li == NULL);
1214 /* DELAY_LIST is a list of insns that have already been placed into delay
1215 slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
1216 If not, return 0; otherwise return 1. */
1219 check_annul_list_true_false (int annul_true_p, rtx delay_list)
1225 for (temp = delay_list; temp; temp = XEXP (temp, 1))
1227 rtx trial = XEXP (temp, 0);
1229 if ((annul_true_p && INSN_FROM_TARGET_P (trial))
1230 || (!annul_true_p && !INSN_FROM_TARGET_P (trial)))
1238 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1239 the condition tested by INSN is CONDITION and the resources shown in
1240 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1241 from SEQ's delay list, in addition to whatever insns it may execute
1242 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1243 needed while searching for delay slot insns. Return the concatenated
1244 delay list if possible, otherwise, return 0.
1246 SLOTS_TO_FILL is the total number of slots required by INSN, and
1247 PSLOTS_FILLED points to the number filled so far (also the number of
1248 insns in DELAY_LIST). It is updated with the number that have been
1249 filled from the SEQUENCE, if any.
1251 PANNUL_P points to a nonzero value if we already know that we need
1252 to annul INSN. If this routine determines that annulling is needed,
1253 it may set that value nonzero.
1255 PNEW_THREAD points to a location that is to receive the place at which
1256 execution should continue. */
1259 steal_delay_list_from_target (rtx insn, rtx condition, rtx seq,
1260 rtx delay_list, struct resources *sets,
1261 struct resources *needed,
1262 struct resources *other_needed,
1263 int slots_to_fill, int *pslots_filled,
1264 int *pannul_p, rtx *pnew_thread)
1267 int slots_remaining = slots_to_fill - *pslots_filled;
1268 int total_slots_filled = *pslots_filled;
1269 rtx new_delay_list = 0;
1270 int must_annul = *pannul_p;
1273 struct resources cc_set;
1275 /* We can't do anything if there are more delay slots in SEQ than we
1276 can handle, or if we don't know that it will be a taken branch.
1277 We know that it will be a taken branch if it is either an unconditional
1278 branch or a conditional branch with a stricter branch condition.
1280 Also, exit if the branch has more than one set, since then it is computing
1281 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1282 ??? It may be possible to move other sets into INSN in addition to
1283 moving the instructions in the delay slots.
1285 We can not steal the delay list if one of the instructions in the
1286 current delay_list modifies the condition codes and the jump in the
1287 sequence is a conditional jump. We can not do this because we can
1288 not change the direction of the jump because the condition codes
1289 will effect the direction of the jump in the sequence. */
1291 CLEAR_RESOURCE (&cc_set);
1292 for (temp = delay_list; temp; temp = XEXP (temp, 1))
1294 rtx trial = XEXP (temp, 0);
1296 mark_set_resources (trial, &cc_set, 0, MARK_SRC_DEST_CALL);
1297 if (insn_references_resource_p (XVECEXP (seq , 0, 0), &cc_set, 0))
1301 if (XVECLEN (seq, 0) - 1 > slots_remaining
1302 || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))
1303 || ! single_set (XVECEXP (seq, 0, 0)))
1306 #ifdef MD_CAN_REDIRECT_BRANCH
1307 /* On some targets, branches with delay slots can have a limited
1308 displacement. Give the back end a chance to tell us we can't do
1310 if (! MD_CAN_REDIRECT_BRANCH (insn, XVECEXP (seq, 0, 0)))
1314 for (i = 1; i < XVECLEN (seq, 0); i++)
1316 rtx trial = XVECEXP (seq, 0, i);
1319 if (insn_references_resource_p (trial, sets, 0)
1320 || insn_sets_resource_p (trial, needed, 0)
1321 || insn_sets_resource_p (trial, sets, 0)
1323 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1325 || find_reg_note (trial, REG_CC_USER, NULL_RTX)
1327 /* If TRIAL is from the fallthrough code of an annulled branch insn
1328 in SEQ, we cannot use it. */
1329 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1330 && ! INSN_FROM_TARGET_P (trial)))
1333 /* If this insn was already done (usually in a previous delay slot),
1334 pretend we put it in our delay slot. */
1335 if (redundant_insn (trial, insn, new_delay_list))
1338 /* We will end up re-vectoring this branch, so compute flags
1339 based on jumping to the new label. */
1340 flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
1343 && ((condition == const_true_rtx
1344 || (! insn_sets_resource_p (trial, other_needed, 0)
1345 && ! may_trap_p (PATTERN (trial)))))
1346 ? eligible_for_delay (insn, total_slots_filled, trial, flags)
1347 : (must_annul || (delay_list == NULL && new_delay_list == NULL))
1349 check_annul_list_true_false (0, delay_list)
1350 && check_annul_list_true_false (0, new_delay_list)
1351 && eligible_for_annul_false (insn, total_slots_filled,
1356 temp = copy_rtx (trial);
1357 INSN_FROM_TARGET_P (temp) = 1;
1358 new_delay_list = add_to_delay_list (temp, new_delay_list);
1359 total_slots_filled++;
1361 if (--slots_remaining == 0)
1368 /* Show the place to which we will be branching. */
1369 *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1371 /* Add any new insns to the delay list and update the count of the
1372 number of slots filled. */
1373 *pslots_filled = total_slots_filled;
1377 if (delay_list == 0)
1378 return new_delay_list;
1380 for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1381 delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1386 /* Similar to steal_delay_list_from_target except that SEQ is on the
1387 fallthrough path of INSN. Here we only do something if the delay insn
1388 of SEQ is an unconditional branch. In that case we steal its delay slot
1389 for INSN since unconditional branches are much easier to fill. */
1392 steal_delay_list_from_fallthrough (rtx insn, rtx condition, rtx seq,
1393 rtx delay_list, struct resources *sets,
1394 struct resources *needed,
1395 struct resources *other_needed,
1396 int slots_to_fill, int *pslots_filled,
1401 int must_annul = *pannul_p;
1404 flags = get_jump_flags (insn, JUMP_LABEL (insn));
1406 /* We can't do anything if SEQ's delay insn isn't an
1407 unconditional branch. */
1409 if (! simplejump_p (XVECEXP (seq, 0, 0))
1410 && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1413 for (i = 1; i < XVECLEN (seq, 0); i++)
1415 rtx trial = XVECEXP (seq, 0, i);
1417 /* If TRIAL sets CC0, stealing it will move it too far from the use
1419 if (insn_references_resource_p (trial, sets, 0)
1420 || insn_sets_resource_p (trial, needed, 0)
1421 || insn_sets_resource_p (trial, sets, 0)
1423 || sets_cc0_p (PATTERN (trial))
1429 /* If this insn was already done, we don't need it. */
1430 if (redundant_insn (trial, insn, delay_list))
1432 delete_from_delay_slot (trial);
1437 && ((condition == const_true_rtx
1438 || (! insn_sets_resource_p (trial, other_needed, 0)
1439 && ! may_trap_p (PATTERN (trial)))))
1440 ? eligible_for_delay (insn, *pslots_filled, trial, flags)
1441 : (must_annul || delay_list == NULL) && (must_annul = 1,
1442 check_annul_list_true_false (1, delay_list)
1443 && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
1447 delete_from_delay_slot (trial);
1448 delay_list = add_to_delay_list (trial, delay_list);
1450 if (++(*pslots_filled) == slots_to_fill)
1462 /* Try merging insns starting at THREAD which match exactly the insns in
1465 If all insns were matched and the insn was previously annulling, the
1466 annul bit will be cleared.
1468 For each insn that is merged, if the branch is or will be non-annulling,
1469 we delete the merged insn. */
1472 try_merge_delay_insns (rtx insn, rtx thread)
1474 rtx trial, next_trial;
1475 rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1476 int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1477 int slot_number = 1;
1478 int num_slots = XVECLEN (PATTERN (insn), 0);
1479 rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1480 struct resources set, needed;
1481 rtx merged_insns = 0;
1485 flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
1487 CLEAR_RESOURCE (&needed);
1488 CLEAR_RESOURCE (&set);
1490 /* If this is not an annulling branch, take into account anything needed in
1491 INSN's delay slot. This prevents two increments from being incorrectly
1492 folded into one. If we are annulling, this would be the correct
1493 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1494 will essentially disable this optimization. This method is somewhat of
1495 a kludge, but I don't see a better way.) */
1497 for (i = 1 ; i < num_slots; i++)
1498 if (XVECEXP (PATTERN (insn), 0, i))
1499 mark_referenced_resources (XVECEXP (PATTERN (insn), 0, i), &needed, 1);
1501 for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1503 rtx pat = PATTERN (trial);
1504 rtx oldtrial = trial;
1506 next_trial = next_nonnote_insn (trial);
1508 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1509 if (GET_CODE (trial) == INSN
1510 && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1513 if (GET_CODE (next_to_match) == GET_CODE (trial)
1515 /* We can't share an insn that sets cc0. */
1516 && ! sets_cc0_p (pat)
1518 && ! insn_references_resource_p (trial, &set, 1)
1519 && ! insn_sets_resource_p (trial, &set, 1)
1520 && ! insn_sets_resource_p (trial, &needed, 1)
1521 && (trial = try_split (pat, trial, 0)) != 0
1522 /* Update next_trial, in case try_split succeeded. */
1523 && (next_trial = next_nonnote_insn (trial))
1524 /* Likewise THREAD. */
1525 && (thread = oldtrial == thread ? trial : thread)
1526 && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1527 /* Have to test this condition if annul condition is different
1528 from (and less restrictive than) non-annulling one. */
1529 && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
1534 update_block (trial, thread);
1535 if (trial == thread)
1536 thread = next_active_insn (thread);
1538 delete_related_insns (trial);
1539 INSN_FROM_TARGET_P (next_to_match) = 0;
1542 merged_insns = gen_rtx_INSN_LIST (VOIDmode, trial, merged_insns);
1544 if (++slot_number == num_slots)
1547 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1550 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
1551 mark_referenced_resources (trial, &needed, 1);
1554 /* See if we stopped on a filled insn. If we did, try to see if its
1555 delay slots match. */
1556 if (slot_number != num_slots
1557 && trial && GET_CODE (trial) == INSN
1558 && GET_CODE (PATTERN (trial)) == SEQUENCE
1559 && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1561 rtx pat = PATTERN (trial);
1562 rtx filled_insn = XVECEXP (pat, 0, 0);
1564 /* Account for resources set/needed by the filled insn. */
1565 mark_set_resources (filled_insn, &set, 0, MARK_SRC_DEST_CALL);
1566 mark_referenced_resources (filled_insn, &needed, 1);
1568 for (i = 1; i < XVECLEN (pat, 0); i++)
1570 rtx dtrial = XVECEXP (pat, 0, i);
1572 if (! insn_references_resource_p (dtrial, &set, 1)
1573 && ! insn_sets_resource_p (dtrial, &set, 1)
1574 && ! insn_sets_resource_p (dtrial, &needed, 1)
1576 && ! sets_cc0_p (PATTERN (dtrial))
1578 && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1579 && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
1585 update_block (dtrial, thread);
1586 new = delete_from_delay_slot (dtrial);
1587 if (INSN_DELETED_P (thread))
1589 INSN_FROM_TARGET_P (next_to_match) = 0;
1592 merged_insns = gen_rtx_INSN_LIST (SImode, dtrial,
1595 if (++slot_number == num_slots)
1598 next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1602 /* Keep track of the set/referenced resources for the delay
1603 slots of any trial insns we encounter. */
1604 mark_set_resources (dtrial, &set, 0, MARK_SRC_DEST_CALL);
1605 mark_referenced_resources (dtrial, &needed, 1);
1610 /* If all insns in the delay slot have been matched and we were previously
1611 annulling the branch, we need not any more. In that case delete all the
1612 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1613 the delay list so that we know that it isn't only being used at the
1615 if (slot_number == num_slots && annul_p)
1617 for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1619 if (GET_MODE (merged_insns) == SImode)
1623 update_block (XEXP (merged_insns, 0), thread);
1624 new = delete_from_delay_slot (XEXP (merged_insns, 0));
1625 if (INSN_DELETED_P (thread))
1630 update_block (XEXP (merged_insns, 0), thread);
1631 delete_related_insns (XEXP (merged_insns, 0));
1635 INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1637 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1638 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1642 /* See if INSN is redundant with an insn in front of TARGET. Often this
1643 is called when INSN is a candidate for a delay slot of TARGET.
1644 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1645 of INSN. Often INSN will be redundant with an insn in a delay slot of
1646 some previous insn. This happens when we have a series of branches to the
1647 same label; in that case the first insn at the target might want to go
1648 into each of the delay slots.
1650 If we are not careful, this routine can take up a significant fraction
1651 of the total compilation time (4%), but only wins rarely. Hence we
1652 speed this routine up by making two passes. The first pass goes back
1653 until it hits a label and sees if it finds an insn with an identical
1654 pattern. Only in this (relatively rare) event does it check for
1657 We do not split insns we encounter. This could cause us not to find a
1658 redundant insn, but the cost of splitting seems greater than the possible
1659 gain in rare cases. */
1662 redundant_insn (rtx insn, rtx target, rtx delay_list)
1664 rtx target_main = target;
1665 rtx ipat = PATTERN (insn);
1667 struct resources needed, set;
1669 unsigned insns_to_search;
1671 /* If INSN has any REG_UNUSED notes, it can't match anything since we
1672 are allowed to not actually assign to such a register. */
1673 if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0)
1676 /* Scan backwards looking for a match. */
1677 for (trial = PREV_INSN (target),
1678 insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH;
1679 trial && insns_to_search > 0;
1680 trial = PREV_INSN (trial), --insns_to_search)
1682 if (GET_CODE (trial) == CODE_LABEL)
1685 if (! INSN_P (trial))
1688 pat = PATTERN (trial);
1689 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1692 if (GET_CODE (pat) == SEQUENCE)
1694 /* Stop for a CALL and its delay slots because it is difficult to
1695 track its resource needs correctly. */
1696 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1699 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1700 slots because it is difficult to track its resource needs
1703 #ifdef INSN_SETS_ARE_DELAYED
1704 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
1708 #ifdef INSN_REFERENCES_ARE_DELAYED
1709 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
1713 /* See if any of the insns in the delay slot match, updating
1714 resource requirements as we go. */
1715 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1716 if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
1717 && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat)
1718 && ! find_reg_note (XVECEXP (pat, 0, i), REG_UNUSED, NULL_RTX))
1721 /* If found a match, exit this loop early. */
1726 else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)
1727 && ! find_reg_note (trial, REG_UNUSED, NULL_RTX))
1731 /* If we didn't find an insn that matches, return 0. */
1735 /* See what resources this insn sets and needs. If they overlap, or
1736 if this insn references CC0, it can't be redundant. */
1738 CLEAR_RESOURCE (&needed);
1739 CLEAR_RESOURCE (&set);
1740 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
1741 mark_referenced_resources (insn, &needed, 1);
1743 /* If TARGET is a SEQUENCE, get the main insn. */
1744 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1745 target_main = XVECEXP (PATTERN (target), 0, 0);
1747 if (resource_conflicts_p (&needed, &set)
1749 || reg_mentioned_p (cc0_rtx, ipat)
1751 /* The insn requiring the delay may not set anything needed or set by
1753 || insn_sets_resource_p (target_main, &needed, 1)
1754 || insn_sets_resource_p (target_main, &set, 1))
1757 /* Insns we pass may not set either NEEDED or SET, so merge them for
1759 needed.memory |= set.memory;
1760 needed.unch_memory |= set.unch_memory;
1761 IOR_HARD_REG_SET (needed.regs, set.regs);
1763 /* This insn isn't redundant if it conflicts with an insn that either is
1764 or will be in a delay slot of TARGET. */
1768 if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
1770 delay_list = XEXP (delay_list, 1);
1773 if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1774 for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
1775 if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
1778 /* Scan backwards until we reach a label or an insn that uses something
1779 INSN sets or sets something insn uses or sets. */
1781 for (trial = PREV_INSN (target),
1782 insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH;
1783 trial && GET_CODE (trial) != CODE_LABEL && insns_to_search > 0;
1784 trial = PREV_INSN (trial), --insns_to_search)
1786 if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
1787 && GET_CODE (trial) != JUMP_INSN)
1790 pat = PATTERN (trial);
1791 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1794 if (GET_CODE (pat) == SEQUENCE)
1796 /* If this is a CALL_INSN and its delay slots, it is hard to track
1797 the resource needs properly, so give up. */
1798 if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1801 /* If this is an INSN or JUMP_INSN with delayed effects, it
1802 is hard to track the resource needs properly, so give up. */
1804 #ifdef INSN_SETS_ARE_DELAYED
1805 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
1809 #ifdef INSN_REFERENCES_ARE_DELAYED
1810 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
1814 /* See if any of the insns in the delay slot match, updating
1815 resource requirements as we go. */
1816 for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1818 rtx candidate = XVECEXP (pat, 0, i);
1820 /* If an insn will be annulled if the branch is false, it isn't
1821 considered as a possible duplicate insn. */
1822 if (rtx_equal_p (PATTERN (candidate), ipat)
1823 && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1824 && INSN_FROM_TARGET_P (candidate)))
1826 /* Show that this insn will be used in the sequel. */
1827 INSN_FROM_TARGET_P (candidate) = 0;
1831 /* Unless this is an annulled insn from the target of a branch,
1832 we must stop if it sets anything needed or set by INSN. */
1833 if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1834 || ! INSN_FROM_TARGET_P (candidate))
1835 && insn_sets_resource_p (candidate, &needed, 1))
1839 /* If the insn requiring the delay slot conflicts with INSN, we
1841 if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
1846 /* See if TRIAL is the same as INSN. */
1847 pat = PATTERN (trial);
1848 if (rtx_equal_p (pat, ipat))
1851 /* Can't go any further if TRIAL conflicts with INSN. */
1852 if (insn_sets_resource_p (trial, &needed, 1))
1860 /* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero,
1861 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1862 is nonzero, we are allowed to fall into this thread; otherwise, we are
1865 If LABEL is used more than one or we pass a label other than LABEL before
1866 finding an active insn, we do not own this thread. */
1869 own_thread_p (rtx thread, rtx label, int allow_fallthrough)
1874 /* We don't own the function end. */
1878 /* Get the first active insn, or THREAD, if it is an active insn. */
1879 active_insn = next_active_insn (PREV_INSN (thread));
1881 for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
1882 if (GET_CODE (insn) == CODE_LABEL
1883 && (insn != label || LABEL_NUSES (insn) != 1))
1886 if (allow_fallthrough)
1889 /* Ensure that we reach a BARRIER before any insn or label. */
1890 for (insn = prev_nonnote_insn (thread);
1891 insn == 0 || GET_CODE (insn) != BARRIER;
1892 insn = prev_nonnote_insn (insn))
1894 || GET_CODE (insn) == CODE_LABEL
1895 || (GET_CODE (insn) == INSN
1896 && GET_CODE (PATTERN (insn)) != USE
1897 && GET_CODE (PATTERN (insn)) != CLOBBER))
1903 /* Called when INSN is being moved from a location near the target of a jump.
1904 We leave a marker of the form (use (INSN)) immediately in front
1905 of WHERE for mark_target_live_regs. These markers will be deleted when
1908 We used to try to update the live status of registers if WHERE is at
1909 the start of a basic block, but that can't work since we may remove a
1910 BARRIER in relax_delay_slots. */
1913 update_block (rtx insn, rtx where)
1915 /* Ignore if this was in a delay slot and it came from the target of
1917 if (INSN_FROM_TARGET_P (insn))
1920 emit_insn_before (gen_rtx_USE (VOIDmode, insn), where);
1922 /* INSN might be making a value live in a block where it didn't use to
1923 be. So recompute liveness information for this block. */
1925 incr_ticks_for_insn (insn);
1928 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
1929 the basic block containing the jump. */
1932 reorg_redirect_jump (rtx jump, rtx nlabel)
1934 incr_ticks_for_insn (jump);
1935 return redirect_jump (jump, nlabel, 1);
1938 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
1939 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
1940 that reference values used in INSN. If we find one, then we move the
1941 REG_DEAD note to INSN.
1943 This is needed to handle the case where an later insn (after INSN) has a
1944 REG_DEAD note for a register used by INSN, and this later insn subsequently
1945 gets moved before a CODE_LABEL because it is a redundant insn. In this
1946 case, mark_target_live_regs may be confused into thinking the register
1947 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
1950 update_reg_dead_notes (rtx insn, rtx delayed_insn)
1954 for (p = next_nonnote_insn (insn); p != delayed_insn;
1955 p = next_nonnote_insn (p))
1956 for (link = REG_NOTES (p); link; link = next)
1958 next = XEXP (link, 1);
1960 if (REG_NOTE_KIND (link) != REG_DEAD
1961 || !REG_P (XEXP (link, 0)))
1964 if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
1966 /* Move the REG_DEAD note from P to INSN. */
1967 remove_note (p, link);
1968 XEXP (link, 1) = REG_NOTES (insn);
1969 REG_NOTES (insn) = link;
1974 /* Called when an insn redundant with start_insn is deleted. If there
1975 is a REG_DEAD note for the target of start_insn between start_insn
1976 and stop_insn, then the REG_DEAD note needs to be deleted since the
1977 value no longer dies there.
1979 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
1980 confused into thinking the register is dead. */
1983 fix_reg_dead_note (rtx start_insn, rtx stop_insn)
1987 for (p = next_nonnote_insn (start_insn); p != stop_insn;
1988 p = next_nonnote_insn (p))
1989 for (link = REG_NOTES (p); link; link = next)
1991 next = XEXP (link, 1);
1993 if (REG_NOTE_KIND (link) != REG_DEAD
1994 || !REG_P (XEXP (link, 0)))
1997 if (reg_set_p (XEXP (link, 0), PATTERN (start_insn)))
1999 remove_note (p, link);
2005 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
2007 This handles the case of udivmodXi4 instructions which optimize their
2008 output depending on whether any REG_UNUSED notes are present.
2009 we must make sure that INSN calculates as many results as REDUNDANT_INSN
2013 update_reg_unused_notes (rtx insn, rtx redundant_insn)
2017 for (link = REG_NOTES (insn); link; link = next)
2019 next = XEXP (link, 1);
2021 if (REG_NOTE_KIND (link) != REG_UNUSED
2022 || !REG_P (XEXP (link, 0)))
2025 if (! find_regno_note (redundant_insn, REG_UNUSED,
2026 REGNO (XEXP (link, 0))))
2027 remove_note (insn, link);
2031 /* Scan a function looking for insns that need a delay slot and find insns to
2032 put into the delay slot.
2034 NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such
2035 as calls). We do these first since we don't want jump insns (that are
2036 easier to fill) to get the only insns that could be used for non-jump insns.
2037 When it is zero, only try to fill JUMP_INSNs.
2039 When slots are filled in this manner, the insns (including the
2040 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2041 it is possible to tell whether a delay slot has really been filled
2042 or not. `final' knows how to deal with this, by communicating
2043 through FINAL_SEQUENCE. */
2046 fill_simple_delay_slots (int non_jumps_p)
2048 rtx insn, pat, trial, next_trial;
2050 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2051 struct resources needed, set;
2052 int slots_to_fill, slots_filled;
2055 for (i = 0; i < num_unfilled_slots; i++)
2058 /* Get the next insn to fill. If it has already had any slots assigned,
2059 we can't do anything with it. Maybe we'll improve this later. */
2061 insn = unfilled_slots_base[i];
2063 || INSN_DELETED_P (insn)
2064 || (GET_CODE (insn) == INSN
2065 && GET_CODE (PATTERN (insn)) == SEQUENCE)
2066 || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2067 || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2070 /* It may have been that this insn used to need delay slots, but
2071 now doesn't; ignore in that case. This can happen, for example,
2072 on the HP PA RISC, where the number of delay slots depends on
2073 what insns are nearby. */
2074 slots_to_fill = num_delay_slots (insn);
2076 /* Some machine description have defined instructions to have
2077 delay slots only in certain circumstances which may depend on
2078 nearby insns (which change due to reorg's actions).
2080 For example, the PA port normally has delay slots for unconditional
2083 However, the PA port claims such jumps do not have a delay slot
2084 if they are immediate successors of certain CALL_INSNs. This
2085 allows the port to favor filling the delay slot of the call with
2086 the unconditional jump. */
2087 if (slots_to_fill == 0)
2090 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2091 says how many. After initialization, first try optimizing
2094 nop add %o7,.-L1,%o7
2098 If this case applies, the delay slot of the call is filled with
2099 the unconditional jump. This is done first to avoid having the
2100 delay slot of the call filled in the backward scan. Also, since
2101 the unconditional jump is likely to also have a delay slot, that
2102 insn must exist when it is subsequently scanned.
2104 This is tried on each insn with delay slots as some machines
2105 have insns which perform calls, but are not represented as
2111 if (GET_CODE (insn) == JUMP_INSN)
2112 flags = get_jump_flags (insn, JUMP_LABEL (insn));
2114 flags = get_jump_flags (insn, NULL_RTX);
2116 if ((trial = next_active_insn (insn))
2117 && GET_CODE (trial) == JUMP_INSN
2118 && simplejump_p (trial)
2119 && eligible_for_delay (insn, slots_filled, trial, flags)
2120 && no_labels_between_p (insn, trial)
2121 && ! can_throw_internal (trial))
2125 delay_list = add_to_delay_list (trial, delay_list);
2127 /* TRIAL may have had its delay slot filled, then unfilled. When
2128 the delay slot is unfilled, TRIAL is placed back on the unfilled
2129 slots obstack. Unfortunately, it is placed on the end of the
2130 obstack, not in its original location. Therefore, we must search
2131 from entry i + 1 to the end of the unfilled slots obstack to
2132 try and find TRIAL. */
2133 tmp = &unfilled_slots_base[i + 1];
2134 while (*tmp != trial && tmp != unfilled_slots_next)
2137 /* Remove the unconditional jump from consideration for delay slot
2138 filling and unthread it. */
2142 rtx next = NEXT_INSN (trial);
2143 rtx prev = PREV_INSN (trial);
2145 NEXT_INSN (prev) = next;
2147 PREV_INSN (next) = prev;
2151 /* Now, scan backwards from the insn to search for a potential
2152 delay-slot candidate. Stop searching when a label or jump is hit.
2154 For each candidate, if it is to go into the delay slot (moved
2155 forward in execution sequence), it must not need or set any resources
2156 that were set by later insns and must not set any resources that
2157 are needed for those insns.
2159 The delay slot insn itself sets resources unless it is a call
2160 (in which case the called routine, not the insn itself, is doing
2163 if (slots_filled < slots_to_fill)
2165 CLEAR_RESOURCE (&needed);
2166 CLEAR_RESOURCE (&set);
2167 mark_set_resources (insn, &set, 0, MARK_SRC_DEST);
2168 mark_referenced_resources (insn, &needed, 0);
2170 for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2173 next_trial = prev_nonnote_insn (trial);
2175 /* This must be an INSN or CALL_INSN. */
2176 pat = PATTERN (trial);
2178 /* USE and CLOBBER at this level was just for flow; ignore it. */
2179 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2182 /* Check for resource conflict first, to avoid unnecessary
2184 if (! insn_references_resource_p (trial, &set, 1)
2185 && ! insn_sets_resource_p (trial, &set, 1)
2186 && ! insn_sets_resource_p (trial, &needed, 1)
2188 /* Can't separate set of cc0 from its use. */
2189 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2191 && ! can_throw_internal (trial))
2193 trial = try_split (pat, trial, 1);
2194 next_trial = prev_nonnote_insn (trial);
2195 if (eligible_for_delay (insn, slots_filled, trial, flags))
2197 /* In this case, we are searching backward, so if we
2198 find insns to put on the delay list, we want
2199 to put them at the head, rather than the
2200 tail, of the list. */
2202 update_reg_dead_notes (trial, insn);
2203 delay_list = gen_rtx_INSN_LIST (VOIDmode,
2205 update_block (trial, trial);
2206 delete_related_insns (trial);
2207 if (slots_to_fill == ++slots_filled)
2213 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2214 mark_referenced_resources (trial, &needed, 1);
2218 /* If all needed slots haven't been filled, we come here. */
2220 /* Try to optimize case of jumping around a single insn. */
2221 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2222 if (slots_filled != slots_to_fill
2224 && GET_CODE (insn) == JUMP_INSN
2225 && (condjump_p (insn) || condjump_in_parallel_p (insn)))
2227 delay_list = optimize_skip (insn);
2233 /* Try to get insns from beyond the insn needing the delay slot.
2234 These insns can neither set or reference resources set in insns being
2235 skipped, cannot set resources in the insn being skipped, and, if this
2236 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2237 call might not return).
2239 There used to be code which continued past the target label if
2240 we saw all uses of the target label. This code did not work,
2241 because it failed to account for some instructions which were
2242 both annulled and marked as from the target. This can happen as a
2243 result of optimize_skip. Since this code was redundant with
2244 fill_eager_delay_slots anyways, it was just deleted. */
2246 if (slots_filled != slots_to_fill
2247 /* If this instruction could throw an exception which is
2248 caught in the same function, then it's not safe to fill
2249 the delay slot with an instruction from beyond this
2250 point. For example, consider:
2261 Even though `i' is a local variable, we must be sure not
2262 to put `i = 3' in the delay slot if `f' might throw an
2265 Presumably, we should also check to see if we could get
2266 back to this function via `setjmp'. */
2267 && ! can_throw_internal (insn)
2268 && (GET_CODE (insn) != JUMP_INSN
2269 || ((condjump_p (insn) || condjump_in_parallel_p (insn))
2270 && ! simplejump_p (insn)
2271 && JUMP_LABEL (insn) != 0)))
2273 /* Invariant: If insn is a JUMP_INSN, the insn's jump
2274 label. Otherwise, zero. */
2276 int maybe_never = 0;
2277 rtx pat, trial_delay;
2279 CLEAR_RESOURCE (&needed);
2280 CLEAR_RESOURCE (&set);
2282 if (GET_CODE (insn) == CALL_INSN)
2284 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
2285 mark_referenced_resources (insn, &needed, 1);
2290 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
2291 mark_referenced_resources (insn, &needed, 1);
2292 if (GET_CODE (insn) == JUMP_INSN)
2293 target = JUMP_LABEL (insn);
2297 for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2299 next_trial = next_nonnote_insn (trial);
2301 if (GET_CODE (trial) == CODE_LABEL
2302 || GET_CODE (trial) == BARRIER)
2305 /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
2306 pat = PATTERN (trial);
2308 /* Stand-alone USE and CLOBBER are just for flow. */
2309 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2312 /* If this already has filled delay slots, get the insn needing
2314 if (GET_CODE (pat) == SEQUENCE)
2315 trial_delay = XVECEXP (pat, 0, 0);
2317 trial_delay = trial;
2319 /* Stop our search when seeing an unconditional jump. */
2320 if (GET_CODE (trial_delay) == JUMP_INSN)
2323 /* See if we have a resource problem before we try to
2325 if (GET_CODE (pat) != SEQUENCE
2326 && ! insn_references_resource_p (trial, &set, 1)
2327 && ! insn_sets_resource_p (trial, &set, 1)
2328 && ! insn_sets_resource_p (trial, &needed, 1)
2330 && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2332 && ! (maybe_never && may_trap_p (pat))
2333 && (trial = try_split (pat, trial, 0))
2334 && eligible_for_delay (insn, slots_filled, trial, flags)
2335 && ! can_throw_internal(trial))
2337 next_trial = next_nonnote_insn (trial);
2338 delay_list = add_to_delay_list (trial, delay_list);
2341 if (reg_mentioned_p (cc0_rtx, pat))
2342 link_cc0_insns (trial);
2345 delete_related_insns (trial);
2346 if (slots_to_fill == ++slots_filled)
2351 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2352 mark_referenced_resources (trial, &needed, 1);
2354 /* Ensure we don't put insns between the setting of cc and the
2355 comparison by moving a setting of cc into an earlier delay
2356 slot since these insns could clobber the condition code. */
2359 /* If this is a call or jump, we might not get here. */
2360 if (GET_CODE (trial_delay) == CALL_INSN
2361 || GET_CODE (trial_delay) == JUMP_INSN)
2365 /* If there are slots left to fill and our search was stopped by an
2366 unconditional branch, try the insn at the branch target. We can
2367 redirect the branch if it works.
2369 Don't do this if the insn at the branch target is a branch. */
2370 if (slots_to_fill != slots_filled
2372 && GET_CODE (trial) == JUMP_INSN
2373 && simplejump_p (trial)
2374 && (target == 0 || JUMP_LABEL (trial) == target)
2375 && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2376 && ! (GET_CODE (next_trial) == INSN
2377 && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2378 && GET_CODE (next_trial) != JUMP_INSN
2379 && ! insn_references_resource_p (next_trial, &set, 1)
2380 && ! insn_sets_resource_p (next_trial, &set, 1)
2381 && ! insn_sets_resource_p (next_trial, &needed, 1)
2383 && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2385 && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2386 && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2387 && eligible_for_delay (insn, slots_filled, next_trial, flags)
2388 && ! can_throw_internal (trial))
2390 /* See comment in relax_delay_slots about necessity of using
2391 next_real_insn here. */
2392 rtx new_label = next_real_insn (next_trial);
2395 new_label = get_label_before (new_label);
2397 new_label = find_end_label ();
2402 = add_to_delay_list (copy_rtx (next_trial), delay_list);
2404 reorg_redirect_jump (trial, new_label);
2406 /* If we merged because we both jumped to the same place,
2407 redirect the original insn also. */
2409 reorg_redirect_jump (insn, new_label);
2414 /* If this is an unconditional jump, then try to get insns from the
2415 target of the jump. */
2416 if (GET_CODE (insn) == JUMP_INSN
2417 && simplejump_p (insn)
2418 && slots_filled != slots_to_fill)
2420 = fill_slots_from_thread (insn, const_true_rtx,
2421 next_active_insn (JUMP_LABEL (insn)),
2423 own_thread_p (JUMP_LABEL (insn),
2424 JUMP_LABEL (insn), 0),
2425 slots_to_fill, &slots_filled,
2429 unfilled_slots_base[i]
2430 = emit_delay_sequence (insn, delay_list, slots_filled);
2432 if (slots_to_fill == slots_filled)
2433 unfilled_slots_base[i] = 0;
2435 note_delay_statistics (slots_filled, 0);
2438 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2439 /* See if the epilogue needs any delay slots. Try to fill them if so.
2440 The only thing we can do is scan backwards from the end of the
2441 function. If we did this in a previous pass, it is incorrect to do it
2443 if (current_function_epilogue_delay_list)
2446 slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2447 if (slots_to_fill == 0)
2451 CLEAR_RESOURCE (&set);
2453 /* The frame pointer and stack pointer are needed at the beginning of
2454 the epilogue, so instructions setting them can not be put in the
2455 epilogue delay slot. However, everything else needed at function
2456 end is safe, so we don't want to use end_of_function_needs here. */
2457 CLEAR_RESOURCE (&needed);
2458 if (frame_pointer_needed)
2460 SET_HARD_REG_BIT (needed.regs, FRAME_POINTER_REGNUM);
2461 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2462 SET_HARD_REG_BIT (needed.regs, HARD_FRAME_POINTER_REGNUM);
2464 if (! EXIT_IGNORE_STACK
2465 || current_function_sp_is_unchanging)
2466 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
2469 SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
2471 #ifdef EPILOGUE_USES
2472 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2474 if (EPILOGUE_USES (i))
2475 SET_HARD_REG_BIT (needed.regs, i);
2479 for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2480 trial = PREV_INSN (trial))
2482 if (GET_CODE (trial) == NOTE)
2484 pat = PATTERN (trial);
2485 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2488 if (! insn_references_resource_p (trial, &set, 1)
2489 && ! insn_sets_resource_p (trial, &needed, 1)
2490 && ! insn_sets_resource_p (trial, &set, 1)
2492 /* Don't want to mess with cc0 here. */
2493 && ! reg_mentioned_p (cc0_rtx, pat)
2495 && ! can_throw_internal (trial))
2497 trial = try_split (pat, trial, 1);
2498 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2500 /* Here as well we are searching backward, so put the
2501 insns we find on the head of the list. */
2503 current_function_epilogue_delay_list
2504 = gen_rtx_INSN_LIST (VOIDmode, trial,
2505 current_function_epilogue_delay_list);
2506 mark_end_of_function_resources (trial, 1);
2507 update_block (trial, trial);
2508 delete_related_insns (trial);
2510 /* Clear deleted bit so final.c will output the insn. */
2511 INSN_DELETED_P (trial) = 0;
2513 if (slots_to_fill == ++slots_filled)
2519 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2520 mark_referenced_resources (trial, &needed, 1);
2523 note_delay_statistics (slots_filled, 0);
2527 /* Try to find insns to place in delay slots.
2529 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2530 or is an unconditional branch if CONDITION is const_true_rtx.
2531 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2533 THREAD is a flow-of-control, either the insns to be executed if the
2534 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2536 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2537 to see if any potential delay slot insns set things needed there.
2539 LIKELY is nonzero if it is extremely likely that the branch will be
2540 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2541 end of a loop back up to the top.
2543 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2544 thread. I.e., it is the fallthrough code of our jump or the target of the
2545 jump when we are the only jump going there.
2547 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2548 case, we can only take insns from the head of the thread for our delay
2549 slot. We then adjust the jump to point after the insns we have taken. */
2552 fill_slots_from_thread (rtx insn, rtx condition, rtx thread,
2553 rtx opposite_thread, int likely, int thread_if_true,
2554 int own_thread, int slots_to_fill,
2555 int *pslots_filled, rtx delay_list)
2558 struct resources opposite_needed, set, needed;
2564 /* Validate our arguments. */
2565 if ((condition == const_true_rtx && ! thread_if_true)
2566 || (! own_thread && ! thread_if_true))
2569 flags = get_jump_flags (insn, JUMP_LABEL (insn));
2571 /* If our thread is the end of subroutine, we can't get any delay
2576 /* If this is an unconditional branch, nothing is needed at the
2577 opposite thread. Otherwise, compute what is needed there. */
2578 if (condition == const_true_rtx)
2579 CLEAR_RESOURCE (&opposite_needed);
2581 mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed);
2583 /* If the insn at THREAD can be split, do it here to avoid having to
2584 update THREAD and NEW_THREAD if it is done in the loop below. Also
2585 initialize NEW_THREAD. */
2587 new_thread = thread = try_split (PATTERN (thread), thread, 0);
2589 /* Scan insns at THREAD. We are looking for an insn that can be removed
2590 from THREAD (it neither sets nor references resources that were set
2591 ahead of it and it doesn't set anything needs by the insns ahead of
2592 it) and that either can be placed in an annulling insn or aren't
2593 needed at OPPOSITE_THREAD. */
2595 CLEAR_RESOURCE (&needed);
2596 CLEAR_RESOURCE (&set);
2598 /* If we do not own this thread, we must stop as soon as we find
2599 something that we can't put in a delay slot, since all we can do
2600 is branch into THREAD at a later point. Therefore, labels stop
2601 the search if this is not the `true' thread. */
2603 for (trial = thread;
2604 ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2605 trial = next_nonnote_insn (trial))
2609 /* If we have passed a label, we no longer own this thread. */
2610 if (GET_CODE (trial) == CODE_LABEL)
2616 pat = PATTERN (trial);
2617 if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2620 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2621 don't separate or copy insns that set and use CC0. */
2622 if (! insn_references_resource_p (trial, &set, 1)
2623 && ! insn_sets_resource_p (trial, &set, 1)
2624 && ! insn_sets_resource_p (trial, &needed, 1)
2626 && ! (reg_mentioned_p (cc0_rtx, pat)
2627 && (! own_thread || ! sets_cc0_p (pat)))
2629 && ! can_throw_internal (trial))
2633 /* If TRIAL is redundant with some insn before INSN, we don't
2634 actually need to add it to the delay list; we can merely pretend
2636 if ((prior_insn = redundant_insn (trial, insn, delay_list)))
2638 fix_reg_dead_note (prior_insn, insn);
2641 update_block (trial, thread);
2642 if (trial == thread)
2644 thread = next_active_insn (thread);
2645 if (new_thread == trial)
2646 new_thread = thread;
2649 delete_related_insns (trial);
2653 update_reg_unused_notes (prior_insn, trial);
2654 new_thread = next_active_insn (trial);
2660 /* There are two ways we can win: If TRIAL doesn't set anything
2661 needed at the opposite thread and can't trap, or if it can
2662 go into an annulled delay slot. */
2664 && (condition == const_true_rtx
2665 || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2666 && ! may_trap_p (pat))))
2669 trial = try_split (pat, trial, 0);
2670 if (new_thread == old_trial)
2672 if (thread == old_trial)
2674 pat = PATTERN (trial);
2675 if (eligible_for_delay (insn, *pslots_filled, trial, flags))
2679 #ifdef ANNUL_IFTRUE_SLOTS
2682 #ifdef ANNUL_IFFALSE_SLOTS
2688 trial = try_split (pat, trial, 0);
2689 if (new_thread == old_trial)
2691 if (thread == old_trial)
2693 pat = PATTERN (trial);
2694 if ((must_annul || delay_list == NULL) && (thread_if_true
2695 ? check_annul_list_true_false (0, delay_list)
2696 && eligible_for_annul_false (insn, *pslots_filled, trial, flags)
2697 : check_annul_list_true_false (1, delay_list)
2698 && eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
2706 if (reg_mentioned_p (cc0_rtx, pat))
2707 link_cc0_insns (trial);
2710 /* If we own this thread, delete the insn. If this is the
2711 destination of a branch, show that a basic block status
2712 may have been updated. In any case, mark the new
2713 starting point of this thread. */
2718 update_block (trial, thread);
2719 if (trial == thread)
2721 thread = next_active_insn (thread);
2722 if (new_thread == trial)
2723 new_thread = thread;
2726 /* We are moving this insn, not deleting it. We must
2727 temporarily increment the use count on any referenced
2728 label lest it be deleted by delete_related_insns. */
2729 note = find_reg_note (trial, REG_LABEL, 0);
2730 /* REG_LABEL could be NOTE_INSN_DELETED_LABEL too. */
2731 if (note && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2732 LABEL_NUSES (XEXP (note, 0))++;
2734 delete_related_insns (trial);
2736 if (note && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2737 LABEL_NUSES (XEXP (note, 0))--;
2740 new_thread = next_active_insn (trial);
2742 temp = own_thread ? trial : copy_rtx (trial);
2744 INSN_FROM_TARGET_P (temp) = 1;
2746 delay_list = add_to_delay_list (temp, delay_list);
2748 if (slots_to_fill == ++(*pslots_filled))
2750 /* Even though we have filled all the slots, we
2751 may be branching to a location that has a
2752 redundant insn. Skip any if so. */
2753 while (new_thread && ! own_thread
2754 && ! insn_sets_resource_p (new_thread, &set, 1)
2755 && ! insn_sets_resource_p (new_thread, &needed, 1)
2756 && ! insn_references_resource_p (new_thread,
2759 = redundant_insn (new_thread, insn,
2762 /* We know we do not own the thread, so no need
2763 to call update_block and delete_insn. */
2764 fix_reg_dead_note (prior_insn, insn);
2765 update_reg_unused_notes (prior_insn, new_thread);
2766 new_thread = next_active_insn (new_thread);
2776 /* This insn can't go into a delay slot. */
2778 mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2779 mark_referenced_resources (trial, &needed, 1);
2781 /* Ensure we don't put insns between the setting of cc and the comparison
2782 by moving a setting of cc into an earlier delay slot since these insns
2783 could clobber the condition code. */
2786 /* If this insn is a register-register copy and the next insn has
2787 a use of our destination, change it to use our source. That way,
2788 it will become a candidate for our delay slot the next time
2789 through this loop. This case occurs commonly in loops that
2792 We could check for more complex cases than those tested below,
2793 but it doesn't seem worth it. It might also be a good idea to try
2794 to swap the two insns. That might do better.
2796 We can't do this if the next insn modifies our destination, because
2797 that would make the replacement into the insn invalid. We also can't
2798 do this if it modifies our source, because it might be an earlyclobber
2799 operand. This latter test also prevents updating the contents of
2800 a PRE_INC. We also can't do this if there's overlap of source and
2801 destination. Overlap may happen for larger-than-register-size modes. */
2803 if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2804 && REG_P (SET_SRC (pat))
2805 && REG_P (SET_DEST (pat))
2806 && !reg_overlap_mentioned_p (SET_DEST (pat), SET_SRC (pat)))
2808 rtx next = next_nonnote_insn (trial);
2810 if (next && GET_CODE (next) == INSN
2811 && GET_CODE (PATTERN (next)) != USE
2812 && ! reg_set_p (SET_DEST (pat), next)
2813 && ! reg_set_p (SET_SRC (pat), next)
2814 && reg_referenced_p (SET_DEST (pat), PATTERN (next))
2815 && ! modified_in_p (SET_DEST (pat), next))
2816 validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2820 /* If we stopped on a branch insn that has delay slots, see if we can
2821 steal some of the insns in those slots. */
2822 if (trial && GET_CODE (trial) == INSN
2823 && GET_CODE (PATTERN (trial)) == SEQUENCE
2824 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2826 /* If this is the `true' thread, we will want to follow the jump,
2827 so we can only do this if we have taken everything up to here. */
2828 if (thread_if_true && trial == new_thread)
2831 = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2832 delay_list, &set, &needed,
2833 &opposite_needed, slots_to_fill,
2834 pslots_filled, &must_annul,
2836 /* If we owned the thread and are told that it branched
2837 elsewhere, make sure we own the thread at the new location. */
2838 if (own_thread && trial != new_thread)
2839 own_thread = own_thread_p (new_thread, new_thread, 0);
2841 else if (! thread_if_true)
2843 = steal_delay_list_from_fallthrough (insn, condition,
2845 delay_list, &set, &needed,
2846 &opposite_needed, slots_to_fill,
2847 pslots_filled, &must_annul);
2850 /* If we haven't found anything for this delay slot and it is very
2851 likely that the branch will be taken, see if the insn at our target
2852 increments or decrements a register with an increment that does not
2853 depend on the destination register. If so, try to place the opposite
2854 arithmetic insn after the jump insn and put the arithmetic insn in the
2855 delay slot. If we can't do this, return. */
2856 if (delay_list == 0 && likely && new_thread
2857 && GET_CODE (new_thread) == INSN
2858 && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
2859 && asm_noperands (PATTERN (new_thread)) < 0)
2861 rtx pat = PATTERN (new_thread);
2866 pat = PATTERN (trial);
2868 if (GET_CODE (trial) != INSN
2869 || GET_CODE (pat) != SET
2870 || ! eligible_for_delay (insn, 0, trial, flags)
2871 || can_throw_internal (trial))
2874 dest = SET_DEST (pat), src = SET_SRC (pat);
2875 if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2876 && rtx_equal_p (XEXP (src, 0), dest)
2877 && ! reg_overlap_mentioned_p (dest, XEXP (src, 1))
2878 && ! side_effects_p (pat))
2880 rtx other = XEXP (src, 1);
2884 /* If this is a constant adjustment, use the same code with
2885 the negated constant. Otherwise, reverse the sense of the
2887 if (GET_CODE (other) == CONST_INT)
2888 new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
2889 negate_rtx (GET_MODE (src), other));
2891 new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
2892 GET_MODE (src), dest, other);
2894 ninsn = emit_insn_after (gen_rtx_SET (VOIDmode, dest, new_arith),
2897 if (recog_memoized (ninsn) < 0
2898 || (extract_insn (ninsn), ! constrain_operands (1)))
2900 delete_related_insns (ninsn);
2906 update_block (trial, thread);
2907 if (trial == thread)
2909 thread = next_active_insn (thread);
2910 if (new_thread == trial)
2911 new_thread = thread;
2913 delete_related_insns (trial);
2916 new_thread = next_active_insn (trial);
2918 ninsn = own_thread ? trial : copy_rtx (trial);
2920 INSN_FROM_TARGET_P (ninsn) = 1;
2922 delay_list = add_to_delay_list (ninsn, NULL_RTX);
2927 if (delay_list && must_annul)
2928 INSN_ANNULLED_BRANCH_P (insn) = 1;
2930 /* If we are to branch into the middle of this thread, find an appropriate
2931 label or make a new one if none, and redirect INSN to it. If we hit the
2932 end of the function, use the end-of-function label. */
2933 if (new_thread != thread)
2937 if (! thread_if_true)
2940 if (new_thread && GET_CODE (new_thread) == JUMP_INSN
2941 && (simplejump_p (new_thread)
2942 || GET_CODE (PATTERN (new_thread)) == RETURN)
2943 && redirect_with_delay_list_safe_p (insn,
2944 JUMP_LABEL (new_thread),
2946 new_thread = follow_jumps (JUMP_LABEL (new_thread));
2948 if (new_thread == 0)
2949 label = find_end_label ();
2950 else if (GET_CODE (new_thread) == CODE_LABEL)
2953 label = get_label_before (new_thread);
2956 reorg_redirect_jump (insn, label);
2962 /* Make another attempt to find insns to place in delay slots.
2964 We previously looked for insns located in front of the delay insn
2965 and, for non-jump delay insns, located behind the delay insn.
2967 Here only try to schedule jump insns and try to move insns from either
2968 the target or the following insns into the delay slot. If annulling is
2969 supported, we will be likely to do this. Otherwise, we can do this only
2973 fill_eager_delay_slots (void)
2977 int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2979 for (i = 0; i < num_unfilled_slots; i++)
2982 rtx target_label, insn_at_target, fallthrough_insn;
2985 int own_fallthrough;
2986 int prediction, slots_to_fill, slots_filled;
2988 insn = unfilled_slots_base[i];
2990 || INSN_DELETED_P (insn)
2991 || GET_CODE (insn) != JUMP_INSN
2992 || ! (condjump_p (insn) || condjump_in_parallel_p (insn)))
2995 slots_to_fill = num_delay_slots (insn);
2996 /* Some machine description have defined instructions to have
2997 delay slots only in certain circumstances which may depend on
2998 nearby insns (which change due to reorg's actions).
3000 For example, the PA port normally has delay slots for unconditional
3003 However, the PA port claims such jumps do not have a delay slot
3004 if they are immediate successors of certain CALL_INSNs. This
3005 allows the port to favor filling the delay slot of the call with
3006 the unconditional jump. */
3007 if (slots_to_fill == 0)
3011 target_label = JUMP_LABEL (insn);
3012 condition = get_branch_condition (insn, target_label);
3017 /* Get the next active fallthrough and target insns and see if we own
3018 them. Then see whether the branch is likely true. We don't need
3019 to do a lot of this for unconditional branches. */
3021 insn_at_target = next_active_insn (target_label);
3022 own_target = own_thread_p (target_label, target_label, 0);
3024 if (condition == const_true_rtx)
3026 own_fallthrough = 0;
3027 fallthrough_insn = 0;
3032 fallthrough_insn = next_active_insn (insn);
3033 own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
3034 prediction = mostly_true_jump (insn, condition);
3037 /* If this insn is expected to branch, first try to get insns from our
3038 target, then our fallthrough insns. If it is not expected to branch,
3039 try the other order. */
3044 = fill_slots_from_thread (insn, condition, insn_at_target,
3045 fallthrough_insn, prediction == 2, 1,
3047 slots_to_fill, &slots_filled, delay_list);
3049 if (delay_list == 0 && own_fallthrough)
3051 /* Even though we didn't find anything for delay slots,
3052 we might have found a redundant insn which we deleted
3053 from the thread that was filled. So we have to recompute
3054 the next insn at the target. */
3055 target_label = JUMP_LABEL (insn);
3056 insn_at_target = next_active_insn (target_label);
3059 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3060 insn_at_target, 0, 0,
3062 slots_to_fill, &slots_filled,
3068 if (own_fallthrough)
3070 = fill_slots_from_thread (insn, condition, fallthrough_insn,
3071 insn_at_target, 0, 0,
3073 slots_to_fill, &slots_filled,
3076 if (delay_list == 0)
3078 = fill_slots_from_thread (insn, condition, insn_at_target,
3079 next_active_insn (insn), 0, 1,
3081 slots_to_fill, &slots_filled,
3086 unfilled_slots_base[i]
3087 = emit_delay_sequence (insn, delay_list, slots_filled);
3089 if (slots_to_fill == slots_filled)
3090 unfilled_slots_base[i] = 0;
3092 note_delay_statistics (slots_filled, 1);
3096 /* Once we have tried two ways to fill a delay slot, make a pass over the
3097 code to try to improve the results and to do such things as more jump
3101 relax_delay_slots (rtx first)
3103 rtx insn, next, pat;
3104 rtx trial, delay_insn, target_label;
3106 /* Look at every JUMP_INSN and see if we can improve it. */
3107 for (insn = first; insn; insn = next)
3111 next = next_active_insn (insn);
3113 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3114 the next insn, or jumps to a label that is not the last of a
3115 group of consecutive labels. */
3116 if (GET_CODE (insn) == JUMP_INSN
3117 && (condjump_p (insn) || condjump_in_parallel_p (insn))
3118 && (target_label = JUMP_LABEL (insn)) != 0)
3120 target_label = skip_consecutive_labels (follow_jumps (target_label));
3121 if (target_label == 0)
3122 target_label = find_end_label ();
3124 if (target_label && next_active_insn (target_label) == next
3125 && ! condjump_in_parallel_p (insn))
3131 if (target_label && target_label != JUMP_LABEL (insn))
3132 reorg_redirect_jump (insn, target_label);
3134 /* See if this jump branches around an unconditional jump.
3135 If so, invert this jump and point it to the target of the
3137 if (next && GET_CODE (next) == JUMP_INSN
3138 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3140 && next_active_insn (target_label) == next_active_insn (next)
3141 && no_labels_between_p (insn, next))
3143 rtx label = JUMP_LABEL (next);
3145 /* Be careful how we do this to avoid deleting code or
3146 labels that are momentarily dead. See similar optimization
3149 We also need to ensure we properly handle the case when
3150 invert_jump fails. */
3152 ++LABEL_NUSES (target_label);
3154 ++LABEL_NUSES (label);
3156 if (invert_jump (insn, label, 1))
3158 delete_related_insns (next);
3163 --LABEL_NUSES (label);
3165 if (--LABEL_NUSES (target_label) == 0)
3166 delete_related_insns (target_label);
3172 /* If this is an unconditional jump and the previous insn is a
3173 conditional jump, try reversing the condition of the previous
3174 insn and swapping our targets. The next pass might be able to
3177 Don't do this if we expect the conditional branch to be true, because
3178 we would then be making the more common case longer. */
3180 if (GET_CODE (insn) == JUMP_INSN
3181 && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3182 && (other = prev_active_insn (insn)) != 0
3183 && (condjump_p (other) || condjump_in_parallel_p (other))
3184 && no_labels_between_p (other, insn)
3185 && 0 > mostly_true_jump (other,
3186 get_branch_condition (other,
3187 JUMP_LABEL (other))))
3189 rtx other_target = JUMP_LABEL (other);
3190 target_label = JUMP_LABEL (insn);
3192 if (invert_jump (other, target_label, 0))
3193 reorg_redirect_jump (insn, other_target);
3196 /* Now look only at cases where we have filled a delay slot. */
3197 if (GET_CODE (insn) != INSN
3198 || GET_CODE (PATTERN (insn)) != SEQUENCE)
3201 pat = PATTERN (insn);
3202 delay_insn = XVECEXP (pat, 0, 0);
3204 /* See if the first insn in the delay slot is redundant with some
3205 previous insn. Remove it from the delay slot if so; then set up
3206 to reprocess this insn. */
3207 if (redundant_insn (XVECEXP (pat, 0, 1), delay_insn, 0))
3209 delete_from_delay_slot (XVECEXP (pat, 0, 1));
3210 next = prev_active_insn (next);
3214 /* See if we have a RETURN insn with a filled delay slot followed
3215 by a RETURN insn with an unfilled a delay slot. If so, we can delete
3216 the first RETURN (but not its delay insn). This gives the same
3217 effect in fewer instructions.
3219 Only do so if optimizing for size since this results in slower, but
3222 && GET_CODE (PATTERN (delay_insn)) == RETURN
3224 && GET_CODE (next) == JUMP_INSN
3225 && GET_CODE (PATTERN (next)) == RETURN)
3230 /* Delete the RETURN and just execute the delay list insns.
3232 We do this by deleting the INSN containing the SEQUENCE, then
3233 re-emitting the insns separately, and then deleting the RETURN.
3234 This allows the count of the jump target to be properly
3237 /* Clear the from target bit, since these insns are no longer
3239 for (i = 0; i < XVECLEN (pat, 0); i++)
3240 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3242 trial = PREV_INSN (insn);
3243 delete_related_insns (insn);
3244 if (GET_CODE (pat) != SEQUENCE)
3247 for (i = 0; i < XVECLEN (pat, 0); i++)
3249 rtx this_insn = XVECEXP (pat, 0, i);
3250 add_insn_after (this_insn, after);
3253 delete_scheduled_jump (delay_insn);
3257 /* Now look only at the cases where we have a filled JUMP_INSN. */
3258 if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3259 || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0))
3260 || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0))))
3263 target_label = JUMP_LABEL (delay_insn);
3267 /* If this jump goes to another unconditional jump, thread it, but
3268 don't convert a jump into a RETURN here. */
3269 trial = skip_consecutive_labels (follow_jumps (target_label));
3271 trial = find_end_label ();
3273 if (trial && trial != target_label
3274 && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
3276 reorg_redirect_jump (delay_insn, trial);
3277 target_label = trial;
3280 /* If the first insn at TARGET_LABEL is redundant with a previous
3281 insn, redirect the jump to the following insn process again. */
3282 trial = next_active_insn (target_label);
3283 if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3284 && redundant_insn (trial, insn, 0)
3285 && ! can_throw_internal (trial))
3287 /* Figure out where to emit the special USE insn so we don't
3288 later incorrectly compute register live/death info. */
3289 rtx tmp = next_active_insn (trial);
3291 tmp = find_end_label ();
3295 /* Insert the special USE insn and update dataflow info. */
3296 update_block (trial, tmp);
3298 /* Now emit a label before the special USE insn, and
3299 redirect our jump to the new label. */
3300 target_label = get_label_before (PREV_INSN (tmp));
3301 reorg_redirect_jump (delay_insn, target_label);
3307 /* Similarly, if it is an unconditional jump with one insn in its
3308 delay list and that insn is redundant, thread the jump. */
3309 if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3310 && XVECLEN (PATTERN (trial), 0) == 2
3311 && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3312 && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3313 || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3314 && redundant_insn (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3316 target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3317 if (target_label == 0)
3318 target_label = find_end_label ();
3321 && redirect_with_delay_slots_safe_p (delay_insn, target_label,
3324 reorg_redirect_jump (delay_insn, target_label);
3331 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3332 && prev_active_insn (target_label) == insn
3333 && ! condjump_in_parallel_p (delay_insn)
3335 /* If the last insn in the delay slot sets CC0 for some insn,
3336 various code assumes that it is in a delay slot. We could
3337 put it back where it belonged and delete the register notes,
3338 but it doesn't seem worthwhile in this uncommon case. */
3339 && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3340 REG_CC_USER, NULL_RTX)
3347 /* All this insn does is execute its delay list and jump to the
3348 following insn. So delete the jump and just execute the delay
3351 We do this by deleting the INSN containing the SEQUENCE, then
3352 re-emitting the insns separately, and then deleting the jump.
3353 This allows the count of the jump target to be properly
3356 /* Clear the from target bit, since these insns are no longer
3358 for (i = 0; i < XVECLEN (pat, 0); i++)
3359 INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3361 trial = PREV_INSN (insn);
3362 delete_related_insns (insn);
3363 if (GET_CODE (pat) != SEQUENCE)
3366 for (i = 0; i < XVECLEN (pat, 0); i++)
3368 rtx this_insn = XVECEXP (pat, 0, i);
3369 add_insn_after (this_insn, after);
3372 delete_scheduled_jump (delay_insn);
3376 /* See if this is an unconditional jump around a single insn which is
3377 identical to the one in its delay slot. In this case, we can just
3378 delete the branch and the insn in its delay slot. */
3379 if (next && GET_CODE (next) == INSN
3380 && prev_label (next_active_insn (next)) == target_label
3381 && simplejump_p (insn)
3382 && XVECLEN (pat, 0) == 2
3383 && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
3385 delete_related_insns (insn);
3389 /* See if this jump (with its delay slots) branches around another
3390 jump (without delay slots). If so, invert this jump and point
3391 it to the target of the second jump. We cannot do this for
3392 annulled jumps, though. Again, don't convert a jump to a RETURN
3394 if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3395 && next && GET_CODE (next) == JUMP_INSN
3396 && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3397 && next_active_insn (target_label) == next_active_insn (next)
3398 && no_labels_between_p (insn, next))
3400 rtx label = JUMP_LABEL (next);
3401 rtx old_label = JUMP_LABEL (delay_insn);
3404 label = find_end_label ();
3406 /* find_end_label can generate a new label. Check this first. */
3408 && no_labels_between_p (insn, next)
3409 && redirect_with_delay_slots_safe_p (delay_insn, label, insn))
3411 /* Be careful how we do this to avoid deleting code or labels
3412 that are momentarily dead. See similar optimization in
3415 ++LABEL_NUSES (old_label);
3417 if (invert_jump (delay_insn, label, 1))
3421 /* Must update the INSN_FROM_TARGET_P bits now that
3422 the branch is reversed, so that mark_target_live_regs
3423 will handle the delay slot insn correctly. */
3424 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
3426 rtx slot = XVECEXP (PATTERN (insn), 0, i);
3427 INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
3430 delete_related_insns (next);
3434 if (old_label && --LABEL_NUSES (old_label) == 0)
3435 delete_related_insns (old_label);
3440 /* If we own the thread opposite the way this insn branches, see if we
3441 can merge its delay slots with following insns. */
3442 if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3443 && own_thread_p (NEXT_INSN (insn), 0, 1))
3444 try_merge_delay_insns (insn, next);
3445 else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3446 && own_thread_p (target_label, target_label, 0))
3447 try_merge_delay_insns (insn, next_active_insn (target_label));
3449 /* If we get here, we haven't deleted INSN. But we may have deleted
3450 NEXT, so recompute it. */
3451 next = next_active_insn (insn);
3457 /* Look for filled jumps to the end of function label. We can try to convert
3458 them into RETURN insns if the insns in the delay slot are valid for the
3462 make_return_insns (rtx first)
3464 rtx insn, jump_insn, pat;
3465 rtx real_return_label = end_of_function_label;
3468 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3469 /* If a previous pass filled delay slots in the epilogue, things get a
3470 bit more complicated, as those filler insns would generally (without
3471 data flow analysis) have to be executed after any existing branch
3472 delay slot filler insns. It is also unknown whether such a
3473 transformation would actually be profitable. Note that the existing
3474 code only cares for branches with (some) filled delay slots. */
3475 if (current_function_epilogue_delay_list != NULL)
3479 /* See if there is a RETURN insn in the function other than the one we
3480 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3481 into a RETURN to jump to it. */
3482 for (insn = first; insn; insn = NEXT_INSN (insn))
3483 if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3485 real_return_label = get_label_before (insn);
3489 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3490 was equal to END_OF_FUNCTION_LABEL. */
3491 LABEL_NUSES (real_return_label)++;
3493 /* Clear the list of insns to fill so we can use it. */
3494 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3496 for (insn = first; insn; insn = NEXT_INSN (insn))
3500 /* Only look at filled JUMP_INSNs that go to the end of function
3502 if (GET_CODE (insn) != INSN
3503 || GET_CODE (PATTERN (insn)) != SEQUENCE
3504 || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3505 || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3508 pat = PATTERN (insn);
3509 jump_insn = XVECEXP (pat, 0, 0);
3511 /* If we can't make the jump into a RETURN, try to redirect it to the best
3512 RETURN and go on to the next insn. */
3513 if (! reorg_redirect_jump (jump_insn, NULL_RTX))
3515 /* Make sure redirecting the jump will not invalidate the delay
3517 if (redirect_with_delay_slots_safe_p (jump_insn,
3520 reorg_redirect_jump (jump_insn, real_return_label);
3524 /* See if this RETURN can accept the insns current in its delay slot.
3525 It can if it has more or an equal number of slots and the contents
3526 of each is valid. */
3528 flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
3529 slots = num_delay_slots (jump_insn);
3530 if (slots >= XVECLEN (pat, 0) - 1)
3532 for (i = 1; i < XVECLEN (pat, 0); i++)
3534 #ifdef ANNUL_IFFALSE_SLOTS
3535 (INSN_ANNULLED_BRANCH_P (jump_insn)
3536 && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3537 ? eligible_for_annul_false (jump_insn, i - 1,
3538 XVECEXP (pat, 0, i), flags) :
3540 #ifdef ANNUL_IFTRUE_SLOTS
3541 (INSN_ANNULLED_BRANCH_P (jump_insn)
3542 && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3543 ? eligible_for_annul_true (jump_insn, i - 1,
3544 XVECEXP (pat, 0, i), flags) :
3546 eligible_for_delay (jump_insn, i - 1,
3547 XVECEXP (pat, 0, i), flags)))
3553 if (i == XVECLEN (pat, 0))
3556 /* We have to do something with this insn. If it is an unconditional
3557 RETURN, delete the SEQUENCE and output the individual insns,
3558 followed by the RETURN. Then set things up so we try to find
3559 insns for its delay slots, if it needs some. */
3560 if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3562 rtx prev = PREV_INSN (insn);
3564 delete_related_insns (insn);
3565 for (i = 1; i < XVECLEN (pat, 0); i++)
3566 prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3568 insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3569 emit_barrier_after (insn);
3572 obstack_ptr_grow (&unfilled_slots_obstack, insn);
3575 /* It is probably more efficient to keep this with its current
3576 delay slot as a branch to a RETURN. */
3577 reorg_redirect_jump (jump_insn, real_return_label);
3580 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3581 new delay slots we have created. */
3582 if (--LABEL_NUSES (real_return_label) == 0)
3583 delete_related_insns (real_return_label);
3585 fill_simple_delay_slots (1);
3586 fill_simple_delay_slots (0);
3590 /* Try to find insns to place in delay slots. */
3593 dbr_schedule (rtx first, FILE *file)
3595 rtx insn, next, epilogue_insn = 0;
3598 int old_flag_no_peephole = flag_no_peephole;
3600 /* Execute `final' once in prescan mode to delete any insns that won't be
3601 used. Don't let final try to do any peephole optimization--it will
3602 ruin dataflow information for this pass. */
3604 flag_no_peephole = 1;
3605 final (first, 0, NO_DEBUG, 1, 1);
3606 flag_no_peephole = old_flag_no_peephole;
3609 /* If the current function has no insns other than the prologue and
3610 epilogue, then do not try to fill any delay slots. */
3611 if (n_basic_blocks == 0)
3614 /* Find the highest INSN_UID and allocate and initialize our map from
3615 INSN_UID's to position in code. */
3616 for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3618 if (INSN_UID (insn) > max_uid)
3619 max_uid = INSN_UID (insn);
3620 if (GET_CODE (insn) == NOTE
3621 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
3622 epilogue_insn = insn;
3625 uid_to_ruid = xmalloc ((max_uid + 1) * sizeof (int));
3626 for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3627 uid_to_ruid[INSN_UID (insn)] = i;
3629 /* Initialize the list of insns that need filling. */
3630 if (unfilled_firstobj == 0)
3632 gcc_obstack_init (&unfilled_slots_obstack);
3633 unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0);
3636 for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3640 INSN_ANNULLED_BRANCH_P (insn) = 0;
3641 INSN_FROM_TARGET_P (insn) = 0;
3643 /* Skip vector tables. We can't get attributes for them. */
3644 if (GET_CODE (insn) == JUMP_INSN
3645 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3646 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3649 if (num_delay_slots (insn) > 0)
3650 obstack_ptr_grow (&unfilled_slots_obstack, insn);
3652 /* Ensure all jumps go to the last of a set of consecutive labels. */
3653 if (GET_CODE (insn) == JUMP_INSN
3654 && (condjump_p (insn) || condjump_in_parallel_p (insn))
3655 && JUMP_LABEL (insn) != 0
3656 && ((target = skip_consecutive_labels (JUMP_LABEL (insn)))
3657 != JUMP_LABEL (insn)))
3658 redirect_jump (insn, target, 1);
3661 init_resource_info (epilogue_insn);
3663 /* Show we haven't computed an end-of-function label yet. */
3664 end_of_function_label = 0;
3666 /* Initialize the statistics for this function. */
3667 memset (num_insns_needing_delays, 0, sizeof num_insns_needing_delays);
3668 memset (num_filled_delays, 0, sizeof num_filled_delays);
3670 /* Now do the delay slot filling. Try everything twice in case earlier
3671 changes make more slots fillable. */
3673 for (reorg_pass_number = 0;
3674 reorg_pass_number < MAX_REORG_PASSES;
3675 reorg_pass_number++)
3677 fill_simple_delay_slots (1);
3678 fill_simple_delay_slots (0);
3679 fill_eager_delay_slots ();
3680 relax_delay_slots (first);
3683 /* Delete any USE insns made by update_block; subsequent passes don't need
3684 them or know how to deal with them. */
3685 for (insn = first; insn; insn = next)
3687 next = NEXT_INSN (insn);
3689 if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3690 && INSN_P (XEXP (PATTERN (insn), 0)))
3691 next = delete_related_insns (insn);
3694 /* If we made an end of function label, indicate that it is now
3695 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3696 If it is now unused, delete it. */
3697 if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3698 delete_related_insns (end_of_function_label);
3701 if (HAVE_return && end_of_function_label != 0)
3702 make_return_insns (first);
3705 obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3707 /* It is not clear why the line below is needed, but it does seem to be. */
3708 unfilled_firstobj = obstack_alloc (&unfilled_slots_obstack, 0);
3712 int i, j, need_comma;
3713 int total_delay_slots[MAX_DELAY_HISTOGRAM + 1];
3714 int total_annul_slots[MAX_DELAY_HISTOGRAM + 1];
3716 for (reorg_pass_number = 0;
3717 reorg_pass_number < MAX_REORG_PASSES;
3718 reorg_pass_number++)
3720 fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3721 for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3724 fprintf (file, ";; Reorg function #%d\n", i);
3726 fprintf (file, ";; %d insns needing delay slots\n;; ",
3727 num_insns_needing_delays[i][reorg_pass_number]);
3729 for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3730 if (num_filled_delays[i][j][reorg_pass_number])
3733 fprintf (file, ", ");
3735 fprintf (file, "%d got %d delays",
3736 num_filled_delays[i][j][reorg_pass_number], j);
3738 fprintf (file, "\n");
3741 memset (total_delay_slots, 0, sizeof total_delay_slots);
3742 memset (total_annul_slots, 0, sizeof total_annul_slots);
3743 for (insn = first; insn; insn = NEXT_INSN (insn))
3745 if (! INSN_DELETED_P (insn)
3746 && GET_CODE (insn) == INSN
3747 && GET_CODE (PATTERN (insn)) != USE
3748 && GET_CODE (PATTERN (insn)) != CLOBBER)
3750 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
3752 j = XVECLEN (PATTERN (insn), 0) - 1;
3753 if (j > MAX_DELAY_HISTOGRAM)
3754 j = MAX_DELAY_HISTOGRAM;
3755 if (INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (insn), 0, 0)))
3756 total_annul_slots[j]++;
3758 total_delay_slots[j]++;
3760 else if (num_delay_slots (insn) > 0)
3761 total_delay_slots[0]++;
3764 fprintf (file, ";; Reorg totals: ");
3766 for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3768 if (total_delay_slots[j])
3771 fprintf (file, ", ");
3773 fprintf (file, "%d got %d delays", total_delay_slots[j], j);
3776 fprintf (file, "\n");
3777 #if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
3778 fprintf (file, ";; Reorg annuls: ");
3780 for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3782 if (total_annul_slots[j])
3785 fprintf (file, ", ");
3787 fprintf (file, "%d got %d delays", total_annul_slots[j], j);
3790 fprintf (file, "\n");
3792 fprintf (file, "\n");
3795 /* For all JUMP insns, fill in branch prediction notes, so that during
3796 assembler output a target can set branch prediction bits in the code.
3797 We have to do this now, as up until this point the destinations of
3798 JUMPS can be moved around and changed, but past right here that cannot
3800 for (insn = first; insn; insn = NEXT_INSN (insn))
3804 if (GET_CODE (insn) == INSN)
3806 rtx pat = PATTERN (insn);
3808 if (GET_CODE (pat) == SEQUENCE)
3809 insn = XVECEXP (pat, 0, 0);
3811 if (GET_CODE (insn) != JUMP_INSN)
3814 pred_flags = get_jump_flags (insn, JUMP_LABEL (insn));
3815 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PRED,
3816 GEN_INT (pred_flags),
3819 free_resource_info ();
3821 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3822 /* SPARC assembler, for instance, emit warning when debug info is output
3823 into the delay slot. */
3827 for (link = current_function_epilogue_delay_list;
3829 link = XEXP (link, 1))
3830 INSN_LOCATOR (XEXP (link, 0)) = 0;
3834 #endif /* DELAY_SLOTS */